lib/classifier-private.h

   1 /*
   2  * Copyright (c) 2014, 2015, 2016 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 "ccmap.h"
  21 #include "cmap.h"
  22 #include "flow.h"
  23 #include "hash.h"
  24 #include "rculist.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 uint8_t n_indices;                   /* How many indices to use. */
  44     const struct flowmap index_maps[CLS_MAX_INDICES + 1]; /* Stage maps. */
  45     unsigned int trie_plen[CLS_MAX_TRIES];  /* Trie prefix length in 'mask'
  46                                              * (runtime configurable). */
  47     const int ports_mask_len;
  48     struct ccmap indices[CLS_MAX_INDICES];  /* Staged lookup indices. */
  49     rcu_trie_ptr ports_trie;                /* NULL if none. */
  50
  51     /* These fields are accessed by all readers. */
  52     struct cmap rules;                      /* Contains 'cls_match'es. */
  53     const struct minimask mask;             /* Wildcards for fields. */
  54     /* 'mask' must be the last field. */
  55 };
  56
  57 /* Internal representation of a rule in a "struct cls_subtable".
  58  *
  59  * The 'next' member is an element in a singly linked, null-terminated list.
  60  * This list links together identical "cls_match"es in order of decreasing
  61  * priority.  The classifier code maintains the invariant that at most one rule
  62  * of a given priority is visible for any given lookup version.
  63  */
  64 struct cls_match {
  65     /* Accessed by everybody. */
  66     OVSRCU_TYPE(struct cls_match *) next; /* Equal, lower-priority matches. */
  67     OVSRCU_TYPE(struct cls_conjunction_set *) conj_set;
  68
  69     /* Accessed by readers interested in wildcarding. */
  70     const int priority;         /* Larger numbers are higher priorities. */
  71
  72     /* Accessed by all readers. */
  73     struct cmap_node cmap_node; /* Within struct cls_subtable 'rules'. */
  74
  75     /* Rule versioning.
  76      *
  77      * CLS_NOT_REMOVED_VERSION has a special meaning for 'remove_version',
  78      * meaning that the rule has been added but not yet removed.
  79      */
  80     const cls_version_t add_version;        /* Version rule was added in. */
  81     ATOMIC(cls_version_t) remove_version;   /* Version rule is removed in. */
  82
  83     const struct cls_rule *cls_rule;
  84     const struct miniflow flow; /* Matching rule. Mask is in the subtable. */
  85     /* 'flow' must be the last field. */
  86 };
  87
  88 /* Utilities for accessing the 'cls_match' member of struct cls_rule. */
  89 static inline struct cls_match *
  90 get_cls_match_protected(const struct cls_rule *rule)
  91 {
  92     return ovsrcu_get_protected(struct cls_match *, &rule->cls_match);
  93 }
  94
  95 static inline struct cls_match *
  96 get_cls_match(const struct cls_rule *rule)
  97 {
  98     return ovsrcu_get(struct cls_match *, &rule->cls_match);
  99 }
 100
 101 /* Must be RCU postponed. */
 102 void cls_match_free_cb(struct cls_match *);
 103
 104 static inline void
 105 cls_match_set_remove_version(struct cls_match *rule, cls_version_t version)
 106 {
 107     atomic_store_relaxed(&rule->remove_version, version);
 108 }
 109
 110 static inline bool
 111 cls_match_visible_in_version(const struct cls_match *rule,
 112                              cls_version_t version)
 113 {
 114     cls_version_t remove_version;
 115
 116     /* C11 does not want to access an atomic via a const object pointer. */
 117     atomic_read_relaxed(&CONST_CAST(struct cls_match *, rule)->remove_version,
 118                         &remove_version);
 119
 120     return rule->add_version <= version && version < remove_version;
 121 }
 122
 123 static inline bool
 124 cls_match_is_eventually_invisible(const struct cls_match *rule)
 125 {
 126     cls_version_t remove_version;
 127
 128     /* C11 does not want to access an atomic via a const object pointer. */
 129     atomic_read_relaxed(&CONST_CAST(struct cls_match *, rule)->remove_version,
 130                         &remove_version);
 131
 132     return remove_version <= CLS_MAX_VERSION;
 133 }
 134
 135 \f
 136 /* cls_match 'next' */
 137
 138 static inline const struct cls_match *
 139 cls_match_next(const struct cls_match *rule)
 140 {
 141     return ovsrcu_get(struct cls_match *, &rule->next);
 142 }
 143
 144 static inline struct cls_match *
 145 cls_match_next_protected(const struct cls_match *rule)
 146 {
 147     return ovsrcu_get_protected(struct cls_match *, &rule->next);
 148 }
 149
 150 /* Puts 'rule' in the position between 'prev' and 'next'.  If 'prev' == NULL,
 151  * then the 'rule' is the new list head, and if 'next' == NULL, the rule is the
 152  * new list tail.
 153  * If there are any nodes between 'prev' and 'next', they are dropped from the
 154  * list. */
 155 static inline void
 156 cls_match_insert(struct cls_match *prev, struct cls_match *next,
 157                  struct cls_match *rule)
 158 {
 159     ovsrcu_set_hidden(&rule->next, next);
 160
 161     if (prev) {
 162         ovsrcu_set(&prev->next, rule);
 163     }
 164 }
 165
 166 /* Puts 'new_rule' in the position of 'old_rule', which is the next node after
 167  * 'prev'. If 'prev' == NULL, then the 'new_rule' is the new list head.
 168  *
 169  * The replaced cls_match still links to the later rules, and may still be
 170  * referenced by other threads until all other threads quiesce.  The replaced
 171  * rule may not be re-inserted, re-initialized, or deleted until after all
 172  * other threads have quiesced (use ovsrcu_postpone). */
 173 static inline void
 174 cls_match_replace(struct cls_match *prev,
 175                   struct cls_match *old_rule, struct cls_match *new_rule)
 176 {
 177     cls_match_insert(prev, cls_match_next_protected(old_rule), new_rule);
 178 }
 179
 180 /* Removes 'rule' following 'prev' from the list. If 'prev' is NULL, then the
 181  * 'rule' is a list head, and the caller is responsible for maintaining its
 182  * list head pointer (if any).
 183  *
 184  * Afterward, the removed rule is not linked to any more, but still links to
 185  * the following rules, and may still be referenced by other threads until all
 186  * other threads quiesce.  The removed rule may not be re-inserted,
 187  * re-initialized, or deleted until after all other threads have quiesced (use
 188  * ovsrcu_postpone).
 189  */
 190 static inline void
 191 cls_match_remove(struct cls_match *prev, struct cls_match *rule)
 192 {
 193     if (prev) {
 194         ovsrcu_set(&prev->next, cls_match_next_protected(rule));
 195     }
 196 }
 197
 198 #define CLS_MATCH_FOR_EACH(ITER, HEAD)                              \
 199     for ((ITER) = (HEAD); (ITER); (ITER) = cls_match_next(ITER))
 200
 201 #define CLS_MATCH_FOR_EACH_AFTER_HEAD(ITER, HEAD)   \
 202     CLS_MATCH_FOR_EACH(ITER, cls_match_next(HEAD))
 203
 204 /* Iterate cls_matches keeping the previous pointer for modifications. */
 205 #define FOR_EACH_RULE_IN_LIST_PROTECTED(ITER, PREV, HEAD)           \
 206     for ((PREV) = NULL, (ITER) = (HEAD);                            \
 207          (ITER);                                                    \
 208          (PREV) = (ITER), (ITER) = cls_match_next_protected(ITER))
 209
 210 \f
 211 /* A longest-prefix match tree. */
 212 struct trie_node {
 213     uint32_t prefix;           /* Prefix bits for this node, MSB first. */
 214     uint8_t  n_bits;           /* Never zero, except for the root node. */
 215     unsigned int n_rules;      /* Number of rules that have this prefix. */
 216     rcu_trie_ptr edges[2];     /* Both NULL if leaf. */
 217 };
 218
 219 /* Max bits per node.  Must fit in struct trie_node's 'prefix'.
 220  * Also tested with 16, 8, and 5 to stress the implementation. */
 221 #define TRIE_PREFIX_BITS 32
 222 \f
 223 /* flow/miniflow/minimask/minimatch utilities.
 224  * These are only used by the classifier, so place them here to allow
 225  * for better optimization. */
 226
 227 /* Returns a hash value for the bits of 'flow' where there are 1-bits in
 228  * 'mask', given 'basis'.
 229  *
 230  * The hash values returned by this function are the same as those returned by
 231  * miniflow_hash_in_minimask(), only the form of the arguments differ. */
 232 static inline uint32_t
 233 flow_hash_in_minimask(const struct flow *flow, const struct minimask *mask,
 234                       uint32_t basis)
 235 {
 236     const uint64_t *mask_values = miniflow_get_values(&mask->masks);
 237     const uint64_t *flow_u64 = (const uint64_t *)flow;
 238     const uint64_t *p = mask_values;
 239     uint32_t hash = basis;
 240     map_t map;
 241
 242     FLOWMAP_FOR_EACH_MAP (map, mask->masks.map) {
 243         size_t idx;
 244
 245         MAP_FOR_EACH_INDEX (idx, map) {
 246             hash = hash_add64(hash, flow_u64[idx] & *p++);
 247         }
 248         flow_u64 += MAP_T_BITS;
 249     }
 250
 251     return hash_finish(hash, (p - mask_values) * 8);
 252 }
 253
 254 /* Returns a hash value for the bits of 'flow' where there are 1-bits in
 255  * 'mask', given 'basis'.
 256  *
 257  * The hash values returned by this function are the same as those returned by
 258  * flow_hash_in_minimask(), only the form of the arguments differ. */
 259 static inline uint32_t
 260 miniflow_hash_in_minimask(const struct miniflow *flow,
 261                           const struct minimask *mask, uint32_t basis)
 262 {
 263     const uint64_t *mask_values = miniflow_get_values(&mask->masks);
 264     const uint64_t *p = mask_values;
 265     uint32_t hash = basis;
 266     uint64_t value;
 267
 268     MINIFLOW_FOR_EACH_IN_FLOWMAP(value, flow, mask->masks.map) {
 269         hash = hash_add64(hash, value & *p++);
 270     }
 271
 272     return hash_finish(hash, (p - mask_values) * 8);
 273 }
 274
 275 /* Returns a hash value for the values of 'flow', indicated by 'range', where
 276  * there are 1-bits in 'mask', given 'basis'.  'range' must be a continuous
 277  * subset of the bits in 'mask''s map, representing a continuous range of the
 278  * minimask's mask data.  '*offset' must be the number of 64-bit units of the
 279  * minimask's data to skip to get to the first unit covered by 'range'. On
 280  * return '*offset' is updated with the number of 64-bit units of the minimask
 281  * consumed.
 282  *
 283  * Typically this function is called for successive ranges of minimask's masks,
 284  * and the first invocation passes '*offset' as zero.
 285  *
 286  * The hash values returned by this function are the same as those returned by
 287  * minimatch_hash_range(), only the form of the arguments differ. */
 288 static inline uint32_t
 289 flow_hash_in_minimask_range(const struct flow *flow,
 290                             const struct minimask *mask,
 291                             const struct flowmap range,
 292                             unsigned int *offset,
 293                             uint32_t *basis)
 294 {
 295     const uint64_t *mask_values = miniflow_get_values(&mask->masks);
 296     const uint64_t *flow_u64 = (const uint64_t *)flow;
 297     const uint64_t *p = mask_values + *offset;
 298     uint32_t hash = *basis;
 299     map_t map;
 300
 301     FLOWMAP_FOR_EACH_MAP (map, range) {
 302         size_t idx;
 303
 304         MAP_FOR_EACH_INDEX (idx, map) {
 305             hash = hash_add64(hash, flow_u64[idx] & *p++);
 306         }
 307         flow_u64 += MAP_T_BITS;
 308     }
 309
 310     *basis = hash; /* Allow continuation from the unfinished value. */
 311     *offset = p - mask_values;
 312     return hash_finish(hash, *offset * 8);
 313 }
 314
 315 /* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask. */
 316 static inline void
 317 flow_wildcards_fold_minimask(struct flow_wildcards *wc,
 318                              const struct minimask *mask)
 319 {
 320     flow_union_with_miniflow(&wc->masks, &mask->masks);
 321 }
 322
 323 /* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask for bits in
 324  * 'fmap'.  1-bits in 'fmap' are a subset of 1-bits in 'mask''s map. */
 325 static inline void
 326 flow_wildcards_fold_minimask_in_map(struct flow_wildcards *wc,
 327                                     const struct minimask *mask,
 328                                     const struct flowmap fmap)
 329 {
 330     flow_union_with_miniflow_subset(&wc->masks, &mask->masks, fmap);
 331 }
 332
 333 /* Returns a hash value for 'mask', given 'basis'. */
 334 static inline uint32_t
 335 minimask_hash(const struct minimask *mask, uint32_t basis)
 336 {
 337     const uint64_t *p = miniflow_get_values(&mask->masks);
 338     size_t n_values = miniflow_n_values(&mask->masks);
 339     uint32_t hash = basis;
 340
 341     for (size_t i = 0; i < n_values; i++) {
 342         hash = hash_add64(hash, *p++);
 343     }
 344
 345     map_t map;
 346     FLOWMAP_FOR_EACH_MAP (map, mask->masks.map) {
 347         hash = hash_add64(hash, map);
 348     }
 349
 350     return hash_finish(hash, n_values);
 351 }
 352
 353 /* Returns a hash value for the values of 'match->flow', indicated by 'range',
 354  * where there are 1-bits in 'match->mask', given 'basis'.  'range' must be a
 355  * continuous subset of the bits in the map of 'match', representing a
 356  * continuous range of the mask data of 'match'.  '*offset' must be the number
 357  * of 64-bit units of the match data to skip to get to the first unit covered
 358  * by 'range'.  On return '*offset' is updated with the number of 64-bit units
 359  * of the match consumed.
 360  *
 361  * Typically this function is called for successive ranges of minimask's masks,
 362  * and the first invocation passes '*offset' as zero.
 363  *
 364  * The hash values returned by this function are the same as those returned by
 365  * flow_hash_in_minimask_range(), only the form of the arguments differ. */
 366 static inline uint32_t
 367 minimatch_hash_range(const struct minimatch *match,
 368                      const struct flowmap range, unsigned int *offset,
 369                      uint32_t *basis)
 370 {
 371     const uint64_t *p = miniflow_get_values(match->flow) + *offset;
 372     const uint64_t *q = miniflow_get_values(&match->mask->masks) + *offset;
 373     unsigned int n = flowmap_n_1bits(range);
 374     uint32_t hash = *basis;
 375
 376     for (unsigned int i = 0; i < n; i++) {
 377         hash = hash_add64(hash, p[i] & q[i]);
 378     }
 379     *basis = hash; /* Allow continuation from the unfinished value. */
 380     *offset += n;
 381     return hash_finish(hash, *offset * 8);
 382 }
 383
 384 #endif