source: trunk/mem.c @ 675

Last change on this file since 675 was 675, checked in by moo, 5 years ago

improved fixe for #224: 2G/4G limitation on 64bit arch

  • Property svn:eol-style set to native
File size: 8.4 KB
Line 
1#ifdef TEST
2#include <limits.h>
3#include <stdio.h>
4#   define XCACHE_DEBUG
5#else
6#include <php.h>
7#endif
8
9#ifdef XCACHE_DEBUG
10#   define ALLOC_DEBUG_BLOCK_CHECK
11#endif
12
13
14#include <assert.h>
15#include <stdlib.h>
16#include <string.h>
17#define XC_MEMBLOCK_IMPL _xc_mem_block_t
18#define XC_MEM_IMPL _xc_mem_mem_t
19#include "xc_shm.h"
20#include "align.h"
21#include "utils.h"
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_mem_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_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    TRACE("avail: %lu (%luKB). Allocate size: %lu realsize: %lu (%luKB)"
94            , mem->avail, mem->avail / 1024
95            , size
96            , realsize, realsize / 1024
97            );
98    do {
99        p = NULL;
100        if (mem->avail < realsize) {
101            TRACE("%s", " oom");
102            break;
103        }
104
105        b = NULL;
106        minsize = ULONG_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            TRACE("%s", " no fit chunk");
131            break;
132        }
133
134        prev = b;
135
136        cur = prev->next;
137        p = PADD(cur, BLOCK_HEADER_SIZE());
138
139        /* update the block header */
140        mem->avail -= realsize;
141
142        /* perfect fit, just unlink */
143        if (cur->size == realsize) {
144            prev->next = cur->next;
145            TRACE(" perfect fit. Got: %p", p);
146            break;
147        }
148
149        /* make new free block after alloced space */
150
151        /* save, as it might be overwrited by newb (cur->size is ok) */
152        b = cur->next;
153
154        /* prev|cur     |next=b */
155
156        newb = (xc_block_t *)PADD(cur, realsize);
157        xc_block_setup(newb, cur->size - realsize, b);
158        cur->size = realsize;
159        /* prev|cur|newb|next
160         *            `--^
161         */
162
163        TRACE(" -> avail: %lu (%luKB). new next: %p offset: %lu %luKB. Got: %p"
164                , mem->avail, mem->avail / 1024
165                , newb
166                , PSUB(newb, mem), PSUB(newb, mem) / 1024
167                , p
168                );
169        prev->next = newb;
170        /* prev|cur|newb|next
171         *    `-----^
172         */
173
174    } while (0);
175
176    return p;
177}
178/* }}} */
179static XC_MEM_FREE(xc_mem_free) /* {{{ return block size freed */
180{
181    xc_block_t *cur, *b;
182    int size;
183
184    cur = (xc_block_t *) (CHAR_PTR(p) - BLOCK_HEADER_SIZE());
185    TRACE("freeing: %p, size=%lu", p, cur->size);
186    xc_block_check(cur);
187    assert((char*)mem < (char*)cur && (char*)cur < (char*)mem + mem->size);
188
189    /* find free block right before the p */
190    b = mem->headblock;
191    while (b->next != 0 && b->next < cur) {
192        b = b->next;
193    }
194
195    /* restore block */
196    cur->next = b->next;
197    b->next = cur;
198    size = cur->size;
199
200    TRACE(" avail %lu (%luKB)", mem->avail, mem->avail / 1024);
201    mem->avail += size;
202
203    /* combine prev|cur */
204    if (PADD(b, b->size) == (char *)cur) {
205        b->size += cur->size;
206        b->next = cur->next;
207        cur = b;
208        TRACE("%s", " combine prev");
209    }
210
211    /* combine cur|next */
212    b = cur->next;
213    if (PADD(cur, cur->size) == (char *)b) {
214        cur->size += b->size;
215        cur->next = b->next;
216        TRACE("%s", " combine next");
217    }
218    TRACE(" -> avail %lu (%luKB)", mem->avail, mem->avail / 1024);
219    return size;
220}
221/* }}} */
222static XC_MEM_CALLOC(xc_mem_calloc) /* {{{ */
223{
224    xc_memsize_t realsize = memb * size;
225    void *p = xc_mem_malloc(mem, realsize);
226
227    if (p) {
228        memset(p, 0, realsize);
229    }
230    return p;
231}
232/* }}} */
233static XC_MEM_REALLOC(xc_mem_realloc) /* {{{ */
234{
235    void *newp = xc_mem_malloc(mem, size);
236    if (p && newp) {
237        memcpy(newp, p, size);
238        xc_mem_free(mem, p);
239    }
240    return newp;
241}
242/* }}} */
243static XC_MEM_STRNDUP(xc_mem_strndup) /* {{{ */
244{
245    void *p = xc_mem_malloc(mem, len + 1);
246    if (p) {
247        memcpy(p, str, len + 1);
248    }
249    return p;
250}
251/* }}} */
252static XC_MEM_STRDUP(xc_mem_strdup) /* {{{ */
253{
254    return xc_mem_strndup(mem, str, strlen(str));
255}
256/* }}} */
257
258static XC_MEM_AVAIL(xc_mem_avail) /* {{{ */
259{
260    return mem->avail;
261}
262/* }}} */
263static XC_MEM_SIZE(xc_mem_size) /* {{{ */
264{
265    return mem->size;
266}
267/* }}} */
268
269static XC_MEM_FREEBLOCK_FIRST(xc_mem_freeblock_first) /* {{{ */
270{
271    return mem->headblock->next;
272}
273/* }}} */
274XC_MEM_FREEBLOCK_NEXT(xc_mem_freeblock_next) /* {{{ */
275{
276    return block->next;
277}
278/* }}} */
279XC_MEM_BLOCK_SIZE(xc_mem_block_size) /* {{{ */
280{
281    return block->size;
282}
283/* }}} */
284XC_MEM_BLOCK_OFFSET(xc_mem_block_offset) /* {{{ */
285{
286    return ((char *) block) - ((char *) mem);
287}
288/* }}} */
289
290static XC_MEM_INIT(xc_mem_init) /* {{{ */
291{
292    xc_block_t *b;
293#define MINSIZE (ALIGN(sizeof(xc_mem_t)) + sizeof(xc_block_t))
294    /* requires at least the header and 1 tail block */
295    if (size < MINSIZE) {
296        fprintf(stderr, "xc_mem_init requires %lu bytes at least\n", (unsigned long) MINSIZE);
297        return NULL;
298    }
299    TRACE("size=%lu", size);
300    mem->shm = shm;
301    mem->size = size;
302    mem->avail = size - MINSIZE;
303
304    /* pointer to first block, right after ALIGNed header */
305    b = mem->headblock;
306    xc_block_setup(b, 0, (xc_block_t *) PADD(mem, ALIGN(sizeof(xc_mem_t))));
307
308    /* first block*/
309    b = b->next;
310    xc_block_setup(b, mem->avail, 0);
311#undef MINSIZE
312
313    return mem;
314}
315/* }}} */
316static XC_MEM_DESTROY(xc_mem_destroy) /* {{{ */
317{
318}
319/* }}} */
320
321#ifdef TEST
322/* {{{ */
323#undef CHECK
324#define CHECK(a, msg) do { if ((a) == NULL) { puts(msg); return -1; } } while (0)
325#include <time.h>
326
327int main()
328{
329    int count = 0;
330    void *p;
331    void *memory;
332    xc_mem_t *mem;
333    void **ptrs;
334    int size, i;
335
336#if 0
337    fprintf(stderr, "%s", "Input test size: ");
338    scanf("%d", &size);
339#else
340    size = 100;
341#endif
342    CHECK(memory = malloc(size), "OOM");
343    CHECK(ptrs   = malloc(size * sizeof(void*)), "OOM");
344    CHECK(mem    = xc_mem_init(memory, size), "Failed init memory allocator");
345
346    while ((p = xc_mem_malloc(mem, 1))) {
347        ptrs[count ++] = p;
348    }
349    fprintf(stderr, "count=%d, random freeing\n", count);
350    srandom(time(NULL));
351    while (count) {
352        i = (random() % count);
353        fprintf(stderr, "freeing %d: ", i);
354        xc_mem_free(mem, ptrs[i]);
355        ptrs[i] = ptrs[count - 1];
356        count --;
357    }
358
359    free(ptrs);
360    free(memory);
361    return 0;
362}
363/* }}} */
364#endif
365
366typedef struct {
367    const char              *name;
368    const xc_mem_handlers_t *handlers;
369} xc_mem_scheme_t;
370static xc_mem_scheme_t xc_mem_schemes[10];
371
372int xc_mem_scheme_register(const char *name, const xc_mem_handlers_t *handlers) /* {{{ */
373{
374    int i;
375    for (i = 0; i < 10; i ++) {
376        if (!xc_mem_schemes[i].name) {
377            xc_mem_schemes[i].name = name;
378            xc_mem_schemes[i].handlers = handlers;
379            return 1;
380        }
381    }
382    return 0;
383}
384/* }}} */
385const xc_mem_handlers_t *xc_mem_scheme_find(const char *name) /* {{{ */
386{
387    int i;
388    for (i = 0; i < 10 && xc_mem_schemes[i].name; i ++) {
389        if (strcmp(xc_mem_schemes[i].name, name) == 0) {
390            return xc_mem_schemes[i].handlers;
391        }
392    }
393    return NULL;
394}
395/* }}} */
396
397static xc_mem_handlers_t xc_mem_mem_handlers = XC_MEM_HANDLERS(mem);
398void xc_shm_mem_init() /* {{{ */
399{
400    memset(xc_mem_schemes, 0, sizeof(xc_mem_schemes));
401
402    if (xc_mem_scheme_register("mem", &xc_mem_mem_handlers) == 0) {
403        zend_error(E_ERROR, "XCache: failed to register mem mem_scheme");
404    }
405}
406/* }}} */
Note: See TracBrowser for help on using the repository browser.