linux内存管理总结之内存分配

 1.伙伴系统
    伙伴系统规定，无论是已分配内存块和空闲内存块，其大小都是2的k次幂个页面的大小，k的取值范围是0到MAX_ORDER 。当需要分配一个
大小为n个页面大小的内存块时，先计算一个i值，使2^i-1 <= n <= 2^i ,然后在空闲内存块页面大小为2^i的链表中查找，若无符合要求的块，则在
2^i+1的链表中查找......，这种情况下这样一个大的内存块便被分为了两部分，两部分彼此成为了伙伴，一部分被分配，另一部分被加入对应的链表
中。当一个块被释放时，会检测其伙伴 ，若空闲，则合并为一个大的内存块。
    linux为每个不同的zone使用了不同的伙伴系统，可以cat  /proc/buddyinfo查看其使用信息。每个zone描述符都有free_area_t结构数组，每个结
构描述了数组索引对应的空闲页面块链表和一对伙伴状态的位图。

 2.slab

    分配和释放数据结构是所有内核中很普遍的操作，如果为了存放很少的字节而分配一个物理页，显然是不合理的，况且频繁的分配和释放会使伙伴
系统的开销增大。linux中采用了slab来处理这种情况。缓存一些数据结构作为对象，每种对象对应一个高速缓存。高速缓存被划分为多个slab,slab由
1页或多个连续的物理页组成，多数情况下为1页。每个slab都包含一些对象成员，即缓存的数据结构。当需要一个新对象时，就从对应slab中分配空闲
的对象。
    innode结构是磁盘索引节点在内存中的体现，内核中使用slab来管理其创建和释放。struct inode由inode_cachep高速缓存进行分配，内核请求分配
一个新的inode结构时，内核就从部分满或者空的slab(若没有部分满的slab）返回一个已分配但未被使用的结构的指针。

    使用cat /proc/slabinfo查看高速缓存相关信息。
 
3.接口函数
    内核提供了几个接口用来实现在内核中分配和释放内存，所有接口都可以追溯至alloc_pages_node，这个函数做一个检查，避免分配过大的内存块，
接着该函数调用了__alloc_pages()进行实质性的内存分配。__alloc_pages()从来不被直接调用，需要接口函数选择从哪个node和zone进行分配，而
__alloc_pages检查选定的zone中可分配页面的数量是否满足分配要求（但是不知道页面是否连续），若是不满足，会退至其他区进行分配。通常，接
口函数如果没有指定__GFP_DMA和GFP__HIGHMEM标志，相当于只设置了GFP_NORMAL，则会先会扫描ZONE_NORMAL，其次为__GFP_DMA；
如果只是设定了GFP__HIGHMEM，扫描次序分别为ZONE_HIGHMEM、ZONE_NORMAL、ZONE_DMA;  如果只是设定了GFP_DMA则只在 ZONE_DMA
分配。选定了zone后，若是请求分配的页数为1,该页并不直接从伙伴系统获得，而是取自per-CPU的页缓存。若是请求分配多个物理页，内核调用__rmqueue
从伙伴系统的相应链表中选择内存块。具体内容可参考PLKA。

    核心接口函数是alloc_pages:
    alloc_pages(gfp_t gfp_mask, unsigned int order);
    该函数分配2^order个连续的物理页，成功返回指向第一个页面的指针，出错返回NULL;若是gfp_mask没有明确指定__GFP_HIGHMEM，则分配的物理页面肯
定不是高端内存，因此通过void *page_address(struct page *page)肯定会获得其相应的虚拟地址。  
    当gfp_mask 指定__GFP_HIGHMEM，那么页分配器会优先高端内存分配物理页，若是高端内存没有足够页面，也可从常规内存和DMA区分配。
    alloc_page(gfp_mask)是该函数的变体，只分配一页。
    void __free_pages(*page, order)用来释放分配的页。该函数先做一个检查，如果释放的是一页，则不还给伙伴系统而是放入到per-CPU缓存中。否则，该函数
调用了__free_pages_ok()。在释放页时，伙伴系统会判断是否需要合并伙伴。
    
    函数__get_free_pages(gfp_t gfp_mask, unsigned int order)也是分配连续的物理页，但是他只能在低端内存中分配页面，分配成功返回第一个页的虚拟地址。这个
函数必须进行错误检查。
    __get_free_page(gfp_mask)是该函数的变体，只分配一页。
    get_zero_page(gfp_mask)是该函数的变体，分配填充为0的一页
    void free_pages(addr, order)用来释放分配的页。

    kmalloc(size_t,gtp_t)也是用来分配连续的物理页，但是它建立在slab分配器基础之上，使用了一组通用高速缓存，在系统初始化（start_kernel)期间由kmem_cache_init创建（专用高速缓存由kmem_cache_create()创建）。如果分配器中没有空闲的对象可用，则必须新建一个slab，最终会调用__aolloc_pages,

kmalloc()只能在低端分配内存，即便指定 __GFP_HIGHMEM，这个标志也会被清除，最后返回低端的逻辑地址。kfree()用来释放分配的内存。

4.非连续内存分配

    将内存区域映射到连续的物理页是最好的选择，这样可以充分利用高速缓存。若是将不连续的物理页映射到在内核空间连续的虚拟页，必须一个一个的映射，并建立页表，频繁的修改页表使处理器频繁的刷新TLB，造成平均访问内存时间增加。不过若是对内存区的请求不是很频繁，这种方法可以有效的避免外部碎片；或者需要分配一大段内存，调用kmalloc()可能失败时，也应当采用这种方法。vmalloc便是用来实现这种分配的。

    vmalloc(unsigned long size);

    vmalloc（）映射到的连续虚拟地址位于VMALLOC_START到VMALLOC_END之间。使用vmalloc()映射内存时，先从该区域分配出可用的连续的一段；接着通过伙伴系统获得物理页，此时使用了GFP_KERNEL|__GFP_HIGHMEM标志，优先从高端内存获得物理页，这样是为了节省宝贵的低端内存，而不是专门为了映射高端内存。分配物理页时每次只分配一页，保证了内存即使有很严重的碎片，分配仍可正常进行（分配大块连续的物理页可以用alloc_pages(__HIGHMEM) ），重复调用
alloc_page()的过程中，会将分配的页描述符stuct page结构的指针存放在一个数组中,。最后内核调用map_vm_area()将这些页连续的映射到vmalloc区域并修改更新
master kernel Page Global Directory,当内核态进程访问vmalloc区的这一段时，因为该段所对应的进程页表表项为空，缺页异常发生，处理程序检查master kernel Page Global Directory是否有该线性地址的表项，就会把他的值复制到相应的进程页表项中。

    vmalloc()是可能睡眠的，因为其调用了kmalloc(GFP_KERNEL)来获得页表的存储空间。
    vfree()用来释放分配的内存。

 5.内核映射
    高端内存物理页的分配只能通过alloc_pages和alloc_page。内核使用两种机制将高端内存映射到内核空间：内核映射（分为永久映射和临时映射）和非连续内存分配（vmalloc)。这两方法底层机制是不同的。vmalloc会分配一段连续的虚拟地址vm_struct,尽量从高端内存对应的伙伴系统分配内存，每个页面都需要独立的调用函数alloc_page.，还需专门的建立页表。而内核映射是显式的将高端内存映射到地址空间，并返回线性地址，例如先通过alloc_page(__GFP_HIGHMEM)得到物理页，再使用kmap(struct page *page)来建立到永久映射区的映射。
    内核在vmalloc区之后分配了一个地址从PKMAP _BASE 到FIXADDR_START的区域作为永久映射区 。永久映射使用master kernel Page Global Directory中一个专门的页表pkmap_page_table中，他位于PKMAP _BASE处，页表的表项由宏LAST_PKMAP 产生。当前页表项的状态由数组pkmap_count[LAST_PKMAP]简单管理，其中的每一项为被映射页的计数器个数：计数器为0,对应页表项没有映射高度内存并且可用;计数器为1，对应的页表虽被映射，但是TLB 没被刷新，因为当全局的页表被更改时，需要对所有的CPU刷新，因此每个表项全部至少使用一次后才被刷新以防止过大的开销; 任意更高的数值表示内核有n-1处使用该页。为记录高端内存物理页与永久映射关联的虚拟地址的关系，内核使用了散列表page_address_htable，该表包含一个page_address_map结构，每个结构包含一个page结构指针和分配给page的虚拟地址。
     kmap()先调用PageHighMEM()检查指定的页是否位于高端内存，若不是，则返回由page_address()得到的逻辑地址 ,page_address()接受一个sturct *page作为参数，如果物理页不在高端内存，它调用__va()将其转为逻辑地址;如果物理页处于高端内存，该函数到page_address_htable散列表中查找，如果在其中找到对应的物理页，就返回物理页的虚拟地址。    确认物理页位于高端内存后，内核调用kmap_high(),该函数使用page_address()检查该页是否被映射到永久映射区，如果没有，必须调用map_new_virtual()映射该页，这时函数先反向扫描pkmap_count数组找到一个空闲位置，若是没有找到函数就会睡眠。找到空闲位置后，函数修改页表，物理页被映射到相应位置，但是TLB尚未更新，计数器设为1，更新散列表page_address_htable，最后函数返回新映射页的虚拟地址。
    kunmap()用来解除映射。

    上面分析可知kmap()是可能睡眠的，为了在中断上下文等环境下映射高端内存，内核提供了一个备选的映射函数，其执行是原子的，其具体实现与固定映射区有关，固定映射区有一组保留的映射，内核可以原子的把高端内存中的一个页映射到某个保留的映射中，具体来说就是利用固定内核映射中的一段空间，为每个CPU保存13个窗口，每个窗口的功能是固定的，不同进程需 要分配同一个窗口的时候就进行覆盖，因此不会导致进程阻塞。
    void *kmap_atomic(struct page *page, enum km_type tpye);
    枚举类型type描述了临时映射的目的，对应一个保留的映射。

    稍微总结一下：vmallc()和kmap()虽然都需要建立页表，然而vmalloc()主要是建立动态分配和释放的内存区，建立和释放的过程非常复杂，需要对pgd,pud,pmd,pte进行修改。而永久内核映射就简单的多，在32位x86上，如果没有设置PAE，则有4MB的线性 地址可以用来映射，4MB当然是只有一个页表就够用了，这个专门的页表地址存放在pkmap_page_table变量中。只需要设置这个页表中相应的表 项就可以了，一共1024个表项，每个对应一个4KB的页，因为表项比较少，耗尽的时候会导致进程阻塞，这样就不能用在中断处理程序中。而临时内核映 射则更加简单了，其实就是永久内核映射的原子实现版，因此可以用于中断处理程序和可延迟函数的内部。

6,ioremap
    每个设备的I/O端口都被组织成一组专用寄存器，比如控制寄存器、状态寄存器、输出寄存器、输入寄存器，为降低成本，通常把同一i/o端口用于不同目的。
    有些体系结构的CPU（如PowerPC）通常只实现一个物理地址空间（RAM）。在这种情况下，外设I/O端口的物理地址就被映射到CPU的单一物理地址空间中，而成为内存的一部分，通常I/O端口映射到的这一部分物理地址是连续的。此时，CPU可以象访问一个内存单元那样访问外设I/O端口，而不需要设立专门的外设I/O指令。这就是所谓的“内存映射方式”。
    而另外一些体系结构的CPU（典型地如X86）则为外设专门实现了一个单独地地址空间，称为“I/O地址空间”或者“I/O端口空间”。这是一个与CPU地RAM物理地址空间不同的地址空间，所有外设的I/O端口均在这一空间中进行编址。CPU通过设立专门的I/O指令（如X86的IN和OUT指令）来访问这一空间中的地址单元（也即I/O端口）。这就是所谓的“I/O映射方式”（I/O－mapped）。与RAM物理地址空间相比，I/O地址空间通常都比较小，如x86 CPU的I/O空间就只有64KB。

    对于两种方式，需要说明的是，因为最流行的I/O 总线总是基于PC，即便是内存映射方式，在访问I/O端口映射到的物理地址时，需要增加控制逻辑形成对应的I/O读写信号。    还有一点，即便采用的是I/O映射方式，也并非所有的设备都会把寄存器映射到I/O地址空间，ISA设备普遍采用I/O端口，而大多数PCI设备把寄存器映射到某个内存地址区段。　　Linux将基于I/O映射方式的或内存映射方式的I/O端口通称为“I/O区域”（I/O region）。在硬件层，I/O区域和内存区域没有概念上的区别，都通过地址总线和控制总线发送电平信号进行访问，再通过数据总线进行读写。
    再说明一个概念，映射到内存的寄存器或设备内存都被称为I/O内存。一般来说，在系统运行时，外设的I/O内存资源的物理地址是已知的，由硬件的设计决定。但是CPU通常并没有为这些已知的外设I/O内存的物理地址预定义虚拟地址范围，驱动程序并不能直接通过物理地址访问I/O内存资源，而必须使用ioremap()将它们映射到内核空间内（通过页表），然后才能根据映射所得到的虚地址范围，通过一组专用函数访问I/O内存（这里避免直接使用指针）。 最为人所知的I/O 内存区是PC上的ISA内存段，其范围是640K到1MB之间; 对于PCI设备的I/O内存，只要知道了其物理地址，就能简单地重映射并访问这些内存。  

    void * ioremap(unsigned long phys_addr, unsigned long size, unsigned long flags);
    ioremap是面向页的，需要建立页表，但是并不实际分配内存，常常用来将PCI设备内存映射到内核空间。某些情况，PCI设备的地址可能映射到逻辑地址，这样是无需建立页表的，直接通过偏移操作即可。
    iounmap用来解除这个映射。