datapath/table.c

   1 /*
   2  * Copyright (c) 2009 Nicira Networks.
   3  * Distributed under the terms of the GNU GPL version 2.
   4  *
   5  * Significant portions of this file may be copied from parts of the Linux
   6  * kernel, by Linus Torvalds and others.
   7  */
   8
   9 #include "flow.h"
  10 #include "datapath.h"
  11
  12 #include <linux/gfp.h>
  13 #include <linux/jhash.h>
  14 #include <linux/slab.h>
  15 #include <linux/vmalloc.h>
  16 #include <linux/mm.h>
  17 #include <linux/highmem.h>
  18 #include <asm/pgtable.h>
  19
  20 static void free_table(struct sw_flow ***flows, unsigned int n_buckets,
  21                        int free_flows)
  22 {
  23         unsigned int i;
  24
  25         for (i = 0; i < n_buckets >> DP_L1_BITS; i++) {
  26                 struct sw_flow **l2 = flows[i];
  27                 if (free_flows) {
  28                         unsigned int j;
  29                         for (j = 0; j < DP_L1_SIZE; j++) {
  30                                 if (l2[j])
  31                                         flow_free(l2[j]);
  32                         }
  33                 }
  34                 free_page((unsigned long)l2);
  35         }
  36         kfree(flows);
  37 }
  38
  39 static struct sw_flow ***alloc_table(unsigned int n_buckets)
  40 {
  41         struct sw_flow ***flows;
  42         unsigned int i;
  43
  44         flows = kmalloc((n_buckets >> DP_L1_BITS) * sizeof(struct sw_flow**),
  45                         GFP_KERNEL);
  46         if (!flows)
  47                 return NULL;
  48         for (i = 0; i < n_buckets >> DP_L1_BITS; i++) {
  49                 flows[i] = (struct sw_flow **)get_zeroed_page(GFP_KERNEL);
  50                 if (!flows[i]) {
  51                         free_table(flows, i << DP_L1_BITS, 0);
  52                         return NULL;
  53                 }
  54         }
  55         return flows;
  56 }
  57
  58 struct dp_table *dp_table_create(unsigned int n_buckets)
  59 {
  60         struct dp_table *table;
  61
  62         table = kzalloc(sizeof *table, GFP_KERNEL);
  63         if (!table)
  64                 goto err;
  65
  66         table->n_buckets = n_buckets;
  67         table->flows[0] = alloc_table(n_buckets);
  68         if (!table[0].flows)
  69                 goto err_free_tables;
  70
  71         table->flows[1] = alloc_table(n_buckets);
  72         if (!table->flows[1])
  73                 goto err_free_flows0;
  74
  75         return table;
  76
  77 err_free_flows0:
  78         free_table(table->flows[0], table->n_buckets, 0);
  79 err_free_tables:
  80         kfree(table);
  81 err:
  82         return NULL;
  83 }
  84
  85 void dp_table_destroy(struct dp_table *table, int free_flows)
  86 {
  87         int i;
  88         for (i = 0; i < 2; i++)
  89                 free_table(table->flows[i], table->n_buckets, free_flows);
  90         kfree(table);
  91 }
  92
  93 static struct sw_flow **find_bucket(struct dp_table *table,
  94                                     struct sw_flow ***flows, u32 hash)
  95 {
  96         unsigned int l1 = (hash & (table->n_buckets - 1)) >> DP_L1_SHIFT;
  97         unsigned int l2 = hash & ((1 << DP_L2_BITS) - 1);
  98         return &flows[l1][l2];
  99 }
 100
 101 static struct sw_flow *lookup_table(struct dp_table *table,
 102                                     struct sw_flow ***flows, u32 hash,
 103                                     const struct odp_flow_key *key)
 104 {
 105         struct sw_flow **bucket = find_bucket(table, flows, hash);
 106         struct sw_flow *flow = rcu_dereference(*bucket);
 107         if (flow && !memcmp(&flow->key, key, sizeof(struct odp_flow_key)))
 108                 return flow;
 109         return NULL;
 110 }
 111
 112 static u32 flow_hash0(const struct odp_flow_key *key)
 113 {
 114         return jhash2((u32*)key, sizeof *key / sizeof(u32), 0xaaaaaaaa);
 115 }
 116
 117 static u32 flow_hash1(const struct odp_flow_key *key)
 118 {
 119         return jhash2((u32*)key, sizeof *key / sizeof(u32), 0x55555555);
 120 }
 121
 122 static void find_buckets(struct dp_table *table,
 123                          const struct odp_flow_key *key,
 124                          struct sw_flow **buckets[2])
 125 {
 126         buckets[0] = find_bucket(table, table->flows[0], flow_hash0(key));
 127         buckets[1] = find_bucket(table, table->flows[1], flow_hash1(key));
 128 }
 129
 130 struct sw_flow *dp_table_lookup(struct dp_table *table,
 131                                 const struct odp_flow_key *key)
 132 {
 133         struct sw_flow *flow;
 134         flow = lookup_table(table, table->flows[0], flow_hash0(key), key);
 135         if (!flow)
 136                 flow = lookup_table(table, table->flows[1],
 137                                     flow_hash1(key), key);
 138         return flow;
 139 }
 140
 141 int dp_table_foreach(struct dp_table *table,
 142                      int (*callback)(struct sw_flow *flow, void *aux),
 143                      void *aux)
 144 {
 145         unsigned int i, j, k;
 146         for (i = 0; i < 2; i++) {
 147                 for (j = 0; j < table->n_buckets >> DP_L1_BITS; j++) {
 148                         struct sw_flow **l2 = table->flows[i][j];
 149                         for (k = 0; k < DP_L1_SIZE; k++) {
 150                                 struct sw_flow *flow = rcu_dereference(l2[k]);
 151                                 if (flow) {
 152                                         int error = callback(flow, aux);
 153                                         if (error)
 154                                                 return error;
 155                                 }
 156                         }
 157                 }
 158         }
 159         return 0;
 160 }
 161
 162 static int insert_flow(struct sw_flow *flow, void *new_table_)
 163 {
 164         struct dp_table *new_table = new_table_;
 165         struct sw_flow **buckets[2];
 166         int i;
 167
 168         find_buckets(new_table, &flow->key, buckets);
 169         for (i = 0; i < 2; i++) {
 170                 if (!*buckets[i]) {
 171                         rcu_assign_pointer(*buckets[i], flow);
 172                         return 0;
 173                 }
 174         }
 175         WARN_ON_ONCE(1);
 176         return 0;
 177 }
 178
 179 static void dp_free_table_rcu(struct rcu_head *rcu)
 180 {
 181         struct dp_table *table = container_of(rcu, struct dp_table, rcu);
 182         dp_table_destroy(table, 0);
 183 }
 184
 185 int dp_table_expand(struct datapath *dp)
 186 {
 187         struct dp_table *old_table = rcu_dereference(dp->table);
 188         struct dp_table *new_table = dp_table_create(old_table->n_buckets * 2);
 189         if (!new_table)
 190                 return -ENOMEM;
 191         dp_table_foreach(old_table, insert_flow, new_table);
 192         rcu_assign_pointer(dp->table, new_table);
 193         call_rcu(&old_table->rcu, dp_free_table_rcu);
 194         return 0;
 195 }
 196
 197 static void dp_free_table_and_flows_rcu(struct rcu_head *rcu)
 198 {
 199         struct dp_table *table = container_of(rcu, struct dp_table, rcu);
 200         dp_table_destroy(table, 1);
 201 }
 202
 203 int dp_table_flush(struct datapath *dp)
 204 {
 205         struct dp_table *old_table = rcu_dereference(dp->table);
 206         struct dp_table *new_table = dp_table_create(DP_L1_SIZE);
 207         if (!new_table)
 208                 return -ENOMEM;
 209         rcu_assign_pointer(dp->table, new_table);
 210         call_rcu(&old_table->rcu, dp_free_table_and_flows_rcu);
 211         return 0;
 212 }
 213
 214 struct sw_flow **
 215 dp_table_lookup_for_insert(struct dp_table *table,
 216                            const struct odp_flow_key *target)
 217 {
 218         struct sw_flow **buckets[2];
 219         struct sw_flow **empty_bucket = NULL;
 220         int i;
 221
 222         find_buckets(table, target, buckets);
 223         for (i = 0; i < 2; i++) {
 224                 struct sw_flow *f = rcu_dereference(*buckets[i]);
 225                 if (f) {
 226                         if (!memcmp(&f->key, target, sizeof(struct odp_flow_key)))
 227                                 return buckets[i];
 228                 } else if (!empty_bucket)
 229                         empty_bucket = buckets[i];
 230         }
 231         return empty_bucket;
 232 }
 233
 234 int dp_table_delete(struct dp_table *table, struct sw_flow *target)
 235 {
 236         struct sw_flow **buckets[2];
 237         int i;
 238
 239         find_buckets(table, &target->key, buckets);
 240         for (i = 0; i < 2; i++) {
 241                 struct sw_flow *flow = rcu_dereference(*buckets[i]);
 242                 if (flow == target) {
 243                         rcu_assign_pointer(*buckets[i], NULL);
 244                         return 0;
 245                 }
 246         }
 247         return -ENOENT;
 248 }