LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
* [PATCH] avoid negative shifts in radix-tree.c
@ 2007-08-25 14:26 Peter Firefly Lund
  2007-08-26 16:01 ` [LV] " Jan-Benedict Glaw
  2007-08-27 13:28 ` Christoph Hellwig
  0 siblings, 2 replies; 4+ messages in thread
From: Peter Firefly Lund @ 2007-08-25 14:26 UTC (permalink / raw)
  To: Christoph Lameter
  Cc: Momchil Velikov, Christoph Hellwig, linux-kernel, trivial

(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)



^ permalink raw reply	[flat|nested] 4+ messages in thread

* Re: [LV] [PATCH] avoid negative shifts in radix-tree.c
  2007-08-25 14:26 [PATCH] avoid negative shifts in radix-tree.c Peter Firefly Lund
@ 2007-08-26 16:01 ` Jan-Benedict Glaw
  2007-08-27 13:28 ` Christoph Hellwig
  1 sibling, 0 replies; 4+ messages in thread
From: Jan-Benedict Glaw @ 2007-08-26 16:01 UTC (permalink / raw)
  To: Peter Firefly Lund
  Cc: Christoph Lameter, Christoph Hellwig, trivial, linux-kernel,
	Momchil Velikov

[-- 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 --]

^ permalink raw reply	[flat|nested] 4+ messages in thread

* Re: [PATCH] avoid negative shifts in radix-tree.c
  2007-08-25 14:26 [PATCH] avoid negative shifts in radix-tree.c Peter Firefly Lund
  2007-08-26 16:01 ` [LV] " Jan-Benedict Glaw
@ 2007-08-27 13:28 ` Christoph Hellwig
  2007-08-29 11:39   ` Maciej W. Rozycki
  1 sibling, 1 reply; 4+ messages in thread
From: Christoph Hellwig @ 2007-08-27 13:28 UTC (permalink / raw)
  To: Peter Firefly Lund
  Cc: Christoph Lameter, Momchil Velikov, Christoph Hellwig,
	linux-kernel, trivial

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?

^ permalink raw reply	[flat|nested] 4+ messages in thread

* Re: [PATCH] avoid negative shifts in radix-tree.c
  2007-08-27 13:28 ` Christoph Hellwig
@ 2007-08-29 11:39   ` Maciej W. Rozycki
  0 siblings, 0 replies; 4+ messages in thread
From: Maciej W. Rozycki @ 2007-08-29 11:39 UTC (permalink / raw)
  To: Christoph Hellwig
  Cc: Peter Firefly Lund, Christoph Lameter, Momchil Velikov, linux-kernel

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;
 }

^ permalink raw reply	[flat|nested] 4+ messages in thread

end of thread, other threads:[~2007-08-29 11:39 UTC | newest]

Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2007-08-25 14:26 [PATCH] avoid negative shifts in radix-tree.c Peter Firefly Lund
2007-08-26 16:01 ` [LV] " Jan-Benedict Glaw
2007-08-27 13:28 ` Christoph Hellwig
2007-08-29 11:39   ` Maciej W. Rozycki

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).