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;
92653Sigor@sysoev.ru uint8_t freeable;
9363Sigor@sysoev.ru
9463Sigor@sysoev.ru /* Block size must be less than 4G. */
9563Sigor@sysoev.ru uint32_t size;
9663Sigor@sysoev.ru
9763Sigor@sysoev.ru u_char *start;
9863Sigor@sysoev.ru nxt_mp_page_t pages[];
9963Sigor@sysoev.ru } nxt_mp_block_t;
10063Sigor@sysoev.ru
10163Sigor@sysoev.ru
10263Sigor@sysoev.ru struct nxt_mp_s {
10363Sigor@sysoev.ru /* rbtree of nxt_mp_block_t. */
10463Sigor@sysoev.ru nxt_rbtree_t blocks;
10563Sigor@sysoev.ru
10663Sigor@sysoev.ru uint8_t chunk_size_shift;
10763Sigor@sysoev.ru uint8_t page_size_shift;
10863Sigor@sysoev.ru uint32_t page_size;
10963Sigor@sysoev.ru uint32_t page_alignment;
11063Sigor@sysoev.ru uint32_t cluster_size;
11163Sigor@sysoev.ru uint32_t retain;
11263Sigor@sysoev.ru
113128Smax.romanov@nginx.com #if (NXT_DEBUG)
114128Smax.romanov@nginx.com nxt_pid_t pid;
115128Smax.romanov@nginx.com nxt_tid_t tid;
116128Smax.romanov@nginx.com #endif
117128Smax.romanov@nginx.com
118164Smax.romanov@nginx.com nxt_work_t *cleanup;
119164Smax.romanov@nginx.com
12063Sigor@sysoev.ru /* Lists of nxt_mp_page_t. */
12163Sigor@sysoev.ru nxt_queue_t free_pages;
12263Sigor@sysoev.ru nxt_queue_t nget_pages;
12363Sigor@sysoev.ru nxt_queue_t get_pages;
12493Smax.romanov@nginx.com nxt_queue_t chunk_pages[];
12563Sigor@sysoev.ru };
12663Sigor@sysoev.ru
12763Sigor@sysoev.ru
12863Sigor@sysoev.ru #define nxt_mp_chunk_get_free(map) \
12963Sigor@sysoev.ru (__builtin_ffs(map) - 1)
13063Sigor@sysoev.ru
13163Sigor@sysoev.ru
13263Sigor@sysoev.ru #define nxt_mp_chunk_is_free(map, chunk) \
13363Sigor@sysoev.ru ((map & (1 << chunk)) != 0)
13463Sigor@sysoev.ru
13563Sigor@sysoev.ru
13663Sigor@sysoev.ru #define nxt_mp_chunk_set_busy(map, chunk) \
13763Sigor@sysoev.ru map &= ~(1 << chunk)
13863Sigor@sysoev.ru
13963Sigor@sysoev.ru
14063Sigor@sysoev.ru #define nxt_mp_chunk_set_free(map, chunk) \
14163Sigor@sysoev.ru map |= (1 << chunk)
14263Sigor@sysoev.ru
14363Sigor@sysoev.ru
14463Sigor@sysoev.ru #define nxt_mp_free_junk(p, size) \
14563Sigor@sysoev.ru memset((p), 0x5A, size)
14663Sigor@sysoev.ru
14763Sigor@sysoev.ru
14863Sigor@sysoev.ru #if !(NXT_DEBUG_MEMORY)
14968Sigor@sysoev.ru static void *nxt_mp_alloc_small(nxt_mp_t *mp, size_t size);
15063Sigor@sysoev.ru static void *nxt_mp_get_small(nxt_mp_t *mp, nxt_queue_t *pages, size_t size);
15163Sigor@sysoev.ru static nxt_mp_page_t *nxt_mp_alloc_page(nxt_mp_t *mp);
15263Sigor@sysoev.ru static nxt_mp_block_t *nxt_mp_alloc_cluster(nxt_mp_t *mp);
15363Sigor@sysoev.ru #endif
154653Sigor@sysoev.ru static void *nxt_mp_alloc_large(nxt_mp_t *mp, size_t alignment, size_t size,
155653Sigor@sysoev.ru nxt_bool_t freeable);
15663Sigor@sysoev.ru static intptr_t nxt_mp_rbtree_compare(nxt_rbtree_node_t *node1,
15763Sigor@sysoev.ru nxt_rbtree_node_t *node2);
158*2139Sandrew@digital-domain.net static nxt_mp_block_t *nxt_mp_find_block(nxt_rbtree_t *tree, const u_char *p);
15963Sigor@sysoev.ru static const char *nxt_mp_chunk_free(nxt_mp_t *mp, nxt_mp_block_t *cluster,
16063Sigor@sysoev.ru u_char *p);
16163Sigor@sysoev.ru
16263Sigor@sysoev.ru
16393Smax.romanov@nginx.com #if (NXT_HAVE_BUILTIN_CLZ)
16493Smax.romanov@nginx.com
16593Smax.romanov@nginx.com #define nxt_lg2(value) \
16693Smax.romanov@nginx.com (31 - __builtin_clz(value))
16793Smax.romanov@nginx.com
16893Smax.romanov@nginx.com #else
16993Smax.romanov@nginx.com
17093Smax.romanov@nginx.com static const int nxt_lg2_tab64[64] = {
17193Smax.romanov@nginx.com 63, 0, 58, 1, 59, 47, 53, 2,
17293Smax.romanov@nginx.com 60, 39, 48, 27, 54, 33, 42, 3,
17393Smax.romanov@nginx.com 61, 51, 37, 40, 49, 18, 28, 20,
17493Smax.romanov@nginx.com 55, 30, 34, 11, 43, 14, 22, 4,
17593Smax.romanov@nginx.com 62, 57, 46, 52, 38, 26, 32, 41,
17693Smax.romanov@nginx.com 50, 36, 17, 19, 29, 10, 13, 21,
17793Smax.romanov@nginx.com 56, 45, 25, 31, 35, 16, 9, 12,
17893Smax.romanov@nginx.com 44, 24, 15, 8, 23, 7, 6, 5
17993Smax.romanov@nginx.com };
18093Smax.romanov@nginx.com
18193Smax.romanov@nginx.com static const uint64_t nxt_lg2_magic = 0x07EDD5E59A4E28C2ULL;
18293Smax.romanov@nginx.com
18393Smax.romanov@nginx.com static int
nxt_lg2(uint64_t v)18493Smax.romanov@nginx.com nxt_lg2(uint64_t v)
18593Smax.romanov@nginx.com {
18693Smax.romanov@nginx.com v |= v >> 1;
18793Smax.romanov@nginx.com v |= v >> 2;
18893Smax.romanov@nginx.com v |= v >> 4;
18993Smax.romanov@nginx.com v |= v >> 8;
19093Smax.romanov@nginx.com v |= v >> 16;
19193Smax.romanov@nginx.com v |= v >> 32;
19293Smax.romanov@nginx.com return nxt_lg2_tab64[ ((v - (v >> 1)) * nxt_lg2_magic) >> 58 ];
19393Smax.romanov@nginx.com }
19493Smax.romanov@nginx.com
19593Smax.romanov@nginx.com #endif
19693Smax.romanov@nginx.com
19793Smax.romanov@nginx.com
198128Smax.romanov@nginx.com #if (NXT_DEBUG)
199128Smax.romanov@nginx.com
200128Smax.romanov@nginx.com nxt_inline void
nxt_mp_thread_assert(nxt_mp_t * mp)201128Smax.romanov@nginx.com nxt_mp_thread_assert(nxt_mp_t *mp)
202128Smax.romanov@nginx.com {
203128Smax.romanov@nginx.com nxt_tid_t tid;
204128Smax.romanov@nginx.com nxt_thread_t *thread;
205128Smax.romanov@nginx.com
206128Smax.romanov@nginx.com thread = nxt_thread();
207128Smax.romanov@nginx.com tid = nxt_thread_tid(thread);
208128Smax.romanov@nginx.com
209128Smax.romanov@nginx.com if (nxt_fast_path(mp->tid == tid)) {
210128Smax.romanov@nginx.com return;
211128Smax.romanov@nginx.com }
212128Smax.romanov@nginx.com
213128Smax.romanov@nginx.com if (nxt_slow_path(nxt_pid != mp->pid)) {
214128Smax.romanov@nginx.com mp->pid = nxt_pid;
215128Smax.romanov@nginx.com mp->tid = tid;
216128Smax.romanov@nginx.com
217128Smax.romanov@nginx.com return;
218128Smax.romanov@nginx.com }
219128Smax.romanov@nginx.com
220128Smax.romanov@nginx.com nxt_log_alert(thread->log, "mem_pool locked by thread %PT", mp->tid);
221128Smax.romanov@nginx.com nxt_abort();
222128Smax.romanov@nginx.com }
223128Smax.romanov@nginx.com
224128Smax.romanov@nginx.com #else
225128Smax.romanov@nginx.com
226128Smax.romanov@nginx.com #define nxt_mp_thread_assert(mp)
227128Smax.romanov@nginx.com
228128Smax.romanov@nginx.com #endif
229128Smax.romanov@nginx.com
230128Smax.romanov@nginx.com
231128Smax.romanov@nginx.com void
nxt_mp_thread_adopt(nxt_mp_t * mp)232128Smax.romanov@nginx.com nxt_mp_thread_adopt(nxt_mp_t *mp)
233128Smax.romanov@nginx.com {
234128Smax.romanov@nginx.com #if (NXT_DEBUG)
235128Smax.romanov@nginx.com mp->pid = nxt_pid;
236737Svbart@nginx.com mp->tid = nxt_thread_tid(nxt_thread());
237128Smax.romanov@nginx.com #endif
238128Smax.romanov@nginx.com }
239128Smax.romanov@nginx.com
240128Smax.romanov@nginx.com
24163Sigor@sysoev.ru nxt_mp_t *
nxt_mp_create(size_t cluster_size,size_t page_alignment,size_t page_size,size_t min_chunk_size)24263Sigor@sysoev.ru nxt_mp_create(size_t cluster_size, size_t page_alignment, size_t page_size,
24363Sigor@sysoev.ru size_t min_chunk_size)
24463Sigor@sysoev.ru {
24563Sigor@sysoev.ru nxt_mp_t *mp;
24669Sigor@sysoev.ru uint32_t pages, chunk_size_shift, page_size_shift;
24763Sigor@sysoev.ru nxt_queue_t *chunk_pages;
24863Sigor@sysoev.ru
24969Sigor@sysoev.ru chunk_size_shift = nxt_lg2(min_chunk_size);
25069Sigor@sysoev.ru page_size_shift = nxt_lg2(page_size);
25163Sigor@sysoev.ru
25269Sigor@sysoev.ru pages = page_size_shift - chunk_size_shift;
25363Sigor@sysoev.ru
25463Sigor@sysoev.ru mp = nxt_zalloc(sizeof(nxt_mp_t) + pages * sizeof(nxt_queue_t));
25563Sigor@sysoev.ru
25663Sigor@sysoev.ru if (nxt_fast_path(mp != NULL)) {
25763Sigor@sysoev.ru mp->retain = 1;
25869Sigor@sysoev.ru mp->chunk_size_shift = chunk_size_shift;
25969Sigor@sysoev.ru mp->page_size_shift = page_size_shift;
26063Sigor@sysoev.ru mp->page_size = page_size;
26163Sigor@sysoev.ru mp->page_alignment = nxt_max(page_alignment, NXT_MAX_ALIGNMENT);
26263Sigor@sysoev.ru mp->cluster_size = cluster_size;
26363Sigor@sysoev.ru
26463Sigor@sysoev.ru chunk_pages = mp->chunk_pages;
26563Sigor@sysoev.ru
26669Sigor@sysoev.ru while (pages != 0) {
26763Sigor@sysoev.ru nxt_queue_init(chunk_pages);
26863Sigor@sysoev.ru chunk_pages++;
26969Sigor@sysoev.ru pages--;
27072Sigor@sysoev.ru }
27163Sigor@sysoev.ru
27263Sigor@sysoev.ru nxt_queue_init(&mp->free_pages);
27364Sigor@sysoev.ru nxt_queue_init(&mp->nget_pages);
27464Sigor@sysoev.ru nxt_queue_init(&mp->get_pages);
27569Sigor@sysoev.ru
27669Sigor@sysoev.ru nxt_rbtree_init(&mp->blocks, nxt_mp_rbtree_compare);
27763Sigor@sysoev.ru }
27863Sigor@sysoev.ru
279145Smax.romanov@nginx.com nxt_debug_alloc("mp %p create(%uz, %uz, %uz, %uz)", mp, cluster_size,
280145Smax.romanov@nginx.com page_alignment, page_size, min_chunk_size);
281145Smax.romanov@nginx.com
28263Sigor@sysoev.ru return mp;
28363Sigor@sysoev.ru }
28463Sigor@sysoev.ru
28563Sigor@sysoev.ru
28663Sigor@sysoev.ru void
nxt_mp_retain(nxt_mp_t * mp)287430Sigor@sysoev.ru nxt_mp_retain(nxt_mp_t *mp)
288430Sigor@sysoev.ru {
289430Sigor@sysoev.ru mp->retain++;
290430Sigor@sysoev.ru
291430Sigor@sysoev.ru nxt_thread_log_debug("mp %p retain: %uD", mp, mp->retain);
292430Sigor@sysoev.ru }
293430Sigor@sysoev.ru
294430Sigor@sysoev.ru
295430Sigor@sysoev.ru void
nxt_mp_release(nxt_mp_t * mp)296430Sigor@sysoev.ru nxt_mp_release(nxt_mp_t *mp)
297430Sigor@sysoev.ru {
298430Sigor@sysoev.ru mp->retain--;
299430Sigor@sysoev.ru
300430Sigor@sysoev.ru nxt_thread_log_debug("mp %p release: %uD", mp, mp->retain);
301430Sigor@sysoev.ru
302430Sigor@sysoev.ru if (mp->retain == 0) {
303430Sigor@sysoev.ru nxt_mp_destroy(mp);
304430Sigor@sysoev.ru }
305430Sigor@sysoev.ru }
306430Sigor@sysoev.ru
307430Sigor@sysoev.ru
308430Sigor@sysoev.ru void
nxt_mp_destroy(nxt_mp_t * mp)30963Sigor@sysoev.ru nxt_mp_destroy(nxt_mp_t *mp)
31063Sigor@sysoev.ru {
31163Sigor@sysoev.ru void *p;
312164Smax.romanov@nginx.com nxt_work_t *work, *next_work;
31363Sigor@sysoev.ru nxt_mp_block_t *block;
31463Sigor@sysoev.ru nxt_rbtree_node_t *node, *next;
31563Sigor@sysoev.ru
316145Smax.romanov@nginx.com nxt_debug_alloc("mp %p destroy", mp);
31763Sigor@sysoev.ru
318131Smax.romanov@nginx.com nxt_mp_thread_assert(mp);
319131Smax.romanov@nginx.com
320164Smax.romanov@nginx.com while (mp->cleanup != NULL) {
321164Smax.romanov@nginx.com work = mp->cleanup;
322164Smax.romanov@nginx.com next_work = work->next;
323164Smax.romanov@nginx.com
324164Smax.romanov@nginx.com work->handler(work->task, work->obj, work->data);
325164Smax.romanov@nginx.com
326164Smax.romanov@nginx.com mp->cleanup = next_work;
327164Smax.romanov@nginx.com }
328164Smax.romanov@nginx.com
32963Sigor@sysoev.ru next = nxt_rbtree_root(&mp->blocks);
33063Sigor@sysoev.ru
33163Sigor@sysoev.ru while (next != nxt_rbtree_sentinel(&mp->blocks)) {
33263Sigor@sysoev.ru
33363Sigor@sysoev.ru node = nxt_rbtree_destroy_next(&mp->blocks, &next);
33463Sigor@sysoev.ru block = (nxt_mp_block_t *) node;
33563Sigor@sysoev.ru
33663Sigor@sysoev.ru p = block->start;
33763Sigor@sysoev.ru
33863Sigor@sysoev.ru if (block->type != NXT_MP_EMBEDDED_BLOCK) {
33963Sigor@sysoev.ru nxt_free(block);
34063Sigor@sysoev.ru }
34163Sigor@sysoev.ru
34263Sigor@sysoev.ru nxt_free(p);
34363Sigor@sysoev.ru }
34463Sigor@sysoev.ru
34563Sigor@sysoev.ru nxt_free(mp);
34663Sigor@sysoev.ru }
34763Sigor@sysoev.ru
34863Sigor@sysoev.ru
34963Sigor@sysoev.ru nxt_bool_t
nxt_mp_test_sizes(size_t cluster_size,size_t page_alignment,size_t page_size,size_t min_chunk_size)35063Sigor@sysoev.ru nxt_mp_test_sizes(size_t cluster_size, size_t page_alignment, size_t page_size,
35163Sigor@sysoev.ru size_t min_chunk_size)
35263Sigor@sysoev.ru {
35363Sigor@sysoev.ru nxt_bool_t valid;
35463Sigor@sysoev.ru
35563Sigor@sysoev.ru /* Alignment and sizes must be a power of 2. */
35663Sigor@sysoev.ru
35763Sigor@sysoev.ru valid = nxt_expect(1, (nxt_is_power_of_two(page_alignment)
35863Sigor@sysoev.ru && nxt_is_power_of_two(page_size)
35963Sigor@sysoev.ru && nxt_is_power_of_two(min_chunk_size)));
36063Sigor@sysoev.ru if (!valid) {
36163Sigor@sysoev.ru return 0;
36263Sigor@sysoev.ru }
36363Sigor@sysoev.ru
36463Sigor@sysoev.ru page_alignment = nxt_max(page_alignment, NXT_MAX_ALIGNMENT);
36563Sigor@sysoev.ru
36663Sigor@sysoev.ru valid = nxt_expect(1, (page_size >= 64
36763Sigor@sysoev.ru && page_size >= page_alignment
36863Sigor@sysoev.ru && page_size >= min_chunk_size
36963Sigor@sysoev.ru && min_chunk_size * 32 >= page_size
37063Sigor@sysoev.ru && cluster_size >= page_size
37163Sigor@sysoev.ru && cluster_size / page_size <= 256
37263Sigor@sysoev.ru && cluster_size % page_size == 0));
37363Sigor@sysoev.ru if (!valid) {
37463Sigor@sysoev.ru return 0;
37563Sigor@sysoev.ru }
37663Sigor@sysoev.ru
37763Sigor@sysoev.ru return 1;
37863Sigor@sysoev.ru }
37963Sigor@sysoev.ru
38063Sigor@sysoev.ru
38163Sigor@sysoev.ru nxt_bool_t
nxt_mp_is_empty(nxt_mp_t * mp)38263Sigor@sysoev.ru nxt_mp_is_empty(nxt_mp_t *mp)
38363Sigor@sysoev.ru {
38463Sigor@sysoev.ru return (nxt_rbtree_is_empty(&mp->blocks)
38563Sigor@sysoev.ru && nxt_queue_is_empty(&mp->free_pages));
38663Sigor@sysoev.ru }
38763Sigor@sysoev.ru
38863Sigor@sysoev.ru
38963Sigor@sysoev.ru void *
nxt_mp_alloc(nxt_mp_t * mp,size_t size)39063Sigor@sysoev.ru nxt_mp_alloc(nxt_mp_t *mp, size_t size)
39163Sigor@sysoev.ru {
392145Smax.romanov@nginx.com void *p;
39363Sigor@sysoev.ru
39463Sigor@sysoev.ru #if !(NXT_DEBUG_MEMORY)
39563Sigor@sysoev.ru
39663Sigor@sysoev.ru if (size <= mp->page_size) {
397145Smax.romanov@nginx.com p = nxt_mp_alloc_small(mp, size);
398145Smax.romanov@nginx.com
399145Smax.romanov@nginx.com } else {
400653Sigor@sysoev.ru p = nxt_mp_alloc_large(mp, NXT_MAX_ALIGNMENT, size, 1);
401147Svbart@nginx.com }
402145Smax.romanov@nginx.com
403147Svbart@nginx.com #else
404145Smax.romanov@nginx.com
405653Sigor@sysoev.ru p = nxt_mp_alloc_large(mp, NXT_MAX_ALIGNMENT, size, 1);
406145Smax.romanov@nginx.com
40763Sigor@sysoev.ru #endif
40863Sigor@sysoev.ru
409145Smax.romanov@nginx.com nxt_debug_alloc("mp %p alloc(%uz): %p", mp, size, p);
410145Smax.romanov@nginx.com
411145Smax.romanov@nginx.com return p;
41263Sigor@sysoev.ru }
41363Sigor@sysoev.ru
41463Sigor@sysoev.ru
41563Sigor@sysoev.ru void *
nxt_mp_zalloc(nxt_mp_t * mp,size_t size)41663Sigor@sysoev.ru nxt_mp_zalloc(nxt_mp_t *mp, size_t size)
41763Sigor@sysoev.ru {
41863Sigor@sysoev.ru void *p;
41963Sigor@sysoev.ru
42063Sigor@sysoev.ru p = nxt_mp_alloc(mp, size);
42163Sigor@sysoev.ru
42263Sigor@sysoev.ru if (nxt_fast_path(p != NULL)) {
42363Sigor@sysoev.ru memset(p, 0, size);
42463Sigor@sysoev.ru }
42563Sigor@sysoev.ru
42663Sigor@sysoev.ru return p;
42763Sigor@sysoev.ru }
42863Sigor@sysoev.ru
42963Sigor@sysoev.ru
43063Sigor@sysoev.ru void *
nxt_mp_align(nxt_mp_t * mp,size_t alignment,size_t size)43163Sigor@sysoev.ru nxt_mp_align(nxt_mp_t *mp, size_t alignment, size_t size)
43263Sigor@sysoev.ru {
433145Smax.romanov@nginx.com void *p;
43463Sigor@sysoev.ru
43563Sigor@sysoev.ru /* Alignment must be a power of 2. */
43663Sigor@sysoev.ru
43763Sigor@sysoev.ru if (nxt_fast_path(nxt_is_power_of_two(alignment))) {
43863Sigor@sysoev.ru
43963Sigor@sysoev.ru #if !(NXT_DEBUG_MEMORY)
44063Sigor@sysoev.ru
441147Svbart@nginx.com size_t aligned_size;
442147Svbart@nginx.com
443145Smax.romanov@nginx.com aligned_size = nxt_max(size, alignment);
444145Smax.romanov@nginx.com
445145Smax.romanov@nginx.com if (aligned_size <= mp->page_size && alignment <= mp->page_alignment) {
446145Smax.romanov@nginx.com p = nxt_mp_alloc_small(mp, aligned_size);
44763Sigor@sysoev.ru
448145Smax.romanov@nginx.com } else {
449653Sigor@sysoev.ru p = nxt_mp_alloc_large(mp, alignment, size, 1);
450147Svbart@nginx.com }
451145Smax.romanov@nginx.com
452147Svbart@nginx.com #else
453145Smax.romanov@nginx.com
454653Sigor@sysoev.ru p = nxt_mp_alloc_large(mp, alignment, size, 1);
455145Smax.romanov@nginx.com
45663Sigor@sysoev.ru #endif
45763Sigor@sysoev.ru
458145Smax.romanov@nginx.com } else {
459145Smax.romanov@nginx.com p = NULL;
46063Sigor@sysoev.ru }
46163Sigor@sysoev.ru
462145Smax.romanov@nginx.com nxt_debug_alloc("mp %p align(@%uz:%uz): %p", mp, alignment, size, p);
463145Smax.romanov@nginx.com
464145Smax.romanov@nginx.com return p;
46563Sigor@sysoev.ru }
46663Sigor@sysoev.ru
46763Sigor@sysoev.ru
46863Sigor@sysoev.ru void *
nxt_mp_zalign(nxt_mp_t * mp,size_t alignment,size_t size)46963Sigor@sysoev.ru nxt_mp_zalign(nxt_mp_t *mp, size_t alignment, size_t size)
47063Sigor@sysoev.ru {
47163Sigor@sysoev.ru void *p;
47263Sigor@sysoev.ru
47363Sigor@sysoev.ru p = nxt_mp_align(mp, alignment, size);
47463Sigor@sysoev.ru
47563Sigor@sysoev.ru if (nxt_fast_path(p != NULL)) {
47663Sigor@sysoev.ru memset(p, 0, size);
47763Sigor@sysoev.ru }
47863Sigor@sysoev.ru
47963Sigor@sysoev.ru return p;
48063Sigor@sysoev.ru }
48163Sigor@sysoev.ru
48263Sigor@sysoev.ru
48363Sigor@sysoev.ru nxt_inline nxt_uint_t
nxt_mp_chunk_pages_index(nxt_mp_t * mp,size_t size)48463Sigor@sysoev.ru nxt_mp_chunk_pages_index(nxt_mp_t *mp, size_t size)
48563Sigor@sysoev.ru {
48663Sigor@sysoev.ru nxt_int_t n, index;
48763Sigor@sysoev.ru
48863Sigor@sysoev.ru index = 0;
48963Sigor@sysoev.ru
49063Sigor@sysoev.ru if (size > 1) {
49163Sigor@sysoev.ru n = nxt_lg2(size - 1) + 1 - mp->chunk_size_shift;
49263Sigor@sysoev.ru
49363Sigor@sysoev.ru if (n > 0) {
49463Sigor@sysoev.ru index = n;
49563Sigor@sysoev.ru }
49663Sigor@sysoev.ru }
49763Sigor@sysoev.ru
49863Sigor@sysoev.ru return index;
49963Sigor@sysoev.ru }
50063Sigor@sysoev.ru
50163Sigor@sysoev.ru
50268Sigor@sysoev.ru #if !(NXT_DEBUG_MEMORY)
50368Sigor@sysoev.ru
50468Sigor@sysoev.ru nxt_inline u_char *
nxt_mp_page_addr(nxt_mp_t * mp,nxt_mp_page_t * page)50568Sigor@sysoev.ru nxt_mp_page_addr(nxt_mp_t *mp, nxt_mp_page_t *page)
50668Sigor@sysoev.ru {
50768Sigor@sysoev.ru size_t page_offset;
50868Sigor@sysoev.ru nxt_mp_block_t *block;
50968Sigor@sysoev.ru
51068Sigor@sysoev.ru page_offset = page->number * sizeof(nxt_mp_page_t)
51168Sigor@sysoev.ru + offsetof(nxt_mp_block_t, pages);
51268Sigor@sysoev.ru
51368Sigor@sysoev.ru block = (nxt_mp_block_t *) ((u_char *) page - page_offset);
51468Sigor@sysoev.ru
51568Sigor@sysoev.ru return block->start + (page->number << mp->page_size_shift);
51668Sigor@sysoev.ru }
51768Sigor@sysoev.ru
51868Sigor@sysoev.ru
51963Sigor@sysoev.ru static void *
nxt_mp_alloc_small(nxt_mp_t * mp,size_t size)52063Sigor@sysoev.ru nxt_mp_alloc_small(nxt_mp_t *mp, size_t size)
52163Sigor@sysoev.ru {
52263Sigor@sysoev.ru u_char *p;
52363Sigor@sysoev.ru nxt_uint_t n, index;
52463Sigor@sysoev.ru nxt_queue_t *chunk_pages;
52563Sigor@sysoev.ru nxt_mp_page_t *page;
52663Sigor@sysoev.ru nxt_queue_link_t *link;
52763Sigor@sysoev.ru
528128Smax.romanov@nginx.com nxt_mp_thread_assert(mp);
529128Smax.romanov@nginx.com
53063Sigor@sysoev.ru p = NULL;
53163Sigor@sysoev.ru
53263Sigor@sysoev.ru if (size <= mp->page_size / 2) {
53363Sigor@sysoev.ru
53463Sigor@sysoev.ru index = nxt_mp_chunk_pages_index(mp, size);
53563Sigor@sysoev.ru chunk_pages = &mp->chunk_pages[index];
53663Sigor@sysoev.ru
53763Sigor@sysoev.ru if (nxt_fast_path(!nxt_queue_is_empty(chunk_pages))) {
53863Sigor@sysoev.ru
53963Sigor@sysoev.ru link = nxt_queue_first(chunk_pages);
54063Sigor@sysoev.ru page = nxt_queue_link_data(link, nxt_mp_page_t, link);
54163Sigor@sysoev.ru
54263Sigor@sysoev.ru p = nxt_mp_page_addr(mp, page);
54363Sigor@sysoev.ru
54463Sigor@sysoev.ru n = nxt_mp_chunk_get_free(page->u.map);
54563Sigor@sysoev.ru nxt_mp_chunk_set_busy(page->u.map, n);
54663Sigor@sysoev.ru
54763Sigor@sysoev.ru p += ((n << index) << mp->chunk_size_shift);
54863Sigor@sysoev.ru
54963Sigor@sysoev.ru page->chunks--;
55063Sigor@sysoev.ru
55163Sigor@sysoev.ru if (page->chunks == 0) {
55263Sigor@sysoev.ru /*
55363Sigor@sysoev.ru * Remove full page from the pool chunk pages list
55463Sigor@sysoev.ru * of pages with free chunks.
55563Sigor@sysoev.ru */
55663Sigor@sysoev.ru nxt_queue_remove(&page->link);
55763Sigor@sysoev.ru }
55863Sigor@sysoev.ru
55963Sigor@sysoev.ru } else {
56063Sigor@sysoev.ru page = nxt_mp_alloc_page(mp);
56163Sigor@sysoev.ru
56263Sigor@sysoev.ru if (nxt_fast_path(page != NULL)) {
56363Sigor@sysoev.ru page->size = (1 << index);
56463Sigor@sysoev.ru
56563Sigor@sysoev.ru n = mp->page_size_shift - (index + mp->chunk_size_shift);
56663Sigor@sysoev.ru page->chunks = (1 << n) - 1;
56763Sigor@sysoev.ru
56863Sigor@sysoev.ru nxt_queue_insert_head(chunk_pages, &page->link);
56963Sigor@sysoev.ru
57063Sigor@sysoev.ru /* Mark the first chunk as busy. */
57163Sigor@sysoev.ru page->u.map = 0xFFFFFFFE;
57263Sigor@sysoev.ru
57363Sigor@sysoev.ru p = nxt_mp_page_addr(mp, page);
57463Sigor@sysoev.ru }
57563Sigor@sysoev.ru }
57663Sigor@sysoev.ru
57763Sigor@sysoev.ru } else {
57863Sigor@sysoev.ru page = nxt_mp_alloc_page(mp);
57963Sigor@sysoev.ru
58063Sigor@sysoev.ru if (nxt_fast_path(page != NULL)) {
58163Sigor@sysoev.ru page->size = mp->page_size >> mp->chunk_size_shift;
58263Sigor@sysoev.ru
58363Sigor@sysoev.ru p = nxt_mp_page_addr(mp, page);
58463Sigor@sysoev.ru }
58563Sigor@sysoev.ru }
58663Sigor@sysoev.ru
587145Smax.romanov@nginx.com nxt_debug_alloc("mp %p chunk:%uz alloc: %p", mp,
58863Sigor@sysoev.ru page->size << mp->chunk_size_shift, p);
58963Sigor@sysoev.ru
59063Sigor@sysoev.ru return p;
59163Sigor@sysoev.ru }
59263Sigor@sysoev.ru
59363Sigor@sysoev.ru
59468Sigor@sysoev.ru static void *
nxt_mp_get_small(nxt_mp_t * mp,nxt_queue_t * pages,size_t size)59568Sigor@sysoev.ru nxt_mp_get_small(nxt_mp_t *mp, nxt_queue_t *pages, size_t size)
59668Sigor@sysoev.ru {
59768Sigor@sysoev.ru u_char *p;
59868Sigor@sysoev.ru uint32_t available;
59968Sigor@sysoev.ru nxt_mp_page_t *page;
60068Sigor@sysoev.ru nxt_queue_link_t *link, *next;
60168Sigor@sysoev.ru
602128Smax.romanov@nginx.com nxt_mp_thread_assert(mp);
603128Smax.romanov@nginx.com
60468Sigor@sysoev.ru for (link = nxt_queue_first(pages);
60568Sigor@sysoev.ru link != nxt_queue_tail(pages);
60668Sigor@sysoev.ru link = next)
60768Sigor@sysoev.ru {
60868Sigor@sysoev.ru next = nxt_queue_next(link);
60968Sigor@sysoev.ru page = nxt_queue_link_data(link, nxt_mp_page_t, link);
61068Sigor@sysoev.ru
61168Sigor@sysoev.ru available = mp->page_size - page->u.taken;
61268Sigor@sysoev.ru
61368Sigor@sysoev.ru if (size <= available) {
61468Sigor@sysoev.ru goto found;
61568Sigor@sysoev.ru }
61668Sigor@sysoev.ru
61768Sigor@sysoev.ru if (available == 0 || page->fails++ > 100) {
61868Sigor@sysoev.ru nxt_queue_remove(link);
61968Sigor@sysoev.ru }
62068Sigor@sysoev.ru }
62168Sigor@sysoev.ru
62268Sigor@sysoev.ru page = nxt_mp_alloc_page(mp);
62368Sigor@sysoev.ru
62468Sigor@sysoev.ru if (nxt_slow_path(page == NULL)) {
62568Sigor@sysoev.ru return page;
62668Sigor@sysoev.ru }
62768Sigor@sysoev.ru
62868Sigor@sysoev.ru nxt_queue_insert_head(pages, &page->link);
62968Sigor@sysoev.ru
63068Sigor@sysoev.ru page->size = 0xFF;
631129Smax.romanov@nginx.com page->u.taken = 0;
63268Sigor@sysoev.ru
63368Sigor@sysoev.ru found:
63468Sigor@sysoev.ru
63568Sigor@sysoev.ru p = nxt_mp_page_addr(mp, page);
63668Sigor@sysoev.ru
63768Sigor@sysoev.ru p += page->u.taken;
63868Sigor@sysoev.ru page->u.taken += size;
63968Sigor@sysoev.ru
64068Sigor@sysoev.ru return p;
64168Sigor@sysoev.ru }
64268Sigor@sysoev.ru
64368Sigor@sysoev.ru
64463Sigor@sysoev.ru static nxt_mp_page_t *
nxt_mp_alloc_page(nxt_mp_t * mp)64563Sigor@sysoev.ru nxt_mp_alloc_page(nxt_mp_t *mp)
64663Sigor@sysoev.ru {
64763Sigor@sysoev.ru nxt_mp_page_t *page;
64863Sigor@sysoev.ru nxt_mp_block_t *cluster;
64963Sigor@sysoev.ru nxt_queue_link_t *link;
65063Sigor@sysoev.ru
65163Sigor@sysoev.ru if (nxt_queue_is_empty(&mp->free_pages)) {
65263Sigor@sysoev.ru cluster = nxt_mp_alloc_cluster(mp);
65363Sigor@sysoev.ru if (nxt_slow_path(cluster == NULL)) {
65463Sigor@sysoev.ru return NULL;
65563Sigor@sysoev.ru }
65663Sigor@sysoev.ru }
65763Sigor@sysoev.ru
65863Sigor@sysoev.ru link = nxt_queue_first(&mp->free_pages);
65963Sigor@sysoev.ru nxt_queue_remove(link);
66063Sigor@sysoev.ru
66163Sigor@sysoev.ru page = nxt_queue_link_data(link, nxt_mp_page_t, link);
66263Sigor@sysoev.ru
66363Sigor@sysoev.ru return page;
66463Sigor@sysoev.ru }
66563Sigor@sysoev.ru
66663Sigor@sysoev.ru
66763Sigor@sysoev.ru static nxt_mp_block_t *
nxt_mp_alloc_cluster(nxt_mp_t * mp)66863Sigor@sysoev.ru nxt_mp_alloc_cluster(nxt_mp_t *mp)
66963Sigor@sysoev.ru {
67063Sigor@sysoev.ru nxt_uint_t n;
67163Sigor@sysoev.ru nxt_mp_block_t *cluster;
67263Sigor@sysoev.ru
67363Sigor@sysoev.ru n = mp->cluster_size >> mp->page_size_shift;
67463Sigor@sysoev.ru
67563Sigor@sysoev.ru cluster = nxt_zalloc(sizeof(nxt_mp_block_t) + n * sizeof(nxt_mp_page_t));
67663Sigor@sysoev.ru
67763Sigor@sysoev.ru if (nxt_slow_path(cluster == NULL)) {
67863Sigor@sysoev.ru return NULL;
67963Sigor@sysoev.ru }
68063Sigor@sysoev.ru
68163Sigor@sysoev.ru /* NXT_MP_CLUSTER_BLOCK type is zero. */
68263Sigor@sysoev.ru
68363Sigor@sysoev.ru cluster->size = mp->cluster_size;
68463Sigor@sysoev.ru
68563Sigor@sysoev.ru cluster->start = nxt_memalign(mp->page_alignment, mp->cluster_size);
68663Sigor@sysoev.ru if (nxt_slow_path(cluster->start == NULL)) {
68763Sigor@sysoev.ru nxt_free(cluster);
68863Sigor@sysoev.ru return NULL;
68963Sigor@sysoev.ru }
69063Sigor@sysoev.ru
69163Sigor@sysoev.ru n--;
69263Sigor@sysoev.ru cluster->pages[n].number = n;
69363Sigor@sysoev.ru nxt_queue_insert_head(&mp->free_pages, &cluster->pages[n].link);
69463Sigor@sysoev.ru
69563Sigor@sysoev.ru while (n != 0) {
69663Sigor@sysoev.ru n--;
69763Sigor@sysoev.ru cluster->pages[n].number = n;
69863Sigor@sysoev.ru nxt_queue_insert_before(&cluster->pages[n + 1].link,
69963Sigor@sysoev.ru &cluster->pages[n].link);
70063Sigor@sysoev.ru }
70163Sigor@sysoev.ru
70263Sigor@sysoev.ru nxt_rbtree_insert(&mp->blocks, &cluster->node);
70363Sigor@sysoev.ru
70463Sigor@sysoev.ru return cluster;
70563Sigor@sysoev.ru }
70663Sigor@sysoev.ru
70763Sigor@sysoev.ru #endif
70863Sigor@sysoev.ru
70963Sigor@sysoev.ru
71063Sigor@sysoev.ru static void *
nxt_mp_alloc_large(nxt_mp_t * mp,size_t alignment,size_t size,nxt_bool_t freeable)711653Sigor@sysoev.ru nxt_mp_alloc_large(nxt_mp_t *mp, size_t alignment, size_t size,
712653Sigor@sysoev.ru nxt_bool_t freeable)
71363Sigor@sysoev.ru {
71463Sigor@sysoev.ru u_char *p;
71563Sigor@sysoev.ru size_t aligned_size;
71663Sigor@sysoev.ru uint8_t type;
71763Sigor@sysoev.ru nxt_mp_block_t *block;
71863Sigor@sysoev.ru
719128Smax.romanov@nginx.com nxt_mp_thread_assert(mp);
720128Smax.romanov@nginx.com
72163Sigor@sysoev.ru /* Allocation must be less than 4G. */
72263Sigor@sysoev.ru if (nxt_slow_path(size >= 0xFFFFFFFF)) {
72363Sigor@sysoev.ru return NULL;
72463Sigor@sysoev.ru }
72563Sigor@sysoev.ru
72663Sigor@sysoev.ru if (nxt_is_power_of_two(size)) {
72763Sigor@sysoev.ru block = nxt_malloc(sizeof(nxt_mp_block_t));
72863Sigor@sysoev.ru if (nxt_slow_path(block == NULL)) {
72963Sigor@sysoev.ru return NULL;
73063Sigor@sysoev.ru }
73163Sigor@sysoev.ru
73263Sigor@sysoev.ru p = nxt_memalign(alignment, size);
73363Sigor@sysoev.ru if (nxt_slow_path(p == NULL)) {
73463Sigor@sysoev.ru nxt_free(block);
73563Sigor@sysoev.ru return NULL;
73663Sigor@sysoev.ru }
73763Sigor@sysoev.ru
73863Sigor@sysoev.ru type = NXT_MP_DISCRETE_BLOCK;
73963Sigor@sysoev.ru
74063Sigor@sysoev.ru } else {
74163Sigor@sysoev.ru aligned_size = nxt_align_size(size, sizeof(uintptr_t));
74263Sigor@sysoev.ru
74363Sigor@sysoev.ru p = nxt_memalign(alignment, aligned_size + sizeof(nxt_mp_block_t));
74463Sigor@sysoev.ru if (nxt_slow_path(p == NULL)) {
74563Sigor@sysoev.ru return NULL;
74663Sigor@sysoev.ru }
74763Sigor@sysoev.ru
74863Sigor@sysoev.ru block = (nxt_mp_block_t *) (p + aligned_size);
74963Sigor@sysoev.ru type = NXT_MP_EMBEDDED_BLOCK;
75063Sigor@sysoev.ru }
75163Sigor@sysoev.ru
75263Sigor@sysoev.ru block->type = type;
753653Sigor@sysoev.ru block->freeable = freeable;
75463Sigor@sysoev.ru block->size = size;
75563Sigor@sysoev.ru block->start = p;
75663Sigor@sysoev.ru
75763Sigor@sysoev.ru nxt_rbtree_insert(&mp->blocks, &block->node);
75863Sigor@sysoev.ru
75963Sigor@sysoev.ru return p;
76063Sigor@sysoev.ru }
76163Sigor@sysoev.ru
76263Sigor@sysoev.ru
76363Sigor@sysoev.ru static intptr_t
nxt_mp_rbtree_compare(nxt_rbtree_node_t * node1,nxt_rbtree_node_t * node2)76463Sigor@sysoev.ru nxt_mp_rbtree_compare(nxt_rbtree_node_t *node1, nxt_rbtree_node_t *node2)
76563Sigor@sysoev.ru {
76663Sigor@sysoev.ru nxt_mp_block_t *block1, *block2;
76763Sigor@sysoev.ru
76863Sigor@sysoev.ru block1 = (nxt_mp_block_t *) node1;
76963Sigor@sysoev.ru block2 = (nxt_mp_block_t *) node2;
77063Sigor@sysoev.ru
771832Svbart@nginx.com /*
772832Svbart@nginx.com * Shifting is necessary to prevent overflow of intptr_t when block1->start
773832Svbart@nginx.com * is much greater than block2->start or vice versa.
774832Svbart@nginx.com *
775832Svbart@nginx.com * It is safe to drop one bit since there cannot be adjacent addresses
776832Svbart@nginx.com * because of alignments and allocation sizes. Effectively this reduces
777832Svbart@nginx.com * the absolute values to fit into the magnitude of intptr_t.
778832Svbart@nginx.com */
779832Svbart@nginx.com return ((uintptr_t) block1->start >> 1) - ((uintptr_t) block2->start >> 1);
78063Sigor@sysoev.ru }
78163Sigor@sysoev.ru
78263Sigor@sysoev.ru
78363Sigor@sysoev.ru void
nxt_mp_free(nxt_mp_t * mp,void * p)78463Sigor@sysoev.ru nxt_mp_free(nxt_mp_t *mp, void *p)
78563Sigor@sysoev.ru {
78663Sigor@sysoev.ru const char *err;
78763Sigor@sysoev.ru nxt_mp_block_t *block;
78863Sigor@sysoev.ru
789128Smax.romanov@nginx.com nxt_mp_thread_assert(mp);
790128Smax.romanov@nginx.com
791145Smax.romanov@nginx.com nxt_debug_alloc("mp %p free(%p)", mp, p);
79263Sigor@sysoev.ru
79363Sigor@sysoev.ru block = nxt_mp_find_block(&mp->blocks, p);
79463Sigor@sysoev.ru
79563Sigor@sysoev.ru if (nxt_fast_path(block != NULL)) {
79663Sigor@sysoev.ru
79763Sigor@sysoev.ru if (block->type == NXT_MP_CLUSTER_BLOCK) {
79863Sigor@sysoev.ru err = nxt_mp_chunk_free(mp, block, p);
79963Sigor@sysoev.ru
80063Sigor@sysoev.ru if (nxt_fast_path(err == NULL)) {
80163Sigor@sysoev.ru return;
80263Sigor@sysoev.ru }
80363Sigor@sysoev.ru
80463Sigor@sysoev.ru } else if (nxt_fast_path(p == block->start)) {
805653Sigor@sysoev.ru
806653Sigor@sysoev.ru if (block->freeable) {
807653Sigor@sysoev.ru nxt_rbtree_delete(&mp->blocks, &block->node);
80863Sigor@sysoev.ru
809653Sigor@sysoev.ru if (block->type == NXT_MP_DISCRETE_BLOCK) {
810653Sigor@sysoev.ru nxt_free(block);
811653Sigor@sysoev.ru }
812653Sigor@sysoev.ru
813653Sigor@sysoev.ru nxt_free(p);
814653Sigor@sysoev.ru
815653Sigor@sysoev.ru return;
81663Sigor@sysoev.ru }
81763Sigor@sysoev.ru
818653Sigor@sysoev.ru err = "freed pointer points to non-freeable block: %p";
81963Sigor@sysoev.ru
82063Sigor@sysoev.ru } else {
82163Sigor@sysoev.ru err = "freed pointer points to middle of block: %p";
82263Sigor@sysoev.ru }
82363Sigor@sysoev.ru
82463Sigor@sysoev.ru } else {
82563Sigor@sysoev.ru err = "freed pointer is out of pool: %p";
82663Sigor@sysoev.ru }
82763Sigor@sysoev.ru
828564Svbart@nginx.com nxt_thread_log_alert(err, p);
82963Sigor@sysoev.ru }
83063Sigor@sysoev.ru
83163Sigor@sysoev.ru
83263Sigor@sysoev.ru static nxt_mp_block_t *
nxt_mp_find_block(nxt_rbtree_t * tree,const u_char * p)833*2139Sandrew@digital-domain.net nxt_mp_find_block(nxt_rbtree_t *tree, const u_char *p)
83463Sigor@sysoev.ru {
83563Sigor@sysoev.ru nxt_mp_block_t *block;
83663Sigor@sysoev.ru nxt_rbtree_node_t *node, *sentinel;
83763Sigor@sysoev.ru
83863Sigor@sysoev.ru node = nxt_rbtree_root(tree);
83963Sigor@sysoev.ru sentinel = nxt_rbtree_sentinel(tree);
84063Sigor@sysoev.ru
84163Sigor@sysoev.ru while (node != sentinel) {
84263Sigor@sysoev.ru
84363Sigor@sysoev.ru block = (nxt_mp_block_t *) node;
84463Sigor@sysoev.ru
84563Sigor@sysoev.ru if (p < block->start) {
84663Sigor@sysoev.ru node = node->left;
84763Sigor@sysoev.ru
84863Sigor@sysoev.ru } else if (p >= block->start + block->size) {
84963Sigor@sysoev.ru node = node->right;
85063Sigor@sysoev.ru
85163Sigor@sysoev.ru } else {
85263Sigor@sysoev.ru return block;
85363Sigor@sysoev.ru }
85463Sigor@sysoev.ru }
85563Sigor@sysoev.ru
85663Sigor@sysoev.ru return NULL;
85763Sigor@sysoev.ru }
85863Sigor@sysoev.ru
85963Sigor@sysoev.ru
86063Sigor@sysoev.ru static const char *
nxt_mp_chunk_free(nxt_mp_t * mp,nxt_mp_block_t * cluster,u_char * p)86163Sigor@sysoev.ru nxt_mp_chunk_free(nxt_mp_t *mp, nxt_mp_block_t *cluster, u_char *p)
86263Sigor@sysoev.ru {
86363Sigor@sysoev.ru u_char *start;
86463Sigor@sysoev.ru uintptr_t offset;
86563Sigor@sysoev.ru nxt_uint_t n, size, chunk;
86663Sigor@sysoev.ru nxt_queue_t *chunk_pages;
86763Sigor@sysoev.ru nxt_mp_page_t *page;
86863Sigor@sysoev.ru
86963Sigor@sysoev.ru n = (p - cluster->start) >> mp->page_size_shift;
87063Sigor@sysoev.ru start = cluster->start + (n << mp->page_size_shift);
87163Sigor@sysoev.ru
87263Sigor@sysoev.ru page = &cluster->pages[n];
87363Sigor@sysoev.ru
87463Sigor@sysoev.ru if (nxt_slow_path(page->size == 0)) {
87563Sigor@sysoev.ru return "freed pointer points to already free page: %p";
87663Sigor@sysoev.ru }
87763Sigor@sysoev.ru
87863Sigor@sysoev.ru if (nxt_slow_path(page->size == 0xFF)) {
879653Sigor@sysoev.ru return "freed pointer points to non-freeable page: %p";
88063Sigor@sysoev.ru }
88163Sigor@sysoev.ru
88263Sigor@sysoev.ru size = page->size << mp->chunk_size_shift;
88363Sigor@sysoev.ru
88463Sigor@sysoev.ru if (size != mp->page_size) {
88563Sigor@sysoev.ru
88663Sigor@sysoev.ru offset = (uintptr_t) (p - start) & (mp->page_size - 1);
88763Sigor@sysoev.ru chunk = offset / size;
88863Sigor@sysoev.ru
88963Sigor@sysoev.ru if (nxt_slow_path(offset != chunk * size)) {
89063Sigor@sysoev.ru return "freed pointer points to wrong chunk: %p";
89163Sigor@sysoev.ru }
89263Sigor@sysoev.ru
89363Sigor@sysoev.ru if (nxt_slow_path(nxt_mp_chunk_is_free(page->u.map, chunk))) {
89463Sigor@sysoev.ru return "freed pointer points to already free chunk: %p";
89563Sigor@sysoev.ru }
89663Sigor@sysoev.ru
89763Sigor@sysoev.ru nxt_mp_chunk_set_free(page->u.map, chunk);
89863Sigor@sysoev.ru
89963Sigor@sysoev.ru if (page->u.map != 0xFFFFFFFF) {
90063Sigor@sysoev.ru page->chunks++;
90163Sigor@sysoev.ru
90263Sigor@sysoev.ru if (page->chunks == 1) {
90363Sigor@sysoev.ru /*
90463Sigor@sysoev.ru * Add the page to the head of pool chunk pages list
90563Sigor@sysoev.ru * of pages with free chunks.
90663Sigor@sysoev.ru */
90763Sigor@sysoev.ru n = nxt_mp_chunk_pages_index(mp, size);
90863Sigor@sysoev.ru chunk_pages = &mp->chunk_pages[n];
90963Sigor@sysoev.ru
91063Sigor@sysoev.ru nxt_queue_insert_head(chunk_pages, &page->link);
91163Sigor@sysoev.ru }
91263Sigor@sysoev.ru
91363Sigor@sysoev.ru nxt_mp_free_junk(p, size);
91463Sigor@sysoev.ru
91563Sigor@sysoev.ru return NULL;
91663Sigor@sysoev.ru
91763Sigor@sysoev.ru } else {
91863Sigor@sysoev.ru /*
91963Sigor@sysoev.ru * All chunks are free, remove the page from pool
92063Sigor@sysoev.ru * chunk pages list of pages with free chunks.
92163Sigor@sysoev.ru */
92263Sigor@sysoev.ru nxt_queue_remove(&page->link);
92363Sigor@sysoev.ru }
92463Sigor@sysoev.ru
92563Sigor@sysoev.ru } else if (nxt_slow_path(p != start)) {
92663Sigor@sysoev.ru return "invalid pointer to chunk: %p";
92763Sigor@sysoev.ru }
92863Sigor@sysoev.ru
92963Sigor@sysoev.ru /* Add the free page to the pool's free pages tree. */
93063Sigor@sysoev.ru
93163Sigor@sysoev.ru page->size = 0;
93263Sigor@sysoev.ru nxt_queue_insert_head(&mp->free_pages, &page->link);
93363Sigor@sysoev.ru
93463Sigor@sysoev.ru nxt_mp_free_junk(p, size);
93563Sigor@sysoev.ru
93663Sigor@sysoev.ru /* Test if all pages in the cluster are free. */
93763Sigor@sysoev.ru
93863Sigor@sysoev.ru n = mp->cluster_size >> mp->page_size_shift;
93963Sigor@sysoev.ru page = cluster->pages;
94063Sigor@sysoev.ru
94163Sigor@sysoev.ru do {
9422078Salx.manpages@gmail.com if (page->size != 0) {
9432078Salx.manpages@gmail.com return NULL;
9442078Salx.manpages@gmail.com }
94563Sigor@sysoev.ru
9462078Salx.manpages@gmail.com page++;
9472078Salx.manpages@gmail.com n--;
94863Sigor@sysoev.ru } while (n != 0);
94963Sigor@sysoev.ru
95063Sigor@sysoev.ru /* Free cluster. */
95163Sigor@sysoev.ru
95263Sigor@sysoev.ru n = mp->cluster_size >> mp->page_size_shift;
95363Sigor@sysoev.ru page = cluster->pages;
95463Sigor@sysoev.ru
95563Sigor@sysoev.ru do {
9562078Salx.manpages@gmail.com nxt_queue_remove(&page->link);
9572078Salx.manpages@gmail.com page++;
9582078Salx.manpages@gmail.com n--;
95963Sigor@sysoev.ru } while (n != 0);
96063Sigor@sysoev.ru
96163Sigor@sysoev.ru nxt_rbtree_delete(&mp->blocks, &cluster->node);
96263Sigor@sysoev.ru
96363Sigor@sysoev.ru p = cluster->start;
96463Sigor@sysoev.ru
96563Sigor@sysoev.ru nxt_free(cluster);
96663Sigor@sysoev.ru nxt_free(p);
96763Sigor@sysoev.ru
96863Sigor@sysoev.ru return NULL;
96963Sigor@sysoev.ru }
97063Sigor@sysoev.ru
97163Sigor@sysoev.ru
97263Sigor@sysoev.ru void *
nxt_mp_nget(nxt_mp_t * mp,size_t size)97363Sigor@sysoev.ru nxt_mp_nget(nxt_mp_t *mp, size_t size)
97463Sigor@sysoev.ru {
975145Smax.romanov@nginx.com void *p;
97663Sigor@sysoev.ru
97763Sigor@sysoev.ru #if !(NXT_DEBUG_MEMORY)
97863Sigor@sysoev.ru
97963Sigor@sysoev.ru if (size <= mp->page_size) {
980145Smax.romanov@nginx.com p = nxt_mp_get_small(mp, &mp->nget_pages, size);
981145Smax.romanov@nginx.com
982145Smax.romanov@nginx.com } else {
983653Sigor@sysoev.ru p = nxt_mp_alloc_large(mp, NXT_MAX_ALIGNMENT, size, 0);
984147Svbart@nginx.com }
985145Smax.romanov@nginx.com
986147Svbart@nginx.com #else
987145Smax.romanov@nginx.com
988653Sigor@sysoev.ru p = nxt_mp_alloc_large(mp, NXT_MAX_ALIGNMENT, size, 0);
989145Smax.romanov@nginx.com
99063Sigor@sysoev.ru #endif
99163Sigor@sysoev.ru
992145Smax.romanov@nginx.com nxt_debug_alloc("mp %p nget(%uz): %p", mp, size, p);
993145Smax.romanov@nginx.com
994145Smax.romanov@nginx.com return p;
99563Sigor@sysoev.ru }
99663Sigor@sysoev.ru
99763Sigor@sysoev.ru
99863Sigor@sysoev.ru void *
nxt_mp_get(nxt_mp_t * mp,size_t size)99963Sigor@sysoev.ru nxt_mp_get(nxt_mp_t *mp, size_t size)
100063Sigor@sysoev.ru {
1001145Smax.romanov@nginx.com void *p;
100263Sigor@sysoev.ru
100363Sigor@sysoev.ru #if !(NXT_DEBUG_MEMORY)
100463Sigor@sysoev.ru
100563Sigor@sysoev.ru if (size <= mp->page_size) {
100663Sigor@sysoev.ru size = nxt_max(size, NXT_MAX_ALIGNMENT);
1007145Smax.romanov@nginx.com p = nxt_mp_get_small(mp, &mp->get_pages, size);
1008145Smax.romanov@nginx.com
1009145Smax.romanov@nginx.com } else {
1010653Sigor@sysoev.ru p = nxt_mp_alloc_large(mp, NXT_MAX_ALIGNMENT, size, 0);
1011147Svbart@nginx.com }
1012145Smax.romanov@nginx.com
1013147Svbart@nginx.com #else
1014145Smax.romanov@nginx.com
1015653Sigor@sysoev.ru p = nxt_mp_alloc_large(mp, NXT_MAX_ALIGNMENT, size, 0);
1016145Smax.romanov@nginx.com
101763Sigor@sysoev.ru #endif
101863Sigor@sysoev.ru
1019145Smax.romanov@nginx.com nxt_debug_alloc("mp %p get(%uz): %p", mp, size, p);
1020145Smax.romanov@nginx.com
1021145Smax.romanov@nginx.com return p;
102263Sigor@sysoev.ru }
102363Sigor@sysoev.ru
102463Sigor@sysoev.ru
102563Sigor@sysoev.ru void *
nxt_mp_zget(nxt_mp_t * mp,size_t size)102663Sigor@sysoev.ru nxt_mp_zget(nxt_mp_t *mp, size_t size)
102763Sigor@sysoev.ru {
102863Sigor@sysoev.ru void *p;
102963Sigor@sysoev.ru
103063Sigor@sysoev.ru p = nxt_mp_get(mp, size);
103163Sigor@sysoev.ru
103263Sigor@sysoev.ru if (nxt_fast_path(p != NULL)) {
103363Sigor@sysoev.ru memset(p, 0, size);
103463Sigor@sysoev.ru }
103563Sigor@sysoev.ru
103663Sigor@sysoev.ru return p;
103763Sigor@sysoev.ru }
1038164Smax.romanov@nginx.com
1039164Smax.romanov@nginx.com
1040164Smax.romanov@nginx.com nxt_int_t
nxt_mp_cleanup(nxt_mp_t * mp,nxt_work_handler_t handler,nxt_task_t * task,void * obj,void * data)1041164Smax.romanov@nginx.com nxt_mp_cleanup(nxt_mp_t *mp, nxt_work_handler_t handler,
1042164Smax.romanov@nginx.com nxt_task_t *task, void *obj, void *data)
1043164Smax.romanov@nginx.com {
1044164Smax.romanov@nginx.com nxt_work_t *work;
1045164Smax.romanov@nginx.com
1046164Smax.romanov@nginx.com work = nxt_mp_get(mp, sizeof(nxt_work_t));
1047164Smax.romanov@nginx.com
1048164Smax.romanov@nginx.com if (nxt_slow_path(work == NULL)) {
1049164Smax.romanov@nginx.com return NXT_ERROR;
1050164Smax.romanov@nginx.com }
1051164Smax.romanov@nginx.com
1052164Smax.romanov@nginx.com work->next = mp->cleanup;
1053164Smax.romanov@nginx.com work->handler = handler;
1054164Smax.romanov@nginx.com work->task = task;
1055164Smax.romanov@nginx.com work->obj = obj;
1056164Smax.romanov@nginx.com work->data = data;
1057164Smax.romanov@nginx.com
1058164Smax.romanov@nginx.com mp->cleanup = work;
1059164Smax.romanov@nginx.com
1060164Smax.romanov@nginx.com return NXT_OK;
1061164Smax.romanov@nginx.com }
10621563Svbart@nginx.com
10631563Svbart@nginx.com
10641563Svbart@nginx.com void *
nxt_mp_lvlhsh_alloc(void * pool,size_t size)10651563Svbart@nginx.com nxt_mp_lvlhsh_alloc(void *pool, size_t size)
10661563Svbart@nginx.com {
10671563Svbart@nginx.com return nxt_mp_align(pool, size, size);
10681563Svbart@nginx.com }
10691563Svbart@nginx.com
10701563Svbart@nginx.com
10711563Svbart@nginx.com void
nxt_mp_lvlhsh_free(void * pool,void * p)10721563Svbart@nginx.com nxt_mp_lvlhsh_free(void *pool, void *p)
10731563Svbart@nginx.com {
10741563Svbart@nginx.com nxt_mp_free(pool, p);
10751563Svbart@nginx.com }
1076