Buddy FAQ. Written by Alex Verstak. License: use at your own risk. ------------------------------ Q1: What is buddy allocator? A1: It's the most ancient memory manager I know of. Q2: How does it generally perform? A2: Poor locality and fragmentation, guaranteed speed O(logN). Q3: What is it for? A3: It's for managing DMA-able physical RAM. Q4: Why buddy system for DMA-able RAM? A4: It has several advantages: 1. Quick allocation/deallocation. 2. A block will never cross DMA 64KB boundary (unless it is more than 64KB). 3. No headers for free or used blocks, only a small fixed-size tree. 4. Convenient block sizes: 4K,8K,16K,32K,64K,...,16MB,...,1GB. 5. Fragmentation doesn't matter much. 6. Locality doesn't matter at all. Q5: Why not use buddy system for all physical RAM? A5: It has several disadvantages: 1. O(logN) is fast, but O(1) is faster. 2. Alignment is more of an obstacle for normal RAM. 3. Block sizes are different. Q6: Why not use buddy system for virtual RAM? A6: Because it sucks. Q7: What cookies does it have? Q7: There are some: 1. Allocation and deallocation at fixed address. 2. The above is page granular, not constrained by block sizes. 3. It never touches RAM being managed. 4. Therefore, one can easily cut out the regions with no RAM. Q8: Can I have several buddy systems? A8: No. Q9: How long is a page? A9: 4KB by default. You can change it to 8, 16, etc by defining ALLOCATION_GRANULARITY=1, 2, etc. Q10: How dumb-proof is it? A10: I tried to make it reliable. It rounds up ugly block sizes and can usually catch external intrusion in debug mode. However, no error correction. Q11: How to compile it? A11: I hope, any ANSI C compiler will do. I used GCC 2.8.1. Code uses two include files: assert.h for assert and stdio.h for printf. Q12: How to integrate it in OS? A12: It needs access to several static variables and a tree. Re-entrancy is not allowed. Calling convention is, well, C. The routines won't eat more than 128 bytes of stack. However, buddy_stat is recursive and can eat more. 4KB is more than enough. Q13: Example, please!!! A13: #include "buddy.h" //Suggested Initialization int s=buddy_size(16384*1024); //get tree size for 16MB buddy_init((char*)0x72000,0,16384*1024); //initialize 16MB starting 0, //use RAM at 0x72000 for tree buddy_free_all(); //make RAM available buddy_alloc_at((void*)0x72000,s); //reserve RAM for tree buddy_alloc_at((void*)0xa0000,0x60000); //reserve BIOS and video RAM buddy_free_at((void*)0xe0000,0x10000); //free 64KB of BIOS RAM ... #ifdef DEBUG buddy_stat(); //print statistics #endif ... //Suggested Runtime void *p=buddy_alloc(32768); //allocate 32K for DMA buddy_free(p); //...and free it void *f=buddy_alloc(4096); //allocate page for VM buddy_free(f); //...and free it --------------------------- end of buddy FAQ