xref: /unit/src/nxt_mp.c (revision 2139:99d792169ffb)
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