About :: TODO :: Blog :: RSS :: Old blog :: Projects :: GIT :: Gallery :: Notes

Thu, 27 Jul 2006

Network tree allocator.


Brief and simplified allocation/freeing algorithm design description.

Each node inside AVL tree will have a head of the list(s), each list entry can be dereferenced into special container which holds info about it's two neighbours (if it is used region, then it's neighbours are either NULLs or free regions).

Free algorithm.
When some chunk is freed it is found in the tree and then it's neighbours are found too, then each of three containers are removed from appropriate nodes and regions are concatenated into one free region and new (or existing) node selected to store this new memeber inside node's list.

Allocation algorithm.
If there is a node with exactly requested (aligned) size, then one of it's chunks is used and that chunk is moved from free into used list.
If there is no such a node, then the nearest with larger regions is used. System removes one chunk from free list and split it into the two - chunks are moved into used and free lists inside nodes of the appropriate sizes (chunk with requested size into used list, empty chunk (and new container for it) is moved into empty list).

There are no pointers inside each AVL node (it's size is 10 bytes on every arch), but instead variable size bitfields are used which are offsets inside global array of nodes. Mentioned above containers for free and used memory regions must have at least one pointer to the actual region, a pointer (or it's id) to the next container (to create lists of used/free chunks) and two bitfields to show it's neighbours.

While moving home I changed my opinion on above notes.
Everything that uses lists and is not FIFO or LIFO is broken. Or at least a lot of.
So, no lists.
Main AVL tree will be replaced with array of trees, each one corresponds to the set of used chunks of the selected size, each tree will be indexed with a pointer to the used chunk (or it's part). All free chunks will be placed into the single-linked list. Allocation and freeing algorithms are essentially the same as described above.

/devel/networking/nta :: Link / Comments ()