基于哈希的用户态内存申请固定缓存方法

本发明涉及一种用户态内存申请固定方法，更具体的说，尤其涉及一种基于哈希的用户态内存申请固定缓存方法。

现在越来越多的公司从云服务商租借IT设施，而不是构建他们自己的设备，因为云带来了诸多的好处，例如简单管理，高可扩展性，低开销等。在云平台上，云存储是一个非常重要的服务。对于云服务提供商来说，构建高吞吐、低延迟并消耗可控资源的存储服务是一个急切的需求。众所周知，一个存储服务的质量取决于软件和硬件两个因素，所以云存储提供商必须要经常从这两个方面去更新组件，提升云存储的性能。在低速存储设备时代，一个存储服务的性能瓶颈主要是在硬件组件上，因为软件上的开销相比硬件来说占比要小很多。HDD(hard disk drives)处理IO请求的延迟大于2毫秒，而软件处理IO请求的延迟为微妙级别，差一个数量级。但是随着基于NAND FLASH存储颗粒SSD(Solid State Drive，固态硬盘)的出现，这种情况就开始改变。在硬件上处理IO请求的延迟变得越来越低，甚至小于100微秒，此时软件开销成为了存储应用程序性能提升的主要瓶颈。当前新型的存储介质3Dxpoint(一种存储芯片)的访问延迟越来越接近内存的延迟，导致软件上的开销显得越来越突出。

根据INTEL在存储软件栈上的研究显示，内核软件栈占据了大量的执行时间，主要包括如下的一些开销，用户态和内核态之间的上下文切换开销，在内核态和用户态之间的数据拷贝，IO请求的中断处理操作，在内核IO栈上共享资源的竞争等。同样，内核级别的IO优化仍然有一些限制，导致很难满足用户应用程序的需求。第一，内核必要要足够通用，因为它对应用程序提供一个抽象层，管理所有的硬件资源。因此，很难在不损失通用性的情况下去优化内核。第二，内核也无法实现任何专门针对某些应用程序优化的策略，因为它必须要在应用程序中提供公平性。第三，内核的不断更新也需要移植此类特定应用程序的优化。

自从存储设备的硬件延迟降低到只有几微秒之后，存储IO栈上的研究就处于一个热点状态。Linux协会近来准备应用从网络IO子系统上的一些优化手段到块设备IO子系统上，例如，blk-poll是一个通用的框架，能够允许设备驱动去实现自定义的轮询函数针对一个特定的存储设备。面向一个NVMe(Non-Volatile Memory express，NVMe存储系统)的原型设备利用轮询方式同样实现了同步和异步IO处理模型。而新型存储设备NVMe需要基于几个新的特点重新设计块设备IO子系统，Huffman在2012年提出了利用多队列模型。在内核空间，也提出了在多核上分配多个队列来提升SSD的性能。为了减少由于上下文切换造成的延迟调度开销，提出了一个低延迟的IO完成机制基于低级别的硬件抽象层。尽管针对内核存在的一些问题进行了优化，但是仍然有一些开销无法避免，研究者已经尝试旁路内核直接在用户态访问快速存储设备。

从上述研究方向可以看出，在存储IO栈上主要解决的问题就是用户态和内核态之间的上下文切换开销，在内核态和用户态之间的数据拷贝，IO请求的中断处理操作，在内核IO栈上共享资源的竞争等。目前研究趋势偏向于在用户态直接访问快速存储设备SSD。但是也会带来一些新的问题，例如，在用户态直接访问快速存储设备时由于可能存在修改虚拟地址到物理地址映射关系的情况，所以需要在进行DMA(Direct Memory Access，直接存储器访问)操作时对内存进行固定操作，保持在DMA操作执行过程中虚拟地址到物理地址的映射关系不变，这是有一定的开销的，在面对IO密集型应用时频繁的固定内存会严重降低应用的IO请求执行效率。目前对DMA缓冲区操作的研究主要集中在网络方面，例如多种针对RDMA(RemoteDirect Memory Access，远程直接内存访问)缓冲区的研究，尚没有针对用户态直接访问快速存储设备时的DMA缓冲区研究。

本发明的目的就是提供一种基于哈希的用户态内存申请固定缓存方法，在用户态直接访问NVMe设备的系统中减少用户态内存频繁申请固定释放的开销。

本发明的技术方案是：

基于哈希的用户态内存申请固定缓存方法，其特征在于，包括以下步骤：

1)按照用户期望使用的内存大小申请并固定相应大小的用户态内存；

2)释放用户使用完的用户态内存；

其中，步骤1)包括以下步骤：

步骤(1.1)获得用户期望使用的内存大小size；

步骤(1.2)首先在缓存用户态内存块的哈希表中查是否有长度为size的内存块链表，如果到执行步骤(1.3)，如果没有到执行步骤(1.4)；

步骤(1.3)获取哈希表中长度为size的内存块链表首地址，删除掉链表中的第一个内存块，然后执行步骤(1.9)；

步骤(1.4)哈希表中查是否有比size更大的内存块链表，如果没有执行步骤(1.5)，如果有执行步骤(1.6)；

步骤(1.5)从大内存池中申请并固定size大小的用户态内存，并执行步骤(1.9)；

步骤(1.6)获得哈希表中第一个比size大的内存块链表，删除掉表中的第一个内存块，并将这个内存块划分为两个部分，其中一部分大小为size，执行步骤(1.7)；

步骤(1.7)获得划分后的另一块内存大小a_size，在哈希表中查是否有相应大小的内存块链表，如果有直接加入链表，没有执行步骤(1.8)；

步骤(1.8)首先创建一个哈希表项，该表项中标记的内存块大小为a_size，并创建一个链表，链表中加入划分后的另一块内存，并标记新建的哈希表项指向这个新建的链表，执行步骤(1.9)；

步骤(1.9)返回相应size大小的内存块的首地址。

步骤2)包括以下步骤：

步骤(2.1)首先查看当前哈希表中缓存的所有内存容量是否达到最大阈值，超出之后执行步骤(2.2)，没有超出执行步骤(2.3)；

步骤(2.2)按照内存大小从小到大删除部分内存块，直到哈希表中缓存的所有内存容量为最小阈值；

步骤(2.3)获得当前删除内存块的首地址，在缓存池中向前搜索当前删除的内存块是否能合并成为更大的一块，然后在缓存池中向后搜索是否能合并成为更大的一块，合并完成后在哈希表中删除合并之前的内存块；

步骤(2.4)获得合并后的内存块大小b_size，首先查看当前哈希表中是否有相应大小的内存块链表，如果有执行步骤(2.5)，如果没有执行步骤(2.6)；

步骤(2.5)获得b_size大小的哈希表项中的内存块链表，将当前合并后的内存块直接加入；

步骤(2.6)创建一个哈希表项，该表项中标记的内存块大小为b_size，并创建一个链表，链表中加入合并后的内存块，并标记新建的哈希表项指向这个新建的链表。

本发明的有益效果是：基于哈希的用户态内存申请固定缓存方法，应用于基于用户态直接访问NVMe设备的系统中，减少用户态内存频繁申请固定释放的开销。通过利用哈希的方法，能够在O(1)的时间复杂度内查到相应大小的申请固定好的内存返回给用户使用，并且在释放时能够前后合并内存块大小，满足较大内存场景的需求。并且在释放时放到一个哈希表链接的缓存池中，能够将一个申请固定内存开销分摊到多个操作中，减少用户态申请固定内存的开销，提高系统的性能，减少IO请求的处理延迟。

图1为本发明的基于哈希的用户态内存申请固定缓存方法的申请内存流程图。

图2为本发明的基于哈希的用户态内存申请固定缓存方法的释放内存流程图。

以下结合附图(图1-图2)对本发明作进一步详细的说明。

图1为本发明的基于哈希的用户态内存申请固定缓存方法的申请内存流程图。图1中包括以下步骤：步骤A1，获取申请固定内存大小；步骤A2，判断哈希表是否有相应大小的项，如果是，则进入步骤A5，如果否，则进入步骤A3；步骤A3，判断哈希表是否有更大的项，如果是，则进入步骤A4，如果否，则在大内存池中申请并固定后进入步骤A5；步骤A4，划分内存块为两部分，一部分插入哈希表中，另一部分返回；步骤A5，返回申请固定内存块。图2为本发明的基于哈希的用户态内存申请固定缓存方法的释放内存流程图。图2中包括以下步骤：步骤B1，获取释放内存大小；步骤B2，判断内存容量是否最大阈值，如果是，则按照内存大小删除直到小于最小阈值后进入步骤B3，如果否，则直接进入步骤B3；步骤B3，在缓存池中向前和向后合并内存块；步骤B4，判断是否有合并后内存大小的项，如果是，则到相应的哈希表项直接插入后进入步骤B6，如果否，则进入步骤B5；步骤B5，创建一个哈希表项后插入；步骤6，函数返回。

本发明提供一种减少用户态访问NVMe设备时分配和固定内存开销的方法，应用于基于用户态直接访问NVMe设备的存储系统中，通过在释放使用完的固定内存时将这部分内存缓存起来，以供接下来的线程处理时使用，来减少重新分配和固定内存的开销，提高系统的性能，减少IO请求的处理延迟。包括以下步骤：(a)按照用户期望使用的内存大小申请并固定相应大小的用户态内存；(b)释放用户使用完的用户态内存。通过利用哈希的方法，能够在O(1)的时间复杂度内查到相应大小的申请固定好的内存返回给用户使用，并且在释放时能够前后合并内存块大小，满足较大内存场景的需求。

基于哈希的用户态内存申请固定缓存方法，其特征在于，包括以下步骤：

1)按照用户期望使用的内存大小申请并固定相应大小的用户态内存，如图1所示；

2)释放用户使用完的用户态内存，如图2所示；

其中，步骤1)包括按照用户期望使用的内存大小申请并固定相应大小的用户态内存步骤：

步骤(1.1)获得用户期望使用的内存大小size；

步骤(1.2)首先在缓存用户态内存块的哈希表中查是否有长度为size的内存块链表，如果到执行步骤(1.3)，如果没有到执行步骤(1.4)；

步骤(1.3)获取哈希表中长度为size的内存块链表首地址，删除掉链表中的第一个内存块，然后执行步骤(1.9)；

步骤(1.4)哈希表中查是否有比size更大的内存块链表，如果没有执行步骤(1.5)，如果有执行步骤(1.6)；

步骤(1.5)从大内存池中申请并固定size大小的用户态内存，并执行步骤(1.9)；

步骤(1.6)获得哈希表中第一个比size大的内存块链表，删除掉表中的第一个内存块，并将这个内存块划分为两个部分，其中一部分大小为size，执行步骤(1.7)；

步骤(1.7)获得划分后的另一块内存大小a_size，在哈希表中查是否有相应大小的内存块链表，如果有直接加入链表，没有执行步骤(1.8)；

步骤(1.8)首先创建一个哈希表项，该表项中标记的内存块大小为a_size，并创建一个链表，链表中加入划分后的另一块内存，并标记新建的哈希表项指向这个新建的链表，执行步骤(1.9)；

步骤(1.9)返回相应size大小的内存块的首地址。

步骤2)释放用户使用完的用户态内存包括以下步骤：

步骤(2.1)首先查看当前哈希表中缓存的所有内存容量是否达到最大阈值，超出之后执行步骤(2.2)，没有超出执行步骤(2.3)；

步骤(2.2)按照内存大小从小到大删除部分内存块，直到哈希表中缓存的所有内存容量为最小阈值；

步骤(2.3)获得当前删除内存块的首地址，在缓存池中向前搜索当前删除的内存块是否能合并成为更大的一块，然后在缓存池中向后搜索是否能合并成为更大的一块，合并完成后在哈希表中删除合并之前的内存块；

步骤(2.4)获得合并后的内存块大小b_size，首先查看当前哈希表中是否有相应大小的内存块链表，如果有执行步骤(2.5)，如果没有执行步骤(2.6)；

步骤(2.5)获得b_size大小的哈希表项中的内存块链表，将当前合并后的内存块直接加入；

步骤(2.6)创建一个哈希表项，该表项中标记的内存块大小为b_size，并创建一个链表，链表中加入合并后的内存块，并标记新建的哈希表项指向这个新建的链表。

本发明说明书中未作详细描述的内容属于本领域专业技术人员公知的现有技术。在此指明，以上叙述有助于本领域技术人员理解本发明创造，但并非限制本发明创造的保护范围。任何没有脱离本发明创造实质内容的对以上叙述的等同替换、修饰改进和/或删繁从简而进行的实施，均落入本发明创造的保护范围。