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.

• FRAGMENT - small identically sized parts of a larger BLOCK, they are when travered in lists etc _not_ allocated.
• BLOCK - large memory area, if used for FRAGMENTS, they are linked in a lists. One list for each FRAGMENT size supported.
• TOP - head struct that holds information about and points to a chain of BLOCKS for a particular FRAGMENT size.
• CHUNK - a contiguous area of free memory
• AREA - a piece of memory, either allocated or freed.

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.

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

• Small allocations are "aligned" upwards to a set of preset sizes. In the current implementation I use 20, 28, 52, 116, 312, 580, 812, 2028 bytes. Memory allocations of these sizes are refered to as FRAGMENTS. (The reason for these specific sizes is the requirement that they must be 32-bit aligned and fit as good as possible within 4060 bytes.)
• Allocations larger than 2028 will get a BLOCK for that allocation only.
• Each of these sizes has it's own TOP. When a FRAGMENT is requested, a larger BLOCK will be allocated and divided into many FRAGMENTS (all of the same size). TOP points to a list with BLOCKS that contains FRAGMENTS of the same size. Each BLOCK has a 'number of free FRAGMENTS' counter and so has each TOP (for the entire chain).
• A BLOCK is around 4060 bytes plus the size of the information header. This size is adjusted to make the allocation of the big block not require more than 4096 bytes. (This might not be so easy to be sure of, if you don't know how the big-block system works, but the BMALLOC system uses an extra header of 12 bytes and the header for the FRAGMENT BLOCK is 20 bytes in a general 32-bit unix environment.)
• In case the allocation of a BLOCK fails when a FRAGMENT is required, the next size of FRAGMENTS will be checked for a free FRAGMENT. First when the larger size lists have been tested without success it will fail for real.

• When FRAGMENTS are freed so that a BLOCK becomes non-used, it is returned to the system.
• FREEing a fragment adds the buffer in a LIFO-order. That means that the next request for a fragment from the same list, the last freed buffer will be returned first.

• REALLOCATION of a FRAGMENT does first check if the new size would fit within the same FRAGMENT and if it would use the same FRAGMENT size. If it does and would, the same pointer is returned.

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.

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...

• FRAGMENTS - 32-bit pointer to its parent BLOCK (lowest bit must be 0)
• BLOCK - 32-bit size (lowest bit must be 1 to separate this from FRAGMENTS)

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.

• We add memory to the "system" with the add_pool() function call. It specifies the start and size of the new block of memory that will be used in this memory allocation system. Several add_pool() calls are supported and they may or may not add contiguous memory.
• Make all blocks get allocated aligned to BLOCKSIZE (sometimes referred to as 'grain size'), 64 bytes in my implementation. Reports tell us there is no real gain in increasing the size of the align.
• We link *all* pieces of memory (AREAS), free or not free. We keep the list in address order and thus when a FREE() occurs we know instanstly if there are FREE CHUNKS wall-to-wall. No list "travels" needed. Requires some extra space in every allocated BLOCK. Still needs to put the new CHUNK in the right place in size-sorted list/tree. All memory areas, allocated or not, contain the following info in the header:
  • size of this memory area
  • FREE status
  • pointer to the next AREA closest in memory
  • pointer to the prev AREA closest in memory
  (12 bytes in total)
• Sort all FREE CHUNKS in size-order. We use a SPLAY TREE algorithm for maximum speed. Data/structs used for the size-sorting functions are kept in an abstraction layer away from this since it is really not changing anything (except executing speed).

• Fetch a CHUNK that RSIZE fits within. If the found CHUNK is larger than RSIZE, split it and return the RSIZE to the caller. Link the new CHUNK into the list/tree.

• Since the allocated BLOCK has kept its link-pointers, we can without checking any list instantly see if there are any FREE CHUNKS that are wall-to-wall with the AREA (both sides). If the AREA *is* wall-to-wall with one or two CHUNKS that or they are unlinked from the lists, enlarged and re-linked into the lists.

• There IS NO realloc() of large blocks, they are performed in the higher layer (dmalloc).

• "Dynamic Storage Allocation: A Survey and Critical Review" (Paul R. Wilson, Mark S. Johnstone, Michael Neely, David Boles) ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps
• "A Memory Allocator" (Doug Lea) http://g.oswego.edu/dl/html/malloc.html