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 #ifndef _ACL_RUN_H_ 35 #define _ACL_RUN_H_ 36 37 #include <rte_acl.h> 38 #include "acl.h" 39 40 #define MAX_SEARCHES_AVX16 16 41 #define MAX_SEARCHES_SSE8 8 42 #define MAX_SEARCHES_ALTIVEC8 8 43 #define MAX_SEARCHES_SSE4 4 44 #define MAX_SEARCHES_ALTIVEC4 4 45 #define MAX_SEARCHES_SCALAR 2 46 47 #define GET_NEXT_4BYTES(prm, idx) \ 48 (*((const int32_t *)((prm)[(idx)].data + *(prm)[idx].data_index++))) 49 50 51 #define RTE_ACL_NODE_INDEX ((uint32_t)~RTE_ACL_NODE_TYPE) 52 53 #define SCALAR_QRANGE_MULT 0x01010101 54 #define SCALAR_QRANGE_MASK 0x7f7f7f7f 55 #define SCALAR_QRANGE_MIN 0x80808080 56 57 /* 58 * Structure to manage N parallel trie traversals. 59 * The runtime trie traversal routines can process 8, 4, or 2 tries 60 * in parallel. Each packet may require multiple trie traversals (up to 4). 61 * This structure is used to fill the slots (0 to n-1) for parallel processing 62 * with the trie traversals needed for each packet. 63 */ 64 struct acl_flow_data { 65 uint32_t num_packets; 66 /* number of packets processed */ 67 uint32_t started; 68 /* number of trie traversals in progress */ 69 uint32_t trie; 70 /* current trie index (0 to N-1) */ 71 uint32_t cmplt_size; 72 /* maximum number of packets to process */ 73 uint32_t total_packets; 74 /* number of result categories per packet. */ 75 uint32_t categories; 76 const uint64_t *trans; 77 const uint8_t **data; 78 uint32_t *results; 79 struct completion *last_cmplt; 80 struct completion *cmplt_array; 81 }; 82 83 /* 84 * Structure to maintain running results for 85 * a single packet (up to 4 tries). 86 */ 87 struct completion { 88 uint32_t *results; /* running results. */ 89 int32_t priority[RTE_ACL_MAX_CATEGORIES]; /* running priorities. */ 90 uint32_t count; /* num of remaining tries */ 91 /* true for allocated struct */ 92 } __attribute__((aligned(XMM_SIZE))); 93 94 /* 95 * One parms structure for each slot in the search engine. 96 */ 97 struct parms { 98 const uint8_t *data; 99 /* input data for this packet */ 100 const uint32_t *data_index; 101 /* data indirection for this trie */ 102 struct completion *cmplt; 103 /* completion data for this packet */ 104 }; 105 106 /* 107 * Define an global idle node for unused engine slots 108 */ 109 static const uint32_t idle[UINT8_MAX + 1]; 110 111 /* 112 * Allocate a completion structure to manage the tries for a packet. 113 */ 114 static inline struct completion * 115 alloc_completion(struct completion *p, uint32_t size, uint32_t tries, 116 uint32_t *results) 117 { 118 uint32_t n; 119 120 for (n = 0; n < size; n++) { 121 122 if (p[n].count == 0) { 123 124 /* mark as allocated and set number of tries. */ 125 p[n].count = tries; 126 p[n].results = results; 127 return &(p[n]); 128 } 129 } 130 131 /* should never get here */ 132 return NULL; 133 } 134 135 /* 136 * Resolve priority for a single result trie. 137 */ 138 static inline void 139 resolve_single_priority(uint64_t transition, int n, 140 const struct rte_acl_ctx *ctx, struct parms *parms, 141 const struct rte_acl_match_results *p) 142 { 143 if (parms[n].cmplt->count == ctx->num_tries || 144 parms[n].cmplt->priority[0] <= 145 p[transition].priority[0]) { 146 147 parms[n].cmplt->priority[0] = p[transition].priority[0]; 148 parms[n].cmplt->results[0] = p[transition].results[0]; 149 } 150 } 151 152 /* 153 * Routine to fill a slot in the parallel trie traversal array (parms) from 154 * the list of packets (flows). 155 */ 156 static inline uint64_t 157 acl_start_next_trie(struct acl_flow_data *flows, struct parms *parms, int n, 158 const struct rte_acl_ctx *ctx) 159 { 160 uint64_t transition; 161 162 /* if there are any more packets to process */ 163 if (flows->num_packets < flows->total_packets) { 164 parms[n].data = flows->data[flows->num_packets]; 165 parms[n].data_index = ctx->trie[flows->trie].data_index; 166 167 /* if this is the first trie for this packet */ 168 if (flows->trie == 0) { 169 flows->last_cmplt = alloc_completion(flows->cmplt_array, 170 flows->cmplt_size, ctx->num_tries, 171 flows->results + 172 flows->num_packets * flows->categories); 173 } 174 175 /* set completion parameters and starting index for this slot */ 176 parms[n].cmplt = flows->last_cmplt; 177 transition = 178 flows->trans[parms[n].data[*parms[n].data_index++] + 179 ctx->trie[flows->trie].root_index]; 180 181 /* 182 * if this is the last trie for this packet, 183 * then setup next packet. 184 */ 185 flows->trie++; 186 if (flows->trie >= ctx->num_tries) { 187 flows->trie = 0; 188 flows->num_packets++; 189 } 190 191 /* keep track of number of active trie traversals */ 192 flows->started++; 193 194 /* no more tries to process, set slot to an idle position */ 195 } else { 196 transition = ctx->idle; 197 parms[n].data = (const uint8_t *)idle; 198 parms[n].data_index = idle; 199 } 200 return transition; 201 } 202 203 static inline void 204 acl_set_flow(struct acl_flow_data *flows, struct completion *cmplt, 205 uint32_t cmplt_size, const uint8_t **data, uint32_t *results, 206 uint32_t data_num, uint32_t categories, const uint64_t *trans) 207 { 208 flows->num_packets = 0; 209 flows->started = 0; 210 flows->trie = 0; 211 flows->last_cmplt = NULL; 212 flows->cmplt_array = cmplt; 213 flows->total_packets = data_num; 214 flows->categories = categories; 215 flows->cmplt_size = cmplt_size; 216 flows->data = data; 217 flows->results = results; 218 flows->trans = trans; 219 } 220 221 typedef void (*resolve_priority_t) 222 (uint64_t transition, int n, const struct rte_acl_ctx *ctx, 223 struct parms *parms, const struct rte_acl_match_results *p, 224 uint32_t categories); 225 226 /* 227 * Detect matches. If a match node transition is found, then this trie 228 * traversal is complete and fill the slot with the next trie 229 * to be processed. 230 */ 231 static inline uint64_t 232 acl_match_check(uint64_t transition, int slot, 233 const struct rte_acl_ctx *ctx, struct parms *parms, 234 struct acl_flow_data *flows, resolve_priority_t resolve_priority) 235 { 236 const struct rte_acl_match_results *p; 237 238 p = (const struct rte_acl_match_results *) 239 (flows->trans + ctx->match_index); 240 241 if (transition & RTE_ACL_NODE_MATCH) { 242 243 /* Remove flags from index and decrement active traversals */ 244 transition &= RTE_ACL_NODE_INDEX; 245 flows->started--; 246 247 /* Resolve priorities for this trie and running results */ 248 if (flows->categories == 1) 249 resolve_single_priority(transition, slot, ctx, 250 parms, p); 251 else 252 resolve_priority(transition, slot, ctx, parms, 253 p, flows->categories); 254 255 /* Count down completed tries for this search request */ 256 parms[slot].cmplt->count--; 257 258 /* Fill the slot with the next trie or idle trie */ 259 transition = acl_start_next_trie(flows, parms, slot, ctx); 260 } 261 262 return transition; 263 } 264 265 #endif /* _ACL_RUN_H_ */ 266