1 /* 2 * Pool allocator for low memory targets. 3 */ 4 5 #include <stdio.h> 6 #include <stdlib.h> 7 #include <string.h> 8 #include <stdint.h> 9 #include <stdarg.h> 10 #include "duktape.h" 11 #include "duk_alloc_pool.h" 12 13 /* Define to enable some debug printfs. */ 14 /* #define DUK_ALLOC_POOL_DEBUG */ 15 16 /* Define to enable approximate waste tracking. */ 17 /* #define DUK_ALLOC_POOL_TRACK_WASTE */ 18 19 /* Define to track global highwater for used and waste bytes. VERY SLOW, only 20 * useful for manual testing. 21 */ 22 /* #define DUK_ALLOC_POOL_TRACK_HIGHWATER */ 23 24 #if defined(DUK_ALLOC_POOL_ROMPTR_COMPRESSION) 25 #if 0 /* This extern declaration is provided by duktape.h, array provided by duktape.c. */ 26 extern const void * const duk_rom_compressed_pointers[]; 27 #endif 28 const void *duk_alloc_pool_romptr_low = NULL; 29 const void *duk_alloc_pool_romptr_high = NULL; 30 static void duk__alloc_pool_romptr_init(void); 31 #endif 32 33 #if defined(DUK_USE_HEAPPTR16) 34 void *duk_alloc_pool_ptrcomp_base = NULL; 35 #endif 36 37 #if defined(DUK_ALLOC_POOL_DEBUG) 38 static void duk__alloc_pool_dprintf(const char *fmt, ...) { 39 va_list ap; 40 va_start(ap, fmt); 41 vfprintf(stderr, fmt, ap); 42 va_end(ap); 43 } 44 #endif 45 46 /* 47 * Pool initialization 48 */ 49 50 void *duk_alloc_pool_init(char *buffer, 51 size_t size, 52 const duk_pool_config *configs, 53 duk_pool_state *states, 54 int num_pools, 55 duk_pool_global *global) { 56 double t_min, t_max, t_curr, x; 57 int step, i, j, n; 58 size_t total; 59 char *p; 60 61 /* XXX: check that 'size' is not too large when using pointer 62 * compression. 63 */ 64 65 /* To optimize pool counts first come up with a 't' which still allows 66 * total pool size to fit within user provided region. After that 67 * sprinkle any remaining bytes to the counts. Binary search with a 68 * fixed step count; last round uses 't_min' as 't_curr' to ensure it 69 * succeeds. 70 */ 71 72 t_min = 0.0; /* Unless config is insane, this should always be "good". */ 73 t_max = 1e6; 74 75 for (step = 0; ; step++) { 76 if (step >= 100) { 77 /* Force "known good", rerun config, and break out. 78 * Deals with rounding corner cases where t_curr is 79 * persistently "bad" even though t_min is a valid 80 * solution. 81 */ 82 t_curr = t_min; 83 } else { 84 t_curr = (t_min + t_max) / 2.0; 85 } 86 87 for (i = 0, total = 0; i < num_pools; i++) { 88 states[i].size = configs[i].size; 89 90 /* Target bytes = A*t + B ==> target count = (A*t + B) / block_size. 91 * Rely on A and B being small enough so that 'x' won't wrap. 92 */ 93 x = ((double) configs[i].a * t_curr + (double) configs[i].b) / (double) configs[i].size; 94 95 states[i].count = (unsigned int) x; 96 total += (size_t) states[i].size * (size_t) states[i].count; 97 if (total > size) { 98 goto bad; 99 } 100 } 101 102 /* t_curr is good. */ 103 #if defined(DUK_ALLOC_POOL_DEBUG) 104 duk__alloc_pool_dprintf("duk_alloc_pool_init: step=%d, t=[%lf %lf %lf] -> total %ld/%ld (good)\n", 105 step, t_min, t_curr, t_max, (long) total, (long) size); 106 #endif 107 if (step >= 100) { 108 /* Keep state[] initialization state. The state was 109 * created using the highest 't_min'. 110 */ 111 break; 112 } 113 t_min = t_curr; 114 continue; 115 116 bad: 117 /* t_curr is bad. */ 118 #if defined(DUK_ALLOC_POOL_DEBUG) 119 duk__alloc_pool_dprintf("duk_alloc_pool_init: step=%d, t=[%lf %lf %lf] -> total %ld/%ld (bad)\n", 120 step, t_min, t_curr, t_max, (long) total, (long) size); 121 #endif 122 123 if (step >= 1000) { 124 /* Cannot find any good solution; shouldn't happen 125 * unless config is bad or 'size' is so small that 126 * even a baseline allocation won't fit. 127 */ 128 return NULL; 129 } 130 t_max = t_curr; 131 /* continue */ 132 } 133 134 /* The base configuration is now good; sprinkle any leftovers to 135 * pools in descending order. Note that for good t_curr, 'total' 136 * indicates allocated bytes so far and 'size - total' indicates 137 * leftovers. 138 */ 139 for (i = num_pools - 1; i >= 0; i--) { 140 while (size - total >= states[i].size) { 141 /* Ignore potential wrapping of states[i].count as the count 142 * is 32 bits and shouldn't wrap in practice. 143 */ 144 states[i].count++; 145 total += states[i].size; 146 #if defined(DUK_ALLOC_POOL_DEBUG) 147 duk__alloc_pool_dprintf("duk_alloc_pool_init: sprinkle %ld bytes (%ld left after) to pool index %ld, new count %ld\n", 148 (long) states[i].size, (long) (size - total), (long) i, (long) states[i].count); 149 #endif 150 } 151 } 152 153 /* Pool counts are final. Allocate the user supplied region based 154 * on the final counts, initialize free lists for each block size, 155 * and otherwise finalize 'state' for use. 156 */ 157 p = buffer; 158 global->num_pools = num_pools; 159 global->states = states; 160 #if defined(DUK_ALLOC_POOL_TRACK_HIGHWATER) 161 #if defined(DUK_ALLOC_POOL_DEBUG) 162 duk__alloc_pool_dprintf("duk_alloc_pool_init: global highwater mark tracking enabled, THIS IS VERY SLOW!\n"); 163 #endif 164 global->hwm_used_bytes = 0U; 165 global->hwm_waste_bytes = 0U; 166 #endif 167 #if defined(DUK_ALLOC_POOL_TRACK_WASTE) 168 #if defined(DUK_ALLOC_POOL_DEBUG) 169 duk__alloc_pool_dprintf("duk_alloc_pool_init: approximate waste tracking enabled\n"); 170 #endif 171 #endif 172 173 #if defined(DUK_USE_HEAPPTR16) 174 /* Register global base value for pointer compression, assumes 175 * a single active pool -4 allows a single subtract to be used and 176 * still ensures no non-NULL pointer encodes to zero. 177 */ 178 duk_alloc_pool_ptrcomp_base = (void *) (p - 4); 179 #endif 180 181 for (i = 0; i < num_pools; i++) { 182 n = (int) states[i].count; 183 if (n > 0) { 184 states[i].first = (duk_pool_free *) p; 185 for (j = 0; j < n; j++) { 186 char *p_next = p + states[i].size; 187 ((duk_pool_free *) p)->next = 188 (j == n - 1) ? (duk_pool_free *) NULL : (duk_pool_free *) p_next; 189 p = p_next; 190 } 191 } else { 192 states[i].first = (duk_pool_free *) NULL; 193 } 194 states[i].alloc_end = p; 195 #if defined(DUK_ALLOC_POOL_TRACK_HIGHWATER) 196 states[i].hwm_used_count = 0; 197 #endif 198 /* All members of 'state' now initialized. */ 199 200 #if defined(DUK_ALLOC_POOL_DEBUG) 201 duk__alloc_pool_dprintf("duk_alloc_pool_init: block size %5ld, count %5ld, %8ld total bytes, " 202 "end %p\n", 203 (long) states[i].size, (long) states[i].count, 204 (long) states[i].size * (long) states[i].count, 205 (void *) states[i].alloc_end); 206 #endif 207 } 208 209 #if defined(DUK_ALLOC_POOL_ROMPTR_COMPRESSION) 210 /* ROM pointer compression precomputation. Assumes a single active 211 * pool. 212 */ 213 duk__alloc_pool_romptr_init(); 214 #endif 215 216 /* Use 'global' as udata. */ 217 return (void *) global; 218 } 219 220 /* 221 * Misc helpers 222 */ 223 224 #if defined(DUK_ALLOC_POOL_TRACK_WASTE) 225 static void duk__alloc_pool_set_waste_marker(void *ptr, size_t used, size_t size) { 226 /* Rely on the base pointer and size being divisible by 4 and thus 227 * aligned. Use 32-bit markers: a 4-byte resolution is good enough, 228 * and comparing 32 bits at a time makes false waste estimates less 229 * likely than when comparing as bytes. 230 */ 231 duk_uint32_t *p, *p_start, *p_end; 232 size_t used_round; 233 234 used_round = (used + 3U) & ~0x03U; /* round up to 4 */ 235 p_end = (duk_uint32_t *) ((duk_uint8_t *) ptr + size); 236 p_start = (duk_uint32_t *) ((duk_uint8_t *) ptr + used_round); 237 p = (duk_uint32_t *) p_start; 238 while (p != p_end) { 239 *p++ = DUK_ALLOC_POOL_WASTE_MARKER; 240 } 241 } 242 #else /* DUK_ALLOC_POOL_TRACK_WASTE */ 243 static void duk__alloc_pool_set_waste_marker(void *ptr, size_t used, size_t size) { 244 (void) ptr; (void) used; (void) size; 245 } 246 #endif /* DUK_ALLOC_POOL_TRACK_WASTE */ 247 248 #if defined(DUK_ALLOC_POOL_TRACK_WASTE) 249 static size_t duk__alloc_pool_get_waste_estimate(void *ptr, size_t size) { 250 duk_uint32_t *p, *p_end, *p_start; 251 252 /* Assumes size is >= 4. */ 253 p_start = (duk_uint32_t *) ptr; 254 p_end = (duk_uint32_t *) ((duk_uint8_t *) ptr + size); 255 p = p_end; 256 257 /* This scan may cause harmless valgrind complaints: there may be 258 * uninitialized bytes within the legitimate allocation or between 259 * the start of the waste marker and the end of the allocation. 260 */ 261 do { 262 p--; 263 if (*p == DUK_ALLOC_POOL_WASTE_MARKER) { 264 ; 265 } else { 266 return (size_t) (p_end - p - 1) * 4U; 267 } 268 } while (p != p_start); 269 270 return size; 271 } 272 #else /* DUK_ALLOC_POOL_TRACK_WASTE */ 273 static size_t duk__alloc_pool_get_waste_estimate(void *ptr, size_t size) { 274 (void) ptr; (void) size; 275 return 0; 276 } 277 #endif /* DUK_ALLOC_POOL_TRACK_WASTE */ 278 279 static int duk__alloc_pool_ptr_in_freelist(duk_pool_state *s, void *ptr) { 280 duk_pool_free *curr; 281 282 for (curr = s->first; curr != NULL; curr = curr->next) { 283 if ((void *) curr == ptr) { 284 return 1; 285 } 286 } 287 return 0; 288 } 289 290 void duk_alloc_pool_get_pool_stats(duk_pool_state *s, duk_pool_stats *res) { 291 void *curr; 292 size_t free_count; 293 size_t used_count; 294 size_t waste_bytes; 295 296 curr = s->alloc_end - (s->size * s->count); 297 free_count = 0U; 298 waste_bytes = 0U; 299 while (curr != s->alloc_end) { 300 if (duk__alloc_pool_ptr_in_freelist(s, curr)) { 301 free_count++; 302 } else { 303 waste_bytes += duk__alloc_pool_get_waste_estimate(curr, s->size); 304 } 305 curr = curr + s->size; 306 } 307 used_count = (size_t) (s->count - free_count); 308 309 res->used_count = used_count; 310 res->used_bytes = (size_t) (used_count * s->size); 311 res->free_count = free_count; 312 res->free_bytes = (size_t) (free_count * s->size); 313 res->waste_bytes = waste_bytes; 314 #if defined(DUK_ALLOC_POOL_TRACK_HIGHWATER) 315 res->hwm_used_count = s->hwm_used_count; 316 #else 317 res->hwm_used_count = 0U; 318 #endif 319 } 320 321 void duk_alloc_pool_get_global_stats(duk_pool_global *g, duk_pool_global_stats *res) { 322 int i; 323 size_t total_used = 0U; 324 size_t total_free = 0U; 325 size_t total_waste = 0U; 326 327 for (i = 0; i < g->num_pools; i++) { 328 duk_pool_state *s = &g->states[i]; 329 duk_pool_stats stats; 330 331 duk_alloc_pool_get_pool_stats(s, &stats); suite()332 333 total_used += stats.used_bytes; 334 total_free += stats.free_bytes; 335 total_waste += stats.waste_bytes; 336 } 337 338 res->used_bytes = total_used; 339 res->free_bytes = total_free; 340 res->waste_bytes = total_waste; 341 #if defined(DUK_ALLOC_POOL_TRACK_HIGHWATER) 342 res->hwm_used_bytes = g->hwm_used_bytes; 343 res->hwm_waste_bytes = g->hwm_waste_bytes; 344 #else 345 res->hwm_used_bytes = 0U; 346 res->hwm_waste_bytes = 0U; 347 #endif 348 } 349 350 #if defined(DUK_ALLOC_POOL_TRACK_HIGHWATER) 351 static void duk__alloc_pool_update_highwater(duk_pool_global *g) { 352 int i; 353 size_t total_used = 0U; 354 size_t total_free = 0U; 355 size_t total_waste = 0U; 356 357 /* Per pool highwater used count, useful to checking if a pool is 358 * too small. 359 */ 360 for (i = 0; i < g->num_pools; i++) { 361 duk_pool_state *s = &g->states[i]; 362 duk_pool_stats stats; 363 364 duk_alloc_pool_get_pool_stats(s, &stats); 365 if (stats.used_count > s->hwm_used_count) { 366 #if defined(DUK_ALLOC_POOL_DEBUG) 367 duk__alloc_pool_dprintf("duk__alloc_pool_update_highwater: pool %ld (%ld bytes) highwater updated: count %ld -> %ld\n", 368 (long) i, (long) s->size, 369 (long) s->hwm_used_count, (long) stats.used_count); 370 #endif 371 s->hwm_used_count = stats.used_count; 372 } 373 374 total_used += stats.used_bytes; 375 total_free += stats.free_bytes; 376 total_waste += stats.waste_bytes; 377 } 378 379 /* Global highwater mark for used and waste bytes. Both fields are 380 * updated from the same snapshot based on highest used count. 381 * This is VERY, VERY slow and only useful for development. 382 * (Note that updating HWM states for pools individually and then 383 * summing them won't create a consistent global snapshot. There 384 * are still easy ways to make this much, much faster.) 385 */ 386 if (total_used > g->hwm_used_bytes) { 387 #if defined(DUK_ALLOC_POOL_DEBUG) 388 duk__alloc_pool_dprintf("duk__alloc_pool_update_highwater: global highwater updated: used=%ld, bytes=%ld -> " 389 "used=%ld, bytes=%ld\n", 390 (long) g->hwm_used_bytes, (long) g->hwm_waste_bytes, 391 (long) total_used, (long) total_waste); 392 #endif 393 g->hwm_used_bytes = total_used; 394 g->hwm_waste_bytes = total_waste; 395 } 396 } 397 #else /* DUK_ALLOC_POOL_TRACK_HIGHWATER */ 398 static void duk__alloc_pool_update_highwater(duk_pool_global *g) { 399 (void) g; 400 } 401 #endif /* DUK_ALLOC_POOL_TRACK_HIGHWATER */ 402 403 /* 404 * Allocation providers 405 */ 406 407 void *duk_alloc_pool(void *udata, duk_size_t size) { 408 duk_pool_global *g = (duk_pool_global *) udata; 409 int i, n; 410 411 #if defined(DUK_ALLOC_POOL_DEBUG) 412 duk__alloc_pool_dprintf("duk_alloc_pool: %p %ld\n", udata, (long) size); 413 #endif 414 415 if (size == 0) { 416 return NULL; 417 } 418 419 for (i = 0, n = g->num_pools; i < n; i++) { 420 duk_pool_state *st = g->states + i; 421 422 if (size <= st->size) { 423 duk_pool_free *res = st->first; 424 if (res != NULL) { 425 st->first = res->next; 426 duk__alloc_pool_set_waste_marker((void *) res, size, st->size); 427 duk__alloc_pool_update_highwater(g); 428 return (void *) res; 429 } 430 } 431 432 /* Allocation doesn't fit or no free entries, try to borrow 433 * from the next block size. There's no support for preventing 434 * a borrow at present. 435 */ 436 } 437 438 return NULL; 439 } 440 441 void *duk_realloc_pool(void *udata, void *ptr, duk_size_t size) { 442 duk_pool_global *g = (duk_pool_global *) udata; 443 int i, j, n; 444 445 #if defined(DUK_ALLOC_POOL_DEBUG) 446 duk__alloc_pool_dprintf("duk_realloc_pool: %p %p %ld\n", udata, ptr, (long) size); 447 #endif 448 449 if (ptr == NULL) { 450 return duk_alloc_pool(udata, size); 451 } 452 if (size == 0) { 453 duk_free_pool(udata, ptr); 454 return NULL; 455 } 456 457 /* Non-NULL pointers are necessarily from the pool so we should 458 * always be able to find the allocation. 459 */ 460 461 for (i = 0, n = g->num_pools; i < n; i++) { 462 duk_pool_state *st = g->states + i; 463 char *new_ptr; 464 465 /* Because 'ptr' is assumed to be in the pool and pools are 466 * allocated in sequence, it suffices to check for end pointer 467 * only. 468 */ 469 if ((char *) ptr >= st->alloc_end) { 470 continue; 471 } 472 473 if (size <= st->size) { 474 /* Allocation still fits existing allocation. Check if 475 * we can shrink the allocation to a smaller block size 476 * (smallest possible). 477 */ 478 for (j = 0; j < i; j++) { 479 duk_pool_state *st2 = g->states + j; 480 481 if (size <= st2->size) { 482 new_ptr = (char *) st2->first; 483 if (new_ptr != NULL) { 484 #if defined(DUK_ALLOC_POOL_DEBUG) 485 duk__alloc_pool_dprintf("duk_realloc_pool: shrink, block size %ld -> %ld\n", 486 (long) st->size, (long) st2->size); 487 #endif 488 st2->first = ((duk_pool_free *) new_ptr)->next; 489 memcpy((void *) new_ptr, (const void *) ptr, (size_t) size); 490 ((duk_pool_free *) ptr)->next = st->first; 491 st->first = (duk_pool_free *) ptr; 492 duk__alloc_pool_set_waste_marker((void *) new_ptr, size, st2->size); 493 duk__alloc_pool_update_highwater(g); 494 return (void *) new_ptr; 495 } 496 } 497 } 498 499 /* Failed to shrink; return existing pointer. */ 500 duk__alloc_pool_set_waste_marker((void *) ptr, size, st->size); 501 return ptr; 502 } 503 504 /* Find first free larger block. */ 505 for (j = i + 1; j < n; j++) { 506 duk_pool_state *st2 = g->states + j; 507 508 if (size <= st2->size) { 509 new_ptr = (char *) st2->first; 510 if (new_ptr != NULL) { 511 st2->first = ((duk_pool_free *) new_ptr)->next; 512 memcpy((void *) new_ptr, (const void *) ptr, (size_t) st->size); 513 ((duk_pool_free *) ptr)->next = st->first; 514 st->first = (duk_pool_free *) ptr; 515 duk__alloc_pool_set_waste_marker((void *) new_ptr, size, st2->size); 516 duk__alloc_pool_update_highwater(g); 517 return (void *) new_ptr; 518 } 519 } 520 } 521 522 /* Failed to resize. */ 523 return NULL; 524 } 525 526 /* We should never be here because 'ptr' should be a valid pool 527 * entry and thus always found above. 528 */ 529 return NULL; 530 } 531 532 void duk_free_pool(void *udata, void *ptr) { 533 duk_pool_global *g = (duk_pool_global *) udata; 534 int i, n; 535 536 #if defined(DUK_ALLOC_POOL_DEBUG) 537 duk__alloc_pool_dprintf("duk_free_pool: %p %p\n", udata, ptr); 538 #endif 539 540 if (ptr == NULL) { 541 return; 542 } 543 544 for (i = 0, n = g->num_pools; i < n; i++) { 545 duk_pool_state *st = g->states + i; 546 547 /* Enough to check end address only. */ 548 if ((char *) ptr >= st->alloc_end) { 549 continue; 550 } 551 552 ((duk_pool_free *) ptr)->next = st->first; 553 st->first = (duk_pool_free *) ptr; 554 #if 0 /* never necessary when freeing */ 555 duk__alloc_pool_update_highwater(g); 556 #endif 557 return; 558 } 559 560 /* We should never be here because 'ptr' should be a valid pool 561 * entry and thus always found above. 562 */ 563 } 564 565 /* 566 * Pointer compression 567 */ 568 569 #if defined(DUK_ALLOC_POOL_ROMPTR_COMPRESSION) 570 static void duk__alloc_pool_romptr_init(void) { 571 /* Scan ROM pointer range for faster detection of "is 'p' a ROM pointer" 572 * later on. 573 */ 574 const void * const * ptrs = (const void * const *) duk_rom_compressed_pointers; 575 duk_alloc_pool_romptr_low = duk_alloc_pool_romptr_high = (const void *) *ptrs; 576 while (*ptrs) { 577 if (*ptrs > duk_alloc_pool_romptr_high) { 578 duk_alloc_pool_romptr_high = (const void *) *ptrs; 579 } 580 if (*ptrs < duk_alloc_pool_romptr_low) { 581 duk_alloc_pool_romptr_low = (const void *) *ptrs; 582 } 583 ptrs++; 584 } 585 } 586 #endif 587 588 /* Encode/decode functions are defined in the header to allow inlining. */ 589 590 #if defined(DUK_ALLOC_POOL_ROMPTR_COMPRESSION) 591 duk_uint16_t duk_alloc_pool_enc16_rom(void *ptr) { 592 /* The if-condition should be the fastest possible check 593 * for "is 'ptr' in ROM?". If pointer is in ROM, we'd like 594 * to compress it quickly. Here we just scan a ~1K array 595 * which is very bad for performance. 596 */ 597 const void * const * ptrs = duk_rom_compressed_pointers; 598 while (*ptrs) { 599 if (*ptrs == ptr) { 600 return DUK_ALLOC_POOL_ROMPTR_FIRST + (duk_uint16_t) (ptrs - duk_rom_compressed_pointers); 601 } 602 ptrs++; 603 } 604 605 /* We should really never be here: Duktape should only be 606 * compressing pointers which are in the ROM compressed 607 * pointers list, which are known at 'make dist' time. 608 * We go on, causing a pointer compression error. 609 */ 610 return 0; 611 } 612 #endif 613