1// Copyright 2016 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// gccgo-specific support for GC.
6
7package runtime
8
9import (
10	"runtime/internal/sys"
11	"unsafe"
12)
13
14// For gccgo, use go:linkname to export compiler-called functions.
15//
16//go:linkname gcWriteBarrier
17
18// gcRoot is a single GC root: a variable plus a ptrmask.
19//go:notinheap
20type gcRoot struct {
21	decl    unsafe.Pointer // Pointer to variable.
22	size    uintptr        // Size of variable.
23	ptrdata uintptr        // Length of gcdata.
24	gcdata  *uint8         // Pointer mask.
25}
26
27// gcRootList is the set of GC roots for a package.
28// The next field is used to put this all into a linked list.
29// count gives the real length of the array.
30type gcRootList struct {
31	next  *gcRootList
32	count int
33	roots [1 << 26]gcRoot
34}
35
36// roots is the list of GC roots for the program.
37// The compiler keeps this variable itself off the list.
38var gcRoots *gcRootList
39
40// Slice containing pointers to all reachable gcRoot's sorted by
41// starting address (generated at init time from 'gcRoots').
42// The compiler also keeps this variable itself off the list.
43// The storage backing this slice is allocated via persistentalloc(), the
44// idea being that we don't want to treat the slice itself as a global
45// variable, since it points to things that don't need to be scanned
46// themselves.
47var gcRootsIndex []*gcRoot
48
49// rootradixsort performs an in-place radix sort of the 'arr' rootptr slice.
50// Note: not a stable sort, however we expect it to be called only on slices
51// with no duplicate entries, so this should not matter.
52func rootradixsort(arr []*gcRoot, lo, hi int, bit uint) {
53	// Partition the array into two bins based on the values at the
54	// specified bit position: 0's bin (grown from the left) and and
55	// 1's bin (grown from the right). We keep two boundary markers,
56	// the 0's boundary "zbb" (which grows to the right) and the 1's
57	// boundary "obb" (which grows to the left). At each step we
58	// examine the bit for the right-of-ZBB element: if it is zero, we
59	// leave it in place and move the ZBB to the right. If the bit is
60	// not zero, then we swap the ZBB and OBB elements and move the
61	// OBB to the left. When this is done, the two partitions are then
62	// sorted using the next lower bit.
63
64	// 0's bin boundary, initially set to before the first element
65	zbb := lo - 1
66	// 1's bin boundary, set to just beyond the last element
67	obb := hi + 1
68	// mask to pick up bit of interest
69	bmask := uintptr(1) << bit
70
71	for obb-zbb > 1 {
72		zbbval := uintptr(arr[zbb+1].decl) & bmask
73		if zbbval == 0 {
74			// Move zbb one to the right
75			zbb++
76		} else {
77			// Move obb one to the left and swap
78			arr[obb-1], arr[zbb+1] = arr[zbb+1], arr[obb-1]
79			obb--
80		}
81	}
82
83	if bit != 0 {
84		// NB: in most cases there is just a single partition to visit
85		// so if we wanted to reduce stack space we could check for this
86		// and insert a goto back up to the top.
87		if zbb-lo > 0 {
88			rootradixsort(arr, lo, zbb, bit-1)
89		}
90		if hi-obb > 0 {
91			rootradixsort(arr, obb, hi, bit-1)
92		}
93	}
94}
95
96//go:nowritebarrier
97func createGcRootsIndex() {
98	// Count roots
99	nroots := 0
100	gcr := gcRoots
101	for gcr != nil {
102		nroots += gcr.count
103		gcr = gcr.next
104	}
105
106	// Construct the gcRootsIndex slice. Use non-heap storage for the array
107	// backing the slice.
108	sp := (*notInHeapSlice)(unsafe.Pointer(&gcRootsIndex))
109	sp.array = (*notInHeap)(persistentalloc1(sys.PtrSize*uintptr(nroots), sys.PtrSize, &memstats.other_sys))
110	if sp.array == nil {
111		throw("runtime: cannot allocate memory")
112	}
113	sp.len = nroots
114	sp.cap = nroots
115
116	// Populate the roots index slice
117	gcr = gcRoots
118	k := 0
119	for gcr != nil {
120		for i := 0; i < gcr.count; i++ {
121			gcRootsIndex[k] = &gcr.roots[i]
122			k++
123		}
124		gcr = gcr.next
125	}
126
127	// Sort it by starting address.
128	rootradixsort(gcRootsIndex, 0, nroots-1, sys.PtrSize*8-1)
129}
130
131// registerGCRoots is called by compiler-generated code.
132//go:linkname registerGCRoots
133
134// registerGCRoots is called by init functions to register the GC
135// roots for a package.  The init functions are run sequentially at
136// the start of the program, so no locking is needed.
137func registerGCRoots(r *gcRootList) {
138	r.next = gcRoots
139	gcRoots = r
140}
141
142// checkPreempt is called when the preempt field in the running G is true.
143// It preempts the goroutine if it is safe to do so.
144// If preemptscan is true, this scans the stack for the garbage collector
145// and carries on.
146func checkPreempt() {
147	gp := getg()
148	if !gp.preempt || gp != gp.m.curg || !canPreemptM(gp.m) {
149		return
150	}
151
152	if gp.preemptStop {
153		mcall(preemptPark)
154	}
155
156	// Act like goroutine called runtime.Gosched.
157	mcall(gopreempt_m)
158}
159
160// gcWriteBarrier implements a write barrier. This is implemented in
161// assembly in the gc library, but there is no special advantage to
162// doing so with gccgo.
163//go:nosplit
164//go:nowritebarrier
165func gcWriteBarrier(dst *uintptr, src uintptr) {
166	buf := &getg().m.p.ptr().wbBuf
167	if !buf.putFast(src, *dst) {
168		wbBufFlush(dst, src)
169	}
170	*dst = src
171}
172