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