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#include "catchup.h"
30#include "init.h"
31#include "match.h"
32#include "program_runtime.h"
33#include "rose.h"
34#include "rose_common.h"
35#include "nfa/nfa_api.h"
36#include "nfa/nfa_internal.h"
37#include "nfa/nfa_rev_api.h"
38#include "nfa/mcclellan.h"
39#include "util/fatbit.h"
40
41static rose_inline
42void runAnchoredTableBlock(const struct RoseEngine *t, const void *atable,
43 struct hs_scratch *scratch) {
44 const u8 *buffer = scratch->core_info.buf;
45 size_t length = scratch->core_info.len;
46 size_t alen = MIN(length, t->anchoredDistance);
47 const struct anchored_matcher_info *curr = atable;
48
49 DEBUG_PRINTF("BEGIN ANCHORED (over %zu/%zu)\n", alen, length);
50
51 do {
52 const struct NFA *nfa
53 = (const struct NFA *)((const char *)curr + sizeof(*curr));
54
55 assert(t->anchoredDistance > curr->anchoredMinDistance);
56 if (length >= curr->anchoredMinDistance) {
57 size_t local_alen = alen - curr->anchoredMinDistance;
58 const u8 *local_buffer = buffer + curr->anchoredMinDistance;
59
60 DEBUG_PRINTF("--anchored nfa (+%u)\n", curr->anchoredMinDistance);
61 assert(isMcClellanType(nfa->type));
62 if (nfa->type == MCCLELLAN_NFA_8) {
63 nfaExecMcClellan8_B(nfa, curr->anchoredMinDistance,
64 local_buffer, local_alen,
65 roseAnchoredCallback, scratch);
66 } else {
67 nfaExecMcClellan16_B(nfa, curr->anchoredMinDistance,
68 local_buffer, local_alen,
69 roseAnchoredCallback, scratch);
70 }
71 }
72
73 if (!curr->next_offset) {
74 break;
75 }
76
77 curr = (const void *)((const char *)curr + curr->next_offset);
78 } while (1);
79}
80
81static really_inline
82void init_state_for_block(const struct RoseEngine *t, char *state) {
83 assert(t);
84 assert(state);
85
86 DEBUG_PRINTF("init for Rose %p with %u state indices\n", t,
87 t->rolesWithStateCount);
88
89 // Rose is guaranteed 8-aligned state
90 assert(ISALIGNED_N(state, 8));
91
92 init_state(t, state);
93}
94
95static really_inline
96void init_outfixes_for_block(const struct RoseEngine *t,
97 struct hs_scratch *scratch, char *state,
98 char is_small_block) {
99 /* active leaf array has been cleared by the init scatter */
100
101 if (t->initMpvNfa != MO_INVALID_IDX) {
102 assert(t->initMpvNfa == 0);
103 const struct NFA *nfa = getNfaByQueue(t, 0);
104 DEBUG_PRINTF("testing minwidth %u > len %zu\n", nfa->minWidth,
105 scratch->core_info.len);
106 size_t len = nfaRevAccelCheck(nfa, scratch->core_info.buf,
107 scratch->core_info.len);
108 if (len) {
109 u8 *activeArray = getActiveLeafArray(t, state);
110 const u32 activeArraySize = t->activeArrayCount;
111 const u32 qCount = t->queueCount;
112
113 mmbit_set(activeArray, activeArraySize, 0);
114 fatbit_set(scratch->aqa, qCount, 0);
115
116 struct mq *q = scratch->queues;
117 initQueue(q, 0, t, scratch);
118 q->length = len; /* adjust for rev_accel */
119 nfaQueueInitState(nfa, q);
120 pushQueueAt(q, 0, MQE_START, 0);
121 pushQueueAt(q, 1, MQE_TOP, 0);
122 }
123 }
124
125 if (is_small_block && !t->hasOutfixesInSmallBlock) {
126 DEBUG_PRINTF("all outfixes in small block table\n");
127 return;
128 }
129
130 if (t->outfixBeginQueue != t->outfixEndQueue) {
131 blockInitSufPQ(t, state, scratch, is_small_block);
132 }
133}
134
135static really_inline
136void init_for_block(const struct RoseEngine *t, struct hs_scratch *scratch,
137 char *state, char is_small_block) {
138 init_state_for_block(t, state);
139
140 struct RoseContext *tctxt = &scratch->tctxt;
141
142 tctxt->groups = t->initialGroups;
143 tctxt->lit_offset_adjust = 1; // index after last byte
144 tctxt->delayLastEndOffset = 0;
145 tctxt->lastEndOffset = 0;
146 tctxt->filledDelayedSlots = 0;
147 tctxt->lastMatchOffset = 0;
148 tctxt->lastCombMatchOffset = 0;
149 tctxt->minMatchOffset = 0;
150 tctxt->minNonMpvMatchOffset = 0;
151 tctxt->next_mpv_offset = 0;
152
153 scratch->al_log_sum = 0;
154
155 fatbit_clear(scratch->aqa);
156
157 scratch->catchup_pq.qm_size = 0;
158
159 init_outfixes_for_block(t, scratch, state, is_small_block);
160}
161
162static rose_inline
163void roseBlockEodExec(const struct RoseEngine *t, u64a offset,
164 struct hs_scratch *scratch) {
165 assert(t->requiresEodCheck);
166 assert(t->maxBiAnchoredWidth == ROSE_BOUND_INF
167 || offset <= t->maxBiAnchoredWidth);
168
169 assert(!can_stop_matching(scratch));
170 assert(t->eodProgramOffset);
171
172 // Ensure that history is correct before we look for EOD matches.
173 roseFlushLastByteHistory(t, scratch, offset);
174 scratch->tctxt.lastEndOffset = offset;
175
176 DEBUG_PRINTF("running eod program at %u\n", t->eodProgramOffset);
177
178 // There should be no pending delayed literals.
179 assert(!scratch->tctxt.filledDelayedSlots);
180
181 const u64a som = 0;
182 const u8 flags = ROSE_PROG_FLAG_SKIP_MPV_CATCHUP;
183
184 // Note: we ignore the result, as this is the last thing to ever happen on
185 // a scan.
186 roseRunProgram(t, scratch, t->eodProgramOffset, som, offset, flags);
187}
188
189/**
190 * \brief Run the anchored matcher, if any. Returns non-zero if matching should
191 * halt.
192 */
193static rose_inline
194int roseBlockAnchored(const struct RoseEngine *t, struct hs_scratch *scratch) {
195 const void *atable = getALiteralMatcher(t);
196 if (!atable) {
197 DEBUG_PRINTF("no anchored table\n");
198 return 0;
199 }
200
201 const size_t length = scratch->core_info.len;
202
203 if (t->amatcherMaxBiAnchoredWidth != ROSE_BOUND_INF &&
204 length > t->amatcherMaxBiAnchoredWidth) {
205 return 0;
206 }
207
208 if (length < t->amatcherMinWidth) {
209 return 0;
210 }
211
212 runAnchoredTableBlock(t, atable, scratch);
213
214 return can_stop_matching(scratch);
215}
216
217/**
218 * \brief Run the floating matcher, if any. Returns non-zero if matching should
219 * halt.
220 */
221static rose_inline
222int roseBlockFloating(const struct RoseEngine *t, struct hs_scratch *scratch) {
223 const struct HWLM *ftable = getFLiteralMatcher(t);
224 if (!ftable) {
225 return 0;
226 }
227
228 const size_t length = scratch->core_info.len;
229 char *state = scratch->core_info.state;
230 struct RoseContext *tctxt = &scratch->tctxt;
231
232 DEBUG_PRINTF("ftable fd=%u fmd %u\n", t->floatingDistance,
233 t->floatingMinDistance);
234 if (t->noFloatingRoots && !roseHasInFlightMatches(t, state, scratch)) {
235 DEBUG_PRINTF("skip FLOATING: no inflight matches\n");
236 return 0;
237 }
238
239 if (t->fmatcherMaxBiAnchoredWidth != ROSE_BOUND_INF &&
240 length > t->fmatcherMaxBiAnchoredWidth) {
241 return 0;
242 }
243
244 if (length < t->fmatcherMinWidth) {
245 return 0;
246 }
247
248 const u8 *buffer = scratch->core_info.buf;
249 size_t flen = length;
250 if (t->floatingDistance != ROSE_BOUND_INF) {
251 flen = MIN(t->floatingDistance, length);
252 }
253 if (flen <= t->floatingMinDistance) {
254 return 0;
255 }
256
257 DEBUG_PRINTF("BEGIN FLOATING (over %zu/%zu)\n", flen, length);
258 DEBUG_PRINTF("-- %016llx\n", tctxt->groups);
259 hwlmExec(ftable, buffer, flen, t->floatingMinDistance, roseFloatingCallback,
260 scratch, tctxt->groups & t->floating_group_mask);
261
262 return can_stop_matching(scratch);
263}
264
265static rose_inline
266void runEagerPrefixesBlock(const struct RoseEngine *t,
267 struct hs_scratch *scratch) {
268 if (!t->eagerIterOffset) {
269 return;
270 }
271
272 char *state = scratch->core_info.state;
273 u8 *ara = getActiveLeftArray(t, state); /* indexed by offsets into
274 * left_table */
275 const u32 arCount = t->activeLeftCount;
276 const u32 qCount = t->queueCount;
277 const struct LeftNfaInfo *left_table = getLeftTable(t);
278 const struct mmbit_sparse_iter *it = getByOffset(t, t->eagerIterOffset);
279
280 struct mmbit_sparse_state si_state[MAX_SPARSE_ITER_STATES];
281
282 u32 idx = 0;
283 u32 ri = mmbit_sparse_iter_begin(ara, arCount, &idx, it, si_state);
284 for (; ri != MMB_INVALID;
285 ri = mmbit_sparse_iter_next(ara, arCount, ri, &idx, it, si_state)) {
286 const struct LeftNfaInfo *left = left_table + ri;
287 u32 qi = ri + t->leftfixBeginQueue;
288 DEBUG_PRINTF("leftfix %u/%u, maxLag=%u\n", ri, arCount, left->maxLag);
289
290 assert(!fatbit_isset(scratch->aqa, qCount, qi));
291 assert(left->eager);
292 assert(!left->infix);
293
294 struct mq *q = scratch->queues + qi;
295 const struct NFA *nfa = getNfaByQueue(t, qi);
296
297 if (scratch->core_info.len < nfa->minWidth) {
298 /* we know that there is not enough data for this to ever match, so
299 * we can immediately squash/ */
300 mmbit_unset(ara, arCount, ri);
301 scratch->tctxt.groups &= left->squash_mask;
302 }
303
304 s64a loc = MIN(scratch->core_info.len, EAGER_STOP_OFFSET);
305
306 fatbit_set(scratch->aqa, qCount, qi);
307 initRoseQueue(t, qi, left, scratch);
308
309 pushQueueAt(q, 0, MQE_START, 0);
310 pushQueueAt(q, 1, MQE_TOP, 0);
311 pushQueueAt(q, 2, MQE_END, loc);
312 nfaQueueInitState(nfa, q);
313
314 char alive = nfaQueueExecToMatch(q->nfa, q, loc);
315
316 if (!alive) {
317 DEBUG_PRINTF("queue %u dead, squashing\n", qi);
318 mmbit_unset(ara, arCount, ri);
319 fatbit_unset(scratch->aqa, qCount, qi);
320 scratch->tctxt.groups &= left->squash_mask;
321 } else if (q->cur == q->end) {
322 assert(alive != MO_MATCHES_PENDING);
323 if (loc == (s64a)scratch->core_info.len) {
324 /* We know that the prefix does not match in the block so we
325 * can squash the groups anyway even though it did not die */
326 /* TODO: if we knew the minimum lag the leftfix is checked at we
327 * could make this check tighter */
328 DEBUG_PRINTF("queue %u has no match in block, squashing\n", qi);
329 mmbit_unset(ara, arCount, ri);
330 fatbit_unset(scratch->aqa, qCount, qi);
331 scratch->tctxt.groups &= left->squash_mask;
332 } else {
333 DEBUG_PRINTF("queue %u finished, nfa lives\n", qi);
334 q->cur = q->end = 0;
335 pushQueueAt(q, 0, MQE_START, loc);
336 }
337 } else {
338 assert(alive == MO_MATCHES_PENDING);
339 DEBUG_PRINTF("queue %u unfinished, nfa lives\n", qi);
340 q->end--; /* remove end item */
341 }
342 }
343}
344
345void roseBlockExec(const struct RoseEngine *t, struct hs_scratch *scratch) {
346 assert(t);
347 assert(scratch);
348 assert(scratch->core_info.buf);
349 assert(mmbit_sparse_iter_state_size(t->rolesWithStateCount)
350 < MAX_SPARSE_ITER_STATES);
351
352 // We should not have been called if we've already been told to terminate
353 // matching.
354 assert(!told_to_stop_matching(scratch));
355
356 // If this block is shorter than our minimum width, then no pattern in this
357 // RoseEngine could match.
358 /* minWidth checks should have already been performed by the caller */
359 assert(scratch->core_info.len >= t->minWidth);
360
361 // Similarly, we may have a maximum width (for engines constructed entirely
362 // of bi-anchored patterns).
363 /* This check is now handled by the interpreter */
364 assert(t->maxBiAnchoredWidth == ROSE_BOUND_INF
365 || scratch->core_info.len <= t->maxBiAnchoredWidth);
366
367 const size_t length = scratch->core_info.len;
368
369 // We have optimizations for small block scans: we run a single coalesced
370 // HWLM scan instead of running the anchored and floating matchers. Some
371 // outfixes are disabled as well (for SEP scans of single-byte literals,
372 // which are also run in the HWLM scan).
373 const char is_small_block =
374 (length < ROSE_SMALL_BLOCK_LEN && t->sbmatcherOffset);
375
376 char *state = scratch->core_info.state;
377
378 init_for_block(t, scratch, state, is_small_block);
379
380 struct RoseContext *tctxt = &scratch->tctxt;
381
382 if (is_small_block) {
383 const void *sbtable = getSBLiteralMatcher(t);
384 assert(sbtable);
385
386 size_t sblen = MIN(length, t->smallBlockDistance);
387
388 DEBUG_PRINTF("BEGIN SMALL BLOCK (over %zu/%zu)\n", sblen, length);
389 DEBUG_PRINTF("-- %016llx\n", tctxt->groups);
390 hwlmExec(sbtable, scratch->core_info.buf, sblen, 0, roseCallback,
391 scratch, tctxt->groups);
392 } else {
393 runEagerPrefixesBlock(t, scratch);
394
395 if (roseBlockAnchored(t, scratch)) {
396 return;
397 }
398 if (roseBlockFloating(t, scratch)) {
399 return;
400 }
401 }
402
403 if (cleanUpDelayed(t, scratch, length, 0) == HWLM_TERMINATE_MATCHING) {
404 return;
405 }
406
407 assert(!can_stop_matching(scratch));
408
409 roseCatchUpTo(t, scratch, length);
410
411 if (!t->requiresEodCheck || !t->eodProgramOffset) {
412 DEBUG_PRINTF("no eod check required\n");
413 return;
414 }
415
416 if (can_stop_matching(scratch)) {
417 DEBUG_PRINTF("bailing, already halted\n");
418 return;
419 }
420
421 roseBlockEodExec(t, length, scratch);
422}
423