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 | |
41 | static rose_inline |
42 | void 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 | |
81 | static really_inline |
82 | void 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 | |
95 | static really_inline |
96 | void 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 | |
135 | static really_inline |
136 | void 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 | |
162 | static rose_inline |
163 | void 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 | */ |
193 | static rose_inline |
194 | int 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 | */ |
221 | static rose_inline |
222 | int 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 | |
265 | static rose_inline |
266 | void 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 | |
345 | void 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 | |