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