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

Mon, 24 Jul 2006

Network tree allocator.


Here is brief description of my efforts directed to full sending and receiving zero-copy support for netchannels.

Main idea is to replace slab allocator with netchannel's own, so that all allocator's pool could be mapped from userspace. In that case all skbs allocated from that pool automagically become visible to userspace applications without any single memory copy.
If that allocator will be created in a right way, it will also solve problem with memory fragmentation and more generic problem with power of 2 allocators - big alignment overhead.

I read some papers about memory allocation in MMU-less systems (like uClinux kernels), and found that it is quite common problem, and there are several non-power-of-2 allocators, which might be used with my approach.
But it is not interesting way, I think, so I started to draw some initial design notes about how netchannel allocator will look like.

It will have several pools of contiguous memory chunks, at least pool of page sized chunks (which will be used for usual alocations) and one contiguos region (probably allocated at a boot time) for jumbo frames (and actually management of that pool can be used for MMU-less allocators).
Each contiguous region will have some control block attached which will store pointers to free and used sub-blocks inside the region (I plan to use chunks aligned to predefined constant value, for example 32 bytes). When some block is freed inside the contiguous region, it will be concatenated with neighbour free blocks thus reducing memory fragmentation. Pointers to the free regions will be placed into the AVL-tree as the fastest search/insert/delete tree among existing binary trees (all even worst times never exceed O(log2(N)), where N is number of nodes).
If size of the free area inside contiguous region differs after allocation/freeing, pointer will be moved inside the tree, thus rebalancing it.

Each AVL node is designed to be very memory efficient, so it only uses 12 bytes on any arch. This limits maximum number of nodes to 64k-1, if each node corresponds to value multiple of 32 bytes, this allows maximum 2mb contiguous block allocation, which is more than enough right now. If that limit is going to be changed, one just need to change definition of one type (avl_t). Current proof-of-concept userspace model implementation of the tree works with 16bit type to store each node's value parameter.

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