Find_vma
В общих чертах назначение функции find_vma состоит в поиске первой области VMA, содержащей заданный адрес. Вернее, ее назначение состоит в поиске первой области VMA, в которой значение vm_end превышает заданный адрес, но этот адрес все еще может находиться за пределами VMA, поскольку он может быть меньше значения vm_start этой области VMA. Функция возвращает указатель на VMA или NULL, если ни одна область VMA не соответствует запросу.
Вначале проверяется та же область VMA, которая соответствовала последнему запросу к этому процессу, с использованием члена mmap_cache объекта mm, предназначенного специально для этой цели. Автор не проверял это сам, но в документации по этой функции указано, что коэффициент попадания в кэш составляет 35 процентов, а это весьма неплохой показатель, если учитывать то, что кэш состоит только из одной структуры VMA. Безусловно, этому способствует широко известное свойство, которое часто называют «локализацией ссылок»: согласно этому принципу программное обеспечение, как правило, обращается к данным (и командам), расположенным рядом с недавно использованными данными (и командами). Поскольку VMA содержит ряд смежных адресов, локализация ссылок способствует повышению вероятности того, что необходимые адреса будут находиться в той же области VMA, которая удовлетворяла предыдущему запросу.
При модификации списка VMA это значение кэша в нескольких других местах устанавливается в NULL для указания на то, что изменения в списке VMA могли сделать содержимое кэша недействительным. По крайней мере, в одном из этих случаев, в строке , очистка кэша иногда может не потребоваться; сделав этот код немного интеллектуальнее, можно существенно повысить коэффициент попадания в кэш.
Этот маленький кэш не применяется. Если дерево AVL не существует, функция find_vma просто проходит по всем структурам VMA в списке, возвращая первую из них, которая соответствует условию. Помните, что этот список структур VMA находится в отсортированном порядке, поэтому первая же область VMA, которая соответствует условию, представляет собой область VMA с наименьшим адресом, являющуюся таковой. Если функция выходит за конец списка, не найдя соответствия, переменная vma устанавливается в NULL и возвращается именно это значение.
При наличии достаточно большого количества областей VMA прохождение по дереву становится быстрее, чем перебор связанного списка; поскольку деревья AVL сбалансированы, это операция с логарифмическими, а не линейными затратами времени. Итеративное прохождение по дереву встречается не так уж редко, но эта структура обладает некоторыми особенностями, которые не сразу бросаются в глаза. Прежде всего, обратите внимание на присваивание в строке ; в ней отслеживается наилучший узел, найденный до сих пор, поэтому будет возвращен именно он, если не нашлось ничего лучшего. Проверка if в следующей строке— это оптимизация для проверки того, лежит ли addr полностью в пределах VMA (мы уже знаем, что к этому моменту addr меньше значения vm_end для данной области VMA). Поскольку области VMA никогда не перекрываются, не существует другой, более подходящей области VMA, поэтому можно сразу же прекратить обход дерева.
Если во время обхода дерева или просмотра списка была найдена область VMA, полученное значение сохраняется в кэше до следующего поиска.
В любом случае возвращается значение vma; оно может быть равным NULL или может указывать на первую область VMA, которая удовлетворяет условию поиска.
