Linux traffic control u32 hashtable filters based on MAC address

Question

I am currently working with a traffic shaping Linux node. The rule set has grown to about 2500 hosts, all identified specifically by MAC address. The filter configuration is "basic", meaning that on average, 1250 rules must be tested before a packet is filtered to the correct class. At line rates we're currently seeing, this is causing too much CPU on the host, causing packets to be dropped.

I would like to move from the linear linked-list ruleset to a 6-level hashtable lookup (one for each byte of the MAC address)

I am completely unsure on how to achieve this currently. Most documentation on this feature is reasonably confusing to me, and as far as I've found, it all is based on IP address hashing.

I'm currently matching packets based on their L2 header values with a filter, example (for egress/upload):

MAC: 52:54:00:12:34:56

tc filter add dev <dev> protocol ip parent 1:0 prio 1 u32 match u16 0x0800 at -2 match u16 0x3456 0xffff at -4 match u32 0x52540012 0xffffffff at -8 flowid 1:50

Are there any resources I could follow to maybe explain the hashtable setup better?

Answer 1

Lets say 52:54:00:12:34:56 goes to 1:50 and 52:54:00:12:37:56 goes to 1:51.

For a 256-wise split of the rules, start with one hash table, lets call it 2::

# tc filter add dev eth1 parent 1:0 prio 1 handle 2: protocol ip u32 divisor 256

To select on a single byte, we select 4 bytes at a specific offset, and use a bitmask to select which one. The offset 0 would be the start of the payload, negative addressing gets us back into the layer 2 frame header. First, go back 2 bytes to check the ethertype (0x800), 6 more bytes gets us to the start of the (48-bit) source mac address. Adding back 2 means the following (starting at minus 6) 4 bytes are the lower 32 bits of the source mac address. From here, we can put the ff in the mask to the byte in the mac address that we want.

# tc filter add dev <dev> protocol ip parent 1:0 prio 1 u32 ht 800:: \
    match u16 0x0800 at -2 \
    hashkey mask 0x000000ff at -6 \
    link 2:

Note my examples match the IPv4 filter right away and do not repeat it later, I do not think it matters - in any case, we only need it exactly once.

Then insert the rules, putting the (hexadecimal) byte to the ht handle. The alignment above means that the hash in hashtable is no-op for 8-bit values, meaning the address ending in :56 hex shows up in ht 2:56 hex:

# tc filter add dev <dev> protocol ip parent 1:0 prio 1 u32 \
  ht 2:56: \
  match u16 0x3456 0xffff at -4 match u32 0x52540012 0xffffffff at -8 \
  flowid 1:50
# tc filter add dev <dev> protocol ip parent 1:0 prio 1 u32 \
  ht 2:56: \
  match u16 0x3756 0xffff at -4 match u32 0x52540012 0xffffffff at -8 \
  flowid 1:51
... any many more mac addr rules

Flowchart:

1:0 =hash 1st byte=> ht 2:56 =sequential mac filter=> flowid 1:50

Now of course, adding another hashtable layer for the second (or more) bytes is possible and potentially further reduces the number of rules traversed, but you probably only have a handful of mac addrs with matching last-byte, so why bother going 6-level?