net/liquidio: add APIs to start device and update link
[dpdk.git] / 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