Page MenuHomeFreeBSD

libalias: Switch to efficient data structure for outgoing traffic
ClosedPublic

Authored by donner on May 27 2021, 10:42 PM.

Details

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

Diff Detail

Repository
R10 FreeBSD src repository
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

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

donner edited the test plan for this revision. (Show Details)

rebase to a buf fixed parent review

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.

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

Rebase and rename splayTableOut to linkSplayOut, remove hashsize

donner retitled this revision from libalias: Switch to efficient data structure to libalias: Switch to efficient data structure for outgoing traffic.May 28 2021, 9:02 PM
donner added a reviewer: kp.
This revision was not accepted when it landed; it landed in state Needs Review.Jun 19 2021, 8:10 PM
This revision was automatically updated to reflect the committed changes.