介绍一下几个linux的内存分配器。

伙伴分配器

内核初始化完毕后，使用页分配器管理物理页，当前使用的页分配器就是伙伴分配器，伙伴分配器的特点是管理算法简单且高效。

基本伙伴分配器

连续的物理页称为页块（page block），阶（order）是页的数量单位，2的n次方个连续页称为n阶页块，满足如下条件的两个n阶页块称为伙伴（buddy）。

1. 两个页块是相邻的，即物理地址是连续的；
2. 页块的第一页的物理面页号必须是2的n次方的整数倍；
3. 如果合并（n+1）阶页块，第一页的物理页号必须是2的括号(n+1)次方的整数倍。

伙伴分配器分配和释放物理页的数量单位也为阶（order）。以单页为说明，0号页和1号页是伙伴，2号页和3号页是伙伴。1号页和2号页不是伙伴？因为1号页和2号页合并组成一阶页块，第一页的物理页号不是2的整数倍。

分配过程

1. 查看是否有空闲的n阶页块，如果有，则直接分配；如果没有，则进入步骤2。
2. 查看是否有空闲的n+1阶页块，如果有，把该页块拆分为两个n阶页块，一个插入空闲n阶页块链表，另一个分配出去；如果没有，执行步骤3。
3. 查看是否有空闲的n+2阶页块，如果有，拆分为两个n+1阶页块，一个插入空闲n+1阶页块链表，另一个执行步骤2；如果没有，继续寻找更高阶页块。

释放过程

释放过程与分配过程基本相反。

1. 查看伙伴页块是否空闲，如果不空闲，则把这个页块插入到空闲n阶页块的链表中；如果空闲，就合并为n+1阶页块。
2. 如果合并，寻找合并后的n+1阶页块是否空闲，如果空闲，按照步骤1执行。

分区伙伴分配器

内核在基本伙伴分配器的基础上做了进一步扩展。

• 支持内存节点和区域，称为分区的伙伴分配器
• 为预防内存碎片，把物理页根据可移动性分组
• 针对分配单页做性能优化。为减少处理器之间的竞争，在内存区域增加一个每处理器页集合

内存区域的结构体struct zone成员free_area用来维护空闲页块，数组下标对应页块的阶数。结构体free_area的成员free_list是空闲页块的链表，nr_free是空闲页块的数量。内存区域的结构体成员managed_pages是伙伴分配器管理的物理页的数量。具体看下源码：

struct zone {
	/* Read-mostly fields */

	/* zone watermarks, access with *_wmark_pages(zone) macros */
    //区域水线，使用_wmark_pages(zone)宏进行访问
	unsigned long watermark[NR_WMARK];

	unsigned long nr_reserved_highatomic;

	/*
	 * We don't know if the memory that we're going to allocate will be
	 * freeable or/and it will be released eventually, so to avoid totally
	 * wasting several GB of ram we must reserve some of the lower zone
	 * memory (otherwise we risk to run OOM on the lower zones despite
	 * there being tons of freeable ram on the higher zones).  This array is
	 * recalculated at runtime if the sysctl_lowmem_reserve_ratio sysctl
	 * changes.
	 */
	long lowmem_reserve[MAX_NR_ZONES];

#ifdef CONFIG_NUMA
	int node;
#endif
	struct pglist_data	*zone_pgdat;
	struct per_cpu_pageset __percpu *pageset;

#ifndef CONFIG_SPARSEMEM
	/*
	 * Flags for a pageblock_nr_pages block. See pageblock-flags.h.
	 * In SPARSEMEM, this map is stored in struct mem_section
	 */
	unsigned long		*pageblock_flags;
#endif /* CONFIG_SPARSEMEM */

	/* zone_start_pfn == zone_start_paddr >> PAGE_SHIFT */
	unsigned long		zone_start_pfn;

	/*
	 * spanned_pages is the total pages spanned by the zone, including
	 * holes, which is calculated as:
	 * 	spanned_pages = zone_end_pfn - zone_start_pfn;
	 *
	 * present_pages is physical pages existing within the zone, which
	 * is calculated as:
	 *	present_pages = spanned_pages - absent_pages(pages in holes);
	 *
	 * managed_pages is present pages managed by the buddy system, which
	 * is calculated as (reserved_pages includes pages allocated by the
	 * bootmem allocator):
	 *	managed_pages = present_pages - reserved_pages;
	 *
	 * So present_pages may be used by memory hotplug or memory power
	 * management logic to figure out unmanaged pages by checking
	 * (present_pages - managed_pages). And managed_pages should be used
	 * by page allocator and vm scanner to calculate all kinds of watermarks
	 * and thresholds.
	 *
	 * Locking rules:
	 *
	 * zone_start_pfn and spanned_pages are protected by span_seqlock.
	 * It is a seqlock because it has to be read outside of zone->lock,
	 * and it is done in the main allocator path.  But, it is written
	 * quite infrequently.
	 *
	 * The span_seq lock is declared along with zone->lock because it is
	 * frequently read in proximity to zone->lock.  It's good to
	 * give them a chance of being in the same cacheline.
	 *
	 * Write access to present_pages at runtime should be protected by
	 * mem_hotplug_begin/end(). Any reader who can't tolerant drift of
	 * present_pages should get_online_mems() to get a stable value.
	 *
	 * Read access to managed_pages should be safe because it's unsigned
	 * long. Write access to zone->managed_pages and totalram_pages are
	 * protected by managed_page_count_lock at runtime. Idealy only
	 * adjust_managed_page_count() should be used instead of directly
	 * touching zone->managed_pages and totalram_pages.
	 */
	unsigned long		managed_pages;
	unsigned long		spanned_pages;
	unsigned long		present_pages;

	const char		*name;

#ifdef CONFIG_MEMORY_ISOLATION
	/*
	 * Number of isolated pageblock. It is used to solve incorrect
	 * freepage counting problem due to racy retrieving migratetype
	 * of pageblock. Protected by zone->lock.
	 */
	unsigned long		nr_isolate_pageblock;
#endif

#ifdef CONFIG_MEMORY_HOTPLUG
	/* see spanned/present_pages for more description */
	seqlock_t		span_seqlock;
#endif

	int initialized;

	/* Write-intensive fields used from the page allocator */
	ZONE_PADDING(_pad1_)

	/* free areas of different sizes */
    //MAX_ORDER是最大阶数，实际上是可分配的最大阶数加1
    //默认值11，意味着伙伴分配器一次最多可分配2^10页
	struct free_area	free_area[MAX_ORDER];

	/* zone flags, see below */
	unsigned long		flags;

	/* Primarily protects free_area */
	spinlock_t		lock;

	/* Write-intensive fields used by compaction and vmstats. */
	ZONE_PADDING(_pad2_)

	/*
	 * When free pages are below this point, additional steps are taken
	 * when reading the number of free pages to avoid per-cpu counter
	 * drift allowing watermarks to be breached
	 */
	unsigned long percpu_drift_mark;

#if defined CONFIG_COMPACTION || defined CONFIG_CMA
	/* pfn where compaction free scanner should start */
	unsigned long		compact_cached_free_pfn;
	/* pfn where async and sync compaction migration scanner should start */
	unsigned long		compact_cached_migrate_pfn[2];
#endif

#ifdef CONFIG_COMPACTION
	/*
	 * On compaction failure, 1<
	unsigned int		compact_considered;
	unsigned int		compact_defer_shift;
	int			compact_order_failed;
#endif

#if defined CONFIG_COMPACTION || defined CONFIG_CMA
	/* Set to true when the PG_migrate_skip bits should be cleared */
	bool			compact_blockskip_flush;
#endif

	bool			contiguous;

	ZONE_PADDING(_pad3_)
	/* Zone statistics */
	atomic_long_t		vm_stat[NR_VM_ZONE_STAT_ITEMS];
} ____cacheline_internodealigned_in_smp;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153

介绍里面两个成员

struct free_area

struct free_area {
	struct list_head	free_list[MIGRATE_TYPES];
	unsigned long		nr_free;
};
1
2
3
4

区域水线

首选的内存区域在什么情况下从备用区域借用物理页？此问题从区域水线讲解深入理解，每个内存区域有3个水线。

水线区分

1. 高水线（HIGH）：如果内存区域的空闲页数大于高水线，说明该内存区域的内存充足；
2. 低水线（LOW）：如果内存区域的空闲页数小于低水线，说明该内存区域的内存轻微不足；
3. 最低水线（MIN）：如果内存区域空闲页数小于最低水线，说明该内存区域的内存严重不足。

最低水线以下的内存称为紧急保留内存，在内存严重不足的紧急情况下才会给少量的紧急保留内存使用，或是释放更多的内存来使用。这种情况一般很少存在，现在内存一般足够大，基本不用考虑这个问题。

enum zone_watermarks {
	WMARK_MIN,
	WMARK_LOW,
	WMARK_HIGH,
	NR_WMARK
};

#define min_wmark_pages(z) (z->watermark[WMARK_MIN])
#define low_wmark_pages(z) (z->watermark[WMARK_LOW])
#define high_wmark_pages(z) (z->watermark[WMARK_HIGH])
1
2
3
4
5
6
7
8
9
10

水线计算

计算水线时，有两个重要参数
1.min_free_kbytes最小空闲字节数。默认值$4\sqrt{lowmem\_kbytes}$，并且限制范围由机器决定。其中lowmem_kbytes是低端内存大小，单位是KB，通过命令cat proc/sys/vm/min_free_kbytes查看，也可以修改。
2. watermark_scale_factor水线缩放因子。默认值10，通过命令cat proc/sys/vm/watermark_scale_factor查看，也可修改，取值范围[1,1000]。

可以通过_setup_per_zone_wmarks()负责计算每个内存区域的最低水线、低水线和高水线。

• min_free_pages=min_free_pages所对应的页数
• lowmem_pages=所有低端内存区域伙伴分配器管理的页数总和
• 高端内存区域的最低水线=zone->managed_pages/1024
• 低端内存区域的最低水线=min_free_pages*zone->managed_pages/lowmem_pages

低水线和高水线计算

增量=max(最低水线/4,managed_pages*watermark_scale_factor/10000)
低水线=最低水线+增量
高水线=最低水线+增量*2
1
2
3

如果最低水线/4比较大，那么计算公式简化为

低水线=最低水线*5/4
高水线=最低水线*3/2
1
2

slab分配器

Buddy提供以page为单位的内存分配接口，这对内核来说颗粒度还太大，所以需要一种新的机制，将page拆分为更小的单位来管理。
linux中支持的主要有：slab、slub、slob。其中slob分配器的总代码量比较少，但分配速度不是最高效的，所以不是为大型系统设计，适合内存紧张的嵌入式系统。在配备大量物理内存的大型计算机上，slab分配器的管理数据结构的内存开销比较大，所以设计了slub分配器。这里只介绍slab，其余两种差不多，可以类推。

/*
 * struct slab
 *
 * Manages the objs in a slab. Placed either at the beginning of mem allocated
 * for a slab, or allocated from an general cache.
 * Slabs are chained into three list: fully used, partial, fully free slabs.
 */
struct slab {
	struct list_head list;     //满，部分满或空的链表
	unsigned long colouroff;    //slab着色的偏移量
	void *s_mem;		/* including colour offset */ //在slab中的第一个对象
	unsigned int inuse;	/* num of objs active in slab */  //slab中已分配的对象数
	kmem_bufctl_t free;     //第一个空闲对象
	unsigned short nodeid;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

内存缓存

介绍一下通用的内存缓存和专用的内存缓存编程接口

通用的内存缓存

三种分配器有统一的编程接口
分配内存kmalloc：块分配器找到一个合适的通用内存缓存，对象的长度刚好大于等于请求的长度。

static __always_inline void *kmalloc（size_t size,gfp_t flags;
1

参数size是需要分配内存的长度，flags是传给页分配器的分配标志位
重新分配内存krealloc：根据新的长度给对象重新分配内存，如果分配成功返回新地址，失败返回NULL。

void *krealloc(const void *p,size_t new_size,gpf_t flags);
1

参数p是需要重新分配的对象，new_size需要分配的新的长度，flag标志位。
释放内存kfree：释放对象

void kfree(const void *objp);
1

这里有个问题，内核如何知道kfree该释放哪个kmem_cache对象呢？首先，根据对象的虚拟地址来得到其物理地址，然后得到物理页号，得到page实例，注意如果是复合页，要得到首页的page实例，再根据page实例的成员slab_cache得到kmem_cache对象。
使用通用内存缓存，有缺陷。块分配器需要找到一个对象，其长度需要刚好大于等于请求的通用内存长度，如果请求的长度和内存缓存对象相差很大，就会浪费很大的空间。

专用内存缓存

为了解决上述问题，引入专用内存缓存。接口：

• 创建内存缓存kmem_cache_create：创建专用的内存缓存，如果成功返回内存缓存地址，失败返回NULL
• 指定内存缓存分配kmem_cache_alloc：从指定内存缓存中分配地址
• 释放对象kmem_cache_free：释放所属的内存缓存对应的对象
• 销毁内存缓存keme_cache_destroy

数据结构

每个内存缓存对应一个kmem_cache实例。每个slab由一个或多个连续的物理页组成，页的阶数为kmem_cache.gfporder，如果阶数大于0，则组成一个复合页。
slab被划分为多个对象，大多数情况下slab长度不是对象长度的整数倍，slab有剩余部分，可以用来给slab着色。着色指，把slab的第一个对象从slab的起始地址偏移一个数值，偏移值是处理器一级缓存行的整数倍，不同slab的偏移值不同，使不同的slab对象映射到处理器不同的缓存行。

struct kmem_cache {
    //本地高速缓存，每CPU结构，对象释放时，优先放入这个本地CPU高速缓存中
	struct array_cache __percpu *cpu_cache;
/* 1) Cache tunables. Protected by slab_mutex */
    //本地高速缓存预留数量，控制一次获得或转移对象的数量
	unsigned int batchcount; 
	unsigned int limit; //本地高速缓存中空闲对象的最大数目
	unsigned int shared; //CPU共享高速缓存标志，实际地址保存在kmem_cache_node结构中
    unsigned int size; //对象长度 + 填充字节
    
	struct reciprocal_value reciprocal_buffer_size;
/* 2) touched by every alloc & free from the backend */

	unsigned int flags;		/* constant flags */
    //每个slab的对象数量，同一个slab高速缓存中对象个数相同
	unsigned int num;		/* # of objs per slab */

/* 3) cache_grow/shrink */
	/* order of pgs per slab (2^n) */
	unsigned int gfporder;  //slab阶数

	/* force GFP flags, e.g. GFP_DMA */
	gfp_t allocflags;

	size_t colour;			/* cache colouring range */
	unsigned int colour_off;	/* colour offset */

    //空闲对象链表放在slab外部时使用，
    //管理用于slab对象管理结构中freelist成员的缓存，也就是又一个新缓存
	struct kmem_cache *freelist_cache;
	unsigned int freelist_size;  //空闲对象链表的大小

	/* constructor func */
	void (*ctor)(void *obj);

/* 4) cache creation/removal */
	const char *name;
	struct list_head list;
	int refcount;
	int object_size;  //对象原始长度
	int align;  //对齐的长度

/* 5) statistics */
#ifdef CONFIG_DEBUG_SLAB
	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;
#ifdef CONFIG_DEBUG_SLAB_LEAK
	atomic_t store_user_clean;
#endif

	/*
	 * If debugging is enabled, then the allocator can add additional
	 * fields and/or padding to every object. 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;
#endif /* CONFIG_DEBUG_SLAB */

#ifdef CONFIG_MEMCG
	struct memcg_cache_params memcg_params;
#endif
#ifdef CONFIG_KASAN
	struct kasan_cache kasan_info;
#endif

#ifdef CONFIG_SLAB_FREELIST_RANDOM
	unsigned int *random_seq;
#endif
    //每node链表，每个NUMA的结点都有该SLAB链表
	struct kmem_cache_node *node[MAX_NUMNODES];
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

每个内存节点对应一个kmem_cache_node实例

struct kmem_cache_node {
	spinlock_t list_lock;

	struct list_head slabs_partial;	//部分空闲链表
	struct list_head slabs_full; //完全用尽链表
	struct list_head slabs_free; //完全空闲链表
	unsigned long total_slabs;	// slab总数量
	unsigned long free_slabs;	// 空闲slab数量
	unsigned long free_objects; //高速缓存中空闲对象个数(包括slabs_partial、slabs_free链表中空闲对象)
	unsigned int free_limit; //高速缓存中空闲对象的上限
	unsigned int colour_next;	/* Per-node cache coloring */
	struct array_cache *shared;	// 结点上所有CPU共享的本地高速缓存
	struct alien_cache **alien;	// 其他结点上所有CPU共享的本地高速缓存
	unsigned long next_reap;	/* updated without locking */
	int free_touched;		/* updated without locking */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

再来看一下整体的结构图

再贴一下array_cache代码

struct array_cache {
	unsigned int avail; //当前CPU上该slab可用对象数量
    //最大对象数目，和kmem_cache中一样
    //当本地对象缓冲池的空闲对象数目大于limit时就会主动释放batchcount个对象，便于内核回收和销毁slab
	unsigned int limit;
    //同kmem_cache，本地高速缓存预留数量，控制一次获得或转移对象的数量
    //表示当前CPU的本地对象缓冲池array_cache为空时，从共享的缓冲池或者slabs_partial/slabs_free列表中获取对象的数目。
	unsigned int batchcount;
	unsigned int touched; //标志位，从缓存获取对象时，touched置1，缓存收缩时, touched置0
	void *entry[];	/* 伪数组，使用时用于保存刚释放的对象
			 * Must have this definition in here for the proper
			 * alignment of array_cache. Also simplifies accessing
			 * the entries.
			 */
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

page结构体

struct page {
	/* First double word block */
    /* 标志位，每个bit代表不同的含义 */
	unsigned long flags;		/* Atomic flags, some possibly updated asynchronously */
	union {
		/*
		 * 如果mapping = 0，说明该page属于交换缓存（swap cache）；当需要使用地址空间时会指定交换分区的地址空间swapper_space
		 * 如果mapping != 0，bit[0] = 0，说明该page属于页缓存或文件映射，mapping指向文件的地址空间address_space
		 * 如果mapping != 0，bit[0] != 0，说明该page为匿名映射，mapping指向struct anon_vma对象
		 */
		struct address_space *mapping;	
		void *s_mem;			/* slab first object */
	};

	/* Second double word */
	struct {
		union {
			pgoff_t index;		/* Our offset within mapping. */
			void *freelist;		/* sl[aou]b first free object */
			bool pfmemalloc;	
		};

		union {
#if defined(CONFIG_HAVE_CMPXCHG_DOUBLE) && \
	defined(CONFIG_HAVE_ALIGNED_STRUCT_PAGE)
			/* Used for cmpxchg_double in slub */
			unsigned long counters;
#else
			/*
			 * Keep _count separate from slub cmpxchg_double data.
			 * As the rest of the double word is protected by
			 * slab_lock but _count is not.
			 */
			unsigned counters;
#endif

			struct {

				union {
					/*
					 * 被页表映射的次数，也就是说该page同时被多少个进程共享。初始值为-1，如果只被一个进程的页表映射了，该值为0 。
					 * 如果该page处于伙伴系统中，该值为PAGE_BUDDY_MAPCOUNT_VALUE（-128），
					 * 内核通过判断该值是否为PAGE_BUDDY_MAPCOUNT_VALUE来确定该page是否属于伙伴系统。
					 */
					atomic_t _mapcount;

					struct { /* SLUB */
						unsigned inuse:16;/* 这个inuse表示这个page已经使用了多少个object              */
						unsigned objects:15;
						unsigned frozen:1;/* frozen代表slab在cpu_slub，unfroze代表在partial队列或者full队列 */
					};
					int units;	/* SLOB */
				};
				/* 
				 * 引用计数，表示内核中引用该page的次数，如果要操作该page，引用计数会+1，操作完成-1。
				 * 当该值为0时，表示没有引用该page的位置，所以该page可以被解除映射，这往往在内存回收时是有用的
				 */
				atomic_t _count;		/* Usage count, see below. */
			};
			unsigned int active;	/* SLAB */
		};
	};

	/* Third double word block */
	union {
		/*
		 * page处于伙伴系统中时，用于链接相同阶的伙伴（只使用伙伴中的第一个page的lru即可达到目的）
		 * 设置PG_slab, 则page属于slab，page->lru.next指向page驻留的的缓存的管理结构，page->lru.prec指向保存该page的slab的管理结构
         * page被用户态使用或被当做页缓存使用时，用于将该page连入zone中相应的lru链表，供内存回收时使用
		 */
		struct list_head lru;	/* Pageout list, eg. active_list
					 * protected by zone->lru_lock !
					 * Can be used as a generic list
					 * by the page owner.
					 */
		/* 用作per cpu partial的链表使用 */
		struct {		/* slub per cpu partial pages */
			struct page *next;	/* Next partial slab */
#ifdef CONFIG_64BIT
			int pages;	/* Nr of partial slabs left */
			int pobjects;	/* Approximate # of objects */
#else
			/*  */
			short int pages;
			short int pobjects;
#endif
		};

		struct slab *slab_page; /* slab fields */
		struct rcu_head rcu_head;	/* Used by SLAB
						 * when destroying via RCU
						 */
		/* First tail page of compound page */
		struct {
			compound_page_dtor *compound_dtor;
			unsigned long compound_order;
		};
	};

	/* Remainder is not double word aligned */
	union {
		/*
		 * 如果设置了PG_private标志，则private字段指向struct buffer_head
		 * 如果设置了PG_compound，则指向struct page
		 * 如果设置了PG_swapcache标志，private存储了该page在交换分区中对应的位置信息swp_entry_t
		 * 如果_mapcount = PAGE_BUDDY_MAPCOUNT_VALUE，说明该page位于伙伴系统，private存储该伙伴的阶
		 */
		unsigned long private;		
		struct kmem_cache *slab_cache;	/* SL[AU]B: Pointer to slab */
		struct page *first_page;	/* Compound tail pages */
	};

#ifdef CONFIG_MEMCG
	struct mem_cgroup *mem_cgroup;
#endif

	/*
	 * On machines where all RAM is mapped into kernel address space,
	 * we can simply calculate the virtual address. On machines with
	 * highmem some memory is mapped into kernel virtual memory
	 * dynamically, so we need a place to store that address.
	 * Note that this field could be 16 bits on x86 ... ;)
	 *
	 * Architectures with slow multiplication can define
	 * WANT_PAGE_VIRTUAL in asm/page.h
	 */
#if defined(WANT_PAGE_VIRTUAL)
	void *virtual;			/* Kernel virtual address (NULL if
					   not kmapped, ie. highmem) */
#endif /* WANT_PAGE_VIRTUAL */

#ifdef CONFIG_KMEMCHECK
	/*
	 * kmemcheck wants to track the status of each byte in a page; this
	 * is a pointer to such a status block. NULL if not tracked.
	 */
	void *shadow;
#endif

#ifdef LAST_CPUPID_NOT_IN_PAGE_FLAGS
	int _last_cpupid;
#endif
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

计算slab长度

calculate_slab_order函数主要计算一个slab占用的页面个数，即计算阶数。简要介绍一下基本步骤：

1. 如果阶数大于等于最大阶数，那么选择这个阶数。尽量选择低的阶数，是因为申请高阶页块成功的概率较低。
2. 如果剩余长度小于等于slab长度的八分之一，就选择这个阶数。

static inline size_t calculate_slab_order(struct kmem_cache *cachep, size_t size, size_t align, unsigned long flags)
{
    size_t left_over = 0;
    int gfporder;

    //首先从order为0开始尝试，直到最大order(MAX_GFP_ORDER)为止
    for (gfporder = 0 ; gfporder <= MAX_GFP_ORDER; gfporder++) 
    {
        unsigned int num;
        size_t remainder;
        //调用cache计算函数，如果该order放不下一个size大小的object，即num为0，表示order太小，需要调整。
        //计算一个slab中的object的数目和slab剩余的字节数
        cache_estimate(gfporder, size, align, flags, &remainder, &num);
        if (!num)
            continue;
        //如果Slab管理区没有和对象存放在一起，并且该order存放对象数量大于每个Slab允许存放最大的对象数量，则返回。主要针对大内存对象
        if ((flags & CFLGS_OFF_SLAB) && num > offslab_limit)
            break;
        
        //找到了合适的order,将相关参数保存。
        //Slab中的对象数量
        cachep->num = num;
        //order值
        cachep->gfporder = gfporder;
        //Slab中的碎片大小
        left_over = remainder;
        //SLAB_RECLAIM_ACCOUNT：内核检查用户态程序有没有足够内存可用，被标记为这个标志的Slab将作为通缉对象。
        if (flags & SLAB_RECLAIM_ACCOUNT)
            break;
        //slab_break_gfp_order 定义为0
        //一个slab按照最小的页面数计算，比如不超过4KB的对象，每次分配slab只需要一页即可
        if (gfporder >= slab_break_gfp_order)
            break;
        //Slab碎片的8倍大小还是小于Slab大小，那么这样的碎片是可以接受的。
        if ((left_over * 8) <= (PAGE_SIZE << gfporder))
            break;
    }
    return left_over;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

着色

slab是一个或多个连续的物理页，起始地址总是页长度的整数倍，不同slab中相同偏移的位置在处理器一级缓存中的索引相同。如果slab的剩余部分的长度超过一级缓存行的长度，剩余部分对应的一级缓存行没有被利用；如果对象的填充字节的长度超过一级缓存行的长度，填充字节对应的一级缓存行没有被利用。这两种情况导致处理器的某些缓存行需要被反复刷新，而其余的缓存行却未被充分利用。
那么，slab着色是怎么回事呢？其实就是利用slab中的空余空间去做不同的偏移，这样就可以根据不同的偏移来区分size相同的对象了。
为什么slab中会有剩余空间？因为slab是以空间换时间。
做偏移的时候，也要考虑到缓存行中的对齐。
假如slab中有14个字节的剩余空间，cache line以4字节对齐，我们来看看有多少种可能的偏移，也就是有多少种可能的颜色。
第一种，偏移为0，也就是不偏移，那么剩余的14个字节在哪儿呢？放到结尾处，作为偏移补偿。
第二种，偏移4字节，此时偏移补偿为10字节。
第三种，偏移8字节，此时偏移补偿为6字节。
第四种，偏移12字节，此时偏移补偿为2字节。
再继续，就只能回归不偏移了，因为上一种的偏移补偿为2字节，已经不够对齐用了。
来总结一下看看有几种颜色。
第一种无偏移，后面是剩余空间 free 能满足多少次对齐 align ，就有多少种，总数： free/align +1 。
如果 free 小于 align ，slab着色就起不到作用，因为颜色只有一种，即不偏移的情况。
如果size相同的对象很多，但 free 不够大，或者 free/align 不够大，效果也不好。
因为颜色用完了，会从头再来。
继续上面的例子，如果有五个相同的对象，第五个对象的颜色与第一个相同，偏移为0。
这样一来，让一个slab移到缓存行b上面，另一个slab还是在原来的缓存行a上，两块数据分别可以在缓存行的a和b行上面进行读取，那么我们读取数据的时候就不会造成不必要的数据交换了。

每处理器数组缓存

内存缓存为每个处理器创建一个数组缓存（结构体array_cahce）。释放对象时，把对象存放到当前处理器对应的数组缓存中；分配对象的时候，先从当前处理器的数组缓存分配对象，采用后进先出（Last In First Out，LIFO）的原则，能保证本地cpu最近释放该slab cache的obj立马被下一个slab内存申请者获取到(有很大概率此obj仍然在本地cpu的硬件高速缓存中)，这种做可以提高性能。

array_cache中的entry空数组，就是用于保存本地cpu刚释放的obj，所以该数组初始化时为空，只有本地cpu释放slab cache的obj后才会将此obj装入到entry数组。array_cache的entry成员数组中保存的obj数量是由成员limit控制的，超过该限制后会将entry数组中的batchcount个obj迁移到对应节点cpu共享的空闲对象链表中。
分配对象的时候，先从当前处理器数组缓存分配对象，如果数组缓存为空，就批量分配对象，重新填充数组缓存，批量的值是在数组缓存的成员中；释放对象时，如果数组缓存是满的，就先把数组缓存中的对象批量还给slab（因为是由slab进行分配的），批量的值就是数组缓存的一个成员，然后把正在释放的对象存到数组缓存中。

slab分配器支持NUMA体系结构

内存缓存针对每个内存节点创建一个kmem_cache_node实例。

slab缓存会为不同的节点维护一个自己的slab链表，用来缓存和管理自己节点的slab obj，这通过kmem_cache中node数组成员来实现，node数组中的每个数组项都为其对应的节点分配了一个struct kmem_cache_node结构。
struct kmem_cache_node结构定义的变量是一个每node变量。相比于struct array_cache定义的每cpu变量，kmem_cache_node管理的内存区域粒度更大，因为kmem_cache_node维护的对象是slab，而array_cache维护的对象是slab中的obj（一个kmem_cache可能包含一个或多个slab，而一个slab中可能包含一个或多个slab obj）。
struct kmem_cache_node对于本节点中slab的管理主要分了3个链表：slabs_partial(部分空闲slab链表),非空闲slab链表（slabs_full）和全空闲slab链表(slabs_free)。struct kmem_cache_node还会将本地节点中需要节点共享的slab obj缓存在它的shared成员中。若本地节点向访问其他节点贡献的slab obj，可以利用struct kmem_cache_node中的alien成员去获取。
struct kmem_cache_node中成员share指向共享数组缓存，alien指向远程节点数组缓存，每个节点都有一个alien。这两个成员用来分阶段释放从其他节点进入的对象，先释放到alien，再释放到share，最后再到远程节点的slab。
分配和释放本地内存节点的对象时，也会使用共享数组缓存。分配对象时，如果当前处理器的数组缓存是空的，共享数组缓存里面的对象可以用于重填；释放对象时，如果当前处理器的数组缓存是满的，并且共享数组缓存有空闲空间，可以转移一部分对象到共享数组缓存，不需要把对象批量还给slab，然后把正在释放的对象添加到当前处理器的数组缓存中。

回收内存

对于所有对象空闲的slab，没有立即释放，而是放在空闲slab链表中。只有内存节点上空闲对象的数量超过限制，才开始回收空闲slab，直到空闲对象的数量小于或等于限制。
结构体kmem_cache_node的成员slabs_free是空闲slab链表的头节点，成员free_objects是空闲对象的数量，成员free_limit是空闲对象的数量限制。
此外，每个处理器每隔2秒针对内存缓存执行：

• 回收节点对应的远程节点数组缓存中的对象
• 如果过去2秒没有从当前处理器的数组缓存中分配对象，那么回收数组缓存中的对象

不连续页分配器

当设备长时间运行后，内存碎片化，很难找到连续的物理页。在这种情况下，如果需要分配长度超过一页的内存块，可以使用不连续页分配器，分配虚拟地址连续但是物理地址不连续的内存块。在32位系统中不连续分配器还有一个好处：优先从高端内存区域分配页，保留稀缺的低端内存区域。

数据结构

不连续页分配器的数据结构关系如下

每个虚拟内存区域对应一个vmap_area实例，每个vmap_area实例关联一个vm_struct实例。看代码

struct vm_struct {
	struct vm_struct	*next;  //指向下一个vm_struct实例
	void			*addr;  //起始的虚拟地址
	unsigned long		size;  //虚拟地址长度
	unsigned long		flags;  //标志
	struct page		**pages;  //page的指针数组
	unsigned int		nr_pages;  //页数
	phys_addr_t		phys_addr;  //起始物理地址
	const void		*caller;
};

struct vmap_area {
    //起始和结束的虚拟地址
	unsigned long va_start;
	unsigned long va_end;

	unsigned long flags;  //标志位
	struct rb_node rb_node;         /* address sorted rbtree */
    //指向vm_struct的链表（按虚拟地址从小到大排序）
	struct list_head list;          /* address sorted list */
	struct llist_node purge_list;    /* "lazy purge" list */
	struct vm_struct *vm;
	struct rcu_head rcu_head;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

函数接口

主要有以下几个重接口：

• vmalloc:分配不连续的物理页并且把物理页映射到连续的虚拟地址空间
• vfree:释放vmalloc分配的物理页和虚拟地址空间
• vmap:把已经分配的不连续物理页映射到连续的虚拟地址空间
• vunmap:释放使用vmap分配的虚拟地址空间

这里主要介绍一下vmalloc
vmalloc最终会调用__vmalloc_node_range，并把VMALLOC_START和VMALLOC_END传入，该函数是vmalloc的主要实现，用来从(start, end)中申请一段大小为size的虚拟地址空间，并给这块虚拟地址空间申请物理内存(基本是不连续的)，并写入页表。

static void *__vmalloc_node(unsigned long size, unsigned long align,
                gfp_t gfp_mask, pgprot_t prot, int node, const void *caller)
{
    return __vmalloc_node_range(size, align, VMALLOC_START, VMALLOC_END,
                gfp_mask, prot, 0, node, caller);
}

static inline void *__vmalloc_node_flags(unsigned long size, int node, gfp_t flags)
{
    return __vmalloc_node(size, 1, flags, PAGE_KERNEL,
                    node, __builtin_return_address(0));
}

/**
 *    vmalloc  -  allocate virtually contiguous memory
 *    @size:        allocation size
 *    Allocate enough pages to cover @size from the page level
 *    allocator and map them into contiguous kernel virtual space.
 *
 *    For tight control over page level allocator and protection flags
 *    use __vmalloc() instead.
 */
void *vmalloc(unsigned long size)
{
    return __vmalloc_node_flags(size, NUMA_NO_NODE, GFP_KERNEL | __GFP_HIGHMEM);
}
EXPORT_SYMBOL(vmalloc);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

从上面可以看出，vmalloc虚拟地址空间的范围是（VMALLOC_START,VMALLOC_END），每种处理器架构都需要定义这两个宏。如ARM64架构定义宏如下

/*
 * VMALLOC range.
 *
 * VMALLOC_START: beginning of the kernel vmalloc space
 * VMALLOC_END: extends to the available space below vmmemmap, PCI I/O space
 *	and fixed mappings
 */
/* MODULES_END内核模块区域的结束地址
 * PAGE_OFFSET线性映射区域的起始地址
 * PUD_SIZE页目录上层表项映射的地址空间长度
 * VMEMMAP_SIZE是vmemap区域的长度
 * VMALLOC_END: extends to the available space below vmmemmap, PCI I/O space
 *
 */
#define VMALLOC_START		(MODULES_END)
#define VMALLOC_END		(PAGE_OFFSET - PUD_SIZE - VMEMMAP_SIZE - SZ_64K)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

vmalloc函数执行过程：分配虚拟内存区域、分配物理页、在内核的页表中把虚拟页映射到物理页。
具体介绍一下。vmalloc函数分配的单位是页，如果请求分配的长度不是页的整数倍，就把长度向上对齐到页的整数倍。一般情况下，建议在申请内存长度超过一页时，一定要使用vmalloc函数，因为它的执行非常简单：

1. 分配虚拟内存区域：在vm_struct实例和vmap_area实例中遍历已存在的对应vmap_area实例，在两个实例之间找到一个足够大的空洞。如果找到，就把起始地址和结束地址保存到新的地址空间中，然后把新的vmap_area加入到红黑树或链表中，最后把新的实例关联到vm_struct中。
2. 分配物理页：从页分配器中分配一个物理页，把物理地址存放到pages指针数组中，再给nr_pages加1。
3. 在内核的页表中把虚拟页映射到物理页：将物理内存与虚拟内存一一建立映射，然后返回虚拟起始地址给用户，完成分配动作。

最后说一下进程内核页表的更新。从进程被创建时，除了复制一份父进程的页表还会复制一份内核页表。而内核页表必须保证每个进程使用的都是一样的，在 vmalloc 中，已经触发了内核页表的修改（所谓内核页表就是 init 进程的 mm_struct），那其他进程如何同步呢？

答案是通过缺页中断来实现延时同步。因为当其他进程想要访问新映射的 vmalloc 区虚拟地址时，由于其内核页表没更新，因此会匹配不到，触发缺页中断。进而此时再将修改的内核页表同步到该进程中即可。意味着如果没有使用到这部分地址，也不会触发内核页表同步。