Changeset 1135 in svn for trunk/xcache/xc_allocator.c


Ignore:
Timestamp:
2012-08-09T09:04:02Z (3 years ago)
Author:
Xuefer
Message:

refactor: s/mem/allocator/

Location:
trunk
Files:
1 edited
1 moved

Legend:

Unmodified
Added
Removed
  • trunk

    • Property svn:ignore
      •  

        old new  
        11acinclude.m4
        22aclocal.m4
         3allocator_test
        34autom4te.cache
        45build
         
        1617conftest.c
        1718.deps
         19devel.fpm
        1820devel.ini
        1921devel.php
        20 devel.fpm
        2122.gdb_history
        2223include
  • trunk/xcache/xc_allocator.c

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