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  /* g_vlan_mask sets the vlan_ids to 0 if vlan.use-for-tracking
139  * is disabled. */
140  fhk.vlan_id[0] = p->vlan_id[0] & g_vlan_mask;
141  fhk.vlan_id[1] = p->vlan_id[1] & g_vlan_mask;
142 
143  hash = hashword(fhk.u32, 5, flow_config.hash_rand);
144 
145  } else if (ICMPV4_DEST_UNREACH_IS_VALID(p)) {
146  uint32_t psrc = IPV4_GET_RAW_IPSRC_U32(ICMPV4_GET_EMB_IPV4(p));
147  uint32_t pdst = IPV4_GET_RAW_IPDST_U32(ICMPV4_GET_EMB_IPV4(p));
148  FlowHashKey4 fhk;
149 
150  const int ai = (psrc > pdst);
151  fhk.addrs[1-ai] = psrc;
152  fhk.addrs[ai] = pdst;
153 
154  const int pi = (p->icmpv4vars.emb_sport > p->icmpv4vars.emb_dport);
155  fhk.ports[1-pi] = p->icmpv4vars.emb_sport;
156  fhk.ports[pi] = p->icmpv4vars.emb_dport;
157 
158  fhk.proto = (uint16_t)ICMPV4_GET_EMB_PROTO(p);
159  fhk.recur = (uint16_t)p->recursion_level;
160  fhk.vlan_id[0] = p->vlan_id[0] & g_vlan_mask;
161  fhk.vlan_id[1] = p->vlan_id[1] & g_vlan_mask;
162 
163  hash = hashword(fhk.u32, 5, flow_config.hash_rand);
164 
165  } else {
166  FlowHashKey4 fhk;
167  const int ai = (p->src.addr_data32[0] > p->dst.addr_data32[0]);
168  fhk.addrs[1-ai] = p->src.addr_data32[0];
169  fhk.addrs[ai] = p->dst.addr_data32[0];
170  fhk.ports[0] = 0xfeed;
171  fhk.ports[1] = 0xbeef;
172  fhk.proto = (uint16_t)p->proto;
173  fhk.recur = (uint16_t)p->recursion_level;
174  fhk.vlan_id[0] = p->vlan_id[0] & g_vlan_mask;
175  fhk.vlan_id[1] = p->vlan_id[1] & g_vlan_mask;
176 
177  hash = hashword(fhk.u32, 5, flow_config.hash_rand);
178  }
179  } else if (p->ip6h != NULL) {
180  FlowHashKey6 fhk;
181  if (FlowHashRawAddressIPv6GtU32(p->src.addr_data32, p->dst.addr_data32)) {
182  fhk.src[0] = p->src.addr_data32[0];
183  fhk.src[1] = p->src.addr_data32[1];
184  fhk.src[2] = p->src.addr_data32[2];
185  fhk.src[3] = p->src.addr_data32[3];
186  fhk.dst[0] = p->dst.addr_data32[0];
187  fhk.dst[1] = p->dst.addr_data32[1];
188  fhk.dst[2] = p->dst.addr_data32[2];
189  fhk.dst[3] = p->dst.addr_data32[3];
190  } else {
191  fhk.src[0] = p->dst.addr_data32[0];
192  fhk.src[1] = p->dst.addr_data32[1];
193  fhk.src[2] = p->dst.addr_data32[2];
194  fhk.src[3] = p->dst.addr_data32[3];
195  fhk.dst[0] = p->src.addr_data32[0];
196  fhk.dst[1] = p->src.addr_data32[1];
197  fhk.dst[2] = p->src.addr_data32[2];
198  fhk.dst[3] = p->src.addr_data32[3];
199  }
200 
201  const int pi = (p->sp > p->dp);
202  fhk.ports[1-pi] = p->sp;
203  fhk.ports[pi] = p->dp;
204  fhk.proto = (uint16_t)p->proto;
205  fhk.recur = (uint16_t)p->recursion_level;
206  fhk.vlan_id[0] = p->vlan_id[0] & g_vlan_mask;
207  fhk.vlan_id[1] = p->vlan_id[1] & g_vlan_mask;
208 
209  hash = hashword(fhk.u32, 11, flow_config.hash_rand);
210  }
211 
212  return hash;
213 }
214 
215 /**
216  * Basic hashing function for FlowKey
217  *
218  * \note Function only used for bypass and TCP or UDP flows
219  *
220  * \note this is only used at start to create Flow from pinned maps
221  * so fairness is not an issue
222  */
223 uint32_t FlowKeyGetHash(FlowKey *fk)
224 {
225  uint32_t hash = 0;
226 
227  if (fk->src.family == AF_INET) {
228  FlowHashKey4 fhk;
229  int ai = (fk->src.address.address_un_data32[0] > fk->dst.address.address_un_data32[0]);
230  fhk.addrs[1-ai] = fk->src.address.address_un_data32[0];
231  fhk.addrs[ai] = fk->dst.address.address_un_data32[0];
232 
233  const int pi = (fk->sp > fk->dp);
234  fhk.ports[1-pi] = fk->sp;
235  fhk.ports[pi] = fk->dp;
236 
237  fhk.proto = (uint16_t)fk->proto;
238  fhk.recur = (uint16_t)fk->recursion_level;
239  fhk.vlan_id[0] = fk->vlan_id[0] & g_vlan_mask;
240  fhk.vlan_id[1] = fk->vlan_id[1] & g_vlan_mask;
241 
242  hash = hashword(fhk.u32, 5, flow_config.hash_rand);
243  } else {
244  FlowHashKey6 fhk;
245  if (FlowHashRawAddressIPv6GtU32(fk->src.address.address_un_data32,
247  fhk.src[0] = fk->src.address.address_un_data32[0];
248  fhk.src[1] = fk->src.address.address_un_data32[1];
249  fhk.src[2] = fk->src.address.address_un_data32[2];
250  fhk.src[3] = fk->src.address.address_un_data32[3];
251  fhk.dst[0] = fk->dst.address.address_un_data32[0];
252  fhk.dst[1] = fk->dst.address.address_un_data32[1];
253  fhk.dst[2] = fk->dst.address.address_un_data32[2];
254  fhk.dst[3] = fk->dst.address.address_un_data32[3];
255  } else {
256  fhk.src[0] = fk->dst.address.address_un_data32[0];
257  fhk.src[1] = fk->dst.address.address_un_data32[1];
258  fhk.src[2] = fk->dst.address.address_un_data32[2];
259  fhk.src[3] = fk->dst.address.address_un_data32[3];
260  fhk.dst[0] = fk->src.address.address_un_data32[0];
261  fhk.dst[1] = fk->src.address.address_un_data32[1];
262  fhk.dst[2] = fk->src.address.address_un_data32[2];
263  fhk.dst[3] = fk->src.address.address_un_data32[3];
264  }
265 
266  const int pi = (fk->sp > fk->dp);
267  fhk.ports[1-pi] = fk->sp;
268  fhk.ports[pi] = fk->dp;
269  fhk.proto = (uint16_t)fk->proto;
270  fhk.recur = (uint16_t)fk->recursion_level;
271  fhk.vlan_id[0] = fk->vlan_id[0] & g_vlan_mask;
272  fhk.vlan_id[1] = fk->vlan_id[1] & g_vlan_mask;
273 
274  hash = hashword(fhk.u32, 11, flow_config.hash_rand);
275  }
276  return hash;
277 }
278 
279 static inline bool CmpAddrs(const uint32_t addr1[4], const uint32_t addr2[4])
280 {
281  return addr1[0] == addr2[0] && addr1[1] == addr2[1] &&
282  addr1[2] == addr2[2] && addr1[3] == addr2[3];
283 }
284 
285 static inline bool CmpAddrsAndPorts(const uint32_t src1[4],
286  const uint32_t dst1[4], Port src_port1, Port dst_port1,
287  const uint32_t src2[4], const uint32_t dst2[4], Port src_port2,
288  Port dst_port2)
289 {
290  /* Compare the source and destination addresses. If they are not equal,
291  * compare the first source address with the second destination address,
292  * and vice versa. Likewise for ports. */
293  return (CmpAddrs(src1, src2) && CmpAddrs(dst1, dst2) &&
294  src_port1 == src_port2 && dst_port1 == dst_port2) ||
295  (CmpAddrs(src1, dst2) && CmpAddrs(dst1, src2) &&
296  src_port1 == dst_port2 && dst_port1 == src_port2);
297 }
298 
299 static inline bool CmpVlanIds(const uint16_t vlan_id1[2], const uint16_t vlan_id2[2])
300 {
301  return ((vlan_id1[0] ^ vlan_id2[0]) & g_vlan_mask) == 0 &&
302  ((vlan_id1[1] ^ vlan_id2[1]) & g_vlan_mask) == 0;
303 }
304 
305 /* Since two or more flows can have the same hash key, we need to compare
306  * the flow with the current packet or flow key. */
307 static inline bool CmpFlowPacket(const Flow *f, const Packet *p)
308 {
309  const uint32_t *f_src = f->src.address.address_un_data32;
310  const uint32_t *f_dst = f->dst.address.address_un_data32;
311  const uint32_t *p_src = p->src.address.address_un_data32;
312  const uint32_t *p_dst = p->dst.address.address_un_data32;
313  return CmpAddrsAndPorts(f_src, f_dst, f->sp, f->dp, p_src, p_dst, p->sp,
314  p->dp) && f->proto == p->proto &&
315  f->recursion_level == p->recursion_level &&
316  CmpVlanIds(f->vlan_id, p->vlan_id);
317 }
318 
319 static inline bool CmpFlowKey(const Flow *f, const FlowKey *k)
320 {
321  const uint32_t *f_src = f->src.address.address_un_data32;
322  const uint32_t *f_dst = f->dst.address.address_un_data32;
323  const uint32_t *k_src = k->src.address.address_un_data32;
324  const uint32_t *k_dst = k->dst.address.address_un_data32;
325  return CmpAddrsAndPorts(f_src, f_dst, f->sp, f->dp, k_src, k_dst, k->sp,
326  k->dp) && f->proto == k->proto &&
327  f->recursion_level == k->recursion_level &&
328  CmpVlanIds(f->vlan_id, k->vlan_id);
329 }
330 
331 static inline bool CmpAddrsAndICMPTypes(const uint32_t src1[4],
332  const uint32_t dst1[4], uint8_t icmp_s_type1, uint8_t icmp_d_type1,
333  const uint32_t src2[4], const uint32_t dst2[4], uint8_t icmp_s_type2,
334  uint8_t icmp_d_type2)
335 {
336  /* Compare the source and destination addresses. If they are not equal,
337  * compare the first source address with the second destination address,
338  * and vice versa. Likewise for icmp types. */
339  return (CmpAddrs(src1, src2) && CmpAddrs(dst1, dst2) &&
340  icmp_s_type1 == icmp_s_type2 && icmp_d_type1 == icmp_d_type2) ||
341  (CmpAddrs(src1, dst2) && CmpAddrs(dst1, src2) &&
342  icmp_s_type1 == icmp_d_type2 && icmp_d_type1 == icmp_s_type2);
343 }
344 
345 static inline bool CmpFlowICMPPacket(const Flow *f, const Packet *p)
346 {
347  const uint32_t *f_src = f->src.address.address_un_data32;
348  const uint32_t *f_dst = f->dst.address.address_un_data32;
349  const uint32_t *p_src = p->src.address.address_un_data32;
350  const uint32_t *p_dst = p->dst.address.address_un_data32;
351  return CmpAddrsAndICMPTypes(f_src, f_dst, f->icmp_s.type,
352  f->icmp_d.type, p_src, p_dst, p->icmp_s.type, p->icmp_d.type) &&
353  f->proto == p->proto && f->recursion_level == p->recursion_level &&
354  CmpVlanIds(f->vlan_id, p->vlan_id);
355 }
356 
357 /**
358  * \brief See if a ICMP packet belongs to a flow by comparing the embedded
359  * packet in the ICMP error packet to the flow.
360  *
361  * \param f flow
362  * \param p ICMP packet
363  *
364  * \retval 1 match
365  * \retval 0 no match
366  */
367 static inline int FlowCompareICMPv4(Flow *f, const Packet *p)
368 {
370  /* first check the direction of the flow, in other words, the client ->
371  * server direction as it's most likely the ICMP error will be a
372  * response to the clients traffic */
373  if ((f->src.addr_data32[0] == IPV4_GET_RAW_IPSRC_U32( ICMPV4_GET_EMB_IPV4(p) )) &&
374  (f->dst.addr_data32[0] == IPV4_GET_RAW_IPDST_U32( ICMPV4_GET_EMB_IPV4(p) )) &&
375  f->sp == p->icmpv4vars.emb_sport &&
376  f->dp == p->icmpv4vars.emb_dport &&
377  f->proto == ICMPV4_GET_EMB_PROTO(p) &&
378  f->recursion_level == p->recursion_level &&
379  f->vlan_id[0] == p->vlan_id[0] &&
380  f->vlan_id[1] == p->vlan_id[1])
381  {
382  return 1;
383 
384  /* check the less likely case where the ICMP error was a response to
385  * a packet from the server. */
386  } else if ((f->dst.addr_data32[0] == IPV4_GET_RAW_IPSRC_U32( ICMPV4_GET_EMB_IPV4(p) )) &&
387  (f->src.addr_data32[0] == IPV4_GET_RAW_IPDST_U32( ICMPV4_GET_EMB_IPV4(p) )) &&
388  f->dp == p->icmpv4vars.emb_sport &&
389  f->sp == p->icmpv4vars.emb_dport &&
390  f->proto == ICMPV4_GET_EMB_PROTO(p) &&
391  f->recursion_level == p->recursion_level &&
392  f->vlan_id[0] == p->vlan_id[0] &&
393  f->vlan_id[1] == p->vlan_id[1])
394  {
395  return 1;
396  }
397 
398  /* no match, fall through */
399  } else {
400  /* just treat ICMP as a normal proto for now */
401  return CmpFlowICMPPacket(f, p);
402  }
403 
404  return 0;
405 }
406 
408 {
409  p->flags |= PKT_WANTS_FLOW;
410  p->flow_hash = FlowGetHash(p);
411 }
412 
413 int TcpSessionPacketSsnReuse(const Packet *p, const Flow *f, void *tcp_ssn);
414 
415 static inline int FlowCompare(Flow *f, const Packet *p)
416 {
417  if (p->proto == IPPROTO_ICMP) {
418  return FlowCompareICMPv4(f, p);
419  } else if (p->proto == IPPROTO_TCP) {
420  if (CmpFlowPacket(f, p) == 0)
421  return 0;
422 
423  /* if this session is 'reused', we don't return it anymore,
424  * so return false on the compare */
425  if (f->flags & FLOW_TCP_REUSED)
426  return 0;
427 
428  return 1;
429  } else {
430  return CmpFlowPacket(f, p);
431  }
432 }
433 
434 /**
435  * \brief Check if we should create a flow based on a packet
436  *
437  * We use this check to filter out flow creation based on:
438  * - ICMP error messages
439  *
440  * \param p packet
441  * \retval 1 true
442  * \retval 0 false
443  */
444 static inline int FlowCreateCheck(const Packet *p)
445 {
446  if (PKT_IS_ICMPV4(p)) {
447  if (ICMPV4_IS_ERROR_MSG(p)) {
448  return 0;
449  }
450  }
451 
452  return 1;
453 }
454 
455 static inline void FlowUpdateCounter(ThreadVars *tv, DecodeThreadVars *dtv,
456  uint8_t proto)
457 {
458 #ifdef UNITTESTS
459  if (tv && dtv) {
460 #endif
461  switch (proto){
462  case IPPROTO_UDP:
463  StatsIncr(tv, dtv->counter_flow_udp);
464  break;
465  case IPPROTO_TCP:
466  StatsIncr(tv, dtv->counter_flow_tcp);
467  break;
468  case IPPROTO_ICMP:
469  StatsIncr(tv, dtv->counter_flow_icmp4);
470  break;
471  case IPPROTO_ICMPV6:
472  StatsIncr(tv, dtv->counter_flow_icmp6);
473  break;
474  }
475 #ifdef UNITTESTS
476  }
477 #endif
478 }
479 
480 /**
481  * \brief Get a new flow
482  *
483  * Get a new flow. We're checking memcap first and will try to make room
484  * if the memcap is reached.
485  *
486  * \param tv thread vars
487  * \param dtv decode thread vars (for flow log api thread data)
488  *
489  * \retval f *LOCKED* flow on succes, NULL on error.
490  */
491 static Flow *FlowGetNew(ThreadVars *tv, DecodeThreadVars *dtv, const Packet *p)
492 {
493  Flow *f = NULL;
494 
495  if (FlowCreateCheck(p) == 0) {
496  return NULL;
497  }
498 
499  /* get a flow from the spare queue */
501  if (f == NULL) {
502  /* If we reached the max memcap, we get a used flow */
503  if (!(FLOW_CHECK_MEMCAP(sizeof(Flow) + FlowStorageSize()))) {
504  /* declare state of emergency */
505  if (!(SC_ATOMIC_GET(flow_flags) & FLOW_EMERGENCY)) {
506  SC_ATOMIC_OR(flow_flags, FLOW_EMERGENCY);
507 
509 
510  /* under high load, waking up the flow mgr each time leads
511  * to high cpu usage. Flows are not timed out much faster if
512  * we check a 1000 times a second. */
514  }
515 
516  f = FlowGetUsedFlow(tv, dtv);
517  if (f == NULL) {
518  /* max memcap reached, so increments the counter */
519  if (tv != NULL && dtv != NULL) {
520  StatsIncr(tv, dtv->counter_flow_memcap);
521  }
522 
523  /* very rare, but we can fail. Just giving up */
524  return NULL;
525  }
526 
527  /* freed a flow, but it's unlocked */
528  } else {
529  /* now see if we can alloc a new flow */
530  f = FlowAlloc();
531  if (f == NULL) {
532  if (tv != NULL && dtv != NULL) {
533  StatsIncr(tv, dtv->counter_flow_memcap);
534  }
535  return NULL;
536  }
537 
538  /* flow is initialized but *unlocked* */
539  }
540  } else {
541  /* flow has been recycled before it went into the spare queue */
542 
543  /* flow is initialized (recylced) but *unlocked* */
544  }
545 
546  FLOWLOCK_WRLOCK(f);
547  FlowUpdateCounter(tv, dtv, p->proto);
548  return f;
549 }
550 
551 static Flow *TcpReuseReplace(ThreadVars *tv, DecodeThreadVars *dtv,
552  FlowBucket *fb, Flow *old_f,
553  const uint32_t hash, const Packet *p)
554 {
555  /* tag flow as reused so future lookups won't find it */
556  old_f->flags |= FLOW_TCP_REUSED;
557  /* get some settings that we move over to the new flow */
558  FlowThreadId thread_id[2] = { old_f->thread_id[0], old_f->thread_id[1] };
559 
560  /* since fb lock is still held this flow won't be found until we are done */
561  FLOWLOCK_UNLOCK(old_f);
562 
563  /* Get a new flow. It will be either a locked flow or NULL */
564  Flow *f = FlowGetNew(tv, dtv, p);
565  if (f == NULL) {
566  return NULL;
567  }
568 
569  /* flow is locked */
570 
571  /* put at the start of the list */
572  f->hnext = fb->head;
573  fb->head->hprev = f;
574  fb->head = f;
575 
576  /* initialize and return */
577  FlowInit(f, p);
578  f->flow_hash = hash;
579  f->fb = fb;
580 
581  f->thread_id[0] = thread_id[0];
582  f->thread_id[1] = thread_id[1];
583  return f;
584 }
585 
586 /** \brief Get Flow for packet
587  *
588  * Hash retrieval function for flows. Looks up the hash bucket containing the
589  * flow pointer. Then compares the packet with the found flow to see if it is
590  * the flow we need. If it isn't, walk the list until the right flow is found.
591  *
592  * If the flow is not found or the bucket was emtpy, a new flow is taken from
593  * the queue. FlowDequeue() will alloc new flows as long as we stay within our
594  * memcap limit.
595  *
596  * The p->flow pointer is updated to point to the flow.
597  *
598  * \param tv thread vars
599  * \param dtv decode thread vars (for flow log api thread data)
600  *
601  * \retval f *LOCKED* flow or NULL
602  */
604 {
605  Flow *f = NULL;
606 
607  /* get our hash bucket and lock it */
608  const uint32_t hash = p->flow_hash;
609  FlowBucket *fb = &flow_hash[hash % flow_config.hash_size];
610  FBLOCK_LOCK(fb);
611 
612  SCLogDebug("fb %p fb->head %p", fb, fb->head);
613 
614  /* see if the bucket already has a flow */
615  if (fb->head == NULL) {
616  f = FlowGetNew(tv, dtv, p);
617  if (f == NULL) {
618  FBLOCK_UNLOCK(fb);
619  return NULL;
620  }
621 
622  /* flow is locked */
623  fb->head = f;
624  fb->tail = f;
625 
626  /* got one, now lock, initialize and return */
627  FlowInit(f, p);
628  f->flow_hash = hash;
629  f->fb = fb;
631 
632  FlowReference(dest, f);
633 
634  FBLOCK_UNLOCK(fb);
635  return f;
636  }
637 
638  /* ok, we have a flow in the bucket. Let's find out if it is our flow */
639  f = fb->head;
640 
641  /* see if this is the flow we are looking for */
642  if (FlowCompare(f, p) == 0) {
643  Flow *pf = NULL; /* previous flow */
644 
645  while (f) {
646  pf = f;
647  f = f->hnext;
648 
649  if (f == NULL) {
650  f = pf->hnext = FlowGetNew(tv, dtv, p);
651  if (f == NULL) {
652  FBLOCK_UNLOCK(fb);
653  return NULL;
654  }
655  fb->tail = f;
656 
657  /* flow is locked */
658 
659  f->hprev = pf;
660 
661  /* initialize and return */
662  FlowInit(f, p);
663  f->flow_hash = hash;
664  f->fb = fb;
666 
667  FlowReference(dest, f);
668 
669  FBLOCK_UNLOCK(fb);
670  return f;
671  }
672 
673  if (FlowCompare(f, p) != 0) {
674  /* we found our flow, lets put it on top of the
675  * hash list -- this rewards active flows */
676  if (f->hnext) {
677  f->hnext->hprev = f->hprev;
678  }
679  if (f->hprev) {
680  f->hprev->hnext = f->hnext;
681  }
682  if (f == fb->tail) {
683  fb->tail = f->hprev;
684  }
685 
686  f->hnext = fb->head;
687  f->hprev = NULL;
688  fb->head->hprev = f;
689  fb->head = f;
690 
691  /* found our flow, lock & return */
692  FLOWLOCK_WRLOCK(f);
693  if (unlikely(TcpSessionPacketSsnReuse(p, f, f->protoctx) == 1)) {
694  f = TcpReuseReplace(tv, dtv, fb, f, hash, p);
695  if (f == NULL) {
696  FBLOCK_UNLOCK(fb);
697  return NULL;
698  }
699  }
700 
701  FlowReference(dest, f);
702 
703  FBLOCK_UNLOCK(fb);
704  return f;
705  }
706  }
707  }
708 
709  /* lock & return */
710  FLOWLOCK_WRLOCK(f);
711  if (unlikely(TcpSessionPacketSsnReuse(p, f, f->protoctx) == 1)) {
712  f = TcpReuseReplace(tv, dtv, fb, f, hash, p);
713  if (f == NULL) {
714  FBLOCK_UNLOCK(fb);
715  return NULL;
716  }
717  }
718 
719  FlowReference(dest, f);
720 
721  FBLOCK_UNLOCK(fb);
722  return f;
723 }
724 
725 static inline int FlowCompareKey(Flow *f, FlowKey *key)
726 {
727  if ((f->proto != IPPROTO_TCP) && (f->proto != IPPROTO_UDP))
728  return 0;
729  return CmpFlowKey(f, key);
730 }
731 
732 /** \brief Get or create a Flow using a FlowKey
733  *
734  * Hash retrieval function for flows. Looks up the hash bucket containing the
735  * flow pointer. Then compares the packet with the found flow to see if it is
736  * the flow we need. If it isn't, walk the list until the right flow is found.
737  * Return a new Flow if ever no Flow was found.
738  *
739  *
740  * \param key Pointer to FlowKey build using flow to look for
741  * \param ttime time to use for flow creation
742  * \param hash Value of the flow hash
743  * \retval f *LOCKED* flow or NULL
744  */
745 
746 Flow *FlowGetFromFlowKey(FlowKey *key, struct timespec *ttime, const uint32_t hash)
747 {
748  Flow *f = FlowGetExistingFlowFromHash(key, hash);
749 
750  if (f != NULL) {
751  return f;
752  }
753 
754  /* No existing flow so let's get one new */
756  if (f == NULL) {
757  /* now see if we can alloc a new flow */
758  f = FlowAlloc();
759  if (f == NULL) {
760  SCLogDebug("Can't get a spare flow at start");
761  return NULL;
762  }
763  }
764  f->proto = key->proto;
765  f->vlan_id[0] = key->vlan_id[0];
766  f->vlan_id[1] = key->vlan_id[1];
767  f->src.addr_data32[0] = key->src.addr_data32[0];
768  f->src.addr_data32[1] = key->src.addr_data32[1];
769  f->src.addr_data32[2] = key->src.addr_data32[2];
770  f->src.addr_data32[3] = key->src.addr_data32[3];
771  f->dst.addr_data32[0] = key->dst.addr_data32[0];
772  f->dst.addr_data32[1] = key->dst.addr_data32[1];
773  f->dst.addr_data32[2] = key->dst.addr_data32[2];
774  f->dst.addr_data32[3] = key->dst.addr_data32[3];
775  f->sp = key->sp;
776  f->dp = key->dp;
777  f->recursion_level = 0;
778  f->flow_hash = hash;
779  if (key->src.family == AF_INET) {
780  f->flags |= FLOW_IPV4;
781  } else if (key->src.family == AF_INET6) {
782  f->flags |= FLOW_IPV6;
783  }
784 
786  /* set timestamp to now */
787  f->startts.tv_sec = ttime->tv_sec;
788  f->startts.tv_usec = ttime->tv_nsec * 1000;
789  f->lastts = f->startts;
790 
791  FlowBucket *fb = &flow_hash[hash % flow_config.hash_size];
792  FBLOCK_LOCK(fb);
793  f->fb = fb;
794  if (fb->head == NULL) {
795  fb->head = f;
796  fb->tail = f;
797  } else {
798  f->hprev = fb->tail;
799  f->hprev->hnext = f;
800  fb->tail = f;
801  }
802  FLOWLOCK_WRLOCK(f);
803  FBLOCK_UNLOCK(fb);
804 
805  return f;
806 }
807 
808 /** \brief Look for existing Flow using a FlowKey
809  *
810  * Hash retrieval function for flows. Looks up the hash bucket containing the
811  * flow pointer. Then compares the packet with the found flow to see if it is
812  * the flow we need. If it isn't, walk the list until the right flow is found.
813  *
814  *
815  * \param key Pointer to FlowKey build using flow to look for
816  * \param hash Value of the flow hash
817  * \retval f *LOCKED* flow or NULL
818  */
819 Flow *FlowGetExistingFlowFromHash(FlowKey *key, const uint32_t hash)
820 {
821  /* get our hash bucket and lock it */
822  FlowBucket *fb = &flow_hash[hash % flow_config.hash_size];
823  FBLOCK_LOCK(fb);
824 
825  SCLogDebug("fb %p fb->head %p", fb, fb->head);
826 
827  /* return if the bucket don't have a flow */
828  if (fb->head == NULL) {
829  FBLOCK_UNLOCK(fb);
830  return NULL;
831  }
832 
833  /* ok, we have a flow in the bucket. Let's find out if it is our flow */
834  Flow *f = fb->head;
835 
836  /* see if this is the flow we are looking for */
837  if (FlowCompareKey(f, key) == 0) {
838  while (f) {
839  f = f->hnext;
840 
841  if (f == NULL) {
842  FBLOCK_UNLOCK(fb);
843  return NULL;
844  }
845 
846  if (FlowCompareKey(f, key) != 0) {
847  /* found our flow, lock & return */
848  FLOWLOCK_WRLOCK(f);
849 
850  FBLOCK_UNLOCK(fb);
851  return f;
852  }
853  }
854  }
855 
856  /* lock & return */
857  FLOWLOCK_WRLOCK(f);
858 
859  FBLOCK_UNLOCK(fb);
860  return f;
861 }
862 
863 /** \internal
864  * \brief Get a flow from the hash directly.
865  *
866  * Called in conditions where the spare queue is empty and memcap is reached.
867  *
868  * Walks the hash until a flow can be freed. Timeouts are disregarded, use_cnt
869  * is adhered to. "flow_prune_idx" atomic int makes sure we don't start at the
870  * top each time since that would clear the top of the hash leading to longer
871  * and longer search times under high pressure (observed).
872  *
873  * \param tv thread vars
874  * \param dtv decode thread vars (for flow log api thread data)
875  *
876  * \retval f flow or NULL
877  */
878 static Flow *FlowGetUsedFlow(ThreadVars *tv, DecodeThreadVars *dtv)
879 {
880  uint32_t idx = SC_ATOMIC_GET(flow_prune_idx) % flow_config.hash_size;
881  uint32_t cnt = flow_config.hash_size;
882 
883  while (cnt--) {
884  if (++idx >= flow_config.hash_size)
885  idx = 0;
886 
887  FlowBucket *fb = &flow_hash[idx];
888 
889  if (FBLOCK_TRYLOCK(fb) != 0)
890  continue;
891 
892  Flow *f = fb->tail;
893  if (f == NULL) {
894  FBLOCK_UNLOCK(fb);
895  continue;
896  }
897 
898  if (FLOWLOCK_TRYWRLOCK(f) != 0) {
899  FBLOCK_UNLOCK(fb);
900  continue;
901  }
902 
903  /** never prune a flow that is used by a packet or stream msg
904  * we are currently processing in one of the threads */
905  if (SC_ATOMIC_GET(f->use_cnt) > 0) {
906  FBLOCK_UNLOCK(fb);
907  FLOWLOCK_UNLOCK(f);
908  continue;
909  }
910 
911  /* remove from the hash */
912  if (f->hprev != NULL)
913  f->hprev->hnext = f->hnext;
914  if (f->hnext != NULL)
915  f->hnext->hprev = f->hprev;
916  if (fb->head == f)
917  fb->head = f->hnext;
918  if (fb->tail == f)
919  fb->tail = f->hprev;
920 
921  f->hnext = NULL;
922  f->hprev = NULL;
923  f->fb = NULL;
924  SC_ATOMIC_SET(fb->next_ts, 0);
925  FBLOCK_UNLOCK(fb);
926 
927  int state = SC_ATOMIC_GET(f->flow_state);
928  if (state == FLOW_STATE_NEW)
930  else if (state == FLOW_STATE_ESTABLISHED)
932  else if (state == FLOW_STATE_CLOSED)
934 #ifdef CAPTURE_OFFLOAD
935  else if (state == FLOW_STATE_CAPTURE_BYPASSED)
937 #endif
938  else if (state == FLOW_STATE_LOCAL_BYPASSED)
940 
942 
943  if (SC_ATOMIC_GET(flow_flags) & FLOW_EMERGENCY)
945 
946  /* invoke flow log api */
947  if (dtv && dtv->output_flow_thread_data)
948  (void)OutputFlowLog(tv, dtv->output_flow_thread_data, f);
949 
950  FlowClearMemory(f, f->protomap);
951 
953 
954  FLOWLOCK_UNLOCK(f);
955 
956  (void) SC_ATOMIC_ADD(flow_prune_idx, (flow_config.hash_size - cnt));
957  return f;
958  }
959 
960  return NULL;
961 }
#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:407
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:137
UDPHdr * udph
Definition: decode.h:524
#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:415
uint16_t FlowThreadId
Definition: flow.h:305
Port dp
Definition: decode.h:423
Flow * FlowGetExistingFlowFromHash(FlowKey *key, const uint32_t hash)
Look for existing Flow using a FlowKey.
Definition: flow-hash.c:819
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:413
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 Flow_::@121::@125 icmp_s
struct timeval startts
Definition: flow.h:458
#define FLOWLOCK_WRLOCK(fb)
Definition: flow.h:240
struct Packet_::@43::@52 icmp_s
Flow * FlowGetFlowFromHash(ThreadVars *tv, DecodeThreadVars *dtv, const Packet *p, Flow **dest)
Get Flow for packet.
Definition: flow-hash.c:603
uint16_t ports[2]
Definition: flow-hash.c:85
TCPHdr * tcph
Definition: decode.h:522
#define FLOW_END_FLAG_STATE_BYPASSED
Definition: flow.h:216
uint32_t FlowKeyGetHash(FlowKey *fk)
Definition: flow-hash.c:223
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:435
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:682
uint16_t counter_flow_tcp
Definition: decode.h:681
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:502
#define FLOW_END_FLAG_STATE_NEW
Definition: flow.h:209
char family
Definition: decode.h:111
uint8_t proto
Definition: decode.h:430
uint32_t src[4]
Definition: flow-hash.c:97
uint8_t recursion_level
Definition: decode.h:433
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:690
#define FLOW_END_FLAG_STATE_CLOSED
Definition: flow.h:211
void StatsIncr(ThreadVars *tv, uint16_t id)
Increments the local counter.
Definition: counters.c:168
uint32_t dst[4]
Definition: flow-hash.c:97
#define ICMPV4_GET_EMB_IPV4(p)
uint16_t counter_flow_icmp4
Definition: decode.h:683
uint16_t Port
Definition: decode.h:235
uint16_t counter_flow_memcap
Definition: decode.h:679
Flow * FlowAlloc(void)
allocate a flow
Definition: flow-util.c:51
uint16_t g_vlan_mask
Definition: suricata.c:237
struct Flow_::@123::@126 icmp_d
struct timeval lastts
Definition: flow.h:358
struct FlowBucket_ * fb
Definition: flow.h:453
struct Packet_::@45::@53 icmp_d
IPV4Hdr * ip4h
Definition: decode.h:500
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
FlowBucket * flow_hash
Definition: flow-private.h:96
const uint32_t u32[5]
Definition: flow-hash.c:90
Port dp
Definition: flow.h:338
union FlowAddress_::@120 address
Address dst
Definition: flow.h:281
#define FLOW_END_FLAG_EMERGENCY
Definition: flow.h:212
uint32_t address_un_data32[4]
Definition: decode.h:113
uint32_t address_un_data32[4]
Definition: flow.h:290
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:255
uint16_t ports[2]
Definition: flow-hash.c:98
void FlowUpdateState(Flow *f, enum FlowState s)
Definition: flow.c:1104
uint16_t vlan_id[2]
Definition: flow-hash.c:101
uint16_t emb_dport
uint16_t counter_flow_icmp6
Definition: decode.h:684
#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
FlowThreadId thread_id[2]
Definition: flow.h:426
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:1114
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:1030
uint32_t flow_hash
Definition: decode.h:449
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:443
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:746
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:515
#define FBLOCK_LOCK(fb)
Definition: flow-hash.h:68
union Address_::@42 address
Address src
Definition: decode.h:412
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