blog
blog copied to clipboard
Published
20 hours ago •
junnplus
junnplus
Python的内存模型架构 -- 内存池
arena 内存池 (arena的管理)
我们来看看arena是如何被管理的。
/*==========================================================================
Arena management.
`arenas` is a vector of arena_objects. It contains maxarenas entries, some of
which may not be currently used (== they're arena_objects that aren't
currently associated with an allocated arena). Note that arenas proper are
separately malloc'ed.
Prior to Python 2.5, arenas were never free()'ed. Starting with Python 2.5,
we do try to free() arenas, and use some mild heuristic strategies to increase
the likelihood that arenas eventually can be freed.
unused_arena_objects
This is a singly-linked list of the arena_objects that are currently not
being used (no arena is associated with them). Objects are taken off the
head of the list in new_arena(), and are pushed on the head of the list in
PyObject_Free() when the arena is empty. Key invariant: an arena_object
is on this list if and only if its .address member is 0.
usable_arenas
This is a doubly-linked list of the arena_objects associated with arenas
that have pools available. These pools are either waiting to be reused,
or have not been used before. The list is sorted to have the most-
allocated arenas first (ascending order based on the nfreepools member).
This means that the next allocation will come from a heavily used arena,
which gives the nearly empty arenas a chance to be returned to the system.
In my unscientific tests this dramatically improved the number of arenas
that could be freed.
Note that an arena_object associated with an arena all of whose pools are
currently in use isn't on either list.
*/
通过上面的注释我们可以知道，在Python中，arena_object被数组arenas管理，arenas数组包含了maxarenas个arena_object。
/* 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;
需要注意的是，arenas数组管理的arena_object可能还没有分配arena内存块，所以arena_object分为两种状态：
- 一种是“未使用”状态，
arena_object还没有分配arena内存； - 一种是“可用”状态，
arena_object分配了arena内存块。
两种状态都有一个arena_object链表对应着。
/* 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;
unused_arena_objects是连接了“未使用”的arena_object的单向链表表头，arena_object与arena_object之间通过nextarena连接。
usable_arenas是连接了“可用”的arena_object的双向链表表头，arena_object与arena_object之间通过nextarena和prevarena连接。其中arena分配了可利用的pool，这个pool正在等待被再次使用或者还未被使用。这个链表是按照成员nfreepools升序排序，也就是说下次分配会从使用最多的arena开始取。几乎为空的arena将可能返回系统释放arena。
我们接下来看看arena如何被创建的。
new_arena函数生成一个arena，我们先整体的看下new_arena函数：
/* 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 */
void *address;
...
if (unused_arena_objects == NULL) {
/* 生成 `arena_object` */
/* 把 `arena_object` 放到 arenas 和 unused_arena_objects 中 */
}
/* 给`arena_object` 结构体分配 arena 内存块 */
/* 把 arena 内存块划分 pool */
return arenaobj;
}
我们先看if语句里面的内容：
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.
*/
// [1]
numarenas = maxarenas ? maxarenas << 1 : INITIAL_ARENA_OBJECTS;
// [2]
if (numarenas <= maxarenas)
return NULL; /* overflow */
#if SIZEOF_SIZE_T <= SIZEOF_INT
if (numarenas > SIZE_MAX / sizeof(*arenas))
return NULL; /* overflow */
#endif
// [3]
nbytes = numarenas * sizeof(*arenas);
arenaobj = (struct arena_object *)PyMem_RawRealloc(arenas, nbytes);
if (arenaobj == NULL)
return NULL;
arenas = arenaobj;
当没有“未使用”的arena_object的时候，需要扩充arenas数组。
[1]处确定本次需要申请的arena_object个数。
需要注意的是，第一次初始化的时候，arenas大小maxarenas为0，这时候会默认申请16个arena_object。
/* 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
除此之外，numarenas会被设置成maxarenas的两倍，[2]这边就要注意numarenas可能会溢出。
[3]这边申请了numarenas - maxarenas大小的内存空间，PyMem_RawRealloc函数在前面提到了是第1层的分配器，等同于第0层的realloc，在第一个参数为NULL时，与malloc相同。
同时arenas指向申请的内存空间首地址。
/* 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. */
// [1]
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. */
// [2]
unused_arena_objects = &arenas[maxarenas];
maxarenas = numarenas;
}
[1]我们把新分配的arena_object作为“未使用”的arena_object通过nextarena连接到一个单向链表，同时初始化arena_object的addree指针域为0，表明没有分配arena内存块。
[2]将unused_arena_objects指向单向链表表头地址，并更新maxarenas的值。
完成数组arenas的工作之后，接下来是给arena_object结构体分配arena内存块：
/* Take the next available arena object off the head of the list. */
assert(unused_arena_objects != NULL);
// [1]
arenaobj = unused_arena_objects;
unused_arena_objects = arenaobj->nextarena;
assert(arenaobj->address == 0);
address = _PyObject_Arena.alloc(_PyObject_Arena.ctx, ARENA_SIZE);
if (address == NULL) {
/* The allocation failed: return NULL after putting the
* arenaobj back.
*/
arenaobj->nextarena = unused_arena_objects;
unused_arena_objects = arenaobj;
return NULL;
}
// [2]
arenaobj->address = (uintptr_t)address;
[1]从unused_arena_objects链表中取出未使用的arena_object，并申请arena内存块空间(256KB)，如果申请内存失败会将arena_object再次连接到unused_arena_objects中。
[2]arena_object的address指针域指向刚申请的arena内存块首地址。
arena_object分配了arena之后就变成了“可用”状态，就与unused_arena_objects没有关系了，等待着被usable_arenas接收。
接下来就是在arena内存块中划分pool：
++narenas_currently_allocated;
++ntimes_arena_allocated;
if (narenas_currently_allocated > narenas_highwater)
narenas_highwater = narenas_currently_allocated;
arenaobj->freepools = NULL;
/* pool_address <- first pool-aligned address in the arena
nfreepools <- number of whole pools that fit after alignment */
// [1]
arenaobj->pool_address = (block*)arenaobj->address;
arenaobj->nfreepools = ARENA_SIZE / POOL_SIZE;
assert(POOL_SIZE * arenaobj->nfreepools == ARENA_SIZE);
// [2]
excess = (uint)(arenaobj->address & POOL_SIZE_MASK);
if (excess != 0) {
--arenaobj->nfreepools;
arenaobj->pool_address += POOL_SIZE - excess;
}
arenaobj->ntotalpools = arenaobj->nfreepools;
[1]新分配的arena的freepools指针域设置为NULL，这是因为需要等到释放一个pool时，这个freepools才会被用到。
[2]将arena_object结构体的pool_address指针域指向address指针域，空闲的pool数量通过ARENA_SIZE / POOL_SIZE = 64 计算得到。
[3]通过POOL_SIZE_MASK(4K - 1)来对arena的地址进行屏蔽处理，计算超出过的量excess，excess为0表示当前arena的地址刚好是4K对齐的（4K字节的倍数），arena内被pool填满了。如果超过的量不为0，pool_address就会偏移POOL_SIZE - excess大小。此时arena内前后加起来会产生一个pool的空白，空闲的pool数量自然也要减掉一个。
数组arenas实际上就是小块内存池，上一篇提到过，Python内部默认的小块内存与大块内存的分界点是512KB，当申请的内存小于512字节时，PyObject_Malloc会在内存池中申请内存；当申请的内存大于512字节时，PyObject_Malloc会调用malloc来申请内存。而Python对小块内存的arena的个数是否有限制呢？
Python通过WITH_MEMORY_LIMITS编译参数来激活对内存的限制：
/*
* 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()/mmap() 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...
*
* Arenas are allocated with mmap() on systems supporting anonymous memory
* mappings to reduce heap fragmentation.
*/
#define ARENA_SIZE (256 << 10) /* 256KB */
#ifdef WITH_MEMORY_LIMITS
#define MAX_ARENAS (SMALL_MEMORY_LIMIT / ARENA_SIZE)
#endif
SMALL_MEMORY_LIMIT表示小块内存池的大小，同时也会限制了arenas的大小。默认情况下是没有对小块内存池的大小做任何限制。
pool 内存池 (pool的管理)
在实际的使用中，Python并不直接与arenas和arena打交道。当Python申请内存时，最基本的操作单元并不是arena，而是pool。
我们知道block是Python中内存分配的最小单位，而block是由pool来管理的，pool是一个有size概念的内存管理抽象体，一个pool中的block总是有确定的大小。因此，要找到与所申请的大小相对应的block，需要先找到有这个block的pool。
Python中为了实现快速搜索对应block大小的pool，维护了一个usedpools的数组。在了解usedpools数组之前，我们得先提以下pool的三种状态：
- used状态，pool中部分block被使用，这种状态的pool受控
usedpools数组； - full状态，pool中所有的block都被使用；
- empty状态，pool中所有的block都未被使用，处于这个状态的pool的集合通过
pool_header中的nextpool构成单向链表，这个链表的表头就是arena_object中的freepools。
arena包含的三种状态pool的表示：
那么usedpools是怎么和pool联系起来呢？
当申请内存时，申请的大小会对应到一个size class index，就是通过索引将usedpools和pool联系起来的。
usedpools的每个size class index都会对应一个pool_header指针，每个pool用双向链表相连，形成一个循环双向链表。
我们来看下usedpools的定义：
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)
#if NB_SMALL_SIZE_CLASSES > 64
#error "NB_SMALL_SIZE_CLASSES should be less than 64"
#endif /* NB_SMALL_SIZE_CLASSES > 64 */
#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 */
};
usedpools是一个指向pool_header指针的数组。
typedef struct pool_header *poolp;
其中的NB_SMALL_SIZE_CLASSES指明了一共有多少size class：
#define ALIGNMENT 8 /* must be 2^N */
...
#define SMALL_REQUEST_THRESHOLD 512
#define NB_SMALL_SIZE_CLASSES (SMALL_REQUEST_THRESHOLD / ALIGNMENT)
usedpools元素PT(0)是可以被展开的：
#define PTA(x) ((poolp )((uint8_t *)&(usedpools[2*(x)]) - 2*sizeof(block *)))
#define PT(x) PTA(x), PTA(x)
展开之后的usedpools看上去是这样的：
static poolp usedpools[142] = {
PTA(0), PTA(0), PTA(1), PTA(1), PTA(2), PTA(2), PTA(3), PTA(3), PTA(4), PTA(4), PTA(5), PTA(5), PTA(6), PTA(6), PTA(7), PAT(7),
...
}
被调用的PTA宏的定义：
#define PTA(x) ((poolp )((uint8_t *)&(usedpools[2*(x)]) - 2*sizeof(block *)))
这个宏定义为，指向usedpools[2x]的地址再往前两个block *大小的位置。结合usedpools是一个指向pool_header指针的数组来看：
struct pool_header {
union { block *_padding;
uint count; } ref;
block *freeblock;
struct pool_header *nextpool;
struct pool_header *prevpool;
...
}
nextpool和pool_header的地址之间，正好差了两个block *的偏移量。
实际上在初始化usedpools的之后，把usedpools[size + size]当作pool_header用的话，那么usedpools[size + size].nextpool正好取到usedpools[size + size]的地址，而么usedpools[size + size].prevpool也正好取到usedpools[size + size]的地址。
为什么会设计成初始化这么复杂的usedpools数组呢？其实是有原因的。
因为usedpools数组会经常被使用，如果直接存储一个完整的pool_header会导致userpools数组变大，缓存承载不下。
PyObject_Malloc
我们再回到上一篇的PyObject_Malloc(_PyObject_Alloc)函数。
static void *
_PyObject_Alloc(int use_calloc, void *ctx, size_t nelem, size_t elsize)
{
...
// 小块内存分配
if ((nbytes - 1) < SMALL_REQUEST_THRESHOLD) {
// [A] 从 usedpools 中分配 pool
pool = usedpools[size + size];
if (pool != pool->nextpool) {
// 返回 pool 中的 block
}
// [B] 无可用 arena
if (usable_arenas == NULL) {
// 通过 new_arena() 生成 arena
}
// [C] 分配使用完释放的 pool
pool = usable_arenas->freepools;
if (pool != NULL) {
// 初始化使用完释放的 pool 并返回 block
}
// [D] 分配空的 pool
pool = (poolp)usable_arenas->pool_address;
// 初始化空的 pool 并返回 block
}
...
}
把代码分成4块来看：
- [A] 从 usedpools 中分配 pool，并返回 pool 中的 block
- [B] 无可用 arena 时，通过 new_arena() 生成 arena
- [C] 从 usable_arenas->freepools 分配使用完释放的 pool，初始化并返回 block
- [D] 从 usable_arenas->pool_address 分配空的 pool，初始化并返回 blcok
当Python启动之后，在usedpools这个小块空间内存池中，并不存在任何可用的内存，准确地说，不存在任何可用的pool。在这里，Python采用了延迟分配的策略，即当我们确实开始申请小块内存时，Python才开始建立这个内存池。正如前面所提到的，当申请28个字节的内存时，Python实际上将申请32字节的内存。Python首先会根据32字节对应的class size index（3）在usedpools中对应的位置查找，如果发现在对应的位置后并没有链接任何可用的pool，Python会从usable_arenas链表中的第一个“可用的”arena中获得一个pool。
摘自：《Python源码剖析》 — 陈儒
所以上面的4块代码，会按照[B][D][A][C]的顺序来解读。
[B] 无可用 arena 时，通过 new_arena() 生成 arena。
/* 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);
usable_arenas指向新生成arena的地址，并构建双向链表。
[D] 从 usable_arenas->pool_address 分配空的 pool，初始化并返回 blcok
/* Carve off a new pool. */
assert(usable_arenas->nfreepools > 0);
assert(usable_arenas->freepools == NULL);
// [1]
pool = (poolp)usable_arenas->pool_address;
assert((block*)pool <= (block*)usable_arenas->address +
ARENA_SIZE - POOL_SIZE);
pool->arenaindex = (uint)(usable_arenas - arenas);
assert(&arenas[pool->arenaindex] == usable_arenas);
// [2]
pool->szidx = DUMMY_SIZE_IDX;
// [3]
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);
}
}
// [4]
goto init_pool;
[1]从pool_address取出一个空的pool，然后设置pool中的arenaindex，这个index实际上就是pool所在的arena位于arenas所指的数组中的序号。
[2]将新的pool的szidx设置为DUMMY_SIZE_IDX，用来表示还没确定pool中block的大小。
#define DUMMY_SIZE_IDX 0xffff /* size class of newly cached pools */
[3]pool_address未被利用的pool的地址开头向后移动一个pool大小。
[4]初始化pool
init_pool:
/* Frontlink to used pools. */
// [1]
next = usedpools[size + size]; /* == prev */
pool->nextpool = next;
pool->prevpool = next;
next->nextpool = pool;
next->prevpool = pool;
pool->ref.count = 1;
// [2]
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;
assert(bp != NULL);
pool->freeblock = *(block **)bp;
UNLOCK();
if (use_calloc)
memset(bp, 0, nbytes);
return (void *)bp;
}
/*
* Initialize the pool header, set up the free list to
* contain just the second block, and return the first
* block.
*/
// [3]
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();
if (use_calloc)
memset(bp, 0, nbytes);
return (void *)bp;
[1]将新的pool加入usedpools[size + size]对应的双向链表中。
[2]判断这个pool的block大小是否是申请的大小，如果是就从pool的freeblock取一个block返回。
[3]这边是上一篇介绍的pool的初始化。当pool的block大小不是申请的大小是，这个pool会重新初始化并返回block。
[A] 从 usedpools 中分配 pool，并返回 pool 中的 block。
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);
// [1]
if ((pool->freeblock = *(block **)bp) != NULL) {
UNLOCK();
if (use_calloc)
memset(bp, 0, nbytes);
return (void *)bp;
}
/*
* Reached the end of the free list, try to extend it.
*/
// [2]
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();
if (use_calloc)
memset(bp, 0, nbytes);
return (void *)bp;
}
// [3]
/* Pool is full, unlink from used pools. */
next = pool->nextpool;
pool = pool->prevpool;
next->prevpool = pool;
pool->nextpool = next;
UNLOCK();
if (use_calloc)
memset(bp, 0, nbytes);
return (void *)bp;
}
从pool的freeblock指向的位置取出一个block，这个block可能是使用完毕的空闲block，也可能是未被使用的block。
[1]当有使用完毕的block就返回。
[2]如果是未被使用的block，且下一次还可以分配block的话，需要将freeblock和nextoffset都会向后移动一个block的距离。
[3]如果下一次不能在分配block，也就是当前pool为full状态，就把pool从usedpools内存池中拿走。
[C] 从 usable_arenas->freepools 分配使用完释放的 pool，初始化并返回 block
/* 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:
...
}
从usable_arenas->freepools取出使用完释放的pool，将pool放入对应的usedpools[size + size]双向链表中，然后初始化并返回block。
PyObject_Free
void
PyObject_Free(void *ptr)
{
_PyObject.free(_PyObject.ctx, ptr);
}
static void
_PyObject_Free(void *ctx, void *p)
{
/* PyObject_Free(NULL) has no effect */
if (p == NULL) {
return;
}
_Py_AllocatedBlocks--;
if (!pymalloc_free(ctx, p)) {
/* pymalloc didn't allocate this address */
PyMem_RawFree(p);
}
}
/* Free a memory block allocated by pymalloc_alloc().
Return 1 if it was freed.
Return 0 if the block was not allocated by pymalloc_alloc(). */
static int
pymalloc_free(void *ctx, void *p)
{
poolp pool;
block *lastfree;
poolp next, prev;
uint size;
assert(p != NULL);
#ifdef WITH_VALGRIND
if (UNLIKELY(running_on_valgrind > 0)) {
return 0;
}
#endif
pool = POOL_ADDR(p);
if (!address_in_range(p, pool)) {
return 0;
}
/* We allocated this address. */
/* 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) {
/* 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;
goto success;
}
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 */
goto success;
}
/* 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. */
_PyObject_Arena.free(_PyObject_Arena.ctx,
(void *)ao->address, ARENA_SIZE);
ao->address = 0; /* mark unassociated */
--narenas_currently_allocated;
goto success;
}
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);
goto success;
}
/* 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. */
goto success;
}
/* 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);
goto success;
success:
return 1;
}
