Linux存储管理机制分析.doc

g200518029 谭志远 linux存储管理机制分析北京工业大学软件学院谭志远g200518029目录摘要2关键字21、数据结构表及变量说明31.1、数据结构及变量表31.2、数据结构描述32、完成功能的主要函数表43、页面失效处理（有效性失效）代码框图44、程序段代码注释65、linux中存储器管理的相关概念及实现415.1、伙伴算法425.2、slab435.3、缓冲区445.4、地址映射机制445.5、进程的虚拟空间455.6、页故障的产生475.7、交换机制475.8、linux中新页框的分配方案485.9、缓冲区高速缓存485.10、刷新机制496、收获和感想497、参考文献50摘要作者针对linux 2.4.18版本中的memory.c文件进行了代码阅读和分析，通过阅读该文件进一步地理解了linux中的存储管理机制，尤其是页面失效处理在linux中的实现方式。作者把对源代码的分析和理解通过文字的形式在本文中整理、归纳出来。在文章中列出了一些与存储管理机制实现有关的数据结构和重要变量，了解这些数据结构和变量有助于对源代码的阅读和理解；除此以外，还给出了memory.c文件实现页面失效处理的主要函数。作者认为在开始分析源代码前对代码的执行流程有一个初步的理解是十分必要的，所在进入代码分析前以原理框图的显示介绍了代码的执行流程。最后，对linux存储管理的相关概念和实现方案进行了讲述，并且谈了一下作者在对memory.c文件进行了代码阅读和分析后的一些收获和感想。关键字页目录 中间页目录 页表 地址映射 页面分配1、数据结构表及变量说明1.1、数据结构及变量表主要数据结构或变量名具体含义struct page描述一个物理页框struct vm_area_struct描述一个进程地址空间vm_operations_struct对进程地址空间的一些操作struct free_area_struct主要用于描述buddy算法中的一个空闲页框 long max_mapnr是当前系统中物理内存的页面数目long num_physpages物理页面的数目void *high_memory 高端内存的地址指针struct page *highmem_start_page高位内存的起始页指针1.2、数据结构描述typedef struct page struct list_head list; /* 指向链表中的下一页 */struct address_space *mapping;/* 用来指定我们正在映射的索引节点（inode）*/unsigned long index; /* 在映射表中的偏移. */struct page *next_hash; /* 指向页高速缓存哈希表中下一个共享的页*/atomic_t count; /* 引用这个页的个数 */unsigned long flags; /* 页中各种不同的属性 */struct list_head lru; /* 用在active list中 */wait_queue_head_t wait;/* 等待这一页的页队列 */struct page *pprev_hash; /* 与next_hash相对应 */struct buffer_head * buffers; /* 把缓冲区映射到一个磁盘块 */void *virtual; /* kernel virtual address (null if not kmapped, ie. highmem) */struct zone_struct *zone; /* 页所在的内存管理区 */ mem_map_t;struct vm_area_struct struct mm_struct * vm_mm; /* 虚拟区域的参数 */unsigned long vm_start; /* 虚拟区域的起始地址 */unsigned long vm_end; /* 虚拟区域的结束地址 */struct vm_area_struct *vm_next; /* 指向下一个vm_area_struct结构的指针 */pgprot_t vm_page_prot; /* 虚拟区域的保护掩码 */unsigned long vm_flags; /* 虚拟区域如何使用 */rb_node_t vm_rb;struct vm_area_struct *vm_next_share;struct vm_area_struct *vm_pprev_share;struct vm_operations_struct * vm_ops; /* 虚拟区域上的相应的操作. */unsigned long vm_pgoff; /* 虚拟区域中的偏移量 */struct file * vm_file; /* file we map to (can be null). */unsigned long vm_raend; /* xxx: put full readahead info here. */void * vm_private_data; /* was vm_pte (shared mem) */;struct vm_operations_struct void (*open)(struct vm_area_struct * area); void (*close)(struct vm_area_struct * area); struct page * (*nopage)(struct vm_area_struct * area, unsigned long address, int unused);typedef struct free_area_structstruct list_head free_list;unsigned int *map; free_area_t;2、完成功能的主要函数表主要函数功能static int do_wp_page()为所缺的页分配一个新的页框，然后函数更新缺页的数目static int do_swap_page()当发生缺页异常时，如所缺的页有换出标志，就调用该函数将其重新调入static int do_anonymous_page()分配一个匿名页面static int do_no_page()该函数在缺页服务中负责建立一个新页面static inline int handle_pte_fault()该函数用于区分是需要请求调页还是写时拷贝调页int handle_mm_fault()进行缺页装入内存的处理3、页面失效处理（有效性失效）代码框图失效包括：保护性失效，有效性失效调用do_page_fault()函数，找到失页调用handle_mm_fault()函数，进行缺页装入内存的处理检查address的页目录和页表是否存在，然后调用pte_alloc()函数分配一个新页面返回-1，表示失败n是否成功分配新页面y调用handle_pte_fault()函数，以便确定采用何种方案分配新页框调用do_wp_page()分配一个新页框，并把就页框的数据拷贝到新页框n是否为请求调页y先调用pte_prensent()再次确认该页面当前不在内存，再调用宏pte_none()进一步确认该页从未被进程访问过调用do_swap_page()把该页从交换区重新找回n是否一直未被访问过调用lookup_swap_cache()检查交换区是否包含该换出页的标识符y调用do_no_page()分配一个新页框并进行初始化y是/否n是匿名映射，调用do_anonymous_page()函数获取新的页框页框是否被为磁盘映射n调用swapin_readahead()函数从交换区获取一组包含所请求页的页面y用vma_ops_nopage域指向的装入这个页的函数，由该函数将所缺的页从磁盘装入内存是否成功读取所请求页ny完成页面失效处理调用read_swap_cache_async()函数，该函数会使当前进程挂起直到该页从磁盘上读出为止4、程序段代码注释#include /内存管理头文件。含有页面大小定义和一些页面释放函数原型。struct page结构的定义，page的标志位定义以及存取操作宏定义。struct vm_area_struct定义。mm子系统的函数原型说明。#include /和vm_area_struct的操作mmap/mprotect/munmap相关的常量宏定义。#include /交换有关的头文件#include /多处理器支持(锁)有关的头文件#include /交换控制有关的头文件#include /该文件定义了 struct kiobuf 结构,它是 kiobuf 接口的核心部分#include /与高位内存区头文件#include /页映射有关的头文件#include /包括页表项的分配和释放宏/函数#include /用户空间的存取有关的头文件#include /翻译后援存储器有关的文件unsigned long max_mapnr; /是当前系统中物理内存的页面数目unsigned long num_physpages; /物理页面的数目void * high_memory; /高端内存的地址指针struct page *highmem_start_page; /高位内存的起始页指针/*为了节约内存的使用，在系统中，各进程通常采用共享内存，即不同的进程可以共享同一 *段代码段或数据段。当某一进程发生对共享的内存发生写操作时，为了不影响其它进程的 *正常运行，系统将把该内存块复制一份，供需要写操作的进程使用，这就是所谓的 * copy-on-write机制。copy_cow_page就是提供复制内存功能的函数，它调用c语言中标*准的内存操作函数，将首地址为from的一块虚拟内存页复制到首地址为to的空间中。 */static inline void copy_cow_page(struct page * from, struct page * to, unsigned long address)if (from = zero_page(address) /*如果首地址为from的一块虚拟内存页是0页，就释放首地址为to的空间*/clear_user_highpage(to, address);return;/*将首地址为from的一块虚拟内存页复制到首地址为to的空间中*/copy_user_highpage(to, from, address); mem_map_t * mem_map;/页面指针/* *释放一个页面 */void _free_pte(pte_t pte)struct page *page = pte_page(pte);if (!valid_page(page) | pagereserved(page)/*如果页面无效或者该页面是被保留的就不做任何工作*/return;if (pte_dirty(pte) /*检查该页面是否为脏页*/set_page_dirty(page);/*添加脏页面到脏页面表*/free_page_and_swap_cache(page);/*把脏页面放到交换区并释放页面的内存空间*/* *释放一个中间页目录 *这个函数用来释放一个pmd的项。首先它会调用pmd_none和pmd_bad进行一些例行检 *查;然后它调用pte_offset得到这个项所指向的pte首地址，最后调用pte_free释放掉这个*pte项。 */static inline void free_one_pmd(pmd_t * dir)pte_t * pte;if (pmd_none(*dir) /*判断是否存在相应的pmd项*/return;if (pmd_bad(*dir) /*通过检查它是否包含一个合法的物理地址来例行检查目录入口的合法性*/pmd_error(*dir);pmd_clear(dir); /*它把pmd清0*/return;pte = pte_offset(dir, 0); /*得到这个项所指向的pte首地址*/pmd_clear(dir); /*它把pmd清0*/pte_free(pte); /*释放掉这个pte表*/*释放一个页目录 *这个函数用来释放一个pgd的项。首先它会调用pgd_none和pgd_bad进行一些例行检查(在 * i386里，这两个函数是永远正确的);然后它调用pmd_offset得到这个项所指向的pmd首 *地址（在i386中，它实际还是返回原来的pgd的地址，因为它没有pmd），并把这个pmd*中的项一个一个的释放掉（i386里只有一个）；最后调用pmd_free释放掉这个pmd表。 *这里面有点不是很清楚的是，它把pgd清0不是在pgd_clear中做的，而是在pmd_clear *中做的，从程序中来看，如果在pgd_clear中就清掉的话，那下面的pmd的地址就找不着*了，所以当然不能这样做，但是这又和没有pmd表这个概念有点出入。 */static inline void free_one_pgd(pgd_t * dir)int j;pmd_t * pmd;if (pgd_none(*dir) /*判断是否存在相应的pgd项*/return;if (pgd_bad(*dir) /*通过检查它是否包含一个合法的物理地址来例行检查目录入口的合法性*/pgd_error(*dir);pgd_clear(dir); /*它把pgd清0*/return;pmd = pmd_offset(dir, 0); /*调用pmd_offset得到这个项所指向的pmd首地址*/pgd_clear(dir); /*它把pgd清0*/*并把这个pmd中的项一个一个的释放掉*/for (j = 0; j ptrs_per_pmd ; j+) prefetchw(pmd+j+(prefetch_stride/16);free_one_pmd(pmd+j);pmd_free(pmd); /*释放掉这个pmd表*/* low and high watermarks for page table cache. * the system should try to have pgt_water0 = cache elements pgd;spin_lock(&mm-page_table_lock);page_dir += first;do free_one_pgd(page_dir); /*释放pgd中的一个项*/page_dir+; while (-nr);spin_unlock(&mm-page_table_lock);/* keep the page table cache within bounds */*返回被释放的页面的数目*/check_pgt_cache();#define pte_table_mask(ptrs_per_pte-1) * sizeof(pte_t)#define pmd_table_mask(ptrs_per_pmd-1) * sizeof(pmd_t)/* * copy one vm_area from one task to the other. assumes the page tables * already present in the new task to be cleared in the whole range * covered by this vma. * * 08jan98 merged into one routine from several inline routines to reduce * variable count and make things faster. -jj * * dst-page_table_lock is held on entry and exit, * but may be dropped within pmd_alloc() and pte_alloc(). */* *该函数的主要功能是将某个任务或进程的vma块复制给另一个任务或进程。 *其工作机制是循环调用copy_pmd_range，将vma块中的所有虚拟空间复制到对应的虚拟 *空间中。在做复制之前，必须确保新任务对应的被复制的虚拟空间中必须都为零。 *copy_page_range按dup_mmap()-copy_mm()-do_fork()的顺序被调用（以上三个函数均在* kernel/fork.c中）。当进程被创建的时候，需要从父进程处复制所有的虚拟空间，*copy_page_range完成的就是这个任务。 */int copy_page_range(struct mm_struct *dst, struct mm_struct *src,struct vm_area_struct *vma)pgd_t * src_pgd, * dst_pgd;unsigned long address = vma-vm_start;unsigned long end = vma-vm_end;unsigned long cow = (vma-vm_flags & (vm_shared | vm_maywrite) = = vm_maywrite;src_pgd = pgd_offset(src, address)-1;/*值是页目录项*/dst_pgd = pgd_offset(dst, address)-1; /*调用pgd_offset得到这个项所指向的pgd首地址*/for (;) pmd_t * src_pmd, * dst_pmd;src_pgd+; dst_pgd+;/* copy_pmd_range */if (pgd_none(*src_pgd) /*判断是否存在相应的pgd项*/goto skip_copy_pmd_range;if (pgd_bad(*src_pgd) /*通过检查它是否包含一个合法的物理地址来例行检查目录入口的合法性*/pgd_error(*src_pgd);pgd_clear(src_pgd); /*它把pgd清0*/skip_copy_pmd_range:address = (address + pgdir_size) & pgdir_mask;if (!address | (address = end)/*如果address为0或者address大于或等于end（虚拟内存的结束地址）*/goto out;continue;src_pmd = pmd_offset(src_pgd, address); /*调用pgd_offset得到这个项所指向的pmd首地址*/dst_pmd = pmd_alloc(dst, dst_pgd, address); /*调用pmd_alloc分配一个页中间目录*/if (!dst_pmd)goto nomem;do pte_t * src_pte, * dst_pte;/* copy_pte_range */if (pmd_none(*src_pmd) /*判断是否存在相应的pmd项*/goto skip_copy_pte_range;if (pmd_bad(*src_pmd) /*通过检查它是否包含一个合法的物理地址来例行检查目录入口的合法性*/pmd_error(*src_pmd);pmd_clear(src_pmd); /*它把pmd清0*/skip_copy_pte_range:address = (address + pmd_size) & pmd_mask;if (address = end)/*address大于或等于end（虚拟内存的结束地址）*/goto out;goto cont_copy_pmd_range;src_pte = pte_offset(src_pmd, address); /*调用pte_offset得到这个项所指向的pte首地址*/dst_pte = pte_alloc(dst, dst_pmd, address); /*调用pte_alloc分配一个新的页表*/if (!dst_pte)goto nomem;spin_lock(&src-page_table_lock);do pte_t pte = *src_pte;struct page *ptepage;/* copy_one_pte */if (pte_none(pte) /*判断是否存在相应的pte项*/goto cont_copy_pte_range_noset;if (!pte_present(pte) /*页面pte不在内存中*/swap_duplicate(pte_to_swp_entry(pte); /*增加了重复的页面*/goto cont_copy_pte_range;ptepage = pte_page(pte);if (!valid_page(ptepage) | pagereserved(ptepage)/*如果页面无效或者已被保留就跳到cont_copy_pte_range*/goto cont_copy_pte_range;/* if its a cow mapping, write protect it both in the parent and the child */if (cow & pte_write(pte) /*如果是写时拷贝且该页面是写保护*/ptep_set_wrprotect(src_pte); /*对写时拷贝页面src_pte设置写保护 */pte = *src_pte;/* if its a shared mapping, mark it clean in the child */if (vma-vm_flags & vm_shared)/*虚拟内存是共享映射*/pte = pte_mkclean(pte); /*清除pte页面的”dirty”属性 */pte = pte_mkold(pte); /*从新设置pte页面的访问指示器为0 */get_page(ptepage); dst-rss+;cont_copy_pte_range:set_pte(dst_pte, pte); /*将的物理页映射到新的虚拟内存页表项pte上*/cont_copy_pte_range_noset:address += page_size;if (address = end)goto out_unlock;src_pte+;dst_pte+; while (unsigned long)src_pte & pte_table_mask);spin_unlock(&src-page_table_lock);cont_copy_pmd_range:src_pmd+;dst_pmd+; while (unsigned long)src_pmd & pmd_table_mask);out_unlock:spin_unlock(&src-page_table_lock);out:return 0;nomem:return -enomem;/* * return indicates whether a page was freed so caller can adjust rss */*如果page页面不为空，就打印一个语句并调用bug()处理它*/static inline void forget_pte(pte_t page)if (!pte_none(page) /*判断是否存在相应的pte项，如果返回1就表示不存在，返回0就表示存在*/printk(forget_pte: old mapping existed!n);bug();/*zap为zero all pages的缩写。该函数的作用是将在pmd中从虚拟地址address开始，长度*为size的内存块通过循环调用pte_clear将其页表项清零，调用free_pte将所含空间中的 *物理内存或交换空间中的虚存页释放掉。在释放之前，必须检查从address开始长 *度为size的内存块有无越过pmd_size.(溢出则可使指针逃出01023的区间)。 */static inline int zap_pte_range(mmu_gather_t *tlb, pmd_t * pmd, unsigned long address, unsigned long size)unsigned long offset;pte_t * ptep;int freed = 0;if (pmd_none(*pmd) /*判断是否存在相应的pmd项，如果返回1就表示不存在，返回0就表示存在*/return 0;if (pmd_bad(*pmd) /*通过检查它是否包含一个合法的物理地址来例行检查目录入口的合法性*/pmd_error(*pmd);pmd_clear(pmd); /*它把pmd清0*/return 0;ptep = pte_offset(pmd, address); /*调用pte_offset得到这个项所指向的pte首地址*/offset = address & pmd_mask;if (offset + size pmd_size) /*检查从address开始长度为size的内存块有无越过pmd_size*/size = pmd_size - offset;size &= page_mask; /*page_mask的值为0xfffff000*/for (offset=0; offset (address + pgdir_size) & pgdir_mask)end = (address + pgdir_size) & pgdir_mask);freed = 0;do freed += zap_pte_range(tlb, pmd, address, end - address);/*调用zap_pte_range()将指定范围的pte清0*/address = (address + pmd_size) & pmd_mask; pmd+; while (address = end)bug();spin_lock(&mm-page_table_lock);flush_cache_range(mm, address, end); /*刷新指定范围的内存*/tlb = tlb_gather_mmu(mm);do freed += zap_pmd_range(tlb, dir, address, end - address); /*调用zap_pmd_range ()清除指定范围的pmd，并返回释放的页面数目*/address = (address + pgdir_size) & pgdir_mask;dir+; while (address & (address mm) * notice that rss is an unsigned long. */if (mm-rss freed)mm-rss -= freed;elsemm-rss = 0;spin_unlock(&mm-page_table_lock);/*在页表中快速查找一个页面*/static struct page * follow_page(struct mm_struct *mm, unsigned long address, int write) pgd_t *pgd;pmd_t *pmd;pte_t *ptep, pte;pgd = pgd_offset(mm, address); /*调用pgd_offset得到这个项所指向的pgd首地址*/if (pgd_none(*pgd) | pgd_bad(*pgd)/*如果不存在相应的pgd项或目录入口不合法，就跳转到out处*/goto out;pmd = pmd_offset(pgd, address); /*调用pmd_offset得到这个项所指向的pmd首地址*/if (pmd_none(*pmd) | pmd_bad(*pmd)/*如果不存在相应的pmd项或目录入口不合法，就跳转到out处*/goto out;ptep = pte_offset(pmd, address); /*调用pte_offset得到这个项所指向的pte首地址*/if (!ptep)/*如果找不到该页面，就跳转到out处*/goto out;pte = *ptep;if (pte_present(pte) /*指定的页面不在内存中*/if (!write | (pte_write(pte) & pte_dirty(pte)/*如果write 为0或者页面即是写保护又是脏页面，返回该页面在页目录中对应的页面地址*/*the address of the page referenced by the page directory entry*/return pte_page(pte); out:return 0;/* *如果页面有效该函数就返回指定物理页面的地址，否则返回0 */static inline struct page * get_page_map(struct page *page)if (!valid_page(page)return 0;/*页面无效返回0*/return page;/* * 取得用户页面 */int get_user_pages(struct task_struct *tsk, struct mm_struct *mm, unsigned long start,int len, int write, int force, struct page *pages, struct vm_area_struct *vmas)int i;unsigned int flags;/* * require read or write permissions. * if force is set, we only require the may flags. */flags = write ? (vm_write | vm_maywrite) : (vm_read | vm_mayread);flags &= force ? (vm_mayread | vm_maywrite) : (vm_read | vm_write);i = 0;do struct vm_area_struct *vma;vma = find_extend_vma(mm, start);/*找到扩展的虚拟内存地址*/if ( !vma | (pages & vma-vm_flags & vm_io) | !(flags & vma-vm_