Traversing a VMA red-black tree in Linux

void dfs(struct rb_node *node)
{
	struct vm_area_struct *vma;
	vma = rb_entry(node, struct vm_area_struct, vm_rb);
	trace_printk("VMA: [0x%px - 0x%px]", (void *)vma->vm_start, (void *)vma->vm_end);

	if (node->rb_left)
		dfs(node->rb_left);
	if (node->rb_right)
		dfs(node->rb_right);
}

Each entry of /proc/$PID/maps is a VMA (Virtual Memory Area) of the task’s user memory address space, described by a struct vm_area_struct inside the Linux kernel. One way to organize these VMAs is using a red-black tree (rbtree). AFAIK each task has its own rbtree. Today I pre-order DFS’d such an rbtree.

I did (inside my Linux kernel) dfs(current->mm->mm_rb.rb_node); (remember to tracing_on() and tracing_off() before and after it) then I got something like the following when I did grep VMA /sys/kernel/debug/tracing/trace:

/* VMA: [0x00000000004bf000 - 0x00000000004c2000] */
  /* VMA: [0x0000000000401000 - 0x0000000000497000] */
    /* VMA: [0x0000000000400000 - 0x0000000000401000] */
    /* VMA: [0x0000000000497000 - 0x00000000004be000] */
  /* VMA: [0x00007ffe09d55000 - 0x00007ffe09d76000] */
    /* VMA: [0x00000000004c5000 - 0x00000000004c6000] */
      /* VMA: [0x00000000004c2000 - 0x00000000004c5000] */
      /* VMA: [0x000000000073d000 - 0x0000000000760000] */
    /* VMA: [0x00007ffe09db3000 - 0x00007ffe09db4000] */
      /* VMA: [0x00007ffe09daf000 - 0x00007ffe09db3000] */

[vsyscall] is not a VMA.

Yeah, as you see, a BST rooted at 0x4bf000. Kernel functions including find_vma() use this (find_vma() looks up vmcache first, though).

---