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

内核管理页面使用了2个算法:伙伴算法和slub算法,伙伴算法以页为单位管理内存,但在大多数情况下,程序需要的并不是一整页,而是几个、几十个字节的小内存。于是需要另外一套系统来完成对小内存的管理,这就是slub系统。slub系统运行在伙伴系统之上,为内核提供小内存管理的功能。

slub把内存分组管理,每个组分别包含 8、64、512、…2048个字节,在4K页大小的默认情况下,另外还有两个特殊的组,分别是96B和192B,共11组。之所以这样分配是因为如果申请2^12B大小的内存,就可以使用伙伴系统提供的接口直接申请一个完整的页面即可。

slub就相当于零售商,它向伙伴系统“批发”内存,然后在零售出去。一下是整个slub系统的框图:

202306111243123171.png

一切的一切源于kmalloc_caches[12]这个数组,该数组的定义如下:

    struct kmem_cache *kmalloc_caches[KMALLOC_SHIFT_HIGH + 1];

每个数组元素对应一种大小的内存,可以把一个kmem_cache结构体看做是一个特定大小内存的零售商,整个slub系统中共有12个这样的零售商,每个“零售商”只“零售”特定大小的内存,例如:有的“零售商”只"零售"8Byte大小的内存,有的只”零售“16Byte大小的内存。

每个零售商(kmem_cache)有两个“部门”,一个是“仓库”:kmem_cache_node,一个“营业厅”:kmem_cache_cpu。“营业厅”里只保留一个slab,只有在营业厅(kmem_cache_cpu)中没有空闲内存的情况下才会从仓库中换出其他的slab。
所谓slab就是零售商(kmem_cache)批发的连续的整页内存,零售商把这些整页的内存分成许多小内存,然后分别“零售”出去,一个slab可能包含多个连续的内存页。slab的大小和零售商有关。

1. slub的分配原理

slub管理器从伙伴系统哪里每次批发2^order个页面,之后这些物理页面被按照对象大小(objsize)组织成单向链表。由于单项链表的指针要分配额外的存储空间,所以一个对象的实际大小要大约分配给程序使用的大小。kmem_cache中的size就表示实际大小,而objsize表示分配出去可以使用的大小。在多CPU的系统中,为了防止过多使用自旋锁带来的性能开销,每一个CPU有一个kmem_cache_cpu结构,仓库中货物主要是通过kmem_cache_cpu结构管理。oid*指向的是下一个空闲的object的首地址,这样object就连成了一个单链表。

202306111243136692.png

  • slub系统刚刚创建处理,第一次申请slub内存

    此时slub系统刚刚建立起来,营业厅(kmem_cache_cpu)和仓库(kmem_cache_node)中没有任何可用的slub可以使用,此时只能向伙伴同中申请可用的内存项,并把这些页面分成很多的object,取出其中一个object标志为已被占用,并返回给用户,其余的object标志为空闲并放在kmem_cache_cpu中保存。

  • slub的kmem_cache_cpu中保存的slab上有空闲的object可以使用

    直接把kmem_cache_cpu中保存的一个空闲object返回给用户,并把freelist指向下一个空闲的object

  • kmem_cache_cpu中已经没有空闲的object了,但kmem_cache_node的partial中有空闲的object

    从kmem_cache_node的partial变量中获取有空闲object的slab,并把一个空闲的object返回给用户

  • 在kmem_cache_cpu和kmem_cache_node中都没有空闲页面了

    slub已经连续申请了很多页,现在kmem_cache_cpu中保存的物理页面上已经没有空闲的object可以使用了,而此时kmem_cache_node中也没有空闲页面了,只能向内存管理器(伙伴系统)申请slub,并把该slub初始化,返回第一个obect

向slub系统释放内存块(object)时,如果kmem_cache_cpu中缓存的slab就是该object所在的slab,则把该object放在空闲链表中即可,如果kmem_cache_cpu中缓存的slab不是该object所在的slab,然后把该object释放到该object所在的slab中。在释放object的时候可以分为一下三种情况:

  • object在释放之前slab是full状态的时候(slab中的object都是被占用的),释放该object后,这是该slab就是半满(partail)的状态了,这时需要把该slab添加到kmem_cache_node中的partial链表中。
  • slab是partial状态时(slab中既有object被占用,又有空闲的),直接把该object加入到该slab的空闲队列中即可。
  • 该object在释放后,slab中的object全部是空闲的,还需要把该slab释放掉。

在分配缓存块的时候,要分两种路径, fast pathslow path ,也就是 快速通道普通通道 。其中 kmem_cache_cpu 就是快速通道,kmem_cache_node 是普通通道。每次分配的时候,要先从 kmem_cache_cpu 进行分配。如果 kmem_cache_cpu 里面没有空闲的块,那就到 kmem_cache_node 中进行分配;如果还是没有空闲的块,才去伙伴系统分配新的页。

2. slub分配和释放API

202306111243142793.png

对于内核的申请内存,有两种方式,一种是通过伙伴系统申请page allocator,一种是通过slab allocatorr,对于内核有驱动模块,文件系统等方式会申请内存。其主要的方式有两种

  • 提供特定类型的内核缓存方式

    内核为专用高速缓存的申请和释放提供了一套完整的接口,根据所传入的参数为具体的对象分配 slab 缓存kmem_cache_create() 用于对一个指定的对象创建高速缓存。它从 cache_cache 普通高速缓存中为新的专有缓存分配一个高速缓存描述符,并把这个描述符插入到高速缓存描述符形成的 cache_chain 链表中kmem_cache_alloc() 在其参数所指定的高速缓存中分配一个 slab。相反, kmem_cache_free() 在其参数所指定的高速缓存中释放一个 slab

        struct kmem_cache *kmem_cache_create(const char *, size_t, size_t,---------创建slab描述符kmem_cache,此时并没有真正分配内存
                    unsigned long, void (*)(void *));
        void *kmem_cache_alloc(struct kmem_cache *, gfp_t flags);------------------分配slab缓存对象
        void kmem_cache_free(struct kmem_cache *, void *);-------------------------释放slab缓存对象
        void kmem_cache_destroy(struct kmem_cache *);-----------------------------销毁slab描述符
        
    
  • 供一般的内存分配方式,适合于所有的device drivers

    kmalloc(size,flags)分配长度为size字节的一个内存区,并返回指向该内存区起始处的一个void指针,如果没有足够内存,则结果为NULL指针
    kfree(*ptr)释放 *ptr指向的内存区

3. kmalloc分配函数

内核常用的kmalloc函数的核心是slab机制,按照内存块的2^order来创建多个slab描述符,例如16B/32B…等大小,系统启动的时候在create_kmalloc_caches函数中完成。我们主要来看看kmalloc的实现

    static __always_inline void *kmalloc(size_t size, gfp_t flags)
    {
    	if (__builtin_constant_p(size)) {                                                              
    		if (size > KMALLOC_MAX_CACHE_SIZE)
    			return kmalloc_large(size, flags);
    #ifndef CONFIG_SLOB
    		if (!(flags & GFP_DMA)) {
    			int index = kmalloc_index(size);
    
    			if (!index)
    				return ZERO_SIZE_PTR;
    
    			return kmem_cache_alloc_trace(kmalloc_caches[index],
    					flags, size);
    		}
    #endif
    	}
    	return __kmalloc(size, flags);
    }
  • 当超过KMALLOC_MAX_CACHE_SIZE(如果为slub,则为2页),则使用伙伴系统从kmalloc_large页面分配器分配页面,_builtin_constant_p(exp)是gcc的内建函数,用于判断一个值是否为编译时常数,如果参数exp的值是常数,函数返回 1,否则返回 0。就是说,如果size不是常数,就调用__kmalloc(size, flags);去处理
  • kmalloc_index()函数按大小计算索引值,然后调用kmem_cache_alloc_trace分配
    static __always_inline int kmalloc_index(size_t size)
    {
    	if (!size)
    		return 0;
    
    	if (size <= KMALLOC_MIN_SIZE)
    		return KMALLOC_SHIFT_LOW;
    
    	if (KMALLOC_MIN_SIZE <= 32 && size > 64 && size <= 96)
    		return 1;
    	if (KMALLOC_MIN_SIZE <= 64 && size > 128 && size <= 192)
    		return 2;
    	if (size <=          8) return 3;
    	if (size <=         16) return 4;
    	if (size <=         32) return 5;
    	if (size <=         64) return 6;
    	if (size <=        128) return 7;
    	if (size <=        256) return 8;
    	if (size <=        512) return 9;
    	if (size <=       1024) return 10;
    	if (size <=   2 * 1024) return 11;
    	if (size <=   4 * 1024) return 12;
    	if (size <=   8 * 1024) return 13;
    	if (size <=  16 * 1024) return 14;
    	if (size <=  32 * 1024) return 15;
    	if (size <=  64 * 1024) return 16;
    	if (size <= 128 * 1024) return 17;
    	if (size <= 256 * 1024) return 18;
    	if (size <= 512 * 1024) return 19;
    	if (size <= 1024 * 1024) return 20;
    	if (size <=  2 * 1024 * 1024) return 21;
    	if (size <=  4 * 1024 * 1024) return 22;
    	if (size <=  8 * 1024 * 1024) return 23;
    	if (size <=  16 * 1024 * 1024) return 24;
    	if (size <=  32 * 1024 * 1024) return 25;
    	if (size <=  64 * 1024 * 1024) return 26;
    	BUG();
    
    	/* Will never be reached. Needed because the compiler may complain */
    	return -1;
    }

根据0到64M或更小的请求大小返回索引,为0到23之间的数字。如果超过64M,则返回-1作为错误。

根据请求大小的索引值

  • 0 =无分配(零分配)

  • 1 = 65 … 96字节

  • 2 = 120 … 192字节

  • n = 2 ^(n-1)… 2 ^ n -1

    • 3 = 1 … 8
    • 4 = 9 … 16
    • 5 = 17 … 32
    • 6 = 33 … 64
    • 26 = 32M-1 … 64M
  • 但是,如果大小为1〜KMALLOC_MIN_SIZE,则返回KMALLOC_SHIFT_LOW。

    • rpi2示例)KMALLOC_MIN_SIZE = 64,KMALLOC_SHIFT_LOW = 6
    • arm64 ex)KMALLOC_MIN_SIZE = 128,KMALLOC_SHIFT_LOW = 7

下面我们来看看__kmalloc,其处理流程如下:

    void *__kmalloc(size_t size, gfp_t flags)
    {
    	struct kmem_cache *s;
    	void *ret;
    
    	if (unlikely(size > KMALLOC_MAX_CACHE_SIZE))
    		return kmalloc_large(size, flags);
    
    	s = kmalloc_slab(size, flags);
    
    	if (unlikely(ZERO_OR_NULL_PTR(s)))
    		return s;
    
    	ret = slab_alloc(s, flags, _RET_IP_);
    
    	trace_kmalloc(_RET_IP_, ret, size, s->size, flags);
    
    	kasan_kmalloc(s, ret, size, flags);
    
    	return ret;
    }
  • 如果超过KMALLOC_MAX_CACHE_SIZE(如果为slub,则为2页),则使用伙伴系统通过kmalloc_large()函数从页面分配器分配页面。
  • 检索适当的kmalloc slab缓存
  • 获得kmalloc缓存中分配的。
    struct kmem_cache *kmalloc_slab(size_t size, gfp_t flags)
    {
    	int index;
    
    	if (unlikely(size > KMALLOC_MAX_SIZE)) {                                                --------------------------(1)
    		WARN_ON_ONCE(!(flags & __GFP_NOWARN));
    		return NULL;
    	}
    
    	if (size <= 192) {                                                                     ---------------------------(2)
    		if (!size)
    			return ZERO_SIZE_PTR;
    
    		index = size_index[size_index_elem(size)];
    	} else
    		index = fls(size - 1);
    
    #ifdef CONFIG_ZONE_DMA                                                                      -------------------------(3)
    	if (unlikely((flags & GFP_DMA)))
    		return kmalloc_dma_caches[index];
    
    #endif
    	return kmalloc_caches[index];
    }
  • size为1至192,则使用已创建的size_index []表来计算索引,193至KMALLOC_MAX_SIZE(对于slub,则为2页),则将计算并返回所需的位数。
        193〜256→8
        257〜512→9
        513〜1024 → 10
        1025〜2048 → 11
        2049〜4096 → 12
        4097〜8192 → 13
  • 最后如果开启了DMA内存配置且设置了GFP_DMA标志,将结合索引值通过kmalloc_dma_caches返回kmem_cache管理结构信息,否则将通过kmalloc_caches返回该结构。

由此可以看出kmalloc()实现较为简单,起分配所得的内存不仅是虚拟地址上的连续存储空间,同时也是物理地址上的连续存储空间。

slab(或slub/slob)对内存进行了二次管理,使系统可以申请小块内存。Slab先从buddy拿到数个页的内存,然后切成固定的小块(称为object),再分配出去。从/proc/slabinfo中可以看到系统内有很多slab,每个slab管理着数个页的内存,它们可分为两种:一个是各模块专用的,一种是通用的。

  • 一类是内核里常用的数据结构,如TCPv6,UDPv6等,由于内核经常要申请和释放这类数据结构,所以就针对这些数据结构做一个slab,然后再次申请这类结构体时就总是从这个slab里来申请一个object(使用kmem_cache_alloc()申请)。
  • 另一类是一些小粒度的内存申请,如slabinfo中的kmalloc-16,kmalloc-32等(使用kmalloc()申请)。
阅读全文