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 | |
44 | typedef 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 | |
50 | static really_inline |
51 | int 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 | |
64 | static rose_inline |
65 | char 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 | |
89 | static really_inline |
90 | char 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 | |
97 | static really_inline |
98 | void 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 | |
112 | static really_inline |
113 | void 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 | |
123 | static really_inline |
124 | void 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 | |
139 | static really_inline |
140 | void 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 | |
154 | static really_inline |
155 | void pq_pop_nice(struct catchup_pq *pq) { |
156 | pq_pop(pq->qm, pq->qm_size); |
157 | pq->qm_size--; |
158 | } |
159 | |
160 | static really_inline |
161 | s64a 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 */ |
167 | static really_inline |
168 | hwlmcb_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 | |
224 | static really_inline |
225 | hwlmcb_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 | |
236 | restart: |
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 */ |
282 | static |
283 | int 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 | |
302 | static really_inline |
303 | void 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 | |
312 | static really_inline |
313 | hwlmcb_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 | |
337 | static really_inline |
338 | s64a 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 | |
355 | hwlmcb_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 | |
426 | done: |
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 | |
444 | static really_inline |
445 | char 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 | |
455 | static |
456 | int 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 | |
476 | int 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 | |
487 | static really_inline |
488 | char 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 | |
502 | static really_inline |
503 | hwlmcb_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 | |
567 | void 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 | |
612 | void 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 | */ |
677 | static rose_inline |
678 | hwlmcb_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 | |
754 | static never_inline |
755 | hwlmcb_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 | } |
847 | exit:; |
848 | tctxt->minNonMpvMatchOffset = scratch->core_info.buf_offset + loc; |
849 | DEBUG_PRINTF("roseCatchUpNfas done\n" ); |
850 | return HWLM_CONTINUE_MATCHING; |
851 | } |
852 | |
853 | hwlmcb_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 | |
881 | hwlmcb_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 | |