1/*
2 * Copyright (c) 2015-2018, 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 ROSE_MATCH_H
30#define ROSE_MATCH_H
31
32#include "catchup.h"
33#include "runtime.h"
34#include "scratch.h"
35#include "report.h"
36#include "rose_common.h"
37#include "rose_internal.h"
38#include "ue2common.h"
39#include "hwlm/hwlm.h"
40#include "nfa/nfa_api.h"
41#include "nfa/nfa_api_queue.h"
42#include "nfa/nfa_api_util.h"
43#include "som/som_runtime.h"
44#include "util/bitutils.h"
45#include "util/exhaust.h"
46#include "util/fatbit.h"
47#include "util/multibit.h"
48
49/* Callbacks, defined in catchup.c */
50
51int roseNfaAdaptor(u64a start, u64a end, ReportID id, void *context);
52
53/* Callbacks, defined in match.c */
54
55hwlmcb_rv_t roseCallback(size_t end, u32 id, struct hs_scratch *scratch);
56hwlmcb_rv_t roseFloatingCallback(size_t end, u32 id,
57 struct hs_scratch *scratch);
58hwlmcb_rv_t roseDelayRebuildCallback(size_t end, u32 id,
59 struct hs_scratch *scratch);
60int roseAnchoredCallback(u64a start, u64a end, u32 id, void *ctx);
61
62/* Common code, used all over Rose runtime */
63
64hwlmcb_rv_t roseHandleChainMatch(const struct RoseEngine *t,
65 struct hs_scratch *scratch, u32 event,
66 u64a top_squash_distance, u64a end,
67 char in_catchup);
68
69/** \brief Initialize the queue for a suffix/outfix engine. */
70static really_inline
71void initQueue(struct mq *q, u32 qi, const struct RoseEngine *t,
72 struct hs_scratch *scratch) {
73 const struct NfaInfo *info = getNfaInfoByQueue(t, qi);
74 assert(scratch->fullState);
75 q->nfa = getNfaByInfo(t, info);
76 q->end = 0;
77 q->cur = 0;
78 q->state = scratch->fullState + info->fullStateOffset;
79 q->streamState = scratch->core_info.state + info->stateOffset;
80 q->offset = scratch->core_info.buf_offset;
81 q->buffer = scratch->core_info.buf;
82 q->length = scratch->core_info.len;
83 q->history = scratch->core_info.hbuf;
84 q->hlength = scratch->core_info.hlen;
85 q->cb = roseNfaAdaptor;
86 q->context = scratch;
87 q->report_current = 0;
88
89 DEBUG_PRINTF("qi=%u, offset=%llu, fullState=%u, streamState=%u, "
90 "state=%u\n", qi, q->offset, info->fullStateOffset,
91 info->stateOffset, *(u32 *)q->state);
92}
93
94/** \brief Initialize the queue for a leftfix (prefix/infix) engine. */
95static really_inline
96void initRoseQueue(const struct RoseEngine *t, u32 qi,
97 const struct LeftNfaInfo *left,
98 struct hs_scratch *scratch) {
99 struct mq *q = scratch->queues + qi;
100 const struct NfaInfo *info = getNfaInfoByQueue(t, qi);
101 q->nfa = getNfaByInfo(t, info);
102 q->end = 0;
103 q->cur = 0;
104 q->state = scratch->fullState + info->fullStateOffset;
105
106 // Transient roses don't have stream state, we use tstate in scratch
107 // instead. The only reason we need this at ALL is for LimEx extended
108 // regions, which assume that they have access to q->streamState +
109 // compressedStateSize.
110 if (left->transient) {
111 q->streamState = (char *)scratch->tstate + info->stateOffset;
112 } else {
113 q->streamState = scratch->core_info.state + info->stateOffset;
114 }
115
116 q->offset = scratch->core_info.buf_offset;
117 q->buffer = scratch->core_info.buf;
118 q->length = scratch->core_info.len;
119 q->history = scratch->core_info.hbuf;
120 q->hlength = scratch->core_info.hlen;
121 q->cb = NULL;
122 q->context = NULL;
123 q->report_current = 0;
124
125 DEBUG_PRINTF("qi=%u, offset=%llu, fullState=%u, streamState=%u, "
126 "state=%u\n", qi, q->offset, info->fullStateOffset,
127 info->stateOffset, *(u32 *)q->state);
128}
129
130/** returns 0 if space for two items (top and end) on the queue */
131static really_inline
132char isQueueFull(const struct mq *q) {
133 return q->end + 2 > MAX_MQE_LEN;
134}
135
136static really_inline
137void loadStreamState(const struct NFA *nfa, struct mq *q, s64a loc) {
138 DEBUG_PRINTF("offset=%llu, length=%zu, hlength=%zu, loc=%lld\n",
139 q->offset, q->length, q->hlength, loc);
140 nfaExpandState(nfa, q->state, q->streamState, q->offset + loc,
141 queue_prev_byte(q, loc));
142}
143
144static really_inline
145void storeRoseDelay(const struct RoseEngine *t, char *state,
146 const struct LeftNfaInfo *left, u32 loc) {
147 u32 di = left->lagIndex;
148 if (di == ROSE_OFFSET_INVALID) {
149 return;
150 }
151
152 assert(loc < 256); // ONE WHOLE BYTE!
153 DEBUG_PRINTF("storing rose delay %u in slot %u\n", loc, di);
154 u8 *leftfixDelay = getLeftfixLagTable(t, state);
155 assert(loc <= MAX_STORED_LEFTFIX_LAG);
156 leftfixDelay[di] = loc;
157}
158
159static really_inline
160void setAsZombie(const struct RoseEngine *t, char *state,
161 const struct LeftNfaInfo *left) {
162 u32 di = left->lagIndex;
163 assert(di != ROSE_OFFSET_INVALID);
164 if (di == ROSE_OFFSET_INVALID) {
165 return;
166 }
167
168 u8 *leftfixDelay = getLeftfixLagTable(t, state);
169 leftfixDelay[di] = OWB_ZOMBIE_ALWAYS_YES;
170}
171
172/* loadRoseDelay MUST NOT be called on the first stream write as it is only
173 * initialized for running nfas on stream boundaries */
174static really_inline
175u32 loadRoseDelay(const struct RoseEngine *t, const char *state,
176 const struct LeftNfaInfo *left) {
177 u32 di = left->lagIndex;
178 if (di == ROSE_OFFSET_INVALID) {
179 return 0;
180 }
181
182 const u8 *leftfixDelay = getLeftfixLagTableConst(t, state);
183 u32 loc = leftfixDelay[di];
184 DEBUG_PRINTF("read rose delay %u from slot %u\n", loc, di);
185 return loc;
186}
187
188static really_inline
189char isZombie(const struct RoseEngine *t, const char *state,
190 const struct LeftNfaInfo *left) {
191 u32 di = left->lagIndex;
192 assert(di != ROSE_OFFSET_INVALID);
193 if (di == ROSE_OFFSET_INVALID) {
194 return 0;
195 }
196
197 const u8 *leftfixDelay = getLeftfixLagTableConst(t, state);
198 DEBUG_PRINTF("read owb %hhu from slot %u\n", leftfixDelay[di], di);
199 return leftfixDelay[di] == OWB_ZOMBIE_ALWAYS_YES;
200}
201
202hwlmcb_rv_t flushQueuedLiterals_i(const struct RoseEngine *t,
203 struct hs_scratch *scratch, u64a end);
204
205static really_inline
206hwlmcb_rv_t flushQueuedLiterals(const struct RoseEngine *t,
207 struct hs_scratch *scratch, u64a end) {
208 struct RoseContext *tctxt = &scratch->tctxt;
209
210 if (tctxt->delayLastEndOffset == end) {
211 DEBUG_PRINTF("no progress, no flush\n");
212 return HWLM_CONTINUE_MATCHING;
213 }
214
215 if (!tctxt->filledDelayedSlots && !scratch->al_log_sum) {
216 tctxt->delayLastEndOffset = end;
217 return HWLM_CONTINUE_MATCHING;
218 }
219
220 return flushQueuedLiterals_i(t, scratch, end);
221}
222
223static really_inline
224hwlmcb_rv_t cleanUpDelayed(const struct RoseEngine *t,
225 struct hs_scratch *scratch, size_t length,
226 u64a offset) {
227 if (can_stop_matching(scratch)) {
228 return HWLM_TERMINATE_MATCHING;
229 }
230
231 if (flushQueuedLiterals(t, scratch, length + offset)
232 == HWLM_TERMINATE_MATCHING) {
233 return HWLM_TERMINATE_MATCHING;
234 }
235
236 struct RoseContext *tctxt = &scratch->tctxt;
237 if (tctxt->filledDelayedSlots) {
238 DEBUG_PRINTF("dirty\n");
239 scratch->core_info.status |= STATUS_DELAY_DIRTY;
240 } else {
241 scratch->core_info.status &= ~STATUS_DELAY_DIRTY;
242 }
243
244 tctxt->filledDelayedSlots = 0;
245 tctxt->delayLastEndOffset = offset;
246
247 return HWLM_CONTINUE_MATCHING;
248}
249
250static rose_inline
251void roseFlushLastByteHistory(const struct RoseEngine *t,
252 struct hs_scratch *scratch, u64a currEnd) {
253 if (!t->lastByteHistoryIterOffset) {
254 return;
255 }
256
257 struct RoseContext *tctxt = &scratch->tctxt;
258 struct core_info *ci = &scratch->core_info;
259
260 /* currEnd is last byte of string + 1 */
261 if (tctxt->lastEndOffset == ci->buf_offset + ci->len
262 || currEnd != ci->buf_offset + ci->len) {
263 /* already flushed or it is not yet time to flush */
264 return;
265 }
266
267 DEBUG_PRINTF("flushing\n");
268
269 const struct mmbit_sparse_iter *it =
270 getByOffset(t, t->lastByteHistoryIterOffset);
271 assert(ISALIGNED(it));
272
273 const u32 numStates = t->rolesWithStateCount;
274 void *role_state = getRoleState(scratch->core_info.state);
275
276 struct mmbit_sparse_state si_state[MAX_SPARSE_ITER_STATES];
277
278 mmbit_sparse_iter_unset(role_state, numStates, it, si_state);
279}
280
281static rose_inline
282int roseHasInFlightMatches(const struct RoseEngine *t, char *state,
283 const struct hs_scratch *scratch) {
284 if (scratch->al_log_sum) {
285 DEBUG_PRINTF("anchored literals in log\n");
286 return 1;
287 }
288
289 if (scratch->tctxt.filledDelayedSlots) {
290 DEBUG_PRINTF("delayed literal\n");
291 return 1;
292 }
293
294 if (mmbit_any(getRoleState(state), t->rolesWithStateCount)) {
295 DEBUG_PRINTF("role state is set\n");
296 return 1;
297 }
298
299 return 0;
300}
301
302static rose_inline
303hwlmcb_rv_t roseHaltIfExhausted(const struct RoseEngine *t,
304 struct hs_scratch *scratch) {
305 struct core_info *ci = &scratch->core_info;
306 if (isAllExhausted(t, ci->exhaustionVector)) {
307 ci->status |= STATUS_EXHAUSTED;
308 scratch->tctxt.groups = 0;
309 DEBUG_PRINTF("all exhausted, termination requested\n");
310 return HWLM_TERMINATE_MATCHING;
311 }
312
313 return HWLM_CONTINUE_MATCHING;
314}
315
316static really_inline
317hwlmcb_rv_t ensureQueueFlushed_i(const struct RoseEngine *t,
318 struct hs_scratch *scratch, u32 qi, s64a loc,
319 char is_mpv, char in_catchup) {
320 struct RoseContext *tctxt = &scratch->tctxt;
321 u8 *aa = getActiveLeafArray(t, scratch->core_info.state);
322 struct fatbit *activeQueues = scratch->aqa;
323 u32 aaCount = t->activeArrayCount;
324 u32 qCount = t->queueCount;
325
326 struct mq *q = &scratch->queues[qi];
327 DEBUG_PRINTF("qcl %lld, loc: %lld, min (non mpv) match offset: %llu\n",
328 q_cur_loc(q), loc, tctxt->minNonMpvMatchOffset);
329 if (q_cur_loc(q) == loc) {
330 /* too many tops enqueued at the one spot; need to flatten this queue.
331 * We can use the full catchups as it will short circuit as we are
332 * already at this location. It also saves waking everybody up */
333 pushQueueNoMerge(q, MQE_END, loc);
334 nfaQueueExec(q->nfa, q, loc);
335 q->cur = q->end = 0;
336 pushQueueAt(q, 0, MQE_START, loc);
337 } else if (!in_catchup) {
338 if (is_mpv) {
339 tctxt->next_mpv_offset = 0; /* force us to catch the mpv */
340 if (loc + scratch->core_info.buf_offset
341 <= tctxt->minNonMpvMatchOffset) {
342 DEBUG_PRINTF("flushing chained\n");
343 if (roseCatchUpMPV(t, loc, scratch) ==
344 HWLM_TERMINATE_MATCHING) {
345 return HWLM_TERMINATE_MATCHING;
346 }
347 goto done_queue_empty;
348 }
349 }
350
351 if (roseCatchUpTo(t, scratch, loc + scratch->core_info.buf_offset) ==
352 HWLM_TERMINATE_MATCHING) {
353 return HWLM_TERMINATE_MATCHING;
354 }
355 } else {
356 /* we must be a chained nfa */
357 assert(is_mpv);
358 DEBUG_PRINTF("flushing chained\n");
359 tctxt->next_mpv_offset = 0; /* force us to catch the mpv */
360 if (roseCatchUpMPV(t, loc, scratch) == HWLM_TERMINATE_MATCHING) {
361 return HWLM_TERMINATE_MATCHING;
362 }
363 }
364done_queue_empty:
365 if (!mmbit_set(aa, aaCount, qi)) {
366 initQueue(q, qi, t, scratch);
367 nfaQueueInitState(q->nfa, q);
368 pushQueueAt(q, 0, MQE_START, loc);
369 fatbit_set(activeQueues, qCount, qi);
370 }
371
372 assert(!isQueueFull(q));
373
374 return roseHaltIfExhausted(t, scratch);
375}
376
377static rose_inline
378hwlmcb_rv_t ensureQueueFlushed(const struct RoseEngine *t,
379 struct hs_scratch *scratch, u32 qi, s64a loc) {
380 return ensureQueueFlushed_i(t, scratch, qi, loc, 0, 0);
381}
382
383#endif
384