内存管理（二）物理内存管理
# Linux, 2020-12-03
接上一篇 Blog
**cat /proc/
内存管理
HuSharpOS 中的内存管理
这里先从指定位置处读取LOADER写入的物理内存大小。本项目中，物理内存的配置为32M(bochs配置文件bochsrc.cfg中”megs: 32”)，减去低端的 1MB 、减去LOADER开启分页机制时创建 PDT 和 PT 占用的1MB（紧邻低端1MB之上），还有30MB，内核和用户内存池各占15M。所以，内核物理内存池的起始地址为 0x20_0000（2MB）。
kernel_pool.phy_addr_begin = 2MB; // 起始地址
user_pool.phy_addr_begin = 2MB+15MB;
4GB 虚拟地址空间中，高 1GB 为内核空间，其中 1GB 之上的 1MB 虚拟空间已在LOADER阶段映射到物理内存的低端1MB。所以，内核虚拟地址池的起始地址为0xc010_0000（1GB+1MB）。
以页(4KB)为单位的内存管理，采用 bitmap (位图) 技术。本项目中，自定义内核物理内存的 bitmap 存放于0xc009_a000 ，自定义内核主线程栈顶为0xc009_f000、内核主线程PCB为0xc009_a000。
所以，本系统最大支持 4 个页框的位图（一个页框大小的位图可表示 128M 内存， 4 个页框即 512M ,虽说是远远大于分配内存，但是任性～），用于内核/用户物理内存池bitmap、内核虚拟地址池bitmap。
malloc 和 free
/* 内存块描述符信息 */
struct mem_block_desc{
unsigned int block_size; // 内存块大小
unsigned int blocks_per_arena; // 每个arena可容纳此mem_blcok的数量
struct list free_list; // 空闲内存块mem_block链表
};
// 内存块
struct mem_block {
struct list_elem free_elem;
};
// arena 的元信息 12个字节
struct arena {
struct mem_block_desc* desc;// arena 关联的指针
// large为 ture 时,cnt表示的是页框数。
// 否则cnt表示空闲mem_block数量
uint32_t cnt;
bool large;
};
// 内核内存块描述符数组
// 本系统支持7种规格的内存块: 16 32 64 128 256 512 1024字节
struct mem_block_desc k_block_descs[7];
基于bitmap，实现了以页为单位的内存管理。 虚拟地址是连续的，但物理地址可能连续，也可能不连续。一次性申请count个虚拟页之后，再依次为每一个虚拟页申请物理页，并在页表中依次添加映射关联。
在以页(4KB)为单位的内存管理基础上，实现小内存块的管理，可满足任意内存大小的分配与释放(malloc/free)。这里采用arena模型。
类似 Linux 的伙伴系统
Linux 中的内存管理
物理内存的组织方式
1、发展历程
1、平坦内存模型：Flat Memory Model
我们可以从 0 开始对物理页编号，这样每个物理页都会有个页号。由于物理地址是连续的，页也是连续的，每个页大小也是一样的。因而对于任何一个地址，只要直接除一下每页的大小，很容易直接算出在哪一页。每个页有一个结构 struct page 表示，这个结构也是放在一个数组里面，这样根据页号，很容易通过下标找到相应的 struct page 结构。
2、对称多处理器：SMP Symmetric multiprocessing
当刚出现多处理器时，仍然采用所有的 CPU 访问内存都要过总线，而且距离都是一样的。
3、非一致内存访问：NUMA Non-uniform memory access
在这种模式下，内存不是一整块。每个 CPU 都有自己的本地内存，CPU 访问本地内存不用过总线，因而速度要快很多，每个 CPU 和内存在一起，称为一个 NUMA 节点。但是，在本地内存不足的情况下，每个 CPU 都可以去另外的 NUMA 节点申请内存，这个时候访问延时就会比较长。
2、物理内存的组织
节点
typedef struct pglist_data
NUMA 节点：每个 CPU 都有自己的本地内存，CPU 访问本地内存不用过总线，因而速度要快很多，每个 CPU 和内存在一起，称为一个 NUMA 节点。
但是，在本地内存不足的情况下，每个 CPU 都可以去另外的 NUMA 节点申请内存，这个时候访问延时就会比较长。
内存被分成了多个节点，每个节点再被分成一个一个的页面。由于页需要全局唯一定位，页还是需要有全局唯一的页号的。但是由于物理内存不是连起来的了，页号也就不再连续了。于是内存模型就变成了非连续内存模型，管理起来就复杂一些。
typedef struct pglist_data pg_data_t，它里面有以下的成员变量：
- 每一个节点都有自己的 ID：node_id；
- node_mem_map 就是这个节点的 struct page 数组，用于描述这个节点里面的所有的页；
- node_start_pfn 是这个节点的起始页号；
- node_spanned_pages 是这个节点中包含不连续的物理内存地址的页面数；
- node_present_pages 是真正可用的物理页面的数目。
struct zonelist node_zonelists[MAX_ZONELISTS];每一个节点分成一个个区域 zone，放在数组 node_zones 里面。这个数组的大小为 MAX_NR_ZONES。
DMA（Direct Memory Access，直接内存存取）的内存。
DMA 是这样一种机制：要把外设的数据读入内存或把内存的数据传送到外设，原来都要通过 CPU 控制完成，但是这会占用 CPU，影响 CPU 处理其他事情，所以有了 DMA 模式。CPU 只需向 DMA 控制器下达指令，让 DMA 控制器来处理数据的传送，数据传送完毕再把信息反馈给 CPU，这样就可以解放 CPU。
区域
struct zone
到这里，我们把内存分成了节点，把节点分成了区域。
冷热页
per_cpu_pageset 用于区分冷热页。什么叫冷热页呢？咱们讲 x86 体系结构的时候讲过，为了让 CPU 快速访问段描述符，在 CPU 里面有段描述符缓存。CPU 访问这个缓存的速度比内存快得多。同样对于页面来讲，也是这样的。如果一个页被加载到 CPU 高速缓存里面，这就是一个热页（Hot Page），CPU 读起来速度会快很多，如果没有就是冷页（Cold Page）。由于每个 CPU 都有自己的高速缓存，因而 per_cpu_pageset 也是每个 CPU 一个。
页
struct page
第一种模式，要用就用一整页。这一整页的内存，或者直接和虚拟地址空间建立映射关系，我们把这种称为匿名页（Anonymous Page）。或者用于关联一个文件，然后再和虚拟地址空间建立映射关系，这样的文件，我们称为内存映射文件（Memory-mapped File）。
第二种模式，仅需分配小块内存。有时候，我们不需要一下子分配这么多的内存，例如分配一个 task_struct 结构，只需要分配小块的内存，去存储这个进程描述结构的对象。为了满足对这种小内存块的需要，Linux 系统采用了一种被称为slab allocator的技术，用于分配称为 slab 的一小块内存。它的基本原理是从内存管理模块申请一整块页，然后划分成多个小块的存储池，用复杂的队列来维护这些小块的状态（状态包括：被分配了 / 被放回池子 / 应该被回收）。
页的分配
1、用户态的分配
进程分配内存的两种方式–brk() 和mmap() 详情见此 Blog
进程分配内存有两种方式，分别由两个系统调用完成：brk和mmap（不考虑共享内存）。
1、brk是将数据段(.data)的最高地址指针_edata往高地址推；
2、mmap是在进程的虚拟地址空间中（堆和栈中间，称为文件映射区域的地方）找一块空闲的虚拟内存。
这两种方式分配的都是虚拟内存，没有分配物理内存。在第一次访问已分配的虚拟地址空间的时候，发生缺页中断，操作系统负责分配物理内存，然后建立虚拟内存和物理内存之间的映射关系。
2、内核态的分配
伙伴算法
对于要分配比较大的内存，例如到分配页级别的，可以使用伙伴系统（Buddy System）。
一种物理内存分配和回收的方法，物理内存所有空闲页都记录在BUDDY链表中。
首先，系统建立一个链表，链表中的每个元素代表一类大小的物理内存，分别为2的0次方、1次方、2次方，个页大小，对应4K、8K、16K的内存，每一类大小的内存又有一个链表，表示目前可以分配的物理内存。当向内核请求分配 (2^(i-1)，2^i] 数目的页块时，按照 2^i 页块请求处理。
例如现在仅存需要分配8K的物理内存，系统首先从8K那个链表中查询有无可分配的内存，若有直接分配；否则查找16K大小的链表，若有，首先将16K一分为二，将其中一个分配给进程，另一个插入8K的链表中，若无，继续查找32K，若有，首先把32K一分为二，其中一个16K大小的内存插入16K链表中，然后另一个16K继续一分为二，将其中一个插入8K的链表中，另一个分配给进程……..以此类推。当内存释放时，查看相邻内存有无空闲，若存在两个联系的8K的空闲内存，直接合并成一个16K的内存，插入16K链表中。
每一个 zone，都有伙伴系统维护的各种大小的队列
系统中所有的页面都存储在数组mem_map[]中，可以通过该数组找到系统中的每一页（空闲或非空闲）。而其中的空闲页面则可由上述提到的以伙伴关系组织的空闲页链表（free_area[MAX_ORDER]）来索引。
缺点：
-
合并的要求太过严格，只能是满足伙伴关系的块才能合并，比如第1块和第2块就不能合并。
-
碎片问题：一个连续的内存中仅仅一个页面被占用，导致整块内存区都不具备合并的条件
-
浪费问题：伙伴算法只能分配2的幂次方内存区，当需要8K（2页）时，好说，当需要9K时，那就需要分配16K（4页）的内存空间，但是实际只用到9K空间，多余的7K空间就被浪费掉。
-
算法的效率问题： 伙伴算法涉及了比较多的计算还有链表和位图的操作，开销还是比较大的，如果每次2^n大小的伙伴块就会合并到2^(n+1)的链表队列中，那么2^n大小链表中的块就会因为合并操作而减少，但系统随后立即有可能又有对该大小块的需求，为此必须再从2^(n+1)大小的链表中拆分，这样的合并又立即拆分的过程是无效率的。
SLAB算法
是一种对伙伴算法的一种补充，对于用户进程的内存分配，伙伴算法已经够好了，但对于内核进程，还需要存在一类很小的数据（字节大小，比如进程描述符、虚拟内存描述符等），若每次给几个字节的数据分配一个4KB的页，实在太浪费，于是就有了SLBA算法，SLAB算法其实就是把一个页用力劈成一小块一小块，然后再分配。
内存片段（小块内存）被看作对象，当被使用完后，并不直接释放而是被缓存到“存储池”里，留做下次使用，这无疑避免了频繁创建与销毁对象所带来的额外负载。
root@hjh-Ubuntu:~# more /proc/slabinfo slabinfo - version: 2.1 # name <active_objs> <num_objs> <objsize> <objperslab> <pagesperslab> : tunables <limit> <batchcount> <sharedfactor> : slabdata <active_slabs> <num_slabs> <sharedavail> uvm_tools_event_tracker_t 0 0 1128 29 8 : tunables 0 0 0 : slabdata 0 0 0通过
/proc/slabinfo查看可以找到内核执行现场使用的各种slab信息统计
- Kmalloc
Slab分配器不仅仅只用来存放内核专用的结构体，它还被用来处理内核对小块内存的请求。当然鉴于Slab分配器的特点，一般来说内核程序中对小于一页的小块内存的请求才通过Slab分配器提供的接口Kmalloc来完成（虽然它可分配32 到131072字节的内存）。从内核内存分配的角度来讲，kmalloc可被看成是get_free_page（s）的一个有效补充，内存分配粒度更灵活了。
内核非连续内存分配（Vmalloc）
分片
分片又分为外部分片和内部分片之说，所谓内部分片是说系统为了满足一小段内存区（连续）的需要，不得不分配了一大区域连续内存给它，从而造成了空间浪费；外部分片是指系统虽有足够的内存，但却是分散的碎片，无法满足对大块“连续内存”的需求。无论何种分片都是系统有效利用内存的障碍。
伙伴关系也好、slab技术也好，从内存管理理论角度而言目的基本是一致的，它们都是为了防止“分片”
- slab分配器使得一个页面内包含的众多小块内存可独立被分配使用，避免了内部分片，节约了空闲内存。
- 伙伴关系把内存块按大小分组管理，一定程度上减轻了外部分片的危害，因为页框分配不在盲目，而是按照大小依次有序进行，不过伙伴关系只是减轻了外部分片，但并未彻底消除。
vmalloc
所以避免外部分片的最终思路还是落到了如何利用不连续的内存块组合成“看起来很大的内存块”——这里的情况很类似于用户空间分配虚拟内存，内存逻辑上连续，其实映射到并不一定连续的物理内存上。Linux内核借用了这个技术，允许内核程序在内核地址空间中分配虚拟地址，同样也利用页表（内核页表）将虚拟地址映射到分散的内存页上。以此完美地解决了内核内存使用中的外部分片问题。内核提供vmalloc函数分配内核虚拟内存，该函数不同于kmalloc，它可以分配较Kmalloc大得多的内存空间（可远大于128K，但必须是页大小的倍数），但相比Kmalloc来说,Vmalloc需要对内核虚拟地址进行重映射，必须更新内核页表，因此分配效率上要低一些（用空间换时间）
与用户进程相似,内核也有一个名为init_mm的mm_strcut结构来描述内核地址空间，其中页表项pdg=swapper_pg_dir包含了系统内核空间（3G-4G）的映射关系。
因此vmalloc分配内核虚拟地址必须更新内核页表，而kmalloc或get_free_page由于分配的连续内存，所以不需要更新内核页表。
总结 kmalloc 和 vmalloc
由get_free_page或Kmalloc函数所分配的连续内存都陷于物理映射区域，所以它们返回的内核虚拟地址和实际物理地址仅仅是相差一个偏移量（PAGE_OFFSET），你可以很方便的将其转化为物理内存地址，同时内核也提供了virt_to_phys（）函数将内核虚拟空间中的物理映射区地址转化为物理地址。要知道，物理内存映射区中的地址与内核页表是有序对应的，系统中的每个物理页面都可以找到它对应的内核虚拟地址（在物理内存映射区中的）。
而vmalloc分配的地址则限于vmalloc_start与vmalloc_end之间。每一块vmalloc分配的内核虚拟内存都对应一个vm_struct结构体（可别和vm_area_struct搞混，那可是进程虚拟内存区域的结构），不同的内核虚拟地址被4k大小的空闲区间隔，以防止越界）。与进程虚拟地址的特性一样，这些虚拟地址与物理内存没有简单的位移关系，必须通过内核页表才可转换为物理地址或物理页。它们有可能尚未被映射，在发生缺页时才真正分配物理页面。
但是应该注意的是，vmalloc()申请物理内存时是立即分配的，因为内核认为这种内存分配请求是正当而且紧急的；相反，用户态有内存请求时，内核总是尽可能的延后，毕竟用户态跟内核态不在一个特权级。
- 物理内存的连续性一般是由于设备驱动的使用，或者DMA. 但是vmalloc申请效率比较低，还会造成TLB抖动. 一般内核里常用kmalloc.
- kmalloc和vmalloc是分配的是内核的内存,malloc分配的是用户的内存
- kmalloc保证分配的内存在物理上是连续的,vmalloc保证的是在虚拟地址空间上的连续
- kmalloc能分配的大小有限,vmalloc和malloc能分配的大小相对较大
页面换出
现代操作系统使用分页机制和虚拟内存，同时为了提高物理页面的利用率，采用了请求调页的机制，即物理内存的分配只有在真正需要的时候才会进行，比如发生了真正的读写操作。
什么情况下会触发页面换出呢？
1、启动一个程序时，装载器把进程可执行文件映射到进程的虚拟地址空间中，注意是虚拟地址空间，从入口函数开始分配一定数量的物理内存页，让其运行。事实上，某个程序可以使用的物理内存页数量基本是固定的（一般运行过程中），当执行到的代码没有在内存中，就会发生pagefault，进而由内存管理器把相应页面调入到内存，如果进程物理页面没有空间，就考虑换出某些页面。而不止是代码，进程中动态申请的内存也有可能由于内存紧张被换出到外存，在需要的时候再调入到内存中。合理的换入换出机制能够充分发挥现代操作系统多任务的优势，各个任务均能够正常的运行。但是换入换出机制毕竟需要和磁盘打交道，磁盘IO一直以来都是性能的瓶颈所在，所以设计一个良好的换入换出机制显得异常重要。
2、当然还有一种情况，就是作为内存管理系统应该主动去做的，而不能等真的出了事儿再做，这就是内核线程kswapd0。这个内核线程，在系统初始化的时候就被创建。这样它会进入一个无限循环，直到系统停止。在这个循环中，如果内存使用没有那么紧张，那它就可以放心睡大觉；如果内存紧张了，就需要去检查一下内存，看看是否需要换出一些内存页。
kswapd0：主要作用是用来回收内存。在kswapd中，有2个阀值，pages_hige和pages_low。当空闲内存页的数量低于pages_low的时候，kswapd进程就会扫描内存并且每次释放出32个 free pages，直到freepage的数量到达pages_high。具体回收内存有如下原则：
- 如果页未经更改就将该页放入空闲队列；
- 如果页已经更改并且是可备份回文件系统的，就理解将内存页的内容写回磁盘；
- 如果页已经更改但是没有任何磁盘上的备份，就将其写入swap分区。
所有的页面都被挂在 LRU 列表中。LRU 是 Least Recent Use，也就是最近最少使用。也就是说，这个列表里面会按照活跃程度进行排序，这样就容易把不怎么用的内存页拿出来做处理。
内存页总共分两类，一类是匿名页，和虚拟地址空间进行关联；一类是内存映射，不但和虚拟地址空间关联，还和文件管理关联。
它们每一类都有两个列表，一个是 active，一个是 inactive。顾名思义，active 就是比较活跃的，inactive 就是不怎么活跃的。这两个里面的页会变化，过一段时间，活跃的可能变为不活跃，不活跃的可能变为活跃。如果要换出内存，那就是从不活跃的列表中找出最不活跃的，换出到硬盘上。