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 * Rose has several components which run behind the main (floating table) clock
34 * and need to be caught up before we report matches.
35 *
36 * Currently we have to deal with:
37 * 1. Suffix/Outfix NFAs
38 * 2. A single MPV NFA (chained), which may also be triggered by (1).
39 *
40 * The approach is to:
41 * - (A) build a priority queue of the suffix/outfixes based on their first
42 * match location;
43 * - (B) process the matches from the priority queue in order;
44 * - (C) As we report matches from (B) we interleave matches from the MPV if it
45 * exists.
46 */
47
48#ifndef ROSE_CATCHUP_H
49#define ROSE_CATCHUP_H
50
51#include "hwlm/hwlm.h"
52#include "runtime.h"
53#include "scratch.h"
54#include "rose.h"
55#include "rose_common.h"
56#include "rose_internal.h"
57#include "ue2common.h"
58#include "util/multibit.h"
59
60hwlmcb_rv_t roseCatchUpAll(s64a loc, struct hs_scratch *scratch);
61
62/* will only catch mpv up to last reported external match */
63hwlmcb_rv_t roseCatchUpSuf(s64a loc, struct hs_scratch *scratch);
64
65hwlmcb_rv_t roseCatchUpMPV_i(const struct RoseEngine *t, s64a loc,
66 struct hs_scratch *scratch);
67
68void blockInitSufPQ(const struct RoseEngine *t, char *state,
69 struct hs_scratch *scratch, char is_small_block);
70void streamInitSufPQ(const struct RoseEngine *t, char *state,
71 struct hs_scratch *scratch);
72
73static really_inline
74int canSkipCatchUpMPV(const struct RoseEngine *t, struct hs_scratch *scratch,
75 u64a cur_offset) {
76 if (!has_chained_nfas(t)) {
77 return 1;
78 }
79
80 /* note: we may have to run at less than tctxt.minMatchOffset as we may
81 * have a full queue of postponed events that we need to flush */
82 if (cur_offset < scratch->tctxt.next_mpv_offset) {
83 DEBUG_PRINTF("skipping cur_offset %llu min %llu, mpv %llu\n",
84 cur_offset, scratch->tctxt.minMatchOffset,
85 scratch->tctxt.next_mpv_offset);
86 return 1;
87 }
88
89 assert(t->activeArrayCount);
90
91 DEBUG_PRINTF("cur offset offset: %llu\n", cur_offset);
92 DEBUG_PRINTF("min match offset %llu\n", scratch->tctxt.minMatchOffset);
93
94 assert(t->outfixBeginQueue == 1); /* if it exists mpv is queue 0 */
95
96 const u8 *aa = getActiveLeafArray(t, scratch->core_info.state);
97 return !mmbit_isset(aa, t->activeArrayCount, 0);
98}
99
100/** \brief Catches up the MPV. */
101static really_inline
102hwlmcb_rv_t roseCatchUpMPV(const struct RoseEngine *t, s64a loc,
103 struct hs_scratch *scratch) {
104 u64a cur_offset = loc + scratch->core_info.buf_offset;
105 assert(cur_offset >= scratch->tctxt.minMatchOffset);
106 assert(!can_stop_matching(scratch));
107
108 if (canSkipCatchUpMPV(t, scratch, cur_offset)) {
109 if (t->flushCombProgramOffset) {
110 if (roseRunFlushCombProgram(t, scratch, cur_offset)
111 == HWLM_TERMINATE_MATCHING) {
112 return HWLM_TERMINATE_MATCHING;
113 }
114 }
115 updateMinMatchOffsetFromMpv(&scratch->tctxt, cur_offset);
116 return HWLM_CONTINUE_MATCHING;
117 }
118
119 /* Note: chained tails MUST not participate in the priority queue as
120 * they may have events pushed on during this process which may be before
121 * the catch up point */
122
123 return roseCatchUpMPV_i(t, loc, scratch);
124}
125
126/** \brief Catches up NFAs and the MPV. */
127static rose_inline
128hwlmcb_rv_t roseCatchUpTo(const struct RoseEngine *t,
129 struct hs_scratch *scratch, u64a end) {
130 /* no need to catch up if we are at the same offset as last time */
131 if (end <= scratch->tctxt.minMatchOffset) {
132 /* we must already be up to date */
133 DEBUG_PRINTF("skip\n");
134 return HWLM_CONTINUE_MATCHING;
135 }
136
137 char *state = scratch->core_info.state;
138 s64a loc = end - scratch->core_info.buf_offset;
139
140 if (end <= scratch->tctxt.minNonMpvMatchOffset) {
141 /* only need to catch up the mpv */
142 return roseCatchUpMPV(t, loc, scratch);
143 }
144
145 assert(scratch->tctxt.minMatchOffset >= scratch->core_info.buf_offset);
146 hwlmcb_rv_t rv;
147 if (!t->activeArrayCount
148 || !mmbit_any(getActiveLeafArray(t, state), t->activeArrayCount)) {
149 if (t->flushCombProgramOffset) {
150 if (roseRunFlushCombProgram(t, scratch, end)
151 == HWLM_TERMINATE_MATCHING) {
152 return HWLM_TERMINATE_MATCHING;
153 }
154 }
155 updateMinMatchOffset(&scratch->tctxt, end);
156 rv = HWLM_CONTINUE_MATCHING;
157 } else {
158 rv = roseCatchUpAll(loc, scratch);
159 }
160
161 assert(rv != HWLM_CONTINUE_MATCHING
162 || scratch->tctxt.minMatchOffset == end);
163 assert(rv != HWLM_CONTINUE_MATCHING
164 || scratch->tctxt.minNonMpvMatchOffset == end);
165 assert(!can_stop_matching(scratch) || rv == HWLM_TERMINATE_MATCHING);
166 return rv;
167}
168
169/**
170 * \brief Catches up anything which may add triggers on the MPV (suffixes and
171 * outfixes).
172 *
173 * The MPV will be run only to intersperse matches in the output match stream
174 * if external matches are raised.
175 */
176static rose_inline
177hwlmcb_rv_t roseCatchUpMpvFeeders(const struct RoseEngine *t,
178 struct hs_scratch *scratch, u64a end) {
179 /* no need to catch up if we are at the same offset as last time */
180 if (end <= scratch->tctxt.minNonMpvMatchOffset) {
181 /* we must already be up to date */
182 DEBUG_PRINTF("skip\n");
183 return HWLM_CONTINUE_MATCHING;
184 }
185
186 s64a loc = end - scratch->core_info.buf_offset;
187
188 assert(t->activeArrayCount); /* mpv is in active array */
189 assert(scratch->tctxt.minMatchOffset >= scratch->core_info.buf_offset);
190
191 if (!t->mpvTriggeredByLeaf) {
192 /* no need to check as they never put triggers onto the mpv */
193 return HWLM_CONTINUE_MATCHING;
194 }
195
196 /* sadly, this branch rarely gets taken as the mpv itself is usually
197 * alive. */
198 char *state = scratch->core_info.state;
199 if (!mmbit_any(getActiveLeafArray(t, state), t->activeArrayCount)) {
200 scratch->tctxt.minNonMpvMatchOffset = end;
201 return HWLM_CONTINUE_MATCHING;
202 }
203
204 return roseCatchUpSuf(loc, scratch);
205}
206
207#endif
208