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