12c4f8b9cSfslongjin# MMIO 22c4f8b9cSfslongjin 32c4f8b9cSfslongjinMMIO是“内存映射IO”的缩写，它被广泛应用于与硬件设备的交互之中。 42c4f8b9cSfslongjin 52c4f8b9cSfslongjin## 地址空间管理 62c4f8b9cSfslongjin 72c4f8b9cSfslongjinDragonOS中实现了MMIO地址空间的管理机制，本节将介绍它们。 82c4f8b9cSfslongjin 92c4f8b9cSfslongjin### 为什么需要MMIO地址空间自动分配？ 102c4f8b9cSfslongjin 112c4f8b9cSfslongjin  由于计算机上的很多设备都需要MMIO的地址空间，而每台计算机上所连接的各种设备的对MMIO地址空间的需求是不一样的。如果我们为每个类型的设备都手动指定一个MMIO地址，会使得虚拟地址空间被大大浪费，也会增加系统的复杂性。并且，我们在将来还需要为不同的虚拟内存区域做异常处理函数。因此，我们需要一套能够自动分配MMIO地址空间的机制。 122c4f8b9cSfslongjin 132c4f8b9cSfslongjin### 这套机制提供了什么功能？ 142c4f8b9cSfslongjin 152c4f8b9cSfslongjin- 为驱动程序分配4K到1GB的MMIO虚拟地址空间 162c4f8b9cSfslongjin- 对于这些虚拟地址空间，添加到VMA中进行统一管理 172c4f8b9cSfslongjin- 可以批量释放这些地址空间 182c4f8b9cSfslongjin 192c4f8b9cSfslongjin### 这套机制是如何实现的？ 202c4f8b9cSfslongjin 212c4f8b9cSfslongjin  这套机制本质上是使用了伙伴系统来对MMIO虚拟地址空间进行维护。在`mm/mm.h`中指定了MMIO的虚拟地址空间范围，这个范围是`0xffffa10000000000`开始的1TB的空间。也就是说，这个伙伴系统为MMIO维护了这1TB的虚拟地址空间。 222c4f8b9cSfslongjin 232c4f8b9cSfslongjin### 地址空间分配过程 242c4f8b9cSfslongjin 252c4f8b9cSfslongjin1. 初始化MMIO-mapping模块，在mmio的伙伴系统中创建512个1GB的`__mmio_buddy_addr_region` 262c4f8b9cSfslongjin2. 驱动程序使用`mmio_create`请求分配地址空间。 272c4f8b9cSfslongjin3. `mmio_create`对申请的地址空间大小按照2的n次幂进行对齐，然后从buddy中申请内存地址空间 282c4f8b9cSfslongjin4. 创建VMA，并将VMA标记为`VM_IO|VM_DONTCOPY`。MMIO的vma只绑定在`initial_mm`下，且不会被拷贝。 292c4f8b9cSfslongjin5. 分配完成 302c4f8b9cSfslongjin 312c4f8b9cSfslongjin一旦MMIO地址空间分配完成，它就像普通的vma一样，可以使用mmap系列函数进行操作。 322c4f8b9cSfslongjin 332c4f8b9cSfslongjin### MMIO的映射过程 342c4f8b9cSfslongjin 352c4f8b9cSfslongjin  在得到了虚拟地址空间之后，当我们尝试往这块地址空间内映射内存时，我们可以调用`mm_map`函数，对这块区域进行映射。 362c4f8b9cSfslongjin 372c4f8b9cSfslongjin  该函数会对MMIO的VMA的映射做出特殊处理。即：创建`Page`结构体以及对应的`anon_vma`. 然后会将对应的物理地址，填写到页表之中。 382c4f8b9cSfslongjin 392c4f8b9cSfslongjin### MMIO虚拟地址空间的释放 402c4f8b9cSfslongjin 412c4f8b9cSfslongjin  当设备被卸载时，驱动程序可以调用`mmio_release`函数对指定的mmio地址空间进行释放。 422c4f8b9cSfslongjin 432c4f8b9cSfslongjin  释放的过程中，`mmio_release`将执行以下流程： 442c4f8b9cSfslongjin 452c4f8b9cSfslongjin1. 取消mmio区域在页表中的映射。 462c4f8b9cSfslongjin2. 将释放MMIO区域的VMA 472c4f8b9cSfslongjin3. 将地址空间归还给mmio的伙伴系统。 48*c2481452Shoumkh 49*c2481452Shoumkh## MMIO的伙伴算法 50*c2481452Shoumkh 51*c2481452Shoumkh### 伙伴的定义 52*c2481452Shoumkh 53*c2481452Shoumkh  同时满足以下三个条件的两个内存块被称为伙伴内存块： 54*c2481452Shoumkh 55*c2481452Shoumkh1. 两个内存块的大小相同 56*c2481452Shoumkh2. 两个内存块的内存地址连续 57*c2481452Shoumkh3. 两个内存块由同一个大块内存分裂得到 58*c2481452Shoumkh 59*c2481452Shoumkh### 伙伴算法 60*c2481452Shoumkh 61*c2481452Shoumkh  伙伴（buddy）算法的作用是维护以及组织大块连续内存块的分配和回收，以减少系统时运行产生的外部碎片。伙伴系统中的每个内存块的大小均为$2^n$。 在DragonOS中，伙伴系统内存池共维护了1TB的连续存储空间，最大的内存块大小为$1G$，即$2^{30}B$，最小的内存块大小为$4K$，即 $2^{12}B$。 62*c2481452Shoumkh 63*c2481452Shoumkh  伙伴算法的核心思想是当应用申请内存时，每次都分配比申请的内存大小更大的最小内存块，同时分配出去的内存块大小为$2^nB$。（e.g. 假设某应用申请了$3B$内存，显然并没有整数值n，使$2^n = 3$ ，且$3 \in [2^1,2^2]$，所以系统会去取一块大小为$2^2B$的内存块，将它分配给申请的应用，本次申请内存操作顺利完成。） 64*c2481452Shoumkh 65*c2481452Shoumkh  那么当伙伴系统中没有如此“合适”的内存块时该怎么办呢？系统先会去寻找更大的内存块，如果找到了，则会将大内存块分裂成合适的内存块分配给应用。（e.g. 假设申请$3B$内存，此时系统中比$3B$大的最小内存块的大小为$16B$，那么$16B$会被分裂成两块$8B$的内存块，一块放入内存池中，一块继续分裂成两块$4B$的内存块。两块$4B$的内存块，一块放入内存池中，一块分配给应用。至此，本次申请内存操作顺利完成。） 66*c2481452Shoumkh 67*c2481452Shoumkh  如果系统没有找到更大的内存块，系统将会尝试合并较小的内存块，直到符合申请空间的大小。（e.g. 假设申请$3B$内存，系统检查内存池发现只有两个$2B$的内存块，那么系统将会把这两个$2B$的内存块合并成一块$4B$的内存块，并分配给应用。至此，本次申请内存操作顺利完成。） 68*c2481452Shoumkh 69*c2481452Shoumkh  最后，当系统既没有找到大块内存，又无法成功合并小块内存时，就会通知应用内存不够，无法分配内存。 70*c2481452Shoumkh 71*c2481452Shoumkh### 伙伴算法的数据结构 72*c2481452Shoumkh 73*c2481452Shoumkh``` 74*c2481452Shoumkh 75*c2481452Shoumkh MmioBuddyMemPool 76*c2481452Shoumkh 77*c2481452Shoumkh┌─────────────────────────────────────────────────────────────────────────────────────┐ 78*c2481452Shoumkh│ │ 79*c2481452Shoumkh│ pool_start_addr │ 80*c2481452Shoumkh│ │ 81*c2481452Shoumkh├─────────────────────────────────────────────────────────────────────────────────────┤ 82*c2481452Shoumkh│ │ 83*c2481452Shoumkh│ pool_size │ 84*c2481452Shoumkh│ │ 85*c2481452Shoumkh├─────────────────────────────────────────────────────────────────────────────────────┤ 86*c2481452Shoumkh│ │ 87*c2481452Shoumkh│ │ 88*c2481452Shoumkh│ free_regions │ 89*c2481452Shoumkh│ │ 90*c2481452Shoumkh│ ┌────────────┐ │ 91*c2481452Shoumkh│ │ │ ┌───────┐ ┌────────┐ │ 92*c2481452Shoumkh│ │ ┌────────┬─┼────►│ ├────►│ │ │ 93*c2481452Shoumkh│ │ │ list │ │ │ vaddr │ │ vaddr │ │ 94*c2481452Shoumkh│ │ │ │◄├─────┤ │◄────┤ │ │ 95*c2481452Shoumkh│ MmioFreeRegionList├────────┤ │ └───────┘ └────────┘ │ 96*c2481452Shoumkh│ │ │num_free│ │ │ 97*c2481452Shoumkh│ │ └────────┘ │ MmioBuddyAddrRegion │ 98*c2481452Shoumkh│ MMIO_BUDDY_MIN_EXP - 12 │ 0 │ │ 99*c2481452Shoumkh│ ├────────────┤ │ 100*c2481452Shoumkh│ │ 1 │ │ 101*c2481452Shoumkh│ ├────────────┤ │ 102*c2481452Shoumkh│ │ 2 │ │ 103*c2481452Shoumkh│ ├────────────┤ │ 104*c2481452Shoumkh│ │ 3 │ │ 105*c2481452Shoumkh│ ├────────────┤ │ 106*c2481452Shoumkh│ │ ... │ │ 107*c2481452Shoumkh│ ├────────────┤ │ 108*c2481452Shoumkh│ │ ... │ │ 109*c2481452Shoumkh│ ├────────────┤ │ 110*c2481452Shoumkh│ MMIO_BUDDY_MAX_EXP - 12 │ 18 │ │ 111*c2481452Shoumkh│ └────────────┘ │ 112*c2481452Shoumkh│ │ 113*c2481452Shoumkh│ │ 114*c2481452Shoumkh│ │ 115*c2481452Shoumkh└─────────────────────────────────────────────────────────────────────────────────────┘ 116*c2481452Shoumkh``` 117*c2481452Shoumkh 118*c2481452Shoumkh```rust 119*c2481452Shoumkh 120*c2481452Shoumkh/// 最大的内存块为1G，其幂为30 121*c2481452Shoumkhconst MMIO_BUDDY_MAX_EXP: u32 = PAGE_1G_SHIFT; 122*c2481452Shoumkh/// 最小的内存块为4K，其幂为12 123*c2481452Shoumkhconst MMIO_BUDDY_MIN_EXP: u32 = PAGE_4K_SHIFT; 124*c2481452Shoumkh/// 内存池数组的大小为18 125*c2481452Shoumkhconst MMIO_BUDDY_REGION_COUNT: u32 = MMIO_BUDDY_MAX_EXP - MMIO_BUDDY_MIN_EXP + 1; 126*c2481452Shoumkh 127*c2481452Shoumkh/// buddy内存池 128*c2481452Shoumkhpub struct MmioBuddyMemPool { 129*c2481452Shoumkh /// 内存池的起始地址 130*c2481452Shoumkh pool_start_addr: u64, 131*c2481452Shoumkh /// 内存池大小：初始化为1TB 132*c2481452Shoumkh pool_size: u64, 133*c2481452Shoumkh /// 空闲内存块链表数组 134*c2481452Shoumkh /// MMIO_BUDDY_REGION_COUNT = MMIO_BUDDY_MAX_EXP - MMIO_BUDDY_MIN_EXP + 1 135*c2481452Shoumkh free_regions: [SpinLock<MmioFreeRegionList>; MMIO_BUDDY_REGION_COUNT as usize], 136*c2481452Shoumkh} 137*c2481452Shoumkh 138*c2481452Shoumkh/// 空闲内存块链表结构体 139*c2481452Shoumkhpub struct MmioFreeRegionList { 140*c2481452Shoumkh /// 存储了空闲内存块信息的结构体的链表 141*c2481452Shoumkh list: LinkedList<Box<MmioBuddyAddrRegion>>, 142*c2481452Shoumkh /// 当前链表空闲块的数量 143*c2481452Shoumkh num_free: i64, 144*c2481452Shoumkh} 145*c2481452Shoumkh 146*c2481452Shoumkh/// mmio伙伴系统内部的地址区域结构体 147*c2481452Shoumkhpub struct MmioBuddyAddrRegion { 148*c2481452Shoumkh /// 内存块的起始地址 149*c2481452Shoumkh vaddr: u64, 150*c2481452Shoumkh} 151*c2481452Shoumkh 152*c2481452Shoumkh``` 153*c2481452Shoumkh 154*c2481452Shoumkh### 设计思路 155*c2481452Shoumkh 156*c2481452Shoumkh  DragonOS中，使用`MmioBuddyMemPool`结构体作为buddy（为表述方便，以下将伙伴算法简称为buddy）内存池的数据结构，其记录了内存池的起始地址（pool_start_addr）以及内存池中内存块的总大小（pool_size），同时其维护了大小为`MMIO_BUDDY_REGION_COUNT`的双向链表数组（free_regions）。`free_regions`中的各个链表维护了若干空闲内存块（MmioBuddyAddrRegion）。 157*c2481452Shoumkh 158*c2481452Shoumkh  `free_regions`的下标（index）与内存块的大小有关。由于每个内存块大小都为$2^{n}$ bytes，那么可以令$exp = n$。index与exp的换算公式如下：$index = exp - 12$。e.g. 一个大小为$2^{12}$ bytes的内存块，其$exp = 12$，使用上述公式计算得$index = 12 -12 = 0$，所以该内存块会被存入`free_regions[0].list`中。通过上述换算公式，每次取出或释放$2^n$大小的内存块，只需要操作`free_regions[n -12]`即可。DragonOS中，buddy内存池最大的内存块大小为$1G = 2^{30}bytes$，最小的内存块大小为 $4K = 2^{12} bytes$，所以$index\in[0,18]$。 159*c2481452Shoumkh 160*c2481452Shoumkh  作为内存分配机制，buddy服务于所有进程，为了解决在各个进程之间实现free_regions中的链表数据同步的问题，`free_regions`中的链表类型采用加了 {ref}`自旋锁 <_spinlock_doc_spinlock>`（SpinLock）的空闲内存块链表（MmioFreeRegionList），`MmioFreeRegionList`中封装有真正的存储了空闲内存块信息的结构体的链表（list）和对应链表长度（num_free）。有了自选锁后，同一时刻只允许一个进程修改某个链表，如取出链表元素（申请内存）或者向链表中插入元素（释放内存）。 161*c2481452Shoumkh 162*c2481452Shoumkh  `MmioFreeRegionList`中的元素类型为`MmioBuddyAddrRegion`结构体，`MmioBuddyAddrRegion`记录了内存块的起始地址（vaddr）。 163*c2481452Shoumkh 164*c2481452Shoumkh### 伙伴算法内部api 165*c2481452Shoumkh 166*c2481452Shoumkh**P.S 以下函数均为MmioBuddyMemPool的成员函数。系统中已经创建了一个MmioBuddyMemPool类型的全局引用`MMIO_POOL`，如要使用以下函数，请以`MMIO_POOL.xxx()`形式使用，以此形式使用则不需要传入self。** 167*c2481452Shoumkh 168*c2481452Shoumkh| **函数名** | **描述** | 169*c2481452Shoumkh|:----------------------------------------------------------------- |:--------------------------------------------------------- | 170*c2481452Shoumkh| __create_region(&self, vaddr) | 将虚拟地址传入，创建新的内存块地址结构体 | 171*c2481452Shoumkh| __give_back_block(&self, vaddr, exp) | 将地址为vaddr，幂为exp的内存块归还给buddy | 172*c2481452Shoumkh| __buddy_split(&self,region,exp,list_guard) | 将给定大小为$2^{exp}$的内存块一分为二，并插入内存块大小为$2^{exp-1}$的链表中 | 173*c2481452Shoumkh| __query_addr_region(&self,exp,list_guard) | 从buddy中申请一块大小为$2^{exp}$的内存块 | 174*c2481452Shoumkh| mmio_buddy_query_addr_region(&self,exp) | 对query_addr_region进行封装，**请使用这个函数，而不是__query_addr_region** | 175*c2481452Shoumkh| __buddy_add_region_obj(&self,region,list_guard) | 往指定的地址空间链表中添加一个内存块 | 176*c2481452Shoumkh| __buddy_block_vaddr(&self, vaddr, exp) | 根据地址和内存块大小，计算伙伴块虚拟内存的地址 | 177*c2481452Shoumkh| __pop_buddy_block( &self, vaddr,exp,list_guard) | 寻找并弹出指定内存块的伙伴块 | 178*c2481452Shoumkh| __buddy_pop_region( &self, list_guard) | 从指定空闲链表中取出内存区域 | 179*c2481452Shoumkh| __buddy_merge(&self,exp,list_guard,high_list_guard) | 合并所有$2^{exp}$大小的内存块 | 180*c2481452Shoumkh| __buddy_merge_blocks(&self,region_1,region_2,exp,high_list_guard) | 合并两个**已经从链表中取出的**内存块 | 181*c2481452Shoumkh 182*c2481452Shoumkh### 伙伴算法对外api 183*c2481452Shoumkh 184*c2481452Shoumkh| **函数名** | **描述** | 185*c2481452Shoumkh| ----------------------------------------------- | ------------------------------------------- | 186*c2481452Shoumkh| __mmio_buddy_init() | 初始化buddy系统，**在mmio_init()中调用，请勿随意调用** | 187*c2481452Shoumkh| __exp2index(exp) | 将$2^{exp}$的exp转换成内存池中的数组的下标（index） | 188*c2481452Shoumkh| mmio_create(size,vm_flags,res_vaddr,res_length) | 创建一块根据size对齐后的大小的mmio区域，并将其vma绑定到initial_mm | 189*c2481452Shoumkh| mmio_release(vaddr, length) | 取消地址为vaddr，大小为length的mmio的映射并将其归还到buddy中 | 190