Is lseek () O (1) complexity?

Question

I know my question has the answer here: QFile to look for performance . But I'm not quite happy with the answer. Even after considering the next implementation of generic_file_llseek() for ext4, I cannot figure out how to measure complexity.

 /** * 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 ->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(&file->f_dentry->d_inode->i_mutex); rval = generic_file_llseek_unlocked(file, offset, origin); mutex_unlock(&file->f_dentry->d_inode->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->f_mapping->host; switch (origin) { case SEEK_END: offset += inode->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->f_pos; break; } if (offset < 0 || offset > inode->i_sb->s_maxbytes) return -EINVAL; /* Special lock needed here? */ if (offset != file->f_pos) { file->f_pos = offset; file->f_version = 0; } return offset; } 

Say, for example, I have a 4 GB file and I know the offset for the middle part of the file, how exactly does lseek() get me there without crossing the whole file? Does the OS mean where every byte of the file is?

Answer 1

lseek() , as implemented in ext4 , will simply increment the file pointer and check for some checks. It does not depend on the file size, i.e. O(1) .

You can also see this in the code, there is no loop or calls to suspicious functions.

However, although this is true in ext4 , this may not be true for other file systems, as this behavior is not guaranteed by POSIX. But, most likely, if the file system is not intended for a special purpose.

Answer 2

lseek complexity depends on the presentation of the file on your system. In most modern systems, the file is organized by some clever tree-like data structure, as a result of which seek is executed in time O(logx(n)) , where n is the file size and x is some system number.

Answer 3

Yes, the OS already knows how to find a specific byte in a file.

No, this is not guaranteed by O (1). You sent the O (1) code, but the code of other file systems may not exist.

Yes, it will be fast enough, if only the OS or file system is not scary.