Bug 253912 - [PATCH] Inefficient lookup of incoming packets in libalias
Summary: [PATCH] Inefficient lookup of incoming packets in libalias
Status: New
Alias: None
Product: Base System
Classification: Unclassified
Component: kern (show other bugs)
Version: CURRENT
Hardware: Any Any
: --- Affects Only Me
Assignee: freebsd-bugs (Nobody)
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2021-02-28 15:05 UTC by Lukas Turek
Modified: 2022-06-17 11:15 UTC (History)
1 user (show)

See Also:


Attachments
Change lookup of incoming packets to use both addresses (6.73 KB, patch)
2021-02-28 15:05 UTC, Lukas Turek
no flags Details | Diff
A similar fix for rewritten libalias in FreeBSD 13.1 (4.19 KB, patch)
2022-06-17 11:15 UTC, Lukas Turek
no flags Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Lukas Turek 2021-02-28 15:05:20 UTC
Created attachment 222878 [details]
Change lookup of incoming packets to use both addresses

While lookup of outgoing packets uses hash based on both source and destination address, for incoming packets only alias address and port is used. So when multiple connections from different addresses target the same port of redirected address (using redirect_addr or redirect_port in IPFW), the link table must be searched sequentially - tens of thousand of items for every incoming packet. To make it worse, the search is under a lock, so it is forced to run on a single core. Consequently just 1000pps from different addresses are enough to bring down a server with the fastest CPU available in under a minute.

The attached patch fixes the problem by using both addresses and ports for lookup of incoming packets. We are running it currently on 11.2, but it applies to CURRENT without changes.
Comment 1 Lukas Turek 2022-06-17 11:13:03 UTC
Even though libalias database was mostly rewriten, this bug is still present in 13.1. The problem wasn't in the data structure itself (hash table or splay tree), but in the key used for lookup. If the key contains only alias address and port, all packets from many addresses in DDoS targeting the same local address and port will collide in a single entry. I made a new patch working in a similar way to the previous one. I did some simple tests, but we haven't deployed it in production yet.
Comment 2 Lukas Turek 2022-06-17 11:15:18 UTC
Created attachment 234750 [details]
A similar fix for rewritten libalias in FreeBSD 13.1