lib/classifier-private.h

   1 /*
   2  * Copyright (c) 2014 Nicira, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #ifndef CLASSIFIER_PRIVATE_H
  18 #define CLASSIFIER_PRIVATE_H 1
  19
  20 #include "cmap.h"
  21 #include "flow.h"
  22 #include "hash.h"
  23 #include "rculist.h"
  24 #include "tag.h"
  25
  26 /* Classifier internal definitions, subject to change at any time. */
  27
  28 /* A set of rules that all have the same fields wildcarded. */
  29 struct cls_subtable {
  30     /* The fields are only used by writers and iterators. */
  31     struct cmap_node cmap_node; /* Within struct classifier 'subtables_map'. */
  32
  33     /* The fields are only used by writers. */
  34     int max_priority OVS_GUARDED;  /* Max priority of any rule in subtable. */
  35     unsigned int max_count OVS_GUARDED;     /* Count of max_priority rules. */
  36
  37     /* Identical, but lower priority rules are not inserted to any of the
  38      * following data structures. */
  39
  40     /* These fields are accessed by readers who care about wildcarding. */
  41     const tag_type tag;       /* Tag generated from mask for partitioning. */
  42     const uint8_t n_indices;                   /* How many indices to use. */
  43     const uint8_t index_ofs[CLS_MAX_INDICES];  /* u32 segment boundaries. */
  44     unsigned int trie_plen[CLS_MAX_TRIES];  /* Trie prefix length in 'mask'
  45                                              * (runtime configurable). */
  46     const int ports_mask_len;
  47     struct cmap indices[CLS_MAX_INDICES];   /* Staged lookup indices. */
  48     rcu_trie_ptr ports_trie;                /* NULL if none. */
  49
  50     /* These fields are accessed by all readers. */
  51     struct cmap rules;                      /* Contains 'cls_match'es. */
  52     const struct minimask mask;             /* Wildcards for fields. */
  53     /* 'mask' must be the last field. */
  54 };
  55
  56 /* Associates a metadata value (that is, a value of the OpenFlow 1.1+ metadata
  57  * field) with tags for the "cls_subtable"s that contain rules that match that
  58  * metadata value.  */
  59 struct cls_partition {
  60     struct cmap_node cmap_node; /* In struct classifier's 'partitions' map. */
  61     ovs_be64 metadata;          /* metadata value for this partition. */
  62     tag_type tags;              /* OR of each flow's cls_subtable tag. */
  63     struct tag_tracker tracker OVS_GUARDED; /* Tracks the bits in 'tags'. */
  64 };
  65
  66 /* Internal representation of a rule in a "struct cls_subtable". */
  67 struct cls_match {
  68     /* Accessed by everybody. */
  69     struct rculist list OVS_GUARDED; /* Identical, lower-priority rules. */
  70
  71     /* Accessed only by writers. */
  72     struct cls_partition *partition OVS_GUARDED;
  73
  74     /* Accessed by readers interested in wildcarding. */
  75     const int priority;         /* Larger numbers are higher priorities. */
  76     struct cmap_node index_nodes[CLS_MAX_INDICES]; /* Within subtable's
  77                                                     * 'indices'. */
  78     /* Accessed by all readers. */
  79     struct cmap_node cmap_node; /* Within struct cls_subtable 'rules'. */
  80     const struct cls_rule *cls_rule;
  81     const struct miniflow flow; /* Matching rule. Mask is in the subtable. */
  82     /* 'flow' must be the last field. */
  83 };
  84
  85 /* A longest-prefix match tree. */
  86 struct trie_node {
  87     uint32_t prefix;           /* Prefix bits for this node, MSB first. */
  88     uint8_t  n_bits;           /* Never zero, except for the root node. */
  89     unsigned int n_rules;      /* Number of rules that have this prefix. */
  90     rcu_trie_ptr edges[2];     /* Both NULL if leaf. */
  91 };
  92
  93 /* Max bits per node.  Must fit in struct trie_node's 'prefix'.
  94  * Also tested with 16, 8, and 5 to stress the implementation. */
  95 #define TRIE_PREFIX_BITS 32
  96 \f
  97 /* flow/miniflow/minimask/minimatch utilities.
  98  * These are only used by the classifier, so place them here to allow
  99  * for better optimization. */
 100
 101 static inline uint64_t
 102 miniflow_get_map_in_range(const struct miniflow *miniflow,
 103                           uint8_t start, uint8_t end, unsigned int *offset)
 104 {
 105     uint64_t map = miniflow->map;
 106     *offset = 0;
 107
 108     if (start > 0) {
 109         uint64_t msk = (UINT64_C(1) << start) - 1; /* 'start' LSBs set */
 110         *offset = count_1bits(map & msk);
 111         map &= ~msk;
 112     }
 113     if (end < FLOW_U32S) {
 114         uint64_t msk = (UINT64_C(1) << end) - 1; /* 'end' LSBs set */
 115         map &= msk;
 116     }
 117     return map;
 118 }
 119
 120 /* Returns a hash value for the bits of 'flow' where there are 1-bits in
 121  * 'mask', given 'basis'.
 122  *
 123  * The hash values returned by this function are the same as those returned by
 124  * miniflow_hash_in_minimask(), only the form of the arguments differ. */
 125 static inline uint32_t
 126 flow_hash_in_minimask(const struct flow *flow, const struct minimask *mask,
 127                       uint32_t basis)
 128 {
 129     const uint32_t *mask_values = miniflow_get_u32_values(&mask->masks);
 130     const uint32_t *flow_u32 = (const uint32_t *)flow;
 131     const uint32_t *p = mask_values;
 132     uint32_t hash;
 133     uint64_t map;
 134
 135     hash = basis;
 136     for (map = mask->masks.map; map; map = zero_rightmost_1bit(map)) {
 137         hash = hash_add(hash, flow_u32[raw_ctz(map)] & *p++);
 138     }
 139
 140     return hash_finish(hash, (p - mask_values) * 4);
 141 }
 142
 143 /* Returns a hash value for the bits of 'flow' where there are 1-bits in
 144  * 'mask', given 'basis'.
 145  *
 146  * The hash values returned by this function are the same as those returned by
 147  * flow_hash_in_minimask(), only the form of the arguments differ. */
 148 static inline uint32_t
 149 miniflow_hash_in_minimask(const struct miniflow *flow,
 150                           const struct minimask *mask, uint32_t basis)
 151 {
 152     const uint32_t *mask_values = miniflow_get_u32_values(&mask->masks);
 153     const uint32_t *p = mask_values;
 154     uint32_t hash = basis;
 155     uint32_t flow_u32;
 156
 157     MINIFLOW_FOR_EACH_IN_MAP(flow_u32, flow, mask->masks.map) {
 158         hash = hash_add(hash, flow_u32 & *p++);
 159     }
 160
 161     return hash_finish(hash, (p - mask_values) * 4);
 162 }
 163
 164 /* Returns a hash value for the bits of range [start, end) in 'flow',
 165  * where there are 1-bits in 'mask', given 'hash'.
 166  *
 167  * The hash values returned by this function are the same as those returned by
 168  * minimatch_hash_range(), only the form of the arguments differ. */
 169 static inline uint32_t
 170 flow_hash_in_minimask_range(const struct flow *flow,
 171                             const struct minimask *mask,
 172                             uint8_t start, uint8_t end, uint32_t *basis)
 173 {
 174     const uint32_t *mask_values = miniflow_get_u32_values(&mask->masks);
 175     const uint32_t *flow_u32 = (const uint32_t *)flow;
 176     unsigned int offset;
 177     uint64_t map = miniflow_get_map_in_range(&mask->masks, start, end,
 178                                              &offset);
 179     const uint32_t *p = mask_values + offset;
 180     uint32_t hash = *basis;
 181
 182     for (; map; map = zero_rightmost_1bit(map)) {
 183         hash = hash_add(hash, flow_u32[raw_ctz(map)] & *p++);
 184     }
 185
 186     *basis = hash; /* Allow continuation from the unfinished value. */
 187     return hash_finish(hash, (p - mask_values) * 4);
 188 }
 189
 190 /* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask. */
 191 static inline void
 192 flow_wildcards_fold_minimask(struct flow_wildcards *wc,
 193                              const struct minimask *mask)
 194 {
 195     flow_union_with_miniflow(&wc->masks, &mask->masks);
 196 }
 197
 198 /* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask
 199  * in range [start, end). */
 200 static inline void
 201 flow_wildcards_fold_minimask_range(struct flow_wildcards *wc,
 202                                    const struct minimask *mask,
 203                                    uint8_t start, uint8_t end)
 204 {
 205     uint32_t *dst_u32 = (uint32_t *)&wc->masks;
 206     unsigned int offset;
 207     uint64_t map = miniflow_get_map_in_range(&mask->masks, start, end,
 208                                              &offset);
 209     const uint32_t *p = miniflow_get_u32_values(&mask->masks) + offset;
 210
 211     for (; map; map = zero_rightmost_1bit(map)) {
 212         dst_u32[raw_ctz(map)] |= *p++;
 213     }
 214 }
 215
 216 /* Returns a hash value for 'flow', given 'basis'. */
 217 static inline uint32_t
 218 miniflow_hash(const struct miniflow *flow, uint32_t basis)
 219 {
 220     const uint32_t *values = miniflow_get_u32_values(flow);
 221     const uint32_t *p = values;
 222     uint32_t hash = basis;
 223     uint64_t hash_map = 0;
 224     uint64_t map;
 225
 226     for (map = flow->map; map; map = zero_rightmost_1bit(map)) {
 227         if (*p) {
 228             hash = hash_add(hash, *p);
 229             hash_map |= rightmost_1bit(map);
 230         }
 231         p++;
 232     }
 233     hash = hash_add(hash, hash_map);
 234     hash = hash_add(hash, hash_map >> 32);
 235
 236     return hash_finish(hash, p - values);
 237 }
 238
 239 /* Returns a hash value for 'mask', given 'basis'. */
 240 static inline uint32_t
 241 minimask_hash(const struct minimask *mask, uint32_t basis)
 242 {
 243     return miniflow_hash(&mask->masks, basis);
 244 }
 245
 246 /* Returns a hash value for 'match', given 'basis'. */
 247 static inline uint32_t
 248 minimatch_hash(const struct minimatch *match, uint32_t basis)
 249 {
 250     return miniflow_hash(&match->flow, minimask_hash(&match->mask, basis));
 251 }
 252
 253 /* Returns a hash value for the bits of range [start, end) in 'minimatch',
 254  * given 'basis'.
 255  *
 256  * The hash values returned by this function are the same as those returned by
 257  * flow_hash_in_minimask_range(), only the form of the arguments differ. */
 258 static inline uint32_t
 259 minimatch_hash_range(const struct minimatch *match, uint8_t start, uint8_t end,
 260                      uint32_t *basis)
 261 {
 262     unsigned int offset;
 263     const uint32_t *p, *q;
 264     uint32_t hash = *basis;
 265     int n, i;
 266
 267     n = count_1bits(miniflow_get_map_in_range(&match->mask.masks, start, end,
 268                                               &offset));
 269     q = miniflow_get_u32_values(&match->mask.masks) + offset;
 270     p = miniflow_get_u32_values(&match->flow) + offset;
 271
 272     for (i = 0; i < n; i++) {
 273         hash = hash_add(hash, p[i] & q[i]);
 274     }
 275     *basis = hash; /* Allow continuation from the unfinished value. */
 276     return hash_finish(hash, (offset + n) * 4);
 277 }
 278
 279 #endif