Lock-less Synchronization For Netgraph
Student: Zain Khan (zain@freebsd.org)
Mentors: Gleb Smirnoff (glebius@freebsd.org), Alexander Chernikov (melifaro@freebsd.org)
Overview
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).
Problem Statement + Scope
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.
Solution
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.
Notes/Methods
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
Deliverables
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
Testing
The test scripts which construct and control graphs should be reasonably complex to cover the cases of interest.
Dates and Milestones
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