vm_area_structの探索関数(find_vma_**関数群)について

はじめに

"Understanding the Linux Kernel"(version. 2.6.11)のch.9 Process Address Spaceのvm_area_structを探索する関数群:

  • find_vma(struct mm_struct * mm, unsigned long addr)
  • find_vma_prev(struct mm_struct *mm, unsigned long addr, struct vm_area_struct **pprev)
  • find_vma_preparefind_vma_prepare(struct mm_struct *mm, unsigned long addr, struct vm_area_struct **pprev, struct rb_node ***rb_link, struct rb_node ** rb_parent)
  • find_vma_intersection(struct mm_struct * mm, unsigned long start_addr, unsigned long end_addr)

あたりをまとめる。

何れの関数もaddrを引数にとって、それに対応するstruct vm_area_structを返すが、必ずしもvma->vm_start <= addr < vma->vm_endとなるような(struct vm_area_struct)vmaを見つける関数ではなく、理解が難しいところだ。

その後、find_vma_**関数群のユースケースもまとめておきたい。

準備

記法

数学では、閉集合、開集合の記号として、[, ], (, )を用いることがある。例えば、

  • ○ < x < △ ==> x in (○, △)
  • ○<= x < △ ==> x in [○, △)
  • ○< x <= △ ==> x in (○, △]

といった具合。本記事では、この記法に沿うことにする。

red black tree

find_vma系の関数はaddrが与えられたとき、mm_struct(大体はcurrent->mmで与えられる変数)から、所要のvm_area_structを検索する関数である(mm_structがprocessごとのvirtual memoryの管理をする構造体で、vm_area_structがどの領域を使用しているかを表すので、(mm_struct):(vm_area_struct)は1:nの関係。)

f:id:knknkn11626:20190729170330p:plain
Figure9.2

上記のイメージに沿って、最も高位のaddressの範囲のvm_area_structを「一番右端のvm_area_struct」と表現することにする。同様に、「一番左端のvm_area_struct」といえば、最も低位のaddressの範囲のvm_area_structを指すことにする。

このとき、個々のvm_area_structとの間が双方向リストで表現されていると線形探索(O(n))となる。しかしながら一般に木構造を用いればO(log_2(n))で探索できるので、双方向リストでの検索はnが大きくなると効率が悪い。そこで、vm_area_structの中に、struct rb_node vm_rb;をembedして2分木探索のノードを表現している。linux kernel(2.6.11)では、赤黒木(red-black tree)を採用している。

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. */
        // skip

    struct rb_node vm_rb;
        // skip
}

任意のstruct rb_node* rb_nodeがあったときに、vma = container_of(rb_node, struct vm_area_struct, vm_rb);とすることで、rb_nodeを所有しているvm_area_structのオブジェクトを発見できるので、vm_rbはポインタ型ではなくstruct rb_node構造体そのものがembedされている必要がある。

red-black treeのアルゴリズムは、"Understanding the Linux Kernel" ch.9の"Memory Region Data Structures"の節に概要が書いてあるので、本記事では省略する。

find_vma関数群

Note) 一応4つとも解説しましたが、find_vmaだけ抑えていれば、コード自体は追えるのではないかと思います。

find_vma

https://kernel.googlesource.com/pub/scm/linux/kernel/git/stable/linux-stable/+/refs/heads/linux-2.6.11.y/mm/mmap.c#1357 の部分。

find_vmaのロジックは以下の4通りに分けられる(ややこしい..)。

1: vma = mm->mmap_cache;が返される場合((vma && vma->vm_end > addr && vma->vm_start <= addr)がtrueの場合)。このとき、addrは[vma->vm_start, vma->vm_end)の範囲に含まれる。一番素直な場合。

2: addrが一番右端のvm_area_structよりも高位のアドレスにある場合。このとき、https://kernel.googlesource.com/pub/scm/linux/kernel/git/stable/linux-stable/+/refs/heads/linux-2.6.11.y/mm/mmap.c#1383 にヒットし続けるので、vma=NULLのママとなり、NULLが返される:

f:id:knknkn11626:20190729174206j:plain
2の場合(rightmostのvm_area_structよりもaddrが大きい場合)

3: mm_structの中で、addrが[vma->vm_start, vma->vm_end)の範囲に含まれるようなvm_area_structが存在した場合。このとき、break文で抜けるので、このvmaが戻り値となる。

4: 3と違って、mm_structの中で、addrが[vma->vm_start, vma->vm_end)の範囲に含まれるようなvm_area_structが存在しなかった場合。4が一番ややこしい。この場合は、3のbreak文を抜けずにwhile文の条件がfalse(rb_node=nullでwhile (rb_node)がfalse)となる。このとき、一度はwhileの中のif文がtrueとなっているので、nullが返されることはなく、直前にvma = vma_tmp;のように代入されたvmaが返される。以下の図のようになる。

f:id:knknkn11626:20190729173900j:plainf:id:knknkn11626:20190729173915j:plain
4の場合(leftmostの場合、および2つのvm_area_structの間に挟まる場合)

1, 3については、[vma->vm_start, vma->vm_end)の範囲にaddrが含まれるようなvm_area_structを返しますよ、といっているだけなのでほぼ同じ。

find_vmaユースケース

上記の4つのパターンから言えることは、find_vmaがnullでない場合1,3と4の場合があるというわけだ。上で見たように、

  • 1,3はaddrがvm_area_structの範囲内にある場合、

  • 4はaddrがvm_area_structの範囲に入らなかった場合

であり、意味合いがかなり異なる。

そこで、vma = find_vma(mm, addr);を使用した後、更に以下の条件分岐を施す場合がある。ここでlen[addr, addr+len)を表現するために用いることとする:

  • addr > vma->vm_start : 1,3の場合(vma && addr > vma->vm_startと書くとより厳密な判定)

  • addr + len <= vma->vm_start : 4の場合で且つ、[addr, addr+len)というoverlapしない領域を確保できる場合(下図)

f:id:knknkn11626:20190729180503j:plain

  • (!vma || addr + len <= vma->vm_start): [addr, addr+len)というoverlapしない領域を確保できる場合(2の場合はその先にvm_area_struct構造体がないので問題なく確保できることに注意)

find_vma_intersection

find_vma_intersectionはfind_vmaの補助関数で、以下のような関数である:

/* Look up the first VMA which intersects the interval start_addr..end_addr-1,
   NULL if none.  Assume start_addr < end_addr. */
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)
        vma = NULL;
    return vma;
}

start_addr < end_addrを仮定すると、以下の図の場合(4の場合で[start_addr, end_addr)がfind_vmaで得られた範囲とintersectする場合)にのみnullでない戻り値が得られる:

f:id:knknkn11626:20190729181633j:plain
4の場合で[start_addr, end_addr)がfind_vmaで得られた範囲とintersectする場合

1,3の場合は、vma->vm_start <= start_addr < vma->vm_endとなるため、必然的にif文がfalseになる -> nullが返されることに注意しよう。

この関数はsys_brkで

 /* Check against existing mmap mappings. */
    if (find_vma_intersection(mm, oldbrk, newbrk+PAGE_SIZE))
        goto out;

という形で使われているだけなので、大したことない。

find_vma_prev

コード -> https://kernel.googlesource.com/pub/scm/linux/kernel/git/stable/linux-stable/+/refs/heads/linux-2.6.11.y/mm/mmap.c#1396

find_vmaは引数のaddrより先のvm_area_structを返すのだった。一方、find_vma_prevはaddrの直前のvm_area_structをpprevという引数に格納し、addrの直後のvm_area_structを戻り値として返す。

結果的に、挙動はfind_vmaとおなじになるが、addrより直前のノードのpprevの情報が入手できる。

この関数の内部実装ではfind_vmaを使用していないので、find_vmaの節と同じように場合分けしてみる:

1: addrが一番左端のvm_areaより低位にある場合。このとき、ifの条件分岐が一度だけtrueになった後はwhileを抜けるので以下の図のようになる:

f:id:knknkn11626:20190729183249j:plain
1の場合

以下のような場合も1の場合にふくまれる:

f:id:knknkn11626:20190729184814j:plain
1の場合

2: 下の図のような場合。一度はif文がfalseになるので。

f:id:knknkn11626:20190729184546j:plainf:id:knknkn11626:20190729184549j:plain
vm_areaの間に挟まってるか、vm_areaの中にあるか

以下のような場合も2に当てはまる

f:id:knknkn11626:20190729185703j:plain
2,3の場合

上の場合、(addr < prev->vm_next->vm_end)の条件が当てはまり,while文を抜けることも、rb_node=NULLになり抜けることもある。

3: if (!prev->vm_nextがtrueになり、抜ける場合

f:id:knknkn11626:20190729185855j:plain
3の場合

--

Note) こうしてみると様々な場合があるが、pprevは必ずaddrの直前のvm_area_structになる。これは、https://kernel.googlesource.com/pub/scm/linux/kernel/git/stable/linux-stable/+/refs/heads/linux-2.6.11.y/mm/mmap.c#1417addr >= prev->vm_endが保証されているため。

次にfind_vma_prevのユースケースも見ておく。

find_vma_prevのユースケース

vma = find_vma_prev(mm, addr, &prev);としておく。ここでlen[addr, addr+len)を表現するために用いることとする:

  • vma && (vma->vm_start <= addr) : addrがprevとvma(prevの直後)の間にある場合。
  • !vma: 3の場合(addrが一番右端のvm_area_structより高位の場合)

  • vma && vma->vm_start >= addr+len: [addr, addr+len)の範囲がprevとvma(prevの直後)の間にある場合。

find_vma_prepare

static struct vm_area_struct *
find_vma_prepare(struct mm_struct *mm, unsigned long addr,
        struct vm_area_struct **pprev, struct rb_node ***rb_link,
        struct rb_node ** rb_parent)

一番ややこしいが、find_vma_prevよりさらに、直前の状態を返すためにrb_linkやrb_parentを引数としておいているだけだ。

https://kernel.googlesource.com/pub/scm/linux/kernel/git/stable/linux-stable/+/refs/heads/linux-2.6.11.y/mm/mmap.c#321 ではvma_tmp->vm_end <= addrが保証されてるので、pprevはaddrの直前のノードが入る。


結論としては、find_vmaがどのような挙動であるかを抑えておけば、find_vma_prevとかも似たような感じなので、その場で対応できそう。