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
5package runtime_test
6
7import (
8	"fmt"
9	"internal/goos"
10	. "runtime"
11	"testing"
12)
13
14func 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
44func 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
224func 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
701func 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
753func 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
985func 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