Changeset 391 for python/trunk/Objects/obmalloc.c
- Timestamp:
- Mar 19, 2014, 11:31:01 PM (11 years ago)
- Location:
- python/trunk
- Files:
-
- 2 edited
-
. (modified) (1 prop)
-
Objects/obmalloc.c (modified) (40 diffs)
Legend:
- Unmodified
- Added
- Removed
-
python/trunk
-
Property svn:mergeinfo
set to
/python/vendor/Python-2.7.6 merged eligible /python/vendor/current merged eligible
-
Property svn:mergeinfo
set to
-
python/trunk/Objects/obmalloc.c
r2 r391 2 2 3 3 #ifdef WITH_PYMALLOC 4 5 #ifdef WITH_VALGRIND 6 #include <valgrind/valgrind.h> 7 8 /* If we're using GCC, use __builtin_expect() to reduce overhead of 9 the valgrind checks */ 10 #if defined(__GNUC__) && (__GNUC__ > 2) && defined(__OPTIMIZE__) 11 # define UNLIKELY(value) __builtin_expect((value), 0) 12 #else 13 # define UNLIKELY(value) (value) 14 #endif 15 16 /* -1 indicates that we haven't checked that we're running on valgrind yet. */ 17 static int running_on_valgrind = -1; 18 #endif 4 19 5 20 /* An object allocator for Python. … … 13 28 14 29 15 30 Object-specific allocators 16 31 _____ ______ ______ ________ 17 32 [ int ] [ dict ] [ list ] ... [ string ] Python core | … … 53 68 */ 54 69 55 /* #undef WITH_MEMORY_LIMITS */ 70 /* #undef WITH_MEMORY_LIMITS */ /* disable mem limit checks */ 56 71 57 72 /*==========================================================================*/ … … 81 96 * For small requests we have the following table: 82 97 * 83 * Request in bytes 98 * Request in bytes Size of allocated block Size class idx 84 99 * ---------------------------------------------------------------- 85 100 * 1-8 8 0 86 * 87 * 88 * 89 * 90 * 91 * 92 * 93 * 94 * 95 * 96 * 101 * 9-16 16 1 102 * 17-24 24 2 103 * 25-32 32 3 104 * 33-40 40 4 105 * 41-48 48 5 106 * 49-56 56 6 107 * 57-64 64 7 108 * 65-72 72 8 109 * ... ... ... 110 * 241-248 248 30 111 * 249-256 256 31 97 112 * 98 * 113 * 0, 257 and up: routed to the underlying allocator. 99 114 */ 100 115 … … 113 128 * You shouldn't change this unless you know what you are doing. 114 129 */ 115 #define ALIGNMENT 8/* must be 2^N */116 #define ALIGNMENT_SHIFT 117 #define ALIGNMENT_MASK 130 #define ALIGNMENT 8 /* must be 2^N */ 131 #define ALIGNMENT_SHIFT 3 132 #define ALIGNMENT_MASK (ALIGNMENT - 1) 118 133 119 134 /* Return the number of bytes in size class I, as a uint. */ … … 126 141 * 127 142 * The following invariants must hold: 128 * 129 * 143 * 1) ALIGNMENT <= SMALL_REQUEST_THRESHOLD <= 256 144 * 2) SMALL_REQUEST_THRESHOLD is evenly divisible by ALIGNMENT 130 145 * 131 146 * Although not required, for better performance and space efficiency, 132 147 * it is recommended that SMALL_REQUEST_THRESHOLD is set to a power of 2. 133 148 */ 134 #define SMALL_REQUEST_THRESHOLD 135 #define NB_SMALL_SIZE_CLASSES 149 #define SMALL_REQUEST_THRESHOLD 256 150 #define NB_SMALL_SIZE_CLASSES (SMALL_REQUEST_THRESHOLD / ALIGNMENT) 136 151 137 152 /* … … 145 160 * currently targets. 146 161 */ 147 #define SYSTEM_PAGE_SIZE 148 #define SYSTEM_PAGE_SIZE_MASK 162 #define SYSTEM_PAGE_SIZE (4 * 1024) 163 #define SYSTEM_PAGE_SIZE_MASK (SYSTEM_PAGE_SIZE - 1) 149 164 150 165 /* … … 153 168 #ifdef WITH_MEMORY_LIMITS 154 169 #ifndef SMALL_MEMORY_LIMIT 155 #define SMALL_MEMORY_LIMIT (64 * 1024 * 1024)/* 64 MB -- more? */170 #define SMALL_MEMORY_LIMIT (64 * 1024 * 1024) /* 64 MB -- more? */ 156 171 #endif 157 172 #endif … … 170 185 * memory from the system across various platforms. 171 186 */ 172 #define ARENA_SIZE (256 << 10)/* 256KB */187 #define ARENA_SIZE (256 << 10) /* 256KB */ 173 188 174 189 #ifdef WITH_MEMORY_LIMITS 175 #define MAX_ARENAS 190 #define MAX_ARENAS (SMALL_MEMORY_LIMIT / ARENA_SIZE) 176 191 #endif 177 192 … … 180 195 * between 1K and SYSTEM_PAGE_SIZE, that is: 1k, 2k, 4k. 181 196 */ 182 #define POOL_SIZE SYSTEM_PAGE_SIZE/* must be 2^N */183 #define POOL_SIZE_MASK 197 #define POOL_SIZE SYSTEM_PAGE_SIZE /* must be 2^N */ 198 #define POOL_SIZE_MASK SYSTEM_PAGE_SIZE_MASK 184 199 185 200 /* … … 207 222 * Python's threads are serialized, so object malloc locking is disabled. 208 223 */ 209 #define SIMPLELOCK_DECL(lock) /* simple lock declaration*/210 #define SIMPLELOCK_INIT(lock) /* allocate (if needed) and initialize*/211 #define SIMPLELOCK_FINI(lock) /* free/destroy an existing lock*/212 #define SIMPLELOCK_LOCK(lock) 213 #define SIMPLELOCK_UNLOCK(lock) 224 #define SIMPLELOCK_DECL(lock) /* simple lock declaration */ 225 #define SIMPLELOCK_INIT(lock) /* allocate (if needed) and initialize */ 226 #define SIMPLELOCK_FINI(lock) /* free/destroy an existing lock */ 227 #define SIMPLELOCK_LOCK(lock) /* acquire released lock */ 228 #define SIMPLELOCK_UNLOCK(lock) /* release acquired lock */ 214 229 215 230 /* … … 218 233 */ 219 234 #undef uchar 220 #define uchar unsigned char/* assuming == 8 bits */235 #define uchar unsigned char /* assuming == 8 bits */ 221 236 222 237 #undef uint 223 #define uint unsigned int/* assuming >= 16 bits */238 #define uint unsigned int /* assuming >= 16 bits */ 224 239 225 240 #undef ulong 226 #define ulong unsigned long/* assuming >= 32 bits */241 #define ulong unsigned long /* assuming >= 32 bits */ 227 242 228 243 #undef uptr 229 #define uptr 244 #define uptr Py_uintptr_t 230 245 231 246 /* When you say memory, my mind reasons in terms of (pointers to) blocks */ … … 234 249 /* Pool for small blocks. */ 235 250 struct pool_header { 236 237 uint count; } ref;/* number of allocated blocks */238 block *freeblock;/* pool's free list head */239 struct pool_header *nextpool;/* next pool of this size class */240 struct pool_header *prevpool;/* previous pool "" */241 uint arenaindex;/* index into arenas of base adr */242 uint szidx; /* block size class index*/243 uint nextoffset; /* bytes to virgin block*/244 uint maxnextoffset; /* largest valid nextoffset*/251 union { block *_padding; 252 uint count; } ref; /* number of allocated blocks */ 253 block *freeblock; /* pool's free list head */ 254 struct pool_header *nextpool; /* next pool of this size class */ 255 struct pool_header *prevpool; /* previous pool "" */ 256 uint arenaindex; /* index into arenas of base adr */ 257 uint szidx; /* block size class index */ 258 uint nextoffset; /* bytes to virgin block */ 259 uint maxnextoffset; /* largest valid nextoffset */ 245 260 }; 246 261 … … 249 264 /* Record keeping for arenas. */ 250 265 struct arena_object { 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 266 /* The address of the arena, as returned by malloc. Note that 0 267 * will never be returned by a successful malloc, and is used 268 * here to mark an arena_object that doesn't correspond to an 269 * allocated arena. 270 */ 271 uptr address; 272 273 /* Pool-aligned pointer to the next pool to be carved off. */ 274 block* pool_address; 275 276 /* The number of available pools in the arena: free pools + never- 277 * allocated pools. 278 */ 279 uint nfreepools; 280 281 /* The total number of pools in the arena, whether or not available. */ 282 uint ntotalpools; 283 284 /* Singly-linked list of available pools. */ 285 struct pool_header* freepools; 286 287 /* Whenever this arena_object is not associated with an allocated 288 * arena, the nextarena member is used to link all unassociated 289 * arena_objects in the singly-linked `unused_arena_objects` list. 290 * The prevarena member is unused in this case. 291 * 292 * When this arena_object is associated with an allocated arena 293 * with at least one available pool, both members are used in the 294 * doubly-linked `usable_arenas` list, which is maintained in 295 * increasing order of `nfreepools` values. 296 * 297 * Else this arena_object is associated with an allocated arena 298 * all of whose pools are in use. `nextarena` and `prevarena` 299 * are both meaningless in this case. 300 */ 301 struct arena_object* nextarena; 302 struct arena_object* prevarena; 288 303 }; 289 304 290 305 #undef ROUNDUP 291 #define ROUNDUP(x) 292 #define POOL_OVERHEAD 293 294 #define DUMMY_SIZE_IDX 0xffff/* size class of newly cached pools */306 #define ROUNDUP(x) (((x) + ALIGNMENT_MASK) & ~ALIGNMENT_MASK) 307 #define POOL_OVERHEAD ROUNDUP(sizeof(struct pool_header)) 308 309 #define DUMMY_SIZE_IDX 0xffff /* size class of newly cached pools */ 295 310 296 311 /* Round pointer P down to the closest pool-aligned address <= P, as a poolp */ … … 306 321 */ 307 322 SIMPLELOCK_DECL(_malloc_lock) 308 #define LOCK() 309 #define UNLOCK() 310 #define LOCK_INIT() 311 #define LOCK_FINI() 323 #define LOCK() SIMPLELOCK_LOCK(_malloc_lock) 324 #define UNLOCK() SIMPLELOCK_UNLOCK(_malloc_lock) 325 #define LOCK_INIT() SIMPLELOCK_INIT(_malloc_lock) 326 #define LOCK_FINI() SIMPLELOCK_FINI(_malloc_lock) 312 327 313 328 /* … … 389 404 immediately follow a pool_header's first two members: 390 405 391 392 393 406 union { block *_padding; 407 uint count; } ref; 408 block *freeblock; 394 409 395 410 each of which consume sizeof(block *) bytes. So what usedpools[i+i] really … … 407 422 **************************************************************************** */ 408 423 409 #define PTA(x) 410 #define PT(x) 424 #define PTA(x) ((poolp )((uchar *)&(usedpools[2*(x)]) - 2*sizeof(block *))) 425 #define PT(x) PTA(x), PTA(x) 411 426 412 427 static poolp usedpools[2 * ((NB_SMALL_SIZE_CLASSES + 7) / 8) * 8] = { 413 428 PT(0), PT(1), PT(2), PT(3), PT(4), PT(5), PT(6), PT(7) 414 429 #if NB_SMALL_SIZE_CLASSES > 8 415 430 , PT(8), PT(9), PT(10), PT(11), PT(12), PT(13), PT(14), PT(15) 416 431 #if NB_SMALL_SIZE_CLASSES > 16 417 432 , PT(16), PT(17), PT(18), PT(19), PT(20), PT(21), PT(22), PT(23) 418 433 #if NB_SMALL_SIZE_CLASSES > 24 419 434 , PT(24), PT(25), PT(26), PT(27), PT(28), PT(29), PT(30), PT(31) 420 435 #if NB_SMALL_SIZE_CLASSES > 32 421 436 , PT(32), PT(33), PT(34), PT(35), PT(36), PT(37), PT(38), PT(39) 422 437 #if NB_SMALL_SIZE_CLASSES > 40 423 438 , PT(40), PT(41), PT(42), PT(43), PT(44), PT(45), PT(46), PT(47) 424 439 #if NB_SMALL_SIZE_CLASSES > 48 425 440 , PT(48), PT(49), PT(50), PT(51), PT(52), PT(53), PT(54), PT(55) 426 441 #if NB_SMALL_SIZE_CLASSES > 56 427 442 , PT(56), PT(57), PT(58), PT(59), PT(60), PT(61), PT(62), PT(63) 428 443 #endif /* NB_SMALL_SIZE_CLASSES > 56 */ 429 444 #endif /* NB_SMALL_SIZE_CLASSES > 48 */ … … 509 524 new_arena(void) 510 525 { 511 512 uint excess;/* number of bytes above pool alignment */526 struct arena_object* arenaobj; 527 uint excess; /* number of bytes above pool alignment */ 513 528 514 529 #ifdef PYMALLOC_DEBUG 515 516 517 #endif 518 519 520 521 522 523 524 525 526 527 528 return NULL;/* overflow */530 if (Py_GETENV("PYTHONMALLOCSTATS")) 531 _PyObject_DebugMallocStats(); 532 #endif 533 if (unused_arena_objects == NULL) { 534 uint i; 535 uint numarenas; 536 size_t nbytes; 537 538 /* Double the number of arena objects on each allocation. 539 * Note that it's possible for `numarenas` to overflow. 540 */ 541 numarenas = maxarenas ? maxarenas << 1 : INITIAL_ARENA_OBJECTS; 542 if (numarenas <= maxarenas) 543 return NULL; /* overflow */ 529 544 #if SIZEOF_SIZE_T <= SIZEOF_INT 530 531 return NULL;/* overflow */532 #endif 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 arenas[i].address = 0;/* mark as unassociated */551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 545 if (numarenas > PY_SIZE_MAX / sizeof(*arenas)) 546 return NULL; /* overflow */ 547 #endif 548 nbytes = numarenas * sizeof(*arenas); 549 arenaobj = (struct arena_object *)realloc(arenas, nbytes); 550 if (arenaobj == NULL) 551 return NULL; 552 arenas = arenaobj; 553 554 /* We might need to fix pointers that were copied. However, 555 * new_arena only gets called when all the pages in the 556 * previous arenas are full. Thus, there are *no* pointers 557 * into the old array. Thus, we don't have to worry about 558 * invalid pointers. Just to be sure, some asserts: 559 */ 560 assert(usable_arenas == NULL); 561 assert(unused_arena_objects == NULL); 562 563 /* Put the new arenas on the unused_arena_objects list. */ 564 for (i = maxarenas; i < numarenas; ++i) { 565 arenas[i].address = 0; /* mark as unassociated */ 566 arenas[i].nextarena = i < numarenas - 1 ? 567 &arenas[i+1] : NULL; 568 } 569 570 /* Update globals. */ 571 unused_arena_objects = &arenas[maxarenas]; 572 maxarenas = numarenas; 573 } 574 575 /* Take the next available arena object off the head of the list. */ 576 assert(unused_arena_objects != NULL); 577 arenaobj = unused_arena_objects; 578 unused_arena_objects = arenaobj->nextarena; 579 assert(arenaobj->address == 0); 580 arenaobj->address = (uptr)malloc(ARENA_SIZE); 581 if (arenaobj->address == 0) { 582 /* The allocation failed: return NULL after putting the 583 * arenaobj back. 584 */ 585 arenaobj->nextarena = unused_arena_objects; 586 unused_arena_objects = arenaobj; 587 return NULL; 588 } 589 590 ++narenas_currently_allocated; 576 591 #ifdef PYMALLOC_DEBUG 577 578 579 580 #endif 581 582 583 584 585 586 587 588 589 590 591 592 593 594 592 ++ntimes_arena_allocated; 593 if (narenas_currently_allocated > narenas_highwater) 594 narenas_highwater = narenas_currently_allocated; 595 #endif 596 arenaobj->freepools = NULL; 597 /* pool_address <- first pool-aligned address in the arena 598 nfreepools <- number of whole pools that fit after alignment */ 599 arenaobj->pool_address = (block*)arenaobj->address; 600 arenaobj->nfreepools = ARENA_SIZE / POOL_SIZE; 601 assert(POOL_SIZE * arenaobj->nfreepools == ARENA_SIZE); 602 excess = (uint)(arenaobj->address & POOL_SIZE_MASK); 603 if (excess != 0) { 604 --arenaobj->nfreepools; 605 arenaobj->pool_address += POOL_SIZE - excess; 606 } 607 arenaobj->ntotalpools = arenaobj->nfreepools; 608 609 return arenaobj; 595 610 } 596 611 … … 608 623 arenas[(POOL)->arenaindex].address. Then P belongs to the arena if and only if 609 624 610 625 B <= P < B + ARENA_SIZE 611 626 612 627 Subtracting B throughout, this is true iff 613 628 614 629 0 <= P-B < ARENA_SIZE 615 630 616 631 By using unsigned arithmetic, the "0 <=" half of the test can be skipped. … … 646 661 AO.address is 0, and the second test in the macro reduces to: 647 662 648 663 P < ARENA_SIZE 649 664 650 665 If P >= ARENA_SIZE (extremely likely), the macro again correctly concludes … … 668 683 obmalloc controls. Since this test is needed at every entry point, it's 669 684 extremely desirable that it be this fast. 685 686 Since Py_ADDRESS_IN_RANGE may be reading from memory which was not allocated 687 by Python, it is important that (POOL)->arenaindex is read only once, as 688 another thread may be concurrently modifying the value without holding the 689 GIL. To accomplish this, the arenaindex_temp variable is used to store 690 (POOL)->arenaindex for the duration of the Py_ADDRESS_IN_RANGE macro's 691 execution. The caller of the macro is responsible for declaring this 692 variable. 670 693 */ 671 #define Py_ADDRESS_IN_RANGE(P, POOL) 672 ((POOL)->arenaindex < maxarenas &&\673 (uptr)(P) - arenas[(POOL)->arenaindex].address < (uptr)ARENA_SIZE && \674 arenas[(POOL)->arenaindex].address != 0)694 #define Py_ADDRESS_IN_RANGE(P, POOL) \ 695 ((arenaindex_temp = (POOL)->arenaindex) < maxarenas && \ 696 (uptr)(P) - arenas[arenaindex_temp].address < (uptr)ARENA_SIZE && \ 697 arenas[arenaindex_temp].address != 0) 675 698 676 699 … … 695 718 696 719 #if defined(__GNUC__) && ((__GNUC__ == 3) && (__GNUC_MINOR__ >= 1) || \ 697 720 (__GNUC__ >= 4)) 698 721 #define Py_NO_INLINE __attribute__((__noinline__)) 699 722 #else … … 724 747 PyObject_Malloc(size_t nbytes) 725 748 { 726 block *bp; 727 poolp pool; 728 poolp next; 729 uint size; 730 731 /* 732 * Limit ourselves to PY_SSIZE_T_MAX bytes to prevent security holes. 733 * Most python internals blindly use a signed Py_ssize_t to track 734 * things without checking for overflows or negatives. 735 * As size_t is unsigned, checking for nbytes < 0 is not required. 736 */ 737 if (nbytes > PY_SSIZE_T_MAX) 738 return NULL; 739 740 /* 741 * This implicitly redirects malloc(0). 742 */ 743 if ((nbytes - 1) < SMALL_REQUEST_THRESHOLD) { 744 LOCK(); 745 /* 746 * Most frequent paths first 747 */ 748 size = (uint)(nbytes - 1) >> ALIGNMENT_SHIFT; 749 pool = usedpools[size + size]; 750 if (pool != pool->nextpool) { 751 /* 752 * There is a used pool for this size class. 753 * Pick up the head block of its free list. 754 */ 755 ++pool->ref.count; 756 bp = pool->freeblock; 757 assert(bp != NULL); 758 if ((pool->freeblock = *(block **)bp) != NULL) { 759 UNLOCK(); 760 return (void *)bp; 761 } 762 /* 763 * Reached the end of the free list, try to extend it. 764 */ 765 if (pool->nextoffset <= pool->maxnextoffset) { 766 /* There is room for another block. */ 767 pool->freeblock = (block*)pool + 768 pool->nextoffset; 769 pool->nextoffset += INDEX2SIZE(size); 770 *(block **)(pool->freeblock) = NULL; 771 UNLOCK(); 772 return (void *)bp; 773 } 774 /* Pool is full, unlink from used pools. */ 775 next = pool->nextpool; 776 pool = pool->prevpool; 777 next->prevpool = pool; 778 pool->nextpool = next; 779 UNLOCK(); 780 return (void *)bp; 781 } 782 783 /* There isn't a pool of the right size class immediately 784 * available: use a free pool. 785 */ 786 if (usable_arenas == NULL) { 787 /* No arena has a free pool: allocate a new arena. */ 749 block *bp; 750 poolp pool; 751 poolp next; 752 uint size; 753 754 #ifdef WITH_VALGRIND 755 if (UNLIKELY(running_on_valgrind == -1)) 756 running_on_valgrind = RUNNING_ON_VALGRIND; 757 if (UNLIKELY(running_on_valgrind)) 758 goto redirect; 759 #endif 760 761 /* 762 * Limit ourselves to PY_SSIZE_T_MAX bytes to prevent security holes. 763 * Most python internals blindly use a signed Py_ssize_t to track 764 * things without checking for overflows or negatives. 765 * As size_t is unsigned, checking for nbytes < 0 is not required. 766 */ 767 if (nbytes > PY_SSIZE_T_MAX) 768 return NULL; 769 770 /* 771 * This implicitly redirects malloc(0). 772 */ 773 if ((nbytes - 1) < SMALL_REQUEST_THRESHOLD) { 774 LOCK(); 775 /* 776 * Most frequent paths first 777 */ 778 size = (uint)(nbytes - 1) >> ALIGNMENT_SHIFT; 779 pool = usedpools[size + size]; 780 if (pool != pool->nextpool) { 781 /* 782 * There is a used pool for this size class. 783 * Pick up the head block of its free list. 784 */ 785 ++pool->ref.count; 786 bp = pool->freeblock; 787 assert(bp != NULL); 788 if ((pool->freeblock = *(block **)bp) != NULL) { 789 UNLOCK(); 790 return (void *)bp; 791 } 792 /* 793 * Reached the end of the free list, try to extend it. 794 */ 795 if (pool->nextoffset <= pool->maxnextoffset) { 796 /* There is room for another block. */ 797 pool->freeblock = (block*)pool + 798 pool->nextoffset; 799 pool->nextoffset += INDEX2SIZE(size); 800 *(block **)(pool->freeblock) = NULL; 801 UNLOCK(); 802 return (void *)bp; 803 } 804 /* Pool is full, unlink from used pools. */ 805 next = pool->nextpool; 806 pool = pool->prevpool; 807 next->prevpool = pool; 808 pool->nextpool = next; 809 UNLOCK(); 810 return (void *)bp; 811 } 812 813 /* There isn't a pool of the right size class immediately 814 * available: use a free pool. 815 */ 816 if (usable_arenas == NULL) { 817 /* No arena has a free pool: allocate a new arena. */ 788 818 #ifdef WITH_MEMORY_LIMITS 789 790 791 792 793 #endif 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 819 if (narenas_currently_allocated >= MAX_ARENAS) { 820 UNLOCK(); 821 goto redirect; 822 } 823 #endif 824 usable_arenas = new_arena(); 825 if (usable_arenas == NULL) { 826 UNLOCK(); 827 goto redirect; 828 } 829 usable_arenas->nextarena = 830 usable_arenas->prevarena = NULL; 831 } 832 assert(usable_arenas->address != 0); 833 834 /* Try to get a cached free pool. */ 835 pool = usable_arenas->freepools; 836 if (pool != NULL) { 837 /* Unlink from cached pools. */ 838 usable_arenas->freepools = pool->nextpool; 839 840 /* This arena already had the smallest nfreepools 841 * value, so decreasing nfreepools doesn't change 842 * that, and we don't need to rearrange the 843 * usable_arenas list. However, if the arena has 844 * become wholly allocated, we need to remove its 845 * arena_object from usable_arenas. 846 */ 847 --usable_arenas->nfreepools; 848 if (usable_arenas->nfreepools == 0) { 849 /* Wholly allocated: remove. */ 850 assert(usable_arenas->freepools == NULL); 851 assert(usable_arenas->nextarena == NULL || 852 usable_arenas->nextarena->prevarena == 853 usable_arenas); 854 855 usable_arenas = usable_arenas->nextarena; 856 if (usable_arenas != NULL) { 857 usable_arenas->prevarena = NULL; 858 assert(usable_arenas->address != 0); 859 } 860 } 861 else { 862 /* nfreepools > 0: it must be that freepools 863 * isn't NULL, or that we haven't yet carved 864 * off all the arena's pools for the first 865 * time. 866 */ 867 assert(usable_arenas->freepools != NULL || 868 usable_arenas->pool_address <= 869 (block*)usable_arenas->address + 870 ARENA_SIZE - POOL_SIZE); 871 } 872 init_pool: 873 /* Frontlink to used pools. */ 874 next = usedpools[size + size]; /* == prev */ 875 pool->nextpool = next; 876 pool->prevpool = next; 877 next->nextpool = pool; 878 next->prevpool = pool; 879 pool->ref.count = 1; 880 if (pool->szidx == size) { 881 /* Luckily, this pool last contained blocks 882 * of the same size class, so its header 883 * and free list are already initialized. 884 */ 885 bp = pool->freeblock; 886 pool->freeblock = *(block **)bp; 887 UNLOCK(); 888 return (void *)bp; 889 } 890 /* 891 * Initialize the pool header, set up the free list to 892 * contain just the second block, and return the first 893 * block. 894 */ 895 pool->szidx = size; 896 size = INDEX2SIZE(size); 897 bp = (block *)pool + POOL_OVERHEAD; 898 pool->nextoffset = POOL_OVERHEAD + (size << 1); 899 pool->maxnextoffset = POOL_SIZE - size; 900 pool->freeblock = bp + size; 901 *(block **)(pool->freeblock) = NULL; 902 UNLOCK(); 903 return (void *)bp; 904 } 905 906 /* Carve off a new pool. */ 907 assert(usable_arenas->nfreepools > 0); 908 assert(usable_arenas->freepools == NULL); 909 pool = (poolp)usable_arenas->pool_address; 910 assert((block*)pool <= (block*)usable_arenas->address + 911 ARENA_SIZE - POOL_SIZE); 912 pool->arenaindex = usable_arenas - arenas; 913 assert(&arenas[pool->arenaindex] == usable_arenas); 914 pool->szidx = DUMMY_SIZE_IDX; 915 usable_arenas->pool_address += POOL_SIZE; 916 --usable_arenas->nfreepools; 917 918 if (usable_arenas->nfreepools == 0) { 919 assert(usable_arenas->nextarena == NULL || 920 usable_arenas->nextarena->prevarena == 921 usable_arenas); 922 /* Unlink the arena: it is completely allocated. */ 923 usable_arenas = usable_arenas->nextarena; 924 if (usable_arenas != NULL) { 925 usable_arenas->prevarena = NULL; 926 assert(usable_arenas->address != 0); 927 } 928 } 929 930 goto init_pool; 931 } 932 933 /* The small block allocator ends here. */ 904 934 905 935 redirect: 906 907 908 909 910 911 912 913 936 /* Redirect the original request to the underlying (libc) allocator. 937 * We jump here on bigger requests, on error in the code above (as a 938 * last chance to serve the request) or when the max memory limit 939 * has been reached. 940 */ 941 if (nbytes == 0) 942 nbytes = 1; 943 return (void *)malloc(nbytes); 914 944 } 915 945 … … 920 950 PyObject_Free(void *p) 921 951 { 922 poolp pool; 923 block *lastfree; 924 poolp next, prev; 925 uint size; 926 927 if (p == NULL) /* free(NULL) has no effect */ 928 return; 929 930 pool = POOL_ADDR(p); 931 if (Py_ADDRESS_IN_RANGE(p, pool)) { 932 /* We allocated this address. */ 933 LOCK(); 934 /* Link p to the start of the pool's freeblock list. Since 935 * the pool had at least the p block outstanding, the pool 936 * wasn't empty (so it's already in a usedpools[] list, or 937 * was full and is in no list -- it's not in the freeblocks 938 * list in any case). 939 */ 940 assert(pool->ref.count > 0); /* else it was empty */ 941 *(block **)p = lastfree = pool->freeblock; 942 pool->freeblock = (block *)p; 943 if (lastfree) { 944 struct arena_object* ao; 945 uint nf; /* ao->nfreepools */ 946 947 /* freeblock wasn't NULL, so the pool wasn't full, 948 * and the pool is in a usedpools[] list. 949 */ 950 if (--pool->ref.count != 0) { 951 /* pool isn't empty: leave it in usedpools */ 952 UNLOCK(); 953 return; 954 } 955 /* Pool is now empty: unlink from usedpools, and 956 * link to the front of freepools. This ensures that 957 * previously freed pools will be allocated later 958 * (being not referenced, they are perhaps paged out). 959 */ 960 next = pool->nextpool; 961 prev = pool->prevpool; 962 next->prevpool = prev; 963 prev->nextpool = next; 964 965 /* Link the pool to freepools. This is a singly-linked 966 * list, and pool->prevpool isn't used there. 967 */ 968 ao = &arenas[pool->arenaindex]; 969 pool->nextpool = ao->freepools; 970 ao->freepools = pool; 971 nf = ++ao->nfreepools; 972 973 /* All the rest is arena management. We just freed 974 * a pool, and there are 4 cases for arena mgmt: 975 * 1. If all the pools are free, return the arena to 976 * the system free(). 977 * 2. If this is the only free pool in the arena, 978 * add the arena back to the `usable_arenas` list. 979 * 3. If the "next" arena has a smaller count of free 980 * pools, we have to "slide this arena right" to 981 * restore that usable_arenas is sorted in order of 982 * nfreepools. 983 * 4. Else there's nothing more to do. 984 */ 985 if (nf == ao->ntotalpools) { 986 /* Case 1. First unlink ao from usable_arenas. 987 */ 988 assert(ao->prevarena == NULL || 989 ao->prevarena->address != 0); 990 assert(ao ->nextarena == NULL || 991 ao->nextarena->address != 0); 992 993 /* Fix the pointer in the prevarena, or the 994 * usable_arenas pointer. 995 */ 996 if (ao->prevarena == NULL) { 997 usable_arenas = ao->nextarena; 998 assert(usable_arenas == NULL || 999 usable_arenas->address != 0); 1000 } 1001 else { 1002 assert(ao->prevarena->nextarena == ao); 1003 ao->prevarena->nextarena = 1004 ao->nextarena; 1005 } 1006 /* Fix the pointer in the nextarena. */ 1007 if (ao->nextarena != NULL) { 1008 assert(ao->nextarena->prevarena == ao); 1009 ao->nextarena->prevarena = 1010 ao->prevarena; 1011 } 1012 /* Record that this arena_object slot is 1013 * available to be reused. 1014 */ 1015 ao->nextarena = unused_arena_objects; 1016 unused_arena_objects = ao; 1017 1018 /* Free the entire arena. */ 1019 free((void *)ao->address); 1020 ao->address = 0; /* mark unassociated */ 1021 --narenas_currently_allocated; 1022 1023 UNLOCK(); 1024 return; 1025 } 1026 if (nf == 1) { 1027 /* Case 2. Put ao at the head of 1028 * usable_arenas. Note that because 1029 * ao->nfreepools was 0 before, ao isn't 1030 * currently on the usable_arenas list. 1031 */ 1032 ao->nextarena = usable_arenas; 1033 ao->prevarena = NULL; 1034 if (usable_arenas) 1035 usable_arenas->prevarena = ao; 1036 usable_arenas = ao; 1037 assert(usable_arenas->address != 0); 1038 1039 UNLOCK(); 1040 return; 1041 } 1042 /* If this arena is now out of order, we need to keep 1043 * the list sorted. The list is kept sorted so that 1044 * the "most full" arenas are used first, which allows 1045 * the nearly empty arenas to be completely freed. In 1046 * a few un-scientific tests, it seems like this 1047 * approach allowed a lot more memory to be freed. 1048 */ 1049 if (ao->nextarena == NULL || 1050 nf <= ao->nextarena->nfreepools) { 1051 /* Case 4. Nothing to do. */ 1052 UNLOCK(); 1053 return; 1054 } 1055 /* Case 3: We have to move the arena towards the end 1056 * of the list, because it has more free pools than 1057 * the arena to its right. 1058 * First unlink ao from usable_arenas. 1059 */ 1060 if (ao->prevarena != NULL) { 1061 /* ao isn't at the head of the list */ 1062 assert(ao->prevarena->nextarena == ao); 1063 ao->prevarena->nextarena = ao->nextarena; 1064 } 1065 else { 1066 /* ao is at the head of the list */ 1067 assert(usable_arenas == ao); 1068 usable_arenas = ao->nextarena; 1069 } 1070 ao->nextarena->prevarena = ao->prevarena; 1071 1072 /* Locate the new insertion point by iterating over 1073 * the list, using our nextarena pointer. 1074 */ 1075 while (ao->nextarena != NULL && 1076 nf > ao->nextarena->nfreepools) { 1077 ao->prevarena = ao->nextarena; 1078 ao->nextarena = ao->nextarena->nextarena; 1079 } 1080 1081 /* Insert ao at this point. */ 1082 assert(ao->nextarena == NULL || 1083 ao->prevarena == ao->nextarena->prevarena); 1084 assert(ao->prevarena->nextarena == ao->nextarena); 1085 1086 ao->prevarena->nextarena = ao; 1087 if (ao->nextarena != NULL) 1088 ao->nextarena->prevarena = ao; 1089 1090 /* Verify that the swaps worked. */ 1091 assert(ao->nextarena == NULL || 1092 nf <= ao->nextarena->nfreepools); 1093 assert(ao->prevarena == NULL || 1094 nf > ao->prevarena->nfreepools); 1095 assert(ao->nextarena == NULL || 1096 ao->nextarena->prevarena == ao); 1097 assert((usable_arenas == ao && 1098 ao->prevarena == NULL) || 1099 ao->prevarena->nextarena == ao); 1100 1101 UNLOCK(); 1102 return; 1103 } 1104 /* Pool was full, so doesn't currently live in any list: 1105 * link it to the front of the appropriate usedpools[] list. 1106 * This mimics LRU pool usage for new allocations and 1107 * targets optimal filling when several pools contain 1108 * blocks of the same size class. 1109 */ 1110 --pool->ref.count; 1111 assert(pool->ref.count > 0); /* else the pool is empty */ 1112 size = pool->szidx; 1113 next = usedpools[size + size]; 1114 prev = next->prevpool; 1115 /* insert pool before next: prev <-> pool <-> next */ 1116 pool->nextpool = next; 1117 pool->prevpool = prev; 1118 next->prevpool = pool; 1119 prev->nextpool = pool; 1120 UNLOCK(); 1121 return; 1122 } 1123 1124 /* We didn't allocate this address. */ 1125 free(p); 952 poolp pool; 953 block *lastfree; 954 poolp next, prev; 955 uint size; 956 #ifndef Py_USING_MEMORY_DEBUGGER 957 uint arenaindex_temp; 958 #endif 959 960 if (p == NULL) /* free(NULL) has no effect */ 961 return; 962 963 #ifdef WITH_VALGRIND 964 if (UNLIKELY(running_on_valgrind > 0)) 965 goto redirect; 966 #endif 967 968 pool = POOL_ADDR(p); 969 if (Py_ADDRESS_IN_RANGE(p, pool)) { 970 /* We allocated this address. */ 971 LOCK(); 972 /* Link p to the start of the pool's freeblock list. Since 973 * the pool had at least the p block outstanding, the pool 974 * wasn't empty (so it's already in a usedpools[] list, or 975 * was full and is in no list -- it's not in the freeblocks 976 * list in any case). 977 */ 978 assert(pool->ref.count > 0); /* else it was empty */ 979 *(block **)p = lastfree = pool->freeblock; 980 pool->freeblock = (block *)p; 981 if (lastfree) { 982 struct arena_object* ao; 983 uint nf; /* ao->nfreepools */ 984 985 /* freeblock wasn't NULL, so the pool wasn't full, 986 * and the pool is in a usedpools[] list. 987 */ 988 if (--pool->ref.count != 0) { 989 /* pool isn't empty: leave it in usedpools */ 990 UNLOCK(); 991 return; 992 } 993 /* Pool is now empty: unlink from usedpools, and 994 * link to the front of freepools. This ensures that 995 * previously freed pools will be allocated later 996 * (being not referenced, they are perhaps paged out). 997 */ 998 next = pool->nextpool; 999 prev = pool->prevpool; 1000 next->prevpool = prev; 1001 prev->nextpool = next; 1002 1003 /* Link the pool to freepools. This is a singly-linked 1004 * list, and pool->prevpool isn't used there. 1005 */ 1006 ao = &arenas[pool->arenaindex]; 1007 pool->nextpool = ao->freepools; 1008 ao->freepools = pool; 1009 nf = ++ao->nfreepools; 1010 1011 /* All the rest is arena management. We just freed 1012 * a pool, and there are 4 cases for arena mgmt: 1013 * 1. If all the pools are free, return the arena to 1014 * the system free(). 1015 * 2. If this is the only free pool in the arena, 1016 * add the arena back to the `usable_arenas` list. 1017 * 3. If the "next" arena has a smaller count of free 1018 * pools, we have to "slide this arena right" to 1019 * restore that usable_arenas is sorted in order of 1020 * nfreepools. 1021 * 4. Else there's nothing more to do. 1022 */ 1023 if (nf == ao->ntotalpools) { 1024 /* Case 1. First unlink ao from usable_arenas. 1025 */ 1026 assert(ao->prevarena == NULL || 1027 ao->prevarena->address != 0); 1028 assert(ao ->nextarena == NULL || 1029 ao->nextarena->address != 0); 1030 1031 /* Fix the pointer in the prevarena, or the 1032 * usable_arenas pointer. 1033 */ 1034 if (ao->prevarena == NULL) { 1035 usable_arenas = ao->nextarena; 1036 assert(usable_arenas == NULL || 1037 usable_arenas->address != 0); 1038 } 1039 else { 1040 assert(ao->prevarena->nextarena == ao); 1041 ao->prevarena->nextarena = 1042 ao->nextarena; 1043 } 1044 /* Fix the pointer in the nextarena. */ 1045 if (ao->nextarena != NULL) { 1046 assert(ao->nextarena->prevarena == ao); 1047 ao->nextarena->prevarena = 1048 ao->prevarena; 1049 } 1050 /* Record that this arena_object slot is 1051 * available to be reused. 1052 */ 1053 ao->nextarena = unused_arena_objects; 1054 unused_arena_objects = ao; 1055 1056 /* Free the entire arena. */ 1057 free((void *)ao->address); 1058 ao->address = 0; /* mark unassociated */ 1059 --narenas_currently_allocated; 1060 1061 UNLOCK(); 1062 return; 1063 } 1064 if (nf == 1) { 1065 /* Case 2. Put ao at the head of 1066 * usable_arenas. Note that because 1067 * ao->nfreepools was 0 before, ao isn't 1068 * currently on the usable_arenas list. 1069 */ 1070 ao->nextarena = usable_arenas; 1071 ao->prevarena = NULL; 1072 if (usable_arenas) 1073 usable_arenas->prevarena = ao; 1074 usable_arenas = ao; 1075 assert(usable_arenas->address != 0); 1076 1077 UNLOCK(); 1078 return; 1079 } 1080 /* If this arena is now out of order, we need to keep 1081 * the list sorted. The list is kept sorted so that 1082 * the "most full" arenas are used first, which allows 1083 * the nearly empty arenas to be completely freed. In 1084 * a few un-scientific tests, it seems like this 1085 * approach allowed a lot more memory to be freed. 1086 */ 1087 if (ao->nextarena == NULL || 1088 nf <= ao->nextarena->nfreepools) { 1089 /* Case 4. Nothing to do. */ 1090 UNLOCK(); 1091 return; 1092 } 1093 /* Case 3: We have to move the arena towards the end 1094 * of the list, because it has more free pools than 1095 * the arena to its right. 1096 * First unlink ao from usable_arenas. 1097 */ 1098 if (ao->prevarena != NULL) { 1099 /* ao isn't at the head of the list */ 1100 assert(ao->prevarena->nextarena == ao); 1101 ao->prevarena->nextarena = ao->nextarena; 1102 } 1103 else { 1104 /* ao is at the head of the list */ 1105 assert(usable_arenas == ao); 1106 usable_arenas = ao->nextarena; 1107 } 1108 ao->nextarena->prevarena = ao->prevarena; 1109 1110 /* Locate the new insertion point by iterating over 1111 * the list, using our nextarena pointer. 1112 */ 1113 while (ao->nextarena != NULL && 1114 nf > ao->nextarena->nfreepools) { 1115 ao->prevarena = ao->nextarena; 1116 ao->nextarena = ao->nextarena->nextarena; 1117 } 1118 1119 /* Insert ao at this point. */ 1120 assert(ao->nextarena == NULL || 1121 ao->prevarena == ao->nextarena->prevarena); 1122 assert(ao->prevarena->nextarena == ao->nextarena); 1123 1124 ao->prevarena->nextarena = ao; 1125 if (ao->nextarena != NULL) 1126 ao->nextarena->prevarena = ao; 1127 1128 /* Verify that the swaps worked. */ 1129 assert(ao->nextarena == NULL || 1130 nf <= ao->nextarena->nfreepools); 1131 assert(ao->prevarena == NULL || 1132 nf > ao->prevarena->nfreepools); 1133 assert(ao->nextarena == NULL || 1134 ao->nextarena->prevarena == ao); 1135 assert((usable_arenas == ao && 1136 ao->prevarena == NULL) || 1137 ao->prevarena->nextarena == ao); 1138 1139 UNLOCK(); 1140 return; 1141 } 1142 /* Pool was full, so doesn't currently live in any list: 1143 * link it to the front of the appropriate usedpools[] list. 1144 * This mimics LRU pool usage for new allocations and 1145 * targets optimal filling when several pools contain 1146 * blocks of the same size class. 1147 */ 1148 --pool->ref.count; 1149 assert(pool->ref.count > 0); /* else the pool is empty */ 1150 size = pool->szidx; 1151 next = usedpools[size + size]; 1152 prev = next->prevpool; 1153 /* insert pool before next: prev <-> pool <-> next */ 1154 pool->nextpool = next; 1155 pool->prevpool = prev; 1156 next->prevpool = pool; 1157 prev->nextpool = pool; 1158 UNLOCK(); 1159 return; 1160 } 1161 1162 #ifdef WITH_VALGRIND 1163 redirect: 1164 #endif 1165 /* We didn't allocate this address. */ 1166 free(p); 1126 1167 } 1127 1168 … … 1135 1176 PyObject_Realloc(void *p, size_t nbytes) 1136 1177 { 1137 void *bp; 1138 poolp pool; 1139 size_t size; 1140 1141 if (p == NULL) 1142 return PyObject_Malloc(nbytes); 1143 1144 /* 1145 * Limit ourselves to PY_SSIZE_T_MAX bytes to prevent security holes. 1146 * Most python internals blindly use a signed Py_ssize_t to track 1147 * things without checking for overflows or negatives. 1148 * As size_t is unsigned, checking for nbytes < 0 is not required. 1149 */ 1150 if (nbytes > PY_SSIZE_T_MAX) 1151 return NULL; 1152 1153 pool = POOL_ADDR(p); 1154 if (Py_ADDRESS_IN_RANGE(p, pool)) { 1155 /* We're in charge of this block */ 1156 size = INDEX2SIZE(pool->szidx); 1157 if (nbytes <= size) { 1158 /* The block is staying the same or shrinking. If 1159 * it's shrinking, there's a tradeoff: it costs 1160 * cycles to copy the block to a smaller size class, 1161 * but it wastes memory not to copy it. The 1162 * compromise here is to copy on shrink only if at 1163 * least 25% of size can be shaved off. 1164 */ 1165 if (4 * nbytes > 3 * size) { 1166 /* It's the same, 1167 * or shrinking and new/old > 3/4. 1168 */ 1169 return p; 1170 } 1171 size = nbytes; 1172 } 1173 bp = PyObject_Malloc(nbytes); 1174 if (bp != NULL) { 1175 memcpy(bp, p, size); 1176 PyObject_Free(p); 1177 } 1178 return bp; 1179 } 1180 /* We're not managing this block. If nbytes <= 1181 * SMALL_REQUEST_THRESHOLD, it's tempting to try to take over this 1182 * block. However, if we do, we need to copy the valid data from 1183 * the C-managed block to one of our blocks, and there's no portable 1184 * way to know how much of the memory space starting at p is valid. 1185 * As bug 1185883 pointed out the hard way, it's possible that the 1186 * C-managed block is "at the end" of allocated VM space, so that 1187 * a memory fault can occur if we try to copy nbytes bytes starting 1188 * at p. Instead we punt: let C continue to manage this block. 1189 */ 1190 if (nbytes) 1191 return realloc(p, nbytes); 1192 /* C doesn't define the result of realloc(p, 0) (it may or may not 1193 * return NULL then), but Python's docs promise that nbytes==0 never 1194 * returns NULL. We don't pass 0 to realloc(), to avoid that endcase 1195 * to begin with. Even then, we can't be sure that realloc() won't 1196 * return NULL. 1197 */ 1198 bp = realloc(p, 1); 1199 return bp ? bp : p; 1200 } 1201 1202 #else /* ! WITH_PYMALLOC */ 1178 void *bp; 1179 poolp pool; 1180 size_t size; 1181 #ifndef Py_USING_MEMORY_DEBUGGER 1182 uint arenaindex_temp; 1183 #endif 1184 1185 if (p == NULL) 1186 return PyObject_Malloc(nbytes); 1187 1188 /* 1189 * Limit ourselves to PY_SSIZE_T_MAX bytes to prevent security holes. 1190 * Most python internals blindly use a signed Py_ssize_t to track 1191 * things without checking for overflows or negatives. 1192 * As size_t is unsigned, checking for nbytes < 0 is not required. 1193 */ 1194 if (nbytes > PY_SSIZE_T_MAX) 1195 return NULL; 1196 1197 #ifdef WITH_VALGRIND 1198 /* Treat running_on_valgrind == -1 the same as 0 */ 1199 if (UNLIKELY(running_on_valgrind > 0)) 1200 goto redirect; 1201 #endif 1202 1203 pool = POOL_ADDR(p); 1204 if (Py_ADDRESS_IN_RANGE(p, pool)) { 1205 /* We're in charge of this block */ 1206 size = INDEX2SIZE(pool->szidx); 1207 if (nbytes <= size) { 1208 /* The block is staying the same or shrinking. If 1209 * it's shrinking, there's a tradeoff: it costs 1210 * cycles to copy the block to a smaller size class, 1211 * but it wastes memory not to copy it. The 1212 * compromise here is to copy on shrink only if at 1213 * least 25% of size can be shaved off. 1214 */ 1215 if (4 * nbytes > 3 * size) { 1216 /* It's the same, 1217 * or shrinking and new/old > 3/4. 1218 */ 1219 return p; 1220 } 1221 size = nbytes; 1222 } 1223 bp = PyObject_Malloc(nbytes); 1224 if (bp != NULL) { 1225 memcpy(bp, p, size); 1226 PyObject_Free(p); 1227 } 1228 return bp; 1229 } 1230 #ifdef WITH_VALGRIND 1231 redirect: 1232 #endif 1233 /* We're not managing this block. If nbytes <= 1234 * SMALL_REQUEST_THRESHOLD, it's tempting to try to take over this 1235 * block. However, if we do, we need to copy the valid data from 1236 * the C-managed block to one of our blocks, and there's no portable 1237 * way to know how much of the memory space starting at p is valid. 1238 * As bug 1185883 pointed out the hard way, it's possible that the 1239 * C-managed block is "at the end" of allocated VM space, so that 1240 * a memory fault can occur if we try to copy nbytes bytes starting 1241 * at p. Instead we punt: let C continue to manage this block. 1242 */ 1243 if (nbytes) 1244 return realloc(p, nbytes); 1245 /* C doesn't define the result of realloc(p, 0) (it may or may not 1246 * return NULL then), but Python's docs promise that nbytes==0 never 1247 * returns NULL. We don't pass 0 to realloc(), to avoid that endcase 1248 * to begin with. Even then, we can't be sure that realloc() won't 1249 * return NULL. 1250 */ 1251 bp = realloc(p, 1); 1252 return bp ? bp : p; 1253 } 1254 1255 #else /* ! WITH_PYMALLOC */ 1203 1256 1204 1257 /*==========================================================================*/ … … 1209 1262 PyObject_Malloc(size_t n) 1210 1263 { 1211 1264 return PyMem_MALLOC(n); 1212 1265 } 1213 1266 … … 1215 1268 PyObject_Realloc(void *p, size_t n) 1216 1269 { 1217 1270 return PyMem_REALLOC(p, n); 1218 1271 } 1219 1272 … … 1221 1274 PyObject_Free(void *p) 1222 1275 { 1223 1276 PyMem_FREE(p); 1224 1277 } 1225 1278 #endif /* WITH_PYMALLOC */ … … 1242 1295 #define FORBIDDENBYTE 0xFB /* untouchable bytes at each end of a block */ 1243 1296 1244 static size_t serialno = 0; /* incremented on each debug {m,re}alloc */ 1297 /* We tag each block with an API ID in order to tag API violations */ 1298 #define _PYMALLOC_MEM_ID 'm' /* the PyMem_Malloc() API */ 1299 #define _PYMALLOC_OBJ_ID 'o' /* The PyObject_Malloc() API */ 1300 1301 static size_t serialno = 0; /* incremented on each debug {m,re}alloc */ 1245 1302 1246 1303 /* serialno is always incremented via calling this routine. The point is … … 1250 1307 bumpserialno(void) 1251 1308 { 1252 1309 ++serialno; 1253 1310 } 1254 1311 … … 1259 1316 read_size_t(const void *p) 1260 1317 { 1261 1262 1263 1264 1265 1266 1267 1318 const uchar *q = (const uchar *)p; 1319 size_t result = *q++; 1320 int i; 1321 1322 for (i = SST; --i > 0; ++q) 1323 result = (result << 8) | *q; 1324 return result; 1268 1325 } 1269 1326 … … 1274 1331 write_size_t(void *p, size_t n) 1275 1332 { 1276 1277 1278 1279 1280 1281 1282 1333 uchar *q = (uchar *)p + SST - 1; 1334 int i; 1335 1336 for (i = SST; --i >= 0; --q) { 1337 *q = (uchar)(n & 0xff); 1338 n >>= 8; 1339 } 1283 1340 } 1284 1341 … … 1291 1348 pool_is_in_list(const poolp target, poolp list) 1292 1349 { 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1350 poolp origlist = list; 1351 assert(target != NULL); 1352 if (list == NULL) 1353 return 0; 1354 do { 1355 if (target == list) 1356 return 1; 1357 list = list->nextpool; 1358 } while (list != NULL && list != origlist); 1359 return 0; 1303 1360 } 1304 1361 … … 1306 1363 #define pool_is_in_list(X, Y) 1 1307 1364 1308 #endif 1365 #endif /* Py_DEBUG */ 1309 1366 1310 1367 /* Let S = sizeof(size_t). The debug malloc asks for 4*S extra bytes and … … 1332 1389 */ 1333 1390 1391 /* debug replacements for the PyMem_* memory API */ 1392 void * 1393 _PyMem_DebugMalloc(size_t nbytes) 1394 { 1395 return _PyObject_DebugMallocApi(_PYMALLOC_MEM_ID, nbytes); 1396 } 1397 void * 1398 _PyMem_DebugRealloc(void *p, size_t nbytes) 1399 { 1400 return _PyObject_DebugReallocApi(_PYMALLOC_MEM_ID, p, nbytes); 1401 } 1402 void 1403 _PyMem_DebugFree(void *p) 1404 { 1405 _PyObject_DebugFreeApi(_PYMALLOC_MEM_ID, p); 1406 } 1407 1408 /* debug replacements for the PyObject_* memory API */ 1334 1409 void * 1335 1410 _PyObject_DebugMalloc(size_t nbytes) 1336 1411 { 1337 uchar *p; /* base address of malloc'ed block */ 1338 uchar *tail; /* p + 2*SST + nbytes == pointer to tail pad bytes */ 1339 size_t total; /* nbytes + 4*SST */ 1340 1341 bumpserialno(); 1342 total = nbytes + 4*SST; 1343 if (total < nbytes) 1344 /* overflow: can't represent total as a size_t */ 1345 return NULL; 1346 1347 p = (uchar *)PyObject_Malloc(total); 1348 if (p == NULL) 1349 return NULL; 1350 1351 write_size_t(p, nbytes); 1352 memset(p + SST, FORBIDDENBYTE, SST); 1353 1354 if (nbytes > 0) 1355 memset(p + 2*SST, CLEANBYTE, nbytes); 1356 1357 tail = p + 2*SST + nbytes; 1358 memset(tail, FORBIDDENBYTE, SST); 1359 write_size_t(tail + SST, serialno); 1360 1361 return p + 2*SST; 1412 return _PyObject_DebugMallocApi(_PYMALLOC_OBJ_ID, nbytes); 1413 } 1414 void * 1415 _PyObject_DebugRealloc(void *p, size_t nbytes) 1416 { 1417 return _PyObject_DebugReallocApi(_PYMALLOC_OBJ_ID, p, nbytes); 1418 } 1419 void 1420 _PyObject_DebugFree(void *p) 1421 { 1422 _PyObject_DebugFreeApi(_PYMALLOC_OBJ_ID, p); 1423 } 1424 void 1425 _PyObject_DebugCheckAddress(const void *p) 1426 { 1427 _PyObject_DebugCheckAddressApi(_PYMALLOC_OBJ_ID, p); 1428 } 1429 1430 1431 /* generic debug memory api, with an "id" to identify the API in use */ 1432 void * 1433 _PyObject_DebugMallocApi(char id, size_t nbytes) 1434 { 1435 uchar *p; /* base address of malloc'ed block */ 1436 uchar *tail; /* p + 2*SST + nbytes == pointer to tail pad bytes */ 1437 size_t total; /* nbytes + 4*SST */ 1438 1439 bumpserialno(); 1440 total = nbytes + 4*SST; 1441 if (total < nbytes) 1442 /* overflow: can't represent total as a size_t */ 1443 return NULL; 1444 1445 p = (uchar *)PyObject_Malloc(total); 1446 if (p == NULL) 1447 return NULL; 1448 1449 /* at p, write size (SST bytes), id (1 byte), pad (SST-1 bytes) */ 1450 write_size_t(p, nbytes); 1451 p[SST] = (uchar)id; 1452 memset(p + SST + 1 , FORBIDDENBYTE, SST-1); 1453 1454 if (nbytes > 0) 1455 memset(p + 2*SST, CLEANBYTE, nbytes); 1456 1457 /* at tail, write pad (SST bytes) and serialno (SST bytes) */ 1458 tail = p + 2*SST + nbytes; 1459 memset(tail, FORBIDDENBYTE, SST); 1460 write_size_t(tail + SST, serialno); 1461 1462 return p + 2*SST; 1362 1463 } 1363 1464 1364 1465 /* The debug free first checks the 2*SST bytes on each end for sanity (in 1365 particular, that the FORBIDDENBYTEs are still intact).1466 particular, that the FORBIDDENBYTEs with the api ID are still intact). 1366 1467 Then fills the original bytes with DEADBYTE. 1367 1468 Then calls the underlying free. 1368 1469 */ 1369 1470 void 1370 _PyObject_DebugFree(void *p) 1371 { 1372 uchar *q = (uchar *)p - 2*SST; /* address returned from malloc */ 1373 size_t nbytes; 1374 1375 if (p == NULL) 1376 return; 1377 _PyObject_DebugCheckAddress(p); 1378 nbytes = read_size_t(q); 1379 if (nbytes > 0) 1380 memset(q, DEADBYTE, nbytes); 1381 PyObject_Free(q); 1471 _PyObject_DebugFreeApi(char api, void *p) 1472 { 1473 uchar *q = (uchar *)p - 2*SST; /* address returned from malloc */ 1474 size_t nbytes; 1475 1476 if (p == NULL) 1477 return; 1478 _PyObject_DebugCheckAddressApi(api, p); 1479 nbytes = read_size_t(q); 1480 nbytes += 4*SST; 1481 if (nbytes > 0) 1482 memset(q, DEADBYTE, nbytes); 1483 PyObject_Free(q); 1382 1484 } 1383 1485 1384 1486 void * 1385 _PyObject_DebugRealloc(void *p, size_t nbytes) 1386 { 1387 uchar *q = (uchar *)p; 1388 uchar *tail; 1389 size_t total; /* nbytes + 4*SST */ 1390 size_t original_nbytes; 1391 int i; 1392 1393 if (p == NULL) 1394 return _PyObject_DebugMalloc(nbytes); 1395 1396 _PyObject_DebugCheckAddress(p); 1397 bumpserialno(); 1398 original_nbytes = read_size_t(q - 2*SST); 1399 total = nbytes + 4*SST; 1400 if (total < nbytes) 1401 /* overflow: can't represent total as a size_t */ 1402 return NULL; 1403 1404 if (nbytes < original_nbytes) { 1405 /* shrinking: mark old extra memory dead */ 1406 memset(q + nbytes, DEADBYTE, original_nbytes - nbytes); 1407 } 1408 1409 /* Resize and add decorations. */ 1410 q = (uchar *)PyObject_Realloc(q - 2*SST, total); 1411 if (q == NULL) 1412 return NULL; 1413 1414 write_size_t(q, nbytes); 1415 for (i = 0; i < SST; ++i) 1416 assert(q[SST + i] == FORBIDDENBYTE); 1417 q += 2*SST; 1418 tail = q + nbytes; 1419 memset(tail, FORBIDDENBYTE, SST); 1420 write_size_t(tail + SST, serialno); 1421 1422 if (nbytes > original_nbytes) { 1423 /* growing: mark new extra memory clean */ 1424 memset(q + original_nbytes, CLEANBYTE, 1425 nbytes - original_nbytes); 1426 } 1427 1428 return q; 1487 _PyObject_DebugReallocApi(char api, void *p, size_t nbytes) 1488 { 1489 uchar *q = (uchar *)p; 1490 uchar *tail; 1491 size_t total; /* nbytes + 4*SST */ 1492 size_t original_nbytes; 1493 int i; 1494 1495 if (p == NULL) 1496 return _PyObject_DebugMallocApi(api, nbytes); 1497 1498 _PyObject_DebugCheckAddressApi(api, p); 1499 bumpserialno(); 1500 original_nbytes = read_size_t(q - 2*SST); 1501 total = nbytes + 4*SST; 1502 if (total < nbytes) 1503 /* overflow: can't represent total as a size_t */ 1504 return NULL; 1505 1506 if (nbytes < original_nbytes) { 1507 /* shrinking: mark old extra memory dead */ 1508 memset(q + nbytes, DEADBYTE, original_nbytes - nbytes + 2*SST); 1509 } 1510 1511 /* Resize and add decorations. We may get a new pointer here, in which 1512 * case we didn't get the chance to mark the old memory with DEADBYTE, 1513 * but we live with that. 1514 */ 1515 q = (uchar *)PyObject_Realloc(q - 2*SST, total); 1516 if (q == NULL) 1517 return NULL; 1518 1519 write_size_t(q, nbytes); 1520 assert(q[SST] == (uchar)api); 1521 for (i = 1; i < SST; ++i) 1522 assert(q[SST + i] == FORBIDDENBYTE); 1523 q += 2*SST; 1524 tail = q + nbytes; 1525 memset(tail, FORBIDDENBYTE, SST); 1526 write_size_t(tail + SST, serialno); 1527 1528 if (nbytes > original_nbytes) { 1529 /* growing: mark new extra memory clean */ 1530 memset(q + original_nbytes, CLEANBYTE, 1531 nbytes - original_nbytes); 1532 } 1533 1534 return q; 1429 1535 } 1430 1536 … … 1432 1538 * If anything is wrong, print info to stderr via _PyObject_DebugDumpAddress, 1433 1539 * and call Py_FatalError to kill the program. 1540 * The API id, is also checked. 1434 1541 */ 1435 1542 void 1436 _PyObject_DebugCheckAddress(const void *p) 1437 { 1438 const uchar *q = (const uchar *)p; 1439 char *msg; 1440 size_t nbytes; 1441 const uchar *tail; 1442 int i; 1443 1444 if (p == NULL) { 1445 msg = "didn't expect a NULL pointer"; 1446 goto error; 1447 } 1448 1449 /* Check the stuff at the start of p first: if there's underwrite 1450 * corruption, the number-of-bytes field may be nuts, and checking 1451 * the tail could lead to a segfault then. 1452 */ 1453 for (i = SST; i >= 1; --i) { 1454 if (*(q-i) != FORBIDDENBYTE) { 1455 msg = "bad leading pad byte"; 1456 goto error; 1457 } 1458 } 1459 1460 nbytes = read_size_t(q - 2*SST); 1461 tail = q + nbytes; 1462 for (i = 0; i < SST; ++i) { 1463 if (tail[i] != FORBIDDENBYTE) { 1464 msg = "bad trailing pad byte"; 1465 goto error; 1466 } 1467 } 1468 1469 return; 1543 _PyObject_DebugCheckAddressApi(char api, const void *p) 1544 { 1545 const uchar *q = (const uchar *)p; 1546 char msgbuf[64]; 1547 char *msg; 1548 size_t nbytes; 1549 const uchar *tail; 1550 int i; 1551 char id; 1552 1553 if (p == NULL) { 1554 msg = "didn't expect a NULL pointer"; 1555 goto error; 1556 } 1557 1558 /* Check the API id */ 1559 id = (char)q[-SST]; 1560 if (id != api) { 1561 msg = msgbuf; 1562 snprintf(msg, sizeof(msgbuf), "bad ID: Allocated using API '%c', verified using API '%c'", id, api); 1563 msgbuf[sizeof(msgbuf)-1] = 0; 1564 goto error; 1565 } 1566 1567 /* Check the stuff at the start of p first: if there's underwrite 1568 * corruption, the number-of-bytes field may be nuts, and checking 1569 * the tail could lead to a segfault then. 1570 */ 1571 for (i = SST-1; i >= 1; --i) { 1572 if (*(q-i) != FORBIDDENBYTE) { 1573 msg = "bad leading pad byte"; 1574 goto error; 1575 } 1576 } 1577 1578 nbytes = read_size_t(q - 2*SST); 1579 tail = q + nbytes; 1580 for (i = 0; i < SST; ++i) { 1581 if (tail[i] != FORBIDDENBYTE) { 1582 msg = "bad trailing pad byte"; 1583 goto error; 1584 } 1585 } 1586 1587 return; 1470 1588 1471 1589 error: 1472 1473 1590 _PyObject_DebugDumpAddress(p); 1591 Py_FatalError(msg); 1474 1592 } 1475 1593 … … 1478 1596 _PyObject_DebugDumpAddress(const void *p) 1479 1597 { 1480 const uchar *q = (const uchar *)p; 1481 const uchar *tail; 1482 size_t nbytes, serial; 1483 int i; 1484 int ok; 1485 1486 fprintf(stderr, "Debug memory block at address p=%p:\n", p); 1487 if (p == NULL) 1488 return; 1489 1490 nbytes = read_size_t(q - 2*SST); 1491 fprintf(stderr, " %" PY_FORMAT_SIZE_T "u bytes originally " 1492 "requested\n", nbytes); 1493 1494 /* In case this is nuts, check the leading pad bytes first. */ 1495 fprintf(stderr, " The %d pad bytes at p-%d are ", SST, SST); 1496 ok = 1; 1497 for (i = 1; i <= SST; ++i) { 1498 if (*(q-i) != FORBIDDENBYTE) { 1499 ok = 0; 1500 break; 1501 } 1502 } 1503 if (ok) 1504 fputs("FORBIDDENBYTE, as expected.\n", stderr); 1505 else { 1506 fprintf(stderr, "not all FORBIDDENBYTE (0x%02x):\n", 1507 FORBIDDENBYTE); 1508 for (i = SST; i >= 1; --i) { 1509 const uchar byte = *(q-i); 1510 fprintf(stderr, " at p-%d: 0x%02x", i, byte); 1511 if (byte != FORBIDDENBYTE) 1512 fputs(" *** OUCH", stderr); 1513 fputc('\n', stderr); 1514 } 1515 1516 fputs(" Because memory is corrupted at the start, the " 1517 "count of bytes requested\n" 1518 " may be bogus, and checking the trailing pad " 1519 "bytes may segfault.\n", stderr); 1520 } 1521 1522 tail = q + nbytes; 1523 fprintf(stderr, " The %d pad bytes at tail=%p are ", SST, tail); 1524 ok = 1; 1525 for (i = 0; i < SST; ++i) { 1526 if (tail[i] != FORBIDDENBYTE) { 1527 ok = 0; 1528 break; 1529 } 1530 } 1531 if (ok) 1532 fputs("FORBIDDENBYTE, as expected.\n", stderr); 1533 else { 1534 fprintf(stderr, "not all FORBIDDENBYTE (0x%02x):\n", 1535 FORBIDDENBYTE); 1536 for (i = 0; i < SST; ++i) { 1537 const uchar byte = tail[i]; 1538 fprintf(stderr, " at tail+%d: 0x%02x", 1539 i, byte); 1540 if (byte != FORBIDDENBYTE) 1541 fputs(" *** OUCH", stderr); 1542 fputc('\n', stderr); 1543 } 1544 } 1545 1546 serial = read_size_t(tail + SST); 1547 fprintf(stderr, " The block was made by call #%" PY_FORMAT_SIZE_T 1548 "u to debug malloc/realloc.\n", serial); 1549 1550 if (nbytes > 0) { 1551 i = 0; 1552 fputs(" Data at p:", stderr); 1553 /* print up to 8 bytes at the start */ 1554 while (q < tail && i < 8) { 1555 fprintf(stderr, " %02x", *q); 1556 ++i; 1557 ++q; 1558 } 1559 /* and up to 8 at the end */ 1560 if (q < tail) { 1561 if (tail - q > 8) { 1562 fputs(" ...", stderr); 1563 q = tail - 8; 1564 } 1565 while (q < tail) { 1566 fprintf(stderr, " %02x", *q); 1567 ++q; 1568 } 1569 } 1570 fputc('\n', stderr); 1571 } 1598 const uchar *q = (const uchar *)p; 1599 const uchar *tail; 1600 size_t nbytes, serial; 1601 int i; 1602 int ok; 1603 char id; 1604 1605 fprintf(stderr, "Debug memory block at address p=%p:", p); 1606 if (p == NULL) { 1607 fprintf(stderr, "\n"); 1608 return; 1609 } 1610 id = (char)q[-SST]; 1611 fprintf(stderr, " API '%c'\n", id); 1612 1613 nbytes = read_size_t(q - 2*SST); 1614 fprintf(stderr, " %" PY_FORMAT_SIZE_T "u bytes originally " 1615 "requested\n", nbytes); 1616 1617 /* In case this is nuts, check the leading pad bytes first. */ 1618 fprintf(stderr, " The %d pad bytes at p-%d are ", SST-1, SST-1); 1619 ok = 1; 1620 for (i = 1; i <= SST-1; ++i) { 1621 if (*(q-i) != FORBIDDENBYTE) { 1622 ok = 0; 1623 break; 1624 } 1625 } 1626 if (ok) 1627 fputs("FORBIDDENBYTE, as expected.\n", stderr); 1628 else { 1629 fprintf(stderr, "not all FORBIDDENBYTE (0x%02x):\n", 1630 FORBIDDENBYTE); 1631 for (i = SST-1; i >= 1; --i) { 1632 const uchar byte = *(q-i); 1633 fprintf(stderr, " at p-%d: 0x%02x", i, byte); 1634 if (byte != FORBIDDENBYTE) 1635 fputs(" *** OUCH", stderr); 1636 fputc('\n', stderr); 1637 } 1638 1639 fputs(" Because memory is corrupted at the start, the " 1640 "count of bytes requested\n" 1641 " may be bogus, and checking the trailing pad " 1642 "bytes may segfault.\n", stderr); 1643 } 1644 1645 tail = q + nbytes; 1646 fprintf(stderr, " The %d pad bytes at tail=%p are ", SST, tail); 1647 ok = 1; 1648 for (i = 0; i < SST; ++i) { 1649 if (tail[i] != FORBIDDENBYTE) { 1650 ok = 0; 1651 break; 1652 } 1653 } 1654 if (ok) 1655 fputs("FORBIDDENBYTE, as expected.\n", stderr); 1656 else { 1657 fprintf(stderr, "not all FORBIDDENBYTE (0x%02x):\n", 1658 FORBIDDENBYTE); 1659 for (i = 0; i < SST; ++i) { 1660 const uchar byte = tail[i]; 1661 fprintf(stderr, " at tail+%d: 0x%02x", 1662 i, byte); 1663 if (byte != FORBIDDENBYTE) 1664 fputs(" *** OUCH", stderr); 1665 fputc('\n', stderr); 1666 } 1667 } 1668 1669 serial = read_size_t(tail + SST); 1670 fprintf(stderr, " The block was made by call #%" PY_FORMAT_SIZE_T 1671 "u to debug malloc/realloc.\n", serial); 1672 1673 if (nbytes > 0) { 1674 i = 0; 1675 fputs(" Data at p:", stderr); 1676 /* print up to 8 bytes at the start */ 1677 while (q < tail && i < 8) { 1678 fprintf(stderr, " %02x", *q); 1679 ++i; 1680 ++q; 1681 } 1682 /* and up to 8 at the end */ 1683 if (q < tail) { 1684 if (tail - q > 8) { 1685 fputs(" ...", stderr); 1686 q = tail - 8; 1687 } 1688 while (q < tail) { 1689 fprintf(stderr, " %02x", *q); 1690 ++q; 1691 } 1692 } 1693 fputc('\n', stderr); 1694 } 1572 1695 } 1573 1696 … … 1575 1698 printone(const char* msg, size_t value) 1576 1699 { 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 uint digit = (uint)(value - nextvalue * 10);1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1700 int i, k; 1701 char buf[100]; 1702 size_t origvalue = value; 1703 1704 fputs(msg, stderr); 1705 for (i = (int)strlen(msg); i < 35; ++i) 1706 fputc(' ', stderr); 1707 fputc('=', stderr); 1708 1709 /* Write the value with commas. */ 1710 i = 22; 1711 buf[i--] = '\0'; 1712 buf[i--] = '\n'; 1713 k = 3; 1714 do { 1715 size_t nextvalue = value / 10; 1716 unsigned int digit = (unsigned int)(value - nextvalue * 10); 1717 value = nextvalue; 1718 buf[i--] = (char)(digit + '0'); 1719 --k; 1720 if (k == 0 && value && i >= 0) { 1721 k = 3; 1722 buf[i--] = ','; 1723 } 1724 } while (value && i >= 0); 1725 1726 while (i >= 0) 1727 buf[i--] = ' '; 1728 fputs(buf, stderr); 1729 1730 return origvalue; 1608 1731 } 1609 1732 … … 1615 1738 _PyObject_DebugMallocStats(void) 1616 1739 { 1617 uint i; 1618 const uint numclasses = SMALL_REQUEST_THRESHOLD >> ALIGNMENT_SHIFT; 1619 /* # of pools, allocated blocks, and free blocks per class index */ 1620 size_t numpools[SMALL_REQUEST_THRESHOLD >> ALIGNMENT_SHIFT]; 1621 size_t numblocks[SMALL_REQUEST_THRESHOLD >> ALIGNMENT_SHIFT]; 1622 size_t numfreeblocks[SMALL_REQUEST_THRESHOLD >> ALIGNMENT_SHIFT]; 1623 /* total # of allocated bytes in used and full pools */ 1624 size_t allocated_bytes = 0; 1625 /* total # of available bytes in used pools */ 1626 size_t available_bytes = 0; 1627 /* # of free pools + pools not yet carved out of current arena */ 1628 uint numfreepools = 0; 1629 /* # of bytes for arena alignment padding */ 1630 size_t arena_alignment = 0; 1631 /* # of bytes in used and full pools used for pool_headers */ 1632 size_t pool_header_bytes = 0; 1633 /* # of bytes in used and full pools wasted due to quantization, 1634 * i.e. the necessarily leftover space at the ends of used and 1635 * full pools. 1636 */ 1637 size_t quantization = 0; 1638 /* # of arenas actually allocated. */ 1639 size_t narenas = 0; 1640 /* running total -- should equal narenas * ARENA_SIZE */ 1641 size_t total; 1642 char buf[128]; 1643 1644 fprintf(stderr, "Small block threshold = %d, in %u size classes.\n", 1645 SMALL_REQUEST_THRESHOLD, numclasses); 1646 1647 for (i = 0; i < numclasses; ++i) 1648 numpools[i] = numblocks[i] = numfreeblocks[i] = 0; 1649 1650 /* Because full pools aren't linked to from anything, it's easiest 1651 * to march over all the arenas. If we're lucky, most of the memory 1652 * will be living in full pools -- would be a shame to miss them. 1653 */ 1654 for (i = 0; i < maxarenas; ++i) { 1655 uint poolsinarena; 1656 uint j; 1657 uptr base = arenas[i].address; 1658 1659 /* Skip arenas which are not allocated. */ 1660 if (arenas[i].address == (uptr)NULL) 1661 continue; 1662 narenas += 1; 1663 1664 poolsinarena = arenas[i].ntotalpools; 1665 numfreepools += arenas[i].nfreepools; 1666 1667 /* round up to pool alignment */ 1668 if (base & (uptr)POOL_SIZE_MASK) { 1669 arena_alignment += POOL_SIZE; 1670 base &= ~(uptr)POOL_SIZE_MASK; 1671 base += POOL_SIZE; 1672 } 1673 1674 /* visit every pool in the arena */ 1675 assert(base <= (uptr) arenas[i].pool_address); 1676 for (j = 0; 1677 base < (uptr) arenas[i].pool_address; 1678 ++j, base += POOL_SIZE) { 1679 poolp p = (poolp)base; 1680 const uint sz = p->szidx; 1681 uint freeblocks; 1682 1683 if (p->ref.count == 0) { 1684 /* currently unused */ 1685 assert(pool_is_in_list(p, arenas[i].freepools)); 1686 continue; 1687 } 1688 ++numpools[sz]; 1689 numblocks[sz] += p->ref.count; 1690 freeblocks = NUMBLOCKS(sz) - p->ref.count; 1691 numfreeblocks[sz] += freeblocks; 1740 uint i; 1741 const uint numclasses = SMALL_REQUEST_THRESHOLD >> ALIGNMENT_SHIFT; 1742 /* # of pools, allocated blocks, and free blocks per class index */ 1743 size_t numpools[SMALL_REQUEST_THRESHOLD >> ALIGNMENT_SHIFT]; 1744 size_t numblocks[SMALL_REQUEST_THRESHOLD >> ALIGNMENT_SHIFT]; 1745 size_t numfreeblocks[SMALL_REQUEST_THRESHOLD >> ALIGNMENT_SHIFT]; 1746 /* total # of allocated bytes in used and full pools */ 1747 size_t allocated_bytes = 0; 1748 /* total # of available bytes in used pools */ 1749 size_t available_bytes = 0; 1750 /* # of free pools + pools not yet carved out of current arena */ 1751 uint numfreepools = 0; 1752 /* # of bytes for arena alignment padding */ 1753 size_t arena_alignment = 0; 1754 /* # of bytes in used and full pools used for pool_headers */ 1755 size_t pool_header_bytes = 0; 1756 /* # of bytes in used and full pools wasted due to quantization, 1757 * i.e. the necessarily leftover space at the ends of used and 1758 * full pools. 1759 */ 1760 size_t quantization = 0; 1761 /* # of arenas actually allocated. */ 1762 size_t narenas = 0; 1763 /* running total -- should equal narenas * ARENA_SIZE */ 1764 size_t total; 1765 char buf[128]; 1766 1767 fprintf(stderr, "Small block threshold = %d, in %u size classes.\n", 1768 SMALL_REQUEST_THRESHOLD, numclasses); 1769 1770 for (i = 0; i < numclasses; ++i) 1771 numpools[i] = numblocks[i] = numfreeblocks[i] = 0; 1772 1773 /* Because full pools aren't linked to from anything, it's easiest 1774 * to march over all the arenas. If we're lucky, most of the memory 1775 * will be living in full pools -- would be a shame to miss them. 1776 */ 1777 for (i = 0; i < maxarenas; ++i) { 1778 uint j; 1779 uptr base = arenas[i].address; 1780 1781 /* Skip arenas which are not allocated. */ 1782 if (arenas[i].address == (uptr)NULL) 1783 continue; 1784 narenas += 1; 1785 1786 numfreepools += arenas[i].nfreepools; 1787 1788 /* round up to pool alignment */ 1789 if (base & (uptr)POOL_SIZE_MASK) { 1790 arena_alignment += POOL_SIZE; 1791 base &= ~(uptr)POOL_SIZE_MASK; 1792 base += POOL_SIZE; 1793 } 1794 1795 /* visit every pool in the arena */ 1796 assert(base <= (uptr) arenas[i].pool_address); 1797 for (j = 0; 1798 base < (uptr) arenas[i].pool_address; 1799 ++j, base += POOL_SIZE) { 1800 poolp p = (poolp)base; 1801 const uint sz = p->szidx; 1802 uint freeblocks; 1803 1804 if (p->ref.count == 0) { 1805 /* currently unused */ 1806 assert(pool_is_in_list(p, arenas[i].freepools)); 1807 continue; 1808 } 1809 ++numpools[sz]; 1810 numblocks[sz] += p->ref.count; 1811 freeblocks = NUMBLOCKS(sz) - p->ref.count; 1812 numfreeblocks[sz] += freeblocks; 1692 1813 #ifdef Py_DEBUG 1693 1694 1695 #endif 1696 1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711 1712 1713 1714 1715 1716 1717 1718 1719 1720 1721 1722 1723 1724 1725 1726 1727 1728 1729 1730 1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 } 1751 1752 #endif 1814 if (freeblocks > 0) 1815 assert(pool_is_in_list(p, usedpools[sz + sz])); 1816 #endif 1817 } 1818 } 1819 assert(narenas == narenas_currently_allocated); 1820 1821 fputc('\n', stderr); 1822 fputs("class size num pools blocks in use avail blocks\n" 1823 "----- ---- --------- ------------- ------------\n", 1824 stderr); 1825 1826 for (i = 0; i < numclasses; ++i) { 1827 size_t p = numpools[i]; 1828 size_t b = numblocks[i]; 1829 size_t f = numfreeblocks[i]; 1830 uint size = INDEX2SIZE(i); 1831 if (p == 0) { 1832 assert(b == 0 && f == 0); 1833 continue; 1834 } 1835 fprintf(stderr, "%5u %6u " 1836 "%11" PY_FORMAT_SIZE_T "u " 1837 "%15" PY_FORMAT_SIZE_T "u " 1838 "%13" PY_FORMAT_SIZE_T "u\n", 1839 i, size, p, b, f); 1840 allocated_bytes += b * size; 1841 available_bytes += f * size; 1842 pool_header_bytes += p * POOL_OVERHEAD; 1843 quantization += p * ((POOL_SIZE - POOL_OVERHEAD) % size); 1844 } 1845 fputc('\n', stderr); 1846 (void)printone("# times object malloc called", serialno); 1847 1848 (void)printone("# arenas allocated total", ntimes_arena_allocated); 1849 (void)printone("# arenas reclaimed", ntimes_arena_allocated - narenas); 1850 (void)printone("# arenas highwater mark", narenas_highwater); 1851 (void)printone("# arenas allocated current", narenas); 1852 1853 PyOS_snprintf(buf, sizeof(buf), 1854 "%" PY_FORMAT_SIZE_T "u arenas * %d bytes/arena", 1855 narenas, ARENA_SIZE); 1856 (void)printone(buf, narenas * ARENA_SIZE); 1857 1858 fputc('\n', stderr); 1859 1860 total = printone("# bytes in allocated blocks", allocated_bytes); 1861 total += printone("# bytes in available blocks", available_bytes); 1862 1863 PyOS_snprintf(buf, sizeof(buf), 1864 "%u unused pools * %d bytes", numfreepools, POOL_SIZE); 1865 total += printone(buf, (size_t)numfreepools * POOL_SIZE); 1866 1867 total += printone("# bytes lost to pool headers", pool_header_bytes); 1868 total += printone("# bytes lost to quantization", quantization); 1869 total += printone("# bytes lost to arena alignment", arena_alignment); 1870 (void)printone("Total", total); 1871 } 1872 1873 #endif /* PYMALLOC_DEBUG */ 1753 1874 1754 1875 #ifdef Py_USING_MEMORY_DEBUGGER … … 1759 1880 Py_ADDRESS_IN_RANGE(void *P, poolp pool) 1760 1881 { 1761 return pool->arenaindex < maxarenas && 1762 (uptr)P - arenas[pool->arenaindex].address < (uptr)ARENA_SIZE && 1763 arenas[pool->arenaindex].address != 0; 1764 } 1765 #endif 1882 uint arenaindex_temp = pool->arenaindex; 1883 1884 return arenaindex_temp < maxarenas && 1885 (uptr)P - arenas[arenaindex_temp].address < (uptr)ARENA_SIZE && 1886 arenas[arenaindex_temp].address != 0; 1887 } 1888 #endif
Note:
See TracChangeset
for help on using the changeset viewer.
