suricata
util-thash.c
Go to the documentation of this file.
1 /* Copyright (C) 2007-2024 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  *
23  */
24 
25 #include "suricata-common.h"
26 #include "conf.h"
27 
28 #include "util-debug.h"
29 #include "util-thash.h"
30 
31 #include "util-random.h"
32 #include "util-misc.h"
33 #include "util-byte.h"
34 
35 #include "util-hash-lookup3.h"
36 #include "util-validate.h"
37 
38 static THashData *THashGetUsed(THashTableContext *ctx, uint32_t data_size);
39 static void THashDataEnqueue (THashDataQueue *q, THashData *h);
40 
42 {
43  THashDataEnqueue(&ctx->spare_q, h);
44  (void) SC_ATOMIC_SUB(ctx->counter, 1);
45 }
46 
47 static THashDataQueue *THashDataQueueInit (THashDataQueue *q)
48 {
49  if (q != NULL) {
50  memset(q, 0, sizeof(THashDataQueue));
51  HQLOCK_INIT(q);
52  }
53  return q;
54 }
55 
57 {
59  if (q == NULL) {
60  SCLogError("Fatal error encountered in THashDataQueueNew. Exiting...");
61  exit(EXIT_SUCCESS);
62  }
63  q = THashDataQueueInit(q);
64  return q;
65 }
66 
67 /**
68  * \brief Destroy a queue
69  *
70  * \param q the queue to destroy
71  */
72 static void THashDataQueueDestroy (THashDataQueue *q)
73 {
74  HQLOCK_DESTROY(q);
75 }
76 
77 /**
78  * \brief add to queue
79  *
80  * \param q queue
81  * \param h data
82  */
83 static void THashDataEnqueue (THashDataQueue *q, THashData *h)
84 {
85 #ifdef DEBUG
86  BUG_ON(q == NULL || h == NULL);
87 #endif
88 
89  HQLOCK_LOCK(q);
90 
91  /* more data in queue */
92  if (q->top != NULL) {
93  h->next = q->top;
94  q->top->prev = h;
95  q->top = h;
96  /* only data */
97  } else {
98  q->top = h;
99  q->bot = h;
100  }
101  q->len++;
102 #ifdef DBG_PERF
103  if (q->len > q->dbg_maxlen)
104  q->dbg_maxlen = q->len;
105 #endif /* DBG_PERF */
106  HQLOCK_UNLOCK(q);
107 }
108 
109 /**
110  * \brief remove data from the queue
111  *
112  * \param q queue
113  *
114  * \retval h data or NULL if empty list.
115  */
116 static THashData *THashDataDequeue (THashDataQueue *q)
117 {
118  HQLOCK_LOCK(q);
119 
120  THashData *h = q->bot;
121  if (h == NULL) {
122  HQLOCK_UNLOCK(q);
123  return NULL;
124  }
125 
126  /* more packets in queue */
127  if (q->bot->prev != NULL) {
128  q->bot = q->bot->prev;
129  q->bot->next = NULL;
130  /* just the one we remove, so now empty */
131  } else {
132  q->top = NULL;
133  q->bot = NULL;
134  }
135 
136 #ifdef DEBUG
137  BUG_ON(q->len == 0);
138 #endif
139  if (q->len > 0)
140  q->len--;
141 
142  h->next = NULL;
143  h->prev = NULL;
144 
145  HQLOCK_UNLOCK(q);
146  return h;
147 }
148 
149 #if 0
150 static uint32_t THashDataQueueLen(THashDataQueue *q)
151 {
152  uint32_t len;
153  HQLOCK_LOCK(q);
154  len = q->len;
155  HQLOCK_UNLOCK(q);
156  return len;
157 }
158 #endif
159 
160 static THashData *THashDataAlloc(THashTableContext *ctx, uint32_t data_size)
161 {
162  const size_t thash_data_size = THASH_DATA_SIZE(ctx);
163 
164  if (!(THASH_CHECK_MEMCAP(ctx, thash_data_size + data_size))) {
165  return NULL;
166  }
167 
168  size_t total_data_size = thash_data_size + data_size;
169 
170  (void)SC_ATOMIC_ADD(ctx->memuse, total_data_size);
171 
172  THashData *h = SCCalloc(1, thash_data_size);
173  if (unlikely(h == NULL))
174  goto error;
175 
176  /* points to data right after THashData block */
177  h->data = (uint8_t *)h + sizeof(THashData);
178 
179 // memset(h, 0x00, data_size);
180 
181  SCMutexInit(&h->m, NULL);
182  SC_ATOMIC_INIT(h->use_cnt);
183  return h;
184 
185 error:
186  (void)SC_ATOMIC_SUB(ctx->memuse, total_data_size);
187  return NULL;
188 }
189 
190 static void THashDataFree(THashTableContext *ctx, THashData *h)
191 {
192  if (h != NULL) {
193  DEBUG_VALIDATE_BUG_ON(SC_ATOMIC_GET(h->use_cnt) != 0);
194 
195  uint32_t data_size = 0;
196  if (h->data != NULL) {
197  if (ctx->config.DataSize) {
198  data_size = ctx->config.DataSize(h->data);
199  }
200  ctx->config.DataFree(h->data);
201  }
202  SCMutexDestroy(&h->m);
203  SCFree(h);
204  (void)SC_ATOMIC_SUB(ctx->memuse, THASH_DATA_SIZE(ctx) + (uint64_t)data_size);
205  }
206 }
207 
208 #define THASH_DEFAULT_HASHSIZE 4096
209 #define THASH_DEFAULT_MEMCAP 16777216
210 #define THASH_DEFAULT_PREALLOC 1000
211 
212 #define GET_VAR(prefix,name) \
213  snprintf(varname, sizeof(varname), "%s.%s", (prefix), (name))
214 
215 /** \brief initialize the configuration
216  * \warning Not thread safe */
217 static int THashInitConfig(THashTableContext *ctx, const char *cnf_prefix)
218 {
219  char varname[256];
220 
221  SCLogDebug("initializing thash engine...");
222 
223  /* Check if we have memcap and hash_size defined at config */
224  const char *conf_val;
225  uint32_t configval = 0;
226 
227  /** set config values for memcap, prealloc and hash_size */
228  GET_VAR(cnf_prefix, "memcap");
229  if ((SCConfGet(varname, &conf_val)) == 1) {
230  uint64_t memcap;
231  if (ParseSizeStringU64(conf_val, &memcap) < 0) {
232  SCLogError("Error parsing %s "
233  "from conf file - %s. Killing engine",
234  varname, conf_val);
235  return -1;
236  }
237  SC_ATOMIC_INIT(ctx->config.memcap);
238  SC_ATOMIC_SET(ctx->config.memcap, memcap);
239  }
240  GET_VAR(cnf_prefix, "hash-size");
241  if ((SCConfGet(varname, &conf_val)) == 1) {
242  if (StringParseUint32(&configval, 10, (uint16_t)strlen(conf_val), conf_val) > 0) {
243  ctx->config.hash_size = configval;
244  }
245  }
246 
247  GET_VAR(cnf_prefix, "prealloc");
248  if ((SCConfGet(varname, &conf_val)) == 1) {
249  if (StringParseUint32(&configval, 10, (uint16_t)strlen(conf_val), conf_val) > 0) {
250  ctx->config.prealloc = configval;
251  } else {
252  WarnInvalidConfEntry(varname, "%"PRIu32, ctx->config.prealloc);
253  }
254  }
255 
256  /* alloc hash memory */
257  uint64_t hash_size = ctx->config.hash_size * sizeof(THashHashRow);
258  if (!(THASH_CHECK_MEMCAP(ctx, hash_size))) {
259  SCLogError("allocating hash failed: "
260  "max hash memcap is smaller than projected hash size. "
261  "Memcap: %" PRIu64 ", Hash table size %" PRIu64 ". Calculate "
262  "total hash size by multiplying \"hash-size\" with %" PRIuMAX ", "
263  "which is the hash bucket size.",
264  SC_ATOMIC_GET(ctx->config.memcap), hash_size, (uintmax_t)sizeof(THashHashRow));
265  return -1;
266  }
267  ctx->array = SCMallocAligned(ctx->config.hash_size * sizeof(THashHashRow), CLS);
268  if (unlikely(ctx->array == NULL)) {
269  SCLogError("Fatal error encountered in THashInitConfig. Exiting...");
270  return -1;
271  }
272  memset(ctx->array, 0, ctx->config.hash_size * sizeof(THashHashRow));
273 
274  uint32_t i = 0;
275  for (i = 0; i < ctx->config.hash_size; i++) {
276  HRLOCK_INIT(&ctx->array[i]);
277  }
278  (void)SC_ATOMIC_ADD(ctx->memuse, (ctx->config.hash_size * sizeof(THashHashRow)));
279 
280  /* pre allocate prealloc */
281  for (i = 0; i < ctx->config.prealloc; i++) {
283  SCLogError("preallocating data failed: "
284  "max thash memcap reached. Memcap %" PRIu64 ", "
285  "Memuse %" PRIu64 ".",
286  SC_ATOMIC_GET(ctx->config.memcap),
287  ((uint64_t)SC_ATOMIC_GET(ctx->memuse) + THASH_DATA_SIZE(ctx)));
288  return -1;
289  }
290 
291  THashData *h = THashDataAlloc(ctx, 0 /* as we don't have string data here */);
292  if (h == NULL) {
293  SCLogError("preallocating data failed: %s", strerror(errno));
294  return -1;
295  }
296  THashDataEnqueue(&ctx->spare_q,h);
297  }
298 
299  return 0;
300 }
301 
302 THashTableContext *THashInit(const char *cnf_prefix, uint32_t data_size,
303  int (*DataSet)(void *, void *), void (*DataFree)(void *),
304  uint32_t (*DataHash)(uint32_t, void *), bool (*DataCompare)(void *, void *),
305  bool (*DataExpired)(void *, SCTime_t), uint32_t (*DataSize)(void *), bool reset_memcap,
306  uint64_t memcap, uint32_t hashsize)
307 {
308  THashTableContext *ctx = SCCalloc(1, sizeof(*ctx));
309  BUG_ON(!ctx);
310 
311  ctx->config.data_size = data_size;
312  ctx->config.DataSet = DataSet;
313  ctx->config.DataFree = DataFree;
314  ctx->config.DataHash = DataHash;
315  ctx->config.DataCompare = DataCompare;
316  ctx->config.DataExpired = DataExpired;
317  ctx->config.DataSize = DataSize;
318 
319  /* set defaults */
320  ctx->config.hash_rand = (uint32_t)RandomGet();
321  ctx->config.hash_size = hashsize > 0 ? hashsize : THASH_DEFAULT_HASHSIZE;
322  /* Reset memcap in case of loading from file to the highest possible value
323  unless defined by the rule keyword */
324  if (memcap > 0) {
325  SC_ATOMIC_SET(ctx->config.memcap, memcap);
326  } else {
327  SC_ATOMIC_SET(ctx->config.memcap, reset_memcap ? UINT64_MAX : THASH_DEFAULT_MEMCAP);
328  }
329  ctx->config.prealloc = THASH_DEFAULT_PREALLOC;
330 
331  SC_ATOMIC_INIT(ctx->counter);
332  SC_ATOMIC_INIT(ctx->memuse);
333  SC_ATOMIC_INIT(ctx->prune_idx);
334  THashDataQueueInit(&ctx->spare_q);
335 
336  if (THashInitConfig(ctx, cnf_prefix) < 0) {
338  ctx = NULL;
339  }
340  return ctx;
341 }
342 
343 /* \brief Set memcap to current memuse
344  * */
346 {
348  ctx->config.memcap, MAX(SC_ATOMIC_GET(ctx->memuse), SC_ATOMIC_GET(ctx->config.memcap)));
349  SCLogDebug("memcap after load set to: %" PRIu64, SC_ATOMIC_GET(ctx->config.memcap));
350 }
351 
352 /** \brief shutdown the flow engine
353  * \warning Not thread safe */
355 {
356  THashData *h;
357 
358  /* free spare queue */
359  while ((h = THashDataDequeue(&ctx->spare_q))) {
360  BUG_ON(SC_ATOMIC_GET(h->use_cnt) > 0);
361  THashDataFree(ctx, h);
362  }
363 
364  /* clear and free the hash */
365  if (ctx->array != NULL) {
366  for (uint32_t u = 0; u < ctx->config.hash_size; u++) {
367  h = ctx->array[u].head;
368  while (h) {
369  THashData *n = h->next;
370  THashDataFree(ctx, h);
371  h = n;
372  }
373 
374  HRLOCK_DESTROY(&ctx->array[u]);
375  }
376  SCFreeAligned(ctx->array);
377  ctx->array = NULL;
378  (void)SC_ATOMIC_SUB(ctx->memuse, ctx->config.hash_size * sizeof(THashHashRow));
379  }
380  THashDataQueueDestroy(&ctx->spare_q);
381  DEBUG_VALIDATE_BUG_ON(SC_ATOMIC_GET(ctx->memuse) != 0);
382  SCFree(ctx);
383 }
384 
385 /** \brief Walk the hash
386  *
387  */
388 int THashWalk(THashTableContext *ctx, THashFormatFunc FormatterFunc, THashOutputFunc OutputterFunc, void *output_ctx)
389 {
390  uint32_t u;
391 
392  if (ctx->array == NULL)
393  return -1;
394 
395  bool err = false;
396  for (u = 0; u < ctx->config.hash_size; u++) {
397  THashHashRow *hb = &ctx->array[u];
398  HRLOCK_LOCK(hb);
399  THashData *h = hb->head;
400  while (h) {
401  char output_string[1024] = "";
402  int size = FormatterFunc(h->data, output_string, sizeof(output_string));
403  if (size > 0) {
404  if (OutputterFunc(output_ctx, (const uint8_t *)output_string, size) < 0) {
405  err = true;
406  break;
407  }
408  }
409  h = h->next;
410  }
411  HRLOCK_UNLOCK(hb);
412  if (err)
413  return -1;
414  }
415  return 0;
416 }
417 
418 /** \brief expire data from the hash
419  * Walk the hash table and remove data that is exprired according to the
420  * DataExpired callback.
421  * \retval cnt number of items successfully expired/removed
422  */
424 {
425  if (ctx->config.DataExpired == NULL)
426  return 0;
427 
428  SCLogDebug("timeout: starting");
429  uint32_t cnt = 0;
430 
431  for (uint32_t i = 0; i < ctx->config.hash_size; i++) {
432  THashHashRow *hb = &ctx->array[i];
433  if (HRLOCK_TRYLOCK(hb) != 0)
434  continue;
435  /* hash bucket is now locked */
436  THashData *h = hb->head;
437  while (h) {
438  THashData *next = h->next;
439  THashDataLock(h);
440  DEBUG_VALIDATE_BUG_ON(SC_ATOMIC_GET(h->use_cnt) > (uint32_t)INT_MAX);
441  /* only consider items with no references to it */
442  if (SC_ATOMIC_GET(h->use_cnt) == 0 && ctx->config.DataExpired(h->data, ts)) {
443  /* remove from the hash */
444  if (h->prev != NULL)
445  h->prev->next = h->next;
446  if (h->next != NULL)
447  h->next->prev = h->prev;
448  if (hb->head == h)
449  hb->head = h->next;
450  if (hb->tail == h)
451  hb->tail = h->prev;
452  h->next = NULL;
453  h->prev = NULL;
454  SCLogDebug("timeout: removing data %p", h);
455  if (ctx->config.DataSize) {
456  uint32_t data_size = ctx->config.DataSize(h->data);
457  if (data_size > 0)
458  (void)SC_ATOMIC_SUB(ctx->memuse, (uint64_t)data_size);
459  }
460  ctx->config.DataFree(h->data);
461  THashDataUnlock(h);
463  cnt++;
464  } else {
465  THashDataUnlock(h);
466  }
467  h = next;
468  }
469  HRLOCK_UNLOCK(hb);
470  }
471 
472  SCLogDebug("timeout: ending: %u entries expired", cnt);
473  return cnt;
474 }
475 
476 /** \brief Cleanup the thash engine
477  *
478  * Cleanup the thash engine from tag and threshold.
479  *
480  */
482 {
483  uint32_t u;
484 
485  if (ctx->array == NULL)
486  return;
487 
488  for (u = 0; u < ctx->config.hash_size; u++) {
489  THashHashRow *hb = &ctx->array[u];
490  HRLOCK_LOCK(hb);
491  THashData *h = hb->head;
492  while (h) {
493  if ((SC_ATOMIC_GET(h->use_cnt) > 0)) {
494  h = h->next;
495  } else {
496  THashData *n = h->next;
497  /* remove from the hash */
498  if (h->prev != NULL)
499  h->prev->next = h->next;
500  if (h->next != NULL)
501  h->next->prev = h->prev;
502  if (hb->head == h)
503  hb->head = h->next;
504  if (hb->tail == h)
505  hb->tail = h->prev;
506  h->next = NULL;
507  h->prev = NULL;
508  if (ctx->config.DataSize) {
509  uint32_t data_size = ctx->config.DataSize(h->data);
510  if (data_size > 0)
511  (void)SC_ATOMIC_SUB(ctx->memuse, (uint64_t)data_size);
512  }
514  h = n;
515  }
516  }
517  HRLOCK_UNLOCK(hb);
518  }
519 }
520 
521 /* calculate the hash key for this packet
522  *
523  * we're using:
524  * hash_rand -- set at init time
525  * source address
526  */
527 static uint32_t THashGetKey(const THashConfig *cnf, void *data)
528 {
529  uint32_t key;
530 
531  key = cnf->DataHash(cnf->hash_rand, data);
532  key %= cnf->hash_size;
533 
534  return key;
535 }
536 
537 static inline int THashCompare(const THashConfig *cnf, void *a, void *b)
538 {
539  if (cnf->DataCompare(a, b))
540  return 1;
541  return 0;
542 }
543 
544 /**
545  * \brief Get new data
546  *
547  * Get new data. We're checking memcap first and will try to make room
548  * if the memcap is reached.
549  *
550  * \retval h *LOCKED* data on succes, NULL on error.
551  */
552 static THashData *THashDataGetNew(THashTableContext *ctx, void *data)
553 {
554  THashData *h = NULL;
555  uint32_t data_size = 0;
556  if (ctx->config.DataSize) {
557  data_size = ctx->config.DataSize(data);
558  }
559 
560  /* get data from the spare queue */
561  h = THashDataDequeue(&ctx->spare_q);
562  if (h == NULL) {
563  /* If we reached the max memcap, we get used data */
564  if (!(THASH_CHECK_MEMCAP(ctx, THASH_DATA_SIZE(ctx) + data_size))) {
565  h = THashGetUsed(ctx, data_size);
566  if (h == NULL) {
567  return NULL;
568  }
569 
570  if (!SC_ATOMIC_GET(ctx->memcap_reached)) {
571  SC_ATOMIC_SET(ctx->memcap_reached, true);
572  }
573 
574  /* freed data, but it's unlocked */
575  } else {
576  /* now see if we can alloc a new data */
577  h = THashDataAlloc(ctx, data_size);
578  if (h == NULL) {
579  return NULL;
580  }
581 
582  /* data is initialized but *unlocked* */
583  }
584  } else {
585  /* data has been recycled before it went into the spare queue */
586  /* data is initialized (recycled) but *unlocked* */
587  /* the recycled data was THashData and again does not include
588  * the size of current data to be added */
589  if (data_size > 0) {
590  /* Since it is prealloc'd data, it already has THashData in its memuse */
591  (void)SC_ATOMIC_ADD(ctx->memuse, data_size);
592  if (!(THASH_CHECK_MEMCAP(ctx, data_size))) {
593  if (!SC_ATOMIC_GET(ctx->memcap_reached)) {
594  SC_ATOMIC_SET(ctx->memcap_reached, true);
595  }
596  SCLogError("Adding data will exceed memcap: %" PRIu64 ", current memuse: %" PRIu64,
597  SC_ATOMIC_GET((ctx)->config.memcap), SC_ATOMIC_GET(ctx->memuse));
598  }
599  }
600  }
601 
602  // setup the data
603  BUG_ON(ctx->config.DataSet(h->data, data) != 0);
604  (void) SC_ATOMIC_ADD(ctx->counter, 1);
605  SCMutexLock(&h->m);
606  return h;
607 }
608 
609 /*
610  * returns a *LOCKED* data or NULL
611  */
612 
613 struct THashDataGetResult
615 {
616  struct THashDataGetResult res = { .data = NULL, .is_new = false, };
617  THashData *h = NULL;
618 
619  /* get the key to our bucket */
620  uint32_t key = THashGetKey(&ctx->config, data);
621  /* get our hash bucket and lock it */
622  THashHashRow *hb = &ctx->array[key];
623  HRLOCK_LOCK(hb);
624 
625  /* see if the bucket already has data */
626  if (hb->head == NULL) {
627  h = THashDataGetNew(ctx, data);
628  if (h == NULL) {
629  HRLOCK_UNLOCK(hb);
630  return res;
631  }
632 
633  /* data is locked */
634  hb->head = h;
635  hb->tail = h;
636 
637  /* initialize and return */
638  (void) THashIncrUsecnt(h);
639 
640  HRLOCK_UNLOCK(hb);
641  res.data = h;
642  res.is_new = true;
643  return res;
644  }
645 
646  /* ok, we have data in the bucket. Let's find out if it is our data */
647  h = hb->head;
648 
649  /* see if this is the data we are looking for */
650  if (THashCompare(&ctx->config, h->data, data) == 0) {
651  THashData *ph = NULL; /* previous data */
652 
653  while (h) {
654  ph = h;
655  h = h->next;
656 
657  if (h == NULL) {
658  h = ph->next = THashDataGetNew(ctx, data);
659  if (h == NULL) {
660  HRLOCK_UNLOCK(hb);
661  return res;
662  }
663  hb->tail = h;
664 
665  /* data is locked */
666 
667  h->prev = ph;
668 
669  /* initialize and return */
670  (void) THashIncrUsecnt(h);
671 
672  HRLOCK_UNLOCK(hb);
673  res.data = h;
674  res.is_new = true;
675  return res;
676  }
677 
678  if (THashCompare(&ctx->config, h->data, data) != 0) {
679  /* we found our data, lets put it on top of the
680  * hash list -- this rewards active data */
681  if (h->next) {
682  h->next->prev = h->prev;
683  }
684  if (h->prev) {
685  h->prev->next = h->next;
686  }
687  if (h == hb->tail) {
688  hb->tail = h->prev;
689  }
690 
691  h->next = hb->head;
692  h->prev = NULL;
693  hb->head->prev = h;
694  hb->head = h;
695 
696  /* found our data, lock & return */
697  SCMutexLock(&h->m);
698  (void) THashIncrUsecnt(h);
699  HRLOCK_UNLOCK(hb);
700  res.data = h;
701  res.is_new = false;
702  /* coverity[missing_unlock : FALSE] */
703  return res;
704  }
705  }
706  }
707 
708  /* lock & return */
709  SCMutexLock(&h->m);
710  (void) THashIncrUsecnt(h);
711  HRLOCK_UNLOCK(hb);
712  res.data = h;
713  res.is_new = false;
714  /* coverity[missing_unlock : FALSE] */
715  return res;
716 }
717 
718 /** \brief look up data in the hash
719  *
720  * \param data data to look up
721  *
722  * \retval h *LOCKED* data or NULL
723  */
725 {
726  THashData *h = NULL;
727 
728  /* get the key to our bucket */
729  uint32_t key = THashGetKey(&ctx->config, data);
730  /* get our hash bucket and lock it */
731  THashHashRow *hb = &ctx->array[key];
732  HRLOCK_LOCK(hb);
733 
734  if (hb->head == NULL) {
735  HRLOCK_UNLOCK(hb);
736  return h;
737  }
738 
739  /* ok, we have data in the bucket. Let's find out if it is our data */
740  h = hb->head;
741 
742  /* see if this is the data we are looking for */
743  if (THashCompare(&ctx->config, h->data, data) == 0) {
744  while (h) {
745  h = h->next;
746  if (h == NULL) {
747  HRLOCK_UNLOCK(hb);
748  return h;
749  }
750 
751  if (THashCompare(&ctx->config, h->data, data) != 0) {
752  /* we found our data, lets put it on top of the
753  * hash list -- this rewards active data */
754  if (h->next) {
755  h->next->prev = h->prev;
756  }
757  if (h->prev) {
758  h->prev->next = h->next;
759  }
760  if (h == hb->tail) {
761  hb->tail = h->prev;
762  }
763 
764  h->next = hb->head;
765  h->prev = NULL;
766  hb->head->prev = h;
767  hb->head = h;
768 
769  /* found our data, lock & return */
770  SCMutexLock(&h->m);
771  (void) THashIncrUsecnt(h);
772  HRLOCK_UNLOCK(hb);
773  return h;
774  }
775  }
776  }
777 
778  /* lock & return */
779  SCMutexLock(&h->m);
780  (void) THashIncrUsecnt(h);
781  HRLOCK_UNLOCK(hb);
782  return h;
783 }
784 
785 /** \internal
786  * \brief Get data from the hash directly.
787  *
788  * Called in conditions where the spare queue is empty and memcap is
789  * reached.
790  *
791  * Walks the hash until data can be freed. "prune_idx" atomic int makes
792  * sure we don't start at the top each time since that would clear the top
793  * of the hash leading to longer and longer search times under high
794  * pressure (observed).
795  *
796  * \retval h data or NULL
797  */
798 static THashData *THashGetUsed(THashTableContext *ctx, uint32_t data_size)
799 {
800  uint32_t idx = SC_ATOMIC_GET(ctx->prune_idx) % ctx->config.hash_size;
801  uint32_t cnt = ctx->config.hash_size;
802 
803  while (cnt--) {
804  if (++idx >= ctx->config.hash_size)
805  idx = 0;
806 
807  THashHashRow *hb = &ctx->array[idx];
808 
809  if (HRLOCK_TRYLOCK(hb) != 0)
810  continue;
811 
812  THashData *h = hb->tail;
813  if (h == NULL) {
814  HRLOCK_UNLOCK(hb);
815  continue;
816  }
817 
818  if (SCMutexTrylock(&h->m) != 0) {
819  HRLOCK_UNLOCK(hb);
820  continue;
821  }
822 
823  if (SC_ATOMIC_GET(h->use_cnt) > 0) {
824  HRLOCK_UNLOCK(hb);
825  SCMutexUnlock(&h->m);
826  continue;
827  }
828 
829  /* remove from the hash */
830  if (h->prev != NULL)
831  h->prev->next = h->next;
832  if (h->next != NULL)
833  h->next->prev = h->prev;
834  if (hb->head == h)
835  hb->head = h->next;
836  if (hb->tail == h)
837  hb->tail = h->prev;
838 
839  h->next = NULL;
840  h->prev = NULL;
841  HRLOCK_UNLOCK(hb);
842 
843  if (h->data != NULL) {
844  if (ctx->config.DataSize) {
845  uint32_t h_data_size = ctx->config.DataSize(h->data);
846  if (h_data_size > 0) {
847  (void)SC_ATOMIC_SUB(ctx->memuse, (uint64_t)h_data_size);
848  }
849  }
850  ctx->config.DataFree(h->data);
851  }
852  SCMutexUnlock(&h->m);
853 
854  (void) SC_ATOMIC_ADD(ctx->prune_idx, (ctx->config.hash_size - cnt));
855  if (data_size > 0)
856  (void)SC_ATOMIC_ADD(ctx->memuse, data_size);
857  return h;
858  }
859 
860  return NULL;
861 }
862 
863 /**
864  * \retval int -1 not found
865  * \retval int 0 found, but it was busy (ref cnt)
866  * \retval int 1 found and removed */
868 {
869  /* get the key to our bucket */
870  uint32_t key = THashGetKey(&ctx->config, data);
871  /* get our hash bucket and lock it */
872  THashHashRow *hb = &ctx->array[key];
873 
874  HRLOCK_LOCK(hb);
875  THashData *h = hb->head;
876  while (h != NULL) {
877  /* see if this is the data we are looking for */
878  if (THashCompare(&ctx->config, h->data, data) == 0) {
879  h = h->next;
880  continue;
881  }
882 
883  SCMutexLock(&h->m);
884  if (SC_ATOMIC_GET(h->use_cnt) > 0) {
885  SCMutexUnlock(&h->m);
886  HRLOCK_UNLOCK(hb);
887  return 0;
888  }
889 
890  /* remove from the hash */
891  if (h->prev != NULL)
892  h->prev->next = h->next;
893  if (h->next != NULL)
894  h->next->prev = h->prev;
895  if (hb->head == h)
896  hb->head = h->next;
897  if (hb->tail == h)
898  hb->tail = h->prev;
899 
900  h->next = NULL;
901  h->prev = NULL;
902  SCMutexUnlock(&h->m);
903  HRLOCK_UNLOCK(hb);
904  THashDataFree(ctx, h);
905  SCLogDebug("found and removed");
906  return 1;
907  }
908 
909  HRLOCK_UNLOCK(hb);
910  SCLogDebug("data not found");
911  return -1;
912 }
HRLOCK_DESTROY
#define HRLOCK_DESTROY(fb)
Definition: host.h:50
util-byte.h
HQLOCK_LOCK
#define HQLOCK_LOCK(q)
Definition: host-queue.h:67
len
uint8_t len
Definition: app-layer-dnp3.h:2
ts
uint64_t ts
Definition: source-erf-file.c:55
THashCleanup
void THashCleanup(THashTableContext *ctx)
Cleanup the thash engine.
Definition: util-thash.c:481
THashDataGetResult::data
THashData * data
Definition: util-thash.h:192
SC_ATOMIC_INIT
#define SC_ATOMIC_INIT(name)
wrapper for initializing an atomic variable.
Definition: util-atomic.h:314
CLS
#define CLS
Definition: suricata-common.h:61
unlikely
#define unlikely(expr)
Definition: util-optimize.h:35
SC_ATOMIC_SET
#define SC_ATOMIC_SET(name, val)
Set the value for the atomic variable.
Definition: util-atomic.h:386
HQLOCK_DESTROY
#define HQLOCK_DESTROY(q)
Definition: host-queue.h:66
THashOutputFunc
int(* THashOutputFunc)(void *output_ctx, const uint8_t *data, const uint32_t data_len)
Definition: util-thash.h:121
SCLogDebug
#define SCLogDebug(...)
Definition: util-debug.h:269
ParseSizeStringU64
int ParseSizeStringU64(const char *size, uint64_t *res)
Definition: util-misc.c:190
next
struct HtpBodyChunk_ * next
Definition: app-layer-htp.h:0
THashData_::prev
struct THashData_ * prev
Definition: util-thash.h:95
THashRemoveFromHash
int THashRemoveFromHash(THashTableContext *ctx, void *data)
Definition: util-thash.c:867
ctx
struct Thresholds ctx
SC_ATOMIC_ADD
#define SC_ATOMIC_ADD(name, val)
add a value to our atomic variable
Definition: util-atomic.h:332
SCConfGet
int SCConfGet(const char *name, const char **vptr)
Retrieve the value of a configuration node.
Definition: conf.c:350
THashData_::next
struct THashData_ * next
Definition: util-thash.h:94
THashConsolidateMemcap
void THashConsolidateMemcap(THashTableContext *ctx)
Definition: util-thash.c:345
SCMutexLock
#define SCMutexLock(mut)
Definition: threads-debug.h:117
THashDataQueue_
Definition: util-thash.h:105
RandomGet
long int RandomGet(void)
Definition: util-random.c:130
THashDataConfig_::DataCompare
bool(* DataCompare)(void *, void *)
Definition: util-thash.h:134
MAX
#define MAX(x, y)
Definition: suricata-common.h:404
HRLOCK_LOCK
#define HRLOCK_LOCK(fb)
Definition: host.h:51
HRLOCK_UNLOCK
#define HRLOCK_UNLOCK(fb)
Definition: host.h:53
THashDataConfig_::hash_size
uint32_t hash_size
Definition: util-thash.h:127
util-debug.h
THASH_DEFAULT_HASHSIZE
#define THASH_DEFAULT_HASHSIZE
Definition: util-thash.c:208
SCMutexUnlock
#define SCMutexUnlock(mut)
Definition: threads-debug.h:119
THashTableContext_
Definition: util-thash.h:141
THASH_DATA_SIZE
#define THASH_DATA_SIZE(ctx)
Definition: util-thash.h:139
THashDataQueue_::bot
THashData * bot
Definition: util-thash.h:107
StringParseUint32
int StringParseUint32(uint32_t *res, int base, size_t len, const char *str)
Definition: util-byte.c:313
THashData_::m
SCMutex m
Definition: util-thash.h:87
BUG_ON
#define BUG_ON(x)
Definition: suricata-common.h:309
SC_ATOMIC_SUB
#define SC_ATOMIC_SUB(name, val)
sub a value from our atomic variable
Definition: util-atomic.h:341
THashDataGetResult
Definition: util-thash.h:191
SCFreeAligned
#define SCFreeAligned(p)
Definition: util-mem.h:77
GET_VAR
#define GET_VAR(prefix, name)
Definition: util-thash.c:212
conf.h
SCTime_t
Definition: util-time.h:40
HRLOCK_INIT
#define HRLOCK_INIT(fb)
Definition: host.h:49
THashDataMoveToSpare
void THashDataMoveToSpare(THashTableContext *ctx, THashData *h)
Definition: util-thash.c:41
SCMutexInit
#define SCMutexInit(mut, mutattrs)
Definition: threads-debug.h:116
WarnInvalidConfEntry
#define WarnInvalidConfEntry(param_name, format, value)
Generic API that can be used by all to log an invalid conf entry.
Definition: util-misc.h:35
THashShutdown
void THashShutdown(THashTableContext *ctx)
shutdown the flow engine
Definition: util-thash.c:354
HQLOCK_UNLOCK
#define HQLOCK_UNLOCK(q)
Definition: host-queue.h:69
THashData_::data
void * data
Definition: util-thash.h:92
cnt
uint32_t cnt
Definition: tmqh-packetpool.h:7
THashData_
Definition: util-thash.h:85
THashDataQueue_::len
uint32_t len
Definition: util-thash.h:108
suricata-common.h
THASH_DEFAULT_MEMCAP
#define THASH_DEFAULT_MEMCAP
Definition: util-thash.c:209
SCMallocAligned
#define SCMallocAligned(size, align)
Definition: util-mem.h:68
HQLOCK_INIT
#define HQLOCK_INIT(q)
Definition: host-queue.h:65
THashGetFromHash
struct THashDataGetResult THashGetFromHash(THashTableContext *ctx, void *data)
Definition: util-thash.c:614
hashsize
#define hashsize(n)
Definition: util-hash-lookup3.h:40
THashLookupFromHash
THashData * THashLookupFromHash(THashTableContext *ctx, void *data)
look up data in the hash
Definition: util-thash.c:724
util-hash-lookup3.h
THASH_DEFAULT_PREALLOC
#define THASH_DEFAULT_PREALLOC
Definition: util-thash.c:210
util-validate.h
SCMalloc
#define SCMalloc(sz)
Definition: util-mem.h:47
THashDataConfig_
Definition: util-thash.h:124
SCLogError
#define SCLogError(...)
Macro used to log ERROR messages.
Definition: util-debug.h:261
THashWalk
int THashWalk(THashTableContext *ctx, THashFormatFunc FormatterFunc, THashOutputFunc OutputterFunc, void *output_ctx)
Walk the hash.
Definition: util-thash.c:388
SCFree
#define SCFree(p)
Definition: util-mem.h:61
THashFormatFunc
int(* THashFormatFunc)(const void *in_data, char *output, size_t output_size)
Definition: util-thash.h:122
THashDataConfig_::DataHash
uint32_t(* DataHash)(uint32_t, void *)
Definition: util-thash.h:133
util-random.h
HRLOCK_TRYLOCK
#define HRLOCK_TRYLOCK(fb)
Definition: host.h:52
THashDataGetResult::is_new
bool is_new
Definition: util-thash.h:193
THashInit
THashTableContext * THashInit(const char *cnf_prefix, uint32_t data_size, int(*DataSet)(void *, void *), void(*DataFree)(void *), uint32_t(*DataHash)(uint32_t, void *), bool(*DataCompare)(void *, void *), bool(*DataExpired)(void *, SCTime_t), uint32_t(*DataSize)(void *), bool reset_memcap, uint64_t memcap, uint32_t hashsize)
Definition: util-thash.c:302
THashDataConfig_::hash_rand
uint32_t hash_rand
Definition: util-thash.h:126
THashExpire
uint32_t THashExpire(THashTableContext *ctx, const SCTime_t ts)
expire data from the hash Walk the hash table and remove data that is exprired according to the DataE...
Definition: util-thash.c:423
THashIncrUsecnt
#define THashIncrUsecnt(h)
Definition: util-thash.h:168
SC_ATOMIC_GET
#define SC_ATOMIC_GET(name)
Get the value from the atomic variable.
Definition: util-atomic.h:375
util-misc.h
util-thash.h
SCCalloc
#define SCCalloc(nm, sz)
Definition: util-mem.h:53
SCMutexDestroy
#define SCMutexDestroy
Definition: threads-debug.h:120
THASH_CHECK_MEMCAP
#define THASH_CHECK_MEMCAP(ctx, size)
check if a memory alloc would fit in the memcap
Definition: util-thash.h:164
DEBUG_VALIDATE_BUG_ON
#define DEBUG_VALIDATE_BUG_ON(exp)
Definition: util-validate.h:102
THashDataQueueNew
THashDataQueue * THashDataQueueNew(void)
Definition: util-thash.c:56
SCMutexTrylock
#define SCMutexTrylock(mut)
Definition: threads-debug.h:118
THashDataQueue_::top
THashData * top
Definition: util-thash.h:106