六、内存管理机制
1、内存管理架构
2、小块空间的内存池
3、循环引用的垃圾收集
4、python中的垃圾收集
1、内存管理架构
Python内存管理机制有两套实现，由编译符号PYMALLOC_DEBUG控制，当该符号被定义时，开启debug模式下的内存管理机制，这套机制在正常内存管理动作外还记录许多关于内存的信息，方便调试。
Python内存管理机制被抽象成分层设计：
[obmalloc.c]
Object-specific allocators
_____ ______ ______ ________
[ int ] [ dict ] [ list ] ... [ string ] Python core |
+3 | <----- Object-specific memory -----> | <-- Non-object memory --> |
_______________________________ | |
[ Python's object allocator ] | |
+2 | ####### Object memory ####### | <------ Internal buffers ------> |
______________________________________________________________ |
[ Python's raw memory allocator (PyMem_ API) ] |
+1 | <----- Python memory (under PyMem manager's control) ------> | |
__________________________________________________________________
[ Underlying general-purpose allocator (ex: C library malloc) ]
0 | <------ Virtual memory allocated for the python process -------> |
=========================================================================
_______________________________________________________________________
[ OS-specific Virtual Memory Manager (VMM) ]
-1 | <--- Kernel dynamic storage allocation & management (page-based) ---> |
__________________________________ __________________________________
[ ] [ ]
-2 | <-- Physical memory: ROM/RAM --> | | <-- Secondary storage (swap) --> |-1层、-2层是虚拟机或操作系统和物理硬盘等的级别，我们不管。
0层是操作系统提供的内存管理接口，python用的是C运行时提供的malloc接口和free接口，这一层由操作系统实现并管理，python无法干涉这一层的行为。上面三层则是由Python实现并维护。
1层时python基于0层的包装，为Python提供一层统一的 raw memory 管理接口：
[pymem.h] PyAPI_FUNC(void *) PyMem_Malloc(size_t);
PyAPI_FUNC(void *) PyMem_Realloc(void *, size_t);
PyAPI_FUNC(void) PyMem_Free(void *); [object.c] void *
PyMem_Malloc(size_t nbytes)
{
return PyMem_MALLOC(nbytes);
} void *
PyMem_Realloc(void *p, size_t nbytes)
{
return PyMem_REALLOC(p, nbytes);
} void
PyMem_Free(void *p)
{
PyMem_FREE(p);
}
对应宏实现：
[pymem.h] #define PyMem_MALLOC(n) ((size_t)(n) > (size_t)PY_SSIZE_T_MAX ? NULL \
: malloc((n) ? (n) : ))
#define PyMem_REALLOC(p, n) ((size_t)(n) > (size_t)PY_SSIZE_T_MAX ? NULL \
: realloc((p), (n) ? (n) : ))
#define PyMem_FREE free
使用宏可减少一次函数调用提高运行效率；另一方面，对于用户使用C编写python扩展模块来说，使用宏是危险的，python内存管理的宏可能会变，导致旧版与新版python产生二进制不兼容。故使用C编写Python扩展时，使用函数接口是好习惯。
1层还提供Python中类型的内存分配器：
[pymem.h] #define PyMem_New(type, n) \
( ((size_t)(n) > PY_SSIZE_T_MAX / sizeof(type)) ? NULL : \
( (type *) PyMem_Malloc((n) * sizeof(type)) ) )
#define PyMem_NEW(type, n) \
( ((size_t)(n) > PY_SSIZE_T_MAX / sizeof(type)) ? NULL : \
( (type *) PyMem_MALLOC((n) * sizeof(type)) ) ) #define PyMem_Resize(p, type, n) \
( (p) = ((size_t)(n) > PY_SSIZE_T_MAX / sizeof(type)) ? NULL : \
(type *) PyMem_Realloc((p), (n) * sizeof(type)) )
#define PyMem_RESIZE(p, type, n) \
( (p) = ((size_t)(n) > PY_SSIZE_T_MAX / sizeof(type)) ? NULL : \
(type *) PyMem_REALLOC((p), (n) * sizeof(type)) ) #define PyMem_Del PyMem_Free
#define PyMem_DEL PyMem_FREE
PyMem_Malloc需要提供所需申请空间的大小，而PyMem_New只需提供类型和数量。
1层提供的功能是有限的，故需要2层；2层提供创建Python对象的接口（Pymalloc机制），gc管理就在其中。
3层则是Python的一些常用对象，如整数对象，字符串对象等。
2、小块空间的内存池
对于Python中小块内存管理（不为创建对象而申请），Python2.5中启用内存池机制，通过PyObject_Malloc、PyObject_Realloc、PyObject_Free提供。小块内存内存池也可视为一个层次结构，下到上分为：block、pool、arena和内存池。
2.1、Block
最底层有一个确定大小的内存块block。不同的block有不同的内存大小（size class），并且是8字节对齐：
[obmalloc.c] #define ALIGNMENT 8 /* must be 2^N */
#define ALIGNMENT_SHIFT 3
#define ALIGNMENT_MASK (ALIGNMENT - 1)
block大小上限为256，申请内存超过时就使用PyMem函数族处理：
[obmalloc.h] #define SMALL_REQUEST_THRESHOLD 256
#define NB_SMALL_SIZE_CLASSES (SMALL_REQUEST_THRESHOLD / ALIGNMENT)
根据以上设定可得：
[obmalloc.c]
* Request in bytes Size of allocated block Size class idx
* ----------------------------------------------------------------
* 1-8 8 0
* 9-16 16 1
* 17-24 24 2
* 25-32 32 3
* 33-40 40 4
* 41-48 48 5
* 49-56 56 6
* 57-64 64 7
* 65-72 72 8
* ... ... ...
* 241-248 248 30
* 249-256 256 31
*
* 0, 257 and up: routed to the underlying allocator.
size class index 到 size class 的转换：
[obmalloc.c] /* Return the number of bytes in size class I, as a uint. */
#define INDEX2SIZE(I) (((uint)(I) + 1) << ALIGNMENT_SHIFT)
block只是一个概念，在Python源码中并无实体。而管理block的则是pool。
2.2、pool
pool管理着一堆固定大小的block块，是block的集合。pool的大小通常为系统内存页（4K）：
[obmalloc.c] #define SYSTEM_PAGE_SIZE (4 * 1024)
#define SYSTEM_PAGE_SIZE_MASK (SYSTEM_PAGE_SIZE - 1) #define POOL_SIZE SYSTEM_PAGE_SIZE /* must be 2^N */
#define POOL_SIZE_MASK SYSTEM_PAGE_SIZE_MASK
python中pool相关的结构：
[obmalloc.h] /* When you say memory, my mind reasons in terms of (pointers to) blocks */
typedef uchar block; /* Pool for small blocks. */
struct pool_header {
union { block *_padding;
uint count; } ref; /* number of allocated blocks */
block *freeblock; /* pool's free list head */
struct pool_header *nextpool; /* next pool of this size class */
struct pool_header *prevpool; /* previous pool "" */
uint arenaindex; /* index into arenas of base adr */
uint szidx; /* block size class index */
uint nextoffset; /* bytes to virgin block */
uint maxnextoffset; /* largest valid nextoffset */
};
这是一个pool的头部，4KB除去这头部剩下的就是pool管理的内存了。
一个pool管理着一堆同样大小的block，由szidx（size class index）决定。
将4KB内存改造成pool：
申请block：
if (pool != pool->nextpool) {
/*
* There is a used pool for this size class.
* Pick up the head block of its free list.
*/
++pool->ref.count;
bp = pool->freeblock;
assert(bp != NULL);
if ((pool->freeblock = *(block **)bp) != NULL) {
UNLOCK();
return (void *)bp;
}
/*
* Reached the end of the free list, try to extend it.
*/
if (pool->nextoffset <= pool->maxnextoffset) {
/* There is room for another block. */
pool->freeblock = (block*)pool +
pool->nextoffset;
pool->nextoffset += INDEX2SIZE(size);
*(block **)(pool->freeblock) = NULL;
UNLOCK();
return (void *)bp;
}
/* Pool is full, unlink from used pools. */
next = pool->nextpool;
pool = pool->prevpool;
next->prevpool = pool;
pool->nextpool = next;
UNLOCK();
return (void *)bp;
}
释放block：
void
PyObject_Free(void *p)
{
poolp pool;
block *lastfree;
poolp next, prev;
uint size;
#ifndef Py_USING_MEMORY_DEBUGGER
uint arenaindex_temp;
#endif if (p == NULL) /* free(NULL) has no effect */
return; #ifdef WITH_VALGRIND
if (UNLIKELY(running_on_valgrind > ))
goto redirect;
#endif pool = POOL_ADDR(p);
if (Py_ADDRESS_IN_RANGE(p, pool)) {
/* We allocated this address. */
LOCK();
/* Link p to the start of the pool's freeblock list. Since
* the pool had at least the p block outstanding, the pool
* wasn't empty (so it's already in a usedpools[] list, or
* was full and is in no list -- it's not in the freeblocks
* list in any case).
*/
assert(pool->ref.count > ); /* else it was empty */
*(block **)p = lastfree = pool->freeblock;
pool->freeblock = (block *)p;
if (lastfree) {
struct arena_object* ao;
uint nf; /* ao->nfreepools */ /* freeblock wasn't NULL, so the pool wasn't full,
* and the pool is in a usedpools[] list.
*/
if (--pool->ref.count != ) {
/* pool isn't empty: leave it in usedpools */
UNLOCK();
return;
}
/* Pool is now empty: unlink from usedpools, and
* link to the front of freepools. This ensures that
* previously freed pools will be allocated later
* (being not referenced, they are perhaps paged out).
*/
next = pool->nextpool;
prev = pool->prevpool;
next->prevpool = prev;
prev->nextpool = next; /* Link the pool to freepools. This is a singly-linked
* list, and pool->prevpool isn't used there.
*/
ao = &arenas[pool->arenaindex];
pool->nextpool = ao->freepools;
ao->freepools = pool;
nf = ++ao->nfreepools; /* All the rest is arena management. We just freed
* a pool, and there are 4 cases for arena mgmt:
* 1. If all the pools are free, return the arena to
* the system free().
* 2. If this is the only free pool in the arena,
* add the arena back to the `usable_arenas` list.
* 3. If the "next" arena has a smaller count of free
* pools, we have to "slide this arena right" to
* restore that usable_arenas is sorted in order of
* nfreepools.
* 4. Else there's nothing more to do.
*/
if (nf == ao->ntotalpools) {
/* Case 1. First unlink ao from usable_arenas.
*/
assert(ao->prevarena == NULL ||
ao->prevarena->address != );
assert(ao ->nextarena == NULL ||
ao->nextarena->address != ); /* Fix the pointer in the prevarena, or the
* usable_arenas pointer.
*/
if (ao->prevarena == NULL) {
usable_arenas = ao->nextarena;
assert(usable_arenas == NULL ||
usable_arenas->address != );
}
else {
assert(ao->prevarena->nextarena == ao);
ao->prevarena->nextarena =
ao->nextarena;
}
/* Fix the pointer in the nextarena. */
if (ao->nextarena != NULL) {
assert(ao->nextarena->prevarena == ao);
ao->nextarena->prevarena =
ao->prevarena;
}
/* Record that this arena_object slot is
* available to be reused.
*/
ao->nextarena = unused_arena_objects;
unused_arena_objects = ao; /* Free the entire arena. */
free((void *)ao->address);
ao->address = ; /* mark unassociated */
--narenas_currently_allocated; UNLOCK();
return;
}
if (nf == ) {
/* Case 2. Put ao at the head of
* usable_arenas. Note that because
* ao->nfreepools was 0 before, ao isn't
* currently on the usable_arenas list.
*/
ao->nextarena = usable_arenas;
ao->prevarena = NULL;
if (usable_arenas)
usable_arenas->prevarena = ao;
usable_arenas = ao;
assert(usable_arenas->address != ); UNLOCK();
return;
}
/* If this arena is now out of order, we need to keep
* the list sorted. The list is kept sorted so that
* the "most full" arenas are used first, which allows
* the nearly empty arenas to be completely freed. In
* a few un-scientific tests, it seems like this
* approach allowed a lot more memory to be freed.
*/
if (ao->nextarena == NULL ||
nf <= ao->nextarena->nfreepools) {
/* Case 4. Nothing to do. */
UNLOCK();
return;
}
/* Case 3: We have to move the arena towards the end
* of the list, because it has more free pools than
* the arena to its right.
* First unlink ao from usable_arenas.
*/
if (ao->prevarena != NULL) {
/* ao isn't at the head of the list */
assert(ao->prevarena->nextarena == ao);
ao->prevarena->nextarena = ao->nextarena;
}
else {
/* ao is at the head of the list */
assert(usable_arenas == ao);
usable_arenas = ao->nextarena;
}
ao->nextarena->prevarena = ao->prevarena; /* Locate the new insertion point by iterating over
* the list, using our nextarena pointer.
*/
while (ao->nextarena != NULL &&
nf > ao->nextarena->nfreepools) {
ao->prevarena = ao->nextarena;
ao->nextarena = ao->nextarena->nextarena;
} /* Insert ao at this point. */
assert(ao->nextarena == NULL ||
ao->prevarena == ao->nextarena->prevarena);
assert(ao->prevarena->nextarena == ao->nextarena); ao->prevarena->nextarena = ao;
if (ao->nextarena != NULL)
ao->nextarena->prevarena = ao; /* Verify that the swaps worked. */
assert(ao->nextarena == NULL ||
nf <= ao->nextarena->nfreepools);
assert(ao->prevarena == NULL ||
nf > ao->prevarena->nfreepools);
assert(ao->nextarena == NULL ||
ao->nextarena->prevarena == ao);
assert((usable_arenas == ao &&
ao->prevarena == NULL) ||
ao->prevarena->nextarena == ao); UNLOCK();
return;
}
/* Pool was full, so doesn't currently live in any list:
* link it to the front of the appropriate usedpools[] list.
* This mimics LRU pool usage for new allocations and
* targets optimal filling when several pools contain
* blocks of the same size class.
*/
--pool->ref.count;
assert(pool->ref.count > ); /* else the pool is empty */
size = pool->szidx;
next = usedpools[size + size];
prev = next->prevpool;
/* insert pool before next: prev <-> pool <-> next */
pool->nextpool = next;
pool->prevpool = prev;
next->prevpool = pool;
prev->nextpool = pool;
UNLOCK();
return;
} #ifdef WITH_VALGRIND
redirect:
#endif
/* We didn't allocate this address. */
free(p);
}
释放后freeblock会调整指到释放了的blobk上，有效利用空闲block。
block分配的一般行为：
[obmalloc.c]-[allocate block]
...
if (pool != pool->nextpool) {
/*
* There is a used pool for this size class.
* Pick up the head block of its free list.
*/
++pool->ref.count;
bp = pool->freeblock;
assert(bp != NULL);
if ((pool->freeblock = *(block **)bp) != NULL) {
UNLOCK();
return (void *)bp;
}
...
if (pool->nextoffset <= pool->maxnextoffset) {
...
}
...
}
freeblock为空证明pool满了，会提供另一个pool。而pool的集合则是arena。
2.3、arena
arena是多个pool的聚合。Pyhton中arena的默认大小为256KB（可装64个pool）：
[obmalloc.c]
#define ARENA_SIZE (256 << 10) /* 256KB */
Python中的arena：
[obmalloc.c] typedef uchar block; /* Record keeping for arenas. */
struct arena_object {
/* The address of the arena, as returned by malloc. Note that 0
* will never be returned by a successful malloc, and is used
* here to mark an arena_object that doesn't correspond to an
* allocated arena.
*/
uptr address; /* Pool-aligned pointer to the next pool to be carved off. */
block* pool_address; /* The number of available pools in the arena: free pools + never-
* allocated pools.
*/
uint nfreepools; /* The total number of pools in the arena, whether or not available. */
uint ntotalpools; /* Singly-linked list of available pools. */
struct pool_header* freepools; /* Whenever this arena_object is not associated with an allocated
* arena, the nextarena member is used to link all unassociated
* arena_objects in the singly-linked `unused_arena_objects` list.
* The prevarena member is unused in this case.
*
* When this arena_object is associated with an allocated arena
* with at least one available pool, both members are used in the
* doubly-linked `usable_arenas` list, which is maintained in
* increasing order of `nfreepools` values.
*
* Else this arena_object is associated with an allocated arena
* all of whose pools are in use. `nextarena` and `prevarena`
* are both meaningless in this case.
*/
struct arena_object* nextarena;
struct arena_object* prevarena;
};
一个完整的arena是 一个arena_object和其管理的pool集合；
一个完整的pool时一个 pool_header 和其管理的block集合。
pool_header和其管理的block内存上是连续的，而arena则是分离：
差别体现在申请pool_header时其所管理的内存被申请了，而arena_object则没有。
当一个arena_object没与pool集合建立联系时，arena处于“未使用”状态，否则进入“可用”状态。未使用的单向连接（unused_arena_objects），可用的双向连接（usable_arenas）。
arena的申请new_arena：
[obmalloc.c] /* Array of objects used to track chunks of memory (arenas). */
static struct arena_object* arenas = NULL;
/* Number of slots currently allocated in the `arenas` vector. */
static uint maxarenas = ; /* The head of the singly-linked, NULL-terminated list of available
* arena_objects.
*/
static struct arena_object* unused_arena_objects = NULL; /* The head of the doubly-linked, NULL-terminated at each end, list of
* arena_objects associated with arenas that have pools available.
*/
static struct arena_object* usable_arenas = NULL; /* How many arena_objects do we initially allocate?
* 16 = can allocate 16 arenas = 16 * ARENA_SIZE = 4MB before growing the
* `arenas` vector.
*/
#define INITIAL_ARENA_OBJECTS 16 /* Number of arenas allocated that haven't been free()'d. */
static size_t narenas_currently_allocated = ; #ifdef PYMALLOC_DEBUG
/* Total number of times malloc() called to allocate an arena. */
static size_t ntimes_arena_allocated = ;
/* High water mark (max value ever seen) for narenas_currently_allocated. */
static size_t narenas_highwater = ;
#endif /* Allocate a new arena. If we run out of memory, return NULL. Else
* allocate a new arena, and return the address of an arena_object
* describing the new arena. It's expected that the caller will set
* `usable_arenas` to the return value.
*/
static struct arena_object*
new_arena(void)
{
struct arena_object* arenaobj;
uint excess; /* number of bytes above pool alignment */ #ifdef PYMALLOC_DEBUG
if (Py_GETENV("PYTHONMALLOCSTATS"))
_PyObject_DebugMallocStats();
#endif
if (unused_arena_objects == NULL) {
uint i;
uint numarenas;
size_t nbytes; /* Double the number of arena objects on each allocation.
* Note that it's possible for `numarenas` to overflow.
*/
numarenas = maxarenas ? maxarenas << : INITIAL_ARENA_OBJECTS;
if (numarenas <= maxarenas)
return NULL; /* overflow */
#if SIZEOF_SIZE_T <= SIZEOF_INT
if (numarenas > PY_SIZE_MAX / sizeof(*arenas))
return NULL; /* overflow */
#endif
nbytes = numarenas * sizeof(*arenas);
arenaobj = (struct arena_object *)realloc(arenas, nbytes);
if (arenaobj == NULL)
return NULL;
arenas = arenaobj; /* We might need to fix pointers that were copied. However,
* new_arena only gets called when all the pages in the
* previous arenas are full. Thus, there are *no* pointers
* into the old array. Thus, we don't have to worry about
* invalid pointers. Just to be sure, some asserts:
*/
assert(usable_arenas == NULL);
assert(unused_arena_objects == NULL); /* Put the new arenas on the unused_arena_objects list. */
for (i = maxarenas; i < numarenas; ++i) {
arenas[i].address = ; /* mark as unassociated */
arenas[i].nextarena = i < numarenas - ?
&arenas[i+] : NULL;
} /* Update globals. */
unused_arena_objects = &arenas[maxarenas];
maxarenas = numarenas;
} /* Take the next available arena object off the head of the list. */
assert(unused_arena_objects != NULL);
arenaobj = unused_arena_objects;
unused_arena_objects = arenaobj->nextarena;
assert(arenaobj->address == );
arenaobj->address = (uptr)malloc(ARENA_SIZE);
if (arenaobj->address == ) {
/* The allocation failed: return NULL after putting the
* arenaobj back.
*/
arenaobj->nextarena = unused_arena_objects;
unused_arena_objects = arenaobj;
return NULL;
} ++narenas_currently_allocated;
#ifdef PYMALLOC_DEBUG
++ntimes_arena_allocated;
if (narenas_currently_allocated > narenas_highwater)
narenas_highwater = narenas_currently_allocated;
#endif
arenaobj->freepools = NULL;
/* pool_address <- first pool-aligned address in the arena
nfreepools <- number of whole pools that fit after alignment */
arenaobj->pool_address = (block*)arenaobj->address;
arenaobj->nfreepools = ARENA_SIZE / POOL_SIZE;
assert(POOL_SIZE * arenaobj->nfreepools == ARENA_SIZE);
excess = (uint)(arenaobj->address & POOL_SIZE_MASK);
if (excess != ) {
--arenaobj->nfreepools;
arenaobj->pool_address += POOL_SIZE - excess;
}
arenaobj->ntotalpools = arenaobj->nfreepools; return arenaobj;
}
先检查unused_arena_objects中是否有“未使用”的arena，有则从中取；否则新增arenas（并调整maxarenas的值）；
先申请ARENA_SIZE（256KB）的内存块，将其变成“可用”，然后设置一些维护pool的信息，后被usable_arenas接收；
address标记arena_object状态（“未使用”还是“可用”）。
2.4、内存池
小块内存池大小限制由SMALL_MEMORY_LIMIT控制，默认不限制：
/*
* Maximum amount of memory managed by the allocator for small requests.
*/
#ifdef WITH_MEMORY_LIMITS
#ifndef SMALL_MEMORY_LIMIT
#define SMALL_MEMORY_LIMIT (64 * 1024 * 1024) /* 64 MB -- more? */
#endif
#endif /*
* The allocator sub-allocates <Big> blocks of memory (called arenas) aligned
* on a page boundary. This is a reserved virtual address space for the
* current process (obtained through a malloc call). In no way this means
* that the memory arenas will be used entirely. A malloc(<Big>) is usually
* an address range reservation for <Big> bytes, unless all pages within this
* space are referenced subsequently. So malloc'ing big blocks and not using
* them does not mean "wasting memory". It's an addressable range wastage...
*
* Therefore, allocating arenas with malloc is not optimal, because there is
* some address space wastage, but this is the most portable way to request
* memory from the system across various platforms.
*/
#define ARENA_SIZE (256 << 10) /* 256KB */ #ifdef WITH_MEMORY_LIMITS
#define MAX_ARENAS (SMALL_MEMORY_LIMIT / ARENA_SIZE)
#endif
虽然arena是Python小块内存池的最上层结构，但申请内存时不与它打交道，而是直接以pool作为基本操作单元。同一个arena里面可能管理着 管理不同大小block的pool。
pool在python运行时处于used状态、full状态或empty状态中的一种。arena包含三种状态pool的集合的一个可能状态：
看下维护used状态pool的usedpools：
[obmalloc.c]
typedef uchar block; #define PTA(x) ((poolp )((uchar *)&(usedpools[2*(x)]) - 2*sizeof(block *)))
#define PT(x) PTA(x), PTA(x) static poolp usedpools[ * ((NB_SMALL_SIZE_CLASSES + ) / ) * ] = {
PT(), PT(), PT(), PT(), PT(), PT(), PT(), PT()
#if NB_SMALL_SIZE_CLASSES > 8
, PT(), PT(), PT(), PT(), PT(), PT(), PT(), PT()
#if NB_SMALL_SIZE_CLASSES > 16
, PT(), PT(), PT(), PT(), PT(), PT(), PT(), PT()
#if NB_SMALL_SIZE_CLASSES > 24
, PT(), PT(), PT(), PT(), PT(), PT(), PT(), PT()
#if NB_SMALL_SIZE_CLASSES > 32
, PT(), PT(), PT(), PT(), PT(), PT(), PT(), PT()
#if NB_SMALL_SIZE_CLASSES > 40
, PT(), PT(), PT(), PT(), PT(), PT(), PT(), PT()
#if NB_SMALL_SIZE_CLASSES > 48
, PT(), PT(), PT(), PT(), PT(), PT(), PT(), PT()
#if NB_SMALL_SIZE_CLASSES > 56
, PT(), PT(), PT(), PT(), PT(), PT(), PT(), PT()
#endif /* NB_SMALL_SIZE_CLASSES > 56 */
#endif /* NB_SMALL_SIZE_CLASSES > 48 */
#endif /* NB_SMALL_SIZE_CLASSES > 40 */
#endif /* NB_SMALL_SIZE_CLASSES > 32 */
#endif /* NB_SMALL_SIZE_CLASSES > 24 */
#endif /* NB_SMALL_SIZE_CLASSES > 16 */
#endif /* NB_SMALL_SIZE_CLASSES > 8 */
};
其中 NB_SMALL_SIZE_CLASSES 指明一共有多少个size class：
[obmalloc.c] #define SMALL_REQUEST_THRESHOLD 256
#define NB_SMALL_SIZE_CLASSES (SMALL_REQUEST_THRESHOLD / ALIGNMENT)
Python启动后usedpools中无可用pool。Python采用延迟分配策略，当我们申请小块内存时才分配。
初始分配空间代码PyObject_Malloc：
#undef PyObject_Malloc
void *
PyObject_Malloc(size_t nbytes)
{
block *bp;
poolp pool;
poolp next;
uint size; #ifdef WITH_VALGRIND
if (UNLIKELY(running_on_valgrind == -))
running_on_valgrind = RUNNING_ON_VALGRIND;
if (UNLIKELY(running_on_valgrind))
goto redirect;
#endif /*
* Limit ourselves to PY_SSIZE_T_MAX bytes to prevent security holes.
* Most python internals blindly use a signed Py_ssize_t to track
* things without checking for overflows or negatives.
* As size_t is unsigned, checking for nbytes < 0 is not required.
*/
if (nbytes > PY_SSIZE_T_MAX)
return NULL; /*
* This implicitly redirects malloc(0).
*/
if ((nbytes - ) < SMALL_REQUEST_THRESHOLD) {
LOCK();
/*
* Most frequent paths first
*/
size = (uint)(nbytes - ) >> ALIGNMENT_SHIFT;
pool = usedpools[size + size];
if (pool != pool->nextpool) {
/*
* There is a used pool for this size class.
* Pick up the head block of its free list.
*/
++pool->ref.count;
bp = pool->freeblock;
assert(bp != NULL);
if ((pool->freeblock = *(block **)bp) != NULL) {
UNLOCK();
return (void *)bp;
}
/*
* Reached the end of the free list, try to extend it.
*/
if (pool->nextoffset <= pool->maxnextoffset) {
/* There is room for another block. */
pool->freeblock = (block*)pool +
pool->nextoffset;
pool->nextoffset += INDEX2SIZE(size);
*(block **)(pool->freeblock) = NULL;
UNLOCK();
return (void *)bp;
}
/* Pool is full, unlink from used pools. */
next = pool->nextpool;
pool = pool->prevpool;
next->prevpool = pool;
pool->nextpool = next;
UNLOCK();
return (void *)bp;
} /* There isn't a pool of the right size class immediately
* available: use a free pool.
*/
if (usable_arenas == NULL) {
/* No arena has a free pool: allocate a new arena. */
#ifdef WITH_MEMORY_LIMITS
if (narenas_currently_allocated >= MAX_ARENAS) {
UNLOCK();
goto redirect;
}
#endif
usable_arenas = new_arena();
if (usable_arenas == NULL) {
UNLOCK();
goto redirect;
}
usable_arenas->nextarena =
usable_arenas->prevarena = NULL;
}
assert(usable_arenas->address != ); /* Try to get a cached free pool. */
pool = usable_arenas->freepools;
if (pool != NULL) {
/* Unlink from cached pools. */
usable_arenas->freepools = pool->nextpool; /* This arena already had the smallest nfreepools
* value, so decreasing nfreepools doesn't change
* that, and we don't need to rearrange the
* usable_arenas list. However, if the arena has
* become wholly allocated, we need to remove its
* arena_object from usable_arenas.
*/
--usable_arenas->nfreepools;
if (usable_arenas->nfreepools == ) {
/* Wholly allocated: remove. */
assert(usable_arenas->freepools == NULL);
assert(usable_arenas->nextarena == NULL ||
usable_arenas->nextarena->prevarena ==
usable_arenas); usable_arenas = usable_arenas->nextarena;
if (usable_arenas != NULL) {
usable_arenas->prevarena = NULL;
assert(usable_arenas->address != );
}
}
else {
/* nfreepools > 0: it must be that freepools
* isn't NULL, or that we haven't yet carved
* off all the arena's pools for the first
* time.
*/
assert(usable_arenas->freepools != NULL ||
usable_arenas->pool_address <=
(block*)usable_arenas->address +
ARENA_SIZE - POOL_SIZE);
}
init_pool:
/* Frontlink to used pools. */
next = usedpools[size + size]; /* == prev */
pool->nextpool = next;
pool->prevpool = next;
next->nextpool = pool;
next->prevpool = pool;
pool->ref.count = ;
if (pool->szidx == size) {
/* Luckily, this pool last contained blocks
* of the same size class, so its header
* and free list are already initialized.
*/
bp = pool->freeblock;
pool->freeblock = *(block **)bp;
UNLOCK();
return (void *)bp;
}
/*
* Initialize the pool header, set up the free list to
* contain just the second block, and return the first
* block.
*/
pool->szidx = size;
size = INDEX2SIZE(size);
bp = (block *)pool + POOL_OVERHEAD;
pool->nextoffset = POOL_OVERHEAD + (size << );
pool->maxnextoffset = POOL_SIZE - size;
pool->freeblock = bp + size;
*(block **)(pool->freeblock) = NULL;
UNLOCK();
return (void *)bp;
} /* Carve off a new pool. */
assert(usable_arenas->nfreepools > );
assert(usable_arenas->freepools == NULL);
pool = (poolp)usable_arenas->pool_address;
assert((block*)pool <= (block*)usable_arenas->address +
ARENA_SIZE - POOL_SIZE);
pool->arenaindex = usable_arenas - arenas;
assert(&arenas[pool->arenaindex] == usable_arenas);
pool->szidx = DUMMY_SIZE_IDX;
usable_arenas->pool_address += POOL_SIZE;
--usable_arenas->nfreepools; if (usable_arenas->nfreepools == ) {
assert(usable_arenas->nextarena == NULL ||
usable_arenas->nextarena->prevarena ==
usable_arenas);
/* Unlink the arena: it is completely allocated. */
usable_arenas = usable_arenas->nextarena;
if (usable_arenas != NULL) {
usable_arenas->prevarena = NULL;
assert(usable_arenas->address != );
}
} goto init_pool;
} /* The small block allocator ends here. */ redirect:
/* Redirect the original request to the underlying (libc) allocator.
* We jump here on bigger requests, on error in the code above (as a
* last chance to serve the request) or when the max memory limit
* has been reached.
*/
if (nbytes == )
nbytes = ;
return (void *)malloc(nbytes);
}
开始如果usable_arenas为空，则从new_arena申请一个arena，再构建usable_arenas链表，从usable_arenas取一个可用pool。取完后如arena无可用pool，将其移出usable_arenas。
取到pool后将其放到usedpools中，然后对pool进行初始化，返回相应block。
python2.5后，将arena内存泄漏问题修复（arena申请pool但从不释放），回收代码PyObject_Free：
#undef PyObject_Free
void
PyObject_Free(void *p)
{
poolp pool;
block *lastfree;
poolp next, prev;
uint size;
#ifndef Py_USING_MEMORY_DEBUGGER
uint arenaindex_temp;
#endif if (p == NULL) /* free(NULL) has no effect */
return; #ifdef WITH_VALGRIND
if (UNLIKELY(running_on_valgrind > ))
goto redirect;
#endif pool = POOL_ADDR(p);
if (Py_ADDRESS_IN_RANGE(p, pool)) {
/* We allocated this address. */
LOCK();
/* Link p to the start of the pool's freeblock list. Since
* the pool had at least the p block outstanding, the pool
* wasn't empty (so it's already in a usedpools[] list, or
* was full and is in no list -- it's not in the freeblocks
* list in any case).
*/
assert(pool->ref.count > ); /* else it was empty */
*(block **)p = lastfree = pool->freeblock;
pool->freeblock = (block *)p;
if (lastfree) {
struct arena_object* ao;
uint nf; /* ao->nfreepools */ /* freeblock wasn't NULL, so the pool wasn't full,
* and the pool is in a usedpools[] list.
*/
if (--pool->ref.count != ) {
/* pool isn't empty: leave it in usedpools */
UNLOCK();
return;
}
/* Pool is now empty: unlink from usedpools, and
* link to the front of freepools. This ensures that
* previously freed pools will be allocated later
* (being not referenced, they are perhaps paged out).
*/
next = pool->nextpool;
prev = pool->prevpool;
next->prevpool = prev;
prev->nextpool = next; /* Link the pool to freepools. This is a singly-linked
* list, and pool->prevpool isn't used there.
*/
ao = &arenas[pool->arenaindex];
pool->nextpool = ao->freepools;
ao->freepools = pool;
nf = ++ao->nfreepools; /* All the rest is arena management. We just freed
* a pool, and there are 4 cases for arena mgmt:
* 1. If all the pools are free, return the arena to
* the system free().
* 2. If this is the only free pool in the arena,
* add the arena back to the `usable_arenas` list.
* 3. If the "next" arena has a smaller count of free
* pools, we have to "slide this arena right" to
* restore that usable_arenas is sorted in order of
* nfreepools.
* 4. Else there's nothing more to do.
*/
if (nf == ao->ntotalpools) {
/* Case 1. First unlink ao from usable_arenas.
*/
assert(ao->prevarena == NULL ||
ao->prevarena->address != );
assert(ao ->nextarena == NULL ||
ao->nextarena->address != ); /* Fix the pointer in the prevarena, or the
* usable_arenas pointer.
*/
if (ao->prevarena == NULL) {
usable_arenas = ao->nextarena;
assert(usable_arenas == NULL ||
usable_arenas->address != );
}
else {
assert(ao->prevarena->nextarena == ao);
ao->prevarena->nextarena =
ao->nextarena;
}
/* Fix the pointer in the nextarena. */
if (ao->nextarena != NULL) {
assert(ao->nextarena->prevarena == ao);
ao->nextarena->prevarena =
ao->prevarena;
}
/* Record that this arena_object slot is
* available to be reused.
*/
ao->nextarena = unused_arena_objects;
unused_arena_objects = ao; /* Free the entire arena. */
free((void *)ao->address);
ao->address = ; /* mark unassociated */
--narenas_currently_allocated; UNLOCK();
return;
}
if (nf == ) {
/* Case 2. Put ao at the head of
* usable_arenas. Note that because
* ao->nfreepools was 0 before, ao isn't
* currently on the usable_arenas list.
*/
ao->nextarena = usable_arenas;
ao->prevarena = NULL;
if (usable_arenas)
usable_arenas->prevarena = ao;
usable_arenas = ao;
assert(usable_arenas->address != ); UNLOCK();
return;
}
/* If this arena is now out of order, we need to keep
* the list sorted. The list is kept sorted so that
* the "most full" arenas are used first, which allows
* the nearly empty arenas to be completely freed. In
* a few un-scientific tests, it seems like this
* approach allowed a lot more memory to be freed.
*/
if (ao->nextarena == NULL ||
nf <= ao->nextarena->nfreepools) {
/* Case 4. Nothing to do. */
UNLOCK();
return;
}
/* Case 3: We have to move the arena towards the end
* of the list, because it has more free pools than
* the arena to its right.
* First unlink ao from usable_arenas.
*/
if (ao->prevarena != NULL) {
/* ao isn't at the head of the list */
assert(ao->prevarena->nextarena == ao);
ao->prevarena->nextarena = ao->nextarena;
}
else {
/* ao is at the head of the list */
assert(usable_arenas == ao);
usable_arenas = ao->nextarena;
}
ao->nextarena->prevarena = ao->prevarena; /* Locate the new insertion point by iterating over
* the list, using our nextarena pointer.
*/
while (ao->nextarena != NULL &&
nf > ao->nextarena->nfreepools) {
ao->prevarena = ao->nextarena;
ao->nextarena = ao->nextarena->nextarena;
} /* Insert ao at this point. */
assert(ao->nextarena == NULL ||
ao->prevarena == ao->nextarena->prevarena);
assert(ao->prevarena->nextarena == ao->nextarena); ao->prevarena->nextarena = ao;
if (ao->nextarena != NULL)
ao->nextarena->prevarena = ao; /* Verify that the swaps worked. */
assert(ao->nextarena == NULL ||
nf <= ao->nextarena->nfreepools);
assert(ao->prevarena == NULL ||
nf > ao->prevarena->nfreepools);
assert(ao->nextarena == NULL ||
ao->nextarena->prevarena == ao);
assert((usable_arenas == ao &&
ao->prevarena == NULL) ||
ao->prevarena->nextarena == ao); UNLOCK();
return;
}
/* Pool was full, so doesn't currently live in any list:
* link it to the front of the appropriate usedpools[] list.
* This mimics LRU pool usage for new allocations and
* targets optimal filling when several pools contain
* blocks of the same size class.
*/
--pool->ref.count;
assert(pool->ref.count > ); /* else the pool is empty */
size = pool->szidx;
next = usedpools[size + size];
prev = next->prevpool;
/* insert pool before next: prev <-> pool <-> next */
pool->nextpool = next;
pool->prevpool = prev;
next->prevpool = pool;
prev->nextpool = pool;
UNLOCK();
return;
} #ifdef WITH_VALGRIND
redirect:
#endif
/* We didn't allocate this address. */
free(p);
}
1、如果arena中所有pool都是empty，释放pool集合所占内存；
2、如果之前arena没有empty的pool，多一个后将arena移到usable_arenas中；
3、usable_arenas时一个有序链表，nfreepools个数递增，保证一个arena empty pool个数越多被使用机会越少。从而保证多余内存被释放并归还系统；
4、其他情况不对arena进行处理；
3、循环引用的垃圾收集
python通过引用计数实时内存管理，优点是具有实时性，缺点是带来维护引用计数额外操作、更多的内存分配与释放。python设计了大量内存池，除了第2节提到的小块内存的内存池，对其他python对象也有内存池机制，以此弥补引用计数软肋。
引用计数还有一致命弱点----循环引用，python引入标记-清除以及分代回收填补此漏洞。
垃圾回收分两阶段：垃圾检测和垃圾回收。
python垃圾收集的过程：
4、python中的垃圾收集
4.1、可收集对象链表
python中循环引用发生在container对象间，用PyGC_Head变成可收集对象（进入可收集对象链表）：
[objimpl.h] /* GC information is stored BEFORE the object structure. */
typedef union _gc_head {
struct {
union _gc_head *gc_next;
union _gc_head *gc_prev;
Py_ssize_t gc_refs;
} gc;
long double dummy; /* force worst-case alignment */
} PyGC_Head;
container创建过程：
[gcmodule.c] PyObject *
_PyObject_GC_New(PyTypeObject *tp)
{
PyObject *op = _PyObject_GC_Malloc(_PyObject_SIZE(tp));
if (op != NULL)
op = PyObject_INIT(op, tp);
return op;
}
PyObject *
_PyObject_GC_Malloc(size_t basicsize)
{
PyObject *op;
PyGC_Head *g;
if (basicsize > PY_SSIZE_T_MAX - sizeof(PyGC_Head))
return PyErr_NoMemory();
g = (PyGC_Head *)PyObject_MALLOC(
sizeof(PyGC_Head) + basicsize);
if (g == NULL)
return PyErr_NoMemory();
g->gc.gc_refs = GC_UNTRACKED;
generations[].count++; /* number of allocated GC objects */
if (generations[].count > generations[].threshold &&
enabled &&
generations[].threshold &&
!collecting &&
!PyErr_Occurred()) {
collecting = ;
collect_generations();
collecting = ;
}
op = FROM_GC(g);
return op;
}
创建后第一部分是用于垃圾收集的PyGC_Head，接着是python所有对象都有的PyObject_HEAD，最后是属于container对象自身的数据。
PyGC_Head和PyObject_HEAD地址转换：
[gcmodule.c] /* Get an object's GC head */
#define AS_GC(o) ((PyGC_Head *)(o)-1) /* Get the object given the GC head */
#define FROM_GC(g) ((PyObject *)(((PyGC_Head *)g)+1)) [objimpl.h] #define _Py_AS_GC(o) ((PyGC_Head *)(o)-1)
在创建某个container对象最后一步会链接到可收集对象链表中：
[objimpl.h] /* Tell the GC to track this object. NB: While the object is tracked the
* collector it must be safe to call the ob_traverse method. */
#define _PyObject_GC_TRACK(o) do { \
PyGC_Head *g = _Py_AS_GC(o); \
if (g->gc.gc_refs != _PyGC_REFS_UNTRACKED) \
Py_FatalError("GC object already tracked"); \
g->gc.gc_refs = _PyGC_REFS_REACHABLE; \
g->gc.gc_next = _PyGC_generation0; \
g->gc.gc_prev = _PyGC_generation0->gc.gc_prev; \
g->gc.gc_prev->gc.gc_next = g; \
_PyGC_generation0->gc.gc_prev = g; \
} while ();
从链表摘除container对象：
[objimpl.h] /* Tell the GC to stop tracking this object.
* gc_next doesn't need to be set to NULL, but doing so is a good
* way to provoke memory errors if calling code is confused.
*/
#define _PyObject_GC_UNTRACK(o) do { \
PyGC_Head *g = _Py_AS_GC(o); \
assert(g->gc.gc_refs != _PyGC_REFS_UNTRACKED); \
g->gc.gc_refs = _PyGC_REFS_UNTRACKED; \
g->gc.gc_prev->gc.gc_next = g->gc.gc_next; \
g->gc.gc_next->gc.gc_prev = g->gc.gc_prev; \
g->gc.gc_next = NULL; \
} while ();
4.2、分代的垃圾收集
python中引入分代的垃圾收集机制，共有3代，每一代都是一个链表，在之前的链表基础上加上一个表头：
[gcmodule.c]
struct gc_generation {
PyGC_Head head;
int threshold; /* collection threshold */
int count; /* count of allocations or collections of younger
generations */
};
python中维护 了三个gc_generation结构的数组，通过这数组控制三条可收集对象链表，即三个“代”：
[gcmodule.c] #define NUM_GENERATIONS 3
#define GEN_HEAD(n) (&generations[n].head) /* linked lists of container objects */
static struct gc_generation generations[NUM_GENERATIONS] = {
/* PyGC_Head, threshold, count */
{{{GEN_HEAD(), GEN_HEAD(), }}, , },
{{{GEN_HEAD(), GEN_HEAD(), }}, , },
{{{GEN_HEAD(), GEN_HEAD(), }}, , },
}; PyGC_Head *_PyGC_generation0 = GEN_HEAD();
count表示有多少个可收集对象，threshold表示该链可容纳收集对象个数，当超过这个值时会触发垃圾回收机制：
[gcmodule.c] static Py_ssize_t
collect_generations(void)
{
int i;
Py_ssize_t n = ; /* Find the oldest generation (highest numbered) where the count
* exceeds the threshold. Objects in the that generation and
* generations younger than it will be collected. */
for (i = NUM_GENERATIONS-; i >= ; i--) {
if (generations[i].count > generations[i].threshold) {
/* Avoid quadratic performance degradation in number
of tracked objects. See comments at the beginning
of this file, and issue #4074.
*/
if (i == NUM_GENERATIONS -
&& long_lived_pending < long_lived_total / )
continue;
n = collect(i);
break;
}
}
return n;
}
4.3、Python中的标记——清除方法
开始垃圾收集前，会将收集的代及更年轻的代合并，再进行收集：
[gcmodule.c] static void
gc_list_init(PyGC_Head *list)
{
list->gc.gc_prev = list;
list->gc.gc_next = list;
} /* append list `from` onto list `to`; `from` becomes an empty list */
static void
gc_list_merge(PyGC_Head *from, PyGC_Head *to)
{
PyGC_Head *tail;
assert(from != to);
if (!gc_list_is_empty(from)) {
tail = to->gc.gc_prev;
tail->gc.gc_next = from->gc.gc_next;
tail->gc.gc_next->gc.gc_prev = tail;
to->gc.gc_prev = from->gc.gc_prev;
to->gc.gc_prev->gc.gc_next = to;
}
gc_list_init(from);
}
为了得出真正的引用计数，引入有效引入计数，使用计数副本计算，即PyGC_Head中的gc.gc_ref：
[gcmodule.c] static void
update_refs(PyGC_Head *containers)
{
PyGC_Head *gc = containers->gc.gc_next;
for (; gc != containers; gc = gc->gc.gc_next) {
assert(gc->gc.gc_refs == GC_REACHABLE);
gc->gc.gc_refs = Py_REFCNT(FROM_GC(gc));
/* Python's cyclic gc should never see an incoming refcount
* of 0: if something decref'ed to 0, it should have been
* deallocated immediately at that time.
* Possible cause (if the assert triggers): a tp_dealloc
* routine left a gc-aware object tracked during its teardown
* phase, and did something-- or allowed something to happen --
* that called back into Python. gc can trigger then, and may
* see the still-tracked dying object. Before this assert
* was added, such mistakes went on to allow gc to try to
* delete the object again. In a debug build, that caused
* a mysterious segfault, when _Py_ForgetReference tried
* to remove the object from the doubly-linked list of all
* objects a second time. In a release build, an actual
* double deallocation occurred, which leads to corruption
* of the allocator's internal bookkeeping pointers. That's
* so serious that maybe this should be a release-build
* check instead of an assert?
*/
assert(gc->gc.gc_refs != );
}
}
先将对象gc.gc_ref设置为ob_refcnt的值，再将循环引用摘除：
[gcmodule.c] static void
subtract_refs(PyGC_Head *containers)
{
traverseproc traverse;
PyGC_Head *gc = containers->gc.gc_next;
for (; gc != containers; gc=gc->gc.gc_next) {
traverse = Py_TYPE(FROM_GC(gc))->tp_traverse;
(void) traverse(FROM_GC(gc),
(visitproc)visit_decref,
NULL);
}
}
traverse与特定的container对象相关，用于遍历container对象中的每一个引用，对引用作某种动作，在subtract_refs中动作就是visit_dec_ref。完成后摘除了container对象间的环引用，得出root object（用于开始标记--清除算法）集合。
得出root object集合后，开始标记垃圾，用move_unreachable将可回收对象从root object链表中移到unreachable链表中：
[gcmodule.c] static void
move_unreachable(PyGC_Head *young, PyGC_Head *unreachable)
{
PyGC_Head *gc = young->gc.gc_next; /* Invariants: all objects "to the left" of us in young have gc_refs
* = GC_REACHABLE, and are indeed reachable (directly or indirectly)
* from outside the young list as it was at entry. All other objects
* from the original young "to the left" of us are in unreachable now,
* and have gc_refs = GC_TENTATIVELY_UNREACHABLE. All objects to the
* left of us in 'young' now have been scanned, and no objects here
* or to the right have been scanned yet.
*/ while (gc != young) {
PyGC_Head *next; if (gc->gc.gc_refs) {
/* gc is definitely reachable from outside the
* original 'young'. Mark it as such, and traverse
* its pointers to find any other objects that may
* be directly reachable from it. Note that the
* call to tp_traverse may append objects to young,
* so we have to wait until it returns to determine
* the next object to visit.
*/
PyObject *op = FROM_GC(gc);
traverseproc traverse = Py_TYPE(op)->tp_traverse;
assert(gc->gc.gc_refs > );
gc->gc.gc_refs = GC_REACHABLE;
(void) traverse(op,
(visitproc)visit_reachable,
(void *)young);
next = gc->gc.gc_next;
if (PyTuple_CheckExact(op)) {
_PyTuple_MaybeUntrack(op);
}
}
else {
/* This *may* be unreachable. To make progress,
* assume it is. gc isn't directly reachable from
* any object we've already traversed, but may be
* reachable from an object we haven't gotten to yet.
* visit_reachable will eventually move gc back into
* young if that's so, and we'll see it again.
*/
next = gc->gc.gc_next;
gc_list_move(gc, unreachable);
gc->gc.gc_refs = GC_TENTATIVELY_UNREACHABLE;
}
gc = next;
}
} static int
visit_reachable(PyObject *op, PyGC_Head *reachable)
{
if (PyObject_IS_GC(op)) {
PyGC_Head *gc = AS_GC(op);
const Py_ssize_t gc_refs = gc->gc.gc_refs; if (gc_refs == ) {
/* This is in move_unreachable's 'young' list, but
* the traversal hasn't yet gotten to it. All
* we need to do is tell move_unreachable that it's
* reachable.
*/
gc->gc.gc_refs = ;
}
else if (gc_refs == GC_TENTATIVELY_UNREACHABLE) {
/* This had gc_refs = 0 when move_unreachable got
* to it, but turns out it's reachable after all.
* Move it back to move_unreachable's 'young' list,
* and move_unreachable will eventually get to it
* again.
*/
gc_list_move(gc, reachable);
gc->gc.gc_refs = ;
}
/* Else there's nothing to do.
* If gc_refs > 0, it must be in move_unreachable's 'young'
* list, and move_unreachable will eventually get to it.
* If gc_refs == GC_REACHABLE, it's either in some other
* generation so we don't care about it, or move_unreachable
* already dealt with it.
* If gc_refs == GC_UNTRACKED, it must be ignored.
*/
else {
assert(gc_refs >
|| gc_refs == GC_REACHABLE
|| gc_refs == GC_UNTRACKED);
}
}
return ;
}
分割完就得到垃圾回收目标对象，unreachable链表中的对象。
但是，并不是所有在unreachable链表中的对象都能安全回收。
当一个container对象，从类对象实例化出来的实例对象，定义了__del__方法时（python中称为finalizer）。当一个拥有finalizer的实例对象被销毁时，首先调用finalizer，因为__del__是python在对象销毁时进行资源释放的Hook机制。问题是，unreachable链表中都是循环引用对象，需要被销毁，其中有对象的finalizer引用了另一对象，python又不能保证销毁顺序。python将unreachable链表中拥有finalizer的PyInstanceObject都移到garbage的PyListObject对象中。
回收unreachable链表中的垃圾对象：
[gcmodule.c] static int
gc_list_is_empty(PyGC_Head *list)
{
return (list->gc.gc_next == list);
} /* Break reference cycles by clearing the containers involved. This is
* tricky business as the lists can be changing and we don't know which
* objects may be freed. It is possible I screwed something up here.
*/
static void
delete_garbage(PyGC_Head *collectable, PyGC_Head *old)
{
inquiry clear; while (!gc_list_is_empty(collectable)) {
PyGC_Head *gc = collectable->gc.gc_next;
PyObject *op = FROM_GC(gc); assert(IS_TENTATIVELY_UNREACHABLE(op));
if (debug & DEBUG_SAVEALL) {
PyList_Append(garbage, op);
}
else {
if ((clear = Py_TYPE(op)->tp_clear) != NULL) {
Py_INCREF(op);
clear(op);
Py_DECREF(op);
}
}
if (collectable->gc.gc_next == gc) {
/* object is still alive, move it, it may die later */
gc_list_move(gc, old);
gc->gc.gc_refs = GC_REACHABLE;
}
}
}
对ob_refcnt下手，将unreachable链表中所有对象ob_refcnt变为0，引发对象销毁。
其中调用container对象的tp_clear操作，调整container对象中每个引用所用的对象的引用计数值，从而打破循环。
实际完成垃圾收集的collect：
[gcmodule.c] /* This is the main function. Read this to understand how the
* collection process works. */
static Py_ssize_t
collect(int generation)
{
int i;
Py_ssize_t m = ; /* # objects collected */
Py_ssize_t n = ; /* # unreachable objects that couldn't be collected */
PyGC_Head *young; /* the generation we are examining */
PyGC_Head *old; /* next older generation */
PyGC_Head unreachable; /* non-problematic unreachable trash */
PyGC_Head finalizers; /* objects with, & reachable from, __del__ */
PyGC_Head *gc;
double t1 = 0.0; if (delstr == NULL) {
delstr = PyString_InternFromString("__del__");
if (delstr == NULL)
Py_FatalError("gc couldn't allocate \"__del__\"");
} if (debug & DEBUG_STATS) {
PySys_WriteStderr("gc: collecting generation %d...\n",
generation);
PySys_WriteStderr("gc: objects in each generation:");
for (i = ; i < NUM_GENERATIONS; i++)
PySys_WriteStderr(" %" PY_FORMAT_SIZE_T "d",
gc_list_size(GEN_HEAD(i)));
t1 = get_time();
PySys_WriteStderr("\n");
} /* update collection and allocation counters */
if (generation+ < NUM_GENERATIONS)
generations[generation+].count += ;
for (i = ; i <= generation; i++)
generations[i].count = ; /* merge younger generations with one we are currently collecting */
for (i = ; i < generation; i++) {
gc_list_merge(GEN_HEAD(i), GEN_HEAD(generation));
} /* handy references */
young = GEN_HEAD(generation);
if (generation < NUM_GENERATIONS-)
old = GEN_HEAD(generation+);
else
old = young; /* Using ob_refcnt and gc_refs, calculate which objects in the
* container set are reachable from outside the set (i.e., have a
* refcount greater than 0 when all the references within the
* set are taken into account).
*/
update_refs(young);
subtract_refs(young); /* Leave everything reachable from outside young in young, and move
* everything else (in young) to unreachable.
* NOTE: This used to move the reachable objects into a reachable
* set instead. But most things usually turn out to be reachable,
* so it's more efficient to move the unreachable things.
*/
gc_list_init(&unreachable);
move_unreachable(young, &unreachable); /* Move reachable objects to next generation. */
if (young != old) {
if (generation == NUM_GENERATIONS - ) {
long_lived_pending += gc_list_size(young);
}
gc_list_merge(young, old);
}
else {
/* We only untrack dicts in full collections, to avoid quadratic
dict build-up. See issue #14775. */
untrack_dicts(young);
long_lived_pending = ;
long_lived_total = gc_list_size(young);
} /* All objects in unreachable are trash, but objects reachable from
* finalizers can't safely be deleted. Python programmers should take
* care not to create such things. For Python, finalizers means
* instance objects with __del__ methods. Weakrefs with callbacks
* can also call arbitrary Python code but they will be dealt with by
* handle_weakrefs().
*/
gc_list_init(&finalizers);
move_finalizers(&unreachable, &finalizers);
/* finalizers contains the unreachable objects with a finalizer;
* unreachable objects reachable *from* those are also uncollectable,
* and we move those into the finalizers list too.
*/
move_finalizer_reachable(&finalizers); /* Collect statistics on collectable objects found and print
* debugging information.
*/
for (gc = unreachable.gc.gc_next; gc != &unreachable;
gc = gc->gc.gc_next) {
m++;
if (debug & DEBUG_COLLECTABLE) {
debug_cycle("collectable", FROM_GC(gc));
}
} /* Clear weakrefs and invoke callbacks as necessary. */
m += handle_weakrefs(&unreachable, old); /* Call tp_clear on objects in the unreachable set. This will cause
* the reference cycles to be broken. It may also cause some objects
* in finalizers to be freed.
*/
delete_garbage(&unreachable, old); /* Collect statistics on uncollectable objects found and print
* debugging information. */
for (gc = finalizers.gc.gc_next;
gc != &finalizers;
gc = gc->gc.gc_next) {
n++;
if (debug & DEBUG_UNCOLLECTABLE)
debug_cycle("uncollectable", FROM_GC(gc));
}
if (debug & DEBUG_STATS) {
double t2 = get_time();
if (m == && n == )
PySys_WriteStderr("gc: done");
else
PySys_WriteStderr(
"gc: done, "
"%" PY_FORMAT_SIZE_T "d unreachable, "
"%" PY_FORMAT_SIZE_T "d uncollectable",
n+m, n);
if (t1 && t2) {
PySys_WriteStderr(", %.4fs elapsed", t2-t1);
}
PySys_WriteStderr(".\n");
} /* Append instances in the uncollectable set to a Python
* reachable list of garbage. The programmer has to deal with
* this if they insist on creating this type of structure.
*/
(void)handle_finalizers(&finalizers, old); /* Clear free list only during the collection of the highest
* generation */
if (generation == NUM_GENERATIONS-) {
clear_freelists();
} if (PyErr_Occurred()) {
if (gc_str == NULL)
gc_str = PyString_FromString("garbage collection");
PyErr_WriteUnraisable(gc_str);
Py_FatalError("unexpected exception during garbage collection");
}
return n+m;
}
python中的垃圾收集机制完全是为了处理循环引用而设计的，几乎大多数对象创建时都会被纳入垃圾收集机制的监控中。并且，正常的引用计数就能销毁一个被纳入垃圾收集机制监控的对象。
python很多对象挂在垃圾收集监控的链表上，但大多情况是引用计数在维护这些对象。对引用计数无能为力的循环引用，垃圾收集机制才起作用。而垃圾收集机制只处理引用计数不为0的情况：一是被程序使用的对象（不能被回收），二是循环引用对象。因此垃圾回收机制只能处理循环引用中的对象。
还有一点，PyObject_GC_New底层是以之前剖析的PyObject_Malloc作为真正申请内存的接口的，大多数情况下Python都在使用内存池。而本书中剖析过得最大的对象PyTypeObject也不超过200个字节，小于256个字节，故也使用内存池。因此可将垃圾收集和内存管理融为一体。
4.5、python 中 的gc模块
python中通过gc模块提供了观察和手动实用gc机制的接口。
具体打开python，动手实验。