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  // Allocation policy is the subject of this file. All free spans live in
    10  // a treap for most of their time being free. See
    11  // 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 base address
    16  // and each span necessarily has a unique base address.
    17  // Spans are returned based on a first-fit algorithm, acquiring the span
    18  // with the lowest base address which still satisfies the request.
    19  //
    20  // The first-fit algorithm is possible due to an augmentation of each
    21  // treapNode to maintain the size of the largest span in the subtree rooted
    22  // at that treapNode. Below we refer to this invariant as the maxPages
    23  // invariant.
    24  //
    25  // The primary routines are
    26  // insert: adds a span to the treap
    27  // remove: removes the span from that treap that best fits the required size
    28  // removeSpan: which removes a specific span from the treap
    29  //
    30  // Whenever a pointer to a span which is owned by the treap is acquired, that
    31  // span must not be mutated. To mutate a span in the treap, remove it first.
    32  //
    33  // mheap_.lock must be held when manipulating this data structure.
    34  
    35  package runtime
    36  
    37  import (
    38  	"unsafe"
    39  )
    40  
    41  //go:notinheap
    42  type mTreap struct {
    43  	treap           *treapNode
    44  	unscavHugePages uintptr // number of unscavenged huge pages in the treap
    45  }
    46  
    47  //go:notinheap
    48  type treapNode struct {
    49  	right    *treapNode      // all treapNodes > this treap node
    50  	left     *treapNode      // all treapNodes < this treap node
    51  	parent   *treapNode      // direct parent of this node, nil if root
    52  	key      uintptr         // base address of the span, used as primary sort key
    53  	span     *mspan          // span at base address key
    54  	maxPages uintptr         // the maximum size of any span in this subtree, including the root
    55  	priority uint32          // random number used by treap algorithm to keep tree probabilistically balanced
    56  	types    treapIterFilter // the types of spans available in this subtree
    57  }
    58  
    59  // updateInvariants is a helper method which has a node recompute its own
    60  // maxPages and types values by looking at its own span as well as the
    61  // values of its direct children.
    62  //
    63  // Returns true if anything changed.
    64  func (t *treapNode) updateInvariants() bool {
    65  	m, i := t.maxPages, t.types
    66  	t.maxPages = t.span.npages
    67  	t.types = t.span.treapFilter()
    68  	if t.left != nil {
    69  		t.types |= t.left.types
    70  		if t.maxPages < t.left.maxPages {
    71  			t.maxPages = t.left.maxPages
    72  		}
    73  	}
    74  	if t.right != nil {
    75  		t.types |= t.right.types
    76  		if t.maxPages < t.right.maxPages {
    77  			t.maxPages = t.right.maxPages
    78  		}
    79  	}
    80  	return m != t.maxPages || i != t.types
    81  }
    82  
    83  // findMinimal finds the minimal (lowest base addressed) node in the treap
    84  // which matches the criteria set out by the filter f and returns nil if
    85  // none exists.
    86  //
    87  // This algorithm is functionally the same as (*mTreap).find, so see that
    88  // method for more details.
    89  func (t *treapNode) findMinimal(f treapIterFilter) *treapNode {
    90  	if t == nil || !f.matches(t.types) {
    91  		return nil
    92  	}
    93  	for t != nil {
    94  		if t.left != nil && f.matches(t.left.types) {
    95  			t = t.left
    96  		} else if f.matches(t.span.treapFilter()) {
    97  			break
    98  		} else if t.right != nil && f.matches(t.right.types) {
    99  			t = t.right
   100  		} else {
   101  			println("runtime: f=", f)
   102  			throw("failed to find minimal node matching filter")
   103  		}
   104  	}
   105  	return t
   106  }
   107  
   108  // findMaximal finds the maximal (highest base addressed) node in the treap
   109  // which matches the criteria set out by the filter f and returns nil if
   110  // none exists.
   111  //
   112  // This algorithm is the logical inversion of findMinimal and just changes
   113  // the order of the left and right tests.
   114  func (t *treapNode) findMaximal(f treapIterFilter) *treapNode {
   115  	if t == nil || !f.matches(t.types) {
   116  		return nil
   117  	}
   118  	for t != nil {
   119  		if t.right != nil && f.matches(t.right.types) {
   120  			t = t.right
   121  		} else if f.matches(t.span.treapFilter()) {
   122  			break
   123  		} else if t.left != nil && f.matches(t.left.types) {
   124  			t = t.left
   125  		} else {
   126  			println("runtime: f=", f)
   127  			throw("failed to find minimal node matching filter")
   128  		}
   129  	}
   130  	return t
   131  }
   132  
   133  // pred returns the predecessor of t in the treap subject to the criteria
   134  // specified by the filter f. Returns nil if no such predecessor exists.
   135  func (t *treapNode) pred(f treapIterFilter) *treapNode {
   136  	if t.left != nil && f.matches(t.left.types) {
   137  		// The node has a left subtree which contains at least one matching
   138  		// node, find the maximal matching node in that subtree.
   139  		return t.left.findMaximal(f)
   140  	}
   141  	// Lacking a left subtree, look to the parents.
   142  	p := t // previous node
   143  	t = t.parent
   144  	for t != nil {
   145  		// Walk up the tree until we find a node that has a left subtree
   146  		// that we haven't already visited.
   147  		if t.right == p {
   148  			if f.matches(t.span.treapFilter()) {
   149  				// If this node matches, then it's guaranteed to be the
   150  				// predecessor since everything to its left is strictly
   151  				// greater.
   152  				return t
   153  			} else if t.left != nil && f.matches(t.left.types) {
   154  				// Failing the root of this subtree, if its left subtree has
   155  				// something, that's where we'll find our predecessor.
   156  				return t.left.findMaximal(f)
   157  			}
   158  		}
   159  		p = t
   160  		t = t.parent
   161  	}
   162  	// If the parent is nil, then we've hit the root without finding
   163  	// a suitable left subtree containing the node (and the predecessor
   164  	// wasn't on the path). Thus, there's no predecessor, so just return
   165  	// nil.
   166  	return nil
   167  }
   168  
   169  // succ returns the successor of t in the treap subject to the criteria
   170  // specified by the filter f. Returns nil if no such successor exists.
   171  func (t *treapNode) succ(f treapIterFilter) *treapNode {
   172  	// See pred. This method is just the logical inversion of it.
   173  	if t.right != nil && f.matches(t.right.types) {
   174  		return t.right.findMinimal(f)
   175  	}
   176  	p := t
   177  	t = t.parent
   178  	for t != nil {
   179  		if t.left == p {
   180  			if f.matches(t.span.treapFilter()) {
   181  				return t
   182  			} else if t.right != nil && f.matches(t.right.types) {
   183  				return t.right.findMinimal(f)
   184  			}
   185  		}
   186  		p = t
   187  		t = t.parent
   188  	}
   189  	return nil
   190  }
   191  
   192  // isSpanInTreap is handy for debugging. One should hold the heap lock, usually
   193  // mheap_.lock().
   194  func (t *treapNode) isSpanInTreap(s *mspan) bool {
   195  	if t == nil {
   196  		return false
   197  	}
   198  	return t.span == s || t.left.isSpanInTreap(s) || t.right.isSpanInTreap(s)
   199  }
   200  
   201  // walkTreap is handy for debugging and testing.
   202  // Starting at some treapnode t, for example the root, do a depth first preorder walk of
   203  // the tree executing fn at each treap node. One should hold the heap lock, usually
   204  // mheap_.lock().
   205  func (t *treapNode) walkTreap(fn func(tn *treapNode)) {
   206  	if t == nil {
   207  		return
   208  	}
   209  	fn(t)
   210  	t.left.walkTreap(fn)
   211  	t.right.walkTreap(fn)
   212  }
   213  
   214  // checkTreapNode when used in conjunction with walkTreap can usually detect a
   215  // poorly formed treap.
   216  func checkTreapNode(t *treapNode) {
   217  	if t == nil {
   218  		return
   219  	}
   220  	if t.span.next != nil || t.span.prev != nil || t.span.list != nil {
   221  		throw("span may be on an mSpanList while simultaneously in the treap")
   222  	}
   223  	if t.span.base() != t.key {
   224  		println("runtime: checkTreapNode treapNode t=", t, "     t.key=", t.key,
   225  			"t.span.base()=", t.span.base())
   226  		throw("why does span.base() and treap.key do not match?")
   227  	}
   228  	if t.left != nil && t.key < t.left.key {
   229  		throw("found out-of-order spans in treap (left child has greater base address)")
   230  	}
   231  	if t.right != nil && t.key > t.right.key {
   232  		throw("found out-of-order spans in treap (right child has lesser base address)")
   233  	}
   234  }
   235  
   236  // validateInvariants is handy for debugging and testing.
   237  // It ensures that the various invariants on each treap node are
   238  // appropriately maintained throughout the treap by walking the
   239  // treap in a post-order manner.
   240  func (t *treapNode) validateInvariants() (uintptr, treapIterFilter) {
   241  	if t == nil {
   242  		return 0, 0
   243  	}
   244  	leftMax, leftTypes := t.left.validateInvariants()
   245  	rightMax, rightTypes := t.right.validateInvariants()
   246  	max := t.span.npages
   247  	if leftMax > max {
   248  		max = leftMax
   249  	}
   250  	if rightMax > max {
   251  		max = rightMax
   252  	}
   253  	if max != t.maxPages {
   254  		println("runtime: t.maxPages=", t.maxPages, "want=", max)
   255  		throw("maxPages invariant violated in treap")
   256  	}
   257  	typ := t.span.treapFilter() | leftTypes | rightTypes
   258  	if typ != t.types {
   259  		println("runtime: t.types=", t.types, "want=", typ)
   260  		throw("types invariant violated in treap")
   261  	}
   262  	return max, typ
   263  }
   264  
   265  // treapIterType represents the type of iteration to perform
   266  // over the treap. Each different flag is represented by a bit
   267  // in the type, and types may be combined together by a bitwise
   268  // or operation.
   269  //
   270  // Note that only 5 bits are available for treapIterType, do not
   271  // use the 3 higher-order bits. This constraint is to allow for
   272  // expansion into a treapIterFilter, which is a uint32.
   273  type treapIterType uint8
   274  
   275  const (
   276  	treapIterScav treapIterType = 1 << iota // scavenged spans
   277  	treapIterHuge                           // spans containing at least one huge page
   278  	treapIterBits = iota
   279  )
   280  
   281  // treapIterFilter is a bitwise filter of different spans by binary
   282  // properties. Each bit of a treapIterFilter represents a unique
   283  // combination of bits set in a treapIterType, in other words, it
   284  // represents the power set of a treapIterType.
   285  //
   286  // The purpose of this representation is to allow the existence of
   287  // a specific span type to bubble up in the treap (see the types
   288  // field on treapNode).
   289  //
   290  // More specifically, any treapIterType may be transformed into a
   291  // treapIterFilter for a specific combination of flags via the
   292  // following operation: 1 << (0x1f&treapIterType).
   293  type treapIterFilter uint32
   294  
   295  // treapFilterAll represents the filter which allows all spans.
   296  const treapFilterAll = ^treapIterFilter(0)
   297  
   298  // treapFilter creates a new treapIterFilter from two treapIterTypes.
   299  // mask represents a bitmask for which flags we should check against
   300  // and match for the expected result after applying the mask.
   301  func treapFilter(mask, match treapIterType) treapIterFilter {
   302  	allow := treapIterFilter(0)
   303  	for i := treapIterType(0); i < 1<<treapIterBits; i++ {
   304  		if mask&i == match {
   305  			allow |= 1 << i
   306  		}
   307  	}
   308  	return allow
   309  }
   310  
   311  // matches returns true if m and f intersect.
   312  func (f treapIterFilter) matches(m treapIterFilter) bool {
   313  	return f&m != 0
   314  }
   315  
   316  // treapFilter returns the treapIterFilter exactly matching this span,
   317  // i.e. popcount(result) == 1.
   318  func (s *mspan) treapFilter() treapIterFilter {
   319  	have := treapIterType(0)
   320  	if s.scavenged {
   321  		have |= treapIterScav
   322  	}
   323  	if s.hugePages() > 0 {
   324  		have |= treapIterHuge
   325  	}
   326  	return treapIterFilter(uint32(1) << (0x1f & have))
   327  }
   328  
   329  // treapIter is a bidirectional iterator type which may be used to iterate over a
   330  // an mTreap in-order forwards (increasing order) or backwards (decreasing order).
   331  // Its purpose is to hide details about the treap from users when trying to iterate
   332  // over it.
   333  //
   334  // To create iterators over the treap, call start or end on an mTreap.
   335  type treapIter struct {
   336  	f treapIterFilter
   337  	t *treapNode
   338  }
   339  
   340  // span returns the span at the current position in the treap.
   341  // If the treap is not valid, span will panic.
   342  func (i *treapIter) span() *mspan {
   343  	return i.t.span
   344  }
   345  
   346  // valid returns whether the iterator represents a valid position
   347  // in the mTreap.
   348  func (i *treapIter) valid() bool {
   349  	return i.t != nil
   350  }
   351  
   352  // next moves the iterator forward by one. Once the iterator
   353  // ceases to be valid, calling next will panic.
   354  func (i treapIter) next() treapIter {
   355  	i.t = i.t.succ(i.f)
   356  	return i
   357  }
   358  
   359  // prev moves the iterator backwards by one. Once the iterator
   360  // ceases to be valid, calling prev will panic.
   361  func (i treapIter) prev() treapIter {
   362  	i.t = i.t.pred(i.f)
   363  	return i
   364  }
   365  
   366  // start returns an iterator which points to the start of the treap (the
   367  // left-most node in the treap) subject to mask and match constraints.
   368  func (root *mTreap) start(mask, match treapIterType) treapIter {
   369  	f := treapFilter(mask, match)
   370  	return treapIter{f, root.treap.findMinimal(f)}
   371  }
   372  
   373  // end returns an iterator which points to the end of the treap (the
   374  // right-most node in the treap) subject to mask and match constraints.
   375  func (root *mTreap) end(mask, match treapIterType) treapIter {
   376  	f := treapFilter(mask, match)
   377  	return treapIter{f, root.treap.findMaximal(f)}
   378  }
   379  
   380  // mutate allows one to mutate the span without removing it from the treap via a
   381  // callback. The span's base and size are allowed to change as long as the span
   382  // remains in the same order relative to its predecessor and successor.
   383  //
   384  // Note however that any operation that causes a treap rebalancing inside of fn
   385  // is strictly forbidden, as that may cause treap node metadata to go
   386  // out-of-sync.
   387  func (root *mTreap) mutate(i treapIter, fn func(span *mspan)) {
   388  	s := i.span()
   389  	// Save some state about the span for later inspection.
   390  	hpages := s.hugePages()
   391  	scavenged := s.scavenged
   392  	// Call the mutator.
   393  	fn(s)
   394  	// Update unscavHugePages appropriately.
   395  	if !scavenged {
   396  		mheap_.free.unscavHugePages -= hpages
   397  	}
   398  	if !s.scavenged {
   399  		mheap_.free.unscavHugePages += s.hugePages()
   400  	}
   401  	// Update the key in case the base changed.
   402  	i.t.key = s.base()
   403  	// Updating invariants up the tree needs to happen if
   404  	// anything changed at all, so just go ahead and do it
   405  	// unconditionally.
   406  	//
   407  	// If it turns out nothing changed, it'll exit quickly.
   408  	t := i.t
   409  	for t != nil && t.updateInvariants() {
   410  		t = t.parent
   411  	}
   412  }
   413  
   414  // insert adds span to the large span treap.
   415  func (root *mTreap) insert(span *mspan) {
   416  	if !span.scavenged {
   417  		root.unscavHugePages += span.hugePages()
   418  	}
   419  	base := span.base()
   420  	var last *treapNode
   421  	pt := &root.treap
   422  	for t := *pt; t != nil; t = *pt {
   423  		last = t
   424  		if t.key < base {
   425  			pt = &t.right
   426  		} else if t.key > base {
   427  			pt = &t.left
   428  		} else {
   429  			throw("inserting span already in treap")
   430  		}
   431  	}
   432  
   433  	// Add t as new leaf in tree of span size and unique addrs.
   434  	// The balanced tree is a treap using priority as the random heap priority.
   435  	// That is, it is a binary tree ordered according to the key,
   436  	// but then among the space of possible binary trees respecting those
   437  	// keys, it is kept balanced on average by maintaining a heap ordering
   438  	// on the priority: s.priority <= both s.right.priority and s.right.priority.
   439  	// https://en.wikipedia.org/wiki/Treap
   440  	// https://faculty.washington.edu/aragon/pubs/rst89.pdf
   441  
   442  	t := (*treapNode)(mheap_.treapalloc.alloc())
   443  	t.key = span.base()
   444  	t.priority = fastrand()
   445  	t.span = span
   446  	t.maxPages = span.npages
   447  	t.types = span.treapFilter()
   448  	t.parent = last
   449  	*pt = t // t now at a leaf.
   450  
   451  	// Update the tree to maintain the various invariants.
   452  	i := t
   453  	for i.parent != nil && i.parent.updateInvariants() {
   454  		i = i.parent
   455  	}
   456  
   457  	// Rotate up into tree according to priority.
   458  	for t.parent != nil && t.parent.priority > t.priority {
   459  		if t != nil && t.span.base() != t.key {
   460  			println("runtime: insert t=", t, "t.key=", t.key)
   461  			println("runtime:      t.span=", t.span, "t.span.base()=", t.span.base())
   462  			throw("span and treap node base addresses do not match")
   463  		}
   464  		if t.parent.left == t {
   465  			root.rotateRight(t.parent)
   466  		} else {
   467  			if t.parent.right != t {
   468  				throw("treap insert finds a broken treap")
   469  			}
   470  			root.rotateLeft(t.parent)
   471  		}
   472  	}
   473  }
   474  
   475  func (root *mTreap) removeNode(t *treapNode) {
   476  	if !t.span.scavenged {
   477  		root.unscavHugePages -= t.span.hugePages()
   478  	}
   479  	if t.span.base() != t.key {
   480  		throw("span and treap node base addresses do not match")
   481  	}
   482  	// Rotate t down to be leaf of tree for removal, respecting priorities.
   483  	for t.right != nil || t.left != nil {
   484  		if t.right == nil || t.left != nil && t.left.priority < t.right.priority {
   485  			root.rotateRight(t)
   486  		} else {
   487  			root.rotateLeft(t)
   488  		}
   489  	}
   490  	// Remove t, now a leaf.
   491  	if t.parent != nil {
   492  		p := t.parent
   493  		if p.left == t {
   494  			p.left = nil
   495  		} else {
   496  			p.right = nil
   497  		}
   498  		// Walk up the tree updating invariants until no updates occur.
   499  		for p != nil && p.updateInvariants() {
   500  			p = p.parent
   501  		}
   502  	} else {
   503  		root.treap = nil
   504  	}
   505  	// Return the found treapNode's span after freeing the treapNode.
   506  	mheap_.treapalloc.free(unsafe.Pointer(t))
   507  }
   508  
   509  // find searches for, finds, and returns the treap iterator over all spans
   510  // representing the position of the span with the smallest base address which is
   511  // at least npages in size. If no span has at least npages it returns an invalid
   512  // iterator.
   513  //
   514  // This algorithm is as follows:
   515  // * If there's a left child and its subtree can satisfy this allocation,
   516  //   continue down that subtree.
   517  // * If there's no such left child, check if the root of this subtree can
   518  //   satisfy the allocation. If so, we're done.
   519  // * If the root cannot satisfy the allocation either, continue down the
   520  //   right subtree if able.
   521  // * Else, break and report that we cannot satisfy the allocation.
   522  //
   523  // The preference for left, then current, then right, results in us getting
   524  // the left-most node which will contain the span with the lowest base
   525  // address.
   526  //
   527  // Note that if a request cannot be satisfied the fourth case will be
   528  // reached immediately at the root, since neither the left subtree nor
   529  // the right subtree will have a sufficient maxPages, whilst the root
   530  // node is also unable to satisfy it.
   531  func (root *mTreap) find(npages uintptr) treapIter {
   532  	t := root.treap
   533  	for t != nil {
   534  		if t.span == nil {
   535  			throw("treap node with nil span found")
   536  		}
   537  		// Iterate over the treap trying to go as far left
   538  		// as possible while simultaneously ensuring that the
   539  		// subtrees we choose always have a span which can
   540  		// satisfy the allocation.
   541  		if t.left != nil && t.left.maxPages >= npages {
   542  			t = t.left
   543  		} else if t.span.npages >= npages {
   544  			// Before going right, if this span can satisfy the
   545  			// request, stop here.
   546  			break
   547  		} else if t.right != nil && t.right.maxPages >= npages {
   548  			t = t.right
   549  		} else {
   550  			t = nil
   551  		}
   552  	}
   553  	return treapIter{treapFilterAll, t}
   554  }
   555  
   556  // removeSpan searches for, finds, deletes span along with
   557  // the associated treap node. If the span is not in the treap
   558  // then t will eventually be set to nil and the t.span
   559  // will throw.
   560  func (root *mTreap) removeSpan(span *mspan) {
   561  	base := span.base()
   562  	t := root.treap
   563  	for t.span != span {
   564  		if t.key < base {
   565  			t = t.right
   566  		} else if t.key > base {
   567  			t = t.left
   568  		}
   569  	}
   570  	root.removeNode(t)
   571  }
   572  
   573  // erase removes the element referred to by the current position of the
   574  // iterator. This operation consumes the given iterator, so it should no
   575  // longer be used. It is up to the caller to get the next or previous
   576  // iterator before calling erase, if need be.
   577  func (root *mTreap) erase(i treapIter) {
   578  	root.removeNode(i.t)
   579  }
   580  
   581  // rotateLeft rotates the tree rooted at node x.
   582  // turning (x a (y b c)) into (y (x a b) c).
   583  func (root *mTreap) rotateLeft(x *treapNode) {
   584  	// p -> (x a (y b c))
   585  	p := x.parent
   586  	a, y := x.left, x.right
   587  	b, c := y.left, y.right
   588  
   589  	y.left = x
   590  	x.parent = y
   591  	y.right = c
   592  	if c != nil {
   593  		c.parent = y
   594  	}
   595  	x.left = a
   596  	if a != nil {
   597  		a.parent = x
   598  	}
   599  	x.right = b
   600  	if b != nil {
   601  		b.parent = x
   602  	}
   603  
   604  	y.parent = p
   605  	if p == nil {
   606  		root.treap = y
   607  	} else if p.left == x {
   608  		p.left = y
   609  	} else {
   610  		if p.right != x {
   611  			throw("large span treap rotateLeft")
   612  		}
   613  		p.right = y
   614  	}
   615  
   616  	x.updateInvariants()
   617  	y.updateInvariants()
   618  }
   619  
   620  // rotateRight rotates the tree rooted at node y.
   621  // turning (y (x a b) c) into (x a (y b c)).
   622  func (root *mTreap) rotateRight(y *treapNode) {
   623  	// p -> (y (x a b) c)
   624  	p := y.parent
   625  	x, c := y.left, y.right
   626  	a, b := x.left, x.right
   627  
   628  	x.left = a
   629  	if a != nil {
   630  		a.parent = x
   631  	}
   632  	x.right = y
   633  	y.parent = x
   634  	y.left = b
   635  	if b != nil {
   636  		b.parent = y
   637  	}
   638  	y.right = c
   639  	if c != nil {
   640  		c.parent = y
   641  	}
   642  
   643  	x.parent = p
   644  	if p == nil {
   645  		root.treap = x
   646  	} else if p.left == y {
   647  		p.left = x
   648  	} else {
   649  		if p.right != y {
   650  			throw("large span treap rotateRight")
   651  		}
   652  		p.right = x
   653  	}
   654  
   655  	y.updateInvariants()
   656  	x.updateInvariants()
   657  }
   658  

View as plain text