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	"math/rand"
10	. "runtime"
11	"testing"
12)
13
14// Ensures that got and want are the same, and if not, reports
15// detailed diff information.
16func checkPallocBits(t *testing.T, got, want *PallocBits) bool {
17	d := DiffPallocBits(got, want)
18	if len(d) != 0 {
19		t.Errorf("%d range(s) different", len(d))
20		for _, bits := range d {
21			t.Logf("\t@ bit index %d", bits.I)
22			t.Logf("\t|  got: %s", StringifyPallocBits(got, bits))
23			t.Logf("\t| want: %s", StringifyPallocBits(want, bits))
24		}
25		return false
26	}
27	return true
28}
29
30// makePallocBits produces an initialized PallocBits by setting
31// the ranges in s to 1 and the rest to zero.
32func makePallocBits(s []BitRange) *PallocBits {
33	b := new(PallocBits)
34	for _, v := range s {
35		b.AllocRange(v.I, v.N)
36	}
37	return b
38}
39
40// Ensures that PallocBits.AllocRange works, which is a fundamental
41// method used for testing and initialization since it's used by
42// makePallocBits.
43func TestPallocBitsAllocRange(t *testing.T) {
44	test := func(t *testing.T, i, n uint, want *PallocBits) {
45		checkPallocBits(t, makePallocBits([]BitRange{{i, n}}), want)
46	}
47	t.Run("OneLow", func(t *testing.T) {
48		want := new(PallocBits)
49		want[0] = 0x1
50		test(t, 0, 1, want)
51	})
52	t.Run("OneHigh", func(t *testing.T) {
53		want := new(PallocBits)
54		want[PallocChunkPages/64-1] = 1 << 63
55		test(t, PallocChunkPages-1, 1, want)
56	})
57	t.Run("Inner", func(t *testing.T) {
58		want := new(PallocBits)
59		want[2] = 0x3e
60		test(t, 129, 5, want)
61	})
62	t.Run("Aligned", func(t *testing.T) {
63		want := new(PallocBits)
64		want[2] = ^uint64(0)
65		want[3] = ^uint64(0)
66		test(t, 128, 128, want)
67	})
68	t.Run("Begin", func(t *testing.T) {
69		want := new(PallocBits)
70		want[0] = ^uint64(0)
71		want[1] = ^uint64(0)
72		want[2] = ^uint64(0)
73		want[3] = ^uint64(0)
74		want[4] = ^uint64(0)
75		want[5] = 0x1
76		test(t, 0, 321, want)
77	})
78	t.Run("End", func(t *testing.T) {
79		want := new(PallocBits)
80		want[PallocChunkPages/64-1] = ^uint64(0)
81		want[PallocChunkPages/64-2] = ^uint64(0)
82		want[PallocChunkPages/64-3] = ^uint64(0)
83		want[PallocChunkPages/64-4] = 1 << 63
84		test(t, PallocChunkPages-(64*3+1), 64*3+1, want)
85	})
86	t.Run("All", func(t *testing.T) {
87		want := new(PallocBits)
88		for i := range want {
89			want[i] = ^uint64(0)
90		}
91		test(t, 0, PallocChunkPages, want)
92	})
93}
94
95// Inverts every bit in the PallocBits.
96func invertPallocBits(b *PallocBits) {
97	for i := range b {
98		b[i] = ^b[i]
99	}
100}
101
102// Ensures two packed summaries are identical, and reports a detailed description
103// of the difference if they're not.
104func checkPallocSum(t *testing.T, got, want PallocSum) {
105	if got.Start() != want.Start() {
106		t.Errorf("inconsistent start: got %d, want %d", got.Start(), want.Start())
107	}
108	if got.Max() != want.Max() {
109		t.Errorf("inconsistent max: got %d, want %d", got.Max(), want.Max())
110	}
111	if got.End() != want.End() {
112		t.Errorf("inconsistent end: got %d, want %d", got.End(), want.End())
113	}
114}
115
116func TestMallocBitsPopcntRange(t *testing.T) {
117	type test struct {
118		i, n uint // bit range to popcnt over.
119		want uint // expected popcnt result on that range.
120	}
121	tests := map[string]struct {
122		init  []BitRange // bit ranges to set to 1 in the bitmap.
123		tests []test     // a set of popcnt tests to run over the bitmap.
124	}{
125		"None": {
126			tests: []test{
127				{0, 1, 0},
128				{5, 3, 0},
129				{2, 11, 0},
130				{PallocChunkPages/4 + 1, PallocChunkPages / 2, 0},
131				{0, PallocChunkPages, 0},
132			},
133		},
134		"All": {
135			init: []BitRange{{0, PallocChunkPages}},
136			tests: []test{
137				{0, 1, 1},
138				{5, 3, 3},
139				{2, 11, 11},
140				{PallocChunkPages/4 + 1, PallocChunkPages / 2, PallocChunkPages / 2},
141				{0, PallocChunkPages, PallocChunkPages},
142			},
143		},
144		"Half": {
145			init: []BitRange{{PallocChunkPages / 2, PallocChunkPages / 2}},
146			tests: []test{
147				{0, 1, 0},
148				{5, 3, 0},
149				{2, 11, 0},
150				{PallocChunkPages/2 - 1, 1, 0},
151				{PallocChunkPages / 2, 1, 1},
152				{PallocChunkPages/2 + 10, 1, 1},
153				{PallocChunkPages/2 - 1, 2, 1},
154				{PallocChunkPages / 4, PallocChunkPages / 4, 0},
155				{PallocChunkPages / 4, PallocChunkPages/4 + 1, 1},
156				{PallocChunkPages/4 + 1, PallocChunkPages / 2, PallocChunkPages/4 + 1},
157				{0, PallocChunkPages, PallocChunkPages / 2},
158			},
159		},
160		"OddBound": {
161			init: []BitRange{{0, 111}},
162			tests: []test{
163				{0, 1, 1},
164				{5, 3, 3},
165				{2, 11, 11},
166				{110, 2, 1},
167				{99, 50, 12},
168				{110, 1, 1},
169				{111, 1, 0},
170				{99, 1, 1},
171				{120, 1, 0},
172				{PallocChunkPages / 2, PallocChunkPages / 2, 0},
173				{0, PallocChunkPages, 111},
174			},
175		},
176		"Scattered": {
177			init: []BitRange{
178				{1, 3}, {5, 1}, {7, 1}, {10, 2}, {13, 1}, {15, 4},
179				{21, 1}, {23, 1}, {26, 2}, {30, 5}, {36, 2}, {40, 3},
180				{44, 6}, {51, 1}, {53, 2}, {58, 3}, {63, 1}, {67, 2},
181				{71, 10}, {84, 1}, {89, 7}, {99, 2}, {103, 1}, {107, 2},
182				{111, 1}, {113, 1}, {115, 1}, {118, 1}, {120, 2}, {125, 5},
183			},
184			tests: []test{
185				{0, 11, 6},
186				{0, 64, 39},
187				{13, 64, 40},
188				{64, 64, 34},
189				{0, 128, 73},
190				{1, 128, 74},
191				{0, PallocChunkPages, 75},
192			},
193		},
194	}
195	for name, v := range tests {
196		v := v
197		t.Run(name, func(t *testing.T) {
198			b := makePallocBits(v.init)
199			for _, h := range v.tests {
200				if got := b.PopcntRange(h.i, h.n); got != h.want {
201					t.Errorf("bad popcnt (i=%d, n=%d): got %d, want %d", h.i, h.n, got, h.want)
202				}
203			}
204		})
205	}
206}
207
208// Ensures computing bit summaries works as expected by generating random
209// bitmaps and checking against a reference implementation.
210func TestPallocBitsSummarizeRandom(t *testing.T) {
211	b := new(PallocBits)
212	for i := 0; i < 1000; i++ {
213		// Randomize bitmap.
214		for i := range b {
215			b[i] = rand.Uint64()
216		}
217		// Check summary against reference implementation.
218		checkPallocSum(t, b.Summarize(), SummarizeSlow(b))
219	}
220}
221
222// Ensures computing bit summaries works as expected.
223func TestPallocBitsSummarize(t *testing.T) {
224	var emptySum = PackPallocSum(PallocChunkPages, PallocChunkPages, PallocChunkPages)
225	type test struct {
226		free []BitRange // Ranges of free (zero) bits.
227		hits []PallocSum
228	}
229	tests := make(map[string]test)
230	tests["NoneFree"] = test{
231		free: []BitRange{},
232		hits: []PallocSum{
233			PackPallocSum(0, 0, 0),
234		},
235	}
236	tests["OnlyStart"] = test{
237		free: []BitRange{{0, 10}},
238		hits: []PallocSum{
239			PackPallocSum(10, 10, 0),
240		},
241	}
242	tests["OnlyEnd"] = test{
243		free: []BitRange{{PallocChunkPages - 40, 40}},
244		hits: []PallocSum{
245			PackPallocSum(0, 40, 40),
246		},
247	}
248	tests["StartAndEnd"] = test{
249		free: []BitRange{{0, 11}, {PallocChunkPages - 23, 23}},
250		hits: []PallocSum{
251			PackPallocSum(11, 23, 23),
252		},
253	}
254	tests["StartMaxEnd"] = test{
255		free: []BitRange{{0, 4}, {50, 100}, {PallocChunkPages - 4, 4}},
256		hits: []PallocSum{
257			PackPallocSum(4, 100, 4),
258		},
259	}
260	tests["OnlyMax"] = test{
261		free: []BitRange{{1, 20}, {35, 241}, {PallocChunkPages - 50, 30}},
262		hits: []PallocSum{
263			PackPallocSum(0, 241, 0),
264		},
265	}
266	tests["MultiMax"] = test{
267		free: []BitRange{{35, 2}, {40, 5}, {100, 5}},
268		hits: []PallocSum{
269			PackPallocSum(0, 5, 0),
270		},
271	}
272	tests["One"] = test{
273		free: []BitRange{{2, 1}},
274		hits: []PallocSum{
275			PackPallocSum(0, 1, 0),
276		},
277	}
278	tests["AllFree"] = test{
279		free: []BitRange{{0, PallocChunkPages}},
280		hits: []PallocSum{
281			emptySum,
282		},
283	}
284	for name, v := range tests {
285		v := v
286		t.Run(name, func(t *testing.T) {
287			b := makePallocBits(v.free)
288			// In the PallocBits we create 1's represent free spots, but in our actual
289			// PallocBits 1 means not free, so invert.
290			invertPallocBits(b)
291			for _, h := range v.hits {
292				checkPallocSum(t, b.Summarize(), h)
293			}
294		})
295	}
296}
297
298// Benchmarks how quickly we can summarize a PallocBits.
299func BenchmarkPallocBitsSummarize(b *testing.B) {
300	buf0 := new(PallocBits)
301	buf1 := new(PallocBits)
302	for i := 0; i < len(buf1); i++ {
303		buf1[i] = ^uint64(0)
304	}
305	bufa := new(PallocBits)
306	for i := 0; i < len(bufa); i++ {
307		bufa[i] = 0xaa
308	}
309	for _, buf := range []*PallocBits{buf0, buf1, bufa} {
310		b.Run(fmt.Sprintf("Unpacked%02X", buf[0]), func(b *testing.B) {
311			for i := 0; i < b.N; i++ {
312				buf.Summarize()
313			}
314		})
315	}
316}
317
318// Ensures page allocation works.
319func TestPallocBitsAlloc(t *testing.T) {
320	tests := map[string]struct {
321		before []BitRange
322		after  []BitRange
323		npages uintptr
324		hits   []uint
325	}{
326		"AllFree1": {
327			npages: 1,
328			hits:   []uint{0, 1, 2, 3, 4, 5},
329			after:  []BitRange{{0, 6}},
330		},
331		"AllFree2": {
332			npages: 2,
333			hits:   []uint{0, 2, 4, 6, 8, 10},
334			after:  []BitRange{{0, 12}},
335		},
336		"AllFree5": {
337			npages: 5,
338			hits:   []uint{0, 5, 10, 15, 20},
339			after:  []BitRange{{0, 25}},
340		},
341		"AllFree64": {
342			npages: 64,
343			hits:   []uint{0, 64, 128},
344			after:  []BitRange{{0, 192}},
345		},
346		"AllFree65": {
347			npages: 65,
348			hits:   []uint{0, 65, 130},
349			after:  []BitRange{{0, 195}},
350		},
351		"SomeFree64": {
352			before: []BitRange{{0, 32}, {64, 32}, {100, PallocChunkPages - 100}},
353			npages: 64,
354			hits:   []uint{^uint(0)},
355			after:  []BitRange{{0, 32}, {64, 32}, {100, PallocChunkPages - 100}},
356		},
357		"NoneFree1": {
358			before: []BitRange{{0, PallocChunkPages}},
359			npages: 1,
360			hits:   []uint{^uint(0), ^uint(0)},
361			after:  []BitRange{{0, PallocChunkPages}},
362		},
363		"NoneFree2": {
364			before: []BitRange{{0, PallocChunkPages}},
365			npages: 2,
366			hits:   []uint{^uint(0), ^uint(0)},
367			after:  []BitRange{{0, PallocChunkPages}},
368		},
369		"NoneFree5": {
370			before: []BitRange{{0, PallocChunkPages}},
371			npages: 5,
372			hits:   []uint{^uint(0), ^uint(0)},
373			after:  []BitRange{{0, PallocChunkPages}},
374		},
375		"NoneFree65": {
376			before: []BitRange{{0, PallocChunkPages}},
377			npages: 65,
378			hits:   []uint{^uint(0), ^uint(0)},
379			after:  []BitRange{{0, PallocChunkPages}},
380		},
381		"ExactFit1": {
382			before: []BitRange{{0, PallocChunkPages/2 - 3}, {PallocChunkPages/2 - 2, PallocChunkPages/2 + 2}},
383			npages: 1,
384			hits:   []uint{PallocChunkPages/2 - 3, ^uint(0)},
385			after:  []BitRange{{0, PallocChunkPages}},
386		},
387		"ExactFit2": {
388			before: []BitRange{{0, PallocChunkPages/2 - 3}, {PallocChunkPages/2 - 1, PallocChunkPages/2 + 1}},
389			npages: 2,
390			hits:   []uint{PallocChunkPages/2 - 3, ^uint(0)},
391			after:  []BitRange{{0, PallocChunkPages}},
392		},
393		"ExactFit5": {
394			before: []BitRange{{0, PallocChunkPages/2 - 3}, {PallocChunkPages/2 + 2, PallocChunkPages/2 - 2}},
395			npages: 5,
396			hits:   []uint{PallocChunkPages/2 - 3, ^uint(0)},
397			after:  []BitRange{{0, PallocChunkPages}},
398		},
399		"ExactFit65": {
400			before: []BitRange{{0, PallocChunkPages/2 - 31}, {PallocChunkPages/2 + 34, PallocChunkPages/2 - 34}},
401			npages: 65,
402			hits:   []uint{PallocChunkPages/2 - 31, ^uint(0)},
403			after:  []BitRange{{0, PallocChunkPages}},
404		},
405		"SomeFree161": {
406			before: []BitRange{{0, 185}, {331, 1}},
407			npages: 161,
408			hits:   []uint{332},
409			after:  []BitRange{{0, 185}, {331, 162}},
410		},
411	}
412	for name, v := range tests {
413		v := v
414		t.Run(name, func(t *testing.T) {
415			b := makePallocBits(v.before)
416			for iter, i := range v.hits {
417				a, _ := b.Find(v.npages, 0)
418				if i != a {
419					t.Fatalf("find #%d picked wrong index: want %d, got %d", iter+1, i, a)
420				}
421				if i != ^uint(0) {
422					b.AllocRange(a, uint(v.npages))
423				}
424			}
425			want := makePallocBits(v.after)
426			checkPallocBits(t, b, want)
427		})
428	}
429}
430
431// Ensures page freeing works.
432func TestPallocBitsFree(t *testing.T) {
433	tests := map[string]struct {
434		beforeInv []BitRange
435		afterInv  []BitRange
436		frees     []uint
437		npages    uintptr
438	}{
439		"SomeFree": {
440			npages:    1,
441			beforeInv: []BitRange{{0, 32}, {64, 32}, {100, 1}},
442			frees:     []uint{32},
443			afterInv:  []BitRange{{0, 33}, {64, 32}, {100, 1}},
444		},
445		"NoneFree1": {
446			npages:   1,
447			frees:    []uint{0, 1, 2, 3, 4, 5},
448			afterInv: []BitRange{{0, 6}},
449		},
450		"NoneFree2": {
451			npages:   2,
452			frees:    []uint{0, 2, 4, 6, 8, 10},
453			afterInv: []BitRange{{0, 12}},
454		},
455		"NoneFree5": {
456			npages:   5,
457			frees:    []uint{0, 5, 10, 15, 20},
458			afterInv: []BitRange{{0, 25}},
459		},
460		"NoneFree64": {
461			npages:   64,
462			frees:    []uint{0, 64, 128},
463			afterInv: []BitRange{{0, 192}},
464		},
465		"NoneFree65": {
466			npages:   65,
467			frees:    []uint{0, 65, 130},
468			afterInv: []BitRange{{0, 195}},
469		},
470	}
471	for name, v := range tests {
472		v := v
473		t.Run(name, func(t *testing.T) {
474			b := makePallocBits(v.beforeInv)
475			invertPallocBits(b)
476			for _, i := range v.frees {
477				b.Free(i, uint(v.npages))
478			}
479			want := makePallocBits(v.afterInv)
480			invertPallocBits(want)
481			checkPallocBits(t, b, want)
482		})
483	}
484}
485
486func TestFindBitRange64(t *testing.T) {
487	check := func(x uint64, n uint, result uint) {
488		i := FindBitRange64(x, n)
489		if result == ^uint(0) && i < 64 {
490			t.Errorf("case (%016x, %d): got %d, want failure", x, n, i)
491		} else if result != ^uint(0) && i != result {
492			t.Errorf("case (%016x, %d): got %d, want %d", x, n, i, result)
493		}
494	}
495	for i := uint(0); i <= 64; i++ {
496		check(^uint64(0), i, 0)
497	}
498	check(0, 0, 0)
499	for i := uint(1); i <= 64; i++ {
500		check(0, i, ^uint(0))
501	}
502	check(0x8000000000000000, 1, 63)
503	check(0xc000010001010000, 2, 62)
504	check(0xc000010001030000, 2, 16)
505	check(0xe000030001030000, 3, 61)
506	check(0xe000030001070000, 3, 16)
507	check(0xffff03ff01070000, 16, 48)
508	check(0xffff03ff0107ffff, 16, 0)
509	check(0x0fff03ff01079fff, 16, ^uint(0))
510}
511