Details

Reviewers

lev
kp

Group Reviewers

network

Commits

rG1883127de488: libalias: Switch to SPLAY trees
rG3a96a25da861: libalias: Switch to SPLAY trees
rG935fc93af157: libalias: Switch to efficient data structure for outgoing traffic

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

rS FreeBSD src repository - subversion

Lint

Lint Passed

Unit

No Test Coverage

Build Status

Buildable 39548
Build 36437: arc lint + arc unit

Event Timeline

donner created this revision.May 27 2021, 10:42 PM

Herald added subscribers: melifaro, imp. · View Herald TranscriptMay 27 2021, 10:42 PM

donner requested review of this revision.May 27 2021, 10:42 PM

Harbormaster completed remote builds in B39523: Diff 90031.May 27 2021, 10:42 PM

donner added a reviewer: network.May 27 2021, 10:48 PM

donner edited the test plan for this revision. (Show Details)May 27 2021, 11:03 PM

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

rebase to a buf fixed parent review

Harbormaster completed remote builds in B39538: Diff 90059.May 28 2021, 2:38 PM

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.

Rebase to parent

Harbormaster completed remote builds in B39548: Diff 90075.May 28 2021, 7:09 PM

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

Harbormaster completed remote builds in B39552: Diff 90087.May 28 2021, 9:01 PM

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.

donner edited parent revisions, added: D30582: libalias: Restructure - Finalize; removed: D30283: libalias: Restructure searching.May 31 2021, 4:56 PM