This captures some considerations and design decisions that I have made, both for my own memory later on ("what the hell was I thinking?!?"), and for anyone interested to criticize/improve/hack on this code.

One of the factors taken into account while making these decisions, was the relative emphasis on the multi-thread vs. single-thread use cases: the latter is the vastly more prevalent. But, one can not optimize the single-thread performance without having a functioning code for multi-thread.

stateless ACLs

The stateless trivially parallelizes, and the only potential for the race between the different threads is during the reconfiguration, at the time of replacing the old ACL being checked, with the new ACL.

In case an acl_add_replace is being used to replace the rules within the existing entry, a reallocation of am->acls[X].rules vector will happen and potentially a change in count.

acl_match_5tuple() has the following code:

a = am->acls + acl_index;
for (i = 0; i < a->count; i++)
  {
    r = a->rules + i;
   . . .

Ideally we should be immune from a->rules changing, but the problem arises if the count changes in flight, and the new ruleset is smaller - then we will attempt to "match" against the free memory.

This can(?) be solved by replacing the for() with while(), so the comparison happens at each iteration.

full_acl_match_5tuple(), which iterates over the list of ACLs, is a bit less immune, since it takes the pointer to the vector to iterate and keeps a local copy of that pointer.

This race can be solved by checking the current pointer to the vector with the source pointer, and seeing if there is an (unlikely) change, and if there is, return the "deny" action, or, better, restart the check.

Since the check reloads the ACL list on a per-packet basis, there is only a window of opportunity of one packet to "match" packet against an incorrect rule set. The workers also do not change anything, only read. Therefore, it looks like building special structures to ensure that it does not happen at all might be not worth it.

At least not until we have a unit-test able to reliably catch this condition and test that the measures applied are effective. Adding the code which is not possible to exercise is worse than not adding any code at all.

So, I opt for "do-nothing" here for the moment.

reflexive ACLs: single-thread

Before we talk multi-thread, is worth revisiting the design of the reflexive ACLs in the plugin, and the history of their evolution.

The very first version of the ACL plugin, shipped in 1701, mostly did the job using the existing components and gluing them together. Because it needed to work in bridged forwarding path only, using L2 classifier as an insertion point appeared natural, also L2 classifier, being a table with sessions, seemed like a good place to hold the sessions.

So, the original design had two conceptual nodes: one, pointed by the next_miss from the L2 classifier table, was checking the actual ACL, and inserting session into the L2 classifier table, and the other one, pointed to by the next_match within the specific session rule, was checking the existing session. The timing out of the existing connections was done in the datapath, by periodically calling the aging function.

This decision to use the existing components, with its attrativeness, did bring a few limitations as well:

L2 classifier is a simple mask-and-value match, with a fixed mask across the table. So, sanely supporting IPv6 packets with extension headers in that framework was impossible.
There is no way to get a backpressure from L2 classifier depending on memory usage. When it runs out of memory, it simply crashes the box. When it runs out of memory ? We don't really know. Depends on how it allocates it.
Since we need to match the reflected traffic, we had to create two full session entries in two different directions, which is quite wasteful memory-wise.
(showstopper): the L2 classifier runs only in the bridged data path, so supporting routed data path would require creating something else entirely different, which would mean much more headaches support-wise going forward.

Because of that, I have moved to a different model of creating a session-5-tuple from the packet data - once, and then doing all the matching just on that 5-tuple.

This has allowed to add support for skipping IPv6 extension headers.

Also, this new version started to store the sessions in a dedicated bihash-per-interface, with the session key data being aligned for the ingress packets, and being mirrored for the egress packets. This allows of significant savings in memory, because now we need to keep only one copy of the session table per interface instead of two, and also to only have ONE node for all the lookups, (L2/L3 path, in/out, IPv4/IPv6) - significantly reducing the code complexity.

Unfortunately, bihash still has the "lack of backpressure" problem, in a sense that if you try to insert too many entries and run out of memory in the heap you supplied, you get a crash.

To somewhat workaround against that, there is a "maximum tested number of sessions" value, which tracks the currently inserted sessions in the bihash, and if this number is being approached, a more aggressive cleanup can happen. If this number is reached, two behaviors are possible:

attempt to do the stateless ACL matching and permit the packet if it succeeds
deny the packet

Currently I have opted for a second one, since it allows for a better defined behavior, and if you have to permit the traffic in both directions, why using stateful anyway ?

In order to be able to do the cleanup, we need to discriminate between the session types, with each session type having its own idle timeout. In order to do that, we keep three lists, defined in enum acl_timeout_e: ACL_TIMEOUT_UDP_IDLE, ACL_TIMEOUT_TCP_IDLE, ACL_TIMEOUT_TCP_TRANSIENT.

The first one is hopefully obvious - it is just all UDP connections. They have an idle timeout of 600 seconds.

The second and third is a bit more subtle. TCP is a complicated protocol, and we need to tread the fine line between doing too little and doing too much, and triggering the potential compatibility issues because of being a "middlebox".

I decided to split the TCP connections into two classes: established, and everything else. "Established", means we have seen the SYN and ACK from both sides (with PUSH obviously masked out). This is the "active" state of any TCP connection and we would like to ensure we do not screw it up. So, the connections in this state have the default idle timer of 24 hours.

All the rest of the connections have the idle timeout of 2 minutes, (inspired by an old value of MSL) and based on the observation that the states this class represent are usually very short lived.

Once we have these three baskets of connections, it is trivial to imagine a simple cleanup mechanism to deal with this: take a TCP transient connection that has been hanging around.

It is debatable whether we want to do discrimination between the different TCP transient connections. Assuming we do FIFO (and the lists allow us to do just that), it means a given connection on the head of the list has been hanging around for longest. Thus, if we are short on resources, we might just go ahead and reuse it within the datapath.

This is where we are slowly approaching the question "Why in the world have not you used timer wheel or such ?"

The answer is simple: within the above constraints, it does not buy me much.

Also, timer wheel creates a leaky abstraction with a difficult to manage corner case. Which corner case ?

We have a set of objects (sessions) with an event that may or may not happen (idle timeout timer firing), and a necessity to reset the idle timeout when there is activity on the session.

In the worst case, where we had a 10000 of one-packet UDP sessions just created 10 minutes ago, we would need to deal with a spike of 10000 expired timers.

Of course, if we have the active traffic on all of these 10000 connections, then we will not have to deal with that ? Right, but we will still have to deal with canceling and requeueing the timers.

In the best possible case, requeueing a timer is going to be something along the lines of a linked-list removal and reinsertion.

However, keep in mind we already need to classify the connections for reuse, so therefore we already have the linked lists!

And if we just check these linked lists periodically in a FIFO fashion, we can get away with a very simple per-packet operation: writing back the timestamp of "now" into the connection structure.

Then rather than requeueing the list on a per-packet or per-frame basis, we can defer this action until the time this session appears on the head of the FIFO list, and the cleaning routine makes the decision about whether to discard the session (because the interval since last activity is bigger than the idle timeout), or to requeue the session back to the end of the list (because the last activity was less than idle timeout ago).

So, rather than using the timers, we can simply reuse our classification FIFOs, with the following heuristic: do not look at the session that was enqueued at time X until X+session_timeout. If we enqueue the sessions in the order of their initial activity, then we can simply use enqueue timestamp of the head session as a decision criterion for when we need to get back at looking at it for the timeout purposes.

Since the number of FIFOs is small, we get a slightly worse check performance than with timers, but still O(1).

We seemingly do quite a few "useless" operations of requeueing the items back to the tail of the list - but, these are the operations we do not have to do in the active data path, so overall it is a win.

(Diversion: I believe this problem is congruent to poll vs. epoll or events vs. threads, some reading on this subject: http://web.archive.org/web/20120225022154/http://sheddingbikes.com/posts/1280829388.html)

We can also can run a TCP-like scheme for adaptively changing the wait period in the routine that deals with the connection timeouts: we can attempt to check the connections a couple of times per second (same as we would advance the timer wheel), and then if we have requeued close to a max-per-quantum number of connections, we can half the waiting interval, and if we did not requeue any, we can slowly increment the waiting interval - which at a steady state should stabilize similar to what the TCP rate does.

reflexive ACLs: multi-thread

The single-threaded implementation in 1704 used a separate "cleaner" process to deal with the timing out of the connections. It is all good and great when you know that there is only a single core to run everything on, but the existence of the lists proves to be a massive difficulty when it comes to operating from multiple threads.

Initial study shows that with a few assumptions (e.g. that the cleaner running in main thread and the worker have a demarcation point in time where either one or the other one touches the session in the list) it might be possible to make it work, but the resulting trickiness of doing it neatly with all the corner cases is quite large.

So, for the multi-threaded scenario, we need to move the connection aging back to the same CPU as its creation.

Luckily we can do this with the help of the interrupts.

So, the design is as follows: the aging thread (acl_fa_session_cleaner_process) periodically fires the interrupts to the workers interrupt nodes (acl_fa_worker_session_cleaner_process_node.index), using vlib_node_set_interrupt_pending(), and the interrupt node acl_fa_worker_conn_cleaner_process() calls acl_fa_check_idle_sessions() which does the actual job of advancing the lists. And within the actual datapath the only thing we will be doing is putting the items onto FIFO, and updating the last active time on the existing connection.

The one "delicate" part is that the worker for one leg of the connection might be different from the worker of another leg of the connection - but, even if the "owner" tries to free the connection, nothing terrible can happen - worst case the element of the pool (which is nominally free for a short period) will get the timestamp updated - same thing about the TCP flags seen.

A slightly trickier issue arises when the packet initially seen by one worker (thus owned by that worker), and the return packet processed by another worker, and as a result changes the the class of the connection (e.g. becomes TCP_ESTABLISHED from TCP_TRANSIENT or vice versa). If the class changes from one with the shorter idle time to the one with the longer idle time, then unless we are in the starvation mode where the transient connections are recycled, we can simply do nothing and let the normal requeue mechanism kick in. If the class changes from the longer idle timer to the shorter idle timer, then we risk keeping the connection around for longer than needed, which will affect the resource usage.

One solution to that is to have NxN ring buffers (where N is the number of workers), such that the non-owner can signal to the owner the connection# that needs to be requeued out of order.

A simpler solution though, is to ensure that each FIFO's period is equal to that of a shortest timer. This way the resource starvation problem is taken care of, at an expense of some additional work.

This all looks sufficiently nice and simple until a skeleton falls out of the closet: sometimes we want to clean the connections en masse before they expire.

There few potential scenarios: 1) removal of an ACL from the interface 2) removal of an interface 3) manual action of an operator (in the future).

In order to tackle this, we need to modify the logic which decides whether to requeue the connection on the end of the list, or to delete it due to idle timeout:

We define a point in time, and have each worker thread fast-forward through its FIFO, in the process looking for sessions that satisfy the criteria, and either keeping them or requeueing them.

To keep the ease of appearance to the outside world, we still process this as an event within the connection cleaner thread, but this event handler does as follows: 1) it creates the bitmap of the sw_if_index values requested to be cleared 2) for each worker, it waits to ensure there is no cleanup operation in progress (and if there is one, it waits), and then makes a copy of the bitmap, sets the per-worker flag of a cleanup operation, and sends an interrupt. 3) wait until all cleanup operations have completed.

Within the worker interrupt node, we check if the "cleanup in progress" is set, and if it is, we check the "fast forward time" value. If unset, we initialize it to value now, and compare the requested bitmap of sw_if_index values (pending_clear_sw_if_index_bitmap) with the bitmap of sw_if_index that this worker deals with.

(we set the bit in the bitmap every time we enqueue the packet onto a FIFO - serviced_sw_if_index_bitmap in acl_fa_conn_list_add_session).

If the result of this AND operation is zero - then we can clear the flag of cleanup in progress and return. Else we kick off the quantum of cleanup, and make sure we get another interrupt ASAP if that cleanup operation returns non-zero, meaning there is more work to do. When that operation returns zero, everything has been processed, we can clear the "cleanup-in-progress" flag, and zeroize the bitmap of sw_if_index-es requested to be cleaned.

The interrupt node signals its wish to receive an interrupt ASAP by setting interrupt_is_needed flag within the per-worker structure. The main thread, while waiting for the cleanup operation to complete, checks if there is a request for interrupt, and if there is - it sends one.

This approach gives us a way to mass-clean the connections which is reusing the code of the regular idle connection cleanup.

One potential inefficiency is the bitmap values set by the session insertion in the data path - there is nothing to clear them.

So, if one rearranges the interface placement with the workers, then the cleanups will cause some unnecessary work. For now, we consider it an acceptable limitation. It can be resolved by having another per-worker bitmap, which, when set, would trigger the cleanup of the bits in the serviced_sw_if_index_bitmap).

=== the end ===