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

Fri, 28 Jul 2006

Network tree allocator.


And to complicate thins even more let's do everything simple.

Each allocated physical page (or pointers to larger contiguous blocks, they must differ and there must exist some way to obtain pointer to the start of the block from it's internal pointer, for example it is trivial to obtain pointer to the physical page (do not confuse with struct page) from the pointer inside that page - one just needs to AND given address with PAGE_MASK) is inserted into the AVL tree and live there forever. Each node has a bitmask of free and empty regions inside that page (if minimum allowed allocation block is 32 bytes, this bitmask takes PAGE_SIZE/32 bits), where each bit corresponds to part of the page which is used or free.
Each free region is placed into array of single-linked lists, where each list entry stores pointer to the actual free region and a pointer to the next entry. Array is indexed using allocation size (aligned to the minimum allowed allocation size).

When region is freed, appropriate page pointer is calculated (using trivial AND with PAGE_MASK) and page is selected inside the tree. Using offset from the page address to freed address we can select two neighbour regions which are either used or free and theirs sizes using search inside bitmask of free and used regions in each node. Free ones are searched inside lists for the appropriate sizes (yes, using slow search inside single-linked list, call me a loser), removed from that lists and concatenated (with node's bitmask update), then new free region is placed into the list for appropriate size.

When system is asked to allocate new region it checks list of free regions for the appropriate size, if it is empty it tries to get next list (with increased size). Eventually it will find the list with free region, which will be splitted into the used one (and appropriate pointer will be returned to the caller), and free one which will be moved into the new list for appropriate size. Bitmask of free and used regions for the node, which hosts page where returned region is allocated, will be updated accordingly.

If search (through single-linked list) for the free region which should be concatenated with freed one will take too much time (for example SLOB allocator works with similar searching for free object and no one complains), it is possible to replace it with double-linked one and set of pointers inside node which will point directly to the free region, so it can be removed and concatenated without speed overhead, but that will require list or array of pointers inside each node, so we will have additional memory overhead.

There is also a problem with jumbo frames and more than one page allocations. For the above scheme to work with more than a page contiguous blocks it is required that there is a way to determine initial pointer (start of the contiguous block) from any pointer inside that block (which is trivial with page sized chunks). It can be solved by allocation of the big sized pages from special address ranges (i.e. we can get page address and if it is from big sized pool of addresses, it will be updated accordingly).

But enough for theory, talks are cheap, so I plan to create initial implementation today.

P.S. And how that could be easier if I would not care too much about memory overhead... But it is another story.

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