Switch to random allocation on circuitIDs.

Fixes a possible root cause of 11553 by only making 64 attempts at
most to pick a circuitID.  Previously, we would test every possible
circuit ID until we found one or ran out.

This algorithm succeeds probabilistically. As the comment says:

  This potentially causes us to give up early if our circuit ID
  space is nearly full.  If we have N circuit IDs in use, then we
  will reject a new circuit with probability (N / max_range) ^
  MAX_CIRCID_ATTEMPTS.  This means that in practice, a few percent
  of our circuit ID capacity will go unused.

  The alternative here, though, is to do a linear search over the
  whole circuit ID space every time we extend a circuit, which is
  not so great either.

This makes new vs old clients distinguishable, so we should try to
batch it with other patches that do that, like 11438.

1 files changed, 10 insertions, 0 deletions

diff --git a/changes/bug11553 b/changes/bug11553
index 1540f4642f..ed30ce9850 100644
--- a/changes/bug11553
+++ b/changes/bug11553
@@ -3,3 +3,13 @@
       warning for the whole channel, and include a description of
       how many circuits there were on the channel. Fix for part of ticket
       #11553.
+
+
+  o Major features (performance):
+    - Avoid wasting cycles looking for usable circuit IDs. Previously,
+      when allocating a new circuit ID, we would in the worst case do a
+      linear scan over the entire possible range of circuit IDs before
+      deciding that we had exhausted our possibilities. Now, we
+      try 64 circuit IDs at random before deciding that we probably
+      won't succeed. Fix for a possible root cause of ticket
+      #11553.