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 /* 772 * Shifting is necessary to prevent overflow of intptr_t when block1->start 773 * is much greater than block2->start or vice versa. 774 * 775 * It is safe to drop one bit since there cannot be adjacent addresses 776 * because of alignments and allocation sizes. Effectively this reduces 777 * the absolute values to fit into the magnitude of intptr_t. 778 */ 779 return ((uintptr_t) block1->start >> 1) - ((uintptr_t) block2->start >> 1); 780 } 781 782 783 void 784 nxt_mp_free(nxt_mp_t *mp, void *p) 785 { 786 const char *err; 787 nxt_mp_block_t *block; 788 789 nxt_mp_thread_assert(mp); 790 791 nxt_debug_alloc("mp %p free(%p)", mp, p); 792 793 block = nxt_mp_find_block(&mp->blocks, p); 794 795 if (nxt_fast_path(block != NULL)) { 796 797 if (block->type == NXT_MP_CLUSTER_BLOCK) { 798 err = nxt_mp_chunk_free(mp, block, p); 799 800 if (nxt_fast_path(err == NULL)) { 801 return; 802 } 803 804 } else if (nxt_fast_path(p == block->start)) { 805 806 if (block->freeable) { 807 nxt_rbtree_delete(&mp->blocks, &block->node); 808 809 if (block->type == NXT_MP_DISCRETE_BLOCK) { 810 nxt_free(block); 811 } 812 813 nxt_free(p); 814 815 return; 816 } 817 818 err = "freed pointer points to non-freeable block: %p"; 819 820 } else { 821 err = "freed pointer points to middle of block: %p"; 822 } 823 824 } else { 825 err = "freed pointer is out of pool: %p"; 826 } 827 828 nxt_thread_log_alert(err, p); 829 } 830 831 832 static nxt_mp_block_t * 833 nxt_mp_find_block(nxt_rbtree_t *tree, u_char *p) 834 { 835 nxt_mp_block_t *block; 836 nxt_rbtree_node_t *node, *sentinel; 837 838 node = nxt_rbtree_root(tree); 839 sentinel = nxt_rbtree_sentinel(tree); 840 841 while (node != sentinel) { 842 843 block = (nxt_mp_block_t *) node; 844 845 if (p < block->start) { 846 node = node->left; 847 848 } else if (p >= block->start + block->size) { 849 node = node->right; 850 851 } else { 852 return block; 853 } 854 } 855 856 return NULL; 857 } 858 859 860 static const char * 861 nxt_mp_chunk_free(nxt_mp_t *mp, nxt_mp_block_t *cluster, u_char *p) 862 { 863 u_char *start; 864 uintptr_t offset; 865 nxt_uint_t n, size, chunk; 866 nxt_queue_t *chunk_pages; 867 nxt_mp_page_t *page; 868 869 n = (p - cluster->start) >> mp->page_size_shift; 870 start = cluster->start + (n << mp->page_size_shift); 871 872 page = &cluster->pages[n]; 873 874 if (nxt_slow_path(page->size == 0)) { 875 return "freed pointer points to already free page: %p"; 876 } 877 878 if (nxt_slow_path(page->size == 0xFF)) { 879 return "freed pointer points to non-freeable page: %p"; 880 } 881 882 size = page->size << mp->chunk_size_shift; 883 884 if (size != mp->page_size) { 885 886 offset = (uintptr_t) (p - start) & (mp->page_size - 1); 887 chunk = offset / size; 888 889 if (nxt_slow_path(offset != chunk * size)) { 890 return "freed pointer points to wrong chunk: %p"; 891 } 892 893 if (nxt_slow_path(nxt_mp_chunk_is_free(page->u.map, chunk))) { 894 return "freed pointer points to already free chunk: %p"; 895 } 896 897 nxt_mp_chunk_set_free(page->u.map, chunk); 898 899 if (page->u.map != 0xFFFFFFFF) { 900 page->chunks++; 901 902 if (page->chunks == 1) { 903 /* 904 * Add the page to the head of pool chunk pages list 905 * of pages with free chunks. 906 */ 907 n = nxt_mp_chunk_pages_index(mp, size); 908 chunk_pages = &mp->chunk_pages[n]; 909 910 nxt_queue_insert_head(chunk_pages, &page->link); 911 } 912 913 nxt_mp_free_junk(p, size); 914 915 return NULL; 916 917 } else { 918 /* 919 * All chunks are free, remove the page from pool 920 * chunk pages list of pages with free chunks. 921 */ 922 nxt_queue_remove(&page->link); 923 } 924 925 } else if (nxt_slow_path(p != start)) { 926 return "invalid pointer to chunk: %p"; 927 } 928 929 /* Add the free page to the pool's free pages tree. */ 930 931 page->size = 0; 932 nxt_queue_insert_head(&mp->free_pages, &page->link); 933 934 nxt_mp_free_junk(p, size); 935 936 /* Test if all pages in the cluster are free. */ 937 938 n = mp->cluster_size >> mp->page_size_shift; 939 page = cluster->pages; 940 941 do { 942 if (page->size != 0) { 943 return NULL; 944 } 945 946 page++; 947 n--; 948 } while (n != 0); 949 950 /* Free cluster. */ 951 952 n = mp->cluster_size >> mp->page_size_shift; 953 page = cluster->pages; 954 955 do { 956 nxt_queue_remove(&page->link); 957 page++; 958 n--; 959 } while (n != 0); 960 961 nxt_rbtree_delete(&mp->blocks, &cluster->node); 962 963 p = cluster->start; 964 965 nxt_free(cluster); 966 nxt_free(p); 967 968 return NULL; 969 } 970 971 972 void * 973 nxt_mp_nget(nxt_mp_t *mp, size_t size) 974 { 975 void *p; 976 977 #if !(NXT_DEBUG_MEMORY) 978 979 if (size <= mp->page_size) { 980 p = nxt_mp_get_small(mp, &mp->nget_pages, size); 981 982 } else { 983 p = nxt_mp_alloc_large(mp, NXT_MAX_ALIGNMENT, size, 0); 984 } 985 986 #else 987 988 p = nxt_mp_alloc_large(mp, NXT_MAX_ALIGNMENT, size, 0); 989 990 #endif 991 992 nxt_debug_alloc("mp %p nget(%uz): %p", mp, size, p); 993 994 return p; 995 } 996 997 998 void * 999 nxt_mp_get(nxt_mp_t *mp, size_t size) 1000 { 1001 void *p; 1002 1003 #if !(NXT_DEBUG_MEMORY) 1004 1005 if (size <= mp->page_size) { 1006 size = nxt_max(size, NXT_MAX_ALIGNMENT); 1007 p = nxt_mp_get_small(mp, &mp->get_pages, size); 1008 1009 } else { 1010 p = nxt_mp_alloc_large(mp, NXT_MAX_ALIGNMENT, size, 0); 1011 } 1012 1013 #else 1014 1015 p = nxt_mp_alloc_large(mp, NXT_MAX_ALIGNMENT, size, 0); 1016 1017 #endif 1018 1019 nxt_debug_alloc("mp %p get(%uz): %p", mp, size, p); 1020 1021 return p; 1022 } 1023 1024 1025 void * 1026 nxt_mp_zget(nxt_mp_t *mp, size_t size) 1027 { 1028 void *p; 1029 1030 p = nxt_mp_get(mp, size); 1031 1032 if (nxt_fast_path(p != NULL)) { 1033 memset(p, 0, size); 1034 } 1035 1036 return p; 1037 } 1038 1039 1040 nxt_int_t 1041 nxt_mp_cleanup(nxt_mp_t *mp, nxt_work_handler_t handler, 1042 nxt_task_t *task, void *obj, void *data) 1043 { 1044 nxt_work_t *work; 1045 1046 work = nxt_mp_get(mp, sizeof(nxt_work_t)); 1047 1048 if (nxt_slow_path(work == NULL)) { 1049 return NXT_ERROR; 1050 } 1051 1052 work->next = mp->cleanup; 1053 work->handler = handler; 1054 work->task = task; 1055 work->obj = obj; 1056 work->data = data; 1057 1058 mp->cleanup = work; 1059 1060 return NXT_OK; 1061 } 1062 1063 1064 void * 1065 nxt_mp_lvlhsh_alloc(void *pool, size_t size) 1066 { 1067 return nxt_mp_align(pool, size, size); 1068 } 1069 1070 1071 void 1072 nxt_mp_lvlhsh_free(void *pool, void *p) 1073 { 1074 nxt_mp_free(pool, p); 1075 } 1076