实验要求实现内存分配功能,关于内存分配的方法机制已经非常多了,本文主要尝试使用红黑树来实现内存空间的管理和分配,完整代码可见GitHub

原理

内存块

对于一个内存块来说,除了本身内存区域之外,通常还需要保存区域大小和是否空闲等信息。在内存管理过程中,通常需要合并相邻的内存空间,为了方便检查相邻空间的大小和空闲状态,内存块信息在头部和尾部各保留一份。需要注意的是,内存区大小包含了头部和尾部的占用空间。

Block size
Block size
0 0 a
0 0 a
Payload
(allocated block only)
Payload<div>(allocated block only)</div>
Padding (optional)
Padding (optional)
3 2 1 0
3 2 1 0
31
31
a = 1: Allocated
a = 0: Free
[Not supported by viewer]
Block size
Block size
0 0 a
0 0 a
Header
Header
Footer
Footer

为了方便访问内存块的信息,需要以下的宏定义:

/* Basic constants and macros */
#define WSIZE               4
#define DSIZE               8
#define QSIZE		        16

/* Pack a size and allocated bit into a word */
#define PACK(size, alloc)   ((size) | (alloc))

/* Read and write a word at address p */
#define GET(p)              (*(unsigned int*)(p))
#define PUT(p, val)         (*(unsigned int*)(p) = (val))

/* Read the size and allocated fields from adress p */
#define GET_SIZE(p)         (GET(p) & ~0x7)
#define GET_ALLOC(p)        (GET(p) & 0x1)

/* Given block ptr bp, compute address of its header and footer */
#define HDRP(bp)            ((char*)(bp) - WSIZE)
#define FTRP(bp)            ((char*)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

/* Given block ptr bp, compute address of next and previous blocks */
#define NEXT_BLKP(bp)       ((char*)(bp) + GET_SIZE(((char*)(bp) - WSIZE)))
#define PREV_BLKP(bp)       ((char*)(bp) - GET_SIZE(((char*)(bp) - DSIZE)))

红黑树

内存分配中最消耗时间的操作就是寻找合适的空闲空间,常见的链表法都是线性查找,查找时间最差情况下是,效率不是很高。为了提高查找效率,可以使用平衡树追踪所有的空闲空间,红黑树是比较理想的选择。

实现红黑树是一件非常麻烦的事情,所以本文使用的红黑树从Emin Martinian实现的红黑树版本上修改而来:red_black_tree.hred_black_tree.c。修改的内容如下:

  • 实现大于等于查询,相当于实现了最佳适配算法
  • 将所有动态内存内容删除,使用外部传入指针的方式代替
  • 删除一些不需要的功能(例如释放、打印等)

使用了红黑树之后,内存块的最小大小也就有了限制:

#define BLK_HDFT_SIZE       DSIZE
#define BLK_LINK_SIZE       (sizeof(rbt_node))
#define BLK_MIN_SIZE        ((BLK_HDFT_SIZE+BLK_LINK_SIZE+DSIZE-1)/DSIZE*DSIZE)

在使用红黑树之前,需要定义树结构体、树根节点、哨兵节点以及比较函数。

static rbt_tree tree;
static rbt_node root;
static rbt_node nil;

int compare(const void* lhs, const void* rhs)
{
    return lhs < rhs;
}

实现

insert_free_block

将空闲内存块加入红黑树。

static void insert_free_block(void *bp)
{
    rbt_node *np = (rbt_node *) bp;
    np->key = (void *) GET_SIZE(HDRP(bp));
    rbt_insert(&tree, np);
}

remove_free_block

将空闲块从红黑树中删除。

static void remove_free_block(void *bp)
{
    rbt_node *np = (rbt_node *) bp;
    rbt_remove(&tree, np);
}

coalesce

尝试将空闲内存块和相邻的内存块合并。

static void *coalesce(void *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) {        
    	insert_free_block(bp);
        return bp;
    } else if (prev_alloc && !next_alloc) { 
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        remove_free_block(NEXT_BLKP(bp));
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
        insert_free_block(bp);
    } else if (!prev_alloc && next_alloc) { 
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        remove_free_block(PREV_BLKP(bp));
        PUT(FTRP(bp), PACK(size, 0));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
        insert_free_block(bp);
    } else {                                
        size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
        remove_free_block(PREV_BLKP(bp));
        remove_free_block(NEXT_BLKP(bp));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
        insert_free_block(bp);
    }
    return bp;
}

extend_heap

扩展堆空间,将新申请的空间初始化为一块空闲内存区域,更新尾部标记,最后调用合并操作。

static void *extend_heap(size_t words)
{
    /* Allocate an even number of words to maintain alignment */
    size_t size = (words % 2) ? (words+1) * WSIZE : words * WSIZE;
    char *bp = mem_sbrk(size);
    if ((long)(bp) == -1)
        return NULL;

    /* Initialize free block header/footer and the epilogue header */
    PUT(HDRP(bp), PACK(size, 0));           /* Free block header */
    PUT(FTRP(bp), PACK(size, 0));           /* Free block footer */
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));   /* New epilogue header*/

    /* Coalesce if the prvious block was free */
    return coalesce(bp);
}

find_fit

在红黑树中找到满足要求的最小空间。

static void *find_fit(size_t asize)
{
    /* Available block not found */
    rbt_node *np = rbt_query_ge(&tree, (void *) asize);
    return np;
}

place

修改内存区域的空闲位,如果内存空间有剩余,那么将剩余空间重新加入红黑树。

static void place(void *bp, size_t asize)
{
    int free_size = GET_SIZE(HDRP(bp));
    int used_size = (free_size - asize >= BLK_MIN_SIZE) ? asize : free_size;
    int left_size = free_size - used_size;

    remove_free_block(bp);

    /* Place block */
    PUT(HDRP(bp), PACK(used_size, 1));
    PUT(FTRP(bp), PACK(used_size, 1));

    /* Place left block */
    if (left_size) {
        PUT(HDRP(NEXT_BLKP(bp)), PACK(left_size, 0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(left_size, 0));
        insert_free_block(NEXT_BLKP(bp));
    }
}

mm_init

初始化头尾内存块的同时初始化红黑树。

int mm_init(void)
{
    /* Create the initial empty heap */
    char *heap_listp;
    if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1)
        return -1;
    PUT(heap_listp, 0);

    /* Alignment padding */
    PUT(heap_listp + (1*WSIZE), PACK(DSIZE, 1)); /* Prologue header */
    PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1)); /* Prologue footer */
    PUT(heap_listp + (3*WSIZE), PACK(0, 1));

    /* Epilogue header */
    heap_listp += (2*WSIZE);

    rbt_init(&tree, &nil, &root, compare);

    /* Extend the empty heap with a free block of CHUNKSIZE bytes */
    if (extend_heap(CHUNKSIZE/WSIZE) == NULL)
        return -1;
    return 0;	
}

mm_malloc

如果请求大小为零,那么就不需要分配。然后,需要计算加上头部和尾部并且对齐后需要的内存大小,由于内存空闲在空闲的时候需要保存红黑树的节点,所以内存区域的大小不能小于足够保存红黑树的内存空间大小。首先需要寻找满足空间大小的内存块,如果找不到需要扩大堆空间。

void *mm_malloc(size_t size)
{
    /* Ignore spurious request */
    if (size == 0)
        return NULL;

    /* Adjust size */
    size_t asize = DSIZE * ((size + BLK_HDFT_SIZE + (DSIZE-1)) / DSIZE);
    if (asize <= BLK_MIN_SIZE)
        asize = BLK_MIN_SIZE;

    /* Search for free list for a fit */
    char *bp;
    if ((bp = find_fit(asize)) != NULL) {
        place(bp, asize);
        return bp;
    }

    /* No fit found. Get more memory and place the block */
    size_t extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
        return NULL;
    place(bp, asize);
    return bp;
}

mm_free

将区域标记为空闲后调用合并操作。

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_realloc

为了充分利用空间,我分了以下几种情况:

  • 如果大小参数为0,那么函数的做用就等同于mm_free;
  • 如果指针参数是NULL,那么函数的作用就等同于mm_malloc;
  • 然后继续分类讨论:
    • 如果新间的大小等于原空间的大小,那么什么事都不用做;
    • 如果新空间大小小于原空间的大小,那么把原空间缩小就好了;
    • 如果新空间大小大于原空间的大小,那么尝试与原空间的前后控件合并,如果无法合并就用mm_malloc重新分配一个空间。
void *mm_realloc(void *bp, size_t size)
{
    /* If ptr equals to NULL, do malloc */
    if (bp == NULL)
        return mm_malloc(size);

    /* If size equals to 0, do free */
    if (size == 0) {
        mm_free(bp);
        return NULL;
    }

    /* Calculate new block size */
    size_t asize = DSIZE * ((size + BLK_HDFT_SIZE + (DSIZE-1)) / DSIZE);
    if (asize <= BLK_MIN_SIZE)
        asize = BLK_MIN_SIZE;

    /* Get information about block size and allocate status */
    size_t next_alloc   = GET_ALLOC (HDRP(NEXT_BLKP(bp)));
    size_t prev_alloc   = GET_ALLOC (HDRP(PREV_BLKP(bp)));
    size_t next_size    = GET_SIZE  (HDRP(NEXT_BLKP(bp)));
    size_t prev_size    = GET_SIZE  (HDRP(PREV_BLKP(bp)));
    size_t old_size     = GET_SIZE  (HDRP(bp));
    size_t copy_size    = MIN       (old_size-BLK_HDFT_SIZE, size);

    /* New block size is equal or smaller than old block */
    if (asize <= old_size) {           
    	size_t used_size = (old_size - asize >= BLK_MIN_SIZE) ? asize : old_size;
    	size_t left_size = old_size - used_size;
    	PUT(HDRP(bp), PACK(used_size, 1));
    	PUT(FTRP(bp), PACK(used_size, 1));
    	if (left_size) {
    		PUT(HDRP(NEXT_BLKP(bp)), PACK(left_size, 0));
    		PUT(FTRP(NEXT_BLKP(bp)), PACK(left_size, 0));
    		insert_free_block(NEXT_BLKP(bp));
    	}
        return bp;
    } 

    /* New block size is bigger than old block */
    if (!next_alloc && prev_alloc && old_size + next_size >= asize) {	
        /* Merge with next free block */
        size_t merged_size = old_size + next_size;
    	size_t used_size = (merged_size - asize >= BLK_MIN_SIZE) ? asize : merged_size;
    	size_t left_size = merged_size - used_size;
        remove_free_block(NEXT_BLKP(bp));
    	PUT(HDRP(bp), PACK(used_size, 1));
    	PUT(FTRP(bp), PACK(used_size, 1));
    	if (left_size) {
    		PUT(HDRP(NEXT_BLKP(bp)), PACK(left_size, 0));
    		PUT(FTRP(NEXT_BLKP(bp)), PACK(left_size, 0));
    		insert_free_block(NEXT_BLKP(bp));
    	}
    	return bp;
    } else if (!prev_alloc && next_alloc && old_size + prev_size >= asize) {	
        /* Merge with previous free block */
        size_t merged_size = old_size + prev_size;
        size_t used_size = (merged_size - asize >= BLK_MIN_SIZE) ? asize : merged_size;
    	size_t left_size = merged_size - used_size;
    	char *nbp = PREV_BLKP(bp);
    	remove_free_block(nbp);
        memmove(nbp, bp, copy_size);
    	PUT(HDRP(nbp), PACK(used_size, 1));
    	PUT(FTRP(nbp), PACK(used_size, 1));
    	if (left_size) {
    		PUT(HDRP(NEXT_BLKP(nbp)), PACK(left_size, 0));
    		PUT(FTRP(NEXT_BLKP(nbp)), PACK(left_size, 0));
    		insert_free_block(NEXT_BLKP(nbp));
    	}
    	return nbp;
    } else if (!prev_alloc && !next_alloc && prev_alloc + old_size + next_size >= asize) {	
        /* Merge with previous and next free block */
        size_t merged_size = old_size + prev_size + next_size;
    	size_t used_size = (merged_size - asize >= BLK_MIN_SIZE) ? asize : merged_size;
    	size_t left_size = merged_size - used_size;
        char *nbp = PREV_BLKP(bp);
        remove_free_block(PREV_BLKP(bp));
    	remove_free_block(NEXT_BLKP(bp));
        memmove(nbp, bp, copy_size);
    	PUT(HDRP(nbp), PACK(used_size, 1));
    	PUT(FTRP(nbp), PACK(used_size, 1));
    	if (left_size) {
    		PUT(HDRP(NEXT_BLKP(nbp)), PACK(left_size, 0));
    		PUT(FTRP(NEXT_BLKP(nbp)), PACK(left_size, 0));
    		insert_free_block(NEXT_BLKP(nbp));
    	}
    	return nbp;
    }

    /* Malloc new space */
    char *nbp = mm_malloc(size);
    if (nbp == NULL)
    	return NULL;
    memmove(nbp, bp, copy_size);
    mm_free(bp);
    return nbp;
}