第二部分LINUX存储管理

1、第二章 linux存储管理linux的分页管理机制linux的地址划分 每一个用户进程都可以访问4gb的线性虚拟内存空间。 从0到3gb的虚拟内存地址是用户空间，用户进程可以直接对其进行访问。 从3gb到4gb的虚拟内存地址为核心态空间，存放仅供核心态访问的代码和数据，用户态进程不可访问。 所有进程从3gb到4gb的虚拟空间都是一样的，有同样的页目录项，同样的页表，对应到同样的物理内存段。linux以此方式让内核态进程共享代码段和数据段。 内核态虚拟空间从3gb到3gb+4m的一段（也就是进程页目录第768项所管辖的范围），被映射到物理空间0到4m段。因此，进程处于核心态时，只要通过访问虚拟空

2、间3gb到3gb+4m段，偏移地址0到4m，即访问了物理空间0到4m段。虚拟地址转换 pgd pmd pte page frame 每当启动一个新进程，linux 都为其分配一个 task_struct 结构，内含 saved_kernel_stack、kernel_stack_page、ldt、tss、mm 等内存管理信息，详见进程管理部分。mm_struct(include/linux/sched.h)203 struct mm_struct 204 struct vm_area_struct * mmap; / /* * list of vmas list of vmas * */ /2

3、05 struct vm_area_struct * mmap_avl; / /* * tree of vmas tree of vmas * */ /206 struct vm_area_struct * mmap_cache; / /* * last find_vma result last find_vma result * */ /207 pgd_t * pgd;208 atomic_t mm_users; / /* * how many users with user space? how many users with user space? * */ /209 atomic_t

4、mm_count; / /* * how many how many 进程进程/ /线程线程 refer to struct mm_struct (users count as refer to struct mm_struct (users count as 1) 1) * */ /210 int map_count; / /* * number of vmas number of vmas * */ /211 struct semaphore mmap_sem; /* 对mmap操作的信号量 */212 spinlock_t page_table_lock;214 struct list_

5、head mmlist; / /* * list of all active mms list of all active mms * */ /216 unsigned long start_code, end_code, start_data, end_data;217 unsigned long start_brk, brk, start_stack;218 unsigned long arg_start, arg_end, env_start, env_end;219 unsigned long rss, total_vm, locked_vm;220 unsigned long def

6、_flags;221 unsigned long cpu_vm_mask;222 unsigned long swap_cnt; / /* * number of pages to swap on next pass number of pages to swap on next pass * */ /223 unsigned long swap_address;226 mm_context_t context; / /* * architecture-specific mm context architecture-specific mm context * */ /227 ;pcb对内存的

7、控制(之一)struct mm_struct结构的成员 pgd_t * pgd;表示进程页目录的起始地址。pcb对内存的控制 task mm_struct vm_area_struct vm_mm pgd mm vm_operations_struct vm_next *open mmap pgd vm_area_struct pte pte vm_next page page frame frame 第二章 linux存储管理虚存段（vma）的组织和管理(克服页表中空表项过烂问题)vma段（vitual memory area） 一个vma段是某个进程的一段连续的虚存空间； 在这段虚存里的所

8、有单元拥有相同的特征。例如：属于同一进程，相同的访问权限，同时被锁定（locked），同时受保护（protected），等等。vm_area_struct(include/linux/mm.h)41 struct vm_area_struct 42 struct mm_struct * vm_mm; /* vm area parameters */43 unsigned long vm_start;44 unsigned long vm_end;47 struct vm_area_struct *vm_next; /* linked list of vm areas per task, sor

9、ted by address */49 pgprot_t vm_page_prot;50 unsigned long vm_flags;53 short vm_avl_height; /* avl tree of vm areas per task, sorted by address */54 struct vm_area_struct * vm_avl_left;55 struct vm_area_struct * vm_avl_right;61 struct vm_area_struct *vm_next_share;62 struct vm_area_struct *vm_pprev_

10、share;64 struct vm_operations_struct * vm_ops;65 unsigned long vm_pgoff; /* offset in page_size units, *not* page_cache_size */* 如果vma段的内容是关于文件的，则vm_offset就是该段内容相对于文件起始位置的偏移量。 */66 struct file * vm_file;67 unsigned long vm_raend;68 void * vm_private_data; /* was vm_pte, 用于共享内存，含shm_swp_type和共享内存段id号

11、 */69 ;vma段的链表 进程通常占用几个vma段，分别用于代码段、数据段、堆栈段等。属于同一进程的vma段通过vm_next指针连接，组成链表。如图。 struct mm_struct结构的成员struct vm_area_struct * mmap 表示进程的vma链表的表头。pcb对内存的控制(之二) task mm_struct vm_area_struct vm_mm pgd mm vm_operations_struct vm_next *open mmap pgd vm_area_struct pte pte vm_next page page frame frame pcb

12、对内存的控制(之三) linux同时维护了一个avl（adelson-velskii and landis）树。 在树中，所有vma段均有左指针vm_avl_left指 向 相 邻 的 低 地 址 虚 存 段 ， 右 指 针vm_avl_right指向相邻的高地址虚存段。 struct mm_struct结构的成员struct vm_area_struct * mmap_avl表示进程的avl树的根，vm_avl_height表示avl树的高度。 对vma段可以进行加锁、加保护等操作。avl树 vm_area_struct (1000,2000) vm_avl_left vm_avl_righ

13、t (500,670) vm_avl_left vm_avl_right (2500,3000) vm_avl_left vm_avl_right (350,450) vm_avl_left vm_avl_right (800,900) vm_avl_left vm_avl_right第二章 linux存储管理物理空间管理物理空间的组织(include/linux/fs.h,struct page) 物理内存以页帧(page frame)为单位，页帧的长度固定，等于页长，对intel cpu缺省为4k字节。 linux对物理内存的管理通过mem_map表描述(mm/memory.c)。 mem

14、_map在系统初始化时由free_area_init()函数创建(mm/page_alloc.c)。 它本身是关于struct page mem_map_t (linux/mm.h)的数组，每项mem_map_t对应一个关于核心态、用户态代码和数据等的页帧。mem_map在物理空间的位置 0x000000(0k) empty_zero_page 由 mem_init 初始化 0x001000(4k) swapper_pg_dir 核心态访问空间的页目录 0x002000(8k) pg0 0x003000(12k) bad_pages 0x004000(16k) bad_pg_table 0x0

15、05000(20k) floppy_track_buffer 0x006000(24k) kernel_code+text free 0x0a0000(640k reserved 0x100000(1m) pg_tables(4k) swap_cache mem_map bitmap freestruct page134 typedef struct page 135 struct list_head list;136 struct address_space *mapping; /* 见书中解释 */137 unsigned long index; /* 若该页帧的内容是文件，则index指

16、出文件的inode和偏移位置 */ 138 struct page *next_hash;139 atomic_t count; /* 指明目前使用该页面的用户数。count=0意味着此页空闲 */140 unsigned long flags; /* atomic flags, some possibly updated asynchronously */141 struct list_head lru;142 unsigned long age; /* 页帧的年龄，越小越先换出 */ 143 wait_queue_head_t wait;144 struct page *pprev_has

17、h;145 struct buffer_head * buffers; /* 若该页帧作为缓冲区，则指示地址 */ 146 void *virtual; /* non-null if kmapped */147 struct zone_struct *zone;148 mem_map_t;第二章 linux存储管理空闲物理内存管理(buddy system impelmentation codes)空闲内存的组织 bitmap free_area next 每 1 位对应 20页 prev map next prev 每 1 位对应 21页 map next prev 每 1 位对应 22页

18、map . .pagepage2 pages2 pages4 pages4 pagesbitmap 表 在物理内存低端，紧跟mem_map表的bitmap表以位图方式记录了所有物理内存的空闲状况。 与mem_map一样，bitmap表在系统初始化时由free_area_init()函数创建(mm/page_alloc.c)。 与一般性位图不同的是，bitmap表分割成nr_mem_lists组(缺省值6)。bitmap 表 首先是第0组，初始化时设定了长度为(end_mem-start_mem) / page_size/20+3,每位表示20个页帧的空闲状况，置位表示已被占用。 接着是第1组，

19、初始化时设定了长度为： (end_mem-start_mem) / page_size/21+3 ，每位表示连续21个页帧的空闲状况，置位表示其中1页或2页已被占用。 类似地，对第i组，初始化时设定了长度为： (end_mem-start_mem) / page_size / 2i+3 ，每位表示连续2i个页帧的空闲状况，置位表示其中1页或几页已被占用。 例如对第5组，某个bit所对应的连续32页帧中只要有一个被占用，此位即置1，只有当所有32页帧全部回收后才清0。free_area数组 linux用free_area数组记录空闲的物理页帧。free_area数组由nr_mem_lists个f

20、ree_area_struct结构类型的数组元素构成，每个元素均作为一条空闲块链表的表头。 struct free_area_struct struct page *next; /* 此结构的next,prev指针与struct page匹配 */ struct page *prev; unsigned int * map; /* 指向bitmap */ ; static struct free_area_struct free_areanr_mem_lists; 所有单个空闲页帧组成的链表挂到free_area数组的第0项后面。连续2 i个空闲页帧则被挂到free_area数组的第i项后面。

21、操作函数 分配内存块由_get_free_pages()函数和宏定义_get_free_page()执行 释放内存块可以调用free_pages()函数执行。分配算法 linux采用buddy算法分配空闲块，块长可以是2i个 (0= i nr_mem_lists) 页帧。 当分配长度是2i页帧的块时，从free_area数组的第i条链表开始搜索，找不到再搜索第i+1条链表，余此类推。 若找到的空闲块长正好等于需求的块长，则直接将它从free_area删除，返回首地址。 若找到的空闲块长大于需求的块长，则将空闲块一分为二，前半部分插入free_area中前一条链表，取后半部分。 若还大，则继续对

22、半分，留一半取一半，直至相等。 bitmap表也相应调整。每分配一个2i页帧长的块，都要将bitmap表从第i组到第nr_mem_lists组的对应的bit置1。释放算法 回收空闲块时，change_bit()函数根据bitmap表的对应组，判断回收块的前后邻居是否也为空。 若空则合并，即修改bitmap表中对应位，从free_area的空闲链表中取下该相邻块。 此判断是个递归过程，直至找不到空闲邻居为止。 将最后合并的最大块插入free_area的相应链表中。第二章 linux存储管理slab第二章 linux存储管理核心态内存的申请与释放核心态内存 核心态内存是用来存放linux核心系统数

23、据结构的内存区域，处于进程虚拟空间的3 g 至 4 g （ 精 确 地 说 应 该 是3g+high_memory，其中high_memory是系统在启动阶段测得的物理内存的实际容量）范围内。 核心态内存的分配和释放以块(block)为单位。核心态空闲内存的组织 blocksize 表表 sizes 表表 127 0 firstfree dmafree 63 0 firstfree dmafree page_descriptor 1 0 firstfree dmafree 1 5 firstfree block_header dmafree 32 64 .4096-16 . .131072-1

24、6orderfirstfree nfree bh_flags bh_flagsblocksize表 blocksize表规定申请内存块时可供选择的块长度： static const unsigned int blocksize = 32, 64, 128,252, 508, 1020,2040,4096 16, 8192 16, 16384 16, 32768 16, 65536 16, 131072 16,0 /* 表示blocksize表的结束 */ ; 它们近似等于2的次幂。sizes表 sizes表管理那些从物理空间free_area申请得到的用于核心态内存空间分配的空闲块。 size

25、s表的元素类型是struct size_descriptor， 每个表项实质上就是两个由等长空闲块所组成链表的表头，一是dma可访问的，一是一般性的。核心内存的申请和释放 核心内存申请char *kmalloc (unsigned long size, int priority); 核心内存释放 kfree(char * addr); 参见文件“kmalloc.doc”kmalloc cache#define max_cache_order 3struct page_descriptor * kmalloc_cachemax_cache_order; free_kmalloc_pages fr

26、ee_pages get_kmalloc_pages _get_free_pages核心态空间sizes 表kmalloc_cache物理空间free_area第二章 linux存储管理用户态内存的申请与释放用户态内存 由vmalloc()分配的存储空间在进程的虚拟空间是连续的，但它对应的物理内存仍需经缺页中断后，由缺页中断服务程序分配。所分配的物理页帧也不是连续的。这些特征与访问用户态内存相似，所以不妨把vmalloc()和vfree()称作用户态内存的申请与释放界面。 注意，malloc()、free()与vmalloc()、vfree()不是一回事，gcc并不是利用vmalloc、vfr

27、ee实现malloc、free的。用户态内存的位置 可分配的虚拟空间在3g+high_memory+hole_8m以上高端，由vmlist链表管理。 3g是核心态赖以访问物理内存的始址，high_memory是安装在计算机中实际可用的物理内存的最高地址，因此3g+high_memory也就是（从虚拟空间中看到的）物理内存的上界。hole_8m则是长度为8m的“隔离带”，起到越界保护作用。 尽管vmalloc返回高于任何物理地址的高端地址，但因为vmalloc同时更改了页表甚至页目录，处理器仍能正确地访问这些高端连续地址（页目录和页表把高端虚拟地址映射到实际的物理地址）。内核态程序与进程用户态程

28、序共享同一个页目录，同一组页表，因而内核态程序也能正常访问。管理用户态内存的结构vmlist 链表的节点类型 vm_struct(mm/vmalloc.c):struct vm_struct unsigned long flags; /* 虚拟内存块的占用标志 */ void * addr; /* 虚拟内存块的起始地址 */ unsigned long size; /* 虚拟内存块的长度 */ struct vm_struct * next; /* 下一个虚拟内存块 */;static struct vm_struct * vmlist = null; vmlist 3g+high_memor

29、y+hole_8mflagssizeflagssize操作函数 申请 void * vmalloc(unsigned long size)； 释放 void vfree(void * addr)； 参见文件vmalloc.dockmalloc与vmalloc的比较 vmalloc返回的地址空间不能绕过cpu的页表机构直接使用。当操作系统某些管理模块（如dma部件）需要直接使用实际物理地址时，vmalloc不合适，必须用kmalloc。 向vmalloc申请小块内存（如1页左右）也不合适，因为无论是内存的分配还是使用，都涉及到内存和页表两方面因素。 比较合适的情形可能是申请大块缓冲区。此时，尽管

30、大缓冲区占用了大段虚拟地址，但实际占用的物理地址不大，因为当前不用的内容不会调入物理内存中。相反，如果用kmalloc申请大缓冲区，那么，将实实在在占用这么大的一块物理内存。何况，缺省情况下，kmalloc可分配的最大内存块只有131054字节。第二章 linux存储管理交换空间两种交换空间 一种用整个块设备，如硬盘的一个分区，称作交换设备，效率较高； 另一种用文件系统中固定长度的文件，称作交换文件，效率较低。 linux允许并行管理max_swapfiles个交换空间（max_swapfiles的缺省值为8）。交换空间的格式 前4096字节是一个以字符串 “swap_space”结尾的位图。

31、位图的每一位（bit）对应一个交换空间的页面，置位表示对应的页面可用于换页操作。 第4096字节之后则是真正存放换出页面的空间。 这样，每个交换空间最多可容纳 （4096-10）* 8 1 = 32687个页面。启用交换空间 int sys_swapon(const char * swapfile, int swapflags); 第一个参数swapfile是设备名或文件名， swapflags规定交换空间的优先数。该参数中，swap_flag_prefer（0x8000）必须置位，swap_flag_prio_mask(0x7fff)指定一个正的优先数。如果没有指定优先数，swapon自动给

32、出一个负的优先数，负优先数的取值决定于swapon的调用次数。每注册一个交换空间，就在swap_info表中填一项swap_info_struct结构 25 struct swap_info_struct swap_infomax_swapfiles; 49 struct swap_info_struct 50 unsigned int flags; /* 如果swp_used位置位，则被占用。如果swp_writeok，则该交换空间准备就绪。 */ 51 kdev_t swap_device; /* 对于交换设备，swap_device属性表示交换设备的主、次设备号 */ 52 spinlo

33、ck_t sdev_lock; /* 对于此设备的互斥锁 */ 53 struct dentry * swap_file; /* 对于交换文件，swap_file属性指向该文件的inode */ 54 struct vfsmount *swap_vfsmnt; 55 unsigned short * swap_map;/* 指向一张表，其每一字节按顺序对应交换空间的一个页面，字节的值代表了引用该页面的进程数 */ 56 unsigned int lowest_bit; /*交换空间中的第一个没有被任何进程使用的交换页在swap_map数组中的下标 */ 57 unsigned int high

34、est_bit; /* 交换空间中最后一个没被任何进程使用的交换页的下标 */ 58 unsigned int cluster_next; /*上次从当前的cluster中成功分配的交换页面的后继页面在swap_map数组中的下标 */ 59 unsigned int cluster_nr; /* 当前cluster中可供使用的交换页面的个数 */ 60 int prio; /*交换空间的优先级。优先级越高，交换文件申请交换页面的时候越优先考虑 */ 61 int pages; /* 表示该交换空间尚有多少空闲空间可供保存进程换出的物理页 */ 62 unsigned long max; 63

35、 int next; /*指向下一项交换空间的的指针 */ 64 ;153 struct swap_list_t 154 int head; /* head of priority-ordered swapfile list */155 int next; /* swapfile to be used next */156 ;23 struct swap_list_t swap_list = -1, -1;注销交换空间int sys_swapoff(const char * swapfile);交换空间的工作 kswapd进程换出页面时，调用try_to_swap_out() 测试页面的年龄。如果