2

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?

1
  • Is this implementing a fixed relationship between mac address & resulting treatment - or just some more or less arbitrary grouping that happens to be keyed on mac address?
    – anx
    Oct 18, 2020 at 20:17

1 Answer 1

0

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?

2
  • How are the source and destination MAC address offsets determined? It's not entirely clear from this discussion. Is the source address the first 6 bytes of the L2 header, and the destination the 6 bytes after that? Nov 26, 2022 at 23:19
  • @FKEinternet That is simply copied from the question, except for different alignment. 4 bytes from -8 plus together with 2 bytes from -4 is referring to the same source address (in byte offset 6-11 from start of ether frame) where I select a subset from, when I fetch 4 bytes from -6, then only "hashing" the last one.
    – anx
    Nov 27, 2022 at 1:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.