nedmalloc结构分析

矫情吗；* 2022-08-07 03:52 154阅读 0赞

##  ##

## 【内存池】nedmalloc结构分析 ##

(2011-06-11 11:09:02)

![sg_trans.gif][]转载*▼*

nedmalloc是一个跨平台的高性能多线程内存分配库，很多库都使用它，例如:OGRE.现在我们来看看nedmalloc的实现(以WIN32部分为例)  
     
位操作小技巧；  
（1）、获取最低位的出现位置的掩码；x&(-x)  
 （2） 、判断值为2的幂：x& (x-1) == 0  
 （3） 、获取从最低的值为1的位开始到左边MSB的掩码:x | (-x)  
 （4） 、字节对齐；(x+ 2^m) &( 2^m -1)  
  
nedmalloc设计的数据结构和使用方法有几个有趣的地方：  
1、从操作系统得到的内存后分了3层，内存块=>简单内存描述结构(数据节点)=>内存数据节点链(面向开发者)  
2、内存块处理流程：  
 创建线程共享内存池(多个线程通过这个“池”来向系统申请/复用内存，这里需要互斥)  
      |-->释放内存时将内存放到各线程自己的数据结构中（TLS），对于小块内存用简单数组链表来保存，  
          对于大块的内存就用过“树”来保存（设计上应该是考虑小块的内存使用频率较高，简单链表访问  
          时间相对快）    
 线程请求内存时，首先从线程自己维护的空闲内存查找，然后再从线程内存池中查找。  
  
3、内存是按照"块"对齐的形式分配的，而且用户得到的可用内存是真正内存块的"一部分"，由于块的大小是对齐的，表示块大小的字节的最低3位用于表示块的使用标志。  
  
========================================================  
  
  现在我们具体看看Win32平台下nedmalloc：  
1、分配流程  
  nedpmalloc(nedpool \*p, size\_t size)  
     |  
  从线程的独立数据中查询空闲的内存  
  GetThreadCache(&p, &threadcache,&mymspace, &size)  
     |   |------>检查申请大小，如果小于sizeof(threadcacheblk)，用sizeof(threadcacheblk)代替  
     |   |       因为在该块内存"释放"时需要放到空闲链表中，注意threadcacheblk的内存布局和malloc\_chunk  
     |   |       是一样的，虽然它们的含义有区别。  
     |   |               |  
     |   |       对于首次调用来说，需要初始化全局内存池  
     |   |       InitPool(&syspool, 0, -1)  
     |   |            |--------->检查全局参数并初始化ensure\_initialization  
     |   |                       初始化内存池的锁和设置TLS  
     |   |                       INITIAL\_LOCK(&p->mutex)  
     |   |                       TlsAlloc(syspool->mycache)  
     |   |                             |  
     |   |                       创建线程池的空间  
     |   |                       create\_mspace(capacity, 1)  
     |   |                             |  
     |   |                    计算"实际"分配的大小：  
     |   |     capacity + pad\_request(sizeof(struct malloc\_state)) + \{align\_offset(chunk2mem(0))  
     |   |    pad\_request(sizeof(struct malloc\_segment)) + ((MCHUNK\_SIZE +CHUNK\_ALIGN\_MASK) &  
     |   |     ~CHUNK\_ALIGN\_MASK)\}  
     |   |                         
     |   | 从大小的计算可以知道，在没有被"外部接口"使用时，至少会包含malloc\_state结构和malloc\_segment  
     |    |  结构， 这里多个数据结构都是分别计算块对齐的（这里分结构对齐的目的一方面为了访问结构的时候可  
     |    |  以从块对 齐的位置开始，这样在存储的时候会快一些，但最主要的是为了使地址低位的bit"空闲"，用于       |   |  表 示其他的含义）  
     |   |                             |  
     |   |                  初始化malloc\_state结构  
     |   |                  init\_user\_mstate(tbase, tsize)  
     |   |                             ||  
     |   |                 这个函数中需要注意几个细节：  
     |    |          （1）指针计算：  
     |   |                  mchunkptr msp = align\_as\_chunk(tbase);

|   |               计算对齐偏移，align\_as\_chunk中会 有 chunk2mem的 调用。

|   |                  mstate m = (mstate)(chunk2mem(msp));

|    |                   志位的。  
     |   |---->分配线程缓存AllocCache(nedpool\* p)  
     |              |-->分配新的threadcache结构  
     |              tc=p->caches\[n\]=(threadcache \*)mspace\_calloc(p->m\[0\], 1,sizeof(threadcache))  
     |              mspace\_malloc(此函数中的逻辑分支较多，需要结合内存释放来分析，后面我们再详细看)，由于  
     |              threadcache比较小，  
     |              所以这里大小会调整为MIN\_CHUNK\_SIZE，并且内存会在malloc\_state的top中分配  
     |                   size\_t rsize = ms->topsize -=nb;  
     |                     mchunkptr p = ms->top;  
     |                     mchunkptr r = ms->top = chunk\_plus\_offset(p,nb);  
     |                     r->head = rsize | PINUSE\_BIT;  
     |                          |  
     |                          |  
     |             初始化thread\_cache，并设置线程的TLS  
     |         TlsSetValue(p->mycache, (void \*)(size\_t)(n+1))   
     |         需要注意的是：这里用的值是n+1，另外tc->mymspace =tc->threadid % end(这里求余实际上是为了减少碰撞)  
     |          (事实上thread\_cache结构是用于维护内存申请者内存块信息的中间结构)  
如果返回的内存缓存thread\_cache结构有效，而且调整后的大小，那么请求的内存从cache中分配threadcache\_malloc(p,tc, &size)  
     |   |-->分配内存的时候是按照块对齐的(8,16,20...)字节，所以这里首先计算能满足用户需求的最小的块大小  
     |     (threadcache有一个在使用上和malloc\_state的smallbins非常相似的结构设计成员bins,它是threadcacheblk的指  
     |      针数组，但是在使用上，它们有所不同)  
     |           |  
     |     获取对应块大小对齐的指针binsptr=&tc->bins\[idx\*2\](这里是对指针数组成员取了地址),如果当前的链表信息为  
     |    空，或者空间不足，那么检查下一个块，这里只检查下一个大小的块，是为了减少损失的内存使用。如果得  
     |     到的块非空，那么将当前的块从链表中分离出来返回（这里每个链包含两个指针，应该是首，尾指针）  
     |  
 如果从线程各自的缓存中分配失败，那么就从malloc\_state中分配  
  mstatepms = GetMSpace(p, &tc, mymspace,size)  
     |           |->根据myspace获取malloc\_state(注意，获取的malloc\_state并不一定是当前线程创建的)，  
     |              如果该malloc\_state不能锁定，那么历遍其他的malloc\_state看能否锁定，如果失败，只要没有超过内  
     |              存池允许的上限， 那么创建一个。这里有个细节  
     |              if(tc)  
     |                 tc->mymspace=n;  
     |             else  
     |             \{   
     |                 if(TLSSET(p->mycache, (void \*)(size\_t)(-(n+1))))abort();  
     |             \}  
     |             如果在首次初始化线程缓存thread\_cache的时候失败，TLS的值将会是-1,而后面会到达GetMSpace，假  
     |             设这时候创建成功，那么TLS会变成-2,这样在下次GetThreadCache的时候会重新myspace为1，这样它  
     |             不会进行Allocache的调用;如果这时创建失败，那么会等待上一次使用的malloc\_state空闲，这是TLS会  
     |             保持-1, 最后会将myspace设置为0。  
 在获取的malloc\_state上分配空间mspace\_malloc(pms, size)  
    
    
2、内存释放流程  
 nedpfree(nedpool \*p, void\* mem)  
    |  
 计算当前线程使用的cache信息  
 GetThreadCache(&p, &tc,&mymspace,0)(线程对应的cache确定(分配成功)后是不会改变的)  
    |  
 如果内存块比较小，而且thread\_cache成功，那么将内存块放到cache中  
 threadcache\_free(p, tc, mymspace, mem, memsize)  
        |->将mem转变为threadcacheblk\*,并根据mem对应内存块的实际大小（申请者使用的部分只是  
           真实内存块的一部分）链入到thread\_cache的bin成员中（有需要的话调整首尾指针）  
           如果cache中的内存块总大小超过特定上限时将cache中的内存返回到malloc\_state中  
           ReleaseFreeInCache->根据加入到cache的先后顺序将threadcacheblk释放到malloc\_state  
                |  
           RemoveCacheEntries->从cache的尾指针开始历遍threadcacheblk链，将"时间"过长的块释放  
           mspace\_free(0, f)  
                |--->获取malloc\_state   
                  这里需要先描述一下malloc\_trunk结构的含义：  
                  struct malloc\_chunk \{   
                     size\_t              prev\_foot;   
                     size\_t              head;        
                     struct malloc\_chunk\*fd;          
                     struct malloc\_chunk\* bk;  
                   \};  
                  如果当前malloc\_chunk被使用，那么下一个malloc\_chunk的head的pinuse位会被置位，而且它（下一个  
                  chunk）的prev\_foot = malloc\_state ^ mparams.magic.如果当前块未被使用，那么它（当前块）的  
                  prev\_foot是上一个块的大小，而且下一个块的pinuse不会被置位，而且它（下一个chunk）的prev\_foot表  
                  示上一块的大小。                      
                   （prev\_foot的最低位是用于表示该块是否为操作系统的真正分配的内存）  
                     
                   根据malloc\_chunk的状态进行不同的"释放"处理:  
                   i.如果当前块是从操作系统中分配，那么返还给操作系统HeapFree  
                   ii.\[向前合并\]如果当前块的前一块空闲，那么将这两块（不可能同时出现3块同时空闲，而且但前块在最  
                      后一块"FFN"）一起处理  
                      a.如果首块地址不同于malloc\_state的dv(它的作用是保存连续空间中中间释放的连续块，对于先申请  
                         先释放的应用来说，这种处理方式会有好处，因为在分配的时候会先检查dv是否能满足需求),那么  
                         根据块的大小分别是"存放"到不同的地方等待复用unlink\_chunk  
                      b.如果下一块正在被使用，那么修改下一块的prev\_foot和pinuse标志位  
                   iii.\[向后合并\]如果下一个块空闲，那么将当前块和下一块合并处理  
                      a.如果下一个块已经是top(末尾的空闲块)，那么更新top的指向（扩容）  
                      b.如果下一个块是dv，那么将当前块合并到dv中  
                      c.如果都不是，那么简单地释放下一个块，并修改下一块地prev\_foot,pinuse  
                        unlink\_chunk(fm, next, nsize);  
                        set\_size\_and\_pinuse\_of\_free\_chunk(p, psize);  
                   iv.如果下一块正在使用，那么简单修改下一块的标志set\_free\_with\_pinuse(p, psize,next)  
                     
                   对于没有合并到"空闲"空间中的块，根据块的大小，挂接到不同的链表(树)中  
                   if (is\_small(psize)) \{   
                      insert\_small\_chunk(fm, p, psize);  
                   \}  
                   else \{   
                      tchunkptr tp = (tchunkptr)p;  
                      insert\_large\_chunk(fm, tp, psize);  
                   \}  
                     
                   这里需要补充一下malloc\_state的smallbins成员的使用：  
                   所有"释放"到malloc\_state的空闲内存块会连成双向链表，而smallbins中pref\_foot和head是不直接使用  
                   的，smallbins的大小是为了访问fd和bk两个指针而设计的。smallbins实际上是将链表中按照内存块的的  
                   大小分段保存链表的指针，方便在分配时查找。  
                   (理解了这个，那么insert\_small\_chunk的处理流程就比较简单了)  
                     
                   现在看看比较大的内存块的处理思想：  
                   "大块"内存的"释放"是放到"树中的，树的结构根据内存块的大小(256为单位)按照类似"哈夫曼"编码的的  
             形式划分到二叉树中，树的每个节点是一个双向链表，保存了大小相同的块的指针。（思路清楚了，加  
             入、删除节点的代码比较容易理解，这里不再展开）需要注意的是这里malloc\_stat的treebins成员保存的是  
             树（块区域大小）的开始指针（很简单的使用方式），它的用法和smallbins的"似结构体非结构体"的特殊用  
             法不同。                      
     
3、扩展分配nedprealloc函数  
    这个函数是nedpmalloc -> memcpy ->nedpfree的组合，这里不展开了，需要注意的是，如果新申请的空间比原来的空间小，那么是直接返回原来的空间的。       
  
 现在，我们再看看内存分配最终的入口mspace\_malloc的实现（对着mspace\_free来看，比较容易理解）  
4、内存分配逻辑  
   mspace\_malloc  
       |  
   i.如果请求的块小于MAX\_SMALL\_REQUEST，首先尝试在smallbins中分配  
     b = smallbin\_at(ms, idx);  
     p = b->fd;  
     unlink\_first\_small\_chunk(ms, b, p, idx);  
     set\_inuse\_and\_pinuse(ms, p,small\_index2size(idx));  
     注意，为了提高重用成功率，这里允许使用使用比实际请求大小大一阶（下一个块对齐大小）的块  
         |(如果分配不成功)  
     如果请求的块大于malloc\_state的dvsize（上一个空洞块留下的空隙）:  
       i.smallbin非空，那么在smallbin中分配后检查是否可以替换原来的dv块  
           if (SIZE\_T\_SIZE != 4 && rsize< MIN\_CHUNK\_SIZE)\{...\}  
           else\{... replace\_dv(ms, r, rsize);\}  
       ii.从treebin中分配tmalloc\_small()  
                              |  
                    根据请求大小计算树的根(开始查找最小匹配块的根)  
                    compute\_bit2idx(leastbit, i);  
                    v = t = \*treebin\_at(m, i);  
                              |  
                    查找最小的匹配块while ((t = leftmost\_child(t)) != 0)\{...\}  
                    并将分配后留下的空闲块设置到dv中  
                    unlink\_large\_chunk(m, v);  
                    replace\_dv(m, r, rsize);  
  ii.如果申请大小大于MAX\_REQUEST,实际上会失败  
  iii.计算块对齐大小pad\_request(bytes)，并从树中分配  
       tmalloc\_large(ms, nb)  
          |  
       tmalloc\_large和tmalloc\_small的主要不同是：  
       a.tmalloc\_large首先根据大小计算"最接近"的节点，并从该节点开始计算"最小的"满足需求的节点  
       b.如果"最接近节点"为空，tmalloc\_large允许扩展一阶大小来寻找"最小的"满足需求大的节点  
       (结合malloc\_tree\_chunk和块的组织方式，代码比较容易理解)  
         
  iv.如果请求大小小于dvsize，那么从dv中分配  
     mchunkptr p = ms->dv;  
     mchunkptr r = ms->dv = chunk\_plus\_offset(p,nb);  
     ms->dvsize = rsize;  
  v.如果请求大小小于topsize，那么从malloc\_state的top块中分配  
  vi.从系统空间中分配sys\_alloc(ms, nb);  
     sys\_alloc兼容了多个平台分配机制，通过不同宏来开关对应的代码段，对于Win32来说，最终会调用HeapAlloc  
     sys\_alloc流程：  
     按照块对齐和附加内存管理结构（如malloc\_state）计算内存块的大小  
     \-->不同平台下使用不同的系统函数分配"物理内存"(系统内存)，并将得到的内存  
            |(这里主要不同宏控制的代码，比较简单，不展开了)  
            |  
     如果malloc\_state不含有真正的可用内存（top为空），那么初始化它init\_bins,init\_top  
     如果malloc\_state已经初始化，那么检查是否可以将top中剩下的空间合并到新分配的空间中（只有在可连续分配扩展的  
     情况下才有效），并重新初始化init\_top, 这里合并分了两种情况：  
       a.新分配的块在某个分快后，并和前一个分块在地址空间上相连，而且前一分块空间包含top  
         while (sp != 0 && tbase !=sp->base + sp->size)  
           sp = (NO\_SEGMENT\_TRAVERSAL) ? 0 :sp->next;  
         segment\_holds(sp, m->top)  
       b.某一个现有的分快紧接着新分配的块，这时需要将原来的块合并到新分配的块prepend\_alloc  
       c.a和b都不满足的情况下，将新块加入到块链表add\_segment(m, tbase, tsize,mmap\_flag)，并重新设置top  
         |  
         |  
      从top中分配内存  
        
    
  好了，现在我们对nedmalloc的处理思想和算法实现都比较清楚了(在\*nix平台下还有一些细节这里没有列处理，可以查看代码),下面概括一下：  
   1、使用连续的内存分段思想管理大片的连续内存  
   2、从1的内存块中以块对齐方式分配内存，小的内存分块放到线程的TLS指定的cache双向链表中，大的分块放到树结构中  
   3、树结构是以类似哈夫曼编码的方式组织的（以块大小编码），每个内部节点是一个双向链表  
     4、外部内存申请：threadcache->线程公用内存池;释放：线程cache链表->内存节点树

[sg_trans.gif]: /images/20220805/3a3243ce06894daa82b3cb2489f7e09e.png