blob: ed439c56c256af7700c0eeeeed1b2362df0d021f [file] [log] [blame] [edit]
// 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)
}
})
}
}