src/plugins/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 #include <vppinfra/lb_hash_hash.h>
  34
  35 #if defined (__SSE4_2__)
  36 #include <immintrin.h>
  37 #endif
  38
  39 /*
  40  * @brief Number of entries per bucket.
  41  */
  42 #define LBHASH_ENTRY_PER_BUCKET 4
  43
  44 #define LB_HASH_DO_NOT_USE_SSE_BUCKETS 0
  45
  46 /*
  47  * @brief One bucket contains 4 entries.
  48  * Each bucket takes one 64B cache line in memory.
  49  */
  50 typedef struct {
  51   CLIB_CACHE_LINE_ALIGN_MARK (cacheline0);
  52   u32 hash[LBHASH_ENTRY_PER_BUCKET];
  53   u32 timeout[LBHASH_ENTRY_PER_BUCKET];
  54   u32 vip[LBHASH_ENTRY_PER_BUCKET];
  55   u32 value[LBHASH_ENTRY_PER_BUCKET];
  56 } lb_hash_bucket_t;
  57
  58 typedef struct {
  59   u32 buckets_mask;
  60   u32 timeout;
  61   lb_hash_bucket_t buckets[];
  62 } lb_hash_t;
  63
  64 #define lb_hash_nbuckets(h) (((h)->buckets_mask) + 1)
  65 #define lb_hash_size(h) ((h)->buckets_mask + LBHASH_ENTRY_PER_BUCKET)
  66
  67 #define lb_hash_foreach_bucket(h, bucket) \
  68   for (bucket = (h)->buckets; \
  69         bucket < (h)->buckets + lb_hash_nbuckets(h); \
  70         bucket++)
  71
  72 #define lb_hash_foreach_entry(h, bucket, i) \
  73     lb_hash_foreach_bucket(h, bucket) \
  74       for (i = 0; i < LBHASH_ENTRY_PER_BUCKET; i++)
  75
  76 #define lb_hash_foreach_valid_entry(h, bucket, i, now) \
  77     lb_hash_foreach_entry(h, bucket, i) \
  78        if (!clib_u32_loop_gt((now), bucket->timeout[i]))
  79
  80 static_always_inline
  81 lb_hash_t *lb_hash_alloc(u32 buckets, u32 timeout)
  82 {
  83   if (!is_pow2(buckets))
  84     return NULL;
  85
  86   // Allocate 1 more bucket for prefetch
  87   u32 size = ((uword)&((lb_hash_t *)(0))->buckets[0]) +
  88       sizeof(lb_hash_bucket_t) * (buckets + 1);
  89   u8 *mem = 0;
  90   lb_hash_t *h;
  91   vec_alloc_aligned(mem, size, CLIB_CACHE_LINE_BYTES);
  92   clib_memset(mem, 0, size);
  93   h = (lb_hash_t *)mem;
  94   h->buckets_mask = (buckets - 1);
  95   h->timeout = timeout;
  96   return h;
  97 }
  98
  99 static_always_inline
 100 void lb_hash_free(lb_hash_t *h)
 101 {
 102   u8 *mem = (u8 *)h;
 103   vec_free(mem);
 104 }
 105
 106 static_always_inline
 107 void lb_hash_prefetch_bucket(lb_hash_t *ht, u32 hash)
 108 {
 109   lb_hash_bucket_t *bucket = &ht->buckets[hash & ht->buckets_mask];
 110   CLIB_PREFETCH(bucket, sizeof(*bucket), READ);
 111 }
 112
 113 static_always_inline
 114 void lb_hash_get(lb_hash_t *ht, u32 hash, u32 vip, u32 time_now,
 115                  u32 *available_index, u32 *found_value)
 116 {
 117   lb_hash_bucket_t *bucket = &ht->buckets[hash & ht->buckets_mask];
 118   *found_value = 0;
 119   *available_index = ~0;
 120 #if __SSE4_2__ && LB_HASH_DO_NOT_USE_SSE_BUCKETS == 0
 121   u32 bitmask, found_index;
 122   __m128i mask;
 123
 124   // mask[*] = timeout[*] > now
 125   mask = _mm_cmpgt_epi32(_mm_loadu_si128 ((__m128i *) bucket->timeout),
 126                          _mm_set1_epi32 (time_now));
 127   // bitmask[*] = now <= timeout[*/4]
 128   bitmask = (~_mm_movemask_epi8(mask)) & 0xffff;
 129   // Get first index with now <= timeout[*], if any.
 130   *available_index = (bitmask)?__builtin_ctz(bitmask)/4:*available_index;
 131
 132   // mask[*] = (timeout[*] > now) && (hash[*] == hash)
 133   mask = _mm_and_si128(mask,
 134                        _mm_cmpeq_epi32(
 135                            _mm_loadu_si128 ((__m128i *) bucket->hash),
 136                            _mm_set1_epi32 (hash)));
 137
 138   // Load the array of vip values
 139   // mask[*] = (timeout[*] > now) && (hash[*] == hash) && (vip[*] == vip)
 140   mask = _mm_and_si128(mask,
 141                        _mm_cmpeq_epi32(
 142                            _mm_loadu_si128 ((__m128i *) bucket->vip),
 143                            _mm_set1_epi32 (vip)));
 144
 145   // mask[*] = (timeout[*x4] > now) && (hash[*x4] == hash) && (vip[*x4] == vip)
 146   bitmask = _mm_movemask_epi8(mask);
 147   // Get first index, if any
 148   found_index = (bitmask)?__builtin_ctzll(bitmask)/4:0;
 149   ASSERT(found_index < 4);
 150   *found_value = (bitmask)?bucket->value[found_index]:*found_value;
 151   bucket->timeout[found_index] =
 152       (bitmask)?time_now + ht->timeout:bucket->timeout[found_index];
 153 #else
 154   u32 i;
 155   for (i = 0; i < LBHASH_ENTRY_PER_BUCKET; i++) {
 156       u8 cmp = (bucket->hash[i] == hash && bucket->vip[i] == vip);
 157       u8 timeouted = clib_u32_loop_gt(time_now, bucket->timeout[i]);
 158       *found_value = (cmp || timeouted)?*found_value:bucket->value[i];
 159       bucket->timeout[i] = (cmp || timeouted)?time_now + ht->timeout:bucket->timeout[i];
 160       *available_index = (timeouted && (*available_index == ~0))?i:*available_index;
 161
 162       if (!cmp)
 163         return;
 164   }
 165 #endif
 166 }
 167
 168 static_always_inline
 169 u32 lb_hash_available_value(lb_hash_t *h, u32 hash, u32 available_index)
 170 {
 171   return h->buckets[hash & h->buckets_mask].value[available_index];
 172 }
 173
 174 static_always_inline
 175 void lb_hash_put(lb_hash_t *h, u32 hash, u32 value, u32 vip,
 176                  u32 available_index, u32 time_now)
 177 {
 178   lb_hash_bucket_t *bucket = &h->buckets[hash & h->buckets_mask];
 179   bucket->hash[available_index] = hash;
 180   bucket->value[available_index] = value;
 181   bucket->timeout[available_index] = time_now + h->timeout;
 182   bucket->vip[available_index] = vip;
 183 }
 184
 185 static_always_inline
 186 u32 lb_hash_elts(lb_hash_t *h, u32 time_now)
 187 {
 188   u32 tot = 0;
 189   lb_hash_bucket_t *bucket;
 190   u32 i;
 191   lb_hash_foreach_valid_entry(h, bucket, i, time_now) {
 192     tot++;
 193   }
 194   return tot;
 195 }
 196
 197 #endif /* LB_PLUGIN_LB_LBHASH_H_ */