高性能无锁(Lock-free) 内存池

时间：2023-01-10 19:42:46
http://blog.csdn.net/jadedrip/article/details/5787388

由于懒惰，一直脱到现在才完成，实在是罪过啊！很快会用它来改写我的无锁容器，嗯，如果我不懒惰的话。

稍微解释一下关键问题：

先分配一块内存，然后将内存划分为等大的内存格。每次调用 alloc 就分配一块内存格出去。

可分配内存是个链表，这个链表被直接贮存在未分配的内存里。换句话说，未被分配的内存格里存放了一个指针，这个指针指向下一个未被分配的空闲内存格。

另外，为了我们分配的内存可以被正确释放，还需要一个链表来贮存我们分配的内存列表，这里我把这个链表贮存在我们分配的内存首部。也就是每块分配的内存，前几个字节保存了下一块内存的指针。

我们通过 cas 争用的一个指针指向了链表头，分配内存的过程就是从链表头摘取一个内存格，而释放的过程就是在链表头挂上内存格（注意，都是链表头，因此只需要争用一个指针）。

设计上希望代码支持 64 位，考虑到64位指针本身就是64位，但是当前系统最高应该只使用了 48位，因此使用剩下的部分来作为 ABA 计数。如果你的程序没有使用 256T 以上就应该没有问题吧，嗯——大概。

 

内存池的初始大小最好是够大，如果在中途分配，可能由于几个线程同时进程分配内存而一下子分配好几块，由于串联可分配内存的操作是比较费时的，为了节约，我把他们全挂上了，如果你希望节约内存的分配量，可以牺牲 cpu时间，放弃多分配的内存。

 

这个很快会作为一个库的一个组件发布，这个库暂时被命名为 lugce, 谁有更好的名字可以推荐不？呵呵

 

照例发表源码：

[cpp]  view plain  copy
  1. /*  
  2.  * Copyright (C) 2010  Chen Wang ( China ) 
  3.  * Email: jadedrip@gmail.com 
  4.  * 
  5.  * This library is free software; you can redistribute it and/or 
  6.  * modify it under the terms of the GNU Lesser General Public 
  7.  * License as published by the Free Software Foundation; either 
  8.  * version 2.1 of the License, or (at your option) any later version. 
  9.  * 
  10.  * This library is distributed in the hope that it will be useful, 
  11.  * but WITHOUT ANY WARRANTY; without even the implied warranty of 
  12.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU 
  13.  * Lesser General Public License for more details. 
  14.  * 
  15.  * You should have received a copy of the GNU Lesser General Public 
  16.  * License along with this library; if not, write to the Free Software 
  17.  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA 
  18.  */  
  19. #pragma once  
  20. #include <exception>  
  21. #include "lockfree.hpp"  
  22. #if !defined(_MSC_VER) || (_MSC_VER < 1600)  
  23. #   define nullptr NULL  
  24. #endif  
  25. namespace lugce  
  26. {  
  27.     namespace lockfree  
  28.     {  
  29.         template< typename T, int blocksize=255 >  
  30.         class memory_pool  
  31.         {  
  32.             static const int objsize= sizeof(T) < sizeof(intptr_t) ? sizeof(intptr_t) : sizeof(T);  
  33.             static const int64 aba_inc  =0x0001000000000000LL;  // ABA 计数每次需要增加的值  
  34.             static const int64 aba_mark =0xFFFF000000000000LL;  // ABA Mark  
  35.             static const int64 ptr_mark =0x0000FFFFFFFFFFFFLL;      // 指针 Mark  
  36.         public:  
  37.             memory_pool()  
  38.             {  
  39.                 char *block=tadem_block();  
  40.                 _first_block=block;  
  41.                 _free_head.data=reinterpret_cast<intptr_t>(block)+sizeof(intptr_t)+objsize;   // 指向链表头  
  42.             }  
  43.             ~memory_pool()  
  44.             {  
  45.                 // 释放内存块  
  46.                 char * next=_first_block;  
  47.                 do{  
  48.                     char *p=next;  
  49.                     intptr_t x=*(intptr_t*)p;  
  50.                     next=(char*)x;  
  51.                     delete[] p;  
  52.                 }while(next);  
  53.             }  
  54.         public:  
  55.             /// 申请内存，返回一个指向新内存的指针  
  56.             T* alloc()  
  57.             {  
  58.                 /// 尝试从堆栈中弹出一个空闲索引  
  59.                 atomic_int64 nval;  
  60.                 atomic_int64 old;  
  61.                 for(;;){  
  62.                     old=_free_head;  
  63.                     assert( (_free_head.data & ptr_mark) > 0x10000 );  
  64.                     intptr_t *next=reinterpret_cast<intptr_t*>( _free_head.data & ptr_mark ); // 指向下一块空闲单位的指针  
  65.                     if( *next==0 ){ // 没有空闲，需要创建新块  
  66.                         // 创建新块  
  67.                         create_new_block();  
  68.                         continue;  
  69.                     }  
  70.                     nval.data=( (old.data + aba_inc)  & aba_mark);  
  71.                     nval.data|=int64(*next);    // ABA 计数  
  72.                     //assert( (nval.data & ptr_mark) > 0x10000 );  
  73.                     if( atomic_cas( &_free_head, old.data, nval.data  ) )   
  74.                         break;  
  75.                 };  
  76.                 return reinterpret_cast<T*>(old.data & ptr_mark);  
  77.             }  
  78.             void free( const T* ptr )  
  79.             {  
  80.                 intptr_t *p=(intptr_t*)ptr;  
  81.                 atomic_int64 nval;  
  82.                 atomic_int64 old;  
  83.                 // 尝试将其放回链表  
  84.                 do{  
  85.                     old=_free_head;  
  86.                     *p=(intptr_t)(old.data & ptr_mark); // 把内容改为下一个空闲索引  
  87.                     assert(*p > 10000);  
  88.                     nval.data=((old.data + aba_inc) & aba_mark) | (intptr_t)ptr;  
  89.                     assert( (nval.data & ptr_mark) > 0x10000 );  
  90.                 }while( !atomic_cas(&_free_head, old.data, nval.data) );  
  91.             }  
  92.         private:  
  93.             /// 创建新的内存块  
  94.             void create_new_block()  
  95.             {  
  96.                 char *block=tadem_block();  // 分配内存  
  97.                 atomic_intptr_t *p=(atomic_intptr_t*)_first_block;  
  98.                 // 尝试挂接到内存块链表  
  99.                 while( !atomic_cas( p, 0, intptr_t(block) ) ){  
  100.                     p=(atomic_intptr_t*)(p->data);   // 移动到链表下一位  
  101.                 }  
  102.                 p=(atomic_intptr_t*)( block+sizeof(intptr_t) ); // 让 p 指向链表尾部  
  103.                 // 尝试挂接到空闲内存栈头上  
  104.                 atomic_int64 old;  
  105.                 atomic_int64 nval;  
  106.                 do{  
  107.                     old=_free_head;  
  108.                     p->data=intptr_t(old.data & ptr_mark);       // 让链表尾指向当前尾      
  109.                     intptr_t x=*(intptr_t*)(p->data);  
  110.                     assert( x==0 || x > 10000 );  
  111.                     assert(p->data>10000);  
  112.                     nval.data= ( (old.data + aba_inc) & aba_mark) | reinterpret_cast<int64>(block+sizeof(intptr_t)+objsize);  // 新的下块空闲指向本块  
  113.                     assert( (nval.data & ptr_mark) > 0x10000 );  
  114.                 } while( !atomic_cas(&_free_head, old.data, nval.data ) );  
  115.             }  
  116.             /// 创建新内存块，并将内存串联为链表  
  117.             char* tadem_block()  
  118.             {  
  119.                 char *block=new char[blocksize * objsize+sizeof(intptr_t)]; // 准备一块内存，注意 new 可能抛出异常  
  120.                 char *p=block;  
  121.                 *reinterpret_cast<intptr_t*>(p)=0;    // 内存的头是对齐的，我们用来保存下一块内存的地址，以构建内存块链表（用来内存池析构时释放内存块）  
  122.                 p+=sizeof(intptr_t);  
  123.                 *reinterpret_cast<intptr_t*>(p)=0;    // 接下来的4个字节，同样是对齐的，作为链表的尾部  
  124.                 p+=objsize;  
  125.                 // 把这块内存做成链表  
  126.                 for( int32 i=0; i< blocksize-2; ++i ){  
  127.                     *reinterpret_cast<intptr_t*>(p)=reinterpret_cast<intptr_t>(p)+objsize;  // 内容成为指向下一块的空闲单元的指针  
  128.                     p+=objsize;  
  129.                 }  
  130.                 *reinterpret_cast<intptr_t*>(p)=reinterpret_cast<intptr_t>(block)+sizeof(intptr_t);     // 最后一块指向尾节点  
  131.                 return block;  
  132.             }  
  133.         private:  
  134.             char * _first_block;  
  135.             atomic_int64 _free_head;    // 下一个空闲块的索引  
  136.         };  
  137.     };  
  138. };  

顶
0
踩
标签：

相关文章