看csapp写内存分配器
浏览数：51 /
时间：2015年06月11日
目标：实现一个放置策略为首次适配，并合策略为立即并合基于隐式空闲链表的内存分配器。
这里使用memlib.c包提供的存储器系统模型，该模型允许我们在不干涉已存在的malloc包的情况下运行分配器，也就是说封装了malloc函数。
memlib.h
void mem_init(void); void *mem_sbrk(int incr);
memlib.c:（封装了malloc函数）
#include <stdio.h>
#include <stdlib.h>
#include "csapp.h"
#define MAX_HEAP (1 << 30)
static char *mem_heap; /* Points to first byte of heap */
static char *mem_brk; /* Points to last byte of heap plus 1 */
static char *mem_max_addr; /* Max legal heap addr plus 1*/
void mem_init(void)
{
mem_heap = (char *)Malloc(MAX_HEAP);
mem_brk = (char *)mem_heap;
mem_max_addr = (char *)(mem_heap + MAX_HEAP);
}
/*
* mem_sbrk - Simple model of the sbrk function. Extends the heap
* by incr bytes and returns the start address of the new area. In
* this model, the heap cannot be shrunk.
*/
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;
}
mm.h
/*************************************************************************
> File Name: mm.h
> Author: connan_d
> Mail: [email protected]
> Created Time: 2015年05月07日 星期四 10时40分49秒
> 定义了内存分配器的接口
************************************************************************/
int mm_init(); //初始化
void *mm_malloc(size_t size); //分配内存
void mm_free(void *bp); //回收内存mm.c
/*************************************************************************
> File Name: mm.c
> Author: connan_d
> Mail: [email protected]
> Created Time: 2015年05月07日 星期四 10时50分51秒
************************************************************************/
#include<stdio.h>
#include "mm.h"
#include "memlib.h"
static void *extend_heap(size_t words); //拓展堆的可用空间，返回原堆顶地址(mem_brk),失败返回NULL
static void *coalesce(void *bp); //并合bp指向块的前后块,返回并合后的块指针
static void *find_fit(size_t size); //寻找第一个空间大于size的空闲块，返回其地址,未找到时，返回NULL
static void place(void *bp, size_t asize); //分割find_fit返回的块，创建块结构
//宏定义
#define WSIZE 4
#define DSIZE 8
#define CHUNKSIZE (1<<12) //每次拓展堆的大小
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define PACK(size, alloc) ((size) | (alloc)) //将块大小和标志位整合到一个字中
#define GET(p) (*(unsigned int *)(p)) //返回p指向的字
#define PUT(p, val) (*(unsigned int *)(p) = (val)) //将值压入p指向的字
#define GET_SIZE(p) (GET(p) & ~0x7) //返回头或尾部的高29位,即该块的大小
#define GET_ALLOC(p) (GET(p) & 0x1) //返回标志位
#define HDRP(bp) ((char *)bp - WSIZE) //返回块的头部
#define FTRP(bp) ((char *)bp + GET_SIZE(bp) - DSIZE) //返回块的尾部
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE((char *)bp - WSIZE)) //当前当块的下一块
#define PREV_BLKP(bp) ((char *)bp - GET_SIZE((char *)bp - DSIZE)) //返回但前块的上一块
static void *heap_listp; //指向第一个块(序言块)
//接口
int mm_init(void) //初始化，成功返回0，失败返回
{
mem_init();
if ( (heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1)
return -1;
PUT(heap_listp, 0);
PUT(heap_listp + WSIZE, PACK(8, 1)); //序言块头部
PUT(heap_listp + 2*WSIZE, PACK(8, 1)); //序言块尾部
PUT(heap_listp + 3*WSIZE, PACK(0, 1)); //结尾块
heap_listp += 2*WSIZE;
if (extend_heap(CHUNKSIZE/WSIZE) == NULL)
return -1;
return 0;
}
void mm_free(void *bp) //释放bp指向块的内存
{
size_t size = GET_SIZE(HDRP(bp));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
coalesce(bp); //并合前后块
}
void *mm_malloc(size_t size) //分配size字节大小的块，返回指向块的指针
{
size_t asize; //调整过的size
size_t extendsize;
void *bp;
if (size == 0)
return NULL;
if (size < DSIZE)
asize = 2 * DSIZE;
else
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;
}
//工具函数定义
static void *extend_heap(size_t words) //拓展堆的可用空间，返回原堆顶地址(mem_brk),失败返回NULL
{
char *bp;
size_t size;
size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE; //保持双字对齐
if ((long)(bp = mem_sbrk(size)) == -1)
return NULL;
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));
return (void *)bp;
}
static void *coalesce(void *bp) //并合bp指向块的前后块,返回并合后的块指针
{
size_t prev_alloc = GET_ALLOC(HDRP(PREV_BLKP(bp))); //上一块是否分配
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); //下一块是否分配
size_t size;
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));
bp = PREV_BLKP(bp);
}
else
{
size += GET_SIZE(HDRP(PREV_BLKP(bp))) +
GET_SIZE(FTRP(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;
}
static void *find_fit(size_t size) //寻找第一个空间大于size的空闲块，返回其地址,未找到时，返回NULL
{
void *bp;
for (bp = heap_listp; GET_SIZE(bp) > 0; bp = NEXT_BLKP(bp))
{
if (GET_SIZE(HDRP(bp)) >= size && GET_ALLOC(HDRP(bp)) != 1) //返回第一块未分配且空间大于size的空闲块
return bp;
}
return NULL;
}
static void place(void *bp, size_t asize) //分割find_fit返回的块，创建块结构
{
size_t bsize = GET_SIZE(HDRP(bp));
if ( (bsize - asize) > 2*DSIZE ) //最小块为16字节,分割块
{
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
bp = NEXT_BLKP(bp);
PUT(HDRP(bp), PACK(bsize - asize, 0));
PUT(FTRP(bp), PACK(bsize - asize, 0));
}
else //不用分割
{
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
}
}
mmTest.c
/*************************************************************************
> File Name: mmTest.c
> Author: connan_d
> Mail: [email protected]
> Created Time: 2015年05月07日 星期四 14时23分30秒
************************************************************************/
#include<stdio.h>
#include "mm.h"
int main()
{
mem_init(); //初始化模型
mm_init(); //初始化分配器
int *a = mm_malloc(sizeof(int)); //测试int
*a = 1;
char *b = mm_malloc(sizeof(char)); //测试char
*b = 'z';
double *c = mm_malloc(sizeof(double)); //测试double
*c = 2.0;
printf("a = %d\nb = %c\nc = %f\n", *a, *b, *c);
}编译链接时需要csapp.h头文件：gcc -o mmtest mmTest.c mm.c memlib.c -lpthread
结果：
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
