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