Bug Summary

File:src/usr.sbin/eigrpd/rde_dual.c
Warning:line 631, column 8
Access to field 'flags' results in a dereference of a null pointer (loaded from field 'nbr')

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple amd64-unknown-openbsd7.0 -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name rde_dual.c -analyzer-store=region -analyzer-opt-analyze-nested-blocks -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 -fno-rounding-math -mconstructor-aliases -munwind-tables -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/lib/clang/13.0.0 -I /usr/src/usr.sbin/eigrpd -internal-isystem /usr/local/lib/clang/13.0.0/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 -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/vmm/scan-build/2022-01-12-194120-40624-1 -x c /usr/src/usr.sbin/eigrpd/rde_dual.c
1/* $OpenBSD: rde_dual.c,v 1.28 2016/09/02 16:44:33 renato 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); }
6
←
Assuming field 'rbe_right' is null
→
7
←
Taking false branch
→
8
←
Assuming field 'rbe_parent' is null
→
9
←
Returning without writing to 'elm->successor.nbr', which participates in a condition later
→
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))
13
←
Assuming 'route' is not equal to null
→
14
←
Loop condition is true. Entering loop body
→
250 if (route->nbr == nbr)
15
←
Assuming 'nbr' is equal to field 'nbr'
→
16
←
Taking true branch
→
251 return (route);
17
←
Returning without writing to 'rn->successor.nbr', which participates in a condition later
→
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
486/* ARGSUSED */
487static void
488reply_active_timer(int fd, short event, void *arg)
489{
490 struct reply_node *reply = arg;
491 struct rde_nbr *nbr = reply->nbr;
492
493 log_debug("%s: neighbor %s is stuck in active", __func__,
494 log_addr(nbr->eigrp->af, &nbr->addr));
495
496 rde_nbr_del(reply->nbr, 1);
497}
498
499static void
500reply_active_start_timer(struct reply_node *reply)
501{
502 struct eigrp *eigrp = reply->nbr->eigrp;
503 struct timeval tv;
504
505 timerclear(&tv)(&tv)->tv_sec = (&tv)->tv_usec = 0;
506 tv.tv_sec = eigrp->active_timeout * 60;
507 if (evtimer_add(&reply->ev_active_timeout, &tv)event_add(&reply->ev_active_timeout, &tv) == -1)
508 fatal("reply_active_start_timer");
509}
510
511static void
512reply_active_stop_timer(struct reply_node *reply)
513{
514 if (evtimer_pending(&reply->ev_active_timeout, NULL)event_pending(&reply->ev_active_timeout, 0x01, ((void *
)0)) &&
515 evtimer_del(&reply->ev_active_timeout)event_del(&reply->ev_active_timeout) == -1)
516 fatal("reply_active_stop_timer");
517}
518
519/* ARGSUSED */
520static void
521reply_sia_timer(int fd, short event, void *arg)
522{
523 struct reply_node *reply = arg;
524 struct rde_nbr *nbr = reply->nbr;
525 struct rt_node *rn = reply->rn;
526 struct rinfo ri;
527
528 log_debug("%s: nbr %s prefix %s", __func__, log_addr(nbr->eigrp->af,
529 &nbr->addr), log_prefix(rn));
530
531 if (reply->siaquery_sent > 0 && reply->siareply_recv == 0) {
532 log_debug("%s: neighbor %s is stuck in active", __func__,
533 log_addr(nbr->eigrp->af, &nbr->addr));
534 rde_nbr_del(nbr, 1);
535 return;
536 }
537
538 /*
539 * draft-savage-eigrp-04 - Section 4.4.1.1:
540 * "Up to three SIA-QUERY packets for a specific destination may
541 * be sent, each at a value of one-half the ACTIVE time, so long
542 * as each are successfully acknowledged and met with an SIA-REPLY".
543 */
544 if (reply->siaquery_sent >= 3)
545 return;
546
547 reply->siaquery_sent++;
548 reply->siareply_recv = 0;
549
550 /* restart sia and active timeouts */
551 reply_sia_start_timer(reply);
552 reply_active_start_timer(reply);
553
554 /* send an sia-query */
555 rinfo_fill_successor(rn, &ri);
556 ri.metric.flags |= F_METRIC_ACTIVE0x04;
557 rde_send_siaquery(nbr, &ri);
558}
559
560static void
561reply_sia_start_timer(struct reply_node *reply)
562{
563 struct eigrp *eigrp = reply->nbr->eigrp;
564 struct timeval tv;
565
566 /*
567 * draft-savage-eigrp-04 - Section 4.4.1.1:
568 * "The SIA-QUERY packet SHOULD be sent on a per-destination basis
569 * at one-half of the ACTIVE timeout period."
570 */
571 timerclear(&tv)(&tv)->tv_sec = (&tv)->tv_usec = 0;
572 tv.tv_sec = (eigrp->active_timeout * 60) / 2;
573 if (evtimer_add(&reply->ev_sia_timeout, &tv)event_add(&reply->ev_sia_timeout, &tv) == -1)
574 fatal("reply_sia_start_timer");
575}
576
577static void
578reply_sia_stop_timer(struct reply_node *reply)
579{
580 if (evtimer_pending(&reply->ev_sia_timeout, NULL)event_pending(&reply->ev_sia_timeout, 0x01, ((void *)0
)) &&
581 evtimer_del(&reply->ev_sia_timeout)event_del(&reply->ev_sia_timeout) == -1)
582 fatal("reply_sia_stop_timer");
583}
584
585void
586rinfo_fill_successor(struct rt_node *rn, struct rinfo *ri)
587{
588 if (rn->successor.nbr == NULL((void *)0)) {
589 rinfo_fill_infinite(rn, EIGRP_ROUTE_INTERNAL, ri);
590 return;
591 }
592
593 memset(ri, 0, sizeof(*ri));
594 ri->af = rn->eigrp->af;
595 ri->type = rn->successor.type;
596 ri->prefix = rn->prefix;
597 ri->prefixlen = rn->prefixlen;
598 ri->metric = rn->successor.metric;
599 if (ri->type == EIGRP_ROUTE_EXTERNAL)
600 ri->emetric = rn->successor.emetric;
601}
602
603static void
604rinfo_fill_infinite(struct rt_node *rn, enum route_type type, struct rinfo *ri)
605{
606 memset(ri, 0, sizeof(*ri));
607 ri->af = rn->eigrp->af;
608 ri->type = type;
609 ri->prefix = rn->prefix;
610 ri->prefixlen = rn->prefixlen;
611 ri->metric.delay = EIGRP_INFINITE_METRIC((uint32_t )(~0));
612}
613
614static void
615rt_update_fib(struct rt_node *rn)
616{
617 struct eigrp *eigrp = rn->eigrp;
618 uint8_t maximum_paths = eigrp->maximum_paths;
619 uint8_t variance = eigrp->variance;
620 int installed = 0;
621 struct eigrp_route *route;
622
623 if (rn->state
44.1
Field 'state' is equal to DUAL_STA_PASSIVE
 == DUAL_STA_PASSIVE0x0001) {
45
←
Taking true branch
→
624 /* no multipath for attached networks. */
625 if (rn->successor.nbr &&
46
←
Assuming field 'nbr' is null
→
626 (rn->successor.nbr->flags & F_RDE_NBR_LOCAL0x02))
627 return;
628
629 TAILQ_FOREACH(route, &rn->routes, entry)for((route) = ((&rn->routes)->tqh_first); (route) !=
((void *)0); (route) = ((route)->entry.tqe_next)) {
47
←
Loop condition is true. Entering loop body
→
630 /* skip redistributed routes */
631 if (route->nbr->flags & F_RDE_NBR_REDIST0x04)
48
←
Access to field 'flags' results in a dereference of a null pointer (loaded from field 'nbr')
632 continue;
633
634 /*
635 * Only feasible successors and the successor itself
636 * are elegible to be installed.
637 */
638 if (route->rdistance >= rn->successor.fdistance)
639 goto uninstall;
640
641 if (route->distance >
642 (rn->successor.fdistance * variance))
643 goto uninstall;
644
645 if (installed >= maximum_paths)
646 goto uninstall;
647
648 installed++;
649
650 if ((route->flags & F_EIGRP_ROUTE_INSTALLED0x01) &&
651 !(route->flags & F_EIGRP_ROUTE_M_CHANGED0x02))
652 continue;
653
654 rde_send_change_kroute(rn, route);
655 continue;
656
657uninstall:
658 if (route->flags & F_EIGRP_ROUTE_INSTALLED0x01)
659 rde_send_delete_kroute(rn, route);
660 }
661 } else {
662 TAILQ_FOREACH(route, &rn->routes, entry)for((route) = ((&rn->routes)->tqh_first); (route) !=
((void *)0); (route) = ((route)->entry.tqe_next))
663 if (route->flags & F_EIGRP_ROUTE_INSTALLED0x01)
664 rde_send_delete_kroute(rn, route);
665 }
666}
667
668static void
669rt_set_successor(struct rt_node *rn, struct eigrp_route *successor)
670{
671 struct eigrp *eigrp = rn->eigrp;
672 struct eigrp_iface *ei;
673 struct summary_addr *summary;
674
675 if (successor
38.1
'successor' is not equal to NULL
 == NULL((void *)0)) {
39
←
Taking false branch
→
676 rn->successor.nbr = NULL((void *)0);
677 rn->successor.type = 0;
678 rn->successor.fdistance = EIGRP_INFINITE_METRIC((uint32_t )(~0));
679 rn->successor.rdistance = EIGRP_INFINITE_METRIC((uint32_t )(~0));
680 memset(&rn->successor.metric, 0,
681 sizeof(rn->successor.metric));
682 rn->successor.metric.delay = EIGRP_INFINITE_METRIC((uint32_t )(~0));
683 memset(&rn->successor.emetric, 0,
684 sizeof(rn->successor.emetric));
685 } else {
686 rn->successor.nbr = successor->nbr;
687 rn->successor.type = successor->type;
688 rn->successor.fdistance = successor->distance;
689 rn->successor.rdistance = successor->rdistance;
690 rn->successor.metric = successor->metric;
691 rn->successor.emetric = successor->emetric;
692 }
693
694 TAILQ_FOREACH(ei, &eigrp->ei_list, e_entry)for((ei) = ((&eigrp->ei_list)->tqh_first); (ei) != (
(void *)0); (ei) = ((ei)->e_entry.tqe_next)) {
40
←
Assuming 'ei' is equal to null
→
41
←
Loop condition is false. Execution continues on line 694
→
695 summary = rde_summary_check(ei, &rn->prefix, rn->prefixlen);
696 if (summary)
697 rt_summary_set(eigrp, summary, &rn->successor.metric);
698 }
699}
42
←
Returning without writing to 'successor->nbr'
→
700
701static struct eigrp_route *
702rt_get_successor_fc(struct rt_node *rn)
703{
704 struct eigrp_route *route, *successor = NULL((void *)0);
705 uint32_t distance = EIGRP_INFINITE_METRIC((uint32_t )(~0));
706 int external_only = 1;
707
708 TAILQ_FOREACH(route, &rn->routes, entry)for((route) = ((&rn->routes)->tqh_first); (route) !=
((void *)0); (route) = ((route)->entry.tqe_next))
23
←
Assuming 'route' is not equal to null
→
24
←
Loop condition is true. Entering loop body
→
27
←
Assuming 'route' is equal to null
→
28
←
Loop condition is false. Execution continues on line 720
→
709 if (route->type == EIGRP_ROUTE_INTERNAL) {
25
←
Assuming field 'type' is not equal to EIGRP_ROUTE_INTERNAL
→
26
←
Taking false branch
→
710 /*
711 * connected routes should always be prefered over
712 * received routes independent of the metric.
713 */
714 if (route->nbr->flags & F_RDE_NBR_LOCAL0x02)
715 return (route);
716
717 external_only = 0;
718 }
719
720 TAILQ_FOREACH(route, &rn->routes, entry)for((route) = ((&rn->routes)->tqh_first); (route) !=
((void *)0); (route) = ((route)->entry.tqe_next)) {
29
←
Loop condition is true. Entering loop body
→
34
←
Loop condition is false. Execution continues on line 737
→
721 /*
722 * draft-savage-eigrp-04 - Section 5.4.7:
723 * "Internal routes MUST be prefered over external routes
724 * independent of the metric."
725 */
726 if (route->type == EIGRP_ROUTE_EXTERNAL && !external_only)
30
←
Assuming field 'type' is not equal to EIGRP_ROUTE_EXTERNAL
→
727 continue;
728
729 /* pick the best route that meets the feasibility condition */
730 if (route->rdistance < rn->successor.fdistance &&
31
←
Assuming field 'rdistance' is < field 'fdistance'
→
33
←
Taking true branch
→
731 route->distance < distance) {
32
←
Assuming 'distance' is > field 'distance'
→
732 distance = route->distance;
733 successor = route;
734 }
735 }
736
737 return (successor);
35
←
Returning without writing to 'rn->successor.nbr', which participates in a condition later
→
738}
739
740struct summary_addr *
741rde_summary_check(struct eigrp_iface *ei, union eigrpd_addr *prefix,
742 uint8_t prefixlen)
743{
744 struct summary_addr *summary;
745
746 TAILQ_FOREACH(summary, &ei->summary_list, entry)for((summary) = ((&ei->summary_list)->tqh_first); (
summary) != ((void *)0); (summary) = ((summary)->entry.tqe_next
)) {
747 /* do not filter the summary itself */
748 if (summary->prefixlen == prefixlen &&
749 !eigrp_addrcmp(ei->eigrp->af, prefix, &summary->prefix))
750 return (NULL((void *)0));
751
752 if (summary->prefixlen <= prefixlen &&
753 !eigrp_prefixcmp(ei->eigrp->af, prefix, &summary->prefix,
754 summary->prefixlen))
755 return (summary);
756 }
757
758 return (NULL((void *)0));
759}
760
761static void
762rde_send_update(struct eigrp_iface *ei, struct rinfo *ri)
763{
764 if (ri->metric.hop_count >= ei->eigrp->maximum_hops ||
765 rde_summary_check(ei, &ri->prefix, ri->prefixlen))
766 ri->metric.delay = EIGRP_INFINITE_METRIC((uint32_t )(~0));
767
768 rde_imsg_compose_eigrpe(IMSG_SEND_MUPDATE, ei->ifaceid, 0,
769 ri, sizeof(*ri));
770 rde_imsg_compose_eigrpe(IMSG_SEND_MUPDATE_END, ei->ifaceid, 0,
771 NULL((void *)0), 0);
772}
773
774static void
775rde_send_update_all(struct rt_node *rn, struct rinfo *ri)
776{
777 struct eigrp *eigrp = rn->eigrp;
778 struct eigrp_iface *ei;
779
780 TAILQ_FOREACH(ei, &eigrp->ei_list, e_entry)for((ei) = ((&eigrp->ei_list)->tqh_first); (ei) != (
(void *)0); (ei) = ((ei)->e_entry.tqe_next)) {
781 /* respect split-horizon configuration */
782 if (rn->successor.nbr && rn->successor.nbr->ei == ei &&
783 ei->splithorizon)
784 continue;
785 rde_send_update(ei, ri);
786 }
787}
788
789static void
790rde_send_query(struct eigrp_iface *ei, struct rinfo *ri, int push)
791{
792 rde_imsg_compose_eigrpe(IMSG_SEND_MQUERY, ei->ifaceid, 0,
793 ri, sizeof(*ri));
794 if (push)
795 rde_imsg_compose_eigrpe(IMSG_SEND_MQUERY_END, ei->ifaceid,
796 0, NULL((void *)0), 0);
797}
798
799static void
800rde_send_siaquery(struct rde_nbr *nbr, struct rinfo *ri)
801{
802 rde_imsg_compose_eigrpe(IMSG_SEND_QUERY, nbr->peerid, 0,
803 ri, sizeof(*ri));
804 rde_imsg_compose_eigrpe(IMSG_SEND_SIAQUERY_END, nbr->peerid, 0,
805 NULL((void *)0), 0);
806}
807
808static void
809rde_send_query_all(struct eigrp *eigrp, struct rt_node *rn, int push)
810{
811 struct eigrp_iface *ei;
812 struct rde_nbr *nbr;
813 struct rinfo ri;
814
815 rinfo_fill_successor(rn, &ri);
816 ri.metric.flags |= F_METRIC_ACTIVE0x04;
817
818 TAILQ_FOREACH(ei, &eigrp->ei_list, e_entry)for((ei) = ((&eigrp->ei_list)->tqh_first); (ei) != (
(void *)0); (ei) = ((ei)->e_entry.tqe_next)) {
819 /* respect split-horizon configuration */
820 if (rn->successor.nbr && rn->successor.nbr->ei == ei &&
821 ei->splithorizon)
822 continue;
823
824 rde_send_query(ei, &ri, push);
825 }
826
827 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))
828 if (nbr->ei->eigrp == eigrp && !(nbr->flags & F_RDE_NBR_SELF0x01)) {
829 /* respect split-horizon configuration */
830 if (rn->successor.nbr &&
831 rn->successor.nbr->ei == nbr->ei &&
832 nbr->ei->splithorizon)
833 continue;
834
835 reply_outstanding_add(rn, nbr);
836 }
837}
838
839void
840rde_flush_queries(void)
841{
842 struct eigrp *eigrp;
843 struct eigrp_iface *ei;
844
845 TAILQ_FOREACH(eigrp, &rdeconf->instances, entry)for((eigrp) = ((&rdeconf->instances)->tqh_first); (
eigrp) != ((void *)0); (eigrp) = ((eigrp)->entry.tqe_next)
)
846 TAILQ_FOREACH(ei, &eigrp->ei_list, e_entry)for((ei) = ((&eigrp->ei_list)->tqh_first); (ei) != (
(void *)0); (ei) = ((ei)->e_entry.tqe_next))
847 rde_imsg_compose_eigrpe(IMSG_SEND_MQUERY_END,
848 ei->ifaceid, 0, NULL((void *)0), 0);
849}
850
851static void
852rde_send_reply(struct rde_nbr *nbr, struct rinfo *ri, int siareply)
853{
854 int type;
855
856 if (ri->metric.hop_count >= nbr->eigrp->maximum_hops ||
857 rde_summary_check(nbr->ei, &ri->prefix, ri->prefixlen))
858 ri->metric.delay = EIGRP_INFINITE_METRIC((uint32_t )(~0));
859
860 if (!siareply)
861 type = IMSG_SEND_REPLY_END;
862 else
863 type = IMSG_SEND_SIAREPLY_END;
864
865 rde_imsg_compose_eigrpe(IMSG_SEND_REPLY, nbr->peerid, 0,
866 ri, sizeof(*ri));
867 rde_imsg_compose_eigrpe(type, nbr->peerid, 0, NULL((void *)0), 0);
868}
869
870void
871rde_check_update(struct rde_nbr *nbr, struct rinfo *ri)
872{
873 struct eigrp *eigrp = nbr->eigrp;
874 struct rt_node *rn;
875 struct eigrp_route *route, *successor;
876 uint32_t old_fdistance;
877 struct rinfo sri;
878
879 rn = rt_find(eigrp, ri);
880 if (rn == NULL((void *)0)) {
881 if (ri->metric.delay == EIGRP_INFINITE_METRIC((uint32_t )(~0)))
882 return;
883
884 rn = rt_new(eigrp, ri);
885 route = route_new(rn, nbr, ri);
886
887 old_fdistance = EIGRP_INFINITE_METRIC((uint32_t )(~0));
888 } else {
889 old_fdistance = rn->successor.fdistance;
890
891 if (ri->metric.delay == EIGRP_INFINITE_METRIC((uint32_t )(~0))) {
892 route = route_find(nbr, rn);
893 if (route)
894 route_del(rn, route);
895 } else {
896 route = route_find(nbr, rn);
897 if (route == NULL((void *)0))
898 route = route_new(rn, nbr, ri);
899 else
900 route_update_metrics(eigrp, route, ri);
901 }
902 }
903
904 switch (rn->state) {
905 case DUAL_STA_PASSIVE0x0001:
906 successor = rt_get_successor_fc(rn);
907
908 /*
909 * go active if the successor was affected and no feasible
910 * successor exist.
911 */
912 if (successor == NULL((void *)0)) {
913 rde_send_query_all(eigrp, rn, 1);
914
915 dual_fsm(rn, DUAL_EVT_4);
916 } else {
917 rt_set_successor(rn, successor);
918 rt_update_fib(rn);
919
920 /* send update with new metric if necessary */
921 rinfo_fill_successor(rn, &sri);
922 if (rn->successor.fdistance != old_fdistance)
923 rde_send_update_all(rn, &sri);
924 }
925 break;
926 case DUAL_STA_ACTIVE10x0004:
927 /* XXX event 9 if cost increase? */
928 break;
929 case DUAL_STA_ACTIVE30x0010:
930 /* XXX event 10 if cost increase? */
931 break;
932 }
933
934 if ((rn->state & DUAL_STA_ACTIVE_ALL(0x0002 | 0x0004 | 0x0008 | 0x0010)) && TAILQ_EMPTY(&rn->rijk)(((&rn->rijk)->tqh_first) == ((void *)0)))
935 rde_last_reply(rn);
936}
937
938void
939rde_check_query(struct rde_nbr *nbr, struct rinfo *ri, int siaquery)
940{
941 struct eigrp *eigrp = nbr->eigrp;
942 struct rt_node *rn;
943 struct eigrp_route *route, *successor;
944 uint32_t old_fdistance;
945 struct rinfo sri;
946 int reply_sent = 0;
947
948 /*
949 * draft-savage-eigrp-02 - Section 4.3:
950 * "When a query is received for a route that doesn't exist in our
951 * topology table, a reply with infinite metric is sent and an entry
952 * in the topology table is added with the metric in the QUERY if
953 * the metric is not an infinite value".
954 */
955 rn = rt_find(eigrp, ri);
956 if (rn == NULL((void *)0)) {
957 sri = *ri;
958 sri.metric.delay = EIGRP_INFINITE_METRIC((uint32_t )(~0));
959 rde_send_reply(nbr, &sri, 0);
960
961 if (ri->metric.delay == EIGRP_INFINITE_METRIC((uint32_t )(~0)))
962 return;
963
964 rn = rt_new(eigrp, ri);
965 route = route_new(rn, nbr, ri);
966 rt_set_successor(rn, route);
967 return;
968 }
969
970 old_fdistance = rn->successor.fdistance;
971
972 if (ri->metric.delay == EIGRP_INFINITE_METRIC((uint32_t )(~0))) {
973 route = route_find(nbr, rn);
974 if (route)
975 route_del(rn, route);
976 } else {
977 route = route_find(nbr, rn);
978 if (route == NULL((void *)0))
979 route = route_new(rn, nbr, ri);
980 else
981 route_update_metrics(eigrp, route, ri);
982 }
983
984 switch (rn->state) {
985 case DUAL_STA_PASSIVE0x0001:
986 successor = rt_get_successor_fc(rn);
987
988 /*
989 * go active if the successor was affected and no feasible
990 * successor exist.
991 */
992 if (successor == NULL((void *)0)) {
993 rde_send_query_all(eigrp, rn, 1);
994 dual_fsm(rn, DUAL_EVT_3);
995 } else {
996 rt_set_successor(rn, successor);
997 rt_update_fib(rn);
998
999 /* send reply */
1000 rinfo_fill_successor(rn, &sri);
1001 rde_send_reply(nbr, &sri, 0);
1002 reply_sent = 1;
1003
1004 /* send update with new metric if necessary */
1005 if (rn->successor.fdistance != old_fdistance)
1006 rde_send_update_all(rn, &sri);
1007 }
1008 break;
1009 case DUAL_STA_ACTIVE00x0002:
1010 case DUAL_STA_ACTIVE10x0004:
1011 if (nbr == rn->successor.nbr)
1012 dual_fsm(rn, DUAL_EVT_5);
1013 else {
1014 dual_fsm(rn, DUAL_EVT_6);
1015 rinfo_fill_successor(rn, &sri);
1016 sri.metric.flags |= F_METRIC_ACTIVE0x04;
1017 rde_send_reply(nbr, &sri, 0);
1018 reply_sent = 1;
1019 }
1020 break;
1021 case DUAL_STA_ACTIVE20x0008:
1022 case DUAL_STA_ACTIVE30x0010:
1023 if (nbr == rn->successor.nbr) {
1024 /* XXX not defined in the spec, do nothing? */
1025 } else {
1026 dual_fsm(rn, DUAL_EVT_6);
1027 rinfo_fill_successor(rn, &sri);
1028 sri.metric.flags |= F_METRIC_ACTIVE0x04;
1029 rde_send_reply(nbr, &sri, 0);
1030 reply_sent = 1;
1031 }
1032 break;
1033 }
1034
1035 if ((rn->state & DUAL_STA_ACTIVE_ALL(0x0002 | 0x0004 | 0x0008 | 0x0010)) && TAILQ_EMPTY(&rn->rijk)(((&rn->rijk)->tqh_first) == ((void *)0)))
1036 rde_last_reply(rn);
1037
1038 if (siaquery && !reply_sent) {
1039 rinfo_fill_successor(rn, &sri);
1040 sri.metric.flags |= F_METRIC_ACTIVE0x04;
1041 rde_send_reply(nbr, &sri, 1);
1042 }
1043}
1044
1045static void
1046rde_last_reply(struct rt_node *rn)
1047{
1048 struct eigrp *eigrp = rn->eigrp;
1049 struct eigrp_route *successor;
1050 struct rde_nbr *old_successor;
1051 uint32_t old_fdistance;
1052 struct rinfo ri;
1053
1054 old_successor = rn->successor.nbr;
1055 old_fdistance = rn->successor.fdistance;
1056
1057 switch (rn->state) {
1058 case DUAL_STA_ACTIVE00x0002:
1059 successor = rt_get_successor_fc(rn);
1060 if (successor == NULL((void *)0)) {
1061 /* feasibility condition is not met */
1062 rde_send_query_all(eigrp, rn, 1);
1063 dual_fsm(rn, DUAL_EVT_11);
1064 break;
1065 }
1066
1067 /* update successor - feasibility condition is met */
1068 rt_set_successor(rn, successor);
1069
1070 /* advertise new successor to neighbors */
1071 rinfo_fill_successor(rn, &ri);
1072 rde_send_update_all(rn, &ri);
1073
1074 dual_fsm(rn, DUAL_EVT_14);
1075 break;
1076 case DUAL_STA_ACTIVE10x0004:
1077 /* update successor */
1078 rn->successor.fdistance = EIGRP_INFINITE_METRIC((uint32_t )(~0));
1079 successor = rt_get_successor_fc(rn);
1080 rt_set_successor(rn, successor);
1081
1082 /* advertise new successor to neighbors */
1083 rinfo_fill_successor(rn, &ri);
1084 rde_send_update_all(rn, &ri);
1085
1086 dual_fsm(rn, DUAL_EVT_15);
1087 break;
1088 case DUAL_STA_ACTIVE20x0008:
1089 successor = rt_get_successor_fc(rn);
1090 if (successor == NULL((void *)0)) {
1091 /* feasibility condition is not met */
1092 rde_send_query_all(eigrp, rn, 1);
1093 dual_fsm(rn, DUAL_EVT_12);
1094 break;
1095 }
1096
1097 /* update successor - feasibility condition is met */
1098 rt_set_successor(rn, successor);
1099
1100 /* send a reply to the old successor */
1101 rinfo_fill_successor(rn, &ri);
1102 ri.metric.flags |= F_METRIC_ACTIVE0x04;
1103 if (old_successor)
1104 rde_send_reply(old_successor, &ri, 0);
1105
1106 /* advertise new successor to neighbors */
1107 rde_send_update_all(rn, &ri);
1108
1109 dual_fsm(rn, DUAL_EVT_16);
1110 break;
1111 case DUAL_STA_ACTIVE30x0010:
1112 /* update successor */
1113 rn->successor.fdistance = EIGRP_INFINITE_METRIC((uint32_t )(~0));
1114 successor = rt_get_successor_fc(rn);
1115 rt_set_successor(rn, successor);
1116
1117 /* send a reply to the old successor */
1118 rinfo_fill_successor(rn, &ri);
1119 ri.metric.flags |= F_METRIC_ACTIVE0x04;
1120 if (old_successor)
1121 rde_send_reply(old_successor, &ri, 0);
1122
1123 /* advertise new successor to neighbors */
1124 rde_send_update_all(rn, &ri);
1125
1126 dual_fsm(rn, DUAL_EVT_13);
1127 break;
1128 }
1129
1130 if (rn->state == DUAL_STA_PASSIVE0x0001 && rn->successor.nbr == NULL((void *)0))
1131 rt_del(rn);
1132}
1133
1134void
1135rde_check_reply(struct rde_nbr *nbr, struct rinfo *ri, int siareply)
1136{
1137 struct eigrp *eigrp = nbr->eigrp;
1138 struct rt_node *rn;
1139 struct reply_node *reply;
1140 struct eigrp_route *route;
1141
1142 rn = rt_find(eigrp, ri);
1143 if (rn == NULL((void *)0))
1144 return;
1145
1146 /* XXX ignore reply when the state is passive? */
1147 if (rn->state == DUAL_STA_PASSIVE0x0001)
1148 return;
1149
1150 reply = reply_outstanding_find(rn, nbr);
1151 if (reply == NULL((void *)0))
1152 return;
1153
1154 if (siareply) {
1155 reply->siareply_recv = 1;
1156 reply_active_start_timer(reply);
1157 return;
1158 }
1159
1160 if (ri->metric.delay == EIGRP_INFINITE_METRIC((uint32_t )(~0))) {
1161 route = route_find(nbr, rn);
1162 if (route)
1163 route_del(rn, route);
1164 } else {
1165 route = route_find(nbr, rn);
1166 if (route == NULL((void *)0))
1167 route = route_new(rn, nbr, ri);
1168 else
1169 route_update_metrics(eigrp, route, ri);
1170 }
1171
1172 reply_outstanding_remove(reply);
1173 if (TAILQ_EMPTY(&rn->rijk)(((&rn->rijk)->tqh_first) == ((void *)0)))
1174 rde_last_reply(rn);
1175}
1176
1177void
1178rde_check_link_down_rn(struct rde_nbr *nbr, struct rt_node *rn,
1179 struct eigrp_route *route)
1180{
1181 struct eigrp *eigrp = nbr->eigrp;
1182 struct reply_node *reply;
1183 struct eigrp_route *successor;
1184 uint32_t old_fdistance;
1185 struct rinfo ri;
1186 enum route_type type;
1187
1188 old_fdistance = rn->successor.fdistance;
1189
1190 type = route->type;
1191 route_del(rn, route);
1192
1193 switch (rn->state) {
21
←
Control jumps to 'case 1:' at line 1194
→
1194 case DUAL_STA_PASSIVE0x0001:
1195 successor = rt_get_successor_fc(rn);
22
←
Calling 'rt_get_successor_fc'
→
36
←
Returning from 'rt_get_successor_fc'
→
1196
1197 /*
1198 * go active if the successor was affected and no feasible
1199 * successor exist.
1200 */
1201 if (successor
36.1
'successor' is not equal to NULL
 == NULL((void *)0)) {
37
←
Taking false branch
→
1202 rde_send_query_all(eigrp, rn, 0);
1203
1204 dual_fsm(rn, DUAL_EVT_4);
1205 } else {
1206 rt_set_successor(rn, successor);
38
←
Calling 'rt_set_successor'
→
43
←
Returning from 'rt_set_successor'
→
1207 rt_update_fib(rn);
44
←
Calling 'rt_update_fib'
→
1208
1209 /* send update with new metric if necessary */
1210 rinfo_fill_successor(rn, &ri);
1211 if (rn->successor.fdistance != old_fdistance)
1212 rde_send_update_all(rn, &ri);
1213 }
1214 break;
1215 case DUAL_STA_ACTIVE10x0004:
1216 if (nbr == rn->successor.nbr)
1217 dual_fsm(rn, DUAL_EVT_9);
1218 break;
1219 case DUAL_STA_ACTIVE30x0010:
1220 if (nbr == rn->successor.nbr)
1221 dual_fsm(rn, DUAL_EVT_10);
1222 break;
1223 }
1224
1225 if (rn->state & DUAL_STA_ACTIVE_ALL(0x0002 | 0x0004 | 0x0008 | 0x0010)) {
1226 reply = reply_outstanding_find(rn, nbr);
1227 if (reply) {
1228 rinfo_fill_infinite(rn, type, &ri);
1229 rde_check_reply(nbr, &ri, 0);
1230 }
1231 }
1232}
1233
1234void
1235rde_check_link_down_nbr(struct rde_nbr *nbr)
1236{
1237 struct eigrp *eigrp = nbr->eigrp;
1238 struct rt_node *rn, *safe;
1239 struct eigrp_route *route;
1240
1241 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)) {
5
←
Calling 'rt_tree_RB_NEXT'
→
10
←
Returning from 'rt_tree_RB_NEXT'
→
11
←
Loop condition is true. Entering loop body
→
1242 route = route_find(nbr, rn);
12
←
Calling 'route_find'
→
18
←
Returning from 'route_find'
→
1243 if (route
18.1
'route' is non-null
) {
19
←
Taking true branch
→
1244 rde_check_link_down_rn(nbr, rn, route);
20
←
Calling 'rde_check_link_down_rn'
→
1245 if (rn->successor.nbr == nbr)
1246 rn->successor.nbr = NULL((void *)0);
1247 }
1248 }
1249}
1250
1251void
1252rde_check_link_down(unsigned int ifindex)
1253{
1254 struct rde_nbr *nbr;
1255
1256 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))
1
Loop condition is true. Entering loop body
→
1257 if (nbr->ei->iface->ifindex == ifindex)
2
←
Assuming 'ifindex' is equal to field 'ifindex'
→
3
←
Taking true branch
→
1258 rde_check_link_down_nbr(nbr);
4
←
Calling 'rde_check_link_down_nbr'
→
1259
1260 rde_flush_queries();
1261}
1262
1263void
1264rde_check_link_cost_change(struct rde_nbr *nbr, struct eigrp_iface *ei)
1265{
1266}
1267
1268static __inline int
1269rde_nbr_compare(struct rde_nbr *a, struct rde_nbr *b)
1270{
1271 return (a->peerid - b->peerid);
1272}
1273
1274struct rde_nbr *
1275rde_nbr_find(uint32_t peerid)
1276{
1277 struct rde_nbr n;
1278
1279 n.peerid = peerid;
1280
1281 return (RB_FIND(rde_nbr_head, &rde_nbrs, &n)rde_nbr_head_RB_FIND(&rde_nbrs, &n));
1282}
1283
1284struct rde_nbr *
1285rde_nbr_new(uint32_t peerid, struct rde_nbr *new)
1286{
1287 struct rde_nbr *nbr;
1288
1289 if ((nbr = calloc(1, sizeof(*nbr))) == NULL((void *)0))
1290 fatal("rde_nbr_new");
1291
1292 nbr->peerid = peerid;
1293 nbr->ifaceid = new->ifaceid;
1294 nbr->addr = new->addr;
1295 nbr->ei = eigrp_if_lookup_id(nbr->ifaceid);
1296 if (nbr->ei)
1297 nbr->eigrp = nbr->ei->eigrp;
1298 TAILQ_INIT(&nbr->rijk)do { (&nbr->rijk)->tqh_first = ((void *)0); (&nbr
->rijk)->tqh_last = &(&nbr->rijk)->tqh_first
; } while (0);
1299 nbr->flags = new->flags;
1300
1301 if (nbr->peerid != NBR_IDSELF1 &&
1302 RB_INSERT(rde_nbr_head, &rde_nbrs, nbr)rde_nbr_head_RB_INSERT(&rde_nbrs, nbr) != NULL((void *)0))
1303 fatalx("rde_nbr_new: RB_INSERT failed");
1304
1305 return (nbr);
1306}
1307
1308void
1309rde_nbr_del(struct rde_nbr *nbr, int peerterm)
1310{
1311 struct reply_node *reply;
1312
1313 if (peerterm)
1314 rde_imsg_compose_eigrpe(IMSG_NEIGHBOR_DOWN, nbr->peerid,
1315 0, NULL((void *)0), 0);
1316
1317 while((reply = TAILQ_FIRST(&nbr->rijk)((&nbr->rijk)->tqh_first)) != NULL((void *)0))
1318 reply_outstanding_remove(reply);
1319
1320 if (nbr->peerid != NBR_IDSELF1)
1321 RB_REMOVE(rde_nbr_head, &rde_nbrs, nbr)rde_nbr_head_RB_REMOVE(&rde_nbrs, nbr);
1322 free(nbr);
1323}