diff options
Diffstat (limited to 'app/nginx/src/core/ngx_slab.c')
-rw-r--r-- | app/nginx/src/core/ngx_slab.c | 806 |
1 files changed, 806 insertions, 0 deletions
diff --git a/app/nginx/src/core/ngx_slab.c b/app/nginx/src/core/ngx_slab.c new file mode 100644 index 0000000..1d4ce2b --- /dev/null +++ b/app/nginx/src/core/ngx_slab.c @@ -0,0 +1,806 @@ + +/* + * Copyright (C) Igor Sysoev + * Copyright (C) Nginx, Inc. + */ + +#include <ngx_config.h> +#include <ngx_core.h> + + +#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 + + +#define ngx_slab_slots(pool) \ + (ngx_slab_page_t *) ((u_char *) (pool) + sizeof(ngx_slab_pool_t)) + +#define ngx_slab_page_type(page) ((page)->prev & NGX_SLAB_PAGE_MASK) + +#define ngx_slab_page_prev(page) \ + (ngx_slab_page_t *) ((page)->prev & ~NGX_SLAB_PAGE_MASK) + +#define ngx_slab_page_addr(pool, page) \ + ((((page) - (pool)->pages) << ngx_pagesize_shift) \ + + (uintptr_t) (pool)->start) + + +#if (NGX_DEBUG_MALLOC) + +#define ngx_slab_junk(p, size) ngx_memset(p, 0xA5, size) + +#elif (NGX_HAVE_DEBUG_MALLOC) + +#define ngx_slab_junk(p, size) \ + if (ngx_debug_malloc) ngx_memset(p, 0xA5, size) + +#else + +#define ngx_slab_junk(p, size) + +#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 void ngx_slab_error(ngx_slab_pool_t *pool, ngx_uint_t level, + char *text); + + +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, *page; + + /* 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 = (size_t) 1 << pool->min_shift; + + slots = ngx_slab_slots(pool); + + p = (u_char *) slots; + size = pool->end - p; + + ngx_slab_junk(p, size); + + n = ngx_pagesize_shift - pool->min_shift; + + for (i = 0; i < n; i++) { + /* only "next" is used in list head */ + slots[i].slab = 0; + slots[i].next = &slots[i]; + slots[i].prev = 0; + } + + p += n * sizeof(ngx_slab_page_t); + + pool->stats = (ngx_slab_stat_t *) p; + ngx_memzero(pool->stats, n * sizeof(ngx_slab_stat_t)); + + p += n * sizeof(ngx_slab_stat_t); + + size -= n * (sizeof(ngx_slab_page_t) + sizeof(ngx_slab_stat_t)); + + pages = (ngx_uint_t) (size / (ngx_pagesize + sizeof(ngx_slab_page_t))); + + pool->pages = (ngx_slab_page_t *) p; + ngx_memzero(pool->pages, pages * sizeof(ngx_slab_page_t)); + + page = pool->pages; + + /* only "next" is used in list head */ + pool->free.slab = 0; + pool->free.next = page; + pool->free.prev = 0; + + page->slab = pages; + page->next = &pool->free; + page->prev = (uintptr_t) &pool->free; + + pool->start = ngx_align_ptr(p + pages * sizeof(ngx_slab_page_t), + ngx_pagesize); + + m = pages - (pool->end - pool->start) / ngx_pagesize; + if (m > 0) { + pages -= m; + page->slab = pages; + } + + pool->last = pool->pages + pages; + pool->pfree = pages; + + pool->log_nomem = 1; + pool->log_ctx = &pool->zero; + pool->zero = '\0'; +} + + +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_shift) + + ((size % ngx_pagesize) ? 1 : 0)); + if (page) { + p = ngx_slab_page_addr(pool, page); + + } 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 { + shift = pool->min_shift; + slot = 0; + } + + pool->stats[slot].reqs++; + + ngx_log_debug2(NGX_LOG_DEBUG_ALLOC, ngx_cycle->log, 0, + "slab alloc: %uz slot: %ui", size, slot); + + slots = ngx_slab_slots(pool); + page = slots[slot].next; + + if (page->next != page) { + + if (shift < ngx_slab_exact_shift) { + + bitmap = (uintptr_t *) ngx_slab_page_addr(pool, page); + + map = (ngx_pagesize >> 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 + i) << shift; + + p = (uintptr_t) bitmap + i; + + pool->stats[slot].used++; + + if (bitmap[n] == NGX_SLAB_BUSY) { + for (n = n + 1; n < map; n++) { + if (bitmap[n] != NGX_SLAB_BUSY) { + goto done; + } + } + + prev = ngx_slab_page_prev(page); + prev->next = page->next; + page->next->prev = page->prev; + + page->next = NULL; + page->prev = NGX_SLAB_SMALL; + } + + goto done; + } + } + } + + } else if (shift == ngx_slab_exact_shift) { + + 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_prev(page); + prev->next = page->next; + page->next->prev = page->prev; + + page->next = NULL; + page->prev = NGX_SLAB_EXACT; + } + + p = ngx_slab_page_addr(pool, page) + (i << shift); + + pool->stats[slot].used++; + + goto done; + } + + } else { /* shift > ngx_slab_exact_shift */ + + mask = ((uintptr_t) 1 << (ngx_pagesize >> shift)) - 1; + mask <<= NGX_SLAB_MAP_SHIFT; + + 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_prev(page); + prev->next = page->next; + page->next->prev = page->prev; + + page->next = NULL; + page->prev = NGX_SLAB_BIG; + } + + p = ngx_slab_page_addr(pool, page) + (i << shift); + + pool->stats[slot].used++; + + goto done; + } + } + + ngx_slab_error(pool, NGX_LOG_ALERT, "ngx_slab_alloc(): page is busy"); + ngx_debug_point(); + } + + page = ngx_slab_alloc_pages(pool, 1); + + if (page) { + if (shift < ngx_slab_exact_shift) { + bitmap = (uintptr_t *) ngx_slab_page_addr(pool, page); + + n = (ngx_pagesize >> shift) / ((1 << shift) * 8); + + if (n == 0) { + n = 1; + } + + /* "n" elements for bitmap, plus one requested */ + bitmap[0] = ((uintptr_t) 2 << n) - 1; + + map = (ngx_pagesize >> 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; + + pool->stats[slot].total += (ngx_pagesize >> shift) - n; + + p = ngx_slab_page_addr(pool, page) + (n << shift); + + pool->stats[slot].used++; + + 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; + + pool->stats[slot].total += sizeof(uintptr_t) * 8; + + p = ngx_slab_page_addr(pool, page); + + pool->stats[slot].used++; + + 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; + + pool->stats[slot].total += ngx_pagesize >> shift; + + p = ngx_slab_page_addr(pool, page); + + pool->stats[slot].used++; + + goto done; + } + } + + p = 0; + + pool->stats[slot].fails++; + +done: + + ngx_log_debug1(NGX_LOG_DEBUG_ALLOC, ngx_cycle->log, 0, + "slab alloc: %p", (void *) p); + + return (void *) p; +} + + +void * +ngx_slab_calloc(ngx_slab_pool_t *pool, size_t size) +{ + void *p; + + ngx_shmtx_lock(&pool->mutex); + + p = ngx_slab_calloc_locked(pool, size); + + ngx_shmtx_unlock(&pool->mutex); + + return p; +} + + +void * +ngx_slab_calloc_locked(ngx_slab_pool_t *pool, size_t size) +{ + void *p; + + p = ngx_slab_alloc_locked(pool, size); + if (p) { + ngx_memzero(p, size); + } + + return 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 i, 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_slab_error(pool, NGX_LOG_ALERT, "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 = ngx_slab_page_type(page); + + switch (type) { + + case NGX_SLAB_SMALL: + + shift = slab & NGX_SLAB_SHIFT_MASK; + size = (size_t) 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)); + n /= sizeof(uintptr_t) * 8; + bitmap = (uintptr_t *) + ((uintptr_t) p & ~((uintptr_t) ngx_pagesize - 1)); + + if (bitmap[n] & m) { + slot = shift - pool->min_shift; + + if (page->next == NULL) { + slots = ngx_slab_slots(pool); + + 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 = (ngx_pagesize >> shift) / ((1 << shift) * 8); + + if (n == 0) { + n = 1; + } + + if (bitmap[0] & ~(((uintptr_t) 1 << n) - 1)) { + goto done; + } + + map = (ngx_pagesize >> shift) / (sizeof(uintptr_t) * 8); + + for (i = 1; i < map; i++) { + if (bitmap[i]) { + goto done; + } + } + + ngx_slab_free_pages(pool, page, 1); + + pool->stats[slot].total -= (ngx_pagesize >> shift) - n; + + 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) { + slot = ngx_slab_exact_shift - pool->min_shift; + + if (slab == NGX_SLAB_BUSY) { + slots = ngx_slab_slots(pool); + + 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); + + pool->stats[slot].total -= sizeof(uintptr_t) * 8; + + goto done; + } + + goto chunk_already_free; + + case NGX_SLAB_BIG: + + shift = slab & NGX_SLAB_SHIFT_MASK; + size = (size_t) 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) { + slot = shift - pool->min_shift; + + if (page->next == NULL) { + slots = ngx_slab_slots(pool); + + 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); + + pool->stats[slot].total -= ngx_pagesize >> shift; + + 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_START)) { + ngx_slab_error(pool, NGX_LOG_ALERT, + "ngx_slab_free(): page is already free"); + goto fail; + } + + if (slab == NGX_SLAB_PAGE_BUSY) { + ngx_slab_error(pool, NGX_LOG_ALERT, + "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); + + ngx_slab_junk(p, size << ngx_pagesize_shift); + + return; + } + + /* not reached */ + + return; + +done: + + pool->stats[slot].used--; + + ngx_slab_junk(p, size); + + return; + +wrong_chunk: + + ngx_slab_error(pool, NGX_LOG_ALERT, + "ngx_slab_free(): pointer to wrong chunk"); + + goto fail; + +chunk_already_free: + + ngx_slab_error(pool, NGX_LOG_ALERT, + "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[page->slab - 1].prev = (uintptr_t) &page[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; + page->next = NULL; + page->prev = NGX_SLAB_PAGE; + + pool->pfree -= pages; + + if (--pages == 0) { + return page; + } + + for (p = page + 1; pages; pages--) { + p->slab = NGX_SLAB_PAGE_BUSY; + p->next = NULL; + p->prev = NGX_SLAB_PAGE; + p++; + } + + return page; + } + } + + if (pool->log_nomem) { + ngx_slab_error(pool, NGX_LOG_CRIT, + "ngx_slab_alloc() failed: no memory"); + } + + 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, *join; + + pool->pfree += pages; + + page->slab = pages--; + + if (pages) { + ngx_memzero(&page[1], pages * sizeof(ngx_slab_page_t)); + } + + if (page->next) { + prev = ngx_slab_page_prev(page); + prev->next = page->next; + page->next->prev = page->prev; + } + + join = page + page->slab; + + if (join < pool->last) { + + if (ngx_slab_page_type(join) == NGX_SLAB_PAGE) { + + if (join->next != NULL) { + pages += join->slab; + page->slab += join->slab; + + prev = ngx_slab_page_prev(join); + prev->next = join->next; + join->next->prev = join->prev; + + join->slab = NGX_SLAB_PAGE_FREE; + join->next = NULL; + join->prev = NGX_SLAB_PAGE; + } + } + } + + if (page > pool->pages) { + join = page - 1; + + if (ngx_slab_page_type(join) == NGX_SLAB_PAGE) { + + if (join->slab == NGX_SLAB_PAGE_FREE) { + join = ngx_slab_page_prev(join); + } + + if (join->next != NULL) { + pages += join->slab; + join->slab += page->slab; + + prev = ngx_slab_page_prev(join); + prev->next = join->next; + join->next->prev = join->prev; + + page->slab = NGX_SLAB_PAGE_FREE; + page->next = NULL; + page->prev = NGX_SLAB_PAGE; + + page = join; + } + } + } + + if (pages) { + page[pages].prev = (uintptr_t) page; + } + + page->prev = (uintptr_t) &pool->free; + page->next = pool->free.next; + + page->next->prev = (uintptr_t) page; + + pool->free.next = page; +} + + +static void +ngx_slab_error(ngx_slab_pool_t *pool, ngx_uint_t level, char *text) +{ + ngx_log_error(level, ngx_cycle->log, 0, "%s%s", text, pool->log_ctx); +} |