I haven’t written some c++ now for a good six months, I’ve been busy within Unity, c#, and python for the most part, at the time of this post. This weekend I thought I would brush up a little bit, I thought back to some of the more challenging assignments I had back when I was in school. This one isn’t as wide in scope as that assignment, but it was a great exercise. I’m not one to jump into heavy template usage where it isn’t needed, but this sort of system really kind of depends on it for extensibility of multiple data types.
This turned out pretty great for an initial pass like this. It is a node based memory manager, you define a class that specifies how much memory you want each node to hold, as well as how many nodes. Each node can store up to that amount of memory. What I’ve always enjoyed about memory managers is just how the memory is contiguous, minimizing paging, performance gains if done right and really just helping to keep things organized.
How the CDataAllocator initializes nodes contiguously in memory
Here is the implementation:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 |
#pragma once namespace Chazix { #define recast_ reinterpret_cast #define stcast_ static_cast template <size_t S> class CDataAllocatorBase; using byte = unsigned char; constexpr const byte g_validPad = 0xAA; constexpr const byte g_emptyMem = 0xEE; //----------------------------------------------------------------------------------------------- struct SHeader { byte m_size[4]{ 0 }; }; //----------------------------------------------------------------------------------------------- template <size_t T> struct SPadding { byte m_pad[T]{ 0 }; }; //----------------------------------------------------------------------------------------------- #pragma pack(push, 1) template <size_t S> class CNode : public CListNode<CNode<S>> { public: void Init() { memset(&m_header, 0x00, sizeof(m_header)); *m_header.m_size = DataSize(); memset(&m_padInit, g_validPad, sizeof(m_padInit)); memset(m_data, g_emptyMem, sizeof(m_data)); memset(&m_padEnd, g_validPad, sizeof(m_padEnd)); } size_t DataSize() { return sizeof(m_data) / sizeof(byte); } private: SHeader m_header; SPadding<4> m_padInit; byte m_data[S]{ 0 }; SPadding<4> m_padEnd; friend class CDataAllocatorBase<S>; }; #pragma pack(pop) //----------------------------------------------------------------------------------------------- template <size_t S> class CDataAllocatorBase { public: CDataAllocatorBase(size_t nodeCount) : m_segments(nodeCount), m_totalSize(nodeCount * sizeof(CNode<S>)) { m_buffer = new byte[m_totalSize]; m_freeList = std::make_unique<CLinkedList<CNode<S>>>(); m_inUseList = std::make_unique<CLinkedList<CNode<S>>>(); for (auto i = 0; i < m_segments; ++i) { CNode<S>* node = recast_<CNode<S>*>(m_buffer + i * sizeof(CNode<S>)); node->Init(); m_freeList->Append(node); } } virtual ~CDataAllocatorBase() { delete[] m_buffer; m_freeList.reset(nullptr); m_inUseList.reset(nullptr); } template <typename T, typename ... C> T* Alloc(C ... args) { assert(sizeof(T) <= DataSize()); CNode<S>* node = m_freeList->PopFront(); assert(node != nullptr); // out of usable memory T* data = new (node->m_data) T(args...); m_inUseList->Append(node); return recast_<T*>(data); } template <typename T> void Delete(T* data) { /* => need to find node in m_inUseList that uses data * => would be more ideal to have header information to be able * => to grab the CNode<S> in O(k) time */ CNode<S>* iter = m_inUseList->Begin(); for (; iter != m_inUseList->End(); iter = m_inUseList->Step()) { if (memcmp(data, iter->m_data, DataSize()) == 0) { break; } } assert(iter != m_inUseList->End()); memset(iter->m_data, g_emptyMem, DataSize()); m_inUseList->Remove(iter); m_freeList->Append(iter); } size_t DataSize() { return m_dataSize; } protected: size_t m_dataSize{ S }; size_t m_segments{ 0 }; size_t m_totalSize{ 0 }; std::unique_ptr<CLinkedList<CNode<S>>> m_freeList{ nullptr }; std::unique_ptr<CLinkedList<CNode<S>>> m_inUseList{ nullptr }; byte* m_buffer{ nullptr }; }; //----------------------------------------------------------------------------------------------- // store up to 64 bytes per node class CDataAllocator64 : public CDataAllocatorBase<64> { public: CDataAllocator64(size_t nodeCount) : CDataAllocatorBase<64>(nodeCount) {}; }; } |
This is a simple example for how it can be used:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
static void TestDataAllocator64() { size_t nodeCount = 1 << 8; // 256 nodes CDataAllocator64 allocator(nodeCount); char* data = allocator.Alloc<char>(); strcpy_s(data, allocator.DataSize(), "this is a test"); std::vector<std::string*> stringData; for (int i = 0; i < nodeCount - 1; ++i) { stringData.push_back(allocator.Alloc<std::string>("this is a test")); } allocator.Delete(data); for (auto data : stringData) { allocator.Delete(data); } stringData.clear(); for (int i = 0; i < nodeCount; ++i) { stringData.push_back(allocator.Alloc<std::string>("this is a test")); } for (auto data : stringData) { allocator.Delete(data); } } |
Some of the improvements for this one could be: to associate a key to each node in it’s header, so when we delete we can collect it in O(k) time through an unordered_map. Right now I’m utilizing a linked list to traverse the nodes. Also, more information on how many nodes are free and in use. Another awesome improvement would be to mark a node as reusable, so we can pack more data into nodes that still have memory bytes available for storage. As well as padding validation, to make sure memory hasn’t been trampled. Maybe also, memory range verification when deleting data – to make sure it’s something that most likely can be deleted in the particular allocator. Just a few things I’ve been thinking about, it was a fun little exercise.