pintos-os.org Git - openvswitch/blob - 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/random.h>
  15 #include <linux/slab.h>
  16 #include <linux/vmalloc.h>
  17 #include <linux/mm.h>
  18 #include <linux/highmem.h>
  19 #include <asm/pgtable.h>
  20
  21 static inline int bucket_size(int n_flows)
  22 {
  23         return sizeof(struct dp_bucket) + sizeof(struct sw_flow*) * n_flows;
  24 }
  25
  26 static struct dp_bucket *dp_bucket_alloc(int n_flows)
  27 {
  28         return kmalloc(bucket_size(n_flows), GFP_KERNEL);
  29 }
  30
  31 static void free_buckets(struct dp_bucket ***l1, unsigned int n_buckets,
  32                          int free_flows)
  33 {
  34         unsigned int i;
  35
  36         for (i = 0; i < n_buckets >> DP_L1_BITS; i++) {
  37                 struct dp_bucket **l2 = l1[i];
  38                 unsigned int j;
  39
  40                 for (j = 0; j < DP_L1_SIZE; j++) {
  41                         struct dp_bucket *bucket = l2[j];
  42                         if (!bucket)
  43                                 continue;
  44
  45                         if (free_flows) {
  46                                 unsigned int k;
  47                                 for (k = 0; k < bucket->n_flows; k++)
  48                                         flow_free(bucket->flows[k]);
  49                         }
  50                         kfree(bucket);
  51                 }
  52                 free_page((unsigned long)l2);
  53         }
  54         kfree(l1);
  55 }
  56
  57 static struct dp_bucket ***alloc_buckets(unsigned int n_buckets)
  58 {
  59         struct dp_bucket ***l1;
  60         unsigned int i;
  61
  62         l1 = kmalloc((n_buckets >> DP_L1_BITS) * sizeof(struct dp_bucket**),
  63                      GFP_KERNEL);
  64         if (!l1)
  65                 return NULL;
  66         for (i = 0; i < n_buckets >> DP_L1_BITS; i++) {
  67                 l1[i] = (struct dp_bucket **)get_zeroed_page(GFP_KERNEL);
  68                 if (!l1[i]) {
  69                         free_buckets(l1, i << DP_L1_BITS, 0);
  70                         return NULL;
  71                 }
  72         }
  73         return l1;
  74 }
  75
  76 /**
  77  * dp_table_create - create and return a new flow table
  78  * @n_buckets: number of buckets in the new table
  79  *
  80  * Creates and returns a new flow table, or %NULL if memory cannot be
  81  * allocated.  @n_buckets must be a power of 2 in the range %DP_L1_SIZE to
  82  * %DP_MAX_BUCKETS.
  83  */
  84 struct dp_table *dp_table_create(unsigned int n_buckets)
  85 {
  86         struct dp_table *table;
  87
  88         table = kzalloc(sizeof *table, GFP_KERNEL);
  89         if (!table)
  90                 goto err;
  91
  92         table->n_buckets = n_buckets;
  93         table->buckets = alloc_buckets(n_buckets);
  94         if (!table->buckets)
  95                 goto err_free_table;
  96         get_random_bytes(&table->hash_seed, sizeof table->hash_seed);
  97
  98         return table;
  99
 100 err_free_table:
 101         kfree(table);
 102 err:
 103         return NULL;
 104 }
 105
 106 /**
 107  * dp_table_destroy - destroy flow table and optionally the flows it contains
 108  * @table: table to destroy (must not be %NULL)
 109  * @free_flows: whether to destroy the flows
 110  *
 111  * If @free_flows is zero, then the buckets in @table are destroyed but not the
 112  * flows within those buckets.  This behavior is useful when a table is being
 113  * replaced by a larger or smaller one without destroying the flows.
 114  *
 115  * If @free_flows is nonzero, then the flows in @table are destroyed as well as
 116  * the buckets.
 117  */
 118 void dp_table_destroy(struct dp_table *table, int free_flows)
 119 {
 120         free_buckets(table->buckets, table->n_buckets, free_flows);
 121         kfree(table);
 122 }
 123
 124 static struct dp_bucket **find_bucket(struct dp_table *table, u32 hash)
 125 {
 126         unsigned int l1 = (hash & (table->n_buckets - 1)) >> DP_L1_SHIFT;
 127         unsigned int l2 = hash & ((1 << DP_L2_BITS) - 1);
 128         return &table->buckets[l1][l2];
 129 }
 130
 131 static int search_bucket(const struct dp_bucket *bucket, const struct odp_flow_key *key)
 132 {
 133         int i;
 134
 135         for (i = 0; i < bucket->n_flows; i++) {
 136                 struct sw_flow *flow = rcu_dereference(bucket->flows[i]);
 137                 if (!memcmp(&flow->key, key, sizeof(struct odp_flow_key)))
 138                         return i;
 139         }
 140
 141         return -1;
 142 }
 143
 144 static struct sw_flow *lookup_flow(struct dp_table *table, u32 hash,
 145                                    const struct odp_flow_key *key)
 146 {
 147         struct dp_bucket **bucketp = find_bucket(table, hash);
 148         struct dp_bucket *bucket = rcu_dereference(*bucketp);
 149         int index;
 150
 151         if (!bucket)
 152                 return NULL;
 153
 154         index = search_bucket(bucket, key);
 155         if (index < 0)
 156                 return NULL;
 157
 158         return bucket->flows[index];
 159 }
 160
 161 static u32 flow_hash(const struct dp_table *table,
 162                      const struct odp_flow_key *key)
 163 {
 164         return jhash2((u32*)key, sizeof *key / sizeof(u32), table->hash_seed);
 165 }
 166
 167 /**
 168  * dp_table_lookup - searches flow table for a matching flow
 169  * @table: flow table to search
 170  * @key: flow key for which to search
 171  *
 172  * Searches @table for a flow whose key is equal to @key.  Returns the flow if
 173  * successful, otherwise %NULL.
 174  */
 175 struct sw_flow *dp_table_lookup(struct dp_table *table,
 176                                 const struct odp_flow_key *key)
 177 {
 178         return lookup_flow(table, flow_hash(table, key), key);
 179 }
 180
 181 /**
 182  * dp_table_foreach - iterate through flow table
 183  * @table: table to iterate
 184  * @callback: function to call for each flow entry
 185  * @aux: Extra data to pass to @callback
 186  *
 187  * Iterates through all of the flows in @table in hash order, passing each of
 188  * them in turn to @callback.  If @callback returns nonzero, this terminates
 189  * the iteration and dp_table_foreach() returns the same value.  Returns 0 if
 190  * @callback never returns nonzero.
 191  *
 192  * This function does not try to intelligently handle the case where @callback
 193  * adds or removes flows in @table.
 194  */
 195 int dp_table_foreach(struct dp_table *table,
 196                      int (*callback)(struct sw_flow *flow, void *aux),
 197                      void *aux)
 198 {
 199         unsigned int i, j, k;
 200         for (i = 0; i < table->n_buckets >> DP_L1_BITS; i++) {
 201                 struct dp_bucket **l2 = table->buckets[i];
 202                 for (j = 0; j < DP_L1_SIZE; j++) {
 203                         struct dp_bucket *bucket = rcu_dereference(l2[j]);
 204                         if (!bucket)
 205                                 continue;
 206
 207                         for (k = 0; k < bucket->n_flows; k++) {
 208                                 int error = (*callback)(bucket->flows[k], aux);
 209                                 if (error)
 210                                         return error;
 211                         }
 212                 }
 213         }
 214         return 0;
 215 }
 216
 217 static int insert_flow(struct sw_flow *flow, void *new_table_)
 218 {
 219         struct dp_table *new_table = new_table_;
 220         return dp_table_insert(new_table, flow);
 221 }
 222
 223 static void dp_free_table_rcu(struct rcu_head *rcu)
 224 {
 225         struct dp_table *table = container_of(rcu, struct dp_table, rcu);
 226         dp_table_destroy(table, 0);
 227 }
 228
 229 /**
 230  * dp_table_expand - replace datapath's flow table by one with more buckets
 231  * @dp: datapath to expand
 232  *
 233  * Replaces @dp's flow table by one that has twice as many buckets.  All of the
 234  * flows in @dp's flow table are moved to the new flow table.  Returns 0 if
 235  * successful, otherwise a negative error.
 236  */
 237 int dp_table_expand(struct datapath *dp)
 238 {
 239         struct dp_table *old_table = rcu_dereference(dp->table);
 240         struct dp_table *new_table;
 241
 242         new_table = dp_table_create(old_table->n_buckets * 2);
 243         if (!new_table)
 244                 goto error;
 245
 246         if (dp_table_foreach(old_table, insert_flow, new_table))
 247                 goto error_free_new_table;
 248
 249         rcu_assign_pointer(dp->table, new_table);
 250         call_rcu(&old_table->rcu, dp_free_table_rcu);
 251         return 0;
 252
 253 error_free_new_table:
 254         dp_table_destroy(new_table, 0);
 255 error:
 256         return -ENOMEM;
 257 }
 258
 259 static void dp_free_table_and_flows_rcu(struct rcu_head *rcu)
 260 {
 261         struct dp_table *table = container_of(rcu, struct dp_table, rcu);
 262         dp_table_destroy(table, 1);
 263 }
 264
 265 /**
 266  * dp_table_flush - clear datapath's flow table
 267  * @dp: datapath to clear
 268  *
 269  * Replaces @dp's flow table by an empty flow table, destroying all the flows
 270  * in the old table (after a suitable RCU grace period).
 271  */
 272 int dp_table_flush(struct datapath *dp)
 273 {
 274         struct dp_table *old_table = rcu_dereference(dp->table);
 275         struct dp_table *new_table = dp_table_create(DP_L1_SIZE);
 276         if (!new_table)
 277                 return -ENOMEM;
 278         rcu_assign_pointer(dp->table, new_table);
 279         call_rcu(&old_table->rcu, dp_free_table_and_flows_rcu);
 280         return 0;
 281 }
 282
 283 static void dp_free_bucket_rcu(struct rcu_head *rcu)
 284 {
 285         struct dp_bucket *bucket = container_of(rcu, struct dp_bucket, rcu);
 286         kfree(bucket);
 287 }
 288
 289 /**
 290  * dp_table_insert - insert flow into table
 291  * @table: table in which to insert flow
 292  * @target: flow to insert
 293  *
 294  * The caller must ensure that no flow with key identical to @target->key
 295  * already exists in @table.  Returns 0 or a negative error (currently just
 296  * -ENOMEM).
 297  *
 298  * The caller is responsible for updating &struct datapath's n_flows member.
 299  */
 300 int dp_table_insert(struct dp_table *table, struct sw_flow *target)
 301 {
 302         u32 hash = flow_hash(table, &target->key);
 303         struct dp_bucket **oldp = find_bucket(table, hash);
 304         struct dp_bucket *old = *rcu_dereference(oldp);
 305         unsigned int n = old ? old->n_flows : 0;
 306         struct dp_bucket *new = dp_bucket_alloc(n + 1);
 307
 308         if (!new)
 309                 return -ENOMEM;
 310
 311         new->n_flows = n + 1;
 312         if (old)
 313                 memcpy(new->flows, old->flows, n * sizeof(struct sw_flow*));
 314         new->flows[n] = target;
 315
 316         rcu_assign_pointer(*oldp, new);
 317         if (old)
 318                 call_rcu(&old->rcu, dp_free_bucket_rcu);
 319
 320         return 0;
 321 }
 322
 323 /**
 324  * dp_table_delete - remove flow from table
 325  * @table: table from which to remove flow
 326  * @target: flow to remove
 327  *
 328  * The caller must ensure that @target itself is in @table.  (It is not
 329  * good enough for @table to contain a different flow with a key equal to
 330  * @target's key.)
 331  *
 332  * Returns 0 or a negative error (currently just -ENOMEM).  Yes, it *is*
 333  * possible for a flow deletion to fail due to lack of memory.
 334  *
 335  * The caller is responsible for updating &struct datapath's n_flows member.
 336  */
 337 int dp_table_delete(struct dp_table *table, struct sw_flow *target)
 338 {
 339         u32 hash = flow_hash(table, &target->key);
 340         struct dp_bucket **oldp = find_bucket(table, hash);
 341         struct dp_bucket *old = *rcu_dereference(oldp);
 342         unsigned int n = old->n_flows;
 343         struct dp_bucket *new;
 344
 345         if (n > 1) {
 346                 unsigned int i;
 347
 348                 new = dp_bucket_alloc(n - 1);
 349                 if (!new)
 350                         return -ENOMEM;
 351
 352                 new->n_flows = 0;
 353                 for (i = 0; i < n; i++) {
 354                         struct sw_flow *flow = old->flows[i];
 355                         if (flow != target)
 356                                 new->flows[new->n_flows++] = flow;
 357                 }
 358                 WARN_ON_ONCE(new->n_flows != n - 1);
 359         } else {
 360                 new = NULL;
 361         }
 362
 363         rcu_assign_pointer(*oldp, new);
 364         call_rcu(&old->rcu, dp_free_bucket_rcu);
 365
 366         return 0;
 367 }