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 | |
60 | hwlmcb_rv_t roseCatchUpAll(s64a loc, struct hs_scratch *scratch); |
61 | |
62 | /* will only catch mpv up to last reported external match */ |
63 | hwlmcb_rv_t roseCatchUpSuf(s64a loc, struct hs_scratch *scratch); |
64 | |
65 | hwlmcb_rv_t roseCatchUpMPV_i(const struct RoseEngine *t, s64a loc, |
66 | struct hs_scratch *scratch); |
67 | |
68 | void blockInitSufPQ(const struct RoseEngine *t, char *state, |
69 | struct hs_scratch *scratch, char is_small_block); |
70 | void streamInitSufPQ(const struct RoseEngine *t, char *state, |
71 | struct hs_scratch *scratch); |
72 | |
73 | static really_inline |
74 | int 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. */ |
101 | static really_inline |
102 | hwlmcb_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. */ |
127 | static rose_inline |
128 | hwlmcb_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 | */ |
176 | static rose_inline |
177 | hwlmcb_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 | |