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  * Each ACL RT contains an idle nomatch node:
  81  * a SINGLE node at predefined position (RTE_ACL_DFA_SIZE)
  82  * that points to itself.
  83  */
  84 #define RTE_ACL_IDLE_NODE       (RTE_ACL_DFA_SIZE | RTE_ACL_NODE_SINGLE)
  85
  86 /*
  87  * Structure of a node is a set of ptrs and each ptr has a bit map
  88  * of values associated with this transition.
  89  */
  90 struct rte_acl_ptr_set {
  91         struct rte_acl_bitset values;   /* input values associated with ptr */
  92         struct rte_acl_node  *ptr;      /* transition to next node */
  93 };
  94
  95 struct rte_acl_classifier_results {
  96         int results[RTE_ACL_MAX_CATEGORIES];
  97 };
  98
  99 struct rte_acl_match_results {
 100         uint32_t results[RTE_ACL_MAX_CATEGORIES];
 101         int32_t priority[RTE_ACL_MAX_CATEGORIES];
 102 };
 103
 104 struct rte_acl_node {
 105         uint64_t node_index;  /* index for this node */
 106         uint32_t level;       /* level 0-n in the trie */
 107         uint32_t ref_count;   /* ref count for this node */
 108         struct rte_acl_bitset  values;
 109         /* set of all values that map to another node
 110          * (union of bits in each transition.
 111          */
 112         uint32_t                num_ptrs; /* number of ptr_set in use */
 113         uint32_t                max_ptrs; /* number of allocated ptr_set */
 114         uint32_t                min_add;  /* number of ptr_set per allocation */
 115         struct rte_acl_ptr_set *ptrs;     /* transitions array for this node */
 116         int32_t                 match_flag;
 117         int32_t                 match_index; /* index to match data */
 118         uint32_t                node_type;
 119         int32_t                 fanout;
 120         /* number of ranges (transitions w/ consecutive bits) */
 121         int32_t                 id;
 122         struct rte_acl_match_results *mrt; /* only valid when match_flag != 0 */
 123         union {
 124                 char            transitions[RTE_ACL_QUAD_SIZE];
 125                 /* boundaries for ranged node */
 126                 uint8_t         dfa_gr64[RTE_ACL_DFA_GR64_NUM];
 127         };
 128         struct rte_acl_node     *next;
 129         /* free list link or pointer to duplicate node during merge */
 130         struct rte_acl_node     *prev;
 131         /* points to node from which this node was duplicated */
 132 };
 133
 134 /*
 135  * Types of tries used to generate runtime structure(s)
 136  */
 137 enum {
 138         RTE_ACL_FULL_TRIE = 0,
 139         RTE_ACL_NOSRC_TRIE = 1,
 140         RTE_ACL_NODST_TRIE = 2,
 141         RTE_ACL_NOPORTS_TRIE = 4,
 142         RTE_ACL_NOVLAN_TRIE = 8,
 143         RTE_ACL_UNUSED_TRIE = 0x80000000
 144 };
 145
 146
 147 /** MAX number of tries per one ACL context.*/
 148 #define RTE_ACL_MAX_TRIES       8
 149
 150 /** Max number of characters in PM name.*/
 151 #define RTE_ACL_NAMESIZE        32
 152
 153
 154 struct rte_acl_trie {
 155         uint32_t        type;
 156         uint32_t        count;
 157         uint32_t        root_index;
 158         const uint32_t *data_index;
 159         uint32_t        num_data_indexes;
 160 };
 161
 162 struct rte_acl_bld_trie {
 163         struct rte_acl_node *trie;
 164 };
 165
 166 struct rte_acl_ctx {
 167         char                name[RTE_ACL_NAMESIZE];
 168         /** Name of the ACL context. */
 169         int32_t             socket_id;
 170         /** Socket ID to allocate memory from. */
 171         enum rte_acl_classify_alg alg;
 172         void               *rules;
 173         uint32_t            max_rules;
 174         uint32_t            rule_sz;
 175         uint32_t            num_rules;
 176         uint32_t            num_categories;
 177         uint32_t            num_tries;
 178         uint32_t            match_index;
 179         uint64_t            no_match;
 180         uint64_t            idle;
 181         uint64_t           *trans_table;
 182         uint32_t           *data_indexes;
 183         struct rte_acl_trie trie[RTE_ACL_MAX_TRIES];
 184         void               *mem;
 185         size_t              mem_sz;
 186         struct rte_acl_config config; /* copy of build config. */
 187 };
 188
 189 int rte_acl_gen(struct rte_acl_ctx *ctx, struct rte_acl_trie *trie,
 190         struct rte_acl_bld_trie *node_bld_trie, uint32_t num_tries,
 191         uint32_t num_categories, uint32_t data_index_sz, size_t max_size);
 192
 193 typedef int (*rte_acl_classify_t)
 194 (const struct rte_acl_ctx *, const uint8_t **, uint32_t *, uint32_t, uint32_t);
 195
 196 /*
 197  * Different implementations of ACL classify.
 198  */
 199 int
 200 rte_acl_classify_scalar(const struct rte_acl_ctx *ctx, const uint8_t **data,
 201         uint32_t *results, uint32_t num, uint32_t categories);
 202
 203 int
 204 rte_acl_classify_sse(const struct rte_acl_ctx *ctx, const uint8_t **data,
 205         uint32_t *results, uint32_t num, uint32_t categories);
 206
 207 int
 208 rte_acl_classify_avx2(const struct rte_acl_ctx *ctx, const uint8_t **data,
 209         uint32_t *results, uint32_t num, uint32_t categories);
 210
 211 int
 212 rte_acl_classify_avx512x16(const struct rte_acl_ctx *ctx, const uint8_t **data,
 213         uint32_t *results, uint32_t num, uint32_t categories);
 214
 215 int
 216 rte_acl_classify_avx512x32(const struct rte_acl_ctx *ctx, const uint8_t **data,
 217         uint32_t *results, uint32_t num, uint32_t categories);
 218
 219 int
 220 rte_acl_classify_neon(const struct rte_acl_ctx *ctx, const uint8_t **data,
 221         uint32_t *results, uint32_t num, uint32_t categories);
 222
 223 int
 224 rte_acl_classify_altivec(const struct rte_acl_ctx *ctx, const uint8_t **data,
 225         uint32_t *results, uint32_t num, uint32_t categories);
 226
 227 #ifdef __cplusplus
 228 }
 229 #endif /* __cplusplus */
 230
 231 #endif /* _ACL_H_ */