Source file src/runtime/mpagealloc_test.go

Documentation: runtime

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

View as plain text