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

Wed, 26 Jul 2006

Network tree allocator.


AVL tree implementation has passed 90 milliards search/insert operations (tree was recreated after 10 millions operations), which confirms it's correctness.
Test used full 64k-node tree, which took about 768kb of memory, maxiumum tree height is 16. If use that tree as a base for memeory allocator in kernel and limit maximum allocation of 64kb and align each allocation to 32 bytes, the whole tree will have 2048 nodes (height does not exceed 11), which takes 24kb. If kernel power-of-2 allocator is used for 1500 bytes sized chunks, it's overhead will become higher than AVL-tree one when 50 allocations are in flight, if 9k jumbo frames are used, then it is enough to allocate 4 frames.
AVL-tree overhead does not get into account how free chunks will be placed inside the node. Since both input and output part of the stack can allocate the whole pages, it is not correct to put some list header into each page in the NTA pool, so pages and other free chunks must be stored inside arrays bound to each node inside AVL tree. That arrays will be refilled from main pools each time node is empty and there is a request for appropriate size.

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