Click
Loading...
Searching...
No Matches
common.hh
1#ifndef CLICK_FLOWCOMMON_HH
2#define CLICK_FLOWCOMMON_HH
3#include <click/ring.hh>
4#include <click/multithread.hh>
5#include <functional>
6#include <click/allocator.hh>
7CLICK_DECLS
8
9#ifdef HAVE_FLOW
10
11#define DEBUG_CLASSIFIER_MATCH 0 //0 no, 1 build-time only, 2 whole time, 3 print table after each dup
12#define DEBUG_CLASSIFIER_RELEASE 0
13#define DEBUG_CLASSIFIER_TIMEOUT 0
14#define DEBUG_CLASSIFIER_TIMEOUT_CHECK 0 //1 check at release, 2 check at insert (big hit)
15#define DEBUG_CLASSIFIER 0 //1 : Build-time only, >1 : whole time, >2 lock prints
16
17#define HAVE_STATIC_CLASSIFICATION 0 || !HAVE_FLOW_DYNAMIC
18
19#define RELEASE_RESET 0
20#define RELEASE_KEEP 1
21#define RELEASE_EPOCH 2
22
23#define DEBUG_CLASSIFIER_CHECK 0
24
25#if DEBUG_CLASSIFIER > 1
26 #define debug_flow_2(...) click_chatter(__VA_ARGS__);
27 #define debug_flow(...) click_chatter(__VA_ARGS__);
28#elif DEBUG_CLASSIFIER
29 #define debug_flow(...) click_chatter(__VA_ARGS__);
30 #define debug_flow_2(...)
31#else
32 #define debug_flow(...)
33 #define debug_flow_2(...)
34#endif
35
36#if DEBUG_CLASSIFIER_CHECK || DEBUG_CLASSIFIER
37 #define flow_assert(...) assert(__VA_ARGS__);
38 #define FLOW_INDEX(table,index) table[index]
39#else
40 #define flow_assert(...)
41 #define FLOW_INDEX(table,index) table.unchecked_at(index)
42#endif
43
44class FlowControlBlock;
45class FCBPool;
46class FlowNode;
47class Element;
48
49union FlowNodeData{
50 uint8_t data_8;
51 uint16_t data_16;
52 uint32_t data_32;
53#if HAVE_LONG_CLASSIFICATION
54 uint64_t data_64;
55 void* data_ptr;
56#endif
57
58 explicit FlowNodeData() :
59#if HAVE_LONG_CLASSIFICATION
60 data_64(0)
61#else
62 data_32(0)
63#endif
64 {};
65
66#if HAVE_LONG_CLASSIFICATION
67 explicit FlowNodeData(uint8_t d) : data_64(d) {};
68 explicit FlowNodeData(uint16_t d) : data_64(d) {};
69 explicit FlowNodeData(uint32_t d) : data_64(d) {};
70 explicit FlowNodeData(uint64_t d) : data_64(d) {};
71#else
72 explicit FlowNodeData(uint8_t d) : data_32(d) {};
73 explicit FlowNodeData(uint16_t d) : data_32(d) {};
74 explicit FlowNodeData(uint32_t d) : data_32(d) {};
75 explicit FlowNodeData(uint64_t d) : data_32((uint32_t)d) {};
76#endif
77
78 inline bool equals(const FlowNodeData &other) {
79#if HAVE_LONG_CLASSIFICATION
80 return data_64 == other.data_64;
81#else
82 return data_32 == other.data_32;
83#endif
84 }
85
86 inline uint64_t get_long() const {
87#if HAVE_LONG_CLASSIFICATION
88 return data_64;
89#else
90 return data_32;
91#endif
92 }
93};
94
95typedef void (*SubFlowRealeaseFnt)(FlowControlBlock* fcb, void* thunk);
96
97#if HAVE_FLOW_DYNAMIC
98struct FlowReleaseChain {
99 SubFlowRealeaseFnt previous_fnt;
100 void* previous_thunk;
101};
102#else
103struct FlowReleaseChain {
104};
105#endif
106
107class FlowControlBlock {
108
109private:
110#if HAVE_FLOW_DYNAMIC
111 #ifdef FLOW_ATOMIC_USE_COUNT
112 atomic_uint32_t use_count;
113 #else
114 unsigned use_count;
115 #endif
116#endif
117
118 public:
119#if DEBUG_CLASSIFIER
120 int thread = -1;
121#endif
122 Timestamp lastseen; //Last seen is also used without sloppy timeout for cache purposes
123
124#if HAVE_CTX_GLOBAL_TIMEOUT
129 //0x20 is reserved, see below
130 #define FLOW_TIMEOUT_INLIST 0x40 //Timeout is already in release list
131 #define FLOW_TIMEOUT 0x80 //Timeout set
132 #define FLOW_TIMEOUT_SHIFT 8
133 #define FLOW_TIMEOUT_MASK 0x000000ff //Delta + lastseen timestamp in msec
134
135 FlowControlBlock* next;
136
137 inline bool hasTimeout() const {
138 return flags & FLOW_TIMEOUT;
139 }
140
141 inline bool timeoutPassed(Timestamp now) const {
142 unsigned t = (flags >> FLOW_TIMEOUT_SHIFT);
143 return t == 0 || (now - lastseen).msecval() > t;
144 }
145#endif
146
147 #define FLOW_EARLY_DROP 0x20
148 uint32_t flags;
149
150 inline void set_early_drop(bool set=true) {
151 if (set)
152 flags |= FLOW_EARLY_DROP;
153 else
154 flags &= ~FLOW_EARLY_DROP;
155 }
156
157 inline bool is_early_drop() const {
158 return flags & FLOW_EARLY_DROP;
159 }
160
161
162
163#if HAVE_FLOW_DYNAMIC
164 SubFlowRealeaseFnt release_fnt ;
165 void* thunk;
166#endif
167
168 FlowNode* parent;
169
170 union {
171 uint8_t data[0];
172 uint16_t data_16[0];
173 uint32_t data_32[0];
174 uint64_t data_64[0];
175 FlowNodeData node_data[0];
176 };
177 inline FlowNodeData& get_data() {
178 return node_data[0];
179 }
180 //No data after this
181
182 bool combine_data(uint8_t* data, Element* origin);
183 inline void initialize() {
184#if HAVE_FLOW_DYNAMIC
185 use_count = 0;
186#endif
187 flags = 0;
188#if DEBUG_CLASSIFIER
189 thread = -1;
190#endif
191#if HAVE_FLOW_DYNAMIC
192 release_fnt = 0;
193 thunk = 0;
194#endif
195#if HAVE_CTX_GLOBAL_TIMEOUT
196 next = 0; //TODO : only once?
197#endif
198 }
199
200
201#if HAVE_FLOW_DYNAMIC
202 inline void acquire(int packets_nr = 1);
203 inline void release(int packets_nr = 1);
204
205 inline void _do_release();
206
207 inline unsigned count() const {
208 return use_count;
209 }
210
211 inline void reset_count(unsigned n) {
212 use_count = n;
213 }
214#else
215 inline void acquire(int packets_nr = 1) {
216 (void)packets_nr;
217 }
218 inline void release(int packets_nr = 1) {
219 (void)packets_nr;
220 }
221 inline int count() const {
222 return 0;
223 }
224#endif
225 FlowControlBlock* duplicate(unsigned use_count);
226 inline FCBPool* get_pool() const;
227
228 void print(String prefix, int data_offset =-1, bool show_ptr=false) const;
229 void reverse_print();
230 FlowNode* find_root();
231
232 bool empty();
233
237 void check() {
238 }
239
240 int hashcode() const;
241};
242
243class FlowControlBlockRef { public:
244
245 FlowControlBlock* _ref;
246
247 FlowControlBlockRef(FlowControlBlock* ref) {
248 _ref = ref;
249 }
250
251 typedef FlowControlBlockRef key_type;
252 typedef const FlowControlBlockRef &key_const_reference;
253
254 key_const_reference hashkey() const {
255 return const_cast<key_const_reference>(*this);
256 }
257
258 inline int hashcode() const {
259 return _ref->hashcode();
260 }
261};
262
263bool operator==(const FlowControlBlockRef &ra, const FlowControlBlockRef &rb);
264
265class FlowTableHolder;
266
267extern __thread FlowControlBlock* fcb_stack;
268extern __thread FlowTableHolder* fcb_table;
269
270
271#define SFCB_STACK_PUSH() FlowControlBlock* fcb_save = fcb_stack;fcb_stack=0;
272#define SFCB_STACK_POP() fcb_stack=fcb_save;
273#define SFCB_STACK(fnt) \
274 {SFCB_STACK_PUSH();fnt;SFCB_STACK_POP();}
275
276
277#define CLICK_DEBUG_FCBPOOL 0
278
279#define SFCB_POOL_COUNT 32
280#define SFCB_POOL_SIZE 2048
281class FCBPool {
282private:
283 class SFCBList {
284 private:
285 FlowControlBlock* _p;
286 unsigned _count;
287 public:
288
289 operator int() const { return _count; }
290
291 SFCBList (int c) : _p(0), _count( c ) {
292 }
293
294 SFCBList() : _p(0), _count(0) {
295 }
296
297 inline void reset() {
298 _p = 0;
299 _count = 0;
300 }
301
302 inline void assign(SFCBList list) {
303 flow_assert(_p == NULL);
304 flow_assert(_count == 0);
305 _count = list._count;
306 _p = list._p;
307 }
308
309 inline int count() const {
310 return _count;
311 }
312
313 inline void add(FlowControlBlock* fcb) {
314 flow_assert(fcb);
315#if CLICK_DEBUG_FCBPOOL
316 assert(*(((uint64_t*)fcb) + 1) != ALLOCATOR_POISON);
317 assert(fcb->count() == 0);
318 *(((uint64_t*)fcb) + 1) = ALLOCATOR_POISON;
319#endif
320 *((FlowControlBlock**)fcb) = _p;
321 _p = fcb;
322 _count++;
323 }
324
325 inline FlowControlBlock* get() {
326 FlowControlBlock* fcb = _p;
327 flow_assert(fcb);
328#if CLICK_DEBUG_FCBPOOL
329 assert(*(((uint64_t*)fcb) + 1) == ALLOCATOR_POISON);
330 *(((uint64_t*)fcb) + 1) = 0;
331#endif
332 _p = *((FlowControlBlock**)fcb);
333 _count--;
334 fcb->initialize();
335 return fcb;
336 }
337 };
338
339
340 inline FlowControlBlock* alloc_new() {
341 FlowControlBlock* fcb = (FlowControlBlock*)CLICK_LALLOC(sizeof(FlowControlBlock) + _data_size);
342 flow_assert(fcb);
343/*#if HAVE_FLOW_DYNAMIC
344 fcb->release_fnt = &pool_release_fnt;
345 fcb->thunk = this;
346#endif*/
347 fcb->initialize();
348 return fcb;
349 }
350
351 typedef MPMCRing<SFCBList,SFCB_POOL_COUNT> SFCBListRing;
352
353 SFCBListRing global_fcb_list_ring;
354
355
356 size_t _data_size;
357 per_thread_oread<SFCBList> lists;
358public:
359 static FCBPool* biggest_pool;
360 static int initialized;
361 static int init_data_size() {
362 return biggest_pool->data_size();
363 }
364
365 static FlowControlBlock* init_allocate();
366 static void init_release(FlowControlBlock*);
367
368 FCBPool() : _data_size(0), lists() {
369 }
370
371 ~FCBPool() {
372 //TODO
373 /*
374 //Free all per-thread caches
375 for (unsigned i = 0; i < lists.weight(); i++) {
376 SFCBList &list = lists.get_value(i);
377 FlowControlBlock* fcb;
378 while (list.count > 0 && (fcb = list.get()) != NULL) {
379 CLICK_LFREE(fcb,sizeof(FlowControlBlock) + _data_size);
380 }
381 }
382
383 //Free the caches inside the global ring
384 SFCBList list;
385 while ((list = global_fcb_list_ring.extract()) != 0) {
386 FlowControlBlock* fcb;
387 while (list.count > 0 && (fcb = list.get()) != NULL) {
388 CLICK_LFREE(fcb,sizeof(FlowControlBlock) + _data_size);
389 }
390 }*/
391 }
392
393
394 void initialize(size_t data_size, FlowTableHolder* table) {
395 _data_size = data_size;
396 if (!biggest_pool || biggest_pool->data_size() < data_size) {
397 biggest_pool = this;
398 fcb_table = table;
399 }
400 FCBPool::initialized++;
401 }
402
403 void compress(Bitvector threads);
404
405 inline FlowControlBlock* allocate() {
406 if (lists->count() > 0)
407 return lists->get();
408
409 SFCBList newlist;
410
411 newlist = global_fcb_list_ring.extract();
412 if (newlist.count()) {
413 lists->assign(newlist);
414 FlowControlBlock* fcb = lists->get();
415 return fcb;
416 } else {
417 FlowControlBlock* fcb = alloc_new();
418 flow_assert(fcb);
419 return fcb;
420 }
421 }
422
423 inline FlowControlBlock* allocate_empty() {
424 FlowControlBlock* fcb = allocate();
425 bzero(fcb->data + sizeof(FlowNodeData), data_size() - sizeof(FlowNodeData));
426 return fcb;
427 }
428
429 inline void release(FlowControlBlock* fcb) {
430 if (lists->count() >= SFCB_POOL_SIZE) {
431 global_fcb_list_ring.insert(lists.get());
432 lists->reset();
433 }
434 lists->add(fcb);
435 }
436
437 static void pool_release_fnt(FlowControlBlock* fcb, void* thunk) {
438 static_cast<FCBPool*>(thunk)->release(fcb);
439 }
440
441 size_t data_size() {
442 return _data_size;
443 }
444};
445
446class FlowTableHolder {
447public:
448
449 FlowTableHolder();
450 ~FlowTableHolder();
451
452 FCBPool* get_pool() {
453 return &_pool;
454 }
455
456
457#if HAVE_CTX_GLOBAL_TIMEOUT
458 void delete_all_flows();
459#endif
460 void set_release_fnt(SubFlowRealeaseFnt pool_release_fnt, void* thunk);
461
462
463 inline void release(FlowControlBlock* fcb) {
464 if (likely(_classifier_release_fnt)) //Release the FCB from the tree
465 _classifier_release_fnt(fcb, _classifier_thunk);
466 _pool.release(fcb); //Release the FCB itself inside the pool
467 }
468
469#if HAVE_CTX_GLOBAL_TIMEOUT
470 void release_later(FlowControlBlock* fcb);
471 bool check_release();
472 struct fcb_list {
473 static const unsigned DEFAULT_THRESH = 64;
474 fcb_list() : _next(0), _count(0), _count_thresh(DEFAULT_THRESH) {
475
476 }
477 FlowControlBlock* _next;
478 unsigned _count;
479 unsigned _count_thresh;
480
481 unsigned count() const {
482 return _count;
483 }
484
485 inline FlowControlBlock* find(FlowControlBlock* fcb) {
486 FlowControlBlock* head = _next;
487 #if DEBUG_CLASSIFIER_TIMEOUT > 3
488 click_chatter("FIND head %p",head);
489 #endif
490 while (head != 0) {
491 if (fcb == head)
492 return fcb;
493
494 flow_assert(head != head->next);
495 head = head->next;
496 #if DEBUG_CLASSIFIER_TIMEOUT > 5
497 click_chatter("FIND next %p",head);
498 #endif
499 }
500 return 0;
501 }
502
503 inline int find_count() {
504 FlowControlBlock* head = _next;
505 int i = 0;
506 while (head != 0) {
507 i++;
508 head = head->next;
509 }
510 return i;
511 }
512
513 };
514 per_thread<fcb_list> old_flows;
515#endif
516
517protected:
518 FCBPool _pool;
519 SubFlowRealeaseFnt _classifier_release_fnt;
520 void* _classifier_thunk;
521
522};
523
524
525//#if !HAVE_FLOW_DYNAMIC
526extern __thread FlowTableHolder* fcb_table;
527//#endif
528
529/*#if HAVE_FLOW_DYNAMIC
530 inline FCBPool* FlowControlBlock::get_pool() const { //Only works at initialisation
531 return static_cast<FCBPool*>(thunk);
532 }
533#else*/
534 inline FCBPool* FlowControlBlock::get_pool() const {
535 return fcb_table->get_pool();
536 }
537//#endif
538
539#if HAVE_FLOW_DYNAMIC
540 void FlowControlBlock::acquire(int packets_nr) {
541#if DEBUG_CLASSIFIER
542 if (thread != -1 && thread != click_current_cpu_id()) {
543 click_chatter("Read FCB %p for thread %d from thread %d",this, thread, click_current_cpu_id());
544 abort();
545 }
546#endif
547 use_count += packets_nr;
548#if DEBUG_CLASSIFIER_RELEASE > 1
549 click_chatter("Acquire %d to %p, total is %d", packets_nr, this, use_count);
550#endif
551}
552
553inline void FlowControlBlock::_do_release() {
554#if DEBUG_CLASSIFIER && HAVE_CTX_GLOBAL_TIMEOUT
555 flow_assert(!(flags & FLOW_TIMEOUT_INLIST));
556#endif
557 flow_assert(thread == click_current_cpu_id());
558 //click_chatter("Release fnt is %p",release_fnt);
559 SFCB_STACK(
560#if HAVE_FLOW_DYNAMIC
561 if (release_fnt)
562 release_fnt(this, thunk);
563#endif
564 //click_chatter("Releasing from table");
565 if (fcb_table)
566 fcb_table->release(this);
567 );
568}
569
570inline void FlowControlBlock::release(int packets_nr) {
571 flow_assert(thread == -1 || thread == click_current_cpu_id());
572#ifndef NDEBUG
573 if ((int)use_count - packets_nr < 0) {
574 click_chatter("ERROR : negative release : release %p, use_count = %d, releasing %d",this,use_count,packets_nr);
575 //assert(use_count - packets_nr >= 0);
576 }
577#endif
578 use_count -= packets_nr;
579
580#if DEBUG_CLASSIFIER_RELEASE > 1
581 click_chatter("Release %d to %p, total is %d",packets_nr,this,use_count);
582#endif
583
584 if (use_count == 0) {
585 debug_flow_2("[%d] Release fcb %p, uc 0, hc %d",click_current_cpu_id(), this,hasTimeout());
586 //assert(this->hasTimeout());
587#if HAVE_CTX_GLOBAL_TIMEOUT
588 if (this->hasTimeout()) {
589 if (this->flags & FLOW_TIMEOUT_INLIST) {
590#if DEBUG_CLASSIFIER_TIMEOUT > 2
591 click_chatter("Not releasing %p because timeout is in list, uc %d",this,use_count);
592#endif
593#if DEBUG_CLASSIFIER_TIMEOUT_CHECK > 1
594 assert(fcb_table->old_flows.get().find(this));
595#endif
596 return;
597 }
598#if DEBUG_CLASSIFIER_TIMEOUT_CHECK > 1
599 assert(!fcb_table->old_flows.get().find(this));
600#endif
601 //Timeout is not in list yet
602 if (!this->timeoutPassed(Timestamp::recent_steady())) {
603#if DEBUG_CLASSIFIER_TIMEOUT > 2
604 click_chatter("Not releasing %p because timeout is not passed. Adding to the list",this);
605#endif
606 if (fcb_table)
607 fcb_table->release_later(this);
608 return;
609 } else {
610#if DEBUG_CLASSIFIER_TIMEOUT > 2
611 unsigned t = (flags >> FLOW_TIMEOUT_SHIFT);
612 click_chatter("Timeout %p has passed (%d/%d msec)!",this, (Timestamp::recent_steady() - lastseen).msecval(),t);
613#endif
614 }
615 } else { //Does not have timeout
616#if DEBUG_CLASSIFIER_TIMEOUT > 2
617 click_chatter("No timeout for fcb %p",this);
618#endif
619 }
620#endif
621 this->_do_release();
622
623 } //use_count > 0
624#if DEBUG_CLASSIFIER_RELEASE
625 else {
626 click_chatter("NO RELEASE, fcb %p, uc %d",this,this->use_count);
627 }
628#endif
629}
630#endif
631
632#else
633#define SFCB_STACK(fnt) \
634 {fnt;}
635#endif //HAVE_FLOW
636
637CLICK_ENDDECLS
638
639#endif
Bitvector
Vector of bits.
Definition bitvector.hh:21
Element
Base class for Click elements.
Definition element.hh:42
String
A string of characters.
Definition string.hh:22
Timestamp
Represents a moment or interval in time.
Definition timestamp.hh:125
Timestamp::recent_steady
static Timestamp recent_steady()
Return a recent steady-clock time.
Definition timestamp.hh:1000
atomic_uint32_t
A 32-bit integer with support for atomic operations.
Definition atomic.hh:71
per_thread
Definition sync.hh:57
Generated on Mon Nov 2 2026 11:59:47 for Click by doxygen 1.9.8