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/rcupdate.h>
  11 #include <linux/slab.h>
  12
  13 /* Attempts to append 'table' to the set of tables in 'chain'.  Returns 0 or
  14  * negative error.  If 'table' is null it is assumed that table creation failed
  15  * due to out-of-memory. */
  16 static int add_table(struct sw_chain *chain, struct sw_table *table)
  17 {
  18         if (table == NULL)
  19                 return -ENOMEM;
  20         if (chain->n_tables >= CHAIN_MAX_TABLES) {
  21                 printk("too many tables in chain\n");
  22                 table->destroy(table);
  23                 return -ENOBUFS;
  24         }
  25         chain->tables[chain->n_tables++] = table;
  26         return 0;
  27 }
  28
  29 /* Creates and returns a new chain associated with 'dp'.  Returns NULL if the
  30  * chain cannot be created. */
  31 struct sw_chain *chain_create(struct datapath *dp)
  32 {
  33         struct sw_chain *chain = kzalloc(sizeof *chain, GFP_KERNEL);
  34         if (chain == NULL)
  35                 return NULL;
  36         chain->dp = dp;
  37
  38         if (add_table(chain, table_mac_create(TABLE_MAC_NUM_BUCKETS,
  39                                                 TABLE_MAC_MAX_FLOWS))
  40                 || add_table(chain, table_hash2_create(0x1EDC6F41, TABLE_HASH_MAX_FLOWS,
  41                                                 0x741B8CD7, TABLE_HASH_MAX_FLOWS))
  42                 || add_table(chain, table_linear_create(TABLE_LINEAR_MAX_FLOWS))) {
  43                 chain_destroy(chain);
  44                 return NULL;
  45         }
  46
  47         return chain;
  48 }
  49
  50 /* Searches 'chain' for a flow matching 'key', which must not have any wildcard
  51  * fields.  Returns the flow if successful, otherwise a null pointer.
  52  *
  53  * Caller must hold rcu_read_lock, and not release it until it is done with the
  54  * returned flow. */
  55 struct sw_flow *chain_lookup(struct sw_chain *chain,
  56                          const struct sw_flow_key *key)
  57 {
  58         int i;
  59
  60         BUG_ON(key->wildcards);
  61         for (i = 0; i < chain->n_tables; i++) {
  62                 struct sw_table *t = chain->tables[i];
  63                 struct sw_flow *flow = t->lookup(t, key);
  64                 if (flow)
  65                         return flow;
  66         }
  67         return NULL;
  68 }
  69
  70 /* Inserts 'flow' into 'chain', replacing any duplicate flow.  Returns 0 if
  71  * successful or a negative error.
  72  *
  73  * If successful, 'flow' becomes owned by the chain, otherwise it is retained
  74  * by the caller.
  75  *
  76  * Caller must hold rcu_read_lock.  If insertion is successful, it must not
  77  * release rcu_read_lock until it is done with the inserted flow. */
  78 int chain_insert(struct sw_chain *chain, struct sw_flow *flow)
  79 {
  80         int i;
  81
  82         for (i = 0; i < chain->n_tables; i++) {
  83                 struct sw_table *t = chain->tables[i];
  84                 if (t->insert(t, flow))
  85                         return 0;
  86         }
  87
  88         return -ENOBUFS;
  89 }
  90
  91 /* Deletes from 'chain' any and all flows that match 'key'.  Returns the number
  92  * of flows that were deleted.
  93  *
  94  * Expensive in the general case as currently implemented, since it requires
  95  * iterating through the entire contents of each table for keys that contain
  96  * wildcards.  Relatively cheap for fully specified keys.
  97  *
  98  * The caller need not hold any locks. */
  99 int chain_delete(struct sw_chain *chain, const struct sw_flow_key *key, int strict)
 100 {
 101         int count = 0;
 102         int i;
 103
 104         for (i = 0; i < chain->n_tables; i++) {
 105                 struct sw_table *t = chain->tables[i];
 106                 rcu_read_lock();
 107                 count += t->delete(t, key, strict);
 108                 rcu_read_unlock();
 109         }
 110
 111         return count;
 112
 113 }
 114
 115 /* Performs timeout processing on all the tables in 'chain'.  Returns the
 116  * number of flow entries deleted through expiration.
 117  *
 118  * Expensive as currently implemented, since it iterates through the entire
 119  * contents of each table.
 120  *
 121  * The caller need not hold any locks. */
 122 int chain_timeout(struct sw_chain *chain)
 123 {
 124         int count = 0;
 125         int i;
 126
 127         for (i = 0; i < chain->n_tables; i++) {
 128                 struct sw_table *t = chain->tables[i];
 129                 rcu_read_lock();
 130                 count += t->timeout(chain->dp, t);
 131                 rcu_read_unlock();
 132         }
 133         return count;
 134 }
 135
 136 /* Destroys 'chain', which must not have any users. */
 137 void chain_destroy(struct sw_chain *chain)
 138 {
 139         int i;
 140
 141         synchronize_rcu();
 142         for (i = 0; i < chain->n_tables; i++) {
 143                 struct sw_table *t = chain->tables[i];
 144                 t->destroy(t);
 145         }
 146         kfree(chain);
 147 }
 148
 149 /* Prints statistics for each of the tables in 'chain'. */
 150 void chain_print_stats(struct sw_chain *chain)
 151 {
 152         int i;
 153
 154         printk("\n");
 155         for (i = 0; i < chain->n_tables; i++) {
 156                 struct sw_table *t = chain->tables[i];
 157                 struct sw_table_stats stats;
 158                 t->stats(t, &stats);
 159                 printk("%s: %lu/%lu flows\n",
 160                                         stats.name, stats.n_flows, stats.max_flows);
 161         }
 162 }