Après la publication du patch de Tarun Sahu le 3 septembre 2026, Phoronix a rapporté le 24 octobre son envoi dans une pull request pour Linux 7.4. Le changement proposé remplace des recherches linéaires par une recherche binaire dans deux fonctions de memblock, l’allocateur de mémoire physique utilisé au début du démarrage. Pour une charge de récupération KHO d’environ 393 000 pages, Sahu rapporte un temps passé d’environ 268 secondes à 50 millisecondes.
Le rôle de memblock au début du démarrage de Linux
memblock, dans mm/memblock.c, gère la mémoire physique avant que l’allocateur complet de pages du noyau soit opérationnel. Le patch proposé concerne memblock_add_range() et memblock_isolate_range(), qui recherchent des régions candidates dans cette liste.
Comment la recherche binaire cible les listes fragmentées
La recherche binaire, aussi appelée recherche dichotomique, réduit la portion de la liste à examiner au lieu de repartir de son début. Le patch définit une recherche de type « borne inférieure » : elle repère la première région dont la fin dépasse l’adresse de départ recherchée.
Tarun Sahu décrit les balayages linéaires répétés comme un cas en O(N²) lorsque la mémoire est fortement fragmentée. Selon l’auteur, la recherche proposée ramène la complexité au pire cas à O(N log N), et à O(N) pour les ajouts séquentiels. Sahu précise aussi qu’un balayage linéaire peut être efficace pour les petites listes. Il situe le code concerné dans l’initialisation au démarrage, avec le hotplug mémoire comme exception.
Ce que mesure le résultat KHO
Pour une charge KHO d’environ 393 000 pages, Tarun Sahu, auteur du patch, rapporte les durées de récupération suivantes :
| Opération mesurée | Avant le changement | Après le changement |
| Récupération de mémoire KHO | Environ 268 secondes | Environ 50 millisecondes |
KHO signifie Kernel Handover. Ces durées concernent la récupération de mémoire dans cette charge précise ; elles décrivent le résultat rapporté par Sahu pour cette opération.
Un autre rapport de charge, fondé sur des marqueurs de démarrage
Dongli Zhang a rapporté plusieurs essais sur un système à 32 processeurs et un nœud, avec THP réglé sur « never » et des pages de 4K. Dans ses journaux, l’intervalle entre les marqueurs mem-auto-init et SLUB est passé de 38,355755 secondes à 0,264273 seconde. Ces valeurs décrivent cet intervalle dans sa charge et son système.
