学习 Linux 内存分配

2021-04-19

学习 Linux 内核内存分配算法,简单查阅了一下相关的内核源码和收集了部分资料(大部分资料来源于广大网友)。


1. 设备

  • 设备关系。

图片来源:《深入理解计算机系统》- 第一章 - 计算机漫游

  • 存储关系。

图片来源:《深入理解计算机系统》- 第一章 - 计算机漫游


2. 内存布局

  • 存储。

图片来源:《深入理解计算机系统》- 第一章 - 计算机漫游

  • 模型:node - 存储节点;zone - 管理区;page - 页面。

图片来源:Linux 内存管理窥探(2):内存模型

图片来源:Linux 内存管理窥探(2):内存模型

  • 虚拟内存。

图片来源:Linux 内存管理窥探(1):内存规划与分布

图片来源:Linux 内存管理窥探(1):内存规划与分布

图片来源:《深入理解计算机系统》- 第九章 - 虚拟内存

  • MMU 地址翻译。

图片来源:《深入理解计算机系统》- 第九章 - 虚拟内存

图片来源:初探 MMU

  • 页表分页机制。

3. 内存分配算法

Linux 系统内存分配流程。

图片来源:Linux内核内存管理算法Buddy和Slab


3.1. buddy - 伙伴算法

伙伴算法分配内存最小单位页(page)。缺点:分配粒度大。

图片来源:Linux内核内存管理算法Buddy和Slab


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 算法框架。

图片来源:Linux内核内存管理算法Buddy和Slab

图片来源:linux 内核 内存管理 slub算法 (一) 原理


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. 引用