* Buddy allocator - help! I thought I understood this
@ 2001-09-05 18:48 Alex Bligh - linux-kernel
2001-09-05 20:44 ` Alex Bligh - linux-kernel
2001-09-08 1:47 ` Linus Torvalds
0 siblings, 2 replies; 3+ messages in thread
From: Alex Bligh - linux-kernel @ 2001-09-05 18:48 UTC (permalink / raw)
To: linux-kernel; +Cc: Alex Bligh - linux-kernel
I could swear I understood this bit of __free_pages_ok()
Monday night, but my mind appears to have gone blank.
As I recall, the memory bitmaps indicate by the
status a bit op returns whether or not a page
is on the free list for that particular order
area.
So how does this work (lines from vanilla 2.4.9
attached). I'm interested particularly in line
114:
if (!__test_and_change_bit(index, area->map))
This examines the bitmap entry, in the
current order being examined bitmap.
As the page is being free'd, on the first pass,
won't the page ALWAYS register as unallocated?
This claims to test whether the buddy page
is still allocated. Wouldn't this test be:
if (!__test_and_change_bit(index^1, area->map))
The annoying thing is I'm SURE I read through
this and understood it fully Monday night.
Or is the bitmap trying to tell us whether the
BUDDY is used? This doesn't seem to be what
expand et al are doing.
Please help - my head hurts.
(NB, if this is a code bug rather than local brain
bug, this explains a lot)
--
Alex Bligh
99 if (page_idx & ~mask)
100 BUG();
101 index = page_idx >> (1 + order);
102
103 area = zone->free_area + order;
104
105 spin_lock_irqsave(&zone->lock, flags);
106
107 zone->free_pages -= mask;
108
109 while (mask + (1 << (MAX_ORDER-1))) {
110 struct page *buddy1, *buddy2;
111
112 if (area >= zone->free_area + MAX_ORDER)
113 BUG();
114 if (!__test_and_change_bit(index, area->map))
115 /*
116 * the buddy page is still allocated.
117 */
118 break;
119 /*
120 * Move the buddy up one level.
121 */
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: Buddy allocator - help! I thought I understood this
2001-09-05 18:48 Buddy allocator - help! I thought I understood this Alex Bligh - linux-kernel
@ 2001-09-05 20:44 ` Alex Bligh - linux-kernel
2001-09-08 1:47 ` Linus Torvalds
1 sibling, 0 replies; 3+ messages in thread
From: Alex Bligh - linux-kernel @ 2001-09-05 20:44 UTC (permalink / raw)
To: Alex Bligh - linux-kernel, linux-kernel; +Cc: Alex Bligh - linux-kernel
thanks for the responses. FWIW:
> (NB, if this is a code bug rather than local brain
> bug, this explains a lot)
It's was a transient local brain bug. The bit
is shared between two pages of the same order.
> 101 index = page_idx >> (1 + order);
I missed this today ^^^
And hence my previous patch did have a bug,
for arcane reasons; I'll resubmit it if
it works.
--
Alex Bligh
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: Buddy allocator - help! I thought I understood this
2001-09-05 18:48 Buddy allocator - help! I thought I understood this Alex Bligh - linux-kernel
2001-09-05 20:44 ` Alex Bligh - linux-kernel
@ 2001-09-08 1:47 ` Linus Torvalds
1 sibling, 0 replies; 3+ messages in thread
From: Linus Torvalds @ 2001-09-08 1:47 UTC (permalink / raw)
To: linux-kernel
In article <525190103.999719280@[10.132.112.53]>,
Alex Bligh - linux-kernel <linux-kernel@alex.org.uk> wrote:
>I could swear I understood this bit of __free_pages_ok()
>Monday night, but my mind appears to have gone blank.
>
>As I recall, the memory bitmaps indicate by the
>status a bit op returns whether or not a page
>is on the free list for that particular order
>area.
No. It actually indicates that the _buddy_ of the page is on the free
list for that particular order.
Basically each bit describes two pages of the order in question, which
is sufficient because while they have four states (both free, first
free, second free, neither free), we get the "other bit" of information
from the fact that we are just freeing one page - which obviously cannot
have been free before.
Thus the games with xor'ing the bit around, and looking at the old
state.
And no, most kernel programmers don't have to actually follow that piece
of code. Ugly but efficient.
Linus
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2001-09-08 1:51 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2001-09-05 18:48 Buddy allocator - help! I thought I understood this Alex Bligh - linux-kernel
2001-09-05 20:44 ` Alex Bligh - linux-kernel
2001-09-08 1:47 ` Linus Torvalds
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).