Chinaunix首页 | 论坛 | 博客
  • 博客访问: 325404
  • 博文数量: 78
  • 博客积分: 1322
  • 博客等级: 中尉
  • 技术积分: 680
  • 用 户 组: 普通用户
  • 注册时间: 2010-04-14 13:24
文章分类
文章存档

2012年(20)

2011年(55)

2010年(3)

分类:

2011-10-10 14:57:56

原文地址:kmalloc VS kmem_cache_alloc 作者:xiaosuo

Linux内核为需要动态分配内存的内核程序提供了kmalloc/kfree/kcalloc/krealloc函数接口,它们分别对应于C标准库的malloc/free/calloc/krealloc。除此之外,Linux还提供了kmem_cache_xxx系列系统调用,以提供比上述接口更低的时间复杂度和空间复杂度,那么两者的效率究竟能差多少,它们又各自适合于何种场合呢?

Linux内存系统的层次结构

为了保证灵活性,Linux内存分配系统是分层设计的,这种层次设计使得整个设计更加明晰,每个层次都能简单而有效地进行局部优化,所以一般也能提供更好的性能,当然扩展性也更好了,不然的出现就不可能那么轻松自然了。Linux内存系统自上而下分成以下几部分:

单位
接口 算法
动态大小
kmalloc/kfree/krealloc/kcalloc  按大小组织的缓存数组
固定大小
kmem_cache_create/kmem_cache_destroy
kmem_cache_alloc/kmem_cache_free
Slab[2]
2^n页alloc_pages/free_pages
__get_free_pages/__free_pages
伙伴算法

kmalloc相对于kmem_cache_alloc的时间复杂度

因为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:

ptr = kmalloc(128, GTP_KERNEL);

实际执行的将是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的空间复杂度

除了时间复杂度,内存分配器的另外一个目标就是更好的空间复杂度,尽可能地减少内部碎片和外部碎片,充分利用已有内存空间。因为kmalloc所利用的内存块的大小是事先定义好的,所以很多情况下会产生内部碎片,浪费空间,而kmem_cache_alloc由于内存大小也是量身定做的缘故则不会。但是,有一点是kmem_cache_alloc所不能做到的,那就是动态大小的内存空间,这个任务是非kmalloc莫属。

其它

kmem_cache_create的参数列表中还有构造函数和析构函数(SLUB中已经去掉了析构函数),对构造函数的支持也是Slab相对于其它内存分配器的优势,他能够避免对一块内存的重复初始化,从而提高效率,而kmalloc则不能。

结论

动态创建固定大小的内存对象,虽然kmalloc的时间复杂度并不大,但是联系到空间复杂度,还是采用kmem_cache_alloc的好;而非固定大小的内存申请,只能经由kmalloc来解决。

参考连接:

[1]
[2] Linux slab 分配器详解
[3]
阅读(1074) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~