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

Fri, 10 Nov 2006

Netchannels wildcards algos.


Here was initial design of netchannels wildcards with appropriate picture.

Let's analyze first problem we strike when trying to implement that design.
It is presentation of wildcard intervals (for example two rules: 192.168.0.0-192.168.0.255 and 192.168.0.10-192.168.0.20) in one-dimensional set of non-crossing ranges. Our example splits into three ranges: 192.168.0.0-192.168.0.9, 192.168.0.10-192.168.0.20, 192.168.0.21-192.168.0.255.
All those intervals can be easily represented by structures in C language and can be placed into tree for the fastest access. Each interval structure will have a pointer to the next dimansion range tree (like tree for ports and protocols), nodes of the last tree of intervals will contain pointers to the actual netchannels, which parameters (address, ports and so on) cover selected intervals in appropriate dimensions.
Interval splitting happens in context of netchannel creation and must be protected against simultaneous access both from softirqs (where packets enter network stack) and process context, where other netchannel can be added or removed.
In theory all netchannel trees of intervals can be protected by BH-disabling locks - but it is not nice solution - even if tree traversal itself is very fast and can be done under BH-disabling lock, there is possibility that interval currently being checked must be split into several ones, which requires intervals allocations, which should not be perfomed in atomic context.
So I propose simple scheme lurked in Linux socket locking - under BH-disabling lock we set the flag, that we currently process the tree, so process context will sleep on that flag until it is cleared and (under the same BH-disabling lock) set it again protecting itself against other process trying to access the tree. So usual lock will serialize process and softirq process and semaphore-like locking will be used to serialize process context.

/devel/networking :: Link / Comments ()