source: trunk/xcache/xc_mem.c @ 989

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

clean up

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