source: trunk/mem.c @ 49

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

big diff yet small change: fix ran into outside of shared memory. and commit the test that figure it out.
valgrind rocks even for our code for shared memory.

File size: 7.8 KB
Line 
1#ifdef TEST
2#include <limits.h>
3#include <stdio.h>
4#else
5#include <php.h>
6#endif
7
8#include <assert.h>
9#include <stdlib.h>
10#include <string.h>
11#include "mem.h"
12#include "align.h"
13
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
29// {{{ mem
30struct _xc_block_t {
31#ifdef ALLOC_DEBUG_BLOCK_CHECK
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
44#ifndef XtOffsetOf
45#   include <linux/stddef.h>
46#   define XtOffsetOf(s_type, field) offsetof(s_type, field)
47#endif
48
49#define SizeOf(type, field) sizeof( ((type *) 0)->field )
50#define BLOCK_HEADER_SIZE() (ALIGN( XtOffsetOf(xc_block_t, size) + SizeOf(xc_block_t, size) ))
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{
57#ifdef ALLOC_DEBUG_BLOCK_CHECK
58    b->magic = BLOCK_MAGIC;
59#endif
60    b->size = size;
61    b->next = next;
62}
63/* }}} */
64#ifdef ALLOC_DEBUG_BLOCK_CHECK
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
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
96    do {
97        p = NULL;
98        if (mem->avail < realsize) {
99#ifdef ALLOC_DEBUG
100            fprintf(stderr, " oom\n");
101#endif
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) {
130#ifdef ALLOC_DEBUG
131            fprintf(stderr, " no fit chunk\n");
132#endif
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
144        /* perfect fit, just unlink */
145        if (cur->size == realsize) {
146            prev->next = cur->next;
147#ifdef ALLOC_DEBUG
148            fprintf(stderr, " perfect fit. Got: %p\n", p);
149#endif
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
168        fprintf(stderr, " -> avail: %d (%dKB). new next: %p offset: %d %dKB. Got: %p\n"
169                , mem->avail, mem->avail / 1024
170                , newb
171                , PSUB(newb, mem), PSUB(newb, mem) / 1024
172                , p
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
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
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
209#ifdef ALLOC_DEBUG
210    fprintf(stderr, ", avail %d (%dKB)", mem->avail, mem->avail / 1024);
211#endif
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;
219#ifdef ALLOC_DEBUG
220        fprintf(stderr, ", combine prev");
221#endif
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;
229#ifdef ALLOC_DEBUG
230        fprintf(stderr, ", combine next");
231#endif
232    }
233#ifdef ALLOC_DEBUG
234    fprintf(stderr, " -> avail %d (%dKB)\n", mem->avail, mem->avail / 1024);
235#endif
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
244    memset(p, 0, realsize);
245    return p;
246}
247/* }}} */
248void *xc_mem_realloc(xc_mem_t *mem, const void *p, xc_memsize_t size) /* {{{ */
249{
250    void *newp = xc_mem_malloc(mem, size);
251    memcpy(newp, p, size);
252    xc_mem_free(mem, p);
253    return newp;
254}
255/* }}} */
256char *xc_mem_strndup(xc_mem_t *mem, const char *str, xc_memsize_t len) /* {{{ */
257{
258    void *p = xc_mem_malloc(mem, len + 1);
259    memcpy(p, str, len + 1);
260    return p;
261}
262/* }}} */
263char *xc_mem_strdup(xc_mem_t *mem, const char *str) /* {{{ */
264{
265    return xc_mem_strndup(mem, str, strlen(str));
266}
267/* }}} */
268
269xc_memsize_t xc_mem_avail(xc_mem_t *mem) /* {{{ */
270{
271    return mem->avail;
272}
273/* }}} */
274xc_memsize_t xc_mem_size(xc_mem_t *mem) /* {{{ */
275{
276    return mem->size;
277}
278/* }}} */
279
280const xc_block_t *xc_mem_freeblock_first(xc_mem_t *mem) /* {{{ */
281{
282    return mem->headblock->next;
283}
284/* }}} */
285const xc_block_t *xc_mem_freeblock_next(const xc_block_t *block) /* {{{ */
286{
287    return block->next;
288}
289/* }}} */
290xc_memsize_t xc_mem_block_size(const xc_block_t *block) /* {{{ */
291{
292    return block->size;
293}
294/* }}} */
295xc_memsize_t xc_mem_block_offset(const xc_mem_t *mem, const xc_block_t *block) /* {{{ */
296{
297    return ((char *) block) - ((char *) mem);
298}
299/* }}} */
300
301xc_mem_t *xc_mem_init(void *ptr, xc_memsize_t size) /* {{{ */
302{
303    xc_mem_t   *mem;
304    xc_block_t *b;
305
306#define MINSIZE (ALIGN(sizeof(xc_mem_t)) + sizeof(xc_block_t))
307    /* requires at least the header and 1 tail block */
308    if (size < MINSIZE) {
309        fprintf(stderr, "xc_mem_init requires %d bytes at least\n", MINSIZE);
310        return NULL;
311    }
312    mem = (xc_mem_t *) ptr;
313    mem->size = size;
314    mem->avail = size - MINSIZE;
315
316    /* pointer to first block, right after ALIGNed header */
317    b = mem->headblock;
318    xc_block_setup(b, 0, (xc_block_t *) PADD(mem, ALIGN(sizeof(xc_mem_t))));
319
320    /* first block*/
321    b = b->next;
322    xc_block_setup(b, mem->avail, 0);
323#undef MINSIZE
324
325    return mem;
326}
327/* }}} */
328void xc_mem_destroy(xc_mem_t *mem) /* {{{ */
329{
330}
331/* }}} */
332
333#ifdef TEST
334/* {{{ */
335#undef CHECK
336#define CHECK(a, msg) do { if ((a) == NULL) { puts(msg); return -1; } } while (0)
337#include <time.h>
338
339int main()
340{
341    int count = 0;
342    void *p;
343    void *memory;
344    xc_mem_t *mem;
345    void **ptrs;
346    int size, i;
347
348#if 0
349    fprintf(stderr, "%s", "Input test size: ");
350    scanf("%d", &size);
351#else
352    size = 100;
353#endif
354    CHECK(memory = malloc(size), "OOM");
355    CHECK(ptrs   = malloc(size * sizeof(void*)), "OOM");
356    CHECK(mem    = xc_mem_init(memory, size), "Failed init memory allocator");
357
358    while ((p = xc_mem_malloc(mem, 1))) {
359        ptrs[count ++] = p;
360    }
361    fprintf(stderr, "count=%d, random freeing\n", count);
362    srandom(time(NULL));
363    while (count) {
364        i = (random() % count);
365        fprintf(stderr, "freeing %d: ", i);
366        xc_mem_free(mem, ptrs[i]);
367        ptrs[i] = ptrs[count - 1];
368        count --;
369    }
370
371    free(memory);
372    return 0;
373}
374/* }}} */
375#endif
Note: See TracBrowser for help on using the repository browser.