Download
Description
A small C program that generates very fast u32 hashing filters given a random set of prefixes and destination class ids as input. The resulting filters can be appended to a file containing the htb class definitions to create a complete tc input file.
The program generates a tree of u32 hash tables. The root table contains entries for the first byte in the IPv4 address. Each entry contains hash tables for the second byte, whose entries in turn contain hash tables for the third and so on. Only entries used in the prefixes supplied are generated.
This way, regardless of the IP address, classifying a packet into a class needs a fixed number of operations (the maximum tree depth is 4). At constant traffic levels, increasing the number of prefixes will only increase the used memory. CPU usage should remain fairly the same.
Compile/run instructions
root@br1 [/home/vcalinus]# gcc -o prefixtree prefixtree.c
root@br1 [/home/vcalinus]# ./prefixtree IPv4 u32 hash filter generator - (C) 2006 Calin Velea
Syntax: prefixtree {prefix.in} {u32filters.out} {interface} {src/dst} [batch]
Arguments
- {prefix.in} – input file. Contains the list of prefixes and the associated class ids in the following format:
<prefix> <classid>
….
- {u32filters.out} – output file. Contains the generated u32 hash filters
- {interface} – interface where the shaping takes place (tc filter add dev {interface} )
- {src/dst} – indicates whether we are shaping upload or download (affects src/dst and hash offsets in tc statements)
- [batch] – if specified, will generate an output file acceptable for tc -b
Typical usage example
tc.main.src – base tc file
qdisc add dev eth0 root handle 1: htb default 99 r2q 1 class add dev eth0 parent 1: classid 1:1 htb rate 400000kbit ceil 400000kbit quantum 1536 #default class add dev eth0 parent 1:1 classid 1:99 htb rate 100kbit ceil 100kbit qdisc add dev eth0 parent 1:99 handle 99: sfq quantum 1520 perturb 10
# cust1 – class 1:101 class add dev eth0 parent 1:1 classid 1:101 htb rate 10120kbit ceil 10120kbit quantum 1536 qdisc add dev eth0 parent 1:101 handle 101: sfq quantum 1520 perturb 10 # cust2 – class 1:102 class add dev eth0 parent 1:1 classid 1:102 htb rate 20096kbit ceil 20096kbit quantum 1536 qdisc add dev eth0 parent 1:102 handle 102: sfq quantum 1520 perturb 10 # cust3 – class 1:1af class add dev eth0 parent 1:1 classid 1:1af htb rate 20096kbit ceil 20096kbit quantum 1536 qdisc add dev eth0 parent 1:1af handle 1af: sfq quantum 1520 perturb 10
prefixes.in – input file for prefixtree
68.91.0.0/20 1:101 195.28.184.0/29 1:102 89.165.145.5/32 1:1af
Run it:
root@br1 [/home/vcalinus]# ./prefixtree prefixes.in u32filters.out eth0 src batch
lines parsed: 3
total hashtables: 8
Output file:
root@br1 [/home/vcalinus]# cat u32filters.out ##### Generated with prefixtree v1.0 ##### filter add dev eth0 parent 1:0 prio 5 protocol ip u32 filter add dev eth0 parent 1:0 prio 5 handle 10: protocol ip u32 divisor 256 filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 800:: match ip src 0.0.0.0/0 hashkey mask 0xff000000 at 12 link 10: ## entries for 68.0.0.0/8 filter add dev eth0 parent 1:0 prio 5 handle 11: protocol ip u32 divisor 256 filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 10:44: match ip src 0.0.0.0/0 hashkey mask 0xff0000 at 12 link 11: ## entries for 68.91.0.0/16 filter add dev eth0 parent 1:0 prio 5 handle 12: protocol ip u32 divisor 256 filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 11:5b: match ip src 0.0.0.0/0 hashkey mask 0xff00 at 12 link 12: filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 12:0: match ip src 0.0.0.0/0 flowid 1:101 filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 12:1: match ip src 0.0.0.0/0 flowid 1:101 filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 12:2: match ip src 0.0.0.0/0 flowid 1:101 filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 12:3: match ip src 0.0.0.0/0 flowid 1:101 filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 12:4: match ip src 0.0.0.0/0 flowid 1:101 filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 12:5: match ip src 0.0.0.0/0 flowid 1:101 filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 12:6: match ip src 0.0.0.0/0 flowid 1:101 filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 12:7: match ip src 0.0.0.0/0 flowid 1:101 filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 12:8: match ip src 0.0.0.0/0 flowid 1:101 filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 12:9: match ip src 0.0.0.0/0 flowid 1:101 filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 12:a: match ip src 0.0.0.0/0 flowid 1:101 filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 12:b: match ip src 0.0.0.0/0 flowid 1:101 filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 12:c: match ip src 0.0.0.0/0 flowid 1:101 filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 12:d: match ip src 0.0.0.0/0 flowid 1:101 filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 12:e: match ip src 0.0.0.0/0 flowid 1:101 filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 12:f: match ip src 0.0.0.0/0 flowid 1:101 ## entries for 89.0.0.0/8 filter add dev eth0 parent 1:0 prio 5 handle 16: protocol ip u32 divisor 256 filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 10:59: match ip src 0.0.0.0/0 hashkey mask 0xff0000 at 12 link 16: ## entries for 89.165.0.0/16 filter add dev eth0 parent 1:0 prio 5 handle 17: protocol ip u32 divisor 256 filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 16:a5: match ip src 0.0.0.0/0 hashkey mask 0xff00 at 12 link 17: ## entries for 89.165.145.0/24 filter add dev eth0 parent 1:0 prio 5 handle 18: protocol ip u32 divisor 256 filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 17:91: match ip src 0.0.0.0/0 hashkey mask 0xff at 12 link 18: filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 18:5: match ip src 0.0.0.0/0 flowid 1:1af ## entries for 195.0.0.0/8 filter add dev eth0 parent 1:0 prio 5 handle 13: protocol ip u32 divisor 256 filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 10:c3: match ip src 0.0.0.0/0 hashkey mask 0xff0000 at 12 link 13: ## entries for 195.28.0.0/16 filter add dev eth0 parent 1:0 prio 5 handle 14: protocol ip u32 divisor 256 filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 13:1c: match ip src 0.0.0.0/0 hashkey mask 0xff00 at 12 link 14: ## entries for 195.28.184.0/24 filter add dev eth0 parent 1:0 prio 5 handle 15: protocol ip u32 divisor 256 filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 14:b8: match ip src 0.0.0.0/0 hashkey mask 0xff at 12 link 15: filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 15:0: match ip src 0.0.0.0/0 flowid 1:102 filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 15:1: match ip src 0.0.0.0/0 flowid 1:102 filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 15:2: match ip src 0.0.0.0/0 flowid 1:102 filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 15:3: match ip src 0.0.0.0/0 flowid 1:102 filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 15:4: match ip src 0.0.0.0/0 flowid 1:102 filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 15:5: match ip src 0.0.0.0/0 flowid 1:102 filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 15:6: match ip src 0.0.0.0/0 flowid 1:102 filter add dev eth0 protocol ip parent 1:0 prio 5 u32 ht 15:7: match ip src 0.0.0.0/0 flowid 1:102 root@br1 [/home/vcalinus]#
Finishing up
Put classes and filters together:
cat u32filters.out >> tc.main.src
Apply everything:
tc –b < tc.main.src
Repeat the steps above using dst when running prefixtree to shape the download.
Optimizing existing tc files
Suppose you have a tc file which is not using hashing. Classification is done only based on src/dst prefix match (no port or other specific u32 matches are used). You could easily optimize it by separating the classes and filters part, constructing an input file for prefixtree then joining it back with the classes part. You need to write a script to parse the files and extract the prefixes and class ids (from the tc statements).
grep –v "tc filter add" unoptimized_tc.in > classes.out grep "tc filter add" unoptimized_tc.in > unoptimized_filters.out ./generate_prefixtree_input classes.out unoptimized_filters.out prefixes.in ./prefixtree prefixes.in optimized_filters.out $iface src batch cat optimized_filters_out >> classes.out mv classes.out optimized_tc.in tc –b < optimized_tc.in
Test Results
Real-world testing has shown troughputs of 1300Mbps / 250.000 pps (aggregated in+out) for a 2.6.20 linux shaping bridge on a quad-core Xeon X3210 (2.13GHz, 8M L2 cache), 2GBs of RAM using Intel PCI Express Gigabit NICs. At this traffic level, CPU utilization averages varied between 25 – 50 % for every core. Almost 8.000 prefixes of various lengths were being shaped, with a roughly equal number of htb classes.
5000 series Xeons with 12MB of L2 cache, running at 3GHz or more should come close to 6-700.000 pps peak performance, saturating several gigabit interfaces.