您的位置: 首页  >  文章  >  Python源码阅读-内存管理机制（二）

Python源码阅读-内存管理机制（二）

分类: 文章 • 2024-04-02 20:08:53

arena

arena: 多个pool聚合的结果

arena size

pool的大小默认值位4KB

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

obmalloc.c中代码

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

arena 结构

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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
2
3
1. 与其他arena连接, 组成双向链表
2. 维护arena中可用的pool, 单链表
3. 其他信息

pool_header 与 arena_object

1
2
pool_header和管理的blocks内存是一块连续的内存 => pool_header被申请时, 其管理的block集合的内存一并被申请
arena_object和其管理的内存是分离的 => arena_object被申请时, 其管理的pool集合的内存没有被申请, 而是在某一时刻建立的联系

Python源码阅读-内存管理机制（二）

arena的两种状态

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

全局由两个链表维护着

1
2
3
4
5
6
7
8
9
10
11
/* 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/* 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初始化的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
/* 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单链表里面

Python源码阅读-内存管理机制（二）

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

Python源码阅读-内存管理机制（二）

没有可用的arena?

此时

1
2
3
4
5
    // 判断成立
    if (unused_arena_objects == NULL) {
        ....
        // 确定需要申请的个数, 首次初始化, 16, 之后每次翻倍
        numarenas = maxarenas ? maxarenas << 1 : INITIAL_ARENA_OBJECTS;

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

即, 数组扩大了一倍

arena分配

new了一个全新的 arena之后,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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

Python源码阅读-内存管理机制（二）

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

1
2
          pool = usable_arenas->freepools;
          if (pool != NULL) {

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
  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内存块里面获取

图示

Python源码阅读-内存管理机制（二）

一个arena满了之后呢

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
  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
2
3
4
1. arena中所有pool都是闲置的(empty), 将arena内存释放, 返回给操作系统
2. 如果arena中之前所有的pool都是占用的(used), 现在释放了一个pool(empty), 需要将 arena加入到usable_arenas, 会加入链表表头
3. 如果arena中empty的pool个数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

如果有的情况, 用现成的

1
2
3
4
5
6
pool = usedpools[size + size];
if pool可用:
    pool 没满, 取一个block返回
    pool 满了, 从下一个pool取一个block返回
否则:
    获取arena, 从里面初始化一个pool, 拿到第一个block, 返回

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

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

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

内存池

arena 内存池的大小

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

obmalloc.c

1
2
3
4
5
6
7
8
9
#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
2
3
4
5
6
1. used状态: pool中至少有一个block已经被使用, 并且至少有一个block未被使用. 这种状态的pool受控于Python内部维护的usedpool数组
 
2. full状态: pool中所有的block都已经被使用, 这种状态的pool在arena中, 但不在arena的freepools链表中
处于full的pool各自独立, 不会被链表维护起来
 
3. empty状态: pool中所有block都未被使用, 处于这个状态的pool的集合通过其pool_header中的nextpool构成一个链表, 链表的表头是arena_object中的freepools

usedpools

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

结构:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
  #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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
  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, 心好累>_

直接上图

Python源码阅读-内存管理机制（二）

new一个pool时维护

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
         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, 直接从里面获取

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
      if ((nbytes - 1) > ALIGNMENT_SHIFT;
          pool = usedpools[size + size];
 
          // 注意这里的判断, pool != pool-> nextpool 表示得到的链表不是空的
          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);
              if ((pool->freeblock = *(block **)bp) != NULL) {
                  UNLOCK();
                  return (void *)bp;
              }
              /*
               * Reached the end of the free list, try to extend it.
               */
              if (pool->nextoffset maxnextoffset) {
                  /* There is room for another block. */
                  pool->freeblock = (block*)pool +
                                    pool->nextoffset;
                  pool->nextoffset += INDEX2SIZE(size);
                  *(block **)(pool->freeblock) = NULL;
                  UNLOCK();
                  return (void *)bp;
              }
              /* Pool is full, unlink from used pools. */
              next = pool->nextpool;
              pool = pool->prevpool;
              next->prevpool = pool;
              pool->nextpool = next;
              UNLOCK();
              return (void *)bp;   // here
          }

全局结构

Python源码阅读-内存管理机制（二）

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

相关推荐