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  // http://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 keep tree probablistically balanced
    47  }
    48  
    49  func (t *treapNode) init() {
    50  	t.right = nil
    51  	t.left = nil
    52  	t.parent = nil
    53  	t.spanKey = nil
    54  	t.npagesKey = 0
    55  	t.priority = 0
    56  }
    57  
    58  // isSpanInTreap is handy for debugging. One should hold the heap lock, usually
    59  // mheap_.lock().
    60  func (t *treapNode) isSpanInTreap(s *mspan) bool {
    61  	if t == nil {
    62  		return false
    63  	}
    64  	return t.spanKey == s || t.left.isSpanInTreap(s) || t.right.isSpanInTreap(s)
    65  }
    66  
    67  // walkTreap is handy for debugging.
    68  // Starting at some treapnode t, for example the root, do a depth first preorder walk of
    69  // the tree executing fn at each treap node. One should hold the heap lock, usually
    70  // mheap_.lock().
    71  func (t *treapNode) walkTreap(fn func(tn *treapNode)) {
    72  	if t == nil {
    73  		return
    74  	}
    75  	fn(t)
    76  	t.left.walkTreap(fn)
    77  	t.right.walkTreap(fn)
    78  }
    79  
    80  // checkTreapNode when used in conjunction with walkTreap can usually detect a
    81  // poorly formed treap.
    82  func checkTreapNode(t *treapNode) {
    83  	// lessThan is used to order the treap.
    84  	// npagesKey and npages are the primary keys.
    85  	// spanKey and span are the secondary keys.
    86  	// span == nil (0) will always be lessThan all
    87  	// spans of the same size.
    88  	lessThan := func(npages uintptr, s *mspan) bool {
    89  		if t.npagesKey != npages {
    90  			return t.npagesKey < npages
    91  		}
    92  		// t.npagesKey == npages
    93  		return uintptr(unsafe.Pointer(t.spanKey)) < uintptr(unsafe.Pointer(s))
    94  	}
    95  
    96  	if t == nil {
    97  		return
    98  	}
    99  	if t.spanKey.npages != t.npagesKey || t.spanKey.next != nil {
   100  		println("runtime: checkTreapNode treapNode t=", t, "     t.npagesKey=", t.npagesKey,
   101  			"t.spanKey.npages=", t.spanKey.npages)
   102  		throw("why does span.npages and treap.ngagesKey do not match?")
   103  	}
   104  	if t.left != nil && lessThan(t.left.npagesKey, t.left.spanKey) {
   105  		throw("t.lessThan(t.left.npagesKey, t.left.spanKey) is not false")
   106  	}
   107  	if t.right != nil && !lessThan(t.right.npagesKey, t.right.spanKey) {
   108  		throw("!t.lessThan(t.left.npagesKey, t.left.spanKey) is not false")
   109  	}
   110  }
   111  
   112  // insert adds span to the large span treap.
   113  func (root *mTreap) insert(span *mspan) {
   114  	npages := span.npages
   115  	var last *treapNode
   116  	pt := &root.treap
   117  	for t := *pt; t != nil; t = *pt {
   118  		last = t
   119  		if t.npagesKey < npages {
   120  			pt = &t.right
   121  		} else if t.npagesKey > npages {
   122  			pt = &t.left
   123  		} else if uintptr(unsafe.Pointer(t.spanKey)) < uintptr(unsafe.Pointer(span)) {
   124  			// t.npagesKey == npages, so sort on span addresses.
   125  			pt = &t.right
   126  		} else if uintptr(unsafe.Pointer(t.spanKey)) > uintptr(unsafe.Pointer(span)) {
   127  			pt = &t.left
   128  		} else {
   129  			throw("inserting span already in treap")
   130  		}
   131  	}
   132  
   133  	// Add t as new leaf in tree of span size and unique addrs.
   134  	// The balanced tree is a treap using priority as the random heap priority.
   135  	// That is, it is a binary tree ordered according to the npagesKey,
   136  	// but then among the space of possible binary trees respecting those
   137  	// npagesKeys, it is kept balanced on average by maintaining a heap ordering
   138  	// on the priority: s.priority <= both s.right.priority and s.right.priority.
   139  	// https://en.wikipedia.org/wiki/Treap
   140  	// http://faculty.washington.edu/aragon/pubs/rst89.pdf
   141  
   142  	t := (*treapNode)(mheap_.treapalloc.alloc())
   143  	t.init()
   144  	t.npagesKey = span.npages
   145  	t.priority = fastrand()
   146  	t.spanKey = span
   147  	t.parent = last
   148  	*pt = t // t now at a leaf.
   149  	// Rotate up into tree according to priority.
   150  	for t.parent != nil && t.parent.priority > t.priority {
   151  		if t != nil && t.spanKey.npages != t.npagesKey {
   152  			println("runtime: insert t=", t, "t.npagesKey=", t.npagesKey)
   153  			println("runtime:      t.spanKey=", t.spanKey, "t.spanKey.npages=", t.spanKey.npages)
   154  			throw("span and treap sizes do not match?")
   155  		}
   156  		if t.parent.left == t {
   157  			root.rotateRight(t.parent)
   158  		} else {
   159  			if t.parent.right != t {
   160  				throw("treap insert finds a broken treap")
   161  			}
   162  			root.rotateLeft(t.parent)
   163  		}
   164  	}
   165  }
   166  
   167  func (root *mTreap) removeNode(t *treapNode) {
   168  	if t.spanKey.npages != t.npagesKey {
   169  		throw("span and treap node npages do not match")
   170  	}
   171  
   172  	// Rotate t down to be leaf of tree for removal, respecting priorities.
   173  	for t.right != nil || t.left != nil {
   174  		if t.right == nil || t.left != nil && t.left.priority < t.right.priority {
   175  			root.rotateRight(t)
   176  		} else {
   177  			root.rotateLeft(t)
   178  		}
   179  	}
   180  	// Remove t, now a leaf.
   181  	if t.parent != nil {
   182  		if t.parent.left == t {
   183  			t.parent.left = nil
   184  		} else {
   185  			t.parent.right = nil
   186  		}
   187  	} else {
   188  		root.treap = nil
   189  	}
   190  	// Return the found treapNode's span after freeing the treapNode.
   191  	t.spanKey = nil
   192  	t.npagesKey = 0
   193  	mheap_.treapalloc.free(unsafe.Pointer(t))
   194  }
   195  
   196  // remove searches for, finds, removes from the treap, and returns the smallest
   197  // span that can hold npages. If no span has at least npages return nil.
   198  // This is slightly more complicated than a simple binary tree search
   199  // since if an exact match is not found the next larger node is
   200  // returned.
   201  // If the last node inspected > npagesKey not holding
   202  // a left node (a smaller npages) is the "best fit" node.
   203  func (root *mTreap) remove(npages uintptr) *mspan {
   204  	t := root.treap
   205  	for t != nil {
   206  		if t.spanKey == nil {
   207  			throw("treap node with nil spanKey found")
   208  		}
   209  		if t.npagesKey < npages {
   210  			t = t.right
   211  		} else if t.left != nil && t.left.npagesKey >= npages {
   212  			t = t.left
   213  		} else {
   214  			result := t.spanKey
   215  			root.removeNode(t)
   216  			return result
   217  		}
   218  	}
   219  	return nil
   220  }
   221  
   222  // removeSpan searches for, finds, deletes span along with
   223  // the associated treap node. If the span is not in the treap
   224  // then t will eventually be set to nil and the t.spanKey
   225  // will throw.
   226  func (root *mTreap) removeSpan(span *mspan) {
   227  	npages := span.npages
   228  	t := root.treap
   229  	for t.spanKey != span {
   230  		if t.npagesKey < npages {
   231  			t = t.right
   232  		} else if t.npagesKey > npages {
   233  			t = t.left
   234  		} else if uintptr(unsafe.Pointer(t.spanKey)) < uintptr(unsafe.Pointer(span)) {
   235  			t = t.right
   236  		} else if uintptr(unsafe.Pointer(t.spanKey)) > uintptr(unsafe.Pointer(span)) {
   237  			t = t.left
   238  		}
   239  	}
   240  	root.removeNode(t)
   241  }
   242  
   243  // scavengetreap visits each node in the treap and scavenges the
   244  // treapNode's span.
   245  func scavengetreap(treap *treapNode, now, limit uint64) uintptr {
   246  	if treap == nil {
   247  		return 0
   248  	}
   249  	return scavengeTreapNode(treap, now, limit) +
   250  		scavengetreap(treap.left, now, limit) +
   251  		scavengetreap(treap.right, now, limit)
   252  }
   253  
   254  // rotateLeft rotates the tree rooted at node x.
   255  // turning (x a (y b c)) into (y (x a b) c).
   256  func (root *mTreap) rotateLeft(x *treapNode) {
   257  	// p -> (x a (y b c))
   258  	p := x.parent
   259  	a, y := x.left, x.right
   260  	b, c := y.left, y.right
   261  
   262  	y.left = x
   263  	x.parent = y
   264  	y.right = c
   265  	if c != nil {
   266  		c.parent = y
   267  	}
   268  	x.left = a
   269  	if a != nil {
   270  		a.parent = x
   271  	}
   272  	x.right = b
   273  	if b != nil {
   274  		b.parent = x
   275  	}
   276  
   277  	y.parent = p
   278  	if p == nil {
   279  		root.treap = y
   280  	} else if p.left == x {
   281  		p.left = y
   282  	} else {
   283  		if p.right != x {
   284  			throw("large span treap rotateLeft")
   285  		}
   286  		p.right = y
   287  	}
   288  }
   289  
   290  // rotateRight rotates the tree rooted at node y.
   291  // turning (y (x a b) c) into (x a (y b c)).
   292  func (root *mTreap) rotateRight(y *treapNode) {
   293  	// p -> (y (x a b) c)
   294  	p := y.parent
   295  	x, c := y.left, y.right
   296  	a, b := x.left, x.right
   297  
   298  	x.left = a
   299  	if a != nil {
   300  		a.parent = x
   301  	}
   302  	x.right = y
   303  	y.parent = x
   304  	y.left = b
   305  	if b != nil {
   306  		b.parent = y
   307  	}
   308  	y.right = c
   309  	if c != nil {
   310  		c.parent = y
   311  	}
   312  
   313  	x.parent = p
   314  	if p == nil {
   315  		root.treap = x
   316  	} else if p.left == y {
   317  		p.left = x
   318  	} else {
   319  		if p.right != y {
   320  			throw("large span treap rotateRight")
   321  		}
   322  		p.right = x
   323  	}
   324  }
   325
View as plain text