pythonソース分析---メモリ割り当て(2)
23277 ワード
とっくに一部の内容を书くべきでした...最近は負のエネルギーが...怪我はしないよ.の
前編で述べたように、pythonのメモリ割り当てにおいて2つの非常に重要な方法:PyObject_MallocとPyObject_Free
具体的にこの2つの方法に来る前に、まず他のものを見てみましょう.
前述したように、poolは実際にarena構造上に割り当てられていますが、poolはarenaによって管理されているわけではありません.また、poolは実際にはタイプがあることを知っています.各タイプのpoolは固定サイズのメモリのみを割り当てるために使用されます.例えば、poolのszidx番号が0であれば、8バイトのメモリを割り当てるために使用されます.
はい、poolはarenaに割り当てられていますが、彼が管理しているわけではありません.では、何が管理しているのでしょうか...上に貼ったコードはusedpools配列を定義しています.うん、それで定義します.の
そして、それぞれのタイプのpoolが二重チェーンテーブルを構成しており、この配列はこの二重チェーンテーブルの頭部を保存しています..
ほほほ、间违いないでしょう、この事はどのように実现したのですか...この実现は本当に时々trickで、私も长い间见てやっと理解して、本当に才疏学浅で、以前は本当にこのような実现を见たことがありません...
前のマクロPTAとPTがあればわかりますが、PT(0)は実は2つのポインタを定義しており、保存されている値はちょうど1番目のポインタのアドレスから2つのポインタのアドレスを減算しています.うん、poolの定義を見てみましょう.
ええと、2つのポインタサイズを加えるとちょうどnextpoolポインタを指しているかどうか、3つのポインタサイズを加えるとprevpoolポインタを指しているかどうか見てみましょう.のここの実現はあまり言わない.の実は上の注釈もいくつかのものを説明しています...理解できないなら、自分でもっとよく見てください.のこの過程は必ず自分で努力して理解しなければならない...
では次にPyObject_を見てみましょうMallocの定義でしょう.
基本的に内容は上のコードの注釈ではっきり言うべきでしょう..ここでもう一つ面白いところはpoolがfreeblockポインタで離散した単鎖表を実現し、解放されたblockがこの単鎖表の頭部に置かれることです...この単一チェーンテーブルがどのように実現されているかについては...PyObjectを見てみましょうFreeの実現こそが...
では、次にその実現を見てみましょう.
これ、実はコードはよく理解するべきで、多くの判断があって、poolが空いているかどうか、arenaが空いているかどうか、それからarenaの順序を調整します..
また、上記のfreeblockの単一チェーンテーブルは、どのように実現されていますか.の実はよく見れば理解できるはずなのに...ここは詳しくは言いませんが...多くのものはやはり自分で理解しなければなりません..
ここまでpythonのメモリ割り当てのものも大体分かりました...
前編で述べたように、pythonのメモリ割り当てにおいて2つの非常に重要な方法:PyObject_MallocとPyObject_Free
具体的にこの2つの方法に来る前に、まず他のものを見てみましょう.
// usedpool
// 。。 。。。
// , pool , , next, 3 prev
//
#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)
#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 */
};
前述したように、poolは実際にarena構造上に割り当てられていますが、poolはarenaによって管理されているわけではありません.また、poolは実際にはタイプがあることを知っています.各タイプのpoolは固定サイズのメモリのみを割り当てるために使用されます.例えば、poolのszidx番号が0であれば、8バイトのメモリを割り当てるために使用されます.
はい、poolはarenaに割り当てられていますが、彼が管理しているわけではありません.では、何が管理しているのでしょうか...上に貼ったコードはusedpools配列を定義しています.うん、それで定義します.の
そして、それぞれのタイプのpoolが二重チェーンテーブルを構成しており、この配列はこの二重チェーンテーブルの頭部を保存しています..
ほほほ、间违いないでしょう、この事はどのように実现したのですか...この実现は本当に时々trickで、私も长い间见てやっと理解して、本当に才疏学浅で、以前は本当にこのような実现を见たことがありません...
前のマクロPTAとPTがあればわかりますが、PT(0)は実は2つのポインタを定義しており、保存されている値はちょうど1番目のポインタのアドレスから2つのポインタのアドレスを減算しています.うん、poolの定義を見てみましょう.
struct pool_header {
union { block *_padding;
uint count; } ref; /* number of allocated blocks */ // pool block
block *freeblock; /* pool's free list head */ // block, , ,
struct pool_header *nextpool; /* next pool of this size class */ // pool
struct pool_header *prevpool; /* previous pool "" */
uint arenaindex; /* index into arenas of base adr */ // arena
uint szidx; /* block size class index */ // ,8 ,16 。。。
uint nextoffset; /* bytes to virgin block */ // block
uint maxnextoffset; /* largest valid nextoffset */ // block
};
typedef struct pool_header *poolp; //
ええと、2つのポインタサイズを加えるとちょうどnextpoolポインタを指しているかどうか、3つのポインタサイズを加えるとprevpoolポインタを指しているかどうか見てみましょう.のここの実現はあまり言わない.の実は上の注釈もいくつかのものを説明しています...理解できないなら、自分でもっとよく見てください.のこの過程は必ず自分で努力して理解しなければならない...
では次に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
*/
// nbytes 8 , 0
// 8 , 0,9 1,16 1,17 2, pool
// pool
size = (uint)(nbytes - 1) >> ALIGNMENT_SHIFT; //ALIGNMENT_SHIFT=3
pool = usedpools[size + size]; // pool
if (pool != pool->nextpool) { // pool
/*
* There is a used pool for this size class.
* Pick up the head block of its free list.
*/
++pool->ref.count; // block +1
bp = pool->freeblock; // bp freeblock,
assert(bp != NULL);
// freeblock , block
// block
if ((pool->freeblock = *(block **)bp) != NULL) {
// , block,
UNLOCK();
return (void *)bp;
}
// freeblock ,
if (pool->nextoffset <= pool->maxnextoffset) {
/* There is room for another block. */
// pool , freeblock
pool->freeblock = (block*)pool +
pool->nextoffset;
pool->nextoffset += INDEX2SIZE(size); // nextoffset
*(block **)(pool->freeblock) = NULL; // NULL,
UNLOCK();
return (void *)bp;
}
/* Pool is full, unlink from used pools. */
// , pool , pool usedpool
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.
*/
// , pool
// pool
if (usable_arenas == NULL) { // arena,
/* 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. */
// arena pool
pool = usable_arenas->freepools;
if (pool != NULL) {
/* Unlink from cached pools. */
// arena freepool
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; // pool 1
if (usable_arenas->nfreepools == 0) {
// , arena , arena usable_arenas
/* 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. */
// pool, usedpool
// pool ,
next = usedpools[size + size]; /* == prev */
pool->nextpool = next;
pool->prevpool = next;
next->nextpool = pool;
next->prevpool = pool;
pool->ref.count = 1; // block 1
if (pool->szidx == size) { // pool ,
/* 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; // block
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 ,
pool->szidx = size;
size = INDEX2SIZE(size); //
bp = (block *)pool + POOL_OVERHEAD; // , arena
pool->nextoffset = POOL_OVERHEAD + (size << 1);
pool->maxnextoffset = POOL_SIZE - size; // block
pool->freeblock = bp + size; // block
*(block **)(pool->freeblock) = NULL; // null, freeblock block, ,
UNLOCK();
return (void *)bp;
}
/* Carve off a new pool. */
// arena pool, arena freepool ,
// freepool , freepool
assert(usable_arenas->nfreepools > 0);
assert(usable_arenas->freepools == NULL);
pool = (poolp)usable_arenas->pool_address; // pool
assert((block*)pool <= (block*)usable_arenas->address +
ARENA_SIZE - POOL_SIZE);
pool->arenaindex = usable_arenas - arenas; // pool arena
assert(&arenas[pool->arenaindex] == usable_arenas);
pool->szidx = DUMMY_SIZE_IDX; // pool , pool
usable_arenas->pool_address += POOL_SIZE; // pool
--usable_arenas->nfreepools; // pool
// arena pool , usable_arenas
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);
}
}
// pool
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);
}
基本的に内容は上のコードの注釈ではっきり言うべきでしょう..ここでもう一つ面白いところはpoolがfreeblockポインタで離散した単鎖表を実現し、解放されたblockがこの単鎖表の頭部に置かれることです...この単一チェーンテーブルがどのように実現されているかについては...PyObjectを見てみましょうFreeの実現こそが...
では、次にその実現を見てみましょう.
void
PyObject_Free(void *p)
{
poolp pool; // 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
// block pool , arena pool
// 4KB , 4KB
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 */
// freeblock , , freelock,
// block blcok
*(block **)p = lastfree = pool->freeblock; // P freelock ,
pool->freeblock = (block *)p; // freeblock , block
if (lastfree) {
// , ,pool
// pool
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 block, usedpools
/* 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).
*/
// , pool , pool usedpool
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.
*/
// pool arena, pool arena pool
ao = &arenas[pool->arenaindex];
pool->nextpool = ao->freepools;
ao->freepools = pool;
nf = ++ao->nfreepools; // arena pool +1
/* 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.
*/
/**
(1) arena pool , arena 256KB
(2) pool arena pool, arena usable_arenas
(3) arena pool arena , arena , , pool
**/
if (nf == ao->ntotalpools) { // arena pool
//
/* 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.
*/
// arena unused_arena_objects
ao->nextarena = unused_arena_objects;
unused_arena_objects = ao;
/* Free the entire arena. */
// arena 256KB
#ifdef ARENAS_USE_MMAP
munmap((void *)ao->address, ARENA_SIZE);
#else
free((void *)ao->address);
#endif
ao->address = 0; /* mark unassociated */
--narenas_currently_allocated;
UNLOCK();
return;
}
if (nf == 1) { // pool 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.
*/
// arena usable_arenas
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.
*/
// arena arena , arena pool
// arena ,
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.
*/
// arena next arena, pool
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.
*/
// arena , pool
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 , ,
// pool pool
--pool->ref.count; // block 1
assert(pool->ref.count > 0); /* else the pool is empty */
size = pool->szidx;
next = usedpools[size + size]; // szidx pool
prev = next->prevpool;
/* insert pool before next: prev <-> pool <-> next */
// pool
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);
}
これ、実はコードはよく理解するべきで、多くの判断があって、poolが空いているかどうか、arenaが空いているかどうか、それからarenaの順序を調整します..
また、上記のfreeblockの単一チェーンテーブルは、どのように実現されていますか.の実はよく見れば理解できるはずなのに...ここは詳しくは言いませんが...多くのものはやはり自分で理解しなければなりません..
ここまでpythonのメモリ割り当てのものも大体分かりました...