lib/librte_acl/acl_run.h

   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         uint32_t            total_packets;
  73         uint32_t            categories;
  74         /* number of result categories per packet. */
  75         /* maximum number of packets to process */
  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_ */