6

我正在尝试在 C 中编写用于调试目的的自定义分配器（作为练习），其中我将使用单个链表使用 First Fit 算法将内存的空闲列表保持在一起。我在下面显示了我想在“空内存节点”中创建的结构。

我如何在我获得的内存的前几个字节处写入头块（具体来说是一个联合）（我使用 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-----------------------^
*/

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

4

7 回答 7

3

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

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

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

假设你从'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;
}

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

于 2009-11-10T01:07:01.000 回答
2

你为什么使用工会？只需使用 astruct并返回&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));
于 2009-11-09T13:17:54.410 回答
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。

于 2009-11-09T14:02:44.320 回答
1

您可能还想声明dummy_align_varasunion header* prev以便可以将空闲内存块放在双向链表中。

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

最后，您没有提到它，保持列表按大小排序可以更快地找到为给定请求分配的最佳块，而按地址排序可以更容易合并释放的块。如果你想同时做这两个，使用户部分至少 3header*大，它将适合释放块时所需的指针。

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

于 2009-11-09T13:36:34.933 回答
1

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

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

于 2009-11-09T13:52:46.903 回答
1

如果你愿意，你可以使用你原来的工会，像这样：

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

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

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

于 2009-11-09T21:11:06.550 回答
0

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

于 2009-11-09T13:46:50.670 回答