Adding upstream version 2.6.7+dfsg.upstream/2.6.7+dfsg

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 282 insertions, 0 deletions

diff --git a/doc/devel/lloadd/design.md b/doc/devel/lloadd/design.md
new file mode 100644
index 0000000..62fcd88
--- /dev/null
+++ b/doc/devel/lloadd/design.md
@@ -0,0 +1,282 @@
+TODO:
+- [ ] keep a global op in-flight counter? (might need locking)
+- [-] scheduling (who does what, more than one select thread? How does the proxy
+      work get distributed between threads?)
+- [ ] managing timeouts?
+- [X] outline locking policy: seems like there might be a lock inversion in the
+      design looming: when working with op, might need a lock on both client and
+      upstream but depending on where we started, we might want to start with
+      locking one, then other
+- [ ] how to deal with the balancer running out of fds? Especially when we hit
+      the limit, then lose an upstream connection and accept() a client, we
+      wouldn't be able to initiate a new one. A bit of a DoS... But probably not
+      a concern for Ericsson
+- [ ] non-Linux? No idea how anything other than poll works (moot if building a
+      libevent/libuv-based load balancer since they take care of that, except
+      edge-triggered I/O?)
+- [-] rootDSE? Controls and exops might have different semantics and need
+      binding to the same upstream connection.
+- [ ] Just piggybacking on OpenLDAP as a module? Would still need some updates
+      in the core and the module/subsystem would be a very invasive one. On the
+      other hand, allows to expose live configuration and monitoring over LDAP
+      over the current slapd listeners without re-inventing the wheel.
+
+
+Expecting to handle only LDAPv3
+
+terms:
+  server - configured target
+  upstream - a single connection to a server
+  client - an incoming connection
+
+To maintain fairness `G( requested => ( F( progressed | failed ) ) )`, use
+queues and put timeouts in
+
+Runtime organisation
+------
+- main thread with its own event base handling signals
+- one thread (later possibly more) listening on the rendezvous sockets, handing
+  the new sockets to worker threads
+- n worker threads dealing with client and server I/O (dispatching actual work
+  to the thread pool most likely)
+- a thread pool to handle actual work
+
+Operational behaviour
+------
+
+- client read -> upstream write:
+  - client read:
+    - if TLS_SETUP, keep processing, set state back when finished and note that
+      we're under TLS
+    - ber_get_next(), if we don't have a tag, finished (unless we have true
+      edge-triggered I/O, also put the fd back into the ones we're waiting for)
+    - peek at op tag:
+      - unbind:
+        - with a single lock, mark all pending ops in upstreams abandoned, clear
+          client link (would it be fast enough if we remove them from upstream
+          map instead?)
+        - locked per op:
+          - remove op from upstream map
+          - check upstream is not write-suspended, if it is ...
+          - try to write the abandon op to upstream, suspend upstream if not
+            fully sent
+          - remove op from client map (how if we're in avl_apply?, another pass?)
+        - would be nice if we could wipe the complete client map then, otherwise
+          we need to queue it to have it freed when all abandons get passed onto
+          the upstream (just dropping them might put extra strain on upstreams,
+          will probably have a queue on each client/upstream anyway, not just a
+          single Ber)
+      - bind:
+        - check mechanism is not EXTERNAL (or implement it)
+        - abandon existing ops (see unbind)
+        - set state to BINDING, put DN into authzid
+        - pick upstream, create PDU and sent
+      - abandon:
+        - find op, mark for abandon, send to appropriate upstream
+      - Exop:
+        - check not BINDING (unless it's a cancel?)
+        - check OID:
+          - STARTTLS:
+            - check we don't have TLS yet
+            - abandon all
+            - set state to TLS_SETUP
+            - send the hello
+          - VC(?):
+            - similar to bind except for the abandons/state change
+      - other:
+        - check not BINDING
+        - pick an upstream
+        - create a PDU, send (marking upstream suspended if not written in full)
+      - check if should read again (keep a counter of number of times to read
+        off a connection in a single pass so that we maintain fairness)
+      - if read enough requests and can still read, re-queue ourselves (if we
+        don't have true edge-triggered I/O, we can just register the fd again)
+  - upstream write (only when suspended):
+    - flush the current BER
+    - there shouldn't be anything else?
+- upstream read -> client write:
+  - upstream read:
+    - ber_get_next(), if we don't have a tag, finished (unless we have true
+      edge-triggered I/O, also put the fd back into the ones we're waiting for)
+    - when we get it, peek at msgid, resolve client connection, lock, check:
+      - if unsolicited, handle as close (and mark connection closing)
+      - if op is abandoned or does not exist, drop PDU and op, update counters
+      - if client backlogged, suspend upstream, register callback to unsuspend
+        (on progress when writing to client or abandon from client (connection
+        death, abandon proper, ...))
+    - reconstruct final PDU, write BER to client, if did not write fully,
+      suspend client
+    - if a final response, decrement operation counts on upstream and client
+    - check if should read again (keep a counter of number of responses to read
+      off a connection in a single pass so that we don't starve any?)
+  - client write ready (only checked for when suspended):
+    - write the rest of pending BER if any
+    - on successful write, pick all pending ops that need failure response, push
+      to client (are there any controls that need to be present in response even
+      in the case of failure?, what to do with them?)
+    - on successfully flushing them, walk through suspended upstreams, picking
+      the pending PDU (unsuspending the upstream) and writing, if PDU flushed
+      successfully, pick next upstream
+    - if we successfully flushed all suspended upstreams, unsuspend client
+      (and disable the write callback)
+- upstream close/error:
+  - look up pending ops, try to write to clients, mark clients suspended that
+    have ops that need responses (another queue associated with client to speed
+    up?)
+  - schedule a new connection open
+- client close/error:
+  - same as unbind
+- client inactive (no pending ops and nothing happened in x seconds)
+  - might just send notice of disconnection and close
+- op timeout handling:
+  - mark for abandon
+  - send abandon
+  - send timeLimitExceeded/adminLimitExceeded to client
+
+Picking an upstream:
+- while there is a level available:
+  - pick a random ordering of upstreams based on weights
+  - while there is an upstream in the level:
+    - check number of ops in-flight (this is where we lock the upstream map)
+    - find the least busy connection (and check if a new connection should be
+      opened)
+    - try to lock for socket write, if available (no BER queued) we have our
+      upstream
+
+PDU processing:
+- request (have an upstream selected):
+  - get new msgid from upstream
+  - create an Op structure (actually, with the need for freelist lock, we can
+    make it a cache for freed operation structures, avoiding some malloc
+    traffic, to reset, we need slap_sl_mem_create( ,,, 1 ))
+  - check proxyauthz is not present? or just let upstream reject it if there are
+    two?
+  - add own controls at the end:
+    - construct proxyauthz from authzid
+    - construct session tracking from remote IP, own name, authzid
+  - send over
+  - insert Op into client and upstream maps
+- response/intermediate/entry:
+  - look up Op in upstream's map
+  - write old msgid, rest of the response can go unchanged
+  - if a response, remove Op from all maps (client and upstream)
+
+Managing upstreams:
+- async connect up to min_connections (is there a point in having a connection
+  count range if we can't use it when needed since all of the below is async?)
+- when connected, set up TLS (if requested)
+- when done, send a bind
+- go for the bind interaction
+- when done, add it to the upstream's connection list
+- (if a connection is suspended or connections are over 75 % op limit, schedule
+  creating a new connection setup unless connection limit has been hit)
+
+Managing timeouts:
+- two options:
+  - maintain a separate locked priority queue to give a perfect ordering to when
+    each operation is to time out, would need to maintain yet another place
+    where operations can be found.
+    - the locking protocol for disposing of the operation would need to be
+      adjusted and might become even more complicated, might do the alternative
+      initially and then attempt this if it helps performance
+  - just do a sweep over all clients (that mutex is less contended) every so
+    often. With many in-flight operations might be a lot of wasted work.
+    - we still need to sweep over all clients to check if they should be killed
+      anyway
+
+Dispatcher thread (2^n of them, fd x is handled by thread no x % (2^n)):
+- poll on all registered fds
+- remove each fd that's ready from the registered list and schedule the work
+- work threads can put their fd back in if they deem necessary (=not suspended)
+- this works as a poor man's edge-triggered polling, with enough workers, should
+  we do proper edge triggered I/O? What about non-Linux?
+
+Listener thread:
+- slapd has just one, which then reassigns the sockets to separate I/O
+  threads
+
+Threading:
+- if using slap_sl_malloc, how much perf do we gain? To allocate a context per
+  op, we should have a dedicated parent context so that when we free it, we can
+  use that exclusively. The parent context's parent would be the main thread's
+  context. This implies a lot of slap_sl_mem_setctx/slap_sl_mem_create( ,,, 0 )
+  and making sure an op does not allocate/free things from two threads at the
+  same time (might need an Op mutex after all? Not such a huge cost if we
+  routinely reuse Op structures)
+
+Locking policy:
+- read mutexes are unnecessary, we only have one thread receiving data from the
+  connection - the one started from the dispatcher
+- two reference counters of operation structures (an op is accessible from
+  client and upstream map, each counter is consistent when thread has a lock on
+  corresponding map), when decreasing the counter to zero, start freeing
+  procedure
+- place to mark disposal finished for each side, consistency enforced by holding
+  the freelist lock when reading/manipulating
+- when op is created, we already have a write lock on upstream socket and map,
+  start writing, insert to upstream map with upstream refcount 1, unlock, lock
+  client, insert (client refcount 0), unlock, lock upstream, decrement refcount
+  (triggers a test if we need to drop it now), unlock upstream, done
+- when upstream processes a PDU, locks its map, increments counter, (potentially
+  removes if it's a response), unlocks, locks client's map, write mutex (this
+  order?) and full client mutex (if a bind response)
+- when client side wants to work with a PDU (abandon, (un)bind), locks its map,
+  increase refcount, unlocks, locks upstream map, write mutex, sends or queues
+  abandon, unlocks write mutex, initiates freeing procedure from upstream side
+  (or if having to remember we've already increased client-side refcount, mark
+  for deletion, lose upstream lock, lock client, decref, either triggering
+  deletion from client or mark for it)
+- if we have operation lock, we can simplify a bit (no need for three-stage
+  locking above)
+
+Shutdown:
+- stop accept() thread(s) - potentially add a channel to hand these listening
+  sockets over for zero-downtime restart
+- if very gentle, mark connections as closing, start timeout and:
+  - when a new non-abandon PDU comes in from client - return LDAP_UNAVAILABLE
+  - when receiving a PDU from upstream, send over to client, if no ops pending,
+    send unsolicited response and close (RFC4511 suggests unsolicited response
+    is the last PDU coming from the upstream and libldap agrees, so we can't
+    send it for a socket we want to shut down more gracefully)
+- gentle (or very gentle timed out):
+  - set timeout
+  - mark all ops as abandoned
+  - send unbind to all upstreams
+  - send unsolicited to all clients
+- imminent (or gentle timed out):
+  - async close all connections?
+  - exit()
+
+RootDSE:
+- default option is not to care and if a control/exop has special restrictions,
+  it is the admin's job to flag it as such in the load-balancer's config
+- another is not to care about the search request but check each search entry
+  being passed back, check DN and if it's a rootDSE, filter the list of
+  controls/exops/sasl mechs (external!) that are supported
+- last one is to check all search requests for the DN/scope and synthesise the
+  response locally - probably not (would need to configure the complete list of
+  controls, exops, sasl mechs, naming contexts in the balancer)
+
+Potential red flags:
+- we suspend upstreams, if we ever suspend clients we need to be sure we can't
+  create dependency cycles
+  - is this an issue when only suspending the read side of each? Because even if
+    we stop reading from everything, we should eventually flush data to those we
+    can still talk to, as upstreams are flushed, we can start sending new
+    requests from live clients (those that are suspended are due to their own
+    inability to accept data)
+  - we might need to suspend a client if there is a reason to choose a
+    particular upstream (multi-request operation - bind, VC, PR, TXN, ...)
+    - a SASL bind, but that means there are no outstanding ops to receive
+      it holds that !suspended(client) \or !suspended(upstream), so they
+      cannot participate in a cycle
+    - VC - multiple binds at the same time - !!! more analysis needed
+    - PR - should only be able to have one per connection (that's a problem
+      for later, maybe even needs a dedicated upstream connection)
+    - TXN - ??? probably same situation as PR
+  - or if we have a queue for pending Bers on the server, we not need to suspend
+    clients, upstream is only chosen if the queue is free or there is a reason
+    to send it to that particular upstream (multi-stage bind/VC, PR, ...), but
+    that still makes it possible for a client to exhaust all our memory by
+    sending requests (VC or other ones bound to a slow upstream or by not
+    reading the responses at all)