lib/classifier.h

   1 /*
   2  * Copyright (c) 2009 Nicira Networks.
   3  *
   4  * Permission to use, copy, modify, and/or distribute this software for any
   5  * purpose with or without fee is hereby granted, provided that the above
   6  * copyright notice and this permission notice appear in all copies.
   7  *
   8  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
   9  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  10  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  11  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  12  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  13  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  14  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  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
  30 #include "flow.h"
  31 #include "hmap.h"
  32 #include "list.h"
  33 #include "openflow/openflow.h"
  34
  35 /* Number of bytes of fields in a rule. */
  36 #define CLS_N_BYTES 31
  37
  38 /* Fields in a rule.
  39  *
  40  * This definition sets the ordering of fields, which is important for
  41  * performance (see above).  To adjust the ordering, change the order of the
  42  * lines. */
  43 #define CLS_FIELDS                                          \
  44     /*                           flow_t       all-caps */   \
  45     /*        wildcard bit(s)    member name  name     */   \
  46     /*        -----------------  -----------  -------- */   \
  47     CLS_FIELD(OFPFW_IN_PORT,     in_port,     IN_PORT)      \
  48     CLS_FIELD(OFPFW_DL_VLAN,     dl_vlan,     DL_VLAN)      \
  49     CLS_FIELD(OFPFW_DL_SRC,      dl_src,      DL_SRC)       \
  50     CLS_FIELD(OFPFW_DL_DST,      dl_dst,      DL_DST)       \
  51     CLS_FIELD(OFPFW_DL_TYPE,     dl_type,     DL_TYPE)      \
  52     CLS_FIELD(OFPFW_NW_SRC_MASK, nw_src,      NW_SRC)       \
  53     CLS_FIELD(OFPFW_NW_DST_MASK, nw_dst,      NW_DST)       \
  54     CLS_FIELD(OFPFW_NW_PROTO,    nw_proto,    NW_PROTO)     \
  55     CLS_FIELD(OFPFW_TP_SRC,      tp_src,      TP_SRC)       \
  56     CLS_FIELD(OFPFW_TP_DST,      tp_dst,      TP_DST)
  57
  58 /* Field indexes.
  59  *
  60  * (These are also indexed into struct classifier's 'tables' array.) */
  61 enum {
  62 #define CLS_FIELD(WILDCARDS, MEMBER, NAME) CLS_F_IDX_##NAME,
  63     CLS_FIELDS
  64 #undef CLS_FIELD
  65     CLS_F_IDX_EXACT,            /* Exact-match table. */
  66     CLS_N_FIELDS = CLS_F_IDX_EXACT
  67 };
  68
  69 /* Field information. */
  70 struct cls_field {
  71     int ofs;                    /* Offset in flow_t. */
  72     int len;                    /* Length in bytes. */
  73     uint32_t wildcards;         /* OFPFW_* bit or bits for this field. */
  74     const char *name;           /* Name (for debugging). */
  75 };
  76 extern const struct cls_field cls_fields[CLS_N_FIELDS + 1];
  77
  78 /* A flow classifier. */
  79 struct classifier {
  80     int n_rules;                /* Sum of hmap_count() over tables[]. */
  81     struct hmap tables[CLS_N_FIELDS]; /* Contain cls_bucket elements. */
  82     struct hmap exact_table;          /* Contain cls_rule elements. */
  83 };
  84
  85 /* A group of rules with the same fixed values for initial fields. */
  86 struct cls_bucket {
  87     struct hmap_node hmap_node; /* Within struct classifier 'tables'. */
  88     struct list rules;          /* In order from highest to lowest priority. */
  89     flow_t fixed;               /* Values for fixed fields. */
  90 };
  91
  92 /* A flow classification rule.
  93  *
  94  * Use cls_rule_from_flow() or cls_rule_from_match() to initialize a cls_rule
  95  * or you will almost certainly not initialize 'table_idx' correctly, with
  96  * disastrous results! */
  97 struct cls_rule {
  98     union {
  99         struct list list;       /* Within struct cls_bucket 'rules'. */
 100         struct hmap_node hmap;  /* Within struct classifier 'exact_table'. */
 101     } node;
 102     flow_t flow;                /* All field values. */
 103     struct flow_wildcards wc;   /* Wildcards for fields. */
 104     unsigned int priority;      /* Larger numbers are higher priorities. */
 105     unsigned int table_idx;     /* Index into struct classifier 'tables'. */
 106 };
 107
 108 void cls_rule_from_flow(struct cls_rule *, const flow_t *, uint32_t wildcards,
 109                         unsigned int priority);
 110 void cls_rule_from_match(struct cls_rule *, const struct ofp_match *,
 111                          unsigned int priority);
 112 void cls_rule_print(const struct cls_rule *);
 113 void cls_rule_moved(struct classifier *,
 114                     struct cls_rule *old, struct cls_rule *new);
 115 void cls_rule_replace(struct classifier *, const struct cls_rule *old,
 116                       struct cls_rule *new);
 117
 118 void classifier_init(struct classifier *);
 119 void classifier_destroy(struct classifier *);
 120 bool classifier_is_empty(const struct classifier *);
 121 int classifier_count(const struct classifier *);
 122 int classifier_count_exact(const struct classifier *);
 123 struct cls_rule *classifier_insert(struct classifier *, struct cls_rule *);
 124 void classifier_insert_exact(struct classifier *, struct cls_rule *);
 125 void classifier_remove(struct classifier *, struct cls_rule *);
 126 struct cls_rule *classifier_lookup(const struct classifier *, const flow_t *);
 127 struct cls_rule *classifier_lookup_wild(const struct classifier *,
 128                                         const flow_t *);
 129 struct cls_rule *classifier_lookup_exact(const struct classifier *,
 130                                          const flow_t *);
 131
 132 typedef void cls_cb_func(struct cls_rule *, void *aux);
 133
 134 enum {
 135     CLS_INC_EXACT = 1 << 0,     /* Include exact-match flows? */
 136     CLS_INC_WILD = 1 << 1,      /* Include flows with wildcards? */
 137     CLS_INC_ALL = CLS_INC_EXACT | CLS_INC_WILD
 138 };
 139 void classifier_for_each(const struct classifier *, int include,
 140                          cls_cb_func *, void *aux);
 141 void classifier_for_each_match(const struct classifier *,
 142                                const struct cls_rule *,
 143                                int include, cls_cb_func *, void *aux);
 144 struct cls_rule *classifier_find_rule_exactly(const struct classifier *,
 145                                               const flow_t *target,
 146                                               uint32_t wildcards,
 147                                               unsigned int priority);
 148
 149 #endif /* classifier.h */