Python 源码剖析（六）【内存管理机制】六、内存管理机制

六、内存管理机制

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) : 1))
#define PyMem_REALLOC(p, n)
((size_t)(n) > (size_t)PY_SSIZE_T_MAX
? NULL 
: realloc((p), (n) ? (n) : 1))
#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 > 0))
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 > 0);
/* 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 != 0) {
/* 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 != 0);
assert(ao ->nextarena == NULL ||
ao->nextarena->address != 0);
/* 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 != 0);
}
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 = 0;
/* mark unassociated */
--narenas_currently_allocated;
UNLOCK();
return;
}
if (nf == 1) {
/* 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 != 0);
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 > 0);
/* 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 = 0;
/* 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 = 0;
#ifdef PYMALLOC_DEBUG
/* Total number of times malloc() called to allocate an arena. */
static size_t ntimes_arena_allocated = 0;
/* High water mark (max value ever seen) for narenas_currently_allocated. */
static size_t narenas_highwater = 0;
#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 << 1 : 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 = 0;
/* mark as unassociated */
arenas[i].nextarena = i < numarenas - 1 ?
&arenas[i+1] : 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 == 0);
arenaobj->address = (uptr)malloc(ARENA_SIZE);
if (arenaobj->address == 0) {
/* 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 != 0) {
--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[2 * ((NB_SMALL_SIZE_CLASSES + 7) / 8) * 8] = {
PT(0), PT(1), PT(2), PT(3), PT(4), PT(5), PT(6), PT(7)
#if NB_SMALL_SIZE_CLASSES > 8
, PT(8), PT(9), PT(10), PT(11), PT(12), PT(13), PT(14), PT(15)
#if NB_SMALL_SIZE_CLASSES > 16
, PT(16), PT(17), PT(18), PT(19), PT(20), PT(21), PT(22), PT(23)
#if NB_SMALL_SIZE_CLASSES > 24
, PT(24), PT(25), PT(26), PT(27), PT(28), PT(29), PT(30), PT(31)
#if NB_SMALL_SIZE_CLASSES > 32
, PT(32), PT(33), PT(34), PT(35), PT(36), PT(37), PT(38), PT(39)
#if NB_SMALL_SIZE_CLASSES > 40
, PT(40), PT(41), PT(42), PT(43), PT(44), PT(45), PT(46), PT(47)
#if NB_SMALL_SIZE_CLASSES > 48
, PT(48), PT(49), PT(50), PT(51), PT(52), PT(53), PT(54), PT(55)
#if NB_SMALL_SIZE_CLASSES > 56
, PT(56), PT(57), PT(58), PT(59), PT(60), PT(61), PT(62), PT(63)
#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 == -1))
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 - 1) < SMALL_REQUEST_THRESHOLD) {
LOCK();
/*
* Most frequent paths first
*/
size = (uint)(nbytes - 1) >> 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 != 0);
/* 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 == 0) {
/* 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 != 0);
}
}
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 = 1;
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 << 1);
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 > 0);
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 == 0) {
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 != 0);
}
}
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 == 0)
nbytes = 1;
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 > 0))
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 > 0);
/* 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 != 0) {
/* 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 != 0);
assert(ao ->nextarena == NULL ||
ao->nextarena->address != 0);
/* 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 != 0);
}
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 = 0;
/* mark unassociated */
--narenas_currently_allocated;
UNLOCK();
return;
}
if (nf == 1) {
/* 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 != 0);
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 > 0);
/* 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[0].count++; /* number of allocated GC objects */
if (generations[0].count > generations[0].threshold &&
enabled &&
generations[0].threshold &&
!collecting &&
!PyErr_Occurred()) {
collecting = 1;
collect_generations();
collecting = 0;
}
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 (0);

从链表摘除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 (0);

 

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(0), GEN_HEAD(0), 0}},
700,
0},
{{{GEN_HEAD(1), GEN_HEAD(1), 0}},
10,
0},
{{{GEN_HEAD(2), GEN_HEAD(2), 0}},
10,
0},
};
PyGC_Head *_PyGC_generation0 = GEN_HEAD(0);

count表示有多少个可收集对象，threshold表示该链可容纳收集对象个数，当超过这个值时会触发垃圾回收机制：

[gcmodule.c]
static Py_ssize_t
collect_generations(void)
{
int i;
Py_ssize_t n = 0;
/* 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-1; i >= 0; 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 - 1
&& long_lived_pending < long_lived_total / 4)
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 != 0);
}
}

先将对象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 > 0);
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 == 0) {
/* 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 = 1;
}
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 = 1;
}
/* 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 > 0
|| gc_refs == GC_REACHABLE
|| gc_refs == GC_UNTRACKED);
}
}
return 0;
}

分割完就得到垃圾回收目标对象，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 = 0; /* # objects collected */
Py_ssize_t n = 0; /* # 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 = 0; 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+1 < NUM_GENERATIONS)
generations[generation+1].count += 1;
for (i = 0; i <= generation; i++)
generations[i].count = 0;
/* merge younger generations with one we are currently collecting */
for (i = 0; i < generation; i++) {
gc_list_merge(GEN_HEAD(i), GEN_HEAD(generation));
}
/* handy references */
young = GEN_HEAD(generation);
if (generation < NUM_GENERATIONS-1)
old = GEN_HEAD(generation+1);
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 - 2) {
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 = 0;
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 == 0 && n == 0)
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-1) {
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，动手实验。