Line data    Source code

       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 trivial 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          13 : lb_hash_t *lb_hash_alloc(u32 buckets, u32 timeout)
      82             : {
      83          13 :   if (!is_pow2(buckets))
      84           0 :     return NULL;
      85             : 
      86             :   // Allocate 1 more bucket for prefetch
      87          13 :   u32 size = ((uword)&((lb_hash_t *)(0))->buckets[0]) +
      88             :       sizeof(lb_hash_bucket_t) * (buckets + 1);
      89          13 :   u8 *mem = 0;
      90             :   lb_hash_t *h;
      91          13 :   vec_validate_aligned (mem, size - 1, CLIB_CACHE_LINE_BYTES);
      92          13 :   h = (lb_hash_t *)mem;
      93          13 :   h->buckets_mask = (buckets - 1);
      94          13 :   h->timeout = timeout;
      95          13 :   return h;
      96             : }
      97             : 
      98             : static_always_inline
      99          13 : void lb_hash_free(lb_hash_t *h)
     100             : {
     101          13 :   u8 *mem = (u8 *)h;
     102          13 :   vec_free(mem);
     103          13 : }
     104             : 
     105             : static_always_inline
     106        1287 : void lb_hash_prefetch_bucket(lb_hash_t *ht, u32 hash)
     107             : {
     108        1287 :   lb_hash_bucket_t *bucket = &ht->buckets[hash & ht->buckets_mask];
     109        1287 :   CLIB_PREFETCH(bucket, sizeof(*bucket), READ);
     110        1287 : }
     111             : 
     112             : static_always_inline
     113        1300 : void lb_hash_get(lb_hash_t *ht, u32 hash, u32 vip, u32 time_now,
     114             :                  u32 *available_index, u32 *found_value)
     115             : {
     116        1300 :   lb_hash_bucket_t *bucket = &ht->buckets[hash & ht->buckets_mask];
     117        1300 :   *found_value = 0;
     118        1300 :   *available_index = ~0;
     119             : #if __SSE4_2__ && LB_HASH_DO_NOT_USE_SSE_BUCKETS == 0
     120             :   u32 bitmask, found_index;
     121             :   __m128i mask;
     122             : 
     123             :   // mask[*] = timeout[*] > now
     124        5200 :   mask = _mm_cmpgt_epi32(_mm_loadu_si128 ((__m128i *) bucket->timeout),
     125             :                          _mm_set1_epi32 (time_now));
     126             :   // bitmask[*] = now <= timeout[*/4]
     127        1300 :   bitmask = (~_mm_movemask_epi8(mask)) & 0xffff;
     128             :   // Get first index with now <= timeout[*], if any.
     129        1300 :   *available_index = (bitmask)?__builtin_ctz(bitmask)/4:*available_index;
     130             : 
     131             :   // mask[*] = (timeout[*] > now) && (hash[*] == hash)
     132        3900 :   mask = _mm_and_si128(mask,
     133             :                        _mm_cmpeq_epi32(
     134        1300 :                            _mm_loadu_si128 ((__m128i *) bucket->hash),
     135             :                            _mm_set1_epi32 (hash)));
     136             : 
     137             :   // Load the array of vip values
     138             :   // mask[*] = (timeout[*] > now) && (hash[*] == hash) && (vip[*] == vip)
     139        5200 :   mask = _mm_and_si128(mask,
     140             :                        _mm_cmpeq_epi32(
     141        1300 :                            _mm_loadu_si128 ((__m128i *) bucket->vip),
     142             :                            _mm_set1_epi32 (vip)));
     143             : 
     144             :   // mask[*] = (timeout[*x4] > now) && (hash[*x4] == hash) && (vip[*x4] == vip)
     145        1300 :   bitmask = _mm_movemask_epi8(mask);
     146             :   // Get first index, if any
     147        1300 :   found_index = (bitmask)?__builtin_ctzll(bitmask)/4:0;
     148        1300 :   ASSERT(found_index < 4);
     149        1300 :   *found_value = (bitmask)?bucket->value[found_index]:*found_value;
     150        1300 :   bucket->timeout[found_index] =
     151        1300 :       (bitmask)?time_now + ht->timeout:bucket->timeout[found_index];
     152             : #else
     153             :   u32 i;
     154             :   for (i = 0; i < LBHASH_ENTRY_PER_BUCKET; i++) {
     155             :       u8 cmp = (bucket->hash[i] == hash && bucket->vip[i] == vip);
     156             :       u8 timeouted = clib_u32_loop_gt(time_now, bucket->timeout[i]);
     157             :       *found_value = (cmp || timeouted)?*found_value:bucket->value[i];
     158             :       bucket->timeout[i] = (cmp || timeouted)?time_now + ht->timeout:bucket->timeout[i];
     159             :       *available_index = (timeouted && (*available_index == ~0))?i:*available_index;
     160             : 
     161             :       if (!cmp)
     162             :         return;
     163             :   }
     164             : #endif
     165        1300 : }
     166             : 
     167             : static_always_inline
     168        1250 : u32 lb_hash_available_value(lb_hash_t *h, u32 hash, u32 available_index)
     169             : {
     170        1250 :   return h->buckets[hash & h->buckets_mask].value[available_index];
     171             : }
     172             : 
     173             : static_always_inline
     174        1250 : void lb_hash_put(lb_hash_t *h, u32 hash, u32 value, u32 vip,
     175             :                  u32 available_index, u32 time_now)
     176             : {
     177        1250 :   lb_hash_bucket_t *bucket = &h->buckets[hash & h->buckets_mask];
     178        1250 :   bucket->hash[available_index] = hash;
     179        1250 :   bucket->value[available_index] = value;
     180        1250 :   bucket->timeout[available_index] = time_now + h->timeout;
     181        1250 :   bucket->vip[available_index] = vip;
     182        1250 : }
     183             : 
     184             : static_always_inline
     185           0 : u32 lb_hash_elts(lb_hash_t *h, u32 time_now)
     186             : {
     187           0 :   u32 tot = 0;
     188             :   lb_hash_bucket_t *bucket;
     189             :   u32 i;
     190           0 :   lb_hash_foreach_valid_entry(h, bucket, i, time_now) {
     191           0 :     tot++;
     192             :   }
     193           0 :   return tot;
     194             : }
     195             : 
     196             : #endif /* LB_PLUGIN_LB_LBHASH_H_ */