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/rand"
    11  	. "runtime"
    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 && goos.IsIos == 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  		t.Run(name, func(t *testing.T) {
   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); 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  	}
   451  }
   452  

View as plain text