1/*
2 * Copyright (c) 2016-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/** \file
30 * \brief Runtime functions to do with reports, inlined into callers.
31 */
32
33#ifndef REPORT_H
34#define REPORT_H
35
36#include "hs_internal.h"
37#include "hs_runtime.h"
38#include "scratch.h"
39#include "ue2common.h"
40#include "nfa/callback.h"
41#include "nfa/nfa_internal.h"
42#include "rose/runtime.h"
43#include "som/som_runtime.h"
44#include "util/exhaust.h"
45#include "util/logical.h"
46#include "util/fatbit.h"
47
48enum DedupeResult {
49 DEDUPE_CONTINUE, //!< Continue with match, not a dupe.
50 DEDUPE_SKIP, //!< Don't report this match, dupe or delayed due to SOM.
51 DEDUPE_HALT //!< User instructed us to stop matching.
52};
53
54static really_inline
55enum DedupeResult dedupeCatchup(const struct RoseEngine *rose,
56 struct hs_scratch *scratch, u64a offset,
57 u64a from_offset, u64a to_offset, u32 dkey,
58 s32 offset_adjust, char is_external_report,
59 char quash_som, const char do_som) {
60 DEBUG_PRINTF("offset=%llu, match=[%llu,%llu], dkey=%u, do_som=%d\n", offset,
61 from_offset, to_offset, dkey, do_som);
62
63 // We should not have been called if there's no dedupe work to do.
64 assert(do_som || dkey != MO_INVALID_IDX);
65
66 struct match_deduper *deduper = &scratch->deduper;
67 if (offset != deduper->current_report_offset) {
68 assert(deduper->current_report_offset == ~0ULL ||
69 deduper->current_report_offset < offset);
70 if (offset == deduper->current_report_offset + 1) {
71 fatbit_clear(deduper->log[offset % 2]);
72 } else {
73 fatbit_clear(deduper->log[0]);
74 fatbit_clear(deduper->log[1]);
75 }
76
77 if (do_som && flushStoredSomMatches(scratch, offset)) {
78 return DEDUPE_HALT;
79 }
80 deduper->current_report_offset = offset;
81 }
82
83 if (dkey != MO_INVALID_IDX) {
84 const u32 dkeyCount = rose->dkeyCount;
85 if (is_external_report || quash_som) {
86 DEBUG_PRINTF("checking dkey %u at offset %llu\n", dkey, to_offset);
87 assert(offset_adjust == 0 || offset_adjust == -1);
88 if (fatbit_set(deduper->log[to_offset % 2], dkeyCount, dkey)) {
89 /* we have already raised this report at this offset, squash
90 * dupe match. */
91 DEBUG_PRINTF("dedupe\n");
92 return DEDUPE_SKIP;
93 }
94 } else if (do_som) {
95 /* SOM external event */
96 DEBUG_PRINTF("checking dkey %u at offset %llu\n", dkey, to_offset);
97 assert(offset_adjust == 0 || offset_adjust == -1);
98 u64a *starts = deduper->som_start_log[to_offset % 2];
99 if (fatbit_set(deduper->som_log[to_offset % 2], dkeyCount, dkey)) {
100 starts[dkey] = MIN(starts[dkey], from_offset);
101 } else {
102 starts[dkey] = from_offset;
103 }
104 DEBUG_PRINTF("starts[%u]=%llu\n", dkey, starts[dkey]);
105
106 if (offset_adjust) {
107 deduper->som_log_dirty |= 1;
108 } else {
109 deduper->som_log_dirty |= 2;
110 }
111
112 return DEDUPE_SKIP;
113 }
114 }
115
116 return DEDUPE_CONTINUE;
117}
118
119/** \brief Test whether the given key (\a ekey) is set in the exhaustion vector
120 * \a evec. */
121static really_inline
122int isExhausted(const struct RoseEngine *rose, const char *evec, u32 ekey) {
123 DEBUG_PRINTF("checking exhaustion %p %u\n", evec, ekey);
124 assert(ekey != INVALID_EKEY);
125 assert(ekey < rose->ekeyCount);
126 return mmbit_isset((const u8 *)evec, rose->ekeyCount, ekey);
127}
128
129/** \brief Returns 1 if all exhaustion keys in the bitvector are on. */
130static really_inline
131int isAllExhausted(const struct RoseEngine *rose, const char *evec) {
132 if (!rose->canExhaust) {
133 return 0; /* pattern set is inexhaustible */
134 }
135
136 return mmbit_all((const u8 *)evec, rose->ekeyCount);
137}
138
139/** \brief Mark key \a ekey on in the exhaustion vector. */
140static really_inline
141void markAsMatched(const struct RoseEngine *rose, char *evec, u32 ekey) {
142 DEBUG_PRINTF("marking as exhausted key %u\n", ekey);
143 assert(ekey != INVALID_EKEY);
144 assert(ekey < rose->ekeyCount);
145 mmbit_set((u8 *)evec, rose->ekeyCount, ekey);
146}
147
148/** \brief Clear all keys in the exhaustion vector. */
149static really_inline
150void clearEvec(const struct RoseEngine *rose, char *evec) {
151 DEBUG_PRINTF("clearing evec %p %u\n", evec, rose->ekeyCount);
152 mmbit_clear((u8 *)evec, rose->ekeyCount);
153}
154
155/** \brief Test whether the given key (\a lkey) is set in the logical vector
156 * \a lvec. */
157static really_inline
158char getLogicalVal(const struct RoseEngine *rose, const char *lvec, u32 lkey) {
159 DEBUG_PRINTF("checking lkey matching %p %u\n", lvec, lkey);
160 assert(lkey != INVALID_LKEY);
161 assert(lkey < rose->lkeyCount + rose->lopCount);
162 return mmbit_isset((const u8 *)lvec, rose->lkeyCount + rose->lopCount,
163 lkey);
164}
165
166/** \brief Mark key \a lkey on in the logical vector. */
167static really_inline
168void setLogicalVal(const struct RoseEngine *rose, char *lvec, u32 lkey,
169 char val) {
170 DEBUG_PRINTF("marking as matched logical key %u\n", lkey);
171 assert(lkey != INVALID_LKEY);
172 assert(lkey < rose->lkeyCount + rose->lopCount);
173 switch (val) {
174 case 0:
175 mmbit_unset((u8 *)lvec, rose->lkeyCount + rose->lopCount, lkey);
176 break;
177 default:
178 mmbit_set((u8 *)lvec, rose->lkeyCount + rose->lopCount, lkey);
179 break;
180 }
181}
182
183/** \brief Mark key \a ckey on in the combination vector. */
184static really_inline
185void setCombinationActive(const struct RoseEngine *rose, char *cvec, u32 ckey) {
186 DEBUG_PRINTF("marking as active combination key %u\n", ckey);
187 assert(ckey != INVALID_CKEY);
188 assert(ckey < rose->ckeyCount);
189 mmbit_set((u8 *)cvec, rose->ckeyCount, ckey);
190}
191
192/** \brief Returns 1 if compliant to all logical combinations. */
193static really_inline
194char isLogicalCombination(const struct RoseEngine *rose, char *lvec,
195 u32 start, u32 result) {
196 const struct LogicalOp *logicalTree = (const struct LogicalOp *)
197 ((const char *)rose + rose->logicalTreeOffset);
198 assert(start >= rose->lkeyCount);
199 assert(start <= result);
200 assert(result < rose->lkeyCount + rose->lopCount);
201 for (u32 i = start; i <= result; i++) {
202 const struct LogicalOp *op = logicalTree + (i - rose->lkeyCount);
203 assert(i == op->id);
204 assert(op->op <= LAST_LOGICAL_OP);
205 switch ((enum LogicalOpType)op->op) {
206 case LOGICAL_OP_NOT:
207 setLogicalVal(rose, lvec, op->id,
208 !getLogicalVal(rose, lvec, op->ro));
209 break;
210 case LOGICAL_OP_AND:
211 setLogicalVal(rose, lvec, op->id,
212 getLogicalVal(rose, lvec, op->lo) &
213 getLogicalVal(rose, lvec, op->ro)); // &&
214 break;
215 case LOGICAL_OP_OR:
216 setLogicalVal(rose, lvec, op->id,
217 getLogicalVal(rose, lvec, op->lo) |
218 getLogicalVal(rose, lvec, op->ro)); // ||
219 break;
220 }
221 }
222 return getLogicalVal(rose, lvec, result);
223}
224
225/** \brief Clear all keys in the logical vector. */
226static really_inline
227void clearLvec(const struct RoseEngine *rose, char *lvec, char *cvec) {
228 DEBUG_PRINTF("clearing lvec %p %u\n", lvec,
229 rose->lkeyCount + rose->lopCount);
230 DEBUG_PRINTF("clearing cvec %p %u\n", cvec, rose->ckeyCount);
231 mmbit_clear((u8 *)lvec, rose->lkeyCount + rose->lopCount);
232 mmbit_clear((u8 *)cvec, rose->ckeyCount);
233}
234
235/** \brief Clear all keys in the combination vector. */
236static really_inline
237void clearCvec(const struct RoseEngine *rose, char *cvec) {
238 DEBUG_PRINTF("clearing cvec %p %u\n", cvec, rose->ckeyCount);
239 mmbit_clear((u8 *)cvec, rose->ckeyCount);
240}
241
242/**
243 * \brief Deliver the given report to the user callback.
244 *
245 * Assumes all preconditions (bounds, exhaustion etc) have been checked and
246 * that dedupe catchup has been done.
247 */
248static really_inline
249int roseDeliverReport(u64a offset, ReportID onmatch, s32 offset_adjust,
250 struct hs_scratch *scratch, u32 ekey) {
251 assert(scratch);
252 assert(scratch->magic == SCRATCH_MAGIC);
253
254 struct core_info *ci = &scratch->core_info;
255
256 u32 flags = 0;
257#ifndef RELEASE_BUILD
258 if (offset_adjust) {
259 // alert testing tools that we've got adjusted matches
260 flags |= HS_MATCH_FLAG_ADJUSTED;
261 }
262#endif
263
264 assert(!can_stop_matching(scratch));
265 assert(ekey == INVALID_EKEY ||
266 !isExhausted(ci->rose, ci->exhaustionVector, ekey));
267
268 u64a from_offset = 0;
269 u64a to_offset = offset + offset_adjust;
270
271 DEBUG_PRINTF(">> reporting match @[%llu,%llu] for sig %u ctxt %p <<\n",
272 from_offset, to_offset, onmatch, ci->userContext);
273
274 int halt = ci->userCallback(onmatch, from_offset, to_offset, flags,
275 ci->userContext);
276 if (halt) {
277 DEBUG_PRINTF("callback requested to terminate matches\n");
278 ci->status |= STATUS_TERMINATED;
279 return MO_HALT_MATCHING;
280 }
281
282 if (ekey != INVALID_EKEY) {
283 markAsMatched(ci->rose, ci->exhaustionVector, ekey);
284 return MO_CONTINUE_MATCHING;
285 } else {
286 return ROSE_CONTINUE_MATCHING_NO_EXHAUST;
287 }
288}
289
290/**
291 * \brief Deliver the given SOM report to the user callback.
292 *
293 * Assumes all preconditions (bounds, exhaustion etc) have been checked and
294 * that dedupe catchup has been done.
295 */
296static really_inline
297int roseDeliverSomReport(u64a from_offset, u64a to_offset, ReportID onmatch,
298 s32 offset_adjust, struct hs_scratch *scratch,
299 u32 ekey) {
300 assert(scratch);
301 assert(scratch->magic == SCRATCH_MAGIC);
302
303 struct core_info *ci = &scratch->core_info;
304
305 u32 flags = 0;
306#ifndef RELEASE_BUILD
307 if (offset_adjust) {
308 // alert testing tools that we've got adjusted matches
309 flags |= HS_MATCH_FLAG_ADJUSTED;
310 }
311#endif
312
313 assert(!can_stop_matching(scratch));
314 assert(ekey == INVALID_EKEY ||
315 !isExhausted(ci->rose, ci->exhaustionVector, ekey));
316
317 to_offset += offset_adjust;
318 assert(from_offset == HS_OFFSET_PAST_HORIZON || from_offset <= to_offset);
319
320 DEBUG_PRINTF(">> reporting match @[%llu,%llu] for sig %u ctxt %p <<\n",
321 from_offset, to_offset, onmatch, ci->userContext);
322
323 int halt = ci->userCallback(onmatch, from_offset, to_offset, flags,
324 ci->userContext);
325
326 if (halt) {
327 DEBUG_PRINTF("callback requested to terminate matches\n");
328 ci->status |= STATUS_TERMINATED;
329 return MO_HALT_MATCHING;
330 }
331
332 if (ekey != INVALID_EKEY) {
333 markAsMatched(ci->rose, ci->exhaustionVector, ekey);
334 return MO_CONTINUE_MATCHING;
335 } else {
336 return ROSE_CONTINUE_MATCHING_NO_EXHAUST;
337 }
338}
339
340#endif // REPORT_H
341