はじめに
"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の関係。)
上記のイメージに沿って、最も高位の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
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が返される：
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が返される。以下の図のようになる。
1, 3については、[vma->vm_start, vma->vm_end)の範囲にaddrが含まれるようなvm_area_structを返しますよ、といっているだけなのでほぼ同じ。
find_vmaのユースケース
上記の4つのパターンから言えることは、find_vmaがnullでない場合1,3と4の場合があるというわけだ。上で見たように、
であり、意味合いがかなり異なる。
そこで、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しない領域を確保できる場合(下図)
(!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でない戻り値が得られる：
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
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を抜けるので以下の図のようになる：
以下のような場合も1の場合にふくまれる：
2: 下の図のような場合。一度はif文がfalseになるので。
以下のような場合も2に当てはまる
上の場合、(addr < prev->vm_next->vm_end)の条件が当てはまり,while文を抜けることも、rb_node=NULLになり抜けることもある。
3: if (!prev->vm_nextがtrueになり、抜ける場合
--
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#1417 でaddr >= prev->vm_endが保証されているため。
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とかも似たような感じなので、その場で対応できそう。
