fuse: allow using readdir cache

The cache is only used if it's completed, not while it's still being
filled; this constraint could be lifted later, if it turns out to be
useful.

Introduce state in struct fuse_file that indicates the position within the
cache.  After a seek, reset the position to the beginning of the cache and
search the cache for the current position.  If the current position is not
found in the cache, then fall back to uncached readdir.

It can also happen that page(s) disappear from the cache, in which case we
must also fall back to uncached readdir.

Signed-off-by: Miklos Szeredi <mszeredi@redhat.com>

3 files changed, 161 insertions, 4 deletions

diff --git a/fs/fuse/file.c b/fs/fuse/file.c
index d15c14912e72..e10c0443c56f 100644
--- a/fs/fuse/file.c
+++ b/fs/fuse/file.c
@@ -59,6 +59,7 @@ struct fuse_file *fuse_file_alloc(struct fuse_conn *fc)
         }
 
         INIT_LIST_HEAD(&ff->write_entry);
+        mutex_init(&ff->readdir.lock);
         refcount_set(&ff->count, 1);
         RB_CLEAR_NODE(&ff->polled_node);
         init_waitqueue_head(&ff->poll_wait);
@@ -73,6 +74,7 @@ struct fuse_file *fuse_file_alloc(struct fuse_conn *fc)
 void fuse_file_free(struct fuse_file *ff)
 {
         fuse_request_free(ff->reserved_req);
+        mutex_destroy(&ff->readdir.lock);
         kfree(ff);
 }
 
diff --git a/fs/fuse/fuse_i.h b/fs/fuse/fuse_i.h
index d2fa7588533e..49e42635e3ac 100644
--- a/fs/fuse/fuse_i.h
+++ b/fs/fuse/fuse_i.h
@@ -163,6 +163,21 @@ struct fuse_file {
         /** Entry on inode's write_files list */
         struct list_head write_entry;
 
+        /* Readdir related */
+        struct {
+                /*
+                 * Protects below fields against (crazy) parallel readdir on
+                 * same open file.  Uncontended in the normal case.
+                 */
+                struct mutex lock;
+
+                /* Dir stream position */
+                loff_t pos;
+
+                /* Offset in cache */
+                loff_t cache_off;
+        } readdir;
+
         /** RB node to be linked on fuse_conn->polled_files */
         struct rb_node polled_node;
 
diff --git a/fs/fuse/readdir.c b/fs/fuse/readdir.c
index 6c5ada164f7e..5bdc0b945d72 100644
--- a/fs/fuse/readdir.c
+++ b/fs/fuse/readdir.c
@@ -289,7 +289,7 @@ static int parse_dirplusfile(char *buf, size_t nbytes, struct file *file,
         return 0;
 }
 
-int fuse_readdir(struct file *file, struct dir_context *ctx)
+static int fuse_readdir_uncached(struct file *file, struct dir_context *ctx)
 {
         int plus, err;
         size_t nbytes;
@@ -300,9 +300,6 @@ int fuse_readdir(struct file *file, struct dir_context *ctx)
         u64 attr_version = 0;
         bool locked;
 
-        if (is_bad_inode(inode))
-                return -EIO;
-
         req = fuse_get_req(fc, 1);
         if (IS_ERR(req))
                 return PTR_ERR(req);
@@ -351,3 +348,146 @@ int fuse_readdir(struct file *file, struct dir_context *ctx)
         fuse_invalidate_atime(inode);
         return err;
 }
+
+enum fuse_parse_result {
+        FOUND_ERR = -1,
+        FOUND_NONE = 0,
+        FOUND_SOME,
+        FOUND_ALL,
+};
+
+static enum fuse_parse_result fuse_parse_cache(struct fuse_file *ff,
+                                               void *addr, unsigned int size,
+                                               struct dir_context *ctx)
+{
+        unsigned int offset = ff->readdir.cache_off & ~PAGE_MASK;
+        enum fuse_parse_result res = FOUND_NONE;
+
+        WARN_ON(offset >= size);
+
+        for (;;) {
+                struct fuse_dirent *dirent = addr + offset;
+                unsigned int nbytes = size - offset;
+                size_t reclen = FUSE_DIRENT_SIZE(dirent);
+
+                if (nbytes < FUSE_NAME_OFFSET || !dirent->namelen)
+                        break;
+
+                if (WARN_ON(dirent->namelen > FUSE_NAME_MAX))
+                        return FOUND_ERR;
+                if (WARN_ON(reclen > nbytes))
+                        return FOUND_ERR;
+                if (WARN_ON(memchr(dirent->name, '/', dirent->namelen) != NULL))
+                        return FOUND_ERR;
+
+                if (ff->readdir.pos == ctx->pos) {
+                        res = FOUND_SOME;
+                        if (!dir_emit(ctx, dirent->name, dirent->namelen,
+                                      dirent->ino, dirent->type))
+                                return FOUND_ALL;
+                        ctx->pos = dirent->off;
+                }
+                ff->readdir.pos = dirent->off;
+                ff->readdir.cache_off += reclen;
+
+                offset += reclen;
+        }
+
+        return res;
+}
+
+#define UNCACHED 1
+
+static int fuse_readdir_cached(struct file *file, struct dir_context *ctx)
+{
+        struct fuse_file *ff = file->private_data;
+        struct inode *inode = file_inode(file);
+        struct fuse_inode *fi = get_fuse_inode(inode);
+        enum fuse_parse_result res;
+        pgoff_t index;
+        unsigned int size;
+        struct page *page;
+        void *addr;
+
+        /* Seeked?  If so, reset the cache stream */
+        if (ff->readdir.pos != ctx->pos) {
+                ff->readdir.pos = 0;
+                ff->readdir.cache_off = 0;
+        }
+
+retry:
+        spin_lock(&fi->rdc.lock);
+        if (!fi->rdc.cached) {
+                spin_unlock(&fi->rdc.lock);
+                return UNCACHED;
+        }
+        WARN_ON(fi->rdc.size < ff->readdir.cache_off);
+
+        index = ff->readdir.cache_off >> PAGE_SHIFT;
+
+        if (index == (fi->rdc.size >> PAGE_SHIFT))
+                size = fi->rdc.size & ~PAGE_MASK;
+        else
+                size = PAGE_SIZE;
+        spin_unlock(&fi->rdc.lock);
+
+        /* EOF? */
+        if ((ff->readdir.cache_off & ~PAGE_MASK) == size)
+                return 0;
+
+        page = find_get_page_flags(file->f_mapping, index,
+                                   FGP_ACCESSED | FGP_LOCK);
+        if (!page) {
+                /*
+                 * Uh-oh: page gone missing, cache is useless
+                 */
+                return UNCACHED;
+        }
+
+        addr = kmap(page);
+        res = fuse_parse_cache(ff, addr, size, ctx);
+        kunmap(page);
+        unlock_page(page);
+        put_page(page);
+
+        if (res == FOUND_ERR)
+                return -EIO;
+
+        if (res == FOUND_ALL)
+                return 0;
+
+        if (size == PAGE_SIZE) {
+                /* We hit end of page: skip to next page. */
+                ff->readdir.cache_off = ALIGN(ff->readdir.cache_off, PAGE_SIZE);
+                goto retry;
+        }
+
+        /*
+         * End of cache reached.  If found position, then we are done, otherwise
+         * need to fall back to uncached, since the position we were looking for
+         * wasn't in the cache.
+         */
+        return res == FOUND_SOME ? 0 : UNCACHED;
+}
+
+int fuse_readdir(struct file *file, struct dir_context *ctx)
+{
+        struct fuse_file *ff = file->private_data;
+        struct inode *inode = file_inode(file);
+        int err;
+
+        if (is_bad_inode(inode))
+                return -EIO;
+
+        mutex_lock(&ff->readdir.lock);
+
+        err = UNCACHED;
+        if (ff->open_flags & FOPEN_CACHE_DIR)
+                err = fuse_readdir_cached(file, ctx);
+        if (err == UNCACHED)
+                err = fuse_readdir_uncached(file, ctx);
+
+        mutex_unlock(&ff->readdir.lock);
+
+        return err;
+}