这里简单提一下在RTOS环境开发中,比较容易出现的一个BUG为例，引出我们为什么要设计我们这个内存池的轮子。以FreeRTOS为例，堆管理malloc和free的实现是基于链表进行的，链表是一个全局的资源，且操作不是一个原子操作，涉及很多步骤，所以多处调用时就必须进行临界段保护，否则操作到一半被打断进行另外的操作就会导致资源被破坏。FreeRTOS的处理方式是关调度的方式来实现临界段保护，关调度只能保证任务不会抢占，无法保证中断抢占，所以中断中不能调用FreeRTOS的malloc和free接口。而有时驱动设计又必须使用动态内存管理，驱动很多都是中断驱动的有时必须在中断中调用堆管理接口，此时直接调用FreeRTOS的堆管理接口就会导致问题，上述问题很可能难以发现，并且不一定能测试出来，可能在某种凑巧时机，刚好中断中打断任务中的堆接口执行，并调用堆管理接口此时就会出现问题。这种问题很可能就会出现很大的随机性导致了的调试的困难。知道了这个原因就可以避免类似的错误了，但是回到问题来，我们中断中还是有动态内存的使用需求那怎么办呢，最简单的方式就是还是使用FreeRTOS提供的堆接口，把关调度改为关中断，这样就可以保证临界段不被抢占，就不会有问题，但是这里会有一些副作用就是关中断时间的增加，并且这个时间还是不确定的，我们下一节就进行了实测。当然堆管理还有碎片化等问题，所以不适合在驱动层和中断时调用。所以我们还有一种方式就是使用内存池，这是很多中间件，驱动比较常见的方式，我们这一篇就是要来实现一个简单高效的内存池，但是我们不满足于此，我们还有更高的要求，毕竟是在驱动层甚至中断中使用，我们希望它执行非常快，并且执行时间基本无波动，因为这两个指标都是很重要的，很多系统甚至是必须要满足的。
执行时间测试有很多种方式，一般使用硬件定时器。我们这里使用另一种实践中也常用的方式，使用IO翻转，示波器查看波形的方式测试，进入接口执行时翻转IO，退出接口执行，再次翻转IO，IO波形得脉宽即执行时间，这样可以可视化观察，疏密变化可以看出执行时间的抖动，脉宽可以看出执行时间，maloc和free使用不同IO对比，还可以看出申请和释放的时间分布等等，所以这是一种非常好的方式。
我这里实测某个平台，freertos得malloc和free执行时间如下(注意执行时间硬件平台不一样也不一样)，可以看到时间抖动较大，时间也不短，4.6uS已经算很长了，比如中断中做时序解析这个时间很可能就难以满足需求。
后面我们对比修改为我们高效的内存池实现的对比测试，可以看到基本无抖动，且执行时间非常短(这里还未去掉翻转IO函数本身的执行和IO响应时间)。从汇编代码其实也可以看出指令很少了。
将一块空间划分为n个等大小的块，前面用一个字段标记是否使用的标记，剩余部分作为有效存储空间。初始化全部是空闲，标记都是0，需要申请时从头开始搜索，搜索到标记为0的块则可申请将标记改为1，释放则直接匹配地址将对应的标记设置为0.
上述标记至少需要占用一个字节，并且插入到有效块前会影响有效块的对齐属性，所以还可以优化，标记信息单独使用bitmap记录，如下所示，
有效块可以按照需要的原始数据结构连续对齐，bitmap一个bit对应一个块，为1表示该块已分配为0表示空闲，bitmap也减少了空间占用。申请释放算法和原来类似，申请只是变为了搜索bitmap的最低字节最低位开始的0的位置将其设置为1，获取对应的块地址，释放则是根据地址计算bitmap的bit索引将对应的bit设置为0.
上述bitmap实现在存储上已经优化了，但是在执行时间上因为要遍历搜寻所以是有抖动的，那么要满足我们的无时间抖动设计，目标就是要实现查找最低字节最低为开始的0的位置的算法时间固定。我们前面很多文章其实已经提到了矛盾的思想即，从矛盾的角度看问题，要解决一个问题可以看其对立面，因为往往矛盾是此消彼长的，算法的时间和空间就是矛盾体，要求时间那么我们就去看看是否能从空间的角度去考虑，一种常见的空间换时间的方法就是查表法，查表一方面时间固定一方面也高效。实际在uSOSII的实现中，查找最高就绪优先级就使用了该算法，我们直接拿过来使用并简单介绍下其原理。
首先我们将bitmap按照矩阵排列，自然而然地想到以字节为列，bit0~7对应0~7列，多个字节对应多行。每个bit对应一个块，bit为1表示空闲，为0表示占用。
那么最低字节的最低位位1则是我们要找的空闲块。那么如何快速找到这个bit呢，常规思想是从字节0开始找，如果全为0则继续找字节1，找到不为0的字节，然后从bit0到bit7找最开始出现的1的位置，那么这个bit在整个bit的索引就是(字节序号*8+位序号).
所以时间上可以分解为两步，第一步是找字节位置，第二步找bit位置。
找bit位置实际我们可以很快想到通过查表法实现。
8为数据有256种可能，每一种可能我们直接将其最低出现1的位置写出来就行，实际就是构造一个256字节的数组表，其指定索引的值，就是这个索引对应的数字，其最先出现1的bit位置。
比如
00000000 没有1则最低最先出现1的位置是0，所以数组索引1的位置值为0
00000001 最先出现1的位置是bit0，所以数组索引1的位置值为0
00000010 最先出现1的位置是bit1，所以数组索引2的位置值为1
00000011 最先出现1的位置是bit0，所以数组索引3的位置值为0
00000100 最先出现1的位置是bit2，所以数组索引4的位置值为2
所以最终构造出如下表格
static uint8_t const s_unmaptbl[256] = {0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x00 to 0x0F */4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x10 to 0x1F */5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x20 to 0x2F */4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x30 to 0x3F */6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x40 to 0x4F */4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x50 to 0x5F */5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x60 to 0x6F */4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x70 to 0x7F */7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x80 to 0x8F */4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x90 to 0x9F */5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xA0 to 0xAF */4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xB0 to 0xBF */6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xC0 to 0xCF */4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xD0 to 0xDF */5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xE0 to 0xEF */4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 /* 0xF0 to 0xFF */};
现在查找字节最开始出现1的位置查表一步就得到了时间是固定的，那么查找字节按照前面介绍还是的从字节0开始查询最开始不是0的字节。我们仔细思考一下，前面一个字节8个bit一行的角度去查找最开始的1是对应的列，现在查找字节不就是对应的行吗。
那么我们把每一行是否是0先记录下来，再用一个bitmap来记录这一行是否为0不就行了吗。如下所示我们原来的bitmap有8个字节，8行，那么我们再使用一个字节8个bit就可以记录这8个字节是否为0了，这个新增的bitmap我们叫做grp。
如果原来bitmap的字节1为0则grp的bit0为0，否则为1表示这个字节中有1即有空闲块。那么问题简单了，查找这8个字节，最低字节不为0的字节，即查找这个grp的最低位最先出现的1，这样问题归一了，就是我们前面的查表。这样要找最低字节的最低先出现的1就是两步查表，先根据grp查找到字节位置，然后根据这个字节的值查找bit位置。最终的索引就是”字节位置*8+bit位置”
最终算法实现如下
y = s_unmaptbl[dev->grp];x = s_unmaptbl[dev->tbl[y]];index = (uint8_t)((y<<3) + x);
这里的dev->grp即我们上面的grp字节，
Dev->tbl即bitmap字节数组。
y即字节位置，x即bit位置，index即bitmap的索引位置。
而找bitmap索引将对应的bit改为0即申请，操作如下，index>>3得到字节索引，~(1u<<(index & 0x07)是清除对应的bit。如果这个字节变为了0，则相应的grp字节的对应bit也要清零
if(((dev->tbl[index3] &= (~(1u<<(index & 0x07)))) == 0)){dev->grp &= ~(1u<<(index3));}
释放则是将bitmap对应索引位置的bit置为1，
dev->grp |= 1u<<(index>>3);dev->tbl[index>>3] |= 1u<<(index & 0x07);
举例如下
Tbl的2~7字节都非0所以，grp的bit2~bit7都为1，
tbl中最低字节最低位出现的1是字节2的bit3.
计算过程如下，先grp=0xFC=252查表得到，索引252处的值为2，所以定位到字节2
Tbl[2]的值为0x08，查表得到该索引对应的值是3
所以最开始出现1的位置是字节2的bit3，即2*8+3=19.
源码如下
Mem_pool.c
static uint8_t const s_unmaptbl[256] = {0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x00 to 0x0F */4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x10 to 0x1F */5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x20 to 0x2F */4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x30 to 0x3F */6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x40 to 0x4F */4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x50 to 0x5F */5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x60 to 0x6F */4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x70 to 0x7F */7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x80 to 0x8F */4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x90 to 0x9F */5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xA0 to 0xAF */4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xB0 to 0xBF */6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xC0 to 0xCF */4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xD0 to 0xDF */5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xE0 to 0xEF */4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 /* 0xF0 to 0xFF */};int mem_pool_init(mem_pool_st* dev, void* buffer, void* tbl, uint32_t itemsize, uint32_t itemnum){if(dev == (mem_pool_st*)0){return -1;}if((buffer == (void*)0) || (tbl == (void*)0)){return -1;}dev->buffer = buffer;dev->itemnum = itemnum;dev->itemsize = itemsize;dev->grp = (uint8_t)0xFF;dev->tbl = tbl;for(uint32_t i=0; i< (dev->itemnum+7)/8; i++){dev->tbl[i] = (uint8_t)0xFF;}return 0;}uint8_t* mem_pool_malloc(mem_pool_st* dev){/* 查找最靠前的,空闲的块 */if(dev == (mem_pool_st*)0){return (void*)0;}if((dev->buffer == (void*)0) || (dev->tbl == (uint8_t*)0)){return (void*)0;}uint8_t y;uint8_t x;uint8_t index;y = s_unmaptbl[dev->grp];x = s_unmaptbl[dev->tbl[y]];index = (uint8_t)((y<<3) + x);if((index == 0) && (dev->tbl[0]==0)){/* 找到的索引为0,且对应的tbl为0, 说明bitmap所有位都为0,即无空闲 */return (void*)0;}else{/* 对应bit置0,表示已经占用 */if(((dev->tbl[index>>3] &= (~(1u<<(index & 0x07)))) == 0)){dev->grp &= ~(1u<<(index>>3));}/* 返回对应的地址 */return dev->buffer + dev->itemsize*index;}}int mem_pool_free(mem_pool_st* dev, uint8_t* buffer){if(dev == (mem_pool_st*)0){return -1;}if((dev->buffer == (void*)0) || (dev->tbl == (uint8_t*)0)){return -1;}if(buffer == (void*)0){return -2;}uint8_t index;index = (buffer - dev->buffer)/dev->itemsize;if(((dev->grp & (1u<<(index>>3))) != 0) && ((dev->tbl[index>>3] & (1u<<(index & 0x07))) != 0)){/* 释放空闲的块 */return -3;}/* 设置对应bit位置为1表示空闲 */dev->grp |= 1u<<(index>>3);dev->tbl[index>>3] |= 1u<<(index & 0x07);return 0;}
Mem_pool.h
extern "C" {typedef struct{uint32_t grp;uint32_t itemsize; /**< 区块大小 */uint32_t itemnum; /**< 总区块数,8的倍数,最多256 */uint8_t* buffer; /**< 用户提供的缓存区,大小为itemsize*itemnum */uint8_t* tbl;} mem_pool_st;int mem_pool_init(mem_pool_st* dev, void* buffer, void* tbl, uint32_t itemsize, uint32_t itemnum);uint8_t* mem_pool_malloc(mem_pool_st* dev);int mem_pool_free(mem_pool_st* dev, uint8_t* buffer);}
我们将其替换到我们某个驱动的实现中的malloc和free调用，测试功能OK，并按照二测试其时间抖动和执行时间，确认执行时间非常短，且基本无抖动。
初始化代码如下
static dma_trans_t s_trans_buffer[TRANS_POOL_NUM];static uint8_t s_trans_bitmap_buffer[(TRANS_POOL_NUM+7)/8];static mem_group_info_t s_group_buffer[GROUP_POOL_NUM];static uint8_t s_group_bitmap_buffer[(GROUP_POOL_NUM+7)/8];mem_pool_st s_trans_mem_pool_dev;mem_pool_st s_group_mem_pool_dev;mem_pool_init(&s_trans_mem_pool_dev, s_trans_buffer, s_trans_bitmap_buffer, sizeof(dma_trans_t), TRANS_POOL_NUM);mem_pool_init(&s_group_mem_pool_dev, s_group_buffer, s_group_bitmap_buffer, sizeof(mem_group_info_t), GROUP_POOL_NUM);
申请
trans = (dma_trans_t *)mem_pool_malloc(&s_trans_mem_pool_dev);释放
mem_pool_free(&s_trans_mem_pool_dev, trans);以上我们借鉴uCOSII中的算法应用到我们自己设计的内存池轮子上，实现了高效且无时间抖动的内存池实现，是一个非常有用的轮子。这也提醒我们平常多注意借鉴参考别人的思想实现，并为己所用，不断积累。
以上实际使用的是bitmap查表实现固定时间，使用二维bitmap来扩充容量，上述例子是支持最大块数64个即8x8。如果要扩充更大的块数怎么办呢，自然想到得是增加二维的X/Y即可，即可将tbl和grp由8位改为16位，但是这存在一个问题，改为16位查表的表有2^16种情况,需要64k这在嵌入式中很可能是不可接受的。我们再来思考前面tbl扩展到grp，即X扩展到Y的过程，即一维扩展到二维的过程，我们是不是突然眼前一亮，拍案而起，甚至有点激动了，是的很自然的我们可以再增加一维变为三维，即对于体中点得位置，可以先找面，再找行，再找行中的bit点，就是这么简单自然，所以只需要将grp也改为数组即可，再增加一个vol字节对grp数组进行记录，vol一个bit 记录grp一个字节是否为0。所以我们要从本质去理解一项技术才可能是正真得理解，比好比这个查表从维度扩充角度去思考这才是本质，懂了这个本质自然会扩充，并为己所用应用到其他场景，而不是纠结于查表等技术细节，纠结于这些实际并没有理解本质，也仅仅会这个案例而已很难举一反三，这也是我们为什么思考问题一定要思考到本质，为什么我一直强调思考技术问题一定要思考到背后的本质甚至哲学意义，背后的原理甚至哲学意义才是普适得本质原理。
我们通过增加维度实现扩充，这就是降维打击，三阶搜寻变为了三次查表，有点类似”对数的本质是把乘除法降维成加减法”，也许四维度空间生物看我们三维空间的生物是多么的藐视了。
不由的要感叹世界的奇妙，也许只有造物主能做到，能够降维实际也是一种普遍的现象，可能也是造物主虽然没有让我们活在高维世界但是给我们开了个后门，让我们拥有了对高维进行降维分析的能力，对数降维，投影降维等都类似，可以让我们从侧面推测全貌，不知道能否从数学抽象角度来建立体系，证明具备何种属性的空间具备可降维性，那么这就建立了一套分析高维的数理体系了。
