1 // Copyright 2009 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.
7 // See malloc.go for the general overview.
9 // Large spans are the subject of this file. Spans consisting of less than
10 // _MaxMHeapLists are held in lists of like sized spans. Larger spans
11 // are held in a treap. See https://en.wikipedia.org/wiki/Treap or
12 // http://faculty.washington.edu/aragon/pubs/rst89.pdf for an overview.
13 // sema.go also holds an implementation of a treap.
15 // Each treapNode holds a single span. The treap is sorted by page size
16 // and for spans of the same size a secondary sort based on start address
18 // Spans are returned based on a best fit algorithm and for spans of the same
19 // size the one at the lowest address is selected.
21 // The primary routines are
22 // insert: adds a span to the treap
23 // remove: removes the span from that treap that best fits the required size
24 // removeSpan: which removes a specific span from the treap
26 // _mheap.lock must be held when manipulating this data structure.
40 type treapNode
struct {
41 right
*treapNode
// all treapNodes > this treap node
42 left
*treapNode
// all treapNodes < this treap node
43 parent
*treapNode
// direct parent of this node, nil if root
44 npagesKey
uintptr // number of pages in spanKey, used as primary sort key
45 spanKey
*mspan
// span of size npagesKey, used as secondary sort key
46 priority
uint32 // random number used by treap algorithm keep tree probablistically balanced
49 func (t
*treapNode
) init() {
58 // isSpanInTreap is handy for debugging. One should hold the heap lock, usually
60 func (t
*treapNode
) isSpanInTreap(s
*mspan
) bool {
64 return t
.spanKey
== s || t
.left
.isSpanInTreap(s
) || t
.right
.isSpanInTreap(s
)
67 // walkTreap is handy for debugging.
68 // Starting at some treapnode t, for example the root, do a depth first preorder walk of
69 // the tree executing fn at each treap node. One should hold the heap lock, usually
71 func (t
*treapNode
) walkTreap(fn
func(tn
*treapNode
)) {
80 // checkTreapNode when used in conjunction with walkTreap can usually detect a
81 // poorly formed treap.
82 func checkTreapNode(t
*treapNode
) {
83 // lessThan is used to order the treap.
84 // npagesKey and npages are the primary keys.
85 // spanKey and span are the secondary keys.
86 // span == nil (0) will always be lessThan all
87 // spans of the same size.
88 lessThan
:= func(npages
uintptr, s
*mspan
) bool {
89 if t
.npagesKey
!= npages
{
90 return t
.npagesKey
< npages
92 // t.npagesKey == npages
93 return uintptr(unsafe
.Pointer(t
.spanKey
)) < uintptr(unsafe
.Pointer(s
))
99 if t
.spanKey
.npages
!= t
.npagesKey || t
.spanKey
.next
!= nil {
100 println("runtime: checkTreapNode treapNode t=", t
, " t.npagesKey=", t
.npagesKey
,
101 "t.spanKey.npages=", t
.spanKey
.npages
)
102 throw("why does span.npages and treap.ngagesKey do not match?")
104 if t
.left
!= nil && lessThan(t
.left
.npagesKey
, t
.left
.spanKey
) {
105 throw("t.lessThan(t.left.npagesKey, t.left.spanKey) is not false")
107 if t
.right
!= nil && !lessThan(t
.right
.npagesKey
, t
.right
.spanKey
) {
108 throw("!t.lessThan(t.left.npagesKey, t.left.spanKey) is not false")
112 // insert adds span to the large span treap.
113 func (root
*mTreap
) insert(span
*mspan
) {
114 npages
:= span
.npages
117 for t
:= *pt
; t
!= nil; t
= *pt
{
119 if t
.npagesKey
< npages
{
121 } else if t
.npagesKey
> npages
{
123 } else if uintptr(unsafe
.Pointer(t
.spanKey
)) < uintptr(unsafe
.Pointer(span
)) {
124 // t.npagesKey == npages, so sort on span addresses.
126 } else if uintptr(unsafe
.Pointer(t
.spanKey
)) > uintptr(unsafe
.Pointer(span
)) {
129 throw("inserting span already in treap")
133 // Add t as new leaf in tree of span size and unique addrs.
134 // The balanced tree is a treap using priority as the random heap priority.
135 // That is, it is a binary tree ordered according to the npagesKey,
136 // but then among the space of possible binary trees respecting those
137 // npagesKeys, it is kept balanced on average by maintaining a heap ordering
138 // on the priority: s.priority <= both s.right.priority and s.right.priority.
139 // https://en.wikipedia.org/wiki/Treap
140 // http://faculty.washington.edu/aragon/pubs/rst89.pdf
142 t
:= (*treapNode
)(mheap_
.treapalloc
.alloc())
144 t
.npagesKey
= span
.npages
145 t
.priority
= fastrand()
148 *pt
= t
// t now at a leaf.
149 // Rotate up into tree according to priority.
150 for t
.parent
!= nil && t
.parent
.priority
> t
.priority
{
151 if t
!= nil && t
.spanKey
.npages
!= t
.npagesKey
{
152 println("runtime: insert t=", t
, "t.npagesKey=", t
.npagesKey
)
153 println("runtime: t.spanKey=", t
.spanKey
, "t.spanKey.npages=", t
.spanKey
.npages
)
154 throw("span and treap sizes do not match?")
156 if t
.parent
.left
== t
{
157 root
.rotateRight(t
.parent
)
159 if t
.parent
.right
!= t
{
160 throw("treap insert finds a broken treap")
162 root
.rotateLeft(t
.parent
)
167 func (root
*mTreap
) removeNode(t
*treapNode
) *mspan
{
168 if t
.spanKey
.npages
!= t
.npagesKey
{
169 throw("span and treap node npages do not match")
173 // Rotate t down to be leaf of tree for removal, respecting priorities.
174 for t
.right
!= nil || t
.left
!= nil {
175 if t
.right
== nil || t
.left
!= nil && t
.left
.priority
< t
.right
.priority
{
181 // Remove t, now a leaf.
183 if t
.parent
.left
== t
{
191 // Return the found treapNode's span after freeing the treapNode.
194 mheap_
.treapalloc
.free(unsafe
.Pointer(t
))
198 // remove searches for, finds, removes from the treap, and returns the smallest
199 // span that can hold npages. If no span has at least npages return nil.
200 // This is slightly more complicated than a simple binary tree search
201 // since if an exact match is not found the next larger node is
203 // If the last node inspected > npagesKey not holding
204 // a left node (a smaller npages) is the "best fit" node.
205 func (root
*mTreap
) remove(npages
uintptr) *mspan
{
208 if t
.spanKey
== nil {
209 throw("treap node with nil spanKey found")
211 if t
.npagesKey
< npages
{
213 } else if t
.left
!= nil && t
.left
.npagesKey
>= npages
{
224 // removeSpan searches for, finds, deletes span along with
225 // the associated treap node. If the span is not in the treap
226 // then t will eventually be set to nil and the t.spanKey
228 func (root
*mTreap
) removeSpan(span
*mspan
) {
229 npages
:= span
.npages
231 for t
.spanKey
!= span
{
232 if t
.npagesKey
< npages
{
234 } else if t
.npagesKey
> npages
{
236 } else if uintptr(unsafe
.Pointer(t
.spanKey
)) < uintptr(unsafe
.Pointer(span
)) {
238 } else if uintptr(unsafe
.Pointer(t
.spanKey
)) > uintptr(unsafe
.Pointer(span
)) {
245 // scavengetreap visits each node in the treap and scavenges the
247 func scavengetreap(treap
*treapNode
, now
, limit
uint64) uintptr {
251 return scavengeTreapNode(treap
, now
, limit
) +
252 scavengetreap(treap
.left
, now
, limit
) +
253 scavengetreap(treap
.right
, now
, limit
)
256 // rotateLeft rotates the tree rooted at node x.
257 // turning (x a (y b c)) into (y (x a b) c).
258 func (root
*mTreap
) rotateLeft(x
*treapNode
) {
259 // p -> (x a (y b c))
261 a
, y
:= x
.left
, x
.right
262 b
, c
:= y
.left
, y
.right
282 } else if p
.left
== x
{
286 throw("large span treap rotateLeft")
292 // rotateRight rotates the tree rooted at node y.
293 // turning (y (x a b) c) into (x a (y b c)).
294 func (root
*mTreap
) rotateRight(y
*treapNode
) {
295 // p -> (y (x a b) c)
297 x
, c
:= y
.left
, y
.right
298 a
, b
:= x
.left
, x
.right
318 } else if p
.left
== y
{
322 throw("large span treap rotateRight")