logo
当前位置:首 页 > 编程技术 >服务器语言 >python > 查看文章

Python 的内存分配策略

arena

arena: 多个pool聚合的结果

arena size

pool的大小默认值位4KB

arena的大小默认值256KB, 能放置 256/4=64 个pool

obmalloc.c中代码

#define ARENA_SIZE              (256 << 10)     /* 256KB */

arena 结构

一个完整的arena = arena_object + pool集合

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. */

    // 单链表, 可用pool集合

    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.

*/

    // arena链表

    struct arena_object* nextarena;

    struct arena_object* prevarena;

};

arena_object的作用

1. 与其他arena连接, 组成双向链表

2. 维护arena中可用的pool, 单链表

3. 其他信息

pool_header 与 arena_object

pool_header和管理的blocks内存是一块连续的内存 => pool_header被申请时, 其管理的block集合的内存一并被申请

arena_object和其管理的内存是分离的 => arena_object被申请时, 其管理的pool集合的内存没有被申请, 而是在某一时刻建立的联系

arena的两种状态

arena存在两种状态: 未使用(没有建立联系)/可用(建立了联系)

全局由两个链表维护着

/* 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;

arena的初始化

首先, 来看下初始化相关的一些参数定义

代码obmalloc.c

/* Array of objects used to track chunks of memory (arenas). */

// arena_object 数组

static struct arena_object* arenas = NULL;

 

/* Number of slots currently allocated in the `arenas` vector. */

// 当前arenas中管理的arena_object的个数, 初始化时=0

static uint maxarenas = 0;

 

/* How many arena_objects do we initially allocate?

* 16 = can allocate 16 arenas = 16 * ARENA_SIZE = 4MB before growing the

* `arenas` vector.

*/

// 初始化时申请的arena_object个数

#define INITIAL_ARENA_OBJECTS 16

 

/* Number of arenas allocated that haven’t been free()’d. */

static size_t narenas_currently_allocated = 0;

 

/* The head of the singly-linked, NULL-terminated list of available

* arena_objects.

*/

// 未使用状态arena的单链表

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.

*/

// 可用状态arena的双向链表

static struct arena_object* usable_arenas = NULL;

然后, 看下obmalloc.c中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;

    int err;

 

    // 判断是否需要扩充”未使用”的arena_object列表

    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.

*/

        // 确定需要申请的个数, 首次初始化, 16, 之后每次翻倍

        numarenas = maxarenas ? maxarenas  1 : INITIAL_ARENA_OBJECTS;

        if (numarenas  maxarenas)

            return NULL;                /* overflow */  //溢出了

 

        ….

 

        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 */

            // 新申请的一律为0, 标识着这个arena处于”未使用”

            arenas[i].nextarena = i  numarenas – 1 ?

                                   &arenas[i+1] : NULL;

        }

 

        // 将其放入unused_arena_objects链表中

        // unused_arena_objects 为新分配内存空间的开头

        /* 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);

 

    // 从unused_arena_objects中, 获取一个未使用的object

    arenaobj = unused_arena_objects;

    unused_arena_objects = arenaobj->nextarena; // 更新链表

 

    // 开始处理这个 arenaobject

 

    assert(arenaobj->address == 0);

    // 申请内存, 256KB, 内存地址赋值给arena的address. 这块内存可用

#ifdef ARENAS_USE_MMAP

    address = mmap(NULL, ARENA_SIZE, PROT_READ|PROT_WRITE,

                   MAP_PRIVATE|MAP_ANONYMOUS, –1, 0);

    err = (address == MAP_FAILED);

#else

    address = malloc(ARENA_SIZE);

    err = (address == 0);

#endif

    if (err) {

        /* The allocation failed: return NULL after putting the

* arenaobj back.

*/

        arenaobj->nextarena = unused_arena_objects;

        unused_arena_objects = arenaobj;

        return NULL;

    }

    arenaobj->address = (uptr)address;

 

    ++narenas_currently_allocated;

 

    // 设置pool集合相关信息

    arenaobj->freepools = NULL;  // 设置为NULL, 只有在释放一个pool的时候才有用

    /* 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);

 

    // 将pool的起始地址调整为系统页的边界

    // 申请到 256KB, 放弃了一些内存, 而将可使用的内存边界pool_address调整到了与系统页对齐

    excess = (uint)(arenaobj->address & POOL_SIZE_MASK);

    if (excess != 0) {

        —arenaobj->nfreepools;

        arenaobj->pool_address += POOL_SIZE – excess;

    }

    arenaobj->ntotalpools = arenaobj->nfreepools;

 

    return arenaobj;

}

图示: 初始化arenas数组, 初始化后的所有arena都在unused_arena_objects单链表里面

图示: 从arenas取一个arena进行初始化

没有可用的arena?

此时

    // 判断成立

    if (unused_arena_objects == NULL) {

        ….

        // 确定需要申请的个数, 首次初始化, 16, 之后每次翻倍

        numarenas = maxarenas ? maxarenas << 1 : INITIAL_ARENA_OBJECTS;

然后, 假设第一次分配了16个, 发现没有arena之后, 第二次处理结果: numarenas = 32

即, 数组扩大了一倍

arena分配

new了一个全新的 arena之后,

void *

  PyObject_Malloc(size_t nbytes)

  {

            // 刚开始没有可用的arena

            if (usable_arenas == NULL) {

              // new一个, 作为双向链表的表头

              usable_arenas = new_arena();

              if (usable_arenas == NULL) {

                  UNLOCK();

                  goto redirect;

              }

 

              usable_arenas->nextarena =

                  usable_arenas->prevarena = NULL;

 

           }

 

          …….

 

          // 从arena中获取一个pool

          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;

 

          // 更新 pool_address 向下一个节点

          usable_arenas->pool_address += POOL_SIZE;

          // 可用节点数量-1

          —usable_arenas->nfreepools;

 

}

图示: 从全新的arena中获取一个pool

假设arena是旧的, 怎么分配的pool

          pool = usable_arenas->freepools;

          if (pool != NULL) {

这个arena->freepools是何方神圣?

当arena中一整块pool被释放的时候

  void

  PyObject_Free(void *p)

  {

 

              struct arena_object* ao;

              uint nf;  /* ao->nfreepools */

 

              /* 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;

也就是说, 在pool整块被释放的时候, 会将pool加入到arena->freepools作为单链表的表头, 然后, 在从非全新arena中分配pool时, 优先从arena->freepools里面取, 如果取不到, 再从arena内存块里面获取

图示

一个arena满了之后呢

很自然, 从下一个arena中获取

  void *

  PyObject_Malloc(size_t nbytes)

  {

 

          // 当发现用完了最后一个pool!!!!!!!!!!!

          // nfreepools = 0

          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; // 更新下一个节点的prevarens

                  assert(usable_arenas->address != 0);

              }

              // 没有下一个, 此时 usable_arenas = NULL, 下次进行内存分配的时候, 就会从arenas数组中取一个

 

          }

 

  }

注意: 这里有个逻辑, 就是每分配一个pool, 就检查是不是用到了最后一个, 如果是, 需要变更usable_arenas到下一个可用的节点, 如果没有可用的, 那么下次进行内存分配的时候, 会判定从arenas数组中取一个

arena回收

内存分配和回收最小单位是block, 当一个block被回收的时候, 可能触发pool被回收, pool被回收, 将会触发arena的回收机制

四种情况

1. arena中所有pool都是闲置的(empty), arena内存释放, 返回给操作系统

2. 如果arena中之前所有的pool都是占用的(used), 现在释放了一个pool(empty), 需要将 arena加入到usable_arenas, 会加入链表表头

3. 如果arenaemptypool个数n, 则从useable_arenas开始寻找可以插入的位置. arena插入.(useable_arenas是一个有序链表, empty pool的个数, 保证empty pool数量越多, 被使用的几率越小, 最终被整体释放的机会越大)

4. 其他情况, 不对arena 进行处理

具体可以看PyObject_Free的代码

内存分配步骤

好的, 到这里, 我们已经知道了block和pool的关系(包括pool怎么管理block的), 以及arena和pool的关系(怎么从arena中拉到可用的pool)

那么, 在分析PyObject_Malloc(size_t nbytes)如何进行内存分配的时候, 我们就刨除掉这些管理代码

关注: 如何寻找得到一块可用的nbytes的block内存

其实代码那么多, 寻址得到对应的block也就这么几行代码, 其他代码都是pool没有, 找arena, 申请arena, arena没有, 找arenas, 最终的到一块pool, 初始化, 返回第一个block

如果有的情况, 用现成的

pool = usedpools[size + size];

if pool可用:

    pool 没满, 取一个block返回

    pool 满了, 从下一个pool取一个block返回

否则:

    获取arena, 从里面初始化一个pool, 拿到第一个block, 返回

从上面这个判断逻辑来看, 内存分配其实主要操作的是pool, 跟arena并不是基本的操作单元(只是用来管理pool的)

结论: 进行内存分配和销毁, 所有操作都是在pool上进行的

usedpools 是什么鬼? 其实是可用pool缓冲池, 后面说

内存池

arena 内存池的大小

取决于用户, Python提供的编译符号, 用于决定是否控制

obmalloc.c

#ifdef WITH_MEMORY_LIMITS

#ifndef SMALL_MEMORY_LIMIT

#define SMALL_MEMORY_LIMIT      (64 * 1024 * 1024)      /* 64 MB — more? */

#endif

#endif

 

#ifdef WITH_MEMORY_LIMITS

#define MAX_ARENAS              (SMALL_MEMORY_LIMIT / ARENA_SIZE)

#endif

具体使用中, python并不直接与arenas和arena打交道, 当Python申请内存时, 最基本的操作单元并不是arena, 而是pool

问题: pool中所有block的size一样, 但是在arena中, 每个pool的size都可能不一样, 那么最终这些pool是怎么维护的? 怎么根据大小找到需要的block所在的pool? => usedpools

pool在内存池中的三种状态

1. used状态pool中至少有一个block已经被使用, 并且至少有一个block未被使用. 这种状态的pool受控于Python内部维护的usedpool数组

 

2. full状态pool中所有的block都已经被使用, 这种状态的poolarena, 但不在arenafreepools链表中

处于fullpool各自独立, 不会被链表维护起来

 

3. empty状态pool中所有block都未被使用, 处于这个状态的pool的集合通过其pool_header中的nextpool构成一个链表, 链表的表头是arena_object中的freepools

usedpools

usedpools数组: 维护着所有处于used状态的pool, 当申请内存的时候, 会通过usedpools寻找到一块可用的(处于used状态的)pool, 从中分配一个block

结构:

  #define SMALL_REQUEST_THRESHOLD 512

  // 512/8 = 64

  #define NB_SMALL_SIZE_CLASSES   (SMALL_REQUEST_THRESHOLD / ALIGNMENT)

 

  #define PTA(x)  ((poolp )((uchar *)&(usedpools[2*(x)]) – 2*sizeof(block *)))

  #define PT(x)   PTA(x), PTA(x)

 

  // 2 * ((64 + 7) / 8) * 8 = 128, 大小为128的数组

  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数组

static poolp usedpools[128] = {

   PTA(0), PTA(0), PTA(1), PTA(1), PTA(2), PTA(2), PTA(3), PTA(3),

   ….

   PTA(63), PTA(63)

}


解开看(obmalloc.c)

  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      */

  };

  typedef struct pool_header *poolp;

  usedpools[0] = PTA(0) = ((poolp )((uchar *)

为了看懂这步的trick, 心好累>_

直接上图

new一个pool时维护

init获得的情况, 其实就是将刚刚从arena中获取的pool加入到 usedpools 对应的双向链表中, 然后初始化, 然后返回block

         init_pool:

              /* Frontlink to used pools. */

 

              // 1. 获取得到usedpools链表头

              next = usedpools[size + size]; /* == prev */

 

              // 2. 将新的pool加入到双向链表

              pool->nextpool = next;

              pool->prevpool = next;

              next->nextpool = pool;

              next->prevpool = pool;

              pool->ref.count = 1;

 

              // 3. 后面的是具体pool和block的了

              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 maxnextoffset = POOL_SIZE – size;

              pool->freeblock = bp + size;

              *(block **)(pool->freeblock) = NULL;

              UNLOCK();

              return (void *)bp;   // here

          }

从现有pool中获取block

从现有的pool, 其实就是 usedpools得到双向链表头部, 判断是不是空链表, 不是的话代表有可用的pool, 直接从里面获取

全局结构

先这样吧, Python中整个内存池基本结构和机制大概如此, 是不是发现有好多数组/链表等等, 在分配/回收上处理下做成各种池…..

后面还有内存相关的就是垃圾收集了, 后面再说了吧

一个有大大梦想但是没有支撑这梦想的技术的攻城狮,大家就当这个博客是你的技术工具箱吧,我会吧我工作中遇到的问题贴在这,大家需要的记得把我放到收藏夹哦! 百度输入“子傲代码”就可以了

—— 陈子傲

admin
众说纷纭Comments
大眼 可爱 大笑 坏笑 害羞 发怒 折磨 快哭了 大哭 白眼 晕 流汗 困 腼腆 惊讶 憨笑 色 得意 骷髅 囧 睡觉 眨眼 亲亲 疑问 闭嘴 难过 淡定 抗议 鄙视 猪头
小提示:直接粘贴图片到输入框试试
努力发送中...
footer logo
未经许可请勿自行使用、转载、修改、复制、发行、出售、发表或以其它方式利用本网站之内容
Copyright ©ziao design Studio All Rights Reserved.沪ICP备14052271号-3