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.
14 // Ensures that got and want are the same, and if not, reports
15 // detailed diff information.
16 func checkPallocBits(t
*testing
.T
, got
, want
*PallocBits
) bool {
17 d
:= DiffPallocBits(got
, want
)
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
))
30 // makePallocBits produces an initialized PallocBits by setting
31 // the ranges in s to 1 and the rest to zero.
32 func makePallocBits(s
[]BitRange
) *PallocBits
{
35 b
.AllocRange(v
.I
, v
.N
)
40 // Ensures that PallocBits.AllocRange works, which is a fundamental
41 // method used for testing and initialization since it's used by
43 func TestPallocBitsAllocRange(t
*testing
.T
) {
44 test
:= func(t
*testing
.T
, i
, n
uint, want
*PallocBits
) {
45 checkPallocBits(t
, makePallocBits([]BitRange
{{i
, n
}}), want
)
47 t
.Run("OneLow", func(t
*testing
.T
) {
48 want
:= new(PallocBits
)
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
)
57 t
.Run("Inner", func(t
*testing
.T
) {
58 want
:= new(PallocBits
)
62 t
.Run("Aligned", func(t
*testing
.T
) {
63 want
:= new(PallocBits
)
66 test(t
, 128, 128, want
)
68 t
.Run("Begin", func(t
*testing
.T
) {
69 want
:= new(PallocBits
)
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
)
86 t
.Run("All", func(t
*testing
.T
) {
87 want
:= new(PallocBits
)
91 test(t
, 0, PallocChunkPages
, want
)
95 // Inverts every bit in the PallocBits.
96 func invertPallocBits(b
*PallocBits
) {
102 // Ensures two packed summaries are identical, and reports a detailed description
103 // of the difference if they're not.
104 func 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())
108 if got
.Max() != want
.Max() {
109 t
.Errorf("inconsistent max: got %d, want %d", got
.Max(), want
.Max())
111 if got
.End() != want
.End() {
112 t
.Errorf("inconsistent end: got %d, want %d", got
.End(), want
.End())
116 func TestMallocBitsPopcntRange(t
*testing
.T
) {
118 i
, n
uint // bit range to popcnt over.
119 want
uint // expected popcnt result on that range.
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.
130 {PallocChunkPages
/4 + 1, PallocChunkPages
/ 2, 0},
131 {0, PallocChunkPages
, 0},
135 init
: []BitRange
{{0, PallocChunkPages
}},
140 {PallocChunkPages
/4 + 1, PallocChunkPages
/ 2, PallocChunkPages
/ 2},
141 {0, PallocChunkPages
, PallocChunkPages
},
145 init
: []BitRange
{{PallocChunkPages
/ 2, PallocChunkPages
/ 2}},
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},
161 init
: []BitRange
{{0, 111}},
172 {PallocChunkPages
/ 2, PallocChunkPages
/ 2, 0},
173 {0, PallocChunkPages
, 111},
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},
191 {0, PallocChunkPages
, 75},
195 for name
, v
:= range tests
{
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
)
208 // Ensures computing bit summaries works as expected by generating random
209 // bitmaps and checking against a reference implementation.
210 func TestPallocBitsSummarizeRandom(t
*testing
.T
) {
212 for i
:= 0; i
< 1000; i
++ {
217 // Check summary against reference implementation.
218 checkPallocSum(t
, b
.Summarize(), SummarizeSlow(b
))
222 // Ensures computing bit summaries works as expected.
223 func TestPallocBitsSummarize(t
*testing
.T
) {
224 var emptySum
= PackPallocSum(PallocChunkPages
, PallocChunkPages
, PallocChunkPages
)
226 free
[]BitRange
// Ranges of free (zero) bits.
229 tests
:= make(map[string]test
)
230 tests
["NoneFree"] = test
{
233 PackPallocSum(0, 0, 0),
236 tests
["OnlyStart"] = test
{
237 free
: []BitRange
{{0, 10}},
239 PackPallocSum(10, 10, 0),
242 tests
["OnlyEnd"] = test
{
243 free
: []BitRange
{{PallocChunkPages
- 40, 40}},
245 PackPallocSum(0, 40, 40),
248 tests
["StartAndEnd"] = test
{
249 free
: []BitRange
{{0, 11}, {PallocChunkPages
- 23, 23}},
251 PackPallocSum(11, 23, 23),
254 tests
["StartMaxEnd"] = test
{
255 free
: []BitRange
{{0, 4}, {50, 100}, {PallocChunkPages
- 4, 4}},
257 PackPallocSum(4, 100, 4),
260 tests
["OnlyMax"] = test
{
261 free
: []BitRange
{{1, 20}, {35, 241}, {PallocChunkPages
- 50, 30}},
263 PackPallocSum(0, 241, 0),
266 tests
["MultiMax"] = test
{
267 free
: []BitRange
{{35, 2}, {40, 5}, {100, 5}},
269 PackPallocSum(0, 5, 0),
273 free
: []BitRange
{{2, 1}},
275 PackPallocSum(0, 1, 0),
278 tests
["AllFree"] = test
{
279 free
: []BitRange
{{0, PallocChunkPages
}},
284 for name
, v
:= range tests
{
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.
291 for _
, h
:= range v
.hits
{
292 checkPallocSum(t
, b
.Summarize(), h
)
298 // Benchmarks how quickly we can summarize a PallocBits.
299 func BenchmarkPallocBitsSummarize(b
*testing
.B
) {
300 patterns
:= []uint64{
316 for _
, p
:= range patterns
{
317 buf
:= new(PallocBits
)
318 for i
:= 0; i
< len(buf
); i
++ {
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
++ {
330 // Ensures page allocation works.
331 func TestPallocBitsAlloc(t
*testing
.T
) {
332 tests
:= map[string]struct {
340 hits
: []uint{0, 1, 2, 3, 4, 5},
341 after
: []BitRange
{{0, 6}},
345 hits
: []uint{0, 2, 4, 6, 8, 10},
346 after
: []BitRange
{{0, 12}},
350 hits
: []uint{0, 5, 10, 15, 20},
351 after
: []BitRange
{{0, 25}},
355 hits
: []uint{0, 64, 128},
356 after
: []BitRange
{{0, 192}},
360 hits
: []uint{0, 65, 130},
361 after
: []BitRange
{{0, 195}},
364 before
: []BitRange
{{0, 32}, {64, 32}, {100, PallocChunkPages
- 100}},
366 hits
: []uint{^uint(0)},
367 after
: []BitRange
{{0, 32}, {64, 32}, {100, PallocChunkPages
- 100}},
370 before
: []BitRange
{{0, PallocChunkPages
}},
372 hits
: []uint{^uint(0), ^uint(0)},
373 after
: []BitRange
{{0, PallocChunkPages
}},
376 before
: []BitRange
{{0, PallocChunkPages
}},
378 hits
: []uint{^uint(0), ^uint(0)},
379 after
: []BitRange
{{0, PallocChunkPages
}},
382 before
: []BitRange
{{0, PallocChunkPages
}},
384 hits
: []uint{^uint(0), ^uint(0)},
385 after
: []BitRange
{{0, PallocChunkPages
}},
388 before
: []BitRange
{{0, PallocChunkPages
}},
390 hits
: []uint{^uint(0), ^uint(0)},
391 after
: []BitRange
{{0, PallocChunkPages
}},
394 before
: []BitRange
{{0, PallocChunkPages
/2 - 3}, {PallocChunkPages
/2 - 2, PallocChunkPages
/2 + 2}},
396 hits
: []uint{PallocChunkPages
/2 - 3, ^uint(0)},
397 after
: []BitRange
{{0, PallocChunkPages
}},
400 before
: []BitRange
{{0, PallocChunkPages
/2 - 3}, {PallocChunkPages
/2 - 1, PallocChunkPages
/2 + 1}},
402 hits
: []uint{PallocChunkPages
/2 - 3, ^uint(0)},
403 after
: []BitRange
{{0, PallocChunkPages
}},
406 before
: []BitRange
{{0, PallocChunkPages
/2 - 3}, {PallocChunkPages
/2 + 2, PallocChunkPages
/2 - 2}},
408 hits
: []uint{PallocChunkPages
/2 - 3, ^uint(0)},
409 after
: []BitRange
{{0, PallocChunkPages
}},
412 before
: []BitRange
{{0, PallocChunkPages
/2 - 31}, {PallocChunkPages
/2 + 34, PallocChunkPages
/2 - 34}},
414 hits
: []uint{PallocChunkPages
/2 - 31, ^uint(0)},
415 after
: []BitRange
{{0, PallocChunkPages
}},
418 before
: []BitRange
{{0, 185}, {331, 1}},
421 after
: []BitRange
{{0, 185}, {331, 162}},
424 for name
, v
:= range tests
{
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)
431 t
.Fatalf("find #%d picked wrong index: want %d, got %d", iter
+1, i
, a
)
434 b
.AllocRange(a
, uint(v
.npages
))
437 want
:= makePallocBits(v
.after
)
438 checkPallocBits(t
, b
, want
)
443 // Ensures page freeing works.
444 func TestPallocBitsFree(t
*testing
.T
) {
445 tests
:= map[string]struct {
453 beforeInv
: []BitRange
{{0, 32}, {64, 32}, {100, 1}},
455 afterInv
: []BitRange
{{0, 33}, {64, 32}, {100, 1}},
459 frees
: []uint{0, 1, 2, 3, 4, 5},
460 afterInv
: []BitRange
{{0, 6}},
464 frees
: []uint{0, 2, 4, 6, 8, 10},
465 afterInv
: []BitRange
{{0, 12}},
469 frees
: []uint{0, 5, 10, 15, 20},
470 afterInv
: []BitRange
{{0, 25}},
474 frees
: []uint{0, 64, 128},
475 afterInv
: []BitRange
{{0, 192}},
479 frees
: []uint{0, 65, 130},
480 afterInv
: []BitRange
{{0, 195}},
483 for name
, v
:= range tests
{
485 t
.Run(name
, func(t
*testing
.T
) {
486 b
:= makePallocBits(v
.beforeInv
)
488 for _
, i
:= range v
.frees
{
489 b
.Free(i
, uint(v
.npages
))
491 want
:= makePallocBits(v
.afterInv
)
492 invertPallocBits(want
)
493 checkPallocBits(t
, b
, want
)
498 func 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
)
507 for i
:= uint(1); i
<= 64; i
++ {
508 check(^uint64(0), i
, 0)
510 for i
:= uint(1); i
<= 64; i
++ {
511 check(0, i
, ^uint(0))
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))
523 func BenchmarkFindBitRange64(b
*testing
.B
) {
524 patterns
:= []uint64{
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
)