Книга: Разработка ядра Linux

Функция find_vma()

Функция find_vma()

Функция find_vma() определена в файле mm/mmap.c.

Эта функция позволяет найти в заданном адресном пространстве ту первую область памяти, для которой значение поля vm_end больше заданного адреса addr. Другими словами, эта функция позволяет найти первую область памяти, которая содержит адрес addr или начинается с адреса, большего адреса addr. Если такой области памяти не существует, то функция возвращает значение NULL.

В противном случае возвращается указатель на соответствующую структуру vm_area_struct. Обратите внимание, что найденная область VMA может начинаться с адреса, большего адреса addr, и этот адрес не обязательно принадлежит найденной области памяти. Результат выполнения функции find_vma() кэшируется в поле map_cache дескриптора памяти. Поскольку очень велика вероятность того, что после одной операции с областью памяти последуют еще операции с ней же, то процент попаданий в кэш получается достаточно большим (на практике получаются значения порядка 30-40%). Проверка кэшированных результатов выполняется очень быстро. Если нужный адрес в кэше не найден, то выполняется поиск по всем областям памяти, связанным с заданным дескриптором. Этот поиск выполняется с помощью красно-черного дерева следующим образом.

struct vm_area_struct* find_vma(struct mm_struct *mm,
 unsigned long addr) {
 struct vm_area_struct *vma = NULL;
 if (mm) {
  vma = mm->mmap_cache;
  if (!(vma && vma->vm_end > addr && vma->vm_start <= addr)) {
   struct rb_node* rb_node;
   rb_node = mm->mm_rb.rb_node;
   vma = NULL;
   while (rb_node) {
    struct vm_area_struct* vma_tmp;
    vma_tmp =
     rb_entry(rb_node, struct vm_area_struct, vm_rb);
    if (vma_tmp->vm_end > addr) {
     vma = vma_tmp;
     if (vma_tmp->vm_start <= addr)
      break;
     rb_node = rb_node->rb_left;
    } else
     rb_node = rb_node->rb_right;
   }
   if (vma)
    mm->mmap_cache = vma;
  }
 }
 return vma;
}

Вначале выполняется проверка поля vma_cache на предмет того, содержит ли кэшированная область VMA необходимый адрес. Обратите внимание, что простая проверка того, является ли значение поля vm_end большим addr, не гарантирует что проверяемая область памяти является первой, в которой есть адреса, большие addr. Поэтому, для того чтобы кэш в этой ситуации оказался полезным, проверяемый адрес должен принадлежать кэшированной области памяти. К счастью, это как раз и соответствует случаю выполнения последовательных операций с одной и той же областью VMA.

Если кэш не содержит нужную область VMA, то функция должна выполнять поиск по красно-черному дереву. Это выполняется путем проверки узлов дерева. Если значение поля vma_end для области памяти текущего узла больше addr, то текущим становится левый дочерний узел, в противном случае — правый. Функция завершает свою работу, как только находится область памяти, которая содержит адрес addr. Если такая область VMA не найдена, то функция продолжает поиск по дереву и возвращает ту область памяти, которая начинается после адреса addr. Если вообще не найдена ни одна область памяти, то возвращается значение NULL.

Оглавление книги