1 #include "test/jemalloc_test.h" 2 3 static void 4 do_fill_test(cache_bin_t *bin, cache_bin_info_t *info, void **ptrs, 5 cache_bin_sz_t ncached_max, cache_bin_sz_t nfill_attempt, 6 cache_bin_sz_t nfill_succeed) { 7 bool success; 8 void *ptr; 9 assert_true(cache_bin_ncached_get_local(bin, info) == 0, ""); 10 CACHE_BIN_PTR_ARRAY_DECLARE(arr, nfill_attempt); 11 cache_bin_init_ptr_array_for_fill(bin, info, &arr, nfill_attempt); 12 for (cache_bin_sz_t i = 0; i < nfill_succeed; i++) { 13 arr.ptr[i] = &ptrs[i]; 14 } 15 cache_bin_finish_fill(bin, info, &arr, nfill_succeed); 16 expect_true(cache_bin_ncached_get_local(bin, info) == nfill_succeed, 17 ""); 18 cache_bin_low_water_set(bin); 19 20 for (cache_bin_sz_t i = 0; i < nfill_succeed; i++) { 21 ptr = cache_bin_alloc(bin, &success); 22 expect_true(success, ""); 23 expect_ptr_eq(ptr, (void *)&ptrs[i], 24 "Should pop in order filled"); 25 expect_true(cache_bin_low_water_get(bin, info) 26 == nfill_succeed - i - 1, ""); 27 } 28 expect_true(cache_bin_ncached_get_local(bin, info) == 0, ""); 29 expect_true(cache_bin_low_water_get(bin, info) == 0, ""); 30 } 31 32 static void 33 do_flush_test(cache_bin_t *bin, cache_bin_info_t *info, void **ptrs, 34 cache_bin_sz_t nfill, cache_bin_sz_t nflush) { 35 bool success; 36 assert_true(cache_bin_ncached_get_local(bin, info) == 0, ""); 37 38 for (cache_bin_sz_t i = 0; i < nfill; i++) { 39 success = cache_bin_dalloc_easy(bin, &ptrs[i]); 40 expect_true(success, ""); 41 } 42 43 CACHE_BIN_PTR_ARRAY_DECLARE(arr, nflush); 44 cache_bin_init_ptr_array_for_flush(bin, info, &arr, nflush); 45 for (cache_bin_sz_t i = 0; i < nflush; i++) { 46 expect_ptr_eq(arr.ptr[i], &ptrs[nflush - i - 1], ""); 47 } 48 cache_bin_finish_flush(bin, info, &arr, nflush); 49 50 expect_true(cache_bin_ncached_get_local(bin, info) == nfill - nflush, 51 ""); 52 while (cache_bin_ncached_get_local(bin, info) > 0) { 53 cache_bin_alloc(bin, &success); 54 } 55 } 56 57 static void 58 do_batch_alloc_test(cache_bin_t *bin, cache_bin_info_t *info, void **ptrs, 59 cache_bin_sz_t nfill, size_t batch) { 60 assert_true(cache_bin_ncached_get_local(bin, info) == 0, ""); 61 CACHE_BIN_PTR_ARRAY_DECLARE(arr, nfill); 62 cache_bin_init_ptr_array_for_fill(bin, info, &arr, nfill); 63 for (cache_bin_sz_t i = 0; i < nfill; i++) { 64 arr.ptr[i] = &ptrs[i]; 65 } 66 cache_bin_finish_fill(bin, info, &arr, nfill); 67 assert_true(cache_bin_ncached_get_local(bin, info) == nfill, ""); 68 cache_bin_low_water_set(bin); 69 70 void **out = malloc((batch + 1) * sizeof(void *)); 71 size_t n = cache_bin_alloc_batch(bin, batch, out); 72 assert_true(n == ((size_t)nfill < batch ? (size_t)nfill : batch), ""); 73 for (cache_bin_sz_t i = 0; i < (cache_bin_sz_t)n; i++) { 74 expect_ptr_eq(out[i], &ptrs[i], ""); 75 } 76 expect_true(cache_bin_low_water_get(bin, info) == nfill - 77 (cache_bin_sz_t)n, ""); 78 while (cache_bin_ncached_get_local(bin, info) > 0) { 79 bool success; 80 cache_bin_alloc(bin, &success); 81 } 82 free(out); 83 } 84 85 static void 86 test_bin_init(cache_bin_t *bin, cache_bin_info_t *info) { 87 size_t size; 88 size_t alignment; 89 cache_bin_info_compute_alloc(info, 1, &size, &alignment); 90 void *mem = mallocx(size, MALLOCX_ALIGN(alignment)); 91 assert_ptr_not_null(mem, "Unexpected mallocx failure"); 92 93 size_t cur_offset = 0; 94 cache_bin_preincrement(info, 1, mem, &cur_offset); 95 cache_bin_init(bin, info, mem, &cur_offset); 96 cache_bin_postincrement(info, 1, mem, &cur_offset); 97 assert_zu_eq(cur_offset, size, "Should use all requested memory"); 98 } 99 100 TEST_BEGIN(test_cache_bin) { 101 const int ncached_max = 100; 102 bool success; 103 void *ptr; 104 105 cache_bin_info_t info; 106 cache_bin_info_init(&info, ncached_max); 107 cache_bin_t bin; 108 test_bin_init(&bin, &info); 109 110 /* Initialize to empty; should then have 0 elements. */ 111 expect_d_eq(ncached_max, cache_bin_info_ncached_max(&info), ""); 112 expect_true(cache_bin_ncached_get_local(&bin, &info) == 0, ""); 113 expect_true(cache_bin_low_water_get(&bin, &info) == 0, ""); 114 115 ptr = cache_bin_alloc_easy(&bin, &success); 116 expect_false(success, "Shouldn't successfully allocate when empty"); 117 expect_ptr_null(ptr, "Shouldn't get a non-null pointer on failure"); 118 119 ptr = cache_bin_alloc(&bin, &success); 120 expect_false(success, "Shouldn't successfully allocate when empty"); 121 expect_ptr_null(ptr, "Shouldn't get a non-null pointer on failure"); 122 123 /* 124 * We allocate one more item than ncached_max, so we can test cache bin 125 * exhaustion. 126 */ 127 void **ptrs = mallocx(sizeof(void *) * (ncached_max + 1), 0); 128 assert_ptr_not_null(ptrs, "Unexpected mallocx failure"); 129 for (cache_bin_sz_t i = 0; i < ncached_max; i++) { 130 expect_true(cache_bin_ncached_get_local(&bin, &info) == i, ""); 131 success = cache_bin_dalloc_easy(&bin, &ptrs[i]); 132 expect_true(success, 133 "Should be able to dalloc into a non-full cache bin."); 134 expect_true(cache_bin_low_water_get(&bin, &info) == 0, 135 "Pushes and pops shouldn't change low water of zero."); 136 } 137 expect_true(cache_bin_ncached_get_local(&bin, &info) == ncached_max, 138 ""); 139 success = cache_bin_dalloc_easy(&bin, &ptrs[ncached_max]); 140 expect_false(success, "Shouldn't be able to dalloc into a full bin."); 141 142 cache_bin_low_water_set(&bin); 143 144 for (cache_bin_sz_t i = 0; i < ncached_max; i++) { 145 expect_true(cache_bin_low_water_get(&bin, &info) 146 == ncached_max - i, ""); 147 expect_true(cache_bin_ncached_get_local(&bin, &info) 148 == ncached_max - i, ""); 149 /* 150 * This should fail -- the easy variant can't change the low 151 * water mark. 152 */ 153 ptr = cache_bin_alloc_easy(&bin, &success); 154 expect_ptr_null(ptr, ""); 155 expect_false(success, ""); 156 expect_true(cache_bin_low_water_get(&bin, &info) 157 == ncached_max - i, ""); 158 expect_true(cache_bin_ncached_get_local(&bin, &info) 159 == ncached_max - i, ""); 160 161 /* This should succeed, though. */ 162 ptr = cache_bin_alloc(&bin, &success); 163 expect_true(success, ""); 164 expect_ptr_eq(ptr, &ptrs[ncached_max - i - 1], 165 "Alloc should pop in stack order"); 166 expect_true(cache_bin_low_water_get(&bin, &info) 167 == ncached_max - i - 1, ""); 168 expect_true(cache_bin_ncached_get_local(&bin, &info) 169 == ncached_max - i - 1, ""); 170 } 171 /* Now we're empty -- all alloc attempts should fail. */ 172 expect_true(cache_bin_ncached_get_local(&bin, &info) == 0, ""); 173 ptr = cache_bin_alloc_easy(&bin, &success); 174 expect_ptr_null(ptr, ""); 175 expect_false(success, ""); 176 ptr = cache_bin_alloc(&bin, &success); 177 expect_ptr_null(ptr, ""); 178 expect_false(success, ""); 179 180 for (cache_bin_sz_t i = 0; i < ncached_max / 2; i++) { 181 cache_bin_dalloc_easy(&bin, &ptrs[i]); 182 } 183 cache_bin_low_water_set(&bin); 184 185 for (cache_bin_sz_t i = ncached_max / 2; i < ncached_max; i++) { 186 cache_bin_dalloc_easy(&bin, &ptrs[i]); 187 } 188 expect_true(cache_bin_ncached_get_local(&bin, &info) == ncached_max, 189 ""); 190 for (cache_bin_sz_t i = ncached_max - 1; i >= ncached_max / 2; i--) { 191 /* 192 * Size is bigger than low water -- the reduced version should 193 * succeed. 194 */ 195 ptr = cache_bin_alloc_easy(&bin, &success); 196 expect_true(success, ""); 197 expect_ptr_eq(ptr, &ptrs[i], ""); 198 } 199 /* But now, we've hit low-water. */ 200 ptr = cache_bin_alloc_easy(&bin, &success); 201 expect_false(success, ""); 202 expect_ptr_null(ptr, ""); 203 204 /* We're going to test filling -- we must be empty to start. */ 205 while (cache_bin_ncached_get_local(&bin, &info)) { 206 cache_bin_alloc(&bin, &success); 207 expect_true(success, ""); 208 } 209 210 /* Test fill. */ 211 /* Try to fill all, succeed fully. */ 212 do_fill_test(&bin, &info, ptrs, ncached_max, ncached_max, ncached_max); 213 /* Try to fill all, succeed partially. */ 214 do_fill_test(&bin, &info, ptrs, ncached_max, ncached_max, 215 ncached_max / 2); 216 /* Try to fill all, fail completely. */ 217 do_fill_test(&bin, &info, ptrs, ncached_max, ncached_max, 0); 218 219 /* Try to fill some, succeed fully. */ 220 do_fill_test(&bin, &info, ptrs, ncached_max, ncached_max / 2, 221 ncached_max / 2); 222 /* Try to fill some, succeed partially. */ 223 do_fill_test(&bin, &info, ptrs, ncached_max, ncached_max / 2, 224 ncached_max / 4); 225 /* Try to fill some, fail completely. */ 226 do_fill_test(&bin, &info, ptrs, ncached_max, ncached_max / 2, 0); 227 228 do_flush_test(&bin, &info, ptrs, ncached_max, ncached_max); 229 do_flush_test(&bin, &info, ptrs, ncached_max, ncached_max / 2); 230 do_flush_test(&bin, &info, ptrs, ncached_max, 0); 231 do_flush_test(&bin, &info, ptrs, ncached_max / 2, ncached_max / 2); 232 do_flush_test(&bin, &info, ptrs, ncached_max / 2, ncached_max / 4); 233 do_flush_test(&bin, &info, ptrs, ncached_max / 2, 0); 234 235 do_batch_alloc_test(&bin, &info, ptrs, ncached_max, ncached_max); 236 do_batch_alloc_test(&bin, &info, ptrs, ncached_max, ncached_max * 2); 237 do_batch_alloc_test(&bin, &info, ptrs, ncached_max, ncached_max / 2); 238 do_batch_alloc_test(&bin, &info, ptrs, ncached_max, 2); 239 do_batch_alloc_test(&bin, &info, ptrs, ncached_max, 1); 240 do_batch_alloc_test(&bin, &info, ptrs, ncached_max, 0); 241 do_batch_alloc_test(&bin, &info, ptrs, ncached_max / 2, 242 ncached_max / 2); 243 do_batch_alloc_test(&bin, &info, ptrs, ncached_max / 2, ncached_max); 244 do_batch_alloc_test(&bin, &info, ptrs, ncached_max / 2, 245 ncached_max / 4); 246 do_batch_alloc_test(&bin, &info, ptrs, ncached_max / 2, 2); 247 do_batch_alloc_test(&bin, &info, ptrs, ncached_max / 2, 1); 248 do_batch_alloc_test(&bin, &info, ptrs, ncached_max / 2, 0); 249 do_batch_alloc_test(&bin, &info, ptrs, 2, ncached_max); 250 do_batch_alloc_test(&bin, &info, ptrs, 2, 2); 251 do_batch_alloc_test(&bin, &info, ptrs, 2, 1); 252 do_batch_alloc_test(&bin, &info, ptrs, 2, 0); 253 do_batch_alloc_test(&bin, &info, ptrs, 1, 2); 254 do_batch_alloc_test(&bin, &info, ptrs, 1, 1); 255 do_batch_alloc_test(&bin, &info, ptrs, 1, 0); 256 do_batch_alloc_test(&bin, &info, ptrs, 0, 2); 257 do_batch_alloc_test(&bin, &info, ptrs, 0, 1); 258 do_batch_alloc_test(&bin, &info, ptrs, 0, 0); 259 260 free(ptrs); 261 } 262 TEST_END 263 264 static void 265 do_flush_stashed_test(cache_bin_t *bin, cache_bin_info_t *info, void **ptrs, 266 cache_bin_sz_t nfill, cache_bin_sz_t nstash) { 267 expect_true(cache_bin_ncached_get_local(bin, info) == 0, 268 "Bin not empty"); 269 expect_true(cache_bin_nstashed_get_local(bin, info) == 0, 270 "Bin not empty"); 271 expect_true(nfill + nstash <= info->ncached_max, "Exceeded max"); 272 273 bool ret; 274 /* Fill */ 275 for (cache_bin_sz_t i = 0; i < nfill; i++) { 276 ret = cache_bin_dalloc_easy(bin, &ptrs[i]); 277 expect_true(ret, "Unexpected fill failure"); 278 } 279 expect_true(cache_bin_ncached_get_local(bin, info) == nfill, 280 "Wrong cached count"); 281 282 /* Stash */ 283 for (cache_bin_sz_t i = 0; i < nstash; i++) { 284 ret = cache_bin_stash(bin, &ptrs[i + nfill]); 285 expect_true(ret, "Unexpected stash failure"); 286 } 287 expect_true(cache_bin_nstashed_get_local(bin, info) == nstash, 288 "Wrong stashed count"); 289 290 if (nfill + nstash == info->ncached_max) { 291 ret = cache_bin_dalloc_easy(bin, &ptrs[0]); 292 expect_false(ret, "Should not dalloc into a full bin"); 293 ret = cache_bin_stash(bin, &ptrs[0]); 294 expect_false(ret, "Should not stash into a full bin"); 295 } 296 297 /* Alloc filled ones */ 298 for (cache_bin_sz_t i = 0; i < nfill; i++) { 299 void *ptr = cache_bin_alloc(bin, &ret); 300 expect_true(ret, "Unexpected alloc failure"); 301 /* Verify it's not from the stashed range. */ 302 expect_true((uintptr_t)ptr < (uintptr_t)&ptrs[nfill], 303 "Should not alloc stashed ptrs"); 304 } 305 expect_true(cache_bin_ncached_get_local(bin, info) == 0, 306 "Wrong cached count"); 307 expect_true(cache_bin_nstashed_get_local(bin, info) == nstash, 308 "Wrong stashed count"); 309 310 cache_bin_alloc(bin, &ret); 311 expect_false(ret, "Should not alloc stashed"); 312 313 /* Clear stashed ones */ 314 cache_bin_finish_flush_stashed(bin, info); 315 expect_true(cache_bin_ncached_get_local(bin, info) == 0, 316 "Wrong cached count"); 317 expect_true(cache_bin_nstashed_get_local(bin, info) == 0, 318 "Wrong stashed count"); 319 320 cache_bin_alloc(bin, &ret); 321 expect_false(ret, "Should not alloc from empty bin"); 322 } 323 324 TEST_BEGIN(test_cache_bin_stash) { 325 const int ncached_max = 100; 326 327 cache_bin_t bin; 328 cache_bin_info_t info; 329 cache_bin_info_init(&info, ncached_max); 330 test_bin_init(&bin, &info); 331 332 /* 333 * The content of this array is not accessed; instead the interior 334 * addresses are used to insert / stash into the bins as test pointers. 335 */ 336 void **ptrs = mallocx(sizeof(void *) * (ncached_max + 1), 0); 337 assert_ptr_not_null(ptrs, "Unexpected mallocx failure"); 338 bool ret; 339 for (cache_bin_sz_t i = 0; i < ncached_max; i++) { 340 expect_true(cache_bin_ncached_get_local(&bin, &info) == 341 (i / 2 + i % 2), "Wrong ncached value"); 342 expect_true(cache_bin_nstashed_get_local(&bin, &info) == i / 2, 343 "Wrong nstashed value"); 344 if (i % 2 == 0) { 345 cache_bin_dalloc_easy(&bin, &ptrs[i]); 346 } else { 347 ret = cache_bin_stash(&bin, &ptrs[i]); 348 expect_true(ret, "Should be able to stash into a " 349 "non-full cache bin"); 350 } 351 } 352 ret = cache_bin_dalloc_easy(&bin, &ptrs[0]); 353 expect_false(ret, "Should not dalloc into a full cache bin"); 354 ret = cache_bin_stash(&bin, &ptrs[0]); 355 expect_false(ret, "Should not stash into a full cache bin"); 356 for (cache_bin_sz_t i = 0; i < ncached_max; i++) { 357 void *ptr = cache_bin_alloc(&bin, &ret); 358 if (i < ncached_max / 2) { 359 expect_true(ret, "Should be able to alloc"); 360 uintptr_t diff = ((uintptr_t)ptr - (uintptr_t)&ptrs[0]) 361 / sizeof(void *); 362 expect_true(diff % 2 == 0, "Should be able to alloc"); 363 } else { 364 expect_false(ret, "Should not alloc stashed"); 365 expect_true(cache_bin_nstashed_get_local(&bin, &info) == 366 ncached_max / 2, "Wrong nstashed value"); 367 } 368 } 369 370 test_bin_init(&bin, &info); 371 do_flush_stashed_test(&bin, &info, ptrs, ncached_max, 0); 372 do_flush_stashed_test(&bin, &info, ptrs, 0, ncached_max); 373 do_flush_stashed_test(&bin, &info, ptrs, ncached_max / 2, ncached_max / 2); 374 do_flush_stashed_test(&bin, &info, ptrs, ncached_max / 4, ncached_max / 2); 375 do_flush_stashed_test(&bin, &info, ptrs, ncached_max / 2, ncached_max / 4); 376 do_flush_stashed_test(&bin, &info, ptrs, ncached_max / 4, ncached_max / 4); 377 } 378 TEST_END 379 380 int 381 main(void) { 382 return test(test_cache_bin, 383 test_cache_bin_stash); 384 } 385
Indexes created Sat Apr 18 00:22:28 UTC 2026