Xen devel - Aug 2006 - What''s the reason for padding the alloc_bitmap in page_alloc.c?

I see the code in init_boot_allocator that added an extra longword to 
the size of alloc_bitmap.  Is there really a chance for overrun in 
map_alloc or map_free as the comment suggests?  I would think that 
allocating or freeing more than we have would be considered a bug.  I 
don''t know the history of that padding but I wonder if it is from 
another overflow that is fixable.  Doing bitmap_size = (max_page + 7)/8  
should be enough.

    /*
     * Allocate space for the allocation bitmap. Include an extra longword
     * of padding for possible overrun in map_alloc and map_free.
     */
    bitmap_size  = max_page / 8;
    bitmap_size += sizeof(unsigned long);
    bitmap_size  = round_pgup(bitmap_size);
    alloc_bitmap = (unsigned long *)maddr_to_virt(bitmap_start);


In page_alloc.c end_boot_allocator, there''s a slight chance that the 
allocated_in_map macro can cause an overflow.  This is because it uses 
i+1 as the parameter and i goes to i < max_pages (if i == max_pages then 
we overflow).

Most of the time, this is ok because the allocation is bigger than 
needed. But if it is just right, then we could have a problem.

    /* Pages that are free now go to the domain sub-allocator. */
    for ( i = 0; i < max_page; i++ )
    {
        curr_free = next_free;
        next_free = !allocated_in_map(i+1);
        if ( next_free )
            map_alloc(i+1, 1); /* prevent merging in free_heap_pages() */
        if ( curr_free )
            free_heap_pages(pfn_dom_zone_type(i), mfn_to_page(i), 0);
    }


and with allocate_in_map as:

#define allocated_in_map(_pn)                 \
( !! (alloc_bitmap[(_pn)/PAGES_PER_MAPWORD] & \
     (1UL<<((_pn)&(PAGES_PER_MAPWORD-1)))) )

We see here that we are indexing past the bitmap and can cause 
problems.  I wonder if this was actually happening and the above padding 
was done to hide this bug.  Well the padding does fix the bug, but I 
don''t think it''s the proper approach.

Attached is a patch to fix the overflow problem in end_boot_allocator.  
I''ll run it some time without that padding (do bitmap_size = (max_page
+
7)/8 instead) and see if there''s any other problems.  I''ll
also put a
test into map_alloc and map_free to tell me if something goes past 
max_page or bitmap size.

I would hate to have 134,184,960 bytes of memory:  134,184,960 / 4096 = 
32,760 :  32,760 / 8 = 4095  : 4095 + 4 = 4099 And now we have an extra 
page for the bitmap without it ever being used.   (OK that was 
hypothetical, but does make a small point. ;)

-- Steve

just in case you want the patch.

Signed-off-by: Steven Rostedt <srostedt@redhat.com>






_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xensource.com
http://lists.xensource.com/xen-devel

On 5/8/06 4:55 am, "Steven Rostedt" <srostedt@redhat.com> wrote:
> I see the code in init_boot_allocator that added an extra longword to
> the size of alloc_bitmap.  Is there really a chance for overrun in
> map_alloc or map_free as the comment suggests?  I would think that
> allocating or freeing more than we have would be considered a bug.  I
> don''t know the history of that padding but I wonder if it is from
> another overflow that is fixable.  Doing bitmap_size = (max_page + 7)/8
> should be enough.
There are plenty of places that can look one page (bit) beyond the end of
the map:
 1. Map_alloc and map_free set end_idx/offset as first_page + nr_pages. This
clearly references the first page *after* the range of interest. What if
that range ends on max_page-1?
 2. Free_heap_pages checks neighbouring pages of the freed range for
potential opportunities to merge to a higher-order buddy list. What if the
last page of the range being freed is max_page-1?

However, I think the bitmap allocation could be made a bit tighter. Perhaps:
   bitmap_size = round_pgup(max_page/8 + 1);
This rounds down to bytes, but then adds an extra byte so that we can always
go one off the end of the bitmap (really it''s just a simplification of
(max_page + 1 + 7) / 8). How does that sound?

NB. Going off the start of the bitmap is never a problem, since page 0 is
never available for allocation. :-)

 -- Keir



_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xensource.com
http://lists.xensource.com/xen-devel