中国科学技术大学计算机系 陈香兰（0512－87161312） xlanchen@ustc.edu.cn Spring 2011 Linux操作系统分析 中国科学技术大学计算机系 陈香兰（0512－87161312） xlanchen@ustc.edu.cn Spring 2011

内存管理

内存管理 在前面已经提到： RAM的其余部分称为动态存储器（dynamic memory） Linux如何有效地利用x86的分段和分页机制把逻辑地址转换为物理地址 RAM的某些部分永久地分配给内核，用以存放内核代码以及静态数据 RAM的其余部分称为动态存储器（dynamic memory） 2018/12/7 Linux OS Analysis

Linux内核的前512个页框（假定内核所需内存<1MB，from ULK2） 不可用的页框 可用的页框 内核代码 初始化过的内核数据 未初始化过的内核数据 2018/12/7 Linux OS Analysis

动态存储器 进程和内核都需要动态存储器 属于稀缺资源 整个系统的性能取决于如何有效地管理动态存储器 对动态存储器的使用要进行优化 原则： 对于动态存储器要尽可能做到： 按需分配，不需要时释放 2018/12/7 Linux OS Analysis

主要内容 内核如何给自己分配动态存储器 页框管理 小内存管理 非连续存储区管理 2018/12/7 Linux OS Analysis

1、页框管理 Linux采用页作为内存管理的基本单位 Linux采用的标准的页框大小为4KB 例如：512M的物理内存对应于？？？个页框？ 由分页单元引发的缺页异常很容易得到解释 4KB是大多数磁盘块大小的倍数 传输效率高 管理方便 例如：512M的物理内存对应于？？？个页框？ include/asm-x86/page.h 2018/12/7 Linux OS Analysis

内核必须记录每个页框的当前状态 哪些属于进程，哪些存放了内核代码/数据 对于动态存储器中的页框：是否空闲，即是否可用 如果一个页框不可用，内核需要知道是谁在用这个页框 用户态进程、动态分配的内核数据结构、静态的内核代码、页面cache、设备驱动程序缓冲的数据等等 2018/12/7 Linux OS Analysis

页描述符 内核使用页描述符来跟踪管理物理内存 每个物理页框都用一个页描述符表示 页描述符用struct page的结构描述 参见mm_types.h 所有物理页框的描述符，组织在mem_map的数组中 定义 2018/12/7 Linux OS Analysis

mem_map数组 相当于物理内存的一个缩影 每个物理页框，使用一个struct page表示，它们组织在mem_map数组中 2018/12/7 Linux OS Analysis

mem_map数组的空间分配 2018/12/7 Linux OS Analysis

mem_map数组的初始化 初始化 2018/12/7 Linux OS Analysis

页描述符 页描述符中的各个字段将在用到时再逐步介绍，首先看一下 count：页的使用引用计数器 0：空闲 >0：页已经分配给一个或多个进程或用户某些内核数据结构 flags：页框状态，最多可以有32个，每个使用一个位表示 2018/12/7 Linux OS Analysis

页框状态 2018/12/7 Linux OS Analysis

页描述符将会占用很大的一段空间 由于每个struct page结构小于64个字节，因此1MB的内存需要使用约4个页面来存放mem_map数组 2018/12/7 Linux OS Analysis

关于NUMA 不考虑 物理内存被划分为若干个node 存取时间不等 考虑CPU局部性 Node使用数据结构pg_data_t描述 每个node被划分成若干个zone 2018/12/7 Linux OS Analysis

存储区(Memory Zones) 在一个理想的体系结构中，一个页框就是一个物理存储单元，可以用于任何事情，例如 存放内核数据/用户数据/缓存磁盘数据等 实际上存在硬件制约：一些页框由于自身的物理地址的原因不能被一些任务所使用，例如 ISA总线的DMA控制器只能对ram的前16M寻址 在一些具有大容量ram的32位计算机中，CPU不能直接访问所有的物理存储器，因为线性地址空间不够 2018/12/7 Linux OS Analysis

ZONE_DMA ZONE_NORMAL ZONE_HIGHMEM 为了应付这种限制，Linux把具有同样性质的物理内存划分成——区(zones) Linux把物理存储器划分为4个区 ZONE_DMA ZONE_DMA32 (未见用） ZONE_NORMAL ZONE_HIGHMEM 参见枚举类型zone_type 896MB 16MB MAX ZONE_DMA ZONE_NORMAL ZONE_HIGHMEM 物理内存 2018/12/7 Linux OS Analysis

ZONE_DMA ZONE_NORMAL ZONE_HIGHMEM ZONE_DMA 和ZONE_NORMAL区 包含存储器的“常规”页，通过把它们映射到线性地址空间的3GB以上，内核就可直接访问 而ZONE_HIGHMEN区 中包含的存储器页面不能由内核直接访问 3GB 3GB+16MB 3GB+896MB 4GB <3G 线性空间 × ZONE_DMA ZONE_NORMAL ZONE_HIGHMEM 物理内存 16MB 896MB MAX 2018/12/7 Linux OS Analysis

每个zone使用struct zone表示 关键：free_area 小结： Mem_map、node、zone之间的关系 2018/12/7 Linux OS Analysis

动态内存 内存布局： 动态内存及引用它的一些值 2018/12/7 Linux OS Analysis

请求页框 内核实现了一种底层的内存分配机制，并提供了几个接口供其他内核函数调用。 分配： 释放 alloc_pages/alloc_page/alloc_pages_node/alloc_pages_current/… __get_free_pages/__get_free_page/__get_dma_pages/get_zeroed_page 释放 free_pages/__free_pages/free_page/__free_page 2018/12/7 Linux OS Analysis

调用关键函数：get_page_from_freelist 2018/12/7 Linux OS Analysis 调用关键函数：get_page_from_freelist

类似alloc_pages，但是返回第一个 所分配页框的线性地址 分配一个页框，返回值同上 用来分配适用于DMA的页框 2018/12/7 Linux OS Analysis

这个函数与__get_free_page基本等价， 差别在于它把所分配页框中的页面数据 全部清0。 这在给用户态的空间分配页框时候很有 用。因为这个页框虽然是可被分配的， 但是里面的数据可能包含了内核的一些 敏感信息。 清0，可以避免信息泄露 2018/12/7 Linux OS Analysis

关于unsigned int gfp_mask 指明可在何处并以何种方式查找空闲的页框 GFP_ATOMIC， 这种分配是高优先级的并且不能睡眠。一般在中断处理程序，下半部分和其他不能睡眠的场合下使用 GFP_KERNEL， 这是普通的分配模式，允许睡眠。一般在用户进程可能调用到的内核函数中使用，这个时候进程是可以安全的睡眠的 GFP_DMA， 设备驱动程序需要DMA内存时使用 2018/12/7 Linux OS Analysis

关于gfp_mask的进一步解释 标志位及其含义 2018/12/7 Linux OS Analysis

2018/12/7 Linux OS Analysis

等等 2018/12/7 Linux OS Analysis

释放页框 如果page对应的页框不是被保留的页框(PG_reserved标志为0)，就 把描述符的count字段减1。如果count变为0，就调用释放 与上一个函数类似，只是第一个参数是要释放的 第一个页框的线性地址addr 2018/12/7 Linux OS Analysis

在内核中释放页框时要非常小心，必须确保只释放了所请求的页框，否则内核可能会崩溃 page = __get_free_page(GFP_KERNEL,3); If (!page){ /*如果内存不足，分配失败，必须在这里处理这个失败*/ } /*现在’page’变量指向了8个连续页框的起始线性地址*/ free_pages(page,3); /*现在页框被释放，不应该再对page中存放的线性地址进行操作*/ 2018/12/7 Linux OS Analysis

页框的管理 内核要为分配一组连续的页框建立一种稳定、高效的分配策略 这种策略要解决（外部）碎片问题： 频繁的请求和释放不同大小的一组连续页框，必然导致在物理页框中分散许多小块的空闲页框 这样，即使有足够的空闲页框满足请求，但要分配一个大块的连续页框可能就无法满足了 2018/12/7 Linux OS Analysis

基于下面的原因，Linux内核首选第二种方法 有两种办法可以避免这样的碎片 利用MMU把一组非连续的物理空闲页框映射到连续的线性地址空间 使用一种适当的技术来记录现存的空闲连续页框的情况，以尽量避免为满足对小块的请求而把大块的空闲块进行分割 基于下面的原因，Linux内核首选第二种方法 在某些情况下，必须使用连续的页框，如DMA 尽量少的修改内核页表 2018/12/7 Linux OS Analysis

buddy算法（伙伴算法） Linux使用著名的伙伴算法来解决碎片问题。 每个块的第一个页框的物理地址是该块大小的整数倍 例如：大小为16个页框的块，其起址是16×4KB的倍数 2018/12/7 Linux OS Analysis

伙伴的定义 例如：0和1是伙伴，1和2不是伙伴 两个伙伴的大小必须相同，物理地址必须连续 事实上伙伴是通过对大块的物理内存划分获得的 假定伙伴的大小为b 那么第一个伙伴的物理地址必须是2×b×4KB对齐 事实上伙伴是通过对大块的物理内存划分获得的 假如从第0个页面开始到第3个页面结束的内存 每次都对半划分，那么第一次划分获得大小为2页的伙伴 进一步划分，可以获得大小为1页的伙伴，例如0和1，2和3 1 2 3 1 2 3 2018/12/7 Linux OS Analysis

数据结构 Linux为每个zone使用各自独立的伙伴系统 每个伙伴系统使用的主要数据结构为： 空闲内存管理数组free_area 2018/12/7 Linux OS Analysis

mem_map数组 空闲内存管理数组 前面介绍过的页描述符数组 每个页描述符描述一个物理页框 整个mem_map数组描述整个zone中的所有的物理内存 空闲内存管理数组 空闲内存按照伙伴管理的方法进行组织 使用free_area结构 2018/12/7 Linux OS Analysis

伙伴 当两个伙伴都为空闲的时候，就合并成一个更大的块 该过程将一直进行，直到找不到可以合并的伙伴为止 寻找伙伴 给定一个要释放的空闲块 找到其伙伴 查看其状态：合并 or 不合并 2018/12/7 Linux OS Analysis

举例 假设有128MB的ram。 假设要请求一个大小为128个页框的块(0.5MB)。 128MB最多可以分成215=32768个页框，214=16384个8KB（2页）的块 或213=8192个16KB（4页）的块，直至64个大小为512个页的块 假设要请求一个大小为128个页框的块(0.5MB)。 算法先free_area[7]中检查是否有空闲块（块大小为128个页框） 若没有，就到free_area[8]中找一个空闲块（块大小为256个页框） 若存在这样的块，内核就把256个页框分成两等份，一半用作满足 请求，另一半插入free_area[7]中 如果在free_area[8]中也没有空闲块，就继续找free_area[9]中是否有 空闲块。 2018/12/7 Linux OS Analysis

如果free_area[9]也没有空闲块，内存不够，返回一个错误 信号 若有，先将512分成伙伴，一个插入free_area[8]中，另一 个进一步划分成伙伴，取其一插入free_area[7]中，另一个 分配出去 如果free_area[9]也没有空闲块，内存不够，返回一个错误 信号 2018/12/7 Linux OS Analysis

伙伴系统相关数据结构的最初初始化 伙伴系统的释放式初始化 arch/x86/mm/init_32.c:mem_init 2018/12/7 Linux OS Analysis

内存的分配与回收 阅读相关代码 关键：nr_free __free_one_page __rmqueue __free_pages __free_pages_ok free_one_page mm/page_alloc.c buffered_rmqueue get_page_from_freelist __alloc_pages_internal __alloc_pages 2018/12/7 Linux OS Analysis

2018/12/7 Linux OS Analysis

2018/12/7 Linux OS Analysis

页框管理小结 页描述符 Mem_map数组 Zone 空闲页框的管理 空闲页框管理 伙伴算法 Zone_dma 空闲页框管理 Zone_normal Zone_highmem 空闲页框管理 Mem_map 数 组 物理内存：highmem 物理内存： DMA 物理内存： Normal 线性空间(<3GB) 线 性 空 间 ( 3GB~4GB) 2018/12/7 Linux OS Analysis

察看/proc/buddyinfo: cat /proc/buddyinfo Kernel memory allocator information Memory fragmentation is a problem under some workloads, and buddyinfo is a useful tool for helping diagnose these problems. Buddyinfo will give you a clue as to how big an area you can safely allocate, or why a previous allocation failed. Each column represents the number of pages of a certain order which are available. From Documentation/filesystems/proc.txt 2018/12/7 Linux OS Analysis

2、内存区管理(memory area) 单单分配页面的分配器肯定是不能满足要求的 内核中大量使用各种数据结构，大小从几个字节到几十上百k不等，都取整到2的幂次个页面那是完全不现实的 早期内核的解决方法是提供大小为2,4,8,16,...,131056字节的内存区域 需要新的内存区域时，内核从伙伴系统申请页面，把它们划分成一个个区域，取一个来满足需求 如果某个页面中的内存区域都释放了，页面就交回到伙伴系统 2018/12/7 Linux OS Analysis

但这种分配方法有许多值得改进的地方： 不同的数据类型用不同的方法分配内存可能提高效率。比如需要初始化的数据结构，释放后可以暂存着，再分配时就不必初始化了 内核的函数常常重复地使用同一类型的内存区，缓存最近释放的对象可以加速分配和释放 对内存的请求可以按照请求频率来分类，频繁使用的类型使用专门的缓存，很少使用的可以使用通用缓存 使用2的幂次大小的内存区域时硬件高速缓存冲突的概率较大，有可能通过仔细安排内存区域的起始地址来减少硬件高速缓存冲突 缓存一定数量的对象可以减少对buddy系统的调用，从而节省时间并减少由此引起的硬件高速缓存污染 2018/12/7 Linux OS Analysis

Linux2.6.26中 SLOB Allocator: Simple List Of Blocks Slab Slub：slab的一个变种 NUMA Slab Slub：slab的一个变种 Kmalloc/kfree 本课介绍基本的slab算法 2018/12/7 Linux OS Analysis

slab分配器 slab分配器体现了这些改进思想 slab分配器把内存区看成对象 slab分配器把对象分组放进高速缓存。 每个高速缓存都是同种类型内存对象的一种“储备” 例如当一个文件被打开时，存放相应“打开文件”对象所需的内存是从一个叫做filp(file pointer)的slab分配器的高速缓存中得到的 也就是说每种对象类型对应一个高速缓存 2018/12/7 Linux OS Analysis

每个高速缓存被分成多个slabs，每个slab由一个或多个连续的页框组成，其中包含一定数目的对象 2018/12/7 Linux OS Analysis

每个slab有三种状态：全满，半满，全空 半满介于两者之间 当内核函数需要一个新的对象时， 优先从半满的slab满足这个请求 否则从全空的slab中取一个对象满足请求 如果没有空的slab则向buddy系统申请页面生成一个新的slab 2018/12/7 Linux OS Analysis

高速缓存描述符和slab描述符之间的关系 2018/12/7 Linux OS Analysis

普通和专用高速缓存 每个高速缓存使用kmem_cache表示 普通高速缓存根据大小分配内存 专用高速缓存根据类型分配 26个，2组（一组用于DMA分配，另一组用于常规分配） 每组13个，大小从25=32个字节，到217=132017个字节 数据结构cache_sizes 数组：malloc_sizes 专用高速缓存根据类型分配 2018/12/7 Linux OS Analysis

阅读文件kmalloc_sizes.h 2018/12/7 Linux OS Analysis

2018/12/7 Linux OS Analysis

slab分配器提供的接口 创建专用高速缓存：kmem_cache_create 撤销专用高速缓存：kmem_cache_destroy 从专用高速缓冲中分配和释放 从高速缓存中分配/释放一个内存对象 kmem_cache_alloc/kmem_cache_free 从普通高速缓存中分配和释放 kmalloc/kfree 举例说明使用情况 2018/12/7 Linux OS Analysis

slab分配器和伙伴系统的接口 slab分配器调用kmem_getpages()来获取一组连续的空闲页框 相应的有kmem_freepages()来释放分配给slab分配器的页框 2018/12/7 Linux OS Analysis

如果编写的内核模块有许多创建和释放数据结构的操作，可以考虑调用前面所述的slab分配器的接口创建一个高速缓存 这样可以大大减少内存的访问时间 2018/12/7 Linux OS Analysis

察看/proc/slabinfo The slabinfo file gives information about memory usage at the slab level. Linux uses slab pools for memory management above page level in version 2.2. Commonly used objects have their own slab pool (such as network buffers, directory cache, and so on). Documentation/filesystems/proc.txt 2018/12/7 Linux OS Analysis

3、非连续存储区管理 把线性空间映射到一组连续的页框是很好的选择 有时候不得不将线性空间映射到一组不连续的页框 优点：避免碎片 2018/12/7 Linux OS Analysis

为非连续内存区保留的线性地址空间 VMALLOC_START~VMALLOC_END 2018/12/7 Linux OS Analysis

非连续存储区的描述符vm_struct Vmalloc等分配一个非连续存储区 Vfree释放非连续线性区间 include/linux/vmalloc.h mm/vmalloc.c 2018/12/7 Linux OS Analysis

页框管理、内存区管理、非连续存储区管理之间的关系 使用分配到缓冲区 使用分配到线性区 直接使用分配到的 页框，例如进程描述符 使用slab算法，以若干 个字节为单位进行管理 非连续存储区，映射 到非连续的物理页框上 分配出 一些页框 分配出 一些页框 物理内存：页框管理，以页框为单位进行管理 2018/12/7 Linux OS Analysis

察看/proc/meminfo Provides information about distribution and utilization of memory cat /proc/meminfo 关于每一项的解释，参见Documentation/filesystems/proc.txt 2018/12/7 Linux OS Analysis

作业 Linux的页框管理采用什么算法？简述该算法。 Linux中的slab算法的用途是什么？简述该算法。 什么是非连续内存区？ 2018/12/7 Linux OS Analysis