datapath/chain.c

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