1#include <stddef.h>
2#include <stdint.h>
3#include <stdio.h>
4#include <stdlib.h>
5#include <string.h>
6
7#include "allocator.h"
8#include "dump.h"
9
10static AllocatorStats stats = {};
11
12#define BUBBLEWRAP 32 // the number of bytes around allocated block
13
14typedef struct {
15 void* addr;
16 union {
17 unsigned nbytes;
18 void* _padding;
19 };
20} MemBlockInfo;
21
22static unsigned calc_memsize(unsigned nbytes)
23{
24 return sizeof(MemBlockInfo) + nbytes + BUBBLEWRAP * 2;
25}
26
27static uint8_t* region_from_block(void* block)
28{
29 return (uint8_t*) (((ptrdiff_t) block) - sizeof(MemBlockInfo) - BUBBLEWRAP);
30}
31
32static uint8_t* block_from_region(uint8_t* region_start)
33{
34 return region_start + sizeof(MemBlockInfo) + BUBBLEWRAP;
35}
36
37static void check_region(const char* caller_name, void* block, unsigned nbytes)
38{
39 unsigned memsize = calc_memsize(nbytes);
40 uint8_t* region_start = region_from_block(block);
41 uint8_t* region_end = region_start + memsize;
42 uint8_t* block_start = block_from_region(region_start);
43 uint8_t* block_end = block_start + nbytes;
44
45 unsigned num_damaged_lower = 0;
46 for (unsigned i = sizeof(MemBlockInfo) + BUBBLEWRAP - 1; i >= sizeof(MemBlockInfo); i--) {
47 if (region_start[i] != 0xFF) {
48 num_damaged_lower++;
49 }
50 }
51
52 unsigned num_damaged_upper = 0;
53 for (uint8_t* p = block_end; p < region_end; p++) {
54 if (*p != 0xFF) {
55 num_damaged_upper++;
56 }
57 }
58
59 if (num_damaged_upper || num_damaged_lower) {
60 if (num_damaged_upper && num_damaged_lower) {
61 fprintf(stderr, "%s: damaged %u bytes below %p and %u bytes above %u\n",
62 caller_name, num_damaged_lower, block, num_damaged_upper, nbytes);
63 dump_hex_simple(stderr, region_start, BUBBLEWRAP);
64 dump_hex_simple(stderr, block_end, BUBBLEWRAP);
65 } else if (num_damaged_upper) {
66 fprintf(stderr, "%s: damaged %u bytes above %p + %u\n",
67 caller_name, num_damaged_upper, block, nbytes);
68 dump_hex_simple(stderr, block_end, BUBBLEWRAP);
69 } else {
70 fprintf(stderr, "%s: damaged %u bytes below %p\n",
71 caller_name, num_damaged_lower, block);
72 dump_hex_simple(stderr, region_start, BUBBLEWRAP);
73 }
74 exit(1);
75 }
76}
77
78static void* _allocate(unsigned nbytes, bool clean)
79{
80 unsigned memsize = calc_memsize(nbytes);
81
82 uint8_t* region_start;
83 if (clean) {
84 region_start = calloc(1, memsize);
85 } else {
86 region_start = malloc(memsize);
87 }
88 if (!region_start) {
89 return nullptr;
90 }
91 uint8_t* region_end = region_start + memsize;
92 uint8_t* block_start = region_start + sizeof(MemBlockInfo) + BUBBLEWRAP;
93 uint8_t* block_end = block_start + nbytes;
94
95 if (region_end <= block_end) {
96 fprintf(stderr, "%s: region_end %p must be greater than block_end %p\n",
97 __func__, (void*) region_end, (void*) block_end);
98 exit(1);
99 }
100
101 memset(region_start, 0xFF, block_start - region_start);
102 memset(block_end, 0xFF, region_end - block_end);
103
104 MemBlockInfo* info = (MemBlockInfo*) region_start;
105 info->addr = block_start;
106 info->nbytes = nbytes;
107
108 atomic_fetch_add(&stats.blocks_allocated, 1);
109
110 if (debug_allocator.verbose) {
111 printf("%s: %u bytes -> %p\n", __func__, nbytes, (void*) block_start);
112 }
113 return block_start;
114}
115
116static void _release(void** addr_ptr, unsigned nbytes)
117{
118 void* addr = *addr_ptr;
119 if (!addr) {
120 return;
121 }
122
123 check_region(__func__, addr, nbytes);
124
125 free(region_from_block(addr));
126
127 if (debug_allocator.verbose) {
128 fprintf(stderr, "%s: %p %u bytes\n", __func__, addr, nbytes);
129 }
130 atomic_fetch_sub(&stats.blocks_allocated, 1);
131
132 *addr_ptr = nullptr;
133}
134
135static bool _reallocate(void** addr_ptr, unsigned old_nbytes, unsigned new_nbytes, bool clean, bool* addr_changed)
136{
137 if (old_nbytes == new_nbytes) {
138 goto success_same_addr;
139 }
140
141 void* addr = *addr_ptr;
142
143 // shall we allocate new addr?
144 if (addr == nullptr) {
145 if (old_nbytes != 0) {
146 goto error;
147 }
148 addr = _allocate(new_nbytes, clean);
149 if (!addr) {
150 goto error;
151 }
152 *addr_ptr = addr;
153 goto success_changed_addr;
154 }
155
156 void* new_addr = _allocate(new_nbytes, false);
157 if (new_addr == nullptr) {
158 goto error;
159 }
160
161 memcpy(new_addr, addr, old_nbytes);
162 _release(&addr, old_nbytes);
163
164 if (clean) {
165 memset(((uint8_t*) new_addr) + old_nbytes, 0, new_nbytes - old_nbytes);
166 }
167 *addr_ptr = new_addr;
168
169success_changed_addr:
170 if (addr_changed) { *addr_changed = true; }
171 return true;
172
173success_same_addr:
174 if (addr_changed) { *addr_changed = false; }
175 return true;
176
177error:
178 if (addr_changed) { *addr_changed = false; }
179 return false;
180}
181
182static void _dump()
183{
184 fprintf(stderr, "Debug allocator: dump is not implemented\n");
185}
186
187Allocator debug_allocator = {
188 .init = nullptr,
189 .allocate = _allocate,
190 .reallocate = _reallocate,
191 .release = _release,
192 .dump = _dump,
193 .trace = false,
194 .verbose = false,
195 .stats = &stats
196};