lib/classifier-private.h

   1 /*
   2  * Copyright (c) 2014, 2015 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     struct cmap_node cmap_node;    /* Within classifier's 'subtables_map'. */
  31
  32     /* These fields are only used by writers. */
  33     int max_priority;              /* Max priority of any rule in subtable. */
  34     unsigned int max_count;        /* Count of max_priority rules. */
  35
  36     /* Accessed by iterators. */
  37     struct rculist rules_list;              /* Unordered. */
  38
  39     /* Identical, but lower priority rules are not inserted to any of the
  40      * following data structures. */
  41
  42     /* These fields are accessed by readers who care about wildcarding. */
  43     const tag_type tag;       /* Tag generated from mask for partitioning. */
  44     const uint8_t n_indices;                   /* How many indices to use. */
  45     const uint8_t index_ofs[CLS_MAX_INDICES];  /* u64 segment boundaries. */
  46     unsigned int trie_plen[CLS_MAX_TRIES];  /* Trie prefix length in 'mask'
  47                                              * (runtime configurable). */
  48     const int ports_mask_len;
  49     struct cmap indices[CLS_MAX_INDICES];   /* Staged lookup indices. */
  50     rcu_trie_ptr ports_trie;                /* NULL if none. */
  51
  52     /* These fields are accessed by all readers. */
  53     struct cmap rules;                      /* Contains 'cls_match'es. */
  54     const struct minimask mask;             /* Wildcards for fields. */
  55     /* 'mask' must be the last field. */
  56 };
  57
  58 /* Associates a metadata value (that is, a value of the OpenFlow 1.1+ metadata
  59  * field) with tags for the "cls_subtable"s that contain rules that match that
  60  * metadata value.  */
  61 struct cls_partition {
  62     struct cmap_node cmap_node; /* In struct classifier's 'partitions' map. */
  63     ovs_be64 metadata;          /* metadata value for this partition. */
  64     tag_type tags;              /* OR of each flow's cls_subtable tag. */
  65     struct tag_tracker tracker; /* Tracks the bits in 'tags'. */
  66 };
  67
  68 /* Internal representation of a rule in a "struct cls_subtable".
  69  *
  70  * The 'next' member is an element in a singly linked, null-terminated list.
  71  * This list links together identical "cls_match"es in order of decreasing
  72  * priority.  The classifier code maintains the invariant that at most one rule
  73  * of a given priority is visible for any given lookup version.
  74  */
  75 struct cls_match {
  76     /* Accessed by everybody. */
  77     OVSRCU_TYPE(struct cls_match *) next; /* Equal, lower-priority matches. */
  78     OVSRCU_TYPE(struct cls_conjunction_set *) conj_set;
  79
  80     /* Accessed only by writers. */
  81     struct cls_partition *partition;
  82
  83     /* Accessed by readers interested in wildcarding. */
  84     const int priority;         /* Larger numbers are higher priorities. */
  85     struct cmap_node index_nodes[CLS_MAX_INDICES]; /* Within subtable's
  86                                                     * 'indices'. */
  87     /* Accessed by all readers. */
  88     struct cmap_node cmap_node; /* Within struct cls_subtable 'rules'. */
  89
  90     /* Controls rule's visibility to lookups.
  91      *
  92      * When 'visibility' is:
  93      *
  94      * > 0  - rule is visible starting from version 'visibility'
  95      * <= 0 - rule is invisible starting from version '-(visibility)'
  96      *
  97      * The minimum version number used in lookups is 1 (== CLS_NO_VERSION),
  98      * which implies that when 'visibility' is:
  99      *
 100      * 1    - rule is visible in all lookup versions
 101      * 0    - rule is invisible in all lookup versions. */
 102     atomic_llong visibility;
 103
 104     const struct cls_rule *cls_rule;
 105     const struct miniflow flow; /* Matching rule. Mask is in the subtable. */
 106     /* 'flow' must be the last field. */
 107 };
 108
 109 /* Must be RCU postponed. */
 110 void cls_match_free_cb(struct cls_match *);
 111
 112 static inline void
 113 cls_match_set_visibility(struct cls_match *rule, long long version)
 114 {
 115     atomic_store_relaxed(&rule->visibility, version);
 116 }
 117
 118 static inline bool
 119 cls_match_visible_in_version(const struct cls_match *rule, long long version)
 120 {
 121     long long visibility;
 122
 123     /* C11 does not want to access an atomic via a const object pointer. */
 124     atomic_read_relaxed(&CONST_CAST(struct cls_match *, rule)->visibility,
 125                         &visibility);
 126
 127     if (OVS_LIKELY(visibility > 0)) {
 128         /* Rule is visible starting from version 'visibility'. */
 129         return version >= visibility;
 130     } else {
 131         /* Rule is invisible starting from version '-visibility'. */
 132         return version < -visibility;
 133     }
 134 }
 135
 136 static inline bool
 137 cls_match_is_eventually_invisible(const struct cls_match *rule)
 138 {
 139     long long visibility;
 140
 141     /* C11 does not want to access an atomic via a const object pointer. */
 142     atomic_read_relaxed(&CONST_CAST(struct cls_match *, rule)->visibility,
 143                         &visibility);
 144
 145     return visibility <= 0;
 146 }
 147
 148 \f
 149 /* cls_match 'next' */
 150
 151 static inline const struct cls_match *
 152 cls_match_next(const struct cls_match *rule)
 153 {
 154     return ovsrcu_get(struct cls_match *, &rule->next);
 155 }
 156
 157 static inline struct cls_match *
 158 cls_match_next_protected(const struct cls_match *rule)
 159 {
 160     return ovsrcu_get_protected(struct cls_match *, &rule->next);
 161 }
 162
 163 /* Puts 'rule' in the position between 'prev' and 'next'.  If 'prev' == NULL,
 164  * then the 'rule' is the new list head, and if 'next' == NULL, the rule is the
 165  * new list tail.
 166  * If there are any nodes between 'prev' and 'next', they are dropped from the
 167  * list. */
 168 static inline void
 169 cls_match_insert(struct cls_match *prev, struct cls_match *next,
 170                  struct cls_match *rule)
 171 {
 172     ovsrcu_set_hidden(&rule->next, next);
 173
 174     if (prev) {
 175         ovsrcu_set(&prev->next, rule);
 176     }
 177 }
 178
 179 /* Puts 'new_rule' in the position of 'old_rule', which is the next node after
 180  * 'prev'. If 'prev' == NULL, then the 'new_rule' is the new list head.
 181  *
 182  * The replaced cls_match still links to the later rules, and may still be
 183  * referenced by other threads until all other threads quiesce.  The replaced
 184  * rule may not be re-inserted, re-initialized, or deleted until after all
 185  * other threads have quiesced (use ovsrcu_postpone). */
 186 static inline void
 187 cls_match_replace(struct cls_match *prev,
 188                   struct cls_match *old_rule, struct cls_match *new_rule)
 189 {
 190     cls_match_insert(prev, cls_match_next_protected(old_rule), new_rule);
 191 }
 192
 193 /* Removes 'rule' following 'prev' from the list. If 'prev' is NULL, then the
 194  * 'rule' is a list head, and the caller is responsible for maintaining its
 195  * list head pointer (if any).
 196  *
 197  * Afterward, the removed rule is not linked to any more, but still links to
 198  * the following rules, and may still be referenced by other threads until all
 199  * other threads quiesce.  The removed rule may not be re-inserted,
 200  * re-initialized, or deleted until after all other threads have quiesced (use
 201  * ovsrcu_postpone).
 202  */
 203 static inline void
 204 cls_match_remove(struct cls_match *prev, struct cls_match *rule)
 205 {
 206     if (prev) {
 207         ovsrcu_set(&prev->next, cls_match_next_protected(rule));
 208     }
 209 }
 210
 211 #define CLS_MATCH_FOR_EACH(ITER, HEAD)                              \
 212     for ((ITER) = (HEAD); (ITER); (ITER) = cls_match_next(ITER))
 213
 214 #define CLS_MATCH_FOR_EACH_AFTER_HEAD(ITER, HEAD)   \
 215     CLS_MATCH_FOR_EACH(ITER, cls_match_next(HEAD))
 216
 217 /* Iterate cls_matches keeping the previous pointer for modifications. */
 218 #define FOR_EACH_RULE_IN_LIST_PROTECTED(ITER, PREV, HEAD)           \
 219     for ((PREV) = NULL, (ITER) = (HEAD);                            \
 220          (ITER);                                                    \
 221          (PREV) = (ITER), (ITER) = cls_match_next_protected(ITER))
 222
 223 \f
 224 /* A longest-prefix match tree. */
 225 struct trie_node {
 226     uint32_t prefix;           /* Prefix bits for this node, MSB first. */
 227     uint8_t  n_bits;           /* Never zero, except for the root node. */
 228     unsigned int n_rules;      /* Number of rules that have this prefix. */
 229     rcu_trie_ptr edges[2];     /* Both NULL if leaf. */
 230 };
 231
 232 /* Max bits per node.  Must fit in struct trie_node's 'prefix'.
 233  * Also tested with 16, 8, and 5 to stress the implementation. */
 234 #define TRIE_PREFIX_BITS 32
 235 \f
 236 /* flow/miniflow/minimask/minimatch utilities.
 237  * These are only used by the classifier, so place them here to allow
 238  * for better optimization. */
 239
 240 static inline uint64_t
 241 miniflow_get_map_in_range(const struct miniflow *miniflow,
 242                           uint8_t start, uint8_t end, unsigned int *offset)
 243 {
 244     uint64_t map = miniflow->map;
 245     *offset = 0;
 246
 247     if (start > 0) {
 248         uint64_t msk = (UINT64_C(1) << start) - 1; /* 'start' LSBs set */
 249         *offset = count_1bits(map & msk);
 250         map &= ~msk;
 251     }
 252     if (end < FLOW_U64S) {
 253         uint64_t msk = (UINT64_C(1) << end) - 1; /* 'end' LSBs set */
 254         map &= msk;
 255     }
 256     return map;
 257 }
 258
 259 /* Returns a hash value for the bits of 'flow' where there are 1-bits in
 260  * 'mask', given 'basis'.
 261  *
 262  * The hash values returned by this function are the same as those returned by
 263  * miniflow_hash_in_minimask(), only the form of the arguments differ. */
 264 static inline uint32_t
 265 flow_hash_in_minimask(const struct flow *flow, const struct minimask *mask,
 266                       uint32_t basis)
 267 {
 268     const uint64_t *mask_values = miniflow_get_values(&mask->masks);
 269     const uint64_t *flow_u64 = (const uint64_t *)flow;
 270     const uint64_t *p = mask_values;
 271     uint32_t hash;
 272     int idx;
 273
 274     hash = basis;
 275     MAP_FOR_EACH_INDEX(idx, mask->masks.map) {
 276         hash = hash_add64(hash, flow_u64[idx] & *p++);
 277     }
 278
 279     return hash_finish(hash, (p - mask_values) * 8);
 280 }
 281
 282 /* Returns a hash value for the bits of 'flow' where there are 1-bits in
 283  * 'mask', given 'basis'.
 284  *
 285  * The hash values returned by this function are the same as those returned by
 286  * flow_hash_in_minimask(), only the form of the arguments differ. */
 287 static inline uint32_t
 288 miniflow_hash_in_minimask(const struct miniflow *flow,
 289                           const struct minimask *mask, uint32_t basis)
 290 {
 291     const uint64_t *mask_values = miniflow_get_values(&mask->masks);
 292     const uint64_t *p = mask_values;
 293     uint32_t hash = basis;
 294     uint64_t flow_u64;
 295
 296     MINIFLOW_FOR_EACH_IN_MAP(flow_u64, flow, mask->masks.map) {
 297         hash = hash_add64(hash, flow_u64 & *p++);
 298     }
 299
 300     return hash_finish(hash, (p - mask_values) * 8);
 301 }
 302
 303 /* Returns a hash value for the bits of range [start, end) in 'flow',
 304  * where there are 1-bits in 'mask', given 'hash'.
 305  *
 306  * The hash values returned by this function are the same as those returned by
 307  * minimatch_hash_range(), only the form of the arguments differ. */
 308 static inline uint32_t
 309 flow_hash_in_minimask_range(const struct flow *flow,
 310                             const struct minimask *mask,
 311                             uint8_t start, uint8_t end, uint32_t *basis)
 312 {
 313     const uint64_t *mask_values = miniflow_get_values(&mask->masks);
 314     const uint64_t *flow_u64 = (const uint64_t *)flow;
 315     unsigned int offset;
 316     uint64_t map;
 317     const uint64_t *p;
 318     uint32_t hash = *basis;
 319     int idx;
 320
 321     map = miniflow_get_map_in_range(&mask->masks, start, end, &offset);
 322     p = mask_values + offset;
 323     MAP_FOR_EACH_INDEX(idx, map) {
 324         hash = hash_add64(hash, flow_u64[idx] & *p++);
 325     }
 326
 327     *basis = hash; /* Allow continuation from the unfinished value. */
 328     return hash_finish(hash, (p - mask_values) * 8);
 329 }
 330
 331 /* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask. */
 332 static inline void
 333 flow_wildcards_fold_minimask(struct flow_wildcards *wc,
 334                              const struct minimask *mask)
 335 {
 336     flow_union_with_miniflow(&wc->masks, &mask->masks);
 337 }
 338
 339 /* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask
 340  * in range [start, end). */
 341 static inline void
 342 flow_wildcards_fold_minimask_range(struct flow_wildcards *wc,
 343                                    const struct minimask *mask,
 344                                    uint8_t start, uint8_t end)
 345 {
 346     uint64_t *dst_u64 = (uint64_t *)&wc->masks;
 347     unsigned int offset;
 348     uint64_t map;
 349     const uint64_t *p;
 350     int idx;
 351
 352     map = miniflow_get_map_in_range(&mask->masks, start, end, &offset);
 353     p = miniflow_get_values(&mask->masks) + offset;
 354     MAP_FOR_EACH_INDEX(idx, map) {
 355         dst_u64[idx] |= *p++;
 356     }
 357 }
 358
 359 /* Returns a hash value for 'flow', given 'basis'. */
 360 static inline uint32_t
 361 miniflow_hash(const struct miniflow *flow, uint32_t basis)
 362 {
 363     const uint64_t *values = miniflow_get_values(flow);
 364     const uint64_t *p = values;
 365     uint32_t hash = basis;
 366     uint64_t hash_map = 0;
 367     uint64_t map;
 368
 369     for (map = flow->map; map; map = zero_rightmost_1bit(map)) {
 370         if (*p) {
 371             hash = hash_add64(hash, *p);
 372             hash_map |= rightmost_1bit(map);
 373         }
 374         p++;
 375     }
 376     hash = hash_add64(hash, hash_map);
 377
 378     return hash_finish(hash, p - values);
 379 }
 380
 381 /* Returns a hash value for 'mask', given 'basis'. */
 382 static inline uint32_t
 383 minimask_hash(const struct minimask *mask, uint32_t basis)
 384 {
 385     return miniflow_hash(&mask->masks, basis);
 386 }
 387
 388 /* Returns a hash value for 'match', given 'basis'. */
 389 static inline uint32_t
 390 minimatch_hash(const struct minimatch *match, uint32_t basis)
 391 {
 392     return miniflow_hash(&match->flow, minimask_hash(&match->mask, basis));
 393 }
 394
 395 /* Returns a hash value for the bits of range [start, end) in 'minimatch',
 396  * given 'basis'.
 397  *
 398  * The hash values returned by this function are the same as those returned by
 399  * flow_hash_in_minimask_range(), only the form of the arguments differ. */
 400 static inline uint32_t
 401 minimatch_hash_range(const struct minimatch *match, uint8_t start, uint8_t end,
 402                      uint32_t *basis)
 403 {
 404     unsigned int offset;
 405     const uint64_t *p, *q;
 406     uint32_t hash = *basis;
 407     int n, i;
 408
 409     n = count_1bits(miniflow_get_map_in_range(&match->mask.masks, start, end,
 410                                               &offset));
 411     q = miniflow_get_values(&match->mask.masks) + offset;
 412     p = miniflow_get_values(&match->flow) + offset;
 413
 414     for (i = 0; i < n; i++) {
 415         hash = hash_add64(hash, p[i] & q[i]);
 416     }
 417     *basis = hash; /* Allow continuation from the unfinished value. */
 418     return hash_finish(hash, (offset + n) * 8);
 419 }
 420
 421 #endif