Source file src/runtime/mpagealloc_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  	. "runtime"
    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 && goos.IsIos == 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  		t.Run(name, func(t *testing.T) {
   185  			// By creating a new pageAlloc, we will
   186  			// grow it for each chunk defined in x.
   187  			x := make(map[ChunkIdx][]BitRange)
   188  			for _, c := range v.chunks {
   189  				x[c] = []BitRange{}
   190  			}
   191  			b := NewPageAlloc(x, nil)
   192  			defer FreePageAlloc(b)
   193  
   194  			got := b.InUse()
   195  			want := v.inUse
   196  
   197  			// Check for mismatches.
   198  			if len(got) != len(want) {
   199  				t.Fail()
   200  			} else {
   201  				for i := range want {
   202  					if !want[i].Equals(got[i]) {
   203  						t.Fail()
   204  						break
   205  					}
   206  				}
   207  			}
   208  			if t.Failed() {
   209  				t.Logf("found inUse mismatch")
   210  				t.Logf("got:")
   211  				for i, r := range got {
   212  					t.Logf("\t#%d [0x%x, 0x%x)", i, r.Base(), r.Limit())
   213  				}
   214  				t.Logf("want:")
   215  				for i, r := range want {
   216  					t.Logf("\t#%d [0x%x, 0x%x)", i, r.Base(), r.Limit())
   217  				}
   218  			}
   219  		})
   220  	}
   221  }
   222  
   223  func TestPageAllocAlloc(t *testing.T) {
   224  	if GOOS == "openbsd" && testing.Short() {
   225  		t.Skip("skipping because virtual memory is limited; see #36210")
   226  	}
   227  	type hit struct {
   228  		npages, base, scav uintptr
   229  	}
   230  	type test struct {
   231  		scav   map[ChunkIdx][]BitRange
   232  		before map[ChunkIdx][]BitRange
   233  		after  map[ChunkIdx][]BitRange
   234  		hits   []hit
   235  	}
   236  	tests := map[string]test{
   237  		"AllFree1": {
   238  			before: map[ChunkIdx][]BitRange{
   239  				BaseChunkIdx: {},
   240  			},
   241  			scav: map[ChunkIdx][]BitRange{
   242  				BaseChunkIdx: {{0, 1}, {2, 2}},
   243  			},
   244  			hits: []hit{
   245  				{1, PageBase(BaseChunkIdx, 0), PageSize},
   246  				{1, PageBase(BaseChunkIdx, 1), 0},
   247  				{1, PageBase(BaseChunkIdx, 2), PageSize},
   248  				{1, PageBase(BaseChunkIdx, 3), PageSize},
   249  				{1, PageBase(BaseChunkIdx, 4), 0},
   250  			},
   251  			after: map[ChunkIdx][]BitRange{
   252  				BaseChunkIdx: {{0, 5}},
   253  			},
   254  		},
   255  		"ManyArena1": {
   256  			before: map[ChunkIdx][]BitRange{
   257  				BaseChunkIdx:     {{0, PallocChunkPages}},
   258  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
   259  				BaseChunkIdx + 2: {{0, PallocChunkPages - 1}},
   260  			},
   261  			scav: map[ChunkIdx][]BitRange{
   262  				BaseChunkIdx:     {{0, PallocChunkPages}},
   263  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
   264  				BaseChunkIdx + 2: {{0, PallocChunkPages}},
   265  			},
   266  			hits: []hit{
   267  				{1, PageBase(BaseChunkIdx+2, PallocChunkPages-1), PageSize},
   268  			},
   269  			after: map[ChunkIdx][]BitRange{
   270  				BaseChunkIdx:     {{0, PallocChunkPages}},
   271  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
   272  				BaseChunkIdx + 2: {{0, PallocChunkPages}},
   273  			},
   274  		},
   275  		"NotContiguous1": {
   276  			before: map[ChunkIdx][]BitRange{
   277  				BaseChunkIdx:        {{0, PallocChunkPages}},
   278  				BaseChunkIdx + 0xff: {{0, 0}},
   279  			},
   280  			scav: map[ChunkIdx][]BitRange{
   281  				BaseChunkIdx:        {{0, PallocChunkPages}},
   282  				BaseChunkIdx + 0xff: {{0, PallocChunkPages}},
   283  			},
   284  			hits: []hit{
   285  				{1, PageBase(BaseChunkIdx+0xff, 0), PageSize},
   286  			},
   287  			after: map[ChunkIdx][]BitRange{
   288  				BaseChunkIdx:        {{0, PallocChunkPages}},
   289  				BaseChunkIdx + 0xff: {{0, 1}},
   290  			},
   291  		},
   292  		"AllFree2": {
   293  			before: map[ChunkIdx][]BitRange{
   294  				BaseChunkIdx: {},
   295  			},
   296  			scav: map[ChunkIdx][]BitRange{
   297  				BaseChunkIdx: {{0, 3}, {7, 1}},
   298  			},
   299  			hits: []hit{
   300  				{2, PageBase(BaseChunkIdx, 0), 2 * PageSize},
   301  				{2, PageBase(BaseChunkIdx, 2), PageSize},
   302  				{2, PageBase(BaseChunkIdx, 4), 0},
   303  				{2, PageBase(BaseChunkIdx, 6), PageSize},
   304  				{2, PageBase(BaseChunkIdx, 8), 0},
   305  			},
   306  			after: map[ChunkIdx][]BitRange{
   307  				BaseChunkIdx: {{0, 10}},
   308  			},
   309  		},
   310  		"Straddle2": {
   311  			before: map[ChunkIdx][]BitRange{
   312  				BaseChunkIdx:     {{0, PallocChunkPages - 1}},
   313  				BaseChunkIdx + 1: {{1, PallocChunkPages - 1}},
   314  			},
   315  			scav: map[ChunkIdx][]BitRange{
   316  				BaseChunkIdx:     {{PallocChunkPages - 1, 1}},
   317  				BaseChunkIdx + 1: {},
   318  			},
   319  			hits: []hit{
   320  				{2, PageBase(BaseChunkIdx, PallocChunkPages-1), PageSize},
   321  			},
   322  			after: map[ChunkIdx][]BitRange{
   323  				BaseChunkIdx:     {{0, PallocChunkPages}},
   324  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
   325  			},
   326  		},
   327  		"AllFree5": {
   328  			before: map[ChunkIdx][]BitRange{
   329  				BaseChunkIdx: {},
   330  			},
   331  			scav: map[ChunkIdx][]BitRange{
   332  				BaseChunkIdx: {{0, 8}, {9, 1}, {17, 5}},
   333  			},
   334  			hits: []hit{
   335  				{5, PageBase(BaseChunkIdx, 0), 5 * PageSize},
   336  				{5, PageBase(BaseChunkIdx, 5), 4 * PageSize},
   337  				{5, PageBase(BaseChunkIdx, 10), 0},
   338  				{5, PageBase(BaseChunkIdx, 15), 3 * PageSize},
   339  				{5, PageBase(BaseChunkIdx, 20), 2 * PageSize},
   340  			},
   341  			after: map[ChunkIdx][]BitRange{
   342  				BaseChunkIdx: {{0, 25}},
   343  			},
   344  		},
   345  		"ExhaustPallocChunkPages-3": {
   346  			before: map[ChunkIdx][]BitRange{
   347  				BaseChunkIdx: {},
   348  			},
   349  			scav: map[ChunkIdx][]BitRange{
   350  				BaseChunkIdx: {{10, 1}},
   351  			},
   352  			hits: []hit{
   353  				{PallocChunkPages - 3, PageBase(BaseChunkIdx, 0), PageSize},
   354  				{PallocChunkPages - 3, 0, 0},
   355  				{1, PageBase(BaseChunkIdx, PallocChunkPages-3), 0},
   356  				{2, PageBase(BaseChunkIdx, PallocChunkPages-2), 0},
   357  				{1, 0, 0},
   358  				{PallocChunkPages - 3, 0, 0},
   359  			},
   360  			after: map[ChunkIdx][]BitRange{
   361  				BaseChunkIdx: {{0, PallocChunkPages}},
   362  			},
   363  		},
   364  		"AllFreePallocChunkPages": {
   365  			before: map[ChunkIdx][]BitRange{
   366  				BaseChunkIdx: {},
   367  			},
   368  			scav: map[ChunkIdx][]BitRange{
   369  				BaseChunkIdx: {{0, 1}, {PallocChunkPages - 1, 1}},
   370  			},
   371  			hits: []hit{
   372  				{PallocChunkPages, PageBase(BaseChunkIdx, 0), 2 * PageSize},
   373  				{PallocChunkPages, 0, 0},
   374  				{1, 0, 0},
   375  			},
   376  			after: map[ChunkIdx][]BitRange{
   377  				BaseChunkIdx: {{0, PallocChunkPages}},
   378  			},
   379  		},
   380  		"StraddlePallocChunkPages+1": {
   381  			before: map[ChunkIdx][]BitRange{
   382  				BaseChunkIdx:     {{0, PallocChunkPages / 2}},
   383  				BaseChunkIdx + 1: {},
   384  			},
   385  			scav: map[ChunkIdx][]BitRange{
   386  				BaseChunkIdx:     {{0, PallocChunkPages}},
   387  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
   388  			},
   389  			hits: []hit{
   390  				{PallocChunkPages + 1, PageBase(BaseChunkIdx, PallocChunkPages/2), (PallocChunkPages + 1) * PageSize},
   391  				{PallocChunkPages, 0, 0},
   392  				{1, PageBase(BaseChunkIdx+1, PallocChunkPages/2+1), PageSize},
   393  			},
   394  			after: map[ChunkIdx][]BitRange{
   395  				BaseChunkIdx:     {{0, PallocChunkPages}},
   396  				BaseChunkIdx + 1: {{0, PallocChunkPages/2 + 2}},
   397  			},
   398  		},
   399  		"AllFreePallocChunkPages*2": {
   400  			before: map[ChunkIdx][]BitRange{
   401  				BaseChunkIdx:     {},
   402  				BaseChunkIdx + 1: {},
   403  			},
   404  			scav: map[ChunkIdx][]BitRange{
   405  				BaseChunkIdx:     {},
   406  				BaseChunkIdx + 1: {},
   407  			},
   408  			hits: []hit{
   409  				{PallocChunkPages * 2, PageBase(BaseChunkIdx, 0), 0},
   410  				{PallocChunkPages * 2, 0, 0},
   411  				{1, 0, 0},
   412  			},
   413  			after: map[ChunkIdx][]BitRange{
   414  				BaseChunkIdx:     {{0, PallocChunkPages}},
   415  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
   416  			},
   417  		},
   418  		"NotContiguousPallocChunkPages*2": {
   419  			before: map[ChunkIdx][]BitRange{
   420  				BaseChunkIdx:        {},
   421  				BaseChunkIdx + 0x40: {},
   422  				BaseChunkIdx + 0x41: {},
   423  			},
   424  			scav: map[ChunkIdx][]BitRange{
   425  				BaseChunkIdx:        {{0, PallocChunkPages}},
   426  				BaseChunkIdx + 0x40: {},
   427  				BaseChunkIdx + 0x41: {},
   428  			},
   429  			hits: []hit{
   430  				{PallocChunkPages * 2, PageBase(BaseChunkIdx+0x40, 0), 0},
   431  				{21, PageBase(BaseChunkIdx, 0), 21 * PageSize},
   432  				{1, PageBase(BaseChunkIdx, 21), PageSize},
   433  			},
   434  			after: map[ChunkIdx][]BitRange{
   435  				BaseChunkIdx:        {{0, 22}},
   436  				BaseChunkIdx + 0x40: {{0, PallocChunkPages}},
   437  				BaseChunkIdx + 0x41: {{0, PallocChunkPages}},
   438  			},
   439  		},
   440  		"StraddlePallocChunkPages*5/4": {
   441  			before: map[ChunkIdx][]BitRange{
   442  				BaseChunkIdx:     {{0, PallocChunkPages}},
   443  				BaseChunkIdx + 1: {{0, PallocChunkPages * 3 / 4}},
   444  				BaseChunkIdx + 2: {{0, PallocChunkPages * 3 / 4}},
   445  				BaseChunkIdx + 3: {{0, 0}},
   446  			},
   447  			scav: map[ChunkIdx][]BitRange{
   448  				BaseChunkIdx:     {{0, PallocChunkPages}},
   449  				BaseChunkIdx + 1: {{PallocChunkPages / 2, PallocChunkPages/4 + 1}},
   450  				BaseChunkIdx + 2: {{PallocChunkPages / 3, 1}},
   451  				BaseChunkIdx + 3: {{PallocChunkPages * 2 / 3, 1}},
   452  			},
   453  			hits: []hit{
   454  				{PallocChunkPages * 5 / 4, PageBase(BaseChunkIdx+2, PallocChunkPages*3/4), PageSize},
   455  				{PallocChunkPages * 5 / 4, 0, 0},
   456  				{1, PageBase(BaseChunkIdx+1, PallocChunkPages*3/4), PageSize},
   457  			},
   458  			after: map[ChunkIdx][]BitRange{
   459  				BaseChunkIdx:     {{0, PallocChunkPages}},
   460  				BaseChunkIdx + 1: {{0, PallocChunkPages*3/4 + 1}},
   461  				BaseChunkIdx + 2: {{0, PallocChunkPages}},
   462  				BaseChunkIdx + 3: {{0, PallocChunkPages}},
   463  			},
   464  		},
   465  	}
   466  	if PallocChunkPages >= 512 {
   467  		tests["AllFree64"] = test{
   468  			before: map[ChunkIdx][]BitRange{
   469  				BaseChunkIdx: {},
   470  			},
   471  			scav: map[ChunkIdx][]BitRange{
   472  				BaseChunkIdx: {{21, 1}, {63, 65}},
   473  			},
   474  			hits: []hit{
   475  				{64, PageBase(BaseChunkIdx, 0), 2 * PageSize},
   476  				{64, PageBase(BaseChunkIdx, 64), 64 * PageSize},
   477  				{64, PageBase(BaseChunkIdx, 128), 0},
   478  			},
   479  			after: map[ChunkIdx][]BitRange{
   480  				BaseChunkIdx: {{0, 192}},
   481  			},
   482  		}
   483  		tests["AllFree65"] = test{
   484  			before: map[ChunkIdx][]BitRange{
   485  				BaseChunkIdx: {},
   486  			},
   487  			scav: map[ChunkIdx][]BitRange{
   488  				BaseChunkIdx: {{129, 1}},
   489  			},
   490  			hits: []hit{
   491  				{65, PageBase(BaseChunkIdx, 0), 0},
   492  				{65, PageBase(BaseChunkIdx, 65), PageSize},
   493  				{65, PageBase(BaseChunkIdx, 130), 0},
   494  			},
   495  			after: map[ChunkIdx][]BitRange{
   496  				BaseChunkIdx: {{0, 195}},
   497  			},
   498  		}
   499  		tests["StraddlePallocChunkPages"] = test{
   500  			before: map[ChunkIdx][]BitRange{
   501  				BaseChunkIdx:     {{0, PallocChunkPages / 2}},
   502  				BaseChunkIdx + 1: {{PallocChunkPages / 2, PallocChunkPages / 2}},
   503  			},
   504  			scav: map[ChunkIdx][]BitRange{
   505  				BaseChunkIdx:     {},
   506  				BaseChunkIdx + 1: {{3, 100}},
   507  			},
   508  			hits: []hit{
   509  				{PallocChunkPages, PageBase(BaseChunkIdx, PallocChunkPages/2), 100 * PageSize},
   510  				{PallocChunkPages, 0, 0},
   511  				{1, 0, 0},
   512  			},
   513  			after: map[ChunkIdx][]BitRange{
   514  				BaseChunkIdx:     {{0, PallocChunkPages}},
   515  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
   516  			},
   517  		}
   518  		tests["AllFreePallocChunkPages*7+5"] = test{
   519  			before: map[ChunkIdx][]BitRange{
   520  				BaseChunkIdx:     {},
   521  				BaseChunkIdx + 1: {},
   522  				BaseChunkIdx + 2: {},
   523  				BaseChunkIdx + 3: {},
   524  				BaseChunkIdx + 4: {},
   525  				BaseChunkIdx + 5: {},
   526  				BaseChunkIdx + 6: {},
   527  				BaseChunkIdx + 7: {},
   528  			},
   529  			scav: map[ChunkIdx][]BitRange{
   530  				BaseChunkIdx:     {{50, 1}},
   531  				BaseChunkIdx + 1: {{31, 1}},
   532  				BaseChunkIdx + 2: {{7, 1}},
   533  				BaseChunkIdx + 3: {{200, 1}},
   534  				BaseChunkIdx + 4: {{3, 1}},
   535  				BaseChunkIdx + 5: {{51, 1}},
   536  				BaseChunkIdx + 6: {{20, 1}},
   537  				BaseChunkIdx + 7: {{1, 1}},
   538  			},
   539  			hits: []hit{
   540  				{PallocChunkPages*7 + 5, PageBase(BaseChunkIdx, 0), 8 * PageSize},
   541  				{PallocChunkPages*7 + 5, 0, 0},
   542  				{1, PageBase(BaseChunkIdx+7, 5), 0},
   543  			},
   544  			after: map[ChunkIdx][]BitRange{
   545  				BaseChunkIdx:     {{0, PallocChunkPages}},
   546  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
   547  				BaseChunkIdx + 2: {{0, PallocChunkPages}},
   548  				BaseChunkIdx + 3: {{0, PallocChunkPages}},
   549  				BaseChunkIdx + 4: {{0, PallocChunkPages}},
   550  				BaseChunkIdx + 5: {{0, PallocChunkPages}},
   551  				BaseChunkIdx + 6: {{0, PallocChunkPages}},
   552  				BaseChunkIdx + 7: {{0, 6}},
   553  			},
   554  		}
   555  		tests["StraddlePallocChunkPages*2"] = test{
   556  			before: map[ChunkIdx][]BitRange{
   557  				BaseChunkIdx:     {{0, PallocChunkPages / 2}},
   558  				BaseChunkIdx + 1: {},
   559  				BaseChunkIdx + 2: {{PallocChunkPages / 2, PallocChunkPages / 2}},
   560  			},
   561  			scav: map[ChunkIdx][]BitRange{
   562  				BaseChunkIdx:     {{0, 7}},
   563  				BaseChunkIdx + 1: {{3, 5}, {121, 10}},
   564  				BaseChunkIdx + 2: {{PallocChunkPages/2 + 12, 2}},
   565  			},
   566  			hits: []hit{
   567  				{PallocChunkPages * 2, PageBase(BaseChunkIdx, PallocChunkPages/2), 15 * PageSize},
   568  				{PallocChunkPages * 2, 0, 0},
   569  				{1, 0, 0},
   570  			},
   571  			after: map[ChunkIdx][]BitRange{
   572  				BaseChunkIdx:     {{0, PallocChunkPages}},
   573  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
   574  				BaseChunkIdx + 2: {{0, PallocChunkPages}},
   575  			},
   576  		}
   577  	}
   578  	// Disable these tests on iOS since we have a small address space.
   579  	// See #46860.
   580  	if PageAlloc64Bit != 0 && goos.IsIos == 0 {
   581  		const chunkIdxBigJump = 0x100000 // chunk index offset which translates to O(TiB)
   582  
   583  		// This test attempts to trigger a bug wherein we look at unmapped summary
   584  		// memory that isn't just in the case where we exhaust the heap.
   585  		//
   586  		// It achieves this by placing a chunk such that its summary will be
   587  		// at the very end of a physical page. It then also places another chunk
   588  		// much further up in the address space, such that any allocations into the
   589  		// first chunk do not exhaust the heap and the second chunk's summary is not in the
   590  		// page immediately adjacent to the first chunk's summary's page.
   591  		// Allocating into this first chunk to exhaustion and then into the second
   592  		// chunk may then trigger a check in the allocator which erroneously looks at
   593  		// unmapped summary memory and crashes.
   594  
   595  		// Figure out how many chunks are in a physical page, then align BaseChunkIdx
   596  		// to a physical page in the chunk summary array. Here we only assume that
   597  		// each summary array is aligned to some physical page.
   598  		sumsPerPhysPage := ChunkIdx(PhysPageSize / PallocSumBytes)
   599  		baseChunkIdx := BaseChunkIdx &^ (sumsPerPhysPage - 1)
   600  		tests["DiscontiguousMappedSumBoundary"] = test{
   601  			before: map[ChunkIdx][]BitRange{
   602  				baseChunkIdx + sumsPerPhysPage - 1: {},
   603  				baseChunkIdx + chunkIdxBigJump:     {},
   604  			},
   605  			scav: map[ChunkIdx][]BitRange{
   606  				baseChunkIdx + sumsPerPhysPage - 1: {},
   607  				baseChunkIdx + chunkIdxBigJump:     {},
   608  			},
   609  			hits: []hit{
   610  				{PallocChunkPages - 1, PageBase(baseChunkIdx+sumsPerPhysPage-1, 0), 0},
   611  				{1, PageBase(baseChunkIdx+sumsPerPhysPage-1, PallocChunkPages-1), 0},
   612  				{1, PageBase(baseChunkIdx+chunkIdxBigJump, 0), 0},
   613  				{PallocChunkPages - 1, PageBase(baseChunkIdx+chunkIdxBigJump, 1), 0},
   614  				{1, 0, 0},
   615  			},
   616  			after: map[ChunkIdx][]BitRange{
   617  				baseChunkIdx + sumsPerPhysPage - 1: {{0, PallocChunkPages}},
   618  				baseChunkIdx + chunkIdxBigJump:     {{0, PallocChunkPages}},
   619  			},
   620  		}
   621  
   622  		// Test to check for issue #40191. Essentially, the candidate searchAddr
   623  		// discovered by find may not point to mapped memory, so we need to handle
   624  		// that explicitly.
   625  		//
   626  		// chunkIdxSmallOffset is an offset intended to be used within chunkIdxBigJump.
   627  		// It is far enough within chunkIdxBigJump that the summaries at the beginning
   628  		// of an address range the size of chunkIdxBigJump will not be mapped in.
   629  		const chunkIdxSmallOffset = 0x503
   630  		tests["DiscontiguousBadSearchAddr"] = test{
   631  			before: map[ChunkIdx][]BitRange{
   632  				// The mechanism for the bug involves three chunks, A, B, and C, which are
   633  				// far apart in the address space. In particular, B is chunkIdxBigJump +
   634  				// chunkIdxSmalloffset chunks away from B, and C is 2*chunkIdxBigJump chunks
   635  				// away from A. A has 1 page free, B has several (NOT at the end of B), and
   636  				// C is totally free.
   637  				// Note that B's free memory must not be at the end of B because the fast
   638  				// path in the page allocator will check if the searchAddr even gives us
   639  				// enough space to place the allocation in a chunk before accessing the
   640  				// summary.
   641  				BaseChunkIdx + chunkIdxBigJump*0: {{0, PallocChunkPages - 1}},
   642  				BaseChunkIdx + chunkIdxBigJump*1 + chunkIdxSmallOffset: {
   643  					{0, PallocChunkPages - 10},
   644  					{PallocChunkPages - 1, 1},
   645  				},
   646  				BaseChunkIdx + chunkIdxBigJump*2: {},
   647  			},
   648  			scav: map[ChunkIdx][]BitRange{
   649  				BaseChunkIdx + chunkIdxBigJump*0:                       {},
   650  				BaseChunkIdx + chunkIdxBigJump*1 + chunkIdxSmallOffset: {},
   651  				BaseChunkIdx + chunkIdxBigJump*2:                       {},
   652  			},
   653  			hits: []hit{
   654  				// We first allocate into A to set the page allocator's searchAddr to the
   655  				// end of that chunk. That is the only purpose A serves.
   656  				{1, PageBase(BaseChunkIdx, PallocChunkPages-1), 0},
   657  				// Then, we make a big allocation that doesn't fit into B, and so must be
   658  				// fulfilled by C.
   659  				//
   660  				// On the way to fulfilling the allocation into C, we estimate searchAddr
   661  				// using the summary structure, but that will give us a searchAddr of
   662  				// B's base address minus chunkIdxSmallOffset chunks. These chunks will
   663  				// not be mapped.
   664  				{100, PageBase(baseChunkIdx+chunkIdxBigJump*2, 0), 0},
   665  				// Now we try to make a smaller allocation that can be fulfilled by B.
   666  				// In an older implementation of the page allocator, this will segfault,
   667  				// because this last allocation will first try to access the summary
   668  				// for B's base address minus chunkIdxSmallOffset chunks in the fast path,
   669  				// and this will not be mapped.
   670  				{9, PageBase(baseChunkIdx+chunkIdxBigJump*1+chunkIdxSmallOffset, PallocChunkPages-10), 0},
   671  			},
   672  			after: map[ChunkIdx][]BitRange{
   673  				BaseChunkIdx + chunkIdxBigJump*0:                       {{0, PallocChunkPages}},
   674  				BaseChunkIdx + chunkIdxBigJump*1 + chunkIdxSmallOffset: {{0, PallocChunkPages}},
   675  				BaseChunkIdx + chunkIdxBigJump*2:                       {{0, 100}},
   676  			},
   677  		}
   678  	}
   679  	for name, v := range tests {
   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  		t.Run(fmt.Sprintf("%d", npages), func(t *testing.T) {
   707  			// Construct b.
   708  			bDesc := make(map[ChunkIdx][]BitRange)
   709  			for i := ChunkIdx(0); i < 4; i++ {
   710  				bDesc[BaseChunkIdx+i] = []BitRange{}
   711  			}
   712  			b := NewPageAlloc(bDesc, nil)
   713  			defer FreePageAlloc(b)
   714  
   715  			// Allocate into b with npages until we've exhausted the heap.
   716  			nAlloc := (PallocChunkPages * 4) / int(npages)
   717  			for i := 0; i < nAlloc; i++ {
   718  				addr := PageBase(BaseChunkIdx, uint(i)*uint(npages))
   719  				if a, _ := b.Alloc(npages); a != addr {
   720  					t.Fatalf("bad alloc #%d: want 0x%x, got 0x%x", i+1, addr, a)
   721  				}
   722  			}
   723  
   724  			// Check to make sure the next allocation fails.
   725  			if a, _ := b.Alloc(npages); a != 0 {
   726  				t.Fatalf("bad alloc #%d: want 0, got 0x%x", nAlloc, a)
   727  			}
   728  
   729  			// Construct what we want the heap to look like now.
   730  			allocPages := nAlloc * int(npages)
   731  			wantDesc := make(map[ChunkIdx][]BitRange)
   732  			for i := ChunkIdx(0); i < 4; i++ {
   733  				if allocPages >= PallocChunkPages {
   734  					wantDesc[BaseChunkIdx+i] = []BitRange{{0, PallocChunkPages}}
   735  					allocPages -= PallocChunkPages
   736  				} else if allocPages > 0 {
   737  					wantDesc[BaseChunkIdx+i] = []BitRange{{0, uint(allocPages)}}
   738  					allocPages = 0
   739  				} else {
   740  					wantDesc[BaseChunkIdx+i] = []BitRange{}
   741  				}
   742  			}
   743  			want := NewPageAlloc(wantDesc, nil)
   744  			defer FreePageAlloc(want)
   745  
   746  			// Check to make sure the heap b matches what we want.
   747  			checkPageAlloc(t, want, b)
   748  		})
   749  	}
   750  }
   751  
   752  func TestPageAllocFree(t *testing.T) {
   753  	if GOOS == "openbsd" && testing.Short() {
   754  		t.Skip("skipping because virtual memory is limited; see #36210")
   755  	}
   756  	type test struct {
   757  		before map[ChunkIdx][]BitRange
   758  		after  map[ChunkIdx][]BitRange
   759  		npages uintptr
   760  		frees  []uintptr
   761  	}
   762  	tests := map[string]test{
   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  		"FreePallocChunkPages": {
   844  			npages: PallocChunkPages,
   845  			before: map[ChunkIdx][]BitRange{
   846  				BaseChunkIdx: {{0, PallocChunkPages}},
   847  			},
   848  			frees: []uintptr{
   849  				PageBase(BaseChunkIdx, 0),
   850  			},
   851  			after: map[ChunkIdx][]BitRange{
   852  				BaseChunkIdx: {},
   853  			},
   854  		},
   855  		"StraddlePallocChunkPages": {
   856  			npages: PallocChunkPages,
   857  			before: map[ChunkIdx][]BitRange{
   858  				BaseChunkIdx:     {{PallocChunkPages / 2, PallocChunkPages / 2}},
   859  				BaseChunkIdx + 1: {{0, PallocChunkPages / 2}},
   860  			},
   861  			frees: []uintptr{
   862  				PageBase(BaseChunkIdx, PallocChunkPages/2),
   863  			},
   864  			after: map[ChunkIdx][]BitRange{
   865  				BaseChunkIdx:     {},
   866  				BaseChunkIdx + 1: {},
   867  			},
   868  		},
   869  		"StraddlePallocChunkPages+1": {
   870  			npages: PallocChunkPages + 1,
   871  			before: map[ChunkIdx][]BitRange{
   872  				BaseChunkIdx:     {{0, PallocChunkPages}},
   873  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
   874  			},
   875  			frees: []uintptr{
   876  				PageBase(BaseChunkIdx, PallocChunkPages/2),
   877  			},
   878  			after: map[ChunkIdx][]BitRange{
   879  				BaseChunkIdx:     {{0, PallocChunkPages / 2}},
   880  				BaseChunkIdx + 1: {{PallocChunkPages/2 + 1, PallocChunkPages/2 - 1}},
   881  			},
   882  		},
   883  		"FreePallocChunkPages*2": {
   884  			npages: PallocChunkPages * 2,
   885  			before: map[ChunkIdx][]BitRange{
   886  				BaseChunkIdx:     {{0, PallocChunkPages}},
   887  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
   888  			},
   889  			frees: []uintptr{
   890  				PageBase(BaseChunkIdx, 0),
   891  			},
   892  			after: map[ChunkIdx][]BitRange{
   893  				BaseChunkIdx:     {},
   894  				BaseChunkIdx + 1: {},
   895  			},
   896  		},
   897  		"StraddlePallocChunkPages*2": {
   898  			npages: PallocChunkPages * 2,
   899  			before: map[ChunkIdx][]BitRange{
   900  				BaseChunkIdx:     {{0, PallocChunkPages}},
   901  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
   902  				BaseChunkIdx + 2: {{0, PallocChunkPages}},
   903  			},
   904  			frees: []uintptr{
   905  				PageBase(BaseChunkIdx, PallocChunkPages/2),
   906  			},
   907  			after: map[ChunkIdx][]BitRange{
   908  				BaseChunkIdx:     {{0, PallocChunkPages / 2}},
   909  				BaseChunkIdx + 1: {},
   910  				BaseChunkIdx + 2: {{PallocChunkPages / 2, PallocChunkPages / 2}},
   911  			},
   912  		},
   913  		"AllFreePallocChunkPages*7+5": {
   914  			npages: PallocChunkPages*7 + 5,
   915  			before: map[ChunkIdx][]BitRange{
   916  				BaseChunkIdx:     {{0, PallocChunkPages}},
   917  				BaseChunkIdx + 1: {{0, PallocChunkPages}},
   918  				BaseChunkIdx + 2: {{0, PallocChunkPages}},
   919  				BaseChunkIdx + 3: {{0, PallocChunkPages}},
   920  				BaseChunkIdx + 4: {{0, PallocChunkPages}},
   921  				BaseChunkIdx + 5: {{0, PallocChunkPages}},
   922  				BaseChunkIdx + 6: {{0, PallocChunkPages}},
   923  				BaseChunkIdx + 7: {{0, PallocChunkPages}},
   924  			},
   925  			frees: []uintptr{
   926  				PageBase(BaseChunkIdx, 0),
   927  			},
   928  			after: map[ChunkIdx][]BitRange{
   929  				BaseChunkIdx:     {},
   930  				BaseChunkIdx + 1: {},
   931  				BaseChunkIdx + 2: {},
   932  				BaseChunkIdx + 3: {},
   933  				BaseChunkIdx + 4: {},
   934  				BaseChunkIdx + 5: {},
   935  				BaseChunkIdx + 6: {},
   936  				BaseChunkIdx + 7: {{5, PallocChunkPages - 5}},
   937  			},
   938  		},
   939  	}
   940  	if PallocChunkPages >= 512 {
   941  		// avoid constant overflow when PallocChunkPages is small
   942  		var PallocChunkPages uint = PallocChunkPages
   943  		tests["Free64"] = test{
   944  			npages: 64,
   945  			before: map[ChunkIdx][]BitRange{
   946  				BaseChunkIdx: {{0, PallocChunkPages}},
   947  			},
   948  			frees: []uintptr{
   949  				PageBase(BaseChunkIdx, 0),
   950  				PageBase(BaseChunkIdx, 64),
   951  				PageBase(BaseChunkIdx, 128),
   952  			},
   953  			after: map[ChunkIdx][]BitRange{
   954  				BaseChunkIdx: {{192, PallocChunkPages - 192}},
   955  			},
   956  		}
   957  		tests["Free65"] = test{
   958  			npages: 65,
   959  			before: map[ChunkIdx][]BitRange{
   960  				BaseChunkIdx: {{0, PallocChunkPages}},
   961  			},
   962  			frees: []uintptr{
   963  				PageBase(BaseChunkIdx, 0),
   964  				PageBase(BaseChunkIdx, 65),
   965  				PageBase(BaseChunkIdx, 130),
   966  			},
   967  			after: map[ChunkIdx][]BitRange{
   968  				BaseChunkIdx: {{195, PallocChunkPages - 195}},
   969  			},
   970  		}
   971  	}
   972  	for name, v := range tests {
   973  		t.Run(name, func(t *testing.T) {
   974  			b := NewPageAlloc(v.before, nil)
   975  			defer FreePageAlloc(b)
   976  
   977  			for _, addr := range v.frees {
   978  				b.Free(addr, v.npages)
   979  			}
   980  			want := NewPageAlloc(v.after, nil)
   981  			defer FreePageAlloc(want)
   982  
   983  			checkPageAlloc(t, want, b)
   984  		})
   985  	}
   986  }
   987  
   988  func TestPageAllocAllocAndFree(t *testing.T) {
   989  	if GOOS == "openbsd" && testing.Short() {
   990  		t.Skip("skipping because virtual memory is limited; see #36210")
   991  	}
   992  	type hit struct {
   993  		alloc  bool
   994  		npages uintptr
   995  		base   uintptr
   996  	}
   997  	tests := map[string]struct {
   998  		init map[ChunkIdx][]BitRange
   999  		hits []hit
  1000  	}{
  1001  		// TODO(mknyszek): Write more tests here.
  1002  		"Chunks8": {
  1003  			init: map[ChunkIdx][]BitRange{
  1004  				BaseChunkIdx:     {},
  1005  				BaseChunkIdx + 1: {},
  1006  				BaseChunkIdx + 2: {},
  1007  				BaseChunkIdx + 3: {},
  1008  				BaseChunkIdx + 4: {},
  1009  				BaseChunkIdx + 5: {},
  1010  				BaseChunkIdx + 6: {},
  1011  				BaseChunkIdx + 7: {},
  1012  			},
  1013  			hits: []hit{
  1014  				{true, PallocChunkPages * 8, PageBase(BaseChunkIdx, 0)},
  1015  				{false, PallocChunkPages * 8, PageBase(BaseChunkIdx, 0)},
  1016  				{true, PallocChunkPages * 8, PageBase(BaseChunkIdx, 0)},
  1017  				{false, PallocChunkPages * 8, PageBase(BaseChunkIdx, 0)},
  1018  				{true, PallocChunkPages * 8, PageBase(BaseChunkIdx, 0)},
  1019  				{false, PallocChunkPages * 8, PageBase(BaseChunkIdx, 0)},
  1020  				{true, 1, PageBase(BaseChunkIdx, 0)},
  1021  				{false, 1, PageBase(BaseChunkIdx, 0)},
  1022  				{true, PallocChunkPages * 8, PageBase(BaseChunkIdx, 0)},
  1023  			},
  1024  		},
  1025  	}
  1026  	for name, v := range tests {
  1027  		t.Run(name, func(t *testing.T) {
  1028  			b := NewPageAlloc(v.init, nil)
  1029  			defer FreePageAlloc(b)
  1030  
  1031  			for iter, i := range v.hits {
  1032  				if i.alloc {
  1033  					if a, _ := b.Alloc(i.npages); a != i.base {
  1034  						t.Fatalf("bad alloc #%d: want 0x%x, got 0x%x", iter+1, i.base, a)
  1035  					}
  1036  				} else {
  1037  					b.Free(i.base, i.npages)
  1038  				}
  1039  			}
  1040  		})
  1041  	}
  1042  }
  1043  

View as plain text