【彻底搞懂C指针】Malloc 和 Free 的具体实现

• https://danluu.com/malloc-tutorial/

• 进程间的通信 : ①共享内存 ② 消息传递 （内核实现）

分配策略 (实现方面)

by DUCK

sbrk()

malocal实现的主要函数
man sbrk 查看

数据结构

一个参考代码

• https://github.com/danluu/malloc-tutorial/tree/master

#include <assert.h>
#include <string.h>
#include <sys/types.h>
#include <unistd.h>
// Don't include stdlb since the names will conflict?// TODO: align// sbrk some extra space every time we need it.
// This does no bookkeeping and therefore has no ability to free, realloc, etc.
void *nofree_malloc(size_t size) {void *p = sbrk(0);void *request = sbrk(size);if (request == (void*) -1) { return NULL; // sbrk failed} else {assert(p == request); // Not thread safe.return p;}
}// 单链表
struct block_meta {size_t size;struct block_meta *next;int free;int magic;    // For debugging only. TODO: remove this in non-debug mode.
};#define META_SIZE sizeof(struct block_meta)void *global_base = NULL;// Iterate through blocks until we find one that's large enough.
// TODO: split block up if it's larger than necessary
struct block_meta *find_free_block(struct block_meta **last, size_t size) {struct block_meta *current = global_base;while (current && !(current->free && current->size >= size)) {*last = current;current = current->next;}return current;
}struct block_meta *request_space(struct block_meta* last, size_t size) {struct block_meta *block;block = sbrk(0);void *request = sbrk(size + META_SIZE);assert((void*)block == request); // Not thread safe.if (request == (void*) -1) {return NULL; // sbrk failed.}if (last) { // NULL on first request.last->next = block;}block->size = size;block->next = NULL;block->free = 0;block->magic = 0x12345678;return block;
}// If it's the first ever call, i.e., global_base == NULL, request_space and set global_base.
// Otherwise, if we can find a free block, use it.
// If not, request_space.
void *malloc(size_t size) { // 定义一个名为malloc的函数，它接受一个size_t类型的参数size，并返回一个void指针。struct block_meta *block; // 定义一个指向block_meta结构的指针block。// TODO: align size? // 这是一个待办事项，提示开发者可能需要对size进行对齐。if (size <= 0) { // 如果请求的内存大小小于或等于0，return NULL; // 则返回NULL。}if (!global_base) { // 如果全局变量global_base为空（即这是第一次调用malloc），block = request_space(NULL, size); // 则请求分配size大小的内存空间，并将返回的内存块的地址赋值给block。if (!block) { // 如果内存分配失败（即request_space返回NULL），return NULL; // 则返回NULL。}global_base = block; // 将global_base设置为新分配的内存块的地址。} else { // 如果global_base不为空（即已经有内存块被分配过），struct block_meta *last = global_base; // 定义一个新的指针last，并将其初始化为global_base。block = find_free_block(&last, size); // 在已分配的内存块中查找一个足够大的空闲块。if (!block) { // 如果没有找到足够大的空闲块，block = request_space(last, size); // 则请求分配新的内存空间。if (!block) { // 如果内存分配失败，return NULL; // 则返回NULL。}} else {      // 如果找到了一个足够大的空闲块，// TODO: consider splitting block here. // 这是一个待办事项，提示开发者可能需要在这里将找到的空闲块进行分割。block->free = 0; // 将空闲块的状态设置为已使用。block->magic = 0x77777777; // 设置一个魔数，用于后续的错误检查或调试。}}return(block+1); // 返回分配的内存块的地址。注意这里返回的是block+1，这是因为block实际上指向的是内存块的元数据，而我们需要返回的是可用内存的地址。
}void *calloc(size_t nelem, size_t elsize) { // 定义一个名为calloc的函数，它接受两个size_t类型的参数nelem和elsize，并返回一个void指针。size_t size = nelem * elsize; // 计算需要分配的总内存大小。void *ptr = malloc(size); // 调用malloc函数分配内存。memset(ptr, 0, size); // 使用memset函数将新分配的内存初始化为0。return ptr; // 返回分配的内存的地址。
}struct block_meta *get_block_ptr(void *ptr) { // 定义一个名为get_block_ptr的函数，它接受一个void指针ptr，并返回一个指向block_meta结构的指针。return (struct block_meta*)ptr - 1; // 返回ptr指针前一个位置的地址，这个地址就是内存块的元数据的地址。
}void free(void *ptr) { // 定义一个名为free的函数，它接受一个void指针ptr。if (!ptr) { // 如果ptr为空，return; // 则直接返回。}struct block_meta* block_ptr = get_block_ptr(ptr); // 获取ptr对应的内存块的元数据的地址。assert(block_ptr->free == 0); // 断言这个内存块当前是被使用的。assert(block_ptr->magic == 0x77777777 || block_ptr->magic == 0x12345678); // 断言这个内存块的魔数是正确的。block_ptr->free = 1; // 将这个内存块的状态设置为未使用。block_ptr->magic = 0x55555555; // 更新这个内存块的魔数。
}void *realloc(void *ptr, size_t size) { // 定义一个名为realloc的函数，它接受一个void指针ptr和一个size_t类型的参数size，并返回一个void指针。if (!ptr) { return malloc(size); // 如果ptr为空，则realloc函数应该表现得像malloc函数一样。}struct block_meta* block_ptr = get_block_ptr(ptr); // 获取ptr对应的内存块的元数据的地址。if (block_ptr->size >= size) {return ptr; // 如果当前内存块的大小已经足够大，那么直接返回ptr。}void *new_ptr;new_ptr = malloc(size); // 分配新的内存空间。if (!new_ptr) {return NULL; // 如果内存分配失败，返回NULL。}memcpy(new_ptr, ptr, block_ptr->size); // 将旧内存块中的数据复制到新内存块中。free(ptr); // 释放旧内存块。 return new_ptr; // 返回新内存块的地址。
}

郭郭大佬的补充代码

考虑free空间的分配
可以加到 free 空间
如果可以合并就合并 否则会增加 heap 的高度 影响效率

分隔操作

线程安全改进

malloc的可重入性和线程安全分析

malloc函数是一个我们经常使用的函数，如果不对会造成一些潜在的问题。下面就malloc函数的线程安全性和可重入性做一些分析。
我们知道一个函数要做到线程安全，需要解决多个线程调用函数时访问共享资源的冲突。而一个函数要做到可重入，需要不在函数内部使用静态或全局数据，不返回静态或全局数据，也不调用不可重入函数。
malloc函数线程安全但是不可重入的，因为malloc函数在用户空间要自己管理各进程共享的内存链表，由于有共享资源访问，本身会造成线程不安全。为了做到线程安全，需要加锁进行保护。同时这个锁必须是递归锁，因为如果当程序调用malloc函数时收到信号，在信号处理函数里再调用malloc函数，如果使用一般的锁就会造成死锁（信号处理函数中断了原程序的执行），所以要使用递归锁。
虽然使用递归锁能够保证malloc函数的线程安全性，但是不能保证它的可重入性。按上面的场景，程序调用malloc函数时收到信号，在信号处理函数里再调用malloc函数就可能破坏共享的内存链表等资源，因而是不可重入的。
至于malloc函数访问内核的共享数据结构可以正常的加锁保护，因为一个进程程调用malloc函数进入内核时，必须等到返回用户空间前夕才能执行信号处理函数，这时内核数据结构已经访问完成，内核锁已释放，所以不会有问题。

• 参考 : 【彻底搞懂C指针】Malloc 和 Free 的具体实现_哔哩哔哩_bilibili