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