内存引用如何定位在移动的垃圾回收实现中？
How are memory references located in a moving garbage collection implementation?
在移动的垃圾收集器中，必须有一种精确的方法来区分堆栈和堆上的哪些值是引用，哪些是立即值。在我读过的关于垃圾收集的大部分文献中，这个细节似乎都被掩盖了。
我研究过为每个堆栈帧分配一些前导码是否可行，例如，在调用每个参数之前对其进行描述。但可以肯定的是，这一切所做的只是将问题转移到间接的更高层次。那么，在 GC 循环期间遍历前导码以获取立即值或引用时，如何区分前导码和堆栈帧？
有人可以解释一下这在现实世界中是如何实现的吗？
这里是这个问题的示例程序，它使用第一个 class 函数词法闭包及其栈帧图和位于堆上的父环境：
一个示例程序
def foo(x) = {
def bar(y,z) = {
return x + y + z
}
return bar
}
def main() = {
let makeBar = foo(1)
makeBar(2,3)
}
调用时 Bar 的栈帧:
在此示例中，bar 的堆栈帧有一个局部变量 x，它是指向堆上某个值的指针，其中参数 y 和 z 是立即整数值。
我读到 Objective CAML 为放置在堆栈上的每个值使用一个标记位，该标记位作为每个值的前缀。允许在 GC 循环期间对每个值进行二进制 ref-or-imm 检查。但这可能会产生一些不需要的副作用。整数限制为 31 位，并且需要调整原始计算的动态代码生成以弥补这一点。总之——感觉有点太脏了。一定有更优雅的解决方案。
是否可以静态地知道和访问这些信息？比如以某种方式将类型信息传递给垃圾收集器？
Could somebody explain how this is implemented in the real world?
有几种可能的方法
- 保守的堆栈扫描。一切都被视为潜在的指针。这会导致 GC 不精确。不精确的扫描会阻止对象被重新定位，这反过来会阻止或复杂化 semi-space/compacting GCs.
的实施
- 如您所述，标记位。这可以被认为是不太保守的扫描，但它仍然不精确
- 编译器在任何给定时间保留确切堆栈布局的知识，即指针所在的位置。由于这可能会因指令而异，并且指针也可以驻留在寄存器中，因此这将非常复杂。
作为一种简化，它仅针对所有线程可以协作将控制权移交给 GC 的特定点进行当另一个线程请求 GC 时，已知堆栈布局。这称为安全点（在下面解释）。
- 可能还有其他机制，例如将堆栈划分为引用和非引用条目，并始终确保已注册的引用也在堆栈中的某处，但我不知道这种方法有多实用
Gil Tene 对什么是安全点有一个很好的解释，尽管主要是 JVM 特定的解释，所以我将在这里引用相关部分：
Here is a collection of statement about "what is a safepoint" that
attempt to be both correct and somewhat precise:
- A thread can be at a safepoint or not be at a safepoint. When at a safepoint, the thread's representation of it's Java machine state is
well described, and can be safely manipulated and observed by other
threads in the JVM. When not at a safepoint, the thread's
representation of the java machine state will NOT be manipulated by
other threads in the JVM. [Note that other threads do not manipulate a
thread's actual logical machine state, just it's representation of
that state. A simple example of changing the representation of machine
state is changing the virtual addresss that a java reference stack
variable points to as a result of relocating that object. The logical
state of the reference variable is not affected by this change, as the
reference still refers to the same object, and two references variable
referring to the same object will still be logically equal to each
other even if they temporarily point to different virtual addresses].
[...]
- All [practical] JVMs apply some highly efficient mechanism for frequently crossing safepoint opportunities, where the thread does not
actually enter a safepoint unless someone else indicates the need to
do so. E.g. most call sites and loop backedges in generated code will
include some sort of safepoint polling sequence that amounts to "do I
need to go to a safepoint now?". Many HotSpot variants (OpenJDK and
Oracle JDK) currently use a simple global "go to safepoint" indicator
in the form of a page that is protected when a safepoint is needed,
and unprotected otherwise. The safepoint polling for this mechanism
amounts to a load from a fixed address in that page. If the load traps
with a SEGV, the thread knows it needs to go to enter a safepoint.
Zing uses a different, per-thread go-to-safepoint indicator of similar
efficiency.
[...]
上面的答案确定了三个主要备选方案。已经尝试了第三个备选方案的变体：
- 让编译器对堆栈和对象框架中的变量进行分区/重新排序，以便（例如）引用变量位于标量变量之前。
也就是说，运行时需要保留的类型信息是一个单一的数字。这可以存储在框架本身中，或者作为与 class 或方法相关联的类型信息......以正常方式。但是，这会引入其他开销；例如需要双堆栈和堆栈指针。根据经验，这不是胜利。
其他几点：
各种GC都存在识别引用的问题
如果您采用 "conservative" 方法（其中引用标识可能不准确），那么您无法安全地压缩堆。这包括各种复制收集器。
标记位（除非它们是硬件支持的）对于高效的算术运算来说可能是有问题的。 （如果你需要 "steal" 一点来区分指针和非指针，那么算术运算需要额外的指令来补偿。FWIW，麻省理工学院的 CLU 编译器曾经这样做......早在 1980 年代。CLU GC是一个准确的 mark/sweep/compact 收集器，但整数运算很慢......我不记得他们是如何处理浮点数的。）
我发现了另一种可能的方法，描述为 Emery's Idea:
- Run two copies of a program. When checking a suspected pointer check both copies of memory.
- If the int/pointer in question is the same in both programs it is an int.
- If the int/pointer has the same base but a different offset then it is a pointer.
我可以看到这在现实世界的例子中有显着的性能开销，但对于顺序语言，或者那些 运行 在用户 space 中使用减少计时器并发在单核上的语言是可能的方法。
在移动的垃圾收集器中，必须有一种精确的方法来区分堆栈和堆上的哪些值是引用，哪些是立即值。在我读过的关于垃圾收集的大部分文献中，这个细节似乎都被掩盖了。
我研究过为每个堆栈帧分配一些前导码是否可行，例如，在调用每个参数之前对其进行描述。但可以肯定的是，这一切所做的只是将问题转移到间接的更高层次。那么，在 GC 循环期间遍历前导码以获取立即值或引用时，如何区分前导码和堆栈帧？
有人可以解释一下这在现实世界中是如何实现的吗？
这里是这个问题的示例程序，它使用第一个 class 函数词法闭包及其栈帧图和位于堆上的父环境：
一个示例程序
def foo(x) = {
def bar(y,z) = {
return x + y + z
}
return bar
}
def main() = {
let makeBar = foo(1)
makeBar(2,3)
}
调用时 Bar 的栈帧:
在此示例中，bar 的堆栈帧有一个局部变量 x，它是指向堆上某个值的指针，其中参数 y 和 z 是立即整数值。
我读到 Objective CAML 为放置在堆栈上的每个值使用一个标记位，该标记位作为每个值的前缀。允许在 GC 循环期间对每个值进行二进制 ref-or-imm 检查。但这可能会产生一些不需要的副作用。整数限制为 31 位，并且需要调整原始计算的动态代码生成以弥补这一点。总之——感觉有点太脏了。一定有更优雅的解决方案。
是否可以静态地知道和访问这些信息？比如以某种方式将类型信息传递给垃圾收集器？
Could somebody explain how this is implemented in the real world?
有几种可能的方法
- 保守的堆栈扫描。一切都被视为潜在的指针。这会导致 GC 不精确。不精确的扫描会阻止对象被重新定位，这反过来会阻止或复杂化 semi-space/compacting GCs. 的实施
- 如您所述，标记位。这可以被认为是不太保守的扫描，但它仍然不精确
- 编译器在任何给定时间保留确切堆栈布局的知识，即指针所在的位置。由于这可能会因指令而异，并且指针也可以驻留在寄存器中，因此这将非常复杂。
作为一种简化，它仅针对所有线程可以协作将控制权移交给 GC 的特定点进行当另一个线程请求 GC 时，已知堆栈布局。这称为安全点（在下面解释）。 - 可能还有其他机制，例如将堆栈划分为引用和非引用条目，并始终确保已注册的引用也在堆栈中的某处，但我不知道这种方法有多实用
Gil Tene 对什么是安全点有一个很好的解释，尽管主要是 JVM 特定的解释，所以我将在这里引用相关部分：
Here is a collection of statement about "what is a safepoint" that attempt to be both correct and somewhat precise:
- A thread can be at a safepoint or not be at a safepoint. When at a safepoint, the thread's representation of it's Java machine state is well described, and can be safely manipulated and observed by other threads in the JVM. When not at a safepoint, the thread's representation of the java machine state will NOT be manipulated by other threads in the JVM. [Note that other threads do not manipulate a thread's actual logical machine state, just it's representation of that state. A simple example of changing the representation of machine state is changing the virtual addresss that a java reference stack variable points to as a result of relocating that object. The logical state of the reference variable is not affected by this change, as the reference still refers to the same object, and two references variable referring to the same object will still be logically equal to each other even if they temporarily point to different virtual addresses].
[...]
- All [practical] JVMs apply some highly efficient mechanism for frequently crossing safepoint opportunities, where the thread does not actually enter a safepoint unless someone else indicates the need to do so. E.g. most call sites and loop backedges in generated code will include some sort of safepoint polling sequence that amounts to "do I need to go to a safepoint now?". Many HotSpot variants (OpenJDK and Oracle JDK) currently use a simple global "go to safepoint" indicator in the form of a page that is protected when a safepoint is needed, and unprotected otherwise. The safepoint polling for this mechanism amounts to a load from a fixed address in that page. If the load traps with a SEGV, the thread knows it needs to go to enter a safepoint. Zing uses a different, per-thread go-to-safepoint indicator of similar efficiency.
[...]
上面的答案确定了三个主要备选方案。已经尝试了第三个备选方案的变体：
- 让编译器对堆栈和对象框架中的变量进行分区/重新排序，以便（例如）引用变量位于标量变量之前。
也就是说，运行时需要保留的类型信息是一个单一的数字。这可以存储在框架本身中，或者作为与 class 或方法相关联的类型信息......以正常方式。但是，这会引入其他开销；例如需要双堆栈和堆栈指针。根据经验，这不是胜利。
其他几点：
各种GC都存在识别引用的问题
如果您采用 "conservative" 方法（其中引用标识可能不准确），那么您无法安全地压缩堆。这包括各种复制收集器。
标记位（除非它们是硬件支持的）对于高效的算术运算来说可能是有问题的。 （如果你需要 "steal" 一点来区分指针和非指针，那么算术运算需要额外的指令来补偿。FWIW，麻省理工学院的 CLU 编译器曾经这样做......早在 1980 年代。CLU GC是一个准确的 mark/sweep/compact 收集器，但整数运算很慢......我不记得他们是如何处理浮点数的。）
我发现了另一种可能的方法，描述为 Emery's Idea:
- Run two copies of a program. When checking a suspected pointer check both copies of memory.
- If the int/pointer in question is the same in both programs it is an int.
- If the int/pointer has the same base but a different offset then it is a pointer.
我可以看到这在现实世界的例子中有显着的性能开销，但对于顺序语言，或者那些 运行 在用户 space 中使用减少计时器并发在单核上的语言是可能的方法。