298 lines
9.3 KiB
C
298 lines
9.3 KiB
C
#define MAX(x, y) ((x) > (y) ? (x) : (y))
|
||
/*
|
||
* mm-naive.c - 参考实现，是一个最快的、最低效率的malloc.
|
||
*
|
||
* 在这个参考实现中，分配一个块，仅仅是增加brk指针，
|
||
* 块内部全部是载荷数据，块内没有header或者footer等
|
||
* 管理用的数据信息。分配出去的块，永远不释放或者回收。
|
||
* 重分配函数（realloc）的实现，是直接通过mm_malloc和mm_free实现的
|
||
*
|
||
* 亲们请注意：你需要把此段注释，替换成你的算法设计思想。用描述性
|
||
* 的话来说清楚。
|
||
* 请将此文件，重新命名为mm_201309060024.c（就是mm_你的学号.c）
|
||
*/
|
||
#include <assert.h>
|
||
#include <stdio.h>
|
||
#include <stdlib.h>
|
||
|
||
#ifndef _WIN32
|
||
#include <unistd.h>
|
||
#endif
|
||
#include <string.h>
|
||
|
||
#include "memlib.h"
|
||
#include "mm.h"
|
||
|
||
/*********************************************************
|
||
* 亲们请注意：开始之前，请把下面的信息修改为你的个人信息
|
||
********************************************************/
|
||
team_t team = {
|
||
/* 团队名字 */
|
||
"8-Bit Brainstorm",
|
||
/* 团队老大的名字 */
|
||
"Cikki",
|
||
/* 团队老大的email地址 */
|
||
"c_gh0s7@nudt.edu.cn",
|
||
/* 团队其他成员的名字 (如果没有，就空着) */
|
||
"",
|
||
/* 团队其他成员的email地址 (如果没有，就空着) */
|
||
""};
|
||
|
||
/* 基本常量和宏定义 */
|
||
#define ALIGNMENT 8 /* 将块对齐到8字节（双字） */
|
||
#define ALIGN(size) \
|
||
(((size) + (ALIGNMENT - 1)) & ~0x7) /* 向上舍入到最近的8的倍数 */
|
||
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
|
||
|
||
/* 内存分配器的关键参数 */
|
||
#define WSIZE 4 /* 字（word）的大小 = 4字节 */
|
||
#define DSIZE 8 /* 双字（double word）的大小 = 8字节 */
|
||
#define CHUNKSIZE (1 << 12) /* 扩展堆时的默认大小 = 4096字节 = 4KB */
|
||
|
||
/* 用于操作头部和脚部的宏 */
|
||
#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) /* 获取块大小，去掉低3位的标志位 */
|
||
#define GET_ALLOC(p) (GET(p) & 0x1) /* 获取已分配位（0=空闲，1=已分配）*/
|
||
|
||
/* 给定块指针bp，计算块的头部和脚部位置 */
|
||
#define HDRP(bp) ((char *)(bp) - WSIZE) /* 指向块头部的指针 */
|
||
#define FTRP(bp) \
|
||
((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) /* 指向块脚部的指针 */
|
||
|
||
/* 给定块指针bp，计算下一个和前一个块的地址 */
|
||
#define NEXT_BLKP(bp) \
|
||
((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE))) /* 下一个块的指针 */
|
||
#define PREV_BLKP(bp) \
|
||
((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE))) /* 前一个块的指针 */
|
||
|
||
static char *heap_listp; /* 指向堆的第一个块的指针 */
|
||
|
||
static void *extend_heap(size_t words);
|
||
static void *coalesce(void *bp);
|
||
static void *find_fit(size_t asize);
|
||
static void place(void *bp, size_t asize);
|
||
|
||
static void print_block(int request_id, int payload);
|
||
|
||
/*
|
||
* mm_init - 初始化内存分配器
|
||
* 创建初始空堆，包括序言块和结尾块
|
||
* 返回值：成功返回0，错误返回-1
|
||
*/
|
||
int mm_init(void) {
|
||
// 创建初始空堆
|
||
if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1)
|
||
return -1;
|
||
PUT(heap_listp, 0); // 对齐填充
|
||
PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1)); // 序言块头部
|
||
PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1)); // 序言块尾部
|
||
PUT(heap_listp + (3 * WSIZE), PACK(0, 1)); // 结尾块
|
||
heap_listp += (2 * WSIZE);
|
||
|
||
// 扩展空堆
|
||
if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
|
||
return -1;
|
||
return 0;
|
||
}
|
||
|
||
/*
|
||
* extend_heap - 通过增加brk指针来扩展堆
|
||
* 参数 words: 请求的字数（以字为单位）
|
||
* 返回值：指向新分配区域的指针，如果出错则返回NULL
|
||
*/
|
||
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;
|
||
|
||
// 初始化空闲块头部/尾部和结尾块
|
||
PUT(HDRP(bp), PACK(size, 0)); // 空闲块头部
|
||
PUT(FTRP(bp), PACK(size, 0)); // 空闲块尾部
|
||
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); // 新的结尾块
|
||
|
||
return coalesce(bp);
|
||
}
|
||
|
||
/*
|
||
* coalesce - 合并相邻的空闲块
|
||
* 参数 bp: 指向刚被释放的块的指针
|
||
* 返回值：指向合并后的块的指针
|
||
*
|
||
* 有四种情况：
|
||
* Case 1：前后块都已分配
|
||
* Case 2：前块已分配，后块空闲
|
||
* Case 3：前块空闲，后块已分配
|
||
* Case 4：前后块都空闲
|
||
*/
|
||
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;
|
||
}
|
||
|
||
/*
|
||
* mm_malloc - 分配一个大小为size字节的块
|
||
* 参数 size: 请求的字节数
|
||
* 返回值：指向新分配块的指针，如果错误则返回NULL
|
||
*
|
||
* 分配策略：
|
||
* 1. 调整请求大小为8字节对齐
|
||
* 2. 搜索空闲链表找到第一个适合的块
|
||
* 3. 如果没有找到合适的块，扩展堆
|
||
*/
|
||
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
|
||
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;
|
||
}
|
||
|
||
/*
|
||
* mm_free - 释放一个之前分配的块
|
||
* 参数 bp: 指向要释放的块的指针
|
||
*
|
||
* 处理步骤：
|
||
* 1. 标记块为空闲（更新头部和脚部）
|
||
* 2. 合并相邻的空闲块（如果有的话）
|
||
*/
|
||
void mm_free(void *bp) {
|
||
if (bp == NULL)
|
||
return;
|
||
|
||
size_t size = GET_SIZE(HDRP(bp));
|
||
PUT(HDRP(bp), PACK(size, 0));
|
||
PUT(FTRP(bp), PACK(size, 0));
|
||
coalesce(bp);
|
||
}
|
||
|
||
/*
|
||
* mm_realloc - 调整一个已分配块的大小
|
||
* 参数：
|
||
* ptr - 指向旧块的指针
|
||
* size - 请求的新大小
|
||
* 返回值：指向新块的指针
|
||
*
|
||
* 处理策略：
|
||
* 1. 如果ptr为NULL，等同于malloc
|
||
* 2. 如果size为0，等同于free
|
||
* 3. 分配新块，复制数据，释放旧块
|
||
*/
|
||
void *mm_realloc(void *ptr, size_t size) {
|
||
if (ptr == NULL)
|
||
return mm_malloc(size);
|
||
|
||
if (size == 0) {
|
||
mm_free(ptr);
|
||
return NULL;
|
||
}
|
||
|
||
void *newptr = mm_malloc(size);
|
||
if (newptr == NULL)
|
||
return NULL;
|
||
|
||
size_t copySize = GET_SIZE(HDRP(ptr)) - DSIZE;
|
||
if (size < copySize)
|
||
copySize = size;
|
||
memcpy(newptr, ptr, copySize);
|
||
mm_free(ptr);
|
||
return newptr;
|
||
}
|
||
|
||
/*
|
||
* find_fit - 使用首次适配搜索，查找满足所需大小的空闲块
|
||
* 参数 asize: 调整后的块大小
|
||
* 返回值：找到则返回块指针，否则返回NULL
|
||
*/
|
||
static void *find_fit(size_t asize) {
|
||
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;
|
||
}
|
||
|
||
/*
|
||
* place - 将请求的块放置在空闲块的起始位置
|
||
* 参数：
|
||
* bp - 空闲块指针
|
||
* asize - 请求的大小
|
||
*
|
||
* 如果剩余部分足够大（>= 2*DSIZE），则分割块
|
||
*/
|
||
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));
|
||
}
|
||
}
|
||
|
||
/*
|
||
* mm_heapcheck - 目前暂不支持堆检查，可以不用修改
|
||
*/
|
||
void mm_heapcheck(void) {}
|
||
|
||
/*
|
||
* 输出一块数据 - 用于heapcheck，然而在此并没有什么用，可以不用修改
|
||
*/
|
||
|
||
static void print_block(int request_id, int payload) {
|
||
printf("\n[%s]$BLOCK %d %d\n", __func__, request_id, payload);
|
||
}
|