11

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

/**
 * 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()不遍历整个文件的情况下究竟如何才能到达那里？操作系统是否已经知道文件的每个字节所在的位置？

4

3 回答 3

7

lseek()正如在中实现的那样，ext4只会增加文件指针并进行一些验证检查。它不依赖于文件大小，这意味着它是O(1).

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

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

于 2014-02-09T11:24:01.930 回答
1

lseek的复杂性取决于系统中文件的表示。在大多数现代系统上，文件由一些巧妙的树状数据结构组织，从而seek及时执行O(logx(n))，其中 n 是文件的大小，x 是某个系统相关的数字。

于 2014-02-09T11:24:26.130 回答
0

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

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

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

于 2014-02-09T11:46:40.153 回答