mgcscavenge_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  	"math/rand"
		10  	. "runtime"
		11  	"runtime/internal/sys"
		12  	"testing"
		13  )
		14  
		15  // makePallocData produces an initialized PallocData by setting
		16  // the ranges of described in alloc and scavenge.
		17  func makePallocData(alloc, scavenged []BitRange) *PallocData {
		18  	b := new(PallocData)
		19  	for _, v := range alloc {
		20  		if v.N == 0 {
		21  			// Skip N==0. It's harmless and allocRange doesn't
		22  			// handle this case.
		23  			continue
		24  		}
		25  		b.AllocRange(v.I, v.N)
		26  	}
		27  	for _, v := range scavenged {
		28  		if v.N == 0 {
		29  			// See the previous loop.
		30  			continue
		31  		}
		32  		b.ScavengedSetRange(v.I, v.N)
		33  	}
		34  	return b
		35  }
		36  
		37  func TestFillAligned(t *testing.T) {
		38  	fillAlignedSlow := func(x uint64, m uint) uint64 {
		39  		if m == 1 {
		40  			return x
		41  		}
		42  		out := uint64(0)
		43  		for i := uint(0); i < 64; i += m {
		44  			for j := uint(0); j < m; j++ {
		45  				if x&(uint64(1)<<(i+j)) != 0 {
		46  					out |= ((uint64(1) << m) - 1) << i
		47  					break
		48  				}
		49  			}
		50  		}
		51  		return out
		52  	}
		53  	check := func(x uint64, m uint) {
		54  		want := fillAlignedSlow(x, m)
		55  		if got := FillAligned(x, m); got != want {
		56  			t.Logf("got:	%064b", got)
		57  			t.Logf("want: %064b", want)
		58  			t.Errorf("bad fillAligned(%016x, %d)", x, m)
		59  		}
		60  	}
		61  	for m := uint(1); m <= 64; m *= 2 {
		62  		tests := []uint64{
		63  			0x0000000000000000,
		64  			0x00000000ffffffff,
		65  			0xffffffff00000000,
		66  			0x8000000000000001,
		67  			0xf00000000000000f,
		68  			0xf00000010050000f,
		69  			0xffffffffffffffff,
		70  			0x0000000000000001,
		71  			0x0000000000000002,
		72  			0x0000000000000008,
		73  			uint64(1) << (m - 1),
		74  			uint64(1) << m,
		75  			// Try a few fixed arbitrary examples.
		76  			0xb02b9effcf137016,
		77  			0x3975a076a9fbff18,
		78  			0x0f8c88ec3b81506e,
		79  			0x60f14d80ef2fa0e6,
		80  		}
		81  		for _, test := range tests {
		82  			check(test, m)
		83  		}
		84  		for i := 0; i < 1000; i++ {
		85  			// Try a pseudo-random numbers.
		86  			check(rand.Uint64(), m)
		87  
		88  			if m > 1 {
		89  				// For m != 1, let's construct a slightly more interesting
		90  				// random test. Generate a bitmap which is either 0 or
		91  				// randomly set bits for each m-aligned group of m bits.
		92  				val := uint64(0)
		93  				for n := uint(0); n < 64; n += m {
		94  					// For each group of m bits, flip a coin:
		95  					// * Leave them as zero.
		96  					// * Set them randomly.
		97  					if rand.Uint64()%2 == 0 {
		98  						val |= (rand.Uint64() & ((1 << m) - 1)) << n
		99  					}
	 100  				}
	 101  				check(val, m)
	 102  			}
	 103  		}
	 104  	}
	 105  }
	 106  
	 107  func TestPallocDataFindScavengeCandidate(t *testing.T) {
	 108  	type test struct {
	 109  		alloc, scavenged []BitRange
	 110  		min, max				 uintptr
	 111  		want						 BitRange
	 112  	}
	 113  	tests := map[string]test{
	 114  		"MixedMin1": {
	 115  			alloc:		 []BitRange{{0, 40}, {42, PallocChunkPages - 42}},
	 116  			scavenged: []BitRange{{0, 41}, {42, PallocChunkPages - 42}},
	 117  			min:			 1,
	 118  			max:			 PallocChunkPages,
	 119  			want:			BitRange{41, 1},
	 120  		},
	 121  		"MultiMin1": {
	 122  			alloc:		 []BitRange{{0, 63}, {65, 20}, {87, PallocChunkPages - 87}},
	 123  			scavenged: []BitRange{{86, 1}},
	 124  			min:			 1,
	 125  			max:			 PallocChunkPages,
	 126  			want:			BitRange{85, 1},
	 127  		},
	 128  	}
	 129  	// Try out different page minimums.
	 130  	for m := uintptr(1); m <= 64; m *= 2 {
	 131  		suffix := fmt.Sprintf("Min%d", m)
	 132  		tests["AllFree"+suffix] = test{
	 133  			min:	m,
	 134  			max:	PallocChunkPages,
	 135  			want: BitRange{0, PallocChunkPages},
	 136  		}
	 137  		tests["AllScavenged"+suffix] = test{
	 138  			scavenged: []BitRange{{0, PallocChunkPages}},
	 139  			min:			 m,
	 140  			max:			 PallocChunkPages,
	 141  			want:			BitRange{0, 0},
	 142  		}
	 143  		tests["NoneFree"+suffix] = test{
	 144  			alloc:		 []BitRange{{0, PallocChunkPages}},
	 145  			scavenged: []BitRange{{PallocChunkPages / 2, PallocChunkPages / 2}},
	 146  			min:			 m,
	 147  			max:			 PallocChunkPages,
	 148  			want:			BitRange{0, 0},
	 149  		}
	 150  		tests["StartFree"+suffix] = test{
	 151  			alloc: []BitRange{{uint(m), PallocChunkPages - uint(m)}},
	 152  			min:	 m,
	 153  			max:	 PallocChunkPages,
	 154  			want:	BitRange{0, uint(m)},
	 155  		}
	 156  		tests["EndFree"+suffix] = test{
	 157  			alloc: []BitRange{{0, PallocChunkPages - uint(m)}},
	 158  			min:	 m,
	 159  			max:	 PallocChunkPages,
	 160  			want:	BitRange{PallocChunkPages - uint(m), uint(m)},
	 161  		}
	 162  		tests["Straddle64"+suffix] = test{
	 163  			alloc: []BitRange{{0, 64 - uint(m)}, {64 + uint(m), PallocChunkPages - (64 + uint(m))}},
	 164  			min:	 m,
	 165  			max:	 2 * m,
	 166  			want:	BitRange{64 - uint(m), 2 * uint(m)},
	 167  		}
	 168  		tests["BottomEdge64WithFull"+suffix] = test{
	 169  			alloc:		 []BitRange{{64, 64}, {128 + 3*uint(m), PallocChunkPages - (128 + 3*uint(m))}},
	 170  			scavenged: []BitRange{{1, 10}},
	 171  			min:			 m,
	 172  			max:			 3 * m,
	 173  			want:			BitRange{128, 3 * uint(m)},
	 174  		}
	 175  		tests["BottomEdge64WithPocket"+suffix] = test{
	 176  			alloc:		 []BitRange{{64, 62}, {127, 1}, {128 + 3*uint(m), PallocChunkPages - (128 + 3*uint(m))}},
	 177  			scavenged: []BitRange{{1, 10}},
	 178  			min:			 m,
	 179  			max:			 3 * m,
	 180  			want:			BitRange{128, 3 * uint(m)},
	 181  		}
	 182  		tests["Max0"+suffix] = test{
	 183  			scavenged: []BitRange{{0, PallocChunkPages - uint(m)}},
	 184  			min:			 m,
	 185  			max:			 0,
	 186  			want:			BitRange{PallocChunkPages - uint(m), uint(m)},
	 187  		}
	 188  		if m <= 8 {
	 189  			tests["OneFree"] = test{
	 190  				alloc: []BitRange{{0, 40}, {40 + uint(m), PallocChunkPages - (40 + uint(m))}},
	 191  				min:	 m,
	 192  				max:	 PallocChunkPages,
	 193  				want:	BitRange{40, uint(m)},
	 194  			}
	 195  			tests["OneScavenged"] = test{
	 196  				alloc:		 []BitRange{{0, 40}, {40 + uint(m), PallocChunkPages - (40 + uint(m))}},
	 197  				scavenged: []BitRange{{40, 1}},
	 198  				min:			 m,
	 199  				max:			 PallocChunkPages,
	 200  				want:			BitRange{0, 0},
	 201  			}
	 202  		}
	 203  		if m > 1 {
	 204  			tests["MaxUnaligned"+suffix] = test{
	 205  				scavenged: []BitRange{{0, PallocChunkPages - uint(m*2-1)}},
	 206  				min:			 m,
	 207  				max:			 m - 2,
	 208  				want:			BitRange{PallocChunkPages - uint(m), uint(m)},
	 209  			}
	 210  			tests["SkipSmall"+suffix] = test{
	 211  				alloc: []BitRange{{0, 64 - uint(m)}, {64, 5}, {70, 11}, {82, PallocChunkPages - 82}},
	 212  				min:	 m,
	 213  				max:	 m,
	 214  				want:	BitRange{64 - uint(m), uint(m)},
	 215  			}
	 216  			tests["SkipMisaligned"+suffix] = test{
	 217  				alloc: []BitRange{{0, 64 - uint(m)}, {64, 63}, {127 + uint(m), PallocChunkPages - (127 + uint(m))}},
	 218  				min:	 m,
	 219  				max:	 m,
	 220  				want:	BitRange{64 - uint(m), uint(m)},
	 221  			}
	 222  			tests["MaxLessThan"+suffix] = test{
	 223  				scavenged: []BitRange{{0, PallocChunkPages - uint(m)}},
	 224  				min:			 m,
	 225  				max:			 1,
	 226  				want:			BitRange{PallocChunkPages - uint(m), uint(m)},
	 227  			}
	 228  		}
	 229  	}
	 230  	if PhysHugePageSize > uintptr(PageSize) {
	 231  		// Check hugepage preserving behavior.
	 232  		bits := uint(PhysHugePageSize / uintptr(PageSize))
	 233  		if bits < PallocChunkPages {
	 234  			tests["PreserveHugePageBottom"] = test{
	 235  				alloc: []BitRange{{bits + 2, PallocChunkPages - (bits + 2)}},
	 236  				min:	 1,
	 237  				max:	 3, // Make it so that max would have us try to break the huge page.
	 238  				want:	BitRange{0, bits + 2},
	 239  			}
	 240  			if 3*bits < PallocChunkPages {
	 241  				// We need at least 3 huge pages in a chunk for this test to make sense.
	 242  				tests["PreserveHugePageMiddle"] = test{
	 243  					alloc: []BitRange{{0, bits - 10}, {2*bits + 10, PallocChunkPages - (2*bits + 10)}},
	 244  					min:	 1,
	 245  					max:	 12, // Make it so that max would have us try to break the huge page.
	 246  					want:	BitRange{bits, bits + 10},
	 247  				}
	 248  			}
	 249  			tests["PreserveHugePageTop"] = test{
	 250  				alloc: []BitRange{{0, PallocChunkPages - bits}},
	 251  				min:	 1,
	 252  				max:	 1, // Even one page would break a huge page in this case.
	 253  				want:	BitRange{PallocChunkPages - bits, bits},
	 254  			}
	 255  		} else if bits == PallocChunkPages {
	 256  			tests["PreserveHugePageAll"] = test{
	 257  				min:	1,
	 258  				max:	1, // Even one page would break a huge page in this case.
	 259  				want: BitRange{0, PallocChunkPages},
	 260  			}
	 261  		} else {
	 262  			// The huge page size is greater than pallocChunkPages, so it should
	 263  			// be effectively disabled. There's no way we can possible scavenge
	 264  			// a huge page out of this bitmap chunk.
	 265  			tests["PreserveHugePageNone"] = test{
	 266  				min:	1,
	 267  				max:	1,
	 268  				want: BitRange{PallocChunkPages - 1, 1},
	 269  			}
	 270  		}
	 271  	}
	 272  	for name, v := range tests {
	 273  		v := v
	 274  		t.Run(name, func(t *testing.T) {
	 275  			b := makePallocData(v.alloc, v.scavenged)
	 276  			start, size := b.FindScavengeCandidate(PallocChunkPages-1, v.min, v.max)
	 277  			got := BitRange{start, size}
	 278  			if !(got.N == 0 && v.want.N == 0) && got != v.want {
	 279  				t.Fatalf("candidate mismatch: got %v, want %v", got, v.want)
	 280  			}
	 281  		})
	 282  	}
	 283  }
	 284  
	 285  // Tests end-to-end scavenging on a pageAlloc.
	 286  func TestPageAllocScavenge(t *testing.T) {
	 287  	if GOOS == "openbsd" && testing.Short() {
	 288  		t.Skip("skipping because virtual memory is limited; see #36210")
	 289  	}
	 290  	type test struct {
	 291  		request, expect uintptr
	 292  	}
	 293  	minPages := PhysPageSize / PageSize
	 294  	if minPages < 1 {
	 295  		minPages = 1
	 296  	}
	 297  	type setup struct {
	 298  		beforeAlloc map[ChunkIdx][]BitRange
	 299  		beforeScav	map[ChunkIdx][]BitRange
	 300  		expect			[]test
	 301  		afterScav	 map[ChunkIdx][]BitRange
	 302  	}
	 303  	tests := map[string]setup{
	 304  		"AllFreeUnscavExhaust": {
	 305  			beforeAlloc: map[ChunkIdx][]BitRange{
	 306  				BaseChunkIdx:		 {},
	 307  				BaseChunkIdx + 1: {},
	 308  				BaseChunkIdx + 2: {},
	 309  			},
	 310  			beforeScav: map[ChunkIdx][]BitRange{
	 311  				BaseChunkIdx:		 {},
	 312  				BaseChunkIdx + 1: {},
	 313  				BaseChunkIdx + 2: {},
	 314  			},
	 315  			expect: []test{
	 316  				{^uintptr(0), 3 * PallocChunkPages * PageSize},
	 317  			},
	 318  			afterScav: map[ChunkIdx][]BitRange{
	 319  				BaseChunkIdx:		 {{0, PallocChunkPages}},
	 320  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
	 321  				BaseChunkIdx + 2: {{0, PallocChunkPages}},
	 322  			},
	 323  		},
	 324  		"NoneFreeUnscavExhaust": {
	 325  			beforeAlloc: map[ChunkIdx][]BitRange{
	 326  				BaseChunkIdx:		 {{0, PallocChunkPages}},
	 327  				BaseChunkIdx + 1: {},
	 328  				BaseChunkIdx + 2: {{0, PallocChunkPages}},
	 329  			},
	 330  			beforeScav: map[ChunkIdx][]BitRange{
	 331  				BaseChunkIdx:		 {},
	 332  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
	 333  				BaseChunkIdx + 2: {},
	 334  			},
	 335  			expect: []test{
	 336  				{^uintptr(0), 0},
	 337  			},
	 338  			afterScav: map[ChunkIdx][]BitRange{
	 339  				BaseChunkIdx:		 {},
	 340  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
	 341  				BaseChunkIdx + 2: {},
	 342  			},
	 343  		},
	 344  		"ScavHighestPageFirst": {
	 345  			beforeAlloc: map[ChunkIdx][]BitRange{
	 346  				BaseChunkIdx: {},
	 347  			},
	 348  			beforeScav: map[ChunkIdx][]BitRange{
	 349  				BaseChunkIdx: {{uint(minPages), PallocChunkPages - uint(2*minPages)}},
	 350  			},
	 351  			expect: []test{
	 352  				{1, minPages * PageSize},
	 353  			},
	 354  			afterScav: map[ChunkIdx][]BitRange{
	 355  				BaseChunkIdx: {{uint(minPages), PallocChunkPages - uint(minPages)}},
	 356  			},
	 357  		},
	 358  		"ScavMultiple": {
	 359  			beforeAlloc: map[ChunkIdx][]BitRange{
	 360  				BaseChunkIdx: {},
	 361  			},
	 362  			beforeScav: map[ChunkIdx][]BitRange{
	 363  				BaseChunkIdx: {{uint(minPages), PallocChunkPages - uint(2*minPages)}},
	 364  			},
	 365  			expect: []test{
	 366  				{minPages * PageSize, minPages * PageSize},
	 367  				{minPages * PageSize, minPages * PageSize},
	 368  			},
	 369  			afterScav: map[ChunkIdx][]BitRange{
	 370  				BaseChunkIdx: {{0, PallocChunkPages}},
	 371  			},
	 372  		},
	 373  		"ScavMultiple2": {
	 374  			beforeAlloc: map[ChunkIdx][]BitRange{
	 375  				BaseChunkIdx:		 {},
	 376  				BaseChunkIdx + 1: {},
	 377  			},
	 378  			beforeScav: map[ChunkIdx][]BitRange{
	 379  				BaseChunkIdx:		 {{uint(minPages), PallocChunkPages - uint(2*minPages)}},
	 380  				BaseChunkIdx + 1: {{0, PallocChunkPages - uint(2*minPages)}},
	 381  			},
	 382  			expect: []test{
	 383  				{2 * minPages * PageSize, 2 * minPages * PageSize},
	 384  				{minPages * PageSize, minPages * PageSize},
	 385  				{minPages * PageSize, minPages * PageSize},
	 386  			},
	 387  			afterScav: map[ChunkIdx][]BitRange{
	 388  				BaseChunkIdx:		 {{0, PallocChunkPages}},
	 389  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
	 390  			},
	 391  		},
	 392  		"ScavDiscontiguous": {
	 393  			beforeAlloc: map[ChunkIdx][]BitRange{
	 394  				BaseChunkIdx:			 {},
	 395  				BaseChunkIdx + 0xe: {},
	 396  			},
	 397  			beforeScav: map[ChunkIdx][]BitRange{
	 398  				BaseChunkIdx:			 {{uint(minPages), PallocChunkPages - uint(2*minPages)}},
	 399  				BaseChunkIdx + 0xe: {{uint(2 * minPages), PallocChunkPages - uint(2*minPages)}},
	 400  			},
	 401  			expect: []test{
	 402  				{2 * minPages * PageSize, 2 * minPages * PageSize},
	 403  				{^uintptr(0), 2 * minPages * PageSize},
	 404  				{^uintptr(0), 0},
	 405  			},
	 406  			afterScav: map[ChunkIdx][]BitRange{
	 407  				BaseChunkIdx:			 {{0, PallocChunkPages}},
	 408  				BaseChunkIdx + 0xe: {{0, PallocChunkPages}},
	 409  			},
	 410  		},
	 411  	}
	 412  	// Disable these tests on iOS since we have a small address space.
	 413  	// See #46860.
	 414  	if PageAlloc64Bit != 0 && sys.GoosIos == 0 {
	 415  		tests["ScavAllVeryDiscontiguous"] = setup{
	 416  			beforeAlloc: map[ChunkIdx][]BitRange{
	 417  				BaseChunkIdx:					{},
	 418  				BaseChunkIdx + 0x1000: {},
	 419  			},
	 420  			beforeScav: map[ChunkIdx][]BitRange{
	 421  				BaseChunkIdx:					{},
	 422  				BaseChunkIdx + 0x1000: {},
	 423  			},
	 424  			expect: []test{
	 425  				{^uintptr(0), 2 * PallocChunkPages * PageSize},
	 426  				{^uintptr(0), 0},
	 427  			},
	 428  			afterScav: map[ChunkIdx][]BitRange{
	 429  				BaseChunkIdx:					{{0, PallocChunkPages}},
	 430  				BaseChunkIdx + 0x1000: {{0, PallocChunkPages}},
	 431  			},
	 432  		}
	 433  	}
	 434  	for name, v := range tests {
	 435  		v := v
	 436  		runTest := func(t *testing.T, mayUnlock bool) {
	 437  			b := NewPageAlloc(v.beforeAlloc, v.beforeScav)
	 438  			defer FreePageAlloc(b)
	 439  
	 440  			for iter, h := range v.expect {
	 441  				if got := b.Scavenge(h.request, mayUnlock); got != h.expect {
	 442  					t.Fatalf("bad scavenge #%d: want %d, got %d", iter+1, h.expect, got)
	 443  				}
	 444  			}
	 445  			want := NewPageAlloc(v.beforeAlloc, v.afterScav)
	 446  			defer FreePageAlloc(want)
	 447  
	 448  			checkPageAlloc(t, want, b)
	 449  		}
	 450  		t.Run(name, func(t *testing.T) {
	 451  			runTest(t, false)
	 452  		})
	 453  		t.Run(name+"MayUnlock", func(t *testing.T) {
	 454  			runTest(t, true)
	 455  		})
	 456  	}
	 457  }
	 458
View as plain text