The patch from Christoph Lameter:
[PATCH] radix-tree: Remove unnecessary indirections and clean up code
is only partially merged into -mm tree. This patch completes it.
Signed-off-by: Christoph Lameter <[email protected]>
Signed-off-by: Wu Fengguang <[email protected]>
---
lib/radix-tree.c | 12 +++++-------
1 files changed, 5 insertions(+), 7 deletions(-)
--- linux.orig/lib/radix-tree.c
+++ linux/lib/radix-tree.c
@@ -291,27 +291,25 @@ static inline void **__lookup_slot(struc
unsigned long index)
{
unsigned int height, shift;
- struct radix_tree_node **slot;
+ struct radix_tree_node *slot;
height = root->height;
if (index > radix_tree_maxindex(height))
return NULL;
shift = (height-1) * RADIX_TREE_MAP_SHIFT;
- slot = &root->rnode;
+ slot = root->rnode;
while (height > 0) {
- if (*slot == NULL)
+ if (slot == NULL)
return NULL;
- slot = (struct radix_tree_node **)
- ((*slot)->slots +
- ((index >> shift) & RADIX_TREE_MAP_MASK));
+ slot = slot->slots[(index >> shift) & RADIX_TREE_MAP_MASK];
shift -= RADIX_TREE_MAP_SHIFT;
height--;
}
- return (void **)slot;
+ return slot;
}
/**
--
Wu Fengguang <[email protected]> wrote:
>
> [PATCH] radix-tree: Remove unnecessary indirections and clean up code
>
> is only partially merged into -mm tree. This patch completes it.
md: autorun ...
md: ... autorun DONE.
Unable to handle kernel paging request at virtual address 8000003c
printing eip:
c013e16f
*pde = 00000000
Oops: 0000 [#1]
SMP
Modules linked in:
CPU: 1
EIP: 0060:[<c013e16f>] Not tainted VLI
EFLAGS: 00010086 (2.6.15-rc5-mm1)
EIP is at find_get_page+0x2e/0x4e
eax: 8000003c ebx: cff867e8 ecx: 8000003c edx: 8000003c
esi: cff867e8 edi: 00000000 ebp: cffafd44 esp: cffafd38
ds: 007b es: 007b ss: 0068
Process swapper (pid: 1, threadinfo=cffae000 task=cffa1a90)
Stack: <0>cff867ec 00000000 00042454 cffafdcc c013e5e7 cff867e8 00000000 cfcc62
<0>00000000 00000001 cffafdcc c02406b3 00001000 00000000 00042454 000000
<0>ffffffff 00000001 00000001 00000000 00000042 cff8673c 00000000 000000
Call Trace:
[<c0103b3b>] show_stack+0x8c/0xa2
[<c0103cd0>] show_registers+0x15d/0x1c5
[<c0103ed2>] die+0x10e/0x196
[<c048073a>] do_page_fault+0x34c/0x6b5
[<c01037ef>] error_code+0x4f/0x54
[<c013e5e7>] do_generic_mapping_read+0x13a/0x4ad
[<c013ec14>] __generic_file_aio_read+0x1c8/0x20c
[<c013ed63>] generic_file_read+0xa2/0xbb
[<c015ec94>] vfs_read+0xd4/0x19e
[<c015f02e>] sys_read+0x4b/0x75
[<c060f118>] identify_ramdisk_image+0x78/0x1ca
[<c060f2e3>] rd_load_image+0x79/0x317
[<c06119a9>] initrd_load+0x43/0x7d
[<c060ef4b>] prepare_namespace+0x3d/0x131
[<c01003f1>] init+0xe6/0x1d9
[<c01010dd>] kernel_thread_helper+0x5/0xb
Code: 83 ec 0c 89 5d fc 8b 5d 08 8d 43 10 e8 05 1d 34 00 8b 45 0c 89 44 24 04 8
<0>Kernel panic - not syncing: Attempted to kill init!
On Sun, Dec 04, 2005 at 03:57:50PM -0800, Andrew Morton wrote:
> Wu Fengguang <[email protected]> wrote:
> >
> > [PATCH] radix-tree: Remove unnecessary indirections and clean up code
> >
> > is only partially merged into -mm tree. This patch completes it.
>
> md: autorun ...
> md: ... autorun DONE.
> Unable to handle kernel paging request at virtual address 8000003c
> printing eip:
> c013e16f
> *pde = 00000000
> Oops: 0000 [#1]
> SMP
> Modules linked in:
> CPU: 1
> EIP: 0060:[<c013e16f>] Not tainted VLI
> EFLAGS: 00010086 (2.6.15-rc5-mm1)
> EIP is at find_get_page+0x2e/0x4e
It has been running ok on several machines for over a month. A mysterious
bug mysteriously corrected by the following radix-tree look-aside cache patch?
I'll test this single patch against -mm tree, thanks.
Wu
On Sun, Dec 04, 2005 at 03:57:50PM -0800, Andrew Morton wrote:
> Wu Fengguang <[email protected]> wrote:
> >
> > [PATCH] radix-tree: Remove unnecessary indirections and clean up code
> >
> > is only partially merged into -mm tree. This patch completes it.
>
> md: autorun ...
> md: ... autorun DONE.
> Unable to handle kernel paging request at virtual address 8000003c
> printing eip:
> c013e16f
> *pde = 00000000
> Oops: 0000 [#1]
> SMP
> Modules linked in:
> CPU: 1
> EIP: 0060:[<c013e16f>] Not tainted VLI
> EFLAGS: 00010086 (2.6.15-rc5-mm1)
> EIP is at find_get_page+0x2e/0x4e
It is reproduced here on linux-2.6.15-rc3-mm1 with this single patch.
I'm using qemu, and its screen outputs are not accessible. So I added some
delays to the dump code, and grabbed two screen shots.
Wu
On Sun, Dec 04, 2005 at 03:57:50PM -0800, Andrew Morton wrote:
> Wu Fengguang <[email protected]> wrote:
> >
> > [PATCH] radix-tree: Remove unnecessary indirections and clean up code
> >
> > is only partially merged into -mm tree. This patch completes it.
>
> md: autorun ...
> md: ... autorun DONE.
> Unable to handle kernel paging request at virtual address 8000003c
Sorry, the bug is caused by the returning line:
return slot;
It should be
return &slot;
The patch originally applies to
void *radix_tree_lookup()
But in -mm the function turns into
void **__lookup_slot()
And in my radixtree patch, it is
void *radix_tree_lookup_node()
The prototypes changed forth and back, so the problem was never discovered.
Wu
On Mon, 5 Dec 2005, Wu Fengguang wrote:
> It is reproduced here on linux-2.6.15-rc3-mm1 with this single patch.
> I'm using qemu, and its screen outputs are not accessible. So I added some
> delays to the dump code, and grabbed two screen shots.
Lets drop this patch. __lookup_slot returns a pointer to the slot element
and this patch changes the behavior of __lookup_slot making it return the
contents of the slot. Without the indirection the address of the slot is
not available so we need to keep the indirections in __lookup_slot.
On Mon, 5 Dec 2005, Wu Fengguang wrote:
> return slot;
>
> It should be
>
> return &slot;
That wont work. slot is a local variable. Drop this patch please.
On Mon, Dec 05, 2005 at 09:24:18AM -0800, Christoph Lameter wrote:
> On Mon, 5 Dec 2005, Wu Fengguang wrote:
>
> > return slot;
> >
> > It should be
> >
> > return &slot;
>
> That wont work. slot is a local variable. Drop this patch please.
Thanks. Sorry for the careless mistake.
But your patch do fit well in my patch :)
void *radix_tree_lookup_node(struct radix_tree_root *root,
unsigned long index, unsigned int level)
{
unsigned int height, shift;
struct radix_tree_node *slot;
height = root->height;
if (index > radix_tree_maxindex(height))
return NULL;
shift = (height-1) * RADIX_TREE_MAP_SHIFT;
slot = root->rnode;
while (height > level) {
if (slot == NULL)
return NULL;
slot = slot->slots[(index >> shift) & RADIX_TREE_MAP_MASK];
shift -= RADIX_TREE_MAP_SHIFT;
height--;
}
return slot;
}
void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
{
struct radix_tree_node *node;
node = radix_tree_lookup_node(root, index, 1);
return node->slots + (index & RADIX_TREE_MAP_MASK);
}