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