Source file src/runtime/mgclarge.go

Documentation: runtime

     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.
     4  
     5  // Page heap.
     6  //
     7  // See malloc.go for the general overview.
     8  //
     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  // https://faculty.washington.edu/aragon/pubs/rst89.pdf for an overview.
    13  // sema.go also holds an implementation of a treap.
    14  //
    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
    17  // is done.
    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.
    20  //
    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
    25  //
    26  // _mheap.lock must be held when manipulating this data structure.
    27  
    28  package runtime
    29  
    30  import (
    31  	"unsafe"
    32  )
    33  
    34  //go:notinheap
    35  type mTreap struct {
    36  	treap *treapNode
    37  }
    38  
    39  //go:notinheap
    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 to keep tree probabilistically balanced
    47  }
    48  
    49  func (t *treapNode) pred() *treapNode {
    50  	if t.left != nil {
    51  		// If it has a left child, its predecessor will be
    52  		// its right most left (grand)child.
    53  		t = t.left
    54  		for t.right != nil {
    55  			t = t.right
    56  		}
    57  		return t
    58  	}
    59  	// If it has no left child, its predecessor will be
    60  	// the first grandparent who's right child is its
    61  	// ancestor.
    62  	//
    63  	// We compute this by walking up the treap until the
    64  	// current node's parent is its parent's right child.
    65  	//
    66  	// If we find at any point walking up the treap
    67  	// that the current node doesn't have a parent,
    68  	// we've hit the root. This means that t is already
    69  	// the left-most node in the treap and therefore
    70  	// has no predecessor.
    71  	for t.parent != nil && t.parent.right != t {
    72  		if t.parent.left != t {
    73  			println("runtime: predecessor t=", t, "t.spanKey=", t.spanKey)
    74  			throw("node is not its parent's child")
    75  		}
    76  		t = t.parent
    77  	}
    78  	return t.parent
    79  }
    80  
    81  func (t *treapNode) succ() *treapNode {
    82  	if t.right != nil {
    83  		// If it has a right child, its successor will be
    84  		// its left-most right (grand)child.
    85  		t = t.right
    86  		for t.left != nil {
    87  			t = t.left
    88  		}
    89  		return t
    90  	}
    91  	// See pred.
    92  	for t.parent != nil && t.parent.left != t {
    93  		if t.parent.right != t {
    94  			println("runtime: predecessor t=", t, "t.spanKey=", t.spanKey)
    95  			throw("node is not its parent's child")
    96  		}
    97  		t = t.parent
    98  	}
    99  	return t.parent
   100  }
   101  
   102  // isSpanInTreap is handy for debugging. One should hold the heap lock, usually
   103  // mheap_.lock().
   104  func (t *treapNode) isSpanInTreap(s *mspan) bool {
   105  	if t == nil {
   106  		return false
   107  	}
   108  	return t.spanKey == s || t.left.isSpanInTreap(s) || t.right.isSpanInTreap(s)
   109  }
   110  
   111  // walkTreap is handy for debugging.
   112  // Starting at some treapnode t, for example the root, do a depth first preorder walk of
   113  // the tree executing fn at each treap node. One should hold the heap lock, usually
   114  // mheap_.lock().
   115  func (t *treapNode) walkTreap(fn func(tn *treapNode)) {
   116  	if t == nil {
   117  		return
   118  	}
   119  	fn(t)
   120  	t.left.walkTreap(fn)
   121  	t.right.walkTreap(fn)
   122  }
   123  
   124  // checkTreapNode when used in conjunction with walkTreap can usually detect a
   125  // poorly formed treap.
   126  func checkTreapNode(t *treapNode) {
   127  	// lessThan is used to order the treap.
   128  	// npagesKey and npages are the primary keys.
   129  	// spanKey and span are the secondary keys.
   130  	// span == nil (0) will always be lessThan all
   131  	// spans of the same size.
   132  	lessThan := func(npages uintptr, s *mspan) bool {
   133  		if t.npagesKey != npages {
   134  			return t.npagesKey < npages
   135  		}
   136  		// t.npagesKey == npages
   137  		return t.spanKey.base() < s.base()
   138  	}
   139  
   140  	if t == nil {
   141  		return
   142  	}
   143  	if t.spanKey.next != nil || t.spanKey.prev != nil || t.spanKey.list != nil {
   144  		throw("span may be on an mSpanList while simultaneously in the treap")
   145  	}
   146  	if t.spanKey.npages != t.npagesKey {
   147  		println("runtime: checkTreapNode treapNode t=", t, "     t.npagesKey=", t.npagesKey,
   148  			"t.spanKey.npages=", t.spanKey.npages)
   149  		throw("span.npages and treap.npagesKey do not match")
   150  	}
   151  	if t.left != nil && lessThan(t.left.npagesKey, t.left.spanKey) {
   152  		throw("t.lessThan(t.left.npagesKey, t.left.spanKey) is not false")
   153  	}
   154  	if t.right != nil && !lessThan(t.right.npagesKey, t.right.spanKey) {
   155  		throw("!t.lessThan(t.left.npagesKey, t.left.spanKey) is not false")
   156  	}
   157  }
   158  
   159  // treapIter is a bidirectional iterator type which may be used to iterate over a
   160  // an mTreap in-order forwards (increasing order) or backwards (decreasing order).
   161  // Its purpose is to hide details about the treap from users when trying to iterate
   162  // over it.
   163  //
   164  // To create iterators over the treap, call start or end on an mTreap.
   165  type treapIter struct {
   166  	t *treapNode
   167  }
   168  
   169  // span returns the span at the current position in the treap.
   170  // If the treap is not valid, span will panic.
   171  func (i *treapIter) span() *mspan {
   172  	return i.t.spanKey
   173  }
   174  
   175  // valid returns whether the iterator represents a valid position
   176  // in the mTreap.
   177  func (i *treapIter) valid() bool {
   178  	return i.t != nil
   179  }
   180  
   181  // next moves the iterator forward by one. Once the iterator
   182  // ceases to be valid, calling next will panic.
   183  func (i treapIter) next() treapIter {
   184  	i.t = i.t.succ()
   185  	return i
   186  }
   187  
   188  // prev moves the iterator backwards by one. Once the iterator
   189  // ceases to be valid, calling prev will panic.
   190  func (i treapIter) prev() treapIter {
   191  	i.t = i.t.pred()
   192  	return i
   193  }
   194  
   195  // start returns an iterator which points to the start of the treap (the
   196  // left-most node in the treap).
   197  func (root *mTreap) start() treapIter {
   198  	t := root.treap
   199  	if t == nil {
   200  		return treapIter{}
   201  	}
   202  	for t.left != nil {
   203  		t = t.left
   204  	}
   205  	return treapIter{t: t}
   206  }
   207  
   208  // end returns an iterator which points to the end of the treap (the
   209  // right-most node in the treap).
   210  func (root *mTreap) end() treapIter {
   211  	t := root.treap
   212  	if t == nil {
   213  		return treapIter{}
   214  	}
   215  	for t.right != nil {
   216  		t = t.right
   217  	}
   218  	return treapIter{t: t}
   219  }
   220  
   221  // insert adds span to the large span treap.
   222  func (root *mTreap) insert(span *mspan) {
   223  	npages := span.npages
   224  	var last *treapNode
   225  	pt := &root.treap
   226  	for t := *pt; t != nil; t = *pt {
   227  		last = t
   228  		if t.npagesKey < npages {
   229  			pt = &t.right
   230  		} else if t.npagesKey > npages {
   231  			pt = &t.left
   232  		} else if t.spanKey.base() < span.base() {
   233  			// t.npagesKey == npages, so sort on span addresses.
   234  			pt = &t.right
   235  		} else if t.spanKey.base() > span.base() {
   236  			pt = &t.left
   237  		} else {
   238  			throw("inserting span already in treap")
   239  		}
   240  	}
   241  
   242  	// Add t as new leaf in tree of span size and unique addrs.
   243  	// The balanced tree is a treap using priority as the random heap priority.
   244  	// That is, it is a binary tree ordered according to the npagesKey,
   245  	// but then among the space of possible binary trees respecting those
   246  	// npagesKeys, it is kept balanced on average by maintaining a heap ordering
   247  	// on the priority: s.priority <= both s.right.priority and s.right.priority.
   248  	// https://en.wikipedia.org/wiki/Treap
   249  	// https://faculty.washington.edu/aragon/pubs/rst89.pdf
   250  
   251  	t := (*treapNode)(mheap_.treapalloc.alloc())
   252  	t.npagesKey = span.npages
   253  	t.priority = fastrand()
   254  	t.spanKey = span
   255  	t.parent = last
   256  	*pt = t // t now at a leaf.
   257  	// Rotate up into tree according to priority.
   258  	for t.parent != nil && t.parent.priority > t.priority {
   259  		if t != nil && t.spanKey.npages != t.npagesKey {
   260  			println("runtime: insert t=", t, "t.npagesKey=", t.npagesKey)
   261  			println("runtime:      t.spanKey=", t.spanKey, "t.spanKey.npages=", t.spanKey.npages)
   262  			throw("span and treap sizes do not match?")
   263  		}
   264  		if t.parent.left == t {
   265  			root.rotateRight(t.parent)
   266  		} else {
   267  			if t.parent.right != t {
   268  				throw("treap insert finds a broken treap")
   269  			}
   270  			root.rotateLeft(t.parent)
   271  		}
   272  	}
   273  }
   274  
   275  func (root *mTreap) removeNode(t *treapNode) {
   276  	if t.spanKey.npages != t.npagesKey {
   277  		throw("span and treap node npages do not match")
   278  	}
   279  	// Rotate t down to be leaf of tree for removal, respecting priorities.
   280  	for t.right != nil || t.left != nil {
   281  		if t.right == nil || t.left != nil && t.left.priority < t.right.priority {
   282  			root.rotateRight(t)
   283  		} else {
   284  			root.rotateLeft(t)
   285  		}
   286  	}
   287  	// Remove t, now a leaf.
   288  	if t.parent != nil {
   289  		if t.parent.left == t {
   290  			t.parent.left = nil
   291  		} else {
   292  			t.parent.right = nil
   293  		}
   294  	} else {
   295  		root.treap = nil
   296  	}
   297  	// Return the found treapNode's span after freeing the treapNode.
   298  	mheap_.treapalloc.free(unsafe.Pointer(t))
   299  }
   300  
   301  // find searches for, finds, and returns the treap node containing the
   302  // smallest span that can hold npages. If no span has at least npages
   303  // it returns nil.
   304  // This is a simple binary tree search that tracks the best-fit node found
   305  // so far. The best-fit node is guaranteed to be on the path to a
   306  // (maybe non-existent) lowest-base exact match.
   307  func (root *mTreap) find(npages uintptr) *treapNode {
   308  	var best *treapNode
   309  	t := root.treap
   310  	for t != nil {
   311  		if t.spanKey == nil {
   312  			throw("treap node with nil spanKey found")
   313  		}
   314  		// If we found an exact match, try to go left anyway. There could be
   315  		// a span there with a lower base address.
   316  		//
   317  		// Don't bother checking nil-ness of left and right here; even if t
   318  		// becomes nil, we already know the other path had nothing better for
   319  		// us anyway.
   320  		if t.npagesKey >= npages {
   321  			best = t
   322  			t = t.left
   323  		} else {
   324  			t = t.right
   325  		}
   326  	}
   327  	return best
   328  }
   329  
   330  // removeSpan searches for, finds, deletes span along with
   331  // the associated treap node. If the span is not in the treap
   332  // then t will eventually be set to nil and the t.spanKey
   333  // will throw.
   334  func (root *mTreap) removeSpan(span *mspan) {
   335  	npages := span.npages
   336  	t := root.treap
   337  	for t.spanKey != span {
   338  		if t.npagesKey < npages {
   339  			t = t.right
   340  		} else if t.npagesKey > npages {
   341  			t = t.left
   342  		} else if t.spanKey.base() < span.base() {
   343  			t = t.right
   344  		} else if t.spanKey.base() > span.base() {
   345  			t = t.left
   346  		}
   347  	}
   348  	root.removeNode(t)
   349  }
   350  
   351  // erase removes the element referred to by the current position of the
   352  // iterator. This operation consumes the given iterator, so it should no
   353  // longer be used. It is up to the caller to get the next or previous
   354  // iterator before calling erase, if need be.
   355  func (root *mTreap) erase(i treapIter) {
   356  	root.removeNode(i.t)
   357  }
   358  
   359  // rotateLeft rotates the tree rooted at node x.
   360  // turning (x a (y b c)) into (y (x a b) c).
   361  func (root *mTreap) rotateLeft(x *treapNode) {
   362  	// p -> (x a (y b c))
   363  	p := x.parent
   364  	a, y := x.left, x.right
   365  	b, c := y.left, y.right
   366  
   367  	y.left = x
   368  	x.parent = y
   369  	y.right = c
   370  	if c != nil {
   371  		c.parent = y
   372  	}
   373  	x.left = a
   374  	if a != nil {
   375  		a.parent = x
   376  	}
   377  	x.right = b
   378  	if b != nil {
   379  		b.parent = x
   380  	}
   381  
   382  	y.parent = p
   383  	if p == nil {
   384  		root.treap = y
   385  	} else if p.left == x {
   386  		p.left = y
   387  	} else {
   388  		if p.right != x {
   389  			throw("large span treap rotateLeft")
   390  		}
   391  		p.right = y
   392  	}
   393  }
   394  
   395  // rotateRight rotates the tree rooted at node y.
   396  // turning (y (x a b) c) into (x a (y b c)).
   397  func (root *mTreap) rotateRight(y *treapNode) {
   398  	// p -> (y (x a b) c)
   399  	p := y.parent
   400  	x, c := y.left, y.right
   401  	a, b := x.left, x.right
   402  
   403  	x.left = a
   404  	if a != nil {
   405  		a.parent = x
   406  	}
   407  	x.right = y
   408  	y.parent = x
   409  	y.left = b
   410  	if b != nil {
   411  		b.parent = y
   412  	}
   413  	y.right = c
   414  	if c != nil {
   415  		c.parent = y
   416  	}
   417  
   418  	x.parent = p
   419  	if p == nil {
   420  		root.treap = x
   421  	} else if p.left == y {
   422  		p.left = x
   423  	} else {
   424  		if p.right != y {
   425  			throw("large span treap rotateRight")
   426  		}
   427  		p.right = x
   428  	}
   429  }
   430  

View as plain text