title: Is lseek() O(1) complexity?
body: <p>I know that my question has an answer here: <a href="https://stackoverflow.com/questions/6171403/qfile-seek-performance">QFile seek performance</a>. But I am not completely satisfied with the answer. Even after looking at the following implementation of <code>generic_file_llseek()</code> for ext4, I can't seem to understand how can the complexity be measured.</p>
  
  <pre><code>/**
   * generic_file_llseek - generic llseek implementation for regular files
   * @file:       file structure to seek on
   * @offset:     file offset to seek to
   * @origin:     type of seek
   *
   * This is a generic implemenation of -&gt;llseek useable for all normal local
   * filesystems.  It just updates the file offset to the value specified by
   * @offset and @origin under i_mutex.
   */
  loff_t generic_file_llseek(struct file *file, loff_t offset, int origin)
  {
          loff_t rval;
  
          mutex_lock(&amp;file-&gt;f_dentry-&gt;d_inode-&gt;i_mutex);
          rval = generic_file_llseek_unlocked(file, offset, origin);
          mutex_unlock(&amp;file-&gt;f_dentry-&gt;d_inode-&gt;i_mutex);
  
          return rval;
  }
  
  /**
   * generic_file_llseek_unlocked - lockless generic llseek implementation
   * @file:       file structure to seek on
   * @offset:     file offset to seek to
   * @origin:     type of seek
   *
   * Updates the file offset to the value specified by @offset and @origin.
   * Locking must be provided by the caller.
   */
  loff_t
  generic_file_llseek_unlocked(struct file *file, loff_t offset, int origin)
  {
          struct inode *inode = file-&gt;f_mapping-&gt;host;
  
          switch (origin) {
          case SEEK_END:
                  offset += inode-&gt;i_size;
                  break;
          case SEEK_CUR:
                  /*
                   * Here we special-case the lseek(fd, 0, SEEK_CUR)
                   * position-querying operation.  Avoid rewriting the "same"
                   * f_pos value back to the file because a concurrent read(),
                   * write() or lseek() might have altered it
                   */
                  if (offset == 0)
                          return file-&gt;f_pos;
                 break;
          }
  
          if (offset &lt; 0 || offset &gt; inode-&gt;i_sb-&gt;s_maxbytes)
                  return -EINVAL;
  
          /* Special lock needed here? */
          if (offset != file-&gt;f_pos) {
                  file-&gt;f_pos = offset;
  
                  file-&gt;f_version = 0;
          }
  
          return offset;
  }
  </code></pre>
  
  <p>Say, for example, I have a 4GB file, and I know the offset for the middle portion in the file, how exactly does a <code>lseek()</code> get me there without traversing the entire file? Does the OS already know where each byte of the file resides?</p>