基于malloc与free函数的实现代码及分析_C 语言

  用于内存管理的malloc与free这对函数,对于使用C语言的程序员应该很熟悉。前段时间听说有的IT公司以“实现一个简单功能的malloc”作为面试题,正好最近在复习K&R,上面有所介绍,因此花了些时间仔细研究了一下。毕竟把题目做出来是次要的,了解实现思想、提升技术才是主要的。本文主要是对malloc与free实现思路的介绍,蓝色部分文字是在个人思考中觉得比较核心的东西;另外对于代码的说明,有一些K&R上的解释,使用绿色加亮。

  在研究K&R第八章第五节的实现之前,不妨先看看其第五章第四节的alloc/afree实现,虽然这段代码主要目的是展示地址运算。

复制代码 代码如下:

alloc实现

#define ALLOCSIZE 10000
static char allocbuf[ALLOCSIZE];    /*storage for alloc*/
static char *allocp = allocbuf;    /*next free position*/

char *alloc(int n)
{
    if(allocbuf+ALLOCSIZE - allocp >= n) {
        allocp += n;
        return alloc - n;
    } else
        return 0;
}

void afree(char *p)
{
    if (p >= allocbuf && p<allocbuf + ALLOCSIZE)
        allocp = p;
}

  这种简单实现的缺点:

    1.作为代表内存资源的allocbuf,其实是预先分配好的,可能存在浪费。

    2.分配和释放的顺序类似于栈,即“后进先出”,释放时如果不按顺序会造成异常。

  这个实现虽然比较简陋,但是依然提供了一个思路。如果能把这两个缺点消除,就能够实现比较理想的malloc/free。

  仅仅依靠地址运算来进行定位,是限制分配回收灵活性的原因,它要求已使用部分和未使用部分必须通过某个地址分开成两个相邻区域。为了能让这两个区域能够互相交错,甚至其中还包括一些没有分配的地址空间,需要使用指针把同类的内存空间连接起来形成链表,这样就可以处理地址不连续的一系列内存空间。但是为什么只连接了空闲空间而不连接使用中的空间?这么问可能出于在对图中二者类比时的直觉而没有经过思考,这很简单,因为没有必要。前者相互链接是为了能够在内存分配时遍历所有空闲空间,并且在使用free()回收已使用空间时进行重新插入。而对于使用中的空间,由于我们在分配空间时已经知道它们的地址了,回收时可以直接告诉free(),并不用像malloc()时进行遍历。

  既然提到了链表,可能对数据结构稍有了解的人会立刻写下一个struct来代表一个内存区域,其中包含一个指向下一个内存区域的指针,但是这个struct的其他成员该怎么写呢?作为待分配的内存区域,大小是不定的,如果把它声明为struct的成员变量显然不妥;如果声明为一个指向某个其他的区域的指针,这似乎又和上面的直观表示不相符合。(当然,这么做也是可以实现的,它看上去是介于上图的两者之间,把管理结构和实际分配的空间相剥离,在文末我会专门的讨论一下这种实现方法)因此,这里仍然把控制结构和空闲空间相分开,但保持它们在内存地址中相邻,形成下图的形式,而正由这个特点,我们可以利用对控制结构指针的指针运算来定位对应的内存区域:

  

  对应地,把控制信息定义为Header:

复制代码 代码如下:

typedef long Align;/*for alignment to long boundary*/
union header {
    struct {
        union header *ptr; /*next block if on free list*/
        unsigned size; /*size of this block*/
    } s;
    Align x;
};

typedef union header Header;

  使用union而不是直接使用struct的原因是为了地址对齐。这里是long对齐,union的x永远不会使用。

  这样,malloc的主要工作就是对这些Header和其后的内存块的管理。

复制代码 代码如下:

malloc()

static Header base;
static Header *freep = NULL;

void *malloc(unsigned nbytes)
{
    Header *p, *prevp;
    unsigned nunits;
    nunits = (nbytes+sizeof(Header)-1)/sizeof(Header) + 1;
    if((prevp = freep) == NULL) { /* no free list */
        base.s.ptr = freep = prevp = &base;
        base.s.size = 0;
    }
    for(p = prevp->s.ptr; ;prevp = p, p= p->s.ptr) {
        if(p->s.size >= nunits) { /* big enough */
            if (p->s.size == nunits)  /* exactly */
                prevp->s.ptr = p->s.ptr;
            else {
                p->s.size -= nunits;
                p += p->s.size;
                p->s.size = nunits;
            }
            freep = prevp;
            return (void*)(p+1);
        }
        if (p== freep) /* wrapped around free list */
            if ((p = morecore(nunits)) == NULL)
                return NULL; /* none left */
    }
}

  实际分配的空间是Header大小的整数倍,并且多出一个Header大小的空间用于放置Header。但是直观来看这并不是nunits = (nbytes+sizeof(Header)-1)/sizeof(Header) + 1啊?如果用(nbytes+sizeof(Header))/sizeof(Header)+1岂不是刚好?其实不是这样,如果使用后者,nbytes+sizeof(Header)%sizeof(Header) == 0时,又多分配了一个Header大小的空间了,因此还要在小括号里减去1,这时才能符合要求。

   malloc()第一次调用时建立一个退化链表base,只有一个大小是0的空间,并指向它自己。freep用于标识空闲链表的某个元素,每次查找时可能发生变化;中间的查找和分配过程是基本的链表操作,在空闲链表中不存在合适大小的空闲空间时调用morecore()获得更多内存空间;最后的返回值是空闲空间的首地址,即Header之后的地址,这个接口与库函数一致。

复制代码 代码如下:

morecore()

#define NALLOC 1024    /* minimum #units to request */
static Header *morecore(unsigned nu)
{
    char *cp;
    Header *up;
    if(nu < NALLOC)
        nu = NALLOC;
    cp = sbrk(nu * sizeof(Header));
    if(cp == (char *)-1)    /* no space at all*/
        return NULL;
    up = (Header *)cp;
    up->s.size = nu;
    free((void *)(up+1));
    return freep;
}

  morecore()从系统申请更多的可用空间,并加入。由于调用了sbrk(),系统开销比较大,为避免morecore()本身的调用次数,设定了一个NALLOC,如果每次申请的空间小于NALLOC,就申请NALLOC大小的空间,使得后续malloc()不必每次都需要调用morecore()。对于sbrk(),在后面会有介绍。

  这里有个让人惊讶的地方:malloc()调用了morecore(),morecore()又调用了free()!第一次看到这里时可能会觉得不可思议,因为按照惯性思维,malloc()和free()似乎应该是相互分开的,各司其职啊?但请再思考一下,free()是把空闲链表进行扩充,而malloc()在空闲链表不足时,从系统申请到更多内存空间后,也要先把它们转化成空闲链表的一部分,再进行利用。这样,malloc()调用free()完成后面的工作也是顺理成章了。根据这个思想,后面是free()的实现。在此之前,还有几个morecore()自身的细节:

  1.如果系统也没有空间可以分配,sbrk()返回-1。cp是char *类型,在有的机器上char无符号,这里需要一次强制类型转换。

  2.morecore()调用的返回值看上去比较奇怪,别担心,freep会在free()中修改的。使用这个返回值也是为了在malloc()里的判断、p = freep的再次赋值的语句能够紧凑。

复制代码 代码如下:

free()

void free(void *ap)
{
    Header *bp,*p;
    bp = (Header *)ap -1; /* point to block header */
    for(p=freep;!(bp>p && bp< p->s.ptr);p=p->s.ptr)
        if(p>=p->s.ptr && (bp>p || bp<p->s.ptr))
            break;    /* freed block at start or end of arena*/
    if (bp+bp->s.size==p->s.ptr) {    /* join to upper nbr */
        bp->s.size += p->s.ptr->s.size;
        bp->s.ptr = p->s.ptr->s.ptr;
    } else
        bp->s.ptr = p->s.ptr;
    if (p+p->s.size == bp) {     /* join to lower nbr */
        p->s.size += bp->s.size;
        p->s.ptr = bp->s.ptr;
    } else
        p->s.ptr = bp;
    freep = p;
}

   free()首先定位要释放的ap对应的bp与空闲链表的相对位置,找到它的的最近的上一个和下一个空闲空间,或是当它在整个空闲空间的前面或后面时找到空闲链表的首尾元素。注意,由于malloc()的分配方式和free()的回收时的合并方式(下文马上要提到),可以保证整个空闲空间的链表总是从低地址逐个升高,在最高地址的空闲空间回指向低地址第一个空闲空间。

  定位后,根据要释放的空间与附近空间的相邻性,进行合并,也即修改对应空间的Header。两个if并列可以使得bp可以同时与高地址和低地址空闲空间结合(如果都相邻),或者进行二者之一的合并,或者不合并。

  完成了这三部分代码后(注意放到同一源文件中,sbrk()需要#include <unistd.h>),就可以使用了。当然要注意,命名和stdlib.h中的同名函数是冲突的,可以自行改名。

  第一次审视源码,会发现很多实现可能原先并没有想到:Header的结构和对齐填充、空间的取整、链表的操作和初始化(边界情况)、malloc()对free()的调用、由malloc()和free()暗中保证的链表地址有序等等,确实很值得玩味。另外再附上前文中提到的两个问题还有一些补充问题的简单思考

1.Header与空闲空间相剥离,Header中包含一个指向其空闲空间的指针

  这样做未必不可,相应地算法需要改动。同时,由于Header和空闲空间不再相邻,sbrk()获得的空间也应该包含Header的部分,内存的分布可能会更加琐碎。当然,这也可能带来好处,即用其他数据结构对链表进行管理,比如按大小进行hash,这样查找起来更快。

2.关于sbrk()

  sbrk()也是库函数,它能使堆往栈的方向增长,具体可以参考:brk(), sbrk() 用法详解。

3.可以改进的方

  空闲空间的寻找是线性的,查找过程在内存分配中可以看作是循环首次适应算法,在某些情况下可能很慢;如果再建立一个数据结构,如hash表,对不同大小的空间进行索引,肯定可以加快查找本身,并且能实现一些算法,比如最佳匹配。但查找加快的代价是,修改这个索引会占用额外的时间,这是需要权衡的。

  morecore()中的最小分配空间是宏定义,在实际使用中完全可以作为参数传递,根据需要设定最小分配下限。

时间: 2024-08-30 05:21:02

基于malloc与free函数的实现代码及分析_C 语言的相关文章

基于Protobuf C++ serialize到char*的实现方法分析_C 语言

protobuf的Demo程序是 C++版本的protubuf有几种serialize和unSerialize的方法: 方法一: 官方demo程序采用的是 复制代码 代码如下:  // Write the new address book back to disk.     fstream output(argv[1], ios::out | ios::trunc | ios::binary);     if (!address_book.SerializeToOstream(&output))

基于C++输出指针自增(++)运算的示例分析_C 语言

复制代码 代码如下: #include "stdafx.h"#include <iostream>using namespace std;int _tmain(int argc, _TCHAR* argv[]){ char s[] = "012345678", *p = s;  cout << "s:"<<s<<endl; cout << "*p++ = " <

C语言中函数与指针的应用总结_C 语言

1. 首先,在C语言中函数是一种function-to-pointer的方式,即对于一个函数,会将其自动转换成指针的类型. 复制代码 代码如下: #include<stdio.h> void fun(){} int main(void){   printf("%p %p %p\n", &fun, fun, *fun);   return 0;} -------------------------------------------------------------

深入C++实现函数itoa()的分析_C 语言

函数itoa()是将整数型转换为c语言风格字符串的函数,原型:char * itoa(int data, char*p, int num):data是传入的带转化的数字,为整型变量(data的最大值为2的31次方减去1),p是传入的字符型指针,指向存储转换后字符串空间的首地址:num指定要转换成几进制的数字字符串(二进制,八进制,十进制,十六进制).如有不足之处,还望指正!!! 复制代码 代码如下: // TestInheritance.cpp : 定义控制台应用程序的入口点.//#includ

C++中函数模板的用法详细解析_C 语言

定义 我们知道函数的重载可以实现一个函数名多用,将功能相同或者类似函数用同一个名来定义.这样可以简化函数的调用形式,但是程序中,仍然需要分别定义每一个函数. C++提供的函数模板可以更加简化这个过程. 所谓函数模板实际上是建立一个通用函数,其涵涵素类型额形参类型不具体指定,用一个虚拟的类型来代表,这个通用函数就称为函数模板. 凡是函数体相同的函数都可以用这个模板来代替,不必定义多个函数,只需要在模板中定义一次即可.在调用函数时,系统会根据实参的类型来取代模板中的虚拟类型,从而实现了不同函数的功能

C++通过自定义函数求一元二次方程的根_C 语言

本文实例讲述了C++通过自定义函数求一元二次方程的根.分享给大家供大家参考,具体如下: /* * 作 者: 刘同宾 * 完成日期:2012 年 11 月 24 日 * 版 本 号:v1.0 * 输入描述: * 问题描述: 求一元二次方程的根.定义函数 * 程序输出: * 问题分析:略 * 算法设计:略 */ #include<iostream> #include<cmath> using namespace std; double x,x1,x2,t; //定义全局变量 void

c语言:基于函数指针的两个示例分析_C 语言

第一个:------------------------------------------------------ 复制代码 代码如下: #include <stdio.h>#include <string.h>void tell_me(int f(const char *, const char *));int main(void){   tell_me(strcmp);   tell_me(main);   return 0;}void tell_me(int f(const

bloom filter概念讲解以及代码分析_C 语言

一. 简介1.什么是bloom filter?Bloom filter 是由 Howard Bloom 在 1970 年提出的二进制向量数据结构,它具有很好的空间和时间效率,被用来检测一个元素是不是集合中的一个成员,这种检测只会对在集合内的数据错判,而不会对不是集合内的数据进行错判,这样每个检测请求返回有"在集合内(可能错误)"和"不在集合内(绝对不在集合内)"两种情况,可见 Bloom filter 是牺牲了正确率换取时间和空间. 2.bloom filter的计

c文件汇编后函数参数传递的不同之处_C 语言

mac下clang编译后函数的参数先保存在寄存器中(以一定的规则保存),然后在函数中压入栈里,以待后用.例如上篇例子,红色部分: 复制代码 代码如下: .global _decToBin  _decToBin:     pushq     %rbp     movq    %rsp,%rbp      movq     %rdi,-8(%rbp) #第一个参数,保存在rdi中     movq     %rsi,-16(%rbp) #第二个参数,保存在rsi中      movq    -8(%