...
Run Format

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 uintptr(unsafe.Pointer(t.spanKey)) < uintptr(unsafe.Pointer(s))
   138  	}
   139  
   140  	if t == nil {
   141  		return
   142  	}
   143  	if t.spanKey.npages != t.npagesKey || t.spanKey.next != nil {
   144  		println("runtime: checkTreapNode treapNode t=", t, "     t.npagesKey=", t.npagesKey,
   145  			"t.spanKey.npages=", t.spanKey.npages)
   146  		throw("why does span.npages and treap.ngagesKey do not match?")
   147  	}
   148  	if t.left != nil && lessThan(t.left.npagesKey, t.left.spanKey) {
   149  		throw("t.lessThan(t.left.npagesKey, t.left.spanKey) is not false")
   150  	}
   151  	if t.right != nil && !lessThan(t.right.npagesKey, t.right.spanKey) {
   152  		throw("!t.lessThan(t.left.npagesKey, t.left.spanKey) is not false")
   153  	}
   154  }
   155  
   156  // treapIter is a bidirectional iterator type which may be used to iterate over a
   157  // an mTreap in-order forwards (increasing order) or backwards (decreasing order).
   158  // Its purpose is to hide details about the treap from users when trying to iterate
   159  // over it.
   160  //
   161  // To create iterators over the treap, call start or end on an mTreap.
   162  type treapIter struct {
   163  	t *treapNode
   164  }
   165  
   166  // span returns the span at the current position in the treap.
   167  // If the treap is not valid, span will panic.
   168  func (i *treapIter) span() *mspan {
   169  	return i.t.spanKey
   170  }
   171  
   172  // valid returns whether the iterator represents a valid position
   173  // in the mTreap.
   174  func (i *treapIter) valid() bool {
   175  	return i.t != nil
   176  }
   177  
   178  // next moves the iterator forward by one. Once the iterator
   179  // ceases to be valid, calling next will panic.
   180  func (i treapIter) next() treapIter {
   181  	i.t = i.t.succ()
   182  	return i
   183  }
   184  
   185  // prev moves the iterator backwards by one. Once the iterator
   186  // ceases to be valid, calling prev will panic.
   187  func (i treapIter) prev() treapIter {
   188  	i.t = i.t.pred()
   189  	return i
   190  }
   191  
   192  // start returns an iterator which points to the start of the treap (the
   193  // left-most node in the treap).
   194  func (root *mTreap) start() treapIter {
   195  	t := root.treap
   196  	if t == nil {
   197  		return treapIter{}
   198  	}
   199  	for t.left != nil {
   200  		t = t.left
   201  	}
   202  	return treapIter{t: t}
   203  }
   204  
   205  // end returns an iterator which points to the end of the treap (the
   206  // right-most node in the treap).
   207  func (root *mTreap) end() treapIter {
   208  	t := root.treap
   209  	if t == nil {
   210  		return treapIter{}
   211  	}
   212  	for t.right != nil {
   213  		t = t.right
   214  	}
   215  	return treapIter{t: t}
   216  }
   217  
   218  // insert adds span to the large span treap.
   219  func (root *mTreap) insert(span *mspan) {
   220  	npages := span.npages
   221  	var last *treapNode
   222  	pt := &root.treap
   223  	for t := *pt; t != nil; t = *pt {
   224  		last = t
   225  		if t.npagesKey < npages {
   226  			pt = &t.right
   227  		} else if t.npagesKey > npages {
   228  			pt = &t.left
   229  		} else if t.spanKey.base() < span.base() {
   230  			// t.npagesKey == npages, so sort on span addresses.
   231  			pt = &t.right
   232  		} else if t.spanKey.base() > span.base() {
   233  			pt = &t.left
   234  		} else {
   235  			throw("inserting span already in treap")
   236  		}
   237  	}
   238  
   239  	// Add t as new leaf in tree of span size and unique addrs.
   240  	// The balanced tree is a treap using priority as the random heap priority.
   241  	// That is, it is a binary tree ordered according to the npagesKey,
   242  	// but then among the space of possible binary trees respecting those
   243  	// npagesKeys, it is kept balanced on average by maintaining a heap ordering
   244  	// on the priority: s.priority <= both s.right.priority and s.right.priority.
   245  	// https://en.wikipedia.org/wiki/Treap
   246  	// https://faculty.washington.edu/aragon/pubs/rst89.pdf
   247  
   248  	t := (*treapNode)(mheap_.treapalloc.alloc())
   249  	t.npagesKey = span.npages
   250  	t.priority = fastrand()
   251  	t.spanKey = span
   252  	t.parent = last
   253  	*pt = t // t now at a leaf.
   254  	// Rotate up into tree according to priority.
   255  	for t.parent != nil && t.parent.priority > t.priority {
   256  		if t != nil && t.spanKey.npages != t.npagesKey {
   257  			println("runtime: insert t=", t, "t.npagesKey=", t.npagesKey)
   258  			println("runtime:      t.spanKey=", t.spanKey, "t.spanKey.npages=", t.spanKey.npages)
   259  			throw("span and treap sizes do not match?")
   260  		}
   261  		if t.parent.left == t {
   262  			root.rotateRight(t.parent)
   263  		} else {
   264  			if t.parent.right != t {
   265  				throw("treap insert finds a broken treap")
   266  			}
   267  			root.rotateLeft(t.parent)
   268  		}
   269  	}
   270  }
   271  
   272  func (root *mTreap) removeNode(t *treapNode) {
   273  	if t.spanKey.npages != t.npagesKey {
   274  		throw("span and treap node npages do not match")
   275  	}
   276  	// Rotate t down to be leaf of tree for removal, respecting priorities.
   277  	for t.right != nil || t.left != nil {
   278  		if t.right == nil || t.left != nil && t.left.priority < t.right.priority {
   279  			root.rotateRight(t)
   280  		} else {
   281  			root.rotateLeft(t)
   282  		}
   283  	}
   284  	// Remove t, now a leaf.
   285  	if t.parent != nil {
   286  		if t.parent.left == t {
   287  			t.parent.left = nil
   288  		} else {
   289  			t.parent.right = nil
   290  		}
   291  	} else {
   292  		root.treap = nil
   293  	}
   294  	// Return the found treapNode's span after freeing the treapNode.
   295  	mheap_.treapalloc.free(unsafe.Pointer(t))
   296  }
   297  
   298  // find searches for, finds, and returns the treap node containing the
   299  // smallest span that can hold npages. If no span has at least npages
   300  // it returns nil.
   301  // This is slightly more complicated than a simple binary tree search
   302  // since if an exact match is not found the next larger node is
   303  // returned.
   304  func (root *mTreap) find(npages uintptr) *treapNode {
   305  	t := root.treap
   306  	for t != nil {
   307  		if t.spanKey == nil {
   308  			throw("treap node with nil spanKey found")
   309  		}
   310  		if t.npagesKey < npages {
   311  			t = t.right
   312  		} else if t.left != nil && t.left.npagesKey >= npages {
   313  			t = t.left
   314  		} else {
   315  			return t
   316  		}
   317  	}
   318  	return nil
   319  }
   320  
   321  // removeSpan searches for, finds, deletes span along with
   322  // the associated treap node. If the span is not in the treap
   323  // then t will eventually be set to nil and the t.spanKey
   324  // will throw.
   325  func (root *mTreap) removeSpan(span *mspan) {
   326  	npages := span.npages
   327  	t := root.treap
   328  	for t.spanKey != span {
   329  		if t.npagesKey < npages {
   330  			t = t.right
   331  		} else if t.npagesKey > npages {
   332  			t = t.left
   333  		} else if t.spanKey.base() < span.base() {
   334  			t = t.right
   335  		} else if t.spanKey.base() > span.base() {
   336  			t = t.left
   337  		}
   338  	}
   339  	root.removeNode(t)
   340  }
   341  
   342  // erase removes the element referred to by the current position of the
   343  // iterator. This operation consumes the given iterator, so it should no
   344  // longer be used. It is up to the caller to get the next or previous
   345  // iterator before calling erase, if need be.
   346  func (root *mTreap) erase(i treapIter) {
   347  	root.removeNode(i.t)
   348  }
   349  
   350  // rotateLeft rotates the tree rooted at node x.
   351  // turning (x a (y b c)) into (y (x a b) c).
   352  func (root *mTreap) rotateLeft(x *treapNode) {
   353  	// p -> (x a (y b c))
   354  	p := x.parent
   355  	a, y := x.left, x.right
   356  	b, c := y.left, y.right
   357  
   358  	y.left = x
   359  	x.parent = y
   360  	y.right = c
   361  	if c != nil {
   362  		c.parent = y
   363  	}
   364  	x.left = a
   365  	if a != nil {
   366  		a.parent = x
   367  	}
   368  	x.right = b
   369  	if b != nil {
   370  		b.parent = x
   371  	}
   372  
   373  	y.parent = p
   374  	if p == nil {
   375  		root.treap = y
   376  	} else if p.left == x {
   377  		p.left = y
   378  	} else {
   379  		if p.right != x {
   380  			throw("large span treap rotateLeft")
   381  		}
   382  		p.right = y
   383  	}
   384  }
   385  
   386  // rotateRight rotates the tree rooted at node y.
   387  // turning (y (x a b) c) into (x a (y b c)).
   388  func (root *mTreap) rotateRight(y *treapNode) {
   389  	// p -> (y (x a b) c)
   390  	p := y.parent
   391  	x, c := y.left, y.right
   392  	a, b := x.left, x.right
   393  
   394  	x.left = a
   395  	if a != nil {
   396  		a.parent = x
   397  	}
   398  	x.right = y
   399  	y.parent = x
   400  	y.left = b
   401  	if b != nil {
   402  		b.parent = y
   403  	}
   404  	y.right = c
   405  	if c != nil {
   406  		c.parent = y
   407  	}
   408  
   409  	x.parent = p
   410  	if p == nil {
   411  		root.treap = x
   412  	} else if p.left == y {
   413  		p.left = x
   414  	} else {
   415  		if p.right != y {
   416  			throw("large span treap rotateRight")
   417  		}
   418  		p.right = x
   419  	}
   420  }
   421  

View as plain text