自定义malloc()实现头设计

Question

我正在尝试用 C 语言编写一个用于调试目的的自定义分配器（作为练习），其中我将使用单个链接列表来使用“首次拟合算法”将可用内存列表组合在一起。我在下面显示了我想在“空内存节点”中创建的结构。

如何在我获得的内存的前几个字节处写入标头块（具体来说是一个联合）（我使用 malloc() 来最初获取一块内存），以便剩余的字节是空闲的？

这是我正在使用的联合：

/*Define Header Structure for proper alignment*/
union header {
struct{
    union header* next;
    unsigned size ; /*Make it size_t*/
}s; 
double dummy_align_var;
};

-------------------------------------------------------------------------------
|Next        |Size of  |16Byte| User is concerned only about |16Byte|         |
|Free Memory |Allocated|Header| this portion  of memory      |Footer|Checksum |
|Address     |Block    |Picket| and has no knowledge of rest |Picket|         |
-------------------------------------------------------------------------------
|-------Header---------|      ^Address Returned to user
                              ^------User Requested Size-----^
^-------------Memory Obtained From The Operating System-----------------------^
*/

[编辑] 根据提供的建议更改了块结构。

Answer 1

对于调试 malloc，请考虑在控制结构和用户数据的开头之间以及用户数据的结尾和校验和之间放置填充空间。填充的一个字节应该是零字节 0x00 - 因此字符串操作停止；考虑将另一个设置为 0xFF。如果你有一个固定的模式并发现它已经改变，你就知道有些东西超出了界限——但是你的敏感控制数据更有可能没有被践踏。如果您在分配给用户的空间的任一侧使用 16 个字节的填充，您可能会放置适当对齐的 4 个字节的零（因此是一个零 4 字节整数），并且可能将 0xFFFFFFFF 表示为 -1。此外，由于您可能会将请求的大小四舍五入为基本块大小的倍数，因此将不供用户使用的字节设置为已知值 - 并验证它们是否保持不变。这将检测“超出分配长度的一个”的修改，或者仅超出分配长度的几个字节的修改，否则可能无法检测到。

填充中零字节的唯一缺点是，在查找空字节时，您将无法轻松检测到未在分配的内存末尾停止的读取操作。您可以通过使用不带零字节的填充的替代选项来深入了解这些内容。

另一个需要考虑的选择是尝试将控制数据与返回给用户的内存完全分离。当然，完全分离是不可能的，但至少要与分配的块分开维护一个分配列表（具有大小和指针）。同样，这可以让您宝贵的控制数据远离不受控制的内存践踏操作，从而为您提供保护。您并没有完全免受错误指针的影响，但您受到了更好的保护。 （您仍然可以在分配的空间周围提供缓冲区以检测失控的写入。）但是，这种设计与问题明显不同。

---

假设您从“malloc()”获取内存块，那么您会这样做 - 粗略地说：

void *my_malloc(size_t nbytes)
{
    size_t reqblocks = (nbytes + sizeof(header) - 1) / sizeof(header);
    size_t reqspace  = (reqblocks + 2) * sizeof(header) + 2 * sizeof(padding);
    void *space = malloc(reqspace);
    if (space == 0)
        return space;
    void *retval = (char *)space + sizeof(header) + sizeof(padding);
    header *head = space;
    head->next = ...next...;
    head->size = nbytes;
    ...set head padding to chosen value...
    ...set tail padding to chosen value...
    ...set gap between nbytes and block boundary to chosen value...
    return retval;
}

还有一些解释要做......

Answer 2

我会做类似的事情

#define MEM_ALIGN 4 // 8 on 64b eventually

struct header {
    union aligned_header {
        struct _s {
            union aligned_header* next;
            size_t size;
        } data;
        char dummy_align_var[sizeof(struct _s) + sizeof(struct _s)%MEM_ALIGN];
    } header_data;
    char user_address;
};

并返回&user_address。

Answer 3

你为什么使用工会？只需使用 struct 并将 &dummy_align_var 返回给用户作为空闲块的开始。

哦，由于这是为了调试，我建议您添加一个 mungwall：在用户区域的两侧放置 16 个字节，并用某种模式填充它们（例如 0xdeadbeef，重复四次）。在 free() 期间检查这些字节是否没有改变。

[编辑] 这是一些伪代码：

struct header {
    struct header * next;
    unsigned size;
    // put mungwall here
    double user_data;
};

init()
    int blockSize = 1024;
    char * bigMem = original_malloc(blockSize);
    struct header * first = (struct header *)bigMem;
    first->next = NULL;
    first->size = blockSize - (sizeof(struct header) - sizeof(double));

Answer 4

您可能还想将 dummy_align_var 声明为 union header* prev ，以便可以将空闲内存块放入双向链表中。

当您想要将释放的块与前一个和下一个黑色块合并（以防它们也空闲）时，这对性能有很大帮助。

最后，您没有提到这一点，保持列表按大小排序可以更快地找到为给定请求分配的最佳块，而按地址排序可以更轻松地合并已释放的块。如果您想同时执行这两个操作，请将用户部分设置为至少 3 header* 大，它将适合释放块时所需的指针。

除了 Aaron 提到的边界之外，还用相同的模式覆盖释放的缓冲区。这使得更容易识别使用已释放缓冲区的代码。

Answer 5

我建议这会很有用：
几年前，我需要备份 malloc() 工具以用于调试目的（分配跟踪器等）...并且从他们的 libstdc 中获取 FreeBSD 实现非常容易。我记得 FreeBSSD 5.0 甚至 4.x 后期版本，但有趣的是它们的设施被隔离在简单的库 malloc.o 模块中，因此该层的重载非常简单的复制粘贴，并且实现非常好。

你真的要做所有这些工作吗？是的，这只是检查点，我不假装这个解决方案是最好的。

Answer 6

如果需要，您可以使用原始联合，如下所示：

union header *hdr = malloc(total_size);
void *user_ptr = hdr + 1;
char *trailer_ptr = (char *)user_ptr + user_size;

这会将 user_ptr 设置为下一个 union header 的开始位置，如果 malloc ed 块被视为这些联合的数组。这就是您返回给用户的价值。

它还将 trailer_ptr 设置为指向用户分配后的第一个字节，您可以在其中放置校验和。

Answer 7

如果你不想使用 malloc()，你应该看看 sbrk