| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3879 人关注过本帖, 1 人收藏
标题:malloc lab(问题在贴中)
只看楼主 加入收藏
诠释0x208
Rank: 1
等 级:新手上路
帖 子:14
专家分:0
注 册:2017-12-22
结帖率:50%
收藏(1)
已结贴  问题点数:20 回复次数:4 
malloc lab(问题在贴中)
一、内存系统模型
    内存模型由memlib.c包所提供,允许我们在不干涉malloc系统包的情况下,运行分配器。其中含有以下函数:
    mem_init():用malloc函数得到一个大的、双字对齐的字节数组,视为堆。
    mem_heap变量:指向堆的首地址
    mem_brk变量:指向堆顶,它与mem_heap之间的字节表示已分配的虚拟内存
    mem_sbrk():请求额外的堆内存(让mem_brk增加),且不会收缩堆

二、分配器的函数原型
int mm_init(void);
void *mm_malloc(size_t size);
void mm_free(void *ptr);

mm_init()函数初始化分配器,若成功返回0,否则返回-1。mm_malloc()和mm_free()函数与原始的malloc和free原型和语义相同。这些函数在源文件mm.c中。
分配器对块大小使用双字边界对齐,采用教材图9-39所示的块格式,如下:

最小块大小为16(有效载荷不允许为0),空闲链表组织为一个隐式空闲链表,并具有以下恒定形式:

    第一个字为填充字(不使用),后面紧跟着一个特殊的序言块,这是一个8字节的已分配块,只由一个头部和一个脚部组成。序言块是在初始化时创建,并且永不释放。
    序言块后紧跟的是0个或多个普通块。
    堆总是以一个特殊的结尾块来结束,这个块是一个大小为0的已分配块,只由一个头部组成。
    分配器用一个static的全局变量heap_listp指向序言块。

三、操纵空闲链表的基本常数和宏
    在空闲链表中操作头部和脚部要大量使用强制类型转换和指针运算,因此,预定义一些宏(macro)来访问和遍历空闲链表很有帮助,见教材图9-43。
    PACK(size, alloc):将大小和已分配位打包成一个字(头部/脚部)
    GET(p):返回地址p处的字
    GET_SIZE(p):返回地址p处的字的大小(头部/脚部)
    GET_ALLOC(p):返回地址p处的字的已分配位(头部/脚部)
    bp:该指针表示块指针,即有效载荷第一个字节的地址
    HDRP(bp)/FTRP(bp):返回这个块的头部/脚部地址
    NEXT_BLKP(bp)/PREV_BLKP(bp):返回下一个块/前一个块的块指针

四、创建初始空闲链表
1、mm_init()从内存系统得到4个字,并将它们初始化为填充字、序言块头部、序言块脚部、结尾块。然后调用extend_heap()函数,将堆扩展CHUNKSIZE字节,并创建初始空闲块。(见mm.c)

2、extend_heap()为保持双字对齐,将请求大小向上舍入到最接近的2字倍数,然后调用mem_sbrk()请求额外的堆空间。该空间紧接在结尾块之后。
    巧妙的是,结尾块就作为新空间的头部,而新空间的最后一个字作为新的结尾块。
    最后,由于extend_heap()也可能被mm_malloc()调用,因此很可能旧的块是以一个空闲块结束,因此需要coalesce()函数来合并这两个空闲块。
   
五、释放和合并块
    mm_free()用于释放一个块。该函数释放所请求的块(bp),并调用coalesce()函数来合并与之邻接的空闲块。(4种情况,见图9-40)

六、分配块
    mm_malloc()函数用来分配大小为size的块。函数必须调整请求的大小,从而为头部和脚部留出空间,并满足双字对齐的要求。最小块大小为16字节(载荷不能为0)。
    分配器调整了请求大小之后,会搜索空闲链表,寻找一个合适的空闲块(有多种策略,这里采用首次适配)。如果能找到,就放着这个请求块,并可选地分割出多余的部分;如果不能找到,就调用extend_heap()来扩展堆,并将请求放在这个新空闲块中。最后返回新分配的块
    可选地分割:将请求块放置在空闲块的起始位置,只有当剩余部分的大于等于最小块大小时,才进行分割。

七、编写程序,测试分配器是否正确
随机生成100个整数存入链表,然后输出链表中的所有结点,最后清空整个链表。要求使用自己的动态分配器。
示例程序:test.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "memlib.h"
#include "mm.h"

struct Node
{
    int element;
    struct Node * next;
};

void Insert(struct Node * L, int X)
{
    struct Node *P, *Q;
    P = L;
    while (P->next != NULL)
        P = P->next;
    Q = mm_malloc(sizeof(struct Node));
    Q->element = X;
    Q->next = P->next;
    P->next = Q;
}

void PrintList(struct Node * L)
{
    struct Node *P;
    P = L->next;
    while (P != NULL)
    {
        printf("%d ", P->element);
        P = P->next;
    }
    printf("\n");
}

void ClearList(struct Node * L) // delete all nodes
{
    struct Node *P;

    while (L->next != NULL)
    {
        P = L->next;
        L->next = P->next;
        mm_free(P);
    }
}

int main()
{
    int i;
    struct Node * L;

    mem_init();
    if (mm_init() == -1)
        exit(-1);

    L = mm_malloc(sizeof(struct Node)); // Header
    L->next = NULL;

    srand(time(NULL));
    for (i = 0; i < 100; i ++)
        Insert(L, rand() % 100);

    PrintList(L);
    ClearList(L);
}

示例程序:memlib.h
#include <unistd.h>

void mem_init(void);               
void *mem_sbrk(int incr);


示例程序:mm.h
extern int mm_init(void);
extern void *mm_malloc (size_t size);
extern void mm_free (void *ptr);


示例程序:mm.c
/*
 * Simple, 32-bit and 64-bit clean allocator based on implicit free
 * lists, first-fit placement, and boundary tag coalescing, as described
 * in the CS:APP3e text. Blocks must be aligned to doubleword (8 byte)
 * boundaries. Minimum block size is 16 bytes.
 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#include "mm.h"
#include "memlib.h"

/* Basic constants and macros */
#define WSIZE       4       /* Word and header/footer size (bytes) */
#define DSIZE       8       /* Double word size (bytes) */
#define CHUNKSIZE  (1<<12)  /* Extend heap by this amount (bytes) */  

#define MAX(x, y) ((x) > (y)? (x) : (y))  

/* 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 address 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)))

/* Global variables */
static char *heap_listp = 0;  /* Pointer to first block */  

/* Function prototypes for internal helper routines */
static void *extend_heap(size_t words);
static void place(void *bp, size_t asize);
static void *find_fit(size_t asize);
static void *coalesce(void *bp);

/*
 * mm_init - Initialize the memory manager
 */
int mm_init(void)
{
    /* Create the initial empty heap */
    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);                    

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

/*
 * mm_malloc - Allocate a block with at least size bytes of payload
 */
void *mm_malloc(size_t size)
{
    size_t asize;      /* Adjusted block size */
    size_t extendsize; /* Amount to extend heap if no fit */
    char *bp;      

    /* Ignore spurious requests */
    if (size == 0)
        return NULL;

    /* Adjust block size to include overhead and alignment reqs. */
    if (size <= DSIZE)                                      
        asize = 2*DSIZE;                                   
    else
        asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE);

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

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

/*
 * mm_free - Free a block
 */
void mm_free(void *bp)
{
    if (bp == 0)
        return;

    size_t size = GET_SIZE(HDRP(bp));

    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    coalesce(bp);
}

/*
 * coalesce - Boundary tag coalescing. Return ptr to coalesced block
 */
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) {            /* Case 1 */
        return bp;
    }

    else if (prev_alloc && !next_alloc) {      /* Case 2 */
        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) {      /* Case 3 */
        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 {                                     /* Case 4 */
        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;
}

/*
 * extend_heap - Extend heap with free block and return its block pointer
 */
static void *extend_heap(size_t words)
{
    char *bp;
    size_t size;

    /* Allocate an even number of words to maintain alignment */
    size = (words % 2) ? (words+1) * WSIZE : words * WSIZE;
    if ((long)(bp = mem_sbrk(size)) == -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 previous block was free */
    return coalesce(bp);                                         
}

/*
 * place - Place block of asize bytes at start of free block bp
 *         and split if remainder would be at least minimum block size
 */
static void place(void *bp, size_t asize)
{
    size_t csize = GET_SIZE(HDRP(bp));   

    if ((csize - asize) >= (2*DSIZE)) {
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));
        bp = NEXT_BLKP(bp);
        PUT(HDRP(bp), PACK(csize-asize, 0));
        PUT(FTRP(bp), PACK(csize-asize, 0));
    }
    else {
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
    }
}

/*
 * find_fit - Find a fit for a block with asize bytes
 */
static void *find_fit(size_t asize)
{
    /* First-fit search */
    void *bp;

    for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
            return bp;
        }
    }
    return NULL; /* No fit */
}

示例程序:memlib.c
/*
 * memlib.c - a module that simulates the memory system.  Needed
 * because it allows us to interleave calls from the student's malloc
 * package with the system's malloc package in libc.
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <sys/mman.h>
#include <string.h>
#include <errno.h>

#include "memlib.h"

#define MAX_HEAP (20*(1<<20))  /* 20 MB */

/* Private global variables */
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*/

/*
 * mem_init - Initialize the memory system model
 */
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.c中增加函数printblocks(),功能为扫描整个堆,并输出已分配块和空闲块的数量。在mm_free()函数的最后调用此函数。
2、在分配器中,将搜索策略由首次适配改为最佳适配策略。
3、在mm.c中增加函数mm_realloc(),其功能与realloc()功能一致。编写一个程序测试realloc是否成功。
4、在隐式空闲链表的基础上,实现简单分离存储。
5、将隐式空闲链表改为显式空闲链表。
图片附件: 游客没有浏览图片的权限,请 登录注册
搜索更多相关主题的帖子: void size include block PUT 
2018-07-12 09:41
诠释0x208
Rank: 1
等 级:新手上路
帖 子:14
专家分:0
注 册:2017-12-22
收藏
得分:0 
如果有大佬能解决,附上qq,我能有偿支付
2018-07-12 09:59
MeandC
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:8
帖 子:245
专家分:792
注 册:2018-7-14
收藏
得分:10 
大佬大佬,在下实在是看不懂

C果然是有点难啊!
2018-07-14 23:49
八画小子
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:贵宾
威 望:37
帖 子:709
专家分:2063
注 册:2010-11-11
收藏
得分:10 
以下是引用诠释0x208在2018-7-12 09:59:36的发言:

如果有大佬能解决,附上qq,我能有偿支付

896057905
2018-07-16 08:14
去去去时间简
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2021-6-22
收藏
得分:0 
这不是答案吧答案呢
2021-06-22 09:40
快速回复:malloc lab(问题在贴中)
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.044351 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved