From 68e0647f432f9d79ae13a23f614ef293bfd297a9 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?=C3=96mer=20Sinan=20A=C4=9Facan?= Date: Tue, 5 Feb 2019 00:18:44 -0500 Subject: rts: Non-concurrent mark and sweep This implements the core heap structure and a serial mark/sweep collector which can be used to manage the oldest-generation heap. This is the first step towards a concurrent mark-and-sweep collector aimed at low-latency applications. The full design of the collector implemented here is described in detail in a technical note B. Gamari. "A Concurrent Garbage Collector For the Glasgow Haskell Compiler" (2018) The basic heap structure used in this design is heavily inspired by K. Ueno & A. Ohori. "A fully concurrent garbage collector for functional programs on multicore processors." /ACM SIGPLAN Notices/ Vol. 51. No. 9 (presented by ICFP 2016) This design is intended to allow both marking and sweeping concurrent to execution of a multi-core mutator. Unlike the Ueno design, which requires no global synchronization pauses, the collector introduced here requires a stop-the-world pause at the beginning and end of the mark phase. To avoid heap fragmentation, the allocator consists of a number of fixed-size /sub-allocators/. Each of these sub-allocators allocators into its own set of /segments/, themselves allocated from the block allocator. Each segment is broken into a set of fixed-size allocation blocks (which back allocations) in addition to a bitmap (used to track the liveness of blocks) and some additional metadata (used also used to track liveness). This heap structure enables collection via mark-and-sweep, which can be performed concurrently via a snapshot-at-the-beginning scheme (although concurrent collection is not implemented in this patch). The mark queue is a fairly straightforward chunked-array structure. The representation is a bit more verbose than a typical mark queue to accomodate a combination of two features: * a mark FIFO, which improves the locality of marking, reducing one of the major overheads seen in mark/sweep allocators (see [1] for details) * the selector optimization and indirection shortcutting, which requires that we track where we found each reference to an object in case we need to update the reference at a later point (e.g. when we find that it is an indirection). See Note [Origin references in the nonmoving collector] (in `NonMovingMark.h`) for details. Beyond this the mark/sweep is fairly run-of-the-mill. [1] R. Garner, S.M. Blackburn, D. Frampton. "Effective Prefetch for Mark-Sweep Garbage Collection." ISMM 2007. Co-Authored-By: Ben Gamari --- rts/sm/GCAux.c | 8 ++++++++ 1 file changed, 8 insertions(+) (limited to 'rts/sm/GCAux.c') diff --git a/rts/sm/GCAux.c b/rts/sm/GCAux.c index 650dc2c1df..6076f61d6f 100644 --- a/rts/sm/GCAux.c +++ b/rts/sm/GCAux.c @@ -60,6 +60,14 @@ isAlive(StgClosure *p) // ignore closures in generations that we're not collecting. bd = Bdescr((P_)q); + // isAlive is used when scavenging moving generations, before the mark + // phase. Because we don't know alive-ness of objects before the mark phase + // we have to conservatively treat objects in the non-moving generation as + // alive here. + if (bd->flags & BF_NONMOVING) { + return p; + } + // if it's a pointer into to-space, then we're done if (bd->flags & BF_EVACUATED) { return p; -- cgit v1.2.1 From 13dd78ddb158f98b35ad2eda50d0a7af63920ece Mon Sep 17 00:00:00 2001 From: Ben Gamari Date: Thu, 18 Apr 2019 14:08:32 -0400 Subject: Nonmoving: Allow aging and refactor static objects logic This commit does two things: * Allow aging of objects during the preparatory minor GC * Refactor handling of static objects to avoid the use of a hashtable --- rts/sm/GCAux.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'rts/sm/GCAux.c') diff --git a/rts/sm/GCAux.c b/rts/sm/GCAux.c index 6076f61d6f..11080c1f22 100644 --- a/rts/sm/GCAux.c +++ b/rts/sm/GCAux.c @@ -148,14 +148,14 @@ markCAFs (evac_fn evac, void *user) StgIndStatic *c; for (c = dyn_caf_list; - c != (StgIndStatic*)END_OF_CAF_LIST; + ((StgWord) c | STATIC_FLAG_LIST) != (StgWord)END_OF_CAF_LIST; c = (StgIndStatic *)c->static_link) { c = (StgIndStatic *)UNTAG_STATIC_LIST_PTR(c); evac(user, &c->indirectee); } for (c = revertible_caf_list; - c != (StgIndStatic*)END_OF_CAF_LIST; + ((StgWord) c | STATIC_FLAG_LIST) != (StgWord)END_OF_CAF_LIST; c = (StgIndStatic *)c->static_link) { c = (StgIndStatic *)UNTAG_STATIC_LIST_PTR(c); -- cgit v1.2.1