Associating Virtual Addresses with a Region

By reference to a virtual address, find_vma finds the first region in user address space whose end is after the given address and therefore satisfies the addr < vm_area_struct->vm_end condition. As parameters, the function requires not only the virtual address (addr) but also a pointer to the mm_struct instance of the relevant process whose address space is to be scanned.

struct vm_area_struct * find_vma(struct mm_struct * mm, unsigned long addr) {

struct vm_area_struct *vma = NULL;

/* (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;

struct vm_area_struct * vma_tmp;

vma_tmp = rb_entry(rb_node, struct vm_area_struct, vm_rb);

return vma;

The kernel first checks whether the region last processed and now held in mm->mmap_cache contains 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 the if block and immediately returns the pointer to the region.

If not, the red-black tree must be searched step by step. rb_node is the data structure used to represent each node in the tree. rb_entry enables the ''useful data'' (in this case, an instance of vm_area_struct) to be removed from the node.

The root element of the tree is located in mm->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 the while loop to return a pointer to the vm_area_struct instance. Otherwise, the search is resumed at the

□ left child if the end address of the current region is after the required address, or at the

□ right child if the end address of the region is before the 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 in mmap_cache because there is a strong likelihood that the next find_vma call will search for a neighboring address in the same region.

find_vma_intersection is another helper function to establish whether an interval bounded by start_ addr and end_addr is fully within an existing region. It builds on find_vma and is easily implemented as follows:

static inline struct vm_area_struct * find_vma_intersection(struct mm_struct * mm, unsigned long start_addr, unsigned long end_addr)

struct vm_area_struct * vma = find_vma(mm,start_addr);

if (vma && end_addr <= vma->vm_start)

Continue reading here: Merging Regions

Was this article helpful?

0 0