linux-toradex.git/mm/bootmem.c, branch v2.6.27.25

bootmem: fix aligning of node-relative indexes and offsets

2008-08-20T22:40:31+00:00

Absolute alignment requirements may never be applied to node-relative
offsets.  Andreas Herrmann spotted this flaw when a bootmem allocation on
an unaligned node was itself not aligned because the combination of an
unaligned node with an aligned offset into that node is not garuanteed to
be aligned itself.

This patch introduces two helper functions that align a node-relative
index or offset with respect to the node's starting address so that the
absolute PFN or virtual address that results from combining the two
satisfies the requested alignment.

Then all the broken ALIGN()s in alloc_bootmem_core() are replaced by these
helpers.

Signed-off-by: Johannes Weiner 
Reported-by: Andreas Herrmann 
Debugged-by: Andreas Herrmann 
Reviewed-by: Andreas Herrmann 
Tested-by: Andreas Herrmann 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

bootmem allocator: alloc_bootmem_core(): page-align the end offset

2008-08-15T15:35:41+00:00

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.

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 
Acked-by: Johannes Weiner 
Cc: David Miller 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

bootmem: replace node_boot_start in struct bootmem_data

2008-07-24T17:47:20+00:00

Almost all users of this field need a PFN instead of a physical address,
so replace node_boot_start with node_min_pfn.

[Lee.Schermerhorn@hp.com: fix spurious BUG_ON() in mark_bootmem()]
Signed-off-by: Johannes Weiner 
Cc: 
Signed-off-by: Lee Schermerhorn 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

bootmem: revisit alloc_bootmem_section

2008-07-24T17:47:20+00:00

Since alloc_bootmem_core does no goal-fallback anymore and just returns
NULL if the allocation fails, we might now use it in alloc_bootmem_section
without all the fixup code for a misplaced allocation.

Also, the limit can be the first PFN of the next section as the semantics
is that the limit is _above_ the allocated region, not within.

Signed-off-by: Johannes Weiner 
Cc: Yasunori Goto 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

bootmem: Make __alloc_bootmem_low_node fall back to other nodes

2008-07-24T17:47:20+00:00

__alloc_bootmem_node already does this, make the interface consistent.

Signed-off-by: Johannes Weiner 
Cc: Ingo Molnar 
Cc: Yinghai Lu 
Cc: Andi Kleen 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

bootmem: respect goal more likely

2008-07-24T17:47:20+00:00

The old node-agnostic code tried allocating on all nodes starting from the
one with the lowest range.  alloc_bootmem_core retried without the goal if
it could not satisfy it and so the goal was only respected at all when it
happened to be on the first (lowest page numbers) node (or theoretically
if allocations failed on all nodes before to the one holding the goal).

Introduce a non-panicking helper that starts allocating from the node
holding the goal and falls back only after all thes tries failed, thus
moving the goal fallback code out of alloc_bootmem_core.

Make all other allocation functions benefit from this new helper.

Signed-off-by: Johannes Weiner 
Cc: Ingo Molnar 
Cc: Yinghai Lu 
Cc: Andi Kleen 
Cc: Yasunori Goto 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

bootmem: factor out the marking of a PFN range

2008-07-24T17:47:20+00:00

Introduce new helpers that mark a range that resides completely on a node
or node-agnostic ranges that might also span node boundaries.

The free/reserve API functions will then directly use these helpers.

Note that the free/reserve semantics become more strict: while the prior
code took basically arbitrary range arguments and marked the PFNs that
happen to fall into that range, the new code requires node-specific ranges
to be completely on the node.  The node-agnostic requests might span node
boundaries as long as the nodes are contiguous.

Passing ranges that do not satisfy these criteria is a bug.

[akpm@linux-foundation.org: fix printk warnings]
Signed-off-by: Johannes Weiner 
Cc: Ingo Molnar 
Cc: Yinghai Lu 
Cc: Andi Kleen 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

bootmem: free/reserve helpers

2008-07-24T17:47:20+00:00

Factor out the common operation of marking a range on the bitmap.

[akpm@linux-foundation.org: fix various warnings]
Signed-off-by: Johannes Weiner 
Cc: Ingo Molnar 
Cc: Yinghai Lu 
Cc: Andi Kleen 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

bootmem: clean up alloc_bootmem_core

2008-07-24T17:47:20+00:00

alloc_bootmem_core has become quite nasty to read over time.  This is a
clean rewrite that keeps the semantics.

bdata->last_pos has been dropped.

bdata->last_success has been renamed to hint_idx and it is now an index
relative to the node's range.  Since further block searching might start
at this index, it is now set to the end of a succeeded allocation rather
than its beginning.

bdata->last_offset has been renamed to last_end_off to be more clear that
it represents the ending address of the last allocation relative to the
node.

[y-goto@jp.fujitsu.com: fix new alloc_bootmem_core()]
Signed-off-by: Johannes Weiner 
Signed-off-by: Yasunori Goto 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

bootmem: clean up free_all_bootmem_core

2008-07-24T17:47:20+00:00

Rewrite the code in a more concise way using less variables.

[akpm@linux-foundation.org: fix printk warnings]
Signed-off-by: Johannes Weiner 
Cc: Ingo Molnar 
Cc: Yinghai Lu 
Cc: Andi Kleen 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds