1/*
2 * Copyright (c) 2015-2016, 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#include "repeat.h"
30#include "util/join.h"
31
32/* impl of limex functions which depend only on state size */
33
34#if !defined(SIZE) || !defined(STATE_T) || !defined(LOAD_FROM_ENG) \
35 || !defined(INLINE_ATTR)
36# error Must define SIZE, STATE_T, LOAD_FROM_ENG and INLINE_ATTR in includer.
37#endif
38
39#define IMPL_NFA_T JOIN(struct LimExNFA, SIZE)
40
41#define TESTEOD_FN JOIN(moNfaTestEod, SIZE)
42#define LIMEX_INACCEPT_FN JOIN(limexInAccept, SIZE)
43#define LIMEX_INANYACCEPT_FN JOIN(limexInAnyAccept, SIZE)
44#define EXPIRE_ESTATE_FN JOIN(limexExpireExtendedState, SIZE)
45#define REPORTCURRENT_FN JOIN(moNfaReportCurrent, SIZE)
46#define INITIAL_FN JOIN(moNfaInitial, SIZE)
47#define TOP_FN JOIN(moNfaTop, SIZE)
48#define TOPN_FN JOIN(moNfaTopN, SIZE)
49#define PROCESS_ACCEPTS_IMPL_FN JOIN(moProcessAcceptsImpl, SIZE)
50#define PROCESS_ACCEPTS_FN JOIN(moProcessAccepts, SIZE)
51#define PROCESS_ACCEPTS_NOSQUASH_FN JOIN(moProcessAcceptsNoSquash, SIZE)
52#define CONTEXT_T JOIN(NFAContext, SIZE)
53#define ONES_STATE JOIN(ones_, STATE_T)
54#define AND_STATE JOIN(and_, STATE_T)
55#define OR_STATE JOIN(or_, STATE_T)
56#define ANDNOT_STATE JOIN(andnot_, STATE_T)
57#define CLEARBIT_STATE JOIN(clearbit_, STATE_T)
58#define TESTBIT_STATE JOIN(testbit_, STATE_T)
59#define ISNONZERO_STATE JOIN(isNonZero_, STATE_T)
60#define ISZERO_STATE JOIN(isZero_, STATE_T)
61#define SQUASH_UNTUG_BR_FN JOIN(lazyTug, SIZE)
62#define GET_NFA_REPEAT_INFO_FN JOIN(getNfaRepeatInfo, SIZE)
63
64#if defined(ARCH_64_BIT) && (SIZE >= 64)
65#define CHUNK_T u64a
66#define FIND_AND_CLEAR_FN findAndClearLSB_64
67#define POPCOUNT_FN popcount64
68#define RANK_IN_MASK_FN rank_in_mask64
69#else
70#define CHUNK_T u32
71#define FIND_AND_CLEAR_FN findAndClearLSB_32
72#define POPCOUNT_FN popcount32
73#define RANK_IN_MASK_FN rank_in_mask32
74#endif
75
76#define NUM_STATE_CHUNKS (sizeof(STATE_T) / sizeof(CHUNK_T))
77
78static really_inline
79void SQUASH_UNTUG_BR_FN(const IMPL_NFA_T *limex,
80 const union RepeatControl *repeat_ctrl,
81 const char *repeat_state, u64a offset,
82 STATE_T *accstate) {
83 // switch off cyclic tug-accepts which aren't tuggable right now.
84
85 /* TODO: might be nice to work which br to examine based on accstate rather
86 * than iterating overall br */
87
88 if (!limex->repeatCount) {
89 return;
90 }
91
92 assert(repeat_ctrl);
93 assert(repeat_state);
94
95 for (u32 i = 0; i < limex->repeatCount; i++) {
96 const struct NFARepeatInfo *info = GET_NFA_REPEAT_INFO_FN(limex, i);
97
98 u32 cyclicState = info->cyclicState;
99 if (!TESTBIT_STATE(*accstate, cyclicState)) {
100 continue;
101 }
102
103 DEBUG_PRINTF("repeat %u (cyclic state %u) is active\n", i, cyclicState);
104 DEBUG_PRINTF("checking if offset %llu would match\n", offset);
105
106 const union RepeatControl *ctrl = repeat_ctrl + i;
107 const char *state = repeat_state + info->stateOffset;
108 const struct RepeatInfo *repeat = getRepeatInfo(info);
109 if (repeatHasMatch(repeat, ctrl, state, offset) != REPEAT_MATCH) {
110 DEBUG_PRINTF("not ready to accept yet\n");
111 CLEARBIT_STATE(accstate, cyclicState);
112 }
113 }
114}
115
116static really_inline
117char PROCESS_ACCEPTS_IMPL_FN(const IMPL_NFA_T *limex, const STATE_T *s,
118 STATE_T *squash, const STATE_T *acceptMask,
119 const struct NFAAccept *acceptTable, u64a offset,
120 NfaCallback callback, void *context) {
121 assert(s);
122 assert(limex);
123 assert(callback);
124
125 const STATE_T accept_mask = *acceptMask;
126 STATE_T accepts = AND_STATE(*s, accept_mask);
127
128 // Caller must ensure that we have at least one accept state on.
129 assert(ISNONZERO_STATE(accepts));
130
131 CHUNK_T chunks[NUM_STATE_CHUNKS];
132 memcpy(chunks, &accepts, sizeof(accepts));
133
134 CHUNK_T mask_chunks[NUM_STATE_CHUNKS];
135 memcpy(mask_chunks, &accept_mask, sizeof(accept_mask));
136
137 u32 base_index = 0; // Cumulative sum of mask popcount up to current chunk.
138 for (u32 i = 0; i < NUM_STATE_CHUNKS; i++) {
139 CHUNK_T chunk = chunks[i];
140 while (chunk != 0) {
141 u32 bit = FIND_AND_CLEAR_FN(&chunk);
142 u32 local_idx = RANK_IN_MASK_FN(mask_chunks[i], bit);
143 u32 idx = local_idx + base_index;
144 const struct NFAAccept *a = &acceptTable[idx];
145 DEBUG_PRINTF("state %u: firing report list=%u, offset=%llu\n",
146 bit + i * (u32)sizeof(chunk) * 8, a->reports, offset);
147 int rv = limexRunAccept((const char *)limex, a, callback, context,
148 offset);
149 if (unlikely(rv == MO_HALT_MATCHING)) {
150 return 1;
151 }
152 if (squash != NULL && a->squash != MO_INVALID_IDX) {
153 DEBUG_PRINTF("applying squash mask at offset %u\n", a->squash);
154 const ENG_STATE_T *sq =
155 (const ENG_STATE_T *)((const char *)limex + a->squash);
156 *squash = AND_STATE(*squash, LOAD_FROM_ENG(sq));
157 }
158 }
159 base_index += POPCOUNT_FN(mask_chunks[i]);
160 }
161
162 return 0;
163}
164
165static never_inline
166char PROCESS_ACCEPTS_FN(const IMPL_NFA_T *limex, STATE_T *s,
167 const STATE_T *acceptMask,
168 const struct NFAAccept *acceptTable, u64a offset,
169 NfaCallback callback, void *context) {
170 // We have squash masks we might have to apply after firing reports.
171 STATE_T squash = ONES_STATE;
172 return PROCESS_ACCEPTS_IMPL_FN(limex, s, &squash, acceptMask, acceptTable,
173 offset, callback, context);
174
175 *s = AND_STATE(*s, squash);
176}
177
178static never_inline
179char PROCESS_ACCEPTS_NOSQUASH_FN(const IMPL_NFA_T *limex, const STATE_T *s,
180 const STATE_T *acceptMask,
181 const struct NFAAccept *acceptTable,
182 u64a offset, NfaCallback callback,
183 void *context) {
184 STATE_T *squash = NULL;
185 return PROCESS_ACCEPTS_IMPL_FN(limex, s, squash, acceptMask, acceptTable,
186 offset, callback, context);
187}
188
189// Run EOD accepts. Note that repeat_ctrl and repeat_state may be NULL if this
190// LimEx contains no repeat structures.
191static really_inline
192char TESTEOD_FN(const IMPL_NFA_T *limex, const STATE_T *s,
193 const union RepeatControl *repeat_ctrl,
194 const char *repeat_state, u64a offset,
195 NfaCallback callback, void *context) {
196 assert(limex && s);
197
198 // There may not be any EOD accepts in this NFA.
199 if (!limex->acceptEodCount) {
200 return MO_CONTINUE_MATCHING;
201 }
202
203 const STATE_T acceptEodMask = LOAD_FROM_ENG(&limex->acceptAtEOD);
204 STATE_T foundAccepts = AND_STATE(*s, acceptEodMask);
205
206 SQUASH_UNTUG_BR_FN(limex, repeat_ctrl, repeat_state,
207 offset + 1 /* EOD 'symbol' */, &foundAccepts);
208
209 if (unlikely(ISNONZERO_STATE(foundAccepts))) {
210 const struct NFAAccept *acceptEodTable = getAcceptEodTable(limex);
211 if (PROCESS_ACCEPTS_NOSQUASH_FN(limex, &foundAccepts, &acceptEodMask,
212 acceptEodTable, offset, callback,
213 context)) {
214 return MO_HALT_MATCHING;
215 }
216 }
217
218 return MO_CONTINUE_MATCHING;
219}
220
221// Run accepts corresponding to current state.
222static really_inline
223char REPORTCURRENT_FN(const IMPL_NFA_T *limex, const struct mq *q) {
224 assert(limex && q);
225 assert(q->state);
226 assert(q_cur_type(q) == MQE_START);
227
228 STATE_T s = *(STATE_T *)q->state;
229 STATE_T acceptMask = LOAD_FROM_ENG(&limex->accept);
230 STATE_T foundAccepts = AND_STATE(s, acceptMask);
231
232 if (unlikely(ISNONZERO_STATE(foundAccepts))) {
233 DEBUG_PRINTF("found accepts\n");
234 DEBUG_PRINTF("for nfa %p\n", limex);
235 const struct NFAAccept *acceptTable = getAcceptTable(limex);
236 u64a offset = q_cur_offset(q);
237
238 if (PROCESS_ACCEPTS_NOSQUASH_FN(limex, &foundAccepts, &acceptMask,
239 acceptTable, offset, q->cb,
240 q->context)) {
241 return MO_HALT_MATCHING;
242 }
243 }
244
245 return MO_CONTINUE_MATCHING;
246}
247
248static really_inline
249STATE_T INITIAL_FN(const IMPL_NFA_T *impl, char onlyDs) {
250 return LOAD_FROM_ENG(onlyDs ? &impl->initDS : &impl->init);
251}
252
253static really_inline
254STATE_T TOP_FN(const IMPL_NFA_T *impl, char onlyDs, STATE_T state) {
255 return OR_STATE(INITIAL_FN(impl, onlyDs), state);
256}
257
258static really_inline
259STATE_T TOPN_FN(const IMPL_NFA_T *limex, STATE_T state, u32 n) {
260 assert(n < limex->topCount);
261 const ENG_STATE_T *topsptr =
262 (const ENG_STATE_T *)((const char *)limex + limex->topOffset);
263 STATE_T top = LOAD_FROM_ENG(&topsptr[n]);
264 return OR_STATE(top, state);
265}
266
267static really_inline
268void EXPIRE_ESTATE_FN(const IMPL_NFA_T *limex, struct CONTEXT_T *ctx,
269 u64a offset) {
270 assert(limex);
271 assert(ctx);
272
273 if (!limex->repeatCount) {
274 return;
275 }
276
277 DEBUG_PRINTF("expire estate at offset %llu\n", offset);
278
279 const STATE_T cyclics
280 = AND_STATE(ctx->s, LOAD_FROM_ENG(&limex->repeatCyclicMask));
281 if (ISZERO_STATE(cyclics)) {
282 DEBUG_PRINTF("no cyclic states are on\n");
283 return;
284 }
285
286 for (u32 i = 0; i < limex->repeatCount; i++) {
287 const struct NFARepeatInfo *info = GET_NFA_REPEAT_INFO_FN(limex, i);
288
289 u32 cyclicState = info->cyclicState;
290 if (!TESTBIT_STATE(cyclics, cyclicState)) {
291 continue;
292 }
293
294 DEBUG_PRINTF("repeat %u (cyclic state %u) is active\n", i,
295 cyclicState);
296
297 const struct RepeatInfo *repeat = getRepeatInfo(info);
298 if (repeat->repeatMax == REPEAT_INF) {
299 continue; // can't expire
300 }
301
302 const union RepeatControl *repeat_ctrl = ctx->repeat_ctrl + i;
303 const char *repeat_state = ctx->repeat_state + info->stateOffset;
304 u64a last_top = repeatLastTop(repeat, repeat_ctrl, repeat_state);
305 assert(repeat->repeatMax < REPEAT_INF);
306 DEBUG_PRINTF("offset %llu, last_top %llu repeatMax %u\n", offset,
307 last_top, repeat->repeatMax);
308 u64a adj = 0;
309 /* if the cycle's tugs are active at repeat max, it is still alive */
310 if (TESTBIT_STATE(LOAD_FROM_ENG(&limex->accept), cyclicState) ||
311 TESTBIT_STATE(LOAD_FROM_ENG(&limex->acceptAtEOD), cyclicState)) {
312 DEBUG_PRINTF("lazy tug possible - may still be inspected\n");
313 adj = 1;
314 } else {
315 const ENG_STATE_T *tug_mask =
316 (const ENG_STATE_T *)((const char *)info + info->tugMaskOffset);
317 if (ISNONZERO_STATE(AND_STATE(ctx->s, LOAD_FROM_ENG(tug_mask)))) {
318 DEBUG_PRINTF("tug possible - may still be inspected\n");
319 adj = 1;
320 }
321 }
322
323 if (offset >= last_top + repeat->repeatMax + adj) {
324 DEBUG_PRINTF("repeat state is stale, squashing state %u\n",
325 cyclicState);
326 CLEARBIT_STATE(&ctx->s, cyclicState);
327 }
328 }
329}
330
331// Specialised inAccept call: LimEx NFAs with the "lazy tug" optimisation (see
332// UE-1636) need to guard cyclic tug-accepts as well.
333static really_inline
334char LIMEX_INACCEPT_FN(const IMPL_NFA_T *limex, STATE_T state,
335 union RepeatControl *repeat_ctrl, char *repeat_state,
336 u64a offset, ReportID report) {
337 assert(limex);
338
339 const STATE_T accept_mask = LOAD_FROM_ENG(&limex->accept);
340 STATE_T accepts = AND_STATE(state, accept_mask);
341
342 // Are we in an accept state?
343 if (ISZERO_STATE(accepts)) {
344 DEBUG_PRINTF("no accept states are on\n");
345 return 0;
346 }
347
348 SQUASH_UNTUG_BR_FN(limex, repeat_ctrl, repeat_state, offset, &accepts);
349
350 DEBUG_PRINTF("looking for report %u\n", report);
351
352 const struct NFAAccept *acceptTable = getAcceptTable(limex);
353
354 CHUNK_T chunks[NUM_STATE_CHUNKS];
355 memcpy(chunks, &accepts, sizeof(accepts));
356
357 CHUNK_T mask_chunks[NUM_STATE_CHUNKS];
358 memcpy(mask_chunks, &accept_mask, sizeof(accept_mask));
359
360 u32 base_index = 0; // Cumulative sum of mask popcount up to current chunk.
361 for (u32 i = 0; i < NUM_STATE_CHUNKS; i++) {
362 CHUNK_T chunk = chunks[i];
363 while (chunk != 0) {
364 u32 bit = FIND_AND_CLEAR_FN(&chunk);
365 u32 local_idx = RANK_IN_MASK_FN(mask_chunks[i], bit);
366 u32 idx = local_idx + base_index;
367 assert(idx < limex->acceptCount);
368 const struct NFAAccept *a = &acceptTable[idx];
369 DEBUG_PRINTF("state %u is on, report list at %u\n",
370 bit + i * (u32)sizeof(chunk) * 8, a->reports);
371
372 if (limexAcceptHasReport((const char *)limex, a, report)) {
373 DEBUG_PRINTF("report %u is on\n", report);
374 return 1;
375 }
376 }
377 base_index += POPCOUNT_FN(mask_chunks[i]);
378 }
379
380 return 0;
381}
382
383static really_inline
384char LIMEX_INANYACCEPT_FN(const IMPL_NFA_T *limex, STATE_T state,
385 union RepeatControl *repeat_ctrl, char *repeat_state,
386 u64a offset) {
387 assert(limex);
388
389 const STATE_T acceptMask = LOAD_FROM_ENG(&limex->accept);
390 STATE_T accstate = AND_STATE(state, acceptMask);
391
392 // Are we in an accept state?
393 if (ISZERO_STATE(accstate)) {
394 DEBUG_PRINTF("no accept states are on\n");
395 return 0;
396 }
397
398 SQUASH_UNTUG_BR_FN(limex, repeat_ctrl, repeat_state, offset, &accstate);
399
400 return ISNONZERO_STATE(accstate);
401}
402
403#undef TESTEOD_FN
404#undef REPORTCURRENT_FN
405#undef EXPIRE_ESTATE_FN
406#undef LIMEX_INACCEPT_FN
407#undef LIMEX_INANYACCEPT_FN
408#undef INITIAL_FN
409#undef TOP_FN
410#undef TOPN_FN
411#undef CONTEXT_T
412#undef IMPL_NFA_T
413#undef ONES_STATE
414#undef AND_STATE
415#undef OR_STATE
416#undef ANDNOT_STATE
417#undef CLEARBIT_STATE
418#undef TESTBIT_STATE
419#undef ISNONZERO_STATE
420#undef ISZERO_STATE
421#undef PROCESS_ACCEPTS_IMPL_FN
422#undef PROCESS_ACCEPTS_FN
423#undef PROCESS_ACCEPTS_NOSQUASH_FN
424#undef SQUASH_UNTUG_BR_FN
425#undef GET_NFA_REPEAT_INFO_FN
426
427#undef CHUNK_T
428#undef FIND_AND_CLEAR_FN
429#undef POPCOUNT_FN
430#undef RANK_IN_MASK_FN
431#undef NUM_STATE_CHUNKS
432