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 | #ifndef ROSE_MATCH_H |
30 | #define ROSE_MATCH_H |
31 | |
32 | #include "catchup.h" |
33 | #include "runtime.h" |
34 | #include "scratch.h" |
35 | #include "report.h" |
36 | #include "rose_common.h" |
37 | #include "rose_internal.h" |
38 | #include "ue2common.h" |
39 | #include "hwlm/hwlm.h" |
40 | #include "nfa/nfa_api.h" |
41 | #include "nfa/nfa_api_queue.h" |
42 | #include "nfa/nfa_api_util.h" |
43 | #include "som/som_runtime.h" |
44 | #include "util/bitutils.h" |
45 | #include "util/exhaust.h" |
46 | #include "util/fatbit.h" |
47 | #include "util/multibit.h" |
48 | |
49 | /* Callbacks, defined in catchup.c */ |
50 | |
51 | int roseNfaAdaptor(u64a start, u64a end, ReportID id, void *context); |
52 | |
53 | /* Callbacks, defined in match.c */ |
54 | |
55 | hwlmcb_rv_t roseCallback(size_t end, u32 id, struct hs_scratch *scratch); |
56 | hwlmcb_rv_t roseFloatingCallback(size_t end, u32 id, |
57 | struct hs_scratch *scratch); |
58 | hwlmcb_rv_t roseDelayRebuildCallback(size_t end, u32 id, |
59 | struct hs_scratch *scratch); |
60 | int roseAnchoredCallback(u64a start, u64a end, u32 id, void *ctx); |
61 | |
62 | /* Common code, used all over Rose runtime */ |
63 | |
64 | hwlmcb_rv_t roseHandleChainMatch(const struct RoseEngine *t, |
65 | struct hs_scratch *scratch, u32 event, |
66 | u64a top_squash_distance, u64a end, |
67 | char in_catchup); |
68 | |
69 | /** \brief Initialize the queue for a suffix/outfix engine. */ |
70 | static really_inline |
71 | void initQueue(struct mq *q, u32 qi, const struct RoseEngine *t, |
72 | struct hs_scratch *scratch) { |
73 | const struct NfaInfo *info = getNfaInfoByQueue(t, qi); |
74 | assert(scratch->fullState); |
75 | q->nfa = getNfaByInfo(t, info); |
76 | q->end = 0; |
77 | q->cur = 0; |
78 | q->state = scratch->fullState + info->fullStateOffset; |
79 | q->streamState = scratch->core_info.state + info->stateOffset; |
80 | q->offset = scratch->core_info.buf_offset; |
81 | q->buffer = scratch->core_info.buf; |
82 | q->length = scratch->core_info.len; |
83 | q->history = scratch->core_info.hbuf; |
84 | q->hlength = scratch->core_info.hlen; |
85 | q->cb = roseNfaAdaptor; |
86 | q->context = scratch; |
87 | q->report_current = 0; |
88 | |
89 | DEBUG_PRINTF("qi=%u, offset=%llu, fullState=%u, streamState=%u, " |
90 | "state=%u\n" , qi, q->offset, info->fullStateOffset, |
91 | info->stateOffset, *(u32 *)q->state); |
92 | } |
93 | |
94 | /** \brief Initialize the queue for a leftfix (prefix/infix) engine. */ |
95 | static really_inline |
96 | void initRoseQueue(const struct RoseEngine *t, u32 qi, |
97 | const struct LeftNfaInfo *left, |
98 | struct hs_scratch *scratch) { |
99 | struct mq *q = scratch->queues + qi; |
100 | const struct NfaInfo *info = getNfaInfoByQueue(t, qi); |
101 | q->nfa = getNfaByInfo(t, info); |
102 | q->end = 0; |
103 | q->cur = 0; |
104 | q->state = scratch->fullState + info->fullStateOffset; |
105 | |
106 | // Transient roses don't have stream state, we use tstate in scratch |
107 | // instead. The only reason we need this at ALL is for LimEx extended |
108 | // regions, which assume that they have access to q->streamState + |
109 | // compressedStateSize. |
110 | if (left->transient) { |
111 | q->streamState = (char *)scratch->tstate + info->stateOffset; |
112 | } else { |
113 | q->streamState = scratch->core_info.state + info->stateOffset; |
114 | } |
115 | |
116 | q->offset = scratch->core_info.buf_offset; |
117 | q->buffer = scratch->core_info.buf; |
118 | q->length = scratch->core_info.len; |
119 | q->history = scratch->core_info.hbuf; |
120 | q->hlength = scratch->core_info.hlen; |
121 | q->cb = NULL; |
122 | q->context = NULL; |
123 | q->report_current = 0; |
124 | |
125 | DEBUG_PRINTF("qi=%u, offset=%llu, fullState=%u, streamState=%u, " |
126 | "state=%u\n" , qi, q->offset, info->fullStateOffset, |
127 | info->stateOffset, *(u32 *)q->state); |
128 | } |
129 | |
130 | /** returns 0 if space for two items (top and end) on the queue */ |
131 | static really_inline |
132 | char isQueueFull(const struct mq *q) { |
133 | return q->end + 2 > MAX_MQE_LEN; |
134 | } |
135 | |
136 | static really_inline |
137 | void loadStreamState(const struct NFA *nfa, struct mq *q, s64a loc) { |
138 | DEBUG_PRINTF("offset=%llu, length=%zu, hlength=%zu, loc=%lld\n" , |
139 | q->offset, q->length, q->hlength, loc); |
140 | nfaExpandState(nfa, q->state, q->streamState, q->offset + loc, |
141 | queue_prev_byte(q, loc)); |
142 | } |
143 | |
144 | static really_inline |
145 | void storeRoseDelay(const struct RoseEngine *t, char *state, |
146 | const struct LeftNfaInfo *left, u32 loc) { |
147 | u32 di = left->lagIndex; |
148 | if (di == ROSE_OFFSET_INVALID) { |
149 | return; |
150 | } |
151 | |
152 | assert(loc < 256); // ONE WHOLE BYTE! |
153 | DEBUG_PRINTF("storing rose delay %u in slot %u\n" , loc, di); |
154 | u8 *leftfixDelay = getLeftfixLagTable(t, state); |
155 | assert(loc <= MAX_STORED_LEFTFIX_LAG); |
156 | leftfixDelay[di] = loc; |
157 | } |
158 | |
159 | static really_inline |
160 | void setAsZombie(const struct RoseEngine *t, char *state, |
161 | const struct LeftNfaInfo *left) { |
162 | u32 di = left->lagIndex; |
163 | assert(di != ROSE_OFFSET_INVALID); |
164 | if (di == ROSE_OFFSET_INVALID) { |
165 | return; |
166 | } |
167 | |
168 | u8 *leftfixDelay = getLeftfixLagTable(t, state); |
169 | leftfixDelay[di] = OWB_ZOMBIE_ALWAYS_YES; |
170 | } |
171 | |
172 | /* loadRoseDelay MUST NOT be called on the first stream write as it is only |
173 | * initialized for running nfas on stream boundaries */ |
174 | static really_inline |
175 | u32 loadRoseDelay(const struct RoseEngine *t, const char *state, |
176 | const struct LeftNfaInfo *left) { |
177 | u32 di = left->lagIndex; |
178 | if (di == ROSE_OFFSET_INVALID) { |
179 | return 0; |
180 | } |
181 | |
182 | const u8 *leftfixDelay = getLeftfixLagTableConst(t, state); |
183 | u32 loc = leftfixDelay[di]; |
184 | DEBUG_PRINTF("read rose delay %u from slot %u\n" , loc, di); |
185 | return loc; |
186 | } |
187 | |
188 | static really_inline |
189 | char isZombie(const struct RoseEngine *t, const char *state, |
190 | const struct LeftNfaInfo *left) { |
191 | u32 di = left->lagIndex; |
192 | assert(di != ROSE_OFFSET_INVALID); |
193 | if (di == ROSE_OFFSET_INVALID) { |
194 | return 0; |
195 | } |
196 | |
197 | const u8 *leftfixDelay = getLeftfixLagTableConst(t, state); |
198 | DEBUG_PRINTF("read owb %hhu from slot %u\n" , leftfixDelay[di], di); |
199 | return leftfixDelay[di] == OWB_ZOMBIE_ALWAYS_YES; |
200 | } |
201 | |
202 | hwlmcb_rv_t flushQueuedLiterals_i(const struct RoseEngine *t, |
203 | struct hs_scratch *scratch, u64a end); |
204 | |
205 | static really_inline |
206 | hwlmcb_rv_t flushQueuedLiterals(const struct RoseEngine *t, |
207 | struct hs_scratch *scratch, u64a end) { |
208 | struct RoseContext *tctxt = &scratch->tctxt; |
209 | |
210 | if (tctxt->delayLastEndOffset == end) { |
211 | DEBUG_PRINTF("no progress, no flush\n" ); |
212 | return HWLM_CONTINUE_MATCHING; |
213 | } |
214 | |
215 | if (!tctxt->filledDelayedSlots && !scratch->al_log_sum) { |
216 | tctxt->delayLastEndOffset = end; |
217 | return HWLM_CONTINUE_MATCHING; |
218 | } |
219 | |
220 | return flushQueuedLiterals_i(t, scratch, end); |
221 | } |
222 | |
223 | static really_inline |
224 | hwlmcb_rv_t cleanUpDelayed(const struct RoseEngine *t, |
225 | struct hs_scratch *scratch, size_t length, |
226 | u64a offset) { |
227 | if (can_stop_matching(scratch)) { |
228 | return HWLM_TERMINATE_MATCHING; |
229 | } |
230 | |
231 | if (flushQueuedLiterals(t, scratch, length + offset) |
232 | == HWLM_TERMINATE_MATCHING) { |
233 | return HWLM_TERMINATE_MATCHING; |
234 | } |
235 | |
236 | struct RoseContext *tctxt = &scratch->tctxt; |
237 | if (tctxt->filledDelayedSlots) { |
238 | DEBUG_PRINTF("dirty\n" ); |
239 | scratch->core_info.status |= STATUS_DELAY_DIRTY; |
240 | } else { |
241 | scratch->core_info.status &= ~STATUS_DELAY_DIRTY; |
242 | } |
243 | |
244 | tctxt->filledDelayedSlots = 0; |
245 | tctxt->delayLastEndOffset = offset; |
246 | |
247 | return HWLM_CONTINUE_MATCHING; |
248 | } |
249 | |
250 | static rose_inline |
251 | void roseFlushLastByteHistory(const struct RoseEngine *t, |
252 | struct hs_scratch *scratch, u64a currEnd) { |
253 | if (!t->lastByteHistoryIterOffset) { |
254 | return; |
255 | } |
256 | |
257 | struct RoseContext *tctxt = &scratch->tctxt; |
258 | struct core_info *ci = &scratch->core_info; |
259 | |
260 | /* currEnd is last byte of string + 1 */ |
261 | if (tctxt->lastEndOffset == ci->buf_offset + ci->len |
262 | || currEnd != ci->buf_offset + ci->len) { |
263 | /* already flushed or it is not yet time to flush */ |
264 | return; |
265 | } |
266 | |
267 | DEBUG_PRINTF("flushing\n" ); |
268 | |
269 | const struct mmbit_sparse_iter *it = |
270 | getByOffset(t, t->lastByteHistoryIterOffset); |
271 | assert(ISALIGNED(it)); |
272 | |
273 | const u32 numStates = t->rolesWithStateCount; |
274 | void *role_state = getRoleState(scratch->core_info.state); |
275 | |
276 | struct mmbit_sparse_state si_state[MAX_SPARSE_ITER_STATES]; |
277 | |
278 | mmbit_sparse_iter_unset(role_state, numStates, it, si_state); |
279 | } |
280 | |
281 | static rose_inline |
282 | int roseHasInFlightMatches(const struct RoseEngine *t, char *state, |
283 | const struct hs_scratch *scratch) { |
284 | if (scratch->al_log_sum) { |
285 | DEBUG_PRINTF("anchored literals in log\n" ); |
286 | return 1; |
287 | } |
288 | |
289 | if (scratch->tctxt.filledDelayedSlots) { |
290 | DEBUG_PRINTF("delayed literal\n" ); |
291 | return 1; |
292 | } |
293 | |
294 | if (mmbit_any(getRoleState(state), t->rolesWithStateCount)) { |
295 | DEBUG_PRINTF("role state is set\n" ); |
296 | return 1; |
297 | } |
298 | |
299 | return 0; |
300 | } |
301 | |
302 | static rose_inline |
303 | hwlmcb_rv_t roseHaltIfExhausted(const struct RoseEngine *t, |
304 | struct hs_scratch *scratch) { |
305 | struct core_info *ci = &scratch->core_info; |
306 | if (isAllExhausted(t, ci->exhaustionVector)) { |
307 | ci->status |= STATUS_EXHAUSTED; |
308 | scratch->tctxt.groups = 0; |
309 | DEBUG_PRINTF("all exhausted, termination requested\n" ); |
310 | return HWLM_TERMINATE_MATCHING; |
311 | } |
312 | |
313 | return HWLM_CONTINUE_MATCHING; |
314 | } |
315 | |
316 | static really_inline |
317 | hwlmcb_rv_t ensureQueueFlushed_i(const struct RoseEngine *t, |
318 | struct hs_scratch *scratch, u32 qi, s64a loc, |
319 | char is_mpv, char in_catchup) { |
320 | struct RoseContext *tctxt = &scratch->tctxt; |
321 | u8 *aa = getActiveLeafArray(t, scratch->core_info.state); |
322 | struct fatbit *activeQueues = scratch->aqa; |
323 | u32 aaCount = t->activeArrayCount; |
324 | u32 qCount = t->queueCount; |
325 | |
326 | struct mq *q = &scratch->queues[qi]; |
327 | DEBUG_PRINTF("qcl %lld, loc: %lld, min (non mpv) match offset: %llu\n" , |
328 | q_cur_loc(q), loc, tctxt->minNonMpvMatchOffset); |
329 | if (q_cur_loc(q) == loc) { |
330 | /* too many tops enqueued at the one spot; need to flatten this queue. |
331 | * We can use the full catchups as it will short circuit as we are |
332 | * already at this location. It also saves waking everybody up */ |
333 | pushQueueNoMerge(q, MQE_END, loc); |
334 | nfaQueueExec(q->nfa, q, loc); |
335 | q->cur = q->end = 0; |
336 | pushQueueAt(q, 0, MQE_START, loc); |
337 | } else if (!in_catchup) { |
338 | if (is_mpv) { |
339 | tctxt->next_mpv_offset = 0; /* force us to catch the mpv */ |
340 | if (loc + scratch->core_info.buf_offset |
341 | <= tctxt->minNonMpvMatchOffset) { |
342 | DEBUG_PRINTF("flushing chained\n" ); |
343 | if (roseCatchUpMPV(t, loc, scratch) == |
344 | HWLM_TERMINATE_MATCHING) { |
345 | return HWLM_TERMINATE_MATCHING; |
346 | } |
347 | goto done_queue_empty; |
348 | } |
349 | } |
350 | |
351 | if (roseCatchUpTo(t, scratch, loc + scratch->core_info.buf_offset) == |
352 | HWLM_TERMINATE_MATCHING) { |
353 | return HWLM_TERMINATE_MATCHING; |
354 | } |
355 | } else { |
356 | /* we must be a chained nfa */ |
357 | assert(is_mpv); |
358 | DEBUG_PRINTF("flushing chained\n" ); |
359 | tctxt->next_mpv_offset = 0; /* force us to catch the mpv */ |
360 | if (roseCatchUpMPV(t, loc, scratch) == HWLM_TERMINATE_MATCHING) { |
361 | return HWLM_TERMINATE_MATCHING; |
362 | } |
363 | } |
364 | done_queue_empty: |
365 | if (!mmbit_set(aa, aaCount, qi)) { |
366 | initQueue(q, qi, t, scratch); |
367 | nfaQueueInitState(q->nfa, q); |
368 | pushQueueAt(q, 0, MQE_START, loc); |
369 | fatbit_set(activeQueues, qCount, qi); |
370 | } |
371 | |
372 | assert(!isQueueFull(q)); |
373 | |
374 | return roseHaltIfExhausted(t, scratch); |
375 | } |
376 | |
377 | static rose_inline |
378 | hwlmcb_rv_t ensureQueueFlushed(const struct RoseEngine *t, |
379 | struct hs_scratch *scratch, u32 qi, s64a loc) { |
380 | return ensureQueueFlushed_i(t, scratch, qi, loc, 0, 0); |
381 | } |
382 | |
383 | #endif |
384 | |