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 "counting_miracle.h" |
31 | #include "infix.h" |
32 | #include "match.h" |
33 | #include "miracle.h" |
34 | #include "program_runtime.h" |
35 | #include "rose.h" |
36 | #include "rose_internal.h" |
37 | #include "stream_long_lit.h" |
38 | #include "hwlm/hwlm.h" |
39 | #include "nfa/mcclellan.h" |
40 | #include "nfa/nfa_api.h" |
41 | #include "nfa/nfa_api_queue.h" |
42 | #include "nfa/nfa_internal.h" |
43 | #include "util/fatbit.h" |
44 | |
45 | static rose_inline |
46 | void runAnchoredTableStream(const struct RoseEngine *t, const void *atable, |
47 | size_t alen, u64a offset, |
48 | struct hs_scratch *scratch) { |
49 | char *state_base = scratch->core_info.state + t->stateOffsets.anchorState; |
50 | const struct anchored_matcher_info *curr = atable; |
51 | |
52 | do { |
53 | DEBUG_PRINTF("--anchored nfa (+%u) no %u so %u\n" , |
54 | curr->anchoredMinDistance, curr->next_offset, |
55 | curr->state_offset); |
56 | const struct NFA *nfa |
57 | = (const struct NFA *)((const char *)curr + sizeof(*curr)); |
58 | assert(ISALIGNED_CL(nfa)); |
59 | assert(isMcClellanType(nfa->type)); |
60 | |
61 | char *state = state_base + curr->state_offset; |
62 | |
63 | char start = 0; |
64 | size_t adj = 0; |
65 | |
66 | if (offset <= curr->anchoredMinDistance) { |
67 | adj = curr->anchoredMinDistance - offset; |
68 | if (adj >= alen) { |
69 | goto next_nfa; |
70 | } |
71 | |
72 | start = 1; |
73 | } else { |
74 | // (No state decompress necessary.) |
75 | if (nfa->type == MCCLELLAN_NFA_8) { |
76 | if (!*(u8 *)state) { |
77 | goto next_nfa; |
78 | } |
79 | } else { |
80 | if (!unaligned_load_u16(state)) { |
81 | goto next_nfa; |
82 | } |
83 | } |
84 | } |
85 | |
86 | if (nfa->type == MCCLELLAN_NFA_8) { |
87 | nfaExecMcClellan8_SimpStream(nfa, state, scratch->core_info.buf, |
88 | start, adj, alen, roseAnchoredCallback, |
89 | scratch); |
90 | } else { |
91 | nfaExecMcClellan16_SimpStream(nfa, state, scratch->core_info.buf, |
92 | start, adj, alen, |
93 | roseAnchoredCallback, scratch); |
94 | } |
95 | |
96 | next_nfa: |
97 | if (!curr->next_offset) { |
98 | break; |
99 | } |
100 | |
101 | curr = (const void *)((const char *)curr + curr->next_offset); |
102 | } while (1); |
103 | } |
104 | |
105 | |
106 | static really_inline |
107 | void saveStreamState(const struct NFA *nfa, struct mq *q, s64a loc) { |
108 | DEBUG_PRINTF("offset=%llu, length=%zu, hlength=%zu, loc=%lld\n" , |
109 | q->offset, q->length, q->hlength, loc); |
110 | nfaQueueCompressState(nfa, q, loc); |
111 | } |
112 | |
113 | static really_inline |
114 | u8 getByteBefore(const struct core_info *ci, s64a sp) { |
115 | if (sp > 0) { // in main buffer |
116 | assert(sp <= (s64a)ci->len); |
117 | return ci->buf[sp - 1]; |
118 | } |
119 | // in history buffer |
120 | assert(-sp < (s64a)ci->hlen); |
121 | return ci->hbuf[ci->hlen + sp - 1]; |
122 | } |
123 | |
124 | /** \brief Return value for \ref roseScanForMiracles. */ |
125 | enum MiracleAction { |
126 | MIRACLE_DEAD, //!< kill off this engine |
127 | MIRACLE_SAVED, //!< engine has been caught up and state saved |
128 | MIRACLE_CONTINUE //!< continue running and catch up engine |
129 | }; |
130 | |
131 | static really_inline |
132 | enum MiracleAction roseScanForMiracles(const struct RoseEngine *t, char *state, |
133 | struct hs_scratch *scratch, u32 qi, |
134 | const struct LeftNfaInfo *left, |
135 | const struct NFA *nfa) { |
136 | struct core_info *ci = &scratch->core_info; |
137 | const u32 qCount = t->queueCount; |
138 | struct mq *q = scratch->queues + qi; |
139 | |
140 | const char q_active = fatbit_isset(scratch->aqa, qCount, qi); |
141 | DEBUG_PRINTF("q_active=%d\n" , q_active); |
142 | |
143 | const s64a begin_loc = q_active ? q_cur_loc(q) : 0; |
144 | const s64a end_loc = ci->len; |
145 | |
146 | s64a miracle_loc; |
147 | if (roseMiracleOccurs(t, left, ci, begin_loc, end_loc, &miracle_loc)) { |
148 | goto found_miracle; |
149 | } |
150 | |
151 | if (roseCountingMiracleOccurs(t, left, ci, begin_loc, end_loc, |
152 | &miracle_loc)) { |
153 | goto found_miracle; |
154 | } |
155 | |
156 | DEBUG_PRINTF("no miracle\n" ); |
157 | return MIRACLE_CONTINUE; |
158 | |
159 | found_miracle: |
160 | DEBUG_PRINTF("miracle at %lld\n" , miracle_loc); |
161 | |
162 | if (left->infix) { |
163 | if (!q_active) { |
164 | DEBUG_PRINTF("killing infix\n" ); |
165 | return MIRACLE_DEAD; |
166 | } |
167 | |
168 | DEBUG_PRINTF("skip q forward, %lld to %lld\n" , begin_loc, miracle_loc); |
169 | q_skip_forward_to(q, miracle_loc); |
170 | if (q_last_type(q) == MQE_START) { |
171 | DEBUG_PRINTF("miracle caused infix to die\n" ); |
172 | return MIRACLE_DEAD; |
173 | } |
174 | |
175 | DEBUG_PRINTF("re-init infix state\n" ); |
176 | assert(q->items[q->cur].type == MQE_START); |
177 | q->items[q->cur].location = miracle_loc; |
178 | nfaQueueInitState(q->nfa, q); |
179 | } else { |
180 | if (miracle_loc > end_loc - t->historyRequired) { |
181 | char *streamState = state + getNfaInfoByQueue(t, qi)->stateOffset; |
182 | u64a offset = ci->buf_offset + miracle_loc; |
183 | u8 key = offset ? getByteBefore(ci, miracle_loc) : 0; |
184 | DEBUG_PRINTF("init state, key=0x%02x, offset=%llu\n" , key, offset); |
185 | if (!nfaInitCompressedState(nfa, offset, streamState, key)) { |
186 | return MIRACLE_DEAD; |
187 | } |
188 | storeRoseDelay(t, state, left, (s64a)ci->len - miracle_loc); |
189 | return MIRACLE_SAVED; |
190 | } |
191 | |
192 | DEBUG_PRINTF("re-init prefix (skip %lld->%lld)\n" , begin_loc, |
193 | miracle_loc); |
194 | if (!q_active) { |
195 | fatbit_set(scratch->aqa, qCount, qi); |
196 | initRoseQueue(t, qi, left, scratch); |
197 | } |
198 | q->cur = q->end = 0; |
199 | pushQueueAt(q, 0, MQE_START, miracle_loc); |
200 | pushQueueAt(q, 1, MQE_TOP, miracle_loc); |
201 | nfaQueueInitState(q->nfa, q); |
202 | } |
203 | |
204 | return MIRACLE_CONTINUE; |
205 | } |
206 | |
207 | |
208 | static really_inline |
209 | char roseCatchUpLeftfix(const struct RoseEngine *t, char *state, |
210 | struct hs_scratch *scratch, u32 qi, |
211 | const struct LeftNfaInfo *left) { |
212 | assert(!left->transient); // active roses only |
213 | |
214 | struct core_info *ci = &scratch->core_info; |
215 | const u32 qCount = t->queueCount; |
216 | struct mq *q = scratch->queues + qi; |
217 | const struct NFA *nfa = getNfaByQueue(t, qi); |
218 | |
219 | if (nfaSupportsZombie(nfa) |
220 | && ci->buf_offset /* prefix can be alive with no q */ |
221 | && !fatbit_isset(scratch->aqa, qCount, qi) |
222 | && isZombie(t, state, left)) { |
223 | DEBUG_PRINTF("yawn - zombie\n" ); |
224 | return 1; |
225 | } |
226 | |
227 | if (left->stopTable) { |
228 | enum MiracleAction mrv = |
229 | roseScanForMiracles(t, state, scratch, qi, left, nfa); |
230 | switch (mrv) { |
231 | case MIRACLE_DEAD: |
232 | return 0; |
233 | case MIRACLE_SAVED: |
234 | return 1; |
235 | default: |
236 | assert(mrv == MIRACLE_CONTINUE); |
237 | break; |
238 | } |
239 | } |
240 | |
241 | if (!fatbit_set(scratch->aqa, qCount, qi)) { |
242 | initRoseQueue(t, qi, left, scratch); |
243 | |
244 | s32 sp; |
245 | if (ci->buf_offset) { |
246 | sp = -(s32)loadRoseDelay(t, state, left); |
247 | } else { |
248 | sp = 0; |
249 | } |
250 | |
251 | DEBUG_PRINTF("ci->len=%zu, sp=%d, historyRequired=%u\n" , ci->len, sp, |
252 | t->historyRequired); |
253 | |
254 | if ( ci->len - sp + 1 < t->historyRequired) { |
255 | // we'll end up safely in the history region. |
256 | DEBUG_PRINTF("safely in history, skipping\n" ); |
257 | storeRoseDelay(t, state, left, (s64a)ci->len - sp); |
258 | return 1; |
259 | } |
260 | |
261 | pushQueueAt(q, 0, MQE_START, sp); |
262 | if (left->infix || ci->buf_offset + sp > 0) { |
263 | loadStreamState(nfa, q, sp); |
264 | } else { |
265 | pushQueueAt(q, 1, MQE_TOP, sp); |
266 | nfaQueueInitState(nfa, q); |
267 | } |
268 | } else { |
269 | DEBUG_PRINTF("queue already active\n" ); |
270 | if (q->end - q->cur == 1 && q_cur_type(q) == MQE_START) { |
271 | DEBUG_PRINTF("empty queue, start loc=%lld\n" , q_cur_loc(q)); |
272 | s64a last_loc = q_cur_loc(q); |
273 | if (ci->len - last_loc + 1 < t->historyRequired) { |
274 | // we'll end up safely in the history region. |
275 | DEBUG_PRINTF("safely in history, saving state and skipping\n" ); |
276 | saveStreamState(nfa, q, last_loc); |
277 | storeRoseDelay(t, state, left, (s64a)ci->len - last_loc); |
278 | return 1; |
279 | } |
280 | } |
281 | } |
282 | |
283 | // Determine whether the byte before last_loc will be in the history |
284 | // buffer on the next stream write. |
285 | s64a last_loc = q_last_loc(q); |
286 | s64a leftovers = ci->len - last_loc; |
287 | if (leftovers + 1 >= t->historyRequired) { |
288 | u32 catchup_offset = left->maxLag ? left->maxLag - 1 : 0; |
289 | last_loc = (s64a)ci->len - catchup_offset; |
290 | } |
291 | |
292 | if (left->infix) { |
293 | if (infixTooOld(q, last_loc)) { |
294 | DEBUG_PRINTF("infix died of old age\n" ); |
295 | return 0; |
296 | } |
297 | reduceInfixQueue(q, last_loc, left->maxQueueLen, q->nfa->maxWidth); |
298 | } |
299 | |
300 | DEBUG_PRINTF("end scan at %lld\n" , last_loc); |
301 | pushQueueNoMerge(q, MQE_END, last_loc); |
302 | |
303 | #ifdef DEBUG |
304 | debugQueue(q); |
305 | #endif |
306 | |
307 | char rv = nfaQueueExecRose(nfa, q, MO_INVALID_IDX); |
308 | if (!rv) { /* nfa is dead */ |
309 | DEBUG_PRINTF("died catching up to stream boundary\n" ); |
310 | return 0; |
311 | } else { |
312 | DEBUG_PRINTF("alive, saving stream state\n" ); |
313 | if (nfaSupportsZombie(nfa) && |
314 | nfaGetZombieStatus(nfa, q, last_loc) == NFA_ZOMBIE_ALWAYS_YES) { |
315 | DEBUG_PRINTF("not so fast - zombie\n" ); |
316 | setAsZombie(t, state, left); |
317 | } else { |
318 | saveStreamState(nfa, q, last_loc); |
319 | storeRoseDelay(t, state, left, (s64a)ci->len - last_loc); |
320 | } |
321 | } |
322 | |
323 | return 1; |
324 | } |
325 | |
326 | static rose_inline |
327 | void roseCatchUpLeftfixes(const struct RoseEngine *t, char *state, |
328 | struct hs_scratch *scratch) { |
329 | if (!t->activeLeftIterOffset) { |
330 | // No sparse iter, no non-transient roses. |
331 | return; |
332 | } |
333 | |
334 | // As per UE-1629, we catch up leftfix engines to: |
335 | // * current position (last location in the queue, or last location we |
336 | // executed to if the queue is empty) if that position (and the byte |
337 | // before so we can decompress the stream state) will be in the history |
338 | // buffer on the next stream write; OR |
339 | // * (stream_boundary - max_delay) other |
340 | |
341 | u8 *ara = getActiveLeftArray(t, state); /* indexed by offsets into |
342 | * left_table */ |
343 | const u32 arCount = t->activeLeftCount; |
344 | const struct LeftNfaInfo *left_table = getLeftTable(t); |
345 | const struct mmbit_sparse_iter *it = getActiveLeftIter(t); |
346 | |
347 | struct mmbit_sparse_state si_state[MAX_SPARSE_ITER_STATES]; |
348 | |
349 | u32 idx = 0; |
350 | u32 ri = mmbit_sparse_iter_begin(ara, arCount, &idx, it, si_state); |
351 | for (; ri != MMB_INVALID; |
352 | ri = mmbit_sparse_iter_next(ara, arCount, ri, &idx, it, si_state)) { |
353 | const struct LeftNfaInfo *left = left_table + ri; |
354 | u32 qi = ri + t->leftfixBeginQueue; |
355 | DEBUG_PRINTF("leftfix %u of %u, maxLag=%u, infix=%d\n" , ri, arCount, |
356 | left->maxLag, (int)left->infix); |
357 | if (!roseCatchUpLeftfix(t, state, scratch, qi, left)) { |
358 | DEBUG_PRINTF("removing rose %u from active list\n" , ri); |
359 | DEBUG_PRINTF("groups old=%016llx mask=%016llx\n" , |
360 | scratch->tctxt.groups, left->squash_mask); |
361 | scratch->tctxt.groups &= left->squash_mask; |
362 | mmbit_unset(ara, arCount, ri); |
363 | } |
364 | } |
365 | } |
366 | |
367 | // Saves out stream state for all our active suffix NFAs. |
368 | static rose_inline |
369 | void roseSaveNfaStreamState(const struct RoseEngine *t, char *state, |
370 | struct hs_scratch *scratch) { |
371 | struct mq *queues = scratch->queues; |
372 | u8 *aa = getActiveLeafArray(t, state); |
373 | u32 aaCount = t->activeArrayCount; |
374 | |
375 | if (scratch->tctxt.mpv_inactive) { |
376 | DEBUG_PRINTF("mpv is dead as a doornail\n" ); |
377 | /* mpv if it exists is queue 0 */ |
378 | mmbit_unset(aa, aaCount, 0); |
379 | } |
380 | |
381 | for (u32 qi = mmbit_iterate(aa, aaCount, MMB_INVALID); qi != MMB_INVALID; |
382 | qi = mmbit_iterate(aa, aaCount, qi)) { |
383 | DEBUG_PRINTF("saving stream state for qi=%u\n" , qi); |
384 | |
385 | struct mq *q = queues + qi; |
386 | |
387 | // If it's active, it should have an active queue (as we should have |
388 | // done some work!) |
389 | assert(fatbit_isset(scratch->aqa, t->queueCount, qi)); |
390 | |
391 | const struct NFA *nfa = getNfaByQueue(t, qi); |
392 | saveStreamState(nfa, q, q_cur_loc(q)); |
393 | } |
394 | } |
395 | |
396 | static rose_inline |
397 | void ensureStreamNeatAndTidy(const struct RoseEngine *t, char *state, |
398 | struct hs_scratch *scratch, size_t length, |
399 | u64a offset) { |
400 | struct RoseContext *tctxt = &scratch->tctxt; |
401 | |
402 | if (roseCatchUpTo(t, scratch, length + scratch->core_info.buf_offset) == |
403 | HWLM_TERMINATE_MATCHING) { |
404 | return; /* dead; no need to clean up state. */ |
405 | } |
406 | roseSaveNfaStreamState(t, state, scratch); |
407 | roseCatchUpLeftfixes(t, state, scratch); |
408 | roseFlushLastByteHistory(t, scratch, offset + length); |
409 | tctxt->lastEndOffset = offset + length; |
410 | storeGroups(t, state, tctxt->groups); |
411 | storeLongLiteralState(t, state, scratch); |
412 | } |
413 | |
414 | static really_inline |
415 | void do_rebuild(const struct RoseEngine *t, struct hs_scratch *scratch) { |
416 | assert(t->drmatcherOffset); |
417 | assert(!can_stop_matching(scratch)); |
418 | |
419 | const struct HWLM *hwlm = getByOffset(t, t->drmatcherOffset); |
420 | size_t len = MIN(scratch->core_info.hlen, t->delayRebuildLength); |
421 | const u8 *buf = scratch->core_info.hbuf + scratch->core_info.hlen - len; |
422 | DEBUG_PRINTF("BEGIN FLOATING REBUILD over %zu bytes\n" , len); |
423 | |
424 | scratch->core_info.status &= ~STATUS_DELAY_DIRTY; |
425 | |
426 | hwlmExec(hwlm, buf, len, 0, roseDelayRebuildCallback, scratch, |
427 | scratch->tctxt.groups); |
428 | assert(!can_stop_matching(scratch)); |
429 | } |
430 | |
431 | static rose_inline |
432 | void runEagerPrefixesStream(const struct RoseEngine *t, |
433 | struct hs_scratch *scratch) { |
434 | if (!t->eagerIterOffset |
435 | || scratch->core_info.buf_offset >= EAGER_STOP_OFFSET) { |
436 | return; |
437 | } |
438 | |
439 | char *state = scratch->core_info.state; |
440 | u8 *ara = getActiveLeftArray(t, state); /* indexed by offsets into |
441 | * left_table */ |
442 | const u32 arCount = t->activeLeftCount; |
443 | const u32 qCount = t->queueCount; |
444 | const struct LeftNfaInfo *left_table = getLeftTable(t); |
445 | const struct mmbit_sparse_iter *it = getByOffset(t, t->eagerIterOffset); |
446 | |
447 | struct mmbit_sparse_state si_state[MAX_SPARSE_ITER_STATES]; |
448 | |
449 | u32 idx = 0; |
450 | u32 ri = mmbit_sparse_iter_begin(ara, arCount, &idx, it, si_state); |
451 | for (; ri != MMB_INVALID; |
452 | ri = mmbit_sparse_iter_next(ara, arCount, ri, &idx, it, si_state)) { |
453 | const struct LeftNfaInfo *left = left_table + ri; |
454 | u32 qi = ri + t->leftfixBeginQueue; |
455 | DEBUG_PRINTF("leftfix %u of %u, maxLag=%u\n" , ri, arCount, left->maxLag); |
456 | |
457 | assert(!fatbit_isset(scratch->aqa, qCount, qi)); |
458 | assert(left->eager); |
459 | assert(!left->infix); |
460 | |
461 | struct mq *q = scratch->queues + qi; |
462 | const struct NFA *nfa = getNfaByQueue(t, qi); |
463 | s64a loc = MIN(scratch->core_info.len, |
464 | EAGER_STOP_OFFSET - scratch->core_info.buf_offset); |
465 | |
466 | fatbit_set(scratch->aqa, qCount, qi); |
467 | initRoseQueue(t, qi, left, scratch); |
468 | |
469 | if (scratch->core_info.buf_offset) { |
470 | s64a sp = left->transient ? -(s64a)scratch->core_info.hlen |
471 | : -(s64a)loadRoseDelay(t, state, left); |
472 | pushQueueAt(q, 0, MQE_START, sp); |
473 | if (scratch->core_info.buf_offset + sp > 0) { |
474 | loadStreamState(nfa, q, sp); |
475 | /* if the leftfix fix is currently in a match state, we cannot |
476 | * advance it. */ |
477 | if (nfaInAnyAcceptState(nfa, q)) { |
478 | continue; |
479 | } |
480 | pushQueueAt(q, 1, MQE_END, loc); |
481 | } else { |
482 | pushQueueAt(q, 1, MQE_TOP, sp); |
483 | pushQueueAt(q, 2, MQE_END, loc); |
484 | nfaQueueInitState(q->nfa, q); |
485 | } |
486 | } else { |
487 | pushQueueAt(q, 0, MQE_START, 0); |
488 | pushQueueAt(q, 1, MQE_TOP, 0); |
489 | pushQueueAt(q, 2, MQE_END, loc); |
490 | nfaQueueInitState(nfa, q); |
491 | } |
492 | |
493 | char alive = nfaQueueExecToMatch(q->nfa, q, loc); |
494 | |
495 | if (!alive) { |
496 | DEBUG_PRINTF("queue %u dead, squashing\n" , qi); |
497 | mmbit_unset(ara, arCount, ri); |
498 | fatbit_unset(scratch->aqa, qCount, qi); |
499 | scratch->tctxt.groups &= left->squash_mask; |
500 | } else if (q->cur == q->end) { |
501 | assert(alive != MO_MATCHES_PENDING); |
502 | /* unlike in block mode we cannot squash groups if there is no match |
503 | * in this block as we need the groups on for later stream writes */ |
504 | /* TODO: investigate possibility of a method to suppress groups for |
505 | * a single stream block. */ |
506 | DEBUG_PRINTF("queue %u finished, nfa lives\n" , qi); |
507 | q->cur = q->end = 0; |
508 | pushQueueAt(q, 0, MQE_START, loc); |
509 | } else { |
510 | assert(alive == MO_MATCHES_PENDING); |
511 | DEBUG_PRINTF("queue %u unfinished, nfa lives\n" , qi); |
512 | q->end--; /* remove end item */ |
513 | } |
514 | } |
515 | } |
516 | |
517 | static really_inline |
518 | int can_never_match(const struct RoseEngine *t, char *state, |
519 | struct hs_scratch *scratch, size_t length, u64a offset) { |
520 | struct RoseContext *tctxt = &scratch->tctxt; |
521 | |
522 | if (tctxt->groups) { |
523 | DEBUG_PRINTF("still has active groups\n" ); |
524 | return 0; |
525 | } |
526 | |
527 | if (offset + length <= t->anchoredDistance) { /* not < as may have eod */ |
528 | DEBUG_PRINTF("still in anchored region\n" ); |
529 | return 0; |
530 | } |
531 | |
532 | if (t->lastByteHistoryIterOffset) { /* last byte history is hard */ |
533 | DEBUG_PRINTF("last byte history\n" ); |
534 | return 0; |
535 | } |
536 | |
537 | if (mmbit_any(getActiveLeafArray(t, state), t->activeArrayCount)) { |
538 | DEBUG_PRINTF("active leaf\n" ); |
539 | return 0; |
540 | } |
541 | |
542 | return 1; |
543 | } |
544 | |
545 | void roseStreamExec(const struct RoseEngine *t, struct hs_scratch *scratch) { |
546 | DEBUG_PRINTF("OH HAI [%llu, %llu)\n" , scratch->core_info.buf_offset, |
547 | scratch->core_info.buf_offset + (u64a)scratch->core_info.len); |
548 | assert(t); |
549 | assert(scratch->core_info.hbuf); |
550 | assert(scratch->core_info.buf); |
551 | |
552 | // We should not have been called if we've already been told to terminate |
553 | // matching. |
554 | assert(!told_to_stop_matching(scratch)); |
555 | |
556 | assert(mmbit_sparse_iter_state_size(t->rolesWithStateCount) |
557 | < MAX_SPARSE_ITER_STATES); |
558 | |
559 | size_t length = scratch->core_info.len; |
560 | u64a offset = scratch->core_info.buf_offset; |
561 | |
562 | // We may have a maximum width (for engines constructed entirely |
563 | // of bi-anchored patterns). If this write would result in us progressing |
564 | // beyond this point, we cannot possibly match. |
565 | if (t->maxBiAnchoredWidth != ROSE_BOUND_INF |
566 | && offset + length > t->maxBiAnchoredWidth) { |
567 | DEBUG_PRINTF("bailing, write would progress beyond maxBAWidth\n" ); |
568 | return; |
569 | } |
570 | |
571 | char *state = scratch->core_info.state; |
572 | |
573 | struct RoseContext *tctxt = &scratch->tctxt; |
574 | tctxt->mpv_inactive = 0; |
575 | tctxt->groups = loadGroups(t, state); |
576 | tctxt->lit_offset_adjust = offset + 1; // index after last byte |
577 | tctxt->delayLastEndOffset = offset; |
578 | tctxt->lastEndOffset = offset; |
579 | tctxt->filledDelayedSlots = 0; |
580 | tctxt->lastMatchOffset = 0; |
581 | tctxt->lastCombMatchOffset = offset; |
582 | tctxt->minMatchOffset = offset; |
583 | tctxt->minNonMpvMatchOffset = offset; |
584 | tctxt->next_mpv_offset = 0; |
585 | |
586 | DEBUG_PRINTF("BEGIN: history len=%zu, buffer len=%zu groups=%016llx\n" , |
587 | scratch->core_info.hlen, scratch->core_info.len, tctxt->groups); |
588 | |
589 | fatbit_clear(scratch->aqa); |
590 | scratch->al_log_sum = 0; |
591 | scratch->catchup_pq.qm_size = 0; |
592 | |
593 | if (t->outfixBeginQueue != t->outfixEndQueue) { |
594 | streamInitSufPQ(t, state, scratch); |
595 | } |
596 | |
597 | runEagerPrefixesStream(t, scratch); |
598 | |
599 | u32 alen = t->anchoredDistance > offset ? |
600 | MIN(length + offset, t->anchoredDistance) - offset : 0; |
601 | |
602 | const struct anchored_matcher_info *atable = getALiteralMatcher(t); |
603 | if (atable && alen) { |
604 | DEBUG_PRINTF("BEGIN ANCHORED %zu/%u\n" , scratch->core_info.hlen, alen); |
605 | runAnchoredTableStream(t, atable, alen, offset, scratch); |
606 | |
607 | if (can_stop_matching(scratch)) { |
608 | goto exit; |
609 | } |
610 | } |
611 | |
612 | const struct HWLM *ftable = getFLiteralMatcher(t); |
613 | if (ftable) { |
614 | // Load in long literal table state and set up "fake history" buffers |
615 | // (ll_buf, etc, used by the CHECK_LONG_LIT instruction). Note that this |
616 | // must be done here in order to ensure that it happens before any path |
617 | // that leads to storeLongLiteralState(), which relies on these buffers. |
618 | loadLongLiteralState(t, state, scratch); |
619 | |
620 | if (t->noFloatingRoots && !roseHasInFlightMatches(t, state, scratch)) { |
621 | DEBUG_PRINTF("skip FLOATING: no inflight matches\n" ); |
622 | goto flush_delay_and_exit; |
623 | } |
624 | |
625 | size_t flen = length; |
626 | if (t->floatingDistance != ROSE_BOUND_INF) { |
627 | flen = t->floatingDistance > offset ? |
628 | MIN(t->floatingDistance, length + offset) - offset : 0; |
629 | } |
630 | |
631 | size_t hlength = scratch->core_info.hlen; |
632 | |
633 | char rebuild = hlength && |
634 | (scratch->core_info.status & STATUS_DELAY_DIRTY) && |
635 | (t->maxFloatingDelayedMatch == ROSE_BOUND_INF || |
636 | offset < t->maxFloatingDelayedMatch); |
637 | DEBUG_PRINTF("**rebuild %hhd status %hhu mfdm %u, offset %llu\n" , |
638 | rebuild, scratch->core_info.status, |
639 | t->maxFloatingDelayedMatch, offset); |
640 | |
641 | if (rebuild) { /* rebuild floating delayed match stuff */ |
642 | do_rebuild(t, scratch); |
643 | } |
644 | |
645 | if (!flen) { |
646 | goto flush_delay_and_exit; |
647 | } |
648 | |
649 | if (flen + offset <= t->floatingMinDistance) { |
650 | DEBUG_PRINTF("skip FLOATING: before floating min\n" ); |
651 | goto flush_delay_and_exit; |
652 | } |
653 | |
654 | size_t start = 0; |
655 | if (offset < t->floatingMinDistance) { |
656 | // This scan crosses the floating min distance, so we can use that |
657 | // to set HWLM's "start" offset. |
658 | start = t->floatingMinDistance - offset; |
659 | } |
660 | DEBUG_PRINTF("start=%zu\n" , start); |
661 | |
662 | DEBUG_PRINTF("BEGIN FLOATING (over %zu/%zu)\n" , flen, length); |
663 | hwlmExecStreaming(ftable, flen, start, roseFloatingCallback, scratch, |
664 | tctxt->groups & t->floating_group_mask); |
665 | } |
666 | |
667 | flush_delay_and_exit: |
668 | DEBUG_PRINTF("flushing floating\n" ); |
669 | if (cleanUpDelayed(t, scratch, length, offset) == HWLM_TERMINATE_MATCHING) { |
670 | return; |
671 | } |
672 | |
673 | exit: |
674 | DEBUG_PRINTF("CLEAN UP TIME\n" ); |
675 | if (!can_stop_matching(scratch)) { |
676 | ensureStreamNeatAndTidy(t, state, scratch, length, offset); |
677 | } |
678 | |
679 | if (!told_to_stop_matching(scratch) |
680 | && can_never_match(t, state, scratch, length, offset)) { |
681 | DEBUG_PRINTF("PATTERN SET IS EXHAUSTED\n" ); |
682 | scratch->core_info.status = STATUS_EXHAUSTED; |
683 | return; |
684 | } |
685 | |
686 | DEBUG_PRINTF("DONE STREAMING SCAN, status = %u\n" , |
687 | scratch->core_info.status); |
688 | return; |
689 | } |
690 | |
691 | static rose_inline |
692 | void roseStreamInitEod(const struct RoseEngine *t, u64a offset, |
693 | struct hs_scratch *scratch) { |
694 | struct RoseContext *tctxt = &scratch->tctxt; |
695 | /* TODO: diff groups for eod */ |
696 | tctxt->groups = loadGroups(t, scratch->core_info.state); |
697 | tctxt->lit_offset_adjust = scratch->core_info.buf_offset |
698 | - scratch->core_info.hlen |
699 | + 1; // index after last byte |
700 | tctxt->delayLastEndOffset = offset; |
701 | tctxt->lastEndOffset = offset; |
702 | tctxt->filledDelayedSlots = 0; |
703 | tctxt->lastMatchOffset = 0; |
704 | tctxt->lastCombMatchOffset = offset; /* DO NOT set 0 here! */ |
705 | tctxt->minMatchOffset = offset; |
706 | tctxt->minNonMpvMatchOffset = offset; |
707 | tctxt->next_mpv_offset = offset; |
708 | |
709 | scratch->catchup_pq.qm_size = 0; |
710 | scratch->al_log_sum = 0; /* clear the anchored logs */ |
711 | |
712 | fatbit_clear(scratch->aqa); |
713 | } |
714 | |
715 | void roseStreamEodExec(const struct RoseEngine *t, u64a offset, |
716 | struct hs_scratch *scratch) { |
717 | assert(scratch); |
718 | assert(t->requiresEodCheck); |
719 | DEBUG_PRINTF("ci buf %p/%zu his %p/%zu\n" , scratch->core_info.buf, |
720 | scratch->core_info.len, scratch->core_info.hbuf, |
721 | scratch->core_info.hlen); |
722 | |
723 | // We should not have been called if we've already been told to terminate |
724 | // matching. |
725 | assert(!told_to_stop_matching(scratch)); |
726 | |
727 | if (t->maxBiAnchoredWidth != ROSE_BOUND_INF |
728 | && offset > t->maxBiAnchoredWidth) { |
729 | DEBUG_PRINTF("bailing, we are beyond max width\n" ); |
730 | /* also some of the history/state may be stale */ |
731 | return; |
732 | } |
733 | |
734 | if (!t->eodProgramOffset) { |
735 | DEBUG_PRINTF("no eod program\n" ); |
736 | return; |
737 | } |
738 | |
739 | roseStreamInitEod(t, offset, scratch); |
740 | |
741 | DEBUG_PRINTF("running eod program at %u\n" , t->eodProgramOffset); |
742 | |
743 | // There should be no pending delayed literals. |
744 | assert(!scratch->tctxt.filledDelayedSlots); |
745 | |
746 | const u64a som = 0; |
747 | const u8 flags = ROSE_PROG_FLAG_SKIP_MPV_CATCHUP; |
748 | |
749 | // Note: we ignore the result, as this is the last thing to ever happen on |
750 | // a scan. |
751 | roseRunProgram(t, scratch, t->eodProgramOffset, som, offset, flags); |
752 | } |
753 | |