switch/chain.c

   1 /* Copyright (C) 2008 Board of Trustees, Leland Stanford Jr. University.
   2  *
   3  * Permission is hereby granted, free of charge, to any person obtaining a copy
   4  * of this software and associated documentation files (the "Software"), to
   5  * deal in the Software without restriction, including without limitation the
   6  * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
   7  * sell copies of the Software, and to permit persons to whom the Software is
   8  * furnished to do so, subject to the following conditions:
   9  *
  10  * The above copyright notice and this permission notice shall be included in
  11  * all copies or substantial portions of the Software.
  12  *
  13  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  14  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  15  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  16  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  17  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  18  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  19  * IN THE SOFTWARE.
  20  */
  21
  22 #include "chain.h"
  23 #include <assert.h>
  24 #include <errno.h>
  25 #include <stdlib.h>
  26 #include "switch-flow.h"
  27 #include "table.h"
  28
  29 #define THIS_MODULE VLM_chain
  30 #include "vlog.h"
  31
  32 /* Attempts to append 'table' to the set of tables in 'chain'.  Returns 0 or
  33  * negative error.  If 'table' is null it is assumed that table creation failed
  34  * due to out-of-memory. */
  35 static int add_table(struct sw_chain *chain, struct sw_table *table)
  36 {
  37     if (table == NULL)
  38         return -ENOMEM;
  39     if (chain->n_tables >= CHAIN_MAX_TABLES) {
  40         VLOG_ERR("too many tables in chain\n");
  41         table->destroy(table);
  42         return -ENOBUFS;
  43     }
  44     chain->tables[chain->n_tables++] = table;
  45     return 0;
  46 }
  47
  48 /* Creates and returns a new chain.  Returns NULL if the chain cannot be
  49  * created. */
  50 struct sw_chain *chain_create(void)
  51 {
  52     struct sw_chain *chain = calloc(1, sizeof *chain);
  53     if (chain == NULL)
  54         return NULL;
  55
  56     if (add_table(chain, table_mac_create(TABLE_MAC_NUM_BUCKETS,
  57                                           TABLE_MAC_MAX_FLOWS))
  58         || add_table(chain, table_hash2_create(0x1EDC6F41, TABLE_HASH_MAX_FLOWS,
  59                                                0x741B8CD7, TABLE_HASH_MAX_FLOWS))
  60         || add_table(chain, table_linear_create(TABLE_LINEAR_MAX_FLOWS))) {
  61         chain_destroy(chain);
  62         return NULL;
  63     }
  64
  65     return chain;
  66 }
  67
  68 /* Searches 'chain' for a flow matching 'key', which must not have any wildcard
  69  * fields.  Returns the flow if successful, otherwise a null pointer. */
  70 struct sw_flow *
  71 chain_lookup(struct sw_chain *chain, const struct sw_flow_key *key)
  72 {
  73     int i;
  74
  75     assert(!key->wildcards);
  76     for (i = 0; i < chain->n_tables; i++) {
  77         struct sw_table *t = chain->tables[i];
  78         struct sw_flow *flow = t->lookup(t, key);
  79         if (flow)
  80             return flow;
  81     }
  82     return NULL;
  83 }
  84
  85 /* Inserts 'flow' into 'chain', replacing any duplicate flow.  Returns 0 if
  86  * successful or a negative error.
  87  *
  88  * If successful, 'flow' becomes owned by the chain, otherwise it is retained
  89  * by the caller. */
  90 int
  91 chain_insert(struct sw_chain *chain, struct sw_flow *flow)
  92 {
  93     int i;
  94
  95     for (i = 0; i < chain->n_tables; i++) {
  96         struct sw_table *t = chain->tables[i];
  97         if (t->insert(t, flow))
  98             return 0;
  99     }
 100
 101     return -ENOBUFS;
 102 }
 103
 104 /* Deletes from 'chain' any and all flows that match 'key'.  Returns the number
 105  * of flows that were deleted.
 106  *
 107  * Expensive in the general case as currently implemented, since it requires
 108  * iterating through the entire contents of each table for keys that contain
 109  * wildcards.  Relatively cheap for fully specified keys.
 110  *
 111  * The caller need not hold any locks. */
 112 int
 113 chain_delete(struct sw_chain *chain, const struct sw_flow_key *key, int strict)
 114 {
 115     int count = 0;
 116     int i;
 117
 118     for (i = 0; i < chain->n_tables; i++) {
 119         struct sw_table *t = chain->tables[i];
 120         count += t->delete(t, key, strict);
 121     }
 122
 123     return count;
 124
 125 }
 126
 127 /* Performs timeout processing on all the tables in 'chain'.  Returns the
 128  * number of flow entries deleted through expiration.
 129  *
 130  * Expensive as currently implemented, since it iterates through the entire
 131  * contents of each table.
 132  *
 133  * The caller need not hold any locks. */
 134 int
 135 chain_timeout(struct sw_chain *chain, struct datapath *dp)
 136 {
 137     int count = 0;
 138     int i;
 139
 140     for (i = 0; i < chain->n_tables; i++) {
 141         struct sw_table *t = chain->tables[i];
 142         count += t->timeout(dp, t);
 143     }
 144     return count;
 145 }
 146
 147 /* Destroys 'chain', which must not have any users. */
 148 void
 149 chain_destroy(struct sw_chain *chain)
 150 {
 151     int i;
 152
 153     for (i = 0; i < chain->n_tables; i++) {
 154         struct sw_table *t = chain->tables[i];
 155         t->destroy(t);
 156     }
 157     free(chain);
 158 }
 159
 160 /* Prints statistics for each of the tables in 'chain'. */
 161 void
 162 chain_print_stats(struct sw_chain *chain)
 163 {
 164     int i;
 165
 166     printf("\n");
 167     for (i = 0; i < chain->n_tables; i++) {
 168         struct sw_table *t = chain->tables[i];
 169         struct sw_table_stats stats;
 170         t->stats(t, &stats);
 171         printf("%s: %lu/%lu flows\n",
 172                stats.name, stats.n_flows, stats.max_flows);
 173     }
 174 }