Bug Summary

File:src/usr.sbin/eigrpd/rde_dual.c
Warning:line 896, column 5
Value stored to 'route' is never read

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple amd64-unknown-openbsd7.4 -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name rde_dual.c -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 1 -pic-is-pie -mframe-pointer=all -relaxed-aliasing -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -target-feature +retpoline-indirect-calls -target-feature +retpoline-indirect-branches -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/usr/src/usr.sbin/eigrpd/obj -resource-dir /usr/local/llvm16/lib/clang/16 -I /usr/src/usr.sbin/eigrpd -internal-isystem /usr/local/llvm16/lib/clang/16/include -internal-externc-isystem /usr/include -O2 -fdebug-compilation-dir=/usr/src/usr.sbin/eigrpd/obj -ferror-limit 19 -fwrapv -D_RET_PROTECTOR -ret-protector -fcf-protection=branch -fno-jump-tables -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -fno-builtin-malloc -fno-builtin-calloc -fno-builtin-realloc -fno-builtin-valloc -fno-builtin-free -fno-builtin-strdup -fno-builtin-strndup -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/ben/Projects/scan/2024-01-11-140451-98009-1 -x c /usr/src/usr.sbin/eigrpd/rde_dual.c
1/* $OpenBSD: rde_dual.c,v 1.31 2023/03/08 04:43:13 guenther Exp $ */
2
3/*
4 * Copyright (c) 2015 Renato Westphal <renato@openbsd.org>
5 *
6 * Permission to use, copy, modify, and distribute this software for any
7 * purpose with or without fee is hereby granted, provided that the above
8 * copyright notice and this permission notice appear in all copies.
9 *
10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 */
18
19#include <sys/types.h>
20
21#include <stdlib.h>
22#include <string.h>
23
24#include "eigrpd.h"
25#include "eigrpe.h"
26#include "rde.h"
27#include "log.h"
28
29static int dual_fsm(struct rt_node *, enum dual_event);
30static __inline int rt_compare(struct rt_node *, struct rt_node *);
31static struct rt_node *rt_find(struct eigrp *, struct rinfo *);
32static struct rt_node *rt_new(struct eigrp *, struct rinfo *);
33static struct eigrp_route *route_find(struct rde_nbr *, struct rt_node *);
34static struct eigrp_route *route_new(struct rt_node *, struct rde_nbr *,
35 struct rinfo *);
36static void route_del(struct rt_node *, struct eigrp_route *);
37static uint32_t safe_sum_uint32(uint32_t, uint32_t);
38static uint32_t safe_mul_uint32(uint32_t, uint32_t);
39static uint32_t route_composite_metric(uint8_t *, uint32_t, uint32_t,
40 uint8_t, uint8_t);
41static void route_update_metrics(struct eigrp *,
42 struct eigrp_route *, struct rinfo *);
43static void reply_outstanding_add(struct rt_node *,
44 struct rde_nbr *);
45static struct reply_node *reply_outstanding_find(struct rt_node *,
46 struct rde_nbr *);
47static void reply_outstanding_remove(struct reply_node *);
48static void reply_active_timer(int, short, void *);
49static void reply_active_start_timer(struct reply_node *);
50static void reply_active_stop_timer(struct reply_node *);
51static void reply_sia_timer(int, short, void *);
52static void reply_sia_start_timer(struct reply_node *);
53static void reply_sia_stop_timer(struct reply_node *);
54static void rinfo_fill_infinite(struct rt_node *, enum route_type,
55 struct rinfo *);
56static void rt_update_fib(struct rt_node *);
57static void rt_set_successor(struct rt_node *,
58 struct eigrp_route *);
59static struct eigrp_route *rt_get_successor_fc(struct rt_node *);
60static void rde_send_update(struct eigrp_iface *, struct rinfo *);
61static void rde_send_update_all(struct rt_node *, struct rinfo *);
62static void rde_send_query(struct eigrp_iface *, struct rinfo *,
63 int);
64static void rde_send_siaquery(struct rde_nbr *, struct rinfo *);
65static void rde_send_query_all(struct eigrp *, struct rt_node *,
66 int);
67static void rde_send_reply(struct rde_nbr *, struct rinfo *, int);
68static void rde_last_reply(struct rt_node *);
69static __inline int rde_nbr_compare(struct rde_nbr *, struct rde_nbr *);
70
71RB_GENERATE(rt_tree, rt_node, entry, rt_compare)void rt_tree_RB_INSERT_COLOR(struct rt_tree *head, struct rt_node
*elm) { struct rt_node *parent, *gparent, *tmp; while ((parent
= (elm)->entry.rbe_parent) && (parent)->entry.
rbe_color == 1) { gparent = (parent)->entry.rbe_parent; if
(parent == (gparent)->entry.rbe_left) { tmp = (gparent)->
entry.rbe_right; if (tmp && (tmp)->entry.rbe_color
== 1) { (tmp)->entry.rbe_color = 0; do { (parent)->entry
.rbe_color = 0; (gparent)->entry.rbe_color = 1; } while (0
); elm = gparent; continue; } if ((parent)->entry.rbe_right
== elm) { do { (tmp) = (parent)->entry.rbe_right; if (((parent
)->entry.rbe_right = (tmp)->entry.rbe_left)) { ((tmp)->
entry.rbe_left)->entry.rbe_parent = (parent); } do {} while
(0); if (((tmp)->entry.rbe_parent = (parent)->entry.rbe_parent
)) { if ((parent) == ((parent)->entry.rbe_parent)->entry
.rbe_left) ((parent)->entry.rbe_parent)->entry.rbe_left
= (tmp); else ((parent)->entry.rbe_parent)->entry.rbe_right
= (tmp); } else (head)->rbh_root = (tmp); (tmp)->entry
.rbe_left = (parent); (parent)->entry.rbe_parent = (tmp); do
{} while (0); if (((tmp)->entry.rbe_parent)) do {} while (
0); } while (0); tmp = parent; parent = elm; elm = tmp; } do {
(parent)->entry.rbe_color = 0; (gparent)->entry.rbe_color
= 1; } while (0); do { (tmp) = (gparent)->entry.rbe_left;
if (((gparent)->entry.rbe_left = (tmp)->entry.rbe_right
)) { ((tmp)->entry.rbe_right)->entry.rbe_parent = (gparent
); } do {} while (0); if (((tmp)->entry.rbe_parent = (gparent
)->entry.rbe_parent)) { if ((gparent) == ((gparent)->entry
.rbe_parent)->entry.rbe_left) ((gparent)->entry.rbe_parent
)->entry.rbe_left = (tmp); else ((gparent)->entry.rbe_parent
)->entry.rbe_right = (tmp); } else (head)->rbh_root = (
tmp); (tmp)->entry.rbe_right = (gparent); (gparent)->entry
.rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent
)) do {} while (0); } while (0); } else { tmp = (gparent)->
entry.rbe_left; if (tmp && (tmp)->entry.rbe_color ==
1) { (tmp)->entry.rbe_color = 0; do { (parent)->entry.
rbe_color = 0; (gparent)->entry.rbe_color = 1; } while (0)
; elm = gparent; continue; } if ((parent)->entry.rbe_left ==
elm) { do { (tmp) = (parent)->entry.rbe_left; if (((parent
)->entry.rbe_left = (tmp)->entry.rbe_right)) { ((tmp)->
entry.rbe_right)->entry.rbe_parent = (parent); } do {} while
(0); if (((tmp)->entry.rbe_parent = (parent)->entry.rbe_parent
)) { if ((parent) == ((parent)->entry.rbe_parent)->entry
.rbe_left) ((parent)->entry.rbe_parent)->entry.rbe_left
= (tmp); else ((parent)->entry.rbe_parent)->entry.rbe_right
= (tmp); } else (head)->rbh_root = (tmp); (tmp)->entry
.rbe_right = (parent); (parent)->entry.rbe_parent = (tmp);
do {} while (0); if (((tmp)->entry.rbe_parent)) do {} while
(0); } while (0); tmp = parent; parent = elm; elm = tmp; } do
{ (parent)->entry.rbe_color = 0; (gparent)->entry.rbe_color
= 1; } while (0); do { (tmp) = (gparent)->entry.rbe_right
; if (((gparent)->entry.rbe_right = (tmp)->entry.rbe_left
)) { ((tmp)->entry.rbe_left)->entry.rbe_parent = (gparent
); } do {} while (0); if (((tmp)->entry.rbe_parent = (gparent
)->entry.rbe_parent)) { if ((gparent) == ((gparent)->entry
.rbe_parent)->entry.rbe_left) ((gparent)->entry.rbe_parent
)->entry.rbe_left = (tmp); else ((gparent)->entry.rbe_parent
)->entry.rbe_right = (tmp); } else (head)->rbh_root = (
tmp); (tmp)->entry.rbe_left = (gparent); (gparent)->entry
.rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent
)) do {} while (0); } while (0); } } (head->rbh_root)->
entry.rbe_color = 0; } void rt_tree_RB_REMOVE_COLOR(struct rt_tree
*head, struct rt_node *parent, struct rt_node *elm) { struct
rt_node *tmp; while ((elm == ((void *)0) || (elm)->entry.
rbe_color == 0) && elm != (head)->rbh_root) { if (
(parent)->entry.rbe_left == elm) { tmp = (parent)->entry
.rbe_right; if ((tmp)->entry.rbe_color == 1) { do { (tmp)->
entry.rbe_color = 0; (parent)->entry.rbe_color = 1; } while
(0); do { (tmp) = (parent)->entry.rbe_right; if (((parent
)->entry.rbe_right = (tmp)->entry.rbe_left)) { ((tmp)->
entry.rbe_left)->entry.rbe_parent = (parent); } do {} while
(0); if (((tmp)->entry.rbe_parent = (parent)->entry.rbe_parent
)) { if ((parent) == ((parent)->entry.rbe_parent)->entry
.rbe_left) ((parent)->entry.rbe_parent)->entry.rbe_left
= (tmp); else ((parent)->entry.rbe_parent)->entry.rbe_right
= (tmp); } else (head)->rbh_root = (tmp); (tmp)->entry
.rbe_left = (parent); (parent)->entry.rbe_parent = (tmp); do
{} while (0); if (((tmp)->entry.rbe_parent)) do {} while (
0); } while (0); tmp = (parent)->entry.rbe_right; } if (((
tmp)->entry.rbe_left == ((void *)0) || ((tmp)->entry.rbe_left
)->entry.rbe_color == 0) && ((tmp)->entry.rbe_right
== ((void *)0) || ((tmp)->entry.rbe_right)->entry.rbe_color
== 0)) { (tmp)->entry.rbe_color = 1; elm = parent; parent
= (elm)->entry.rbe_parent; } else { if ((tmp)->entry.rbe_right
== ((void *)0) || ((tmp)->entry.rbe_right)->entry.rbe_color
== 0) { struct rt_node *oleft; if ((oleft = (tmp)->entry.
rbe_left)) (oleft)->entry.rbe_color = 0; (tmp)->entry.rbe_color
= 1; do { (oleft) = (tmp)->entry.rbe_left; if (((tmp)->
entry.rbe_left = (oleft)->entry.rbe_right)) { ((oleft)->
entry.rbe_right)->entry.rbe_parent = (tmp); } do {} while (
0); if (((oleft)->entry.rbe_parent = (tmp)->entry.rbe_parent
)) { if ((tmp) == ((tmp)->entry.rbe_parent)->entry.rbe_left
) ((tmp)->entry.rbe_parent)->entry.rbe_left = (oleft); else
((tmp)->entry.rbe_parent)->entry.rbe_right = (oleft); }
else (head)->rbh_root = (oleft); (oleft)->entry.rbe_right
= (tmp); (tmp)->entry.rbe_parent = (oleft); do {} while (
0); if (((oleft)->entry.rbe_parent)) do {} while (0); } while
(0); tmp = (parent)->entry.rbe_right; } (tmp)->entry.rbe_color
= (parent)->entry.rbe_color; (parent)->entry.rbe_color
= 0; if ((tmp)->entry.rbe_right) ((tmp)->entry.rbe_right
)->entry.rbe_color = 0; do { (tmp) = (parent)->entry.rbe_right
; if (((parent)->entry.rbe_right = (tmp)->entry.rbe_left
)) { ((tmp)->entry.rbe_left)->entry.rbe_parent = (parent
); } do {} while (0); if (((tmp)->entry.rbe_parent = (parent
)->entry.rbe_parent)) { if ((parent) == ((parent)->entry
.rbe_parent)->entry.rbe_left) ((parent)->entry.rbe_parent
)->entry.rbe_left = (tmp); else ((parent)->entry.rbe_parent
)->entry.rbe_right = (tmp); } else (head)->rbh_root = (
tmp); (tmp)->entry.rbe_left = (parent); (parent)->entry
.rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent
)) do {} while (0); } while (0); elm = (head)->rbh_root; break
; } } else { tmp = (parent)->entry.rbe_left; if ((tmp)->
entry.rbe_color == 1) { do { (tmp)->entry.rbe_color = 0; (
parent)->entry.rbe_color = 1; } while (0); do { (tmp) = (parent
)->entry.rbe_left; if (((parent)->entry.rbe_left = (tmp
)->entry.rbe_right)) { ((tmp)->entry.rbe_right)->entry
.rbe_parent = (parent); } do {} while (0); if (((tmp)->entry
.rbe_parent = (parent)->entry.rbe_parent)) { if ((parent) ==
((parent)->entry.rbe_parent)->entry.rbe_left) ((parent
)->entry.rbe_parent)->entry.rbe_left = (tmp); else ((parent
)->entry.rbe_parent)->entry.rbe_right = (tmp); } else (
head)->rbh_root = (tmp); (tmp)->entry.rbe_right = (parent
); (parent)->entry.rbe_parent = (tmp); do {} while (0); if
(((tmp)->entry.rbe_parent)) do {} while (0); } while (0);
tmp = (parent)->entry.rbe_left; } if (((tmp)->entry.rbe_left
== ((void *)0) || ((tmp)->entry.rbe_left)->entry.rbe_color
== 0) && ((tmp)->entry.rbe_right == ((void *)0) ||
((tmp)->entry.rbe_right)->entry.rbe_color == 0)) { (tmp
)->entry.rbe_color = 1; elm = parent; parent = (elm)->entry
.rbe_parent; } else { if ((tmp)->entry.rbe_left == ((void *
)0) || ((tmp)->entry.rbe_left)->entry.rbe_color == 0) {
struct rt_node *oright; if ((oright = (tmp)->entry.rbe_right
)) (oright)->entry.rbe_color = 0; (tmp)->entry.rbe_color
= 1; do { (oright) = (tmp)->entry.rbe_right; if (((tmp)->
entry.rbe_right = (oright)->entry.rbe_left)) { ((oright)->
entry.rbe_left)->entry.rbe_parent = (tmp); } do {} while (
0); if (((oright)->entry.rbe_parent = (tmp)->entry.rbe_parent
)) { if ((tmp) == ((tmp)->entry.rbe_parent)->entry.rbe_left
) ((tmp)->entry.rbe_parent)->entry.rbe_left = (oright);
else ((tmp)->entry.rbe_parent)->entry.rbe_right = (oright
); } else (head)->rbh_root = (oright); (oright)->entry.
rbe_left = (tmp); (tmp)->entry.rbe_parent = (oright); do {
} while (0); if (((oright)->entry.rbe_parent)) do {} while
(0); } while (0); tmp = (parent)->entry.rbe_left; } (tmp)
->entry.rbe_color = (parent)->entry.rbe_color; (parent)
->entry.rbe_color = 0; if ((tmp)->entry.rbe_left) ((tmp
)->entry.rbe_left)->entry.rbe_color = 0; do { (tmp) = (
parent)->entry.rbe_left; if (((parent)->entry.rbe_left =
(tmp)->entry.rbe_right)) { ((tmp)->entry.rbe_right)->
entry.rbe_parent = (parent); } do {} while (0); if (((tmp)->
entry.rbe_parent = (parent)->entry.rbe_parent)) { if ((parent
) == ((parent)->entry.rbe_parent)->entry.rbe_left) ((parent
)->entry.rbe_parent)->entry.rbe_left = (tmp); else ((parent
)->entry.rbe_parent)->entry.rbe_right = (tmp); } else (
head)->rbh_root = (tmp); (tmp)->entry.rbe_right = (parent
); (parent)->entry.rbe_parent = (tmp); do {} while (0); if
(((tmp)->entry.rbe_parent)) do {} while (0); } while (0);
elm = (head)->rbh_root; break; } } } if (elm) (elm)->entry
.rbe_color = 0; } struct rt_node * rt_tree_RB_REMOVE(struct rt_tree
*head, struct rt_node *elm) { struct rt_node *child, *parent
, *old = elm; int color; if ((elm)->entry.rbe_left == ((void
*)0)) child = (elm)->entry.rbe_right; else if ((elm)->
entry.rbe_right == ((void *)0)) child = (elm)->entry.rbe_left
; else { struct rt_node *left; elm = (elm)->entry.rbe_right
; while ((left = (elm)->entry.rbe_left)) elm = left; child
= (elm)->entry.rbe_right; parent = (elm)->entry.rbe_parent
; color = (elm)->entry.rbe_color; if (child) (child)->entry
.rbe_parent = parent; if (parent) { if ((parent)->entry.rbe_left
== elm) (parent)->entry.rbe_left = child; else (parent)->
entry.rbe_right = child; do {} while (0); } else (head)->rbh_root
= child; if ((elm)->entry.rbe_parent == old) parent = elm
; (elm)->entry = (old)->entry; if ((old)->entry.rbe_parent
) { if (((old)->entry.rbe_parent)->entry.rbe_left == old
) ((old)->entry.rbe_parent)->entry.rbe_left = elm; else
((old)->entry.rbe_parent)->entry.rbe_right = elm; do {
} while (0); } else (head)->rbh_root = elm; ((old)->entry
.rbe_left)->entry.rbe_parent = elm; if ((old)->entry.rbe_right
) ((old)->entry.rbe_right)->entry.rbe_parent = elm; if (
parent) { left = parent; do { do {} while (0); } while ((left
= (left)->entry.rbe_parent)); } goto color; } parent = (elm
)->entry.rbe_parent; color = (elm)->entry.rbe_color; if
(child) (child)->entry.rbe_parent = parent; if (parent) {
if ((parent)->entry.rbe_left == elm) (parent)->entry.rbe_left
= child; else (parent)->entry.rbe_right = child; do {} while
(0); } else (head)->rbh_root = child; color: if (color ==
0) rt_tree_RB_REMOVE_COLOR(head, parent, child); return (old
); } struct rt_node * rt_tree_RB_INSERT(struct rt_tree *head,
struct rt_node *elm) { struct rt_node *tmp; struct rt_node *
parent = ((void *)0); int comp = 0; tmp = (head)->rbh_root
; while (tmp) { parent = tmp; comp = (rt_compare)(elm, parent
); if (comp < 0) tmp = (tmp)->entry.rbe_left; else if (
comp > 0) tmp = (tmp)->entry.rbe_right; else return (tmp
); } do { (elm)->entry.rbe_parent = parent; (elm)->entry
.rbe_left = (elm)->entry.rbe_right = ((void *)0); (elm)->
entry.rbe_color = 1; } while (0); if (parent != ((void *)0)) {
if (comp < 0) (parent)->entry.rbe_left = elm; else (parent
)->entry.rbe_right = elm; do {} while (0); } else (head)->
rbh_root = elm; rt_tree_RB_INSERT_COLOR(head, elm); return ((
(void *)0)); } struct rt_node * rt_tree_RB_FIND(struct rt_tree
*head, struct rt_node *elm) { struct rt_node *tmp = (head)->
rbh_root; int comp; while (tmp) { comp = rt_compare(elm, tmp)
; if (comp < 0) tmp = (tmp)->entry.rbe_left; else if (comp
> 0) tmp = (tmp)->entry.rbe_right; else return (tmp); }
return (((void *)0)); } struct rt_node * rt_tree_RB_NFIND(struct
rt_tree *head, struct rt_node *elm) { struct rt_node *tmp = (
head)->rbh_root; struct rt_node *res = ((void *)0); int comp
; while (tmp) { comp = rt_compare(elm, tmp); if (comp < 0)
{ res = tmp; tmp = (tmp)->entry.rbe_left; } else if (comp
> 0) tmp = (tmp)->entry.rbe_right; else return (tmp); }
return (res); } struct rt_node * rt_tree_RB_NEXT(struct rt_node
*elm) { if ((elm)->entry.rbe_right) { elm = (elm)->entry
.rbe_right; while ((elm)->entry.rbe_left) elm = (elm)->
entry.rbe_left; } else { if ((elm)->entry.rbe_parent &&
(elm == ((elm)->entry.rbe_parent)->entry.rbe_left)) elm
= (elm)->entry.rbe_parent; else { while ((elm)->entry.
rbe_parent && (elm == ((elm)->entry.rbe_parent)->
entry.rbe_right)) elm = (elm)->entry.rbe_parent; elm = (elm
)->entry.rbe_parent; } } return (elm); } struct rt_node * rt_tree_RB_PREV
(struct rt_node *elm) { if ((elm)->entry.rbe_left) { elm =
(elm)->entry.rbe_left; while ((elm)->entry.rbe_right) elm
= (elm)->entry.rbe_right; } else { if ((elm)->entry.rbe_parent
&& (elm == ((elm)->entry.rbe_parent)->entry.rbe_right
)) elm = (elm)->entry.rbe_parent; else { while ((elm)->
entry.rbe_parent && (elm == ((elm)->entry.rbe_parent
)->entry.rbe_left)) elm = (elm)->entry.rbe_parent; elm =
(elm)->entry.rbe_parent; } } return (elm); } struct rt_node
* rt_tree_RB_MINMAX(struct rt_tree *head, int val) { struct rt_node
*tmp = (head)->rbh_root; struct rt_node *parent = ((void *
)0); while (tmp) { parent = tmp; if (val < 0) tmp = (tmp)->
entry.rbe_left; else tmp = (tmp)->entry.rbe_right; } return
(parent); }
72RB_GENERATE(rde_nbr_head, rde_nbr, entry, rde_nbr_compare)void rde_nbr_head_RB_INSERT_COLOR(struct rde_nbr_head *head, struct
rde_nbr *elm) { struct rde_nbr *parent, *gparent, *tmp; while
((parent = (elm)->entry.rbe_parent) && (parent)->
entry.rbe_color == 1) { gparent = (parent)->entry.rbe_parent
; if (parent == (gparent)->entry.rbe_left) { tmp = (gparent
)->entry.rbe_right; if (tmp && (tmp)->entry.rbe_color
== 1) { (tmp)->entry.rbe_color = 0; do { (parent)->entry
.rbe_color = 0; (gparent)->entry.rbe_color = 1; } while (0
); elm = gparent; continue; } if ((parent)->entry.rbe_right
== elm) { do { (tmp) = (parent)->entry.rbe_right; if (((parent
)->entry.rbe_right = (tmp)->entry.rbe_left)) { ((tmp)->
entry.rbe_left)->entry.rbe_parent = (parent); } do {} while
(0); if (((tmp)->entry.rbe_parent = (parent)->entry.rbe_parent
)) { if ((parent) == ((parent)->entry.rbe_parent)->entry
.rbe_left) ((parent)->entry.rbe_parent)->entry.rbe_left
= (tmp); else ((parent)->entry.rbe_parent)->entry.rbe_right
= (tmp); } else (head)->rbh_root = (tmp); (tmp)->entry
.rbe_left = (parent); (parent)->entry.rbe_parent = (tmp); do
{} while (0); if (((tmp)->entry.rbe_parent)) do {} while (
0); } while (0); tmp = parent; parent = elm; elm = tmp; } do {
(parent)->entry.rbe_color = 0; (gparent)->entry.rbe_color
= 1; } while (0); do { (tmp) = (gparent)->entry.rbe_left;
if (((gparent)->entry.rbe_left = (tmp)->entry.rbe_right
)) { ((tmp)->entry.rbe_right)->entry.rbe_parent = (gparent
); } do {} while (0); if (((tmp)->entry.rbe_parent = (gparent
)->entry.rbe_parent)) { if ((gparent) == ((gparent)->entry
.rbe_parent)->entry.rbe_left) ((gparent)->entry.rbe_parent
)->entry.rbe_left = (tmp); else ((gparent)->entry.rbe_parent
)->entry.rbe_right = (tmp); } else (head)->rbh_root = (
tmp); (tmp)->entry.rbe_right = (gparent); (gparent)->entry
.rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent
)) do {} while (0); } while (0); } else { tmp = (gparent)->
entry.rbe_left; if (tmp && (tmp)->entry.rbe_color ==
1) { (tmp)->entry.rbe_color = 0; do { (parent)->entry.
rbe_color = 0; (gparent)->entry.rbe_color = 1; } while (0)
; elm = gparent; continue; } if ((parent)->entry.rbe_left ==
elm) { do { (tmp) = (parent)->entry.rbe_left; if (((parent
)->entry.rbe_left = (tmp)->entry.rbe_right)) { ((tmp)->
entry.rbe_right)->entry.rbe_parent = (parent); } do {} while
(0); if (((tmp)->entry.rbe_parent = (parent)->entry.rbe_parent
)) { if ((parent) == ((parent)->entry.rbe_parent)->entry
.rbe_left) ((parent)->entry.rbe_parent)->entry.rbe_left
= (tmp); else ((parent)->entry.rbe_parent)->entry.rbe_right
= (tmp); } else (head)->rbh_root = (tmp); (tmp)->entry
.rbe_right = (parent); (parent)->entry.rbe_parent = (tmp);
do {} while (0); if (((tmp)->entry.rbe_parent)) do {} while
(0); } while (0); tmp = parent; parent = elm; elm = tmp; } do
{ (parent)->entry.rbe_color = 0; (gparent)->entry.rbe_color
= 1; } while (0); do { (tmp) = (gparent)->entry.rbe_right
; if (((gparent)->entry.rbe_right = (tmp)->entry.rbe_left
)) { ((tmp)->entry.rbe_left)->entry.rbe_parent = (gparent
); } do {} while (0); if (((tmp)->entry.rbe_parent = (gparent
)->entry.rbe_parent)) { if ((gparent) == ((gparent)->entry
.rbe_parent)->entry.rbe_left) ((gparent)->entry.rbe_parent
)->entry.rbe_left = (tmp); else ((gparent)->entry.rbe_parent
)->entry.rbe_right = (tmp); } else (head)->rbh_root = (
tmp); (tmp)->entry.rbe_left = (gparent); (gparent)->entry
.rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent
)) do {} while (0); } while (0); } } (head->rbh_root)->
entry.rbe_color = 0; } void rde_nbr_head_RB_REMOVE_COLOR(struct
rde_nbr_head *head, struct rde_nbr *parent, struct rde_nbr *
elm) { struct rde_nbr *tmp; while ((elm == ((void *)0) || (elm
)->entry.rbe_color == 0) && elm != (head)->rbh_root
) { if ((parent)->entry.rbe_left == elm) { tmp = (parent)->
entry.rbe_right; if ((tmp)->entry.rbe_color == 1) { do { (
tmp)->entry.rbe_color = 0; (parent)->entry.rbe_color = 1
; } while (0); do { (tmp) = (parent)->entry.rbe_right; if (
((parent)->entry.rbe_right = (tmp)->entry.rbe_left)) { (
(tmp)->entry.rbe_left)->entry.rbe_parent = (parent); } do
{} while (0); if (((tmp)->entry.rbe_parent = (parent)->
entry.rbe_parent)) { if ((parent) == ((parent)->entry.rbe_parent
)->entry.rbe_left) ((parent)->entry.rbe_parent)->entry
.rbe_left = (tmp); else ((parent)->entry.rbe_parent)->entry
.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)
->entry.rbe_left = (parent); (parent)->entry.rbe_parent
= (tmp); do {} while (0); if (((tmp)->entry.rbe_parent)) do
{} while (0); } while (0); tmp = (parent)->entry.rbe_right
; } if (((tmp)->entry.rbe_left == ((void *)0) || ((tmp)->
entry.rbe_left)->entry.rbe_color == 0) && ((tmp)->
entry.rbe_right == ((void *)0) || ((tmp)->entry.rbe_right)
->entry.rbe_color == 0)) { (tmp)->entry.rbe_color = 1; elm
= parent; parent = (elm)->entry.rbe_parent; } else { if (
(tmp)->entry.rbe_right == ((void *)0) || ((tmp)->entry.
rbe_right)->entry.rbe_color == 0) { struct rde_nbr *oleft;
if ((oleft = (tmp)->entry.rbe_left)) (oleft)->entry.rbe_color
= 0; (tmp)->entry.rbe_color = 1; do { (oleft) = (tmp)->
entry.rbe_left; if (((tmp)->entry.rbe_left = (oleft)->entry
.rbe_right)) { ((oleft)->entry.rbe_right)->entry.rbe_parent
= (tmp); } do {} while (0); if (((oleft)->entry.rbe_parent
= (tmp)->entry.rbe_parent)) { if ((tmp) == ((tmp)->entry
.rbe_parent)->entry.rbe_left) ((tmp)->entry.rbe_parent)
->entry.rbe_left = (oleft); else ((tmp)->entry.rbe_parent
)->entry.rbe_right = (oleft); } else (head)->rbh_root =
(oleft); (oleft)->entry.rbe_right = (tmp); (tmp)->entry
.rbe_parent = (oleft); do {} while (0); if (((oleft)->entry
.rbe_parent)) do {} while (0); } while (0); tmp = (parent)->
entry.rbe_right; } (tmp)->entry.rbe_color = (parent)->entry
.rbe_color; (parent)->entry.rbe_color = 0; if ((tmp)->entry
.rbe_right) ((tmp)->entry.rbe_right)->entry.rbe_color =
0; do { (tmp) = (parent)->entry.rbe_right; if (((parent)->
entry.rbe_right = (tmp)->entry.rbe_left)) { ((tmp)->entry
.rbe_left)->entry.rbe_parent = (parent); } do {} while (0)
; if (((tmp)->entry.rbe_parent = (parent)->entry.rbe_parent
)) { if ((parent) == ((parent)->entry.rbe_parent)->entry
.rbe_left) ((parent)->entry.rbe_parent)->entry.rbe_left
= (tmp); else ((parent)->entry.rbe_parent)->entry.rbe_right
= (tmp); } else (head)->rbh_root = (tmp); (tmp)->entry
.rbe_left = (parent); (parent)->entry.rbe_parent = (tmp); do
{} while (0); if (((tmp)->entry.rbe_parent)) do {} while (
0); } while (0); elm = (head)->rbh_root; break; } } else {
tmp = (parent)->entry.rbe_left; if ((tmp)->entry.rbe_color
== 1) { do { (tmp)->entry.rbe_color = 0; (parent)->entry
.rbe_color = 1; } while (0); do { (tmp) = (parent)->entry.
rbe_left; if (((parent)->entry.rbe_left = (tmp)->entry.
rbe_right)) { ((tmp)->entry.rbe_right)->entry.rbe_parent
= (parent); } do {} while (0); if (((tmp)->entry.rbe_parent
= (parent)->entry.rbe_parent)) { if ((parent) == ((parent
)->entry.rbe_parent)->entry.rbe_left) ((parent)->entry
.rbe_parent)->entry.rbe_left = (tmp); else ((parent)->entry
.rbe_parent)->entry.rbe_right = (tmp); } else (head)->rbh_root
= (tmp); (tmp)->entry.rbe_right = (parent); (parent)->
entry.rbe_parent = (tmp); do {} while (0); if (((tmp)->entry
.rbe_parent)) do {} while (0); } while (0); tmp = (parent)->
entry.rbe_left; } if (((tmp)->entry.rbe_left == ((void *)0
) || ((tmp)->entry.rbe_left)->entry.rbe_color == 0) &&
((tmp)->entry.rbe_right == ((void *)0) || ((tmp)->entry
.rbe_right)->entry.rbe_color == 0)) { (tmp)->entry.rbe_color
= 1; elm = parent; parent = (elm)->entry.rbe_parent; } else
{ if ((tmp)->entry.rbe_left == ((void *)0) || ((tmp)->
entry.rbe_left)->entry.rbe_color == 0) { struct rde_nbr *oright
; if ((oright = (tmp)->entry.rbe_right)) (oright)->entry
.rbe_color = 0; (tmp)->entry.rbe_color = 1; do { (oright) =
(tmp)->entry.rbe_right; if (((tmp)->entry.rbe_right = (
oright)->entry.rbe_left)) { ((oright)->entry.rbe_left)->
entry.rbe_parent = (tmp); } do {} while (0); if (((oright)->
entry.rbe_parent = (tmp)->entry.rbe_parent)) { if ((tmp) ==
((tmp)->entry.rbe_parent)->entry.rbe_left) ((tmp)->
entry.rbe_parent)->entry.rbe_left = (oright); else ((tmp)->
entry.rbe_parent)->entry.rbe_right = (oright); } else (head
)->rbh_root = (oright); (oright)->entry.rbe_left = (tmp
); (tmp)->entry.rbe_parent = (oright); do {} while (0); if
(((oright)->entry.rbe_parent)) do {} while (0); } while (
0); tmp = (parent)->entry.rbe_left; } (tmp)->entry.rbe_color
= (parent)->entry.rbe_color; (parent)->entry.rbe_color
= 0; if ((tmp)->entry.rbe_left) ((tmp)->entry.rbe_left
)->entry.rbe_color = 0; do { (tmp) = (parent)->entry.rbe_left
; if (((parent)->entry.rbe_left = (tmp)->entry.rbe_right
)) { ((tmp)->entry.rbe_right)->entry.rbe_parent = (parent
); } do {} while (0); if (((tmp)->entry.rbe_parent = (parent
)->entry.rbe_parent)) { if ((parent) == ((parent)->entry
.rbe_parent)->entry.rbe_left) ((parent)->entry.rbe_parent
)->entry.rbe_left = (tmp); else ((parent)->entry.rbe_parent
)->entry.rbe_right = (tmp); } else (head)->rbh_root = (
tmp); (tmp)->entry.rbe_right = (parent); (parent)->entry
.rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent
)) do {} while (0); } while (0); elm = (head)->rbh_root; break
; } } } if (elm) (elm)->entry.rbe_color = 0; } struct rde_nbr
* rde_nbr_head_RB_REMOVE(struct rde_nbr_head *head, struct rde_nbr
*elm) { struct rde_nbr *child, *parent, *old = elm; int color
; if ((elm)->entry.rbe_left == ((void *)0)) child = (elm)->
entry.rbe_right; else if ((elm)->entry.rbe_right == ((void
*)0)) child = (elm)->entry.rbe_left; else { struct rde_nbr
*left; elm = (elm)->entry.rbe_right; while ((left = (elm)
->entry.rbe_left)) elm = left; child = (elm)->entry.rbe_right
; parent = (elm)->entry.rbe_parent; color = (elm)->entry
.rbe_color; if (child) (child)->entry.rbe_parent = parent;
if (parent) { if ((parent)->entry.rbe_left == elm) (parent
)->entry.rbe_left = child; else (parent)->entry.rbe_right
= child; do {} while (0); } else (head)->rbh_root = child
; if ((elm)->entry.rbe_parent == old) parent = elm; (elm)->
entry = (old)->entry; if ((old)->entry.rbe_parent) { if
(((old)->entry.rbe_parent)->entry.rbe_left == old) ((old
)->entry.rbe_parent)->entry.rbe_left = elm; else ((old)
->entry.rbe_parent)->entry.rbe_right = elm; do {} while
(0); } else (head)->rbh_root = elm; ((old)->entry.rbe_left
)->entry.rbe_parent = elm; if ((old)->entry.rbe_right) (
(old)->entry.rbe_right)->entry.rbe_parent = elm; if (parent
) { left = parent; do { do {} while (0); } while ((left = (left
)->entry.rbe_parent)); } goto color; } parent = (elm)->
entry.rbe_parent; color = (elm)->entry.rbe_color; if (child
) (child)->entry.rbe_parent = parent; if (parent) { if ((parent
)->entry.rbe_left == elm) (parent)->entry.rbe_left = child
; else (parent)->entry.rbe_right = child; do {} while (0);
} else (head)->rbh_root = child; color: if (color == 0) rde_nbr_head_RB_REMOVE_COLOR
(head, parent, child); return (old); } struct rde_nbr * rde_nbr_head_RB_INSERT
(struct rde_nbr_head *head, struct rde_nbr *elm) { struct rde_nbr
*tmp; struct rde_nbr *parent = ((void *)0); int comp = 0; tmp
= (head)->rbh_root; while (tmp) { parent = tmp; comp = (rde_nbr_compare
)(elm, parent); if (comp < 0) tmp = (tmp)->entry.rbe_left
; else if (comp > 0) tmp = (tmp)->entry.rbe_right; else
return (tmp); } do { (elm)->entry.rbe_parent = parent; (elm
)->entry.rbe_left = (elm)->entry.rbe_right = ((void *)0
); (elm)->entry.rbe_color = 1; } while (0); if (parent != (
(void *)0)) { if (comp < 0) (parent)->entry.rbe_left = elm
; else (parent)->entry.rbe_right = elm; do {} while (0); }
else (head)->rbh_root = elm; rde_nbr_head_RB_INSERT_COLOR
(head, elm); return (((void *)0)); } struct rde_nbr * rde_nbr_head_RB_FIND
(struct rde_nbr_head *head, struct rde_nbr *elm) { struct rde_nbr
*tmp = (head)->rbh_root; int comp; while (tmp) { comp = rde_nbr_compare
(elm, tmp); if (comp < 0) tmp = (tmp)->entry.rbe_left; else
if (comp > 0) tmp = (tmp)->entry.rbe_right; else return
(tmp); } return (((void *)0)); } struct rde_nbr * rde_nbr_head_RB_NFIND
(struct rde_nbr_head *head, struct rde_nbr *elm) { struct rde_nbr
*tmp = (head)->rbh_root; struct rde_nbr *res = ((void *)0
); int comp; while (tmp) { comp = rde_nbr_compare(elm, tmp); if
(comp < 0) { res = tmp; tmp = (tmp)->entry.rbe_left; }
else if (comp > 0) tmp = (tmp)->entry.rbe_right; else return
(tmp); } return (res); } struct rde_nbr * rde_nbr_head_RB_NEXT
(struct rde_nbr *elm) { if ((elm)->entry.rbe_right) { elm =
(elm)->entry.rbe_right; while ((elm)->entry.rbe_left) elm
= (elm)->entry.rbe_left; } else { if ((elm)->entry.rbe_parent
&& (elm == ((elm)->entry.rbe_parent)->entry.rbe_left
)) elm = (elm)->entry.rbe_parent; else { while ((elm)->
entry.rbe_parent && (elm == ((elm)->entry.rbe_parent
)->entry.rbe_right)) elm = (elm)->entry.rbe_parent; elm
= (elm)->entry.rbe_parent; } } return (elm); } struct rde_nbr
* rde_nbr_head_RB_PREV(struct rde_nbr *elm) { if ((elm)->
entry.rbe_left) { elm = (elm)->entry.rbe_left; while ((elm
)->entry.rbe_right) elm = (elm)->entry.rbe_right; } else
{ if ((elm)->entry.rbe_parent && (elm == ((elm)->
entry.rbe_parent)->entry.rbe_right)) elm = (elm)->entry
.rbe_parent; else { while ((elm)->entry.rbe_parent &&
(elm == ((elm)->entry.rbe_parent)->entry.rbe_left)) elm
= (elm)->entry.rbe_parent; elm = (elm)->entry.rbe_parent
; } } return (elm); } struct rde_nbr * rde_nbr_head_RB_MINMAX
(struct rde_nbr_head *head, int val) { struct rde_nbr *tmp = (
head)->rbh_root; struct rde_nbr *parent = ((void *)0); while
(tmp) { parent = tmp; if (val < 0) tmp = (tmp)->entry.
rbe_left; else tmp = (tmp)->entry.rbe_right; } return (parent
); }
73
74struct rde_nbr_head rde_nbrs = RB_INITIALIZER(&rde_nbrs){ ((void *)0) };
75
76/*
77 * NOTE: events that don't cause a state transition aren't triggered to avoid
78 * too much verbosity and are here mostly for illustration purposes.
79 */
80static struct {
81 int state;
82 enum dual_event event;
83 int new_state;
84} dual_fsm_tbl[] = {
85 /* current state event resulting state */
86/* Passive */
87 {DUAL_STA_PASSIVE0x0001, DUAL_EVT_1, 0},
88 {DUAL_STA_PASSIVE0x0001, DUAL_EVT_2, 0},
89 {DUAL_STA_PASSIVE0x0001, DUAL_EVT_3, DUAL_STA_ACTIVE30x0010},
90 {DUAL_STA_PASSIVE0x0001, DUAL_EVT_4, DUAL_STA_ACTIVE10x0004},
91/* Active Oij=0 */
92 {DUAL_STA_ACTIVE00x0002, DUAL_EVT_5, DUAL_STA_ACTIVE20x0008},
93 {DUAL_STA_ACTIVE00x0002, DUAL_EVT_11, DUAL_STA_ACTIVE10x0004},
94 {DUAL_STA_ACTIVE00x0002, DUAL_EVT_14, DUAL_STA_PASSIVE0x0001},
95/* Active Oij=1 */
96 {DUAL_STA_ACTIVE10x0004, DUAL_EVT_5, DUAL_STA_ACTIVE20x0008},
97 {DUAL_STA_ACTIVE10x0004, DUAL_EVT_9, DUAL_STA_ACTIVE00x0002},
98 {DUAL_STA_ACTIVE10x0004, DUAL_EVT_15, DUAL_STA_PASSIVE0x0001},
99/* Active Oij=2 */
100 {DUAL_STA_ACTIVE20x0008, DUAL_EVT_12, DUAL_STA_ACTIVE30x0010},
101 {DUAL_STA_ACTIVE20x0008, DUAL_EVT_16, DUAL_STA_PASSIVE0x0001},
102/* Active Oij=3 */
103 {DUAL_STA_ACTIVE30x0010, DUAL_EVT_10, DUAL_STA_ACTIVE20x0008},
104 {DUAL_STA_ACTIVE30x0010, DUAL_EVT_13, DUAL_STA_PASSIVE0x0001},
105/* Active (all) */
106 {DUAL_STA_ACTIVE_ALL(0x0002 | 0x0004 | 0x0008 | 0x0010), DUAL_EVT_6, 0},
107 {DUAL_STA_ACTIVE_ALL(0x0002 | 0x0004 | 0x0008 | 0x0010), DUAL_EVT_7, 0},
108 {DUAL_STA_ACTIVE_ALL(0x0002 | 0x0004 | 0x0008 | 0x0010), DUAL_EVT_8, 0},
109/* sentinel */
110 {-1, 0, 0},
111};
112
113static const char * const dual_event_names[] = {
114 "DUAL_EVT_1",
115 "DUAL_EVT_2",
116 "DUAL_EVT_3",
117 "DUAL_EVT_4",
118 "DUAL_EVT_5",
119 "DUAL_EVT_6",
120 "DUAL_EVT_7",
121 "DUAL_EVT_8",
122 "DUAL_EVT_9",
123 "DUAL_EVT_10",
124 "DUAL_EVT_11",
125 "DUAL_EVT_12",
126 "DUAL_EVT_13",
127 "DUAL_EVT_14",
128 "DUAL_EVT_15",
129 "DUAL_EVT_16"
130};
131
132static int
133dual_fsm(struct rt_node *rn, enum dual_event event)
134{
135 int old_state;
136 int new_state = 0;
137 int i;
138
139 old_state = rn->state;
140 for (i = 0; dual_fsm_tbl[i].state != -1; i++)
141 if ((dual_fsm_tbl[i].state & old_state) &&
142 (dual_fsm_tbl[i].event == event)) {
143 new_state = dual_fsm_tbl[i].new_state;
144 break;
145 }
146
147 if (dual_fsm_tbl[i].state == -1) {
148 /* event outside of the defined fsm, ignore it. */
149 log_warnx("%s: route %s, event %s not expected in state %s",
150 __func__, log_prefix(rn), dual_event_names[event],
151 dual_state_name(old_state));
152 return (0);
153 }
154
155 if (new_state != 0)
156 rn->state = new_state;
157
158 if (old_state != rn->state) {
159 log_debug("%s: event %s changing state for prefix %s "
160 "from %s to %s", __func__, dual_event_names[event],
161 log_prefix(rn), dual_state_name(old_state),
162 dual_state_name(rn->state));
163
164 if (old_state == DUAL_STA_PASSIVE0x0001 ||
165 new_state == DUAL_STA_PASSIVE0x0001)
166 rt_update_fib(rn);
167 }
168
169 return (0);
170}
171
172static __inline int
173rt_compare(struct rt_node *a, struct rt_node *b)
174{
175 int addrcmp;
176
177 addrcmp = eigrp_addrcmp(a->eigrp->af, &a->prefix, &b->prefix);
178 if (addrcmp != 0)
179 return (addrcmp);
180
181 if (a->prefixlen < b->prefixlen)
182 return (-1);
183 if (a->prefixlen > b->prefixlen)
184 return (1);
185
186 return (0);
187}
188
189static struct rt_node *
190rt_find(struct eigrp *eigrp, struct rinfo *ri)
191{
192 struct rt_node rn;
193
194 rn.eigrp = eigrp;
195 rn.prefix = ri->prefix;
196 rn.prefixlen = ri->prefixlen;
197
198 return (RB_FIND(rt_tree, &eigrp->topology, &rn)rt_tree_RB_FIND(&eigrp->topology, &rn));
199}
200
201static struct rt_node *
202rt_new(struct eigrp *eigrp, struct rinfo *ri)
203{
204 struct rt_node *rn;
205
206 if ((rn = calloc(1, sizeof(*rn))) == NULL((void *)0))
207 fatal("rt_new");
208
209 rn->eigrp = eigrp;
210 rn->prefix = ri->prefix;
211 rn->prefixlen = ri->prefixlen;
212 rn->state = DUAL_STA_PASSIVE0x0001;
213 TAILQ_INIT(&rn->routes)do { (&rn->routes)->tqh_first = ((void *)0); (&
rn->routes)->tqh_last = &(&rn->routes)->tqh_first
; } while (0);
214 TAILQ_INIT(&rn->rijk)do { (&rn->rijk)->tqh_first = ((void *)0); (&rn
->rijk)->tqh_last = &(&rn->rijk)->tqh_first
; } while (0);
215 rt_set_successor(rn, NULL((void *)0));
216
217 if (RB_INSERT(rt_tree, &eigrp->topology, rn)rt_tree_RB_INSERT(&eigrp->topology, rn) != NULL((void *)0)) {
218 log_warnx("%s failed for %s", __func__, log_prefix(rn));
219 free(rn);
220 return (NULL((void *)0));
221 }
222
223 log_debug("%s: prefix %s", __func__, log_prefix(rn));
224
225 return (rn);
226}
227
228void
229rt_del(struct rt_node *rn)
230{
231 struct eigrp_route *route;
232 struct reply_node *reply;
233
234 log_debug("%s: prefix %s", __func__, log_prefix(rn));
235
236 while ((reply = TAILQ_FIRST(&rn->rijk)((&rn->rijk)->tqh_first)) != NULL((void *)0))
237 reply_outstanding_remove(reply);
238 while ((route = TAILQ_FIRST(&rn->routes)((&rn->routes)->tqh_first)) != NULL((void *)0))
239 route_del(rn, route);
240 RB_REMOVE(rt_tree, &rn->eigrp->topology, rn)rt_tree_RB_REMOVE(&rn->eigrp->topology, rn);
241 free(rn);
242}
243
244static struct eigrp_route *
245route_find(struct rde_nbr *nbr, struct rt_node *rn)
246{
247 struct eigrp_route *route;
248
249 TAILQ_FOREACH(route, &rn->routes, entry)for((route) = ((&rn->routes)->tqh_first); (route) !=
((void *)0); (route) = ((route)->entry.tqe_next))
250 if (route->nbr == nbr)
251 return (route);
252
253 return (NULL((void *)0));
254}
255
256static struct eigrp_route *
257route_new(struct rt_node *rn, struct rde_nbr *nbr, struct rinfo *ri)
258{
259 struct eigrp *eigrp = rn->eigrp;
260 struct eigrp_route *route, *tmp;
261
262 if ((route = calloc(1, sizeof(*route))) == NULL((void *)0))
263 fatal("route_new");
264
265 route->nbr = nbr;
266 route->type = ri->type;
267 if (eigrp_addrisset(eigrp->af, &ri->nexthop))
268 route->nexthop = ri->nexthop;
269 else
270 route->nexthop = nbr->addr;
271 route_update_metrics(eigrp, route, ri);
272
273 /* order by nexthop */
274 TAILQ_FOREACH(tmp, &rn->routes, entry)for((tmp) = ((&rn->routes)->tqh_first); (tmp) != ((
void *)0); (tmp) = ((tmp)->entry.tqe_next))
275 if (eigrp_addrcmp(eigrp->af, &tmp->nexthop,
276 &route->nexthop) > 0)
277 break;
278 if (tmp)
279 TAILQ_INSERT_BEFORE(tmp, route, entry)do { (route)->entry.tqe_prev = (tmp)->entry.tqe_prev; (
route)->entry.tqe_next = (tmp); *(tmp)->entry.tqe_prev =
(route); (tmp)->entry.tqe_prev = &(route)->entry.tqe_next
; } while (0);
280 else
281 TAILQ_INSERT_TAIL(&rn->routes, route, entry)do { (route)->entry.tqe_next = ((void *)0); (route)->entry
.tqe_prev = (&rn->routes)->tqh_last; *(&rn->
routes)->tqh_last = (route); (&rn->routes)->tqh_last
= &(route)->entry.tqe_next; } while (0);
282
283 log_debug("%s: prefix %s via %s distance (%u/%u)", __func__,
284 log_prefix(rn), log_route_origin(eigrp->af, route->nbr),
285 route->distance, route->rdistance);
286
287 return (route);
288}
289
290static void
291route_del(struct rt_node *rn, struct eigrp_route *route)
292{
293 struct eigrp *eigrp = rn->eigrp;
294
295 log_debug("%s: prefix %s via %s", __func__, log_prefix(rn),
296 log_route_origin(eigrp->af, route->nbr));
297
298 if (route->flags & F_EIGRP_ROUTE_INSTALLED0x01)
299 rde_send_delete_kroute(rn, route);
300
301 TAILQ_REMOVE(&rn->routes, route, entry)do { if (((route)->entry.tqe_next) != ((void *)0)) (route)
->entry.tqe_next->entry.tqe_prev = (route)->entry.tqe_prev
; else (&rn->routes)->tqh_last = (route)->entry.
tqe_prev; *(route)->entry.tqe_prev = (route)->entry.tqe_next
; ; ; } while (0);
302 free(route);
303}
304
305static uint32_t
306safe_sum_uint32(uint32_t a, uint32_t b)
307{
308 uint64_t total;
309
310 total = (uint64_t) a + (uint64_t) b;
311
312 if (total >> 32)
313 return ((uint32_t )(~0));
314
315 return ((uint32_t) total);
316}
317
318static uint32_t
319safe_mul_uint32(uint32_t a, uint32_t b)
320{
321 uint64_t total;
322
323 total = (uint64_t) a * (uint64_t) b;
324
325 if (total >> 32)
326 return ((uint32_t )(~0));
327
328 return ((uint32_t) total);
329}
330
331uint32_t
332eigrp_composite_delay(uint32_t delay)
333{
334 /* cheap overflow protection */
335 delay = min(delay, (1 << 24) - 1)((delay) <= ((1 << 24) - 1) ? (delay) : ((1 <<
24) - 1));
336 return (delay * EIGRP_SCALING_FACTOR256);
337}
338
339uint32_t
340eigrp_real_delay(uint32_t delay)
341{
342 return (delay / EIGRP_SCALING_FACTOR256);
343}
344
345uint32_t
346eigrp_composite_bandwidth(uint32_t bandwidth)
347{
348 /* truncate before applying the scaling factor */
349 bandwidth = 10000000 / bandwidth;
350 return (EIGRP_SCALING_FACTOR256 * bandwidth);
351}
352
353uint32_t
354eigrp_real_bandwidth(uint32_t bandwidth)
355{
356 /*
357 * apply the scaling factor before the division and only then truncate.
358 * this is to keep consistent with what cisco does.
359 */
360 return ((EIGRP_SCALING_FACTOR256 * (uint32_t)10000000) / bandwidth);
361}
362
363static uint32_t
364route_composite_metric(uint8_t *kvalues, uint32_t delay, uint32_t bandwidth,
365 uint8_t load, uint8_t reliability)
366{
367 uint64_t distance;
368 uint32_t operand1, operand2, operand3;
369 double operand4;
370
371 /*
372 * Need to apply the scaling factor before any division to avoid
373 * losing information from truncation.
374 */
375 operand1 = safe_mul_uint32(kvalues[0] * EIGRP_SCALING_FACTOR256,
376 10000000 / bandwidth);
377 operand2 = safe_mul_uint32(kvalues[1] * EIGRP_SCALING_FACTOR256,
378 10000000 / bandwidth) / (256 - load);
379 operand3 = safe_mul_uint32(kvalues[2] * EIGRP_SCALING_FACTOR256, delay);
380
381 distance = (uint64_t) operand1 + (uint64_t) operand2 +
382 (uint64_t) operand3;
383
384 /* if K5 is set to zero, the last term of the formula is not used */
385 if (kvalues[4] != 0) {
386 operand4 = (double) kvalues[4] / (reliability + kvalues[3]);
387 /* no risk of overflow (64 bits), operand4 can be at most 255 */
388 distance *= operand4;
389 }
390
391 /* overflow protection */
392 if (distance >> 32)
393 distance = ((uint32_t )(~0));
394
395 return ((uint32_t) distance);
396}
397
398static void
399route_update_metrics(struct eigrp *eigrp, struct eigrp_route *route,
400 struct rinfo *ri)
401{
402 struct eigrp_iface *ei = route->nbr->ei;
403 uint32_t delay, bandwidth;
404 int mtu;
405
406 route->metric = ri->metric;
407 route->emetric = ri->emetric;
408 route->flags |= F_EIGRP_ROUTE_M_CHANGED0x02;
409
410 delay = eigrp_real_delay(route->metric.delay);
411 bandwidth = eigrp_real_bandwidth(route->metric.bandwidth);
412
413 if (route->nbr->flags & F_RDE_NBR_SELF0x01)
414 route->rdistance = 0;
415 else {
416 route->rdistance = route_composite_metric(eigrp->kvalues,
417 delay, bandwidth, route->metric.load,
418 route->metric.reliability);
419
420 /* update the delay */
421 delay = safe_sum_uint32(delay, ei->delay);
422 route->metric.delay = eigrp_composite_delay(delay);
423
424 /* update the bandwidth */
425 bandwidth = min(bandwidth, ei->bandwidth)((bandwidth) <= (ei->bandwidth) ? (bandwidth) : (ei->
bandwidth));
426 route->metric.bandwidth = eigrp_composite_bandwidth(bandwidth);
427
428 /* update the mtu */
429 mtu = min(metric_decode_mtu(route->metric.mtu), ei->iface->mtu)((metric_decode_mtu(route->metric.mtu)) <= (ei->iface
->mtu) ? (metric_decode_mtu(route->metric.mtu)) : (ei->
iface->mtu));
430 metric_encode_mtu(route->metric.mtu, mtu);
431
432 /* update the hop count */
433 if (route->metric.hop_count < UINT8_MAX0xff)
434 route->metric.hop_count++;
435 }
436
437 route->distance = route_composite_metric(eigrp->kvalues, delay,
438 bandwidth, DEFAULT_LOAD1, DEFAULT_RELIABILITY255);
439}
440
441static void
442reply_outstanding_add(struct rt_node *rn, struct rde_nbr *nbr)
443{
444 struct reply_node *reply;
445
446 if ((reply = calloc(1, sizeof(*reply))) == NULL((void *)0))
447 fatal("reply_outstanding_add");
448
449 evtimer_set(&reply->ev_active_timeout, reply_active_timer, reply)event_set(&reply->ev_active_timeout, -1, 0, reply_active_timer
, reply);
450 evtimer_set(&reply->ev_sia_timeout, reply_sia_timer, reply)event_set(&reply->ev_sia_timeout, -1, 0, reply_sia_timer
, reply);
451 reply->siaquery_sent = 0;
452 reply->siareply_recv = 0;
453 reply->rn = rn;
454 reply->nbr = nbr;
455 TAILQ_INSERT_TAIL(&rn->rijk, reply, rn_entry)do { (reply)->rn_entry.tqe_next = ((void *)0); (reply)->
rn_entry.tqe_prev = (&rn->rijk)->tqh_last; *(&rn
->rijk)->tqh_last = (reply); (&rn->rijk)->tqh_last
= &(reply)->rn_entry.tqe_next; } while (0);
456 TAILQ_INSERT_TAIL(&nbr->rijk, reply, nbr_entry)do { (reply)->nbr_entry.tqe_next = ((void *)0); (reply)->
nbr_entry.tqe_prev = (&nbr->rijk)->tqh_last; *(&
nbr->rijk)->tqh_last = (reply); (&nbr->rijk)->
tqh_last = &(reply)->nbr_entry.tqe_next; } while (0);
457
458 if (rn->eigrp->active_timeout > 0) {
459 reply_active_start_timer(reply);
460 reply_sia_start_timer(reply);
461 }
462}
463
464static struct reply_node *
465reply_outstanding_find(struct rt_node *rn, struct rde_nbr *nbr)
466{
467 struct reply_node *reply;
468
469 TAILQ_FOREACH(reply, &rn->rijk, rn_entry)for((reply) = ((&rn->rijk)->tqh_first); (reply) != (
(void *)0); (reply) = ((reply)->rn_entry.tqe_next))
470 if (reply->nbr == nbr)
471 return (reply);
472
473 return (NULL((void *)0));
474}
475
476static void
477reply_outstanding_remove(struct reply_node *reply)
478{
479 reply_active_stop_timer(reply);
480 reply_sia_stop_timer(reply);
481 TAILQ_REMOVE(&reply->rn->rijk, reply, rn_entry)do { if (((reply)->rn_entry.tqe_next) != ((void *)0)) (reply
)->rn_entry.tqe_next->rn_entry.tqe_prev = (reply)->rn_entry
.tqe_prev; else (&reply->rn->rijk)->tqh_last = (
reply)->rn_entry.tqe_prev; *(reply)->rn_entry.tqe_prev =
(reply)->rn_entry.tqe_next; ; ; } while (0);
482 TAILQ_REMOVE(&reply->nbr->rijk, reply, nbr_entry)do { if (((reply)->nbr_entry.tqe_next) != ((void *)0)) (reply
)->nbr_entry.tqe_next->nbr_entry.tqe_prev = (reply)->
nbr_entry.tqe_prev; else (&reply->nbr->rijk)->tqh_last
= (reply)->nbr_entry.tqe_prev; *(reply)->nbr_entry.tqe_prev
= (reply)->nbr_entry.tqe_next; ; ; } while (0);
483 free(reply);
484}
485
486static void
487reply_active_timer(int fd, short event, void *arg)
488{
489 struct reply_node *reply = arg;
490 struct rde_nbr *nbr = reply->nbr;
491
492 log_debug("%s: neighbor %s is stuck in active", __func__,
493 log_addr(nbr->eigrp->af, &nbr->addr));
494
495 rde_nbr_del(reply->nbr, 1);
496}
497
498static void
499reply_active_start_timer(struct reply_node *reply)
500{
501 struct eigrp *eigrp = reply->nbr->eigrp;
502 struct timeval tv;
503
504 timerclear(&tv)(&tv)->tv_sec = (&tv)->tv_usec = 0;
505 tv.tv_sec = eigrp->active_timeout * 60;
506 if (evtimer_add(&reply->ev_active_timeout, &tv)event_add(&reply->ev_active_timeout, &tv) == -1)
507 fatal("reply_active_start_timer");
508}
509
510static void
511reply_active_stop_timer(struct reply_node *reply)
512{
513 if (evtimer_pending(&reply->ev_active_timeout, NULL)event_pending(&reply->ev_active_timeout, 0x01, ((void *
)0)) &&
514 evtimer_del(&reply->ev_active_timeout)event_del(&reply->ev_active_timeout) == -1)
515 fatal("reply_active_stop_timer");
516}
517
518static void
519reply_sia_timer(int fd, short event, void *arg)
520{
521 struct reply_node *reply = arg;
522 struct rde_nbr *nbr = reply->nbr;
523 struct rt_node *rn = reply->rn;
524 struct rinfo ri;
525
526 log_debug("%s: nbr %s prefix %s", __func__, log_addr(nbr->eigrp->af,
527 &nbr->addr), log_prefix(rn));
528
529 if (reply->siaquery_sent > 0 && reply->siareply_recv == 0) {
530 log_debug("%s: neighbor %s is stuck in active", __func__,
531 log_addr(nbr->eigrp->af, &nbr->addr));
532 rde_nbr_del(nbr, 1);
533 return;
534 }
535
536 /*
537 * draft-savage-eigrp-04 - Section 4.4.1.1:
538 * "Up to three SIA-QUERY packets for a specific destination may
539 * be sent, each at a value of one-half the ACTIVE time, so long
540 * as each are successfully acknowledged and met with an SIA-REPLY".
541 */
542 if (reply->siaquery_sent >= 3)
543 return;
544
545 reply->siaquery_sent++;
546 reply->siareply_recv = 0;
547
548 /* restart sia and active timeouts */
549 reply_sia_start_timer(reply);
550 reply_active_start_timer(reply);
551
552 /* send an sia-query */
553 rinfo_fill_successor(rn, &ri);
554 ri.metric.flags |= F_METRIC_ACTIVE0x04;
555 rde_send_siaquery(nbr, &ri);
556}
557
558static void
559reply_sia_start_timer(struct reply_node *reply)
560{
561 struct eigrp *eigrp = reply->nbr->eigrp;
562 struct timeval tv;
563
564 /*
565 * draft-savage-eigrp-04 - Section 4.4.1.1:
566 * "The SIA-QUERY packet SHOULD be sent on a per-destination basis
567 * at one-half of the ACTIVE timeout period."
568 */
569 timerclear(&tv)(&tv)->tv_sec = (&tv)->tv_usec = 0;
570 tv.tv_sec = (eigrp->active_timeout * 60) / 2;
571 if (evtimer_add(&reply->ev_sia_timeout, &tv)event_add(&reply->ev_sia_timeout, &tv) == -1)
572 fatal("reply_sia_start_timer");
573}
574
575static void
576reply_sia_stop_timer(struct reply_node *reply)
577{
578 if (evtimer_pending(&reply->ev_sia_timeout, NULL)event_pending(&reply->ev_sia_timeout, 0x01, ((void *)0
)) &&
579 evtimer_del(&reply->ev_sia_timeout)event_del(&reply->ev_sia_timeout) == -1)
580 fatal("reply_sia_stop_timer");
581}
582
583void
584rinfo_fill_successor(struct rt_node *rn, struct rinfo *ri)
585{
586 if (rn->successor.nbr == NULL((void *)0)) {
587 rinfo_fill_infinite(rn, EIGRP_ROUTE_INTERNAL, ri);
588 return;
589 }
590
591 memset(ri, 0, sizeof(*ri));
592 ri->af = rn->eigrp->af;
593 ri->type = rn->successor.type;
594 ri->prefix = rn->prefix;
595 ri->prefixlen = rn->prefixlen;
596 ri->metric = rn->successor.metric;
597 if (ri->type == EIGRP_ROUTE_EXTERNAL)
598 ri->emetric = rn->successor.emetric;
599}
600
601static void
602rinfo_fill_infinite(struct rt_node *rn, enum route_type type, struct rinfo *ri)
603{
604 memset(ri, 0, sizeof(*ri));
605 ri->af = rn->eigrp->af;
606 ri->type = type;
607 ri->prefix = rn->prefix;
608 ri->prefixlen = rn->prefixlen;
609 ri->metric.delay = EIGRP_INFINITE_METRIC((uint32_t )(~0));
610}
611
612static void
613rt_update_fib(struct rt_node *rn)
614{
615 struct eigrp *eigrp = rn->eigrp;
616 uint8_t maximum_paths = eigrp->maximum_paths;
617 uint8_t variance = eigrp->variance;
618 int installed = 0;
619 struct eigrp_route *route;
620
621 if (rn->state == DUAL_STA_PASSIVE0x0001) {
622 /* no multipath for attached networks. */
623 if (rn->successor.nbr &&
624 (rn->successor.nbr->flags & F_RDE_NBR_LOCAL0x02))
625 return;
626
627 TAILQ_FOREACH(route, &rn->routes, entry)for((route) = ((&rn->routes)->tqh_first); (route) !=
((void *)0); (route) = ((route)->entry.tqe_next)) {
628 /* skip redistributed routes */
629 if (route->nbr->flags & F_RDE_NBR_REDIST0x04)
630 continue;
631
632 /*
633 * Only feasible successors and the successor itself
634 * are eligible to be installed.
635 */
636 if (route->rdistance >= rn->successor.fdistance)
637 goto uninstall;
638
639 if (route->distance >
640 (rn->successor.fdistance * variance))
641 goto uninstall;
642
643 if (installed >= maximum_paths)
644 goto uninstall;
645
646 installed++;
647
648 if ((route->flags & F_EIGRP_ROUTE_INSTALLED0x01) &&
649 !(route->flags & F_EIGRP_ROUTE_M_CHANGED0x02))
650 continue;
651
652 rde_send_change_kroute(rn, route);
653 continue;
654
655uninstall:
656 if (route->flags & F_EIGRP_ROUTE_INSTALLED0x01)
657 rde_send_delete_kroute(rn, route);
658 }
659 } else {
660 TAILQ_FOREACH(route, &rn->routes, entry)for((route) = ((&rn->routes)->tqh_first); (route) !=
((void *)0); (route) = ((route)->entry.tqe_next))
661 if (route->flags & F_EIGRP_ROUTE_INSTALLED0x01)
662 rde_send_delete_kroute(rn, route);
663 }
664}
665
666static void
667rt_set_successor(struct rt_node *rn, struct eigrp_route *successor)
668{
669 struct eigrp *eigrp = rn->eigrp;
670 struct eigrp_iface *ei;
671 struct summary_addr *summary;
672
673 if (successor == NULL((void *)0)) {
674 rn->successor.nbr = NULL((void *)0);
675 rn->successor.type = 0;
676 rn->successor.fdistance = EIGRP_INFINITE_METRIC((uint32_t )(~0));
677 rn->successor.rdistance = EIGRP_INFINITE_METRIC((uint32_t )(~0));
678 memset(&rn->successor.metric, 0,
679 sizeof(rn->successor.metric));
680 rn->successor.metric.delay = EIGRP_INFINITE_METRIC((uint32_t )(~0));
681 memset(&rn->successor.emetric, 0,
682 sizeof(rn->successor.emetric));
683 } else {
684 rn->successor.nbr = successor->nbr;
685 rn->successor.type = successor->type;
686 rn->successor.fdistance = successor->distance;
687 rn->successor.rdistance = successor->rdistance;
688 rn->successor.metric = successor->metric;
689 rn->successor.emetric = successor->emetric;
690 }
691
692 TAILQ_FOREACH(ei, &eigrp->ei_list, e_entry)for((ei) = ((&eigrp->ei_list)->tqh_first); (ei) != (
(void *)0); (ei) = ((ei)->e_entry.tqe_next)) {
693 summary = rde_summary_check(ei, &rn->prefix, rn->prefixlen);
694 if (summary)
695 rt_summary_set(eigrp, summary, &rn->successor.metric);
696 }
697}
698
699static struct eigrp_route *
700rt_get_successor_fc(struct rt_node *rn)
701{
702 struct eigrp_route *route, *successor = NULL((void *)0);
703 uint32_t distance = EIGRP_INFINITE_METRIC((uint32_t )(~0));
704 int external_only = 1;
705
706 TAILQ_FOREACH(route, &rn->routes, entry)for((route) = ((&rn->routes)->tqh_first); (route) !=
((void *)0); (route) = ((route)->entry.tqe_next))
707 if (route->type == EIGRP_ROUTE_INTERNAL) {
708 /*
709 * connected routes should always be preferred over
710 * received routes independent of the metric.
711 */
712 if (route->nbr->flags & F_RDE_NBR_LOCAL0x02)
713 return (route);
714
715 external_only = 0;
716 }
717
718 TAILQ_FOREACH(route, &rn->routes, entry)for((route) = ((&rn->routes)->tqh_first); (route) !=
((void *)0); (route) = ((route)->entry.tqe_next)) {
719 /*
720 * draft-savage-eigrp-04 - Section 5.4.7:
721 * "Internal routes MUST be preferred over external routes
722 * independent of the metric."
723 */
724 if (route->type == EIGRP_ROUTE_EXTERNAL && !external_only)
725 continue;
726
727 /* pick the best route that meets the feasibility condition */
728 if (route->rdistance < rn->successor.fdistance &&
729 route->distance < distance) {
730 distance = route->distance;
731 successor = route;
732 }
733 }
734
735 return (successor);
736}
737
738struct summary_addr *
739rde_summary_check(struct eigrp_iface *ei, union eigrpd_addr *prefix,
740 uint8_t prefixlen)
741{
742 struct summary_addr *summary;
743
744 TAILQ_FOREACH(summary, &ei->summary_list, entry)for((summary) = ((&ei->summary_list)->tqh_first); (
summary) != ((void *)0); (summary) = ((summary)->entry.tqe_next
)) {
745 /* do not filter the summary itself */
746 if (summary->prefixlen == prefixlen &&
747 !eigrp_addrcmp(ei->eigrp->af, prefix, &summary->prefix))
748 return (NULL((void *)0));
749
750 if (summary->prefixlen <= prefixlen &&
751 !eigrp_prefixcmp(ei->eigrp->af, prefix, &summary->prefix,
752 summary->prefixlen))
753 return (summary);
754 }
755
756 return (NULL((void *)0));
757}
758
759static void
760rde_send_update(struct eigrp_iface *ei, struct rinfo *ri)
761{
762 if (ri->metric.hop_count >= ei->eigrp->maximum_hops ||
763 rde_summary_check(ei, &ri->prefix, ri->prefixlen))
764 ri->metric.delay = EIGRP_INFINITE_METRIC((uint32_t )(~0));
765
766 rde_imsg_compose_eigrpe(IMSG_SEND_MUPDATE, ei->ifaceid, 0,
767 ri, sizeof(*ri));
768 rde_imsg_compose_eigrpe(IMSG_SEND_MUPDATE_END, ei->ifaceid, 0,
769 NULL((void *)0), 0);
770}
771
772static void
773rde_send_update_all(struct rt_node *rn, struct rinfo *ri)
774{
775 struct eigrp *eigrp = rn->eigrp;
776 struct eigrp_iface *ei;
777
778 TAILQ_FOREACH(ei, &eigrp->ei_list, e_entry)for((ei) = ((&eigrp->ei_list)->tqh_first); (ei) != (
(void *)0); (ei) = ((ei)->e_entry.tqe_next)) {
779 /* respect split-horizon configuration */
780 if (rn->successor.nbr && rn->successor.nbr->ei == ei &&
781 ei->splithorizon)
782 continue;
783 rde_send_update(ei, ri);
784 }
785}
786
787static void
788rde_send_query(struct eigrp_iface *ei, struct rinfo *ri, int push)
789{
790 rde_imsg_compose_eigrpe(IMSG_SEND_MQUERY, ei->ifaceid, 0,
791 ri, sizeof(*ri));
792 if (push)
793 rde_imsg_compose_eigrpe(IMSG_SEND_MQUERY_END, ei->ifaceid,
794 0, NULL((void *)0), 0);
795}
796
797static void
798rde_send_siaquery(struct rde_nbr *nbr, struct rinfo *ri)
799{
800 rde_imsg_compose_eigrpe(IMSG_SEND_QUERY, nbr->peerid, 0,
801 ri, sizeof(*ri));
802 rde_imsg_compose_eigrpe(IMSG_SEND_SIAQUERY_END, nbr->peerid, 0,
803 NULL((void *)0), 0);
804}
805
806static void
807rde_send_query_all(struct eigrp *eigrp, struct rt_node *rn, int push)
808{
809 struct eigrp_iface *ei;
810 struct rde_nbr *nbr;
811 struct rinfo ri;
812
813 rinfo_fill_successor(rn, &ri);
814 ri.metric.flags |= F_METRIC_ACTIVE0x04;
815
816 TAILQ_FOREACH(ei, &eigrp->ei_list, e_entry)for((ei) = ((&eigrp->ei_list)->tqh_first); (ei) != (
(void *)0); (ei) = ((ei)->e_entry.tqe_next)) {
817 /* respect split-horizon configuration */
818 if (rn->successor.nbr && rn->successor.nbr->ei == ei &&
819 ei->splithorizon)
820 continue;
821
822 rde_send_query(ei, &ri, push);
823 }
824
825 RB_FOREACH(nbr, rde_nbr_head, &rde_nbrs)for ((nbr) = rde_nbr_head_RB_MINMAX(&rde_nbrs, -1); (nbr)
!= ((void *)0); (nbr) = rde_nbr_head_RB_NEXT(nbr))
826 if (nbr->ei->eigrp == eigrp && !(nbr->flags & F_RDE_NBR_SELF0x01)) {
827 /* respect split-horizon configuration */
828 if (rn->successor.nbr &&
829 rn->successor.nbr->ei == nbr->ei &&
830 nbr->ei->splithorizon)
831 continue;
832
833 reply_outstanding_add(rn, nbr);
834 }
835}
836
837void
838rde_flush_queries(void)
839{
840 struct eigrp *eigrp;
841 struct eigrp_iface *ei;
842
843 TAILQ_FOREACH(eigrp, &rdeconf->instances, entry)for((eigrp) = ((&rdeconf->instances)->tqh_first); (
eigrp) != ((void *)0); (eigrp) = ((eigrp)->entry.tqe_next)
)
844 TAILQ_FOREACH(ei, &eigrp->ei_list, e_entry)for((ei) = ((&eigrp->ei_list)->tqh_first); (ei) != (
(void *)0); (ei) = ((ei)->e_entry.tqe_next))
845 rde_imsg_compose_eigrpe(IMSG_SEND_MQUERY_END,
846 ei->ifaceid, 0, NULL((void *)0), 0);
847}
848
849static void
850rde_send_reply(struct rde_nbr *nbr, struct rinfo *ri, int siareply)
851{
852 int type;
853
854 if (ri->metric.hop_count >= nbr->eigrp->maximum_hops ||
855 rde_summary_check(nbr->ei, &ri->prefix, ri->prefixlen))
856 ri->metric.delay = EIGRP_INFINITE_METRIC((uint32_t )(~0));
857
858 if (!siareply)
859 type = IMSG_SEND_REPLY_END;
860 else
861 type = IMSG_SEND_SIAREPLY_END;
862
863 rde_imsg_compose_eigrpe(IMSG_SEND_REPLY, nbr->peerid, 0,
864 ri, sizeof(*ri));
865 rde_imsg_compose_eigrpe(type, nbr->peerid, 0, NULL((void *)0), 0);
866}
867
868void
869rde_check_update(struct rde_nbr *nbr, struct rinfo *ri)
870{
871 struct eigrp *eigrp = nbr->eigrp;
872 struct rt_node *rn;
873 struct eigrp_route *route, *successor;
874 uint32_t old_fdistance;
875 struct rinfo sri;
876
877 rn = rt_find(eigrp, ri);
878 if (rn == NULL((void *)0)) {
879 if (ri->metric.delay == EIGRP_INFINITE_METRIC((uint32_t )(~0)))
880 return;
881
882 rn = rt_new(eigrp, ri);
883 route = route_new(rn, nbr, ri);
884
885 old_fdistance = EIGRP_INFINITE_METRIC((uint32_t )(~0));
886 } else {
887 old_fdistance = rn->successor.fdistance;
888
889 if (ri->metric.delay == EIGRP_INFINITE_METRIC((uint32_t )(~0))) {
890 route = route_find(nbr, rn);
891 if (route)
892 route_del(rn, route);
893 } else {
894 route = route_find(nbr, rn);
895 if (route == NULL((void *)0))
896 route = route_new(rn, nbr, ri);
Value stored to 'route' is never read
897 else
898 route_update_metrics(eigrp, route, ri);
899 }
900 }
901
902 switch (rn->state) {
903 case DUAL_STA_PASSIVE0x0001:
904 successor = rt_get_successor_fc(rn);
905
906 /*
907 * go active if the successor was affected and no feasible
908 * successor exist.
909 */
910 if (successor == NULL((void *)0)) {
911 rde_send_query_all(eigrp, rn, 1);
912
913 dual_fsm(rn, DUAL_EVT_4);
914 } else {
915 rt_set_successor(rn, successor);
916 rt_update_fib(rn);
917
918 /* send update with new metric if necessary */
919 rinfo_fill_successor(rn, &sri);
920 if (rn->successor.fdistance != old_fdistance)
921 rde_send_update_all(rn, &sri);
922 }
923 break;
924 case DUAL_STA_ACTIVE10x0004:
925 /* XXX event 9 if cost increase? */
926 break;
927 case DUAL_STA_ACTIVE30x0010:
928 /* XXX event 10 if cost increase? */
929 break;
930 }
931
932 if ((rn->state & DUAL_STA_ACTIVE_ALL(0x0002 | 0x0004 | 0x0008 | 0x0010)) && TAILQ_EMPTY(&rn->rijk)(((&rn->rijk)->tqh_first) == ((void *)0)))
933 rde_last_reply(rn);
934}
935
936void
937rde_check_query(struct rde_nbr *nbr, struct rinfo *ri, int siaquery)
938{
939 struct eigrp *eigrp = nbr->eigrp;
940 struct rt_node *rn;
941 struct eigrp_route *route, *successor;
942 uint32_t old_fdistance;
943 struct rinfo sri;
944 int reply_sent = 0;
945
946 /*
947 * draft-savage-eigrp-02 - Section 4.3:
948 * "When a query is received for a route that doesn't exist in our
949 * topology table, a reply with infinite metric is sent and an entry
950 * in the topology table is added with the metric in the QUERY if
951 * the metric is not an infinite value".
952 */
953 rn = rt_find(eigrp, ri);
954 if (rn == NULL((void *)0)) {
955 sri = *ri;
956 sri.metric.delay = EIGRP_INFINITE_METRIC((uint32_t )(~0));
957 rde_send_reply(nbr, &sri, 0);
958
959 if (ri->metric.delay == EIGRP_INFINITE_METRIC((uint32_t )(~0)))
960 return;
961
962 rn = rt_new(eigrp, ri);
963 route = route_new(rn, nbr, ri);
964 rt_set_successor(rn, route);
965 return;
966 }
967
968 old_fdistance = rn->successor.fdistance;
969
970 if (ri->metric.delay == EIGRP_INFINITE_METRIC((uint32_t )(~0))) {
971 route = route_find(nbr, rn);
972 if (route)
973 route_del(rn, route);
974 } else {
975 route = route_find(nbr, rn);
976 if (route == NULL((void *)0))
977 route = route_new(rn, nbr, ri);
978 else
979 route_update_metrics(eigrp, route, ri);
980 }
981
982 switch (rn->state) {
983 case DUAL_STA_PASSIVE0x0001:
984 successor = rt_get_successor_fc(rn);
985
986 /*
987 * go active if the successor was affected and no feasible
988 * successor exist.
989 */
990 if (successor == NULL((void *)0)) {
991 rde_send_query_all(eigrp, rn, 1);
992 dual_fsm(rn, DUAL_EVT_3);
993 } else {
994 rt_set_successor(rn, successor);
995 rt_update_fib(rn);
996
997 /* send reply */
998 rinfo_fill_successor(rn, &sri);
999 rde_send_reply(nbr, &sri, 0);
1000 reply_sent = 1;
1001
1002 /* send update with new metric if necessary */
1003 if (rn->successor.fdistance != old_fdistance)
1004 rde_send_update_all(rn, &sri);
1005 }
1006 break;
1007 case DUAL_STA_ACTIVE00x0002:
1008 case DUAL_STA_ACTIVE10x0004:
1009 if (nbr == rn->successor.nbr)
1010 dual_fsm(rn, DUAL_EVT_5);
1011 else {
1012 dual_fsm(rn, DUAL_EVT_6);
1013 rinfo_fill_successor(rn, &sri);
1014 sri.metric.flags |= F_METRIC_ACTIVE0x04;
1015 rde_send_reply(nbr, &sri, 0);
1016 reply_sent = 1;
1017 }
1018 break;
1019 case DUAL_STA_ACTIVE20x0008:
1020 case DUAL_STA_ACTIVE30x0010:
1021 if (nbr == rn->successor.nbr) {
1022 /* XXX not defined in the spec, do nothing? */
1023 } else {
1024 dual_fsm(rn, DUAL_EVT_6);
1025 rinfo_fill_successor(rn, &sri);
1026 sri.metric.flags |= F_METRIC_ACTIVE0x04;
1027 rde_send_reply(nbr, &sri, 0);
1028 reply_sent = 1;
1029 }
1030 break;
1031 }
1032
1033 if ((rn->state & DUAL_STA_ACTIVE_ALL(0x0002 | 0x0004 | 0x0008 | 0x0010)) && TAILQ_EMPTY(&rn->rijk)(((&rn->rijk)->tqh_first) == ((void *)0)))
1034 rde_last_reply(rn);
1035
1036 if (siaquery && !reply_sent) {
1037 rinfo_fill_successor(rn, &sri);
1038 sri.metric.flags |= F_METRIC_ACTIVE0x04;
1039 rde_send_reply(nbr, &sri, 1);
1040 }
1041}
1042
1043static void
1044rde_last_reply(struct rt_node *rn)
1045{
1046 struct eigrp *eigrp = rn->eigrp;
1047 struct eigrp_route *successor;
1048 struct rde_nbr *old_successor;
1049 struct rinfo ri;
1050
1051 old_successor = rn->successor.nbr;
1052
1053 switch (rn->state) {
1054 case DUAL_STA_ACTIVE00x0002:
1055 successor = rt_get_successor_fc(rn);
1056 if (successor == NULL((void *)0)) {
1057 /* feasibility condition is not met */
1058 rde_send_query_all(eigrp, rn, 1);
1059 dual_fsm(rn, DUAL_EVT_11);
1060 break;
1061 }
1062
1063 /* update successor - feasibility condition is met */
1064 rt_set_successor(rn, successor);
1065
1066 /* advertise new successor to neighbors */
1067 rinfo_fill_successor(rn, &ri);
1068 rde_send_update_all(rn, &ri);
1069
1070 dual_fsm(rn, DUAL_EVT_14);
1071 break;
1072 case DUAL_STA_ACTIVE10x0004:
1073 /* update successor */
1074 rn->successor.fdistance = EIGRP_INFINITE_METRIC((uint32_t )(~0));
1075 successor = rt_get_successor_fc(rn);
1076 rt_set_successor(rn, successor);
1077
1078 /* advertise new successor to neighbors */
1079 rinfo_fill_successor(rn, &ri);
1080 rde_send_update_all(rn, &ri);
1081
1082 dual_fsm(rn, DUAL_EVT_15);
1083 break;
1084 case DUAL_STA_ACTIVE20x0008:
1085 successor = rt_get_successor_fc(rn);
1086 if (successor == NULL((void *)0)) {
1087 /* feasibility condition is not met */
1088 rde_send_query_all(eigrp, rn, 1);
1089 dual_fsm(rn, DUAL_EVT_12);
1090 break;
1091 }
1092
1093 /* update successor - feasibility condition is met */
1094 rt_set_successor(rn, successor);
1095
1096 /* send a reply to the old successor */
1097 rinfo_fill_successor(rn, &ri);
1098 ri.metric.flags |= F_METRIC_ACTIVE0x04;
1099 if (old_successor)
1100 rde_send_reply(old_successor, &ri, 0);
1101
1102 /* advertise new successor to neighbors */
1103 rde_send_update_all(rn, &ri);
1104
1105 dual_fsm(rn, DUAL_EVT_16);
1106 break;
1107 case DUAL_STA_ACTIVE30x0010:
1108 /* update successor */
1109 rn->successor.fdistance = EIGRP_INFINITE_METRIC((uint32_t )(~0));
1110 successor = rt_get_successor_fc(rn);
1111 rt_set_successor(rn, successor);
1112
1113 /* send a reply to the old successor */
1114 rinfo_fill_successor(rn, &ri);
1115 ri.metric.flags |= F_METRIC_ACTIVE0x04;
1116 if (old_successor)
1117 rde_send_reply(old_successor, &ri, 0);
1118
1119 /* advertise new successor to neighbors */
1120 rde_send_update_all(rn, &ri);
1121
1122 dual_fsm(rn, DUAL_EVT_13);
1123 break;
1124 }
1125
1126 if (rn->state == DUAL_STA_PASSIVE0x0001 && rn->successor.nbr == NULL((void *)0))
1127 rt_del(rn);
1128}
1129
1130void
1131rde_check_reply(struct rde_nbr *nbr, struct rinfo *ri, int siareply)
1132{
1133 struct eigrp *eigrp = nbr->eigrp;
1134 struct rt_node *rn;
1135 struct reply_node *reply;
1136 struct eigrp_route *route;
1137
1138 rn = rt_find(eigrp, ri);
1139 if (rn == NULL((void *)0))
1140 return;
1141
1142 /* XXX ignore reply when the state is passive? */
1143 if (rn->state == DUAL_STA_PASSIVE0x0001)
1144 return;
1145
1146 reply = reply_outstanding_find(rn, nbr);
1147 if (reply == NULL((void *)0))
1148 return;
1149
1150 if (siareply) {
1151 reply->siareply_recv = 1;
1152 reply_active_start_timer(reply);
1153 return;
1154 }
1155
1156 if (ri->metric.delay == EIGRP_INFINITE_METRIC((uint32_t )(~0))) {
1157 route = route_find(nbr, rn);
1158 if (route)
1159 route_del(rn, route);
1160 } else {
1161 route = route_find(nbr, rn);
1162 if (route == NULL((void *)0))
1163 route = route_new(rn, nbr, ri);
1164 else
1165 route_update_metrics(eigrp, route, ri);
1166 }
1167
1168 reply_outstanding_remove(reply);
1169 if (TAILQ_EMPTY(&rn->rijk)(((&rn->rijk)->tqh_first) == ((void *)0)))
1170 rde_last_reply(rn);
1171}
1172
1173void
1174rde_check_link_down_rn(struct rde_nbr *nbr, struct rt_node *rn,
1175 struct eigrp_route *route)
1176{
1177 struct eigrp *eigrp = nbr->eigrp;
1178 struct reply_node *reply;
1179 struct eigrp_route *successor;
1180 uint32_t old_fdistance;
1181 struct rinfo ri;
1182 enum route_type type;
1183
1184 old_fdistance = rn->successor.fdistance;
1185
1186 type = route->type;
1187 route_del(rn, route);
1188
1189 switch (rn->state) {
1190 case DUAL_STA_PASSIVE0x0001:
1191 successor = rt_get_successor_fc(rn);
1192
1193 /*
1194 * go active if the successor was affected and no feasible
1195 * successor exist.
1196 */
1197 if (successor == NULL((void *)0)) {
1198 rde_send_query_all(eigrp, rn, 0);
1199
1200 dual_fsm(rn, DUAL_EVT_4);
1201 } else {
1202 rt_set_successor(rn, successor);
1203 rt_update_fib(rn);
1204
1205 /* send update with new metric if necessary */
1206 rinfo_fill_successor(rn, &ri);
1207 if (rn->successor.fdistance != old_fdistance)
1208 rde_send_update_all(rn, &ri);
1209 }
1210 break;
1211 case DUAL_STA_ACTIVE10x0004:
1212 if (nbr == rn->successor.nbr)
1213 dual_fsm(rn, DUAL_EVT_9);
1214 break;
1215 case DUAL_STA_ACTIVE30x0010:
1216 if (nbr == rn->successor.nbr)
1217 dual_fsm(rn, DUAL_EVT_10);
1218 break;
1219 }
1220
1221 if (rn->state & DUAL_STA_ACTIVE_ALL(0x0002 | 0x0004 | 0x0008 | 0x0010)) {
1222 reply = reply_outstanding_find(rn, nbr);
1223 if (reply) {
1224 rinfo_fill_infinite(rn, type, &ri);
1225 rde_check_reply(nbr, &ri, 0);
1226 }
1227 }
1228}
1229
1230void
1231rde_check_link_down_nbr(struct rde_nbr *nbr)
1232{
1233 struct eigrp *eigrp = nbr->eigrp;
1234 struct rt_node *rn, *safe;
1235 struct eigrp_route *route;
1236
1237 RB_FOREACH_SAFE(rn, rt_tree, &eigrp->topology, safe)for ((rn) = rt_tree_RB_MINMAX(&eigrp->topology, -1); (
(rn) != ((void *)0)) && ((safe) = rt_tree_RB_NEXT(rn)
, 1); (rn) = (safe)) {
1238 route = route_find(nbr, rn);
1239 if (route) {
1240 rde_check_link_down_rn(nbr, rn, route);
1241 if (rn->successor.nbr == nbr)
1242 rn->successor.nbr = NULL((void *)0);
1243 }
1244 }
1245}
1246
1247void
1248rde_check_link_down(unsigned int ifindex)
1249{
1250 struct rde_nbr *nbr;
1251
1252 RB_FOREACH(nbr, rde_nbr_head, &rde_nbrs)for ((nbr) = rde_nbr_head_RB_MINMAX(&rde_nbrs, -1); (nbr)
!= ((void *)0); (nbr) = rde_nbr_head_RB_NEXT(nbr))
1253 if (nbr->ei->iface->ifindex == ifindex)
1254 rde_check_link_down_nbr(nbr);
1255
1256 rde_flush_queries();
1257}
1258
1259void
1260rde_check_link_cost_change(struct rde_nbr *nbr, struct eigrp_iface *ei)
1261{
1262}
1263
1264static __inline int
1265rde_nbr_compare(struct rde_nbr *a, struct rde_nbr *b)
1266{
1267 return (a->peerid - b->peerid);
1268}
1269
1270struct rde_nbr *
1271rde_nbr_find(uint32_t peerid)
1272{
1273 struct rde_nbr n;
1274
1275 n.peerid = peerid;
1276
1277 return (RB_FIND(rde_nbr_head, &rde_nbrs, &n)rde_nbr_head_RB_FIND(&rde_nbrs, &n));
1278}
1279
1280struct rde_nbr *
1281rde_nbr_new(uint32_t peerid, struct rde_nbr *new)
1282{
1283 struct rde_nbr *nbr;
1284
1285 if ((nbr = calloc(1, sizeof(*nbr))) == NULL((void *)0))
1286 fatal("rde_nbr_new");
1287
1288 nbr->peerid = peerid;
1289 nbr->ifaceid = new->ifaceid;
1290 nbr->addr = new->addr;
1291 nbr->ei = eigrp_if_lookup_id(nbr->ifaceid);
1292 if (nbr->ei)
1293 nbr->eigrp = nbr->ei->eigrp;
1294 TAILQ_INIT(&nbr->rijk)do { (&nbr->rijk)->tqh_first = ((void *)0); (&nbr
->rijk)->tqh_last = &(&nbr->rijk)->tqh_first
; } while (0);
1295 nbr->flags = new->flags;
1296
1297 if (nbr->peerid != NBR_IDSELF1 &&
1298 RB_INSERT(rde_nbr_head, &rde_nbrs, nbr)rde_nbr_head_RB_INSERT(&rde_nbrs, nbr) != NULL((void *)0))
1299 fatalx("rde_nbr_new: RB_INSERT failed");
1300
1301 return (nbr);
1302}
1303
1304void
1305rde_nbr_del(struct rde_nbr *nbr, int peerterm)
1306{
1307 struct reply_node *reply;
1308
1309 if (peerterm)
1310 rde_imsg_compose_eigrpe(IMSG_NEIGHBOR_DOWN, nbr->peerid,
1311 0, NULL((void *)0), 0);
1312
1313 while((reply = TAILQ_FIRST(&nbr->rijk)((&nbr->rijk)->tqh_first)) != NULL((void *)0))
1314 reply_outstanding_remove(reply);
1315
1316 if (nbr->peerid != NBR_IDSELF1)
1317 RB_REMOVE(rde_nbr_head, &rde_nbrs, nbr)rde_nbr_head_RB_REMOVE(&rde_nbrs, nbr);
1318 free(nbr);
1319}