2023-06-11  阅读(349)
原文作者:奇小葩 原文地址:https://blog.csdn.net/u012489236/category_9614673.html

在linux的内核运行需要动态分配内存的时候,其中有两种分配方案:

  • 第一种是以页为单位分配内存,即一次分配内存的大小必须是页的整数倍
  • 第二种是按需分配,一次分配的内存大小是随机的

对于第一种方案是通过伙伴系统实现,以页为单位管理和分配内存,但是这个单位确实也太大了。对于第二种方案,在现实的需求中,如果我们要为一个10个字符的字符串分配空间,如果按照伙伴系统采用分配一个4KB或者更多空间的完整页面,不仅浪费而且完全不可接受。显然的解决方案是需要将页拆分为更小的单位,可以容纳大量的小对象。同时新的解决方案月不能给内核带来更大的开销,不能对系统性能产生影响,同时也必须保证内存的利用率和效率。基于此,slab的分配器就应运而生,该机制是并没有脱离伙伴系统,是基于伙伴系统分配的大内存进一步细化分成小内存分配,SLAB 就是为了解决这个小粒度内存分配的问题的。

slab分配器对许多可能的工作负荷都能很好工作,但是有一些场景,也无法提供最优化的性能。如果某些计算机处于当前硬件尺度的边界上,slab分配器就会出现一些问题。同时对于嵌入式系统来说slab分配器代码量和复杂度都太高,所以内核增加了两个替代品,所以目前有三种实现算法,分别是slab、slub、slob,并且,依据它们各自的分配算法,在适用性方面会有一定的侧重。

  • Slab是最基础的,最早基于Bonwick的开创性论文并且可用 自Linux内核版本2.2起。
  • slob是被改进的slab,针对嵌入式系统进行了特别优化,以便减小代码量。围绕一个简单的内存块链表展开,在分配内存时,使用同样简单的最新适配算法。slob分配器只有大约600行代码,总的代码量很小。从速度来说,它不是最高效的分配器,页肯定不是为大型系统设计的。
  • slub是在slab上进行的改进简化,在大型机上表现出色,并且能更好的使用NUMA系统,slub相对于slab有5%-10%的性能提升和减小50%的内存占用

文章代码分析基于以linux-4.9.88,以NXP的IMX系列硬件,分析slub的工作原理。

1. slub数据结构

要想理解slub分配器,首先需要了解slub分配器的核心结构体,kmem_cache的结构体定义如下

    struct kmem_cache {
    	struct kmem_cache_cpu __percpu *cpu_slab;
    	/* Used for retriving partial slabs etc */
    	unsigned long flags;
    	unsigned long min_partial;
    	int size;		/* The size of an object including meta data */
    	int object_size;	/* The size of an object without meta data */
    	int offset;		/* Free pointer offset. */
    	int cpu_partial;	/* Number of per cpu partial objects to keep around */
    	struct kmem_cache_order_objects oo;
    
    	/* Allocation and freeing of slabs */
    	struct kmem_cache_order_objects max;
    	struct kmem_cache_order_objects min;
    	gfp_t allocflags;	/* gfp flags to use on each alloc */
    	int refcount;		/* Refcount for slab cache destroy */
    	void (*ctor)(void *);
    	int inuse;		/* Offset to metadata */
    	int align;		/* Alignment */
    	int reserved;		/* Reserved bytes at the end of slabs */
    	const char *name;	/* Name (only for display!) */
    	struct list_head list;	/* List of slab caches */
    	int red_left_pad;	/* Left redzone padding size */
    	struct kmem_cache_node *node[MAX_NUMNODES];
    }
结构体成员变量 含义
cpu_slab 一个percpu变量,对于每个cpu来说,相当于一个本地内存缓存池。当分配内存的时候优先从本地cpu分配内存以保证cache的命中率。
flags object分配掩码
min_partial 限制structkmem_cache_node中的partial链表slab的数量。如果大于这个mini_partial的值,那么多余的slab就会被释放。
size 分配的objectsize
object_size 实际的objectsize
offset offset就是存储下个object地址数据相对于这个object首地址的偏移。
cpu_partial percpupartial中所有slab的freeobject的数量的最大值,超过这个值就会将所有的slab转移到kmem_cache_node的partial链表
oo oo用来存放分配给slub的页框的阶数(高16位)和slub中的对象数量(低16位)
min 当按照oo大小分配内存的时候出现内存不足就会考虑min大小方式分配。min只需要可以容纳一个object即可。
allocflags 从伙伴系统分配内存掩码。
list 有一个slab_caches链表,所有的slab都会挂入此链表。
node slab节点。在NUMA系统中,每个node都有一个structkmem_cache_node数据结构

在该结构体中,有一个变量struct list_head list,可以想象下,对于操作系统来讲,要创建和管理的缓存不至于task_struct,对于mm_struct,fs_struct都需要这个结构体,所有的缓存最后都会放到这个链表中,也就是LIST_HEAD(slab_caches)。对于缓存中哪些对象被分配,哪些是空着,什么情况下整个大内存块都被分配完了,需要向伙伴系统申请几个页形成新的大内存块?这些信息该由谁来维护呢??就引出了两个成员变量kmem_cache_cpu和kmem_cache_node。

在分配缓存的时候,需要分两种路径,快速通道(kmem_cache_cpu)和普通通道(kmem_cache_node),每次分配的时候,要先从kmem_cache_cpu分配;如果kmem_cache_cpu里面没有空闲块,那就从kmem_cache_node中进行分配;如果还是没有空闲块,最后从伙伴系统中分配新的页。

cpu_cache对于每个CPU来说,相当于一个本地内存缓冲池,当分配内存的时候,优先从本地CPU分配内存以及保证cache的命中率,struct kmem_cache_cpu用于管理slub缓存

    struct kmem_cache_cpu {
    	void **freelist;	/* Pointer to next available object */
    	unsigned long tid;	/* Globally unique transaction id */
    	struct page *page;	/* The slab from which we are allocating */
    	struct page *partial;	/* Partially allocated frozen slabs */
    #ifdef CONFIG_SLUB_STATS
    	unsigned stat[NR_SLUB_STAT_ITEMS];
    #endif
    };
结构体成员变量 含义
freelist 指向本地CPU的第一个空闲对象,这一项会有指针指向下一个空闲的项,最终所有空闲的项会形成一个链表
tid 主要用来同步
page 指向大内存块的第一个页,缓存块就是从里面分配的
partial 大内存块的第一个页,之所以名字叫partial(部分),就是因为它里面部分被分配出去了,部分是空的。这是一个备用列表,当page满了,就会从这里找

struct kmem_cache_node:用于管理每个Node的slub页面,由于每个Node的访问速度不一致,slub页面由Node来管理;

    struct kmem_cache_node {
    	spinlock_t list_lock;
    #ifdef CONFIG_SLUB
    	unsigned long nr_partial;               /* partial slab链表中slab的数量 */
    	struct list_head partial;               /* partial slab链表表头 */
    #ifdef CONFIG_SLUB_DEBUG
    	atomic_long_t nr_slabs;                 /* 节点中的slab数 */  
    	atomic_long_t total_objects;            /* 节点中的对象数 */  
    	struct list_head full;                  /* full slab链表表头 */  
    #endif
    #endi
    }
结构体成员变量 含义
list_lock 自旋锁,保护数据
nr_partial partialslab链表中slab的数量
partial 这个链表里存放的是部分空闲的大内存块。这是kmem_cache_cpu里面的partial的备用列表,如果那里没有,就到这里来找。

其结构图如下图所示

202306111243029041.png

2. 初始化

为了初始化slub的数据结构,内核需要若干远小于一整页的内存块,这些最适合使用kmalloc来分配。但是此时只有slub系统已经完成初始化后,才能使用kmalloc。换而言之,kmalloc只能在kmalloc已经初始化之后初始化,这个是不可能,所以内核使用kmem_cache_init函数用于初始化slub分配器。
分配器的初始化工作主要是初始化用于kmalloc的gerneral cache,slub分配器的gerneral cache定义如下:

    extern struct kmem_cache *kmalloc_caches[KMALLOC_SHIFT_HIGH + 1];
    #define KMALLOC_SHIFT_HIGH	(PAGE_SHIFT + 1)
    #define PAGE_SHIFT  12 
    //(各个架构下的定义都有些差异,如果是arm64,那么是通过CONFIG_ARM64_PAGE_SHIFT来指定的,这个配置项在arch/arm64/Kconfig文件中定义,默认为12,也就是默认页面大小为4KiB,笔者以arm64为例)

那么KMALLOC_SHIFT_HIGH=PAGE_SHIFT + 1 = 12 + 1 = 13,KMALLOC_SHIFT_HIGH+1=13+ 1= 14说明kmalloc_caches数组中有14个元素,每个元素是kmem_cache这个结构体

它在内核初始化阶段(start_kernel)、伙伴系统启用之后调用,它首先执行缓存初始化过程,如下图所示

202306111243047272.png

  • 从缓存中分配kmem_cache对象,并复制并使用临时kmem_cache
  • 从缓存中分配kmem_cache_node对象,然后复制并使用临时使用的kmem_cache_node
  • kmalloc boot cache

起初并没有boot cache,因此定义了两个静态变量(boot_kmem_cache,boot_kmem_cache_node)用于临时使用。这里的核心是boot cache创建函数:create_boot_cache()

202306111243055183.png

当调用create_boot_cache创建完kmem_cache和kmem_cache_node两个Cache后,就需要调用bootstrap从Cache中为kmem_cache和kmem_cache_node分配内存空间然后将静态变量boot_kmem_cache和boot_kmem_cache_node中的内容复制到分配的内存空间中,这相当于完成了一次对自身的重建。

    static struct kmem_cache * __init bootstrap(struct kmem_cache *static_cache)
    {
    	int node;
    	struct kmem_cache *s = kmem_cache_zalloc(kmem_cache, GFP_NOWAIT);                                        --------------------(1)
    	struct kmem_cache_node *n;
    
    	memcpy(s, static_cache, kmem_cache->object_size);
    
    	/*
    	 * This runs very early, and only the boot processor is supposed to be
    	 * up.  Even if it weren't true, IRQs are not up so we couldn't fire
    	 * IPIs around.
    	 */
    	__flush_cpu_slab(s, smp_processor_id());
    	for_each_kmem_cache_node(s, node, n) {                                                                   --------------------(2)
    		struct page *p;
    
    		list_for_each_entry(p, &n->partial, lru)
    			p->slab_cache = s;
    
    #ifdef CONFIG_SLUB_DEBUG
    		list_for_each_entry(p, &n->full, lru)
    			p->slab_cache = s;
    #endif
    	}
    	slab_init_memcg_params(s);
    	list_add(&s->list, &slab_caches);
    	return s;
    }
  • 1.首先将会通过kmem_cache_zalloc()申请kmem_cache空间,值得注意的是该函数申请调用kmem_cache_zalloc()->kmem_cache_alloc()->slab_alloc(),其最终将会通过前面create_boot_cache()初始化创建的kmem_cache来申请slub空间来使用。临时使用的kmem_cache结构形式接收的参数static_cache的内容复制到新分配的缓存中,其大小与object_size相同。早期引导过程中,因此无法对其他CPU进行IPI调用,因此仅刷新本地CPU。

  • 2.通过for_each_node_state()遍历各个内存管理节点node,在通过get_node()获取对应节点的slab,如果slab不为空这回遍历部分满slab链,修正每个slab指向kmem_cache的指针,如果开启CONFIG_SLUB_DEBUG,则会遍历满slab链,设置每个slab指向kmem_cache的指针;最后将kmem_cache添加到全局slab_caches链表中。

    接下来是创建kmalloc boot cache - create_kmalloc_caches(),来初始化kmalloc_caches表,其最终创建的kmalloc_caches是以{0,96,192,8,16,32,64,128,256,512,1024,2046,4096,8196}为大小的slab表;创建完之后,将设置slab_state为UP,然后将kmem_cache的name成员进行初始化;最后如果配置了CONFIG_ZONE_DMA,将会初始化创建kmalloc_dma_caches表。可以得到size_index与kmalloc_caches的对应关系

202306111243061014.png

我们以通常情况下KMALLOC_MIN_SIZE等于8为例进行说明。size_index[0-23]数组根据对象大小映射到不同的kmalloc_caches[0-13]保存的cache。观察kmalloc_caches[0-13]数组,可见索引即该cache slab块的order。由于最小对象为8(23)字节,kmalloc_caches[0-2]这三个数组元素没有用到,slub使用kmalloc_caches[1]保存96字节大小的对象,kmalloc_caches[2] 保存192字节大小的对象,相当于细分了kmalloc的粒度,有利于减少空间的浪费。kmalloc_caches[0]未使用。

3. 总结

slab分配器中用到了对象这个概念,就是内核中的数据结构以及对该数据结构进行创建和撤销的操作。其核心思想如下

  • 将内核中经常使用的对象放到高速缓存中,并且由系统保持为初始的可利用状态,比如进程描述符,内核中会频繁对此数据进行申请和释放
  • 当一个新进场创建时,内核就会直接从slab分配器的高速缓存中获取一个已经初始化的对象
  • 当进程结束时,该结构所占的页框并不被释放,而是重新返回slab分配器中,如果没有基于对象的slab分配器,内核将花费更多的时间去分配、初始化、已经释放对象。

202306111243084745.png

上图显示了slab、cache及object 三者之间的关系。该图显示了2个大小为3KB 的内核对象和3个大小为7KB的对象,它们位于各自的cache中。slab分配算法采用 cache来存储内核对象。在创建 cache 时,若干起初标记为free的对象被分配到 cache。cache内的对象数量取决于相关slab的大小。例如,12KB slab(由3个连续的4KB页面组成)可以存储6个2KB对象。最初,cache内的所有对象都标记为空闲。当需要内核数据结构的新对象时,分配器可以从cache上分配任何空闲对象以便满足请求。从cache上分配的对象标记为used(使用)。

让我们考虑一个场景,这里内核为表示进程描述符的对象从slab分配器请求内存。在 Linux 系统中,进程描述符属于 struct task_struct 类型,它需要大约1.7KB的内存。当Linux内核创建一个新任务时,它从cache中请求 struct task_struct对象的必要内存。cache 利用已经在slab中分配的并且标记为 free (空闲)的 struct task_struct对象来满足请求。
在Linux中,slab可以处于三种可能状态之一:

  • 满的:slab的所有对象标记为使用。
  • 空的:slab上的所有对象标记为空闲。
  • 部分:slab上的对象有的标记为使用,有的标记为空闲。

slab分配器首先尝试在部分为空的slab中用空闲对象来满足请求。如果不存在,则从空的slab 中分配空闲对象。如果没有空的slab可用,则从连续物理页面分配新的slab,并将其分配给cache;从这个slab上,再分配对象内存。slab分配器提供两个主要优点:

  • 减小伙伴算法在分配小块连续内存时所产生的内部碎片问题,因为每个内核数据结构都有关联的cache,每个 cache都由一个或多个slab组成,而slab按所表示对象的大小来分块。因此,当内核请求对象内存时,slab 分配器可以返回刚好表示对象的所需内存。
  • 将频繁使用的对象缓存起来,减小分配、初始化和释放的时间开销 ,当对象频繁地被分配和释放时,如来自内核请求的情况,slab 分配方案在管理内存时特别有效。分配和释放内存的动作可能是一个耗时过程。然而,由于对象已预先创建,因此可以从cache 中快速分配。再者,当内核用完对象并释放它时,它被标记为空闲并返回到cache,从而立即可用于后续的内核请求。

对于伙伴系统和slab分配器,就好比“批发商”和“零售商”,“批发商”,是指按页面管理并分配内存的机制;而“零售商”,则是从“批发商”那里批发获取资源,并以字节为单位,管理和分配内存的机制。作为零售商的slab,那么就需要解决两个问题

  • 该如何从批发商buddy system批发内存
  • 如何管理批发的内存并把这些内存“散卖“出去,如何使这些散内存由更高的使用效率

4. 参考文档

趣谈Linux操作系统
Linux内存管理:slub分配器
操作系统内存分配算法_操作系统基础45-伙伴系统和slab内存分配

阅读全文
  • 点赞