apc_sma.c

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