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 . "runtime" 10 "testing" 11) 12 13func checkPageAlloc(t *testing.T, want, got *PageAlloc) { 14 // Ensure start and end are correct. 15 wantStart, wantEnd := want.Bounds() 16 gotStart, gotEnd := got.Bounds() 17 if gotStart != wantStart { 18 t.Fatalf("start values not equal: got %d, want %d", gotStart, wantStart) 19 } 20 if gotEnd != wantEnd { 21 t.Fatalf("end values not equal: got %d, want %d", gotEnd, wantEnd) 22 } 23 24 for i := gotStart; i < gotEnd; i++ { 25 // Check the bitmaps. Note that we may have nil data. 26 gb, wb := got.PallocData(i), want.PallocData(i) 27 if gb == nil && wb == nil { 28 continue 29 } 30 if (gb == nil && wb != nil) || (gb != nil && wb == nil) { 31 t.Errorf("chunk %d nilness mismatch", i) 32 } 33 if !checkPallocBits(t, gb.PallocBits(), wb.PallocBits()) { 34 t.Logf("in chunk %d (mallocBits)", i) 35 } 36 if !checkPallocBits(t, gb.Scavenged(), wb.Scavenged()) { 37 t.Logf("in chunk %d (scavenged)", i) 38 } 39 } 40 // TODO(mknyszek): Verify summaries too? 41} 42 43func TestPageAllocGrow(t *testing.T) { 44 if GOOS == "openbsd" && testing.Short() { 45 t.Skip("skipping because virtual memory is limited; see #36210") 46 } 47 type test struct { 48 chunks []ChunkIdx 49 inUse []AddrRange 50 } 51 tests := map[string]test{ 52 "One": { 53 chunks: []ChunkIdx{ 54 BaseChunkIdx, 55 }, 56 inUse: []AddrRange{ 57 {PageBase(BaseChunkIdx, 0), PageBase(BaseChunkIdx+1, 0)}, 58 }, 59 }, 60 "Contiguous2": { 61 chunks: []ChunkIdx{ 62 BaseChunkIdx, 63 BaseChunkIdx + 1, 64 }, 65 inUse: []AddrRange{ 66 {PageBase(BaseChunkIdx, 0), PageBase(BaseChunkIdx+2, 0)}, 67 }, 68 }, 69 "Contiguous5": { 70 chunks: []ChunkIdx{ 71 BaseChunkIdx, 72 BaseChunkIdx + 1, 73 BaseChunkIdx + 2, 74 BaseChunkIdx + 3, 75 BaseChunkIdx + 4, 76 }, 77 inUse: []AddrRange{ 78 {PageBase(BaseChunkIdx, 0), PageBase(BaseChunkIdx+5, 0)}, 79 }, 80 }, 81 "Discontiguous": { 82 chunks: []ChunkIdx{ 83 BaseChunkIdx, 84 BaseChunkIdx + 2, 85 BaseChunkIdx + 4, 86 }, 87 inUse: []AddrRange{ 88 {PageBase(BaseChunkIdx, 0), PageBase(BaseChunkIdx+1, 0)}, 89 {PageBase(BaseChunkIdx+2, 0), PageBase(BaseChunkIdx+3, 0)}, 90 {PageBase(BaseChunkIdx+4, 0), PageBase(BaseChunkIdx+5, 0)}, 91 }, 92 }, 93 "Mixed": { 94 chunks: []ChunkIdx{ 95 BaseChunkIdx, 96 BaseChunkIdx + 1, 97 BaseChunkIdx + 2, 98 BaseChunkIdx + 4, 99 }, 100 inUse: []AddrRange{ 101 {PageBase(BaseChunkIdx, 0), PageBase(BaseChunkIdx+3, 0)}, 102 {PageBase(BaseChunkIdx+4, 0), PageBase(BaseChunkIdx+5, 0)}, 103 }, 104 }, 105 "WildlyDiscontiguous": { 106 chunks: []ChunkIdx{ 107 BaseChunkIdx, 108 BaseChunkIdx + 1, 109 BaseChunkIdx + 0x10, 110 BaseChunkIdx + 0x21, 111 }, 112 inUse: []AddrRange{ 113 {PageBase(BaseChunkIdx, 0), PageBase(BaseChunkIdx+2, 0)}, 114 {PageBase(BaseChunkIdx+0x10, 0), PageBase(BaseChunkIdx+0x11, 0)}, 115 {PageBase(BaseChunkIdx+0x21, 0), PageBase(BaseChunkIdx+0x22, 0)}, 116 }, 117 }, 118 "ManyDiscontiguous": { 119 // The initial cap is 16. Test 33 ranges, to exercise the growth path (twice). 120 chunks: []ChunkIdx{ 121 BaseChunkIdx, BaseChunkIdx + 2, BaseChunkIdx + 4, BaseChunkIdx + 6, 122 BaseChunkIdx + 8, BaseChunkIdx + 10, BaseChunkIdx + 12, BaseChunkIdx + 14, 123 BaseChunkIdx + 16, BaseChunkIdx + 18, BaseChunkIdx + 20, BaseChunkIdx + 22, 124 BaseChunkIdx + 24, BaseChunkIdx + 26, BaseChunkIdx + 28, BaseChunkIdx + 30, 125 BaseChunkIdx + 32, BaseChunkIdx + 34, BaseChunkIdx + 36, BaseChunkIdx + 38, 126 BaseChunkIdx + 40, BaseChunkIdx + 42, BaseChunkIdx + 44, BaseChunkIdx + 46, 127 BaseChunkIdx + 48, BaseChunkIdx + 50, BaseChunkIdx + 52, BaseChunkIdx + 54, 128 BaseChunkIdx + 56, BaseChunkIdx + 58, BaseChunkIdx + 60, BaseChunkIdx + 62, 129 BaseChunkIdx + 64, 130 }, 131 inUse: []AddrRange{ 132 {PageBase(BaseChunkIdx, 0), PageBase(BaseChunkIdx+1, 0)}, 133 {PageBase(BaseChunkIdx+2, 0), PageBase(BaseChunkIdx+3, 0)}, 134 {PageBase(BaseChunkIdx+4, 0), PageBase(BaseChunkIdx+5, 0)}, 135 {PageBase(BaseChunkIdx+6, 0), PageBase(BaseChunkIdx+7, 0)}, 136 {PageBase(BaseChunkIdx+8, 0), PageBase(BaseChunkIdx+9, 0)}, 137 {PageBase(BaseChunkIdx+10, 0), PageBase(BaseChunkIdx+11, 0)}, 138 {PageBase(BaseChunkIdx+12, 0), PageBase(BaseChunkIdx+13, 0)}, 139 {PageBase(BaseChunkIdx+14, 0), PageBase(BaseChunkIdx+15, 0)}, 140 {PageBase(BaseChunkIdx+16, 0), PageBase(BaseChunkIdx+17, 0)}, 141 {PageBase(BaseChunkIdx+18, 0), PageBase(BaseChunkIdx+19, 0)}, 142 {PageBase(BaseChunkIdx+20, 0), PageBase(BaseChunkIdx+21, 0)}, 143 {PageBase(BaseChunkIdx+22, 0), PageBase(BaseChunkIdx+23, 0)}, 144 {PageBase(BaseChunkIdx+24, 0), PageBase(BaseChunkIdx+25, 0)}, 145 {PageBase(BaseChunkIdx+26, 0), PageBase(BaseChunkIdx+27, 0)}, 146 {PageBase(BaseChunkIdx+28, 0), PageBase(BaseChunkIdx+29, 0)}, 147 {PageBase(BaseChunkIdx+30, 0), PageBase(BaseChunkIdx+31, 0)}, 148 {PageBase(BaseChunkIdx+32, 0), PageBase(BaseChunkIdx+33, 0)}, 149 {PageBase(BaseChunkIdx+34, 0), PageBase(BaseChunkIdx+35, 0)}, 150 {PageBase(BaseChunkIdx+36, 0), PageBase(BaseChunkIdx+37, 0)}, 151 {PageBase(BaseChunkIdx+38, 0), PageBase(BaseChunkIdx+39, 0)}, 152 {PageBase(BaseChunkIdx+40, 0), PageBase(BaseChunkIdx+41, 0)}, 153 {PageBase(BaseChunkIdx+42, 0), PageBase(BaseChunkIdx+43, 0)}, 154 {PageBase(BaseChunkIdx+44, 0), PageBase(BaseChunkIdx+45, 0)}, 155 {PageBase(BaseChunkIdx+46, 0), PageBase(BaseChunkIdx+47, 0)}, 156 {PageBase(BaseChunkIdx+48, 0), PageBase(BaseChunkIdx+49, 0)}, 157 {PageBase(BaseChunkIdx+50, 0), PageBase(BaseChunkIdx+51, 0)}, 158 {PageBase(BaseChunkIdx+52, 0), PageBase(BaseChunkIdx+53, 0)}, 159 {PageBase(BaseChunkIdx+54, 0), PageBase(BaseChunkIdx+55, 0)}, 160 {PageBase(BaseChunkIdx+56, 0), PageBase(BaseChunkIdx+57, 0)}, 161 {PageBase(BaseChunkIdx+58, 0), PageBase(BaseChunkIdx+59, 0)}, 162 {PageBase(BaseChunkIdx+60, 0), PageBase(BaseChunkIdx+61, 0)}, 163 {PageBase(BaseChunkIdx+62, 0), PageBase(BaseChunkIdx+63, 0)}, 164 {PageBase(BaseChunkIdx+64, 0), PageBase(BaseChunkIdx+65, 0)}, 165 }, 166 }, 167 } 168 if PageAlloc64Bit != 0 { 169 tests["ExtremelyDiscontiguous"] = test{ 170 chunks: []ChunkIdx{ 171 BaseChunkIdx, 172 BaseChunkIdx + 0x100000, // constant translates to O(TiB) 173 }, 174 inUse: []AddrRange{ 175 {PageBase(BaseChunkIdx, 0), PageBase(BaseChunkIdx+1, 0)}, 176 {PageBase(BaseChunkIdx+0x100000, 0), PageBase(BaseChunkIdx+0x100001, 0)}, 177 }, 178 } 179 } 180 for name, v := range tests { 181 v := v 182 t.Run(name, func(t *testing.T) { 183 // By creating a new pageAlloc, we will 184 // grow it for each chunk defined in x. 185 x := make(map[ChunkIdx][]BitRange) 186 for _, c := range v.chunks { 187 x[c] = []BitRange{} 188 } 189 b := NewPageAlloc(x, nil) 190 defer FreePageAlloc(b) 191 192 got := b.InUse() 193 want := v.inUse 194 195 // Check for mismatches. 196 if len(got) != len(want) { 197 t.Fail() 198 } else { 199 for i := range want { 200 if want[i] != got[i] { 201 t.Fail() 202 break 203 } 204 } 205 } 206 if t.Failed() { 207 t.Logf("found inUse mismatch") 208 t.Logf("got:") 209 for i, r := range got { 210 t.Logf("\t#%d [0x%x, 0x%x)", i, r.Base, r.Limit) 211 } 212 t.Logf("want:") 213 for i, r := range want { 214 t.Logf("\t#%d [0x%x, 0x%x)", i, r.Base, r.Limit) 215 } 216 } 217 }) 218 } 219} 220 221func TestPageAllocAlloc(t *testing.T) { 222 if GOOS == "openbsd" && testing.Short() { 223 t.Skip("skipping because virtual memory is limited; see #36210") 224 } 225 type hit struct { 226 npages, base, scav uintptr 227 } 228 type test struct { 229 scav map[ChunkIdx][]BitRange 230 before map[ChunkIdx][]BitRange 231 after map[ChunkIdx][]BitRange 232 hits []hit 233 } 234 tests := map[string]test{ 235 "AllFree1": { 236 before: map[ChunkIdx][]BitRange{ 237 BaseChunkIdx: {}, 238 }, 239 scav: map[ChunkIdx][]BitRange{ 240 BaseChunkIdx: {{0, 1}, {2, 2}}, 241 }, 242 hits: []hit{ 243 {1, PageBase(BaseChunkIdx, 0), PageSize}, 244 {1, PageBase(BaseChunkIdx, 1), 0}, 245 {1, PageBase(BaseChunkIdx, 2), PageSize}, 246 {1, PageBase(BaseChunkIdx, 3), PageSize}, 247 {1, PageBase(BaseChunkIdx, 4), 0}, 248 }, 249 after: map[ChunkIdx][]BitRange{ 250 BaseChunkIdx: {{0, 5}}, 251 }, 252 }, 253 "ManyArena1": { 254 before: map[ChunkIdx][]BitRange{ 255 BaseChunkIdx: {{0, PallocChunkPages}}, 256 BaseChunkIdx + 1: {{0, PallocChunkPages}}, 257 BaseChunkIdx + 2: {{0, PallocChunkPages - 1}}, 258 }, 259 scav: map[ChunkIdx][]BitRange{ 260 BaseChunkIdx: {{0, PallocChunkPages}}, 261 BaseChunkIdx + 1: {{0, PallocChunkPages}}, 262 BaseChunkIdx + 2: {{0, PallocChunkPages}}, 263 }, 264 hits: []hit{ 265 {1, PageBase(BaseChunkIdx+2, PallocChunkPages-1), PageSize}, 266 }, 267 after: map[ChunkIdx][]BitRange{ 268 BaseChunkIdx: {{0, PallocChunkPages}}, 269 BaseChunkIdx + 1: {{0, PallocChunkPages}}, 270 BaseChunkIdx + 2: {{0, PallocChunkPages}}, 271 }, 272 }, 273 "NotContiguous1": { 274 before: map[ChunkIdx][]BitRange{ 275 BaseChunkIdx: {{0, PallocChunkPages}}, 276 BaseChunkIdx + 0xff: {{0, 0}}, 277 }, 278 scav: map[ChunkIdx][]BitRange{ 279 BaseChunkIdx: {{0, PallocChunkPages}}, 280 BaseChunkIdx + 0xff: {{0, PallocChunkPages}}, 281 }, 282 hits: []hit{ 283 {1, PageBase(BaseChunkIdx+0xff, 0), PageSize}, 284 }, 285 after: map[ChunkIdx][]BitRange{ 286 BaseChunkIdx: {{0, PallocChunkPages}}, 287 BaseChunkIdx + 0xff: {{0, 1}}, 288 }, 289 }, 290 "AllFree2": { 291 before: map[ChunkIdx][]BitRange{ 292 BaseChunkIdx: {}, 293 }, 294 scav: map[ChunkIdx][]BitRange{ 295 BaseChunkIdx: {{0, 3}, {7, 1}}, 296 }, 297 hits: []hit{ 298 {2, PageBase(BaseChunkIdx, 0), 2 * PageSize}, 299 {2, PageBase(BaseChunkIdx, 2), PageSize}, 300 {2, PageBase(BaseChunkIdx, 4), 0}, 301 {2, PageBase(BaseChunkIdx, 6), PageSize}, 302 {2, PageBase(BaseChunkIdx, 8), 0}, 303 }, 304 after: map[ChunkIdx][]BitRange{ 305 BaseChunkIdx: {{0, 10}}, 306 }, 307 }, 308 "Straddle2": { 309 before: map[ChunkIdx][]BitRange{ 310 BaseChunkIdx: {{0, PallocChunkPages - 1}}, 311 BaseChunkIdx + 1: {{1, PallocChunkPages - 1}}, 312 }, 313 scav: map[ChunkIdx][]BitRange{ 314 BaseChunkIdx: {{PallocChunkPages - 1, 1}}, 315 BaseChunkIdx + 1: {}, 316 }, 317 hits: []hit{ 318 {2, PageBase(BaseChunkIdx, PallocChunkPages-1), PageSize}, 319 }, 320 after: map[ChunkIdx][]BitRange{ 321 BaseChunkIdx: {{0, PallocChunkPages}}, 322 BaseChunkIdx + 1: {{0, PallocChunkPages}}, 323 }, 324 }, 325 "AllFree5": { 326 before: map[ChunkIdx][]BitRange{ 327 BaseChunkIdx: {}, 328 }, 329 scav: map[ChunkIdx][]BitRange{ 330 BaseChunkIdx: {{0, 8}, {9, 1}, {17, 5}}, 331 }, 332 hits: []hit{ 333 {5, PageBase(BaseChunkIdx, 0), 5 * PageSize}, 334 {5, PageBase(BaseChunkIdx, 5), 4 * PageSize}, 335 {5, PageBase(BaseChunkIdx, 10), 0}, 336 {5, PageBase(BaseChunkIdx, 15), 3 * PageSize}, 337 {5, PageBase(BaseChunkIdx, 20), 2 * PageSize}, 338 }, 339 after: map[ChunkIdx][]BitRange{ 340 BaseChunkIdx: {{0, 25}}, 341 }, 342 }, 343 "AllFree64": { 344 before: map[ChunkIdx][]BitRange{ 345 BaseChunkIdx: {}, 346 }, 347 scav: map[ChunkIdx][]BitRange{ 348 BaseChunkIdx: {{21, 1}, {63, 65}}, 349 }, 350 hits: []hit{ 351 {64, PageBase(BaseChunkIdx, 0), 2 * PageSize}, 352 {64, PageBase(BaseChunkIdx, 64), 64 * PageSize}, 353 {64, PageBase(BaseChunkIdx, 128), 0}, 354 }, 355 after: map[ChunkIdx][]BitRange{ 356 BaseChunkIdx: {{0, 192}}, 357 }, 358 }, 359 "AllFree65": { 360 before: map[ChunkIdx][]BitRange{ 361 BaseChunkIdx: {}, 362 }, 363 scav: map[ChunkIdx][]BitRange{ 364 BaseChunkIdx: {{129, 1}}, 365 }, 366 hits: []hit{ 367 {65, PageBase(BaseChunkIdx, 0), 0}, 368 {65, PageBase(BaseChunkIdx, 65), PageSize}, 369 {65, PageBase(BaseChunkIdx, 130), 0}, 370 }, 371 after: map[ChunkIdx][]BitRange{ 372 BaseChunkIdx: {{0, 195}}, 373 }, 374 }, 375 "ExhaustPallocChunkPages-3": { 376 before: map[ChunkIdx][]BitRange{ 377 BaseChunkIdx: {}, 378 }, 379 scav: map[ChunkIdx][]BitRange{ 380 BaseChunkIdx: {{10, 1}}, 381 }, 382 hits: []hit{ 383 {PallocChunkPages - 3, PageBase(BaseChunkIdx, 0), PageSize}, 384 {PallocChunkPages - 3, 0, 0}, 385 {1, PageBase(BaseChunkIdx, PallocChunkPages-3), 0}, 386 {2, PageBase(BaseChunkIdx, PallocChunkPages-2), 0}, 387 {1, 0, 0}, 388 {PallocChunkPages - 3, 0, 0}, 389 }, 390 after: map[ChunkIdx][]BitRange{ 391 BaseChunkIdx: {{0, PallocChunkPages}}, 392 }, 393 }, 394 "AllFreePallocChunkPages": { 395 before: map[ChunkIdx][]BitRange{ 396 BaseChunkIdx: {}, 397 }, 398 scav: map[ChunkIdx][]BitRange{ 399 BaseChunkIdx: {{0, 1}, {PallocChunkPages - 1, 1}}, 400 }, 401 hits: []hit{ 402 {PallocChunkPages, PageBase(BaseChunkIdx, 0), 2 * PageSize}, 403 {PallocChunkPages, 0, 0}, 404 {1, 0, 0}, 405 }, 406 after: map[ChunkIdx][]BitRange{ 407 BaseChunkIdx: {{0, PallocChunkPages}}, 408 }, 409 }, 410 "StraddlePallocChunkPages": { 411 before: map[ChunkIdx][]BitRange{ 412 BaseChunkIdx: {{0, PallocChunkPages / 2}}, 413 BaseChunkIdx + 1: {{PallocChunkPages / 2, PallocChunkPages / 2}}, 414 }, 415 scav: map[ChunkIdx][]BitRange{ 416 BaseChunkIdx: {}, 417 BaseChunkIdx + 1: {{3, 100}}, 418 }, 419 hits: []hit{ 420 {PallocChunkPages, PageBase(BaseChunkIdx, PallocChunkPages/2), 100 * PageSize}, 421 {PallocChunkPages, 0, 0}, 422 {1, 0, 0}, 423 }, 424 after: map[ChunkIdx][]BitRange{ 425 BaseChunkIdx: {{0, PallocChunkPages}}, 426 BaseChunkIdx + 1: {{0, PallocChunkPages}}, 427 }, 428 }, 429 "StraddlePallocChunkPages+1": { 430 before: map[ChunkIdx][]BitRange{ 431 BaseChunkIdx: {{0, PallocChunkPages / 2}}, 432 BaseChunkIdx + 1: {}, 433 }, 434 scav: map[ChunkIdx][]BitRange{ 435 BaseChunkIdx: {{0, PallocChunkPages}}, 436 BaseChunkIdx + 1: {{0, PallocChunkPages}}, 437 }, 438 hits: []hit{ 439 {PallocChunkPages + 1, PageBase(BaseChunkIdx, PallocChunkPages/2), (PallocChunkPages + 1) * PageSize}, 440 {PallocChunkPages, 0, 0}, 441 {1, PageBase(BaseChunkIdx+1, PallocChunkPages/2+1), PageSize}, 442 }, 443 after: map[ChunkIdx][]BitRange{ 444 BaseChunkIdx: {{0, PallocChunkPages}}, 445 BaseChunkIdx + 1: {{0, PallocChunkPages/2 + 2}}, 446 }, 447 }, 448 "AllFreePallocChunkPages*2": { 449 before: map[ChunkIdx][]BitRange{ 450 BaseChunkIdx: {}, 451 BaseChunkIdx + 1: {}, 452 }, 453 scav: map[ChunkIdx][]BitRange{ 454 BaseChunkIdx: {}, 455 BaseChunkIdx + 1: {}, 456 }, 457 hits: []hit{ 458 {PallocChunkPages * 2, PageBase(BaseChunkIdx, 0), 0}, 459 {PallocChunkPages * 2, 0, 0}, 460 {1, 0, 0}, 461 }, 462 after: map[ChunkIdx][]BitRange{ 463 BaseChunkIdx: {{0, PallocChunkPages}}, 464 BaseChunkIdx + 1: {{0, PallocChunkPages}}, 465 }, 466 }, 467 "NotContiguousPallocChunkPages*2": { 468 before: map[ChunkIdx][]BitRange{ 469 BaseChunkIdx: {}, 470 BaseChunkIdx + 0x40: {}, 471 BaseChunkIdx + 0x41: {}, 472 }, 473 scav: map[ChunkIdx][]BitRange{ 474 BaseChunkIdx: {{0, PallocChunkPages}}, 475 BaseChunkIdx + 0x40: {}, 476 BaseChunkIdx + 0x41: {}, 477 }, 478 hits: []hit{ 479 {PallocChunkPages * 2, PageBase(BaseChunkIdx+0x40, 0), 0}, 480 {21, PageBase(BaseChunkIdx, 0), 21 * PageSize}, 481 {1, PageBase(BaseChunkIdx, 21), PageSize}, 482 }, 483 after: map[ChunkIdx][]BitRange{ 484 BaseChunkIdx: {{0, 22}}, 485 BaseChunkIdx + 0x40: {{0, PallocChunkPages}}, 486 BaseChunkIdx + 0x41: {{0, PallocChunkPages}}, 487 }, 488 }, 489 "StraddlePallocChunkPages*2": { 490 before: map[ChunkIdx][]BitRange{ 491 BaseChunkIdx: {{0, PallocChunkPages / 2}}, 492 BaseChunkIdx + 1: {}, 493 BaseChunkIdx + 2: {{PallocChunkPages / 2, PallocChunkPages / 2}}, 494 }, 495 scav: map[ChunkIdx][]BitRange{ 496 BaseChunkIdx: {{0, 7}}, 497 BaseChunkIdx + 1: {{3, 5}, {121, 10}}, 498 BaseChunkIdx + 2: {{PallocChunkPages/2 + 12, 2}}, 499 }, 500 hits: []hit{ 501 {PallocChunkPages * 2, PageBase(BaseChunkIdx, PallocChunkPages/2), 15 * PageSize}, 502 {PallocChunkPages * 2, 0, 0}, 503 {1, 0, 0}, 504 }, 505 after: map[ChunkIdx][]BitRange{ 506 BaseChunkIdx: {{0, PallocChunkPages}}, 507 BaseChunkIdx + 1: {{0, PallocChunkPages}}, 508 BaseChunkIdx + 2: {{0, PallocChunkPages}}, 509 }, 510 }, 511 "StraddlePallocChunkPages*5/4": { 512 before: map[ChunkIdx][]BitRange{ 513 BaseChunkIdx: {{0, PallocChunkPages}}, 514 BaseChunkIdx + 1: {{0, PallocChunkPages * 3 / 4}}, 515 BaseChunkIdx + 2: {{0, PallocChunkPages * 3 / 4}}, 516 BaseChunkIdx + 3: {{0, 0}}, 517 }, 518 scav: map[ChunkIdx][]BitRange{ 519 BaseChunkIdx: {{0, PallocChunkPages}}, 520 BaseChunkIdx + 1: {{PallocChunkPages / 2, PallocChunkPages/4 + 1}}, 521 BaseChunkIdx + 2: {{PallocChunkPages / 3, 1}}, 522 BaseChunkIdx + 3: {{PallocChunkPages * 2 / 3, 1}}, 523 }, 524 hits: []hit{ 525 {PallocChunkPages * 5 / 4, PageBase(BaseChunkIdx+2, PallocChunkPages*3/4), PageSize}, 526 {PallocChunkPages * 5 / 4, 0, 0}, 527 {1, PageBase(BaseChunkIdx+1, PallocChunkPages*3/4), PageSize}, 528 }, 529 after: map[ChunkIdx][]BitRange{ 530 BaseChunkIdx: {{0, PallocChunkPages}}, 531 BaseChunkIdx + 1: {{0, PallocChunkPages*3/4 + 1}}, 532 BaseChunkIdx + 2: {{0, PallocChunkPages}}, 533 BaseChunkIdx + 3: {{0, PallocChunkPages}}, 534 }, 535 }, 536 "AllFreePallocChunkPages*7+5": { 537 before: map[ChunkIdx][]BitRange{ 538 BaseChunkIdx: {}, 539 BaseChunkIdx + 1: {}, 540 BaseChunkIdx + 2: {}, 541 BaseChunkIdx + 3: {}, 542 BaseChunkIdx + 4: {}, 543 BaseChunkIdx + 5: {}, 544 BaseChunkIdx + 6: {}, 545 BaseChunkIdx + 7: {}, 546 }, 547 scav: map[ChunkIdx][]BitRange{ 548 BaseChunkIdx: {{50, 1}}, 549 BaseChunkIdx + 1: {{31, 1}}, 550 BaseChunkIdx + 2: {{7, 1}}, 551 BaseChunkIdx + 3: {{200, 1}}, 552 BaseChunkIdx + 4: {{3, 1}}, 553 BaseChunkIdx + 5: {{51, 1}}, 554 BaseChunkIdx + 6: {{20, 1}}, 555 BaseChunkIdx + 7: {{1, 1}}, 556 }, 557 hits: []hit{ 558 {PallocChunkPages*7 + 5, PageBase(BaseChunkIdx, 0), 8 * PageSize}, 559 {PallocChunkPages*7 + 5, 0, 0}, 560 {1, PageBase(BaseChunkIdx+7, 5), 0}, 561 }, 562 after: map[ChunkIdx][]BitRange{ 563 BaseChunkIdx: {{0, PallocChunkPages}}, 564 BaseChunkIdx + 1: {{0, PallocChunkPages}}, 565 BaseChunkIdx + 2: {{0, PallocChunkPages}}, 566 BaseChunkIdx + 3: {{0, PallocChunkPages}}, 567 BaseChunkIdx + 4: {{0, PallocChunkPages}}, 568 BaseChunkIdx + 5: {{0, PallocChunkPages}}, 569 BaseChunkIdx + 6: {{0, PallocChunkPages}}, 570 BaseChunkIdx + 7: {{0, 6}}, 571 }, 572 }, 573 } 574 if PageAlloc64Bit != 0 { 575 const chunkIdxBigJump = 0x100000 // chunk index offset which translates to O(TiB) 576 577 // This test attempts to trigger a bug wherein we look at unmapped summary 578 // memory that isn't just in the case where we exhaust the heap. 579 // 580 // It achieves this by placing a chunk such that its summary will be 581 // at the very end of a physical page. It then also places another chunk 582 // much further up in the address space, such that any allocations into the 583 // first chunk do not exhaust the heap and the second chunk's summary is not in the 584 // page immediately adjacent to the first chunk's summary's page. 585 // Allocating into this first chunk to exhaustion and then into the second 586 // chunk may then trigger a check in the allocator which erroneously looks at 587 // unmapped summary memory and crashes. 588 589 // Figure out how many chunks are in a physical page, then align BaseChunkIdx 590 // to a physical page in the chunk summary array. Here we only assume that 591 // each summary array is aligned to some physical page. 592 sumsPerPhysPage := ChunkIdx(PhysPageSize / PallocSumBytes) 593 baseChunkIdx := BaseChunkIdx &^ (sumsPerPhysPage - 1) 594 tests["DiscontiguousMappedSumBoundary"] = test{ 595 before: map[ChunkIdx][]BitRange{ 596 baseChunkIdx + sumsPerPhysPage - 1: {}, 597 baseChunkIdx + chunkIdxBigJump: {}, 598 }, 599 scav: map[ChunkIdx][]BitRange{ 600 baseChunkIdx + sumsPerPhysPage - 1: {}, 601 baseChunkIdx + chunkIdxBigJump: {}, 602 }, 603 hits: []hit{ 604 {PallocChunkPages - 1, PageBase(baseChunkIdx+sumsPerPhysPage-1, 0), 0}, 605 {1, PageBase(baseChunkIdx+sumsPerPhysPage-1, PallocChunkPages-1), 0}, 606 {1, PageBase(baseChunkIdx+chunkIdxBigJump, 0), 0}, 607 {PallocChunkPages - 1, PageBase(baseChunkIdx+chunkIdxBigJump, 1), 0}, 608 {1, 0, 0}, 609 }, 610 after: map[ChunkIdx][]BitRange{ 611 baseChunkIdx + sumsPerPhysPage - 1: {{0, PallocChunkPages}}, 612 baseChunkIdx + chunkIdxBigJump: {{0, PallocChunkPages}}, 613 }, 614 } 615 } 616 for name, v := range tests { 617 v := v 618 t.Run(name, func(t *testing.T) { 619 b := NewPageAlloc(v.before, v.scav) 620 defer FreePageAlloc(b) 621 622 for iter, i := range v.hits { 623 a, s := b.Alloc(i.npages) 624 if a != i.base { 625 t.Fatalf("bad alloc #%d: want base 0x%x, got 0x%x", iter+1, i.base, a) 626 } 627 if s != i.scav { 628 t.Fatalf("bad alloc #%d: want scav %d, got %d", iter+1, i.scav, s) 629 } 630 } 631 want := NewPageAlloc(v.after, v.scav) 632 defer FreePageAlloc(want) 633 634 checkPageAlloc(t, want, b) 635 }) 636 } 637} 638 639func TestPageAllocExhaust(t *testing.T) { 640 if GOOS == "openbsd" && testing.Short() { 641 t.Skip("skipping because virtual memory is limited; see #36210") 642 } 643 for _, npages := range []uintptr{1, 2, 3, 4, 5, 8, 16, 64, 1024, 1025, 2048, 2049} { 644 npages := npages 645 t.Run(fmt.Sprintf("%d", npages), func(t *testing.T) { 646 // Construct b. 647 bDesc := make(map[ChunkIdx][]BitRange) 648 for i := ChunkIdx(0); i < 4; i++ { 649 bDesc[BaseChunkIdx+i] = []BitRange{} 650 } 651 b := NewPageAlloc(bDesc, nil) 652 defer FreePageAlloc(b) 653 654 // Allocate into b with npages until we've exhausted the heap. 655 nAlloc := (PallocChunkPages * 4) / int(npages) 656 for i := 0; i < nAlloc; i++ { 657 addr := PageBase(BaseChunkIdx, uint(i)*uint(npages)) 658 if a, _ := b.Alloc(npages); a != addr { 659 t.Fatalf("bad alloc #%d: want 0x%x, got 0x%x", i+1, addr, a) 660 } 661 } 662 663 // Check to make sure the next allocation fails. 664 if a, _ := b.Alloc(npages); a != 0 { 665 t.Fatalf("bad alloc #%d: want 0, got 0x%x", nAlloc, a) 666 } 667 668 // Construct what we want the heap to look like now. 669 allocPages := nAlloc * int(npages) 670 wantDesc := make(map[ChunkIdx][]BitRange) 671 for i := ChunkIdx(0); i < 4; i++ { 672 if allocPages >= PallocChunkPages { 673 wantDesc[BaseChunkIdx+i] = []BitRange{{0, PallocChunkPages}} 674 allocPages -= PallocChunkPages 675 } else if allocPages > 0 { 676 wantDesc[BaseChunkIdx+i] = []BitRange{{0, uint(allocPages)}} 677 allocPages = 0 678 } else { 679 wantDesc[BaseChunkIdx+i] = []BitRange{} 680 } 681 } 682 want := NewPageAlloc(wantDesc, nil) 683 defer FreePageAlloc(want) 684 685 // Check to make sure the heap b matches what we want. 686 checkPageAlloc(t, want, b) 687 }) 688 } 689} 690 691func TestPageAllocFree(t *testing.T) { 692 if GOOS == "openbsd" && testing.Short() { 693 t.Skip("skipping because virtual memory is limited; see #36210") 694 } 695 tests := map[string]struct { 696 before map[ChunkIdx][]BitRange 697 after map[ChunkIdx][]BitRange 698 npages uintptr 699 frees []uintptr 700 }{ 701 "Free1": { 702 npages: 1, 703 before: map[ChunkIdx][]BitRange{ 704 BaseChunkIdx: {{0, PallocChunkPages}}, 705 }, 706 frees: []uintptr{ 707 PageBase(BaseChunkIdx, 0), 708 PageBase(BaseChunkIdx, 1), 709 PageBase(BaseChunkIdx, 2), 710 PageBase(BaseChunkIdx, 3), 711 PageBase(BaseChunkIdx, 4), 712 }, 713 after: map[ChunkIdx][]BitRange{ 714 BaseChunkIdx: {{5, PallocChunkPages - 5}}, 715 }, 716 }, 717 "ManyArena1": { 718 npages: 1, 719 before: map[ChunkIdx][]BitRange{ 720 BaseChunkIdx: {{0, PallocChunkPages}}, 721 BaseChunkIdx + 1: {{0, PallocChunkPages}}, 722 BaseChunkIdx + 2: {{0, PallocChunkPages}}, 723 }, 724 frees: []uintptr{ 725 PageBase(BaseChunkIdx, PallocChunkPages/2), 726 PageBase(BaseChunkIdx+1, 0), 727 PageBase(BaseChunkIdx+2, PallocChunkPages-1), 728 }, 729 after: map[ChunkIdx][]BitRange{ 730 BaseChunkIdx: {{0, PallocChunkPages / 2}, {PallocChunkPages/2 + 1, PallocChunkPages/2 - 1}}, 731 BaseChunkIdx + 1: {{1, PallocChunkPages - 1}}, 732 BaseChunkIdx + 2: {{0, PallocChunkPages - 1}}, 733 }, 734 }, 735 "Free2": { 736 npages: 2, 737 before: map[ChunkIdx][]BitRange{ 738 BaseChunkIdx: {{0, PallocChunkPages}}, 739 }, 740 frees: []uintptr{ 741 PageBase(BaseChunkIdx, 0), 742 PageBase(BaseChunkIdx, 2), 743 PageBase(BaseChunkIdx, 4), 744 PageBase(BaseChunkIdx, 6), 745 PageBase(BaseChunkIdx, 8), 746 }, 747 after: map[ChunkIdx][]BitRange{ 748 BaseChunkIdx: {{10, PallocChunkPages - 10}}, 749 }, 750 }, 751 "Straddle2": { 752 npages: 2, 753 before: map[ChunkIdx][]BitRange{ 754 BaseChunkIdx: {{PallocChunkPages - 1, 1}}, 755 BaseChunkIdx + 1: {{0, 1}}, 756 }, 757 frees: []uintptr{ 758 PageBase(BaseChunkIdx, PallocChunkPages-1), 759 }, 760 after: map[ChunkIdx][]BitRange{ 761 BaseChunkIdx: {}, 762 BaseChunkIdx + 1: {}, 763 }, 764 }, 765 "Free5": { 766 npages: 5, 767 before: map[ChunkIdx][]BitRange{ 768 BaseChunkIdx: {{0, PallocChunkPages}}, 769 }, 770 frees: []uintptr{ 771 PageBase(BaseChunkIdx, 0), 772 PageBase(BaseChunkIdx, 5), 773 PageBase(BaseChunkIdx, 10), 774 PageBase(BaseChunkIdx, 15), 775 PageBase(BaseChunkIdx, 20), 776 }, 777 after: map[ChunkIdx][]BitRange{ 778 BaseChunkIdx: {{25, PallocChunkPages - 25}}, 779 }, 780 }, 781 "Free64": { 782 npages: 64, 783 before: map[ChunkIdx][]BitRange{ 784 BaseChunkIdx: {{0, PallocChunkPages}}, 785 }, 786 frees: []uintptr{ 787 PageBase(BaseChunkIdx, 0), 788 PageBase(BaseChunkIdx, 64), 789 PageBase(BaseChunkIdx, 128), 790 }, 791 after: map[ChunkIdx][]BitRange{ 792 BaseChunkIdx: {{192, PallocChunkPages - 192}}, 793 }, 794 }, 795 "Free65": { 796 npages: 65, 797 before: map[ChunkIdx][]BitRange{ 798 BaseChunkIdx: {{0, PallocChunkPages}}, 799 }, 800 frees: []uintptr{ 801 PageBase(BaseChunkIdx, 0), 802 PageBase(BaseChunkIdx, 65), 803 PageBase(BaseChunkIdx, 130), 804 }, 805 after: map[ChunkIdx][]BitRange{ 806 BaseChunkIdx: {{195, PallocChunkPages - 195}}, 807 }, 808 }, 809 "FreePallocChunkPages": { 810 npages: PallocChunkPages, 811 before: map[ChunkIdx][]BitRange{ 812 BaseChunkIdx: {{0, PallocChunkPages}}, 813 }, 814 frees: []uintptr{ 815 PageBase(BaseChunkIdx, 0), 816 }, 817 after: map[ChunkIdx][]BitRange{ 818 BaseChunkIdx: {}, 819 }, 820 }, 821 "StraddlePallocChunkPages": { 822 npages: PallocChunkPages, 823 before: map[ChunkIdx][]BitRange{ 824 BaseChunkIdx: {{PallocChunkPages / 2, PallocChunkPages / 2}}, 825 BaseChunkIdx + 1: {{0, PallocChunkPages / 2}}, 826 }, 827 frees: []uintptr{ 828 PageBase(BaseChunkIdx, PallocChunkPages/2), 829 }, 830 after: map[ChunkIdx][]BitRange{ 831 BaseChunkIdx: {}, 832 BaseChunkIdx + 1: {}, 833 }, 834 }, 835 "StraddlePallocChunkPages+1": { 836 npages: PallocChunkPages + 1, 837 before: map[ChunkIdx][]BitRange{ 838 BaseChunkIdx: {{0, PallocChunkPages}}, 839 BaseChunkIdx + 1: {{0, PallocChunkPages}}, 840 }, 841 frees: []uintptr{ 842 PageBase(BaseChunkIdx, PallocChunkPages/2), 843 }, 844 after: map[ChunkIdx][]BitRange{ 845 BaseChunkIdx: {{0, PallocChunkPages / 2}}, 846 BaseChunkIdx + 1: {{PallocChunkPages/2 + 1, PallocChunkPages/2 - 1}}, 847 }, 848 }, 849 "FreePallocChunkPages*2": { 850 npages: PallocChunkPages * 2, 851 before: map[ChunkIdx][]BitRange{ 852 BaseChunkIdx: {{0, PallocChunkPages}}, 853 BaseChunkIdx + 1: {{0, PallocChunkPages}}, 854 }, 855 frees: []uintptr{ 856 PageBase(BaseChunkIdx, 0), 857 }, 858 after: map[ChunkIdx][]BitRange{ 859 BaseChunkIdx: {}, 860 BaseChunkIdx + 1: {}, 861 }, 862 }, 863 "StraddlePallocChunkPages*2": { 864 npages: PallocChunkPages * 2, 865 before: map[ChunkIdx][]BitRange{ 866 BaseChunkIdx: {{0, PallocChunkPages}}, 867 BaseChunkIdx + 1: {{0, PallocChunkPages}}, 868 BaseChunkIdx + 2: {{0, PallocChunkPages}}, 869 }, 870 frees: []uintptr{ 871 PageBase(BaseChunkIdx, PallocChunkPages/2), 872 }, 873 after: map[ChunkIdx][]BitRange{ 874 BaseChunkIdx: {{0, PallocChunkPages / 2}}, 875 BaseChunkIdx + 1: {}, 876 BaseChunkIdx + 2: {{PallocChunkPages / 2, PallocChunkPages / 2}}, 877 }, 878 }, 879 "AllFreePallocChunkPages*7+5": { 880 npages: PallocChunkPages*7 + 5, 881 before: map[ChunkIdx][]BitRange{ 882 BaseChunkIdx: {{0, PallocChunkPages}}, 883 BaseChunkIdx + 1: {{0, PallocChunkPages}}, 884 BaseChunkIdx + 2: {{0, PallocChunkPages}}, 885 BaseChunkIdx + 3: {{0, PallocChunkPages}}, 886 BaseChunkIdx + 4: {{0, PallocChunkPages}}, 887 BaseChunkIdx + 5: {{0, PallocChunkPages}}, 888 BaseChunkIdx + 6: {{0, PallocChunkPages}}, 889 BaseChunkIdx + 7: {{0, PallocChunkPages}}, 890 }, 891 frees: []uintptr{ 892 PageBase(BaseChunkIdx, 0), 893 }, 894 after: map[ChunkIdx][]BitRange{ 895 BaseChunkIdx: {}, 896 BaseChunkIdx + 1: {}, 897 BaseChunkIdx + 2: {}, 898 BaseChunkIdx + 3: {}, 899 BaseChunkIdx + 4: {}, 900 BaseChunkIdx + 5: {}, 901 BaseChunkIdx + 6: {}, 902 BaseChunkIdx + 7: {{5, PallocChunkPages - 5}}, 903 }, 904 }, 905 } 906 for name, v := range tests { 907 v := v 908 t.Run(name, func(t *testing.T) { 909 b := NewPageAlloc(v.before, nil) 910 defer FreePageAlloc(b) 911 912 for _, addr := range v.frees { 913 b.Free(addr, v.npages) 914 } 915 want := NewPageAlloc(v.after, nil) 916 defer FreePageAlloc(want) 917 918 checkPageAlloc(t, want, b) 919 }) 920 } 921} 922 923func TestPageAllocAllocAndFree(t *testing.T) { 924 if GOOS == "openbsd" && testing.Short() { 925 t.Skip("skipping because virtual memory is limited; see #36210") 926 } 927 type hit struct { 928 alloc bool 929 npages uintptr 930 base uintptr 931 } 932 tests := map[string]struct { 933 init map[ChunkIdx][]BitRange 934 hits []hit 935 }{ 936 // TODO(mknyszek): Write more tests here. 937 "Chunks8": { 938 init: map[ChunkIdx][]BitRange{ 939 BaseChunkIdx: {}, 940 BaseChunkIdx + 1: {}, 941 BaseChunkIdx + 2: {}, 942 BaseChunkIdx + 3: {}, 943 BaseChunkIdx + 4: {}, 944 BaseChunkIdx + 5: {}, 945 BaseChunkIdx + 6: {}, 946 BaseChunkIdx + 7: {}, 947 }, 948 hits: []hit{ 949 {true, PallocChunkPages * 8, PageBase(BaseChunkIdx, 0)}, 950 {false, PallocChunkPages * 8, PageBase(BaseChunkIdx, 0)}, 951 {true, PallocChunkPages * 8, PageBase(BaseChunkIdx, 0)}, 952 {false, PallocChunkPages * 8, PageBase(BaseChunkIdx, 0)}, 953 {true, PallocChunkPages * 8, PageBase(BaseChunkIdx, 0)}, 954 {false, PallocChunkPages * 8, PageBase(BaseChunkIdx, 0)}, 955 {true, 1, PageBase(BaseChunkIdx, 0)}, 956 {false, 1, PageBase(BaseChunkIdx, 0)}, 957 {true, PallocChunkPages * 8, PageBase(BaseChunkIdx, 0)}, 958 }, 959 }, 960 } 961 for name, v := range tests { 962 v := v 963 t.Run(name, func(t *testing.T) { 964 b := NewPageAlloc(v.init, nil) 965 defer FreePageAlloc(b) 966 967 for iter, i := range v.hits { 968 if i.alloc { 969 if a, _ := b.Alloc(i.npages); a != i.base { 970 t.Fatalf("bad alloc #%d: want 0x%x, got 0x%x", iter+1, i.base, a) 971 } 972 } else { 973 b.Free(i.base, i.npages) 974 } 975 } 976 }) 977 } 978} 979