...
Run Format

Source file src/runtime/mgclarge.go

Documentation: runtime

  // 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
  	}
  }
  

View as plain text