Lock-less Synchronization For Netgraph


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.


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.




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

Dates and Milestones

Github Repo


SummerOfCode2023Projects/LocklessSynchronizationBetweenNodesInNetgraph (last edited 2023-07-19T22:59:22+0000 by ZainKhan)