Daniel's page
main thoughts license
Memory Allocation Algorithm Theories
GOAL

dbestfit is intended to be a 100% working memory allocation system. It should be capable of replacing an ordinary Operating System's own routines. It should work good in a multitasking, shared memory, non-virtual memory environment without clogging the memory. Primary aimed for small machines, CPUs and memory amounts.

I use a best-fit algorithm with a slight overhead in order to increase speed a lot. It should remain scalable and work good with very large amount of memory and free/used memory blocks too.

TERMINOLOGY

MEMORY SYSTEM

We split the system in two parts. One part allocates small memory amounts and one part allocates large memory amounts, but all allocations are done "through" the small-part-system. There is an option to use only the small system (and thus use the OS for large blocks) or the complete package.

Small Size Allocations

Keywords for this system is 'Deferred Coalescing' and 'quick lists'.

ALLOC

FREE
REALLOC

OVERHEAD

Yes, there is an overhead on small allocations (internal fragmentation). Yet, I do believe that small allocations more often than larger ones are used dynamically. I believe that a large overhead is not a big problem if it remains only for a while. The big gain is with the extreme speed we can GET and RETURN small allocations. This has yet to be proven. I am open to other systems of dealing with the small ones, but I don`t believe in using the same system for all sizes of allocations.

IMPROVEMENTS

An addition to the above described algorithm is the `save-empty-BLOCKS-a- while-afterwards`. It will be used when the last used FRAGMENT within a BLOCK is freed. The BLOCK will then not get returned to the system until "a few more" FRAGMENTS have been freed in case the last [few] freed FRAGMENTS are allocated yet again (and thus prevent the huge overhead of making FRAGMENTS in a BLOCK). The "only" drawback of such a SEBAWA concept is that it would mean an even bigger overhead...

HEADERS -in allocated data

Larger Allocations

If the requested size is larger than the largest FRAGMENT size supported, the allocation will be made for this memory area alone, or if a BLOCK is allocated to fit lots of FRAGMENTS a large block is also desired.

ALLOC RSIZE - requested size aligned properly

FREE AREA - piece of memory that is returned to the system

REALLOC

FURTHER READING

daniel at haxx dot .se