学习 Linux 内核内存分配算法,简单查阅了一下相关的内核源码和收集了部分资料(大部分资料来源于广大网友)。
1. 设备
- 设备关系。
图片来源:《深入理解计算机系统》- 第一章 - 计算机漫游
- 存储关系。
图片来源:《深入理解计算机系统》- 第一章 - 计算机漫游
2. 内存布局
- 存储。
图片来源:《深入理解计算机系统》- 第一章 - 计算机漫游
- 模型:node - 存储节点;zone - 管理区;page - 页面。
图片来源:Linux 内存管理窥探(2):内存模型
图片来源:Linux 内存管理窥探(2):内存模型
- 虚拟内存。
图片来源:《深入理解计算机系统》- 第九章 - 虚拟内存
- MMU 地址翻译。
图片来源:《深入理解计算机系统》- 第九章 - 虚拟内存
图片来源:初探 MMU
- 页表分页机制。
3. 内存分配算法
Linux 系统内存分配流程。
3.1. buddy - 伙伴算法
伙伴算法分配内存最小单位页(page)。缺点:分配粒度大。
3.1.1. 分配源码
1
alloc_pages ->alloc_pages_node ->__alloc_pages -> __alloc_pages_nodemask -> get_page_from_freelist -> zone_watermark_ok -> rmqueue -> __rmqueue_smallest
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* gfp.h */
#define alloc_pages(gfp_mask, order) \
alloc_pages_node(numa_node_id(), gfp_mask, order)
/*
* Allocate pages, preferring the node given as nid. When nid == NUMA_NO_NODE,
* prefer the current CPU's closest node. Otherwise node must be valid and
* online.
*/
static inline struct page *alloc_pages_node(int nid, gfp_t gfp_mask, unsigned int order) {
if (nid == NUMA_NO_NODE)
nid = numa_mem_id();
return __alloc_pages_node(nid, gfp_mask, order);
}
4. slab 内存分配算法
因为 buddy 分配内存粒度大,不能高效满足小内存分配,所以引入了 slab 算法。
算法讲解得比较详细的,参考这两篇帖子:
4.1. 概述
- slab 算法框架。
4.2. 使用
参考内核 epoll 源码是实现,epoll 通过一颗红黑树管理监控的 fd 节点,节点通过 slab 接口管理内存。
- 初始化。
1
2
3
4
5
6
7
8
9
10
11
/* Slab cache used to allocate "struct epitem" */
static struct kmem_cache *epi_cache __read_mostly;
static int __init eventpoll_init(void) {
...
/* Allocates slab cache used to allocate "struct epitem" items */
epi_cache = kmem_cache_create(
"eventpoll_epi", sizeof(struct epitem), 0,
SLAB_HWCACHE_ALIGN | SLAB_PANIC | SLAB_ACCOUNT, NULL);
...
}
- 插入节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
* Must be called with "mtx" held.
*/
static int ep_insert(struct eventpoll *ep, const struct epoll_event *event,
struct file *tfile, int fd, int full_check) {
...
struct epitem *epi;
...
if (!(epi = kmem_cache_alloc(epi_cache, GFP_KERNEL)))
return -ENOMEM;
...
error_create_wakeup_source:
kmem_cache_free(epi_cache, epi);
return error;
}
- 删除节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
* Removes a "struct epitem" from the eventpoll RB tree and deallocates
* all the associated resources. Must be called with "mtx" held.
*/
static int ep_remove(struct eventpoll *ep, struct epitem *epi) {
...
call_rcu(&epi->rcu, epi_rcu_free);
...
}
static void epi_rcu_free(struct rcu_head *head) {
struct epitem *epi = container_of(head, struct epitem, rcu);
kmem_cache_free(epi_cache, epi);
}
5. 引用
- alloc_page分配内存空间–Linux内存管理(十七)
- [2015 SP] 北京大学 Principles of Operating System 操作系统原理 by 陈向群 - 伙伴系统
- slab分配器–Linux内存管理(二十二)
- linux 内核 内存管理 slub算法 (一) 原理
- Linux内核伙伴算法和Slab分配器
- Linux内存管理之SLAB原理浅析。
- linux内核开发第22讲:页框和伙伴算法以及slab机制
- linux内核开发第23讲:linux内核内存管理和分配方法概述
- linux内核开发第24讲:kmalloc()的内核源码实现
- linux内核开发第25讲:kmalloc()分析之高速缓存和size的对应关系
- 【os浅尝】话说虚拟内存~
- Linux C 进程内存布局探索(2) 堆内存从 sbrk 到 malloc 及 free
- Linux C 进程内存布局探索(1) 进程内存布局基础与栈及 ASLR
- gdb带源码调试libc
- Linux内核内存管理算法Buddy和Slab
- 一次 Java 进程 OOM 的排查分析(glibc 篇)
- Linux下禁止使用swap及防止OOM机制导致进程被kill掉
- OOM和Swap分区
- Linux内核必读五本书籍(强烈推荐)
- Linux服务端swap配置和监控
- 操作系统中的多级页表到底是为了解决什么问题?
- Linux是几级页表?
- Linux四级页表及其原理
- 线程切换与进程切换以及开销
- 操作系统原理:第48讲,地址转换过程及TLB的引入
- 为何要内存对齐
- 利用CPU缓存实现高性能程序
- 伙伴系统内存分配算法
- 伙伴算法和Slab机制
- Glibc 的malloc源代码分析
- linux内核开发第10讲:x86段页式内存管理和页表映射机制
- Linux内核伙伴算法和Slab分配器