xref: /unit/src/nxt_mem_zone.c (revision 2404:a254723b8549)
10Sigor@sysoev.ru 
20Sigor@sysoev.ru /*
30Sigor@sysoev.ru  * Copyright (C) Igor Sysoev
40Sigor@sysoev.ru  * Copyright (C) NGINX, Inc.
50Sigor@sysoev.ru  */
60Sigor@sysoev.ru 
70Sigor@sysoev.ru #include <nxt_main.h>
80Sigor@sysoev.ru 
90Sigor@sysoev.ru 
100Sigor@sysoev.ru #define NXT_MEM_ZONE_PAGE_FREE      0
110Sigor@sysoev.ru /*
120Sigor@sysoev.ru  * A page was never allocated before so it should be filled with
130Sigor@sysoev.ru  * junk on the first time allocation if memory debugging is enabled.
140Sigor@sysoev.ru  */
150Sigor@sysoev.ru #define NXT_MEM_ZONE_PAGE_FRESH     1
160Sigor@sysoev.ru 
170Sigor@sysoev.ru /* An entire page is currently used, no chunks inside the page. */
180Sigor@sysoev.ru #define NXT_MEM_ZONE_PAGE_USED      2
190Sigor@sysoev.ru 
200Sigor@sysoev.ru 
210Sigor@sysoev.ru typedef struct nxt_mem_zone_page_s  nxt_mem_zone_page_t;
220Sigor@sysoev.ru 
230Sigor@sysoev.ru struct nxt_mem_zone_page_s {
240Sigor@sysoev.ru     /*
250Sigor@sysoev.ru      * A size of page chunks if value is greater than or equal to 16.
260Sigor@sysoev.ru      * Otherwise it is used to mark page state: NXT_MEM_ZONE_PAGE_FREE,
270Sigor@sysoev.ru      * NXT_MEM_ZONE_PAGE_FRESH, and NXT_MEM_ZONE_PAGE_USED.
280Sigor@sysoev.ru      */
290Sigor@sysoev.ru     uint16_t               size;
300Sigor@sysoev.ru 
310Sigor@sysoev.ru     /* A number of free chunks of a chunked page. */
320Sigor@sysoev.ru     uint16_t               chunks;
330Sigor@sysoev.ru 
340Sigor@sysoev.ru     union {
350Sigor@sysoev.ru         /* A chunk bitmap if a number of chunks is lesser than 32. */
360Sigor@sysoev.ru         uint8_t            map[4];
370Sigor@sysoev.ru         /*
380Sigor@sysoev.ru          * The count is a number of successive occupied pages in the first
390Sigor@sysoev.ru          * page.  In the next occupied pages and in all free pages the count
400Sigor@sysoev.ru          * is zero, because a number of successive free pages is stored in
410Sigor@sysoev.ru          * free block size resided in beginning of the first free page.
420Sigor@sysoev.ru          */
430Sigor@sysoev.ru         uint32_t           count;
440Sigor@sysoev.ru     } u;
450Sigor@sysoev.ru 
460Sigor@sysoev.ru     /* Used for slot list of pages with free chunks. */
470Sigor@sysoev.ru     nxt_mem_zone_page_t    *next;
480Sigor@sysoev.ru 
490Sigor@sysoev.ru     /*
500Sigor@sysoev.ru      * Used to link of all pages including free, chunked and occupied
510Sigor@sysoev.ru      * pages to coalesce free pages.
520Sigor@sysoev.ru      */
530Sigor@sysoev.ru     nxt_queue_link_t       link;
540Sigor@sysoev.ru };
550Sigor@sysoev.ru 
560Sigor@sysoev.ru 
570Sigor@sysoev.ru typedef struct {
580Sigor@sysoev.ru     uint32_t               size;
590Sigor@sysoev.ru     uint32_t               chunks;
600Sigor@sysoev.ru     uint32_t               start;
610Sigor@sysoev.ru     uint32_t               map_size;
620Sigor@sysoev.ru     nxt_mem_zone_page_t    *pages;
630Sigor@sysoev.ru } nxt_mem_zone_slot_t;
640Sigor@sysoev.ru 
650Sigor@sysoev.ru 
660Sigor@sysoev.ru typedef struct {
670Sigor@sysoev.ru     NXT_RBTREE_NODE        (node);
680Sigor@sysoev.ru     uint32_t               size;
690Sigor@sysoev.ru } nxt_mem_zone_free_block_t;
700Sigor@sysoev.ru 
710Sigor@sysoev.ru 
720Sigor@sysoev.ru struct nxt_mem_zone_s {
730Sigor@sysoev.ru     nxt_thread_spinlock_t  lock;
740Sigor@sysoev.ru     nxt_mem_zone_page_t    *pages;
750Sigor@sysoev.ru     nxt_mem_zone_page_t    sentinel_page;
760Sigor@sysoev.ru     nxt_rbtree_t           free_pages;
770Sigor@sysoev.ru 
780Sigor@sysoev.ru     uint32_t               page_size_shift;
790Sigor@sysoev.ru     uint32_t               page_size_mask;
800Sigor@sysoev.ru     uint32_t               max_chunk_size;
810Sigor@sysoev.ru     uint32_t               small_bitmap_min_size;
820Sigor@sysoev.ru 
830Sigor@sysoev.ru     u_char                 *start;
840Sigor@sysoev.ru     u_char                 *end;
850Sigor@sysoev.ru 
860Sigor@sysoev.ru     nxt_mem_zone_slot_t    slots[];
870Sigor@sysoev.ru };
880Sigor@sysoev.ru 
890Sigor@sysoev.ru 
902084Salx.manpages@gmail.com #define nxt_mem_zone_page_addr(zone, page)                                    \
910Sigor@sysoev.ru     (void *) (zone->start + ((page - zone->pages) << zone->page_size_shift))
920Sigor@sysoev.ru 
930Sigor@sysoev.ru 
942084Salx.manpages@gmail.com #define nxt_mem_zone_addr_page(zone, addr)                                    \
950Sigor@sysoev.ru     &zone->pages[((u_char *) addr - zone->start) >> zone->page_size_shift]
960Sigor@sysoev.ru 
970Sigor@sysoev.ru 
982084Salx.manpages@gmail.com #define nxt_mem_zone_page_is_free(page)                                       \
990Sigor@sysoev.ru     (page->size < NXT_MEM_ZONE_PAGE_USED)
1000Sigor@sysoev.ru 
1010Sigor@sysoev.ru 
1022084Salx.manpages@gmail.com #define nxt_mem_zone_page_is_chunked(page)                                    \
1030Sigor@sysoev.ru     (page->size >= 16)
1040Sigor@sysoev.ru 
1050Sigor@sysoev.ru 
1062084Salx.manpages@gmail.com #define nxt_mem_zone_page_bitmap(zone, slot)                                  \
1070Sigor@sysoev.ru     (slot->size < zone->small_bitmap_min_size)
1080Sigor@sysoev.ru 
1090Sigor@sysoev.ru 
1102084Salx.manpages@gmail.com #define nxt_mem_zone_set_chunk_free(map, chunk)                               \
1110Sigor@sysoev.ru     map[chunk / 8] &= ~(0x80 >> (chunk & 7))
1120Sigor@sysoev.ru 
1130Sigor@sysoev.ru 
1142084Salx.manpages@gmail.com #define nxt_mem_zone_chunk_is_free(map, chunk)                                \
1150Sigor@sysoev.ru     ((map[chunk / 8] & (0x80 >> (chunk & 7))) == 0)
1160Sigor@sysoev.ru 
1170Sigor@sysoev.ru 
1182084Salx.manpages@gmail.com #define nxt_mem_zone_fresh_junk(p, size)                                      \
1190Sigor@sysoev.ru     nxt_memset((p), 0xA5, size)
1200Sigor@sysoev.ru 
1210Sigor@sysoev.ru 
1222084Salx.manpages@gmail.com #define nxt_mem_zone_free_junk(p, size)                                       \
1230Sigor@sysoev.ru     nxt_memset((p), 0x5A, size)
1240Sigor@sysoev.ru 
1250Sigor@sysoev.ru 
1260Sigor@sysoev.ru static uint32_t nxt_mem_zone_pages(u_char *start, size_t zone_size,
1270Sigor@sysoev.ru     nxt_uint_t page_size);
1280Sigor@sysoev.ru static void *nxt_mem_zone_slots_init(nxt_mem_zone_t *zone,
1290Sigor@sysoev.ru     nxt_uint_t page_size);
1300Sigor@sysoev.ru static void nxt_mem_zone_slot_init(nxt_mem_zone_slot_t *slot,
1310Sigor@sysoev.ru     nxt_uint_t page_size);
1325Sigor@sysoev.ru static intptr_t nxt_mem_zone_rbtree_compare(nxt_rbtree_node_t *node1,
1330Sigor@sysoev.ru     nxt_rbtree_node_t *node2);
1340Sigor@sysoev.ru static void *nxt_mem_zone_alloc_small(nxt_mem_zone_t *zone,
1350Sigor@sysoev.ru     nxt_mem_zone_slot_t *slot, size_t size);
1360Sigor@sysoev.ru static nxt_uint_t nxt_mem_zone_alloc_chunk(uint8_t *map, nxt_uint_t offset,
1370Sigor@sysoev.ru     nxt_uint_t size);
1380Sigor@sysoev.ru static void *nxt_mem_zone_alloc_large(nxt_mem_zone_t *zone, size_t alignment,
1390Sigor@sysoev.ru     size_t size);
1400Sigor@sysoev.ru static nxt_mem_zone_page_t *nxt_mem_zone_alloc_pages(nxt_mem_zone_t *zone,
1410Sigor@sysoev.ru     size_t alignment, uint32_t pages);
1420Sigor@sysoev.ru static nxt_mem_zone_free_block_t *
1430Sigor@sysoev.ru     nxt_mem_zone_find_free_block(nxt_mem_zone_t *zone, nxt_rbtree_node_t *node,
1440Sigor@sysoev.ru     uint32_t alignment, uint32_t pages);
1450Sigor@sysoev.ru static const char *nxt_mem_zone_free_chunk(nxt_mem_zone_t *zone,
1460Sigor@sysoev.ru     nxt_mem_zone_page_t *page, void *p);
1470Sigor@sysoev.ru static void nxt_mem_zone_free_pages(nxt_mem_zone_t *zone,
1480Sigor@sysoev.ru     nxt_mem_zone_page_t *page, nxt_uint_t count);
1490Sigor@sysoev.ru 
1500Sigor@sysoev.ru 
1510Sigor@sysoev.ru static nxt_log_moderation_t  nxt_mem_zone_log_moderation = {
1520Sigor@sysoev.ru     NXT_LOG_ALERT, 2, "mem_zone_alloc() failed, not enough memory",
1530Sigor@sysoev.ru     NXT_LOG_MODERATION
1540Sigor@sysoev.ru };
1550Sigor@sysoev.ru 
1560Sigor@sysoev.ru 
1570Sigor@sysoev.ru nxt_mem_zone_t *
nxt_mem_zone_init(u_char * start,size_t zone_size,nxt_uint_t page_size)1580Sigor@sysoev.ru nxt_mem_zone_init(u_char *start, size_t zone_size, nxt_uint_t page_size)
1590Sigor@sysoev.ru {
1600Sigor@sysoev.ru     uint32_t                   pages;
1610Sigor@sysoev.ru     nxt_uint_t                 n;
1620Sigor@sysoev.ru     nxt_mem_zone_t             *zone;
1630Sigor@sysoev.ru     nxt_mem_zone_page_t        *page;
1640Sigor@sysoev.ru     nxt_mem_zone_free_block_t  *block;
1650Sigor@sysoev.ru 
1660Sigor@sysoev.ru     if (nxt_slow_path((page_size & (page_size - 1)) != 0)) {
1670Sigor@sysoev.ru         nxt_thread_log_alert("mem zone page size must be a power of 2");
1680Sigor@sysoev.ru         return NULL;
1690Sigor@sysoev.ru     }
1700Sigor@sysoev.ru 
1710Sigor@sysoev.ru     pages = nxt_mem_zone_pages(start, zone_size, page_size);
1720Sigor@sysoev.ru     if (pages == 0) {
1730Sigor@sysoev.ru         return NULL;
1740Sigor@sysoev.ru     }
1750Sigor@sysoev.ru 
1760Sigor@sysoev.ru     zone = (nxt_mem_zone_t *) start;
1770Sigor@sysoev.ru 
1780Sigor@sysoev.ru     /* The function returns address after all slots. */
1790Sigor@sysoev.ru     page = nxt_mem_zone_slots_init(zone, page_size);
1800Sigor@sysoev.ru 
1810Sigor@sysoev.ru     zone->pages = page;
1820Sigor@sysoev.ru 
1830Sigor@sysoev.ru     for (n = 0; n < pages; n++) {
1840Sigor@sysoev.ru         page[n].size = NXT_MEM_ZONE_PAGE_FRESH;
1850Sigor@sysoev.ru     }
1860Sigor@sysoev.ru 
1870Sigor@sysoev.ru     /*
1880Sigor@sysoev.ru      * A special sentinel page entry marked as used does not correspond
1890Sigor@sysoev.ru      * to a real page.  The entry simplifies neighbour queue nodes check
1900Sigor@sysoev.ru      * in nxt_mem_zone_free_pages().
1910Sigor@sysoev.ru      */
1920Sigor@sysoev.ru     zone->sentinel_page.size = NXT_MEM_ZONE_PAGE_USED;
1930Sigor@sysoev.ru     nxt_queue_sentinel(&zone->sentinel_page.link);
1940Sigor@sysoev.ru     nxt_queue_insert_after(&zone->sentinel_page.link, &page->link);
1950Sigor@sysoev.ru 
1960Sigor@sysoev.ru     /* rbtree of free pages. */
1970Sigor@sysoev.ru 
1985Sigor@sysoev.ru     nxt_rbtree_init(&zone->free_pages, nxt_mem_zone_rbtree_compare);
1990Sigor@sysoev.ru 
2000Sigor@sysoev.ru     block = (nxt_mem_zone_free_block_t *) zone->start;
2010Sigor@sysoev.ru     block->size = pages;
2020Sigor@sysoev.ru 
2030Sigor@sysoev.ru     nxt_rbtree_insert(&zone->free_pages, &block->node);
2040Sigor@sysoev.ru 
2050Sigor@sysoev.ru     return zone;
2060Sigor@sysoev.ru }
2070Sigor@sysoev.ru 
2080Sigor@sysoev.ru 
2090Sigor@sysoev.ru static uint32_t
nxt_mem_zone_pages(u_char * start,size_t zone_size,nxt_uint_t page_size)2100Sigor@sysoev.ru nxt_mem_zone_pages(u_char *start, size_t zone_size, nxt_uint_t page_size)
2110Sigor@sysoev.ru {
2120Sigor@sysoev.ru     u_char          *end;
2130Sigor@sysoev.ru     size_t          reserved;
2140Sigor@sysoev.ru     nxt_uint_t      n, pages, size, chunks, last;
2150Sigor@sysoev.ru     nxt_mem_zone_t  *zone;
2160Sigor@sysoev.ru 
2170Sigor@sysoev.ru     /*
2180Sigor@sysoev.ru      * Find all maximum chunk sizes which zone page can be split on
2190Sigor@sysoev.ru      * with minimum 16-byte step.
2200Sigor@sysoev.ru      */
2210Sigor@sysoev.ru     last = page_size / 16;
2220Sigor@sysoev.ru     n = 0;
2230Sigor@sysoev.ru     size = 32;
2240Sigor@sysoev.ru 
2250Sigor@sysoev.ru     do {
2260Sigor@sysoev.ru         chunks = page_size / size;
2270Sigor@sysoev.ru 
2280Sigor@sysoev.ru         if (last != chunks) {
2290Sigor@sysoev.ru             last = chunks;
2300Sigor@sysoev.ru             n++;
2310Sigor@sysoev.ru         }
2320Sigor@sysoev.ru 
2330Sigor@sysoev.ru         size += 16;
2340Sigor@sysoev.ru 
2350Sigor@sysoev.ru     } while (chunks > 1);
2360Sigor@sysoev.ru 
2370Sigor@sysoev.ru     /*
2380Sigor@sysoev.ru      * Find number of usable zone pages except zone bookkeeping data,
2390Sigor@sysoev.ru      * slots, and pages entries.
2400Sigor@sysoev.ru      */
2410Sigor@sysoev.ru     reserved = sizeof(nxt_mem_zone_t) + (n * sizeof(nxt_mem_zone_slot_t));
2420Sigor@sysoev.ru 
2430Sigor@sysoev.ru     end = nxt_trunc_ptr(start + zone_size, page_size);
2440Sigor@sysoev.ru     zone_size = end - start;
2450Sigor@sysoev.ru 
2460Sigor@sysoev.ru     pages = (zone_size - reserved) / (page_size + sizeof(nxt_mem_zone_page_t));
2470Sigor@sysoev.ru 
2480Sigor@sysoev.ru     if (reserved > zone_size || pages == 0) {
2490Sigor@sysoev.ru         nxt_thread_log_alert("mem zone size is too small: %uz", zone_size);
2500Sigor@sysoev.ru         return 0;
2510Sigor@sysoev.ru     }
2520Sigor@sysoev.ru 
2530Sigor@sysoev.ru     reserved += pages * sizeof(nxt_mem_zone_page_t);
2540Sigor@sysoev.ru     nxt_memzero(start, reserved);
2550Sigor@sysoev.ru 
2560Sigor@sysoev.ru     zone = (nxt_mem_zone_t *) start;
2570Sigor@sysoev.ru 
2580Sigor@sysoev.ru     zone->start = nxt_align_ptr(start + reserved, page_size);
2590Sigor@sysoev.ru     zone->end = end;
2600Sigor@sysoev.ru 
2610Sigor@sysoev.ru     nxt_thread_log_debug("mem zone pages: %uD, unused:%z", pages,
2620Sigor@sysoev.ru                          end - (zone->start + pages * page_size));
2630Sigor@sysoev.ru 
2640Sigor@sysoev.ru     /*
2650Sigor@sysoev.ru      * If a chunk size is lesser than zone->small_bitmap_min_size
2660Sigor@sysoev.ru      * bytes, a page's chunk bitmap is larger than 32 bits and the
2670Sigor@sysoev.ru      * bimap is placed at the start of the page.
2680Sigor@sysoev.ru      */
2690Sigor@sysoev.ru     zone->small_bitmap_min_size = page_size / 32;
2700Sigor@sysoev.ru 
2710Sigor@sysoev.ru     zone->page_size_mask = page_size - 1;
2720Sigor@sysoev.ru     zone->max_chunk_size = page_size / 2;
2730Sigor@sysoev.ru 
2740Sigor@sysoev.ru     n = zone->max_chunk_size;
2750Sigor@sysoev.ru 
2760Sigor@sysoev.ru     do {
2770Sigor@sysoev.ru         zone->page_size_shift++;
2780Sigor@sysoev.ru         n /= 2;
2790Sigor@sysoev.ru     } while (n != 0);
2800Sigor@sysoev.ru 
2810Sigor@sysoev.ru     return (uint32_t) pages;
2820Sigor@sysoev.ru }
2830Sigor@sysoev.ru 
2840Sigor@sysoev.ru 
2850Sigor@sysoev.ru static void *
nxt_mem_zone_slots_init(nxt_mem_zone_t * zone,nxt_uint_t page_size)2860Sigor@sysoev.ru nxt_mem_zone_slots_init(nxt_mem_zone_t *zone, nxt_uint_t page_size)
2870Sigor@sysoev.ru {
2880Sigor@sysoev.ru     nxt_uint_t           n, size, chunks;
2890Sigor@sysoev.ru     nxt_mem_zone_slot_t  *slot;
2900Sigor@sysoev.ru 
2910Sigor@sysoev.ru     slot = zone->slots;
2920Sigor@sysoev.ru 
2930Sigor@sysoev.ru     slot[0].chunks = page_size / 16;
2940Sigor@sysoev.ru     slot[0].size = 16;
2950Sigor@sysoev.ru 
2960Sigor@sysoev.ru     n = 0;
2970Sigor@sysoev.ru     size = 32;
2980Sigor@sysoev.ru 
2990Sigor@sysoev.ru     for ( ;; ) {
3000Sigor@sysoev.ru         chunks = page_size / size;
3010Sigor@sysoev.ru 
3020Sigor@sysoev.ru         if (slot[n].chunks != chunks) {
3030Sigor@sysoev.ru 
3040Sigor@sysoev.ru             nxt_mem_zone_slot_init(&slot[n], page_size);
3050Sigor@sysoev.ru 
3060Sigor@sysoev.ru             nxt_thread_log_debug(
3070Sigor@sysoev.ru                            "mem zone size:%uD chunks:%uD start:%uD map:%uD",
3080Sigor@sysoev.ru                            slot[n].size, slot[n].chunks + 1,
3090Sigor@sysoev.ru                            slot[n].start, slot[n].map_size);
3100Sigor@sysoev.ru 
3110Sigor@sysoev.ru             n++;
3120Sigor@sysoev.ru 
3130Sigor@sysoev.ru             if (chunks == 1) {
3140Sigor@sysoev.ru                 return &slot[n];
3150Sigor@sysoev.ru             }
3160Sigor@sysoev.ru         }
3170Sigor@sysoev.ru 
3180Sigor@sysoev.ru         slot[n].chunks = chunks;
3190Sigor@sysoev.ru         slot[n].size = size;
3200Sigor@sysoev.ru         size += 16;
3210Sigor@sysoev.ru     }
3220Sigor@sysoev.ru }
3230Sigor@sysoev.ru 
3240Sigor@sysoev.ru 
3250Sigor@sysoev.ru static void
nxt_mem_zone_slot_init(nxt_mem_zone_slot_t * slot,nxt_uint_t page_size)3260Sigor@sysoev.ru nxt_mem_zone_slot_init(nxt_mem_zone_slot_t *slot, nxt_uint_t page_size)
3270Sigor@sysoev.ru {
3280Sigor@sysoev.ru     /*
3290Sigor@sysoev.ru      * Calculate number of bytes required to store a chunk bitmap
3300Sigor@sysoev.ru      * and align it to 4 bytes.
3310Sigor@sysoev.ru      */
3320Sigor@sysoev.ru     slot->map_size = nxt_align_size(((slot->chunks + 7) / 8), 4);
3330Sigor@sysoev.ru 
3340Sigor@sysoev.ru     /* If chunk size is not a multiple of zone page size, there
3350Sigor@sysoev.ru      * is surplus space which can be used for the chunk's bitmap.
3360Sigor@sysoev.ru      */
3370Sigor@sysoev.ru     slot->start = page_size - slot->chunks * slot->size;
3380Sigor@sysoev.ru 
3390Sigor@sysoev.ru     /* slot->chunks should be one less than actual number of chunks. */
3400Sigor@sysoev.ru     slot->chunks--;
3410Sigor@sysoev.ru 
3420Sigor@sysoev.ru     if (slot->map_size > 4) {
3430Sigor@sysoev.ru         /* A page's chunks bitmap is placed at the start of the page. */
3440Sigor@sysoev.ru 
3450Sigor@sysoev.ru         if (slot->start < slot->map_size) {
3460Sigor@sysoev.ru             /*
3470Sigor@sysoev.ru              * There is no surplus space or the space is too
3480Sigor@sysoev.ru              * small for chunks bitmap, so use the first chunks.
3490Sigor@sysoev.ru              */
3500Sigor@sysoev.ru             if (slot->size < slot->map_size) {
3510Sigor@sysoev.ru                 /* The first chunks are occupied by bitmap. */
3520Sigor@sysoev.ru                 slot->chunks -= slot->map_size / slot->size;
3530Sigor@sysoev.ru                 slot->start = nxt_align_size(slot->map_size, 16);
3540Sigor@sysoev.ru 
3550Sigor@sysoev.ru             } else {
3560Sigor@sysoev.ru                 /* The first chunk is occupied by bitmap. */
3570Sigor@sysoev.ru                 slot->chunks--;
3580Sigor@sysoev.ru                 slot->start = slot->size;
3590Sigor@sysoev.ru             }
3600Sigor@sysoev.ru         }
3610Sigor@sysoev.ru     }
3620Sigor@sysoev.ru }
3630Sigor@sysoev.ru 
3640Sigor@sysoev.ru 
3650Sigor@sysoev.ru /*
3660Sigor@sysoev.ru  * Round up to the next highest power of 2.  The algorithm is
3670Sigor@sysoev.ru  * described in "Bit Twiddling Hacks" by Sean Eron Anderson.
3680Sigor@sysoev.ru  */
3690Sigor@sysoev.ru 
3700Sigor@sysoev.ru nxt_inline uint32_t
nxt_next_highest_power_of_two(uint32_t n)3710Sigor@sysoev.ru nxt_next_highest_power_of_two(uint32_t n)
3720Sigor@sysoev.ru {
3730Sigor@sysoev.ru     n--;
3740Sigor@sysoev.ru     n |= n >> 1;
3750Sigor@sysoev.ru     n |= n >> 2;
3760Sigor@sysoev.ru     n |= n >> 4;
3770Sigor@sysoev.ru     n |= n >> 8;
3780Sigor@sysoev.ru     n |= n >> 16;
3790Sigor@sysoev.ru     n++;
3800Sigor@sysoev.ru 
3810Sigor@sysoev.ru     return n;
3820Sigor@sysoev.ru }
3830Sigor@sysoev.ru 
3840Sigor@sysoev.ru 
3855Sigor@sysoev.ru static intptr_t
nxt_mem_zone_rbtree_compare(nxt_rbtree_node_t * node1,nxt_rbtree_node_t * node2)3860Sigor@sysoev.ru nxt_mem_zone_rbtree_compare(nxt_rbtree_node_t *node1, nxt_rbtree_node_t *node2)
3870Sigor@sysoev.ru {
3880Sigor@sysoev.ru     u_char                     *start1, *end1, *start2, *end2;
3890Sigor@sysoev.ru     uint32_t                   n, size, size1, size2;
3900Sigor@sysoev.ru     nxt_mem_zone_free_block_t  *block1, *block2;
3910Sigor@sysoev.ru 
3920Sigor@sysoev.ru     block1 = (nxt_mem_zone_free_block_t *) node1;
3930Sigor@sysoev.ru     block2 = (nxt_mem_zone_free_block_t *) node2;
3940Sigor@sysoev.ru 
3950Sigor@sysoev.ru     size1 = block1->size;
3960Sigor@sysoev.ru     size2 = block2->size;
3970Sigor@sysoev.ru 
3980Sigor@sysoev.ru     /*
3990Sigor@sysoev.ru      * This subtractions do not overflow if number of pages of a free
4000Sigor@sysoev.ru      * block is below 2^31-1.  This allows to use blocks up to 128G if
4010Sigor@sysoev.ru      * a zone page size is just 64 bytes.
4020Sigor@sysoev.ru      */
4030Sigor@sysoev.ru     n = size1 - size2;
4040Sigor@sysoev.ru 
4050Sigor@sysoev.ru     if (n != 0) {
4060Sigor@sysoev.ru         return n;
4070Sigor@sysoev.ru     }
4080Sigor@sysoev.ru 
4090Sigor@sysoev.ru     /*
4100Sigor@sysoev.ru      * Sort equally sized blocks by their capability to allocate memory with
4110Sigor@sysoev.ru      * alignment equal to the size rounded the previous higest power of 2.
4120Sigor@sysoev.ru      */
4130Sigor@sysoev.ru 
4140Sigor@sysoev.ru     /* Round the size to the previous higest power of two. */
4150Sigor@sysoev.ru     size = nxt_next_highest_power_of_two(size1) >> 1;
4160Sigor@sysoev.ru 
4170Sigor@sysoev.ru     /* Align the blocks' start and end to the rounded size. */
4180Sigor@sysoev.ru     start1 = nxt_align_ptr(block1, size);
4190Sigor@sysoev.ru     end1 = nxt_trunc_ptr((u_char *) block1 + size1, size);
4200Sigor@sysoev.ru 
4210Sigor@sysoev.ru     start2 = nxt_align_ptr(block2, size);
4220Sigor@sysoev.ru     end2 = nxt_trunc_ptr((u_char *) block2 + size2, size);
4230Sigor@sysoev.ru 
4240Sigor@sysoev.ru     return (end1 - start1) - (end2 - start2);
4250Sigor@sysoev.ru }
4260Sigor@sysoev.ru 
4270Sigor@sysoev.ru 
4280Sigor@sysoev.ru void *
nxt_mem_zone_zalloc(nxt_mem_zone_t * zone,size_t size)4290Sigor@sysoev.ru nxt_mem_zone_zalloc(nxt_mem_zone_t *zone, size_t size)
4300Sigor@sysoev.ru {
4310Sigor@sysoev.ru     void  *p;
4320Sigor@sysoev.ru 
4330Sigor@sysoev.ru     p = nxt_mem_zone_align(zone, 1, size);
4340Sigor@sysoev.ru 
4350Sigor@sysoev.ru     if (nxt_fast_path(p != NULL)) {
4360Sigor@sysoev.ru         nxt_memzero(p, size);
4370Sigor@sysoev.ru     }
4380Sigor@sysoev.ru 
4390Sigor@sysoev.ru     return p;
4400Sigor@sysoev.ru }
4410Sigor@sysoev.ru 
4420Sigor@sysoev.ru 
4430Sigor@sysoev.ru void *
nxt_mem_zone_align(nxt_mem_zone_t * zone,size_t alignment,size_t size)4440Sigor@sysoev.ru nxt_mem_zone_align(nxt_mem_zone_t *zone, size_t alignment, size_t size)
4450Sigor@sysoev.ru {
4460Sigor@sysoev.ru     void                 *p;
4470Sigor@sysoev.ru     nxt_mem_zone_slot_t  *slot;
4480Sigor@sysoev.ru 
4490Sigor@sysoev.ru     if (nxt_slow_path((alignment - 1) & alignment) != 0) {
4500Sigor@sysoev.ru         /* Alignment must be a power of 2. */
4510Sigor@sysoev.ru         return NULL;
4520Sigor@sysoev.ru     }
4530Sigor@sysoev.ru 
4540Sigor@sysoev.ru     if (size <= zone->max_chunk_size && alignment <= zone->max_chunk_size) {
4550Sigor@sysoev.ru         /* All chunks are aligned to 16. */
4560Sigor@sysoev.ru 
4570Sigor@sysoev.ru         if (alignment > 16) {
4580Sigor@sysoev.ru             /*
4590Sigor@sysoev.ru              * Chunks which size is power of 2 are aligned to the size.
4600Sigor@sysoev.ru              * So allocation size should be increased to the next highest
4610Sigor@sysoev.ru              * power of two.  This can waste memory, but a main consumer
4620Sigor@sysoev.ru              * of aligned allocations is lvlhsh which anyway allocates
4630Sigor@sysoev.ru              * memory with alignment equal to size.
4640Sigor@sysoev.ru              */
4650Sigor@sysoev.ru             size = nxt_next_highest_power_of_two(size);
4660Sigor@sysoev.ru             size = nxt_max(size, alignment);
4670Sigor@sysoev.ru         }
4680Sigor@sysoev.ru 
4690Sigor@sysoev.ru         /*
4700Sigor@sysoev.ru          * Find a zone slot with appropriate chunk size.
4710Sigor@sysoev.ru          * This operation can be performed without holding lock.
4720Sigor@sysoev.ru          */
4730Sigor@sysoev.ru         for (slot = zone->slots; slot->size < size; slot++) { /* void */ }
4740Sigor@sysoev.ru 
4750Sigor@sysoev.ru         nxt_thread_log_debug("mem zone alloc: @%uz:%uz chunk:%uD",
4760Sigor@sysoev.ru                              alignment, size, slot->size);
4770Sigor@sysoev.ru 
4780Sigor@sysoev.ru         nxt_thread_spin_lock(&zone->lock);
4790Sigor@sysoev.ru 
4800Sigor@sysoev.ru         p = nxt_mem_zone_alloc_small(zone, slot, size);
4810Sigor@sysoev.ru 
4820Sigor@sysoev.ru     } else {
4830Sigor@sysoev.ru 
4840Sigor@sysoev.ru         nxt_thread_log_debug("mem zone alloc: @%uz:%uz", alignment, size);
4850Sigor@sysoev.ru 
4860Sigor@sysoev.ru         nxt_thread_spin_lock(&zone->lock);
4870Sigor@sysoev.ru 
4880Sigor@sysoev.ru         p = nxt_mem_zone_alloc_large(zone, alignment, size);
4890Sigor@sysoev.ru     }
4900Sigor@sysoev.ru 
4910Sigor@sysoev.ru     nxt_thread_spin_unlock(&zone->lock);
4920Sigor@sysoev.ru 
4930Sigor@sysoev.ru     if (nxt_fast_path(p != NULL)) {
4940Sigor@sysoev.ru         nxt_thread_log_debug("mem zone alloc: %p", p);
4950Sigor@sysoev.ru 
4960Sigor@sysoev.ru     } else {
497564Svbart@nginx.com         nxt_log_alert_moderate(&nxt_mem_zone_log_moderation, nxt_thread_log(),
4980Sigor@sysoev.ru                     "nxt_mem_zone_alloc(%uz, %uz) failed, not enough memory",
4990Sigor@sysoev.ru                     alignment, size);
5000Sigor@sysoev.ru     }
5010Sigor@sysoev.ru 
5020Sigor@sysoev.ru     return p;
5030Sigor@sysoev.ru }
5040Sigor@sysoev.ru 
5050Sigor@sysoev.ru 
5060Sigor@sysoev.ru static void *
nxt_mem_zone_alloc_small(nxt_mem_zone_t * zone,nxt_mem_zone_slot_t * slot,size_t size)5070Sigor@sysoev.ru nxt_mem_zone_alloc_small(nxt_mem_zone_t *zone, nxt_mem_zone_slot_t *slot,
5080Sigor@sysoev.ru     size_t size)
5090Sigor@sysoev.ru {
5100Sigor@sysoev.ru     u_char               *p;
5110Sigor@sysoev.ru     uint8_t              *map;
5120Sigor@sysoev.ru     nxt_mem_zone_page_t  *page;
5130Sigor@sysoev.ru 
5140Sigor@sysoev.ru     page = slot->pages;
5150Sigor@sysoev.ru 
5160Sigor@sysoev.ru     if (nxt_fast_path(page != NULL)) {
5170Sigor@sysoev.ru 
5180Sigor@sysoev.ru         p = nxt_mem_zone_page_addr(zone, page);
5190Sigor@sysoev.ru 
5200Sigor@sysoev.ru         if (nxt_mem_zone_page_bitmap(zone, slot)) {
5210Sigor@sysoev.ru             /* A page's chunks bitmap is placed at the start of the page. */
5220Sigor@sysoev.ru             map = p;
5230Sigor@sysoev.ru 
5240Sigor@sysoev.ru         } else {
5250Sigor@sysoev.ru             map = page->u.map;
5260Sigor@sysoev.ru         }
5270Sigor@sysoev.ru 
5280Sigor@sysoev.ru         p += nxt_mem_zone_alloc_chunk(map, slot->start, slot->size);
5290Sigor@sysoev.ru 
5300Sigor@sysoev.ru         page->chunks--;
5310Sigor@sysoev.ru 
5320Sigor@sysoev.ru         if (page->chunks == 0) {
5330Sigor@sysoev.ru             /*
5340Sigor@sysoev.ru              * Remove full page from the zone slot list of pages with
5350Sigor@sysoev.ru              * free chunks.
5360Sigor@sysoev.ru              */
5370Sigor@sysoev.ru             slot->pages = page->next;
5380Sigor@sysoev.ru #if (NXT_DEBUG)
5390Sigor@sysoev.ru             page->next = NULL;
5400Sigor@sysoev.ru #endif
5410Sigor@sysoev.ru         }
5420Sigor@sysoev.ru 
5430Sigor@sysoev.ru         return p;
5440Sigor@sysoev.ru     }
5450Sigor@sysoev.ru 
5460Sigor@sysoev.ru     page = nxt_mem_zone_alloc_pages(zone, 1, 1);
5470Sigor@sysoev.ru 
5480Sigor@sysoev.ru     if (nxt_fast_path(page != NULL)) {
5490Sigor@sysoev.ru 
5500Sigor@sysoev.ru         slot->pages = page;
5510Sigor@sysoev.ru 
5520Sigor@sysoev.ru         page->size = slot->size;
5530Sigor@sysoev.ru         /* slot->chunks are already one less. */
5540Sigor@sysoev.ru         page->chunks = slot->chunks;
5550Sigor@sysoev.ru         page->u.count = 0;
5560Sigor@sysoev.ru         page->next = NULL;
5570Sigor@sysoev.ru 
5580Sigor@sysoev.ru         p = nxt_mem_zone_page_addr(zone, page);
5590Sigor@sysoev.ru 
5600Sigor@sysoev.ru         if (nxt_mem_zone_page_bitmap(zone, slot)) {
5610Sigor@sysoev.ru             /* A page's chunks bitmap is placed at the start of the page. */
5620Sigor@sysoev.ru             map = p;
5630Sigor@sysoev.ru             nxt_memzero(map, slot->map_size);
5640Sigor@sysoev.ru 
5650Sigor@sysoev.ru         } else {
5660Sigor@sysoev.ru             map = page->u.map;
5670Sigor@sysoev.ru         }
5680Sigor@sysoev.ru 
5690Sigor@sysoev.ru         /* Mark the first chunk as busy. */
5700Sigor@sysoev.ru         map[0] = 0x80;
5710Sigor@sysoev.ru 
5720Sigor@sysoev.ru         return p + slot->start;
5730Sigor@sysoev.ru     }
5740Sigor@sysoev.ru 
5750Sigor@sysoev.ru     return NULL;
5760Sigor@sysoev.ru }
5770Sigor@sysoev.ru 
5780Sigor@sysoev.ru 
5790Sigor@sysoev.ru static nxt_uint_t
nxt_mem_zone_alloc_chunk(uint8_t * map,nxt_uint_t offset,nxt_uint_t size)5800Sigor@sysoev.ru nxt_mem_zone_alloc_chunk(uint8_t *map, nxt_uint_t offset, nxt_uint_t size)
5810Sigor@sysoev.ru {
5820Sigor@sysoev.ru     uint8_t     mask;
5830Sigor@sysoev.ru     nxt_uint_t  n;
5840Sigor@sysoev.ru 
5850Sigor@sysoev.ru     n = 0;
5860Sigor@sysoev.ru 
5870Sigor@sysoev.ru     /* The page must have at least one free chunk. */
5880Sigor@sysoev.ru 
5890Sigor@sysoev.ru     for ( ;; ) {
5900Sigor@sysoev.ru         /* The bitmap is always aligned to uint32_t. */
5910Sigor@sysoev.ru 
592611Svbart@nginx.com         if (*(uint32_t *) &map[n] != 0xFFFFFFFF) {
5930Sigor@sysoev.ru 
5940Sigor@sysoev.ru             do {
595611Svbart@nginx.com                 if (map[n] != 0xFF) {
5960Sigor@sysoev.ru 
5970Sigor@sysoev.ru                     mask = 0x80;
5980Sigor@sysoev.ru 
5990Sigor@sysoev.ru                     do {
6000Sigor@sysoev.ru                         if ((map[n] & mask) == 0) {
6010Sigor@sysoev.ru                             /* The free chunk is found. */
6020Sigor@sysoev.ru                             map[n] |= mask;
6030Sigor@sysoev.ru                             return offset;
6040Sigor@sysoev.ru                         }
6050Sigor@sysoev.ru 
6060Sigor@sysoev.ru                         offset += size;
6070Sigor@sysoev.ru                         mask >>= 1;
6080Sigor@sysoev.ru 
6090Sigor@sysoev.ru                     } while (mask != 0);
6100Sigor@sysoev.ru 
6110Sigor@sysoev.ru                 } else {
6120Sigor@sysoev.ru                     /* Fast-forward: all 8 chunks are occupied. */
6130Sigor@sysoev.ru                     offset += size * 8;
6140Sigor@sysoev.ru                 }
6150Sigor@sysoev.ru 
6160Sigor@sysoev.ru                 n++;
6170Sigor@sysoev.ru 
6180Sigor@sysoev.ru             } while (n % 4 != 0);
6190Sigor@sysoev.ru 
6200Sigor@sysoev.ru         } else {
6210Sigor@sysoev.ru             /* Fast-forward: all 32 chunks are occupied. */
6220Sigor@sysoev.ru             offset += size * 32;
6230Sigor@sysoev.ru             n += 4;
6240Sigor@sysoev.ru         }
6250Sigor@sysoev.ru     }
6260Sigor@sysoev.ru }
6270Sigor@sysoev.ru 
6280Sigor@sysoev.ru 
6290Sigor@sysoev.ru static void *
nxt_mem_zone_alloc_large(nxt_mem_zone_t * zone,size_t alignment,size_t size)6300Sigor@sysoev.ru nxt_mem_zone_alloc_large(nxt_mem_zone_t *zone, size_t alignment, size_t size)
6310Sigor@sysoev.ru {
6320Sigor@sysoev.ru     uint32_t             pages;
6330Sigor@sysoev.ru     nxt_mem_zone_page_t  *page;
6340Sigor@sysoev.ru 
6350Sigor@sysoev.ru     pages = (size + zone->page_size_mask) >> zone->page_size_shift;
6360Sigor@sysoev.ru 
6370Sigor@sysoev.ru     page = nxt_mem_zone_alloc_pages(zone, alignment, pages);
6380Sigor@sysoev.ru 
6390Sigor@sysoev.ru     if (nxt_fast_path(page != NULL)) {
6400Sigor@sysoev.ru         return nxt_mem_zone_page_addr(zone, page);
6410Sigor@sysoev.ru     }
6420Sigor@sysoev.ru 
6430Sigor@sysoev.ru     return NULL;
6440Sigor@sysoev.ru }
6450Sigor@sysoev.ru 
6460Sigor@sysoev.ru 
6470Sigor@sysoev.ru static nxt_mem_zone_page_t *
nxt_mem_zone_alloc_pages(nxt_mem_zone_t * zone,size_t alignment,uint32_t pages)6480Sigor@sysoev.ru nxt_mem_zone_alloc_pages(nxt_mem_zone_t *zone, size_t alignment, uint32_t pages)
6490Sigor@sysoev.ru {
6500Sigor@sysoev.ru     u_char                     *p;
6510Sigor@sysoev.ru     size_t                     prev_size;
6520Sigor@sysoev.ru     uint32_t                   prev_pages, node_pages, next_pages;
6530Sigor@sysoev.ru     nxt_uint_t                 n;
6540Sigor@sysoev.ru     nxt_mem_zone_page_t        *prev_page, *page, *next_page;
6550Sigor@sysoev.ru     nxt_mem_zone_free_block_t  *block, *next_block;
6560Sigor@sysoev.ru 
6570Sigor@sysoev.ru     block = nxt_mem_zone_find_free_block(zone,
6580Sigor@sysoev.ru                                          nxt_rbtree_root(&zone->free_pages),
6590Sigor@sysoev.ru                                          alignment, pages);
6600Sigor@sysoev.ru 
6610Sigor@sysoev.ru     if (nxt_slow_path(block == NULL)) {
6620Sigor@sysoev.ru         return NULL;
6630Sigor@sysoev.ru     }
6640Sigor@sysoev.ru 
6650Sigor@sysoev.ru     node_pages = block->size;
6660Sigor@sysoev.ru 
6670Sigor@sysoev.ru     nxt_rbtree_delete(&zone->free_pages, &block->node);
6680Sigor@sysoev.ru 
6690Sigor@sysoev.ru     p = nxt_align_ptr(block, alignment);
6700Sigor@sysoev.ru     page = nxt_mem_zone_addr_page(zone, p);
6710Sigor@sysoev.ru 
6720Sigor@sysoev.ru     prev_size = p - (u_char *) block;
6730Sigor@sysoev.ru 
6740Sigor@sysoev.ru     if (prev_size != 0) {
675*2404Sa.clayton@nginx.com         prev_pages = prev_size >> zone->page_size_shift;
6760Sigor@sysoev.ru         node_pages -= prev_pages;
6770Sigor@sysoev.ru 
6780Sigor@sysoev.ru         block->size = prev_pages;
6790Sigor@sysoev.ru         nxt_rbtree_insert(&zone->free_pages, &block->node);
6800Sigor@sysoev.ru 
6810Sigor@sysoev.ru         prev_page = nxt_mem_zone_addr_page(zone, block);
6820Sigor@sysoev.ru         nxt_queue_insert_after(&prev_page->link, &page->link);
6830Sigor@sysoev.ru     }
6840Sigor@sysoev.ru 
6850Sigor@sysoev.ru     next_pages = node_pages - pages;
6860Sigor@sysoev.ru 
6870Sigor@sysoev.ru     if (next_pages != 0) {
6880Sigor@sysoev.ru         next_page = &page[pages];
6890Sigor@sysoev.ru         next_block = nxt_mem_zone_page_addr(zone, next_page);
6900Sigor@sysoev.ru         next_block->size = next_pages;
6910Sigor@sysoev.ru 
6920Sigor@sysoev.ru         nxt_rbtree_insert(&zone->free_pages, &next_block->node);
6930Sigor@sysoev.ru         nxt_queue_insert_after(&page->link, &next_page->link);
6940Sigor@sysoev.ru     }
6950Sigor@sysoev.ru 
6960Sigor@sysoev.ru     /* Go through pages after all rbtree operations to not trash CPU cache. */
6970Sigor@sysoev.ru 
6980Sigor@sysoev.ru     page[0].u.count = pages;
6990Sigor@sysoev.ru 
7000Sigor@sysoev.ru     for (n = 0; n < pages; n++) {
7010Sigor@sysoev.ru 
7020Sigor@sysoev.ru         if (page[n].size == NXT_MEM_ZONE_PAGE_FRESH) {
7030Sigor@sysoev.ru             nxt_mem_zone_fresh_junk(nxt_mem_zone_page_addr(zone, &page[n]),
7040Sigor@sysoev.ru                                     zone->page_size_mask + 1);
7050Sigor@sysoev.ru         }
7060Sigor@sysoev.ru 
7070Sigor@sysoev.ru         page[n].size = NXT_MEM_ZONE_PAGE_USED;
7080Sigor@sysoev.ru     }
7090Sigor@sysoev.ru 
7100Sigor@sysoev.ru     return page;
7110Sigor@sysoev.ru }
7120Sigor@sysoev.ru 
7130Sigor@sysoev.ru 
7140Sigor@sysoev.ru /*
7150Sigor@sysoev.ru  * Free blocks are sorted by size and then if the sizes are equal
7160Sigor@sysoev.ru  * by aligned allocation capabilty.  The former criterion is just
7170Sigor@sysoev.ru  * comparison with a requested size and it can be used for iteractive
7180Sigor@sysoev.ru  * search.  The later criterion cannot be tested only by the requested
7190Sigor@sysoev.ru  * size and alignment, so recursive in-order tree traversal is required
7200Sigor@sysoev.ru  * to find a suitable free block.  nxt_mem_zone_find_free_block() uses
7210Sigor@sysoev.ru  * only recursive in-order tree traversal because anyway the slowest part
7220Sigor@sysoev.ru  * of the algorithm are CPU cache misses.  Besides the last tail recursive
7230Sigor@sysoev.ru  * call may be optimized by compiler into iteractive search.
7240Sigor@sysoev.ru  */
7250Sigor@sysoev.ru 
7260Sigor@sysoev.ru 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)7270Sigor@sysoev.ru nxt_mem_zone_find_free_block(nxt_mem_zone_t *zone, nxt_rbtree_node_t *node,
7280Sigor@sysoev.ru     uint32_t alignment, uint32_t pages)
7290Sigor@sysoev.ru {
7300Sigor@sysoev.ru     u_char                     *aligned, *end;
7310Sigor@sysoev.ru     nxt_mem_zone_free_block_t  *block, *free_block;
7320Sigor@sysoev.ru 
7330Sigor@sysoev.ru     if (node == nxt_rbtree_sentinel(&zone->free_pages)) {
7340Sigor@sysoev.ru         return NULL;
7350Sigor@sysoev.ru     }
7360Sigor@sysoev.ru 
7370Sigor@sysoev.ru     block = (nxt_mem_zone_free_block_t *) node;
7380Sigor@sysoev.ru 
7390Sigor@sysoev.ru     if (pages <= block->size) {
7400Sigor@sysoev.ru 
7410Sigor@sysoev.ru         free_block = nxt_mem_zone_find_free_block(zone, block->node.left,
7420Sigor@sysoev.ru                                                   alignment, pages);
7430Sigor@sysoev.ru         if (free_block != NULL) {
7440Sigor@sysoev.ru             return free_block;
7450Sigor@sysoev.ru         }
7460Sigor@sysoev.ru 
7470Sigor@sysoev.ru         aligned = nxt_align_ptr(block, alignment);
7480Sigor@sysoev.ru 
7490Sigor@sysoev.ru         if (pages == block->size) {
7500Sigor@sysoev.ru             if (aligned == (u_char *) block) {
7510Sigor@sysoev.ru                 /* Exact match. */
7520Sigor@sysoev.ru                 return block;
7530Sigor@sysoev.ru             }
7540Sigor@sysoev.ru 
7550Sigor@sysoev.ru         } else {  /* pages < block->size */
7560Sigor@sysoev.ru             aligned += pages << zone->page_size_shift;
75798Svbart@nginx.com             end = nxt_pointer_to(block, block->size << zone->page_size_shift);
7580Sigor@sysoev.ru 
7590Sigor@sysoev.ru             if (aligned <= end) {
7600Sigor@sysoev.ru                 return block;
7610Sigor@sysoev.ru             }
7620Sigor@sysoev.ru         }
7630Sigor@sysoev.ru     }
7640Sigor@sysoev.ru 
7650Sigor@sysoev.ru     return nxt_mem_zone_find_free_block(zone, block->node.right,
7660Sigor@sysoev.ru                                         alignment, pages);
7670Sigor@sysoev.ru }
7680Sigor@sysoev.ru 
7690Sigor@sysoev.ru 
7700Sigor@sysoev.ru void
nxt_mem_zone_free(nxt_mem_zone_t * zone,void * p)7710Sigor@sysoev.ru nxt_mem_zone_free(nxt_mem_zone_t *zone, void *p)
7720Sigor@sysoev.ru {
7730Sigor@sysoev.ru     nxt_uint_t           count;
7740Sigor@sysoev.ru     const char           *err;
7750Sigor@sysoev.ru     nxt_mem_zone_page_t  *page;
7760Sigor@sysoev.ru 
7770Sigor@sysoev.ru     nxt_thread_log_debug("mem zone free: %p", p);
7780Sigor@sysoev.ru 
7790Sigor@sysoev.ru     if (nxt_fast_path(zone->start <= (u_char *) p
7800Sigor@sysoev.ru                       && (u_char *) p < zone->end))
7810Sigor@sysoev.ru     {
7820Sigor@sysoev.ru         page = nxt_mem_zone_addr_page(zone, p);
7830Sigor@sysoev.ru 
7840Sigor@sysoev.ru         nxt_thread_spin_lock(&zone->lock);
7850Sigor@sysoev.ru 
7860Sigor@sysoev.ru         if (nxt_mem_zone_page_is_chunked(page)) {
7870Sigor@sysoev.ru             err = nxt_mem_zone_free_chunk(zone, page, p);
7880Sigor@sysoev.ru 
7890Sigor@sysoev.ru         } else if (nxt_slow_path(nxt_mem_zone_page_is_free(page))) {
7900Sigor@sysoev.ru             err = "page is already free";
7910Sigor@sysoev.ru 
7920Sigor@sysoev.ru         } else if (nxt_slow_path((uintptr_t) p & zone->page_size_mask) != 0) {
7930Sigor@sysoev.ru             err = "invalid pointer to chunk";
7940Sigor@sysoev.ru 
7950Sigor@sysoev.ru         } else {
7960Sigor@sysoev.ru             count = page->u.count;
7970Sigor@sysoev.ru 
7980Sigor@sysoev.ru             if (nxt_fast_path(count != 0)) {
7990Sigor@sysoev.ru                 nxt_mem_zone_free_junk(p, count * zone->page_size_mask + 1);
8000Sigor@sysoev.ru                 nxt_mem_zone_free_pages(zone, page, count);
8010Sigor@sysoev.ru                 err = NULL;
8020Sigor@sysoev.ru 
8030Sigor@sysoev.ru             } else {
8040Sigor@sysoev.ru                 /* Not the first allocated page. */
8050Sigor@sysoev.ru                 err = "pointer to wrong page";
8060Sigor@sysoev.ru             }
8070Sigor@sysoev.ru         }
8080Sigor@sysoev.ru 
8090Sigor@sysoev.ru         nxt_thread_spin_unlock(&zone->lock);
8100Sigor@sysoev.ru 
8110Sigor@sysoev.ru     } else {
8120Sigor@sysoev.ru         err = "pointer is out of zone";
8130Sigor@sysoev.ru     }
8140Sigor@sysoev.ru 
8150Sigor@sysoev.ru     if (nxt_slow_path(err != NULL)) {
8160Sigor@sysoev.ru         nxt_thread_log_alert("nxt_mem_zone_free(%p): %s", p, err);
8170Sigor@sysoev.ru     }
8180Sigor@sysoev.ru }
8190Sigor@sysoev.ru 
8200Sigor@sysoev.ru 
8210Sigor@sysoev.ru static const char *
nxt_mem_zone_free_chunk(nxt_mem_zone_t * zone,nxt_mem_zone_page_t * page,void * p)8220Sigor@sysoev.ru nxt_mem_zone_free_chunk(nxt_mem_zone_t *zone, nxt_mem_zone_page_t *page,
8230Sigor@sysoev.ru     void *p)
8240Sigor@sysoev.ru {
8250Sigor@sysoev.ru     u_char               *map;
8260Sigor@sysoev.ru     uint32_t             size, offset, chunk;
8270Sigor@sysoev.ru     nxt_mem_zone_page_t  *pg, **ppg;
8280Sigor@sysoev.ru     nxt_mem_zone_slot_t  *slot;
8290Sigor@sysoev.ru 
8300Sigor@sysoev.ru     size = page->size;
8310Sigor@sysoev.ru 
8320Sigor@sysoev.ru     /* Find a zone slot with appropriate chunk size. */
8330Sigor@sysoev.ru     for (slot = zone->slots; slot->size < size; slot++) { /* void */ }
8340Sigor@sysoev.ru 
8350Sigor@sysoev.ru     offset = (uintptr_t) p & zone->page_size_mask;
8360Sigor@sysoev.ru     offset -= slot->start;
8370Sigor@sysoev.ru 
8380Sigor@sysoev.ru     chunk = offset / size;
8390Sigor@sysoev.ru 
8400Sigor@sysoev.ru     if (nxt_slow_path(offset != chunk * size)) {
8410Sigor@sysoev.ru         return "pointer to wrong chunk";
8420Sigor@sysoev.ru     }
8430Sigor@sysoev.ru 
8440Sigor@sysoev.ru     if (nxt_mem_zone_page_bitmap(zone, slot)) {
8450Sigor@sysoev.ru         /* A page's chunks bitmap is placed at the start of the page. */
8460Sigor@sysoev.ru         map = (u_char *) ((uintptr_t) p & ~((uintptr_t) zone->page_size_mask));
8470Sigor@sysoev.ru 
8480Sigor@sysoev.ru     } else {
8490Sigor@sysoev.ru         map = page->u.map;
8500Sigor@sysoev.ru     }
8510Sigor@sysoev.ru 
8520Sigor@sysoev.ru     if (nxt_mem_zone_chunk_is_free(map, chunk)) {
8530Sigor@sysoev.ru         return "chunk is already free";
8540Sigor@sysoev.ru     }
8550Sigor@sysoev.ru 
8560Sigor@sysoev.ru     nxt_mem_zone_set_chunk_free(map, chunk);
8570Sigor@sysoev.ru 
8580Sigor@sysoev.ru     nxt_mem_zone_free_junk(p, page->size);
8590Sigor@sysoev.ru 
8600Sigor@sysoev.ru     if (page->chunks == 0) {
8610Sigor@sysoev.ru         page->chunks = 1;
8620Sigor@sysoev.ru 
8630Sigor@sysoev.ru         /* Add the page to the head of slot list of pages with free chunks. */
8640Sigor@sysoev.ru         page->next = slot->pages;
8650Sigor@sysoev.ru         slot->pages = page;
8660Sigor@sysoev.ru 
8670Sigor@sysoev.ru     } else if (page->chunks != slot->chunks) {
8680Sigor@sysoev.ru         page->chunks++;
8690Sigor@sysoev.ru 
8700Sigor@sysoev.ru     } else {
8710Sigor@sysoev.ru 
8720Sigor@sysoev.ru         if (map != page->u.map) {
8730Sigor@sysoev.ru             nxt_mem_zone_free_junk(map, slot->map_size);
8740Sigor@sysoev.ru         }
8750Sigor@sysoev.ru 
8760Sigor@sysoev.ru         /*
8770Sigor@sysoev.ru          * All chunks are free, remove the page from the slot list of pages
8780Sigor@sysoev.ru          * with free chunks and add the page to the free pages tree.
8790Sigor@sysoev.ru          */
8800Sigor@sysoev.ru         ppg = &slot->pages;
8810Sigor@sysoev.ru 
8820Sigor@sysoev.ru         for (pg = slot->pages; pg != NULL; pg = pg->next) {
8830Sigor@sysoev.ru 
8840Sigor@sysoev.ru             if (pg == page) {
8850Sigor@sysoev.ru                 *ppg = page->next;
8860Sigor@sysoev.ru                 break;
8870Sigor@sysoev.ru             }
8880Sigor@sysoev.ru 
8890Sigor@sysoev.ru             ppg = &pg->next;
8900Sigor@sysoev.ru         }
8910Sigor@sysoev.ru 
8920Sigor@sysoev.ru         nxt_mem_zone_free_pages(zone, page, 1);
8930Sigor@sysoev.ru     }
8940Sigor@sysoev.ru 
8950Sigor@sysoev.ru     return NULL;
8960Sigor@sysoev.ru }
8970Sigor@sysoev.ru 
8980Sigor@sysoev.ru 
8990Sigor@sysoev.ru static void
nxt_mem_zone_free_pages(nxt_mem_zone_t * zone,nxt_mem_zone_page_t * page,nxt_uint_t count)9000Sigor@sysoev.ru nxt_mem_zone_free_pages(nxt_mem_zone_t *zone, nxt_mem_zone_page_t *page,
9010Sigor@sysoev.ru     nxt_uint_t count)
9020Sigor@sysoev.ru {
9030Sigor@sysoev.ru     nxt_mem_zone_page_t        *prev_page, *next_page;
9040Sigor@sysoev.ru     nxt_mem_zone_free_block_t  *block, *prev_block, *next_block;
9050Sigor@sysoev.ru 
9060Sigor@sysoev.ru     page->size = NXT_MEM_ZONE_PAGE_FREE;
9070Sigor@sysoev.ru     page->chunks = 0;
9080Sigor@sysoev.ru     page->u.count = 0;
9090Sigor@sysoev.ru     page->next = NULL;
9100Sigor@sysoev.ru 
9110Sigor@sysoev.ru     nxt_memzero(&page[1], (count - 1) * sizeof(nxt_mem_zone_page_t));
9120Sigor@sysoev.ru 
9130Sigor@sysoev.ru     next_page = nxt_queue_link_data(page->link.next, nxt_mem_zone_page_t, link);
9140Sigor@sysoev.ru 
9150Sigor@sysoev.ru     if (nxt_mem_zone_page_is_free(next_page)) {
9160Sigor@sysoev.ru 
9170Sigor@sysoev.ru         /* Coalesce with the next free pages. */
9180Sigor@sysoev.ru 
9190Sigor@sysoev.ru         nxt_queue_remove(&next_page->link);
9200Sigor@sysoev.ru         nxt_memzero(next_page, sizeof(nxt_mem_zone_page_t));
9210Sigor@sysoev.ru 
9220Sigor@sysoev.ru         next_block = nxt_mem_zone_page_addr(zone, next_page);
9230Sigor@sysoev.ru         count += next_block->size;
9240Sigor@sysoev.ru         nxt_rbtree_delete(&zone->free_pages, &next_block->node);
9250Sigor@sysoev.ru     }
9260Sigor@sysoev.ru 
9270Sigor@sysoev.ru     prev_page = nxt_queue_link_data(page->link.prev, nxt_mem_zone_page_t, link);
9280Sigor@sysoev.ru 
9290Sigor@sysoev.ru     if (nxt_mem_zone_page_is_free(prev_page)) {
9300Sigor@sysoev.ru 
9310Sigor@sysoev.ru         /* Coalesce with the previous free pages. */
9320Sigor@sysoev.ru 
9330Sigor@sysoev.ru         nxt_queue_remove(&page->link);
9340Sigor@sysoev.ru 
9350Sigor@sysoev.ru         prev_block = nxt_mem_zone_page_addr(zone, prev_page);
9360Sigor@sysoev.ru         count += prev_block->size;
9370Sigor@sysoev.ru         nxt_rbtree_delete(&zone->free_pages, &prev_block->node);
9380Sigor@sysoev.ru 
9390Sigor@sysoev.ru         prev_block->size = count;
9400Sigor@sysoev.ru         nxt_rbtree_insert(&zone->free_pages, &prev_block->node);
9410Sigor@sysoev.ru 
9420Sigor@sysoev.ru         return;
9430Sigor@sysoev.ru     }
9440Sigor@sysoev.ru 
9450Sigor@sysoev.ru     block = nxt_mem_zone_page_addr(zone, page);
9460Sigor@sysoev.ru     block->size = count;
9470Sigor@sysoev.ru     nxt_rbtree_insert(&zone->free_pages, &block->node);
9480Sigor@sysoev.ru }
949