suricata
util-rohash.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  * Chained read only hash table implementation, meaning that
24  * after the initial fill no changes are allowed.
25  *
26  * Loading takes 2 stages.
27  * - stage1 maps data
28  * - stage2 fills blob
29  *
30  * \todo a bloomfilter in the ROHashTableOffsets could possibly prevent
31  * a lot of cache misses when validating a potential match
32  *
33  * \todo maybe add a user ctx to be returned instead, something like a
34  * 4/8 byte ptr or simply a flag
35  */
36 
37 #include "suricata-common.h"
38 #include "util-hash.h"
39 #include "util-unittest.h"
40 #include "util-memcmp.h"
41 #include "util-hash-lookup3.h"
42 #include "util-rohash.h"
43 #include "util-debug.h"
44 
45 /** item_size data beyond this header */
46 typedef struct ROHashTableItem_ {
47  uint32_t pos; /**< position relative to other values with same hash */
50 
51 /** offset table */
52 typedef struct ROHashTableOffsets_ {
53  uint32_t cnt; /**< number of items for this hash */
54  uint32_t offset; /**< position in the blob of the first item */
56 
57 /** \brief initialize a new rohash
58  *
59  * \param hash_bits hash size as 2^hash_bits, so power of 2, max 31
60  * \param item_size size of the data to store
61  *
62  * \retval table ptr or NULL on error
63  */
64 ROHashTable *ROHashInit(uint8_t hash_bits, uint16_t item_size)
65 {
66  if (item_size % 4 != 0 || item_size == 0) {
67  SCLogError("data size must be multiple of 4");
68  return NULL;
69  }
70  if (hash_bits < 4 || hash_bits > 31) {
71  SCLogError("invalid hash_bits setting, valid range is 4-31");
72  return NULL;
73  }
74 
75  uint32_t size = hashsize(hash_bits) * sizeof(ROHashTableOffsets);
76 
77  ROHashTable *table = SCCalloc(1, sizeof(ROHashTable) + size);
78  if (unlikely(table == NULL)) {
79  SCLogError("failed to alloc memory");
80  return NULL;
81  }
82 
83  table->items = 0;
84  table->item_size = item_size;
85  table->hash_bits = hash_bits;
86  TAILQ_INIT(&table->head);
87 
88  return table;
89 }
90 
91 void ROHashFree(ROHashTable *table)
92 {
93  if (table != NULL) {
94  if (table->data != NULL) {
95  SCFree(table->data);
96  }
97 
98  SCFree(table);
99  }
100 }
101 
103 {
104  uint32_t r1 = hashsize(table->hash_bits) * sizeof(ROHashTableOffsets);
105  uint32_t r2 = table->items * table->item_size;
106  return (uint32_t)(r1 + r2 + sizeof(ROHashTable));
107 }
108 
109 /**
110  * \retval NULL not found
111  * \retval ptr found
112  */
113 void *ROHashLookup(ROHashTable *table, void *data, uint16_t size)
114 {
115  if (data == NULL || size != table->item_size) {
116  SCReturnPtr(NULL, "void");
117  }
118 
119  const uint32_t hash = hashword(data, table->item_size / 4, 0) & hashmask(table->hash_bits);
120 
121  /* get offsets start */
122  const ROHashTableOffsets *os = (ROHashTableOffsets *)((uint8_t *)table + sizeof(ROHashTable));
123  const ROHashTableOffsets *o = &os[hash];
124 
125  /* no matches */
126  if (o->cnt == 0) {
127  SCReturnPtr(NULL, "void");
128  }
129 
130  for (uint32_t u = 0; u < o->cnt; u++) {
131  uint32_t offset = (o->offset + u) * table->item_size;
132 
133  if (SCMemcmp(table->data + offset, data, table->item_size) == 0) {
134  SCReturnPtr(table->data + offset, "void");
135  }
136  }
137  SCReturnPtr(NULL, "void");
138 }
139 
140 /** \brief Add a new value to the hash
141  *
142  * \note can only be done when table isn't in a locked state yet
143  *
144  * \param table the hash table
145  * \param value value to add
146  * \param size value size. *MUST* match table item_size
147  *
148  * \retval 0 error
149  * \retval 1 ok
150  */
151 int ROHashInitQueueValue(ROHashTable *table, void *value, uint16_t size)
152 {
153  if (table->locked) {
154  SCLogError("can't add value to locked table");
155  return 0;
156  }
157  if (table->item_size != size) {
158  SCLogError("wrong size for data %u != %u", size, table->item_size);
159  return 0;
160  }
161 
162  ROHashTableItem *item = SCCalloc(1, sizeof(ROHashTableItem) + table->item_size);
163  if (item != NULL) {
164  memcpy((void *)item + sizeof(ROHashTableItem), value, table->item_size);
165  TAILQ_INSERT_TAIL(&table->head, item, next);
166  return 1;
167  }
168 
169  return 0;
170 }
171 
172 /** \brief create final hash data structure
173  *
174  * \param table the hash table
175  *
176  * \retval 0 error
177  * \retval 1 ok
178  *
179  * \note after this call the nothing can be added to the hash anymore.
180  */
182 {
183  if (table->locked) {
184  SCLogError("table already locked");
185  return 0;
186  }
187 
188  ROHashTableItem *item = NULL;
189  ROHashTableOffsets *os = (ROHashTableOffsets *)((uint8_t *)table + sizeof(ROHashTable));
190 
191  /* count items per hash value */
192  TAILQ_FOREACH(item, &table->head, next) {
193  uint32_t hash =
194  hashword((uint32_t *)((uint8_t *)item + sizeof(*item)), table->item_size / 4, 0) &
195  hashmask(table->hash_bits);
196  ROHashTableOffsets *o = &os[hash];
197 
198  item->pos = o->cnt;
199  o->cnt++;
200  table->items++;
201  }
202 
203  if (table->items == 0) {
204  SCLogError("no items");
205  return 0;
206  }
207 
208  /* get the data block */
209  uint32_t newsize = table->items * table->item_size;
210  table->data = SCCalloc(1, newsize);
211  if (table->data == NULL) {
212  SCLogError("failed to alloc memory");
213  return 0;
214  }
215 
216  /* calc offsets into the block per hash value */
217  uint32_t total = 0;
218  for (uint32_t x = 0; x < hashsize(table->hash_bits); x++) {
219  ROHashTableOffsets *o = &os[x];
220 
221  if (o->cnt == 0)
222  continue;
223 
224  o->offset = total;
225  total += o->cnt;
226  }
227 
228  /* copy each value into the data block */
229  TAILQ_FOREACH(item, &table->head, next) {
230  uint32_t hash =
231  hashword((uint32_t *)((uint8_t *)item + sizeof(*item)), table->item_size / 4, 0) &
232  hashmask(table->hash_bits);
233 
234  ROHashTableOffsets *o = &os[hash];
235  uint32_t offset = (o->offset + item->pos) * table->item_size;
236 
237  memcpy(table->data + offset, (uint8_t *)item + sizeof(*item), table->item_size);
238  }
239 
240  /* clean up temp items */
241  while ((item = TAILQ_FIRST(&table->head))) {
242  TAILQ_REMOVE(&table->head, item, next);
243  SCFree(item);
244  }
245 
246  table->locked = 1;
247  return 1;
248 }
ROHashTable_::data
void * data
Definition: util-rohash.h:32
hashword
uint32_t hashword(const uint32_t *k, size_t length, uint32_t initval)
Definition: util-hash-lookup3.c:172
offset
uint64_t offset
Definition: util-streaming-buffer.h:0
TAILQ_INIT
#define TAILQ_INIT(head)
Definition: queue.h:262
ROHashTableOffsets
struct ROHashTableOffsets_ ROHashTableOffsets
unlikely
#define unlikely(expr)
Definition: util-optimize.h:35
ROHashTableOffsets_
Definition: util-rohash.c:52
ROHashTableOffsets_::offset
uint32_t offset
Definition: util-rohash.c:54
next
struct HtpBodyChunk_ * next
Definition: app-layer-htp.h:0
util-hash.h
TAILQ_FOREACH
#define TAILQ_FOREACH(var, head, field)
Definition: queue.h:252
ROHashTable_
Definition: util-rohash.h:27
TAILQ_INSERT_TAIL
#define TAILQ_INSERT_TAIL(head, elm, field)
Definition: queue.h:294
util-unittest.h
util-rohash.h
TAILQ_ENTRY
#define TAILQ_ENTRY(type)
Definition: queue.h:239
util-memcmp.h
ROHashInitFinalize
int ROHashInitFinalize(ROHashTable *table)
create final hash data structure
Definition: util-rohash.c:181
TAILQ_REMOVE
#define TAILQ_REMOVE(head, elm, field)
Definition: queue.h:312
util-debug.h
TAILQ_FIRST
#define TAILQ_FIRST(head)
Definition: queue.h:250
ROHashTable_::item_size
uint16_t item_size
Definition: util-rohash.h:30
ROHashLookup
void * ROHashLookup(ROHashTable *table, void *data, uint16_t size)
Definition: util-rohash.c:113
ROHashTableOffsets_::cnt
uint32_t cnt
Definition: util-rohash.c:53
ROHashTable_::hash_bits
uint8_t hash_bits
Definition: util-rohash.h:29
ROHashMemorySize
uint32_t ROHashMemorySize(ROHashTable *table)
Definition: util-rohash.c:102
SCReturnPtr
#define SCReturnPtr(x, type)
Definition: util-debug.h:287
ROHashTableItem_
Definition: util-rohash.c:46
ROHashTable_::items
uint32_t items
Definition: util-rohash.h:31
suricata-common.h
ROHashInit
ROHashTable * ROHashInit(uint8_t hash_bits, uint16_t item_size)
initialize a new rohash
Definition: util-rohash.c:64
hashsize
#define hashsize(n)
Definition: util-hash-lookup3.h:40
ROHashInitQueueValue
int ROHashInitQueueValue(ROHashTable *table, void *value, uint16_t size)
Add a new value to the hash.
Definition: util-rohash.c:151
util-hash-lookup3.h
hashmask
#define hashmask(n)
Definition: util-hash-lookup3.h:41
SCLogError
#define SCLogError(...)
Macro used to log ERROR messages.
Definition: util-debug.h:261
ROHashFree
void ROHashFree(ROHashTable *table)
Definition: util-rohash.c:91
SCFree
#define SCFree(p)
Definition: util-mem.h:61
ROHashTable_::locked
uint8_t locked
Definition: util-rohash.h:28
ROHashTable
struct ROHashTable_ ROHashTable
ROHashTableItem_::pos
uint32_t pos
Definition: util-rohash.c:47
ROHashTableItem
struct ROHashTableItem_ ROHashTableItem
SCCalloc
#define SCCalloc(nm, sz)
Definition: util-mem.h:53
SCMemcmp
#define SCMemcmp(a, b, c)
Definition: util-memcmp.h:290