仮想メモリ領域は、プロセス毎のmm_struct(current->mm)に、mm_struct.mm_rbをルートとする赤黒木でリスト管理されます。

struct mm_struct {
       struct vm_area_struct * mmap;           /* list of VMAs */
       struct rb_root mm_rb;
       struct vm_area_struct * mmap_cache;     /* last find_vma result */
       int map_count
 :
};

struct vm_area_struct {
       struct mm_struct * vm_mm;       /* The address space we belong to. */
       unsigned long vm_start;         /* Our start address within vm_mm. */
       unsigned long vm_end;           /* The first byte after our end address
                                          within vm_mm. */

       struct vm_area_struct *vm_next, *vm_prev;

       pgprot_t vm_page_prot;          /* Access permissions of this VMA. */
       unsigned long vm_flags;         /* Flags, see mm.h. */

       struct rb_node vm_rb;
  :
};

find_vma()は、struct mm_struct current->mmの指定するアドレスのvm_area_structを取得します。

mm->mmap_cacheでないなら、赤黒木のルートのmm->mm_rbから検索します。赤黒木から取得したvm_area_structのアドレスとの大/小をチェックすることで、次のノードが右か左かとして、走査します。

再度同じvm_area_structが検索される可能性が高いため、取得したvm_area_structをmm->mmap_cacheに設定しておきます。

rb_entryマクロはlist_headマクロと同じで、メンバーとしてのptrの構造体のアドレスを返すだけで、 rb_nodeのアドレスからstruct vm_area_structのメンバーvm_rbの位置のオフセットを引けば、その先頭。すなわち、rb_nodeの属するstruct vm_area_structが取得できます。

#define rb_entry(ptr, type, member) container_of(ptr, type, member)

struct rb_node
{
       unsigned long  rb_parent_color;
       struct rb_node *rb_right;
       struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));

struct rb_root
{
       struct rb_node *rb_node;
};

struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
{
       struct vm_area_struct *vma = NULL;

       if (mm) {
               /* Check the cache first. */
               /* (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;
}

補足

struct mm_structのmmapには、vm_area_structが昇順にリストされています。（vm_area_structの仮想空間）vm_area_structをインサートする場合、前後のvm_area_structとアドレスが連続する場合、１つのvm_area_structに連結するため、vm_area_structの前後のvm_area_structも必要なためです。赤黒木は目的とするvm_area_structと連続するvm_area_structはリスト的に連続となりません。違うノードのパス下にあることも。そのため昇順のリストのvm_area_structも必要となります。