内容纲要
我****！
Malloc Lab是ICS（计算机系统概论）这门课最鬼畜的作业...没有之一。
具体内容差不多就是要你用C实现：
malloc函数：
给定内存大小S，分配大小为S的连续内存，返回一个指针。free函数
给定一个malloc或者realloc返回的指针，释放malloc/realloc分配的内存。realloc函数
给定一个malloc或者realloc返回的指针和新的内存大小S，为这个指针所代表的连续内存块重新分配大小为S的内存。
你能使用的函数只有sbrk，目标是最大化单位时间的内存流量与峰值内存利用率的加权和。
思路
正确的思路应该是分块链表...即，使用链表维护大小不超过8, 16, 24, 32,64, ...一些空余内存块，然后直接分配即可，能拿到几乎满分...
但是我走了邪路...写了Treap，最后只拿了79分，但是舍不得这么大一堆代码，于是使用分块链表复合优化了一下，最终内存利用率还是上不去，拿了84分...写了大约20个小时，几个版本的代码，极度恶心...
恶心到我都不想继续写这篇博客了，一想到malloc就生理不适，唉，直接把代码贴上来吧。
代码
/*
* mm.c
* Treap套分块的分块链表
* 使用Treap直接维护较大的空闲内存段，提高峰值内存利用率，同时使用Treap维护分块链表块，用分块链表维护小内存块，加速运行。
*
* 分块链表块中的节点串接成普通单相链表，分块链表块头串接成双向链表，维护较小的内存段，提高运行速度。
* 对于每个Treap维护的空段，如此安排内存（括号内为占用空间大小/byte）：
* size+used[0](4)|fa_offset(4)|chl_offset(4)|chr_offset(4)|key(4)|空闲内存空间|size+used(4)[0](大端法存储)
* 使用一个指针指向当前根节点。
* 使用Treap成批为分块链表分配内存，对于每个链表节点组，如此安排内存：
* size+used[1](4)|count(2)|ulen(2)|prev(4)|next(4)|分块链表节点|head+used[1|(4)(大端法存储)
* 其中，ulen表示分块链表每个节点的大小，prev和next表示下一个和上一个链表块头的地址，而head表示当前链表块内链表头地址。
* 真正的数据由分块链表节点组成，每个节点：
* next(4)|head(4)|数据
* 其中head保留到链表组头的offset
* 该链表节点在分配之后为：
* size+used[1](4)|head(4)|数据
* 对于每个其它Treap已分配的段，如此安排内存：
* size+used[1](4)|padding(4)|数据|used[1](1)
* 这样，长度为8k的段可以存放至多8k-9字节的数据，footer处的used标签可以被用来识别这个段的类型
* malloc：
* 小块（小于等于64）：使用分块链表存储
* 大块：先从Treap中查询BestFit，查询成功直接使用，否然扩充堆，直到末尾的空余块加上新扩充的内存能够支持这次malloc，并加以分配
* free：
* 小块：free掉块，如果整个链表块都free了，用Treapfree掉整个块，减少内存碎片。
* 大块：free掉块，看看左右相邻块是否是空闲的，如果是空闲的，那么进行合并并更新Treap，否然free掉的块自建一个Treap节点并插入
* realloc：
* 大块扩大块：尝试在不扩充堆的情况下向后扩展，如果失败，那么调用malloc重新分配内存后拷贝，然后free掉整个块。
* 其它情况：malloc，然后拷贝后free
* calloc：略
*/
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include "mm.h"
#include "memlib.h"
/* If you want debugging output, use the following macro. When you hand
* in, remove the #define DEBUG line. */
//#define DEBUG
#define ITER_LIM 1000 // 死循环检查
#ifdef DEBUG
# define dbg_printf(...) printf(__VA_ARGS__)
#else
# define dbg_printf(...)
#endif
/* do not change the following! */
#ifdef DRIVER
/* create aliases for driver tests */
#define malloc mm_malloc
#define free mm_free
#define realloc mm_realloc
#define calloc mm_calloc
#endif /* def DRIVER */
/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8
/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(p) (((size_t)(p) + (ALIGNMENT-1)) & ~0x7)
/* 我的宏定义 */
/* 大小端转换，这个写成函数好一点 */
inline unsigned B2S_S2B(unsigned a) {
return (((a&0xffu)<<24)+((a&0xff00u)<<8)+((a&0xff0000u)>>8)+(((a&0xff000000u)>>24)&0xffu));
}
#define ISNULL(v) (v == 0)
/* Treap宏定义 */
/* 父节点指针 */
#define TR_FAP(p) (_mem_heap_lo()+(*((unsigned*)(p+4))))
/* 左儿子节点指针 */
#define TR_LCP(p) (_mem_heap_lo()+(*((unsigned*)(p+8))))
/* 右儿子节点指针 */
#define TR_RCP(p) (_mem_heap_lo()+(*((unsigned*)(p+12))))
/* 节点总大小 */
#define TR_SZ(p) (*((unsigned*)(p)))
/* Treap节点key值 */
#define TR_KEY(p) (*((unsigned*)(p+16)))
/* 对应的SET系列函数 */
#define TR_SETFAP(p, v) (*((unsigned*)(p+4)) = (unsigned)(v-_mem_heap_lo()))
#define TR_SETLCP(p, v) (*((unsigned*)(p+8)) = (unsigned)(v-_mem_heap_lo()))
#define TR_SETRCP(p, v) (*((unsigned*)(p+12)) = (unsigned)(v-_mem_heap_lo()))
#define TR_SETSZ(p, v) (*((unsigned*)(p)) = v)
#define TR_SETKEY(p, v) (*((unsigned*)(p+16)) = v)
/* 这个函数用于更新footer */
#define TR_SETFT(p) (*((unsigned*)(p+TR_SZ(p)-4)) = B2S_S2B(TR_SZ(p)))
/* 支撑大小为s字节的数据，至少需要多大的节点 */
#define TR_NEEDED(s) max(ALIGN(s+9), TR_MINSZ)
/* 除了未分配链表节点外的任何段的大小的宏定义 */
#define SG_SZ(p) (*((unsigned*)(p))&(~7))
/* 分块链表宏定义 */
/* 单节点操作 */
#define LS_NXT(p) (_mem_heap_lo()+(*((unsigned*)(p))))
#define LS_HEAD(p) (_mem_heap_lo()+(*((unsigned*)(p+4))))
#define LS_SETNXT(p, v) ((*((unsigned*)(p))) = (v-_mem_heap_lo()))
#define LS_SETHEAD(p, v) ((*((unsigned*)(p+4))) = (v-_mem_heap_lo()))
/* 判断一个已分配段是不是链表节点分配出去的 */
#define LSALLOCED(p) !((*((unsigned*)(p)))&1)
/* 链表块头操作 */
#define LSH_CNT(p) (*((unsigned short*)(p+4)))
#define LSH_ULEN(p) (*((unsigned short*)(p+6)))
#define LSH_INCRCNT(p) (++(*((unsigned short*)(p+4))))
#define LSH_DECRCNT(p) (--(*((unsigned short*)(p+4))))
#define LSH_SETCNT(p, v) ((*((unsigned short*)(p+4))) = v)
#define LSH_SETULEN(p, v) ((*((unsigned short*)(p+6))) = v)
#define LSH_HEAD(p) (_mem_heap_lo()+(B2S_S2B(*((unsigned*)(p+SG_SZ(p)-4)))-1))
#define LSH_PREV(p) (_mem_heap_lo()+(*((unsigned*)(p+8))))
#define LSH_NEXT(p) (_mem_heap_lo()+(*((unsigned*)(p+12))))
#define LSH_SETHEAD(p, v) ((*((unsigned*)(p+SG_SZ(p)-4))) = (B2S_S2B((v-_mem_heap_lo())+1)))
#define LSH_SETPREV(p, v) ((*((unsigned*)(p+8))) = (v-_mem_heap_lo()))
#define LSH_SETNEXT(p, v) ((*((unsigned*)(p+12))) = (v-_mem_heap_lo()))
/* 该链表块节点总数 */
#define LSH_MAXCNT(p) ((SG_SZ(p)-20)/(LSH_ULEN(p)+8))
/* 链表块表操作 */
#define L_TABLE(s) (l_table[s]+_mem_heap_lo())
#define L_SETTABLE(s, v) (l_table[s] = v-_mem_heap_lo())
/* 常量定义 */
/* 容纳单个Treap节点的最小大小 */
#define TR_MINSZ 24
/* 虚拟空Treap节点 */
#define MNULL (_mem_heap_lo())
/* 每次扩充堆时扩充的对齐的大小 */
#define PUSHSIZE 4096
/* 按照页面对齐 */
#define ALIGNPUSH(x) (x+PUSHSIZE-1)&(~(PUSHSIZE-1))
/* 每次为分块链表分配节点时至少直接拿出这么长的Treap节点 */
#define LISTSIZE 512+64
/* 每次为分块链表分配节点时至少一次分配这么多分块链表节点 */
#define LISTNODE 16
/* 分块链表大小对齐函数 */
#define LSM_ALIGN(x) ((x+7)&(~7))
/* 分块链表分类-大小转换函数 */
#define LSM_S2C(x) ((x)/8-1)
#define LSM_C2S(x) ((x)*8+8)
/* 分块链表处理64大小之内的malloc请求 */
#define LISTPROC 32
/* 分为8类 */
#define LISTCLASSES 4
#ifdef DEBUG
#define checkheap(...) mm_checkheap(__VA_ARGS__)
void dbg_cycle();
#else
#define checkheap(...)
#endif
void * memhlo;
/* 将函数调用换做常量调用，极大加速 */
#define _mem_heap_lo() memhlo
/* 助手函数 */
inline unsigned min(unsigned a, unsigned b) {return a < b ? a : b;}
inline unsigned max(unsigned a, unsigned b) {return a > b ? a : b;}
/* Treap全局变量 */
/* 指向Treap根节点的指针 */
void * g_rootptr;
/* 树结构起始点 */
void * g_treap;
/* Treap基本函数 */
inline void rotate (void * u) {
void * v = TR_FAP(u);
void * f = TR_FAP(v);
if(TR_LCP(v) == u) {
TR_SETLCP(v, TR_RCP(u));
if(TR_RCP(u) != MNULL) TR_SETFAP(TR_RCP(u), v);
TR_SETRCP(u, v);
TR_SETFAP(u, f);
TR_SETFAP(v, u);
} else {
TR_SETRCP(v, TR_LCP(u));
if(TR_LCP(u) != MNULL) TR_SETFAP(TR_LCP(u), v);
TR_SETLCP(u, v);
TR_SETFAP(u, f);
TR_SETFAP(v, u);
}
if(f != MNULL) {
if(TR_LCP(f) == v) TR_SETLCP(f, u);
else TR_SETRCP(f, u);
}
if(v == g_rootptr) g_rootptr = u;
}
inline void adjust (void * u) {
#ifdef DEBUG
int _cnt = 0;
#endif
while(TR_FAP(u) != MNULL && TR_KEY(u) > TR_KEY(TR_FAP(u))) {
rotate(u);
#ifdef DEBUG
if(++_cnt > ITER_LIM) {
dbg_printf("iteration limit exceeded in function insert.\n");
dbg_cycle();
}
#endif
}
}
inline void sink (void * u) {
#ifdef DEBUG
int _cnt = 0;
#endif
void * t1, * t2;
while(1) {
t1 = TR_LCP(u);
t2 = TR_RCP(u);
if(t1 == MNULL && t2 == MNULL) return ;
if(t1 != MNULL && t2 != MNULL) {
if(TR_KEY(t1) > TR_KEY(t2)) rotate(t1);
else rotate(t2);
} else if(t1 != MNULL) rotate(t1);
else rotate(t2);
#ifdef DEBUG
if(++_cnt > ITER_LIM) {
dbg_printf("iteration limit exceeded in function sink, u:%p.\n", u);
dbg_cycle();
}
#endif
}
}
inline void erase (void * u) {
sink(u);
if(u != g_rootptr) {
if(TR_LCP(TR_FAP(u)) == u) TR_SETLCP(TR_FAP(u), MNULL);
else TR_SETRCP(TR_FAP(u), MNULL);
} else {
g_rootptr = MNULL;
}
}
inline void * newnode (void * u, unsigned tr_size, void * f) {
TR_SETFAP(u, f);
TR_SETLCP(u, MNULL);
TR_SETRCP(u, MNULL);
TR_SETKEY(u, rand());
TR_SETSZ(u, tr_size);
TR_SETFT(u);
return u;
}
inline void * insert (void * u) {
if(g_rootptr == MNULL) {
g_rootptr = u;
return u;
}
void * l = g_rootptr;
void * p = MNULL;
#ifdef DEBUG
int _cnt = 0;
#endif
while(l != MNULL) {
p = l;
if(TR_SZ(l) > TR_SZ(u)) l = TR_LCP(l);
else l = TR_RCP(l);
#ifdef DEBUG
if(++_cnt > ITER_LIM) {
dbg_printf("iteration limit exceeded in function insert.\n");
dbg_cycle();
}
#endif
}
if(TR_SZ(p) > TR_SZ(u)) TR_SETLCP(p, u);
else TR_SETRCP(p, u);
TR_SETFAP(u, p);
adjust(u);
return u;
}
/* 查询BestFit函数，失败时返回MNULL，此处bsize应该由TR_NEEDED生成*/
inline void * query (unsigned tr_needed) {
void * u = g_rootptr;
void * low = MNULL;
unsigned lowval = ~0;
#ifdef DEBUG
int _cnt = 0;
#endif
while(u != MNULL) {
unsigned t = TR_SZ(u);
if(t == tr_needed) return u;
else if(t > tr_needed) {
if(t < lowval) {
lowval = t;
low = u;
}
u = TR_LCP(u);
} else u = TR_RCP(u);
#ifdef DEBUG
if(++_cnt > ITER_LIM) {
dbg_printf("iteration limit exceeded in function query.\n");
dbg_cycle();
}
#endif
}
return low;
}
/* 内存助手函数 */
/* 将某一段（或者某一段的部分）内存转化为已分配内存，返回内存数据起始地址 */
inline void * serve (void * u, unsigned sz) {
*((char*)(u+sz-1)) = 1;
*((unsigned*)u) = sz|1;
return u+8;
}
/* 取出紧接在brk前面的Treap节点，如果没有，那么返回MNULL */
inline void * tailnode () {
if(!((*((char*)mem_heap_hi()))&1)) { /* 是一个Treap节点 */
return mem_heap_hi()-B2S_S2B(*((unsigned*)(mem_heap_hi()-3)))+1;
} else return MNULL;
}
unsigned _push_heap_alloc;
/* 按照PUSHSIZE将堆推高，并把推高后的堆末尾的字节塞入Treap */
inline void * push_heap (unsigned more) {
unsigned aligned = ALIGNPUSH(more);
void * t = mem_sbrk(aligned);
if((long)t < 0) return NULL;
if(aligned >= TR_MINSZ+more) {
insert(newnode(t+more, aligned-more, MNULL));
_push_heap_alloc = more;
} else _push_heap_alloc = aligned;
return t;
}
/* 前向声明 */
void * treap_malloc (size_t size) ;
/* 分块链表全局变量 */
/* 指向链表头的指针数组 */
unsigned* l_table;
/* 分块链表助手函数 */
/* 初始化链表块 */
void list_init (void * ptr, unsigned size) {
dbg_printf("new list block: %p\n", ptr-8);
unsigned short nodes = (*((unsigned*)(ptr-8))-1-20)/(size+8); // 计算实际分配的内存大小以及可用节点数
void * head = ptr-8;
LSH_SETCNT(head, 0); // 设置链表块头属性
LSH_SETULEN(head, size);
LSH_SETHEAD(head, head+16);
for(int i = 0; i<nodes-1; i++) { // 初始化链表结构
LS_SETHEAD(head+16+i*(size+8), head);
LS_SETNXT(head+16+i*(size+8), head+16+(i+1)*(size+8));
}
LS_SETHEAD(head+16+(nodes-1)*(size+8), head); // 处理链表尾部
LS_SETNXT(head+16+(nodes-1)*(size+8), MNULL);
LSH_SETNEXT(head, L_TABLE(LSM_S2C(size))); // 拼接链表块
LSH_SETPREV(head, MNULL);
L_SETTABLE(LSM_S2C(size), head);
}
/* 扩充链表块 */
inline void list_require (unsigned size) {
unsigned needed = max(LISTSIZE-9, (size+8)*LISTNODE); // 计算块大小
void * ptr = treap_malloc(needed); // 使用Treap分配整块内存
list_init(ptr, size);
}
/* 主程序 */
/*
* Initialize: return -1 on error, 0 on success.
*/
int mm_init(void) {
dbg_printf("init\n");
srand(19260817); // 使用一个膜法素数初始化随机函数，让Treap的运行时间-1s
memhlo = mem_heap_lo();
void * mnull = mem_sbrk(TR_MINSZ); // 为MNULL节点分配空间
if((long)mnull < 0) return -1;
newnode(mnull, TR_MINSZ, MNULL);
l_table = mem_sbrk(4*LISTCLASSES); // 为分块链表头部表分配空间
if((long)l_table < 0) return -1;
memset(l_table, 0, 4u*LISTCLASSES); // 清零
g_treap = g_rootptr = mem_sbrk(TR_MINSZ); // 初始化根节点
if((long)g_rootptr < 0) return -1;
else newnode(g_rootptr, TR_MINSZ, MNULL);
void * tmp = mem_sbrk(PUSHSIZE-TR_MINSZ*2-4*LISTCLASSES);
if((long)tmp < 0) return -1;
insert(newnode(tmp, PUSHSIZE-TR_MINSZ*2-4*LISTCLASSES, MNULL)); // 初始化第一个页面
return 0;
}
/*
* treap来管理大块内存分配
*/
unsigned _m_lst = 0;
void * treap_malloc (size_t size) {
unsigned needed = TR_NEEDED(size);
unsigned m_lst = _m_lst;
_m_lst = needed;
void * tr_node = query(needed);
if(tr_node != MNULL) { // 有空闲段可以分配
unsigned tr_sz = TR_SZ(tr_node);
if(tr_sz-needed < TR_MINSZ) { // 分裂节点后的剩余空间不足，不能分裂节点
erase(tr_node); // 把节点整个用掉
return serve(tr_node, tr_sz); // 分配内存
} else { // 我裂开来
erase(tr_node); // 删掉
if(needed <= m_lst) { // 大小相对较小，放在前面
void * ntr_node = tr_node+needed;
newnode(ntr_node, tr_sz-needed, MNULL); // 创建新节点
insert(ntr_node); // 插入新节点
return serve(tr_node, needed); // 分配内存
} else { // 放在后面
void * ntr_node = tr_node;
newnode(ntr_node, tr_sz-needed, MNULL); // 创建新节点
insert(ntr_node); // 插入新节点
return serve(tr_node+tr_sz-needed, needed); // 分配内存
}
}
} else { // 莫得空闲段能够容纳它了！
tr_node = tailnode(); // 尝试拿出一个连在brk前面的空闲段
if(tr_node == MNULL) { // 然而现实很残酷，莫得
void * ret = push_heap(needed);
if(ret == NULL) return NULL;
return serve(ret, _push_heap_alloc);
} else { // 拿到了!
unsigned tr_sz = TR_SZ(tr_node);
erase(tr_node);
void * suc = push_heap(needed-tr_sz);
if(suc == NULL) return NULL;
else return serve(tr_node, tr_sz+_push_heap_alloc);
}
}
checkheap(__LINE__);
}
/* 整理链表节点的内存，准备分配 */
inline void * list_serve (void * u, unsigned sz, void * head) {
*((unsigned*)(u+4)) = head-_mem_heap_lo();
return u+8;
}
/* 分块链表管理小段内存分配，加速运行 */
inline void * list_malloc (unsigned size) {
size = LSM_ALIGN(size); // 对齐到能够容纳size的最小的块大小
unsigned size_class = LSM_S2C(size);
if(MNULL == L_TABLE(size_class)) list_require(size); // 不够用了！
void * head = L_TABLE(size_class); // 取出链表块
void * ptr = LSH_HEAD(head); // 取出链表块的第一个节点
LSH_SETHEAD(head, LS_NXT(ptr));
if(LSH_HEAD(head) == MNULL) // 从链表块中删除
L_SETTABLE(size_class, LSH_NEXT(head)); // 链表块用光了，从链表块链表中删除
LSH_INCRCNT(head); // 块计数器增加
return list_serve(ptr, size, head); // 上菜啦！
}
int mc = 0;
inline void * malloc (size_t size) {
//mc ++;
//if(mc % 4096 == 0) printf("%d\n", mc);
dbg_printf("malloc:%lx", size);
void * ret;
if(size > LISTPROC) ret = treap_malloc(size);
else ret = list_malloc(size);
dbg_printf(", %p\n", ret);
checkheap(__LINE__);
return ret;
}
/*
* free
*/
void dumpseg(void * p, int interp);
void pallseg ();
inline void treap_free (void *ptr) {
ptr -= 8;
#ifdef DEBUG
//pallseg();
#endif
unsigned seg_size = *((unsigned*)ptr)-1; // 获取段大小
if(ptr > g_treap && !((*((char*)(ptr-1)))&1)) { // 康康左边有没有可以合并的空闲段
void * tr_nodel = ptr-B2S_S2B(*((unsigned*)(ptr-4))); // 找到你了！
seg_size += TR_SZ(tr_nodel);
erase(tr_nodel); // 自我销毁
ptr = tr_nodel;
}
if(ptr+seg_size < mem_heap_hi() && !((*((unsigned*)(ptr+seg_size)))&1)) { // 康康右边有没有可以合并的空闲段
void * tr_noder = ptr+seg_size; // 找到你了*2！
seg_size += TR_SZ(tr_noder);
erase(tr_noder); // 自我销毁
}
newnode(ptr, seg_size, MNULL); // 生成新的Treap节点
insert(ptr); // 插♂入
checkheap(__LINE__);
}
void list_free (void * ptr) {
ptr -= 8;
void * head = LS_HEAD(ptr);
unsigned size_class = LSM_S2C(LSH_ULEN(head));
if(!LSH_DECRCNT(head)) { // 整个块链表都被放飞了, 而且还有这种块的剩余（防止抖动）！
// 从链表块链表内删掉
if(L_TABLE(size_class) == head) L_SETTABLE(size_class, LSH_NEXT(head));
else LSH_SETNEXT(LSH_PREV(head), LSH_NEXT(head));
if(LSH_NEXT(head) != MNULL)
LSH_SETPREV(LSH_NEXT(head), LSH_PREV(head));
// 放飞自我！整块化作Treap中的空闲内存
dbg_printf("release:%p, sz:%u\n", head, SG_SZ(head));
treap_free(head+8);
} else {
//把自己加回链表块内
LS_SETNXT(ptr, LSH_HEAD(head));
LSH_SETHEAD(head, ptr);
}
}
void free (void * ptr) {
if(ptr == 0) return ;
//return treap_free(ptr);
dbg_printf("free:%p, ", ptr);
if(LSALLOCED(ptr-8)) {
dbg_printf("lis\n");
list_free(ptr);
}
else {
dbg_printf("trp\n");
treap_free(ptr);
}
checkheap(__LINE__);
}
/*
* realloc - you may never want to look at mm-naive.c
*/
void *treap_realloc(void *oldptr, unsigned size) {
oldptr -= 8;
unsigned seg_size = *((unsigned*)oldptr)-1;
unsigned tr_needed = TR_NEEDED(size);
if(tr_needed == seg_size) return oldptr+8; // 不用进行任何操作
if(tr_needed < seg_size) { // 我缩水了
if(seg_size-tr_needed < TR_MINSZ) return oldptr+8; // 收缩出来的空余空间太小，没卵用
void * ret = serve(oldptr, tr_needed);
free(serve(oldptr+tr_needed, seg_size-tr_needed)); // 有新的内存释放了
return ret;
} else { // 我膨胀了
void * nxt = oldptr+(*((unsigned*)oldptr))-1;
if(nxt <= mem_heap_hi() && !((*((unsigned*)nxt))&1)) { // 后面刚好是一段空闲内存
unsigned suc_sz = *((unsigned*)nxt);
if(suc_sz+seg_size >= tr_needed) { // 康康够不够用
erase(nxt);
if(suc_sz+seg_size >= tr_needed+TR_MINSZ) { // 可以裂开
//我裂开来
insert(newnode(oldptr+tr_needed, suc_sz+seg_size-tr_needed, MNULL));
return serve(oldptr, tr_needed); // 分配内存
} else
return serve(oldptr, suc_sz+seg_size); // 无法裂开，统统用光
} else { // 不够用了，搬家喽
void * dest = malloc(tr_needed);
if(dest == NULL) return NULL; // 直接炸裂
memcpy(dest, oldptr+8, seg_size-8); // 整段拷贝
insert(newnode(oldptr, seg_size, MNULL)); // 回收垃圾
return dest;
}
} else if(nxt > mem_heap_hi()) { // 刚好在堆的末尾
void * res = push_heap(tr_needed-seg_size);
if(res == NULL) return NULL;
return serve(oldptr, seg_size+_push_heap_alloc);
} else { // 什么特殊性质都没有，诉诸大力进行解决
void * dest = malloc(tr_needed);
if((long)dest < 0) return NULL; // 直接炸裂
memcpy(dest, oldptr+8, seg_size-8); // 搬家
insert(newnode(oldptr, seg_size, MNULL)); // 回收垃圾
return dest;
}
}
}
void * realloc (void *oldptr, size_t size) {
//return treap_realloc(oldptr, size);
if(size == 0) {
free(oldptr);
return NULL;
}
if(oldptr == NULL) return malloc(size);
dbg_printf("realloc:%p, %lx", oldptr, size);
// 判断它是链表节点分配的还是Treap直接分配的
if(!LSALLOCED(oldptr-8) && size > LISTPROC) return treap_realloc(oldptr, size);
else {
void * ret = malloc(size);
unsigned oldsz;
if(LSALLOCED(oldptr-8)) oldsz = LSH_ULEN(LS_HEAD(oldptr-8));
else oldsz = SG_SZ(oldptr-8);
memcpy(ret, oldptr, min(oldsz, size));
free(oldptr);
return ret;
}
checkheap(__LINE__);
}
/*
* calloc - you may want to look at mm-naive.c
* This function is not tested by mdriver, but it is
* needed to run the traces.
*/
void *calloc (size_t nmemb, size_t size) {
size_t bytes = nmemb * size;
void *newptr;
newptr = malloc(bytes);
memset(newptr, 0, bytes);
return newptr;
}
/*
* Return whether the pointer is in the heap.
* May be useful for debugging.
*/
static int in_heap(const void *p) {
return p <= mem_heap_hi() && p >= _mem_heap_lo();
}
/*
* Return whether the pointer is aligned.
* May be useful for debugging.
*/
static int aligned(const void *p) {
return (size_t)ALIGN(p) == (size_t)p;
}
//下面的函数都是用来调试的
void dumpmem (void * ptr, int size) {
for(int i = 0; i<(size+7)/8 && ptr+i*8 <= mem_heap_hi(); i++) {
dbg_printf(" %10p: ", ptr+i*8);
for(int j = 0; j<8 && ptr+i*8+j<=mem_heap_hi(); j++)
dbg_printf(" %02x", *((unsigned char*)(ptr+i*8+j)));
dbg_printf("\n");
}
}
void dumpseg (void * ptr, int interp) {
if(interp == -1) {
if((*((unsigned*)ptr))&1) {
dbg_printf("\e[41;37mallocated memory segment: %p\e[0m\n", ptr);
unsigned l = (*((unsigned*)ptr))-1;
dbg_printf("length(header): %x\n", l);
dbg_printf("typebyte(footer): %02x\n", B2S_S2B((*((unsigned*)(ptr+l-4))))&255);
} else {
dbg_printf("\e[46;30mTreap node: %p\e[0m\n", ptr);
dbg_printf("length(header): %x\n", (*((unsigned*)ptr)));
dbg_printf("fa(header): %p, raw:%x\n", TR_FAP(ptr), (*((unsigned*)ptr+4)));
dbg_printf("chl(header): %p, raw:%x\n", TR_LCP(ptr), (*((unsigned*)ptr+8)));
dbg_printf("chr(header): %p, raw:%x\n", TR_RCP(ptr), (*((unsigned*)ptr+12)));
dbg_printf("key(header): %x\n", TR_KEY(ptr));
dbg_printf("length(tail): %x\n", B2S_S2B(*((unsigned*)(ptr+(*((unsigned*)ptr))-4))));
}
} else {
if(interp == 0) {
if(!((*((unsigned*)ptr))&1)) dbg_printf("(header) misinterpretation\n");
dbg_printf("allocated memory segment: %p\n", ptr);
unsigned l = (*((unsigned*)ptr))-1;
dbg_printf("length(header): %x\n", l);
dbg_printf("typebyte(footer): %02x\n", B2S_S2B((*((unsigned*)(ptr+l-4))))&255);
} else {
if(((*((unsigned*)ptr))&1)) dbg_printf("(header) misinterpretation\n");
dbg_printf("Treap node: %p\n", ptr);
dbg_printf("length(header): %x\n", (*((unsigned*)ptr)));
dbg_printf("fa(header): %p, raw:%x\n", TR_FAP(ptr), (*((unsigned*)ptr+4)));
dbg_printf("chl(header): %p, raw:%x\n", TR_LCP(ptr), (*((unsigned*)ptr+8)));
dbg_printf("chr(header): %p, raw:%x\n", TR_RCP(ptr), (*((unsigned*)ptr+12)));
dbg_printf("key(header): %x\n", TR_KEY(ptr));
dbg_printf("length(tail): %x\n", B2S_S2B(*((unsigned*)(ptr+(*((unsigned*)ptr))-4))));
}
}
}
int check_node (void * u) {
if(TR_LCP(u) != MNULL && TR_FAP(TR_LCP(u)) != u) {
dbg_printf("node %p left child has wrong father pointer.\n", u);
return 0;
}
if(TR_RCP(u) != MNULL && TR_FAP(TR_RCP(u)) != u) {
dbg_printf("node %p right child has wrong father pointer.\n", u);
return 0;
}
if(TR_LCP(u) != MNULL && TR_SZ(TR_LCP(u)) > TR_SZ(u)) {
dbg_printf("left child(%u) is greater than u(%u).\n", TR_SZ(TR_LCP(u)), TR_SZ(u));
return 0;
}
if(TR_LCP(u) != MNULL && TR_SZ(TR_LCP(u)) > TR_SZ(u)) {
dbg_printf("right child(%u) is smaller than u(%u).\n", TR_SZ(TR_RCP(u)), TR_SZ(u));
return 0;
}
return 1;
}
void pallseg () {
void * curseg = g_treap;
while(curseg <= mem_heap_hi()) {
unsigned seg_size = (*((unsigned*)curseg))&(~7);
dumpseg(curseg, -1);
curseg += seg_size;
}
}
void dbg_cycle () {
while(1) {
char buf[256];
scanf("%s", buf);
if(strcmp(buf, "d") == 0) {
long ptr, len;
scanf("%lx%lx", &ptr, &len);
dumpmem((void*)ptr, len);
} else if(strcmp(buf, "p") == 0) {
long ptr;
scanf("%lx%s", &ptr, buf);
if(strcmp(buf, "n") == 0) dumpseg((void*)ptr, 1);
else if(strcmp(buf, "u") == 0) dumpseg((void*)ptr, 0);
else dumpseg((void*)ptr, -1);
} else if(strcmp(buf, "g") == 0) {
dbg_printf("lo:%p, hi:%p\n", _mem_heap_lo(), mem_heap_hi());
dbg_printf("ro:%p, mn:%p\n", g_rootptr, MNULL);
for(int i = 0; i<LISTCLASSES; i++)
dbg_printf("list class [%u]: %p\n", LSM_C2S(i), L_TABLE(i));
} else if(strcmp(buf, "pa") == 0) {
pallseg();
} else if(strcmp(buf, "lh") == 0) {
long x;
scanf("%lx", &x);
void * ptr = (void*)x;
printf("list header %p:\n", ptr);
printf("cnt:%x, ulen:%x\n", LSH_CNT(ptr), LSH_ULEN(ptr));
printf("prev:%p, next:%p\n", LSH_PREV(ptr), LSH_NEXT(ptr));
printf("head:%p, size:%x\n", LSH_HEAD(ptr), SG_SZ(ptr));
}else if(strcmp(buf, "q") == 0) {
exit(0);
}
}
}
/*
* mm_checkheap
*/
void mm_checkheap(int lineno) {
void * curseg = g_treap, * ljmp = (void*)-1;
while(curseg <= mem_heap_hi()) {
ljmp = curseg;
unsigned seg_size = (*((unsigned*)curseg))&(~7);
curseg += seg_size;
}
if(curseg != mem_heap_hi()+1) {
dbg_printf("mm_checkheap called at [%d] line failed, heap overun.\n", lineno);
dbg_printf("last jump: %p\n", ljmp);
dbg_cycle();
return ;
}
curseg = g_treap;
while(curseg <= mem_heap_hi()) {
unsigned seg_size = (*((unsigned*)curseg))&(~7);
if(((*((unsigned*)curseg))&1) != (B2S_S2B(*((unsigned*)(curseg+seg_size-4)))&1)) {
dbg_printf("broken segment tag at %p of length %u\n", curseg, seg_size);
dbg_cycle();
return ;
}
curseg += seg_size;
}
curseg = g_treap;
while(curseg <= mem_heap_hi()) {
unsigned seg_size = (*((unsigned*)curseg))&(~7);
if(((*((unsigned*)curseg))&7) != (B2S_S2B(*((unsigned*)(curseg+seg_size-4)))&7)) {
dbg_printf("broken segment tag at %p of length %u\n", curseg, seg_size);
dbg_cycle();
return ;
}
curseg += seg_size;
}
curseg = g_treap;
while(curseg <= mem_heap_hi()) {
unsigned seg_size = (*((unsigned*)curseg))&(~7);
if(!((*((unsigned*)curseg))&7) && !check_node(curseg)) {
dbg_printf("exceptional Treap node at %p of length %u\n", curseg, seg_size);
dbg_cycle();
return ;
}
curseg += seg_size;
}
}