1 2 /* 3 * Copyright (C) Igor Sysoev 4 * Copyright (C) NGINX, Inc. 5 */ 6 7 #include <nxt_main.h> 8 9 10 /* 11 * A memory pool allocates memory in clusters of specified size and aligned 12 * to page_alignment. A cluster is divided on pages of specified size. Page 13 * size must be a power of 2. A page can be used entirely or can be divided 14 * on chunks of equal size. Chunk size must be a power of 2. Non-freeable 15 * memory is also allocated from pages. A cluster can contains a mix of pages 16 * with different chunk sizes and non-freeable pages. Cluster size must be 17 * a multiple of page size and may be not a power of 2. Allocations greater 18 * than page are allocated outside clusters. Start addresses and sizes of 19 * the clusters and large allocations are stored in rbtree blocks to find 20 * them on free operations. The rbtree nodes are sorted by start addresses. 21 * The rbtree is also used to destroy memory pool. 22 */ 23 24 25 typedef struct { 26 /* 27 * Used to link 28 * *) pages with free chunks in pool chunk pages lists, 29 * *) pages with free space for non-freeable allocations, 30 * *) free pages in clusters. 31 */ 32 nxt_queue_link_t link; 33 34 union { 35 /* Chunk bitmap. There can be no more than 32 chunks in a page. */ 36 uint32_t map; 37 38 /* Size of taken non-freeable space. */ 39 uint32_t taken; 40 } u; 41 42 /* 43 * Size of chunks or page shifted by pool->chunk_size_shift. Zero means 44 * that page is free, 0xFF means page with non-freeable allocations. 45 */ 46 uint8_t size; 47 48 /* Number of free chunks of a chunked page. */ 49 uint8_t chunks; 50 51 /* 52 * Number of allocation fails due to free space insufficiency 53 * in non-freeable page. 54 */ 55 uint8_t fails; 56 57 /* 58 * Page number in page cluster. 59 * There can be no more than 256 pages in a cluster. 60 */ 61 uint8_t number; 62 } nxt_mp_page_t; 63 64 65 /* 66 * Some malloc implementations (e.g. jemalloc) allocates large enough 67 * blocks (e.g. greater than 4K) with 4K alignment. So if a block 68 * descriptor will be allocated together with the block it will take 69 * excessive 4K memory. So it is better to allocate the block descriptor 70 * apart. 71 */ 72 73 typedef enum { 74 /* Block of cluster. The block is allocated apart of the cluster. */ 75 NXT_MP_CLUSTER_BLOCK = 0, 76 /* 77 * Block of large allocation. 78 * The block is allocated apart of the allocation. 79 */ 80 NXT_MP_DISCRETE_BLOCK, 81 /* 82 * Block of large allocation. 83 * The block is allocated just after of the allocation. 84 */ 85 NXT_MP_EMBEDDED_BLOCK, 86 } nxt_mp_block_type_t; 87 88 89 typedef struct { 90 NXT_RBTREE_NODE (node); 91 nxt_mp_block_type_t type:8; 92 uint8_t freeable; 93 94 /* Block size must be less than 4G. */ 95 uint32_t size; 96 97 u_char *start; 98 nxt_mp_page_t pages[]; 99 } nxt_mp_block_t; 100 101 102 struct nxt_mp_s { 103 /* rbtree of nxt_mp_block_t. */ 104 nxt_rbtree_t blocks; 105 106 uint8_t chunk_size_shift; 107 uint8_t page_size_shift; 108 uint32_t page_size; 109 uint32_t page_alignment; 110 uint32_t cluster_size; 111 uint32_t retain; 112 113 #if (NXT_DEBUG) 114 nxt_pid_t pid; 115 nxt_tid_t tid; 116 #endif 117 118 nxt_work_t *cleanup; 119 120 /* Lists of nxt_mp_page_t. */ 121 nxt_queue_t free_pages; 122 nxt_queue_t nget_pages; 123 nxt_queue_t get_pages; 124 nxt_queue_t chunk_pages[]; 125 }; 126 127 128 #define nxt_mp_chunk_get_free(map) \ 129 (__builtin_ffs(map) - 1) 130 131 132 #define nxt_mp_chunk_is_free(map, chunk) \ 133 ((map & (1 << chunk)) != 0) 134 135 136 #define nxt_mp_chunk_set_busy(map, chunk) \ 137 map &= ~(1 << chunk) 138 139 140 #define nxt_mp_chunk_set_free(map, chunk) \ 141 map |= (1 << chunk) 142 143 144 #define nxt_mp_free_junk(p, size) \ 145 memset((p), 0x5A, size) 146 147 148 #if !(NXT_DEBUG_MEMORY) 149 static void *nxt_mp_alloc_small(nxt_mp_t *mp, size_t size); 150 static void *nxt_mp_get_small(nxt_mp_t *mp, nxt_queue_t *pages, size_t size); 151 static nxt_mp_page_t *nxt_mp_alloc_page(nxt_mp_t *mp); 152 static nxt_mp_block_t *nxt_mp_alloc_cluster(nxt_mp_t *mp); 153 #endif 154 static void *nxt_mp_alloc_large(nxt_mp_t *mp, size_t alignment, size_t size, 155 nxt_bool_t freeable); 156 static intptr_t nxt_mp_rbtree_compare(nxt_rbtree_node_t *node1, 157 nxt_rbtree_node_t *node2); 158 static nxt_mp_block_t *nxt_mp_find_block(nxt_rbtree_t *tree, u_char *p); 159 static const char *nxt_mp_chunk_free(nxt_mp_t *mp, nxt_mp_block_t *cluster, 160 u_char *p); 161 162 163 #if (NXT_HAVE_BUILTIN_CLZ) 164 165 #define nxt_lg2(value) \ 166 (31 - __builtin_clz(value)) 167 168 #else 169 170 static const int nxt_lg2_tab64[64] = { 171 63, 0, 58, 1, 59, 47, 53, 2, 172 60, 39, 48, 27, 54, 33, 42, 3, 173 61, 51, 37, 40, 49, 18, 28, 20, 174 55, 30, 34, 11, 43, 14, 22, 4, 175 62, 57, 46, 52, 38, 26, 32, 41, 176 50, 36, 17, 19, 29, 10, 13, 21, 177 56, 45, 25, 31, 35, 16, 9, 12, 178 44, 24, 15, 8, 23, 7, 6, 5 179 }; 180 181 static const uint64_t nxt_lg2_magic = 0x07EDD5E59A4E28C2ULL; 182 183 static int 184 nxt_lg2(uint64_t v) 185 { 186 v |= v >> 1; 187 v |= v >> 2; 188 v |= v >> 4; 189 v |= v >> 8; 190 v |= v >> 16; 191 v |= v >> 32; 192 return nxt_lg2_tab64[ ((v - (v >> 1)) * nxt_lg2_magic) >> 58 ]; 193 } 194 195 #endif 196 197 198 #if (NXT_DEBUG) 199 200 nxt_inline void 201 nxt_mp_thread_assert(nxt_mp_t *mp) 202 { 203 nxt_tid_t tid; 204 nxt_thread_t *thread; 205 206 thread = nxt_thread(); 207 tid = nxt_thread_tid(thread); 208 209 if (nxt_fast_path(mp->tid == tid)) { 210 return; 211 } 212 213 if (nxt_slow_path(nxt_pid != mp->pid)) { 214 mp->pid = nxt_pid; 215 mp->tid = tid; 216 217 return; 218 } 219 220 nxt_log_alert(thread->log, "mem_pool locked by thread %PT", mp->tid); 221 nxt_abort(); 222 } 223 224 #else 225 226 #define nxt_mp_thread_assert(mp) 227 228 #endif 229 230 231 void 232 nxt_mp_thread_adopt(nxt_mp_t *mp) 233 { 234 #if (NXT_DEBUG) 235 mp->pid = nxt_pid; 236 mp->tid = nxt_thread_tid(nxt_thread()); 237 #endif 238 } 239 240 241 nxt_mp_t * 242 nxt_mp_create(size_t cluster_size, size_t page_alignment, size_t page_size, 243 size_t min_chunk_size) 244 { 245 nxt_mp_t *mp; 246 uint32_t pages, chunk_size_shift, page_size_shift; 247 nxt_queue_t *chunk_pages; 248 249 chunk_size_shift = nxt_lg2(min_chunk_size); 250 page_size_shift = nxt_lg2(page_size); 251 252 pages = page_size_shift - chunk_size_shift; 253 254 mp = nxt_zalloc(sizeof(nxt_mp_t) + pages * sizeof(nxt_queue_t)); 255 256 if (nxt_fast_path(mp != NULL)) { 257 mp->retain = 1; 258 mp->chunk_size_shift = chunk_size_shift; 259 mp->page_size_shift = page_size_shift; 260 mp->page_size = page_size; 261 mp->page_alignment = nxt_max(page_alignment, NXT_MAX_ALIGNMENT); 262 mp->cluster_size = cluster_size; 263 264 chunk_pages = mp->chunk_pages; 265 266 while (pages != 0) { 267 nxt_queue_init(chunk_pages); 268 chunk_pages++; 269 pages--; 270 } 271 272 nxt_queue_init(&mp->free_pages); 273 nxt_queue_init(&mp->nget_pages); 274 nxt_queue_init(&mp->get_pages); 275 276 nxt_rbtree_init(&mp->blocks, nxt_mp_rbtree_compare); 277 } 278 279 nxt_debug_alloc("mp %p create(%uz, %uz, %uz, %uz)", mp, cluster_size, 280 page_alignment, page_size, min_chunk_size); 281 282 return mp; 283 } 284 285 286 void 287 nxt_mp_retain(nxt_mp_t *mp) 288 { 289 mp->retain++; 290 291 nxt_thread_log_debug("mp %p retain: %uD", mp, mp->retain); 292 } 293 294 295 void 296 nxt_mp_release(nxt_mp_t *mp) 297 { 298 mp->retain--; 299 300 nxt_thread_log_debug("mp %p release: %uD", mp, mp->retain); 301 302 if (mp->retain == 0) { 303 nxt_mp_destroy(mp); 304 } 305 } 306 307 308 void 309 nxt_mp_destroy(nxt_mp_t *mp) 310 { 311 void *p; 312 nxt_work_t *work, *next_work; 313 nxt_mp_block_t *block; 314 nxt_rbtree_node_t *node, *next; 315 316 nxt_debug_alloc("mp %p destroy", mp); 317 318 nxt_mp_thread_assert(mp); 319 320 while (mp->cleanup != NULL) { 321 work = mp->cleanup; 322 next_work = work->next; 323 324 work->handler(work->task, work->obj, work->data); 325 326 mp->cleanup = next_work; 327 } 328 329 next = nxt_rbtree_root(&mp->blocks); 330 331 while (next != nxt_rbtree_sentinel(&mp->blocks)) { 332 333 node = nxt_rbtree_destroy_next(&mp->blocks, &next); 334 block = (nxt_mp_block_t *) node; 335 336 p = block->start; 337 338 if (block->type != NXT_MP_EMBEDDED_BLOCK) { 339 nxt_free(block); 340 } 341 342 nxt_free(p); 343 } 344 345 nxt_free(mp); 346 } 347 348 349 nxt_bool_t 350 nxt_mp_test_sizes(size_t cluster_size, size_t page_alignment, size_t page_size, 351 size_t min_chunk_size) 352 { 353 nxt_bool_t valid; 354 355 /* Alignment and sizes must be a power of 2. */ 356 357 valid = nxt_expect(1, (nxt_is_power_of_two(page_alignment) 358 && nxt_is_power_of_two(page_size) 359 && nxt_is_power_of_two(min_chunk_size))); 360 if (!valid) { 361 return 0; 362 } 363 364 page_alignment = nxt_max(page_alignment, NXT_MAX_ALIGNMENT); 365 366 valid = nxt_expect(1, (page_size >= 64 367 && page_size >= page_alignment 368 && page_size >= min_chunk_size 369 && min_chunk_size * 32 >= page_size 370 && cluster_size >= page_size 371 && cluster_size / page_size <= 256 372 && cluster_size % page_size == 0)); 373 if (!valid) { 374 return 0; 375 } 376 377 return 1; 378 } 379 380 381 nxt_bool_t 382 nxt_mp_is_empty(nxt_mp_t *mp) 383 { 384 return (nxt_rbtree_is_empty(&mp->blocks) 385 && nxt_queue_is_empty(&mp->free_pages)); 386 } 387 388 389 void * 390 nxt_mp_alloc(nxt_mp_t *mp, size_t size) 391 { 392 void *p; 393 394 #if !(NXT_DEBUG_MEMORY) 395 396 if (size <= mp->page_size) { 397 p = nxt_mp_alloc_small(mp, size); 398 399 } else { 400 p = nxt_mp_alloc_large(mp, NXT_MAX_ALIGNMENT, size, 1); 401 } 402 403 #else 404 405 p = nxt_mp_alloc_large(mp, NXT_MAX_ALIGNMENT, size, 1); 406 407 #endif 408 409 nxt_debug_alloc("mp %p alloc(%uz): %p", mp, size, p); 410 411 return p; 412 } 413 414 415 void * 416 nxt_mp_zalloc(nxt_mp_t *mp, size_t size) 417 { 418 void *p; 419 420 p = nxt_mp_alloc(mp, size); 421 422 if (nxt_fast_path(p != NULL)) { 423 memset(p, 0, size); 424 } 425 426 return p; 427 } 428 429 430 void * 431 nxt_mp_align(nxt_mp_t *mp, size_t alignment, size_t size) 432 { 433 void *p; 434 435 /* Alignment must be a power of 2. */ 436 437 if (nxt_fast_path(nxt_is_power_of_two(alignment))) { 438 439 #if !(NXT_DEBUG_MEMORY) 440 441 size_t aligned_size; 442 443 aligned_size = nxt_max(size, alignment); 444 445 if (aligned_size <= mp->page_size && alignment <= mp->page_alignment) { 446 p = nxt_mp_alloc_small(mp, aligned_size); 447 448 } else { 449 p = nxt_mp_alloc_large(mp, alignment, size, 1); 450 } 451 452 #else 453 454 p = nxt_mp_alloc_large(mp, alignment, size, 1); 455 456 #endif 457 458 } else { 459 p = NULL; 460 } 461 462 nxt_debug_alloc("mp %p align(@%uz:%uz): %p", mp, alignment, size, p); 463 464 return p; 465 } 466 467 468 void * 469 nxt_mp_zalign(nxt_mp_t *mp, size_t alignment, size_t size) 470 { 471 void *p; 472 473 p = nxt_mp_align(mp, alignment, size); 474 475 if (nxt_fast_path(p != NULL)) { 476 memset(p, 0, size); 477 } 478 479 return p; 480 } 481 482 483 nxt_inline nxt_uint_t 484 nxt_mp_chunk_pages_index(nxt_mp_t *mp, size_t size) 485 { 486 nxt_int_t n, index; 487 488 index = 0; 489 490 if (size > 1) { 491 n = nxt_lg2(size - 1) + 1 - mp->chunk_size_shift; 492 493 if (n > 0) { 494 index = n; 495 } 496 } 497 498 return index; 499 } 500 501 502 #if !(NXT_DEBUG_MEMORY) 503 504 nxt_inline u_char * 505 nxt_mp_page_addr(nxt_mp_t *mp, nxt_mp_page_t *page) 506 { 507 size_t page_offset; 508 nxt_mp_block_t *block; 509 510 page_offset = page->number * sizeof(nxt_mp_page_t) 511 + offsetof(nxt_mp_block_t, pages); 512 513 block = (nxt_mp_block_t *) ((u_char *) page - page_offset); 514 515 return block->start + (page->number << mp->page_size_shift); 516 } 517 518 519 static void * 520 nxt_mp_alloc_small(nxt_mp_t *mp, size_t size) 521 { 522 u_char *p; 523 nxt_uint_t n, index; 524 nxt_queue_t *chunk_pages; 525 nxt_mp_page_t *page; 526 nxt_queue_link_t *link; 527 528 nxt_mp_thread_assert(mp); 529 530 p = NULL; 531 532 if (size <= mp->page_size / 2) { 533 534 index = nxt_mp_chunk_pages_index(mp, size); 535 chunk_pages = &mp->chunk_pages[index]; 536 537 if (nxt_fast_path(!nxt_queue_is_empty(chunk_pages))) { 538 539 link = nxt_queue_first(chunk_pages); 540 page = nxt_queue_link_data(link, nxt_mp_page_t, link); 541 542 p = nxt_mp_page_addr(mp, page); 543 544 n = nxt_mp_chunk_get_free(page->u.map); 545 nxt_mp_chunk_set_busy(page->u.map, n); 546 547 p += ((n << index) << mp->chunk_size_shift); 548 549 page->chunks--; 550 551 if (page->chunks == 0) { 552 /* 553 * Remove full page from the pool chunk pages list 554 * of pages with free chunks. 555 */ 556 nxt_queue_remove(&page->link); 557 } 558 559 } else { 560 page = nxt_mp_alloc_page(mp); 561 562 if (nxt_fast_path(page != NULL)) { 563 page->size = (1 << index); 564 565 n = mp->page_size_shift - (index + mp->chunk_size_shift); 566 page->chunks = (1 << n) - 1; 567 568 nxt_queue_insert_head(chunk_pages, &page->link); 569 570 /* Mark the first chunk as busy. */ 571 page->u.map = 0xFFFFFFFE; 572 573 p = nxt_mp_page_addr(mp, page); 574 } 575 } 576 577 } else { 578 page = nxt_mp_alloc_page(mp); 579 580 if (nxt_fast_path(page != NULL)) { 581 page->size = mp->page_size >> mp->chunk_size_shift; 582 583 p = nxt_mp_page_addr(mp, page); 584 } 585 } 586 587 nxt_debug_alloc("mp %p chunk:%uz alloc: %p", mp, 588 page->size << mp->chunk_size_shift, p); 589 590 return p; 591 } 592 593 594 static void * 595 nxt_mp_get_small(nxt_mp_t *mp, nxt_queue_t *pages, size_t size) 596 { 597 u_char *p; 598 uint32_t available; 599 nxt_mp_page_t *page; 600 nxt_queue_link_t *link, *next; 601 602 nxt_mp_thread_assert(mp); 603 604 for (link = nxt_queue_first(pages); 605 link != nxt_queue_tail(pages); 606 link = next) 607 { 608 next = nxt_queue_next(link); 609 page = nxt_queue_link_data(link, nxt_mp_page_t, link); 610 611 available = mp->page_size - page->u.taken; 612 613 if (size <= available) { 614 goto found; 615 } 616 617 if (available == 0 || page->fails++ > 100) { 618 nxt_queue_remove(link); 619 } 620 } 621 622 page = nxt_mp_alloc_page(mp); 623 624 if (nxt_slow_path(page == NULL)) { 625 return page; 626 } 627 628 nxt_queue_insert_head(pages, &page->link); 629 630 page->size = 0xFF; 631 page->u.taken = 0; 632 633 found: 634 635 p = nxt_mp_page_addr(mp, page); 636 637 p += page->u.taken; 638 page->u.taken += size; 639 640 return p; 641 } 642 643 644 static nxt_mp_page_t * 645 nxt_mp_alloc_page(nxt_mp_t *mp) 646 { 647 nxt_mp_page_t *page; 648 nxt_mp_block_t *cluster; 649 nxt_queue_link_t *link; 650 651 if (nxt_queue_is_empty(&mp->free_pages)) { 652 cluster = nxt_mp_alloc_cluster(mp); 653 if (nxt_slow_path(cluster == NULL)) { 654 return NULL; 655 } 656 } 657 658 link = nxt_queue_first(&mp->free_pages); 659 nxt_queue_remove(link); 660 661 page = nxt_queue_link_data(link, nxt_mp_page_t, link); 662 663 return page; 664 } 665 666 667 static nxt_mp_block_t * 668 nxt_mp_alloc_cluster(nxt_mp_t *mp) 669 { 670 nxt_uint_t n; 671 nxt_mp_block_t *cluster; 672 673 n = mp->cluster_size >> mp->page_size_shift; 674 675 cluster = nxt_zalloc(sizeof(nxt_mp_block_t) + n * sizeof(nxt_mp_page_t)); 676 677 if (nxt_slow_path(cluster == NULL)) { 678 return NULL; 679 } 680 681 /* NXT_MP_CLUSTER_BLOCK type is zero. */ 682 683 cluster->size = mp->cluster_size; 684 685 cluster->start = nxt_memalign(mp->page_alignment, mp->cluster_size); 686 if (nxt_slow_path(cluster->start == NULL)) { 687 nxt_free(cluster); 688 return NULL; 689 } 690 691 n--; 692 cluster->pages[n].number = n; 693 nxt_queue_insert_head(&mp->free_pages, &cluster->pages[n].link); 694 695 while (n != 0) { 696 n--; 697 cluster->pages[n].number = n; 698 nxt_queue_insert_before(&cluster->pages[n + 1].link, 699 &cluster->pages[n].link); 700 } 701 702 nxt_rbtree_insert(&mp->blocks, &cluster->node); 703 704 return cluster; 705 } 706 707 #endif 708 709 710 static void * 711 nxt_mp_alloc_large(nxt_mp_t *mp, size_t alignment, size_t size, 712 nxt_bool_t freeable) 713 { 714 u_char *p; 715 size_t aligned_size; 716 uint8_t type; 717 nxt_mp_block_t *block; 718 719 nxt_mp_thread_assert(mp); 720 721 /* Allocation must be less than 4G. */ 722 if (nxt_slow_path(size >= 0xFFFFFFFF)) { 723 return NULL; 724 } 725 726 if (nxt_is_power_of_two(size)) { 727 block = nxt_malloc(sizeof(nxt_mp_block_t)); 728 if (nxt_slow_path(block == NULL)) { 729 return NULL; 730 } 731 732 p = nxt_memalign(alignment, size); 733 if (nxt_slow_path(p == NULL)) { 734 nxt_free(block); 735 return NULL; 736 } 737 738 type = NXT_MP_DISCRETE_BLOCK; 739 740 } else { 741 aligned_size = nxt_align_size(size, sizeof(uintptr_t)); 742 743 p = nxt_memalign(alignment, aligned_size + sizeof(nxt_mp_block_t)); 744 if (nxt_slow_path(p == NULL)) { 745 return NULL; 746 } 747 748 block = (nxt_mp_block_t *) (p + aligned_size); 749 type = NXT_MP_EMBEDDED_BLOCK; 750 } 751 752 block->type = type; 753 block->freeable = freeable; 754 block->size = size; 755 block->start = p; 756 757 nxt_rbtree_insert(&mp->blocks, &block->node); 758 759 return p; 760 } 761 762 763 static intptr_t 764 nxt_mp_rbtree_compare(nxt_rbtree_node_t *node1, nxt_rbtree_node_t *node2) 765 { 766 nxt_mp_block_t *block1, *block2; 767 768 block1 = (nxt_mp_block_t *) node1; 769 block2 = (nxt_mp_block_t *) node2; 770 771 return (uintptr_t) block1->start - (uintptr_t) block2->start; 772 } 773 774 775 void 776 nxt_mp_free(nxt_mp_t *mp, void *p) 777 { 778 const char *err; 779 nxt_mp_block_t *block; 780 781 nxt_mp_thread_assert(mp); 782 783 nxt_debug_alloc("mp %p free(%p)", mp, p); 784 785 block = nxt_mp_find_block(&mp->blocks, p); 786 787 if (nxt_fast_path(block != NULL)) { 788 789 if (block->type == NXT_MP_CLUSTER_BLOCK) { 790 err = nxt_mp_chunk_free(mp, block, p); 791 792 if (nxt_fast_path(err == NULL)) { 793 return; 794 } 795 796 } else if (nxt_fast_path(p == block->start)) { 797 798 if (block->freeable) { 799 nxt_rbtree_delete(&mp->blocks, &block->node); 800 801 if (block->type == NXT_MP_DISCRETE_BLOCK) { 802 nxt_free(block); 803 } 804 805 nxt_free(p); 806 807 return; 808 } 809 810 err = "freed pointer points to non-freeable block: %p"; 811 812 } else { 813 err = "freed pointer points to middle of block: %p"; 814 } 815 816 } else { 817 err = "freed pointer is out of pool: %p"; 818 } 819 820 nxt_thread_log_alert(err, p); 821 } 822 823 824 static nxt_mp_block_t * 825 nxt_mp_find_block(nxt_rbtree_t *tree, u_char *p) 826 { 827 nxt_mp_block_t *block; 828 nxt_rbtree_node_t *node, *sentinel; 829 830 node = nxt_rbtree_root(tree); 831 sentinel = nxt_rbtree_sentinel(tree); 832 833 while (node != sentinel) { 834 835 block = (nxt_mp_block_t *) node; 836 837 if (p < block->start) { 838 node = node->left; 839 840 } else if (p >= block->start + block->size) { 841 node = node->right; 842 843 } else { 844 return block; 845 } 846 } 847 848 return NULL; 849 } 850 851 852 static const char * 853 nxt_mp_chunk_free(nxt_mp_t *mp, nxt_mp_block_t *cluster, u_char *p) 854 { 855 u_char *start; 856 uintptr_t offset; 857 nxt_uint_t n, size, chunk; 858 nxt_queue_t *chunk_pages; 859 nxt_mp_page_t *page; 860 861 n = (p - cluster->start) >> mp->page_size_shift; 862 start = cluster->start + (n << mp->page_size_shift); 863 864 page = &cluster->pages[n]; 865 866 if (nxt_slow_path(page->size == 0)) { 867 return "freed pointer points to already free page: %p"; 868 } 869 870 if (nxt_slow_path(page->size == 0xFF)) { 871 return "freed pointer points to non-freeable page: %p"; 872 } 873 874 size = page->size << mp->chunk_size_shift; 875 876 if (size != mp->page_size) { 877 878 offset = (uintptr_t) (p - start) & (mp->page_size - 1); 879 chunk = offset / size; 880 881 if (nxt_slow_path(offset != chunk * size)) { 882 return "freed pointer points to wrong chunk: %p"; 883 } 884 885 if (nxt_slow_path(nxt_mp_chunk_is_free(page->u.map, chunk))) { 886 return "freed pointer points to already free chunk: %p"; 887 } 888 889 nxt_mp_chunk_set_free(page->u.map, chunk); 890 891 if (page->u.map != 0xFFFFFFFF) { 892 page->chunks++; 893 894 if (page->chunks == 1) { 895 /* 896 * Add the page to the head of pool chunk pages list 897 * of pages with free chunks. 898 */ 899 n = nxt_mp_chunk_pages_index(mp, size); 900 chunk_pages = &mp->chunk_pages[n]; 901 902 nxt_queue_insert_head(chunk_pages, &page->link); 903 } 904 905 nxt_mp_free_junk(p, size); 906 907 return NULL; 908 909 } else { 910 /* 911 * All chunks are free, remove the page from pool 912 * chunk pages list of pages with free chunks. 913 */ 914 nxt_queue_remove(&page->link); 915 } 916 917 } else if (nxt_slow_path(p != start)) { 918 return "invalid pointer to chunk: %p"; 919 } 920 921 /* Add the free page to the pool's free pages tree. */ 922 923 page->size = 0; 924 nxt_queue_insert_head(&mp->free_pages, &page->link); 925 926 nxt_mp_free_junk(p, size); 927 928 /* Test if all pages in the cluster are free. */ 929 930 n = mp->cluster_size >> mp->page_size_shift; 931 page = cluster->pages; 932 933 do { 934 if (page->size != 0) { 935 return NULL; 936 } 937 938 page++; 939 n--; 940 } while (n != 0); 941 942 /* Free cluster. */ 943 944 n = mp->cluster_size >> mp->page_size_shift; 945 page = cluster->pages; 946 947 do { 948 nxt_queue_remove(&page->link); 949 page++; 950 n--; 951 } while (n != 0); 952 953 nxt_rbtree_delete(&mp->blocks, &cluster->node); 954 955 p = cluster->start; 956 957 nxt_free(cluster); 958 nxt_free(p); 959 960 return NULL; 961 } 962 963 964 void * 965 nxt_mp_nget(nxt_mp_t *mp, size_t size) 966 { 967 void *p; 968 969 #if !(NXT_DEBUG_MEMORY) 970 971 if (size <= mp->page_size) { 972 p = nxt_mp_get_small(mp, &mp->nget_pages, size); 973 974 } else { 975 p = nxt_mp_alloc_large(mp, NXT_MAX_ALIGNMENT, size, 0); 976 } 977 978 #else 979 980 p = nxt_mp_alloc_large(mp, NXT_MAX_ALIGNMENT, size, 0); 981 982 #endif 983 984 nxt_debug_alloc("mp %p nget(%uz): %p", mp, size, p); 985 986 return p; 987 } 988 989 990 void * 991 nxt_mp_get(nxt_mp_t *mp, size_t size) 992 { 993 void *p; 994 995 #if !(NXT_DEBUG_MEMORY) 996 997 if (size <= mp->page_size) { 998 size = nxt_max(size, NXT_MAX_ALIGNMENT); 999 p = nxt_mp_get_small(mp, &mp->get_pages, size); 1000 1001 } else { 1002 p = nxt_mp_alloc_large(mp, NXT_MAX_ALIGNMENT, size, 0); 1003 } 1004 1005 #else 1006 1007 p = nxt_mp_alloc_large(mp, NXT_MAX_ALIGNMENT, size, 0); 1008 1009 #endif 1010 1011 nxt_debug_alloc("mp %p get(%uz): %p", mp, size, p); 1012 1013 return p; 1014 } 1015 1016 1017 void * 1018 nxt_mp_zget(nxt_mp_t *mp, size_t size) 1019 { 1020 void *p; 1021 1022 p = nxt_mp_get(mp, size); 1023 1024 if (nxt_fast_path(p != NULL)) { 1025 memset(p, 0, size); 1026 } 1027 1028 return p; 1029 } 1030 1031 1032 nxt_int_t 1033 nxt_mp_cleanup(nxt_mp_t *mp, nxt_work_handler_t handler, 1034 nxt_task_t *task, void *obj, void *data) 1035 { 1036 nxt_work_t *work; 1037 1038 work = nxt_mp_get(mp, sizeof(nxt_work_t)); 1039 1040 if (nxt_slow_path(work == NULL)) { 1041 return NXT_ERROR; 1042 } 1043 1044 work->next = mp->cleanup; 1045 work->handler = handler; 1046 work->task = task; 1047 work->obj = obj; 1048 work->data = data; 1049 1050 mp->cleanup = work; 1051 1052 return NXT_OK; 1053 } 1054