Chapter 4: Virtual Process Memory
/* (Cache hit rate is typically around 35%.) */
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;
}The kernel first checks whether the region last processed and now held inmm->mmap_cachecontains the
required address — that is, whether its end is after the required address and its start is before. If so, the
kernel does not execute theifblock and immediately returns the pointer to the region.
If not, the red-black tree must be searched step by step.rb_nodeis the data structure used to represent
each node in the tree.rb_entryenables the ‘‘useful data‘‘ (in this case, an instance ofvm_area_struct)
to be removed from the node.
The root element of the tree is located inmm->mm_rb.rb_node. If the end address of the associated region
is less than the required address and the start address is greater than the required address, the kernel has
found the appropriate element and can exit thewhileloop to return a pointer to thevm_area_struct
instance. Otherwise, the search is resumed at the
❑ left childif the end address of the current region isafterthe required address,or at the
❑ right childif the end address of the region isbeforethe required address.As the root elements of the tree have null pointers as child elements, it is easy for the kernel to decide
when to terminate the search and return a null pointer as an error message.
If a suitable region is found, a pointer to it is stored inmmap_cachebecause there is a strong likelihood
that the nextfind_vmacall will search for a neighboring address in the same region.