From mboxrd@z Thu Jan  1 00:00:00 1970
From: Al Viro <viro@ZenIV.linux.org.uk>
Subject: Re: undefined behaviour in fs/jbd*/revoke.c:hash()
Date: Thu, 16 Jun 2011 01:29:54 +0100
Message-ID: <20110616002954.GK11521@ZenIV.linux.org.uk>
References: <4DF938D9.32713.4300B4D5@pageexec.freemail.hu>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Cc: linux-fsdevel@vger.kernel.org, David Miller <davem@davemloft.net>
To: pageexec@freemail.hu
Return-path: <linux-fsdevel-owner@vger.kernel.org>
Received: from zeniv.linux.org.uk ([195.92.253.2]:33050 "EHLO
	ZenIV.linux.org.uk" rhost-flags-OK-OK-OK-OK) by vger.kernel.org
	with ESMTP id S1752590Ab1FPA34 (ORCPT
	<rfc822;linux-fsdevel@vger.kernel.org>);
	Wed, 15 Jun 2011 20:29:56 -0400
Content-Disposition: inline
In-Reply-To: <4DF938D9.32713.4300B4D5@pageexec.freemail.hu>
Sender: linux-fsdevel-owner@vger.kernel.org
List-ID: <linux-fsdevel.vger.kernel.org>

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...