Lock-less Synchronization For Netgraph

Student: Zain Khan (zain@freebsd.org)
Mentors: Gleb Smirnoff (glebius@freebsd.org), Alexander Chernikov (melifaro@freebsd.org)

Netgraph helps us implement custom or complex networking functions by letting us arrange kernel objects called nodes in a graph connected using hooks. Nodes may perform a well-defined set of actions on incoming packets, and may send the output to another connected node. To 'send' a packet to a neighbour can also be seen as calling a function on that neighbouring node.

Now in a pre-SMP world, a thread (or the thread) would always see nodes as idle (not busy), so that their functions can immediately be called. Concurrency introduced the possibility of a busy node. Moreover, a journey of a packet also needs to take heed of changes in the structure of the graph, for example: the addressed node's path may not remain intact due to no-longer-existing hooks or nodes in between, which may lead to cases such as referring to an object that has been freed. To counter such disasters, the existing source code uses a topology read-write mutex which protects data flow from restructuring events (and restructuring events from other restructuring events).

We want to regain the same smooth flow for data which existed when concurrent cpus were not a thing. That is, data should simply never wait every time there is a restructuring event. At the same time we also obviously do not want to give the kernel reasons to panic.

FreeBSD has its own set of concurrency-safe data structures and mechanisms. One of these mechanisms is Epoch. Epoch-based reclamation involves waiting for existing read-side critical sections to finish before the data structures need to be modified or reclaimed. Concurrency Kit data structures such as CK_LISTs can also be leveraged in place of the current LISTs used in the base source.

Completely get rid of ng_acquire_read/write() but probably the queues are to stay for the stack limit support
Since locked nodes should not be a thing, we have to pay some attention to how MSG_ITEMS are handled
Use a callback for NET_EPOCH_CALL for freeing nodes/hooks
Reference counts needed?
Test long broken chains?
Does a node need to pay special attention to ghost data?
Just use the generalized CK_LIST iterator for other node types
Sleepable mutexes may be needed

The base system (ng_base.c) should not contain any locks which block data flow
ng_tee, ng_source, ng_echo etc. (simplest node types) should work in any complex graph

The test scripts which construct and control graphs should be reasonably complex to cover the cases of interest.

29 May: Coding period begins
- Should probably build kernel with options NETGRAPH
- Write callbacks for safe reclamation (ng_kill_node(), ng_kill_hook())
- NET_EPOCH_ASSERT() where needed
- Remove TOPOLOGY_RLOCKs in ng_address_path and similar routines
- Remove ng_acquire_read()/ng_acquire_write()
- DELIVERABLE: A simple test graph script that runs without panic in face of the above removals
14 July: Mid-term Evaluation
- Handling MSGs
- More complex test scripts
- Testing on real hardware with at least 4 CPUs
- DELIVERABLE: Again, it should just work
28 August: Final Submission