plugins/lb-plugin/lb/lbhash.h

   1 /*
   2  * Copyright (c) 2012 Cisco and/or its affiliates.
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15
  16 /**
  17  * vppinfra already includes tons of different hash tables.
  18  * MagLev flow table is a bit different. It has to be very efficient
  19  * for both writing and reading operations. But it does not need to
  20  * be 100% reliable (write can fail). It also needs to recycle
  21  * old entries in a lazy way.
  22  *
  23  * This hash table is the most dummy hash table you can do.
  24  * Fixed total size, fixed bucket size.
  25  * Advantage is that it could be very efficient (maybe).
  26  *
  27  */
  28
  29 #ifndef LB_PLUGIN_LB_LBHASH_H_
  30 #define LB_PLUGIN_LB_LBHASH_H_
  31
  32 #include <vnet/vnet.h>
  33
  34 #define LBHASH_ENTRY_PER_BUCKET_LOG2 2
  35 #define LBHASH_ENTRY_PER_BUCKET (1 << LBHASH_ENTRY_PER_BUCKET_LOG2)
  36 #define LBHASH_ENTRY_PER_BUCKET_MASK (LBHASH_ENTRY_PER_BUCKET - 1)
  37
  38 typedef struct {
  39   u64 key[5];
  40   u32 value;
  41   u32 last_seen;
  42 } lb_hash_entry_t;
  43
  44 typedef struct {
  45   u32 buckets_mask;
  46   u32 timeout;
  47   lb_hash_entry_t entries[];
  48 } lb_hash_t;
  49
  50 #define lb_hash_nbuckets(h) (((h)->buckets_mask >> LBHASH_ENTRY_PER_BUCKET_LOG2) + 1)
  51 #define lb_hash_size(h) ((h)->buckets_mask + LBHASH_ENTRY_PER_BUCKET)
  52
  53 #define lb_hash_foreach_entry(h, e) \
  54   for (e = (h)->entries; e < h->entries + lb_hash_size(h); e++)
  55
  56 #define lb_hash_foreach_valid_entry(h, e, now) \
  57     lb_hash_foreach_entry(h, e) \
  58        if (!clib_u32_loop_gt((now), (e)->last_seen + (h)->timeout))
  59
  60 static_always_inline
  61 lb_hash_t *lb_hash_alloc(u32 buckets, u32 timeout)
  62 {
  63   if ((!is_pow2(buckets)) ||
  64       ((buckets << LBHASH_ENTRY_PER_BUCKET_LOG2) == 0))
  65     return NULL;
  66
  67   // Allocate 1 more bucket for prefetch
  68   u32 size = sizeof(lb_hash_t) + ((buckets << LBHASH_ENTRY_PER_BUCKET_LOG2) + 1)* sizeof(lb_hash_entry_t);
  69   u8 *mem = 0;
  70   lb_hash_t *h;
  71   vec_alloc_aligned(mem, size, CLIB_CACHE_LINE_BYTES);
  72   h = (lb_hash_t *)mem;
  73   h->buckets_mask = (buckets - 1) << LBHASH_ENTRY_PER_BUCKET_LOG2;
  74   h->timeout = timeout;
  75   return h;
  76 }
  77
  78 static_always_inline
  79 void lb_hash_free(lb_hash_t *h)
  80 {
  81   vec_free(h);
  82 }
  83
  84 #if __SSE4_2__
  85 static_always_inline
  86 u32 lb_hash_crc_u32(u32 data, u32 value)
  87 {
  88   __asm__ volatile( "crc32l %[data], %[value];"
  89                     : [value] "+r" (value)
  90                     : [data] "rm" (data));
  91   return value;
  92 }
  93
  94 static_always_inline
  95 u32 lb_hash_hash(u64 k[5])
  96 {
  97   u32 * dp = (u32 *) k;
  98   u32 value = 0;
  99
 100   value = lb_hash_crc_u32 (dp[0], value);
 101   value = lb_hash_crc_u32 (dp[1], value);
 102   value = lb_hash_crc_u32 (dp[2], value);
 103   value = lb_hash_crc_u32 (dp[3], value);
 104   value = lb_hash_crc_u32 (dp[4], value);
 105   value = lb_hash_crc_u32 (dp[5], value);
 106   value = lb_hash_crc_u32 (dp[6], value);
 107   value = lb_hash_crc_u32 (dp[7], value);
 108   value = lb_hash_crc_u32 (dp[8], value);
 109   value = lb_hash_crc_u32 (dp[9], value);
 110   return value;
 111 }
 112 #else
 113 static_always_inline
 114 u32 lb_hash_hash(u64 k[5])
 115 {
 116   u64 tmp = k[0] ^ k[1] ^ k[2] ^ k[3] ^ k[4];
 117   return (u32)clib_xxhash (tmp);
 118 }
 119 #endif
 120
 121
 122
 123 static_always_inline
 124 void lb_hash_get(lb_hash_t *h, u64 k[5], u32 hash, u32 time_now, u32 *available_index, u32 *value)
 125 {
 126   lb_hash_entry_t *e = &h->entries[hash & h->buckets_mask];
 127   u32 i;
 128   *value = ~0;
 129   *available_index = ~0;
 130   CLIB_PREFETCH (&(e[1]), sizeof(lb_hash_entry_t), STORE);
 131   for (i=0; i<LBHASH_ENTRY_PER_BUCKET; i++) {
 132     CLIB_PREFETCH (&(e[i+2]), sizeof(lb_hash_entry_t), STORE); //+2 somehow performs best
 133     u64 cmp =
 134         (e[i].key[0] ^ k[0]) |
 135         (e[i].key[1] ^ k[1]) |
 136         (e[i].key[2] ^ k[2]) |
 137         (e[i].key[3] ^ k[3]) |
 138         (e[i].key[4] ^ k[4]);
 139
 140     u8 timeouted = clib_u32_loop_gt(time_now, e[i].last_seen + h->timeout);
 141
 142     *value = (cmp || timeouted)?*value:e[i].value;
 143     e[i].last_seen = (cmp || timeouted)?e[i].last_seen:time_now;
 144     *available_index = (timeouted && (*available_index == ~0))?(&e[i] - h->entries):*available_index;
 145
 146     if (!cmp)
 147       return;
 148   }
 149 }
 150
 151 static_always_inline
 152 u32 lb_hash_available_value(lb_hash_t *h, u32 available_index)
 153 {
 154   return h->entries[available_index].value;
 155 }
 156
 157 static_always_inline
 158 u32 lb_hash_put(lb_hash_t *h, u64 k[5], u32 value, u32 available_index, u32 time_now)
 159 {
 160   lb_hash_entry_t *e = &h->entries[available_index];
 161   e->key[0] = k[0];
 162   e->key[1] = k[1];
 163   e->key[2] = k[2];
 164   e->key[3] = k[3];
 165   e->key[4] = k[4];
 166   e->value = value;
 167   e->last_seen = time_now;
 168   return 0;
 169 }
 170
 171 static_always_inline
 172 u32 lb_hash_elts(lb_hash_t *h, u32 time_now)
 173 {
 174   u32 tot = 0;
 175   lb_hash_entry_t *e;
 176   lb_hash_foreach_valid_entry(h, e, time_now) {
 177     tot++;
 178   }
 179   return tot;
 180 }
 181
 182 #endif /* LB_PLUGIN_LB_LBHASH_H_ */