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