Kmalloc的实现

Kmalloc的实现

Kmalloc是内核对内存的管理理分配函数（以下说的malloc和Kmalloc是同指kmalloc）

基本的思想是把内存页面分块，分块涵盖有几种类型，

0m<16b,

16

32

64

128

512

1024

2048

这个内存页面分块是一个页面一个页面的分。比如一个4k的页面，要么都分成16b大小的块，要不就都分成32b大小的块。这里的16b或32b的块就是我们常说的存储桶了。所以存储桶的大小有16b，32b，64b…。我们可以把4k的页面看做是一个大的存储桶，这个大桶中放都很多小桶。但是不要搞混了，这里说到的存储桶依然是小的存储桶。这么多的存储桶是通过什么东西来管理的呢？答案是存储桶目录和存储桶描述符。

1．  存储桶目录

存储桶目录很简单，就是定义存储桶的大小和这号存储对应的第一个存储桶描述符，，下面会讲到。我们来看一下存储桶目录的定义：

// 存储桶目录结构。

struct _bucket_dir

{/* 8 bytes */

  int size;                         // 该存储桶的大小(字节数)。

  struct bucket_desc *chain;       // 该存储桶目录项的桶描述符链表指针。

};

// 存储桶目录列表(数组)。

struct _bucket_dir bucket_dir[] = {

  {16, (struct bucket_desc *) 0},        // 16 字节长度的内存块。

  {32, (struct bucket_desc *) 0},        // 32 字节长度的内存块。

  {64, (struct bucket_desc *) 0},        // 64 字节长度的内存块。

  {128, (struct bucket_desc *) 0},             // 128 字节长度的内存块。

  {256, (struct bucket_desc *) 0},             // 256 字节长度的内存块。

  {512, (struct bucket_desc *) 0},             // 512 字节长度的内存块。

  {1024, (struct bucket_desc *) 0},    // 1024 字节长度的内存块。

  {2048, (struct bucket_desc *) 0},    // 2048 字节长度的内存块。

  {4096, (struct bucket_desc *) 0},    // 4096 字节(1 页)内存。

  {0, (struct bucket_desc *) 0}

};

从存储桶目录列表(数组)让我们从代码上理解存储桶的的概念。对c语言不是很精通的人可能会对(struct bucket_desc *) 0个东西有点疑惑。其实这个是一强制的类型转换，把一个常量转化为struct bucket_desc指针类型。存储桶目录列表(数组)有什么用呢？我们通过一个图片来说明

                                                             图1

左边的部分就是存储桶目录列表(数组)，在初始化的时候描述符指针就不是上面说的(struct bucket_desc *) 0了，而是一个可用的存储桶描述符指针。从图片中可以看出存储桶目录列表(数组)中的每个存储桶描述符指针都指向一个存储桶描述符。因为一个类型的存储桶会对应着很多此类型的存储桶描述符(下面还会讲到)，这些同类型的存储桶描述符会以链表的形式串联在一起。这里也回答了上面说到的“为什么是第一个？”的问题。讲到这里“存储桶目录列表(数组)有什么用呢？”的问题还是没有说明白，不过你可能已经猜到了。如果没有猜到也不要急，等把下面的内容搞清楚了自然就明了了。

2．  存储桶描述符

存储桶描述符是一个结构体，那么存储桶描述符有哪些内容呢？从上面的图1中你可能会想到它有5个元素，其中的两个元素是next和存储桶的类型（16，32或64…这些东西）。下面通过代码来让存储桶描述符一目了然

// 存储桶描述符结构。

struct bucket_desc

{/* 16 bytes */

  void *page;                      // 该桶描述符对应的内存页面指针。

  struct bucket_desc *next;  // 下一个描述符指针。

  void *freeptr;                   // 指向本桶中空闲内存位置的指针。

  unsigned short refcnt;              // 引用计数。

  unsigned short bucket_size;// 本描述符对应存储桶的大小。

};

这里会有一个问题，这样的存储桶描述符有多少个。是如何在内存中存储的呢？为了不引出其它的问题和易懂，这里先不回答这个问题。

下面来介绍存储桶描述符中的元素：我想我不必介绍next和bucket_size了（图1中更加明了）。

page

page是什么意思，在讲page之前先讲一下kmalloc设计时的一些想法。每个存储桶描述符对应（管理）的是一个页面的内存。这个面会被分为很多个相同大小的块（存储桶）。Page就是这个页面的首地址，也就是代码中注释的“内存页面指针”。

Freeptr

freeptr是指向一个空闲的存储桶，当然这个存储桶肯定是在page这个页面内的。在这个页面内可能会有很多空闲的相信桶，freeptr到底是指向哪个空闲的存储桶呢？这个问题留到后面讲。因为这里不好说明。

refcnt

refcnt是计数用的，就是当这个存储桶描述符对应的一页面内存中的一个存储桶被占用（malloc）这个数值会增加1，当这个存储桶描述符对应的一页面内存中的一个存储桶被释放（free）这个数值会增减1。当然refcnt的作用还不仅于此。它还跟释放内存页面有关，怕跑题，这里就不多讲。感兴趣的读者可以去baidu。我在讲解内存释放（free）时也有可能会提到。

       基于我们又对存储桶描述符有更多的了解，我们可以把上面的图1补充一下

                                                        图2

看到这里，我们对kmalloc有了初步的了解，下面将更深入了学习kmalloc。当然在进入下一步之前我们将上面还未解决的问题总结一下：

1.       存储桶描述符有多少个。是如何在内存中存储的呢？

2.       freeptr是指向一个空闲的存储桶，freeptr到底是指向哪个空闲的存储桶呢？

…..

我们再围绕这两个问题进行深入的讨论。先来看第1个问题.在设计这个程序（kmalloc）时这个问题就没有准确答案，因为没有人知道操作系统运行时到底要malloc多少内存，可能很多可能也很少这和操作系统执行的任务有关。所以程序设计就有点麻烦，不过学过数据结构的同学知道解决问题的方法那就是链表。

程序的作者是这样设计的。系统在第一次调用malloc之前可以内存中只有存储桶目录列表(数组)，和几个数据类型的定义。真正建立存储桶描述符和申请内存页面是在第一次调用malloc的时候。这时候内存中才真正有了存储桶。当然这里又出来了一个问题，如果第一次是malloc（10），16b的存储桶肯定是建立好了。那32b,64b…的存储桶是不是也建立好了呢？答案是否定的。所以这里的第一次对不同的存储桶类型来讲的。也就是说，如何所有的存储桶类型都存在于内存中那么有要有8个“第一次“。当然这8个第一次的操作相似，我们可以举一反三。

那我们就来看看第一次调用malloc（10）时程序是如何操作的。

1.       这里要伸请的是10b，毫无疑问，肯定会从存储桶目录列表(数组)中找到存储桶类型为16b的那个项。我们暂时称为16b项（以后类似的称其它的为32b项，64b项…）因为是第一次调用所以16b项中的存储桶描述符一定是0，程序检测到16b项中的存储桶描述符是0后就会为存储桶描述符申请1页的内存。这样一来，一页内存中可以放多少个存储桶描述符可发算出来了

4k/sizeof(struct bucket_desc)

当然这些是有限的，根据我们上面讨论的结果这个数值可能会不够用，不够用怎么办？不够用再申请咯。什么时候申请呢？当然是用完的时候了。这里为什么会那么多废话？往下面看就会知道了。现在malloc（10）绝对是够用的。

这里的每个存储桶描述符是用前面说到的链表串联起来的。这样也方便一个个的查找。

2.       现在存储桶描述符是有了，但是还没有存储桶，当然在为第一个存储桶描述符申请一个页面的空间来存放存储桶了。到这里内存中有4k/sizeof(struct bucket_desc) 个存储桶描述符4k/16b个存储桶。为什么不每个存储桶描述符都申请一个页面存放存储桶呢？当然是为了节约内存。用到了再申请。

到这里上面的第一个问题已经解决。

接下来看第二个问题freeptr是指向一个空闲的存储桶，freeptr到底是指向哪个空闲的存储桶呢？在回答这个问题之前来看一下存储桶的结构。它是不是就只有一块16b的内存大小的空间这么简单呢，答案是否定的。看一下图片

图3

每个存储桶前面的4bytes都用于存放一个指针，这个指针指向下一个空闲的存储桶。下图就比较直观一些。红色的表示被正在被占用（未被释放）

图4

左图中表示每个桶都没有被使用（第一次malloc时就是这种情况），右图中有2个正在被使用，显然是有malloc和free操作过的。

现在回到我们的问题2.freeptr就是指向空闲页面中的某一个空闲的存储桶的头4byte的位置，也可以说这个freeptr就是空闲存储桶的链表头。讲到这里我们已经是讲到两个链表了，可以说malloc这个函数就是操作链表了。现在两个问题都解决了。但是不是万事大吉。还有一些事情没完。如果读者还感兴趣可以往下看。

（先去洗澡了，未完待续）