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_QEXACT     (2U << RTE_ACL_TYPE_SHIFT)
  66 #define RTE_ACL_NODE_QRANGE     (3U << RTE_ACL_TYPE_SHIFT)
  67 #define RTE_ACL_NODE_MATCH      (4U << RTE_ACL_TYPE_SHIFT)
  68 #define RTE_ACL_NODE_TYPE       (7U << RTE_ACL_TYPE_SHIFT)
  69 #define RTE_ACL_NODE_UNDEFINED  UINT32_MAX
  70
  71 /*
  72  * Structure of a node is a set of ptrs and each ptr has a bit map
  73  * of values associated with this transition.
  74  */
  75 struct rte_acl_ptr_set {
  76         struct rte_acl_bitset values;   /* input values associated with ptr */
  77         struct rte_acl_node  *ptr;      /* transition to next node */
  78 };
  79
  80 struct rte_acl_classifier_results {
  81         int results[RTE_ACL_MAX_CATEGORIES];
  82 };
  83
  84 struct rte_acl_match_results {
  85         uint32_t results[RTE_ACL_MAX_CATEGORIES];
  86         int32_t priority[RTE_ACL_MAX_CATEGORIES];
  87 };
  88
  89 struct rte_acl_node {
  90         uint64_t node_index;  /* index for this node */
  91         uint32_t level;       /* level 0-n in the trie */
  92         uint32_t ref_count;   /* ref count for this node */
  93         struct rte_acl_bitset  values;
  94         /* set of all values that map to another node
  95          * (union of bits in each transition.
  96          */
  97         uint32_t                num_ptrs; /* number of ptr_set in use */
  98         uint32_t                max_ptrs; /* number of allocated ptr_set */
  99         uint32_t                min_add;  /* number of ptr_set per allocation */
 100         struct rte_acl_ptr_set *ptrs;     /* transitions array for this node */
 101         int32_t                 match_flag;
 102         int32_t                 match_index; /* index to match data */
 103         uint32_t                node_type;
 104         int32_t                 fanout;
 105         /* number of ranges (transitions w/ consecutive bits) */
 106         int32_t                 id;
 107         struct rte_acl_match_results *mrt; /* only valid when match_flag != 0 */
 108         union {
 109                 char            transitions[RTE_ACL_QUAD_SIZE];
 110                 /* boundaries for ranged node */
 111                 uint8_t         dfa_gr64[RTE_ACL_DFA_GR64_NUM];
 112         };
 113         struct rte_acl_node     *next;
 114         /* free list link or pointer to duplicate node during merge */
 115         struct rte_acl_node     *prev;
 116         /* points to node from which this node was duplicated */
 117
 118         uint32_t                subtree_id;
 119         uint32_t                subtree_ref_count;
 120
 121 };
 122 enum {
 123         RTE_ACL_SUBTREE_NODE = 0x80000000
 124 };
 125
 126 /*
 127  * Types of tries used to generate runtime structure(s)
 128  */
 129 enum {
 130         RTE_ACL_FULL_TRIE = 0,
 131         RTE_ACL_NOSRC_TRIE = 1,
 132         RTE_ACL_NODST_TRIE = 2,
 133         RTE_ACL_NOPORTS_TRIE = 4,
 134         RTE_ACL_NOVLAN_TRIE = 8,
 135         RTE_ACL_UNUSED_TRIE = 0x80000000
 136 };
 137
 138
 139 /** MAX number of tries per one ACL context.*/
 140 #define RTE_ACL_MAX_TRIES       8
 141
 142 /** Max number of characters in PM name.*/
 143 #define RTE_ACL_NAMESIZE        32
 144
 145
 146 struct rte_acl_trie {
 147         uint32_t        type;
 148         uint32_t        count;
 149         int32_t         smallest;  /* smallest rule in this trie */
 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, int match_num);
 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 #ifdef __cplusplus
 201 }
 202 #endif /* __cplusplus */
 203
 204 #endif /* _ACL_H_ */