Source file src/pkg/runtime/mgclarge.go

     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