libalias: Switch to efficient data structure for outgoing traffic

[donner]

Summary

Current data structure is using a hash of unordered lists. Those
unordered lists are quite efficient, because the least recently
inserted entries are most likely to used again. In order to avoid
long search times in other cases, the lists are hashed in to many
buckets. Unfortunatly a search for a miss needs an exhaustive
inspection and a careful definition of the hash.

Splay trees offer a similar feature (almost O(1) for access of the
least recently used entries), and amortized O(ln(n)) for almost all
other cases. Get rid of the hash.

Depends on D30283

Test Plan

1_instance:1_singleinit  ->  passed  [0.003s]
1_instance:2_destroynull  ->  expected_failure: Code expects valid pointer.  [0.014s]
1_instance:3_multiinit  ->  passed  [0.005s]
1_instance:4_multiinstance  ->  passed  [0.031s]
2_natout:1_simplemasq  ->  passed  [0.003s]
2_natout:2_unregistered  ->  passed  [0.003s]
2_natout:3_cgn  ->  passed  [0.003s]
2_natout:4_udp  ->  passed  [0.003s]
2_natout:5_sameport  ->  passed  [0.003s]
2_natout:6_cleartable  ->  passed  [0.003s]
2_natout:7_stress  ->  passed  [0.066s]
3_natin:1_portforward  ->  passed  [0.003s]
3_natin:2_portoverlap  ->  passed  [0.003s]
3_natin:3_redirectany  ->  passed  [0.003s]
3_natin:4_redirectaddr  ->  passed  [0.003s]
3_natin:5_lsnat  ->  passed  [0.003s]
3_natin:6_oneshot  ->  passed  [0.003s]

Running perfomance test with parameters:

Maximum Runtime (max_seconds) = 10
Amount of valid connections (batch_size) = 2000
Amount of random, incoming packets (batch_size) = 1000
Repeat count of a random, incoming packet (attack_size) = 1000
Amount of open port forwardings (redir_size) = 2000

before

  1    0.0   0.59   0.16   0.06   0.11
  2    0.0   0.75   0.15   0.06   0.10
  3    0.0   0.81   0.19   0.05   0.11
  4    0.1   0.96   0.18   0.06   0.11
  5    0.1   1.09   0.19   0.06   0.11
...
146    9.5  48.32   1.98   0.12   0.16
147    9.6  51.12   1.87   0.13   0.16
148    9.7  46.53   1.73   0.13   0.16
149    9.8  46.17   1.84   0.10   0.16
150   10.0
   Rounds  :       149
newNAT ok  :    299649
newNAT fail:         0
useNAT ok  :   2463974 (out)
useNAT fail:         0 (out)
useNAT ok  :  19933275 (in)
useNAT fail:         0 (in)
RANDOM ok  :      1962
RANDOM fail:    147038
ATTACK ok  :         0
ATTACK fail:    149000
             ---------
      Total:  22994898

after

RND SECOND newNAT RANDOM ATTACK useNAT
  1    0.0   0.85   0.15   0.06   0.11
  2    0.0   0.99   0.14   0.05   0.12
  3    0.0   1.13   0.18   0.05   0.11
  4    0.1   1.24   0.20   0.06   0.12
  5    0.1   1.41   0.19   0.06   0.12
...
278    9.9   5.56   2.09   0.12   0.18
279    9.9   6.05   2.21   0.09   0.18
280   10.0   5.46   2.12   0.14   0.17
281   10.0   5.29

Results
   Rounds  :       280
newNAT ok  :    562000
newNAT fail:         0
useNAT ok  :   4607670 (out)
useNAT fail:     20463 (out)
useNAT ok  :  37431023 (in)
useNAT fail:         0 (in)
RANDOM ok  :      3658
RANDOM fail:    276376
ATTACK ok  :         3
ATTACK fail:    279997
             ---------
      Total:  43181190

[donner]

Despite the splay is much faster, it can stall during SPLAY_REMOVE for currently unknown reasons.
100% CPU in an infinite loop.

[donner]

rebase to a buf fixed parent review

[donner]

In D30516#685362, @donner wrote:

Despite the splay is much faster, it can stall during SPLAY_REMOVE for currently unknown reasons.
100% CPU in an infinite loop.

Fixed in parent review. The wrong pointer was freed during a loop.

[donner]

Rebase to parent

[donner]

Running a test for 900 seconds:

7269  899.1  64.66  51.93   0.11   0.20
7270  899.3  61.78  50.91   2.56   0.20
7271  899.5  59.87  49.33   2.87   0.20
7272  899.7  59.21  49.39   3.68   0.20
7273  900.0

Results
   Rounds  :      7272
newNAT ok  :  14545063
newNAT fail:         0
useNAT ok  : 119435373 (out)
useNAT fail:    542017 (out)
useNAT ok  : 970714639 (in)
useNAT fail:         0 (in)
RANDOM ok  :     96612
RANDOM fail:   7175388
ATTACK ok  :       107
ATTACK fail:   7271893
             ---------
      Total: 1119781092

  Cleanup  : 21.06s

[donner]

Rebase and rename splayTableOut to linkSplayOut, remove hashsize

[donner]

Rebase

[donner]

rebase