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 "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(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  uint32_t r1 = hashsize(table->hash_bits) * sizeof(ROHashTableOffsets);
106  uint32_t r2 = table->items * table->item_size;
107  return (uint32_t)(r1 + r2 + sizeof(ROHashTable));
108 }
109 
110 /**
111  * \retval NULL not found
112  * \retval ptr found
113  */
114 void *ROHashLookup(ROHashTable *table, void *data, uint16_t size)
115 {
116  if (data == NULL || size != table->item_size) {
117  SCReturnPtr(NULL, "void");
118  }
119 
120  uint32_t hash = hashword(data, table->item_size/4, 0) & hashmask(table->hash_bits);
121 
122  /* get offsets start */
123  ROHashTableOffsets *os = (void *)table + sizeof(ROHashTable);
124  ROHashTableOffsets *o = &os[hash];
125 
126  /* no matches */
127  if (o->cnt == 0) {
128  SCReturnPtr(NULL, "void");
129  }
130 
131  uint32_t u;
132  for (u = 0; u < o->cnt; u++) {
133  uint32_t offset = (o->offset + u) * table->item_size;
134 
135  if (SCMemcmp(table->data + offset, data, table->item_size) == 0) {
136  SCReturnPtr(table->data + offset, "void");
137  }
138  }
139  SCReturnPtr(NULL, "void");
140 }
141 
142 /** \brief Add a new value to the hash
143  *
144  * \note can only be done when table isn't in a locked state yet
145  *
146  * \param table the hash table
147  * \param value value to add
148  * \param size value size. *MUST* match table item_size
149  *
150  * \retval 0 error
151  * \retval 1 ok
152  */
153 int ROHashInitQueueValue(ROHashTable *table, void *value, uint16_t size)
154 {
155  if (table->locked) {
156  SCLogError(SC_ERR_HASH_TABLE_INIT, "can't add value to locked table");
157  return 0;
158  }
159  if (table->item_size != size) {
160  SCLogError(SC_ERR_HASH_TABLE_INIT, "wrong size for data %u != %u", size, table->item_size);
161  return 0;
162  }
163 
164  ROHashTableItem *item = SCMalloc(sizeof(ROHashTableItem) + table->item_size);
165  if (item != NULL) {
166  memset(item, 0x00, sizeof(ROHashTableItem));
167  memcpy((void *)item + sizeof(ROHashTableItem), value, table->item_size);
168  TAILQ_INSERT_TAIL(&table->head, item, next);
169  return 1;
170  }
171 
172  return 0;
173 }
174 
175 /** \brief create final hash data structure
176  *
177  * \param table the hash table
178  *
179  * \retval 0 error
180  * \retval 1 ok
181  *
182  * \note after this call the nothing can be added to the hash anymore.
183  */
185 {
186  if (table->locked) {
187  SCLogError(SC_ERR_HASH_TABLE_INIT, "table already locked");
188  return 0;
189  }
190 
191  ROHashTableItem *item = NULL;
192  ROHashTableOffsets *os = (void *)table + sizeof(ROHashTable);
193 
194  /* count items per hash value */
195  TAILQ_FOREACH(item, &table->head, next) {
196  uint32_t hash = hashword((void *)item + sizeof(*item), table->item_size/4, 0) & hashmask(table->hash_bits);
197  ROHashTableOffsets *o = &os[hash];
198 
199  item->pos = o->cnt;
200  o->cnt++;
201  table->items++;
202  }
203 
204  if (table->items == 0) {
205  SCLogError(SC_ERR_HASH_TABLE_INIT, "no items");
206  return 0;
207  }
208 
209  /* get the data block */
210  uint32_t newsize = table->items * table->item_size;
211  table->data = SCMalloc(newsize);
212  if (table->data == NULL) {
213  SCLogError(SC_ERR_HASH_TABLE_INIT, "failed to alloc memory");
214  return 0;
215  }
216  memset(table->data, 0x00, newsize);
217 
218  /* calc offsets into the block per hash value */
219  uint32_t total = 0;
220  uint32_t x;
221  for (x = 0; x < hashsize(table->hash_bits); x++) {
222  ROHashTableOffsets *o = &os[x];
223 
224  if (o->cnt == 0)
225  continue;
226 
227  o->offset = total;
228  total += o->cnt;
229  }
230 
231  /* copy each value into the data block */
232  TAILQ_FOREACH(item, &table->head, next) {
233  uint32_t hash = hashword((void *)item + sizeof(*item), table->item_size/4, 0) & hashmask(table->hash_bits);
234 
235  ROHashTableOffsets *o = &os[hash];
236  uint32_t offset = (o->offset + item->pos) * table->item_size;
237 
238  memcpy(table->data + offset, (void *)item + sizeof(*item), table->item_size);
239 
240  }
241 
242  /* clean up temp items */
243  while ((item = TAILQ_FIRST(&table->head))) {
244  TAILQ_REMOVE(&table->head, item, next);
245  SCFree(item);
246  }
247 
248  table->locked = 1;
249  return 1;
250 }
ROHashTable_::data
void * data
Definition: util-rohash.h:33
hashword
uint32_t hashword(const uint32_t *k, size_t length, uint32_t initval)
Definition: util-hash-lookup3.c:174
offset
uint64_t offset
Definition: util-streaming-buffer.h:0
TAILQ_INIT
#define TAILQ_INIT(head)
Definition: queue.h:262
SC_ERR_HASH_TABLE_INIT
@ SC_ERR_HASH_TABLE_INIT
Definition: util-error.h:144
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:28
TAILQ_INSERT_TAIL
#define TAILQ_INSERT_TAIL(head, elm, field)
Definition: queue.h:294
util-unittest.h
hashsize
#define hashsize(n)
Definition: util-hash-lookup3.c:67
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:184
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:31
ROHashLookup
void * ROHashLookup(ROHashTable *table, void *data, uint16_t size)
Definition: util-rohash.c:114
ROHashTableOffsets_::cnt
uint32_t cnt
Definition: util-rohash.c:53
ROHashTable_::hash_bits
uint8_t hash_bits
Definition: util-rohash.h:30
hashmask
#define hashmask(n)
Definition: util-hash-lookup3.c:68
ROHashMemorySize
uint32_t ROHashMemorySize(ROHashTable *table)
Definition: util-rohash.c:103
SCReturnPtr
#define SCReturnPtr(x, type)
Definition: util-debug.h:314
ROHashTableItem_
Definition: util-rohash.c:46
ROHashTable_::items
uint32_t items
Definition: util-rohash.h:32
suricata-common.h
SCLogError
#define SCLogError(err_code,...)
Macro used to log ERROR messages.
Definition: util-debug.h:255
ROHashInit
ROHashTable * ROHashInit(uint8_t hash_bits, uint16_t item_size)
initialize a new rohash
Definition: util-rohash.c:64
ROHashInitQueueValue
int ROHashInitQueueValue(ROHashTable *table, void *value, uint16_t size)
Add a new value to the hash.
Definition: util-rohash.c:153
util-hash-lookup3.h
SCMalloc
#define SCMalloc(sz)
Definition: util-mem.h:47
ROHashFree
void ROHashFree(ROHashTable *table)
Definition: util-rohash.c:92
SCFree
#define SCFree(p)
Definition: util-mem.h:61
ROHashTable_::locked
uint8_t locked
Definition: util-rohash.h:29
ROHashTable
struct ROHashTable_ ROHashTable
ROHashTableItem_::pos
uint32_t pos
Definition: util-rohash.c:47
ROHashTableItem
struct ROHashTableItem_ ROHashTableItem
SCMemcmp
#define SCMemcmp(a, b, c)
Definition: util-memcmp.h:290