Monday, June 30, 2008

Memory management - low allocator base - binary buddy.

As I intended to memory managers implementing, I decide to write here about several techniques about this.
I don't interested on allocators in uspace now. I want to describe some tips and tricks on memory management while you haven't anything - just raw gdt/tss/ so on and raw addresses.
On low level of memory management and allocation system we're need to have a simple and fast memory allocator, it must avoid external fragmentation as strong as it possible.
There are one good allocator that doesn't sick with big external fragmentation - buddy system. You can find many it's types, but I'd like binary type - it's a very simple in calculation (that really needs).
Some words about buddy system... Buddy system is a such system that based on buddy relations for splitting memory areas. This system has several limitation - you must know deep of separation, I mean how much blocks maximally can contents buddy itself, and overally it can maps fixed memory area size (but it can be depends on implementation). The goal of this technique is to find free block aligned to requested size, when you are looking for some block size - you will separate block with bigger size and so on, while you didn't finf more situable block size. Look for illustrations: 
buddy system explanation
Fig. 1

The first bar shows clean buddy system without any allocated block (4096 bytes). When we're requesting to allocate block with size 512 byte we're separate zone to two blocks, and one of this zone separate we're separate too and use one of them - like it shown on the second bar. If we're request to allocate three more 512-sized block we will got the picture displayed on third bar.
It's a good and relativetly fast methodics, but has many restrictions - for example assume that your buddy system has 16byte-sized minimal blocks - and you request 10 bytes - so, you will get a wasted space - and so on - it's an inernal fragmentation. Be sure - you can align block sizes to other numbers , like you want and depend on your target, but anyway it will not safe to use buddy for all allocations.
Another point is a free/busy/separated blocks list storing - on low level you cannot use binary trees in case that they need to have some memory allocation technique already, usually for this used simple pointers lists, but it's a worse practice.
On the next post about memory management I will describe my solution of this problem with some useful code snippets.

No comments: