runtime: add tests for runtime mTreap

This change exports the runtime mTreap in export_test.go and then adds a
series of tests which check that the invariants of the treap are
maintained under different operations. These tests also include tests
for the treap iterator type.

Also, we note that the find() operation on the treap never actually was
best-fit, so the tests just ensure that it returns an appropriately
sized span.

For #30333.

Change-Id: If81f7c746dda6677ebca925cb0a940134701b894
Reviewed-on: https://go-review.googlesource.com/c/go/+/164100
Run-TryBot: Michael Knyszek <mknyszek@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Austin Clements <austin@google.com>

1 files changed, 113 insertions, 0 deletions

diff --git a/src/runtime/export_test.go b/src/runtime/export_test.go
index a16e664895..c950a6dc8e 100644
--- a/src/runtime/export_test.go
+++ b/src/runtime/export_test.go
@@ -515,3 +515,116 @@ func MapTombstoneCheck(m map[int]int) {
 		}
 	}
 }
+
+// Span is a safe wrapper around an mspan, whose memory
+// is managed manually.
+type Span struct {
+	*mspan
+}
+
+func AllocSpan(base, npages uintptr) Span {
+	lock(&mheap_.lock)
+	s := (*mspan)(mheap_.spanalloc.alloc())
+	unlock(&mheap_.lock)
+	s.init(base, npages)
+	return Span{s}
+}
+
+func (s *Span) Free() {
+	lock(&mheap_.lock)
+	mheap_.spanalloc.free(unsafe.Pointer(s.mspan))
+	unlock(&mheap_.lock)
+	s.mspan = nil
+}
+
+func (s Span) Base() uintptr {
+	return s.mspan.base()
+}
+
+func (s Span) Pages() uintptr {
+	return s.mspan.npages
+}
+
+type TreapIter struct {
+	treapIter
+}
+
+func (t TreapIter) Span() Span {
+	return Span{t.span()}
+}
+
+func (t TreapIter) Valid() bool {
+	return t.valid()
+}
+
+func (t TreapIter) Next() TreapIter {
+	return TreapIter{t.next()}
+}
+
+func (t TreapIter) Prev() TreapIter {
+	return TreapIter{t.prev()}
+}
+
+// Treap is a safe wrapper around mTreap for testing.
+//
+// It must never be heap-allocated because mTreap is
+// notinheap.
+//
+//go:notinheap
+type Treap struct {
+	mTreap
+}
+
+func (t *Treap) Start() TreapIter {
+	return TreapIter{t.start()}
+}
+
+func (t *Treap) End() TreapIter {
+	return TreapIter{t.end()}
+}
+
+func (t *Treap) Insert(s Span) {
+	// mTreap uses a fixalloc in mheap_ for treapNode
+	// allocation which requires the mheap_ lock to manipulate.
+	// Locking here is safe because the treap itself never allocs
+	// or otherwise ends up grabbing this lock.
+	lock(&mheap_.lock)
+	t.insert(s.mspan)
+	unlock(&mheap_.lock)
+	t.CheckInvariants()
+}
+
+func (t *Treap) Find(npages uintptr) TreapIter {
+	return TreapIter{t.find(npages)}
+}
+
+func (t *Treap) Erase(i TreapIter) {
+	// mTreap uses a fixalloc in mheap_ for treapNode
+	// freeing which requires the mheap_ lock to manipulate.
+	// Locking here is safe because the treap itself never allocs
+	// or otherwise ends up grabbing this lock.
+	lock(&mheap_.lock)
+	t.erase(i.treapIter)
+	unlock(&mheap_.lock)
+	t.CheckInvariants()
+}
+
+func (t *Treap) RemoveSpan(s Span) {
+	// See Erase about locking.
+	lock(&mheap_.lock)
+	t.removeSpan(s.mspan)
+	unlock(&mheap_.lock)
+	t.CheckInvariants()
+}
+
+func (t *Treap) Size() int {
+	i := 0
+	t.mTreap.treap.walkTreap(func(t *treapNode) {
+		i++
+	})
+	return i
+}
+
+func (t *Treap) CheckInvariants() {
+	t.mTreap.treap.walkTreap(checkTreapNode)
+}