Kmalloc内部实现：挖掘Linux内核内存分配（一）

为什么写这篇文章：

最近我在几个linux设备上发现整数溢出，以致我开始用kmalloc重写内存分配。

注意：

理解这篇文章需要知道点linux内核。有时候我肯能用熟知的一些函数名。如果你不知道他们的意义，可以快速google。我提到的所有关于cache的函数都能在/usr/src/linux/mm/slab.c找到。一些数字是在IA-32架构上给出的。我努力加粗函数名和数据类型。在一些代码中我删除了调试代码。我忽略了SMP（多核）代码，因为我没有多核系统。我是个偷懒的人。你准备读了吗？

整体浏览：

任何操作系统需要一个方式来管理物理内存。设备驱动和内核的其他部分能够分配内存块去存储数据。这些内存来自系统RAM，当我们谈到系统RAM，它常指代Page_size块。在一些架构上是4k。然而，当一些驱动或者其他内核函数需要动态分配内存，他们经常不需要整页。因此，需要一些实体来管理RAM，处理不同大小内存卡的请求。这样一个分配器需要仔细平衡两个目标：速度和最小化碎片大小，在块上分配但没用到的内存。后者尤为重要，因为任何碎片化内存将会浪费RAM。这个工作有kmalloc函数来执行，它的相对函数是kfree。

Kmalloc 做的不多：

事实上，kmalloc只是一个实际内存管理器的接口。因此为了理解kmalloc，非常需要首先理解缓存分配机制。这将使这次讨论的焦点。理解之后，你将会发现kmalloc只是缓存分配服务的一个使用者。

缓存概述:

     缓存分配器背后的想法很简单：将内存划分为对象池，每个对象池包含同样大小的对象，并且不同的池包含不同的大小。因此，当有人请求一个给定大小的内存块，找到第一个能够足够大的块的内存池，分配给他完事。这就是所有要做的事情。下面内容将会复杂点。需要考虑一些事情：每个池多大为好？如果我们用完一个池的对象，我们如何创建更多的池？我们如何追踪池子的对象是free的或者在使用中？我们应该有多少池？池大小之间的gap多大为好？ 

正如之前所说，内存被分为包含对象的池。每个池被认为是一个缓存，内核中有许多这样的缓存池。这些池的关键数据结构是：kmem_cache_t。它用来处理池用到的所有信息，比如每个对象的大小以及每个池中对象数目。驱动能够通过kmem_cache_create函数创建它选定大小的内存池。这个函数创建调用者给定大小的内存，然后将它插入已创建的全局内存池cache_cache。cache_cache是一个静态kem_cache_t对象，用来管理所有系统级缓存。你可以通过/proc/slabinfo看到所有缓存大小。除了全局缓存池，我们也有通用缓存池。通用缓存池是一个缓存数组，每个元素后一个是前一个的2指数幂倍。在IA-32中以32开始，一直到131072*2.对于每个大小，有两个cache，一个为普通内存，一个为DMA。在IA-32，DMA内存必须是16位可寻址的。这就是kmalloc如何工作的。当kmalloc被调用，他搜索通用缓存知道找到一个合适的缓存块。然后调用__kem_cache_alloc来从缓存获取对象并返回给调用者。同样的，kfree只是通过调用__kem_cache_free来返回对象到他的缓存池。

Caches 和 slabs:

     关键的数据结构是kem_cache_t。它有多个成员，下面是一些重要的：
        
     struct list_head    slabs_full;
    struct list_head    slabs_partial;
    struct list_head    slabs_free;
       这些链表是为这个缓存的slab的。解释在下面。

    unsigned int        objsize;

缓存中每个对象的大小。

    unsigned int        flags;  

缓存的标志位。决定某些操作，并且存储对象追踪信息。

    unsigned int        num;    
        在每个slab上存储的对象大小。

    spinlock_t      spinlock;   
       多CPU中保护并发访问的结构。

    unsigned int        gfporder;
      每个slab中分配2^gfporder个页。

    unsigned int        gfpflags;
        MA内存需要。

    char            name[CACHE_NAMELEN];
       chache的名字。

    struct list_head    next;
        When this cache is user created and belongs to the global cache_cache list, this sews it into the list.

    void (*ctor)(void *, kmem_cache_t *, unsigned long);
   void (*dtor)(void *, kmem_cache_t *, unsigned long);
        由创建者传来的构造和析构函数，在Create/Free时调用。
    

   这里还有一些其他用来统计的数据，与SMP数据意义，会在之后看到。

为了在每个缓存里组织对象，内核依赖slabs。一个slab持有一些对象和控制信息。一个缓存包含多个slab，每个slab包含多个对象。一slab只是由get_free_pages分配的几个内存页。为了组织所有的slab，一个缓存用标准内核链表管理三个单独的slab链表，一个是是没有对象的slabs的free_list，一个是全满的full_list，一个是部分满的partial_list，每个slab有slab_t类型指定，包含一个链表指针指向其他slabs。也就是说一个slab将会在三个链表之一。