+section: rts

+synopsis: Correctly mark slop bytes when shrinking large arrays.

+  Heap census no longer traverses garbage-collected closures when profiling

+  is off.

+issues: #19048

+mrs: !15685

+  // threadPaused() can't correctly mark the slop, so we do it here. See #15571

+  // and Note [marking slop when overwriting immutable closures].

+ * Utilities for marking slop callable from Cmm

+void stg_writeSlopMarker (StgWord *slop, StgWord n)

+    writeSlopMarker(slop, n);

+void stg_overwritingClosure (StgClosure *p)

+    overwritingClosure(p);

+ * If check fails, fall back to the conservative code path: just mark the slop

+/* Note [shrink-array slop marker]

+ * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

+ * When shrinkSmallMutableArray# or shrinkMutableByteArray# creates n words of

+ * slop at address `slop_start`, we write an O(1) marker so that the heap

+ * census (heapCensus in ProfHeap.c) and the sanity checker (checkHeapChain in

+ * Sanity.c) can skip over the slop without reading stale heap pointers.

+ *

+ * The marker scheme (let n = number of slop words):

+ *

+ *   n == 0  nothing written (no slop)

+ *   n == 1  slop[0] = 0

+ *   n >= 2  slop[0] = (StgWord)(-1)   -- sentinel (0xFFFF...FFFF)

+ *           slop[1] = n - 2           -- words remaining after the two-word header

+ *

+ * The sentinel value (StgWord)(-1) is safe because info-table pointers always

+ * live in the text segment; 0xFFFF...FFFF is never a valid info pointer.

+ *

+ * An array may be shrunk multiple times, leaving consecutive slop regions.

+ * Traversal code must therefore loop over all slop regions before advancing

+ * to the next live closure.  See the while-loops in heapCensusBlock (ProfHeap.c)

+ * and checkHeapChain (Sanity.c).

+ */

+

+       /* fall-back: not at end of nursery block; write slop marker.

+          See Note [shrink-array slop marker] */

+       W_ n;

+       n = old_wds - new_wds;

+       foreign "C" stg_writeSlopMarker(mba + WDS(new_wds) "ptr", n);

+   /* Write slop marker. See Note [shrink-array slop marker] */

+   W_ old_size_sma, n_sma, slop_start;

+   old_size_sma = StgSmallMutArrPtrs_ptrs(mba);

+   n_sma = old_size_sma - new_size;

+   slop_start = mba + SIZEOF_StgSmallMutArrPtrs + WDS(new_size);

+   foreign "C" stg_writeSlopMarker(slop_start "ptr", n_sma);

+

+   // No ordering needed: the concurrent mark thread bounds the slop with the

+   // marker's own release/acquire (Note [Slop marker memory ordering]), not

+   // with this store, and reading the new size it never scans the slop.

+                        // skip over marked slop; loop because an array

+                        // may have been shrunk multiple times.

+                        // See Note [shrink-array slop marker] in PrimOps.cmm.

+                        while (r < bd->free) {

+                            if (!*r) {

+                                r++;

+                            } else if (*r == (StgWord)(-1)) {

+                                StgWord skip = *(r + 1);

+                                r += 2 + skip;

+                            } else {

+                                break;

+                            }

+                        }

+        /* skip over slop (zero words from large/pinned objects, or

+           shrink-array slop markers); loop because an array may have been

+           shrunk multiple times, leaving consecutive slop regions.

+           See Note [slop on the heap] and Note [shrink-array slop marker]

+           in PrimOps.cmm.

+

+           Note [skipping slop in the heap profiler]

+           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

+           Slop left behind after major GC comes in two forms:

+

+            1. Zero words: alignment padding for large/pinned objects.

+               We zero these explicitly (see MEMSET_SLOP_W in allocatePinned).

+

+            2. Shrink-array slop markers: written by stg_shrinkMutableByteArrayzh

+               and stg_shrinkSmallMutableArrayzh in all build modes.  A single-word

+               slop region is represented as a zero word; a multi-word region begins

+               with the sentinel (StgWord)(-1) followed by a count of additional

+               words.  See Note [shrink-array slop marker] in PrimOps.cmm.

+

+           Because an array can be shrunk multiple times, we loop until we

+           see a word that looks like a valid info pointer. */

+        while (p < bd->free) {

+            if (!*p) {

+                p++;

+            } else if (*p == (StgWord)(-1)) {

+                StgWord skip = *(p + 1);

+                p += 2 + skip;

+            } else {

+                break;

+            }

+        }

+    // we mark slop of blackhole'd thunks, which doesn't happen in the

+                // mark the slop so that the sanity checker can tell

+   Note [marking slop when overwriting immutable closures]

+   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

+   When we overwrite a closure in the heap with a smaller one, we need to mark

+   the "slop" -- the memory that is left unoccupied -- so that the heap can be

+   linearly scanned. See Note [slop on the heap]

+   For mutable closures (e.g. shrinking arrays), slop is always marked

+   unconditionally via writeSlopMarker, in all build modes.

+   See Note [shrink-array slop marker] in PrimOps.cmm.

+

+   For immutable closures (e.g. thunks overwritten with indirections), slop

+   marking is only needed for:

+    - LDV profiling (PROFILING, and +RTS -hb)

+   However we can get into trouble if we're marking slop for immutable closures

+   when using multiple threads, since there is nothing preventing another thread

+   from still being in the process of reading the memory we're about to

+   overwrite.

+   Thus, with the THREADED RTS and +RTS -N2 or greater we must not mark

+   may race with a mutator during slop marking. Consequently, we also disable

+   marking of immutable closures when the non-moving GC is in use.

+   Hence, an immutable closure's slop is marked when either:

+// Note [Slop marker memory ordering]

+// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

+// The non-moving GC mark thread reads SmallMutArrPtrs payload elements

+// concurrently with the mutator, which may shrink the array via

+// stg_shrinkSmallMutableArrayzh.  Shrinking writes a slop marker over the

+// vacated elements (see Note [shrink-array slop marker] in PrimOps.cmm):

+//

+//   n == 1:  slop[0] = 0

+//   n >= 2:  slop[0] = -1   (sentinel)

+//            slop[1] = n-2  (count of further slop words)

+//

+// The mark thread reads elements with ACQUIRE_LOAD and, at each position i>0,

+// re-reads element i-1 after reading i to detect a concurrently written -1

+// sentinel (see rts/sm/NonMovingMark.c).  For this check to be sound the

+// store of -1 to slop[0] must be visible to the reader when it observes the

+// skip count at slop[1].  This is guaranteed by the release-acquire pairing:

+// the RELEASE_STORE of n-2 to slop[1] ensures that the prior RELAXED_STORE

+// of -1 to slop[0] is visible to any thread that performs an ACQUIRE_LOAD of

+// slop[1] and sees the skip count.

+//

+// The re-read of element i-1 is only performed when the value c just read at

+// position i could plausibly be a skip count, i.e. when (StgWord)c < n-i

+// (a skip count at position i must satisfy i + skip <= n-1, so skip < n-i).

+// Values at or above that bound are valid closure pointers, so no re-read is

+// needed.  In practice closure pointers are word-aligned kernel addresses and

+// far exceed any plausible skip count, so this eliminates virtually all of

+// the redundant re-reads.

+//

+// The non-moving GC only runs in the threaded RTS, where RELEASE_STORE and

+// ACQUIRE_LOAD are both __atomic_* operations.  The _ALWAYS variants are not

+// needed here.

+INLINE_HEADER void writeSlopMarker(StgWord *slop, StgWord n)

+{

+    // See Note [Slop marker memory ordering]

+    if (n == 1) {

+        RELAXED_STORE(&slop[0], (StgWord)0);

+    } else if (n >= 2) {

+        RELAXED_STORE(&slop[0], (StgWord)(-1));

+        RELEASE_STORE(&slop[1], n - 2);

+    }

+}

+

+markImmutableSlop (StgClosure *p,

+          uint32_t offset,    /*< offset to start marking at, in words */

+          uint32_t size       /*< total closure size, in words */

+    // see Note [marking slop when overwriting immutable closures], also #8402

+    const bool want_to_mark = false

+    const bool can_mark =

+    if(!(want_to_mark && can_mark))

+    // Write a slop marker so that the heap profiler and sanity checker can skip

+    // over the slop without reading stale heap pointers.

+    // See Note [shrink-array slop marker] in PrimOps.cmm for the encoding.

+    writeSlopMarker((StgWord *)p + offset, size - offset);

+void stg_writeSlopMarker (StgWord *slop, StgWord n);

+    markImmutableSlop(p, sizeofW(StgThunkHeader), size);

+    markImmutableSlop(p, sizeofW(StgThunkHeader), size);

+                 MarkSlop.c

+        StgWord n = arr->ptrs;

+        if (n == 0) break;

+

+        for (StgWord i = 0; i < n; i++) {

+            StgClosure *c = ACQUIRE_LOAD(&arr->payload[i]);

+            // If NULL or -1, we know the rest is slop

+            if (c == NULL || c == (StgClosure *)(-1)) break;

+            // A valid skip count at position i must satisfy

+            //   i + skip <= n-1  (sentinel at i-1, count at i, skip more words)

+            // i.e. skip < n-i.  If c is out of that range it cannot be a skip

+            // count, so we must have read a valid closure pointer.

+            bool maybe_slop_count = (StgWord)c < n - i;

+            if (maybe_slop_count && i != 0) {

+                // Otherwise re-read the previous element: the mutator may have

+                // written -1 there after we last saw it, making the current

+                // word the skip count rather than a valid closure pointer.

+                //

+                // The ACQUIRE_LOAD of payload[i] above synchronizes with the

+                // RELEASE_STORE in writeSlopMarker, so a RELAXED_LOAD suffices

+                // here; see Note [Slop marker memory ordering] in

+                // rts/include/rts/storage/ClosureMacros.h.

+                if (RELAXED_LOAD(&arr->payload[i-1]) == (StgClosure *)(-1)) break;

+            }

+

+            // Track origin so indirections reached through array elements get

+            // short-cut (see Note [Origin references in the nonmoving

+            // collector] in NonMovingMark.h), but only when c cannot be a skip

+            // count, i.e. c >= n-i.

+            // The collapse rewrites the cell with a CAS that fires only if it

+            // still holds c; restricting to c >= n-i guarantees c differs from

+            // any skip count the mutator could write at this cell while

+            // concurrently shrinking the array, so the CAS can never clobber a

+            // slop marker. Real heap addresses are far above n, so in practice

+            // every element is still short-cut.

+            StgClosure **origin = maybe_slop_count ? NULL : &arr->payload[i];

+            markQueuePushClosure(queue, c, origin);

+                /* skip slop; loop because an array may have been shrunk

+                   multiple times.  See Note [slop on the heap] in Storage.c

+                   and Note [shrink-array slop marker] in PrimOps.cmm. */

+                while (p < bd->free) {

+                    if (!*p) {

+                        p++;

+                    } else if (*p == (StgWord)(-1)) {

+                        StgWord skip = *(p + 1);

+                        p += 2 + skip;

+                    } else {

+                        break;

+                    }

+                }

+    //   * We can't mark the slop. However, we can sanity-check the heap after a

+    //     [marking slop when overwriting immutable closures].

+ *   overwritten. See Note [marking slop when overwriting immutable closures].

+ * To allow the heap profiler and sanity checker to linearly scan over heap

+ * blocks, slop must be identifiable without reading stale heap pointers.

+ * See Note [skipping slop in the heap profiler]

+ * Shrunk-array slop has a further, concurrent reader: the non-moving GC mark

+ * thread scans SmallMutArrPtrs payloads while the mutator may be shrinking

+ * them, so it must identify the slop with the right memory ordering. See Note

+ * [Slop marker memory ordering] in ClosureMacros.h.

+ * For pinned/large-object alignment slop we use explicit zeroing:

+ * For shrunk-array slop we write an O(1) marker in all build modes.

+ * See Note [shrink-array slop marker] in PrimOps.cmm for the encoding.

+ * This replaces the old approach of zeroing the entire slop region, which was a

+ * no-op in vanilla (non-profiling, non-debug) builds and caused heap-census

+ * crashes (#19048, #17572, #9666).

+ * When performing LDV profiling or using a (single threaded) debug RTS we mark

+ * slop even when overwriting immutable closures, see Note [marking slop when

+ * overwriting immutable closures].

+{-# LANGUAGE MagicHash, UnboxedTuples, BlockArguments #-}

+module Main where

+

+import GHC.Exts

+import GHC.ST   (ST(..), runST)

+import System.Mem (performMajorGC)

+

+-- Lifted wrapper so SmallArray# can appear in non-unlifted positions.

+data SmallArr a = SmallArr (SmallArray# a)

+

+main :: IO ()

+main = do

+  let arr = buildArr

+  let n = case arr of SmallArr a -> I# (sizeofSmallArray# a)

+  putStrLn $ "size after shrink = " ++ show n

+  -- With +RTS -hT -i0 this triggers heapCensus.

+  -- The census advances past the 10 live elements, then hits the 490

+  -- stale heap pointers in the slop and crashes.

+  performMajorGC

+  -- Keep arr alive across the GC by reading from it after.

+  let v = case arr of SmallArr a -> case indexSmallArray# a 0# of (# x #) -> x

+  putStrLn $ "arr[0] = " ++ show (v :: Integer)

+  putStrLn "survived"

+

+-- Allocate 500 slots, write a DISTINCT Integer to every slot, then

+-- shrink to 10.  Slots [10..499] become slop: they still hold live,

+-- non-zero heap pointers in the raw memory, but the ptrs header field

+-- says there are only 10 elements.  zeroSlop is a no-op in non-PROFILING

+-- builds (even when -hT is active), so the slop is never cleared.

+buildArr :: SmallArr Integer

+buildArr = runST $ ST \s0 ->

+  -- All 500 slots start with a non-null initial value.

+  case newSmallArray# 500# (0 :: Integer) s0 of { (# s1, ma #) ->

+  -- Overwrite every slot with a distinct Integer so each holds a

+  -- unique heap pointer (no sharing, definitely non-zero).

+  case fill 499 ma s1 of { s2 ->

+  -- Shrink: ptrs = 10, but physical slots [10..499] are NOT zeroed.

+  case shrinkSmallMutableArray# ma 10# s2 of { s3 ->

+  case unsafeFreezeSmallArray# ma s3 of { (# s4, a #) ->

+  (# s4, SmallArr a #) }}}}

+

+-- Fill slots [0..n] each with a distinct Integer value (n, n-1, ..., 0).

+-- 'Integer' guarantees a genuine heap object for every value.

+fill :: Int -> SmallMutableArray# s Integer -> State# s -> State# s

+fill 0 ma s = writeSmallArray# ma 0# (0 :: Integer) s

+fill n ma s =

+  let I# n# = n

+  in case writeSmallArray# ma n# (fromIntegral n :: Integer) s of

+       s' -> fill (n - 1) ma s'

+size after shrink = 10

+arr[0] = 0

+survived

+

+test('T19048',

+     [ omit_ghci

+     , no_check_hp

+     , js_skip

+     , extra_run_opts('+RTS -hT -i0 -RTS')

+     ],

+     compile_and_run, ['-O -rtsopts'])