1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2010-2014 Intel Corporation
3 */
4
5 #include <stdalign.h>
6 #include <stdio.h>
7 #include <string.h>
8
9 #include <rte_common.h>
10 #include <rte_malloc.h>
11 #include <rte_byteorder.h>
12 #include <rte_log.h>
13 #include <rte_lpm.h>
14
15 #include "rte_table_lpm.h"
16
17 #include "table_log.h"
18
19 #ifndef RTE_TABLE_LPM_MAX_NEXT_HOPS
20 #define RTE_TABLE_LPM_MAX_NEXT_HOPS 65536
21 #endif
22
23 #ifdef RTE_TABLE_STATS_COLLECT
24
25 #define RTE_TABLE_LPM_STATS_PKTS_IN_ADD(table, val) \
26 table->stats.n_pkts_in += val
27 #define RTE_TABLE_LPM_STATS_PKTS_LOOKUP_MISS(table, val) \
28 table->stats.n_pkts_lookup_miss += val
29
30 #else
31
32 #define RTE_TABLE_LPM_STATS_PKTS_IN_ADD(table, val)
33 #define RTE_TABLE_LPM_STATS_PKTS_LOOKUP_MISS(table, val)
34
35 #endif
36
37 struct rte_table_lpm {
38 struct rte_table_stats stats;
39
40 /* Input parameters */
41 uint32_t entry_size;
42 uint32_t entry_unique_size;
43 uint32_t n_rules;
44 uint32_t offset;
45
46 /* Handle to low-level LPM table */
47 struct rte_lpm *lpm;
48
49 /* Next Hop Table (NHT) */
50 uint32_t nht_users[RTE_TABLE_LPM_MAX_NEXT_HOPS];
51 alignas(RTE_CACHE_LINE_SIZE) uint8_t nht[];
52 };
53
54 static void *
rte_table_lpm_create(void * params,int socket_id,uint32_t entry_size)55 rte_table_lpm_create(void *params, int socket_id, uint32_t entry_size)
56 {
57 struct rte_table_lpm_params *p = params;
58 struct rte_table_lpm *lpm;
59 struct rte_lpm_config lpm_config;
60
61 uint32_t total_size, nht_size;
62
63 /* Check input parameters */
64 if (p == NULL) {
65 TABLE_LOG(ERR, "%s: NULL input parameters", __func__);
66 return NULL;
67 }
68 if (p->n_rules == 0) {
69 TABLE_LOG(ERR, "%s: Invalid n_rules", __func__);
70 return NULL;
71 }
72 if (p->number_tbl8s == 0) {
73 TABLE_LOG(ERR, "%s: Invalid number_tbl8s", __func__);
74 return NULL;
75 }
76 if (p->entry_unique_size == 0) {
77 TABLE_LOG(ERR, "%s: Invalid entry_unique_size",
78 __func__);
79 return NULL;
80 }
81 if (p->entry_unique_size > entry_size) {
82 TABLE_LOG(ERR, "%s: Invalid entry_unique_size",
83 __func__);
84 return NULL;
85 }
86 if (p->name == NULL) {
87 TABLE_LOG(ERR, "%s: Table name is NULL",
88 __func__);
89 return NULL;
90 }
91 entry_size = RTE_ALIGN(entry_size, sizeof(uint64_t));
92
93 /* Memory allocation */
94 nht_size = RTE_TABLE_LPM_MAX_NEXT_HOPS * entry_size;
95 total_size = sizeof(struct rte_table_lpm) + nht_size;
96 lpm = rte_zmalloc_socket("TABLE", total_size, RTE_CACHE_LINE_SIZE,
97 socket_id);
98 if (lpm == NULL) {
99 TABLE_LOG(ERR,
100 "%s: Cannot allocate %u bytes for LPM table",
101 __func__, total_size);
102 return NULL;
103 }
104
105 /* LPM low-level table creation */
106 lpm_config.max_rules = p->n_rules;
107 lpm_config.number_tbl8s = p->number_tbl8s;
108 lpm_config.flags = p->flags;
109 lpm->lpm = rte_lpm_create(p->name, socket_id, &lpm_config);
110
111 if (lpm->lpm == NULL) {
112 rte_free(lpm);
113 TABLE_LOG(ERR, "Unable to create low-level LPM table");
114 return NULL;
115 }
116
117 /* Memory initialization */
118 lpm->entry_size = entry_size;
119 lpm->entry_unique_size = p->entry_unique_size;
120 lpm->n_rules = p->n_rules;
121 lpm->offset = p->offset;
122
123 return lpm;
124 }
125
126 static int
rte_table_lpm_free(void * table)127 rte_table_lpm_free(void *table)
128 {
129 struct rte_table_lpm *lpm = table;
130
131 /* Check input parameters */
132 if (lpm == NULL) {
133 TABLE_LOG(ERR, "%s: table parameter is NULL", __func__);
134 return -EINVAL;
135 }
136
137 /* Free previously allocated resources */
138 rte_lpm_free(lpm->lpm);
139 rte_free(lpm);
140
141 return 0;
142 }
143
144 static int
nht_find_free(struct rte_table_lpm * lpm,uint32_t * pos)145 nht_find_free(struct rte_table_lpm *lpm, uint32_t *pos)
146 {
147 uint32_t i;
148
149 for (i = 0; i < RTE_TABLE_LPM_MAX_NEXT_HOPS; i++) {
150 if (lpm->nht_users[i] == 0) {
151 *pos = i;
152 return 1;
153 }
154 }
155
156 return 0;
157 }
158
159 static int
nht_find_existing(struct rte_table_lpm * lpm,void * entry,uint32_t * pos)160 nht_find_existing(struct rte_table_lpm *lpm, void *entry, uint32_t *pos)
161 {
162 uint32_t i;
163
164 for (i = 0; i < RTE_TABLE_LPM_MAX_NEXT_HOPS; i++) {
165 uint8_t *nht_entry = &lpm->nht[i * lpm->entry_size];
166
167 if ((lpm->nht_users[i] > 0) && (memcmp(nht_entry, entry,
168 lpm->entry_unique_size) == 0)) {
169 *pos = i;
170 return 1;
171 }
172 }
173
174 return 0;
175 }
176
177 static int
rte_table_lpm_entry_add(void * table,void * key,void * entry,int * key_found,void ** entry_ptr)178 rte_table_lpm_entry_add(
179 void *table,
180 void *key,
181 void *entry,
182 int *key_found,
183 void **entry_ptr)
184 {
185 struct rte_table_lpm *lpm = table;
186 struct rte_table_lpm_key *ip_prefix = key;
187 uint32_t nht_pos, nht_pos0_valid;
188 int status;
189 uint32_t nht_pos0 = 0;
190
191 /* Check input parameters */
192 if (lpm == NULL) {
193 TABLE_LOG(ERR, "%s: table parameter is NULL", __func__);
194 return -EINVAL;
195 }
196 if (ip_prefix == NULL) {
197 TABLE_LOG(ERR, "%s: ip_prefix parameter is NULL",
198 __func__);
199 return -EINVAL;
200 }
201 if (entry == NULL) {
202 TABLE_LOG(ERR, "%s: entry parameter is NULL", __func__);
203 return -EINVAL;
204 }
205
206 if ((ip_prefix->depth == 0) || (ip_prefix->depth > 32)) {
207 TABLE_LOG(ERR, "%s: invalid depth (%d)",
208 __func__, ip_prefix->depth);
209 return -EINVAL;
210 }
211
212 /* Check if rule is already present in the table */
213 status = rte_lpm_is_rule_present(lpm->lpm, ip_prefix->ip,
214 ip_prefix->depth, &nht_pos0);
215 nht_pos0_valid = status > 0;
216
217 /* Find existing or free NHT entry */
218 if (nht_find_existing(lpm, entry, &nht_pos) == 0) {
219 uint8_t *nht_entry;
220
221 if (nht_find_free(lpm, &nht_pos) == 0) {
222 TABLE_LOG(ERR, "%s: NHT full", __func__);
223 return -1;
224 }
225
226 nht_entry = &lpm->nht[nht_pos * lpm->entry_size];
227 memcpy(nht_entry, entry, lpm->entry_size);
228 }
229
230 /* Add rule to low level LPM table */
231 if (rte_lpm_add(lpm->lpm, ip_prefix->ip, ip_prefix->depth, nht_pos) < 0) {
232 TABLE_LOG(ERR, "%s: LPM rule add failed", __func__);
233 return -1;
234 }
235
236 /* Commit NHT changes */
237 lpm->nht_users[nht_pos]++;
238 lpm->nht_users[nht_pos0] -= nht_pos0_valid;
239
240 *key_found = nht_pos0_valid;
241 *entry_ptr = (void *) &lpm->nht[nht_pos * lpm->entry_size];
242 return 0;
243 }
244
245 static int
rte_table_lpm_entry_delete(void * table,void * key,int * key_found,void * entry)246 rte_table_lpm_entry_delete(
247 void *table,
248 void *key,
249 int *key_found,
250 void *entry)
251 {
252 struct rte_table_lpm *lpm = table;
253 struct rte_table_lpm_key *ip_prefix = key;
254 uint32_t nht_pos;
255 int status;
256
257 /* Check input parameters */
258 if (lpm == NULL) {
259 TABLE_LOG(ERR, "%s: table parameter is NULL", __func__);
260 return -EINVAL;
261 }
262 if (ip_prefix == NULL) {
263 TABLE_LOG(ERR, "%s: ip_prefix parameter is NULL",
264 __func__);
265 return -EINVAL;
266 }
267 if ((ip_prefix->depth == 0) || (ip_prefix->depth > 32)) {
268 TABLE_LOG(ERR, "%s: invalid depth (%d)", __func__,
269 ip_prefix->depth);
270 return -EINVAL;
271 }
272
273 /* Return if rule is not present in the table */
274 status = rte_lpm_is_rule_present(lpm->lpm, ip_prefix->ip,
275 ip_prefix->depth, &nht_pos);
276 if (status < 0) {
277 TABLE_LOG(ERR, "%s: LPM algorithmic error", __func__);
278 return -1;
279 }
280 if (status == 0) {
281 *key_found = 0;
282 return 0;
283 }
284
285 /* Delete rule from the low-level LPM table */
286 status = rte_lpm_delete(lpm->lpm, ip_prefix->ip, ip_prefix->depth);
287 if (status) {
288 TABLE_LOG(ERR, "%s: LPM rule delete failed", __func__);
289 return -1;
290 }
291
292 /* Commit NHT changes */
293 lpm->nht_users[nht_pos]--;
294
295 *key_found = 1;
296 if (entry)
297 memcpy(entry, &lpm->nht[nht_pos * lpm->entry_size],
298 lpm->entry_size);
299
300 return 0;
301 }
302
303 static int
rte_table_lpm_lookup(void * table,struct rte_mbuf ** pkts,uint64_t pkts_mask,uint64_t * lookup_hit_mask,void ** entries)304 rte_table_lpm_lookup(
305 void *table,
306 struct rte_mbuf **pkts,
307 uint64_t pkts_mask,
308 uint64_t *lookup_hit_mask,
309 void **entries)
310 {
311 struct rte_table_lpm *lpm = (struct rte_table_lpm *) table;
312 uint64_t pkts_out_mask = 0;
313 uint32_t i;
314
315 __rte_unused uint32_t n_pkts_in = rte_popcount64(pkts_mask);
316 RTE_TABLE_LPM_STATS_PKTS_IN_ADD(lpm, n_pkts_in);
317
318 pkts_out_mask = 0;
319 for (i = 0; i < (uint32_t)(RTE_PORT_IN_BURST_SIZE_MAX -
320 rte_clz64(pkts_mask)); i++) {
321 uint64_t pkt_mask = 1LLU << i;
322
323 if (pkt_mask & pkts_mask) {
324 struct rte_mbuf *pkt = pkts[i];
325 uint32_t ip = rte_bswap32(
326 RTE_MBUF_METADATA_UINT32(pkt, lpm->offset));
327 int status;
328 uint32_t nht_pos;
329
330 status = rte_lpm_lookup(lpm->lpm, ip, &nht_pos);
331 if (status == 0) {
332 pkts_out_mask |= pkt_mask;
333 entries[i] = (void *) &lpm->nht[nht_pos *
334 lpm->entry_size];
335 }
336 }
337 }
338
339 *lookup_hit_mask = pkts_out_mask;
340 RTE_TABLE_LPM_STATS_PKTS_LOOKUP_MISS(lpm, n_pkts_in - rte_popcount64(pkts_out_mask));
341 return 0;
342 }
343
344 static int
rte_table_lpm_stats_read(void * table,struct rte_table_stats * stats,int clear)345 rte_table_lpm_stats_read(void *table, struct rte_table_stats *stats, int clear)
346 {
347 struct rte_table_lpm *t = table;
348
349 if (stats != NULL)
350 memcpy(stats, &t->stats, sizeof(t->stats));
351
352 if (clear)
353 memset(&t->stats, 0, sizeof(t->stats));
354
355 return 0;
356 }
357
358 struct rte_table_ops rte_table_lpm_ops = {
359 .f_create = rte_table_lpm_create,
360 .f_free = rte_table_lpm_free,
361 .f_add = rte_table_lpm_entry_add,
362 .f_delete = rte_table_lpm_entry_delete,
363 .f_add_bulk = NULL,
364 .f_delete_bulk = NULL,
365 .f_lookup = rte_table_lpm_lookup,
366 .f_stats = rte_table_lpm_stats_read,
367 };
368