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