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