summaryrefslogtreecommitdiff
path: root/src/runtime/mcentral.go
blob: ae5c6f1d54e2b35a426d7d4840aafd0d4caf3a06 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Central free lists.
//
// See malloc.h for an overview.
//
// The MCentral doesn't actually contain the list of free objects; the MSpan does.
// Each MCentral is two lists of MSpans: those with free objects (c->nonempty)
// and those that are completely allocated (c->empty).

package runtime

import "unsafe"

// Initialize a single central free list.
func mCentral_Init(c *mcentral, sizeclass int32) {
	c.sizeclass = sizeclass
	mSpanList_Init(&c.nonempty)
	mSpanList_Init(&c.empty)
}

// Allocate a span to use in an MCache.
func mCentral_CacheSpan(c *mcentral) *mspan {
	lock(&c.lock)
	sg := mheap_.sweepgen
retry:
	var s *mspan
	for s = c.nonempty.next; s != &c.nonempty; s = s.next {
		if s.sweepgen == sg-2 && cas(&s.sweepgen, sg-2, sg-1) {
			mSpanList_Remove(s)
			mSpanList_InsertBack(&c.empty, s)
			unlock(&c.lock)
			mSpan_Sweep(s, true)
			goto havespan
		}
		if s.sweepgen == sg-1 {
			// the span is being swept by background sweeper, skip
			continue
		}
		// we have a nonempty span that does not require sweeping, allocate from it
		mSpanList_Remove(s)
		mSpanList_InsertBack(&c.empty, s)
		unlock(&c.lock)
		goto havespan
	}

	for s = c.empty.next; s != &c.empty; s = s.next {
		if s.sweepgen == sg-2 && cas(&s.sweepgen, sg-2, sg-1) {
			// we have an empty span that requires sweeping,
			// sweep it and see if we can free some space in it
			mSpanList_Remove(s)
			// swept spans are at the end of the list
			mSpanList_InsertBack(&c.empty, s)
			unlock(&c.lock)
			mSpan_Sweep(s, true)
			if s.freelist.ptr() != nil {
				goto havespan
			}
			lock(&c.lock)
			// the span is still empty after sweep
			// it is already in the empty list, so just retry
			goto retry
		}
		if s.sweepgen == sg-1 {
			// the span is being swept by background sweeper, skip
			continue
		}
		// already swept empty span,
		// all subsequent ones must also be either swept or in process of sweeping
		break
	}
	unlock(&c.lock)

	// Replenish central list if empty.
	s = mCentral_Grow(c)
	if s == nil {
		return nil
	}
	lock(&c.lock)
	mSpanList_InsertBack(&c.empty, s)
	unlock(&c.lock)

	// At this point s is a non-empty span, queued at the end of the empty list,
	// c is unlocked.
havespan:
	cap := int32((s.npages << _PageShift) / s.elemsize)
	n := cap - int32(s.ref)
	if n == 0 {
		gothrow("empty span")
	}
	if s.freelist.ptr() == nil {
		gothrow("freelist empty")
	}
	s.incache = true
	return s
}

// Return span from an MCache.
func mCentral_UncacheSpan(c *mcentral, s *mspan) {
	lock(&c.lock)

	s.incache = false

	if s.ref == 0 {
		gothrow("uncaching full span")
	}

	cap := int32((s.npages << _PageShift) / s.elemsize)
	n := cap - int32(s.ref)
	if n > 0 {
		mSpanList_Remove(s)
		mSpanList_Insert(&c.nonempty, s)
	}
	unlock(&c.lock)
}

// Free n objects from a span s back into the central free list c.
// Called during sweep.
// Returns true if the span was returned to heap.  Sets sweepgen to
// the latest generation.
// If preserve=true, don't return the span to heap nor relink in MCentral lists;
// caller takes care of it.
func mCentral_FreeSpan(c *mcentral, s *mspan, n int32, start gclinkptr, end gclinkptr, preserve bool) bool {
	if s.incache {
		gothrow("freespan into cached span")
	}

	// Add the objects back to s's free list.
	wasempty := s.freelist.ptr() == nil
	end.ptr().next = s.freelist
	s.freelist = start
	s.ref -= uint16(n)

	if preserve {
		// preserve is set only when called from MCentral_CacheSpan above,
		// the span must be in the empty list.
		if s.next == nil {
			gothrow("can't preserve unlinked span")
		}
		atomicstore(&s.sweepgen, mheap_.sweepgen)
		return false
	}

	lock(&c.lock)

	// Move to nonempty if necessary.
	if wasempty {
		mSpanList_Remove(s)
		mSpanList_Insert(&c.nonempty, s)
	}

	// delay updating sweepgen until here.  This is the signal that
	// the span may be used in an MCache, so it must come after the
	// linked list operations above (actually, just after the
	// lock of c above.)
	atomicstore(&s.sweepgen, mheap_.sweepgen)

	if s.ref != 0 {
		unlock(&c.lock)
		return false
	}

	// s is completely freed, return it to the heap.
	mSpanList_Remove(s)
	s.needzero = 1
	s.freelist = 0
	unlock(&c.lock)
	unmarkspan(uintptr(s.start)<<_PageShift, s.npages<<_PageShift)
	mHeap_Free(&mheap_, s, 0)
	return true
}

// Fetch a new span from the heap and carve into objects for the free list.
func mCentral_Grow(c *mcentral) *mspan {
	npages := uintptr(class_to_allocnpages[c.sizeclass])
	size := uintptr(class_to_size[c.sizeclass])
	n := (npages << _PageShift) / size

	s := mHeap_Alloc(&mheap_, npages, c.sizeclass, false, true)
	if s == nil {
		return nil
	}

	p := uintptr(s.start << _PageShift)
	s.limit = p + size*n
	head := gclinkptr(p)
	tail := gclinkptr(p)
	// i==0 iteration already done
	for i := uintptr(1); i < n; i++ {
		p += size
		tail.ptr().next = gclinkptr(p)
		tail = gclinkptr(p)
	}
	if s.freelist.ptr() != nil {
		gothrow("freelist not empty")
	}
	tail.ptr().next = 0
	s.freelist = head
	markspan(unsafe.Pointer(uintptr(s.start)<<_PageShift), size, n, size*n < s.npages<<_PageShift)
	return s
}