带红黑树的空闲列表分配器
Free List Allocator with Red Black Tree
我正在尝试使用红黑树实现空闲列表分配器以优化 O(LogN) 最适合搜索。
我的策略是，当一个块被分配时，它被分配一个 Header where
struct Header {
std::size_t m_Size;
};
因此sizeof(Header) == sizeof(std::size_t)
这已经完成，所以在释放时我可以知道分配了多少字节以将其作为空闲节点返回。
现在这个解决方案有问题，因为现在我必须将 Header 本身 + 分配的块对齐到请求的对齐方式，所以在 Header 和分配的块开始之间填充，并且需要在分配块的末尾和新 Header 的开始之间进行填充（因此下一个块 Header 将已经对齐）。
为了更好地说明问题，这里有一个红黑树，其节点指示空闲块大小减去 sizeof(Header)
现在假设用户分配了一个大小为 16 且对齐为 16 的块：
allocate(16, 16);
现在最适合的节点将为我们生成节点 17。
但是我们不能指望它，假设节点 17 位于地址 0x8 并且我们在 x32 上，所以 sizeof(Header) = 4.
Header 的地址将来自 0x8-0xC，现在我们需要添加一个填充，以便我们的块将按要求对齐到 16，此填充等于 4 个字节，因此我们分配的块将从0x10 与 16 对齐。现在块末尾不需要填充，因为 0x10 + 16d 将与下一个块对齐 Header.
分配块末尾到新块开始之间的填充很容易预先计算，如下所示：
std::size_t headerPadding = size % sizeof(Header) != 0 ? sizeof(Header) - size % sizeof(Header) : 0;
所以它不依赖于空闲节点的地址。
但是 Header 末尾和分配块 开始之间的填充 IS 取决于空闲节点的地址，就像我演示的那样。
对于我们的示例，在这个特定节点的情况下，总需要的大小将是 4（Header 和分配块之间的填充）+ 16（分配块大小）+ 0（下一个空闲块头对齐所需的填充）= 20.
显然节点17不匹配。
现在我解决这个问题的策略如下：
- 找到最合适的
- 查看是否最合身符合描述的尺寸要求
- 如果是，我们就完成了
- 如果没有得到它的继任者并检查它是否符合描述的尺寸要求
- 如果是，我们就完成了
- 如果不从后继父节点重新开始，直到我们到达满足大小要求的节点或我们再次达到原始最佳拟合
下面是描述该过程的代码：
void FreeTreeAllocator::Find(const std::size_t size, const std::size_t alignment, std::size_t& sizePadding, std::size_t& headerPadding, RBTree::Node*& curr)
{
headerPadding = size % sizeof(Header) != 0 ? sizeof(Header) - size % sizeof(Header) : 0;
RBTree::Node* best = m_Tree.SearchBest(m_Tree.m_Root, size + headerPadding);
RBTree::Node* origin = best;
std::vector<std::size_t> visited;
while (visited[visited.size() - 1] != (std::size_t)origin && !IsNodeBigEnough(size, alignment, sizePadding, headerPadding, best))
{
RBTree::Node* successor = m_Tree.Successor(best);
if (IsNodeBigEnough(size, alignment, sizePadding, headerPadding, successor))
{
best = successor;
break;
}
else
{
std::vector<std::size_t>::iterator it;
do {
best = successor->m_Parent;
it = std::find(visited.begin(), visited.end(), (std::size_t)best);
} while (it != visited.end());
}
visited.push_back((std::size_t)best);
}
}
bool FreeTreeAllocator::IsNodeBigEnough(const std::size_t size, const std::size_t alignment, std::size_t& sizePadding, std::size_t& headerPadding, RBTree::Node* curr)
{
if (curr == m_Tree.m_Nil)
return false;
void* currentAddress = reinterpret_cast<char*>(curr) + sizeof(Header);
std::size_t space = curr->m_Value;
std::align(alignment, size, currentAddress, space);
sizePadding = reinterpret_cast<char*>(currentAddress) - reinterpret_cast<char*>(curr) - sizeof(Header);
return sizePadding + size + headerPadding <= curr->m_Value;
}
现在对于给定的分配请求：
allocate(16, 16);
和图片中给定的示例树下面描述的算法，搜索路径将是：
17 -> 21 -> 22 -> 23 -> 25 -> 27
在最坏的情况下，这是 O(LogN + M)，其中 M 是原始最适合节点的右子树的大小。
现在有一种方法可以解决这个问题，如果我使 sizeof(Header) = sizeof(std::max_align_t)，这样 Header 和分配块开始之间的填充将始终为 0，所以我们不再需要这个填充，因为每个请求都将在没有这个填充的情况下对齐，所以我们真的可以这样做：
void FreeTreeAllocator::Find(const std::size_t size, std::size_t& headerPadding, RBTree::Node*& curr)
{
headerPadding = size % sizeof(Header) != 0 ? sizeof(Header) - size % sizeof(Header) : 0;
RBTree::Node* best = m_Tree.SearchBest(m_Tree.m_Root, size + headerPadding);
return best;
但是，与我提出的 O(LogN + M) 最适合搜索的想法相比，这会浪费大量内存。
现在我为什么要问呢？
因为我看到使用 Red Black Tree 作为空闲列表分配器的优化以将最适合搜索减少到 O(LogN) 而我似乎无法真正做到 O(LogN)，我猜我的设计缺陷是需要有一个 Header 来记录释放时要返回给空闲块的字节数，如果没有这个，我看不出有什么方法可以做到一个 Header ，或者这样做，这样我就可以在列表中查找特定于节点的填充时对齐（通过使 sizeof(Header) = sizeof(std::max_align_t)，甚至 sizeof(Header) = 1) 那么这可以通过简单的 O(LogN) 搜索来解决。
我正在寻找有关如何解决此问题的想法，其他实现如何在 O(LogN) 中做到这一点，同时保持尽可能低的内部碎片？
更新:
我最终将节点地址与 alignof(std::max_align_t) - sizeof(Header) 对齐，这样无论您是否在 x32/x64 上，Header 始终对齐（请记住 Header 由 sizeof(std::size_t)), 而不管 alignof(std::max_align_t) 是 8 还是 16.
这使得分配的有效负载从与 alignof(std::max_align_t) 对齐的地址开始，就像 malloc, 所以无论分配什么，它总是与最大对齐对齐，并且 Header 和有效负载之间不需要填充。
唯一需要的填充是在有效载荷之后匹配下一个与 alignof(std::max_align_t) - sizeof(Header) 对齐的地址 + 使其成为所需的任何填充，因此分配的块至少 sizeof(RBTree::Node) 字节大（包括 sizeof(Header) 内部等式）所以当释放时我们可以安全地存储一个RBTree::Node而不覆盖其他数据。
在 Header 和有效负载之间没有填充，并且需要将下一个块对齐到 alignof(std::max_align_t) - sizeof(Header) 的填充，我们可以轻松地使用 O(LogN) 的默认值 RBTree::Search，因为填充可以是根据块的大小预先计算并从等式中删除特定节点的起始地址。
我将这个空闲列表分配器优化为 O(LogN) 唯一剩下的问题是释放部分，更准确地说是合并部分。
我现在无法解决的是如何O(1)聚结。我重新排列了 RBTree::Node 结构，例如 m_Parent 是第一个，所以它的 LSB 总是设置为 1（对于每个依赖 m_Parent 的函数，我有一个 getter 函数来修复它) 然后我可以检查当前释放块的下一个块（我们可以从 Header 到达下一个大小的块）如果第一个 sizeof(std::size_t) 字节 & 0x1 是真的，如果是的话它是空闲节点，如果不是，它是一个带有 Header 的繁忙块（因为 Header 的 m_Size LSB 将始终为 0，因为我们添加填充以与 std::max_align_t 对齐）。
剩下的问题是如何到达前一个内存块并知道它是空闲还是忙碌，我还不能确定，很想听听建议。
对于填充问题：
确保您的空闲列表节点的大小是 2 的幂——16 或 32 字节——并确保您的空闲列表节点的地址全部对齐 node_size * x - sizeof(Header) 字节。
现在，您的所有分配都将自动按节点大小的倍数对齐，无需填充。
需要更大对齐的分配将很少见，因此找到合适大小的 left-most 块并在树中向前走直到找到有效的块可能是合理的。
但是，如果您需要优化 large-alignment 分配，那么您可以先按大小对块进行排序，然后通过对每个节点分配地址（节点地址 + sizeof(Header)).
然后，在树中进行一次搜索将找到一个可用的 exactly-fitting 块，或者找到一个更大的块。您很有可能能够以满足对齐要求的方式拆分较大的块，但如果没有，那么您可以再次在树中向前跳转以找到该大小有效的块，或者甚至更大的块等
结果搜索速度更快，但仍不能保证 O(log N)。要解决这个问题，您可以在向前跳过有限次数后放弃，然后恢复寻找 requested_size + requested_alignment 的块。如果您找到其中之一，那么可以保证您能够将其拆分以满足您的对齐约束。
there need to be a Header for book-keeping on how much bytes to give back to a free block when deallocating
在 64 位平台上，消除 header 的一种方法是让您的分配器管理 power-of-2 object 大小的区域。每个竞技场都有一个 object 大小，所有竞技场的大小都相同。然后以这种方式映射（仅保留）一大块虚拟内存，使其按其自身大小（也是 2 的幂）对齐。这样，您指向 object 的指针就是结构化的：低位是竞技场内 object 的偏移量，接下来的位是竞技场编号。对于每个竞技场，它需要维护空闲列表并分配 object 计数，但空闲列表最初必须仅包含一页或 1 object（以较大者为准），以便它不会提交页面帧到整个保留的虚拟内存，这将 运行 立即内存不足。
例如，如果您有 8GiB arenas objects 的 power-2-sizes 从 8 到 65536 字节，那么较低的 [0:32] 位是 object 内的偏移量竞技场，位 [33:36] 是竞技场编号和 object 大小的 log2（竞技场 [0, 2] 未使用，因为它们对于空闲列表下一个指针来说不够大）。
完整的答案是我的 OP 更新和这个答案。
我在 O(1).
中找到了聚结的解决方案
我的 OP 更新描述了我们如何在 O(1) 中实现与下一个块的合并，但没有描述如何在 O(1) 中与前一个块实现合并。
为此，我在繁忙块 Header 结构和 RBTree::Node 结构中存储了一个额外的 std::size_t m_PrevSize 作为 第一个成员 。
当一个块被分配并变得繁忙时（通过简单分配或块分割），我只需使用 Header 的 m_Size 属性 和第一个 [=18] 移动到下一个块=] 字节为 0。这会将下一个内存块设置为忙碌或空闲，而前一个内存块很忙，因此无需合并。
当一个块被释放并且我将它转换为空闲块时，我做同样的事情但是将第一个 std::size_t 字节设置为 RBTree::Node 的 m_Value 属性 这基本上是如何这个空闲块有很多字节，在释放时我可以检查自己的 m_PrevSize 属性 如果它不是 0 则返回 m_PrevSize 字节并进行合并。
我正在尝试使用红黑树实现空闲列表分配器以优化 O(LogN) 最适合搜索。
我的策略是，当一个块被分配时，它被分配一个 Header where
struct Header {
std::size_t m_Size;
};
因此sizeof(Header) == sizeof(std::size_t)
这已经完成，所以在释放时我可以知道分配了多少字节以将其作为空闲节点返回。
现在这个解决方案有问题，因为现在我必须将 Header 本身 + 分配的块对齐到请求的对齐方式，所以在 Header 和分配的块开始之间填充，并且需要在分配块的末尾和新 Header 的开始之间进行填充（因此下一个块 Header 将已经对齐）。
为了更好地说明问题，这里有一个红黑树，其节点指示空闲块大小减去 sizeof(Header)
现在假设用户分配了一个大小为 16 且对齐为 16 的块：
allocate(16, 16);
现在最适合的节点将为我们生成节点 17。
但是我们不能指望它，假设节点 17 位于地址 0x8 并且我们在 x32 上，所以 sizeof(Header) = 4.
Header 的地址将来自 0x8-0xC，现在我们需要添加一个填充，以便我们的块将按要求对齐到 16，此填充等于 4 个字节，因此我们分配的块将从0x10 与 16 对齐。现在块末尾不需要填充，因为 0x10 + 16d 将与下一个块对齐 Header.
分配块末尾到新块开始之间的填充很容易预先计算，如下所示：
std::size_t headerPadding = size % sizeof(Header) != 0 ? sizeof(Header) - size % sizeof(Header) : 0;
所以它不依赖于空闲节点的地址。
但是 Header 末尾和分配块 开始之间的填充 IS 取决于空闲节点的地址，就像我演示的那样。
对于我们的示例，在这个特定节点的情况下，总需要的大小将是 4（Header 和分配块之间的填充）+ 16（分配块大小）+ 0（下一个空闲块头对齐所需的填充）= 20.
显然节点17不匹配。
现在我解决这个问题的策略如下：
- 找到最合适的
- 查看是否最合身符合描述的尺寸要求
- 如果是，我们就完成了
- 如果没有得到它的继任者并检查它是否符合描述的尺寸要求
- 如果是，我们就完成了
- 如果不从后继父节点重新开始，直到我们到达满足大小要求的节点或我们再次达到原始最佳拟合
下面是描述该过程的代码：
void FreeTreeAllocator::Find(const std::size_t size, const std::size_t alignment, std::size_t& sizePadding, std::size_t& headerPadding, RBTree::Node*& curr)
{
headerPadding = size % sizeof(Header) != 0 ? sizeof(Header) - size % sizeof(Header) : 0;
RBTree::Node* best = m_Tree.SearchBest(m_Tree.m_Root, size + headerPadding);
RBTree::Node* origin = best;
std::vector<std::size_t> visited;
while (visited[visited.size() - 1] != (std::size_t)origin && !IsNodeBigEnough(size, alignment, sizePadding, headerPadding, best))
{
RBTree::Node* successor = m_Tree.Successor(best);
if (IsNodeBigEnough(size, alignment, sizePadding, headerPadding, successor))
{
best = successor;
break;
}
else
{
std::vector<std::size_t>::iterator it;
do {
best = successor->m_Parent;
it = std::find(visited.begin(), visited.end(), (std::size_t)best);
} while (it != visited.end());
}
visited.push_back((std::size_t)best);
}
}
bool FreeTreeAllocator::IsNodeBigEnough(const std::size_t size, const std::size_t alignment, std::size_t& sizePadding, std::size_t& headerPadding, RBTree::Node* curr)
{
if (curr == m_Tree.m_Nil)
return false;
void* currentAddress = reinterpret_cast<char*>(curr) + sizeof(Header);
std::size_t space = curr->m_Value;
std::align(alignment, size, currentAddress, space);
sizePadding = reinterpret_cast<char*>(currentAddress) - reinterpret_cast<char*>(curr) - sizeof(Header);
return sizePadding + size + headerPadding <= curr->m_Value;
}
现在对于给定的分配请求：
allocate(16, 16);
和图片中给定的示例树下面描述的算法，搜索路径将是：
17 -> 21 -> 22 -> 23 -> 25 -> 27
在最坏的情况下，这是 O(LogN + M)，其中 M 是原始最适合节点的右子树的大小。
现在有一种方法可以解决这个问题，如果我使 sizeof(Header) = sizeof(std::max_align_t)，这样 Header 和分配块开始之间的填充将始终为 0，所以我们不再需要这个填充，因为每个请求都将在没有这个填充的情况下对齐，所以我们真的可以这样做：
void FreeTreeAllocator::Find(const std::size_t size, std::size_t& headerPadding, RBTree::Node*& curr)
{
headerPadding = size % sizeof(Header) != 0 ? sizeof(Header) - size % sizeof(Header) : 0;
RBTree::Node* best = m_Tree.SearchBest(m_Tree.m_Root, size + headerPadding);
return best;
但是，与我提出的 O(LogN + M) 最适合搜索的想法相比，这会浪费大量内存。
现在我为什么要问呢？
因为我看到使用 Red Black Tree 作为空闲列表分配器的优化以将最适合搜索减少到 O(LogN) 而我似乎无法真正做到 O(LogN)，我猜我的设计缺陷是需要有一个 Header 来记录释放时要返回给空闲块的字节数，如果没有这个，我看不出有什么方法可以做到一个 Header ，或者这样做，这样我就可以在列表中查找特定于节点的填充时对齐（通过使 sizeof(Header) = sizeof(std::max_align_t)，甚至 sizeof(Header) = 1) 那么这可以通过简单的 O(LogN) 搜索来解决。
我正在寻找有关如何解决此问题的想法，其他实现如何在 O(LogN) 中做到这一点，同时保持尽可能低的内部碎片？
更新:
我最终将节点地址与 alignof(std::max_align_t) - sizeof(Header) 对齐，这样无论您是否在 x32/x64 上，Header 始终对齐（请记住 Header 由 sizeof(std::size_t)), 而不管 alignof(std::max_align_t) 是 8 还是 16.
这使得分配的有效负载从与 alignof(std::max_align_t) 对齐的地址开始，就像 malloc, 所以无论分配什么，它总是与最大对齐对齐，并且 Header 和有效负载之间不需要填充。
唯一需要的填充是在有效载荷之后匹配下一个与 alignof(std::max_align_t) - sizeof(Header) 对齐的地址 + 使其成为所需的任何填充，因此分配的块至少 sizeof(RBTree::Node) 字节大（包括 sizeof(Header) 内部等式）所以当释放时我们可以安全地存储一个RBTree::Node而不覆盖其他数据。
在 Header 和有效负载之间没有填充，并且需要将下一个块对齐到 alignof(std::max_align_t) - sizeof(Header) 的填充，我们可以轻松地使用 O(LogN) 的默认值 RBTree::Search，因为填充可以是根据块的大小预先计算并从等式中删除特定节点的起始地址。
我将这个空闲列表分配器优化为 O(LogN) 唯一剩下的问题是释放部分，更准确地说是合并部分。
我现在无法解决的是如何O(1)聚结。我重新排列了 RBTree::Node 结构，例如 m_Parent 是第一个，所以它的 LSB 总是设置为 1（对于每个依赖 m_Parent 的函数，我有一个 getter 函数来修复它) 然后我可以检查当前释放块的下一个块（我们可以从 Header 到达下一个大小的块）如果第一个 sizeof(std::size_t) 字节 & 0x1 是真的，如果是的话它是空闲节点，如果不是，它是一个带有 Header 的繁忙块（因为 Header 的 m_Size LSB 将始终为 0，因为我们添加填充以与 std::max_align_t 对齐）。
剩下的问题是如何到达前一个内存块并知道它是空闲还是忙碌，我还不能确定，很想听听建议。
对于填充问题：
确保您的空闲列表节点的大小是 2 的幂——16 或 32 字节——并确保您的空闲列表节点的地址全部对齐 node_size * x - sizeof(Header) 字节。
现在，您的所有分配都将自动按节点大小的倍数对齐，无需填充。
需要更大对齐的分配将很少见，因此找到合适大小的 left-most 块并在树中向前走直到找到有效的块可能是合理的。
但是，如果您需要优化 large-alignment 分配，那么您可以先按大小对块进行排序，然后通过对每个节点分配地址（节点地址 + sizeof(Header)).
然后，在树中进行一次搜索将找到一个可用的 exactly-fitting 块，或者找到一个更大的块。您很有可能能够以满足对齐要求的方式拆分较大的块，但如果没有，那么您可以再次在树中向前跳转以找到该大小有效的块，或者甚至更大的块等
结果搜索速度更快，但仍不能保证 O(log N)。要解决这个问题，您可以在向前跳过有限次数后放弃，然后恢复寻找 requested_size + requested_alignment 的块。如果您找到其中之一，那么可以保证您能够将其拆分以满足您的对齐约束。
there need to be a Header for book-keeping on how much bytes to give back to a free block when deallocating
在 64 位平台上，消除 header 的一种方法是让您的分配器管理 power-of-2 object 大小的区域。每个竞技场都有一个 object 大小，所有竞技场的大小都相同。然后以这种方式映射（仅保留）一大块虚拟内存，使其按其自身大小（也是 2 的幂）对齐。这样，您指向 object 的指针就是结构化的：低位是竞技场内 object 的偏移量，接下来的位是竞技场编号。对于每个竞技场，它需要维护空闲列表并分配 object 计数，但空闲列表最初必须仅包含一页或 1 object（以较大者为准），以便它不会提交页面帧到整个保留的虚拟内存，这将 运行 立即内存不足。
例如，如果您有 8GiB arenas objects 的 power-2-sizes 从 8 到 65536 字节，那么较低的 [0:32] 位是 object 内的偏移量竞技场，位 [33:36] 是竞技场编号和 object 大小的 log2（竞技场 [0, 2] 未使用，因为它们对于空闲列表下一个指针来说不够大）。
完整的答案是我的 OP 更新和这个答案。
我在 O(1).
中找到了聚结的解决方案
我的 OP 更新描述了我们如何在 O(1) 中实现与下一个块的合并，但没有描述如何在 O(1) 中与前一个块实现合并。
为此，我在繁忙块 Header 结构和 RBTree::Node 结构中存储了一个额外的 std::size_t m_PrevSize 作为 第一个成员 。
当一个块被分配并变得繁忙时（通过简单分配或块分割），我只需使用 Header 的 m_Size 属性 和第一个 [=18] 移动到下一个块=] 字节为 0。这会将下一个内存块设置为忙碌或空闲，而前一个内存块很忙，因此无需合并。
当一个块被释放并且我将它转换为空闲块时，我做同样的事情但是将第一个 std::size_t 字节设置为 RBTree::Node 的 m_Value 属性 这基本上是如何这个空闲块有很多字节，在释放时我可以检查自己的 m_PrevSize 属性 如果它不是 0 则返回 m_PrevSize 字节并进行合并。