suricata
util-mpm-ac-ks.h
Go to the documentation of this file.
1 /* Copyright (C) 2013-2014 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 Anoop Saldanha <anoopsaldanha@gmail.com>
22  * \author Ken Steele <suricata@tilera.com>
23  *
24  */
25 
26 #ifndef __UTIL_MPM_AC_KS__H__
27 #define __UTIL_MPM_AC_KS__H__
28 
29 typedef struct SCACTilePatternList_ {
30  uint8_t *cs;
31  uint16_t patlen;
32 
33  uint16_t offset;
34  uint16_t depth;
35 
36  /* Pattern Id */
37  uint32_t pid;
38 
39  /* sid(s) for this pattern */
40  uint32_t sids_size;
43 
44 typedef struct SCACTileOutputTable_ {
45  /* list of pattern indexes */
47  /* number of entries in pattern list */
48  uint32_t no_of_entries;
50 
51 struct SCACTileSearchCtx_;
52 
53 /* Reordered for Tilera cache */
54 typedef struct SCACTileCtx_ {
55 
56  /* Convert input character to matching alphabet */
57  uint8_t translate_table[256];
58 
59  /* The all important memory hungry state_table.
60  * The size of each next-state is determined by bytes_per_state.
61  */
62  void *state_table;
63 
64  /* Specialized search function based on size of data in delta
65  * tables. The alphabet size determines address shifting and the
66  * number of states could make the next state could be 16 bits or
67  * 32 bits.
68  */
69  uint32_t (*Search)(const struct SCACTileSearchCtx_ *ctx, struct MpmThreadCtx_ *,
70  PrefilterRuleStore *, const uint8_t *, uint32_t);
71 
72  /* Function to set the next state based on size of next state
73  * (bytes_per_state).
74  */
75  void (*SetNextState)(struct SCACTileCtx_ *ctx, int state, int aa,
76  int new_state, int outputs);
77 
78  /* List of patterns that match for this state. Indexed by State Number */
80  /* Indexed by MpmPatternIndex */
82 
83  /* pattern arrays. We need this only during the goto table
84  creation phase */
86 
87  /* goto_table, failure table and output table. Needed to create
88  * state_table. Will be freed, once we have created the
89  * state_table */
90  int32_t (*goto_table)[256];
91  int32_t *failure_table;
92 
93  /* Number of states used */
94  uint32_t state_count;
95  /* Number of states allocated. */
97 
98  uint32_t alpha_hist[256];
99  /* Number of characters in the compressed alphabet. */
100  uint16_t alphabet_size;
101  /* Space used to store compressed alphabet is the next
102  * larger or equal power-of-2.
103  */
105 
106  /* How many bytes are used to store the next state. */
108 
110 
111 
112 /* Only the stuff used at search time. This
113  * structure is created after all the patterns are added.
114  */
115 typedef struct SCACTileSearchCtx_ {
116 
117  /* Specialized search function based on size of data in delta
118  * tables. The alphabet size determines address shifting and the
119  * number of states could make the next state could be 16 bits or
120  * 32 bits.
121  */
122  uint32_t (*Search)(const struct SCACTileSearchCtx_ *ctx, struct MpmThreadCtx_ *,
123  PrefilterRuleStore *, const uint8_t *, uint32_t);
124 
125  /* Convert input character to matching alphabet */
126  uint8_t translate_table[256];
127 
128  /* the all important memory hungry state_table */
129  void *state_table;
130 
131  /* List of patterns that match for this state. Indexed by State Number */
134 
135  /* Number of bytes in the array of bits. One bit per pattern in this MPM. */
137 
138  /* Number of states used */
139  uint32_t state_count;
140 
141  uint32_t pattern_cnt;
142 
143  /* MPM Creation data, only used at initialization. */
145 
147 
148 
149 typedef struct SCACTileThreadCtx_ {
150  /* the total calls we make to the search function */
151  uint32_t total_calls;
152  /* the total patterns that we ended up matching against */
153  uint64_t total_matches;
155 
156 void MpmACTileRegister(void);
157 
158 #endif /* __UTIL_MPM_AC_KS__H__ */
SCACTileSearchCtx
struct SCACTileSearchCtx_ SCACTileSearchCtx
SCACTileSearchCtx_
Definition: util-mpm-ac-ks.h:115
MpmPatternIndex
uint32_t MpmPatternIndex
Definition: util-mpm.h:44
SCACTileCtx_::Search
uint32_t(* Search)(const struct SCACTileSearchCtx_ *ctx, struct MpmThreadCtx_ *, PrefilterRuleStore *, const uint8_t *, uint32_t)
Definition: util-mpm-ac-ks.h:69
SCACTileCtx_::allocated_state_count
uint32_t allocated_state_count
Definition: util-mpm-ac-ks.h:96
MpmThreadCtx_
Definition: util-mpm.h:46
SCACTileSearchCtx_::Search
uint32_t(* Search)(const struct SCACTileSearchCtx_ *ctx, struct MpmThreadCtx_ *, PrefilterRuleStore *, const uint8_t *, uint32_t)
Definition: util-mpm-ac-ks.h:122
PrefilterRuleStore_
structure for storing potential rule matches
Definition: util-prefilter.h:32
SCACTileCtx_::pattern_list
SCACTilePatternList * pattern_list
Definition: util-mpm-ac-ks.h:81
SCACTileThreadCtx
struct SCACTileThreadCtx_ SCACTileThreadCtx
SCACTilePatternList_::offset
uint16_t offset
Definition: util-mpm-ac-ks.h:33
MpmACTileRegister
void MpmACTileRegister(void)
Register the aho-corasick mpm 'ks' originally developed by Ken Steele for Tilera Tile-Gx processor.
Definition: util-mpm-ac-ks.c:1467
SCACTileThreadCtx_::total_matches
uint64_t total_matches
Definition: util-mpm-ac-ks.h:153
SCACTileOutputTable
struct SCACTileOutputTable_ SCACTileOutputTable
SCACTileOutputTable_::no_of_entries
uint32_t no_of_entries
Definition: util-mpm-ac-ks.h:48
SCACTileSearchCtx_::output_table
SCACTileOutputTable * output_table
Definition: util-mpm-ac-ks.h:132
SCACTileSearchCtx_::pattern_cnt
uint32_t pattern_cnt
Definition: util-mpm-ac-ks.h:141
SCACTileSearchCtx_::state_table
void * state_table
Definition: util-mpm-ac-ks.h:129
SCACTileCtx_::goto_table
int32_t(* goto_table)[256]
Definition: util-mpm-ac-ks.h:90
SCACTileSearchCtx_::state_count
uint32_t state_count
Definition: util-mpm-ac-ks.h:139
SCACTileOutputTable_
Definition: util-mpm-ac-ks.h:44
SCACTileThreadCtx_
Definition: util-mpm-ac-ks.h:149
SCACTileSearchCtx_::mpm_bitarray_size
uint32_t mpm_bitarray_size
Definition: util-mpm-ac-ks.h:136
SCACTileCtx_::state_count
uint32_t state_count
Definition: util-mpm-ac-ks.h:94
SCACTileOutputTable_::patterns
MpmPatternIndex * patterns
Definition: util-mpm-ac-ks.h:46
SCACTilePatternList
struct SCACTilePatternList_ SCACTilePatternList
SCACTileSearchCtx_::init_ctx
SCACTileCtx * init_ctx
Definition: util-mpm-ac-ks.h:144
SCACTilePatternList_::pid
uint32_t pid
Definition: util-mpm-ac-ks.h:37
SCACTilePatternList_::sids
SigIntId * sids
Definition: util-mpm-ac-ks.h:41
SCACTileCtx_::alpha_hist
uint32_t alpha_hist[256]
Definition: util-mpm-ac-ks.h:98
MpmPattern_
Definition: util-mpm.h:54
SCACTileSearchCtx_::pattern_list
SCACTilePatternList * pattern_list
Definition: util-mpm-ac-ks.h:133
SCACTileCtx_::bytes_per_state
uint8_t bytes_per_state
Definition: util-mpm-ac-ks.h:107
SCACTileCtx_::alphabet_storage
uint16_t alphabet_storage
Definition: util-mpm-ac-ks.h:104
SCACTilePatternList_::cs
uint8_t * cs
Definition: util-mpm-ac-ks.h:30
SCACTileCtx_::SetNextState
void(* SetNextState)(struct SCACTileCtx_ *ctx, int state, int aa, int new_state, int outputs)
Definition: util-mpm-ac-ks.h:75
SCACTileThreadCtx_::total_calls
uint32_t total_calls
Definition: util-mpm-ac-ks.h:151
SCACTileCtx_::translate_table
uint8_t translate_table[256]
Definition: util-mpm-ac-ks.h:57
SCACTilePatternList_::depth
uint16_t depth
Definition: util-mpm-ac-ks.h:34
SCACTileCtx_::state_table
void * state_table
Definition: util-mpm-ac-ks.h:62
SCACTilePatternList_::patlen
uint16_t patlen
Definition: util-mpm-ac-ks.h:31
SCACTileCtx
struct SCACTileCtx_ SCACTileCtx
SCACTileCtx_
Definition: util-mpm-ac-ks.h:54
SCACTilePatternList_
Definition: util-mpm-ac-ks.h:29
SCACTileCtx_::parray
MpmPattern ** parray
Definition: util-mpm-ac-ks.h:85
SCACTilePatternList_::sids_size
uint32_t sids_size
Definition: util-mpm-ac-ks.h:40
SigIntId
#define SigIntId
Definition: suricata-common.h:297
SCACTileSearchCtx_::translate_table
uint8_t translate_table[256]
Definition: util-mpm-ac-ks.h:126
SCACTileCtx_::failure_table
int32_t * failure_table
Definition: util-mpm-ac-ks.h:91
SCACTileCtx_::output_table
SCACTileOutputTable * output_table
Definition: util-mpm-ac-ks.h:79
SCACTileCtx_::alphabet_size
uint16_t alphabet_size
Definition: util-mpm-ac-ks.h:100