lib/classifier.h

   1 /*
   2  * Copyright (c) 2009, 2010 Nicira Networks.
   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_H
  18 #define CLASSIFIER_H 1
  19
  20 /* Flow classifier.
  21  *
  22  * This flow classifier assumes that we can arrange the fields in a flow in an
  23  * order such that the set of wildcarded fields in a rule tend to fall toward
  24  * the end of the ordering.  That is, if field F is wildcarded, then all the
  25  * fields after F tend to be wildcarded as well.  If this assumption is
  26  * violated, then the classifier will still classify flows correctly, but its
  27  * performance will suffer.
  28  *
  29  * The classifier uses a collection of CLS_N_FIELDS hash tables for wildcarded
  30  * flows.  Each of these tables contains the flows that wildcard a given field
  31  * and do not wildcard any of the fields that precede F in the ordering.  The
  32  * key for each hash table is the value of the fields preceding F that are not
  33  * wildcarded.  All the flows that fall within a table and have the same key
  34  * are kept as a linked list ordered from highest to lowest priority.
  35  *
  36  * The classifier also maintains a separate hash table of exact-match flows.
  37  *
  38  * To search the classifier we first search the table of exact-match flows,
  39  * since exact-match flows always have highest priority.  If there is a match,
  40  * we're done.  Otherwise, we search each of the CLS_N_FIELDS hash tables in
  41  * turn, looking for the highest-priority match, and return it (if any).
  42  */
  43
  44 #include "flow.h"
  45 #include "hmap.h"
  46 #include "list.h"
  47 #include "openflow/nicira-ext.h"
  48 #include "openflow/openflow.h"
  49
  50 /* Number of bytes of fields in a rule. */
  51 #define CLS_N_BYTES 37
  52
  53 /* Fields in a rule.
  54  *
  55  * This definition sets the ordering of fields, which is important for
  56  * performance (see above).  To adjust the ordering, change the order of the
  57  * lines. */
  58 #define CLS_FIELDS                                          \
  59     /*                           flow_t       all-caps */   \
  60     /*        wildcard bit(s)    member name  name     */   \
  61     /*        -----------------  -----------  -------- */   \
  62     CLS_FIELD(OFPFW_IN_PORT,     in_port,     IN_PORT)      \
  63     CLS_FIELD(NXFW_TUN_ID,       tun_id,      TUN_ID)       \
  64     CLS_FIELD(OFPFW_DL_VLAN,     dl_vlan,     DL_VLAN)      \
  65     CLS_FIELD(OFPFW_DL_VLAN_PCP, dl_vlan_pcp, DL_VLAN_PCP)  \
  66     CLS_FIELD(OFPFW_DL_SRC,      dl_src,      DL_SRC)       \
  67     CLS_FIELD(OFPFW_DL_DST,      dl_dst,      DL_DST)       \
  68     CLS_FIELD(OFPFW_DL_TYPE,     dl_type,     DL_TYPE)      \
  69     CLS_FIELD(OFPFW_NW_SRC_MASK, nw_src,      NW_SRC)       \
  70     CLS_FIELD(OFPFW_NW_DST_MASK, nw_dst,      NW_DST)       \
  71     CLS_FIELD(OFPFW_NW_PROTO,    nw_proto,    NW_PROTO)     \
  72     CLS_FIELD(OFPFW_NW_TOS,      nw_tos,      NW_TOS)       \
  73     CLS_FIELD(OFPFW_TP_SRC,      tp_src,      TP_SRC)       \
  74     CLS_FIELD(OFPFW_TP_DST,      tp_dst,      TP_DST)
  75
  76 /* Field indexes.
  77  *
  78  * (These are also indexed into struct classifier's 'tables' array.) */
  79 enum {
  80 #define CLS_FIELD(WILDCARDS, MEMBER, NAME) CLS_F_IDX_##NAME,
  81     CLS_FIELDS
  82 #undef CLS_FIELD
  83     CLS_F_IDX_EXACT,            /* Exact-match table. */
  84     CLS_N_FIELDS = CLS_F_IDX_EXACT
  85 };
  86
  87 /* Field information. */
  88 struct cls_field {
  89     int ofs;                    /* Offset in flow_t. */
  90     int len;                    /* Length in bytes. */
  91     uint32_t wildcards;         /* OFPFW_* bit or bits for this field. */
  92     const char *name;           /* Name (for debugging). */
  93 };
  94 extern const struct cls_field cls_fields[CLS_N_FIELDS + 1];
  95
  96 /* A flow classifier. */
  97 struct classifier {
  98     int n_rules;                /* Sum of hmap_count() over tables[]. */
  99     struct hmap tables[CLS_N_FIELDS]; /* Contain cls_bucket elements. */
 100     struct hmap exact_table;          /* Contain cls_rule elements. */
 101 };
 102
 103 /* A group of rules with the same fixed values for initial fields. */
 104 struct cls_bucket {
 105     struct hmap_node hmap_node; /* Within struct classifier 'tables'. */
 106     struct list rules;          /* In order from highest to lowest priority. */
 107     flow_t fixed;               /* Values for fixed fields. */
 108 };
 109
 110 /* A flow classification rule.
 111  *
 112  * Use cls_rule_from_flow() or cls_rule_from_match() to initialize a cls_rule
 113  * or you will almost certainly not initialize 'table_idx' correctly, with
 114  * disastrous results! */
 115 struct cls_rule {
 116     union {
 117         struct list list;       /* Within struct cls_bucket 'rules'. */
 118         struct hmap_node hmap;  /* Within struct classifier 'exact_table'. */
 119     } node;
 120     flow_t flow;                /* All field values. */
 121     struct flow_wildcards wc;   /* Wildcards for fields. */
 122     unsigned int priority;      /* Larger numbers are higher priorities. */
 123     unsigned int table_idx;     /* Index into struct classifier 'tables'. */
 124 };
 125
 126 void cls_rule_from_flow(const flow_t *, uint32_t wildcards,
 127                         unsigned int priority, struct cls_rule *);
 128 void cls_rule_from_match(const struct ofp_match *, unsigned int priority,
 129                          bool tun_id_from_cookie, uint64_t cookie,
 130                          struct cls_rule *);
 131 char *cls_rule_to_string(const struct cls_rule *);
 132 void cls_rule_print(const struct cls_rule *);
 133 void cls_rule_moved(struct classifier *,
 134                     struct cls_rule *old, struct cls_rule *new);
 135 void cls_rule_replace(struct classifier *, const struct cls_rule *old,
 136                       struct cls_rule *new);
 137
 138 void classifier_init(struct classifier *);
 139 void classifier_destroy(struct classifier *);
 140 bool classifier_is_empty(const struct classifier *);
 141 int classifier_count(const struct classifier *);
 142 int classifier_count_exact(const struct classifier *);
 143 struct cls_rule *classifier_insert(struct classifier *, struct cls_rule *);
 144 void classifier_insert_exact(struct classifier *, struct cls_rule *);
 145 void classifier_remove(struct classifier *, struct cls_rule *);
 146 struct cls_rule *classifier_lookup(const struct classifier *, const flow_t *);
 147 struct cls_rule *classifier_lookup_wild(const struct classifier *,
 148                                         const flow_t *);
 149 struct cls_rule *classifier_lookup_exact(const struct classifier *,
 150                                          const flow_t *);
 151 bool classifier_rule_overlaps(const struct classifier *, const flow_t *,
 152                               uint32_t wildcards, unsigned int priority);
 153
 154 typedef void cls_cb_func(struct cls_rule *, void *aux);
 155
 156 enum {
 157     CLS_INC_EXACT = 1 << 0,     /* Include exact-match flows? */
 158     CLS_INC_WILD = 1 << 1,      /* Include flows with wildcards? */
 159     CLS_INC_ALL = CLS_INC_EXACT | CLS_INC_WILD
 160 };
 161 void classifier_for_each(const struct classifier *, int include,
 162                          cls_cb_func *, void *aux);
 163 void classifier_for_each_match(const struct classifier *,
 164                                const struct cls_rule *,
 165                                int include, cls_cb_func *, void *aux);
 166 struct cls_rule *classifier_find_rule_exactly(const struct classifier *,
 167                                               const flow_t *target,
 168                                               uint32_t wildcards,
 169                                               unsigned int priority);
 170
 171 #endif /* classifier.h */