1 /* suba - sub-allocate memory from larger chunk of memory
2 * Copyright (c) 2003 Michael B. Allen <mba2000 ioplex.com>
3 *
4 * The MIT License
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a
7 * copy of this software and associated documentation files (the "Software"),
8 * to deal in the Software without restriction, including without limitation
9 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
10 * and/or sell copies of the Software, and to permit persons to whom the
11 * Software is furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be included
14 * in all copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
20 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
21 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
22 * OTHER DEALINGS IN THE SOFTWARE.
23 */
24
25 #include <stdlib.h>
26 #include <string.h>
27 #include <stdio.h>
28 #include <errno.h>
29
30 #include "mba/suba.h"
31 #include "mba/dbug.h"
32 #include "mba/msgno.h"
33
34 struct cell {
35 size_t size;
36 /* void *stk[4]; */
37 int line;
38 ref_t next; /* reference to next cell in free list */
39 };
40
41 #define ALIGNMASK 7UL
42 #define ALIGN(s) (((s) + ALIGNMASK) & ~ALIGNMASK)
43 #define POFF ALIGN(offsetof(struct cell, next))
44 #define C2P(c) ((char *)(c) + POFF)
45 #define P2C(p) ((struct cell *)((char *)(p) - POFF))
46 #define ISADJ(c1,c2) ((struct cell *)(C2P(c1) + (c1)->size) == (struct cell *)(c2))
47 #define SREF(s,p) (ref_t)((char *)(p) - (char *)(s))
48 #define SADR(s,r) (void *)((char *)(s) + (r))
49 #define RECLAIM_DEPTH_MAX 2
50 #define SUBA_MAGIC "\xFF\x15\x15\x15SUBA"
51
52 int suba_print_free_list(struct allocator *suba);
53
54 void *
suba_addr(const struct allocator * suba,const ref_t ref)55 suba_addr(const struct allocator *suba, const ref_t ref)
56 {
57 if (suba && ref > 0 && ref <= suba->size) {
58 return (char *)suba + ref;
59 }
60 return NULL;
61 }
62 ref_t
suba_ref(const struct allocator * suba,const void * ptr)63 suba_ref(const struct allocator *suba, const void *ptr)
64 {
65 if (suba && ptr) {
66 ref_t ref = (char *)ptr - (char *)suba;
67 if (ref > 0 && ref <= suba->size) {
68 return ref;
69 }
70 }
71 return 0;
72 }
73
74 struct allocator *
suba_init(void * mem,size_t size,int rst,size_t mincell)75 suba_init(void *mem, size_t size, int rst, size_t mincell)
76 {
77 struct allocator *suba = mem;
78 size_t hdrsiz;
79
80 hdrsiz = ALIGN(sizeof *suba);
81
82 if (mem == NULL || size <= (hdrsiz + POFF) ||
83 (!rst && memcmp(SUBA_MAGIC, suba->magic, 8)) != 0) {
84 PMNO(errno = EINVAL);
85 return NULL;
86 }
87
88 if (rst) {
89 struct cell *c;
90
91 memset(suba, 0, hdrsiz);
92 memcpy(suba->magic, SUBA_MAGIC, 8);
93 suba->tail = hdrsiz;
94 /* cell data must be large enough for next ref_t */
95 suba->mincell = ALIGN(sizeof(size_t));
96 if (mincell > suba->mincell) {
97 suba->mincell = ALIGN(mincell);
98 }
99 suba->size = suba->max_free = size;
100
101 c = suba_addr(suba, hdrsiz);
102 c->size = size - (hdrsiz + POFF);
103 c->next = suba->tail;
104 }
105
106 return suba;
107 }
108 void *
suba_alloc(struct allocator * suba,size_t size,int zero)109 suba_alloc(struct allocator *suba, size_t size, int zero)
110 {
111 struct cell *c1, *c2, *c3;
112 size_t s = size;
113 int reclaim = 0;
114
115 size = size < suba->mincell ? suba->mincell : ALIGN(size);
116
117 again:
118 if (reclaim) {
119 int progress = 0;
120
121 if (suba->reclaim && suba->reclaim_depth <= RECLAIM_DEPTH_MAX) {
122 suba->reclaim_depth++;
123 progress = suba->reclaim(suba, suba->reclaim_arg, reclaim);
124 suba->reclaim_depth--;
125 }
126
127 if (!progress) {
128 PMNO(errno = ENOMEM);
129 return NULL;
130 }
131 }
132
133 c2 = SADR(suba, suba->tail);
134 for ( ;; ) {
135 c1 = c2;
136 if ((c2 = suba_addr(suba, c1->next)) == NULL) {
137 PMNF(errno = EFAULT, ": 0x%08x", c1->next);
138 return NULL;
139 }
140 if (c2->size >= size) {
141 break; /* found a cell large enough */
142 }
143 if (c1->next == suba->tail) {
144 reclaim++;
145 goto again;
146 }
147 }
148
149 if (c2->size > (POFF + size + suba->mincell)) {
150 /* split new cell */
151 c3 = (struct cell *)(C2P(c2) + size);
152 c3->size = c2->size - (size + POFF);
153 if (c1 == c2) {
154 c1 = c3;
155 } else {
156 c3->next = c2->next;
157 }
158 c1->next = SREF(suba, c3);
159 c2->size = size;
160 if (c2 == SADR(suba, suba->tail)) {
161 suba->tail = SREF(suba, c3);
162 }
163 } else if (c1->next == suba->tail) {
164 /* never use the last cell! */
165 reclaim++;
166 goto again;
167 } else { /* use the entire cell */
168 c1->next = c2->next;
169 }
170
171 suba->alloc_total += POFF + c2->size;
172 suba->size_total += s;
173
174 /*
175 dbug_stacktrace(c2->stk, 1, 4);
176
177 suba_print_cell(suba, "ALLOC", c2);
178 */
179
180 return zero ? memset(C2P(c2), 0, size) : C2P(c2);
181 }
182 int
suba_free(void * suba0,void * ptr)183 suba_free(void *suba0, void *ptr)
184 {
185 struct allocator *suba = suba0;
186 struct cell *c1, *c2, *c3;
187 ref_t ref;
188 int j1, j2;
189
190 if (!ptr) return 0;
191
192 if (!suba_ref(suba, ptr)) {
193 PMNO(errno = EFAULT);
194 return -1;
195 }
196 /* splice the cell back into the list */
197 c1 = SADR(suba, suba->tail);
198 c2 = P2C(ptr);
199 if (c2->size > suba->max_free || (ref = suba_ref(suba, c2)) == 0) {
200 PMNF(errno = EINVAL, ": %p: %d", ptr, c2->size);
201 return -1;
202 }
203
204 suba->free_total += POFF + c2->size;
205 /*
206 c2->stk[0] = NULL;
207
208 suba_print_cell(suba, " FREE", c2);
209 */
210
211 if (c2 > c1) { /* append to end of list */
212 if (ISADJ(c1,c2)) { /* join with last cell */
213 c1->size += POFF + c2->size;
214 return 0;
215 }
216 c2->next = c1->next;
217 suba->tail = c1->next = ref;
218
219 return 0;
220 }
221
222 while (c1->next < ref) { /* find insertion point */
223 if (c1->next < POFF) {
224 PMNF(errno = EINVAL, ": next ref corrupted: %d", c1->next);
225 return -1;
226 }
227 c1 = SADR(suba, c1->next);
228 }
229 c3 = SADR(suba, c1->next);
230
231 j1 = ISADJ(c1,c2); /* c1 and c2 need to be joined */
232 j2 = ISADJ(c2,c3); /* c2 and c3 need to be joined */
233
234 if (j1) {
235 if (j2) { /* splice all three cells together */
236 if (SREF(suba, c3) == suba->tail) {
237 suba->tail = SREF(suba, c1);
238 }
239 c1->next = c3->next;
240 c1->size += POFF + c3->size;
241 }
242 c1->size += POFF + c2->size;
243 } else {
244 if (j2) {
245 if (SREF(suba, c3) == suba->tail) {
246 suba->tail = ref;
247 }
248 c2->next = c3->next == SREF(suba, c3) ? ref : c3->next;
249 c2->size += POFF + c3->size;
250 } else {
251 c2->next = c1->next;
252 }
253 c1->next = ref;
254 }
255
256 return 0;
257 }
258 void *
suba_realloc(struct allocator * suba,void * ptr,size_t size)259 suba_realloc(struct allocator *suba, void *ptr, size_t size)
260 {
261 struct cell *c;
262 void *p;
263
264 if (ptr == NULL) {
265 if ((p = suba_alloc(suba, size, 0)) == NULL) {
266 AMSG("");
267 }
268 return p;
269 }
270 if (size == 0) {
271 suba_free(suba, ptr);
272 return NULL;
273 }
274 c = P2C(ptr);
275 if (c->size < size || (c->size - ALIGN(size)) > suba->mincell) {
276 p = suba_alloc(suba, size, 0);
277 } else {
278 return ptr;
279 }
280 if (p) {
281 memcpy(p, ptr, size);
282 suba_free(suba, ptr);
283 }
284
285 return p;
286 }
287
288 int
suba_print_cell(struct allocator * suba,const char * msg,struct cell * c)289 suba_print_cell(struct allocator *suba, const char *msg, struct cell *c)
290 {
291 ref_t ref = suba_ref(suba, c);
292 if (ref >= ALIGN(sizeof *suba) && (ref + POFF + c->size) <= 10000000) {
293 fprintf(stderr, "%s: %8u-%-8lu %8u %-8u\n", msg, ref, ref + POFF + c->size, c->size, c->next);
294 } else {
295 fprintf(stderr, "%s: %8u-err %8u %-8u\n", msg, ref, c->size, c->next);
296 return 0;
297 }
298 return 1;
299 }
300 /*
301 int
302 suba_print_alloc_list(struct allocator *suba, FILE *stream)
303 {
304 struct cell *c, *tail = SADR(suba, suba->tail);
305
306 c = (struct cell *)((char *)suba + ALIGN(sizeof *suba));
307 while (c < tail) {
308 if (c->stk[0]) {
309 unsigned char buf[1024], *blim = buf + 1024;
310 unsigned char msg[16];
311 sprintf((char *)msg, "%d", c->size);
312 dbug_sprint_stacktrace(buf, blim, c->stk, 4, msg);
313 fputs((const char *)buf, stream);
314 fflush(stream);
315 }
316 c = (struct cell *)((char *)c + POFF + c->size);
317 }
318
319 return 0;
320 }
321 */
322 int
suba_print_free_list(struct allocator * suba)323 suba_print_free_list(struct allocator *suba)
324 {
325 struct cell *c;
326 char buf[10];
327 int count = 0;
328 int ret = 1;
329
330 c = suba_addr(suba, suba->tail);
331 while (c->next < suba->tail) {
332 if (c->next < POFF) {
333 PMNF(errno = EINVAL, ": next ref corrupted: %d", c->next);
334 return -1;
335 }
336 c = suba_addr(suba, c->next);
337 sprintf(buf, "%d", count++);
338 if (!suba_print_cell(suba, buf, c)) {
339 ret = 0;
340 }
341 }
342 c = suba_addr(suba, c->next);
343 sprintf(buf, "%d", count++);
344 if (!suba_print_cell(suba, buf, c)) {
345 ret = 0;
346 }
347
348 fprintf(stderr, "count: start-end size next\n");
349
350 return ret;
351 }
352
353