lib/librte_acl/acl.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_H_
  35 #define _ACL_H_
  36
  37 #ifdef __cplusplus
  38 extern"C" {
  39 #endif /* __cplusplus */
  40
  41 #define RTE_ACL_QUAD_MAX        5
  42 #define RTE_ACL_QUAD_SIZE       4
  43 #define RTE_ACL_QUAD_SINGLE     UINT64_C(0x7f7f7f7f00000000)
  44
  45 #define RTE_ACL_SINGLE_TRIE_SIZE        2000
  46
  47 #define RTE_ACL_DFA_MAX         UINT8_MAX
  48 #define RTE_ACL_DFA_SIZE        (UINT8_MAX + 1)
  49
  50 #define RTE_ACL_DFA_GR64_SIZE   64
  51 #define RTE_ACL_DFA_GR64_NUM    (RTE_ACL_DFA_SIZE / RTE_ACL_DFA_GR64_SIZE)
  52 #define RTE_ACL_DFA_GR64_BIT    \
  53         (CHAR_BIT * sizeof(uint32_t) / RTE_ACL_DFA_GR64_NUM)
  54
  55 typedef int bits_t;
  56
  57 #define RTE_ACL_BIT_SET_SIZE    ((UINT8_MAX + 1) / (sizeof(bits_t) * CHAR_BIT))
  58
  59 struct rte_acl_bitset {
  60         bits_t             bits[RTE_ACL_BIT_SET_SIZE];
  61 };
  62
  63 #define RTE_ACL_NODE_DFA        (0 << RTE_ACL_TYPE_SHIFT)
  64 #define RTE_ACL_NODE_SINGLE     (1U << RTE_ACL_TYPE_SHIFT)
  65 #define RTE_ACL_NODE_QRANGE     (3U << RTE_ACL_TYPE_SHIFT)
  66 #define RTE_ACL_NODE_MATCH      (4U << RTE_ACL_TYPE_SHIFT)
  67 #define RTE_ACL_NODE_TYPE       (7U << RTE_ACL_TYPE_SHIFT)
  68 #define RTE_ACL_NODE_UNDEFINED  UINT32_MAX
  69
  70 /*
  71  * ACL RT structure is a set of multibit tries (with stride == 8)
  72  * represented by an array of transitions. The next position is calculated
  73  * based on the current position and the input byte.
  74  * Each transition is 64 bit value with the following format:
  75  * | node_type_specific : 32 | node_type : 3 | node_addr : 29 |
  76  * For all node types except RTE_ACL_NODE_MATCH, node_addr is an index
  77  * to the start of the node in the transtions array.
  78  * Few different node types are used:
  79  * RTE_ACL_NODE_MATCH:
  80  * node_addr value is and index into an array that contains the return value
  81  * and its priority for each category.
  82  * Upper 32 bits of the transition value are not used for that node type.
  83  * RTE_ACL_NODE_QRANGE:
  84  * that node consist of up to 5 transitions.
  85  * Upper 32 bits are interpreted as 4 signed character values which
  86  * are ordered from smallest(INT8_MIN) to largest (INT8_MAX).
  87  * These values define 5 ranges:
  88  * INT8_MIN <= range[0]  <= ((int8_t *)&transition)[4]
  89  * ((int8_t *)&transition)[4] < range[1] <= ((int8_t *)&transition)[5]
  90  * ((int8_t *)&transition)[5] < range[2] <= ((int8_t *)&transition)[6]
  91  * ((int8_t *)&transition)[6] < range[3] <= ((int8_t *)&transition)[7]
  92  * ((int8_t *)&transition)[7] < range[4] <= INT8_MAX
  93  * So for input byte value within range[i] i-th transition within that node
  94  * will be used.
  95  * RTE_ACL_NODE_SINGLE:
  96  * always transitions to the same node regardless of the input value.
  97  * RTE_ACL_NODE_DFA:
  98  * that node consits of up to 256 transitions.
  99  * In attempt to conserve space all transitions are divided into 4 consecutive
 100  * groups, by 64 transitions per group:
 101  * group64[i] contains transitions[i * 64, .. i * 64 + 63].
 102  * Upper 32 bits are interpreted as 4 unsigned character values one per group,
 103  * which contain index to the start of the given group within the node.
 104  * So to calculate transition index within the node for given input byte value:
 105  * input_byte - ((uint8_t *)&transition)[4 + input_byte / 64].
 106  */
 107
 108 /*
 109  * Structure of a node is a set of ptrs and each ptr has a bit map
 110  * of values associated with this transition.
 111  */
 112 struct rte_acl_ptr_set {
 113         struct rte_acl_bitset values;   /* input values associated with ptr */
 114         struct rte_acl_node  *ptr;      /* transition to next node */
 115 };
 116
 117 struct rte_acl_classifier_results {
 118         int results[RTE_ACL_MAX_CATEGORIES];
 119 };
 120
 121 struct rte_acl_match_results {
 122         uint32_t results[RTE_ACL_MAX_CATEGORIES];
 123         int32_t priority[RTE_ACL_MAX_CATEGORIES];
 124 };
 125
 126 struct rte_acl_node {
 127         uint64_t node_index;  /* index for this node */
 128         uint32_t level;       /* level 0-n in the trie */
 129         uint32_t ref_count;   /* ref count for this node */
 130         struct rte_acl_bitset  values;
 131         /* set of all values that map to another node
 132          * (union of bits in each transition.
 133          */
 134         uint32_t                num_ptrs; /* number of ptr_set in use */
 135         uint32_t                max_ptrs; /* number of allocated ptr_set */
 136         uint32_t                min_add;  /* number of ptr_set per allocation */
 137         struct rte_acl_ptr_set *ptrs;     /* transitions array for this node */
 138         int32_t                 match_flag;
 139         int32_t                 match_index; /* index to match data */
 140         uint32_t                node_type;
 141         int32_t                 fanout;
 142         /* number of ranges (transitions w/ consecutive bits) */
 143         int32_t                 id;
 144         struct rte_acl_match_results *mrt; /* only valid when match_flag != 0 */
 145         union {
 146                 char            transitions[RTE_ACL_QUAD_SIZE];
 147                 /* boundaries for ranged node */
 148                 uint8_t         dfa_gr64[RTE_ACL_DFA_GR64_NUM];
 149         };
 150         struct rte_acl_node     *next;
 151         /* free list link or pointer to duplicate node during merge */
 152         struct rte_acl_node     *prev;
 153         /* points to node from which this node was duplicated */
 154 };
 155
 156 /*
 157  * Types of tries used to generate runtime structure(s)
 158  */
 159 enum {
 160         RTE_ACL_FULL_TRIE = 0,
 161         RTE_ACL_NOSRC_TRIE = 1,
 162         RTE_ACL_NODST_TRIE = 2,
 163         RTE_ACL_NOPORTS_TRIE = 4,
 164         RTE_ACL_NOVLAN_TRIE = 8,
 165         RTE_ACL_UNUSED_TRIE = 0x80000000
 166 };
 167
 168
 169 /** MAX number of tries per one ACL context.*/
 170 #define RTE_ACL_MAX_TRIES       8
 171
 172 /** Max number of characters in PM name.*/
 173 #define RTE_ACL_NAMESIZE        32
 174
 175
 176 struct rte_acl_trie {
 177         uint32_t        type;
 178         uint32_t        count;
 179         uint32_t        root_index;
 180         const uint32_t *data_index;
 181         uint32_t        num_data_indexes;
 182 };
 183
 184 struct rte_acl_bld_trie {
 185         struct rte_acl_node *trie;
 186 };
 187
 188 struct rte_acl_ctx {
 189         char                name[RTE_ACL_NAMESIZE];
 190         /** Name of the ACL context. */
 191         int32_t             socket_id;
 192         /** Socket ID to allocate memory from. */
 193         enum rte_acl_classify_alg alg;
 194         void               *rules;
 195         uint32_t            max_rules;
 196         uint32_t            rule_sz;
 197         uint32_t            num_rules;
 198         uint32_t            num_categories;
 199         uint32_t            num_tries;
 200         uint32_t            match_index;
 201         uint64_t            no_match;
 202         uint64_t            idle;
 203         uint64_t           *trans_table;
 204         uint32_t           *data_indexes;
 205         struct rte_acl_trie trie[RTE_ACL_MAX_TRIES];
 206         void               *mem;
 207         size_t              mem_sz;
 208         struct rte_acl_config config; /* copy of build config. */
 209 };
 210
 211 int rte_acl_gen(struct rte_acl_ctx *ctx, struct rte_acl_trie *trie,
 212         struct rte_acl_bld_trie *node_bld_trie, uint32_t num_tries,
 213         uint32_t num_categories, uint32_t data_index_sz, size_t max_size);
 214
 215 typedef int (*rte_acl_classify_t)
 216 (const struct rte_acl_ctx *, const uint8_t **, uint32_t *, uint32_t, uint32_t);
 217
 218 /*
 219  * Different implementations of ACL classify.
 220  */
 221 int
 222 rte_acl_classify_scalar(const struct rte_acl_ctx *ctx, const uint8_t **data,
 223         uint32_t *results, uint32_t num, uint32_t categories);
 224
 225 int
 226 rte_acl_classify_sse(const struct rte_acl_ctx *ctx, const uint8_t **data,
 227         uint32_t *results, uint32_t num, uint32_t categories);
 228
 229 int
 230 rte_acl_classify_avx2(const struct rte_acl_ctx *ctx, const uint8_t **data,
 231         uint32_t *results, uint32_t num, uint32_t categories);
 232
 233 #ifdef __cplusplus
 234 }
 235 #endif /* __cplusplus */
 236
 237 #endif /* _ACL_H_ */