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