Initializing buddy allocator

[NOTNULL]

Hi all,
After reading Intel docs, memory mgmt tutorials, Linux memory management books, I got an overall idea of memory management and various algorithms used to allocate and free page frames. I prefer to implement buddy allocator in my kernel to allocate page frames in different regions (DMA and NORMAL). I didn't find any tutorial that explains how to initialize the buddy system allocater based on the physical memory available in the system. There will be two variables to hold the buddy data structure in my kernl, one for DMA page frames (<16 MB) and another for NORMAL regions (>16 MB).

Could anyone explain me how to initialize the buddy allocator? i.e., how to add the page frames into the different page frame regions (1, 2, 4, 8, 16, etc), initially?

[Pype.Clicker]

from collected knowledge in the FAQ

Since your memory is initially a contiguous region, you just set the bits accordingly, e.g. for each 'granularity' of the buddy,
- detect the first bit to be set
- detect the last bit to be set
- set all the bits in that region

the 'first bit to be set' will be the first 2^N 'page' to be fully within the free region, e.g. if you're reported 15MB of free memory starting at 1MB, your buddy looks like
[tt]01xx xxxx xxxx xxxx (1MB)[/tt]
[tt]0-1- x-x- x-x- x-x-(2MB)[/tt]
[tt]0--- 1--- x--- x---(4MB)[/tt]
[tt]0--- ---- 1--- ----(8MB)[/tt]

Similarily, if only 12MB are reported above 1MB (e.g. an odd system having 13MB of RAM installed)
[tt]01xx xxxx xxxx 1000(1M)[/tt]
[tt]0-1- x-x- x-x- 0-0-(2M)[/tt]
[tt]0--- 1--- 1--- 0---(4M)[/tt]
[tt]0--- ---- 0--- ----(8M)[/tt]

[NOTNULL]

Thanks pype. I think I have understood the buddy bitmaps wrongly. Will the buddy bitmaps of various sizes (1p, 2p, 4p, 8p, etc) point to the same memory regions? I designed my buddy allocator in such a way that physical memory will be grouped into 2^N pages, where N=0,1,2,3,4,etc. Please clarify.

Any help greatly appreciated.

[Pype.Clicker]

well, all the bitmaps of your buddy will be in separate memory areas. bit 0 of buddy(0) will be for page frame 00000xxx while bit 0 of buddy(1) is for page frame 00000xxx and 00001xxx. bit 0 of buddy(2) covers 00000xxx - 00003xxx and so on.

Let's say you have N pages of memory, you'll use

Code: Select all

  buddy = new array[20] of pointers;
  buddysize=N/8 + ((N%8)?1:0);

  for (i=0..19) {
     buddy[i] = new array(buddysize) of chars;
     buddysize=buddysize/2;
  }

If you want to allocate a n-pages chunk in the buddy, you proceed as such:
- let 2^k be smallest power of 2 above n
- search for a bit present in buddy[k] (say it's at position i)
if found,
- clear_bit(buddy[k],i)
- you got pages i*2^k .. ((i+1)*2^k)-1
- only pages i*2^k .. (i*2^k) + n interrest us, the other will be returned
if not found,
- repeat search for k=k+1 until you reach k=20 (chunk of 4GB)

Note that this only works if bits buddy[k],i and buddy[k],i+1 are cleared when buddy[k+1],i/2 is set (for even i)