Source file src/runtime/mgcscavenge_test.go

     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  	"internal/goos"
    10  	"math"
    11  	"math/rand"
    12  	. "runtime"
    13  	"runtime/internal/atomic"
    14  	"testing"
    15  	"time"
    16  )
    17  
    18  // makePallocData produces an initialized PallocData by setting
    19  // the ranges of described in alloc and scavenge.
    20  func makePallocData(alloc, scavenged []BitRange) *PallocData {
    21  	b := new(PallocData)
    22  	for _, v := range alloc {
    23  		if v.N == 0 {
    24  			// Skip N==0. It's harmless and allocRange doesn't
    25  			// handle this case.
    26  			continue
    27  		}
    28  		b.AllocRange(v.I, v.N)
    29  	}
    30  	for _, v := range scavenged {
    31  		if v.N == 0 {
    32  			// See the previous loop.
    33  			continue
    34  		}
    35  		b.ScavengedSetRange(v.I, v.N)
    36  	}
    37  	return b
    38  }
    39  
    40  func TestFillAligned(t *testing.T) {
    41  	fillAlignedSlow := func(x uint64, m uint) uint64 {
    42  		if m == 1 {
    43  			return x
    44  		}
    45  		out := uint64(0)
    46  		for i := uint(0); i < 64; i += m {
    47  			for j := uint(0); j < m; j++ {
    48  				if x&(uint64(1)<<(i+j)) != 0 {
    49  					out |= ((uint64(1) << m) - 1) << i
    50  					break
    51  				}
    52  			}
    53  		}
    54  		return out
    55  	}
    56  	check := func(x uint64, m uint) {
    57  		want := fillAlignedSlow(x, m)
    58  		if got := FillAligned(x, m); got != want {
    59  			t.Logf("got:  %064b", got)
    60  			t.Logf("want: %064b", want)
    61  			t.Errorf("bad fillAligned(%016x, %d)", x, m)
    62  		}
    63  	}
    64  	for m := uint(1); m <= 64; m *= 2 {
    65  		tests := []uint64{
    66  			0x0000000000000000,
    67  			0x00000000ffffffff,
    68  			0xffffffff00000000,
    69  			0x8000000000000001,
    70  			0xf00000000000000f,
    71  			0xf00000010050000f,
    72  			0xffffffffffffffff,
    73  			0x0000000000000001,
    74  			0x0000000000000002,
    75  			0x0000000000000008,
    76  			uint64(1) << (m - 1),
    77  			uint64(1) << m,
    78  			// Try a few fixed arbitrary examples.
    79  			0xb02b9effcf137016,
    80  			0x3975a076a9fbff18,
    81  			0x0f8c88ec3b81506e,
    82  			0x60f14d80ef2fa0e6,
    83  		}
    84  		for _, test := range tests {
    85  			check(test, m)
    86  		}
    87  		for i := 0; i < 1000; i++ {
    88  			// Try a pseudo-random numbers.
    89  			check(rand.Uint64(), m)
    90  
    91  			if m > 1 {
    92  				// For m != 1, let's construct a slightly more interesting
    93  				// random test. Generate a bitmap which is either 0 or
    94  				// randomly set bits for each m-aligned group of m bits.
    95  				val := uint64(0)
    96  				for n := uint(0); n < 64; n += m {
    97  					// For each group of m bits, flip a coin:
    98  					// * Leave them as zero.
    99  					// * Set them randomly.
   100  					if rand.Uint64()%2 == 0 {
   101  						val |= (rand.Uint64() & ((1 << m) - 1)) << n
   102  					}
   103  				}
   104  				check(val, m)
   105  			}
   106  		}
   107  	}
   108  }
   109  
   110  func TestPallocDataFindScavengeCandidate(t *testing.T) {
   111  	type test struct {
   112  		alloc, scavenged []BitRange
   113  		min, max         uintptr
   114  		want             BitRange
   115  	}
   116  	tests := map[string]test{
   117  		"MixedMin1": {
   118  			alloc:     []BitRange{{0, 40}, {42, PallocChunkPages - 42}},
   119  			scavenged: []BitRange{{0, 41}, {42, PallocChunkPages - 42}},
   120  			min:       1,
   121  			max:       PallocChunkPages,
   122  			want:      BitRange{41, 1},
   123  		},
   124  		"MultiMin1": {
   125  			alloc:     []BitRange{{0, 63}, {65, 20}, {87, PallocChunkPages - 87}},
   126  			scavenged: []BitRange{{86, 1}},
   127  			min:       1,
   128  			max:       PallocChunkPages,
   129  			want:      BitRange{85, 1},
   130  		},
   131  	}
   132  	// Try out different page minimums.
   133  	for m := uintptr(1); m <= 64; m *= 2 {
   134  		suffix := fmt.Sprintf("Min%d", m)
   135  		tests["AllFree"+suffix] = test{
   136  			min:  m,
   137  			max:  PallocChunkPages,
   138  			want: BitRange{0, PallocChunkPages},
   139  		}
   140  		tests["AllScavenged"+suffix] = test{
   141  			scavenged: []BitRange{{0, PallocChunkPages}},
   142  			min:       m,
   143  			max:       PallocChunkPages,
   144  			want:      BitRange{0, 0},
   145  		}
   146  		tests["NoneFree"+suffix] = test{
   147  			alloc:     []BitRange{{0, PallocChunkPages}},
   148  			scavenged: []BitRange{{PallocChunkPages / 2, PallocChunkPages / 2}},
   149  			min:       m,
   150  			max:       PallocChunkPages,
   151  			want:      BitRange{0, 0},
   152  		}
   153  		tests["StartFree"+suffix] = test{
   154  			alloc: []BitRange{{uint(m), PallocChunkPages - uint(m)}},
   155  			min:   m,
   156  			max:   PallocChunkPages,
   157  			want:  BitRange{0, uint(m)},
   158  		}
   159  		tests["EndFree"+suffix] = test{
   160  			alloc: []BitRange{{0, PallocChunkPages - uint(m)}},
   161  			min:   m,
   162  			max:   PallocChunkPages,
   163  			want:  BitRange{PallocChunkPages - uint(m), uint(m)},
   164  		}
   165  		tests["Straddle64"+suffix] = test{
   166  			alloc: []BitRange{{0, 64 - uint(m)}, {64 + uint(m), PallocChunkPages - (64 + uint(m))}},
   167  			min:   m,
   168  			max:   2 * m,
   169  			want:  BitRange{64 - uint(m), 2 * uint(m)},
   170  		}
   171  		tests["BottomEdge64WithFull"+suffix] = test{
   172  			alloc:     []BitRange{{64, 64}, {128 + 3*uint(m), PallocChunkPages - (128 + 3*uint(m))}},
   173  			scavenged: []BitRange{{1, 10}},
   174  			min:       m,
   175  			max:       3 * m,
   176  			want:      BitRange{128, 3 * uint(m)},
   177  		}
   178  		tests["BottomEdge64WithPocket"+suffix] = test{
   179  			alloc:     []BitRange{{64, 62}, {127, 1}, {128 + 3*uint(m), PallocChunkPages - (128 + 3*uint(m))}},
   180  			scavenged: []BitRange{{1, 10}},
   181  			min:       m,
   182  			max:       3 * m,
   183  			want:      BitRange{128, 3 * uint(m)},
   184  		}
   185  		tests["Max0"+suffix] = test{
   186  			scavenged: []BitRange{{0, PallocChunkPages - uint(m)}},
   187  			min:       m,
   188  			max:       0,
   189  			want:      BitRange{PallocChunkPages - uint(m), uint(m)},
   190  		}
   191  		if m <= 8 {
   192  			tests["OneFree"] = test{
   193  				alloc: []BitRange{{0, 40}, {40 + uint(m), PallocChunkPages - (40 + uint(m))}},
   194  				min:   m,
   195  				max:   PallocChunkPages,
   196  				want:  BitRange{40, uint(m)},
   197  			}
   198  			tests["OneScavenged"] = test{
   199  				alloc:     []BitRange{{0, 40}, {40 + uint(m), PallocChunkPages - (40 + uint(m))}},
   200  				scavenged: []BitRange{{40, 1}},
   201  				min:       m,
   202  				max:       PallocChunkPages,
   203  				want:      BitRange{0, 0},
   204  			}
   205  		}
   206  		if m > 1 {
   207  			tests["MaxUnaligned"+suffix] = test{
   208  				scavenged: []BitRange{{0, PallocChunkPages - uint(m*2-1)}},
   209  				min:       m,
   210  				max:       m - 2,
   211  				want:      BitRange{PallocChunkPages - uint(m), uint(m)},
   212  			}
   213  			tests["SkipSmall"+suffix] = test{
   214  				alloc: []BitRange{{0, 64 - uint(m)}, {64, 5}, {70, 11}, {82, PallocChunkPages - 82}},
   215  				min:   m,
   216  				max:   m,
   217  				want:  BitRange{64 - uint(m), uint(m)},
   218  			}
   219  			tests["SkipMisaligned"+suffix] = test{
   220  				alloc: []BitRange{{0, 64 - uint(m)}, {64, 63}, {127 + uint(m), PallocChunkPages - (127 + uint(m))}},
   221  				min:   m,
   222  				max:   m,
   223  				want:  BitRange{64 - uint(m), uint(m)},
   224  			}
   225  			tests["MaxLessThan"+suffix] = test{
   226  				scavenged: []BitRange{{0, PallocChunkPages - uint(m)}},
   227  				min:       m,
   228  				max:       1,
   229  				want:      BitRange{PallocChunkPages - uint(m), uint(m)},
   230  			}
   231  		}
   232  	}
   233  	if PhysHugePageSize > uintptr(PageSize) {
   234  		// Check hugepage preserving behavior.
   235  		bits := uint(PhysHugePageSize / uintptr(PageSize))
   236  		if bits < PallocChunkPages {
   237  			tests["PreserveHugePageBottom"] = test{
   238  				alloc: []BitRange{{bits + 2, PallocChunkPages - (bits + 2)}},
   239  				min:   1,
   240  				max:   3, // Make it so that max would have us try to break the huge page.
   241  				want:  BitRange{0, bits + 2},
   242  			}
   243  			if 3*bits < PallocChunkPages {
   244  				// We need at least 3 huge pages in a chunk for this test to make sense.
   245  				tests["PreserveHugePageMiddle"] = test{
   246  					alloc: []BitRange{{0, bits - 10}, {2*bits + 10, PallocChunkPages - (2*bits + 10)}},
   247  					min:   1,
   248  					max:   12, // Make it so that max would have us try to break the huge page.
   249  					want:  BitRange{bits, bits + 10},
   250  				}
   251  			}
   252  			tests["PreserveHugePageTop"] = test{
   253  				alloc: []BitRange{{0, PallocChunkPages - bits}},
   254  				min:   1,
   255  				max:   1, // Even one page would break a huge page in this case.
   256  				want:  BitRange{PallocChunkPages - bits, bits},
   257  			}
   258  		} else if bits == PallocChunkPages {
   259  			tests["PreserveHugePageAll"] = test{
   260  				min:  1,
   261  				max:  1, // Even one page would break a huge page in this case.
   262  				want: BitRange{0, PallocChunkPages},
   263  			}
   264  		} else {
   265  			// The huge page size is greater than pallocChunkPages, so it should
   266  			// be effectively disabled. There's no way we can possible scavenge
   267  			// a huge page out of this bitmap chunk.
   268  			tests["PreserveHugePageNone"] = test{
   269  				min:  1,
   270  				max:  1,
   271  				want: BitRange{PallocChunkPages - 1, 1},
   272  			}
   273  		}
   274  	}
   275  	for name, v := range tests {
   276  		v := v
   277  		t.Run(name, func(t *testing.T) {
   278  			b := makePallocData(v.alloc, v.scavenged)
   279  			start, size := b.FindScavengeCandidate(PallocChunkPages-1, v.min, v.max)
   280  			got := BitRange{start, size}
   281  			if !(got.N == 0 && v.want.N == 0) && got != v.want {
   282  				t.Fatalf("candidate mismatch: got %v, want %v", got, v.want)
   283  			}
   284  		})
   285  	}
   286  }
   287  
   288  // Tests end-to-end scavenging on a pageAlloc.
   289  func TestPageAllocScavenge(t *testing.T) {
   290  	if GOOS == "openbsd" && testing.Short() {
   291  		t.Skip("skipping because virtual memory is limited; see #36210")
   292  	}
   293  	type test struct {
   294  		request, expect uintptr
   295  	}
   296  	minPages := PhysPageSize / PageSize
   297  	if minPages < 1 {
   298  		minPages = 1
   299  	}
   300  	type setup struct {
   301  		beforeAlloc map[ChunkIdx][]BitRange
   302  		beforeScav  map[ChunkIdx][]BitRange
   303  		expect      []test
   304  		afterScav   map[ChunkIdx][]BitRange
   305  	}
   306  	tests := map[string]setup{
   307  		"AllFreeUnscavExhaust": {
   308  			beforeAlloc: map[ChunkIdx][]BitRange{
   309  				BaseChunkIdx:     {},
   310  				BaseChunkIdx + 1: {},
   311  				BaseChunkIdx + 2: {},
   312  			},
   313  			beforeScav: map[ChunkIdx][]BitRange{
   314  				BaseChunkIdx:     {},
   315  				BaseChunkIdx + 1: {},
   316  				BaseChunkIdx + 2: {},
   317  			},
   318  			expect: []test{
   319  				{^uintptr(0), 3 * PallocChunkPages * PageSize},
   320  			},
   321  			afterScav: map[ChunkIdx][]BitRange{
   322  				BaseChunkIdx:     {{0, PallocChunkPages}},
   323  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
   324  				BaseChunkIdx + 2: {{0, PallocChunkPages}},
   325  			},
   326  		},
   327  		"NoneFreeUnscavExhaust": {
   328  			beforeAlloc: map[ChunkIdx][]BitRange{
   329  				BaseChunkIdx:     {{0, PallocChunkPages}},
   330  				BaseChunkIdx + 1: {},
   331  				BaseChunkIdx + 2: {{0, PallocChunkPages}},
   332  			},
   333  			beforeScav: map[ChunkIdx][]BitRange{
   334  				BaseChunkIdx:     {},
   335  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
   336  				BaseChunkIdx + 2: {},
   337  			},
   338  			expect: []test{
   339  				{^uintptr(0), 0},
   340  			},
   341  			afterScav: map[ChunkIdx][]BitRange{
   342  				BaseChunkIdx:     {},
   343  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
   344  				BaseChunkIdx + 2: {},
   345  			},
   346  		},
   347  		"ScavHighestPageFirst": {
   348  			beforeAlloc: map[ChunkIdx][]BitRange{
   349  				BaseChunkIdx: {},
   350  			},
   351  			beforeScav: map[ChunkIdx][]BitRange{
   352  				BaseChunkIdx: {{uint(minPages), PallocChunkPages - uint(2*minPages)}},
   353  			},
   354  			expect: []test{
   355  				{1, minPages * PageSize},
   356  			},
   357  			afterScav: map[ChunkIdx][]BitRange{
   358  				BaseChunkIdx: {{uint(minPages), PallocChunkPages - uint(minPages)}},
   359  			},
   360  		},
   361  		"ScavMultiple": {
   362  			beforeAlloc: map[ChunkIdx][]BitRange{
   363  				BaseChunkIdx: {},
   364  			},
   365  			beforeScav: map[ChunkIdx][]BitRange{
   366  				BaseChunkIdx: {{uint(minPages), PallocChunkPages - uint(2*minPages)}},
   367  			},
   368  			expect: []test{
   369  				{minPages * PageSize, minPages * PageSize},
   370  				{minPages * PageSize, minPages * PageSize},
   371  			},
   372  			afterScav: map[ChunkIdx][]BitRange{
   373  				BaseChunkIdx: {{0, PallocChunkPages}},
   374  			},
   375  		},
   376  		"ScavMultiple2": {
   377  			beforeAlloc: map[ChunkIdx][]BitRange{
   378  				BaseChunkIdx:     {},
   379  				BaseChunkIdx + 1: {},
   380  			},
   381  			beforeScav: map[ChunkIdx][]BitRange{
   382  				BaseChunkIdx:     {{uint(minPages), PallocChunkPages - uint(2*minPages)}},
   383  				BaseChunkIdx + 1: {{0, PallocChunkPages - uint(2*minPages)}},
   384  			},
   385  			expect: []test{
   386  				{2 * minPages * PageSize, 2 * minPages * PageSize},
   387  				{minPages * PageSize, minPages * PageSize},
   388  				{minPages * PageSize, minPages * PageSize},
   389  			},
   390  			afterScav: map[ChunkIdx][]BitRange{
   391  				BaseChunkIdx:     {{0, PallocChunkPages}},
   392  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
   393  			},
   394  		},
   395  		"ScavDiscontiguous": {
   396  			beforeAlloc: map[ChunkIdx][]BitRange{
   397  				BaseChunkIdx:       {},
   398  				BaseChunkIdx + 0xe: {},
   399  			},
   400  			beforeScav: map[ChunkIdx][]BitRange{
   401  				BaseChunkIdx:       {{uint(minPages), PallocChunkPages - uint(2*minPages)}},
   402  				BaseChunkIdx + 0xe: {{uint(2 * minPages), PallocChunkPages - uint(2*minPages)}},
   403  			},
   404  			expect: []test{
   405  				{2 * minPages * PageSize, 2 * minPages * PageSize},
   406  				{^uintptr(0), 2 * minPages * PageSize},
   407  				{^uintptr(0), 0},
   408  			},
   409  			afterScav: map[ChunkIdx][]BitRange{
   410  				BaseChunkIdx:       {{0, PallocChunkPages}},
   411  				BaseChunkIdx + 0xe: {{0, PallocChunkPages}},
   412  			},
   413  		},
   414  	}
   415  	// Disable these tests on iOS since we have a small address space.
   416  	// See #46860.
   417  	if PageAlloc64Bit != 0 && goos.IsIos == 0 {
   418  		tests["ScavAllVeryDiscontiguous"] = setup{
   419  			beforeAlloc: map[ChunkIdx][]BitRange{
   420  				BaseChunkIdx:          {},
   421  				BaseChunkIdx + 0x1000: {},
   422  			},
   423  			beforeScav: map[ChunkIdx][]BitRange{
   424  				BaseChunkIdx:          {},
   425  				BaseChunkIdx + 0x1000: {},
   426  			},
   427  			expect: []test{
   428  				{^uintptr(0), 2 * PallocChunkPages * PageSize},
   429  				{^uintptr(0), 0},
   430  			},
   431  			afterScav: map[ChunkIdx][]BitRange{
   432  				BaseChunkIdx:          {{0, PallocChunkPages}},
   433  				BaseChunkIdx + 0x1000: {{0, PallocChunkPages}},
   434  			},
   435  		}
   436  	}
   437  	for name, v := range tests {
   438  		v := v
   439  		t.Run(name, func(t *testing.T) {
   440  			b := NewPageAlloc(v.beforeAlloc, v.beforeScav)
   441  			defer FreePageAlloc(b)
   442  
   443  			for iter, h := range v.expect {
   444  				if got := b.Scavenge(h.request); got != h.expect {
   445  					t.Fatalf("bad scavenge #%d: want %d, got %d", iter+1, h.expect, got)
   446  				}
   447  			}
   448  			want := NewPageAlloc(v.beforeAlloc, v.afterScav)
   449  			defer FreePageAlloc(want)
   450  
   451  			checkPageAlloc(t, want, b)
   452  		})
   453  	}
   454  }
   455  
   456  func TestScavenger(t *testing.T) {
   457  	// workedTime is a standard conversion of bytes of scavenge
   458  	// work to time elapsed.
   459  	workedTime := func(bytes uintptr) int64 {
   460  		return int64((bytes+4095)/4096) * int64(10*time.Microsecond)
   461  	}
   462  
   463  	// Set up a bunch of state that we're going to track and verify
   464  	// throughout the test.
   465  	totalWork := uint64(64<<20 - 3*PhysPageSize)
   466  	var totalSlept, totalWorked atomic.Int64
   467  	var availableWork atomic.Uint64
   468  	var stopAt atomic.Uint64 // How much available work to stop at.
   469  
   470  	// Set up the scavenger.
   471  	var s Scavenger
   472  	s.Sleep = func(ns int64) int64 {
   473  		totalSlept.Add(ns)
   474  		return ns
   475  	}
   476  	s.Scavenge = func(bytes uintptr) (uintptr, int64) {
   477  		avail := availableWork.Load()
   478  		if uint64(bytes) > avail {
   479  			bytes = uintptr(avail)
   480  		}
   481  		t := workedTime(bytes)
   482  		if bytes != 0 {
   483  			availableWork.Add(-int64(bytes))
   484  			totalWorked.Add(t)
   485  		}
   486  		return bytes, t
   487  	}
   488  	s.ShouldStop = func() bool {
   489  		if availableWork.Load() <= stopAt.Load() {
   490  			return true
   491  		}
   492  		return false
   493  	}
   494  	s.GoMaxProcs = func() int32 {
   495  		return 1
   496  	}
   497  
   498  	// Define a helper for verifying that various properties hold.
   499  	verifyScavengerState := func(t *testing.T, expWork uint64) {
   500  		t.Helper()
   501  
   502  		// Check to make sure it did the amount of work we expected.
   503  		if workDone := uint64(s.Released()); workDone != expWork {
   504  			t.Errorf("want %d bytes of work done, got %d", expWork, workDone)
   505  		}
   506  		// Check to make sure the scavenger is meeting its CPU target.
   507  		idealFraction := float64(ScavengePercent) / 100.0
   508  		cpuFraction := float64(totalWorked.Load()) / float64(totalWorked.Load()+totalSlept.Load())
   509  		if cpuFraction < idealFraction-0.005 || cpuFraction > idealFraction+0.005 {
   510  			t.Errorf("want %f CPU fraction, got %f", idealFraction, cpuFraction)
   511  		}
   512  	}
   513  
   514  	// Start the scavenger.
   515  	s.Start()
   516  
   517  	// Set up some work and let the scavenger run to completion.
   518  	availableWork.Store(totalWork)
   519  	s.Wake()
   520  	if !s.BlockUntilParked(2e9 /* 2 seconds */) {
   521  		t.Fatal("timed out waiting for scavenger to run to completion")
   522  	}
   523  	// Run a check.
   524  	verifyScavengerState(t, totalWork)
   525  
   526  	// Now let's do it again and see what happens when we have no work to do.
   527  	// It should've gone right back to sleep.
   528  	s.Wake()
   529  	if !s.BlockUntilParked(2e9 /* 2 seconds */) {
   530  		t.Fatal("timed out waiting for scavenger to run to completion")
   531  	}
   532  	// Run another check.
   533  	verifyScavengerState(t, totalWork)
   534  
   535  	// One more time, this time doing the same amount of work as the first time.
   536  	// Let's see if we can get the scavenger to continue.
   537  	availableWork.Store(totalWork)
   538  	s.Wake()
   539  	if !s.BlockUntilParked(2e9 /* 2 seconds */) {
   540  		t.Fatal("timed out waiting for scavenger to run to completion")
   541  	}
   542  	// Run another check.
   543  	verifyScavengerState(t, 2*totalWork)
   544  
   545  	// This time, let's stop after a certain amount of work.
   546  	//
   547  	// Pick a stopping point such that when subtracted from totalWork
   548  	// we get a multiple of a relatively large power of 2. verifyScavengerState
   549  	// always makes an exact check, but the scavenger might go a little over,
   550  	// which is OK. If this breaks often or gets annoying to maintain, modify
   551  	// verifyScavengerState.
   552  	availableWork.Store(totalWork)
   553  	stoppingPoint := uint64(1<<20 - 3*PhysPageSize)
   554  	stopAt.Store(stoppingPoint)
   555  	s.Wake()
   556  	if !s.BlockUntilParked(2e9 /* 2 seconds */) {
   557  		t.Fatal("timed out waiting for scavenger to run to completion")
   558  	}
   559  	// Run another check.
   560  	verifyScavengerState(t, 2*totalWork+(totalWork-stoppingPoint))
   561  
   562  	// Clean up.
   563  	s.Stop()
   564  }
   565  
   566  func TestScavengeIndex(t *testing.T) {
   567  	// This test suite tests the scavengeIndex data structure.
   568  
   569  	// markFunc is a function that makes the address range [base, limit)
   570  	// available for scavenging in a test index.
   571  	type markFunc func(base, limit uintptr)
   572  
   573  	// findFunc is a function that searches for the next available page
   574  	// to scavenge in the index. It asserts that the page is found in
   575  	// chunk "ci" at page "offset."
   576  	type findFunc func(ci ChunkIdx, offset uint)
   577  
   578  	// The structure of the tests below is as follows:
   579  	//
   580  	// setup creates a fake scavengeIndex that can be mutated and queried by
   581  	// the functions it returns. Those functions capture the testing.T that
   582  	// setup is called with, so they're bound to the subtest they're created in.
   583  	//
   584  	// Tests are then organized into test cases which mark some pages as
   585  	// scavenge-able then try to find them. Tests expect that the initial
   586  	// state of the scavengeIndex has all of the chunks as dense in the last
   587  	// generation and empty to the scavenger.
   588  	//
   589  	// There are a few additional tests that interleave mark and find operations,
   590  	// so they're defined separately, but use the same infrastructure.
   591  	setup := func(t *testing.T, force bool) (mark markFunc, find findFunc, nextGen func()) {
   592  		t.Helper()
   593  
   594  		// Pick some reasonable bounds. We don't need a huge range just to test.
   595  		si := NewScavengeIndex(BaseChunkIdx, BaseChunkIdx+64)
   596  
   597  		// Initialize all the chunks as dense and empty.
   598  		//
   599  		// Also, reset search addresses so that we can get page offsets.
   600  		si.AllocRange(PageBase(BaseChunkIdx, 0), PageBase(BaseChunkIdx+64, 0))
   601  		si.NextGen()
   602  		si.FreeRange(PageBase(BaseChunkIdx, 0), PageBase(BaseChunkIdx+64, 0))
   603  		for ci := BaseChunkIdx; ci < BaseChunkIdx+64; ci++ {
   604  			si.SetEmpty(ci)
   605  		}
   606  		si.ResetSearchAddrs()
   607  
   608  		// Create and return test functions.
   609  		mark = func(base, limit uintptr) {
   610  			t.Helper()
   611  
   612  			si.AllocRange(base, limit)
   613  			si.FreeRange(base, limit)
   614  		}
   615  		find = func(want ChunkIdx, wantOffset uint) {
   616  			t.Helper()
   617  
   618  			got, gotOffset := si.Find(force)
   619  			if want != got {
   620  				t.Errorf("find: wanted chunk index %d, got %d", want, got)
   621  			}
   622  			if wantOffset != gotOffset {
   623  				t.Errorf("find: wanted page offset %d, got %d", wantOffset, gotOffset)
   624  			}
   625  			if t.Failed() {
   626  				t.FailNow()
   627  			}
   628  			si.SetEmpty(got)
   629  		}
   630  		nextGen = func() {
   631  			t.Helper()
   632  
   633  			si.NextGen()
   634  		}
   635  		return
   636  	}
   637  
   638  	// Each of these test cases calls mark and then find once.
   639  	type testCase struct {
   640  		name string
   641  		mark func(markFunc)
   642  		find func(findFunc)
   643  	}
   644  	for _, test := range []testCase{
   645  		{
   646  			name: "Uninitialized",
   647  			mark: func(_ markFunc) {},
   648  			find: func(_ findFunc) {},
   649  		},
   650  		{
   651  			name: "OnePage",
   652  			mark: func(mark markFunc) {
   653  				mark(PageBase(BaseChunkIdx, 3), PageBase(BaseChunkIdx, 4))
   654  			},
   655  			find: func(find findFunc) {
   656  				find(BaseChunkIdx, 3)
   657  			},
   658  		},
   659  		{
   660  			name: "FirstPage",
   661  			mark: func(mark markFunc) {
   662  				mark(PageBase(BaseChunkIdx, 0), PageBase(BaseChunkIdx, 1))
   663  			},
   664  			find: func(find findFunc) {
   665  				find(BaseChunkIdx, 0)
   666  			},
   667  		},
   668  		{
   669  			name: "SeveralPages",
   670  			mark: func(mark markFunc) {
   671  				mark(PageBase(BaseChunkIdx, 9), PageBase(BaseChunkIdx, 14))
   672  			},
   673  			find: func(find findFunc) {
   674  				find(BaseChunkIdx, 13)
   675  			},
   676  		},
   677  		{
   678  			name: "WholeChunk",
   679  			mark: func(mark markFunc) {
   680  				mark(PageBase(BaseChunkIdx, 0), PageBase(BaseChunkIdx+1, 0))
   681  			},
   682  			find: func(find findFunc) {
   683  				find(BaseChunkIdx, PallocChunkPages-1)
   684  			},
   685  		},
   686  		{
   687  			name: "LastPage",
   688  			mark: func(mark markFunc) {
   689  				mark(PageBase(BaseChunkIdx, PallocChunkPages-1), PageBase(BaseChunkIdx+1, 0))
   690  			},
   691  			find: func(find findFunc) {
   692  				find(BaseChunkIdx, PallocChunkPages-1)
   693  			},
   694  		},
   695  		{
   696  			name: "TwoChunks",
   697  			mark: func(mark markFunc) {
   698  				mark(PageBase(BaseChunkIdx, 128), PageBase(BaseChunkIdx+1, 128))
   699  			},
   700  			find: func(find findFunc) {
   701  				find(BaseChunkIdx+1, 127)
   702  				find(BaseChunkIdx, PallocChunkPages-1)
   703  			},
   704  		},
   705  		{
   706  			name: "TwoChunksOffset",
   707  			mark: func(mark markFunc) {
   708  				mark(PageBase(BaseChunkIdx+7, 128), PageBase(BaseChunkIdx+8, 129))
   709  			},
   710  			find: func(find findFunc) {
   711  				find(BaseChunkIdx+8, 128)
   712  				find(BaseChunkIdx+7, PallocChunkPages-1)
   713  			},
   714  		},
   715  		{
   716  			name: "SevenChunksOffset",
   717  			mark: func(mark markFunc) {
   718  				mark(PageBase(BaseChunkIdx+6, 11), PageBase(BaseChunkIdx+13, 15))
   719  			},
   720  			find: func(find findFunc) {
   721  				find(BaseChunkIdx+13, 14)
   722  				for i := BaseChunkIdx + 12; i >= BaseChunkIdx+6; i-- {
   723  					find(i, PallocChunkPages-1)
   724  				}
   725  			},
   726  		},
   727  		{
   728  			name: "ThirtyTwoChunks",
   729  			mark: func(mark markFunc) {
   730  				mark(PageBase(BaseChunkIdx, 0), PageBase(BaseChunkIdx+32, 0))
   731  			},
   732  			find: func(find findFunc) {
   733  				for i := BaseChunkIdx + 31; i >= BaseChunkIdx; i-- {
   734  					find(i, PallocChunkPages-1)
   735  				}
   736  			},
   737  		},
   738  		{
   739  			name: "ThirtyTwoChunksOffset",
   740  			mark: func(mark markFunc) {
   741  				mark(PageBase(BaseChunkIdx+3, 0), PageBase(BaseChunkIdx+35, 0))
   742  			},
   743  			find: func(find findFunc) {
   744  				for i := BaseChunkIdx + 34; i >= BaseChunkIdx+3; i-- {
   745  					find(i, PallocChunkPages-1)
   746  				}
   747  			},
   748  		},
   749  		{
   750  			name: "Mark",
   751  			mark: func(mark markFunc) {
   752  				for i := BaseChunkIdx; i < BaseChunkIdx+32; i++ {
   753  					mark(PageBase(i, 0), PageBase(i+1, 0))
   754  				}
   755  			},
   756  			find: func(find findFunc) {
   757  				for i := BaseChunkIdx + 31; i >= BaseChunkIdx; i-- {
   758  					find(i, PallocChunkPages-1)
   759  				}
   760  			},
   761  		},
   762  		{
   763  			name: "MarkIdempotentOneChunk",
   764  			mark: func(mark markFunc) {
   765  				mark(PageBase(BaseChunkIdx, 0), PageBase(BaseChunkIdx+1, 0))
   766  				mark(PageBase(BaseChunkIdx, 0), PageBase(BaseChunkIdx+1, 0))
   767  			},
   768  			find: func(find findFunc) {
   769  				find(BaseChunkIdx, PallocChunkPages-1)
   770  			},
   771  		},
   772  		{
   773  			name: "MarkIdempotentThirtyTwoChunks",
   774  			mark: func(mark markFunc) {
   775  				mark(PageBase(BaseChunkIdx, 0), PageBase(BaseChunkIdx+32, 0))
   776  				mark(PageBase(BaseChunkIdx, 0), PageBase(BaseChunkIdx+32, 0))
   777  			},
   778  			find: func(find findFunc) {
   779  				for i := BaseChunkIdx + 31; i >= BaseChunkIdx; i-- {
   780  					find(i, PallocChunkPages-1)
   781  				}
   782  			},
   783  		},
   784  		{
   785  			name: "MarkIdempotentThirtyTwoChunksOffset",
   786  			mark: func(mark markFunc) {
   787  				mark(PageBase(BaseChunkIdx+4, 0), PageBase(BaseChunkIdx+31, 0))
   788  				mark(PageBase(BaseChunkIdx+5, 0), PageBase(BaseChunkIdx+36, 0))
   789  			},
   790  			find: func(find findFunc) {
   791  				for i := BaseChunkIdx + 35; i >= BaseChunkIdx+4; i-- {
   792  					find(i, PallocChunkPages-1)
   793  				}
   794  			},
   795  		},
   796  	} {
   797  		test := test
   798  		t.Run("Bg/"+test.name, func(t *testing.T) {
   799  			mark, find, nextGen := setup(t, false)
   800  			test.mark(mark)
   801  			find(0, 0)      // Make sure we find nothing at this point.
   802  			nextGen()       // Move to the next generation.
   803  			test.find(find) // Now we should be able to find things.
   804  			find(0, 0)      // The test should always fully exhaust the index.
   805  		})
   806  		t.Run("Force/"+test.name, func(t *testing.T) {
   807  			mark, find, _ := setup(t, true)
   808  			test.mark(mark)
   809  			test.find(find) // Finding should always work when forced.
   810  			find(0, 0)      // The test should always fully exhaust the index.
   811  		})
   812  	}
   813  	t.Run("Bg/MarkInterleaved", func(t *testing.T) {
   814  		mark, find, nextGen := setup(t, false)
   815  		for i := BaseChunkIdx; i < BaseChunkIdx+32; i++ {
   816  			mark(PageBase(i, 0), PageBase(i+1, 0))
   817  			nextGen()
   818  			find(i, PallocChunkPages-1)
   819  		}
   820  		find(0, 0)
   821  	})
   822  	t.Run("Force/MarkInterleaved", func(t *testing.T) {
   823  		mark, find, _ := setup(t, true)
   824  		for i := BaseChunkIdx; i < BaseChunkIdx+32; i++ {
   825  			mark(PageBase(i, 0), PageBase(i+1, 0))
   826  			find(i, PallocChunkPages-1)
   827  		}
   828  		find(0, 0)
   829  	})
   830  }
   831  
   832  func TestScavChunkDataPack(t *testing.T) {
   833  	if !CheckPackScavChunkData(1918237402, 512, 512, 0b11) {
   834  		t.Error("failed pack/unpack check for scavChunkData 1")
   835  	}
   836  	if !CheckPackScavChunkData(^uint32(0), 12, 0, 0b00) {
   837  		t.Error("failed pack/unpack check for scavChunkData 2")
   838  	}
   839  }
   840  
   841  func FuzzPIController(f *testing.F) {
   842  	isNormal := func(x float64) bool {
   843  		return !math.IsInf(x, 0) && !math.IsNaN(x)
   844  	}
   845  	isPositive := func(x float64) bool {
   846  		return isNormal(x) && x > 0
   847  	}
   848  	// Seed with constants from controllers in the runtime.
   849  	// It's not critical that we keep these in sync, they're just
   850  	// reasonable seed inputs.
   851  	f.Add(0.3375, 3.2e6, 1e9, 0.001, 1000.0, 0.01)
   852  	f.Add(0.9, 4.0, 1000.0, -1000.0, 1000.0, 0.84)
   853  	f.Fuzz(func(t *testing.T, kp, ti, tt, min, max, setPoint float64) {
   854  		// Ignore uninteresting invalid parameters. These parameters
   855  		// are constant, so in practice surprising values will be documented
   856  		// or will be other otherwise immediately visible.
   857  		//
   858  		// We just want to make sure that given a non-Inf, non-NaN input,
   859  		// we always get a non-Inf, non-NaN output.
   860  		if !isPositive(kp) || !isPositive(ti) || !isPositive(tt) {
   861  			return
   862  		}
   863  		if !isNormal(min) || !isNormal(max) || min > max {
   864  			return
   865  		}
   866  		// Use a random source, but make it deterministic.
   867  		rs := rand.New(rand.NewSource(800))
   868  		randFloat64 := func() float64 {
   869  			return math.Float64frombits(rs.Uint64())
   870  		}
   871  		p := NewPIController(kp, ti, tt, min, max)
   872  		state := float64(0)
   873  		for i := 0; i < 100; i++ {
   874  			input := randFloat64()
   875  			// Ignore the "ok" parameter. We're just trying to break it.
   876  			// state is intentionally completely uncorrelated with the input.
   877  			var ok bool
   878  			state, ok = p.Next(input, setPoint, 1.0)
   879  			if !isNormal(state) {
   880  				t.Fatalf("got NaN or Inf result from controller: %f %v", state, ok)
   881  			}
   882  		}
   883  	})
   884  }
   885  

View as plain text