[LV] Partial success and a Linux kernel bug

[Peter Firefly Lund]

On Wed, 2007-08-22 at 12:22 +0200, Peter Firefly Lund wrote:

> This is the register values (if we can trust them *):
>            r0  3fffff25   r1  fffffffb   r3  ffffffff
> 
> so the size is 25h, which is too big.  It can only be 0 <= size <= 32.  
> I am a little bit unclear on where the source bit vector is, it can be
> either in memory or in a register for this instruction.  I'm pretty sure
> it is in a register (r3).  In that case pos is also wrong because it has
> to be <= 31 (unsigned).
> 
> No wonder I'm getting a "reserved operand" fault.

I tracked it down late last night.  It is a bug in the Linux kernel
which has been there since the radix tree code was merged in 2.5.8
(April 2002).

It tries to right shift by a negative amount in some cases, which is
undefined by the C standard (C99 final draft, section 6.5.7 "Bitwise
shift operators", paragraph 3.).  Shifts by < 0 or >= the width of the
value of to be shifted (after promotion) are undefined.

The code catches such cases two lower but by then it is, strictly
speaking, too late.  Most archs don't crash because of that, though ;)

The VAX gcc compiles the shift to a "bit vector extraction" instruction
which takes an "undefined operand fault" if the shift amount is out of
range.

The code was originally written in 2001/2002 by Momchil Velikov and
Christoph Hellwig.

http://www.cs.helsinki.fi/linux/linux-kernel/2001-51/0142.html
http://lkml.org/lkml/2002/1/5/63

Here is the original offending code:

+/* Return the maximum key, which can be store into a radix tree with
+   height HEIGHT.  */
+static inline unsigned long
+rat_index_max (unsigned int height)
+{
+	unsigned int tmp = height * RAT_MAP_SHIFT;
+	unsigned long index = (~0UL >> (RAT_INDEX_BITS - tmp - 1)) >> 1;
+	if (tmp >= RAT_INDEX_BITS)
+		index = ~0UL;
+	return index;
+}

and here is modern equivalent (in lib/radix_tree.c):

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

It was originally used in many places in the code but nowadays its
values get cached so it is only called at boot, with the values 0..6 (on
the VAX).

RADIX_TREE_MAP_SHIFT is 6.
RADIX_TREE_INDEX_BITS is 32.
so if height == 6, tmp becomes 36.
The shift becomes 32 - 36 - 1 = -5.

(Why the expression ends with '>> 1' outside the parenthesis is beyond
me, be the way.)

Returning to the EXTZV instruction, its size (r0) is 37 and the pos (r1)
is -5.  It all makes sense now.

After changing this code (I changed it to a loop that shifted one bit at
a time + had masked the shift value with 63 -- what can I say, I was
tired), the kernel boots as far as trying to get an IP address with
bootp.  After timing out, it tries to call delqa_close which isn't
implemented so it halts.

To sum up: I need to send a small patch to the kernel janitors or
Christoph Lameter who seems to be the last guy who touched the code in a
significant way plus I need to try again with a bootp daemon running.
And I need to download a userspace tarball :)

-Peter

_______________________________________________
Linux-Vax mailing list
Linux-Vax at pergamentum.com
http://www.pergamentum.com/mailman/listinfo/linux-vax