1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2010-2014 Intel Corporation
3 */
4
5 #include <stdint.h>
6 #include <stdio.h>
7 #include <string.h>
8 #include <errno.h>
9
10 #include <sys/queue.h>
11 #include <rte_eal_memconfig.h>
12 #include <rte_malloc.h>
13 #include <rte_common.h>
14 #include <rte_errno.h>
15 #include <rte_string_fns.h>
16 #include <rte_log.h>
17 #include <rte_tailq.h>
18
19 #include "rte_fbk_hash.h"
20
21 TAILQ_HEAD(rte_fbk_hash_list, rte_tailq_entry);
22
23 static struct rte_tailq_elem rte_fbk_hash_tailq = {
24 .name = "RTE_FBK_HASH",
25 };
EAL_REGISTER_TAILQ(rte_fbk_hash_tailq)26 EAL_REGISTER_TAILQ(rte_fbk_hash_tailq)
27
28 /**
29 * Performs a lookup for an existing hash table, and returns a pointer to
30 * the table if found.
31 *
32 * @param name
33 * Name of the hash table to find
34 *
35 * @return
36 * pointer to hash table structure or NULL on error.
37 */
38 struct rte_fbk_hash_table *
39 rte_fbk_hash_find_existing(const char *name)
40 {
41 struct rte_fbk_hash_table *h = NULL;
42 struct rte_tailq_entry *te;
43 struct rte_fbk_hash_list *fbk_hash_list;
44
45 fbk_hash_list = RTE_TAILQ_CAST(rte_fbk_hash_tailq.head,
46 rte_fbk_hash_list);
47
48 rte_mcfg_tailq_read_lock();
49 TAILQ_FOREACH(te, fbk_hash_list, next) {
50 h = (struct rte_fbk_hash_table *) te->data;
51 if (strncmp(name, h->name, RTE_FBK_HASH_NAMESIZE) == 0)
52 break;
53 }
54 rte_mcfg_tailq_read_unlock();
55 if (te == NULL) {
56 rte_errno = ENOENT;
57 return NULL;
58 }
59 return h;
60 }
61
62 /**
63 * Create a new hash table for use with four byte keys.
64 *
65 * @param params
66 * Parameters used in creation of hash table.
67 *
68 * @return
69 * Pointer to hash table structure that is used in future hash table
70 * operations, or NULL on error.
71 */
72 struct rte_fbk_hash_table *
rte_fbk_hash_create(const struct rte_fbk_hash_params * params)73 rte_fbk_hash_create(const struct rte_fbk_hash_params *params)
74 {
75 struct rte_fbk_hash_table *ht = NULL;
76 struct rte_tailq_entry *te;
77 char hash_name[RTE_FBK_HASH_NAMESIZE];
78 const uint32_t mem_size =
79 sizeof(*ht) + (sizeof(ht->t[0]) * params->entries);
80 uint32_t i;
81 struct rte_fbk_hash_list *fbk_hash_list;
82 rte_fbk_hash_fn default_hash_func = (rte_fbk_hash_fn)rte_jhash_1word;
83
84 fbk_hash_list = RTE_TAILQ_CAST(rte_fbk_hash_tailq.head,
85 rte_fbk_hash_list);
86
87 /* Error checking of parameters. */
88 if ((!rte_is_power_of_2(params->entries)) ||
89 (!rte_is_power_of_2(params->entries_per_bucket)) ||
90 (params->entries == 0) ||
91 (params->entries_per_bucket == 0) ||
92 (params->entries_per_bucket > params->entries) ||
93 (params->entries > RTE_FBK_HASH_ENTRIES_MAX) ||
94 (params->entries_per_bucket > RTE_FBK_HASH_ENTRIES_PER_BUCKET_MAX)){
95 rte_errno = EINVAL;
96 return NULL;
97 }
98
99 snprintf(hash_name, sizeof(hash_name), "FBK_%s", params->name);
100
101 rte_mcfg_tailq_write_lock();
102
103 /* guarantee there's no existing */
104 TAILQ_FOREACH(te, fbk_hash_list, next) {
105 ht = (struct rte_fbk_hash_table *) te->data;
106 if (strncmp(params->name, ht->name, RTE_FBK_HASH_NAMESIZE) == 0)
107 break;
108 }
109 ht = NULL;
110 if (te != NULL) {
111 rte_errno = EEXIST;
112 goto exit;
113 }
114
115 te = rte_zmalloc("FBK_HASH_TAILQ_ENTRY", sizeof(*te), 0);
116 if (te == NULL) {
117 RTE_LOG(ERR, HASH, "Failed to allocate tailq entry\n");
118 goto exit;
119 }
120
121 /* Allocate memory for table. */
122 ht = rte_zmalloc_socket(hash_name, mem_size,
123 0, params->socket_id);
124 if (ht == NULL) {
125 RTE_LOG(ERR, HASH, "Failed to allocate fbk hash table\n");
126 rte_free(te);
127 goto exit;
128 }
129
130 /* Default hash function */
131 #if defined(RTE_ARCH_X86)
132 default_hash_func = (rte_fbk_hash_fn)rte_hash_crc_4byte;
133 #elif defined(RTE_ARCH_ARM64)
134 if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_CRC32))
135 default_hash_func = (rte_fbk_hash_fn)rte_hash_crc_4byte;
136 #endif
137
138 /* Set up hash table context. */
139 strlcpy(ht->name, params->name, sizeof(ht->name));
140 ht->entries = params->entries;
141 ht->entries_per_bucket = params->entries_per_bucket;
142 ht->used_entries = 0;
143 ht->bucket_mask = (params->entries / params->entries_per_bucket) - 1;
144 for (ht->bucket_shift = 0, i = 1;
145 (params->entries_per_bucket & i) == 0;
146 ht->bucket_shift++, i <<= 1)
147 ; /* empty loop body */
148
149 if (params->hash_func != NULL) {
150 ht->hash_func = params->hash_func;
151 ht->init_val = params->init_val;
152 }
153 else {
154 ht->hash_func = default_hash_func;
155 ht->init_val = RTE_FBK_HASH_INIT_VAL_DEFAULT;
156 }
157
158 te->data = (void *) ht;
159
160 TAILQ_INSERT_TAIL(fbk_hash_list, te, next);
161
162 exit:
163 rte_mcfg_tailq_write_unlock();
164
165 return ht;
166 }
167
168 /**
169 * Free all memory used by a hash table.
170 *
171 * @param ht
172 * Hash table to deallocate.
173 */
174 void
rte_fbk_hash_free(struct rte_fbk_hash_table * ht)175 rte_fbk_hash_free(struct rte_fbk_hash_table *ht)
176 {
177 struct rte_tailq_entry *te;
178 struct rte_fbk_hash_list *fbk_hash_list;
179
180 if (ht == NULL)
181 return;
182
183 fbk_hash_list = RTE_TAILQ_CAST(rte_fbk_hash_tailq.head,
184 rte_fbk_hash_list);
185
186 rte_mcfg_tailq_write_lock();
187
188 /* find out tailq entry */
189 TAILQ_FOREACH(te, fbk_hash_list, next) {
190 if (te->data == (void *) ht)
191 break;
192 }
193
194 if (te == NULL) {
195 rte_mcfg_tailq_write_unlock();
196 return;
197 }
198
199 TAILQ_REMOVE(fbk_hash_list, te, next);
200
201 rte_mcfg_tailq_write_unlock();
202
203 rte_free(ht);
204 rte_free(te);
205 }
206