lib/ccmap.c

   1 /*
   2  * Copyright (c) 2014, 2016 Nicira, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <config.h>
  18 #include "ccmap.h"
  19 #include "coverage.h"
  20 #include "bitmap.h"
  21 #include "hash.h"
  22 #include "ovs-rcu.h"
  23 #include "random.h"
  24 #include "util.h"
  25
  26 COVERAGE_DEFINE(ccmap_expand);
  27 COVERAGE_DEFINE(ccmap_shrink);
  28
  29 /* A count-only version of the cmap. */
  30
  31 /* Allow protected access to the value without atomic semantics.  This makes
  32  * the exclusive writer somewhat faster. */
  33 typedef union {
  34     unsigned long long         protected_value;
  35     ATOMIC(unsigned long long) atomic_value;
  36 } ccmap_node_t;
  37 BUILD_ASSERT_DECL(sizeof(ccmap_node_t) == sizeof(uint64_t));
  38
  39 static uint64_t
  40 ccmap_node_get(const ccmap_node_t *node)
  41 {
  42     uint64_t value;
  43
  44     atomic_read_relaxed(&CONST_CAST(ccmap_node_t *, node)->atomic_value,
  45                         &value);
  46
  47     return value;
  48 }
  49
  50 /* It is safe to allow compiler optimize reads by the exclusive writer. */
  51 static uint64_t
  52 ccmap_node_get_protected(const ccmap_node_t *node)
  53 {
  54     return node->protected_value;
  55 }
  56
  57 static void
  58 ccmap_node_set_protected(ccmap_node_t *node, uint64_t value)
  59 {
  60     atomic_store_relaxed(&node->atomic_value, value);
  61 }
  62
  63 static uint64_t
  64 ccmap_node(uint32_t count, uint32_t hash)
  65 {
  66     return (uint64_t)count << 32 | hash;
  67 }
  68
  69 static uint32_t
  70 ccmap_node_hash(uint64_t node)
  71 {
  72     return node;
  73 }
  74
  75 static uint32_t
  76 ccmap_node_count(uint64_t node)
  77 {
  78     return node >> 32;
  79 }
  80
  81 /* Number of nodes per bucket. */
  82 #define CCMAP_K (CACHE_LINE_SIZE / sizeof(ccmap_node_t))
  83
  84 /* A cuckoo hash bucket.  Designed to be cache-aligned and exactly one cache
  85  * line long. */
  86 struct ccmap_bucket {
  87     /* Each node incudes both the hash (low 32-bits) and the count (high
  88      * 32-bits), allowing readers always getting a consistent pair. */
  89     ccmap_node_t nodes[CCMAP_K];
  90 };
  91 BUILD_ASSERT_DECL(sizeof(struct ccmap_bucket) == CACHE_LINE_SIZE);
  92
  93 /* Default maximum load factor (as a fraction of UINT32_MAX + 1) before
  94  * enlarging a ccmap.  Reasonable values lie between about 75% and 93%.  Smaller
  95  * values waste memory; larger values increase the average insertion time. */
  96 #define CCMAP_MAX_LOAD ((uint32_t) (UINT32_MAX * .85))
  97
  98 /* Default minimum load factor (as a fraction of UINT32_MAX + 1) before
  99  * shrinking a ccmap.  Currently, the value is chosen to be 20%, this
 100  * means ccmap will have a 40% load factor after shrink. */
 101 #define CCMAP_MIN_LOAD ((uint32_t) (UINT32_MAX * .20))
 102
 103 /* The implementation of a concurrent hash map. */
 104 struct ccmap_impl {
 105     unsigned int n_unique;      /* Number of in-use nodes. */
 106     unsigned int n;             /* Number of hashes inserted. */
 107     unsigned int max_n;         /* Max nodes before enlarging. */
 108     unsigned int min_n;         /* Min nodes before shrinking. */
 109     uint32_t mask;              /* Number of 'buckets', minus one. */
 110     uint32_t basis;             /* Basis for rehashing client's hash values. */
 111
 112     /* Padding to make ccmap_impl exactly one cache line long. */
 113     uint8_t pad[CACHE_LINE_SIZE - sizeof(unsigned int) * 6];
 114
 115     struct ccmap_bucket buckets[];
 116 };
 117 BUILD_ASSERT_DECL(sizeof(struct ccmap_impl) == CACHE_LINE_SIZE);
 118
 119 static struct ccmap_impl *ccmap_rehash(struct ccmap *, uint32_t mask);
 120
 121 /* Given a rehashed value 'hash', returns the other hash for that rehashed
 122  * value.  This is symmetric: other_hash(other_hash(x)) == x.  (See also "Hash
 123  * Functions" at the top of cmap.c.) */
 124 static uint32_t
 125 other_hash(uint32_t hash)
 126 {
 127     return (hash << 16) | (hash >> 16);
 128 }
 129
 130 /* Returns the rehashed value for 'hash' within 'impl'.  (See also "Hash
 131  * Functions" at the top of this file.) */
 132 static uint32_t
 133 rehash(const struct ccmap_impl *impl, uint32_t hash)
 134 {
 135     return hash_finish(impl->basis, hash);
 136 }
 137
 138 static struct ccmap_impl *
 139 ccmap_get_impl(const struct ccmap *ccmap)
 140 {
 141     return ovsrcu_get(struct ccmap_impl *, &ccmap->impl);
 142 }
 143
 144 static uint32_t
 145 calc_max_n(uint32_t mask)
 146 {
 147     return ((uint64_t) (mask + 1) * CCMAP_K * CCMAP_MAX_LOAD) >> 32;
 148 }
 149
 150 static uint32_t
 151 calc_min_n(uint32_t mask)
 152 {
 153     return ((uint64_t) (mask + 1) * CCMAP_K * CCMAP_MIN_LOAD) >> 32;
 154 }
 155
 156 static struct ccmap_impl *
 157 ccmap_impl_create(uint32_t mask)
 158 {
 159     struct ccmap_impl *impl;
 160
 161     ovs_assert(is_pow2(mask + 1));
 162
 163     impl = xzalloc_cacheline(sizeof *impl
 164                              + (mask + 1) * sizeof *impl->buckets);
 165     impl->n_unique = 0;
 166     impl->n = 0;
 167     impl->max_n = calc_max_n(mask);
 168     impl->min_n = calc_min_n(mask);
 169     impl->mask = mask;
 170     impl->basis = random_uint32();
 171
 172     return impl;
 173 }
 174
 175 /* Initializes 'ccmap' as an empty concurrent hash map. */
 176 void
 177 ccmap_init(struct ccmap *ccmap)
 178 {
 179     ovsrcu_set(&ccmap->impl, ccmap_impl_create(0));
 180 }
 181
 182 /* Destroys 'ccmap'.
 183  *
 184  * The client is responsible for destroying any data previously held in
 185  * 'ccmap'. */
 186 void
 187 ccmap_destroy(struct ccmap *ccmap)
 188 {
 189     if (ccmap) {
 190         ovsrcu_postpone(free_cacheline, ccmap_get_impl(ccmap));
 191     }
 192 }
 193
 194 /* Returns the number of hashes inserted in 'ccmap', including duplicates. */
 195 size_t
 196 ccmap_count(const struct ccmap *ccmap)
 197 {
 198     return ccmap_get_impl(ccmap)->n;
 199 }
 200
 201 /* Returns true if 'ccmap' is empty, false otherwise. */
 202 bool
 203 ccmap_is_empty(const struct ccmap *ccmap)
 204 {
 205     return ccmap_count(ccmap) == 0;
 206 }
 207
 208 /* returns 0 if not found. Map does not contain zero counts. */
 209 static uint32_t
 210 ccmap_find_in_bucket(const struct ccmap_bucket *bucket, uint32_t hash)
 211 {
 212     for (int i = 0; i < CCMAP_K; i++) {
 213         uint64_t node = ccmap_node_get(&bucket->nodes[i]);
 214
 215         if (ccmap_node_hash(node) == hash) {
 216             return ccmap_node_count(node);
 217         }
 218     }
 219     return 0;
 220 }
 221
 222 /* Searches 'ccmap' for a node with the specified 'hash'.  If one is
 223  * found, returns the count associated with it, otherwise zero.
 224  */
 225 uint32_t
 226 ccmap_find(const struct ccmap *ccmap, uint32_t hash)
 227 {
 228     const struct ccmap_impl *impl = ccmap_get_impl(ccmap);
 229     uint32_t h = rehash(impl, hash);
 230     uint32_t count;
 231
 232     count = ccmap_find_in_bucket(&impl->buckets[h & impl->mask], hash);
 233     if (!count) {
 234         h = other_hash(h);
 235         count = ccmap_find_in_bucket(&impl->buckets[h & impl->mask], hash);
 236     }
 237     return count;
 238 }
 239
 240 static int
 241 ccmap_find_slot_protected(struct ccmap_bucket *b, uint32_t hash,
 242                           uint32_t *count)
 243 {
 244     for (int i = 0; i < CCMAP_K; i++) {
 245         uint64_t node = ccmap_node_get_protected(&b->nodes[i]);
 246
 247         *count = ccmap_node_count(node);
 248         if (ccmap_node_hash(node) == hash && *count) {
 249             return i;
 250         }
 251     }
 252     return -1;
 253 }
 254
 255 static int
 256 ccmap_find_empty_slot_protected(struct ccmap_bucket *b)
 257 {
 258     for (int i = 0; i < CCMAP_K; i++) {
 259         uint64_t node = ccmap_node_get_protected(&b->nodes[i]);
 260
 261         if (!ccmap_node_count(node)) {
 262             return i;
 263         }
 264     }
 265     return -1;
 266 }
 267
 268 static void
 269 ccmap_set_bucket(struct ccmap_bucket *b, int i, uint32_t count, uint32_t hash)
 270 {
 271     ccmap_node_set_protected(&b->nodes[i], ccmap_node(count, hash));
 272 }
 273
 274 /* Searches 'b' for a node with the given 'hash'.  If it finds one, increments
 275  * the associated count by 'inc' and returns the new value. Otherwise returns
 276  * 0. */
 277 static uint32_t
 278 ccmap_inc_bucket_existing(struct ccmap_bucket *b, uint32_t hash, uint32_t inc)
 279 {
 280     uint32_t count;
 281
 282     int i = ccmap_find_slot_protected(b, hash, &count);
 283     if (i < 0) {
 284         return 0;
 285     }
 286     count += inc;
 287     ccmap_set_bucket(b, i, count, hash);
 288     return count;
 289 }
 290
 291 /* Searches 'b' for an empty slot.  If successful, stores 'inc' and 'hash' in
 292  * the slot and returns 'inc'.  Otherwise, returns 0. */
 293 static uint32_t
 294 ccmap_inc_bucket_new(struct ccmap_bucket *b, uint32_t hash, uint32_t inc)
 295 {
 296     int i = ccmap_find_empty_slot_protected(b);
 297     if (i < 0) {
 298         return 0;
 299     }
 300     ccmap_set_bucket(b, i, inc, hash);
 301     return inc;
 302 }
 303
 304 /* Returns the other bucket that b->nodes[slot] could occupy in 'impl'.  (This
 305  * might be the same as 'b'.) */
 306 static struct ccmap_bucket *
 307 other_bucket_protected(struct ccmap_impl *impl, struct ccmap_bucket *b, int slot)
 308 {
 309     uint64_t node = ccmap_node_get_protected(&b->nodes[slot]);
 310
 311     uint32_t h1 = rehash(impl, ccmap_node_hash(node));
 312     uint32_t h2 = other_hash(h1);
 313     uint32_t b_idx = b - impl->buckets;
 314     uint32_t other_h = (h1 & impl->mask) == b_idx ? h2 : h1;
 315
 316     return &impl->buckets[other_h & impl->mask];
 317 }
 318
 319 /* Count 'inc' for 'hash' is to be inserted into 'impl', but both candidate
 320  * buckets 'b1' and 'b2' are full.  This function attempts to rearrange buckets
 321  * within 'impl' to make room for 'hash'.
 322  *
 323  * Returns 'inc' if the new count for the 'hash' was inserted, otherwise
 324  * returns 0.
 325  *
 326  * The implementation is a general-purpose breadth-first search.  At first
 327  * glance, this is more complex than a random walk through 'impl' (suggested by
 328  * some references), but random walks have a tendency to loop back through a
 329  * single bucket.  We have to move nodes backward along the path that we find,
 330  * so that no node actually disappears from the hash table, which means a
 331  * random walk would have to be careful to deal with loops.  By contrast, a
 332  * successful breadth-first search always finds a *shortest* path through the
 333  * hash table, and a shortest path will never contain loops, so it avoids that
 334  * problem entirely.
 335  */
 336 static uint32_t
 337 ccmap_inc_bfs(struct ccmap_impl *impl, uint32_t hash,
 338               struct ccmap_bucket *b1, struct ccmap_bucket *b2, uint32_t inc)
 339 {
 340     enum { MAX_DEPTH = 4 };
 341
 342     /* A path from 'start' to 'end' via the 'n' steps in 'slots[]'.
 343      *
 344      * One can follow the path via:
 345      *
 346      *     struct ccmap_bucket *b;
 347      *     int i;
 348      *
 349      *     b = path->start;
 350      *     for (i = 0; i < path->n; i++) {
 351      *         b = other_bucket_protected(impl, b, path->slots[i]);
 352      *     }
 353      *     ovs_assert(b == path->end);
 354      */
 355     struct ccmap_path {
 356         struct ccmap_bucket *start; /* First bucket along the path. */
 357         struct ccmap_bucket *end;   /* Last bucket on the path. */
 358         uint8_t slots[MAX_DEPTH];  /* Slots used for each hop. */
 359         int n;                     /* Number of slots[]. */
 360     };
 361
 362     /* We need to limit the amount of work we do trying to find a path.  It
 363      * might actually be impossible to rearrange the ccmap, and after some time
 364      * it is likely to be easier to rehash the entire ccmap.
 365      *
 366      * This value of MAX_QUEUE is an arbitrary limit suggested by one of the
 367      * references.  Empirically, it seems to work OK. */
 368     enum { MAX_QUEUE = 500 };
 369     struct ccmap_path queue[MAX_QUEUE];
 370     int head = 0;
 371     int tail = 0;
 372
 373     /* Add 'b1' and 'b2' as starting points for the search. */
 374     queue[head].start = b1;
 375     queue[head].end = b1;
 376     queue[head].n = 0;
 377     head++;
 378     if (b1 != b2) {
 379         queue[head].start = b2;
 380         queue[head].end = b2;
 381         queue[head].n = 0;
 382         head++;
 383     }
 384
 385     while (tail < head) {
 386         const struct ccmap_path *path = &queue[tail++];
 387         struct ccmap_bucket *this = path->end;
 388         int i;
 389
 390         for (i = 0; i < CCMAP_K; i++) {
 391             struct ccmap_bucket *next = other_bucket_protected(impl, this, i);
 392             int j;
 393
 394             if (this == next) {
 395                 continue;
 396             }
 397
 398             j = ccmap_find_empty_slot_protected(next);
 399             if (j >= 0) {
 400                 /* We've found a path along which we can rearrange the hash
 401                  * table:  Start at path->start, follow all the slots in
 402                  * path->slots[], then follow slot 'i', then the bucket you
 403                  * arrive at has slot 'j' empty. */
 404                 struct ccmap_bucket *buckets[MAX_DEPTH + 2];
 405                 int slots[MAX_DEPTH + 2];
 406                 int k;
 407
 408                 /* Figure out the full sequence of slots. */
 409                 for (k = 0; k < path->n; k++) {
 410                     slots[k] = path->slots[k];
 411                 }
 412                 slots[path->n] = i;
 413                 slots[path->n + 1] = j;
 414
 415                 /* Figure out the full sequence of buckets. */
 416                 buckets[0] = path->start;
 417                 for (k = 0; k <= path->n; k++) {
 418                     buckets[k + 1] = other_bucket_protected(impl, buckets[k], slots[k]);
 419                 }
 420
 421                 /* Now the path is fully expressed.  One can start from
 422                  * buckets[0], go via slots[0] to buckets[1], via slots[1] to
 423                  * buckets[2], and so on.
 424                  *
 425                  * Move all the nodes across the path "backward".  After each
 426                  * step some node appears in two buckets.  Thus, every node is
 427                  * always visible to a concurrent search. */
 428                 for (k = path->n + 1; k > 0; k--) {
 429                     uint64_t node = ccmap_node_get_protected
 430                         (&buckets[k - 1]->nodes[slots[k - 1]]);
 431                     ccmap_node_set_protected(&buckets[k]->nodes[slots[k]],
 432                                              node);
 433                 }
 434
 435                 /* Finally, insert the count. */
 436                 ccmap_set_bucket(buckets[0], slots[0], inc, hash);
 437
 438                 return inc;
 439             }
 440
 441             if (path->n < MAX_DEPTH && head < MAX_QUEUE) {
 442                 struct ccmap_path *new_path = &queue[head++];
 443
 444                 *new_path = *path;
 445                 new_path->end = next;
 446                 new_path->slots[new_path->n++] = i;
 447             }
 448         }
 449     }
 450
 451     return 0;
 452 }
 453
 454 /* Increments the count associated with 'hash', in 'impl', by 'inc'. */
 455 static uint32_t
 456 ccmap_try_inc(struct ccmap_impl *impl, uint32_t hash, uint32_t inc)
 457 {
 458     uint32_t h1 = rehash(impl, hash);
 459     uint32_t h2 = other_hash(h1);
 460     struct ccmap_bucket *b1 = &impl->buckets[h1 & impl->mask];
 461     struct ccmap_bucket *b2 = &impl->buckets[h2 & impl->mask];
 462     uint32_t count;
 463
 464     return OVS_UNLIKELY(count = ccmap_inc_bucket_existing(b1, hash, inc))
 465         ? count : OVS_UNLIKELY(count = ccmap_inc_bucket_existing(b2, hash, inc))
 466         ? count : OVS_LIKELY(count = ccmap_inc_bucket_new(b1, hash, inc))
 467         ? count : OVS_LIKELY(count = ccmap_inc_bucket_new(b2, hash, inc))
 468         ? count : ccmap_inc_bfs(impl, hash, b1, b2, inc);
 469 }
 470
 471 /* Increments the count of 'hash' values in the 'ccmap'.  The caller must
 472  * ensure that 'ccmap' cannot change concurrently (from another thread).
 473  *
 474  * Returns the current count of the given hash value after the incremention. */
 475 uint32_t
 476 ccmap_inc(struct ccmap *ccmap, uint32_t hash)
 477 {
 478     struct ccmap_impl *impl = ccmap_get_impl(ccmap);
 479     uint32_t count;
 480
 481     if (OVS_UNLIKELY(impl->n_unique >= impl->max_n)) {
 482         COVERAGE_INC(ccmap_expand);
 483         impl = ccmap_rehash(ccmap, (impl->mask << 1) | 1);
 484     }
 485
 486     while (OVS_UNLIKELY(!(count = ccmap_try_inc(impl, hash, 1)))) {
 487         impl = ccmap_rehash(ccmap, impl->mask);
 488     }
 489     ++impl->n;
 490     if (count == 1) {
 491         ++impl->n_unique;
 492     }
 493     return count;
 494 }
 495
 496 /* Decrement the count associated with 'hash' in the bucket identified by
 497  * 'h'. Return the OLD count if successful, or 0. */
 498 static uint32_t
 499 ccmap_dec__(struct ccmap_impl *impl, uint32_t hash, uint32_t h)
 500 {
 501     struct ccmap_bucket *b = &impl->buckets[h & impl->mask];
 502     uint32_t count;
 503
 504     int slot = ccmap_find_slot_protected(b, hash, &count);
 505     if (slot < 0) {
 506         return 0;
 507     }
 508
 509     ccmap_set_bucket(b, slot, count - 1, hash);
 510     return count;
 511 }
 512
 513 /* Decrements the count associated with 'hash'.  The caller must
 514  * ensure that 'ccmap' cannot change concurrently (from another thread).
 515  *
 516  * Returns the current count related to 'hash' in the ccmap after the
 517  * decrement. */
 518 uint32_t
 519 ccmap_dec(struct ccmap *ccmap, uint32_t hash)
 520 {
 521     struct ccmap_impl *impl = ccmap_get_impl(ccmap);
 522     uint32_t h1 = rehash(impl, hash);
 523     uint32_t h2 = other_hash(h1);
 524
 525     uint32_t old_count = ccmap_dec__(impl, hash, h1);
 526     if (!old_count) {
 527         old_count = ccmap_dec__(impl, hash, h2);
 528     }
 529     ovs_assert(old_count);
 530
 531     old_count--;
 532
 533     if (old_count == 0) {
 534         impl->n_unique--;
 535         if (OVS_UNLIKELY(impl->n_unique < impl->min_n)) {
 536             COVERAGE_INC(ccmap_shrink);
 537             impl = ccmap_rehash(ccmap, impl->mask >> 1);
 538         }
 539     }
 540     impl->n--;
 541     return old_count;
 542 }
 543
 544 static bool
 545 ccmap_try_rehash(const struct ccmap_impl *old, struct ccmap_impl *new)
 546 {
 547     const struct ccmap_bucket *b;
 548
 549     for (b = old->buckets; b <= &old->buckets[old->mask]; b++) {
 550         for (int i = 0; i < CCMAP_K; i++) {
 551             uint64_t node = ccmap_node_get_protected(&b->nodes[i]);
 552             uint32_t count = ccmap_node_count(node);
 553
 554             if (count && !ccmap_try_inc(new, ccmap_node_hash(node), count)) {
 555                 return false;
 556             }
 557         }
 558     }
 559     return true;
 560 }
 561
 562 static struct ccmap_impl *
 563 ccmap_rehash(struct ccmap *ccmap, uint32_t mask)
 564 {
 565     struct ccmap_impl *old = ccmap_get_impl(ccmap);
 566     struct ccmap_impl *new = ccmap_impl_create(mask);
 567
 568     ovs_assert(old->n_unique < new->max_n);
 569
 570     while (!ccmap_try_rehash(old, new)) {
 571         memset(new->buckets, 0, (mask + 1) * sizeof *new->buckets);
 572         new->basis = random_uint32();
 573     }
 574
 575     new->n = old->n;
 576     new->n_unique = old->n_unique;
 577     ovsrcu_set(&ccmap->impl, new);
 578     ovsrcu_postpone(free_cacheline, old);
 579
 580     return new;
 581 }