Re: Buddy algorithm questions

[William Lee Irwin III <wli@holomorphy.com>]

On Thu, Aug 21, 2003 at 09:38:10AM -0700, Kirk True wrote:
> I am using Mel's excellent primer on the VM and the O'Reilly kernel 
> book, but I'm unable (too daft?) to find answers to the following 
> questions on buddy pairing:
> 1. Are "page_idx", "index", "buddy1", and "buddy2" always a multiple of
>    2^order? I don't think index needs to be, but I believe it's
>    absolutely critical that the others are. Is this correct?

page_idx and index are; buddy1 and buddy2 are the the page and its
buddy.


On Thu, Aug 21, 2003 at 09:38:10AM -0700, Kirk True wrote:
> 2. Is the address of buddy2 always after the address of buddy1 or is the
>    address of buddy2 always before the address of buddy1? My assumption
>    is "no", because from __free_pages_ok:
>        buddy1 = base + (page_idx ^ -mask);
>        buddy2 = base + page_idx;
>    (page_idx ^ -mask) flips the 2^order bit of page_idx. So there are
>    two cases:
>        1. If the 2^order bit *was* set, "page_idx ^ -mask" *clears* the
>           bit with the result that the value is (page_idx - 2^order).
>           Thus the address of buddy1 is less than the address of buddy2.
>        2. If the 2^order bit was *not* set, "page_idx ^ -mask" *sets*
>           the bit with the result that the value is (page_idx +
>           2^order). Thus buddy1 > buddy2.
>    Is this assessment correct?

That assessment is correct.


On Thu, Aug 21, 2003 at 09:38:10AM -0700, Kirk True wrote:
> 3. Question 2 dealt with the *addresses* of buddy1 and buddy2. What
>    about their respective *indexes* into the zone's mem_map array? That
>    is, is the index of buddy2 always after the index of buddy1 or is the
>    index of buddy2 always before the index of buddy1?

No. They are buddies, so they will have opposite alignments at level
order + 1, i.e. one will be the middle of the next higher-order page,
and the other will be at the beginning of it.


On Thu, Aug 21, 2003 at 09:38:10AM -0700, Kirk True wrote:
> 4. __free_pages_ok performs a bitwise exclusive OR to find the buddy.
>    However, on the allocation side of things __alloc_pages, rmqueue, nor
>    expand have any such bitwise operations. The code in expand makes it
>    look as though buddy2's address is always buddy1's plus the
>    order-sized page block. How is it then that sometimes buddy1's
>    address is before buddy2's and sometimes it's after in
>    __free_pages_ok as mentioned in question 2 above?
> I look forward to your answers or pointers to answers ;)

expand() gets to choose whether it's dealing with an aligned or
unaligned buddy because it's just breaking a lower-order page off of
a higher-order page, and nothing below it cares where inside the
higher-order page the lower-order piece comes from.

rmqueue() doesn't do the accounting itself; it hands it all off to
expand() apart from the bottom-level bit twiddle.

__alloc_pages() hands off all the work to rmqueue() and expand().


-- wli
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>