V8 Garbage Collection [DRAFT]
Created at 2017-04-15T12:09:10+09:00

Assumes things I've written in v8-ignition-turbofan.

Basic steps

[ Initialization ]
- Isolate::Init =>
  - Heap::Setup =>
    - ConfigureHeapDefault
    - InitializeGCOnce =>
    - new MemoryAllocator, StoreBuffer, IncrementalMarking, ConcurrentMarking
    - new NewSpace, OldSpace (for object) , OldSpace (for executable code), MapSpace + SetUp
    - new Scavenger, MarkCompactCollector

- InitializeGCOnce =>
  - Scavenger::Initialize =>
  - StaticScavengeVisitor::Initialize =>
  - MarkCompactCollector::Initialize =>


[ Allocation via GC system]
(externally)
- v8::Object::New =>
  - Factory::NewJSObject =>
    - CALL_HEAP_FUNCTION =>
      - Heap::AllocateJSObject (return allocation (Object*)) =>
        - AllocateJSObjectFromMap =>
          - SelectSpace (check PretenureFlag, here assume it's NOT_TENURED, then selects NEW_SPACE)
          - Allocate (from existing Map) =>
            - AllocateRaw =>
              - (assume allocate to NEW_SPACE)
              - NewSpace::AllocateRaw => AllocateRawUnaligned =>
                - HeapObject::FromAddress(AllocationInfo::top) (return address top + kHeapObjectTag)
                - AllocationInfo::set_top (extends heap by size_in_bytes)
            - HeapObject::set_map_no_write_barrier =>
              - MapWord::FromMap
              - set_map_word =>
                - NOBARRIER_WRITE_FIELD(... kMapOffset, map_word.value_) =>
                  - FIELD_ADDR(...kMapOffset) (which is HeapObject's `this` pointer + offset - kHeapObjectTag)
          - InitializeJSObjectFromMap => (forget now)
      - (if allocation failed, Heap::CollectGarbage and retry)
      - RETURN_OBJECT_UNLESS_RETRY =>
        - Handle<JSObject>(JSObject::cast(...)) =>
          - location_ = HandleScope::GetHandle (returns Object**) =>
            - Isolate::handle_scope_data::canonical_scope
            - (CanonicalHandleScope::lookup or CreateHandle)
            - CanonicalHandleScope::lookup => ?
            - CreateHandle =>
              - assign allocated (Heap)Object's pointer to current HandleScopeData::next
              - increment HandleScopeData::next
              - (possibly Extend)
              - return the pointer to the handle (Object**)


[ Heap Object memory layout in heap ]

                 top --------------------
top + kHeapObjectTag -------------------- ( HeapObject's `this` points to here for GC purpose,
                                            but XXX_WRITE_FIELD (and FIELD_ADDR) subtracts it to use memory from top)
 top + size_in_bytes --------------------


[ Data structure ]
Isolate
'-' HandleScopeData
  '-' CanonicalHandleScope
'-' HandleScopeImplementer

Handle (extends HandleBase)
'-' _location (keep pointer to heap object, which means its type is **Object)

Q. what's the scenerio of having a nested HandleScope ?
Q. what are these HandleScope variants ? (e.g. CanonicalHandleScope, DeferredHandleScope, SealHandleScope)

Garbage collections

Tracing facility

Heap
'-' GCTracer
  '-' Event (_current)
    '-' Type (e.g. SCAVENGER, MARK_COMPACTOR)
    '-* Scope
      '-' start_time_

[ Setups ]
- Heap::Setup => new GCTracer

- Heap::CollectGarbage => GCTracer::Start => Event::Event

- TRACE_GC(tracer(), GCTracer::Scope::XXX) =>
  - GCTracer::Scope => set start_time_
  - GCTracer::Scope::~Scope (a.k.a. when out of scope) =>
    - GCTracer::AddScopeSample => set Event::scopes[scope] += duration

[ FLAGs ]
trace_gc
trace_gc_verbose
trace_gc_nvp

Entrypoint

Q. Garbage collection entrypoint (GarbageCollectionReason)?
  - CALL_HEAP_FUNCTION => kAllocationFailure
  - kMemoryPressure
  - MemoryReducer ?
  - SCAVENGER
    - blink idle task ? (kIdleTask)
    - copying
    - aging evacuation
  - MARK_COMPACTOR
    - marking <= some interrupt ?
      - incremental
    - sweep and compact <= memory pressure ?
  - Some contract between ObjectSpace and AllocationSpace

Q. what's "commited" ? Q. what's remembered set ? Q. memory barrier for incremental ?

Copying

[ Copying ]

< 0 >
(assume coming here from CALL_HEAP_FUNCTION)
- Heap::CollectGarbage() =>
- Heap::CollectGarbage =>
  - Heap::Scavenge
    - NewSpace::Flip
    - PromotionQueue::Initialize
    - ScavengeVisitor
    - IterateRoots => ?
    - RememberedSet::Iterate => CheckAndScavengeObject => ?
    - DoScavenge =>
      - (while "coping queue" is not empty)
        - StaticScavengeVisitor::IterateBody (of the object at the bottom of queue) =>
          - (let's assume that's JSObject)
          - StaticNewSpaceVisitor::IterateBody =>
            - VisitorDispatchTable::GetVisitor
            - FlexibleBodyVisitor::Visit =>
              - JSObject::BodyDescriptor::IterateBody (CRTP) =>
                - BodyDescriptorBase::IterateBodyImpl => IteratePointers<StaticScavengeVisitor> =>
                  - StaticScavengeVisitor::VisitPointers (CRTP) (= StaticNewSpaceVisitor) =>
                    - StaticScavengeVisitor::VisitPointer =>
                      - Scavenger::ScavengeObject (coping GC implementation) =>
                        - if it's already copied (a.k.a. HeapObject's MapWord IsForwardingAddress)
                        - then update pointer to be forwarded address
                        - otherwise ScavengeObjectSlow =>
                          - (btw, assume the properties value is JSObject again)
                          - VisitorDispatchTable<ScavengingCallback>::GetVisitor and Visit =>
                            - ObjectEvacuationStrategy<POINTER_OBJECT>::Visit =>
                              - EvacuateObject<POINTER_OBJECT, kWordAligned> => (SEE BELOW < 1 > )
          - Q. ObjectVisitor initialization? callback table?
            - StaticNewSpaceVisitor::Initialize (register visitor for each map visitor id) =>
              - e.g. VisitorDispatchTable::Register(kVisitJSObject, &JSObjectVisitor::Visitor)
            - Scavenger::Initialize => ScavengingVisitor::Initialize =>
              - e.g. VisitorDispatchTable::Register(kVisitJSObject, &ObjectEvacuationStrategy<POINTER_OBJECT>::Visit)
      - (while PromotionQueue is not empty)
        - PromotionQueue::remove
        - IterateAndScavengePromotedObject =>
          - HeapObjectIterateBody => IterateBodyFast => BodyDescriptorApply =>
            - CallIterateBody::apply => JSObject::BodyDescriptor::IterateBody => ... (CRTP) ... =>
              - IterateAndScavengePromotedObjectsVisitor::VisitPointers (CRTP) =>
                - (for each pointer in object fields which referencing "from space")
                  - Scavenger::ScavengeObject (see above)
                  - if scavenged object is in FromSpace (i.e. NewSpace),
                    add this promoted object's field into RememberedSet
    - NewSpace::set_age_mark (heap object below this will be promoted if it's still live next time)

< 1 >
- ScavenginVisitor::EvacuateObject =>
  - if not object ShouldBePromoted (Q. how do we check age of heap object ?)
  - then SemiSpaceCopyObject =>
    - NewSpace::AllocateRaw
    - PromotionQueue::SetNewLimit to the NewSpace::top
    - MigrateObject =>
      - Heap::CopyBlock
      - set forwarding address to the original HeapObject location
    - update pointer to be the newly allocated HeapObject
  - otherwise PromoteObject =>
    - OldSpace::AllocateRaw
    - MigrateObject (here as well)
    - Release_CompareAndSwap (some chromium atomic operation util)
      - to update pointer to be the newly allocated HeapObject
      - since pointer from remember set (old space) is olready handled (Reme!berSet::Iterate before DoScavenge)
        so, we don't have to worry about loaing such track here? but, we do for promoted objects at this cycle?
    - if migratedObject is POINTER_OBJECT then PromotionQueue


(tracing entry)
- ?
  - Heap::ComputeFastPromotionMode =>
    - print "Fast promotion mode: false survival rate:" (for trace_gc_verbose)
  - GCTracer::Stop =>
    - PrintNVP (for trace_gc_nvp) =>
      - print e.g. "41 ms: pause=23.4 mutator=46.9 gc=s ... scavenge=21.31 ..."
  - Heap::PrintShortHeapStatistics (for trace_gc_verbose) =>
    - print e.g. "New space, used: 448 KB, available: 558 KB, committed: 2048 KB"

[ Example ]
(gc.js)
var x = new Object; // Q. how is this object allocated ? (like Factory::New ?)
for (var i = 0; i < 20000; i++) {
  x.p = new Object;
  x = x.p;
}
// Object -> Object -> Object -> Object ... -> Object
//                                             ^^x^^

(tracing)
$ ./out.gn/x64.debug/v8_shell --trace_gc --trace_gc_verbose --trace_gc_nvp gc.js
[26296:0x560474e15e40] Shrinking page 0x1aa83d300000: end 0x1aa83d380000 -> 0x1aa83d352000
[26296:0x560474e15e40] Shrinking page 0x113613280000: end 0x1136132ff000 -> 0x1136132fe000
[26296:0x560474e15e40] Shrinking page 0x113613400000: end 0x11361347f000 -> 0x113613466000
[26296:0x560474e15e40] Shrinking page 0x16ed7c400000: end 0x16ed7c480000 -> 0x16ed7c405000
[26296:0x560474e15e40] Fast promotion mode: false survival rate: 44%
[26296:0x560474e15e40]       41 ms: pause=23.4 mutator=46.9 gc=s reduce_memory=0 heap.prologue=0.01 heap.epilogue=0.80 heap.epilogue.reduce_new_space=0.01 heap.external.prologue=0.00 heap.external.epilogue=0.01 heap.external_weak_global_handles=0.02 scavenge=21.31 evacuate=0.00 old_new=0.18 weak=0.00 roots=0.27 code=0.00 semispace=20.69 steps_count=0 steps_took=0.0 scavenge_throughput=44140 total_size_before=4002472 total_size_after=3430520 holes_size_before=0 holes_size_after=0 allocated=4002472 promoted=0 semi_space_copied=459160 nodes_died_in_new=0 nodes_copied_in_new=0 nodes_promoted=0 promotion_ratio=0.0% average_survival_ratio=44.5% promotion_rate=0.0% semi_space_copy_rate=44.5% new_space_allocation_throughput=0.0 context_disposal_rate=0.0
[26296:0x560474e15e40] Memory allocator,   used:   8704 KB, available: 1457664 KB
[26296:0x560474e15e40] New space,          used:    448 KB, available:    558 KB, committed:   2048 KB
[26296:0x560474e15e40] Old space,          used:    988 KB, available:      0 KB, committed:   1352 KB
[26296:0x560474e15e40] Code space,         used:   1857 KB, available:      0 KB, committed:   2456KB
[26296:0x560474e15e40] Map space,          used:     55 KB, available:      0 KB, committed:    532 KB
[26296:0x560474e15e40] Large object space, used:      0 KB, available: 1457143 KB, committed:      0 KB
[26296:0x560474e15e40] All spaces,         used:   3350 KB, available: 1457702 KB, committed:   6388KB
[26296:0x560474e15e40] External memory reported:      0 KB
[26296:0x560474e15e40] Total time spent in GC  : 23.4 ms
[26296:0x560474e15e40] Fast promotion mode: false survival rate: 2%
[26296:0x560474e15e40]       73 ms: pause=1.9 mutator=30.1 gc=s reduce_memory=0 heap.prologue=0.01 heap.epilogue=0.54 heap.epilogue.reduce_new_space=0.00 heap.external.prologue=0.00 heap.external.epilogue=0.00 heap.external_weak_global_handles=0.01 scavenge=1.00 evacuate=0.00 old_new=0.27 weak=0.00 roots=0.38 code=0.00 semispace=0.23 steps_count=0 steps_took=0.0 scavenge_throughput=81514 total_size_before=4008896 total_size_after=2998816 holes_size_before=0 holes_size_after=0 allocated=578376 promoted=20832 semi_space_copied=208 nodes_died_in_new=0 nodes_copied_in_new=0 nodes_promoted=0 promotion_ratio=2.0% average_survival_ratio=23.3% promotion_rate=4.5% semi_space_copy_rate=0.0% new_space_allocation_throughput=19012.1 context_disposal_rate=0.0
[26296:0x560474e15e40] Memory allocator,   used:   8704 KB, available: 1457664 KB
[26296:0x560474e15e40] New space,          used:      0 KB, available:   1006 KB, committed:   2048 KB
[26296:0x560474e15e40] Old space,          used:   1011 KB, available:      0 KB, committed:   1352 KB
[26296:0x560474e15e40] Code space,         used:   1861 KB, available:      0 KB, committed:   2456KB
[26296:0x560474e15e40] Map space,          used:     55 KB, available:      0 KB, committed:    532 KB
[26296:0x560474e15e40] Large object space, used:      0 KB, available: 1457143 KB, committed:      0 KB
[26296:0x560474e15e40] All spaces,         used:   2928 KB, available: 1458150 KB, committed:   6388KB
[26296:0x560474e15e40] External memory reported:      0 KB
[26296:0x560474e15e40] Total time spent in GC  : 25.3 ms

Mark, Sweep, and Compact

MarkCompactCollector::CollectorState - IDLE, PREPARE_GC, MARK_LIVE_OBJECTS, SWEEP_SPACES (otuers aare. not used yet?)

- Heap::PerformGarbageCollection => Heap::MarkCompact =>
  - MarkCompactCollector::Prepare =>
    - PagedSpace::PrepareForMarkCompact => ?
  - MarkCompactCollector::CollectGarbage =>
    - MarkLiveObjects =>
      - MarkingDeque::StartUsing => ?
      - MarkRoots => ?
      - ProcessMarkingDeque => ?
    - StartSweepSpaces =>
      - StartSweepSpace =>
        - ?
      - Sweeper::StartSweeping => ?
    - EvacuateNewSpaceAndCandidates =>
      - EvacuatePagesInParallel => ?
      - (for each page in new_space_evacuation_pages_)
        - ? Sweeper::AddPage
      - (for each page in old_space_evacuation_pages_)
        - ? Sweeper::AddPage


# TODO

(incremental, concurrent marking ?? how are they scheduled/triggered ??)
- IncrementalMarking::Start
- ConcurrentMarking::Task (not used yet?)

Q. how does marking deque allocates space during gc?
  - "from" space as stack

Q. how is memory layout for paged space for old space, freelist, compaction ?