Union Mount: A Directory listing approach with lseek support

RFC PATCH In review Bharata B Rao 4 participants 12 messages Dec 5, 2007 – Dec 7, 2007 VFS

lore

Share & tools

lore

Bharata B Rao

author

2007-12-05 14:38 UTC #0 lore raw

cover Union Mount: A Directory listing approach with lseek support

Hi,

In Union Mount, the merged view of directories of the union is obtained by enhancing readdir(2)/getdents(2) to read and merge the entries of all the directories by eliminating the duplicates. While we have tried a few approaches for this, none of them could perfectly solve all the problems. One of the challenges has been to provide a correct directory seek support for the union mounted directories. Sometime back when I posted an
RFC (http://lkml.org/lkml/2007/9/7/22) on this problem, one of the suggestions I got was to have the dirents stored in a cache (which we already do for duplicate elimination) and define the directory seek behaviour on this cache constructed out of unioned directories.

I set out to try this and the result is this set of patches. I am myself not impressed by the implementation complexity in these patches but posting them here only to get further comments and suggestions. Moreover I haven't debugged them thoroughly to uncover all the problems. While I don't expect anybody try these patches, for the completeness sake I have to mention that these apply on top of Jan Blunck's patches on 2.6.24-rc2-mm1 (ftp://ftp.suse.com/pub/people/jblunck/patches/).

In this approach, the cached dirents are given offsets in the form of linearly increasing indices/cookies (like 0, 1, 2,...). This helps us to uniformly define offsets across all the directories of the union irrespective of the type of filesystem involved. Also this is needed to define a seek behaviour on the union mounted directory. This cache is stored as part of the struct file of the topmost directory of the union and will remain as long as the directory is kept open.

While this approach works, it has the following downsides:

- The cache can grow arbitrarily large in size for big directories thereby consuming lots of memory. Pruning individual cache entries is out of question as entire cache is needed for subsequent readdirs for duplicate elimination.

- When an exising union gets overlaid by a new directory, there is a possibility of the cache getting duplicated for the new union, thereby wasting more space.

- Whenever _any_ directory that is part of the union gets modified (addition/deletion of entries), the dirent cache of all the unions which this directory is part of, needs to be purged and rebuilt. This is expensive not only due to re-reads of dirents but also because readdir(2)/getdents(2) needs to be synchronized with other operations like mkdir/mknod/link/unlink etc.

- Since lseek(2) of the unioned directory also works on the same dirent cache, it too needs to be invalidated when the directory gets modified.

- Supporting SEEK_END of lseek(2) is expensive as it involves reading in all the dirents to know the EOF of the directory file.

After all this, I am beginning to think if it would be better to delegate this readdir and whiteout processing to userspace. Can this be better handled by readdir(3) in glibc ? But even with this, I am not sure if correct seek behaviour (from lseek(2) or seekdir(3)) can be achieved in an easy manner. Any thoughts on this ?

Earlier Erez Zodak had suggested that things will become easier if readdir state is stored as a disk file (http://lkml.org/lkml/2007/9/7/114). This approach simplifies directory seek support in Unionfs. But I am not sure if such an approach would go well with VFS based unification approach like Union Mount.

Regards,
Bharata.

Bharata B Rao

author

2007-12-05 14:38 UTC #1 lore raw

RFC PATCH 1/5 Remove existing directory listing implementation

Remove the existing readdir implementation.

Signed-off-by Bharata B Rao <[email protected]>

---
 fs/readdir.c          |   10 +
 fs/union.c            |  333 --------------------------------------------------
 include/linux/union.h |   23 ---
 3 files changed, 8 insertions(+), 358 deletions(-)

fs/readdir.c +8 -2

@@ -16,12 +16,12 @@
 #include <linux/security.h>
 #include <linux/syscalls.h>
 #include <linux/unistd.h>
-#include <linux/union.h>
 
 #include <asm/uaccess.h>
 
 int vfs_readdir(struct file *file, filldir_t filler, void *buf)
 {
+	struct inode *inode = file->f_path.dentry->d_inode;
 	int res = -ENOTDIR;
 
 	if (!file->f_op || !file->f_op->readdir)

@@ -31,7 +31,13 @@ int vfs_readdir(struct file *file, filld
 	if (res)
 		goto out;
 
-	res = do_readdir(file, buf, filler);
+	mutex_lock(&inode->i_mutex);
+	res = -ENOENT;
+	if (!IS_DEADDIR(inode)) {
+		res = file->f_op->readdir(file, buf, filler);
+		file_accessed(file);
+	}
+	mutex_unlock(&inode->i_mutex);
 out:
 	return res;
 }

fs/union.c +0 ~~-333~~

339 lines not on this page · raw message

include/linux/union.h +0 ~~-23~~

@@ -54,7 +54,6 @@ extern int attach_mnt_union(struct vfsmo
 			    struct dentry *);
 extern void detach_mnt_union(struct vfsmount *);
 extern int last_union_is_root(struct path *);
-extern int readdir_union(struct file *, void *, filldir_t);
 extern int is_dir_unioned(struct path *);
 extern int union_relookup_topmost(struct nameidata *, int);
 extern struct dentry *union_create_topmost(struct nameidata *, struct qstr *,

@@ -83,27 +82,5 @@ extern int union_copyup(struct nameidata
 
 #endif	/* CONFIG_UNION_MOUNT */
 
-static inline int do_readdir(struct file *file, void *buf, filldir_t filler)
-{
-	int res = 0;
-	struct inode *inode = file->f_path.dentry->d_inode;
-
-#ifdef CONFIG_UNION_MOUNT
-	if (IS_MNT_UNION(file->f_path.mnt) && is_dir_unioned(&file->f_path))
-		res = readdir_union(file, buf, filler);
-	else
-#endif
-	{
-		mutex_lock(&inode->i_mutex);
-		res = -ENOENT;
-		if (!IS_DEADDIR(inode)) {
-			res = file->f_op->readdir(file, buf, filler);
-			file_accessed(file);
-		}
-		mutex_unlock(&inode->i_mutex);
-	}
-	return res;
-}
-
 #endif	/* __KERNEL__ */
 #endif	/* __LINUX_UNION_H */

Dave Hansen

2007-12-05 16:27 UTC #2 lore raw

Re: [RFC PATCH 1/5] Remove existing directory listing implementation

Quoted 1 line · Bharata B Rao

Remove the existing readdir implementation.

You may have had a better description in your 0/5 mail, but this is what goes into the git log in the end, so I think you need to beef this up a bit.

-- Dave

Bharata B Rao

author

2007-12-05 14:39 UTC #3 lore raw

RFC PATCH 2/5 Add New directory listing approach

In reply to Bharata B Rao

Another readdir implementation for union uounted directories.

Reads dirents from all layers of the union into a cache, eliminates duplicates, before returning them into userspace. The cache is stored persistently as part of struct file of the topmost directory. Instead of original directory offsets, offsets are defined as linearly increasing indices on this cache and the same is returned to userspace.

Signed-off-by Bharata B Rao <[email protected]>

---
 fs/file_table.c       |    1 
 fs/readdir.c          |   10 -
 fs/union.c            |  281 ++++++++++++++++++++++++++++++++++++++++++++++++++
 include/linux/fs.h    |   30 +++++
 include/linux/union.h |   28 ++++
 5 files changed, 342 insertions(+), 8 deletions(-)

fs/file_table.c +1 -0

@@ -286,6 +286,7 @@ void fastcall __fput(struct file *file)
 		drop_file_write_access(file);
 
 	put_pid(file->f_owner.pid);
+	put_rdstate(file->f_rdstate);
 	file_kill(file);
 	file->f_path.dentry = NULL;
 	file->f_path.mnt = NULL;

fs/readdir.c +2 -8

@@ -16,12 +16,12 @@
 #include <linux/security.h>
 #include <linux/syscalls.h>
 #include <linux/unistd.h>
+#include <linux/union.h>
 
 #include <asm/uaccess.h>
 
 int vfs_readdir(struct file *file, filldir_t filler, void *buf)
 {
-	struct inode *inode = file->f_path.dentry->d_inode;
 	int res = -ENOTDIR;
 
 	if (!file->f_op || !file->f_op->readdir)

@@ -31,13 +31,7 @@ int vfs_readdir(struct file *file, filld
 	if (res)
 		goto out;
 
-	mutex_lock(&inode->i_mutex);
-	res = -ENOENT;
-	if (!IS_DEADDIR(inode)) {
-		res = file->f_op->readdir(file, buf, filler);
-		file_accessed(file);
-	}
-	mutex_unlock(&inode->i_mutex);
+	res = do_readdir(file, buf, filler);
 out:
 	return res;
 }

fs/union.c +281 -0

301 lines not on this page · raw message

include/linux/fs.h +30 -0

@@ -785,6 +785,33 @@ static inline int ra_has_index(struct fi
 		index <  ra->start + ra->size);
 }
 
+#ifdef CONFIG_UNION_MOUNT
+/* The readdir cache object */
+struct rdcache_entry {
+	struct list_head list;
+	unsigned long ino;
+	unsigned long off;
+	struct qstr name;
+	unsigned int dtype;
+};
+
+struct rdstate {
+	struct path cur_path;	/* Current directory on which readdir is
+				   in progress */
+	loff_t file_off;	/* File offset of underlying directory */
+	loff_t cur_off;		/* Offset to current dirent in rdcache */
+	loff_t last_off;	/* Offset to last dirent in rdcache */
+	loff_t nr_dirents;	/* Number of entries from current underlying
+				   directory in rdcache */
+	struct list_head dirent_cache;	/* cache of directory entries */
+};
+
+extern void put_rdstate(struct rdstate *rdstate);
+
+#else
+#define put_rdstate(x)		do { } while (0)
+#endif
+
 #define FILE_MNT_WRITE_TAKEN	1
 #define FILE_MNT_WRITE_RELEASED	2

@@ -823,6 +850,9 @@ struct file {
 #endif /* #ifdef CONFIG_EPOLL */
 	struct address_space	*f_mapping;
 	unsigned long f_mnt_write_state;
+#ifdef CONFIG_UNION_MOUNT
+	struct rdstate		*f_rdstate;
+#endif
 };
 extern spinlock_t files_lock;
 #define file_list_lock() spin_lock(&files_lock);

include/linux/union.h +28 -0

@@ -36,6 +36,7 @@ struct union_mount {
 
 	struct path u_this;		/* this is me */
 	struct path u_next;		/* this is what I overlay */
+	loff_t nr_dirents;		/* nr dirents in this directory */
 };
 
 #define IS_UNION(dentry)	(!list_empty(&(dentry)->d_unions) || \

@@ -53,6 +54,7 @@ extern void __shrink_d_unions(struct den
 extern int attach_mnt_union(struct vfsmount *, struct vfsmount *,
 			    struct dentry *);
 extern void detach_mnt_union(struct vfsmount *);
+extern int readdir_union(struct file *, void *, filldir_t);
 extern int last_union_is_root(struct path *);
 extern int is_dir_unioned(struct path *);
 extern int union_relookup_topmost(struct nameidata *, int);

@@ -61,6 +63,8 @@ extern struct dentry *union_create_topmo
 extern int __union_copyup(struct path *, struct nameidata *, struct path *);
 extern int union_copyup(struct nameidata *, int);
 
+extern struct mutex union_rdmutex;
+
 #else /* CONFIG_UNION_MOUNT */
 
 #define IS_UNION(x)			(0)

@@ -82,5 +86,29 @@ extern int union_copyup(struct nameidata
 
 #endif	/* CONFIG_UNION_MOUNT */
 
+static inline int do_readdir(struct file *file, void *buf, filldir_t filler)
+{
+	int res = 0;
+	struct inode *inode = file->f_path.dentry->d_inode;
+
+	mutex_lock(&inode->i_mutex);
+#ifdef CONFIG_UNION_MOUNT
+	if (IS_MNT_UNION(file->f_path.mnt) && is_dir_unioned(&file->f_path)) {
+		mutex_lock(&union_rdmutex);
+		res = readdir_union(file, buf, filler);
+		mutex_unlock(&union_rdmutex);
+	} else
+#endif
+	{
+		res = -ENOENT;
+		if (!IS_DEADDIR(inode)) {
+			res = file->f_op->readdir(file, buf, filler);
+			file_accessed(file);
+		}
+	}
+	mutex_unlock(&inode->i_mutex);
+	return res;
+}
+
 #endif	/* __KERNEL__ */
 #endif	/* __LINUX_UNION_H */

Bharata B Rao

author

2007-12-05 15:01 UTC #4 lore raw

RFC PATCH 3/5 Add list_for_each_entry_reverse_from()

In reply to Bharata B Rao

Introduce list_for_each_entry_reverse_from() needed by a subsequent patch.

Signed-off-by Bharata B Rao <[email protected]>

---
 include/linux/list.h |   13 +++++++++++++
 1 file changed, 13 insertions(+)

include/linux/list.h +13 -0

@@ -562,6 +562,19 @@ static inline void list_splice_init_rcu(
 	     pos = list_entry(pos->member.next, typeof(*pos), member))
 
 /**
+ * list_for_each_entry_reverse_from - iterate backwards over list of given
+ * type from the current point
+ * @pos:	the type * to use as a loop cursor.
+ * @head:	the head for your list.
+ * @member:	the name of the list_struct within the struct.
+ *
+ * Iterate backwards over list of given type, continuing from current position.
+ */
+#define list_for_each_entry_reverse_from(pos, head, member)		\
+	for (; prefetch(pos->member.prev), &pos->member != (head);	\
+	     pos = list_entry(pos->member.prev, typeof(*pos), member))
+
+/**
  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
  * @pos:	the type * to use as a loop cursor.
  * @n:		another type * to use as temporary storage

Bharata B Rao

author

2007-12-05 14:41 UTC #5 lore raw

RFC PATCH 4/5 Directory seek support

In reply to Bharata B Rao

Directory seek support.

Define the seek behaviour on the stored cache of dirents.

Signed-off-by Bharata B Rao <[email protected]>

---
 fs/read_write.c       |   11 ---
 fs/union.c            |  171 +++++++++++++++++++++++++++++++++++++++++++++++++-
 include/linux/fs.h    |    8 ++
 include/linux/union.h |   25 +++++++
 4 files changed, 205 insertions(+), 10 deletions(-)

fs/read_write.c +2 -9

@@ -16,6 +16,7 @@
 #include <linux/syscalls.h>
 #include <linux/pagemap.h>
 #include <linux/splice.h>
+#include <linux/union.h>
 #include "read_write.h"
 
 #include <asm/uaccess.h>

@@ -116,15 +117,7 @@ EXPORT_SYMBOL(default_llseek);
 
 loff_t vfs_llseek(struct file *file, loff_t offset, int origin)
 {
-	loff_t (*fn)(struct file *, loff_t, int);
-
-	fn = no_llseek;
-	if (file->f_mode & FMODE_LSEEK) {
-		fn = default_llseek;
-		if (file->f_op && file->f_op->llseek)
-			fn = file->f_op->llseek;
-	}
-	return fn(file, offset, origin);
+	return do_llseek(file, offset, origin);
 }
 EXPORT_SYMBOL(vfs_llseek);

fs/union.c +170 -1

206 lines not on this page · raw message

include/linux/fs.h +8 -0

@@ -803,9 +803,17 @@ struct rdstate {
 	loff_t last_off;	/* Offset to last dirent in rdcache */
 	loff_t nr_dirents;	/* Number of entries from current underlying
 				   directory in rdcache */
+	loff_t fill_off;	/* Fill cache upto this offset. Used during
+				   seek */
 	struct list_head dirent_cache;	/* cache of directory entries */
+	struct rdcache_entry *cur_dirent;	/* pointer to current directory
+				entry in rdcache which corresponds to cur_off */
+	int flags;
 };
 
+#define RDSTATE_STALE		0x01
+#define RDSTATE_NEED_UPDATE	0x02
+
 extern void put_rdstate(struct rdstate *rdstate);
 
 #else

include/linux/union.h +25 -0

@@ -55,6 +55,7 @@ extern int attach_mnt_union(struct vfsmo
 			    struct dentry *);
 extern void detach_mnt_union(struct vfsmount *);
 extern int readdir_union(struct file *, void *, filldir_t);
+extern loff_t llseek_union(struct file *, loff_t, int);
 extern int last_union_is_root(struct path *);
 extern int is_dir_unioned(struct path *);
 extern int union_relookup_topmost(struct nameidata *, int);

@@ -110,5 +111,29 @@ static inline int do_readdir(struct file
 	return res;
 }
 
+static inline loff_t do_llseek(struct file *file, loff_t offset, int origin)
+{
+	long long res;
+#ifdef CONFIG_UNION_MOUNT
+	if (IS_MNT_UNION(file->f_path.mnt) && is_dir_unioned(&file->f_path)) {
+		mutex_lock(&union_rdmutex);
+		res = llseek_union(file, offset, origin);
+		mutex_unlock(&union_rdmutex);
+	} else
+#endif
+	{
+		loff_t (*fn)(struct file *, loff_t, int);
+
+		fn = no_llseek;
+		if (file->f_mode & FMODE_LSEEK) {
+			fn = default_llseek;
+			if (file->f_op && file->f_op->llseek)
+				fn = file->f_op->llseek;
+		}
+		res = fn(file, offset, origin);
+	}
+	return res;
+}
+
 #endif	/* __KERNEL__ */
 #endif	/* __LINUX_UNION_H */

Bharata B Rao

author

2007-12-05 14:41 UTC #6 lore raw

RFC PATCH 5/5 Directory cache invalidation

In reply to Bharata B Rao

Changes to keep dirent cache uptodate.

Dirent cache stored as part of topmost directory's struct file needs to be marked stale whenever there is a modification in any of the directories that is part of the union. Modifications(like addition/deletion of new entries) to a directory can occur from places like mkdir, rmdir, mknod etc.

Signed-off-by Bharata B Rao <[email protected]>

---
 fs/dcache.c            |    1 
 fs/namei.c             |   13 +++
 fs/union.c             |  178 ++++++++++++++++++++++++++++++++++++++++++++++++-
 include/linux/dcache.h |    4 -
 include/linux/fs.h     |    4 +
 include/linux/union.h  |    3 
 6 files changed, 201 insertions(+), 2 deletions(-)

fs/dcache.c +1 -0

@@ -974,6 +974,7 @@ struct dentry *d_alloc(struct dentry * p
 #endif
 #ifdef CONFIG_UNION_MOUNT
 	INIT_LIST_HEAD(&dentry->d_unions);
+	INIT_LIST_HEAD(&dentry->d_overlaid);
 	dentry->d_unionized = 0;
 #endif
 	INIT_HLIST_NODE(&dentry->d_hash);

fs/namei.c +13 -0

@@ -2237,6 +2237,7 @@ static int __open_namei_create(struct na
 	nd->path.dentry = path->dentry;
 	if (error)
 		return error;
+	rdcache_invalidate(&nd->path);
 	/* Don't check for write permission, don't truncate */
 	return may_open(nd, 0, flag & ~O_TRUNC);
 }

@@ -2682,6 +2683,8 @@ asmlinkage long sys_mknodat(int dfd, con
 					  mode, 0);
 			break;
 	}
+	if (!error)
+		rdcache_invalidate(&nd.path);
 	mnt_drop_write(nd.path.mnt);
 out_dput:
 	path_put_conditional(&path, &nd);

@@ -2757,6 +2760,8 @@ asmlinkage long sys_mkdirat(int dfd, con
 	if (error)
 		goto out_dput;
 	error = vfs_mkdir(nd.path.dentry->d_inode, path.dentry, mode);
+	if (!error)
+		rdcache_invalidate(&nd.path);
 	mnt_drop_write(nd.path.mnt);
 out_dput:
 	path_put_conditional(&path, &nd);

@@ -3287,6 +3292,8 @@ static long do_rmdir(int dfd, const char
 	if (error)
 		goto exit3;
 	error = vfs_rmdir(nd.path.dentry->d_inode, path.dentry);
+	if (!error)
+		rdcache_invalidate(&nd.path);
 	mnt_drop_write(nd.path.mnt);
 exit3:
 	path_put_conditional(&path, &nd);

@@ -3375,6 +3382,8 @@ static long do_unlinkat(int dfd, const c
 		if (error)
 			goto exit2;
 		error = vfs_unlink(nd.path.dentry->d_inode, path.dentry);
+		if (!error)
+			rdcache_invalidate(&nd.path);
 		mnt_drop_write(nd.path.mnt);
 	exit2:
 		path_put_conditional(&path, &nd);

@@ -3466,6 +3475,8 @@ asmlinkage long sys_symlinkat(const char
 		goto out_dput;
 	error = vfs_symlink(nd.path.dentry->d_inode, path.dentry, from,
 			    S_IALLUGO);
+	if (!error)
+		rdcache_invalidate(&nd.path);
 	mnt_drop_write(nd.path.mnt);
 out_dput:
 	path_put_conditional(&path, &nd);

@@ -3566,6 +3577,8 @@ asmlinkage long sys_linkat(int olddfd, c
 		goto out_dput;
 	error = vfs_link(old_nd.path.dentry, nd.path.dentry->d_inode,
 			 path.dentry);
+	if (!error)
+		rdcache_invalidate(&nd.path);
 	mnt_drop_write(nd.path.mnt);
 out_dput:
 	path_put_conditional(&path, &nd);

fs/union.c +177 -1

271 lines not on this page · raw message

include/linux/dcache.h +3 -1

@@ -97,9 +97,11 @@ struct dentry {
 #ifdef CONFIG_UNION_MOUNT
 	/*
 	 * The following fields are used by the VFS based union mount
-	 * implementation. Both are protected by union_lock!
+	 * implementation. They are protected by union_lock!
 	 */
 	struct list_head d_unions;	/* list of union_mount's */
+	struct list_head d_overlaid;	/* list of union_mount's from where this
+					   dentry is overlaid */
 	unsigned int d_unionized;	/* unions referencing this dentry */
 #endif

include/linux/fs.h +4 -0

@@ -798,6 +798,8 @@ struct rdcache_entry {
 struct rdstate {
 	struct path cur_path;	/* Current directory on which readdir is
 				   in progress */
+	struct hlist_node hash;	/* used to link into readdir_hashtable */
+	struct path path;	/* the path to which this rdstate belongs to */
 	loff_t file_off;	/* File offset of underlying directory */
 	loff_t cur_off;		/* Offset to current dirent in rdcache */
 	loff_t last_off;	/* Offset to last dirent in rdcache */

@@ -815,9 +817,11 @@ struct rdstate {
 #define RDSTATE_NEED_UPDATE	0x02
 
 extern void put_rdstate(struct rdstate *rdstate);
+extern void rdcache_invalidate(struct path *path);
 
 #else
 #define put_rdstate(x)		do { } while (0)
+#define rdcache_invalidate(x)	do { } while (0)
 #endif
 
 #define FILE_MNT_WRITE_TAKEN	1

include/linux/union.h +3 -0

@@ -31,6 +31,7 @@ struct union_mount {
 	struct mutex u_mutex;
 	struct list_head u_unions;	/* list head for d_unions */
 	struct list_head u_list;	/* list head for mnt_unions */
+	struct list_head u_overlaid;	/* list head for d_overlaid */
 	struct hlist_node u_hash;	/* list head for seaching */
 	struct hlist_node u_rhash;	/* list head for reverse seaching */

@@ -42,6 +43,7 @@ struct union_mount {
 #define IS_UNION(dentry)	(!list_empty(&(dentry)->d_unions) || \
 				 (dentry)->d_unionized)
 #define IS_MNT_UNION(mnt)	((mnt)->mnt_flags & MNT_UNION)
+#define IS_DENTRY_OVERLAID(dentry)	(dentry)->d_unionized
 
 extern int is_unionized(struct dentry *, struct vfsmount *);
 extern int append_to_union(struct vfsmount *, struct dentry *,

@@ -70,6 +72,7 @@ extern struct mutex union_rdmutex;
 
 #define IS_UNION(x)			(0)
 #define IS_MNT_UNION(x)			(0)
+#define IS_DENTRY_OVERLAID(x)		(0)
 #define is_unionized(x, y)		(0)
 #define append_to_union(x1, y1, x2, y2, z)	({ BUG(); (0); })
 #define follow_union_down(x, y)		({ (0); })

Dave Hansen

2007-12-05 17:22 UTC #7 lore raw

In reply to Bharata B Rao

Quoted 7 lines · Bharata B Rao

In this approach, the cached dirents are given offsets in the form of linearly increasing indices/cookies (like 0, 1, 2,...). This helps us to uniformly define offsets across all the directories of the union irrespective of the type of filesystem involved. Also this is needed to define a seek behaviour on the union mounted directory. This cache is stored as part of the struct file of the topmost directory of the union and will remain as long as the directory is kept open.

That's a little brute force, don't you think? Especially the memory exhaustion seems to really make this an undesirable approach.

I think the key here is what kind of consistency we're trying to provide. If a directory is being changed underneath a reader, what kinds of guarantees do they get about the contents of their directory read? When do those guarantees start? Are there any at open() time?

Rather than give each _dirent_ an offset, could we give each sub-mount an offset? Let's say we have three members comprising a union mount directory. The first has 100 dirents, the second 200, and the third 10,000. When the first readdir is done, we populate the table like this:

	mount_offset[0] = 0;
	mount_offset[1] = 100;
	mount_offset[2] = 300;

If someone seeks back to 150, then we subtrack the mount[1]'s offset (100), and realize that we want the 50th dirent from mount[1].

I don't know whether we're bound to this:

http://www.opengroup.org/onlinepubs/007908775/xsh/readdir.html

"If a file is removed from or added to the directory after the most recent call to opendir() or rewinddir(), whether a subsequent call to readdir() returns an entry for that file is unspecified."

But that would seem to tell me that once you populate a table such as the one I've described and create it at open(dir) time, you don't actually ever need to update it.

The storage for this is only comparable to the number of mounts that you have. One issue comes if we manage to overflow our data types with too many entries in too many submounts. But, I guess we can just truncate the directory in that case.

-- Dave

Jan Blunck

2007-12-06 10:01 UTC #8 lore raw

Quoted 4 lines · Dave Hansen

I think the key here is what kind of consistency we're trying to provide. If a directory is being changed underneath a reader, what kinds of guarantees do they get about the contents of their directory read? When do those guarantees start? Are there any at open() time?

But we still want to be compliant to what POSIX defines. The problem isn't the consistency of the readdir result but the seekdir/telldir interface. IMHO that interface is totally broken: you need to be able to find every offset given by telldir since the last open. The problem is that seekdir isn't able to return errors. Otherwise you could just forbid seeking on union directories.

Quoted 6 lines

Rather than give each _dirent_ an offset, could we give each sub-mount an offset? Let's say we have three members comprising a union mount directory. The first has 100 dirents, the second 200, and the third 10,000. When the first readdir is done, we populate the table like this:

Quoted 6 lines

	mount_offset[0] = 0;
	mount_offset[1] = 100;
	mount_offset[2] = 300;
If someone seeks back to 150, then we subtrack the mount[1]'s offset (100), and realize that we want the 50th dirent from mount[1].

Yes, that is a nice idea and it is exactly what I have implemented in my patch series. But you forgot one thing: directories are not flat files. The dentry offset in a directory is a random cookie. Therefore it is not possible to have a linear mapping without allocating memory.

Quoted 4 lines

I don't know whether we're bound to this:
http://www.opengroup.org/onlinepubs/007908775/xsh/readdir.html

Quoted 8 lines

"If a file is removed from or added to the directory after the most recent call to opendir() or rewinddir(), whether a subsequent call to readdir() returns an entry for that file is unspecified."
But that would seem to tell me that once you populate a table such as the one I've described and create it at open(dir) time, you don't actually ever need to update it.

Yes, I'm using such a patch on our S390 buildservers to work around some readdir/seek/rm problem with old glibc versions. It seems to work but on the other hand this are really huge systems and I haven't run out of memory while doing a readdir yet ;)

The proper way to implement this would be to cache the offsets on a per inode base. Otherwise the user could easily DoS this by opening a number of directories and never close them.

Regards,
Jan

Signature · 1 line

Jan Blunck <[email protected]>

Bharata B Rao

author

2007-12-06 15:11 UTC #9 lore raw

Quoted 7 lines · Jan Blunck

Quoted 4 lines · Dave Hansen
I think the key here is what kind of consistency we're trying to provide. If a directory is being changed underneath a reader, what kinds of guarantees do they get about the contents of their directory read? When do those guarantees start? Are there any at open() time?

Quoted 5 lines

But we still want to be compliant to what POSIX defines. The problem isn't the consistency of the readdir result but the seekdir/telldir interface. IMHO that interface is totally broken: you need to be able to find every offset given by telldir since the last open. The problem is that seekdir isn't able to return errors. Otherwise you could just forbid seeking on union directories.

Also, what kind of consistency is expected when a directory is open(2)ed and readdir(2) and lseek(2) are applied to it when the directory gets changed underneath the reader. From this:
http://www.opengroup.org/onlinepubs/009695399/functions/lseek.html
the behaviour/guarantees wasn't apparent to me.

Quoted 11 lines

Quoted 11 lines
Rather than give each _dirent_ an offset, could we give each sub-mount an offset? Let's say we have three members comprising a union mount directory. The first has 100 dirents, the second 200, and the third 10,000. When the first readdir is done, we populate the table like this:
	mount_offset[0] = 0;
	mount_offset[1] = 100;
	mount_offset[2] = 300;

Quoted 7 lines

Quoted 2 lines
If someone seeks back to 150, then we subtrack the mount[1]'s offset (100), and realize that we want the 50th dirent from mount[1].
Yes, that is a nice idea and it is exactly what I have implemented in my patch series. But you forgot one thing: directories are not flat files. The dentry offset in a directory is a random cookie. Therefore it is not possible to have a linear mapping without allocating memory.

And I defined this linear behaviour on the cache of dirents we maintain in the approach I posted. And the main reason we maintain cache of dirents in memory is for duplicate elimination.

Quoted 14 lines

Quoted 5 lines
I don't know whether we're bound to this:
http://www.opengroup.org/onlinepubs/007908775/xsh/readdir.html
Quoted 8 lines
"If a file is removed from or added to the directory after the most recent call to opendir() or rewinddir(), whether a subsequent call to readdir() returns an entry for that file is unspecified."
But that would seem to tell me that once you populate a table such as the one I've described and create it at open(dir) time, you don't actually ever need to update it.

Quoted 9 lines

Yes, I'm using such a patch on our S390 buildservers to work around some readdir/seek/rm problem with old glibc versions. It seems to work but on the other hand this are really huge systems and I haven't run out of memory while doing a readdir yet ;)
The proper way to implement this would be to cache the offsets on a per inode base. Otherwise the user could easily DoS this by opening a number of directories and never close them.

You mean cache the offsets or dirents ? How would that solve the seek problem ? How would it enable you to define a seek behaviour for the entire union of directories ?

Regards,
Bharata.

Dave Hansen

2007-12-06 17:55 UTC #10 lore raw

In reply to Jan Blunck

Quoted 10 lines · Jan Blunck

Quoted 10 lines
Rather than give each _dirent_ an offset, could we give each sub-mount an offset? Let's say we have three members comprising a union mount directory. The first has 100 dirents, the second 200, and the third 10,000. When the first readdir is done, we populate the table like this:
      mount_offset[0] = 0;
      mount_offset[1] = 100;
      mount_offset[2] = 300;

Quoted 7 lines

Quoted 2 lines
If someone seeks back to 150, then we subtrack the mount[1]'s offset (100), and realize that we want the 50th dirent from mount[1].
Yes, that is a nice idea and it is exactly what I have implemented in my patch series. But you forgot one thing: directories are not flat files. The dentry offset in a directory is a random cookie. Therefore it is not possible to have a linear mapping without allocating memory.

Is is truly a random cookie where the fs gets to put anything in there that it can fit in a long? Isn't that an advantage? Being a random cookie, we can encode anything we want in there. We could encode the "mount index" (or whatever you want to call it) in high or low bits and have the rest store the fs-specific offset. The only problem there would be running out of storage space in long.

But, what do people expect when they have huge directories (or huge directory offsets)? Surely, if their fs is already pressing the fs's directory data types to the limits, they can't simply union mount a couple of those directories together and expect magic. Union mounts also can't be expected to compress these directory positions to fit.

So, I think it's reasonable behavior to readdir() until the sum of the highest position seen on each mount would overflow the off_t that we have to store it in.

-- Dave

[email protected]

2007-12-07 02:14 UTC #11 lore raw

In reply to Bharata B Rao

Bharata B Rao:

Quoted 3 lines

- The cache can grow arbitrarily large in size for big directories thereby consuming lots of memory. Pruning individual cache entries is out of question as entire cache is needed for subsequent readdirs for duplicate elimination.

Additionally, the memory usage may be a problem too since your implementation calls kmalloc() for every names.

Quoted 6 lines

- Whenever _any_ directory that is part of the union gets modified (addition/deletion of entries), the dirent cache of all the unions which this directory is part of, needs to be purged and rebuilt. This is expensive not only due to re-reads of dirents but also because readdir(2)/getdents(2) needs to be synchronized with other operations like mkdir/mknod/link/unlink etc.

The cache in struct file doesn't need to be refreshed unless rewinddir() is issued. Also you can maintain the cache in every add/del entries, instead of discarding the cache entirely.

Quoted 2 lines

After all this, I am beginning to think if it would be better to delegate this readdir and whiteout processing to userspace. Can this be better handled

Yes, I had such idea once. And copy-up too. They can be done in userspace (while you need to be careful about the privilege).

Anyway I agree with you. As I wrote before, this approach consumes a lot of memory and cpu (for comparing whiteouted names).

Junjiro Okajima