source: trunk/xcache/xc_allocator_bestfit.c @ 1385

Last change on this file since 1385 was 1385, checked in by moo, 11 months ago

readonly protection for copied array

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