Dans un précédent article, j’expliquais comment Linux stockait les routes dans un arbre compressé pour obtenir d’excellents résultats sur les temps de recherche. Le graphique suivant montre la progression des performances à travers les époques :

Deux scénarios sont testés :

• 500 000 routes extraites d’un routeur Internet (la moitié étant des /24)
• 500 000 routes /32 réparties consécutivement dans 4 sous-réseaux distincts

Tous les noyaux sont compilés avec GCC 4.9 (issu de Debian Jessie). Cette version est compatible avec des noyaux antiques¹ ainsi qu’avec les noyaux les plus récents. La configuration du noyau utilisée est celle par défaut avec les options CONFIG_SMP et CONFIG_IP_MULTIPLE_TABLES activées (sans toutefois utiliser de règles de routage). D’autres options mineures sont activées pour permettre de prendre les mesures.

Le banc d’essai se déroule dans une machine virtuelle utilisant un seul vCPU². Le CPU hôte est un Intel Core i5-4670K et le gouverneur CPU est configuré en mode « performance ». Les mesures sont faites par un module noyau appelant la fonction fib_lookup() en boucle en variant les destinations. Le chronométrage de chacune des 100 000 itérations est effectuée par la TSC et convertie en nanosecondes en se basant sur une fréquence d’horloge arbitraire. La valeur médiane est retenue.

Quelques noyaux apportent un progrès notable :

• Avec Linux 2.6.39, commit 3630b7c050d9, David Miller retire l’implémentation basée sur des tables de hachage pour utiliser des arbres compressés (disponible sous forme d’option à la compilation depuis Linux 2.6.13). Cela provoque une légère régression dans le cas des routes en /32 mais améliore grandement les performances dans le cas général.

• Avec Linux 3.0, commit 281dc5c5ec0f, l’amélioration n’est pas liée à un changement dans le sous-système réseau. Linus Torvalds a désactivé l’optimisation en taille qui était utilisée par défaut. Cette option devait permettre de rendre le cache des instructions plus efficace mais les compilateurs généraient cependant un code plus lent sur x86.

• Avec Linux 3.6, commit f4530fa574df, David Miller ajoute une optimisation destinée à ne plus évaluer les règles de routage quand elles n’ont pas été modifiées. À partir de cette version, l’option CONFIG_IP_MULTIPLE_TABLES ne dégrade plus les performances à moins de configurer explicitement des règles de routage. Cette version retire également le cache des routes (commit 5e9965c15ba8). Toutefois, cela n’a pas d’effet sur les mesures car l’appel direct à fib_lookup() contourne ce cache.

• Avec Linux 4.0, notamment le commit 9f9e636d4f89, Alexander Duyck réorganise l’algorithme de recherche des routes pour en augmenter les performances. Le résultat est probant !

• Avec Linux 4.1, commit 0ddcf43d5d4a, Alexander Duyck fusionne les tables local et main quand aucune règle de routage n’est utilisée. Pour le trafic non local, ces deux tables étaient successivement consultées.

Mise à jour à mi-2018#

Voici un graphique pour des noyaux plus récents. Les performances sont plutôt stables. Les recherches sont mesurées par lot de cinq pour réduire les coûts. Les petites régressions des versions 4.2 et 4.16 peuvent ou non être significatives (une variation de 5 ns correspond à une recherche dans le cache de niveau 2).

Les récentes vulnérabilités Meltdown et Spectre ont défrayé la chronique en raison de l’impact sur les performances des correctifs. La recherche d’une route s’effectuant intégralement dans le noyau, les correctifs devraient n’avoir aucun effet, comme confirmé sur les graphiques ci-dessous:

Les mesures ont été faites sur une machine virtuelle avec un seul vCPU. L’hôte est un Intel Core i5-4670K (micro-architecture Haswell) tournant à 3,4 GHz avec un microcode à jour et un noyau 4.16 de Debian. Lorsqu’il est protégé, l’hôte utilise PTI, retpoline et IBPB. Dans le cas contraire, l’hôte tourne avec un ancien microcode et les protections sont désactivées au niveau de la ligne de commande (nopti nospectre_v2). Les noyaux pour la machine virtuelle sont compilés avec GCC 7.3 qui inclus le support de retpoline.