About TODO Blog RSS Old blog Projects Gallery Notes

Wed, 09 Aug 2006

Network tree allocator.


While thinking some more about generic tree and hash table data representation, I've come to the conclusion, that tree should be more appropriate case for the structures which can dynamically grow/shrink with the time. For example with netwrok tree allocator it is trivial task to add new memory into the cache, and it is easy task to remove pages (but not trivial, since AVL-tree removing algo is very complex, although fast (and to be 100% honest with the reader, I want to note, that I did not implement it for NTA)), so memory hotplug and various OOM conditions can be handled much more nicely than with table based approach where parts of the table must be relocated.

The same issue comes in mind with recent changes in network hash tables manipulations - table dynamic grow/shrink sometimes requires the whole table relocation, which can be extremely large. As far as I recall there was a discussion about tree vs. table approach and the later was selected, but I do not recall any details already. Well, maybe it's time to reimplement the thing... At least for upcoming fast NAT rework I plan to use trees instead of hash tables to store NAT entries, and since most of my work looks for the most people like researching-only (it is not actually) projects far from reality (only two of them are in the kernel tree), I can create any crazy schemes I like.

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

Comments are closed for this story.