release/src/router/nginx/src/core/ngx_slab.c

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