Multicore OCaml GC

In a mostly functional language like OCaml, it is desirable to have each domain (our unit of parallelism) collect its own local garbage independently. Given that OCaml is commonly used for writing latency sensitive code such as trading systems, UIs, networked unikernels, it is also desirable to minimise the stop-the-world phases in the GC. Although obvious, the difficulty is to make this work in the presence of mutations. In this talk, we will present the overall design of Multicore OCaml GC, but also deep dive into a few of the interesting techniques that make it work.

1. Multicore OCaml GC KC Sivaramakrishnan, Stephen Dolan OCaml Labs University of Cambridge
2. Multicore OCaml
3. • Adds native support for concurrency and parallelism in OCaml Multicore OCaml
4. • Adds native support for concurrency and parallelism in OCaml • Fibers for concurrency, Domains for parallelism ✦ M fibers over N domains ✦ M >>> N Multicore OCaml
5. • Adds native support for concurrency and parallelism in OCaml • Fibers for concurrency, Domains for parallelism ✦ M fibers over N domains ✦ M >>> N • This talk ✦ Overview of multicore GC with a few deep dives. Multicore OCaml
6. • Adds native support for concurrency and parallelism in OCaml • Fibers for concurrency, Domains for parallelism ✦ M fibers over N domains ✦ M >>> N • This talk ✦ Overview of multicore GC with a few deep dives. Multicore OCaml
7. Outline • Difficult to appreciate GC choices in isolation • Begin with a GC for a purely functional language ✦ Gradually add mutations, parallelism and concurrency
8. B Purely functional stack registers heap A C D E
9. B Purely functional • Stop-the-world mark and sweep stack registers heap A C D E
10. B Purely functional • Stop-the-world mark and sweep • Tri-color marking ✦ States: White (Unmarked), Grey (Marking), Black (Marked) ✦ Roots = registers + stack stack registers heap A C D E
11. B Purely functional • Stop-the-world mark and sweep • Tri-color marking ✦ States: White (Unmarked), Grey (Marking), Black (Marked) ✦ Roots = registers + stack • White —> Grey (mark stack) —> Black stack registers heap A C B D E B A mark stack
12. B Purely functional • Stop-the-world mark and sweep • Tri-color marking ✦ States: White (Unmarked), Grey (Marking), Black (Marked) ✦ Roots = registers + stack • White —> Grey (mark stack) —> Black • Mark stack is empty => done ✦ White object = garbage stack registers heap A C B D E A mark stack B D
13. B Purely functional stack registers heap A C B D E A mark stack B D
14. B Purely functional • Pros ✦ Simple ✦ Can perform the GC incrementally ✤ …|—mutator—|—mark—|—mutator—|—mark—|—mutator—|—sweep—|… stack registers heap A C B D E A mark stack B D
15. B Purely functional • Pros ✦ Simple ✦ Can perform the GC incrementally ✤ …|—mutator—|—mark—|—mutator—|—mark—|—mutator—|—sweep—|… • Cons ✦ Need to maintain free-list of objects => allocations overheads + fragmentation stack registers heap A C B D E A mark stack B D
16. Generational GC
17. Generational GC • Generational Hypothesis ✦ Young objects are much more likely to die than old objects
18. Generational GC • Generational Hypothesis ✦ Young objects are much more likely to die than old objects minor heap major heap stack registers
19. Generational GC • Generational Hypothesis ✦ Young objects are much more likely to die than old objects minor heap major heap stack registers frontier
20. Generational GC • Generational Hypothesis ✦ Young objects are much more likely to die than old objects minor heap major heap stack registers frontier • Minor heap collected by copying collection ✦ Survivors promoted to major heap
21. Generational GC • Generational Hypothesis ✦ Young objects are much more likely to die than old objects minor heap major heap stack registers frontier • Minor heap collected by copying collection ✦ Survivors promoted to major heap • Roots are registers and stack ✦ purely functional => no pointers from major to minor
22. Mutations — Minor GC • Old objects might point to young objects minor heap major heap
23. Mutations — Minor GC • Old objects might point to young objects • Must know those pointers for minor GC ✦ (Naively) scan the major GC for such pointers minor heap major heap
24. Mutations — Minor GC • Old objects might point to young objects • Must know those pointers for minor GC ✦ (Naively) scan the major GC for such pointers • Intercept mutations with write barrier (* Before r := x *) let write_barrier (r, x) = if is_major r && is_minor x then remembered_set.add r minor heap major heap
25. Mutations — Minor GC • Old objects might point to young objects • Must know those pointers for minor GC ✦ (Naively) scan the major GC for such pointers • Intercept mutations with write barrier (* Before r := x *) let write_barrier (r, x) = if is_major r && is_minor x then remembered_set.add r • Remembered set ✦ Set of major heap addresses that point to minor heap ✦ Used as root for minor collection ✦ Cleared after minor collection. minor heap major heap
26. Mutations — Major GC A B C
27. Mutations — Major GC A B C
28. Mutations — Major GC A B C
29. Mutations — Major GC A B C A
30. Mutations — Major GC A C A
31. Mutations — Major GC • Mutations are problematic if both conditions hold 1. Exists Black —> White 2. All Grey —> White* —> White paths are deleted A C A
32. Mutations — Major GC • Mutations are problematic if both conditions hold 1. Exists Black —> White 2. All Grey —> White* —> White paths are deleted A C A • Insertion/Dijkstra/Incremental barrier prevents 1
33. B Mutations — Major GC • Mutations are problematic if both conditions hold 1. Exists Black —> White 2. All Grey —> White* —> White paths are deleted A C A • Insertion/Dijkstra/Incremental barrier prevents 1 A C
34. B Mutations — Major GC • Mutations are problematic if both conditions hold 1. Exists Black —> White 2. All Grey —> White* —> White paths are deleted A C A • Insertion/Dijkstra/Incremental barrier prevents 1 A C
35. B B Mutations — Major GC • Mutations are problematic if both conditions hold 1. Exists Black —> White 2. All Grey —> White* —> White paths are deleted A C A • Insertion/Dijkstra/Incremental barrier prevents 1 A C
36. B B Mutations — Major GC • Mutations are problematic if both conditions hold 1. Exists Black —> White 2. All Grey —> White* —> White paths are deleted A C A • Insertion/Dijkstra/Incremental barrier prevents 1 A C • Deletion/Yuasa/snapshot-at-beginning prevents 2
37. B B Mutations — Major GC • Mutations are problematic if both conditions hold 1. Exists Black —> White 2. All Grey —> White* —> White paths are deleted A C A • Insertion/Dijkstra/Incremental barrier prevents 1 A C B C A • Deletion/Yuasa/snapshot-at-beginning prevents 2
38. B B Mutations — Major GC • Mutations are problematic if both conditions hold 1. Exists Black —> White 2. All Grey —> White* —> White paths are deleted A C A • Insertion/Dijkstra/Incremental barrier prevents 1 A C B C A • Deletion/Yuasa/snapshot-at-beginning prevents 2
39. B B Mutations — Major GC • Mutations are problematic if both conditions hold 1. Exists Black —> White 2. All Grey —> White* —> White paths are deleted A C A • Insertion/Dijkstra/Incremental barrier prevents 1 A C B C A B • Deletion/Yuasa/snapshot-at-beginning prevents 2
40. B B Mutations — Major GC • Mutations are problematic if both conditions hold 1. Exists Black —> White 2. All Grey —> White* —> White paths are deleted A C A • Insertion/Dijkstra/Incremental barrier prevents 1 A C B C A B • Deletion/Yuasa/snapshot-at-beginning prevents 2 (* Before r := x *) let write_barrier (r, x) = if is_major r && is_minor x then remembered_set.add r else if is_major r && is_major x then mark(!r)
41. Parallelism — Minor GC • Domain.spawn : (unit -> unit) -> unit
42. Parallelism — Minor GC • Domain.spawn : (unit -> unit) -> unit • Collect each domain’s young garbage independently?
43. Parallelism — Minor GC • Domain.spawn : (unit -> unit) -> unit • Collect each domain’s young garbage independently? major heap domain n minor heap(s) domain 0 …
44. Parallelism — Minor GC • Domain.spawn : (unit -> unit) -> unit • Collect each domain’s young garbage independently? • Invariant: Minor heap objects are only accessed by owning domain major heap domain n minor heap(s) domain 0 …
45. Parallelism — Minor GC • Domain.spawn : (unit -> unit) -> unit • Collect each domain’s young garbage independently? • Invariant: Minor heap objects are only accessed by owning domain • Doligez-Leroy POPL’93 ✦ No pointers between minor heaps ✦ No pointers from major to minor heaps major heap domain n minor heap(s) domain 0 …
46. Parallelism — Minor GC • Domain.spawn : (unit -> unit) -> unit • Collect each domain’s young garbage independently? • Invariant: Minor heap objects are only accessed by owning domain • Doligez-Leroy POPL’93 ✦ No pointers between minor heaps ✦ No pointers from major to minor heaps • Before r := x, if is_major(r) && is_minor(x), then promote(x). major heap domain n minor heap(s) domain 0 …
47. Parallelism — Minor GC • Domain.spawn : (unit -> unit) -> unit • Collect each domain’s young garbage independently? • Invariant: Minor heap objects are only accessed by owning domain • Doligez-Leroy POPL’93 ✦ No pointers between minor heaps ✦ No pointers from major to minor heaps • Before r := x, if is_major(r) && is_minor(x), then promote(x). • Too much promotion. Ex: work-stealing queue major heap domain n minor heap(s) domain 0 …
48. Parallelism — Minor GC major heap domain n minor heap(s) domain 0 …
49. Parallelism — Minor GC major heap domain n minor heap(s) • Weaker invariant ✦ No pointers between minor heaps ✦ Objects in foreign minor heap are not accessed directly domain 0 …
50. Parallelism — Minor GC major heap domain n minor heap(s) • Weaker invariant ✦ No pointers between minor heaps ✦ Objects in foreign minor heap are not accessed directly • Read barrier. If the value loaded is ✦ integers, object in shared heap or own minor heap => continue ✦ object in foreign minor heap => Read fault (Interrupt + promote) domain 0 …
51. Efficient read barrier check
52. Efficient read barrier check • Given x, is x an integer1 or in shared heap2 or own minor heap3
53. Efficient read barrier check • Given x, is x an integer1 or in shared heap2 or own minor heap3 • Careful VM mapping + bit-twiddling
54. Efficient read barrier check • Given x, is x an integer1 or in shared heap2 or own minor heap3 • Careful VM mapping + bit-twiddling • Example: 16-bit address space, 0xPQRS ✦ Minor area 0x4200 — 0x42ff ✦ Domain 0 : 0x4220 — 0x422f ✦ Domain 1 : 0x4250 — 0x425f ✦ Domain 2 : 0x42a0 — 0x42af 0x4200 0x42ff 0 1 2 0x4220 0x422f 0x4250 0x425f 0x42a0 0x42af
55. Efficient read barrier check • Given x, is x an integer1 or in shared heap2 or own minor heap3 • Careful VM mapping + bit-twiddling • Example: 16-bit address space, 0xPQRS ✦ Minor area 0x4200 — 0x42ff ✦ Domain 0 : 0x4220 — 0x422f ✦ Domain 1 : 0x4250 — 0x425f ✦ Domain 2 : 0x42a0 — 0x42af • Integer low_bit(S) = 0x1, Minor PQ = 0x42, R determines domain 0x4200 0x42ff 0 1 2 0x4220 0x422f 0x4250 0x425f 0x42a0 0x42af
56. Efficient read barrier check • Given x, is x an integer1 or in shared heap2 or own minor heap3 • Careful VM mapping + bit-twiddling • Example: 16-bit address space, 0xPQRS ✦ Minor area 0x4200 — 0x42ff ✦ Domain 0 : 0x4220 — 0x422f ✦ Domain 1 : 0x4250 — 0x425f ✦ Domain 2 : 0x42a0 — 0x42af • Integer low_bit(S) = 0x1, Minor PQ = 0x42, R determines domain • Compare with y, where y lies within domain => allocation pointer! ✦ On amd64, allocation pointer is in r15 register 0x4200 0x42ff 0 1 2 0x4220 0x422f 0x4250 0x425f 0x42a0 0x42af
57. Efficient read barrier check # %rax holds x (value of interest) xor %r15, %rax sub 0x0010, %rax test 0xff01, %rax # Any bit set => ZF not set => not foreign minor
58. Efficient read barrier check # %rax holds x (value of interest) xor %r15, %rax sub 0x0010, %rax test 0xff01, %rax # Any bit set => ZF not set => not foreign minor # low_bit(%rax) = 1 xor %r15, %rax # low_bit(%rax) = 1 sub 0x0010, %rax # low_bit(%rax) = 1 test 0xff01, %rax # ZF not set Integer
59. Efficient read barrier check # %rax holds x (value of interest) xor %r15, %rax sub 0x0010, %rax test 0xff01, %rax # Any bit set => ZF not set => not foreign minor # low_bit(%rax) = 1 xor %r15, %rax # low_bit(%rax) = 1 sub 0x0010, %rax # low_bit(%rax) = 1 test 0xff01, %rax # ZF not set # PQ(%r15) != PQ(%rax) xor %r15, %rax # PQ(%rax) is non-zero sub 0x0010, %rax # PQ(%rax) is non-zero test 0xff01, %rax # ZF not set Integer Shared heap
60. Efficient read barrier check # %rax holds x (value of interest) xor %r15, %rax sub 0x0010, %rax test 0xff01, %rax # Any bit set => ZF not set => not foreign minor
61. Efficient read barrier check # %rax holds x (value of interest) xor %r15, %rax sub 0x0010, %rax test 0xff01, %rax # Any bit set => ZF not set => not foreign minor # PQR(%r15) = PQR(%rax) xor %r15, %rax # PQR(%rax) is zero sub 0x0010, %rax # PQ(%rax) is non-zero test 0xff01, %rax # ZF not set Own minor heap
62. Efficient read barrier check # %rax holds x (value of interest) xor %r15, %rax sub 0x0010, %rax test 0xff01, %rax # Any bit set => ZF not set => not foreign minor # PQR(%r15) = PQR(%rax) xor %r15, %rax # PQR(%rax) is zero sub 0x0010, %rax # PQ(%rax) is non-zero test 0xff01, %rax # ZF not set Own minor heap # PQ(%r15) = PQ(%rax) # S(%r15) = S(%rax) = 0 # R(%r15) != R(%rax) xor %r15, %rax # R(%rax) is non-zero, rest 0 sub 0x0010, %rax # rest 0 test 0xff01, %rax # ZF set Foreign minor heap
63. Promotion
64. • How do you promote objects to the major heap on read fault? Promotion
65. • How do you promote objects to the major heap on read fault? • Several alternatives 1. Copy the object to major heap. ✤ Mutable objects, Abstract_tag, … 2. Move the object closure + minor GC. ✤ False promotions, latency, … 3. Move the object closure + scan the minor GC ✤ Need to examine all objects on minor GC Promotion
66. • How do you promote objects to the major heap on read fault? • Several alternatives 1. Copy the object to major heap. ✤ Mutable objects, Abstract_tag, … 2. Move the object closure + minor GC. ✤ False promotions, latency, … 3. Move the object closure + scan the minor GC ✤ Need to examine all objects on minor GC • Hypothesis: most objects promoted on read faults are young. ✦ 95% promoted objects among the youngest 5% Promotion
67. • How do you promote objects to the major heap on read fault? • Several alternatives 1. Copy the object to major heap. ✤ Mutable objects, Abstract_tag, … 2. Move the object closure + minor GC. ✤ False promotions, latency, … 3. Move the object closure + scan the minor GC ✤ Need to examine all objects on minor GC • Hypothesis: most objects promoted on read faults are young. ✦ 95% promoted objects among the youngest 5% • Combine 2 & 3 Promotion
68. Promotion
69. • If promoted object among youngest x%, ✦ move + fix pointers to promoted object ❖ Scan roots = registers + current stack + remembered set ❖ Younger minor objects ❖ Older minor objects referring to younger objects (mutations!) Promotion
70. • If promoted object among youngest x%, ✦ move + fix pointers to promoted object ❖ Scan roots = registers + current stack + remembered set ❖ Younger minor objects ❖ Older minor objects referring to younger objects (mutations!) Promotion (* r := x *) let write_barrier (r, x) = if is_major r && is_minor x then remembered_set.add r else if is_major r && is_major x then mark(!r) else if is_minor r && is_minor x && addr r > addr x then promotion_set.add r
71. • If promoted object among youngest x%, ✦ move + fix pointers to promoted object ❖ Scan roots = registers + current stack + remembered set ❖ Younger minor objects ❖ Older minor objects referring to younger objects (mutations!) • Otherwise, move + minor GC Promotion (* r := x *) let write_barrier (r, x) = if is_major r && is_minor x then remembered_set.add r else if is_major r && is_major x then mark(!r) else if is_minor r && is_minor x && addr r > addr x then promotion_set.add r
72. Parallelism — Major GC
73. Parallelism — Major GC • OCaml’s GC is incremental, needs to be concurrent w/ parallelism
74. Parallelism — Major GC • OCaml’s GC is incremental, needs to be concurrent w/ parallelism • Design based on VCGC from Inferno project (ISMM’98)
75. Parallelism — Major GC • OCaml’s GC is incremental, needs to be concurrent w/ parallelism • Design based on VCGC from Inferno project (ISMM’98) ✦ Allows mutator, marker, sweeper threads to concurrently
76. Parallelism — Major GC • OCaml’s GC is incremental, needs to be concurrent w/ parallelism • Design based on VCGC from Inferno project (ISMM’98) ✦ Allows mutator, marker, sweeper threads to concurrently • Multicore OCaml is MCGC
77. Parallelism — Major GC • OCaml’s GC is incremental, needs to be concurrent w/ parallelism • Design based on VCGC from Inferno project (ISMM’98) ✦ Allows mutator, marker, sweeper threads to concurrently • Multicore OCaml is MCGC ✦ States Garbage Free Unmarked Marked
78. Parallelism — Major GC • OCaml’s GC is incremental, needs to be concurrent w/ parallelism • Design based on VCGC from Inferno project (ISMM’98) ✦ Allows mutator, marker, sweeper threads to concurrently • Multicore OCaml is MCGC ✦ States ✦ Domains alternate between mutator and gc thread Garbage Free Unmarked Marked
79. Parallelism — Major GC • OCaml’s GC is incremental, needs to be concurrent w/ parallelism • Design based on VCGC from Inferno project (ISMM’98) ✦ Allows mutator, marker, sweeper threads to concurrently • Multicore OCaml is MCGC ✦ States ✦ Domains alternate between mutator and gc thread ✦ GC thread Garbage Free Unmarked Marked Garbage Free Unmarked Marked
80. Parallelism — Major GC • OCaml’s GC is incremental, needs to be concurrent w/ parallelism • Design based on VCGC from Inferno project (ISMM’98) ✦ Allows mutator, marker, sweeper threads to concurrently • Multicore OCaml is MCGC ✦ States ✦ Domains alternate between mutator and gc thread ✦ GC thread ✦ Marking is racy but idempotent Garbage Free Unmarked Marked Garbage Free Unmarked Marked
81. Parallelism — Major GC • OCaml’s GC is incremental, needs to be concurrent w/ parallelism • Design based on VCGC from Inferno project (ISMM’98) ✦ Allows mutator, marker, sweeper threads to concurrently • Multicore OCaml is MCGC ✦ States ✦ Domains alternate between mutator and gc thread ✦ GC thread ✦ Marking is racy but idempotent • Stop-the-world Garbage Free Unmarked Marked Garbage Free Unmarked Marked
82. Parallelism — Major GC • OCaml’s GC is incremental, needs to be concurrent w/ parallelism • Design based on VCGC from Inferno project (ISMM’98) ✦ Allows mutator, marker, sweeper threads to concurrently • Multicore OCaml is MCGC ✦ States ✦ Domains alternate between mutator and gc thread ✦ GC thread ✦ Marking is racy but idempotent • Stop-the-world Garbage Free Unmarked Marked Garbage Free Unmarked Marked Garbage Free Unmarked Marked Garbage Free Unmarked Marked
83. • Fibers = stack segment on heap Concurrency — Minor GC
84. • Fibers = stack segment on heap Concurrency — Minor GC minor heap (domain x) major heap current stack registers y x remembered fiber set remembered set
85. • Fibers = stack segment on heap Concurrency — Minor GC minor heap (domain x) major heap current stack registers y x remembered fiber set remembered set • Remembered fiber set ✦ Set of fibers in major heap that were ran in the current cycle of domain x ✦ Cleared after minor GC
86. • Fibers transitively reachable are not promoted automatically ✦ Avoids false promotions Concurrency — Promotions minor heap (domain 0) major heap r x f z
87. Concurrency — Promotions minor heap (domain 0) major heap r x f remembered set z
88. • Fibers transitively reachable are not promoted automatically ✦ Avoids false promotions Concurrency — Promotions minor heap (domain 0) major heap r x f remembered set z
89. • Fibers transitively reachable are not promoted automatically ✦ Avoids false promotions ✦ Promote on continuing foreign fiber Concurrency — Promotions minor heap (domain 0) major heap r x f remembered set continue f v @ domain 1 z
90. • Fibers transitively reachable are not promoted automatically ✦ Avoids false promotions ✦ Promote on continuing foreign fiber Concurrency — Promotions minor heap (domain 0) major heap r x f remembered set continue f v @ domain 1 z
91. Concurrency — Promotions
92. • Recall, promotion fast path = move + scan and forward ✦ Do not scan remembered fiber set ✤ Context switches <<< promotions Concurrency — Promotions
93. • Recall, promotion fast path = move + scan and forward ✦ Do not scan remembered fiber set ✤ Context switches <<< promotions • Scan lazily before context switch ✦ Only once per fiber per promotion Concurrency — Promotions
94. Concurrency — Major GC
95. • (Multicore) OCaml uses deletion barrier Concurrency — Major GC
96. • (Multicore) OCaml uses deletion barrier • Fiber stack pop is a deletion ✦ Before switching to unmarked fiber, complete marking fiber Concurrency — Major GC
97. • (Multicore) OCaml uses deletion barrier • Fiber stack pop is a deletion ✦ Before switching to unmarked fiber, complete marking fiber • Marking is racy but idempotent ✦ Race between mutator (context switch) and gc (marking) unsafe Concurrency — Major GC
98. • (Multicore) OCaml uses deletion barrier • Fiber stack pop is a deletion ✦ Before switching to unmarked fiber, complete marking fiber • Marking is racy but idempotent ✦ Race between mutator (context switch) and gc (marking) unsafe Concurrency — Major GC Unmarked Marked Marking Fibers
99. Summary • Multicore OCaml GC ✦ Optimize for latency ✦ Independent minor GCs + mostly-concurrent mark-and-sweep Mutations Concurrency Parallelism Minor GC rem set rem fiber set local heaps Promotions o2y rem set lazy scanning read faults Major GC deletion barrier mark & switch MCGC
100. Questions?
101. Backup Slides
102. Purely functional GC stack registers heap
103. Purely functional GC stack registers heap • Stop-the-world mark and sweep
104. Purely functional GC stack registers heap 0x0000 0xffff • Stop-the-world mark and sweep
105. Purely functional GC stack registers heap 0x0000 0xffff frontier • Stop-the-world mark and sweep
106. Purely functional GC stack registers heap 0x0000 0xffff frontier • Stop-the-world mark and sweep • 2-pass mark compact ✦ Fast allocations by bumping the frontier
107. Purely functional GC stack registers heap 0x0000 0xffff frontier • Stop-the-world mark and sweep • 2-pass mark compact ✦ Fast allocations by bumping the frontier • All heap pointers go right
108. Purely functional GC stack registers heap 0x0000 0xffff frontier • Mark roots
109. Purely functional GC stack registers heap 0x0000 0xffff frontier • Mark roots • Scan from frontier to start. For each marked object, • Mark reachable object & reverse pointers
110. Purely functional GC stack registers 0x0000 0xffff frontier • Mark roots • Scan from frontier to start. For each marked object, • Mark reachable object & reverse pointers • Scan from start to frontier. For each marked object, • Copy to next available free space & reverse pointers pointing left
111. Purely functional GC stack registers 0x0000 0xffff frontier
112. Purely functional GC stack registers 0x0000 0xffff frontier • Pros ✦ Simple & fast allocation ✦ Efficient use of space
113. Purely functional GC stack registers 0x0000 0xffff frontier • Pros ✦ Simple & fast allocation ✦ Efficient use of space • Cons ✦ Need to touch all the objects on the heap ✦ Compaction as default is leads to long pause times