1// Copyright 2020 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5// GC checkmarks
6//
7// In a concurrent garbage collector, one worries about failing to mark
8// a live object due to mutations without write barriers or bugs in the
9// collector implementation. As a sanity check, the GC has a 'checkmark'
10// mode that retraverses the object graph with the world stopped, to make
11// sure that everything that should be marked is marked.
12
13package runtime
14
15import (
16	"internal/goarch"
17	"internal/runtime/atomic"
18	"runtime/internal/sys"
19	"unsafe"
20)
21
22// A checkmarksMap stores the GC marks in "checkmarks" mode. It is a
23// per-arena bitmap with a bit for every word in the arena. The mark
24// is stored on the bit corresponding to the first word of the marked
25// allocation.
26type checkmarksMap struct {
27	_ sys.NotInHeap
28	b [heapArenaBytes / goarch.PtrSize / 8]uint8
29}
30
31// If useCheckmark is true, marking of an object uses the checkmark
32// bits instead of the standard mark bits.
33var useCheckmark = false
34
35// startCheckmarks prepares for the checkmarks phase.
36//
37// The world must be stopped.
38func startCheckmarks() {
39	assertWorldStopped()
40
41	// Clear all checkmarks.
42	for _, ai := range mheap_.allArenas {
43		arena := mheap_.arenas[ai.l1()][ai.l2()]
44		bitmap := arena.checkmarks
45
46		if bitmap == nil {
47			// Allocate bitmap on first use.
48			bitmap = (*checkmarksMap)(persistentalloc(unsafe.Sizeof(*bitmap), 0, &memstats.gcMiscSys))
49			if bitmap == nil {
50				throw("out of memory allocating checkmarks bitmap")
51			}
52			arena.checkmarks = bitmap
53		} else {
54			// Otherwise clear the existing bitmap.
55			clear(bitmap.b[:])
56		}
57	}
58	// Enable checkmarking.
59	useCheckmark = true
60}
61
62// endCheckmarks ends the checkmarks phase.
63func endCheckmarks() {
64	if gcMarkWorkAvailable(nil) {
65		throw("GC work not flushed")
66	}
67	useCheckmark = false
68}
69
70// setCheckmark throws if marking object is a checkmarks violation,
71// and otherwise sets obj's checkmark. It returns true if obj was
72// already checkmarked.
73func setCheckmark(obj, base, off uintptr, mbits markBits) bool {
74	if !mbits.isMarked() {
75		printlock()
76		print("runtime: checkmarks found unexpected unmarked object obj=", hex(obj), "\n")
77		print("runtime: found obj at *(", hex(base), "+", hex(off), ")\n")
78
79		// Dump the source (base) object
80		gcDumpObject("base", base, off)
81
82		// Dump the object
83		gcDumpObject("obj", obj, ^uintptr(0))
84
85		getg().m.traceback = 2
86		throw("checkmark found unmarked object")
87	}
88
89	ai := arenaIndex(obj)
90	arena := mheap_.arenas[ai.l1()][ai.l2()]
91	arenaWord := (obj / heapArenaBytes / 8) % uintptr(len(arena.checkmarks.b))
92	mask := byte(1 << ((obj / heapArenaBytes) % 8))
93	bytep := &arena.checkmarks.b[arenaWord]
94
95	if atomic.Load8(bytep)&mask != 0 {
96		// Already checkmarked.
97		return true
98	}
99
100	atomic.Or8(bytep, mask)
101	return false
102}
103