[PATCH] avoid negative shifts in radix-tree.c

[PATCH] avoid negative shifts in radix-tree.c

[Peter Firefly Lund]

(linux-vax@pergamentum.com only bcc'ed because it's subscribers only,
Lameter addressed because I think he touched the code last, Velikov and
Hellwig because they touched the code first.)

The current code in __max_index() will shift by a negative amount first
and only then fix the situation by ignoring the result if the shift
amount would have been negative.  This happens to work on almost any
architecture despite not being valid C.

Chapter and verse from the (draft) ISO C99 standard, "6.5.7 Bitwise
shift operators", paragraph 3:

  "The integer promotions are performed on each of the operands. The
   type of the result is that of the promoted left operand. If the
   value of the right operand is negative or is greater than or equal
   to the width of the promoted left operand, the behavior is
   undefined."

Right-shifting by a negative amount causes a "reserved operand fault" on
the VAX with some gcc versions.


Applies to 2.6.22.
Boot tested lightly on an emulated VAX.

(The function is called 7 times on booth with the values 0..6 -- I
checked that the return values were the same + that it returns ~0UL for
height==6 as was clearly the intention.)

-Peter

--- lib/radix-tree-old.c	2007-08-25 15:36:40.000000000 +0200
+++ lib/radix-tree.c	2007-08-25 15:36:51.000000000 +0200
@@ -980,12 +980,14 @@ radix_tree_node_ctor(void *node, struct 
 
 static __init unsigned long __maxindex(unsigned int height)
 {
-	unsigned int tmp = height * RADIX_TREE_MAP_SHIFT;
-	unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1;
-
-	if (tmp >= RADIX_TREE_INDEX_BITS)
-		index = ~0UL;
-	return index;
+	unsigned int	tmp   = height * RADIX_TREE_MAP_SHIFT;
+	int		shift = RADIX_TREE_INDEX_BITS - tmp;
+	unsigned long	index;
+
+	if (shift < 0)
+		return ~0UL;
+	else
+		return ~0UL >> shift;
 }
 
 static __init void radix_tree_init_maxindex(void)

Re: [LV] [PATCH] avoid negative shifts in radix-tree.c

[Jan-Benedict Glaw]

[-- Attachment #1: Type: text/plain, Size: 1219 bytes --]

On Sat, 2007-08-25 16:26:07 +0200, Peter Firefly Lund <firefly@vax64.dk> wrote:
> --- lib/radix-tree-old.c	2007-08-25 15:36:40.000000000 +0200
> +++ lib/radix-tree.c	2007-08-25 15:36:51.000000000 +0200
> @@ -980,12 +980,14 @@ radix_tree_node_ctor(void *node, struct 
>  
>  static __init unsigned long __maxindex(unsigned int height)
>  {
> -	unsigned int tmp = height * RADIX_TREE_MAP_SHIFT;
> -	unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1;
> -
> -	if (tmp >= RADIX_TREE_INDEX_BITS)
> -		index = ~0UL;
> -	return index;
> +	unsigned int	tmp   = 
> +	int shift = RADIX_TREE_INDEX_BITS - height * RADIX_TREE_MAP_SHIFT;
> +	unsigned long	index;
> +
> +	if (shift < 0)
> +		return ~0UL;
> +	else
> +		return ~0UL >> shift;
>  }
>  
>  static __init void radix_tree_init_maxindex(void)

`index' seems to be unused now?  And indention does neither follow
kernel coding style, nor this file's style. You'd also hammer out
`tmp' and put its initializer right there where it's used.

MfG, JBG

-- 
      Jan-Benedict Glaw      jbglaw@lug-owl.de              +49-172-7608481
Signature of:               Träume nicht von Dein Leben: Lebe Deinen Traum!
the second  :

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] avoid negative shifts in radix-tree.c

[Christoph Hellwig]

On Sat, Aug 25, 2007 at 04:26:07PM +0200, Peter Firefly Lund wrote:
> (linux-vax@pergamentum.com only bcc'ed because it's subscribers only,
> Lameter addressed because I think he touched the code last, Velikov and
> Hellwig because they touched the code first.)
> 
> The current code in __max_index() will shift by a negative amount first
> and only then fix the situation by ignoring the result if the shift
> amount would have been negative.  This happens to work on almost any
> architecture despite not being valid C.
> 
> Chapter and verse from the (draft) ISO C99 standard, "6.5.7 Bitwise
> shift operators", paragraph 3:
> 
>   "The integer promotions are performed on each of the operands. The
>    type of the result is that of the promoted left operand. If the
>    value of the right operand is negative or is greater than or equal
>    to the width of the promoted left operand, the behavior is
>    undefined."
> 
> Right-shifting by a negative amount causes a "reserved operand fault" on
> the VAX with some gcc versions.
> 
> 
> Applies to 2.6.22.
> Boot tested lightly on an emulated VAX.
> 
> (The function is called 7 times on booth with the values 0..6 -- I
> checked that the return values were the same + that it returns ~0UL for
> height==6 as was clearly the intention.)
> 
> -Peter
> 
> --- lib/radix-tree-old.c	2007-08-25 15:36:40.000000000 +0200
> +++ lib/radix-tree.c	2007-08-25 15:36:51.000000000 +0200
> @@ -980,12 +980,14 @@ radix_tree_node_ctor(void *node, struct 
>  
>  static __init unsigned long __maxindex(unsigned int height)
>  {
> -	unsigned int tmp = height * RADIX_TREE_MAP_SHIFT;
> -	unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1;
> -
> -	if (tmp >= RADIX_TREE_INDEX_BITS)
> -		index = ~0UL;
> -	return index;
> +	unsigned int	tmp   = height * RADIX_TREE_MAP_SHIFT;
> +	int		shift = RADIX_TREE_INDEX_BITS - tmp;
> +	unsigned long	index;
> +
> +	if (shift < 0)
> +		return ~0UL;
> +	else
> +		return ~0UL >> shift;

The conceptual change looks fine to me, but the code looks a little odd,
what about:

static __init unsigned long __maxindex(unsigned int height)
{
	unsigned int tmp = height * RADIX_TREE_MAP_SHIFT;
	int shift = RADIX_TREE_INDEX_BITS - tmp;

	if (shift < 0)
		return ~0UL;
	return ~0UL >> shift;
}

instead?

Re: [PATCH] avoid negative shifts in radix-tree.c

[Maciej W. Rozycki]

On Mon, 27 Aug 2007, Christoph Hellwig wrote:

> The conceptual change looks fine to me, but the code looks a little odd,
> what about:
> 
> static __init unsigned long __maxindex(unsigned int height)
> {
> 	unsigned int tmp = height * RADIX_TREE_MAP_SHIFT;
> 	int shift = RADIX_TREE_INDEX_BITS - tmp;
> 
> 	if (shift < 0)
> 		return ~0UL;
> 	return ~0UL >> shift;
> }
> 
> instead?

 This patch has been successfully tested on actual hardware (VAXstation 
4000/90).  If nobody objects, I'll push it to Andrew.

  Maciej

Signed-off-by: Maciej W. Rozycki <macro@linux-mips.org>

patch-vax-2.6.17-rc4-20070111-radix-maxindex-0
diff -up --recursive --new-file linux-vax-2.6.17-rc4-20070111.macro/lib/radix-tree.c linux-vax-2.6.17-rc4-20070111/lib/radix-tree.c
--- linux-vax-2.6.17-rc4-20070111.macro/lib/radix-tree.c	2006-10-31 19:05:50.000000000 +0000
+++ linux-vax-2.6.17-rc4-20070111/lib/radix-tree.c	2007-01-22 01:24:17.000000000 +0000
@@ -825,9 +825,11 @@ radix_tree_node_ctor(void *node, kmem_ca
 static __init unsigned long __maxindex(unsigned int height)
 {
 	unsigned int tmp = height * RADIX_TREE_MAP_SHIFT;
-	unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1;
+	unsigned long index;
 
-	if (tmp >= RADIX_TREE_INDEX_BITS)
+	if (tmp < RADIX_TREE_INDEX_BITS)
+		index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1;
+	else
 		index = ~0UL;
 	return index;
 }