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 #ifndef INFIX_H
30 #define INFIX_H
31
32 #include "ue2common.h"
33 #include "nfa/nfa_api.h"
34 #include "nfa/nfa_api_queue.h"
35 #include "nfa/nfa_internal.h"
36
37 static really_inline
infixTooOld(struct mq * q,s64a curr_loc)38 int infixTooOld(struct mq *q, s64a curr_loc) {
39 u32 maxAge = q->nfa->maxWidth;
40
41 if (!maxAge) {
42 return 0;
43 }
44
45 return q_last_loc(q) + maxAge < curr_loc;
46 }
47
48 static really_inline
canReduceQueue(const struct mq * q,s64a curr_loc,u32 maxTops,u32 maxAge)49 int canReduceQueue(const struct mq *q, s64a curr_loc, u32 maxTops, u32 maxAge) {
50 u32 qlen = q->end - q->cur; /* includes MQE_START */
51
52 if (maxAge && q->items[q->cur].location + maxAge < curr_loc) {
53 return 1;
54 }
55
56 if (qlen - 1 > maxTops) {
57 return 1;
58 }
59
60 if (qlen - 1 == maxTops
61 && q->items[q->cur].location != q->items[q->cur + 1].location) {
62 /* we can advance start to the first top location */
63 return 1;
64 }
65
66 return 0;
67 }
68
69 /**
70 * Removes tops which are known not to affect the final state from the queue.
71 * May also reinitialise the engine state if it is unneeded.
72 *
73 * maxAge is the maximum width of the infix. Any tops/state before this can be
74 * ignored. 0 is used to indicate that there is no upper bound on the width of
75 * the pattern.
76 *
77 * maxTops is the maximum number of locations of tops that can affect the top.
78 * It is only possible for the last maxTops tops to affect the final state -
79 * earlier ones can be safely removed. Also, any state before the max tops may
80 * be ignored.
81 *
82 * This code assumes/requires that there are not multiple tops at the same
83 * location in the queue. This code also assumes that it is not a multitop
84 * engine.
85 */
86 static really_inline
reduceInfixQueue(struct mq * q,s64a curr_loc,u32 maxTops,u32 maxAge)87 void reduceInfixQueue(struct mq *q, s64a curr_loc, u32 maxTops, u32 maxAge) {
88 assert(q->end > q->cur);
89 assert(maxTops);
90 u32 qlen = q->end - q->cur; /* includes MQE_START */
91 DEBUG_PRINTF("q=%p, len=%u, maxTops=%u maxAge=%u\n", q, qlen, maxTops,
92 maxAge);
93
94 if (!canReduceQueue(q, curr_loc, maxTops, maxAge)) {
95 DEBUG_PRINTF("nothing to do\n");
96 return;
97 }
98
99 #ifdef DEBUG
100 debugQueue(q);
101 #endif
102
103 char drop_state = qlen - 1 >= maxTops
104 || (maxAge && q->items[q->cur].location + maxAge < curr_loc);
105
106 LIMIT_TO_AT_MOST(&maxTops, qlen - 1);
107
108 // We leave our START where it is, at the front of the queue.
109 assert(q->items[q->cur].type == MQE_START);
110
111 // We want to shuffle maxQueueLen items from the end of the queue to just
112 // after the start, effectively dequeuing old items. We could use memmove
113 // for this, but it's probably not a good idea to take the cost of the
114 // function call.
115 const struct mq_item *src = &q->items[q->cur + qlen - maxTops];
116
117 q->items[0] = q->items[q->cur]; /* shift start event to 0 slot */
118 q->cur = 0;
119 q->end = 1;
120 struct mq_item *dst = &q->items[1];
121 u32 i = 0;
122 if (maxAge) {
123 /* any event which is older than maxAge can be dropped */
124 for (; i < maxTops; i++, src++) {
125 if (src->location >= curr_loc - maxAge) {
126 break;
127 }
128 }
129 }
130
131 for (; i < maxTops; i++) {
132 *dst = *src;
133 src++;
134 dst++;
135 q->end++;
136 }
137
138 if (drop_state) {
139 /* clear state and shift start up to first top */
140 s64a new_loc;
141 if (q->end > 1) {
142 new_loc = q->items[1].location;
143 } else {
144 DEBUG_PRINTF("no tops\n");
145 new_loc = curr_loc;
146 }
147
148 DEBUG_PRINTF("advancing start from %lld to %lld\n",
149 q->items[0].location, new_loc);
150 assert(new_loc > q->items[0].location);
151 q->items[0].location = new_loc;
152 nfaQueueInitState(q->nfa, q);
153 }
154
155 DEBUG_PRINTF("reduced queue to len=%u\n", q->end - q->cur);
156 #ifdef DEBUG
157 debugQueue(q);
158 #endif
159 }
160
161 #endif
162