Skip to contentSkip to conversation

Overlayfs file handle decode optimization

PATCH Superseded Amir Goldstein 2 participants 12 messages Feb 6, 2018 – Feb 16, 2018

Subsystems (2)

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

Amir Goldstein

author maintainer
#0 lore raw

cover Overlayfs file handle decode optimization

Miklos,

This patch set completes the known 'debt' for the NFS export work and is available with the rest if the 'debt' and fixes on my github [1].

Patch 2 is a cosmetic re-factoring of dcache name hash functions. I tried hard to make sure there is no-change to existing users. Please double check me on that.

To verify optimization, I ran all the overlay/exportfs tests, which are now upstream. I added prints to real fs decode functions to verify they are not called when decoding a lower dir file handle of a deleted dir.

To verify the hash function, I added prints inside iget5_locked() to check when an inode is added to an empty hash list and then I ran some tests to populate cache with a few 1000 upper or lower inodes.

When populated with pure upper inodes, the hash values were far less random (pointer values) and out of 2000 inodes there were 1-5 hash collisions depending on the test run.

When populated with pure lower inodes, the hash values seemed more random and out of 2000 inodes there were 3-4 hash collisions depending on the test run. So for a quick test that seem to indicate that the file handle hash function is at least better than the real inode hash. The real lower file handles were xfs file handles all with the same uuid, with sequential 64-bit inode numbers and zero generation (xfs inodes on a newly formatted fs).

I guess it is possible to improve the efficiency of the hash function by xoring the 16 bytes of uuid to a single long value and feeding it as salt to full_name_long_hash() instead of computing a hash on the uuid which is already random.

Performance benchmarks/regression testing is high on my TODO list, but still did not get there.

Thanks,
Amir.

[1] https://github.com/amir73il/linux/commits/ovl-nfs-export

Amir Goldstein (4):
ovl: disambiguate ovl_encode_fh()
fs/namei.c: factor out helper full_name_long_hash()
ovl: hash inodes by lower file handle for NFS export
ovl: lookup in inode cache when decoding lower file handle

 fs/namei.c                 | 41 +++++++++++++++++-------
 fs/overlayfs/copy_up.c     |  6 ++--
 fs/overlayfs/export.c      | 51 +++++++++++++----------------
 fs/overlayfs/inode.c       | 80 +++++++++++++++++++++++++++++++++++++++++++---
 fs/overlayfs/namei.c       | 12 +++----
 fs/overlayfs/overlayfs.h   | 13 ++++++--
 fs/overlayfs/super.c       |  2 ++
 include/linux/hash.h       | 10 +++++-
 include/linux/stringhash.h |  6 +++-
 9 files changed, 163 insertions(+), 58 deletions(-)
Signature · 1 line
2.7.4
author maintainer
#1 lore raw

RFC PATCH 1/1 ovl: check lower ancestry on encode of lower dir file handle

This change relaxes copy up on encode of merge dir with lower layer > 1 and handles the case of encoding a merge dir with lower layer 1, where an ancestor is a non-indexed merge dir. In that case, decode of the lower file handle will not have been possible if the non-indexed ancestor is redirected before or after encode.

Before encoding a non-upper directory file handle from real layer N, we need to check if it will be possible to reconnect an overlay dentry from the real lower decoded dentry. This is done by following the overlay ancestry up to a 'layer N connected' ancestor and verifying that all parents along the way are 'layer N connectable'. If an ancestor that is NOT 'layer N connectable' is found, we need to copy up an ancestor, which is 'layer N connectable', thus making that ancestor 'layer N connected'. For example:

layer 1: /a
layer 2: /a/b/c

The overlay dentry /a is NOT 'layer 2 connectable', because if dir /a is copied up and renamed, upper dir /a will be indexed by lower dir /a from layer 1. The dir /a from layer 2 will never be indexed, so the alrogithm in ovl_lookup_real_ancestor() (*) will not be able to lookup a connected overlay dentry from the connected lower dentry /a/b/c.

To avoid this problem on decode time, we need to copy up an ancestor of /a/b/c, which is 'layer 2 connectable', on encode time. That ancestor is /a/b. After copy up (and index) of /a/b, it will become 'layer 2 connected' and when the time comes to decode the file handle from lower dentry /a/b/c, ovl_lookup_real_ancestor() will find the indexed ancestor /a/b and decoding a connected overlay dentry will be accomplished.

(*) the alrogithm in ovl_lookup_real_ancestor() can be improved to lookup an entry /a in the lower layers above layer N and find the indexed dir /a from layer 1. If that improvement is made, then the check for 'layer N connected' will need to verify there are no redirects in lower layers above layer N. In the example above, /a will be 'layer 2 connectable'. However, if layer 2 dir /a is a target of a layer 1 redirect, then /a will NOT be 'layer 2 connectable':

layer 1: /A (redirect = /a)
layer 2: /a/b/c

---

Miklos,

I was able to convince myself that this patch is correct and it passed all existing tests and some manual tests of the new cases.

I was also able to convince myself that the single CONNECTED bit in dentry is all the optimization we need and that there is no added value in gathering more state information on lookup.
This extra lookup information or redirected lower layers will be needed if we ever implement (*) above.

Was I able to also convince you that this patch is correct? and that no extra lookup information is needed?

I will write more tests to cover the cases handles by this change.

Thanks,
Amir.

 fs/overlayfs/export.c    | 176 +++++++++++++++++++++++++++++++++++++++--------
 fs/overlayfs/overlayfs.h |   1 +
 2 files changed, 147 insertions(+), 30 deletions(-)
fs/overlayfs/export.c +146 -30
index 07d70255095b..b545e3b8249f 100644
@@ -19,6 +19,138 @@
 #include <linux/ratelimit.h>
 #include "overlayfs.h"
 
+
+static int ovl_encode_maybe_copy_up(struct dentry *dentry)
+{
+	int err;
+
+	if (ovl_dentry_upper(dentry))
+		return 0;
+
+	err = ovl_want_write(dentry);
+	if (!err) {
+		err = ovl_copy_up(dentry);
+		ovl_drop_write(dentry);
+	}
+
+	if (err) {
+		pr_warn_ratelimited("overlayfs: failed to copy up on encode (%pd2, err=%i)\n",
+				    dentry, err);
+	}
+
+	return err;
+}
+
+/*
+ * Before encoding a non-upper directory file handle from real layer N, we need
+ * to check if it will be possible to reconnect an overlay dentry from the real
+ * lower decoded dentry. This is done by following the overlay ancestry up to a
+ * 'layer N connected' ancestor and verifying that all parents along the way are
+ * 'layer N connectable'. If an ancestor that is NOT 'layer N connectable' is
+ * found, we need to copy up an ancestor, which is 'layer N connectable', thus
+ * making that ancestor 'layer N connected'. For example:
+ *
+ * layer 1: /a
+ * layer 2: /a/b/c
+ *
+ * The overlay dentry /a is NOT 'layer 2 connectable', because if dir /a is
+ * copied up and renamed, upper dir /a will be indexed by lower dir /a from
+ * layer 1. The dir /a from layer 2 will never be indexed, so the alrogithm (*)
+ * in ovl_lookup_real_ancestor() will not be able to lookup a connected overlay
+ * dentry from the connected lower dentry /a/b/c.
+ *
+ * To avoid this problem on decode time, we need to copy up an ancestor of
+ * /a/b/c, which is 'layer 2 connectable', on encode time. That ancestor is
+ * /a/b. After copy up (and index) of /a/b, it will become 'layer 2 connected'
+ * and when the time comes to decode the file handle from lower dentry /a/b/c,
+ * ovl_lookup_real_ancestor() will find the indexed ancestor /a/b and decoding
+ * a connected overlay dentry will be accomplished.
+ *
+ * (*) the alrogithm in ovl_lookup_real_ancestor() can be improved to lookup an
+ * entry /a in the lower layers above layer N and find the indexed dir /a from
+ * layer 1. If that improvement is made, then the check for 'layer N connected'
+ * will need to verify there are no redirects in lower layers above N. In the
+ * example above, /a will be 'layer 2 connectable'. However, if layer 2 dir /a
+ * is a target of a layer 1 redirect, then /a will NOT be 'layer 2 connectable':
+ *
+ * layer 1: /A (redirect = /a)
+ * layer 2: /a/b/c
+ */
+static int ovl_dentry_connectable_layer(struct dentry *dentry)
+{
+	struct ovl_entry *oe = OVL_E(dentry);
+
+	/* We can get overlay root from root of any layer */
+	if (dentry == dentry->d_sb->s_root)
+		return oe->numlower;
+
+	/* We cannot get upper/overlay path from non-indexed lower dentry */
+	if (ovl_dentry_upper(dentry) &&
+	    !ovl_test_flag(OVL_INDEX, d_inode(dentry)))
+		return 0;
+
+	/* Pure upper cannot be ancestor of non pure upper */
+	if (WARN_ON(!oe->numlower))
+		return 0;
+
+	/* We can get upper/overlay path from indexed/lower dentry */
+	return oe->lowerstack[0].layer->idx;
+}
+
+/*
+ * @dentry is 'connected' if all ancestors up to root or a 'connected' ancestor
+ * have the same uppermost lower layer as the origin's layer. We may need to
+ * copy up a 'connectable' ancestor to make it 'connected'. A 'connected' dentry
+ * cannot become non 'connected', so cache positive result in dentry flags.
+ */
+static bool ovl_dentry_connect(struct dentry *dentry)
+{
+	struct dentry *next, *parent = NULL;
+	int origin_layer;
+	int err = 0;
+
+	if (ovl_dentry_test_flag(OVL_E_CONNECTED, dentry))
+		return true;
+
+	if (WARN_ON(dentry == dentry->d_sb->s_root) ||
+	    WARN_ON(!ovl_dentry_lower(dentry)))
+		return true;
+
+	/* Find the topmost origin layer connectable ancestor of @dentry */
+	origin_layer = OVL_E(dentry)->lowerstack[0].layer->idx;
+	next = dget(dentry);
+	for (;;) {
+		parent = dget_parent(next);
+
+		/*
+		 * If @parent is not origin layer connectable, then copy up
+		 * @next which is origin layer connectable and we are done.
+		 */
+		if (ovl_dentry_connectable_layer(parent) < origin_layer) {
+			err = ovl_encode_maybe_copy_up(next);
+			break;
+		}
+
+		/* If parent is connected we are done */
+		if (ovl_dentry_test_flag(OVL_E_CONNECTED, dentry))
+			return true;
+
+		/* If parent is root or indexed we are done */
+		if (parent == next || ovl_test_flag(OVL_INDEX, d_inode(parent)))
+			break;
+
+		dput(next);
+		next = parent;
+	}
+
+	dput(parent);
+	dput(next);
+
+	if (!err)
+		ovl_dentry_set_flag(OVL_E_CONNECTED, dentry);
+	return !err;
+}
+
 /*
  * We only need to encode origin if there is a chance that the same object was
  * encoded pre copy up and then we need to stay consistent with the same
@@ -42,7 +174,7 @@
  *
  * (*) Connecting an overlay dir from real lower dentry is not always
  * possible when there are redirects in lower layers. To mitigate this case,
- * we copy up the lower dir first and then encode an upper dir file handle.
+ * we may copy up the lower dir first and then encode an upper dir file handle.
  */
 static bool ovl_should_encode_origin(struct dentry *dentry)
 {
@@ -51,41 +183,25 @@ static bool ovl_should_encode_origin(struct dentry *dentry)
 	if (!ovl_dentry_lower(dentry))
 		return false;
 
-	/*
-	 * Decoding a merge dir, whose origin's parent is under a redirected
-	 * lower dir is not always possible. As a simple aproximation, we do
-	 * not encode lower dir file handles when overlay has multiple lower
-	 * layers and origin is below the topmost lower layer.
-	 *
-	 * TODO: copy up only the parent that is under redirected lower.
-	 */
-	if (d_is_dir(dentry) && ofs->upper_mnt &&
-	    OVL_E(dentry)->lowerstack[0].layer->idx > 1)
-		return false;
-
 	/* Decoding a non-indexed upper from origin is not implemented */
 	if (ovl_dentry_upper(dentry) &&
 	    !ovl_test_flag(OVL_INDEX, d_inode(dentry)))
 		return false;
 
-	return true;
-}
-
-static int ovl_encode_maybe_copy_up(struct dentry *dentry)
-{
-	int err;
-
-	if (ovl_dentry_upper(dentry))
-		return 0;
-
-	err = ovl_want_write(dentry);
-	if (err)
-		return err;
-
-	err = ovl_copy_up(dentry);
+	/*
+	 * Decoding a merge dir, whose origin's ancestor is under a redirected
+	 * lower dir is not always possible. As a simple aproximation, we do
+	 * not encode lower dir file handles when overlay has multiple lower
+	 * layers and origin is on a non 'connectable' layer.
+	 * ovl_dentry_connect() will try to make origin's layer 'connected' by
+	 * copying up a 'connectable' ancestor. If ovl_dentry_connect() cannot
+	 * find a 'connectable' ancestor, it will return false and then this
+	 * dentry will be copied up and encoded as an upper file handle.
+	 */
+	if (d_is_dir(dentry) && ofs->upper_mnt)
+		return ovl_dentry_connect(dentry);
 
-	ovl_drop_write(dentry);
-	return err;
+	return true;
 }
 
 static int ovl_d_to_fh(struct dentry *dentry, char *buf, int buflen)
fs/overlayfs/overlayfs.h +1 -0
index 0df25a9c94bd..225ff1171147 100644
@@ -40,6 +40,7 @@ enum ovl_inode_flag {
 enum ovl_entry_flag {
 	OVL_E_UPPER_ALIAS,
 	OVL_E_OPAQUE,
+	OVL_E_CONNECTED,
 };
 
 /*
Signature · 1 line
2.7.4
maintainer
#2 lore raw

Re: [RFC][PATCH] ovl: check lower ancestry on encode of lower dir file handle

Quoted 6 lines · Amir Goldstein

This change relaxes copy up on encode of merge dir with lower layer > 1 and handles the case of encoding a merge dir with lower layer 1, where an ancestor is a non-indexed merge dir. In that case, decode of the lower file handle will not have been possible if the non-indexed ancestor is redirected before or after encode.

Quoted 7 lines

Before encoding a non-upper directory file handle from real layer N, we need to check if it will be possible to reconnect an overlay dentry from the real lower decoded dentry. This is done by following the overlay ancestry up to a 'layer N connected' ancestor and verifying that all parents along the way are 'layer N connectable'. If an ancestor that is NOT 'layer N connectable' is found, we need to copy up an ancestor, which is 'layer N connectable', thus making that ancestor 'layer N connected'.

Makes sense. One comment inline, otherwise looks good.

Quoted 120 lines

For example:

layer 1: /a
layer 2: /a/b/c

The overlay dentry /a is NOT 'layer 2 connectable', because if dir /a is copied up and renamed, upper dir /a will be indexed by lower dir /a from layer 1. The dir /a from layer 2 will never be indexed, so the alrogithm in ovl_lookup_real_ancestor() (*) will not be able to lookup a connected overlay dentry from the connected lower dentry /a/b/c.

To avoid this problem on decode time, we need to copy up an ancestor of /a/b/c, which is 'layer 2 connectable', on encode time. That ancestor is /a/b. After copy up (and index) of /a/b, it will become 'layer 2 connected' and when the time comes to decode the file handle from lower dentry /a/b/c, ovl_lookup_real_ancestor() will find the indexed ancestor /a/b and decoding a connected overlay dentry will be accomplished.

(*) the alrogithm in ovl_lookup_real_ancestor() can be improved to lookup an entry /a in the lower layers above layer N and find the indexed dir /a from layer 1. If that improvement is made, then the check for 'layer N connected' will need to verify there are no redirects in lower layers above layer N. In the example above, /a will be 'layer 2 connectable'. However, if layer 2 dir /a is a target of a layer 1 redirect, then /a will NOT be 'layer 2 connectable':

layer 1: /A (redirect = /a)
layer 2: /a/b/c

---

Miklos,

I was able to convince myself that this patch is correct and it passed all existing tests and some manual tests of the new cases.

I was also able to convince myself that the single CONNECTED bit in dentry is all the optimization we need and that there is no added value in gathering more state information on lookup.
This extra lookup information or redirected lower layers will be needed if we ever implement (*) above.

Was I able to also convince you that this patch is correct? and that no extra lookup information is needed?

I will write more tests to cover the cases handles by this change.

Thanks,
Amir.

 fs/overlayfs/export.c    | 176 +++++++++++++++++++++++++++++++++++++++--------
 fs/overlayfs/overlayfs.h |   1 +
 2 files changed, 147 insertions(+), 30 deletions(-)
fs/overlayfs/export.c +57 -0
index 07d70255095b..b545e3b8249f 100644
@@ -19,6 +19,138 @@
 #include <linux/ratelimit.h>
 #include "overlayfs.h"
 
+
+static int ovl_encode_maybe_copy_up(struct dentry *dentry)
+{
+       int err;
+
+       if (ovl_dentry_upper(dentry))
+               return 0;
+
+       err = ovl_want_write(dentry);
+       if (!err) {
+               err = ovl_copy_up(dentry);
+               ovl_drop_write(dentry);
+       }
+
+       if (err) {
+               pr_warn_ratelimited("overlayfs: failed to copy up on encode (%pd2, err=%i)\n",
+                                   dentry, err);
+       }
+
+       return err;
+}
+
+/*
+ * Before encoding a non-upper directory file handle from real layer N, we need
+ * to check if it will be possible to reconnect an overlay dentry from the real
+ * lower decoded dentry. This is done by following the overlay ancestry up to a
+ * 'layer N connected' ancestor and verifying that all parents along the way are
+ * 'layer N connectable'. If an ancestor that is NOT 'layer N connectable' is
+ * found, we need to copy up an ancestor, which is 'layer N connectable', thus
+ * making that ancestor 'layer N connected'. For example:
+ *
+ * layer 1: /a
+ * layer 2: /a/b/c
+ *
+ * The overlay dentry /a is NOT 'layer 2 connectable', because if dir /a is
+ * copied up and renamed, upper dir /a will be indexed by lower dir /a from
+ * layer 1. The dir /a from layer 2 will never be indexed, so the alrogithm (*)
+ * in ovl_lookup_real_ancestor() will not be able to lookup a connected overlay
+ * dentry from the connected lower dentry /a/b/c.
+ *
+ * To avoid this problem on decode time, we need to copy up an ancestor of
+ * /a/b/c, which is 'layer 2 connectable', on encode time. That ancestor is
+ * /a/b. After copy up (and index) of /a/b, it will become 'layer 2 connected'
+ * and when the time comes to decode the file handle from lower dentry /a/b/c,
+ * ovl_lookup_real_ancestor() will find the indexed ancestor /a/b and decoding
+ * a connected overlay dentry will be accomplished.
+ *
+ * (*) the alrogithm in ovl_lookup_real_ancestor() can be improved to lookup an
+ * entry /a in the lower layers above layer N and find the indexed dir /a from
+ * layer 1. If that improvement is made, then the check for 'layer N connected'
+ * will need to verify there are no redirects in lower layers above N. In the
+ * example above, /a will be 'layer 2 connectable'. However, if layer 2 dir /a
+ * is a target of a layer 1 redirect, then /a will NOT be 'layer 2 connectable':
+ *
+ * layer 1: /A (redirect = /a)
+ * layer 2: /a/b/c
+ */

fs/overlayfs/export.c line 88

Quoted 10 lines
fs/overlayfs/export.c +10 -0
+static int ovl_dentry_connectable_layer(struct dentry *dentry)
+{
+       struct ovl_entry *oe = OVL_E(dentry);
+
+       /* We can get overlay root from root of any layer */
+       if (dentry == dentry->d_sb->s_root)
+               return oe->numlower;
+
+       /* We cannot get upper/overlay path from non-indexed lower dentry */
+       if (ovl_dentry_upper(dentry) &&

Code is contradicting comment. I guess code is wrong?

Quoted 147 lines
fs/overlayfs/export.c +79 -30
+           !ovl_test_flag(OVL_INDEX, d_inode(dentry)))
+               return 0;
+
+       /* Pure upper cannot be ancestor of non pure upper */
+       if (WARN_ON(!oe->numlower))
+               return 0;
+
+       /* We can get upper/overlay path from indexed/lower dentry */
+       return oe->lowerstack[0].layer->idx;
+}
+
+/*
+ * @dentry is 'connected' if all ancestors up to root or a 'connected' ancestor
+ * have the same uppermost lower layer as the origin's layer. We may need to
+ * copy up a 'connectable' ancestor to make it 'connected'. A 'connected' dentry
+ * cannot become non 'connected', so cache positive result in dentry flags.
+ */
+static bool ovl_dentry_connect(struct dentry *dentry)
+{
+       struct dentry *next, *parent = NULL;
+       int origin_layer;
+       int err = 0;
+
+       if (ovl_dentry_test_flag(OVL_E_CONNECTED, dentry))
+               return true;
+
+       if (WARN_ON(dentry == dentry->d_sb->s_root) ||
+           WARN_ON(!ovl_dentry_lower(dentry)))
+               return true;
+
+       /* Find the topmost origin layer connectable ancestor of @dentry */
+       origin_layer = OVL_E(dentry)->lowerstack[0].layer->idx;
+       next = dget(dentry);
+       for (;;) {
+               parent = dget_parent(next);
+
+               /*
+                * If @parent is not origin layer connectable, then copy up
+                * @next which is origin layer connectable and we are done.
+                */
+               if (ovl_dentry_connectable_layer(parent) < origin_layer) {
+                       err = ovl_encode_maybe_copy_up(next);
+                       break;
+               }
+
+               /* If parent is connected we are done */
+               if (ovl_dentry_test_flag(OVL_E_CONNECTED, dentry))
+                       return true;
+
+               /* If parent is root or indexed we are done */
+               if (parent == next || ovl_test_flag(OVL_INDEX, d_inode(parent)))
+                       break;
+
+               dput(next);
+               next = parent;
+       }
+
+       dput(parent);
+       dput(next);
+
+       if (!err)
+               ovl_dentry_set_flag(OVL_E_CONNECTED, dentry);
+       return !err;
+}
+
 /*
  * We only need to encode origin if there is a chance that the same object was
  * encoded pre copy up and then we need to stay consistent with the same
@@ -42,7 +174,7 @@
  *
  * (*) Connecting an overlay dir from real lower dentry is not always
  * possible when there are redirects in lower layers. To mitigate this case,
- * we copy up the lower dir first and then encode an upper dir file handle.
+ * we may copy up the lower dir first and then encode an upper dir file handle.
  */
 static bool ovl_should_encode_origin(struct dentry *dentry)
 {
@@ -51,41 +183,25 @@ static bool ovl_should_encode_origin(struct dentry *dentry)
        if (!ovl_dentry_lower(dentry))
                return false;
 
-       /*
-        * Decoding a merge dir, whose origin's parent is under a redirected
-        * lower dir is not always possible. As a simple aproximation, we do
-        * not encode lower dir file handles when overlay has multiple lower
-        * layers and origin is below the topmost lower layer.
-        *
-        * TODO: copy up only the parent that is under redirected lower.
-        */
-       if (d_is_dir(dentry) && ofs->upper_mnt &&
-           OVL_E(dentry)->lowerstack[0].layer->idx > 1)
-               return false;
-
        /* Decoding a non-indexed upper from origin is not implemented */
        if (ovl_dentry_upper(dentry) &&
            !ovl_test_flag(OVL_INDEX, d_inode(dentry)))
                return false;
 
-       return true;
-}
-
-static int ovl_encode_maybe_copy_up(struct dentry *dentry)
-{
-       int err;
-
-       if (ovl_dentry_upper(dentry))
-               return 0;
-
-       err = ovl_want_write(dentry);
-       if (err)
-               return err;
-
-       err = ovl_copy_up(dentry);
+       /*
+        * Decoding a merge dir, whose origin's ancestor is under a redirected
+        * lower dir is not always possible. As a simple aproximation, we do
+        * not encode lower dir file handles when overlay has multiple lower
+        * layers and origin is on a non 'connectable' layer.
+        * ovl_dentry_connect() will try to make origin's layer 'connected' by
+        * copying up a 'connectable' ancestor. If ovl_dentry_connect() cannot
+        * find a 'connectable' ancestor, it will return false and then this
+        * dentry will be copied up and encoded as an upper file handle.
+        */
+       if (d_is_dir(dentry) && ofs->upper_mnt)
+               return ovl_dentry_connect(dentry);
 
-       ovl_drop_write(dentry);
-       return err;
+       return true;
 }
 
 static int ovl_d_to_fh(struct dentry *dentry, char *buf, int buflen)
fs/overlayfs/overlayfs.h +1 -1
index 0df25a9c94bd..225ff1171147 100644
@@ -40,6 +40,7 @@ enum ovl_inode_flag {
 enum ovl_entry_flag {
        OVL_E_UPPER_ALIAS,
        OVL_E_OPAQUE,
+       OVL_E_CONNECTED,
 };
 
 /*
--

2.7.4

author maintainer
#3 lore raw

Re: [RFC][PATCH] ovl: check lower ancestry on encode of lower dir file handle

Quoted 141 lines · Miklos Szeredi
Quoted 6 lines · Amir Goldstein

This change relaxes copy up on encode of merge dir with lower layer > 1 and handles the case of encoding a merge dir with lower layer 1, where an ancestor is a non-indexed merge dir. In that case, decode of the lower file handle will not have been possible if the non-indexed ancestor is redirected before or after encode.

Quoted 7 lines

Before encoding a non-upper directory file handle from real layer N, we need to check if it will be possible to reconnect an overlay dentry from the real lower decoded dentry. This is done by following the overlay ancestry up to a 'layer N connected' ancestor and verifying that all parents along the way are 'layer N connectable'. If an ancestor that is NOT 'layer N connectable' is found, we need to copy up an ancestor, which is 'layer N connectable', thus making that ancestor 'layer N connected'.

Makes sense. One comment inline, otherwise looks good.

Quoted 124 lines

For example:

layer 1: /a
layer 2: /a/b/c

The overlay dentry /a is NOT 'layer 2 connectable', because if dir /a is copied up and renamed, upper dir /a will be indexed by lower dir /a from layer 1. The dir /a from layer 2 will never be indexed, so the alrogithm in ovl_lookup_real_ancestor() (*) will not be able to lookup a connected overlay dentry from the connected lower dentry /a/b/c.

To avoid this problem on decode time, we need to copy up an ancestor of /a/b/c, which is 'layer 2 connectable', on encode time. That ancestor is /a/b. After copy up (and index) of /a/b, it will become 'layer 2 connected' and when the time comes to decode the file handle from lower dentry /a/b/c, ovl_lookup_real_ancestor() will find the indexed ancestor /a/b and decoding a connected overlay dentry will be accomplished.

(*) the alrogithm in ovl_lookup_real_ancestor() can be improved to lookup an entry /a in the lower layers above layer N and find the indexed dir /a from layer 1. If that improvement is made, then the check for 'layer N connected' will need to verify there are no redirects in lower layers above layer N. In the example above, /a will be 'layer 2 connectable'. However, if layer 2 dir /a is a target of a layer 1 redirect, then /a will NOT be 'layer 2 connectable':

layer 1: /A (redirect = /a)
layer 2: /a/b/c

---

Miklos,

I was able to convince myself that this patch is correct and it passed all existing tests and some manual tests of the new cases.

I was also able to convince myself that the single CONNECTED bit in dentry is all the optimization we need and that there is no added value in gathering more state information on lookup.
This extra lookup information or redirected lower layers will be needed if we ever implement (*) above.

Was I able to also convince you that this patch is correct? and that no extra lookup information is needed?

I will write more tests to cover the cases handles by this change.

Thanks,
Amir.

 fs/overlayfs/export.c    | 176 +++++++++++++++++++++++++++++++++++++++--------
 fs/overlayfs/overlayfs.h |   1 +
 2 files changed, 147 insertions(+), 30 deletions(-)
fs/overlayfs/export.c +61 -0
index 07d70255095b..b545e3b8249f 100644
@@ -19,6 +19,138 @@
 #include <linux/ratelimit.h>
 #include "overlayfs.h"
 
+
+static int ovl_encode_maybe_copy_up(struct dentry *dentry)
+{
+       int err;
+
+       if (ovl_dentry_upper(dentry))
+               return 0;
+
+       err = ovl_want_write(dentry);
+       if (!err) {
+               err = ovl_copy_up(dentry);
+               ovl_drop_write(dentry);
+       }
+
+       if (err) {
+               pr_warn_ratelimited("overlayfs: failed to copy up on encode (%pd2, err=%i)\n",
+                                   dentry, err);
+       }
+
+       return err;
+}
+
+/*
+ * Before encoding a non-upper directory file handle from real layer N, we need
+ * to check if it will be possible to reconnect an overlay dentry from the real
+ * lower decoded dentry. This is done by following the overlay ancestry up to a
+ * 'layer N connected' ancestor and verifying that all parents along the way are
+ * 'layer N connectable'. If an ancestor that is NOT 'layer N connectable' is
+ * found, we need to copy up an ancestor, which is 'layer N connectable', thus
+ * making that ancestor 'layer N connected'. For example:
+ *
+ * layer 1: /a
+ * layer 2: /a/b/c
+ *
+ * The overlay dentry /a is NOT 'layer 2 connectable', because if dir /a is
+ * copied up and renamed, upper dir /a will be indexed by lower dir /a from
+ * layer 1. The dir /a from layer 2 will never be indexed, so the alrogithm (*)
+ * in ovl_lookup_real_ancestor() will not be able to lookup a connected overlay
+ * dentry from the connected lower dentry /a/b/c.
+ *
+ * To avoid this problem on decode time, we need to copy up an ancestor of
+ * /a/b/c, which is 'layer 2 connectable', on encode time. That ancestor is
+ * /a/b. After copy up (and index) of /a/b, it will become 'layer 2 connected'
+ * and when the time comes to decode the file handle from lower dentry /a/b/c,
+ * ovl_lookup_real_ancestor() will find the indexed ancestor /a/b and decoding
+ * a connected overlay dentry will be accomplished.
+ *
+ * (*) the alrogithm in ovl_lookup_real_ancestor() can be improved to lookup an
+ * entry /a in the lower layers above layer N and find the indexed dir /a from
+ * layer 1. If that improvement is made, then the check for 'layer N connected'
+ * will need to verify there are no redirects in lower layers above N. In the
+ * example above, /a will be 'layer 2 connectable'. However, if layer 2 dir /a
+ * is a target of a layer 1 redirect, then /a will NOT be 'layer 2 connectable':
+ *
+ * layer 1: /A (redirect = /a)
+ * layer 2: /a/b/c
+ */
+static int ovl_dentry_connectable_layer(struct dentry *dentry)
+{
+       struct ovl_entry *oe = OVL_E(dentry);
+
Quoted 9 lines

fs/overlayfs/export.c line 88

Quoted 6 lines
fs/overlayfs/export.c +6 -0
+       /* We can get overlay root from root of any layer */
+       if (dentry == dentry->d_sb->s_root)
+               return oe->numlower;
+
+       /* We cannot get upper/overlay path from non-indexed lower dentry */
+       if (ovl_dentry_upper(dentry) &&

Code is contradicting comment. I guess code is wrong?

This is patch v1, but already posted patch v2 with a bug fix.
patch v2 has a comment above this function:
/* Return 0 for upper file handle, > 0 for lower file handle or < 0 on error. */

N-connectable means you can get from layer <= N to overlay path. Returning 0 here mean 0-connected, meaning only upper file handle can be decoded.

What do you find contradicting in code/comment?

Quoted 11 lines

fs/overlayfs/export.c line 99

Quoted 11 lines
fs/overlayfs/export.c +11 -0
+           !ovl_test_flag(OVL_INDEX, d_inode(dentry)))
+               return 0;
+
+       /* Pure upper cannot be ancestor of non pure upper */
+       if (WARN_ON(!oe->numlower))
+               return 0;
+
+       /* We can get upper/overlay path from indexed/lower dentry */
+       return oe->lowerstack[0].layer->idx;
+}
+

Thanks,
Amir.

maintainer
#4 lore raw

Re: [RFC][PATCH] ovl: check lower ancestry on encode of lower dir file handle

Quoted 18 lines · Amir Goldstein
Quoted 15 lines · Miklos Szeredi

fs/overlayfs/export.c line 88

Quoted 10 lines · Amir Goldstein
fs/overlayfs/export.c +10 -0
+static int ovl_dentry_connectable_layer(struct dentry *dentry)
+{
+       struct ovl_entry *oe = OVL_E(dentry);
+
+       /* We can get overlay root from root of any layer */
+       if (dentry == dentry->d_sb->s_root)
+               return oe->numlower;
+
+       /* We cannot get upper/overlay path from non-indexed lower dentry */
+       if (ovl_dentry_upper(dentry) &&

Code is contradicting comment. I guess code is wrong?

Quoted 1 line

This is patch v1, but already posted patch v2 with a bug fix.

I was actually reviewing the git commit (which should be v2), but apparently found the wrong mail to reply to.

Quoted 8 lines

patch v2 has a comment above this function:
/* Return 0 for upper file handle, > 0 for lower file handle or < 0 on error. */

N-connectable means you can get from layer <= N to overlay path. Returning 0 here mean 0-connected, meaning only upper file handle can be decoded.

What do you find contradicting in code/comment?

The comment says "non-indexed lower dentry", the code says "non-indexed upper dentry".

But I think I see what you meant: "non-indexed merge dir", right?

Quoted 5 lines
Quoted 5 lines

fs/overlayfs/export.c line 92

Quoted 5 lines
fs/overlayfs/export.c +4 -0
+           !ovl_test_flag(OVL_INDEX, d_inode(dentry)))
+               return 0;
+
+       /* Pure upper cannot be ancestor of non pure upper */

Not true. We can have a redirected dir inside a non-merge dir (but we don't call that pure, and it's not purity you are testing here, but non-mergeness).

What cannot happen is that a lower dentry has a non-merge parent.

Quoted 2 lines
Quoted 2 lines

fs/overlayfs/export.c line 94

Quoted 2 lines
fs/overlayfs/export.c +2 -0
+       if (WARN_ON(!oe->numlower))
+               return 0;

But we've already returned zero for the non-merge upper case, without any warning. So in this form, the warning makes no sense (probably should just be removed).

Other than this, I think the code is fine, only the comments are confusing.

Thanks,
Miklos

author maintainer
#5 lore raw

Re: [RFC][PATCH] ovl: check lower ancestry on encode of lower dir file handle

Quoted 31 lines · Miklos Szeredi
Quoted 18 lines · Amir Goldstein
Quoted 15 lines · Miklos Szeredi

fs/overlayfs/export.c line 88

Quoted 10 lines · Amir Goldstein
fs/overlayfs/export.c +10 -0
+static int ovl_dentry_connectable_layer(struct dentry *dentry)
+{
+       struct ovl_entry *oe = OVL_E(dentry);
+
+       /* We can get overlay root from root of any layer */
+       if (dentry == dentry->d_sb->s_root)
+               return oe->numlower;
+
+       /* We cannot get upper/overlay path from non-indexed lower dentry */
+       if (ovl_dentry_upper(dentry) &&

Code is contradicting comment. I guess code is wrong?

Quoted 1 line

This is patch v1, but already posted patch v2 with a bug fix.

I was actually reviewing the git commit (which should be v2), but apparently found the wrong mail to reply to.

Quoted 7 lines

patch v2 has a comment above this function:
/* Return 0 for upper file handle, > 0 for lower file handle or < 0 on error. */

N-connectable means you can get from layer <= N to overlay path. Returning 0 here mean 0-connected, meaning only upper file handle can be decoded.

Quoted 6 lines
Quoted 1 line

What do you find contradicting in code/comment?

The comment says "non-indexed lower dentry", the code says "non-indexed upper dentry".

But I think I see what you meant: "non-indexed merge dir", right?

Correct.
Actually, maybe comment should have said:
"We cannot get upper/overlay path from non-indexed lower file handle" because this function is checking the future implications of encoding a lower or upper file handle.
But its hard enough to understand it now, so changing comment to "non-indexed merge dir" is fine by me.

Quoted 7 lines
Quoted 6 lines
Quoted 6 lines

fs/overlayfs/export.c line 92

Quoted 6 lines
fs/overlayfs/export.c +4 -0
+           !ovl_test_flag(OVL_INDEX, d_inode(dentry)))
+               return 0;
+
+       /* Pure upper cannot be ancestor of non pure upper */
Quoted 5 lines

Not true. We can have a redirected dir inside a non-merge dir (but we don't call that pure, and it's not purity you are testing here, but non-mergeness).

What cannot happen is that a lower dentry has a non-merge parent.

Yeh, I guess comment should have said "pure non-upper".

Quoted 8 lines
Quoted 3 lines
Quoted 3 lines

fs/overlayfs/export.c line 94

Quoted 3 lines
fs/overlayfs/export.c +2 -0
+       if (WARN_ON(!oe->numlower))
+               return 0;

But we've already returned zero for the non-merge upper case, without any warning. So in this form, the warning makes no sense (probably should just be removed).

I agree.

Quoted 2 lines

Other than this, I think the code is fine, only the comments are confusing.

You should have seen the earlier drafts... ;-)
Trying to explain the situation was the hard part of this patch.

I assume you will be making the modifications you suggested on commit.

Thanks,
Amir.

maintainer
#6 lore raw

Re: [RFC][PATCH] ovl: check lower ancestry on encode of lower dir file handle

Quoted 1 line · Amir Goldstein

I assume you will be making the modifications you suggested on commit.

Sure. Pushed the three fixes to overlayfs-next.

Thanks,
Miklos

author maintainer
#7 lore raw

Re: [RFC][PATCH] ovl: check lower ancestry on encode of lower dir file handle

Quoted 5 lines · Miklos Szeredi
Quoted 1 line · Amir Goldstein

I assume you will be making the modifications you suggested on commit.

Sure. Pushed the three fixes to overlayfs-next.

Tested.

Rebased and pushed optimization patches to ovl-nfs-export.

Thanks,
Amir.

author maintainer
#8 lore raw

PATCH 1/4 ovl: disambiguate ovl_encode_fh()

In reply to Amir Goldstein

Rename ovl_encode_fh() to ovl_encode_real_fh() to differentiate from the exportfs function ovl_encode_inode_fh() and change the latter to ovl_encode_fh() to match the exportfs method name.

Rename ovl_decode_fh() to ovl_decode_real_fh() for consistency.

---
 fs/overlayfs/copy_up.c   |  6 +++---
 fs/overlayfs/export.c    | 12 ++++++------
 fs/overlayfs/namei.c     | 10 +++++-----
 fs/overlayfs/overlayfs.h |  4 ++--
 4 files changed, 16 insertions(+), 16 deletions(-)
fs/overlayfs/copy_up.c +3 -3
index d855f508fa20..8bede0742619 100644
@@ -232,7 +232,7 @@ int ovl_set_attr(struct dentry *upperdentry, struct kstat *stat)
 	return err;
 }
 
-struct ovl_fh *ovl_encode_fh(struct dentry *real, bool is_upper)
+struct ovl_fh *ovl_encode_real_fh(struct dentry *real, bool is_upper)
 {
 	struct ovl_fh *fh;
 	int fh_type, fh_len, dwords;
@@ -300,7 +300,7 @@ int ovl_set_origin(struct dentry *dentry, struct dentry *lower,
 	 * up and a pure upper inode.
 	 */
 	if (ovl_can_decode_fh(lower->d_sb)) {
-		fh = ovl_encode_fh(lower, false);
+		fh = ovl_encode_real_fh(lower, false);
 		if (IS_ERR(fh))
 			return PTR_ERR(fh);
 	}
@@ -321,7 +321,7 @@ static int ovl_set_upper_fh(struct dentry *upper, struct dentry *index)
 	const struct ovl_fh *fh;
 	int err;
 
-	fh = ovl_encode_fh(upper, true);
+	fh = ovl_encode_real_fh(upper, true);
 	if (IS_ERR(fh))
 		return PTR_ERR(fh);
 
fs/overlayfs/export.c +6 -6
index c5dcb08c3a77..031cbe060e1b 100644
@@ -225,8 +225,8 @@ static int ovl_d_to_fh(struct dentry *dentry, char *buf, int buflen)
 		goto fail;
 
 	/* Encode an upper or lower file handle */
-	fh = ovl_encode_fh(err ? ovl_dentry_lower(dentry) :
-				 ovl_dentry_upper(dentry), !err);
+	fh = ovl_encode_real_fh(err ? ovl_dentry_lower(dentry) :
+				      ovl_dentry_upper(dentry), !err);
 	err = PTR_ERR(fh);
 	if (IS_ERR(fh))
 		goto fail;
@@ -264,8 +264,8 @@ static int ovl_dentry_to_fh(struct dentry *dentry, u32 *fid, int *max_len)
 	return OVL_FILEID;
 }
 
-static int ovl_encode_inode_fh(struct inode *inode, u32 *fid, int *max_len,
-			       struct inode *parent)
+static int ovl_encode_fh(struct inode *inode, u32 *fid, int *max_len,
+			 struct inode *parent)
 {
 	struct dentry *dentry;
 	int type;
@@ -682,7 +682,7 @@ static struct dentry *ovl_upper_fh_to_d(struct super_block *sb,
 	if (!ofs->upper_mnt)
 		return ERR_PTR(-EACCES);
 
-	upper = ovl_decode_fh(fh, ofs->upper_mnt);
+	upper = ovl_decode_real_fh(fh, ofs->upper_mnt);
 	if (IS_ERR_OR_NULL(upper))
 		return upper;
 
@@ -826,7 +826,7 @@ static struct dentry *ovl_get_parent(struct dentry *dentry)
 }
 
 const struct export_operations ovl_export_operations = {
-	.encode_fh	= ovl_encode_inode_fh,
+	.encode_fh	= ovl_encode_fh,
 	.fh_to_dentry	= ovl_fh_to_dentry,
 	.fh_to_parent	= ovl_fh_to_parent,
 	.get_name	= ovl_get_name,
fs/overlayfs/namei.c +5 -5
index de3e6da1d5a5..287938911abe 100644
@@ -171,7 +171,7 @@ static struct ovl_fh *ovl_get_fh(struct dentry *dentry, const char *name)
 	goto out;
 }
 
-struct dentry *ovl_decode_fh(struct ovl_fh *fh, struct vfsmount *mnt)
+struct dentry *ovl_decode_real_fh(struct ovl_fh *fh, struct vfsmount *mnt)
 {
 	struct dentry *real;
 	int bytes;
@@ -317,7 +317,7 @@ int ovl_check_origin_fh(struct ovl_fs *ofs, struct ovl_fh *fh,
 	int i;
 
 	for (i = 0; i < ofs->numlower; i++) {
-		origin = ovl_decode_fh(fh, ofs->lower_layers[i].mnt);
+		origin = ovl_decode_real_fh(fh, ofs->lower_layers[i].mnt);
 		if (origin)
 			break;
 	}
@@ -415,7 +415,7 @@ int ovl_verify_set_fh(struct dentry *dentry, const char *name,
 	struct ovl_fh *fh;
 	int err;
 
-	fh = ovl_encode_fh(real, is_upper);
+	fh = ovl_encode_real_fh(real, is_upper);
 	err = PTR_ERR(fh);
 	if (IS_ERR(fh))
 		goto fail;
@@ -451,7 +451,7 @@ struct dentry *ovl_index_upper(struct ovl_fs *ofs, struct dentry *index)
 	if (IS_ERR_OR_NULL(fh))
 		return ERR_CAST(fh);
 
-	upper = ovl_decode_fh(fh, ofs->upper_mnt);
+	upper = ovl_decode_real_fh(fh, ofs->upper_mnt);
 	kfree(fh);
 
 	if (IS_ERR_OR_NULL(upper))
@@ -619,7 +619,7 @@ int ovl_get_index_name(struct dentry *origin, struct qstr *name)
 	struct ovl_fh *fh;
 	int err;
 
-	fh = ovl_encode_fh(origin, false);
+	fh = ovl_encode_real_fh(origin, false);
 	if (IS_ERR(fh))
 		return PTR_ERR(fh);
 
fs/overlayfs/overlayfs.h +2 -2
index 225ff1171147..dd6c10e5a7db 100644
@@ -266,7 +266,7 @@ static inline bool ovl_is_impuredir(struct dentry *dentry)
 
 /* namei.c */
 int ovl_check_fh_len(struct ovl_fh *fh, int fh_len);
-struct dentry *ovl_decode_fh(struct ovl_fh *fh, struct vfsmount *mnt);
+struct dentry *ovl_decode_real_fh(struct ovl_fh *fh, struct vfsmount *mnt);
 int ovl_check_origin_fh(struct ovl_fs *ofs, struct ovl_fh *fh,
 			struct dentry *upperdentry, struct ovl_path **stackp);
 int ovl_verify_set_fh(struct dentry *dentry, const char *name,
@@ -361,7 +361,7 @@ int ovl_copy_up(struct dentry *dentry);
 int ovl_copy_up_flags(struct dentry *dentry, int flags);
 int ovl_copy_xattr(struct dentry *old, struct dentry *new);
 int ovl_set_attr(struct dentry *upper, struct kstat *stat);
-struct ovl_fh *ovl_encode_fh(struct dentry *real, bool is_upper);
+struct ovl_fh *ovl_encode_real_fh(struct dentry *real, bool is_upper);
 int ovl_set_origin(struct dentry *dentry, struct dentry *lower,
 		   struct dentry *upper);
 
Signature · 1 line
2.7.4
author maintainer
#9 lore raw

PATCH 2/4 fs/namei.c: factor out helper full_name_long_hash()

In reply to Amir Goldstein

This is a flavor of full_name_hash() which does not truncate the long hash value to 32-bit in case long is 64-bit.

A helper __hash_64() is introduced to multiply with GOLDEN_RATIO_64, just as the the helper __hash_32() multiples with GOLDEN_RATIO_32. This makes the 32 and 64 bit variants of fold_long_hash() look similar.

---
 fs/namei.c                 | 41 ++++++++++++++++++++++++++++++-----------
 include/linux/hash.h       | 10 +++++++++-
 include/linux/stringhash.h |  6 +++++-
 3 files changed, 44 insertions(+), 13 deletions(-)
fs/namei.c +30 -11
index 921ae32dbc80..afe2a8af9ce4 100644
@@ -1804,7 +1804,7 @@ static int walk_component(struct nameidata *nd, int flags)
 
 #ifdef HASH_MIX
 
-/* Architecture provides HASH_MIX and fold_hash() in <asm/hash.h> */
+/* Architecture provides HASH_MIX and fold_long_hash() in <asm/hash.h> */
 
 #elif defined(CONFIG_64BIT)
 /*
@@ -1843,15 +1843,13 @@ static int walk_component(struct nameidata *nd, int flags)
 	y *= 9			)
 
 /*
- * Fold two longs into one 32-bit hash value.  This must be fast, but
+ * Fold two longs into one long hash value.  This must be fast, but
  * latency isn't quite as critical, as there is a fair bit of additional
  * work done before the hash value is used.
  */
-static inline unsigned int fold_hash(unsigned long x, unsigned long y)
+static inline unsigned long fold_long_hash(unsigned long x, unsigned long y)
 {
-	y ^= x * GOLDEN_RATIO_64;
-	y *= GOLDEN_RATIO_64;
-	return y >> 32;
+	return __hash_64(y ^ __hash_64(x));
 }
 
 #else	/* 32-bit case */
@@ -1872,7 +1870,7 @@ static inline unsigned int fold_hash(unsigned long x, unsigned long y)
 	x += y,	y = rol32(y,20),\
 	y *= 9			)
 
-static inline unsigned int fold_hash(unsigned long x, unsigned long y)
+static inline unsigned long fold_long_hash(unsigned long x, unsigned long y)
 {
 	/* Use arch-optimized multiply if one exists */
 	return __hash_32(y ^ __hash_32(x));
@@ -1880,6 +1878,11 @@ static inline unsigned int fold_hash(unsigned long x, unsigned long y)
 
 #endif
 
+static inline unsigned int fold_hash(unsigned long x, unsigned long y)
+{
+	return fold_long_hash(x, y) >> (BITS_PER_LONG - 32);
+}
+
 /*
  * Return the hash of a string of known length.  This is carfully
  * designed to match hash_name(), which is the more critical function.
@@ -1887,7 +1890,8 @@ static inline unsigned int fold_hash(unsigned long x, unsigned long y)
  * payload bytes, to match the way that hash_name() iterates until it
  * finds the delimiter after the name.
  */
-unsigned int full_name_hash(const void *salt, const char *name, unsigned int len)
+unsigned long full_name_long_hash(const void *salt, const char *name,
+				  unsigned int len)
 {
 	unsigned long a, x = 0, y = (unsigned long)salt;
 
@@ -1903,7 +1907,14 @@ unsigned int full_name_hash(const void *salt, const char *name, unsigned int len
 	}
 	x ^= a & bytemask_from_count(len);
 done:
-	return fold_hash(x, y);
+	return fold_long_hash(x, y);
+}
+EXPORT_SYMBOL(full_name_long_hash);
+
+unsigned int full_name_hash(const void *salt, const char *name,
+			    unsigned int len)
+{
+	return full_name_long_hash(salt, name, len) >> (BITS_PER_LONG - 32);
 }
 EXPORT_SYMBOL(full_name_hash);
 
@@ -1964,12 +1975,20 @@ static inline u64 hash_name(const void *salt, const char *name)
 #else	/* !CONFIG_DCACHE_WORD_ACCESS: Slow, byte-at-a-time version */
 
 /* Return the hash of a string of known length */
-unsigned int full_name_hash(const void *salt, const char *name, unsigned int len)
+unsigned long full_name_long_hash(const void *salt, const char *name,
+				  unsigned int len)
 {
 	unsigned long hash = init_name_hash(salt);
 	while (len--)
 		hash = partial_name_hash((unsigned char)*name++, hash);
-	return end_name_hash(hash);
+	return hash;
+}
+EXPORT_SYMBOL(full_name_long_hash);
+
+unsigned int full_name_hash(const void *salt, const char *name,
+			    unsigned int len)
+{
+	return end_name_hash(full_name_long_hash(salt, name, len));
 }
 EXPORT_SYMBOL(full_name_hash);
 
include/linux/hash.h +9 -1
index ad6fa21d977b..fb2324f20c22 100644
@@ -71,6 +71,14 @@ static inline u32 hash_32_generic(u32 val, unsigned int bits)
 	return __hash_32(val) >> (32 - bits);
 }
 
+#ifndef HAVE_ARCH__HASH_64
+#define __hash_64 __hash_64_generic
+#endif
+static inline u64 __hash_64_generic(u64 val)
+{
+	return val * GOLDEN_RATIO_64;
+}
+
 #ifndef HAVE_ARCH_HASH_64
 #define hash_64 hash_64_generic
 #endif
@@ -78,7 +86,7 @@ static __always_inline u32 hash_64_generic(u64 val, unsigned int bits)
 {
 #if BITS_PER_LONG == 64
 	/* 64x64-bit multiply is efficient on all 64-bit processors */
-	return val * GOLDEN_RATIO_64 >> (64 - bits);
+	return __hash_64(val) >> (64 - bits);
 #else
 	/* Hash 64 bits using only 32x32-bit multiply. */
 	return hash_32((u32)val ^ __hash_32(val >> 32), bits);
include/linux/stringhash.h +5 -1
index e8f0f852968f..80bdf4bd9c8b 100644
@@ -63,7 +63,11 @@ static inline unsigned long end_name_hash(unsigned long hash)
  *
  * If not set, this falls back to a wrapper around the preceding.
  */
-extern unsigned int __pure full_name_hash(const void *salt, const char *, unsigned int);
+extern unsigned int __pure full_name_hash(const void *salt, const char *name,
+					  unsigned int len);
+extern unsigned long __pure full_name_long_hash(const void *salt,
+						const char *name,
+						unsigned int len);
 
 /*
  * A hash_len is a u64 with the hash of a string in the low
Signature · 1 line
2.7.4
author maintainer
#10 lore raw

PATCH 3/4 ovl: hash inodes by lower file handle for NFS export

In reply to Amir Goldstein

An overlay file handle contains a real underlying filesystem file handle and decoding an overlay file handle typically starts by decoding the real file handle.

Decoding a real directory file handle can be expensive, and it could be avoided in some cases by looking in the overlay inode cache before decoding a lower overlay file handle.

In order to be able to do that, we store a copy of the lower file handle in overlay inode i_private field and hash the overlay inode by the value of lower file handle instead of by the lower inode pointer.

A helper ovl_lookup_inode_fh() is introduced to lookup overlay inode by lower file handle. A followup patch will use this helper to optimize overlay lower file handle decode for the hot inode cache case.

---
 fs/overlayfs/inode.c     | 80 +++++++++++++++++++++++++++++++++++++++++++++---
 fs/overlayfs/namei.c     |  2 +-
 fs/overlayfs/overlayfs.h |  9 ++++++
 fs/overlayfs/super.c     |  2 ++
 4 files changed, 87 insertions(+), 6 deletions(-)
fs/overlayfs/inode.c +75 -5
index b6b44cf9ec26..5fef29e2f80f 100644
@@ -651,12 +651,65 @@ static bool ovl_verify_inode(struct inode *inode, struct dentry *lowerdentry,
 	return true;
 }
 
+/*
+ * Overlay inodes are hashed by lower file handle for NFS export, so decode can
+ * lookup inode cache before doing index lookup and decoding real file handles.
+ * For pure upper or non-indexed upper or without NFS export, we hash by real
+ * inode pointer as before NFS export. i_private holds a copy of lower file
+ * handle or the real inode pointer respectively.
+ */
+static int ovl_inode_test_fh(struct inode *inode, void *data)
+{
+	return ovl_test_flag(OVL_I_PRIVATE_FH, inode) &&
+	       ovl_fs_equal(inode->i_private, data);
+}
+
+/* Compute hash from real fs uuid and real fs file handle */
+static unsigned long ovl_fh_hash(struct ovl_fh *fh)
+{
+	/*
+	 * Mixing the uuid with the real file handle is needed for an
+	 * overlay configuration of many lower layers on different fs.
+	 * Other ovl_fh header values are not likely to add random bits.
+	 */
+	return full_name_long_hash(NULL, (const char *)&fh->uuid,
+				   fh->len - offsetof(struct ovl_fh, uuid));
+}
+
+static struct ovl_fh *ovl_real_fh_hash(struct dentry *real, bool is_upper,
+				       unsigned long *pkey)
+{
+	struct ovl_fh *fh = ovl_encode_real_fh(real, is_upper);
+
+	if (!IS_ERR(fh))
+		*pkey = ovl_fh_hash(fh);
+
+	return fh;
+}
+
+/* Lookup overlay inode by real inode file handle */
+struct inode *ovl_lookup_inode_fh(struct super_block *sb, struct ovl_fh *fh)
+{
+	return ilookup5(sb, ovl_fh_hash(fh), ovl_inode_test_fh, fh);
+}
+
+/* Lookup overlay inode by real upper inode or by lower inode file handle */
 struct inode *ovl_lookup_inode(struct super_block *sb, struct dentry *real,
 			       bool is_upper)
 {
 	struct inode *inode, *key = d_inode(real);
+	struct ovl_fh *fh;
 
-	inode = ilookup5(sb, (unsigned long) key, ovl_inode_test, key);
+	if (is_upper) {
+		inode = ilookup5(sb, (unsigned long) key, ovl_inode_test, key);
+	} else {
+		fh = ovl_encode_real_fh(real, false);
+		if (IS_ERR(fh))
+			return ERR_CAST(fh);
+
+		inode = ovl_lookup_inode_fh(sb, fh);
+		kfree(fh);
+	}
 	if (!inode)
 		return NULL;
 
@@ -709,23 +762,35 @@ struct inode *ovl_get_inode(struct super_block *sb, struct dentry *upperdentry,
 	struct inode *realinode = upperdentry ? d_inode(upperdentry) : NULL;
 	struct inode *inode;
 	bool bylower = ovl_hash_bylower(sb, upperdentry, lowerdentry, index);
+	struct ovl_fh *fh = NULL;
+	unsigned long key;
 	bool is_dir;
 
 	if (!realinode)
 		realinode = d_inode(lowerdentry);
 
+	/* Hash non-upper and indexed by origin fh for NFS export */
+	if (sb->s_export_op && bylower) {
+		fh = ovl_real_fh_hash(lowerdentry, false, &key);
+		if (IS_ERR(fh))
+			return ERR_CAST(fh);
+	} else if (bylower) {
+		key = (unsigned long) d_inode(lowerdentry);
+	} else if (upperdentry) {
+		key = (unsigned long) d_inode(upperdentry);
+	}
+
 	/*
 	 * Copy up origin (lower) may exist for non-indexed upper, but we must
 	 * not use lower as hash key if this is a broken hardlink.
 	 */
 	is_dir = S_ISDIR(realinode->i_mode);
 	if (upperdentry || bylower) {
-		struct inode *key = d_inode(bylower ? lowerdentry :
-						      upperdentry);
 		unsigned int nlink = is_dir ? 1 : realinode->i_nlink;
 
-		inode = iget5_locked(sb, (unsigned long) key,
-				     ovl_inode_test, ovl_inode_set, key);
+		inode = iget5_locked(sb, key, fh ? ovl_inode_test_fh :
+						   ovl_inode_test,
+				     ovl_inode_set, fh ?: (void *)key);
 		if (!inode)
 			goto out_nomem;
 		if (!(inode->i_state & I_NEW)) {
@@ -742,6 +807,10 @@ struct inode *ovl_get_inode(struct super_block *sb, struct dentry *upperdentry,
 
 			dput(upperdentry);
 			goto out;
+		} else if (fh) {
+			/* i_private keeps the reference to fh */
+			ovl_set_flag(OVL_I_PRIVATE_FH, inode);
+			fh = NULL;
 		}
 
 		/* Recalculate nlink for non-dir due to indexing */
@@ -771,6 +840,7 @@ struct inode *ovl_get_inode(struct super_block *sb, struct dentry *upperdentry,
 	if (inode->i_state & I_NEW)
 		unlock_new_inode(inode);
 out:
+	kfree(fh);
 	return inode;
 
 out_nomem:
fs/overlayfs/namei.c +1 -1
index 287938911abe..74ccbe0813cd 100644
@@ -393,7 +393,7 @@ static int ovl_verify_fh(struct dentry *dentry, const char *name,
 	if (IS_ERR(ofh))
 		return PTR_ERR(ofh);
 
-	if (fh->len != ofh->len || memcmp(fh, ofh, fh->len))
+	if (!ovl_fs_equal(fh, ofh))
 		err = -ESTALE;
 
 	kfree(ofh);
fs/overlayfs/overlayfs.h +9 -0
index dd6c10e5a7db..b94db3f6f4ae 100644
@@ -35,6 +35,8 @@ enum ovl_inode_flag {
 	/* Non-merge dir that may contain whiteout entries */
 	OVL_WHITEOUTS,
 	OVL_INDEX,
+	/* inode->i_priavte is a file handle copy */
+	OVL_I_PRIVATE_FH,
 };
 
 enum ovl_entry_flag {
@@ -83,6 +85,12 @@ struct ovl_fh {
 	u8 fid[0];	/* file identifier */
 } __packed;
 
+static inline bool ovl_fs_equal(const struct ovl_fh *fh1,
+				const struct ovl_fh *fh2)
+{
+	return fh1->len == fh2->len && !memcmp(fh1, fh2, fh1->len);
+}
+
 static inline int ovl_do_rmdir(struct inode *dir, struct dentry *dentry)
 {
 	int err = vfs_rmdir(dir, dentry);
@@ -326,6 +334,7 @@ int ovl_update_time(struct inode *inode, struct timespec *ts, int flags);
 bool ovl_is_private_xattr(const char *name);
 
 struct inode *ovl_new_inode(struct super_block *sb, umode_t mode, dev_t rdev);
+struct inode *ovl_lookup_inode_fh(struct super_block *sb, struct ovl_fh *fh);
 struct inode *ovl_lookup_inode(struct super_block *sb, struct dentry *real,
 			       bool is_upper);
 struct inode *ovl_get_inode(struct super_block *sb, struct dentry *upperdentry,
fs/overlayfs/super.c +2 -0
index 7c24619ae7fc..d17dffc611cc 100644
@@ -220,6 +220,8 @@ static void ovl_destroy_inode(struct inode *inode)
 	kfree(oi->redirect);
 	ovl_dir_cache_free(inode);
 	mutex_destroy(&oi->lock);
+	if (ovl_test_flag(OVL_I_PRIVATE_FH, inode))
+		kfree(inode->i_private);
 
 	call_rcu(&inode->i_rcu, ovl_i_callback);
 }
Signature · 1 line
2.7.4
author maintainer
#11 lore raw

PATCH 4/4 ovl: lookup in inode cache when decoding lower file handle

In reply to Amir Goldstein

When decoding a lower file handle, we need to check if lower file was copied up and indexed and if it has a whiteout index, we need to check if this is an unlinked but open non-dir before returning -ESTALE.

To find out if this is an unlinked but open non-dir we need to lookup an overlay inode in inode cache with an alias.

Before this change, the overlay inode was looked up by lower inode and that required decoding the lower file handle before looking in inode cache. If the lower inode turned out to be a directory, we may have paid an expensive cost to reconnect that lower directory for nothing.

After this change, we start by looking up an overlay inode in inode cache by lower file handle. If we don't find an overlay inode and dentry alias, then we only need to decode the lower file handle in case the lower file is not indexed or if the index is a non-dir.

---
 fs/overlayfs/export.c | 39 ++++++++++++++++-----------------------
 1 file changed, 16 insertions(+), 23 deletions(-)
fs/overlayfs/export.c +16 -23
index 031cbe060e1b..f8dce6976248 100644
@@ -700,22 +700,26 @@ static struct dentry *ovl_lower_fh_to_d(struct super_block *sb,
 	struct ovl_path *stack = &origin;
 	struct dentry *dentry = NULL;
 	struct dentry *index = NULL;
-	struct inode *inode = NULL;
-	bool is_deleted = false;
+	struct inode *inode;
 	int err;
 
-	/* First lookup indexed upper by fh */
+	/* First lookup overlay inode in inode cache by fh */
+	inode = ovl_lookup_inode_fh(sb, fh);
+	if (IS_ERR(inode))
+		return ERR_CAST(inode);
+	if (inode) {
+		dentry = d_find_any_alias(inode);
+		iput(inode);
+		if (dentry)
+			return dentry;
+	}
+
+	/* Then lookup indexed upper by fh */
 	if (ofs->indexdir) {
 		index = ovl_get_index_fh(ofs, fh);
 		err = PTR_ERR(index);
-		if (IS_ERR(index)) {
-			if (err != -ESTALE)
-				return ERR_PTR(err);
-
-			/* Found a whiteout index - treat as deleted inode */
-			is_deleted = true;
-			index = NULL;
-		}
+		if (IS_ERR(index))
+			return index;
 	}
 
 	/* Then try to get upper dir by index */
@@ -731,7 +735,7 @@ static struct dentry *ovl_lower_fh_to_d(struct super_block *sb,
 		goto out;
 	}
 
-	/* Then lookup origin by fh */
+	/* Then lookup indexed non-dir origin or non-upper by fh */
 	err = ovl_check_origin_fh(ofs, fh, NULL, &stack);
 	if (err) {
 		goto out_err;
@@ -739,16 +743,6 @@ static struct dentry *ovl_lower_fh_to_d(struct super_block *sb,
 		err = ovl_verify_origin(index, origin.dentry, false);
 		if (err)
 			goto out_err;
-	} else if (is_deleted) {
-		/* Lookup deleted non-dir by origin inode */
-		if (!d_is_dir(origin.dentry))
-			inode = ovl_lookup_inode(sb, origin.dentry, false);
-		err = -ESTALE;
-		if (!inode || atomic_read(&inode->i_count) == 1)
-			goto out_err;
-
-		/* Deleted but still open? */
-		index = dget(ovl_i_dentry_upper(inode));
 	}
 
 	dentry = ovl_get_dentry(sb, NULL, &origin, index);
@@ -756,7 +750,6 @@ static struct dentry *ovl_lower_fh_to_d(struct super_block *sb,
 out:
 	dput(origin.dentry);
 	dput(index);
-	iput(inode);
 	return dentry;
 
 out_err:
Signature · 1 line
2.7.4