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