DPDK  18.05.1
rte_cuckoo_hash.h
1 /* SPDX-License-Identifier: BSD-3-Clause
2  * Copyright(c) 2016 Intel Corporation
3  */
4 
5 /* rte_cuckoo_hash.h
6  * This file hold Cuckoo Hash private data structures to allows include from
7  * platform specific files like rte_cuckoo_hash_x86.h
8  */
9 
10 #ifndef _RTE_CUCKOO_HASH_H_
11 #define _RTE_CUCKOO_HASH_H_
12 
13 #if defined(RTE_ARCH_X86)
14 #include "rte_cmp_x86.h"
15 #endif
16 
17 #if defined(RTE_ARCH_ARM64)
18 #include "rte_cmp_arm64.h"
19 #endif
20 
21 /* Macro to enable/disable run-time checking of function parameters */
22 #if defined(RTE_LIBRTE_HASH_DEBUG)
23 #define RETURN_IF_TRUE(cond, retval) do { \
24  if (cond) \
25  return retval; \
26 } while (0)
27 #else
28 #define RETURN_IF_TRUE(cond, retval)
29 #endif
30 
31 #include <rte_hash_crc.h>
32 #include <rte_jhash.h>
33 
34 #if defined(RTE_ARCH_X86) || defined(RTE_ARCH_ARM64)
35 /*
36  * All different options to select a key compare function,
37  * based on the key size and custom function.
38  */
39 enum cmp_jump_table_case {
40  KEY_CUSTOM = 0,
41  KEY_16_BYTES,
42  KEY_32_BYTES,
43  KEY_48_BYTES,
44  KEY_64_BYTES,
45  KEY_80_BYTES,
46  KEY_96_BYTES,
47  KEY_112_BYTES,
48  KEY_128_BYTES,
49  KEY_OTHER_BYTES,
50  NUM_KEY_CMP_CASES,
51 };
52 
53 /*
54  * Table storing all different key compare functions
55  * (multi-process supported)
56  */
57 const rte_hash_cmp_eq_t cmp_jump_table[NUM_KEY_CMP_CASES] = {
58  NULL,
59  rte_hash_k16_cmp_eq,
60  rte_hash_k32_cmp_eq,
61  rte_hash_k48_cmp_eq,
62  rte_hash_k64_cmp_eq,
63  rte_hash_k80_cmp_eq,
64  rte_hash_k96_cmp_eq,
65  rte_hash_k112_cmp_eq,
66  rte_hash_k128_cmp_eq,
67  memcmp
68 };
69 #else
70 /*
71  * All different options to select a key compare function,
72  * based on the key size and custom function.
73  */
74 enum cmp_jump_table_case {
75  KEY_CUSTOM = 0,
76  KEY_OTHER_BYTES,
77  NUM_KEY_CMP_CASES,
78 };
79 
80 /*
81  * Table storing all different key compare functions
82  * (multi-process supported)
83  */
84 const rte_hash_cmp_eq_t cmp_jump_table[NUM_KEY_CMP_CASES] = {
85  NULL,
86  memcmp
87 };
88 
89 #endif
90 
91 enum add_key_case {
92  ADD_KEY_SINGLEWRITER = 0,
93  ADD_KEY_MULTIWRITER,
94  ADD_KEY_MULTIWRITER_TM,
95 };
96 
98 #define RTE_HASH_BUCKET_ENTRIES 8
99 
100 #define NULL_SIGNATURE 0
101 
102 #define EMPTY_SLOT 0
103 
104 #define KEY_ALIGNMENT 16
105 
106 #define LCORE_CACHE_SIZE 64
107 
108 #define RTE_HASH_MAX_PUSHES 100
109 
110 #define RTE_HASH_BFS_QUEUE_MAX_LEN 1000
111 
112 #define RTE_XABORT_CUCKOO_PATH_INVALIDED 0x4
113 
114 #define RTE_HASH_TSX_MAX_RETRY 10
115 
116 struct lcore_cache {
117  unsigned len;
118  void *objs[LCORE_CACHE_SIZE];
120 
121 /* Structure that stores key-value pair */
122 struct rte_hash_key {
123  union {
124  uintptr_t idata;
125  void *pdata;
126  };
127  /* Variable key size */
128  char key[0];
129 } __attribute__((aligned(KEY_ALIGNMENT)));
130 
131 /* All different signature compare functions */
132 enum rte_hash_sig_compare_function {
133  RTE_HASH_COMPARE_SCALAR = 0,
134  RTE_HASH_COMPARE_SSE,
135  RTE_HASH_COMPARE_AVX2,
136  RTE_HASH_COMPARE_NUM
137 };
138 
141  hash_sig_t sig_current[RTE_HASH_BUCKET_ENTRIES];
142 
143  uint32_t key_idx[RTE_HASH_BUCKET_ENTRIES];
144 
145  hash_sig_t sig_alt[RTE_HASH_BUCKET_ENTRIES];
146 
147  uint8_t flag[RTE_HASH_BUCKET_ENTRIES];
149 
151 struct rte_hash {
153  uint32_t entries;
154  uint32_t num_buckets;
158  uint8_t hw_trans_mem_support;
160  struct lcore_cache *local_free_slots;
162  enum add_key_case add_key;
166  /* Fields used in lookup */
167 
168  uint32_t key_len __rte_cache_aligned;
174  enum cmp_jump_table_case cmp_jump_table_idx;
176  enum rte_hash_sig_compare_function sig_cmp_fn;
178  uint32_t bucket_bitmask;
180  uint32_t key_entry_size;
182  void *key_store;
188 
189 struct queue_node {
190  struct rte_hash_bucket *bkt; /* Current bucket on the bfs search */
191 
192  struct queue_node *prev; /* Parent(bucket) in search path */
193  int prev_slot; /* Parent(slot) in search path */
194 };
195 
196 #endif