1 /* Copyright The kNet Project. 2 3 Licensed under the Apache License, Version 2.0 (the "License"); 4 you may not use this file except in compliance with the License. 5 You may obtain a copy of the License at 6 7 http://www.apache.org/licenses/LICENSE-2.0 8 9 Unless required by applicable law or agreed to in writing, software 10 distributed under the License is distributed on an "AS IS" BASIS, 11 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 See the License for the specific language governing permissions and 13 limitations under the License. */ 14 #pragma once 15 16 /** @file LockFreePoolAllocator.h 17 @brief The PoolAllocatable<T> and LockFreePoolAllocator<T> template classes. */ 18 19 #include <iostream> 20 #include "Atomics.h" 21 22 namespace kNet 23 { 24 25 template<typename T> 26 struct PoolAllocatable 27 { 28 /// Points to the next item in the lock-free linked list. Do not access or 29 /// dereference this variable in client code, as it is used internally by 30 /// LockFreePoolAllocator only. 31 T * volatile next; 32 }; 33 34 /// T must implement PoolAllocatable. 35 template<typename T> 36 class LockFreePoolAllocator 37 { 38 public: LockFreePoolAllocator()39 LockFreePoolAllocator() 40 :root(0) 41 { 42 } 43 ~LockFreePoolAllocator()44 ~LockFreePoolAllocator() 45 { 46 UnsafeClearAll(); 47 } 48 49 /// Allocates a new object of type T. Call Free() to deallocate the object. New()50 T *New() 51 { 52 // Currently the use of lockfree allocation pool is disabled, since it has a known race condition, documented below. 53 return new T(); 54 55 /* 56 for(;;) 57 { 58 T *allocated = root; 59 if (!allocated) // If the root is null, there are no objects in the pool, so we must create new from the runtime heap. 60 { 61 allocated = new T(); 62 allocated->next = 0; 63 return allocated; 64 } 65 66 ///\bug Note that this function is not thread-safe. Accessing allocated->next may already be dangling if another thread has deleted it. 67 T *newRoot = allocated->next; 68 69 if (CmpXChgPointer((void**)&root, newRoot, allocated)) 70 { 71 allocated->next = 0; 72 return allocated; 73 } 74 } 75 */ 76 } 77 Free(T * ptr)78 void Free(T *ptr) 79 { 80 delete ptr; 81 82 // Currently the use of lockfree allocation pool is disabled, since it has a known race condition. 83 /* 84 if (!ptr) 85 return; 86 87 assert(ptr != root); 88 89 for(;;) 90 { 91 ptr->next = root; 92 if (CmpXChgPointer((void**)&root, ptr, ptr->next)) 93 return; 94 } 95 */ 96 } 97 98 /// Deallocates all cached unused nodes in this pool. Thread-safe and lock-free. If you are manually tearing 99 /// down the pool and there are no other threads accessing this, you may call the even faster version 100 /// UnsafeClearAll(), which ignores compare-and-swap updates. ClearAll()101 void ClearAll() 102 { 103 while(root) 104 { 105 T *node = New(); 106 delete node; 107 } 108 } 109 110 /// A fast method to free all items allocated in the pool. 111 /// Not thread-safe, only call when you can guarantee there are no threads calling New() or Free(). UnsafeClearAll()112 void UnsafeClearAll() 113 { 114 assert(!DebugHasCycle()); 115 T *node = root; 116 while(node) 117 { 118 T *next = node->next; 119 delete node; 120 node = next; 121 } 122 root = 0; 123 } 124 125 /// A debugging function that checks whether the underlying linked list has a cycle or not. Not thread-safe! DebugHasCycle()126 bool DebugHasCycle() 127 { 128 T *n1 = root; 129 if (!n1) 130 return false; 131 T *n2 = n1->next; 132 while(n2 != 0) 133 { 134 if (n1 == n2) 135 return true; 136 137 n1 = n1->next; 138 n2 = n2->next; 139 if (n2) 140 n2 = n2->next; 141 } 142 return false; 143 } 144 145 /// A debugging function that prints out all the objects in the pool. Not thread-safe! DumpPool()146 void DumpPool() 147 { 148 using namespace std; 149 150 T *node = root; 151 cout << "Root: 0x" << ios::hex << root << ".Next: " << ios::hex << (root ? root->next : 0) << std::endl; 152 int size = 0; 153 if (node) 154 node = node->next; 155 while(node) 156 { 157 cout << "Node: 0x" << ios::hex << node << ".Next: " << ios::hex << (node ? node->next : 0) << std::endl; 158 node = node->next; 159 ++size; 160 } 161 cout << "Total: " << size << " elements." << endl; 162 } 163 164 private: 165 T * volatile root; 166 }; 167 168 } // ~kNet 169