AT&T的malloc实现--malloc的基础和本质

时间:2021-11-09 13:03:58

malloc作为标准c的一个内存分配调用想必每一个搞过C语言的都用过,然而在这个很常用的统一接口下面却有着N种不同的实现,linux的glibc有自己的实现,windows的crt有自己的实现,这些实现都有着自己的策略,特别是glibc的实现让人看的头晕,crt的实现虽然简单但是有着策略感觉很傻,最原始而且最能说明本质的实现我认为还是贝尔实验室的实现,很简单,前后不超过60行代码,让人读后心旷神怡,连同free的实现一同构成了一幅美丽的图景,本质上贝尔实验室的malloc使用了一个线性的链表来表示可以分配的内存块,熟悉伙伴系统和slab的应该知道这是这么回事,但是仍然和slab和伙伴系统有所不同,slab中分配的都是相同大小的内存块,而伙伴系统中分配的是不同确定大小的内存块,比如确定的1,2,4,8...的内存,贝尔试验室的malloc版本是一种随意的分配,本身遵循碎片最少化,利用率最大化的原则分配,其实想想slab的初衷,其实就是一个池的概念,省去了分配时的开销,而伙伴系统的提出就是为了消除碎片,贝尔malloc版本一举两得,虽然现在很多人已经遗忘了这个版本或者你可以说glibc或者crt的实现已经超越了这个版本,但是这些实现或多或少的给蛇添了足,没有贝尔malloc实现的那么纯粹。现在首先看一下基本的数据结构:

typedef struct mem{

struct mem *next;

Unsigned len;

}mem;

这个数据结构表示一切的内存块slot,每一个slot代表一块内存,其中的len表示其长度,这个结构体其实就是一个头的概念,真正的数据附着在这个结构体的后面相邻的地方,这个结构体设计的巧妙之处在于它可以让malloc和free更简单的实现,正式由于它的第一个字段是一个mem*类型的,妙在哪里呢?只有看了malloc才知道:

mem *F; //一个全局的mem*链表,F的含义就是Free,它指向当前空闲链表的头,该链表是一个线性链表

void *malloc(unsigned size)

{

register mem *p, *q, *r, *s;

unsigned register k, m;

extern char *sbrk(int);

char *top, *top1;

size = (size+7) & ~7; //字节对齐

r = (mem *) &F; //取链表头的地址,该头本身就是一个指针类型,因此r实际上是指针的指针,正是由于mem的第一个字段是一个mem*类型,它才可以转化为mem*类型的,F取地址后就是F的地址,存储的是F,而F是一个men指针,因此&F地址处的数据就是一个mem*类型,将之转化为mem*之后,其数据整好是mem的next字段,注意此时它的len字段无效,这个转化的意义就在于r的next就是F

for (p = F, q = 0; p; r = p, p = p->next) //遍历空闲链表,直到F的前驱为NULL

{

if ((k = p->len) >= size && ( !q || m > k)) //&之前的确保当前的空闲块满足分配要求,之后的确保找到大于size的空闲块的最小的那一块

{

m = k; //m记录当前找到的满足要求的最小块

q = p; //q记录当前满足要求的那一块

s = r; //s记录当前满足要求的前一块

}

}

if (q) //如果找了满足要求的块,要么直接分配,要么分割后分配然后重将分配后没有使用的那一块加入空闲链表

{

if (q->len - size >= MINBLK) //满足分割要求,也就是最小粒度要求

{

p = (mem *)(((char *)(q+1)) + size); //设置q的大小,这一块将从空闲链表移除,返回使用

p->next = q->next; //将分割后的新的空闲块的next设置为分割前的q的next

p->len = q->len - size - sizeof(mem); //分割后的p的len显然减少了size和mem的加和的大小

s->next = p; //将满足要求的前一块的next指向q的后一块

q->len = size; //将q分配出去,也就是从空闲链表移除

}

else //如果不能分割,那么直接将这一块q分配出去

s->next = q->next;

}

else //如果没有找到合适的空闲块可以分配,那么就要向操作系统要了

{

top = (char *)(((long)sbrk(0) + 7) & ~7); //找到当前的堆的顶部

if (F && (char *)(F+1) + F->len == top) //如果有空闲块并且空闲块就是堆顶的那一块

{

q = F; //将空闲块首指针赋给q

F = F->next; //向后推进空闲块

}

else //否则将堆顶赋给q

q = (mem *) top;

top1 = (char *)(q+1) + size; //找到新的堆顶,但是要预先分配SBGULP

if (sbrk((int)(top1-top+SBGULP)) == (Char *) -1)

return 0;

r = (mem *)top1; //r记录新的将要分配的slot的next

r->len = SBGULP - sizeof(mem);

r->next = F; //将原来的空闲链表赋给新的slot的next的next

F = r; //新的slot的下一个slot赋给新的空闲链表

q->len = size;

}

return (char *)(q+1); //返回q,q就是分配的内存

}

以上就是malloc的操作,很有条理,并且很清晰,关键就是指针的使用,看了这个实现就会发现原来指针还能这么使用,如果mem结构体的第一个字段不是mem类型的指针,那么上述的malloc实现根本就不可能有这么简单。注意“下一个元素”有两个概念,一个是逻辑上的概念,用next字段得到,另一个是物理上的概念,用qn = (char *)f + q->len这种方式得到,用next指针得到的下一个元素物理上不一定相邻,所有的用next连在一起的元素都是空闲元素,而用偏移得到的下一个元素是物理上相邻的内存块,也就是虚拟内存相邻的内存块,用此方式得到的内存块不一定是空闲块。分配也就是上面这个malloc函数,很简单的一个函数,释放其实也是很有意思的,其实就是free函数:

void free(char *f)

{

mem *p, *q, *r;

char *pn, *qn;

if (!f)

return;

q = (mem *) ((char *)f - sizeof(mem)); //得到要释放的f所在的mem头的位置,虽然q已经从空闲链表摘除,但是它还是本质存在的

qn = (char *)f + q->len; //在线性链表中得到q的下一个元素,不一定是空闲元素,因为它是靠内存位置来游历的

for (p = F, r = (mem *) &F; ; r = p, p = p->next)

{

if (qn == (Char *) p) //如果q的下一个元素就是p的话,那么吞并掉它,注意p一定是空闲元素,因为它是靠next指针来游历的

{

q->len += p->len + sizeof(mem); //更新q的len字段,这就是吞并p的行为

p = p->next; //由于p被将要释放的q吞并,导致p进入q内部而不复存在,其本身也就成为了一个将要被释放的内存块的一部分

}

pn = p ? ((char *) (p+1)) + p->len : 0; //得到p的下一个元素,不一定空闲

if (pn == (char *) q) //如果p的后面相邻元素就是将要释放的q,那么q就和p合并作为一个更大的空闲块存在

{

p->len += sizeof(mem) + q->len; //合并p和q

q->len = 0; //丢掉q

q->next = p; //回环,实际上已经丢弃了q

r->next = p; //这一个很有意思,下面会专门说

break;

}

if (pn < (char *) q) //如果不相邻并且p后面相邻的元素地址比q小的话就将q链接进空闲链表

{

r->next = q; //更新链接指针

q->next = p;

break;

}

}

}

到此为止,所有的分配和释放就说完了,是不是很简单呢?上面的合并操作的目的和伙伴系统的一样,只不过伙伴系统合并的是大小固定的内存块,而这里的合并是只要相邻有合并的可能就合并而不管内存块的大小。注意上述的代码没有考虑并发和需要锁的情况,但是这就是最纯真,也是最本质的东西,不是吗?在这种简单而又可以说明本质之后,我会写两篇关于malloc的改进版本,分别是微软的和glibc的版本。

附:关于指针的一个问题

前面说过,如果不是mem结构设计得如此巧妙,那么AT&T的malloc不会这么简单,最重要的就是可以通过&F然后将之转化为mem*类型,这样这个指针就是F的前一个元素,如果不这么设计mem结构,那么可能除了next指针之外还需要一个prev指针了。注意,设F为mem指针,&F并不是一个真正的mem指针,而是由于mem的第一个字段为一个mem指针,而&F在内存中应该是一个mem指针的指针,但是该指针的指针不论如何也是一个指针类型,其指向的数据正好也是一个指针,后者是mem指针类型,这正好符合mem结构体的布局,mem结构体的第一个字段就是一个mem指针类型,因此我们可以将&F理解成F的前一个元素,因为&F的第一个字段是F,这仅仅是可以这么理解,如果不将next作为第一个字段,那么就没有这样的事,并且任何改变&F的next字段的行为都会改变F本身,除了&F是F的前一个元素这件事成立之外,它们还有别的千丝万缕的联系,这就是指针的伟大,同时也可能带来更多的困惑。