Skip to contentSkip to conversation

avoid negative shifts in radix-tree.c

PATCH In review Peter Firefly Lund 4 participants 4 messages Aug 25, 2007 – Aug 29, 2007 Library code

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 avoid negative shifts in radix-tree.c

([email protected] 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

radix-tree.c renamed from radix-tree-old.c +8 -6
@@ -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)
#1 lore raw
Quoted 13 lines · Peter Firefly Lund
radix-tree.c renamed from radix-tree-old.c +1 -6
@@ -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   = 

radix-tree.c radix_tree_node_ctor(void *node, struct · line 993

Quoted 10 lines
radix-tree.c renamed from radix-tree-old.c +7 -0
+	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

Signature · 3 lines
      Jan-Benedict Glaw      [email protected]              +49-172-7608481
Signature of:               Träume nicht von Dein Leben: Lebe Deinen Traum!
the second  :
#2 lore raw
In reply to Peter Firefly Lund
Quoted 41 lines · Peter Firefly Lund

([email protected] 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.)

(quoted diff) +0 -1
-Peter
radix-tree.c renamed from radix-tree-old.c +0 -4
@@ -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)

radix-tree.c radix_tree_node_ctor(void *node, struct · line 990

Quoted 10 lines
radix-tree.c renamed from radix-tree-old.c +8 -2
-		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?

#3 lore raw
Quoted 13 lines · Christoph Hellwig

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;
}
Quoted 1 line

instead?

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

Maciej

patch-vax-2.6.17-rc4-20070111-radix-maxindex-0

lib/radix-tree.c +4 -2
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
@@ -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;
 }