source: branches/1.0/mem.c @ 112

Last change on this file since 112 was 112, checked in by moo, 8 years ago

avoid crash when OOM on mem_(calloc|realloc|strndup)

File size: 7.8 KB
RevLine 
[49]1#ifdef TEST
2#include <limits.h>
3#include <stdio.h>
4#else
[1]5#include <php.h>
[49]6#endif
7
8#include <assert.h>
[1]9#include <stdlib.h>
[49]10#include <string.h>
[1]11#include "mem.h"
12#include "align.h"
13
[49]14#ifdef TEST
15#   define ALLOC_DEBUG
16#endif
17#ifdef ALLOC_DEBUG
18#   define ALLOC_DEBUG_BLOCK_CHECK
19#endif
20
21#if 0
22#undef ALLOC_DEBUG_BLOCK_CHECK
23#endif
24
25#define CHAR_PTR(p) ((char *) (p))
26#define PADD(p, a) (CHAR_PTR(p) + a)
27#define PSUB(p1, p2) (CHAR_PTR(p1) - CHAR_PTR(p2))
28
[1]29// {{{ mem
30struct _xc_block_t {
[49]31#ifdef ALLOC_DEBUG_BLOCK_CHECK
[1]32    unsigned int magic;
33#endif
34    xc_memsize_t size; /* reserved even after alloc */
35    xc_block_t *next;  /* not used after alloc */
36};
37
38struct _xc_mem_t {
39    xc_memsize_t size;
40    xc_memsize_t avail;       /* total free */
41    xc_block_t headblock[1];  /* just as a pointer to first block*/
42};
43
[49]44#ifndef XtOffsetOf
45#   include <linux/stddef.h>
46#   define XtOffsetOf(s_type, field) offsetof(s_type, field)
[1]47#endif
[49]48
[1]49#define SizeOf(type, field) sizeof( ((type *) 0)->field )
[49]50#define BLOCK_HEADER_SIZE() (ALIGN( XtOffsetOf(xc_block_t, size) + SizeOf(xc_block_t, size) ))
[1]51
52#define BLOCK_MAGIC ((unsigned int) 0x87655678)
53
54/* }}} */
55static inline void xc_block_setup(xc_block_t *b, xc_memsize_t size, xc_block_t *next) /* {{{ */
56{
[49]57#ifdef ALLOC_DEBUG_BLOCK_CHECK
[1]58    b->magic = BLOCK_MAGIC;
59#endif
60    b->size = size;
61    b->next = next;
62}
63/* }}} */
[49]64#ifdef ALLOC_DEBUG_BLOCK_CHECK
[1]65static void xc_block_check(xc_block_t *b) /* {{{ */
66{
67    if (b->magic != BLOCK_MAGIC) {
68        fprintf(stderr, "0x%X != 0x%X magic wrong \n", b->magic, BLOCK_MAGIC);
69    }
70}
71/* }}} */
72#else
73#   define xc_block_check(b) do { } while(0)
74#endif
75
76
77void *xc_mem_malloc(xc_mem_t *mem, xc_memsize_t size) /* {{{ */
78{
79    xc_block_t *prev, *cur;
80    xc_block_t *newb, *b;
81    xc_memsize_t realsize;
82    xc_memsize_t minsize;
83    void *p;
84    /* [xc_block_t:size|size] */
85    realsize = BLOCK_HEADER_SIZE() + size;
86    /* realsize is ALIGNed so next block start at ALIGNed address */
87    realsize = ALIGN(realsize);
88
[49]89#ifdef ALLOC_DEBUG
90    fprintf(stderr, "avail: %d (%dKB). Allocate size: %d realsize: %d (%dKB)"
91            , mem->avail, mem->avail / 1024
92            , size
93            , realsize, realsize / 1024
94            );
95#endif
[1]96    do {
97        p = NULL;
98        if (mem->avail < realsize) {
[49]99#ifdef ALLOC_DEBUG
100            fprintf(stderr, " oom\n");
101#endif
[1]102            break;
103        }
104
105        b = NULL;
106        minsize = INT_MAX;
107
108        /* prev|cur */
109
110        for (prev = mem->headblock; prev->next; prev = cur) {
111            /* while (prev->next != 0) { */
112            cur = prev->next;
113            xc_block_check(cur);
114            if (cur->size == realsize) {
115                /* found a perfect fit, stop searching */
116                b = prev;
117                break;
118            }
119            /* make sure we can split on the block */
120            else if (cur->size > (sizeof(xc_block_t) + realsize) &&
121                    cur->size < minsize) {
122                /* cur is acceptable and memller */
123                b = prev;
124                minsize = cur->size;
125            }
126            prev = cur;
127        }
128
129        if (b == NULL) {
[49]130#ifdef ALLOC_DEBUG
131            fprintf(stderr, " no fit chunk\n");
132#endif
[1]133            break;
134        }
135
136        prev = b;
137
138        cur = prev->next;
139        p = PADD(cur, BLOCK_HEADER_SIZE());
140
141        /* update the block header */
142        mem->avail -= realsize;
143
[49]144        /* perfect fit, just unlink */
[1]145        if (cur->size == realsize) {
146            prev->next = cur->next;
[49]147#ifdef ALLOC_DEBUG
148            fprintf(stderr, " perfect fit. Got: %p\n", p);
149#endif
[1]150            break;
151        }
152
153        /* make new free block after alloced space */
154
155        /* save, as it might be overwrited by newb (cur->size is ok) */
156        b = cur->next;
157
158        /* prev|cur     |next=b */
159
160        newb = (xc_block_t *)PADD(cur, realsize);
161        xc_block_setup(newb, cur->size - realsize, b);
162        cur->size = realsize;
163        /* prev|cur|newb|next
164         *            `--^
165         */
166
167#ifdef ALLOC_DEBUG
[49]168        fprintf(stderr, " -> avail: %d (%dKB). new next: %p offset: %d %dKB. Got: %p\n"
169                , mem->avail, mem->avail / 1024
[1]170                , newb
[49]171                , PSUB(newb, mem), PSUB(newb, mem) / 1024
172                , p
[1]173                );
174#endif
175        prev->next = newb;
176        /* prev|cur|newb|next
177         *    `-----^
178         */
179
180    } while (0);
181
182    return p;
183}
184/* }}} */
185int xc_mem_free(xc_mem_t *mem, const void *p) /* {{{ return block size freed */
186{
187    xc_block_t *cur, *b;
188    int size;
189
[49]190    cur = (xc_block_t *) (CHAR_PTR(p) - BLOCK_HEADER_SIZE());
191#ifdef ALLOC_DEBUG
192    fprintf(stderr, "freeing: %p", p);
193    fprintf(stderr, ", size=%d", cur->size);
194#endif
[1]195    xc_block_check(cur);
196    assert((char*)mem < (char*)cur && (char*)cur < (char*)mem + mem->size);
197
198    /* find free block right before the p */
199    b = mem->headblock;
200    while (b->next != 0 && b->next < cur) {
201        b = b->next;
202    }
203
204    /* restore block */
205    cur->next = b->next;
206    b->next = cur;
207    size = cur->size;
208
[49]209#ifdef ALLOC_DEBUG
210    fprintf(stderr, ", avail %d (%dKB)", mem->avail, mem->avail / 1024);
211#endif
[1]212    mem->avail += size;
213
214    /* combine prev|cur */
215    if (PADD(b, b->size) == (char *)cur) {
216        b->size += cur->size;
217        b->next = cur->next;
218        cur = b;
[49]219#ifdef ALLOC_DEBUG
220        fprintf(stderr, ", combine prev");
221#endif
[1]222    }
223
224    /* combine cur|next */
225    b = cur->next;
226    if (PADD(cur, cur->size) == (char *)b) {
227        cur->size += b->size;
228        cur->next = b->next;
[49]229#ifdef ALLOC_DEBUG
230        fprintf(stderr, ", combine next");
231#endif
[1]232    }
[49]233#ifdef ALLOC_DEBUG
234    fprintf(stderr, " -> avail %d (%dKB)\n", mem->avail, mem->avail / 1024);
235#endif
[1]236    return size;
237}
238/* }}} */
239void *xc_mem_calloc(xc_mem_t *mem, xc_memsize_t memb, xc_memsize_t size) /* {{{ */
240{
241    xc_memsize_t realsize = memb * size;
242    void *p = xc_mem_malloc(mem, realsize);
243
[112]244    if (p) {
245        memset(p, 0, realsize);
246    }
[1]247    return p;
248}
249/* }}} */
250void *xc_mem_realloc(xc_mem_t *mem, const void *p, xc_memsize_t size) /* {{{ */
251{
252    void *newp = xc_mem_malloc(mem, size);
[112]253    if (p) {
254        memcpy(newp, p, size);
255        xc_mem_free(mem, p);
256    }
[1]257    return newp;
258}
259/* }}} */
260char *xc_mem_strndup(xc_mem_t *mem, const char *str, xc_memsize_t len) /* {{{ */
261{
262    void *p = xc_mem_malloc(mem, len + 1);
[112]263    if (p) {
264        memcpy(p, str, len + 1);
265    }
[1]266    return p;
267}
268/* }}} */
269char *xc_mem_strdup(xc_mem_t *mem, const char *str) /* {{{ */
270{
271    return xc_mem_strndup(mem, str, strlen(str));
272}
273/* }}} */
274
275xc_memsize_t xc_mem_avail(xc_mem_t *mem) /* {{{ */
276{
277    return mem->avail;
278}
279/* }}} */
280xc_memsize_t xc_mem_size(xc_mem_t *mem) /* {{{ */
281{
282    return mem->size;
283}
284/* }}} */
285
286const xc_block_t *xc_mem_freeblock_first(xc_mem_t *mem) /* {{{ */
287{
288    return mem->headblock->next;
289}
290/* }}} */
291const xc_block_t *xc_mem_freeblock_next(const xc_block_t *block) /* {{{ */
292{
293    return block->next;
294}
295/* }}} */
296xc_memsize_t xc_mem_block_size(const xc_block_t *block) /* {{{ */
297{
298    return block->size;
299}
300/* }}} */
301xc_memsize_t xc_mem_block_offset(const xc_mem_t *mem, const xc_block_t *block) /* {{{ */
302{
303    return ((char *) block) - ((char *) mem);
304}
305/* }}} */
306
307xc_mem_t *xc_mem_init(void *ptr, xc_memsize_t size) /* {{{ */
308{
[49]309    xc_mem_t   *mem;
310    xc_block_t *b;
[1]311
[49]312#define MINSIZE (ALIGN(sizeof(xc_mem_t)) + sizeof(xc_block_t))
313    /* requires at least the header and 1 tail block */
314    if (size < MINSIZE) {
315        fprintf(stderr, "xc_mem_init requires %d bytes at least\n", MINSIZE);
316        return NULL;
317    }
318    mem = (xc_mem_t *) ptr;
[1]319    mem->size = size;
[49]320    mem->avail = size - MINSIZE;
[1]321
[49]322    /* pointer to first block, right after ALIGNed header */
[1]323    b = mem->headblock;
[49]324    xc_block_setup(b, 0, (xc_block_t *) PADD(mem, ALIGN(sizeof(xc_mem_t))));
[1]325
326    /* first block*/
327    b = b->next;
328    xc_block_setup(b, mem->avail, 0);
[49]329#undef MINSIZE
[1]330
331    return mem;
332}
333/* }}} */
334void xc_mem_destroy(xc_mem_t *mem) /* {{{ */
335{
336}
337/* }}} */
[49]338
339#ifdef TEST
340/* {{{ */
341#undef CHECK
342#define CHECK(a, msg) do { if ((a) == NULL) { puts(msg); return -1; } } while (0)
343#include <time.h>
344
345int main()
346{
347    int count = 0;
348    void *p;
349    void *memory;
350    xc_mem_t *mem;
351    void **ptrs;
352    int size, i;
353
354#if 0
355    fprintf(stderr, "%s", "Input test size: ");
356    scanf("%d", &size);
357#else
358    size = 100;
359#endif
360    CHECK(memory = malloc(size), "OOM");
361    CHECK(ptrs   = malloc(size * sizeof(void*)), "OOM");
362    CHECK(mem    = xc_mem_init(memory, size), "Failed init memory allocator");
363
364    while ((p = xc_mem_malloc(mem, 1))) {
365        ptrs[count ++] = p;
366    }
367    fprintf(stderr, "count=%d, random freeing\n", count);
368    srandom(time(NULL));
369    while (count) {
370        i = (random() % count);
371        fprintf(stderr, "freeing %d: ", i);
372        xc_mem_free(mem, ptrs[i]);
373        ptrs[i] = ptrs[count - 1];
374        count --;
375    }
376
[54]377    free(ptrs);
[49]378    free(memory);
379    return 0;
380}
381/* }}} */
382#endif
Note: See TracBrowser for help on using the repository browser.