source: trunk/xcache/xc_mem.c @ 1044

Last change on this file since 1044 was 1044, checked in by moo, 21 months ago

refactor: fix c89 compatibility

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