* Re: Buddy algorithm questions
2003-08-21 16:38 ` Buddy algorithm questions Kirk True
@ 2003-08-21 22:36 ` William Lee Irwin III
0 siblings, 0 replies; 2+ messages in thread
From: William Lee Irwin III @ 2003-08-21 22:36 UTC (permalink / raw)
To: Kirk True; +Cc: Linux Memory Manager List
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>
^ permalink raw reply [flat|nested] 2+ messages in thread