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	"math/rand"
9	. "runtime"
10	"testing"
11)
12
13func checkPageCache(t *testing.T, got, want PageCache) {
14	if got.Base() != want.Base() {
15		t.Errorf("bad pageCache base: got 0x%x, want 0x%x", got.Base(), want.Base())
16	}
17	if got.Cache() != want.Cache() {
18		t.Errorf("bad pageCache bits: got %016x, want %016x", got.Base(), want.Base())
19	}
20	if got.Scav() != want.Scav() {
21		t.Errorf("bad pageCache scav: got %016x, want %016x", got.Scav(), want.Scav())
22	}
23}
24
25func TestPageCacheAlloc(t *testing.T) {
26	base := PageBase(BaseChunkIdx, 0)
27	type hit struct {
28		npages uintptr
29		base   uintptr
30		scav   uintptr
31	}
32	tests := map[string]struct {
33		cache PageCache
34		hits  []hit
35	}{
36		"Empty": {
37			cache: NewPageCache(base, 0, 0),
38			hits: []hit{
39				{1, 0, 0},
40				{2, 0, 0},
41				{3, 0, 0},
42				{4, 0, 0},
43				{5, 0, 0},
44				{11, 0, 0},
45				{12, 0, 0},
46				{16, 0, 0},
47				{27, 0, 0},
48				{32, 0, 0},
49				{43, 0, 0},
50				{57, 0, 0},
51				{64, 0, 0},
52				{121, 0, 0},
53			},
54		},
55		"Lo1": {
56			cache: NewPageCache(base, 0x1, 0x1),
57			hits: []hit{
58				{1, base, PageSize},
59				{1, 0, 0},
60				{10, 0, 0},
61			},
62		},
63		"Hi1": {
64			cache: NewPageCache(base, 0x1<<63, 0x1),
65			hits: []hit{
66				{1, base + 63*PageSize, 0},
67				{1, 0, 0},
68				{10, 0, 0},
69			},
70		},
71		"Swiss1": {
72			cache: NewPageCache(base, 0x20005555, 0x5505),
73			hits: []hit{
74				{2, 0, 0},
75				{1, base, PageSize},
76				{1, base + 2*PageSize, PageSize},
77				{1, base + 4*PageSize, 0},
78				{1, base + 6*PageSize, 0},
79				{1, base + 8*PageSize, PageSize},
80				{1, base + 10*PageSize, PageSize},
81				{1, base + 12*PageSize, PageSize},
82				{1, base + 14*PageSize, PageSize},
83				{1, base + 29*PageSize, 0},
84				{1, 0, 0},
85				{10, 0, 0},
86			},
87		},
88		"Lo2": {
89			cache: NewPageCache(base, 0x3, 0x2<<62),
90			hits: []hit{
91				{2, base, 0},
92				{2, 0, 0},
93				{1, 0, 0},
94			},
95		},
96		"Hi2": {
97			cache: NewPageCache(base, 0x3<<62, 0x3<<62),
98			hits: []hit{
99				{2, base + 62*PageSize, 2 * PageSize},
100				{2, 0, 0},
101				{1, 0, 0},
102			},
103		},
104		"Swiss2": {
105			cache: NewPageCache(base, 0x3333<<31, 0x3030<<31),
106			hits: []hit{
107				{2, base + 31*PageSize, 0},
108				{2, base + 35*PageSize, 2 * PageSize},
109				{2, base + 39*PageSize, 0},
110				{2, base + 43*PageSize, 2 * PageSize},
111				{2, 0, 0},
112			},
113		},
114		"Hi53": {
115			cache: NewPageCache(base, ((uint64(1)<<53)-1)<<10, ((uint64(1)<<16)-1)<<10),
116			hits: []hit{
117				{53, base + 10*PageSize, 16 * PageSize},
118				{53, 0, 0},
119				{1, 0, 0},
120			},
121		},
122		"Full53": {
123			cache: NewPageCache(base, ^uint64(0), ((uint64(1)<<16)-1)<<10),
124			hits: []hit{
125				{53, base, 16 * PageSize},
126				{53, 0, 0},
127				{1, base + 53*PageSize, 0},
128			},
129		},
130		"Full64": {
131			cache: NewPageCache(base, ^uint64(0), ^uint64(0)),
132			hits: []hit{
133				{64, base, 64 * PageSize},
134				{64, 0, 0},
135				{1, 0, 0},
136			},
137		},
138		"FullMixed": {
139			cache: NewPageCache(base, ^uint64(0), ^uint64(0)),
140			hits: []hit{
141				{5, base, 5 * PageSize},
142				{7, base + 5*PageSize, 7 * PageSize},
143				{1, base + 12*PageSize, 1 * PageSize},
144				{23, base + 13*PageSize, 23 * PageSize},
145				{63, 0, 0},
146				{3, base + 36*PageSize, 3 * PageSize},
147				{3, base + 39*PageSize, 3 * PageSize},
148				{3, base + 42*PageSize, 3 * PageSize},
149				{12, base + 45*PageSize, 12 * PageSize},
150				{11, 0, 0},
151				{4, base + 57*PageSize, 4 * PageSize},
152				{4, 0, 0},
153				{6, 0, 0},
154				{36, 0, 0},
155				{2, base + 61*PageSize, 2 * PageSize},
156				{3, 0, 0},
157				{1, base + 63*PageSize, 1 * PageSize},
158				{4, 0, 0},
159				{2, 0, 0},
160				{62, 0, 0},
161				{1, 0, 0},
162			},
163		},
164	}
165	for name, test := range tests {
166		test := test
167		t.Run(name, func(t *testing.T) {
168			c := test.cache
169			for i, h := range test.hits {
170				b, s := c.Alloc(h.npages)
171				if b != h.base {
172					t.Fatalf("bad alloc base #%d: got 0x%x, want 0x%x", i, b, h.base)
173				}
174				if s != h.scav {
175					t.Fatalf("bad alloc scav #%d: got %d, want %d", i, s, h.scav)
176				}
177			}
178		})
179	}
180}
181
182func TestPageCacheFlush(t *testing.T) {
183	if GOOS == "openbsd" && testing.Short() {
184		t.Skip("skipping because virtual memory is limited; see #36210")
185	}
186	bits64ToBitRanges := func(bits uint64, base uint) []BitRange {
187		var ranges []BitRange
188		start, size := uint(0), uint(0)
189		for i := 0; i < 64; i++ {
190			if bits&(1<<i) != 0 {
191				if size == 0 {
192					start = uint(i) + base
193				}
194				size++
195			} else {
196				if size != 0 {
197					ranges = append(ranges, BitRange{start, size})
198					size = 0
199				}
200			}
201		}
202		if size != 0 {
203			ranges = append(ranges, BitRange{start, size})
204		}
205		return ranges
206	}
207	runTest := func(t *testing.T, base uint, cache, scav uint64) {
208		// Set up the before state.
209		beforeAlloc := map[ChunkIdx][]BitRange{
210			BaseChunkIdx: {{base, 64}},
211		}
212		beforeScav := map[ChunkIdx][]BitRange{
213			BaseChunkIdx: {},
214		}
215		b := NewPageAlloc(beforeAlloc, beforeScav)
216		defer FreePageAlloc(b)
217
218		// Create and flush the cache.
219		c := NewPageCache(PageBase(BaseChunkIdx, base), cache, scav)
220		c.Flush(b)
221		if !c.Empty() {
222			t.Errorf("pageCache flush did not clear cache")
223		}
224
225		// Set up the expected after state.
226		afterAlloc := map[ChunkIdx][]BitRange{
227			BaseChunkIdx: bits64ToBitRanges(^cache, base),
228		}
229		afterScav := map[ChunkIdx][]BitRange{
230			BaseChunkIdx: bits64ToBitRanges(scav, base),
231		}
232		want := NewPageAlloc(afterAlloc, afterScav)
233		defer FreePageAlloc(want)
234
235		// Check to see if it worked.
236		checkPageAlloc(t, want, b)
237	}
238
239	// Empty.
240	runTest(t, 0, 0, 0)
241
242	// Full.
243	runTest(t, 0, ^uint64(0), ^uint64(0))
244
245	// Random.
246	for i := 0; i < 100; i++ {
247		// Generate random valid base within a chunk.
248		base := uint(rand.Intn(PallocChunkPages/64)) * 64
249
250		// Generate random cache.
251		cache := rand.Uint64()
252		scav := rand.Uint64() & cache
253
254		// Run the test.
255		runTest(t, base, cache, scav)
256	}
257}
258
259func TestPageAllocAllocToCache(t *testing.T) {
260	if GOOS == "openbsd" && testing.Short() {
261		t.Skip("skipping because virtual memory is limited; see #36210")
262	}
263	type test struct {
264		before map[ChunkIdx][]BitRange
265		scav   map[ChunkIdx][]BitRange
266		hits   []PageCache // expected base addresses and patterns
267		after  map[ChunkIdx][]BitRange
268	}
269	tests := map[string]test{
270		"AllFree": {
271			before: map[ChunkIdx][]BitRange{
272				BaseChunkIdx: {},
273			},
274			scav: map[ChunkIdx][]BitRange{
275				BaseChunkIdx: {{1, 1}, {64, 64}},
276			},
277			hits: []PageCache{
278				NewPageCache(PageBase(BaseChunkIdx, 0), ^uint64(0), 0x2),
279				NewPageCache(PageBase(BaseChunkIdx, 64), ^uint64(0), ^uint64(0)),
280				NewPageCache(PageBase(BaseChunkIdx, 128), ^uint64(0), 0),
281				NewPageCache(PageBase(BaseChunkIdx, 192), ^uint64(0), 0),
282			},
283			after: map[ChunkIdx][]BitRange{
284				BaseChunkIdx: {{0, 256}},
285			},
286		},
287		"ManyArena": {
288			before: map[ChunkIdx][]BitRange{
289				BaseChunkIdx:     {{0, PallocChunkPages}},
290				BaseChunkIdx + 1: {{0, PallocChunkPages}},
291				BaseChunkIdx + 2: {{0, PallocChunkPages - 64}},
292			},
293			scav: map[ChunkIdx][]BitRange{
294				BaseChunkIdx:     {{0, PallocChunkPages}},
295				BaseChunkIdx + 1: {{0, PallocChunkPages}},
296				BaseChunkIdx + 2: {},
297			},
298			hits: []PageCache{
299				NewPageCache(PageBase(BaseChunkIdx+2, PallocChunkPages-64), ^uint64(0), 0),
300			},
301			after: map[ChunkIdx][]BitRange{
302				BaseChunkIdx:     {{0, PallocChunkPages}},
303				BaseChunkIdx + 1: {{0, PallocChunkPages}},
304				BaseChunkIdx + 2: {{0, PallocChunkPages}},
305			},
306		},
307		"NotContiguous": {
308			before: map[ChunkIdx][]BitRange{
309				BaseChunkIdx:        {{0, PallocChunkPages}},
310				BaseChunkIdx + 0xff: {{0, 0}},
311			},
312			scav: map[ChunkIdx][]BitRange{
313				BaseChunkIdx:        {{0, PallocChunkPages}},
314				BaseChunkIdx + 0xff: {{31, 67}},
315			},
316			hits: []PageCache{
317				NewPageCache(PageBase(BaseChunkIdx+0xff, 0), ^uint64(0), ((uint64(1)<<33)-1)<<31),
318			},
319			after: map[ChunkIdx][]BitRange{
320				BaseChunkIdx:        {{0, PallocChunkPages}},
321				BaseChunkIdx + 0xff: {{0, 64}},
322			},
323		},
324		"First": {
325			before: map[ChunkIdx][]BitRange{
326				BaseChunkIdx: {{0, 32}, {33, 31}, {96, 32}},
327			},
328			scav: map[ChunkIdx][]BitRange{
329				BaseChunkIdx: {{1, 4}, {31, 5}, {66, 2}},
330			},
331			hits: []PageCache{
332				NewPageCache(PageBase(BaseChunkIdx, 0), 1<<32, 1<<32),
333				NewPageCache(PageBase(BaseChunkIdx, 64), (uint64(1)<<32)-1, 0x3<<2),
334			},
335			after: map[ChunkIdx][]BitRange{
336				BaseChunkIdx: {{0, 128}},
337			},
338		},
339		"Fail": {
340			before: map[ChunkIdx][]BitRange{
341				BaseChunkIdx: {{0, PallocChunkPages}},
342			},
343			hits: []PageCache{
344				NewPageCache(0, 0, 0),
345				NewPageCache(0, 0, 0),
346				NewPageCache(0, 0, 0),
347			},
348			after: map[ChunkIdx][]BitRange{
349				BaseChunkIdx: {{0, PallocChunkPages}},
350			},
351		},
352	}
353	if PageAlloc64Bit != 0 {
354		const chunkIdxBigJump = 0x100000 // chunk index offset which translates to O(TiB)
355
356		// This test is similar to the one with the same name for
357		// pageAlloc.alloc and serves the same purpose.
358		// See mpagealloc_test.go for details.
359		sumsPerPhysPage := ChunkIdx(PhysPageSize / PallocSumBytes)
360		baseChunkIdx := BaseChunkIdx &^ (sumsPerPhysPage - 1)
361		tests["DiscontiguousMappedSumBoundary"] = test{
362			before: map[ChunkIdx][]BitRange{
363				baseChunkIdx + sumsPerPhysPage - 1: {{0, PallocChunkPages - 1}},
364				baseChunkIdx + chunkIdxBigJump:     {{1, PallocChunkPages - 1}},
365			},
366			scav: map[ChunkIdx][]BitRange{
367				baseChunkIdx + sumsPerPhysPage - 1: {},
368				baseChunkIdx + chunkIdxBigJump:     {},
369			},
370			hits: []PageCache{
371				NewPageCache(PageBase(baseChunkIdx+sumsPerPhysPage-1, PallocChunkPages-64), 1<<63, 0),
372				NewPageCache(PageBase(baseChunkIdx+chunkIdxBigJump, 0), 1, 0),
373				NewPageCache(0, 0, 0),
374			},
375			after: map[ChunkIdx][]BitRange{
376				baseChunkIdx + sumsPerPhysPage - 1: {{0, PallocChunkPages}},
377				baseChunkIdx + chunkIdxBigJump:     {{0, PallocChunkPages}},
378			},
379		}
380	}
381	for name, v := range tests {
382		v := v
383		t.Run(name, func(t *testing.T) {
384			b := NewPageAlloc(v.before, v.scav)
385			defer FreePageAlloc(b)
386
387			for _, expect := range v.hits {
388				checkPageCache(t, b.AllocToCache(), expect)
389				if t.Failed() {
390					return
391				}
392			}
393			want := NewPageAlloc(v.after, v.scav)
394			defer FreePageAlloc(want)
395
396			checkPageAlloc(t, want, b)
397		})
398	}
399}
400