source: trunk/xcache/xc_allocator_bestfit.c @ 1391

Last change on this file since 1391 was 1391, checked in by moo, 15 months ago

fix xtest

  • Property svn:eol-style set to native
File size: 7.7 KB
Line 
1#define _xc_allocator_t _xc_allocator_bestfit_t
2#define _xc_allocator_block_t _xc_allocator_bestfit_block_t
3#include "xc_allocator.h"
4#undef _xc_allocator_t
5#undef _xc_allocator_block_t
6
7#ifdef TEST
8#   include <limits.h>
9#   include <stdio.h>
10#   define XCACHE_DEBUG
11typedef int zend_bool;
12#   define ZEND_ATTRIBUTE_PTR_FORMAT(a, b, c)
13#   define zend_error(type, error) fprintf(stderr, "%s", error)
14#else
15#   include <php.h>
16#endif
17
18#ifdef XCACHE_DEBUG
19#   define ALLOC_DEBUG_BLOCK_CHECK
20#endif
21
22
23#include <assert.h>
24#include <stdlib.h>
25#include <string.h>
26#include "xc_shm.h"
27#include "util/xc_align.h"
28#include "util/xc_trace.h"
29
30#if 0
31#undef ALLOC_DEBUG_BLOCK_CHECK
32#endif
33
34#define CHAR_PTR(p) ((char *) (p))
35#define PADD(p, a) (CHAR_PTR(p) + a)
36#define PSUB(p1, p2) (CHAR_PTR(p1) - CHAR_PTR(p2))
37
38/* {{{ allocator */
39typedef struct _xc_allocator_bestfit_block_t xc_allocator_bestfit_block_t;
40struct _xc_allocator_bestfit_block_t {
41#ifdef ALLOC_DEBUG_BLOCK_CHECK
42    unsigned int magic;
43#endif
44    xc_memsize_t size; /* reserved even after alloc */
45    xc_allocator_bestfit_block_t *next;  /* not used after alloc */
46};
47
48typedef struct _xc_allocator_bestfit_t {
49    const xc_allocator_vtable_t *vtable;
50    xc_shm_t *shm;
51    xc_memsize_t size;
52    xc_memsize_t avail;       /* total free */
53    xc_allocator_bestfit_block_t headblock[1];  /* just as a pointer to first block*/
54} xc_allocator_bestfit_t;
55
56#include <stddef.h>
57
58#define SizeOf(type, field) sizeof( ((type *) 0)->field )
59#define BLOCK_HEADER_SIZE() (ALIGN( offsetof(xc_allocator_bestfit_block_t, size) + SizeOf(xc_allocator_bestfit_block_t, size) ))
60
61#define BLOCK_MAGIC ((unsigned int) 0x87655678)
62
63/* }}} */
64static inline void xc_block_setup(xc_allocator_bestfit_block_t *b, xc_memsize_t size, xc_allocator_bestfit_block_t *next) /* {{{ */
65{
66#ifdef ALLOC_DEBUG_BLOCK_CHECK
67    b->magic = BLOCK_MAGIC;
68#endif
69    b->size = size;
70    b->next = next;
71}
72/* }}} */
73#ifdef ALLOC_DEBUG_BLOCK_CHECK
74static void xc_block_check(xc_allocator_bestfit_block_t *b) /* {{{ */
75{
76    if (b->magic != BLOCK_MAGIC) {
77        fprintf(stderr, "0x%X != 0x%X magic wrong \n", b->magic, BLOCK_MAGIC);
78    }
79}
80/* }}} */
81#else
82#   define xc_block_check(b) do { } while(0)
83#endif
84
85
86static XC_ALLOCATOR_MALLOC(xc_allocator_bestfit_malloc) /* {{{ */
87{
88    xc_allocator_bestfit_block_t *prev, *cur;
89    xc_allocator_bestfit_block_t *newb, *b;
90    xc_memsize_t realsize;
91    xc_memsize_t minsize;
92    void *p;
93    /* [xc_allocator_bestfit_block_t:size|size] */
94    realsize = BLOCK_HEADER_SIZE() + size;
95    /* realsize is ALIGNed so next block start at ALIGNed address */
96    realsize = ALIGN(realsize);
97
98    TRACE("avail: %lu (%luKB). Allocate size: %lu realsize: %lu (%luKB)"
99            , allocator->avail, allocator->avail / 1024
100            , size
101            , realsize, realsize / 1024
102            );
103    do {
104        p = NULL;
105        if (allocator->avail < realsize) {
106            TRACE("%s", " oom");
107            break;
108        }
109
110        b = NULL;
111        minsize = ULONG_MAX;
112
113        /* prev|cur */
114
115        for (prev = allocator->headblock; prev->next; prev = cur) {
116            /* while (prev->next != 0) { */
117            cur = prev->next;
118            xc_block_check(cur);
119            if (cur->size == realsize) {
120                /* found a perfect fit, stop searching */
121                b = prev;
122                break;
123            }
124            /* make sure we can split on the block */
125            else if (cur->size > (sizeof(xc_allocator_bestfit_block_t) + realsize) &&
126                    cur->size < minsize) {
127                /* cur is acceptable and memller */
128                b = prev;
129                minsize = cur->size;
130            }
131            prev = cur;
132        }
133
134        if (b == NULL) {
135            TRACE("%s", " no fit chunk");
136            break;
137        }
138
139        prev = b;
140
141        cur = prev->next;
142        p = PADD(cur, BLOCK_HEADER_SIZE());
143
144        /* update the block header */
145        allocator->avail -= realsize;
146
147        /* perfect fit, just unlink */
148        if (cur->size == realsize) {
149            prev->next = cur->next;
150            TRACE(" perfect fit. Got: %p", p);
151            break;
152        }
153
154        /* make new free block after alloced space */
155
156        /* save, as it might be overwrited by newb (cur->size is ok) */
157        b = cur->next;
158
159        /* prev|cur     |next=b */
160
161        newb = (xc_allocator_bestfit_block_t *)PADD(cur, realsize);
162        xc_block_setup(newb, cur->size - realsize, b);
163        cur->size = realsize;
164        /* prev|cur|newb|next
165         *            `--^
166         */
167
168        TRACE(" -> avail: %lu (%luKB). new next: %p offset: %lu %luKB. Got: %p"
169                , allocator->avail, allocator->avail / 1024
170                , newb
171                , PSUB(newb, allocator), PSUB(newb, allocator) / 1024
172                , p
173                );
174        prev->next = newb;
175        /* prev|cur|newb|next
176         *    `-----^
177         */
178
179    } while (0);
180
181    return p;
182}
183/* }}} */
184static XC_ALLOCATOR_FREE(xc_allocator_bestfit_free) /* {{{ return block size freed */
185{
186    xc_allocator_bestfit_block_t *cur, *b;
187    int size;
188
189    cur = (xc_allocator_bestfit_block_t *) (CHAR_PTR(p) - BLOCK_HEADER_SIZE());
190    TRACE("freeing: %p, size=%lu", p, cur->size);
191    xc_block_check(cur);
192    assert((char*)allocator < (char*)cur);
193    assert((char*)cur < (char*)allocator + allocator->size);
194
195    /* find free block right before the p */
196    b = allocator->headblock;
197    while (b->next != 0 && b->next < cur) {
198        b = b->next;
199    }
200
201    /* restore block */
202    cur->next = b->next;
203    b->next = cur;
204    size = cur->size;
205
206    TRACE(" avail %lu (%luKB)", allocator->avail, allocator->avail / 1024);
207    allocator->avail += size;
208
209    /* combine prev|cur */
210    if (PADD(b, b->size) == (char *)cur) {
211        b->size += cur->size;
212        b->next = cur->next;
213        cur = b;
214        TRACE("%s", " combine prev");
215    }
216
217    /* combine cur|next */
218    b = cur->next;
219    if (PADD(cur, cur->size) == (char *)b) {
220        cur->size += b->size;
221        cur->next = b->next;
222        TRACE("%s", " combine next");
223    }
224    TRACE(" -> avail %lu (%luKB)", allocator->avail, allocator->avail / 1024);
225    return size;
226}
227/* }}} */
228static XC_ALLOCATOR_CALLOC(xc_allocator_bestfit_calloc) /* {{{ */
229{
230    xc_memsize_t realsize = memb * size;
231    void *p = xc_allocator_bestfit_malloc(allocator, realsize);
232
233    if (p) {
234        memset(p, 0, realsize);
235    }
236    return p;
237}
238/* }}} */
239static XC_ALLOCATOR_REALLOC(xc_allocator_bestfit_realloc) /* {{{ */
240{
241    void *newp = xc_allocator_bestfit_malloc(allocator, size);
242    if (p && newp) {
243        memcpy(newp, p, size);
244        xc_allocator_bestfit_free(allocator, p);
245    }
246    return newp;
247}
248/* }}} */
249
250static XC_ALLOCATOR_AVAIL(xc_allocator_bestfit_avail) /* {{{ */
251{
252    return allocator->avail;
253}
254/* }}} */
255static XC_ALLOCATOR_SIZE(xc_allocator_bestfit_size) /* {{{ */
256{
257    return allocator->size;
258}
259/* }}} */
260
261static XC_ALLOCATOR_FREEBLOCK_FIRST(xc_allocator_bestfit_freeblock_first) /* {{{ */
262{
263    return allocator->headblock->next;
264}
265/* }}} */
266static XC_ALLOCATOR_FREEBLOCK_NEXT(xc_allocator_bestfit_freeblock_next) /* {{{ */
267{
268    return block->next;
269}
270/* }}} */
271static XC_ALLOCATOR_BLOCK_SIZE(xc_allocator_bestfit_block_size) /* {{{ */
272{
273    return block->size;
274}
275/* }}} */
276static XC_ALLOCATOR_BLOCK_OFFSET(xc_allocator_bestfit_block_offset) /* {{{ */
277{
278    return ((char *) block) - ((char *) allocator);
279}
280/* }}} */
281
282static XC_ALLOCATOR_INIT(xc_allocator_bestfit_init) /* {{{ */
283{
284    xc_allocator_bestfit_block_t *b;
285#define MINSIZE (ALIGN(sizeof(xc_allocator_bestfit_t)) + sizeof(xc_allocator_bestfit_block_t))
286    /* requires at least the header and 1 tail block */
287    if (size < MINSIZE) {
288        fprintf(stderr, "xc_allocator_bestfit_init requires %lu bytes at least\n", (unsigned long) MINSIZE);
289        return NULL;
290    }
291    TRACE("size=%lu", size);
292    allocator->shm = shm;
293    allocator->size = size;
294    allocator->avail = size - MINSIZE;
295
296    /* pointer to first block, right after ALIGNed header */
297    b = allocator->headblock;
298    xc_block_setup(b, 0, (xc_allocator_bestfit_block_t *) PADD(allocator, ALIGN(sizeof(xc_allocator_bestfit_t))));
299
300    /* first block*/
301    b = b->next;
302    xc_block_setup(b, allocator->avail, 0);
303#undef MINSIZE
304
305    return allocator;
306}
307/* }}} */
308static XC_ALLOCATOR_DESTROY(xc_allocator_bestfit_destroy) /* {{{ */
309{
310}
311/* }}} */
312
313static xc_allocator_vtable_t xc_allocator_bestfit = XC_ALLOCATOR_VTABLE(allocator_bestfit);
314void xc_allocator_bestfit_register() /* {{{ */
315{
316    if (xc_allocator_register("bestfit", &xc_allocator_bestfit) == 0) {
317        zend_error(E_ERROR, "XCache: failed to register allocator 'bestfit'");
318    }
319}
320/* }}} */
Note: See TracBrowser for help on using the repository browser.