102 Dalmatians: Puppies to the Rescue
Decompilation Source Reference | GitLab repository
Loading...
Searching...
No Matches
heap.c
Go to the documentation of this file.
1/* Recovered game implementation; original addresses identify provenance. */
8#include <intrin.h>
9#include <math.h>
10#include <stdarg.h>
11#include <string.h>
12#define nullptr 0
13
14// Original pcdogs.exe: 0x4465d4
15// Allocates memory using the configured CRT new-handler mode.
16void *CRT_malloc(uint32_t size)
17{
18 return __nh_malloc(size, g_crtDllMain);
19}
20
21// Original pcdogs.exe: 0x4465e6
22// Allocates a supported-size block and retries through the new handler when that mode is enabled. Requests above the CRT size limit fail.
23void *__nh_malloc(uint32_t size, int32_t new_mode)
24{
25 if (size <= CRT_HEAP_MAX_REQUEST)
26 {
27 bool retry_requested;
28
29 do
30 {
31 void *result = _heap_alloc(size);
32
33 if (result || !new_mode)
34 return result;
35
36 retry_requested = CRT_callnewh(size);
37 } while (retry_requested);
38 }
39
40 return NULL;
41}
42
43// Original pcdogs.exe: 0x446612
44// Allocates from the small-block heap when eligible and otherwise uses the Windows heap. Zero-sized requests receive a minimum allocation and sizes follow the CRT's alignment rules.
45void *_heap_alloc(uint32_t size)
46{
47 uint32_t effective_size = size;
48
49 if (effective_size <= g_smallBlockAllocThreshold)
50 {
51 void *result = __sbh_alloc_block(effective_size);
52
53 if (result)
54 return result;
55 }
56
57 if (!effective_size)
58 effective_size = 1;
59
60 return HeapAlloc(g_crtHeapHandle, 0, (effective_size + 0xf) & (~CRT_HEAP_ALIGNMENT_MASK));
61}
62
63// Original pcdogs.exe: 0x446aa6
64// Resizes an allocation in place when possible or allocates and copies a replacement, retrying through the configured new handler. A NULL pointer allocates a new block, and a zero size frees an existing block.
65void *CRT_realloc(void *ptr, uint32_t size)
66{
67 char *old_allocation = ptr;
68
69 if (!old_allocation)
70 return CRT_malloc(size);
71
72 uint32_t requested_size = size;
73
74 if (!requested_size)
75 {
76 CRT_free(old_allocation);
77
78 return nullptr;
79 }
80
81 bool retry_requested;
82
83 do
84 {
85 char *result = nullptr;
86
87 if (requested_size > CRT_HEAP_MAX_REQUEST)
88 {
89 if (!g_crtDllMain)
90 return result;
91 }
92 else
93 {
94 struct CRT_HeapSegment *segment = __sbh_find_block(old_allocation);
95
96 if (!segment)
97 {
98 if (!requested_size)
99 requested_size = 1;
100
101 requested_size = (requested_size + 0xf) & (~CRT_HEAP_ALIGNMENT_MASK);
102 result = HeapReAlloc(g_crtHeapHandle, 0, old_allocation, requested_size);
103 }
104 else
105 {
106 if (requested_size <= g_smallBlockAllocThreshold)
107 {
108 if (!__sbh_resize_block(segment, old_allocation, requested_size))
109 {
110 result = __sbh_alloc_block(requested_size);
111
112 if (result)
113 {
114 uint32_t count = ((struct CRT_HeapBoundaryTag *)old_allocation)[-1].size_flags - CRT_HEAP_BLOCK_ALLOCATED;
115
116 if (count >= requested_size)
117 count = requested_size;
118
119 CRT_MoveBytesOverlapSafe(result, old_allocation, count);
120 __sbh_free_block(segment, old_allocation);
121
122 return result;
123 }
124 }
125 else
126 {
127 result = old_allocation;
128
129 if (result)
130 return result;
131 }
132 }
133
134 if (!requested_size)
135 requested_size = 1;
136
137 requested_size = (requested_size + 0xf) & (~CRT_HEAP_ALIGNMENT_MASK);
138 result = HeapAlloc(g_crtHeapHandle, 0, requested_size);
139
140 if (result)
141 {
142 uint32_t heap_copy_bytes = ((struct CRT_HeapBoundaryTag *)old_allocation)[-1].size_flags - CRT_HEAP_BLOCK_ALLOCATED;
143
144 if (heap_copy_bytes >= requested_size)
145 heap_copy_bytes = requested_size;
146
147 CRT_MoveBytesOverlapSafe(result, old_allocation, heap_copy_bytes);
148 __sbh_free_block(segment, old_allocation);
149 }
150 }
151
152 if (result || !g_crtDllMain)
153 return result;
154 }
155
156 retry_requested = CRT_callnewh(requested_size);
157 } while (retry_requested);
158
159 return nullptr;
160}
161
162// Original pcdogs.exe: 0x446bc6
163// Releases an allocation through the small-block heap or the Windows heap. A NULL pointer has no effect.
164void CRT_free(void *ptr)
165{
166 if (!ptr)
167 return;
168
169 struct CRT_HeapSegment *segment = __sbh_find_block(ptr);
170
171 // Found in heap segment - use small block allocator CRT_free
172 if (segment)
173 {
174 __sbh_free_block(segment, ptr);
175
176 return;
177 }
178
180}
181
182// Original pcdogs.exe: 0x4482c3
183// Returns the usable allocation size from a small-block boundary tag or the Windows heap.
184uint32_t CRT_msize(void *ptr)
185{
186 if (!__sbh_find_block(ptr))
187 return HeapSize(g_crtHeapHandle, 0, ptr);
188
189 return ((struct CRT_HeapBoundaryTag *)ptr)[-1].size_flags - 9;
190}
191
192// Original pcdogs.exe: 0x4484d4
193// Invokes the installed new handler with the requested size and reports whether allocation should be retried. It returns false when no handler is installed.
194int32_t CRT_callnewh(uint32_t size)
195{
196 int32_t new_handler_address = g_crtFiberContext;
197
198 return (new_handler_address && ((int (*)(uint32_t))(uintptr_t)new_handler_address)(size));
199}
200
201// Original pcdogs.exe: 0x4484ef
202// Creates the Windows heap and initializes small-block heap metadata. If metadata initialization fails, it destroys the newly created heap.
203int32_t _heap_init(int32_t mt_flag)
204{
205 HEAP_FLAGS fl_options = !mt_flag;
206 HANDLE heap_handle = HeapCreate(fl_options, CRT_OS_PAGE_BYTES, 0);
207
208 g_crtHeapHandle = heap_handle;
209
210 if (heap_handle)
211 {
212 if (__sbh_heap_init())
213 return 1;
214
215 HeapDestroy(g_crtHeapHandle);
216 }
217
218 return 0;
219}
220
221// Original pcdogs.exe: 0x44852b
222// Allocates the initial small-block region-header table and initializes its capacity and counters. The header allocation is not zero-initialized.
224{
225 struct CRT_HeapSegment *segment_table = HeapAlloc(g_crtHeapHandle, 0, 0x140);
226
227 g_heapSegments = segment_table;
228
229 if (!segment_table)
230 return (int32_t)(segment_table);
231
232 g_lastFreedSegment = nullptr;
234 g_cachedHeapSegment = segment_table;
235 g_heapMaxSegments = 0x10;
236
237 return 1;
238}
239
240// Original pcdogs.exe: 0x448569
241// Finds the small-block region containing an address and returns NULL when none matches. Region membership uses the original unsigned one-megabyte range check.
243{
244 // Check if past end of segment table - not found
245 for (struct CRT_HeapSegment *segment = g_heapSegments; segment < &g_heapSegments[g_heapSegmentCount];
246 segment = &segment[1])
247 {
248 // Check if address is within this 1MB segment (offset < CRT_HEAP_SEGMENT_BYTES)
249 // Found - return pointer to segment descriptor
250 // Not in this segment - advance to next (0x14 bytes per entry)
251 if ((uint32_t)((char *)ptr - (char *)segment->reserved_base) < CRT_HEAP_SEGMENT_BYTES)
252 return segment;
253 }
254
255 return NULL;
256}
257
258// Original pcdogs.exe: 0x448594
259// Frees and coalesces a small block while updating size-class lists and bitmaps. It retains one empty group, decommits the previously retained empty group, and releases a region when all its groups are free.
260void __sbh_free_block(struct CRT_HeapSegment *segment, void *user_ptr)
261{
262 struct CRT_HeapPageMap *page_map_local = segment->page_map;
263 // Calculate which 32KB page this block is in (for page-level tracking)
264 struct CRT_HeapFreeBlock *block_header = (struct CRT_HeapFreeBlock *)((char *)user_ptr - 4);
265 uint32_t page_index = ((uint8_t *)user_ptr - segment->reserved_base) >> CRT_HEAP_PAGE_SHIFT;
266 uint32_t free_size_class;
267 uint32_t prev_size_flags = ((struct CRT_HeapBoundaryTag *)block_header)[-1].size_flags;
268 // Check if next block is CRT_free (bit 0 clear) for forward coalescing
269 uint32_t next_size = ((struct CRT_HeapBoundaryTag *)user_ptr)[-1].size_flags - CRT_HEAP_BLOCK_ALLOCATED;
270 uint32_t merged_size = next_size;
271 struct CRT_HeapFreeBlock *next_block = (void *)((char *)block_header + next_size);
272 int32_t next_block_size = next_block->size_flags;
273
274 if (!((uint8_t)next_block_size & CRT_HEAP_BLOCK_ALLOCATED))
275 {
276 free_size_class = (next_block_size >> 4) - 1;
277
278 if ((next_block_size >> 4) - 1 > CRT_HEAP_LAST_CLASS)
279 free_size_class = CRT_HEAP_LAST_CLASS;
280
281 if (next_block->next == next_block->prev)
282 {
283 if (free_size_class >= CRT_HEAP_CLASS_BANK_SIZE)
284 {
285 uint32_t next_high_class_clear_mask = ~(CRT_HEAP_CLASS_FIRST_BIT >> (((uint8_t)free_size_class - CRT_HEAP_CLASS_BANK_SIZE) & CRT_HEAP_CLASS_INDEX_MASK));
286
287 page_map_local->high_class_bitmap_by_page[page_index] &= next_high_class_clear_mask;
288
289 char next_high_class_count = page_map_local->free_count_by_class[free_size_class];
290
291 page_map_local->free_count_by_class[free_size_class] -= 1;
292
293 if (next_high_class_count == 1)
294 segment->high_class_bitmap &= next_high_class_clear_mask;
295 }
296 else
297 {
298 uint32_t next_low_class_clear_mask = ~(CRT_HEAP_CLASS_FIRST_BIT >> ((uint8_t)free_size_class & CRT_HEAP_CLASS_INDEX_MASK));
299
300 page_map_local->low_class_bitmap_by_page[page_index] &= next_low_class_clear_mask;
301
302 char next_low_class_count = page_map_local->free_count_by_class[free_size_class];
303
304 page_map_local->free_count_by_class[free_size_class] -= 1;
305
306 if (next_low_class_count == 1)
307 segment->low_class_bitmap &= next_low_class_clear_mask;
308 }
309 }
310
311 next_block->prev->next = next_block->next;
312
313 // Remove next block from its CRT_free list and merge sizes
314 struct CRT_HeapFreeBlock *next_free_successor = next_block->next;
315 struct CRT_HeapFreeBlock *next_free_predecessor = next_block->prev;
316
317 next_size += next_block_size;
318 next_free_successor->prev = next_free_predecessor;
319 merged_size = next_size;
320 }
321
322 int32_t merged_size_class = (next_size >> 4) - 1;
323
324 if (merged_size_class > CRT_HEAP_LAST_CLASS)
325 merged_size_class = CRT_HEAP_LAST_CLASS;
326
327 int32_t previous_block_allocated = prev_size_flags & CRT_HEAP_BLOCK_ALLOCATED;
328
329 // Check if previous block is CRT_free (bit 0 of prev size clear) for backward coalescing
330 if (!previous_block_allocated)
331 {
332 // Previous block is CRT_free - adjust pointer backward and merge sizes
333 struct CRT_HeapFreeBlock *previous_block = (struct CRT_HeapFreeBlock *)((char *)block_header - prev_size_flags);
334
335 free_size_class = (prev_size_flags >> 4) - 1;
336
337 if (free_size_class > CRT_HEAP_LAST_CLASS)
338 {
339 free_size_class = CRT_HEAP_LAST_CLASS;
340 }
341
342 next_size += prev_size_flags;
343 merged_size = next_size;
344 merged_size_class = (next_size >> 4) - 1;
345
346 if (merged_size_class > CRT_HEAP_LAST_CLASS)
347 merged_size_class = CRT_HEAP_LAST_CLASS;
348
349 if (free_size_class != (uint32_t)merged_size_class)
350 {
351 if (previous_block->next == previous_block->prev)
352 {
353 if (free_size_class >= CRT_HEAP_CLASS_BANK_SIZE)
354 {
355 uint32_t previous_high_class_clear_mask = ~(CRT_HEAP_CLASS_FIRST_BIT >> (((uint8_t)free_size_class - CRT_HEAP_CLASS_BANK_SIZE) & CRT_HEAP_CLASS_INDEX_MASK));
356
357 page_map_local->high_class_bitmap_by_page[page_index] &= previous_high_class_clear_mask;
358
359 char previous_high_class_count = page_map_local->free_count_by_class[free_size_class];
360
361 page_map_local->free_count_by_class[free_size_class] -= 1;
362
363 if (previous_high_class_count == 1)
364 segment->high_class_bitmap &= previous_high_class_clear_mask;
365 }
366 else
367 {
368 uint32_t previous_low_class_clear_mask = ~(CRT_HEAP_CLASS_FIRST_BIT >> ((uint8_t)free_size_class & CRT_HEAP_CLASS_INDEX_MASK));
369
370 page_map_local->low_class_bitmap_by_page[page_index] &= previous_low_class_clear_mask;
371
372 char previous_low_class_count = page_map_local->free_count_by_class[free_size_class];
373
374 page_map_local->free_count_by_class[free_size_class] -= 1;
375
376 if (previous_low_class_count == 1)
377 segment->low_class_bitmap &= previous_low_class_clear_mask;
378 }
379 }
380
381 previous_block->prev->next = previous_block->next;
382 previous_block->next->prev = previous_block->prev;
383 }
384
385 block_header = previous_block;
386 }
387
388 if (previous_block_allocated || free_size_class != (uint32_t)merged_size_class)
389 {
390 block_header->next = page_map_local->pages[page_index].bins[merged_size_class].next;
391
392 struct CRT_HeapFreeBlock *merged_bin_sentinel = (void *)((char *)&page_map_local->pages[page_index].bins[merged_size_class] - 4);
393
394 block_header->prev = merged_bin_sentinel;
395 merged_bin_sentinel->next = block_header;
396 block_header->next->prev = block_header;
397
398 if (block_header->next == block_header->prev)
399 {
400 char merged_class_count = page_map_local->free_count_by_class[merged_size_class];
401
402 page_map_local->free_count_by_class[merged_size_class] = merged_class_count + 1;
403
404 if (merged_size_class >= CRT_HEAP_CLASS_BANK_SIZE)
405 {
406 if (!merged_class_count)
408
409 page_map_local->high_class_bitmap_by_page[page_index] |=
411 }
412 else
413 {
414 if (!merged_class_count)
415 segment->low_class_bitmap |= CRT_HEAP_CLASS_FIRST_BIT >> ((uint8_t)merged_size_class & CRT_HEAP_CLASS_INDEX_MASK);
416
417 page_map_local->low_class_bitmap_by_page[page_index] |=
418 CRT_HEAP_CLASS_FIRST_BIT >> ((uint8_t)merged_size_class & CRT_HEAP_CLASS_INDEX_MASK);
419 }
420
421 next_size = merged_size;
422 }
423 }
424
425 block_header->size_flags = next_size;
426 *(uint32_t *)(next_size + (char *)block_header - 4) = next_size;
427
428 int32_t allocated_count = page_map_local->pages[page_index].allocated_count;
429
430 page_map_local->pages[page_index].allocated_count -= 1;
431
432 if (allocated_count != 1)
433 return;
434
435 struct CRT_HeapSegment *pending_empty_segment = g_lastFreedSegment;
436 struct CRT_HeapSegment *release_candidate;
437
438 if (pending_empty_segment)
439 {
440 VirtualFree(&pending_empty_segment->reserved_base[g_lastFreedPageIndex << CRT_HEAP_PAGE_SHIFT], CRT_HEAP_PAGE_BYTES,
442
443 struct CRT_HeapSegment *decommitted_segment = g_lastFreedSegment;
444
446 g_lastFreedSegment->page_map->high_class_bitmap_by_page[g_lastFreedPageIndex] = 0;
447
448 struct CRT_HeapPageMap *page_map = g_lastFreedSegment->page_map;
449
451 release_candidate = g_lastFreedSegment;
452
453 if (!release_candidate->page_map->free_count_by_class[CRT_HEAP_LAST_CLASS])
454 {
455 release_candidate->high_class_bitmap &= ~CRT_HEAP_CLASS_LAST_BIT;
456 release_candidate = g_lastFreedSegment;
457 }
458 }
459
460 struct CRT_HeapSegment *remaining_segment;
461
462 if (!pending_empty_segment || release_candidate->free_page_bitmap != 0xffffffff)
463 remaining_segment = segment;
464 else
465 {
466 VirtualFree(release_candidate->reserved_base, 0, MEM_RELEASE);
468
469 struct CRT_HeapSegment *removed_segment = g_lastFreedSegment;
470
471 CRT_MoveBytesOverlapSafeDuplicate(removed_segment, &removed_segment[1],
472 (g_heapSegmentCount - (removed_segment - g_heapSegments) - 1) * 20);
473 remaining_segment = segment;
475
476 if (remaining_segment > g_lastFreedSegment)
477 remaining_segment -= 1;
478
480 }
481
482 g_lastFreedSegment = remaining_segment;
483 g_lastFreedPageIndex = page_index;
484}
485
486// Original pcdogs.exe: 0x4488bf
487// Allocates and splits a suitable small block using the size-class lists, boundary tags, and allocation bitmaps.
488void *__sbh_alloc_block(uint32_t size)
489{
490 struct CRT_HeapSegment *segments = g_heapSegments;
491 struct CRT_HeapSegment *end_segment = &segments[g_heapSegmentCount];
492 uint32_t rounded_size = (size + 0x17) & (~CRT_HEAP_ALIGNMENT_MASK);
493 uint32_t high_class_mask;
494 uint32_t low_class_mask;
495
496 if ((rounded_size >> 4) - 1 >= CRT_HEAP_CLASS_BANK_SIZE)
497 {
498 low_class_mask = 0;
499 high_class_mask = UINT32_MAX >> ((((rounded_size >> 4) - 1) - CRT_HEAP_CLASS_BANK_SIZE) & CRT_HEAP_CLASS_INDEX_MASK);
500 }
501 else
502 {
503 low_class_mask = UINT32_MAX >> (((rounded_size >> 4) - 1) & CRT_HEAP_CLASS_INDEX_MASK);
504 high_class_mask = 0xffffffff;
505 }
506
507 struct CRT_HeapSegment *cached_segment = g_cachedHeapSegment;
508 struct CRT_HeapSegment *segment = cached_segment;
509
510 if (segment < end_segment)
511 {
512 while (!((segment->high_class_bitmap & high_class_mask) | (segment->low_class_bitmap & low_class_mask)))
513 {
514 segment = &segment[1];
515
516 if (segment >= end_segment)
517 break;
518 }
519 }
520
521 if (segment == end_segment)
522 {
523 segment = segments;
524
525 bool found_wrapped_class;
526
527 while (true)
528 {
529 found_wrapped_class = segment != cached_segment;
530
531 if (segment >= cached_segment)
532 break;
533
534 if ((segment->high_class_bitmap & high_class_mask) | (segment->low_class_bitmap & low_class_mask))
535 {
536 found_wrapped_class = segment != cached_segment;
537
538 break;
539 }
540
541 segment = &segment[1];
542 }
543
544 if (!found_wrapped_class)
545 {
546 bool found_free_page;
547
548 while (true)
549 {
550 found_free_page = segment != end_segment;
551
552 if (segment >= end_segment)
553 break;
554
555 if (segment->free_page_bitmap)
556 {
557 found_free_page = segment != end_segment;
558
559 break;
560 }
561
562 segment = &segment[1];
563 }
564
565 if (!found_free_page)
566 {
567 segment = segments;
568
569 bool found_wrapped_free_page;
570
571 while (true)
572 {
573 found_wrapped_free_page = segment != cached_segment;
574
575 if (segment >= cached_segment)
576 break;
577
578 if (segment->free_page_bitmap)
579 {
580 found_wrapped_free_page = segment != cached_segment;
581
582 break;
583 }
584
585 segment = &segment[1];
586 }
587
588 if (!found_wrapped_free_page)
589 {
590 segment = __sbh_alloc_new_region();
591
592 if (!segment)
593 return nullptr;
594 }
595 }
596
598
599 if (segment->page_map->current_page_index == -1)
600 return nullptr;
601 }
602 }
603
604 g_cachedHeapSegment = segment;
605
606 struct CRT_HeapPageMap *page_map = segment->page_map;
607 int32_t page_index = page_map->current_page_index;
608 int32_t selected_page = page_index;
609
610 if (page_index == -1 || !((page_map->high_class_bitmap_by_page[page_index] & high_class_mask) | (page_map->low_class_bitmap_by_page[page_index] & low_class_mask)))
611 {
612 selected_page = 0;
613
614 if (!((page_map->high_class_bitmap_by_page[0] & high_class_mask) | (page_map->low_class_bitmap_by_page[0] & low_class_mask)))
615 {
616 uint32_t eligible_high_classes;
617
618 do
619 {
620 selected_page += 1;
621 eligible_high_classes = page_map->high_class_bitmap_by_page[selected_page] & high_class_mask;
622 } while (!(eligible_high_classes | (low_class_mask & page_map->low_class_bitmap_by_page[selected_page])));
623 }
624
625 page_index = selected_page;
626 }
627
628 int32_t size_class = 0;
629 uint32_t eligible_class_bits = page_map->low_class_bitmap_by_page[page_index] & low_class_mask;
630
631 if (!eligible_class_bits)
632 {
633 eligible_class_bits = page_map->high_class_bitmap_by_page[page_index] & high_class_mask;
634 size_class = CRT_HEAP_CLASS_BANK_SIZE;
635 }
636
637 while (!(eligible_class_bits & CRT_HEAP_CLASS_FIRST_BIT))
638 {
639 eligible_class_bits <<= 1;
640 size_class += 1;
641 }
642
643 struct CRT_HeapFreeBlock *free_block =
644 page_map->pages[page_index].bins[size_class].next;
645 uint32_t remainder_bytes = free_block->size_flags - rounded_size;
646 int32_t remainder_class = (remainder_bytes >> 4) - 1;
647
648 if (remainder_class > CRT_HEAP_LAST_CLASS)
649 remainder_class = CRT_HEAP_LAST_CLASS;
650
651 if (remainder_class != size_class)
652 {
653 if (free_block->next == free_block->prev)
654 {
655 if (size_class >= CRT_HEAP_CLASS_BANK_SIZE)
656 {
657 uint32_t high_class_clear_mask = ~(CRT_HEAP_CLASS_FIRST_BIT >> (((uint8_t)size_class - CRT_HEAP_CLASS_BANK_SIZE) & CRT_HEAP_CLASS_INDEX_MASK));
658
659 page_map->high_class_bitmap_by_page[selected_page] &= high_class_clear_mask;
660
661 char previous_high_class_count = page_map->free_count_by_class[size_class];
662
663 page_map->free_count_by_class[size_class] -= 1;
664
665 if (previous_high_class_count == 1)
666 segment->high_class_bitmap &= high_class_clear_mask;
667 }
668 else
669 {
670 uint32_t low_class_clear_mask = ~(CRT_HEAP_CLASS_FIRST_BIT >> ((uint8_t)size_class & CRT_HEAP_CLASS_INDEX_MASK));
671
672 page_map->low_class_bitmap_by_page[selected_page] &= low_class_clear_mask;
673
674 char previous_low_class_count = page_map->free_count_by_class[size_class];
675
676 page_map->free_count_by_class[size_class] -= 1;
677
678 if (previous_low_class_count == 1)
679 segment->low_class_bitmap &= low_class_clear_mask;
680 }
681 }
682
683 free_block->prev->next = free_block->next;
684 free_block->next->prev = free_block->prev;
685
686 if (remainder_bytes)
687 {
688 struct CRT_HeapFreeBlock *remainder_bin_sentinel = (struct CRT_HeapFreeBlock *)((int32_t)&page_map->pages[page_index] + remainder_class * 8);
689
690 free_block->next = page_map->pages[page_index].bins[remainder_class].next;
691 free_block->prev = remainder_bin_sentinel;
692 remainder_bin_sentinel->next = free_block;
693 free_block->next->prev = free_block;
694
695 if (free_block->next == free_block->prev)
696 {
697 char previous_remainder_class_count = page_map->free_count_by_class[remainder_class];
698
699 if (remainder_class >= CRT_HEAP_CLASS_BANK_SIZE)
700 {
701 page_map->free_count_by_class[remainder_class] = previous_remainder_class_count + 1;
702
703 if (!previous_remainder_class_count)
705
706 page_map->high_class_bitmap_by_page[selected_page] |=
708 }
709 else
710 {
711 page_map->free_count_by_class[remainder_class] = previous_remainder_class_count + 1;
712
713 if (!previous_remainder_class_count)
714 segment->low_class_bitmap |= CRT_HEAP_CLASS_FIRST_BIT >> ((uint8_t)remainder_class & CRT_HEAP_CLASS_INDEX_MASK);
715
716 page_map->low_class_bitmap_by_page[selected_page] |=
717 CRT_HEAP_CLASS_FIRST_BIT >> ((uint8_t)remainder_class & CRT_HEAP_CLASS_INDEX_MASK);
718 }
719 }
720 }
721 }
722
723 if (remainder_bytes)
724 {
725 free_block->size_flags = remainder_bytes;
726 *(uint32_t *)(remainder_bytes + (char *)free_block - 4) = remainder_bytes;
727 }
728
729 struct CRT_HeapFreeBlock *alloc_header = (struct CRT_HeapFreeBlock *)((char *)free_block + remainder_bytes);
730
731 alloc_header->size_flags = rounded_size | CRT_HEAP_BLOCK_ALLOCATED;
732 *(uint32_t *)((char *)alloc_header + rounded_size - 4) = rounded_size | CRT_HEAP_BLOCK_ALLOCATED;
733
734 int32_t allocated_count = page_map->pages[page_index].allocated_count;
735
736 page_map->pages[page_index].allocated_count = allocated_count + 1;
737
738 if (!allocated_count && segment == g_lastFreedSegment && selected_page == g_lastFreedPageIndex)
739 g_lastFreedSegment = nullptr;
740
741 page_map->current_page_index = selected_page;
742
743 return &alloc_header->next;
744}
745
746// Original pcdogs.exe: 0x448bc8
747// Adds a small-block heap region, growing the region-header table when necessary and reserving its virtual address range. A failed virtual-address reservation releases the newly allocated page map.
749{
750 int32_t segment_count = g_heapSegmentCount;
751 int32_t max_segments = g_heapMaxSegments;
752
753 if (segment_count == max_segments)
754 {
755 struct CRT_HeapSegment *resized_segment_table =
756 HeapReAlloc(g_crtHeapHandle, 0, g_heapSegments, (max_segments * 5 + 0x50) << 2);
757
758 if (!resized_segment_table)
759 return nullptr;
760
761 g_heapMaxSegments += 0x10;
762 g_heapSegments = resized_segment_table;
763 segment_count = g_heapSegmentCount;
764 }
765
766 struct CRT_HeapSegment *segment = &g_heapSegments[segment_count];
767 struct CRT_HeapPageMap *page_map = HeapAlloc(g_crtHeapHandle, HEAP_ZERO_MEMORY, 0x41c4);
768
769 segment->page_map = page_map;
770
771 if (page_map)
772 {
773 void *reserved_base = VirtualAlloc(nullptr, CRT_HEAP_SEGMENT_BYTES, MEM_RESERVE, PAGE_READWRITE);
774
775 segment->reserved_base = reserved_base;
776
777 if (reserved_base)
778 {
779 segment->free_page_bitmap = 0xffffffff;
780 segment->low_class_bitmap = 0;
781 segment->high_class_bitmap = 0;
783 segment->page_map->current_page_index = 0xffffffff;
784
785 return segment;
786 }
787
789 }
790
791 return nullptr;
792}
793
794// Original pcdogs.exe: 0x448c79
795// Commits an available small-block group and initializes its page sentinels and free lists. It returns the group index or -1 when no group can be committed.
797{
798 struct CRT_HeapPageMap *map = segment->page_map;
799
800 unsigned index = 0;
801
802 uint32_t bits = segment->free_page_bitmap;
803
804 while (!(bits & CRT_HEAP_CLASS_FIRST_BIT))
805 {
806 bits <<= 1;
807 ++index;
808 }
809
810 struct CRT_HeapPageState *page = &map->pages[index];
811
812 for (unsigned i = 0; i < 63; ++i)
813 {
814 struct CRT_HeapFreeBlock *head = (void *)((char *)&page->bins[i] - 4);
815
816 page->bins[i].next = head;
817 page->bins[i].prev = head;
818 }
819
820 uint8_t *base = segment->reserved_base + (index << 15);
821
822 if (!VirtualAlloc(base, CRT_HEAP_PAGE_BYTES, MEM_COMMIT, PAGE_READWRITE))
823 return -1;
824
825 for (unsigned off = 0; off < CRT_HEAP_PAGE_BYTES; off += CRT_OS_PAGE_BYTES)
826 {
827 struct CRT_HeapFreeBlock *block = (void *)(base + off + 12);
828
829 *(uint32_t *)(base + off + 8) = 0xffffffff;
830 block->size_flags = 0xff0;
831 block->next = (void *)((char *)block + CRT_OS_PAGE_BYTES);
832 block->prev = (void *)((char *)block - CRT_OS_PAGE_BYTES);
833 *(uint32_t *)(base + off + 0xff8) = 0xff0;
834 *(uint32_t *)(base + off + 0xffc) = 0xffffffff;
835 }
836
837 struct CRT_HeapFreeBlock *head = (void *)((char *)&page->bins[63] - 4);
838
839 page->bins[63].next = (void *)(base + 12);
840 page->bins[63].prev = (void *)(base + 0x700c);
841 page->bins[63].next->prev = head;
842 page->bins[63].prev->next = head;
843 map->low_class_bitmap_by_page[index] = 0;
844 map->high_class_bitmap_by_page[index] = 1;
845
846 if (!map->free_count_by_class[63]++)
848
849 segment->free_page_bitmap &= ~(CRT_HEAP_CLASS_FIRST_BIT >> index);
850
851 return index;
852}
853
854// Original pcdogs.exe: 0x448d74
855// Resizes a small block without moving its payload, growing into an adjacent free block or splitting and coalescing a shrinking tail. It reports whether the requested resize succeeded.
856int32_t __sbh_resize_block(struct CRT_HeapSegment *segment, void *user_ptr, uint32_t new_size)
857{
858 struct CRT_HeapPageMap *page_map = segment->page_map;
859 uint32_t rounded_new_size = (new_size + 0x17) & (~CRT_HEAP_ALIGNMENT_MASK);
860 uint32_t page_index = ((char *)user_ptr - (char *)segment->reserved_base) >> CRT_HEAP_PAGE_SHIFT;
861 uint32_t old_block_size = ((struct CRT_HeapBoundaryTag *)user_ptr)[-1].size_flags - CRT_HEAP_BLOCK_ALLOCATED;
862 struct CRT_HeapFreeBlock *block_header = (void *)((char *)user_ptr + old_block_size - sizeof(uint32_t));
863 int32_t next_block_size_flags = block_header->size_flags;
864
865 if (rounded_new_size > old_block_size)
866 {
867 if ((uint8_t)next_block_size_flags & CRT_HEAP_BLOCK_ALLOCATED || rounded_new_size > next_block_size_flags + old_block_size)
868 return 0;
869
870 int32_t next_size_class = (next_block_size_flags >> 4) - 1;
871
872 if (next_size_class > CRT_HEAP_LAST_CLASS)
873 {
874 next_size_class = CRT_HEAP_LAST_CLASS;
875 }
876
877 if (block_header->next == block_header->prev)
878 {
879 if (next_size_class >= CRT_HEAP_CLASS_BANK_SIZE)
880 {
881 uint32_t grow_high_class_clear_mask = ~(CRT_HEAP_CLASS_FIRST_BIT >> (((uint8_t)next_size_class - CRT_HEAP_CLASS_BANK_SIZE) & CRT_HEAP_CLASS_INDEX_MASK));
882
883 page_map->high_class_bitmap_by_page[page_index] &= grow_high_class_clear_mask;
884
885 char grow_high_class_count = page_map->free_count_by_class[next_size_class];
886
887 page_map->free_count_by_class[next_size_class] -= 1;
888
889 if (grow_high_class_count == 1)
890 segment->high_class_bitmap &= grow_high_class_clear_mask;
891 }
892 else
893 {
894 uint32_t grow_low_class_clear_mask = ~(CRT_HEAP_CLASS_FIRST_BIT >> ((uint8_t)next_size_class & CRT_HEAP_CLASS_INDEX_MASK));
895
896 page_map->low_class_bitmap_by_page[page_index] &= grow_low_class_clear_mask;
897
898 char grow_low_class_count = page_map->free_count_by_class[next_size_class];
899
900 page_map->free_count_by_class[next_size_class] -= 1;
901
902 if (grow_low_class_count == 1)
903 segment->low_class_bitmap &= grow_low_class_clear_mask;
904 }
905 }
906
907 block_header->prev->next = block_header->next;
908 block_header->next->prev = block_header->prev;
909
910 int32_t grow_remainder_bytes = next_block_size_flags + old_block_size - rounded_new_size;
911 void *grown_user_pointer;
912
913 if (grow_remainder_bytes <= 0)
914 grown_user_pointer = user_ptr;
915 else
916 {
917 int32_t grow_remainder_class = (grow_remainder_bytes >> 4) - 1;
918
919 if (grow_remainder_class > CRT_HEAP_LAST_CLASS)
920 grow_remainder_class = CRT_HEAP_LAST_CLASS;
921
922 struct CRT_HeapFreeBlock *grow_bin_sentinel = (void *)((char *)&page_map->pages[page_index].bins[grow_remainder_class] - sizeof(uint32_t));
923 struct CRT_HeapFreeBlock *grow_remainder = (void *)((char *)user_ptr + rounded_new_size - sizeof(uint32_t));
924
925 grow_remainder->next = grow_bin_sentinel->next;
926 grow_remainder->prev = grow_bin_sentinel;
927 (grow_bin_sentinel)->next = grow_remainder;
928 grow_remainder->next->prev = grow_remainder;
929
930 if (grow_remainder->next == grow_remainder->prev)
931 {
932 char grow_remainder_class_count = page_map->free_count_by_class[grow_remainder_class];
933
934 page_map->free_count_by_class[grow_remainder_class] = grow_remainder_class_count + 1;
935
936 uint32_t *grow_page_bitmap;
937 char grow_class_bit;
938
939 if (grow_remainder_class >= CRT_HEAP_CLASS_BANK_SIZE)
940 {
941 if (!grow_remainder_class_count)
942 segment->high_class_bitmap |=
943 CRT_HEAP_CLASS_FIRST_BIT >> (((uint8_t)grow_remainder_class - CRT_HEAP_CLASS_BANK_SIZE) & CRT_HEAP_CLASS_INDEX_MASK);
944
945 grow_page_bitmap = &page_map->high_class_bitmap_by_page[page_index];
946 grow_class_bit = (uint8_t)grow_remainder_class - CRT_HEAP_CLASS_BANK_SIZE;
947 }
948 else
949 {
950 if (!grow_remainder_class_count)
951 segment->low_class_bitmap |= CRT_HEAP_CLASS_FIRST_BIT >> ((uint8_t)grow_remainder_class & CRT_HEAP_CLASS_INDEX_MASK);
952
953 grow_page_bitmap = &page_map->low_class_bitmap_by_page[page_index];
954 grow_class_bit = (uint8_t)grow_remainder_class;
955 }
956
957 *grow_page_bitmap |= CRT_HEAP_CLASS_FIRST_BIT >> (grow_class_bit & CRT_HEAP_CLASS_INDEX_MASK);
958 }
959
960 grown_user_pointer = user_ptr;
961 *(uint32_t *)((char *)grown_user_pointer + rounded_new_size - 4) = grow_remainder_bytes;
962 *(uint32_t *)(grow_remainder_bytes + (char *)grown_user_pointer + rounded_new_size - 4 - 4) = grow_remainder_bytes;
963 }
964
965 ((struct CRT_HeapBoundaryTag *)grown_user_pointer)[-1].size_flags = rounded_new_size | CRT_HEAP_BLOCK_ALLOCATED;
966 *(uint32_t *)((char *)grown_user_pointer + rounded_new_size - 8) = rounded_new_size | CRT_HEAP_BLOCK_ALLOCATED;
967 }
968 else if (rounded_new_size < old_block_size)
969 {
970 new_size = old_block_size - rounded_new_size;
971 ((struct CRT_HeapBoundaryTag *)user_ptr)[-1].size_flags = rounded_new_size | CRT_HEAP_BLOCK_ALLOCATED;
972
973 struct CRT_HeapFreeBlock *shrink_remainder_header = (void *)((char *)user_ptr + rounded_new_size - sizeof(uint32_t));
974
975 user_ptr = shrink_remainder_header;
976
977 int32_t shrink_remainder_class = (new_size >> 4) - 1;
978
979 ((struct CRT_HeapBoundaryTag *)shrink_remainder_header)[-1].size_flags = rounded_new_size | CRT_HEAP_BLOCK_ALLOCATED;
980
981 if (shrink_remainder_class > CRT_HEAP_LAST_CLASS)
982 shrink_remainder_class = CRT_HEAP_LAST_CLASS;
983
984 if (!((uint8_t)next_block_size_flags & CRT_HEAP_BLOCK_ALLOCATED))
985 {
986 int32_t shrink_next_class = (next_block_size_flags >> 4) - 1;
987
988 if (shrink_next_class > CRT_HEAP_LAST_CLASS)
989 shrink_next_class = CRT_HEAP_LAST_CLASS;
990
991 if (block_header->next == block_header->prev)
992 {
993 if (shrink_next_class >= CRT_HEAP_CLASS_BANK_SIZE)
994 {
995 uint32_t shrink_high_class_clear_mask = ~(CRT_HEAP_CLASS_FIRST_BIT >> (((uint8_t)shrink_next_class - CRT_HEAP_CLASS_BANK_SIZE) & CRT_HEAP_CLASS_INDEX_MASK));
996
997 page_map->high_class_bitmap_by_page[page_index] &= shrink_high_class_clear_mask;
998
999 char shrink_high_class_count = page_map->free_count_by_class[shrink_next_class];
1000
1001 page_map->free_count_by_class[shrink_next_class] -= 1;
1002
1003 if (shrink_high_class_count == 1)
1004 segment->high_class_bitmap &= shrink_high_class_clear_mask;
1005 }
1006 else
1007 {
1008 uint32_t shrink_low_class_clear_mask = ~(CRT_HEAP_CLASS_FIRST_BIT >> ((uint8_t)shrink_next_class & CRT_HEAP_CLASS_INDEX_MASK));
1009
1010 page_map->low_class_bitmap_by_page[page_index] &= shrink_low_class_clear_mask;
1011
1012 char shrink_low_class_count = page_map->free_count_by_class[shrink_next_class];
1013
1014 page_map->free_count_by_class[shrink_next_class] -= 1;
1015
1016 if (shrink_low_class_count == 1)
1017 segment->low_class_bitmap &= shrink_low_class_clear_mask;
1018 }
1019
1020 shrink_remainder_header = user_ptr;
1021 }
1022
1023 block_header->prev->next = block_header->next;
1024 block_header->next->prev = block_header->prev;
1025
1026 uint32_t coalesced_remainder_size = new_size + next_block_size_flags;
1027
1028 new_size = coalesced_remainder_size;
1029 shrink_remainder_class = (coalesced_remainder_size >> 4) - 1;
1030
1031 if (shrink_remainder_class > CRT_HEAP_LAST_CLASS)
1032 shrink_remainder_class = CRT_HEAP_LAST_CLASS;
1033 }
1034
1035 struct CRT_HeapFreeBlock *shrink_bin_sentinel = (void *)((char *)&page_map->pages[page_index].bins[shrink_remainder_class] - sizeof(uint32_t));
1036
1037 shrink_remainder_header->next = page_map->pages[page_index].bins[shrink_remainder_class].next;
1038 shrink_remainder_header->prev = shrink_bin_sentinel;
1039 shrink_bin_sentinel->next = shrink_remainder_header;
1040 shrink_remainder_header->next->prev = shrink_remainder_header;
1041
1042 if (shrink_remainder_header->next == shrink_remainder_header->prev)
1043 {
1044 char shrink_remainder_class_count = page_map->free_count_by_class[shrink_remainder_class];
1045
1046 page_map->free_count_by_class[shrink_remainder_class] = shrink_remainder_class_count + 1;
1047
1048 uint32_t *shrink_page_bitmap;
1049 char shrink_class_bit;
1050
1051 if (shrink_remainder_class >= CRT_HEAP_CLASS_BANK_SIZE)
1052 {
1053 if (!shrink_remainder_class_count)
1054 segment->high_class_bitmap |= CRT_HEAP_CLASS_FIRST_BIT >> (((uint8_t)shrink_remainder_class - CRT_HEAP_CLASS_BANK_SIZE) & CRT_HEAP_CLASS_INDEX_MASK);
1055
1056 shrink_page_bitmap = &page_map->high_class_bitmap_by_page[page_index];
1057 shrink_class_bit = (uint8_t)shrink_remainder_class - CRT_HEAP_CLASS_BANK_SIZE;
1058 }
1059 else
1060 {
1061 if (!shrink_remainder_class_count)
1062 segment->low_class_bitmap |= CRT_HEAP_CLASS_FIRST_BIT >> ((uint8_t)shrink_remainder_class & CRT_HEAP_CLASS_INDEX_MASK);
1063
1064 shrink_page_bitmap = &page_map->low_class_bitmap_by_page[page_index];
1065 shrink_class_bit = (uint8_t)shrink_remainder_class;
1066 }
1067
1068 *shrink_page_bitmap |= CRT_HEAP_CLASS_FIRST_BIT >> (shrink_class_bit & CRT_HEAP_CLASS_INDEX_MASK);
1069 }
1070
1071 shrink_remainder_header->size_flags = new_size;
1072 *(uint32_t *)((char *)shrink_remainder_header + new_size - 4) = new_size;
1073 }
1074
1075 return 1;
1076}
1077
1078// Original pcdogs.exe: 0x449985
1079// Allocates and zeroes memory, retrying through the configured new handler when needed. The element count and size multiply with the original 32-bit wraparound rather than an added overflow check.
1080void *CRT_calloc(uint32_t count, uint32_t element_size)
1081{
1082 uint32_t total_bytes = count * element_size;
1083 uint32_t requested_bytes = total_bytes;
1084
1085 if (total_bytes <= CRT_HEAP_MAX_REQUEST)
1086 {
1087 if (!total_bytes)
1088 total_bytes = 1;
1089
1090 total_bytes = (total_bytes + 0xf) & (~CRT_HEAP_ALIGNMENT_MASK);
1091 }
1092
1093 bool retry_declined;
1094
1095 do
1096 {
1097 void *result = NULL;
1098
1099 if (total_bytes <= CRT_HEAP_MAX_REQUEST)
1100 {
1101 if (requested_bytes <= g_smallBlockAllocThreshold)
1102 result = __sbh_alloc_block(requested_bytes);
1103
1104 if (requested_bytes <= g_smallBlockAllocThreshold && result)
1105 {
1106 _memset(result, 0, requested_bytes);
1107
1108 return result;
1109 }
1110
1111 result = HeapAlloc(g_crtHeapHandle, HEAP_ZERO_MEMORY, total_bytes);
1112
1113 if (result || !g_crtDllMain)
1114 return result;
1115 }
1116 else if (!g_crtDllMain)
1117 return result;
1118
1119 retry_declined = !CRT_callnewh(total_bytes);
1120 } while (!retry_declined);
1121
1122 return NULL;
1123}
uint32_t CRT_msize(void *ptr)
Definition heap.c:184
void * __nh_malloc(uint32_t size, int32_t new_mode)
Definition heap.c:23
int32_t _heap_init(int32_t mt_flag)
Definition heap.c:203
void * CRT_malloc(uint32_t size)
Definition heap.c:16
void * __sbh_alloc_block(uint32_t size)
Definition heap.c:488
void * CRT_realloc(void *ptr, uint32_t size)
Definition heap.c:65
void * CRT_calloc(uint32_t count, uint32_t element_size)
Definition heap.c:1080
void CRT_free(void *ptr)
Definition heap.c:164
void __sbh_free_block(struct CRT_HeapSegment *segment, void *user_ptr)
Definition heap.c:260
int32_t __sbh_resize_block(struct CRT_HeapSegment *segment, void *user_ptr, uint32_t new_size)
Definition heap.c:856
int32_t __sbh_alloc_new_group(struct CRT_HeapSegment *segment)
Definition heap.c:796
void * _heap_alloc(uint32_t size)
Definition heap.c:45
struct CRT_HeapSegment * __sbh_find_block(void *ptr)
Definition heap.c:242
int32_t __sbh_heap_init()
Definition heap.c:223
struct CRT_HeapSegment * __sbh_alloc_new_region()
Definition heap.c:748
int32_t CRT_callnewh(uint32_t size)
Definition heap.c:194
#define g_pfnHeapFree
#define CRT_HEAP_SEGMENT_BYTES
Definition constants.h:283
#define CRT_OS_PAGE_BYTES
Definition constants.h:285
#define CRT_HEAP_PAGE_BYTES
Definition constants.h:282
#define CRT_HEAP_CLASS_BANK_SIZE
Definition constants.h:279
#define CRT_HEAP_LAST_CLASS
Definition constants.h:281
#define CRT_HEAP_ALIGNMENT_MASK
Definition constants.h:74
#define CRT_HEAP_CLASS_INDEX_MASK
Definition constants.h:280
#define CRT_HEAP_MAX_REQUEST
Definition constants.h:286
#define CRT_HEAP_BLOCK_ALLOCATED
Definition constants.h:71
#define CRT_HEAP_PAGE_SHIFT
Definition constants.h:284
#define CRT_HEAP_CLASS_FIRST_BIT
Definition constants.h:72
#define CRT_HEAP_CLASS_LAST_BIT
Definition constants.h:73
void * CRT_MoveBytesOverlapSafeDuplicate(void *dest, void const *src, uint32_t count)
Definition strings.c:201
char * CRT_MoveBytesOverlapSafe(char *dest, char const *src, uint32_t count)
Definition strings.c:134
void * _memset(void *dest, int32_t value, uint32_t count)
Definition strings.c:189
#define g_crtDllMain
Definition globals.h:199
#define g_cachedHeapSegment
Definition globals.h:277
#define g_crtFiberContext
Definition globals.h:202
#define g_heapSegments
Definition globals.h:283
#define g_crtHeapHandle
Definition globals.h:286
#define g_lastFreedSegment
Definition globals.h:280
uint32_t size_flags
Definition types.h:306
struct CRT_HeapFreeBlock * next
Definition types.h:75
struct CRT_HeapFreeBlock * prev
Definition types.h:76
uint32_t size_flags
Definition types.h:74
struct CRT_HeapFreeBlock * prev
Definition types.h:87
struct CRT_HeapFreeBlock * next
Definition types.h:86
uint32_t low_class_bitmap_by_page[0x20]
Definition types.h:282
struct CRT_HeapPageState pages[0x20]
Definition types.h:284
uint8_t free_count_by_class[0x40]
Definition types.h:281
uint32_t high_class_bitmap_by_page[0x20]
Definition types.h:283
int32_t current_page_index
Definition types.h:280
struct CRT_HeapFreeList bins[0x40]
Definition types.h:270
int32_t allocated_count
Definition types.h:269
uint32_t free_page_bitmap
Definition types.h:99
uint32_t high_class_bitmap
Definition types.h:98
struct CRT_HeapPageMap * page_map
Definition types.h:101
uint8_t * reserved_base
Definition types.h:100
uint32_t low_class_bitmap
Definition types.h:97
#define g_heapMaxSegments
Definition values.h:867
#define g_heapSegmentCount
Definition values.h:873
#define g_lastFreedPageIndex
Definition values.h:870
#define g_smallBlockAllocThreshold
Definition values.h:141
uint32_t HEAP_FLAGS
Definition win32_memory.h:6
#define MEM_DECOMMIT
#define PAGE_READWRITE
#define MEM_RESERVE
#define MEM_RELEASE
#define MEM_COMMIT
#define HEAP_ZERO_MEMORY