Click
Loading...
Searching...
No Matches
allocator.hh
1// -*- c-basic-offset: 4 -*-
2#ifndef CLICK_ALLOCATOR_HH
3#define CLICK_ALLOCATOR_HH
4
5#include <click/config.h>
6#include <click/glue.hh>
7#include <click/multithread.hh>
8#include <click/sync.hh>
9#include <typeinfo>
10#define CLICK_DEBUG_ALLOCATOR 0
11
12CLICK_DECLS
13
14#define ALLOCATOR_POISON 0xA2C188F1
15
16class pool_allocator_mt_base {
17public:
21 static void set_dying(bool v) {
22 _dying = v;
23 }
24 static bool dying() {
25 return _dying;
26 }
27private:
28 static bool _dying;
29protected:
30 static int _n_msg;
31};
32
58template <typename T, bool zero = false, int POOL_SIZE = 64, int POOL_COUNT = 32>
59class pool_allocator_mt : pool_allocator_mt_base { public:
60
61 typedef struct item_t{
62 struct item_t* next;
63#if CLICK_DEBUG_ALLOCATOR
64 uint32_t poison;
65#endif
66 } item;
67
68 typedef struct Pool_t {
69 Pool_t() {
70 first = 0;
71 count = 0;
72 }
73 item* first;
74 int count;
75
76 int find_count() {
77 int i = 0;
78 auto p = first;
79 while (p != 0) {
80 p = p->next;
81 i++;
82 }
83 return i;
84 }
85 } Pool;
86
87 typedef struct GlobalPool_t {
88 uint8_t _pad[sizeof(item)];
89 struct GlobalPool_t* next;
90 } GlobalPool;
91
92 pool_allocator_mt();
93 ~pool_allocator_mt();
94
95 void static_initialize() {
96 _pool.resize(click_max_cpu_ids(),Pool());
97 }
98
99 T* allocate_uninitialized() {
100#if CLICK_DEBUG_ALLOCATOR
101 _allocated++;
102 assert(_allocated >= _released);
103#endif
104 T* e;
105 Pool& p = _pool.get();
106#if CLICK_DEBUG_ALLOCATOR
107 assert(p.count == p.find_count());
108#endif
109 if (p.count == 0) {
110 _global_lock.acquire();
111 if (_global_count > 0) {
112#if CLICK_DEBUG_ALLOCATOR
113 click_chatter("Global pool retrieved by thread %d",click_current_cpu_id());
114#endif
115 p.first = (item*)_global_pool;
116 p.count = POOL_SIZE;
117 _global_pool = _global_pool->next;
118 _global_count--;
119 }
120 _global_lock.release();
121 if (!p.first) {
122 p.first = (item*)(CLICK_LALLOC(sizeof(T)));
123 if (zero) {
124 bzero(p.first,sizeof(T));
125 }
126#if CLICK_DEBUG_ALLOCATOR
127 _newed++;
128#endif
129 p.first->next = 0;
130 p.count++;
131 } else {
132#if CLICK_DEBUG_ALLOCATOR
133 assert( ((item*)(p.first))->poison == ALLOCATOR_POISON);
134 ((item*)(p.first))->poison = 0;
135#endif
136 }
137 } else {
138#if CLICK_DEBUG_ALLOCATOR
139 assert( ((item*)(p.first))->poison == ALLOCATOR_POISON);
140 ((item*)(p.first))->poison = 0;
141#endif
142 }
143 e = (T*)p.first;
144 p.first = p.first->next;
145 p.count--;
146#if CLICK_DEBUG_ALLOCATOR
147 assert(p.count == p.find_count());
148#endif
149
150#if CLICK_DEBUG_ALLOCATOR > 1
151 click_chatter("%s Allocate %p %d %d", typeid(T).name(), e,_released, _allocated);
152#endif
153 return e;
154 }
155
156 T* allocate(const T &t) {
157 T* e = allocate_uninitialized();
158 new(e) T(t);
159 return e;
160 }
161
162 T* allocate() {
163 T* e = allocate_uninitialized();
164 new(e) T();
165 return e;
166 }
167
168 void release_unitialized(T* e) {
169
170#if CLICK_DEBUG_ALLOCATOR
171 _released++;
172#if CLICK_DEBUG_ALLOCATOR > 1
173 click_chatter("%s Release %p %d %d", typeid(T).name(), e, _released, _allocated);
174#endif
175
176 assert(_released <= _allocated);
177#endif
178 Pool& p = _pool.get();
179 ++p.count;
180#if CLICK_DEBUG_ALLOCATOR
181 assert(((item*)e)->poison != ALLOCATOR_POISON);
182 ((item*)e)->poison = ALLOCATOR_POISON;
183#endif
184 if (unlikely(p.count == POOL_SIZE + 1)) {
185 _global_lock.acquire();
186 if (_global_count == POOL_COUNT-1 || dying()) {
187 _global_lock.release();
188 CLICK_LFREE(e,sizeof(T));
189 if (!dying()) {
190#if CLICK_DEBUG_ALLOCATOR
191 click_chatter("Global pool is full, freeing item");
192#endif
193 if (_n_msg++ < 5)
194 click_chatter("Extremly inefficient pool_allocator_mt for %s ! Change parameters !",typeid(T).name());
195 }
196 p.count --;
197 } else {
198 //Move current pool to global pool
199#if CLICK_DEBUG_ALLOCATOR
200 click_chatter("Pool for thread %d is full, putting the pool in the global list",click_current_cpu_id());
201#endif
202 _global_count++;
203 GlobalPool* new_pool = (GlobalPool*)(p.first);
204 new_pool->next = _global_pool;
205 _global_pool = new_pool;
206 _global_lock.release();
207 p.count = 1;
208 ((item*)e)->next = 0;
209 p.first = (item*)e;
210 }
211 } else {
212 ((item*)e)->next = p.first;
213 p.first = (item*)e;
214 }
215#if CLICK_DEBUG_ALLOCATOR
216 assert(p.count == p.find_count());
217#endif
218 }
219
220 void release(T* e) {
221 e->~T();
222 release_unitialized(e);
223 }
224
225private:
226
227 per_thread<Pool> _pool;
228 Spinlock _global_lock;
229 int _global_count;
230 GlobalPool* _global_pool;
231
232
233#if CLICK_DEBUG_ALLOCATOR
234 atomic_uint32_t _allocated;
235 atomic_uint32_t _released;
236 atomic_uint32_t _newed;
237#endif
238};
239
240template <typename T, int POOL_SIZE = 64, int POOL_COUNT = 32>
241class pool_allocator_aware_mt : pool_allocator_mt_base { public:
242
243 typedef struct Pool_t {
244 Pool_t() {
245 first = 0;
246 count = 0;
247 }
248 T* first;
249 int count;
250
251 int find_count() {
252 int i = 0;
253 T* p = first;
254 while (p != 0) {
255 p = (T*)p->pool_next_item;
256 i++;
257 }
258 return i;
259 }
260 } Pool;
261
262
263 pool_allocator_aware_mt();
264 ~pool_allocator_aware_mt();
265
266 bool initialized() {
267 return _pool.weight() == click_max_cpu_ids();
268 }
269
270 T* allocate_uninitialized() {
271#if CLICK_DEBUG_ALLOCATOR
272 _allocated++;
273 assert(_allocated >= _released);
274#endif
275 T* e;
276 Pool& p = _pool.get();
277#if CLICK_DEBUG_ALLOCATOR
278 assert(p.count == p.find_count());
279#endif
280 if (p.count == 0) {
281 _global_lock.acquire();
282 if (_global_count > 0) {
283#if CLICK_DEBUG_ALLOCATOR
284 click_chatter("Global pool retrieved by thread %d",click_current_cpu_id());
285#endif
286 p.first = _global_pool;
287 p.count = POOL_SIZE;
288 _global_pool = (T*)_global_pool->pool_next_pool;
289 _global_count--;
290 }
291 _global_lock.release();
292 if (!p.first) {
293 p.first = new T();
294#if CLICK_DEBUG_ALLOCATOR
295 _newed++;
296#endif
297 p.first->pool_next_item = 0;
298 p.count++;
299 } else {
300#if CLICK_DEBUG_ALLOCATOR
301 assert(p.first->poison == ALLOCATOR_POISON);
302 p.first->poison = 0;
303#endif
304 }
305 } else {
306#if CLICK_DEBUG_ALLOCATOR
307 assert(p.first->poison == ALLOCATOR_POISON);
308 p.first->poison = 0;
309#endif
310 }
311 e = p.first;
312 p.first = (T*)p.first->pool_next_item;
313 p.count--;
314#if CLICK_DEBUG_ALLOCATOR
315 assert(p.count == p.find_count());
316#endif
317 return e;
318 }
319
320 void release_unitialized(T* e) {
321#if CLICK_DEBUG_ALLOCATOR
322 _released++;
323 assert(_released <= _allocated);
324#endif
325 Pool& p = _pool.get();
326 ++p.count;
327#if CLICK_DEBUG_ALLOCATOR
328 assert(e->poison != ALLOCATOR_POISON);
329 e->poison = ALLOCATOR_POISON;
330#endif
331 if (unlikely(p.count == POOL_SIZE + 1)) {
332 _global_lock.acquire();
333 if (_global_count == POOL_COUNT-1 || dying()) {
334 _global_lock.release();
335 delete e;
336 if (!dying()) {
337#if CLICK_DEBUG_ALLOCATOR
338 click_chatter("Global pool is full, freeing item");
339#endif
340 click_chatter("Extremly inefficient pool_allocator_mt for %s ! Change parameters !",typeid(T).name());
341 }
342 p.count --;
343 } else {
344 //Move current pool to global pool
345#if CLICK_DEBUG_ALLOCATOR
346 click_chatter("Pool for thread %d is full, putting the pool in the global list",click_current_cpu_id());
347#endif
348 _global_count++;
349 T* new_pool = (T*)(p.first);
350 new_pool->pool_next_pool = _global_pool;
351 _global_pool = new_pool;
352 _global_lock.release();
353 p.count = 1;
354 e->pool_next_item = 0;
355 p.first = (T*)e;
356 }
357 } else {
358 e->pool_next_item = p.first;
359 p.first = e;
360 }
361#if CLICK_DEBUG_ALLOCATOR
362 assert(p.count == p.find_count());
363#endif
364 }
365
366private:
367
368 per_thread<Pool> _pool;
369 Spinlock _global_lock;
370 int _global_count;
371 T* _global_pool;
372
373
374#if CLICK_DEBUG_ALLOCATOR
375 atomic_uint32_t _allocated;
376 atomic_uint32_t _released;
377 atomic_uint32_t _newed;
378#endif
379};
380
381
382template <typename T, bool ZERO, int POOL_SIZE, int POOL_COUNT>
383pool_allocator_mt<T,ZERO,POOL_SIZE,POOL_COUNT>::pool_allocator_mt() : _pool(Pool()), _global_count(0),_global_pool(0) {
384#if CLICK_DEBUG_ALLOCATOR
385 _released = 0;
386 _allocated = 0;
387 _newed = 0;
388#endif
389}
390
391template <typename T, bool ZERO, int POOL_SIZE, int POOL_COUNT>
392pool_allocator_mt<T,ZERO,POOL_SIZE,POOL_COUNT>::~pool_allocator_mt() {
393 static_assert(sizeof(T) >= sizeof(Pool), "Allocator object is too small");
394#if CLICK_DEBUG_ALLOCATOR
395 int n_release = 0;
396#endif
397 while (_global_pool) {
398 item* p = (item*)_global_pool;
399 _global_pool = _global_pool->next;
400 item* next;
401 while (p) {
402 next = p->next;
403 CLICK_LFREE(p,sizeof(T));
404 p = next;
405#if CLICK_DEBUG_ALLOCATOR
406 n_release++;
407#endif
408 }
409 }
410 for (unsigned i = 0 ; i < _pool.weight(); i++) {
411 Pool &pool = _pool.get_value(i);
412 item* p = pool.first;
413 item* next;
414 while (p) {
415 next = p-> next;
416 CLICK_LFREE(p,sizeof(T));
417 p = next;
418#if CLICK_DEBUG_ALLOCATOR
419 n_release++;
420#endif
421 }
422 }
423#if CLICK_DEBUG_ALLOCATOR
424 click_chatter("Allocator : Newed %u, Freed %d, allocate() %u, released() %u",_newed,n_release,_allocated,_released);
425#endif
426 }
427
428
429template <typename T,int POOL_SIZE, int POOL_COUNT>
430pool_allocator_aware_mt<T,POOL_SIZE,POOL_COUNT>::pool_allocator_aware_mt() : _pool(Pool()),_global_count(0),_global_pool(0) {
431#if CLICK_DEBUG_ALLOCATOR
432 _released = 0;
433 _allocated = 0;
434 _newed = 0;
435#endif
436}
437
438template <typename T, int POOL_SIZE, int POOL_COUNT>
439pool_allocator_aware_mt<T,POOL_SIZE,POOL_COUNT>::~pool_allocator_aware_mt() {
440 static_assert(sizeof(T) >= sizeof(Pool), "Allocator object is too small");
441#if CLICK_DEBUG_ALLOCATOR
442 int n_release = 0;
443#endif
444 while (_global_pool) {
445 T* p = _global_pool;
446 _global_pool = (T*)_global_pool->pool_next_pool;
447 T* next;
448 while (p) {
449 next = (T*)p->pool_next_item;
450 delete p;
451 p = next;
452#if CLICK_DEBUG_ALLOCATOR
453 n_release++;
454#endif
455 }
456 }
457 for (unsigned i = 0 ; i < _pool.weight(); i++) {
458 Pool &pool = _pool.get_value(i);
459 T* p = pool.first;
460 T* next;
461 while (p) {
462 next = (T*)p->pool_next_item;
463 delete p;
464 p = next;
465#if CLICK_DEBUG_ALLOCATOR
466 n_release++;
467#endif
468 }
469 }
470#if CLICK_DEBUG_ALLOCATOR
471 click_chatter("Allocator : Newed %u, Freed %d, allocate() %u, released() %u",_newed,n_release,_allocated,_released);
472#endif
473}
474
475CLICK_ENDDECLS
476#endif
Spinlock
A recursive spinlock for SMP Click threads.
Definition sync.hh:439
Spinlock::release
void release()
Releases the Spinlock.
Definition sync.hh:534
Spinlock::acquire
void acquire()
Acquires the Spinlock.
Definition sync.hh:488
atomic_uint32_t
A 32-bit integer with support for atomic operations.
Definition atomic.hh:71
per_thread
Definition sync.hh:57
per_thread::resize
void resize(unsigned int max_cpu_id, T v)
Definition sync.hh:97
pool_allocator_mt
Definition allocator.hh:59
sync.hh
Classes for synchronizing among multiple CPUs, particularly in the Linux kernel.
Generated on Mon Nov 2 2026 11:59:47 for Click by doxygen 1.9.8