由于懶惰，一直脫到現在才完成，實在是罪過啊！很快會用它來改寫我的無鎖容器，嗯，如果我不懶惰的話。
稍微解釋一下關鍵問題：
先分配一塊內存，然后將內存劃分為等大的內存格。每次調用 alloc 就分配一塊內存格出去。
可分配內存是個鏈表，這個鏈表被直接貯存在未分配的內存里。換句話說，未被分配的內存格里存放了一個指針，這個指針指向下一個未被分配的空閑內存格。
另外，為了我們分配的內存可以被正確釋放，還需要一個鏈表來貯存我們分配的內存列表，這里我把這個鏈表貯存在我們分配的內存首部。也就是每塊分配的內存，前幾個字節(jié)保存了下一塊內存的指針。
我們通過 cas 爭用的一個指針指向了鏈表頭，分配內存的過程就是從鏈表頭摘取一個內存格，而釋放的過程就是在鏈表頭掛上內存格（注意，都是鏈表頭，因此只需要爭用一個指針）。
設計上希望代碼支持 64 位，考慮到64位指針本身就是64位，但是當前系統(tǒng)最高應該只使用了 48位，因此使用剩下的部分來作為 ABA 計數。如果你的程序沒有使用 256T 以上就應該沒有問題吧，嗯——大概。
內存池的初始大小最好是夠大，如果在中途分配，可能由于幾個線程同時進程分配內存而一下子分配好幾塊，由于串聯可分配內存的操作是比較費時的，為了節(jié)約，我把他們全掛上了，如果你希望節(jié)約內存的分配量，可以犧牲 cpu時間，放棄多分配的內存。
這個很快會作為一個庫的一個組件發(fā)布，這個庫暫時被命名為 lugce, 誰有更好的名字可以推薦不？呵呵
照例發(fā)表源碼：
[cpp] view plain copy/* * Copyright (C) 2010 Chen Wang ( China ) * Email: jadedrip@Gmail.com * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation; either * version 2.1 of the License, or (at your option) any later version. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this library; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ #PRagma once #include <exception> #include "lockfree.hpp" #if !defined(_MSC_VER) || (_MSC_VER < 1600) # define nullptr NULL #endif namespace lugce { namespace lockfree { template< typename T, int blocksize=255 > class memory_pool { static const int objsize= sizeof(T) < sizeof(intptr_t) ? sizeof(intptr_t) : sizeof(T); static const int64 aba_inc =0x0001000000000000LL; // ABA 計數每次需要增加的值 static const int64 aba_mark =0xFFFF000000000000LL; // ABA Mark static const int64 ptr_mark =0x0000FFFFFFFFFFFFLL; // 指針 Mark public: memory_pool() { char *block=tadem_block(); _first_block=block; _free_head.data=reinterpret_cast<intptr_t>(block)+sizeof(intptr_t)+objsize; // 指向鏈表頭 } ~memory_pool() { // 釋放內存塊 char * next=_first_block; do{ char *p=next; intptr_t x=*(intptr_t*)p; next=(char*)x; delete[] p; }while(next); } public: /// 申請內存，返回一個指向新內存的指針 T* alloc() { /// 嘗試從堆棧中彈出一個空閑索引 atomic_int64 nval; atomic_int64 old; for(;;){ old=_free_head; assert( (_free_head.data & ptr_mark) > 0x10000 ); intptr_t *next=reinterpret_cast<intptr_t*>( _free_head.data & ptr_mark ); // 指向下一塊空閑單位的指針 if( *next==0 ){ // 沒有空閑，需要創(chuàng)建新塊 // 創(chuàng)建新塊 create_new_block(); continue; } nval.data=( (old.data + aba_inc) & aba_mark); nval.data|=int64(*next); // ABA 計數 //assert( (nval.data & ptr_mark) > 0x10000 ); if( atomic_cas( &_free_head, old.data, nval.data ) ) break; }; return reinterpret_cast<T*>(old.data & ptr_mark); } void free( const T* ptr ) { intptr_t *p=(intptr_t*)ptr; atomic_int64 nval; atomic_int64 old; // 嘗試將其放回鏈表 do{ old=_free_head; *p=(intptr_t)(old.data & ptr_mark); // 把內容改為下一個空閑索引 assert(*p > 10000); nval.data=((old.data + aba_inc) & aba_mark) | (intptr_t)ptr; assert( (nval.data & ptr_mark) > 0x10000 ); }while( !atomic_cas(&_free_head, old.data, nval.data) ); } private: /// 創(chuàng)建新的內存塊 void create_new_block() { char *block=tadem_block(); // 分配內存 atomic_intptr_t *p=(atomic_intptr_t*)_first_block; // 嘗試掛接到內存塊鏈表 while( !atomic_cas( p, 0, intptr_t(block) ) ){ p=(atomic_intptr_t*)(p->data); // 移動到鏈表下一位 } p=(atomic_intptr_t*)( block+sizeof(intptr_t) ); // 讓 p 指向鏈表尾部 // 嘗試掛接到空閑內存棧頭上 atomic_int64 old; atomic_int64 nval; do{ old=_free_head; p->data=intptr_t(old.data & ptr_mark); // 讓鏈表尾指向當前尾 intptr_t x=*(intptr_t*)(p->data); assert( x==0 || x > 10000 ); assert(p->data>10000); nval.data= ( (old.data + aba_inc) & aba_mark) | reinterpret_cast<int64>(block+sizeof(intptr_t)+objsize); // 新的下塊空閑指向本塊 assert( (nval.data & ptr_mark) > 0x10000 ); } while( !atomic_cas(&_free_head, old.data, nval.data ) ); } /// 創(chuàng)建新內存塊，并將內存串聯為鏈表 char* tadem_block() { char *block=new char[blocksize * objsize+sizeof(intptr_t)]; // 準備一塊內存，注意 new 可能拋出異常 char *p=block; *reinterpret_cast<intptr_t*>(p)=0; // 內存的頭是對齊的，我們用來保存下一塊內存的地址，以構建內存塊鏈表（用來內存池析構時釋放內存塊） p+=sizeof(intptr_t); *reinterpret_cast<intptr_t*>(p)=0; // 接下來的4個字節(jié)，同樣是對齊的，作為鏈表的尾部 p+=objsize; // 把這塊內存做成鏈表 for( int32 i=0; i< blocksize-2; ++i ){ *reinterpret_cast<intptr_t*>(p)=reinterpret_cast<intptr_t>(p)+objsize; // 內容成為指向下一塊的空閑單元的指針 p+=objsize; } *reinterpret_cast<intptr_t*>(p)=reinterpret_cast<intptr_t>(block)+sizeof(intptr_t); // 最后一塊指向尾節(jié)點 return block; } private: char * _first_block; atomic_int64 _free_head; // 下一個空閑塊的索引 }; }; }; 頂0踩新聞熱點
疑難解答
