Проблема линейного поиска в memblock
В ветку Linux 7.4, отправленную 24 октября 2026 года, вошел важный патч от инженера Google Таруна Сау (Tarun Sahu). Оптимизация затрагивает файл mm/memblock.c, который отвечает за раннее распределение физической памяти до инициализации полноценного аллокатора страниц. Ранее код использовал линейный поиск для нахождения подходящих регионов памяти, что становилось критическим узким местом при высокой фрагментации.
Результаты оптимизации
Ключевое изменение — переход от линейного сканирования к бинарному поиску в функциях memblock_add_range() и memblock_isolate_range(). Это кардинально меняет сложность алгоритма: худший случай снижается до O(N log N), а для последовательных добавлений сохраняется O(N). На практике это означает, что время извлечения памяти для функции Kernel Handover (KHO) сократилось с ~238–268 секунд до ~50 миллисекунд.
| Метрика | До оптимизации | После оптимизации |
|---|---|---|
| Время извлечения памяти (KHO) | ~268 секунд | ~50 миллисекунд |
| Сложность (худший случай) | Выше (линейный поиск) | O(N log N) |
| Сложность (последовательные добавления) | — | O(N) |
Почему это важно для Live Update
Функция Kernel Handover (KHO) используется инструментами оркестровки, такими как Live Update Orchestrator, для обновления ядра без перезагрузки системы. При наличии множества разрозненных folio (блоков памяти) процесс сканирования занимал почти 4,5 минуты. Внедрение бинарного поиска делает технологию горячей перезагрузки ядра практически мгновенной, устраняя один из главных барьеров для её массового внедрения в продакшен-средах.
Исторический контекст
Удивительно, что линейный поиск сохранялся в коде ядра так долго, учитывая, что оптимизация затрагивает только раннюю стадию загрузки. Однако именно на этом этапе критична эффективность при работе с большими объемами памяти и сложной структурой фрагментации. Патч уже включен в pull-запрос для ветки memblock и будет доступен в релизе Linux 7.4.
Источник: Phoronix ↗