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
33extern "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 */
64struct 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.
72struct 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 */
78struct 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 */
113static really_inline
114void 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 */
147static really_inline
148void 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 */
157static really_inline
158void 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. */
184static 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. */
192static 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. */
199static 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. */
208static 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. */
216static 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 */
225static really_inline
226void 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.
252static never_inline UNUSED
253void 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