Links:
Wiki Page URL: https://wiki.freebsd.org/SummerOfCode2023Projects/LocklessSynchronizationBetweenNodesInNetgraph
Repo URL: https://github.com/zinh88/epoch-netgraph

Contact: Zain Khan <zain@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.

Because the base system is being modified, this is also going to affect the design choices made before, such as queuing on messages, reference counting.

This project involves a lot of testing. For now, some topology protection locks have been removed, and only simple graphs have been tested (with FreeBSD running on a VM). The real tests should be run on hardware with at least 4 CPU cores, I will do that when I get my hands on one.

Sponsor: The Google Summer of Code '23 program