Physical Memory
Linux物理内存
架构
Linux使用节点(node)，区域(zone)，页(page)三级结构来描述整个物理内存。
一个物理内存分为好几个node，每个node存在好几个zone，每个zone中细分为page大小。
一个内存zone中包含该zone中所有可用的内存页。
struct zone {
struct free_area free_area[MAX_ORDER];
...
}
struct free_area {
struct list_head free_list[MIGRATE_TYPES];
unsigned long nr_free;
}不同大小的内存块，即order不同的块，挂载在不同的链表上，内存不够时，从更大order的链表中取一块下来，并切分到合适的大小，由Buddy分配器管理。
节点（node）
目前计算机系统有两种体系结构：
- 非一致性内存访问 NUMA（Non-Uniform Memory Access）意思是内存被划分为各个node，访问一个node花费的时间取决于CPU离这个node的距离。每一个cpu内部有一个本地的node，访问本地node时间比访问其他node的速度快
- 一致性内存访问 UMA（Uniform Memory Access）也可以称为SMP（Symmetric Multi-Process）对称多处理器。意思是所有的处理器访问内存花费的时间是一样的。也可以理解整个内存只有一个node。
- NUMA通常用在服务器领域，可以通过CONFIG_NUMA来配置是否开启
区（zone）
为了一些特殊需求，如DMA，Linux内存分区zone。
- ZOME_DMA
- ZOME_DMA32
- ZOME_NORMAL
- ZOME_HIGHEM：高端内存，用于32位下访问超过4GB的内存。由于64位的空间足够，故64位不含该区。
页（page）
- 分配的基本单位是页，每一个页都对应一个struct page结构体。
其他概念
页框\页帧（page frame）
为了描述一个物理page，内核使用struct page结构来表示一个物理页。假设一个page的大小是4K的，内核会将整个物理内存分割成一个一个4K大小的物理页，而4K大小物理页的区域我们称为page frame。
Page Frame Num(PFN)
将物理地址分成一块一块的大小，就比如大小是4K的话，将一个物理页的区域我们称为page frame, 而对每个page frame的编号就称为PFN.
物理地址和pfn的关系是：物理地址>>PAGE_SHIFT = pfn
内存分配与释放
Linux物理内存分配是以页为单位，x86架构下，每页4Kb，即$2^{12}$bit。
以下以x86为例，即每页4Kb，$2^{12}$bit。
Linux的内存分配策略是Buddy策略+Slab策略
内存的管理主要是处理外部碎片和内部碎片。
Buddy分配$2^{n}$为单位的内存页，不存在外部碎片。
Slab先获取合适大小的Buddy内存，这块内存可以被对象大小整除，也就不存在内部碎片。
Buddy分配器
Buddy System是最基本的分配器，从 zone 中分配内存，zone 中使用一个数组来管理不同大小的Buddy, 该字段定义如下：
/* file: include/linux/mmzone.h */
struct zone {
/* free areas of different sizes */
struct free_area free_area[MAX_ORDER];
}在同一个free_area中的空闲空间大小相同，free_area[i]存储的的是$2^{i}$个页面的空闲的、物理连续的内存块，即每块$2^{i} × 2^{12}$bit大小。
MAX_ORDER为11，即最多分配$2^{10} = 1024$个页面。
struct free_area {
struct list_head free_list[MIGRATE_TYPES];
unsigned long nr_free;
}free_area 中的空闲分组按照 MIGRATE_TYPES 进行了分组，每种类型都保存在一个双向链表中，这里我们将关注点放在Buddy System算法的实现上，不展开讨论 MIGRATE_TYPES.
分配流程
内存不够时，从更大order的链表中取一块下来，并切分到合适的大小，每次切分时按一半来切，另一半放到对应下标的位置进行管理。即切分后不用的内存块会依旧切分为2的整数倍的内存块，加入到对应order的链表中进行管理。
此外，人们发现系统对于 order=0 的内存分配请求是出现频次最高的，为了提升性能，系统就为每个CPU 建立了一个“缓存池”，避免了互斥的开销。
函数的逻辑根据 order 的大小分为两部分：
- 当order = 0, 即申请的内存页数等于1时，系统会从每个CPU的缓存页面中分配内存，如果没有，从buddy system分配。
- 当order > 0, 即申请的内存页数大于1时，系统会从 zone 中分配内存，如果没有，从buddy system分配。
当order = 0, 即申请的内存页数等于1时，系统会从每个CPU的缓存页面中分配内存。“缓存池”，也就是zone 中的字段 struct per_cpu_pageset __percpu *pageset;, 内核将其称为 pcplist, 即 per cpu pages list, 从 pcplist 分配内存的函数是 rmqueue_pcplist:
/* file: mm/page_alloc.c */
static struct page *rmqueue_pcplist(struct zone *preferred_zone,
struct zone *zone, gfp_t gfp_flags,
int migratetype, unsigned int alloc_flags)
{
struct per_cpu_pages *pcp;
struct list_head *list;
struct page *page;
unsigned long flags;
local_irq_save(flags);
/* 获取到当前CPU 的 pageset */
pcp = &this_cpu_ptr(zone->pageset)->pcp;
/* 拿到 pageset 中对应类型的内存列表 */
list = &pcp->lists[migratetype];
page = __rmqueue_pcplist(zone, migratetype, alloc_flags, pcp, list);
if (page) {
__count_zid_vm_events(PGALLOC, page_zonenum(page), 1);
zone_statistics(preferred_zone, zone);
}
local_irq_restore(flags);
return page;
}
static struct page *__rmqueue_pcplist(struct zone *zone, int migratetype,
unsigned int alloc_flags,
struct per_cpu_pages *pcp,
struct list_head *list)
{
struct page *page;
do {
/* 如果目标列表为空，则通过 Buddy System 为该列表补充内存，然后再进行分配 */
if (list_empty(list)) {
pcp->count +=
rmqueue_bulk(zone, 0, READ_ONCE(pcp->batch),
list, migratetype, alloc_flags);
if (unlikely(list_empty(list)))
return NULL;
}
/* 将对应内存列表的第一个内存页作为结果返回 */
page = list_first_entry(list, struct page, lru);
list_del(&page->lru);
pcp->count--;
} while (check_new_pcp(page));
return page;
}如果 order>0, 则通过函数 __rmqueue_smallest 从 zone 中分配内存，Buddy System 的算法实现也包含在该函数中：
/* file: mm/page_alloc.c */
static __always_inline struct page *
__rmqueue_smallest(struct zone *zone, unsigned int order, int migratetype)
{
unsigned int current_order;
struct free_area *area;
struct page *page;
/* Find a page of the appropriate size in the preferred list */
for (current_order = order; current_order < MAX_ORDER;
++current_order) {
area = &(zone->free_area[current_order]);
/* include/linux/mmzone.h: 作用是从 area->free_list[migratetype] 列表中拿到第一个元素，也就是一个连续 2^order 个物理页面 */
page = get_page_from_free_area(area, migratetype);
/* 如果没有对应大小的free list, 则尝试下一个 order 的列表 */
if (!page)
continue;
del_page_from_free_list(page, zone, current_order);
/* 如果 order ！= current_order, 则需要按照Buddy Algorithm将更大的连续内存劈开成更小的Buddy并插入到对应的 free area 列表中，该逻辑在 expand 函数中完成 */
expand(zone, page, order, current_order, migratetype);
set_pcppage_migratetype(page, migratetype);
return page;
}
return NULL;
}函数通过 for 循环遍历 zone->free_area, 找到能够满足请求的最小的Buddy并从中分配内存，如果实际的Buddy 列表大小大于请求的 order, 则通过 expand 对其进行拆分并将未分配的内存存入对应 order 的Buddy列表中，整个算法思路与前文讨论的一样。
回收流程
回收时，如果对应大小的另一块的内存是空闲的，则会进行合并，这个过程是循环进行的，直到不能合并为止。
要找到另一个块，只需要将内存块的地址与内存块的大小做异或操作即可。找到另一块，判断是否空闲，即判断另一块的位图是否为0，为0则循环向上合并，重复这个合并过程。
如果只有Buddy分配器的话，可能导致大量内存块的浪费，比如申请65KB的内存，分配64KB是不够的，只能分配128KB，但只用到65KB，就会造成63KB的浪费，导致了内部碎片。Slab就是解决这类问题的。
Slab分配器
Slab是基于Buddy的分配器，也就是首先向Buddy分配对应的大内存，对这块内存进行管理，从而避免内部碎片。
具体的，Slab向Buddy申请特地大小的内存，这块内存的大小要求能被结构体大小整除，即正好能放下完整的对象，不会存在内部碎片。
Slab策略看起来像池的思想，但由于对象类型很多，不可能每个都分配一个池，Slab可以看成一个通用的拟内存池机制。
一个Slab包含一个或多个连续的物理页面，然后将这些页面均分成固定的大小的各等份，每一等份就是一个对象，各对象通过链表串起来。
Slub分配略复杂，更详细的介绍在Linux分类下的Slub文章中。
看起来Slab只能分配固定大小的的内存，实际上，Linux的Slab实现了kmalloc和vmalloc，可以提供不同大小的可分配内存。
kmalloc、vmalloc
kmalloc、vmalloc对于常用的大小，创建了对应大小的的高速缓存组，部分如下。分配时找到第一个大于等于请求值的那个缓存组分配即可。
kmalloc分配的内存是物理连续的，而vmalloc是不一定是物理连续的。当然它们都是逻辑连续的。
vmalloc通过分配非连续的物理内存块，再修正页表，实现逻辑连续。由于需要建立页表项，同时一个一个地进行映射，导致分配慢、TLB抖动，都会影响效率。因此，内核在不得已才使用，如分配大块内存的情况下，比如加载模块。
kmalloc、vmalloc对于常用的大小，创建了对应大小的的高速缓存组，部分如下。分配时找到第一个大于等于请求值的那个缓存组分配即可。
root:/ # cat /proc/slabinfo | grep "kmalloc"
kmalloc-8192 644 663 8704 3 8 : tunables 0 0 0 : slabdata 221 221 0
kmalloc-4096 2250 2254 4608 7 8 : tunables 0 0 0 : slabdata 322 322 0
kmalloc-2048 6767 6780 2560 12 8 : tunables 0 0 0 : slabdata 565 565 0
kmalloc-1024 2374 2436 1536 21 8 : tunables 0 0 0 : slabdata 116 116 0
kmalloc-512 7034 7296 1024 32 8 : tunables 0 0 0 : slabdata 228 228 0
kmalloc-256 17285 17640 768 21 4 : tunables 0 0 0 : slabdata 840 840 0
kmalloc-128 301624 303775 640 25 4 : tunables 0 0 0 : slabdata 12151 12151 0回收策略
内核检查页面回收分为周期性检查和内存不足时的阻塞检查。
周期性检查由守护进程kswapd完成，定时检查内存使用情况，在少于特定阈值就会发起回收。主要有3个阈值
- pages_min： zone 的预留页面数量，如果小于该阈值，则压力比较大。
- pages_low：控制页面回收的最小阈值，小于该阈值则进行页面回收。
- pages_high：控制进行页面回收的最大阈值。
如果操作系统进行内存回收之后，仍然无法回收到足够多的页面，则启动OOM Killer，挑选一个最合适的进程并kill，释放其内存。
分配和释放API
Buddy
struct page* alloc_pages(gfp_t gft_mask, unsigned int order); // 分配2^order个**连续的物理页**，返回指向首地址，失败则为NULL。
void * page_address(struct page* page); //用该函数转化为对应的逻辑地址。
//其他封装函数
struct page* alloc_page(gfp_mask); //
struct page* alloc_pages(gfp_mask, order);
unsigned long __get_free_page(gfp_t gfp_mask);
unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order); // 作用与alloc_pages()相同，不过只返回第一个页的逻辑地址。
unsigned long get_zeroed_page(unsigned int gfp_mask); // 同_get_free_page(gfp_t gfp_mask), 但初始化为0.
void __free_pages(struct page* page, unsigned int order);
void free_pages(unsigned long addr, unsigned int order);
void free_page(unsigned long addr)分配参数
分配内存时还需要很多标记类参数，例如指定目标 zone （是从 DMA 请求内存还是 NORMAL)、分配到的内存是否要全部置零、如果内存不足，是否可以触发内存回收机制等等，这些标记都定义在 include/linux/gfp.h 中，例如：
/* file: include/linux/gfp.h */
#define ___GFP_DMA 0x01u
#define ___GFP_HIGHMEM 0x02u
#define ___GFP_DMA32 0x04u
#define ___GFP_MOVABLE 0x08u
#define ___GFP_RECLAIMABLE 0x10u
#define ___GFP_HIGH 0x20u
#define ___GFP_IO 0x40u
#define ___GFP_FS 0x80u
#define ___GFP_ZERO 0x100u
#define ___GFP_ATOMIC 0x200u
/* 通过位运算将不同的标记组合起来 */
#define GFP_ATOMIC (__GFP_HIGH|__GFP_ATOMIC|__GFP_KSWAPD_RECLAIM)
#define GFP_KERNEL (__GFP_RECLAIM | __GFP_IO | __GFP_FS)
#define GFP_KERNEL_ACCOUNT (GFP_KERNEL | __GFP_ACCOUNT)
#define GFP_NOWAIT (__GFP_KSWAPD_RECLAIM)源文件中对每个标记位的作用都有详细的说明，这里不再一一讨论。特别指出的是，GFP是Get Free Page的简称，这些标记叫着GFP Flags, 他们控制着Buddy System分配内存时的行为。
Slab、kmalloc和vmalloc
分配至少为size的内存块。
struct kmem_cache *kmem_cache_create(const char *name, //kmem_cache的名称
size_t size, //slab管理对象的大小
size_t align, //slab分配器分配内存的对齐字节数(以align字节对齐)
unsigned long flags, //分配内存掩码，实际会调用到buddy处执行。
void (*ctor)(void *)); //分配对象的构造回调函数
void kmem_cache_destroy(struct kmem_cache *); //销毁该cache
void *kmem_cache_alloc(struct kmem_cache *cachep, int flags); //从该cache分配一块对象
void kmem_cache_free(struct kmem_cache *cachep, void *objp); //从该cache回收指定对象
//kmalloc和vmalloc
void * kmalloc(size_t size, gfp_t flags);
void * vmalloc(unsigned long size);
void kfree(const void* ptr);
void vfree(const void* addr);