avoid negative shifts in radix-tree.c
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, structstatic __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 )
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, structstatic __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 :
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-Peterradix-tree.c renamed from radix-tree-old.c +0
-4@@ -980,12 +980,14 @@ radix_tree_node_ctor(void *node, structstatic __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?
Quoted 13 lines · Christoph Hellwig
The conceptual change looks fine to me, but the code looks a little odd, what about:
static
__initunsigned 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
@@ -825,9 +825,11 @@ radix_tree_node_ctor(void *node, kmem_castatic __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; }