suricata
flow-hash.c
Go to the documentation of this file.
1 /* Copyright (C) 2007-2013 Open Information Security Foundation
2  *
3  * You can copy, redistribute or modify this Program under the terms of
4  * the GNU General Public License version 2 as published by the Free
5  * Software Foundation.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * version 2 along with this program; if not, write to the Free Software
14  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
15  * 02110-1301, USA.
16  */
17 
18 /**
19  * \file
20  *
21  * \author Victor Julien <victor@inliniac.net>
22  * \author Pablo Rincon Crespo <pablo.rincon.crespo@gmail.com>
23  *
24  * Flow Hashing functions.
25  */
26 
27 #include "suricata-common.h"
28 #include "threads.h"
29 
30 #include "decode.h"
31 #include "detect-engine-state.h"
32 
33 #include "flow.h"
34 #include "flow-hash.h"
35 #include "flow-util.h"
36 #include "flow-private.h"
37 #include "flow-manager.h"
38 #include "flow-storage.h"
39 #include "app-layer-parser.h"
40 
41 #include "util-time.h"
42 #include "util-debug.h"
43 
44 #include "util-hash-lookup3.h"
45 
46 #include "conf.h"
47 #include "output.h"
48 #include "output-flow.h"
49 
50 #define FLOW_DEFAULT_FLOW_PRUNE 5
51 
52 SC_ATOMIC_EXTERN(unsigned int, flow_prune_idx);
53 SC_ATOMIC_EXTERN(unsigned int, flow_flags);
54 
55 static Flow *FlowGetUsedFlow(ThreadVars *tv, DecodeThreadVars *dtv);
56 
57 /** \brief compare two raw ipv6 addrs
58  *
59  * \note we don't care about the real ipv6 ip's, this is just
60  * to consistently fill the FlowHashKey6 struct, without all
61  * the SCNtohl calls.
62  *
63  * \warning do not use elsewhere unless you know what you're doing.
64  * detect-engine-address-ipv6.c's AddressIPv6GtU32 is likely
65  * what you are looking for.
66  */
67 static inline int FlowHashRawAddressIPv6GtU32(const uint32_t *a, const uint32_t *b)
68 {
69  int i;
70 
71  for (i = 0; i < 4; i++) {
72  if (a[i] > b[i])
73  return 1;
74  if (a[i] < b[i])
75  break;
76  }
77 
78  return 0;
79 }
80 
81 typedef struct FlowHashKey4_ {
82  union {
83  struct {
84  uint32_t addrs[2];
85  uint16_t ports[2];
86  uint16_t proto; /**< u16 so proto and recur add up to u32 */
87  uint16_t recur; /**< u16 so proto and recur add up to u32 */
88  uint16_t vlan_id[2];
89  };
90  const uint32_t u32[5];
91  };
92 } FlowHashKey4;
93 
94 typedef struct FlowHashKey6_ {
95  union {
96  struct {
97  uint32_t src[4], dst[4];
98  uint16_t ports[2];
99  uint16_t proto; /**< u16 so proto and recur add up to u32 */
100  uint16_t recur; /**< u16 so proto and recur add up to u32 */
101  uint16_t vlan_id[2];
102  };
103  const uint32_t u32[11];
104  };
105 } FlowHashKey6;
106 
107 /* calculate the hash key for this packet
108  *
109  * we're using:
110  * hash_rand -- set at init time
111  * source port
112  * destination port
113  * source address
114  * destination address
115  * recursion level -- for tunnels, make sure different tunnel layers can
116  * never get mixed up.
117  *
118  * For ICMP we only consider UNREACHABLE errors atm.
119  */
120 static inline uint32_t FlowGetHash(const Packet *p)
121 {
122  uint32_t hash = 0;
123 
124  if (p->ip4h != NULL) {
125  if (p->tcph != NULL || p->udph != NULL) {
126  FlowHashKey4 fhk;
127 
128  int ai = (p->src.addr_data32[0] > p->dst.addr_data32[0]);
129  fhk.addrs[1-ai] = p->src.addr_data32[0];
130  fhk.addrs[ai] = p->dst.addr_data32[0];
131 
132  const int pi = (p->sp > p->dp);
133  fhk.ports[1-pi] = p->sp;
134  fhk.ports[pi] = p->dp;
135 
136  fhk.proto = (uint16_t)p->proto;
137  fhk.recur = (uint16_t)p->recursion_level;
138  fhk.vlan_id[0] = p->vlan_id[0];
139  fhk.vlan_id[1] = p->vlan_id[1];
140 
141  hash = hashword(fhk.u32, 5, flow_config.hash_rand);
142 
143  } else if (ICMPV4_DEST_UNREACH_IS_VALID(p)) {
144  uint32_t psrc = IPV4_GET_RAW_IPSRC_U32(ICMPV4_GET_EMB_IPV4(p));
145  uint32_t pdst = IPV4_GET_RAW_IPDST_U32(ICMPV4_GET_EMB_IPV4(p));
146  FlowHashKey4 fhk;
147 
148  const int ai = (psrc > pdst);
149  fhk.addrs[1-ai] = psrc;
150  fhk.addrs[ai] = pdst;
151 
152  const int pi = (p->icmpv4vars.emb_sport > p->icmpv4vars.emb_dport);
153  fhk.ports[1-pi] = p->icmpv4vars.emb_sport;
154  fhk.ports[pi] = p->icmpv4vars.emb_dport;
155 
156  fhk.proto = (uint16_t)ICMPV4_GET_EMB_PROTO(p);
157  fhk.recur = (uint16_t)p->recursion_level;
158  fhk.vlan_id[0] = p->vlan_id[0];
159  fhk.vlan_id[1] = p->vlan_id[1];
160 
161  hash = hashword(fhk.u32, 5, flow_config.hash_rand);
162 
163  } else {
164  FlowHashKey4 fhk;
165  const int ai = (p->src.addr_data32[0] > p->dst.addr_data32[0]);
166  fhk.addrs[1-ai] = p->src.addr_data32[0];
167  fhk.addrs[ai] = p->dst.addr_data32[0];
168  fhk.ports[0] = 0xfeed;
169  fhk.ports[1] = 0xbeef;
170  fhk.proto = (uint16_t)p->proto;
171  fhk.recur = (uint16_t)p->recursion_level;
172  fhk.vlan_id[0] = p->vlan_id[0];
173  fhk.vlan_id[1] = p->vlan_id[1];
174 
175  hash = hashword(fhk.u32, 5, flow_config.hash_rand);
176  }
177  } else if (p->ip6h != NULL) {
178  FlowHashKey6 fhk;
179  if (FlowHashRawAddressIPv6GtU32(p->src.addr_data32, p->dst.addr_data32)) {
180  fhk.src[0] = p->src.addr_data32[0];
181  fhk.src[1] = p->src.addr_data32[1];
182  fhk.src[2] = p->src.addr_data32[2];
183  fhk.src[3] = p->src.addr_data32[3];
184  fhk.dst[0] = p->dst.addr_data32[0];
185  fhk.dst[1] = p->dst.addr_data32[1];
186  fhk.dst[2] = p->dst.addr_data32[2];
187  fhk.dst[3] = p->dst.addr_data32[3];
188  } else {
189  fhk.src[0] = p->dst.addr_data32[0];
190  fhk.src[1] = p->dst.addr_data32[1];
191  fhk.src[2] = p->dst.addr_data32[2];
192  fhk.src[3] = p->dst.addr_data32[3];
193  fhk.dst[0] = p->src.addr_data32[0];
194  fhk.dst[1] = p->src.addr_data32[1];
195  fhk.dst[2] = p->src.addr_data32[2];
196  fhk.dst[3] = p->src.addr_data32[3];
197  }
198 
199  const int pi = (p->sp > p->dp);
200  fhk.ports[1-pi] = p->sp;
201  fhk.ports[pi] = p->dp;
202  fhk.proto = (uint16_t)p->proto;
203  fhk.recur = (uint16_t)p->recursion_level;
204  fhk.vlan_id[0] = p->vlan_id[0];
205  fhk.vlan_id[1] = p->vlan_id[1];
206 
207  hash = hashword(fhk.u32, 11, flow_config.hash_rand);
208  }
209 
210  return hash;
211 }
212 
213 /**
214  * Basic hashing function for FlowKey
215  *
216  * \note Function only used for bypass and TCP or UDP flows
217  *
218  * \note this is only used at start to create Flow from pinned maps
219  * so fairness is not an issue
220  */
221 uint32_t FlowKeyGetHash(FlowKey *fk)
222 {
223  uint32_t hash = 0;
224 
225  if (fk->src.family == AF_INET) {
226  FlowHashKey4 fhk;
227  int ai = (fk->src.address.address_un_data32[0] > fk->dst.address.address_un_data32[0]);
228  fhk.addrs[1-ai] = fk->src.address.address_un_data32[0];
229  fhk.addrs[ai] = fk->dst.address.address_un_data32[0];
230 
231  const int pi = (fk->sp > fk->dp);
232  fhk.ports[1-pi] = fk->sp;
233  fhk.ports[pi] = fk->dp;
234 
235  fhk.proto = (uint16_t)fk->proto;
236  fhk.recur = (uint16_t)fk->recursion_level;
237  fhk.vlan_id[0] = fk->vlan_id[0];
238  fhk.vlan_id[1] = fk->vlan_id[1];
239 
240  hash = hashword(fhk.u32, 5, flow_config.hash_rand);
241  } else {
242  FlowHashKey6 fhk;
243  if (FlowHashRawAddressIPv6GtU32(fk->src.address.address_un_data32,
245  fhk.src[0] = fk->src.address.address_un_data32[0];
246  fhk.src[1] = fk->src.address.address_un_data32[1];
247  fhk.src[2] = fk->src.address.address_un_data32[2];
248  fhk.src[3] = fk->src.address.address_un_data32[3];
249  fhk.dst[0] = fk->dst.address.address_un_data32[0];
250  fhk.dst[1] = fk->dst.address.address_un_data32[1];
251  fhk.dst[2] = fk->dst.address.address_un_data32[2];
252  fhk.dst[3] = fk->dst.address.address_un_data32[3];
253  } else {
254  fhk.src[0] = fk->dst.address.address_un_data32[0];
255  fhk.src[1] = fk->dst.address.address_un_data32[1];
256  fhk.src[2] = fk->dst.address.address_un_data32[2];
257  fhk.src[3] = fk->dst.address.address_un_data32[3];
258  fhk.dst[0] = fk->src.address.address_un_data32[0];
259  fhk.dst[1] = fk->src.address.address_un_data32[1];
260  fhk.dst[2] = fk->src.address.address_un_data32[2];
261  fhk.dst[3] = fk->src.address.address_un_data32[3];
262  }
263 
264  const int pi = (fk->sp > fk->dp);
265  fhk.ports[1-pi] = fk->sp;
266  fhk.ports[pi] = fk->dp;
267  fhk.proto = (uint16_t)fk->proto;
268  fhk.recur = (uint16_t)fk->recursion_level;
269  fhk.vlan_id[0] = fk->vlan_id[0];
270  fhk.vlan_id[1] = fk->vlan_id[1];
271 
272  hash = hashword(fhk.u32, 11, flow_config.hash_rand);
273  }
274 return hash;
275 }
276 
277 /* Since two or more flows can have the same hash key, we need to compare
278  * the flow with the current flow key. */
279 #define CMP_FLOW(f1,f2) \
280  (((CMP_ADDR(&(f1)->src, &(f2)->src) && \
281  CMP_ADDR(&(f1)->dst, &(f2)->dst) && \
282  CMP_PORT((f1)->sp, (f2)->sp) && CMP_PORT((f1)->dp, (f2)->dp)) || \
283  (CMP_ADDR(&(f1)->src, &(f2)->dst) && \
284  CMP_ADDR(&(f1)->dst, &(f2)->src) && \
285  CMP_PORT((f1)->sp, (f2)->dp) && CMP_PORT((f1)->dp, (f2)->sp))) && \
286  (f1)->proto == (f2)->proto && \
287  (f1)->recursion_level == (f2)->recursion_level && \
288  (f1)->vlan_id[0] == (f2)->vlan_id[0] && \
289  (f1)->vlan_id[1] == (f2)->vlan_id[1])
290 #define CMP_FLOW_ICMP(f1,f2) \
291  (((CMP_ADDR(&(f1)->src, &(f2)->src) && \
292  CMP_ADDR(&(f1)->dst, &(f2)->dst) && \
293  CMP_PORT((f1)->icmp_s.type, (f2)->icmp_s.type) && CMP_PORT((f1)->icmp_d.type, (f2)->icmp_d.type)) || \
294  (CMP_ADDR(&(f1)->src, &(f2)->dst) && \
295  CMP_ADDR(&(f1)->dst, &(f2)->src) && \
296  CMP_PORT((f1)->icmp_d.type, (f2)->icmp_s.type) && CMP_PORT((f1)->icmp_s.type, (f2)->icmp_d.type))) && \
297  (f1)->proto == (f2)->proto && \
298  (f1)->recursion_level == (f2)->recursion_level && \
299  (f1)->vlan_id[0] == (f2)->vlan_id[0] && \
300  (f1)->vlan_id[1] == (f2)->vlan_id[1])
301 
302 /**
303  * \brief See if a ICMP packet belongs to a flow by comparing the embedded
304  * packet in the ICMP error packet to the flow.
305  *
306  * \param f flow
307  * \param p ICMP packet
308  *
309  * \retval 1 match
310  * \retval 0 no match
311  */
312 static inline int FlowCompareICMPv4(Flow *f, const Packet *p)
313 {
315  /* first check the direction of the flow, in other words, the client ->
316  * server direction as it's most likely the ICMP error will be a
317  * response to the clients traffic */
318  if ((f->src.addr_data32[0] == IPV4_GET_RAW_IPSRC_U32( ICMPV4_GET_EMB_IPV4(p) )) &&
319  (f->dst.addr_data32[0] == IPV4_GET_RAW_IPDST_U32( ICMPV4_GET_EMB_IPV4(p) )) &&
320  f->sp == p->icmpv4vars.emb_sport &&
321  f->dp == p->icmpv4vars.emb_dport &&
322  f->proto == ICMPV4_GET_EMB_PROTO(p) &&
323  f->recursion_level == p->recursion_level &&
324  f->vlan_id[0] == p->vlan_id[0] &&
325  f->vlan_id[1] == p->vlan_id[1])
326  {
327  return 1;
328 
329  /* check the less likely case where the ICMP error was a response to
330  * a packet from the server. */
331  } else if ((f->dst.addr_data32[0] == IPV4_GET_RAW_IPSRC_U32( ICMPV4_GET_EMB_IPV4(p) )) &&
332  (f->src.addr_data32[0] == IPV4_GET_RAW_IPDST_U32( ICMPV4_GET_EMB_IPV4(p) )) &&
333  f->dp == p->icmpv4vars.emb_sport &&
334  f->sp == p->icmpv4vars.emb_dport &&
335  f->proto == ICMPV4_GET_EMB_PROTO(p) &&
336  f->recursion_level == p->recursion_level &&
337  f->vlan_id[0] == p->vlan_id[0] &&
338  f->vlan_id[1] == p->vlan_id[1])
339  {
340  return 1;
341  }
342 
343  /* no match, fall through */
344  } else {
345  /* just treat ICMP as a normal proto for now */
346  return CMP_FLOW_ICMP(f, p);
347  }
348 
349  return 0;
350 }
351 
353 {
354  p->flags |= PKT_WANTS_FLOW;
355  p->flow_hash = FlowGetHash(p);
356 }
357 
358 int TcpSessionPacketSsnReuse(const Packet *p, const Flow *f, void *tcp_ssn);
359 
360 static inline int FlowCompare(Flow *f, const Packet *p)
361 {
362  if (p->proto == IPPROTO_ICMP) {
363  return FlowCompareICMPv4(f, p);
364  } else if (p->proto == IPPROTO_TCP) {
365  if (CMP_FLOW(f, p) == 0)
366  return 0;
367 
368  /* if this session is 'reused', we don't return it anymore,
369  * so return false on the compare */
370  if (f->flags & FLOW_TCP_REUSED)
371  return 0;
372 
373  return 1;
374  } else {
375  return CMP_FLOW(f, p);
376  }
377 }
378 
379 /**
380  * \brief Check if we should create a flow based on a packet
381  *
382  * We use this check to filter out flow creation based on:
383  * - ICMP error messages
384  *
385  * \param p packet
386  * \retval 1 true
387  * \retval 0 false
388  */
389 static inline int FlowCreateCheck(const Packet *p)
390 {
391  if (PKT_IS_ICMPV4(p)) {
392  if (ICMPV4_IS_ERROR_MSG(p)) {
393  return 0;
394  }
395  }
396 
397  return 1;
398 }
399 
400 static inline void FlowUpdateCounter(ThreadVars *tv, DecodeThreadVars *dtv,
401  uint8_t proto)
402 {
403 #ifdef UNITTESTS
404  if (tv && dtv) {
405 #endif
406  switch (proto){
407  case IPPROTO_UDP:
408  StatsIncr(tv, dtv->counter_flow_udp);
409  break;
410  case IPPROTO_TCP:
411  StatsIncr(tv, dtv->counter_flow_tcp);
412  break;
413  case IPPROTO_ICMP:
414  StatsIncr(tv, dtv->counter_flow_icmp4);
415  break;
416  case IPPROTO_ICMPV6:
417  StatsIncr(tv, dtv->counter_flow_icmp6);
418  break;
419  }
420 #ifdef UNITTESTS
421  }
422 #endif
423 }
424 
425 /**
426  * \brief Get a new flow
427  *
428  * Get a new flow. We're checking memcap first and will try to make room
429  * if the memcap is reached.
430  *
431  * \param tv thread vars
432  * \param dtv decode thread vars (for flow log api thread data)
433  *
434  * \retval f *LOCKED* flow on succes, NULL on error.
435  */
436 static Flow *FlowGetNew(ThreadVars *tv, DecodeThreadVars *dtv, const Packet *p)
437 {
438  Flow *f = NULL;
439 
440  if (FlowCreateCheck(p) == 0) {
441  return NULL;
442  }
443 
444  /* get a flow from the spare queue */
446  if (f == NULL) {
447  /* If we reached the max memcap, we get a used flow */
448  if (!(FLOW_CHECK_MEMCAP(sizeof(Flow) + FlowStorageSize()))) {
449  /* declare state of emergency */
450  if (!(SC_ATOMIC_GET(flow_flags) & FLOW_EMERGENCY)) {
451  SC_ATOMIC_OR(flow_flags, FLOW_EMERGENCY);
452 
454 
455  /* under high load, waking up the flow mgr each time leads
456  * to high cpu usage. Flows are not timed out much faster if
457  * we check a 1000 times a second. */
459  }
460 
461  f = FlowGetUsedFlow(tv, dtv);
462  if (f == NULL) {
463  /* max memcap reached, so increments the counter */
464  if (tv != NULL && dtv != NULL) {
465  StatsIncr(tv, dtv->counter_flow_memcap);
466  }
467 
468  /* very rare, but we can fail. Just giving up */
469  return NULL;
470  }
471 
472  /* freed a flow, but it's unlocked */
473  } else {
474  /* now see if we can alloc a new flow */
475  f = FlowAlloc();
476  if (f == NULL) {
477  if (tv != NULL && dtv != NULL) {
478  StatsIncr(tv, dtv->counter_flow_memcap);
479  }
480  return NULL;
481  }
482 
483  /* flow is initialized but *unlocked* */
484  }
485  } else {
486  /* flow has been recycled before it went into the spare queue */
487 
488  /* flow is initialized (recylced) but *unlocked* */
489  }
490 
491  FLOWLOCK_WRLOCK(f);
492  FlowUpdateCounter(tv, dtv, p->proto);
493  return f;
494 }
495 
496 static Flow *TcpReuseReplace(ThreadVars *tv, DecodeThreadVars *dtv,
497  FlowBucket *fb, Flow *old_f,
498  const uint32_t hash, const Packet *p)
499 {
500  /* tag flow as reused so future lookups won't find it */
501  old_f->flags |= FLOW_TCP_REUSED;
502  /* get some settings that we move over to the new flow */
503  FlowThreadId thread_id = old_f->thread_id;
504 
505  /* since fb lock is still held this flow won't be found until we are done */
506  FLOWLOCK_UNLOCK(old_f);
507 
508  /* Get a new flow. It will be either a locked flow or NULL */
509  Flow *f = FlowGetNew(tv, dtv, p);
510  if (f == NULL) {
511  return NULL;
512  }
513 
514  /* flow is locked */
515 
516  /* put at the start of the list */
517  f->hnext = fb->head;
518  fb->head->hprev = f;
519  fb->head = f;
520 
521  /* initialize and return */
522  FlowInit(f, p);
523  f->flow_hash = hash;
524  f->fb = fb;
525 
526  f->thread_id = thread_id;
527  return f;
528 }
529 
530 /** \brief Get Flow for packet
531  *
532  * Hash retrieval function for flows. Looks up the hash bucket containing the
533  * flow pointer. Then compares the packet with the found flow to see if it is
534  * the flow we need. If it isn't, walk the list until the right flow is found.
535  *
536  * If the flow is not found or the bucket was emtpy, a new flow is taken from
537  * the queue. FlowDequeue() will alloc new flows as long as we stay within our
538  * memcap limit.
539  *
540  * The p->flow pointer is updated to point to the flow.
541  *
542  * \param tv thread vars
543  * \param dtv decode thread vars (for flow log api thread data)
544  *
545  * \retval f *LOCKED* flow or NULL
546  */
548 {
549  Flow *f = NULL;
550 
551  /* get our hash bucket and lock it */
552  const uint32_t hash = p->flow_hash;
553  FlowBucket *fb = &flow_hash[hash % flow_config.hash_size];
554  FBLOCK_LOCK(fb);
555 
556  SCLogDebug("fb %p fb->head %p", fb, fb->head);
557 
558  /* see if the bucket already has a flow */
559  if (fb->head == NULL) {
560  f = FlowGetNew(tv, dtv, p);
561  if (f == NULL) {
562  FBLOCK_UNLOCK(fb);
563  return NULL;
564  }
565 
566  /* flow is locked */
567  fb->head = f;
568  fb->tail = f;
569 
570  /* got one, now lock, initialize and return */
571  FlowInit(f, p);
572  f->flow_hash = hash;
573  f->fb = fb;
575 
576  FlowReference(dest, f);
577 
578  FBLOCK_UNLOCK(fb);
579  return f;
580  }
581 
582  /* ok, we have a flow in the bucket. Let's find out if it is our flow */
583  f = fb->head;
584 
585  /* see if this is the flow we are looking for */
586  if (FlowCompare(f, p) == 0) {
587  Flow *pf = NULL; /* previous flow */
588 
589  while (f) {
590  pf = f;
591  f = f->hnext;
592 
593  if (f == NULL) {
594  f = pf->hnext = FlowGetNew(tv, dtv, p);
595  if (f == NULL) {
596  FBLOCK_UNLOCK(fb);
597  return NULL;
598  }
599  fb->tail = f;
600 
601  /* flow is locked */
602 
603  f->hprev = pf;
604 
605  /* initialize and return */
606  FlowInit(f, p);
607  f->flow_hash = hash;
608  f->fb = fb;
610 
611  FlowReference(dest, f);
612 
613  FBLOCK_UNLOCK(fb);
614  return f;
615  }
616 
617  if (FlowCompare(f, p) != 0) {
618  /* we found our flow, lets put it on top of the
619  * hash list -- this rewards active flows */
620  if (f->hnext) {
621  f->hnext->hprev = f->hprev;
622  }
623  if (f->hprev) {
624  f->hprev->hnext = f->hnext;
625  }
626  if (f == fb->tail) {
627  fb->tail = f->hprev;
628  }
629 
630  f->hnext = fb->head;
631  f->hprev = NULL;
632  fb->head->hprev = f;
633  fb->head = f;
634 
635  /* found our flow, lock & return */
636  FLOWLOCK_WRLOCK(f);
637  if (unlikely(TcpSessionPacketSsnReuse(p, f, f->protoctx) == 1)) {
638  f = TcpReuseReplace(tv, dtv, fb, f, hash, p);
639  if (f == NULL) {
640  FBLOCK_UNLOCK(fb);
641  return NULL;
642  }
643  }
644 
645  FlowReference(dest, f);
646 
647  FBLOCK_UNLOCK(fb);
648  return f;
649  }
650  }
651  }
652 
653  /* lock & return */
654  FLOWLOCK_WRLOCK(f);
655  if (unlikely(TcpSessionPacketSsnReuse(p, f, f->protoctx) == 1)) {
656  f = TcpReuseReplace(tv, dtv, fb, f, hash, p);
657  if (f == NULL) {
658  FBLOCK_UNLOCK(fb);
659  return NULL;
660  }
661  }
662 
663  FlowReference(dest, f);
664 
665  FBLOCK_UNLOCK(fb);
666  return f;
667 }
668 
669 static inline int FlowCompareKey(Flow *f, FlowKey *key)
670 {
671  if ((f->proto != IPPROTO_TCP) && (f->proto != IPPROTO_UDP))
672  return 0;
673  return CMP_FLOW(f, key);
674 }
675 
676 /** \brief Get or create a Flow using a FlowKey
677  *
678  * Hash retrieval function for flows. Looks up the hash bucket containing the
679  * flow pointer. Then compares the packet with the found flow to see if it is
680  * the flow we need. If it isn't, walk the list until the right flow is found.
681  * Return a new Flow if ever no Flow was found.
682  *
683  *
684  * \param key Pointer to FlowKey build using flow to look for
685  * \param ttime time to use for flow creation
686  * \param hash Value of the flow hash
687  * \retval f *LOCKED* flow or NULL
688  */
689 
690 Flow *FlowGetFromFlowKey(FlowKey *key, struct timespec *ttime, const uint32_t hash)
691 {
692  Flow *f = FlowGetExistingFlowFromHash(key, hash);
693 
694  if (f != NULL) {
695  return f;
696  }
697 
698  /* No existing flow so let's get one new */
700  if (f == NULL) {
701  /* now see if we can alloc a new flow */
702  f = FlowAlloc();
703  if (f == NULL) {
704  SCLogDebug("Can't get a spare flow at start");
705  return NULL;
706  }
707  }
708  f->proto = key->proto;
709  f->vlan_id[0] = key->vlan_id[0];
710  f->vlan_id[1] = key->vlan_id[1];
711  f->src.addr_data32[0] = key->src.addr_data32[0];
712  f->src.addr_data32[1] = key->src.addr_data32[1];
713  f->src.addr_data32[2] = key->src.addr_data32[2];
714  f->src.addr_data32[3] = key->src.addr_data32[3];
715  f->dst.addr_data32[0] = key->dst.addr_data32[0];
716  f->dst.addr_data32[1] = key->dst.addr_data32[1];
717  f->dst.addr_data32[2] = key->dst.addr_data32[2];
718  f->dst.addr_data32[3] = key->dst.addr_data32[3];
719  f->sp = key->sp;
720  f->dp = key->dp;
721  f->recursion_level = 0;
722  f->flow_hash = hash;
723  if (key->src.family == AF_INET) {
724  f->flags |= FLOW_IPV4;
725  } else if (key->src.family == AF_INET6) {
726  f->flags |= FLOW_IPV6;
727  }
729 
731  /* set timestamp to now */
732  f->startts.tv_sec = ttime->tv_sec;
733  f->startts.tv_usec = ttime->tv_nsec * 1000;
734  f->lastts = f->startts;
735 
736  FlowBucket *fb = &flow_hash[hash % flow_config.hash_size];
737  FBLOCK_LOCK(fb);
738  f->fb = fb;
739  if (fb->head == NULL) {
740  fb->head = f;
741  fb->tail = f;
742  } else {
743  f->hprev = fb->tail;
744  f->hprev->hnext = f;
745  fb->tail = f;
746  }
747  FLOWLOCK_WRLOCK(f);
748  FBLOCK_UNLOCK(fb);
749 
750  return f;
751 }
752 
753 /** \brief Look for existing Flow using a FlowKey
754  *
755  * Hash retrieval function for flows. Looks up the hash bucket containing the
756  * flow pointer. Then compares the packet with the found flow to see if it is
757  * the flow we need. If it isn't, walk the list until the right flow is found.
758  *
759  *
760  * \param key Pointer to FlowKey build using flow to look for
761  * \param hash Value of the flow hash
762  * \retval f *LOCKED* flow or NULL
763  */
764 Flow *FlowGetExistingFlowFromHash(FlowKey *key, const uint32_t hash)
765 {
766  /* get our hash bucket and lock it */
767  FlowBucket *fb = &flow_hash[hash % flow_config.hash_size];
768  FBLOCK_LOCK(fb);
769 
770  SCLogDebug("fb %p fb->head %p", fb, fb->head);
771 
772  /* return if the bucket don't have a flow */
773  if (fb->head == NULL) {
774  FBLOCK_UNLOCK(fb);
775  return NULL;
776  }
777 
778  /* ok, we have a flow in the bucket. Let's find out if it is our flow */
779  Flow *f = fb->head;
780 
781  /* see if this is the flow we are looking for */
782  if (FlowCompareKey(f, key) == 0) {
783  while (f) {
784  f = f->hnext;
785 
786  if (f == NULL) {
787  FBLOCK_UNLOCK(fb);
788  return NULL;
789  }
790 
791  if (FlowCompareKey(f, key) != 0) {
792  /* found our flow, lock & return */
793  FLOWLOCK_WRLOCK(f);
794 
795  FBLOCK_UNLOCK(fb);
796  return f;
797  }
798  }
799  }
800 
801  /* lock & return */
802  FLOWLOCK_WRLOCK(f);
803 
804  FBLOCK_UNLOCK(fb);
805  return f;
806 }
807 
808 /** \internal
809  * \brief Get a flow from the hash directly.
810  *
811  * Called in conditions where the spare queue is empty and memcap is reached.
812  *
813  * Walks the hash until a flow can be freed. Timeouts are disregarded, use_cnt
814  * is adhered to. "flow_prune_idx" atomic int makes sure we don't start at the
815  * top each time since that would clear the top of the hash leading to longer
816  * and longer search times under high pressure (observed).
817  *
818  * \param tv thread vars
819  * \param dtv decode thread vars (for flow log api thread data)
820  *
821  * \retval f flow or NULL
822  */
823 static Flow *FlowGetUsedFlow(ThreadVars *tv, DecodeThreadVars *dtv)
824 {
825  uint32_t idx = SC_ATOMIC_GET(flow_prune_idx) % flow_config.hash_size;
826  uint32_t cnt = flow_config.hash_size;
827 
828  while (cnt--) {
829  if (++idx >= flow_config.hash_size)
830  idx = 0;
831 
832  FlowBucket *fb = &flow_hash[idx];
833 
834  if (FBLOCK_TRYLOCK(fb) != 0)
835  continue;
836 
837  Flow *f = fb->tail;
838  if (f == NULL) {
839  FBLOCK_UNLOCK(fb);
840  continue;
841  }
842 
843  if (FLOWLOCK_TRYWRLOCK(f) != 0) {
844  FBLOCK_UNLOCK(fb);
845  continue;
846  }
847 
848  /** never prune a flow that is used by a packet or stream msg
849  * we are currently processing in one of the threads */
850  if (SC_ATOMIC_GET(f->use_cnt) > 0) {
851  FBLOCK_UNLOCK(fb);
852  FLOWLOCK_UNLOCK(f);
853  continue;
854  }
855 
856  /* remove from the hash */
857  if (f->hprev != NULL)
858  f->hprev->hnext = f->hnext;
859  if (f->hnext != NULL)
860  f->hnext->hprev = f->hprev;
861  if (fb->head == f)
862  fb->head = f->hnext;
863  if (fb->tail == f)
864  fb->tail = f->hprev;
865 
866  f->hnext = NULL;
867  f->hprev = NULL;
868  f->fb = NULL;
869  SC_ATOMIC_SET(fb->next_ts, 0);
870  FBLOCK_UNLOCK(fb);
871 
872  int state = SC_ATOMIC_GET(f->flow_state);
873  if (state == FLOW_STATE_NEW)
875  else if (state == FLOW_STATE_ESTABLISHED)
877  else if (state == FLOW_STATE_CLOSED)
879  else if (state == FLOW_STATE_CAPTURE_BYPASSED)
881  else if (state == FLOW_STATE_LOCAL_BYPASSED)
883 
885 
886  if (SC_ATOMIC_GET(flow_flags) & FLOW_EMERGENCY)
888 
889  /* invoke flow log api */
890  if (dtv && dtv->output_flow_thread_data)
891  (void)OutputFlowLog(tv, dtv->output_flow_thread_data, f);
892 
893  FlowClearMemory(f, f->protomap);
894 
896 
897  FLOWLOCK_UNLOCK(f);
898 
899  (void) SC_ATOMIC_ADD(flow_prune_idx, (flow_config.hash_size - cnt));
900  return f;
901  }
902 
903  return NULL;
904 }
#define SC_ATOMIC_OR(name, val)
Bitwise OR a value from our atomic variable.
Definition: util-atomic.h:154
#define FLOW_TCP_REUSED
Definition: flow.h:51
void FlowSetupPacket(Packet *p)
prepare packet for a life with flow Set PKT_WANTS_FLOW flag to incidate workers should do a flow look...
Definition: flow-hash.c:352
uint32_t hashword(const uint32_t *k, size_t length, uint32_t initval)
#define FLOW_CHECK_MEMCAP(size)
check if a memory alloc would fit in the memcap
Definition: flow-util.h:135
UDPHdr * udph
Definition: decode.h:522
#define SCLogDebug(...)
Definition: util-debug.h:335
#define FBLOCK_UNLOCK(fb)
Definition: flow-hash.h:70
#define FLOW_IPV6
Definition: flow.h:96
uint16_t emb_sport
struct Flow_ * hnext
Definition: flow.h:451
#define ICMPV4_GET_EMB_PROTO(p)
uint8_t proto
Definition: flow.h:344
#define ICMPV4_DEST_UNREACH_IS_VALID(p)
uint32_t addrs[2]
Definition: flow-hash.c:84
#define FLOWLOCK_UNLOCK(fb)
Definition: flow.h:243
Port sp
Definition: flow.h:331
#define FLOW_END_FLAG_STATE_ESTABLISHED
Definition: flow.h:210
#define unlikely(expr)
Definition: util-optimize.h:35
struct FlowHashKey6_ FlowHashKey6
Port sp
Definition: decode.h:413
uint16_t FlowThreadId
Definition: flow.h:305
Port dp
Definition: decode.h:421
Flow * FlowGetExistingFlowFromHash(FlowKey *key, const uint32_t hash)
Look for existing Flow using a FlowKey.
Definition: flow-hash.c:764
uint16_t vlan_id[2]
Definition: flow.h:285
#define SC_ATOMIC_ADD(name, val)
add a value to our atomic variable
Definition: util-atomic.h:107
#define FLOW_EMERGENCY
Definition: flow-private.h:37
Address dst
Definition: decode.h:411
uint8_t FlowGetProtoMapping(uint8_t proto)
Function to map the protocol to the defined FLOW_PROTO_* enumeration.
Definition: flow-util.c:95
#define FLOW_END_FLAG_FORCED
Definition: flow.h:214
#define IPV4_GET_RAW_IPSRC_U32(ip4h)
Definition: decode-ipv4.h:106
Address src
Definition: flow.h:281
uint16_t src
struct timeval startts
Definition: flow.h:458
#define FLOWLOCK_WRLOCK(fb)
Definition: flow.h:240
Flow * FlowGetFlowFromHash(ThreadVars *tv, DecodeThreadVars *dtv, const Packet *p, Flow **dest)
Get Flow for packet.
Definition: flow-hash.c:547
uint16_t ports[2]
Definition: flow-hash.c:85
TCPHdr * tcph
Definition: decode.h:520
#define FLOW_END_FLAG_STATE_BYPASSED
Definition: flow.h:216
uint32_t FlowKeyGetHash(FlowKey *fk)
Definition: flow-hash.c:221
Flow * head
Definition: flow-hash.h:42
#define FlowWakeupFlowManagerThread()
Definition: flow-manager.h:34
void * protoctx
Definition: flow.h:400
uint16_t vlan_id[2]
Definition: decode.h:433
const uint32_t u32[11]
Definition: flow-hash.c:103
FlowConfig flow_config
Definition: flow-private.h:97
struct Flow_ * hprev
Definition: flow.h:452
FlowAddress dst
Definition: flow.h:329
uint16_t counter_flow_udp
Definition: decode.h:683
#define CMP_FLOW_ICMP(f1, f2)
Definition: flow-hash.c:290
uint16_t counter_flow_tcp
Definition: decode.h:682
uint16_t vlan_id[2]
Definition: flow.h:346
SC_ATOMIC_EXTERN(unsigned int, flow_prune_idx)
uint16_t dst
Port sp
Definition: flow.h:282
IPV6Hdr * ip6h
Definition: decode.h:500
#define FLOW_END_FLAG_STATE_NEW
Definition: flow.h:209
char family
Definition: decode.h:109
uint8_t proto
Definition: decode.h:428
uint32_t src[4]
Definition: flow-hash.c:97
uint8_t recursion_level
Definition: decode.h:431
Data structures and function prototypes for keeping state for the detection engine.
#define FLOWLOCK_TRYWRLOCK(fb)
Definition: flow.h:242
int TcpSessionPacketSsnReuse(const Packet *p, const Flow *f, void *tcp_ssn)
uint16_t proto
Definition: flow-hash.c:99
Structure to hold thread specific data for all decode modules.
Definition: decode.h:632
uint8_t recursion_level
Definition: flow.h:284
TmEcode OutputFlowLog(ThreadVars *tv, void *thread_data, Flow *f)
Run flow logger(s)
Definition: output-flow.c:91
uint16_t recur
Definition: flow-hash.c:100
void * output_flow_thread_data
Definition: decode.h:691
#define FLOW_END_FLAG_STATE_CLOSED
Definition: flow.h:211
void StatsIncr(ThreadVars *tv, uint16_t id)
Increments the local counter.
Definition: counters.c:163
uint32_t dst[4]
Definition: flow-hash.c:97
#define ICMPV4_GET_EMB_IPV4(p)
uint16_t counter_flow_icmp4
Definition: decode.h:684
uint16_t counter_flow_memcap
Definition: decode.h:680
Flow * FlowAlloc(void)
allocate a flow
Definition: flow-util.c:51
union Address_::@40 address
struct timeval lastts
Definition: flow.h:358
struct FlowBucket_ * fb
Definition: flow.h:453
IPV4Hdr * ip4h
Definition: decode.h:498
uint16_t recur
Definition: flow-hash.c:87
uint8_t flow_end_flags
Definition: flow.h:406
#define SC_ATOMIC_SET(name, val)
Set the value for the atomic variable.
Definition: util-atomic.h:207
Flow * FlowDequeue(FlowQueue *q)
remove a flow from the queue
Definition: flow-queue.c:105
FlowThreadId thread_id
Definition: flow.h:426
FlowBucket * flow_hash
Definition: flow-private.h:96
const uint32_t u32[5]
Definition: flow-hash.c:90
Port dp
Definition: flow.h:338
Address dst
Definition: flow.h:281
#define FLOW_END_FLAG_EMERGENCY
Definition: flow.h:212
uint32_t address_un_data32[4]
Definition: decode.h:111
unsigned int FlowStorageSize(void)
Definition: flow-storage.c:34
Definition: flow.h:279
#define FBLOCK_TRYLOCK(fb)
Definition: flow-hash.h:69
#define PKT_IS_ICMPV4(p)
Definition: decode.h:253
uint16_t ports[2]
Definition: flow-hash.c:98
void FlowUpdateState(Flow *f, enum FlowState s)
Definition: flow.c:1101
uint16_t vlan_id[2]
Definition: flow-hash.c:101
uint16_t emb_dport
uint16_t counter_flow_icmp6
Definition: decode.h:685
#define SC_ATOMIC_GET(name)
Get the value from the atomic variable.
Definition: util-atomic.h:192
#define IPV4_GET_RAW_IPDST_U32(ip4h)
Definition: decode-ipv4.h:108
#define ICMPV4_IS_ERROR_MSG(p)
uint32_t flow_hash
Definition: flow.h:353
uint8_t recursion_level
Definition: flow.h:345
FlowAddress src
Definition: flow.h:329
uint32_t hash_rand
Definition: flow.h:263
#define PKT_WANTS_FLOW
Definition: decode.h:1113
struct FlowHashKey4_ FlowHashKey4
int FlowClearMemory(Flow *f, uint8_t proto_map)
Function clear the flow memory before queueing it to spare flow queue.
Definition: flow.c:1027
uint32_t flow_hash
Definition: decode.h:447
Per thread variable structure.
Definition: threadvars.h:57
void FlowTimeoutsEmergency(void)
Definition: flow-manager.c:95
uint8_t proto
Definition: flow.h:283
uint32_t flags
Definition: decode.h:441
void FlowInit(Flow *f, const Packet *p)
Definition: flow-util.c:147
Flow * FlowGetFromFlowKey(FlowKey *key, struct timespec *ttime, const uint32_t hash)
Get or create a Flow using a FlowKey.
Definition: flow-hash.c:690
uint8_t protomap
Definition: flow.h:404
Flow data structure.
Definition: flow.h:325
#define FLOW_IPV4
Definition: flow.h:94
uint16_t vlan_id[2]
Definition: flow-hash.c:88
Port dp
Definition: flow.h:282
uint32_t flags
Definition: flow.h:379
ICMPV4Vars icmpv4vars
Definition: decode.h:513
#define FBLOCK_LOCK(fb)
Definition: flow-hash.h:68
Address src
Definition: decode.h:410
FlowQueue flow_spare_q
Definition: flow-private.h:91
uint16_t proto
Definition: flow-hash.c:86
uint32_t hash_size
Definition: flow.h:264
#define CMP_FLOW(f1, f2)
Definition: flow-hash.c:279