Linux 7.4 accélère d’un facteur 5 000 l’allocateur mémoire de boot grâce à une recherche binaire
Le 24 octobre 2026, un correctif de Tarun Sahu, ingénieur chez Google, remplace la recherche linéaire de l’allocateur de mémoire de boot de Linux par une recherche binaire dans mm/memblock.c. La récupération de mémoire KHO passe de 268 secondes à 50 millisecondes, un gain qui compte surtout pour les mises à jour de noyau sans redémarrage.
24 octobre 2026. Un correctif envoyé pour la fenêtre de fusion de Linux 7.4 remplace une recherche linéaire par une recherche binaire dans mm/memblock.c, l’allocateur de mémoire physique utilisé au tout début du boot. Résultat mesuré : la récupération de mémoire KHO passe d’environ 268 secondes à environ 50 millisecondes. L’auteur, Tarun Sahu, ingénieur chez Google, a repéré qu’un balayage linéaire avait survécu des années dans un chemin pourtant central. Michael Larabel, de Phoronix, résume le sentiment général : on s’étonne qu’il ait duré si longtemps.
Pour un administrateur système ou un responsable de plateforme, l’épisode vaut leçon : les pires régressions ne sont pas dans les algorithmes exotiques, mais dans les boucles simples que personne ne regarde plus — et leur facture n’apparaît que sur les charges que vous n’avez pas encore.
L’allocateur qu’on ne voit jamais
memblock est le premier allocateur de mémoire physique du noyau. Il tourne avant la mise en route du page allocator (l’allocateur par zones, ou buddy allocator), à un moment où le noyau ne dispose encore d’aucune des structures de gestion mémoire de la suite. C’est lui qui découpe, isole et réserve les régions de mémoire physique pendant les premières étapes du démarrage.
Son rôle est ingrat et invisible : il ne s’exécute que quelques instants, sur un matériel varié, puis cède la place à l’allocateur définitif. Résultat, son code est rarement regardé, et ses défauts de complexité se cachent derrière des temps d’exécution si courts que personne ne les mesure — sauf quand la fragmentation les fait exploser.
Le coût caché de la fragmentation KHO
Le déclencheur s’appelle KHO, pour Kernel Handover. C’est la fonctionnalité qui sérialise et restaure l’état mémoire du noyau lors d’une mise à jour à chaud, par le biais d’un kexec : au lieu de redémarrer la machine de zéro, on transfère l’état du noyau sortant vers le noyau entrant. Elle est utilisée par le Live Update Orchestrator de Meta et ses proches.
Quand la mémoire est lourdement fragmentée — des milliers de folios disjoints, comme en produit KHO au moment de reconstituer l’état — la recherche de la région candidate dans memblock devient le goulot d’étranglement. Le code parcourait les régions une par une, en O(n) par insertion, et le cumul faisait de la récupération de mémoire KHO une opération de plusieurs minutes.
Une ligne de code qui change la complexité
Le correctif de Tarun Sahu tient en un changement de méthode : dans memblock_add_range() et memblock_isolate_range(), la recherche linéaire du candidat cède la place à une recherche binaire. Le commentaire du patch est lapidaire :
Using binary search reduces the worst-case complexity to O(N log N) (and O(N) for sequential appends), cutting KHO memory retrieval time from ~268s to ~50ms.
Traduit : la recherche binaire abaisse la complexité du pire cas à O(N log N) — et O(N) pour les ajouts séquentiels — et fait passer la récupération de mémoire KHO de 268 secondes à 50 millisecondes. Soit un gain d’un facteur 5 000, obtenu sans nouvelle structure de données, sans nouveau matériel et sans réécrire l’allocateur : il suffisait de chercher au bon endroit.
La morale technique est double. D’abord, un O(N²) déguisé se cache souvent dans un for innocent, invisible sur les petits jeux de données de test et catastrophique sur les vrais. Ensuite, ce type de défaut ne se corrige pas en ajoutant de la puissance : diviser par 5 000 un temps de boot exigerait une machine 5 000 fois plus rapide, ce qu’aucun achat ne peut offrir. Le bon ordre de grandeur s’achète en complexité, pas en silicium.
Pourquoi ça compte pour les mises à jour live
Le chiffre de 268 secondes n’est pas théorique : c’est le temps que KHO mettait à reconstituer un état mémoire fragmenté, avant que l’allocateur ne cède la place au page allocator. Pour un exploitant qui mise sur les mises à jour de noyau sans redémarrage — le chantier que Meta pousse avec le Live Update Orchestrator — chaque seconde de reconstitution est une seconde d’indisponibilité ou de bascule, sur des flottes où le reboot complet est interdit.
Le correctif s’inscrit dans une fenêtre de fusion Linux 7.4 déjà riche en optimisations de même nature : les changements de workqueue promettent des accélérations de « 10 à 100 fois » sur certains chemins, et des centaines de patchs MM ont été fusionnés. La tendance est claire : le noyau continue de traquer les complexités cachées dans des chemins vieux de plus d’une décennie, parce que c’est là que dorment les gains les plus rentables.
Pour un opérateur, l’implication est concrète. Si vous testez KHO ou un équivalent de mise à jour live, ce correctif change vos mesures de bout en bout : le temps que vous attribuiez au transfert d’état peut en réalité être le temps de recherche d’un allocateur, et disparaître avec le noyau 7.4.
Verdict
Si vous maintenez une flotte Linux où le reboot est coûteux ou interdit, suivez la fusion de Linux 7.4 de près et planifiez des essais de KHO avec ce correctif : un facteur 5 000 sur la reconstitution de mémoire peut faire la différence entre une mise à jour live viable et une mise à jour live abandonnée.
Si vous exploitez des machines classiques qui redémarrent en quelques secondes, vous ne verrez jamais le gain : memblock ne s’exécute que quelques instants sur un boot normal. Retenez simplement la leçon — la prochaine régression de ce type dort probablement dans une boucle linéaire de votre propre pile, pas dans le noyau. Et avant de jeter de la puissance sur un chemin lent, cherchez d’abord si la complexité est du bon ordre.