内核空间内存分配

首先从内核空间开始，讲解内存管理模式。

主要分为三种方式：

伙伴系统

解决了外部碎片问题，针对大块内存分配设计

Linux中的内存管理的“页”大小为4KB。把所有的空闲页分组为11个块链表，每个块链表分别包含1，2，4，8，16，32，64，128，256，512和1024个连续页的页块。最大可以申请1024个连续页，对应4MB大小的连续内存。

分配和释放规则：

由小到大在空闲块数组中找最小的可用空闲块。如空闲块过大，对可用空闲块进行二等分，直到得到合适的可用空闲块

例如，当向内核请求分配(2^(i-1)，2^i]数目的页块时，如果存在2^i大小的分区（即块链表中所有页加起来的内存和），将其整个分配。如果对应的块链表中没有足够的空闲页块，则在更大的页块链表中找。如果此时s <= 2^(i-1)，则将大小为2^i的分区划分为两个 2^(i-1)的分区。重复这个过程，知道满足(2^(i-1)，2^i]。

举例

如果第一次需要一个100K的空间，那么对于1M的空间进行分块处理，第一次分成两个512K，而对于此时还是不满足2i-1 <100 < 2i，继续分片，对第一个512K进行分片，分成2个256K，而256K还是不满足，所有对第一个256K继续进行分片，分成2个128K，满足了条件，所以此时会将第一个A=128K分出去
此时第二个分配请求，分配240K的空间，那么直接就从B=256K分配出去
第三个分配请求，分配64K的空间，从空间查找发现有128K的空间可以分成2个64K的空间，直接分配出去C=64K
第四个分配请求，分配256K的空间，发现只有512K的空间满足要求，直接分配D=256K
第五个释放请求，释放B空间，发现不满足合并规则，那么内存中有3块内存独立的内存空间
第六个释放请求，释放A空间，发现A空间与后面的地址空间被C地址隔离，导致不满足合并规则
第七个分配请求，申请75K的空间，发现第一个128K满足条件，直接分配E=128K
第八个释放请求，释放C空间，发现C相邻的地址空间，满足合并请求，直接合并成128K，合并后与前后相邻的无法再合并
第九个释放请求，释放E空间，发现E释放后，与后面的128K空间合并成256K，又与后面的256K合并成512K，那么现在只剩下D空间
第十个释放请求，释放D空间，发现D释放后，与后面的256K空间合并成512K，而前面的512K又满足合并条件，可以合并成1M的空间

伙伴合并规则为：内核将满足以下条件的三个块称为伙伴：(1)两个块具有相同的大小，记作b。(2)它们的物理地址是连续的。(3)第一块的第一个页的物理地址是2*(2^b)的倍数。如果找到了该内存块的伙伴，确保该伙伴的所有页都是空闲的，以便进行合并。内存继续检查合并后页块的“伙伴”并检查是否可以合并，依次类推。

可以看出，伙伴系统虽然解决了外部碎片，但是会导致内部碎片，例如，针对上图，我们如果需要一个257K的内存空间，那按照其算法，会分配一个512K的内存空间，那么就会有255K的内存空间浪费。

slab分配器

基本概念

针对小粒度内存分配

伙伴系统以页4kb为最小分配单位，但对于一些时候，这太大了，会造成严重的内存浪费，产生大量内存碎片。

对于伙伴系统和slab分配器，就好比“批发商”和“零售商”，“批发商”，是指按页面管理并分配内存的机制；而“零售商”，则是从“批发商”那里批发获取资源，并以字节为单位，管理和分配内存的机制。

目前有三种实现算法，分别是slab、slob，slub。并且，依据它们各自的分配算法，在适用性方面会有一定的侧重。

基于伙伴分配器获得连续的pages，作为某数据结构对象的缓存，再将这段连续的pages从内部切割成一个个对齐的对象，使用时从中取用，这样一段连续的page我们称为一个slab。

每个高速缓存（kmem_cache）由多个slab组成，每个slab由一个或多个物理上连续的页组成。

当内核请求对象内存时，slab 分配器可以返回刚好表示对象的所需内存。

slab分配内存

当使用kmem_cache_alloc()申请内存的时候，优先从本地cpu的slab缓存池申请。如果没有可用对象，从公用per node partial中分配，如果也没有可用对象的话，就只能从伙伴系统分配一个slab了，并挂入per cpu freelist。

slab释放内存

过于复杂，暂时放置

主要结构体

kmem_cache

使用kmem_cache_create()接口创建kmem_cache

结构描述的一段内存就称作一个slab缓存池。一个slab缓存池就像是一箱牛奶，一箱牛奶中有很多瓶牛奶，每瓶牛奶就是一个object。分配内存的时候，就相当于从牛奶箱中拿一瓶。总有拿完的一天。当箱子空的时候，你就需要去超市再买一箱回来。超市就相当于partial链表，超市存储着很多箱牛奶。如果超市也卖完了，自然就要从厂家进货，然后出售给你。厂家就相当于伙伴系统。

per cpu freelist

每一个cpu都会分配一个struct kmem_cacche_cpu的结构体。可以称作是本地缓存池。