工学1号馆

home

malloc 深入剖析5--基于首次适应算法的malloc实现

By Wu Yudong on July 30, 2016

在本文中我们将实现经典的基于首次适应类型的 malloc. 首次适应算法很简单:遍历块链表,当找到满足请求大小并且是free标记的块的时候停止。

1. 指针对齐
通常指针被要求与整型类型对齐 (也即是指针类型大小), 在案例中只考虑32位的情况。于是我们的指针必须是4的倍数 (32 bits = 4 bytes) 因为我们的meta-data块已经对齐,现在唯一要做的是对齐数据块(data block)。

本文地址:http://wuyudong.com/2016/07/30/2372.html,转载请注明源地址。

如何实现呢? 有几种方法,其中比较高效的是增加一个使用算术技巧的预处理宏。

算术技巧: 给定任何的正整数n被4做整数除法,然后乘以4,结果为最接近n且比n小的4的倍数,为了获得最接近n且比n大的4的倍数,只需要在得到的结果上加上4,这个很简单,但是对于n本身为4的倍数的情况不适用,因为这样操作的结果将是4的另一个倍数.
但是,再一次依据算术:

假设x是一个整数,可以表示成 x = 4 × p + q,其中 0 ≤ q ≤ 3,

如果 x 是4的倍数, q = 0 且x−1 = 4×(p−1)+3,于是((x−1)/4)×4+4 = 4× p = x.

如果x 不是4的倍数, 于是 q , 0 and x − 1 = 4 × p + (q − 1) 与0 ≤ q − 1 ≤ 2,于是 (x−1)/4×4+4 = 4× p+4 = x/4×4+4.

我们有表达式 (x−1)/4×4+4 总能得到大于或等于最接近4的倍数.

但是怎样用C语言实现呢 ? 首先,注意到乘以和除以4可以使用比一般运算更快的左移和右移位操作 (C中的>> 和 << ) , 于是我们的式子可以写成C语言的形式为: (((x-1)>>2)<<2)+4,为了防止错误我们需要加上额外的括号:

(((((x)-1)>>2)<<2)+4),现在我们可以写出下面的宏:

#define align4(x) (((((x)-1)>>2)<<2)+4)

2. 查找块:首次适应算法

找到一个足够大的空闲(free)块相当的容易:我们从堆的基地址(base) (在代码中以某种形式记录下来,我们后面用得着)检测当前块,如果满足我们的请求直接将其地址返回,否则继续下一块直到找到一个合适的块或者到达尾部的头地址。 唯一的技巧是保持最后访问的块,于是当我们找不到合适块的时候malloc函数可以很容易扩展堆。代码很简单,base是一个指向堆的起始部位的全局指针:

t_block find_block(t_block *last, size_t size)
{
    t_block b = base;
    while (b && !(b->free && b->size >= size)) {
        *last = b;
        b = b->next;
    }
    return (b);
}

这个函数返回满足条件的块,或者如果没有找到返回NULL,在没有找到的情况下,参数last指向最后访问的块(chunk).

3. 扩展堆
我们并不是总能找到匹配的块,并且有时我们需要扩展堆,这很简单:我们移动 break并初始化一个新的块(block),当然我们需要更新堆中的最后一个块的next域。在后面的开发中,我们需要使用一些技巧在block的结构体上,于是定义一个宏保存meta-data块的大小:

#define BLOCK_SIZE sizeof(struct s_block)

如果sbrk执行失败则返回 NULL,注意到我们不确定 sbrk 返回break的前驱块,我们最初保存它然后移动break,可以通过last 与last->size来计算它

t_block extend_heap(t_block last, size_t s)
{
    t_block b;
    b = sbrk(0);
    if (sbrk(BLOCK_SIZE + s) == (void *)-1)
        /* sbrk失败,返回NULL */
        return (NULL);
    b->size = s;
    b->next = NULL;
    if (last)
        last->next = b;
    b->free = 0;
    return (b);
}

4. 分割块
您可能已经注意到,我们使用第一个有效可用块,不顾它的大小(提供足够大),如果这样做后面将释放很多的空间(试想:如果请求2个字节但是找到一个256字节的块),第一个解决办法是划分块:当一个块空间的大小足够满足要求,可以随后产生一个新的块 (至少为BLOCK SIZE + 4), 我们往链表中插入一个新的块.

QQ截图20160728231059

接下来的函数仅在空间有效的时候被调用,提供的块的大小同样需要对齐。 在这个函数中,我们将做一些指针运算,为了避免错误,将使用一点技巧来保证我们的操作精确到1字节 (注意 p+1 取决于p指向的类型)
我们将块结构体添加另一个域,一个字符数组。该数组的指针指向meta-data块的尾部。 C语言禁止出现0长度数组,于是我们定义一个长度为1的数组。(ps:这样的数组称为柔性数组,我的博客中有专门的文章介绍)

struct s_block {
    size_t size;
    t_block next;
    int free;
    char data[1];
};
/* 更新 BLOCK_SIZE 宏 */
#define BLOCK_SIZE 12        /* 3*4 ... */

注意到这种扩展并不需要在扩展的堆上作任何的修改,因为新的域不能直接使用.
现在实现分割块: 这个函数通过传递的参数来切断块,从而实现要求大小的数据块(data block),Figure 4显示了整个操作过程。

void split_block(t_block b, size_t s)
{
    t_block new;
    new = b->data + s;
    new->size = b->size - s - BLOCK_SIZE;
    new->next = b->next;
    new->free = 1;
    b->size = s;
    b->next = new;
}

注意到第4行使用 b->data进行指针算术运算,因为data域是字符型数组 char[] ,我们可以肯定那个求和运算是按照字节精度完成.

5. malloc函数

现在可以实现我们的malloc了,它几乎就是对之前实现的函数的一个封装,我们必须对齐请求的大小,判断是否是第一次调用malloc函数,并且其他的条件是否被告知。记住之前函数查找块的时候使用了一个全局变量base,这个变量定义如下:

void *base=NULL;

它是空指针并被初始化为 NULL,我们的malloc首先要做的事就是测试base,如果为NULL,这是我们第一次调用,否则我们使用之前描述的算法。

按照下面的步骤实现malloc:

 • 首先对齐请求的块大小;
 • 如果base已经初始化:
     – 查找一个足够大的空闲块;
     – 如果我们找到一个块:
         * 尝试分割块 (请求块的大小和已知块的大小的差距是meta-data块和最小4字节的块;
         * 标记块已经在使用中 (b->free=0);
     – 否则: 扩展堆.
         注意last的使用: find_block使用一个指针指向最后访问的块(chunk), 这样我们就
         可以在扩展堆的时候访问它,而不需要去遍历整个链表.
 • 否则: 扩展堆 (这时指针为空)
   注意,我们扩展堆的函数是使用last=NULL.

同样要注意到每次执行失败,我们都按照malloc的规范返回NULL,下面是malloc 函数的代码:

void *malloc(size_t size)
{
    t_block b, last;
    size_t s;
    /* 对齐 */
    s = align4(size);
    if (base) {
        /* 查找第一个block */
        last = base;
        b = find_block(&last, s);
        if (b) {
            /* 判断能否分割块 */
            if ((b->size - s) >= (BLOCK_SIZE + 4))
                split_block(b, s);
            b->free = 0;
        } else {
            /* 没有合适的块,扩展堆 */
            b = extend_heap(last, s);
            if (!b)
                return (NULL);
        }
    } else {
        /* 第一次 */
        b = extend_heap(NULL, s);
        if (!b)
            return (NULL);
        base = b;
    }
    return (b->data);
}

 

如果文章对您有帮助,欢迎点击下方按钮打赏作者

Comments

No comments yet.
To verify that you are human, please fill in "七"(required)