在 C 中以独立于机器的方式引用堆地址

Question

我正在为编译器构建垃圾收集器。我使用 "physical" 和 "virtual" 地址。虚拟地址的类型为 value_t 且为 32 位。物理地址的类型为 value_t* 并且是 32 位或 64 位指针，具体取决于主机。两者之间的转换如下：

static void* addr_v_to_p(value_t v_addr) {
  assert(0 <= v_addr);
  return (char*)memory_start + v_addr;
}

static value_t addr_p_to_v(void* p_addr) {
  assert(memory_start <= p_addr && p_addr <= memory_end);
  return (value_t)((char*)p_addr - (char*)memory_start);
}

然后我设置了一个类似这样的内存布局：

位图必须引用堆的值。

问题

我想以独立于机器的方式在地址的位图中给出索引。（为此目的，将 VALUE_BITS = sizeof(value_t) * CHAR_BITS 设置为 value_t 类型的位数变得很方便）。我会写：

(ptr, heap_start, bitmap_start of type value_t*)
size_t index = ptr - heap_start;
size_t word_index = index / VALUE_BITS;
bitmap_start[word_index] = ...;

但我不确定这是否有效。

Answer 1

据我了解，您的 "bitmap" 是位序列，每个堆地址都有一个对应的唯一位。大概您还想尽量减少未使用的位数。你问的是你提出的堆地址和位之间映射的方法。

此外，您在虚拟地址和物理地址之间提供的转换函数表明您的内存模型是字节可寻址的，而不是只能以 value_t.[=32 的粒度寻址=]

由于您的位图显然是以 value_t 类型的单位访问的，我认为它是无符号且没有填充位的，因此每个单位中的可用位数是 sizeof(value_t) * CHAR_BIT。这与您的 VALUE_BITS 模数拼写匹配。尽管如此，如果 bitmap_start 将（或合理地可以使）在定义 VALUE_BITS 的任何地方可见（如果它是一个变量）或使用（如果它是一个宏），那么我会倾向于将其初始值设定项/替换文本写为 (sizeof(*bitmap_start) * CHAR_BIT)。如果您更改 bitmap_start 指向的类型，这对我来说更清楚并且会自动适应。

现在让我们考虑从以下开始的代码：

size_t index = ptr - heap_start;

这本身并没有错，但请记住，指针算法是根据指向类型的单位定义的。因此，这给出了由两个指针定义的半开区间中 value_t 类型的单元数，假设 ptr 指向或刚好超过堆的末尾 并且是正确对齐。对齐警告很重要，因为您的模型是字节可寻址的，因此 ptr 可以采用未对齐的有效值。事实上，大多数有效 ptr 值都未对齐。如果您希望根据堆中 byte 偏移量的索引 - 看起来您这样做 - 那么您需要更像这样的东西：

ptrdiff_t index = (char *) ptr - (char *) heap_start;

让我们继续下一部分：

size_t word_index = index / VALUE_BITS;

您似乎在尝试确定包含 index^th 位的位集中的存储单元。如果我们规定每个单元包含VALUE_BITS个可用位，并且你希望每个单元中的每个位都对应一个堆地址，那么就可以了。

但你似乎运行失去了动力，因为这...

bitmap_start[word_index] = ...;

... 细节略有欠缺。您将需要使用位掩码 select bitmap_start[word_index] 的适当位来检查或设置，并且在这样做时您需要注意避免修改相同的其他位单元。这并不难，但我不会为你做。

在 C 中以独立于机器的方式引用堆地址

Referencing heap addresses in a machine independent way in C

c

garbage-collection

bitmap

memory-address