c - 如何保护解释器的 native 调用堆栈免受垃圾收集？

Question

我正在用 C 编写一个 Lisp 解释器。每个 Lisp 对象都由一个 struct LispObject * 和一个 type 字段来表示它是否是一个 int，symbol，缺点等。我将全局环境实现为包含名称和值对的哈希表。

LispObject 始终使用 malloc 动态分配。每当创建一个新对象时，它都会添加到弱引用列表中。当垃圾收集器运行时，它标记所有可从全局环境访问的对象，然后清除弱引用并释放未标记的对象。

保护全局环境免受垃圾收集的影响很容易。我坚持的是如何保护本地 Lisp 对象。明确地说，我还没有实现 Lisp 函数。我要问的是如何保护 LispObject * 类型的局部 C 变量。例如，eval 是一个 C 函数，它接受一个 LispObject * 表达式，应用评估规则，并返回一个 LispObject * 值。我需要保护 eval 中的局部 LispObject * 变量(以及处理 Lisp 对象的其他 C 函数)免受垃圾回收，直到函数返回。

最干净的方法是什么？有什么方法可以标记任何可从 C 调用堆栈访问的 LispObject 吗？

我考虑过实现一个单独的堆栈，仅用于存储不应被垃圾收集的本地 Lisp 对象，但这感觉很笨重，因为本地 LispObject * 变量存储在 C 调用堆栈中在垃圾收集堆栈上，我必须手动推送和弹出对象才能调用 C 函数。理想情况下，当 Lisp 对象存在于本地范围内时，它们将自动受到保护，然后在超出范围时自动失去这种保护。

完整代码:https://notabug.org/jtherrmann/lisp-in-c

Answer 1

我假设您的 GC 是精确 GC。您首先需要定义 可能调用您的 GC 的时间。一个常见的场景是让每个分配例程都可能调用 GC。

您需要编写一个例程来扫描您的调用堆栈以查找本地根。所以你需要有一个机制来将这些局部变量注册到你的 GC 中。换句话说，您应该显式显示您的解释器的调用堆栈(或采用某种 continuation-passing style 方法)。

一种可能是显式您的本地框架作为一些结构。例如查看 Ocaml 运行时的功能(阅读其 §20.5 Living in harmony with the garbage collector 部分)或查看我的旧(未维护)Qish GC。例如，您可以采用每个本地解释器框架都在某个 _ 局部变量(一个 struct)中的约定并使用它。在我的 bismon项目 我会编写一些与此几乎相同的代码(在预处理器扩展之后)，对于具有指针参数 a 和两个本地指针 b 的 C 例程 crout > 和 c

 void crout(struct callingframe_st *cf, LispObject*a) {
   struct mycallframe_st {
      struct callingframe_st* from;
      int nbloc;
      LispObject* aa;
      LispObject* bb;
      LispObject* cc;
   } _;
   memset(&_, 0, sizeof(_));
   _.from = cf;
   _.nbloc = 3; // the current frame has 3 locals: aa, bb, cc
   _.aa = a;
   #define a _.aa
   #define b _.bb
   #define c _.cc

然后是 crout 的主体。它会将 (struct callingframe_st*)(&_) 传递给适当的例程。最后，一定要 #undef a 等...从分配例程调用的 GC 必须将 (struct callingframe_st *)(&_) 作为参数(给出当前调用帧)。

当然，你的b_cons，假设它可以间接调用你的GC，应该声明为

LispObject* b_cons(struct callingframe_st*cf, 
                    LispObject * car, LispObject * cdr);

否则，您需要定义何时调用您的 GC。

---

您需要了解垃圾收集的工作原理(以及精确和保守 GC 之间的区别)。我强烈建议阅读 GC handbook或者至少是 Paul Wilson 的旧 Uniprocessor Garbage Collection Techniques 纸。您可以采用所有例程都遵循 A-normal form 的约定风格(所以你永远不会直接在 C f(g(x),h(x,y)) 中使用所有 f, g, h 可能在进行对象分配)。

您还可以使用一些现有 精确 GC，例如 Ravenbrook MPS .

否则，使用一些保守 GC，例如Boehm's GC .

另请查看具有某些 GC 的现有免费软件解释器的源代码。

另请阅读 Queinnec 的 Lisp In Small Pieces书

---

I have to manually push and pop objects in order to call C functions.

这可能是个好主意(但您随后需要重写大部分代码，并且您实际上可能会定义自己的 bytecode 机制)。看什么Lua或 Nim或 Ocaml字节码解释器或 Emacs Elisp解释器正在做的。

---

为了完成，您可能会考虑(这真的很难，我不建议走那条路，因为这需要很多年的工作)写一些 GCC plugin生成和/或添加临时调用框架元数据和/或生成调用框架相关代码以帮助您进行精确的 GC。这真的很难。 IIRC, CLASP正在做类似的事情(在 Clang 之上，而不是 GCC)。

---

不要忘记垃圾收集是整个程序的事情。