pythonソース分析---メモリ割り当て(2)

23277 ワード

とっくに一部の内容を书くべきでした...最近は負のエネルギーが...怪我はしないよ.の
前編で述べたように、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のメモリ割り当てのものも大体分かりました...