123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716 |
- #ifndef __TC_MALLOC_CHUNK_H
- #define __TC_MALLOC_CHUNK_H
- #include <iostream>
- #include <cassert>
- #include <stdlib.h>
- #include <string.h>
- #include <vector>
- using namespace std;
- namespace tars
- {
- /////////////////////////////////////////////////
- /**
- * @file tc_mem_chunk.h
- * @brief 内存分配器
- *
- */
- static const size_t kPageShift = 15;
- static const size_t kNumClasses = 78;
- static const size_t kPageSize = 1 << kPageShift;
- static const size_t kMaxSize = 256 * 1024;
- static const size_t kAlignment = 8;
- static const size_t kMaxPages = 1 << (20 - kPageShift);
- static const size_t kPageAlignment = 64;
- ////////////////////////////////////////////////////////////////////////////////////////////////////
- /**
- * 请求的内存大小与请求实际得到的内存大小的映射
- * 实际得到的内存大小与内存大小所属的大小类别的映射
- * 内存大小所属的大小类别与该内存大小类别需要的内存页的映射
- */
- class SizeMap
- {
- public:
- SizeMap() { Init(); }
- /*
- *size所属的尺寸类别
- */
- inline int SizeClass(int size)
- {
- return class_array_[ClassIndex(size)];
- }
- /*
- *尺寸类别cl对应的尺寸大小
- */
- inline size_t ByteSizeForClass(size_t cl)
- {
- return class_to_size_[cl];
- }
- /*
- *尺寸类别cl对应的页数
- */
- inline size_t class_to_pages(size_t cl)
- {
- return class_to_pages_[cl];
- }
- private:
- static inline size_t ClassIndex(int s)
- {
- const bool big = (s > kMaxSmallSize);
- const size_t add_amount= big ? (127 + (120<<7)) : 7;
- const size_t shift_amount = big ? 7 : 3;
- return (s + add_amount) >> shift_amount;
- }
- static inline int LgFloor(size_t n)
- {
- int log = 0;
- for (int i = 4; i >= 0; --i)
- {
- int shift = (1 << i);
- size_t x = n >> shift;
- if (x != 0)
- {
- n = x;
- log += shift;
- }
- }
- return log;
- }
- /*
- *初始化
- */
- void Init();
- size_t AlignmentForSize(size_t size);
- int NumMoveSize(size_t size);
- private:
- static const int kMaxSmallSize = 1024;
- static const size_t kClassArraySize = ((kMaxSize + 127 + (120 << 7)) >> 7) + 1;
- size_t class_to_size_[kNumClasses];
- size_t class_to_pages_[kNumClasses];
- unsigned char class_array_[kClassArraySize];
- };
- ////////////////////////////////////////////////////////////////////////////////////////////////////
- class Static
- {
- public:
- static SizeMap* sizemap()
- {
- return &_sizemap;
- }
- private:
- static SizeMap _sizemap;
- };
- ////////////////////////////////////////////////////////////////////////////////////////////////////
- /**
- * TC_Span内存分配器
- *
- * 用于分配sizeof(TC_Span)大小的内存块
- */
- class TC_SpanAllocator
- {
- public:
- TC_SpanAllocator() : _pHead(NULL), _pData(NULL) {}
- void* getHead() const { return _pHead; }
- /**
- * 初始化
- * @param pAddr, 地址, 换到应用程序的绝对地址
- * @param mem_size, 内存大小
- */
- void create(void* pAddr, size_t iSpanSize, size_t iSpanCount);
- /**
- * 连接上
- * @param pAddr, 地址, 换到应用程序的绝对地址
- */
- void connect(void* pAddr);
- /**
- * 重建
- */
- void rebuild();
- /**
- * 是否还有可用block
- *
- * @return bool
- */
- bool isSpanAvailable() const { return _pHead->_spanAvailable > 0; }
- /**
- * 分配一个区块
- *
- * @return void*
- */
- void* allocate();
- /**
- * 释放区块
- * @param pAddr
- */
- void deallocate(void *pAddr);
- #pragma pack(1)
- struct tagSpanAlloc
- {
- size_t _iSpanSize; /**span区块大小*/
- size_t _iSpanCount; /**span个数*/
- size_t _firstAvailableSpan; /**第一个可用的span索引*/
- size_t _spanAvailable; /**可用span个数*/
- };
- #pragma pack()
- static size_t getHeadSize() { return sizeof(tagSpanAlloc); }
- protected:
- /**
- * 初始化
- */
- void init(void *pAddr);
- //禁止copy构造
- TC_SpanAllocator(const TC_SpanAllocator &mcm);
- //禁止复制
- TC_SpanAllocator &operator=(const TC_SpanAllocator &mcm);
- private:
- /**
- * 区块头指针
- */
- tagSpanAlloc *_pHead;
- /**
- * 数据区指针
- */
- unsigned char *_pData;
- };
- ////////////////////////////////////////////////////////////////////////////////////////////////////
- /**
- * 内存分配器
- *
- * 将连续的内存按32K大小分页
- * 并通过TC_Span和PageMap进行管理
- */
- class TC_Page
- {
- public:
- #pragma pack(1)
- struct tagShmFlag
- {
- bool _bShmProtectedArea; /*是否设置保护区*/
- int _iShmFlag; /*内存空间标识,内存未使用前为0,使用后为1*/
- size_t _iShmMemSize; /*内存空间大小*/
- size_t _iShmSpanAddr; /*TC_Span内存区的起始地址,相对地址*/
- size_t _iShmPageMapAddr; /*PageMap内存区的起始地址,相对地址*/
- size_t _iShmPageAddr; /*Data区的内存区的其实地址,相对地址*/
- size_t _iShmSpanNum; /*TC_Span内存区中span的个数*/
- size_t _iShmPageMapNum; /*PageMap内存区中map的个数*/
- size_t _iShmPageNum; /*Data内存区中页的个数*/
- };
- struct tagModifyData
- {
- size_t _iModifyAddr; /*修改的地址*/
- char _cBytes; /*字节数*/
- size_t _iModifyValue; /*值*/
- };
- struct tagModifyHead
- {
- char _cModifyStatus; /*修改状态: 0:目前没有人修改, 1: 开始准备修改, 2:修改完毕, 没有copy到内存中*/
- size_t _iNowIndex; /*更新到目前的索引*/
- tagModifyData _stModifyData[32]; /*一次最多32次修改*/
- };
- struct TC_Span
- {
- size_t start; /*span所管理的页内存的起始页号*/
- size_t length; /*页的个数*/
- size_t next;
- size_t prev;
- size_t objects; /*用于分配内存*/
- unsigned int refcount; /*按照sizeclass类大小划分span拥有的内存后的个数*/
- unsigned int sizeclass; /*内存大小的类别*/
- unsigned int location; /*用于识别该span是空闲,还是处于使用中*/
- enum { IN_USE, ON_FREELIST };
- };
- struct TC_CenterList
- {
- size_t size_class; /*内存大小的类别*/
- TC_Span empty; /*空闲链表*/
- TC_Span nonempty; /*非空闲链表*/
- };
- #pragma pack()
- public:
- TC_Page() : _pShmFlagHead(NULL),_pModifyHead(NULL),_pCenterCache(NULL),_pLarge(NULL),_pFree(NULL),_pSpanMemHead(NULL),_pPageMap(NULL),_pData(NULL) {}
- /**
- * 初始化
- * @param pAddr, 地址, 换到应用程序的绝对地址
- * @param iShmMemSize, 内存大小
- * @param bProtectedArea, 是否使用保护区
- */
- void create(void *pAddr, size_t iShmMemSize, bool bProtectedArea);
- /**
- * 连接上
- * @param pAddr, 地址, 换到应用程序的绝对地址
- */
- void connect(void *pAddr);
- /**
- * 重建
- */
- void rebuild();
- /**
- * 分配一个区块
- * @param iClassSize,需要分配的内存大小类别
- * @param iAllocSize, 分配的数据块大小
- * @param iPageId, 该内存所属的TC_Span的起始页号
- * @param iIndex, 该内存所属的TC_Span的按iAllocSize大小划分后的第iIndex个
- * @return void *
- */
- void* fetchFromSpansSafe(size_t iClassSize, size_t &iAllocSize, size_t &iPageId, size_t &iIndex);
- /**
- * 释放内存, 根据该内存所属TC_Span的起始页和该TC_Span按大小类别划分后的第iIndex个
- * @param iPageId, 该内存所属的TC_Span的起始页号
- * @param iIndex, 该内存所属的TC_Span的按iAllocSize大小划分后的第iIndex个
- */
- void releaseToSpans(size_t iPageId, size_t iIndex);
- /**
- * 释放内存, 绝对地址
- * @param pAddr
- */
- void releaseToSpans(void* pObject);
- /**
- * 根据该内存所属TC_Span的起始页和该TC_Span按大小类别划分后的第iIndex个得到该内存块的起始绝对地址
- * @param iPageId, 该内存所属的TC_Span的起始页号
- * @param iIndex, 该内存所属的TC_Span的按iAllocSize大小划分后的第iIndex个
- */
- void* getAbsolute(size_t iPageId, size_t iIndex);
- /**
- * 修改更新到内存中
- */
- void doUpdate(bool bUpdate = false);
- /**
- * 获得用于存放数据的页内存的数量
- */
- inline size_t getPageNumber();
- /**
- * 获得用于存放数据的页内存的大小
- */
- inline size_t getPageMemSize();
- /**
- * 获得TC_Page所管理内存的结束位置
- */
- inline size_t getPageMemEnd();
- /**
- * 传给TC_Page的内存的最小大小
- */
- static size_t getMinMemSize()
- {
- return sizeof(tagShmFlag) + sizeof(tagModifyHead) + sizeof(TC_CenterList) * kNumClasses + sizeof(TC_Span) + sizeof(TC_Span) * kMaxPages + TC_SpanAllocator::getHeadSize() + sizeof(TC_Span) + sizeof(size_t) + kPageSize;
- }
- protected:
- //禁止copy构造
- TC_Page(const TC_Page &mcm);
- //禁止复制
- TC_Page &operator=(const TC_Page &mcm);
- /**
- * 初始化
- */
- void init(void *pAddr);
- /**
- * 按页初始化用于存放数据的内存
- */
- void initPage(void *pAddr);
- /////////////////////////////////////////////////////////////////////////////////////////////////
- /**
- * 初始化list双向链表
- */
- inline void DLL_Init(TC_Span* list, size_t iIndex);
- /**
- * 从双向链表中删除span指向的节点
- */
- inline void DLL_Remove(TC_Span* span);
- /**
- * 将span指向的节点加入到双向链表list中
- */
- inline void DLL_Prepend(TC_Span* list, TC_Span* span);
- /**
- * 双向链表list是否为空
- */
- inline bool DLL_IsEmpty(TC_Span* list, size_t iIndex)
- {
- return list->next == iIndex;
- }
- //////////////////////////////////////////////////////////////////////////////////////////////////
- /**
- * 得到PageMap中第k个元素存放的指针值,其实际意义就是看Data内存区中第k块内存页属于哪个TC_Span管理
- */
- size_t Get(size_t k) const
- {
- return _pPageMap[k];
- }
- /**
- * 设置PageMap中第k个元素存放的指针值,其实际意义就是看Data内存区中第k块内存页属于哪个TC_Span管理
- */
- void Set(size_t k, size_t v)
- {
- _pPageMap[k] = v;
- }
- /**
- * 确保n未超过页内存的数目与k之差
- */
- bool Ensure(size_t k, size_t n)
- {
- return n <= _pShmFlagHead->_iShmPageMapNum -k;
- }
- //////////////////////////////////////////////////////////////////////////////////////////////////
- /**
- * create或rebuild的时候会调用,用于初始化时将所有的内存页映射到_pLarge上
- */
- bool UseShmMem();
- /**
- * 得到内存页pPageId属于哪个TC_Span管理
- */
- TC_Span* GetDescriptor(size_t pPageId);
- /**
- * 在_pFree或_pLarge链表中查找n块连续的内存页,通过TC_Span返回
- */
- TC_Span* SearchFreeAndLargeLists(size_t n);
- /**
- * 分配n块连续的内存页,通过TC_Span返回,里面会调用SearchFreeAndLargeLists函数
- */
- TC_Span* New(size_t n);
- /**
- * 在_pLarge链表中分配n块连续的内存页,通过TC_Span返回
- */
- TC_Span* AllocLarge(size_t n);
- /**
- * 在span所管理的内存页中,分配出n块连续内存
- */
- TC_Span* Carve(TC_Span* span, size_t n);
- /**
- * 根据span所管理的内存页的数目,将该span插入到_pLarge或_pFree链表中
- */
- void PrependToFreeList(TC_Span* span);
- /**
- * 将span从它所属的链表中删除,里面调用MergeIntoFreeList
- */
- void Delete(TC_Span* span);
- /**
- * 将span从它所属的链表中删除,并且查看该span所管理的内存页前后连续的内存页是否空闲,若是,则进行合并操作
- */
- void MergeIntoFreeList(TC_Span* span);
- /**
- * 设置span所管理的内存页将要进行分割的内存大小类别
- */
- void RegisterSizeClass(TC_Span* span, size_t sc);
- /**
- * 将span所属的内存页,映射到_pPageMap中
- */
- void RecordSpan(TC_Span* span);
- //////////////////////////////////////////////////////////////////////////////////////////////////
- /**
- * 分配一个区块
- * @param iClassSize,需要分配的内存大小类别
- * @param iAllocSize, 分配的数据块大小
- * @param iPageId, 该内存所属的TC_Span的起始页号
- * @param iIndex, 该内存所属的TC_Span的按iAllocSize大小划分后的第iIndex个
- * @return void *
- */
- void* FetchFromSpans(size_t iClassSize, size_t &iAllocSize, size_t &iPageId, size_t &iIndex);
- /**
- * 按iClassSize类别的内存大小分割内存页
- */
- int Populate(size_t iClassSize);
- /**
- * 修改具体的值
- * @param iModifyAddr
- * @param iModifyValue
- */
- //inline void update(void* iModifyAddr, size_t iModifyValue);
- template<typename T>
- void update(void* iModifyAddr, T iModifyValue)
- {
- _pModifyHead->_cModifyStatus = 1;
- _pModifyHead->_stModifyData[_pModifyHead->_iNowIndex]._iModifyAddr = reinterpret_cast<size_t>(iModifyAddr) - reinterpret_cast<size_t>(_pShmFlagHead);
- _pModifyHead->_stModifyData[_pModifyHead->_iNowIndex]._iModifyValue = iModifyValue;
- _pModifyHead->_stModifyData[_pModifyHead->_iNowIndex]._cBytes = sizeof(iModifyValue);
- _pModifyHead->_iNowIndex++;
- assert(_pModifyHead->_iNowIndex < sizeof(_pModifyHead->_stModifyData) / sizeof(tagModifyData));
- }
-
- private:
- /**
- * 头部内存块头指针
- */
- tagShmFlag *_pShmFlagHead;
- /**
- * 保护区内存块头指针
- */
- tagModifyHead *_pModifyHead;
- /**
- * 中央自由链表头指针
- */
- TC_CenterList *_pCenterCache;
- /**
- * 大块内存页的链表指针(大于等于1MB内存块的链表)
- */
- TC_Span *_pLarge;
- /**
- * 小块内存页的链表头指针(小于1MB的内存块)
- */
- TC_Span *_pFree;
- /**
- * 用于分配TC_Span的内存区域的头指针
- */
- TC_SpanAllocator *_pSpanMemHead;
- /**
- * 与数据区内存相映射的内存区头指针
- */
- //void **_pPageMap;
- size_t *_pPageMap;
- /**
- * 数据区的头指针
- */
- void *_pData;
- /**
- * 用于分配TC_Span的内存分配器
- */
- TC_SpanAllocator _spanAlloc;
- };
- ////////////////////////////////////////////////////////////////////////////////////////////////////
- class TC_MallocChunkAllocator
- {
- public:
- TC_MallocChunkAllocator():_pHead(NULL),_pChunk(NULL),_nallocator(NULL) {}
- ~TC_MallocChunkAllocator()
- {
- clear();
- }
- void clear()
- {
- if(_nallocator)
- {
- delete _nallocator;
- _nallocator = NULL;
- }
- _pHead = NULL;
- _pChunk = NULL;
- }
- /**
- * 初始化
- * @param pAddr, 地址, 换到应用程序的绝对地址
- * @param iSize, 内存大小
- * @param bProtectedArea, 是否使用保护区,默认使用
- */
- void create(void *pAddr, size_t iSize, bool bProtectedArea = true);
- /**
- * 连接上
- * @param pAddr, 地址, 换到应用程序的绝对地址
- */
- void connect(void *pAddr);
- /**
- * 扩展空间
- *
- * @param pAddr, 已经是空间被扩展之后的地址
- * @param iSize
- */
- void append(void *pAddr, size_t iSize);
- void* getHead() const { return _pHead; }
- /**
- * 总计内存大小, 包括后续增加的内存块的大小
- *
- * @return size_t
- */
- size_t getMemSize() const { return _pHead->_iTotalSize; }
- /**
- * 用于存放数据的总计内存大小, 包括后续增加的内存块的大小
- *
- */
- size_t getAllCapacity();
- /**
- * 每个chunk的大小, 包括后续增加的内存块的大小
- *
- * vector<size_t>
- */
- void getSingleCapacity(vector<size_t> &vec_capacity);
- /**
- * 根据该内存所属TC_Span的起始页和该TC_Span按大小类别划分后的第iIndex个,换算成绝对地址
- * @param iPageId
- * @param iIndex
- * @return void*
- */
- void* getAbsolute(size_t iPageId, size_t iIndex);
- /**
- * 分配一个区块,绝对地址
- *
- * @param iNeedSize,需要分配的大小
- * @param iAllocSize, 分配的数据块大小
- * @return void*
- */
- void* allocate(size_t iNeedSize, size_t &iAllocSize);
- /**
- * 释放区块, 绝对地址
- * @param pAddr
- */
- void deallocate(void* pAddr);
- /**
- * 分配一个区块
- * @param iNeedSize,需要分配的大小
- * @param iAllocSize, 分配的数据块大小
- * @param iPageId, 该内存所属的TC_Span的起始页号
- * @param iIndex, 该内存所属的TC_Span的按iAllocSize大小划分后的第iIndex个
- * @return void *
- */
- void* allocate(size_t iNeedSize, size_t &iAllocSize, size_t &iPageId, size_t &iIndex);
- /**
- * 释放内存, 根据该内存所属TC_Span的起始页和该TC_Span按大小类别划分后的第iIndex个
- * @param iPageId, 该内存所属的TC_Span的起始页号
- * @param iIndex, 该内存所属的TC_Span的按iAllocSize大小划分后的第iIndex个
- */
- void deallocate(size_t iPageId, size_t iIndex);
- /**
- * 重建
- */
- void rebuild();
- /**
- * 修改更新到内存中
- */
- void doUpdate(bool bUpdate = false);
- /**
- * 头部内存块
- */
- #pragma pack(1)
- struct tagChunkAllocatorHead
- {
- bool _bProtectedArea;
- size_t _iSize;
- size_t _iTotalSize;
- size_t _iNext;
- };
- #pragma pack()
- /**
- * 头部内存块大小
- */
- static size_t getHeadSize() { return sizeof(tagChunkAllocatorHead); }
- /**
- * 传递给此内存分配器的内存块大小要不小于函数的返回值
- */
- static size_t getNeedMinSize() { return sizeof(tagChunkAllocatorHead) + TC_Page::getMinMemSize(); }
- protected:
- void init(void *pAddr);
- void _connect(void *pAddr);
- TC_MallocChunkAllocator *lastAlloc();
- //禁止copy构造
- TC_MallocChunkAllocator(const TC_MallocChunkAllocator &);
- //禁止复制
- TC_MallocChunkAllocator& operator=(const TC_MallocChunkAllocator &);
- private:
- /**
- * 头指针
- */
- tagChunkAllocatorHead *_pHead;
- /**
- * chunk开始的指针
- */
- void *_pChunk;
- /**
- * chunk分配类
- */
- TC_Page _page;
- /**
- * 后续的多块分配器
- */
- TC_MallocChunkAllocator *_nallocator;
- };
-
- }
- #endif
|