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.TB, 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	patterns := []uint64{
301		0,
302		^uint64(0),
303		0xaa,
304		0xaaaaaaaaaaaaaaaa,
305		0x80000000aaaaaaaa,
306		0xaaaaaaaa00000001,
307		0xbbbbbbbbbbbbbbbb,
308		0x80000000bbbbbbbb,
309		0xbbbbbbbb00000001,
310		0xcccccccccccccccc,
311		0x4444444444444444,
312		0x4040404040404040,
313		0x4000400040004000,
314		0x1000404044ccaaff,
315	}
316	for _, p := range patterns {
317		buf := new(PallocBits)
318		for i := 0; i < len(buf); i++ {
319			buf[i] = p
320		}
321		b.Run(fmt.Sprintf("Unpacked%02X", p), func(b *testing.B) {
322			checkPallocSum(b, buf.Summarize(), SummarizeSlow(buf))
323			for i := 0; i < b.N; i++ {
324				buf.Summarize()
325			}
326		})
327	}
328}
329
330// Ensures page allocation works.
331func TestPallocBitsAlloc(t *testing.T) {
332	tests := map[string]struct {
333		before []BitRange
334		after  []BitRange
335		npages uintptr
336		hits   []uint
337	}{
338		"AllFree1": {
339			npages: 1,
340			hits:   []uint{0, 1, 2, 3, 4, 5},
341			after:  []BitRange{{0, 6}},
342		},
343		"AllFree2": {
344			npages: 2,
345			hits:   []uint{0, 2, 4, 6, 8, 10},
346			after:  []BitRange{{0, 12}},
347		},
348		"AllFree5": {
349			npages: 5,
350			hits:   []uint{0, 5, 10, 15, 20},
351			after:  []BitRange{{0, 25}},
352		},
353		"AllFree64": {
354			npages: 64,
355			hits:   []uint{0, 64, 128},
356			after:  []BitRange{{0, 192}},
357		},
358		"AllFree65": {
359			npages: 65,
360			hits:   []uint{0, 65, 130},
361			after:  []BitRange{{0, 195}},
362		},
363		"SomeFree64": {
364			before: []BitRange{{0, 32}, {64, 32}, {100, PallocChunkPages - 100}},
365			npages: 64,
366			hits:   []uint{^uint(0)},
367			after:  []BitRange{{0, 32}, {64, 32}, {100, PallocChunkPages - 100}},
368		},
369		"NoneFree1": {
370			before: []BitRange{{0, PallocChunkPages}},
371			npages: 1,
372			hits:   []uint{^uint(0), ^uint(0)},
373			after:  []BitRange{{0, PallocChunkPages}},
374		},
375		"NoneFree2": {
376			before: []BitRange{{0, PallocChunkPages}},
377			npages: 2,
378			hits:   []uint{^uint(0), ^uint(0)},
379			after:  []BitRange{{0, PallocChunkPages}},
380		},
381		"NoneFree5": {
382			before: []BitRange{{0, PallocChunkPages}},
383			npages: 5,
384			hits:   []uint{^uint(0), ^uint(0)},
385			after:  []BitRange{{0, PallocChunkPages}},
386		},
387		"NoneFree65": {
388			before: []BitRange{{0, PallocChunkPages}},
389			npages: 65,
390			hits:   []uint{^uint(0), ^uint(0)},
391			after:  []BitRange{{0, PallocChunkPages}},
392		},
393		"ExactFit1": {
394			before: []BitRange{{0, PallocChunkPages/2 - 3}, {PallocChunkPages/2 - 2, PallocChunkPages/2 + 2}},
395			npages: 1,
396			hits:   []uint{PallocChunkPages/2 - 3, ^uint(0)},
397			after:  []BitRange{{0, PallocChunkPages}},
398		},
399		"ExactFit2": {
400			before: []BitRange{{0, PallocChunkPages/2 - 3}, {PallocChunkPages/2 - 1, PallocChunkPages/2 + 1}},
401			npages: 2,
402			hits:   []uint{PallocChunkPages/2 - 3, ^uint(0)},
403			after:  []BitRange{{0, PallocChunkPages}},
404		},
405		"ExactFit5": {
406			before: []BitRange{{0, PallocChunkPages/2 - 3}, {PallocChunkPages/2 + 2, PallocChunkPages/2 - 2}},
407			npages: 5,
408			hits:   []uint{PallocChunkPages/2 - 3, ^uint(0)},
409			after:  []BitRange{{0, PallocChunkPages}},
410		},
411		"ExactFit65": {
412			before: []BitRange{{0, PallocChunkPages/2 - 31}, {PallocChunkPages/2 + 34, PallocChunkPages/2 - 34}},
413			npages: 65,
414			hits:   []uint{PallocChunkPages/2 - 31, ^uint(0)},
415			after:  []BitRange{{0, PallocChunkPages}},
416		},
417		"SomeFree161": {
418			before: []BitRange{{0, 185}, {331, 1}},
419			npages: 161,
420			hits:   []uint{332},
421			after:  []BitRange{{0, 185}, {331, 162}},
422		},
423	}
424	for name, v := range tests {
425		v := v
426		t.Run(name, func(t *testing.T) {
427			b := makePallocBits(v.before)
428			for iter, i := range v.hits {
429				a, _ := b.Find(v.npages, 0)
430				if i != a {
431					t.Fatalf("find #%d picked wrong index: want %d, got %d", iter+1, i, a)
432				}
433				if i != ^uint(0) {
434					b.AllocRange(a, uint(v.npages))
435				}
436			}
437			want := makePallocBits(v.after)
438			checkPallocBits(t, b, want)
439		})
440	}
441}
442
443// Ensures page freeing works.
444func TestPallocBitsFree(t *testing.T) {
445	tests := map[string]struct {
446		beforeInv []BitRange
447		afterInv  []BitRange
448		frees     []uint
449		npages    uintptr
450	}{
451		"SomeFree": {
452			npages:    1,
453			beforeInv: []BitRange{{0, 32}, {64, 32}, {100, 1}},
454			frees:     []uint{32},
455			afterInv:  []BitRange{{0, 33}, {64, 32}, {100, 1}},
456		},
457		"NoneFree1": {
458			npages:   1,
459			frees:    []uint{0, 1, 2, 3, 4, 5},
460			afterInv: []BitRange{{0, 6}},
461		},
462		"NoneFree2": {
463			npages:   2,
464			frees:    []uint{0, 2, 4, 6, 8, 10},
465			afterInv: []BitRange{{0, 12}},
466		},
467		"NoneFree5": {
468			npages:   5,
469			frees:    []uint{0, 5, 10, 15, 20},
470			afterInv: []BitRange{{0, 25}},
471		},
472		"NoneFree64": {
473			npages:   64,
474			frees:    []uint{0, 64, 128},
475			afterInv: []BitRange{{0, 192}},
476		},
477		"NoneFree65": {
478			npages:   65,
479			frees:    []uint{0, 65, 130},
480			afterInv: []BitRange{{0, 195}},
481		},
482	}
483	for name, v := range tests {
484		v := v
485		t.Run(name, func(t *testing.T) {
486			b := makePallocBits(v.beforeInv)
487			invertPallocBits(b)
488			for _, i := range v.frees {
489				b.Free(i, uint(v.npages))
490			}
491			want := makePallocBits(v.afterInv)
492			invertPallocBits(want)
493			checkPallocBits(t, b, want)
494		})
495	}
496}
497
498func TestFindBitRange64(t *testing.T) {
499	check := func(x uint64, n uint, result uint) {
500		i := FindBitRange64(x, n)
501		if result == ^uint(0) && i < 64 {
502			t.Errorf("case (%016x, %d): got %d, want failure", x, n, i)
503		} else if result != ^uint(0) && i != result {
504			t.Errorf("case (%016x, %d): got %d, want %d", x, n, i, result)
505		}
506	}
507	for i := uint(1); i <= 64; i++ {
508		check(^uint64(0), i, 0)
509	}
510	for i := uint(1); i <= 64; i++ {
511		check(0, i, ^uint(0))
512	}
513	check(0x8000000000000000, 1, 63)
514	check(0xc000010001010000, 2, 62)
515	check(0xc000010001030000, 2, 16)
516	check(0xe000030001030000, 3, 61)
517	check(0xe000030001070000, 3, 16)
518	check(0xffff03ff01070000, 16, 48)
519	check(0xffff03ff0107ffff, 16, 0)
520	check(0x0fff03ff01079fff, 16, ^uint(0))
521}
522
523func BenchmarkFindBitRange64(b *testing.B) {
524	patterns := []uint64{
525		0,
526		^uint64(0),
527		0xaa,
528		0xaaaaaaaaaaaaaaaa,
529		0x80000000aaaaaaaa,
530		0xaaaaaaaa00000001,
531		0xbbbbbbbbbbbbbbbb,
532		0x80000000bbbbbbbb,
533		0xbbbbbbbb00000001,
534		0xcccccccccccccccc,
535		0x4444444444444444,
536		0x4040404040404040,
537		0x4000400040004000,
538	}
539	sizes := []uint{
540		2, 8, 32,
541	}
542	for _, pattern := range patterns {
543		for _, size := range sizes {
544			b.Run(fmt.Sprintf("Pattern%02XSize%d", pattern, size), func(b *testing.B) {
545				for i := 0; i < b.N; i++ {
546					FindBitRange64(pattern, size)
547				}
548			})
549		}
550	}
551}
552