lib/librte_table/rte_lru.h

   1 /*-
   2  *   BSD LICENSE
   3  *
   4  *   Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
   5  *   All rights reserved.
   6  *
   7  *   Redistribution and use in source and binary forms, with or without
   8  *   modification, are permitted provided that the following conditions
   9  *   are met:
  10  *
  11  *     * Redistributions of source code must retain the above copyright
  12  *       notice, this list of conditions and the following disclaimer.
  13  *     * Redistributions in binary form must reproduce the above copyright
  14  *       notice, this list of conditions and the following disclaimer in
  15  *       the documentation and/or other materials provided with the
  16  *       distribution.
  17  *     * Neither the name of Intel Corporation nor the names of its
  18  *       contributors may be used to endorse or promote products derived
  19  *       from this software without specific prior written permission.
  20  *
  21  *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22  *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23  *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  24  *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  25  *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  26  *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  27  *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  28  *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  29  *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  30  *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  31  *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  32  */
  33
  34 #ifndef __INCLUDE_RTE_LRU_H__
  35 #define __INCLUDE_RTE_LRU_H__
  36
  37 #ifdef __cplusplus
  38 extern "C" {
  39 #endif
  40
  41 #include <stdint.h>
  42
  43 #ifdef __INTEL_COMPILER
  44 #define GCC_VERSION (0)
  45 #else
  46 #define GCC_VERSION (__GNUC__ * 10000+__GNUC_MINOR__*100 + __GNUC_PATCHLEVEL__)
  47 #endif
  48
  49 #ifndef RTE_TABLE_HASH_LRU_STRATEGY
  50 #ifdef __SSE4_2__
  51 #define RTE_TABLE_HASH_LRU_STRATEGY                        2
  52 #else /* if no SSE, use simple scalar version */
  53 #define RTE_TABLE_HASH_LRU_STRATEGY                        1
  54 #endif
  55 #endif
  56
  57 #ifndef RTE_ARCH_X86_64
  58 #undef RTE_TABLE_HASH_LRU_STRATEGY
  59 #define RTE_TABLE_HASH_LRU_STRATEGY                        1
  60 #endif
  61
  62 #if (RTE_TABLE_HASH_LRU_STRATEGY < 0) || (RTE_TABLE_HASH_LRU_STRATEGY > 3)
  63 #error Invalid value for RTE_TABLE_HASH_LRU_STRATEGY
  64 #endif
  65
  66 #if RTE_TABLE_HASH_LRU_STRATEGY == 0
  67
  68 #define lru_init(bucket)                                                \
  69 do                                                                      \
  70         bucket = bucket;                                                \
  71 while (0)
  72
  73 #define lru_pos(bucket) (bucket->lru_list & 0xFFFFLLU)
  74
  75 #define lru_update(bucket, mru_val)                                     \
  76 do {                                                                    \
  77         bucket = bucket;                                                \
  78         mru_val = mru_val;                                              \
  79 } while (0)
  80
  81 #elif RTE_TABLE_HASH_LRU_STRATEGY == 1
  82
  83 #define lru_init(bucket)                                                \
  84 do                                                                      \
  85         bucket->lru_list = 0x0000000100020003LLU;                       \
  86 while (0)
  87
  88 #define lru_pos(bucket) (bucket->lru_list & 0xFFFFLLU)
  89
  90 #define lru_update(bucket, mru_val)                                     \
  91 do {                                                                    \
  92         uint64_t x, pos, x0, x1, x2, mask;                              \
  93                                                                         \
  94         x = bucket->lru_list;                                           \
  95                                                                         \
  96         pos = 4;                                                        \
  97         if ((x >> 48) == ((uint64_t) mru_val))                          \
  98                 pos = 3;                                                \
  99                                                                         \
 100         if (((x >> 32) & 0xFFFFLLU) == ((uint64_t) mru_val))            \
 101                 pos = 2;                                                \
 102                                                                         \
 103         if (((x >> 16) & 0xFFFFLLU) == ((uint64_t) mru_val))            \
 104                 pos = 1;                                                \
 105                                                                         \
 106         if ((x & 0xFFFFLLU) == ((uint64_t) mru_val))                    \
 107                 pos = 0;                                                \
 108                                                                         \
 109                                                                         \
 110         pos <<= 4;                                                      \
 111         mask = (~0LLU) << pos;                                          \
 112         x0 = x & (~mask);                                               \
 113         x1 = (x >> 16) & mask;                                          \
 114         x2 = (x << (48 - pos)) & (0xFFFFLLU << 48);                     \
 115         x = x0 | x1 | x2;                                               \
 116                                                                         \
 117         if (pos != 64)                                                  \
 118                 bucket->lru_list = x;                                   \
 119 } while (0)
 120
 121 #elif RTE_TABLE_HASH_LRU_STRATEGY == 2
 122
 123 #if GCC_VERSION > 40306
 124 #include <x86intrin.h>
 125 #else
 126 #include <emmintrin.h>
 127 #include <smmintrin.h>
 128 #include <xmmintrin.h>
 129 #endif
 130
 131 #define lru_init(bucket)                                                \
 132 do                                                                      \
 133         bucket->lru_list = 0x0000000100020003LLU;                       \
 134 while (0)
 135
 136 #define lru_pos(bucket) (bucket->lru_list & 0xFFFFLLU)
 137
 138 #define lru_update(bucket, mru_val)                                     \
 139 do {                                                                    \
 140         /* set up the masks for all possible shuffles, depends on pos */\
 141         static uint64_t masks[10] = {                                   \
 142                 /* Shuffle order; Make Zero (see _mm_shuffle_epi8 manual) */\
 143                 0x0100070605040302, 0x8080808080808080,                 \
 144                 0x0302070605040100, 0x8080808080808080,                 \
 145                 0x0504070603020100, 0x8080808080808080,                 \
 146                 0x0706050403020100, 0x8080808080808080,                 \
 147                 0x0706050403020100, 0x8080808080808080};                \
 148         /* load up one register with repeats of mru-val  */             \
 149         uint64_t mru2 = mru_val;                                        \
 150         uint64_t mru3 = mru2 | (mru2 << 16);                            \
 151         uint64_t lru = bucket->lru_list;                                \
 152         /* XOR to cause the word we're looking for to go to zero */     \
 153         uint64_t mru = lru ^ ((mru3 << 32) | mru3);                     \
 154         __m128i c = _mm_cvtsi64_si128(mru);                             \
 155         __m128i b = _mm_cvtsi64_si128(lru);                             \
 156         /* Find the minimum value (first zero word, if it's in there) */\
 157         __m128i d = _mm_minpos_epu16(c);                                \
 158         /* Second word is the index to found word (first word is the value) */\
 159         unsigned pos = _mm_extract_epi16(d, 1);                         \
 160         /* move the recently used location to top of list */            \
 161         __m128i k = _mm_shuffle_epi8(b, *((__m128i *) &masks[2 * pos]));\
 162         /* Finally, update the original list with the reordered data */ \
 163         bucket->lru_list = _mm_extract_epi64(k, 0);                     \
 164         /* Phwew! */                                                    \
 165 } while (0)
 166
 167 #elif RTE_TABLE_HASH_LRU_STRATEGY == 3
 168
 169 #if GCC_VERSION > 40306
 170 #include <x86intrin.h>
 171 #else
 172 #include <emmintrin.h>
 173 #include <smmintrin.h>
 174 #include <xmmintrin.h>
 175 #endif
 176
 177 #define lru_init(bucket)                                                \
 178 do                                                                      \
 179         bucket->lru_list = ~0LLU;                                       \
 180 while (0)
 181
 182
 183 static inline int
 184 f_lru_pos(uint64_t lru_list)
 185 {
 186         __m128i lst = _mm_set_epi64x((uint64_t)-1, lru_list);
 187         __m128i min = _mm_minpos_epu16(lst);
 188         return _mm_extract_epi16(min, 1);
 189 }
 190 #define lru_pos(bucket) f_lru_pos(bucket->lru_list)
 191
 192 #define lru_update(bucket, mru_val)                                     \
 193 do {                                                                    \
 194         const uint64_t orvals[] = {0xFFFFLLU, 0xFFFFLLU << 16,          \
 195                 0xFFFFLLU << 32, 0xFFFFLLU << 48, 0LLU};                \
 196         const uint64_t decs[] = {0x1000100010001LLU, 0};                \
 197         __m128i lru = _mm_cvtsi64_si128(bucket->lru_list);              \
 198         __m128i vdec = _mm_cvtsi64_si128(decs[mru_val>>2]);             \
 199         lru = _mm_subs_epu16(lru, vdec);                                \
 200         bucket->lru_list = _mm_extract_epi64(lru, 0) | orvals[mru_val]; \
 201 } while (0)
 202
 203 #else
 204
 205 #error "Incorrect value for RTE_TABLE_HASH_LRU_STRATEGY"
 206
 207 #endif
 208
 209 #ifdef __cplusplus
 210 }
 211 #endif
 212
 213 #endif