1 | /* |
2 | * Copyright (c) 2015-2016, Intel Corporation |
3 | * |
4 | * Redistribution and use in source and binary forms, with or without |
5 | * modification, are permitted provided that the following conditions are met: |
6 | * |
7 | * * Redistributions of source code must retain the above copyright notice, |
8 | * this list of conditions and the following disclaimer. |
9 | * * Redistributions in binary form must reproduce the above copyright |
10 | * notice, this list of conditions and the following disclaimer in the |
11 | * documentation and/or other materials provided with the distribution. |
12 | * * Neither the name of Intel Corporation nor the names of its contributors |
13 | * may be used to endorse or promote products derived from this software |
14 | * without specific prior written permission. |
15 | * |
16 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
17 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
18 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
19 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE |
20 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
21 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
22 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
23 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
24 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
25 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
26 | * POSSIBILITY OF SUCH DAMAGE. |
27 | */ |
28 | |
29 | #ifndef NFA_API_QUEUE_H |
30 | #define NFA_API_QUEUE_H |
31 | |
32 | #ifdef __cplusplus |
33 | extern "C" |
34 | { |
35 | #endif |
36 | |
37 | #include "ue2common.h" |
38 | #include "callback.h" |
39 | |
40 | /** Size of mq::items, max elements on a queue. */ |
41 | #define MAX_MQE_LEN 10 |
42 | |
43 | /** Queue events */ |
44 | |
45 | /** Queue event: begin scanning. Note: stateless engines will start from this |
46 | * location. */ |
47 | #define MQE_START 0U |
48 | |
49 | /** Queue event: stop scanning. */ |
50 | #define MQE_END 1U |
51 | |
52 | /** Queue event: enable start and start-dot-star. */ |
53 | #define MQE_TOP 2U |
54 | |
55 | /** Queue event: first event corresponding to a numbered TOP. Additional tops |
56 | * (in multi-top engines) use the event values from MQE_TOP_FIRST to |
57 | * MQE_INVALID - 1. */ |
58 | #define MQE_TOP_FIRST 4U |
59 | |
60 | /** Invalid queue event */ |
61 | #define MQE_INVALID (~0U) |
62 | |
63 | /** Queue item */ |
64 | struct mq_item { |
65 | u32 type; /**< event type, from MQE_* */ |
66 | s64a location; /**< relative to the start of the current buffer */ |
67 | u64a som; /**< pattern start-of-match corresponding to a top, only used |
68 | * by som engines. */ |
69 | }; |
70 | |
71 | // Forward decl. |
72 | struct NFA; |
73 | |
74 | /** |
75 | * Queue of events to control engine execution. mq::cur is index of first |
76 | * valid event, mq::end is one past the index of last valid event. |
77 | */ |
78 | struct mq { |
79 | const struct NFA *nfa; /**< nfa corresponding to the queue */ |
80 | u32 cur; /**< index of the first valid item in the queue */ |
81 | u32 end; /**< index one past the last valid item in the queue */ |
82 | char *state; /**< uncompressed stream state; lives in scratch */ |
83 | char *streamState; /**< |
84 | * real stream state; used to access structures which |
85 | * not duplicated the scratch state (bounded repeats, |
86 | * etc) */ |
87 | u64a offset; /**< base offset of the buffer */ |
88 | const u8 *buffer; /**< buffer to scan */ |
89 | size_t length; /**< length of buffer */ |
90 | const u8 *history; /**< |
91 | * history buffer; (logically) immediately before the |
92 | * main buffer */ |
93 | size_t hlength; /**< length of the history buffer */ |
94 | struct hs_scratch *scratch; /**< global scratch space */ |
95 | char report_current; /**< |
96 | * report_current matches at starting offset through |
97 | * callback. If true, the queue must be located at a |
98 | * point where MO_MATCHES_PENDING was returned */ |
99 | NfaCallback cb; /**< callback to trigger on matches */ |
100 | void *context; /**< context to pass along with a callback */ |
101 | struct mq_item items[MAX_MQE_LEN]; /**< queue items */ |
102 | }; |
103 | |
104 | |
105 | /** |
106 | * Pushes an (event, location, som) item onto a queue. If it is identical to the |
107 | * previous item on the queue, it is not added to the queue. |
108 | * @param q queue |
109 | * @param e event |
110 | * @param som som marker |
111 | * @param loc event location |
112 | */ |
113 | static really_inline |
114 | void pushQueueSom(struct mq * restrict q, u32 e, s64a loc, u64a som) { |
115 | DEBUG_PRINTF("pushing %u@%lld -> %u [som = %llu]\n" , e, loc, q->end, som); |
116 | assert(q->end < MAX_MQE_LEN); |
117 | assert(e < MQE_INVALID); |
118 | /* stop gcc getting too smart for its own good */ |
119 | /* assert(!q->end || q->items[q->end - 1].location <= loc); */ |
120 | assert(q->end || e == MQE_START); |
121 | |
122 | // Avoid duplicate items on the queue. |
123 | if (q->end) { |
124 | struct mq_item *item = &q->items[q->end - 1]; |
125 | if (item->type == e && item->location == loc) { |
126 | DEBUG_PRINTF("dropping duplicate item\n" ); |
127 | LIMIT_TO_AT_MOST(&item->som, som); /* take lower som */ |
128 | return; |
129 | } |
130 | } |
131 | |
132 | u32 end = q->end; |
133 | struct mq_item *item = &q->items[end]; |
134 | item->type = e; |
135 | item->location = loc; |
136 | item->som = som; |
137 | q->end = end + 1; |
138 | } |
139 | |
140 | /** |
141 | * Pushes an (event, location) item onto a queue. If it is identical to the |
142 | * previous item on the queue, it is not added to the queue. |
143 | * @param q queue |
144 | * @param e event |
145 | * @param loc event location |
146 | */ |
147 | static really_inline |
148 | void pushQueue(struct mq * restrict q, u32 e, s64a loc) { |
149 | pushQueueSom(q, e, loc, 0); |
150 | } |
151 | |
152 | /** |
153 | * Pushes an (event, location) item onto a queue. |
154 | * This version of @ref pushQueue does not check to ensure that the item being |
155 | * added is not already on the queue. Used for events other than tops. |
156 | */ |
157 | static really_inline |
158 | void pushQueueNoMerge(struct mq * restrict q, u32 e, s64a loc) { |
159 | DEBUG_PRINTF("pushing %u@%lld -> %u\n" , e, loc, q->end); |
160 | assert(q->end < MAX_MQE_LEN); |
161 | assert(e < MQE_INVALID); |
162 | /* stop gcc getting too smart for its own good */ |
163 | /* assert(!q->end || q->items[q->end - 1].location <= loc); */ |
164 | assert(q->end || e == MQE_START); |
165 | |
166 | #ifndef NDEBUG |
167 | // We assert that the event is different from its predecessor. If it's a |
168 | // dupe, you should have used the ordinary pushQueue call. |
169 | if (q->end) { |
170 | UNUSED struct mq_item *prev = &q->items[q->end - 1]; |
171 | assert(prev->type != e || prev->location != loc); |
172 | } |
173 | #endif |
174 | |
175 | u32 end = q->end; |
176 | struct mq_item *item = &q->items[end]; |
177 | item->type = e; |
178 | item->location = loc; |
179 | item->som = 0; |
180 | q->end = end + 1; |
181 | } |
182 | |
183 | /** \brief Returns the type of the current queue event. */ |
184 | static really_inline u32 q_cur_type(const struct mq *q) { |
185 | assert(q->cur < q->end); |
186 | assert(q->cur < MAX_MQE_LEN); |
187 | return q->items[q->cur].type; |
188 | } |
189 | |
190 | /** \brief Returns the location (relative to the beginning of the current data |
191 | * buffer) of the current queue event. */ |
192 | static really_inline s64a q_cur_loc(const struct mq *q) { |
193 | assert(q->cur < q->end); |
194 | assert(q->cur < MAX_MQE_LEN); |
195 | return q->items[q->cur].location; |
196 | } |
197 | |
198 | /** \brief Returns the type of the last event in the queue. */ |
199 | static really_inline u32 q_last_type(const struct mq *q) { |
200 | assert(q->cur < q->end); |
201 | assert(q->end > 0); |
202 | assert(q->end <= MAX_MQE_LEN); |
203 | return q->items[q->end - 1].type; |
204 | } |
205 | |
206 | /** \brief Returns the location (relative to the beginning of the current data |
207 | * buffer) of the last event in the queue. */ |
208 | static really_inline s64a q_last_loc(const struct mq *q) { |
209 | assert(q->cur < q->end); |
210 | assert(q->end > 0); |
211 | assert(q->end <= MAX_MQE_LEN); |
212 | return q->items[q->end - 1].location; |
213 | } |
214 | |
215 | /** \brief Returns the absolute stream offset of the current queue event. */ |
216 | static really_inline u64a q_cur_offset(const struct mq *q) { |
217 | assert(q->cur < q->end); |
218 | assert(q->cur < MAX_MQE_LEN); |
219 | return q->offset + (u64a)q->items[q->cur].location; |
220 | } |
221 | |
222 | /** |
223 | * \brief Removes all events in the queue before the given location. |
224 | */ |
225 | static really_inline |
226 | void q_skip_forward_to(struct mq *q, s64a min_loc) { |
227 | assert(q->cur < q->end); |
228 | assert(q->cur < MAX_MQE_LEN); |
229 | assert(q->items[q->cur].type == MQE_START); |
230 | |
231 | if (q_cur_loc(q) >= min_loc) { |
232 | DEBUG_PRINTF("all events >= loc %lld\n" , min_loc); |
233 | return; |
234 | } |
235 | |
236 | const u32 start_loc = q->cur; |
237 | |
238 | do { |
239 | DEBUG_PRINTF("remove item with loc=%lld\n" , q_cur_loc(q)); |
240 | q->cur++; |
241 | } while (q->cur < q->end && q_cur_loc(q) < min_loc); |
242 | |
243 | if (q->cur > start_loc) { |
244 | // Move original MQE_START item forward. |
245 | q->cur--; |
246 | q->items[q->cur] = q->items[start_loc]; |
247 | } |
248 | } |
249 | |
250 | #ifdef DEBUG |
251 | // Dump the contents of the given queue. |
252 | static never_inline UNUSED |
253 | void debugQueue(const struct mq *q) { |
254 | DEBUG_PRINTF("q=%p, nfa=%p\n" , q, q->nfa); |
255 | DEBUG_PRINTF("q offset=%llu, buf={%p, len=%zu}, history={%p, len=%zu}\n" , |
256 | q->offset, q->buffer, q->length, q->history, q->hlength); |
257 | DEBUG_PRINTF("q cur=%u, end=%u\n" , q->cur, q->end); |
258 | for (u32 cur = q->cur; cur < q->end; cur++) { |
259 | const char *type = "UNKNOWN" ; |
260 | u32 e = q->items[cur].type; |
261 | switch (e) { |
262 | case MQE_START: |
263 | type = "MQE_START" ; |
264 | break; |
265 | case MQE_END: |
266 | type = "MQE_END" ; |
267 | break; |
268 | case MQE_TOP: |
269 | type = "MQE_TOP" ; |
270 | break; |
271 | case MQE_INVALID: |
272 | type = "MQE_INVALID" ; |
273 | break; |
274 | default: |
275 | assert(e >= MQE_TOP_FIRST && e < MQE_INVALID); |
276 | type = "MQE_TOP_N" ; |
277 | break; |
278 | } |
279 | DEBUG_PRINTF("\tq[%u] %lld %u:%s\n" , cur, q->items[cur].location, |
280 | q->items[cur].type, type); |
281 | } |
282 | } |
283 | #endif // DEBUG |
284 | |
285 | #ifdef __cplusplus |
286 | } |
287 | #endif |
288 | |
289 | #endif |
290 | |