src/plugins/kubeproxy/kphash.h

   1 /*
   2  * Copyright (c) 2017 Intel 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 KP_PLUGIN_KP_KPHASH_H_
  30 #define KP_PLUGIN_KP_KPHASH_H_
  31
  32 #include <vnet/vnet.h>
  33 #include <vppinfra/xxhash.h>
  34 #include <vppinfra/crc32.h>
  35
  36 /*
  37  * @brief Number of entries per bucket.
  38  */
  39 #define KPHASH_ENTRY_PER_BUCKET 4
  40
  41 #define KP_HASH_DO_NOT_USE_SSE_BUCKETS 0
  42
  43 /**
  44  * 32 bits integer comparison for running values.
  45  * 1 > 0 is true. But 1 > 0xffffffff also is.
  46  */
  47 #define clib_u32_loop_gt(a, b) (((u32)(a)) - ((u32)(b)) < 0x7fffffff)
  48
  49 /*
  50  * @brief One bucket contains 4 entries.
  51  * Each bucket takes one 64B cache line in memory.
  52  */
  53 typedef struct {
  54   CLIB_CACHE_LINE_ALIGN_MARK (cacheline0);
  55   u32 hash[KPHASH_ENTRY_PER_BUCKET];
  56   u32 timeout[KPHASH_ENTRY_PER_BUCKET];
  57   u32 vip[KPHASH_ENTRY_PER_BUCKET];
  58   u32 value[KPHASH_ENTRY_PER_BUCKET];
  59 } kp_hash_bucket_t;
  60
  61 typedef struct {
  62   u32 buckets_mask;
  63   u32 timeout;
  64   kp_hash_bucket_t buckets[];
  65 } kp_hash_t;
  66
  67 #define kp_hash_nbuckets(h) (((h)->buckets_mask) + 1)
  68 #define kp_hash_size(h) ((h)->buckets_mask + KPHASH_ENTRY_PER_BUCKET)
  69
  70 #define kp_hash_foreach_bucket(h, bucket) \
  71   for (bucket = (h)->buckets; \
  72         bucket < (h)->buckets + kp_hash_nbuckets(h); \
  73         bucket++)
  74
  75 #define kp_hash_foreach_entry(h, bucket, i) \
  76     kp_hash_foreach_bucket(h, bucket) \
  77       for (i = 0; i < KPHASH_ENTRY_PER_BUCKET; i++)
  78
  79 #define kp_hash_foreach_valid_entry(h, bucket, i, now) \
  80     kp_hash_foreach_entry(h, bucket, i) \
  81        if (!clib_u32_loop_gt((now), bucket->timeout[i]))
  82
  83 static_always_inline
  84 kp_hash_t *kp_hash_alloc(u32 buckets, u32 timeout)
  85 {
  86   if (!is_pow2(buckets))
  87     return NULL;
  88
  89   // Allocate 1 more bucket for prefetch
  90   u32 size = ((u64)&((kp_hash_t *)(0))->buckets[0]) +
  91       sizeof(kp_hash_bucket_t) * (buckets + 1);
  92   u8 *mem = 0;
  93   kp_hash_t *h;
  94   vec_alloc_aligned(mem, size, CLIB_CACHE_LINE_BYTES);
  95   h = (kp_hash_t *)mem;
  96   h->buckets_mask = (buckets - 1);
  97   h->timeout = timeout;
  98   return h;
  99 }
 100
 101 static_always_inline
 102 void kp_hash_free(kp_hash_t *h)
 103 {
 104   u8 *mem = (u8 *)h;
 105   vec_free(mem);
 106 }
 107
 108 static_always_inline
 109 u32 kp_hash_hash(u64 k0, u64 k1, u64 k2, u64 k3, u64 k4)
 110 {
 111 #ifdef clib_crc32c_uses_intrinsics
 112   u64 key[5];
 113   key[0] = k0;
 114   key[1] = k1;
 115   key[2] = k2;
 116   key[3] = k3;
 117   key[4] = k4;
 118   return clib_crc32c ((u8 *) key, 40);
 119 #else
 120   u64 tmp = k0 ^ k1 ^ k2 ^ k3 ^ k4;
 121   return (u32)clib_xxhash (tmp);
 122 #endif
 123 }
 124
 125 static_always_inline
 126 void kp_hash_prefetch_bucket(kp_hash_t *ht, u32 hash)
 127 {
 128   kp_hash_bucket_t *bucket = &ht->buckets[hash & ht->buckets_mask];
 129   CLIB_PREFETCH(bucket, sizeof(*bucket), READ);
 130 }
 131
 132 static_always_inline
 133 void kp_hash_get(kp_hash_t *ht, u32 hash, u32 vip, u32 time_now,
 134                  u32 *available_index, u32 *found_value)
 135 {
 136   kp_hash_bucket_t *bucket = &ht->buckets[hash & ht->buckets_mask];
 137   *found_value = ~0;
 138   *available_index = ~0;
 139 #if __SSE4_2__ && KP_HASH_DO_NOT_USE_SSE_BUCKETS == 0
 140   u32 bitmask, found_index;
 141   __m128i mask;
 142
 143   // mask[*] = timeout[*] > now
 144   mask = _mm_cmpgt_epi32(_mm_loadu_si128 ((__m128i *) bucket->timeout),
 145                          _mm_set1_epi32 (time_now));
 146   // bitmask[*] = now <= timeout[*/4]
 147   bitmask = (~_mm_movemask_epi8(mask)) & 0xffff;
 148   // Get first index with now <= timeout[*], if any.
 149   *available_index = (bitmask)?__builtin_ctz(bitmask)/4:*available_index;
 150
 151   // mask[*] = (timeout[*] > now) && (hash[*] == hash)
 152   mask = _mm_and_si128(mask,
 153                        _mm_cmpeq_epi32(
 154                            _mm_loadu_si128 ((__m128i *) bucket->hash),
 155                            _mm_set1_epi32 (hash)));
 156
 157   // Load the array of vip values
 158   // mask[*] = (timeout[*] > now) && (hash[*] == hash) && (vip[*] == vip)
 159   mask = _mm_and_si128(mask,
 160                        _mm_cmpeq_epi32(
 161                            _mm_loadu_si128 ((__m128i *) bucket->vip),
 162                            _mm_set1_epi32 (vip)));
 163
 164   // mask[*] = (timeout[*x4] > now) && (hash[*x4] == hash) && (vip[*x4] == vip)
 165   bitmask = _mm_movemask_epi8(mask);
 166   // Get first index, if any
 167   found_index = (bitmask)?__builtin_ctzll(bitmask)/4:0;
 168   ASSERT(found_index < 4);
 169   *found_value = (bitmask)?bucket->value[found_index]:*found_value;
 170   bucket->timeout[found_index] =
 171       (bitmask)?time_now + ht->timeout:bucket->timeout[found_index];
 172 #else
 173   u32 i;
 174   for (i = 0; i < KPHASH_ENTRY_PER_BUCKET; i++) {
 175       u8 cmp = (bucket->hash[i] == hash && bucket->vip[i] == vip);
 176       u8 timeouted = clib_u32_loop_gt(time_now, bucket->timeout[i]);
 177       *found_value = (cmp || timeouted)?*found_value:bucket->value[i];
 178       bucket->timeout[i] = (cmp || timeouted)?time_now + ht->timeout:bucket->timeout[i];
 179       *available_index = (timeouted && (*available_index == ~0))?i:*available_index;
 180
 181       if (!cmp)
 182         return;
 183   }
 184 #endif
 185 }
 186
 187 static_always_inline
 188 u32 kp_hash_available_value(kp_hash_t *h, u32 hash, u32 available_index)
 189 {
 190   return h->buckets[hash & h->buckets_mask].value[available_index];
 191 }
 192
 193 static_always_inline
 194 void kp_hash_put(kp_hash_t *h, u32 hash, u32 value, u32 vip,
 195                  u32 available_index, u32 time_now)
 196 {
 197   kp_hash_bucket_t *bucket = &h->buckets[hash & h->buckets_mask];
 198   bucket->hash[available_index] = hash;
 199   bucket->value[available_index] = value;
 200   bucket->timeout[available_index] = time_now + h->timeout;
 201   bucket->vip[available_index] = vip;
 202 }
 203
 204 static_always_inline
 205 u32 kp_hash_elts(kp_hash_t *h, u32 time_now)
 206 {
 207   u32 tot = 0;
 208   kp_hash_bucket_t *bucket;
 209   u32 i;
 210   kp_hash_foreach_valid_entry(h, bucket, i, time_now) {
 211     tot++;
 212   }
 213   return tot;
 214 }
 215
 216 #endif /* KP_PLUGIN_KP_KPHASH_H_ */