====== Lock-less Synchronization For Netgraph ======
  * Student: Zain Khan (zain@freebsd.org)
  * Mentors: Gleb Smirnoff (glebius@freebsd.org), Alexander Chernikov (melifaro@freebsd.org)

===== Overview =====
[[https://man.freebsd.org/cgi/man.cgi?netgraph(4)|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 [[https://man.freebsd.org/cgi/man.cgi?query=epoch&sektion=9&format=html|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_RLOCK%%''s 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

===== Github Repo =====
https://github.com/zinh88/epoch-netgraph/tree/main