fishjump's blog

fly,fly,fly

0%

MallocLab

发表于
本文字数： 3.4k 阅读时长 ≈ 12 分钟

前置知识

本lab大致的要求就是实现malloc、free、initial函数。initial函数就是要初始化堆。

做这个lab之前，需要对一下知识有一个比较清晰的认知。

  • 组织：如何组织空闲块，也就是如何初始化堆。
  • 放置：如何放置一个新分配的块。
  • 分割：因分配的块放到空闲块之后，如何处理空闲块的剩余部分。
  • 合并：如何处理一个刚刚被释放的块。

组织空闲块

有这样几种方法可以组织空闲块：采用隐式空闲链表、采用显示空闲链表

隐式空闲链表

块的格式：

规定块是双字（8字节）对齐的，也就是块的大小总是8的倍数，所以后三位总是为0，这空出来的三位就来表示状态信息。而剩余的29个高位用来存放块的大小。假设有一个分配的块，大小为24字节，那么其头部状态为

1
0x18 | 0x1   =  0x19         //1为状态为，表示已分配

对于一个大小为24字节，没有被分配的块，其头部为

1
0x18 | 0x0   =  0x18

头部的后面就是有效载荷。有效载荷后面是一片不使用的填充快，其大小是任意的。最后的填充快可以用来对付外部碎片或者满足对齐要求。

每一个块都如此，组织成一个连续的已分配块和空闲块的序列：

这种数据结构叫做隐式空闲链表，因为空闲块是通过头部中的大小字段隐含的连接着的。分配器可以通过遍历堆中的所有块从而间接地遍历空闲块集合。最后有一个大小为0而显示已分配的块是终止头部，用来标记结束块。

1
0x0 | 0x1    //终止头部
优点：

简单

缺点：

效率低。任何操作都需要堆空闲链表进行搜索，搜索时间与块的总数呈线性关系。

显示空闲链表

块的样式：

以后补充。。。

放置策略

当请求一个k字节的块时，分配器搜索空闲链表，查找一个足够大的块。分配器的搜索方式是由防止策略确定的，常见的策略有：首次适配、下一次适配、最佳适配。

首次适配

从又开始搜索空闲链表，选择第一个合适的空闲块。

下一次适配

和首次适配相似，只是起点不是链表的头部而是上一次查询结束的的地方。

最佳适配

最佳适配检查每个空闲块，选择适合所需请求大小的最小空闲块。

分割策略

匹配到合适的空闲块之后，可以选择占用整个空闲块，也可以选择分割为两部分，一部分变为分配块，剩下的部分变成一个新的空闲块。

合并策略

合并空闲块时必要的，否则会产生大量的内存碎片。

立即合并

每次一个块被释放时就合并所有的相邻块。

推迟合并

等到某个稍晚的时候合并，例如知道分配请求失败，然后扫描整个堆，合并所有的空闲块。

获取额外的堆空间

思考这样一种情况，在合并了所有的相邻空闲块之后，还是找不到一块足够大的空闲块来防止请求块，应该怎么办？

遇到这种情况，分配器会通过调用sbrk函数，向内核请求额外的堆内存，分配器将额外的内存转为一个大的空闲块，将这个块插入到空闲链表中，然后将被请求的块放置在这个新的空闲块中。

尝试实现一个简单的分配器

分配器说明：

  • 基于隐式空闲链表
  • 使用立即边界合并
  • 最大的块大小为4GB

分配器使用memlib.c包所提供的内存系统模型，模型的目的在于允许我们在不干涉已存在的系统层malloc包的情况下运行分配器。

mm_init函数将对于队来说的可用的虚拟内存模型化为一个大的、双字对齐的字节数组。在mm_heap和mm_brk之间的字节表示已分配的虚拟内存。分配器通过mm_sbrk函数来请求额外的堆内存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
static char *mem_heap;     //指向堆的第一个字节
static char *mem_brk;      //指向堆的最后一个字节+1 （堆指针）
static char *mem_max_addr;  //最大堆合法地址+1处


//初始化内存系统模型
void mem_init(void)          //注意这里不是初始化堆的mm_init
{
   mem_heap=(char*)Malloc(MAX_HEAP);
   mem_brk=(char*)mem_heap;        //此时指向堆顶
   mem_max_addr=(char*)(mem_heap+MAX_HEAP);
}

void *mem_sbrk(int incr)       //还函数用来扩展堆，改变堆指针，如果改变成功，则指向新内存的首地址
{
    char *old_brk=mem_brk;        //保存
    
    if((incr<0)||((mem_brk+incr)>mem_max_addr))       //检查参数是否合法，同时检测是否会越界
    {
        errno=ENOMEM;
        fprintf(stderr,"ERROR: mem_sbrk failed.RAN out of memory...\n");
        return (void*)-1;
    }
    mem_brk+=incr;
    return (void*)old_brk;
}

书中提供了一组常数和宏来简化空闲链表操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#define WSIZE 4     //字、头部、尾部的大小
#define DSIZE 8     //双字
#define CHUNKSIZE (1<<12)        //按照该大小扩展堆

#define MAX(x,y) ((x)>(y)?(x):(y))
//#difien MIN(x,y)

//打包（size）和已分配位到一个字
#define PACK(size,alloc)  ((size)|(alloc))

//读、写一个p地址的字
#define GET(p)   (*(unsigned int*)(p))
#define PUT(p,val)  (*(unsigned int*)(p) = (val))

//获取块的大小、获取分配状态
#define GET_SIZE(p) (GET(p)&~0x7) //舍弃低三位
#define GET_ALLOC(p) (GET(p)&0x1) //取最低位

//根据块指针，计算出头和尾
#define HDRP(bp)    ((char*)(bp)-WSIZE) 
#define FTRP(bp)    ((char*)(bp)+GET_SIZE(HDRP(bp))-DSIZE)

//根据块指针计算后一个块、前一个块的地址   （是有效存储位置）
#define NEXT_BLKP(bp)  ((char*)(bp)+GET_SIZE(((char*)(bp)-WSIZE)))
#define PREV_BLKP(bp)  ((char*)(bp)-GET_SIZE(((char*)(bp)-DSIZE)))

mm_init

在调用mm_malloc或者mm_free之前，必须用过mm_init函数来初始化堆。如果分配成功就返回0，否则返回-1。mm_init函数从内存系统得到四个字，并将它们初始化，创建一个空的空闲链表。然后调用extend_heap函数将堆扩展CHUNKSIZE字节，并创建初始的空闲块。

隐式空闲链表如图所示。第一个字是一个双字对齐的不使用的填充字，填充后面跟一个序言块（一个八字节的已分配块），只由头和尾组成。序言块在初始化时创建，并且永不释放。序言块后面是零个或者多个已块。结尾有一个特殊的结尾块，这个块是一个大小为零的已分配块，并且只由一个头部组成。分配器使用一个私有全局变量heap_list指向序言块。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int mm_init(void)
{
      //创建初始空堆       mem_sbrk(4*4) 返回值为之前的mem_brk即原始堆顶，经此次调用，堆扩展16字节，mem_brk指向新的堆顶，即结尾块。
    if((heap_list=mem_sbrk(4*WSIZE))==(void*)-1)    //如果分配失败则返回-1，若成功，此时的heap_list指向堆的首字
        return -1;
    PUT(heap_list,0);  //用来双字对齐的不使用的填充字
    PUT(heap_list+(1*WSIZE),PACK(DSIZE,1));     //序言块的头和尾
    PUT(heap_list+(2*WSIZE),PACK(DSIZE,1));
    PUT(heap_list+(3*WSIZE),PACK(0,1));        //结尾块
    heap_list+=(2*WSIZE);    //heap_list指向第二个序言块，如上图所示
    //printf("初始化空闲链表成功\n");
    
    //扩展空堆
    if(extend_heap(CHUNKSIZE/WSIZE)==NULL)      //初次分配扩展   1<<12/4    即1024个字
        return -1;

    //printf("初始化成功\n");

    return 0;           
}

extend_heap函数会在两种不同的环境中被调用：1.当堆被初始化时；2.当mm_malloc不能找到一个合适的匹配块时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static void *extend_heap(size_t words)
{
    char *bp;
    size_t size;
   
    size=(words%2)?(words+1)*WSIZE:words*WSIZE;     //确保双字对齐
    if((long)(bp=mem_sbrk(size))==-1)   //分配失败
       return NULL;
    
    //初始化            上文如果mem_sbrk调用成功，bp的值修改为mem_brk的初始值，即堆结尾（结尾块的后面），然后mem_brk修改为新的堆顶地址
    PUT(HDRP(bp),PACK(size,0));     //HERP(bp)  ((char*)(bp)-WSIZE)  将原始的结尾块更新为一个大的块(1024字)的头部，状态为未分配。
    PUT(FTRP(bp),PACK(size,0));      //新块的尾部
    PUT(HDRP(NEXT_BLKP(bp)),PACK(0,1));    //然后将新块的尾部的后一个字节更改成新的尾部
    
    return coalesce(bp);     //  合并
}

最后的合并书中实现的是隐式空闲链表的立即合并策略

有且仅有四种情况：

  1. 前面已分配、后面已分配
  2. 前面已分配、后面为分配
  3. 前面未分配、后面已分配
  4. 前面未分配、后面未分配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
static void *coalesce(void *bp)    //传入的参数bp是当前块的有效存储位置
{
    size_t prev_alloc=GET_ALLOC(FTRP(PREV_BLKP(bp)));    //获取前后块的分配状态
    size_t next_alloc=GET_ALLOC(HDRP(NEXT_BLKP(bp)));
    size_t size=GET_SIZE(HDRP(bp));      //获取当前块的大小
    
    if(prev_alloc && next_alloc)     //情况一，前后都已分配
    {
        return bp;
    }
    else if(prev_alloc && !next_alloc)    //前分 后未分 此时要合并当前块和后续块  
    {
        //修改当前块的头部和后继块的尾部
        size+=GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp),PACK(size,0));
        PUT(FTRP(bp),PACK(size,0));
    }
    else if(!prev_alloc && next_alloc)    //前未分、后已分
    {
        size+=GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(FTRP(bp),PACK(size,0));
        PUT(HDRP(PREV_BLKP(bp)),PACK(size,0));
        //PUT(FTRP(bp),PACK(size,0));
        //更新bp使其指向合并块的起始有效存储位置
        bp=PREV_BLKP(bp);      //在调用PREV_BLKP的时候bp块的头部还是原始值。
    }
    else if(!prev_alloc && !next_alloc)
    {
        size+=(GET_SIZE(HDRP(PREV_BLKP(bp)))+GET_SIZE(HDRP(NEXT_BLKP(bp))));
        PUT(HDRP(PREV_BLKP(bp)),PACK(size,0));
        PUT(FTRP(NEXT_BLKP(bp)),PACK(size,0));
        bp=PREV_BLKP(bp);
    }
    return bp;
}

mm_free

将指定块释放，也就是将它的标记为改为未分配，在最后再进行一次合并

1
2
3
4
5
6
7
void mm_free(void *bp)
{
    size_t size=GET_SIZE(HDRP(bp));
    PUT(HDRP(bp),PACK(size,0));
    PUT(FTRP(bp),PACK(size,0));
    coalesce(bp);
}

mm_malloc

  1. 判断参数是否合法
  2. 计算实际分配大小
  3. 寻找合适的块，更改头部和尾部
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void *mm_malloc(size_t size)
{
    size_t asize;        //实际分配大小
    size_t extendsize;
    char *bp;
    
    if(size==0)        //判断请求是否有效
        return NULL;
    //计算实际要分配的大小 
    if(size<=DSIZE)
        asize=2*DSIZE;   //如果请求小于一个字，那么直接分配最小块大小即四个字（块是双字对齐的，头和尾占两个字）
    else             //假设size大小为9 则asize应该为8+2*8 24字节
        asize=DSIZE*((size+(DSIZE)+(DSIZE-1))/DSIZE);    
    
    //搜索空闲链表找到一个合适的块
    if((bp=find_fit(asize))!=NULL)
    {
        place(bp,asize);
        return bp;
    }
    //如果找不到一个合适的块
    extendsize=MAX(asize,CHUNKSIZE);
    if((bp=extend_heap(extendsize/WSIZE))==NULL)
        return NULL;
    place(bp,asize);
    return bp;
}

如果不能发现一个匹配的块，那么就扩展堆。

如何实现遍历隐式空闲链表？需要注意的是要适配首次搜索。首次搜索的时候只有一个块，即堆扩展产生的一个1024字的大块。要用到heap_list遍历，首次搜索的时候他还指向第二个序言块。

1
2
3
4
5
6
7
8
9
10
11
12
static void* find_fit(size_t asize)      //搜索成功则返回块地址，失败则返回NULL
{
    void* bp;
    for(bp=heap_list;GET_SIZE(HDRP(bp))>0;bp=NEXT_BLKP(bp))
    {
        if(!GET_ALLOC(HDRP(bp)) && (GET_SIZE(HDRP(bp))>=asize))  //同时满足未分配和大小
        {
            return bp;
        }
    }
    return NULL;
}

place函数要实现的功能：设置头部，如果剩余块的大小大于最小块即四字，则进行分割

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static void place(void* bp,size_t asize)
{
    size_t size=GET_SIZE(HDRP(bp));
    
    if(size-asize>=(2*DSIZE))   //进行分割
    {
        PUT(HDRP(bp),PACK(asize,1));
        PUT(FTRP(bp),PACK(asize,1));
        //剩余块
        bp=NEXT_BLKP(bp);       //指向下一个快
        PUT(HDRP(bp),PACK(size-asize,0));     //设置新块的头和尾
        PUT(FTRP(bp),PACK(size-asize,0));
    }
    else
    {
        PUT(HDRP(bp),PACK(size,1));
        PUT(FTRP(bp),PACK(size,1));
    }
}

mm_realloc

1
void *realloc(void *ptr, size_t size)

该函数返回一个指针，指向重新分配的地址。如果失败则返回NULL。

如果ptr为NULL，则会分配一个指定大小的块并返回一个指向它的指针。

如果ptr不为NULL，那么ptr就是指向一个需要重新分配的内存块，此时判断size，size为指定重新分配的大小，如果size为0那么释放该块并返回一个空指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void *mm_realloc(void *ptr, size_t size)
{
    void *newptr=NULL;
    newptr=mm_malloc(size);    //新分配的指定大小的块
    //如果ptr是空的，且newptr分配成功，则直接返回
    if(!ptr)
    {
        printf("ptr为NULL,直接分配\n");
        return newptr;
    }
    //如果非空，则需要复制一下数据
    size_t copy_size=size;      
    size_t before_size=GET_SIZE(HDRP(ptr));
    if(size>before_size)
    {
        copy_size=before_size;   //全复制
    }
    //printf("copy_size=%d\n",copy_size);
    memcpy(newptr,ptr,copy_size);
    mm_free(ptr);
    return newptr;
}

调试策略

可以使用printf辅助调试，可以在关键代码附近打印相关数值，比如在最后的realloc实现中刚开始有些问题，导致测试不通过，提示信息是未能将原块内容复制到新块。然后我就在这里面插了个printf打印copysize，发现打印的结果为copy_size=0，然后就发现问题出现在before那里，使用GET_SIZE(bp)获取了块的大小，因为bp指向的是有效载荷而不是头部，所以正确的做法就是改为GET_SIZE(HDRP(bp))。

测试优化

1
2
3
make       //编译生成驱动程序

./mdriver -V       //-V参数展示详细信息

通过上述代码，实现了一个基于隐式空闲链表、采用首次适配、立即合并策略的分配器，得了72分。

优化以后再研究，现在实在没什么兴趣。。。。。 看见空间利用率、吞吐量我就头疼。。。。