nginx/src/core/ngx_slab.c

   1
   2 /*
   3  * Copyright (C) Igor Sysoev
   4  */
   5
   6 #include <ngx_config.h>
   7 #include <ngx_core.h>
   8
   9 /*
  10
  11                          12
  12     2048   2             11
  13     1024   4             10
  14     512    8             9
  15     256   16             8
  16
  17     128   32   4   32    7
  18
  19     64    64   8   63    6      1
  20     32   128  16  127    5      1
  21     16   256  32  254    4      2
  22     8    512  64  504    3      8
  23
  24  */
  25
  26
  27 #define NGX_SLAB_PAGE_MASK   3
  28 #define NGX_SLAB_PAGE        0
  29 #define NGX_SLAB_BIG         1
  30 #define NGX_SLAB_EXACT       2
  31 #define NGX_SLAB_SMALL       3
  32
  33 #if (NGX_PTR_SIZE == 4)
  34
  35 #define NGX_SLAB_PAGE_FREE   0
  36 #define NGX_SLAB_PAGE_BUSY   0xffffffff
  37 #define NGX_SLAB_PAGE_START  0x80000000
  38
  39 #define NGX_SLAB_SHIFT_MASK  0x0000000f
  40 #define NGX_SLAB_MAP_MASK    0xffff0000
  41 #define NGX_SLAB_MAP_SHIFT   16
  42
  43 #define NGX_SLAB_BUSY        0xffffffff
  44
  45 #else /* (NGX_PTR_SIZE == 8) */
  46
  47 #define NGX_SLAB_PAGE_FREE   0
  48 #define NGX_SLAB_PAGE_BUSY   0xffffffffffffffff
  49 #define NGX_SLAB_PAGE_START  0x8000000000000000
  50
  51 #define NGX_SLAB_SHIFT_MASK  0x000000000000000f
  52 #define NGX_SLAB_MAP_MASK    0xffffffff00000000
  53 #define NGX_SLAB_MAP_SHIFT   32
  54
  55 #define NGX_SLAB_BUSY        0xffffffffffffffff
  56
  57 #endif
  58
  59
  60 #if (NGX_DEBUG_MALLOC)
  61
  62 #define ngx_slab_junk(p, size)     ngx_memset(p, 0xD0, size)
  63
  64 #else
  65
  66 #if (NGX_FREEBSD)
  67
  68 #define ngx_slab_junk(p, size)                                                \
  69     if (ngx_freebsd_debug_malloc)  ngx_memset(p, 0xD0, size)
  70
  71 #else
  72
  73 #define ngx_slab_junk(p, size)
  74
  75 #endif
  76
  77 #endif
  78
  79 static ngx_slab_page_t *ngx_slab_alloc_pages(ngx_slab_pool_t *pool,
  80     ngx_uint_t pages);
  81 static void ngx_slab_free_pages(ngx_slab_pool_t *pool, ngx_slab_page_t *page,
  82     ngx_uint_t pages);
  83
  84
  85 static ngx_uint_t  ngx_slab_max_size;
  86 static ngx_uint_t  ngx_slab_exact_size;
  87 static ngx_uint_t  ngx_slab_exact_shift;
  88
  89
  90 void
  91 ngx_slab_init(ngx_slab_pool_t *pool)
  92 {
  93     u_char           *p;
  94     size_t            size;
  95     ngx_int_t         m;
  96     ngx_uint_t        i, n, pages;
  97     ngx_slab_page_t  *slots;
  98
  99     /* STUB */
 100     if (ngx_slab_max_size == 0) {
 101         ngx_slab_max_size = ngx_pagesize / 2;
 102         ngx_slab_exact_size = ngx_pagesize / (8 * sizeof(uintptr_t));
 103         for (n = ngx_slab_exact_size; n >>= 1; ngx_slab_exact_shift++) {
 104             /* void */
 105         }
 106     }
 107     /**/
 108
 109     pool->min_size = 1 << pool->min_shift;
 110
 111     p = (u_char *) pool + sizeof(ngx_slab_pool_t);
 112     size = pool->end - p;
 113
 114     ngx_slab_junk(p, size);
 115
 116     slots = (ngx_slab_page_t *) p;
 117     n = ngx_pagesize_shift - pool->min_shift;
 118
 119     for (i = 0; i < n; i++) {
 120         slots[i].slab = 0;
 121         slots[i].next = &slots[i];
 122         slots[i].prev = 0;
 123     }
 124
 125     p += n * sizeof(ngx_slab_page_t);
 126
 127     pages = (ngx_uint_t) (size / (ngx_pagesize + sizeof(ngx_slab_page_t)));
 128
 129     ngx_memzero(p, pages * sizeof(ngx_slab_page_t));
 130
 131     pool->pages = (ngx_slab_page_t *) p;
 132
 133     pool->free.prev = 0;
 134     pool->free.next = (ngx_slab_page_t *) p;
 135
 136     pool->pages->slab = pages;
 137     pool->pages->next = &pool->free;
 138     pool->pages->prev = (uintptr_t) &pool->free;
 139
 140     pool->start = (u_char *)
 141                   ngx_align_ptr((uintptr_t) p + pages * sizeof(ngx_slab_page_t),
 142                                  ngx_pagesize);
 143
 144     m = pages - (pool->end - pool->start) / ngx_pagesize;
 145     if (m > 0) {
 146         pages -= m;
 147         pool->pages->slab = pages;
 148     }
 149
 150 #if 0
 151     ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "slab: %p, %p, %ui, %d",
 152                   pool, pool->start, pages,
 153                   (pool->end - pool->start) / ngx_pagesize - pages);
 154 #endif
 155 }
 156
 157
 158 void *
 159 ngx_slab_alloc(ngx_slab_pool_t *pool, size_t size)
 160 {
 161     void  *p;
 162
 163     ngx_shmtx_lock(&pool->mutex);
 164
 165     p = ngx_slab_alloc_locked(pool, size);
 166
 167     ngx_shmtx_unlock(&pool->mutex);
 168
 169     return p;
 170 }
 171
 172
 173 void *
 174 ngx_slab_alloc_locked(ngx_slab_pool_t *pool, size_t size)
 175 {
 176     size_t            s;
 177     uintptr_t         p, n, m, mask, *bitmap;
 178     ngx_uint_t        i, slot, shift, map;
 179     ngx_slab_page_t  *page, *prev, *slots;
 180
 181     if (size >= ngx_slab_max_size) {
 182
 183         ngx_log_debug1(NGX_LOG_DEBUG_ALLOC, ngx_cycle->log, 0,
 184                        "slab alloc: %uz", size);
 185
 186         page = ngx_slab_alloc_pages(pool, (size + ngx_pagesize - 1)
 187                                           >> ngx_pagesize_shift);
 188         if (page) {
 189             p = (page - pool->pages) << ngx_pagesize_shift;
 190             p += (uintptr_t) pool->start;
 191
 192         } else {
 193             p = 0;
 194         }
 195
 196         goto done;
 197     }
 198
 199     if (size > pool->min_size) {
 200         shift = 1;
 201         for (s = size - 1; s >>= 1; shift++) { /* void */ }
 202         slot = shift - pool->min_shift;
 203
 204     } else {
 205         size = pool->min_size;
 206         shift = pool->min_shift;
 207         slot = 0;
 208     }
 209
 210     ngx_log_debug2(NGX_LOG_DEBUG_ALLOC, ngx_cycle->log, 0,
 211                    "slab alloc: %uz slot: %ui", size, slot);
 212
 213     slots = (ngx_slab_page_t *) ((u_char *) pool + sizeof(ngx_slab_pool_t));
 214     page = slots[slot].next;
 215
 216     if (page->next != page) {
 217
 218         if (shift < ngx_slab_exact_shift) {
 219
 220             do {
 221                 p = (page - pool->pages) << ngx_pagesize_shift;
 222                 bitmap = (uintptr_t *) (pool->start + p);
 223
 224                 map = (1 << (ngx_pagesize_shift - shift))
 225                           / (sizeof(uintptr_t) * 8);
 226
 227                 for (n = 0; n < map; n++) {
 228
 229                     if (bitmap[n] != NGX_SLAB_BUSY) {
 230
 231                         for (m = 1, i = 0; m; m <<= 1, i++) {
 232                             if ((bitmap[n] & m)) {
 233                                 continue;
 234                             }
 235
 236                             bitmap[n] |= m;
 237
 238                             i = ((n * sizeof(uintptr_t) * 8) << shift)
 239                                 + (i << shift);
 240
 241                             if (bitmap[n] == NGX_SLAB_BUSY) {
 242                                 for (n = n + 1; n < map; n++) {
 243                                      if (bitmap[n] != NGX_SLAB_BUSY) {
 244                                          p = (uintptr_t) bitmap + i;
 245
 246                                          goto done;
 247                                      }
 248                                 }
 249
 250                                 prev = (ngx_slab_page_t *)
 251                                             (page->prev & ~NGX_SLAB_PAGE_MASK);
 252                                 prev->next = page->next;
 253                                 page->next->prev = page->prev;
 254
 255                                 page->next = NULL;
 256                                 page->prev = NGX_SLAB_SMALL;
 257                             }
 258
 259                             p = (uintptr_t) bitmap + i;
 260
 261                             goto done;
 262                         }
 263                     }
 264                 }
 265
 266                 page = page->next;
 267
 268             } while (page);
 269
 270         } else if (shift == ngx_slab_exact_shift) {
 271
 272             do {
 273                 if (page->slab != NGX_SLAB_BUSY) {
 274
 275                     for (m = 1, i = 0; m; m <<= 1, i++) {
 276                         if ((page->slab & m)) {
 277                             continue;
 278                         }
 279
 280                         page->slab |= m;
 281
 282                         if (page->slab == NGX_SLAB_BUSY) {
 283                             prev = (ngx_slab_page_t *)
 284                                             (page->prev & ~NGX_SLAB_PAGE_MASK);
 285                             prev->next = page->next;
 286                             page->next->prev = page->prev;
 287
 288                             page->next = NULL;
 289                             page->prev = NGX_SLAB_EXACT;
 290                         }
 291
 292                         p = (page - pool->pages) << ngx_pagesize_shift;
 293                         p += i << shift;
 294                         p += (uintptr_t) pool->start;
 295
 296                         goto done;
 297                     }
 298                 }
 299
 300                 page = page->next;
 301
 302             } while (page);
 303
 304         } else { /* shift > ngx_slab_exact_shift */
 305
 306             n = ngx_pagesize_shift - (page->slab & NGX_SLAB_SHIFT_MASK);
 307             n = 1 << n;
 308             n = ((uintptr_t) 1 << n) - 1;
 309             mask = n << NGX_SLAB_MAP_SHIFT;
 310
 311             do {
 312                 if ((page->slab & NGX_SLAB_MAP_MASK) != mask) {
 313
 314                     for (m = (uintptr_t) 1 << NGX_SLAB_MAP_SHIFT, i = 0;
 315                          m & mask;
 316                          m <<= 1, i++)
 317                     {
 318                         if ((page->slab & m)) {
 319                             continue;
 320                         }
 321
 322                         page->slab |= m;
 323
 324                         if ((page->slab & NGX_SLAB_MAP_MASK) == mask) {
 325                             prev = (ngx_slab_page_t *)
 326                                             (page->prev & ~NGX_SLAB_PAGE_MASK);
 327                             prev->next = page->next;
 328                             page->next->prev = page->prev;
 329
 330                             page->next = NULL;
 331                             page->prev = NGX_SLAB_BIG;
 332                         }
 333
 334                         p = (page - pool->pages) << ngx_pagesize_shift;
 335                         p += i << shift;
 336                         p += (uintptr_t) pool->start;
 337
 338                         goto done;
 339                     }
 340                 }
 341
 342                 page = page->next;
 343
 344             } while (page);
 345         }
 346     }
 347
 348     page = ngx_slab_alloc_pages(pool, 1);
 349
 350     if (page) {
 351         if (shift < ngx_slab_exact_shift) {
 352             p = (page - pool->pages) << ngx_pagesize_shift;
 353             bitmap = (uintptr_t *) (pool->start + p);
 354
 355             s = 1 << shift;
 356             n = (1 << (ngx_pagesize_shift - shift)) / 8 / s;
 357
 358             if (n == 0) {
 359                 n = 1;
 360             }
 361
 362             bitmap[0] = (2 << n) - 1;
 363
 364             map = (1 << (ngx_pagesize_shift - shift)) / (sizeof(uintptr_t) * 8);
 365
 366             for (i = 1; i < map; i++) {
 367                 bitmap[i] = 0;
 368             }
 369
 370             page->slab = shift;
 371             page->next = &slots[slot];
 372             page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_SMALL;
 373
 374             slots[slot].next = page;
 375
 376             p = ((page - pool->pages) << ngx_pagesize_shift) + s * n;
 377             p += (uintptr_t) pool->start;
 378
 379             goto done;
 380
 381         } else if (shift == ngx_slab_exact_shift) {
 382
 383             page->slab = 1;
 384             page->next = &slots[slot];
 385             page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_EXACT;
 386
 387             slots[slot].next = page;
 388
 389             p = (page - pool->pages) << ngx_pagesize_shift;
 390             p += (uintptr_t) pool->start;
 391
 392             goto done;
 393
 394         } else { /* shift > ngx_slab_exact_shift */
 395
 396             page->slab = ((uintptr_t) 1 << NGX_SLAB_MAP_SHIFT) | shift;
 397             page->next = &slots[slot];
 398             page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_BIG;
 399
 400             slots[slot].next = page;
 401
 402             p = (page - pool->pages) << ngx_pagesize_shift;
 403             p += (uintptr_t) pool->start;
 404
 405             goto done;
 406         }
 407     }
 408
 409     p = 0;
 410
 411 done:
 412
 413     ngx_log_debug1(NGX_LOG_DEBUG_ALLOC, ngx_cycle->log, 0, "slab alloc: %p", p);
 414
 415     return (void *) p;
 416 }
 417
 418
 419 void
 420 ngx_slab_free(ngx_slab_pool_t *pool, void *p)
 421 {
 422     ngx_shmtx_lock(&pool->mutex);
 423
 424     ngx_slab_free_locked(pool, p);
 425
 426     ngx_shmtx_unlock(&pool->mutex);
 427 }
 428
 429
 430 void
 431 ngx_slab_free_locked(ngx_slab_pool_t *pool, void *p)
 432 {
 433     size_t            size;
 434     uintptr_t         slab, m, *bitmap;
 435     ngx_uint_t        n, type, slot, shift, map;
 436     ngx_slab_page_t  *slots, *page;
 437
 438     ngx_log_debug1(NGX_LOG_DEBUG_ALLOC, ngx_cycle->log, 0, "slab free: %p", p);
 439
 440     if ((u_char *) p < pool->start || (u_char *) p > pool->end) {
 441         ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0,
 442                       "ngx_slab_free(): outside of pool");
 443         goto fail;
 444     }
 445
 446     n = ((u_char *) p - pool->start) >> ngx_pagesize_shift;
 447     page = &pool->pages[n];
 448     slab = page->slab;
 449     type = page->prev & NGX_SLAB_PAGE_MASK;
 450
 451     switch (type) {
 452
 453     case NGX_SLAB_SMALL:
 454
 455         shift = slab & NGX_SLAB_SHIFT_MASK;
 456         size = 1 << shift;
 457
 458         if ((uintptr_t) p & (size - 1)) {
 459             goto wrong_chunk;
 460         }
 461
 462         n = ((uintptr_t) p & (ngx_pagesize - 1)) >> shift;
 463         m = (uintptr_t) 1 << (n & (sizeof(uintptr_t) * 8 - 1));
 464         n /= (sizeof(uintptr_t) * 8);
 465         bitmap = (uintptr_t *) ((uintptr_t) p & ~(ngx_pagesize - 1));
 466
 467         if (bitmap[n] & m) {
 468
 469             if (page->next == NULL) {
 470                 slots = (ngx_slab_page_t *)
 471                                    ((u_char *) pool + sizeof(ngx_slab_pool_t));
 472                 slot = shift - pool->min_shift;
 473
 474                 page->next = slots[slot].next;
 475                 slots[slot].next = page;
 476
 477                 page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_SMALL;
 478                 page->next->prev = (uintptr_t) page | NGX_SLAB_SMALL;
 479             }
 480
 481             bitmap[n] &= ~m;
 482
 483             n = (1 << (ngx_pagesize_shift - shift)) / 8 / (1 << shift);
 484
 485             if (n == 0) {
 486                 n = 1;
 487             }
 488
 489             if (bitmap[0] & ~(((uintptr_t) 1 << n) - 1)) {
 490                 goto done;
 491             }
 492
 493             map = (1 << (ngx_pagesize_shift - shift)) / (sizeof(uintptr_t) * 8);
 494
 495             for (n = 1; n < map; n++) {
 496                 if (bitmap[n]) {
 497                     goto done;
 498                 }
 499             }
 500
 501             ngx_slab_free_pages(pool, page, 1);
 502
 503             goto done;
 504         }
 505
 506         goto chunk_already_free;
 507
 508     case NGX_SLAB_EXACT:
 509
 510         m = (uintptr_t) 1 <<
 511                 (((uintptr_t) p & (ngx_pagesize - 1)) >> ngx_slab_exact_shift);
 512         size = ngx_slab_exact_size;
 513
 514         if ((uintptr_t) p & (size - 1)) {
 515             goto wrong_chunk;
 516         }
 517
 518         if (slab & m) {
 519             if (slab == NGX_SLAB_BUSY) {
 520                 slots = (ngx_slab_page_t *)
 521                                    ((u_char *) pool + sizeof(ngx_slab_pool_t));
 522                 slot = ngx_slab_exact_shift - pool->min_shift;
 523
 524                 page->next = slots[slot].next;
 525                 slots[slot].next = page;
 526
 527                 page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_EXACT;
 528                 page->next->prev = (uintptr_t) page | NGX_SLAB_EXACT;
 529             }
 530
 531             page->slab &= ~m;
 532
 533             if (page->slab) {
 534                 goto done;
 535             }
 536
 537             ngx_slab_free_pages(pool, page, 1);
 538
 539             goto done;
 540         }
 541
 542         goto chunk_already_free;
 543
 544     case NGX_SLAB_BIG:
 545
 546         shift = slab & NGX_SLAB_SHIFT_MASK;
 547         size = 1 << shift;
 548
 549         if ((uintptr_t) p & (size - 1)) {
 550             goto wrong_chunk;
 551         }
 552
 553         m = (uintptr_t) 1 << ((((uintptr_t) p & (ngx_pagesize - 1)) >> shift)
 554                               + NGX_SLAB_MAP_SHIFT);
 555
 556         if (slab & m) {
 557
 558             if (page->next == NULL) {
 559                 slots = (ngx_slab_page_t *)
 560                                    ((u_char *) pool + sizeof(ngx_slab_pool_t));
 561                 slot = shift - pool->min_shift;
 562
 563                 page->next = slots[slot].next;
 564                 slots[slot].next = page;
 565
 566                 page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_BIG;
 567                 page->next->prev = (uintptr_t) page | NGX_SLAB_BIG;
 568             }
 569
 570             page->slab &= ~m;
 571
 572             if (page->slab & NGX_SLAB_MAP_MASK) {
 573                 goto done;
 574             }
 575
 576             ngx_slab_free_pages(pool, page, 1);
 577
 578             goto done;
 579         }
 580
 581         goto chunk_already_free;
 582
 583     case NGX_SLAB_PAGE:
 584
 585         if ((uintptr_t) p & (ngx_pagesize - 1)) {
 586             goto wrong_chunk;
 587         }
 588
 589         if (slab == NGX_SLAB_PAGE_FREE) {
 590             ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0,
 591                           "ngx_slab_free(): page is already free");
 592             goto fail;
 593         }
 594
 595         if (slab == NGX_SLAB_PAGE_BUSY) {
 596             ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0,
 597                           "ngx_slab_free(): pointer to wrong page");
 598             goto fail;
 599         }
 600
 601         n = ((u_char *) p - pool->start) >> ngx_pagesize_shift;
 602         size = slab & ~NGX_SLAB_PAGE_START;
 603
 604         ngx_slab_free_pages(pool, &pool->pages[n], size);
 605
 606         size <<= ngx_pagesize_shift;
 607
 608         goto done;
 609     }
 610
 611     /* not reached */
 612
 613     return;
 614
 615 done:
 616
 617     ngx_slab_junk(p, size);
 618
 619     return;
 620
 621 wrong_chunk:
 622
 623     ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0,
 624                       "ngx_slab_free(): pointer to wrong chunk");
 625
 626     goto fail;
 627
 628 chunk_already_free:
 629
 630     ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0,
 631                       "ngx_slab_free(): chunk is already free");
 632
 633 fail:
 634
 635     return;
 636 }
 637
 638
 639 static ngx_slab_page_t *
 640 ngx_slab_alloc_pages(ngx_slab_pool_t *pool, ngx_uint_t pages)
 641 {
 642     ngx_slab_page_t  *page, *p;
 643
 644     for (page = pool->free.next; page != &pool->free; page = page->next) {
 645
 646         if (page->slab >= pages) {
 647
 648             if (page->slab > pages) {
 649                 page[pages].slab = page->slab - pages;
 650                 page[pages].next = page->next;
 651                 page[pages].prev = page->prev;
 652
 653                 p = (ngx_slab_page_t *) page->prev;
 654                 p->next = &page[pages];
 655                 page->next->prev = (uintptr_t) &page[pages];
 656
 657             } else {
 658                 p = (ngx_slab_page_t *) page->prev;
 659                 p->next = page->next;
 660                 page->next->prev = page->prev;
 661             }
 662
 663             page->slab = pages | NGX_SLAB_PAGE_START;
 664             page->next = NULL;
 665             page->prev = NGX_SLAB_PAGE;
 666
 667             if (--pages == 0) {
 668                 return page;
 669             }
 670
 671             for (p = page + 1; pages; pages--) {
 672                 p->slab = NGX_SLAB_PAGE_BUSY;
 673                 p->next = NULL;
 674                 p->prev = NGX_SLAB_PAGE;
 675                 p++;
 676             }
 677
 678             return page;
 679         }
 680     }
 681
 682     ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, NGX_ENOMEM,
 683                   "ngx_slab_alloc(): failed");
 684
 685     return NULL;
 686 }
 687
 688
 689 static void
 690 ngx_slab_free_pages(ngx_slab_pool_t *pool, ngx_slab_page_t *page,
 691     ngx_uint_t pages)
 692 {
 693     ngx_slab_page_t  *prev;
 694
 695     page->slab = pages--;
 696
 697     if (pages) {
 698         ngx_memzero(&page[1], pages * sizeof(ngx_slab_page_t));
 699     }
 700
 701     if (page->next) {
 702         prev = (ngx_slab_page_t *) (page->prev & ~NGX_SLAB_PAGE_MASK);
 703         prev->next = page->next;
 704         page->next->prev = page->prev;
 705     }
 706
 707     page->prev = (uintptr_t) &pool->free;
 708     page->next = pool->free.next;
 709
 710     page->next->prev = (uintptr_t) page;
 711
 712     pool->free.next = page;
 713 }