OsFaqWiki - Allocating and Freeing Memory

One of the most basic functions of a kernel is the memory management, i.e. the allocating and freeing of memory.

At square one, the kernel is the only process in the system. But it is not alone: BIOS data structures, memory-mapped hardware registers etc. populate the address space. Among the first things a kernel must do is to start bookkeeping about which areas of physical memory are available for use and which are to be considered "occupied".

The free space will subsequently be used for kernel data structures, application binaries, their heap and stack etc. - the kernel needs a function that marks a memory area as reserved, and makes that memory available to the process requiring it. In the C Standard Library, this is handled by malloc() and free(); in C++ by new() and delete().

A very very simple Memory Manager

The easiest you can do is the WaterMark allocator. Just keep track of how far you've allocated and forget about the notion of "freeing".

            before ...
                                                           <-N-->
    +----+-----+--+--------//--+             +----+-----+--+----+---//--+
    |##A#|##B##|C#|  free      |             |##A#|##B##|C#|##D#|free   |
    +----+-----+--+---------//-+             +----+-----+--+----+---//--+
                  ^freebase    ^freetop                    ^d   ^fbase  ^ftop

When allocating N bytes for D, simply check that freetop-freebase>N and increment freeebase by N. Period.

A very simple Memory Manager

Now, if you need to free things, one of the easiest solution is to put at the start of the freed zone a descriptor that allows you to insert it in a list of free zones. Keeping that list sorted by address helps you identifying contiguous free zones and allows you to merge them in larger free zones.

       first free                        Structure of a   +--.--.--.--+    +---> +-- ...
         \/                              free zone        |F  R  E  E |    |     | FREE
    +----+-----+--+----+---+-----//--+                    |nextfreeptr|----+
    |##A#|free |C#|free|#E#|   free  |               <----|prevfreeptr|
    +----+-|---+--+-|--+---+-----//--+                    | zone size |
           +-next>--+                                     +///////////+

What data structure and algorithms can be used with such lists has been discussed in Memmaker's started thread (as well as in many others)

Tips to go further

Sometimes, and especially when you're working with objects, you have to allocate many objects that always have a certain size. It is wise to create pools of pre-divided large blocks for such objects.
It's way easier to keep the size of allocated objects in a header hidden from the requestor, so that a call to "free" doesn't require the object's size.
It's way easier to design a memory allocator in a host OS than in your kernel.
Magic words like "F R E E" and "U S E D" will make your life easier when debugging. TimRobinson even allows 32 bits to store the address of the requestor so that you can see "okay, this is a N-bytes block that was requested by MySillyFunction(), line 3405" ...

Memory & Microkernels

The following paragraphs were contributed to the Pro-POS Wiki by "Beyond Infinity". He agreed to have them forwarded here due to their catch-all nature.
-- MartinBaute

In a microkernel environment, there comes up a question: where the hell shall I put the memory management? In sense of heap management: give the kernel a dedicated allocator and a dedicated memory area to use - you might need two of them: one for the messages, and one for all the other stuff.

The other task of memory management: Process address space management, keeping track of used pages (yes, lets talk about paging, it is nice, it is neat, it causes a warm fuzzy feeling beneath the toes) and assigning memory to processes as needed, you can split it up. To be more precise, you have to split this task up - or keep every aspect of memory management in kernel land to make it easy. A recommended method for managing process address space: handle it in a per-process-manner. The actual process needs memory: allocate the memory and hand it out to the process. So you can keep the page allocating routines easy and straight forward. For this task of allocating/deallocating memory, you should take into consideration, that the task performing such actions should be able to slip into adress spaces at needs (it loads the required pagedirectory and does what it has to do - slimy little weasel thou' it is.) Take those things into good consideration and put quite an amount of brainwork into them. It's worth doing good engineering here.