undefined behaviour in fs/jbd*/revoke.c:hash()

undefined behaviour in fs/jbd*/revoke.c:hash()

[pageexec]

hi guys,

with a clang compiled kernel while enabling -fcatch-undefined-behavior one gets
a runtime assert in find_revoke_record(), more precisely, in the inlined hash()
function.

the issue is that one of the expressions is 'hash << (hash_shift - 12)' which is
undefined (in C99 at least) when the shift count is negative and it so happens
that hash_shift is 8 because JOURNAL_REVOKE_DEFAULT_HASH is defined to be 256.

i'm not sure what the right fix would be hence this mail ;). JOURNAL_REVOKE_DEFAULT_HASH
could be increased to 4096 (or more) to avoid the negative shift or the shift
count should be fixed to become explicitly non-negative. also given the comment
above the hash() function, this construct may be used elsewhere as well, i didn't
check myself but it might be worth a look.

cheers,
 PaX Team

Re: undefined behaviour in fs/jbd*/revoke.c:hash()

[Al Viro]

On Thu, Jun 16, 2011 at 12:57:29AM +0200, pageexec@freemail.hu wrote:

> the issue is that one of the expressions is 'hash << (hash_shift - 12)' which is
> undefined (in C99 at least) when the shift count is negative and it so happens
> that hash_shift is 8 because JOURNAL_REVOKE_DEFAULT_HASH is defined to be 256.

Not just in C99; it had always been undefined and while nasal daemons had
usually been not particulary nasty here, different implementations easily
gave different results.

> i'm not sure what the right fix would be hence this mail ;). JOURNAL_REVOKE_DEFAULT_HASH
> could be increased to 4096 (or more) to avoid the negative shift or the shift
> count should be fixed to become explicitly non-negative. also given the comment
> above the hash() function, this construct may be used elsewhere as well, i didn't
> check myself but it might be worth a look.

FWIW, this expression is a copy of the thing added in 2.3.9pre8 by davem;
+/* After several hours of tedious analysis, the following hash
+ * function won.  Do not mess with it... -DaveM
+ */
+#define _hashfn(dev,block)     \
+       ((((dev)<<(bh_hash_shift - 6)) ^ ((dev)<<(bh_hash_shift - 9))) ^ \
+        (((block)<<(bh_hash_shift - 6)) ^ ((block) >> 13) ^ ((block) << (bh_hash_shift - 12))) 
+#define hash(dev,block) hash_table[(_hashfn(dev,block) & bh_hash_mask)]

There we probably never had bh_hash_shift < 12, but I really wonder about the
details of that analysis...  If we are aiming for N-bit value, we end up using
bits 13..13+N-1, 0..5 and 0..11, the last two groups shifted up.  What has
bit 12 done to deserve being ignored, to start with?

fs/buffer.c is not using that thing anymore (we use page cache to locate
buffer_heads these days); hell knows if anyone else has copied it...