kohler/click — pull request #112 by trackpick (2014-03-22 19:56:57+00:00)
Title: arptable: make slim()'s hunt for packets scale better

The second part of slim(), which searches for queued IP packets to
delete when ARPTable is at packet capacity, starts its search from
somewhere near the beginning of the _age list. However, in some
scenarios (such as a during nmap host discovery or an nmap-like attack),
the entries that contain packets will be found towards the end of the
list. In the case that ARPTable is constantly at packet capacity (as
would be the case during nmap host discovery), slim() ends up performing
an O(n) traversal for each new IP packet, which kills performance.

This commit adds _packet_search_head, a pointer into the _age list for
slim() to start its search at. _packet_search_head is maintained such
that earlier entries in the list are guaranteed not to contain packets
(thus it is safe to start searching here), and, for the nmap case,
typically the earliest entry with a packet is _packet_search_head itself
(giving an O(1) search).

These are the main cases for maintaining _packet_search_head:

- If _packet_search_head entry gets moved towards the tail of the list,
set _packet_search_head to be the next entry (insert(),
append_query()).

- If a packet gets added to an entry older than _packet_search_head,
make that entry the new _packet_search_head (append_query()).

- Packets always get deleted from the earliest entry that has a packet
(slim()). After deleting a packet, set _packet_search_head to this
entry. (It is OK if the entry has no packets left.)

One scenario still not handled well is one where, in addition to nmap
host discovery / attack, packets are frequently sent to IP addresses
that already appear earlier in the list. In that case, append_query()'s
_timeout_j code (or slim() if _timeout_j is 0) may still end up
repeatedly doing O(n) traversals.

An alternative solution is to have a separate linked list with entries
that have packets queued. That seems way more complex though, and I
believe Eddie likes to keep his ARPEntries small.

Another solution (suggested by rthanks) is to normally only slim on
timer expiry, allow the number of packets to grow to a higher 'critical'
capacity, and do per-packet slimming when the critical capacity is
reached. This requires careful tuning of the timer interval vs. the
difference between the two capacities.

Reviewed-by: rtshanks@meraki.com
Reviewed-by: jdizzle@meraki.com
Signed-off-by: Patrick Verkaik