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