lib/librte_acl/acl.h

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