12.4. Filtres hachés pour un filtrage massif très rapide

Si vous avez besoin de milliers de règles, par exemple, dans le cas où vous avez beaucoup de clients ou d'ordinateurs, tous avec des spécifications QoS différentes, vous pourrez constater que le noyau passe beaucoup de temps à analyser toutes ces règles.

Par défaut, tous les filtres résident dans une grande chaîne qui est analysée par ordre décroissant des priorités. Si vous avez 1000 règles, 1000 contrôles peuvent être nécessaires pour déterminer ce qu'il faut faire d'un paquet.

La vérification irait plus vite s'il y avait 256 chaînes avec chacune quatre règles et si vous pouviez répartir les paquets sur ces 256 chaînes, afin que la bonne règle soit présente.

Ceci est rendu possible par le hachage. Imaginons que vous ayez sur votre réseau 1024 clients avec des modems câble, avec des adresses IP allant de 1.2.0.0 à 1.2.3.255, et que chacun doit avoir un classement particulier, par exemple « pauvre », « moyen » et « bourrage ». Cela vous ferait alors 1024 règles, dans le genre :

# 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

Pour aller plus vite, nous pouvons utiliser la dernière partie de l'adresse IP comme « clé de hachage ». Nous obtenons alors 256 tables, la première ressemblant à ceci :

# 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

La suivante commence comme ceci :

# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
  1.2.0.1 classid 1:1
...

De cette manière, seules quatre recherches au plus sont nécessaires et deux en moyenne.

La configuration est plutôt compliquée, mais elle en vaut vraiment la peine du fait des nombreuses règles. Nous créons d'abord un filtre racine, puis une table avec 256 entrées :

# 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: u32 divisor 256

Nous ajoutons maintenant des règles dans la table précédemment créée :

# 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

Ceci est l'entrée 123, qui contient les correspondances pour 1.2.0.13, 1.2.1.123, 1.2.2.123 et 1.2.3.123 qui les envoient respectivement vers 1:1, 1:2, 1:3 et 1:2. Notez que nous devons spécifier notre seau de hachage en hexadécimal, 0x7b pour 123.

Nous créons ensuite un « filtre de hachage »qui dirige le trafic vers la bonne entrée de la table de hachage :

# 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, certains nombres doivent être expliqués. La table de hachage par défaut est appelée 800:: et tous les filtres démarrent de là. Nous sélectionnons alors l'adresse source qui est en position 12, 13, 14 et 15 dans l'en-tête IP, et indiquons que seule la dernière partie nous intéresse. Ceci est envoyé vers la table de hachage 2: qui a été créée plus tôt.

C'est plutôt compliqué, mais cela marche en pratique et les performances seront époustouflantes. Notez que cet exemple pourrait être amélioré pour que chaque chaîne contienne un filtre, ce qui représenterait le cas idéal !