lbhash.h

Go to the documentation of this file.

/*
 * Copyright (c) 2012 Cisco and/or its affiliates.
 * 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.
 */

/**
 * vppinfra already includes tons of different hash tables.
 * MagLev flow table is a bit different. It has to be very efficient
 * for both writing and reading operations. But it does not need to
 * be 100% reliable (write can fail). It also needs to recycle
 * old entries in a lazy way.
 *
 * This hash table is the most dummy hash table you can do.
 * Fixed total size, fixed bucket size.
 * Advantage is that it could be very efficient (maybe).
 *
 */

#ifndef LB_PLUGIN_LB_LBHASH_H_
#define LB_PLUGIN_LB_LBHASH_H_

#include <vnet/vnet.h>

#define LBHASH_ENTRY_PER_BUCKET_LOG2 2
#define LBHASH_ENTRY_PER_BUCKET (1 << LBHASH_ENTRY_PER_BUCKET_LOG2)
#define LBHASH_ENTRY_PER_BUCKET_MASK (LBHASH_ENTRY_PER_BUCKET - 1)

typedef struct {
  u64 key[5];
  u32 value;
  u32 last_seen;
} lb_hash_entry_t;

typedef struct {
  u32 buckets_mask;
  u32 timeout;
  lb_hash_entry_t entries[];
} lb_hash_t;

#define lb_hash_nbuckets(h) (((h)->buckets_mask >> LBHASH_ENTRY_PER_BUCKET_LOG2) + 1)
#define lb_hash_size(h) ((h)->buckets_mask + LBHASH_ENTRY_PER_BUCKET)

#define lb_hash_foreach_entry(h, e) \
  for (e = (h)->entries; e < h->entries + lb_hash_size(h); e++)

#define lb_hash_foreach_valid_entry(h, e, now) \
    lb_hash_foreach_entry(h, e) \
       if (!clib_u32_loop_gt((now), (e)->last_seen + (h)->timeout))

static_always_inline
lb_hash_t *lb_hash_alloc(u32 buckets, u32 timeout)
{
  if ((!is_pow2(buckets)) ||
      ((buckets << LBHASH_ENTRY_PER_BUCKET_LOG2) == 0))
    return NULL;

  // Allocate 1 more bucket for prefetch
  u32 size = sizeof(lb_hash_t) + ((buckets << LBHASH_ENTRY_PER_BUCKET_LOG2) + 1)* sizeof(lb_hash_entry_t);
  u8 *mem = 0;
  lb_hash_t *h;
  vec_alloc_aligned(mem, size, CLIB_CACHE_LINE_BYTES);
  h = (lb_hash_t *)mem;
  h->buckets_mask = (buckets - 1) << LBHASH_ENTRY_PER_BUCKET_LOG2;
  h->timeout = timeout;
  return h;
}

static_always_inline
void lb_hash_free(lb_hash_t *h)
{
  vec_free(h);
}

#if __SSE4_2__
static_always_inline
u32 lb_hash_crc_u32(u32 data, u32 value)
{
  __asm__ volatile( "crc32l %[data], %[value];"
                    : [value] "+r" (value)
                    : [data] "rm" (data));
  return value;
}

static_always_inline
u32 lb_hash_hash(u64 k[5])
{
  u32 * dp = (u32 *) k;
  u32 value = 0;

  value = lb_hash_crc_u32 (dp[0], value);
  value = lb_hash_crc_u32 (dp[1], value);
  value = lb_hash_crc_u32 (dp[2], value);
  value = lb_hash_crc_u32 (dp[3], value);
  value = lb_hash_crc_u32 (dp[4], value);
  value = lb_hash_crc_u32 (dp[5], value);
  value = lb_hash_crc_u32 (dp[6], value);
  value = lb_hash_crc_u32 (dp[7], value);
  value = lb_hash_crc_u32 (dp[8], value);
  value = lb_hash_crc_u32 (dp[9], value);
  return value;
}
#else
static_always_inline
u32 lb_hash_hash(u64 k[5])
{
  u64 tmp = k[0] ^ k[1] ^ k[2] ^ k[3] ^ k[4];
  return (u32)clib_xxhash (tmp);
}
#endif



static_always_inline
void lb_hash_get(lb_hash_t *h, u64 k[5], u32 hash, u32 time_now, u32 *available_index, u32 *value)
{
  lb_hash_entry_t *e = &h->entries[hash & h->buckets_mask];
  u32 i;
  *value = ~0;
  *available_index = ~0;
  CLIB_PREFETCH (&(e[1]), sizeof(lb_hash_entry_t), STORE);
  for (i=0; i<LBHASH_ENTRY_PER_BUCKET; i++) {
    CLIB_PREFETCH (&(e[i+2]), sizeof(lb_hash_entry_t), STORE); //+2 somehow performs best
    u64 cmp =
        (e[i].key[0] ^ k[0]) |
        (e[i].key[1] ^ k[1]) |
        (e[i].key[2] ^ k[2]) |
        (e[i].key[3] ^ k[3]) |
        (e[i].key[4] ^ k[4]);

    u8 timeouted = clib_u32_loop_gt(time_now, e[i].last_seen + h->timeout);

    *value = (cmp || timeouted)?*value:e[i].value;
    e[i].last_seen = (cmp || timeouted)?e[i].last_seen:time_now;
    *available_index = (timeouted && (*available_index == ~0))?(&e[i] - h->entries):*available_index;

    if (!cmp)
      return;
  }
}

static_always_inline
u32 lb_hash_available_value(lb_hash_t *h, u32 available_index)
{
  return h->entries[available_index].value;
}

static_always_inline
u32 lb_hash_put(lb_hash_t *h, u64 k[5], u32 value, u32 available_index, u32 time_now)
{
  lb_hash_entry_t *e = &h->entries[available_index];
  e->key[0] = k[0];
  e->key[1] = k[1];
  e->key[2] = k[2];
  e->key[3] = k[3];
  e->key[4] = k[4];
  e->value = value;
  e->last_seen = time_now;
  return 0;
}

static_always_inline
u32 lb_hash_elts(lb_hash_t *h, u32 time_now)
{
  u32 tot = 0;
  lb_hash_entry_t *e;
  lb_hash_foreach_valid_entry(h, e, time_now) {
    tot++;
  }
  return tot;
}

#endif /* LB_PLUGIN_LB_LBHASH_H_ */