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