kmalloc VS kmem_cache_alloc(ZZ)_儒雅_百度空间企业库|免费b2b网站

kmalloc VS kmem_cache_alloc(ZZ)_儒雅_百度空间

Linux内核为需要动态分配内存的内核程序提供了 kmalloc/kfree/kcalloc/krealloc函数接口，它们分别对应于C标准库的 malloc/free/calloc/krealloc。除此之外，Linux还提供了kmem_cache_xxx系列系统调用，以提供比上述接口更低的时间复杂度和空间复杂度，那么两者的效率究竟能差多少，它们又各自适合于何种场合呢？
为了保证灵活性，Linux内存分配系统是分层设计的，这种层次设计使得整个设计更加明晰，每个层次都能简单而有效地进行局部优化，所以一般也能提供更好的性能，当然扩展性也更好了，不然的出现就不可能那么轻松自然了。Linux内存系统自上而下分成以下几部分：

因为kmalloc是基于kmem_cache_create实现的，那么时间效率上kmalloc肯定是占不到任何便宜了，那么究竟能差多少呢？让我们先来看看相关代码：

    79 static inline void *kmalloc(size_t size, gfp_t flags)
80 {
81      if (__builtin_constant_p(size)) {
82          int i = 0;
83 #define CACHE(x) \
84          if (size <= x) \
85              goto found; \
86          else \
87              i++;
88 #include "kmalloc_sizes.h"
89 #undef CACHE
90          {
91              extern void __you_cannot_kmalloc_that_much(void);
92              __you_cannot_kmalloc_that_much();
93          }
94 found:
95          return kmem_cache_alloc((flags & GFP_DMA) ?
96              malloc_sizes[i].cs_dmacachep :
97              malloc_sizes[i].cs_cachep, flags);
98      }
99      return __kmalloc(size, flags);
100 }

出于效率上的考虑，上述函数为被声明为内联编译，81行的__builtin_constant_p是gcc的内建函数[]，它能够在编译时判定它的参数是否是编译时常量，如果是它将返回真，因为此函数为内联函数，并且__builtin_constant_p的参数为整型变量，所以判定仍有效。这也就意味着，如果你用如下方式调用kmalloc：

实际执行的将是82-79行的代码。为了能将这部分代码展开，我们不得不参考文件kmalloc_sizes.h的内容：

     1 #if (PAGE_SIZE == 4096)
2          CACHE(32)
3 #endif
4          CACHE(64)
5 #if L1_CACHE_BYTES < 64
6          CACHE(96)
7 #endif
8          CACHE(128)
9 #if L1_CACHE_BYTES < 128
10          CACHE(192)
11 #endif
12          CACHE(256)
13          CACHE(512)
14          CACHE(1024)
15          CACHE(2048)
16          CACHE(4096)
17          CACHE(8192)
18          CACHE(16384)
19          CACHE(32768)
20          CACHE(65536)
21          CACHE(131072)
22 #ifndef CONFIG_MMU
23          CACHE(262144)
24          CACHE(524288)
25          CACHE(1048576)
26 #ifdef CONFIG_LARGE_ALLOCS
27          CACHE(2097152)
28          CACHE(4194304)
29          CACHE(8388608)
30          CACHE(16777216)
31          CACHE(33554432)
32 #endif /* CONFIG_LARGE_ALLOCS */
33 #endif /* CONFIG_MMU */

代码展开后将是一系列的if-else语句块，顺序查找到最小的满足kmalloc大小要求的malloc_sizes的数组的索引。看到这里你也许会失望，顺序查找的时间复杂度不是O(n)么，既然malloc_sizes是数组，为啥不用更加高效的二分搜索呢？这个疑问先保留，不要忘了以上代码是 size为常量的时候才会被执行的，其中肯定存在某些玄机。如果size为常量，那么每个if语句的值在编译时就应该能被算出，汇编的结果也证实了我的猜想，不仅仅是i的值在编译时就被算了出来，就连cs_cachep和cs_dmacachep的偏移量也是编译时计算出来的，编译器的智能程度远远地超出了我的预期。

    movl    malloc_sizes+60, %eax ; 60就是编译时计算出来的。
andl    $-16, %esp
subl    $16, %esp
movl    %edx, 4(%esp)
movl    %eax, (%esp)
call    kmem_cache_alloc

需要指明的一点是，以上行为只有在打开编译器优化的时候才会起效，否则连inline函数它都不会展开。说起来，Linux内核和gcc编译器还真的是“狼狈为奸”好多年，连这点儿优化诡计都被利用上了。

从以上分析来看如果是申请固定大小的内存空间，kmalloc和kmem_cache_alloc时间效率相当。如果申请动态大小的空间，编译时优化是指望不上了，但是因为kmem_cache_alloc也只能申请固定大小的对象空间，所以也只能把kmalloc赶上架了。

哦，因为size不是常量，所以kmalloc将不会走以上分支，这时它调用__kmalloc：

void *__kmalloc(size_t size, gfp_t flags)
{
kmem_cache_t *cachep;

/* If you want to save a few bytes .text space: replace
* __ with kmem_.
* Then kmalloc uses the uninlined functions instead of the inline
* functions.
*/
cachep = __find_general_cachep(size, flags);
if (unlikely(cachep == NULL))
return NULL;
return __cache_alloc(cachep, flags);
}

static inline kmem_cache_t *__find_general_cachep(size_t size, gfp_t gfpflags)
{
struct cache_sizes *csizep = malloc_sizes;

#if DEBUG
/* This happens if someone tries to call
* kmem_cache_create(), or __kmalloc(), before
* the generic caches are initialized.
*/
BUG_ON(malloc_sizes[INDEX_AC].cs_cachep == NULL);
#endif
while (size > csizep->cs_size)
csizep++;

/*
* Really subtle: The last entry with cs->cs_size==ULONG_MAX
* has cs_{dma,}cachep==NULL. Thus no special case
* for large kmalloc calls required.
*/
if (unlikely(gfpflags & GFP_DMA))
return csizep->cs_dmacachep;
return csizep->cs_cachep;
}

看到顺序查找的代码是不是感觉挺差劲的？猜想它也是基于大多数内存块都不是很大这个事实，所以顺序查找的事实时间复杂度反而会比二分查找低。但是，这多少有些让人不爽，SLUB的代码针对这部分又做了优化，基于大多数内存块是按2^N大小连续分部这个事实，用查表加上位级别的大小对齐处理提高了时间效率。由于这部分与本文所讨论的东西关联不大，所以留给看客自己去分析吧！
除了时间复杂度，内存分配器的另外一个目标就是更好的空间复杂度，尽可能地减少内部碎片和外部碎片，充分利用已有内存空间。因为kmalloc所利用的内存块的大小是事先定义好的，所以很多情况下会产生内部碎片，浪费空间，而kmem_cache_alloc由于内存大小也是量身定做的缘故则不会。但是，有一点是kmem_cache_alloc所不能做到的，那就是动态大小的内存空间，这个任务是非kmalloc莫属。
kmem_cache_create的参数列表中还有构造函数和析构函数（SLUB中已经去掉了析构函数），对构造函数的支持也是Slab相对于其它内存分配器的优势，他能够避免对一块内存的重复初始化，从而提高效率，而kmalloc则不能。
动态创建固定大小的内存对象，虽然kmalloc的时间复杂度并不大，但是联系到空间复杂度，还是采用kmem_cache_alloc的好;而非固定大小的内存申请，只能经由kmalloc来解决。

郑重声明：资讯【kmalloc VS kmem_cache_alloc(ZZ)_儒雅_百度空间】由发布，版权归原作者及其所在单位，其原创性以及文中陈述文字和内容未经(企业库qiyeku.com)证实，请读者仅作参考，并请自行核实相关内容。若本文有侵犯到您的版权，请你提供相关证明及申请并与我们联系（qiyeku # qq.com）或【在线投诉】，我们审核后将会尽快处理。

—— 相关资讯 ——