xref: /unit/src/nxt_mem_zone.c (revision 0)
1*0Sigor@sysoev.ru 
2*0Sigor@sysoev.ru /*
3*0Sigor@sysoev.ru  * Copyright (C) Igor Sysoev
4*0Sigor@sysoev.ru  * Copyright (C) NGINX, Inc.
5*0Sigor@sysoev.ru  */
6*0Sigor@sysoev.ru 
7*0Sigor@sysoev.ru #include <nxt_main.h>
8*0Sigor@sysoev.ru 
9*0Sigor@sysoev.ru 
10*0Sigor@sysoev.ru #define NXT_MEM_ZONE_PAGE_FREE      0
11*0Sigor@sysoev.ru /*
12*0Sigor@sysoev.ru  * A page was never allocated before so it should be filled with
13*0Sigor@sysoev.ru  * junk on the first time allocation if memory debugging is enabled.
14*0Sigor@sysoev.ru  */
15*0Sigor@sysoev.ru #define NXT_MEM_ZONE_PAGE_FRESH     1
16*0Sigor@sysoev.ru 
17*0Sigor@sysoev.ru /* An entire page is currently used, no chunks inside the page. */
18*0Sigor@sysoev.ru #define NXT_MEM_ZONE_PAGE_USED      2
19*0Sigor@sysoev.ru 
20*0Sigor@sysoev.ru 
21*0Sigor@sysoev.ru typedef struct nxt_mem_zone_page_s  nxt_mem_zone_page_t;
22*0Sigor@sysoev.ru 
23*0Sigor@sysoev.ru struct nxt_mem_zone_page_s {
24*0Sigor@sysoev.ru     /*
25*0Sigor@sysoev.ru      * A size of page chunks if value is greater than or equal to 16.
26*0Sigor@sysoev.ru      * Otherwise it is used to mark page state: NXT_MEM_ZONE_PAGE_FREE,
27*0Sigor@sysoev.ru      * NXT_MEM_ZONE_PAGE_FRESH, and NXT_MEM_ZONE_PAGE_USED.
28*0Sigor@sysoev.ru      */
29*0Sigor@sysoev.ru     uint16_t               size;
30*0Sigor@sysoev.ru 
31*0Sigor@sysoev.ru     /* A number of free chunks of a chunked page. */
32*0Sigor@sysoev.ru     uint16_t               chunks;
33*0Sigor@sysoev.ru 
34*0Sigor@sysoev.ru     union {
35*0Sigor@sysoev.ru         /* A chunk bitmap if a number of chunks is lesser than 32. */
36*0Sigor@sysoev.ru         uint8_t            map[4];
37*0Sigor@sysoev.ru         /*
38*0Sigor@sysoev.ru          * The count is a number of successive occupied pages in the first
39*0Sigor@sysoev.ru          * page.  In the next occupied pages and in all free pages the count
40*0Sigor@sysoev.ru          * is zero, because a number of successive free pages is stored in
41*0Sigor@sysoev.ru          * free block size resided in beginning of the first free page.
42*0Sigor@sysoev.ru          */
43*0Sigor@sysoev.ru         uint32_t           count;
44*0Sigor@sysoev.ru     } u;
45*0Sigor@sysoev.ru 
46*0Sigor@sysoev.ru     /* Used for slot list of pages with free chunks. */
47*0Sigor@sysoev.ru     nxt_mem_zone_page_t    *next;
48*0Sigor@sysoev.ru 
49*0Sigor@sysoev.ru     /*
50*0Sigor@sysoev.ru      * Used to link of all pages including free, chunked and occupied
51*0Sigor@sysoev.ru      * pages to coalesce free pages.
52*0Sigor@sysoev.ru      */
53*0Sigor@sysoev.ru     nxt_queue_link_t       link;
54*0Sigor@sysoev.ru };
55*0Sigor@sysoev.ru 
56*0Sigor@sysoev.ru 
57*0Sigor@sysoev.ru typedef struct {
58*0Sigor@sysoev.ru     uint32_t               size;
59*0Sigor@sysoev.ru     uint32_t               chunks;
60*0Sigor@sysoev.ru     uint32_t               start;
61*0Sigor@sysoev.ru     uint32_t               map_size;
62*0Sigor@sysoev.ru     nxt_mem_zone_page_t    *pages;
63*0Sigor@sysoev.ru } nxt_mem_zone_slot_t;
64*0Sigor@sysoev.ru 
65*0Sigor@sysoev.ru 
66*0Sigor@sysoev.ru typedef struct {
67*0Sigor@sysoev.ru     NXT_RBTREE_NODE        (node);
68*0Sigor@sysoev.ru     uint32_t               size;
69*0Sigor@sysoev.ru } nxt_mem_zone_free_block_t;
70*0Sigor@sysoev.ru 
71*0Sigor@sysoev.ru 
72*0Sigor@sysoev.ru struct nxt_mem_zone_s {
73*0Sigor@sysoev.ru     nxt_thread_spinlock_t  lock;
74*0Sigor@sysoev.ru     nxt_mem_zone_page_t    *pages;
75*0Sigor@sysoev.ru     nxt_mem_zone_page_t    sentinel_page;
76*0Sigor@sysoev.ru     nxt_rbtree_t           free_pages;
77*0Sigor@sysoev.ru 
78*0Sigor@sysoev.ru     uint32_t               page_size_shift;
79*0Sigor@sysoev.ru     uint32_t               page_size_mask;
80*0Sigor@sysoev.ru     uint32_t               max_chunk_size;
81*0Sigor@sysoev.ru     uint32_t               small_bitmap_min_size;
82*0Sigor@sysoev.ru 
83*0Sigor@sysoev.ru     u_char                 *start;
84*0Sigor@sysoev.ru     u_char                 *end;
85*0Sigor@sysoev.ru 
86*0Sigor@sysoev.ru     nxt_mem_zone_slot_t    slots[];
87*0Sigor@sysoev.ru };
88*0Sigor@sysoev.ru 
89*0Sigor@sysoev.ru 
90*0Sigor@sysoev.ru #define                                                                       \
91*0Sigor@sysoev.ru nxt_mem_zone_page_addr(zone, page)                                            \
92*0Sigor@sysoev.ru     (void *) (zone->start + ((page - zone->pages) << zone->page_size_shift))
93*0Sigor@sysoev.ru 
94*0Sigor@sysoev.ru 
95*0Sigor@sysoev.ru #define                                                                       \
96*0Sigor@sysoev.ru nxt_mem_zone_addr_page(zone, addr)                                            \
97*0Sigor@sysoev.ru     &zone->pages[((u_char *) addr - zone->start) >> zone->page_size_shift]
98*0Sigor@sysoev.ru 
99*0Sigor@sysoev.ru 
100*0Sigor@sysoev.ru #define                                                                       \
101*0Sigor@sysoev.ru nxt_mem_zone_page_is_free(page)                                               \
102*0Sigor@sysoev.ru     (page->size < NXT_MEM_ZONE_PAGE_USED)
103*0Sigor@sysoev.ru 
104*0Sigor@sysoev.ru 
105*0Sigor@sysoev.ru #define                                                                       \
106*0Sigor@sysoev.ru nxt_mem_zone_page_is_chunked(page)                                            \
107*0Sigor@sysoev.ru     (page->size >= 16)
108*0Sigor@sysoev.ru 
109*0Sigor@sysoev.ru 
110*0Sigor@sysoev.ru #define                                                                       \
111*0Sigor@sysoev.ru nxt_mem_zone_page_bitmap(zone, slot)                                          \
112*0Sigor@sysoev.ru     (slot->size < zone->small_bitmap_min_size)
113*0Sigor@sysoev.ru 
114*0Sigor@sysoev.ru 
115*0Sigor@sysoev.ru #define                                                                       \
116*0Sigor@sysoev.ru nxt_mem_zone_set_chunk_free(map, chunk)                                       \
117*0Sigor@sysoev.ru     map[chunk / 8] &= ~(0x80 >> (chunk & 7))
118*0Sigor@sysoev.ru 
119*0Sigor@sysoev.ru 
120*0Sigor@sysoev.ru #define                                                                       \
121*0Sigor@sysoev.ru nxt_mem_zone_chunk_is_free(map, chunk)                                        \
122*0Sigor@sysoev.ru     ((map[chunk / 8] & (0x80 >> (chunk & 7))) == 0)
123*0Sigor@sysoev.ru 
124*0Sigor@sysoev.ru 
125*0Sigor@sysoev.ru #define                                                                       \
126*0Sigor@sysoev.ru nxt_mem_zone_fresh_junk(p, size)                                              \
127*0Sigor@sysoev.ru     nxt_memset((p), 0xA5, size)
128*0Sigor@sysoev.ru 
129*0Sigor@sysoev.ru 
130*0Sigor@sysoev.ru #define                                                                       \
131*0Sigor@sysoev.ru nxt_mem_zone_free_junk(p, size)                                               \
132*0Sigor@sysoev.ru     nxt_memset((p), 0x5A, size)
133*0Sigor@sysoev.ru 
134*0Sigor@sysoev.ru 
135*0Sigor@sysoev.ru static uint32_t nxt_mem_zone_pages(u_char *start, size_t zone_size,
136*0Sigor@sysoev.ru     nxt_uint_t page_size);
137*0Sigor@sysoev.ru static void *nxt_mem_zone_slots_init(nxt_mem_zone_t *zone,
138*0Sigor@sysoev.ru     nxt_uint_t page_size);
139*0Sigor@sysoev.ru static void nxt_mem_zone_slot_init(nxt_mem_zone_slot_t *slot,
140*0Sigor@sysoev.ru     nxt_uint_t page_size);
141*0Sigor@sysoev.ru static nxt_int_t nxt_mem_zone_rbtree_compare(nxt_rbtree_node_t *node1,
142*0Sigor@sysoev.ru     nxt_rbtree_node_t *node2);
143*0Sigor@sysoev.ru static void *nxt_mem_zone_alloc_small(nxt_mem_zone_t *zone,
144*0Sigor@sysoev.ru     nxt_mem_zone_slot_t *slot, size_t size);
145*0Sigor@sysoev.ru static nxt_uint_t nxt_mem_zone_alloc_chunk(uint8_t *map, nxt_uint_t offset,
146*0Sigor@sysoev.ru     nxt_uint_t size);
147*0Sigor@sysoev.ru static void *nxt_mem_zone_alloc_large(nxt_mem_zone_t *zone, size_t alignment,
148*0Sigor@sysoev.ru     size_t size);
149*0Sigor@sysoev.ru static nxt_mem_zone_page_t *nxt_mem_zone_alloc_pages(nxt_mem_zone_t *zone,
150*0Sigor@sysoev.ru     size_t alignment, uint32_t pages);
151*0Sigor@sysoev.ru static nxt_mem_zone_free_block_t *
152*0Sigor@sysoev.ru     nxt_mem_zone_find_free_block(nxt_mem_zone_t *zone, nxt_rbtree_node_t *node,
153*0Sigor@sysoev.ru     uint32_t alignment, uint32_t pages);
154*0Sigor@sysoev.ru static const char *nxt_mem_zone_free_chunk(nxt_mem_zone_t *zone,
155*0Sigor@sysoev.ru     nxt_mem_zone_page_t *page, void *p);
156*0Sigor@sysoev.ru static void nxt_mem_zone_free_pages(nxt_mem_zone_t *zone,
157*0Sigor@sysoev.ru     nxt_mem_zone_page_t *page, nxt_uint_t count);
158*0Sigor@sysoev.ru 
159*0Sigor@sysoev.ru 
160*0Sigor@sysoev.ru static nxt_log_moderation_t  nxt_mem_zone_log_moderation = {
161*0Sigor@sysoev.ru     NXT_LOG_ALERT, 2, "mem_zone_alloc() failed, not enough memory",
162*0Sigor@sysoev.ru     NXT_LOG_MODERATION
163*0Sigor@sysoev.ru };
164*0Sigor@sysoev.ru 
165*0Sigor@sysoev.ru 
166*0Sigor@sysoev.ru nxt_mem_zone_t *
167*0Sigor@sysoev.ru nxt_mem_zone_init(u_char *start, size_t zone_size, nxt_uint_t page_size)
168*0Sigor@sysoev.ru {
169*0Sigor@sysoev.ru     uint32_t                   pages;
170*0Sigor@sysoev.ru     nxt_uint_t                 n;
171*0Sigor@sysoev.ru     nxt_mem_zone_t             *zone;
172*0Sigor@sysoev.ru     nxt_mem_zone_page_t        *page;
173*0Sigor@sysoev.ru     nxt_mem_zone_free_block_t  *block;
174*0Sigor@sysoev.ru 
175*0Sigor@sysoev.ru     if (nxt_slow_path((page_size & (page_size - 1)) != 0)) {
176*0Sigor@sysoev.ru         nxt_thread_log_alert("mem zone page size must be a power of 2");
177*0Sigor@sysoev.ru         return NULL;
178*0Sigor@sysoev.ru     }
179*0Sigor@sysoev.ru 
180*0Sigor@sysoev.ru     pages = nxt_mem_zone_pages(start, zone_size, page_size);
181*0Sigor@sysoev.ru     if (pages == 0) {
182*0Sigor@sysoev.ru         return NULL;
183*0Sigor@sysoev.ru     }
184*0Sigor@sysoev.ru 
185*0Sigor@sysoev.ru     zone = (nxt_mem_zone_t *) start;
186*0Sigor@sysoev.ru 
187*0Sigor@sysoev.ru     /* The function returns address after all slots. */
188*0Sigor@sysoev.ru     page = nxt_mem_zone_slots_init(zone, page_size);
189*0Sigor@sysoev.ru 
190*0Sigor@sysoev.ru     zone->pages = page;
191*0Sigor@sysoev.ru 
192*0Sigor@sysoev.ru     for (n = 0; n < pages; n++) {
193*0Sigor@sysoev.ru         page[n].size = NXT_MEM_ZONE_PAGE_FRESH;
194*0Sigor@sysoev.ru     }
195*0Sigor@sysoev.ru 
196*0Sigor@sysoev.ru     /*
197*0Sigor@sysoev.ru      * A special sentinel page entry marked as used does not correspond
198*0Sigor@sysoev.ru      * to a real page.  The entry simplifies neighbour queue nodes check
199*0Sigor@sysoev.ru      * in nxt_mem_zone_free_pages().
200*0Sigor@sysoev.ru      */
201*0Sigor@sysoev.ru     zone->sentinel_page.size = NXT_MEM_ZONE_PAGE_USED;
202*0Sigor@sysoev.ru     nxt_queue_sentinel(&zone->sentinel_page.link);
203*0Sigor@sysoev.ru     nxt_queue_insert_after(&zone->sentinel_page.link, &page->link);
204*0Sigor@sysoev.ru 
205*0Sigor@sysoev.ru     /* rbtree of free pages. */
206*0Sigor@sysoev.ru 
207*0Sigor@sysoev.ru     nxt_rbtree_init(&zone->free_pages, nxt_mem_zone_rbtree_compare, NULL);
208*0Sigor@sysoev.ru 
209*0Sigor@sysoev.ru     block = (nxt_mem_zone_free_block_t *) zone->start;
210*0Sigor@sysoev.ru     block->size = pages;
211*0Sigor@sysoev.ru 
212*0Sigor@sysoev.ru     nxt_rbtree_insert(&zone->free_pages, &block->node);
213*0Sigor@sysoev.ru 
214*0Sigor@sysoev.ru     return zone;
215*0Sigor@sysoev.ru }
216*0Sigor@sysoev.ru 
217*0Sigor@sysoev.ru 
218*0Sigor@sysoev.ru static uint32_t
219*0Sigor@sysoev.ru nxt_mem_zone_pages(u_char *start, size_t zone_size, nxt_uint_t page_size)
220*0Sigor@sysoev.ru {
221*0Sigor@sysoev.ru     u_char          *end;
222*0Sigor@sysoev.ru     size_t          reserved;
223*0Sigor@sysoev.ru     nxt_uint_t      n, pages, size, chunks, last;
224*0Sigor@sysoev.ru     nxt_mem_zone_t  *zone;
225*0Sigor@sysoev.ru 
226*0Sigor@sysoev.ru     /*
227*0Sigor@sysoev.ru      * Find all maximum chunk sizes which zone page can be split on
228*0Sigor@sysoev.ru      * with minimum 16-byte step.
229*0Sigor@sysoev.ru      */
230*0Sigor@sysoev.ru     last = page_size / 16;
231*0Sigor@sysoev.ru     n = 0;
232*0Sigor@sysoev.ru     size = 32;
233*0Sigor@sysoev.ru 
234*0Sigor@sysoev.ru     do {
235*0Sigor@sysoev.ru         chunks = page_size / size;
236*0Sigor@sysoev.ru 
237*0Sigor@sysoev.ru         if (last != chunks) {
238*0Sigor@sysoev.ru             last = chunks;
239*0Sigor@sysoev.ru             n++;
240*0Sigor@sysoev.ru         }
241*0Sigor@sysoev.ru 
242*0Sigor@sysoev.ru         size += 16;
243*0Sigor@sysoev.ru 
244*0Sigor@sysoev.ru     } while (chunks > 1);
245*0Sigor@sysoev.ru 
246*0Sigor@sysoev.ru     /*
247*0Sigor@sysoev.ru      * Find number of usable zone pages except zone bookkeeping data,
248*0Sigor@sysoev.ru      * slots, and pages entries.
249*0Sigor@sysoev.ru      */
250*0Sigor@sysoev.ru     reserved = sizeof(nxt_mem_zone_t) + (n * sizeof(nxt_mem_zone_slot_t));
251*0Sigor@sysoev.ru 
252*0Sigor@sysoev.ru     end = nxt_trunc_ptr(start + zone_size, page_size);
253*0Sigor@sysoev.ru     zone_size = end - start;
254*0Sigor@sysoev.ru 
255*0Sigor@sysoev.ru     pages = (zone_size - reserved) / (page_size + sizeof(nxt_mem_zone_page_t));
256*0Sigor@sysoev.ru 
257*0Sigor@sysoev.ru     if (reserved > zone_size || pages == 0) {
258*0Sigor@sysoev.ru         nxt_thread_log_alert("mem zone size is too small: %uz", zone_size);
259*0Sigor@sysoev.ru         return 0;
260*0Sigor@sysoev.ru     }
261*0Sigor@sysoev.ru 
262*0Sigor@sysoev.ru     reserved += pages * sizeof(nxt_mem_zone_page_t);
263*0Sigor@sysoev.ru     nxt_memzero(start, reserved);
264*0Sigor@sysoev.ru 
265*0Sigor@sysoev.ru     zone = (nxt_mem_zone_t *) start;
266*0Sigor@sysoev.ru 
267*0Sigor@sysoev.ru     zone->start = nxt_align_ptr(start + reserved, page_size);
268*0Sigor@sysoev.ru     zone->end = end;
269*0Sigor@sysoev.ru 
270*0Sigor@sysoev.ru     nxt_thread_log_debug("mem zone pages: %uD, unused:%z", pages,
271*0Sigor@sysoev.ru                          end - (zone->start + pages * page_size));
272*0Sigor@sysoev.ru 
273*0Sigor@sysoev.ru     /*
274*0Sigor@sysoev.ru      * If a chunk size is lesser than zone->small_bitmap_min_size
275*0Sigor@sysoev.ru      * bytes, a page's chunk bitmap is larger than 32 bits and the
276*0Sigor@sysoev.ru      * bimap is placed at the start of the page.
277*0Sigor@sysoev.ru      */
278*0Sigor@sysoev.ru     zone->small_bitmap_min_size = page_size / 32;
279*0Sigor@sysoev.ru 
280*0Sigor@sysoev.ru     zone->page_size_mask = page_size - 1;
281*0Sigor@sysoev.ru     zone->max_chunk_size = page_size / 2;
282*0Sigor@sysoev.ru 
283*0Sigor@sysoev.ru     n = zone->max_chunk_size;
284*0Sigor@sysoev.ru 
285*0Sigor@sysoev.ru     do {
286*0Sigor@sysoev.ru         zone->page_size_shift++;
287*0Sigor@sysoev.ru         n /= 2;
288*0Sigor@sysoev.ru     } while (n != 0);
289*0Sigor@sysoev.ru 
290*0Sigor@sysoev.ru     return (uint32_t) pages;
291*0Sigor@sysoev.ru }
292*0Sigor@sysoev.ru 
293*0Sigor@sysoev.ru 
294*0Sigor@sysoev.ru static void *
295*0Sigor@sysoev.ru nxt_mem_zone_slots_init(nxt_mem_zone_t *zone, nxt_uint_t page_size)
296*0Sigor@sysoev.ru {
297*0Sigor@sysoev.ru     nxt_uint_t           n, size, chunks;
298*0Sigor@sysoev.ru     nxt_mem_zone_slot_t  *slot;
299*0Sigor@sysoev.ru 
300*0Sigor@sysoev.ru     slot = zone->slots;
301*0Sigor@sysoev.ru 
302*0Sigor@sysoev.ru     slot[0].chunks = page_size / 16;
303*0Sigor@sysoev.ru     slot[0].size = 16;
304*0Sigor@sysoev.ru 
305*0Sigor@sysoev.ru     n = 0;
306*0Sigor@sysoev.ru     size = 32;
307*0Sigor@sysoev.ru 
308*0Sigor@sysoev.ru     for ( ;; ) {
309*0Sigor@sysoev.ru         chunks = page_size / size;
310*0Sigor@sysoev.ru 
311*0Sigor@sysoev.ru         if (slot[n].chunks != chunks) {
312*0Sigor@sysoev.ru 
313*0Sigor@sysoev.ru             nxt_mem_zone_slot_init(&slot[n], page_size);
314*0Sigor@sysoev.ru 
315*0Sigor@sysoev.ru             nxt_thread_log_debug(
316*0Sigor@sysoev.ru                            "mem zone size:%uD chunks:%uD start:%uD map:%uD",
317*0Sigor@sysoev.ru                            slot[n].size, slot[n].chunks + 1,
318*0Sigor@sysoev.ru                            slot[n].start, slot[n].map_size);
319*0Sigor@sysoev.ru 
320*0Sigor@sysoev.ru             n++;
321*0Sigor@sysoev.ru 
322*0Sigor@sysoev.ru             if (chunks == 1) {
323*0Sigor@sysoev.ru                 return &slot[n];
324*0Sigor@sysoev.ru             }
325*0Sigor@sysoev.ru         }
326*0Sigor@sysoev.ru 
327*0Sigor@sysoev.ru         slot[n].chunks = chunks;
328*0Sigor@sysoev.ru         slot[n].size = size;
329*0Sigor@sysoev.ru         size += 16;
330*0Sigor@sysoev.ru     }
331*0Sigor@sysoev.ru }
332*0Sigor@sysoev.ru 
333*0Sigor@sysoev.ru 
334*0Sigor@sysoev.ru static void
335*0Sigor@sysoev.ru nxt_mem_zone_slot_init(nxt_mem_zone_slot_t *slot, nxt_uint_t page_size)
336*0Sigor@sysoev.ru {
337*0Sigor@sysoev.ru     /*
338*0Sigor@sysoev.ru      * Calculate number of bytes required to store a chunk bitmap
339*0Sigor@sysoev.ru      * and align it to 4 bytes.
340*0Sigor@sysoev.ru      */
341*0Sigor@sysoev.ru     slot->map_size = nxt_align_size(((slot->chunks + 7) / 8), 4);
342*0Sigor@sysoev.ru 
343*0Sigor@sysoev.ru     /* If chunk size is not a multiple of zone page size, there
344*0Sigor@sysoev.ru      * is surplus space which can be used for the chunk's bitmap.
345*0Sigor@sysoev.ru      */
346*0Sigor@sysoev.ru     slot->start = page_size - slot->chunks * slot->size;
347*0Sigor@sysoev.ru 
348*0Sigor@sysoev.ru     /* slot->chunks should be one less than actual number of chunks. */
349*0Sigor@sysoev.ru     slot->chunks--;
350*0Sigor@sysoev.ru 
351*0Sigor@sysoev.ru     if (slot->map_size > 4) {
352*0Sigor@sysoev.ru         /* A page's chunks bitmap is placed at the start of the page. */
353*0Sigor@sysoev.ru 
354*0Sigor@sysoev.ru         if (slot->start < slot->map_size) {
355*0Sigor@sysoev.ru             /*
356*0Sigor@sysoev.ru              * There is no surplus space or the space is too
357*0Sigor@sysoev.ru              * small for chunks bitmap, so use the first chunks.
358*0Sigor@sysoev.ru              */
359*0Sigor@sysoev.ru             if (slot->size < slot->map_size) {
360*0Sigor@sysoev.ru                 /* The first chunks are occupied by bitmap. */
361*0Sigor@sysoev.ru                 slot->chunks -= slot->map_size / slot->size;
362*0Sigor@sysoev.ru                 slot->start = nxt_align_size(slot->map_size, 16);
363*0Sigor@sysoev.ru 
364*0Sigor@sysoev.ru             } else {
365*0Sigor@sysoev.ru                 /* The first chunk is occupied by bitmap. */
366*0Sigor@sysoev.ru                 slot->chunks--;
367*0Sigor@sysoev.ru                 slot->start = slot->size;
368*0Sigor@sysoev.ru             }
369*0Sigor@sysoev.ru         }
370*0Sigor@sysoev.ru     }
371*0Sigor@sysoev.ru }
372*0Sigor@sysoev.ru 
373*0Sigor@sysoev.ru 
374*0Sigor@sysoev.ru /*
375*0Sigor@sysoev.ru  * Round up to the next highest power of 2.  The algorithm is
376*0Sigor@sysoev.ru  * described in "Bit Twiddling Hacks" by Sean Eron Anderson.
377*0Sigor@sysoev.ru  */
378*0Sigor@sysoev.ru 
379*0Sigor@sysoev.ru nxt_inline uint32_t
380*0Sigor@sysoev.ru nxt_next_highest_power_of_two(uint32_t n)
381*0Sigor@sysoev.ru {
382*0Sigor@sysoev.ru     n--;
383*0Sigor@sysoev.ru     n |= n >> 1;
384*0Sigor@sysoev.ru     n |= n >> 2;
385*0Sigor@sysoev.ru     n |= n >> 4;
386*0Sigor@sysoev.ru     n |= n >> 8;
387*0Sigor@sysoev.ru     n |= n >> 16;
388*0Sigor@sysoev.ru     n++;
389*0Sigor@sysoev.ru 
390*0Sigor@sysoev.ru     return n;
391*0Sigor@sysoev.ru }
392*0Sigor@sysoev.ru 
393*0Sigor@sysoev.ru 
394*0Sigor@sysoev.ru static nxt_int_t
395*0Sigor@sysoev.ru nxt_mem_zone_rbtree_compare(nxt_rbtree_node_t *node1, nxt_rbtree_node_t *node2)
396*0Sigor@sysoev.ru {
397*0Sigor@sysoev.ru     u_char                     *start1, *end1, *start2, *end2;
398*0Sigor@sysoev.ru     uint32_t                   n, size, size1, size2;
399*0Sigor@sysoev.ru     nxt_mem_zone_free_block_t  *block1, *block2;
400*0Sigor@sysoev.ru 
401*0Sigor@sysoev.ru     block1 = (nxt_mem_zone_free_block_t *) node1;
402*0Sigor@sysoev.ru     block2 = (nxt_mem_zone_free_block_t *) node2;
403*0Sigor@sysoev.ru 
404*0Sigor@sysoev.ru     size1 = block1->size;
405*0Sigor@sysoev.ru     size2 = block2->size;
406*0Sigor@sysoev.ru 
407*0Sigor@sysoev.ru     /*
408*0Sigor@sysoev.ru      * This subtractions do not overflow if number of pages of a free
409*0Sigor@sysoev.ru      * block is below 2^31-1.  This allows to use blocks up to 128G if
410*0Sigor@sysoev.ru      * a zone page size is just 64 bytes.
411*0Sigor@sysoev.ru      */
412*0Sigor@sysoev.ru     n = size1 - size2;
413*0Sigor@sysoev.ru 
414*0Sigor@sysoev.ru     if (n != 0) {
415*0Sigor@sysoev.ru         return n;
416*0Sigor@sysoev.ru     }
417*0Sigor@sysoev.ru 
418*0Sigor@sysoev.ru     /*
419*0Sigor@sysoev.ru      * Sort equally sized blocks by their capability to allocate memory with
420*0Sigor@sysoev.ru      * alignment equal to the size rounded the previous higest power of 2.
421*0Sigor@sysoev.ru      */
422*0Sigor@sysoev.ru 
423*0Sigor@sysoev.ru     /* Round the size to the previous higest power of two. */
424*0Sigor@sysoev.ru     size = nxt_next_highest_power_of_two(size1) >> 1;
425*0Sigor@sysoev.ru 
426*0Sigor@sysoev.ru     /* Align the blocks' start and end to the rounded size. */
427*0Sigor@sysoev.ru     start1 = nxt_align_ptr(block1, size);
428*0Sigor@sysoev.ru     end1 = nxt_trunc_ptr((u_char *) block1 + size1, size);
429*0Sigor@sysoev.ru 
430*0Sigor@sysoev.ru     start2 = nxt_align_ptr(block2, size);
431*0Sigor@sysoev.ru     end2 = nxt_trunc_ptr((u_char *) block2 + size2, size);
432*0Sigor@sysoev.ru 
433*0Sigor@sysoev.ru     return (end1 - start1) - (end2 - start2);
434*0Sigor@sysoev.ru }
435*0Sigor@sysoev.ru 
436*0Sigor@sysoev.ru 
437*0Sigor@sysoev.ru void *
438*0Sigor@sysoev.ru nxt_mem_zone_zalloc(nxt_mem_zone_t *zone, size_t size)
439*0Sigor@sysoev.ru {
440*0Sigor@sysoev.ru     void  *p;
441*0Sigor@sysoev.ru 
442*0Sigor@sysoev.ru     p = nxt_mem_zone_align(zone, 1, size);
443*0Sigor@sysoev.ru 
444*0Sigor@sysoev.ru     if (nxt_fast_path(p != NULL)) {
445*0Sigor@sysoev.ru         nxt_memzero(p, size);
446*0Sigor@sysoev.ru     }
447*0Sigor@sysoev.ru 
448*0Sigor@sysoev.ru     return p;
449*0Sigor@sysoev.ru }
450*0Sigor@sysoev.ru 
451*0Sigor@sysoev.ru 
452*0Sigor@sysoev.ru void *
453*0Sigor@sysoev.ru nxt_mem_zone_align(nxt_mem_zone_t *zone, size_t alignment, size_t size)
454*0Sigor@sysoev.ru {
455*0Sigor@sysoev.ru     void                 *p;
456*0Sigor@sysoev.ru     nxt_mem_zone_slot_t  *slot;
457*0Sigor@sysoev.ru 
458*0Sigor@sysoev.ru     if (nxt_slow_path((alignment - 1) & alignment) != 0) {
459*0Sigor@sysoev.ru         /* Alignment must be a power of 2. */
460*0Sigor@sysoev.ru         return NULL;
461*0Sigor@sysoev.ru     }
462*0Sigor@sysoev.ru 
463*0Sigor@sysoev.ru     if (size <= zone->max_chunk_size && alignment <= zone->max_chunk_size) {
464*0Sigor@sysoev.ru         /* All chunks are aligned to 16. */
465*0Sigor@sysoev.ru 
466*0Sigor@sysoev.ru         if (alignment > 16) {
467*0Sigor@sysoev.ru             /*
468*0Sigor@sysoev.ru              * Chunks which size is power of 2 are aligned to the size.
469*0Sigor@sysoev.ru              * So allocation size should be increased to the next highest
470*0Sigor@sysoev.ru              * power of two.  This can waste memory, but a main consumer
471*0Sigor@sysoev.ru              * of aligned allocations is lvlhsh which anyway allocates
472*0Sigor@sysoev.ru              * memory with alignment equal to size.
473*0Sigor@sysoev.ru              */
474*0Sigor@sysoev.ru             size = nxt_next_highest_power_of_two(size);
475*0Sigor@sysoev.ru             size = nxt_max(size, alignment);
476*0Sigor@sysoev.ru         }
477*0Sigor@sysoev.ru 
478*0Sigor@sysoev.ru         /*
479*0Sigor@sysoev.ru          * Find a zone slot with appropriate chunk size.
480*0Sigor@sysoev.ru          * This operation can be performed without holding lock.
481*0Sigor@sysoev.ru          */
482*0Sigor@sysoev.ru         for (slot = zone->slots; slot->size < size; slot++) { /* void */ }
483*0Sigor@sysoev.ru 
484*0Sigor@sysoev.ru         nxt_thread_log_debug("mem zone alloc: @%uz:%uz chunk:%uD",
485*0Sigor@sysoev.ru                              alignment, size, slot->size);
486*0Sigor@sysoev.ru 
487*0Sigor@sysoev.ru         nxt_thread_spin_lock(&zone->lock);
488*0Sigor@sysoev.ru 
489*0Sigor@sysoev.ru         p = nxt_mem_zone_alloc_small(zone, slot, size);
490*0Sigor@sysoev.ru 
491*0Sigor@sysoev.ru     } else {
492*0Sigor@sysoev.ru 
493*0Sigor@sysoev.ru         nxt_thread_log_debug("mem zone alloc: @%uz:%uz", alignment, size);
494*0Sigor@sysoev.ru 
495*0Sigor@sysoev.ru         nxt_thread_spin_lock(&zone->lock);
496*0Sigor@sysoev.ru 
497*0Sigor@sysoev.ru         p = nxt_mem_zone_alloc_large(zone, alignment, size);
498*0Sigor@sysoev.ru     }
499*0Sigor@sysoev.ru 
500*0Sigor@sysoev.ru     nxt_thread_spin_unlock(&zone->lock);
501*0Sigor@sysoev.ru 
502*0Sigor@sysoev.ru     if (nxt_fast_path(p != NULL)) {
503*0Sigor@sysoev.ru         nxt_thread_log_debug("mem zone alloc: %p", p);
504*0Sigor@sysoev.ru 
505*0Sigor@sysoev.ru     } else {
506*0Sigor@sysoev.ru         nxt_log_moderate(&nxt_mem_zone_log_moderation,
507*0Sigor@sysoev.ru                     NXT_LOG_ALERT, nxt_thread_log(),
508*0Sigor@sysoev.ru                     "nxt_mem_zone_alloc(%uz, %uz) failed, not enough memory",
509*0Sigor@sysoev.ru                     alignment, size);
510*0Sigor@sysoev.ru     }
511*0Sigor@sysoev.ru 
512*0Sigor@sysoev.ru     return p;
513*0Sigor@sysoev.ru }
514*0Sigor@sysoev.ru 
515*0Sigor@sysoev.ru 
516*0Sigor@sysoev.ru static void *
517*0Sigor@sysoev.ru nxt_mem_zone_alloc_small(nxt_mem_zone_t *zone, nxt_mem_zone_slot_t *slot,
518*0Sigor@sysoev.ru     size_t size)
519*0Sigor@sysoev.ru {
520*0Sigor@sysoev.ru     u_char               *p;
521*0Sigor@sysoev.ru     uint8_t              *map;
522*0Sigor@sysoev.ru     nxt_mem_zone_page_t  *page;
523*0Sigor@sysoev.ru 
524*0Sigor@sysoev.ru     page = slot->pages;
525*0Sigor@sysoev.ru 
526*0Sigor@sysoev.ru     if (nxt_fast_path(page != NULL)) {
527*0Sigor@sysoev.ru 
528*0Sigor@sysoev.ru         p = nxt_mem_zone_page_addr(zone, page);
529*0Sigor@sysoev.ru 
530*0Sigor@sysoev.ru         if (nxt_mem_zone_page_bitmap(zone, slot)) {
531*0Sigor@sysoev.ru             /* A page's chunks bitmap is placed at the start of the page. */
532*0Sigor@sysoev.ru             map = p;
533*0Sigor@sysoev.ru 
534*0Sigor@sysoev.ru         } else {
535*0Sigor@sysoev.ru             map = page->u.map;
536*0Sigor@sysoev.ru         }
537*0Sigor@sysoev.ru 
538*0Sigor@sysoev.ru         p += nxt_mem_zone_alloc_chunk(map, slot->start, slot->size);
539*0Sigor@sysoev.ru 
540*0Sigor@sysoev.ru         page->chunks--;
541*0Sigor@sysoev.ru 
542*0Sigor@sysoev.ru         if (page->chunks == 0) {
543*0Sigor@sysoev.ru             /*
544*0Sigor@sysoev.ru              * Remove full page from the zone slot list of pages with
545*0Sigor@sysoev.ru              * free chunks.
546*0Sigor@sysoev.ru              */
547*0Sigor@sysoev.ru             slot->pages = page->next;
548*0Sigor@sysoev.ru #if (NXT_DEBUG)
549*0Sigor@sysoev.ru             page->next = NULL;
550*0Sigor@sysoev.ru #endif
551*0Sigor@sysoev.ru         }
552*0Sigor@sysoev.ru 
553*0Sigor@sysoev.ru         return p;
554*0Sigor@sysoev.ru     }
555*0Sigor@sysoev.ru 
556*0Sigor@sysoev.ru     page = nxt_mem_zone_alloc_pages(zone, 1, 1);
557*0Sigor@sysoev.ru 
558*0Sigor@sysoev.ru     if (nxt_fast_path(page != NULL)) {
559*0Sigor@sysoev.ru 
560*0Sigor@sysoev.ru         slot->pages = page;
561*0Sigor@sysoev.ru 
562*0Sigor@sysoev.ru         page->size = slot->size;
563*0Sigor@sysoev.ru         /* slot->chunks are already one less. */
564*0Sigor@sysoev.ru         page->chunks = slot->chunks;
565*0Sigor@sysoev.ru         page->u.count = 0;
566*0Sigor@sysoev.ru         page->next = NULL;
567*0Sigor@sysoev.ru 
568*0Sigor@sysoev.ru         p = nxt_mem_zone_page_addr(zone, page);
569*0Sigor@sysoev.ru 
570*0Sigor@sysoev.ru         if (nxt_mem_zone_page_bitmap(zone, slot)) {
571*0Sigor@sysoev.ru             /* A page's chunks bitmap is placed at the start of the page. */
572*0Sigor@sysoev.ru             map = p;
573*0Sigor@sysoev.ru             nxt_memzero(map, slot->map_size);
574*0Sigor@sysoev.ru 
575*0Sigor@sysoev.ru         } else {
576*0Sigor@sysoev.ru             map = page->u.map;
577*0Sigor@sysoev.ru         }
578*0Sigor@sysoev.ru 
579*0Sigor@sysoev.ru         /* Mark the first chunk as busy. */
580*0Sigor@sysoev.ru         map[0] = 0x80;
581*0Sigor@sysoev.ru 
582*0Sigor@sysoev.ru         return p + slot->start;
583*0Sigor@sysoev.ru     }
584*0Sigor@sysoev.ru 
585*0Sigor@sysoev.ru     return NULL;
586*0Sigor@sysoev.ru }
587*0Sigor@sysoev.ru 
588*0Sigor@sysoev.ru 
589*0Sigor@sysoev.ru static nxt_uint_t
590*0Sigor@sysoev.ru nxt_mem_zone_alloc_chunk(uint8_t *map, nxt_uint_t offset, nxt_uint_t size)
591*0Sigor@sysoev.ru {
592*0Sigor@sysoev.ru     uint8_t     mask;
593*0Sigor@sysoev.ru     nxt_uint_t  n;
594*0Sigor@sysoev.ru 
595*0Sigor@sysoev.ru     n = 0;
596*0Sigor@sysoev.ru 
597*0Sigor@sysoev.ru     /* The page must have at least one free chunk. */
598*0Sigor@sysoev.ru 
599*0Sigor@sysoev.ru     for ( ;; ) {
600*0Sigor@sysoev.ru         /* The bitmap is always aligned to uint32_t. */
601*0Sigor@sysoev.ru 
602*0Sigor@sysoev.ru         if (*(uint32_t *) &map[n] != 0xffffffff) {
603*0Sigor@sysoev.ru 
604*0Sigor@sysoev.ru             do {
605*0Sigor@sysoev.ru                 if (map[n] != 0xff) {
606*0Sigor@sysoev.ru 
607*0Sigor@sysoev.ru                     mask = 0x80;
608*0Sigor@sysoev.ru 
609*0Sigor@sysoev.ru                     do {
610*0Sigor@sysoev.ru                         if ((map[n] & mask) == 0) {
611*0Sigor@sysoev.ru                             /* The free chunk is found. */
612*0Sigor@sysoev.ru                             map[n] |= mask;
613*0Sigor@sysoev.ru                             return offset;
614*0Sigor@sysoev.ru                         }
615*0Sigor@sysoev.ru 
616*0Sigor@sysoev.ru                         offset += size;
617*0Sigor@sysoev.ru                         mask >>= 1;
618*0Sigor@sysoev.ru 
619*0Sigor@sysoev.ru                     } while (mask != 0);
620*0Sigor@sysoev.ru 
621*0Sigor@sysoev.ru                 } else {
622*0Sigor@sysoev.ru                     /* Fast-forward: all 8 chunks are occupied. */
623*0Sigor@sysoev.ru                     offset += size * 8;
624*0Sigor@sysoev.ru                 }
625*0Sigor@sysoev.ru 
626*0Sigor@sysoev.ru                 n++;
627*0Sigor@sysoev.ru 
628*0Sigor@sysoev.ru             } while (n % 4 != 0);
629*0Sigor@sysoev.ru 
630*0Sigor@sysoev.ru         } else {
631*0Sigor@sysoev.ru             /* Fast-forward: all 32 chunks are occupied. */
632*0Sigor@sysoev.ru             offset += size * 32;
633*0Sigor@sysoev.ru             n += 4;
634*0Sigor@sysoev.ru         }
635*0Sigor@sysoev.ru     }
636*0Sigor@sysoev.ru }
637*0Sigor@sysoev.ru 
638*0Sigor@sysoev.ru 
639*0Sigor@sysoev.ru static void *
640*0Sigor@sysoev.ru nxt_mem_zone_alloc_large(nxt_mem_zone_t *zone, size_t alignment, size_t size)
641*0Sigor@sysoev.ru {
642*0Sigor@sysoev.ru     uint32_t             pages;
643*0Sigor@sysoev.ru     nxt_mem_zone_page_t  *page;
644*0Sigor@sysoev.ru 
645*0Sigor@sysoev.ru     pages = (size + zone->page_size_mask) >> zone->page_size_shift;
646*0Sigor@sysoev.ru 
647*0Sigor@sysoev.ru     page = nxt_mem_zone_alloc_pages(zone, alignment, pages);
648*0Sigor@sysoev.ru 
649*0Sigor@sysoev.ru     if (nxt_fast_path(page != NULL)) {
650*0Sigor@sysoev.ru         return nxt_mem_zone_page_addr(zone, page);
651*0Sigor@sysoev.ru     }
652*0Sigor@sysoev.ru 
653*0Sigor@sysoev.ru     return NULL;
654*0Sigor@sysoev.ru }
655*0Sigor@sysoev.ru 
656*0Sigor@sysoev.ru 
657*0Sigor@sysoev.ru static nxt_mem_zone_page_t *
658*0Sigor@sysoev.ru nxt_mem_zone_alloc_pages(nxt_mem_zone_t *zone, size_t alignment, uint32_t pages)
659*0Sigor@sysoev.ru {
660*0Sigor@sysoev.ru     u_char                     *p;
661*0Sigor@sysoev.ru     size_t                     prev_size;
662*0Sigor@sysoev.ru     uint32_t                   prev_pages, node_pages, next_pages;
663*0Sigor@sysoev.ru     nxt_uint_t                 n;
664*0Sigor@sysoev.ru     nxt_mem_zone_page_t        *prev_page, *page, *next_page;
665*0Sigor@sysoev.ru     nxt_mem_zone_free_block_t  *block, *next_block;
666*0Sigor@sysoev.ru 
667*0Sigor@sysoev.ru     block = nxt_mem_zone_find_free_block(zone,
668*0Sigor@sysoev.ru                                          nxt_rbtree_root(&zone->free_pages),
669*0Sigor@sysoev.ru                                          alignment, pages);
670*0Sigor@sysoev.ru 
671*0Sigor@sysoev.ru     if (nxt_slow_path(block == NULL)) {
672*0Sigor@sysoev.ru         return NULL;
673*0Sigor@sysoev.ru     }
674*0Sigor@sysoev.ru 
675*0Sigor@sysoev.ru     node_pages = block->size;
676*0Sigor@sysoev.ru 
677*0Sigor@sysoev.ru     nxt_rbtree_delete(&zone->free_pages, &block->node);
678*0Sigor@sysoev.ru 
679*0Sigor@sysoev.ru     p = nxt_align_ptr(block, alignment);
680*0Sigor@sysoev.ru     page = nxt_mem_zone_addr_page(zone, p);
681*0Sigor@sysoev.ru 
682*0Sigor@sysoev.ru     prev_size = p - (u_char *) block;
683*0Sigor@sysoev.ru 
684*0Sigor@sysoev.ru     if (prev_size != 0) {
685*0Sigor@sysoev.ru         prev_pages = prev_size >>= zone->page_size_shift;
686*0Sigor@sysoev.ru         node_pages -= prev_pages;
687*0Sigor@sysoev.ru 
688*0Sigor@sysoev.ru         block->size = prev_pages;
689*0Sigor@sysoev.ru         nxt_rbtree_insert(&zone->free_pages, &block->node);
690*0Sigor@sysoev.ru 
691*0Sigor@sysoev.ru         prev_page = nxt_mem_zone_addr_page(zone, block);
692*0Sigor@sysoev.ru         nxt_queue_insert_after(&prev_page->link, &page->link);
693*0Sigor@sysoev.ru     }
694*0Sigor@sysoev.ru 
695*0Sigor@sysoev.ru     next_pages = node_pages - pages;
696*0Sigor@sysoev.ru 
697*0Sigor@sysoev.ru     if (next_pages != 0) {
698*0Sigor@sysoev.ru         next_page = &page[pages];
699*0Sigor@sysoev.ru         next_block = nxt_mem_zone_page_addr(zone, next_page);
700*0Sigor@sysoev.ru         next_block->size = next_pages;
701*0Sigor@sysoev.ru 
702*0Sigor@sysoev.ru         nxt_rbtree_insert(&zone->free_pages, &next_block->node);
703*0Sigor@sysoev.ru         nxt_queue_insert_after(&page->link, &next_page->link);
704*0Sigor@sysoev.ru     }
705*0Sigor@sysoev.ru 
706*0Sigor@sysoev.ru     /* Go through pages after all rbtree operations to not trash CPU cache. */
707*0Sigor@sysoev.ru 
708*0Sigor@sysoev.ru     page[0].u.count = pages;
709*0Sigor@sysoev.ru 
710*0Sigor@sysoev.ru     for (n = 0; n < pages; n++) {
711*0Sigor@sysoev.ru 
712*0Sigor@sysoev.ru         if (page[n].size == NXT_MEM_ZONE_PAGE_FRESH) {
713*0Sigor@sysoev.ru             nxt_mem_zone_fresh_junk(nxt_mem_zone_page_addr(zone, &page[n]),
714*0Sigor@sysoev.ru                                     zone->page_size_mask + 1);
715*0Sigor@sysoev.ru         }
716*0Sigor@sysoev.ru 
717*0Sigor@sysoev.ru         page[n].size = NXT_MEM_ZONE_PAGE_USED;
718*0Sigor@sysoev.ru     }
719*0Sigor@sysoev.ru 
720*0Sigor@sysoev.ru     return page;
721*0Sigor@sysoev.ru }
722*0Sigor@sysoev.ru 
723*0Sigor@sysoev.ru 
724*0Sigor@sysoev.ru /*
725*0Sigor@sysoev.ru  * Free blocks are sorted by size and then if the sizes are equal
726*0Sigor@sysoev.ru  * by aligned allocation capabilty.  The former criterion is just
727*0Sigor@sysoev.ru  * comparison with a requested size and it can be used for iteractive
728*0Sigor@sysoev.ru  * search.  The later criterion cannot be tested only by the requested
729*0Sigor@sysoev.ru  * size and alignment, so recursive in-order tree traversal is required
730*0Sigor@sysoev.ru  * to find a suitable free block.  nxt_mem_zone_find_free_block() uses
731*0Sigor@sysoev.ru  * only recursive in-order tree traversal because anyway the slowest part
732*0Sigor@sysoev.ru  * of the algorithm are CPU cache misses.  Besides the last tail recursive
733*0Sigor@sysoev.ru  * call may be optimized by compiler into iteractive search.
734*0Sigor@sysoev.ru  */
735*0Sigor@sysoev.ru 
736*0Sigor@sysoev.ru static nxt_mem_zone_free_block_t *
737*0Sigor@sysoev.ru nxt_mem_zone_find_free_block(nxt_mem_zone_t *zone, nxt_rbtree_node_t *node,
738*0Sigor@sysoev.ru     uint32_t alignment, uint32_t pages)
739*0Sigor@sysoev.ru {
740*0Sigor@sysoev.ru     u_char                     *aligned, *end;
741*0Sigor@sysoev.ru     nxt_mem_zone_free_block_t  *block, *free_block;
742*0Sigor@sysoev.ru 
743*0Sigor@sysoev.ru     if (node == nxt_rbtree_sentinel(&zone->free_pages)) {
744*0Sigor@sysoev.ru         return NULL;
745*0Sigor@sysoev.ru     }
746*0Sigor@sysoev.ru 
747*0Sigor@sysoev.ru     block = (nxt_mem_zone_free_block_t *) node;
748*0Sigor@sysoev.ru 
749*0Sigor@sysoev.ru     if (pages <= block->size) {
750*0Sigor@sysoev.ru 
751*0Sigor@sysoev.ru         free_block = nxt_mem_zone_find_free_block(zone, block->node.left,
752*0Sigor@sysoev.ru                                                   alignment, pages);
753*0Sigor@sysoev.ru         if (free_block != NULL) {
754*0Sigor@sysoev.ru             return free_block;
755*0Sigor@sysoev.ru         }
756*0Sigor@sysoev.ru 
757*0Sigor@sysoev.ru         aligned = nxt_align_ptr(block, alignment);
758*0Sigor@sysoev.ru 
759*0Sigor@sysoev.ru         if (pages == block->size) {
760*0Sigor@sysoev.ru             if (aligned == (u_char *) block) {
761*0Sigor@sysoev.ru                 /* Exact match. */
762*0Sigor@sysoev.ru                 return block;
763*0Sigor@sysoev.ru             }
764*0Sigor@sysoev.ru 
765*0Sigor@sysoev.ru         } else {  /* pages < block->size */
766*0Sigor@sysoev.ru             aligned += pages << zone->page_size_shift;
767*0Sigor@sysoev.ru             end = (u_char *) block + (block->size << zone->page_size_shift);
768*0Sigor@sysoev.ru 
769*0Sigor@sysoev.ru             if (aligned <= end) {
770*0Sigor@sysoev.ru                 return block;
771*0Sigor@sysoev.ru             }
772*0Sigor@sysoev.ru         }
773*0Sigor@sysoev.ru     }
774*0Sigor@sysoev.ru 
775*0Sigor@sysoev.ru     return nxt_mem_zone_find_free_block(zone, block->node.right,
776*0Sigor@sysoev.ru                                         alignment, pages);
777*0Sigor@sysoev.ru }
778*0Sigor@sysoev.ru 
779*0Sigor@sysoev.ru 
780*0Sigor@sysoev.ru void
781*0Sigor@sysoev.ru nxt_mem_zone_free(nxt_mem_zone_t *zone, void *p)
782*0Sigor@sysoev.ru {
783*0Sigor@sysoev.ru     nxt_uint_t           count;
784*0Sigor@sysoev.ru     const char           *err;
785*0Sigor@sysoev.ru     nxt_mem_zone_page_t  *page;
786*0Sigor@sysoev.ru 
787*0Sigor@sysoev.ru     nxt_thread_log_debug("mem zone free: %p", p);
788*0Sigor@sysoev.ru 
789*0Sigor@sysoev.ru     if (nxt_fast_path(zone->start <= (u_char *) p
790*0Sigor@sysoev.ru                       && (u_char *) p < zone->end))
791*0Sigor@sysoev.ru     {
792*0Sigor@sysoev.ru         page = nxt_mem_zone_addr_page(zone, p);
793*0Sigor@sysoev.ru 
794*0Sigor@sysoev.ru         nxt_thread_spin_lock(&zone->lock);
795*0Sigor@sysoev.ru 
796*0Sigor@sysoev.ru         if (nxt_mem_zone_page_is_chunked(page)) {
797*0Sigor@sysoev.ru             err = nxt_mem_zone_free_chunk(zone, page, p);
798*0Sigor@sysoev.ru 
799*0Sigor@sysoev.ru         } else if (nxt_slow_path(nxt_mem_zone_page_is_free(page))) {
800*0Sigor@sysoev.ru             err = "page is already free";
801*0Sigor@sysoev.ru 
802*0Sigor@sysoev.ru         } else if (nxt_slow_path((uintptr_t) p & zone->page_size_mask) != 0) {
803*0Sigor@sysoev.ru             err = "invalid pointer to chunk";
804*0Sigor@sysoev.ru 
805*0Sigor@sysoev.ru         } else {
806*0Sigor@sysoev.ru             count = page->u.count;
807*0Sigor@sysoev.ru 
808*0Sigor@sysoev.ru             if (nxt_fast_path(count != 0)) {
809*0Sigor@sysoev.ru                 nxt_mem_zone_free_junk(p, count * zone->page_size_mask + 1);
810*0Sigor@sysoev.ru                 nxt_mem_zone_free_pages(zone, page, count);
811*0Sigor@sysoev.ru                 err = NULL;
812*0Sigor@sysoev.ru 
813*0Sigor@sysoev.ru             } else {
814*0Sigor@sysoev.ru                 /* Not the first allocated page. */
815*0Sigor@sysoev.ru                 err = "pointer to wrong page";
816*0Sigor@sysoev.ru             }
817*0Sigor@sysoev.ru         }
818*0Sigor@sysoev.ru 
819*0Sigor@sysoev.ru         nxt_thread_spin_unlock(&zone->lock);
820*0Sigor@sysoev.ru 
821*0Sigor@sysoev.ru     } else {
822*0Sigor@sysoev.ru         err = "pointer is out of zone";
823*0Sigor@sysoev.ru     }
824*0Sigor@sysoev.ru 
825*0Sigor@sysoev.ru     if (nxt_slow_path(err != NULL)) {
826*0Sigor@sysoev.ru         nxt_thread_log_alert("nxt_mem_zone_free(%p): %s", p, err);
827*0Sigor@sysoev.ru     }
828*0Sigor@sysoev.ru }
829*0Sigor@sysoev.ru 
830*0Sigor@sysoev.ru 
831*0Sigor@sysoev.ru static const char *
832*0Sigor@sysoev.ru nxt_mem_zone_free_chunk(nxt_mem_zone_t *zone, nxt_mem_zone_page_t *page,
833*0Sigor@sysoev.ru     void *p)
834*0Sigor@sysoev.ru {
835*0Sigor@sysoev.ru     u_char               *map;
836*0Sigor@sysoev.ru     uint32_t             size, offset, chunk;
837*0Sigor@sysoev.ru     nxt_mem_zone_page_t  *pg, **ppg;
838*0Sigor@sysoev.ru     nxt_mem_zone_slot_t  *slot;
839*0Sigor@sysoev.ru 
840*0Sigor@sysoev.ru     size = page->size;
841*0Sigor@sysoev.ru 
842*0Sigor@sysoev.ru     /* Find a zone slot with appropriate chunk size. */
843*0Sigor@sysoev.ru     for (slot = zone->slots; slot->size < size; slot++) { /* void */ }
844*0Sigor@sysoev.ru 
845*0Sigor@sysoev.ru     offset = (uintptr_t) p & zone->page_size_mask;
846*0Sigor@sysoev.ru     offset -= slot->start;
847*0Sigor@sysoev.ru 
848*0Sigor@sysoev.ru     chunk = offset / size;
849*0Sigor@sysoev.ru 
850*0Sigor@sysoev.ru     if (nxt_slow_path(offset != chunk * size)) {
851*0Sigor@sysoev.ru         return "pointer to wrong chunk";
852*0Sigor@sysoev.ru     }
853*0Sigor@sysoev.ru 
854*0Sigor@sysoev.ru     if (nxt_mem_zone_page_bitmap(zone, slot)) {
855*0Sigor@sysoev.ru         /* A page's chunks bitmap is placed at the start of the page. */
856*0Sigor@sysoev.ru         map = (u_char *) ((uintptr_t) p & ~((uintptr_t) zone->page_size_mask));
857*0Sigor@sysoev.ru 
858*0Sigor@sysoev.ru     } else {
859*0Sigor@sysoev.ru         map = page->u.map;
860*0Sigor@sysoev.ru     }
861*0Sigor@sysoev.ru 
862*0Sigor@sysoev.ru     if (nxt_mem_zone_chunk_is_free(map, chunk)) {
863*0Sigor@sysoev.ru         return "chunk is already free";
864*0Sigor@sysoev.ru     }
865*0Sigor@sysoev.ru 
866*0Sigor@sysoev.ru     nxt_mem_zone_set_chunk_free(map, chunk);
867*0Sigor@sysoev.ru 
868*0Sigor@sysoev.ru     nxt_mem_zone_free_junk(p, page->size);
869*0Sigor@sysoev.ru 
870*0Sigor@sysoev.ru     if (page->chunks == 0) {
871*0Sigor@sysoev.ru         page->chunks = 1;
872*0Sigor@sysoev.ru 
873*0Sigor@sysoev.ru         /* Add the page to the head of slot list of pages with free chunks. */
874*0Sigor@sysoev.ru         page->next = slot->pages;
875*0Sigor@sysoev.ru         slot->pages = page;
876*0Sigor@sysoev.ru 
877*0Sigor@sysoev.ru     } else if (page->chunks != slot->chunks) {
878*0Sigor@sysoev.ru         page->chunks++;
879*0Sigor@sysoev.ru 
880*0Sigor@sysoev.ru     } else {
881*0Sigor@sysoev.ru 
882*0Sigor@sysoev.ru         if (map != page->u.map) {
883*0Sigor@sysoev.ru             nxt_mem_zone_free_junk(map, slot->map_size);
884*0Sigor@sysoev.ru         }
885*0Sigor@sysoev.ru 
886*0Sigor@sysoev.ru         /*
887*0Sigor@sysoev.ru          * All chunks are free, remove the page from the slot list of pages
888*0Sigor@sysoev.ru          * with free chunks and add the page to the free pages tree.
889*0Sigor@sysoev.ru          */
890*0Sigor@sysoev.ru         ppg = &slot->pages;
891*0Sigor@sysoev.ru 
892*0Sigor@sysoev.ru         for (pg = slot->pages; pg != NULL; pg = pg->next) {
893*0Sigor@sysoev.ru 
894*0Sigor@sysoev.ru             if (pg == page) {
895*0Sigor@sysoev.ru                 *ppg = page->next;
896*0Sigor@sysoev.ru                 break;
897*0Sigor@sysoev.ru             }
898*0Sigor@sysoev.ru 
899*0Sigor@sysoev.ru             ppg = &pg->next;
900*0Sigor@sysoev.ru         }
901*0Sigor@sysoev.ru 
902*0Sigor@sysoev.ru         nxt_mem_zone_free_pages(zone, page, 1);
903*0Sigor@sysoev.ru     }
904*0Sigor@sysoev.ru 
905*0Sigor@sysoev.ru     return NULL;
906*0Sigor@sysoev.ru }
907*0Sigor@sysoev.ru 
908*0Sigor@sysoev.ru 
909*0Sigor@sysoev.ru static void
910*0Sigor@sysoev.ru nxt_mem_zone_free_pages(nxt_mem_zone_t *zone, nxt_mem_zone_page_t *page,
911*0Sigor@sysoev.ru     nxt_uint_t count)
912*0Sigor@sysoev.ru {
913*0Sigor@sysoev.ru     nxt_mem_zone_page_t        *prev_page, *next_page;
914*0Sigor@sysoev.ru     nxt_mem_zone_free_block_t  *block, *prev_block, *next_block;
915*0Sigor@sysoev.ru 
916*0Sigor@sysoev.ru     page->size = NXT_MEM_ZONE_PAGE_FREE;
917*0Sigor@sysoev.ru     page->chunks = 0;
918*0Sigor@sysoev.ru     page->u.count = 0;
919*0Sigor@sysoev.ru     page->next = NULL;
920*0Sigor@sysoev.ru 
921*0Sigor@sysoev.ru     nxt_memzero(&page[1], (count - 1) * sizeof(nxt_mem_zone_page_t));
922*0Sigor@sysoev.ru 
923*0Sigor@sysoev.ru     next_page = nxt_queue_link_data(page->link.next, nxt_mem_zone_page_t, link);
924*0Sigor@sysoev.ru 
925*0Sigor@sysoev.ru     if (nxt_mem_zone_page_is_free(next_page)) {
926*0Sigor@sysoev.ru 
927*0Sigor@sysoev.ru         /* Coalesce with the next free pages. */
928*0Sigor@sysoev.ru 
929*0Sigor@sysoev.ru         nxt_queue_remove(&next_page->link);
930*0Sigor@sysoev.ru         nxt_memzero(next_page, sizeof(nxt_mem_zone_page_t));
931*0Sigor@sysoev.ru 
932*0Sigor@sysoev.ru         next_block = nxt_mem_zone_page_addr(zone, next_page);
933*0Sigor@sysoev.ru         count += next_block->size;
934*0Sigor@sysoev.ru         nxt_rbtree_delete(&zone->free_pages, &next_block->node);
935*0Sigor@sysoev.ru     }
936*0Sigor@sysoev.ru 
937*0Sigor@sysoev.ru     prev_page = nxt_queue_link_data(page->link.prev, nxt_mem_zone_page_t, link);
938*0Sigor@sysoev.ru 
939*0Sigor@sysoev.ru     if (nxt_mem_zone_page_is_free(prev_page)) {
940*0Sigor@sysoev.ru 
941*0Sigor@sysoev.ru         /* Coalesce with the previous free pages. */
942*0Sigor@sysoev.ru 
943*0Sigor@sysoev.ru         nxt_queue_remove(&page->link);
944*0Sigor@sysoev.ru 
945*0Sigor@sysoev.ru         prev_block = nxt_mem_zone_page_addr(zone, prev_page);
946*0Sigor@sysoev.ru         count += prev_block->size;
947*0Sigor@sysoev.ru         nxt_rbtree_delete(&zone->free_pages, &prev_block->node);
948*0Sigor@sysoev.ru 
949*0Sigor@sysoev.ru         prev_block->size = count;
950*0Sigor@sysoev.ru         nxt_rbtree_insert(&zone->free_pages, &prev_block->node);
951*0Sigor@sysoev.ru 
952*0Sigor@sysoev.ru         return;
953*0Sigor@sysoev.ru     }
954*0Sigor@sysoev.ru 
955*0Sigor@sysoev.ru     block = nxt_mem_zone_page_addr(zone, page);
956*0Sigor@sysoev.ru     block->size = count;
957*0Sigor@sysoev.ru     nxt_rbtree_insert(&zone->free_pages, &block->node);
958*0Sigor@sysoev.ru }
959