1/*-
2 *   BSD LICENSE
3 *
4 *   Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
5 *   All rights reserved.
6 *
7 *   Redistribution and use in source and binary forms, with or without
8 *   modification, are permitted provided that the following conditions
9 *   are met:
10 *
11 *     * Redistributions of source code must retain the above copyright
12 *       notice, this list of conditions and the following disclaimer.
13 *     * Redistributions in binary form must reproduce the above copyright
14 *       notice, this list of conditions and the following disclaimer in
15 *       the documentation and/or other materials provided with the
16 *       distribution.
17 *     * Neither the name of Intel Corporation nor the names of its
18 *       contributors may be used to endorse or promote products derived
19 *       from this software without specific prior written permission.
20 *
21 *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27 *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28 *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29 *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30 *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31 *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 */
33
34#include "acl_run.h"
35
36/*
37 * Resolve priority for multiple results (scalar version).
38 * This consists comparing the priority of the current traversal with the
39 * running set of results for the packet.
40 * For each result, keep a running array of the result (rule number) and
41 * its priority for each category.
42 */
43static inline void
44resolve_priority_scalar(uint64_t transition, int n,
45	const struct rte_acl_ctx *ctx, struct parms *parms,
46	const struct rte_acl_match_results *p, uint32_t categories)
47{
48	uint32_t i;
49	int32_t *saved_priority;
50	uint32_t *saved_results;
51	const int32_t *priority;
52	const uint32_t *results;
53
54	saved_results = parms[n].cmplt->results;
55	saved_priority = parms[n].cmplt->priority;
56
57	/* results and priorities for completed trie */
58	results = p[transition].results;
59	priority = p[transition].priority;
60
61	/* if this is not the first completed trie */
62	if (parms[n].cmplt->count != ctx->num_tries) {
63		for (i = 0; i < categories; i += RTE_ACL_RESULTS_MULTIPLIER) {
64
65			if (saved_priority[i] <= priority[i]) {
66				saved_priority[i] = priority[i];
67				saved_results[i] = results[i];
68			}
69			if (saved_priority[i + 1] <= priority[i + 1]) {
70				saved_priority[i + 1] = priority[i + 1];
71				saved_results[i + 1] = results[i + 1];
72			}
73			if (saved_priority[i + 2] <= priority[i + 2]) {
74				saved_priority[i + 2] = priority[i + 2];
75				saved_results[i + 2] = results[i + 2];
76			}
77			if (saved_priority[i + 3] <= priority[i + 3]) {
78				saved_priority[i + 3] = priority[i + 3];
79				saved_results[i + 3] = results[i + 3];
80			}
81		}
82	} else {
83		for (i = 0; i < categories; i += RTE_ACL_RESULTS_MULTIPLIER) {
84			saved_priority[i] = priority[i];
85			saved_priority[i + 1] = priority[i + 1];
86			saved_priority[i + 2] = priority[i + 2];
87			saved_priority[i + 3] = priority[i + 3];
88
89			saved_results[i] = results[i];
90			saved_results[i + 1] = results[i + 1];
91			saved_results[i + 2] = results[i + 2];
92			saved_results[i + 3] = results[i + 3];
93		}
94	}
95}
96
97static inline uint32_t
98scan_forward(uint32_t input, uint32_t max)
99{
100	return (input == 0) ? max : rte_bsf32(input);
101}
102
103static inline uint64_t
104scalar_transition(const uint64_t *trans_table, uint64_t transition,
105	uint8_t input)
106{
107	uint32_t addr, index, ranges, x, a, b, c;
108
109	/* break transition into component parts */
110	ranges = transition >> (sizeof(index) * CHAR_BIT);
111	index = transition & ~RTE_ACL_NODE_INDEX;
112	addr = transition ^ index;
113
114	if (index != RTE_ACL_NODE_DFA) {
115		/* calc address for a QRANGE/SINGLE node */
116		c = (uint32_t)input * SCALAR_QRANGE_MULT;
117		a = ranges | SCALAR_QRANGE_MIN;
118		a -= (c & SCALAR_QRANGE_MASK);
119		b = c & SCALAR_QRANGE_MIN;
120		a &= SCALAR_QRANGE_MIN;
121		a ^= (ranges ^ b) & (a ^ b);
122		x = scan_forward(a, 32) >> 3;
123	} else {
124		/* calc address for a DFA node */
125		x = ranges >> (input /
126			RTE_ACL_DFA_GR64_SIZE * RTE_ACL_DFA_GR64_BIT);
127		x &= UINT8_MAX;
128		x = input - x;
129	}
130
131	addr += x;
132
133	/* pickup next transition */
134	transition = *(trans_table + addr);
135	return transition;
136}
137
138int
139rte_acl_classify_scalar(const struct rte_acl_ctx *ctx, const uint8_t **data,
140	uint32_t *results, uint32_t num, uint32_t categories)
141{
142	int n;
143	uint64_t transition0, transition1;
144	uint32_t input0, input1;
145	struct acl_flow_data flows;
146	uint64_t index_array[MAX_SEARCHES_SCALAR];
147	struct completion cmplt[MAX_SEARCHES_SCALAR];
148	struct parms parms[MAX_SEARCHES_SCALAR];
149
150	acl_set_flow(&flows, cmplt, RTE_DIM(cmplt), data, results, num,
151		categories, ctx->trans_table);
152
153	for (n = 0; n < MAX_SEARCHES_SCALAR; n++) {
154		cmplt[n].count = 0;
155		index_array[n] = acl_start_next_trie(&flows, parms, n, ctx);
156	}
157
158	transition0 = index_array[0];
159	transition1 = index_array[1];
160
161	while ((transition0 | transition1) & RTE_ACL_NODE_MATCH) {
162		transition0 = acl_match_check(transition0,
163			0, ctx, parms, &flows, resolve_priority_scalar);
164		transition1 = acl_match_check(transition1,
165			1, ctx, parms, &flows, resolve_priority_scalar);
166	}
167
168	while (flows.started > 0) {
169
170		input0 = GET_NEXT_4BYTES(parms, 0);
171		input1 = GET_NEXT_4BYTES(parms, 1);
172
173		for (n = 0; n < 4; n++) {
174
175			transition0 = scalar_transition(flows.trans,
176				transition0, (uint8_t)input0);
177			input0 >>= CHAR_BIT;
178
179			transition1 = scalar_transition(flows.trans,
180				transition1, (uint8_t)input1);
181			input1 >>= CHAR_BIT;
182		}
183
184		while ((transition0 | transition1) & RTE_ACL_NODE_MATCH) {
185			transition0 = acl_match_check(transition0,
186				0, ctx, parms, &flows, resolve_priority_scalar);
187			transition1 = acl_match_check(transition1,
188				1, ctx, parms, &flows, resolve_priority_scalar);
189		}
190	}
191	return 0;
192}
193