CoreCLR源码探索(四) GC内存收集器的内部实现 分析篇（三）

gc_heap::plan_generation_start函数的代码如下:
根据当前的generaion_allocation_pointer(alloc_ptr)计划代边界

void gc_heap::plan_generation_start (generation* gen, generation* consing_gen, uint8_t* next_plug_to_allocate)
{
    // 特殊处理
    // 如果某些pinned plug很大(大于demotion_plug_len_th(6MB))，把它们出队防止降代
#ifdef BIT64
    // We should never demote big plugs to gen0.
    if (gen == youngest_generation)
    {
        heap_segment* seg = ephemeral_heap_segment;
        size_t mark_stack_large_bos = mark_stack_bos;
        size_t large_plug_pos = 0;
        while (mark_stack_large_bos < mark_stack_tos)
        {
            if (mark_stack_array[mark_stack_large_bos].len > demotion_plug_len_th)
            {
                while (mark_stack_bos <= mark_stack_large_bos)
                {
                    size_t entry = deque_pinned_plug();
                    size_t len = pinned_len (pinned_plug_of (entry));
                    uint8_t* plug = pinned_plug (pinned_plug_of(entry));
                    if (len > demotion_plug_len_th)
                    {
                        dprintf (2, ("ps(%d): S %Ix (%Id)(%Ix)", gen->gen_num, plug, len, (plug+len)));
                    }
                    pinned_len (pinned_plug_of (entry)) = plug - generation_allocation_pointer (consing_gen);
                    assert(mark_stack_array[entry].len == 0 ||
                            mark_stack_array[entry].len >= Align(min_obj_size));
                    generation_allocation_pointer (consing_gen) = plug + len;
                    generation_allocation_limit (consing_gen) = heap_segment_plan_allocated (seg);
                    set_allocator_next_pin (consing_gen);
                }
            }

            mark_stack_large_bos++;
        }
    }
#endif // BIT64

    // 在当前consing_gen的generation_allocation_ptr创建一个最小的对象
    // 以这个对象的开始地址作为计划代边界
    // 这里的处理是保证代与代之间最少有一个对象(初始化代的时候也会这样保证)
    generation_plan_allocation_start (gen) =
        allocate_in_condemned_generations (consing_gen, Align (min_obj_size), -1);
    
    // 压缩后会根据这个大小把这里的空间变为一个free object
    generation_plan_allocation_start_size (gen) = Align (min_obj_size);

    // 如果接下来的空间很小(小于min_obj_size)，则把接下来的空间也加到上面的初始对象里
    size_t allocation_left = (size_t)(generation_allocation_limit (consing_gen) - generation_allocation_pointer (consing_gen));
    if (next_plug_to_allocate)
    {
        size_t dist_to_next_plug = (size_t)(next_plug_to_allocate - generation_allocation_pointer (consing_gen));
        if (allocation_left > dist_to_next_plug)
        {
            allocation_left = dist_to_next_plug;
        }
    }
    if (allocation_left < Align (min_obj_size))
    {
        generation_plan_allocation_start_size (gen) += allocation_left;
        generation_allocation_pointer (consing_gen) += allocation_left;
    }

    dprintf (1, ("plan alloc gen%d(%Ix) start at %Ix (ptr: %Ix, limit: %Ix, next: %Ix)", gen->gen_num, 
        generation_plan_allocation_start (gen),
        generation_plan_allocation_start_size (gen),
        generation_allocation_pointer (consing_gen), generation_allocation_limit (consing_gen),
        next_plug_to_allocate));
}

gc_heap::plan_generation_starts函数的代码如下:
这个函数会在模拟压缩所有对象后调用，用于计划剩余的代边界，如果启用了升代这里会计划gen 0的边界

void gc_heap::plan_generation_starts (generation*& consing_gen)
{
    //make sure that every generation has a planned allocation start
    int  gen_number = settings.condemned_generation;
    while (gen_number >= 0)
    {
        // 因为不能把gen 1和gen 0的边界放到其他segment中
        // 这里需要确保consing_gen的allocation segment是ephemeral heap segment
        if (gen_number < max_generation)
        {
            consing_gen = ensure_ephemeral_heap_segment (consing_gen);
        }
        // 如果这个代的边界尚未计划，则执行计划
        generation* gen = generation_of (gen_number);
        if (0 == generation_plan_allocation_start (gen))
        {
            plan_generation_start (gen, consing_gen, 0);
            assert (generation_plan_allocation_start (gen));
        }
        gen_number--;
    }
    // 设置ephemeral heap segment的计划已分配大小
    // now we know the planned allocation size
    heap_segment_plan_allocated (ephemeral_heap_segment) =
        generation_allocation_pointer (consing_gen);
}

gc_heap::generation_fragmentation函数的代码如下:

size_t gc_heap::generation_fragmentation (generation* gen,
                                          generation* consing_gen,
                                          uint8_t* end)
{
    size_t frag;
    // 判断是否所有对象都压缩到了ephemeral heap segment之前
    uint8_t* alloc = generation_allocation_pointer (consing_gen);
    // If the allocation pointer has reached the ephemeral segment
    // fine, otherwise the whole ephemeral segment is considered
    // fragmentation
    if (in_range_for_segment (alloc, ephemeral_heap_segment))
        {
            // 原allocated - 模拟压缩的结尾allocation_pointer
            if (alloc <= heap_segment_allocated(ephemeral_heap_segment))
                frag = end - alloc;
            else
            {
                // 无一个对象存活，已经把allocated设到开始地址
                // case when no survivors, allocated set to beginning
                frag = 0;
            }
            dprintf (3, ("ephemeral frag: %Id", frag));
        }
    else
        // 所有对象都压缩到了ephemeral heap segment之前
        // 添加整个范围到frag
        frag = (heap_segment_allocated (ephemeral_heap_segment) -
                heap_segment_mem (ephemeral_heap_segment));
    heap_segment* seg = heap_segment_rw (generation_start_segment (gen));

    PREFIX_ASSUME(seg != NULL);

    // 添加其他segment的原allocated - 计划allcated
    while (seg != ephemeral_heap_segment)
    {
        frag += (heap_segment_allocated (seg) -
                 heap_segment_plan_allocated (seg));
        dprintf (3, ("seg: %Ix, frag: %Id", (size_t)seg,
                     (heap_segment_allocated (seg) -
                      heap_segment_plan_allocated (seg))));

        seg = heap_segment_next_rw (seg);
        assert (seg);
    }
    // 添加所有pinned plug前面的空余空间
    dprintf (3, ("frag: %Id discounting pinned plugs", frag));
    //add the length of the dequeued plug free space
    size_t bos = 0;
    while (bos < mark_stack_bos)
    {
        frag += (pinned_len (pinned_plug_of (bos)));
        bos++;
    }

    return frag;
}

gc_heap::decide_on_compacting函数的代码如下:

BOOL gc_heap::decide_on_compacting (int condemned_gen_number,
                                    size_t fragmentation,
                                    BOOL& should_expand)
{
    BOOL should_compact = FALSE;
    should_expand = FALSE;
    generation*   gen = generation_of (condemned_gen_number);
    dynamic_data* dd = dynamic_data_of (condemned_gen_number);
    size_t gen_sizes     = generation_sizes(gen);
    // 碎片空间大小 / 收集代的大小(包括更年轻的代)
    float  fragmentation_burden = ( ((0 == fragmentation) || (0 == gen_sizes)) ? (0.0f) :
                                    (float (fragmentation) / gen_sizes) );

    dprintf (GTC_LOG, ("fragmentation: %Id (%d%%)", fragmentation, (int)(fragmentation_burden * 100.0)));

    // 由Stress GC决定是否压缩
#ifdef STRESS_HEAP
    // for pure GC stress runs we need compaction, for GC stress "mix"
    // we need to ensure a better mix of compacting and sweeping collections
    if (GCStress<cfg_any>::IsEnabled() && !settings.concurrent
        && !g_pConfig->IsGCStressMix())
        should_compact = TRUE;

     // 由Stress GC决定是否压缩
     // 如果压缩次数不够清扫次数的十分之一则开启压缩
#ifdef GC_STATS
    // in GC stress "mix" mode, for stress induced collections make sure we 
    // keep sweeps and compactions relatively balanced. do not (yet) force sweeps
    // against the GC's determination, as it may lead to premature OOMs.
    if (g_pConfig->IsGCStressMix() && settings.stress_induced)
    {
        int compactions = g_GCStatistics.cntCompactFGC+g_GCStatistics.cntCompactNGC;
        int sweeps = g_GCStatistics.cntFGC + g_GCStatistics.cntNGC - compactions;
        if (compactions < sweeps / 10)
        {
            should_compact = TRUE;
        }
    }
#endif // GC_STATS
#endif //STRESS_HEAP

    // 判断是否强制压缩
    if (g_pConfig->GetGCForceCompact())
        should_compact = TRUE;

    // 是否因为OOM(Out Of Memory)导致的GC，如果是则开启压缩
    if ((condemned_gen_number == max_generation) && last_gc_before_oom)
    {
        should_compact = TRUE;
        last_gc_before_oom = FALSE;
        get_gc_data_per_heap()->set_mechanism (gc_heap_compact, compact_last_gc);
    }

    // gc原因中有压缩
    if (settings.reason == reason_induced_compacting)
    {
        dprintf (2, ("induced compacting GC"));
        should_compact = TRUE;
        get_gc_data_per_heap()->set_mechanism (gc_heap_compact, compact_induced_compacting);
    }

    dprintf (2, ("Fragmentation: %d Fragmentation burden %d%%",
                fragmentation, (int) (100*fragmentation_burden)));

    // 如果ephemeral heap segment的空间较少则开启压缩
    if (!should_compact)
    {
        if (dt_low_ephemeral_space_p (tuning_deciding_compaction))
        {
            dprintf(GTC_LOG, ("compacting due to low ephemeral"));
            should_compact = TRUE;
            get_gc_data_per_heap()->set_mechanism (gc_heap_compact, compact_low_ephemeral);
        }
    }

    // 如果ephemeral heap segment的空间较少，并且当前不是Full GC还需要使用新的ephemeral heap segment
    if (should_compact)
    {
        if ((condemned_gen_number >= (max_generation - 1)))
        {
            if (dt_low_ephemeral_space_p (tuning_deciding_expansion))
            {
                dprintf (GTC_LOG,("Not enough space for all ephemeral generations with compaction"));
                should_expand = TRUE;
            }
        }
    }

#ifdef BIT64
    BOOL high_memory = FALSE;
#endif // BIT64

    // 根据碎片空间大小判断
    if (!should_compact)
    {
        // We are not putting this in dt_high_frag_p because it's not exactly
        // high fragmentation - it's just enough planned fragmentation for us to 
        // want to compact. Also the "fragmentation" we are talking about here
        // is different from anywhere else.
        // 碎片空间大小 >= dd_fragmentation_limit 或者
        // 碎片空间大小 / 收集代的大小(包括更年轻的代) >= dd_fragmentation_burden_limit 时开启压缩
        // 作者机器上的dd_fragmentation_limit是200000, dd_fragmentation_burden_limit是0.25
        BOOL frag_exceeded = ((fragmentation >= dd_fragmentation_limit (dd)) &&
                                (fragmentation_burden >= dd_fragmentation_burden_limit (dd)));

        if (frag_exceeded)
        {
#ifdef BACKGROUND_GC
            // do not force compaction if this was a stress-induced GC
            IN_STRESS_HEAP(if (!settings.stress_induced))
            {
#endif // BACKGROUND_GC
            assert (settings.concurrent == FALSE);
            should_compact = TRUE;
            get_gc_data_per_heap()->set_mechanism (gc_heap_compact, compact_high_frag);
#ifdef BACKGROUND_GC
            }
#endif // BACKGROUND_GC
        }

        // 如果占用内存过高则启用压缩
#ifdef BIT64
        // check for high memory situation
        if(!should_compact)
        {
            uint32_t num_heaps = 1;
#ifdef MULTIPLE_HEAPS
            num_heaps = gc_heap::n_heaps;
#endif // MULTIPLE_HEAPS
            
            ptrdiff_t reclaim_space = generation_size(max_generation) - generation_plan_size(max_generation);
            if((settings.entry_memory_load >= high_memory_load_th) && (settings.entry_memory_load < v_high_memory_load_th))
            {
                if(reclaim_space > (int64_t)(min_high_fragmentation_threshold (entry_available_physical_mem, num_heaps)))
                {
                    dprintf(GTC_LOG,("compacting due to fragmentation in high memory"));
                    should_compact = TRUE;
                    get_gc_data_per_heap()->set_mechanism (gc_heap_compact, compact_high_mem_frag);
                }
                high_memory = TRUE;
            }
            else if(settings.entry_memory_load >= v_high_memory_load_th)
            {
                if(reclaim_space > (ptrdiff_t)(min_reclaim_fragmentation_threshold (num_heaps)))
                {
                    dprintf(GTC_LOG,("compacting due to fragmentation in very high memory"));
                    should_compact = TRUE;
                    get_gc_data_per_heap()->set_mechanism (gc_heap_compact, compact_vhigh_mem_frag);
                }
                high_memory = TRUE;
            }
        }
#endif // BIT64
    }

    // 测试是否可以在ephemeral_heap_segment.allocated后面提交一段内存(从系统获取一块物理内存)
    // 如果失败则启用压缩
    allocated (ephemeral_heap_segment);
    size_t size = Align (min_obj_size)*(condemned_gen_number+1);
    // The purpose of calling ensure_gap_allocation here is to make sure
    // that we actually are able to commit the memory to allocate generation
    // starts.
    if ((should_compact == FALSE) &&
        (ensure_gap_allocation (condemned_gen_number) == FALSE))
    {
        should_compact = TRUE;
        get_gc_data_per_heap()->set_mechanism (gc_heap_compact, compact_no_gaps);
    }

    // 如果这次Full GC的效果比较差
    // 需要减少Full GC的频率，should_lock_elevation可以把Full GC变为gen 1 GC
    if (settings.condemned_generation == max_generation)
    {
        //check the progress
        if (
#ifdef BIT64
            (high_memory && !should_compact) ||
#endif // BIT64
            (generation_plan_allocation_start (generation_of (max_generation - 1)) >= 
                generation_allocation_start (generation_of (max_generation - 1))))
        {
            dprintf (2, (" Elevation: gen2 size: %d, gen2 plan size: %d, no progress, elevation = locked",
                     generation_size (max_generation),
                     generation_plan_size (max_generation)));
            //no progress -> lock
            settings.should_lock_elevation = TRUE;
        }
    }

    // 如果启用了NoGCRegion但是仍然启用了GC代表这是无法从SOH(Small Object Heap)或者LOH分配到内存导致的，需要启用压缩
    if (settings.pause_mode == pause_no_gc)
    {
        should_compact = TRUE;
        // 如果ephemeral heap segement压缩后的剩余空间不足还需要设置新的ephemeral heap segment
        if ((size_t)(heap_segment_reserved (ephemeral_heap_segment) - heap_segment_plan_allocated (ephemeral_heap_segment))
            < soh_allocation_no_gc)
        {
            should_expand = TRUE;
        }
    }

    dprintf (2, ("will %s", (should_compact ? "compact" : "sweep")));
    return should_compact;
}

计划阶段在模拟压缩和判断后会在内部包含重定位阶段(relocate_phase)，压缩阶段(compact_phase)和清扫阶段(sweep_phase)的处理，
接下来我们仔细分析一下这三个阶段做了什么事情:

重定位阶段(relocate_phase)

重定位阶段的主要工作是修改对象的指针地址，例如A.Member的Member内存移动后，A中指向Member的指针地址也需要改变。
重定位阶段只会修改指针地址，复制内存会交给下面的压缩阶段(compact_phase)完成。

如下图:

图中对象A和对象B引用了对象C，重定位后各个对象还在原来的位置，只是成员的地址(指针)变化了。

还记得之前标记阶段(mark_phase)使用的GcScanRoots等扫描函数吗？
这些扫描函数同样会在重定位阶段使用，只是执行的不是GCHeap::Promote而是GCHeap::Relocate。
重定位对象会借助计划阶段(plan_phase)构建的brick table和plug树来进行快速的定位，然后对指针地址移动所属plug的reloc位置。

重定位阶段(relocate_phase)的代码

gc_heap::relocate_phase函数的代码如下:

void gc_heap::relocate_phase (int condemned_gen_number,
                              uint8_t* first_condemned_address)
{
    // 生成扫描上下文
    ScanContext sc;
    sc.thread_number = heap_number;
    sc.promotion = FALSE;
    sc.concurrent = FALSE;

    // 统计重定位阶段的开始时间
#ifdef TIME_GC
        unsigned start;
        unsigned finish;
        start = GetCycleCount32();
#endif //TIME_GC

//  %type%  category = quote (relocate);
    dprintf (2,("---- Relocate phase -----"));

#ifdef MULTIPLE_HEAPS
    //join all threads to make sure they are synchronized
    dprintf(3, ("Joining after end of plan"));
    gc_t_join.join(this, gc_join_begin_relocate_phase);
    if (gc_t_join.joined())
#endif //MULTIPLE_HEAPS

    {
#ifdef MULTIPLE_HEAPS

        //join all threads to make sure they are synchronized
        dprintf(3, ("Restarting for relocation"));
        gc_t_join.restart();
#endif //MULTIPLE_HEAPS
    }

    // 扫描根对象(各个线程中栈和寄存器中的对象)
    // 对扫描到的各个对象调用`GCHeap::Relocate`函数
    // 注意`GCHeap::Relocate`函数不会重定位子对象，这里只是用来重定位来源于根对象的引用
    dprintf(3,("Relocating roots"));
    GCScan::GcScanRoots(GCHeap::Relocate,
                            condemned_gen_number, max_generation, &sc);

    verify_pins_with_post_plug_info("after reloc stack");

#ifdef BACKGROUND_GC
    if (recursive_gc_sync::background_running_p())
    {
        scan_background_roots (GCHeap::Relocate, heap_number, &sc);
    }
#endif //BACKGROUND_GC

    // 非Full GC时，遍历Card Table重定位小对象
    // 同上，`gc_heap::relocate_address`函数不会重定位子对象，这里只是用来重定位来源于旧代的引用
    if (condemned_gen_number != max_generation)
    {
        dprintf(3,("Relocating cross generation pointers"));
        mark_through_cards_for_segments (&gc_heap::relocate_address, TRUE);
        verify_pins_with_post_plug_info("after reloc cards");
    }
    // 非Full GC时，遍历Card Table重定位大对象
    // 同上，`gc_heap::relocate_address`函数不会重定位子对象，这里只是用来重定位来源于旧代的引用
    if (condemned_gen_number != max_generation)
    {
        dprintf(3,("Relocating cross generation pointers for large objects"));
        mark_through_cards_for_large_objects (&gc_heap::relocate_address, TRUE);
    }
    else
    {
        // Full GC时，如果启用了大对象压缩则压缩大对象的堆
#ifdef FEATURE_LOH_COMPACTION
        if (loh_compacted_p)
        {
            assert (settings.condemned_generation == max_generation);
            relocate_in_loh_compact();
        }
        else
#endif //FEATURE_LOH_COMPACTION
        {
            relocate_in_large_objects ();
        }
    }
    // 重定位存活下来的对象中的引用（收集代中的对象）
    // 枚举brick table对各个plug中的对象调用`relocate_obj_helper`重定位它们的成员
    {
        dprintf(3,("Relocating survivors"));
        relocate_survivors (condemned_gen_number,
                            first_condemned_address);
    }

    // 扫描在析构队列中的对象
#ifdef FEATURE_PREMORTEM_FINALIZATION
        dprintf(3,("Relocating finalization data"));
        finalize_queue->RelocateFinalizationData (condemned_gen_number,
                                                       __this);
#endif // FEATURE_PREMORTEM_FINALIZATION

    // 扫描在GC Handle表中的对象
// MTHTS
    {
        dprintf(3,("Relocating handle table"));
        GCScan::GcScanHandles(GCHeap::Relocate,
                                  condemned_gen_number, max_generation, &sc);
    }

#ifdef MULTIPLE_HEAPS
    //join all threads to make sure they are synchronized
    dprintf(3, ("Joining after end of relocation"));
    gc_t_join.join(this, gc_join_relocate_phase_done);

#endif //MULTIPLE_HEAPS

    // 统计重定位阶段的结束时间
#ifdef TIME_GC
        finish = GetCycleCount32();
        reloc_time = finish - start;
#endif //TIME_GC

    dprintf(2,( "---- End of Relocate phase ----"));
}

GCHeap::Relocate函数的代码如下:

// ppObject是保存对象地址的地址，例如&A.Member
void GCHeap::Relocate (Object** ppObject, ScanContext* sc,
                       uint32_t flags)
{
    UNREFERENCED_PARAMETER(sc);

    // 对象的地址
    uint8_t* object = (uint8_t*)(Object*)(*ppObject);
    
    THREAD_NUMBER_FROM_CONTEXT;

    //dprintf (3, ("Relocate location %Ix\n", (size_t)ppObject));
    dprintf (3, ("R: %Ix", (size_t)ppObject));

    // 空指针不处理
    if (object == 0)
        return;

    // 获取对象所属的gc_heap
    gc_heap* hp = gc_heap::heap_of (object);

    // 验证对象是否合法，除错用
    // 如果object不一定是对象的开始地址，则不做验证
#ifdef _DEBUG
    if (!(flags & GC_CALL_INTERIOR))
    {
        // We cannot validate this object if it's in the condemned gen because it could 
        // be one of the objects that were overwritten by an artificial gap due to a pinned plug.
        if (!((object >= hp->gc_low) && (object < hp->gc_high)))
        {
            ((CObjectHeader*)object)->Validate(FALSE);
        }
    }
#endif //_DEBUG

    dprintf (3, ("Relocate %Ix\n", (size_t)object));

    uint8_t* pheader;

    // 如果object不一定是对象的开始地址，找到对象的开始地址并重定位该开始地址，然后修改ppObject
    // 例如object是0x10000008，对象的开始地址是0x10000000，重定位后是0x0fff0000则*ppObject会设为0x0fff0008
    if ((flags & GC_CALL_INTERIOR) && gc_heap::settings.loh_compaction)
    {
        if (!((object >= hp->gc_low) && (object < hp->gc_high)))
        {
            return;
        }

        if (gc_heap::loh_object_p (object))
        {
            pheader = hp->find_object (object, 0);
            if (pheader == 0)
            {
                return;
            }

            ptrdiff_t ref_offset = object - pheader;
            hp->relocate_address(&pheader THREAD_NUMBER_ARG);
            *ppObject = (Object*)(pheader + ref_offset);
            return;
        }
    }

    // 如果object是对象的开始地址则重定位object
    {
        pheader = object;
        hp->relocate_address(&pheader THREAD_NUMBER_ARG);
        *ppObject = (Object*)pheader;
    }

    STRESS_LOG_ROOT_RELOCATE(ppObject, object, pheader, ((!(flags & GC_CALL_INTERIOR)) ? ((Object*)object)->GetGCSafeMethodTable() : 0));
}

gc_heap::relocate_address函数的代码如下:

void gc_heap::relocate_address (uint8_t** pold_address THREAD_NUMBER_DCL)
{
    // 不在本次gc回收范围内的对象指针不需要移动
    uint8_t* old_address = *pold_address;
    if (!((old_address >= gc_low) && (old_address < gc_high)))
#ifdef MULTIPLE_HEAPS
    {
        UNREFERENCED_PARAMETER(thread);
        if (old_address == 0)
            return;
        gc_heap* hp = heap_of (old_address);
        if ((hp == this) ||
            !((old_address >= hp->gc_low) && (old_address < hp->gc_high)))
            return;
    }
#else //MULTIPLE_HEAPS
        return ;
#endif //MULTIPLE_HEAPS
    // 根据对象找到对应的brick
    // delta translates old_address into address_gc (old_address);
    size_t  brick = brick_of (old_address);
    int    brick_entry =  brick_table [ brick ];
    uint8_t*  new_address = old_address;
    if (! ((brick_entry == 0)))
    {
    retry:
        {
            // 如果是负数则向前继续找
            while (brick_entry < 0)
            {
                brick = (brick + brick_entry);
                brick_entry =  brick_table [ brick ];
            }
            uint8_t* old_loc = old_address;

            // 根据plug树搜索对象所在的plug
            uint8_t* node = tree_search ((brick_address (brick) + brick_entry-1),
                                      old_loc);
            // 找到时确定新的地址，找不到时继续找前面的brick(有可能在上一个brick中)
            if ((node <= old_loc))
                new_address = (old_address + node_relocation_distance (node));
            else
            {
                if (node_left_p (node))
                {
                    dprintf(3,(" L: %Ix", (size_t)node));
                    new_address = (old_address +
                                   (node_relocation_distance (node) +
                                    node_gap_size (node)));
                }
                else
                {
                    brick = brick - 1;
                    brick_entry =  brick_table [ brick ];
                    goto retry;
                }
            }
        }
        // 修改对象指针的地址
        *pold_address = new_address;
        return;
    }

    // 如果对象是大对象，对象本身就是一个plug所以可以直接取到reloc
#ifdef FEATURE_LOH_COMPACTION
    if (loh_compacted_p
#ifdef FEATURE_BASICFREEZE
        && !frozen_object_p((Object*)old_address)
#endif // FEATURE_BASICFREEZE
        )
    {
        *pold_address = old_address + loh_node_relocation_distance (old_address);
    }
    else
#endif //FEATURE_LOH_COMPACTION
    {
        *pold_address = new_address;
    }
}

gc_heap::relocate_survivors函数的代码如下:
这个函数用于重定位存活下来的对象中的引用

void gc_heap::relocate_survivors (int condemned_gen_number,
                                  uint8_t* first_condemned_address)
{
    generation* condemned_gen = generation_of (condemned_gen_number);
    uint8_t*  start_address = first_condemned_address;
    size_t  current_brick = brick_of (start_address);
    heap_segment*  current_heap_segment = heap_segment_rw (generation_start_segment (condemned_gen));

    PREFIX_ASSUME(current_heap_segment != NULL);

    uint8_t*  end_address = 0;

    // 重设mark_stack_array队列
    reset_pinned_queue_bos();

    // 更新gc_heap中的oldest_pinned_plug对象
    update_oldest_pinned_plug();
    
    end_address = heap_segment_allocated (current_heap_segment);

    size_t  end_brick = brick_of (end_address - 1);

    // 初始化重定位参数
    relocate_args args;
    // 本次gc的回收范围
    args.low = gc_low;
    args.high = gc_high;
    // 当前的plug结尾是否被下一个plug覆盖了
    args.is_shortened = FALSE
    // last_plug或者last_plug后面的pinned plug
    // 处理plug尾部数据覆盖时需要用到它
    args.pinned_plug_entry = 0;
    // 上一个plug，用于遍历树时可以从小地址到大地址遍历(中序遍历)
    args.last_plug = 0;
    
    while (1)
    {
        // 当前segment已经处理完
        if (current_brick > end_brick)
        {
            // 处理最后一个plug，结尾地址是heap_segment_allocated
            if (args.last_plug)
            {
                {
                    assert (!(args.is_shortened));
                    relocate_survivors_in_plug (args.last_plug,
                                                heap_segment_allocated (current_heap_segment),
                                                args.is_shortened, 
                                                args.pinned_plug_entry);
                }

                args.last_plug = 0;
            }

            // 如果有下一个segment则处理下一个
            if (heap_segment_next_rw (current_heap_segment))
            {
                current_heap_segment = heap_segment_next_rw (current_heap_segment);
                current_brick = brick_of (heap_segment_mem (current_heap_segment));
                end_brick = brick_of (heap_segment_allocated (current_heap_segment)-1);
                continue;
            }
            else
            {
                break;
            }
        }
        {
            // 如果当前brick有对应的plug树，处理当前brick
            int brick_entry =  brick_table [ current_brick ];

            if (brick_entry >= 0)
            {
                relocate_survivors_in_brick (brick_address (current_brick) +
                                             brick_entry -1,
                                             &args);
            }
        }
        current_brick++;
    }
}

gc_heap::relocate_survivors_in_brick函数的代码如下:

void gc_heap::relocate_survivors_in_brick (uint8_t* tree, relocate_args* args)
{
    // 遍历plug树
    // 会从小到大调用relocate_survivors_in_plug (中序遍历, 借助args->last_plug)
    // 例如有这样的plug树
    //     a
    //   b   c
    // d  e
    // 枚举顺序是a b d e c
    // 调用relocate_survivors_in_plug的顺序是d b e a c
    assert ((tree != NULL));

    dprintf (3, ("tree: %Ix, args->last_plug: %Ix, left: %Ix, right: %Ix, gap(t): %Ix",
        tree, args->last_plug, 
        (tree + node_left_child (tree)),
        (tree + node_right_child (tree)),
        node_gap_size (tree)));

    // 处理左节点
    if (node_left_child (tree))
    {
        relocate_survivors_in_brick (tree + node_left_child (tree), args);
    }

    // 处理last_plug
    {
        uint8_t*  plug = tree;
        BOOL   has_post_plug_info_p = FALSE;
        BOOL   has_pre_plug_info_p = FALSE;

        // 如果这个plug是pinned plug
        // 获取是否有has_pre_plug_info_p (是否覆盖了last_plug的尾部)
        // 获取是否有has_post_plug_info_p (是否被下一个plug覆盖了尾部)
        if (tree == oldest_pinned_plug)
        {
            args->pinned_plug_entry = get_oldest_pinned_entry (&has_pre_plug_info_p,
                                                               &has_post_plug_info_p);
            assert (tree == pinned_plug (args->pinned_plug_entry));

            dprintf (3, ("tree is the oldest pin: %Ix", tree));
        }

        // 处理last_plug
        if (args->last_plug)
        {
            size_t  gap_size = node_gap_size (tree);
            // last_plug的结尾 = 当前plug的开始地址 - gap
            uint8_t*  gap = (plug - gap_size);
            dprintf (3, ("tree: %Ix, gap: %Ix (%Ix)", tree, gap, gap_size));
            assert (gap_size >= Align (min_obj_size));
            uint8_t*  last_plug_end = gap;

            // last_plug的尾部是否被覆盖了
            // args->is_shortened代表last_plug是pinned_plug，被下一个unpinned plug覆盖了尾部
            // has_pre_plug_info_p代表last_plug是unpinned plug，被下一个pinned plug覆盖了尾部
            BOOL check_last_object_p = (args->is_shortened || has_pre_plug_info_p);

            // 处理last_plug，结尾地址是当前plug的开始地址 - gap
            {
                relocate_survivors_in_plug (args->last_plug, last_plug_end, check_last_object_p, args->pinned_plug_entry);
            }
        }
        else
        {
            assert (!has_pre_plug_info_p);
        }

        // 设置last_plug
        args->last_plug = plug;
        // 设置是否被覆盖了尾部
        args->is_shortened = has_post_plug_info_p;
        if (has_post_plug_info_p)
        {
            dprintf (3, ("setting %Ix as shortened", plug));
        }
        dprintf (3, ("last_plug: %Ix(shortened: %d)", plug, (args->is_shortened ? 1 : 0)));
    }

    // 处理右节点
    if (node_right_child (tree))
    {
        relocate_survivors_in_brick (tree + node_right_child (tree), args);
    }
}

gc_heap::relocate_survivors_in_plug函数的代码如下:

void gc_heap::relocate_survivors_in_plug (uint8_t* plug, uint8_t* plug_end,
                                          BOOL check_last_object_p, 
                                          mark* pinned_plug_entry)
{
    //dprintf(3,("Relocating pointers in Plug [%Ix,%Ix[", (size_t)plug, (size_t)plug_end));
    dprintf (3,("RP: [%Ix,%Ix[", (size_t)plug, (size_t)plug_end));

    // plug的结尾被覆盖过，需要特殊的处理
    if (check_last_object_p)
    {
        relocate_shortened_survivor_helper (plug, plug_end, pinned_plug_entry);
    }
    // 一般的处理
    else
    {
        relocate_survivor_helper (plug, plug_end);
    }
}

gc_heap::relocate_survivor_helper函数的代码如下:

void gc_heap::relocate_survivor_helper (uint8_t* plug, uint8_t* plug_end)
{
    // 枚举plug中的对象，分别调用relocate_obj_helper函数
    uint8_t*  x = plug;
    while (x < plug_end)
    {
        size_t s = size (x);
        uint8_t* next_obj = x + Align (s);
        Prefetch (next_obj);
        relocate_obj_helper (x, s);
        assert (s > 0);
        x = next_obj;
    }
}

gc_heap::relocate_obj_helper函数的代码如下:

inline void
gc_heap::relocate_obj_helper (uint8_t* x, size_t s)
{
    THREAD_FROM_HEAP;
    // 判断对象中是否包含了引用
    if (contain_pointers (x))
    {
        dprintf (3, ("$%Ix$", (size_t)x));

        // 重定位这个对象的所有成员
        // 注意这里不会包含对象自身(nostart)
        go_through_object_nostart (method_table(x), x, s, pval,
                            {
                                uint8_t* child = *pval;
                                reloc_survivor_helper (pval);
                                if (child)
                                {
                                    dprintf (3, ("%Ix->%Ix->%Ix", (uint8_t*)pval, child, *pval));
                                }
                            });

    }
    check_class_object_demotion (x);
}

gc_heap::reloc_survivor_helper函数的代码如下:

inline void
gc_heap::reloc_survivor_helper (uint8_t** pval)
{
    // 执行重定位，relocate_address函数上面有解释
    THREAD_FROM_HEAP;
    relocate_address (pval THREAD_NUMBER_ARG);

    // 如果对象在降代范围中，需要设置来源位置在Card Table中的标记
    check_demotion_helper (pval, (uint8_t*)pval);
}

gc_heap::relocate_shortened_survivor_helper函数的代码如下:

void gc_heap::relocate_shortened_survivor_helper (uint8_t* plug, uint8_t* plug_end, mark* pinned_plug_entry)
{
    uint8_t*  x = plug;

    // 如果p_plug == plug表示当前plug是pinned plug，结尾被下一个plug覆盖
    // 如果p_plug != plug表示当前plug是unpinned plug，结尾被p_plug覆盖
    uint8_t* p_plug = pinned_plug (pinned_plug_entry);
    BOOL is_pinned = (plug == p_plug);
    BOOL check_short_obj_p = (is_pinned ? pinned_plug_entry->post_short_p() : pinned_plug_entry->pre_short_p());

    // 因为这个plug的结尾被覆盖了，下一个plug的gap是特殊gap，这里要加回去大小
    plug_end += sizeof (gap_reloc_pair);

    //dprintf (3, ("%s %Ix is shortened, and last object %s overwritten", (is_pinned ? "PP" : "NP"), plug, (check_short_obj_p ? "is" : "is not")));
    dprintf (3, ("%s %Ix-%Ix short, LO: %s OW", (is_pinned ? "PP" : "NP"), plug, plug_end, (check_short_obj_p ? "is" : "is not")));

    verify_pins_with_post_plug_info("begin reloc short surv");

    // 枚举plug中的对象
    while (x < plug_end)
    {
        // plug的最后一个对象被完全覆盖了，需要做特殊处理
        if (check_short_obj_p && ((plug_end - x) < min_pre_pin_obj_size))
        {
            dprintf (3, ("last obj %Ix is short", x));

            // 当前plug是pinned plug，结尾被下一个unpinned plug覆盖了
            // 根据最后一个对象的成员bitmap重定位
            if (is_pinned)
            {
#ifdef COLLECTIBLE_CLASS
                if (pinned_plug_entry->post_short_collectible_p())
                    unconditional_set_card_collectible (x);
#endif //COLLECTIBLE_CLASS

                // Relocate the saved references based on bits set.
                // 成员应该存在的地址(被覆盖的数据中)，设置Card Table会使用这个地址
                uint8_t** saved_plug_info_start = (uint8_t**)(pinned_plug_entry->get_post_plug_info_start());
                // 成员真实存在的地址(备份数据中)
                uint8_t** saved_info_to_relocate = (uint8_t**)(pinned_plug_entry->get_post_plug_reloc_info());
                // 枚举成员的bitmap
                for (size_t i = 0; i < pinned_plug_entry->get_max_short_bits(); i++)
                {
                    // 如果成员存在则重定位该成员
                    if (pinned_plug_entry->post_short_bit_p (i))
                    {
                        reloc_ref_in_shortened_obj ((saved_plug_info_start + i), (saved_info_to_relocate + i));
                    }
                }
            }
            // 当前plug是unpinned plug，结尾被下一个pinned plug覆盖了
            // 处理和上面一样
            else
            {
#ifdef COLLECTIBLE_CLASS
                if (pinned_plug_entry->pre_short_collectible_p())
                    unconditional_set_card_collectible (x);
#endif //COLLECTIBLE_CLASS

                relocate_pre_plug_info (pinned_plug_entry);

                // Relocate the saved references based on bits set.
                uint8_t** saved_plug_info_start = (uint8_t**)(p_plug - sizeof (plug_and_gap));
                uint8_t** saved_info_to_relocate = (uint8_t**)(pinned_plug_entry->get_pre_plug_reloc_info());
                for (size_t i = 0; i < pinned_plug_entry->get_max_short_bits(); i++)
                {
                    if (pinned_plug_entry->pre_short_bit_p (i))
                    {
                        reloc_ref_in_shortened_obj ((saved_plug_info_start + i), (saved_info_to_relocate + i));
                    }
                }
            }

            // 处理完最后一个对象，可以跳出了
            break;
        }

        size_t s = size (x);
        uint8_t* next_obj = x + Align (s);
        Prefetch (next_obj);

        // 最后一个对象被覆盖了，但是只是覆盖了后半部分，不是全部被覆盖
        if (next_obj >= plug_end) 
        {
            dprintf (3, ("object %Ix is at the end of the plug %Ix->%Ix", 
                next_obj, plug, plug_end));

            verify_pins_with_post_plug_info("before reloc short obj");

            relocate_shortened_obj_helper (x, s, (x + Align (s) - sizeof (plug_and_gap)), pinned_plug_entry, is_pinned);
        }
        // 对象未被覆盖，调用一般的处理
        else
        {
            relocate_obj_helper (x, s);
        }

        assert (s > 0);
        x = next_obj;
    }

    verify_pins_with_post_plug_info("end reloc short surv");
}

gc_heap::reloc_ref_in_shortened_obj函数的代码如下:

inline 
void gc_heap::reloc_ref_in_shortened_obj (uint8_t** address_to_set_card, uint8_t** address_to_reloc)
{
    THREAD_FROM_HEAP;

    // 重定位对象
    // 这里的address_to_reloc会在备份数据中
    uint8_t* old_val = (address_to_reloc ? *address_to_reloc : 0);
    relocate_address (address_to_reloc THREAD_NUMBER_ARG);
    if (address_to_reloc)
    {
        dprintf (3, ("SR %Ix: %Ix->%Ix", (uint8_t*)address_to_reloc, old_val, *address_to_reloc));
    }

    // 如果对象在降代范围中，设置Card Table
    // 这里的address_to_set_card会在被覆盖的数据中
    //check_demotion_helper (current_saved_info_to_relocate, (uint8_t*)pval);
    uint8_t* relocated_addr = *address_to_reloc;
    if ((relocated_addr < demotion_high) &&
        (relocated_addr >= demotion_low))
    {
        dprintf (3, ("set card for location %Ix(%Ix)",
                    (size_t)address_to_set_card, card_of((uint8_t*)address_to_set_card)));

        set_card (card_of ((uint8_t*)address_to_set_card));
    }
#ifdef MULTIPLE_HEAPS
    // 不在当前heap时试着找到对象所在的heap并且用该heap处理
    else if (settings.demotion)
    {
        gc_heap* hp = heap_of (relocated_addr);
        if ((relocated_addr < hp->demotion_high) &&
            (relocated_addr >= hp->demotion_low))
        {
            dprintf (3, ("%Ix on h%d, set card for location %Ix(%Ix)",
                        relocated_addr, hp->heap_number, (size_t)address_to_set_card, card_of((uint8_t*)address_to_set_card)));

            set_card (card_of ((uint8_t*)address_to_set_card));
        }
    }
#endif //MULTIPLE_HEAPS
}

gc_heap::relocate_shortened_obj_helper函数的代码如下:

inline
void gc_heap::relocate_shortened_obj_helper (uint8_t* x, size_t s, uint8_t* end, mark* pinned_plug_entry, BOOL is_pinned)
{
    THREAD_FROM_HEAP;
    uint8_t* plug = pinned_plug (pinned_plug_entry);

    // 如果当前plug是unpinned plug, 代表邻接的pinned plug中保存的pre_plug_info_reloc_start可能已经被移动了
    // 这里需要重定位pinned plug中保存的pre_plug_info_reloc_start (unpinned plug被覆盖的内容的开始地址)
    if (!is_pinned)
    {
        //// Temporary - we just wanna make sure we are doing things right when padding is needed.
        //if ((x + s) < plug)
        //{
        //    dprintf (3, ("obj %Ix needed padding: end %Ix is %d bytes from pinned obj %Ix", 
        //        x, (x + s), (plug- (x + s)), plug));
        //    GCToOSInterface::DebugBreak();
        //}

        relocate_pre_plug_info (pinned_plug_entry);
    }

    verify_pins_with_post_plug_info("after relocate_pre_plug_info");

    uint8_t* saved_plug_info_start = 0;
    uint8_t** saved_info_to_relocate = 0;

    // saved_plug_info_start等于被覆盖的地址的开始
    // saved_info_to_relocate等于原始内容的开始
    if (is_pinned)
    {
        saved_plug_info_start = (uint8_t*)(pinned_plug_entry->get_post_plug_info_start());
        saved_info_to_relocate = (uint8_t**)(pinned_plug_entry->get_post_plug_reloc_info());
    }
    else
    {
        saved_plug_info_start = (plug - sizeof (plug_and_gap));
        saved_info_to_relocate = (uint8_t**)(pinned_plug_entry->get_pre_plug_reloc_info());
    }
    
    uint8_t** current_saved_info_to_relocate = 0;
    uint8_t* child = 0;

    dprintf (3, ("x: %Ix, pp: %Ix, end: %Ix", x, plug, end));

    // 判断对象中是否包含了引用
    if (contain_pointers (x))
    {
        dprintf (3,("$%Ix$", (size_t)x));

        // 重定位这个对象的所有成员
        // 注意这里不会包含对象自身(nostart)
        go_through_object_nostart (method_table(x), x, s, pval,
        {
            dprintf (3, ("obj %Ix, member: %Ix->%Ix", x, (uint8_t*)pval, *pval));

            // 成员所在的部分被覆盖了，调用reloc_ref_in_shortened_obj重定位
            // pval = 成员应该存在的地址(被覆盖的数据中)，设置Card Table会使用这个地址
            // current_saved_info_to_relocate = 成员真实存在的地址(备份数据中)
            if ((uint8_t*)pval >= end)
            {
                current_saved_info_to_relocate = saved_info_to_relocate + ((uint8_t*)pval - saved_plug_info_start) / sizeof (uint8_t**);
                child = *current_saved_info_to_relocate;
                reloc_ref_in_shortened_obj (pval, current_saved_info_to_relocate);
                dprintf (3, ("last part: R-%Ix(saved: %Ix)->%Ix ->%Ix",
                    (uint8_t*)pval, current_saved_info_to_relocate, child, *current_saved_info_to_relocate));
            }
            // 成员所在的部分未被覆盖，调用一般的处理
            else
            {
                reloc_survivor_helper (pval);
            }
        });
    }

    check_class_object_demotion (x);
}

重定位阶段(relocate_phase)只是修改了引用对象的地址，对象还在原来的位置，接下来进入压缩阶段(compact_phase):

压缩阶段(compact_phase)

压缩阶段负责把对象复制到之前模拟压缩到的地址上，简单点来讲就是用memcpy复制这些对象到新的地址。
压缩阶段会使用之前构建的brick table和plug树快速的枚举对象。

gc_heap::compact_phase函数的代码如下:
这个函数的代码是不是有点眼熟？它的流程和上面的relocate_survivors很像，都是枚举brick table然后中序枚举plug树

void gc_heap::compact_phase (int condemned_gen_number,
                             uint8_t*  first_condemned_address,
                             BOOL clear_cards)
{
//  %type%  category = quote (compact);
    // 统计压缩阶段的开始时间
#ifdef TIME_GC
        unsigned start;
        unsigned finish;
        start = GetCycleCount32();
#endif //TIME_GC
    generation*   condemned_gen = generation_of (condemned_gen_number);
    uint8_t*  start_address = first_condemned_address;
    size_t   current_brick = brick_of (start_address);
    heap_segment*  current_heap_segment = heap_segment_rw (generation_start_segment (condemned_gen));

    PREFIX_ASSUME(current_heap_segment != NULL);

    // 重设mark_stack_array队列
    reset_pinned_queue_bos();

    // 更新gc_heap中的oldest_pinned_plug对象
    update_oldest_pinned_plug();

    // 如果should_expand的时候重用了以前的segment作为ephemeral heap segment，则需要重新计算generation_allocation_size
    // reused_seg会影响压缩参数中的check_gennum_p
    BOOL reused_seg = expand_reused_seg_p();
    if (reused_seg)
    {
        for (int i = 1; i <= max_generation; i++)
        {
            generation_allocation_size (generation_of (i)) = 0;
        }
    }

    uint8_t*  end_address = heap_segment_allocated (current_heap_segment);

    size_t  end_brick = brick_of (end_address-1);

    // 初始化压缩参数
    compact_args args;
    // 上一个plug，用于遍历树时可以从小地址到大地址遍历(中序遍历)
    args.last_plug = 0;
    // 当前brick的最后一个plug，更新brick table时使用
    args.before_last_plug = 0;
    // 最后设置的brick，用于复制plug后更新brick table
    args.current_compacted_brick = ~((size_t)1);
    // 当前的plug结尾是否被下一个plug覆盖了
    args.is_shortened = FALSE;
    // last_plug或者last_plug后面的pinned plug
    // 处理plug尾部数据覆盖时需要用到它
    args.pinned_plug_entry = 0;
    // 是否需要在复制对象时复制相应的Card Table范围
    args.copy_cards_p =  (condemned_gen_number >= 1) || !clear_cards;
    // 重新计算generation_allocation_size时使用的参数
    args.check_gennum_p = reused_seg;
    if (args.check_gennum_p)
    {
        args.src_gennum = ((current_heap_segment == ephemeral_heap_segment) ? -1 : 2);
    }

    dprintf (2,("---- Compact Phase: %Ix(%Ix)----", 
        first_condemned_address, brick_of (first_condemned_address)));

#ifdef MULTIPLE_HEAPS
    //restart
    if (gc_t_join.joined())
    {
#endif //MULTIPLE_HEAPS

#ifdef MULTIPLE_HEAPS
        dprintf(3, ("Restarting for compaction"));
        gc_t_join.restart();
    }
#endif //MULTIPLE_HEAPS

    // 再次重设mark_stack_array队列
    reset_pinned_queue_bos();

    // 判断是否需要压缩大对象的堆
#ifdef FEATURE_LOH_COMPACTION
    if (loh_compacted_p)
    {
        compact_loh();
    }
#endif //FEATURE_LOH_COMPACTION

    // 循环brick table
    if ((start_address < end_address) ||
        (condemned_gen_number == max_generation))
    {
        while (1)
        {
            // 当前segment已经处理完
            if (current_brick > end_brick)
            {
                // 处理最后一个plug，大小是heap_segment_allocated - last_plug
                if (args.last_plug != 0)
                {
                    dprintf (3, ("compacting last plug: %Ix", args.last_plug))
                    compact_plug (args.last_plug,
                                  (heap_segment_allocated (current_heap_segment) - args.last_plug),
                                  args.is_shortened,
                                  &args);
                }

                // 如果有下一个segment则处理下一个
                if (heap_segment_next_rw (current_heap_segment))
                {
                    current_heap_segment = heap_segment_next_rw (current_heap_segment);
                    current_brick = brick_of (heap_segment_mem (current_heap_segment));
                    end_brick = brick_of (heap_segment_allocated (current_heap_segment)-1);
                    args.last_plug = 0;
                    // 更新src_gennum (如果segment是ephemeral_heap_segment则需要进一步判断)
                    if (args.check_gennum_p)
                    {
                        args.src_gennum = ((current_heap_segment == ephemeral_heap_segment) ? -1 : 2);
                    }
                    continue;
                }
                // 设置最后一个brick的偏移值, 给compact_plug善后
                else
                {
                    if (args.before_last_plug !=0)
                    {
                        dprintf (3, ("Fixing last brick %Ix to point to plug %Ix",
                                    args.current_compacted_brick, (size_t)args.before_last_plug));
                        assert (args.current_compacted_brick != ~1u);
                        set_brick (args.current_compacted_brick,
                                   args.before_last_plug - brick_address (args.current_compacted_brick));
                    }
                    break;
                }
            }
            {
                // 如果当前brick有对应的plug树，处理当前brick
                int  brick_entry =  brick_table [ current_brick ];
                dprintf (3, ("B: %Ix(%Ix)->%Ix", 
                    current_brick, (size_t)brick_entry, (brick_address (current_brick) + brick_entry - 1)));

                if (brick_entry >= 0)
                {
                    compact_in_brick ((brick_address (current_brick) + brick_entry -1),
                                      &args);

                }
            }
            current_brick++;
        }
    }

    // 复制已完毕
    // 恢复备份的数据到被覆盖的部分
    recover_saved_pinned_info();

    // 统计压缩阶段的结束时间
#ifdef TIME_GC
    finish = GetCycleCount32();
    compact_time = finish - start;
#endif //TIME_GC

    concurrent_print_time_delta ("compact end");

    dprintf(2,("---- End of Compact phase ----"));
}

gc_heap::compact_in_brick函数的代码如下:
这个函数和上面的relocate_survivors_in_brick函数很像

void gc_heap::compact_in_brick (uint8_t* tree, compact_args* args)
{
    assert (tree != NULL);
    int   left_node = node_left_child (tree);
    int   right_node = node_right_child (tree);
    // 需要移动的偏移值，前面计划阶段模拟压缩时设置的reloc
    ptrdiff_t relocation = node_relocation_distance (tree);

    args->print();

    // 处理左节点
    if (left_node)
    {
        dprintf (3, ("B: L: %d->%Ix", left_node, (tree + left_node)));
        compact_in_brick ((tree + left_node), args);
    }

    uint8_t*  plug = tree;
    BOOL   has_pre_plug_info_p = FALSE;
    BOOL   has_post_plug_info_p = FALSE;

    // 如果这个plug是pinned plug
    // 获取是否有has_pre_plug_info_p (是否覆盖了last_plug的尾部)
    // 获取是否有has_post_plug_info_p (是否被下一个plug覆盖了尾部)
    if (tree == oldest_pinned_plug)
    {
        args->pinned_plug_entry = get_oldest_pinned_entry (&has_pre_plug_info_p,
                                                           &has_post_plug_info_p);
        assert (tree == pinned_plug (args->pinned_plug_entry));
    }

    // 处理last_plug
    if (args->last_plug != 0)
    {
        size_t gap_size = node_gap_size (tree);
        // last_plug的结尾 = 当前plug的开始地址 - gap
        uint8_t*  gap = (plug - gap_size);
        uint8_t*  last_plug_end = gap;
        // last_plug的大小 = last_plug的结尾 - last_plug的开始
        size_t last_plug_size = (last_plug_end - args->last_plug);
        dprintf (3, ("tree: %Ix, last_plug: %Ix, gap: %Ix(%Ix), last_plug_end: %Ix, size: %Ix", 
            tree, args->last_plug, gap, gap_size, last_plug_end, last_plug_size));
        
        // last_plug的尾部是否被覆盖了
        // args->is_shortened代表last_plug是pinned_plug，被下一个unpinned plug覆盖了尾部
        // has_pre_plug_info_p代表last_plug是unpinned plug，被下一个pinned plug覆盖了尾部
        BOOL check_last_object_p = (args->is_shortened || has_pre_plug_info_p);
        if (!check_last_object_p)
        {
            assert (last_plug_size >= Align (min_obj_size));
        }

        // 处理last_plug
        compact_plug (args->last_plug, last_plug_size, check_last_object_p, args);
    }
    else
    {
        // 第一个plug不可能覆盖前面的plug的结尾
        assert (!has_pre_plug_info_p);
    }

    dprintf (3, ("set args last plug to plug: %Ix, reloc: %Ix", plug, relocation));
    // 设置last_plug
    args->last_plug = plug;
    // 设置last_plugd移动偏移值
    args->last_plug_relocation = relocation;
    // 设置是否被覆盖了尾部
    args->is_shortened = has_post_plug_info_p;

    // 处理右节点
    if (right_node)
    {
        dprintf (3, ("B: R: %d->%Ix", right_node, (tree + right_node)));
        compact_in_brick ((tree + right_node), args);
    }
}

gc_heap::compact_plug函数的代码如下:

void gc_heap::compact_plug (uint8_t* plug, size_t size, BOOL check_last_object_p, compact_args* args)
{
    args->print();

    // 复制到的地址，plug + reloc
    uint8_t* reloc_plug = plug + args->last_plug_relocation;

    // 如果plug的结尾被覆盖过
    if (check_last_object_p)
    {
        // 添加特殊gap的大小
        size += sizeof (gap_reloc_pair);
        mark* entry = args->pinned_plug_entry;

        // 在复制内存前把被覆盖的内容和原始内容交换一下
        // 复制内存后需要交换回去
        if (args->is_shortened)
        {
            // 当前plug是pinned plug，被下一个unpinned plug覆盖
            assert (entry->has_post_plug_info());
            entry->swap_post_plug_and_saved();
        }
        else
        {
            // 当前plug是unpinned plug，被下一个pinned plug覆盖
            assert (entry->has_pre_plug_info());
            entry->swap_pre_plug_and_saved();
        }
    }

    // 复制之前的brick中的偏移值
    int  old_brick_entry =  brick_table [brick_of (plug)];

    assert (node_relocation_distance (plug) == args->last_plug_relocation);

    // 处理对齐和pad
#ifdef FEATURE_STRUCTALIGN
    ptrdiff_t alignpad = node_alignpad(plug);
    if (alignpad)
    {
        make_unused_array (reloc_plug - alignpad, alignpad);
        if (brick_of (reloc_plug - alignpad) != brick_of (reloc_plug))
        {
            // The alignment padding is straddling one or more bricks;
            // it has to be the last "object" of its first brick.
            fix_brick_to_highest (reloc_plug - alignpad, reloc_plug);
        }
    }
#else // FEATURE_STRUCTALIGN
    size_t unused_arr_size = 0; 
    BOOL  already_padded_p = FALSE;
#ifdef SHORT_PLUGS
    if (is_plug_padded (plug))
    {
        already_padded_p = TRUE;
        clear_plug_padded (plug);
        unused_arr_size = Align (min_obj_size);
    }
#endif //SHORT_PLUGS
    if (node_realigned (plug))
    {
        unused_arr_size += switch_alignment_size (already_padded_p);
    }

    if (unused_arr_size != 0) 
    {
        make_unused_array (reloc_plug - unused_arr_size, unused_arr_size);

        if (brick_of (reloc_plug - unused_arr_size) != brick_of (reloc_plug))
        {
            dprintf (3, ("fix B for padding: %Id: %Ix->%Ix", 
                unused_arr_size, (reloc_plug - unused_arr_size), reloc_plug));
            // The alignment padding is straddling one or more bricks;
            // it has to be the last "object" of its first brick.
            fix_brick_to_highest (reloc_plug - unused_arr_size, reloc_plug);
        }
    }
#endif // FEATURE_STRUCTALIGN

#ifdef SHORT_PLUGS
    if (is_plug_padded (plug))
    {
        make_unused_array (reloc_plug - Align (min_obj_size), Align (min_obj_size));

        if (brick_of (reloc_plug - Align (min_obj_size)) != brick_of (reloc_plug))
        {
            // The alignment padding is straddling one or more bricks;
            // it has to be the last "object" of its first brick.
            fix_brick_to_highest (reloc_plug - Align (min_obj_size), reloc_plug);
        }
    }
#endif //SHORT_PLUGS

    // 复制plug中的所有内容和对应的Card Table中的范围(如果copy_cards_p成立)
    gcmemcopy (reloc_plug, plug, size, args->copy_cards_p);

    // 重新统计generation_allocation_size
    if (args->check_gennum_p)
    {
        int src_gennum = args->src_gennum;
        if (src_gennum == -1)
        {
            src_gennum = object_gennum (plug);
        }

        int dest_gennum = object_gennum_plan (reloc_plug);

        if (src_gennum < dest_gennum)
        {
            generation_allocation_size (generation_of (dest_gennum)) += size;
        }
    }

    // 更新brick table
    // brick table中会保存brick的最后一个plug的偏移值，跨越多个brick的时候后面的brick会是-1
    size_t current_reloc_brick = args->current_compacted_brick;

    // 如果已经到了下一个brick
    // 设置上一个brick的值 = 上一个brick中最后的plug的偏移值, 或者-1
    if (brick_of (reloc_plug) != current_reloc_brick)
    {
        dprintf (3, ("last reloc B: %Ix, current reloc B: %Ix", 
            current_reloc_brick, brick_of (reloc_plug)));

        if (args->before_last_plug)
        {
            dprintf (3,(" fixing last brick %Ix to point to last plug %Ix(%Ix)",
                     current_reloc_brick,
                     args->before_last_plug, 
                     (args->before_last_plug - brick_address (current_reloc_brick))));

            {
                set_brick (current_reloc_brick,
                        args->before_last_plug - brick_address (current_reloc_brick));
            }
        }
        current_reloc_brick = brick_of (reloc_plug);
    }
    
    // 如果跨越了多个brick
    size_t end_brick = brick_of (reloc_plug + size-1);
    if (end_brick != current_reloc_brick)
    {
        // The plug is straddling one or more bricks
        // It has to be the last plug of its first brick
        dprintf (3,("plug spanning multiple bricks, fixing first brick %Ix to %Ix(%Ix)",
                 current_reloc_brick, (size_t)reloc_plug,
                 (reloc_plug - brick_address (current_reloc_brick))));

        // 设置第一个brick中的偏移值
        {
            set_brick (current_reloc_brick,
                    reloc_plug - brick_address (current_reloc_brick));
        }

        // 把后面的brick设为-1，除了end_brick
        // update all intervening brick
        size_t brick = current_reloc_brick + 1;
        dprintf (3,("setting intervening bricks %Ix->%Ix to -1",
            brick, (end_brick - 1)));
        while (brick < end_brick)
        {
            set_brick (brick, -1);
            brick++;
        }

        // 如果end_brick中无其他plug，end_brick也会被设为-1
        // brick_address (end_brick) - 1 - brick_address (end_brick) = -1
        // code last brick offset as a plug address
        args->before_last_plug = brick_address (end_brick) -1;
        current_reloc_brick = end_brick;
        dprintf (3, ("setting before last to %Ix, last brick to %Ix",
            args->before_last_plug, current_reloc_brick));
    } 
    // 如果只在一个brick中
    else
    {
        // 记录当前brick中的最后一个plug
        dprintf (3, ("still in the same brick: %Ix", end_brick));
        args->before_last_plug = reloc_plug;
    }
    // 更新最后设置的brick
    args->current_compacted_brick = current_reloc_brick;

    // 复制完毕以后把被覆盖的内容和原始内容交换回去
    // 注意如果plug移动的距离比覆盖的大小要少，这里会把复制后的内容给破坏掉
    // 后面还需要使用recover_saved_pinned_info还原
    if (check_last_object_p)
    {
        mark* entry = args->pinned_plug_entry;

        if (args->is_shortened)
        {
            entry->swap_post_plug_and_saved();
        }
        else
        {
            entry->swap_pre_plug_and_saved();
        }
    }
}

gc_heap::gcmemcopy函数的代码如下:

// POPO TODO: We should actually just recover the artifically made gaps here..because when we copy
// we always copy the earlier plugs first which means we won't need the gap sizes anymore. This way
// we won't need to individually recover each overwritten part of plugs.
inline
void  gc_heap::gcmemcopy (uint8_t* dest, uint8_t* src, size_t len, BOOL copy_cards_p)
{
    // 如果地址一样可以跳过
    if (dest != src)
    {
#ifdef BACKGROUND_GC
        if (current_c_gc_state == c_gc_state_marking) 
        {
            //TODO: should look to see whether we should consider changing this
            // to copy a consecutive region of the mark array instead.
            copy_mark_bits_for_addresses (dest, src, len);
        }
#endif //BACKGROUND_GC
        // 复制plug中的所有对象到新的地址上
        // memcopy做的东西和memcpy一样，微软自己写的一个函数而已
        //dprintf(3,(" Memcopy [%Ix->%Ix, %Ix->%Ix[", (size_t)src, (size_t)dest, (size_t)src+len, (size_t)dest+len));
        dprintf(3,(" mc: [%Ix->%Ix, %Ix->%Ix[", (size_t)src, (size_t)dest, (size_t)src+len, (size_t)dest+len));
        memcopy (dest - plug_skew, src - plug_skew, (int)len);
#ifdef FEATURE_USE_SOFTWARE_WRITE_WATCH_FOR_GC_HEAP
        if (SoftwareWriteWatch::IsEnabledForGCHeap())
        {
            // The ranges [src - plug_kew .. src[ and [src + len - plug_skew .. src + len[ are ObjHeaders, which don't have GC
            // references, and are not relevant for write watch. The latter range actually corresponds to the ObjHeader for the
            // object at (src + len), so it can be ignored anyway.
            SoftwareWriteWatch::SetDirtyRegion(dest, len - plug_skew);
        }
#endif // FEATURE_USE_SOFTWARE_WRITE_WATCH_FOR_GC_HEAP
        // 复制对应的Card Table范围
        // copy_cards_p成立的时候复制src ~ src+len到dest
        // copy_cards_p不成立的时候清除dest ~ dest+len
        copy_cards_range (dest, src, len, copy_cards_p);
    }
}

gc_heap::compact_loh函数的代码如下:

void gc_heap::compact_loh()
{
    assert (should_compact_loh());

    generation* gen        = large_object_generation;
    heap_segment* start_seg = heap_segment_rw (generation_start_segment (gen));
    PREFIX_ASSUME(start_seg != NULL);
    heap_segment* seg      = start_seg;
    heap_segment* prev_seg = 0;
    uint8_t* o             = generation_allocation_start (gen);

    //Skip the generation gap object
    o = o + AlignQword (size (o));
    // We don't need to ever realloc gen3 start so don't touch it.
    uint8_t* free_space_start = o;
    uint8_t* free_space_end = o;
    generation_allocator (gen)->clear();
    generation_free_list_space (gen) = 0;
    generation_free_obj_space (gen) = 0;

    loh_pinned_queue_bos = 0;

    // 枚举大对象的堆
    while (1)
    {
        // 当前segment处理完毕，处理下一个
        if (o >= heap_segment_allocated (seg))
        {
            heap_segment* next_seg = heap_segment_next (seg);

            // 如果当前segment为空，表示可以删掉这个segment
            // 修改segment链表，把空的segment放到后面
            if ((heap_segment_plan_allocated (seg) == heap_segment_mem (seg)) &&
                (seg != start_seg) && !heap_segment_read_only_p (seg))
            {
                dprintf (3, ("Preparing empty large segment %Ix", (size_t)seg));
                assert (prev_seg);
                heap_segment_next (prev_seg) = next_seg;
                heap_segment_next (seg) = freeable_large_heap_segment;
                freeable_large_heap_segment = seg;
            }
            else
            {
                // 更新heap_segment_allocated
                // 释放(decommit)未使用的内存空间
                if (!heap_segment_read_only_p (seg))
                {
                    // We grew the segment to accommondate allocations.
                    if (heap_segment_plan_allocated (seg) > heap_segment_allocated (seg))
                    {
                        if ((heap_segment_plan_allocated (seg) - plug_skew)  > heap_segment_used (seg))
                        {
                            heap_segment_used (seg) = heap_segment_plan_allocated (seg) - plug_skew;
                        }
                    }

                    heap_segment_allocated (seg) = heap_segment_plan_allocated (seg);
                    dprintf (3, ("Trimming seg to %Ix[", heap_segment_allocated (seg)));
                    decommit_heap_segment_pages (seg, 0);
                    dprintf (1236, ("CLOH: seg: %Ix, alloc: %Ix, used: %Ix, committed: %Ix",
                        seg, 
                        heap_segment_allocated (seg),
                        heap_segment_used (seg),
                        heap_segment_committed (seg)));
                    //heap_segment_used (seg) = heap_segment_allocated (seg) - plug_skew;
                    dprintf (1236, ("CLOH: used is set to %Ix", heap_segment_used (seg)));
                }
                prev_seg = seg;
            }

            // 处理下一个segment，不存在时跳出
            seg = next_seg;
            if (seg == 0)
                break;
            else
            {
                o = heap_segment_mem (seg);
            }
        }

        // 如果对象已标记
        if (marked (o))
        {
            free_space_end = o;
            size_t size = AlignQword (size (o));

            size_t loh_pad;
            uint8_t* reloc = o;
            // 清除标记
            clear_marked (o);

            // 如果对象是固定的
            if (pinned (o))
            {
                // We are relying on the fact the pinned objects are always looked at in the same order 
                // in plan phase and in compact phase.
                mark* m = loh_pinned_plug_of (loh_deque_pinned_plug());
                uint8_t* plug = pinned_plug (m);
                assert (plug == o);

                loh_pad = pinned_len (m);
                // 清除固定标记
                clear_pinned (o);
            }
            else
            {
                loh_pad = AlignQword (loh_padding_obj_size);

                // 复制对象内存
                reloc += loh_node_relocation_distance (o);
                gcmemcopy (reloc, o, size, TRUE);
            }

            // 添加loh_pad到free list
            thread_gap ((reloc - loh_pad), loh_pad, gen);

            // 处理下一个对象
            o = o + size;
            free_space_start = o;
            if (o < heap_segment_allocated (seg))
            {
                assert (!marked (o));
            }
        }
        else
        {
            // 跳过未标记对象
            while (o < heap_segment_allocated (seg) && !marked (o))
            {
                o = o + AlignQword (size (o));
            }
        }
    }

    assert (loh_pinned_plug_que_empty_p());

    dprintf (1235, ("after GC LOH size: %Id, free list: %Id, free obj: %Id\n\n", 
        generation_size (max_generation + 1), 
        generation_free_list_space (gen),
        generation_free_obj_space (gen)));
}

gc_heap::recover_saved_pinned_info函数的代码如下:

void gc_heap::recover_saved_pinned_info()
{
    // 重设mark_stack_array队列
    reset_pinned_queue_bos();

    // 恢复各个pinned plug被覆盖或者覆盖的数据
    while (!(pinned_plug_que_empty_p()))
    {
        mark* oldest_entry = oldest_pin();
        oldest_entry->recover_plug_info();
#ifdef GC_CONFIG_DRIVEN
        if (oldest_entry->has_pre_plug_info() && oldest_entry->has_post_plug_info())
            record_interesting_data_point (idp_pre_and_post_pin);
        else if (oldest_entry->has_pre_plug_info())
            record_interesting_data_point (idp_pre_pin);
        else if (oldest_entry->has_post_plug_info())
            record_interesting_data_point (idp_post_pin);
#endif //GC_CONFIG_DRIVEN

        deque_pinned_plug();
    }
}

mark::recover_plug_info函数的代码如下:
函数前面的注释讲的是之前复制plug的时候已经包含了被覆盖的内容(swap_pre_plug_and_saved)，
但是如果移动的位置小于3个指针的大小(注释中的< 3应该是>= 3)则复制完以后有可能再次被swap_pre_plug_and_saved破坏掉。

// We should think about whether it's really necessary to have to copy back the pre plug
// info since it was already copied during compacting plugs. But if a plug doesn't move
// by < 3 ptr size, it means we'd have to recover pre plug info.
void recover_plug_info() 
{
    // 如果这个pinned plug覆盖了前一个unpinned plug的结尾，把备份的数据恢复回去
    if (saved_pre_p)
    {
        // 如果已经压缩过，需要复制到重定位后的saved_pre_plug_info_reloc_start
        // 并且使用saved_pre_plug_reloc备份(这个备份里面的成员也经过了重定位)
        if (gc_heap::settings.compaction)
        {
            dprintf (3, ("%Ix: REC Pre: %Ix-%Ix", 
                first,
                &saved_pre_plug_reloc, 
                saved_pre_plug_info_reloc_start));
            memcpy (saved_pre_plug_info_reloc_start, &saved_pre_plug_reloc, sizeof (saved_pre_plug_reloc));
        }
        // 如果未压缩过，可以复制到这个pinned plug的前面
        // 并且使用saved_pre_plug备份
        else
        {
            dprintf (3, ("%Ix: REC Pre: %Ix-%Ix", 
                first,
                &saved_pre_plug, 
                (first - sizeof (plug_and_gap))));
            memcpy ((first - sizeof (plug_and_gap)), &saved_pre_plug, sizeof (saved_pre_plug));
        }
    }

    // 如果这个pinned plug被下一个unpinned plug覆盖了结尾，把备份的数据恢复回去
    if (saved_post_p)
    {
        // 因为pinned plug不会移动
        // 这里的saved_post_plug_info_start不会改变
        // 使用saved_post_plug_reloc备份(这个备份里面的成员也经过了重定位)
        if (gc_heap::settings.compaction)
        {
            dprintf (3, ("%Ix: REC Post: %Ix-%Ix", 
                first,
                &saved_post_plug_reloc, 
                saved_post_plug_info_start));
            memcpy (saved_post_plug_info_start, &saved_post_plug_reloc, sizeof (saved_post_plug_reloc));
        }
        // 使用saved_pre_plug备份
        else
        {
            dprintf (3, ("%Ix: REC Post: %Ix-%Ix", 
                first,
                &saved_post_plug, 
                saved_post_plug_info_start));
            memcpy (saved_post_plug_info_start, &saved_post_plug, sizeof (saved_post_plug));
        }
    }
}

压缩阶段结束以后还需要做一些收尾工作，请从上面plan_phase中的fix_generation_bounds (condemned_gen_number, consing_gen);继续看。
如果计划阶段不选择压缩，就会进入清扫阶段:

清扫阶段(sweep_phase)

清扫阶段负责把plug与plug之间的空间变为free object然后加到对应代的free list中，并且负责修改代边界。
加到free list中的区域会在后面供分配新的上下文使用。

清扫阶段的主要工作在函数make_free_lists中完成，名称叫sweep_phase的函数目前不存在。
扫描plug时会使用计划阶段构建好的plug信息和brick table，但模拟压缩的偏移值reloc和计划代边界plan_allocation_start不会被使用。

清扫阶段的代码

gc_heap::make_free_lists函数的代码如下:

void gc_heap::make_free_lists (int condemned_gen_number)
{
    // 统计清扫阶段的开始时间
#ifdef TIME_GC
    unsigned start;
    unsigned finish;
    start = GetCycleCount32();
#endif //TIME_GC

    //Promotion has to happen in sweep case.
    assert (settings.promotion);

    // 从收集代的第一个segment开始处理
    generation* condemned_gen = generation_of (condemned_gen_number);
    uint8_t* start_address = generation_allocation_start (condemned_gen);

    size_t  current_brick = brick_of (start_address);
    heap_segment* current_heap_segment = heap_segment_rw (generation_start_segment (condemned_gen));

    PREFIX_ASSUME(current_heap_segment != NULL);

    uint8_t*  end_address = heap_segment_allocated (current_heap_segment);
    size_t  end_brick = brick_of (end_address-1);

    // 清扫阶段使用的参数
    make_free_args args;
    // 当前生成的free object应该归到的代序号
    // 更新代边界的时候也会使用
    args.free_list_gen_number = min (max_generation, 1 + condemned_gen_number);
    // 超过这个值就需要更新free_list_gen_number和free_list_gen
    // 在清扫阶段settings.promotion == true时
    //    generation_limit遇到gen 0或者gen 1的时候返回heap_segment_reserved (ephemeral_heap_segment)，则原代0的对象归到代1
    //    generation_limit遇到gen 2的时候返回generation_allocation_start (generation_of ((gen_number - 2)))，则原代1的对象归到代2
    // MAX_PTR只是用来检测第一次使用的，后面会更新
    args.current_gen_limit = (((condemned_gen_number == max_generation)) ?
                              MAX_PTR :
                              (generation_limit (args.free_list_gen_number)));
    // 当前生成的free object应该归到的代
    args.free_list_gen = generation_of (args.free_list_gen_number);
    // 当前brick中地址最大的plug，用于更新brick表
    args.highest_plug = 0;

    // 开始遍历brick
    if ((start_address < end_address) ||
        (condemned_gen_number == max_generation))
    {
        while (1)
        {
            // 当前segment处理完毕
            if ((current_brick > end_brick))
            {
                // 如果第一个segment无存活的对象，则重设它的heap_segment_allocated
                // 并且设置generation_allocation_start (gen)等于这个空segment的开始地址
                if (args.current_gen_limit == MAX_PTR)
                {
                    //We had an empty segment
                    //need to allocate the generation start

                    generation* gen = generation_of (max_generation);

                    heap_segment* start_seg = heap_segment_rw (generation_start_segment (gen));

                    PREFIX_ASSUME(start_seg != NULL);

                    uint8_t* gap = heap_segment_mem (start_seg);

                    generation_allocation_start (gen) = gap;
                    heap_segment_allocated (start_seg) = gap + Align (min_obj_size);
                    // 确保代最少有一个对象
                    make_unused_array (gap, Align (min_obj_size));
                    // 更新代边界
                    reset_allocation_pointers (gen, gap);
                    dprintf (3, ("Start segment empty, fixing generation start of %d to: %Ix",
                                 max_generation, (size_t)gap));
                    // 更新current_gen_limit
                    args.current_gen_limit = generation_limit (args.free_list_gen_number);
                }
                // 有下一个segment的时候继续处理下一个segment, 否则跳出
                if (heap_segment_next_rw (current_heap_segment))
                {
                    current_heap_segment = heap_segment_next_rw (current_heap_segment);
                    current_brick = brick_of (heap_segment_mem (current_heap_segment));
                    end_brick = brick_of (heap_segment_allocated (current_heap_segment)-1);

                    continue;
                }
                else
                {
                    break;
                }
            }
            {
                // 如果brick中保存了对plug树的偏移值则
                //    调用make_free_list_in_brick
                //    设置brick到地址最大的plug
                // 否则设置设为-1 (把-2, -3等等的都改为-1)
                int brick_entry =  brick_table [ current_brick ];
                if ((brick_entry >= 0))
                {
                    make_free_list_in_brick (brick_address (current_brick) + brick_entry-1, &args);
                    dprintf(3,("Fixing brick entry %Ix to %Ix",
                               current_brick, (size_t)args.highest_plug));
                    set_brick (current_brick,
                               (args.highest_plug - brick_address (current_brick)));
                }
                else
                {
                    if ((brick_entry > -32768))
                    {

#ifdef _DEBUG
                        ptrdiff_t offset = brick_of (args.highest_plug) - current_brick;
                        if ((brick_entry != -32767) && (! ((offset == brick_entry))))
                        {
                            assert ((brick_entry == -1));
                        }
#endif //_DEBUG
                        //init to -1 for faster find_first_object
                        set_brick (current_brick, -1);
                    }
                }
            }
            current_brick++;
        }
    }
    {
        // 设置剩余的代边界
        int bottom_gen = 0;
        args.free_list_gen_number--;
        while (args.free_list_gen_number >= bottom_gen)
        {
            uint8_t*  gap = 0;
            generation* gen2 = generation_of (args.free_list_gen_number);
            // 保证代中最少有一个对象
            gap = allocate_at_end (Align(min_obj_size));
            generation_allocation_start (gen2) = gap;
            // 设置代边界
            reset_allocation_pointers (gen2, gap);
            dprintf(3,("Fixing generation start of %d to: %Ix",
                       args.free_list_gen_number, (size_t)gap));
            PREFIX_ASSUME(gap != NULL);
            // 代中第一个对象应该是free object
            make_unused_array (gap, Align (min_obj_size));

            args.free_list_gen_number--;
        }

        // 更新alloc_allocated成员到gen 0的开始边界
        //reset the allocated size
        uint8_t* start2 = generation_allocation_start (youngest_generation);
        alloc_allocated = start2 + Align (size (start2));
    }

    // 统计清扫阶段的结束时间
#ifdef TIME_GC
    finish = GetCycleCount32();
    sweep_time = finish - start;
#endif //TIME_GC
}

gc_heap::make_free_list_in_brick函数的代码如下:

void gc_heap::make_free_list_in_brick (uint8_t* tree, make_free_args* args)
{
    assert ((tree != NULL));
    {
        int  right_node = node_right_child (tree);
        int left_node = node_left_child (tree);
        args->highest_plug = 0;
        if (! (0 == tree))
        {
            // 处理左边的节点
            if (! (0 == left_node))
            {
                make_free_list_in_brick (tree + left_node, args);
            }
            // 处理当前节点
            {
                uint8_t*  plug = tree;
                // 当前plug前面的空余空间
                size_t  gap_size = node_gap_size (tree);
                // 空余空间的开始
                uint8_t*  gap = (plug - gap_size);
                dprintf (3,("Making free list %Ix len %d in %d",
                //dprintf (3,("F: %Ix len %Ix in %d",
                        (size_t)gap, gap_size, args->free_list_gen_number));
                // 记录当前brick中地址最大的plug
                args->highest_plug = tree;
#ifdef SHORT_PLUGS
                if (is_plug_padded (plug))
                {
                    dprintf (3, ("%Ix padded", plug));
                    clear_plug_padded (plug);
                }
#endif //SHORT_PLUGS
            gen_crossing:
                {
                    // 如果current_gen_limit等于MAX_PTR，表示我们需要先决定gen 2的边界
                    // 如果plug >= args->current_gen_limit并且plug在ephemeral heap segment，表示我们需要决定gen 1或gen 0的边界
                    // 决定的流程如下
                    // - 第一次current_gen_limit == MAX_PTR，在处理所有对象之前决定gen 2的边界
                    // - 第二次plug超过了generation_allocation_start (generation_of ((gen_number - 2)))并且在ephemeral heap segment中，决定gen 1的边界
                    // - 因为plug不会超过heap_segment_reserved (ephemeral_heap_segment)，第三次会在上面的"设置剩余的代边界"中决定gen 0的边界
                    if ((args->current_gen_limit == MAX_PTR) ||
                        ((plug >= args->current_gen_limit) &&
                         ephemeral_pointer_p (plug)))
                    {
                        dprintf(3,(" Crossing Generation boundary at %Ix",
                               (size_t)args->current_gen_limit));
                        // 在处理所有对象之前决定gen 2的边界时，不需要减1
                        if (!(args->current_gen_limit == MAX_PTR))
                        {
                            args->free_list_gen_number--;
                            args->free_list_gen = generation_of (args->free_list_gen_number);
                        }
                        dprintf(3,( " Fixing generation start of %d to: %Ix",
                                args->free_list_gen_number, (size_t)gap));
                        
                        // 决定代边界
                        reset_allocation_pointers (args->free_list_gen, gap);
                        // 更新current_gen_limit用于决定下一个代的边界
                        args->current_gen_limit = generation_limit (args->free_list_gen_number);

                        // 保证代中最少有一个对象
                        // 如果这个gap比较大(大于最小对象大小 * 2)，剩余的空间还可以在下面放到free list中
                        if ((gap_size >= (2*Align (min_obj_size))))
                        {
                            dprintf(3,(" Splitting the gap in two %Id left",
                                   gap_size));
                            make_unused_array (gap, Align(min_obj_size));
                            gap_size = (gap_size - Align(min_obj_size));
                            gap = (gap + Align(min_obj_size));
                        }
                        else
                        {
                            make_unused_array (gap, gap_size);
                            gap_size = 0;
                        }
                        goto gen_crossing;
                    }
                }

                // 加到free list中
                thread_gap (gap, gap_size, args->free_list_gen);
                add_gen_free (args->free_list_gen->gen_num, gap_size);
            }
            // 处理右边的节点
            if (! (0 == right_node))
            {
                make_free_list_in_brick (tree + right_node, args);
            }
        }
    }
}

压缩阶段结束以后还需要做一些收尾工作，请从上面plan_phase中的recover_saved_pinned_info();继续看。