12.4. Hashing filters for very fast massive filtering
If you have a need for thousands of rules, for example if you have a lot of
clients or computers, all with different QoS specifications, you may find
that the kernel spends a lot of time matching all those rules.
By default, all filters reside in one big chain which is matched in
descending order of priority. If you have 1000 rules, 1000 checks may be
needed to determine what to do with a packet.
Matching would go much quicker if you would have 256 chains with each four
rules - if you could divide packets over those 256 chains, so that the right
rule will be there.
Hashing makes this possible. Let's say you have 1024 cable modem customers in
your network, with IP addresses ranging from 1.2.0.0 to 1.2.3.255, and each
has to go in another bin, for example 'lite', 'regular' and 'premium'. You
would then have 1024 rules like this:
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
1.2.0.0 classid 1:1
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
1.2.0.1 classid 1:1
...
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
1.2.3.254 classid 1:3
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
1.2.3.255 classid 1:2 |
To speed this up, we can use the last part of the IP address as a 'hash
key'. We then get 256 tables, the first of which looks like this:
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
1.2.0.0 classid 1:1
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
1.2.1.0 classid 1:1
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
1.2.2.0 classid 1:3
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
1.2.3.0 classid 1:2 |
The next one starts like this:
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
1.2.0.1 classid 1:1
... |
This way, only four checks are needed at most, two on average.
Configuration is pretty complicated, but very worth it by the time you have
this many rules. First we make a filter root, then we create a table with
256 entries:
# tc filter add dev eth1 parent 1:0 prio 5 protocol ip u32
# tc filter add dev eth1 parent 1:0 prio 5 handle 2: protocol ip u32 divisor 256 |
Now we add some rules to entries in the created table:
# tc filter add dev eth1 protocol ip parent 1:0 prio 5 u32 ht 2:7b: \
match ip src 1.2.0.123 flowid 1:1
# tc filter add dev eth1 protocol ip parent 1:0 prio 5 u32 ht 2:7b: \
match ip src 1.2.1.123 flowid 1:2
# tc filter add dev eth1 protocol ip parent 1:0 prio 5 u32 ht 2:7b: \
match ip src 1.2.3.123 flowid 1:3
# tc filter add dev eth1 protocol ip parent 1:0 prio 5 u32 ht 2:7b: \
match ip src 1.2.4.123 flowid 1:2 |
This is entry 123, which contains matches for 1.2.0.123, 1.2.1.123,
1.2.2.123, 1.2.3.123, and sends them to 1:1, 1:2, 1:3 and 1:2 respectively.
Note that we need to specify our hash bucket in hex, 0x7b is 123.
Next create a 'hashing filter' that directs traffic to the right entry in
the hashing table:
# tc filter add dev eth1 protocol ip parent 1:0 prio 5 u32 ht 800:: \
match ip src 1.2.0.0/16 \
hashkey mask 0x000000ff at 12 \
link 2: |
Ok, some numbers need explaining. The default hash table is called 800:: and
all filtering starts there. Then we select the source address, which lives
as position 12, 13, 14 and 15 in the IP header, and indicate that we are
only interested in the last part. This we send to hash table 2:, which we
created earlier.
It is quite complicated, but it does work in practice and performance will
be staggering. Note that this example could be improved to the ideal case
where each chain contains 1 filter!
