libgo/go/runtime/mpallocbits_test.go

   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
   5 package runtime_test
   6
   7 import (
   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.
  16 func 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.
  32 func 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.
  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)
  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.
  96 func 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.
 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())
 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
 116 func 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.
 210 func 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.
 223 func 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.
 299 func 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.
 331 func 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.
 444 func 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
 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)
 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
 523 func 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 }