[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] | 33 | struct _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] | 41 | struct _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 | /* }}} */ |
---|
| 60 | static 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] | 70 | static 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] | 82 | static 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] | 180 | static 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] | 223 | static 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] | 234 | static 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] | 244 | static 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] | 253 | static XC_MEM_STRDUP(xc_mem_strdup) /* {{{ */ |
---|
[1] | 254 | { |
---|
| 255 | return xc_mem_strndup(mem, str, strlen(str)); |
---|
| 256 | } |
---|
| 257 | /* }}} */ |
---|
| 258 | |
---|
[148] | 259 | static XC_MEM_AVAIL(xc_mem_avail) /* {{{ */ |
---|
[1] | 260 | { |
---|
| 261 | return mem->avail; |
---|
| 262 | } |
---|
| 263 | /* }}} */ |
---|
[148] | 264 | static XC_MEM_SIZE(xc_mem_size) /* {{{ */ |
---|
[1] | 265 | { |
---|
| 266 | return mem->size; |
---|
| 267 | } |
---|
| 268 | /* }}} */ |
---|
| 269 | |
---|
[148] | 270 | static XC_MEM_FREEBLOCK_FIRST(xc_mem_freeblock_first) /* {{{ */ |
---|
[1] | 271 | { |
---|
| 272 | return mem->headblock->next; |
---|
| 273 | } |
---|
| 274 | /* }}} */ |
---|
[148] | 275 | XC_MEM_FREEBLOCK_NEXT(xc_mem_freeblock_next) /* {{{ */ |
---|
[1] | 276 | { |
---|
| 277 | return block->next; |
---|
| 278 | } |
---|
| 279 | /* }}} */ |
---|
[148] | 280 | XC_MEM_BLOCK_SIZE(xc_mem_block_size) /* {{{ */ |
---|
[1] | 281 | { |
---|
| 282 | return block->size; |
---|
| 283 | } |
---|
| 284 | /* }}} */ |
---|
[148] | 285 | XC_MEM_BLOCK_OFFSET(xc_mem_block_offset) /* {{{ */ |
---|
[1] | 286 | { |
---|
| 287 | return ((char *) block) - ((char *) mem); |
---|
| 288 | } |
---|
| 289 | /* }}} */ |
---|
| 290 | |
---|
[148] | 291 | static 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] | 317 | static XC_MEM_DESTROY(xc_mem_destroy) /* {{{ */ |
---|
[1] | 318 | { |
---|
| 319 | } |
---|
| 320 | /* }}} */ |
---|
[49] | 321 | |
---|
| 322 | #ifdef TEST |
---|
| 323 | /* {{{ */ |
---|
| 324 | #undef CHECK |
---|
| 325 | #define CHECK(a, msg) do { if ((a) == NULL) { puts(msg); return -1; } } while (0) |
---|
| 326 | #include <time.h> |
---|
| 327 | |
---|
| 328 | int 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 | |
---|
| 367 | typedef struct { |
---|
| 368 | const char *name; |
---|
| 369 | const xc_mem_handlers_t *handlers; |
---|
| 370 | } xc_mem_scheme_t; |
---|
| 371 | static xc_mem_scheme_t xc_mem_schemes[10]; |
---|
| 372 | |
---|
| 373 | int 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 | /* }}} */ |
---|
| 386 | const 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 | |
---|
| 398 | static xc_mem_handlers_t xc_mem_mem_handlers = XC_MEM_HANDLERS(mem); |
---|
| 399 | void 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 | /* }}} */ |
---|