Pesto protocol proposals

[David Gibson <david@gibson.dropbear.id.au>]

[-- Attachment #1: Type: text/plain, Size: 8554 bytes --]

Most of today and yesterday I've spent thinking about the dynamic
update model and protocol.  I certainly don't have all the details
pinned down, let alone any implementation, but I have come to some
conclusions.

# Shadow forward table

On further consideration, I think this is a bad idea.  To avoid peer
visible disruption, we don't want to destroy and recreate listening
sockets that are associated with a forward rule that's not being
altered.

Doing that with a shadow table would mean we'd need to essentially
diff the two tables as we switch.  That seems moderately complex, and
kind of silly when then client almost certainly have created the
shadow table using specific adds/removes from the original table.

# Rule states / active bit

I think we *do* still want two stage activation of new rules: if the
first stage fails we're guaranteed we can roll back with no peer
visible consequences.  The second stage (the actual bind()s and
listen()s) doesn't have that property, but that's unavoidable.

To implement that, I think each rule should have an "active" bit.  Or,
at least an active bit - it's possible that might not be enough, but
we could extend it to a state field, loosely analagous to the state
field in flow table entries.  But let's assume just the active bit,
until/unless a case shows up where it's insufficient.

Entries are always inserted in inactive state.  Entries must be moved
to inactive state before deletion.  fwd_listen_sync() would ignore
inactive entries.  Turning the active flag on triggers the actual
bind() / listen() calls, but requires no rearrangement of the fwd
table or socket array.  Turning it off close()s the associated
sockets, but again requires no rearrangement of the data structures.

# Tentative client operations

## INSERT
  Parameters: rule specification + rule index
  Returns: error status

Inserts the new rule (inactive) at the given index (moving later
rules, if necessary).

Fails with no effect, for a bad index or if there's no room in the
table or socket array.  Does *not* check for conflicts with other
rules.

NOTE: moving rules could mean thousands of epoll_ctl() calls to
      adjust rule indices.  We don't expect those to fail, but if they
      did, what do we do?

## DELETE
  Parameters: rule index
  Returns: error status

Deletes the given inactive rule (moving later rules, if necessary).

Fails with no effect if it's a bad index, or the given rule is active.

NOTE: As for INSERT

## ACTIVATE
  Parameters: rule index
  Returns: error status

Enables the rule, bind()ing all the necessary listening sockets.

Fails with no effect if the rule conflicts with another active rule.

Completes, even if some bind()s fail (see later for handling of this).

## DEACTIVATE
  Parameters: rule index
  Returns: error status

Disables the rule, close()ing any listening sockets.

Fails with no effect for bad index or an already inactive rule.

## STATUS
  Parameters: rule index
  Returns: active/inactive bit + possible metadata

Indicates whether the rule is currently active.  Could also give
limited metadata about the rule (see below for possible use in bind()
error reporting).

## READ
  Parameters: rule index
  Returns: rule specification, or error code

Reads out the rule spec and returns it.

Fails for bad index.

To dump the whole table, the client can READ each slot starting from
0, until it gets an error.

# Suggested client workflow

I suggest the client should:

   1. Parse all rule modifications
   2. INSERT all new rules
      -> On error, DELETE them again
   3. DEACTIVATE all removed rules
      -> Should only fail if the client has done something wrong
   4. ACTIVATE all new rules
      -> On error (rule conflict):
         DEACTIVATE rules we already ACTIVATEd
	 ACTIVATE rules we already DEACTIVATEd
	 DELETE rules we INSERTed
   5. Check for bind errors (see details later)
      If there are failures we can't tolerate:
         DEACTIVATE rules we already ACTIVATEd
	 ACTIVATE rules we already DEACTIVATEd
	 DELETE rules we INSERTed
   6. DELETE rules we DEACTIVATEd
      -> Should only fail if the client has done something wrong

DEACTIVATE comes before ACTIVATE to avoid spurious conflicts between
new rules and rules we're deleting.

I think that gets us closeish to "as atomic as we can be", at least
from the perspective of peers.  The main case it doesn't catch is that
we don't detect rule conflicts until after we might have removed some
rules.  Is that good enough?

# Bind error handling

Note, in the below I'm considering pasta/passt's command line handling
and conf path as a client rather than part of the backend.

The distinction weak and non-weak entries is a bit clunky.  How many
failures is too many is kind of a question for the client, not the
backend.  So I'm suggesting we remove that concept from the backend.
ACTIVATE completes even if some or all binds fail.  However, we keep a
count of how many sockets we got a bind() or listen() failure for in
the rule, and it can be retrieved with STATUS.  That lets the client
make a decision as to whether to live with it or roll back as best it
can.  A client could also potentially poll later to see if some
failures resolved themselves (we now reattempt bind()s on every
fwd_listen_sync()).

NOTE: the meaning of that count is pretty straightforward with regular
rules, but with SCAN rules, we'd have to be more careful.

# Concurrent updates

I suggest we prevent concurrent updates by only allowing one client to
connect to the control socket at a time.

# Possible tweaks

Not sure if these are improvements or not, but they're options to
consider.

## Rule conflicts

Currently fwd_rule_add() checks for rules with conflicts and rejects
them.  We can't really report that at INSERT, because we could get a
bogus conflict with a rule we intend to DEACTIVATE/DELETE.  But
reporting at ACTIVATE is also a bit clunky.

This could potentially be sidestepped by removing the notion of rule
conflicts entirely.  Instead overlapping rules are simply allowed, and
the first rule to match a flow wins.

## Rollback in backend

The proposal above has rollback essentially handled by the client.  We
could instead do it in the backend.
  - Instead of a single active bit, each rule has an "active now" and
    "active future" bit
  - On client connect, all active future bits are set equal to active
    now bits
  - INSERT adds a rule with active now false and active future true
     - If we conflict check, we check only against active future rules
  - DELETE clears the active future bit
  - ACTIVATE/DEACTIVATE no longer exist
  - ROLLBACK deletes all !active now rules and sets active future bits
    to active now bits again
  - COMMIT does the bind()s and close()s and on success, sets active
    now bits to active future bits.  On failure... it's fairly
    complex, we'd need to think about it

## Persistent rule IDs

Proposal above uses raw indices in the table to identify rules, which
means INSERT and DELETE change the numbers of other rules.  That in
turn requires a bunch of epoll_ctl()s to update existing sockets.

Here's one way we could avoid some of that with a persistent rule ID:
  - Each rule has an ID (say a u32), supplied by the client at INSERT
  - Rules still apply in ID order, so the order matters, but not the
    exact values
  - INSERT to an existing rule ID is not permitted - you must DELETE
    first

Internally we still store the table packed, but sorted by ID.  We
could look up rule by ID either with a binary search, or maybe a radix
lookup table.  If we reduced the ID to a u16 (or so) we could
potentially use a single level lookup table.  I suspect binary search
might be faster than a lookup table anyway, because of dcache impact.

So, we still to memmove() things about for INSERT, and maybe update
the lookup table, but that's relatively easy.  epoll data holds the
persistent ID, so that doesn't need to be altered.

Clients (including the internal conf path) could choose to leave gaps
in the IDs to leave space for future inserts.  And/or certain ranges
could be reserved by convention for different purposes.

-- 
David Gibson (he or they)	| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you, not the other way
				| around.
http://www.ozlabs.org/~dgibson

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]