source: trunk/mem.c @ 148

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

reconstruct shm/allocator

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