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	. "runtime"
10	"testing"
11)
12
13func 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
43func 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				{PageBase(BaseChunkIdx, 0), PageBase(BaseChunkIdx+1, 0)},
58			},
59		},
60		"Contiguous2": {
61			chunks: []ChunkIdx{
62				BaseChunkIdx,
63				BaseChunkIdx + 1,
64			},
65			inUse: []AddrRange{
66				{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				{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				{PageBase(BaseChunkIdx, 0), PageBase(BaseChunkIdx+1, 0)},
89				{PageBase(BaseChunkIdx+2, 0), PageBase(BaseChunkIdx+3, 0)},
90				{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				{PageBase(BaseChunkIdx, 0), PageBase(BaseChunkIdx+3, 0)},
102				{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				{PageBase(BaseChunkIdx, 0), PageBase(BaseChunkIdx+2, 0)},
114				{PageBase(BaseChunkIdx+0x10, 0), PageBase(BaseChunkIdx+0x11, 0)},
115				{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				{PageBase(BaseChunkIdx, 0), PageBase(BaseChunkIdx+1, 0)},
133				{PageBase(BaseChunkIdx+2, 0), PageBase(BaseChunkIdx+3, 0)},
134				{PageBase(BaseChunkIdx+4, 0), PageBase(BaseChunkIdx+5, 0)},
135				{PageBase(BaseChunkIdx+6, 0), PageBase(BaseChunkIdx+7, 0)},
136				{PageBase(BaseChunkIdx+8, 0), PageBase(BaseChunkIdx+9, 0)},
137				{PageBase(BaseChunkIdx+10, 0), PageBase(BaseChunkIdx+11, 0)},
138				{PageBase(BaseChunkIdx+12, 0), PageBase(BaseChunkIdx+13, 0)},
139				{PageBase(BaseChunkIdx+14, 0), PageBase(BaseChunkIdx+15, 0)},
140				{PageBase(BaseChunkIdx+16, 0), PageBase(BaseChunkIdx+17, 0)},
141				{PageBase(BaseChunkIdx+18, 0), PageBase(BaseChunkIdx+19, 0)},
142				{PageBase(BaseChunkIdx+20, 0), PageBase(BaseChunkIdx+21, 0)},
143				{PageBase(BaseChunkIdx+22, 0), PageBase(BaseChunkIdx+23, 0)},
144				{PageBase(BaseChunkIdx+24, 0), PageBase(BaseChunkIdx+25, 0)},
145				{PageBase(BaseChunkIdx+26, 0), PageBase(BaseChunkIdx+27, 0)},
146				{PageBase(BaseChunkIdx+28, 0), PageBase(BaseChunkIdx+29, 0)},
147				{PageBase(BaseChunkIdx+30, 0), PageBase(BaseChunkIdx+31, 0)},
148				{PageBase(BaseChunkIdx+32, 0), PageBase(BaseChunkIdx+33, 0)},
149				{PageBase(BaseChunkIdx+34, 0), PageBase(BaseChunkIdx+35, 0)},
150				{PageBase(BaseChunkIdx+36, 0), PageBase(BaseChunkIdx+37, 0)},
151				{PageBase(BaseChunkIdx+38, 0), PageBase(BaseChunkIdx+39, 0)},
152				{PageBase(BaseChunkIdx+40, 0), PageBase(BaseChunkIdx+41, 0)},
153				{PageBase(BaseChunkIdx+42, 0), PageBase(BaseChunkIdx+43, 0)},
154				{PageBase(BaseChunkIdx+44, 0), PageBase(BaseChunkIdx+45, 0)},
155				{PageBase(BaseChunkIdx+46, 0), PageBase(BaseChunkIdx+47, 0)},
156				{PageBase(BaseChunkIdx+48, 0), PageBase(BaseChunkIdx+49, 0)},
157				{PageBase(BaseChunkIdx+50, 0), PageBase(BaseChunkIdx+51, 0)},
158				{PageBase(BaseChunkIdx+52, 0), PageBase(BaseChunkIdx+53, 0)},
159				{PageBase(BaseChunkIdx+54, 0), PageBase(BaseChunkIdx+55, 0)},
160				{PageBase(BaseChunkIdx+56, 0), PageBase(BaseChunkIdx+57, 0)},
161				{PageBase(BaseChunkIdx+58, 0), PageBase(BaseChunkIdx+59, 0)},
162				{PageBase(BaseChunkIdx+60, 0), PageBase(BaseChunkIdx+61, 0)},
163				{PageBase(BaseChunkIdx+62, 0), PageBase(BaseChunkIdx+63, 0)},
164				{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				{PageBase(BaseChunkIdx, 0), PageBase(BaseChunkIdx+1, 0)},
176				{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] != 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
221func 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	for name, v := range tests {
617		v := v
618		t.Run(name, func(t *testing.T) {
619			b := NewPageAlloc(v.before, v.scav)
620			defer FreePageAlloc(b)
621
622			for iter, i := range v.hits {
623				a, s := b.Alloc(i.npages)
624				if a != i.base {
625					t.Fatalf("bad alloc #%d: want base 0x%x, got 0x%x", iter+1, i.base, a)
626				}
627				if s != i.scav {
628					t.Fatalf("bad alloc #%d: want scav %d, got %d", iter+1, i.scav, s)
629				}
630			}
631			want := NewPageAlloc(v.after, v.scav)
632			defer FreePageAlloc(want)
633
634			checkPageAlloc(t, want, b)
635		})
636	}
637}
638
639func TestPageAllocExhaust(t *testing.T) {
640	if GOOS == "openbsd" && testing.Short() {
641		t.Skip("skipping because virtual memory is limited; see #36210")
642	}
643	for _, npages := range []uintptr{1, 2, 3, 4, 5, 8, 16, 64, 1024, 1025, 2048, 2049} {
644		npages := npages
645		t.Run(fmt.Sprintf("%d", npages), func(t *testing.T) {
646			// Construct b.
647			bDesc := make(map[ChunkIdx][]BitRange)
648			for i := ChunkIdx(0); i < 4; i++ {
649				bDesc[BaseChunkIdx+i] = []BitRange{}
650			}
651			b := NewPageAlloc(bDesc, nil)
652			defer FreePageAlloc(b)
653
654			// Allocate into b with npages until we've exhausted the heap.
655			nAlloc := (PallocChunkPages * 4) / int(npages)
656			for i := 0; i < nAlloc; i++ {
657				addr := PageBase(BaseChunkIdx, uint(i)*uint(npages))
658				if a, _ := b.Alloc(npages); a != addr {
659					t.Fatalf("bad alloc #%d: want 0x%x, got 0x%x", i+1, addr, a)
660				}
661			}
662
663			// Check to make sure the next allocation fails.
664			if a, _ := b.Alloc(npages); a != 0 {
665				t.Fatalf("bad alloc #%d: want 0, got 0x%x", nAlloc, a)
666			}
667
668			// Construct what we want the heap to look like now.
669			allocPages := nAlloc * int(npages)
670			wantDesc := make(map[ChunkIdx][]BitRange)
671			for i := ChunkIdx(0); i < 4; i++ {
672				if allocPages >= PallocChunkPages {
673					wantDesc[BaseChunkIdx+i] = []BitRange{{0, PallocChunkPages}}
674					allocPages -= PallocChunkPages
675				} else if allocPages > 0 {
676					wantDesc[BaseChunkIdx+i] = []BitRange{{0, uint(allocPages)}}
677					allocPages = 0
678				} else {
679					wantDesc[BaseChunkIdx+i] = []BitRange{}
680				}
681			}
682			want := NewPageAlloc(wantDesc, nil)
683			defer FreePageAlloc(want)
684
685			// Check to make sure the heap b matches what we want.
686			checkPageAlloc(t, want, b)
687		})
688	}
689}
690
691func TestPageAllocFree(t *testing.T) {
692	if GOOS == "openbsd" && testing.Short() {
693		t.Skip("skipping because virtual memory is limited; see #36210")
694	}
695	tests := map[string]struct {
696		before map[ChunkIdx][]BitRange
697		after  map[ChunkIdx][]BitRange
698		npages uintptr
699		frees  []uintptr
700	}{
701		"Free1": {
702			npages: 1,
703			before: map[ChunkIdx][]BitRange{
704				BaseChunkIdx: {{0, PallocChunkPages}},
705			},
706			frees: []uintptr{
707				PageBase(BaseChunkIdx, 0),
708				PageBase(BaseChunkIdx, 1),
709				PageBase(BaseChunkIdx, 2),
710				PageBase(BaseChunkIdx, 3),
711				PageBase(BaseChunkIdx, 4),
712			},
713			after: map[ChunkIdx][]BitRange{
714				BaseChunkIdx: {{5, PallocChunkPages - 5}},
715			},
716		},
717		"ManyArena1": {
718			npages: 1,
719			before: map[ChunkIdx][]BitRange{
720				BaseChunkIdx:     {{0, PallocChunkPages}},
721				BaseChunkIdx + 1: {{0, PallocChunkPages}},
722				BaseChunkIdx + 2: {{0, PallocChunkPages}},
723			},
724			frees: []uintptr{
725				PageBase(BaseChunkIdx, PallocChunkPages/2),
726				PageBase(BaseChunkIdx+1, 0),
727				PageBase(BaseChunkIdx+2, PallocChunkPages-1),
728			},
729			after: map[ChunkIdx][]BitRange{
730				BaseChunkIdx:     {{0, PallocChunkPages / 2}, {PallocChunkPages/2 + 1, PallocChunkPages/2 - 1}},
731				BaseChunkIdx + 1: {{1, PallocChunkPages - 1}},
732				BaseChunkIdx + 2: {{0, PallocChunkPages - 1}},
733			},
734		},
735		"Free2": {
736			npages: 2,
737			before: map[ChunkIdx][]BitRange{
738				BaseChunkIdx: {{0, PallocChunkPages}},
739			},
740			frees: []uintptr{
741				PageBase(BaseChunkIdx, 0),
742				PageBase(BaseChunkIdx, 2),
743				PageBase(BaseChunkIdx, 4),
744				PageBase(BaseChunkIdx, 6),
745				PageBase(BaseChunkIdx, 8),
746			},
747			after: map[ChunkIdx][]BitRange{
748				BaseChunkIdx: {{10, PallocChunkPages - 10}},
749			},
750		},
751		"Straddle2": {
752			npages: 2,
753			before: map[ChunkIdx][]BitRange{
754				BaseChunkIdx:     {{PallocChunkPages - 1, 1}},
755				BaseChunkIdx + 1: {{0, 1}},
756			},
757			frees: []uintptr{
758				PageBase(BaseChunkIdx, PallocChunkPages-1),
759			},
760			after: map[ChunkIdx][]BitRange{
761				BaseChunkIdx:     {},
762				BaseChunkIdx + 1: {},
763			},
764		},
765		"Free5": {
766			npages: 5,
767			before: map[ChunkIdx][]BitRange{
768				BaseChunkIdx: {{0, PallocChunkPages}},
769			},
770			frees: []uintptr{
771				PageBase(BaseChunkIdx, 0),
772				PageBase(BaseChunkIdx, 5),
773				PageBase(BaseChunkIdx, 10),
774				PageBase(BaseChunkIdx, 15),
775				PageBase(BaseChunkIdx, 20),
776			},
777			after: map[ChunkIdx][]BitRange{
778				BaseChunkIdx: {{25, PallocChunkPages - 25}},
779			},
780		},
781		"Free64": {
782			npages: 64,
783			before: map[ChunkIdx][]BitRange{
784				BaseChunkIdx: {{0, PallocChunkPages}},
785			},
786			frees: []uintptr{
787				PageBase(BaseChunkIdx, 0),
788				PageBase(BaseChunkIdx, 64),
789				PageBase(BaseChunkIdx, 128),
790			},
791			after: map[ChunkIdx][]BitRange{
792				BaseChunkIdx: {{192, PallocChunkPages - 192}},
793			},
794		},
795		"Free65": {
796			npages: 65,
797			before: map[ChunkIdx][]BitRange{
798				BaseChunkIdx: {{0, PallocChunkPages}},
799			},
800			frees: []uintptr{
801				PageBase(BaseChunkIdx, 0),
802				PageBase(BaseChunkIdx, 65),
803				PageBase(BaseChunkIdx, 130),
804			},
805			after: map[ChunkIdx][]BitRange{
806				BaseChunkIdx: {{195, PallocChunkPages - 195}},
807			},
808		},
809		"FreePallocChunkPages": {
810			npages: PallocChunkPages,
811			before: map[ChunkIdx][]BitRange{
812				BaseChunkIdx: {{0, PallocChunkPages}},
813			},
814			frees: []uintptr{
815				PageBase(BaseChunkIdx, 0),
816			},
817			after: map[ChunkIdx][]BitRange{
818				BaseChunkIdx: {},
819			},
820		},
821		"StraddlePallocChunkPages": {
822			npages: PallocChunkPages,
823			before: map[ChunkIdx][]BitRange{
824				BaseChunkIdx:     {{PallocChunkPages / 2, PallocChunkPages / 2}},
825				BaseChunkIdx + 1: {{0, PallocChunkPages / 2}},
826			},
827			frees: []uintptr{
828				PageBase(BaseChunkIdx, PallocChunkPages/2),
829			},
830			after: map[ChunkIdx][]BitRange{
831				BaseChunkIdx:     {},
832				BaseChunkIdx + 1: {},
833			},
834		},
835		"StraddlePallocChunkPages+1": {
836			npages: PallocChunkPages + 1,
837			before: map[ChunkIdx][]BitRange{
838				BaseChunkIdx:     {{0, PallocChunkPages}},
839				BaseChunkIdx + 1: {{0, PallocChunkPages}},
840			},
841			frees: []uintptr{
842				PageBase(BaseChunkIdx, PallocChunkPages/2),
843			},
844			after: map[ChunkIdx][]BitRange{
845				BaseChunkIdx:     {{0, PallocChunkPages / 2}},
846				BaseChunkIdx + 1: {{PallocChunkPages/2 + 1, PallocChunkPages/2 - 1}},
847			},
848		},
849		"FreePallocChunkPages*2": {
850			npages: PallocChunkPages * 2,
851			before: map[ChunkIdx][]BitRange{
852				BaseChunkIdx:     {{0, PallocChunkPages}},
853				BaseChunkIdx + 1: {{0, PallocChunkPages}},
854			},
855			frees: []uintptr{
856				PageBase(BaseChunkIdx, 0),
857			},
858			after: map[ChunkIdx][]BitRange{
859				BaseChunkIdx:     {},
860				BaseChunkIdx + 1: {},
861			},
862		},
863		"StraddlePallocChunkPages*2": {
864			npages: PallocChunkPages * 2,
865			before: map[ChunkIdx][]BitRange{
866				BaseChunkIdx:     {{0, PallocChunkPages}},
867				BaseChunkIdx + 1: {{0, PallocChunkPages}},
868				BaseChunkIdx + 2: {{0, PallocChunkPages}},
869			},
870			frees: []uintptr{
871				PageBase(BaseChunkIdx, PallocChunkPages/2),
872			},
873			after: map[ChunkIdx][]BitRange{
874				BaseChunkIdx:     {{0, PallocChunkPages / 2}},
875				BaseChunkIdx + 1: {},
876				BaseChunkIdx + 2: {{PallocChunkPages / 2, PallocChunkPages / 2}},
877			},
878		},
879		"AllFreePallocChunkPages*7+5": {
880			npages: PallocChunkPages*7 + 5,
881			before: map[ChunkIdx][]BitRange{
882				BaseChunkIdx:     {{0, PallocChunkPages}},
883				BaseChunkIdx + 1: {{0, PallocChunkPages}},
884				BaseChunkIdx + 2: {{0, PallocChunkPages}},
885				BaseChunkIdx + 3: {{0, PallocChunkPages}},
886				BaseChunkIdx + 4: {{0, PallocChunkPages}},
887				BaseChunkIdx + 5: {{0, PallocChunkPages}},
888				BaseChunkIdx + 6: {{0, PallocChunkPages}},
889				BaseChunkIdx + 7: {{0, PallocChunkPages}},
890			},
891			frees: []uintptr{
892				PageBase(BaseChunkIdx, 0),
893			},
894			after: map[ChunkIdx][]BitRange{
895				BaseChunkIdx:     {},
896				BaseChunkIdx + 1: {},
897				BaseChunkIdx + 2: {},
898				BaseChunkIdx + 3: {},
899				BaseChunkIdx + 4: {},
900				BaseChunkIdx + 5: {},
901				BaseChunkIdx + 6: {},
902				BaseChunkIdx + 7: {{5, PallocChunkPages - 5}},
903			},
904		},
905	}
906	for name, v := range tests {
907		v := v
908		t.Run(name, func(t *testing.T) {
909			b := NewPageAlloc(v.before, nil)
910			defer FreePageAlloc(b)
911
912			for _, addr := range v.frees {
913				b.Free(addr, v.npages)
914			}
915			want := NewPageAlloc(v.after, nil)
916			defer FreePageAlloc(want)
917
918			checkPageAlloc(t, want, b)
919		})
920	}
921}
922
923func TestPageAllocAllocAndFree(t *testing.T) {
924	if GOOS == "openbsd" && testing.Short() {
925		t.Skip("skipping because virtual memory is limited; see #36210")
926	}
927	type hit struct {
928		alloc  bool
929		npages uintptr
930		base   uintptr
931	}
932	tests := map[string]struct {
933		init map[ChunkIdx][]BitRange
934		hits []hit
935	}{
936		// TODO(mknyszek): Write more tests here.
937		"Chunks8": {
938			init: map[ChunkIdx][]BitRange{
939				BaseChunkIdx:     {},
940				BaseChunkIdx + 1: {},
941				BaseChunkIdx + 2: {},
942				BaseChunkIdx + 3: {},
943				BaseChunkIdx + 4: {},
944				BaseChunkIdx + 5: {},
945				BaseChunkIdx + 6: {},
946				BaseChunkIdx + 7: {},
947			},
948			hits: []hit{
949				{true, PallocChunkPages * 8, PageBase(BaseChunkIdx, 0)},
950				{false, PallocChunkPages * 8, PageBase(BaseChunkIdx, 0)},
951				{true, PallocChunkPages * 8, PageBase(BaseChunkIdx, 0)},
952				{false, PallocChunkPages * 8, PageBase(BaseChunkIdx, 0)},
953				{true, PallocChunkPages * 8, PageBase(BaseChunkIdx, 0)},
954				{false, PallocChunkPages * 8, PageBase(BaseChunkIdx, 0)},
955				{true, 1, PageBase(BaseChunkIdx, 0)},
956				{false, 1, PageBase(BaseChunkIdx, 0)},
957				{true, PallocChunkPages * 8, PageBase(BaseChunkIdx, 0)},
958			},
959		},
960	}
961	for name, v := range tests {
962		v := v
963		t.Run(name, func(t *testing.T) {
964			b := NewPageAlloc(v.init, nil)
965			defer FreePageAlloc(b)
966
967			for iter, i := range v.hits {
968				if i.alloc {
969					if a, _ := b.Alloc(i.npages); a != i.base {
970						t.Fatalf("bad alloc #%d: want 0x%x, got 0x%x", iter+1, i.base, a)
971					}
972				} else {
973					b.Free(i.base, i.npages)
974				}
975			}
976		})
977	}
978}
979