Source file src/runtime/mpagealloc_test.go

Documentation: runtime

		 1  // Copyright 2019 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  	"fmt"
		 9  	. "runtime"
		10  	"runtime/internal/sys"
		11  	"testing"
		12  )
		13  
		14  func checkPageAlloc(t *testing.T, want, got *PageAlloc) {
		15  	// Ensure start and end are correct.
		16  	wantStart, wantEnd := want.Bounds()
		17  	gotStart, gotEnd := got.Bounds()
		18  	if gotStart != wantStart {
		19  		t.Fatalf("start values not equal: got %d, want %d", gotStart, wantStart)
		20  	}
		21  	if gotEnd != wantEnd {
		22  		t.Fatalf("end values not equal: got %d, want %d", gotEnd, wantEnd)
		23  	}
		24  
		25  	for i := gotStart; i < gotEnd; i++ {
		26  		// Check the bitmaps. Note that we may have nil data.
		27  		gb, wb := got.PallocData(i), want.PallocData(i)
		28  		if gb == nil && wb == nil {
		29  			continue
		30  		}
		31  		if (gb == nil && wb != nil) || (gb != nil && wb == nil) {
		32  			t.Errorf("chunk %d nilness mismatch", i)
		33  		}
		34  		if !checkPallocBits(t, gb.PallocBits(), wb.PallocBits()) {
		35  			t.Logf("in chunk %d (mallocBits)", i)
		36  		}
		37  		if !checkPallocBits(t, gb.Scavenged(), wb.Scavenged()) {
		38  			t.Logf("in chunk %d (scavenged)", i)
		39  		}
		40  	}
		41  	// TODO(mknyszek): Verify summaries too?
		42  }
		43  
		44  func TestPageAllocGrow(t *testing.T) {
		45  	if GOOS == "openbsd" && testing.Short() {
		46  		t.Skip("skipping because virtual memory is limited; see #36210")
		47  	}
		48  	type test struct {
		49  		chunks []ChunkIdx
		50  		inUse	[]AddrRange
		51  	}
		52  	tests := map[string]test{
		53  		"One": {
		54  			chunks: []ChunkIdx{
		55  				BaseChunkIdx,
		56  			},
		57  			inUse: []AddrRange{
		58  				MakeAddrRange(PageBase(BaseChunkIdx, 0), PageBase(BaseChunkIdx+1, 0)),
		59  			},
		60  		},
		61  		"Contiguous2": {
		62  			chunks: []ChunkIdx{
		63  				BaseChunkIdx,
		64  				BaseChunkIdx + 1,
		65  			},
		66  			inUse: []AddrRange{
		67  				MakeAddrRange(PageBase(BaseChunkIdx, 0), PageBase(BaseChunkIdx+2, 0)),
		68  			},
		69  		},
		70  		"Contiguous5": {
		71  			chunks: []ChunkIdx{
		72  				BaseChunkIdx,
		73  				BaseChunkIdx + 1,
		74  				BaseChunkIdx + 2,
		75  				BaseChunkIdx + 3,
		76  				BaseChunkIdx + 4,
		77  			},
		78  			inUse: []AddrRange{
		79  				MakeAddrRange(PageBase(BaseChunkIdx, 0), PageBase(BaseChunkIdx+5, 0)),
		80  			},
		81  		},
		82  		"Discontiguous": {
		83  			chunks: []ChunkIdx{
		84  				BaseChunkIdx,
		85  				BaseChunkIdx + 2,
		86  				BaseChunkIdx + 4,
		87  			},
		88  			inUse: []AddrRange{
		89  				MakeAddrRange(PageBase(BaseChunkIdx, 0), PageBase(BaseChunkIdx+1, 0)),
		90  				MakeAddrRange(PageBase(BaseChunkIdx+2, 0), PageBase(BaseChunkIdx+3, 0)),
		91  				MakeAddrRange(PageBase(BaseChunkIdx+4, 0), PageBase(BaseChunkIdx+5, 0)),
		92  			},
		93  		},
		94  		"Mixed": {
		95  			chunks: []ChunkIdx{
		96  				BaseChunkIdx,
		97  				BaseChunkIdx + 1,
		98  				BaseChunkIdx + 2,
		99  				BaseChunkIdx + 4,
	 100  			},
	 101  			inUse: []AddrRange{
	 102  				MakeAddrRange(PageBase(BaseChunkIdx, 0), PageBase(BaseChunkIdx+3, 0)),
	 103  				MakeAddrRange(PageBase(BaseChunkIdx+4, 0), PageBase(BaseChunkIdx+5, 0)),
	 104  			},
	 105  		},
	 106  		"WildlyDiscontiguous": {
	 107  			chunks: []ChunkIdx{
	 108  				BaseChunkIdx,
	 109  				BaseChunkIdx + 1,
	 110  				BaseChunkIdx + 0x10,
	 111  				BaseChunkIdx + 0x21,
	 112  			},
	 113  			inUse: []AddrRange{
	 114  				MakeAddrRange(PageBase(BaseChunkIdx, 0), PageBase(BaseChunkIdx+2, 0)),
	 115  				MakeAddrRange(PageBase(BaseChunkIdx+0x10, 0), PageBase(BaseChunkIdx+0x11, 0)),
	 116  				MakeAddrRange(PageBase(BaseChunkIdx+0x21, 0), PageBase(BaseChunkIdx+0x22, 0)),
	 117  			},
	 118  		},
	 119  		"ManyDiscontiguous": {
	 120  			// The initial cap is 16. Test 33 ranges, to exercise the growth path (twice).
	 121  			chunks: []ChunkIdx{
	 122  				BaseChunkIdx, BaseChunkIdx + 2, BaseChunkIdx + 4, BaseChunkIdx + 6,
	 123  				BaseChunkIdx + 8, BaseChunkIdx + 10, BaseChunkIdx + 12, BaseChunkIdx + 14,
	 124  				BaseChunkIdx + 16, BaseChunkIdx + 18, BaseChunkIdx + 20, BaseChunkIdx + 22,
	 125  				BaseChunkIdx + 24, BaseChunkIdx + 26, BaseChunkIdx + 28, BaseChunkIdx + 30,
	 126  				BaseChunkIdx + 32, BaseChunkIdx + 34, BaseChunkIdx + 36, BaseChunkIdx + 38,
	 127  				BaseChunkIdx + 40, BaseChunkIdx + 42, BaseChunkIdx + 44, BaseChunkIdx + 46,
	 128  				BaseChunkIdx + 48, BaseChunkIdx + 50, BaseChunkIdx + 52, BaseChunkIdx + 54,
	 129  				BaseChunkIdx + 56, BaseChunkIdx + 58, BaseChunkIdx + 60, BaseChunkIdx + 62,
	 130  				BaseChunkIdx + 64,
	 131  			},
	 132  			inUse: []AddrRange{
	 133  				MakeAddrRange(PageBase(BaseChunkIdx, 0), PageBase(BaseChunkIdx+1, 0)),
	 134  				MakeAddrRange(PageBase(BaseChunkIdx+2, 0), PageBase(BaseChunkIdx+3, 0)),
	 135  				MakeAddrRange(PageBase(BaseChunkIdx+4, 0), PageBase(BaseChunkIdx+5, 0)),
	 136  				MakeAddrRange(PageBase(BaseChunkIdx+6, 0), PageBase(BaseChunkIdx+7, 0)),
	 137  				MakeAddrRange(PageBase(BaseChunkIdx+8, 0), PageBase(BaseChunkIdx+9, 0)),
	 138  				MakeAddrRange(PageBase(BaseChunkIdx+10, 0), PageBase(BaseChunkIdx+11, 0)),
	 139  				MakeAddrRange(PageBase(BaseChunkIdx+12, 0), PageBase(BaseChunkIdx+13, 0)),
	 140  				MakeAddrRange(PageBase(BaseChunkIdx+14, 0), PageBase(BaseChunkIdx+15, 0)),
	 141  				MakeAddrRange(PageBase(BaseChunkIdx+16, 0), PageBase(BaseChunkIdx+17, 0)),
	 142  				MakeAddrRange(PageBase(BaseChunkIdx+18, 0), PageBase(BaseChunkIdx+19, 0)),
	 143  				MakeAddrRange(PageBase(BaseChunkIdx+20, 0), PageBase(BaseChunkIdx+21, 0)),
	 144  				MakeAddrRange(PageBase(BaseChunkIdx+22, 0), PageBase(BaseChunkIdx+23, 0)),
	 145  				MakeAddrRange(PageBase(BaseChunkIdx+24, 0), PageBase(BaseChunkIdx+25, 0)),
	 146  				MakeAddrRange(PageBase(BaseChunkIdx+26, 0), PageBase(BaseChunkIdx+27, 0)),
	 147  				MakeAddrRange(PageBase(BaseChunkIdx+28, 0), PageBase(BaseChunkIdx+29, 0)),
	 148  				MakeAddrRange(PageBase(BaseChunkIdx+30, 0), PageBase(BaseChunkIdx+31, 0)),
	 149  				MakeAddrRange(PageBase(BaseChunkIdx+32, 0), PageBase(BaseChunkIdx+33, 0)),
	 150  				MakeAddrRange(PageBase(BaseChunkIdx+34, 0), PageBase(BaseChunkIdx+35, 0)),
	 151  				MakeAddrRange(PageBase(BaseChunkIdx+36, 0), PageBase(BaseChunkIdx+37, 0)),
	 152  				MakeAddrRange(PageBase(BaseChunkIdx+38, 0), PageBase(BaseChunkIdx+39, 0)),
	 153  				MakeAddrRange(PageBase(BaseChunkIdx+40, 0), PageBase(BaseChunkIdx+41, 0)),
	 154  				MakeAddrRange(PageBase(BaseChunkIdx+42, 0), PageBase(BaseChunkIdx+43, 0)),
	 155  				MakeAddrRange(PageBase(BaseChunkIdx+44, 0), PageBase(BaseChunkIdx+45, 0)),
	 156  				MakeAddrRange(PageBase(BaseChunkIdx+46, 0), PageBase(BaseChunkIdx+47, 0)),
	 157  				MakeAddrRange(PageBase(BaseChunkIdx+48, 0), PageBase(BaseChunkIdx+49, 0)),
	 158  				MakeAddrRange(PageBase(BaseChunkIdx+50, 0), PageBase(BaseChunkIdx+51, 0)),
	 159  				MakeAddrRange(PageBase(BaseChunkIdx+52, 0), PageBase(BaseChunkIdx+53, 0)),
	 160  				MakeAddrRange(PageBase(BaseChunkIdx+54, 0), PageBase(BaseChunkIdx+55, 0)),
	 161  				MakeAddrRange(PageBase(BaseChunkIdx+56, 0), PageBase(BaseChunkIdx+57, 0)),
	 162  				MakeAddrRange(PageBase(BaseChunkIdx+58, 0), PageBase(BaseChunkIdx+59, 0)),
	 163  				MakeAddrRange(PageBase(BaseChunkIdx+60, 0), PageBase(BaseChunkIdx+61, 0)),
	 164  				MakeAddrRange(PageBase(BaseChunkIdx+62, 0), PageBase(BaseChunkIdx+63, 0)),
	 165  				MakeAddrRange(PageBase(BaseChunkIdx+64, 0), PageBase(BaseChunkIdx+65, 0)),
	 166  			},
	 167  		},
	 168  	}
	 169  	// Disable these tests on iOS since we have a small address space.
	 170  	// See #46860.
	 171  	if PageAlloc64Bit != 0 && sys.GoosIos == 0 {
	 172  		tests["ExtremelyDiscontiguous"] = test{
	 173  			chunks: []ChunkIdx{
	 174  				BaseChunkIdx,
	 175  				BaseChunkIdx + 0x100000, // constant translates to O(TiB)
	 176  			},
	 177  			inUse: []AddrRange{
	 178  				MakeAddrRange(PageBase(BaseChunkIdx, 0), PageBase(BaseChunkIdx+1, 0)),
	 179  				MakeAddrRange(PageBase(BaseChunkIdx+0x100000, 0), PageBase(BaseChunkIdx+0x100001, 0)),
	 180  			},
	 181  		}
	 182  	}
	 183  	for name, v := range tests {
	 184  		v := v
	 185  		t.Run(name, func(t *testing.T) {
	 186  			// By creating a new pageAlloc, we will
	 187  			// grow it for each chunk defined in x.
	 188  			x := make(map[ChunkIdx][]BitRange)
	 189  			for _, c := range v.chunks {
	 190  				x[c] = []BitRange{}
	 191  			}
	 192  			b := NewPageAlloc(x, nil)
	 193  			defer FreePageAlloc(b)
	 194  
	 195  			got := b.InUse()
	 196  			want := v.inUse
	 197  
	 198  			// Check for mismatches.
	 199  			if len(got) != len(want) {
	 200  				t.Fail()
	 201  			} else {
	 202  				for i := range want {
	 203  					if !want[i].Equals(got[i]) {
	 204  						t.Fail()
	 205  						break
	 206  					}
	 207  				}
	 208  			}
	 209  			if t.Failed() {
	 210  				t.Logf("found inUse mismatch")
	 211  				t.Logf("got:")
	 212  				for i, r := range got {
	 213  					t.Logf("\t#%d [0x%x, 0x%x)", i, r.Base(), r.Limit())
	 214  				}
	 215  				t.Logf("want:")
	 216  				for i, r := range want {
	 217  					t.Logf("\t#%d [0x%x, 0x%x)", i, r.Base(), r.Limit())
	 218  				}
	 219  			}
	 220  		})
	 221  	}
	 222  }
	 223  
	 224  func TestPageAllocAlloc(t *testing.T) {
	 225  	if GOOS == "openbsd" && testing.Short() {
	 226  		t.Skip("skipping because virtual memory is limited; see #36210")
	 227  	}
	 228  	type hit struct {
	 229  		npages, base, scav uintptr
	 230  	}
	 231  	type test struct {
	 232  		scav	 map[ChunkIdx][]BitRange
	 233  		before map[ChunkIdx][]BitRange
	 234  		after	map[ChunkIdx][]BitRange
	 235  		hits	 []hit
	 236  	}
	 237  	tests := map[string]test{
	 238  		"AllFree1": {
	 239  			before: map[ChunkIdx][]BitRange{
	 240  				BaseChunkIdx: {},
	 241  			},
	 242  			scav: map[ChunkIdx][]BitRange{
	 243  				BaseChunkIdx: {{0, 1}, {2, 2}},
	 244  			},
	 245  			hits: []hit{
	 246  				{1, PageBase(BaseChunkIdx, 0), PageSize},
	 247  				{1, PageBase(BaseChunkIdx, 1), 0},
	 248  				{1, PageBase(BaseChunkIdx, 2), PageSize},
	 249  				{1, PageBase(BaseChunkIdx, 3), PageSize},
	 250  				{1, PageBase(BaseChunkIdx, 4), 0},
	 251  			},
	 252  			after: map[ChunkIdx][]BitRange{
	 253  				BaseChunkIdx: {{0, 5}},
	 254  			},
	 255  		},
	 256  		"ManyArena1": {
	 257  			before: map[ChunkIdx][]BitRange{
	 258  				BaseChunkIdx:		 {{0, PallocChunkPages}},
	 259  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
	 260  				BaseChunkIdx + 2: {{0, PallocChunkPages - 1}},
	 261  			},
	 262  			scav: map[ChunkIdx][]BitRange{
	 263  				BaseChunkIdx:		 {{0, PallocChunkPages}},
	 264  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
	 265  				BaseChunkIdx + 2: {{0, PallocChunkPages}},
	 266  			},
	 267  			hits: []hit{
	 268  				{1, PageBase(BaseChunkIdx+2, PallocChunkPages-1), PageSize},
	 269  			},
	 270  			after: map[ChunkIdx][]BitRange{
	 271  				BaseChunkIdx:		 {{0, PallocChunkPages}},
	 272  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
	 273  				BaseChunkIdx + 2: {{0, PallocChunkPages}},
	 274  			},
	 275  		},
	 276  		"NotContiguous1": {
	 277  			before: map[ChunkIdx][]BitRange{
	 278  				BaseChunkIdx:				{{0, PallocChunkPages}},
	 279  				BaseChunkIdx + 0xff: {{0, 0}},
	 280  			},
	 281  			scav: map[ChunkIdx][]BitRange{
	 282  				BaseChunkIdx:				{{0, PallocChunkPages}},
	 283  				BaseChunkIdx + 0xff: {{0, PallocChunkPages}},
	 284  			},
	 285  			hits: []hit{
	 286  				{1, PageBase(BaseChunkIdx+0xff, 0), PageSize},
	 287  			},
	 288  			after: map[ChunkIdx][]BitRange{
	 289  				BaseChunkIdx:				{{0, PallocChunkPages}},
	 290  				BaseChunkIdx + 0xff: {{0, 1}},
	 291  			},
	 292  		},
	 293  		"AllFree2": {
	 294  			before: map[ChunkIdx][]BitRange{
	 295  				BaseChunkIdx: {},
	 296  			},
	 297  			scav: map[ChunkIdx][]BitRange{
	 298  				BaseChunkIdx: {{0, 3}, {7, 1}},
	 299  			},
	 300  			hits: []hit{
	 301  				{2, PageBase(BaseChunkIdx, 0), 2 * PageSize},
	 302  				{2, PageBase(BaseChunkIdx, 2), PageSize},
	 303  				{2, PageBase(BaseChunkIdx, 4), 0},
	 304  				{2, PageBase(BaseChunkIdx, 6), PageSize},
	 305  				{2, PageBase(BaseChunkIdx, 8), 0},
	 306  			},
	 307  			after: map[ChunkIdx][]BitRange{
	 308  				BaseChunkIdx: {{0, 10}},
	 309  			},
	 310  		},
	 311  		"Straddle2": {
	 312  			before: map[ChunkIdx][]BitRange{
	 313  				BaseChunkIdx:		 {{0, PallocChunkPages - 1}},
	 314  				BaseChunkIdx + 1: {{1, PallocChunkPages - 1}},
	 315  			},
	 316  			scav: map[ChunkIdx][]BitRange{
	 317  				BaseChunkIdx:		 {{PallocChunkPages - 1, 1}},
	 318  				BaseChunkIdx + 1: {},
	 319  			},
	 320  			hits: []hit{
	 321  				{2, PageBase(BaseChunkIdx, PallocChunkPages-1), PageSize},
	 322  			},
	 323  			after: map[ChunkIdx][]BitRange{
	 324  				BaseChunkIdx:		 {{0, PallocChunkPages}},
	 325  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
	 326  			},
	 327  		},
	 328  		"AllFree5": {
	 329  			before: map[ChunkIdx][]BitRange{
	 330  				BaseChunkIdx: {},
	 331  			},
	 332  			scav: map[ChunkIdx][]BitRange{
	 333  				BaseChunkIdx: {{0, 8}, {9, 1}, {17, 5}},
	 334  			},
	 335  			hits: []hit{
	 336  				{5, PageBase(BaseChunkIdx, 0), 5 * PageSize},
	 337  				{5, PageBase(BaseChunkIdx, 5), 4 * PageSize},
	 338  				{5, PageBase(BaseChunkIdx, 10), 0},
	 339  				{5, PageBase(BaseChunkIdx, 15), 3 * PageSize},
	 340  				{5, PageBase(BaseChunkIdx, 20), 2 * PageSize},
	 341  			},
	 342  			after: map[ChunkIdx][]BitRange{
	 343  				BaseChunkIdx: {{0, 25}},
	 344  			},
	 345  		},
	 346  		"AllFree64": {
	 347  			before: map[ChunkIdx][]BitRange{
	 348  				BaseChunkIdx: {},
	 349  			},
	 350  			scav: map[ChunkIdx][]BitRange{
	 351  				BaseChunkIdx: {{21, 1}, {63, 65}},
	 352  			},
	 353  			hits: []hit{
	 354  				{64, PageBase(BaseChunkIdx, 0), 2 * PageSize},
	 355  				{64, PageBase(BaseChunkIdx, 64), 64 * PageSize},
	 356  				{64, PageBase(BaseChunkIdx, 128), 0},
	 357  			},
	 358  			after: map[ChunkIdx][]BitRange{
	 359  				BaseChunkIdx: {{0, 192}},
	 360  			},
	 361  		},
	 362  		"AllFree65": {
	 363  			before: map[ChunkIdx][]BitRange{
	 364  				BaseChunkIdx: {},
	 365  			},
	 366  			scav: map[ChunkIdx][]BitRange{
	 367  				BaseChunkIdx: {{129, 1}},
	 368  			},
	 369  			hits: []hit{
	 370  				{65, PageBase(BaseChunkIdx, 0), 0},
	 371  				{65, PageBase(BaseChunkIdx, 65), PageSize},
	 372  				{65, PageBase(BaseChunkIdx, 130), 0},
	 373  			},
	 374  			after: map[ChunkIdx][]BitRange{
	 375  				BaseChunkIdx: {{0, 195}},
	 376  			},
	 377  		},
	 378  		"ExhaustPallocChunkPages-3": {
	 379  			before: map[ChunkIdx][]BitRange{
	 380  				BaseChunkIdx: {},
	 381  			},
	 382  			scav: map[ChunkIdx][]BitRange{
	 383  				BaseChunkIdx: {{10, 1}},
	 384  			},
	 385  			hits: []hit{
	 386  				{PallocChunkPages - 3, PageBase(BaseChunkIdx, 0), PageSize},
	 387  				{PallocChunkPages - 3, 0, 0},
	 388  				{1, PageBase(BaseChunkIdx, PallocChunkPages-3), 0},
	 389  				{2, PageBase(BaseChunkIdx, PallocChunkPages-2), 0},
	 390  				{1, 0, 0},
	 391  				{PallocChunkPages - 3, 0, 0},
	 392  			},
	 393  			after: map[ChunkIdx][]BitRange{
	 394  				BaseChunkIdx: {{0, PallocChunkPages}},
	 395  			},
	 396  		},
	 397  		"AllFreePallocChunkPages": {
	 398  			before: map[ChunkIdx][]BitRange{
	 399  				BaseChunkIdx: {},
	 400  			},
	 401  			scav: map[ChunkIdx][]BitRange{
	 402  				BaseChunkIdx: {{0, 1}, {PallocChunkPages - 1, 1}},
	 403  			},
	 404  			hits: []hit{
	 405  				{PallocChunkPages, PageBase(BaseChunkIdx, 0), 2 * PageSize},
	 406  				{PallocChunkPages, 0, 0},
	 407  				{1, 0, 0},
	 408  			},
	 409  			after: map[ChunkIdx][]BitRange{
	 410  				BaseChunkIdx: {{0, PallocChunkPages}},
	 411  			},
	 412  		},
	 413  		"StraddlePallocChunkPages": {
	 414  			before: map[ChunkIdx][]BitRange{
	 415  				BaseChunkIdx:		 {{0, PallocChunkPages / 2}},
	 416  				BaseChunkIdx + 1: {{PallocChunkPages / 2, PallocChunkPages / 2}},
	 417  			},
	 418  			scav: map[ChunkIdx][]BitRange{
	 419  				BaseChunkIdx:		 {},
	 420  				BaseChunkIdx + 1: {{3, 100}},
	 421  			},
	 422  			hits: []hit{
	 423  				{PallocChunkPages, PageBase(BaseChunkIdx, PallocChunkPages/2), 100 * PageSize},
	 424  				{PallocChunkPages, 0, 0},
	 425  				{1, 0, 0},
	 426  			},
	 427  			after: map[ChunkIdx][]BitRange{
	 428  				BaseChunkIdx:		 {{0, PallocChunkPages}},
	 429  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
	 430  			},
	 431  		},
	 432  		"StraddlePallocChunkPages+1": {
	 433  			before: map[ChunkIdx][]BitRange{
	 434  				BaseChunkIdx:		 {{0, PallocChunkPages / 2}},
	 435  				BaseChunkIdx + 1: {},
	 436  			},
	 437  			scav: map[ChunkIdx][]BitRange{
	 438  				BaseChunkIdx:		 {{0, PallocChunkPages}},
	 439  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
	 440  			},
	 441  			hits: []hit{
	 442  				{PallocChunkPages + 1, PageBase(BaseChunkIdx, PallocChunkPages/2), (PallocChunkPages + 1) * PageSize},
	 443  				{PallocChunkPages, 0, 0},
	 444  				{1, PageBase(BaseChunkIdx+1, PallocChunkPages/2+1), PageSize},
	 445  			},
	 446  			after: map[ChunkIdx][]BitRange{
	 447  				BaseChunkIdx:		 {{0, PallocChunkPages}},
	 448  				BaseChunkIdx + 1: {{0, PallocChunkPages/2 + 2}},
	 449  			},
	 450  		},
	 451  		"AllFreePallocChunkPages*2": {
	 452  			before: map[ChunkIdx][]BitRange{
	 453  				BaseChunkIdx:		 {},
	 454  				BaseChunkIdx + 1: {},
	 455  			},
	 456  			scav: map[ChunkIdx][]BitRange{
	 457  				BaseChunkIdx:		 {},
	 458  				BaseChunkIdx + 1: {},
	 459  			},
	 460  			hits: []hit{
	 461  				{PallocChunkPages * 2, PageBase(BaseChunkIdx, 0), 0},
	 462  				{PallocChunkPages * 2, 0, 0},
	 463  				{1, 0, 0},
	 464  			},
	 465  			after: map[ChunkIdx][]BitRange{
	 466  				BaseChunkIdx:		 {{0, PallocChunkPages}},
	 467  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
	 468  			},
	 469  		},
	 470  		"NotContiguousPallocChunkPages*2": {
	 471  			before: map[ChunkIdx][]BitRange{
	 472  				BaseChunkIdx:				{},
	 473  				BaseChunkIdx + 0x40: {},
	 474  				BaseChunkIdx + 0x41: {},
	 475  			},
	 476  			scav: map[ChunkIdx][]BitRange{
	 477  				BaseChunkIdx:				{{0, PallocChunkPages}},
	 478  				BaseChunkIdx + 0x40: {},
	 479  				BaseChunkIdx + 0x41: {},
	 480  			},
	 481  			hits: []hit{
	 482  				{PallocChunkPages * 2, PageBase(BaseChunkIdx+0x40, 0), 0},
	 483  				{21, PageBase(BaseChunkIdx, 0), 21 * PageSize},
	 484  				{1, PageBase(BaseChunkIdx, 21), PageSize},
	 485  			},
	 486  			after: map[ChunkIdx][]BitRange{
	 487  				BaseChunkIdx:				{{0, 22}},
	 488  				BaseChunkIdx + 0x40: {{0, PallocChunkPages}},
	 489  				BaseChunkIdx + 0x41: {{0, PallocChunkPages}},
	 490  			},
	 491  		},
	 492  		"StraddlePallocChunkPages*2": {
	 493  			before: map[ChunkIdx][]BitRange{
	 494  				BaseChunkIdx:		 {{0, PallocChunkPages / 2}},
	 495  				BaseChunkIdx + 1: {},
	 496  				BaseChunkIdx + 2: {{PallocChunkPages / 2, PallocChunkPages / 2}},
	 497  			},
	 498  			scav: map[ChunkIdx][]BitRange{
	 499  				BaseChunkIdx:		 {{0, 7}},
	 500  				BaseChunkIdx + 1: {{3, 5}, {121, 10}},
	 501  				BaseChunkIdx + 2: {{PallocChunkPages/2 + 12, 2}},
	 502  			},
	 503  			hits: []hit{
	 504  				{PallocChunkPages * 2, PageBase(BaseChunkIdx, PallocChunkPages/2), 15 * PageSize},
	 505  				{PallocChunkPages * 2, 0, 0},
	 506  				{1, 0, 0},
	 507  			},
	 508  			after: map[ChunkIdx][]BitRange{
	 509  				BaseChunkIdx:		 {{0, PallocChunkPages}},
	 510  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
	 511  				BaseChunkIdx + 2: {{0, PallocChunkPages}},
	 512  			},
	 513  		},
	 514  		"StraddlePallocChunkPages*5/4": {
	 515  			before: map[ChunkIdx][]BitRange{
	 516  				BaseChunkIdx:		 {{0, PallocChunkPages}},
	 517  				BaseChunkIdx + 1: {{0, PallocChunkPages * 3 / 4}},
	 518  				BaseChunkIdx + 2: {{0, PallocChunkPages * 3 / 4}},
	 519  				BaseChunkIdx + 3: {{0, 0}},
	 520  			},
	 521  			scav: map[ChunkIdx][]BitRange{
	 522  				BaseChunkIdx:		 {{0, PallocChunkPages}},
	 523  				BaseChunkIdx + 1: {{PallocChunkPages / 2, PallocChunkPages/4 + 1}},
	 524  				BaseChunkIdx + 2: {{PallocChunkPages / 3, 1}},
	 525  				BaseChunkIdx + 3: {{PallocChunkPages * 2 / 3, 1}},
	 526  			},
	 527  			hits: []hit{
	 528  				{PallocChunkPages * 5 / 4, PageBase(BaseChunkIdx+2, PallocChunkPages*3/4), PageSize},
	 529  				{PallocChunkPages * 5 / 4, 0, 0},
	 530  				{1, PageBase(BaseChunkIdx+1, PallocChunkPages*3/4), PageSize},
	 531  			},
	 532  			after: map[ChunkIdx][]BitRange{
	 533  				BaseChunkIdx:		 {{0, PallocChunkPages}},
	 534  				BaseChunkIdx + 1: {{0, PallocChunkPages*3/4 + 1}},
	 535  				BaseChunkIdx + 2: {{0, PallocChunkPages}},
	 536  				BaseChunkIdx + 3: {{0, PallocChunkPages}},
	 537  			},
	 538  		},
	 539  		"AllFreePallocChunkPages*7+5": {
	 540  			before: map[ChunkIdx][]BitRange{
	 541  				BaseChunkIdx:		 {},
	 542  				BaseChunkIdx + 1: {},
	 543  				BaseChunkIdx + 2: {},
	 544  				BaseChunkIdx + 3: {},
	 545  				BaseChunkIdx + 4: {},
	 546  				BaseChunkIdx + 5: {},
	 547  				BaseChunkIdx + 6: {},
	 548  				BaseChunkIdx + 7: {},
	 549  			},
	 550  			scav: map[ChunkIdx][]BitRange{
	 551  				BaseChunkIdx:		 {{50, 1}},
	 552  				BaseChunkIdx + 1: {{31, 1}},
	 553  				BaseChunkIdx + 2: {{7, 1}},
	 554  				BaseChunkIdx + 3: {{200, 1}},
	 555  				BaseChunkIdx + 4: {{3, 1}},
	 556  				BaseChunkIdx + 5: {{51, 1}},
	 557  				BaseChunkIdx + 6: {{20, 1}},
	 558  				BaseChunkIdx + 7: {{1, 1}},
	 559  			},
	 560  			hits: []hit{
	 561  				{PallocChunkPages*7 + 5, PageBase(BaseChunkIdx, 0), 8 * PageSize},
	 562  				{PallocChunkPages*7 + 5, 0, 0},
	 563  				{1, PageBase(BaseChunkIdx+7, 5), 0},
	 564  			},
	 565  			after: map[ChunkIdx][]BitRange{
	 566  				BaseChunkIdx:		 {{0, PallocChunkPages}},
	 567  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
	 568  				BaseChunkIdx + 2: {{0, PallocChunkPages}},
	 569  				BaseChunkIdx + 3: {{0, PallocChunkPages}},
	 570  				BaseChunkIdx + 4: {{0, PallocChunkPages}},
	 571  				BaseChunkIdx + 5: {{0, PallocChunkPages}},
	 572  				BaseChunkIdx + 6: {{0, PallocChunkPages}},
	 573  				BaseChunkIdx + 7: {{0, 6}},
	 574  			},
	 575  		},
	 576  	}
	 577  	// Disable these tests on iOS since we have a small address space.
	 578  	// See #46860.
	 579  	if PageAlloc64Bit != 0 && sys.GoosIos == 0 {
	 580  		const chunkIdxBigJump = 0x100000 // chunk index offset which translates to O(TiB)
	 581  
	 582  		// This test attempts to trigger a bug wherein we look at unmapped summary
	 583  		// memory that isn't just in the case where we exhaust the heap.
	 584  		//
	 585  		// It achieves this by placing a chunk such that its summary will be
	 586  		// at the very end of a physical page. It then also places another chunk
	 587  		// much further up in the address space, such that any allocations into the
	 588  		// first chunk do not exhaust the heap and the second chunk's summary is not in the
	 589  		// page immediately adjacent to the first chunk's summary's page.
	 590  		// Allocating into this first chunk to exhaustion and then into the second
	 591  		// chunk may then trigger a check in the allocator which erroneously looks at
	 592  		// unmapped summary memory and crashes.
	 593  
	 594  		// Figure out how many chunks are in a physical page, then align BaseChunkIdx
	 595  		// to a physical page in the chunk summary array. Here we only assume that
	 596  		// each summary array is aligned to some physical page.
	 597  		sumsPerPhysPage := ChunkIdx(PhysPageSize / PallocSumBytes)
	 598  		baseChunkIdx := BaseChunkIdx &^ (sumsPerPhysPage - 1)
	 599  		tests["DiscontiguousMappedSumBoundary"] = test{
	 600  			before: map[ChunkIdx][]BitRange{
	 601  				baseChunkIdx + sumsPerPhysPage - 1: {},
	 602  				baseChunkIdx + chunkIdxBigJump:		 {},
	 603  			},
	 604  			scav: map[ChunkIdx][]BitRange{
	 605  				baseChunkIdx + sumsPerPhysPage - 1: {},
	 606  				baseChunkIdx + chunkIdxBigJump:		 {},
	 607  			},
	 608  			hits: []hit{
	 609  				{PallocChunkPages - 1, PageBase(baseChunkIdx+sumsPerPhysPage-1, 0), 0},
	 610  				{1, PageBase(baseChunkIdx+sumsPerPhysPage-1, PallocChunkPages-1), 0},
	 611  				{1, PageBase(baseChunkIdx+chunkIdxBigJump, 0), 0},
	 612  				{PallocChunkPages - 1, PageBase(baseChunkIdx+chunkIdxBigJump, 1), 0},
	 613  				{1, 0, 0},
	 614  			},
	 615  			after: map[ChunkIdx][]BitRange{
	 616  				baseChunkIdx + sumsPerPhysPage - 1: {{0, PallocChunkPages}},
	 617  				baseChunkIdx + chunkIdxBigJump:		 {{0, PallocChunkPages}},
	 618  			},
	 619  		}
	 620  
	 621  		// Test to check for issue #40191. Essentially, the candidate searchAddr
	 622  		// discovered by find may not point to mapped memory, so we need to handle
	 623  		// that explicitly.
	 624  		//
	 625  		// chunkIdxSmallOffset is an offset intended to be used within chunkIdxBigJump.
	 626  		// It is far enough within chunkIdxBigJump that the summaries at the beginning
	 627  		// of an address range the size of chunkIdxBigJump will not be mapped in.
	 628  		const chunkIdxSmallOffset = 0x503
	 629  		tests["DiscontiguousBadSearchAddr"] = test{
	 630  			before: map[ChunkIdx][]BitRange{
	 631  				// The mechanism for the bug involves three chunks, A, B, and C, which are
	 632  				// far apart in the address space. In particular, B is chunkIdxBigJump +
	 633  				// chunkIdxSmalloffset chunks away from B, and C is 2*chunkIdxBigJump chunks
	 634  				// away from A. A has 1 page free, B has several (NOT at the end of B), and
	 635  				// C is totally free.
	 636  				// Note that B's free memory must not be at the end of B because the fast
	 637  				// path in the page allocator will check if the searchAddr even gives us
	 638  				// enough space to place the allocation in a chunk before accessing the
	 639  				// summary.
	 640  				BaseChunkIdx + chunkIdxBigJump*0: {{0, PallocChunkPages - 1}},
	 641  				BaseChunkIdx + chunkIdxBigJump*1 + chunkIdxSmallOffset: {
	 642  					{0, PallocChunkPages - 10},
	 643  					{PallocChunkPages - 1, 1},
	 644  				},
	 645  				BaseChunkIdx + chunkIdxBigJump*2: {},
	 646  			},
	 647  			scav: map[ChunkIdx][]BitRange{
	 648  				BaseChunkIdx + chunkIdxBigJump*0:											 {},
	 649  				BaseChunkIdx + chunkIdxBigJump*1 + chunkIdxSmallOffset: {},
	 650  				BaseChunkIdx + chunkIdxBigJump*2:											 {},
	 651  			},
	 652  			hits: []hit{
	 653  				// We first allocate into A to set the page allocator's searchAddr to the
	 654  				// end of that chunk. That is the only purpose A serves.
	 655  				{1, PageBase(BaseChunkIdx, PallocChunkPages-1), 0},
	 656  				// Then, we make a big allocation that doesn't fit into B, and so must be
	 657  				// fulfilled by C.
	 658  				//
	 659  				// On the way to fulfilling the allocation into C, we estimate searchAddr
	 660  				// using the summary structure, but that will give us a searchAddr of
	 661  				// B's base address minus chunkIdxSmallOffset chunks. These chunks will
	 662  				// not be mapped.
	 663  				{100, PageBase(baseChunkIdx+chunkIdxBigJump*2, 0), 0},
	 664  				// Now we try to make a smaller allocation that can be fulfilled by B.
	 665  				// In an older implementation of the page allocator, this will segfault,
	 666  				// because this last allocation will first try to access the summary
	 667  				// for B's base address minus chunkIdxSmallOffset chunks in the fast path,
	 668  				// and this will not be mapped.
	 669  				{9, PageBase(baseChunkIdx+chunkIdxBigJump*1+chunkIdxSmallOffset, PallocChunkPages-10), 0},
	 670  			},
	 671  			after: map[ChunkIdx][]BitRange{
	 672  				BaseChunkIdx + chunkIdxBigJump*0:											 {{0, PallocChunkPages}},
	 673  				BaseChunkIdx + chunkIdxBigJump*1 + chunkIdxSmallOffset: {{0, PallocChunkPages}},
	 674  				BaseChunkIdx + chunkIdxBigJump*2:											 {{0, 100}},
	 675  			},
	 676  		}
	 677  	}
	 678  	for name, v := range tests {
	 679  		v := v
	 680  		t.Run(name, func(t *testing.T) {
	 681  			b := NewPageAlloc(v.before, v.scav)
	 682  			defer FreePageAlloc(b)
	 683  
	 684  			for iter, i := range v.hits {
	 685  				a, s := b.Alloc(i.npages)
	 686  				if a != i.base {
	 687  					t.Fatalf("bad alloc #%d: want base 0x%x, got 0x%x", iter+1, i.base, a)
	 688  				}
	 689  				if s != i.scav {
	 690  					t.Fatalf("bad alloc #%d: want scav %d, got %d", iter+1, i.scav, s)
	 691  				}
	 692  			}
	 693  			want := NewPageAlloc(v.after, v.scav)
	 694  			defer FreePageAlloc(want)
	 695  
	 696  			checkPageAlloc(t, want, b)
	 697  		})
	 698  	}
	 699  }
	 700  
	 701  func TestPageAllocExhaust(t *testing.T) {
	 702  	if GOOS == "openbsd" && testing.Short() {
	 703  		t.Skip("skipping because virtual memory is limited; see #36210")
	 704  	}
	 705  	for _, npages := range []uintptr{1, 2, 3, 4, 5, 8, 16, 64, 1024, 1025, 2048, 2049} {
	 706  		npages := npages
	 707  		t.Run(fmt.Sprintf("%d", npages), func(t *testing.T) {
	 708  			// Construct b.
	 709  			bDesc := make(map[ChunkIdx][]BitRange)
	 710  			for i := ChunkIdx(0); i < 4; i++ {
	 711  				bDesc[BaseChunkIdx+i] = []BitRange{}
	 712  			}
	 713  			b := NewPageAlloc(bDesc, nil)
	 714  			defer FreePageAlloc(b)
	 715  
	 716  			// Allocate into b with npages until we've exhausted the heap.
	 717  			nAlloc := (PallocChunkPages * 4) / int(npages)
	 718  			for i := 0; i < nAlloc; i++ {
	 719  				addr := PageBase(BaseChunkIdx, uint(i)*uint(npages))
	 720  				if a, _ := b.Alloc(npages); a != addr {
	 721  					t.Fatalf("bad alloc #%d: want 0x%x, got 0x%x", i+1, addr, a)
	 722  				}
	 723  			}
	 724  
	 725  			// Check to make sure the next allocation fails.
	 726  			if a, _ := b.Alloc(npages); a != 0 {
	 727  				t.Fatalf("bad alloc #%d: want 0, got 0x%x", nAlloc, a)
	 728  			}
	 729  
	 730  			// Construct what we want the heap to look like now.
	 731  			allocPages := nAlloc * int(npages)
	 732  			wantDesc := make(map[ChunkIdx][]BitRange)
	 733  			for i := ChunkIdx(0); i < 4; i++ {
	 734  				if allocPages >= PallocChunkPages {
	 735  					wantDesc[BaseChunkIdx+i] = []BitRange{{0, PallocChunkPages}}
	 736  					allocPages -= PallocChunkPages
	 737  				} else if allocPages > 0 {
	 738  					wantDesc[BaseChunkIdx+i] = []BitRange{{0, uint(allocPages)}}
	 739  					allocPages = 0
	 740  				} else {
	 741  					wantDesc[BaseChunkIdx+i] = []BitRange{}
	 742  				}
	 743  			}
	 744  			want := NewPageAlloc(wantDesc, nil)
	 745  			defer FreePageAlloc(want)
	 746  
	 747  			// Check to make sure the heap b matches what we want.
	 748  			checkPageAlloc(t, want, b)
	 749  		})
	 750  	}
	 751  }
	 752  
	 753  func TestPageAllocFree(t *testing.T) {
	 754  	if GOOS == "openbsd" && testing.Short() {
	 755  		t.Skip("skipping because virtual memory is limited; see #36210")
	 756  	}
	 757  	tests := map[string]struct {
	 758  		before map[ChunkIdx][]BitRange
	 759  		after	map[ChunkIdx][]BitRange
	 760  		npages uintptr
	 761  		frees	[]uintptr
	 762  	}{
	 763  		"Free1": {
	 764  			npages: 1,
	 765  			before: map[ChunkIdx][]BitRange{
	 766  				BaseChunkIdx: {{0, PallocChunkPages}},
	 767  			},
	 768  			frees: []uintptr{
	 769  				PageBase(BaseChunkIdx, 0),
	 770  				PageBase(BaseChunkIdx, 1),
	 771  				PageBase(BaseChunkIdx, 2),
	 772  				PageBase(BaseChunkIdx, 3),
	 773  				PageBase(BaseChunkIdx, 4),
	 774  			},
	 775  			after: map[ChunkIdx][]BitRange{
	 776  				BaseChunkIdx: {{5, PallocChunkPages - 5}},
	 777  			},
	 778  		},
	 779  		"ManyArena1": {
	 780  			npages: 1,
	 781  			before: map[ChunkIdx][]BitRange{
	 782  				BaseChunkIdx:		 {{0, PallocChunkPages}},
	 783  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
	 784  				BaseChunkIdx + 2: {{0, PallocChunkPages}},
	 785  			},
	 786  			frees: []uintptr{
	 787  				PageBase(BaseChunkIdx, PallocChunkPages/2),
	 788  				PageBase(BaseChunkIdx+1, 0),
	 789  				PageBase(BaseChunkIdx+2, PallocChunkPages-1),
	 790  			},
	 791  			after: map[ChunkIdx][]BitRange{
	 792  				BaseChunkIdx:		 {{0, PallocChunkPages / 2}, {PallocChunkPages/2 + 1, PallocChunkPages/2 - 1}},
	 793  				BaseChunkIdx + 1: {{1, PallocChunkPages - 1}},
	 794  				BaseChunkIdx + 2: {{0, PallocChunkPages - 1}},
	 795  			},
	 796  		},
	 797  		"Free2": {
	 798  			npages: 2,
	 799  			before: map[ChunkIdx][]BitRange{
	 800  				BaseChunkIdx: {{0, PallocChunkPages}},
	 801  			},
	 802  			frees: []uintptr{
	 803  				PageBase(BaseChunkIdx, 0),
	 804  				PageBase(BaseChunkIdx, 2),
	 805  				PageBase(BaseChunkIdx, 4),
	 806  				PageBase(BaseChunkIdx, 6),
	 807  				PageBase(BaseChunkIdx, 8),
	 808  			},
	 809  			after: map[ChunkIdx][]BitRange{
	 810  				BaseChunkIdx: {{10, PallocChunkPages - 10}},
	 811  			},
	 812  		},
	 813  		"Straddle2": {
	 814  			npages: 2,
	 815  			before: map[ChunkIdx][]BitRange{
	 816  				BaseChunkIdx:		 {{PallocChunkPages - 1, 1}},
	 817  				BaseChunkIdx + 1: {{0, 1}},
	 818  			},
	 819  			frees: []uintptr{
	 820  				PageBase(BaseChunkIdx, PallocChunkPages-1),
	 821  			},
	 822  			after: map[ChunkIdx][]BitRange{
	 823  				BaseChunkIdx:		 {},
	 824  				BaseChunkIdx + 1: {},
	 825  			},
	 826  		},
	 827  		"Free5": {
	 828  			npages: 5,
	 829  			before: map[ChunkIdx][]BitRange{
	 830  				BaseChunkIdx: {{0, PallocChunkPages}},
	 831  			},
	 832  			frees: []uintptr{
	 833  				PageBase(BaseChunkIdx, 0),
	 834  				PageBase(BaseChunkIdx, 5),
	 835  				PageBase(BaseChunkIdx, 10),
	 836  				PageBase(BaseChunkIdx, 15),
	 837  				PageBase(BaseChunkIdx, 20),
	 838  			},
	 839  			after: map[ChunkIdx][]BitRange{
	 840  				BaseChunkIdx: {{25, PallocChunkPages - 25}},
	 841  			},
	 842  		},
	 843  		"Free64": {
	 844  			npages: 64,
	 845  			before: map[ChunkIdx][]BitRange{
	 846  				BaseChunkIdx: {{0, PallocChunkPages}},
	 847  			},
	 848  			frees: []uintptr{
	 849  				PageBase(BaseChunkIdx, 0),
	 850  				PageBase(BaseChunkIdx, 64),
	 851  				PageBase(BaseChunkIdx, 128),
	 852  			},
	 853  			after: map[ChunkIdx][]BitRange{
	 854  				BaseChunkIdx: {{192, PallocChunkPages - 192}},
	 855  			},
	 856  		},
	 857  		"Free65": {
	 858  			npages: 65,
	 859  			before: map[ChunkIdx][]BitRange{
	 860  				BaseChunkIdx: {{0, PallocChunkPages}},
	 861  			},
	 862  			frees: []uintptr{
	 863  				PageBase(BaseChunkIdx, 0),
	 864  				PageBase(BaseChunkIdx, 65),
	 865  				PageBase(BaseChunkIdx, 130),
	 866  			},
	 867  			after: map[ChunkIdx][]BitRange{
	 868  				BaseChunkIdx: {{195, PallocChunkPages - 195}},
	 869  			},
	 870  		},
	 871  		"FreePallocChunkPages": {
	 872  			npages: PallocChunkPages,
	 873  			before: map[ChunkIdx][]BitRange{
	 874  				BaseChunkIdx: {{0, PallocChunkPages}},
	 875  			},
	 876  			frees: []uintptr{
	 877  				PageBase(BaseChunkIdx, 0),
	 878  			},
	 879  			after: map[ChunkIdx][]BitRange{
	 880  				BaseChunkIdx: {},
	 881  			},
	 882  		},
	 883  		"StraddlePallocChunkPages": {
	 884  			npages: PallocChunkPages,
	 885  			before: map[ChunkIdx][]BitRange{
	 886  				BaseChunkIdx:		 {{PallocChunkPages / 2, PallocChunkPages / 2}},
	 887  				BaseChunkIdx + 1: {{0, PallocChunkPages / 2}},
	 888  			},
	 889  			frees: []uintptr{
	 890  				PageBase(BaseChunkIdx, PallocChunkPages/2),
	 891  			},
	 892  			after: map[ChunkIdx][]BitRange{
	 893  				BaseChunkIdx:		 {},
	 894  				BaseChunkIdx + 1: {},
	 895  			},
	 896  		},
	 897  		"StraddlePallocChunkPages+1": {
	 898  			npages: PallocChunkPages + 1,
	 899  			before: map[ChunkIdx][]BitRange{
	 900  				BaseChunkIdx:		 {{0, PallocChunkPages}},
	 901  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
	 902  			},
	 903  			frees: []uintptr{
	 904  				PageBase(BaseChunkIdx, PallocChunkPages/2),
	 905  			},
	 906  			after: map[ChunkIdx][]BitRange{
	 907  				BaseChunkIdx:		 {{0, PallocChunkPages / 2}},
	 908  				BaseChunkIdx + 1: {{PallocChunkPages/2 + 1, PallocChunkPages/2 - 1}},
	 909  			},
	 910  		},
	 911  		"FreePallocChunkPages*2": {
	 912  			npages: PallocChunkPages * 2,
	 913  			before: map[ChunkIdx][]BitRange{
	 914  				BaseChunkIdx:		 {{0, PallocChunkPages}},
	 915  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
	 916  			},
	 917  			frees: []uintptr{
	 918  				PageBase(BaseChunkIdx, 0),
	 919  			},
	 920  			after: map[ChunkIdx][]BitRange{
	 921  				BaseChunkIdx:		 {},
	 922  				BaseChunkIdx + 1: {},
	 923  			},
	 924  		},
	 925  		"StraddlePallocChunkPages*2": {
	 926  			npages: PallocChunkPages * 2,
	 927  			before: map[ChunkIdx][]BitRange{
	 928  				BaseChunkIdx:		 {{0, PallocChunkPages}},
	 929  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
	 930  				BaseChunkIdx + 2: {{0, PallocChunkPages}},
	 931  			},
	 932  			frees: []uintptr{
	 933  				PageBase(BaseChunkIdx, PallocChunkPages/2),
	 934  			},
	 935  			after: map[ChunkIdx][]BitRange{
	 936  				BaseChunkIdx:		 {{0, PallocChunkPages / 2}},
	 937  				BaseChunkIdx + 1: {},
	 938  				BaseChunkIdx + 2: {{PallocChunkPages / 2, PallocChunkPages / 2}},
	 939  			},
	 940  		},
	 941  		"AllFreePallocChunkPages*7+5": {
	 942  			npages: PallocChunkPages*7 + 5,
	 943  			before: map[ChunkIdx][]BitRange{
	 944  				BaseChunkIdx:		 {{0, PallocChunkPages}},
	 945  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
	 946  				BaseChunkIdx + 2: {{0, PallocChunkPages}},
	 947  				BaseChunkIdx + 3: {{0, PallocChunkPages}},
	 948  				BaseChunkIdx + 4: {{0, PallocChunkPages}},
	 949  				BaseChunkIdx + 5: {{0, PallocChunkPages}},
	 950  				BaseChunkIdx + 6: {{0, PallocChunkPages}},
	 951  				BaseChunkIdx + 7: {{0, PallocChunkPages}},
	 952  			},
	 953  			frees: []uintptr{
	 954  				PageBase(BaseChunkIdx, 0),
	 955  			},
	 956  			after: map[ChunkIdx][]BitRange{
	 957  				BaseChunkIdx:		 {},
	 958  				BaseChunkIdx + 1: {},
	 959  				BaseChunkIdx + 2: {},
	 960  				BaseChunkIdx + 3: {},
	 961  				BaseChunkIdx + 4: {},
	 962  				BaseChunkIdx + 5: {},
	 963  				BaseChunkIdx + 6: {},
	 964  				BaseChunkIdx + 7: {{5, PallocChunkPages - 5}},
	 965  			},
	 966  		},
	 967  	}
	 968  	for name, v := range tests {
	 969  		v := v
	 970  		t.Run(name, func(t *testing.T) {
	 971  			b := NewPageAlloc(v.before, nil)
	 972  			defer FreePageAlloc(b)
	 973  
	 974  			for _, addr := range v.frees {
	 975  				b.Free(addr, v.npages)
	 976  			}
	 977  			want := NewPageAlloc(v.after, nil)
	 978  			defer FreePageAlloc(want)
	 979  
	 980  			checkPageAlloc(t, want, b)
	 981  		})
	 982  	}
	 983  }
	 984  
	 985  func TestPageAllocAllocAndFree(t *testing.T) {
	 986  	if GOOS == "openbsd" && testing.Short() {
	 987  		t.Skip("skipping because virtual memory is limited; see #36210")
	 988  	}
	 989  	type hit struct {
	 990  		alloc	bool
	 991  		npages uintptr
	 992  		base	 uintptr
	 993  	}
	 994  	tests := map[string]struct {
	 995  		init map[ChunkIdx][]BitRange
	 996  		hits []hit
	 997  	}{
	 998  		// TODO(mknyszek): Write more tests here.
	 999  		"Chunks8": {
	1000  			init: map[ChunkIdx][]BitRange{
	1001  				BaseChunkIdx:		 {},
	1002  				BaseChunkIdx + 1: {},
	1003  				BaseChunkIdx + 2: {},
	1004  				BaseChunkIdx + 3: {},
	1005  				BaseChunkIdx + 4: {},
	1006  				BaseChunkIdx + 5: {},
	1007  				BaseChunkIdx + 6: {},
	1008  				BaseChunkIdx + 7: {},
	1009  			},
	1010  			hits: []hit{
	1011  				{true, PallocChunkPages * 8, PageBase(BaseChunkIdx, 0)},
	1012  				{false, PallocChunkPages * 8, PageBase(BaseChunkIdx, 0)},
	1013  				{true, PallocChunkPages * 8, PageBase(BaseChunkIdx, 0)},
	1014  				{false, PallocChunkPages * 8, PageBase(BaseChunkIdx, 0)},
	1015  				{true, PallocChunkPages * 8, PageBase(BaseChunkIdx, 0)},
	1016  				{false, PallocChunkPages * 8, PageBase(BaseChunkIdx, 0)},
	1017  				{true, 1, PageBase(BaseChunkIdx, 0)},
	1018  				{false, 1, PageBase(BaseChunkIdx, 0)},
	1019  				{true, PallocChunkPages * 8, PageBase(BaseChunkIdx, 0)},
	1020  			},
	1021  		},
	1022  	}
	1023  	for name, v := range tests {
	1024  		v := v
	1025  		t.Run(name, func(t *testing.T) {
	1026  			b := NewPageAlloc(v.init, nil)
	1027  			defer FreePageAlloc(b)
	1028  
	1029  			for iter, i := range v.hits {
	1030  				if i.alloc {
	1031  					if a, _ := b.Alloc(i.npages); a != i.base {
	1032  						t.Fatalf("bad alloc #%d: want 0x%x, got 0x%x", iter+1, i.base, a)
	1033  					}
	1034  				} else {
	1035  					b.Free(i.base, i.npages)
	1036  				}
	1037  			}
	1038  		})
	1039  	}
	1040  }
	1041  

View as plain text