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