diff options
Diffstat (limited to 'libgo/go/runtime/mgclarge.go')
| -rw-r--r-- | libgo/go/runtime/mgclarge.go | 326 |
1 files changed, 326 insertions, 0 deletions
diff --git a/libgo/go/runtime/mgclarge.go b/libgo/go/runtime/mgclarge.go new file mode 100644 index 0000000..757e88d --- /dev/null +++ b/libgo/go/runtime/mgclarge.go @@ -0,0 +1,326 @@ +// 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. + +// Page heap. +// +// See malloc.go for the general overview. +// +// Large spans are the subject of this file. Spans consisting of less than +// _MaxMHeapLists are held in lists of like sized spans. Larger spans +// are held in a treap. See https://en.wikipedia.org/wiki/Treap or +// http://faculty.washington.edu/aragon/pubs/rst89.pdf for an overview. +// sema.go also holds an implementation of a treap. +// +// Each treapNode holds a single span. The treap is sorted by page size +// and for spans of the same size a secondary sort based on start address +// is done. +// Spans are returned based on a best fit algorithm and for spans of the same +// size the one at the lowest address is selected. +// +// The primary routines are +// insert: adds a span to the treap +// remove: removes the span from that treap that best fits the required size +// removeSpan: which removes a specific span from the treap +// +// _mheap.lock must be held when manipulating this data structure. + +package runtime + +import ( + "unsafe" +) + +//go:notinheap +type mTreap struct { + treap *treapNode +} + +//go:notinheap +type treapNode struct { + right *treapNode // all treapNodes > this treap node + left *treapNode // all treapNodes < this treap node + parent *treapNode // direct parent of this node, nil if root + npagesKey uintptr // number of pages in spanKey, used as primary sort key + spanKey *mspan // span of size npagesKey, used as secondary sort key + priority uint32 // random number used by treap algorithm keep tree probablistically balanced +} + +func (t *treapNode) init() { + t.right = nil + t.left = nil + t.parent = nil + t.spanKey = nil + t.npagesKey = 0 + t.priority = 0 +} + +// isSpanInTreap is handy for debugging. One should hold the heap lock, usually +// mheap_.lock(). +func (t *treapNode) isSpanInTreap(s *mspan) bool { + if t == nil { + return false + } + return t.spanKey == s || t.left.isSpanInTreap(s) || t.right.isSpanInTreap(s) +} + +// walkTreap is handy for debugging. +// Starting at some treapnode t, for example the root, do a depth first preorder walk of +// the tree executing fn at each treap node. One should hold the heap lock, usually +// mheap_.lock(). +func (t *treapNode) walkTreap(fn func(tn *treapNode)) { + if t == nil { + return + } + fn(t) + t.left.walkTreap(fn) + t.right.walkTreap(fn) +} + +// checkTreapNode when used in conjunction with walkTreap can usually detect a +// poorly formed treap. +func checkTreapNode(t *treapNode) { + // lessThan is used to order the treap. + // npagesKey and npages are the primary keys. + // spanKey and span are the secondary keys. + // span == nil (0) will always be lessThan all + // spans of the same size. + lessThan := func(npages uintptr, s *mspan) bool { + if t.npagesKey != npages { + return t.npagesKey < npages + } + // t.npagesKey == npages + return uintptr(unsafe.Pointer(t.spanKey)) < uintptr(unsafe.Pointer(s)) + } + + if t == nil { + return + } + if t.spanKey.npages != t.npagesKey || t.spanKey.next != nil { + println("runtime: checkTreapNode treapNode t=", t, " t.npagesKey=", t.npagesKey, + "t.spanKey.npages=", t.spanKey.npages) + throw("why does span.npages and treap.ngagesKey do not match?") + } + if t.left != nil && lessThan(t.left.npagesKey, t.left.spanKey) { + throw("t.lessThan(t.left.npagesKey, t.left.spanKey) is not false") + } + if t.right != nil && !lessThan(t.right.npagesKey, t.right.spanKey) { + throw("!t.lessThan(t.left.npagesKey, t.left.spanKey) is not false") + } +} + +// insert adds span to the large span treap. +func (root *mTreap) insert(span *mspan) { + npages := span.npages + var last *treapNode + pt := &root.treap + for t := *pt; t != nil; t = *pt { + last = t + if t.npagesKey < npages { + pt = &t.right + } else if t.npagesKey > npages { + pt = &t.left + } else if uintptr(unsafe.Pointer(t.spanKey)) < uintptr(unsafe.Pointer(span)) { + // t.npagesKey == npages, so sort on span addresses. + pt = &t.right + } else if uintptr(unsafe.Pointer(t.spanKey)) > uintptr(unsafe.Pointer(span)) { + pt = &t.left + } else { + throw("inserting span already in treap") + } + } + + // Add t as new leaf in tree of span size and unique addrs. + // The balanced tree is a treap using priority as the random heap priority. + // That is, it is a binary tree ordered according to the npagesKey, + // but then among the space of possible binary trees respecting those + // npagesKeys, it is kept balanced on average by maintaining a heap ordering + // on the priority: s.priority <= both s.right.priority and s.right.priority. + // https://en.wikipedia.org/wiki/Treap + // http://faculty.washington.edu/aragon/pubs/rst89.pdf + + t := (*treapNode)(mheap_.treapalloc.alloc()) + t.init() + t.npagesKey = span.npages + t.priority = fastrand() + t.spanKey = span + t.parent = last + *pt = t // t now at a leaf. + // Rotate up into tree according to priority. + for t.parent != nil && t.parent.priority > t.priority { + if t != nil && t.spanKey.npages != t.npagesKey { + println("runtime: insert t=", t, "t.npagesKey=", t.npagesKey) + println("runtime: t.spanKey=", t.spanKey, "t.spanKey.npages=", t.spanKey.npages) + throw("span and treap sizes do not match?") + } + if t.parent.left == t { + root.rotateRight(t.parent) + } else { + if t.parent.right != t { + throw("treap insert finds a broken treap") + } + root.rotateLeft(t.parent) + } + } +} + +func (root *mTreap) removeNode(t *treapNode) *mspan { + if t.spanKey.npages != t.npagesKey { + throw("span and treap node npages do not match") + } + result := t.spanKey + + // Rotate t down to be leaf of tree for removal, respecting priorities. + for t.right != nil || t.left != nil { + if t.right == nil || t.left != nil && t.left.priority < t.right.priority { + root.rotateRight(t) + } else { + root.rotateLeft(t) + } + } + // Remove t, now a leaf. + if t.parent != nil { + if t.parent.left == t { + t.parent.left = nil + } else { + t.parent.right = nil + } + } else { + root.treap = nil + } + // Return the found treapNode's span after freeing the treapNode. + t.spanKey = nil + t.npagesKey = 0 + mheap_.treapalloc.free(unsafe.Pointer(t)) + return result +} + +// remove searches for, finds, removes from the treap, and returns the smallest +// span that can hold npages. If no span has at least npages return nil. +// This is slightly more complicated than a simple binary tree search +// since if an exact match is not found the next larger node is +// returned. +// If the last node inspected > npagesKey not holding +// a left node (a smaller npages) is the "best fit" node. +func (root *mTreap) remove(npages uintptr) *mspan { + t := root.treap + for t != nil { + if t.spanKey == nil { + throw("treap node with nil spanKey found") + } + if t.npagesKey < npages { + t = t.right + } else if t.left != nil && t.left.npagesKey >= npages { + t = t.left + } else { + result := t.spanKey + root.removeNode(t) + return result + } + } + return nil +} + +// removeSpan searches for, finds, deletes span along with +// the associated treap node. If the span is not in the treap +// then t will eventually be set to nil and the t.spanKey +// will throw. +func (root *mTreap) removeSpan(span *mspan) { + npages := span.npages + t := root.treap + for t.spanKey != span { + if t.npagesKey < npages { + t = t.right + } else if t.npagesKey > npages { + t = t.left + } else if uintptr(unsafe.Pointer(t.spanKey)) < uintptr(unsafe.Pointer(span)) { + t = t.right + } else if uintptr(unsafe.Pointer(t.spanKey)) > uintptr(unsafe.Pointer(span)) { + t = t.left + } + } + root.removeNode(t) +} + +// scavengetreap visits each node in the treap and scavenges the +// treapNode's span. +func scavengetreap(treap *treapNode, now, limit uint64) uintptr { + if treap == nil { + return 0 + } + return scavengeTreapNode(treap, now, limit) + + scavengetreap(treap.left, now, limit) + + scavengetreap(treap.right, now, limit) +} + +// rotateLeft rotates the tree rooted at node x. +// turning (x a (y b c)) into (y (x a b) c). +func (root *mTreap) rotateLeft(x *treapNode) { + // p -> (x a (y b c)) + p := x.parent + a, y := x.left, x.right + b, c := y.left, y.right + + y.left = x + x.parent = y + y.right = c + if c != nil { + c.parent = y + } + x.left = a + if a != nil { + a.parent = x + } + x.right = b + if b != nil { + b.parent = x + } + + y.parent = p + if p == nil { + root.treap = y + } else if p.left == x { + p.left = y + } else { + if p.right != x { + throw("large span treap rotateLeft") + } + p.right = y + } +} + +// rotateRight rotates the tree rooted at node y. +// turning (y (x a b) c) into (x a (y b c)). +func (root *mTreap) rotateRight(y *treapNode) { + // p -> (y (x a b) c) + p := y.parent + x, c := y.left, y.right + a, b := x.left, x.right + + x.left = a + if a != nil { + a.parent = x + } + x.right = y + y.parent = x + y.left = b + if b != nil { + b.parent = y + } + y.right = c + if c != nil { + c.parent = y + } + + x.parent = p + if p == nil { + root.treap = x + } else if p.left == y { + p.left = x + } else { + if p.right != y { + throw("large span treap rotateRight") + } + p.right = x + } +} |