datapath/chain.c

   1 /*
   2  * Distributed under the terms of the GNU GPL version 2.
   3  * Copyright (c) 2007, 2008 The Board of Trustees of The Leland
   4  * Stanford Junior University
   5  */
   6
   7 #include "chain.h"
   8 #include "flow.h"
   9 #include "table.h"
  10 #include <linux/module.h>
  11 #include <linux/rcupdate.h>
  12 #include <linux/slab.h>
  13 #include <linux/spinlock.h>
  14
  15 static struct sw_table *(*create_hw_table_hook)(void);
  16 static struct module *hw_table_owner;
  17 static DEFINE_SPINLOCK(hook_lock);
  18
  19 /* Attempts to append 'table' to the set of tables in 'chain'.  Returns 0 or
  20  * negative error.  If 'table' is null it is assumed that table creation failed
  21  * due to out-of-memory. */
  22 static int add_table(struct sw_chain *chain, struct sw_table *table)
  23 {
  24         if (table == NULL)
  25                 return -ENOMEM;
  26         if (chain->n_tables >= CHAIN_MAX_TABLES) {
  27                 printk("too many tables in chain\n");
  28                 table->destroy(table);
  29                 return -ENOBUFS;
  30         }
  31         chain->tables[chain->n_tables++] = table;
  32         return 0;
  33 }
  34
  35 /* Creates and returns a new chain associated with 'dp'.  Returns NULL if the
  36  * chain cannot be created. */
  37 struct sw_chain *chain_create(struct datapath *dp)
  38 {
  39         struct sw_chain *chain = kzalloc(sizeof *chain, GFP_KERNEL);
  40         if (chain == NULL)
  41                 goto error;
  42         chain->dp = dp;
  43         chain->owner = try_module_get(hw_table_owner) ? hw_table_owner : NULL;
  44         if (chain->owner && create_hw_table_hook) {
  45                 struct sw_table *hwtable = create_hw_table_hook();
  46                 if (!hwtable || add_table(chain, hwtable))
  47                         goto error;
  48         }
  49
  50         if (add_table(chain, table_hash2_create(0x1EDC6F41, TABLE_HASH_MAX_FLOWS,
  51                                                 0x741B8CD7, TABLE_HASH_MAX_FLOWS))
  52             || add_table(chain, table_linear_create(TABLE_LINEAR_MAX_FLOWS)))
  53                 goto error;
  54         return chain;
  55
  56 error:
  57         if (chain)
  58                 chain_destroy(chain);
  59         return NULL;
  60 }
  61
  62 /* Searches 'chain' for a flow matching 'key', which must not have any wildcard
  63  * fields.  Returns the flow if successful, otherwise a null pointer.
  64  *
  65  * Caller must hold rcu_read_lock or dp_mutex. */
  66 struct sw_flow *chain_lookup(struct sw_chain *chain,
  67                          const struct sw_flow_key *key)
  68 {
  69         int i;
  70
  71         BUG_ON(key->wildcards);
  72         for (i = 0; i < chain->n_tables; i++) {
  73                 struct sw_table *t = chain->tables[i];
  74                 struct sw_flow *flow = t->lookup(t, key);
  75                 t->n_lookup++;
  76                 if (flow) {
  77                         t->n_matched++;
  78                         return flow;
  79                 }
  80         }
  81         return NULL;
  82 }
  83
  84 /* Inserts 'flow' into 'chain', replacing any duplicate flow.  Returns 0 if
  85  * successful or a negative error.
  86  *
  87  * If successful, 'flow' becomes owned by the chain, otherwise it is retained
  88  * by the caller.
  89  *
  90  * Caller must hold dp_mutex. */
  91 int chain_insert(struct sw_chain *chain, struct sw_flow *flow)
  92 {
  93         int i;
  94
  95         might_sleep();
  96         for (i = 0; i < chain->n_tables; i++) {
  97                 struct sw_table *t = chain->tables[i];
  98                 if (t->insert(t, flow))
  99                         return 0;
 100         }
 101
 102         return -ENOBUFS;
 103 }
 104
 105 /* Modifies actions in 'chain' that match 'key'.  If 'strict' set, wildcards
 106  * and priority must match.  Returns the number of flows that were modified.
 107  *
 108  * Expensive in the general case as currently implemented, since it requires
 109  * iterating through the entire contents of each table for keys that contain
 110  * wildcards.  Relatively cheap for fully specified keys. */
 111 int
 112 chain_modify(struct sw_chain *chain, const struct sw_flow_key *key,
 113                 uint16_t priority, int strict,
 114                 const struct ofp_action_header *actions, size_t actions_len)
 115 {
 116         int count = 0;
 117         int i;
 118
 119         for (i = 0; i < chain->n_tables; i++) {
 120                 struct sw_table *t = chain->tables[i];
 121                 count += t->modify(t, key, priority, strict, actions, actions_len);
 122         }
 123
 124         return count;
 125 }
 126
 127 /* Deletes from 'chain' any and all flows that match 'key'.  If 'out_port'
 128  * is not OFPP_NONE, then matching entries must have that port as an
 129  * argument for an output action.  If 'strict" is set, then wildcards and
 130  * priority must match.  Returns the number of flows that were deleted.
 131  *
 132  * Expensive in the general case as currently implemented, since it requires
 133  * iterating through the entire contents of each table for keys that contain
 134  * wildcards.  Relatively cheap for fully specified keys.
 135  *
 136  * Caller must hold dp_mutex. */
 137 int chain_delete(struct sw_chain *chain, const struct sw_flow_key *key,
 138                 uint16_t out_port, uint16_t priority, int strict)
 139 {
 140         int count = 0;
 141         int i;
 142
 143         might_sleep();
 144         for (i = 0; i < chain->n_tables; i++) {
 145                 struct sw_table *t = chain->tables[i];
 146                 count += t->delete(chain->dp, t, key, out_port, priority, strict);
 147         }
 148
 149         return count;
 150 }
 151
 152 /* Performs timeout processing on all the tables in 'chain'.  Returns the
 153  * number of flow entries deleted through expiration.
 154  *
 155  * Expensive as currently implemented, since it iterates through the entire
 156  * contents of each table.
 157  *
 158  * Caller must not hold dp_mutex, because individual tables take and release it
 159  * as necessary. */
 160 int chain_timeout(struct sw_chain *chain)
 161 {
 162         int count = 0;
 163         int i;
 164
 165         might_sleep();
 166         for (i = 0; i < chain->n_tables; i++) {
 167                 struct sw_table *t = chain->tables[i];
 168                 count += t->timeout(chain->dp, t);
 169         }
 170         return count;
 171 }
 172
 173 /* Destroys 'chain', which must not have any users. */
 174 void chain_destroy(struct sw_chain *chain)
 175 {
 176         int i;
 177
 178         synchronize_rcu();
 179         for (i = 0; i < chain->n_tables; i++) {
 180                 struct sw_table *t = chain->tables[i];
 181                 if (t->destroy)
 182                         t->destroy(t);
 183         }
 184         module_put(chain->owner);
 185         kfree(chain);
 186 }
 187
 188 int chain_set_hw_hook(struct sw_table *(*create_hw_table)(void),
 189                       struct module *owner)
 190 {
 191         int retval = -EBUSY;
 192
 193         spin_lock(&hook_lock);
 194         if (!create_hw_table_hook) {
 195                 create_hw_table_hook = create_hw_table;
 196                 hw_table_owner = owner;
 197                 retval = 0;
 198         }
 199         spin_unlock(&hook_lock);
 200
 201         return retval;
 202 }
 203 EXPORT_SYMBOL(chain_set_hw_hook);
 204
 205 void chain_clear_hw_hook(void)
 206 {
 207         create_hw_table_hook = NULL;
 208         hw_table_owner = NULL;
 209 }
 210 EXPORT_SYMBOL(chain_clear_hw_hook);