【内核】Linux 2.6 内存反向映射机制 Reverse Mapping

作者: visayafan
发布时间:2015-07-01 16:34:12

1、为什么要使用反向映射

  物理内存的分页机制,一个PTE(Page Table Entry)对应一个物理页,但一个物理页可以由多个PTE与之相对应,当该页要被回收时,Linux2.4的做法是遍历每个进程的所有PTE判断该PTE是否与该页建立了映射,如果建立则取消该映射,最后无PTE与该相关联后才回收该页。该方法显而易见效率极低,因为其为了查找某个页的关联PTE遍历了所有的PTE,我们不禁想:如果把每个页关联的PTE保存在页结构里面,每次只需要访问那些与之相关联的PTE不很方便吗?确实,2.4之后确实采用过此方法,为每个页结构(Page)维护一个链表,这样确实节省了时间,但此链表所占用的空间及维护此链表的代价很大,在2.6中弃之不用,但反向映射机制的思想不过如此,所以还是有参考价值的,可以参考:http://blog.csdn.net/dog250/article/details/5303581


2、Linux2.6中是如何实现反向映射

  (以下代码均来自内核版本2.6.11.)

2.1 与RM(Reverse Mapping)相关的结构

page, address_space, vm_area_struct, mm_struct, anon_vma.

 以下均显示部分成员:

struct page{
  struct address_space *mapping; /* address_space类型,为对齐需要,其值为4的位数,所以最低两位无用,为充分利用资源,所以此处利用此最低位。
* 最低位为1表示该页为匿名页,并且它指向anon_vma对象。
* 最低为0表映射页,此时mapping指向文件节点地址空间。
*/
atomic_t _mapcount; /* 取值-1时表示没有指向该页框的引用,
取值0时表示该页框不可共享
取值大于0时表示该页框可共享表示有几个PTE引用
*/
  pgoff_t index;
};




struct mm_struct {
pgd_t * pgd;
}

 

struct vm_area_struct {
struct list_head anon_vma_node; /* Serialized by anon_vma->lock */
struct anon_vma *anon_vma; /* Serialized by page_table_lock */
}

 

struct anon_vma {
spinlock_t lock; /* Serialize access to vma list */
struct list_head head; /* List of private "related" vmas */
};


2.2 进程地址空间

 

 1. 每个进程有个进程描述符task_struct,其中有mm域指向该进程的内存描述符mm_struct。

 2. 每个进程都拥有一个内存描述符,其中有PGD域,指向该进程地址空间的全局页目录;mmap域指向第一个内存区域描述符vm_area_strut1。

 3. 进程通过内存区域描述符vm_area_struct管理内存区域,每个内存区域描述符都有vm_start和vm_end域指向该内存区域的在虚拟内存中的起始位置;vm_mm域指向该进程的内存描述符;每个vm_area_struct都有一个anon_vma域指向该进程的anon_vma;

 4. 每个进程都有一个anon_vma,是用于链接所有vm_area_struct的头结点,通过vm_area_struct的anon_vma_node构成双循环链表。

 最终形成了上图。


 现在假设我们要回收一个页,我们要做的是访问所有与该页相关联的PTE并修改之取消二者之间的关联。与之相关联的函数为:try_to_unmap。


2.3 try_to_unmap

2.3.1 try_to_unmap函数及PageOn宏 分析

int try_to_unmap(struct page *page)
{
int ret;

BUG_ON(PageReserved(page));
BUG_ON(!PageLocked(page));

/*判断是不是匿名页,若是的话执行try_to_unmap_anon函数,否则的话执行try_to_unmap_file函数*/
if (PageAnon(page)) // PageAnon函数分析在下面
ret = try_to_unmap_anon(page);
else
ret = try_to_unmap_file(page);

if (!page_mapped(page))
ret = SWAP_SUCCESS;
return ret;
}

static inline int PageAnon(struct page *page)
{
return ((unsigned long)page->mapping & PAGE_MAPPING_ANON) != 0;
/* #define PAGE_MAPPING_ANON 1 此函数非常easy,就是判断page的mapping成员的末位是不是1,是的话返回1,不是的话返回0*/

}


2.3.2 try_to_unmap_anon函数及page_lock_anon_vma函数及list_for_each_entry宏 分析

 还没开始看文件系统一节,所以try_to_unmap_file没看懂,所以此处只分析 try_to_unmap_anon函数,等看完vfs后再来补充吧。

static int try_to_unmap_anon(struct page *page)
{
struct anon_vma *anon_vma;
struct vm_area_struct *vma;
int ret = SWAP_AGAIN;

anon_vma = page_lock_anon_vma(page); /* 获取该匿名页的anon_vma结构
* page_lock_anon_vma函数分析在下面。
*/
if (!anon_vma)
return ret;

list_for_each_entry(vma, &anon_vma->head, anon_vma_node) { /* 循环遍历
* list_for_each_entry分析在下面
* anon_vma就是上图中anon_vma的指针,anon_vma->head得到其head成员(是list_head)类型,
* 其next值便对应上图中vm_area_struct1中的anon_vma_node中的head。
* vma 是vm_area_struct类型的指针,anon_vma_node为typeof(*vma)即vm_area_struct中的成员。
* 到此便可以开始双链表循环
*/
ret = try_to_unmap_one(page, vma); // 不管是调用try_to_unmap_anon还是try_to_unmap_file最终还是回到try_to_unmap_one上
if (ret == SWAP_FAIL || !page_mapped(page))
break;
}
spin_unlock(&anon_vma->lock);
return ret;
}

static struct anon_vma *page_lock_anon_vma(struct page *page)
{
struct anon_vma *anon_vma = NULL;
unsigned long anon_mapping;

rcu_read_lock();
anon_mapping = (unsigned long) page->mapping;
if (!(anon_mapping & PAGE_MAPPING_ANON))
goto out;
if (!page_mapped(page))
goto out;
// 前面已经提到,mapping最低位为1时表匿名页,此时mapping是指向anon_vma指针,故此处-1后强制转化为struct anon_vma指针类型,并返回该值。
anon_vma = (struct anon_vma *) (anon_mapping - PAGE_MAPPING_ANON);
spin_lock(&anon_vma->lock);
out:
rcu_read_unlock();
return anon_vma;
}

/* 参数含义:
* head是list_head指针,无非此处需要的第一个list_head是head->next
* pos是个指向包含list_head的结构体的指针,可以用typeof(*pos)解引用来得到此结构体
* member 是list_head在typeof(*pos)中的名称
* 这样pos = list_entry((head)->next, typeof(*pos), member)第一次便初始化pos为指向包含head->next指向的那个结构体的指针。
* 之后便是双循环链表遍历了
*/
#define list_for_each_entry(pos, head, member) \
for (pos = list_entry((head)->next, typeof(*pos), member); \ // list_entry分析在下面
prefetch(pos->member.next), &pos->member != (head); \
pos = list_entry(pos->member.next, typeof(*pos), member))

/* list_entry函数其实非常简单,其各参数的意义:
* ptr 指向list_head类型的指针
* type 包含list_head类型的结构体
* member list_head在type中的名称
* 返回值:包含ptr指向的list_head的类型为type的指针,即由list_head指针得到包含此list_head结构体的指针,实现也很简单,ptr减去member在type中的偏移即可
*/
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})

2.3.3 try_to_unmap_one函数及vma_address函数及pdg_offset宏 分析

 

Linux采用三级页表:

PGD:顶级页表,由pgd_t项组成的数组,其中第一项指向一个二级页表。

PMD:二级页表,由pmd_t项组成的数组,其中第一项指向一个三级页表(两级处理器没有物理的PMD)。

PTE:是一个页对齐的数组,第一项称为一个页表项,由pte_t类型表示。一个pte_t包含了数据页的物理地址。

 

static int try_to_unmap_one(struct page *page, struct vm_area_struct *vma)
{
struct mm_struct *mm = vma->vm_mm;
unsigned long address;
pgd_t *pgd;
pud_t *pud;
pmd_t *pmd;
pte_t *pte;
pte_t pteval;
int ret = SWAP_AGAIN;

if (!mm->rss)
goto out;
address = vma_address(page, vma); /* 通过页和vma得到线性地址
* vm_address函数解析在下面
*/
if (address == -EFAULT)
goto out;

/*
* We need the page_table_lock to protect us from page faults,
* munmap, fork, etc...
*/
spin_lock(&mm->page_table_lock); // 页表锁

pgd = pgd_offset(mm, address); /* 获得pdg
* pdg_offset通过内存描述符和线性地址得到pgd
* 该函数解析在下面
*/
if (!pgd_present(*pgd))
goto out_unlock;

pud = pud_offset(pgd, address); /* 获得pud
i386上应该是0吧?
*/
if (!pud_present(*pud))
goto out_unlock;

pmd = pmd_offset(pud, address); /* 获得pmd */
if (!pmd_present(*pmd))
goto out_unlock;

pte = pte_offset_map(pmd, address); /* 获得pte */
if (!pte_present(*pte))
goto out_unmap;

/* 有了pgd pmd pte 后我们便达到我们目的了 ===> 查找与页相关联系的页表项,找到后便可以进行修改了(如果是要换出该页的话则应该解除映射pte_unmap()函数)
* 但修改之前还要做些判断和处理
*/

//
if (page_to_pfn(page) != pte_pfn(*pte))
goto out_unmap;

/*
* If the page is mlock()d, we cannot swap it out.
* If it's recently referenced (perhaps page_referenced
* skipped over this mm) then we should reactivate it.
*/
if ((vma->vm_flags & (VM_LOCKED|VM_RESERVED)) ||
ptep_clear_flush_young(vma, address, pte)) {
ret = SWAP_FAIL;
goto out_unmap;
}

/*
* Don't pull an anonymous page out from under get_user_pages.
* GUP carefully breaks COW and raises page count (while holding
* page_table_lock, as we have here) to make sure that the page
* cannot be freed. If we unmap that page here, a user write
* access to the virtual address will bring back the page, but
* its raised count will (ironically) be taken to mean it's not
* an exclusive swap page, do_wp_page will replace it by a copy
* page, and the user never get to see the data GUP was holding
* the original page for.
*
* This test is also useful for when swapoff (unuse_process) has
* to drop page lock: its reference to the page stops existing
* ptes from being unmapped, so swapoff can make progress.
*/
if (PageSwapCache(page) &&
page_count(page) != page_mapcount(page) + 2) {
ret = SWAP_FAIL;
goto out_unmap;
}

/* Nuke the page table entry. */
flush_cache_page(vma, address);
pteval = ptep_clear_flush(vma, address, pte);

/* Move the dirty bit to the physical page now the pte is gone. */
if (pte_dirty(pteval))
set_page_dirty(page);

if (PageAnon(page)) {
swp_entry_t entry = { .val = page->private };
/*
* Store the swap location in the pte.
* See handle_pte_fault() ...
*/
BUG_ON(!PageSwapCache(page));
swap_duplicate(entry);
if (list_empty(&mm->mmlist)) {
spin_lock(&mmlist_lock);
list_add(&mm->mmlist, &init_mm.mmlist);
spin_unlock(&mmlist_lock);
}
set_pte(pte, swp_entry_to_pte(entry));
BUG_ON(pte_file(*pte));
mm->anon_rss--;
}

mm->rss--;
acct_update_integrals();
page_remove_rmap(page);
page_cache_release(page);

out_unmap:
pte_unmap(pte);
out_unlock:
spin_unlock(&mm->page_table_lock);
out:
return ret;
}



static inline unsigned long
vma_address(struct page *page, struct vm_area_struct *vma)
{
pgoff_t pgoff = page->index << (PAGE_CACHE_SHIFT - PAGE_SHIFT); /* PAGE_CACHE_SHIFT - PAGE_SHIFT值为0,其实就是把page->index赋给pgoff
* 至于为什么要这样右移一下,我也不清楚
*/
unsigned long address;
address = vma->vm_start + ((pgoff - vma->vm_pgoff) << PAGE_SHIFT); /* page->index是页的偏移
* vma->vm_pgoff是内存区域首地址的偏移,都是以页为单位
* 相减后再<<PAGE_SHIFT便得到页在内存区域的中的偏移
* 再+vma->vma_start便得到页在内存区域中的地址
*/
if (unlikely(address < vma->vm_start || address >= vma->vm_end)) { /* 得到的地址应该在vm->vm_start和vm_end之间,否则报错 */
/* page should be within any vma from prio_tree_next */
BUG_ON(!PageAnon(page));
return -EFAULT;
}
return address;
}

#define PGDIR_SHIFT 22 // 在i386机子上线性地址0-11位表PTE,12-21表PMD,22-31位表PGD,即线性地址右移22位的结果为其在全局页目录的偏移
#define PTRS_PER_PGD 1024 // 因PGD共10位,所以其最多可以有2^10=1024个全局描述符项

#define pgd_index(address) (((address) >> PGDIR_SHIFT) & (PTRS_PER_PGD-1)) // 得到线性地址address在全局页目录里面的偏移
#define pgd_offset(mm, address) ((mm)->pgd+pgd_index(address)) // 再加上全局描述符基地址(存储在内存描述符mm_struct中的pdg域)后便得到其在全局描述符中的具体位置





标签: App Linux
来源:http://www.cnblogs.com/visayafan/archive/2011/12/24/2300758.

推荐: