[RFC][PATCH 5/14] Introduce union stack

[Bharata B Rao <bharata@linux.vnet.ibm.com>]

From: Jan Blunck <j.blunck@tu-harburg.de>
Subject: Introduce union stack.

Adds union stack infrastructure to the dentry structure and provides
locking routines to walk the union stack.

Signed-off-by: Jan Blunck <j.blunck@tu-harburg.de>
Signed-off-by: Bharata B Rao <bharata@linux.vnet.ibm.com>
---
 fs/Makefile                  |    2 
 fs/dcache.c                  |    5 
 fs/union.c                   |   53 +++++++++
 include/linux/dcache.h       |    6 +
 include/linux/dcache_union.h |  248 +++++++++++++++++++++++++++++++++++++++++++
 5 files changed, 314 insertions(+)

--- a/fs/Makefile
+++ b/fs/Makefile
@@ -49,6 +49,8 @@ obj-$(CONFIG_FS_POSIX_ACL)	+= posix_acl.
 obj-$(CONFIG_NFS_COMMON)	+= nfs_common/
 obj-$(CONFIG_GENERIC_ACL)	+= generic_acl.o
 
+obj-$(CONFIG_UNION_MOUNT)	+= union.o
+
 obj-$(CONFIG_QUOTA)		+= dquot.o
 obj-$(CONFIG_QFMT_V1)		+= quota_v1.o
 obj-$(CONFIG_QFMT_V2)		+= quota_v2.o
--- a/fs/dcache.c
+++ b/fs/dcache.c
@@ -936,6 +936,11 @@ struct dentry *d_alloc(struct dentry * p
 #ifdef CONFIG_PROFILING
 	dentry->d_cookie = NULL;
 #endif
+#ifdef CONFIG_UNION_MOUNT
+	dentry->d_overlaid = NULL;
+	dentry->d_topmost = NULL;
+	dentry->d_union = NULL;
+#endif
 	INIT_HLIST_NODE(&dentry->d_hash);
 	INIT_LIST_HEAD(&dentry->d_lru);
 	INIT_LIST_HEAD(&dentry->d_subdirs);
--- /dev/null
+++ b/fs/union.c
@@ -0,0 +1,53 @@
+/*
+ * VFS based union mount for Linux
+ *
+ * Copyright © 2004-2007 IBM Corporation
+ *   Author(s): Jan Blunck (j.blunck@tu-harburg.de)
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the Free
+ * Software Foundation; either version 2 of the License, or (at your option)
+ * any later version.
+ */
+
+#include <linux/fs.h>
+
+struct union_info * union_alloc(void)
+{
+	struct union_info *info;
+
+	info = kmalloc(sizeof(*info), GFP_ATOMIC);
+	if (!info)
+		return NULL;
+
+	mutex_init(&info->u_mutex);
+	mutex_lock(&info->u_mutex);
+	atomic_set(&info->u_count, 1);
+	UM_DEBUG_LOCK("allocate union %p\n", info);
+	return info;
+}
+
+struct union_info * union_get(struct union_info *info)
+{
+	BUG_ON(!info);
+	BUG_ON(!atomic_read(&info->u_count));
+	atomic_inc(&info->u_count);
+	UM_DEBUG_LOCK("get union %p (count=%d)\n", info,
+		      atomic_read(&info->u_count));
+	return info;
+}
+
+void union_put(struct union_info *info)
+{
+	BUG_ON(!info);
+	UM_DEBUG_LOCK("put union %p (count=%d)\n", info,
+		      atomic_read(&info->u_count));
+	atomic_dec(&info->u_count);
+
+	if (!atomic_read(&info->u_count)) {
+		UM_DEBUG_LOCK("free union %p\n", info);
+		kfree(info);
+	}
+
+	return;
+}
--- a/include/linux/dcache.h
+++ b/include/linux/dcache.h
@@ -93,6 +93,12 @@ struct dentry {
 	struct dentry *d_parent;	/* parent directory */
 	struct qstr d_name;
 
+#ifdef CONFIG_UNION_MOUNT
+	struct dentry *d_overlaid;	/* overlaid directory */
+	struct dentry *d_topmost;	/* topmost directory */
+	struct union_info *d_union;	/* union directory info */
+#endif
+
 	struct list_head d_lru;		/* LRU list */
 	/*
 	 * d_child and d_rcu can share memory
--- /dev/null
+++ b/include/linux/dcache_union.h
@@ -0,0 +1,248 @@
+/*
+ * VFS based union mount for Linux
+ *
+ * Copyright © 2004-2007 IBM Corporation
+ *   Author(s): Jan Blunck (j.blunck@tu-harburg.de)
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the Free
+ * Software Foundation; either version 2 of the License, or (at your option)
+ * any later version.
+ *
+ */
+#ifndef __LINUX_DCACHE_UNION_H
+#define __LINUX_DCACHE_UNION_H
+#ifdef __KERNEL__
+
+#include <linux/union_debug.h>
+#include <linux/fs_struct.h>
+#include <asm/atomic.h>
+#include <asm/semaphore.h>
+
+#ifdef CONFIG_UNION_MOUNT
+
+/*
+ * This is the union info object, that describes general information about this
+ * union directory
+ *
+ * u_mutex protects the union stack against modification. You can reach it
+ * through the d_union field in struct dentry. Hold it when you are walking
+ * or modifing the union stack !
+ */
+struct union_info {
+	atomic_t u_count;
+	struct mutex u_mutex;
+};
+
+/* allocate/de-allocate */
+extern struct union_info *union_alloc(void);
+extern struct union_info *union_get(struct union_info *);
+extern void union_put(struct union_info *);
+
+/*
+ * These are the functions for locking a dentry's union. When one
+ * want to acquire a denties union lock, use:
+ *
+ * - union_lock() when you can sleep,
+ * - union_lock_spinlock() when you are holding a spinlock (that
+ *   you CAN savely give up and reacquire again)
+ * - union_lock_readlock() when you are holding a readlock (that
+ *   you CAN savely give up and reacquire again)
+ *
+ * Otherwise get the union lock early before you enter your
+ * "no sleeping here" code.
+ *
+ * NOTES: union_info structure is reference counted using u_count member.
+ * union_get() and union_put() which get and put references on union_info
+ * should be done under union_info's u_mutex. Since the last union_put() frees
+ * the union_info structure itself it can't obviously be done under u_mutex.
+ * union_release() should be used in such cases (Eg. dput(), umount()) where
+ * union_info is disassociated from the dentries, and it becomes safe
+ * to free the union_info.
+ */
+static inline void __union_lock(struct union_info *uinfo)
+{
+	BUG_ON(!atomic_read(&uinfo->u_count));
+	mutex_lock(&uinfo->u_mutex);
+}
+
+static inline void union_lock(struct dentry *dentry)
+{
+	if (unlikely(dentry && dentry->d_union)) {
+		struct union_info *ui = dentry->d_union;
+
+		UM_DEBUG_LOCK("\"%s\" locking %p (count=%d)\n",
+			      dentry->d_name.name, ui,
+			      atomic_read(&ui->u_count));
+		__union_lock(dentry->d_union);
+	}
+}
+
+static inline void __union_unlock(struct union_info *uinfo)
+{
+	BUG_ON(!atomic_read(&uinfo->u_count));
+	mutex_unlock(&uinfo->u_mutex);
+}
+
+static inline void union_unlock(struct dentry *dentry)
+{
+	if (unlikely(dentry && dentry->d_union)) {
+		struct union_info *ui = dentry->d_union;
+
+		UM_DEBUG_LOCK("\"%s\" unlocking %p (count=%d)\n",
+			      dentry->d_name.name, ui,
+			      atomic_read(&ui->u_count));
+		__union_unlock(dentry->d_union);
+	}
+}
+
+static inline void union_alloc_dentry(struct dentry *dentry)
+{
+	spin_lock(&dentry->d_lock);
+	if (!dentry->d_union) {
+		dentry->d_union = union_alloc();
+		spin_unlock(&dentry->d_lock);
+	} else {
+		spin_unlock(&dentry->d_lock);
+		union_lock(dentry);
+	}
+}
+
+static inline struct union_info *union_lock_and_get(struct dentry *dentry)
+{
+	union_lock(dentry);
+	return union_get(dentry->d_union);
+}
+
+/* Shouldn't be called with last reference to union_info */
+static inline void union_put_and_unlock(struct union_info *uinfo)
+{
+	union_put(uinfo);
+	__union_unlock(&uinfo->u_mutex);
+}
+
+/*
+ * Called when we know for sure that there is no reference
+ * to this union_info from any dentry and it can be safely
+ * destroyed.
+ */
+static inline void union_release(struct union_info *uinfo)
+{
+	if (!uinfo)
+		return;
+
+	mutex_unlock(&uinfo->u_mutex);
+	union_put(uinfo);
+}
+
+/*
+ * Immediately return ZERO if the lock is contended, NON-ZERO if it's acquired.
+ */
+static inline int union_trylock(struct dentry *dentry)
+{
+	int locked = 1;
+
+	if (unlikely(dentry && dentry->d_union)) {
+		UM_DEBUG_LOCK("\"%s\" try locking %p (count=%d)\n",
+			      dentry->d_name.name, dentry->d_union,
+			      atomic_read(&dentry->d_union->u_count));
+		BUG_ON(!atomic_read(&dentry->d_union->u_count));
+		locked = mutex_trylock(&dentry->d_union->u_mutex);
+		UM_DEBUG_LOCK("\"%s\" trylock %p %s\n", dentry->d_name.name,
+			      dentry->d_union,
+			      locked ? "succeeded" : "failed");
+	}
+	return (locked ? 1 : 0);
+}
+
+/*
+ * The following functions are locking helpers to guarantee the locking order
+ * in some situations.
+ */
+
+static inline void union_lock_spinlock(struct dentry *dentry, spinlock_t *lock)
+{
+	while (!union_trylock(dentry)) {
+		spin_unlock(lock);
+		cpu_relax();
+		spin_lock(lock);
+	}
+}
+
+static inline void union_lock_readlock(struct dentry *dentry, rwlock_t *lock)
+{
+	while (!union_trylock(dentry)) {
+		read_unlock(lock);
+		cpu_relax();
+		read_lock(lock);
+	}
+}
+
+/*
+ * This is a *I can't get no sleep* helper which is called when we try
+ * to access the struct fs_struct *fs field of a struct task_struct.
+ *
+ * Yes, this is possibly starving but we have to change root, altroot
+ * or pwd in the frequency of this while loop. Don't think that this
+ * happens really often ;)
+ *
+ * This is called while holding the rwlock_t fs->lock
+ *
+ * TODO: Unlocking side of union_lock_fs() needs 3 union_unlock()s.
+ * May be introduce union_unlock_fs().
+ *
+ * FIXME: This routine is used when the caller wants to dget one or
+ * more of fs->[root, altroot, pwd]. When the caller doesn't want to
+ * dget _all_ of these, it is strictly not necessary to get union_locks
+ * on all of these. Check.
+ */
+static inline void union_lock_fs(struct fs_struct *fs)
+{
+	int locked;
+
+	while (fs) {
+		locked = union_trylock(fs->root);
+		if (!locked)
+			goto loop1;
+		locked = union_trylock(fs->altroot);
+		if (!locked)
+			goto loop2;
+		locked = union_trylock(fs->pwd);
+		if (!locked)
+			goto loop3;
+		break;
+	loop3:
+		union_unlock(fs->altroot);
+	loop2:
+		union_unlock(fs->root);
+	loop1:
+		read_unlock(&fs->lock);
+		UM_DEBUG_LOCK("Failed to get all semaphores in fs_struct!\n");
+		cpu_relax();
+		read_lock(&fs->lock);
+		continue;
+	}
+	BUG_ON(!fs);
+	return;
+}
+
+#define IS_UNION(dentry) ((dentry)->d_overlaid || (dentry)->d_topmost || \
+				(dentry)->d_overlaid)
+
+#else /* CONFIG_UNION_MOUNT */
+
+#define union_lock(dentry) do { /* empty */ } while (0)
+#define union_trylock(dentry) ({ (1); })
+#define union_unlock(dentry) do { /* empty */ } while (0)
+#define union_lock_spinlock(dentry, lock) do { /* empty */ } while (0)
+#define union_lock_readlock(dentry, lock) do { /* empty */ } while (0)
+#define union_lock_fs(fs) do { /* empty */ } while (0)
+#define IS_UNION(dentry) ({ (0); })
+#define union_alloc_dentry(x) ({ BUG(); (0); })
+#define union_lock_and_get(dentry) ({ (NULL); })
+#define union_unlock_and_put(dentry) do { /* empty */ } while (0)
+#define union_release(x) do { BUG(); } while (0)
+
+#endif	/* CONFIG_UNION_MOUNT */
+#endif	/* __KERNEL__ */
+#endif	/* __LINUX_DCACHE_UNION_H */