source: trunk/xcache/xc_mem.c @ 999

Last change on this file since 999 was 999, checked in by moo, 2 years ago

fix mem test

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