heap_allocator
1.0.0
这是我为我一直在开发的一个业余爱好操作系统编写的一个简单的堆分配器。我写这个分配器时只做了很少的研究，并且它被设计得尽可能容易理解。我认为这个存储库对于那些刚接触操作系统开发的人（比如我自己）或者有兴趣查看 malloc 和 free 等函数的简化版本的人来说很有用。
有两个头文件定义堆和链表。编译此存储库：
$ gcc main.c llist.c heap.c -o heap_test
$ ./heap_test
这将运行分配器的演示并打印出一些信息。
为了初始化这个堆，必须提供一段内存。在此存储库中，该内存由malloc提供（是的，通过堆分配堆）。在操作系统设置中，某些页面需要映射并提供给堆（一种情况）。请注意， heap_t结构中的 bin 也需要为其分配内存。
当调用函数 init_heap 时，必须提供空堆结构（带有分配的 bin 指针）的地址。然后，init_heap 函数将创建一个带有标头（ node_t结构）和页脚（ footer_t结构）的大块。为了确定该块的大小，该函数使用常量HEAP_INIT_SIZE 。它将把它添加到start参数中以确定堆的结束位置。
每个内存块的开头都有一个节点结构，末尾有一个页脚结构。该节点保存大小（无论块是否空闲）以及双向链表中使用的两个指针（下一个和上一个）。页脚结构仅保存指向标头的指针（在释放相邻块时使用）。堆末尾的块称为“荒野”块。它是最大的块，其最小和最大大小在 heap.h 中定义。收缩和扩展堆就像调整这个荒野块的大小一样简单。空闲的内存块存储在“bins”中，每个bin实际上只是具有相似大小的节点的双向链接列表。堆结构保存定义数量的 bin（heap.h 中的BIN_COUNT ）。为了确定放置块的 bin，块的大小通过函数get_bin_index映射到 bin 索引。这种一致的分箱功能将确保可以以定义的方式访问和存储块。块在插入到 bin 时进行排序，因此块插入不是 O(1)，但这使得更容易找到最适合的块。请注意，可以按照该堆的用户认为合适的方式定义分箱函数。确定更复杂的分箱函数以帮助快速检索块可能是有益的。
函数heap_alloc获取要分配的堆结构的地址和大小。该函数只是使用get_bin_index来确定该大小的块应该在哪里，当然可能不存在该大小的块。如果在相应的 bin 中没有找到块，则将检查下一个 bin。这将继续，直到找到一个块，或者到达最后一个 bin，在这种情况下，将从荒野块中取出一块内存。如果找到的块足够大，那么它将被分割。为了确定是否应该分割一个块，从我们当前分配不使用的元数据量（开销）中减去。如果剩下的内容大于或等于MIN_ALLOC_SZ那么这意味着我们应该分割这个块并将剩余的内容放入正确的垃圾箱中。一旦我们准备好返回找到的块，我们就获取next字段的地址并返回它。这样做是因为在分配块时未使用next和prev字段，因此块的用户可以将数据写入这些字段，而不会影响堆的内部工作。
函数heap_free采用heap_alloc返回的指针。它减去正确的偏移量以获得节点结构的地址。不是简单地将块放入正确的容器中，而是检查所提供的块周围的块。如果这些块中的任何一个是空闲的，那么我们可以合并这些块以创建更大的块。为了合并块，页脚用于获取前一个块的节点结构和下一个块的节点结构。例如，假设我们有一个名为to_free块。为了获取该块之前的块，我们减去sizeof(footer_t)以获取前一个块的页脚。页脚包含指向前一个块的头部的指针。要获取下一个块，我们只需获取to_free的页脚，然后添加sizeof(footer_t)即可获取下一个块。一旦完成所有这些并重新计算大小，该块就会被放回容器中。
注意：此代码最初是为 32 位机器编译的，这意味着当使用此代码时，可以将 int 转换为指针，因为它们的大小相同。在 64 位系统上，编译器会警告您大小差异。为了消除这些警告，我在从 unsigned int 转换为指针时使用了uintptr_t 。这确实使可读性有点混乱，并且一些强制转换和指针算术很冗长，因此在阅读代码时请记住这一点。
