内存管理，对于C/C++选手来说，是个再熟悉不过的名词。malloc/free，new/delete，一旦使用不当，就会遇到mem leak，uaf，double free等等内存问题。但是对于其他高级语言例如JAVA，JS等，似乎从来不需要关心他们创建对象的死活，是这些语言可以违背计算机的规律么？当然不是，只是这些语言底层的编译器/虚拟机自动对内存进行了管理，我们一般称之为GC(garbage collect)。
GC的历史可以追溯到上世纪50年代，从诞生之初起，它就像一个幕后英雄，默默做着奉献，帮助开发者提高了开发效率。在我看来，GC就像一种内存扩大技术：我们只需要不断的向其索取，而不用担心由于物理内存限制导致的内存问题。对于GC，虽然它能自动管理内存，但是当我们对它了解的越多，越能帮助我们在日常开发工作中提高代码效率。
常见GC算法简介
众所周知，GC主要负责做两件事：
1. 找到内存空间中的垃圾
2. 回收垃圾，让这块内存可以再次被利用
那么GC算法要解决的问题也就是两件事：
1. 明确什么是垃圾
2. 如何回收，让性能和效率可以尽可能的高
针对这两个问题，GC发展了各种各样的算法，我们来简单看一下。
▐什么是垃圾什么是垃圾？对于开发者而言这很清晰，以后不会再被用到的对象就是垃圾。但对于程序而言，无法在当下判断什么对象就永远不会再被使用，所以对于垃圾的评定只有一个：即无法被任意其他对象访问的内存就是垃圾。对于这种情况，现在有如下两种算法可以解决。
引用计数法RCRC的逻辑是最容易理解也是最清晰的，既然垃圾是无法被任意其他对象访问的，那我只需要记录一下当前对象的被引用情况就可以了。
在对象头header上，我们可以添加一个计数器count。一旦有其他对象来持有当前指针，就对count进行++操作，而一旦这个指针被其他对象释放，那就对count进行--操作。一旦当count的值为0的时候，就说明这个对象没有被其他任何对象持有，那就可以对其下判断——这个对象就是垃圾，那就立刻进行回收。
可达性分析相较于RC，可达性分析的逻辑就比较复杂。可达性分析的算法基础在于，在程序运行的某些时刻，有一些对象是肯定不应该被回收的。这些对象，我们称其为GC Roots。常见的GC Roots有当前栈上的变量，全局变量等等。
那么我们只需要以这些Roots为起点，不断向下遍历它所持有的对象，就可以认为这些被遍历到的都是有可能存活的对象。而剩下的，就是一些垃圾了。
▐如何回收确定了这些垃圾对象，接下来要做的就是回收工作。如何回收？主要有以下这些算法：
GC标记清除法顾名思义，这个算法分为两步，标记 + 清除。标记就是使用之前提到的可达性分析，而清除就是将未被标记的对象全部回收。
GC复制算法复制算法，将对象分配空间分为大小完全相同的两块，其中一块称为from，另一块称为to。当我们申请内存时，只在from空间中分配。而当我们进行垃圾回收时，我们则将from空间中所有的存活对象全部复制到to空间中，然后将整块from空间回收，之后将两块空间身份对换。
GC标记压缩法标记压缩法，听起来和标记清除有点类似。事实上，标记压缩的前两步和标记清除完全一样，都是标记存活对象，将垃圾全部清除。而标记压缩会在清除之后，增加一步内存整理工作，用以减少可能的内存碎片问题。
▐其他一些算法分代算法分代算法是一种经验算法，即在大多数情况下，程序内的对象都是在创建完成后很快被回收。按照这个经验，可以将heap分为两块，其中一块称为年轻代，用以分配那些申请的内存，另一块则称为老年代，用以存储那些满足条件的对象。
大部分时间，我们只需要去遍历年轻代中的对象。而那些经过多次GC仍然未被回收的年轻代对象，就可以晋升到老年代；只有当内存整体触发阈值时，我们才会对整块内存进行回收。
QuickJS的垃圾回收算法Weex团队选择QuickJS作为跨端框架的JS引擎，并在原版的基础上进行了一系列增强和优化，在API上是原版的超集，和原版保持兼容。
在GC算法上，自研的QuickJS目前还是和原版保持一致，使用引用计数法(RC)。
▐引用计数算法正如我们之前说的，RC的逻辑是最简单清晰的，只需要在对象头上添加一个计数器ref_count就可以了。
struct JSGCObjectHeader { int ref_count; /* must come first, 32-bit */ JSGCObjectTypeEnum gc_obj_type : 4; uint8_t mark : 4; /* used by the GC */ uint8_t dummy1; /* not used by the GC */ uint16_t dummy2; /* not used by the GC */ struct list_head link;};刚创建完对象时，ref_count的值被设为1。
p->header.ref_count = 1;如果引用了某个对象，就对其计数器++
static inline JSValue JS_DupValue(JSContext *ctx, JSValueConst v){ if (JS_VALUE_HAS_REF_COUNT(v)) { JSRefCountHeader *p = (JSRefCountHeader *)JS_VALUE_GET_PTR(v); p->ref_count++; } return (JSValue)v;}一旦释放了，就对计数器--
static inline void JS_FreeValue(JSContext *ctx, JSValue v){ if (JS_VALUE_HAS_REF_COUNT(v)) { JSRefCountHeader *p = (JSRefCountHeader *)JS_VALUE_GET_PTR(v); if (--p->ref_count <= 0) { __JS_FreeValue(ctx, v); } }}当ref_count<=0时，则证明这个对象已经没有任何被引用对象，可以放心回收。
void __JS_FreeValueRT(JSRuntime *rt, JSValue v){ uint32_t tag = JS_VALUE_GET_TAG(v); switch(tag) { case JS_TAG_STRING: ...... case JS_TAG_SYMBOL: { JSAtomStruct *p = JS_VALUE_GET_PTR(v); JS_FreeAtomStruct(rt, p); } break; default: printf("__JS_FreeValue: unknown tag=%d\n", tag); abort(); }}好了，RC的逻辑就是这么简洁明了，介绍到这里就算完了。
完了么？
引用计数的问题当然不可能这么简单。
我们来考虑一个简单的问题：假设我们有一个对象A，他有一个引用对象B，记为A->B；对象B，他有一个引用对象C，记为B->C；而C，如果其不幸地引用了A，记为C->A，那么就会形成这种状态：C->A->B->C。形如下图：
这就造成一个严重的问题：这三个对象的计数器永远>=1了，分配的内存就会泄漏再也无法被回收了。我们称之为循环引用导致的泄漏。
如何解决循环引用
QuickJS的RC是如何处理这个问题的呢？
首先，QuickJS中有一个链表struct list_head gc_obj_list，上面存储着所有的被分配内存的JS对象(QuickJS GC主要管理的就是这些对象)。
当内存上涨触发阈值时，我们开始做解环的操作。
void JS_RunGC(JSRuntime *rt){ /* decrement the reference of the children of each object. mark = 1 after this pass. */ gc_decref(rt); /* keep the GC objects with a non zero refcount and their childs */ gc_scan(rt); /* free the GC objects in a cycle */ gc_free_cycles(rt);}解环步骤：
1. 遍历整个gc_obj_list，将上面所有的对象的标记位mark置为1。同时遍历这些对象的子对象，对这些子对象的计数器--。同时做判断，如果这些子对象已被标记并且它的ref_count=0，说明它的入度为1，则将其从gc_obj_list上拿下，挂到一个新的链表tmp_obj_list上。
2. 重新遍历gc_obj_list，首先将所有对象的标记位mark置为0，因为证明这些对象有多个入度，是肯定存活对象。同时继续遍历这些对象的子对象，对这些子对象的计数器++，如果这些对象之前被挂到tmp_obj_list上的话则将这些对象给重新挂到gc_obj_list上。之后将tmp_obj_list上的对象的ref_count++，这一步是为了恢复第一步中的--。
3. 将所有挂在tmp_obj_list上的对象全部回收。
这样，我们就把那些循环引用的环给解开了，并将这些已经除了环以外入度为0的对象全部回收了。
参考资料
《垃圾回收的算法与实现》，作者：中村成洋 / 相川光，译者：丁灵，出版社：人民邮电出版社
团队介绍
我们是淘天集团-跨端技术团队，致力于提供高效且性能优异的跨端研发方案，给业务带来效率和体验的全面提升。这里有开箱即用的跨端工具，也有高性能的 Weex 跨端引擎，在 JS 引擎技术、渲染引擎技术等领域有丰富的技术积累和前沿技术探索。
