xenomai系统中的xnheap管理机制
作者简介
顺刚(网名:沐多)，一线码农，从事工控行业，目前在一家工业自动化公司从事工业实时现场总线开发工作，喜欢钻研linux内核及xenomai，个人博客 wsg1100，欢迎大家关注！
目录
xenomai内存池管理
1.xnheap
2. xnpagemap
3. xnbucket
4. xnheap初始化
5. 内存块分配
5.1 小内存分配流程( 2*page_zise）
1. 分配10000字节
6. 内存释放
页内块释放
页连续的块释放
7. 总结
本文分析的xenomai系统中的内存池(xnheap)管理机制。
xenomai内存池管理 通常，操作系统的内存管理，内存分配算法一定要快，否则会影响应用程序的运行效率，其次是内存利用率要高。
但对于硬实时操作系统，首先要保证实时性，即确定性，不同内存大小的分配释放时间必须是确定的，同时也要快。
无论linux还是xenomai，内核在服务或管理应用程序过程中经常需要内存分配，通常linux内存的分配与释放都是时间不确定的，例如，惰性分配导致的缺页异常、页面换出和oom会导致大且不可预测的延迟，不适用于受严格时间限制的实时应用程序。
xenomai作为硬实时内核，不能使用linux这样的内存分配释放接口，为此xenomai采取的措施是：
在内核态，在xenomai内核初始化时，先调用 __vmalloc()从linux管理的zone_normal中分配 一片内存,然后由xenomai自己来管理这片内存，且xenomai提供的内存分配释放时间确定的，这样就不会因为内存的分配释放影响实时性（该内存管理代码量非常少，有效代码数3百行左右，实现精巧，值得研究利用）。
在用户态，glibc的内存管理不具有时间确定性，rt应用只能在程序初始化时分配并访问（避免运行中产生pagefault)，运行中不能使用，否则会严重影响实时性。为此xenomai实时应用库libcobalt为rt应用实现了时间确定的内存动态分配释放heap，供实时任务运行中分配内存，使用方法参见heap management services，其内存管理分配释放算法与内核里的差不多，不在赘述，下面开始。
下面代码基于 xenomai-3.0.8。xenomai 3.1开始有所不同详见文末。
1.xnheap xenomai管理的内存池称为xnheap，内存池大小预先配置，如xenomai的系统内存池cobaltheap，负责内核大多内核数据分配，其大小为 sysheap_size_arg*1024 byte（sysheapsizearg kb），sysheapsize_arg可在内核配置时设置，或者通过内核参数 xenomai.sysheap_size=配置。xenomai内核中这样管理的内存池不止一个，其他的 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) size of shared heap (kb) 简单介绍一下配置项中的几个内存池的用途：
(512)numberof registry slots，xenomai内核运行中内核资源对象存储槽的大小，用于分配系统使用资源的最大大小，如信号(signal)、互斥对象(mutex)、信号量等.
(4096)sizeof system heap(kb) 系统内存池，用于cobalt内核工作过程中动态内存分配，内核中很多任务共享的内存会从该区域分配,例如xddp通讯时数据缓冲区默认从该区域分配。
(512)sizeofprivateheap(kb) 每个cobalt任务私有的内存池，在实时任务创建时，从linux分配内存并初始化，位于cobalt任务调度实体 cobalt_process中,当实时任务内核上下文需要分配内存时，就会从该区域中获取，xddp 通讯中可选从该内存区分配缓冲区。
本节以xenomai的系统内存池cobaltheap为例来了解xenomai内存池管理。cobaltheap在xenomai内核初始化过程中初始化，先调用_vmalloc()从linux管理的zonenormal中分配，然后在调用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要求管理的内存大小必须是pagesize的倍数，且至少有2页，其最大值在xenomai3.0.8版本里为2gb(1membase = membase; heap->npages = size / xnheap_pagesz; if (heap->npages pagemap = kmalloc(sizeof(struct xnpagemap) * heap->npages, gfp_kernel);/*map 大小：每页需要一个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;} 计算该内存总页数npages，然后为每页分配一个xnpagemap对象，npages页需要分配npages个xnpagemap，然后调用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 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[],每页记录为未使用(xnheap_pfree)
设置xnheap的结束地址memlim，并将freelist指向第一个空闲页，然后从第一页开始，前一页保存着后一页起始地址。这样做不仅将空闲页连起来，方便分配时索引，而且通过内存赋值操作，如果该内存页未映射，会触发内核缺页异常，让linux将未映射到物理内存的页面映射到物理内存，这样后续xenomai使用过程中就不会再产生缺页中断，避免影响xenomai实时性。初始化后如下图所示
5. 内存块分配 xenomai内存堆初始化完后，下面通过分配与释放来分析分配释放过程，例如向内存池cobalt_heap()分别分配1byte、50byte、1000byte、5000byte、10000byte数据，然后依次释放。
/*向hobalt_heap分配1字节空间*/ptrt_1 = xnheap_alloc(&hobalt_heap, 1);/*向hobalt_heap分配50字节空间*/ptr_50 = xnheap_alloc(&hobalt_heap, 50);/*连续向hobalt_heap分配1000字节空间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字节空间*/ptr_5000 = xnheap_alloc(&hobalt_heap, 5000);/*向hobalt_heap分配10000字节空间*/ptr_10000 = xnheap_alloc(&hobalt_heap, 10000); 5.1 小内存分配流程(<= 2*page_zise) 1.分配1byte 首先来看分配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 < 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); ......} 首先根据大小size来向最小分配或最大分配对齐，xenomai分配类型分为3类，对于大于xnheappagesz的向上与xnheappagesz对齐；对于小于8byte的，向上与8byte对齐；对于大于8byte，向上与16byte对齐；这样是为了与bucket一一对应。
例如分配5000byte，最终分配到的空间大小为8192 byte（以page_size为4kb计算），要分配1byte空间，将会得到8byte的空间，分配50byte空间得到64byte空间。
我们请求分配1byte的内存，对齐后size为8 byte， buckets[xnheap_nbuckets]只管理请求大小小于2*pageszie的分配池。当请求的大小大于页大小的2倍时，从空闲页列表直接分配页面会更节省空间。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 = 1buckets[ilog].freelist; if (block == null) { block = get_free_range(heap, bsize, log2size); if (block == null) goto out; if (bsize buckets[ilog].fcount += (xnheap_pagesz >> log2size) - 1; } else { if (bsize 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 { ..... } 第一步先对size求log2size，log28=3，得到bucket索引下标ilog = log_28-3=0，再用ilog作为下标得到管理8byte大小池的bucket，buckets[0].freelist指向首个空闲块，如果buckets[ilog].freelist不为null，则将buckets[ilog].freelist指向的块分配出去，buckets[ilog].fcount减一，再根据freelist的地址计算该空闲块位于第几页（pagenum），更新该页的pagemap[pagenum].bcount。再将buckets[ilog].freelist指向下一个空闲页，更新总内存已分配大小heap->used，返回分配到的内存地址block。
但我们内存池刚初始化，buckets[ilog].freelist 为null，进入block==null分支,先为该bucket分配空间。
先通过getfreerange()分配，分配后计算bucket的剩余块数buckets[ilog].fcount，xnheap_pagesz >> log2size就是新页面被分成了多少块，且马上就要被分配出去耍一块，所以再减一。
下面看如何分配bucket管理的空间，getfreerange()中，先分配空闲页，然后再对空闲页进行分块。先看从整块内存找空闲页部分
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; do { lastpage = freepage; freepage = *((caddr_t *) freepage); freecont += xnheap_pagesz; } while (freepage == lastpage + xnheap_pagesz && 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内存中第一个空闲页，10-14行循环迭代freepage并记录大小freecont，直到得到freecont大小的空闲页。我们传入getfreerange()的bsize=8，log_2size = 3，所以循环1次，分配到4kb空间就够了。如下图所示.
条件freecont >= bsize表示分配到了满足大小的连续空闲页，否则就是连续内存空间不够，看lastpage指向的下一个空闲空间是否连续，直到分配到符合条件的内存页，否则无法满足此次分配条件，返回 null。
我们这里分配到了页0，20行更新heap->freelist指向下一个空闲页 。
跳转splitpage对页0进行切割。
splitpage: if (bsize < xnheap_pagesz) { for (block = headpage, eblock = headpage + xnheap_pagesz - bsize; block 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; splitpage操作将一个4k大小的页分成一个个大小为8byte的块，并将这些块连起来，并更xpagemap[pagenum]的type为块大小3(2的幂log_2blocksize），表示该页plist。bcount=1是即将分配出去的第一个块。
回到xnheapalloc(),更新bucket内剩余块数heap->buckets[3].fcount、8字节池空闲地址buckets[3].freelist，整个内存池已分配数heap->used，然后返回内存池分配的到的内存起始地址ptr1。此时如下：
通过以上分析，我们分配1字节空间，最终得到8字节的空间，8(1<<3)字节是xenomai内存池的最小管理单位，并且下次再分配8byte内空间时，直接返回buckets[3].freelist并更新几个成员变量即可，速度极快。
2.分配50byte 同样，根据以上步骤请求分配50字节空间时，先对50向上向上对齐得到64，计算bucket索引ilog = log_2 64-3=3，本次分配请求从bucket[3]管理的内存池中分配，由于首次分配，bucket[3]中没有还管理的空间需要先从xnheap中分配空闲页，最终分配得到64字节大小的空间，分配后如下图所示。
3.分配1000 byte 请求分配1000字节空间时，先对1000向上对齐得到1024，计算bucket索引ilog = log_2 1024-3=7，本次分配请求从bucket[7]管理的内存池中分配，由于首次分配，bucket[7]中没有还管理的空间需要先从xnheap中分配一个空闲页分成4块交给bucket管理，最终本次分配得到1024字节大小的空间，分配后如下图所示。
以上分配后，buckets[7]中还剩余3个空闲块，如果bucket内的所有块分配完了，再次请求分配大小为1000字节的空间时会怎样?会再去分配一页空闲页进行切割。为了表示这个过程，继续执行以下语句，当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);
当分配ptr10003后bucket中不再由空闲块，bucket[7].freelist重新指向null，分配ptr10004时就会触发再次从总内存分配空闲页来分成1k大小的块，分配ptr10004后bucket[7].freelist指向新的空闲页。
4. 分配5000字节 由于请求大小是5000字节，前面说过超过页大小后会与页对齐，也就是8k的空间，且该大小满足 2*page_zise） 1. 分配10000字节 由于请求大小是10000字节，前面说过超过页大小后会与页对齐，也就是12k的空间，对于大于8k（2*page）size）大小的分配请求，从空闲页列表直接分配页面会更节省空间。
if (likely(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; } 先判断总大小，然后调用getfreerange()直接从空闲页列表直接分配,参数log2size=0,该情况下getfree_range()函数执行路径如下；
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; /*在空闲页列表查找满足条件的连续空闲页*/ do { lastpage = freepage; freepage = *((caddr_t *) freepage); freecont += xnheap_pagesz; } while (freepage == lastpage + xnheap_pagesz && freecont = bsize) { /*得到连续的页*/ if (headpage == heap->freelist) heap->freelist = *((caddr_t *)lastpage); /*更新freelist*/ else ..... goto splitpage; } freehead = lastpage; } return null;splitpage: if (bsize < xnheap_pagesz) { //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;} 分配后的内存视图如下。
6. 内存释放 通过以上分析，我们可以将分配到的内存块分为两类：
从bucket中分配，大小小于等于4kb，不仅bucket记录着数量，该块所在页的pagemap[].type也记录着该块的大小。
直接从空闲列表分配，大小大于4kb，pagemap[n].type为xnheapplist（2）表示页n是该块的开始页，后续的n+i页，pagemap[n+i].type都为xnheappcont(1)。
内存块释放的过程就是根据这些信息来定位要释放的块，并将它重新放回bucket内存池或空闲页列表。
通过 xnheap_alloc()分配的内存，通过 xnheap_free()释放，当然必须是在同一个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 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()中先根据地址判断释放的内存块是否属于指定的xnheap。如果合法的，接着计算要释放的内存所在的页号pagenum，以及页内的偏移量boffset。得到页号后从pagemap[pagenum]判断要释放的内存块属于那种类型，再做相应的释放操作。
将前面分配到的内存按不同顺序释放，来查看xnheap的释放流程,由于分配的1000字节的几个内存块比较具有代表性，先看他们的释放，释放顺序如下。
/*释放*/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); 页内块释放 首先释放ptr10001，ptr10001实际指向的内存块可用空间为1024字节，首先计算ptr10001所在的内存页页号pagenum = 2，以及页内的偏移量boffset = 1024.根据页号得到该页的类型pagemap[2].type=10，表示该已分配给buckets管理，跳转执行具体释放操作：
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 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，反算出我们释放的指针指向的内存块大小bsize = 1024字节。知道要释放的内存大小后，验证该地址是否是合法的内存块起始地址，验证方法就是看该地址是否与bsize对齐 。
验证合法后开始释放，要释放的内存属于bucket管理，计算buckets[]下标ilog =10-3=7,属于buckets[7]管理。先将页信息pagemap[pagenum].bcount减一，判断是不是页内要释放的最后一个内存块，如果是另行处理。22-24行将该该块内存放回bucket[7]，将释放的内存指向原来的freelist，freelist指向释放的块，更新fcount值，完成ptr10001的释放。更新整个xnheap内存使用量。释放ptr10001后的内存视图如下。
接着依次释放ptr1000、ptr10003与释放ptr1000_1一致，释放后如图所示
此时pagemap[3].bcount=1，当释放最后一个内存块 ptr10002时，由于是该页最后一块情况有所不同，条件(--heap->pagemap[pagenum].bcount > 0)不满足。执行如下.
default: log2size = heap->pagemap[pagenum].type;/*10*/ bsize = (1 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 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 = nextpage)) { if (unlikely(xpage)) { *tailptr = freeptr; xpage = 0; } tailptr = (caddr_t *)freeptr; } else { --nblocks; xpage = 1; } } *tailptr = freeptr; goto free_pages; } heap->used -= bsize; 现在知道了该块是页的最后一块，接着看该块否是bucket[7]中的最后一个块,判断方式为看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的最后一块，但是页2已经全部空闲，接下来重整页面。
for (tailptr = &heap->buckets[ilog].freelist, freeptr = *tailptr, xpage = 1; freeptr != null && nblocks > 0; freeptr = *((caddr_t *) freeptr)) { if (unlikely(freeptr = nextpage)) { if (unlikely(xpage)) { *tailptr = freeptr; xpage = 0; } tailptr = (caddr_t *)freeptr; } else { --nblocks; xpage = 1; } } *tailptr = freeptr; goto free_pages; 根据frelist找出已经空闲的页，然后跳转至标签freepages进行释放页2，freepages主要调整空闲页之间的freelist,是链表freelist保持递增。
free_pages: /* mark the released pages as free. */ for (pagecont = 0; pagecont 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 freelist = (caddr_t)block; break;
下面释放ptr10004，由于ptr10004是bucket[7]最后一块直接将bucket[7].freelist指向null，然后跳转至标签free_pages进行释放页3就行，释放后如下。
ptrt1、ptr50、ptr_5000均为页和bucket的最后一块，释放流程相同，不再说明。
页连续的块释放 最后看一下ptr10000的释放，ptr10000占用连续的3个页，同样根据ptr10000计算出块开始页的tpye=2（xnheapplist），进入xnheap_plist分支释放,通过看紧接着的页的tpye计算内存块的页数npages。计算该内存块的大小bsize，接着开始释放页。
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 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 used -= bsize; freepage指向块的第一页，tailpage指向块的最后一页，将释放的几页链起来，成为一个子列表，如图所示。
现在仅将块内的页链接起来，接下来执行标签free_pages，将这些要释放的页链接到空闲页列表。
先将这些也对应的pagemap.type标志为空闲（xnheap_free）。
free_pages: /* mark the released pages as free. */ for (pagecont = 0; pagecont pagemap[pagenum + pagecont].type = xnheap_pfree; 将子列表放回空闲页列表，并保持它们递增的链接关系。
for (nextpage = heap->freelist, lastpage = null; nextpage != null && nextpage freelist = (caddr_t)block; break; 将子列表插入空闲链表后，完成释放，视图如下（ptrt1、ptr50、ptr_5000还未释放）。
7. 总结 xenomai内核通过自己管理一片内存来避免内存分配释放影响实时性。
针对小于2*pagesize 的内存请求，xnheap使用bucket建立内存池，使小内存请求迅速得到满足。对于大于2*pagesize 的内存请求,直接向空闲页列表分配。
缺点：当内存页列表比较疏松时，可能会出现分配一个大内存（>4k）需要遍历所有空闲页到最后才分配到的情况。此时复杂度为o(n)，n表示空闲页块数。xenomai3.1对此进行了优化，使用红黑树按空闲块大小来管理空闲页，通过大小直接查找空闲页速度极快，红黑树时间复杂度o(logn)，此外从红黑树中分配的内存从原来4k改变为512byte对齐，这样使内存利用率进一步提高，有机会继续出一篇关于xenomai 3.1内存管理的文章。
原文标题：xenomai内存池管理
文章出处：【微信公众号：linux阅码场】欢迎添加关注!文章转载请注明出处。
13.2W电源原理图讲解
北京纯电市占率达43.1%，比亚迪为何会成为首家产销破30万辆的新能源车企？
要如何判断机器视觉相机是否适合您的应用呢？
关于工业的数字化创新发展之路设备网联化与网络IP化浅析
DC电源模块在传输过程中如何减少能量的损失
xenomai系统中的xnheap管理机制
2020年自动驾驶商业化落地才刚开始
RTU远程终端控制系统的功能特点及应用范围
加码智慧城市背后的底层驱动力到底是什么
华为董事长梁华主题演讲,这三点很重要
LED“尝鲜”3D打印 或成发展趋势
剩余电流动作保护器零线漏电简易排除法
基于FPGA器件实现异步FIFO读写系统的设计
stm32 can不稳定的解决方法
高精度低功耗的超声波传感器MB1043在冶金领域的应用
怎样更换Sony TC-WR535双盒式磁带座上的皮带
基于灵动微MM32F3270微控制器的监护仪
多核风暴来袭 各厂商应对之策分析
亚马逊Echo Alexa Google Home 语音控制彩光WiFi模组SLMWF-11003
RDMA技术简介 RDMA的控制通路和数据通路方案
顺刚(网名:沐多)，一线码农，从事工控行业，目前在一家工业自动化公司从事工业实时现场总线开发工作，喜欢钻研linux内核及xenomai，个人博客 wsg1100，欢迎大家关注！
目录
xenomai内存池管理
1.xnheap
2. xnpagemap
3. xnbucket
4. xnheap初始化
5. 内存块分配
5.1 小内存分配流程( 2*page_zise）
1. 分配10000字节
6. 内存释放
页内块释放
页连续的块释放
7. 总结
本文分析的xenomai系统中的内存池(xnheap)管理机制。
xenomai内存池管理 通常，操作系统的内存管理，内存分配算法一定要快，否则会影响应用程序的运行效率，其次是内存利用率要高。
但对于硬实时操作系统，首先要保证实时性，即确定性，不同内存大小的分配释放时间必须是确定的，同时也要快。
无论linux还是xenomai，内核在服务或管理应用程序过程中经常需要内存分配，通常linux内存的分配与释放都是时间不确定的，例如，惰性分配导致的缺页异常、页面换出和oom会导致大且不可预测的延迟，不适用于受严格时间限制的实时应用程序。
xenomai作为硬实时内核，不能使用linux这样的内存分配释放接口，为此xenomai采取的措施是：
在内核态，在xenomai内核初始化时，先调用 __vmalloc()从linux管理的zone_normal中分配 一片内存,然后由xenomai自己来管理这片内存，且xenomai提供的内存分配释放时间确定的，这样就不会因为内存的分配释放影响实时性（该内存管理代码量非常少，有效代码数3百行左右，实现精巧，值得研究利用）。
在用户态，glibc的内存管理不具有时间确定性，rt应用只能在程序初始化时分配并访问（避免运行中产生pagefault)，运行中不能使用，否则会严重影响实时性。为此xenomai实时应用库libcobalt为rt应用实现了时间确定的内存动态分配释放heap，供实时任务运行中分配内存，使用方法参见heap management services，其内存管理分配释放算法与内核里的差不多，不在赘述，下面开始。
下面代码基于 xenomai-3.0.8。xenomai 3.1开始有所不同详见文末。
1.xnheap xenomai管理的内存池称为xnheap，内存池大小预先配置，如xenomai的系统内存池cobaltheap，负责内核大多内核数据分配，其大小为 sysheap_size_arg*1024 byte（sysheapsizearg kb），sysheapsize_arg可在内核配置时设置，或者通过内核参数 xenomai.sysheap_size=配置。xenomai内核中这样管理的内存池不止一个，其他的 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) size of shared heap (kb) 简单介绍一下配置项中的几个内存池的用途：
(512)numberof registry slots，xenomai内核运行中内核资源对象存储槽的大小，用于分配系统使用资源的最大大小，如信号(signal)、互斥对象(mutex)、信号量等.
(4096)sizeof system heap(kb) 系统内存池，用于cobalt内核工作过程中动态内存分配，内核中很多任务共享的内存会从该区域分配,例如xddp通讯时数据缓冲区默认从该区域分配。
(512)sizeofprivateheap(kb) 每个cobalt任务私有的内存池，在实时任务创建时，从linux分配内存并初始化，位于cobalt任务调度实体 cobalt_process中,当实时任务内核上下文需要分配内存时，就会从该区域中获取，xddp 通讯中可选从该内存区分配缓冲区。
本节以xenomai的系统内存池cobaltheap为例来了解xenomai内存池管理。cobaltheap在xenomai内核初始化过程中初始化，先调用_vmalloc()从linux管理的zonenormal中分配，然后在调用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要求管理的内存大小必须是pagesize的倍数，且至少有2页，其最大值在xenomai3.0.8版本里为2gb(1
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 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[],每页记录为未使用(xnheap_pfree)
设置xnheap的结束地址memlim，并将freelist指向第一个空闲页，然后从第一页开始，前一页保存着后一页起始地址。这样做不仅将空闲页连起来，方便分配时索引，而且通过内存赋值操作，如果该内存页未映射，会触发内核缺页异常，让linux将未映射到物理内存的页面映射到物理内存，这样后续xenomai使用过程中就不会再产生缺页中断，避免影响xenomai实时性。初始化后如下图所示
5. 内存块分配 xenomai内存堆初始化完后，下面通过分配与释放来分析分配释放过程，例如向内存池cobalt_heap()分别分配1byte、50byte、1000byte、5000byte、10000byte数据，然后依次释放。
/*向hobalt_heap分配1字节空间*/ptrt_1 = xnheap_alloc(&hobalt_heap, 1);/*向hobalt_heap分配50字节空间*/ptr_50 = xnheap_alloc(&hobalt_heap, 50);/*连续向hobalt_heap分配1000字节空间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字节空间*/ptr_5000 = xnheap_alloc(&hobalt_heap, 5000);/*向hobalt_heap分配10000字节空间*/ptr_10000 = xnheap_alloc(&hobalt_heap, 10000); 5.1 小内存分配流程(<= 2*page_zise) 1.分配1byte 首先来看分配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 < 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); ......} 首先根据大小size来向最小分配或最大分配对齐，xenomai分配类型分为3类，对于大于xnheappagesz的向上与xnheappagesz对齐；对于小于8byte的，向上与8byte对齐；对于大于8byte，向上与16byte对齐；这样是为了与bucket一一对应。
例如分配5000byte，最终分配到的空间大小为8192 byte（以page_size为4kb计算），要分配1byte空间，将会得到8byte的空间，分配50byte空间得到64byte空间。
我们请求分配1byte的内存，对齐后size为8 byte， buckets[xnheap_nbuckets]只管理请求大小小于2*pageszie的分配池。当请求的大小大于页大小的2倍时，从空闲页列表直接分配页面会更节省空间。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
但我们内存池刚初始化，buckets[ilog].freelist 为null，进入block==null分支,先为该bucket分配空间。
先通过getfreerange()分配，分配后计算bucket的剩余块数buckets[ilog].fcount，xnheap_pagesz >> log2size就是新页面被分成了多少块，且马上就要被分配出去耍一块，所以再减一。
下面看如何分配bucket管理的空间，getfreerange()中，先分配空闲页，然后再对空闲页进行分块。先看从整块内存找空闲页部分
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; do { lastpage = freepage; freepage = *((caddr_t *) freepage); freecont += xnheap_pagesz; } while (freepage == lastpage + xnheap_pagesz && 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内存中第一个空闲页，10-14行循环迭代freepage并记录大小freecont，直到得到freecont大小的空闲页。我们传入getfreerange()的bsize=8，log_2size = 3，所以循环1次，分配到4kb空间就够了。如下图所示.
条件freecont >= bsize表示分配到了满足大小的连续空闲页，否则就是连续内存空间不够，看lastpage指向的下一个空闲空间是否连续，直到分配到符合条件的内存页，否则无法满足此次分配条件，返回 null。
我们这里分配到了页0，20行更新heap->freelist指向下一个空闲页 。
跳转splitpage对页0进行切割。
splitpage: if (bsize < xnheap_pagesz) { for (block = headpage, eblock = headpage + xnheap_pagesz - bsize; block 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; splitpage操作将一个4k大小的页分成一个个大小为8byte的块，并将这些块连起来，并更xpagemap[pagenum]的type为块大小3(2的幂log_2blocksize），表示该页plist。bcount=1是即将分配出去的第一个块。
回到xnheapalloc(),更新bucket内剩余块数heap->buckets[3].fcount、8字节池空闲地址buckets[3].freelist，整个内存池已分配数heap->used，然后返回内存池分配的到的内存起始地址ptr1。此时如下：
通过以上分析，我们分配1字节空间，最终得到8字节的空间，8(1<<3)字节是xenomai内存池的最小管理单位，并且下次再分配8byte内空间时，直接返回buckets[3].freelist并更新几个成员变量即可，速度极快。
2.分配50byte 同样，根据以上步骤请求分配50字节空间时，先对50向上向上对齐得到64，计算bucket索引ilog = log_2 64-3=3，本次分配请求从bucket[3]管理的内存池中分配，由于首次分配，bucket[3]中没有还管理的空间需要先从xnheap中分配空闲页，最终分配得到64字节大小的空间，分配后如下图所示。
3.分配1000 byte 请求分配1000字节空间时，先对1000向上对齐得到1024，计算bucket索引ilog = log_2 1024-3=7，本次分配请求从bucket[7]管理的内存池中分配，由于首次分配，bucket[7]中没有还管理的空间需要先从xnheap中分配一个空闲页分成4块交给bucket管理，最终本次分配得到1024字节大小的空间，分配后如下图所示。
以上分配后，buckets[7]中还剩余3个空闲块，如果bucket内的所有块分配完了，再次请求分配大小为1000字节的空间时会怎样?会再去分配一页空闲页进行切割。为了表示这个过程，继续执行以下语句，当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);
当分配ptr10003后bucket中不再由空闲块，bucket[7].freelist重新指向null，分配ptr10004时就会触发再次从总内存分配空闲页来分成1k大小的块，分配ptr10004后bucket[7].freelist指向新的空闲页。
4. 分配5000字节 由于请求大小是5000字节，前面说过超过页大小后会与页对齐，也就是8k的空间，且该大小满足 2*page_zise） 1. 分配10000字节 由于请求大小是10000字节，前面说过超过页大小后会与页对齐，也就是12k的空间，对于大于8k（2*page）size）大小的分配请求，从空闲页列表直接分配页面会更节省空间。
if (likely(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; } 先判断总大小，然后调用getfreerange()直接从空闲页列表直接分配,参数log2size=0,该情况下getfree_range()函数执行路径如下；
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; /*在空闲页列表查找满足条件的连续空闲页*/ do { lastpage = freepage; freepage = *((caddr_t *) freepage); freecont += xnheap_pagesz; } while (freepage == lastpage + xnheap_pagesz && freecont = bsize) { /*得到连续的页*/ if (headpage == heap->freelist) heap->freelist = *((caddr_t *)lastpage); /*更新freelist*/ else ..... goto splitpage; } freehead = lastpage; } return null;splitpage: if (bsize < xnheap_pagesz) { //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;} 分配后的内存视图如下。
6. 内存释放 通过以上分析，我们可以将分配到的内存块分为两类：
从bucket中分配，大小小于等于4kb，不仅bucket记录着数量，该块所在页的pagemap[].type也记录着该块的大小。
直接从空闲列表分配，大小大于4kb，pagemap[n].type为xnheapplist（2）表示页n是该块的开始页，后续的n+i页，pagemap[n+i].type都为xnheappcont(1)。
内存块释放的过程就是根据这些信息来定位要释放的块，并将它重新放回bucket内存池或空闲页列表。
通过 xnheap_alloc()分配的内存，通过 xnheap_free()释放，当然必须是在同一个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 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()中先根据地址判断释放的内存块是否属于指定的xnheap。如果合法的，接着计算要释放的内存所在的页号pagenum，以及页内的偏移量boffset。得到页号后从pagemap[pagenum]判断要释放的内存块属于那种类型，再做相应的释放操作。
将前面分配到的内存按不同顺序释放，来查看xnheap的释放流程,由于分配的1000字节的几个内存块比较具有代表性，先看他们的释放，释放顺序如下。
/*释放*/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); 页内块释放 首先释放ptr10001，ptr10001实际指向的内存块可用空间为1024字节，首先计算ptr10001所在的内存页页号pagenum = 2，以及页内的偏移量boffset = 1024.根据页号得到该页的类型pagemap[2].type=10，表示该已分配给buckets管理，跳转执行具体释放操作：
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
验证合法后开始释放，要释放的内存属于bucket管理，计算buckets[]下标ilog =10-3=7,属于buckets[7]管理。先将页信息pagemap[pagenum].bcount减一，判断是不是页内要释放的最后一个内存块，如果是另行处理。22-24行将该该块内存放回bucket[7]，将释放的内存指向原来的freelist，freelist指向释放的块，更新fcount值，完成ptr10001的释放。更新整个xnheap内存使用量。释放ptr10001后的内存视图如下。
接着依次释放ptr1000、ptr10003与释放ptr1000_1一致，释放后如图所示
此时pagemap[3].bcount=1，当释放最后一个内存块 ptr10002时，由于是该页最后一块情况有所不同，条件(--heap->pagemap[pagenum].bcount > 0)不满足。执行如下.
default: log2size = heap->pagemap[pagenum].type;/*10*/ bsize = (1
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的最后一块，但是页2已经全部空闲，接下来重整页面。
for (tailptr = &heap->buckets[ilog].freelist, freeptr = *tailptr, xpage = 1; freeptr != null && nblocks > 0; freeptr = *((caddr_t *) freeptr)) { if (unlikely(freeptr = nextpage)) { if (unlikely(xpage)) { *tailptr = freeptr; xpage = 0; } tailptr = (caddr_t *)freeptr; } else { --nblocks; xpage = 1; } } *tailptr = freeptr; goto free_pages; 根据frelist找出已经空闲的页，然后跳转至标签freepages进行释放页2，freepages主要调整空闲页之间的freelist,是链表freelist保持递增。
free_pages: /* mark the released pages as free. */ for (pagecont = 0; pagecont 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 freelist = (caddr_t)block; break;
下面释放ptr10004，由于ptr10004是bucket[7]最后一块直接将bucket[7].freelist指向null，然后跳转至标签free_pages进行释放页3就行，释放后如下。
ptrt1、ptr50、ptr_5000均为页和bucket的最后一块，释放流程相同，不再说明。
页连续的块释放 最后看一下ptr10000的释放，ptr10000占用连续的3个页，同样根据ptr10000计算出块开始页的tpye=2（xnheapplist），进入xnheap_plist分支释放,通过看紧接着的页的tpye计算内存块的页数npages。计算该内存块的大小bsize，接着开始释放页。
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 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 used -= bsize; freepage指向块的第一页，tailpage指向块的最后一页，将释放的几页链起来，成为一个子列表，如图所示。
现在仅将块内的页链接起来，接下来执行标签free_pages，将这些要释放的页链接到空闲页列表。
先将这些也对应的pagemap.type标志为空闲（xnheap_free）。
free_pages: /* mark the released pages as free. */ for (pagecont = 0; pagecont pagemap[pagenum + pagecont].type = xnheap_pfree; 将子列表放回空闲页列表，并保持它们递增的链接关系。
for (nextpage = heap->freelist, lastpage = null; nextpage != null && nextpage freelist = (caddr_t)block; break; 将子列表插入空闲链表后，完成释放，视图如下（ptrt1、ptr50、ptr_5000还未释放）。
7. 总结 xenomai内核通过自己管理一片内存来避免内存分配释放影响实时性。
针对小于2*pagesize 的内存请求，xnheap使用bucket建立内存池，使小内存请求迅速得到满足。对于大于2*pagesize 的内存请求,直接向空闲页列表分配。
缺点：当内存页列表比较疏松时，可能会出现分配一个大内存（>4k）需要遍历所有空闲页到最后才分配到的情况。此时复杂度为o(n)，n表示空闲页块数。xenomai3.1对此进行了优化，使用红黑树按空闲块大小来管理空闲页，通过大小直接查找空闲页速度极快，红黑树时间复杂度o(logn)，此外从红黑树中分配的内存从原来4k改变为512byte对齐，这样使内存利用率进一步提高，有机会继续出一篇关于xenomai 3.1内存管理的文章。
原文标题：xenomai内存池管理
文章出处：【微信公众号：linux阅码场】欢迎添加关注!文章转载请注明出处。
13.2W电源原理图讲解
北京纯电市占率达43.1%，比亚迪为何会成为首家产销破30万辆的新能源车企？
要如何判断机器视觉相机是否适合您的应用呢？
关于工业的数字化创新发展之路设备网联化与网络IP化浅析
DC电源模块在传输过程中如何减少能量的损失
xenomai系统中的xnheap管理机制
2020年自动驾驶商业化落地才刚开始
RTU远程终端控制系统的功能特点及应用范围
加码智慧城市背后的底层驱动力到底是什么
华为董事长梁华主题演讲,这三点很重要
LED“尝鲜”3D打印 或成发展趋势
剩余电流动作保护器零线漏电简易排除法
基于FPGA器件实现异步FIFO读写系统的设计
stm32 can不稳定的解决方法
高精度低功耗的超声波传感器MB1043在冶金领域的应用
怎样更换Sony TC-WR535双盒式磁带座上的皮带
基于灵动微MM32F3270微控制器的监护仪
多核风暴来袭 各厂商应对之策分析
亚马逊Echo Alexa Google Home 语音控制彩光WiFi模组SLMWF-11003
RDMA技术简介 RDMA的控制通路和数据通路方案