src/core/ngx_slab.c - nginx - Git at Google


 /*
  * Copyright (C) Igor Sysoev
  */

 #include <ngx_config.h>
 #include <ngx_core.h>

 /*

                          12
     2048   2             11
     1024   4             10
     512    8             9
     256   16             8

     128   32   4   32    7

     64    64   8   63    6      1
     32   128  16  127    5      1
     16   256  32  254    4      2
     8    512  64  504    3      8

  */


 #define NGX_SLAB_PAGE_MASK   3
 #define NGX_SLAB_PAGE        0
 #define NGX_SLAB_BIG         1
 #define NGX_SLAB_EXACT       2
 #define NGX_SLAB_SMALL       3

 #if (NGX_PTR_SIZE == 4)

 #define NGX_SLAB_PAGE_FREE   0
 #define NGX_SLAB_PAGE_BUSY   0xffffffff
 #define NGX_SLAB_PAGE_START  0x80000000

 #define NGX_SLAB_SHIFT_MASK  0x0000000f
 #define NGX_SLAB_MAP_MASK    0xffff0000
 #define NGX_SLAB_MAP_SHIFT   16

 #define NGX_SLAB_BUSY        0xffffffff

 #else /* (NGX_PTR_SIZE == 8) */

 #define NGX_SLAB_PAGE_FREE   0
 #define NGX_SLAB_PAGE_BUSY   0xffffffffffffffff
 #define NGX_SLAB_PAGE_START  0x8000000000000000

 #define NGX_SLAB_SHIFT_MASK  0x000000000000000f
 #define NGX_SLAB_MAP_MASK    0xffffffff00000000
 #define NGX_SLAB_MAP_SHIFT   32

 #define NGX_SLAB_BUSY        0xffffffffffffffff

 #endif


 #if (NGX_DEBUG_MALLOC)

 #define ngx_slab_junk(p, size)     ngx_memset(p, 0xD0, size)

 #else

 #if (NGX_FREEBSD)

 #define ngx_slab_junk(p, size)                                                \
     if (ngx_freebsd_debug_malloc)  ngx_memset(p, 0xD0, size)

 #else

 #define ngx_slab_junk(p, size)

 #endif

 #endif

 static ngx_slab_page_t *ngx_slab_alloc_pages(ngx_slab_pool_t *pool,
     ngx_uint_t pages);
 static void ngx_slab_free_pages(ngx_slab_pool_t *pool, ngx_slab_page_t *page,
     ngx_uint_t pages);


 static ngx_uint_t  ngx_slab_max_size;
 static ngx_uint_t  ngx_slab_exact_size;
 static ngx_uint_t  ngx_slab_exact_shift;


 void
 ngx_slab_init(ngx_slab_pool_t *pool)
 {
     u_char           *p;
     size_t            size;
     ngx_int_t         m;
     ngx_uint_t        i, n, pages;
     ngx_slab_page_t  *slots;

     /* STUB */
     if (ngx_slab_max_size == 0) {
         ngx_slab_max_size = ngx_pagesize / 2;
         ngx_slab_exact_size = ngx_pagesize / (8 * sizeof(uintptr_t));
         for (n = ngx_slab_exact_size; n >>= 1; ngx_slab_exact_shift++) {
             /* void */
         }
     }
     /**/

     pool->min_size = 1 << pool->min_shift;

     p = (u_char *) pool + sizeof(ngx_slab_pool_t);
     size = pool->end - p;

     ngx_slab_junk(p, size);

     slots = (ngx_slab_page_t *) p;
     n = ngx_pagesize_shift - pool->min_shift;

     for (i = 0; i < n; i++) {
         slots[i].slab = 0;
         slots[i].next = &slots[i];
         slots[i].prev = 0;
     }

     p += n * sizeof(ngx_slab_page_t);

     pages = (ngx_uint_t) (size / (ngx_pagesize + sizeof(ngx_slab_page_t)));

     ngx_memzero(p, pages * sizeof(ngx_slab_page_t));

     pool->pages = (ngx_slab_page_t *) p;

     pool->free.prev = 0;
     pool->free.next = (ngx_slab_page_t *) p;

     pool->pages->slab = pages;
     pool->pages->next = &pool->free;
     pool->pages->prev = (uintptr_t) &pool->free;

     pool->start = (u_char *)
                   ngx_align_ptr((uintptr_t) p + pages * sizeof(ngx_slab_page_t),
                                  ngx_pagesize);

     m = pages - (pool->end - pool->start) / ngx_pagesize;
     if (m > 0) {
         pages -= m;
         pool->pages->slab = pages;
     }

 #if 0
     ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "slab: %p, %p, %ui, %d",
                   pool, pool->start, pages,
                   (pool->end - pool->start) / ngx_pagesize - pages);
 #endif
 }


 void *
 ngx_slab_alloc(ngx_slab_pool_t *pool, size_t size)
 {
     void  *p;

     ngx_shmtx_lock(&pool->mutex);

     p = ngx_slab_alloc_locked(pool, size);

     ngx_shmtx_unlock(&pool->mutex);

     return p;
 }


 void *
 ngx_slab_alloc_locked(ngx_slab_pool_t *pool, size_t size)
 {
     size_t            s;
     uintptr_t         p, n, m, mask, *bitmap;
     ngx_uint_t        i, slot, shift, map;
     ngx_slab_page_t  *page, *prev, *slots;

     if (size >= ngx_slab_max_size) {

         ngx_log_debug1(NGX_LOG_DEBUG_ALLOC, ngx_cycle->log, 0,
                        "slab alloc: %uz", size);

         page = ngx_slab_alloc_pages(pool, (size + ngx_pagesize - 1)
                                           >> ngx_pagesize_shift);
         if (page) {
             p = (page - pool->pages) << ngx_pagesize_shift;
             p += (uintptr_t) pool->start;

         } else {
             p = 0;
         }

         goto done;
     }

     if (size > pool->min_size) {
         shift = 1;
         for (s = size - 1; s >>= 1; shift++) { /* void */ }
         slot = shift - pool->min_shift;

     } else {
         size = pool->min_size;
         shift = pool->min_shift;
         slot = 0;
     }

     ngx_log_debug2(NGX_LOG_DEBUG_ALLOC, ngx_cycle->log, 0,
                    "slab alloc: %uz slot: %ui", size, slot);

     slots = (ngx_slab_page_t *) ((u_char *) pool + sizeof(ngx_slab_pool_t));
     page = slots[slot].next;

     if (page->next != page) {

         if (shift < ngx_slab_exact_shift) {

             do {
                 p = (page - pool->pages) << ngx_pagesize_shift;
                 bitmap = (uintptr_t *) (pool->start + p);

                 map = (1 << (ngx_pagesize_shift - shift))
                           / (sizeof(uintptr_t) * 8);

                 for (n = 0; n < map; n++) {

                     if (bitmap[n] != NGX_SLAB_BUSY) {

                         for (m = 1, i = 0; m; m <<= 1, i++) {
                             if ((bitmap[n] & m)) {
                                 continue;
                             }

                             bitmap[n] |= m;

                             i = ((n * sizeof(uintptr_t) * 8) << shift)
                                 + (i << shift);

                             if (bitmap[n] == NGX_SLAB_BUSY) {
                                 for (n = n + 1; n < map; n++) {
                                      if (bitmap[n] != NGX_SLAB_BUSY) {
                                          p = (uintptr_t) bitmap + i;

                                          goto done;
                                      }
                                 }

                                 prev = (ngx_slab_page_t *)
                                             (page->prev & ~NGX_SLAB_PAGE_MASK);
                                 prev->next = page->next;
                                 page->next->prev = page->prev;

                                 page->next = NULL;
                                 page->prev = NGX_SLAB_SMALL;
                             }

                             p = (uintptr_t) bitmap + i;

                             goto done;
                         }
                     }
                 }

                 page = page->next;

             } while (page);

         } else if (shift == ngx_slab_exact_shift) {

             do {
                 if (page->slab != NGX_SLAB_BUSY) {

                     for (m = 1, i = 0; m; m <<= 1, i++) {
                         if ((page->slab & m)) {
                             continue;
                         }

                         page->slab |= m;

                         if (page->slab == NGX_SLAB_BUSY) {
                             prev = (ngx_slab_page_t *)
                                             (page->prev & ~NGX_SLAB_PAGE_MASK);
                             prev->next = page->next;
                             page->next->prev = page->prev;

                             page->next = NULL;
                             page->prev = NGX_SLAB_EXACT;
                         }

                         p = (page - pool->pages) << ngx_pagesize_shift;
                         p += i << shift;
                         p += (uintptr_t) pool->start;

                         goto done;
                     }
                 }

                 page = page->next;

             } while (page);

         } else { /* shift > ngx_slab_exact_shift */

             n = ngx_pagesize_shift - (page->slab & NGX_SLAB_SHIFT_MASK);
             n = 1 << n;
             n = ((uintptr_t) 1 << n) - 1;
             mask = n << NGX_SLAB_MAP_SHIFT;

             do {
                 if ((page->slab & NGX_SLAB_MAP_MASK) != mask) {

                     for (m = (uintptr_t) 1 << NGX_SLAB_MAP_SHIFT, i = 0;
                          m & mask;
                          m <<= 1, i++)
                     {
                         if ((page->slab & m)) {
                             continue;
                         }

                         page->slab |= m;

                         if ((page->slab & NGX_SLAB_MAP_MASK) == mask) {
                             prev = (ngx_slab_page_t *)
                                             (page->prev & ~NGX_SLAB_PAGE_MASK);
                             prev->next = page->next;
                             page->next->prev = page->prev;

                             page->next = NULL;
                             page->prev = NGX_SLAB_BIG;
                         }

                         p = (page - pool->pages) << ngx_pagesize_shift;
                         p += i << shift;
                         p += (uintptr_t) pool->start;

                         goto done;
                     }
                 }

                 page = page->next;

             } while (page);
         }
     }

     page = ngx_slab_alloc_pages(pool, 1);

     if (page) {
         if (shift < ngx_slab_exact_shift) {
             p = (page - pool->pages) << ngx_pagesize_shift;
             bitmap = (uintptr_t *) (pool->start + p);

             s = 1 << shift;
             n = (1 << (ngx_pagesize_shift - shift)) / 8 / s;

             if (n == 0) {
                 n = 1;
             }

             bitmap[0] = (2 << n) - 1;

             map = (1 << (ngx_pagesize_shift - shift)) / (sizeof(uintptr_t) * 8);

             for (i = 1; i < map; i++) {
                 bitmap[i] = 0;
             }

             page->slab = shift;
             page->next = &slots[slot];
             page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_SMALL;

             slots[slot].next = page;

             p = ((page - pool->pages) << ngx_pagesize_shift) + s * n;
             p += (uintptr_t) pool->start;

             goto done;

         } else if (shift == ngx_slab_exact_shift) {

             page->slab = 1;
             page->next = &slots[slot];
             page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_EXACT;

             slots[slot].next = page;

             p = (page - pool->pages) << ngx_pagesize_shift;
             p += (uintptr_t) pool->start;

             goto done;

         } else { /* shift > ngx_slab_exact_shift */

             page->slab = ((uintptr_t) 1 << NGX_SLAB_MAP_SHIFT) | shift;
             page->next = &slots[slot];
             page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_BIG;

             slots[slot].next = page;

             p = (page - pool->pages) << ngx_pagesize_shift;
             p += (uintptr_t) pool->start;

             goto done;
         }
     }

     p = 0;

 done:

     ngx_log_debug1(NGX_LOG_DEBUG_ALLOC, ngx_cycle->log, 0, "slab alloc: %p", p);

     return (void *) p;
 }


 void
 ngx_slab_free(ngx_slab_pool_t *pool, void *p)
 {
     ngx_shmtx_lock(&pool->mutex);

     ngx_slab_free_locked(pool, p);

     ngx_shmtx_unlock(&pool->mutex);
 }


 void
 ngx_slab_free_locked(ngx_slab_pool_t *pool, void *p)
 {
     size_t            size;
     uintptr_t         slab, m, *bitmap;
     ngx_uint_t        n, type, slot, shift, map;
     ngx_slab_page_t  *slots, *page;

     ngx_log_debug1(NGX_LOG_DEBUG_ALLOC, ngx_cycle->log, 0, "slab free: %p", p);

     if ((u_char *) p < pool->start || (u_char *) p > pool->end) {
         ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0,
                       "ngx_slab_free(): outside of pool");
         goto fail;
     }

     n = ((u_char *) p - pool->start) >> ngx_pagesize_shift;
     page = &pool->pages[n];
     slab = page->slab;
     type = page->prev & NGX_SLAB_PAGE_MASK;

     switch (type) {

     case NGX_SLAB_SMALL:

         shift = slab & NGX_SLAB_SHIFT_MASK;
         size = 1 << shift;

         if ((uintptr_t) p & (size - 1)) {
             goto wrong_chunk;
         }

         n = ((uintptr_t) p & (ngx_pagesize - 1)) >> shift;
         m = (uintptr_t) 1 << (n & (sizeof(uintptr_t) * 8 - 1));
         n /= (sizeof(uintptr_t) * 8);
         bitmap = (uintptr_t *) ((uintptr_t) p & ~(ngx_pagesize - 1));

         if (bitmap[n] & m) {

             if (page->next == NULL) {
                 slots = (ngx_slab_page_t *)
                                    ((u_char *) pool + sizeof(ngx_slab_pool_t));
                 slot = shift - pool->min_shift;

                 page->next = slots[slot].next;
                 slots[slot].next = page;

                 page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_SMALL;
                 page->next->prev = (uintptr_t) page | NGX_SLAB_SMALL;
             }

             bitmap[n] &= ~m;

             n = (1 << (ngx_pagesize_shift - shift)) / 8 / (1 << shift);

             if (n == 0) {
                 n = 1;
             }

             if (bitmap[0] & ~(((uintptr_t) 1 << n) - 1)) {
                 goto done;
             }

             map = (1 << (ngx_pagesize_shift - shift)) / (sizeof(uintptr_t) * 8);

             for (n = 1; n < map; n++) {
                 if (bitmap[n]) {
                     goto done;
                 }
             }

             ngx_slab_free_pages(pool, page, 1);

             goto done;
         }

         goto chunk_already_free;

     case NGX_SLAB_EXACT:

         m = (uintptr_t) 1 <<
                 (((uintptr_t) p & (ngx_pagesize - 1)) >> ngx_slab_exact_shift);
         size = ngx_slab_exact_size;

         if ((uintptr_t) p & (size - 1)) {
             goto wrong_chunk;
         }

         if (slab & m) {
             if (slab == NGX_SLAB_BUSY) {
                 slots = (ngx_slab_page_t *)
                                    ((u_char *) pool + sizeof(ngx_slab_pool_t));
                 slot = ngx_slab_exact_shift - pool->min_shift;

                 page->next = slots[slot].next;
                 slots[slot].next = page;

                 page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_EXACT;
                 page->next->prev = (uintptr_t) page | NGX_SLAB_EXACT;
             }

             page->slab &= ~m;

             if (page->slab) {
                 goto done;
             }

             ngx_slab_free_pages(pool, page, 1);

             goto done;
         }

         goto chunk_already_free;

     case NGX_SLAB_BIG:

         shift = slab & NGX_SLAB_SHIFT_MASK;
         size = 1 << shift;

         if ((uintptr_t) p & (size - 1)) {
             goto wrong_chunk;
         }

         m = (uintptr_t) 1 << ((((uintptr_t) p & (ngx_pagesize - 1)) >> shift)
                               + NGX_SLAB_MAP_SHIFT);

         if (slab & m) {

             if (page->next == NULL) {
                 slots = (ngx_slab_page_t *)
                                    ((u_char *) pool + sizeof(ngx_slab_pool_t));
                 slot = shift - pool->min_shift;

                 page->next = slots[slot].next;
                 slots[slot].next = page;

                 page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_BIG;
                 page->next->prev = (uintptr_t) page | NGX_SLAB_BIG;
             }

             page->slab &= ~m;

             if (page->slab & NGX_SLAB_MAP_MASK) {
                 goto done;
             }

             ngx_slab_free_pages(pool, page, 1);

             goto done;
         }

         goto chunk_already_free;

     case NGX_SLAB_PAGE:

         if ((uintptr_t) p & (ngx_pagesize - 1)) {
             goto wrong_chunk;
         }

         if (slab == NGX_SLAB_PAGE_FREE) {
             ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0,
                           "ngx_slab_free(): page is already free");
             goto fail;
         }

         if (slab == NGX_SLAB_PAGE_BUSY) {
             ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0,
                           "ngx_slab_free(): pointer to wrong page");
             goto fail;
         }

         n = ((u_char *) p - pool->start) >> ngx_pagesize_shift;
         size = slab & ~NGX_SLAB_PAGE_START;

         ngx_slab_free_pages(pool, &pool->pages[n], size);

         size <<= ngx_pagesize_shift;

         goto done;
     }

     /* not reached */

     return;

 done:

     ngx_slab_junk(p, size);

     return;

 wrong_chunk:

     ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0,
                       "ngx_slab_free(): pointer to wrong chunk");

     goto fail;

 chunk_already_free:

     ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0,
                       "ngx_slab_free(): chunk is already free");

 fail:

     return;
 }


 static ngx_slab_page_t *
 ngx_slab_alloc_pages(ngx_slab_pool_t *pool, ngx_uint_t pages)
 {
     ngx_slab_page_t  *page, *p;

     for (page = pool->free.next; page != &pool->free; page = page->next) {

         if (page->slab >= pages) {

             if (page->slab > pages) {
                 page[pages].slab = page->slab - pages;
                 page[pages].next = page->next;
                 page[pages].prev = page->prev;

                 p = (ngx_slab_page_t *) page->prev;
                 p->next = &page[pages];
                 page->next->prev = (uintptr_t) &page[pages];

             } else {
                 p = (ngx_slab_page_t *) page->prev;
                 p->next = page->next;
                 page->next->prev = page->prev;
             }

             page->slab = pages | NGX_SLAB_PAGE_START;

 #if (NGX_DEBUG)
             page->next = NULL;
             page->prev = NGX_SLAB_PAGE;
 #endif

             if (--pages == 0) {
                 return page;
             }

             for (p = page + 1; pages; pages--) {
                 p->slab = NGX_SLAB_PAGE_BUSY;
 #if (NGX_DEBUG)
                 p->next = NULL;
                 p->prev = NGX_SLAB_PAGE;
 #endif
                 p++;
             }

             return page;
         }
     }

     ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, NGX_ENOMEM,
                       "ngx_slab_alloc(): failed");

     return NULL;
 }


 static void
 ngx_slab_free_pages(ngx_slab_pool_t *pool, ngx_slab_page_t *page,
     ngx_uint_t pages)
 {
     ngx_slab_page_t  *prev;

     page->slab = pages--;

     if (pages) {
         ngx_memzero(&page[1], pages * sizeof(ngx_slab_page_t));
     }

     if (page->next) {
         prev = (ngx_slab_page_t *) (page->prev & ~NGX_SLAB_PAGE_MASK);
         prev->next = page->next;
         page->next->prev = page->prev;
     }

     page->prev = (uintptr_t) &pool->free;
     page->next = pool->free.next;

     page->next->prev = (uintptr_t) page;

     pool->free.next = page;
 }

	/*
	* Copyright (C) Igor Sysoev
	*/

	#include <ngx_config.h>
	#include <ngx_core.h>

	/*

	12
	2048 2 11
	1024 4 10
	512 8 9
	256 16 8

	128 32 4 32 7

	64 64 8 63 6 1
	32 128 16 127 5 1
	16 256 32 254 4 2
	8 512 64 504 3 8

	*/


	#define NGX_SLAB_PAGE_MASK 3
	#define NGX_SLAB_PAGE 0
	#define NGX_SLAB_BIG 1
	#define NGX_SLAB_EXACT 2
	#define NGX_SLAB_SMALL 3

	#if (NGX_PTR_SIZE == 4)

	#define NGX_SLAB_PAGE_FREE 0
	#define NGX_SLAB_PAGE_BUSY 0xffffffff
	#define NGX_SLAB_PAGE_START 0x80000000

	#define NGX_SLAB_SHIFT_MASK 0x0000000f
	#define NGX_SLAB_MAP_MASK 0xffff0000
	#define NGX_SLAB_MAP_SHIFT 16

	#define NGX_SLAB_BUSY 0xffffffff

	#else /* (NGX_PTR_SIZE == 8) */

	#define NGX_SLAB_PAGE_FREE 0
	#define NGX_SLAB_PAGE_BUSY 0xffffffffffffffff
	#define NGX_SLAB_PAGE_START 0x8000000000000000

	#define NGX_SLAB_SHIFT_MASK 0x000000000000000f
	#define NGX_SLAB_MAP_MASK 0xffffffff00000000
	#define NGX_SLAB_MAP_SHIFT 32

	#define NGX_SLAB_BUSY 0xffffffffffffffff

	#endif


	#if (NGX_DEBUG_MALLOC)

	#define ngx_slab_junk(p, size) ngx_memset(p, 0xD0, size)

	#else

	#if (NGX_FREEBSD)

	#define ngx_slab_junk(p, size) \
	if (ngx_freebsd_debug_malloc) ngx_memset(p, 0xD0, size)

	#else

	#define ngx_slab_junk(p, size)

	#endif

	#endif

	static ngx_slab_page_t ngx_slab_alloc_pages(ngx_slab_pool_t pool,
	ngx_uint_t pages);
	static void ngx_slab_free_pages(ngx_slab_pool_t pool, ngx_slab_page_t page,
	ngx_uint_t pages);


	static ngx_uint_t ngx_slab_max_size;
	static ngx_uint_t ngx_slab_exact_size;
	static ngx_uint_t ngx_slab_exact_shift;


	void
	ngx_slab_init(ngx_slab_pool_t *pool)
	{
	u_char *p;
	size_t size;
	ngx_int_t m;
	ngx_uint_t i, n, pages;
	ngx_slab_page_t *slots;

	/* STUB */
	if (ngx_slab_max_size == 0) {
	ngx_slab_max_size = ngx_pagesize / 2;
	ngx_slab_exact_size = ngx_pagesize / (8 * sizeof(uintptr_t));
	for (n = ngx_slab_exact_size; n >>= 1; ngx_slab_exact_shift++) {
	/* void */
	}
	}
	/**/

	pool->min_size = 1 << pool->min_shift;

	p = (u_char *) pool + sizeof(ngx_slab_pool_t);
	size = pool->end - p;

	ngx_slab_junk(p, size);

	slots = (ngx_slab_page_t *) p;
	n = ngx_pagesize_shift - pool->min_shift;

	for (i = 0; i < n; i++) {
	slots[i].slab = 0;
	slots[i].next = &slots[i];
	slots[i].prev = 0;
	}

	p += n * sizeof(ngx_slab_page_t);

	pages = (ngx_uint_t) (size / (ngx_pagesize + sizeof(ngx_slab_page_t)));

	ngx_memzero(p, pages * sizeof(ngx_slab_page_t));

	pool->pages = (ngx_slab_page_t *) p;

	pool->free.prev = 0;
	pool->free.next = (ngx_slab_page_t *) p;

	pool->pages->slab = pages;
	pool->pages->next = &pool->free;
	pool->pages->prev = (uintptr_t) &pool->free;

	pool->start = (u_char *)
	ngx_align_ptr((uintptr_t) p + pages * sizeof(ngx_slab_page_t),
	ngx_pagesize);

	m = pages - (pool->end - pool->start) / ngx_pagesize;
	if (m > 0) {
	pages -= m;
	pool->pages->slab = pages;
	}

	#if 0
	ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "slab: %p, %p, %ui, %d",
	pool, pool->start, pages,
	(pool->end - pool->start) / ngx_pagesize - pages);
	#endif
	}


	void *
	ngx_slab_alloc(ngx_slab_pool_t *pool, size_t size)
	{
	void *p;

	ngx_shmtx_lock(&pool->mutex);

	p = ngx_slab_alloc_locked(pool, size);

	ngx_shmtx_unlock(&pool->mutex);

	return p;
	}


	void *
	ngx_slab_alloc_locked(ngx_slab_pool_t *pool, size_t size)
	{
	size_t s;
	uintptr_t p, n, m, mask, *bitmap;
	ngx_uint_t i, slot, shift, map;
	ngx_slab_page_t page, prev, *slots;

	if (size >= ngx_slab_max_size) {

	ngx_log_debug1(NGX_LOG_DEBUG_ALLOC, ngx_cycle->log, 0,
	"slab alloc: %uz", size);

	page = ngx_slab_alloc_pages(pool, (size + ngx_pagesize - 1)
	>> ngx_pagesize_shift);
	if (page) {
	p = (page - pool->pages) << ngx_pagesize_shift;
	p += (uintptr_t) pool->start;

	} else {
	p = 0;
	}

	goto done;
	}

	if (size > pool->min_size) {
	shift = 1;
	for (s = size - 1; s >>= 1; shift++) { /* void */ }
	slot = shift - pool->min_shift;

	} else {
	size = pool->min_size;
	shift = pool->min_shift;
	slot = 0;
	}

	ngx_log_debug2(NGX_LOG_DEBUG_ALLOC, ngx_cycle->log, 0,
	"slab alloc: %uz slot: %ui", size, slot);

	slots = (ngx_slab_page_t ) ((u_char ) pool + sizeof(ngx_slab_pool_t));
	page = slots[slot].next;

	if (page->next != page) {

	if (shift < ngx_slab_exact_shift) {

	do {
	p = (page - pool->pages) << ngx_pagesize_shift;
	bitmap = (uintptr_t *) (pool->start + p);

	map = (1 << (ngx_pagesize_shift - shift))
	/ (sizeof(uintptr_t) * 8);

	for (n = 0; n < map; n++) {

	if (bitmap[n] != NGX_SLAB_BUSY) {

	for (m = 1, i = 0; m; m <<= 1, i++) {
	if ((bitmap[n] & m)) {
	continue;
	}

	bitmap[n] \|= m;

	i = ((n * sizeof(uintptr_t) * 8) << shift)
	+ (i << shift);

	if (bitmap[n] == NGX_SLAB_BUSY) {
	for (n = n + 1; n < map; n++) {
	if (bitmap[n] != NGX_SLAB_BUSY) {
	p = (uintptr_t) bitmap + i;

	goto done;
	}
	}

	prev = (ngx_slab_page_t *)
	(page->prev & ~NGX_SLAB_PAGE_MASK);
	prev->next = page->next;
	page->next->prev = page->prev;

	page->next = NULL;
	page->prev = NGX_SLAB_SMALL;
	}

	p = (uintptr_t) bitmap + i;

	goto done;
	}
	}
	}

	page = page->next;

	} while (page);

	} else if (shift == ngx_slab_exact_shift) {

	do {
	if (page->slab != NGX_SLAB_BUSY) {

	for (m = 1, i = 0; m; m <<= 1, i++) {
	if ((page->slab & m)) {
	continue;
	}

	page->slab \|= m;

	if (page->slab == NGX_SLAB_BUSY) {
	prev = (ngx_slab_page_t *)
	(page->prev & ~NGX_SLAB_PAGE_MASK);
	prev->next = page->next;
	page->next->prev = page->prev;

	page->next = NULL;
	page->prev = NGX_SLAB_EXACT;
	}

	p = (page - pool->pages) << ngx_pagesize_shift;
	p += i << shift;
	p += (uintptr_t) pool->start;

	goto done;
	}
	}

	page = page->next;

	} while (page);

	} else { /* shift > ngx_slab_exact_shift */

	n = ngx_pagesize_shift - (page->slab & NGX_SLAB_SHIFT_MASK);
	n = 1 << n;
	n = ((uintptr_t) 1 << n) - 1;
	mask = n << NGX_SLAB_MAP_SHIFT;

	do {
	if ((page->slab & NGX_SLAB_MAP_MASK) != mask) {

	for (m = (uintptr_t) 1 << NGX_SLAB_MAP_SHIFT, i = 0;
	m & mask;
	m <<= 1, i++)
	{
	if ((page->slab & m)) {
	continue;
	}

	page->slab \|= m;

	if ((page->slab & NGX_SLAB_MAP_MASK) == mask) {
	prev = (ngx_slab_page_t *)
	(page->prev & ~NGX_SLAB_PAGE_MASK);
	prev->next = page->next;
	page->next->prev = page->prev;

	page->next = NULL;
	page->prev = NGX_SLAB_BIG;
	}

	p = (page - pool->pages) << ngx_pagesize_shift;
	p += i << shift;
	p += (uintptr_t) pool->start;

	goto done;
	}
	}

	page = page->next;

	} while (page);
	}
	}

	page = ngx_slab_alloc_pages(pool, 1);

	if (page) {
	if (shift < ngx_slab_exact_shift) {
	p = (page - pool->pages) << ngx_pagesize_shift;
	bitmap = (uintptr_t *) (pool->start + p);

	s = 1 << shift;
	n = (1 << (ngx_pagesize_shift - shift)) / 8 / s;

	if (n == 0) {
	n = 1;
	}

	bitmap[0] = (2 << n) - 1;

	map = (1 << (ngx_pagesize_shift - shift)) / (sizeof(uintptr_t) * 8);

	for (i = 1; i < map; i++) {
	bitmap[i] = 0;
	}

	page->slab = shift;
	page->next = &slots[slot];
	page->prev = (uintptr_t) &slots[slot] \| NGX_SLAB_SMALL;

	slots[slot].next = page;

	p = ((page - pool->pages) << ngx_pagesize_shift) + s * n;
	p += (uintptr_t) pool->start;

	goto done;

	} else if (shift == ngx_slab_exact_shift) {

	page->slab = 1;
	page->next = &slots[slot];
	page->prev = (uintptr_t) &slots[slot] \| NGX_SLAB_EXACT;

	slots[slot].next = page;

	p = (page - pool->pages) << ngx_pagesize_shift;
	p += (uintptr_t) pool->start;

	goto done;

	} else { /* shift > ngx_slab_exact_shift */

	page->slab = ((uintptr_t) 1 << NGX_SLAB_MAP_SHIFT) \| shift;
	page->next = &slots[slot];
	page->prev = (uintptr_t) &slots[slot] \| NGX_SLAB_BIG;

	slots[slot].next = page;

	p = (page - pool->pages) << ngx_pagesize_shift;
	p += (uintptr_t) pool->start;

	goto done;
	}
	}

	p = 0;

	done:

	ngx_log_debug1(NGX_LOG_DEBUG_ALLOC, ngx_cycle->log, 0, "slab alloc: %p", p);

	return (void *) p;
	}


	void
	ngx_slab_free(ngx_slab_pool_t pool, void p)
	{
	ngx_shmtx_lock(&pool->mutex);

	ngx_slab_free_locked(pool, p);

	ngx_shmtx_unlock(&pool->mutex);
	}


	void
	ngx_slab_free_locked(ngx_slab_pool_t pool, void p)
	{
	size_t size;
	uintptr_t slab, m, *bitmap;
	ngx_uint_t n, type, slot, shift, map;
	ngx_slab_page_t slots, page;

	ngx_log_debug1(NGX_LOG_DEBUG_ALLOC, ngx_cycle->log, 0, "slab free: %p", p);

	if ((u_char ) p < pool->start \|\| (u_char ) p > pool->end) {
	ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0,
	"ngx_slab_free(): outside of pool");
	goto fail;
	}

	n = ((u_char *) p - pool->start) >> ngx_pagesize_shift;
	page = &pool->pages[n];
	slab = page->slab;
	type = page->prev & NGX_SLAB_PAGE_MASK;

	switch (type) {

	case NGX_SLAB_SMALL:

	shift = slab & NGX_SLAB_SHIFT_MASK;
	size = 1 << shift;

	if ((uintptr_t) p & (size - 1)) {
	goto wrong_chunk;
	}

	n = ((uintptr_t) p & (ngx_pagesize - 1)) >> shift;
	m = (uintptr_t) 1 << (n & (sizeof(uintptr_t) * 8 - 1));
	n /= (sizeof(uintptr_t) * 8);
	bitmap = (uintptr_t *) ((uintptr_t) p & ~(ngx_pagesize - 1));

	if (bitmap[n] & m) {

	if (page->next == NULL) {
	slots = (ngx_slab_page_t *)
	((u_char *) pool + sizeof(ngx_slab_pool_t));
	slot = shift - pool->min_shift;

	page->next = slots[slot].next;
	slots[slot].next = page;

	page->prev = (uintptr_t) &slots[slot] \| NGX_SLAB_SMALL;
	page->next->prev = (uintptr_t) page \| NGX_SLAB_SMALL;
	}

	bitmap[n] &= ~m;

	n = (1 << (ngx_pagesize_shift - shift)) / 8 / (1 << shift);

	if (n == 0) {
	n = 1;
	}

	if (bitmap[0] & ~(((uintptr_t) 1 << n) - 1)) {
	goto done;
	}

	map = (1 << (ngx_pagesize_shift - shift)) / (sizeof(uintptr_t) * 8);

	for (n = 1; n < map; n++) {
	if (bitmap[n]) {
	goto done;
	}
	}

	ngx_slab_free_pages(pool, page, 1);

	goto done;
	}

	goto chunk_already_free;

	case NGX_SLAB_EXACT:

	m = (uintptr_t) 1 <<
	(((uintptr_t) p & (ngx_pagesize - 1)) >> ngx_slab_exact_shift);
	size = ngx_slab_exact_size;

	if ((uintptr_t) p & (size - 1)) {
	goto wrong_chunk;
	}

	if (slab & m) {
	if (slab == NGX_SLAB_BUSY) {
	slots = (ngx_slab_page_t *)
	((u_char *) pool + sizeof(ngx_slab_pool_t));
	slot = ngx_slab_exact_shift - pool->min_shift;

	page->next = slots[slot].next;
	slots[slot].next = page;

	page->prev = (uintptr_t) &slots[slot] \| NGX_SLAB_EXACT;
	page->next->prev = (uintptr_t) page \| NGX_SLAB_EXACT;
	}

	page->slab &= ~m;

	if (page->slab) {
	goto done;
	}

	ngx_slab_free_pages(pool, page, 1);

	goto done;
	}

	goto chunk_already_free;

	case NGX_SLAB_BIG:

	shift = slab & NGX_SLAB_SHIFT_MASK;
	size = 1 << shift;

	if ((uintptr_t) p & (size - 1)) {
	goto wrong_chunk;
	}

	m = (uintptr_t) 1 << ((((uintptr_t) p & (ngx_pagesize - 1)) >> shift)
	+ NGX_SLAB_MAP_SHIFT);

	if (slab & m) {

	if (page->next == NULL) {
	slots = (ngx_slab_page_t *)
	((u_char *) pool + sizeof(ngx_slab_pool_t));
	slot = shift - pool->min_shift;

	page->next = slots[slot].next;
	slots[slot].next = page;

	page->prev = (uintptr_t) &slots[slot] \| NGX_SLAB_BIG;
	page->next->prev = (uintptr_t) page \| NGX_SLAB_BIG;
	}

	page->slab &= ~m;

	if (page->slab & NGX_SLAB_MAP_MASK) {
	goto done;
	}

	ngx_slab_free_pages(pool, page, 1);

	goto done;
	}

	goto chunk_already_free;

	case NGX_SLAB_PAGE:

	if ((uintptr_t) p & (ngx_pagesize - 1)) {
	goto wrong_chunk;
	}

	if (slab == NGX_SLAB_PAGE_FREE) {
	ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0,
	"ngx_slab_free(): page is already free");
	goto fail;
	}

	if (slab == NGX_SLAB_PAGE_BUSY) {
	ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0,
	"ngx_slab_free(): pointer to wrong page");
	goto fail;
	}

	n = ((u_char *) p - pool->start) >> ngx_pagesize_shift;
	size = slab & ~NGX_SLAB_PAGE_START;

	ngx_slab_free_pages(pool, &pool->pages[n], size);

	size <<= ngx_pagesize_shift;

	goto done;
	}

	/* not reached */

	return;

	done:

	ngx_slab_junk(p, size);

	return;

	wrong_chunk:

	ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0,
	"ngx_slab_free(): pointer to wrong chunk");

	goto fail;

	chunk_already_free:

	ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0,
	"ngx_slab_free(): chunk is already free");

	fail:

	return;
	}


	static ngx_slab_page_t *
	ngx_slab_alloc_pages(ngx_slab_pool_t *pool, ngx_uint_t pages)
	{
	ngx_slab_page_t page, p;

	for (page = pool->free.next; page != &pool->free; page = page->next) {

	if (page->slab >= pages) {

	if (page->slab > pages) {
	page[pages].slab = page->slab - pages;
	page[pages].next = page->next;
	page[pages].prev = page->prev;

	p = (ngx_slab_page_t *) page->prev;
	p->next = &page[pages];
	page->next->prev = (uintptr_t) &page[pages];

	} else {
	p = (ngx_slab_page_t *) page->prev;
	p->next = page->next;
	page->next->prev = page->prev;
	}

	page->slab = pages \| NGX_SLAB_PAGE_START;

	#if (NGX_DEBUG)
	page->next = NULL;
	page->prev = NGX_SLAB_PAGE;
	#endif

	if (--pages == 0) {
	return page;
	}

	for (p = page + 1; pages; pages--) {
	p->slab = NGX_SLAB_PAGE_BUSY;
	#if (NGX_DEBUG)
	p->next = NULL;
	p->prev = NGX_SLAB_PAGE;
	#endif
	p++;
	}

	return page;
	}
	}

	ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, NGX_ENOMEM,
	"ngx_slab_alloc(): failed");

	return NULL;
	}


	static void
	ngx_slab_free_pages(ngx_slab_pool_t pool, ngx_slab_page_t page,
	ngx_uint_t pages)
	{
	ngx_slab_page_t *prev;

	page->slab = pages--;

	if (pages) {
	ngx_memzero(&page[1], pages * sizeof(ngx_slab_page_t));
	}

	if (page->next) {
	prev = (ngx_slab_page_t *) (page->prev & ~NGX_SLAB_PAGE_MASK);
	prev->next = page->next;
	page->next->prev = page->prev;
	}

	page->prev = (uintptr_t) &pool->free;
	page->next = pool->free.next;

	page->next->prev = (uintptr_t) page;

	pool->free.next = page;
	}