最近在读 Python 源码中有关内存管理的部分。Python 在分配小块内存(小于 256 字节)时,采用了内存池,以降低对内核内存分配程序的调用频次。在内存池的设计上,采用了一个分层的设计,由上到下依次是 arena、pool、block。这次我看到的这个比较费解的结构,就来自于分配内存时,对于 pool 的处理。
在最主要的分配内存的函数_PyObject_Alloc 中,我看到了这么一段代码:
- pool = usable_arenas->freepools;
- // some other code ...
- init_pool:
- /* Frontlink to used pools. */
- next = usedpools[size + size]; /* == prev */
- pool->nextpool = next;
- pool->prevpool = next;
- next->nextpool = pool;
- next->prevpool = pool;
从注释和函数命名中也能看出来,这段代码的意思,大概是从 arena 的 freepools 中拿出一个 pool,插入到 usedpools 的开头。但是,这里有一个奇怪的地方:
如果说 usedpools 中存储的不同 size 的 pool 链表,那么为什么 index 要用 size+size 来表示呢?
首先,我在代码中搜索了一下 usedpools,找到了这么一段注释:
This is involved. For an index i, usedpools[i+i] is the header for a list of
all partially used pools holding small blocks with "size class idx" i. So
usedpools[0] corresponds to blocks of size 8, usedpools[2] to blocks of size
16, and so on: index 2*i <-> blocks of size (i+1)<<ALIGNMENT_SHIFT.
哦,就是说,我要找到保存 8 字节 block 的 pool,就去 usedpools[0+0]; 找 16 字节的 pool,就去 usedpools[1+1]。再看一下上面代码中的 size 的由来:
- size = (uint)(nbytes - 1) >> ALIGNMENT_SHIFT;
果然可以和注释里写的对应起来(注意,注释里的 2*i 是 usedpools 的 index,而这里的 nbytes 是实际需要分配的 block 的字节大小,所以一个需要左移位,一个需要右移位,互相转换)。
但是目前为止,好像处在一个 "知其然,而不知其所以然" 的状态:这里没有解释为什么是这样一个奇葩的 size+size 的 index。
往下,又有一段注释(Python 源码的注释真详细):
Major obscurity: While the usedpools vector is declared to have poolp
entries, it doesn't really. It really contains two pointers per (conceptual)
poolp entry, the nextpool and prevpool members of a pool_header. The
excruciating initialization code below fools C so that
usedpool[i+i]
"acts like" a genuine poolp, but only so long as you only reference its
nextpool and prevpool members. The "- 2)" gibberish is
compensating for that a pool_header's nextpool and prevpool members
immediately follow a pool_header's first two members:
union { block *_padding;
uint count; } ref;
block *freeblock;
each of which consume sizeof(block) bytes. So what usedpools[i+i] really
if* C believes it's a poolppointer, then p->nextpool and p->prevpool are both p (meaning that the headed circular list is empty).
这一大段注释说了什么呢?大意就是,你以为 usedpools 里放的是 poolp 类型?其实里面是两两一对的 poolp,一个是 nextpool 指针,一个是 prevpool 指针。这里还使用了一些 trick,让 C 语言认为 usedpools 里放的是 pool_header 变量,只要使用者能保证只使用它的 nextpool、prevpool 成员。
直接看 usedpools 的定义吧:
- #define PTA(x)((poolp)((uint8_t * ) & (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)……
- };
展开宏定义:
- static poolp usedpools[2 * ((NB_SMALL_SIZE_CLASSES + 7) / 8) * 8] = {
- PTA(0),
- PTA(0),
- PTA(1),
- PTA(1),
- PTA(2),
- PTA(2),
- PTA(3),
- PTA(3),
- ...……
- };
而 PTA(x) 定义为,usedpools[2x] 的地址减去 2 个 block * 长度的地址。结合 pool_header 的定义:
- 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 */
- };
nextpool 和 pool_header 的地址之间,正好差了 2 个 block * 的偏移量。所以,在初始化 usedpools 之后,当把 usedpools[size+size] 当作 pool_header 时,那么 usedpools[size+size]->nextpool 将正好取到 usedpools[size+size] 的地址,也就是指向 usedpools[size+size];而 usedpools[size+size]->prevpool 将也正好取到 usedpools[size+size] 的地址。因此:
- next = usedpools[size + size];
- /* == prev */
这段代码 + 注释就说得通了。
然后,经过:
- pool->nextpool = next;
- pool->prevpool = next;
- next->nextpool = pool;
- next->prevpool = pool;
这么一折腾,usedpools 中存储的一对地址(nextpool, prevpool)就指向了真正的 pool_header 变量 pool。
但是,为什么要这么绕的设计这样的 usedpools 结构呢,直接存储一个完整的 pool_header 不简单明了吗?下面这段注释给出了答案:
It's unclear why the usedpools setup is so convoluted. It could be to
minimize the amount of cache required to hold this heavily-referenced table
(which only the two interpool pointer members of a pool_header).
就是说,这样的一个 usedpools 表,会经常的被使用,使用这种结构,就可以减少放入缓存中的数据量(毕竟,我们只需要放入两个指针,而不是整个 pool_header),从而也就提高了缓存的效率。为了提高效率,还真是无所不用其极啊。
到这里,obmalloc.c 中我认为最费解的一个数据结构,就弄清楚啦。
推荐阅读:
{aa2aa}
欢迎关注我的微信公众号 TechTalking,技术 · 生活 · 思考:
来源: http://www.tuicool.com/articles/n6Bjaqn