suricata
util-rohash.c
Go to the documentation of this file.
1 /* Copyright (C) 2007-2012 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 "queue.h"
43 #include "util-rohash.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(SC_ERR_HASH_TABLE_INIT, "data size must be multiple of 4");
68  return NULL;
69  }
70  if (hash_bits < 4 || hash_bits > 31) {
71  SCLogError(SC_ERR_HASH_TABLE_INIT, "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 = SCMalloc(sizeof(ROHashTable) + size);
78  if (unlikely(table == NULL)) {
79  SCLogError(SC_ERR_HASH_TABLE_INIT, "failed to alloc memory");
80  return NULL;
81  }
82  memset(table, 0, sizeof(ROHashTable) + size);
83 
84  table->items = 0;
85  table->item_size = item_size;
86  table->hash_bits = hash_bits;
87  TAILQ_INIT(&table->head);
88 
89  return table;
90 }
91 
92 void ROHashFree(ROHashTable *table)
93 {
94  if (table != NULL) {
95  if (table->data != NULL) {
96  SCFree(table->data);
97  }
98 
99  SCFree(table);
100  }
101 }
102 
104 {
105  return (uint32_t)(hashsize(table->hash_bits) * sizeof(ROHashTableOffsets) +
106  table->items * table->item_size + 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  uint32_t hash = hashword(data, table->item_size/4, 0) & hashmask(table->hash_bits);
120 
121  /* get offsets start */
122  ROHashTableOffsets *os = (void *)table + sizeof(ROHashTable);
123  ROHashTableOffsets *o = &os[hash];
124 
125  /* no matches */
126  if (o->cnt == 0) {
127  SCReturnPtr(NULL, "void");
128  }
129 
130  uint32_t u;
131  for (u = 0; u < o->cnt; u++) {
132  uint32_t offset = (o->offset + u) * table->item_size;
133 
134  if (SCMemcmp(table->data + offset, data, table->item_size) == 0) {
135  SCReturnPtr(table->data + offset, "void");
136  }
137  }
138  SCReturnPtr(NULL, "void");
139 }
140 
141 /** \brief Add a new value to the hash
142  *
143  * \note can only be done when table isn't in a locked state yet
144  *
145  * \param table the hash table
146  * \param value value to add
147  * \param size value size. *MUST* match table item_size
148  *
149  * \retval 0 error
150  * \retval 1 ok
151  */
152 int ROHashInitQueueValue(ROHashTable *table, void *value, uint16_t size)
153 {
154  if (table->locked) {
155  SCLogError(SC_ERR_HASH_TABLE_INIT, "can't add value to locked table");
156  return 0;
157  }
158  if (table->item_size != size) {
159  SCLogError(SC_ERR_HASH_TABLE_INIT, "wrong size for data %u != %u", size, table->item_size);
160  return 0;
161  }
162 
163  ROHashTableItem *item = SCMalloc(sizeof(ROHashTableItem) + table->item_size);
164  if (item != NULL) {
165  memset(item, 0x00, sizeof(ROHashTableItem));
166  memcpy((void *)item + sizeof(ROHashTableItem), value, table->item_size);
167  TAILQ_INSERT_TAIL(&table->head, item, next);
168  return 1;
169  }
170 
171  return 0;
172 }
173 
174 /** \brief create final hash data structure
175  *
176  * \param table the hash table
177  *
178  * \retval 0 error
179  * \retval 1 ok
180  *
181  * \note after this call the nothing can be added to the hash anymore.
182  */
184 {
185  if (table->locked) {
186  SCLogError(SC_ERR_HASH_TABLE_INIT, "table already locked");
187  return 0;
188  }
189 
190  ROHashTableItem *item = NULL;
191  ROHashTableOffsets *os = (void *)table + sizeof(ROHashTable);
192 
193  /* count items per hash value */
194  TAILQ_FOREACH(item, &table->head, next) {
195  uint32_t hash = hashword((void *)item + sizeof(*item), table->item_size/4, 0) & 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(SC_ERR_HASH_TABLE_INIT, "no items");
205  return 0;
206  }
207 
208  /* get the data block */
209  uint32_t newsize = table->items * table->item_size;
210  table->data = SCMalloc(newsize);
211  if (table->data == NULL) {
212  SCLogError(SC_ERR_HASH_TABLE_INIT, "failed to alloc memory");
213  return 0;
214  }
215  memset(table->data, 0x00, newsize);
216 
217  /* calc offsets into the block per hash value */
218  uint32_t total = 0;
219  uint32_t x;
220  for (x = 0; x < hashsize(table->hash_bits); x++) {
221  ROHashTableOffsets *o = &os[x];
222 
223  if (o->cnt == 0)
224  continue;
225 
226  o->offset = total;
227  total += o->cnt;
228  }
229 
230  /* copy each value into the data block */
231  TAILQ_FOREACH(item, &table->head, next) {
232  uint32_t hash = hashword((void *)item + sizeof(*item), table->item_size/4, 0) & 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, (void *)item + sizeof(*item), table->item_size);
238 
239  }
240 
241  /* clean up temp items */
242  while ((item = TAILQ_FIRST(&table->head))) {
243  TAILQ_REMOVE(&table->head, item, next);
244  SCFree(item);
245  }
246 
247  table->locked = 1;
248  return 1;
249 }
uint32_t hashword(const uint32_t *k, size_t length, uint32_t initval)
#define SCMemcmp(a, b, c)
Definition: util-memcmp.h:490
#define hashsize(n)
#define TAILQ_FIRST(head)
Definition: queue.h:339
#define TAILQ_FOREACH(var, head, field)
Definition: queue.h:350
struct HtpBodyChunk_ * next
#define unlikely(expr)
Definition: util-optimize.h:35
uint16_t item_size
Definition: util-rohash.h:32
uint64_t offset
uint32_t ROHashMemorySize(ROHashTable *table)
Definition: util-rohash.c:103
uint8_t locked
Definition: util-rohash.h:30
void * ROHashLookup(ROHashTable *table, void *data, uint16_t size)
Definition: util-rohash.c:113
#define TAILQ_INIT(head)
Definition: queue.h:370
#define SCLogError(err_code,...)
Macro used to log ERROR messages.
Definition: util-debug.h:294
ROHashTable * ROHashInit(uint8_t hash_bits, uint16_t item_size)
initialize a new rohash
Definition: util-rohash.c:64
#define TAILQ_REMOVE(head, elm, field)
Definition: queue.h:412
void * data
Definition: util-rohash.h:34
#define TAILQ_INSERT_TAIL(head, elm, field)
Definition: queue.h:385
#define SCMalloc(a)
Definition: util-mem.h:174
#define hashmask(n)
#define SCFree(a)
Definition: util-mem.h:236
int ROHashInitFinalize(ROHashTable *table)
create final hash data structure
Definition: util-rohash.c:183
#define TAILQ_ENTRY(type)
Definition: queue.h:330
void ROHashFree(ROHashTable *table)
Definition: util-rohash.c:92
uint32_t items
Definition: util-rohash.h:33
#define SCReturnPtr(x, type)
Definition: util-debug.h:353
struct ROHashTableOffsets_ ROHashTableOffsets
int ROHashInitQueueValue(ROHashTable *table, void *value, uint16_t size)
Add a new value to the hash.
Definition: util-rohash.c:152
uint8_t hash_bits
Definition: util-rohash.h:31