如何保护解释器的本机调用堆栈免受垃圾回收?

问题描述 投票:2回答:1

我在C中编写一个Lisp解释器。每个Lisp对象由一个带有struct LispObject *字段的type表示,以指示它是int,symbol,cons等。我已经将全局环境实现为包含名称对的哈希表和价值观。

LispObjects总是动态分配malloc。每当创建一个新对象时,它就会被添加到一个弱引用列表中。当垃圾收集器运行时,它会标记从全局环境可到达的所有对象,然后扫描弱引用并释放未标记的对象。

保护全球环境免受垃圾收集很容易。我坚持的是如何保护本地Lisp对象。为了清楚起见,我还没有实现Lisp函数。我问的是如何保护LispObject *类型的本地C变量。例如,eval是一个C函数,它采用LispObject *表达式,应用评估规则,并返回LispObject *值。我需要保护LispObject *中的本地eval变量(以及处理Lisp对象的其他C函数)从垃圾收集直到函数返回。

最干净的方法是什么?有没有办法标记从C调用堆栈可以访问的任何LispObjects?

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

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

c garbage-collection stack lisp interpreter
1个回答
1
投票

我假设您的GC是精确的GC。您首先需要定义何时可能调用GC。常见的情况是让每个分配例程可能调用GC。

您需要编写一个例程来扫描您的调用堆栈以获取本地根。因此,您需要一台将这些局部变量注册到GC的机器。换句话说,你应该明确你的解释器的调用堆栈(或采用一些continuation-passing style方法)。

可能的可能是将您的本地帧显示为某些struct。查看Ocaml运行时的内容(阅读其章节§20.5 Living in harmony with the garbage collector)或我的旧(未维护的)Qish GC。例如,您可以采用每个局部解释器框架在某个_局部变量(struct)中并使用它的约定。在我的bismon项目中,我会编写一些几乎等效的东西(在预处理器扩展之后),对于C例程crout有一个指针参数a和两个本地指针bc

 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或至少保罗威尔逊的旧Uniprocessor Garbage Collection Techniques纸。您可以采用所有惯例遵循A-normal form样式的约定(因此您永远不会直接在C f(g(x),h(x,y))中编码所有fgh可能正在进行对象分配)。

您也可以使用一些现有的精确GC,例如Ravenbrook MPS

否则,使用像Boehm's GC这样的保守GC。

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

另请阅读Queinnec的Lisp In Small Pieces


我必须手动推送和弹出对象才能调用C函数。

这可能是个好主意(但是你需要重写大部分代码,你可能实际上定义了自己的bytecode机器)。看看LuaNimOcaml字节码解释器或Emacs Elisp解释器正在做什么。


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


不要忘记垃圾收集是一个完整的程序。

© www.soinside.com 2019 - 2024. All rights reserved.