]> git.proxmox.com Git - mirror_frr.git/blob - zebra/zebra_rib.c
Merge pull request #1696 from donaldsharp/pim_node_removal
[mirror_frr.git] / zebra / zebra_rib.c
1 /* Routing Information Base.
2 * Copyright (C) 1997, 98, 99, 2001 Kunihiro Ishiguro
3 *
4 * This file is part of GNU Zebra.
5 *
6 * GNU Zebra is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License as published by the
8 * Free Software Foundation; either version 2, or (at your option) any
9 * later version.
10 *
11 * GNU Zebra is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License along
17 * with this program; see the file COPYING; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 */
20
21 #include <zebra.h>
22
23 #include "if.h"
24 #include "prefix.h"
25 #include "table.h"
26 #include "memory.h"
27 #include "zebra_memory.h"
28 #include "command.h"
29 #include "log.h"
30 #include "log_int.h"
31 #include "sockunion.h"
32 #include "linklist.h"
33 #include "thread.h"
34 #include "workqueue.h"
35 #include "prefix.h"
36 #include "routemap.h"
37 #include "nexthop.h"
38 #include "vrf.h"
39 #include "mpls.h"
40 #include "srcdest_table.h"
41
42 #include "zebra/rib.h"
43 #include "zebra/rt.h"
44 #include "zebra/zebra_ns.h"
45 #include "zebra/zserv.h"
46 #include "zebra/zebra_vrf.h"
47 #include "zebra/redistribute.h"
48 #include "zebra/zebra_routemap.h"
49 #include "zebra/debug.h"
50 #include "zebra/zebra_rnh.h"
51 #include "zebra/interface.h"
52 #include "zebra/connected.h"
53 #include "zebra/zebra_vxlan.h"
54
55 DEFINE_HOOK(rib_update, (struct route_node * rn, const char *reason),
56 (rn, reason))
57
58 /* Should we allow non Quagga processes to delete our routes */
59 extern int allow_delete;
60
61 /* Each route type's string and default distance value. */
62 static const struct {
63 int key;
64 int distance;
65 } route_info[ZEBRA_ROUTE_MAX] = {
66 [ZEBRA_ROUTE_SYSTEM] = {ZEBRA_ROUTE_SYSTEM, 0},
67 [ZEBRA_ROUTE_KERNEL] = {ZEBRA_ROUTE_KERNEL, 0},
68 [ZEBRA_ROUTE_CONNECT] = {ZEBRA_ROUTE_CONNECT, 0},
69 [ZEBRA_ROUTE_STATIC] = {ZEBRA_ROUTE_STATIC, 1},
70 [ZEBRA_ROUTE_RIP] = {ZEBRA_ROUTE_RIP, 120},
71 [ZEBRA_ROUTE_RIPNG] = {ZEBRA_ROUTE_RIPNG, 120},
72 [ZEBRA_ROUTE_OSPF] = {ZEBRA_ROUTE_OSPF, 110},
73 [ZEBRA_ROUTE_OSPF6] = {ZEBRA_ROUTE_OSPF6, 110},
74 [ZEBRA_ROUTE_ISIS] = {ZEBRA_ROUTE_ISIS, 115},
75 [ZEBRA_ROUTE_BGP] = {ZEBRA_ROUTE_BGP, 20 /* IBGP is 200. */},
76 [ZEBRA_ROUTE_PIM] = {ZEBRA_ROUTE_PIM, 255},
77 [ZEBRA_ROUTE_EIGRP] = {ZEBRA_ROUTE_EIGRP, 90},
78 [ZEBRA_ROUTE_NHRP] = {ZEBRA_ROUTE_NHRP, 10},
79 [ZEBRA_ROUTE_HSLS] = {ZEBRA_ROUTE_HSLS, 255},
80 [ZEBRA_ROUTE_OLSR] = {ZEBRA_ROUTE_OLSR, 255},
81 [ZEBRA_ROUTE_TABLE] = {ZEBRA_ROUTE_TABLE, 150},
82 [ZEBRA_ROUTE_LDP] = {ZEBRA_ROUTE_LDP, 150},
83 [ZEBRA_ROUTE_VNC] = {ZEBRA_ROUTE_VNC, 20},
84 [ZEBRA_ROUTE_VNC_DIRECT] = {ZEBRA_ROUTE_VNC_DIRECT, 20},
85 [ZEBRA_ROUTE_VNC_DIRECT_RH] = {ZEBRA_ROUTE_VNC_DIRECT_RH, 20},
86 [ZEBRA_ROUTE_BGP_DIRECT] = {ZEBRA_ROUTE_BGP_DIRECT, 20},
87 [ZEBRA_ROUTE_BGP_DIRECT_EXT] = {ZEBRA_ROUTE_BGP_DIRECT_EXT, 20},
88 [ZEBRA_ROUTE_BABEL] = {ZEBRA_ROUTE_BABEL, 100},
89
90 /* no entry/default: 150 */
91 };
92
93 /* RPF lookup behaviour */
94 static enum multicast_mode ipv4_multicast_mode = MCAST_NO_CONFIG;
95
96
97 static void __attribute__((format(printf, 5, 6)))
98 _rnode_zlog(const char *_func, vrf_id_t vrf_id, struct route_node *rn,
99 int priority, const char *msgfmt, ...)
100 {
101 char buf[SRCDEST2STR_BUFFER + sizeof(" (MRIB)")];
102 char msgbuf[512];
103 va_list ap;
104
105 va_start(ap, msgfmt);
106 vsnprintf(msgbuf, sizeof(msgbuf), msgfmt, ap);
107 va_end(ap);
108
109 if (rn) {
110 rib_table_info_t *info = srcdest_rnode_table_info(rn);
111 srcdest_rnode2str(rn, buf, sizeof(buf));
112
113 if (info->safi == SAFI_MULTICAST)
114 strcat(buf, " (MRIB)");
115 } else {
116 snprintf(buf, sizeof(buf), "{(route_node *) NULL}");
117 }
118
119 zlog(priority, "%s: %d:%s: %s", _func, vrf_id, buf, msgbuf);
120 }
121
122 #define rnode_debug(node, vrf_id, ...) \
123 _rnode_zlog(__func__, vrf_id, node, LOG_DEBUG, __VA_ARGS__)
124 #define rnode_info(node, ...) \
125 _rnode_zlog(__func__, vrf_id, node, LOG_INFO, __VA_ARGS__)
126
127 uint8_t route_distance(int type)
128 {
129 uint8_t distance;
130
131 if ((unsigned)type >= array_size(route_info))
132 distance = 150;
133 else
134 distance = route_info[type].distance;
135
136 return distance;
137 }
138
139 int is_zebra_valid_kernel_table(u_int32_t table_id)
140 {
141 if ((table_id > ZEBRA_KERNEL_TABLE_MAX))
142 return 0;
143
144 #ifdef linux
145 if ((table_id == RT_TABLE_UNSPEC) || (table_id == RT_TABLE_LOCAL)
146 || (table_id == RT_TABLE_COMPAT))
147 return 0;
148 #endif
149
150 return 1;
151 }
152
153 int is_zebra_main_routing_table(u_int32_t table_id)
154 {
155 if ((table_id == RT_TABLE_MAIN)
156 || (table_id == zebrad.rtm_table_default))
157 return 1;
158 return 0;
159 }
160
161 int zebra_check_addr(struct prefix *p)
162 {
163 if (p->family == AF_INET) {
164 u_int32_t addr;
165
166 addr = p->u.prefix4.s_addr;
167 addr = ntohl(addr);
168
169 if (IPV4_NET127(addr) || IN_CLASSD(addr)
170 || IPV4_LINKLOCAL(addr))
171 return 0;
172 }
173 if (p->family == AF_INET6) {
174 if (IN6_IS_ADDR_LOOPBACK(&p->u.prefix6))
175 return 0;
176 if (IN6_IS_ADDR_LINKLOCAL(&p->u.prefix6))
177 return 0;
178 }
179 return 1;
180 }
181
182 /* Add nexthop to the end of a rib node's nexthop list */
183 void route_entry_nexthop_add(struct route_entry *re, struct nexthop *nexthop)
184 {
185 nexthop_add(&re->nexthop, nexthop);
186 re->nexthop_num++;
187 }
188
189
190 /**
191 * copy_nexthop - copy a nexthop to the rib structure.
192 */
193 void route_entry_copy_nexthops(struct route_entry *re, struct nexthop *nh)
194 {
195 assert(!re->nexthop);
196 copy_nexthops(&re->nexthop, nh, NULL);
197 for (struct nexthop *nexthop = nh; nexthop; nexthop = nexthop->next)
198 re->nexthop_num++;
199 }
200
201 /* Delete specified nexthop from the list. */
202 void route_entry_nexthop_delete(struct route_entry *re, struct nexthop *nexthop)
203 {
204 if (nexthop->next)
205 nexthop->next->prev = nexthop->prev;
206 if (nexthop->prev)
207 nexthop->prev->next = nexthop->next;
208 else
209 re->nexthop = nexthop->next;
210 re->nexthop_num--;
211 }
212
213
214 struct nexthop *route_entry_nexthop_ifindex_add(struct route_entry *re,
215 ifindex_t ifindex)
216 {
217 struct nexthop *nexthop;
218
219 nexthop = nexthop_new();
220 nexthop->type = NEXTHOP_TYPE_IFINDEX;
221 nexthop->ifindex = ifindex;
222
223 route_entry_nexthop_add(re, nexthop);
224
225 return nexthop;
226 }
227
228 struct nexthop *route_entry_nexthop_ipv4_add(struct route_entry *re,
229 struct in_addr *ipv4,
230 struct in_addr *src)
231 {
232 struct nexthop *nexthop;
233
234 nexthop = nexthop_new();
235 nexthop->type = NEXTHOP_TYPE_IPV4;
236 nexthop->gate.ipv4 = *ipv4;
237 if (src)
238 nexthop->src.ipv4 = *src;
239
240 route_entry_nexthop_add(re, nexthop);
241
242 return nexthop;
243 }
244
245 struct nexthop *route_entry_nexthop_ipv4_ifindex_add(struct route_entry *re,
246 struct in_addr *ipv4,
247 struct in_addr *src,
248 ifindex_t ifindex)
249 {
250 struct nexthop *nexthop;
251 struct interface *ifp;
252
253 nexthop = nexthop_new();
254 nexthop->type = NEXTHOP_TYPE_IPV4_IFINDEX;
255 nexthop->gate.ipv4 = *ipv4;
256 if (src)
257 nexthop->src.ipv4 = *src;
258 nexthop->ifindex = ifindex;
259 ifp = if_lookup_by_index(nexthop->ifindex, re->nh_vrf_id);
260 /*Pending: need to think if null ifp here is ok during bootup?
261 There was a crash because ifp here was coming to be NULL */
262 if (ifp)
263 if (connected_is_unnumbered(ifp) ||
264 CHECK_FLAG(re->flags, ZEBRA_FLAG_EVPN_ROUTE)) {
265 SET_FLAG(nexthop->flags, NEXTHOP_FLAG_ONLINK);
266 }
267
268 route_entry_nexthop_add(re, nexthop);
269
270 return nexthop;
271 }
272
273 struct nexthop *route_entry_nexthop_ipv6_add(struct route_entry *re,
274 struct in6_addr *ipv6)
275 {
276 struct nexthop *nexthop;
277
278 nexthop = nexthop_new();
279 nexthop->type = NEXTHOP_TYPE_IPV6;
280 nexthop->gate.ipv6 = *ipv6;
281
282 route_entry_nexthop_add(re, nexthop);
283
284 return nexthop;
285 }
286
287 struct nexthop *route_entry_nexthop_ipv6_ifindex_add(struct route_entry *re,
288 struct in6_addr *ipv6,
289 ifindex_t ifindex)
290 {
291 struct nexthop *nexthop;
292
293 nexthop = nexthop_new();
294 nexthop->type = NEXTHOP_TYPE_IPV6_IFINDEX;
295 nexthop->gate.ipv6 = *ipv6;
296 nexthop->ifindex = ifindex;
297
298 route_entry_nexthop_add(re, nexthop);
299
300 return nexthop;
301 }
302
303 struct nexthop *route_entry_nexthop_blackhole_add(struct route_entry *re,
304 enum blackhole_type bh_type)
305 {
306 struct nexthop *nexthop;
307
308 nexthop = nexthop_new();
309 nexthop->type = NEXTHOP_TYPE_BLACKHOLE;
310 nexthop->bh_type = bh_type;
311
312 route_entry_nexthop_add(re, nexthop);
313
314 return nexthop;
315 }
316
317 static void nexthop_set_resolved(afi_t afi, struct nexthop *newhop,
318 struct nexthop *nexthop)
319 {
320 struct nexthop *resolved_hop;
321
322 resolved_hop = nexthop_new();
323 SET_FLAG(resolved_hop->flags, NEXTHOP_FLAG_ACTIVE);
324
325 switch (newhop->type) {
326 case NEXTHOP_TYPE_IPV4:
327 case NEXTHOP_TYPE_IPV4_IFINDEX:
328 /* If the resolving route specifies a gateway, use it */
329 resolved_hop->type = newhop->type;
330 resolved_hop->gate.ipv4 = newhop->gate.ipv4;
331
332 if (newhop->ifindex) {
333 resolved_hop->type = NEXTHOP_TYPE_IPV4_IFINDEX;
334 resolved_hop->ifindex = newhop->ifindex;
335 if (newhop->flags & NEXTHOP_FLAG_ONLINK)
336 resolved_hop->flags |= NEXTHOP_FLAG_ONLINK;
337 }
338 break;
339 case NEXTHOP_TYPE_IPV6:
340 case NEXTHOP_TYPE_IPV6_IFINDEX:
341 resolved_hop->type = newhop->type;
342 resolved_hop->gate.ipv6 = newhop->gate.ipv6;
343
344 if (newhop->ifindex) {
345 resolved_hop->type = NEXTHOP_TYPE_IPV6_IFINDEX;
346 resolved_hop->ifindex = newhop->ifindex;
347 }
348 break;
349 case NEXTHOP_TYPE_IFINDEX:
350 /* If the resolving route is an interface route,
351 * it means the gateway we are looking up is connected
352 * to that interface. (The actual network is _not_ onlink).
353 * Therefore, the resolved route should have the original
354 * gateway as nexthop as it is directly connected.
355 *
356 * On Linux, we have to set the onlink netlink flag because
357 * otherwise, the kernel won't accept the route.
358 */
359 resolved_hop->flags |= NEXTHOP_FLAG_ONLINK;
360 if (afi == AFI_IP) {
361 resolved_hop->type = NEXTHOP_TYPE_IPV4_IFINDEX;
362 resolved_hop->gate.ipv4 = nexthop->gate.ipv4;
363 } else if (afi == AFI_IP6) {
364 resolved_hop->type = NEXTHOP_TYPE_IPV6_IFINDEX;
365 resolved_hop->gate.ipv6 = nexthop->gate.ipv6;
366 }
367 resolved_hop->ifindex = newhop->ifindex;
368 break;
369 case NEXTHOP_TYPE_BLACKHOLE:
370 resolved_hop->type = NEXTHOP_TYPE_BLACKHOLE;
371 resolved_hop->bh_type = nexthop->bh_type;
372 break;
373 }
374
375 /* Copy labels of the resolved route */
376 if (newhop->nh_label)
377 nexthop_add_labels(resolved_hop, newhop->nh_label_type,
378 newhop->nh_label->num_labels,
379 &newhop->nh_label->label[0]);
380
381 resolved_hop->rparent = nexthop;
382 nexthop_add(&nexthop->resolved, resolved_hop);
383 }
384
385 /* If force flag is not set, do not modify falgs at all for uninstall
386 the route from FIB. */
387 static int nexthop_active(afi_t afi, struct route_entry *re,
388 struct nexthop *nexthop, int set,
389 struct route_node *top)
390 {
391 struct prefix p;
392 struct route_table *table;
393 struct route_node *rn;
394 struct route_entry *match = NULL;
395 int resolved;
396 struct nexthop *newhop;
397 struct interface *ifp;
398 rib_dest_t *dest;
399
400 if ((nexthop->type == NEXTHOP_TYPE_IPV4)
401 || nexthop->type == NEXTHOP_TYPE_IPV6)
402 nexthop->ifindex = 0;
403
404 if (set) {
405 UNSET_FLAG(nexthop->flags, NEXTHOP_FLAG_RECURSIVE);
406 zebra_deregister_rnh_static_nexthops(re->nh_vrf_id,
407 nexthop->resolved, top);
408 nexthops_free(nexthop->resolved);
409 nexthop->resolved = NULL;
410 re->nexthop_mtu = 0;
411 }
412
413 /* Skip nexthops that have been filtered out due to route-map */
414 /* The nexthops are specific to this route and so the same */
415 /* nexthop for a different route may not have this flag set */
416 if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_FILTERED))
417 return 0;
418
419 /*
420 * Check to see if we should trust the passed in information
421 * for UNNUMBERED interfaces as that we won't find the GW
422 * address in the routing table.
423 */
424 if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_ONLINK)) {
425 ifp = if_lookup_by_index(nexthop->ifindex, re->nh_vrf_id);
426 if (ifp && connected_is_unnumbered(ifp)) {
427 if (if_is_operative(ifp))
428 return 1;
429 else
430 return 0;
431 } else
432 return 0;
433 }
434
435 /* Make lookup prefix. */
436 memset(&p, 0, sizeof(struct prefix));
437 switch (afi) {
438 case AFI_IP:
439 p.family = AF_INET;
440 p.prefixlen = IPV4_MAX_PREFIXLEN;
441 p.u.prefix4 = nexthop->gate.ipv4;
442 break;
443 case AFI_IP6:
444 p.family = AF_INET6;
445 p.prefixlen = IPV6_MAX_PREFIXLEN;
446 p.u.prefix6 = nexthop->gate.ipv6;
447 break;
448 default:
449 assert(afi != AFI_IP && afi != AFI_IP6);
450 break;
451 }
452 /* Lookup table. */
453 table = zebra_vrf_table(afi, SAFI_UNICAST, re->nh_vrf_id);
454 if (!table)
455 return 0;
456
457 rn = route_node_match(table, (struct prefix *)&p);
458 while (rn) {
459 route_unlock_node(rn);
460
461 /* Lookup should halt if we've matched against ourselves ('top',
462 * if specified) - i.e., we cannot have a nexthop NH1 is
463 * resolved by a route NH1. The exception is if the route is a
464 * host route.
465 */
466 if (top && rn == top)
467 if (((afi == AFI_IP) && (rn->p.prefixlen != 32)) ||
468 ((afi == AFI_IP6) && (rn->p.prefixlen != 128)))
469 return 0;
470
471 /* Pick up selected route. */
472 /* However, do not resolve over default route unless explicitly
473 * allowed. */
474 if (is_default_prefix(&rn->p)
475 && !nh_resolve_via_default(p.family))
476 return 0;
477
478 dest = rib_dest_from_rnode(rn);
479 if (dest && dest->selected_fib &&
480 !CHECK_FLAG(dest->selected_fib->status,
481 ROUTE_ENTRY_REMOVED) &&
482 dest->selected_fib->type != ZEBRA_ROUTE_TABLE)
483 match = dest->selected_fib;
484
485 /* If there is no selected route or matched route is EGP, go up
486 tree. */
487 if (!match) {
488 do {
489 rn = rn->parent;
490 } while (rn && rn->info == NULL);
491 if (rn)
492 route_lock_node(rn);
493
494 continue;
495 }
496
497 if (match->type == ZEBRA_ROUTE_CONNECT) {
498 /* Directly point connected route. */
499 newhop = match->nexthop;
500 if (newhop) {
501 if (nexthop->type == NEXTHOP_TYPE_IPV4
502 || nexthop->type == NEXTHOP_TYPE_IPV6)
503 nexthop->ifindex = newhop->ifindex;
504 }
505 return 1;
506 } else if (CHECK_FLAG(re->flags, ZEBRA_FLAG_INTERNAL)) {
507 resolved = 0;
508 for (ALL_NEXTHOPS(match->nexthop, newhop)) {
509 if (!CHECK_FLAG(newhop->flags,
510 NEXTHOP_FLAG_FIB))
511 continue;
512 if (CHECK_FLAG(newhop->flags,
513 NEXTHOP_FLAG_RECURSIVE))
514 continue;
515
516 if (set) {
517 SET_FLAG(nexthop->flags,
518 NEXTHOP_FLAG_RECURSIVE);
519 SET_FLAG(re->status,
520 ROUTE_ENTRY_NEXTHOPS_CHANGED);
521 nexthop_set_resolved(afi, newhop,
522 nexthop);
523 }
524 resolved = 1;
525 }
526 if (resolved && set)
527 re->nexthop_mtu = match->mtu;
528 return resolved;
529 } else if (re->type == ZEBRA_ROUTE_STATIC) {
530 resolved = 0;
531 for (ALL_NEXTHOPS(match->nexthop, newhop)) {
532 if (!CHECK_FLAG(newhop->flags,
533 NEXTHOP_FLAG_FIB))
534 continue;
535
536 if (set) {
537 SET_FLAG(nexthop->flags,
538 NEXTHOP_FLAG_RECURSIVE);
539 nexthop_set_resolved(afi, newhop,
540 nexthop);
541 }
542 resolved = 1;
543 }
544 if (resolved && set)
545 re->nexthop_mtu = match->mtu;
546 return resolved;
547 } else {
548 return 0;
549 }
550 }
551 return 0;
552 }
553
554 struct route_entry *rib_match(afi_t afi, safi_t safi, vrf_id_t vrf_id,
555 union g_addr *addr, struct route_node **rn_out)
556 {
557 struct prefix p;
558 struct route_table *table;
559 struct route_node *rn;
560 struct route_entry *match = NULL;
561 struct nexthop *newhop;
562
563 /* Lookup table. */
564 table = zebra_vrf_table(afi, safi, vrf_id);
565 if (!table)
566 return 0;
567
568 memset(&p, 0, sizeof(struct prefix));
569 p.family = afi;
570 if (afi == AFI_IP) {
571 p.u.prefix4 = addr->ipv4;
572 p.prefixlen = IPV4_MAX_PREFIXLEN;
573 } else {
574 p.u.prefix6 = addr->ipv6;
575 p.prefixlen = IPV6_MAX_PREFIXLEN;
576 }
577
578 rn = route_node_match(table, (struct prefix *)&p);
579
580 while (rn) {
581 rib_dest_t *dest;
582
583 route_unlock_node(rn);
584
585 dest = rib_dest_from_rnode(rn);
586 if (dest && dest->selected_fib &&
587 !CHECK_FLAG(dest->selected_fib->status, ROUTE_ENTRY_REMOVED))
588 match = dest->selected_fib;
589
590 /* If there is no selected route or matched route is EGP, go up
591 tree. */
592 if (!match) {
593 do {
594 rn = rn->parent;
595 } while (rn && rn->info == NULL);
596 if (rn)
597 route_lock_node(rn);
598 } else {
599 if (match->type != ZEBRA_ROUTE_CONNECT) {
600 int found = 0;
601 for (ALL_NEXTHOPS(match->nexthop, newhop))
602 if (CHECK_FLAG(newhop->flags,
603 NEXTHOP_FLAG_FIB)) {
604 found = 1;
605 break;
606 }
607 if (!found)
608 return NULL;
609 }
610
611 if (rn_out)
612 *rn_out = rn;
613 return match;
614 }
615 }
616 return NULL;
617 }
618
619 struct route_entry *rib_match_ipv4_multicast(vrf_id_t vrf_id,
620 struct in_addr addr,
621 struct route_node **rn_out)
622 {
623 struct route_entry *re = NULL, *mre = NULL, *ure = NULL;
624 struct route_node *m_rn = NULL, *u_rn = NULL;
625 union g_addr gaddr = {.ipv4 = addr};
626
627 switch (ipv4_multicast_mode) {
628 case MCAST_MRIB_ONLY:
629 return rib_match(AFI_IP, SAFI_MULTICAST, vrf_id, &gaddr,
630 rn_out);
631 case MCAST_URIB_ONLY:
632 return rib_match(AFI_IP, SAFI_UNICAST, vrf_id, &gaddr, rn_out);
633 case MCAST_NO_CONFIG:
634 case MCAST_MIX_MRIB_FIRST:
635 re = mre = rib_match(AFI_IP, SAFI_MULTICAST, vrf_id, &gaddr,
636 &m_rn);
637 if (!mre)
638 re = ure = rib_match(AFI_IP, SAFI_UNICAST, vrf_id,
639 &gaddr, &u_rn);
640 break;
641 case MCAST_MIX_DISTANCE:
642 mre = rib_match(AFI_IP, SAFI_MULTICAST, vrf_id, &gaddr, &m_rn);
643 ure = rib_match(AFI_IP, SAFI_UNICAST, vrf_id, &gaddr, &u_rn);
644 if (mre && ure)
645 re = ure->distance < mre->distance ? ure : mre;
646 else if (mre)
647 re = mre;
648 else if (ure)
649 re = ure;
650 break;
651 case MCAST_MIX_PFXLEN:
652 mre = rib_match(AFI_IP, SAFI_MULTICAST, vrf_id, &gaddr, &m_rn);
653 ure = rib_match(AFI_IP, SAFI_UNICAST, vrf_id, &gaddr, &u_rn);
654 if (mre && ure)
655 re = u_rn->p.prefixlen > m_rn->p.prefixlen ? ure : mre;
656 else if (mre)
657 re = mre;
658 else if (ure)
659 re = ure;
660 break;
661 }
662
663 if (rn_out)
664 *rn_out = (re == mre) ? m_rn : u_rn;
665
666 if (IS_ZEBRA_DEBUG_RIB) {
667 char buf[BUFSIZ];
668 inet_ntop(AF_INET, &addr, buf, BUFSIZ);
669
670 zlog_debug("%s: %s: found %s, using %s", __func__, buf,
671 mre ? (ure ? "MRIB+URIB" : "MRIB")
672 : ure ? "URIB" : "nothing",
673 re == ure ? "URIB" : re == mre ? "MRIB" : "none");
674 }
675 return re;
676 }
677
678 void multicast_mode_ipv4_set(enum multicast_mode mode)
679 {
680 if (IS_ZEBRA_DEBUG_RIB)
681 zlog_debug("%s: multicast lookup mode set (%d)", __func__,
682 mode);
683 ipv4_multicast_mode = mode;
684 }
685
686 enum multicast_mode multicast_mode_ipv4_get(void)
687 {
688 return ipv4_multicast_mode;
689 }
690
691 struct route_entry *rib_lookup_ipv4(struct prefix_ipv4 *p, vrf_id_t vrf_id)
692 {
693 struct route_table *table;
694 struct route_node *rn;
695 struct route_entry *match = NULL;
696 struct nexthop *nexthop;
697 rib_dest_t *dest;
698
699 /* Lookup table. */
700 table = zebra_vrf_table(AFI_IP, SAFI_UNICAST, vrf_id);
701 if (!table)
702 return 0;
703
704 rn = route_node_lookup(table, (struct prefix *)p);
705
706 /* No route for this prefix. */
707 if (!rn)
708 return NULL;
709
710 /* Unlock node. */
711 route_unlock_node(rn);
712 dest = rib_dest_from_rnode(rn);
713
714 if (dest && dest->selected_fib &&
715 !CHECK_FLAG(dest->selected_fib->status, ROUTE_ENTRY_REMOVED))
716 match = dest->selected_fib;
717
718 if (!match)
719 return NULL;
720
721 if (match->type == ZEBRA_ROUTE_CONNECT)
722 return match;
723
724 for (ALL_NEXTHOPS(match->nexthop, nexthop))
725 if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_FIB))
726 return match;
727
728 return NULL;
729 }
730
731 /*
732 * This clone function, unlike its original rib_lookup_ipv4(), checks
733 * if specified IPv4 route record (prefix/mask -> gate) exists in
734 * the whole RIB and has ROUTE_ENTRY_SELECTED_FIB set.
735 *
736 * Return values:
737 * -1: error
738 * 0: exact match found
739 * 1: a match was found with a different gate
740 * 2: connected route found
741 * 3: no matches found
742 */
743 int rib_lookup_ipv4_route(struct prefix_ipv4 *p, union sockunion *qgate,
744 vrf_id_t vrf_id)
745 {
746 struct route_table *table;
747 struct route_node *rn;
748 struct route_entry *match = NULL;
749 struct nexthop *nexthop;
750 int nexthops_active;
751 rib_dest_t *dest;
752
753 /* Lookup table. */
754 table = zebra_vrf_table(AFI_IP, SAFI_UNICAST, vrf_id);
755 if (!table)
756 return ZEBRA_RIB_LOOKUP_ERROR;
757
758 /* Scan the RIB table for exactly matching RIB entry. */
759 rn = route_node_lookup(table, (struct prefix *)p);
760
761 /* No route for this prefix. */
762 if (!rn)
763 return ZEBRA_RIB_NOTFOUND;
764
765 /* Unlock node. */
766 route_unlock_node(rn);
767 dest = rib_dest_from_rnode(rn);
768
769 /* Find out if a "selected" RR for the discovered RIB entry exists ever.
770 */
771 if (dest && dest->selected_fib &&
772 !CHECK_FLAG(dest->selected_fib->status, ROUTE_ENTRY_REMOVED))
773 match = dest->selected_fib;
774
775 /* None such found :( */
776 if (!match)
777 return ZEBRA_RIB_NOTFOUND;
778
779 if (match->type == ZEBRA_ROUTE_CONNECT)
780 return ZEBRA_RIB_FOUND_CONNECTED;
781
782 /* Ok, we have a cood candidate, let's check it's nexthop list... */
783 nexthops_active = 0;
784 for (ALL_NEXTHOPS(match->nexthop, nexthop))
785 if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_FIB)) {
786 nexthops_active = 1;
787 if (nexthop->gate.ipv4.s_addr == sockunion2ip(qgate))
788 return ZEBRA_RIB_FOUND_EXACT;
789 if (IS_ZEBRA_DEBUG_RIB) {
790 char gate_buf[INET_ADDRSTRLEN],
791 qgate_buf[INET_ADDRSTRLEN];
792 inet_ntop(AF_INET, &nexthop->gate.ipv4.s_addr,
793 gate_buf, INET_ADDRSTRLEN);
794 inet_ntop(AF_INET, &sockunion2ip(qgate),
795 qgate_buf, INET_ADDRSTRLEN);
796 zlog_debug("%s: qgate == %s, %s == %s",
797 __func__, qgate_buf,
798 nexthop->rparent ? "rgate" : "gate",
799 gate_buf);
800 }
801 }
802
803 if (nexthops_active)
804 return ZEBRA_RIB_FOUND_NOGATE;
805
806 return ZEBRA_RIB_NOTFOUND;
807 }
808
809 #define RIB_SYSTEM_ROUTE(R) \
810 ((R)->type == ZEBRA_ROUTE_KERNEL || (R)->type == ZEBRA_ROUTE_CONNECT)
811
812 /* This function verifies reachability of one given nexthop, which can be
813 * numbered or unnumbered, IPv4 or IPv6. The result is unconditionally stored
814 * in nexthop->flags field. If the 4th parameter, 'set', is non-zero,
815 * nexthop->ifindex will be updated appropriately as well.
816 * An existing route map can turn (otherwise active) nexthop into inactive, but
817 * not vice versa.
818 *
819 * The return value is the final value of 'ACTIVE' flag.
820 */
821
822 static unsigned nexthop_active_check(struct route_node *rn,
823 struct route_entry *re,
824 struct nexthop *nexthop, int set)
825 {
826 struct interface *ifp;
827 route_map_result_t ret = RMAP_MATCH;
828 int family;
829 char buf[SRCDEST2STR_BUFFER];
830 struct prefix *p, *src_p;
831 srcdest_rnode_prefixes(rn, &p, &src_p);
832
833 if (rn->p.family == AF_INET)
834 family = AFI_IP;
835 else if (rn->p.family == AF_INET6)
836 family = AFI_IP6;
837 else
838 family = 0;
839 switch (nexthop->type) {
840 case NEXTHOP_TYPE_IFINDEX:
841 ifp = if_lookup_by_index(nexthop->ifindex, re->nh_vrf_id);
842 if (ifp && if_is_operative(ifp))
843 SET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
844 else
845 UNSET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
846 break;
847 case NEXTHOP_TYPE_IPV4:
848 case NEXTHOP_TYPE_IPV4_IFINDEX:
849 family = AFI_IP;
850 if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_EVPN_RVTEP))
851 SET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
852 else if (nexthop_active(AFI_IP, re, nexthop, set, rn))
853 SET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
854 else
855 UNSET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
856 break;
857 case NEXTHOP_TYPE_IPV6:
858 family = AFI_IP6;
859 if (nexthop_active(AFI_IP6, re, nexthop, set, rn))
860 SET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
861 else
862 UNSET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
863 break;
864 case NEXTHOP_TYPE_IPV6_IFINDEX:
865 /* RFC 5549, v4 prefix with v6 NH */
866 if (rn->p.family != AF_INET)
867 family = AFI_IP6;
868 if (IN6_IS_ADDR_LINKLOCAL(&nexthop->gate.ipv6)) {
869 ifp = if_lookup_by_index(nexthop->ifindex,
870 re->nh_vrf_id);
871 if (ifp && if_is_operative(ifp))
872 SET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
873 else
874 UNSET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
875 } else {
876 if (nexthop_active(AFI_IP6, re, nexthop, set, rn))
877 SET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
878 else
879 UNSET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
880 }
881 break;
882 case NEXTHOP_TYPE_BLACKHOLE:
883 SET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
884 break;
885 default:
886 break;
887 }
888 if (!CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE))
889 return 0;
890
891 /* XXX: What exactly do those checks do? Do we support
892 * e.g. IPv4 routes with IPv6 nexthops or vice versa? */
893 if (RIB_SYSTEM_ROUTE(re) || (family == AFI_IP && p->family != AF_INET)
894 || (family == AFI_IP6 && p->family != AF_INET6))
895 return CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
896
897 /* The original code didn't determine the family correctly
898 * e.g. for NEXTHOP_TYPE_IFINDEX. Retrieve the correct afi
899 * from the rib_table_info in those cases.
900 * Possibly it may be better to use only the rib_table_info
901 * in every case.
902 */
903 if (!family) {
904 rib_table_info_t *info;
905
906 info = srcdest_rnode_table_info(rn);
907 family = info->afi;
908 }
909
910 memset(&nexthop->rmap_src.ipv6, 0, sizeof(union g_addr));
911
912 /* It'll get set if required inside */
913 ret = zebra_route_map_check(family, re->type, p, nexthop, re->nh_vrf_id,
914 re->tag);
915 if (ret == RMAP_DENYMATCH) {
916 if (IS_ZEBRA_DEBUG_RIB) {
917 srcdest_rnode2str(rn, buf, sizeof(buf));
918 zlog_debug(
919 "%u:%s: Filtering out with NH out %s due to route map",
920 re->vrf_id, buf,
921 ifindex2ifname(nexthop->ifindex,
922 re->nh_vrf_id));
923 }
924 UNSET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
925 }
926 return CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
927 }
928
929 /* Iterate over all nexthops of the given RIB entry and refresh their
930 * ACTIVE flag. re->nexthop_active_num is updated accordingly. If any
931 * nexthop is found to toggle the ACTIVE flag, the whole re structure
932 * is flagged with ROUTE_ENTRY_CHANGED. The 4th 'set' argument is
933 * transparently passed to nexthop_active_check().
934 *
935 * Return value is the new number of active nexthops.
936 */
937
938 static int nexthop_active_update(struct route_node *rn, struct route_entry *re,
939 int set)
940 {
941 struct nexthop *nexthop;
942 union g_addr prev_src;
943 unsigned int prev_active, new_active, old_num_nh;
944 ifindex_t prev_index;
945 old_num_nh = re->nexthop_active_num;
946
947 re->nexthop_active_num = 0;
948 UNSET_FLAG(re->status, ROUTE_ENTRY_CHANGED);
949
950 for (nexthop = re->nexthop; nexthop; nexthop = nexthop->next) {
951 /* No protocol daemon provides src and so we're skipping
952 * tracking it */
953 prev_src = nexthop->rmap_src;
954 prev_active = CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
955 prev_index = nexthop->ifindex;
956 if ((new_active = nexthop_active_check(rn, re, nexthop, set)))
957 re->nexthop_active_num++;
958 /* Don't allow src setting on IPv6 addr for now */
959 if (prev_active != new_active || prev_index != nexthop->ifindex
960 || ((nexthop->type >= NEXTHOP_TYPE_IFINDEX
961 && nexthop->type < NEXTHOP_TYPE_IPV6)
962 && prev_src.ipv4.s_addr
963 != nexthop->rmap_src.ipv4.s_addr)
964 || ((nexthop->type >= NEXTHOP_TYPE_IPV6
965 && nexthop->type < NEXTHOP_TYPE_BLACKHOLE)
966 && !(IPV6_ADDR_SAME(&prev_src.ipv6,
967 &nexthop->rmap_src.ipv6)))) {
968 SET_FLAG(re->status, ROUTE_ENTRY_CHANGED);
969 SET_FLAG(re->status, ROUTE_ENTRY_NEXTHOPS_CHANGED);
970 }
971 }
972
973 if (old_num_nh != re->nexthop_active_num)
974 SET_FLAG(re->status, ROUTE_ENTRY_CHANGED);
975
976 if (CHECK_FLAG(re->status, ROUTE_ENTRY_CHANGED)) {
977 SET_FLAG(re->status, ROUTE_ENTRY_NEXTHOPS_CHANGED);
978 }
979
980 return re->nexthop_active_num;
981 }
982
983 /*
984 * Is this RIB labeled-unicast? It must be of type BGP and all paths
985 * (nexthops) must have a label.
986 */
987 int zebra_rib_labeled_unicast(struct route_entry *re)
988 {
989 struct nexthop *nexthop = NULL;
990
991 if (re->type != ZEBRA_ROUTE_BGP)
992 return 0;
993
994 for (ALL_NEXTHOPS(re->nexthop, nexthop))
995 if (!nexthop->nh_label || !nexthop->nh_label->num_labels)
996 return 0;
997
998 return 1;
999 }
1000
1001 void kernel_route_rib_pass_fail(struct route_node *rn, struct prefix *p,
1002 struct route_entry *re,
1003 enum southbound_results res)
1004 {
1005 struct nexthop *nexthop;
1006 char buf[PREFIX_STRLEN];
1007 rib_dest_t *dest;
1008
1009 dest = rib_dest_from_rnode(rn);
1010
1011 switch (res) {
1012 case SOUTHBOUND_INSTALL_SUCCESS:
1013 dest->selected_fib = re;
1014 for (ALL_NEXTHOPS(re->nexthop, nexthop)) {
1015 if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
1016 continue;
1017
1018 if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE))
1019 SET_FLAG(nexthop->flags, NEXTHOP_FLAG_FIB);
1020 else
1021 UNSET_FLAG(nexthop->flags, NEXTHOP_FLAG_FIB);
1022 }
1023 zsend_route_notify_owner(re->type, re->instance, re->vrf_id,
1024 p, ZAPI_ROUTE_INSTALLED);
1025 break;
1026 case SOUTHBOUND_INSTALL_FAILURE:
1027 /*
1028 * I am not sure this is the right thing to do here
1029 * but the code always set selected_fib before
1030 * this assignment was moved here.
1031 */
1032 dest->selected_fib = re;
1033
1034 zsend_route_notify_owner(re->type, re->instance, re->vrf_id,
1035 p, ZAPI_ROUTE_FAIL_INSTALL);
1036 zlog_warn("%u:%s: Route install failed", re->vrf_id,
1037 prefix2str(p, buf, sizeof(buf)));
1038 break;
1039 case SOUTHBOUND_DELETE_SUCCESS:
1040 /*
1041 * The case where selected_fib is not re is
1042 * when we have received a system route
1043 * that is overriding our installed route
1044 * as such we should leave the selected_fib
1045 * pointer alone
1046 */
1047 if (dest->selected_fib == re)
1048 dest->selected_fib = NULL;
1049 for (ALL_NEXTHOPS(re->nexthop, nexthop))
1050 UNSET_FLAG(nexthop->flags, NEXTHOP_FLAG_FIB);
1051 break;
1052 case SOUTHBOUND_DELETE_FAILURE:
1053 /*
1054 * Should we set this to NULL if the
1055 * delete fails?
1056 */
1057 dest->selected_fib = NULL;
1058 zlog_warn("%u:%s: Route Deletion failure", re->vrf_id,
1059 prefix2str(p, buf, sizeof(buf)));
1060 break;
1061 }
1062 }
1063
1064 /* Update flag indicates whether this is a "replace" or not. Currently, this
1065 * is only used for IPv4.
1066 */
1067 void rib_install_kernel(struct route_node *rn, struct route_entry *re,
1068 struct route_entry *old)
1069 {
1070 struct nexthop *nexthop;
1071 rib_table_info_t *info = srcdest_rnode_table_info(rn);
1072 struct prefix *p, *src_p;
1073 struct zebra_vrf *zvrf = vrf_info_lookup(re->vrf_id);
1074
1075 srcdest_rnode_prefixes(rn, &p, &src_p);
1076
1077 if (info->safi != SAFI_UNICAST) {
1078 for (ALL_NEXTHOPS(re->nexthop, nexthop))
1079 SET_FLAG(nexthop->flags, NEXTHOP_FLAG_FIB);
1080 return;
1081 } else {
1082 struct nexthop *prev;
1083
1084 for (ALL_NEXTHOPS(re->nexthop, nexthop)) {
1085 UNSET_FLAG (nexthop->flags, NEXTHOP_FLAG_DUPLICATE);
1086 for (ALL_NEXTHOPS(re->nexthop, prev)) {
1087 if (prev == nexthop)
1088 break;
1089 if (nexthop_same_firsthop (nexthop, prev))
1090 {
1091 SET_FLAG (nexthop->flags, NEXTHOP_FLAG_DUPLICATE);
1092 break;
1093 }
1094 }
1095 }
1096 }
1097
1098 /*
1099 * If this is a replace to a new RE let the originator of the RE
1100 * know that they've lost
1101 */
1102 if (old && old != re)
1103 zsend_route_notify_owner(old->type, old->instance,
1104 old->vrf_id, p,
1105 ZAPI_ROUTE_BETTER_ADMIN_WON);
1106
1107 /*
1108 * Make sure we update the FPM any time we send new information to
1109 * the kernel.
1110 */
1111 hook_call(rib_update, rn, "installing in kernel");
1112 kernel_route_rib(rn, p, src_p, old, re);
1113 zvrf->installs++;
1114
1115 return;
1116 }
1117
1118 /* Uninstall the route from kernel. */
1119 void rib_uninstall_kernel(struct route_node *rn, struct route_entry *re)
1120 {
1121 struct nexthop *nexthop;
1122 rib_table_info_t *info = srcdest_rnode_table_info(rn);
1123 struct prefix *p, *src_p;
1124 struct zebra_vrf *zvrf = vrf_info_lookup(re->vrf_id);
1125
1126 srcdest_rnode_prefixes(rn, &p, &src_p);
1127
1128 if (info->safi != SAFI_UNICAST) {
1129 for (ALL_NEXTHOPS(re->nexthop, nexthop))
1130 UNSET_FLAG(nexthop->flags, NEXTHOP_FLAG_FIB);
1131 return;
1132 }
1133
1134 /*
1135 * Make sure we update the FPM any time we send new information to
1136 * the kernel.
1137 */
1138 hook_call(rib_update, rn, "uninstalling from kernel");
1139 kernel_route_rib(rn, p, src_p, re, NULL);
1140 zvrf->removals++;
1141
1142 return;
1143 }
1144
1145 /* Uninstall the route from kernel. */
1146 static void rib_uninstall(struct route_node *rn, struct route_entry *re)
1147 {
1148 rib_table_info_t *info = srcdest_rnode_table_info(rn);
1149 rib_dest_t *dest = rib_dest_from_rnode(rn);
1150
1151 if (dest && dest->selected_fib == re) {
1152 if (info->safi == SAFI_UNICAST)
1153 hook_call(rib_update, rn, "rib_uninstall");
1154
1155 if (!RIB_SYSTEM_ROUTE(re))
1156 rib_uninstall_kernel(rn, re);
1157
1158 /* If labeled-unicast route, uninstall transit LSP. */
1159 if (zebra_rib_labeled_unicast(re))
1160 zebra_mpls_lsp_uninstall(info->zvrf, rn, re);
1161 }
1162
1163 if (CHECK_FLAG(re->flags, ZEBRA_FLAG_SELECTED)) {
1164 struct prefix *p, *src_p;
1165 srcdest_rnode_prefixes(rn, &p, &src_p);
1166
1167 redistribute_delete(p, src_p, re);
1168 UNSET_FLAG(re->flags, ZEBRA_FLAG_SELECTED);
1169 }
1170 }
1171
1172 /*
1173 * rib_can_delete_dest
1174 *
1175 * Returns TRUE if the given dest can be deleted from the table.
1176 */
1177 static int rib_can_delete_dest(rib_dest_t *dest)
1178 {
1179 if (dest->routes) {
1180 return 0;
1181 }
1182
1183 /*
1184 * Don't delete the dest if we have to update the FPM about this
1185 * prefix.
1186 */
1187 if (CHECK_FLAG(dest->flags, RIB_DEST_UPDATE_FPM)
1188 || CHECK_FLAG(dest->flags, RIB_DEST_SENT_TO_FPM))
1189 return 0;
1190
1191 return 1;
1192 }
1193
1194 /*
1195 * rib_gc_dest
1196 *
1197 * Garbage collect the rib dest corresponding to the given route node
1198 * if appropriate.
1199 *
1200 * Returns TRUE if the dest was deleted, FALSE otherwise.
1201 */
1202 int rib_gc_dest(struct route_node *rn)
1203 {
1204 rib_dest_t *dest;
1205
1206 dest = rib_dest_from_rnode(rn);
1207 if (!dest)
1208 return 0;
1209
1210 if (!rib_can_delete_dest(dest))
1211 return 0;
1212
1213 if (IS_ZEBRA_DEBUG_RIB) {
1214 struct zebra_vrf *zvrf;
1215
1216 zvrf = rib_dest_vrf(dest);
1217 rnode_debug(rn, zvrf_id(zvrf), "removing dest from table");
1218 }
1219
1220 dest->rnode = NULL;
1221 XFREE(MTYPE_RIB_DEST, dest);
1222 rn->info = NULL;
1223
1224 /*
1225 * Release the one reference that we keep on the route node.
1226 */
1227 route_unlock_node(rn);
1228 return 1;
1229 }
1230
1231 static void rib_process_add_fib(struct zebra_vrf *zvrf, struct route_node *rn,
1232 struct route_entry *new)
1233 {
1234 rib_dest_t *dest = rib_dest_from_rnode(rn);
1235
1236 hook_call(rib_update, rn, "new route selected");
1237
1238 /* Update real nexthop. This may actually determine if nexthop is active
1239 * or not. */
1240 if (!nexthop_active_update(rn, new, 1)) {
1241 UNSET_FLAG(new->status, ROUTE_ENTRY_CHANGED);
1242 return;
1243 }
1244
1245 if (IS_ZEBRA_DEBUG_RIB) {
1246 char buf[SRCDEST2STR_BUFFER];
1247 srcdest_rnode2str(rn, buf, sizeof(buf));
1248 zlog_debug("%u:%s: Adding route rn %p, re %p (type %d)",
1249 zvrf_id(zvrf), buf, rn, new, new->type);
1250 }
1251
1252 /* If labeled-unicast route, install transit LSP. */
1253 if (zebra_rib_labeled_unicast(new))
1254 zebra_mpls_lsp_install(zvrf, rn, new);
1255
1256 if (!RIB_SYSTEM_ROUTE(new))
1257 rib_install_kernel(rn, new, NULL);
1258 else
1259 dest->selected_fib = new;
1260
1261 UNSET_FLAG(new->status, ROUTE_ENTRY_CHANGED);
1262 }
1263
1264 static void rib_process_del_fib(struct zebra_vrf *zvrf, struct route_node *rn,
1265 struct route_entry *old)
1266 {
1267 rib_dest_t *dest = rib_dest_from_rnode(rn);
1268 hook_call(rib_update, rn, "removing existing route");
1269
1270 /* Uninstall from kernel. */
1271 if (IS_ZEBRA_DEBUG_RIB) {
1272 char buf[SRCDEST2STR_BUFFER];
1273 srcdest_rnode2str(rn, buf, sizeof(buf));
1274 zlog_debug("%u:%s: Deleting route rn %p, re %p (type %d)",
1275 zvrf_id(zvrf), buf, rn, old, old->type);
1276 }
1277
1278 /* If labeled-unicast route, uninstall transit LSP. */
1279 if (zebra_rib_labeled_unicast(old))
1280 zebra_mpls_lsp_uninstall(zvrf, rn, old);
1281
1282 if (!RIB_SYSTEM_ROUTE(old))
1283 rib_uninstall_kernel(rn, old);
1284 else {
1285 /*
1286 * We are setting this to NULL here
1287 * because that is what we traditionally
1288 * have been doing. I am not positive
1289 * that this is the right thing to do
1290 * but let's leave the code alone
1291 * for the RIB_SYSTEM_ROUTE case
1292 */
1293 dest->selected_fib = NULL;
1294 }
1295
1296 /* Update nexthop for route, reset changed flag. */
1297 nexthop_active_update(rn, old, 1);
1298 UNSET_FLAG(old->status, ROUTE_ENTRY_CHANGED);
1299 }
1300
1301 static void rib_process_update_fib(struct zebra_vrf *zvrf,
1302 struct route_node *rn,
1303 struct route_entry *old,
1304 struct route_entry *new)
1305 {
1306 struct nexthop *nexthop = NULL;
1307 int nh_active = 0;
1308 rib_dest_t *dest = rib_dest_from_rnode(rn);
1309
1310 /*
1311 * We have to install or update if a new route has been selected or
1312 * something has changed.
1313 */
1314 if (new != old || CHECK_FLAG(new->status, ROUTE_ENTRY_CHANGED)) {
1315 hook_call(rib_update, rn, "updating existing route");
1316
1317 /* Update the nexthop; we could determine here that nexthop is
1318 * inactive. */
1319 if (nexthop_active_update(rn, new, 1))
1320 nh_active = 1;
1321
1322 /* If nexthop is active, install the selected route, if
1323 * appropriate. If
1324 * the install succeeds, cleanup flags for prior route, if
1325 * different from
1326 * newly selected.
1327 */
1328 if (nh_active) {
1329 if (IS_ZEBRA_DEBUG_RIB) {
1330 char buf[SRCDEST2STR_BUFFER];
1331 srcdest_rnode2str(rn, buf, sizeof(buf));
1332 if (new != old)
1333 zlog_debug(
1334 "%u:%s: Updating route rn %p, re %p (type %d) "
1335 "old %p (type %d)",
1336 zvrf_id(zvrf), buf, rn, new,
1337 new->type, old, old->type);
1338 else
1339 zlog_debug(
1340 "%u:%s: Updating route rn %p, re %p (type %d)",
1341 zvrf_id(zvrf), buf, rn, new,
1342 new->type);
1343 }
1344
1345 /* If labeled-unicast route, uninstall transit LSP. */
1346 if (zebra_rib_labeled_unicast(old))
1347 zebra_mpls_lsp_uninstall(zvrf, rn, old);
1348
1349 /* Non-system route should be installed. */
1350 if (!RIB_SYSTEM_ROUTE(new)) {
1351 /* If labeled-unicast route, install transit
1352 * LSP. */
1353 if (zebra_rib_labeled_unicast(new))
1354 zebra_mpls_lsp_install(zvrf, rn, new);
1355
1356 rib_install_kernel(rn, new, old);
1357 } else {
1358 /*
1359 * We do not need to install the
1360 * selected route because it
1361 * is already isntalled by
1362 * the system( ie not us )
1363 * so just mark it as winning
1364 * we do need to ensure that
1365 * if we uninstall a route
1366 * from ourselves we don't
1367 * over write this pointer
1368 */
1369 dest->selected_fib = NULL;
1370 }
1371 /* If install succeeded or system route, cleanup flags
1372 * for prior route. */
1373 if (new != old) {
1374 if (RIB_SYSTEM_ROUTE(new)) {
1375 if (!RIB_SYSTEM_ROUTE(old))
1376 rib_uninstall_kernel(rn, old);
1377 } else {
1378 for (nexthop = old->nexthop; nexthop;
1379 nexthop = nexthop->next)
1380 UNSET_FLAG(nexthop->flags,
1381 NEXTHOP_FLAG_FIB);
1382 }
1383 }
1384 }
1385
1386 /*
1387 * If nexthop for selected route is not active or install
1388 * failed, we
1389 * may need to uninstall and delete for redistribution.
1390 */
1391 if (!nh_active) {
1392 if (IS_ZEBRA_DEBUG_RIB) {
1393 char buf[SRCDEST2STR_BUFFER];
1394 srcdest_rnode2str(rn, buf, sizeof(buf));
1395 if (new != old)
1396 zlog_debug(
1397 "%u:%s: Deleting route rn %p, re %p (type %d) "
1398 "old %p (type %d) - %s",
1399 zvrf_id(zvrf), buf, rn, new,
1400 new->type, old, old->type,
1401 nh_active ? "install failed"
1402 : "nexthop inactive");
1403 else
1404 zlog_debug(
1405 "%u:%s: Deleting route rn %p, re %p (type %d) - %s",
1406 zvrf_id(zvrf), buf, rn, new,
1407 new->type,
1408 nh_active ? "install failed"
1409 : "nexthop inactive");
1410 }
1411
1412 /* If labeled-unicast route, uninstall transit LSP. */
1413 if (zebra_rib_labeled_unicast(old))
1414 zebra_mpls_lsp_uninstall(zvrf, rn, old);
1415
1416 if (!RIB_SYSTEM_ROUTE(old))
1417 rib_uninstall_kernel(rn, old);
1418 else
1419 dest->selected_fib = NULL;
1420 }
1421 } else {
1422 /*
1423 * Same route selected; check if in the FIB and if not,
1424 * re-install. This
1425 * is housekeeping code to deal with race conditions in kernel
1426 * with linux
1427 * netlink reporting interface up before IPv4 or IPv6 protocol
1428 * is ready
1429 * to add routes.
1430 */
1431 if (!RIB_SYSTEM_ROUTE(new)) {
1432 bool in_fib = false;
1433
1434 for (ALL_NEXTHOPS(new->nexthop, nexthop))
1435 if (CHECK_FLAG(nexthop->flags,
1436 NEXTHOP_FLAG_FIB)) {
1437 in_fib = true;
1438 break;
1439 }
1440 if (!in_fib)
1441 rib_install_kernel(rn, new, NULL);
1442 }
1443 }
1444
1445 /* Update prior route. */
1446 if (new != old) {
1447 /* Set real nexthop. */
1448 nexthop_active_update(rn, old, 1);
1449 UNSET_FLAG(old->status, ROUTE_ENTRY_CHANGED);
1450 }
1451
1452 /* Clear changed flag. */
1453 UNSET_FLAG(new->status, ROUTE_ENTRY_CHANGED);
1454 }
1455
1456 /* Check if 'alternate' RIB entry is better than 'current'. */
1457 static struct route_entry *rib_choose_best(struct route_entry *current,
1458 struct route_entry *alternate)
1459 {
1460 if (current == NULL)
1461 return alternate;
1462
1463 /* filter route selection in following order:
1464 * - connected beats other types
1465 * - lower distance beats higher
1466 * - lower metric beats higher for equal distance
1467 * - last, hence oldest, route wins tie break.
1468 */
1469
1470 /* Connected routes. Pick the last connected
1471 * route of the set of lowest metric connected routes.
1472 */
1473 if (alternate->type == ZEBRA_ROUTE_CONNECT) {
1474 if (current->type != ZEBRA_ROUTE_CONNECT
1475 || alternate->metric <= current->metric)
1476 return alternate;
1477
1478 return current;
1479 }
1480
1481 if (current->type == ZEBRA_ROUTE_CONNECT)
1482 return current;
1483
1484 /* higher distance loses */
1485 if (alternate->distance < current->distance)
1486 return alternate;
1487 if (current->distance < alternate->distance)
1488 return current;
1489
1490 /* metric tie-breaks equal distance */
1491 if (alternate->metric <= current->metric)
1492 return alternate;
1493
1494 return current;
1495 }
1496
1497 /* Core function for processing routing information base. */
1498 static void rib_process(struct route_node *rn)
1499 {
1500 struct route_entry *re;
1501 struct route_entry *next;
1502 struct route_entry *old_selected = NULL;
1503 struct route_entry *new_selected = NULL;
1504 struct route_entry *old_fib = NULL;
1505 struct route_entry *new_fib = NULL;
1506 struct route_entry *best = NULL;
1507 char buf[SRCDEST2STR_BUFFER];
1508 rib_dest_t *dest;
1509 struct zebra_vrf *zvrf = NULL;
1510 struct prefix *p, *src_p;
1511 srcdest_rnode_prefixes(rn, &p, &src_p);
1512 vrf_id_t vrf_id = VRF_UNKNOWN;
1513
1514 assert(rn);
1515
1516 dest = rib_dest_from_rnode(rn);
1517 if (dest) {
1518 zvrf = rib_dest_vrf(dest);
1519 vrf_id = zvrf_id(zvrf);
1520 }
1521
1522 if (IS_ZEBRA_DEBUG_RIB)
1523 srcdest_rnode2str(rn, buf, sizeof(buf));
1524
1525 if (IS_ZEBRA_DEBUG_RIB_DETAILED)
1526 zlog_debug("%u:%s: Processing rn %p", vrf_id, buf, rn);
1527
1528 /*
1529 * we can have rn's that have a NULL info pointer
1530 * (dest). As such let's not let the deref happen
1531 * additionally we know RNODE_FOREACH_RE_SAFE
1532 * will not iterate so we are ok.
1533 */
1534 if (dest)
1535 old_fib = dest->selected_fib;
1536
1537 RNODE_FOREACH_RE_SAFE (rn, re, next) {
1538 if (IS_ZEBRA_DEBUG_RIB_DETAILED)
1539 zlog_debug(
1540 "%u:%s: Examine re %p (type %d) status %x flags %x "
1541 "dist %d metric %d",
1542 vrf_id, buf, re, re->type, re->status,
1543 re->flags, re->distance, re->metric);
1544
1545 UNSET_FLAG(re->status, ROUTE_ENTRY_NEXTHOPS_CHANGED);
1546
1547 /* Currently selected re. */
1548 if (CHECK_FLAG(re->flags, ZEBRA_FLAG_SELECTED)) {
1549 assert(old_selected == NULL);
1550 old_selected = re;
1551 }
1552
1553 /* Skip deleted entries from selection */
1554 if (CHECK_FLAG(re->status, ROUTE_ENTRY_REMOVED))
1555 continue;
1556
1557 /* Skip unreachable nexthop. */
1558 /* This first call to nexthop_active_update is merely to
1559 * determine if
1560 * there's any change to nexthops associated with this RIB
1561 * entry. Now,
1562 * rib_process() can be invoked due to an external event such as
1563 * link
1564 * down or due to next-hop-tracking evaluation. In the latter
1565 * case,
1566 * a decision has already been made that the NHs have changed.
1567 * So, no
1568 * need to invoke a potentially expensive call again. Further,
1569 * since
1570 * the change might be in a recursive NH which is not caught in
1571 * the nexthop_active_update() code. Thus, we might miss changes
1572 * to
1573 * recursive NHs.
1574 */
1575 if (!CHECK_FLAG(re->status, ROUTE_ENTRY_CHANGED)
1576 && !nexthop_active_update(rn, re, 0)) {
1577 if (re->type == ZEBRA_ROUTE_TABLE) {
1578 /* XXX: HERE BE DRAGONS!!!!!
1579 * In all honesty, I have not yet figured out
1580 * what this part
1581 * does or why the ROUTE_ENTRY_CHANGED test
1582 * above is correct
1583 * or why we need to delete a route here, and
1584 * also not whether
1585 * this concerns both selected and fib route, or
1586 * only selected
1587 * or only fib */
1588 /* This entry was denied by the 'ip protocol
1589 * table' route-map, we
1590 * need to delete it */
1591 if (re != old_selected) {
1592 if (IS_ZEBRA_DEBUG_RIB)
1593 zlog_debug(
1594 "%s: %s: imported via import-table but denied "
1595 "by the ip protocol table route-map",
1596 __func__, buf);
1597 rib_unlink(rn, re);
1598 } else
1599 SET_FLAG(re->status,
1600 ROUTE_ENTRY_REMOVED);
1601 }
1602
1603 continue;
1604 }
1605
1606 /* Infinite distance. */
1607 if (re->distance == DISTANCE_INFINITY) {
1608 UNSET_FLAG(re->status, ROUTE_ENTRY_CHANGED);
1609 continue;
1610 }
1611
1612 if (CHECK_FLAG(re->flags, ZEBRA_FLAG_FIB_OVERRIDE)) {
1613 best = rib_choose_best(new_fib, re);
1614 if (new_fib && best != new_fib)
1615 UNSET_FLAG(new_fib->status,
1616 ROUTE_ENTRY_CHANGED);
1617 new_fib = best;
1618 } else {
1619 best = rib_choose_best(new_selected, re);
1620 if (new_selected && best != new_selected)
1621 UNSET_FLAG(new_selected->status,
1622 ROUTE_ENTRY_CHANGED);
1623 new_selected = best;
1624 }
1625 if (best != re)
1626 UNSET_FLAG(re->status, ROUTE_ENTRY_CHANGED);
1627 } /* RNODE_FOREACH_RE */
1628
1629 /* If no FIB override route, use the selected route also for FIB */
1630 if (new_fib == NULL)
1631 new_fib = new_selected;
1632
1633 /* After the cycle is finished, the following pointers will be set:
1634 * old_selected --- RE entry currently having SELECTED
1635 * new_selected --- RE entry that is newly SELECTED
1636 * old_fib --- RE entry currently in kernel FIB
1637 * new_fib --- RE entry that is newly to be in kernel FIB
1638 *
1639 * new_selected will get SELECTED flag, and is going to be redistributed
1640 * the zclients. new_fib (which can be new_selected) will be installed
1641 * in kernel.
1642 */
1643
1644 if (IS_ZEBRA_DEBUG_RIB_DETAILED) {
1645 zlog_debug(
1646 "%u:%s: After processing: old_selected %p new_selected %p old_fib %p new_fib %p",
1647 vrf_id, buf, (void *)old_selected, (void *)new_selected,
1648 (void *)old_fib, (void *)new_fib);
1649 }
1650
1651 /* Buffer ROUTE_ENTRY_CHANGED here, because it will get cleared if
1652 * fib == selected */
1653 bool selected_changed = new_selected && CHECK_FLAG(new_selected->status,
1654 ROUTE_ENTRY_CHANGED);
1655
1656 /* Update fib according to selection results */
1657 if (new_fib && old_fib)
1658 rib_process_update_fib(zvrf, rn, old_fib, new_fib);
1659 else if (new_fib)
1660 rib_process_add_fib(zvrf, rn, new_fib);
1661 else if (old_fib)
1662 rib_process_del_fib(zvrf, rn, old_fib);
1663
1664 /* Redistribute SELECTED entry */
1665 if (old_selected != new_selected || selected_changed) {
1666 struct nexthop *nexthop;
1667
1668 /* Check if we have a FIB route for the destination, otherwise,
1669 * don't redistribute it */
1670 for (ALL_NEXTHOPS(new_fib ? new_fib->nexthop : NULL, nexthop)) {
1671 if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_FIB)) {
1672 break;
1673 }
1674 }
1675 if (!nexthop)
1676 new_selected = NULL;
1677
1678 if (new_selected && new_selected != new_fib) {
1679 nexthop_active_update(rn, new_selected, 1);
1680 UNSET_FLAG(new_selected->status, ROUTE_ENTRY_CHANGED);
1681 }
1682
1683 if (old_selected) {
1684 if (!new_selected)
1685 redistribute_delete(p, src_p, old_selected);
1686 if (old_selected != new_selected)
1687 UNSET_FLAG(old_selected->flags,
1688 ZEBRA_FLAG_SELECTED);
1689 }
1690
1691 if (new_selected) {
1692 /* Install new or replace existing redistributed entry
1693 */
1694 SET_FLAG(new_selected->flags, ZEBRA_FLAG_SELECTED);
1695 redistribute_update(p, src_p, new_selected,
1696 old_selected);
1697 }
1698 }
1699
1700 /* Remove all RE entries queued for removal */
1701 RNODE_FOREACH_RE_SAFE (rn, re, next) {
1702 if (CHECK_FLAG(re->status, ROUTE_ENTRY_REMOVED)) {
1703 if (IS_ZEBRA_DEBUG_RIB) {
1704 rnode_debug(rn, vrf_id, "rn %p, removing re %p",
1705 (void *)rn, (void *)re);
1706 }
1707 rib_unlink(rn, re);
1708 }
1709 }
1710
1711 /*
1712 * Check if the dest can be deleted now.
1713 */
1714 rib_gc_dest(rn);
1715 }
1716
1717 /* Take a list of route_node structs and return 1, if there was a record
1718 * picked from it and processed by rib_process(). Don't process more,
1719 * than one RN record; operate only in the specified sub-queue.
1720 */
1721 static unsigned int process_subq(struct list *subq, u_char qindex)
1722 {
1723 struct listnode *lnode = listhead(subq);
1724 struct route_node *rnode;
1725 rib_dest_t *dest;
1726 struct zebra_vrf *zvrf = NULL;
1727
1728 if (!lnode)
1729 return 0;
1730
1731 rnode = listgetdata(lnode);
1732 dest = rib_dest_from_rnode(rnode);
1733 if (dest)
1734 zvrf = rib_dest_vrf(dest);
1735
1736 rib_process(rnode);
1737
1738 if (IS_ZEBRA_DEBUG_RIB_DETAILED) {
1739 char buf[SRCDEST2STR_BUFFER];
1740 srcdest_rnode2str(rnode, buf, sizeof(buf));
1741 zlog_debug("%u:%s: rn %p dequeued from sub-queue %u",
1742 zvrf ? zvrf_id(zvrf) : 0, buf, rnode, qindex);
1743 }
1744
1745 if (rnode->info)
1746 UNSET_FLAG(rib_dest_from_rnode(rnode)->flags,
1747 RIB_ROUTE_QUEUED(qindex));
1748
1749 #if 0
1750 else
1751 {
1752 zlog_debug ("%s: called for route_node (%p, %d) with no ribs",
1753 __func__, rnode, rnode->lock);
1754 zlog_backtrace(LOG_DEBUG);
1755 }
1756 #endif
1757 route_unlock_node(rnode);
1758 list_delete_node(subq, lnode);
1759 return 1;
1760 }
1761
1762 /*
1763 * All meta queues have been processed. Trigger next-hop evaluation.
1764 */
1765 static void meta_queue_process_complete(struct work_queue *dummy)
1766 {
1767 struct vrf *vrf;
1768 struct zebra_vrf *zvrf;
1769
1770 /* Evaluate nexthops for those VRFs which underwent route processing.
1771 * This
1772 * should limit the evaluation to the necessary VRFs in most common
1773 * situations.
1774 */
1775 RB_FOREACH (vrf, vrf_id_head, &vrfs_by_id) {
1776 zvrf = vrf->info;
1777 if (zvrf == NULL || !(zvrf->flags & ZEBRA_VRF_RIB_SCHEDULED))
1778 continue;
1779
1780 zvrf->flags &= ~ZEBRA_VRF_RIB_SCHEDULED;
1781 zebra_evaluate_rnh(zvrf_id(zvrf), AF_INET, 0, RNH_NEXTHOP_TYPE,
1782 NULL);
1783 zebra_evaluate_rnh(zvrf_id(zvrf), AF_INET, 0,
1784 RNH_IMPORT_CHECK_TYPE, NULL);
1785 zebra_evaluate_rnh(zvrf_id(zvrf), AF_INET6, 0, RNH_NEXTHOP_TYPE,
1786 NULL);
1787 zebra_evaluate_rnh(zvrf_id(zvrf), AF_INET6, 0,
1788 RNH_IMPORT_CHECK_TYPE, NULL);
1789 }
1790
1791 /* Schedule LSPs for processing, if needed. */
1792 zvrf = vrf_info_lookup(VRF_DEFAULT);
1793 if (mpls_should_lsps_be_processed(zvrf)) {
1794 if (IS_ZEBRA_DEBUG_MPLS)
1795 zlog_debug(
1796 "%u: Scheduling all LSPs upon RIB completion",
1797 zvrf_id(zvrf));
1798 zebra_mpls_lsp_schedule(zvrf);
1799 mpls_unmark_lsps_for_processing(zvrf);
1800 }
1801 }
1802
1803 /* Dispatch the meta queue by picking, processing and unlocking the next RN from
1804 * a non-empty sub-queue with lowest priority. wq is equal to zebra->ribq and
1805 * data
1806 * is pointed to the meta queue structure.
1807 */
1808 static wq_item_status meta_queue_process(struct work_queue *dummy, void *data)
1809 {
1810 struct meta_queue *mq = data;
1811 unsigned i;
1812
1813 for (i = 0; i < MQ_SIZE; i++)
1814 if (process_subq(mq->subq[i], i)) {
1815 mq->size--;
1816 break;
1817 }
1818 return mq->size ? WQ_REQUEUE : WQ_SUCCESS;
1819 }
1820
1821 /*
1822 * Map from rib types to queue type (priority) in meta queue
1823 */
1824 static const u_char meta_queue_map[ZEBRA_ROUTE_MAX] = {
1825 [ZEBRA_ROUTE_SYSTEM] = 4,
1826 [ZEBRA_ROUTE_KERNEL] = 0,
1827 [ZEBRA_ROUTE_CONNECT] = 0,
1828 [ZEBRA_ROUTE_STATIC] = 1,
1829 [ZEBRA_ROUTE_RIP] = 2,
1830 [ZEBRA_ROUTE_RIPNG] = 2,
1831 [ZEBRA_ROUTE_OSPF] = 2,
1832 [ZEBRA_ROUTE_OSPF6] = 2,
1833 [ZEBRA_ROUTE_ISIS] = 2,
1834 [ZEBRA_ROUTE_BGP] = 3,
1835 [ZEBRA_ROUTE_PIM] = 4, // Shouldn't happen but for safety
1836 [ZEBRA_ROUTE_EIGRP] = 2,
1837 [ZEBRA_ROUTE_NHRP] = 2,
1838 [ZEBRA_ROUTE_HSLS] = 4,
1839 [ZEBRA_ROUTE_OLSR] = 4,
1840 [ZEBRA_ROUTE_TABLE] = 1,
1841 [ZEBRA_ROUTE_LDP] = 4,
1842 [ZEBRA_ROUTE_VNC] = 3,
1843 [ZEBRA_ROUTE_VNC_DIRECT] = 3,
1844 [ZEBRA_ROUTE_VNC_DIRECT_RH] = 3,
1845 [ZEBRA_ROUTE_BGP_DIRECT] = 3,
1846 [ZEBRA_ROUTE_BGP_DIRECT_EXT] = 3,
1847 [ZEBRA_ROUTE_BABEL] = 2,
1848 [ZEBRA_ROUTE_ALL] = 4, // Shouldn't happen but for safety
1849 };
1850
1851 /* Look into the RN and queue it into one or more priority queues,
1852 * increasing the size for each data push done.
1853 */
1854 static void rib_meta_queue_add(struct meta_queue *mq, struct route_node *rn)
1855 {
1856 struct route_entry *re;
1857
1858 RNODE_FOREACH_RE (rn, re) {
1859 u_char qindex = meta_queue_map[re->type];
1860 struct zebra_vrf *zvrf;
1861
1862 /* Invariant: at this point we always have rn->info set. */
1863 if (CHECK_FLAG(rib_dest_from_rnode(rn)->flags,
1864 RIB_ROUTE_QUEUED(qindex))) {
1865 if (IS_ZEBRA_DEBUG_RIB_DETAILED)
1866 rnode_debug(
1867 rn, re->vrf_id,
1868 "rn %p is already queued in sub-queue %u",
1869 (void *)rn, qindex);
1870 continue;
1871 }
1872
1873 SET_FLAG(rib_dest_from_rnode(rn)->flags,
1874 RIB_ROUTE_QUEUED(qindex));
1875 listnode_add(mq->subq[qindex], rn);
1876 route_lock_node(rn);
1877 mq->size++;
1878
1879 if (IS_ZEBRA_DEBUG_RIB_DETAILED)
1880 rnode_debug(rn, re->vrf_id,
1881 "queued rn %p into sub-queue %u",
1882 (void *)rn, qindex);
1883
1884 zvrf = zebra_vrf_lookup_by_id(re->vrf_id);
1885 if (zvrf)
1886 zvrf->flags |= ZEBRA_VRF_RIB_SCHEDULED;
1887 }
1888 }
1889
1890 /* Add route_node to work queue and schedule processing */
1891 void rib_queue_add(struct route_node *rn)
1892 {
1893 assert(rn);
1894
1895 /* Pointless to queue a route_node with no RIB entries to add or remove
1896 */
1897 if (!rnode_to_ribs(rn)) {
1898 zlog_debug("%s: called for route_node (%p, %d) with no ribs",
1899 __func__, (void *)rn, rn->lock);
1900 zlog_backtrace(LOG_DEBUG);
1901 return;
1902 }
1903
1904 if (zebrad.ribq == NULL) {
1905 zlog_err("%s: work_queue does not exist!", __func__);
1906 return;
1907 }
1908
1909 /*
1910 * The RIB queue should normally be either empty or holding the only
1911 * work_queue_item element. In the latter case this element would
1912 * hold a pointer to the meta queue structure, which must be used to
1913 * actually queue the route nodes to process. So create the MQ
1914 * holder, if necessary, then push the work into it in any case.
1915 * This semantics was introduced after 0.99.9 release.
1916 */
1917 if (work_queue_empty(zebrad.ribq))
1918 work_queue_add(zebrad.ribq, zebrad.mq);
1919
1920 rib_meta_queue_add(zebrad.mq, rn);
1921
1922 return;
1923 }
1924
1925 /* Create new meta queue.
1926 A destructor function doesn't seem to be necessary here.
1927 */
1928 static struct meta_queue *meta_queue_new(void)
1929 {
1930 struct meta_queue *new;
1931 unsigned i;
1932
1933 new = XCALLOC(MTYPE_WORK_QUEUE, sizeof(struct meta_queue));
1934 assert(new);
1935
1936 for (i = 0; i < MQ_SIZE; i++) {
1937 new->subq[i] = list_new();
1938 assert(new->subq[i]);
1939 }
1940
1941 return new;
1942 }
1943
1944 void meta_queue_free(struct meta_queue *mq)
1945 {
1946 unsigned i;
1947
1948 for (i = 0; i < MQ_SIZE; i++)
1949 list_delete_and_null(&mq->subq[i]);
1950
1951 XFREE(MTYPE_WORK_QUEUE, mq);
1952 }
1953
1954 /* initialise zebra rib work queue */
1955 static void rib_queue_init(struct zebra_t *zebra)
1956 {
1957 assert(zebra);
1958
1959 if (!(zebra->ribq =
1960 work_queue_new(zebra->master, "route_node processing"))) {
1961 zlog_err("%s: could not initialise work queue!", __func__);
1962 return;
1963 }
1964
1965 /* fill in the work queue spec */
1966 zebra->ribq->spec.workfunc = &meta_queue_process;
1967 zebra->ribq->spec.errorfunc = NULL;
1968 zebra->ribq->spec.completion_func = &meta_queue_process_complete;
1969 /* XXX: TODO: These should be runtime configurable via vty */
1970 zebra->ribq->spec.max_retries = 3;
1971 zebra->ribq->spec.hold = ZEBRA_RIB_PROCESS_HOLD_TIME;
1972
1973 if (!(zebra->mq = meta_queue_new())) {
1974 zlog_err("%s: could not initialise meta queue!", __func__);
1975 return;
1976 }
1977 return;
1978 }
1979
1980 /* RIB updates are processed via a queue of pointers to route_nodes.
1981 *
1982 * The queue length is bounded by the maximal size of the routing table,
1983 * as a route_node will not be requeued, if already queued.
1984 *
1985 * REs are submitted via rib_addnode or rib_delnode which set minimal
1986 * state, or static_install_route (when an existing RE is updated)
1987 * and then submit route_node to queue for best-path selection later.
1988 * Order of add/delete state changes are preserved for any given RE.
1989 *
1990 * Deleted REs are reaped during best-path selection.
1991 *
1992 * rib_addnode
1993 * |-> rib_link or unset ROUTE_ENTRY_REMOVE |->Update kernel with
1994 * |-------->| | best RE, if required
1995 * | |
1996 * static_install->|->rib_addqueue...... -> rib_process
1997 * | |
1998 * |-------->| |-> rib_unlink
1999 * |-> set ROUTE_ENTRY_REMOVE |
2000 * rib_delnode (RE freed)
2001 *
2002 * The 'info' pointer of a route_node points to a rib_dest_t
2003 * ('dest'). Queueing state for a route_node is kept on the dest. The
2004 * dest is created on-demand by rib_link() and is kept around at least
2005 * as long as there are ribs hanging off it (@see rib_gc_dest()).
2006 *
2007 * Refcounting (aka "locking" throughout the GNU Zebra and Quagga code):
2008 *
2009 * - route_nodes: refcounted by:
2010 * - dest attached to route_node:
2011 * - managed by: rib_link/rib_gc_dest
2012 * - route_node processing queue
2013 * - managed by: rib_addqueue, rib_process.
2014 *
2015 */
2016
2017 /* Add RE to head of the route node. */
2018 static void rib_link(struct route_node *rn, struct route_entry *re, int process)
2019 {
2020 struct route_entry *head;
2021 rib_dest_t *dest;
2022 afi_t afi;
2023 const char *rmap_name;
2024
2025 assert(re && rn);
2026
2027 dest = rib_dest_from_rnode(rn);
2028 if (!dest) {
2029 if (IS_ZEBRA_DEBUG_RIB_DETAILED)
2030 rnode_debug(rn, re->vrf_id, "rn %p adding dest", rn);
2031
2032 dest = XCALLOC(MTYPE_RIB_DEST, sizeof(rib_dest_t));
2033 route_lock_node(rn); /* rn route table reference */
2034 rn->info = dest;
2035 dest->rnode = rn;
2036 }
2037
2038 head = dest->routes;
2039 if (head) {
2040 head->prev = re;
2041 }
2042 re->next = head;
2043 dest->routes = re;
2044
2045 afi = (rn->p.family == AF_INET)
2046 ? AFI_IP
2047 : (rn->p.family == AF_INET6) ? AFI_IP6 : AFI_MAX;
2048 if (is_zebra_import_table_enabled(afi, re->table)) {
2049 rmap_name = zebra_get_import_table_route_map(afi, re->table);
2050 zebra_add_import_table_entry(rn, re, rmap_name);
2051 } else if (process)
2052 rib_queue_add(rn);
2053 }
2054
2055 void rib_addnode(struct route_node *rn, struct route_entry *re, int process)
2056 {
2057 /* RE node has been un-removed before route-node is processed.
2058 * route_node must hence already be on the queue for processing..
2059 */
2060 if (CHECK_FLAG(re->status, ROUTE_ENTRY_REMOVED)) {
2061 if (IS_ZEBRA_DEBUG_RIB)
2062 rnode_debug(rn, re->vrf_id, "rn %p, un-removed re %p",
2063 (void *)rn, (void *)re);
2064
2065 UNSET_FLAG(re->status, ROUTE_ENTRY_REMOVED);
2066 return;
2067 }
2068 rib_link(rn, re, process);
2069 }
2070
2071 /*
2072 * rib_unlink
2073 *
2074 * Detach a rib structure from a route_node.
2075 *
2076 * Note that a call to rib_unlink() should be followed by a call to
2077 * rib_gc_dest() at some point. This allows a rib_dest_t that is no
2078 * longer required to be deleted.
2079 */
2080 void rib_unlink(struct route_node *rn, struct route_entry *re)
2081 {
2082 rib_dest_t *dest;
2083
2084 assert(rn && re);
2085
2086 if (IS_ZEBRA_DEBUG_RIB)
2087 rnode_debug(rn, re->vrf_id, "rn %p, re %p", (void *)rn,
2088 (void *)re);
2089
2090 dest = rib_dest_from_rnode(rn);
2091
2092 if (re->next)
2093 re->next->prev = re->prev;
2094
2095 if (re->prev)
2096 re->prev->next = re->next;
2097 else {
2098 dest->routes = re->next;
2099 }
2100
2101 if (dest->selected_fib == re)
2102 dest->selected_fib = NULL;
2103
2104 /* free RE and nexthops */
2105 zebra_deregister_rnh_static_nexthops(re->vrf_id, re->nexthop, rn);
2106 nexthops_free(re->nexthop);
2107 XFREE(MTYPE_RE, re);
2108 }
2109
2110 void rib_delnode(struct route_node *rn, struct route_entry *re)
2111 {
2112 afi_t afi;
2113
2114 if (IS_ZEBRA_DEBUG_RIB)
2115 rnode_debug(rn, re->vrf_id, "rn %p, re %p, removing",
2116 (void *)rn, (void *)re);
2117 SET_FLAG(re->status, ROUTE_ENTRY_REMOVED);
2118
2119 afi = (rn->p.family == AF_INET)
2120 ? AFI_IP
2121 : (rn->p.family == AF_INET6) ? AFI_IP6 : AFI_MAX;
2122 if (is_zebra_import_table_enabled(afi, re->table)) {
2123 zebra_del_import_table_entry(rn, re);
2124 /* Just clean up if non main table */
2125 if (IS_ZEBRA_DEBUG_RIB) {
2126 char buf[SRCDEST2STR_BUFFER];
2127 srcdest_rnode2str(rn, buf, sizeof(buf));
2128 zlog_debug(
2129 "%u:%s: Freeing route rn %p, re %p (type %d)",
2130 re->vrf_id, buf, rn, re, re->type);
2131 }
2132
2133 rib_unlink(rn, re);
2134 } else {
2135 rib_queue_add(rn);
2136 }
2137 }
2138
2139 /* This function dumps the contents of a given RE entry into
2140 * standard debug log. Calling function name and IP prefix in
2141 * question are passed as 1st and 2nd arguments.
2142 */
2143
2144 void _route_entry_dump(const char *func, union prefixconstptr pp,
2145 union prefixconstptr src_pp,
2146 const struct route_entry *re)
2147 {
2148 const struct prefix *p = pp.p;
2149 const struct prefix *src_p = src_pp.p;
2150 bool is_srcdst = src_p && src_p->prefixlen;
2151 char straddr[PREFIX_STRLEN];
2152 char srcaddr[PREFIX_STRLEN];
2153 struct nexthop *nexthop;
2154
2155 zlog_debug("%s: dumping RE entry %p for %s%s%s vrf %u", func,
2156 (const void *)re, prefix2str(pp, straddr, sizeof(straddr)),
2157 is_srcdst ? " from " : "",
2158 is_srcdst ? prefix2str(src_pp, srcaddr, sizeof(srcaddr))
2159 : "",
2160 re->vrf_id);
2161 zlog_debug("%s: uptime == %lu, type == %u, instance == %d, table == %d",
2162 func, (unsigned long)re->uptime, re->type, re->instance,
2163 re->table);
2164 zlog_debug(
2165 "%s: metric == %u, mtu == %u, distance == %u, flags == %u, status == %u",
2166 func, re->metric, re->mtu, re->distance, re->flags, re->status);
2167 zlog_debug("%s: nexthop_num == %u, nexthop_active_num == %u", func,
2168 re->nexthop_num, re->nexthop_active_num);
2169
2170 for (ALL_NEXTHOPS(re->nexthop, nexthop)) {
2171 inet_ntop(p->family, &nexthop->gate, straddr, INET6_ADDRSTRLEN);
2172 zlog_debug("%s: %s %s[%u] with flags %s%s%s", func,
2173 (nexthop->rparent ? " NH" : "NH"), straddr,
2174 nexthop->ifindex,
2175 (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE)
2176 ? "ACTIVE "
2177 : ""),
2178 (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_FIB)
2179 ? "FIB "
2180 : ""),
2181 (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_RECURSIVE)
2182 ? "RECURSIVE"
2183 : ""));
2184 }
2185 zlog_debug("%s: dump complete", func);
2186 }
2187
2188 /* This is an exported helper to rtm_read() to dump the strange
2189 * RE entry found by rib_lookup_ipv4_route()
2190 */
2191
2192 void rib_lookup_and_dump(struct prefix_ipv4 *p, vrf_id_t vrf_id)
2193 {
2194 struct route_table *table;
2195 struct route_node *rn;
2196 struct route_entry *re;
2197 char prefix_buf[INET_ADDRSTRLEN];
2198
2199 /* Lookup table. */
2200 table = zebra_vrf_table(AFI_IP, SAFI_UNICAST, vrf_id);
2201 if (!table) {
2202 zlog_err("%s: zebra_vrf_table() returned NULL", __func__);
2203 return;
2204 }
2205
2206 /* Scan the RIB table for exactly matching RE entry. */
2207 rn = route_node_lookup(table, (struct prefix *)p);
2208
2209 /* No route for this prefix. */
2210 if (!rn) {
2211 zlog_debug("%s: lookup failed for %s", __func__,
2212 prefix2str((struct prefix *)p, prefix_buf,
2213 sizeof(prefix_buf)));
2214 return;
2215 }
2216
2217 /* Unlock node. */
2218 route_unlock_node(rn);
2219
2220 /* let's go */
2221 RNODE_FOREACH_RE (rn, re) {
2222 zlog_debug("%s: rn %p, re %p: %s, %s", __func__, (void *)rn,
2223 (void *)re,
2224 (CHECK_FLAG(re->status, ROUTE_ENTRY_REMOVED)
2225 ? "removed"
2226 : "NOT removed"),
2227 (CHECK_FLAG(re->flags, ZEBRA_FLAG_SELECTED)
2228 ? "selected"
2229 : "NOT selected"));
2230 route_entry_dump(p, NULL, re);
2231 }
2232 }
2233
2234 /* Check if requested address assignment will fail due to another
2235 * route being installed by zebra in FIB already. Take necessary
2236 * actions, if needed: remove such a route from FIB and deSELECT
2237 * corresponding RE entry. Then put affected RN into RIBQ head.
2238 */
2239 void rib_lookup_and_pushup(struct prefix_ipv4 *p, vrf_id_t vrf_id)
2240 {
2241 struct route_table *table;
2242 struct route_node *rn;
2243 unsigned changed = 0;
2244 rib_dest_t *dest;
2245
2246 if (NULL == (table = zebra_vrf_table(AFI_IP, SAFI_UNICAST, vrf_id))) {
2247 zlog_err("%s: zebra_vrf_table() returned NULL", __func__);
2248 return;
2249 }
2250
2251 /* No matches would be the simplest case. */
2252 if (NULL == (rn = route_node_lookup(table, (struct prefix *)p)))
2253 return;
2254
2255 /* Unlock node. */
2256 route_unlock_node(rn);
2257
2258 dest = rib_dest_from_rnode(rn);
2259 /* Check all RE entries. In case any changes have to be done, requeue
2260 * the RN into RIBQ head. If the routing message about the new connected
2261 * route (generated by the IP address we are going to assign very soon)
2262 * comes before the RIBQ is processed, the new RE entry will join
2263 * RIBQ record already on head. This is necessary for proper
2264 * revalidation
2265 * of the rest of the RE.
2266 */
2267 if (dest->selected_fib && !RIB_SYSTEM_ROUTE(dest->selected_fib)) {
2268 changed = 1;
2269 if (IS_ZEBRA_DEBUG_RIB) {
2270 char buf[PREFIX_STRLEN];
2271
2272 zlog_debug("%u:%s: freeing way for connected prefix",
2273 dest->selected_fib->vrf_id,
2274 prefix2str(&rn->p, buf, sizeof(buf)));
2275 route_entry_dump(&rn->p, NULL, dest->selected_fib);
2276 }
2277 rib_uninstall(rn, dest->selected_fib);
2278 }
2279 if (changed)
2280 rib_queue_add(rn);
2281 }
2282
2283 int rib_add_multipath(afi_t afi, safi_t safi, struct prefix *p,
2284 struct prefix_ipv6 *src_p, struct route_entry *re)
2285 {
2286 struct route_table *table;
2287 struct route_node *rn;
2288 struct route_entry *same;
2289 struct nexthop *nexthop;
2290 int ret = 0;
2291
2292 if (!re)
2293 return 0;
2294
2295 assert(!src_p || afi == AFI_IP6);
2296
2297 /* Lookup table. */
2298 table = zebra_vrf_table_with_table_id(afi, safi, re->vrf_id, re->table);
2299 if (!table) {
2300 XFREE(MTYPE_RE, re);
2301 return 0;
2302 }
2303
2304 /* Make it sure prefixlen is applied to the prefix. */
2305 apply_mask(p);
2306 if (src_p)
2307 apply_mask_ipv6(src_p);
2308
2309 /* Set default distance by route type. */
2310 if (re->distance == 0) {
2311 re->distance = route_distance(re->type);
2312
2313 /* iBGP distance is 200. */
2314 if (re->type == ZEBRA_ROUTE_BGP
2315 && CHECK_FLAG(re->flags, ZEBRA_FLAG_IBGP))
2316 re->distance = 200;
2317 }
2318
2319 /* Lookup route node.*/
2320 rn = srcdest_rnode_get(table, p, src_p);
2321
2322 /* If same type of route are installed, treat it as a implicit
2323 withdraw. */
2324 RNODE_FOREACH_RE (rn, same) {
2325 if (CHECK_FLAG(same->status, ROUTE_ENTRY_REMOVED))
2326 continue;
2327
2328 if (same->type != re->type)
2329 continue;
2330 if (same->instance != re->instance)
2331 continue;
2332 if (same->type == ZEBRA_ROUTE_KERNEL &&
2333 same->metric != re->metric)
2334 continue;
2335 /*
2336 * We should allow duplicate connected routes because of
2337 * IPv6 link-local routes and unnumbered interfaces on Linux.
2338 */
2339 if (same->type != ZEBRA_ROUTE_CONNECT)
2340 break;
2341 }
2342
2343 /* If this route is kernel route, set FIB flag to the route. */
2344 if (RIB_SYSTEM_ROUTE(re))
2345 for (nexthop = re->nexthop; nexthop; nexthop = nexthop->next)
2346 SET_FLAG(nexthop->flags, NEXTHOP_FLAG_FIB);
2347
2348 /* Link new re to node.*/
2349 if (IS_ZEBRA_DEBUG_RIB) {
2350 rnode_debug(
2351 rn, re->vrf_id,
2352 "Inserting route rn %p, re %p (type %d) existing %p",
2353 (void *)rn, (void *)re, re->type, (void *)same);
2354
2355 if (IS_ZEBRA_DEBUG_RIB_DETAILED)
2356 route_entry_dump(p, src_p, re);
2357 }
2358 rib_addnode(rn, re, 1);
2359 ret = 1;
2360
2361 /* Free implicit route.*/
2362 if (same) {
2363 rib_delnode(rn, same);
2364 ret = -1;
2365 }
2366
2367 route_unlock_node(rn);
2368 return ret;
2369 }
2370
2371 void rib_delete(afi_t afi, safi_t safi, vrf_id_t vrf_id, int type,
2372 u_short instance, int flags, struct prefix *p,
2373 struct prefix_ipv6 *src_p, const struct nexthop *nh,
2374 u_int32_t table_id, u_int32_t metric, bool fromkernel,
2375 struct ethaddr *rmac)
2376 {
2377 struct route_table *table;
2378 struct route_node *rn;
2379 struct route_entry *re;
2380 struct route_entry *fib = NULL;
2381 struct route_entry *same = NULL;
2382 struct nexthop *rtnh;
2383 char buf2[INET6_ADDRSTRLEN];
2384 rib_dest_t *dest;
2385
2386 assert(!src_p || afi == AFI_IP6);
2387
2388 /* Lookup table. */
2389 table = zebra_vrf_table_with_table_id(afi, safi, vrf_id, table_id);
2390 if (!table)
2391 return;
2392
2393 /* Apply mask. */
2394 apply_mask(p);
2395 if (src_p)
2396 apply_mask_ipv6(src_p);
2397
2398 /* Lookup route node. */
2399 rn = srcdest_rnode_lookup(table, p, src_p);
2400 if (!rn) {
2401 char dst_buf[PREFIX_STRLEN], src_buf[PREFIX_STRLEN];
2402
2403 prefix2str(p, dst_buf, sizeof(dst_buf));
2404 if (src_p && src_p->prefixlen)
2405 prefix2str(src_p, src_buf, sizeof(src_buf));
2406 else
2407 src_buf[0] = '\0';
2408
2409 if (IS_ZEBRA_DEBUG_RIB)
2410 zlog_debug("%u:%s%s%s doesn't exist in rib", vrf_id,
2411 dst_buf,
2412 (src_buf[0] != '\0') ? " from " : "",
2413 src_buf);
2414 return;
2415 }
2416
2417 dest = rib_dest_from_rnode(rn);
2418 fib = dest->selected_fib;
2419
2420 /* Lookup same type route. */
2421 RNODE_FOREACH_RE (rn, re) {
2422 if (CHECK_FLAG(re->status, ROUTE_ENTRY_REMOVED))
2423 continue;
2424
2425 if (re->type != type)
2426 continue;
2427 if (re->instance != instance)
2428 continue;
2429 if (re->type == ZEBRA_ROUTE_KERNEL &&
2430 re->metric != metric)
2431 continue;
2432 if (re->type == ZEBRA_ROUTE_CONNECT && (rtnh = re->nexthop)
2433 && rtnh->type == NEXTHOP_TYPE_IFINDEX && nh) {
2434 if (rtnh->ifindex != nh->ifindex)
2435 continue;
2436 same = re;
2437 break;
2438 }
2439 /* Make sure that the route found has the same gateway. */
2440 else {
2441 if (nh == NULL) {
2442 same = re;
2443 break;
2444 }
2445 for (ALL_NEXTHOPS(re->nexthop, rtnh))
2446 if (nexthop_same_no_recurse(rtnh, nh)) {
2447 same = re;
2448 break;
2449 }
2450 if (same)
2451 break;
2452 }
2453 }
2454 /* If same type of route can't be found and this message is from
2455 kernel. */
2456 if (!same) {
2457 /*
2458 * In the past(HA!) we could get here because
2459 * we were receiving a route delete from the
2460 * kernel and we're not marking the proto
2461 * as coming from it's appropriate originator.
2462 * Now that we are properly noticing the fact
2463 * that the kernel has deleted our route we
2464 * are not going to get called in this path
2465 * I am going to leave this here because
2466 * this might still work this way on non-linux
2467 * platforms as well as some weird state I have
2468 * not properly thought of yet.
2469 * If we can show that this code path is
2470 * dead then we can remove it.
2471 */
2472 if (fib && type == ZEBRA_ROUTE_KERNEL
2473 && CHECK_FLAG(flags, ZEBRA_FLAG_SELFROUTE)) {
2474 if (IS_ZEBRA_DEBUG_RIB) {
2475 rnode_debug(
2476 rn, vrf_id,
2477 "rn %p, re %p (type %d) was deleted from kernel, adding",
2478 rn, fib, fib->type);
2479 }
2480 if (allow_delete) {
2481 /* Unset flags. */
2482 for (rtnh = fib->nexthop; rtnh;
2483 rtnh = rtnh->next)
2484 UNSET_FLAG(rtnh->flags,
2485 NEXTHOP_FLAG_FIB);
2486
2487 /*
2488 * This is a non FRR route
2489 * as such we should mark
2490 * it as deleted
2491 */
2492 dest->selected_fib = NULL;
2493 } else {
2494 /* This means someone else, other than Zebra,
2495 * has deleted
2496 * a Zebra router from the kernel. We will add
2497 * it back */
2498 rib_install_kernel(rn, fib, NULL);
2499 }
2500 } else {
2501 if (IS_ZEBRA_DEBUG_RIB) {
2502 if (nh)
2503 rnode_debug(
2504 rn, vrf_id,
2505 "via %s ifindex %d type %d "
2506 "doesn't exist in rib",
2507 inet_ntop(
2508 family2afi(afi),
2509 &nh->gate, buf2,
2510 INET_ADDRSTRLEN), /* FIXME
2511 */
2512 nh->ifindex, type);
2513 else
2514 rnode_debug(
2515 rn, vrf_id,
2516 "type %d doesn't exist in rib",
2517 type);
2518 }
2519 route_unlock_node(rn);
2520 return;
2521 }
2522 }
2523
2524 if (same) {
2525 if (fromkernel &&
2526 CHECK_FLAG(flags, ZEBRA_FLAG_SELFROUTE) &&
2527 !allow_delete) {
2528 rib_install_kernel(rn, same, NULL);
2529 route_unlock_node(rn);
2530
2531 return;
2532 }
2533
2534 if (CHECK_FLAG(flags, ZEBRA_FLAG_EVPN_ROUTE)) {
2535 struct nexthop *tmp_nh;
2536
2537 for (ALL_NEXTHOPS(re->nexthop, tmp_nh)) {
2538 struct ipaddr vtep_ip;
2539
2540 memset(&vtep_ip, 0, sizeof(struct ipaddr));
2541 vtep_ip.ipa_type = IPADDR_V4;
2542 memcpy(&(vtep_ip.ipaddr_v4),
2543 &(tmp_nh->gate.ipv4),
2544 sizeof(struct in_addr));
2545 zebra_vxlan_evpn_vrf_route_del(re->vrf_id, rmac,
2546 &vtep_ip, p);
2547 }
2548 }
2549 rib_delnode(rn, same);
2550 }
2551
2552 route_unlock_node(rn);
2553 return;
2554 }
2555
2556
2557 int rib_add(afi_t afi, safi_t safi, vrf_id_t vrf_id, vrf_id_t nh_vrf_id,
2558 int type, u_short instance, int flags, struct prefix *p,
2559 struct prefix_ipv6 *src_p, const struct nexthop *nh,
2560 u_int32_t table_id, u_int32_t metric,
2561 u_int32_t mtu, uint8_t distance, route_tag_t tag)
2562 {
2563 struct route_entry *re;
2564 struct nexthop *nexthop;
2565
2566 /* Allocate new route_entry structure. */
2567 re = XCALLOC(MTYPE_RE, sizeof(struct route_entry));
2568 re->type = type;
2569 re->instance = instance;
2570 re->distance = distance;
2571 re->flags = flags;
2572 re->metric = metric;
2573 re->mtu = mtu;
2574 re->table = table_id;
2575 re->vrf_id = vrf_id;
2576 re->nh_vrf_id = nh_vrf_id;
2577 re->nexthop_num = 0;
2578 re->uptime = time(NULL);
2579 re->tag = tag;
2580
2581 /* Add nexthop. */
2582 nexthop = nexthop_new();
2583 *nexthop = *nh;
2584 route_entry_nexthop_add(re, nexthop);
2585
2586 return rib_add_multipath(afi, safi, p, src_p, re);
2587 }
2588
2589 /* Schedule routes of a particular table (address-family) based on event. */
2590 static void rib_update_table(struct route_table *table,
2591 rib_update_event_t event)
2592 {
2593 struct route_node *rn;
2594 struct route_entry *re, *next;
2595
2596 /* Walk all routes and queue for processing, if appropriate for
2597 * the trigger event.
2598 */
2599 for (rn = route_top(table); rn; rn = srcdest_route_next(rn)) {
2600 /*
2601 * If we are looking at a route node and the node
2602 * has already been queued we don't
2603 * need to queue it up again
2604 */
2605 if (rn->info
2606 && CHECK_FLAG(rib_dest_from_rnode(rn)->flags,
2607 RIB_ROUTE_ANY_QUEUED))
2608 continue;
2609 switch (event) {
2610 case RIB_UPDATE_IF_CHANGE:
2611 /* Examine all routes that won't get processed by the
2612 * protocol or
2613 * triggered by nexthop evaluation (NHT). This would be
2614 * system,
2615 * kernel and certain static routes. Note that NHT will
2616 * get
2617 * triggered upon an interface event as connected routes
2618 * always
2619 * get queued for processing.
2620 */
2621 RNODE_FOREACH_RE_SAFE (rn, re, next) {
2622 struct nexthop *nh;
2623
2624 if (re->type != ZEBRA_ROUTE_SYSTEM &&
2625 re->type != ZEBRA_ROUTE_KERNEL &&
2626 re->type != ZEBRA_ROUTE_CONNECT &&
2627 re->type != ZEBRA_ROUTE_STATIC)
2628 continue;
2629
2630 if (re->type != ZEBRA_ROUTE_STATIC) {
2631 rib_queue_add(rn);
2632 continue;
2633 }
2634
2635 for (nh = re->nexthop; nh; nh = nh->next)
2636 if (!(nh->type == NEXTHOP_TYPE_IPV4
2637 || nh->type == NEXTHOP_TYPE_IPV6))
2638 break;
2639
2640 /* If we only have nexthops to a
2641 * gateway, NHT will
2642 * take care.
2643 */
2644 if (nh)
2645 rib_queue_add(rn);
2646 }
2647 break;
2648
2649 case RIB_UPDATE_RMAP_CHANGE:
2650 case RIB_UPDATE_OTHER:
2651 /* Right now, examine all routes. Can restrict to a
2652 * protocol in
2653 * some cases (TODO).
2654 */
2655 if (rnode_to_ribs(rn))
2656 rib_queue_add(rn);
2657 break;
2658
2659 default:
2660 break;
2661 }
2662 }
2663 }
2664
2665 /* RIB update function. */
2666 void rib_update(vrf_id_t vrf_id, rib_update_event_t event)
2667 {
2668 struct route_table *table;
2669
2670 /* Process routes of interested address-families. */
2671 table = zebra_vrf_table(AFI_IP, SAFI_UNICAST, vrf_id);
2672 if (table)
2673 rib_update_table(table, event);
2674
2675 table = zebra_vrf_table(AFI_IP6, SAFI_UNICAST, vrf_id);
2676 if (table)
2677 rib_update_table(table, event);
2678 }
2679
2680 /* Remove all routes which comes from non main table. */
2681 static void rib_weed_table(struct route_table *table)
2682 {
2683 struct route_node *rn;
2684 struct route_entry *re;
2685 struct route_entry *next;
2686
2687 if (table)
2688 for (rn = route_top(table); rn; rn = srcdest_route_next(rn))
2689 RNODE_FOREACH_RE_SAFE (rn, re, next) {
2690 if (CHECK_FLAG(re->status, ROUTE_ENTRY_REMOVED))
2691 continue;
2692
2693 if (re->table != zebrad.rtm_table_default
2694 && re->table != RT_TABLE_MAIN)
2695 rib_delnode(rn, re);
2696 }
2697 }
2698
2699 /* Delete all routes from non main table. */
2700 void rib_weed_tables(void)
2701 {
2702 struct vrf *vrf;
2703 struct zebra_vrf *zvrf;
2704
2705 RB_FOREACH (vrf, vrf_id_head, &vrfs_by_id)
2706 if ((zvrf = vrf->info) != NULL) {
2707 rib_weed_table(zvrf->table[AFI_IP][SAFI_UNICAST]);
2708 rib_weed_table(zvrf->table[AFI_IP6][SAFI_UNICAST]);
2709 }
2710 }
2711
2712 /* Delete self installed routes after zebra is relaunched. */
2713 static void rib_sweep_table(struct route_table *table)
2714 {
2715 struct route_node *rn;
2716 struct route_entry *re;
2717 struct route_entry *next;
2718 struct nexthop *nexthop;
2719
2720 if (!table)
2721 return;
2722
2723 for (rn = route_top(table); rn; rn = srcdest_route_next(rn)) {
2724 RNODE_FOREACH_RE_SAFE (rn, re, next) {
2725 if (IS_ZEBRA_DEBUG_RIB)
2726 route_entry_dump(&rn->p, NULL, re);
2727
2728 if (CHECK_FLAG(re->status, ROUTE_ENTRY_REMOVED))
2729 continue;
2730
2731 if (!CHECK_FLAG(re->flags, ZEBRA_FLAG_SELFROUTE))
2732 continue;
2733
2734 /*
2735 * So we are starting up and have received
2736 * routes from the kernel that we have installed
2737 * from a previous run of zebra but not cleaned
2738 * up ( say a kill -9 )
2739 * But since we haven't actually installed
2740 * them yet( we received them from the kernel )
2741 * we don't think they are active.
2742 * So let's pretend they are active to actually
2743 * remove them.
2744 * In all honesty I'm not sure if we should
2745 * mark them as active when we receive them
2746 * This is startup only so probably ok.
2747 *
2748 * If we ever decide to move rib_sweep_table
2749 * to a different spot (ie startup )
2750 * this decision needs to be revisited
2751 */
2752 for (ALL_NEXTHOPS(re->nexthop, nexthop))
2753 SET_FLAG(nexthop->flags, NEXTHOP_FLAG_FIB);
2754
2755 rib_uninstall_kernel(rn, re);
2756 rib_delnode(rn, re);
2757 }
2758 }
2759 }
2760
2761 /* Sweep all RIB tables. */
2762 void rib_sweep_route(void)
2763 {
2764 struct vrf *vrf;
2765 struct zebra_vrf *zvrf;
2766
2767 RB_FOREACH (vrf, vrf_id_head, &vrfs_by_id) {
2768 if ((zvrf = vrf->info) == NULL)
2769 continue;
2770
2771 rib_sweep_table(zvrf->table[AFI_IP][SAFI_UNICAST]);
2772 rib_sweep_table(zvrf->table[AFI_IP6][SAFI_UNICAST]);
2773 }
2774 }
2775
2776 /* Remove specific by protocol routes from 'table'. */
2777 static unsigned long rib_score_proto_table(u_char proto, u_short instance,
2778 struct route_table *table)
2779 {
2780 struct route_node *rn;
2781 struct route_entry *re;
2782 struct route_entry *next;
2783 unsigned long n = 0;
2784
2785 if (table)
2786 for (rn = route_top(table); rn; rn = srcdest_route_next(rn))
2787 RNODE_FOREACH_RE_SAFE (rn, re, next) {
2788 if (CHECK_FLAG(re->status, ROUTE_ENTRY_REMOVED))
2789 continue;
2790 if (re->type == proto
2791 && re->instance == instance) {
2792 rib_delnode(rn, re);
2793 n++;
2794 }
2795 }
2796 return n;
2797 }
2798
2799 /* Remove specific by protocol routes. */
2800 unsigned long rib_score_proto(u_char proto, u_short instance)
2801 {
2802 struct vrf *vrf;
2803 struct zebra_vrf *zvrf;
2804 unsigned long cnt = 0;
2805
2806 RB_FOREACH (vrf, vrf_id_head, &vrfs_by_id)
2807 if ((zvrf = vrf->info) != NULL)
2808 cnt += rib_score_proto_table(
2809 proto, instance,
2810 zvrf->table[AFI_IP][SAFI_UNICAST])
2811 + rib_score_proto_table(
2812 proto, instance,
2813 zvrf->table[AFI_IP6][SAFI_UNICAST]);
2814
2815 return cnt;
2816 }
2817
2818 /* Close RIB and clean up kernel routes. */
2819 void rib_close_table(struct route_table *table)
2820 {
2821 struct route_node *rn;
2822 rib_table_info_t *info;
2823 rib_dest_t *dest;
2824
2825 if (!table)
2826 return;
2827
2828 info = table->info;
2829
2830 for (rn = route_top(table); rn; rn = srcdest_route_next(rn)) {
2831 dest = rib_dest_from_rnode(rn);
2832
2833 if (dest && dest->selected_fib) {
2834 if (info->safi == SAFI_UNICAST)
2835 hook_call(rib_update, rn, NULL);
2836
2837 if (!RIB_SYSTEM_ROUTE(dest->selected_fib))
2838 rib_uninstall_kernel(rn, dest->selected_fib);
2839 }
2840 }
2841 }
2842
2843 /* Routing information base initialize. */
2844 void rib_init(void)
2845 {
2846 rib_queue_init(&zebrad);
2847 }
2848
2849 /*
2850 * vrf_id_get_next
2851 *
2852 * Get the first vrf id that is greater than the given vrf id if any.
2853 *
2854 * Returns TRUE if a vrf id was found, FALSE otherwise.
2855 */
2856 static inline int vrf_id_get_next(vrf_id_t vrf_id, vrf_id_t *next_id_p)
2857 {
2858 struct vrf *vrf;
2859
2860 vrf = vrf_lookup_by_id(vrf_id);
2861 if (vrf) {
2862 vrf = RB_NEXT(vrf_id_head, vrf);
2863 if (vrf) {
2864 *next_id_p = vrf->vrf_id;
2865 return 1;
2866 }
2867 }
2868
2869 return 0;
2870 }
2871
2872 /*
2873 * rib_tables_iter_next
2874 *
2875 * Returns the next table in the iteration.
2876 */
2877 struct route_table *rib_tables_iter_next(rib_tables_iter_t *iter)
2878 {
2879 struct route_table *table;
2880
2881 /*
2882 * Array that helps us go over all AFI/SAFI combinations via one
2883 * index.
2884 */
2885 static struct {
2886 afi_t afi;
2887 safi_t safi;
2888 } afi_safis[] = {
2889 {AFI_IP, SAFI_UNICAST}, {AFI_IP, SAFI_MULTICAST},
2890 {AFI_IP, SAFI_LABELED_UNICAST}, {AFI_IP6, SAFI_UNICAST},
2891 {AFI_IP6, SAFI_MULTICAST}, {AFI_IP6, SAFI_LABELED_UNICAST},
2892 };
2893
2894 table = NULL;
2895
2896 switch (iter->state) {
2897
2898 case RIB_TABLES_ITER_S_INIT:
2899 iter->vrf_id = VRF_DEFAULT;
2900 iter->afi_safi_ix = -1;
2901
2902 /* Fall through */
2903
2904 case RIB_TABLES_ITER_S_ITERATING:
2905 iter->afi_safi_ix++;
2906 while (1) {
2907
2908 while (iter->afi_safi_ix
2909 < (int)ZEBRA_NUM_OF(afi_safis)) {
2910 table = zebra_vrf_table(
2911 afi_safis[iter->afi_safi_ix].afi,
2912 afi_safis[iter->afi_safi_ix].safi,
2913 iter->vrf_id);
2914 if (table)
2915 break;
2916
2917 iter->afi_safi_ix++;
2918 }
2919
2920 /*
2921 * Found another table in this vrf.
2922 */
2923 if (table)
2924 break;
2925
2926 /*
2927 * Done with all tables in the current vrf, go to the
2928 * next
2929 * one.
2930 */
2931 if (!vrf_id_get_next(iter->vrf_id, &iter->vrf_id))
2932 break;
2933
2934 iter->afi_safi_ix = 0;
2935 }
2936
2937 break;
2938
2939 case RIB_TABLES_ITER_S_DONE:
2940 return NULL;
2941 }
2942
2943 if (table)
2944 iter->state = RIB_TABLES_ITER_S_ITERATING;
2945 else
2946 iter->state = RIB_TABLES_ITER_S_DONE;
2947
2948 return table;
2949 }