{
"title": "用c手写一个Memory Allocator",
"tags": [
"post",
"c"
],
"summary": "学过c语言的同学一定用过malloc, calloc, realloc, free . 学会自己管理内存可以使程序性能更高. 然而在不了解其内部原理的情况下使用它们, 容易造成内存溢出, 野指针等问题. 通过这篇文章, 你将了解到内存, 虚拟内存等概念…",
"sources": [
"xlog"
],
"external_urls": [
"https://ming5ming.xlog.app/c-Memory-Allocator"
],
"date_published": "2023-01-20T02:39:46.060Z",
"content": "学过c语言的同学一定用过`malloc`, `calloc`, `realloc`, `free` . 学会自己管理内存可以使程序性能更高. 然而在不了解其内部原理的情况下使用它们, 容易造成**内存溢出**, **野指针**等问题.\n\n通过这篇文章, 你将了解到内存, 虚拟内存等概念, 并且自己手写一个内存管理器(Memory Allocator)\n\n---\n### 内存(RAM) 与 硬盘(DRIVER)\n\n有些人会把内存和硬盘的概念混淆. 通常,内存是用来储存程序的二进制指令及相关变量的硬件, 而硬盘则是用来储存大量数据的硬件.\n\n实际上, [内存](https://zh.wikipedia.org/wiki/%E9%9A%8F%E6%9C%BA%E5%AD%98%E5%8F%96%E5%AD%98%E5%82%A8%E5%99%A8)和[硬盘](https://zh.wikipedia.org/wiki/%E7%A1%AC%E7%9B%98)没有本质的区别, 它们都是[计算机储存器](https://zh.m.wikipedia.org/zh-hans/%E9%9B%BB%E8%85%A6%E8%A8%98%E6%86%B6%E9%AB%94)(memory), 用来储存一定的数据. 内存的访问速度快, 但是单位造价高, 所以用作需要频繁读写的地方, 例如储存程序上下文. 硬盘, 读写速度相较于内存较慢, 但是容量大, 适合用作长期储存不需要频繁读写的文件.\n\n内存可以看作是硬盘的缓存, 当需要获取一段数据时, 可以将硬盘的数据临时拷贝到内存. 等到计算机需要这些数据时, 可以直接从读写速度很快的内存中拿到它们. \n\n\n\n\n\n这样的缓存机制在计算机里随处可见, cpu中除了ALU(计算单元外), 还有一个重要的部分叫做register(寄存器), 寄存器也是一种计算机储存器, 它可以看作是内存的缓存. 这样的说法实际上有些片面, cpu还有一种叫做三级缓存的机制, 此处不再赘述, 有兴趣的读者可以自行查阅.\n\n### 虚拟内存\n\n[虚拟内存](https://zh.m.wikipedia.org/zh-hans/%E8%99%9A%E6%8B%9F%E5%86%85%E5%AD%98), 是计算机系统(OS)对一块内存的抽象. 在应用程序的视角中, 自己占据计算机的全部内存(一块连续可用的地址空间). 然而实际上, 这块内存是由计算机系统暴露给应用程序的内存碎片. 它可能不仅仅包含一部分物理内存, 还会包含硬盘空间.\n\n\n\n\n\n\n如果没有虚拟内存, 进程(process)间会对内存资源进行争夺, 甚至越界访问, 极易造成内存泄漏. 并且由于进程的内存是以块的形式储存, 小部分未分配的内存无法被更大的进程申请, 造成了一定的资源浪费.\n\n使用虚拟内存管理物理内存, 我们可以将物理内存人为的划分成一个个块(chunk), 多个块组成**页(page)**, 然后将页与其占有情况写入页表. 这样就可以将进程所需的内存拆分成块的形式储存, 我们不必使这些内存集中存放, 相反可以将它们放入任意位置. **只需要记录虚拟内存与物理内存之间的映射关系(index), 将映射关系存放在页表中, 我们就可以根据这些信息找到物理内存地址.** 并且这些操作都是由硬件完成, 速度极快, 大大增加了内存的可用性和效率.\n\ncpu首先接受到操作指令, 并且将虚拟地址发送到MMU(内存管理单元), MMU将访问物理内存(实际上访问了物理内存的缓存,TLB)获取页表, 然后找到其映射关系并计算出物理地址, 之后交给cpu, cpu访问物理内存取得数据.\n\n### 内存的结构\n\n在开始操作内存前, 我们先了解一下内存的结构都有哪些.\n- Text section\n- Data section\n- BSS\n- Heap\n- Stack\n\n\n\n我们在使用`malloc`时操作的内存结构是Heap(堆). 它的末尾有一个名为*brk*的指针, 它指向堆顶.\n\n这是一种可以动态分配的内存结构, 可以根据需求动态的申请一定量的内存, 同时支持删除操作, 我们一般通过指针对申请的地址进行数据操作.\n\n操作内存并不需要我们直接对硬件进行操作, 可以直接使用系统封装好的API`sbrk()`\n`sbrk(0)`返回当前程序执行的位置的内存地址.\n`sbrk(x)`使得*brk*向正方向增长x字节(bytes).\n`sbrk(-x)`使得*brk*向负方向增长x字节(bytes).\n如果sbrk()出于某些原因未能完成操作, 将返回`(void*) -1`\n\n### malloc()\n好了, 目前为止我们终于可以写出一个简易的`malloc()`了:\n\n```c\nvoid* malloc( size_t size )\n{\n\tvoid* block;\n\tblock = sbrk(size);\n\tif ( block == (void*) -1 )\n\t\treturn NULL;\n\treturn block;\n}\n```\n\n看起来很不错, 但是不够完美.\n在写`free()`函数时我们接受一个指针, 以便释放与它相关的内存, 然而我们如何得知释放内存的大小呢?\n\n我们可以在每段地址的初段定义一个`Header`:\n```c\nstruct header_t {\n\tsize_t size;\n\tunsigned is_free;\n};\n```\n`size`用来储存`Header`指向的内存的大小.\n`is_free`用来标记这块内存是否被占用.\n现在我们的一块内存看起来是这样的:\n\n\n\n\n我们还需要一个方法可以遍历这个内存, 因为我们需要遍历以找到一块未被占用的内存. 链表是一个不错的方案:\n```c\nstruct header_t {\n\tsize_t size;\n\tunsigned is_free;\n\tstruct header_t* next;\n};\n```\n\n现在它长这样:\n\n\n\n\n\n\n\n\n由于我们以块的形式管理内存, 所以需要对齐操作:\n```c\ntypedef char ALIGN[16];\n\nunion header {\n\tstruct {\n\t\tsize_t size;\n\t\tunsigned is_free;\n\t\tunion header *next;\n\t} s;\n\tALIGN stub;\n};\ntypedef union header header_t;\n```\n\n我们还需要定义首尾节点:\n```c\nheader_t *head, *tail;\n```\n\n为了避免多线程同时调用内存, 要定义我们加入全局锁, 在申请完地址后再释放:\n```c\npthread_mutex_t global_malloc_lock;\n```\n\n现在我们的版本是这样的:\n```c\nvoid* malloc(size_t size) {\n size_t total_size;\n header_t* header;\n void* block;\n\n if ( size <= 0 ) {\n return NULL;\n };\n\n pthread_mutex_lock(&global_malloc_lock);\n header = get_header_t(size);\n\n if (header)\n {\n header->s.isFree = 0;\n pthread_mutex_unlock(&global_malloc_lock);\n return (void*)(header + 1);\n }\n\n total_size = size + sizeof(header_t);\n block = sbrk(total_size);\n\n if (block == (void*) - 1) {\n pthread_mutex_unlock(&global_malloc_lock);\n return NULL;\n } else {\n header = block;\n };\n \n header->s.isFree = 0;\n header->s.size = size;\n header->s.next = NULL;\n\n if (head == NULL)\n head = header;\n if (tail) \n tail->s.next = header;\n\n tail = header;\n pthread_mutex_unlock(&global_malloc_lock);\n return (void*)(header + 1);\n};\n\nheader_t* get_header_t( size_t size ) {\n header_t* curr = head;\n while (curr)\n {\n if ( curr->s.isFree && curr->s.size >= size) {\n pthread_mutex_unlock(&global_malloc_lock);\n return (void*)(head);\n };\n curr = curr->s.next;\n }\n return NULL;\n}\n```\n\n首先我们判断申请的内存是否合法, 之后寻找最低地址的节点指针(`get_header_t()`).\n找到了就标记为`isFree`, 然后解锁返回虚拟地址的首端的指针.\n如果没有找到, 就调用`sbrk`申请内存, 并初始化`header`将其设为`tail`节点, 之后解锁返回地址.\n\n其中`total_size`包含头部与实际所需内存大小两部分.\n\n### free()\n在设计`free()`函数时, 有一个需要注意的细节: 先判断需要释放的地址是否位于堆的尾部\n如果位于尾部, 则直接交给操作系统释放, 否则将其标记为`isFree`, 我们将在以后重用它们.\n```c\nvoid free(void* block) {\n if (!block)\n {\n return NULL;\n }\n \n header_t* header = (header_t*)block - 1;\n void* programbreak = sbrk(0);\n pthread_mutex_lock(&global_malloc_lock);\n \n if ((char*)block + header->s.size == programbreak)\n {\n size_t total_size = header->s.size + sizeof(header_t);\n //release\n if (head == tail)\n {\n head = tail = NULL;\n } else {\n header_t* curr = head;\n //change tail\n while (curr->s.next == tail)\n {\n curr->s.next = NULL;\n tail = curr;\n }\n }\n \n sbrk(-total_size);\n pthread_mutex_unlock(&global_malloc_lock);\n \n return;\n };\n \n header->s.isFree = 1;\n pthread_mutex_unlock(&global_malloc_lock);\n}\n```\n\n首先找到`brk`的位置并将其赋给`programbreak`, 之后判断释放的对象是否位于堆顶. \n`char*`与`size_t`, `void*`具有相同的字节数:\n```c\n//test.c\n#include <stddef.h>\n\nint main(int argc, char const *argv[])\n\n{\n printf(\"char* is:%d, char is:%d, void* is:%d, size_t is:%d\", sizeof(char*), sizeof(char), sizeof(void*), sizeof(size_t));\n return 0;\n}\n\n//char* is:8, char is:1, void* is:8, size_t is:8\n```\n\n如果在堆顶, 则`(char*)block + header->s.size == programbreak`\n之后遍历找到最后一块内存并释放, 把倒数第二块内存设为`tail`.\n如果不在堆顶, 则暂时标记为`isFree`, 等待之后复用.\n\n### calloc()\n```c\nvoid* calloc( size_t nsize, size_t num)\n{\n size_t size;\n void* block;\n\n if (!num || !nsize)\n return NULL;\n \n size = nsize * num;\n //overflow check\n if (size != nsize * num)\n return NULL;\n\n block = malloc(size);\n if (!block)\n return NULL;\n \n memset(block, 0, size);\n return block;\n}\n```\n\ncalloc()要求返回的地址所指向的内存块都为`Null`, 我们可以通过`memset`将其设为0.\n\n### realloc()\n```c\nvoid* realloc(void* block, size_t size)\n{\n header_t* header;\n void* ret;\n \n if (!block || !size)\n return NULL;\n \n header = (header_t*)block - 1;\n \n if (header->s.size >= size)\n return block;\n \n ret = malloc(size);\n if (ret)\n {\n memcpy(ret, block, header->s.size);\n free(block);\n }\n return ret;\n}\n```\n\n`realloc()`比较特殊, 使用时应该注意返回的指针所指向的地址**不一定**会是原来的地址.\n因为`realloc()`时, 会出现两种情况:\n- 堆内存向高位增长, 上方空闲的内存大小可以容纳增长大小. 则返回原来的地址, 并修改`header`的`size`.\n- 堆内存上方空闲内存不足, 调用`malloc`重新申请一块地址, 并把原地址内容复制给新申请的地址. \n\n### Compile\n```bash\n$ gcc -o memalloc.so -fPIC -shared memalloc.c\n$ export LD_PRELOAD=$PWD/memalloc.so\n\n$ ls\nmemalloc.c\t\tmemalloc.so\n```\n\n### 拓展\n\nc/c++一直以其性能优越著名, 然而这也是一直让人诟病的地方. 如果使用它的人缺少对计算机系统的深入了解, 很容易造成误操作.\n而其他高级语言将内存管理自动化, 并将其机制命名为*垃圾回收*(OC), 其原理大致可概况为: 如果某对象**不可达**则会被垃圾回收器回收.\n\n\n\n\n\n### References\n[Memory Allocators 101](https://arjunsreedharan.org/post/148675821737/memory-allocators-101-write-a-simple-memory)\n\n\n推荐阅读:\n\n[《C专家编程》7. 对内存的思考(存储器的层次结构)](https://www.bilibili.com/video/BV1Ed4y1Y7HN)\n\n[What is exactly the base pointer and stack pointer?](https://stackoverflow.com/questions/1395591/what-is-exactly-the-base-pointer-and-stack-pointer-to-what-do-they-point)",
"attributes": [
{
"value": "c-Memory-Allocator",
"trait_type": "xlog_slug"
}
]
}
