summaryrefslogtreecommitdiffstats
path: root/src/runtime/mranges_test.go
diff options
context:
space:
mode:
Diffstat (limited to 'src/runtime/mranges_test.go')
-rw-r--r--src/runtime/mranges_test.go275
1 files changed, 275 insertions, 0 deletions
diff --git a/src/runtime/mranges_test.go b/src/runtime/mranges_test.go
new file mode 100644
index 0000000..ed439c5
--- /dev/null
+++ b/src/runtime/mranges_test.go
@@ -0,0 +1,275 @@
+// Copyright 2020 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package runtime_test
+
+import (
+ . "runtime"
+ "testing"
+)
+
+func validateAddrRanges(t *testing.T, a *AddrRanges, want ...AddrRange) {
+ ranges := a.Ranges()
+ if len(ranges) != len(want) {
+ t.Errorf("want %v, got %v", want, ranges)
+ t.Fatal("different lengths")
+ }
+ gotTotalBytes := uintptr(0)
+ wantTotalBytes := uintptr(0)
+ for i := range ranges {
+ gotTotalBytes += ranges[i].Size()
+ wantTotalBytes += want[i].Size()
+ if ranges[i].Base() >= ranges[i].Limit() {
+ t.Error("empty range found")
+ }
+ // Ensure this is equivalent to what we want.
+ if !ranges[i].Equals(want[i]) {
+ t.Errorf("range %d: got [0x%x, 0x%x), want [0x%x, 0x%x)", i,
+ ranges[i].Base(), ranges[i].Limit(),
+ want[i].Base(), want[i].Limit(),
+ )
+ }
+ if i != 0 {
+ // Ensure the ranges are sorted.
+ if ranges[i-1].Base() >= ranges[i].Base() {
+ t.Errorf("ranges %d and %d are out of sorted order", i-1, i)
+ }
+ // Check for a failure to coalesce.
+ if ranges[i-1].Limit() == ranges[i].Base() {
+ t.Errorf("ranges %d and %d should have coalesced", i-1, i)
+ }
+ // Check if any ranges overlap. Because the ranges are sorted
+ // by base, it's sufficient to just check neighbors.
+ if ranges[i-1].Limit() > ranges[i].Base() {
+ t.Errorf("ranges %d and %d overlap", i-1, i)
+ }
+ }
+ }
+ if wantTotalBytes != gotTotalBytes {
+ t.Errorf("expected %d total bytes, got %d", wantTotalBytes, gotTotalBytes)
+ }
+ if b := a.TotalBytes(); b != gotTotalBytes {
+ t.Errorf("inconsistent total bytes: want %d, got %d", gotTotalBytes, b)
+ }
+ if t.Failed() {
+ t.Errorf("addrRanges: %v", ranges)
+ t.Fatal("detected bad addrRanges")
+ }
+}
+
+func TestAddrRangesAdd(t *testing.T) {
+ a := NewAddrRanges()
+
+ // First range.
+ a.Add(MakeAddrRange(512, 1024))
+ validateAddrRanges(t, &a,
+ MakeAddrRange(512, 1024),
+ )
+
+ // Coalesce up.
+ a.Add(MakeAddrRange(1024, 2048))
+ validateAddrRanges(t, &a,
+ MakeAddrRange(512, 2048),
+ )
+
+ // Add new independent range.
+ a.Add(MakeAddrRange(4096, 8192))
+ validateAddrRanges(t, &a,
+ MakeAddrRange(512, 2048),
+ MakeAddrRange(4096, 8192),
+ )
+
+ // Coalesce down.
+ a.Add(MakeAddrRange(3776, 4096))
+ validateAddrRanges(t, &a,
+ MakeAddrRange(512, 2048),
+ MakeAddrRange(3776, 8192),
+ )
+
+ // Coalesce up and down.
+ a.Add(MakeAddrRange(2048, 3776))
+ validateAddrRanges(t, &a,
+ MakeAddrRange(512, 8192),
+ )
+
+ // Push a bunch of independent ranges to the end to try and force growth.
+ expectedRanges := []AddrRange{MakeAddrRange(512, 8192)}
+ for i := uintptr(0); i < 64; i++ {
+ dRange := MakeAddrRange(8192+(i+1)*2048, 8192+(i+1)*2048+10)
+ a.Add(dRange)
+ expectedRanges = append(expectedRanges, dRange)
+ validateAddrRanges(t, &a, expectedRanges...)
+ }
+
+ // Push a bunch of independent ranges to the beginning to try and force growth.
+ var bottomRanges []AddrRange
+ for i := uintptr(0); i < 63; i++ {
+ dRange := MakeAddrRange(8+i*8, 8+i*8+4)
+ a.Add(dRange)
+ bottomRanges = append(bottomRanges, dRange)
+ validateAddrRanges(t, &a, append(bottomRanges, expectedRanges...)...)
+ }
+}
+
+func TestAddrRangesFindSucc(t *testing.T) {
+ var large []AddrRange
+ for i := 0; i < 100; i++ {
+ large = append(large, MakeAddrRange(5+uintptr(i)*5, 5+uintptr(i)*5+3))
+ }
+
+ type testt struct {
+ name string
+ base uintptr
+ expect int
+ ranges []AddrRange
+ }
+ tests := []testt{
+ {
+ name: "Empty",
+ base: 12,
+ expect: 0,
+ ranges: []AddrRange{},
+ },
+ {
+ name: "OneBefore",
+ base: 12,
+ expect: 0,
+ ranges: []AddrRange{
+ MakeAddrRange(14, 16),
+ },
+ },
+ {
+ name: "OneWithin",
+ base: 14,
+ expect: 1,
+ ranges: []AddrRange{
+ MakeAddrRange(14, 16),
+ },
+ },
+ {
+ name: "OneAfterLimit",
+ base: 16,
+ expect: 1,
+ ranges: []AddrRange{
+ MakeAddrRange(14, 16),
+ },
+ },
+ {
+ name: "OneAfter",
+ base: 17,
+ expect: 1,
+ ranges: []AddrRange{
+ MakeAddrRange(14, 16),
+ },
+ },
+ {
+ name: "ThreeBefore",
+ base: 3,
+ expect: 0,
+ ranges: []AddrRange{
+ MakeAddrRange(6, 10),
+ MakeAddrRange(12, 16),
+ MakeAddrRange(19, 22),
+ },
+ },
+ {
+ name: "ThreeAfter",
+ base: 24,
+ expect: 3,
+ ranges: []AddrRange{
+ MakeAddrRange(6, 10),
+ MakeAddrRange(12, 16),
+ MakeAddrRange(19, 22),
+ },
+ },
+ {
+ name: "ThreeBetween",
+ base: 11,
+ expect: 1,
+ ranges: []AddrRange{
+ MakeAddrRange(6, 10),
+ MakeAddrRange(12, 16),
+ MakeAddrRange(19, 22),
+ },
+ },
+ {
+ name: "ThreeWithin",
+ base: 9,
+ expect: 1,
+ ranges: []AddrRange{
+ MakeAddrRange(6, 10),
+ MakeAddrRange(12, 16),
+ MakeAddrRange(19, 22),
+ },
+ },
+ {
+ name: "Zero",
+ base: 0,
+ expect: 1,
+ ranges: []AddrRange{
+ MakeAddrRange(0, 10),
+ },
+ },
+ {
+ name: "Max",
+ base: ^uintptr(0),
+ expect: 1,
+ ranges: []AddrRange{
+ MakeAddrRange(^uintptr(0)-5, ^uintptr(0)),
+ },
+ },
+ {
+ name: "LargeBefore",
+ base: 2,
+ expect: 0,
+ ranges: large,
+ },
+ {
+ name: "LargeAfter",
+ base: 5 + uintptr(len(large))*5 + 30,
+ expect: len(large),
+ ranges: large,
+ },
+ {
+ name: "LargeBetweenLow",
+ base: 14,
+ expect: 2,
+ ranges: large,
+ },
+ {
+ name: "LargeBetweenHigh",
+ base: 249,
+ expect: 49,
+ ranges: large,
+ },
+ {
+ name: "LargeWithinLow",
+ base: 25,
+ expect: 5,
+ ranges: large,
+ },
+ {
+ name: "LargeWithinHigh",
+ base: 396,
+ expect: 79,
+ ranges: large,
+ },
+ {
+ name: "LargeWithinMiddle",
+ base: 250,
+ expect: 50,
+ ranges: large,
+ },
+ }
+
+ for _, test := range tests {
+ t.Run(test.name, func(t *testing.T) {
+ a := MakeAddrRanges(test.ranges...)
+ i := a.FindSucc(test.base)
+ if i != test.expect {
+ t.Fatalf("expected %d, got %d", test.expect, i)
+ }
+ })
+ }
+}