HomeFreeBSD

libalias: Switch to efficient data structure for incoming traffic

Description

libalias: Switch to efficient data structure for incoming traffic

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
MFC after: 1 week
Differential Revision: https://reviews.freebsd.org/D30536

Details