Proposal to an alternative approach to epoch based memory management.

[shankarseal]

The motivation behind the epoch-based memory management was primarily to avoid expensive interlocked operations (due to reference counting) in hot path, e.g., invoking an eBPF program in network data path. Hence, it follows that the epoch-based solution for memory management too must avoid interlocked operations, or acquiring locks for synchronization, at least in the hot path. Another requirement would be to ensure minimal memory retention, i.e. unused memory is freed as soon as possible.

The epoch module in eBPF was introduced at the beginning of the project nearly three years ago. However, it went through several iterations of change. Each iteration improves on efficacy of the component. Throughout the iterations, the main idea of the component remained the same: a piece of memory that is marked for deletion, is freed only when it is certain that all the threads that were running at the time of the delete operations have exited.

The latest proposed changes (PR: #2796) introduces a two phase commit based algorithm, that involves passing messages sequentially from one cpu to the next using DPCs. The approach while eliminates locks, may suffer from stalling inbound network packets that are indicated to the OS using DPCs from the NIC driver, since the approach may frequently queue DPCs on the CPUs.

Here is an alternative approach to the epoch-based memory management that simplifies the process while keeping the main idea of the memory management intact.

1. A global current epoch is maintained.
2. A global table of epoch entry is maintained. Each epoch entry contains the count of the preemptible threads that is running at that epoch.
3. The epoch_enter function reads the current global epoch without acquiring lock. There may be some cost associated with cache miss.
4. Upon epoch_enter:
   1. For preemptible threads, the thread count for the global epoch entry for the current epoch is incremented. If an entry does not exist for the current epoch, one is created. The table may be implemented using eBPF hashtable. The key to the hashtable entries will be the epoch number and the value would be the preemptible thread count. The current epoch will be returned to the caller. Such preemptible threads usually have low performance requirements, and the cost for these operations will have non-discernible overhead.
   2. For non-preemptible threads, the current epoch is stored in a per-cpu state. Usually, such non-preemptible threads have high performance requirements and may and must not use any interlocked / lock operations.
5. Upon epoch_exit:
   1. For preemptible threads, the caller supplies the epoch returned by epoch_enter function. The thread count for the given epoch will be decremented. If the count drops to zero, the entry will be removed from the table.
   2. For non-preemptible threads the per-cpu epoch will be reset to zero.
6. Upon deletion of epoch manager memory, at first the memory is effectively disabled such that no new thread can access it. E.g., in case of map entries, the entries are atomically removed from the map, etc. Then epoch_free is invoked on the memory.
7. The epoch_free function is assumed to be called infrequently and can withstand performing expensive operations. It does the following:
   1. This function increments the global epoch, assigns it to the freed memory and will insert it to a queue of work items that is processed by a worker routine running at passive irql.
   2. The worker routine looks at the global epoch table and per-cpu epochs to decide if it is safe to free the memory. While looking up the per-cpu epoch, no lock is acquired. This may return stale information and delay the freeing of the memory.
   3. The routine to insert the work item also returns the total count of pending items to free. If that number exceeds the current threshold, the epoch_free routine will invoke the worker routine inline after optionally raising the irql.

[Alan-Jowett]

7ii can get a stale version of the per-cpu epoch state can incorrectly see the epoch as inactive when there is a thread executing in it.

[Alan-Jowett]

Counter proposal:

1. Implement a ring-buffer based lock-free / barrier free inter process message queue.
2. On epoch exit, processor will check for messages in the queue and process them.
3. The timer will capture ring-buffer state and compare it to the previous timer firing.
   a) If the state doesn't change from one timer expiry to the next, queue a DPC.
4. Future optimization - Idle out CPUs from the epoch consensus - design is still TBD.

In this model, there will still be a 2-phase commit of the next epoch. The only thing that would change is the mechanism for sending inter-process messages (from DPC -> ring-buffer), with opportunistic processing of messages.

Note:
This is an evolution of the current algorithm, allowing us to proceed with the current PR and improve in it in the future.

[shankarseal]

@Alan-Jowett and I discussed this offline. The below assumption in my original proposal (point number 6) is wrong:
Upon deletion of epoch manager memory, at first the memory is effectively disabled such that _no new thread can access it._

This is not doable without synchronization using locks or memory barriers.

Hence this proposal will not be correct. The counter proposal offered by Alan will be considered as a performance optimization.