lseek（）函数的时间复杂度是O（1）吗？

Question

我知道我的问题在这里有答案：QFile seek performance。但是我对答案并不完全满意。即使查看了ext4的generic_file_llseek()的以下实现，我似乎也无法理解如何衡量复杂性。

/**
 * 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;
}

例如，我有一个4GB的文件，并且我知道文件中间部分的偏移量，那么lseek()如何在不遍历整个文件的情况下准确地将我带到那里？操作系统是否已经知道文件中每个字节的位置？

比如说，如果我有一个4GB的文件，我知道文件中间部分的偏移量，那么lseek()是如何通过不遍历整个文件来精确定位的呢？操作系统是否已经知道文件中每个字节的位置？

- Nehal J Wani

Answer 1

lseek()在ext4中的实现只会增加文件指针并进行一些验证检查。它不依赖于文件大小，也就是说时间复杂度为O(1)。

此外，您可以在代码中看到，其中没有任何循环或可疑的函数调用。

然而，在ext4上是正确的，但对于其他文件系统可能不是这样，因为这种行为并不受POSIX保证。但除非文件系统用于特殊目的，否则很可能如此。

- hek2mgl

---

这是偶然发生的还是保证会发生的事情？ - user541686

检查一下你发布的代码。这是典型的O(1)代码。 - hek2mgl

据我所知，POSIX对文件系统操作的复杂度没有任何保证。 - Fred Foo

转念一想，我无法确定这个问题是关于这个特定的查找函数还是一般的查找... - user541686

我敢说O(1)确实是保证的，因为lseek本身并没有做任何事情（除了修改一个整数）。当然，如果操作系统在中间没有预读，后续的read可能需要先搜索已分配扇区的列表，然后可能会在机械硬盘上启动寻道，这在距离方面是O(N)。但是，lseek也可能会_减少_旋转延迟（这是无法预测的）。 - Damon

Answer 2

lseek的复杂性取决于系统中文件的表示方式。在大多数现代系统中，文件是通过一些聪明的树状数据结构组织起来的，这导致seek的执行时间为O(logx(n))，其中n是文件的大小，x是某个依赖于系统的数字。

- Marian

---

虽然这是一个聪明而且肯定正确的陈述，但从技术上讲，我怀疑实际的块搜索是否发生在lseek中。我会假设操作系统只会在发出读取或写入指令时（也许是类似于预读取的异步方式，在lseek之后）搜索块。 - Jonas Schäfer

"x"是无关紧要的：不同底数的对数只相差一个常数因子，而大O符号并不考虑常数倍数。 - user529758

@JonasWielicki 是的，这就是我在回答时所想到的。 - hek2mgl

Answer 3

是的，操作系统已经知道如何在文件中找到任何特定的字节。

不，它不能保证是O(1)。你发布的代码是O(1)，但其他文件系统的代码可能不是。

是的，它将足够快，除非操作系统或文件系统很糟糕。

- user253751