163Sigor@sysoev.ru 263Sigor@sysoev.ru /* 363Sigor@sysoev.ru * Copyright (C) Igor Sysoev 463Sigor@sysoev.ru * Copyright (C) NGINX, Inc. 563Sigor@sysoev.ru */ 663Sigor@sysoev.ru 763Sigor@sysoev.ru #include <nxt_main.h> 863Sigor@sysoev.ru 963Sigor@sysoev.ru 1063Sigor@sysoev.ru /* 1163Sigor@sysoev.ru * A memory pool allocates memory in clusters of specified size and aligned 1263Sigor@sysoev.ru * to page_alignment. A cluster is divided on pages of specified size. Page 1363Sigor@sysoev.ru * size must be a power of 2. A page can be used entirely or can be divided 1463Sigor@sysoev.ru * on chunks of equal size. Chunk size must be a power of 2. Non-freeable 1563Sigor@sysoev.ru * memory is also allocated from pages. A cluster can contains a mix of pages 1663Sigor@sysoev.ru * with different chunk sizes and non-freeable pages. Cluster size must be 1763Sigor@sysoev.ru * a multiple of page size and may be not a power of 2. Allocations greater 1863Sigor@sysoev.ru * than page are allocated outside clusters. Start addresses and sizes of 1963Sigor@sysoev.ru * the clusters and large allocations are stored in rbtree blocks to find 2063Sigor@sysoev.ru * them on free operations. The rbtree nodes are sorted by start addresses. 2163Sigor@sysoev.ru * The rbtree is also used to destroy memory pool. 2263Sigor@sysoev.ru */ 2363Sigor@sysoev.ru 2463Sigor@sysoev.ru 2563Sigor@sysoev.ru typedef struct { 2663Sigor@sysoev.ru /* 2763Sigor@sysoev.ru * Used to link 2863Sigor@sysoev.ru * *) pages with free chunks in pool chunk pages lists, 2963Sigor@sysoev.ru * *) pages with free space for non-freeable allocations, 3063Sigor@sysoev.ru * *) free pages in clusters. 3163Sigor@sysoev.ru */ 3263Sigor@sysoev.ru nxt_queue_link_t link; 3363Sigor@sysoev.ru 3463Sigor@sysoev.ru union { 3563Sigor@sysoev.ru /* Chunk bitmap. There can be no more than 32 chunks in a page. */ 3663Sigor@sysoev.ru uint32_t map; 3763Sigor@sysoev.ru 3863Sigor@sysoev.ru /* Size of taken non-freeable space. */ 3963Sigor@sysoev.ru uint32_t taken; 4063Sigor@sysoev.ru } u; 4163Sigor@sysoev.ru 4263Sigor@sysoev.ru /* 4363Sigor@sysoev.ru * Size of chunks or page shifted by pool->chunk_size_shift. Zero means 4463Sigor@sysoev.ru * that page is free, 0xFF means page with non-freeable allocations. 4563Sigor@sysoev.ru */ 4663Sigor@sysoev.ru uint8_t size; 4763Sigor@sysoev.ru 4863Sigor@sysoev.ru /* Number of free chunks of a chunked page. */ 4963Sigor@sysoev.ru uint8_t chunks; 5063Sigor@sysoev.ru 5163Sigor@sysoev.ru /* 5263Sigor@sysoev.ru * Number of allocation fails due to free space insufficiency 5363Sigor@sysoev.ru * in non-freeable page. 5463Sigor@sysoev.ru */ 5563Sigor@sysoev.ru uint8_t fails; 5663Sigor@sysoev.ru 5763Sigor@sysoev.ru /* 5863Sigor@sysoev.ru * Page number in page cluster. 5963Sigor@sysoev.ru * There can be no more than 256 pages in a cluster. 6063Sigor@sysoev.ru */ 6163Sigor@sysoev.ru uint8_t number; 6263Sigor@sysoev.ru } nxt_mp_page_t; 6363Sigor@sysoev.ru 6463Sigor@sysoev.ru 6563Sigor@sysoev.ru /* 6663Sigor@sysoev.ru * Some malloc implementations (e.g. jemalloc) allocates large enough 6763Sigor@sysoev.ru * blocks (e.g. greater than 4K) with 4K alignment. So if a block 6863Sigor@sysoev.ru * descriptor will be allocated together with the block it will take 6963Sigor@sysoev.ru * excessive 4K memory. So it is better to allocate the block descriptor 7063Sigor@sysoev.ru * apart. 7163Sigor@sysoev.ru */ 7263Sigor@sysoev.ru 7363Sigor@sysoev.ru typedef enum { 7463Sigor@sysoev.ru /* Block of cluster. The block is allocated apart of the cluster. */ 7563Sigor@sysoev.ru NXT_MP_CLUSTER_BLOCK = 0, 7663Sigor@sysoev.ru /* 7763Sigor@sysoev.ru * Block of large allocation. 7863Sigor@sysoev.ru * The block is allocated apart of the allocation. 7963Sigor@sysoev.ru */ 8063Sigor@sysoev.ru NXT_MP_DISCRETE_BLOCK, 8163Sigor@sysoev.ru /* 8263Sigor@sysoev.ru * Block of large allocation. 8363Sigor@sysoev.ru * The block is allocated just after of the allocation. 8463Sigor@sysoev.ru */ 8563Sigor@sysoev.ru NXT_MP_EMBEDDED_BLOCK, 8663Sigor@sysoev.ru } nxt_mp_block_type_t; 8763Sigor@sysoev.ru 8863Sigor@sysoev.ru 8963Sigor@sysoev.ru typedef struct { 9063Sigor@sysoev.ru NXT_RBTREE_NODE (node); 9163Sigor@sysoev.ru nxt_mp_block_type_t type:8; 9263Sigor@sysoev.ru 9363Sigor@sysoev.ru /* Block size must be less than 4G. */ 9463Sigor@sysoev.ru uint32_t size; 9563Sigor@sysoev.ru 9663Sigor@sysoev.ru u_char *start; 9763Sigor@sysoev.ru nxt_mp_page_t pages[]; 9863Sigor@sysoev.ru } nxt_mp_block_t; 9963Sigor@sysoev.ru 10063Sigor@sysoev.ru 10163Sigor@sysoev.ru struct nxt_mp_s { 10263Sigor@sysoev.ru /* rbtree of nxt_mp_block_t. */ 10363Sigor@sysoev.ru nxt_rbtree_t blocks; 10463Sigor@sysoev.ru 10563Sigor@sysoev.ru uint8_t chunk_size_shift; 10663Sigor@sysoev.ru uint8_t page_size_shift; 10763Sigor@sysoev.ru uint32_t page_size; 10863Sigor@sysoev.ru uint32_t page_alignment; 10963Sigor@sysoev.ru uint32_t cluster_size; 11063Sigor@sysoev.ru uint32_t retain; 11163Sigor@sysoev.ru 112128Smax.romanov@nginx.com #if (NXT_DEBUG) 113128Smax.romanov@nginx.com nxt_pid_t pid; 114128Smax.romanov@nginx.com nxt_tid_t tid; 115128Smax.romanov@nginx.com #endif 116128Smax.romanov@nginx.com 11763Sigor@sysoev.ru /* Lists of nxt_mp_page_t. */ 11863Sigor@sysoev.ru nxt_queue_t free_pages; 11963Sigor@sysoev.ru nxt_queue_t nget_pages; 12063Sigor@sysoev.ru nxt_queue_t get_pages; 12193Smax.romanov@nginx.com nxt_queue_t chunk_pages[]; 12263Sigor@sysoev.ru }; 12363Sigor@sysoev.ru 12463Sigor@sysoev.ru 12563Sigor@sysoev.ru #define nxt_mp_chunk_get_free(map) \ 12663Sigor@sysoev.ru (__builtin_ffs(map) - 1) 12763Sigor@sysoev.ru 12863Sigor@sysoev.ru 12963Sigor@sysoev.ru #define nxt_mp_chunk_is_free(map, chunk) \ 13063Sigor@sysoev.ru ((map & (1 << chunk)) != 0) 13163Sigor@sysoev.ru 13263Sigor@sysoev.ru 13363Sigor@sysoev.ru #define nxt_mp_chunk_set_busy(map, chunk) \ 13463Sigor@sysoev.ru map &= ~(1 << chunk) 13563Sigor@sysoev.ru 13663Sigor@sysoev.ru 13763Sigor@sysoev.ru #define nxt_mp_chunk_set_free(map, chunk) \ 13863Sigor@sysoev.ru map |= (1 << chunk) 13963Sigor@sysoev.ru 14063Sigor@sysoev.ru 14163Sigor@sysoev.ru #define nxt_mp_free_junk(p, size) \ 14263Sigor@sysoev.ru memset((p), 0x5A, size) 14363Sigor@sysoev.ru 14463Sigor@sysoev.ru 14563Sigor@sysoev.ru #if !(NXT_DEBUG_MEMORY) 14668Sigor@sysoev.ru static void *nxt_mp_alloc_small(nxt_mp_t *mp, size_t size); 14763Sigor@sysoev.ru static void *nxt_mp_get_small(nxt_mp_t *mp, nxt_queue_t *pages, size_t size); 14863Sigor@sysoev.ru static nxt_mp_page_t *nxt_mp_alloc_page(nxt_mp_t *mp); 14963Sigor@sysoev.ru static nxt_mp_block_t *nxt_mp_alloc_cluster(nxt_mp_t *mp); 15063Sigor@sysoev.ru #endif 15163Sigor@sysoev.ru static void *nxt_mp_alloc_large(nxt_mp_t *mp, size_t alignment, size_t size); 15263Sigor@sysoev.ru static intptr_t nxt_mp_rbtree_compare(nxt_rbtree_node_t *node1, 15363Sigor@sysoev.ru nxt_rbtree_node_t *node2); 15463Sigor@sysoev.ru static nxt_mp_block_t *nxt_mp_find_block(nxt_rbtree_t *tree, u_char *p); 15563Sigor@sysoev.ru static const char *nxt_mp_chunk_free(nxt_mp_t *mp, nxt_mp_block_t *cluster, 15663Sigor@sysoev.ru u_char *p); 15763Sigor@sysoev.ru 15863Sigor@sysoev.ru 15993Smax.romanov@nginx.com #if (NXT_HAVE_BUILTIN_CLZ) 16093Smax.romanov@nginx.com 16193Smax.romanov@nginx.com #define nxt_lg2(value) \ 16293Smax.romanov@nginx.com (31 - __builtin_clz(value)) 16393Smax.romanov@nginx.com 16493Smax.romanov@nginx.com #else 16593Smax.romanov@nginx.com 16693Smax.romanov@nginx.com static const int nxt_lg2_tab64[64] = { 16793Smax.romanov@nginx.com 63, 0, 58, 1, 59, 47, 53, 2, 16893Smax.romanov@nginx.com 60, 39, 48, 27, 54, 33, 42, 3, 16993Smax.romanov@nginx.com 61, 51, 37, 40, 49, 18, 28, 20, 17093Smax.romanov@nginx.com 55, 30, 34, 11, 43, 14, 22, 4, 17193Smax.romanov@nginx.com 62, 57, 46, 52, 38, 26, 32, 41, 17293Smax.romanov@nginx.com 50, 36, 17, 19, 29, 10, 13, 21, 17393Smax.romanov@nginx.com 56, 45, 25, 31, 35, 16, 9, 12, 17493Smax.romanov@nginx.com 44, 24, 15, 8, 23, 7, 6, 5 17593Smax.romanov@nginx.com }; 17693Smax.romanov@nginx.com 17793Smax.romanov@nginx.com static const uint64_t nxt_lg2_magic = 0x07EDD5E59A4E28C2ULL; 17893Smax.romanov@nginx.com 17993Smax.romanov@nginx.com static int 18093Smax.romanov@nginx.com nxt_lg2(uint64_t v) 18193Smax.romanov@nginx.com { 18293Smax.romanov@nginx.com v |= v >> 1; 18393Smax.romanov@nginx.com v |= v >> 2; 18493Smax.romanov@nginx.com v |= v >> 4; 18593Smax.romanov@nginx.com v |= v >> 8; 18693Smax.romanov@nginx.com v |= v >> 16; 18793Smax.romanov@nginx.com v |= v >> 32; 18893Smax.romanov@nginx.com return nxt_lg2_tab64[ ((v - (v >> 1)) * nxt_lg2_magic) >> 58 ]; 18993Smax.romanov@nginx.com } 19093Smax.romanov@nginx.com 19193Smax.romanov@nginx.com #endif 19293Smax.romanov@nginx.com 19393Smax.romanov@nginx.com 194128Smax.romanov@nginx.com #if (NXT_DEBUG) 195128Smax.romanov@nginx.com 196128Smax.romanov@nginx.com nxt_inline void 197128Smax.romanov@nginx.com nxt_mp_thread_assert(nxt_mp_t *mp) 198128Smax.romanov@nginx.com { 199128Smax.romanov@nginx.com nxt_tid_t tid; 200128Smax.romanov@nginx.com nxt_thread_t *thread; 201128Smax.romanov@nginx.com 202128Smax.romanov@nginx.com thread = nxt_thread(); 203128Smax.romanov@nginx.com tid = nxt_thread_tid(thread); 204128Smax.romanov@nginx.com 205128Smax.romanov@nginx.com if (nxt_fast_path(mp->tid == tid)) { 206128Smax.romanov@nginx.com return; 207128Smax.romanov@nginx.com } 208128Smax.romanov@nginx.com 209128Smax.romanov@nginx.com if (nxt_slow_path(nxt_pid != mp->pid)) { 210128Smax.romanov@nginx.com mp->pid = nxt_pid; 211128Smax.romanov@nginx.com mp->tid = tid; 212128Smax.romanov@nginx.com 213128Smax.romanov@nginx.com return; 214128Smax.romanov@nginx.com } 215128Smax.romanov@nginx.com 216128Smax.romanov@nginx.com nxt_log_alert(thread->log, "mem_pool locked by thread %PT", mp->tid); 217128Smax.romanov@nginx.com nxt_abort(); 218128Smax.romanov@nginx.com } 219128Smax.romanov@nginx.com 220128Smax.romanov@nginx.com #else 221128Smax.romanov@nginx.com 222128Smax.romanov@nginx.com #define nxt_mp_thread_assert(mp) 223128Smax.romanov@nginx.com 224128Smax.romanov@nginx.com #endif 225128Smax.romanov@nginx.com 226128Smax.romanov@nginx.com 227128Smax.romanov@nginx.com void 228128Smax.romanov@nginx.com nxt_mp_thread_adopt(nxt_mp_t *mp) 229128Smax.romanov@nginx.com { 230128Smax.romanov@nginx.com #if (NXT_DEBUG) 231128Smax.romanov@nginx.com mp->pid = nxt_pid; 232128Smax.romanov@nginx.com mp->tid = nxt_thread_tid(NULL); 233128Smax.romanov@nginx.com #endif 234128Smax.romanov@nginx.com } 235128Smax.romanov@nginx.com 236128Smax.romanov@nginx.com 23763Sigor@sysoev.ru nxt_mp_t * 23863Sigor@sysoev.ru nxt_mp_create(size_t cluster_size, size_t page_alignment, size_t page_size, 23963Sigor@sysoev.ru size_t min_chunk_size) 24063Sigor@sysoev.ru { 24163Sigor@sysoev.ru nxt_mp_t *mp; 24269Sigor@sysoev.ru uint32_t pages, chunk_size_shift, page_size_shift; 24363Sigor@sysoev.ru nxt_queue_t *chunk_pages; 24463Sigor@sysoev.ru 24569Sigor@sysoev.ru chunk_size_shift = nxt_lg2(min_chunk_size); 24669Sigor@sysoev.ru page_size_shift = nxt_lg2(page_size); 24763Sigor@sysoev.ru 24869Sigor@sysoev.ru pages = page_size_shift - chunk_size_shift; 24963Sigor@sysoev.ru 25063Sigor@sysoev.ru mp = nxt_zalloc(sizeof(nxt_mp_t) + pages * sizeof(nxt_queue_t)); 25163Sigor@sysoev.ru 25263Sigor@sysoev.ru if (nxt_fast_path(mp != NULL)) { 25363Sigor@sysoev.ru mp->retain = 1; 25469Sigor@sysoev.ru mp->chunk_size_shift = chunk_size_shift; 25569Sigor@sysoev.ru mp->page_size_shift = page_size_shift; 25663Sigor@sysoev.ru mp->page_size = page_size; 25763Sigor@sysoev.ru mp->page_alignment = nxt_max(page_alignment, NXT_MAX_ALIGNMENT); 25863Sigor@sysoev.ru mp->cluster_size = cluster_size; 25963Sigor@sysoev.ru 26063Sigor@sysoev.ru chunk_pages = mp->chunk_pages; 26163Sigor@sysoev.ru 26269Sigor@sysoev.ru while (pages != 0) { 26363Sigor@sysoev.ru nxt_queue_init(chunk_pages); 26463Sigor@sysoev.ru chunk_pages++; 26569Sigor@sysoev.ru pages--; 26672Sigor@sysoev.ru } 26763Sigor@sysoev.ru 26863Sigor@sysoev.ru nxt_queue_init(&mp->free_pages); 26964Sigor@sysoev.ru nxt_queue_init(&mp->nget_pages); 27064Sigor@sysoev.ru nxt_queue_init(&mp->get_pages); 27169Sigor@sysoev.ru 27269Sigor@sysoev.ru nxt_rbtree_init(&mp->blocks, nxt_mp_rbtree_compare); 27363Sigor@sysoev.ru } 27463Sigor@sysoev.ru 275145Smax.romanov@nginx.com nxt_debug_alloc("mp %p create(%uz, %uz, %uz, %uz)", mp, cluster_size, 276145Smax.romanov@nginx.com page_alignment, page_size, min_chunk_size); 277145Smax.romanov@nginx.com 27863Sigor@sysoev.ru return mp; 27963Sigor@sysoev.ru } 28063Sigor@sysoev.ru 28163Sigor@sysoev.ru 28263Sigor@sysoev.ru void 28363Sigor@sysoev.ru nxt_mp_destroy(nxt_mp_t *mp) 28463Sigor@sysoev.ru { 28563Sigor@sysoev.ru void *p; 28663Sigor@sysoev.ru nxt_mp_block_t *block; 28763Sigor@sysoev.ru nxt_rbtree_node_t *node, *next; 28863Sigor@sysoev.ru 289145Smax.romanov@nginx.com nxt_debug_alloc("mp %p destroy", mp); 29063Sigor@sysoev.ru 291131Smax.romanov@nginx.com nxt_mp_thread_assert(mp); 292131Smax.romanov@nginx.com 29363Sigor@sysoev.ru next = nxt_rbtree_root(&mp->blocks); 29463Sigor@sysoev.ru 29563Sigor@sysoev.ru while (next != nxt_rbtree_sentinel(&mp->blocks)) { 29663Sigor@sysoev.ru 29763Sigor@sysoev.ru node = nxt_rbtree_destroy_next(&mp->blocks, &next); 29863Sigor@sysoev.ru block = (nxt_mp_block_t *) node; 29963Sigor@sysoev.ru 30063Sigor@sysoev.ru p = block->start; 30163Sigor@sysoev.ru 30263Sigor@sysoev.ru if (block->type != NXT_MP_EMBEDDED_BLOCK) { 30363Sigor@sysoev.ru nxt_free(block); 30463Sigor@sysoev.ru } 30563Sigor@sysoev.ru 30663Sigor@sysoev.ru nxt_free(p); 30763Sigor@sysoev.ru } 30863Sigor@sysoev.ru 30963Sigor@sysoev.ru nxt_free(mp); 31063Sigor@sysoev.ru } 31163Sigor@sysoev.ru 31263Sigor@sysoev.ru 31363Sigor@sysoev.ru nxt_bool_t 31463Sigor@sysoev.ru nxt_mp_test_sizes(size_t cluster_size, size_t page_alignment, size_t page_size, 31563Sigor@sysoev.ru size_t min_chunk_size) 31663Sigor@sysoev.ru { 31763Sigor@sysoev.ru nxt_bool_t valid; 31863Sigor@sysoev.ru 31963Sigor@sysoev.ru /* Alignment and sizes must be a power of 2. */ 32063Sigor@sysoev.ru 32163Sigor@sysoev.ru valid = nxt_expect(1, (nxt_is_power_of_two(page_alignment) 32263Sigor@sysoev.ru && nxt_is_power_of_two(page_size) 32363Sigor@sysoev.ru && nxt_is_power_of_two(min_chunk_size))); 32463Sigor@sysoev.ru if (!valid) { 32563Sigor@sysoev.ru return 0; 32663Sigor@sysoev.ru } 32763Sigor@sysoev.ru 32863Sigor@sysoev.ru page_alignment = nxt_max(page_alignment, NXT_MAX_ALIGNMENT); 32963Sigor@sysoev.ru 33063Sigor@sysoev.ru valid = nxt_expect(1, (page_size >= 64 33163Sigor@sysoev.ru && page_size >= page_alignment 33263Sigor@sysoev.ru && page_size >= min_chunk_size 33363Sigor@sysoev.ru && min_chunk_size * 32 >= page_size 33463Sigor@sysoev.ru && cluster_size >= page_size 33563Sigor@sysoev.ru && cluster_size / page_size <= 256 33663Sigor@sysoev.ru && cluster_size % page_size == 0)); 33763Sigor@sysoev.ru if (!valid) { 33863Sigor@sysoev.ru return 0; 33963Sigor@sysoev.ru } 34063Sigor@sysoev.ru 34163Sigor@sysoev.ru return 1; 34263Sigor@sysoev.ru } 34363Sigor@sysoev.ru 34463Sigor@sysoev.ru 34563Sigor@sysoev.ru nxt_bool_t 34663Sigor@sysoev.ru nxt_mp_is_empty(nxt_mp_t *mp) 34763Sigor@sysoev.ru { 34863Sigor@sysoev.ru return (nxt_rbtree_is_empty(&mp->blocks) 34963Sigor@sysoev.ru && nxt_queue_is_empty(&mp->free_pages)); 35063Sigor@sysoev.ru } 35163Sigor@sysoev.ru 35263Sigor@sysoev.ru 35363Sigor@sysoev.ru void * 35463Sigor@sysoev.ru nxt_mp_alloc(nxt_mp_t *mp, size_t size) 35563Sigor@sysoev.ru { 356145Smax.romanov@nginx.com void *p; 35763Sigor@sysoev.ru 35863Sigor@sysoev.ru #if !(NXT_DEBUG_MEMORY) 35963Sigor@sysoev.ru 36063Sigor@sysoev.ru if (size <= mp->page_size) { 361145Smax.romanov@nginx.com p = nxt_mp_alloc_small(mp, size); 362145Smax.romanov@nginx.com 363145Smax.romanov@nginx.com } else { 364*147Svbart@nginx.com p = nxt_mp_alloc_large(mp, NXT_MAX_ALIGNMENT, size); 365*147Svbart@nginx.com } 366145Smax.romanov@nginx.com 367*147Svbart@nginx.com #else 368145Smax.romanov@nginx.com 369145Smax.romanov@nginx.com p = nxt_mp_alloc_large(mp, NXT_MAX_ALIGNMENT, size); 370145Smax.romanov@nginx.com 37163Sigor@sysoev.ru #endif 37263Sigor@sysoev.ru 373145Smax.romanov@nginx.com nxt_debug_alloc("mp %p alloc(%uz): %p", mp, size, p); 374145Smax.romanov@nginx.com 375145Smax.romanov@nginx.com return p; 37663Sigor@sysoev.ru } 37763Sigor@sysoev.ru 37863Sigor@sysoev.ru 37963Sigor@sysoev.ru void * 38063Sigor@sysoev.ru nxt_mp_zalloc(nxt_mp_t *mp, size_t size) 38163Sigor@sysoev.ru { 38263Sigor@sysoev.ru void *p; 38363Sigor@sysoev.ru 38463Sigor@sysoev.ru p = nxt_mp_alloc(mp, size); 38563Sigor@sysoev.ru 38663Sigor@sysoev.ru if (nxt_fast_path(p != NULL)) { 38763Sigor@sysoev.ru memset(p, 0, size); 38863Sigor@sysoev.ru } 38963Sigor@sysoev.ru 39063Sigor@sysoev.ru return p; 39163Sigor@sysoev.ru } 39263Sigor@sysoev.ru 39363Sigor@sysoev.ru 39463Sigor@sysoev.ru void * 39563Sigor@sysoev.ru nxt_mp_align(nxt_mp_t *mp, size_t alignment, size_t size) 39663Sigor@sysoev.ru { 397145Smax.romanov@nginx.com void *p; 39863Sigor@sysoev.ru 39963Sigor@sysoev.ru /* Alignment must be a power of 2. */ 40063Sigor@sysoev.ru 40163Sigor@sysoev.ru if (nxt_fast_path(nxt_is_power_of_two(alignment))) { 40263Sigor@sysoev.ru 40363Sigor@sysoev.ru #if !(NXT_DEBUG_MEMORY) 40463Sigor@sysoev.ru 405*147Svbart@nginx.com size_t aligned_size; 406*147Svbart@nginx.com 407145Smax.romanov@nginx.com aligned_size = nxt_max(size, alignment); 408145Smax.romanov@nginx.com 409145Smax.romanov@nginx.com if (aligned_size <= mp->page_size && alignment <= mp->page_alignment) { 410145Smax.romanov@nginx.com p = nxt_mp_alloc_small(mp, aligned_size); 41163Sigor@sysoev.ru 412145Smax.romanov@nginx.com } else { 413*147Svbart@nginx.com p = nxt_mp_alloc_large(mp, alignment, size); 414*147Svbart@nginx.com } 415145Smax.romanov@nginx.com 416*147Svbart@nginx.com #else 417145Smax.romanov@nginx.com 418145Smax.romanov@nginx.com p = nxt_mp_alloc_large(mp, alignment, size); 419145Smax.romanov@nginx.com 42063Sigor@sysoev.ru #endif 42163Sigor@sysoev.ru 422145Smax.romanov@nginx.com } else { 423145Smax.romanov@nginx.com p = NULL; 42463Sigor@sysoev.ru } 42563Sigor@sysoev.ru 426145Smax.romanov@nginx.com nxt_debug_alloc("mp %p align(@%uz:%uz): %p", mp, alignment, size, p); 427145Smax.romanov@nginx.com 428145Smax.romanov@nginx.com return p; 42963Sigor@sysoev.ru } 43063Sigor@sysoev.ru 43163Sigor@sysoev.ru 43263Sigor@sysoev.ru void * 43363Sigor@sysoev.ru nxt_mp_zalign(nxt_mp_t *mp, size_t alignment, size_t size) 43463Sigor@sysoev.ru { 43563Sigor@sysoev.ru void *p; 43663Sigor@sysoev.ru 43763Sigor@sysoev.ru p = nxt_mp_align(mp, alignment, size); 43863Sigor@sysoev.ru 43963Sigor@sysoev.ru if (nxt_fast_path(p != NULL)) { 44063Sigor@sysoev.ru memset(p, 0, size); 44163Sigor@sysoev.ru } 44263Sigor@sysoev.ru 44363Sigor@sysoev.ru return p; 44463Sigor@sysoev.ru } 44563Sigor@sysoev.ru 44663Sigor@sysoev.ru 44763Sigor@sysoev.ru nxt_inline nxt_uint_t 44863Sigor@sysoev.ru nxt_mp_chunk_pages_index(nxt_mp_t *mp, size_t size) 44963Sigor@sysoev.ru { 45063Sigor@sysoev.ru nxt_int_t n, index; 45163Sigor@sysoev.ru 45263Sigor@sysoev.ru index = 0; 45363Sigor@sysoev.ru 45463Sigor@sysoev.ru if (size > 1) { 45563Sigor@sysoev.ru n = nxt_lg2(size - 1) + 1 - mp->chunk_size_shift; 45663Sigor@sysoev.ru 45763Sigor@sysoev.ru if (n > 0) { 45863Sigor@sysoev.ru index = n; 45963Sigor@sysoev.ru } 46063Sigor@sysoev.ru } 46163Sigor@sysoev.ru 46263Sigor@sysoev.ru return index; 46363Sigor@sysoev.ru } 46463Sigor@sysoev.ru 46563Sigor@sysoev.ru 46668Sigor@sysoev.ru #if !(NXT_DEBUG_MEMORY) 46768Sigor@sysoev.ru 46868Sigor@sysoev.ru nxt_inline u_char * 46968Sigor@sysoev.ru nxt_mp_page_addr(nxt_mp_t *mp, nxt_mp_page_t *page) 47068Sigor@sysoev.ru { 47168Sigor@sysoev.ru size_t page_offset; 47268Sigor@sysoev.ru nxt_mp_block_t *block; 47368Sigor@sysoev.ru 47468Sigor@sysoev.ru page_offset = page->number * sizeof(nxt_mp_page_t) 47568Sigor@sysoev.ru + offsetof(nxt_mp_block_t, pages); 47668Sigor@sysoev.ru 47768Sigor@sysoev.ru block = (nxt_mp_block_t *) ((u_char *) page - page_offset); 47868Sigor@sysoev.ru 47968Sigor@sysoev.ru return block->start + (page->number << mp->page_size_shift); 48068Sigor@sysoev.ru } 48168Sigor@sysoev.ru 48268Sigor@sysoev.ru 48363Sigor@sysoev.ru static void * 48463Sigor@sysoev.ru nxt_mp_alloc_small(nxt_mp_t *mp, size_t size) 48563Sigor@sysoev.ru { 48663Sigor@sysoev.ru u_char *p; 48763Sigor@sysoev.ru nxt_uint_t n, index; 48863Sigor@sysoev.ru nxt_queue_t *chunk_pages; 48963Sigor@sysoev.ru nxt_mp_page_t *page; 49063Sigor@sysoev.ru nxt_queue_link_t *link; 49163Sigor@sysoev.ru 492128Smax.romanov@nginx.com nxt_mp_thread_assert(mp); 493128Smax.romanov@nginx.com 49463Sigor@sysoev.ru p = NULL; 49563Sigor@sysoev.ru 49663Sigor@sysoev.ru if (size <= mp->page_size / 2) { 49763Sigor@sysoev.ru 49863Sigor@sysoev.ru index = nxt_mp_chunk_pages_index(mp, size); 49963Sigor@sysoev.ru chunk_pages = &mp->chunk_pages[index]; 50063Sigor@sysoev.ru 50163Sigor@sysoev.ru if (nxt_fast_path(!nxt_queue_is_empty(chunk_pages))) { 50263Sigor@sysoev.ru 50363Sigor@sysoev.ru link = nxt_queue_first(chunk_pages); 50463Sigor@sysoev.ru page = nxt_queue_link_data(link, nxt_mp_page_t, link); 50563Sigor@sysoev.ru 50663Sigor@sysoev.ru p = nxt_mp_page_addr(mp, page); 50763Sigor@sysoev.ru 50863Sigor@sysoev.ru n = nxt_mp_chunk_get_free(page->u.map); 50963Sigor@sysoev.ru nxt_mp_chunk_set_busy(page->u.map, n); 51063Sigor@sysoev.ru 51163Sigor@sysoev.ru p += ((n << index) << mp->chunk_size_shift); 51263Sigor@sysoev.ru 51363Sigor@sysoev.ru page->chunks--; 51463Sigor@sysoev.ru 51563Sigor@sysoev.ru if (page->chunks == 0) { 51663Sigor@sysoev.ru /* 51763Sigor@sysoev.ru * Remove full page from the pool chunk pages list 51863Sigor@sysoev.ru * of pages with free chunks. 51963Sigor@sysoev.ru */ 52063Sigor@sysoev.ru nxt_queue_remove(&page->link); 52163Sigor@sysoev.ru } 52263Sigor@sysoev.ru 52363Sigor@sysoev.ru } else { 52463Sigor@sysoev.ru page = nxt_mp_alloc_page(mp); 52563Sigor@sysoev.ru 52663Sigor@sysoev.ru if (nxt_fast_path(page != NULL)) { 52763Sigor@sysoev.ru page->size = (1 << index); 52863Sigor@sysoev.ru 52963Sigor@sysoev.ru n = mp->page_size_shift - (index + mp->chunk_size_shift); 53063Sigor@sysoev.ru page->chunks = (1 << n) - 1; 53163Sigor@sysoev.ru 53263Sigor@sysoev.ru nxt_queue_insert_head(chunk_pages, &page->link); 53363Sigor@sysoev.ru 53463Sigor@sysoev.ru /* Mark the first chunk as busy. */ 53563Sigor@sysoev.ru page->u.map = 0xFFFFFFFE; 53663Sigor@sysoev.ru 53763Sigor@sysoev.ru p = nxt_mp_page_addr(mp, page); 53863Sigor@sysoev.ru } 53963Sigor@sysoev.ru } 54063Sigor@sysoev.ru 54163Sigor@sysoev.ru } else { 54263Sigor@sysoev.ru page = nxt_mp_alloc_page(mp); 54363Sigor@sysoev.ru 54463Sigor@sysoev.ru if (nxt_fast_path(page != NULL)) { 54563Sigor@sysoev.ru page->size = mp->page_size >> mp->chunk_size_shift; 54663Sigor@sysoev.ru 54763Sigor@sysoev.ru p = nxt_mp_page_addr(mp, page); 54863Sigor@sysoev.ru } 54963Sigor@sysoev.ru } 55063Sigor@sysoev.ru 551145Smax.romanov@nginx.com nxt_debug_alloc("mp %p chunk:%uz alloc: %p", mp, 55263Sigor@sysoev.ru page->size << mp->chunk_size_shift, p); 55363Sigor@sysoev.ru 55463Sigor@sysoev.ru return p; 55563Sigor@sysoev.ru } 55663Sigor@sysoev.ru 55763Sigor@sysoev.ru 55868Sigor@sysoev.ru static void * 55968Sigor@sysoev.ru nxt_mp_get_small(nxt_mp_t *mp, nxt_queue_t *pages, size_t size) 56068Sigor@sysoev.ru { 56168Sigor@sysoev.ru u_char *p; 56268Sigor@sysoev.ru uint32_t available; 56368Sigor@sysoev.ru nxt_mp_page_t *page; 56468Sigor@sysoev.ru nxt_queue_link_t *link, *next; 56568Sigor@sysoev.ru 566128Smax.romanov@nginx.com nxt_mp_thread_assert(mp); 567128Smax.romanov@nginx.com 56868Sigor@sysoev.ru for (link = nxt_queue_first(pages); 56968Sigor@sysoev.ru link != nxt_queue_tail(pages); 57068Sigor@sysoev.ru link = next) 57168Sigor@sysoev.ru { 57268Sigor@sysoev.ru next = nxt_queue_next(link); 57368Sigor@sysoev.ru page = nxt_queue_link_data(link, nxt_mp_page_t, link); 57468Sigor@sysoev.ru 57568Sigor@sysoev.ru available = mp->page_size - page->u.taken; 57668Sigor@sysoev.ru 57768Sigor@sysoev.ru if (size <= available) { 57868Sigor@sysoev.ru goto found; 57968Sigor@sysoev.ru } 58068Sigor@sysoev.ru 58168Sigor@sysoev.ru if (available == 0 || page->fails++ > 100) { 58268Sigor@sysoev.ru nxt_queue_remove(link); 58368Sigor@sysoev.ru } 58468Sigor@sysoev.ru } 58568Sigor@sysoev.ru 58668Sigor@sysoev.ru page = nxt_mp_alloc_page(mp); 58768Sigor@sysoev.ru 58868Sigor@sysoev.ru if (nxt_slow_path(page == NULL)) { 58968Sigor@sysoev.ru return page; 59068Sigor@sysoev.ru } 59168Sigor@sysoev.ru 59268Sigor@sysoev.ru nxt_queue_insert_head(pages, &page->link); 59368Sigor@sysoev.ru 59468Sigor@sysoev.ru page->size = 0xFF; 595129Smax.romanov@nginx.com page->u.taken = 0; 59668Sigor@sysoev.ru 59768Sigor@sysoev.ru found: 59868Sigor@sysoev.ru 59968Sigor@sysoev.ru p = nxt_mp_page_addr(mp, page); 60068Sigor@sysoev.ru 60168Sigor@sysoev.ru p += page->u.taken; 60268Sigor@sysoev.ru page->u.taken += size; 60368Sigor@sysoev.ru 60468Sigor@sysoev.ru return p; 60568Sigor@sysoev.ru } 60668Sigor@sysoev.ru 60768Sigor@sysoev.ru 60863Sigor@sysoev.ru static nxt_mp_page_t * 60963Sigor@sysoev.ru nxt_mp_alloc_page(nxt_mp_t *mp) 61063Sigor@sysoev.ru { 61163Sigor@sysoev.ru nxt_mp_page_t *page; 61263Sigor@sysoev.ru nxt_mp_block_t *cluster; 61363Sigor@sysoev.ru nxt_queue_link_t *link; 61463Sigor@sysoev.ru 61563Sigor@sysoev.ru if (nxt_queue_is_empty(&mp->free_pages)) { 61663Sigor@sysoev.ru cluster = nxt_mp_alloc_cluster(mp); 61763Sigor@sysoev.ru if (nxt_slow_path(cluster == NULL)) { 61863Sigor@sysoev.ru return NULL; 61963Sigor@sysoev.ru } 62063Sigor@sysoev.ru } 62163Sigor@sysoev.ru 62263Sigor@sysoev.ru link = nxt_queue_first(&mp->free_pages); 62363Sigor@sysoev.ru nxt_queue_remove(link); 62463Sigor@sysoev.ru 62563Sigor@sysoev.ru page = nxt_queue_link_data(link, nxt_mp_page_t, link); 62663Sigor@sysoev.ru 62763Sigor@sysoev.ru return page; 62863Sigor@sysoev.ru } 62963Sigor@sysoev.ru 63063Sigor@sysoev.ru 63163Sigor@sysoev.ru static nxt_mp_block_t * 63263Sigor@sysoev.ru nxt_mp_alloc_cluster(nxt_mp_t *mp) 63363Sigor@sysoev.ru { 63463Sigor@sysoev.ru nxt_uint_t n; 63563Sigor@sysoev.ru nxt_mp_block_t *cluster; 63663Sigor@sysoev.ru 63763Sigor@sysoev.ru n = mp->cluster_size >> mp->page_size_shift; 63863Sigor@sysoev.ru 63963Sigor@sysoev.ru cluster = nxt_zalloc(sizeof(nxt_mp_block_t) + n * sizeof(nxt_mp_page_t)); 64063Sigor@sysoev.ru 64163Sigor@sysoev.ru if (nxt_slow_path(cluster == NULL)) { 64263Sigor@sysoev.ru return NULL; 64363Sigor@sysoev.ru } 64463Sigor@sysoev.ru 64563Sigor@sysoev.ru /* NXT_MP_CLUSTER_BLOCK type is zero. */ 64663Sigor@sysoev.ru 64763Sigor@sysoev.ru cluster->size = mp->cluster_size; 64863Sigor@sysoev.ru 64963Sigor@sysoev.ru cluster->start = nxt_memalign(mp->page_alignment, mp->cluster_size); 65063Sigor@sysoev.ru if (nxt_slow_path(cluster->start == NULL)) { 65163Sigor@sysoev.ru nxt_free(cluster); 65263Sigor@sysoev.ru return NULL; 65363Sigor@sysoev.ru } 65463Sigor@sysoev.ru 65563Sigor@sysoev.ru n--; 65663Sigor@sysoev.ru cluster->pages[n].number = n; 65763Sigor@sysoev.ru nxt_queue_insert_head(&mp->free_pages, &cluster->pages[n].link); 65863Sigor@sysoev.ru 65963Sigor@sysoev.ru while (n != 0) { 66063Sigor@sysoev.ru n--; 66163Sigor@sysoev.ru cluster->pages[n].number = n; 66263Sigor@sysoev.ru nxt_queue_insert_before(&cluster->pages[n + 1].link, 66363Sigor@sysoev.ru &cluster->pages[n].link); 66463Sigor@sysoev.ru } 66563Sigor@sysoev.ru 66663Sigor@sysoev.ru nxt_rbtree_insert(&mp->blocks, &cluster->node); 66763Sigor@sysoev.ru 66863Sigor@sysoev.ru return cluster; 66963Sigor@sysoev.ru } 67063Sigor@sysoev.ru 67163Sigor@sysoev.ru #endif 67263Sigor@sysoev.ru 67363Sigor@sysoev.ru 67463Sigor@sysoev.ru static void * 67563Sigor@sysoev.ru nxt_mp_alloc_large(nxt_mp_t *mp, size_t alignment, size_t size) 67663Sigor@sysoev.ru { 67763Sigor@sysoev.ru u_char *p; 67863Sigor@sysoev.ru size_t aligned_size; 67963Sigor@sysoev.ru uint8_t type; 68063Sigor@sysoev.ru nxt_mp_block_t *block; 68163Sigor@sysoev.ru 682128Smax.romanov@nginx.com nxt_mp_thread_assert(mp); 683128Smax.romanov@nginx.com 68463Sigor@sysoev.ru /* Allocation must be less than 4G. */ 68563Sigor@sysoev.ru if (nxt_slow_path(size >= 0xFFFFFFFF)) { 68663Sigor@sysoev.ru return NULL; 68763Sigor@sysoev.ru } 68863Sigor@sysoev.ru 68963Sigor@sysoev.ru if (nxt_is_power_of_two(size)) { 69063Sigor@sysoev.ru block = nxt_malloc(sizeof(nxt_mp_block_t)); 69163Sigor@sysoev.ru if (nxt_slow_path(block == NULL)) { 69263Sigor@sysoev.ru return NULL; 69363Sigor@sysoev.ru } 69463Sigor@sysoev.ru 69563Sigor@sysoev.ru p = nxt_memalign(alignment, size); 69663Sigor@sysoev.ru if (nxt_slow_path(p == NULL)) { 69763Sigor@sysoev.ru nxt_free(block); 69863Sigor@sysoev.ru return NULL; 69963Sigor@sysoev.ru } 70063Sigor@sysoev.ru 70163Sigor@sysoev.ru type = NXT_MP_DISCRETE_BLOCK; 70263Sigor@sysoev.ru 70363Sigor@sysoev.ru } else { 70463Sigor@sysoev.ru aligned_size = nxt_align_size(size, sizeof(uintptr_t)); 70563Sigor@sysoev.ru 70663Sigor@sysoev.ru p = nxt_memalign(alignment, aligned_size + sizeof(nxt_mp_block_t)); 70763Sigor@sysoev.ru if (nxt_slow_path(p == NULL)) { 70863Sigor@sysoev.ru return NULL; 70963Sigor@sysoev.ru } 71063Sigor@sysoev.ru 71163Sigor@sysoev.ru block = (nxt_mp_block_t *) (p + aligned_size); 71263Sigor@sysoev.ru type = NXT_MP_EMBEDDED_BLOCK; 71363Sigor@sysoev.ru } 71463Sigor@sysoev.ru 71563Sigor@sysoev.ru block->type = type; 71663Sigor@sysoev.ru block->size = size; 71763Sigor@sysoev.ru block->start = p; 71863Sigor@sysoev.ru 71963Sigor@sysoev.ru nxt_rbtree_insert(&mp->blocks, &block->node); 72063Sigor@sysoev.ru 72163Sigor@sysoev.ru return p; 72263Sigor@sysoev.ru } 72363Sigor@sysoev.ru 72463Sigor@sysoev.ru 72563Sigor@sysoev.ru static intptr_t 72663Sigor@sysoev.ru nxt_mp_rbtree_compare(nxt_rbtree_node_t *node1, nxt_rbtree_node_t *node2) 72763Sigor@sysoev.ru { 72863Sigor@sysoev.ru nxt_mp_block_t *block1, *block2; 72963Sigor@sysoev.ru 73063Sigor@sysoev.ru block1 = (nxt_mp_block_t *) node1; 73163Sigor@sysoev.ru block2 = (nxt_mp_block_t *) node2; 73263Sigor@sysoev.ru 73363Sigor@sysoev.ru return (uintptr_t) block1->start - (uintptr_t) block2->start; 73463Sigor@sysoev.ru } 73563Sigor@sysoev.ru 73663Sigor@sysoev.ru 73763Sigor@sysoev.ru void 73863Sigor@sysoev.ru nxt_mp_free(nxt_mp_t *mp, void *p) 73963Sigor@sysoev.ru { 74063Sigor@sysoev.ru const char *err; 74163Sigor@sysoev.ru nxt_thread_t *thread; 74263Sigor@sysoev.ru nxt_mp_block_t *block; 74363Sigor@sysoev.ru 744128Smax.romanov@nginx.com nxt_mp_thread_assert(mp); 745128Smax.romanov@nginx.com 746145Smax.romanov@nginx.com nxt_debug_alloc("mp %p free(%p)", mp, p); 74763Sigor@sysoev.ru 74863Sigor@sysoev.ru block = nxt_mp_find_block(&mp->blocks, p); 74963Sigor@sysoev.ru 75063Sigor@sysoev.ru if (nxt_fast_path(block != NULL)) { 75163Sigor@sysoev.ru 75263Sigor@sysoev.ru if (block->type == NXT_MP_CLUSTER_BLOCK) { 75363Sigor@sysoev.ru err = nxt_mp_chunk_free(mp, block, p); 75463Sigor@sysoev.ru 75563Sigor@sysoev.ru if (nxt_fast_path(err == NULL)) { 75663Sigor@sysoev.ru return; 75763Sigor@sysoev.ru } 75863Sigor@sysoev.ru 75963Sigor@sysoev.ru } else if (nxt_fast_path(p == block->start)) { 76063Sigor@sysoev.ru nxt_rbtree_delete(&mp->blocks, &block->node); 76163Sigor@sysoev.ru 76263Sigor@sysoev.ru if (block->type == NXT_MP_DISCRETE_BLOCK) { 76363Sigor@sysoev.ru nxt_free(block); 76463Sigor@sysoev.ru } 76563Sigor@sysoev.ru 76663Sigor@sysoev.ru nxt_free(p); 76763Sigor@sysoev.ru 76863Sigor@sysoev.ru return; 76963Sigor@sysoev.ru 77063Sigor@sysoev.ru } else { 77163Sigor@sysoev.ru err = "freed pointer points to middle of block: %p"; 77263Sigor@sysoev.ru } 77363Sigor@sysoev.ru 77463Sigor@sysoev.ru } else { 77563Sigor@sysoev.ru err = "freed pointer is out of pool: %p"; 77663Sigor@sysoev.ru } 77763Sigor@sysoev.ru 77863Sigor@sysoev.ru thread = nxt_thread(); 77963Sigor@sysoev.ru 78063Sigor@sysoev.ru nxt_log(thread->task, NXT_LOG_CRIT, err, p); 78163Sigor@sysoev.ru } 78263Sigor@sysoev.ru 78363Sigor@sysoev.ru 78463Sigor@sysoev.ru static nxt_mp_block_t * 78563Sigor@sysoev.ru nxt_mp_find_block(nxt_rbtree_t *tree, u_char *p) 78663Sigor@sysoev.ru { 78763Sigor@sysoev.ru nxt_mp_block_t *block; 78863Sigor@sysoev.ru nxt_rbtree_node_t *node, *sentinel; 78963Sigor@sysoev.ru 79063Sigor@sysoev.ru node = nxt_rbtree_root(tree); 79163Sigor@sysoev.ru sentinel = nxt_rbtree_sentinel(tree); 79263Sigor@sysoev.ru 79363Sigor@sysoev.ru while (node != sentinel) { 79463Sigor@sysoev.ru 79563Sigor@sysoev.ru block = (nxt_mp_block_t *) node; 79663Sigor@sysoev.ru 79763Sigor@sysoev.ru if (p < block->start) { 79863Sigor@sysoev.ru node = node->left; 79963Sigor@sysoev.ru 80063Sigor@sysoev.ru } else if (p >= block->start + block->size) { 80163Sigor@sysoev.ru node = node->right; 80263Sigor@sysoev.ru 80363Sigor@sysoev.ru } else { 80463Sigor@sysoev.ru return block; 80563Sigor@sysoev.ru } 80663Sigor@sysoev.ru } 80763Sigor@sysoev.ru 80863Sigor@sysoev.ru return NULL; 80963Sigor@sysoev.ru } 81063Sigor@sysoev.ru 81163Sigor@sysoev.ru 81263Sigor@sysoev.ru static const char * 81363Sigor@sysoev.ru nxt_mp_chunk_free(nxt_mp_t *mp, nxt_mp_block_t *cluster, u_char *p) 81463Sigor@sysoev.ru { 81563Sigor@sysoev.ru u_char *start; 81663Sigor@sysoev.ru uintptr_t offset; 81763Sigor@sysoev.ru nxt_uint_t n, size, chunk; 81863Sigor@sysoev.ru nxt_queue_t *chunk_pages; 81963Sigor@sysoev.ru nxt_mp_page_t *page; 82063Sigor@sysoev.ru 82163Sigor@sysoev.ru n = (p - cluster->start) >> mp->page_size_shift; 82263Sigor@sysoev.ru start = cluster->start + (n << mp->page_size_shift); 82363Sigor@sysoev.ru 82463Sigor@sysoev.ru page = &cluster->pages[n]; 82563Sigor@sysoev.ru 82663Sigor@sysoev.ru if (nxt_slow_path(page->size == 0)) { 82763Sigor@sysoev.ru return "freed pointer points to already free page: %p"; 82863Sigor@sysoev.ru } 82963Sigor@sysoev.ru 83063Sigor@sysoev.ru if (nxt_slow_path(page->size == 0xFF)) { 83163Sigor@sysoev.ru return "freed pointer points to non-freeble page: %p"; 83263Sigor@sysoev.ru } 83363Sigor@sysoev.ru 83463Sigor@sysoev.ru size = page->size << mp->chunk_size_shift; 83563Sigor@sysoev.ru 83663Sigor@sysoev.ru if (size != mp->page_size) { 83763Sigor@sysoev.ru 83863Sigor@sysoev.ru offset = (uintptr_t) (p - start) & (mp->page_size - 1); 83963Sigor@sysoev.ru chunk = offset / size; 84063Sigor@sysoev.ru 84163Sigor@sysoev.ru if (nxt_slow_path(offset != chunk * size)) { 84263Sigor@sysoev.ru return "freed pointer points to wrong chunk: %p"; 84363Sigor@sysoev.ru } 84463Sigor@sysoev.ru 84563Sigor@sysoev.ru if (nxt_slow_path(nxt_mp_chunk_is_free(page->u.map, chunk))) { 84663Sigor@sysoev.ru return "freed pointer points to already free chunk: %p"; 84763Sigor@sysoev.ru } 84863Sigor@sysoev.ru 84963Sigor@sysoev.ru nxt_mp_chunk_set_free(page->u.map, chunk); 85063Sigor@sysoev.ru 85163Sigor@sysoev.ru if (page->u.map != 0xFFFFFFFF) { 85263Sigor@sysoev.ru page->chunks++; 85363Sigor@sysoev.ru 85463Sigor@sysoev.ru if (page->chunks == 1) { 85563Sigor@sysoev.ru /* 85663Sigor@sysoev.ru * Add the page to the head of pool chunk pages list 85763Sigor@sysoev.ru * of pages with free chunks. 85863Sigor@sysoev.ru */ 85963Sigor@sysoev.ru n = nxt_mp_chunk_pages_index(mp, size); 86063Sigor@sysoev.ru chunk_pages = &mp->chunk_pages[n]; 86163Sigor@sysoev.ru 86263Sigor@sysoev.ru nxt_queue_insert_head(chunk_pages, &page->link); 86363Sigor@sysoev.ru } 86463Sigor@sysoev.ru 86563Sigor@sysoev.ru nxt_mp_free_junk(p, size); 86663Sigor@sysoev.ru 86763Sigor@sysoev.ru return NULL; 86863Sigor@sysoev.ru 86963Sigor@sysoev.ru } else { 87063Sigor@sysoev.ru /* 87163Sigor@sysoev.ru * All chunks are free, remove the page from pool 87263Sigor@sysoev.ru * chunk pages list of pages with free chunks. 87363Sigor@sysoev.ru */ 87463Sigor@sysoev.ru nxt_queue_remove(&page->link); 87563Sigor@sysoev.ru } 87663Sigor@sysoev.ru 87763Sigor@sysoev.ru } else if (nxt_slow_path(p != start)) { 87863Sigor@sysoev.ru return "invalid pointer to chunk: %p"; 87963Sigor@sysoev.ru } 88063Sigor@sysoev.ru 88163Sigor@sysoev.ru /* Add the free page to the pool's free pages tree. */ 88263Sigor@sysoev.ru 88363Sigor@sysoev.ru page->size = 0; 88463Sigor@sysoev.ru nxt_queue_insert_head(&mp->free_pages, &page->link); 88563Sigor@sysoev.ru 88663Sigor@sysoev.ru nxt_mp_free_junk(p, size); 88763Sigor@sysoev.ru 88863Sigor@sysoev.ru /* Test if all pages in the cluster are free. */ 88963Sigor@sysoev.ru 89063Sigor@sysoev.ru n = mp->cluster_size >> mp->page_size_shift; 89163Sigor@sysoev.ru page = cluster->pages; 89263Sigor@sysoev.ru 89363Sigor@sysoev.ru do { 89463Sigor@sysoev.ru if (page->size != 0) { 89563Sigor@sysoev.ru return NULL; 89663Sigor@sysoev.ru } 89763Sigor@sysoev.ru 89863Sigor@sysoev.ru page++; 89963Sigor@sysoev.ru n--; 90063Sigor@sysoev.ru } while (n != 0); 90163Sigor@sysoev.ru 90263Sigor@sysoev.ru /* Free cluster. */ 90363Sigor@sysoev.ru 90463Sigor@sysoev.ru n = mp->cluster_size >> mp->page_size_shift; 90563Sigor@sysoev.ru page = cluster->pages; 90663Sigor@sysoev.ru 90763Sigor@sysoev.ru do { 90863Sigor@sysoev.ru nxt_queue_remove(&page->link); 90963Sigor@sysoev.ru page++; 91063Sigor@sysoev.ru n--; 91163Sigor@sysoev.ru } while (n != 0); 91263Sigor@sysoev.ru 91363Sigor@sysoev.ru nxt_rbtree_delete(&mp->blocks, &cluster->node); 91463Sigor@sysoev.ru 91563Sigor@sysoev.ru p = cluster->start; 91663Sigor@sysoev.ru 91763Sigor@sysoev.ru nxt_free(cluster); 91863Sigor@sysoev.ru nxt_free(p); 91963Sigor@sysoev.ru 92063Sigor@sysoev.ru return NULL; 92163Sigor@sysoev.ru } 92263Sigor@sysoev.ru 92363Sigor@sysoev.ru 92463Sigor@sysoev.ru void * 92563Sigor@sysoev.ru nxt_mp_retain(nxt_mp_t *mp, size_t size) 92663Sigor@sysoev.ru { 92763Sigor@sysoev.ru void *p; 92863Sigor@sysoev.ru 92963Sigor@sysoev.ru p = nxt_mp_alloc(mp, size); 93063Sigor@sysoev.ru 93163Sigor@sysoev.ru if (nxt_fast_path(p != NULL)) { 93263Sigor@sysoev.ru mp->retain++; 933145Smax.romanov@nginx.com nxt_debug_alloc("mp %p retain: %uD", mp, mp->retain); 93463Sigor@sysoev.ru } 93563Sigor@sysoev.ru 93663Sigor@sysoev.ru return p; 93763Sigor@sysoev.ru } 93863Sigor@sysoev.ru 93963Sigor@sysoev.ru 940141Smax.romanov@nginx.com uint32_t 94163Sigor@sysoev.ru nxt_mp_release(nxt_mp_t *mp, void *p) 94263Sigor@sysoev.ru { 94363Sigor@sysoev.ru nxt_mp_free(mp, p); 94463Sigor@sysoev.ru 94563Sigor@sysoev.ru mp->retain--; 94663Sigor@sysoev.ru 947145Smax.romanov@nginx.com nxt_debug_alloc("mp %p release: %uD", mp, mp->retain); 94863Sigor@sysoev.ru 94963Sigor@sysoev.ru if (mp->retain == 0) { 95063Sigor@sysoev.ru nxt_mp_destroy(mp); 951141Smax.romanov@nginx.com 952141Smax.romanov@nginx.com return 0; 95363Sigor@sysoev.ru } 954141Smax.romanov@nginx.com 955141Smax.romanov@nginx.com return mp->retain; 95663Sigor@sysoev.ru } 95763Sigor@sysoev.ru 95863Sigor@sysoev.ru 95963Sigor@sysoev.ru void * 96063Sigor@sysoev.ru nxt_mp_nget(nxt_mp_t *mp, size_t size) 96163Sigor@sysoev.ru { 962145Smax.romanov@nginx.com void *p; 96363Sigor@sysoev.ru 96463Sigor@sysoev.ru #if !(NXT_DEBUG_MEMORY) 96563Sigor@sysoev.ru 96663Sigor@sysoev.ru if (size <= mp->page_size) { 967145Smax.romanov@nginx.com p = nxt_mp_get_small(mp, &mp->nget_pages, size); 968145Smax.romanov@nginx.com 969145Smax.romanov@nginx.com } else { 970*147Svbart@nginx.com p = nxt_mp_alloc_large(mp, NXT_MAX_ALIGNMENT, size); 971*147Svbart@nginx.com } 972145Smax.romanov@nginx.com 973*147Svbart@nginx.com #else 974145Smax.romanov@nginx.com 975145Smax.romanov@nginx.com p = nxt_mp_alloc_large(mp, NXT_MAX_ALIGNMENT, size); 976145Smax.romanov@nginx.com 97763Sigor@sysoev.ru #endif 97863Sigor@sysoev.ru 979145Smax.romanov@nginx.com nxt_debug_alloc("mp %p nget(%uz): %p", mp, size, p); 980145Smax.romanov@nginx.com 981145Smax.romanov@nginx.com return p; 98263Sigor@sysoev.ru } 98363Sigor@sysoev.ru 98463Sigor@sysoev.ru 98563Sigor@sysoev.ru void * 98663Sigor@sysoev.ru nxt_mp_get(nxt_mp_t *mp, size_t size) 98763Sigor@sysoev.ru { 988145Smax.romanov@nginx.com void *p; 98963Sigor@sysoev.ru 99063Sigor@sysoev.ru #if !(NXT_DEBUG_MEMORY) 99163Sigor@sysoev.ru 99263Sigor@sysoev.ru if (size <= mp->page_size) { 99363Sigor@sysoev.ru size = nxt_max(size, NXT_MAX_ALIGNMENT); 994145Smax.romanov@nginx.com p = nxt_mp_get_small(mp, &mp->get_pages, size); 995145Smax.romanov@nginx.com 996145Smax.romanov@nginx.com } else { 997*147Svbart@nginx.com p = nxt_mp_alloc_large(mp, NXT_MAX_ALIGNMENT, size); 998*147Svbart@nginx.com } 999145Smax.romanov@nginx.com 1000*147Svbart@nginx.com #else 1001145Smax.romanov@nginx.com 1002145Smax.romanov@nginx.com p = nxt_mp_alloc_large(mp, NXT_MAX_ALIGNMENT, size); 1003145Smax.romanov@nginx.com 100463Sigor@sysoev.ru #endif 100563Sigor@sysoev.ru 1006145Smax.romanov@nginx.com nxt_debug_alloc("mp %p get(%uz): %p", mp, size, p); 1007145Smax.romanov@nginx.com 1008145Smax.romanov@nginx.com return p; 100963Sigor@sysoev.ru } 101063Sigor@sysoev.ru 101163Sigor@sysoev.ru 101263Sigor@sysoev.ru void * 101363Sigor@sysoev.ru nxt_mp_zget(nxt_mp_t *mp, size_t size) 101463Sigor@sysoev.ru { 101563Sigor@sysoev.ru void *p; 101663Sigor@sysoev.ru 101763Sigor@sysoev.ru p = nxt_mp_get(mp, size); 101863Sigor@sysoev.ru 101963Sigor@sysoev.ru if (nxt_fast_path(p != NULL)) { 102063Sigor@sysoev.ru memset(p, 0, size); 102163Sigor@sysoev.ru } 102263Sigor@sysoev.ru 102363Sigor@sysoev.ru return p; 102463Sigor@sysoev.ru } 1025