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