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