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 275*145Smax.romanov@nginx.com nxt_debug_alloc("mp %p create(%uz, %uz, %uz, %uz)", mp, cluster_size, 276*145Smax.romanov@nginx.com page_alignment, page_size, min_chunk_size); 277*145Smax.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 289*145Smax.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 { 356*145Smax.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) { 361*145Smax.romanov@nginx.com p = nxt_mp_alloc_small(mp, size); 362*145Smax.romanov@nginx.com 363*145Smax.romanov@nginx.com } else { 364*145Smax.romanov@nginx.com 365*145Smax.romanov@nginx.com #endif 366*145Smax.romanov@nginx.com 367*145Smax.romanov@nginx.com p = nxt_mp_alloc_large(mp, NXT_MAX_ALIGNMENT, size); 368*145Smax.romanov@nginx.com 369*145Smax.romanov@nginx.com #if !(NXT_DEBUG_MEMORY) 370*145Smax.romanov@nginx.com 37163Sigor@sysoev.ru } 37263Sigor@sysoev.ru 37363Sigor@sysoev.ru #endif 37463Sigor@sysoev.ru 375*145Smax.romanov@nginx.com nxt_debug_alloc("mp %p alloc(%uz): %p", mp, size, p); 376*145Smax.romanov@nginx.com 377*145Smax.romanov@nginx.com return p; 37863Sigor@sysoev.ru } 37963Sigor@sysoev.ru 38063Sigor@sysoev.ru 38163Sigor@sysoev.ru void * 38263Sigor@sysoev.ru nxt_mp_zalloc(nxt_mp_t *mp, size_t size) 38363Sigor@sysoev.ru { 38463Sigor@sysoev.ru void *p; 38563Sigor@sysoev.ru 38663Sigor@sysoev.ru p = nxt_mp_alloc(mp, size); 38763Sigor@sysoev.ru 38863Sigor@sysoev.ru if (nxt_fast_path(p != NULL)) { 38963Sigor@sysoev.ru memset(p, 0, size); 39063Sigor@sysoev.ru } 39163Sigor@sysoev.ru 39263Sigor@sysoev.ru return p; 39363Sigor@sysoev.ru } 39463Sigor@sysoev.ru 39563Sigor@sysoev.ru 39663Sigor@sysoev.ru void * 39763Sigor@sysoev.ru nxt_mp_align(nxt_mp_t *mp, size_t alignment, size_t size) 39863Sigor@sysoev.ru { 399*145Smax.romanov@nginx.com void *p; 400*145Smax.romanov@nginx.com size_t aligned_size; 40163Sigor@sysoev.ru 40263Sigor@sysoev.ru /* Alignment must be a power of 2. */ 40363Sigor@sysoev.ru 40463Sigor@sysoev.ru if (nxt_fast_path(nxt_is_power_of_two(alignment))) { 40563Sigor@sysoev.ru 40663Sigor@sysoev.ru #if !(NXT_DEBUG_MEMORY) 40763Sigor@sysoev.ru 408*145Smax.romanov@nginx.com aligned_size = nxt_max(size, alignment); 409*145Smax.romanov@nginx.com 410*145Smax.romanov@nginx.com if (aligned_size <= mp->page_size && alignment <= mp->page_alignment) { 411*145Smax.romanov@nginx.com 412*145Smax.romanov@nginx.com p = nxt_mp_alloc_small(mp, aligned_size); 41363Sigor@sysoev.ru 414*145Smax.romanov@nginx.com } else { 415*145Smax.romanov@nginx.com 416*145Smax.romanov@nginx.com #endif 417*145Smax.romanov@nginx.com 418*145Smax.romanov@nginx.com p = nxt_mp_alloc_large(mp, alignment, size); 419*145Smax.romanov@nginx.com 420*145Smax.romanov@nginx.com #if !(NXT_DEBUG_MEMORY) 421*145Smax.romanov@nginx.com 42263Sigor@sysoev.ru } 42363Sigor@sysoev.ru 42463Sigor@sysoev.ru #endif 42563Sigor@sysoev.ru 426*145Smax.romanov@nginx.com } else { 427*145Smax.romanov@nginx.com p = NULL; 42863Sigor@sysoev.ru } 42963Sigor@sysoev.ru 430*145Smax.romanov@nginx.com nxt_debug_alloc("mp %p align(@%uz:%uz): %p", mp, alignment, size, p); 431*145Smax.romanov@nginx.com 432*145Smax.romanov@nginx.com return p; 43363Sigor@sysoev.ru } 43463Sigor@sysoev.ru 43563Sigor@sysoev.ru 43663Sigor@sysoev.ru void * 43763Sigor@sysoev.ru nxt_mp_zalign(nxt_mp_t *mp, size_t alignment, size_t size) 43863Sigor@sysoev.ru { 43963Sigor@sysoev.ru void *p; 44063Sigor@sysoev.ru 44163Sigor@sysoev.ru p = nxt_mp_align(mp, alignment, size); 44263Sigor@sysoev.ru 44363Sigor@sysoev.ru if (nxt_fast_path(p != NULL)) { 44463Sigor@sysoev.ru memset(p, 0, size); 44563Sigor@sysoev.ru } 44663Sigor@sysoev.ru 44763Sigor@sysoev.ru return p; 44863Sigor@sysoev.ru } 44963Sigor@sysoev.ru 45063Sigor@sysoev.ru 45163Sigor@sysoev.ru nxt_inline nxt_uint_t 45263Sigor@sysoev.ru nxt_mp_chunk_pages_index(nxt_mp_t *mp, size_t size) 45363Sigor@sysoev.ru { 45463Sigor@sysoev.ru nxt_int_t n, index; 45563Sigor@sysoev.ru 45663Sigor@sysoev.ru index = 0; 45763Sigor@sysoev.ru 45863Sigor@sysoev.ru if (size > 1) { 45963Sigor@sysoev.ru n = nxt_lg2(size - 1) + 1 - mp->chunk_size_shift; 46063Sigor@sysoev.ru 46163Sigor@sysoev.ru if (n > 0) { 46263Sigor@sysoev.ru index = n; 46363Sigor@sysoev.ru } 46463Sigor@sysoev.ru } 46563Sigor@sysoev.ru 46663Sigor@sysoev.ru return index; 46763Sigor@sysoev.ru } 46863Sigor@sysoev.ru 46963Sigor@sysoev.ru 47068Sigor@sysoev.ru #if !(NXT_DEBUG_MEMORY) 47168Sigor@sysoev.ru 47268Sigor@sysoev.ru nxt_inline u_char * 47368Sigor@sysoev.ru nxt_mp_page_addr(nxt_mp_t *mp, nxt_mp_page_t *page) 47468Sigor@sysoev.ru { 47568Sigor@sysoev.ru size_t page_offset; 47668Sigor@sysoev.ru nxt_mp_block_t *block; 47768Sigor@sysoev.ru 47868Sigor@sysoev.ru page_offset = page->number * sizeof(nxt_mp_page_t) 47968Sigor@sysoev.ru + offsetof(nxt_mp_block_t, pages); 48068Sigor@sysoev.ru 48168Sigor@sysoev.ru block = (nxt_mp_block_t *) ((u_char *) page - page_offset); 48268Sigor@sysoev.ru 48368Sigor@sysoev.ru return block->start + (page->number << mp->page_size_shift); 48468Sigor@sysoev.ru } 48568Sigor@sysoev.ru 48668Sigor@sysoev.ru 48763Sigor@sysoev.ru static void * 48863Sigor@sysoev.ru nxt_mp_alloc_small(nxt_mp_t *mp, size_t size) 48963Sigor@sysoev.ru { 49063Sigor@sysoev.ru u_char *p; 49163Sigor@sysoev.ru nxt_uint_t n, index; 49263Sigor@sysoev.ru nxt_queue_t *chunk_pages; 49363Sigor@sysoev.ru nxt_mp_page_t *page; 49463Sigor@sysoev.ru nxt_queue_link_t *link; 49563Sigor@sysoev.ru 496128Smax.romanov@nginx.com nxt_mp_thread_assert(mp); 497128Smax.romanov@nginx.com 49863Sigor@sysoev.ru p = NULL; 49963Sigor@sysoev.ru 50063Sigor@sysoev.ru if (size <= mp->page_size / 2) { 50163Sigor@sysoev.ru 50263Sigor@sysoev.ru index = nxt_mp_chunk_pages_index(mp, size); 50363Sigor@sysoev.ru chunk_pages = &mp->chunk_pages[index]; 50463Sigor@sysoev.ru 50563Sigor@sysoev.ru if (nxt_fast_path(!nxt_queue_is_empty(chunk_pages))) { 50663Sigor@sysoev.ru 50763Sigor@sysoev.ru link = nxt_queue_first(chunk_pages); 50863Sigor@sysoev.ru page = nxt_queue_link_data(link, nxt_mp_page_t, link); 50963Sigor@sysoev.ru 51063Sigor@sysoev.ru p = nxt_mp_page_addr(mp, page); 51163Sigor@sysoev.ru 51263Sigor@sysoev.ru n = nxt_mp_chunk_get_free(page->u.map); 51363Sigor@sysoev.ru nxt_mp_chunk_set_busy(page->u.map, n); 51463Sigor@sysoev.ru 51563Sigor@sysoev.ru p += ((n << index) << mp->chunk_size_shift); 51663Sigor@sysoev.ru 51763Sigor@sysoev.ru page->chunks--; 51863Sigor@sysoev.ru 51963Sigor@sysoev.ru if (page->chunks == 0) { 52063Sigor@sysoev.ru /* 52163Sigor@sysoev.ru * Remove full page from the pool chunk pages list 52263Sigor@sysoev.ru * of pages with free chunks. 52363Sigor@sysoev.ru */ 52463Sigor@sysoev.ru nxt_queue_remove(&page->link); 52563Sigor@sysoev.ru } 52663Sigor@sysoev.ru 52763Sigor@sysoev.ru } else { 52863Sigor@sysoev.ru page = nxt_mp_alloc_page(mp); 52963Sigor@sysoev.ru 53063Sigor@sysoev.ru if (nxt_fast_path(page != NULL)) { 53163Sigor@sysoev.ru page->size = (1 << index); 53263Sigor@sysoev.ru 53363Sigor@sysoev.ru n = mp->page_size_shift - (index + mp->chunk_size_shift); 53463Sigor@sysoev.ru page->chunks = (1 << n) - 1; 53563Sigor@sysoev.ru 53663Sigor@sysoev.ru nxt_queue_insert_head(chunk_pages, &page->link); 53763Sigor@sysoev.ru 53863Sigor@sysoev.ru /* Mark the first chunk as busy. */ 53963Sigor@sysoev.ru page->u.map = 0xFFFFFFFE; 54063Sigor@sysoev.ru 54163Sigor@sysoev.ru p = nxt_mp_page_addr(mp, page); 54263Sigor@sysoev.ru } 54363Sigor@sysoev.ru } 54463Sigor@sysoev.ru 54563Sigor@sysoev.ru } else { 54663Sigor@sysoev.ru page = nxt_mp_alloc_page(mp); 54763Sigor@sysoev.ru 54863Sigor@sysoev.ru if (nxt_fast_path(page != NULL)) { 54963Sigor@sysoev.ru page->size = mp->page_size >> mp->chunk_size_shift; 55063Sigor@sysoev.ru 55163Sigor@sysoev.ru p = nxt_mp_page_addr(mp, page); 55263Sigor@sysoev.ru } 55363Sigor@sysoev.ru } 55463Sigor@sysoev.ru 555*145Smax.romanov@nginx.com nxt_debug_alloc("mp %p chunk:%uz alloc: %p", mp, 55663Sigor@sysoev.ru page->size << mp->chunk_size_shift, p); 55763Sigor@sysoev.ru 55863Sigor@sysoev.ru return p; 55963Sigor@sysoev.ru } 56063Sigor@sysoev.ru 56163Sigor@sysoev.ru 56268Sigor@sysoev.ru static void * 56368Sigor@sysoev.ru nxt_mp_get_small(nxt_mp_t *mp, nxt_queue_t *pages, size_t size) 56468Sigor@sysoev.ru { 56568Sigor@sysoev.ru u_char *p; 56668Sigor@sysoev.ru uint32_t available; 56768Sigor@sysoev.ru nxt_mp_page_t *page; 56868Sigor@sysoev.ru nxt_queue_link_t *link, *next; 56968Sigor@sysoev.ru 570128Smax.romanov@nginx.com nxt_mp_thread_assert(mp); 571128Smax.romanov@nginx.com 57268Sigor@sysoev.ru for (link = nxt_queue_first(pages); 57368Sigor@sysoev.ru link != nxt_queue_tail(pages); 57468Sigor@sysoev.ru link = next) 57568Sigor@sysoev.ru { 57668Sigor@sysoev.ru next = nxt_queue_next(link); 57768Sigor@sysoev.ru page = nxt_queue_link_data(link, nxt_mp_page_t, link); 57868Sigor@sysoev.ru 57968Sigor@sysoev.ru available = mp->page_size - page->u.taken; 58068Sigor@sysoev.ru 58168Sigor@sysoev.ru if (size <= available) { 58268Sigor@sysoev.ru goto found; 58368Sigor@sysoev.ru } 58468Sigor@sysoev.ru 58568Sigor@sysoev.ru if (available == 0 || page->fails++ > 100) { 58668Sigor@sysoev.ru nxt_queue_remove(link); 58768Sigor@sysoev.ru } 58868Sigor@sysoev.ru } 58968Sigor@sysoev.ru 59068Sigor@sysoev.ru page = nxt_mp_alloc_page(mp); 59168Sigor@sysoev.ru 59268Sigor@sysoev.ru if (nxt_slow_path(page == NULL)) { 59368Sigor@sysoev.ru return page; 59468Sigor@sysoev.ru } 59568Sigor@sysoev.ru 59668Sigor@sysoev.ru nxt_queue_insert_head(pages, &page->link); 59768Sigor@sysoev.ru 59868Sigor@sysoev.ru page->size = 0xFF; 599129Smax.romanov@nginx.com page->u.taken = 0; 60068Sigor@sysoev.ru 60168Sigor@sysoev.ru found: 60268Sigor@sysoev.ru 60368Sigor@sysoev.ru p = nxt_mp_page_addr(mp, page); 60468Sigor@sysoev.ru 60568Sigor@sysoev.ru p += page->u.taken; 60668Sigor@sysoev.ru page->u.taken += size; 60768Sigor@sysoev.ru 60868Sigor@sysoev.ru return p; 60968Sigor@sysoev.ru } 61068Sigor@sysoev.ru 61168Sigor@sysoev.ru 61263Sigor@sysoev.ru static nxt_mp_page_t * 61363Sigor@sysoev.ru nxt_mp_alloc_page(nxt_mp_t *mp) 61463Sigor@sysoev.ru { 61563Sigor@sysoev.ru nxt_mp_page_t *page; 61663Sigor@sysoev.ru nxt_mp_block_t *cluster; 61763Sigor@sysoev.ru nxt_queue_link_t *link; 61863Sigor@sysoev.ru 61963Sigor@sysoev.ru if (nxt_queue_is_empty(&mp->free_pages)) { 62063Sigor@sysoev.ru cluster = nxt_mp_alloc_cluster(mp); 62163Sigor@sysoev.ru if (nxt_slow_path(cluster == NULL)) { 62263Sigor@sysoev.ru return NULL; 62363Sigor@sysoev.ru } 62463Sigor@sysoev.ru } 62563Sigor@sysoev.ru 62663Sigor@sysoev.ru link = nxt_queue_first(&mp->free_pages); 62763Sigor@sysoev.ru nxt_queue_remove(link); 62863Sigor@sysoev.ru 62963Sigor@sysoev.ru page = nxt_queue_link_data(link, nxt_mp_page_t, link); 63063Sigor@sysoev.ru 63163Sigor@sysoev.ru return page; 63263Sigor@sysoev.ru } 63363Sigor@sysoev.ru 63463Sigor@sysoev.ru 63563Sigor@sysoev.ru static nxt_mp_block_t * 63663Sigor@sysoev.ru nxt_mp_alloc_cluster(nxt_mp_t *mp) 63763Sigor@sysoev.ru { 63863Sigor@sysoev.ru nxt_uint_t n; 63963Sigor@sysoev.ru nxt_mp_block_t *cluster; 64063Sigor@sysoev.ru 64163Sigor@sysoev.ru n = mp->cluster_size >> mp->page_size_shift; 64263Sigor@sysoev.ru 64363Sigor@sysoev.ru cluster = nxt_zalloc(sizeof(nxt_mp_block_t) + n * sizeof(nxt_mp_page_t)); 64463Sigor@sysoev.ru 64563Sigor@sysoev.ru if (nxt_slow_path(cluster == NULL)) { 64663Sigor@sysoev.ru return NULL; 64763Sigor@sysoev.ru } 64863Sigor@sysoev.ru 64963Sigor@sysoev.ru /* NXT_MP_CLUSTER_BLOCK type is zero. */ 65063Sigor@sysoev.ru 65163Sigor@sysoev.ru cluster->size = mp->cluster_size; 65263Sigor@sysoev.ru 65363Sigor@sysoev.ru cluster->start = nxt_memalign(mp->page_alignment, mp->cluster_size); 65463Sigor@sysoev.ru if (nxt_slow_path(cluster->start == NULL)) { 65563Sigor@sysoev.ru nxt_free(cluster); 65663Sigor@sysoev.ru return NULL; 65763Sigor@sysoev.ru } 65863Sigor@sysoev.ru 65963Sigor@sysoev.ru n--; 66063Sigor@sysoev.ru cluster->pages[n].number = n; 66163Sigor@sysoev.ru nxt_queue_insert_head(&mp->free_pages, &cluster->pages[n].link); 66263Sigor@sysoev.ru 66363Sigor@sysoev.ru while (n != 0) { 66463Sigor@sysoev.ru n--; 66563Sigor@sysoev.ru cluster->pages[n].number = n; 66663Sigor@sysoev.ru nxt_queue_insert_before(&cluster->pages[n + 1].link, 66763Sigor@sysoev.ru &cluster->pages[n].link); 66863Sigor@sysoev.ru } 66963Sigor@sysoev.ru 67063Sigor@sysoev.ru nxt_rbtree_insert(&mp->blocks, &cluster->node); 67163Sigor@sysoev.ru 67263Sigor@sysoev.ru return cluster; 67363Sigor@sysoev.ru } 67463Sigor@sysoev.ru 67563Sigor@sysoev.ru #endif 67663Sigor@sysoev.ru 67763Sigor@sysoev.ru 67863Sigor@sysoev.ru static void * 67963Sigor@sysoev.ru nxt_mp_alloc_large(nxt_mp_t *mp, size_t alignment, size_t size) 68063Sigor@sysoev.ru { 68163Sigor@sysoev.ru u_char *p; 68263Sigor@sysoev.ru size_t aligned_size; 68363Sigor@sysoev.ru uint8_t type; 68463Sigor@sysoev.ru nxt_mp_block_t *block; 68563Sigor@sysoev.ru 686128Smax.romanov@nginx.com nxt_mp_thread_assert(mp); 687128Smax.romanov@nginx.com 68863Sigor@sysoev.ru /* Allocation must be less than 4G. */ 68963Sigor@sysoev.ru if (nxt_slow_path(size >= 0xFFFFFFFF)) { 69063Sigor@sysoev.ru return NULL; 69163Sigor@sysoev.ru } 69263Sigor@sysoev.ru 69363Sigor@sysoev.ru if (nxt_is_power_of_two(size)) { 69463Sigor@sysoev.ru block = nxt_malloc(sizeof(nxt_mp_block_t)); 69563Sigor@sysoev.ru if (nxt_slow_path(block == NULL)) { 69663Sigor@sysoev.ru return NULL; 69763Sigor@sysoev.ru } 69863Sigor@sysoev.ru 69963Sigor@sysoev.ru p = nxt_memalign(alignment, size); 70063Sigor@sysoev.ru if (nxt_slow_path(p == NULL)) { 70163Sigor@sysoev.ru nxt_free(block); 70263Sigor@sysoev.ru return NULL; 70363Sigor@sysoev.ru } 70463Sigor@sysoev.ru 70563Sigor@sysoev.ru type = NXT_MP_DISCRETE_BLOCK; 70663Sigor@sysoev.ru 70763Sigor@sysoev.ru } else { 70863Sigor@sysoev.ru aligned_size = nxt_align_size(size, sizeof(uintptr_t)); 70963Sigor@sysoev.ru 71063Sigor@sysoev.ru p = nxt_memalign(alignment, aligned_size + sizeof(nxt_mp_block_t)); 71163Sigor@sysoev.ru if (nxt_slow_path(p == NULL)) { 71263Sigor@sysoev.ru return NULL; 71363Sigor@sysoev.ru } 71463Sigor@sysoev.ru 71563Sigor@sysoev.ru block = (nxt_mp_block_t *) (p + aligned_size); 71663Sigor@sysoev.ru type = NXT_MP_EMBEDDED_BLOCK; 71763Sigor@sysoev.ru } 71863Sigor@sysoev.ru 71963Sigor@sysoev.ru block->type = type; 72063Sigor@sysoev.ru block->size = size; 72163Sigor@sysoev.ru block->start = p; 72263Sigor@sysoev.ru 72363Sigor@sysoev.ru nxt_rbtree_insert(&mp->blocks, &block->node); 72463Sigor@sysoev.ru 72563Sigor@sysoev.ru return p; 72663Sigor@sysoev.ru } 72763Sigor@sysoev.ru 72863Sigor@sysoev.ru 72963Sigor@sysoev.ru static intptr_t 73063Sigor@sysoev.ru nxt_mp_rbtree_compare(nxt_rbtree_node_t *node1, nxt_rbtree_node_t *node2) 73163Sigor@sysoev.ru { 73263Sigor@sysoev.ru nxt_mp_block_t *block1, *block2; 73363Sigor@sysoev.ru 73463Sigor@sysoev.ru block1 = (nxt_mp_block_t *) node1; 73563Sigor@sysoev.ru block2 = (nxt_mp_block_t *) node2; 73663Sigor@sysoev.ru 73763Sigor@sysoev.ru return (uintptr_t) block1->start - (uintptr_t) block2->start; 73863Sigor@sysoev.ru } 73963Sigor@sysoev.ru 74063Sigor@sysoev.ru 74163Sigor@sysoev.ru void 74263Sigor@sysoev.ru nxt_mp_free(nxt_mp_t *mp, void *p) 74363Sigor@sysoev.ru { 74463Sigor@sysoev.ru const char *err; 74563Sigor@sysoev.ru nxt_thread_t *thread; 74663Sigor@sysoev.ru nxt_mp_block_t *block; 74763Sigor@sysoev.ru 748128Smax.romanov@nginx.com nxt_mp_thread_assert(mp); 749128Smax.romanov@nginx.com 750*145Smax.romanov@nginx.com nxt_debug_alloc("mp %p free(%p)", mp, p); 75163Sigor@sysoev.ru 75263Sigor@sysoev.ru block = nxt_mp_find_block(&mp->blocks, p); 75363Sigor@sysoev.ru 75463Sigor@sysoev.ru if (nxt_fast_path(block != NULL)) { 75563Sigor@sysoev.ru 75663Sigor@sysoev.ru if (block->type == NXT_MP_CLUSTER_BLOCK) { 75763Sigor@sysoev.ru err = nxt_mp_chunk_free(mp, block, p); 75863Sigor@sysoev.ru 75963Sigor@sysoev.ru if (nxt_fast_path(err == NULL)) { 76063Sigor@sysoev.ru return; 76163Sigor@sysoev.ru } 76263Sigor@sysoev.ru 76363Sigor@sysoev.ru } else if (nxt_fast_path(p == block->start)) { 76463Sigor@sysoev.ru nxt_rbtree_delete(&mp->blocks, &block->node); 76563Sigor@sysoev.ru 76663Sigor@sysoev.ru if (block->type == NXT_MP_DISCRETE_BLOCK) { 76763Sigor@sysoev.ru nxt_free(block); 76863Sigor@sysoev.ru } 76963Sigor@sysoev.ru 77063Sigor@sysoev.ru nxt_free(p); 77163Sigor@sysoev.ru 77263Sigor@sysoev.ru return; 77363Sigor@sysoev.ru 77463Sigor@sysoev.ru } else { 77563Sigor@sysoev.ru err = "freed pointer points to middle of block: %p"; 77663Sigor@sysoev.ru } 77763Sigor@sysoev.ru 77863Sigor@sysoev.ru } else { 77963Sigor@sysoev.ru err = "freed pointer is out of pool: %p"; 78063Sigor@sysoev.ru } 78163Sigor@sysoev.ru 78263Sigor@sysoev.ru thread = nxt_thread(); 78363Sigor@sysoev.ru 78463Sigor@sysoev.ru nxt_log(thread->task, NXT_LOG_CRIT, err, p); 78563Sigor@sysoev.ru } 78663Sigor@sysoev.ru 78763Sigor@sysoev.ru 78863Sigor@sysoev.ru static nxt_mp_block_t * 78963Sigor@sysoev.ru nxt_mp_find_block(nxt_rbtree_t *tree, u_char *p) 79063Sigor@sysoev.ru { 79163Sigor@sysoev.ru nxt_mp_block_t *block; 79263Sigor@sysoev.ru nxt_rbtree_node_t *node, *sentinel; 79363Sigor@sysoev.ru 79463Sigor@sysoev.ru node = nxt_rbtree_root(tree); 79563Sigor@sysoev.ru sentinel = nxt_rbtree_sentinel(tree); 79663Sigor@sysoev.ru 79763Sigor@sysoev.ru while (node != sentinel) { 79863Sigor@sysoev.ru 79963Sigor@sysoev.ru block = (nxt_mp_block_t *) node; 80063Sigor@sysoev.ru 80163Sigor@sysoev.ru if (p < block->start) { 80263Sigor@sysoev.ru node = node->left; 80363Sigor@sysoev.ru 80463Sigor@sysoev.ru } else if (p >= block->start + block->size) { 80563Sigor@sysoev.ru node = node->right; 80663Sigor@sysoev.ru 80763Sigor@sysoev.ru } else { 80863Sigor@sysoev.ru return block; 80963Sigor@sysoev.ru } 81063Sigor@sysoev.ru } 81163Sigor@sysoev.ru 81263Sigor@sysoev.ru return NULL; 81363Sigor@sysoev.ru } 81463Sigor@sysoev.ru 81563Sigor@sysoev.ru 81663Sigor@sysoev.ru static const char * 81763Sigor@sysoev.ru nxt_mp_chunk_free(nxt_mp_t *mp, nxt_mp_block_t *cluster, u_char *p) 81863Sigor@sysoev.ru { 81963Sigor@sysoev.ru u_char *start; 82063Sigor@sysoev.ru uintptr_t offset; 82163Sigor@sysoev.ru nxt_uint_t n, size, chunk; 82263Sigor@sysoev.ru nxt_queue_t *chunk_pages; 82363Sigor@sysoev.ru nxt_mp_page_t *page; 82463Sigor@sysoev.ru 82563Sigor@sysoev.ru n = (p - cluster->start) >> mp->page_size_shift; 82663Sigor@sysoev.ru start = cluster->start + (n << mp->page_size_shift); 82763Sigor@sysoev.ru 82863Sigor@sysoev.ru page = &cluster->pages[n]; 82963Sigor@sysoev.ru 83063Sigor@sysoev.ru if (nxt_slow_path(page->size == 0)) { 83163Sigor@sysoev.ru return "freed pointer points to already free page: %p"; 83263Sigor@sysoev.ru } 83363Sigor@sysoev.ru 83463Sigor@sysoev.ru if (nxt_slow_path(page->size == 0xFF)) { 83563Sigor@sysoev.ru return "freed pointer points to non-freeble page: %p"; 83663Sigor@sysoev.ru } 83763Sigor@sysoev.ru 83863Sigor@sysoev.ru size = page->size << mp->chunk_size_shift; 83963Sigor@sysoev.ru 84063Sigor@sysoev.ru if (size != mp->page_size) { 84163Sigor@sysoev.ru 84263Sigor@sysoev.ru offset = (uintptr_t) (p - start) & (mp->page_size - 1); 84363Sigor@sysoev.ru chunk = offset / size; 84463Sigor@sysoev.ru 84563Sigor@sysoev.ru if (nxt_slow_path(offset != chunk * size)) { 84663Sigor@sysoev.ru return "freed pointer points to wrong chunk: %p"; 84763Sigor@sysoev.ru } 84863Sigor@sysoev.ru 84963Sigor@sysoev.ru if (nxt_slow_path(nxt_mp_chunk_is_free(page->u.map, chunk))) { 85063Sigor@sysoev.ru return "freed pointer points to already free chunk: %p"; 85163Sigor@sysoev.ru } 85263Sigor@sysoev.ru 85363Sigor@sysoev.ru nxt_mp_chunk_set_free(page->u.map, chunk); 85463Sigor@sysoev.ru 85563Sigor@sysoev.ru if (page->u.map != 0xFFFFFFFF) { 85663Sigor@sysoev.ru page->chunks++; 85763Sigor@sysoev.ru 85863Sigor@sysoev.ru if (page->chunks == 1) { 85963Sigor@sysoev.ru /* 86063Sigor@sysoev.ru * Add the page to the head of pool chunk pages list 86163Sigor@sysoev.ru * of pages with free chunks. 86263Sigor@sysoev.ru */ 86363Sigor@sysoev.ru n = nxt_mp_chunk_pages_index(mp, size); 86463Sigor@sysoev.ru chunk_pages = &mp->chunk_pages[n]; 86563Sigor@sysoev.ru 86663Sigor@sysoev.ru nxt_queue_insert_head(chunk_pages, &page->link); 86763Sigor@sysoev.ru } 86863Sigor@sysoev.ru 86963Sigor@sysoev.ru nxt_mp_free_junk(p, size); 87063Sigor@sysoev.ru 87163Sigor@sysoev.ru return NULL; 87263Sigor@sysoev.ru 87363Sigor@sysoev.ru } else { 87463Sigor@sysoev.ru /* 87563Sigor@sysoev.ru * All chunks are free, remove the page from pool 87663Sigor@sysoev.ru * chunk pages list of pages with free chunks. 87763Sigor@sysoev.ru */ 87863Sigor@sysoev.ru nxt_queue_remove(&page->link); 87963Sigor@sysoev.ru } 88063Sigor@sysoev.ru 88163Sigor@sysoev.ru } else if (nxt_slow_path(p != start)) { 88263Sigor@sysoev.ru return "invalid pointer to chunk: %p"; 88363Sigor@sysoev.ru } 88463Sigor@sysoev.ru 88563Sigor@sysoev.ru /* Add the free page to the pool's free pages tree. */ 88663Sigor@sysoev.ru 88763Sigor@sysoev.ru page->size = 0; 88863Sigor@sysoev.ru nxt_queue_insert_head(&mp->free_pages, &page->link); 88963Sigor@sysoev.ru 89063Sigor@sysoev.ru nxt_mp_free_junk(p, size); 89163Sigor@sysoev.ru 89263Sigor@sysoev.ru /* Test if all pages in the cluster are free. */ 89363Sigor@sysoev.ru 89463Sigor@sysoev.ru n = mp->cluster_size >> mp->page_size_shift; 89563Sigor@sysoev.ru page = cluster->pages; 89663Sigor@sysoev.ru 89763Sigor@sysoev.ru do { 89863Sigor@sysoev.ru if (page->size != 0) { 89963Sigor@sysoev.ru return NULL; 90063Sigor@sysoev.ru } 90163Sigor@sysoev.ru 90263Sigor@sysoev.ru page++; 90363Sigor@sysoev.ru n--; 90463Sigor@sysoev.ru } while (n != 0); 90563Sigor@sysoev.ru 90663Sigor@sysoev.ru /* Free cluster. */ 90763Sigor@sysoev.ru 90863Sigor@sysoev.ru n = mp->cluster_size >> mp->page_size_shift; 90963Sigor@sysoev.ru page = cluster->pages; 91063Sigor@sysoev.ru 91163Sigor@sysoev.ru do { 91263Sigor@sysoev.ru nxt_queue_remove(&page->link); 91363Sigor@sysoev.ru page++; 91463Sigor@sysoev.ru n--; 91563Sigor@sysoev.ru } while (n != 0); 91663Sigor@sysoev.ru 91763Sigor@sysoev.ru nxt_rbtree_delete(&mp->blocks, &cluster->node); 91863Sigor@sysoev.ru 91963Sigor@sysoev.ru p = cluster->start; 92063Sigor@sysoev.ru 92163Sigor@sysoev.ru nxt_free(cluster); 92263Sigor@sysoev.ru nxt_free(p); 92363Sigor@sysoev.ru 92463Sigor@sysoev.ru return NULL; 92563Sigor@sysoev.ru } 92663Sigor@sysoev.ru 92763Sigor@sysoev.ru 92863Sigor@sysoev.ru void * 92963Sigor@sysoev.ru nxt_mp_retain(nxt_mp_t *mp, size_t size) 93063Sigor@sysoev.ru { 93163Sigor@sysoev.ru void *p; 93263Sigor@sysoev.ru 93363Sigor@sysoev.ru p = nxt_mp_alloc(mp, size); 93463Sigor@sysoev.ru 93563Sigor@sysoev.ru if (nxt_fast_path(p != NULL)) { 93663Sigor@sysoev.ru mp->retain++; 937*145Smax.romanov@nginx.com nxt_debug_alloc("mp %p retain: %uD", mp, mp->retain); 93863Sigor@sysoev.ru } 93963Sigor@sysoev.ru 94063Sigor@sysoev.ru return p; 94163Sigor@sysoev.ru } 94263Sigor@sysoev.ru 94363Sigor@sysoev.ru 944141Smax.romanov@nginx.com uint32_t 94563Sigor@sysoev.ru nxt_mp_release(nxt_mp_t *mp, void *p) 94663Sigor@sysoev.ru { 94763Sigor@sysoev.ru nxt_mp_free(mp, p); 94863Sigor@sysoev.ru 94963Sigor@sysoev.ru mp->retain--; 95063Sigor@sysoev.ru 951*145Smax.romanov@nginx.com nxt_debug_alloc("mp %p release: %uD", mp, mp->retain); 95263Sigor@sysoev.ru 95363Sigor@sysoev.ru if (mp->retain == 0) { 95463Sigor@sysoev.ru nxt_mp_destroy(mp); 955141Smax.romanov@nginx.com 956141Smax.romanov@nginx.com return 0; 95763Sigor@sysoev.ru } 958141Smax.romanov@nginx.com 959141Smax.romanov@nginx.com return mp->retain; 96063Sigor@sysoev.ru } 96163Sigor@sysoev.ru 96263Sigor@sysoev.ru 96363Sigor@sysoev.ru void * 96463Sigor@sysoev.ru nxt_mp_nget(nxt_mp_t *mp, size_t size) 96563Sigor@sysoev.ru { 966*145Smax.romanov@nginx.com void *p; 96763Sigor@sysoev.ru 96863Sigor@sysoev.ru #if !(NXT_DEBUG_MEMORY) 96963Sigor@sysoev.ru 97063Sigor@sysoev.ru if (size <= mp->page_size) { 971*145Smax.romanov@nginx.com p = nxt_mp_get_small(mp, &mp->nget_pages, size); 972*145Smax.romanov@nginx.com 973*145Smax.romanov@nginx.com } else { 974*145Smax.romanov@nginx.com 975*145Smax.romanov@nginx.com #endif 976*145Smax.romanov@nginx.com 977*145Smax.romanov@nginx.com p = nxt_mp_alloc_large(mp, NXT_MAX_ALIGNMENT, size); 978*145Smax.romanov@nginx.com 979*145Smax.romanov@nginx.com #if !(NXT_DEBUG_MEMORY) 980*145Smax.romanov@nginx.com 98163Sigor@sysoev.ru } 98263Sigor@sysoev.ru 98363Sigor@sysoev.ru #endif 98463Sigor@sysoev.ru 985*145Smax.romanov@nginx.com nxt_debug_alloc("mp %p nget(%uz): %p", mp, size, p); 986*145Smax.romanov@nginx.com 987*145Smax.romanov@nginx.com return p; 98863Sigor@sysoev.ru } 98963Sigor@sysoev.ru 99063Sigor@sysoev.ru 99163Sigor@sysoev.ru void * 99263Sigor@sysoev.ru nxt_mp_get(nxt_mp_t *mp, size_t size) 99363Sigor@sysoev.ru { 994*145Smax.romanov@nginx.com void *p; 99563Sigor@sysoev.ru 99663Sigor@sysoev.ru #if !(NXT_DEBUG_MEMORY) 99763Sigor@sysoev.ru 99863Sigor@sysoev.ru if (size <= mp->page_size) { 99963Sigor@sysoev.ru size = nxt_max(size, NXT_MAX_ALIGNMENT); 1000*145Smax.romanov@nginx.com p = nxt_mp_get_small(mp, &mp->get_pages, size); 1001*145Smax.romanov@nginx.com 1002*145Smax.romanov@nginx.com } else { 1003*145Smax.romanov@nginx.com 1004*145Smax.romanov@nginx.com #endif 1005*145Smax.romanov@nginx.com 1006*145Smax.romanov@nginx.com p = nxt_mp_alloc_large(mp, NXT_MAX_ALIGNMENT, size); 1007*145Smax.romanov@nginx.com 1008*145Smax.romanov@nginx.com #if !(NXT_DEBUG_MEMORY) 1009*145Smax.romanov@nginx.com 101063Sigor@sysoev.ru } 101163Sigor@sysoev.ru 101263Sigor@sysoev.ru #endif 101363Sigor@sysoev.ru 1014*145Smax.romanov@nginx.com nxt_debug_alloc("mp %p get(%uz): %p", mp, size, p); 1015*145Smax.romanov@nginx.com 1016*145Smax.romanov@nginx.com return p; 101763Sigor@sysoev.ru } 101863Sigor@sysoev.ru 101963Sigor@sysoev.ru 102063Sigor@sysoev.ru void * 102163Sigor@sysoev.ru nxt_mp_zget(nxt_mp_t *mp, size_t size) 102263Sigor@sysoev.ru { 102363Sigor@sysoev.ru void *p; 102463Sigor@sysoev.ru 102563Sigor@sysoev.ru p = nxt_mp_get(mp, size); 102663Sigor@sysoev.ru 102763Sigor@sysoev.ru if (nxt_fast_path(p != NULL)) { 102863Sigor@sysoev.ru memset(p, 0, size); 102963Sigor@sysoev.ru } 103063Sigor@sysoev.ru 103163Sigor@sysoev.ru return p; 103263Sigor@sysoev.ru } 1033