datapath/table.c

   1 /*
   2  * Copyright (c) 2009, 2010 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 #include "table.h"
  12
  13 #include <linux/gfp.h>
  14 #include <linux/slab.h>
  15 #include <linux/mm.h>
  16 #include <asm/pgtable.h>
  17
  18 /**
  19  * struct tbl - hash table
  20  * @n_buckets: number of buckets (a power of 2 between %TBL_L1_SIZE and
  21  * %TBL_MAX_BUCKETS)
  22  * @buckets: pointer to @n_buckets/%TBL_L1_SIZE pointers to %TBL_L1_SIZE pointers
  23  * to buckets
  24  * @rcu: RCU callback structure
  25  * @obj_destructor: Called on each element when the table is destroyed.
  26  *
  27  * The @buckets array is logically an array of pointers to buckets.  It is
  28  * broken into two levels to avoid the need to kmalloc() any object larger than
  29  * a single page or to use vmalloc().  @buckets is always nonnull, as is each
  30  * @buckets[i], but each @buckets[i][j] is nonnull only if the specified hash
  31  * bucket is nonempty (for 0 <= i < @n_buckets/%TBL_L1_SIZE, 0 <= j <
  32  * %TBL_L1_SIZE).
  33  */
  34 struct tbl {
  35         struct rcu_head rcu;
  36         unsigned int n_buckets;
  37         struct tbl_bucket ***buckets;
  38         unsigned int count;
  39         void (*obj_destructor)(struct tbl_node *);
  40 };
  41
  42 /**
  43  * struct tbl_bucket - single bucket within a hash table
  44  * @rcu: RCU callback structure
  45  * @n_objs: number of objects in @objs[] array
  46  * @objs: array of @n_objs pointers to table nodes contained inside objects
  47  *
  48  * The expected number of objects per bucket is 1, but this allows for an
  49  * arbitrary number of collisions.
  50  */
  51 struct tbl_bucket {
  52         struct rcu_head rcu;
  53         unsigned int n_objs;
  54         struct tbl_node *objs[];
  55 };
  56
  57 static inline int bucket_size(int n_objs)
  58 {
  59         return sizeof(struct tbl_bucket) + sizeof(struct tbl_node *) * n_objs;
  60 }
  61
  62 static struct tbl_bucket *bucket_alloc(int n_objs)
  63 {
  64         return kmalloc(bucket_size(n_objs), GFP_KERNEL);
  65 }
  66
  67 static void free_buckets(struct tbl_bucket ***l1, unsigned int n_buckets,
  68                          void (*free_obj)(struct tbl_node *))
  69 {
  70         unsigned int i;
  71
  72         for (i = 0; i < n_buckets >> TBL_L1_BITS; i++) {
  73                 struct tbl_bucket **l2 = l1[i];
  74                 unsigned int j;
  75
  76                 for (j = 0; j < TBL_L1_SIZE; j++) {
  77                         struct tbl_bucket *bucket = l2[j];
  78                         if (!bucket)
  79                                 continue;
  80
  81                         if (free_obj) {
  82                                 unsigned int k;
  83                                 for (k = 0; k < bucket->n_objs; k++)
  84                                         free_obj(bucket->objs[k]);
  85                         }
  86                         kfree(bucket);
  87                 }
  88                 free_page((unsigned long)l2);
  89         }
  90         kfree(l1);
  91 }
  92
  93 static struct tbl_bucket ***alloc_buckets(unsigned int n_buckets)
  94 {
  95         struct tbl_bucket ***l1;
  96         unsigned int i;
  97
  98         l1 = kmalloc((n_buckets >> TBL_L1_BITS) * sizeof(struct tbl_bucket **),
  99                      GFP_KERNEL);
 100         if (!l1)
 101                 return NULL;
 102         for (i = 0; i < n_buckets >> TBL_L1_BITS; i++) {
 103                 l1[i] = (struct tbl_bucket **)get_zeroed_page(GFP_KERNEL);
 104                 if (!l1[i]) {
 105                         free_buckets(l1, i << TBL_L1_BITS, 0);
 106                         return NULL;
 107                 }
 108         }
 109         return l1;
 110 }
 111
 112 /**
 113  * tbl_create - create and return a new hash table
 114  * @n_buckets: number of buckets in the new table
 115  *
 116  * Creates and returns a new hash table, or %NULL if memory cannot be
 117  * allocated.  @n_buckets must be a power of 2 in the range %TBL_L1_SIZE to
 118  * %TBL_MAX_BUCKETS.
 119  */
 120 struct tbl *tbl_create(unsigned int n_buckets)
 121 {
 122         struct tbl *table;
 123
 124         if (!n_buckets)
 125                 n_buckets = TBL_L1_SIZE;
 126
 127         table = kzalloc(sizeof *table, GFP_KERNEL);
 128         if (!table)
 129                 goto err;
 130
 131         table->n_buckets = n_buckets;
 132         table->buckets = alloc_buckets(n_buckets);
 133         if (!table->buckets)
 134                 goto err_free_table;
 135
 136         return table;
 137
 138 err_free_table:
 139         kfree(table);
 140 err:
 141         return NULL;
 142 }
 143
 144 /**
 145  * tbl_destroy - destroy hash table and optionally the objects it contains
 146  * @table: table to destroy
 147  * @destructor: function to be called on objects at destruction time
 148  *
 149  * If a destructor is null, then the buckets in @table are destroyed
 150  * but not the objects within those buckets.  This behavior is useful when a
 151  * table is being replaced by a larger or smaller one without destroying the
 152  * objects.
 153  *
 154  * If a destructor is not null, then it is called on the objects in @table
 155  * before destroying the buckets.
 156  */
 157 void tbl_destroy(struct tbl *table, void (*destructor)(struct tbl_node *))
 158 {
 159         if (!table)
 160                 return;
 161
 162         free_buckets(table->buckets, table->n_buckets, destructor);
 163         kfree(table);
 164 }
 165
 166 static void destroy_table_rcu(struct rcu_head *rcu)
 167 {
 168         struct tbl *table = container_of(rcu, struct tbl, rcu);
 169         tbl_destroy(table, table->obj_destructor);
 170 }
 171
 172 /**
 173  * tbl_deferred_destroy - destroy table after a RCU grace period
 174  * @table: table to destroy
 175  * @destructor: function to be called on objects at destruction time
 176  *
 177  * Calls tbl_destroy() on @table after an RCU grace period. If @destructor is
 178  * not null it is called on every element before the table is destroyed. */
 179 void tbl_deferred_destroy(struct tbl *table, void (*destructor)(struct tbl_node *))
 180 {
 181         if (!table)
 182                 return;
 183
 184         table->obj_destructor = destructor;
 185         call_rcu(&table->rcu, destroy_table_rcu);
 186 }
 187
 188 static struct tbl_bucket **find_bucket(struct tbl *table, u32 hash)
 189 {
 190         unsigned int l1 = (hash & (table->n_buckets - 1)) >> TBL_L1_SHIFT;
 191         unsigned int l2 = hash & ((1 << TBL_L2_BITS) - 1);
 192         return &table->buckets[l1][l2];
 193 }
 194
 195 static int search_bucket(const struct tbl_bucket *bucket, void *target, u32 hash,
 196                          int (*cmp)(const struct tbl_node *, void *))
 197 {
 198         int i;
 199
 200         for (i = 0; i < bucket->n_objs; i++) {
 201                 struct tbl_node *obj = rcu_dereference(bucket->objs[i]);
 202                 if (obj->hash == hash && likely(cmp(obj, target)))
 203                         return i;
 204         }
 205
 206         return -1;
 207 }
 208
 209 /**
 210  * tbl_lookup - searches hash table for a matching object
 211  * @table: hash table to search
 212  * @target: identifier for the object that is being searched for, will be
 213  * provided as an argument to @cmp when making comparisions
 214  * @hash: hash of @target
 215  * @cmp: comparision function to match objects with the given hash, returns
 216  * nonzero if the objects match, zero otherwise
 217  *
 218  * Searches @table for an object identified by @target.  Returns the tbl_node
 219  * contained in the object if successful, otherwise %NULL.
 220  */
 221 struct tbl_node *tbl_lookup(struct tbl *table, void *target, u32 hash,
 222                             int (*cmp)(const struct tbl_node *, void *))
 223 {
 224         struct tbl_bucket **bucketp = find_bucket(table, hash);
 225         struct tbl_bucket *bucket = rcu_dereference(*bucketp);
 226         int index;
 227
 228         if (!bucket)
 229                 return NULL;
 230
 231         index = search_bucket(bucket, target, hash, cmp);
 232         if (index < 0)
 233                 return NULL;
 234
 235         return bucket->objs[index];
 236 }
 237
 238 /**
 239  * tbl_foreach - iterate through hash table
 240  * @table: table to iterate
 241  * @callback: function to call for each entry
 242  * @aux: Extra data to pass to @callback
 243  *
 244  * Iterates through all of the objects in @table in hash order, passing each of
 245  * them in turn to @callback.  If @callback returns nonzero, this terminates
 246  * the iteration and tbl_foreach() returns the same value.  Returns 0 if
 247  * @callback never returns nonzero.
 248  *
 249  * This function does not try to intelligently handle the case where @callback
 250  * adds or removes flows in @table.
 251  */
 252 int tbl_foreach(struct tbl *table,
 253                 int (*callback)(struct tbl_node *, void *aux), void *aux)
 254 {
 255         unsigned int i, j, k;
 256         for (i = 0; i < table->n_buckets >> TBL_L1_BITS; i++) {
 257                 struct tbl_bucket **l2 = table->buckets[i];
 258                 for (j = 0; j < TBL_L1_SIZE; j++) {
 259                         struct tbl_bucket *bucket = rcu_dereference(l2[j]);
 260                         if (!bucket)
 261                                 continue;
 262
 263                         for (k = 0; k < bucket->n_objs; k++) {
 264                                 int error = (*callback)(bucket->objs[k], aux);
 265                                 if (error)
 266                                         return error;
 267                         }
 268                 }
 269         }
 270         return 0;
 271 }
 272
 273 static int insert_table_flow(struct tbl_node *node, void *new_table_)
 274 {
 275         struct tbl *new_table = new_table_;
 276         return tbl_insert(new_table, node, node->hash);
 277 }
 278
 279 /**
 280  * tbl_expand - create a hash table with more buckets
 281  * @table: table to expand
 282  *
 283  * Creates a new table containing the same objects as @table but with twice
 284  * as many buckets.  Returns 0 if successful, otherwise a negative error.  The
 285  * caller should free @table upon success (probably using
 286  * tbl_deferred_destroy()).
 287  */
 288 struct tbl *tbl_expand(struct tbl *table)
 289 {
 290         int err;
 291         int n_buckets = table->n_buckets * 2;
 292         struct tbl *new_table;
 293
 294         if (n_buckets >= TBL_MAX_BUCKETS) {
 295                 err = -ENOSPC;
 296                 goto error;
 297         }
 298
 299         err = -ENOMEM;
 300         new_table = tbl_create(n_buckets);
 301         if (!new_table)
 302                 goto error;
 303
 304         if (tbl_foreach(table, insert_table_flow, new_table))
 305                 goto error_free_new_table;
 306
 307         return new_table;
 308
 309 error_free_new_table:
 310         tbl_destroy(new_table, NULL);
 311 error:
 312         return ERR_PTR(err);
 313 }
 314
 315 /**
 316  * tbl_n_buckets - returns the number of buckets
 317  * @table: table to examine
 318  *
 319  * Returns the number of buckets currently allocated in @table, useful when
 320  * deciding whether to expand.
 321  */
 322 int tbl_n_buckets(struct tbl *table)
 323 {
 324         return table->n_buckets;
 325 }
 326
 327 static void free_bucket_rcu(struct rcu_head *rcu)
 328 {
 329         struct tbl_bucket *bucket = container_of(rcu, struct tbl_bucket, rcu);
 330         kfree(bucket);
 331 }
 332
 333 /**
 334  * tbl_insert - insert object into table
 335  * @table: table in which to insert object
 336  * @target: tbl_node contained in object to insert
 337  * @hash: hash of object to insert
 338  *
 339  * The caller must ensure that no object considered to be identical to @target
 340  * already exists in @table.  Returns 0 or a negative error (currently just
 341  * -ENOMEM).
 342  */
 343 int tbl_insert(struct tbl *table, struct tbl_node *target, u32 hash)
 344 {
 345         struct tbl_bucket **oldp = find_bucket(table, hash);
 346         struct tbl_bucket *old = *rcu_dereference(oldp);
 347         unsigned int n = old ? old->n_objs : 0;
 348         struct tbl_bucket *new = bucket_alloc(n + 1);
 349
 350         if (!new)
 351                 return -ENOMEM;
 352
 353         target->hash = hash;
 354
 355         new->n_objs = n + 1;
 356         if (old)
 357                 memcpy(new->objs, old->objs, n * sizeof(struct tbl_node *));
 358         new->objs[n] = target;
 359
 360         rcu_assign_pointer(*oldp, new);
 361         if (old)
 362                 call_rcu(&old->rcu, free_bucket_rcu);
 363
 364         table->count++;
 365
 366         return 0;
 367 }
 368
 369 /**
 370  * tbl_remove - remove object from table
 371  * @table: table from which to remove object
 372  * @target: tbl_node inside of object to remove
 373  *
 374  * The caller must ensure that @target itself is in @table.  (It is not
 375  * good enough for @table to contain a different object considered identical
 376  * @target.)
 377  *
 378  * Returns 0 or a negative error (currently just -ENOMEM).  Yes, it *is*
 379  * possible for object deletion to fail due to lack of memory.
 380  */
 381 int tbl_remove(struct tbl *table, struct tbl_node *target)
 382 {
 383         struct tbl_bucket **oldp = find_bucket(table, target->hash);
 384         struct tbl_bucket *old = *rcu_dereference(oldp);
 385         unsigned int n = old->n_objs;
 386         struct tbl_bucket *new;
 387
 388         if (n > 1) {
 389                 unsigned int i;
 390
 391                 new = bucket_alloc(n - 1);
 392                 if (!new)
 393                         return -ENOMEM;
 394
 395                 new->n_objs = 0;
 396                 for (i = 0; i < n; i++) {
 397                         struct tbl_node *obj = old->objs[i];
 398                         if (obj != target)
 399                                 new->objs[new->n_objs++] = obj;
 400                 }
 401                 WARN_ON_ONCE(new->n_objs != n - 1);
 402         } else {
 403                 new = NULL;
 404         }
 405
 406         rcu_assign_pointer(*oldp, new);
 407         call_rcu(&old->rcu, free_bucket_rcu);
 408
 409         table->count--;
 410
 411         return 0;
 412 }
 413
 414 /**
 415  * tbl_count - retrieves the number of stored objects
 416  * @table: table to count
 417  *
 418  * Returns the number of objects that have been inserted into the hash table.
 419  */
 420 unsigned int tbl_count(struct tbl *table)
 421 {
 422         return table->count;
 423 }