# HG changeset patch # User Igor Sysoev # Date 1164012705 0 # Node ID 201d017ea470484999b8227733783c37a8727fc0 # Parent d1e8c59a50eefc8499eecaa0f85ea5f2bd09380d slab allocator in shared memory diff -r d1e8c59a50ee -r 201d017ea470 auto/sources --- a/auto/sources Sun Nov 19 07:27:10 2006 +0000 +++ b/auto/sources Mon Nov 20 08:51:45 2006 +0000 @@ -23,6 +23,7 @@ src/core/ngx_crc32.h \ src/core/ngx_rbtree.h \ src/core/ngx_radix_tree.h \ + src/core/ngx_slab.h \ src/core/ngx_times.h \ src/core/ngx_shmtx.h \ src/core/ngx_connection.h \ @@ -46,6 +47,7 @@ src/core/ngx_crc32.c \ src/core/ngx_rbtree.c \ src/core/ngx_radix_tree.c \ + src/core/ngx_slab.c \ src/core/ngx_times.c \ src/core/ngx_shmtx.c \ src/core/ngx_connection.c \ diff -r d1e8c59a50ee -r 201d017ea470 src/core/nginx.c --- a/src/core/nginx.c Sun Nov 19 07:27:10 2006 +0000 +++ b/src/core/nginx.c Mon Nov 20 08:51:45 2006 +0000 @@ -621,6 +621,7 @@ ngx_core_conf_t *ccf = conf; #if !(NGX_WIN32) + ngx_str_t lock_file; struct passwd *pwd; struct group *grp; #endif @@ -697,6 +698,7 @@ ngx_memcpy(ngx_cpymem(ccf->oldpid.data, ccf->pid.data, ccf->pid.len), NGX_OLDPID_EXT, sizeof(NGX_OLDPID_EXT)); + if (ccf->lock_file.len == 0) { ccf->lock_file.len = sizeof(NGX_LOCK_PATH) - 1; ccf->lock_file.data = (u_char *) NGX_LOCK_PATH; @@ -706,6 +708,40 @@ return NGX_CONF_ERROR; } + lock_file = cycle->old_cycle->lock_file; + + if (lock_file.len) { + lock_file.len--; + + if (ccf->lock_file.len != lock_file.len + || ngx_strncmp(ccf->lock_file.data, lock_file.data, lock_file.len) + != 0) + { + ngx_log_error(NGX_LOG_EMERG, cycle->log, 0, + "\"lock_file\" could not be changed, ignored"); + } + + cycle->lock_file.len = lock_file.len + 1; + lock_file.len += sizeof(".accept"); + + cycle->lock_file.data = ngx_pstrdup(cycle->pool, &lock_file); + if (cycle->lock_file.data == NULL) { + return NGX_CONF_ERROR; + } + + } else { + cycle->lock_file.len = ccf->lock_file.len + 1; + cycle->lock_file.data = ngx_palloc(cycle->pool, + ccf->lock_file.len + sizeof(".accept")); + if (cycle->lock_file.data == NULL) { + return NGX_CONF_ERROR; + } + + ngx_memcpy(ngx_cpymem(cycle->lock_file.data, ccf->lock_file.data, + ccf->lock_file.len), + ".accept", sizeof(".accept")); + } + #endif return NGX_CONF_OK; diff -r d1e8c59a50ee -r 201d017ea470 src/core/ngx_core.h --- a/src/core/ngx_core.h Sun Nov 19 07:27:10 2006 +0000 +++ b/src/core/ngx_core.h Mon Nov 20 08:51:45 2006 +0000 @@ -64,6 +64,7 @@ #include #include #include +#include #if (NGX_OPENSSL) #include #endif diff -r d1e8c59a50ee -r 201d017ea470 src/core/ngx_cycle.c --- a/src/core/ngx_cycle.c Sun Nov 19 07:27:10 2006 +0000 +++ b/src/core/ngx_cycle.c Mon Nov 20 08:51:45 2006 +0000 @@ -43,12 +43,15 @@ ngx_init_cycle(ngx_cycle_t *old_cycle) { void *rv; + u_char *lock_file; ngx_uint_t i, n; ngx_log_t *log; ngx_conf_t conf; ngx_pool_t *pool; ngx_cycle_t *cycle, **old; - ngx_list_part_t *part; + ngx_shm_zone_t *shm, *oshm; + ngx_slab_pool_t *shpool; + ngx_list_part_t *part, *opart; ngx_open_file_t *file; ngx_listening_t *ls, *nls; ngx_core_conf_t *ccf; @@ -120,6 +123,25 @@ } + if (old_cycle->shared_memory.part.nelts) { + n = old_cycle->shared_memory.part.nelts; + for (part = old_cycle->shared_memory.part.next; part; part = part->next) + { + n += part->nelts; + } + + } else { + n = 1; + } + + if (ngx_list_init(&cycle->shared_memory, pool, n, sizeof(ngx_shm_zone_t)) + == NGX_ERROR) + { + ngx_destroy_pool(pool); + return NULL; + } + + cycle->new_log = ngx_log_create_errlog(cycle, NULL); if (cycle->new_log == NULL) { ngx_destroy_pool(pool); @@ -183,21 +205,6 @@ } -#if 0 - cycle->shm.size = /* STUB */ ngx_pagesize; - cycle->shm.log = log; - - if (ngx_shm_alloc(&cycle->shm) != NGX_OK) { - ngx_destroy_pool(conf.temp_pool); - ngx_destroy_pool(pool); - return NULL; - } - - cycle->shm_last = cycle->shm.addr; - cycle->shm_end = cycle->shm.addr + cycle->shm.size; -#endif - - conf.ctx = cycle->conf_ctx; conf.cycle = cycle; conf.pool = pool; @@ -274,7 +281,7 @@ #endif - if (ngx_test_lockfile(ccf->lock_file.data, log) != NGX_OK) { + if (ngx_test_lockfile(cycle->lock_file.data, log) != NGX_OK) { goto failed; } @@ -343,6 +350,94 @@ } + /* create shared memory */ + + part = &cycle->shared_memory.part; + shm = part->elts; + + for (i = 0; /* void */ ; i++) { + + if (i >= part->nelts) { + if (part->next == NULL) { + break; + } + part = part->next; + shm = part->elts; + i = 0; + } + + shm[i].shm.log = cycle->log; + + opart = &old_cycle->shared_memory.part; + oshm = opart->elts; + + for (n = 0; /* void */ ; n++) { + + if (n >= opart->nelts) { + if (opart->next == NULL) { + break; + } + opart = opart->next; + oshm = opart->elts; + n = 0; + } + + if (ngx_strcmp(shm[i].name.data, oshm[n].name.data) != 0) { + continue; + } + + if (shm[i].shm.size == oshm[n].shm.size) { + shm[i].shm.addr = oshm[n].shm.addr; + goto found; + } + + ngx_shm_free(&oshm[n].shm); + + break; + } + + if (ngx_shm_alloc(&shm[i].shm) != NGX_OK) { + goto failed; + } + + shpool = (ngx_slab_pool_t *) shm[i].shm.addr; + + shpool->end = shm[i].shm.addr + shm[i].shm.size; + shpool->min_shift = 3; + +#if (NGX_HAVE_ATOMIC_OPS) + + lock_file = NULL; + +#else + + lock_file = ngx_palloc(cycle->pool, + cycle->lock_file.len + shm[i].name.len); + + if (lock_file == NULL) { + goto failed; + } + + (void) ngx_cpystrn(ngx_cpymem(lock_file, cycle->lock_file.data, + cycle->lock_file.len), + shm[i].name.data, shm[i].name.len + 1); + +#endif + + if (ngx_shmtx_create(&shpool->mutex, (void *) &shpool->lock, lock_file) + != NGX_OK) + { + goto failed; + } + + ngx_slab_init(shpool); + + found: + + continue; + } + + /* handle the listening sockets */ if (old_cycle->listening.nelts) { @@ -521,12 +616,7 @@ if (ngx_process == NGX_PROCESS_MASTER || ngx_is_init_cycle(old_cycle)) { - if (old_cycle->shm.addr) { - ngx_shm_free(&old_cycle->shm); - } - ngx_destroy_pool(old_cycle->pool); - cycle->old_cycle = NULL; return cycle; @@ -630,10 +720,6 @@ static void ngx_destroy_cycle_pools(ngx_conf_t *conf) { - if (conf->cycle->shm.addr) { - ngx_shm_free(&conf->cycle->shm); - } - ngx_destroy_pool(conf->temp_pool); ngx_destroy_pool(conf->pool); } diff -r d1e8c59a50ee -r 201d017ea470 src/core/ngx_cycle.h --- a/src/core/ngx_cycle.h Sun Nov 19 07:27:10 2006 +0000 +++ b/src/core/ngx_cycle.h Mon Nov 20 08:51:45 2006 +0000 @@ -21,6 +21,12 @@ #define NGX_DEBUG_POINTS_ABORT 2 +typedef struct { + ngx_shm_t shm; + ngx_str_t name; +} ngx_shm_zone_t; + + struct ngx_cycle_s { void ****conf_ctx; ngx_pool_t *pool; @@ -32,13 +38,10 @@ ngx_connection_t *free_connections; ngx_uint_t free_connection_n; - ngx_shm_t shm; - u_char *shm_last; - u_char *shm_end; - ngx_array_t listening; ngx_array_t pathes; ngx_list_t open_files; + ngx_list_t shared_memory; ngx_uint_t connection_n; ngx_uint_t files_n; @@ -51,6 +54,7 @@ ngx_str_t conf_file; ngx_str_t root; + ngx_str_t lock_file; }; diff -r d1e8c59a50ee -r 201d017ea470 src/core/ngx_log.c --- a/src/core/ngx_log.c Sun Nov 19 07:27:10 2006 +0000 +++ b/src/core/ngx_log.c Mon Nov 20 08:51:45 2006 +0000 @@ -190,6 +190,13 @@ #endif +void +ngx_log_abort(ngx_err_t err, const char *text) +{ + ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, err, text); +} + + ngx_log_t * ngx_log_init(void) { diff -r d1e8c59a50ee -r 201d017ea470 src/core/ngx_log.h --- a/src/core/ngx_log.h Sun Nov 19 07:27:10 2006 +0000 +++ b/src/core/ngx_log.h Mon Nov 20 08:51:45 2006 +0000 @@ -201,6 +201,7 @@ ngx_log_t *ngx_log_init(void); ngx_log_t *ngx_log_create_errlog(ngx_cycle_t *cycle, ngx_array_t *args); char *ngx_set_error_log_levels(ngx_conf_t *cf, ngx_log_t *log); +void ngx_log_abort(ngx_err_t err, const char *text); extern ngx_module_t ngx_errlog_module; diff -r d1e8c59a50ee -r 201d017ea470 src/core/ngx_palloc.c --- a/src/core/ngx_palloc.c Sun Nov 19 07:27:10 2006 +0000 +++ b/src/core/ngx_palloc.c Mon Nov 20 08:51:45 2006 +0000 @@ -193,46 +193,6 @@ } -void * -ngx_shalloc(size_t size) -{ - u_char *p; - - if (size < sizeof(int) || (size & 1)) { - p = ngx_cycle->shm_last; - - } else { - p = ngx_align_ptr(ngx_cycle->shm_last, NGX_ALIGNMENT); - } - - if ((size_t) (ngx_cycle->shm_end - p) >= size) { - ngx_cycle->shm_last = p + size; - return p; - } - - ngx_log_error(NGX_LOG_EMERG, ngx_cycle->log, 0, - "allocation of %uz bytes in shared memory failed, " - "only %uz are available", - size, ngx_cycle->shm_end - ngx_cycle->shm_last); - - return NULL; -} - - -void * -ngx_shcalloc(size_t size) -{ - void *p; - - p = ngx_shalloc(size); - if (p) { - ngx_memzero(p, size); - } - - return p; -} - - ngx_pool_cleanup_t * ngx_pool_cleanup_add(ngx_pool_t *p, size_t size) { diff -r d1e8c59a50ee -r 201d017ea470 src/core/ngx_palloc.h --- a/src/core/ngx_palloc.h Sun Nov 19 07:27:10 2006 +0000 +++ b/src/core/ngx_palloc.h Mon Nov 20 08:51:45 2006 +0000 @@ -71,10 +71,6 @@ void *ngx_pcalloc(ngx_pool_t *pool, size_t size); ngx_int_t ngx_pfree(ngx_pool_t *pool, void *p); -void *ngx_shalloc(size_t size); -void *ngx_shcalloc(size_t size); -void ngx_shfree(void *p); - ngx_pool_cleanup_t *ngx_pool_cleanup_add(ngx_pool_t *p, size_t size); void ngx_pool_cleanup_file(void *data); diff -r d1e8c59a50ee -r 201d017ea470 src/core/ngx_shmtx.c --- a/src/core/ngx_shmtx.c Sun Nov 19 07:27:10 2006 +0000 +++ b/src/core/ngx_shmtx.c Mon Nov 20 08:51:45 2006 +0000 @@ -12,7 +12,7 @@ ngx_int_t -ngx_shmtx_create(ngx_shmtx_t *mtx, void *addr, u_char *name, ngx_log_t *log) +ngx_shmtx_create(ngx_shmtx_t *mtx, void *addr, u_char *name) { mtx->lock = addr; @@ -23,14 +23,12 @@ ngx_int_t -ngx_shmtx_create(ngx_shmtx_t *mtx, void *addr, u_char *name, ngx_log_t *log) +ngx_shmtx_create(ngx_shmtx_t *mtx, void *addr, u_char *name) { if (mtx->name) { if (ngx_strcmp(name, mtx->name) == 0) { mtx->name = name; - mtx->log = log; - return NGX_OK; } @@ -40,18 +38,17 @@ mtx->fd = ngx_open_file(name, NGX_FILE_RDWR, NGX_FILE_CREATE_OR_OPEN); if (mtx->fd == NGX_INVALID_FILE) { - ngx_log_error(NGX_LOG_EMERG, log, ngx_errno, + ngx_log_error(NGX_LOG_EMERG, ngx_cycle->log, ngx_errno, ngx_open_file_n " \"%s\" failed", name); return NGX_ERROR; } if (ngx_delete_file(name) == NGX_FILE_ERROR) { - ngx_log_error(NGX_LOG_ALERT, log, ngx_errno, + ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, ngx_errno, ngx_delete_file_n " \"%s\" failed", name); } mtx->name = name; - mtx->log = log; return NGX_OK; } @@ -61,7 +58,7 @@ ngx_shmtx_destory(ngx_shmtx_t *mtx) { if (ngx_close_file(mtx->fd) == NGX_FILE_ERROR) { - ngx_log_error(NGX_LOG_ALERT, mtx->log, ngx_errno, + ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, ngx_errno, ngx_close_file_n " \"%s\" failed", mtx->name); } } diff -r d1e8c59a50ee -r 201d017ea470 src/core/ngx_shmtx.h --- a/src/core/ngx_shmtx.h Sun Nov 19 07:27:10 2006 +0000 +++ b/src/core/ngx_shmtx.h Mon Nov 20 08:51:45 2006 +0000 @@ -18,13 +18,11 @@ #else ngx_fd_t fd; u_char *name; - ngx_log_t *log; #endif } ngx_shmtx_t; -ngx_int_t ngx_shmtx_create(ngx_shmtx_t *mtx, void *addr, u_char *name, - ngx_log_t *log); +ngx_int_t ngx_shmtx_create(ngx_shmtx_t *mtx, void *addr, u_char *name); #if (NGX_HAVE_ATOMIC_OPS) @@ -63,9 +61,7 @@ return 0; } - ngx_log_error(NGX_LOG_ALERT, mtx->log, err, ngx_trylock_fd_n " failed"); - - ngx_abort(); + ngx_log_abort(err, ngx_trylock_fd_n " failed"); } @@ -80,9 +76,7 @@ return; } - ngx_log_error(NGX_LOG_ALERT, mtx->log, err, ngx_lock_fd_n " failed"); - - ngx_abort(); + ngx_log_abort(err, ngx_lock_fd_n " failed"); } @@ -97,9 +91,7 @@ return; } - ngx_log_error(NGX_LOG_ALERT, mtx->log, err, ngx_unlock_fd_n " failed"); - - ngx_abort(); + ngx_log_abort(err, ngx_unlock_fd_n " failed"); } diff -r d1e8c59a50ee -r 201d017ea470 src/core/ngx_slab.c --- a/src/core/ngx_slab.c Sun Nov 19 07:27:10 2006 +0000 +++ b/src/core/ngx_slab.c Mon Nov 20 08:51:45 2006 +0000 @@ -3,9 +3,683 @@ * Copyright (C) Igor Sysoev */ +#include +#include + +/* + + 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 +#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 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); + + /* STUB: possible overflow on 64-bit platform */ + pages = (ngx_uint_t) ((uint64_t) size * ngx_pagesize + / (ngx_pagesize + sizeof(ngx_slab_page_t)) + / ngx_pagesize); + + 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((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 * +ngx_slab_alloc(ngx_slab_pool_t *pool, size_t size) +{ + size_t s; + uintptr_t p, mask, *bitmap; + ngx_uint_t i, n, m, slot, shift, map; + ngx_slab_page_t *page, *prev, *slots; + + ngx_shmtx_lock(&pool->mutex); + + if (size >= ngx_slab_max_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 0 + ngx_log_debug2(NGX_LOG_DEBUG_ALLOC, ngx_cycle->log, 0, + "slab alloc: page %p next: %p", page, page->next); +#endif + + if (page->next != page) { + + if (size < ngx_slab_exact_size) { + + 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 <<= 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 (size == ngx_slab_exact_size) { + + 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 { /* size < ngx_pagesize */ + + n = ngx_pagesize_shift - (page->slab & NGX_SLAB_SHIFT_MASK); + n = 1 << n; + n = (1 << n) - 1; + mask = n << NGX_SLAB_MAP_SHIFT; + + do { + if ((page->slab & NGX_SLAB_MAP_MASK) != mask) { + + for (m = 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 (size < ngx_slab_exact_size) { + 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 (size == ngx_slab_exact_size) { + + 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 { /* size < ngx_pagesize */ + + page->slab = (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_shmtx_unlock(&pool->mutex); + + 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) { - return NULL; + size_t size; + uintptr_t slab, *bitmap; + ngx_uint_t n, m, 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); + + ngx_shmtx_lock(&pool->mutex); + + 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 = 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] & ~((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 = 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 = 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); + + ngx_shmtx_unlock(&pool->mutex); + + 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: + + ngx_shmtx_unlock(&pool->mutex); + + 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)); + } + + prev = (ngx_slab_page_t *) (page->prev & ~NGX_SLAB_PAGE_MASK); + prev->next = page->next; + + page->next = pool->free.next; + pool->free.next = page; + + page->prev = page->next->prev; + page->next->prev = (uintptr_t) page; +} diff -r d1e8c59a50ee -r 201d017ea470 src/core/ngx_slab.h --- a/src/core/ngx_slab.h Sun Nov 19 07:27:10 2006 +0000 +++ b/src/core/ngx_slab.h Mon Nov 20 08:51:45 2006 +0000 @@ -12,32 +12,34 @@ #include -typedef struct ngx_free_slab_s ngx_free_slab_t; - -typedef struct ngx_free_slab_s { - ngx_free_slab_t *next; -} - +typedef struct ngx_slab_page_s ngx_slab_page_t; -typedef struct ngx_slab_block_s ngx_slab_block_t; - -typedef struct ngx_slab_block_s { - ngx_free_slab_t *free; - ngx_slab_buf_t *next; - size_t color; +struct ngx_slab_page_s { + uintptr_t slab; + ngx_slab_page_t *next; + uintptr_t prev; }; typedef struct { - ngx_slab_buf_t *blocks; - size_t size; + ngx_atomic_t lock; + + size_t min_size; + size_t min_shift; - void *start; - uint32_t map; + ngx_slab_page_t *pages; + ngx_slab_page_t free; - ngx_log_t *log; - ngx_free_pool_t free; + u_char *start; + u_char *end; + + ngx_shmtx_t mutex; } ngx_slab_pool_t; +void ngx_slab_init(ngx_slab_pool_t *pool); +void *ngx_slab_alloc(ngx_slab_pool_t *pool, size_t size); +void ngx_slab_free(ngx_slab_pool_t *pool, void *p); + + #endif /* _NGX_SLAB_H_INCLUDED_ */ diff -r d1e8c59a50ee -r 201d017ea470 src/event/ngx_event.c --- a/src/event/ngx_event.c Sun Nov 19 07:27:10 2006 +0000 +++ b/src/event/ngx_event.c Mon Nov 20 08:51:45 2006 +0000 @@ -483,18 +483,7 @@ return NGX_OK; } - if (ngx_accept_mutex_ptr) { - - /* reinit ngx_accept_mutex */ - - if (ngx_shmtx_create(&ngx_accept_mutex, (void *) ngx_accept_mutex_ptr, - ccf->lock_file.data, cycle->log) - != NGX_OK) - { - return NGX_ERROR; - } - return NGX_OK; } @@ -528,8 +517,7 @@ ngx_accept_mutex_ptr = (ngx_atomic_t *) shared; - if (ngx_shmtx_create(&ngx_accept_mutex, shared, ccf->lock_file.data, - cycle->log) + if (ngx_shmtx_create(&ngx_accept_mutex, shared, cycle->lock_file.data) != NGX_OK) { return NGX_ERROR; diff -r d1e8c59a50ee -r 201d017ea470 src/os/unix/ngx_alloc.c --- a/src/os/unix/ngx_alloc.c Sun Nov 19 07:27:10 2006 +0000 +++ b/src/os/unix/ngx_alloc.c Mon Nov 20 08:51:45 2006 +0000 @@ -8,7 +8,8 @@ #include -int ngx_pagesize; +ngx_uint_t ngx_pagesize; +ngx_uint_t ngx_pagesize_shift; ngx_uint_t ngx_cacheline_size; diff -r d1e8c59a50ee -r 201d017ea470 src/os/unix/ngx_alloc.h --- a/src/os/unix/ngx_alloc.h Sun Nov 19 07:27:10 2006 +0000 +++ b/src/os/unix/ngx_alloc.h Mon Nov 20 08:51:45 2006 +0000 @@ -36,7 +36,8 @@ #endif -extern int ngx_pagesize; +extern ngx_uint_t ngx_pagesize; +extern ngx_uint_t ngx_pagesize_shift; extern ngx_uint_t ngx_cacheline_size; diff -r d1e8c59a50ee -r 201d017ea470 src/os/unix/ngx_posix_init.c --- a/src/os/unix/ngx_posix_init.c Sun Nov 19 07:27:10 2006 +0000 +++ b/src/os/unix/ngx_posix_init.c Mon Nov 20 08:51:45 2006 +0000 @@ -30,6 +30,8 @@ ngx_int_t ngx_os_init(ngx_log_t *log) { + ngx_uint_t n; + #if (NGX_HAVE_OS_SPECIFIC_INIT) if (ngx_os_specific_init(log) != NGX_OK) { return NGX_ERROR; @@ -41,6 +43,10 @@ ngx_pagesize = getpagesize(); ngx_cacheline_size = NGX_CPU_CACHE_LINE; + n = ngx_pagesize; + + for (n = ngx_pagesize; n >>= 1; ngx_pagesize_shift++) { /* void */ } + if (ngx_ncpu == 0) { ngx_ncpu = 1; } diff -r d1e8c59a50ee -r 201d017ea470 src/os/win32/ngx_alloc.c --- a/src/os/win32/ngx_alloc.c Sun Nov 19 07:27:10 2006 +0000 +++ b/src/os/win32/ngx_alloc.c Mon Nov 20 08:51:45 2006 +0000 @@ -8,7 +8,8 @@ #include -int ngx_pagesize; +ngx_uint_t ngx_pagesize; +ngx_uint_t ngx_pagesize_shift; ngx_uint_t ngx_cacheline_size; diff -r d1e8c59a50ee -r 201d017ea470 src/os/win32/ngx_alloc.h --- a/src/os/win32/ngx_alloc.h Sun Nov 19 07:27:10 2006 +0000 +++ b/src/os/win32/ngx_alloc.h Mon Nov 20 08:51:45 2006 +0000 @@ -18,7 +18,8 @@ #define ngx_free free #define ngx_memalign(alignment, size, log) ngx_alloc(size, log) -extern int ngx_pagesize; +extern ngx_uint_t ngx_pagesize; +extern ngx_uint_t ngx_pagesize_shift; extern ngx_uint_t ngx_cacheline_size; diff -r d1e8c59a50ee -r 201d017ea470 src/os/win32/ngx_errno.h --- a/src/os/win32/ngx_errno.h Sun Nov 19 07:27:10 2006 +0000 +++ b/src/os/win32/ngx_errno.h Mon Nov 20 08:51:45 2006 +0000 @@ -21,6 +21,7 @@ #define NGX_EPERM ERROR_ACCESS_DENIED #define NGX_ENOENT ERROR_FILE_NOT_FOUND +#define NGX_ENOMEM ERROR_NOT_ENOUGH_MEMORY #define NGX_EACCES ERROR_ACCESS_DENIED #if 0 #define NGX_EEXIST ERROR_FILE_EXISTS diff -r d1e8c59a50ee -r 201d017ea470 src/os/win32/ngx_win32_init.c --- a/src/os/win32/ngx_win32_init.c Sun Nov 19 07:27:10 2006 +0000 +++ b/src/os/win32/ngx_win32_init.c Mon Nov 20 08:51:45 2006 +0000 @@ -53,6 +53,7 @@ DWORD bytes; SOCKET s; WSADATA wsd; + ngx_uint_t n; SYSTEM_INFO si; /* get Windows version */ @@ -101,6 +102,8 @@ ngx_ncpu = si.dwNumberOfProcessors; ngx_cacheline_size = NGX_CPU_CACHE_LINE; + for (n = ngx_pagesize; n >>= 1; ngx_pagesize_shift++) { /* void */ } + /* init Winsock */