济南网站建设飞鸟,wordpress十佳主题,石油 技术支持 东莞网站建设,网站建设项目的实训报告malloc原理
malloc它有一个将可用的内存块连接为一个长长的列表的所谓空闲链表。调用malloc函数时#xff0c;它沿连接表寻找一个大到足以满足 用户请求所需要的内存块。然后#xff0c;将该内存块一分为二#xff08;一块的大小与用户请求的大小相等#xff0c;另一块的大…malloc原理
malloc它有一个将可用的内存块连接为一个长长的列表的所谓空闲链表。调用malloc函数时它沿连接表寻找一个大到足以满足 用户请求所需要的内存块。然后将该内存块一分为二一块的大小与用户请求的大小相等另一块的大小就是剩下的字节。接下来将分配给用户的那块内存传 给用户并将剩下的那块如果有的话返回到连接表上。调用free函数时它将用户释放的内存块连接到空闲链上。到最后空闲链会被切成很多的小内存片 段如果这时用户申请一个大的内存片段那么空闲链上可能没有可以满足用户要求的片段了。于是malloc函数请求延时并开始在空闲链上翻箱倒柜地检 查各内存片段对它们进行整理将相邻的小空闲块合并成较大的内存块。 查询链表的方法
break指针
Linux维护一个break指针这个指针指向堆空间的某个地址。从堆起始地址到break之间的地址空间为映射好的可以供进程访问而从break往上是未映射的地址空间如果访问这段空间则程序会报错。我们用malloc进行内存分配就是从break往上进行的。
First fit从头开始使用第一个数据区大小大于要求size的块所谓此次分配的块。首次适配有更好的运行效率。 Best fit从头开始遍历所有块使用数据区大小大于size且差值最小的块作为此次分配的块。最佳适配具有较高的内存使用率。
int brk(void *addr);
void *sbrk(intptr_t increment);brk将break指针直接设置为某个地址 而sbrk将break从当前位置移动increment所指定的增量如果将increment设置为0则可以获得当前break的地址。
malloc实现 void* malloc(unsigned size); 在堆内存中分配一块长度为size字节的连续区域参数size为需要内存空间的长度。 #include sys/types.h
#include unistd.htypedef struct s_block *t_block;struct s_block {size_t size; // 数据区大小 t_block next; // 指向下个块的指针 int free; // 是否是空闲块 int padding; // 填充4字节保证meta块长度为8的倍数 char data[1] // 这是一个虚拟字段表示数据块的第一个字节长度不应计入meta
};//首次适配
t_block find_block(t_block *last, size_t size) {t_block b first_block;while(b !(b-free b-size size)) {*last b;b b-next;}return b;
}//如果现有block都不能满足size的要求
//则需要在链表最后开辟一个新的block。
//这里关键是如何只使用sbrk创建一个struct#define BLOCK_SIZE 24 //由于存在虚拟的data字段sizeof不能正确计算meta长度这里手工设置 t_block extend_heap(t_block last, size_t s) {t_block b;b sbrk(0);if(sbrk(BLOCK_SIZE s) (void *)-1)return NULL;b-size s;b-next NULL;if(last)last-next b;b-free 0;return b;
}//First fit有一个比较致命的缺点
//就是可能会让很小的size占据很大的一块block
//此时为了提高payload应该在剩余数据区足够大的情况下将其分裂为一个新的blockvoid split_block(t_block b, size_t s) {t_block newb;newb b-data s;newb-size b-size - s - BLOCK_SIZE ;newb-next b-next;newb-free 1;b-size s;b-next newb;
}//由于我们希望malloc分配的数据区是按8字节对齐
//所以在size不为8的倍数时我们需要将size调整为大于size的最小的8的倍数
size_t align8(size_t s) {if(s 0x7 0)return s;return ((s 3) 1) 3;
}void *first_blockNULL;void *malloc(size_t size) {t_block b, last;size_t s;/* 对齐地址 */s align8(size);if(first_block) {/* 查找合适的block */last first_block;b find_block(last, s);if(b) {pre namecode classcpp /* 如果可以则分裂 */if ((b-size - s) ( BLOCK_SIZE 8))split_block(b, s);b-free 0;} else {/* 没有合适的block开辟一个新的 */b extend_heap(last, s);if(!b)return NULL;}} else {b extend_heap(NULL, s);if(!b)return NULL;first_block b;}return b-data;
}calloc实现 void* calloc(size_t numElements, size_t sizeOfElement); 与malloc相似参数sizeOfElement为单位元素长度例如sizeof(int)numElements为元素个数即在内存中申请numElements * sizeOfElement字节大小的连续内存空间。并且会把内存初始化为0。 calloc(num, size) 基本上等于 void *p malloc(num * size); memset(p, 0, num * size); 但理论上 calloc 的实现可避免 num * size 溢出当溢出时返回 NULL 代表失败而 malloc(num * size) 可能会分配了一个尺寸溢出后的内存。 由于我们的数据区是按8字节对齐的所以为了提高效率我们可以每8字节一组置0而不是一个一个字节设置。我们可以通过新建一个size_t指针将内存区域强制看做size_t类型来实现。
void *calloc(size_t number, size_t size) {size_t *news;size_t s8, i;news malloc(number * size);if(news) {s8 align8(number * size) 3;for(i 0; i s8; i)news[i] 0;}return news;
}realloc实现
void* realloc(void* ptr, unsigned newsize);使用realloc函数为ptr重新分配大小为size的一块内存空间。下面是这个函数的工作流程
对ptr进行判断如果ptr为NULL则函数相当于malloc(new_size)试着分配一块大小为new_size的内存如果成功将地址返回否则返回NULL。如果ptr不为NULL则进入2。查看ptr是不是在堆中如果不是的话会抛出realloc invalid pointer异常。如果ptr在堆中则查看new_size大小如果new_size大小为0则相当于free(ptr)将ptr指向的内存空间释放掉返回NULL。如果new_size小于原大小则ptr中的数据可能会丢失只有new_size大小的数据会保存如果size等于原大小等于什么都没有做如果size大于原大小则查看ptr指向的位置还有没有足够的连续内存空间如果有的话分配更多的空间返回的地址和ptr相同如果没有的话在更大的空间内查找如果找到size大小的空间将旧的内容拷贝到新的内存中把旧的内存释放掉则返回新地址否则返回NULL。
//为了实现realloc我们首先要实现一个内存复制方法。
//如同calloc一样为了效率我们以8字节为单位进行复制
void copy_block(t_block src, t_block dst) {size_t *sdata, *ddata;size_t i;sdata src-ptr;ddata dst-ptr;for(i 0; (i * 8) src-size (i * 8) dst-size; i)ddata[i] sdata[i];
}void *realloc(void *p, size_t size)
{size_t s;t_block b, newb;void *newp;if (!p)/* 根据标准库文档当p传入NULL时相当于调用malloc */return malloc(size);if(valid_addr(p)){s align8(size);b get_block(p);if(b-size s){if(b-size - s (BLOCK_SIZE 8))split_block(b,s);} else{/* 看是否可进行合并 */if(b-next b-next-free (b-size BLOCK_SIZE b-next-size) s){fusion(b);if(b-size - s (BLOCK_SIZE 8))split_block(b, s);}else {/* 新malloc */newp malloc (s);if (!newp)return NULL;newb get_block(newp);copy_block(b, new);free(p);return(newp);}}return (p);}return NULL;
}free实现
如何验证所传入的地址是有效地址即确实是通过malloc方式分配的数据区首地址 地址应该在之前malloc所分配的区域内即在first_block和当前break指针范围内 这个地址确实是之前通过我们自己的malloc分配的。如何解决碎片问题
//首先我们在结构体中增加magic pointer同时要修改BLOCK_SIZE
typedef struct s_block *t_block;struct s_block {size_t size; // 数据区大小 t_block next; // 指向下个块的指针 int free; // 是否是空闲块 int padding; // 填充4字节保证meta块长度为8的倍数 char data[1] // 这是一个虚拟字段表示数据块的第一个字节长度不应计入metavoid *ptr; // Magic pointer指向data
};
#define BLOCK_SIZE 24 //我们定义检查地址合法性的函数
t_block get_block(void *p)
{char *tmp;tmp p;return (p tmp - BLOCK_SIZE);
}int valid_addr(void *p)
{if(first_block) {if(p first_block p sbrk(0)) {return p (get_block(p))-ptr;}}return 0;
}将block和相邻block合并。为了满足这个实现需要将s_block改为双向链表。修改后的block结构如下 typedef struct s_block *t_block;
struct s_block {size_t size; /* 数据区大小 */t_block prev; /* 指向上个块的指针 */t_block next; /* 指向下个块的指针 */int free; /* 是否是空闲块 */int padding; /* 填充4字节保证meta块长度为8的倍数 */void *ptr; /* Magic pointer指向data */char data[1] /* 这是一个虚拟字段表示数据块的第一个字节长度不应计入meta */
};
#define BLOCK_SIZE 28合并方法如下
t_block fusion(t_block b) {if (b-next b-next-free) {b-size BLOCK_SIZE b-next-size;b-next b-next-next;if(b-next)b-next-prev b;}return b;
}void free(void *p)
{t_block b;if(valid_addr(p)) {b get_block(p);b-free 1;if(b-prev b-prev-free)b fusion(b-prev);if(b-next)fusion(b);else {if(b-prev)b-prev-prev NULL;elsefirst_block NULL;brk(b);}}
}
