作者簡(jiǎn)介

順剛(網(wǎng)名:沐多)，一線碼農(nóng)，從事工控行業(yè)，目前在一家工業(yè)自動(dòng)化公司從事工業(yè)實(shí)時(shí)現(xiàn)場(chǎng)總線開發(fā)工作，喜歡鉆研Linux內(nèi)核及xenomai，個(gè)人博客 wsg1100，歡迎大家關(guān)注！

目錄

• xenomai內(nèi)存池管理

• 1.xnheap

• 2. xnpagemap

• 3. xnbucket

• 4. xnheap初始化

• 5. 內(nèi)存塊分配

• 5.1 小內(nèi)存分配流程(<= 2*PAGE_ZISE)

• 1.分配1Byte

• 2.分配50Byte

• 3.分配1000 Byte

• 4. 分配5000字節(jié)

• 5.2 大內(nèi)存分配（> 2*PAGE_ZISE）

• 1. 分配10000字節(jié)

• 6. 內(nèi)存釋放

• 頁(yè)內(nèi)塊釋放

• 頁(yè)連續(xù)的塊釋放

• 7. 總結(jié)

本文分析的xenomai系統(tǒng)中的內(nèi)存池(xnheap)管理機(jī)制。

xenomai內(nèi)存池管理

通常，操作系統(tǒng)的內(nèi)存管理，內(nèi)存分配算法一定要快，否則會(huì)影響應(yīng)用程序的運(yùn)行效率，其次是內(nèi)存利用率要高。

但對(duì)于硬實(shí)時(shí)操作系統(tǒng)，首先要保證實(shí)時(shí)性，即確定性，不同內(nèi)存大小的分配釋放時(shí)間必須是確定的，同時(shí)也要快。

無(wú)論linux還是xenomai，內(nèi)核在服務(wù)或管理應(yīng)用程序過(guò)程中經(jīng)常需要內(nèi)存分配，通常linux內(nèi)存的分配與釋放都是時(shí)間不確定的，例如，惰性分配導(dǎo)致的缺頁(yè)異常、頁(yè)面換出和OOM會(huì)導(dǎo)致大且不可預(yù)測(cè)的延遲，不適用于受嚴(yán)格時(shí)間限制的實(shí)時(shí)應(yīng)用程序。

xenomai作為硬實(shí)時(shí)內(nèi)核，不能使用linux這樣的內(nèi)存分配釋放接口，為此xenomai采取的措施是：

• 在內(nèi)核態(tài)，在xenomai內(nèi)核初始化時(shí)，先調(diào)用__vmalloc()從linux管理的ZONE_NORMAL中分配 一片內(nèi)存,然后由xenomai自己來(lái)管理這片內(nèi)存，且xenomai提供的內(nèi)存分配釋放時(shí)間確定的，這樣就不會(huì)因?yàn)閮?nèi)存的分配釋放影響實(shí)時(shí)性（該內(nèi)存管理代碼量非常少，有效代碼數(shù)3百行左右，實(shí)現(xiàn)精巧，值得研究利用）。

• 在用戶態(tài)，glibc的內(nèi)存管理不具有時(shí)間確定性，RT應(yīng)用只能在程序初始化時(shí)分配并訪問(wèn)（避免運(yùn)行中產(chǎn)生pagefault)，運(yùn)行中不能使用，否則會(huì)嚴(yán)重影響實(shí)時(shí)性。為此xenomai實(shí)時(shí)應(yīng)用庫(kù)libcobalt為RT應(yīng)用實(shí)現(xiàn)了時(shí)間確定的內(nèi)存動(dòng)態(tài)分配釋放heap，供實(shí)時(shí)任務(wù)運(yùn)行中分配內(nèi)存，使用方法參見Heap management services，其內(nèi)存管理分配釋放算法與內(nèi)核里的差不多，不在贅述，下面開始。

下面代碼基于 xenomai-3.0.8。xenomai 3.1開始有所不同詳見文末。

1.xnheap

xenomai管理的內(nèi)存池稱為xnheap，內(nèi)存池大小預(yù)先配置，如xenomai的系統(tǒng)內(nèi)存池cobaltheap，負(fù)責(zé)內(nèi)核大多內(nèi)核數(shù)據(jù)分配，其大小為 sysheap_size_arg*1024 Byte（sysheapsizearg KB），sysheapsize_arg可在內(nèi)核配置時(shí)設(shè)置，或者通過(guò)內(nèi)核參數(shù) xenomai.sysheap_size=配置。xenomai內(nèi)核中這樣管理的內(nèi)存池不止一個(gè)，其他的 make menuconfig配置如下。

[*] Xenomai/cobalt  --->      Sizes and static limits  --->          (512) Number of registry slots                                             (4096) Size of system heap (Kb)           (512) Size of private heap (Kb) (512)Sizeofsharedheap(Kb)

簡(jiǎn)單介紹一下配置項(xiàng)中的幾個(gè)內(nèi)存池的用途：

• (512)Numberof registry slots，xenomai內(nèi)核運(yùn)行中內(nèi)核資源對(duì)象存儲(chǔ)槽的大小，用于分配系統(tǒng)使用資源的最大大小，如信號(hào)(signal)、互斥對(duì)象(mutex)、信號(hào)量等.

• (4096)Sizeof system heap(Kb)系統(tǒng)內(nèi)存池，用于cobalt內(nèi)核工作過(guò)程中動(dòng)態(tài)內(nèi)存分配，內(nèi)核中很多任務(wù)共享的內(nèi)存會(huì)從該區(qū)域分配,例如XDDP通訊時(shí)數(shù)據(jù)緩沖區(qū)默認(rèn)從該區(qū)域分配。

• (512)Sizeofprivateheap(Kb)每個(gè)Cobalt任務(wù)私有的內(nèi)存池，在實(shí)時(shí)任務(wù)創(chuàng)建時(shí)，從linux分配內(nèi)存并初始化，位于Cobalt任務(wù)調(diào)度實(shí)體cobalt_process中,當(dāng)實(shí)時(shí)任務(wù)內(nèi)核上下文需要分配內(nèi)存時(shí)，就會(huì)從該區(qū)域中獲取，XDDP 通訊中可選從該內(nèi)存區(qū)分配緩沖區(qū)。

本節(jié)以xenomai的系統(tǒng)內(nèi)存池cobaltheap為例來(lái)了解xenomai內(nèi)存池管理。cobaltheap在xenomai內(nèi)核初始化過(guò)程中初始化，先調(diào)用_vmalloc()從linux管理的ZONENORMAL中分配，然后在調(diào)用xnheap_init()初始化。

static int __init xenomai_init(void){  ......  ret = sys_init();  ......  return ret;}
static __init int sys_init(void){
  void *heapaddr;  int ret, cpu;  heapaddr = xnheap_vmalloc(sysheap_size_arg * 1024);/*256 * 1024*/  if (heapaddr == NULL ||      xnheap_init(&cobalt_heap, heapaddr, sysheap_size_arg * 1024)) {/*初始heap*/    return -ENOMEM;  }  xnheap_set_name(&cobalt_heap, "system heap");/*set heap name */  ....  return 0;}

xenomai要求管理的內(nèi)存大小必須是PAGESIZE的倍數(shù)，且至少有2頁(yè)，其最大值在xenomai3.0.8版本里為2GB(1<<31),其他版本可能有所改變。以sysheapsizearg默認(rèn)值256為例，即cobaltheap大小256KB。

每個(gè)內(nèi)存池分配一個(gè)對(duì)象xnheap來(lái)管理，xnheap結(jié)構(gòu)如下。

struct xnpagemap {  /** PFREE, PCONT, PLIST or log2 */  u32 type : 8;  /** Number of active blocks */  u32 bcount : 24;};struct xnheap {  /** SMP lock */  DECLARE_XNLOCK(lock);  /** Base address of the page array */  caddr_t membase;  /** Memory limit of page array */  caddr_t memlim;  /** Number of pages in the freelist */  int npages;  /** Head of the free page list  */  caddr_t freelist;  /** Address of the page map */  struct xnpagemap *pagemap;  /** Link to heapq */  struct list_head next;  /** log2 bucket list */  struct xnbucket {    caddr_t freelist;    int fcount;  } buckets[XNHEAP_NBUCKETS];  char name[XNOBJECT_NAME_LEN];  /** Size of storage area */  u32 size;  /** Used/busy storage size */  u32 used;};

其中， size標(biāo)志該內(nèi)存池的總大小， used標(biāo)志已分配使用大小， npages表示該內(nèi)存有多少頁(yè)， membase管理的內(nèi)存基地址, memlim記錄內(nèi)存結(jié)束地址.

2. xnpagemap

struct xnpagemap {  /** PFREE, PCONT, PLIST or log2 */  u32 type : 8;  /** Number of active blocks */  u32 bcount : 24;};

pagemap管理著每一頁(yè)，有多少頁(yè)就需要多少項(xiàng), pagemap.type表示該頁(yè)面的類型， pagemap.bcount表示頁(yè)面被分成這類大小的數(shù)量，小于1頁(yè)分配才會(huì)將空閑頁(yè)n分割成多塊，才需要 pagemap[n]來(lái)記錄, pagemap通常管理著小于PAGE_SIZE的分配。pagemap.type有如下幾類：

• XNHEAP_PFREE(0) 表示該頁(yè)面空閑

• XNHEAP_PCONT(1)該頁(yè)為上一頁(yè)的續(xù)，當(dāng)分配的內(nèi)存大于1頁(yè)時(shí)，除首頁(yè)之外的頁(yè)用該標(biāo)識(shí)。

• XNHEAP_PLIST(2) 表示該頁(yè)是塊的開始（每次請(qǐng)求分配的內(nèi)存稱為一個(gè)塊）

• 記錄確切的子塊大小($log_2size$)，值為3-20，（頁(yè)按size大小分割成許多子塊）；

3. xnbucket

  struct xnbucket {    caddr_t freelist;    int fcount;}buckets[XNHEAP_NBUCKETS];

buckets[XNHEAP_NBUCKETS]記錄著整個(gè)xnheap不同大小的分配，因?yàn)閎ucket管理的內(nèi)存分配單元大小最小為8Byte，所以數(shù)組下標(biāo)是log_2size -3，bucket[n]管理著分配單元（塊）大小為2^{n+3}Byte的內(nèi)存池， freelist指向該bucket內(nèi)第一個(gè)空閑塊， fcount標(biāo)識(shí)該bucket可剩余空閑塊數(shù)。

例如請(qǐng)求分配的大小為64Byte，log_264 -3 = 3，則buckets[3]記錄著請(qǐng)求大小64Byte的分配，如果 buckets[3].freelist不為NULL，則 buckets[3].freelist就是本次請(qǐng)求的內(nèi)存首地址。

并不是任何大小的分配都由buckets[]管理。當(dāng)請(qǐng)求大小超過(guò)兩個(gè)頁(yè)時(shí)，不再使用bucket，從空閑頁(yè)列表直接分配頁(yè)面會(huì)更節(jié)省空間。XNHEAP_NBUCKETS=21，表示最大管理8MB(2^{20+3})分配信息，普通分頁(yè)模式下，頁(yè)大小為4KB，只用到 buckets[0-10]，大頁(yè)(hupage)模式(頁(yè)大小為2MB)下才會(huì)使用到 buckets[11-20]，以下分析默認(rèn)頁(yè)大小為4KB。

buckets與pagemap區(qū)別是管理的對(duì)象不同， buckets[n]管理大小2^{n+3}Byte的內(nèi)存池的分配。而 pagemap[n]記錄整個(gè)塊內(nèi)存第n頁(yè)內(nèi)的使用信息。

4. xnheap初始化

當(dāng)分配到一片內(nèi)存作為xnheap后，首先調(diào)用xnheap_init()對(duì)該片內(nèi)存初始化。

int xnheap_init(struct xnheap *heap, void *membase, u32 size){  spl_t s;
  secondary_mode_only();
  heap->size = size;  heap->membase = membase;  heap->npages = size / XNHEAP_PAGESZ; 
  if (heap->npages < 2)     return -EINVAL;
  heap->pagemap = kmalloc(sizeof(struct xnpagemap) * heap->npages,        GFP_KERNEL);/*map 大小：每頁(yè)需要一個(gè)struct xnpagemap*/  if (heap->pagemap == NULL)    return -ENOMEM;
  xnlock_init(&heap->lock);  init_freelist(heap);
  /* Default name, override with xnheap_set_name() */  ksformat(heap->name, sizeof(heap->name), "(%p)", heap);  .....
  return 0;}

計(jì)算該內(nèi)存總頁(yè)數(shù)npages，然后為每頁(yè)分配一個(gè)xnpagemap對(duì)象，npages頁(yè)需要分配npages個(gè)xnpagemap，然后調(diào)用init_freelist()初始化freelist。

static void init_freelist(struct xnheap *heap){  caddr_t freepage;  int n, lastpgnum;
  heap->used = 0;  memset(heap->buckets, 0, sizeof(heap->buckets));  lastpgnum = heap->npages - 1;
  for (n = 0, freepage = heap->membase;       n < lastpgnum; n++, freepage += XNHEAP_PAGESZ) {    *((caddr_t *)freepage) = freepage + XNHEAP_PAGESZ;    heap->pagemap[n].type = XNHEAP_PFREE;    heap->pagemap[n].bcount = 0;  }
  *((caddr_t *) freepage) = NULL;   heap->pagemap[lastpgnum].type = XNHEAP_PFREE;  heap->pagemap[lastpgnum].bcount = 0;  heap->memlim = freepage + XNHEAP_PAGESZ;
  /* The first page starts the free list. */  heap->freelist = heap->membase;/*free list*/}

先初始化pagemap[],每頁(yè)記錄為未使用(XNHEAP_PFREE)

設(shè)置xnheap的結(jié)束地址memlim，并將freelist指向第一個(gè)空閑頁(yè)，然后從第一頁(yè)開始，前一頁(yè)保存著后一頁(yè)起始地址。這樣做不僅將空閑頁(yè)連起來(lái)，方便分配時(shí)索引，而且通過(guò)內(nèi)存賦值操作，如果該內(nèi)存頁(yè)未映射，會(huì)觸發(fā)內(nèi)核缺頁(yè)異常，讓linux將未映射到物理內(nèi)存的頁(yè)面映射到物理內(nèi)存，這樣后續(xù)xenomai使用過(guò)程中就不會(huì)再產(chǎn)生缺頁(yè)中斷，避免影響xenomai實(shí)時(shí)性。初始化后如下圖所示

5. 內(nèi)存塊分配

xenomai內(nèi)存堆初始化完后，下面通過(guò)分配與釋放來(lái)分析分配釋放過(guò)程，例如向內(nèi)存池Cobalt_heap()分別分配1Byte、50Byte、1000Byte、5000Byte、10000Byte數(shù)據(jù)，然后依次釋放。

/*向hobalt_heap分配1字節(jié)空間*/ptrt_1 = xnheap_alloc(&hobalt_heap, 1);/*向hobalt_heap分配50字節(jié)空間*/ptr_50 = xnheap_alloc(&hobalt_heap, 50);/*連續(xù)向hobalt_heap分配1000字節(jié)空間5次*/ptr_1000 = xnheap_alloc(&hobalt_heap, 1000);ptr_1000_1 = xnheap_alloc(&hobalt_heap, 1000);ptr_1000_2 = xnheap_alloc(&hobalt_heap, 1000);ptr_1000_3 = xnheap_alloc(&hobalt_heap, 1000);ptr_1000_4 = xnheap_alloc(&hobalt_heap, 1000);/*向hobalt_heap分配5000字節(jié)空間*/ptr_5000 = xnheap_alloc(&hobalt_heap, 5000);/*向hobalt_heap分配10000字節(jié)空間*/ptr_10000=xnheap_alloc(&hobalt_heap,10000);

5.1 小內(nèi)存分配流程(<= 2*PAGE_ZISE)

1.分配1Byte

首先來(lái)看分配1Byte。

/*includecobaltkernelheap.h*/#define XNHEAP_PAGESZ    PAGE_SIZE#define XNHEAP_MINLOG2    3#define XNHEAP_MAXLOG2    22  /* Holds pagemap.bcount blocks */#define XNHEAP_MINALLOCSZ (1 << XNHEAP_MINLOG2)#define XNHEAP_MINALIGNSZ (1 << 4) /* i.e. 16 bytes */#define XNHEAP_NBUCKETS   (XNHEAP_MAXLOG2 - XNHEAP_MINLOG2 + 2)#define XNHEAP_MAXHEAPSZ  (1 << 31) /* i.e. 2Gb */

void *xnheap_alloc(struct xnheap *heap, u32 size){        u32 pagenum, bsize;  int log2size, ilog;  caddr_t block;  spl_t s;.....  /*   * Sizes lower or equal to the page size are rounded either to   * the minimum allocation size if lower than this value, or to   * the minimum alignment size if greater or equal to this   * value.   */  if (size > XNHEAP_PAGESZ)    size = ALIGN(size, XNHEAP_PAGESZ);/*XNHEAP_PAGESZ = */  else if (size <= XNHEAP_MINALIGNSZ)    size = ALIGN(size, XNHEAP_MINALLOCSZ);  else    size = ALIGN(size, XNHEAP_MINALIGNSZ);  ......}

首先根據(jù)大小size來(lái)向最小分配或最大分配對(duì)齊，xenomai分配類型分為3類，對(duì)于大于XNHEAPPAGESZ的向上與XNHEAPPAGESZ對(duì)齊；對(duì)于小于8Byte的，向上與8Byte對(duì)齊；對(duì)于大于8Byte，向上與16Byte對(duì)齊；這樣是為了與bucket一一對(duì)應(yīng)。

例如分配5000Byte，最終分配到的空間大小為8192 Byte（以PAGE_SIZE為4KB計(jì)算），要分配1Byte空間，將會(huì)得到8Byte的空間，分配50Byte空間得到64Byte空間。

我們請(qǐng)求分配1Byte的內(nèi)存，對(duì)齊后size為8 Byte， buckets[XNHEAP_NBUCKETS]只管理請(qǐng)求大小小于2*PAGESZIE的分配池。當(dāng)請(qǐng)求的大小大于頁(yè)大小的2倍時(shí)，從空閑頁(yè)列表直接分配頁(yè)面會(huì)更節(jié)省空間。8Byte小于2*PAGESZIE，下面看bucket具體的分配流程。

  if (likely(size <= XNHEAP_PAGESZ * 2)) {   /*小于等于2PAGE_SIZE的從空閑鏈表中分配*/    /*     * Find the first power of two greater or equal to the     * rounded size.     */    bsize = size < XNHEAP_MINALLOCSZ ? XNHEAP_MINALLOCSZ : size;    log2size = order_base_2(bsize);    bsize = 1 << log2size;    ilog = log2size - XNHEAP_MINLOG2;     xnlock_get_irqsave(&heap->lock, s);    block = heap->buckets[ilog].freelist;    if (block == NULL) {      block = get_free_range(heap, bsize, log2size);      if (block == NULL)        goto out;      if (bsize <= XNHEAP_PAGESZ)        heap->buckets[ilog].fcount += (XNHEAP_PAGESZ >> log2size) - 1;    } else {      if (bsize <= XNHEAP_PAGESZ)          --heap->buckets[ilog].fcount;      pagenum = ((caddr_t)block - heap->membase) / XNHEAP_PAGESZ;      ++heap->pagemap[pagenum].bcount;    }    heap->buckets[ilog].freelist = *((caddr_t *)block);    heap->used += bsize;  } else {        .....}

第一步先對(duì)size求log2size，log28=3，得到bucket索引下標(biāo)ilog = log_28-3=0，再用ilog作為下標(biāo)得到管理8Byte大小池的bucket，buckets[0].freelist指向首個(gè)空閑塊，如果buckets[ilog].freelist不為NULL，則將buckets[ilog].freelist指向的塊分配出去，buckets[ilog].fcount減一，再根據(jù)freelist的地址計(jì)算該空閑塊位于第幾頁(yè)（pagenum），更新該頁(yè)的pagemap[pagenum].bcount。再將buckets[ilog].freelist指向下一個(gè)空閑頁(yè)，更新總內(nèi)存已分配大小heap->used，返回分配到的內(nèi)存地址block。

但我們內(nèi)存池剛初始化，buckets[ilog].freelist 為NULL，進(jìn)入block==NULL分支,先為該bucket分配空間。

先通過(guò)getfreerange()分配，分配后計(jì)算bucket的剩余塊數(shù)buckets[ilog].fcount，XNHEAP_PAGESZ >> log2size就是新頁(yè)面被分成了多少塊，且馬上就要被分配出去耍一塊，所以再減一。

下面看如何分配bucket管理的空間，getfreerange()中，先分配空閑頁(yè)，然后再對(duì)空閑頁(yè)進(jìn)行分塊。先看從整塊內(nèi)存找空閑頁(yè)部分

static caddr_t get_free_range(struct xnheap *heap, u32 bsize, int log2size){  caddr_t block, eblock, freepage, lastpage, headpage, freehead = NULL;  u32 pagenum, pagecont, freecont;
  freepage = heap->freelist;    /*空閑頁(yè)*/  while (freepage) {    headpage = freepage;    freecont = 0;    do {      lastpage = freepage;      freepage = *((caddr_t *) freepage);      freecont += XNHEAP_PAGESZ;    }    while (freepage == lastpage + XNHEAP_PAGESZ &&            freecont < bsize);
    if (freecont >= bsize) {      if (headpage == heap->freelist)        heap->freelist = *((caddr_t *)lastpage);      else        *((caddr_t *)freehead) = *((caddr_t *)lastpage);
      goto splitpage;    }    freehead = lastpage;  }
  return NULL;
splitpage:  ......
  return headpage;}

heap->freelist指向xnheap內(nèi)存中第一個(gè)空閑頁(yè)，10-14行循環(huán)迭代freepage并記錄大小freecont，直到得到freecont大小的空閑頁(yè)。我們傳入getfreerange()的bsize=8，log_2size= 3，所以循環(huán)1次，分配到4KB空間就夠了。如下圖所示.

條件freecont >= bsize表示分配到了滿足大小的連續(xù)空閑頁(yè)，否則就是連續(xù)內(nèi)存空間不夠，看lastpage指向的下一個(gè)空閑空間是否連續(xù)，直到分配到符合條件的內(nèi)存頁(yè)，否則無(wú)法滿足此次分配條件，返回 NULL。

我們這里分配到了頁(yè)0，20行更新heap->freelist指向下一個(gè)空閑頁(yè) 。

跳轉(zhuǎn)splitpage對(duì)頁(yè)0進(jìn)行切割。

splitpage:  if (bsize < XNHEAP_PAGESZ) {      for (block = headpage, eblock =           headpage + XNHEAP_PAGESZ - bsize; block < eblock;         block += bsize)      *((caddr_t *)block) = block + bsize;
    *((caddr_t *)eblock) = NULL;  } else    *((caddr_t *)headpage) = NULL;
  pagenum = (headpage - heap->membase) / XNHEAP_PAGESZ;  heap->pagemap[pagenum].type = log2size ? : XNHEAP_PLIST;    heap->pagemap[pagenum].bcount = 1;
  for (pagecont = bsize / XNHEAP_PAGESZ; pagecont > 1; pagecont--) {    heap->pagemap[pagenum + pagecont - 1].type = XNHEAP_PCONT;    heap->pagemap[pagenum + pagecont - 1].bcount = 0;  }

returnheadpage;

splitpage操作將一個(gè)4K大小的頁(yè)分成一個(gè)個(gè)大小為8Byte的塊，并將這些塊連起來(lái)，并更xpagemap[pagenum]的type為塊大小3(2的冪log_2blocksize），表示該頁(yè)P(yáng)LIST。bcount=1是即將分配出去的第一個(gè)塊。

回到xnheapalloc(),更新bucket內(nèi)剩余塊數(shù)heap->buckets[3].fcount、8字節(jié)池空閑地址buckets[3].freelist，整個(gè)內(nèi)存池已分配數(shù)heap->used，然后返回內(nèi)存池分配的到的內(nèi)存起始地址ptr1。此時(shí)如下：

通過(guò)以上分析，我們分配1字節(jié)空間，最終得到8字節(jié)的空間，8(1<<3)字節(jié)是xenomai內(nèi)存池的最小管理單位，并且下次再分配8Byte內(nèi)空間時(shí)，直接返回buckets[3].freelist并更新幾個(gè)成員變量即可，速度極快。

2.分配50Byte

同樣，根據(jù)以上步驟請(qǐng)求分配50字節(jié)空間時(shí)，先對(duì)50向上向上對(duì)齊得到64，計(jì)算bucket索引ilog = log_2 64-3=3，本次分配請(qǐng)求從bucket[3]管理的內(nèi)存池中分配，由于首次分配，bucket[3]中沒(méi)有還管理的空間需要先從xnheap中分配空閑頁(yè)，最終分配得到64字節(jié)大小的空間，分配后如下圖所示。

3.分配1000 Byte

請(qǐng)求分配1000字節(jié)空間時(shí)，先對(duì)1000向上對(duì)齊得到1024，計(jì)算bucket索引ilog = log_2 1024-3=7，本次分配請(qǐng)求從bucket[7]管理的內(nèi)存池中分配，由于首次分配，bucket[7]中沒(méi)有還管理的空間需要先從xnheap中分配一個(gè)空閑頁(yè)分成4塊交給bucket管理，最終本次分配得到1024字節(jié)大小的空間，分配后如下圖所示。

以上分配后，buckets[7]中還剩余3個(gè)空閑塊，如果bucket內(nèi)的所有塊分配完了，再次請(qǐng)求分配大小為1000字節(jié)的空間時(shí)會(huì)怎樣?會(huì)再去分配一頁(yè)空閑頁(yè)進(jìn)行切割。為了表示這個(gè)過(guò)程，繼續(xù)執(zhí)行以下語(yǔ)句，當(dāng)ptr10004分配后如下圖所示。

ptr_1000_1 = xnheap_alloc(&hobalt_heap, 1000);ptr_1000_2 = xnheap_alloc(&hobalt_heap, 1000);ptr_1000_3 = xnheap_alloc(&hobalt_heap, 1000);ptr_1000_4=xnheap_alloc(&hobalt_heap,1000);

當(dāng)分配ptr10003后bucket中不再由空閑塊，bucket[7].freelist重新指向NULL，分配ptr10004時(shí)就會(huì)觸發(fā)再次從總內(nèi)存分配空閑頁(yè)來(lái)分成1K大小的塊，分配ptr10004后bucket[7].freelist指向新的空閑頁(yè)。

4. 分配5000字節(jié)

由于請(qǐng)求大小是5000字節(jié)，前面說(shuō)過(guò)超過(guò)頁(yè)大小后會(huì)與頁(yè)對(duì)齊，也就是8K的空間，且該大小滿足 <=2*PAGE_SIZE,會(huì)向bucket[13]分配。

與小于頁(yè)大小（4KB）的分配不同的是，向頁(yè)對(duì)齊后8K，8K空間占用2個(gè)頁(yè)，所以圖中連續(xù)的頁(yè)5、頁(yè)5分配出去，bucket內(nèi)沒(méi)有剩余塊，頁(yè)5對(duì)應(yīng)的xnpagemap[5]的type被設(shè)置為XNHEAP_PCONT(1)表示該頁(yè)與上頁(yè)是連續(xù)的。

5.2 大內(nèi)存分配（> 2*PAGE_ZISE）

1. 分配10000字節(jié)

由于請(qǐng)求大小是10000字節(jié)，前面說(shuō)過(guò)超過(guò)頁(yè)大小后會(huì)與頁(yè)對(duì)齊，也就是12K的空間，對(duì)于大于8K（2*PAGE）SIZE）大小的分配請(qǐng)求，從空閑頁(yè)列表直接分配頁(yè)面會(huì)更節(jié)省空間。

  if (likely(size <= XNHEAP_PAGESZ * 2)) { /*小于8KB*/    ......  } else {    if (size > heap->size)      return NULL;    xnlock_get_irqsave(&heap->lock, s);
    /* Directly request a free page range. */    block = get_free_range(heap, size, 0);    if (block)      heap->used += size;}

先判斷總大小，然后調(diào)用getfreerange()直接從空閑頁(yè)列表直接分配,參數(shù)log2size=0,該情況下getfree_range()函數(shù)執(zhí)行路徑如下；

static caddr_t get_free_range(struct xnheap *heap, u32 bsize, int log2size){  caddr_t block, eblock, freepage, lastpage, headpage, freehead = NULL;  u32 pagenum, pagecont, freecont;
  freepage = heap->freelist;  while (freepage) {    headpage = freepage;    freecont = 0;        /*在空閑頁(yè)列表查找滿足條件的連續(xù)空閑頁(yè)*/    do {      lastpage = freepage;      freepage = *((caddr_t *) freepage);      freecont += XNHEAP_PAGESZ;    }    while (freepage == lastpage + XNHEAP_PAGESZ &&           freecont < bsize);
    if (freecont >= bsize) {  /*得到連續(xù)的頁(yè)*/      if (headpage == heap->freelist)        heap->freelist = *((caddr_t *)lastpage);  /*更新freelist*/      else        .....
      goto splitpage;    }    freehead = lastpage;  }
  return NULL;
splitpage:  if (bsize < XNHEAP_PAGESZ) {  //<4K    .....  } else    *((caddr_t *)headpage) = NULL;
  pagenum = (headpage - heap->membase) / XNHEAP_PAGESZ;
  heap->pagemap[pagenum].type = log2size ? : XNHEAP_PLIST;    heap->pagemap[pagenum].bcount = 1;  for (pagecont = bsize / XNHEAP_PAGESZ; pagecont > 1; pagecont--) {    heap->pagemap[pagenum + pagecont - 1].type = XNHEAP_PCONT;    heap->pagemap[pagenum + pagecont - 1].bcount = 0;  }
  return headpage;}

分配后的內(nèi)存視圖如下。

6. 內(nèi)存釋放

通過(guò)以上分析，我們可以將分配到的內(nèi)存塊分為兩類：

• 從bucket中分配，大小小于等于4KB，不僅bucket記錄著數(shù)量，該塊所在頁(yè)的pagemap[].type也記錄著該塊的大小。

• 直接從空閑列表分配，大小大于4KB，pagemap[n].type為XNHEAPPLIST（2）表示頁(yè)n是該塊的開始頁(yè)，后續(xù)的n+i頁(yè)，pagemap[n+i].type都為XNHEAPPCONT(1)。

內(nèi)存塊釋放的過(guò)程就是根據(jù)這些信息來(lái)定位要釋放的塊，并將它重新放回bucket內(nèi)存池或空閑頁(yè)列表。

通過(guò) xnheap_alloc()分配的內(nèi)存，通過(guò) xnheap_free()釋放，當(dāng)然必須是在同一個(gè)xnheap上操作。

void xnheap_free(struct xnheap *heap, void *block){  caddr_t freepage, lastpage, nextpage, tailpage, freeptr, *tailptr;  int log2size, npages, nblocks, xpage, ilog;  u32 pagenum, pagecont, boffset, bsize;  spl_t s;  xnlock_get_irqsave(&heap->lock, s);      if ((caddr_t)block < heap->membase || (caddr_t)block >= heap->memlim)    goto bad_block;
  /* Compute the heading page number in the page map. */  pagenum = ((caddr_t)block - heap->membase) / XNHEAP_PAGESZ;  boffset = ((caddr_t)block - (heap->membase + pagenum * XNHEAP_PAGESZ));
  switch (heap->pagemap[pagenum].type) {  case XNHEAP_PFREE:  /* Unallocated page? */  case XNHEAP_PCONT:  /* Not a range heading page? */bad_block:    xnlock_put_irqrestore(&heap->lock, s);    XENO_BUG(COBALT);    return;
  case XNHEAP_PLIST:    /**/    .....    break;
  default:    .......  }
  heap->used -= bsize;
  xnlock_put_irqrestore(&heap->lock, s);}

xnheap_free()中先根據(jù)地址判斷釋放的內(nèi)存塊是否屬于指定的xnheap。如果合法的，接著計(jì)算要釋放的內(nèi)存所在的頁(yè)號(hào)pagenum，以及頁(yè)內(nèi)的偏移量boffset。得到頁(yè)號(hào)后從pagemap[pagenum]判斷要釋放的內(nèi)存塊屬于那種類型，再做相應(yīng)的釋放操作。

將前面分配到的內(nèi)存按不同順序釋放，來(lái)查看xnheap的釋放流程,由于分配的1000字節(jié)的幾個(gè)內(nèi)存塊比較具有代表性，先看他們的釋放，釋放順序如下。

/*釋放*/xnheap_free(&hobalt_heap, ptr_1000_1);xnheap_free(&hobalt_heap, ptr_1000);xnheap_free(&hobalt_heap, ptr_1000_3);xnheap_free(&hobalt_heap, ptr_1000_2);xnheap_free(&hobalt_heap,ptr_1000_4);

頁(yè)內(nèi)塊釋放

首先釋放ptr10001，ptr10001實(shí)際指向的內(nèi)存塊可用空間為1024字節(jié)，首先計(jì)算ptr10001所在的內(nèi)存頁(yè)頁(yè)號(hào)pagenum = 2，以及頁(yè)內(nèi)的偏移量boffset = 1024.根據(jù)頁(yè)號(hào)得到該頁(yè)的類型pagemap[2].type=10，表示該已分配給buckets管理，跳轉(zhuǎn)執(zhí)行具體釋放操作：

    switch (heap->pagemap[pagenum].type) {        case XNHEAP_PFREE:  /* Unallocated page? */        case XNHEAP_PCONT:  /* Not a range heading page? */    bad_block:            xnlock_put_irqrestore(&heap->lock, s);            XENO_BUG(COBALT);            return;
        case XNHEAP_PLIST:                .....            break;
        default:            log2size = heap->pagemap[pagenum].type;            bsize = (1 << log2size);            if ((boffset & (bsize - 1)) != 0) /* Not a block start? */                goto bad_block;
            ilog = log2size - XNHEAP_MINLOG2;            if (likely(--heap->pagemap[pagenum].bcount > 0)) {                /* Return the block to the bucketed memory space. */                *((caddr_t *)block) = heap->buckets[ilog].freelist;                heap->buckets[ilog].freelist = block;                ++heap->buckets[ilog].fcount;                break;            }            .....    }heap->used-=bsize;

從pagemap[2].type得到log2size = 10，反算出我們釋放的指針指向的內(nèi)存塊大小bsize = 1024字節(jié)。知道要釋放的內(nèi)存大小后，驗(yàn)證該地址是否是合法的內(nèi)存塊起始地址，驗(yàn)證方法就是看該地址是否與bsize對(duì)齊 。

驗(yàn)證合法后開始釋放，要釋放的內(nèi)存屬于bucket管理，計(jì)算buckets[]下標(biāo)ilog =10-3=7,屬于buckets[7]管理。先將頁(yè)信息pagemap[pagenum].bcount減一，判斷是不是頁(yè)內(nèi)要釋放的最后一個(gè)內(nèi)存塊，如果是另行處理。22-24行將該該塊內(nèi)存放回bucket[7]，將釋放的內(nèi)存指向原來(lái)的freelist，freelist指向釋放的塊，更新fcount值，完成ptr10001的釋放。更新整個(gè)xnheap內(nèi)存使用量。釋放ptr10001后的內(nèi)存視圖如下。

接著依次釋放ptr1000、ptr10003與釋放ptr1000_1一致，釋放后如圖所示

此時(shí)pagemap[3].bcount=1，當(dāng)釋放最后一個(gè)內(nèi)存塊 ptr10002時(shí)，由于是該頁(yè)最后一塊情況有所不同，條件(--heap->pagemap[pagenum].bcount > 0)不滿足。執(zhí)行如下.

  default:    log2size = heap->pagemap[pagenum].type;/*10*/    bsize = (1 << log2size);/*1024*/    if ((boffset & (bsize - 1)) != 0) /* Not a block start? */      goto bad_block;
    ilog = log2size - XNHEAP_MINLOG2;    if (likely(--heap->pagemap[pagenum].bcount > 0)) {      ......      break;    }    npages = bsize / XNHEAP_PAGESZ;     if (unlikely(npages > 1))      goto free_page_list;
    freepage = heap->membase + pagenum * XNHEAP_PAGESZ;    block = freepage;    tailpage = freepage;    nextpage = freepage + XNHEAP_PAGESZ;    nblocks = XNHEAP_PAGESZ >> log2size;    heap->buckets[ilog].fcount -= (nblocks - 1);    XENO_BUG_ON(COBALT, heap->buckets[ilog].fcount < 0);
    if (likely(heap->buckets[ilog].fcount == 0)) {      heap->buckets[ilog].freelist = NULL;      goto free_pages;    }
    /*     * Worst case: multiple pages are traversed by the     * bucket list. Scan the list to remove all blocks     * belonging to the freed page. We are done whenever     * all possible blocks from the freed page have been     * traversed, or we hit the end of list, whichever     * comes first.     */    for (tailptr = &heap->buckets[ilog].freelist, freeptr = *tailptr, xpage = 1;         freeptr != NULL && nblocks > 0; freeptr = *((caddr_t *) freeptr)) {      if (unlikely(freeptr < freepage || freeptr >= nextpage)) {        if (unlikely(xpage)) {          *tailptr = freeptr;          xpage = 0;        }        tailptr = (caddr_t *)freeptr;      } else {        --nblocks;        xpage = 1;      }    }    *tailptr = freeptr;    goto free_pages;  }
heap->used-=bsize;

現(xiàn)在知道了該塊是頁(yè)的最后一塊，接著看該塊否是bucket[7]中的最后一個(gè)塊,判斷方式為看fcount-nblocks - 1是否等于0，如下。

nblocks = XNHEAP_PAGESZ >> log2size;heap->buckets[ilog].fcount -= (nblocks - 1);if (likely(heap->buckets[ilog].fcount == 0)) { /*是*/    heap->buckets[ilog].freelist = NULL;    goto free_pages;}

不是bucket的最后一塊，但是頁(yè)2已經(jīng)全部空閑，接下來(lái)重整頁(yè)面。

  for (tailptr = &heap->buckets[ilog].freelist, freeptr = *tailptr, xpage = 1;         freeptr != NULL && nblocks > 0; freeptr = *((caddr_t *) freeptr)) {      if (unlikely(freeptr < freepage || freeptr >= nextpage)) {        if (unlikely(xpage)) {          *tailptr = freeptr;          xpage = 0;        }        tailptr = (caddr_t *)freeptr;      } else {        --nblocks;        xpage = 1;      }    }    *tailptr = freeptr;gotofree_pages;

根據(jù)frelist找出已經(jīng)空閑的頁(yè)，然后跳轉(zhuǎn)至標(biāo)簽freepages進(jìn)行釋放頁(yè)2，freepages主要調(diào)整空閑頁(yè)之間的freelist,是鏈表freelist保持遞增。

  free_pages:    /* Mark the released pages as free. */    for (pagecont = 0; pagecont < npages; pagecont++)      heap->pagemap[pagenum + pagecont].type = XNHEAP_PFREE;
    /*     * Return the sub-list to the free page list, keeping     * an increasing address order to favor coalescence.     */    for (nextpage = heap->freelist, lastpage = NULL;         nextpage != NULL && nextpage < (caddr_t) block;         lastpage = nextpage, nextpage = *((caddr_t *)nextpage))      ;  /* Loop */
    *((caddr_t *)tailpage) = nextpage;
    if (lastpage)      *((caddr_t *)lastpage) = (caddr_t)block;    else      heap->freelist = (caddr_t)block;break;

下面釋放ptr10004，由于ptr10004是bucket[7]最后一塊直接將bucket[7].freelist指向NULL，然后跳轉(zhuǎn)至標(biāo)簽free_pages進(jìn)行釋放頁(yè)3就行，釋放后如下。

ptrt1、ptr50、ptr_5000均為頁(yè)和bucket的最后一塊，釋放流程相同，不再說(shuō)明。

頁(yè)連續(xù)的塊釋放

最后看一下ptr10000的釋放，ptr10000占用連續(xù)的3個(gè)頁(yè)，同樣根據(jù)ptr10000計(jì)算出塊開始頁(yè)的tpye=2（XNHEAPPLIST），進(jìn)入XNHEAP_PLIST分支釋放,通過(guò)看緊接著的頁(yè)的tpye計(jì)算內(nèi)存塊的頁(yè)數(shù)npages。計(jì)算該內(nèi)存塊的大小bsize，接著開始釋放頁(yè)。

void xnheap_free(struct xnheap *heap, void *block){  caddr_t freepage, lastpage, nextpage, tailpage, freeptr, *tailptr;  int log2size, npages, nblocks, xpage, ilog;  u32 pagenum, pagecont, boffset, bsize;  spl_t s;.......
  /* Compute the heading page number in the page map. */  pagenum = ((caddr_t)block - heap->membase) / XNHEAP_PAGESZ;  boffset = ((caddr_t)block - (heap->membase + pagenum * XNHEAP_PAGESZ));
  switch (heap->pagemap[pagenum].type) {  case XNHEAP_PFREE:  /* Unallocated page? */  case XNHEAP_PCONT:  /* Not a range heading page? */  bad_block:    xnlock_put_irqrestore(&heap->lock, s);    XENO_BUG(COBALT);    return;
  case XNHEAP_PLIST:    npages = 1;    while (npages < heap->npages &&           heap->pagemap[pagenum + npages].type == XNHEAP_PCONT)      npages++;
    bsize = npages * XNHEAP_PAGESZ;
  free_page_list:    /* Link all freed pages in a single sub-list. */    for (freepage = (caddr_t) block,           tailpage = (caddr_t) block + bsize - XNHEAP_PAGESZ;         freepage < tailpage; freepage += XNHEAP_PAGESZ)      *((caddr_t *) freepage) = freepage + XNHEAP_PAGESZ;
  .......
  default:         ......    }
heap->used-=bsize;

freepage指向塊的第一頁(yè)，tailpage指向塊的最后一頁(yè)，將釋放的幾頁(yè)鏈起來(lái)，成為一個(gè)子列表，如圖所示。

現(xiàn)在僅將塊內(nèi)的頁(yè)鏈接起來(lái)，接下來(lái)執(zhí)行標(biāo)簽free_pages，將這些要釋放的頁(yè)鏈接到空閑頁(yè)列表。

先將這些也對(duì)應(yīng)的pagemap.type標(biāo)志為空閑（XNHEAP_FREE）。

free_pages:    /* Mark the released pages as free. */    for (pagecont = 0; pagecont < npages; pagecont++)heap->pagemap[pagenum+pagecont].type=XNHEAP_PFREE;

將子列表放回空閑頁(yè)列表，并保持它們遞增的鏈接關(guān)系。

    for (nextpage = heap->freelist, lastpage = NULL;         nextpage != NULL && nextpage < (caddr_t) block;         lastpage = nextpage, nextpage = *((caddr_t *)nextpage))      ;  /* Loop */
    *((caddr_t *)tailpage) = nextpage;
    if (lastpage)      *((caddr_t *)lastpage) = (caddr_t)block;    else      heap->freelist = (caddr_t)block;break;

將子列表插入空閑鏈表后，完成釋放，視圖如下（ptrt1、ptr50、ptr_5000還未釋放）。

7. 總結(jié)

xenomai內(nèi)核通過(guò)自己管理一片內(nèi)存來(lái)避免內(nèi)存分配釋放影響實(shí)時(shí)性。

針對(duì)小于2*PAGESIZE 的內(nèi)存請(qǐng)求，xnheap使用bucket建立內(nèi)存池，使小內(nèi)存請(qǐng)求迅速得到滿足。對(duì)于大于2*PAGESIZE 的內(nèi)存請(qǐng)求,直接向空閑頁(yè)列表分配。

缺點(diǎn)：當(dāng)內(nèi)存頁(yè)列表比較疏松時(shí)，可能會(huì)出現(xiàn)分配一個(gè)大內(nèi)存（>4K）需要遍歷所有空閑頁(yè)到最后才分配到的情況。此時(shí)復(fù)雜度為O(n)，n表示空閑頁(yè)塊數(shù)。xenomai3.1對(duì)此進(jìn)行了優(yōu)化，使用紅黑樹按空閑塊大小來(lái)管理空閑頁(yè)，通過(guò)大小直接查找空閑頁(yè)速度極快，紅黑樹時(shí)間復(fù)雜度O(logn)，此外從紅黑樹中分配的內(nèi)存從原來(lái)4K改變?yōu)?12Byte對(duì)齊，這樣使內(nèi)存利用率進(jìn)一步提高，有機(jī)會(huì)繼續(xù)出一篇關(guān)于xenomai 3.1內(nèi)存管理的文章。

原文標(biāo)題：xenomai內(nèi)存池管理

文章出處：【微信公眾號(hào)：Linux閱碼場(chǎng)】歡迎添加關(guān)注!文章轉(zhuǎn)載請(qǐng)注明出處。

審核編輯：湯梓紅