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/**
30 * \file
31 * \brief Rose runtime: code for catching up output-exposed engines.
32 */
33
34#include "catchup.h"
35#include "match.h"
36#include "program_runtime.h"
37#include "rose.h"
38#include "nfa/nfa_rev_api.h"
39#include "nfa/mpv.h"
40#include "som/som_runtime.h"
41#include "util/fatbit.h"
42#include "report.h"
43
44typedef struct queue_match PQ_T;
45#define PQ_COMP(pqc_items, a, b) ((pqc_items)[a].loc < (pqc_items)[b].loc)
46#define PQ_COMP_B(pqc_items, a, b_fixed) ((pqc_items)[a].loc < (b_fixed).loc)
47
48#include "util/pqueue.h"
49
50static really_inline
51int roseNfaRunProgram(const struct RoseEngine *rose, struct hs_scratch *scratch,
52 u64a som, u64a offset, ReportID id, const char from_mpv) {
53 const u32 program = id;
54 u8 flags = ROSE_PROG_FLAG_IN_CATCHUP;
55 if (from_mpv) {
56 flags |= ROSE_PROG_FLAG_FROM_MPV;
57 }
58
59 roseRunProgram(rose, scratch, program, som, offset, flags);
60
61 return can_stop_matching(scratch) ? MO_HALT_MATCHING : MO_CONTINUE_MATCHING;
62}
63
64static rose_inline
65char roseSuffixInfoIsExhausted(const struct RoseEngine *rose,
66 const struct NfaInfo *info,
67 const char *exhausted) {
68 if (!info->ekeyListOffset) {
69 return 0;
70 }
71
72 DEBUG_PRINTF("check exhaustion -> start at %u\n", info->ekeyListOffset);
73
74 /* INVALID_EKEY terminated list */
75 const u32 *ekeys = getByOffset(rose, info->ekeyListOffset);
76 while (*ekeys != INVALID_EKEY) {
77 DEBUG_PRINTF("check %u\n", *ekeys);
78 if (!isExhausted(rose, exhausted, *ekeys)) {
79 DEBUG_PRINTF("not exhausted -> alive\n");
80 return 0;
81 }
82 ++ekeys;
83 }
84
85 DEBUG_PRINTF("all ekeys exhausted -> dead\n");
86 return 1;
87}
88
89static really_inline
90char roseSuffixIsExhausted(const struct RoseEngine *rose, u32 qi,
91 const char *exhausted) {
92 DEBUG_PRINTF("check queue %u\n", qi);
93 const struct NfaInfo *info = getNfaInfoByQueue(rose, qi);
94 return roseSuffixInfoIsExhausted(rose, info, exhausted);
95}
96
97static really_inline
98void deactivateQueue(const struct RoseEngine *t, u8 *aa, u32 qi,
99 struct hs_scratch *scratch) {
100 u32 aaCount = t->activeArrayCount;
101 u32 qCount = t->queueCount;
102
103 /* this is sailing close to the wind with regards to invalidating an
104 * iteration. We are saved by the fact that unsetting does not clear the
105 * summary bits -> the block under the gun remains valid
106 */
107 DEBUG_PRINTF("killing off zombie queue %u\n", qi);
108 mmbit_unset(aa, aaCount, qi);
109 fatbit_unset(scratch->aqa, qCount, qi);
110}
111
112static really_inline
113void ensureQueueActive(const struct RoseEngine *t, u32 qi, u32 qCount,
114 struct mq *q, struct hs_scratch *scratch) {
115 if (!fatbit_set(scratch->aqa, qCount, qi)) {
116 DEBUG_PRINTF("initing %u\n", qi);
117 initQueue(q, qi, t, scratch);
118 loadStreamState(q->nfa, q, 0);
119 pushQueueAt(q, 0, MQE_START, 0);
120 }
121}
122
123static really_inline
124void pq_replace_top_with(struct catchup_pq *pq,
125 UNUSED struct hs_scratch *scratch, u32 queue,
126 s64a loc) {
127 DEBUG_PRINTF("inserting q%u in pq at %lld\n", queue, loc);
128 struct queue_match temp = {
129 .queue = queue,
130 .loc = (size_t)loc
131 };
132
133 assert(loc > 0);
134 assert(pq->qm_size);
135 assert(loc <= (s64a)scratch->core_info.len);
136 pq_replace_top(pq->qm, pq->qm_size, temp);
137}
138
139static really_inline
140void pq_insert_with(struct catchup_pq *pq,
141 UNUSED struct hs_scratch *scratch, u32 queue, s64a loc) {
142 DEBUG_PRINTF("inserting q%u in pq at %lld\n", queue, loc);
143 struct queue_match temp = {
144 .queue = queue,
145 .loc = (size_t)loc
146 };
147
148 assert(loc > 0);
149 assert(loc <= (s64a)scratch->core_info.len);
150 pq_insert(pq->qm, pq->qm_size, temp);
151 ++pq->qm_size;
152}
153
154static really_inline
155void pq_pop_nice(struct catchup_pq *pq) {
156 pq_pop(pq->qm, pq->qm_size);
157 pq->qm_size--;
158}
159
160static really_inline
161s64a pq_top_loc(struct catchup_pq *pq) {
162 assert(pq->qm_size);
163 return (s64a)pq_top(pq->qm)->loc;
164}
165
166/* requires that we are the top item on the pq */
167static really_inline
168hwlmcb_rv_t runExistingNfaToNextMatch(const struct RoseEngine *t, u32 qi,
169 struct mq *q, s64a loc,
170 struct hs_scratch *scratch, u8 *aa,
171 char report_curr) {
172 assert(pq_top(scratch->catchup_pq.qm)->queue == qi);
173 assert(scratch->catchup_pq.qm_size);
174 assert(!q->report_current);
175 if (report_curr) {
176 DEBUG_PRINTF("need to report matches\n");
177 q->report_current = 1;
178 }
179
180 DEBUG_PRINTF("running queue from %u:%lld to %lld\n", q->cur, q_cur_loc(q),
181 loc);
182
183 assert(q_cur_loc(q) <= loc);
184
185 char alive = nfaQueueExecToMatch(q->nfa, q, loc);
186
187 /* exit via gift shop */
188 if (alive == MO_MATCHES_PENDING) {
189 /* we have pending matches */
190 assert(q_cur_loc(q) + scratch->core_info.buf_offset
191 >= scratch->tctxt.minMatchOffset);
192 pq_replace_top_with(&scratch->catchup_pq, scratch, qi, q_cur_loc(q));
193 return HWLM_CONTINUE_MATCHING;
194 } else if (!alive) {
195 if (report_curr && can_stop_matching(scratch)) {
196 DEBUG_PRINTF("bailing\n");
197 return HWLM_TERMINATE_MATCHING;
198 }
199
200 deactivateQueue(t, aa, qi, scratch);
201 } else if (q->cur == q->end) {
202 DEBUG_PRINTF("queue %u finished, nfa lives\n", qi);
203 q->cur = q->end = 0;
204 pushQueueAt(q, 0, MQE_START, loc);
205 } else {
206 DEBUG_PRINTF("queue %u unfinished, nfa lives\n", qi);
207 u32 i = 0;
208 while (q->cur < q->end) {
209 q->items[i] = q->items[q->cur++];
210 DEBUG_PRINTF("q[%u] = %u:%lld\n", i, q->items[i].type,
211 q->items[i].location);
212 assert(q->items[i].type != MQE_END);
213 i++;
214 }
215 q->cur = 0;
216 q->end = i;
217 }
218
219 pq_pop_nice(&scratch->catchup_pq);
220
221 return HWLM_CONTINUE_MATCHING;
222}
223
224static really_inline
225hwlmcb_rv_t runNewNfaToNextMatch(const struct RoseEngine *t, u32 qi,
226 struct mq *q, s64a loc,
227 struct hs_scratch *scratch, u8 *aa,
228 s64a report_ok_loc) {
229 assert(!q->report_current);
230 DEBUG_PRINTF("running queue from %u:%lld to %lld\n", q->cur, q_cur_loc(q),
231 loc);
232 DEBUG_PRINTF("min match offset %llu\n", scratch->tctxt.minMatchOffset);
233
234 char alive = 1;
235
236restart:
237 alive = nfaQueueExecToMatch(q->nfa, q, loc);
238
239 if (alive == MO_MATCHES_PENDING) {
240 DEBUG_PRINTF("we have pending matches at %lld\n", q_cur_loc(q));
241 s64a qcl = q_cur_loc(q);
242
243 if (qcl == report_ok_loc) {
244 assert(q->cur != q->end); /* the queue shouldn't be empty if there
245 * are pending matches. */
246 q->report_current = 1;
247 DEBUG_PRINTF("restarting...\n");
248 goto restart;
249 }
250 assert(qcl + scratch->core_info.buf_offset
251 >= scratch->tctxt.minMatchOffset);
252 pq_insert_with(&scratch->catchup_pq, scratch, qi, qcl);
253 } else if (!alive) {
254 if (can_stop_matching(scratch)) {
255 DEBUG_PRINTF("bailing\n");
256 return HWLM_TERMINATE_MATCHING;
257 }
258
259 deactivateQueue(t, aa, qi, scratch);
260 } else if (q->cur == q->end) {
261 DEBUG_PRINTF("queue %u finished, nfa lives\n", qi);
262 q->cur = q->end = 0;
263 pushQueueAt(q, 0, MQE_START, loc);
264 } else {
265 DEBUG_PRINTF("queue %u unfinished, nfa lives\n", qi);
266 u32 i = 0;
267 while (q->cur < q->end) {
268 q->items[i] = q->items[q->cur++];
269 DEBUG_PRINTF("q[%u] = %u:%lld\n", i, q->items[i].type,
270 q->items[i].location);
271 assert(q->items[i].type != MQE_END);
272 i++;
273 }
274 q->cur = 0;
275 q->end = i;
276 }
277
278 return HWLM_CONTINUE_MATCHING;
279}
280
281/* for use by mpv (chained) only */
282static
283int roseNfaFinalBlastAdaptor(u64a start, u64a end, ReportID id, void *context) {
284 struct hs_scratch *scratch = context;
285 assert(scratch && scratch->magic == SCRATCH_MAGIC);
286 const struct RoseEngine *t = scratch->core_info.rose;
287
288 DEBUG_PRINTF("id=%u matched at [%llu,%llu]\n", id, start, end);
289
290 int cb_rv = roseNfaRunProgram(t, scratch, start, end, id, 1);
291 if (cb_rv == MO_HALT_MATCHING) {
292 return MO_HALT_MATCHING;
293 } else if (cb_rv == ROSE_CONTINUE_MATCHING_NO_EXHAUST) {
294 return MO_CONTINUE_MATCHING;
295 } else {
296 assert(cb_rv == MO_CONTINUE_MATCHING);
297 return !roseSuffixIsExhausted(t, 0,
298 scratch->core_info.exhaustionVector);
299 }
300}
301
302static really_inline
303void ensureEnd(struct mq *q, UNUSED u32 qi, s64a final_loc) {
304 DEBUG_PRINTF("ensure MQE_END %lld for queue %u\n", final_loc, qi);
305 if (final_loc >= q_last_loc(q)) {
306 /* TODO: ensure situation does not arise */
307 assert(q_last_type(q) != MQE_END);
308 pushQueueNoMerge(q, MQE_END, final_loc);
309 }
310}
311
312static really_inline
313hwlmcb_rv_t add_to_queue(const struct RoseEngine *t, struct mq *queues,
314 u32 qCount, u8 *aa, struct hs_scratch *scratch,
315 s64a loc, u32 qi, s64a report_ok_loc) {
316 struct mq *q = queues + qi;
317 const struct NfaInfo *info = getNfaInfoByQueue(t, qi);
318
319 if (roseSuffixInfoIsExhausted(t, info,
320 scratch->core_info.exhaustionVector)) {
321 deactivateQueue(t, aa, qi, scratch);
322 return HWLM_CONTINUE_MATCHING;
323 }
324
325 ensureQueueActive(t, qi, qCount, q, scratch);
326
327 if (unlikely(loc < q_cur_loc(q))) {
328 DEBUG_PRINTF("err loc %lld < location %lld\n", loc, q_cur_loc(q));
329 return HWLM_CONTINUE_MATCHING;
330 }
331
332 ensureEnd(q, qi, loc);
333
334 return runNewNfaToNextMatch(t, qi, q, loc, scratch, aa, report_ok_loc);
335}
336
337static really_inline
338s64a findSecondPlace(struct catchup_pq *pq, s64a loc_limit) {
339 assert(pq->qm_size); /* we are still on the pq and we are first place */
340
341 /* we know (*cough* encapsulation) that second place will either be in
342 * pq->qm[1] or pq->qm[2] (we are pq->qm[0]) */
343 switch (pq->qm_size) {
344 case 0:
345 case 1:
346 return (s64a)loc_limit;
347 case 2:
348 return MIN((s64a)pq->qm[1].loc, loc_limit);
349 default:;
350 size_t best = MIN(pq->qm[1].loc, pq->qm[2].loc);
351 return MIN((s64a)best, loc_limit);
352 }
353}
354
355hwlmcb_rv_t roseCatchUpMPV_i(const struct RoseEngine *t, s64a loc,
356 struct hs_scratch *scratch) {
357 char *state = scratch->core_info.state;
358 struct mq *queues = scratch->queues;
359 u8 *aa = getActiveLeafArray(t, state);
360 UNUSED u32 aaCount = t->activeArrayCount;
361 u32 qCount = t->queueCount;
362
363 /* find first match of each pending nfa */
364 DEBUG_PRINTF("aa=%p, aaCount=%u\n", aa, aaCount);
365
366 assert(t->outfixBeginQueue == 1);
367
368 u32 qi = 0;
369 assert(mmbit_isset(aa, aaCount, 0)); /* caller should have already bailed */
370
371 DEBUG_PRINTF("catching up qi=%u to loc %lld\n", qi, loc);
372
373 struct mq *q = queues + qi;
374 const struct NfaInfo *info = getNfaInfoByQueue(t, qi);
375 u64a mpv_exec_end = scratch->core_info.buf_offset + loc;
376 u64a next_pos_match_loc = 0;
377
378 if (roseSuffixInfoIsExhausted(t, info,
379 scratch->core_info.exhaustionVector)) {
380 deactivateQueue(t, aa, qi, scratch);
381 goto done;
382 }
383
384 ensureQueueActive(t, qi, qCount, q, scratch);
385
386 if (unlikely(loc < q_cur_loc(q))) {
387 DEBUG_PRINTF("err loc %lld < location %lld\n", loc, q_cur_loc(q));
388 goto done;
389 }
390
391 ensureEnd(q, qi, loc);
392
393 assert(!q->report_current);
394
395 q->cb = roseNfaFinalBlastAdaptor;
396
397 DEBUG_PRINTF("queue %u blasting, %u/%u [%lld/%lld]\n",
398 qi, q->cur, q->end, q->items[q->cur].location, loc);
399
400 scratch->tctxt.mpv_inactive = 0;
401
402 /* we know it is going to be an mpv, skip the indirection */
403 next_pos_match_loc = nfaExecMpv_QueueExecRaw(q->nfa, q, loc);
404 assert(!q->report_current);
405
406 if (!next_pos_match_loc) { /* 0 means dead */
407 DEBUG_PRINTF("mpv is pining for the fjords\n");
408 if (can_stop_matching(scratch)) {
409 deactivateQueue(t, aa, qi, scratch);
410 return HWLM_TERMINATE_MATCHING;
411 }
412
413 next_pos_match_loc = scratch->core_info.len;
414 scratch->tctxt.mpv_inactive = 1;
415 }
416
417 if (q->cur == q->end) {
418 DEBUG_PRINTF("queue %u finished, nfa lives [%lld]\n", qi, loc);
419 q->cur = 0;
420 q->end = 0;
421 pushQueueAt(q, 0, MQE_START, loc);
422 } else {
423 DEBUG_PRINTF("queue %u not finished, nfa lives [%lld]\n", qi, loc);
424 }
425
426done:
427 if (t->flushCombProgramOffset) {
428 if (roseRunFlushCombProgram(t, scratch, mpv_exec_end)
429 == HWLM_TERMINATE_MATCHING) {
430 return HWLM_TERMINATE_MATCHING;
431 }
432 }
433 updateMinMatchOffsetFromMpv(&scratch->tctxt, mpv_exec_end);
434 scratch->tctxt.next_mpv_offset
435 = MAX(next_pos_match_loc + scratch->core_info.buf_offset,
436 mpv_exec_end + 1);
437
438 DEBUG_PRINTF("next match loc %lld (off %llu)\n", next_pos_match_loc,
439 scratch->tctxt.next_mpv_offset);
440 return can_stop_matching(scratch) ? HWLM_TERMINATE_MATCHING
441 : HWLM_CONTINUE_MATCHING;
442}
443
444static really_inline
445char in_mpv(const struct RoseEngine *rose, const struct hs_scratch *scratch) {
446 const struct RoseContext *tctxt = &scratch->tctxt;
447 assert(tctxt->curr_qi < rose->queueCount);
448 if (tctxt->curr_qi < rose->outfixBeginQueue) {
449 assert(getNfaByQueue(rose, tctxt->curr_qi)->type == MPV_NFA);
450 return 1;
451 }
452 return 0;
453}
454
455static
456int roseNfaBlastAdaptor(u64a start, u64a end, ReportID id, void *context) {
457 struct hs_scratch *scratch = context;
458 assert(scratch && scratch->magic == SCRATCH_MAGIC);
459 const struct RoseEngine *t = scratch->core_info.rose;
460
461 DEBUG_PRINTF("id=%u matched at [%llu,%llu]\n", id, start, end);
462
463 const char from_mpv = in_mpv(t, scratch);
464 int cb_rv = roseNfaRunProgram(t, scratch, start, end, id, from_mpv);
465 if (cb_rv == MO_HALT_MATCHING) {
466 return MO_HALT_MATCHING;
467 } else if (cb_rv == ROSE_CONTINUE_MATCHING_NO_EXHAUST) {
468 return MO_CONTINUE_MATCHING;
469 } else {
470 assert(cb_rv == MO_CONTINUE_MATCHING);
471 return !roseSuffixIsExhausted(t, scratch->tctxt.curr_qi,
472 scratch->core_info.exhaustionVector);
473 }
474}
475
476int roseNfaAdaptor(u64a start, u64a end, ReportID id, void *context) {
477 struct hs_scratch *scratch = context;
478 assert(scratch && scratch->magic == SCRATCH_MAGIC);
479
480 DEBUG_PRINTF("id=%u matched at [%llu,%llu]\n", id, start, end);
481
482 /* must be a external report as haig cannot directly participate in chain */
483 return roseNfaRunProgram(scratch->core_info.rose, scratch, start, end, id,
484 0);
485}
486
487static really_inline
488char blast_queue(struct hs_scratch *scratch, struct mq *q, u32 qi, s64a to_loc,
489 char report_current) {
490 scratch->tctxt.curr_qi = qi;
491 q->cb = roseNfaBlastAdaptor;
492 q->report_current = report_current;
493 DEBUG_PRINTF("queue %u blasting, %u/%u [%lld/%lld]\n", qi, q->cur, q->end,
494 q_cur_loc(q), to_loc);
495 char alive = nfaQueueExec(q->nfa, q, to_loc);
496 q->cb = roseNfaAdaptor;
497 assert(!q->report_current);
498
499 return alive;
500}
501
502static really_inline
503hwlmcb_rv_t buildSufPQ_final(const struct RoseEngine *t, s64a report_ok_loc,
504 s64a second_place_loc, s64a final_loc,
505 struct hs_scratch *scratch, u8 *aa, u32 a_qi) {
506 struct mq *q = scratch->queues + a_qi;
507 const struct NfaInfo *info = getNfaInfoByQueue(t, a_qi);
508 DEBUG_PRINTF("blasting qi=%u to %lld [final %lld]\n", a_qi, second_place_loc,
509 final_loc);
510
511 if (roseSuffixInfoIsExhausted(t, info,
512 scratch->core_info.exhaustionVector)) {
513 deactivateQueue(t, aa, a_qi, scratch);
514 return HWLM_CONTINUE_MATCHING;
515 }
516
517 ensureQueueActive(t, a_qi, t->queueCount, q, scratch);
518
519 if (unlikely(final_loc < q_cur_loc(q))) {
520 DEBUG_PRINTF("err loc %lld < location %lld\n", final_loc, q_cur_loc(q));
521 return HWLM_CONTINUE_MATCHING;
522 }
523
524 ensureEnd(q, a_qi, final_loc);
525
526 char alive = blast_queue(scratch, q, a_qi, second_place_loc, 0);
527
528 /* We have three possible outcomes:
529 * (1) the nfa died
530 * (2) we completed the queue (implies that second_place_loc == final_loc)
531 * (3) the queue ran to second_place_loc and stopped. In this case we need
532 * to find the next match location.
533 */
534
535 if (!alive) {
536 if (can_stop_matching(scratch)) {
537 DEBUG_PRINTF("roseCatchUpNfas done as bailing\n");
538 return HWLM_TERMINATE_MATCHING;
539 }
540
541 deactivateQueue(t, aa, a_qi, scratch);
542 } else if (q->cur == q->end) {
543 DEBUG_PRINTF("queue %u finished, nfa lives [%lld]\n", a_qi, final_loc);
544
545 assert(second_place_loc == final_loc);
546
547 q->cur = q->end = 0;
548 pushQueueAt(q, 0, MQE_START, final_loc);
549 } else {
550 DEBUG_PRINTF("queue %u not finished, %u/%u [%lld/%lld]\n", a_qi, q->cur,
551 q->end, q_cur_loc(q), final_loc);
552 DEBUG_PRINTF("finding next match location\n");
553
554 assert(second_place_loc < final_loc);
555 assert(q_cur_loc(q) >= second_place_loc);
556
557 if (runNewNfaToNextMatch(t, a_qi, q, final_loc, scratch, aa,
558 report_ok_loc) == HWLM_TERMINATE_MATCHING) {
559 DEBUG_PRINTF("roseCatchUpNfas done\n");
560 return HWLM_TERMINATE_MATCHING;
561 }
562 }
563
564 return HWLM_CONTINUE_MATCHING;
565}
566
567void streamInitSufPQ(const struct RoseEngine *t, char *state,
568 struct hs_scratch *scratch) {
569 assert(scratch->catchup_pq.qm_size == 0);
570 assert(t->outfixBeginQueue != t->outfixEndQueue);
571
572 DEBUG_PRINTF("initSufPQ: outfixes [%u,%u)\n", t->outfixBeginQueue,
573 t->outfixEndQueue);
574
575 u32 qCount = t->queueCount;
576 u8 *aa = getActiveLeafArray(t, state);
577 u32 aaCount = t->activeArrayCount;
578 struct mq *queues = scratch->queues;
579 size_t length = scratch->core_info.len;
580
581 u32 qi = mmbit_iterate_bounded(aa, aaCount, t->outfixBeginQueue,
582 t->outfixEndQueue);
583 for (; qi < t->outfixEndQueue;) {
584 DEBUG_PRINTF("adding qi=%u\n", qi);
585 struct mq *q = queues + qi;
586
587 ensureQueueActive(t, qi, qCount, q, scratch);
588 ensureEnd(q, qi, length);
589
590 char alive = nfaQueueExecToMatch(q->nfa, q, length);
591
592 if (alive == MO_MATCHES_PENDING) {
593 DEBUG_PRINTF("we have pending matches at %lld\n", q_cur_loc(q));
594 s64a qcl = q_cur_loc(q);
595
596 pq_insert_with(&scratch->catchup_pq, scratch, qi, qcl);
597 } else if (!alive) {
598 deactivateQueue(t, aa, qi, scratch);
599 } else {
600 assert(q->cur == q->end);
601 /* TODO: can this be simplified? the nfa will never produce any
602 * matches for this block. */
603 DEBUG_PRINTF("queue %u finished, nfa lives\n", qi);
604 q->cur = q->end = 0;
605 pushQueueAt(q, 0, MQE_START, length);
606 }
607
608 qi = mmbit_iterate_bounded(aa, aaCount, qi + 1, t->outfixEndQueue);
609 }
610}
611
612void blockInitSufPQ(const struct RoseEngine *t, char *state,
613 struct hs_scratch *scratch, char is_small_block) {
614 DEBUG_PRINTF("initSufPQ: outfixes [%u,%u)\n", t->outfixBeginQueue,
615 t->outfixEndQueue);
616
617 assert(scratch->catchup_pq.qm_size == 0);
618 assert(t->outfixBeginQueue != t->outfixEndQueue);
619
620 struct mq *queues = scratch->queues;
621 u8 *aa = getActiveLeafArray(t, state);
622 struct fatbit *aqa = scratch->aqa;
623 u32 aaCount = t->activeArrayCount;
624 u32 qCount = t->queueCount;
625 size_t length = scratch->core_info.len;
626
627 for (u32 qi = t->outfixBeginQueue; qi < t->outfixEndQueue; qi++) {
628 const struct NfaInfo *info = getNfaInfoByQueue(t, qi);
629
630 if (is_small_block && info->in_sbmatcher) {
631 DEBUG_PRINTF("skip outfix %u as it's in the SB matcher\n", qi);
632 continue;
633 }
634
635 const struct NFA *nfa = getNfaByInfo(t, info);
636 DEBUG_PRINTF("testing minwidth %u > len %zu\n", nfa->minWidth,
637 length);
638 size_t len = nfaRevAccelCheck(nfa, scratch->core_info.buf, length);
639 if (!len) {
640 continue;
641 }
642 mmbit_set(aa, aaCount, qi);
643 fatbit_set(aqa, qCount, qi);
644 struct mq *q = queues + qi;
645 initQueue(q, qi, t, scratch);
646 q->length = len; /* adjust for rev_accel */
647 nfaQueueInitState(nfa, q);
648 pushQueueAt(q, 0, MQE_START, 0);
649 pushQueueAt(q, 1, MQE_TOP, 0);
650 pushQueueAt(q, 2, MQE_END, length);
651
652 DEBUG_PRINTF("adding qi=%u to pq\n", qi);
653
654 char alive = nfaQueueExecToMatch(q->nfa, q, length);
655
656 if (alive == MO_MATCHES_PENDING) {
657 DEBUG_PRINTF("we have pending matches at %lld\n", q_cur_loc(q));
658 s64a qcl = q_cur_loc(q);
659
660 pq_insert_with(&scratch->catchup_pq, scratch, qi, qcl);
661 } else if (!alive) {
662 deactivateQueue(t, aa, qi, scratch);
663 } else {
664 assert(q->cur == q->end);
665 /* TODO: can this be simplified? the nfa will never produce any
666 * matches for this block. */
667 DEBUG_PRINTF("queue %u finished, nfa lives\n", qi);
668 q->cur = q->end = 0;
669 pushQueueAt(q, 0, MQE_START, length);
670 }
671 }
672}
673
674/**
675 * safe_loc is ???
676 */
677static rose_inline
678hwlmcb_rv_t buildSufPQ(const struct RoseEngine *t, char *state, s64a safe_loc,
679 s64a final_loc, struct hs_scratch *scratch) {
680 assert(scratch->catchup_pq.qm_size <= t->outfixEndQueue);
681
682 struct RoseContext *tctxt = &scratch->tctxt;
683 assert(t->activeArrayCount);
684
685 assert(scratch->core_info.buf_offset + final_loc
686 > tctxt->minNonMpvMatchOffset);
687 DEBUG_PRINTF("buildSufPQ final loc %lld (safe %lld)\n", final_loc,
688 safe_loc);
689 assert(safe_loc <= final_loc);
690
691 u8 *aa = getActiveLeafArray(t, state);
692 u32 aaCount = t->activeArrayCount;
693
694 /* find first match of each pending nfa */
695 DEBUG_PRINTF("aa=%p, aaCount=%u\n", aa, aaCount);
696
697 /* Note: mpv MUST not participate in the main priority queue as
698 * they may have events pushed on during this process which may be before
699 * the catch up point. Outfixes are remain in the pq between catchup events
700 * as they never have any incoming events to worry about.
701 */
702 if (aaCount == t->outfixEndQueue) {
703 return HWLM_CONTINUE_MATCHING;
704 }
705
706 DEBUG_PRINTF("mib %u/%u\n", t->outfixBeginQueue, aaCount);
707
708 u32 a_qi = mmbit_iterate_bounded(aa, aaCount, t->outfixEndQueue, aaCount);
709
710 if (a_qi == MMB_INVALID) {
711 return HWLM_CONTINUE_MATCHING;
712 }
713
714 s64a report_ok_loc = tctxt->minNonMpvMatchOffset + 1
715 - scratch->core_info.buf_offset;
716
717 hwlmcb_rv_t rv = roseCatchUpMPV(t, report_ok_loc, scratch);
718 if (rv != HWLM_CONTINUE_MATCHING) {
719 DEBUG_PRINTF("terminating...\n");
720 return rv;
721 }
722
723 while (a_qi != MMB_INVALID) {
724 DEBUG_PRINTF("catching up qi=%u to %lld\n", a_qi, final_loc);
725 u32 n_qi = mmbit_iterate(aa, aaCount, a_qi);
726
727 s64a second_place_loc
728 = scratch->catchup_pq.qm_size ? pq_top_loc(&scratch->catchup_pq)
729 : safe_loc;
730 second_place_loc = MIN(second_place_loc, safe_loc);
731 if (n_qi == MMB_INVALID && report_ok_loc <= second_place_loc) {
732 if (buildSufPQ_final(t, report_ok_loc, second_place_loc, final_loc,
733 scratch, aa, a_qi)
734 == HWLM_TERMINATE_MATCHING) {
735 return HWLM_TERMINATE_MATCHING;
736 }
737 break;
738 }
739
740 if (add_to_queue(t, scratch->queues, t->queueCount, aa, scratch,
741 final_loc, a_qi, report_ok_loc)
742 == HWLM_TERMINATE_MATCHING) {
743 DEBUG_PRINTF("roseCatchUpNfas done\n");
744 return HWLM_TERMINATE_MATCHING;
745 }
746
747 a_qi = n_qi;
748 }
749
750 DEBUG_PRINTF("PQ BUILD %u items\n", scratch->catchup_pq.qm_size);
751 return HWLM_CONTINUE_MATCHING;
752}
753
754static never_inline
755hwlmcb_rv_t roseCatchUpNfas(const struct RoseEngine *t, s64a loc,
756 s64a final_loc, struct hs_scratch *scratch) {
757 assert(t->activeArrayCount);
758
759 DEBUG_PRINTF("roseCatchUpNfas offset=%llu + %lld/%lld\n",
760 scratch->core_info.buf_offset, loc, final_loc);
761 DEBUG_PRINTF("min non mpv match offset %llu\n",
762 scratch->tctxt.minNonMpvMatchOffset);
763
764 struct RoseContext *tctxt = &scratch->tctxt;
765 assert(scratch->core_info.buf_offset + loc >= tctxt->minNonMpvMatchOffset);
766
767 char *state = scratch->core_info.state;
768 struct mq *queues = scratch->queues;
769 u8 *aa = getActiveLeafArray(t, state);
770
771 /* fire off earliest nfa match and catchup anchored matches to that point */
772 while (scratch->catchup_pq.qm_size) {
773 s64a match_loc = pq_top_loc(&scratch->catchup_pq);
774 u32 qi = pq_top(scratch->catchup_pq.qm)->queue;
775
776 DEBUG_PRINTF("winrar q%u@%lld loc %lld\n", qi, match_loc, loc);
777 assert(match_loc + scratch->core_info.buf_offset
778 >= scratch->tctxt.minNonMpvMatchOffset);
779
780 if (match_loc > loc) {
781 /* we have processed all the matches at or before rose's current
782 * location; only things remaining on the pq should be outfixes. */
783 DEBUG_PRINTF("saving for later\n");
784 goto exit;
785 }
786
787 /* catch up char matches to this point */
788 if (roseCatchUpMPV(t, match_loc, scratch)
789 == HWLM_TERMINATE_MATCHING) {
790 DEBUG_PRINTF("roseCatchUpNfas done\n");
791 return HWLM_TERMINATE_MATCHING;
792 }
793
794 assert(match_loc + scratch->core_info.buf_offset
795 >= scratch->tctxt.minNonMpvMatchOffset);
796
797 struct mq *q = queues + qi;
798
799 /* outfixes must be advanced all the way as they persist in the pq
800 * between catchup events */
801 s64a q_final_loc = qi >= t->outfixEndQueue ? final_loc
802 : (s64a)scratch->core_info.len;
803
804 /* fire nfa matches, and find next place this nfa match */
805 DEBUG_PRINTF("reporting matches %u@%llu [q->cur %u/%u]\n", qi,
806 match_loc, q->cur, q->end);
807
808 /* we then need to catch this nfa up to next earliest nfa match. These
809 * matches can be fired directly from the callback. The callback needs
810 * to ensure that the anchored matches remain in sync though */
811 s64a second_place_loc = findSecondPlace(&scratch->catchup_pq, loc);
812 DEBUG_PRINTF("second place %lld loc %lld\n", second_place_loc, loc);
813
814 if (second_place_loc == q_cur_loc(q)) {
815 if (runExistingNfaToNextMatch(t, qi, q, q_final_loc, scratch, aa, 1)
816 == HWLM_TERMINATE_MATCHING) {
817 return HWLM_TERMINATE_MATCHING;
818 }
819 continue;
820 }
821
822 char alive = blast_queue(scratch, q, qi, second_place_loc, 1);
823
824 if (!alive) {
825 if (can_stop_matching(scratch)) {
826 DEBUG_PRINTF("roseCatchUpNfas done as bailing\n");
827 return HWLM_TERMINATE_MATCHING;
828 }
829
830 deactivateQueue(t, aa, qi, scratch);
831 pq_pop_nice(&scratch->catchup_pq);
832 } else if (q->cur == q->end) {
833 DEBUG_PRINTF("queue %u finished, nfa lives [%lld]\n", qi, loc);
834 q->cur = q->end = 0;
835 pushQueueAt(q, 0, MQE_START, loc);
836 pq_pop_nice(&scratch->catchup_pq);
837 } else if (second_place_loc == q_final_loc) {
838 DEBUG_PRINTF("queue %u on hold\n", qi);
839 pq_pop_nice(&scratch->catchup_pq);
840 break;
841 } else {
842 DEBUG_PRINTF("queue %u not finished, %u/%u [%lld/%lld]\n",
843 qi, q->cur, q->end, q->items[q->cur].location, loc);
844 runExistingNfaToNextMatch(t, qi, q, q_final_loc, scratch, aa, 0);
845 }
846 }
847exit:;
848 tctxt->minNonMpvMatchOffset = scratch->core_info.buf_offset + loc;
849 DEBUG_PRINTF("roseCatchUpNfas done\n");
850 return HWLM_CONTINUE_MATCHING;
851}
852
853hwlmcb_rv_t roseCatchUpAll(s64a loc, struct hs_scratch *scratch) {
854 /* just need suf/outfixes and mpv */
855 DEBUG_PRINTF("loc %lld mnmmo %llu mmo %llu\n", loc,
856 scratch->tctxt.minNonMpvMatchOffset,
857 scratch->tctxt.minMatchOffset);
858 assert(scratch->core_info.buf_offset + loc
859 > scratch->tctxt.minNonMpvMatchOffset);
860
861 const struct RoseEngine *t = scratch->core_info.rose;
862 char *state = scratch->core_info.state;
863
864 hwlmcb_rv_t rv = buildSufPQ(t, state, loc, loc, scratch);
865 if (rv != HWLM_CONTINUE_MATCHING) {
866 return rv;
867 }
868
869 rv = roseCatchUpNfas(t, loc, loc, scratch);
870 if (rv != HWLM_CONTINUE_MATCHING) {
871 return rv;
872 }
873
874 rv = roseCatchUpMPV(t, loc, scratch);
875 assert(rv != HWLM_CONTINUE_MATCHING
876 || scratch->catchup_pq.qm_size <= t->outfixEndQueue);
877 assert(!can_stop_matching(scratch) || rv == HWLM_TERMINATE_MATCHING);
878 return rv;
879}
880
881hwlmcb_rv_t roseCatchUpSuf(s64a loc, struct hs_scratch *scratch) {
882 /* just need suf/outfixes. mpv will be caught up only to last reported
883 * external match */
884 assert(scratch->core_info.buf_offset + loc
885 > scratch->tctxt.minNonMpvMatchOffset);
886
887 const struct RoseEngine *t = scratch->core_info.rose;
888 char *state = scratch->core_info.state;
889
890 hwlmcb_rv_t rv = buildSufPQ(t, state, loc, loc, scratch);
891 if (rv != HWLM_CONTINUE_MATCHING) {
892 return rv;
893 }
894
895 rv = roseCatchUpNfas(t, loc, loc, scratch);
896 assert(rv != HWLM_CONTINUE_MATCHING ||
897 scratch->catchup_pq.qm_size <= t->outfixEndQueue);
898
899 return rv;
900}
901