Click
Loading...
Searching...
No Matches
flow.hh
1#ifndef CLICK_FLOW
2#define CLICK_FLOW 1
3
4#include <click/timestamp.hh>
5#include <click/error.hh>
6#include <click/sync.hh>
7#include <click/packet.hh>
8#include <click/multithread.hh>
9#include <click/bitvector.hh>
10#include <click/vector.hh>
11#include <click/list.hh>
12#include <click/allocator.hh>
13
14#include <thread>
15#include "common.hh"
16
17CLICK_DECLS
18
19#ifdef HAVE_FLOW
20
21#include "node/flow_nodes.hh"
22
23inline void check_thread(FlowNode* parent, FlowNode* child) {
24#if !DEBUG_CLASSIFIER
25 assert(false); //Never run this in non-debug
26#endif
27 FlowNodeData data = child->node_data;
28 while (parent && dynamic_cast<FlowLevelThread*>(parent->level()) == 0) {
29 child = parent;
30 data = child->node_data;
31 parent = parent->parent();
32 }
33 /*
34 click_chatter("Releasing a nonthread??");
35 parent->print();
36 abort();
37 }*/
38 if (!parent)
39 return;
40 if (data.data_32 != click_current_cpu_id()) {
41 click_chatter("Thead %d in level of thread %d", click_current_cpu_id(), data.data_32);
42 assert(false);
43 }
44}
45
46
47class FlowClassificationTable : public FlowTableHolder {
48public:
49 FlowClassificationTable();
50 ~FlowClassificationTable();
51
52 void set_root(FlowNode* node);
53 FlowNode* get_root();
54
55 inline FlowControlBlock* match(Packet* p, FlowNode* parent);
56
57 inline FlowControlBlock* match(Packet* p) {
58 return match(p, _root);
59 }
60 inline bool reverse_match(FlowControlBlock* sfcb, Packet* p, FlowNode* root);
61
62 typedef struct {
63 FlowNode* root;
64 int output;
65 bool is_default;
66 } Rule;
67 static Rule parse(Element* owner, String s, bool verbose = false, bool add_leaf=true);
68 static Rule make_drop_rule(bool ed = false) {
69 Rule r = parse(0, "- drop");
70 if (ed)
71 r.root->traverse_all_leaves([](FlowNodePtr* ptr){ ptr->leaf->set_early_drop();}, true, true);
72 return r;
73 }
74 static Rule make_ip_mask(IPAddress dst, IPAddress mask);
75protected:
76 FlowNode* _root;
77};
78
79
80/*****************************************************
81 * Inline implementations for performances
82 *****************************************************/
83
87bool FlowClassificationTable::reverse_match(FlowControlBlock* sfcb, Packet* p, FlowNode* root) {
88#if HAVE_FLOW_EXACT_MATCH
89 //TODO : work in progress
90 __m256i pdata = _mm256_loadu_si256((__m128i*) p->data());
91 __m256i cdata = _mm256_loadu_si256((__m128i*) sfcb->val);
92 __m256i mask = _mm256_loadu_si256((__m128i*) *sfcb->mask);
93 pdata = _mm256_and_si256(pdata, mask);
94 cdata = _mm256_and_si256(cdata, mask);
95 return _mm256_testc_si256(pdata, cdata);
96#endif
97
98 FlowNode* parent = (FlowNode*)sfcb->parent;
99#if DEBUG_CLASSIFIER
100 if (parent != root && (!parent || !root->find_node(parent))) {
101 click_chatter("GOING TO CRASH WHILE MATCHING fcb %p, with parent %p", sfcb, parent);
102 click_chatter("Parent exists : %d",root->find_node(parent));
103 root->print();
104 sfcb->reverse_print();
105 assert(false);
106 }
107#endif
108 if (unlikely(!parent->_leaf_reverse_match(sfcb,p))) {
109#if DEBUG_CLASSIFIER_MATCH > 2
110 click_chatter("DIF is_default %d Leaf %x %x level %s",parent->default_ptr()->ptr == sfcb,parent->level()->get_data(p).get_long(), sfcb->node_data[0].get_long(),parent->level()->print().c_str());
111#endif
112 return false;
113 } else {
114#if DEBUG_CLASSIFIER_MATCH > 2
115 click_chatter("MAT is_default %d Leaf %x %x level %s",parent->default_ptr()->ptr == sfcb,parent->level()->get_data(p).get_long(), sfcb->node_data[0].get_long(),parent->level()->print().c_str());
116#endif
117 }
118
119 while (parent != root) {
120
121#if DEBUG_CLASSIFIER
122 if (parent->threads.size() <= click_current_cpu_id() || !parent->threads[click_current_cpu_id()]) {
123 click_chatter("[%d] FATAL : Parent should not have this thread",click_current_cpu_id());
124 click_chatter("[%d] FATAL : Thread of parent : %s",click_current_cpu_id(),parent->threads.unparse().c_str());
125 parent->print();
126 assert(parent->threads[click_current_cpu_id()]);
127 }
128#endif
129 FlowNode* child = parent;
130 parent = parent->parent();
131 flow_assert(parent);
132 flow_assert(child != parent);
133
134 //While parent (the old one) is growing, we continue. Because we already matched on that level.
135 if (child->level() == parent->level())
136 continue;
137
138 if (unlikely(!parent->_node_reverse_match(child,p))) {
139#if DEBUG_CLASSIFIER_MATCH > 2
140 click_chatter("DIF is_default %d Child %x %x level %s",parent->default_ptr()->ptr == child ,parent->level()->get_data(p).get_long(), child->node_data.get_long(),parent->level()->print().c_str());
141#endif
142 return false;
143 } else {
144#if DEBUG_CLASSIFIER_MATCH > 2
145 click_chatter("MAT is_default %d Child %x %x level %s",parent->default_ptr()->ptr == child,parent->level()->get_data(p).get_long(), child->node_data.get_long(),parent->level()->print().c_str());
146#endif
147 }
148 };
149 return true;
150}
151
152
153FlowControlBlock* FlowClassificationTable::match(Packet* p, FlowNode* parent) {
154 FlowNodePtr* child_ptr = 0;
155#if DEBUG_CLASSIFIER
156
157 FlowNode* debug_save_root = parent;
158#endif
159 int level_nr = 0;
160 (void)level_nr;
161 do {
162 bool need_grow = false;
163 FlowNodeData data = parent->level()->get_data(p);
164 debug_flow("[%d] Data level %d is %016llX %s",click_current_cpu_id(), level_nr++,data.get_long(),parent->level()->print().c_str());
165 child_ptr = parent->find(data,need_grow);
166 debug_flow("[%d] ->Ptr is %p, is_leaf : %d",click_current_cpu_id(), child_ptr->ptr, child_ptr->is_leaf());
167 if (unlikely(IS_FREE_PTR_ANY(child_ptr->ptr) //Do not change ptr here to 0, as we could follow default path without changing this one
168#if FLOW_KEEP_STRUCTURE
169 || (child_ptr->is_node() && child_ptr->node->released())
170#endif
171 )) { //Unlikely to create a new node.
172
173 if (parent->get_default().ptr) {
174#if HAVE_FLOW_DYNAMIC
175 if (parent->level()->is_dynamic()) {
176 if (unlikely(parent->growing())) {
177 //Table is growing, and we could not find a child, we go to the default table
178 /*
179#if DEBUG_CLASSIFIER
180 if (parent->getNum() == 0) { //Table is growing, but have no more child.
181 debug_flow("Table %s finished growing, deleting %p, type %s",parent->level()->print().c_str(), parent, parent->name().c_str());
182 flow_assert(parent->getNum() == parent->findGetNum());
183 // assert(false); //The release took care of this //TODO : this actually happens from time to time. I guess when releasing is prevented at the end of the tree. To inquiry. not bad
184 } else {
185#if DEBUG_CLASSIFIER
186 click_chatter("Growing table, %d/%d",parent->num, parent->max_size());
187#endif
188 }
189#endif
190*/
191
192 flow_assert(parent->default_ptr()->node->parent() == parent);
193 parent = parent->default_ptr()->node;
194 continue;
195 } else { //Parent is not growing
196 if (need_grow) {
197#if HAVE_STATIC_CLASSIFICATION
198 click_chatter("MAX CAPACITY ACHIEVED, DROPPING");
199 return 0;
200#else
201 parent = parent->start_growing(false);
202 if (!parent) {
203 click_chatter("Could not grow !? Dropping flow !");
204 //TODO : release some children
205 return 0;
206 }
207 flow_assert(_root->find_node(parent));
208 continue;
209#endif
210 }
211
212#if DEBUG_CLASSIFIER_CHECK
213 if(parent->getNum() != parent->findGetNum()) {
214 click_chatter("%d %d",parent->getNum(), parent->findGetNum());
215 abort();
216 }
217 flow_assert(parent->getNum() < parent->max_size());
218#endif
219 parent->inc_num();
220 if (parent->get_default().is_leaf()) { //Leaf are not duplicated, we need to do it ourself
221 debug_flow("[%d] DUPLICATE leaf %p", click_current_cpu_id(),parent->get_default().ptr);
222 //click_chatter("New leaf with data '%x'",data.get_long());
223 //click_chatter("Data %x %x",parent->default_ptr()->leaf->data_32[2],parent->default_ptr()->leaf->data_32[3]);
224 child_ptr->set_leaf(_pool.allocate());
225 flow_assert(child_ptr->leaf);
226 flow_assert(child_ptr->is_leaf());
227 child_ptr->leaf->initialize();
228 child_ptr->leaf->parent = parent;
229
230 /*#if HAVE_FLOW_DYNAMIC
231 child_ptr->leaf->release_fnt = _classifier_release_fnt;
232 #endif*/
233 child_ptr->set_data(data);
234 memcpy(&child_ptr->leaf->node_data[1], &parent->default_ptr()->leaf->node_data[1] ,_pool.data_size() - sizeof(FlowNodeData));
235 #if DEBUG_CLASSIFIER_MATCH > 3
236 _root->print();
237 #endif
238 _root->check(true, false);
239#if DEBUG_CLASSIFIER
240 if (parent->threads.weight() == 1)
241 child_ptr->leaf->thread = parent->threads.clz();
242 else
243 child_ptr->leaf->thread = -1;
244 flow_assert(child_ptr->leaf->thread == -1 || child_ptr->leaf->thread == click_current_cpu_id());
245#endif
246 flow_assert(reverse_match(child_ptr->leaf, p, debug_save_root));
247 return child_ptr->leaf;
248 } else {
249#if FLOW_KEEP_STRUCTURE
250 if (child_ptr->ptr && child_ptr->node->released()) { //Childptr is a released node, just renew it
251 child_ptr->node->renew();
252 child_ptr->set_data(data);
253 //flow_assert(parent->find(data)->ptr == child_ptr->ptr);
254 } else
255#endif
256 { //Duplicate node
257
258 FlowNode* defNode = parent->default_ptr()->node;
259 flow_assert(parent->default_ptr()->node->getNum() == 0);
260 FlowNode* newNode = defNode->level()->create_node(defNode, false, false);
261 newNode->_level = defNode->level();
262 *newNode->default_ptr() = *defNode->default_ptr();
263 child_ptr->set_node(newNode);
264 debug_flow("[%d] DUPLICATE node, new is %p, default is %p",click_current_cpu_id(),child_ptr->node,parent->default_ptr()->ptr);
265
266 child_ptr->set_data(data);
267 child_ptr->set_parent(parent);
268#if DEBUG_CLASSIFIER
269 newNode->threads.clear();
270 newNode->threads.resize(click_max_cpu_ids());
271 newNode->threads[click_current_cpu_id()] = true;
272 flow_assert(parent->threads[click_current_cpu_id()]);
273#endif
274// flow_assert(parent->find(data)->ptr == child_ptr->ptr);
275 }
276 }
277 flow_assert(parent->getNum() == parent->findGetNum());
278
279 _root->check(true, false);
280 }
281 } else
282#endif
283 { //There is a default but it is not a dynamic level
284 flow_assert(child_ptr->node->threads[click_current_cpu_id()]);
285 child_ptr = parent->default_ptr();
286 if (child_ptr->is_leaf()) {
287 _root->check(true, false); //Do nothing if not in debug mode
288 flow_assert(reverse_match(child_ptr->leaf, p, debug_save_root));
289 return child_ptr->leaf;
290 }
291 }
292 } else {
293 click_chatter("ERROR : no classification node and no default path !");// allowed with the "!" symbol
294 click_chatter("Level %s, data %lu", parent->level()->print().c_str(),data.get_long());
295 _root->print();
296 return 0;
297 }
298 } else if (child_ptr->is_leaf()) {
299 flow_assert(child_ptr->leaf->thread == -1 || child_ptr->leaf->thread == click_current_cpu_id());
300#if DEBUG_FLOW
301 if (child_ptr->leaf->parent()) {
302 flow_assert(reverse_match(child_ptr->leaf, p));
303 }
304#endif
305 return child_ptr->leaf;
306 } else { // is an existing node, and not released. Just descend
307
308 flow_assert(child_ptr->node->threads[click_current_cpu_id()]);
309 }
310
311 flow_assert(child_ptr->node->parent() == parent);
312 parent = child_ptr->node;
313
314 flow_assert(parent);
315 } while(1);
316}
317
318inline FlowNodeData FlowNodePtr::data() {
319 if (is_leaf())
320 return leaf->node_data[0];
321 else
322 return node->node_data;
323}
324
325inline FlowNode* FlowNodePtr::parent() const {
326 if (is_leaf())
327 return (FlowNode*)leaf->parent;
328 else
329 return node->parent();
330}
331
332inline void FlowNodePtr::set_data(FlowNodeData data) {
333 if (is_leaf())
334 leaf->node_data[0] = data;
335 else
336 node->node_data = data;
337}
338
339inline void FlowNodePtr::set_parent(FlowNode* parent) {
340 if (is_leaf())
341 leaf->parent = parent;
342 else
343 node->set_parent(parent);
344}
345
346#endif
347
348CLICK_ENDDECLS
349#endif
bitvector.hh
Click's bitvector class.
Element
Base class for Click elements.
Definition element.hh:42
FlowLevelThread
Definition flow_level.hh:291
IPAddress
An IPv4 address.
Definition ipaddress.hh:16
Packet
A network packet.
Definition packet.hh:68
Packet::data
const unsigned char * data() const
Return the packet's data pointer.
Definition packet.hh:1207
String
A string of characters.
Definition string.hh:22
error.hh
Flexible error handling classes.
list.hh
Click's doubly-linked list container template.
packet.hh
The Packet class models packets in Click.
sync.hh
Classes for synchronizing among multiple CPUs, particularly in the Linux kernel.
timestamp.hh
The Timestamp class represents a moment or interval in time.
vector.hh
Click's vector container template.
Generated on Mon Nov 2 2026 11:59:47 for Click by doxygen 1.9.8