1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
|
/* Copyright (C) 2007-2016 Open Information Security Foundation
*
* You can copy, redistribute or modify this Program under the terms of
* the GNU General Public License version 2 as published by the Free
* Software Foundation.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* version 2 along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
* 02110-1301, USA.
*/
/**
* \file
*
* \author Victor Julien <victor@inliniac.net>
*
* thash -> thread hash. Hash table with locking handling.
*/
#ifndef __THASH_H__
#define __THASH_H__
#include "threads.h"
/** Spinlocks or Mutex for the buckets. */
//#define HRLOCK_SPIN
#define HRLOCK_MUTEX
#ifdef HRLOCK_SPIN
#ifdef HRLOCK_MUTEX
#error Cannot enable both HRLOCK_SPIN and HRLOCK_MUTEX
#endif
#endif
#ifdef HRLOCK_SPIN
#define HRLOCK_TYPE SCSpinlock
#define HRLOCK_INIT(fb) SCSpinInit(&(fb)->lock, 0)
#define HRLOCK_DESTROY(fb) SCSpinDestroy(&(fb)->lock)
#define HRLOCK_LOCK(fb) SCSpinLock(&(fb)->lock)
#define HRLOCK_TRYLOCK(fb) SCSpinTrylock(&(fb)->lock)
#define HRLOCK_UNLOCK(fb) SCSpinUnlock(&(fb)->lock)
#elif defined HRLOCK_MUTEX
#define HRLOCK_TYPE SCMutex
#define HRLOCK_INIT(fb) SCMutexInit(&(fb)->lock, NULL)
#define HRLOCK_DESTROY(fb) SCMutexDestroy(&(fb)->lock)
#define HRLOCK_LOCK(fb) SCMutexLock(&(fb)->lock)
#define HRLOCK_TRYLOCK(fb) SCMutexTrylock(&(fb)->lock)
#define HRLOCK_UNLOCK(fb) SCMutexUnlock(&(fb)->lock)
#else
#error Enable HRLOCK_SPIN or HRLOCK_MUTEX
#endif
/** Spinlocks or Mutex for the queues. */
//#define HQLOCK_SPIN
#define HQLOCK_MUTEX
#ifdef HQLOCK_SPIN
#ifdef HQLOCK_MUTEX
#error Cannot enable both HQLOCK_SPIN and HQLOCK_MUTEX
#endif
#endif
#ifdef HQLOCK_SPIN
#define HQLOCK_INIT(q) SCSpinInit(&(q)->s, 0)
#define HQLOCK_DESTROY(q) SCSpinDestroy(&(q)->s)
#define HQLOCK_LOCK(q) SCSpinLock(&(q)->s)
#define HQLOCK_TRYLOCK(q) SCSpinTrylock(&(q)->s)
#define HQLOCK_UNLOCK(q) SCSpinUnlock(&(q)->s)
#elif defined HQLOCK_MUTEX
#define HQLOCK_INIT(q) SCMutexInit(&(q)->m, NULL)
#define HQLOCK_DESTROY(q) SCMutexDestroy(&(q)->m)
#define HQLOCK_LOCK(q) SCMutexLock(&(q)->m)
#define HQLOCK_TRYLOCK(q) SCMutexTrylock(&(q)->m)
#define HQLOCK_UNLOCK(q) SCMutexUnlock(&(q)->m)
#else
#error Enable HQLOCK_SPIN or HQLOCK_MUTEX
#endif
typedef struct THashData_ {
/** ippair mutex */
SCMutex m;
/** use cnt, reference counter */
SC_ATOMIC_DECLARE(unsigned int, use_cnt);
void *data;
struct THashData_ *next;
struct THashData_ *prev;
} THashData;
typedef struct THashHashRow_ {
HRLOCK_TYPE lock;
THashData *head;
THashData *tail;
} __attribute__((aligned(CLS))) THashHashRow;
typedef struct THashDataQueue_
{
THashData *top;
THashData *bot;
uint32_t len;
#ifdef DBG_PERF
uint32_t dbg_maxlen;
#endif /* DBG_PERF */
#ifdef HQLOCK_MUTEX
SCMutex m;
#elif defined HQLOCK_SPIN
SCSpinlock s;
#else
#error Enable HQLOCK_SPIN or HQLOCK_MUTEX
#endif
} THashDataQueue;
typedef int (*THashOutputFunc)(void *output_ctx, const uint8_t *data, const uint32_t data_len);
typedef int (*THashFormatFunc)(const void *in_data, char *output, size_t output_size);
typedef struct THashDataConfig_ {
uint64_t memcap;
uint32_t hash_rand;
uint32_t hash_size;
uint32_t prealloc;
uint32_t data_size;
int (*DataSet)(void *dst, void *src);
void (*DataFree)(void *);
uint32_t (*DataHash)(void *);
bool (*DataCompare)(void *, void *);
} THashConfig;
#define THASH_DATA_SIZE(ctx) (sizeof(THashData) + (ctx)->config.data_size)
typedef struct THashTableContext_ {
/* array of rows indexed by the hash value % hash size */
THashHashRow *array;
SC_ATOMIC_DECLARE(uint64_t, memuse);
SC_ATOMIC_DECLARE(uint32_t, counter);
SC_ATOMIC_DECLARE(uint32_t, prune_idx);
THashDataQueue spare_q;
THashConfig config;
/* flag set if memcap was reached at least once. */
SC_ATOMIC_DECLARE(bool, memcap_reached);
} THashTableContext;
/** \brief check if a memory alloc would fit in the memcap
*
* \param size memory allocation size to check
*
* \retval 1 it fits
* \retval 0 no fit
*/
#define THASH_CHECK_MEMCAP(ctx, size) \
((((uint64_t)SC_ATOMIC_GET((ctx)->memuse) + (uint64_t)(size)) <= (ctx)->config.memcap))
#define THashIncrUsecnt(h) \
(void)SC_ATOMIC_ADD((h)->use_cnt, 1)
#define THashDecrUsecnt(h) \
(void)SC_ATOMIC_SUB((h)->use_cnt, 1)
THashTableContext *THashInit(const char *cnf_prefix, size_t data_size,
int (*DataSet)(void *dst, void *src), void (*DataFree)(void *),
uint32_t (*DataHash)(void *), bool (*DataCompare)(void *, void *), bool reset_memcap,
uint64_t memcap, uint32_t hashsize);
void THashShutdown(THashTableContext *ctx);
static inline void THashDataLock(THashData *d)
{
SCMutexLock(&d->m);
}
static inline void THashDataUnlock(THashData *d)
{
SCMutexUnlock(&d->m);
}
struct THashDataGetResult {
THashData *data;
bool is_new;
};
struct THashDataGetResult THashGetFromHash (THashTableContext *ctx, void *data);
THashData *THashLookupFromHash (THashTableContext *ctx, void *data);
THashDataQueue *THashDataQueueNew(void);
void THashCleanup(THashTableContext *ctx);
int THashWalk(THashTableContext *, THashFormatFunc, THashOutputFunc, void *);
int THashRemoveFromHash (THashTableContext *ctx, void *data);
void THashConsolidateMemcap(THashTableContext *ctx);
void THashDataMoveToSpare(THashTableContext *ctx, THashData *h);
#endif /* __THASH_H__ */
|
