ccmap.c

/*
 * Copyright (c) 2014, 2016 Nicira, Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at:
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include <config.h>
#include "ccmap.h"
#include "coverage.h"
#include "bitmap.h"
#include "hash.h"
#include "ovs-rcu.h"
#include "random.h"
#include "util.h"

COVERAGE_DEFINE(ccmap_expand);
COVERAGE_DEFINE(ccmap_shrink);

/* A count-only version of the cmap. */

/* Allow protected access to the value without atomic semantics.  This makes
 * the exclusive writer somewhat faster. */
typedef union {
    unsigned long long         protected_value;
    ATOMIC(unsigned long long) atomic_value;
} ccmap_node_t;
BUILD_ASSERT_DECL(sizeof(ccmap_node_t) == sizeof(uint64_t));

static uint64_t
ccmap_node_get(const ccmap_node_t *node)
{
    uint64_t value;

    atomic_read_relaxed(&CONST_CAST(ccmap_node_t *, node)->atomic_value,
                        &value);

    return value;
}

/* It is safe to allow compiler optimize reads by the exclusive writer. */
static uint64_t
ccmap_node_get_protected(const ccmap_node_t *node)
{
    return node->protected_value;
}

static void
ccmap_node_set_protected(ccmap_node_t *node, uint64_t value)
{
    atomic_store_relaxed(&node->atomic_value, value);
}

static uint64_t
ccmap_node(uint32_t count, uint32_t hash)
{
    return (uint64_t)count << 32 | hash;
}

static uint32_t
ccmap_node_hash(uint64_t node)
{
    return node;
}

static uint32_t
ccmap_node_count(uint64_t node)
{
    return node >> 32;
}

/* Number of nodes per bucket. */
#define CCMAP_K (CACHE_LINE_SIZE / sizeof(ccmap_node_t))

/* A cuckoo hash bucket.  Designed to be cache-aligned and exactly one cache
 * line long. */
struct ccmap_bucket {
    /* Each node incudes both the hash (low 32-bits) and the count (high
     * 32-bits), allowing readers always getting a consistent pair. */
    ccmap_node_t nodes[CCMAP_K];
};
BUILD_ASSERT_DECL(sizeof(struct ccmap_bucket) == CACHE_LINE_SIZE);

/* Default maximum load factor (as a fraction of UINT32_MAX + 1) before
 * enlarging a ccmap.  Reasonable values lie between about 75% and 93%.  Smaller
 * values waste memory; larger values increase the average insertion time. */
#define CCMAP_MAX_LOAD ((uint32_t) (UINT32_MAX * .85))

/* Default minimum load factor (as a fraction of UINT32_MAX + 1) before
 * shrinking a ccmap.  Currently, the value is chosen to be 20%, this
 * means ccmap will have a 40% load factor after shrink. */
#define CCMAP_MIN_LOAD ((uint32_t) (UINT32_MAX * .20))

/* The implementation of a concurrent hash map. */
struct ccmap_impl {
    PADDED_MEMBERS(CACHE_LINE_SIZE,
        unsigned int n_unique;      /* Number of in-use nodes. */
        unsigned int n;             /* Number of hashes inserted. */
        unsigned int max_n;         /* Max nodes before enlarging. */
        unsigned int min_n;         /* Min nodes before shrinking. */
        uint32_t mask;              /* Number of 'buckets', minus one. */
        uint32_t basis;             /* Basis for rehashing client's
                                       hash values. */
    );
    struct ccmap_bucket buckets[];
};
BUILD_ASSERT_DECL(sizeof(struct ccmap_impl) == CACHE_LINE_SIZE);

static struct ccmap_impl *ccmap_rehash(struct ccmap *, uint32_t mask);

/* Given a rehashed value 'hash', returns the other hash for that rehashed
 * value.  This is symmetric: other_hash(other_hash(x)) == x.  (See also "Hash
 * Functions" at the top of cmap.c.) */
static uint32_t
other_hash(uint32_t hash)
{
    return (hash << 16) | (hash >> 16);
}

/* Returns the rehashed value for 'hash' within 'impl'.  (See also "Hash
 * Functions" at the top of this file.) */
static uint32_t
rehash(const struct ccmap_impl *impl, uint32_t hash)
{
    return hash_finish(impl->basis, hash);
}

static struct ccmap_impl *
ccmap_get_impl(const struct ccmap *ccmap)
{
    return ovsrcu_get(struct ccmap_impl *, &ccmap->impl);
}

static uint32_t
calc_max_n(uint32_t mask)
{
    return ((uint64_t) (mask + 1) * CCMAP_K * CCMAP_MAX_LOAD) >> 32;
}

static uint32_t
calc_min_n(uint32_t mask)
{
    return ((uint64_t) (mask + 1) * CCMAP_K * CCMAP_MIN_LOAD) >> 32;
}

static struct ccmap_impl *
ccmap_impl_create(uint32_t mask)
{
    struct ccmap_impl *impl;

    ovs_assert(is_pow2(mask + 1));

    impl = xzalloc_cacheline(sizeof *impl
                             + (mask + 1) * sizeof *impl->buckets);
    impl->n_unique = 0;
    impl->n = 0;
    impl->max_n = calc_max_n(mask);
    impl->min_n = calc_min_n(mask);
    impl->mask = mask;
    impl->basis = random_uint32();

    return impl;
}

/* Initializes 'ccmap' as an empty concurrent hash map. */
void
ccmap_init(struct ccmap *ccmap)
{
    ovsrcu_set(&ccmap->impl, ccmap_impl_create(0));
}

/* Destroys 'ccmap'.
 *
 * The client is responsible for destroying any data previously held in
 * 'ccmap'. */
void
ccmap_destroy(struct ccmap *ccmap)
{
    if (ccmap) {
        ovsrcu_postpone(free_cacheline, ccmap_get_impl(ccmap));
    }
}

/* Returns the number of hashes inserted in 'ccmap', including duplicates. */
size_t
ccmap_count(const struct ccmap *ccmap)
{
    return ccmap_get_impl(ccmap)->n;
}

/* Returns true if 'ccmap' is empty, false otherwise. */
bool
ccmap_is_empty(const struct ccmap *ccmap)
{
    return ccmap_count(ccmap) == 0;
}

/* returns 0 if not found. Map does not contain zero counts. */
static uint32_t
ccmap_find_in_bucket(const struct ccmap_bucket *bucket, uint32_t hash)
{
    for (int i = 0; i < CCMAP_K; i++) {
        uint64_t node = ccmap_node_get(&bucket->nodes[i]);

        if (ccmap_node_hash(node) == hash) {
            return ccmap_node_count(node);
        }
    }
    return 0;
}

/* Searches 'ccmap' for a node with the specified 'hash'.  If one is
 * found, returns the count associated with it, otherwise zero.
 */
uint32_t
ccmap_find(const struct ccmap *ccmap, uint32_t hash)
{
    const struct ccmap_impl *impl = ccmap_get_impl(ccmap);
    uint32_t h = rehash(impl, hash);
    uint32_t count;

    count = ccmap_find_in_bucket(&impl->buckets[h & impl->mask], hash);
    if (!count) {
        h = other_hash(h);
        count = ccmap_find_in_bucket(&impl->buckets[h & impl->mask], hash);
    }
    return count;
}

static int
ccmap_find_slot_protected(struct ccmap_bucket *b, uint32_t hash,
                          uint32_t *count)
{
    for (int i = 0; i < CCMAP_K; i++) {
        uint64_t node = ccmap_node_get_protected(&b->nodes[i]);

        *count = ccmap_node_count(node);
        if (ccmap_node_hash(node) == hash && *count) {
            return i;
        }
    }
    return -1;
}

static int
ccmap_find_empty_slot_protected(struct ccmap_bucket *b)
{
    for (int i = 0; i < CCMAP_K; i++) {
        uint64_t node = ccmap_node_get_protected(&b->nodes[i]);

        if (!ccmap_node_count(node)) {
            return i;
        }
    }
    return -1;
}

static void
ccmap_set_bucket(struct ccmap_bucket *b, int i, uint32_t count, uint32_t hash)
{
    ccmap_node_set_protected(&b->nodes[i], ccmap_node(count, hash));
}

/* Searches 'b' for a node with the given 'hash'.  If it finds one, increments
 * the associated count by 'inc' and returns the new value. Otherwise returns
 * 0. */
static uint32_t
ccmap_inc_bucket_existing(struct ccmap_bucket *b, uint32_t hash, uint32_t inc)
{
    uint32_t count;

    int i = ccmap_find_slot_protected(b, hash, &count);
    if (i < 0) {
        return 0;
    }
    count += inc;
    ccmap_set_bucket(b, i, count, hash);
    return count;
}

/* Searches 'b' for an empty slot.  If successful, stores 'inc' and 'hash' in
 * the slot and returns 'inc'.  Otherwise, returns 0. */
static uint32_t
ccmap_inc_bucket_new(struct ccmap_bucket *b, uint32_t hash, uint32_t inc)
{
    int i = ccmap_find_empty_slot_protected(b);
    if (i < 0) {
        return 0;
    }
    ccmap_set_bucket(b, i, inc, hash);
    return inc;
}

/* Returns the other bucket that b->nodes[slot] could occupy in 'impl'.  (This
 * might be the same as 'b'.) */
static struct ccmap_bucket *
other_bucket_protected(struct ccmap_impl *impl, struct ccmap_bucket *b, int slot)
{
    uint64_t node = ccmap_node_get_protected(&b->nodes[slot]);

    uint32_t h1 = rehash(impl, ccmap_node_hash(node));
    uint32_t h2 = other_hash(h1);
    uint32_t b_idx = b - impl->buckets;
    uint32_t other_h = (h1 & impl->mask) == b_idx ? h2 : h1;

    return &impl->buckets[other_h & impl->mask];
}

/* Count 'inc' for 'hash' is to be inserted into 'impl', but both candidate
 * buckets 'b1' and 'b2' are full.  This function attempts to rearrange buckets
 * within 'impl' to make room for 'hash'.
 *
 * Returns 'inc' if the new count for the 'hash' was inserted, otherwise
 * returns 0.
 *
 * The implementation is a general-purpose breadth-first search.  At first
 * glance, this is more complex than a random walk through 'impl' (suggested by
 * some references), but random walks have a tendency to loop back through a
 * single bucket.  We have to move nodes backward along the path that we find,
 * so that no node actually disappears from the hash table, which means a
 * random walk would have to be careful to deal with loops.  By contrast, a
 * successful breadth-first search always finds a *shortest* path through the
 * hash table, and a shortest path will never contain loops, so it avoids that
 * problem entirely.
 */
static uint32_t
ccmap_inc_bfs(struct ccmap_impl *impl, uint32_t hash,
              struct ccmap_bucket *b1, struct ccmap_bucket *b2, uint32_t inc)
{
    enum { MAX_DEPTH = 4 };

    /* A path from 'start' to 'end' via the 'n' steps in 'slots[]'.
     *
     * One can follow the path via:
     *
     *     struct ccmap_bucket *b;
     *     int i;
     *
     *     b = path->start;
     *     for (i = 0; i < path->n; i++) {
     *         b = other_bucket_protected(impl, b, path->slots[i]);
     *     }
     *     ovs_assert(b == path->end);
     */
    struct ccmap_path {
        struct ccmap_bucket *start; /* First bucket along the path. */
        struct ccmap_bucket *end;   /* Last bucket on the path. */
        uint8_t slots[MAX_DEPTH];  /* Slots used for each hop. */
        int n;                     /* Number of slots[]. */
    };

    /* We need to limit the amount of work we do trying to find a path.  It
     * might actually be impossible to rearrange the ccmap, and after some time
     * it is likely to be easier to rehash the entire ccmap.
     *
     * This value of MAX_QUEUE is an arbitrary limit suggested by one of the
     * references.  Empirically, it seems to work OK. */
    enum { MAX_QUEUE = 500 };
    struct ccmap_path queue[MAX_QUEUE];
    int head = 0;
    int tail = 0;

    /* Add 'b1' and 'b2' as starting points for the search. */
    queue[head].start = b1;
    queue[head].end = b1;
    queue[head].n = 0;
    head++;
    if (b1 != b2) {
        queue[head].start = b2;
        queue[head].end = b2;
        queue[head].n = 0;
        head++;
    }

    while (tail < head) {
        const struct ccmap_path *path = &queue[tail++];
        struct ccmap_bucket *this = path->end;
        int i;

        for (i = 0; i < CCMAP_K; i++) {
            struct ccmap_bucket *next = other_bucket_protected(impl, this, i);
            int j;

            if (this == next) {
                continue;
            }

            j = ccmap_find_empty_slot_protected(next);
            if (j >= 0) {
                /* We've found a path along which we can rearrange the hash
                 * table:  Start at path->start, follow all the slots in
                 * path->slots[], then follow slot 'i', then the bucket you
                 * arrive at has slot 'j' empty. */
                struct ccmap_bucket *buckets[MAX_DEPTH + 2];
                int slots[MAX_DEPTH + 2];
                int k;

                /* Figure out the full sequence of slots. */
                for (k = 0; k < path->n; k++) {
                    slots[k] = path->slots[k];
                }
                slots[path->n] = i;
                slots[path->n + 1] = j;

                /* Figure out the full sequence of buckets. */
                buckets[0] = path->start;
                for (k = 0; k <= path->n; k++) {
                    buckets[k + 1] = other_bucket_protected(impl, buckets[k], slots[k]);
                }

                /* Now the path is fully expressed.  One can start from
                 * buckets[0], go via slots[0] to buckets[1], via slots[1] to
                 * buckets[2], and so on.
                 *
                 * Move all the nodes across the path "backward".  After each
                 * step some node appears in two buckets.  Thus, every node is
                 * always visible to a concurrent search. */
                for (k = path->n + 1; k > 0; k--) {
                    uint64_t node = ccmap_node_get_protected
                        (&buckets[k - 1]->nodes[slots[k - 1]]);
                    ccmap_node_set_protected(&buckets[k]->nodes[slots[k]],
                                             node);
                }

                /* Finally, insert the count. */
                ccmap_set_bucket(buckets[0], slots[0], inc, hash);

                return inc;
            }

            if (path->n < MAX_DEPTH && head < MAX_QUEUE) {
                struct ccmap_path *new_path = &queue[head++];

                *new_path = *path;
                new_path->end = next;
                new_path->slots[new_path->n++] = i;
            }
        }
    }

    return 0;
}

/* Increments the count associated with 'hash', in 'impl', by 'inc'. */
static uint32_t
ccmap_try_inc(struct ccmap_impl *impl, uint32_t hash, uint32_t inc)
{
    uint32_t h1 = rehash(impl, hash);
    uint32_t h2 = other_hash(h1);
    struct ccmap_bucket *b1 = &impl->buckets[h1 & impl->mask];
    struct ccmap_bucket *b2 = &impl->buckets[h2 & impl->mask];
    uint32_t count;

    return OVS_UNLIKELY(count = ccmap_inc_bucket_existing(b1, hash, inc))
        ? count : OVS_UNLIKELY(count = ccmap_inc_bucket_existing(b2, hash, inc))
        ? count : OVS_LIKELY(count = ccmap_inc_bucket_new(b1, hash, inc))
        ? count : OVS_LIKELY(count = ccmap_inc_bucket_new(b2, hash, inc))
        ? count : ccmap_inc_bfs(impl, hash, b1, b2, inc);
}

/* Increments the count of 'hash' values in the 'ccmap'.  The caller must
 * ensure that 'ccmap' cannot change concurrently (from another thread).
 *
 * Returns the current count of the given hash value after the incremention. */
uint32_t
ccmap_inc(struct ccmap *ccmap, uint32_t hash)
{
    struct ccmap_impl *impl = ccmap_get_impl(ccmap);
    uint32_t count;

    if (OVS_UNLIKELY(impl->n_unique >= impl->max_n)) {
        COVERAGE_INC(ccmap_expand);
        impl = ccmap_rehash(ccmap, (impl->mask << 1) | 1);
    }

    while (OVS_UNLIKELY(!(count = ccmap_try_inc(impl, hash, 1)))) {
        impl = ccmap_rehash(ccmap, impl->mask);
    }
    ++impl->n;
    if (count == 1) {
        ++impl->n_unique;
    }
    return count;
}

/* Decrement the count associated with 'hash' in the bucket identified by
 * 'h'. Return the OLD count if successful, or 0. */
static uint32_t
ccmap_dec__(struct ccmap_impl *impl, uint32_t hash, uint32_t h)
{
    struct ccmap_bucket *b = &impl->buckets[h & impl->mask];
    uint32_t count;

    int slot = ccmap_find_slot_protected(b, hash, &count);
    if (slot < 0) {
        return 0;
    }

    ccmap_set_bucket(b, slot, count - 1, hash);
    return count;
}

/* Decrements the count associated with 'hash'.  The caller must
 * ensure that 'ccmap' cannot change concurrently (from another thread).
 *
 * Returns the current count related to 'hash' in the ccmap after the
 * decrement. */
uint32_t
ccmap_dec(struct ccmap *ccmap, uint32_t hash)
{
    struct ccmap_impl *impl = ccmap_get_impl(ccmap);
    uint32_t h1 = rehash(impl, hash);
    uint32_t h2 = other_hash(h1);

    uint32_t old_count = ccmap_dec__(impl, hash, h1);
    if (!old_count) {
        old_count = ccmap_dec__(impl, hash, h2);
    }
    ovs_assert(old_count);

    old_count--;

    if (old_count == 0) {
        impl->n_unique--;
        if (OVS_UNLIKELY(impl->n_unique < impl->min_n)) {
            COVERAGE_INC(ccmap_shrink);
            impl = ccmap_rehash(ccmap, impl->mask >> 1);
        }
    }
    impl->n--;
    return old_count;
}

static bool
ccmap_try_rehash(const struct ccmap_impl *old, struct ccmap_impl *new)
{
    const struct ccmap_bucket *b;

    for (b = old->buckets; b <= &old->buckets[old->mask]; b++) {
        for (int i = 0; i < CCMAP_K; i++) {
            uint64_t node = ccmap_node_get_protected(&b->nodes[i]);
            uint32_t count = ccmap_node_count(node);

            if (count && !ccmap_try_inc(new, ccmap_node_hash(node), count)) {
                return false;
            }
        }
    }
    return true;
}

static struct ccmap_impl *
ccmap_rehash(struct ccmap *ccmap, uint32_t mask)
{
    struct ccmap_impl *old = ccmap_get_impl(ccmap);
    struct ccmap_impl *new = ccmap_impl_create(mask);

    ovs_assert(old->n_unique < new->max_n);

    while (!ccmap_try_rehash(old, new)) {
        memset(new->buckets, 0, (mask + 1) * sizeof *new->buckets);
        new->basis = random_uint32();
    }

    new->n = old->n;
    new->n_unique = old->n_unique;
    ovsrcu_set(&ccmap->impl, new);
    ovsrcu_postpone(free_cacheline, old);

    return new;
}