net/virtio: fix incorrect cast of void *
[dpdk.git] / rib / rte_rib6.c
1 /* SPDX-License-Identifier: BSD-3-Clause
2  * Copyright(c) 2018 Vladimir Medvedkin <medvedkinv@gmail.com>
3  * Copyright(c) 2019 Intel Corporation
4  */
5
6 #include <stdbool.h>
7 #include <stdint.h>
8
9 #include <rte_eal.h>
10 #include <rte_eal_memconfig.h>
11 #include <rte_errno.h>
12 #include <rte_malloc.h>
13 #include <rte_mempool.h>
14 #include <rte_rwlock.h>
15 #include <rte_string_fns.h>
16 #include <rte_tailq.h>
17
18 #include <rte_rib6.h>
19
20 #define RTE_RIB_VALID_NODE      1
21 #define RIB6_MAXDEPTH           128
22 /* Maximum length of a RIB6 name. */
23 #define RTE_RIB6_NAMESIZE       64
24
25 TAILQ_HEAD(rte_rib6_list, rte_tailq_entry);
26 static struct rte_tailq_elem rte_rib6_tailq = {
27         .name = "RTE_RIB6",
28 };
29 EAL_REGISTER_TAILQ(rte_rib6_tailq)
30
31 struct rte_rib6_node {
32         struct rte_rib6_node    *left;
33         struct rte_rib6_node    *right;
34         struct rte_rib6_node    *parent;
35         uint64_t                nh;
36         uint8_t                 ip[RTE_RIB6_IPV6_ADDR_SIZE];
37         uint8_t                 depth;
38         uint8_t                 flag;
39         __extension__ uint64_t          ext[0];
40 };
41
42 struct rte_rib6 {
43         char            name[RTE_RIB6_NAMESIZE];
44         struct rte_rib6_node    *tree;
45         struct rte_mempool      *node_pool;
46         uint32_t                cur_nodes;
47         uint32_t                cur_routes;
48         int                     max_nodes;
49 };
50
51 static inline bool
52 is_valid_node(struct rte_rib6_node *node)
53 {
54         return (node->flag & RTE_RIB_VALID_NODE) == RTE_RIB_VALID_NODE;
55 }
56
57 static inline bool
58 is_right_node(struct rte_rib6_node *node)
59 {
60         return node->parent->right == node;
61 }
62
63 /*
64  * Check if ip1 is covered by ip2/depth prefix
65  */
66 static inline bool
67 is_covered(const uint8_t ip1[RTE_RIB6_IPV6_ADDR_SIZE],
68                 const uint8_t ip2[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth)
69 {
70         int i;
71
72         for (i = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++)
73                 if ((ip1[i] ^ ip2[i]) & get_msk_part(depth, i))
74                         return false;
75
76         return true;
77 }
78
79 static inline int
80 get_dir(const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth)
81 {
82         uint8_t index, msk;
83
84         /*
85          * depth & 127 clamps depth to values that will not
86          * read off the end of ip.
87          * depth is the number of bits deep into ip to traverse, and
88          * is incremented in blocks of 8 (1 byte). This means the last
89          * 3 bits are irrelevant to what the index of ip should be.
90          */
91         index = (depth & (UINT8_MAX - 1)) / CHAR_BIT;
92
93         /*
94          * msk is the bitmask used to extract the bit used to decide the
95          * direction of the next step of the binary search.
96          */
97         msk = 1 << (7 - (depth & 7));
98
99         return (ip[index] & msk) != 0;
100 }
101
102 static inline struct rte_rib6_node *
103 get_nxt_node(struct rte_rib6_node *node,
104         const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE])
105 {
106         if (node->depth == RIB6_MAXDEPTH)
107                 return NULL;
108
109         return (get_dir(ip, node->depth)) ? node->right : node->left;
110 }
111
112 static struct rte_rib6_node *
113 node_alloc(struct rte_rib6 *rib)
114 {
115         struct rte_rib6_node *ent;
116         int ret;
117
118         ret = rte_mempool_get(rib->node_pool, (void *)&ent);
119         if (unlikely(ret != 0))
120                 return NULL;
121         ++rib->cur_nodes;
122         return ent;
123 }
124
125 static void
126 node_free(struct rte_rib6 *rib, struct rte_rib6_node *ent)
127 {
128         --rib->cur_nodes;
129         rte_mempool_put(rib->node_pool, ent);
130 }
131
132 struct rte_rib6_node *
133 rte_rib6_lookup(struct rte_rib6 *rib,
134         const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE])
135 {
136         struct rte_rib6_node *cur;
137         struct rte_rib6_node *prev = NULL;
138
139         if (unlikely(rib == NULL)) {
140                 rte_errno = EINVAL;
141                 return NULL;
142         }
143         cur = rib->tree;
144
145         while ((cur != NULL) && is_covered(ip, cur->ip, cur->depth)) {
146                 if (is_valid_node(cur))
147                         prev = cur;
148                 cur = get_nxt_node(cur, ip);
149         }
150         return prev;
151 }
152
153 struct rte_rib6_node *
154 rte_rib6_lookup_parent(struct rte_rib6_node *ent)
155 {
156         struct rte_rib6_node *tmp;
157
158         if (ent == NULL)
159                 return NULL;
160
161         tmp = ent->parent;
162         while ((tmp != NULL) && (!is_valid_node(tmp)))
163                 tmp = tmp->parent;
164
165         return tmp;
166 }
167
168 struct rte_rib6_node *
169 rte_rib6_lookup_exact(struct rte_rib6 *rib,
170         const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth)
171 {
172         struct rte_rib6_node *cur;
173         uint8_t tmp_ip[RTE_RIB6_IPV6_ADDR_SIZE];
174         int i;
175
176         if ((rib == NULL) || (ip == NULL) || (depth > RIB6_MAXDEPTH)) {
177                 rte_errno = EINVAL;
178                 return NULL;
179         }
180         cur = rib->tree;
181
182         for (i = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++)
183                 tmp_ip[i] = ip[i] & get_msk_part(depth, i);
184
185         while (cur != NULL) {
186                 if (rte_rib6_is_equal(cur->ip, tmp_ip) &&
187                                 (cur->depth == depth) &&
188                                 is_valid_node(cur))
189                         return cur;
190
191                 if (!(is_covered(tmp_ip, cur->ip, cur->depth)) ||
192                                 (cur->depth >= depth))
193                         break;
194
195                 cur = get_nxt_node(cur, tmp_ip);
196         }
197
198         return NULL;
199 }
200
201 /*
202  *  Traverses on subtree and retreeves more specific routes
203  *  for a given in args ip/depth prefix
204  *  last = NULL means the first invocation
205  */
206 struct rte_rib6_node *
207 rte_rib6_get_nxt(struct rte_rib6 *rib,
208         const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE],
209         uint8_t depth, struct rte_rib6_node *last, int flag)
210 {
211         struct rte_rib6_node *tmp, *prev = NULL;
212         uint8_t tmp_ip[RTE_RIB6_IPV6_ADDR_SIZE];
213         int i;
214
215         if ((rib == NULL) || (ip == NULL) || (depth > RIB6_MAXDEPTH)) {
216                 rte_errno = EINVAL;
217                 return NULL;
218         }
219
220         for (i = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++)
221                 tmp_ip[i] = ip[i] & get_msk_part(depth, i);
222
223         if (last == NULL) {
224                 tmp = rib->tree;
225                 while ((tmp) && (tmp->depth < depth))
226                         tmp = get_nxt_node(tmp, tmp_ip);
227         } else {
228                 tmp = last;
229                 while ((tmp->parent != NULL) && (is_right_node(tmp) ||
230                                 (tmp->parent->right == NULL))) {
231                         tmp = tmp->parent;
232                         if (is_valid_node(tmp) &&
233                                         (is_covered(tmp->ip, tmp_ip, depth) &&
234                                         (tmp->depth > depth)))
235                                 return tmp;
236                 }
237                 tmp = (tmp->parent != NULL) ? tmp->parent->right : NULL;
238         }
239         while (tmp) {
240                 if (is_valid_node(tmp) &&
241                                 (is_covered(tmp->ip, tmp_ip, depth) &&
242                                 (tmp->depth > depth))) {
243                         prev = tmp;
244                         if (flag == RTE_RIB6_GET_NXT_COVER)
245                                 return prev;
246                 }
247                 tmp = (tmp->left != NULL) ? tmp->left : tmp->right;
248         }
249         return prev;
250 }
251
252 void
253 rte_rib6_remove(struct rte_rib6 *rib,
254         const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth)
255 {
256         struct rte_rib6_node *cur, *prev, *child;
257
258         cur = rte_rib6_lookup_exact(rib, ip, depth);
259         if (cur == NULL)
260                 return;
261
262         --rib->cur_routes;
263         cur->flag &= ~RTE_RIB_VALID_NODE;
264         while (!is_valid_node(cur)) {
265                 if ((cur->left != NULL) && (cur->right != NULL))
266                         return;
267                 child = (cur->left == NULL) ? cur->right : cur->left;
268                 if (child != NULL)
269                         child->parent = cur->parent;
270                 if (cur->parent == NULL) {
271                         rib->tree = child;
272                         node_free(rib, cur);
273                         return;
274                 }
275                 if (cur->parent->left == cur)
276                         cur->parent->left = child;
277                 else
278                         cur->parent->right = child;
279                 prev = cur;
280                 cur = cur->parent;
281                 node_free(rib, prev);
282         }
283 }
284
285 struct rte_rib6_node *
286 rte_rib6_insert(struct rte_rib6 *rib,
287         const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth)
288 {
289         struct rte_rib6_node **tmp;
290         struct rte_rib6_node *prev = NULL;
291         struct rte_rib6_node *new_node = NULL;
292         struct rte_rib6_node *common_node = NULL;
293         uint8_t common_prefix[RTE_RIB6_IPV6_ADDR_SIZE];
294         uint8_t tmp_ip[RTE_RIB6_IPV6_ADDR_SIZE];
295         int i, d;
296         uint8_t common_depth, ip_xor;
297
298         if (unlikely((rib == NULL) || (ip == NULL) ||
299                         (depth > RIB6_MAXDEPTH))) {
300                 rte_errno = EINVAL;
301                 return NULL;
302         }
303
304         tmp = &rib->tree;
305
306         for (i = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++)
307                 tmp_ip[i] = ip[i] & get_msk_part(depth, i);
308
309         new_node = rte_rib6_lookup_exact(rib, tmp_ip, depth);
310         if (new_node != NULL) {
311                 rte_errno = EEXIST;
312                 return NULL;
313         }
314
315         new_node = node_alloc(rib);
316         if (new_node == NULL) {
317                 rte_errno = ENOMEM;
318                 return NULL;
319         }
320         new_node->left = NULL;
321         new_node->right = NULL;
322         new_node->parent = NULL;
323         rte_rib6_copy_addr(new_node->ip, tmp_ip);
324         new_node->depth = depth;
325         new_node->flag = RTE_RIB_VALID_NODE;
326
327         /* traverse down the tree to find matching node or closest matching */
328         while (1) {
329                 /* insert as the last node in the branch */
330                 if (*tmp == NULL) {
331                         *tmp = new_node;
332                         new_node->parent = prev;
333                         ++rib->cur_routes;
334                         return *tmp;
335                 }
336                 /*
337                  * Intermediate node found.
338                  * Previous rte_rib6_lookup_exact() returned NULL
339                  * but node with proper search criteria is found.
340                  * Validate intermediate node and return.
341                  */
342                 if (rte_rib6_is_equal(tmp_ip, (*tmp)->ip) &&
343                                 (depth == (*tmp)->depth)) {
344                         node_free(rib, new_node);
345                         (*tmp)->flag |= RTE_RIB_VALID_NODE;
346                         ++rib->cur_routes;
347                         return *tmp;
348                 }
349
350                 if (!is_covered(tmp_ip, (*tmp)->ip, (*tmp)->depth) ||
351                                 ((*tmp)->depth >= depth)) {
352                         break;
353                 }
354                 prev = *tmp;
355
356                 tmp = (get_dir(tmp_ip, (*tmp)->depth)) ? &(*tmp)->right :
357                                 &(*tmp)->left;
358         }
359
360         /* closest node found, new_node should be inserted in the middle */
361         common_depth = RTE_MIN(depth, (*tmp)->depth);
362         for (i = 0, d = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++) {
363                 ip_xor = tmp_ip[i] ^ (*tmp)->ip[i];
364                 if (ip_xor == 0)
365                         d += 8;
366                 else {
367                         d += __builtin_clz(ip_xor << 24);
368                         break;
369                 }
370         }
371
372         common_depth = RTE_MIN(d, common_depth);
373
374         for (i = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++)
375                 common_prefix[i] = tmp_ip[i] & get_msk_part(common_depth, i);
376
377         if (rte_rib6_is_equal(common_prefix, tmp_ip) &&
378                         (common_depth == depth)) {
379                 /* insert as a parent */
380                 if (get_dir((*tmp)->ip, depth))
381                         new_node->right = *tmp;
382                 else
383                         new_node->left = *tmp;
384                 new_node->parent = (*tmp)->parent;
385                 (*tmp)->parent = new_node;
386                 *tmp = new_node;
387         } else {
388                 /* create intermediate node */
389                 common_node = node_alloc(rib);
390                 if (common_node == NULL) {
391                         node_free(rib, new_node);
392                         rte_errno = ENOMEM;
393                         return NULL;
394                 }
395                 rte_rib6_copy_addr(common_node->ip, common_prefix);
396                 common_node->depth = common_depth;
397                 common_node->flag = 0;
398                 common_node->parent = (*tmp)->parent;
399                 new_node->parent = common_node;
400                 (*tmp)->parent = common_node;
401                 if (get_dir((*tmp)->ip, common_depth) == 1) {
402                         common_node->left = new_node;
403                         common_node->right = *tmp;
404                 } else {
405                         common_node->left = *tmp;
406                         common_node->right = new_node;
407                 }
408                 *tmp = common_node;
409         }
410         ++rib->cur_routes;
411         return new_node;
412 }
413
414 int
415 rte_rib6_get_ip(const struct rte_rib6_node *node,
416                 uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE])
417 {
418         if ((node == NULL) || (ip == NULL)) {
419                 rte_errno = EINVAL;
420                 return -1;
421         }
422         rte_rib6_copy_addr(ip, node->ip);
423         return 0;
424 }
425
426 int
427 rte_rib6_get_depth(const struct rte_rib6_node *node, uint8_t *depth)
428 {
429         if ((node == NULL) || (depth == NULL)) {
430                 rte_errno = EINVAL;
431                 return -1;
432         }
433         *depth = node->depth;
434         return 0;
435 }
436
437 void *
438 rte_rib6_get_ext(struct rte_rib6_node *node)
439 {
440         return (node == NULL) ? NULL : &node->ext[0];
441 }
442
443 int
444 rte_rib6_get_nh(const struct rte_rib6_node *node, uint64_t *nh)
445 {
446         if ((node == NULL) || (nh == NULL)) {
447                 rte_errno = EINVAL;
448                 return -1;
449         }
450         *nh = node->nh;
451         return 0;
452 }
453
454 int
455 rte_rib6_set_nh(struct rte_rib6_node *node, uint64_t nh)
456 {
457         if (node == NULL) {
458                 rte_errno = EINVAL;
459                 return -1;
460         }
461         node->nh = nh;
462         return 0;
463 }
464
465 struct rte_rib6 *
466 rte_rib6_create(const char *name, int socket_id,
467                 const struct rte_rib6_conf *conf)
468 {
469         char mem_name[RTE_RIB6_NAMESIZE];
470         struct rte_rib6 *rib = NULL;
471         struct rte_tailq_entry *te;
472         struct rte_rib6_list *rib6_list;
473         struct rte_mempool *node_pool;
474
475         /* Check user arguments. */
476         if (name == NULL || conf == NULL || conf->max_nodes <= 0) {
477                 rte_errno = EINVAL;
478                 return NULL;
479         }
480
481         snprintf(mem_name, sizeof(mem_name), "MP_%s", name);
482         node_pool = rte_mempool_create(mem_name, conf->max_nodes,
483                 sizeof(struct rte_rib6_node) + conf->ext_sz, 0, 0,
484                 NULL, NULL, NULL, NULL, socket_id, 0);
485
486         if (node_pool == NULL) {
487                 RTE_LOG(ERR, LPM,
488                         "Can not allocate mempool for RIB6 %s\n", name);
489                 return NULL;
490         }
491
492         snprintf(mem_name, sizeof(mem_name), "RIB6_%s", name);
493         rib6_list = RTE_TAILQ_CAST(rte_rib6_tailq.head, rte_rib6_list);
494
495         rte_mcfg_tailq_write_lock();
496
497         /* guarantee there's no existing */
498         TAILQ_FOREACH(te, rib6_list, next) {
499                 rib = (struct rte_rib6 *)te->data;
500                 if (strncmp(name, rib->name, RTE_RIB6_NAMESIZE) == 0)
501                         break;
502         }
503         rib = NULL;
504         if (te != NULL) {
505                 rte_errno = EEXIST;
506                 goto exit;
507         }
508
509         /* allocate tailq entry */
510         te = rte_zmalloc("RIB6_TAILQ_ENTRY", sizeof(*te), 0);
511         if (te == NULL) {
512                 RTE_LOG(ERR, LPM,
513                         "Can not allocate tailq entry for RIB6 %s\n", name);
514                 rte_errno = ENOMEM;
515                 goto exit;
516         }
517
518         /* Allocate memory to store the RIB6 data structures. */
519         rib = rte_zmalloc_socket(mem_name,
520                 sizeof(struct rte_rib6), RTE_CACHE_LINE_SIZE, socket_id);
521         if (rib == NULL) {
522                 RTE_LOG(ERR, LPM, "RIB6 %s memory allocation failed\n", name);
523                 rte_errno = ENOMEM;
524                 goto free_te;
525         }
526
527         rte_strlcpy(rib->name, name, sizeof(rib->name));
528         rib->tree = NULL;
529         rib->max_nodes = conf->max_nodes;
530         rib->node_pool = node_pool;
531
532         te->data = (void *)rib;
533         TAILQ_INSERT_TAIL(rib6_list, te, next);
534
535         rte_mcfg_tailq_write_unlock();
536
537         return rib;
538
539 free_te:
540         rte_free(te);
541 exit:
542         rte_mcfg_tailq_write_unlock();
543         rte_mempool_free(node_pool);
544
545         return NULL;
546 }
547
548 struct rte_rib6 *
549 rte_rib6_find_existing(const char *name)
550 {
551         struct rte_rib6 *rib = NULL;
552         struct rte_tailq_entry *te;
553         struct rte_rib6_list *rib6_list;
554
555         if (unlikely(name == NULL)) {
556                 rte_errno = EINVAL;
557                 return NULL;
558         }
559
560         rib6_list = RTE_TAILQ_CAST(rte_rib6_tailq.head, rte_rib6_list);
561
562         rte_mcfg_tailq_read_lock();
563         TAILQ_FOREACH(te, rib6_list, next) {
564                 rib = (struct rte_rib6 *) te->data;
565                 if (strncmp(name, rib->name, RTE_RIB6_NAMESIZE) == 0)
566                         break;
567         }
568         rte_mcfg_tailq_read_unlock();
569
570         if (te == NULL) {
571                 rte_errno = ENOENT;
572                 return NULL;
573         }
574
575         return rib;
576 }
577
578 void
579 rte_rib6_free(struct rte_rib6 *rib)
580 {
581         struct rte_tailq_entry *te;
582         struct rte_rib6_list *rib6_list;
583         struct rte_rib6_node *tmp = NULL;
584
585         if (unlikely(rib == NULL)) {
586                 rte_errno = EINVAL;
587                 return;
588         }
589
590         rib6_list = RTE_TAILQ_CAST(rte_rib6_tailq.head, rte_rib6_list);
591
592         rte_mcfg_tailq_write_lock();
593
594         /* find our tailq entry */
595         TAILQ_FOREACH(te, rib6_list, next) {
596                 if (te->data == (void *)rib)
597                         break;
598         }
599         if (te != NULL)
600                 TAILQ_REMOVE(rib6_list, te, next);
601
602         rte_mcfg_tailq_write_unlock();
603
604         while ((tmp = rte_rib6_get_nxt(rib, 0, 0, tmp,
605                         RTE_RIB6_GET_NXT_ALL)) != NULL)
606                 rte_rib6_remove(rib, tmp->ip, tmp->depth);
607
608         rte_mempool_free(rib->node_pool);
609
610         rte_free(rib);
611         rte_free(te);
612 }