[PATCH] kernfs: Fix kernfs_name_compare

[PATCH] kernfs: Fix kernfs_name_compare

[Rasmus Villemoes]

If the void pointers ns and kn->ns happen to differ by a multiple of
2^32, kernfs_name_compare returns 0, falsely reporting a match to the
caller.

If the return type was changed to long, returning ns - kn->ns would
still be wrong (see acbbe6fbb240 "kcmp: fix standard comparison bug"),
and it would also break the primary comparison of the hashes: The
expression hash - kn->hash has type unsigned int; on 64-bit, long is
perfectly capable of representing all unsigned int values, hence the
return value would always be positive if the hashes are
different. Since the latter is slightly subtle and since returning
hash - kn->hash in the first place is only ok because the hashes are
restricted to 31 bits, add a comment explaining that.

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
 fs/kernfs/dir.c | 11 +++++++++--
 1 file changed, 9 insertions(+), 2 deletions(-)

diff --git a/fs/kernfs/dir.c b/fs/kernfs/dir.c
index 1c771931bb60..64959716936d 100644
--- a/fs/kernfs/dir.c
+++ b/fs/kernfs/dir.c
@@ -201,10 +201,17 @@ static unsigned int kernfs_name_hash(const char *name, const void *ns)
 static int kernfs_name_compare(unsigned int hash, const char *name,
 			       const void *ns, const struct kernfs_node *kn)
 {
+	/*
+	 * This is ok because the hash values are restricted to [0,
+	 * 2^31-1] and because we are returning int (it would be wrong
+	 * had the return type been wider!).
+	 */
 	if (hash != kn->hash)
 		return hash - kn->hash;
-	if (ns != kn->ns)
-		return ns - kn->ns;
+	if (ns < kn->ns)
+		return -1;
+	if (ns > kn->ns)
+		return 1;
 	return strcmp(name, kn->name);
 }
 
-- 
2.0.4

Re: [PATCH] kernfs: Fix kernfs_name_compare

[Tejun Heo]

Hello,

On Thu, Dec 04, 2014 at 05:19:34PM +0100, Rasmus Villemoes wrote:
...
>  {
> +	/*
> +	 * This is ok because the hash values are restricted to [0,
> +	 * 2^31-1] and because we are returning int (it would be wrong
> +	 * had the return type been wider!).
> +	 */
>  	if (hash != kn->hash)
>  		return hash - kn->hash;

Let's just do < > comparisons here too and just note that trying to
determine ordering through subtraction is dangerous.

Thanks.

-- 
tejun

[PATCH v2] kernfs: Fix kernfs_name_compare

[Rasmus Villemoes]

Returning a difference from a comparison functions is usually wrong
(see acbbe6fbb240 "kcmp: fix standard comparison bug" for the long
story). Here there is the additional twist that if the void pointers
ns and kn->ns happen to differ by a multiple of 2^32,
kernfs_name_compare returns 0, falsely reporting a match to the
caller.

Technically 'hash - kn->hash' is ok since the hashes are restricted to
31 bits, but it's better to avoid that subtlety.

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---

Notes:
    v2: Also use explicit < > comparisons of the hashes.

 fs/kernfs/dir.c | 12 ++++++++----
 1 file changed, 8 insertions(+), 4 deletions(-)

diff --git a/fs/kernfs/dir.c b/fs/kernfs/dir.c
index 1c771931bb60..bf9e2f44c3df 100644
--- a/fs/kernfs/dir.c
+++ b/fs/kernfs/dir.c
@@ -201,10 +201,14 @@ static unsigned int kernfs_name_hash(const char *name, const void *ns)
 static int kernfs_name_compare(unsigned int hash, const char *name,
 			       const void *ns, const struct kernfs_node *kn)
 {
-	if (hash != kn->hash)
-		return hash - kn->hash;
-	if (ns != kn->ns)
-		return ns - kn->ns;
+	if (hash < kn->hash)
+		return -1;
+	if (hash > kn->hash)
+		return 1;
+	if (ns < kn->ns)
+		return -1;
+	if (ns > kn->ns)
+		return 1;
 	return strcmp(name, kn->name);
 }
 
-- 
2.1.3

Re: [PATCH v2] kernfs: Fix kernfs_name_compare

[Tejun Heo]

On Fri, Dec 05, 2014 at 11:41:33PM +0100, Rasmus Villemoes wrote:
> Returning a difference from a comparison functions is usually wrong
> (see acbbe6fbb240 "kcmp: fix standard comparison bug" for the long
> story). Here there is the additional twist that if the void pointers
> ns and kn->ns happen to differ by a multiple of 2^32,
> kernfs_name_compare returns 0, falsely reporting a match to the
> caller.
> 
> Technically 'hash - kn->hash' is ok since the hashes are restricted to
> 31 bits, but it's better to avoid that subtlety.
> 
> Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>

Acked-by: Tejun Heo <tj@kernel.org>

And this is a -stable material.  Greg, can you please pick this one
up?

Thanks.

-- 
tejun

Re: [PATCH v2] kernfs: Fix kernfs_name_compare

[Greg Kroah-Hartman]

On Mon, Jan 05, 2015 at 09:13:47AM -0500, Tejun Heo wrote:
> On Fri, Dec 05, 2014 at 11:41:33PM +0100, Rasmus Villemoes wrote:
> > Returning a difference from a comparison functions is usually wrong
> > (see acbbe6fbb240 "kcmp: fix standard comparison bug" for the long
> > story). Here there is the additional twist that if the void pointers
> > ns and kn->ns happen to differ by a multiple of 2^32,
> > kernfs_name_compare returns 0, falsely reporting a match to the
> > caller.
> > 
> > Technically 'hash - kn->hash' is ok since the hashes are restricted to
> > 31 bits, but it's better to avoid that subtlety.
> > 
> > Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
> 
> Acked-by: Tejun Heo <tj@kernel.org>
> 
> And this is a -stable material.  Greg, can you please pick this one
> up?

Will do, thanks.

greg k-h