Ядро Linux в комментариях




Find_vma - часть 2


При наличии достаточно большого количества областей VMA прохождение по дереву становится быстрее, чем перебор связанного списка; поскольку деревья AVL сбалансированы, это операция с логарифмическими, а не линейными затратами времени. Итеративное прохождение по дереву встречается не так уж редко, но эта структура обладает некоторыми особенностями, которые не сразу бросаются в глаза. Прежде всего, обратите внимание на присваивание в строке ; в ней отслеживается наилучший узел, найденный до сих пор, поэтому будет возвращен именно он, если не нашлось ничего лучшего. Проверка if в следующей строке— это оптимизация для проверки того, лежит ли addr полностью в пределах VMA (мы уже знаем, что к этому моменту addr меньше значения vm_end для данной области VMA). Поскольку области VMA никогда не перекрываются, не существует другой, более подходящей области VMA, поэтому можно сразу же прекратить обход дерева.

Если во время обхода дерева или просмотра списка была найдена область VMA, полученное значение сохраняется в кэше до следующего поиска.

В любом случае возвращается значение vma; оно может быть равным NULL или может указывать на первую область VMA, которая удовлетворяет условию поиска.




Содержание  Назад  Вперед