apc_sma.c

   1 /*
   2   +----------------------------------------------------------------------+
   3   | APC                                                                  |
   4   +----------------------------------------------------------------------+
   5   | Copyright (c) 2008 The PHP Group                                     |
   6   +----------------------------------------------------------------------+
   7   | This source file is subject to version 3.01 of the PHP license,      |
   8   | that is bundled with this package in the file LICENSE, and is        |
   9   | available through the world-wide-web at the following url:           |
  10   | http://www.php.net/license/3_01.txt                                  |
  11   | If you did not receive a copy of the PHP license and are unable to   |
  12   | obtain it through the world-wide-web, please send a note to          |
  13   | license@php.net so we can mail you a copy immediately.               |
  14   +----------------------------------------------------------------------+
  15   | Authors: Daniel Cowgill <dcowgill@communityconnect.com>              |
  16   |          Rasmus Lerdorf <rasmus@php.net>                             |
  17   +----------------------------------------------------------------------+
  18
  19    This software was contributed to PHP by Community Connect Inc. in 2002
  20    and revised in 2005 by Yahoo! Inc. to add support for PHP 5.1.
  21    Future revisions and derivatives of this source code must acknowledge
  22    Community Connect Inc. as the original contributor of this module by
  23    leaving this note intact in the source code.
  24
  25    All other licensing and usage conditions are those of the PHP Group.
  26
  27  */
  28
  29 /* $Id: apc_sma.c,v 1.69.2.4 2008/05/11 18:57:00 rasmus Exp $ */
  30
  31 #include "apc_sma.h"
  32 #include "apc.h"
  33 #include "apc_globals.h"
  34 #include "apc_lock.h"
  35 #include "apc_shm.h"
  36 #include "apc_cache.h"
  37 #include <limits.h>
  38 #if APC_MMAP
  39 void *apc_mmap(char *file_mask, size_t size);
  40 void apc_unmap(void* shmaddr, size_t size);
  41 #endif
  42
  43 #ifdef HAVE_VALGRIND_MEMCHECK_H
  44 #include <valgrind/memcheck.h>
  45 #endif
  46
  47 /* {{{ locking macros */
  48 #define LOCK(c)         { HANDLE_BLOCK_INTERRUPTIONS(); apc_lck_lock(c); }
  49 #define RDLOCK(c)       { HANDLE_BLOCK_INTERRUPTIONS(); apc_lck_rdlock(c); }
  50 #define UNLOCK(c)       { apc_lck_unlock(c); HANDLE_UNBLOCK_INTERRUPTIONS(); }
  51 /* }}} */
  52
  53 enum { DEFAULT_NUMSEG=1, DEFAULT_SEGSIZE=30*1024*1024 };
  54
  55 static int sma_initialized = 0;     /* true if the sma has been initialized */
  56 static unsigned int sma_numseg;     /* number of shm segments to allow */
  57 static size_t sma_segsize;          /* size of each shm segment */
  58 static size_t* sma_segments;        /* array of shm segment ids */
  59 static void** sma_shmaddrs;         /* array of shm segment addresses */
  60 static int sma_lastseg = 0;         /* index of MRU segment */
  61
  62 typedef struct header_t header_t;
  63 struct header_t {
  64     apc_lck_t sma_lock;     /* segment lock, MUST BE ALIGNED for futex locks */
  65     size_t segsize;         /* size of entire segment */
  66     size_t avail;           /* bytes available (not necessarily contiguous) */
  67     size_t nfoffset;        /* start next fit search from this offset       */
  68 #if ALLOC_DISTRIBUTION
  69     size_t adist[30];
  70 #endif
  71 };
  72
  73
  74 /* do not enable for threaded http servers */
  75 /* #define __APC_SMA_DEBUG__ 1 */
  76
  77 #ifdef __APC_SMA_DEBUG__
  78 /* global counter for identifying blocks
  79  * Technically it is possible to do the same
  80  * using offsets, but double allocations of the
  81  * same offset can happen. */
  82 static volatile size_t block_id = 0;
  83 #endif
  84
  85 #define APC_SMA_CANARIES 1
  86
  87 typedef struct block_t block_t;
  88 struct block_t {
  89     size_t size;       /* size of this block */
  90     size_t next;       /* offset in segment of next free block */
  91 #ifdef APC_SMA_CANARIES
  92     size_t canary;     /* canary to check for memory overwrites */
  93 #endif
  94 #ifdef __APC_SMA_DEBUG__
  95     size_t id;         /* identifier for the memory block */
  96 #endif
  97 };
  98
  99 /* The macros BLOCKAT and OFFSET are used for convenience throughout this
 100  * module. Both assume the presence of a variable shmaddr that points to the
 101  * beginning of the shared memory segment in question. */
 102
 103 #define BLOCKAT(offset) ((block_t*)((char *)shmaddr + offset))
 104 #define OFFSET(block) ((size_t)(((char*)block) - (char*)shmaddr))
 105
 106 /* Canary macros for setting, checking and resetting memory canaries */
 107 #ifdef APC_SMA_CANARIES
 108     #define SET_CANARY(v) (v)->canary = 0x42424242
 109     #define CHECK_CANARY(v) assert((v)->canary == 0x42424242)
 110     #define RESET_CANARY(v) (v)->canary = -42
 111 #else
 112     #define SET_CANARY(v)
 113     #define CHECK_CANARY(v)
 114     #define RESET_CANARY(v)
 115 #endif
 116
 117
 118 /* {{{ MINBLOCKSIZE */
 119 #define MINBLOCKSIZE (ALIGNWORD(1) + ALIGNWORD(sizeof(block_t)))
 120 /* }}} */
 121
 122 /* {{{ sma_allocate: tries to allocate size bytes in a segment */
 123 static size_t sma_allocate(void* shmaddr, size_t size)
 124 {
 125     header_t* header;       /* header of shared memory segment */
 126     block_t* prv;           /* block prior to working block */
 127     block_t* cur;           /* working block in list */
 128     block_t* prvnextfit;    /* block before next fit */
 129     size_t realsize;        /* actual size of block needed, including header */
 130     size_t last_offset;     /* save the last search offset */
 131     int wrapped=0;
 132     const size_t block_size = ALIGNWORD(sizeof(struct block_t));
 133
 134     realsize = ALIGNWORD(size + block_size);
 135
 136     /*
 137      * First, insure that the segment contains at least realsize free bytes,
 138      * even if they are not contiguous.
 139      */
 140     header = (header_t*) shmaddr;
 141     if (header->avail < realsize) {
 142         return -1;
 143     }
 144
 145     prvnextfit = 0;     /* initially null (no fit) */
 146     last_offset = 0;
 147
 148     /* If we have a next fit offset, start searching from there */
 149     if(header->nfoffset) {
 150         prv = BLOCKAT(header->nfoffset);
 151         /* if prv is the last block, jump to the beginning */
 152         if(prv->next == 0) {
 153             prv = BLOCKAT(ALIGNWORD(sizeof(header_t)));
 154             wrapped = 1;
 155         }
 156     } else {
 157         prv = BLOCKAT(ALIGNWORD(sizeof(header_t)));
 158     }
 159
 160     CHECK_CANARY(prv);
 161
 162     while (prv->next != header->nfoffset) {
 163         cur = BLOCKAT(prv->next);
 164 #ifdef __APC_SMA_DEBUG__
 165         CHECK_CANARY(cur);
 166 #endif
 167         /* If it can fit realiszie bytes in cur block, stop searching */
 168         if (cur->size >= realsize) {
 169             prvnextfit = prv;
 170             break;
 171         }
 172         last_offset = prv->next;
 173         prv = cur;
 174         if(wrapped && (prv->next >= header->nfoffset)) break;
 175
 176         /* Check to see if we need to wrap around and search from the top */
 177         if(header->nfoffset && prv->next == 0) {
 178             prv = BLOCKAT(ALIGNWORD(sizeof(header_t)));
 179 #ifdef __APC_SMA_DEBUG__
 180             CHECK_CANARY(prv);
 181 #endif
 182             last_offset = 0;
 183             wrapped = 1;
 184         }
 185     }
 186
 187     if (prvnextfit == 0) {
 188         header->nfoffset = 0;
 189         return -1;
 190     }
 191
 192     prv = prvnextfit;
 193     cur = BLOCKAT(prv->next);
 194
 195     CHECK_CANARY(prv);
 196     CHECK_CANARY(cur);
 197
 198     if (cur->size == realsize || (cur->size > realsize && cur->size < (realsize + (MINBLOCKSIZE * 2)))) {
 199         /* cur is big enough for realsize, but too small to split - unlink it */
 200         prv->next = cur->next;
 201     }
 202     else {
 203         block_t* nxt;      /* the new block (chopped part of cur) */
 204         size_t nxtoffset;  /* offset of the block currently after cur */
 205         size_t oldsize;    /* size of cur before split */
 206
 207         /* nextfit is too big; split it into two smaller blocks */
 208         nxtoffset = cur->next;
 209         oldsize = cur->size;
 210         prv->next += realsize;  /* skip over newly allocated block */
 211         cur->size = realsize;   /* Set the size of this new block */
 212         nxt = BLOCKAT(prv->next);
 213         nxt->next = nxtoffset;  /* Re-link the shortened block */
 214         nxt->size = oldsize - realsize;  /* and fix the size */
 215         SET_CANARY(nxt);
 216 #ifdef __APC_SMA_DEBUG__
 217         nxt->id = -1;
 218 #endif
 219     }
 220
 221     /* update the block header */
 222     header->avail -= cur->size;
 223 #if ALLOC_DISTRIBUTION
 224     header->adist[(int)(log(size)/log(2))]++;
 225 #endif
 226
 227     header->nfoffset = last_offset;
 228
 229     SET_CANARY(cur);
 230 #ifdef __APC_SMA_DEBUG__
 231     cur->id = ++block_id;
 232     fprintf(stderr, "allocate(realsize=%d,size=%d,id=%d)\n", (int)(size), (int)(cur->size), cur->id);
 233 #endif
 234
 235     return OFFSET(cur) + block_size;
 236 }
 237 /* }}} */
 238
 239 /* {{{ sma_deallocate: deallocates the block at the given offset */
 240 static size_t sma_deallocate(void* shmaddr, size_t offset)
 241 {
 242     header_t* header;   /* header of shared memory segment */
 243     block_t* cur;       /* the new block to insert */
 244     block_t* prv;       /* the block before cur */
 245     block_t* nxt;       /* the block after cur */
 246     size_t size;        /* size of deallocated block */
 247
 248     offset -= ALIGNWORD(sizeof(struct block_t));
 249     assert(offset >= 0);
 250
 251     /* find position of new block in free list */
 252     cur = BLOCKAT(offset);
 253     prv = BLOCKAT(ALIGNWORD(sizeof(header_t)));
 254
 255     CHECK_CANARY(cur);
 256
 257 #ifdef __APC_SMA_DEBUG__
 258     CHECK_CANARY(prv);
 259     fprintf(stderr, "free(%p, size=%d,id=%d)\n", cur, (int)(cur->size), cur->id);
 260 #endif
 261     while (prv->next != 0 && prv->next < offset) {
 262         prv = BLOCKAT(prv->next);
 263 #ifdef __APC_SMA_DEBUG__
 264         CHECK_CANARY(prv);
 265 #endif
 266     }
 267
 268     CHECK_CANARY(prv);
 269
 270     /* insert new block after prv */
 271     cur->next = prv->next;
 272     prv->next = offset;
 273
 274 #ifdef __APC_SMA_DEBUG__
 275     CHECK_CANARY(cur);
 276     cur->id = -1;
 277 #endif
 278
 279     /* update the block header */
 280     header = (header_t*) shmaddr;
 281     header->avail += cur->size;
 282     size = cur->size;
 283
 284     if (((char *)prv) + prv->size == (char *) cur) {
 285         /* cur and prv share an edge, combine them */
 286         prv->size += cur->size;
 287         prv->next = cur->next;
 288         RESET_CANARY(cur);
 289         cur = prv;
 290     }
 291
 292     nxt = BLOCKAT(cur->next);
 293
 294     if (((char *)cur) + cur->size == (char *) nxt) {
 295         /* cur and nxt shared an edge, combine them */
 296         cur->size += nxt->size;
 297         cur->next = nxt->next;
 298 #ifdef __APC_SMA_DEBUG__
 299         CHECK_CANARY(nxt);
 300         nxt->id = -1; /* assert this or set it ? */
 301 #endif
 302         RESET_CANARY(nxt);
 303     }
 304     header->nfoffset = 0;  /* Reset the next fit search marker */
 305
 306     return size;
 307 }
 308 /* }}} */
 309
 310 /* {{{ apc_sma_init */
 311
 312 void apc_sma_init(int numseg, size_t segsize, char *mmap_file_mask)
 313 {
 314     int i;
 315
 316     if (sma_initialized) {
 317         return;
 318     }
 319     sma_initialized = 1;
 320
 321 #if APC_MMAP
 322     /*
 323      * I don't think multiple anonymous mmaps makes any sense
 324      * so force sma_numseg to 1 in this case
 325      */
 326     if(!mmap_file_mask ||
 327        (mmap_file_mask && !strlen(mmap_file_mask)) ||
 328        (mmap_file_mask && !strcmp(mmap_file_mask, "/dev/zero"))) {
 329         sma_numseg = 1;
 330     } else {
 331         sma_numseg = numseg > 0 ? numseg : DEFAULT_NUMSEG;
 332     }
 333 #else
 334     sma_numseg = numseg > 0 ? numseg : DEFAULT_NUMSEG;
 335 #endif
 336
 337     sma_segsize = segsize > 0 ? segsize : DEFAULT_SEGSIZE;
 338
 339     sma_segments = (size_t*) apc_emalloc(sma_numseg*sizeof(size_t));
 340     sma_shmaddrs = (void**) apc_emalloc(sma_numseg*sizeof(void*));
 341
 342     for (i = 0; i < sma_numseg; i++) {
 343         header_t*   header;
 344         block_t*    block;
 345         void*       shmaddr;
 346
 347 #if APC_MMAP
 348         sma_segments[i] = sma_segsize;
 349         sma_shmaddrs[i] = apc_mmap(mmap_file_mask, sma_segsize);
 350         if(sma_numseg != 1) memcpy(&mmap_file_mask[strlen(mmap_file_mask)-6], "XXXXXX", 6);
 351 #else
 352         sma_segments[i] = apc_shm_create(NULL, i, sma_segsize);
 353         sma_shmaddrs[i] = apc_shm_attach(sma_segments[i]);
 354 #endif
 355         shmaddr = sma_shmaddrs[i];
 356
 357         header = (header_t*) shmaddr;
 358         apc_lck_create(NULL, 0, 1, header->sma_lock);
 359         header->segsize = sma_segsize;
 360         header->avail = sma_segsize - ALIGNWORD(sizeof(header_t)) - ALIGNWORD(sizeof(block_t));
 361         header->nfoffset = 0;
 362 #if ALLOC_DISTRIBUTION
 363         {
 364            int j;
 365            for(j=0; j<30; j++) header->adist[j] = 0;
 366         }
 367 #endif
 368         block = BLOCKAT(ALIGNWORD(sizeof(header_t)));
 369         block->size = 0;
 370         block->next = ALIGNWORD(sizeof(header_t)) + ALIGNWORD(sizeof(block_t));
 371         SET_CANARY(block);
 372 #ifdef __APC_SMA_DEBUG__
 373         block->id = -1;
 374 #endif
 375         block = BLOCKAT(block->next);
 376         block->size = header->avail;
 377         block->next = 0;
 378         SET_CANARY(block);
 379 #ifdef __APC_SMA_DEBUG__
 380         block->id = -1;
 381 #endif
 382     }
 383 }
 384 /* }}} */
 385
 386 /* {{{ apc_sma_cleanup */
 387 void apc_sma_cleanup()
 388 {
 389     int i;
 390
 391     assert(sma_initialized);
 392
 393     for (i = 0; i < sma_numseg; i++) {
 394         apc_lck_destroy(((header_t*)sma_shmaddrs[i])->sma_lock);
 395 #if APC_MMAP
 396         apc_unmap(sma_shmaddrs[i], sma_segments[i]);
 397 #else
 398         apc_shm_detach(sma_shmaddrs[i]);
 399 #endif
 400     }
 401     sma_initialized = 0;
 402     apc_efree(sma_segments);
 403     apc_efree(sma_shmaddrs);
 404 }
 405 /* }}} */
 406
 407 /* {{{ apc_sma_malloc */
 408 void* apc_sma_malloc(size_t n)
 409 {
 410     size_t off;
 411     int i;
 412
 413     TSRMLS_FETCH();
 414     assert(sma_initialized);
 415     LOCK(((header_t*)sma_shmaddrs[sma_lastseg])->sma_lock);
 416
 417     off = sma_allocate(sma_shmaddrs[sma_lastseg], n);
 418     if (off != -1) {
 419         void* p = (void *)(((char *)(sma_shmaddrs[sma_lastseg])) + off);
 420         if (APCG(mem_size_ptr) != NULL) { *(APCG(mem_size_ptr)) += n; }
 421         UNLOCK(((header_t*)sma_shmaddrs[sma_lastseg])->sma_lock);
 422 #ifdef VALGRIND_MALLOCLIKE_BLOCK
 423         VALGRIND_MALLOCLIKE_BLOCK(p, n, 0, 0);
 424 #endif
 425         return p;
 426     }
 427     UNLOCK(((header_t*)sma_shmaddrs[sma_lastseg])->sma_lock);
 428
 429     for (i = 0; i < sma_numseg; i++) {
 430         if (i == sma_lastseg) {
 431             continue;
 432         }
 433         LOCK(((header_t*)sma_shmaddrs[i])->sma_lock);
 434         off = sma_allocate(sma_shmaddrs[i], n);
 435         if (off != -1) {
 436             void* p = (void *)(((char *)(sma_shmaddrs[i])) + off);
 437             if (APCG(mem_size_ptr) != NULL) { *(APCG(mem_size_ptr)) += n; }
 438             UNLOCK(((header_t*)sma_shmaddrs[i])->sma_lock);
 439             sma_lastseg = i;
 440 #ifdef VALGRIND_MALLOCLIKE_BLOCK
 441             VALGRIND_MALLOCLIKE_BLOCK(p, n, 0, 0);
 442 #endif
 443             return p;
 444         }
 445         UNLOCK(((header_t*)sma_shmaddrs[i])->sma_lock);
 446     }
 447
 448     return NULL;
 449 }
 450 /* }}} */
 451
 452 /* {{{ apc_sma_realloc */
 453 void* apc_sma_realloc(void *p, size_t n)
 454 {
 455     apc_sma_free(p);
 456     return apc_sma_malloc(n);
 457 }
 458 /* }}} */
 459
 460 /* {{{ apc_sma_strdup */
 461 char* apc_sma_strdup(const char* s)
 462 {
 463     void* q;
 464     int len;
 465
 466     if(!s) return NULL;
 467
 468     len = strlen(s)+1;
 469     q = apc_sma_malloc(len);
 470     if(!q) return NULL;
 471     memcpy(q, s, len);
 472     return q;
 473 }
 474 /* }}} */
 475
 476 /* {{{ apc_sma_free */
 477 void apc_sma_free(void* p)
 478 {
 479     int i;
 480     size_t offset;
 481     size_t d_size;
 482     TSRMLS_FETCH();
 483
 484     if (p == NULL) {
 485         return;
 486     }
 487
 488     assert(sma_initialized);
 489
 490     for (i = 0; i < sma_numseg; i++) {
 491         LOCK(((header_t*)sma_shmaddrs[i])->sma_lock);
 492         offset = (size_t)((char *)p - (char *)(sma_shmaddrs[i]));
 493         if (p >= sma_shmaddrs[i] && offset < sma_segsize) {
 494             d_size = sma_deallocate(sma_shmaddrs[i], offset);
 495             if (APCG(mem_size_ptr) != NULL) { *(APCG(mem_size_ptr)) -= d_size; }
 496             UNLOCK(((header_t*)sma_shmaddrs[i])->sma_lock);
 497 #ifdef VALGRIND_FREELIKE_BLOCK
 498             VALGRIND_FREELIKE_BLOCK(p, 0);
 499 #endif
 500             return;
 501         }
 502         UNLOCK(((header_t*)sma_shmaddrs[i])->sma_lock);
 503     }
 504
 505     apc_eprint("apc_sma_free: could not locate address %p", p);
 506 }
 507 /* }}} */
 508
 509 /* {{{ apc_sma_info */
 510 apc_sma_info_t* apc_sma_info(zend_bool limited)
 511 {
 512     apc_sma_info_t* info;
 513     apc_sma_link_t** link;
 514     int i;
 515         char* shmaddr;
 516         block_t* prv;
 517
 518     if (!sma_initialized) {
 519         return NULL;
 520     }
 521
 522     info = (apc_sma_info_t*) apc_emalloc(sizeof(apc_sma_info_t));
 523     info->num_seg = sma_numseg;
 524     info->seg_size = sma_segsize - ALIGNWORD(sizeof(header_t)) - ALIGNWORD(sizeof(block_t));
 525
 526     info->list = apc_emalloc(info->num_seg * sizeof(apc_sma_link_t*));
 527     for (i = 0; i < sma_numseg; i++) {
 528         info->list[i] = NULL;
 529     }
 530
 531     if(limited) return info;
 532
 533     /* For each segment */
 534     for (i = 0; i < sma_numseg; i++) {
 535         RDLOCK(((header_t*)sma_shmaddrs[i])->sma_lock);
 536         shmaddr = sma_shmaddrs[i];
 537         prv = BLOCKAT(ALIGNWORD(sizeof(header_t)));
 538
 539         link = &info->list[i];
 540
 541         /* For each block in this segment */
 542         while (prv->next != 0) {
 543             block_t* cur = BLOCKAT(prv->next);
 544 #ifdef __APC_SMA_DEBUG__
 545             CHECK_CANARY(cur);
 546 #endif
 547
 548             *link = apc_emalloc(sizeof(apc_sma_link_t));
 549             (*link)->size = cur->size;
 550             (*link)->offset = prv->next;
 551             (*link)->next = NULL;
 552             link = &(*link)->next;
 553
 554             prv = cur;
 555         }
 556         UNLOCK(((header_t*)sma_shmaddrs[i])->sma_lock);
 557     }
 558
 559     return info;
 560 }
 561 /* }}} */
 562
 563 /* {{{ apc_sma_free_info */
 564 void apc_sma_free_info(apc_sma_info_t* info)
 565 {
 566     int i;
 567
 568     for (i = 0; i < info->num_seg; i++) {
 569         apc_sma_link_t* p = info->list[i];
 570         while (p) {
 571             apc_sma_link_t* q = p;
 572             p = p->next;
 573             apc_efree(q);
 574         }
 575     }
 576     apc_efree(info->list);
 577     apc_efree(info);
 578 }
 579 /* }}} */
 580
 581 /* {{{ apc_sma_get_avail_mem */
 582 size_t apc_sma_get_avail_mem()
 583 {
 584     size_t avail_mem = 0;
 585     int i;
 586
 587     for (i = 0; i < sma_numseg; i++) {
 588         header_t* header = (header_t*) sma_shmaddrs[i];
 589         avail_mem += header->avail;
 590     }
 591     return avail_mem;
 592 }
 593 /* }}} */
 594
 595 #if ALLOC_DISTRIBUTION
 596 size_t *apc_sma_get_alloc_distribution(void) {
 597     header_t* header = (header_t*) sma_shmaddrs[0];
 598     return header->adist;
 599 }
 600 #endif
 601
 602 #if 0
 603 /* {{{ apc_sma_check_integrity */
 604 void apc_sma_check_integrity()
 605 {
 606     int i;
 607
 608     /* For each segment */
 609     for (i = 0; i < sma_numseg; i++) {
 610         char* shmaddr = sma_shmaddrs[i];
 611         header_t* header = (header_t*) shmaddr;
 612         block_t* prv = BLOCKAT(ALIGNWORD(sizeof(header_t)));
 613         int avail = 0;
 614
 615         /* For each block in this segment */
 616         while (prv->next != 0) {
 617             block_t* cur = BLOCKAT(prv->next);
 618             avail += cur->size;
 619             prv = cur;
 620         }
 621
 622         assert(avail == header->avail);
 623     }
 624 }
 625 /* }}} */
 626 #endif
 627
 628 /*
 629  * Local variables:
 630  * tab-width: 4
 631  * c-basic-offset: 4
 632  * End:
 633  * vim600: expandtab sw=4 ts=4 sts=4 fdm=marker
 634  * vim<600: expandtab sw=4 ts=4 sts=4
 635  */