]> CyberLeo.Net >> Repos - FreeBSD/FreeBSD.git/commit
libalias: Switch to SPLAY trees
authorLutz Donnerhacke <donner@FreeBSD.org>
Thu, 27 May 2021 21:42:54 +0000 (23:42 +0200)
committerLutz Donnerhacke <donner@FreeBSD.org>
Tue, 6 Jul 2021 07:10:02 +0000 (09:10 +0200)
commit1883127de4888b2a30a6cb51e8fb4bdf33b7f411
treef2df940b587354970b7266db38efc0ca431d82d5
parente0a40dc227718f4bc62f279073baa5b6b2cd6a57
libalias: Switch to SPLAY trees

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 be used again.  In order to avoid
long search times in other cases, the lists are hashed into 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.

Now the data structure should able to quickly react to external
packets without eating CPU cycles for breakfast, preventing a DoS.

PR: 192888
Discussed with: Dimitry Luhtionov
Differential Revision: https://reviews.freebsd.org/D30516
Differential Revision: https://reviews.freebsd.org/D30536
Differential Revision: https://reviews.freebsd.org/D30844

(cherry picked from commit 935fc93af157dee352eb4b6c83f8a2a9e7fd9a4e)
(cherry picked from commit d261e57deacb0d00d9e827447f235df83dda3e3a)
(cherry picked from commit f70c98a2f5d993dc518efd606aa341eda99400ef)
(cherry picked from commit 25392fac9488bcae5c451500df2e2945430484a6)
(cherry picked from commit 2f4d91f9cb22fc65eb65407e8118b433a5d71976)
(cherry picked from commit 4060e77f49d1b9fd2254f3f4da94fd64fce83f72)
sys/netinet/libalias/HISTORY
sys/netinet/libalias/alias_db.c
sys/netinet/libalias/alias_db.h [new file with mode: 0644]
sys/netinet/libalias/alias_local.h