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