Re: [PATCH] Tight check of pfn_valid on sparsemem - v4

[Dave Hansen]

On Sat, 2010-07-31 at 11:38 +0100, Russell King - ARM Linux wrote:
> On Fri, Jul 30, 2010 at 06:32:04PM +0900, Minchan Kim wrote:
> > On Fri, Jul 30, 2010 at 5:55 AM, Dave Hansen <dave@xxxxxxxxxxxxxxxxxx> wrote:
> > > If you free up parts of the mem_map[] array, how does the buddy
> > > allocator still work?  I thought we required at 'struct page's to be
> > > contiguous and present for at least 2^MAX_ORDER-1 pages in one go.
> 
> (Dave, I don't seem to have your mail to reply to.)
> 
> What you say is correct, and memory banks as a rule of thumb tend to be
> powers of two.
> 
> We do have the ability to change MAX_ORDER (which we need to do for some
> platforms where there's only 1MB of DMA-able memory.)
> 
> However, in the case of two 512KB banks, the buddy allocator won't try
> to satisfy a 1MB request as it'll only have two separate 2x512K free
> 'pages' to deal with, and 0x1M free 'pages'.

Right, it won't try to _coalesce_ those pages, but it will go trying to
look for the freed page's buddy in the empty area.  This is probably a
pretty rare issue, but I think it's real.  Take a look at
__free_one_page():

...
        while (order < MAX_ORDER-1) {
                buddy = __page_find_buddy(page, page_idx, order);
                if (!page_is_buddy(page, buddy, order))
                        break;

We look at the page, and the order of the page that just got freed.  We
go looking to see whether the page's buddy at this order is in the buddy
system, and _that_ tells us whether a coalesce can be done.  However, we
do this with some funky math on the original page's 'struct page *':

static inline struct page *
__page_find_buddy(struct page *page, unsigned long page_idx, unsigned int order)
{
        unsigned long buddy_idx = page_idx ^ (1 << order);

        return page + (buddy_idx - page_idx);
}

That relies on all 'struct pages' within the current 2^MAX_ORDER to be
virtually contiguous.  If you free up section_mem_map[] 'struct page'
blocks within the MAX_ORDER, the free'd page's buddy's 'struct page'
might fall in the area that got freed.  In that case, you'll get an
effectively random PageBuddy() value, and might mistakenly coalesce the
page.

In practice with a 1MB MAX_ORDER and 512KB banks, it'll only happen if
you free the page representing the entire 512KB bank, and if the memory
for the other half 'struct page' has already gotten reused.  That's
probably why you've never seen it.

-- Dave

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