[PATCH review 3/6] dcache: Implement d_common_ancestor

[Eric W. Biederman]

If possible find the common ancestor of two dentries.

This is necessary infrastructure for better handling the case
when a dentry is moved out from under the root of a bind mount.

Signed-off-by: "Eric W. Biederman" <ebiederm at xmission.com>
---
 fs/dcache.c            | 37 +++++++++++++++++++++++++++++++++++++
 include/linux/dcache.h |  1 +
 2 files changed, 38 insertions(+)

diff --git a/fs/dcache.c b/fs/dcache.c
index d7fe995dd32d..9f4de1007a8d 100644
--- a/fs/dcache.c
+++ b/fs/dcache.c
@@ -2472,6 +2472,43 @@ void dentry_update_name_case(struct dentry *dentry, struct qstr *name)
 }
 EXPORT_SYMBOL(dentry_update_name_case);
 
+static unsigned long d_depth(const struct dentry *dentry)
+{
+	unsigned long depth = 0;
+
+	while (!IS_ROOT(dentry)) {
+		dentry = dentry->d_parent;
+		depth++;
+	}
+	return depth;
+}
+
+const struct dentry *d_common_ancestor(const struct dentry *left,
+				       const struct dentry *right)
+{
+	unsigned long ldepth = d_depth(left);
+	unsigned long rdepth = d_depth(right);
+
+	while (ldepth > rdepth) {
+		left = left->d_parent;
+		ldepth--;
+	}
+
+	while (rdepth > ldepth) {
+		right = right->d_parent;
+		rdepth--;
+	}
+
+	while (left != right) {
+		if (IS_ROOT(left))
+			return NULL;
+		left = left->d_parent;
+		right = right->d_parent;
+	}
+
+	return left;
+}
+
 static void swap_names(struct dentry *dentry, struct dentry *target)
 {
 	if (unlikely(dname_external(target))) {
diff --git a/include/linux/dcache.h b/include/linux/dcache.h
index 52a5e6915f58..56de8288cdee 100644
--- a/include/linux/dcache.h
+++ b/include/linux/dcache.h
@@ -313,6 +313,7 @@ extern void dentry_update_name_case(struct dentry *, struct qstr *);
 extern void d_move(struct dentry *, struct dentry *);
 extern void d_exchange(struct dentry *, struct dentry *);
 extern struct dentry *d_ancestor(struct dentry *, struct dentry *);
+extern const struct dentry *d_common_ancestor(const struct dentry *, const struct dentry *);
 
 /* appendix may either be NULL or be used for transname suffixes */
 extern struct dentry *d_lookup(const struct dentry *, const struct qstr *);
-- 
2.2.1