mranges_test.go

Documentation: runtime

		 1  // Copyright 2020 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  package runtime_test
		 6  
		 7  import (
		 8  	. "runtime"
		 9  	"testing"
		10  )
		11  
		12  func validateAddrRanges(t *testing.T, a *AddrRanges, want ...AddrRange) {
		13  	ranges := a.Ranges()
		14  	if len(ranges) != len(want) {
		15  		t.Errorf("want %v, got %v", want, ranges)
		16  		t.Fatal("different lengths")
		17  	}
		18  	gotTotalBytes := uintptr(0)
		19  	wantTotalBytes := uintptr(0)
		20  	for i := range ranges {
		21  		gotTotalBytes += ranges[i].Size()
		22  		wantTotalBytes += want[i].Size()
		23  		if ranges[i].Base() >= ranges[i].Limit() {
		24  			t.Error("empty range found")
		25  		}
		26  		// Ensure this is equivalent to what we want.
		27  		if !ranges[i].Equals(want[i]) {
		28  			t.Errorf("range %d: got [0x%x, 0x%x), want [0x%x, 0x%x)", i,
		29  				ranges[i].Base(), ranges[i].Limit(),
		30  				want[i].Base(), want[i].Limit(),
		31  			)
		32  		}
		33  		if i != 0 {
		34  			// Ensure the ranges are sorted.
		35  			if ranges[i-1].Base() >= ranges[i].Base() {
		36  				t.Errorf("ranges %d and %d are out of sorted order", i-1, i)
		37  			}
		38  			// Check for a failure to coalesce.
		39  			if ranges[i-1].Limit() == ranges[i].Base() {
		40  				t.Errorf("ranges %d and %d should have coalesced", i-1, i)
		41  			}
		42  			// Check if any ranges overlap. Because the ranges are sorted
		43  			// by base, it's sufficient to just check neighbors.
		44  			if ranges[i-1].Limit() > ranges[i].Base() {
		45  				t.Errorf("ranges %d and %d overlap", i-1, i)
		46  			}
		47  		}
		48  	}
		49  	if wantTotalBytes != gotTotalBytes {
		50  		t.Errorf("expected %d total bytes, got %d", wantTotalBytes, gotTotalBytes)
		51  	}
		52  	if b := a.TotalBytes(); b != gotTotalBytes {
		53  		t.Errorf("inconsistent total bytes: want %d, got %d", gotTotalBytes, b)
		54  	}
		55  	if t.Failed() {
		56  		t.Errorf("addrRanges: %v", ranges)
		57  		t.Fatal("detected bad addrRanges")
		58  	}
		59  }
		60  
		61  func TestAddrRangesAdd(t *testing.T) {
		62  	a := NewAddrRanges()
		63  
		64  	// First range.
		65  	a.Add(MakeAddrRange(512, 1024))
		66  	validateAddrRanges(t, &a,
		67  		MakeAddrRange(512, 1024),
		68  	)
		69  
		70  	// Coalesce up.
		71  	a.Add(MakeAddrRange(1024, 2048))
		72  	validateAddrRanges(t, &a,
		73  		MakeAddrRange(512, 2048),
		74  	)
		75  
		76  	// Add new independent range.
		77  	a.Add(MakeAddrRange(4096, 8192))
		78  	validateAddrRanges(t, &a,
		79  		MakeAddrRange(512, 2048),
		80  		MakeAddrRange(4096, 8192),
		81  	)
		82  
		83  	// Coalesce down.
		84  	a.Add(MakeAddrRange(3776, 4096))
		85  	validateAddrRanges(t, &a,
		86  		MakeAddrRange(512, 2048),
		87  		MakeAddrRange(3776, 8192),
		88  	)
		89  
		90  	// Coalesce up and down.
		91  	a.Add(MakeAddrRange(2048, 3776))
		92  	validateAddrRanges(t, &a,
		93  		MakeAddrRange(512, 8192),
		94  	)
		95  
		96  	// Push a bunch of independent ranges to the end to try and force growth.
		97  	expectedRanges := []AddrRange{MakeAddrRange(512, 8192)}
		98  	for i := uintptr(0); i < 64; i++ {
		99  		dRange := MakeAddrRange(8192+(i+1)*2048, 8192+(i+1)*2048+10)
	 100  		a.Add(dRange)
	 101  		expectedRanges = append(expectedRanges, dRange)
	 102  		validateAddrRanges(t, &a, expectedRanges...)
	 103  	}
	 104  
	 105  	// Push a bunch of independent ranges to the beginning to try and force growth.
	 106  	var bottomRanges []AddrRange
	 107  	for i := uintptr(0); i < 63; i++ {
	 108  		dRange := MakeAddrRange(8+i*8, 8+i*8+4)
	 109  		a.Add(dRange)
	 110  		bottomRanges = append(bottomRanges, dRange)
	 111  		validateAddrRanges(t, &a, append(bottomRanges, expectedRanges...)...)
	 112  	}
	 113  }
	 114  
	 115  func TestAddrRangesFindSucc(t *testing.T) {
	 116  	var large []AddrRange
	 117  	for i := 0; i < 100; i++ {
	 118  		large = append(large, MakeAddrRange(5+uintptr(i)*5, 5+uintptr(i)*5+3))
	 119  	}
	 120  
	 121  	type testt struct {
	 122  		name	 string
	 123  		base	 uintptr
	 124  		expect int
	 125  		ranges []AddrRange
	 126  	}
	 127  	tests := []testt{
	 128  		{
	 129  			name:	 "Empty",
	 130  			base:	 12,
	 131  			expect: 0,
	 132  			ranges: []AddrRange{},
	 133  		},
	 134  		{
	 135  			name:	 "OneBefore",
	 136  			base:	 12,
	 137  			expect: 0,
	 138  			ranges: []AddrRange{
	 139  				MakeAddrRange(14, 16),
	 140  			},
	 141  		},
	 142  		{
	 143  			name:	 "OneWithin",
	 144  			base:	 14,
	 145  			expect: 1,
	 146  			ranges: []AddrRange{
	 147  				MakeAddrRange(14, 16),
	 148  			},
	 149  		},
	 150  		{
	 151  			name:	 "OneAfterLimit",
	 152  			base:	 16,
	 153  			expect: 1,
	 154  			ranges: []AddrRange{
	 155  				MakeAddrRange(14, 16),
	 156  			},
	 157  		},
	 158  		{
	 159  			name:	 "OneAfter",
	 160  			base:	 17,
	 161  			expect: 1,
	 162  			ranges: []AddrRange{
	 163  				MakeAddrRange(14, 16),
	 164  			},
	 165  		},
	 166  		{
	 167  			name:	 "ThreeBefore",
	 168  			base:	 3,
	 169  			expect: 0,
	 170  			ranges: []AddrRange{
	 171  				MakeAddrRange(6, 10),
	 172  				MakeAddrRange(12, 16),
	 173  				MakeAddrRange(19, 22),
	 174  			},
	 175  		},
	 176  		{
	 177  			name:	 "ThreeAfter",
	 178  			base:	 24,
	 179  			expect: 3,
	 180  			ranges: []AddrRange{
	 181  				MakeAddrRange(6, 10),
	 182  				MakeAddrRange(12, 16),
	 183  				MakeAddrRange(19, 22),
	 184  			},
	 185  		},
	 186  		{
	 187  			name:	 "ThreeBetween",
	 188  			base:	 11,
	 189  			expect: 1,
	 190  			ranges: []AddrRange{
	 191  				MakeAddrRange(6, 10),
	 192  				MakeAddrRange(12, 16),
	 193  				MakeAddrRange(19, 22),
	 194  			},
	 195  		},
	 196  		{
	 197  			name:	 "ThreeWithin",
	 198  			base:	 9,
	 199  			expect: 1,
	 200  			ranges: []AddrRange{
	 201  				MakeAddrRange(6, 10),
	 202  				MakeAddrRange(12, 16),
	 203  				MakeAddrRange(19, 22),
	 204  			},
	 205  		},
	 206  		{
	 207  			name:	 "Zero",
	 208  			base:	 0,
	 209  			expect: 1,
	 210  			ranges: []AddrRange{
	 211  				MakeAddrRange(0, 10),
	 212  			},
	 213  		},
	 214  		{
	 215  			name:	 "Max",
	 216  			base:	 ^uintptr(0),
	 217  			expect: 1,
	 218  			ranges: []AddrRange{
	 219  				MakeAddrRange(^uintptr(0)-5, ^uintptr(0)),
	 220  			},
	 221  		},
	 222  		{
	 223  			name:	 "LargeBefore",
	 224  			base:	 2,
	 225  			expect: 0,
	 226  			ranges: large,
	 227  		},
	 228  		{
	 229  			name:	 "LargeAfter",
	 230  			base:	 5 + uintptr(len(large))*5 + 30,
	 231  			expect: len(large),
	 232  			ranges: large,
	 233  		},
	 234  		{
	 235  			name:	 "LargeBetweenLow",
	 236  			base:	 14,
	 237  			expect: 2,
	 238  			ranges: large,
	 239  		},
	 240  		{
	 241  			name:	 "LargeBetweenHigh",
	 242  			base:	 249,
	 243  			expect: 49,
	 244  			ranges: large,
	 245  		},
	 246  		{
	 247  			name:	 "LargeWithinLow",
	 248  			base:	 25,
	 249  			expect: 5,
	 250  			ranges: large,
	 251  		},
	 252  		{
	 253  			name:	 "LargeWithinHigh",
	 254  			base:	 396,
	 255  			expect: 79,
	 256  			ranges: large,
	 257  		},
	 258  		{
	 259  			name:	 "LargeWithinMiddle",
	 260  			base:	 250,
	 261  			expect: 50,
	 262  			ranges: large,
	 263  		},
	 264  	}
	 265  
	 266  	for _, test := range tests {
	 267  		t.Run(test.name, func(t *testing.T) {
	 268  			a := MakeAddrRanges(test.ranges...)
	 269  			i := a.FindSucc(test.base)
	 270  			if i != test.expect {
	 271  				t.Fatalf("expected %d, got %d", test.expect, i)
	 272  			}
	 273  		})
	 274  	}
	 275  }
	 276
View as plain text