Ruby 垃圾回收原理浅析

zhuoerri · 2022年04月26日 · 最后由 xeniasa 回复于 2024年06月29日 · 1115 次阅读

前言

本人水平有限，如有错误，欢迎指正和补充。

本文会用自问自答的形式，用【公司裁员】打比方，结合 Ruby 3.1 源码，科普 Ruby 垃圾回收的基本原理。内容包含：Ruby 内存模型，标记回收算法，分代回收，增量回收，碎片整理，最后借助最新的 Variable Width Allocation，列举一下局部性原理。

Ruby 内存模型

Q: Ruby 对象在内存里是怎么存储管理的？

每个 Ruby 对象占用一个slot，一个slot 在 64 位的机器上占 40 字节，多个slot聚成一个 Rubypage。所有page组成了Ruby HEAP。如果 Ruby 对象太大，例如一个很长的 String，40 个字节放不下。则在总HEAP里 malloc 一块额外内存来存储。如下图，第一个slot指向了额外数据。

┌──────────────────────────────────────────────────────────────────────────────────┐
│                                                                                  │
│   HEAP  ┌────────────────────────────────────────────────────────────────────┐   │
│         │    RUBY HEAP                                                       │   │
│         │ ┌───────────────────┐ ┌───────────────────┐ ┌───────────────────┐  │   │
│         │ │ page              │ │ page              │ │ page              │  │   │
│         │ │                   │ │                   │ │                   │  │   │
│         │ │ ┌─────┐   ┌─────┐ │ │ ┌─────┐   ┌─────┐ │ │ ┌─────┐   ┌─────┐ │  │   │
│         │ │ │slot │   │slot │ │ │ │slot │   │slot │ │ │ │slot │   │slot │ │  │   │
│      ┌──┼─┼─┤     │   │     │ │ │ │     │   │     │ │ │ │     │   │     │ │  │   │
│      │  │ │ └─────┘   └─────┘ │ │ └─────┘   └─────┘ │ │ └─────┘   └─────┘ │  │   │
│      │  │ │                   │ │                   │ │                   │  │   │
│      │  │ │ ┌─────┐   ┌─────┐ │ │ ┌─────┐   ┌─────┐ │ │ ┌─────┐   ┌─────┐ │  │   │
│      │  │ │ │slot │   │slot │ │ │ │slot │   │slot │ │ │ │slot │   │slot │ │  │   │
│      │  │ │ │     │   │     │ │ │ │     │   │     │ │ │ │     │   │     │ │  │   │
│      │  │ └─┴─────┴───┴─────┴─┘ └─┴─────┴───┴─────┴─┘ └─┴─────┴───┴─────┴─┘  │   │
│      │  │                                                                    │   │
│      │  └────────────────────────────────────────────────────────────────────┘   │
│      │                                                                           │
│      │                                                                           │
│      │                                                                           │
│     ┌▼───────────────┐                                                           │
│     │ extra data     │                                                           │
│     │                │                                                           │
│     └────────────────┘                                                           │
│                                                                                  │
│                                                                                  │
└──────────────────────────────────────────────────────────────────────────────────┘

heap 和 page 的源码在 gc.c , 精简后如下

typedef struct rb_heap_struct {
    struct heap_page *free_pages;
    struct list_head pages;  /* 存放的所有pages， 指向了第一个page */
    struct heap_page *sweeping_page; /* 用来迭代每个pages的临时指针 */
    /* 省略 */
    size_t total_pages;      /* 总page数 */
    size_t total_slots;      /* 总slot数 */
} rb_heap_t;

struct heap_page {
    short total_slots;  /* page内总slot数 */
    short free_slots;  /* page内空闲的slot数 */
    /* 省略 */
    struct heap_page *free_next;  /* 下一个可用的page */
    RVALUE *start; /* page内第一个slot地址 */
    RVALUE *freelist; /* page内空闲的slot列表 */
    /* 省略 */
}

Q: 还是不懂，能打个比方吗？

可以用【公司裁员】来比喻 Ruby 垃圾回收。page可以看作公司【办公室】,slot 看作【工位】, Ruby对象看作【员工】，每个【员工】占一个【工位】。如果一个【工位】不够放私人物品，则在外部【储物柜】(总HEAP) 存放额外数据

Q: 如果【工位】(`slot`) 不够了？

裁掉对公司无用的【员工】(Ruby对象), 空出【工位】(slot) 给【新员工】(新Ruby对象)

Q: 如果裁员后【工位】(`slot`) 还是不够？

租更多的【办公室】(向操作系统要更多的 Rubypage)

Q: 什么时候退租【办公室】(`page`),还内存给操作系统？

空闲【工位】(slot) 的空置率最多 65%。如果裁员完空余【工位】(slot) 超过 65% 的，则超出 65% 的部分是可以退租的额度。Ruby 会在退租额度内，选择完全空置的【办公室】(page) 退租。Ruby 管这种完全空置的page叫tomb page, 管还有 Ruby 对象的page叫eden page.

是否还内存给操作系统的源码也在 gc.c, 精简后如下

/* 在确定了裁员名单后，正式裁员前。会调这个gc_marks_finish函数 */
static int
gc_marks_finish(rb_objspace_t *objspace)
{
  /* 省略 */

  size_t total_slots = heap_allocatable_pages * HEAP_PAGE_OBJ_LIMIT + heap->total_slots;
  size_t sweep_slots = total_slots - objspace->marked_slots; /* 总slot数减去保留的slot数，就是当前空闲的slot数 */
  size_t max_free_slots = (size_t)(total_slots * gc_params.heap_free_slots_max_ratio); /* heap_free_slots_max_ratio默认0.65， 总slot数乘以 0.65 就是空闲slot数的上限 */

  /* 省略 */

  /* 【裁员的slot数】 减去 【空置slot数上限】 , 再除以【每个page内单位slot数】这个单位。最后算出的heap_pages_freeable_pages 就是可以还给操作系统的page数量 */
  if (sweep_slots > max_free_slots) {
      heap_pages_freeable_pages = (sweep_slots - max_free_slots) / HEAP_PAGE_OBJ_LIMIT;
  }
  else {
      heap_pages_freeable_pages = 0;
  }
}

/* 裁员完毕后，会调这个 heap_pages_free_unused_pages函数 */
static void
heap_pages_free_unused_pages(rb_objspace_t *objspace)
{
  /* 省略 */

  /* 如果有退租slot数的额度*/
  if (has_pages_in_tomb_heap) {
        for (i = j = 1; j < heap_allocated_pages; i++) {
            struct heap_page *page = heap_pages_sorted[i];

            /* 如果还有退租slot数的额度，并且当前page是完全空置, 则退还page给操作系统 */
            if (page->flags.in_tomb && page->free_slots == page->total_slots) {
                heap_unlink_page(objspace, heap_tomb, page);
                heap_page_free(objspace, page);
            }

            /* 省略 */
        }
   }
}

Q: 怎么判断哪些【员工】(`Ruby对象`) 是无用的，需要被裁？

用标记回收算法，具体见下一节

标记回收算法

Q: 标记回收算法的流程是怎样的？

还是以公司裁员为例子，分两个阶段：

第一个阶段 Mark，标记有用。HR 从最顶层的总裁问起，觉得谁有用？总裁觉得副总裁 A 和副总裁 B 有用。HR 把副总裁 A 和副总裁 B 标记为有用。然后 HR 再去问副总裁 A 和副总裁 B，觉得谁有用？副总裁们觉得经理 C 和经理 D 有用........。以此类推，递归地标记有用和问下去。最后没有被问到的人，没有被标记有用的人，就可以准备裁了
第二个阶段 Sweep，回收工位。找到所有未标记有用的人，裁掉，让出【工位】(slot)。

标记回收的源码也在 gc.c, 精简后如下

/* 标记obj对象有用 */
static void
gc_mark_ptr(rb_objspace_t *objspace, VALUE obj)
{
  /* 省略 */

  if (!gc_mark_set(objspace, obj)) return; /* 如果已经标记过，则return；否则标记成功，接着执行 */

  /* 省略 */

  gc_grey(objspace, obj); /* 把obj推入栈中，方便之后问它引用了哪些子对象, 觉得哪些子对象有用 */

  /* 省略 */
}

/* 推入栈中 */
static void
gc_grey(rb_objspace_t *objspace, VALUE obj)
{
  /* 省略 */

  push_mark_stack(&objspace->mark_stack, obj);
}

/* 之后从栈中取出对象 */
static inline int
gc_mark_stacked_objects(rb_objspace_t *objspace, int incremental, size_t count)
{
  /* 省略 */

  while (pop_mark_stack(mstack, &obj)) {
     /* 省略 */

     /* 从栈中取出obj，再递归的标记obj引用了的子对象。gc_mark_children之后又会递归调用上面的 gc_mark_ptr 函数标记子对象*/
     gc_mark_children(objspace, obj);
  }

  /* 省略 */
}


/* 标记完后，对每个page调 gc_page_sweep 函数进行回收检查 */
static inline void
gc_sweep_page(rb_objspace_t *objspace, rb_size_pool_t *size_pool, rb_heap_t *heap, struct gc_sweep_context *ctx)
{
  /* 省略 */

  /* page内第一个slot的地址，存在p里 */
  p = sweep_page->start;

  /* page内用一个位图数组mark_bits来标记每个slot是否有用 */
  bits = sweep_page->mark_bits;

  /* 循环检查每个slot对应的位图 */
  for (i=0; i < HEAP_PAGE_BITMAP_LIMIT; i++) {
    bitset = ~bits[i];  /* 把位图取反，就是没有被标记的slot */
    if (bitset) {

        /* 如果取反的位图数组有未标记的slot，调gc_sweep_plane回收 slot, 函数定义见下方 */
        gc_sweep_plane(objspace, heap, (uintptr_t)p, bitset, ctx);
    }
    p += BITS_BITLENGTH;
  }

  /* 省略 */
}

static inline void
gc_sweep_plane(rb_objspace_t *objspace, rb_heap_t *heap, uintptr_t p, bits_t bitset, struct gc_sweep_context *ctx)
{
   /* 省略 */

   do {
        VALUE vp = (VALUE)p;

        /* 取反位图的右边最低位是1，说能原位图右边最低位是0，说明该位对应的slot没被标记，可以被回收 */
        if (bitset & 1) {
          /* 省略 */

          obj_free(objspace, vp) /* 删除slot上的变量，清空slot */

          /* 省略 */
        }

        /* 循环找下一个slot，取反位图bitset右移到下一位 */
        p += slot_size;
        bitset >>= slot_bits;
  }while (bitset);
}

Q: 每次裁员要从头问一遍所有人，有什么办法优化吗？

用 Ruby 2.1 新增的分代回收算法，具体见下一节

分代回收

Q: 分代回收算法的流程是怎样的？

还是以公司裁员打比方。分为【大裁员】(Major/Full) 和【小裁员】(Minor)。

【大裁员】(Major/Full) 还是和之前一样，问一遍所有人。

【小裁员】(Minor) 会默认一些【员工】(Ruby对象) 有用，跳过对这些【员工】(Ruby对象) 的标记和询问。

Q: 哪些【员工】(`Ruby对象`) 会默认有用？

被标记过 3 次的，即躲过三次裁员的【老员工】(Ruby 管这种对象叫old object) 默认有用。同时，【老员工】(old object) 觉得有用的子员工，也自动变为【老员工】, 形成了一个老员工帮。

例如，某个员工之前躲过了两次裁员。当第三次裁员时，HR 询问该员工觉得谁有用时，发现算上目前这次，该员工已经躲过三次裁员了，就把该员工标记为【老员工】(old object)。该员工觉得员工 A 和员工 B 有用，则 HR 把员工 A 和员工 B 也标记为【老员工】(old object)。以此类推，员工 A 和员工 B 又觉得员工 C 和员工 D 有用，则 HR 把员工 C 和员工 D 也标记为【老员工】.....

当第四次【小裁员】(minor) 时，HR 默认这帮老员工有用，跳过对这些老员工的标记和询问

Q: 上面的例子，如果在第三次裁员后，第四次裁员前，新招了一个新员工 E，某个【老员工】(`old object`) 觉得新员工 E 有用。但 HR 跳过了老员工的询问，不知道员工 E 有用，第四次裁员时误裁掉员工 E。怎么办？

【老员工】(old object) 主动给 HR 说，下次裁员时，强制询问我谁有用。HR 给【老员工】(old object) 标记下次【强制询问】的标签。等下次裁员结束，保住了员工 E 后，就可以清除【强制询问】的标签。

Ruby 里这种主动标记强制询问的方法叫 write barrier。Ruby 管这种主动标记强制询问的对象叫 write barrier protected object

Q: 所有的员工都会这么主动帮新员工吗？

很可惜，不会，因为要兼容第三方 c 扩展库。Ruby 给新函数加上了write barrier 行为，但第三方 c 扩展使用的可能是不带write barrier的老函数

Q: 那怎么办？

HR 把这些不主动的员工标记为【老油条】（Ruby 里叫 write barrier unprotected object或者shady）。就算【老油条】混成了【老员工】，HR 每次裁员时，还是要强制标记和询问【老油条】(write barrier unprotected object/shady)

分代回收的源码还是在 gc.c , 精简后如下

/* 标记开始函数 */
static void
gc_marks_start(rb_objspace_t *objspace, int full_mark)
{
  /* 是否大裁员 Major/Full */
  if (full_mark) {
    /* 大裁员 */
    objspace->flags.during_minor_gc = FALSE;


    for (int i = 0; i < SIZE_POOL_COUNT; i++) {
        /* 清空之前标记的【是否有用】【是否强制询问】【是否老员工】等标志 */
        rgengc_mark_and_rememberset_clear(objspace, SIZE_POOL_EDEN_HEAP(&size_pools[i]));
    }
  }
  else {
    /* 小裁员 */
    objspace->flags.during_minor_gc = TRUE;

    for (int i = 0; i < SIZE_POOL_COUNT; i++) {

       /* 先把需要【强制询问】或【老油条】的对象标记询问 */
       rgengc_rememberset_mark(objspace, SIZE_POOL_EDEN_HEAP(&size_pools[i]));
    }
  }

  /* 从顶层对象开始标记询问，gc_mark_roots会调用上一节源码里的 gc_mark_ptr */
  gc_mark_roots(objspace, NULL);
}

/* 清空各种标记位图数组 */
static void
rgengc_mark_and_rememberset_clear(rb_objspace_t *objspace, rb_heap_t *heap)
{
    struct heap_page *page = 0;

    /* mark_bits是【是否有用】的位图数组, uncollectible_bits是【是否老员工/old object】的位图数组, marking_bits是时是否【强制询问】的位图数组; pinned_bits先忽略，讲到碎片整理一节时再说 */
    list_for_each(&heap->pages, page, page_node) {
    memset(&page->mark_bits[0],       0, HEAP_PAGE_BITMAP_SIZE);
    memset(&page->uncollectible_bits[0], 0, HEAP_PAGE_BITMAP_SIZE);
        memset(&page->marking_bits[0],    0, HEAP_PAGE_BITMAP_SIZE);
        memset(&page->pinned_bits[0],     0, HEAP_PAGE_BITMAP_SIZE);

        /* 省略 */
    }
}

/* 标记【强制询问】或【老油条】对象 */
static void
rgengc_rememberset_mark(rb_objspace_t *objspace, rb_heap_t *heap)
{

        /* 省略 */

        /循环检查每个page/
        list_for_each(&heap->pages, page, page_node) { 
                if (page->flags.has_remembered_objects | page->flags.has_uncollectible_shady_objects) { 
                        RVALUE *p = page->start;

                        /* marking_bits 是【强制询问】的位图数组，uncollectible_bits是【老员工】的位图数组，wb_unprotected_bits 是【老油条】的位图数组 */
                        bits_t *marking_bits = page->marking_bits;
                        bits_t *uncollectible_bits = page->uncollectible_bits;
                        bits_t *wb_unprotected_bits = page->wb_unprotected_bits;

                        for (j=0; j<HEAP_PAGE_BITMAP_LIMIT; j++) { 
                                /* bits代表(【强制询问】或者（【老员工】并且【老油条】）) */
                                bits[j] = marking_bits[j] | (uncollectible_bits[j] & wb_unprotected_bits[j]);

                                /* 清空【强制询问】位图数组 */
                                marking_bits[j] = 0;
                        } 

                        /* 省略 */


                        for (j=1; j < HEAP_PAGE_BITMAP_LIMIT; j++) { 
                                bitset = bits[j];
                                /* 检查每个bits位图数组 */
                                rgengc_rememberset_mark_plane(objspace, (uintptr_t)p, bitset);
                                p += BITS_BITLENGTH;
                        } 
                } 
        } 
}

/* 询问有【强制询问】或【老油条】标签的对象 */
static inline void
rgengc_rememberset_mark_plane(rb_objspace_t *objspace, uintptr_t p, bits_t bitset)
{
    if (bitset) {
        do {
            if (bitset & 1) {
                VALUE obj = (VALUE)p;


                /* 标记询问有用的子对象，gc_mark_children 在上一节的源码里也出现过 */
                gc_mark_children(objspace, obj);
            }
            p += sizeof(RVALUE);
            bitset >>= 1;
        } while (bitset);
    }
}

/* 标记obj对象有用 */
static void
gc_mark_ptr(rb_objspace_t *objspace, VALUE obj)
{
  /* 省略 */

  /* 检查是obj的父标对象是谁，即是谁觉得obj有用 */
  rgengc_check_relation(objspace, obj);

  if (!gc_mark_set(objspace, obj)) return; 

  /* 省略 */

  gc_grey(objspace, obj); 

  /* 省略 */
}

/* 检查obj的父标对象是谁，是谁觉得obj有用 */
static void
rgengc_check_relation(rb_objspace_t *objspace, VALUE obj)
{       
        const VALUE old_parent = objspace->rgengc.parent_object;

        /* 如果父标记对象是【老员工】old object */
        if (old_parent) {

                /* 省略 */

                /* 把当前对象obj也标记为【老员工】old object */
                RVALUE_AGE_SET_CANDIDATE(objspace, obj);
        }

        /* 省略 */
} 

/* 标记回收结束时，对page调用gc_setup_mark_bits函数 */
static void
gc_setup_mark_bits(struct heap_page *page)
{
    /* copy oldgen bitmap to mark bitmap */
    /* 把【老员工】uncollectible_bits位图数组复制给【是否有用】mark_bits位图数组，即老员工 old object默认有用 */
    memcpy(&page->mark_bits[0], &page->uncollectible_bits[0], HEAP_PAGE_BITMAP_SIZE);
}

/* 变量a引用了变量b，觉得变量b有用时，触发writebarrier, 把变量a标记为【强制询问】 */
void
rb_gc_writebarrier(VALUE a, VALUE b)
{
    /* 省略 */

    if (!RVALUE_OLD_P(a) || RVALUE_OLD_P(b)) {
        // do nothing
    }
    else {
        /* 如果a是【老员工】(old object)，b不是【老员工】(old object), 则把a标记为【强制询问】 */
        gc_writebarrier_generational(a, b, objspace);
    }

    /* 省略 */
}


/* 把变量a标记为【强制询问】 */
static void
gc_writebarrier_generational(VALUE a, VALUE b, rb_objspace_t *objspace)
{
  /* 省略 */

  rgengc_remember(objspace, a);

  /* 省略 */
}

/* 把obj标记为【强制询问】 */
static int
rgengc_remember(rb_objspace_t *objspace, VALUE obj)
{
  /* 省略 */

  return rgengc_remembersetbits_set(objspace, obj);
}

/* 把obj标记为【强制询问】 */
static int
rgengc_remembersetbits_set(rb_objspace_t *objspace, VALUE obj)
{
    struct heap_page *page = GET_HEAP_PAGE(obj);
    bits_t *bits = &page->marking_bits[0]; /* 【强制询问】的位图数组是page内的 marking_bits */

   /* 省略 */

   page->flags.has_remembered_objects = TRUE;
   MARK_IN_BITMAP(bits, obj); /* 把obj对应的marking_bits位置标为1 */
   return TRUE;
}

Q: 【小裁员】(`minor`) 跳过【老员工】(`old object`) 减少了标记的时间。但【大裁员】(`major/full`) 依然要问一遍所有人，有什么办法优化【大裁员】(`major/full`) 吗？

用 Ruby 2.2 新加的增量回收算法，具体见下一节

增量回收

Q: 增量回收算法是怎么优化【大裁员】(`major/full`) 流程的？

【大裁员】(major/full) 需要问一遍所有人，这个客观事实是改不了的。增量回收算法的优化思路是：通过增量标记询问，尽量减少对员工们正常干活的阻塞。

在 Ruby 2.2 增量回收算法出现前。【大裁员】(major/full) 时，员工们都必须停下手头的工作，等裁员结果出来，才能继续工作。

Ruby 2.2 增量回收算法出来后。除了原先【已标记】(Ruby 叫black object) 和【未标记】(Ruby 叫white object) 这两种状态，HR 新增了一种【询问中】(Ruby 叫grey object) 状态。

例如，第一天 HR 把总裁标记为【询问中】(grey object)，总裁觉得副总裁 A 和副总裁 B 有用。HR 把副总裁 A 和副总裁 B 标记为【询问中】，把总裁标记为【已标记】(black object)。就结束了第一天的标记，员工可以接着干活。第二天，HR 在询问副总裁 A 和副总裁 B。副总裁们觉得经理 C 和经理 D 有用，HR 把经理 C 和经理 D 标记为【询问中】(grey object), 把副总裁们标记为【已标记】(black object)。结束了第二天的标记，员工可以接着干活。以此循环递归，每天增量的询问一些【询问中】的员工，直到没有【询问中】(grey object) 的员工。只剩【已标记】和【未标记】的员工。

Q: 和分代回收时同样的问题：如果某个员工 A 被标记为【已标记】(`black object`), 然后新招了一个员工 B，员工 A 觉得员工 B 有用。但因为 HR 不会再询问员工 A 了，不知道员工 B 有用，导致员工 B 被误裁，怎么办？

跟分代回收类似的解决方案，writebarrier。员工 A 主动把跟 HR 说把员工 B 从【未标记】(white object) 改为【询问中】(grey object)。实际上分代回收的【强制询问】和增量回收的【询问中】用的是同一个标记，同一个位图数组 marking_bits，因为两者的作用一致，都是让 HR 下次询问自己一次。

Q: 所有的员工都会主动帮新员工吗？

很可惜，不会，原因和分代回收时一样，为了兼容第三方 c 扩展库。必须用别的办法对付【老油条】(writebarrier unprotected object)

Q：那怎么办？

HR 在【大裁员】(major/full) 最终标记结束前，会最后再问一遍所有的【老油条】(writebarrier unprotected object)，以防漏掉了哪个有用的员工。

增量回收的源码还是在 gc.c

/* 标记了有用 mark_bits, 没标记强询问 marking_bits 的就是black object*/
static inline int
RVALUE_BLACK_P(VALUE obj)
{
    return RVALUE_MARKED(obj) && !RVALUE_MARKING(obj);
}

#if 0
/* 标记了有用 mark_bits, 同时标记了下次强制询问 marking_bits的就是grey object */
static inline int
RVALUE_GREY_P(VALUE obj)
{
    return RVALUE_MARKED(obj) && RVALUE_MARKING(obj);
}
#endif

/* 还没被标记有用mark_bits的就是white object */
static inline int
RVALUE_WHITE_P(VALUE obj)
{
    return RVALUE_MARKED(obj) == FALSE;
}

/* 增量回收中，a觉得b有用的writebarrier函数 */
static void
gc_writebarrier_incremental(VALUE a, VALUE b, rb_objspace_t *objspace)
{
    gc_report(2, objspace, "gc_writebarrier_incremental: [LG] %p -> %s\n", (void *)a, obj_info(b));

    if (RVALUE_BLACK_P(a)) {
        if (RVALUE_WHITE_P(b)) {
            if (!RVALUE_WB_UNPROTECTED(a)) {
                /* 变量a是black，变量b是white时，把变量b标记为grey */
                gc_report(2, objspace, "gc_writebarrier_incremental: [IN] %p -> %s\n", (void *)a, obj_info(b));
                gc_mark_from(objspace, b, a);
            }
        }
        else if (RVALUE_OLD_P(a) && !RVALUE_OLD_P(b)) {
            if (!RVALUE_WB_UNPROTECTED(b)) {
                /* 变量a是老对象，变量b是新对象时，把变量b标记为老对象 */
                gc_report(1, objspace, "gc_writebarrier_incremental: [GN] %p -> %s\n", (void *)a, obj_info(b));
                RVALUE_AGE_SET_OLD(objspace, b);

                if (RVALUE_BLACK_P(b)) {
                    /* 如果变量b是black时，改为grey，下次强制询问 */
                    gc_grey(objspace, b);
                }
            }
            else {
                gc_report(1, objspace, "gc_writebarrier_incremental: [LL] %p -> %s\n", (void *)a, obj_info(b));
                /* 变量b是【老油条】writebarrier unprotected, 标记b为【老员工】old object */
                gc_remember_unprotected(objspace, b);
            }
        }

        /* 省略 */
    }
}

/* 标记结束前调用的函数 */
static int
gc_marks_finish(rb_objspace_t *objspace)
{
  #if GC_ENABLE_INCREMENTAL_MARK
  /* 省略 */

  /* 增量标记结束前，再询问一遍【老油条】writebarrier unprotected object, 以防漏掉有用变量 */
  /* gc_marks_wb_unprotected_objects 函数会再询问一遍所有writebarrier unprotected object */
  for (int i = 0; i < SIZE_POOL_COUNT; i++) {
    gc_marks_wb_unprotected_objects(objspace, SIZE_POOL_EDEN_HEAP(&size_pools[i]));
  }
  #endif
}

Q: 所以一个【员工】(`Ruby对象`) 总共有哪些标记？

是否有用 (mark_bits), 是否老员工 (uncollectible_bits), 是否老油条 (wb_unprotected_bits), 是否下次强制询问 (marking_bits), 是否钉子户 (pinned_bits)

Q: 裁员完后，不换一下工位，让员工间坐得更近，空出更多的【办公室】(`page`) 吗？

可以，Ruby 2.7 加了碎片整理算法，详情见下一节

碎片整理

Q: 碎片整理算法的流程是怎样的？

以公司裁员打比方，必须先进行一次【大裁员】(major/full) 后，再执行如下两个阶段：

第一阶段，转移工位。两个 HR，一个负责在左边，从左往右找空出的【工位】(slot), 另一个负责在右边，从右往左找【员工】(Ruby对象), 各自找到合适的【工位】(slot) 和【员工】(Ruby对象) 后，把员工转移到新工位，并在原工位上留下新工位的字条。以此循环，直到找不到合适的工位或员工，两个 HR 碰到了一起。
第二阶段，更新引用。通知所有员工，根据原工位留的字条，记一下对应员工的新工位。

具体例子见下图

6个工位，4个员工，A和B记得C和D在5和6号工位
                     ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─        
                        Before Compaction   │       
                     └ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─        
               ┌─────┬─────┬─────┬─────┬─────┬─────┐
 Slot Index    │  1  │  2  │  3  │  4  │  5  │  6  │
               ├─────┼─────┼─────┼─────┼─────┼─────┤
Slot Contents  │  A  │  B  │Empty│Empty│  C  │  D  │
               │     │     │     │     │     │     │
               └─────┴─────┴─────┴─────┴─────┴─────┘
                  │     │                 ▲     ▲   
                  │     │                 │     │   
                  └─────┼─────────────────┘     │   
                        └───────────────────────┘

第一阶段，C和D转移工位到3和4后，在原工位留下字条
                     ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─        
                         After Compaction   │       
                     └ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─        
               ┌─────┬─────┬─────┬─────┬─────┬─────┐
 Slot Index    │  1  │  2  │  3  │  4  │  5  │  6  │
               ├─────┼─────┼─────┼─────┼─────┼─────┤
Slot Contents  │  A  │  B  │  D  │  C  │MOVED│MOVED│
               │     │     │     │     │TO 4 │TO 3 │
               └─────┴─────┴─────┴─────┴─────┴─────┘
                  │     │                 ▲     ▲   
                  │     │                 │     │   
                  └─────┼─────────────────┘     │   
                        └───────────────────────┘

第二阶段，员工A和B根据字条，更新一下记的员工C和D的工位位置
                     ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─        
                        After Ref Updates   │       
                     └ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─        
               ┌─────┬─────┬─────┬─────┬─────┬─────┐
 Slot Index    │  1  │  2  │  3  │  4  │  5  │  6  │
               ├─────┼─────┼─────┼─────┼─────┼─────┤
Slot Contents  │  A  │  B  │  D  │  C  │MOVED│MOVED│
               │     │     │     │     │TO 4 │TO 3 │
               └─────┴─────┴─────┴─────┴─────┴─────┘
                  │     │     ▲     ▲               
                  │     │     │     │               
                  └─────┼─────┼─────┘               
                        └─────┘

Q: 所有员工都会乖乖换工位吗？

很可惜，不会，原因和分代回收一样，为了兼容第三方 c 扩展库。碎片整理时会跳过这些【钉子户】(Ruby 内叫pinned object)

由于原理很简单，更多的难点是在为了升级第三方 c 扩展库，而提供的rb_gc_location, rb_data_type_struct中的dcompact回调函数指针等，本节省略源码解析

Q: 碎片整理除了空出更多的【办公室】(`page`), 还有别的好处吗？

有，根据局部性原理，能优化读取速度。

局部性原理

Q: 什么是局部性原理？

cpu 读取内存数据时，如果是读取相邻的顺序数据，更有机会被 L1，L2，L3 缓存命中，提高性能。

Q: 除了碎片整理，Ruby 垃圾回收中还有哪些优化用到了局部性原理吗？

Ruby 3.1 新加了 Variable Width Allocation, 但跟 jit 一样默认是关闭状态的实验特性。

原先一个【工位】(slot) 只有 40 字节，额外数据需要存储在外部 heap。Variable Width Allocation 的原理是，把【工位】(slot) 扩大到 40 字节，80 字节，160 字节，320 字节四种。虽然可能造成一定的空间浪费，但根据局部性原理，提高了性能。

详情见 Variable Width Allocation 的 redmine

https://bugs.ruby-lang.org/issues/18045

https://bugs.ruby-lang.org/issues/18239

Q: 除了垃圾回收，Ruby 中还有哪些优化用到了局部性原理吗？

Ruby 2.4 中用局部性原理优化了 Hash 的实现，详情见下面文章中 Hash changes 的科普 https://blog.heroku.com/ruby-2-4-features-hashes-integers-rounding

10 个赞

1 楼已删除

ccmywish #2 2022年04月26日

这个 ASCII 图是用什么画的啊？

zhuoerri #3 2022年04月26日

对

ccmywish 回复

ASCII 图用的 https://asciiflow.com/#/

lehug #4 2022年04月26日

深入理解 Java 虚拟机：JVM 高级特性与最佳实践（第 3 版）这个书讲 java 的，一些原理类似

1 个赞

kevinyu #5 2023年02月23日

学习了

johnrosep #6 2024年01月05日

This convertitore video di Youtube is incredibly efficient and user-friendly. It helps me effortlessly convert my favorite videos into different formats for offline enjoyment.

NellyAurora #7 2024年01月09日

The heardle is an online game that you can play right on your computer without downloading. You can experience it with family and friends.

movieclub #8 2024年02月24日

Czy jesteś fanem sportu, który nie może przegapić żadnego meczu czy zawodów na żywo? Odkryj, co MovieClub ma Ci do zaoferowania w 2024 roku. Nasz serwis to Twoja brama do świata sportowych emocji. MovieClub wyróżnia się na rynku dzięki swojej szerokiej ofercie transmisji na żywo, obejmującej mecze piłki nożnej, skoki narciarskie, tenis, siatkówkę i wiele innych dyscyplin. Nie wiesz kiedy Twój ulubiony zespół gra mecz? Nie wiesz gdzie obejrzeć dzisiaj mecze za darmo? W MovieClub odpowiemy na te pytania i wiele więcej. Odkrywaj sport razem z nami, tak jak lubisz!

Omegle #9 2024年03月18日

nice post

nikhil #10 2024年03月21日

Thanks! we are thankful for you to keep alive ruby on rails thanks from RailsCarma

mariaran #11 2024年06月04日

@drift hunters 想了解 Ruby 垃圾回收机制和 Ruby 内部实现更详尽的阐述 .

需要登录后方可回复, 如果你还没有账号请注册新账号

Ruby 垃圾回收原理浅析

Ruby 垃圾回收原理浅析

前言

Ruby 内存模型

Q: Ruby 对象在内存里是怎么存储管理的？

Q: 还是不懂，能打个比方吗？

Q: 如果【工位】(slot) 不够了？

Q: 如果裁员后【工位】(slot) 还是不够？

Q: 什么时候退租【办公室】(page),还内存给操作系统？

Q: 怎么判断哪些【员工】(Ruby对象) 是无用的，需要被裁？

标记回收算法

Q: 标记回收算法的流程是怎样的？

Q: 每次裁员要从头问一遍所有人，有什么办法优化吗？

分代回收

Q: 分代回收算法的流程是怎样的？

Q: 哪些【员工】(Ruby对象) 会默认有用？

Q: 上面的例子，如果在第三次裁员后，第四次裁员前，新招了一个新员工 E，某个【老员工】(old object) 觉得新员工 E 有用。但 HR 跳过了老员工的询问，不知道员工 E 有用，第四次裁员时误裁掉员工 E。怎么办？

Q: 所有的员工都会这么主动帮新员工吗？

Q: 那怎么办？

Q: 【小裁员】(minor) 跳过【老员工】(old object) 减少了标记的时间。但【大裁员】(major/full) 依然要问一遍所有人，有什么办法优化【大裁员】(major/full) 吗？

增量回收

Q: 增量回收算法是怎么优化【大裁员】(major/full) 流程的？

Q: 和分代回收时同样的问题：如果某个员工 A 被标记为【已标记】(black object), 然后新招了一个员工 B，员工 A 觉得员工 B 有用。但因为 HR 不会再询问员工 A 了，不知道员工 B 有用，导致员工 B 被误裁，怎么办？

Q: 所有的员工都会主动帮新员工吗？

Q：那怎么办？

Q: 所以一个【员工】(Ruby对象) 总共有哪些标记？

Q: 裁员完后，不换一下工位，让员工间坐得更近，空出更多的【办公室】(page) 吗？

碎片整理

Q: 碎片整理算法的流程是怎样的？

Q: 所有员工都会乖乖换工位吗？

Q: 碎片整理除了空出更多的【办公室】(page), 还有别的好处吗？

局部性原理

Q: 什么是局部性原理？

Q: 除了碎片整理，Ruby 垃圾回收中还有哪些优化用到了局部性原理吗？

Q: 除了垃圾回收，Ruby 中还有哪些优化用到了局部性原理吗？

Q: 如果【工位】(`slot`) 不够了？

Q: 如果裁员后【工位】(`slot`) 还是不够？

Q: 什么时候退租【办公室】(`page`),还内存给操作系统？

Q: 怎么判断哪些【员工】(`Ruby对象`) 是无用的，需要被裁？

Q: 哪些【员工】(`Ruby对象`) 会默认有用？

Q: 上面的例子，如果在第三次裁员后，第四次裁员前，新招了一个新员工 E，某个【老员工】(`old object`) 觉得新员工 E 有用。但 HR 跳过了老员工的询问，不知道员工 E 有用，第四次裁员时误裁掉员工 E。怎么办？

Q: 【小裁员】(`minor`) 跳过【老员工】(`old object`) 减少了标记的时间。但【大裁员】(`major/full`) 依然要问一遍所有人，有什么办法优化【大裁员】(`major/full`) 吗？

Q: 增量回收算法是怎么优化【大裁员】(`major/full`) 流程的？

Q: 和分代回收时同样的问题：如果某个员工 A 被标记为【已标记】(`black object`), 然后新招了一个员工 B，员工 A 觉得员工 B 有用。但因为 HR 不会再询问员工 A 了，不知道员工 B 有用，导致员工 B 被误裁，怎么办？

Q: 所以一个【员工】(`Ruby对象`) 总共有哪些标记？

Q: 裁员完后，不换一下工位，让员工间坐得更近，空出更多的【办公室】(`page`) 吗？

Q: 碎片整理除了空出更多的【办公室】(`page`), 还有别的好处吗？