datapath/table.c

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