linux-kernel - Bootmem allocator broken [was: console handover badness]

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Thu, 14 Aug 2008 19:11:19 -0400 (EDT)
From:	Mikulas Patocka <mpatocka@...hat.com>
To:	David Miller <davem@...emloft.net>,
	Johannes Weiner <hannes@...urebad.de>
cc:	sparclinux@...r.kernel.org, linux-kernel@...r.kernel.org
Subject: Bootmem allocator broken [was: console handover badness]



On Wed, 13 Aug 2008, David Miller wrote:

> From: Mikulas Patocka <mpatocka@...hat.com>
> Date: Wed, 13 Aug 2008 08:46:37 -0400 (EDT)
> 
> > On Tue, 12 Aug 2008, David Miller wrote:
> > 
> > > Mikulas can you send me the .config you're using in 2.6.27 to trigger
> > > this?
> > > 
> > > Thanks.
> > 
> > Here it is. The computer is Ultra 5 with 512MB RAM.
> 
> Thanks, I've tried a lot of things to try and reproduce this myself but to
> no avail.
> 
> Let's try to track down exactly where the corruption happens.  Please try
> the debug patch below on your box.  It will spit out a message something
> like:
> 
> [    0.000000] BUG: Bogus migrate type 5
> [    0.000000] BUG: Usemap for section 0 corrupted at sparse_init+0x17c/0x218[mm/sparse.c:498]
> 
> The theory is that some other piece of code is either not allocating a large
> enough buffer or overwriting past the end of a validly sized other buffer
> for some reason, and thus clobbering this pageblock flags bitmap.
> 
> Wherever this debugging check first triggers should give us some idea
> of who the culprit might be.

Hi

So I tried the patch and found out that the corruption happens in 
setup_command_line --- the first strcpy call corrupted the migratetype 
map.

Examining the problem further, it turned out that Johannes Weiner 
committed new bootmem allocator to 2.6.27-rc1 and the allocator is broken.

This is the minimal sequence that jams the allocator:

void *p, *q, *r;
p = alloc_bootmem(PAGE_SIZE);
q = alloc_bootmem(64);
free_bootmem(p, PAGE_SIZE);
p = alloc_bootmem(PAGE_SIZE);
r = alloc_bootmem(64);

--- after this sequence (assuming that the allocator was empty or 
page-aligned before), pointer "q" will be equal to pointer "r".

What's hapenning inside the allocator:
p = alloc_bootmem(PAGE_SIZE);
in allocator: last_end_off == PAGE_SIZE, bitmap contains bits 10000...
q = alloc_bootmem(64);
in allocator: last_end_off == PAGE_SIZE + 64, bitmap contains 11000...
free_bootmem(p, PAGE_SIZE);
in allocator: last_end_off == PAGE_SIZE + 64, bitmap contains 01000...
p = alloc_bootmem(PAGE_SIZE);
in allocator: last_end_off == PAGE_SIZE, bitmap contains 11000...
r = alloc_bootmem(64);
and now:
it finds bit "2", as a place where to allocate (sidx)
it hits the condition
if (bdata->last_end_off && PFN_DOWN(bdata->last_end_off) + 1 == sidx))
start_off = ALIGN(bdata->last_end_off, align);
--- you can see that the condition is true, so it assigns start_off = 
ALIGN(bdata->last_end_off, align); --- that is PAGE_SIZE --- and allocates 
over already allocated block.

This patch fixes it (kernels 2.6.27-rc2 and 2.6.27-rc3 boot ok after the 
patch). Johannes, please review the patch and submit it to Linus.

With the patch it tries to continue at the end of previous allocation only 
if the previous allocation ended in the middle of the page.

Signed-off-by: Mikulas Patocka <mpatocka@...hat.com>

---
 mm/bootmem.c |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

Index: linux-2.6.27-rc2-orig/mm/bootmem.c
===================================================================
--- linux-2.6.27-rc2-orig.orig/mm/bootmem.c	2008-08-15 00:10:38.000000000 +0200
+++ linux-2.6.27-rc2-orig/mm/bootmem.c	2008-08-15 00:10:53.000000000 +0200
@@ -473,7 +473,7 @@ find_block:
 				goto find_block;
 			}
 
-		if (bdata->last_end_off &&
+		if (bdata->last_end_off & (PAGE_SIZE - 1) &&
 				PFN_DOWN(bdata->last_end_off) + 1 == sidx)
 			start_off = ALIGN(bdata->last_end_off, align);
 		else


--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/