1 #include "test/jemalloc_test.h" 2 3 #include "jemalloc/internal/psset.h" 4 5 #define PAGESLAB_ADDR ((void *)(1234 * HUGEPAGE)) 6 #define PAGESLAB_AGE 5678 7 8 #define ALLOC_ARENA_IND 111 9 #define ALLOC_ESN 222 10 11 static void 12 edata_init_test(edata_t *edata) { 13 memset(edata, 0, sizeof(*edata)); 14 edata_arena_ind_set(edata, ALLOC_ARENA_IND); 15 edata_esn_set(edata, ALLOC_ESN); 16 } 17 18 static void 19 test_psset_fake_purge(hpdata_t *ps) { 20 hpdata_purge_state_t purge_state; 21 hpdata_alloc_allowed_set(ps, false); 22 hpdata_purge_begin(ps, &purge_state); 23 void *addr; 24 size_t size; 25 while (hpdata_purge_next(ps, &purge_state, &addr, &size)) { 26 } 27 hpdata_purge_end(ps, &purge_state); 28 hpdata_alloc_allowed_set(ps, true); 29 } 30 31 static void 32 test_psset_alloc_new(psset_t *psset, hpdata_t *ps, edata_t *r_edata, 33 size_t size) { 34 hpdata_assert_empty(ps); 35 36 test_psset_fake_purge(ps); 37 38 psset_insert(psset, ps); 39 psset_update_begin(psset, ps); 40 41 void *addr = hpdata_reserve_alloc(ps, size); 42 edata_init(r_edata, edata_arena_ind_get(r_edata), addr, size, 43 /* slab */ false, SC_NSIZES, /* sn */ 0, extent_state_active, 44 /* zeroed */ false, /* committed */ true, EXTENT_PAI_HPA, 45 EXTENT_NOT_HEAD); 46 edata_ps_set(r_edata, ps); 47 psset_update_end(psset, ps); 48 } 49 50 static bool 51 test_psset_alloc_reuse(psset_t *psset, edata_t *r_edata, size_t size) { 52 hpdata_t *ps = psset_pick_alloc(psset, size); 53 if (ps == NULL) { 54 return true; 55 } 56 psset_update_begin(psset, ps); 57 void *addr = hpdata_reserve_alloc(ps, size); 58 edata_init(r_edata, edata_arena_ind_get(r_edata), addr, size, 59 /* slab */ false, SC_NSIZES, /* sn */ 0, extent_state_active, 60 /* zeroed */ false, /* committed */ true, EXTENT_PAI_HPA, 61 EXTENT_NOT_HEAD); 62 edata_ps_set(r_edata, ps); 63 psset_update_end(psset, ps); 64 return false; 65 } 66 67 static hpdata_t * 68 test_psset_dalloc(psset_t *psset, edata_t *edata) { 69 hpdata_t *ps = edata_ps_get(edata); 70 psset_update_begin(psset, ps); 71 hpdata_unreserve(ps, edata_addr_get(edata), edata_size_get(edata)); 72 psset_update_end(psset, ps); 73 if (hpdata_empty(ps)) { 74 psset_remove(psset, ps); 75 return ps; 76 } else { 77 return NULL; 78 } 79 } 80 81 static void 82 edata_expect(edata_t *edata, size_t page_offset, size_t page_cnt) { 83 /* 84 * Note that allocations should get the arena ind of their home 85 * arena, *not* the arena ind of the pageslab allocator. 86 */ 87 expect_u_eq(ALLOC_ARENA_IND, edata_arena_ind_get(edata), 88 "Arena ind changed"); 89 expect_ptr_eq( 90 (void *)((uintptr_t)PAGESLAB_ADDR + (page_offset << LG_PAGE)), 91 edata_addr_get(edata), "Didn't allocate in order"); 92 expect_zu_eq(page_cnt << LG_PAGE, edata_size_get(edata), ""); 93 expect_false(edata_slab_get(edata), ""); 94 expect_u_eq(SC_NSIZES, edata_szind_get_maybe_invalid(edata), 95 ""); 96 expect_u64_eq(0, edata_sn_get(edata), ""); 97 expect_d_eq(edata_state_get(edata), extent_state_active, ""); 98 expect_false(edata_zeroed_get(edata), ""); 99 expect_true(edata_committed_get(edata), ""); 100 expect_d_eq(EXTENT_PAI_HPA, edata_pai_get(edata), ""); 101 expect_false(edata_is_head_get(edata), ""); 102 } 103 104 TEST_BEGIN(test_empty) { 105 bool err; 106 hpdata_t pageslab; 107 hpdata_init(&pageslab, PAGESLAB_ADDR, PAGESLAB_AGE); 108 109 edata_t alloc; 110 edata_init_test(&alloc); 111 112 psset_t psset; 113 psset_init(&psset); 114 115 /* Empty psset should return fail allocations. */ 116 err = test_psset_alloc_reuse(&psset, &alloc, PAGE); 117 expect_true(err, "Empty psset succeeded in an allocation."); 118 } 119 TEST_END 120 121 TEST_BEGIN(test_fill) { 122 bool err; 123 124 hpdata_t pageslab; 125 hpdata_init(&pageslab, PAGESLAB_ADDR, PAGESLAB_AGE); 126 127 edata_t alloc[HUGEPAGE_PAGES]; 128 129 psset_t psset; 130 psset_init(&psset); 131 132 edata_init_test(&alloc[0]); 133 test_psset_alloc_new(&psset, &pageslab, &alloc[0], PAGE); 134 for (size_t i = 1; i < HUGEPAGE_PAGES; i++) { 135 edata_init_test(&alloc[i]); 136 err = test_psset_alloc_reuse(&psset, &alloc[i], PAGE); 137 expect_false(err, "Nonempty psset failed page allocation."); 138 } 139 140 for (size_t i = 0; i < HUGEPAGE_PAGES; i++) { 141 edata_t *edata = &alloc[i]; 142 edata_expect(edata, i, 1); 143 } 144 145 /* The pageslab, and thus psset, should now have no allocations. */ 146 edata_t extra_alloc; 147 edata_init_test(&extra_alloc); 148 err = test_psset_alloc_reuse(&psset, &extra_alloc, PAGE); 149 expect_true(err, "Alloc succeeded even though psset should be empty"); 150 } 151 TEST_END 152 153 TEST_BEGIN(test_reuse) { 154 bool err; 155 hpdata_t *ps; 156 157 hpdata_t pageslab; 158 hpdata_init(&pageslab, PAGESLAB_ADDR, PAGESLAB_AGE); 159 160 edata_t alloc[HUGEPAGE_PAGES]; 161 162 psset_t psset; 163 psset_init(&psset); 164 165 edata_init_test(&alloc[0]); 166 test_psset_alloc_new(&psset, &pageslab, &alloc[0], PAGE); 167 for (size_t i = 1; i < HUGEPAGE_PAGES; i++) { 168 edata_init_test(&alloc[i]); 169 err = test_psset_alloc_reuse(&psset, &alloc[i], PAGE); 170 expect_false(err, "Nonempty psset failed page allocation."); 171 } 172 173 /* Free odd indices. */ 174 for (size_t i = 0; i < HUGEPAGE_PAGES; i ++) { 175 if (i % 2 == 0) { 176 continue; 177 } 178 ps = test_psset_dalloc(&psset, &alloc[i]); 179 expect_ptr_null(ps, "Nonempty pageslab evicted"); 180 } 181 /* Realloc into them. */ 182 for (size_t i = 0; i < HUGEPAGE_PAGES; i++) { 183 if (i % 2 == 0) { 184 continue; 185 } 186 err = test_psset_alloc_reuse(&psset, &alloc[i], PAGE); 187 expect_false(err, "Nonempty psset failed page allocation."); 188 edata_expect(&alloc[i], i, 1); 189 } 190 /* Now, free the pages at indices 0 or 1 mod 2. */ 191 for (size_t i = 0; i < HUGEPAGE_PAGES; i++) { 192 if (i % 4 > 1) { 193 continue; 194 } 195 ps = test_psset_dalloc(&psset, &alloc[i]); 196 expect_ptr_null(ps, "Nonempty pageslab evicted"); 197 } 198 /* And realloc 2-page allocations into them. */ 199 for (size_t i = 0; i < HUGEPAGE_PAGES; i++) { 200 if (i % 4 != 0) { 201 continue; 202 } 203 err = test_psset_alloc_reuse(&psset, &alloc[i], 2 * PAGE); 204 expect_false(err, "Nonempty psset failed page allocation."); 205 edata_expect(&alloc[i], i, 2); 206 } 207 /* Free all the 2-page allocations. */ 208 for (size_t i = 0; i < HUGEPAGE_PAGES; i++) { 209 if (i % 4 != 0) { 210 continue; 211 } 212 ps = test_psset_dalloc(&psset, &alloc[i]); 213 expect_ptr_null(ps, "Nonempty pageslab evicted"); 214 } 215 /* 216 * Free up a 1-page hole next to a 2-page hole, but somewhere in the 217 * middle of the pageslab. Index 11 should be right before such a hole 218 * (since 12 % 4 == 0). 219 */ 220 size_t index_of_3 = 11; 221 ps = test_psset_dalloc(&psset, &alloc[index_of_3]); 222 expect_ptr_null(ps, "Nonempty pageslab evicted"); 223 err = test_psset_alloc_reuse(&psset, &alloc[index_of_3], 3 * PAGE); 224 expect_false(err, "Should have been able to find alloc."); 225 edata_expect(&alloc[index_of_3], index_of_3, 3); 226 227 /* 228 * Free up a 4-page hole at the end. Recall that the pages at offsets 0 229 * and 1 mod 4 were freed above, so we just have to free the last 230 * allocations. 231 */ 232 ps = test_psset_dalloc(&psset, &alloc[HUGEPAGE_PAGES - 1]); 233 expect_ptr_null(ps, "Nonempty pageslab evicted"); 234 ps = test_psset_dalloc(&psset, &alloc[HUGEPAGE_PAGES - 2]); 235 expect_ptr_null(ps, "Nonempty pageslab evicted"); 236 237 /* Make sure we can satisfy an allocation at the very end of a slab. */ 238 size_t index_of_4 = HUGEPAGE_PAGES - 4; 239 err = test_psset_alloc_reuse(&psset, &alloc[index_of_4], 4 * PAGE); 240 expect_false(err, "Should have been able to find alloc."); 241 edata_expect(&alloc[index_of_4], index_of_4, 4); 242 } 243 TEST_END 244 245 TEST_BEGIN(test_evict) { 246 bool err; 247 hpdata_t *ps; 248 249 hpdata_t pageslab; 250 hpdata_init(&pageslab, PAGESLAB_ADDR, PAGESLAB_AGE); 251 252 edata_t alloc[HUGEPAGE_PAGES]; 253 254 psset_t psset; 255 psset_init(&psset); 256 257 /* Alloc the whole slab. */ 258 edata_init_test(&alloc[0]); 259 test_psset_alloc_new(&psset, &pageslab, &alloc[0], PAGE); 260 for (size_t i = 1; i < HUGEPAGE_PAGES; i++) { 261 edata_init_test(&alloc[i]); 262 err = test_psset_alloc_reuse(&psset, &alloc[i], PAGE); 263 expect_false(err, "Unxpected allocation failure"); 264 } 265 266 /* Dealloc the whole slab, going forwards. */ 267 for (size_t i = 0; i < HUGEPAGE_PAGES - 1; i++) { 268 ps = test_psset_dalloc(&psset, &alloc[i]); 269 expect_ptr_null(ps, "Nonempty pageslab evicted"); 270 } 271 ps = test_psset_dalloc(&psset, &alloc[HUGEPAGE_PAGES - 1]); 272 expect_ptr_eq(&pageslab, ps, "Empty pageslab not evicted."); 273 274 err = test_psset_alloc_reuse(&psset, &alloc[0], PAGE); 275 expect_true(err, "psset should be empty."); 276 } 277 TEST_END 278 279 TEST_BEGIN(test_multi_pageslab) { 280 bool err; 281 hpdata_t *ps; 282 283 hpdata_t pageslab[2]; 284 hpdata_init(&pageslab[0], PAGESLAB_ADDR, PAGESLAB_AGE); 285 hpdata_init(&pageslab[1], 286 (void *)((uintptr_t)PAGESLAB_ADDR + HUGEPAGE), 287 PAGESLAB_AGE + 1); 288 289 edata_t alloc[2][HUGEPAGE_PAGES]; 290 291 psset_t psset; 292 psset_init(&psset); 293 294 /* Insert both slabs. */ 295 edata_init_test(&alloc[0][0]); 296 test_psset_alloc_new(&psset, &pageslab[0], &alloc[0][0], PAGE); 297 edata_init_test(&alloc[1][0]); 298 test_psset_alloc_new(&psset, &pageslab[1], &alloc[1][0], PAGE); 299 300 /* Fill them both up; make sure we do so in first-fit order. */ 301 for (size_t i = 0; i < 2; i++) { 302 for (size_t j = 1; j < HUGEPAGE_PAGES; j++) { 303 edata_init_test(&alloc[i][j]); 304 err = test_psset_alloc_reuse(&psset, &alloc[i][j], PAGE); 305 expect_false(err, 306 "Nonempty psset failed page allocation."); 307 assert_ptr_eq(&pageslab[i], edata_ps_get(&alloc[i][j]), 308 "Didn't pick pageslabs in first-fit"); 309 } 310 } 311 312 /* 313 * Free up a 2-page hole in the earlier slab, and a 1-page one in the 314 * later one. We should still pick the later one. 315 */ 316 ps = test_psset_dalloc(&psset, &alloc[0][0]); 317 expect_ptr_null(ps, "Unexpected eviction"); 318 ps = test_psset_dalloc(&psset, &alloc[0][1]); 319 expect_ptr_null(ps, "Unexpected eviction"); 320 ps = test_psset_dalloc(&psset, &alloc[1][0]); 321 expect_ptr_null(ps, "Unexpected eviction"); 322 err = test_psset_alloc_reuse(&psset, &alloc[0][0], PAGE); 323 expect_ptr_eq(&pageslab[1], edata_ps_get(&alloc[0][0]), 324 "Should have picked the fuller pageslab"); 325 326 /* 327 * Now both slabs have 1-page holes. Free up a second one in the later 328 * slab. 329 */ 330 ps = test_psset_dalloc(&psset, &alloc[1][1]); 331 expect_ptr_null(ps, "Unexpected eviction"); 332 333 /* 334 * We should be able to allocate a 2-page object, even though an earlier 335 * size class is nonempty. 336 */ 337 err = test_psset_alloc_reuse(&psset, &alloc[1][0], 2 * PAGE); 338 expect_false(err, "Allocation should have succeeded"); 339 } 340 TEST_END 341 342 static void 343 stats_expect_empty(psset_bin_stats_t *stats) { 344 assert_zu_eq(0, stats->npageslabs, 345 "Supposedly empty bin had positive npageslabs"); 346 expect_zu_eq(0, stats->nactive, "Unexpected nonempty bin" 347 "Supposedly empty bin had positive nactive"); 348 } 349 350 static void 351 stats_expect(psset_t *psset, size_t nactive) { 352 if (nactive == HUGEPAGE_PAGES) { 353 expect_zu_eq(1, psset->stats.full_slabs[0].npageslabs, 354 "Expected a full slab"); 355 expect_zu_eq(HUGEPAGE_PAGES, 356 psset->stats.full_slabs[0].nactive, 357 "Should have exactly filled the bin"); 358 } else { 359 stats_expect_empty(&psset->stats.full_slabs[0]); 360 } 361 size_t ninactive = HUGEPAGE_PAGES - nactive; 362 pszind_t nonempty_pind = PSSET_NPSIZES; 363 if (ninactive != 0 && ninactive < HUGEPAGE_PAGES) { 364 nonempty_pind = sz_psz2ind(sz_psz_quantize_floor( 365 ninactive << LG_PAGE)); 366 } 367 for (pszind_t i = 0; i < PSSET_NPSIZES; i++) { 368 if (i == nonempty_pind) { 369 assert_zu_eq(1, 370 psset->stats.nonfull_slabs[i][0].npageslabs, 371 "Should have found a slab"); 372 expect_zu_eq(nactive, 373 psset->stats.nonfull_slabs[i][0].nactive, 374 "Mismatch in active pages"); 375 } else { 376 stats_expect_empty(&psset->stats.nonfull_slabs[i][0]); 377 } 378 } 379 expect_zu_eq(nactive, psset_nactive(psset), ""); 380 } 381 382 TEST_BEGIN(test_stats) { 383 bool err; 384 385 hpdata_t pageslab; 386 hpdata_init(&pageslab, PAGESLAB_ADDR, PAGESLAB_AGE); 387 388 edata_t alloc[HUGEPAGE_PAGES]; 389 390 psset_t psset; 391 psset_init(&psset); 392 stats_expect(&psset, 0); 393 394 edata_init_test(&alloc[0]); 395 test_psset_alloc_new(&psset, &pageslab, &alloc[0], PAGE); 396 for (size_t i = 1; i < HUGEPAGE_PAGES; i++) { 397 stats_expect(&psset, i); 398 edata_init_test(&alloc[i]); 399 err = test_psset_alloc_reuse(&psset, &alloc[i], PAGE); 400 expect_false(err, "Nonempty psset failed page allocation."); 401 } 402 stats_expect(&psset, HUGEPAGE_PAGES); 403 hpdata_t *ps; 404 for (ssize_t i = HUGEPAGE_PAGES - 1; i >= 0; i--) { 405 ps = test_psset_dalloc(&psset, &alloc[i]); 406 expect_true((ps == NULL) == (i != 0), 407 "test_psset_dalloc should only evict a slab on the last " 408 "free"); 409 stats_expect(&psset, i); 410 } 411 412 test_psset_alloc_new(&psset, &pageslab, &alloc[0], PAGE); 413 stats_expect(&psset, 1); 414 psset_update_begin(&psset, &pageslab); 415 stats_expect(&psset, 0); 416 psset_update_end(&psset, &pageslab); 417 stats_expect(&psset, 1); 418 } 419 TEST_END 420 421 /* 422 * Fills in and inserts two pageslabs, with the first better than the second, 423 * and each fully allocated (into the allocations in allocs and worse_allocs, 424 * each of which should be HUGEPAGE_PAGES long), except for a single free page 425 * at the end. 426 * 427 * (There's nothing magic about these numbers; it's just useful to share the 428 * setup between the oldest fit and the insert/remove test). 429 */ 430 static void 431 init_test_pageslabs(psset_t *psset, hpdata_t *pageslab, 432 hpdata_t *worse_pageslab, edata_t *alloc, edata_t *worse_alloc) { 433 bool err; 434 435 hpdata_init(pageslab, (void *)(10 * HUGEPAGE), PAGESLAB_AGE); 436 /* 437 * This pageslab would be better from an address-first-fit POV, but 438 * worse from an age POV. 439 */ 440 hpdata_init(worse_pageslab, (void *)(9 * HUGEPAGE), PAGESLAB_AGE + 1); 441 442 psset_init(psset); 443 444 edata_init_test(&alloc[0]); 445 test_psset_alloc_new(psset, pageslab, &alloc[0], PAGE); 446 for (size_t i = 1; i < HUGEPAGE_PAGES; i++) { 447 edata_init_test(&alloc[i]); 448 err = test_psset_alloc_reuse(psset, &alloc[i], PAGE); 449 expect_false(err, "Nonempty psset failed page allocation."); 450 expect_ptr_eq(pageslab, edata_ps_get(&alloc[i]), 451 "Allocated from the wrong pageslab"); 452 } 453 454 edata_init_test(&worse_alloc[0]); 455 test_psset_alloc_new(psset, worse_pageslab, &worse_alloc[0], PAGE); 456 expect_ptr_eq(worse_pageslab, edata_ps_get(&worse_alloc[0]), 457 "Allocated from the wrong pageslab"); 458 /* 459 * Make the two pssets otherwise indistinguishable; all full except for 460 * a single page. 461 */ 462 for (size_t i = 1; i < HUGEPAGE_PAGES - 1; i++) { 463 edata_init_test(&worse_alloc[i]); 464 err = test_psset_alloc_reuse(psset, &alloc[i], PAGE); 465 expect_false(err, "Nonempty psset failed page allocation."); 466 expect_ptr_eq(worse_pageslab, edata_ps_get(&alloc[i]), 467 "Allocated from the wrong pageslab"); 468 } 469 470 /* Deallocate the last page from the older pageslab. */ 471 hpdata_t *evicted = test_psset_dalloc(psset, 472 &alloc[HUGEPAGE_PAGES - 1]); 473 expect_ptr_null(evicted, "Unexpected eviction"); 474 } 475 476 TEST_BEGIN(test_oldest_fit) { 477 bool err; 478 edata_t alloc[HUGEPAGE_PAGES]; 479 edata_t worse_alloc[HUGEPAGE_PAGES]; 480 481 hpdata_t pageslab; 482 hpdata_t worse_pageslab; 483 484 psset_t psset; 485 486 init_test_pageslabs(&psset, &pageslab, &worse_pageslab, alloc, 487 worse_alloc); 488 489 /* The edata should come from the better pageslab. */ 490 edata_t test_edata; 491 edata_init_test(&test_edata); 492 err = test_psset_alloc_reuse(&psset, &test_edata, PAGE); 493 expect_false(err, "Nonempty psset failed page allocation"); 494 expect_ptr_eq(&pageslab, edata_ps_get(&test_edata), 495 "Allocated from the wrong pageslab"); 496 } 497 TEST_END 498 499 TEST_BEGIN(test_insert_remove) { 500 bool err; 501 hpdata_t *ps; 502 edata_t alloc[HUGEPAGE_PAGES]; 503 edata_t worse_alloc[HUGEPAGE_PAGES]; 504 505 hpdata_t pageslab; 506 hpdata_t worse_pageslab; 507 508 psset_t psset; 509 510 init_test_pageslabs(&psset, &pageslab, &worse_pageslab, alloc, 511 worse_alloc); 512 513 /* Remove better; should still be able to alloc from worse. */ 514 psset_update_begin(&psset, &pageslab); 515 err = test_psset_alloc_reuse(&psset, &worse_alloc[HUGEPAGE_PAGES - 1], 516 PAGE); 517 expect_false(err, "Removal should still leave an empty page"); 518 expect_ptr_eq(&worse_pageslab, 519 edata_ps_get(&worse_alloc[HUGEPAGE_PAGES - 1]), 520 "Allocated out of wrong ps"); 521 522 /* 523 * After deallocating the previous alloc and reinserting better, it 524 * should be preferred for future allocations. 525 */ 526 ps = test_psset_dalloc(&psset, &worse_alloc[HUGEPAGE_PAGES - 1]); 527 expect_ptr_null(ps, "Incorrect eviction of nonempty pageslab"); 528 psset_update_end(&psset, &pageslab); 529 err = test_psset_alloc_reuse(&psset, &alloc[HUGEPAGE_PAGES - 1], PAGE); 530 expect_false(err, "psset should be nonempty"); 531 expect_ptr_eq(&pageslab, edata_ps_get(&alloc[HUGEPAGE_PAGES - 1]), 532 "Removal/reinsertion shouldn't change ordering"); 533 /* 534 * After deallocating and removing both, allocations should fail. 535 */ 536 ps = test_psset_dalloc(&psset, &alloc[HUGEPAGE_PAGES - 1]); 537 expect_ptr_null(ps, "Incorrect eviction"); 538 psset_update_begin(&psset, &pageslab); 539 psset_update_begin(&psset, &worse_pageslab); 540 err = test_psset_alloc_reuse(&psset, &alloc[HUGEPAGE_PAGES - 1], PAGE); 541 expect_true(err, "psset should be empty, but an alloc succeeded"); 542 } 543 TEST_END 544 545 TEST_BEGIN(test_purge_prefers_nonhuge) { 546 /* 547 * All else being equal, we should prefer purging non-huge pages over 548 * huge ones for non-empty extents. 549 */ 550 551 /* Nothing magic about this constant. */ 552 enum { 553 NHP = 23, 554 }; 555 hpdata_t *hpdata; 556 557 psset_t psset; 558 psset_init(&psset); 559 560 hpdata_t hpdata_huge[NHP]; 561 uintptr_t huge_begin = (uintptr_t)&hpdata_huge[0]; 562 uintptr_t huge_end = (uintptr_t)&hpdata_huge[NHP]; 563 hpdata_t hpdata_nonhuge[NHP]; 564 uintptr_t nonhuge_begin = (uintptr_t)&hpdata_nonhuge[0]; 565 uintptr_t nonhuge_end = (uintptr_t)&hpdata_nonhuge[NHP]; 566 567 for (size_t i = 0; i < NHP; i++) { 568 hpdata_init(&hpdata_huge[i], (void *)((10 + i) * HUGEPAGE), 569 123 + i); 570 psset_insert(&psset, &hpdata_huge[i]); 571 572 hpdata_init(&hpdata_nonhuge[i], 573 (void *)((10 + NHP + i) * HUGEPAGE), 574 456 + i); 575 psset_insert(&psset, &hpdata_nonhuge[i]); 576 577 } 578 for (int i = 0; i < 2 * NHP; i++) { 579 hpdata = psset_pick_alloc(&psset, HUGEPAGE * 3 / 4); 580 psset_update_begin(&psset, hpdata); 581 void *ptr; 582 ptr = hpdata_reserve_alloc(hpdata, HUGEPAGE * 3 / 4); 583 /* Ignore the first alloc, which will stick around. */ 584 (void)ptr; 585 /* 586 * The second alloc is to dirty the pages; free it immediately 587 * after allocating. 588 */ 589 ptr = hpdata_reserve_alloc(hpdata, HUGEPAGE / 4); 590 hpdata_unreserve(hpdata, ptr, HUGEPAGE / 4); 591 592 if (huge_begin <= (uintptr_t)hpdata 593 && (uintptr_t)hpdata < huge_end) { 594 hpdata_hugify(hpdata); 595 } 596 597 hpdata_purge_allowed_set(hpdata, true); 598 psset_update_end(&psset, hpdata); 599 } 600 601 /* 602 * We've got a bunch of 1/8th dirty hpdatas. It should give us all the 603 * non-huge ones to purge, then all the huge ones, then refuse to purge 604 * further. 605 */ 606 for (int i = 0; i < NHP; i++) { 607 hpdata = psset_pick_purge(&psset); 608 assert_true(nonhuge_begin <= (uintptr_t)hpdata 609 && (uintptr_t)hpdata < nonhuge_end, ""); 610 psset_update_begin(&psset, hpdata); 611 test_psset_fake_purge(hpdata); 612 hpdata_purge_allowed_set(hpdata, false); 613 psset_update_end(&psset, hpdata); 614 } 615 for (int i = 0; i < NHP; i++) { 616 hpdata = psset_pick_purge(&psset); 617 expect_true(huge_begin <= (uintptr_t)hpdata 618 && (uintptr_t)hpdata < huge_end, ""); 619 psset_update_begin(&psset, hpdata); 620 hpdata_dehugify(hpdata); 621 test_psset_fake_purge(hpdata); 622 hpdata_purge_allowed_set(hpdata, false); 623 psset_update_end(&psset, hpdata); 624 } 625 } 626 TEST_END 627 628 TEST_BEGIN(test_purge_prefers_empty) { 629 void *ptr; 630 631 psset_t psset; 632 psset_init(&psset); 633 634 hpdata_t hpdata_empty; 635 hpdata_t hpdata_nonempty; 636 hpdata_init(&hpdata_empty, (void *)(10 * HUGEPAGE), 123); 637 psset_insert(&psset, &hpdata_empty); 638 hpdata_init(&hpdata_nonempty, (void *)(11 * HUGEPAGE), 456); 639 psset_insert(&psset, &hpdata_nonempty); 640 641 psset_update_begin(&psset, &hpdata_empty); 642 ptr = hpdata_reserve_alloc(&hpdata_empty, PAGE); 643 expect_ptr_eq(hpdata_addr_get(&hpdata_empty), ptr, ""); 644 hpdata_unreserve(&hpdata_empty, ptr, PAGE); 645 hpdata_purge_allowed_set(&hpdata_empty, true); 646 psset_update_end(&psset, &hpdata_empty); 647 648 psset_update_begin(&psset, &hpdata_nonempty); 649 ptr = hpdata_reserve_alloc(&hpdata_nonempty, 10 * PAGE); 650 expect_ptr_eq(hpdata_addr_get(&hpdata_nonempty), ptr, ""); 651 hpdata_unreserve(&hpdata_nonempty, ptr, 9 * PAGE); 652 hpdata_purge_allowed_set(&hpdata_nonempty, true); 653 psset_update_end(&psset, &hpdata_nonempty); 654 655 /* 656 * The nonempty slab has 9 dirty pages, while the empty one has only 1. 657 * We should still pick the empty one for purging. 658 */ 659 hpdata_t *to_purge = psset_pick_purge(&psset); 660 expect_ptr_eq(&hpdata_empty, to_purge, ""); 661 } 662 TEST_END 663 664 TEST_BEGIN(test_purge_prefers_empty_huge) { 665 void *ptr; 666 667 psset_t psset; 668 psset_init(&psset); 669 670 enum {NHP = 10 }; 671 672 hpdata_t hpdata_huge[NHP]; 673 hpdata_t hpdata_nonhuge[NHP]; 674 675 uintptr_t cur_addr = 100 * HUGEPAGE; 676 uint64_t cur_age = 123; 677 for (int i = 0; i < NHP; i++) { 678 hpdata_init(&hpdata_huge[i], (void *)cur_addr, cur_age); 679 cur_addr += HUGEPAGE; 680 cur_age++; 681 psset_insert(&psset, &hpdata_huge[i]); 682 683 hpdata_init(&hpdata_nonhuge[i], (void *)cur_addr, cur_age); 684 cur_addr += HUGEPAGE; 685 cur_age++; 686 psset_insert(&psset, &hpdata_nonhuge[i]); 687 688 /* 689 * Make the hpdata_huge[i] fully dirty, empty, purgable, and 690 * huge. 691 */ 692 psset_update_begin(&psset, &hpdata_huge[i]); 693 ptr = hpdata_reserve_alloc(&hpdata_huge[i], HUGEPAGE); 694 expect_ptr_eq(hpdata_addr_get(&hpdata_huge[i]), ptr, ""); 695 hpdata_hugify(&hpdata_huge[i]); 696 hpdata_unreserve(&hpdata_huge[i], ptr, HUGEPAGE); 697 hpdata_purge_allowed_set(&hpdata_huge[i], true); 698 psset_update_end(&psset, &hpdata_huge[i]); 699 700 /* 701 * Make hpdata_nonhuge[i] fully dirty, empty, purgable, and 702 * non-huge. 703 */ 704 psset_update_begin(&psset, &hpdata_nonhuge[i]); 705 ptr = hpdata_reserve_alloc(&hpdata_nonhuge[i], HUGEPAGE); 706 expect_ptr_eq(hpdata_addr_get(&hpdata_nonhuge[i]), ptr, ""); 707 hpdata_unreserve(&hpdata_nonhuge[i], ptr, HUGEPAGE); 708 hpdata_purge_allowed_set(&hpdata_nonhuge[i], true); 709 psset_update_end(&psset, &hpdata_nonhuge[i]); 710 } 711 712 /* 713 * We have a bunch of empty slabs, half huge, half nonhuge, inserted in 714 * alternating order. We should pop all the huge ones before popping 715 * any of the non-huge ones for purging. 716 */ 717 for (int i = 0; i < NHP; i++) { 718 hpdata_t *to_purge = psset_pick_purge(&psset); 719 expect_ptr_eq(&hpdata_huge[i], to_purge, ""); 720 psset_update_begin(&psset, to_purge); 721 hpdata_purge_allowed_set(to_purge, false); 722 psset_update_end(&psset, to_purge); 723 } 724 for (int i = 0; i < NHP; i++) { 725 hpdata_t *to_purge = psset_pick_purge(&psset); 726 expect_ptr_eq(&hpdata_nonhuge[i], to_purge, ""); 727 psset_update_begin(&psset, to_purge); 728 hpdata_purge_allowed_set(to_purge, false); 729 psset_update_end(&psset, to_purge); 730 } 731 } 732 TEST_END 733 734 int 735 main(void) { 736 return test_no_reentrancy( 737 test_empty, 738 test_fill, 739 test_reuse, 740 test_evict, 741 test_multi_pageslab, 742 test_stats, 743 test_oldest_fit, 744 test_insert_remove, 745 test_purge_prefers_nonhuge, 746 test_purge_prefers_empty, 747 test_purge_prefers_empty_huge); 748 } 749