概述
内存管理的实现涵盖了许多领域：
- 内存中的物理内存页管理
- 分配大块内存的伙伴系统
- 分配较小内存块的slab、slub和slob分配器
- 分配非连续内存块的vmalloc机制
- 进程的地址空间
在IA-32系统上，可以直接管理的物理内存数量不超过896M。超过该值的内存只能通过高端内存寻址。
在64位系统上，由于可用的地址空间非常巨大，因此不需要高端内存模式。
（N）UMA模型中的内存组织
有两种类型的计算机，分别以不同的方法管理物理内存：
- UMA计算机（uniform memory access，一致内存访问）将可用内存以连续的方式组织起来。SMP(对称多处理)系统中每个处理器访问各个内存区都是同样快。
- NUMA计算机(non-uniform memory access)总是多处理计算机。系统的各个CPU都有本地内存，可支持特别快速的访问。各个处理器之间通过总线连接起来，以支持对其他CPU的本地内存的访问，当然比访问本地内存慢一些。
在UMA系统上，只使用一个NUMA结点来管理整个系统内存。
首先内存划分为结点，各个结点又划分为内存域
pg_data_t是用来表示结点的基本元素，定义如下：
<mmzone.h>
typedef struct pglist_data {
struct zone node_zones[MAX_NR_ZONES];//结点中各内存域的数据结构
struct zonelist node_zonelists[MAX_ZONELISTS];//指定了备用结点及其内存域的列表，以便在当前结点没有内存时，在备用结点中分配
int nr_zones;//结点中，不同内存域的数目
struct page *node_mem_map;//指向page数组，用于描述结点的所有物理内存页struct
bootmem_data*bdata;//在系统启动期间,内存管理子系统初始化之前,内核也需要使用内存(另外,还必须保留部分内存用于初始化内存管理子系统)。为解决这个问题,内核使用了3.4.3节讲解的自举内存分配器(boot memory allocator)。 bdata 指向自举内存分配器数据结构的实例
unsigned long node_start_pfn;//NUMA结点第一个页帧的逻辑编号。系统中所有结点的页帧是依次编号的,每个页帧的号码都是全局唯一的(不只是结点内唯一)。
unsigned long node_present_pages; /* 物理内存页的总数 */
unsigned long node_spanned_pages; /* 物理内存页的总长度,包含洞在内 */
int node_id;//全局结点ID
struct pglist_data *pgdat_next;//连接到下一个内存结点
wait_queue_head_t kswapd_wait;//交换守护进程(swap daemon)的等待队列
struct task_struct *kswapd;//交换守护进程的 task_struct
int kswapd_max_order;
} pg_data_t;内核使用zone结构来描述内存域，其定义如下：
<mmzone.h>
struct zone{
unsigned long free_pages;
/*通常由页分配器访问的字段 */
unsigned long pages_min, pages_low, pages_high;//页换出时使用的“水印”，由init_per_zone_pages_min函数计算
unsigned long lowmem_reserve[MAX_NR_ZONES];//数组分别为各种内存域指定了若干页,用于一些无论如何都不能失败的关键性内存分配
struct per_cpu_pageset pageset[NR_CPUS]; //实现每个CPU的热/冷页帧列表
/*
* 不同长度的空闲区域
*/
spinlock_t lock;
struct free_area free_area[MAX_ORDER];//用于实现伙伴系统。每个数组元素都表示某种固定长度的一些连续内存区
ZONE_PADDING(_pad1_)
/* 通常由页面收回扫描程序访问的字段 */
spinlock_t lru_lock;
struct list_head active_list;
struct list_head inactive_list;
unsigned long nr_scan_active;//指定在回收内存时需要扫描的活动和不活动页的数目。
unsigned long nr_scan_inactive;
unsigned long pages_scanned; /* 上一次回收以来扫描过的页 */
unsigned long flags; /* 内存域标志,见下文 */
/* 内存域统计量 */
atomic_long_t vm_stat[NR_VM_ZONE_STAT_ITEMS];
int prev_priority;
ZONE_PADDING(_pad2_)
/* 很少使用或大多数情况下只读的字段 */
wait_queue_head_t * wait_table;
unsigned long wait_table_hash_nr_entries;
unsigned long wait_table_bits;
/* 支持不连续内存模型的字段。 */
struct pglist_data *zone_pgdat;
unsigned long zone_start_pfn;//是内存域第一个页帧的索引
unsigned long spanned_pages; /* 总长度,包含空洞 */
unsigned long present_pages; /* 内存数量(除去空洞) */
/*
* 很少使用的字段:
*/
char *name;
};首先确定为关键性分配保留的内存空间的最小值。一个不变的约束是，不能少于128K，也不能多于64M。用户可以通过/proc/sys/vm/min_free_kbytes来读取与修改该值。
lowmem_reserve 的计算由 setup_per_zone_lowmem_reserve 完成。内核迭代系统的所有结点,对每个结点的各个内存域分别计算预留内存最小值,具体的算法是将内存域中页帧的总数除以sysctl_lowmem_reserve_ratio[zone]。除数的默认设置对低端内存域是256,对高端内存域是32。
pageset是一个数组，其容量与系统能容纳的CPU数目的最大值相同。其数据结构如下：
<mmzone.h>
struct per_cpu_pageset {
struct per_cpu_pages pcp[2]; /* 索引0对应热页,索引1对应冷页 */
} ____cacheline_aligned_in_smp;
<mmzone.h>
struct per_cpu_pages {
int count;//列表中页数
int high;//页数上限水印,在需要的情况下清空列表
int batch;//添加/删除多页块的时候,块的大小
struct list_head list;//页的链表
};页:
<mm_types.h>
struct page {
unsigned long flags;//原子标志，有些情况下会异步更新
atomic_t _count;//原子计数
union {
atomic_t _mapcount;//内存管理子系统中，映射的页表项计数，用于表示该页是否已经映射，还用于限制逆向搜索
unsigned int inuse;//用于SLUB分配器：分配对象的数目
};
union {
struct {
unsigned long private; /* 由映射私有,不透明数据:
* 如果设置了PagePrivate,通常用于buffer_heads;
* 如果设置了PageSwapCache,则用于swp_entry_t;
* 如果设置了PG_buddy,则用于表示伙伴系统中的阶*/
struct address_space *mapping;/* (指向页帧所在的地址空间)如果最低位为0,则指向inode
* address_space,或为NULL。
* 如果页映射为匿名内存,最低位置位,
* 而且该指针指向anon_vma对象:
* 参见下文的PAGE_MAPPING_ANON
*/
};
struct kmem_cache *slab; /* 用于SLUB分配器:指向slab的指针 */
struct page *first_page; /* 用于复合页的尾页,指向首页 */
};
union{
pgoff_t index; /* 在映射内的偏移量 */
void *freelist; /* SLUB: freelist req. slab lock */
};
struct list_head lru; // 换出页列表,例如由zone->lru_lock保护的active_list!
#if defined(WANT_PAGE_VIRTUAL)
void *virtual;//内核虚拟地址(如果没有映射则为NULL,即高端内存)
#endif /* WANT_PAGE_VIRTUAL */
...
};
页标志（struct page->flags）：
- PG_locked:指定页是否锁定
- PG_error:如果在涉及该页的I/O操作期间发生错误，则设置
- PG_referenced和PG_active控制系统使用该页的活跃程度
- PG_update:表示页的数据已经从块设备读取，其间没有出错
- PG_dirty:脏页
- PG_lru:有助于实现页面回收和切换。
- PG_highmem:表示页在高端内存中
- PG_private:如果page结构的private成员非空，则必须设置
- PG_writeback:如果页的内容处于向块设备回写的过程中，则需要设置该位
- PG_slab:表示页是slab分配器的一部分
- PG_swapcache:表明页处于交换缓存，private字段包含一个类型为swap_entry_t的项
- PG_reclaim:在内核决定回收某个特定页的时候设置
- PG_buddy:如果页空闲且包含在伙伴系统列表中，则设置该项
- PG_compound:表示页属于一个更大的复合页
内核定义了一些标准宏，用于检查页是否设置了某个特定的比特位，或者操作了某个比特位：
- PageXXX(page) 会检查页是否设置了 PG_XXX 位。例如, PageDirty 检查 PG_dirty 位,而 Page-Active 检查 PG_active 位,等等。
- SetPageXXX 在某个比特位没有设置的情况下,设置该比特位,并返回原值。
- ClearPageXXX 无条件地清除某个特定的比特位
- TestClearPageXXX 清除某个设置的比特位,并返回原值。
页表
内核内存管理总是假定使用四级页表，而不管底层处理器是否如此。
根据四级页表结构的需要，虚拟内存地址分为5部分（4个表项用于选择页，1个索引表示页内位置）
n比特位长的地址可以寻址的地址区域长度为2^n字节：
#define PAGE_SIZE (1UL<<PAGE_SHIFT)
#define PUD_SIZE (1UL<<PUD_SHIFT)//一个PUD中，一项内寻址的内存大小
#define PMD_SIZE (1UL<<PMD_SHIFT)
#define PGDIR_SIZE (1UL<<PGDIR_SHIFT)PTRS_PER_XXX指定了给定目录项，能够代表多少个指针
#define PGDIR_SHIFT 39
#define PTRS_PER_PGD 512
#define PUD_SHIFT 30
#define PTRS_PER_PUD 512
#define PMD_SHIFT 21
#define PTRS_PER_PMD 512
#define PTRS_PER_PTE 512内核也提供了方法用于从给定地址提取各个分量
#define PAGE_MASK (~(PAGE_SIZE-1))
#define PUD_MASK (~(PUD_SIZE - 1))
#define PMD_MASK (~(PMD_SIZE-1))
#define PGDIR_MASK (~(PGDIR_SIZE-1))内核提供了4个数据结构来表示页表项的结构
- pgd_t用于全局页目录项
- pud_t用于上层页目录项
- pmd_t用于页中间目录项
- pte_t用于直接页表项
最后一级页表中的项不仅包含了指向页的内存位置的指针，还在多于的比特位中包含了与页有关的附加信息。
- _PAGE_PRESENT 表示页在内存中
- PAGE_ACCESSED:CPU每次访问该页的时候（读或写），都会设置该位
- _PAGE_DIRTY:表示页是脏的
- _PAGE_FILE:用于不同的上下文，即页不在内存中的时候
- _PAGE_USER: 允许用户空间代码访问该页 ，否则只有内核代码可以访问
- _PAGE_WRITE、_PAGE_READ、_PAGE_EXECUTE:用于指定普通进程能否写、读、执行该页
- _PAGE_BIT_NX:IA-32和AMD64提供，用于将页标记为不可执行
初始化内存管理
因为内核在内存管理完全初始化之前就需要使用内存，在系统启动过程期间，使用了一个额外的简化形式的内存管理模块，然后丢弃掉。
<mmzone.h>
#define NODE_DATA(nid) (&contig_page_data)build_all_zonelist->__build_all_zonelist->build_zonelists:该函数的任务是，在当前结点和系统中的其他结点的内存区域之间建立一种等级次序,接下来按照这种次序分配内存。eg：如果内核想要在高端内存域中分配内存，如果失败，则在普通内存域，如果失败，则在DMA内存域中，如果还是失败，则在备选结点中，进行分配。
内核还针对当前内存结点的备选结点，定义了一个等级次序。这有助于在当前结点所有内存域的内存耗尽时，确定一个备选结点。内核使用pg_data_t中的zonelist数组，来表示所描述的层次结构。(备用列表)
<mmzone.h>
typedef struct pglist_data {
...
struct zonelist node_zonelists[MAX_ZONELISTS];
...
} pg_data_t;
#define MAX_ZONES_PER_ZONELIST (MAX_NUMNODES * MAX_NR_ZONES)
struct zonelist {
...
struct zone *zones[MAX_ZONES_PER_ZONELIST + 1]; // NULL分隔
};建立备用层次结构的任务委托给build_zonelists,该函数为每个NUMA结点都创建了相应的数据结构。
对总数N个结点中的结点m来说，内核生成备用列表，选择备用结点的顺序总是:m、m+1、m+2、...、N-1、0、1、2、...、m-1
内核在内存中的布局
内存中的前4KiB是第一个页帧，通常用于BIOS使用，接下来的640KiB是可用的，但也不用于内核加载（太小）。640KiB~~1MiB用于映射各种ROM。1MiB之后，用于内核加载。
管理员可以通过 cat /proc/iomem 查看内存布局
初始化步骤:
setup_arch->machine_specific_memory_setup、parse_early_param、setup_memory、paging_init、zone_sizes_init
首先调用machine_specific_memory_setup创建一个列表，包括系统占据的内存区和空闲内存区
parse_early_param:分析命令行
setup_memory:确定可用物理内存页的数目，初始化bootmem分配器，接下来分配各种内存区，例如，ramfs
paging_init:初始化内核页表并启用内存分页
zone_sizes_init:初始化系统中所有结点的pgdat_t实列。
分页机制的初始化
IA-32系统上第4G内存划分情况
- __PAGE_OFFSET（0xC0000000）~high_memory(将系统中的所有物理内存页映射到内核的虚拟地址空间中)
- high_memory~VMALLOC_START(8M的间隔)
- VMALLOC_START~VMALLOC_END（虚拟内存中连续，但物理内存中不连续的内存区）
- VMALLOC_END~PKMAP_BASE(间隔)
- KMAP_BASE~FIXADDR_START(持久映射：将高端内存域中的非持久页映射到内核中)
- FIXADDR_START~4GIB（固定映射：与物理地址空间中的固定页关联的虚拟地址空间项，但具体关联的页帧可以*选择）
在IA-32系统中，内核虚拟地址空间只有1GIB，如果物理内存超过896MiB，则内核无法直接映射全部物理内存页，因此内核必须保留最后的128MiB用于其他用途。
固定映射的优点在于，在编译时，对此类地址的处理类似于常数（用枚举类型来表示具体的地址），内核一启动，即为其分配了物理地址。
对每个固定映射地址都会创建一个常数，加入到fixed_addresses枚举列表中。
fix_to_virt:用于计算固定映射常数的虚拟地址（编译阶段即可计算出来对应的虚拟地址）
include/asm-x86/fixmap_32.h
#define __fix_to_virt(x) (FIXADDR_TOP -((x) << PAGE_SHIFT))固定映射地址与物理内存页之间的关联是由set_fixmap与set_fixmap_nocache建立的。
按3：1之外的比例划分地址空间，在特定应用场景下是有意义的，比如主要在内核中运行代码的计算机，如网络路由器。
在IA-32系统上的启动过程中，会调用paging_init按如上所述的方式划分虚拟地址空间
paging_init->pagetable_init->kernel_physical_mapping_init：将物理内存映射到虚拟地址空间中从PAGE_OFFSET开始的位置。并建立固定内存映射项和持久内核映射项对应的内存区。
冷热缓存的初始化
zone_pcp_init负责初始化冷热缓存。该函数由free_area_init_nodes调用。
zone_pcp_init->zone_batchsize:算出批量大小（batch）（大约相当于内存域中页数的0.25%）(对热页来说,下限为0,上限为 6batch ,缓存中页的平均数量大约是 4batch ,因为内核不会让缓存水平降到太低。 batch * 4 相当于内存域中页数的千分之一(这也是 zone_batchsize 试图将批量大小优化到总页数0.25‰的原因)。IA-32处理器上L2缓存的数量在0.25 MiB~2 MiB之间,因此在冷热缓存中保持更多的内存是无意义的。根据经验,缓存大小是主内存的千分之一。考虑到当前系统每个CPU配备的物理内存大约在1GiB~2GiB,该规则是有意义的。这样,计算出的批量大小使得冷热缓存中的页有可能放置到CPU的L2缓存中。)
zone_pcp_init->setup_pageset:填充每个per_cpu_pageset实例。
在zone_pcp_init结束时，会输出各个内存域的页数以及计算出的批量大小(batch)
可以通过以下方式查看
dmesg | grep LIFO注册活动内存区
大体过程：添加活动内存区(调用add_active_range)（就是不包含空洞的内存区）--》内核一般性框架--》内存域数据结构的初始化.
zone_sizes_init函数以页帧为单位，存储了不同内存区的边界。
AMD64地址空间设置
64位地址空间的跨度太大，当前没有什么应用程序需要这个。因此当前只是设置了一个比较小的物理地址空间，地址宽度为48位。但在寻址虚拟地址空间时，仍然使用64位。这引出了一个问题：由于物理地址实际上只有48位宽，虚拟地址空间的某些部分无法寻址。
显然，处理器必须隐藏对未实现地址空间的访问。一种可能的想法是，禁止使用超出物理地址空间的虚拟地址空间。但硬件设计师选择了不同的方法，其解决方法基于所谓的符号扩展方法。
虚拟地址空间的低47位（[0,46]）,可以任意设置，比特位[47,63]总是相同的，或全为0,或全为1。因此将地址空间划分为三个部分：下半部，上半部，二者之间的禁用区。上下两部分共同构造了一个48位的地址空间。
启动过程期间的内存初始化
bootmem用于在启动期间分配内存。内核开发者实现一个最先适配分配器用于在启动阶段管理内存，这是可能想到的最简单方式。其核心是用位图管理物理内存。
在IA-32中，是由setup_memory初始化bootmem分配器.
释放初始化数据
由__init标记的函数或数据（其实就是将函数或数据放置在ELF文件中的特殊section中），表示只在内核初始化阶段需要，在初始化阶段完成后可以释放，通过free_initmem函数释放。
可以通过下面的命令查看该信息
dmesg | grep Freeing物理内存的管理
伙伴系统的结构
struct zone{
...
struct free_area free_area[MAX_ORDER];
...
};
struct free_area{
struct list_head free_list[MIGRATE_TYPES];//大小相同的连续内存区
unsigned long nr_free;//当前按内存区中，空闲页块的数目
};内存区中，第一页的链表元素，可用于将内存区维持在链表中。
基于伙伴系统的内存管理专注于某个结点的某个内存域。但所有内存域和结点的伙伴系统，都通过备用分配列表连接起来。
有关伙伴系统当前状态的信息可以在/proc/buddyinfo中查看。
碎片避免
内核提供的方法是反碎片，即试图从最初开始尽可能防止碎片。将具有相同可移动性的页分组的思想。
内核定义了以下宏来表示不同的迁移类型：
<mmzone.h>
#define MIGRATE_UNMOVABLE 0 //不可移动的
#define MIGRATE_RECLAIMABLE 1 //可回收的
#define MIGRATE_MOVABLE 2 //可移动
#define MIGRATE_RESERVE 3 //如果向具有特定从可移动性的列表请求分配内存失败，则从其分配
#define MIGRATE_ISOLATE 4 /* 不能从这里分配 ,用于跨越NUMA结点移动物理内存页*/
#define MIGRATE_TYPES 5 //表示迁移类型的数目对伙伴系统的主要调整，是将空闲列表(free_list)分解成MIGRATE_TYPE个列表.
如果内核无法满足给定迁移类型的分配请求时，会使用备用列表，指定了在当前列表无法满足时，接下来应该使用那一种迁移类型:
mm/page_alloc.c
/*
* 该数组描述了指定迁移类型的空闲列表耗尽时,其他空闲列表在备用列表中的次序。
*/
static int fallbacks[MIGRATE_TYPES][MIGRATE_TYPES-1] = {
[MIGRATE_UNMOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE, MIGRATE_RESERVE },
[MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE, MIGRATE_MOVABLE, MIGRATE_RESERVE },
[MIGRATE_MOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },
[MIGRATE_RESERVE] = { MIGRATE_RESERVE, MIGRATE_RESERVE, MIGRATE_RESERVE },
/* 从来不用 */
};每个迁移链表都应该有适当数量的内存（由pageblock_order和pageblock_nr_pages指定）。如果各迁移类型的链表中没有一块较大的连续内存，那么页面迁移不会提供任何好处，因此在可用内存较少时，会关闭该特性。
在zone结构中有一个pageblock_flags字段，可以用于跟踪包含pageblock_nr_pages个页的内存区的属性。
set_pageblock_migratetype负责设置以page为首的一个内存区的迁移类型。相应的还有get_pageblock_migratetype。
在各个迁移链表之间，当前的页面分配状态可以从/proc/pagetypeinfo获得。
初始化基于可移动性的分组
在内存子系统初始化期间，memmap_init_zone负责处理内存域的page实例。并将所有页标记为可移动的。
在分配内存时,如果必须“盗取”不同于预定迁移类型的内存区,内核在策略上倾向于“盗取”更大的内存区。由于所有页最初都是可移动的,那么在内核分配不可移动的内存区时,则必须“盗取”。
实际上,在启动期间分配可移动内存区的情况较少,那么分配器有很高的几率分配长度最大的内存区,并将其从可移动列表转换到不可移动列表。由于分配的内存区长度是最大的,因此不会向可移动内存中引入碎片。
虚拟可移动内存域
防止物理内存碎片化的另一种方法：虚拟内存域ZONE_MOVABLE(不会关联到任何硬件上有意义的内存范围).该方法必须由管理员显示激活。
基本思想很简单：可用的物理内存划分为两个内存域。一个用于可移动分配，另一个用于不可移动分配。
取决于内核配置和体系结构，ZONE_MOVABLE内存域可能位于高端或普通内存域。
初始化内存域和结点数据结构
体系结构相关的代码在启动期间建立以下信息：
- 系统中各个内存域的页帧边界，保存在max_zone_pfn数组中
- 各结点页帧的分配情况，保存在全局变量early_node_map中
然后根据以上信息通过free_area_init_nodes建立结点和内存域数据结构。
free_area_init_nodes主要用[low,high]形式描述各个内存域的页帧区间,并存储在全局变量arch_zone_lowest_possible_pfn与arch_zone_highest_possible_pfn数组中。然后调用free_area_init_node分别对各个结点建立数据结构。
对各个结点创建数据结构
free_area_init_node->calculate_node_totalpages:计算结点中页的总数
free_area_init_node->alloc_node_mem_map:初始化结点node_mem_map字段
free_area_init_node->free_area_init_core:初始化内存域数据结构
分配器API
伙伴系统将在内存中分配2^order页。内核中细粒度的分配只能借助于slab分配器(或者slub、slob分配器),后者基于伙伴系统。
- alloc_pages(mask, order) 分配2^order页并返回一个 struct page 的实例,表示分配的内存块的起始页。 alloc_page(mask) 是前者在 order = 0 情况下的简化形式,只分配一页。
- get_zeroed_page(mask)分配一页并返回一个page实例,页对应的内存填充0(所有其他函数,分配之后页的内容是未定义的)。
- __get_free_pages(mask, order) 和__get_free_page(mask)的工作方式与上述函数相同,
但返回分配内存块的虚拟地址,而不是 page 实例。 - get_dma_pages(gfp_mask, order) 用来获得适用于DMA的页。
有4个函数用于释放不再使用的页,与所述函数稍有不同。
- free_page(struct page ) 和 free_pages(struct page , order)
- __free_page(addr) 和 __free_pages(addr, order)
分配掩码
p173
内存分配宏
通过使用标志、内存域修饰符和各个分配函数，内核提供了一种非常灵活的内存分配体系。尽管如此，所有接口都可以追溯到一个简单的基本函数(alloc_pages_node)
alloc_page get_zerod_page __get_free_page __get_dma_pages
| | | |
| | ---------------------
| | get_free_pages
------------------------------------------
|
alloc_pages
|
alloc_pages_node内存释放函数也可以归为一个主要函数(__free_pages):
free_page
|
|
|
free_pages __free_page
---------------------------
|
|
|
__free_pages分配页
<include/linux/gfp.h>
static inline struct page *alloc_pages_node(int nid, gfp_t gfp_mask,
unsigned int order)
{
if (unlikely(order >= MAX_ORDER))//避免分配过大内存块
return NULL;
/* Unknown node is current node */
if (nid < 0)//如果指定的结点ID不存在，则选择当前CPU的结点ID
nid = numa_node_id();
return __alloc_pages(gfp_mask, order,
NODE_DATA(nid)->node_zonelists + gfp_zone(gfp_mask));//gfp_zone(gfp_mas)用于选择内存分配的内存域
}内核代码将__alloc_pages称之为“伙伴系统的心脏”。
//mm/page_alloc.c
static struct page *
get_page_from_freelist(gfp_t gfp_mask, unsigned int order,
struct zonelist *zonelist, int alloc_flags)
{
struct zone **z;
struct page *page = NULL;
int classzone_idx = zone_idx(zonelist->zones[0]);
struct zone *zone;
nodemask_t *allowednodes = NULL;/* zonelist_cache approximation */
int zlc_active = 0; /* set if using zonelist_cache */
int did_zlc_setup = 0; /* just call zlc_setup() one time */
enum zone_type highest_zoneidx = -1; /* Gets set for policy zonelists */
zonelist_scan:
/*
* Scan zonelist, looking for a zone with enough free.
* See also cpuset_zone_allowed() comment in kernel/cpuset.c.
*/
z = zonelist->zones;
do {//遍历zone备用列表
/*
* In NUMA, this could be a policy zonelist which contains
* zones that may not be allowed by the current gfp_mask.
* Check the zone is allowed by the current flags
*/
if (unlikely(alloc_should_filter_zonelist(zonelist))) {
if (highest_zoneidx == -1)
highest_zoneidx = gfp_zone(gfp_mask);
if (zone_idx(*z) > highest_zoneidx)
continue;
}
if (NUMA_BUILD && zlc_active &&
!zlc_zone_worth_trying(zonelist, z, allowednodes))
continue;
zone = *z;
if ((alloc_flags & ALLOC_CPUSET) &&
!cpuset_zone_allowed_softwall(zone, gfp_mask))//检查给定内存域是否属于该进程允许运行的CPU
goto try_next_zone;
if (!(alloc_flags & ALLOC_NO_WATERMARKS)) {//检查是否有足够的空闲页
unsigned long mark;
if (alloc_flags & ALLOC_WMARK_MIN)
mark = zone->pages_min;
else if (alloc_flags & ALLOC_WMARK_LOW)
mark = zone->pages_low;
else
mark = zone->pages_high;
if (!zone_watermark_ok(zone, order, mark,
classzone_idx, alloc_flags)) {
if (!zone_reclaim_mode ||
!zone_reclaim(zone, gfp_mask, order))
goto this_zone_full;
}
}
page = buffered_rmqueue(zonelist, zone, order, gfp_mask);
if (page)
break;
this_zone_full:
if (NUMA_BUILD)
zlc_mark_zone_full(zonelist, z);
try_next_zone:
if (NUMA_BUILD && !did_zlc_setup) {
/* we do zlc_setup after the first zone is tried */
allowednodes = zlc_setup(zonelist, alloc_flags);
zlc_active = 1;
did_zlc_setup = 1;
}
} while (*(++z) != NULL);
if (unlikely(NUMA_BUILD && page == NULL && zlc_active)) {
/* Disable zlc cache for second zonelist scan */
zlc_active = 0;
goto zonelist_scan;
}
return page;
}
//mm/page_alloc.c
//可参考:http://blog.chinaunix.net/uid-14528823-id-4146032.html
int zone_watermark_ok(struct zone *z, int order, unsigned long mark,
int classzone_idx, int can_try_harder, int gfp_high)
{
/* free_pages my go negative - that's OK */
long min = mark, free_pages = z->free_pages - (1 << order) + 1;
int o;
if (gfp_high)
min -= min / 2;
if (can_try_harder)
min -= min / 4;
if (free_pages <= min + z->lowmem_reserve[classzone_idx])
return 0;
for (o = 0; o < order; o++) {
/* At the next order, this order's pages become unavailable */
free_pages -= z->free_area[o].nr_free << o;
/* Require fewer higher order pages to be free */
min >>= 1;
if (free_pages <= min)
return 0;
}
return 1;
}如前所述，__alloc_pages是伙伴系统的主函数。我们已经处理了所有的准备工作并描述了所有可能的标志，现在我们把注意力转向相对复杂的部分：该函数的实现，这也是内核中比较冗长的部分之一。特别是可用内存太少或逐渐用完时，函数比较复杂。如果可用内存足够，则必要的工作会很快的完成。
在最简单的情况下，分配内存只涉及调用一次get_page_from_freelist.
<mm/page_alloc.c>
struct page * fastcall
__alloc_pages(gfp_t gfp_mask, unsigned int order,
struct zonelist *zonelist)
{
const gfp_t wait = gfp_mask & __GFP_WAIT;
struct zone **z;
struct page *page;
struct reclaim_state reclaim_state;
struct task_struct *p = current;
int do_retry;
int alloc_flags;
int did_some_progress;
might_sleep_if(wait);
if (should_fail_alloc_page(gfp_mask, order))
return NULL;
restart:
z = zonelist->zones; /* the list of zones suitable for gfp_mask */
if (unlikely(*z == NULL)) {
/*
* Happens if we have an empty zonelist as a result of
* GFP_THISNODE being used on a memoryless node
*/
return NULL;
}
page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, order,
zonelist, ALLOC_WMARK_LOW|ALLOC_CPUSET);//最简单的情况，直接一次就分配成功
if (page)
goto got_pg;
if (NUMA_BUILD && (gfp_mask & GFP_THISNODE) == GFP_THISNODE)
goto nopage;
for (z = zonelist->zones; *z; z++)//遍历备用列表中的所有内存域
wakeup_kswapd(*z, order);//唤醒kswapd守护进程，通过缩小内核缓存和页面回收，获得空闲内存
//下面对分配标志进行设置，修改为在当前情况下，更有可能分配成功的标志
alloc_flags = ALLOC_WMARK_MIN;
if ((unlikely(rt_task(p)) && !in_interrupt()) || !wait)
alloc_flags |= ALLOC_HARDER;
if (gfp_mask & __GFP_HIGH)
alloc_flags |= ALLOC_HIGH;
if (wait)
alloc_flags |= ALLOC_CPUSET;
//在一次调用get_page_from_freelist，试图获取所需页
page = get_page_from_freelist(gfp_mask, order, zonelist, alloc_flags);
if (page)
goto got_pg;
//如果再次失败
rebalance:
if (((p->flags & PF_MEMALLOC) || unlikely(test_thread_flag(TIF_MEMDIE)))
&& !in_interrupt()) {//PF_MEMALLOC：通常只有分配器自身需要更多内存时设置.TIF_MEMDIE:线程刚好被OOM killer机制选中时，设置.
if (!(gfp_mask & __GFP_NOMEMALLOC)) {//__GFP_NOMEMALLOC:禁止使用紧急分配表
nofail_alloc:
/* go through the zonelist yet again, ignoring mins */
page = get_page_from_freelist(gfp_mask, order,
zonelist, ALLOC_NO_WATERMARKS);//完全忽略水印，
if (page)
goto got_pg;
if (gfp_mask & __GFP_NOFAIL) {
congestion_wait(WRITE, HZ/50);
goto nofail_alloc;
}
}
goto nopage;//通过内核消息报告用户，并将NULL指针返回调用者
}
if (!wait)
goto nopage;
//查看是否需要重新调度，因为后面的操作比较耗时
cond_resched();
/* We now go into synchronous reclaim */
cpuset_memory_pressure_bump();
p->flags |= PF_MEMALLOC;
...............................
//try_to_free_pages被PF_MEMALLOC标志隔离开来的原因是
//try_to_free_pages自身也需要分配新的内存，该进程自身应该在
//内存管理方面拥有最高优先级
did_some_progress = try_to_free_pages(zonelist->zones, order, gfp_mask);//查找不需要的页将其换出
...............................
p->flags &= ~PF_MEMALLOC;
cond_resched();
if (order != 0)
drain_all_local_pages();
if (likely(did_some_progress)) {
page = get_page_from_freelist(gfp_mask, order,
zonelist, alloc_flags);//再次尝试分配
if (page)
goto got_pg;
} else if ((gfp_mask & __GFP_FS) && !(gfp_mask & __GFP_NORETRY)) {//如果内核可能执行影响VFS层的调用而又没有设置 GFP_NORETRY ,那么调用OOM killer
if (!try_set_zone_oom(zonelist)) {
schedule_timeout_uninterruptible(1);
goto restart;
}
/*
* Go through the zonelist yet one more time, keep
* very high watermark here, this is only to catch
* a parallel oom killing, we must fail if we're still
* under heavy pressure.
*/
page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, order,
zonelist, ALLOC_WMARK_HIGH|ALLOC_CPUSET);
if (page) {
clear_zonelist_oom(zonelist);
goto got_pg;
}
/* The OOM killer will not help higher order allocs so fail */
if (order > PAGE_ALLOC_COSTLY_ORDER) {//杀死一个进程未必立即出现多于2^PAGE_ALLOC_COSTLY_ORDER页的连续内存区，因此如果要分配如此大的内存区，那么内核会绕怒所选进程，不执行杀死进程的任务，而是承认失败
clear_zonelist_oom(zonelist);
goto nopage;
}
out_of_memory(zonelist, gfp_mask, order);
clear_zonelist_oom(zonelist);
goto restart;
}
do_retry = 0;
if (!(gfp_mask & __GFP_NORETRY)) {
if ((order <= PAGE_ALLOC_COSTLY_ORDER) ||
(gfp_mask & __GFP_REPEAT))
do_retry = 1;
if (gfp_mask & __GFP_NOFAIL)
do_retry = 1;
}
if (do_retry) {
congestion_wait(WRITE, HZ/50);//等待块设备层队列释放,这样内核就有机会换出页
goto rebalance;
}
nopage:
if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit()) {
printk(KERN_WARNING "%s: page allocation failure."
" order:%d, mode:0x%x\n",
p->comm, order, gfp_mask);
dump_stack();
show_mem();
}
got_pg:
return page;综上分析:__alloc_pages在尝试内存分配失败的时候，会利用swap，oom等，获取更多的页
移除选择的页
如果内核找到适当的内存区,具有足够的空闲页可分配。则调用buffered_rmqueue
如果只分配一页，内核会进行优化，该页不是从伙伴系统直接取得，而是取自per-CPU的页缓存。
<mm/page_alloc.c>
static struct page *buffered_rmqueue(struct zonelist *zonelist,
struct zone *zone, int order, gfp_t gfp_flags)
{
unsigned long flags;
struct page *page;
int cold = !!(gfp_flags & __GFP_COLD);
int cpu;
int migratetype = allocflags_to_migratetype(gfp_flags);//确定迁移列表
again:
cpu = get_cpu();
if (likely(order == 0)) {//如果试图请求一页时，内核试图借助per-CPU缓存加速请求的处理，如果缓存为空，内核可借机填充缓存
struct per_cpu_pages *pcp;
pcp = &zone_pcp(zone, cpu)->pcp[cold];
local_irq_save(flags);
if (!pcp->count) {
pcp->count = rmqueue_bulk(zone, 0,
pcp->batch, &pcp->list, migratetype);
if (unlikely(!pcp->count))
goto failed;
}
/* Find a page of the appropriate migrate type */
list_for_each_entry(page, &pcp->list, lru)
if (page_private(page) == migratetype)//页的迁移类型存储在page的private字段
break;
/* Allocate more to the pcp list if necessary */
if (unlikely(&page->lru == &pcp->list)) {//如果上一步中，为找到符号迁移类型的页，则向缓存中添加一些符号当前迁移类型的页，并从中移除一页
pcp->count += rmqueue_bulk(zone, 0,
pcp->batch, &pcp->list, migratetype);
page = list_entry(pcp->list.next, struct page, lru);
}
list_del(&page->lru);
pcp->count--;
} else {//分配多页
spin_lock_irqsave(&zone->lock, flags);
page = __rmqueue(zone, order, migratetype);//该过程可能会失败：内存域中有足够多的空闲页满足分配请求，但页是不连续的
spin_unlock(&zone->lock);
if (!page)
goto failed;
}
__count_zone_vm_events(PGALLOC, zone, 1 << order);
zone_statistics(zonelist, zone);
local_irq_restore(flags);
put_cpu();
VM_BUG_ON(bad_range(zone, page));
if (prep_new_page(page, order, gfp_flags))//做准备工作:将page结构的各项属性，设置到正确状态。并根据需要，将页填0,并设置复合页
goto again;
return page;
failed:
local_irq_restore(flags);
put_cpu();
return NULL;
}内核使用了__rmqueue函数，充当进入伙伴系统的核心
static struct page *__rmqueue(struct zone *zone, unsigned int order,
int migratetype)
{
struct page *page;
page = __rmqueue_smallest(zone, order, migratetype);
if (unlikely(!page))//如果指定的迁移列表不能满足分配请求，则尝试其他迁移列表
page = __rmqueue_fallback(zone, order, migratetype);
return page;
}
static 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]);
if (list_empty(&area->free_list[migratetype]))
continue;
page = list_entry(area->free_list[migratetype].next,
struct page, lru);
list_del(&page->lru);
rmv_page_order(page);//删除PG_buddy位，将private字段设置为0
area->nr_free--;
__mod_zone_page_state(zone, NR_FREE_PAGES, - (1UL << order));
expand(zone, page, order, current_order, area, migratetype);//如果需要，则将页分裂
return page;
}
return NULL;
}
static inline void expand(struct zone *zone, struct page *page,
int low, int high, struct free_area *area,
int migratetype)
{
unsigned long size = 1 << high;
while (high > low) {
area--;
high--;
size >>= 1;
VM_BUG_ON(bad_range(zone, &page[size]));
list_add(&page[size].lru, &area->free_list[migratetype]);
area->nr_free++;
set_page_order(&page[size], high);//设置page的PG_buddy标志，并将private字段设置为当前分配阶
}
}如果在特定的迁移类型列表上没有连续内存可用，则接下来根据备用次序，尝试使用其他迁移类型的列表满足分配请求。该任务委托给__rmqueue_fallback。迁移类型的备用次序在fallbacks数组中定义。
static struct page *__rmqueue_fallback(struct zone *zone, int order,
int start_migratetype)
{
struct free_area * area;
int current_order;
struct page *page;
int migratetype, i;
/* Find the largest possible block of pages in the other list */
//为了避免碎片化，从大阶开始
for (current_order = MAX_ORDER-1; current_order >= order;
--current_order) {
for (i = 0; i < MIGRATE_TYPES - 1; i++) {
migratetype = fallbacks[start_migratetype][i];
/* MIGRATE_RESERVE handled later if necessary */
if (migratetype == MIGRATE_RESERVE)//用于紧急分配的内存
continue;
area = &(zone->free_area[current_order]);
if (list_empty(&area->free_list[migratetype]))
continue;
page = list_entry(area->free_list[migratetype].next,
struct page, lru);
area->nr_free--;
/*
* If breaking a large block of pages, move all free
* pages to the preferred allocation list. If falling
* back for a reclaimable kernel allocation, be more
* agressive about taking ownership of free pages
*/
//如果分解一个大内存块，则将所有空闲页移动到优先选用的分配列表
//如果内核在备用列表中分配可回收内存块，则会更为积极地取得空闲页的所有权
if (unlikely(current_order >= (pageblock_order >> 1)) ||
start_migratetype == MIGRATE_RECLAIMABLE) {
unsigned long pages;
pages = move_freepages_block(zone, page,
start_migratetype);
/* Claim the whole block if over half of it is free */
// 如果大内存块超过一半是空闲的，则主张对整个大内存块的所有权
if (pages >= (1 << (pageblock_order-1)))
set_pageblock_migratetype(page,
start_migratetype);//将修改整个大内存块的迁移类型
migratetype = start_migratetype;
}
/* Remove the page from the freelists */
list_del(&page->lru);
rmv_page_order(page);
__mod_zone_page_state(zone, NR_FREE_PAGES,
-(1UL << order));
if (current_order == pageblock_order)
set_pageblock_migratetype(page,
start_migratetype);
expand(zone, page, order, current_order, area, migratetype);//，如果此前已经改变了迁移类型，那么expand将使用新的迁移类型。否则，剩余部分将放置到原来的迁移列表上
return page;
}
}
/* Use MIGRATE_RESERVE rather than fail an allocation */
return __rmqueue_smallest(zone, order, MIGRATE_RESERVE);//还是不能满足的话，只有从MIGRATE_RESERVE中分配
}释放页
__free_pages是一个基础的函数，用于实现所有的涉及内存释放的函数。
__free_pages首先判断释放的是单页还是多页，如果是单页，则直接将其放入per-CPU缓存中，而不是放回伙伴系统中。如果超出per-CPU缓存的阀值，则会将batch数量的页，放回伙伴系统中。
如果是多个页，则__free_pages将工作委托给__free_pages_ok，最后到__free_one_page.与其名称不同，该函数不仅处理单页的释放，也处理复合页的释放。该函数是内存释放功能的基础，
注意:当page结构设置PG_buddy时，其private字段，为当前按order(但只在页块的第一页设置这两个字段)
<mm/page_alloc.c>
static inline struct page *
__page_find_buddy(struct page *page, unsigned long page_idx, unsigned int order)
{
unsigned long buddy_idx = page_idx ^ (1 << order);
return page + (buddy_idx -page_idx);
}
static inline unsigned long
__find_combined_index(unsigned long page_idx, unsigned int order)
{
return (page_idx & ~(1 << order));
}
static inline int page_is_buddy(struct page *page, struct page *buddy,
int order)
{
...
if (PageBuddy(buddy) && page_order(buddy) == order) {
return 1;
}
return 0;
}
mm/page_alloc.c
static inline void __free_one_page(struct page *page,
struct zone *zone, unsigned int order)
{
int migratetype = get_pageblock_migratetype(page);
...
while (order < MAX_ORDER-1) {
unsigned long combined_idx;
struct page *buddy;
buddy = __page_find_buddy(page, page_idx, order);
if (!page_is_buddy(page, buddy, order))
break; /* 将伙伴向上移动一级。 */
list_del(&buddy->lru);
zone->free_area[order].nr_free--;
rmv_page_order(buddy);
combined_idx = __find_combined_index(page_idx, order);
page = page + (combined_idx -page_idx);
page_idx = combined_idx;
order++;
}
... 内核中不连续页的分配
物理上连续的内存映射对内核来说是最好的，但并不能总成功的使用。在分配一块大内存时，可能内核竭尽全力搜索，也可能无法找到。
内核在其地址空间中分配了一段连续的地址空间，用于建立连续映射。
每个vmalloc分配的子区域都是自包含的，与其他vmalloc分配的子区域，存中一页的安全隔离。
vmalloc是一个接口函数，内核代码用它来分配在虚拟地址空间中连续但物理地址内存中不一定连续的内存。
<vmalloc.h>
void *vmalloc(unsigned long size);vmalloc中，优先使用ZONE_HIGHMEM内存域的页。
数据结构
内核在管理内核虚拟内存中的vmalloc区域时，内核必须跟踪那些子区域被使用，那些是空闲的,用链表将其管理起来。（内核在管理用户虚拟内存时，使用了一个名称上类似的结构struct vm_area_struct）。
struct vm_struct {
/* keep next,addr,size together to speedup lookups */
struct vm_struct *next;
void *addr;//内核虚拟地址空间中的地址
unsigned long size;//长度
unsigned long flags;/*
*VM_ALLOC指定由vmalloc产生的子区域。
*VM_MAP用于表示将现存pages集合映射到连续的虚拟地址空间中
*VM_IOREMAP表示将几乎随机的物理内存区域映射到vmalloc区域中
*/
struct page **pages;//page数组，表示映射到vmalloc区域的物理页
unsigned int nr_pages;//page的个数
unsigned long phys_addr;//仅当用ioremap映射了由物理地址描述的物理内存区域时才需要。
};vm_struct连接在全局vmlist链表中。
创建vm_struct
get_vm_area:根据子区域的长度信息，试图在虚拟的vmalloc空间中找到一个适当的位置。
mm/vmalloc.c
struct vm_struct *__get_vm_area_node(unsigned long size, unsigned long flags,
unsigned long start, unsigned long end, int node)
{
struct vm_struct **p, *tmp, *area;
...
size = PAGE_ALIGN(size);
....
/*
* 总是分配一个警戒页。
*/
size += PAGE_SIZE;
...
for (p = &vmlist; (tmp = *p) != NULL ;p = &tmp->next) {
if ((unsigned long)tmp->addr < addr) {
if((unsigned long)tmp->addr + tmp->size >= addr)
addr = ALIGN(tmp->size +
(unsigned long)tmp->addr, align);
continue;
}
if ((size + addr) < addr)
goto out;
if (size + addr <= (unsigned long)tmp->addr)//如果size+addr不大于当前检查区域的起始地址（保存在tmp->addr），那么内核就找到了一个合适的位置。
goto found;
addr = ALIGN(tmp->size + (unsigned long)tmp->addr, align);
if (addr > end -size)
goto out;
}
found:
area->next = *p;
*p = area;
area->flags = flags;
area->addr = (void *)addr;
area->size = size;
area->pages = NULL;
area->nr_pages = 0;
area->phys_addr = 0;
return area;
...
}remove_vm_area函数将一个现存的子区域从vmalloc地址空间中删除。
<vmalloc.h>
struct vm_struct *remove_vm_area(void *addr);分配内存区
vmalloc-->_vmalloc-->_vmalloc_node
static void *__vmalloc_node(unsigned long size, gfp_t gfp_mask, pgprot_t prot,
int node)
{
struct vm_struct *area;
size = PAGE_ALIGN(size);
if (!size || (size >> PAGE_SHIFT) > num_physpages)
return NULL;
area = get_vm_area_node(size, VM_ALLOC, node, gfp_mask);//寻找一个适当的vm_struct结构
if (!area)
return NULL;
return __vmalloc_area_node(area, gfp_mask, prot, node);//分配物理内存并映射
}
void *__vmalloc_area_node(struct vm_struct *area, gfp_t gfp_mask,
pgprot_t prot, int node)
{
...
for (i = 0; i < area->nr_pages; i++) {
if (node < 0)
area->pages[i] = alloc_page(gfp_mask);//逐页分配
else
area->pages[i] = alloc_pages_node(node, gfp_mask, 0);
if (unlikely(!area->pages[i])) {
/* Successfully allocated i pages, free them in __vunmap() */
area->nr_pages = i;
goto fail;
}
}
if (map_vm_area(area, prot, &pages))//创建映射
goto fail;
return area->addr;
...
}释放内存
vfree用于释放由vmalloc申请的内存。
vfree->__vunmap
static void __vunmap(void *addr, int deallocate_pages)
{
...
area = remove_vm_area(addr);//从vmlist链表中删除vm_struct结构,并删除相应的页表项
...
if (deallocate_pages) {
int i;
for (i = 0; i < area->nr_pages; i++) {
BUG_ON(!area->pages[i]);
__free_page(area->pages[i]);//将页释放回伙伴系统
}
if (area->flags & VM_VPAGES)
vfree(area->pages);
else
kfree(area->pages);
}
kfree(area);
return;
...
}内核映射
持久内核映射
kmap函数：将高端页帧长期映射到内核地址空间中。
kumap:接触映射
数据结构
内核在IA-32平台上在vmalloc区域之后分配了一个区域，从PKMA_BASE到FIXADDR_START。该区域用于持久映射。
pkmap_count（在mm/highmem.m定义）是一容量为LAST_PKMAP的整数数组，其中每个元素都对应于一个持久映射页。它实际上是被映射页的一个使用计数器，语义不太常见。该计数器计算了内核使用该页的次数加1。如果计数器值为2，则内核中只有一处使用该映射页。计数器值为5表示有4处使用。一般地说，计数器值为n代表内核中有n-1处使用该页。
和通常的使用计数器一样，0意味着相关的页没有使用。计数器值1有特殊语义。这表示该位置关联的页已经映射，但由于CPU的TLB没有更新而无法使用，此时访问该页，或者失败，或者会访问到一个不正确的地址。
内核利用下列数据结构，来建立物理内存页的page实例与其在虚似内存区中位置之间的关联：
mm/highmem.c
struct page_address_map {
struct page *page;
void *virtual;
struct list_head list;
}; 该结构保存在散列表中
临时内存映射
刚才描述的kmap函数不能用于中断处理程序，因为它可能进入睡眠状态.
因此内核提供了一个备选的映射函数，其执行是原子的，逻辑上称为kmap_atomic。
Slab 分配器
提供小内存不是slab分配器唯一的任务。由于结构上的特点，它也用作一个缓存，主要针对经常分配并释放的对象。
slab分配器的好处：降低伙伴系统的调用，防止缓存污染，
通过slab着色，slab分配器能够均匀地分布对象，以实现均匀的缓存利用。（着色这个术语是隐喻性的。它与颜色无关，只是表示slab中的对象需要移动的特定偏移量，以便使对象放置到不同的缓存行）
各个缓存管理的对象，会合并为较大的组，覆盖一个或多个连续页帧。这种组称为slab，每个缓存由几个这种slab组成。
备选分配器
-slob:小型机
-slub:大型机
- kmalloc、__kmalloc、kmalloc_node是一般的内存分配函数
- kmalloc_cache_alloc、kmalloc_cache_alloc_node提供特定内存的内核缓存
普通内核代码只需要包含slab.h，即可以使用内存分配的所有标准内核函数。
内核中的内存管理
从程序员的角度来看，建立和使用缓存的任务不是特别困难。必须首先用kmem_cache_create建立一个适当的缓存，接下来即可使用kmem_cache_alloc和kmem_cache_free分配和释放其中包含的对象。slab分配器负责完成与伙伴系统的交互，来分配所需的页。
所有活动缓存列表保存在/proc/slabinfo中
slab分配的原理
slab缓存由两个部分组成：保存管理性数据的缓存对象和保存被管理对象的各个slab。
系统中所有缓存都保存在一个双向链表中，这使得在内存不足的情况下，缩小缓存大小。
对象分配的体系就形成了一个三级的层次结构，分配成本和操作对CPU高速缓存和TLB的负面影响逐级升高。
- 仍然处于CPU高速缓存中的per-CPU对象。
- 现存slab中未使用的对象
- 刚使用伙伴系统分配的新slab中为使用的对象
slab精细结构
每个对象的长度并不反映其确切的大小。相反长度已经进行舍入，以满足某些对齐方式的要求。
管理结构起始于每个slab的起始处，保存了所有的管理数据。其后是一个数组，每个数组项对应于slab中的一个对象。只有在对象没有分配时，相应的数组项才有意义。在这种情况下，它指向了下一个空闲对象的索引。数组的最后一项总是一个结束标记，值为BUFCTL_END。
大多数情况下，slab内存区（减去头部管理空间）的长度是不能被对象长度整除的，因此，内核就有了一些多余的内存，可以用来以偏移量的形式给slab“着色”。
最后，内核需要一种方法，通过对象自身即可识别slab（以及对象驻留的缓存）。根据对象的物理内存地址，可以找到相关的页，因此可以在全局mem_map数组中找到对应的page实例。
我们已经知道，page结构包括一个链表元素，用于管理各种链表中的页。对于slab缓存中的页而言，该指针是不必要的，可用于其他用途。
- page->lru.next指向页驻留的缓存的管理结构
- page->lru.prev指向保存该页的slab的管理结构
<mm/slab.c>
void page_set_cache(struct page *page, struct kmem_cache *cache)
struct kmem_cache *page_get_cache(struct page *page)
void page_set_slab(struct page *page, struct slab *slab)
struct slab *page_get_slab(struct page *page) 此外内核对分配给slab分配器的每个物理内存页都设置标志PG_SLAB。
实现
数据结构
每个缓存由kmem_cache结构的一个实列表示
struct kmem_cache {
/* 1) per-cpu data, touched during every alloc/free */
//per-cpu数组，在每次分配/释放期间都会访问
struct array_cache *array[NR_CPUS];
/* 2) Cache tunables. Protected by cache_chain_mutex */
unsigned int batchcount;//指定了在per-CPU列表为空的情况下，从缓存的slab中获取对象的数目。它还表示在缓存增长时，分配的对象数目。
unsigned int limit;//limit指定了per-CPU列表中保存的对象的最大数目。如果超出该值，内核会将batchcount个对象返回到slab
unsigned int shared;
unsigned int buffer_size;//指定了缓存中管理的对象的长度
u32 reciprocal_buffer_size;//该值用于计算对象的索引
/* 3) touched by every alloc & free from the backend */
unsigned int flags; /* constant flags *///当前只有一个标志。如果管理结构存储在slab外部，则置位CFLAGS_OFF_SLAB
unsigned int num; /* # of objs per slab *///每个slab中对象的最大数目
/* 4) cache_grow/shrink */
/* order of pgs per slab (2^n) */
unsigned int gfporder;//每个slab中的页数
/* force GFP flags, e.g. GFP_DMA */
gfp_t gfpflags;
size_t colour; /* cache colouring range *///缓存着色范围
unsigned int colour_off; /* colour offset *///着色偏移
struct kmem_cache *slabp_cache;//如果slab头部的管理数据存储在slab外部，则其指向分配所需内存的一般性缓存
unsigned int slab_size;
unsigned int dflags; /* dynamic flags *///动态标志
/* constructor func */
void (*ctor)(struct kmem_cache *, void *);//构造函数
/* 5) cache creation/removal */
const char *name;
struct list_head next;//用于将所有kmem_cache实列保存在全家链表cache_chain上。
/* 6) statistics */
#if STATS
unsigned long num_active;
unsigned long num_allocations;
unsigned long high_mark;
unsigned long grown;
unsigned long reaped;
unsigned long errors;
unsigned long max_freeable;
unsigned long node_allocs;
unsigned long node_frees;
unsigned long node_overflow;
atomic_t allochit;
atomic_t allocmiss;
atomic_t freehit;
atomic_t freemiss;
#endif
#if DEBUG
/*
* If debugging is enabled, then the allocator can add additional
* fields and/or padding to every object. buffer_size contains the total
* object size including these internal fields, the following two
* variables contain the offset to the user object and its size.
*/
int obj_offset;
int obj_size;//缓存中对象的长度
#endif
/*
* We put nodelists[] at the end of kmem_cache, because we want to size
* this array to nr_node_ids slots instead of MAX_NUMNODES
* (see kmem_cache_init())
* We still use [MAX_NUMNODES] and not [1] or [0] because cache_cache
* is statically defined, so we reserve the max number of nodes.
*/
struct kmem_list3 *nodelists[MAX_NUMNODES];
/*
* Do not add fields after nodelists[]
*/
};
内核对每个处理器都提供了一个array_cache实列。该结构定义如下:
struct array_cache {
unsigned int avail;//当前可用对象的数目
unsigned int limit;
unsigned int batchcount;
unsigned int touched;//在从缓存移除一个对象时，将touched设置为1，而缓存收缩时，将touched设为0.
spinlock_t lock;
void *entry[];//便于访问内存中，该实列之后的各个对象 /*
* Must have this definition in here for the proper
* alignment of array_cache. Also simplifies accessing
* the entries.
*/
};struct kmem_list3 {
struct list_head slabs_partial; /* partial list first, better asm code */
struct list_head slabs_full;
struct list_head slabs_free;
unsigned long free_objects;
unsigned int free_limit;
unsigned int colour_next; /* Per-node cache coloring */
spinlock_t list_lock;
struct array_cache *shared; /* shared per node */
struct array_cache **alien; /* on other nodes */
unsigned long next_reap; /* updated without locking */
int free_touched; /* updated without locking */
};用于管理slab链表的表头保存在一个独立的数据结构中
struct kmem_list3 {
struct list_head slabs_partial; /* partial list first, better asm code */
struct list_head slabs_full;
struct list_head slabs_free;
unsigned long free_objects;//表示slabs_partial、slabs_free所有slab中空闲对象的总数
unsigned int free_limit;//指定了所有slab上容许的未使用的对象的最大数目
unsigned int colour_next; /* Per-node cache coloring */
spinlock_t list_lock;
struct array_cache *shared; /* shared per node */
struct array_cache **alien; /* on other nodes */
unsigned long next_reap; /* updated without locking *///指定两次收缩的时间间隔
int free_touched; /* updated without locking *///表示缓存是否活动，在缓存中获取一个对象时，将该值设置为1，在收缩时，将其设置为0，但内核只有在该值预先设置为0时，才会对其进行收缩
};初始化
kmem_cache_init函数用于初始化slab分配器。它在内核初始化阶段、伙伴系统启动之后调用。
1 create the cache_cache（kmem_cache静态数据结构）
2+3 create the kmalloc caches
4 Replace the bootstrap head arrays
5 Replace the bootstrap kmem_list3's
6 resize the head arrays to their final sizes
done!
创建缓存
创建新的slab缓存必须调用kmem_cache_create。
<mm/slab.c>
struct kmem_cache *kmem_cache_create(const char *name,size_t size,size_t align,unsigned long flags,void (*ctor)(struct kmem_cache*,void*))
{
...
if (size & (BYTES_PER_WORD - 1)) {//计算填充长度（将对象长度向上舍入到处理器字长的倍数）
size += (BYTES_PER_WORD - 1);
size &= ~(BYTES_PER_WORD - 1);
}
...
//处理对象对齐
if (flags & SLAB_HWCACHE_ALIGN) {
/*
* Default alignment: as specified by the arch code. Except if
* an object is really small, then squeeze multiple objects into
* one cacheline.
*/
ralign = cache_line_size();
while (size <= ralign / 2)
ralign /= 2;
} else {
ralign = BYTES_PER_WORD;
}
...
/* Get cache's description obj. */
cachep = kmem_cache_zalloc(&cache_cache, GFP_KERNEL);//分配struct kmem_cache的一个新实列
...
/*
* Determine if the slab management is 'on' or 'off' slab.
* (bootstrapping cannot cope with offslab caches so don't do
* it too early on.)
*/
//确定是否将slab头存储在slab之上:如果对象的长度大于页帧的1/8，则将头部管理数据存储在slab之外
if ((size >= (PAGE_SIZE >> 3)) && !slab_early_init)
/*
* Size is large, assume best to place the slab management obj
* off-slab (should allow better packing of objs).
*/
flags |= CFLGS_OFF_SLAB;
size = ALIGN(size, align);
left_over = calculate_slab_order(cachep, size, align, flags);//寻找理想的slab长度（迭代计算）
...
slab_size = ALIGN(cachep->num * sizeof(kmem_bufctl_t)+ sizeof(struct slab), align);//slab头的长度会进行舍入，已确保之后的各个数组项适当对齐
if (flags & CFLGS_OFF_SLAB && left_over >= slab_size) {//如果slab上有足够空闲空间可存储slab头，则清除CFLGS_OFF_SLAB标志，将slab头，存储在空闲空间中
flags &= ~CFLGS_OFF_SLAB;
left_over -= slab_size;
}
...
cachep->colour_off = cache_line_size();
/* Offset must be a multiple of the alignment. */
if (cachep->colour_off < align)
cachep->colour_off = align;
cachep->colour = left_over / cachep->colour_off;//计算颜色数目
...
if (setup_cpu_cache(cachep)) {//构建per-CPU缓存与klist3
__kmem_cache_destroy(cachep);
cachep = NULL;
goto oops;
}
//加入全局链表
list_add(&cachep->next, &cache_chain);
}
分配对象
kmem_cache_alloc用于从特定的缓存获取对象。需要两个参数：用于获取对象的缓存，以及精确描述分配特征的标志量。
<slab.h>
void *kmem_cache_alloc(kmem_cache_t *cachep,gfp_t flags)如果per-CPU缓存中有空闲对象，则从中获取。但如果其中的所有对象都已经分配，则重新填充缓存。在最坏的情况下，可能需要新建一个slab.
<mm/slab.c>
static inline void *____cache_alloc(struct kmem_cache *cachep, gfp_t flags)
{
void *objp;
struct array_cache *ac;
check_irq_off();
ac = cpu_cache_get(cachep);
if (likely(ac->avail)) {//per-CPU缓存中有对象
STATS_INC_ALLOCHIT(cachep);
ac->touched = 1;
objp = ac->entry[--ac->avail];
} else {//per-CPU没有对象，需要重新填充
STATS_INC_ALLOCMISS(cachep);
objp = cache_alloc_refill(cachep, flags);
}
return objp;
}<mm/slab.c>
static void *cache_alloc_refill(struct kmem_cache *cachep, gfp_t flags)
{
int batchcount;
struct kmem_list3 *l3;
struct array_cache *ac;
int node;
node = numa_node_id();
check_irq_off();
ac = cpu_cache_get(cachep);
retry:
batchcount = ac->batchcount;
if (!ac->touched && batchcount > BATCHREFILL_LIMIT) {
/*
* If there was little recent activity on this cache, then
* perform only a partial refill. Otherwise we could generate
* refill bouncing.
*/
batchcount = BATCHREFILL_LIMIT;
}
l3 = cachep->nodelists[node];
BUG_ON(ac->avail > 0 || !l3);
spin_lock(&l3->list_lock);
/* See if we can refill from the shared array */
if (l3->shared && transfer_objects(ac, l3->shared, batchcount))
goto alloc_done;
while (batchcount > 0) {
//选择获取对象的slab链表（首先时slab_partial，然后是slab_free）
struct list_head *entry;
struct slab *slabp;
/* Get slab alloc is to come from. */
entry = l3->slabs_partial.next;
if (entry == &l3->slabs_partial) {
l3->free_touched = 1;
entry = l3->slabs_free.next;
if (entry == &l3->slabs_free)
goto must_grow;
}
slabp = list_entry(entry, struct slab, list);
check_slabp(cachep, slabp);
check_spinlock_acquired(cachep);
/*
* The slab was either on partial or free list so
* there must be at least one object available for
* allocation.
*/
BUG_ON(slabp->inuse < 0 || slabp->inuse >= cachep->num);
while (slabp->inuse < cachep->num && batchcount--) {
STATS_INC_ALLOCED(cachep);
STATS_INC_ACTIVE(cachep);
STATS_SET_HIGH(cachep);
//移动
ac->entry[ac->avail++] = slab_get_obj(cachep, slabp,
node);
}
check_slabp(cachep, slabp);
/* move slabp to correct slabp list: */
//将slabp移动到正确的slab链表
list_del(&slabp->list);
if (slabp->free == BUFCTL_END)
list_add(&slabp->list, &l3->slabs_full);
else
list_add(&slabp->list, &l3->slabs_partial);
}
must_grow:
l3->free_objects -= ac->avail;
alloc_done:
spin_unlock(&l3->list_lock);
if (unlikely(!ac->avail)) {
int x;
x = cache_grow(cachep, flags | GFP_THISNODE, node, NULL);
/* cache_grow can reenable interrupts, then ac could change. */
ac = cpu_cache_get(cachep);
if (!x && ac->avail == 0) /* no objects in sight? abort */
return NULL;
if (!ac->avail) /* objects refilled by interrupt? */
goto retry;
}
ac->touched = 1;
return ac->entry[--ac->avail];
}
static void *slab_get_obj(struct kmem_cache *cachep, struct slab *slabp,
int nodeid)
{
void *objp = index_to_obj(cachep, slabp, slabp->free);
kmem_bufctl_t next;
slabp->inuse++;
next = slab_bufctl(slabp)[slabp->free];
#if DEBUG
slab_bufctl(slabp)[slabp->free] = BUFCTL_FREE;
WARN_ON(slabp->nodeid != nodeid);
#endif
slabp->free = next;
return objp;
}
缓存的增长
static int cache_grow(struct kmem_cache *cachep,
gfp_t flags, int nodeid, void *objp)
{
struct slab *slabp;
size_t offset;
gfp_t local_flags;
struct kmem_list3 *l3;
/*
* Be lazy and only check for valid flags here, keeping it out of the
* critical path in kmem_cache_alloc().
*/
BUG_ON(flags & GFP_SLAB_BUG_MASK);
local_flags = flags & (GFP_CONSTRAINT_MASK|GFP_RECLAIM_MASK);
/* Take the l3 list lock to change the colour_next on this node */
check_irq_off();
l3 = cachep->nodelists[nodeid];
spin_lock(&l3->list_lock);
/* Get colour for the slab, and cal the next value. */
//计算颜色和偏移量
offset = l3->colour_next;
l3->colour_next++;
if (l3->colour_next >= cachep->colour)
l3->colour_next = 0;
spin_unlock(&l3->list_lock);
offset *= cachep->colour_off;
if (local_flags & __GFP_WAIT)
local_irq_enable();
/*
* The test for missing atomic flag is performed here, rather than
* the more obvious place, simply to reduce the critical path length
* in kmem_cache_alloc(). If a caller is seriously mis-behaving they
* will eventually be caught here (where it matters).
*/
kmem_flagcheck(cachep, flags);
/*
* Get mem for the objs. Attempt to allocate a physical page from
* 'nodeid'.
*/
if (!objp)
objp = kmem_getpages(cachep, local_flags, nodeid);//利用伙伴系统分配slab使用的页帧。每个页都设置了PG_Slab标志，在一个slab用于满足短期或可回收分配时，则将标志__GFP_RECLAIMABLE传递到伙伴系统
if (!objp)
goto failed;
/* Get slab management. */
slabp = alloc_slabmgmt(cachep, objp, offset,
local_flags & ~GFP_CONSTRAINT_MASK, nodeid);//slabp头部初始化，用适当的值初始化slab数据结构的colouroff、s_mem和inuse成员
if (!slabp)
goto opps1;
slabp->nodeid = nodeid;
slab_map_pages(cachep, slabp, objp);//建立slab页与slab和缓存的关联（复用page结构的lru字段）
cache_init_objs(cachep, slabp);//调用构造函数，初始化slab中的对象
if (local_flags & __GFP_WAIT)
local_irq_disable();
check_irq_off();
spin_lock(&l3->list_lock);
/* Make slab active. */
list_add_tail(&slabp->list, &(l3->slabs_free));
STATS_INC_GROWN(cachep);
l3->free_objects += cachep->num;
spin_unlock(&l3->list_lock);
return 1;
opps1:
kmem_freepages(cachep, objp);
failed:
if (local_flags & __GFP_WAIT)
local_irq_disable();
return 0;
}释放对象
如果一个对象不在需要，那么必须使用kmem_cache_free返回给slab分配器。
类似于分配，根据per-CPU缓存的状态不同，有两种可选的操作流程。如果per-CPU缓存中的对象数目低于允许的限制，则在其存储一个指向缓存中的对象的指针。
否则将一些对象从缓存中移回slab。从编号最低的数组元素开始：缓存的实现依据先进先出原理，这些对象在数组中已经很长时间，因此不太可能仍然驻留在CPU高速缓存中。
static inline void __cache_free(struct kmem_cache *cachep, void *objp)
{
struct array_cache *ac = cpu_cache_get(cachep);
check_irq_off();
objp = cache_free_debugcheck(cachep, objp, __builtin_return_address(0));
/*
* Skip calling cache_free_alien() when the platform is not numa.
* This will avoid cache misses that happen while accessing slabp (which
* is per page memory reference) to get nodeid. Instead use a global
* variable to skip the call, which is mostly likely to be present in
* the cache.
*/
if (numa_platform && cache_free_alien(cachep, objp))
return;
if (likely(ac->avail < ac->limit)) {
STATS_INC_FREEHIT(cachep);
ac->entry[ac->avail++] = objp;
return;
} else {
STATS_INC_FREEMISS(cachep);
cache_flusharray(cachep, ac);
ac->entry[ac->avail++] = objp;
}
}static void free_block(struct kmem_cache *cachep, void **objpp, int nr_objects,
int node)
{
int i;
struct kmem_list3 *l3;
for (i = 0; i < nr_objects; i++) {
void *objp = objpp[i];
struct slab *slabp;
slabp = virt_to_slab(objp);//根据page关系，找到slab
l3 = cachep->nodelists[node];
list_del(&slabp->list);//临时将slab从链表中删除
check_spinlock_acquired_node(cachep, node);
check_slabp(cachep, slabp);
slab_put_obj(cachep, slabp, objp, node);//放入slab：：用于分配的第一个对象是刚刚删除的，而列表中的下一个对象则是此前的第一对象
STATS_DEC_ACTIVE(cachep);
l3->free_objects++;
check_slabp(cachep, slabp);
/* fixup slab chains */
//重新将slab加入链表中
if (slabp->inuse == 0) {
if (l3->free_objects > l3->free_limit) {
l3->free_objects -= cachep->num;
/* No need to drop any previously held
* lock here, even if we have a off-slab slab
* descriptor it is guaranteed to come from
* a different cache, refer to comments before
* alloc_slabmgmt.
*/
//缓存中空闲对象的数目超过预定义的限制cachep->free_limit,则销毁slab
slab_destroy(cachep, slabp);
} else {
list_add(&slabp->list, &l3->slabs_free);
}
} else {
/* Unconditionally move a slab to the end of the
* partial list on free - maximum time for the
* other objects to be freed, too.
*/
list_add_tail(&slabp->list, &l3->slabs_partial);
}
}
}销毁缓存
如果要销毁只包含未使用对象的一个缓存，则必须调用kmem_cache_destroy函数。
- 依次扫描slabs_free链表上的slab.首先对每个slab上的每个对象调用析构函数，然后将slab的内存空间返回给伙伴系统
- 释放用于per-CPU缓存的内存空间
- 从cache_cache链表移除相关数据
通用缓存
kmalloc
kfree
两个函数只是slab分配器的前端。
处理器高速缓存和TLB控制
内核中各个特定于CPU的部分都必须提供下列函数，以便控制TLB和高速缓存。
- flush_tlb_all和flush_cache_all刷出整个TLB和高速缓存。这只在操纵内核（而非用户空间进程的）页表时需要，因为此类修改不仅影响所有进程，而且影响系统中的所有处理器
- flush_tlb_mm(struct mm_struct * mm)和flush_cache_mm刷出所有属于地址空间mm的TLB/高速缓存项
- flush_tlb_range(struct vm_area_struct * vma, unsigned long start, unsigned longend)和flush_cache_range(vma, start,end)刷出地址范围vma->vm_mm中虚拟地址start和end之间的所有TLB/高速缓存项
- flush_tlb_page(struct vm_area_struct * vma, unsigned long page)和flush_cache_page(vma, page)刷出虚拟地址在［page, page + PAGE_SIZE］范围内所有的TLB/高速缓存项。
- update_mmu_cache(struct vm_area_struct * vma, unsigned long address, pte_t pte)在处理页失效之后调用。它在处理器的内存管理单元MMU中加入信息，使得虚拟地址address由页表项pte描述（仅当存在外部MMU时，才需要该函数。通常MMU集成在处理器内部，但有例外情况。例如，MIPS处理器具有外部MMU。）
flush_cache_和flush_tlb_函数经常成对出现:
<kernel/fork.c>
flush_cache_mm(oldmm);
/*操作页表*/
flush_tlb_mm(oldmm);操作的顺序是：刷出高速缓存、操作内存、刷出TLB。这个顺序很重要，有下面两个原因。
- 如果顺序反过来，那么在TLB刷出之后、正确信息提供之前，多处理器系统中的另一个CPU可能从进程的页表取得错误的信息。
- 在刷出高速缓存时，某些体系结构需要依赖TLB中的“虚拟->物理”转换规则（具有该性质的高速缓存称之为严格的）。flush_tlb_mm必须在flush_cache_mm之后执行，以确保这一点
小结
在内核进入正常运作之后，内存管理分两个层次处理。伙伴系统负责物理页帧的管理，而slab分配器则处理小块内存的分配，并提供了用户层malloc函数族的内核等价物