diff options
author | Michael Anthony Knyszek <mknyszek@google.com> | 2019-04-23 18:57:16 +0000 |
---|---|---|
committer | Brad Fitzpatrick <bradfitz@golang.org> | 2019-04-26 16:42:23 +0000 |
commit | 438b1a5dae01812a2b91b648c762414d4854ccd7 (patch) | |
tree | bdf68a95cea3158b6bfebb9132bbc18499c72354 | |
parent | a1a9d8a84d4924cb2d374b33cb5844b2e43c6fe9 (diff) | |
download | go-438b1a5dae01812a2b91b648c762414d4854ccd7.tar.gz go-438b1a5dae01812a2b91b648c762414d4854ccd7.zip |
[release-branch.go1.12] runtime: make mTreap.find actually find the best fit
This change modifies the implementation of mTreap.find to find the
best-fit span with the lowest possible base address.
Fixes #31677.
Change-Id: Ib4bda0f85d7d0590326f939a243a6e4665f37d3f
Reviewed-on: https://go-review.googlesource.com/c/go/+/173479
Run-TryBot: Michael Knyszek <mknyszek@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Austin Clements <austin@google.com>
(cherry picked from commit 8c05d67661c966f5130e51ca685b0c70a5a929ff)
Reviewed-on: https://go-review.googlesource.com/c/go/+/173939
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
-rw-r--r-- | src/runtime/mgclarge.go | 22 | ||||
-rw-r--r-- | src/runtime/treap_test.go | 12 |
2 files changed, 19 insertions, 15 deletions
diff --git a/src/runtime/mgclarge.go b/src/runtime/mgclarge.go index fd68dc4bf5..0e39c66dc3 100644 --- a/src/runtime/mgclarge.go +++ b/src/runtime/mgclarge.go @@ -301,24 +301,30 @@ func (root *mTreap) removeNode(t *treapNode) { // find searches for, finds, and returns the treap node containing the // smallest span that can hold npages. If no span has at least npages // it returns nil. -// This is slightly more complicated than a simple binary tree search -// since if an exact match is not found the next larger node is -// returned. +// This is a simple binary tree search that tracks the best-fit node found +// so far. The best-fit node is guaranteed to be on the path to a +// (maybe non-existent) lowest-base exact match. func (root *mTreap) find(npages uintptr) *treapNode { + var best *treapNode t := root.treap for t != nil { if t.spanKey == nil { throw("treap node with nil spanKey found") } - if t.npagesKey < npages { - t = t.right - } else if t.left != nil && t.left.npagesKey >= npages { + // If we found an exact match, try to go left anyway. There could be + // a span there with a lower base address. + // + // Don't bother checking nil-ness of left and right here; even if t + // becomes nil, we already know the other path had nothing better for + // us anyway. + if t.npagesKey >= npages { + best = t t = t.left } else { - return t + t = t.right } } - return nil + return best } // removeSpan searches for, finds, deletes span along with diff --git a/src/runtime/treap_test.go b/src/runtime/treap_test.go index 49d97699ca..76e4829d99 100644 --- a/src/runtime/treap_test.go +++ b/src/runtime/treap_test.go @@ -58,11 +58,7 @@ func TestTreap(t *testing.T) { } tr.RemoveSpan(spans[0]) }) - t.Run("Find", func(t *testing.T) { - // Note that Find doesn't actually find the best-fit - // element, so just make sure it always returns an element - // that is at least large enough to satisfy the request. - // + t.Run("FindBestFit", func(t *testing.T) { // Run this 10 times, recreating the treap each time. // Because of the non-deterministic structure of a treap, // we'll be able to test different structures this way. @@ -72,8 +68,10 @@ func TestTreap(t *testing.T) { tr.Insert(s) } i := tr.Find(5) - if i.Span().Pages() < 5 { - t.Fatalf("expected span of size at least 5, got size %d", i.Span().Pages()) + if i.Span().Pages() != 5 { + t.Fatalf("expected span of size 5, got span of size %d", i.Span().Pages()) + } else if i.Span().Base() != 0xc0040000 { + t.Fatalf("expected span to have the lowest base address, instead got base %x", i.Span().Base()) } for _, s := range spans { tr.RemoveSpan(s) |