赤黒木3(insert_vm_struct)


find_vma_prepare()で以下の接続ポインタの赤黒木/双方向リストに登録するための必要な位置情報を取得し、__vma_link()でリストします。
・prevは昇順リストの直前のノードのポインタ
・rb_linkは赤黒木の親ノードの左右に接続する子ノードのポインタ
・rb_parentは赤黒木の親ノードのポインタ
static void
__insert_vm_struct(struct mm_struct * mm, struct vm_area_struct * vma)
{
       struct vm_area_struct * __vma, * prev;
       struct rb_node ** rb_link, * rb_parent;

       __vma = find_vma_prepare(mm, vma->vm_start,&prev, &rb_link, &rb_parent);
       if (__vma && __vma->vm_start < vma->vm_end)
               BUG();
       __vma_link(mm, vma, prev, rb_link, rb_parent);
       mark_mm_hugetlb(mm, vma);
       mm->map_count++;
       validate_mm(mm);
}
__vma_link_list()は、 prev->vm_nextに接続とするvmaの昇順リスト、
__vma_link_rb()は、rb_parentを親として、rb_parentの接続子ノードのrb_linkに接続する赤黒木
__vma_link_file()は、vmaがファイルマップならinode->i_mappingのアドレススペースをvma->sharedをヘッドとする双方向リストに接続します。
__vma_link(struct mm_struct *mm, struct vm_area_struct *vma,
       struct vm_area_struct *prev, struct rb_node **rb_link,
       struct rb_node *rb_parent)
{
       __vma_link_list(mm, vma, prev, rb_parent);
       __vma_link_rb(mm, vma, rb_link, rb_parent);
       __vma_link_file(vma);
}
find_vma_prepare()はfind_vma()と同じように、addrのvm_area_structを取得(あれば)しますが、同時に昇順リストの直前vm_area_structと、赤黒木の親の右/左子のどちらに接続されているかの情報(接続ポインタを取得すれば右左は関係ありません。)も取得します。

赤黒木のノードの左パス配下のノードは全て、親ノードより小さく、右パスのそれは親ノードより大きいと言うことで、従ってノードが親の右子ノードに接続されれば、その親ノードが昇順リストの直前のノードとなり、以降その左パスに接続されるなら、直前のノードは、最初に右に接続された親ノードであり続けるわけです。
・親ノード<右子ノードの左子ノードの左子ノード<右子ノードの左子ノード<右子ノード

mm_structのルートからaddrの大小に応じて右左パスを、そして、addrのvmaがなければ、赤黒木の終端(*__rb_link==NULL)まで走査していき、addrのvmaが接続される親をrb_parent、また接続される親の右か左かをrb_linkに設定し、右子ノードを親とするタイミングでrb_prevをその親とします。。
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)
{
       struct vm_area_struct * vma;
       struct rb_node ** __rb_link, * __rb_parent, * rb_prev;

       __rb_link = &mm->mm_rb.rb_node;
       rb_prev = __rb_parent = NULL;
       vma = NULL;

       while (*__rb_link) {
               struct vm_area_struct *vma_tmp;

               __rb_parent = *__rb_link;
               vma_tmp = rb_entry(__rb_parent, struct vm_area_struct, vm_rb);

               if (vma_tmp->vm_end > addr) {
                       vma = vma_tmp;
                       if (vma_tmp->vm_start <= addr)
                               return vma;
                       __rb_link = &__rb_parent->rb_left;
               } else {
                       rb_prev = __rb_parent;
                       __rb_link = &__rb_parent->rb_right;
               }
       }

       *pprev = NULL;
       if (rb_prev)
               *pprev = rb_entry(rb_prev, struct vm_area_struct, vm_rb);
       *rb_link = __rb_link;
       *rb_parent = __rb_parent;
       return vma;
}
昇順リスト
static inline void
__vma_link_list(struct mm_struct *mm, struct vm_area_struct *vma,
               struct vm_area_struct *prev, struct rb_node *rb_parent)
{
       if (prev) {
               vma->vm_next = prev->vm_next;
               prev->vm_next = vma;
       } else {
               mm->mmap = vma;
               if (rb_parent)
                       vma->vm_next = rb_entry(rb_parent,
                                       struct vm_area_struct, vm_rb);
               else
                       vma->vm_next = NULL;
       }
}
赤黒木
static void __vma_link_rb(struct mm_struct *mm, struct vm_area_struct *vma,
                       struct rb_node **rb_link, struct rb_node *rb_parent)
{
       rb_link_node(&vma->vm_rb, rb_parent, rb_link);
       rb_insert_color(&vma->vm_rb, &mm->mm_rb);
}
ファイルマップドリスト
static inline void __vma_link_file(struct vm_area_struct *vma)
{
       struct file * file;

       file = vma->vm_file;
       if (file) {
               struct inode * inode = file->f_dentry->d_inode;
               struct address_space *mapping = inode->i_mapping;

               if (vma->vm_flags & VM_DENYWRITE)
                       atomic_dec(&inode->i_writecount);

               if (vma->vm_flags & VM_SHARED)
                       list_add_tail(&vma->shared, &mapping->i_mmap_shared);
               else
                       list_add_tail(&vma->shared, &mapping->i_mmap);
       }
}

最終更新 2014/07/18 18:15:21 - north
(2014/07/18 18:15:21 作成)


検索

アクセス数
3697898
最近のコメント
コアダンプファイル - sakaia
list_head構造体 - yocto_no_yomikata
勧告ロックと強制ロック - wataash
LKMからのファイル出力 - 重松 宏昌
kprobe - ななし
ksetの実装 - スーパーコピー
カーネルスレッドとは - ノース
カーネルスレッドとは - nbyst
asmlinkageってなに? - ノース
asmlinkageってなに? - よろしく
Adsense
広告情報が設定されていません。