Bug Summary

File:src/usr.sbin/snmpd/kroute.c
Warning:line 677, column 6
1st function call argument is an uninitialized value

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 kroute.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/snmpd/obj -resource-dir /usr/local/lib/clang/13.0.0 -I /usr/src/usr.sbin/snmpd -internal-isystem /usr/local/lib/clang/13.0.0/include -internal-externc-isystem /usr/include -O2 -fdebug-compilation-dir=/usr/src/usr.sbin/snmpd/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/snmpd/kroute.c
1/* $OpenBSD: kroute.c,v 1.38 2019/01/22 09:25:29 krw Exp $ */
2
3/*
4 * Copyright (c) 2007, 2008 Reyk Floeter <reyk@openbsd.org>
5 * Copyright (c) 2004 Esben Norby <norby@openbsd.org>
6 * Copyright (c) 2003, 2004 Henning Brauer <henning@openbsd.org>
7 *
8 * Permission to use, copy, modify, and distribute this software for any
9 * purpose with or without fee is hereby granted, provided that the above
10 * copyright notice and this permission notice appear in all copies.
11 *
12 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
13 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
14 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
15 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
16 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
17 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
18 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
19 */
20
21#include <sys/types.h>
22#include <sys/socket.h>
23#include <sys/sysctl.h>
24#include <sys/tree.h>
25#include <sys/uio.h>
26#include <sys/ioctl.h>
27
28#include <net/if.h>
29#include <net/if_dl.h>
30#include <net/if_types.h>
31#include <net/route.h>
32#include <netinet/in.h>
33#include <netinet/if_ether.h>
34#include <arpa/inet.h>
35
36#include <err.h>
37#include <errno(*__errno()).h>
38#include <fcntl.h>
39#include <stdio.h>
40#include <stdlib.h>
41#include <string.h>
42#include <unistd.h>
43#include <event.h>
44
45#include "snmpd.h"
46
47struct ktable **krt;
48u_int krt_size;
49
50struct {
51 struct event ks_ev;
52 u_long ks_iflastchange;
53 u_long ks_nroutes; /* 4 billions enough? */
54 int ks_fd;
55 int ks_ifd;
56 u_short ks_nkif;
57} kr_state;
58
59struct kroute_node {
60 RB_ENTRY(kroute_node)struct { struct kroute_node *rbe_left; struct kroute_node *rbe_right
; struct kroute_node *rbe_parent; int rbe_color; } entry;
61 struct kroute r;
62 struct kroute_node *next;
63};
64
65struct kroute6_node {
66 RB_ENTRY(kroute6_node)struct { struct kroute6_node *rbe_left; struct kroute6_node *
rbe_right; struct kroute6_node *rbe_parent; int rbe_color; } entry;
67 struct kroute6 r;
68 struct kroute6_node *next;
69};
70
71struct kif_node {
72 RB_ENTRY(kif_node)struct { struct kif_node *rbe_left; struct kif_node *rbe_right
; struct kif_node *rbe_parent; int rbe_color; } entry;
73 TAILQ_HEAD(, kif_addr)struct { struct kif_addr *tqh_first; struct kif_addr **tqh_last
; } addrs;
74 TAILQ_HEAD(, kif_arp)struct { struct kif_arp *tqh_first; struct kif_arp **tqh_last
; } arps;
75 struct kif k;
76};
77
78int kroute_compare(struct kroute_node *, struct kroute_node *);
79int kroute6_compare(struct kroute6_node *, struct kroute6_node *);
80int kif_compare(struct kif_node *, struct kif_node *);
81
82void ktable_init(void);
83int ktable_new(u_int, u_int);
84void ktable_free(u_int);
85int ktable_exists(u_int, u_int *);
86struct ktable *ktable_get(u_int);
87int ktable_update(u_int);
88
89struct kroute_node *kroute_find(struct ktable *, in_addr_t, u_int8_t,
90 u_int8_t);
91struct kroute_node *kroute_matchgw(struct kroute_node *,
92 struct sockaddr_in *);
93int kroute_insert(struct ktable *, struct kroute_node *);
94int kroute_remove(struct ktable *, struct kroute_node *);
95void kroute_clear(struct ktable *);
96
97struct kroute6_node *kroute6_find(struct ktable *, const struct in6_addr *,
98 u_int8_t, u_int8_t);
99struct kroute6_node *kroute6_matchgw(struct kroute6_node *,
100 struct sockaddr_in6 *);
101int kroute6_insert(struct ktable *, struct kroute6_node *);
102int kroute6_remove(struct ktable *, struct kroute6_node *);
103void kroute6_clear(struct ktable *);
104
105struct kif_arp *karp_find(struct sockaddr *, u_short);
106int karp_insert(struct kif_node *, struct kif_arp *);
107int karp_remove(struct kif_node *, struct kif_arp *);
108
109struct kif_node *kif_find(u_short);
110struct kif_node *kif_insert(u_short);
111int kif_remove(struct kif_node *);
112void kif_clear(void);
113struct kif *kif_update(u_short, int, struct if_data *,
114 struct sockaddr_dl *);
115
116int ka_compare(struct kif_addr *, struct kif_addr *);
117void ka_insert(u_short, struct kif_addr *);
118struct kif_addr *ka_find(struct sockaddr *);
119int ka_remove(struct kif_addr *);
120
121u_int8_t prefixlen_classful(in_addr_t);
122u_int8_t mask2prefixlen(in_addr_t);
123in_addr_t prefixlen2mask(u_int8_t);
124u_int8_t mask2prefixlen6(struct sockaddr_in6 *);
125struct in6_addr *prefixlen2mask6(u_int8_t);
126void get_rtaddrs(int, struct sockaddr *, struct sockaddr **);
127void if_change(u_short, int, struct if_data *, struct sockaddr_dl *);
128void if_newaddr(u_short, struct sockaddr *, struct sockaddr *,
129 struct sockaddr *);
130void if_deladdr(u_short, struct sockaddr *, struct sockaddr *,
131 struct sockaddr *);
132void if_announce(void *);
133
134int fetchtable(struct ktable *);
135int fetchifs(u_short);
136int fetcharp(struct ktable *);
137void dispatch_rtmsg(int, short, void *);
138int rtmsg_process(char *, int);
139int dispatch_rtmsg_addr(struct ktable *, struct rt_msghdr *,
140 struct sockaddr *[RTAX_MAX15]);
141
142RB_PROTOTYPE(kroute_tree, kroute_node, entry, kroute_compare)void kroute_tree_RB_INSERT_COLOR(struct kroute_tree *, struct
kroute_node *); void kroute_tree_RB_REMOVE_COLOR(struct kroute_tree
*, struct kroute_node *, struct kroute_node *); struct kroute_node
*kroute_tree_RB_REMOVE(struct kroute_tree *, struct kroute_node
*); struct kroute_node *kroute_tree_RB_INSERT(struct kroute_tree
*, struct kroute_node *); struct kroute_node *kroute_tree_RB_FIND
(struct kroute_tree *, struct kroute_node *); struct kroute_node
*kroute_tree_RB_NFIND(struct kroute_tree *, struct kroute_node
*); struct kroute_node *kroute_tree_RB_NEXT(struct kroute_node
*); struct kroute_node *kroute_tree_RB_PREV(struct kroute_node
*); struct kroute_node *kroute_tree_RB_MINMAX(struct kroute_tree
*, int);
143RB_GENERATE(kroute_tree, kroute_node, entry, kroute_compare)void kroute_tree_RB_INSERT_COLOR(struct kroute_tree *head, struct
kroute_node *elm) { struct kroute_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 kroute_tree_RB_REMOVE_COLOR(struct
kroute_tree *head, struct kroute_node *parent, struct kroute_node
*elm) { struct kroute_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 kroute_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 kroute_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 kroute_node
* kroute_tree_RB_REMOVE(struct kroute_tree *head, struct kroute_node
*elm) { struct kroute_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 kroute_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) kroute_tree_RB_REMOVE_COLOR
(head, parent, child); return (old); } struct kroute_node * kroute_tree_RB_INSERT
(struct kroute_tree *head, struct kroute_node *elm) { struct kroute_node
*tmp; struct kroute_node *parent = ((void *)0); int comp = 0
; tmp = (head)->rbh_root; while (tmp) { parent = tmp; comp
= (kroute_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; kroute_tree_RB_INSERT_COLOR
(head, elm); return (((void *)0)); } struct kroute_node * kroute_tree_RB_FIND
(struct kroute_tree *head, struct kroute_node *elm) { struct kroute_node
*tmp = (head)->rbh_root; int comp; while (tmp) { comp = kroute_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 kroute_node * kroute_tree_RB_NFIND
(struct kroute_tree *head, struct kroute_node *elm) { struct kroute_node
*tmp = (head)->rbh_root; struct kroute_node *res = ((void
*)0); int comp; while (tmp) { comp = kroute_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 kroute_node * kroute_tree_RB_NEXT
(struct kroute_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
kroute_node * kroute_tree_RB_PREV(struct kroute_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 kroute_node * kroute_tree_RB_MINMAX
(struct kroute_tree *head, int val) { struct kroute_node *tmp
= (head)->rbh_root; struct kroute_node *parent = ((void *
)0); while (tmp) { parent = tmp; if (val < 0) tmp = (tmp)->
entry.rbe_left; else tmp = (tmp)->entry.rbe_right; } return
(parent); }
144
145RB_PROTOTYPE(kroute6_tree, kroute6_node, entry, kroute6_compare)void kroute6_tree_RB_INSERT_COLOR(struct kroute6_tree *, struct
kroute6_node *); void kroute6_tree_RB_REMOVE_COLOR(struct kroute6_tree
*, struct kroute6_node *, struct kroute6_node *); struct kroute6_node
*kroute6_tree_RB_REMOVE(struct kroute6_tree *, struct kroute6_node
*); struct kroute6_node *kroute6_tree_RB_INSERT(struct kroute6_tree
*, struct kroute6_node *); struct kroute6_node *kroute6_tree_RB_FIND
(struct kroute6_tree *, struct kroute6_node *); struct kroute6_node
*kroute6_tree_RB_NFIND(struct kroute6_tree *, struct kroute6_node
*); struct kroute6_node *kroute6_tree_RB_NEXT(struct kroute6_node
*); struct kroute6_node *kroute6_tree_RB_PREV(struct kroute6_node
*); struct kroute6_node *kroute6_tree_RB_MINMAX(struct kroute6_tree
*, int);
146RB_GENERATE(kroute6_tree, kroute6_node, entry, kroute6_compare)void kroute6_tree_RB_INSERT_COLOR(struct kroute6_tree *head, struct
kroute6_node *elm) { struct kroute6_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 kroute6_tree_RB_REMOVE_COLOR
(struct kroute6_tree *head, struct kroute6_node *parent, struct
kroute6_node *elm) { struct kroute6_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 kroute6_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 kroute6_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 kroute6_node * kroute6_tree_RB_REMOVE
(struct kroute6_tree *head, struct kroute6_node *elm) { struct
kroute6_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 kroute6_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) kroute6_tree_RB_REMOVE_COLOR
(head, parent, child); return (old); } struct kroute6_node * kroute6_tree_RB_INSERT
(struct kroute6_tree *head, struct kroute6_node *elm) { struct
kroute6_node *tmp; struct kroute6_node *parent = ((void *)0)
; int comp = 0; tmp = (head)->rbh_root; while (tmp) { parent
= tmp; comp = (kroute6_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; kroute6_tree_RB_INSERT_COLOR
(head, elm); return (((void *)0)); } struct kroute6_node * kroute6_tree_RB_FIND
(struct kroute6_tree *head, struct kroute6_node *elm) { struct
kroute6_node *tmp = (head)->rbh_root; int comp; while (tmp
) { comp = kroute6_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 kroute6_node * kroute6_tree_RB_NFIND(struct kroute6_tree
*head, struct kroute6_node *elm) { struct kroute6_node *tmp =
(head)->rbh_root; struct kroute6_node *res = ((void *)0);
int comp; while (tmp) { comp = kroute6_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 kroute6_node * kroute6_tree_RB_NEXT
(struct kroute6_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
kroute6_node * kroute6_tree_RB_PREV(struct kroute6_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 kroute6_node * kroute6_tree_RB_MINMAX
(struct kroute6_tree *head, int val) { struct kroute6_node *tmp
= (head)->rbh_root; struct kroute6_node *parent = ((void *
)0); while (tmp) { parent = tmp; if (val < 0) tmp = (tmp)->
entry.rbe_left; else tmp = (tmp)->entry.rbe_right; } return
(parent); }
147
148RB_HEAD(kif_tree, kif_node)struct kif_tree { struct kif_node *rbh_root; } kit;
149RB_PROTOTYPE(kif_tree, kif_node, entry, kif_compare)void kif_tree_RB_INSERT_COLOR(struct kif_tree *, struct kif_node
*); void kif_tree_RB_REMOVE_COLOR(struct kif_tree *, struct kif_node
*, struct kif_node *); struct kif_node *kif_tree_RB_REMOVE(struct
kif_tree *, struct kif_node *); struct kif_node *kif_tree_RB_INSERT
(struct kif_tree *, struct kif_node *); struct kif_node *kif_tree_RB_FIND
(struct kif_tree *, struct kif_node *); struct kif_node *kif_tree_RB_NFIND
(struct kif_tree *, struct kif_node *); struct kif_node *kif_tree_RB_NEXT
(struct kif_node *); struct kif_node *kif_tree_RB_PREV(struct
kif_node *); struct kif_node *kif_tree_RB_MINMAX(struct kif_tree
*, int);
150RB_GENERATE(kif_tree, kif_node, entry, kif_compare)void kif_tree_RB_INSERT_COLOR(struct kif_tree *head, struct kif_node
*elm) { struct kif_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 kif_tree_RB_REMOVE_COLOR(struct kif_tree
*head, struct kif_node *parent, struct kif_node *elm) { struct
kif_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 kif_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 kif_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 kif_node * kif_tree_RB_REMOVE
(struct kif_tree *head, struct kif_node *elm) { struct kif_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 kif_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) kif_tree_RB_REMOVE_COLOR(head
, parent, child); return (old); } struct kif_node * kif_tree_RB_INSERT
(struct kif_tree *head, struct kif_node *elm) { struct kif_node
*tmp; struct kif_node *parent = ((void *)0); int comp = 0; tmp
= (head)->rbh_root; while (tmp) { parent = tmp; comp = (kif_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; kif_tree_RB_INSERT_COLOR(head
, elm); return (((void *)0)); } struct kif_node * kif_tree_RB_FIND
(struct kif_tree *head, struct kif_node *elm) { struct kif_node
*tmp = (head)->rbh_root; int comp; while (tmp) { comp = kif_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 kif_node * kif_tree_RB_NFIND
(struct kif_tree *head, struct kif_node *elm) { struct kif_node
*tmp = (head)->rbh_root; struct kif_node *res = ((void *)
0); int comp; while (tmp) { comp = kif_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 kif_node * kif_tree_RB_NEXT(
struct kif_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 kif_node
* kif_tree_RB_PREV(struct kif_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 kif_node * kif_tree_RB_MINMAX(struct kif_tree
*head, int val) { struct kif_node *tmp = (head)->rbh_root
; struct kif_node *parent = ((void *)0); while (tmp) { parent
= tmp; if (val < 0) tmp = (tmp)->entry.rbe_left; else tmp
= (tmp)->entry.rbe_right; } return (parent); }
151
152RB_HEAD(ka_tree, kif_addr)struct ka_tree { struct kif_addr *rbh_root; } kat;
153RB_PROTOTYPE(ka_tree, kif_addr, node, ka_compare)void ka_tree_RB_INSERT_COLOR(struct ka_tree *, struct kif_addr
*); void ka_tree_RB_REMOVE_COLOR(struct ka_tree *, struct kif_addr
*, struct kif_addr *); struct kif_addr *ka_tree_RB_REMOVE(struct
ka_tree *, struct kif_addr *); struct kif_addr *ka_tree_RB_INSERT
(struct ka_tree *, struct kif_addr *); struct kif_addr *ka_tree_RB_FIND
(struct ka_tree *, struct kif_addr *); struct kif_addr *ka_tree_RB_NFIND
(struct ka_tree *, struct kif_addr *); struct kif_addr *ka_tree_RB_NEXT
(struct kif_addr *); struct kif_addr *ka_tree_RB_PREV(struct kif_addr
*); struct kif_addr *ka_tree_RB_MINMAX(struct ka_tree *, int
);
154RB_GENERATE(ka_tree, kif_addr, node, ka_compare)void ka_tree_RB_INSERT_COLOR(struct ka_tree *head, struct kif_addr
*elm) { struct kif_addr *parent, *gparent, *tmp; while ((parent
= (elm)->node.rbe_parent) && (parent)->node.rbe_color
== 1) { gparent = (parent)->node.rbe_parent; if (parent ==
(gparent)->node.rbe_left) { tmp = (gparent)->node.rbe_right
; if (tmp && (tmp)->node.rbe_color == 1) { (tmp)->
node.rbe_color = 0; do { (parent)->node.rbe_color = 0; (gparent
)->node.rbe_color = 1; } while (0); elm = gparent; continue
; } if ((parent)->node.rbe_right == elm) { do { (tmp) = (parent
)->node.rbe_right; if (((parent)->node.rbe_right = (tmp
)->node.rbe_left)) { ((tmp)->node.rbe_left)->node.rbe_parent
= (parent); } do {} while (0); if (((tmp)->node.rbe_parent
= (parent)->node.rbe_parent)) { if ((parent) == ((parent)
->node.rbe_parent)->node.rbe_left) ((parent)->node.rbe_parent
)->node.rbe_left = (tmp); else ((parent)->node.rbe_parent
)->node.rbe_right = (tmp); } else (head)->rbh_root = (tmp
); (tmp)->node.rbe_left = (parent); (parent)->node.rbe_parent
= (tmp); do {} while (0); if (((tmp)->node.rbe_parent)) do
{} while (0); } while (0); tmp = parent; parent = elm; elm =
tmp; } do { (parent)->node.rbe_color = 0; (gparent)->node
.rbe_color = 1; } while (0); do { (tmp) = (gparent)->node.
rbe_left; if (((gparent)->node.rbe_left = (tmp)->node.rbe_right
)) { ((tmp)->node.rbe_right)->node.rbe_parent = (gparent
); } do {} while (0); if (((tmp)->node.rbe_parent = (gparent
)->node.rbe_parent)) { if ((gparent) == ((gparent)->node
.rbe_parent)->node.rbe_left) ((gparent)->node.rbe_parent
)->node.rbe_left = (tmp); else ((gparent)->node.rbe_parent
)->node.rbe_right = (tmp); } else (head)->rbh_root = (tmp
); (tmp)->node.rbe_right = (gparent); (gparent)->node.rbe_parent
= (tmp); do {} while (0); if (((tmp)->node.rbe_parent)) do
{} while (0); } while (0); } else { tmp = (gparent)->node
.rbe_left; if (tmp && (tmp)->node.rbe_color == 1) {
(tmp)->node.rbe_color = 0; do { (parent)->node.rbe_color
= 0; (gparent)->node.rbe_color = 1; } while (0); elm = gparent
; continue; } if ((parent)->node.rbe_left == elm) { do { (
tmp) = (parent)->node.rbe_left; if (((parent)->node.rbe_left
= (tmp)->node.rbe_right)) { ((tmp)->node.rbe_right)->
node.rbe_parent = (parent); } do {} while (0); if (((tmp)->
node.rbe_parent = (parent)->node.rbe_parent)) { if ((parent
) == ((parent)->node.rbe_parent)->node.rbe_left) ((parent
)->node.rbe_parent)->node.rbe_left = (tmp); else ((parent
)->node.rbe_parent)->node.rbe_right = (tmp); } else (head
)->rbh_root = (tmp); (tmp)->node.rbe_right = (parent); (
parent)->node.rbe_parent = (tmp); do {} while (0); if (((tmp
)->node.rbe_parent)) do {} while (0); } while (0); tmp = parent
; parent = elm; elm = tmp; } do { (parent)->node.rbe_color
= 0; (gparent)->node.rbe_color = 1; } while (0); do { (tmp
) = (gparent)->node.rbe_right; if (((gparent)->node.rbe_right
= (tmp)->node.rbe_left)) { ((tmp)->node.rbe_left)->
node.rbe_parent = (gparent); } do {} while (0); if (((tmp)->
node.rbe_parent = (gparent)->node.rbe_parent)) { if ((gparent
) == ((gparent)->node.rbe_parent)->node.rbe_left) ((gparent
)->node.rbe_parent)->node.rbe_left = (tmp); else ((gparent
)->node.rbe_parent)->node.rbe_right = (tmp); } else (head
)->rbh_root = (tmp); (tmp)->node.rbe_left = (gparent); (
gparent)->node.rbe_parent = (tmp); do {} while (0); if (((
tmp)->node.rbe_parent)) do {} while (0); } while (0); } } (
head->rbh_root)->node.rbe_color = 0; } void ka_tree_RB_REMOVE_COLOR
(struct ka_tree *head, struct kif_addr *parent, struct kif_addr
*elm) { struct kif_addr *tmp; while ((elm == ((void *)0) || (
elm)->node.rbe_color == 0) && elm != (head)->rbh_root
) { if ((parent)->node.rbe_left == elm) { tmp = (parent)->
node.rbe_right; if ((tmp)->node.rbe_color == 1) { do { (tmp
)->node.rbe_color = 0; (parent)->node.rbe_color = 1; } while
(0); do { (tmp) = (parent)->node.rbe_right; if (((parent)
->node.rbe_right = (tmp)->node.rbe_left)) { ((tmp)->
node.rbe_left)->node.rbe_parent = (parent); } do {} while (
0); if (((tmp)->node.rbe_parent = (parent)->node.rbe_parent
)) { if ((parent) == ((parent)->node.rbe_parent)->node.
rbe_left) ((parent)->node.rbe_parent)->node.rbe_left = (
tmp); else ((parent)->node.rbe_parent)->node.rbe_right =
(tmp); } else (head)->rbh_root = (tmp); (tmp)->node.rbe_left
= (parent); (parent)->node.rbe_parent = (tmp); do {} while
(0); if (((tmp)->node.rbe_parent)) do {} while (0); } while
(0); tmp = (parent)->node.rbe_right; } if (((tmp)->node
.rbe_left == ((void *)0) || ((tmp)->node.rbe_left)->node
.rbe_color == 0) && ((tmp)->node.rbe_right == ((void
*)0) || ((tmp)->node.rbe_right)->node.rbe_color == 0))
{ (tmp)->node.rbe_color = 1; elm = parent; parent = (elm)
->node.rbe_parent; } else { if ((tmp)->node.rbe_right ==
((void *)0) || ((tmp)->node.rbe_right)->node.rbe_color
== 0) { struct kif_addr *oleft; if ((oleft = (tmp)->node.
rbe_left)) (oleft)->node.rbe_color = 0; (tmp)->node.rbe_color
= 1; do { (oleft) = (tmp)->node.rbe_left; if (((tmp)->
node.rbe_left = (oleft)->node.rbe_right)) { ((oleft)->node
.rbe_right)->node.rbe_parent = (tmp); } do {} while (0); if
(((oleft)->node.rbe_parent = (tmp)->node.rbe_parent)) {
if ((tmp) == ((tmp)->node.rbe_parent)->node.rbe_left) (
(tmp)->node.rbe_parent)->node.rbe_left = (oleft); else (
(tmp)->node.rbe_parent)->node.rbe_right = (oleft); } else
(head)->rbh_root = (oleft); (oleft)->node.rbe_right = (
tmp); (tmp)->node.rbe_parent = (oleft); do {} while (0); if
(((oleft)->node.rbe_parent)) do {} while (0); } while (0)
; tmp = (parent)->node.rbe_right; } (tmp)->node.rbe_color
= (parent)->node.rbe_color; (parent)->node.rbe_color =
0; if ((tmp)->node.rbe_right) ((tmp)->node.rbe_right)->
node.rbe_color = 0; do { (tmp) = (parent)->node.rbe_right;
if (((parent)->node.rbe_right = (tmp)->node.rbe_left))
{ ((tmp)->node.rbe_left)->node.rbe_parent = (parent); }
do {} while (0); if (((tmp)->node.rbe_parent = (parent)->
node.rbe_parent)) { if ((parent) == ((parent)->node.rbe_parent
)->node.rbe_left) ((parent)->node.rbe_parent)->node.
rbe_left = (tmp); else ((parent)->node.rbe_parent)->node
.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)
->node.rbe_left = (parent); (parent)->node.rbe_parent =
(tmp); do {} while (0); if (((tmp)->node.rbe_parent)) do {
} while (0); } while (0); elm = (head)->rbh_root; break; }
} else { tmp = (parent)->node.rbe_left; if ((tmp)->node
.rbe_color == 1) { do { (tmp)->node.rbe_color = 0; (parent
)->node.rbe_color = 1; } while (0); do { (tmp) = (parent)->
node.rbe_left; if (((parent)->node.rbe_left = (tmp)->node
.rbe_right)) { ((tmp)->node.rbe_right)->node.rbe_parent
= (parent); } do {} while (0); if (((tmp)->node.rbe_parent
= (parent)->node.rbe_parent)) { if ((parent) == ((parent)
->node.rbe_parent)->node.rbe_left) ((parent)->node.rbe_parent
)->node.rbe_left = (tmp); else ((parent)->node.rbe_parent
)->node.rbe_right = (tmp); } else (head)->rbh_root = (tmp
); (tmp)->node.rbe_right = (parent); (parent)->node.rbe_parent
= (tmp); do {} while (0); if (((tmp)->node.rbe_parent)) do
{} while (0); } while (0); tmp = (parent)->node.rbe_left;
} if (((tmp)->node.rbe_left == ((void *)0) || ((tmp)->
node.rbe_left)->node.rbe_color == 0) && ((tmp)->
node.rbe_right == ((void *)0) || ((tmp)->node.rbe_right)->
node.rbe_color == 0)) { (tmp)->node.rbe_color = 1; elm = parent
; parent = (elm)->node.rbe_parent; } else { if ((tmp)->
node.rbe_left == ((void *)0) || ((tmp)->node.rbe_left)->
node.rbe_color == 0) { struct kif_addr *oright; if ((oright =
(tmp)->node.rbe_right)) (oright)->node.rbe_color = 0; (
tmp)->node.rbe_color = 1; do { (oright) = (tmp)->node.rbe_right
; if (((tmp)->node.rbe_right = (oright)->node.rbe_left)
) { ((oright)->node.rbe_left)->node.rbe_parent = (tmp);
} do {} while (0); if (((oright)->node.rbe_parent = (tmp)
->node.rbe_parent)) { if ((tmp) == ((tmp)->node.rbe_parent
)->node.rbe_left) ((tmp)->node.rbe_parent)->node.rbe_left
= (oright); else ((tmp)->node.rbe_parent)->node.rbe_right
= (oright); } else (head)->rbh_root = (oright); (oright)->
node.rbe_left = (tmp); (tmp)->node.rbe_parent = (oright); do
{} while (0); if (((oright)->node.rbe_parent)) do {} while
(0); } while (0); tmp = (parent)->node.rbe_left; } (tmp)->
node.rbe_color = (parent)->node.rbe_color; (parent)->node
.rbe_color = 0; if ((tmp)->node.rbe_left) ((tmp)->node.
rbe_left)->node.rbe_color = 0; do { (tmp) = (parent)->node
.rbe_left; if (((parent)->node.rbe_left = (tmp)->node.rbe_right
)) { ((tmp)->node.rbe_right)->node.rbe_parent = (parent
); } do {} while (0); if (((tmp)->node.rbe_parent = (parent
)->node.rbe_parent)) { if ((parent) == ((parent)->node.
rbe_parent)->node.rbe_left) ((parent)->node.rbe_parent)
->node.rbe_left = (tmp); else ((parent)->node.rbe_parent
)->node.rbe_right = (tmp); } else (head)->rbh_root = (tmp
); (tmp)->node.rbe_right = (parent); (parent)->node.rbe_parent
= (tmp); do {} while (0); if (((tmp)->node.rbe_parent)) do
{} while (0); } while (0); elm = (head)->rbh_root; break;
} } } if (elm) (elm)->node.rbe_color = 0; } struct kif_addr
* ka_tree_RB_REMOVE(struct ka_tree *head, struct kif_addr *elm
) { struct kif_addr *child, *parent, *old = elm; int color; if
((elm)->node.rbe_left == ((void *)0)) child = (elm)->node
.rbe_right; else if ((elm)->node.rbe_right == ((void *)0))
child = (elm)->node.rbe_left; else { struct kif_addr *left
; elm = (elm)->node.rbe_right; while ((left = (elm)->node
.rbe_left)) elm = left; child = (elm)->node.rbe_right; parent
= (elm)->node.rbe_parent; color = (elm)->node.rbe_color
; if (child) (child)->node.rbe_parent = parent; if (parent
) { if ((parent)->node.rbe_left == elm) (parent)->node.
rbe_left = child; else (parent)->node.rbe_right = child; do
{} while (0); } else (head)->rbh_root = child; if ((elm)->
node.rbe_parent == old) parent = elm; (elm)->node = (old)->
node; if ((old)->node.rbe_parent) { if (((old)->node.rbe_parent
)->node.rbe_left == old) ((old)->node.rbe_parent)->node
.rbe_left = elm; else ((old)->node.rbe_parent)->node.rbe_right
= elm; do {} while (0); } else (head)->rbh_root = elm; ((
old)->node.rbe_left)->node.rbe_parent = elm; if ((old)->
node.rbe_right) ((old)->node.rbe_right)->node.rbe_parent
= elm; if (parent) { left = parent; do { do {} while (0); } while
((left = (left)->node.rbe_parent)); } goto color; } parent
= (elm)->node.rbe_parent; color = (elm)->node.rbe_color
; if (child) (child)->node.rbe_parent = parent; if (parent
) { if ((parent)->node.rbe_left == elm) (parent)->node.
rbe_left = child; else (parent)->node.rbe_right = child; do
{} while (0); } else (head)->rbh_root = child; color: if (
color == 0) ka_tree_RB_REMOVE_COLOR(head, parent, child); return
(old); } struct kif_addr * ka_tree_RB_INSERT(struct ka_tree *
head, struct kif_addr *elm) { struct kif_addr *tmp; struct kif_addr
*parent = ((void *)0); int comp = 0; tmp = (head)->rbh_root
; while (tmp) { parent = tmp; comp = (ka_compare)(elm, parent
); if (comp < 0) tmp = (tmp)->node.rbe_left; else if (comp
> 0) tmp = (tmp)->node.rbe_right; else return (tmp); }
do { (elm)->node.rbe_parent = parent; (elm)->node.rbe_left
= (elm)->node.rbe_right = ((void *)0); (elm)->node.rbe_color
= 1; } while (0); if (parent != ((void *)0)) { if (comp <
0) (parent)->node.rbe_left = elm; else (parent)->node.
rbe_right = elm; do {} while (0); } else (head)->rbh_root =
elm; ka_tree_RB_INSERT_COLOR(head, elm); return (((void *)0)
); } struct kif_addr * ka_tree_RB_FIND(struct ka_tree *head, struct
kif_addr *elm) { struct kif_addr *tmp = (head)->rbh_root;
int comp; while (tmp) { comp = ka_compare(elm, tmp); if (comp
< 0) tmp = (tmp)->node.rbe_left; else if (comp > 0)
tmp = (tmp)->node.rbe_right; else return (tmp); } return (
((void *)0)); } struct kif_addr * ka_tree_RB_NFIND(struct ka_tree
*head, struct kif_addr *elm) { struct kif_addr *tmp = (head)
->rbh_root; struct kif_addr *res = ((void *)0); int comp; while
(tmp) { comp = ka_compare(elm, tmp); if (comp < 0) { res =
tmp; tmp = (tmp)->node.rbe_left; } else if (comp > 0) tmp
= (tmp)->node.rbe_right; else return (tmp); } return (res
); } struct kif_addr * ka_tree_RB_NEXT(struct kif_addr *elm) {
if ((elm)->node.rbe_right) { elm = (elm)->node.rbe_right
; while ((elm)->node.rbe_left) elm = (elm)->node.rbe_left
; } else { if ((elm)->node.rbe_parent && (elm == (
(elm)->node.rbe_parent)->node.rbe_left)) elm = (elm)->
node.rbe_parent; else { while ((elm)->node.rbe_parent &&
(elm == ((elm)->node.rbe_parent)->node.rbe_right)) elm
= (elm)->node.rbe_parent; elm = (elm)->node.rbe_parent
; } } return (elm); } struct kif_addr * ka_tree_RB_PREV(struct
kif_addr *elm) { if ((elm)->node.rbe_left) { elm = (elm)->
node.rbe_left; while ((elm)->node.rbe_right) elm = (elm)->
node.rbe_right; } else { if ((elm)->node.rbe_parent &&
(elm == ((elm)->node.rbe_parent)->node.rbe_right)) elm
= (elm)->node.rbe_parent; else { while ((elm)->node.rbe_parent
&& (elm == ((elm)->node.rbe_parent)->node.rbe_left
)) elm = (elm)->node.rbe_parent; elm = (elm)->node.rbe_parent
; } } return (elm); } struct kif_addr * ka_tree_RB_MINMAX(struct
ka_tree *head, int val) { struct kif_addr *tmp = (head)->
rbh_root; struct kif_addr *parent = ((void *)0); while (tmp) {
parent = tmp; if (val < 0) tmp = (tmp)->node.rbe_left;
else tmp = (tmp)->node.rbe_right; } return (parent); }
155
156void
157kr_init(void)
158{
159 int opt = 0, rcvbuf, default_rcvbuf;
160 unsigned int tid = RTABLE_ANY0xffffffff;
161 socklen_t optlen;
162
163 if ((kr_state.ks_ifd = socket(AF_INET2, SOCK_DGRAM2, 0)) == -1)
164 fatal("kr_init: ioctl socket");
165
166 if ((kr_state.ks_fd = socket(AF_ROUTE17, SOCK_RAW3, 0)) == -1)
167 fatal("kr_init: route socket");
168
169 /* not interested in my own messages */
170 if (setsockopt(kr_state.ks_fd, SOL_SOCKET0xffff, SO_USELOOPBACK0x0040,
171 &opt, sizeof(opt)) == -1)
172 log_warn("%s: SO_USELOOPBACK", __func__); /* not fatal */
173
174 if (snmpd_env->sc_rtfilter && setsockopt(kr_state.ks_fd, AF_ROUTE17,
175 ROUTE_MSGFILTER1, &snmpd_env->sc_rtfilter,
176 sizeof(snmpd_env->sc_rtfilter)) == -1)
177 log_warn("%s: ROUTE_MSGFILTER", __func__);
178
179 /* grow receive buffer, don't wanna miss messages */
180 optlen = sizeof(default_rcvbuf);
181 if (getsockopt(kr_state.ks_fd, SOL_SOCKET0xffff, SO_RCVBUF0x1002,
182 &default_rcvbuf, &optlen) == -1)
183 log_warn("%s: SO_RCVBUF", __func__);
184 else
185 for (rcvbuf = MAX_RTSOCK_BUF(2 * 1024 * 1024);
186 rcvbuf > default_rcvbuf &&
187 setsockopt(kr_state.ks_fd, SOL_SOCKET0xffff, SO_RCVBUF0x1002,
188 &rcvbuf, sizeof(rcvbuf)) == -1 && errno(*__errno()) == ENOBUFS55;
189 rcvbuf /= 2)
190 ; /* nothing */
191
192 if (setsockopt(kr_state.ks_fd, AF_ROUTE17, ROUTE_TABLEFILTER2, &tid,
193 sizeof(tid)) == -1)
194 log_warn("%s: ROUTE_TABLEFILTER", __func__);
195
196 RB_INIT(&kit)do { (&kit)->rbh_root = ((void *)0); } while (0);
197 RB_INIT(&kat)do { (&kat)->rbh_root = ((void *)0); } while (0);
198
199 if (fetchifs(0) == -1)
200 fatalx("kr_init: fetchifs");
201
202 ktable_init();
203
204 event_set(&kr_state.ks_ev, kr_state.ks_fd, EV_READ0x02 | EV_PERSIST0x10,
205 dispatch_rtmsg, NULL((void *)0));
206 event_add(&kr_state.ks_ev, NULL((void *)0));
207}
208
209void
210ktable_init(void)
211{
212 u_int i;
213
214 for (i = 0; i <= RT_TABLEID_MAX255; i++)
215 if (ktable_exists(i, NULL((void *)0)))
216 ktable_update(i);
217}
218
219int
220ktable_new(u_int rtableid, u_int rdomid)
221{
222 struct ktable **xkrt;
223 struct ktable *kt;
224 size_t newsize, oldsize;
225
226 /* resize index table if needed */
227 if (rtableid >= krt_size) {
228 if ((xkrt = reallocarray(krt, rtableid + 1,
229 sizeof(struct ktable *))) == NULL((void *)0)) {
230 log_warn("%s: realloc", __func__);
231 return (-1);
232 }
233 krt = xkrt;
234 oldsize = krt_size * sizeof(struct ktable *);
235 krt_size = rtableid + 1;
236 newsize = krt_size * sizeof(struct ktable *);
237 bzero((char *)krt + oldsize, newsize - oldsize);
238 }
239
240 if (krt[rtableid])
241 fatalx("ktable_new: table already exists");
242
243 /* allocate new element */
244 kt = krt[rtableid] = calloc(1, sizeof(struct ktable));
245 if (kt == NULL((void *)0)) {
246 log_warn("%s: calloc", __func__);
247 return (-1);
248 }
249
250 /* initialize structure ... */
251 RB_INIT(&kt->krt)do { (&kt->krt)->rbh_root = ((void *)0); } while (0
);
252 RB_INIT(&kt->krt6)do { (&kt->krt6)->rbh_root = ((void *)0); } while (
0);
253 kt->rtableid = rtableid;
254 kt->rdomain = rdomid;
255
256 /* ... and load it */
257 if (fetchtable(kt) == -1)
258 return (-1);
259 /* load arp information */
260 if (fetcharp(kt) == -1)
261 return (-1);
262
263 log_debug("%s: new ktable for rtableid %d", __func__, rtableid);
264 return (0);
265}
266
267void
268ktable_free(u_int rtableid)
269{
270 struct ktable *kt;
271
272 if ((kt = ktable_get(rtableid)) == NULL((void *)0))
273 return;
274
275 log_debug("%s: freeing ktable rtableid %u", __func__, kt->rtableid);
276 kroute_clear(kt);
277 kroute6_clear(kt);
278
279 krt[kt->rtableid] = NULL((void *)0);
280 free(kt);
281}
282
283struct ktable *
284ktable_get(u_int rtableid)
285{
286 if (rtableid >= krt_size)
287 return (NULL((void *)0));
288 return (krt[rtableid]);
289}
290
291int
292ktable_update(u_int rtableid)
293{
294 struct ktable *kt;
295 u_int rdomid;
296
297 if (!ktable_exists(rtableid, &rdomid))
298 fatalx("ktable_update: table doesn't exist");
299
300 if (rdomid != rtableid) {
301 if (ktable_get(rdomid) == NULL((void *)0) &&
302 ktable_new(rdomid, rdomid) != 0)
303 return (-1);
304 }
305
306 kt = ktable_get(rtableid);
307 if (kt == NULL((void *)0)) {
308 if (ktable_new(rtableid, rdomid))
309 return (-1);
310 }
311 return (0);
312}
313
314int
315ktable_exists(u_int rtableid, u_int *rdomid)
316{
317 size_t len;
318 struct rt_tableinfo info;
319 int mib[6];
320
321 mib[0] = CTL_NET4;
322 mib[1] = PF_ROUTE17;
323 mib[2] = 0;
324 mib[3] = 0;
325 mib[4] = NET_RT_TABLE5;
326 mib[5] = rtableid;
327
328 len = sizeof(info);
329 if (sysctl(mib, 6, &info, &len, NULL((void *)0), 0) == -1) {
330 if (errno(*__errno()) == ENOENT2)
331 /* table nonexistent */
332 return (0);
333 log_warn("%s: sysctl", __func__);
334 /* must return 0 so that the table is considered non-existent */
335 return (0);
336 }
337 if (rdomid)
338 *rdomid = info.rti_domainid;
339 return (1);
340}
341
342void
343kr_shutdown(void)
344{
345 u_int i;
346
347 for (i = krt_size; i > 0; i--)
348 ktable_free(i - 1);
349 kif_clear();
350}
351
352u_int
353kr_ifnumber(void)
354{
355 return (kr_state.ks_nkif);
356}
357
358u_long
359kr_iflastchange(void)
360{
361 return (kr_state.ks_iflastchange);
362}
363
364int
365kr_updateif(u_int if_index)
366{
367 return (fetchifs(if_index));
368}
369
370u_long
371kr_routenumber(void)
372{
373 return (kr_state.ks_nroutes);
374}
375
376/* rb-tree compare */
377int
378kroute_compare(struct kroute_node *a, struct kroute_node *b)
379{
380 if (ntohl(a->r.prefix.s_addr)(__uint32_t)(__builtin_constant_p(a->r.prefix.s_addr) ? (__uint32_t
)(((__uint32_t)(a->r.prefix.s_addr) & 0xff) << 24
| ((__uint32_t)(a->r.prefix.s_addr) & 0xff00) <<
8 | ((__uint32_t)(a->r.prefix.s_addr) & 0xff0000) >>
8 | ((__uint32_t)(a->r.prefix.s_addr) & 0xff000000) >>
24) : __swap32md(a->r.prefix.s_addr)) < ntohl(b->r.prefix.s_addr)(__uint32_t)(__builtin_constant_p(b->r.prefix.s_addr) ? (__uint32_t
)(((__uint32_t)(b->r.prefix.s_addr) & 0xff) << 24
| ((__uint32_t)(b->r.prefix.s_addr) & 0xff00) <<
8 | ((__uint32_t)(b->r.prefix.s_addr) & 0xff0000) >>
8 | ((__uint32_t)(b->r.prefix.s_addr) & 0xff000000) >>
24) : __swap32md(b->r.prefix.s_addr)))
381 return (-1);
382 if (ntohl(a->r.prefix.s_addr)(__uint32_t)(__builtin_constant_p(a->r.prefix.s_addr) ? (__uint32_t
)(((__uint32_t)(a->r.prefix.s_addr) & 0xff) << 24
| ((__uint32_t)(a->r.prefix.s_addr) & 0xff00) <<
8 | ((__uint32_t)(a->r.prefix.s_addr) & 0xff0000) >>
8 | ((__uint32_t)(a->r.prefix.s_addr) & 0xff000000) >>
24) : __swap32md(a->r.prefix.s_addr)) > ntohl(b->r.prefix.s_addr)(__uint32_t)(__builtin_constant_p(b->r.prefix.s_addr) ? (__uint32_t
)(((__uint32_t)(b->r.prefix.s_addr) & 0xff) << 24
| ((__uint32_t)(b->r.prefix.s_addr) & 0xff00) <<
8 | ((__uint32_t)(b->r.prefix.s_addr) & 0xff0000) >>
8 | ((__uint32_t)(b->r.prefix.s_addr) & 0xff000000) >>
24) : __swap32md(b->r.prefix.s_addr)))
383 return (1);
384 if (a->r.prefixlen < b->r.prefixlen)
385 return (-1);
386 if (a->r.prefixlen > b->r.prefixlen)
387 return (1);
388
389 /* if the priority is RTP_ANY finish on the first address hit */
390 if (a->r.priority == RTP_ANY64 || b->r.priority == RTP_ANY64)
391 return (0);
392 if (a->r.priority < b->r.priority)
393 return (-1);
394 if (a->r.priority > b->r.priority)
395 return (1);
396 return (0);
397}
398
399int
400kroute6_compare(struct kroute6_node *a, struct kroute6_node *b)
401{
402 int i;
403
404 for (i = 0; i < 16; i++) {
405 if (a->r.prefix.s6_addr__u6_addr.__u6_addr8[i] < b->r.prefix.s6_addr__u6_addr.__u6_addr8[i])
406 return (-1);
407 if (a->r.prefix.s6_addr__u6_addr.__u6_addr8[i] > b->r.prefix.s6_addr__u6_addr.__u6_addr8[i])
408 return (1);
409 }
410
411 if (a->r.prefixlen < b->r.prefixlen)
412 return (-1);
413 if (a->r.prefixlen > b->r.prefixlen)
414 return (1);
415
416 /* if the priority is RTP_ANY finish on the first address hit */
417 if (a->r.priority == RTP_ANY64 || b->r.priority == RTP_ANY64)
418 return (0);
419 if (a->r.priority < b->r.priority)
420 return (-1);
421 if (a->r.priority > b->r.priority)
422 return (1);
423 return (0);
424}
425
426int
427kif_compare(struct kif_node *a, struct kif_node *b)
428{
429 return (a->k.if_index - b->k.if_index);
430}
431
432int
433ka_compare(struct kif_addr *a, struct kif_addr *b)
434{
435 if (a->addr.sa.sa_family < b->addr.sa.sa_family)
436 return (-1);
437 if (a->addr.sa.sa_family > b->addr.sa.sa_family)
438 return (1);
439 return (memcmp(&a->addr.sa, &b->addr.sa, a->addr.sa.sa_len));
440}
441
442/* tree management */
443struct kroute_node *
444kroute_find(struct ktable *kt, in_addr_t prefix, u_int8_t prefixlen,
445 u_int8_t prio)
446{
447 struct kroute_node s;
448 struct kroute_node *kn, *tmp;
449
450 s.r.prefix.s_addr = prefix;
451 s.r.prefixlen = prefixlen;
452 s.r.priority = prio;
453
454 kn = RB_FIND(kroute_tree, &kt->krt, &s)kroute_tree_RB_FIND(&kt->krt, &s);
455 if (kn && prio == RTP_ANY64) {
456 tmp = RB_PREV(kroute_tree, &kt->krt, kn)kroute_tree_RB_PREV(kn);
457 while (tmp) {
458 if (kroute_compare(&s, tmp) == 0)
459 kn = tmp;
460 else
461 break;
462 tmp = RB_PREV(kroute_tree, &kt->krt, kn)kroute_tree_RB_PREV(kn);
463 }
464 }
465 return (kn);
466}
467
468struct kroute_node *
469kroute_matchgw(struct kroute_node *kr, struct sockaddr_in *sa_in)
470{
471 in_addr_t nexthop;
472
473 if (sa_in == NULL((void *)0)) {
474 log_warnx("%s: no nexthop defined", __func__);
475 return (NULL((void *)0));
476 }
477 nexthop = sa_in->sin_addr.s_addr;
478
479 while (kr) {
480 if (kr->r.nexthop.s_addr == nexthop)
481 return (kr);
482 kr = kr->next;
483 }
484
485 return (NULL((void *)0));
486}
487
488int
489kroute_insert(struct ktable *kt, struct kroute_node *kr)
490{
491 struct kroute_node *krm;
492
493 if ((krm = RB_INSERT(kroute_tree, &kt->krt, kr)kroute_tree_RB_INSERT(&kt->krt, kr)) != NULL((void *)0)) {
494 /* multipath route, add at end of list */
495 while (krm->next != NULL((void *)0))
496 krm = krm->next;
497 krm->next = kr;
498 kr->next = NULL((void *)0); /* to be sure */
499 }
500
501 kr_state.ks_nroutes++;
502 return (0);
503}
504
505int
506kroute_remove(struct ktable *kt, struct kroute_node *kr)
507{
508 struct kroute_node *krm;
509
510 if ((krm = RB_FIND(kroute_tree, &kt->krt, kr)kroute_tree_RB_FIND(&kt->krt, kr)) == NULL((void *)0)) {
511 log_warnx("%s: failed to find %s/%u", __func__,
512 inet_ntoa(kr->r.prefix), kr->r.prefixlen);
513 return (-1);
514 }
515
516 if (krm == kr) {
517 /* head element */
518 if (RB_REMOVE(kroute_tree, &kt->krt, kr)kroute_tree_RB_REMOVE(&kt->krt, kr) == NULL((void *)0)) {
519 log_warnx("%s: failed for %s/%u", __func__,
520 inet_ntoa(kr->r.prefix), kr->r.prefixlen);
521 return (-1);
522 }
523 if (kr->next != NULL((void *)0)) {
524 if (RB_INSERT(kroute_tree, &kt->krt, kr->next)kroute_tree_RB_INSERT(&kt->krt, kr->next)
525 != NULL((void *)0)) {
526 log_warnx("%s: failed to add %s/%u", __func__,
527 inet_ntoa(kr->r.prefix), kr->r.prefixlen);
528 return (-1);
529 }
530 }
531 } else {
532 /* somewhere in the list */
533 while (krm->next != kr && krm->next != NULL((void *)0))
534 krm = krm->next;
535 if (krm->next == NULL((void *)0)) {
536 log_warnx("%s: multipath list corrupted for %s/%u",
537 __func__, inet_ntoa(kr->r.prefix), kr->r.prefixlen);
538 return (-1);
539 }
540 krm->next = kr->next;
541 }
542
543 kr_state.ks_nroutes--;
544 free(kr);
545 return (0);
546}
547
548void
549kroute_clear(struct ktable *kt)
550{
551 struct kroute_node *kr;
552
553 while ((kr = RB_MIN(kroute_tree, &kt->krt)kroute_tree_RB_MINMAX(&kt->krt, -1)) != NULL((void *)0))
554 kroute_remove(kt, kr);
555}
556
557struct kroute6_node *
558kroute6_find(struct ktable *kt, const struct in6_addr *prefix,
559 u_int8_t prefixlen, u_int8_t prio)
560{
561 struct kroute6_node s;
562 struct kroute6_node *kn6, *tmp;
563
564 memcpy(&s.r.prefix, prefix, sizeof(struct in6_addr));
565 s.r.prefixlen = prefixlen;
566 s.r.priority = prio;
567
568 kn6 = RB_FIND(kroute6_tree, &kt->krt6, &s)kroute6_tree_RB_FIND(&kt->krt6, &s);
569 if (kn6 && prio == RTP_ANY64) {
570 tmp = RB_PREV(kroute6_tree, &kt->krt6, kn6)kroute6_tree_RB_PREV(kn6);
571 while (tmp) {
572 if (kroute6_compare(&s, tmp) == 0)
573 kn6 = tmp;
574 else
575 break;
576 tmp = RB_PREV(kroute6_tree, &kt->krt6, kn6)kroute6_tree_RB_PREV(kn6);
577 }
578 }
579 return (kn6);
580}
581
582struct kroute6_node *
583kroute6_matchgw(struct kroute6_node *kr, struct sockaddr_in6 *sa_in6)
584{
585 struct in6_addr nexthop;
586
587 if (sa_in6 == NULL((void *)0)) {
588 log_warnx("%s: no nexthop defined", __func__);
589 return (NULL((void *)0));
590 }
591 memcpy(&nexthop, &sa_in6->sin6_addr, sizeof(nexthop));
592
593 while (kr) {
594 if (memcmp(&kr->r.nexthop, &nexthop, sizeof(nexthop)) == 0)
595 return (kr);
596 kr = kr->next;
597 }
598
599 return (NULL((void *)0));
600}
601
602int
603kroute6_insert(struct ktable *kt, struct kroute6_node *kr)
604{
605 struct kroute6_node *krm;
606
607 if ((krm = RB_INSERT(kroute6_tree, &kt->krt6, kr)kroute6_tree_RB_INSERT(&kt->krt6, kr)) != NULL((void *)0)) {
608 /* multipath route, add at end of list */
609 while (krm->next != NULL((void *)0))
610 krm = krm->next;
611 krm->next = kr;
612 kr->next = NULL((void *)0); /* to be sure */
613 }
614
615 kr_state.ks_nroutes++;
616 return (0);
617}
618
619int
620kroute6_remove(struct ktable *kt, struct kroute6_node *kr)
621{
622 struct kroute6_node *krm;
623
624 if ((krm = RB_FIND(kroute6_tree, &kt->krt6, kr)kroute6_tree_RB_FIND(&kt->krt6, kr)) == NULL((void *)0)) {
625 log_warnx("%s: failed for %s/%u", __func__,
626 log_in6addr(&kr->r.prefix), kr->r.prefixlen);
627 return (-1);
628 }
629
630 if (krm == kr) {
631 /* head element */
632 if (RB_REMOVE(kroute6_tree, &kt->krt6, kr)kroute6_tree_RB_REMOVE(&kt->krt6, kr) == NULL((void *)0)) {
633 log_warnx("%s: failed for %s/%u", __func__,
634 log_in6addr(&kr->r.prefix), kr->r.prefixlen);
635 return (-1);
636 }
637 if (kr->next != NULL((void *)0)) {
638 if (RB_INSERT(kroute6_tree, &kt->krt6, kr->next)kroute6_tree_RB_INSERT(&kt->krt6, kr->next) !=
639 NULL((void *)0)) {
640 log_warnx("%s: failed to add %s/%u", __func__,
641 log_in6addr(&kr->r.prefix),
642 kr->r.prefixlen);
643 return (-1);
644 }
645 }
646 } else {
647 /* somewhere in the list */
648 while (krm->next != kr && krm->next != NULL((void *)0))
649 krm = krm->next;
650 if (krm->next == NULL((void *)0)) {
651 log_warnx("%s: multipath list corrupted for %s/%u",
652 __func__, log_in6addr(&kr->r.prefix),
653 kr->r.prefixlen);
654 return (-1);
655 }
656 krm->next = kr->next;
657 }
658
659 kr_state.ks_nroutes--;
660 free(kr);
661 return (0);
662}
663
664void
665kroute6_clear(struct ktable *kt)
666{
667 struct kroute6_node *kr;
668
669 while ((kr = RB_MIN(kroute6_tree, &kt->krt6)kroute6_tree_RB_MINMAX(&kt->krt6, -1)) != NULL((void *)0))
670 kroute6_remove(kt, kr);
671}
672
673static inline int
674karp_compare(struct kif_arp *a, struct kif_arp *b)
675{
676 /* Interface indices are assumed equal */
677 if (ntohl(a->addr.sin.sin_addr.s_addr)(__uint32_t)(__builtin_constant_p(a->addr.sin.sin_addr.s_addr
) ? (__uint32_t)(((__uint32_t)(a->addr.sin.sin_addr.s_addr
) & 0xff) << 24 | ((__uint32_t)(a->addr.sin.sin_addr
.s_addr) & 0xff00) << 8 | ((__uint32_t)(a->addr.
sin.sin_addr.s_addr) & 0xff0000) >> 8 | ((__uint32_t
)(a->addr.sin.sin_addr.s_addr) & 0xff000000) >> 24
) : __swap32md(a->addr.sin.sin_addr.s_addr)) >
10
←
1st function call argument is an uninitialized value
678 ntohl(b->addr.sin.sin_addr.s_addr)(__uint32_t)(__builtin_constant_p(b->addr.sin.sin_addr.s_addr
) ? (__uint32_t)(((__uint32_t)(b->addr.sin.sin_addr.s_addr
) & 0xff) << 24 | ((__uint32_t)(b->addr.sin.sin_addr
.s_addr) & 0xff00) << 8 | ((__uint32_t)(b->addr.
sin.sin_addr.s_addr) & 0xff0000) >> 8 | ((__uint32_t
)(b->addr.sin.sin_addr.s_addr) & 0xff000000) >> 24
) : __swap32md(b->addr.sin.sin_addr.s_addr)))
679 return (1);
680 if (ntohl(a->addr.sin.sin_addr.s_addr)(__uint32_t)(__builtin_constant_p(a->addr.sin.sin_addr.s_addr
) ? (__uint32_t)(((__uint32_t)(a->addr.sin.sin_addr.s_addr
) & 0xff) << 24 | ((__uint32_t)(a->addr.sin.sin_addr
.s_addr) & 0xff00) << 8 | ((__uint32_t)(a->addr.
sin.sin_addr.s_addr) & 0xff0000) >> 8 | ((__uint32_t
)(a->addr.sin.sin_addr.s_addr) & 0xff000000) >> 24
) : __swap32md(a->addr.sin.sin_addr.s_addr)) <
681 ntohl(b->addr.sin.sin_addr.s_addr)(__uint32_t)(__builtin_constant_p(b->addr.sin.sin_addr.s_addr
) ? (__uint32_t)(((__uint32_t)(b->addr.sin.sin_addr.s_addr
) & 0xff) << 24 | ((__uint32_t)(b->addr.sin.sin_addr
.s_addr) & 0xff00) << 8 | ((__uint32_t)(b->addr.
sin.sin_addr.s_addr) & 0xff0000) >> 8 | ((__uint32_t
)(b->addr.sin.sin_addr.s_addr) & 0xff000000) >> 24
) : __swap32md(b->addr.sin.sin_addr.s_addr)))
682 return (-1);
683 return (0);
684}
685
686static inline struct kif_arp *
687karp_search(struct kif_node *kn, struct kif_arp *ka)
688{
689 struct kif_arp *pivot;
690
691 TAILQ_FOREACH(pivot, &kn->arps, entry)for((pivot) = ((&kn->arps)->tqh_first); (pivot) != (
(void *)0); (pivot) = ((pivot)->entry.tqe_next)) {
7
←
Assuming 'pivot' is not equal to null
→
8
←
Loop condition is true. Entering loop body
→
692 switch (karp_compare(ka, pivot)) {
9
←
Calling 'karp_compare'
→
693 case 0: /* found */
694 return (pivot);
695 case -1: /* ka < pivot, end the search */
696 return (NULL((void *)0));
697 }
698 }
699 /* looped through the whole list and didn't find */
700 return (NULL((void *)0));
701}
702
703struct kif_arp *
704karp_find(struct sockaddr *sa, u_short ifindex)
705{
706 struct kif_node *kn;
707 struct kif_arp *ka = NULL((void *)0), s;
708
709 memcpy(&s.addr.sa, sa, sa->sa_len);
710
711 if (ifindex == 0) {
2
←
Assuming 'ifindex' is equal to 0
→
3
←
Taking true branch
→
712 /*
713 * We iterate manually to handle zero ifindex special
714 * case differently from kif_find, in particular we
715 * want to look for the address on all available
716 * interfaces.
717 */
718 RB_FOREACH(kn, kif_tree, &kit)for ((kn) = kif_tree_RB_MINMAX(&kit, -1); (kn) != ((void *
)0); (kn) = kif_tree_RB_NEXT(kn)) {
4
←
Assuming 'kn' is not equal to null
→
5
←
Loop condition is true. Entering loop body
→
719 if ((ka = karp_search(kn, &s)) != NULL((void *)0))
6
←
Calling 'karp_search'
→
720 break;
721 }
722 } else {
723 if ((kn = kif_find(ifindex)) == NULL((void *)0))
724 return (NULL((void *)0));
725 ka = karp_search(kn, &s);
726 }
727 return (ka);
728}
729
730int
731karp_insert(struct kif_node *kn, struct kif_arp *ka)
732{
733 struct kif_arp *pivot;
734
735 if (ka->if_index == 0)
736 return (-1);
737 if (!kn && (kn = kif_find(ka->if_index)) == NULL((void *)0))
738 return (-1);
739 /* Put entry on the list in the ascending lexical order */
740 TAILQ_FOREACH(pivot, &kn->arps, entry)for((pivot) = ((&kn->arps)->tqh_first); (pivot) != (
(void *)0); (pivot) = ((pivot)->entry.tqe_next)) {
741 switch (karp_compare(ka, pivot)) {
742 case 0: /* collision */
743 return (-1);
744 case -1: /* ka < pivot */
745 TAILQ_INSERT_BEFORE(pivot, ka, entry)do { (ka)->entry.tqe_prev = (pivot)->entry.tqe_prev; (ka
)->entry.tqe_next = (pivot); *(pivot)->entry.tqe_prev =
(ka); (pivot)->entry.tqe_prev = &(ka)->entry.tqe_next
; } while (0);
746 return (0);
747 }
748 }
749 /* ka is larger than any other element on the list */
750 TAILQ_INSERT_TAIL(&kn->arps, ka, entry)do { (ka)->entry.tqe_next = ((void *)0); (ka)->entry.tqe_prev
= (&kn->arps)->tqh_last; *(&kn->arps)->tqh_last
= (ka); (&kn->arps)->tqh_last = &(ka)->entry
.tqe_next; } while (0);
751 return (0);
752}
753
754int
755karp_remove(struct kif_node *kn, struct kif_arp *ka)
756{
757 if (ka->if_index == 0)
758 return (-1);
759 if (!kn && (kn = kif_find(ka->if_index)) == NULL((void *)0))
760 return (-1);
761 TAILQ_REMOVE(&kn->arps, ka, entry)do { if (((ka)->entry.tqe_next) != ((void *)0)) (ka)->entry
.tqe_next->entry.tqe_prev = (ka)->entry.tqe_prev; else (
&kn->arps)->tqh_last = (ka)->entry.tqe_prev; *(ka
)->entry.tqe_prev = (ka)->entry.tqe_next; ; ; } while (
0);
762 free(ka);
763 return (0);
764}
765
766struct kif_arp *
767karp_first(u_short ifindex)
768{
769 struct kif_node *kn;
770
771 if ((kn = kif_find(ifindex)) == NULL((void *)0))
772 return (NULL((void *)0));
773 return (TAILQ_FIRST(&kn->arps)((&kn->arps)->tqh_first));
774}
775
776struct kif_arp *
777karp_getaddr(struct sockaddr *sa, u_short ifindex, int next)
778{
779 struct kif_arp *ka;
780
781 if ((ka = karp_find(sa, ifindex)) == NULL((void *)0))
1
Calling 'karp_find'
→
782 return (NULL((void *)0));
783 return (next ? TAILQ_NEXT(ka, entry)((ka)->entry.tqe_next) : ka);
784}
785
786struct kif_node *
787kif_find(u_short if_index)
788{
789 struct kif_node s;
790
791 if (if_index == 0)
792 return (RB_MIN(kif_tree, &kit)kif_tree_RB_MINMAX(&kit, -1));
793
794 bzero(&s, sizeof(s));
795 s.k.if_index = if_index;
796
797 return (RB_FIND(kif_tree, &kit, &s)kif_tree_RB_FIND(&kit, &s));
798}
799
800struct kif *
801kr_getif(u_short if_index)
802{
803 struct kif_node *kn;
804
805 kn = kif_find(if_index);
806 if (kn == NULL((void *)0))
807 return (NULL((void *)0));
808
809 return (&kn->k);
810}
811
812struct kif *
813kr_getnextif(u_short if_index)
814{
815 struct kif_node *kn;
816
817 if ((kn = kif_find(if_index)) == NULL((void *)0))
818 return (NULL((void *)0));
819 if (if_index)
820 kn = RB_NEXT(kif_tree, &kit, kn)kif_tree_RB_NEXT(kn);
821 if (kn == NULL((void *)0))
822 return (NULL((void *)0));
823
824 return (&kn->k);
825}
826
827struct kif_node *
828kif_insert(u_short if_index)
829{
830 struct kif_node *kif;
831
832 if ((kif = calloc(1, sizeof(struct kif_node))) == NULL((void *)0))
833 return (NULL((void *)0));
834
835 kif->k.if_index = if_index;
836 TAILQ_INIT(&kif->addrs)do { (&kif->addrs)->tqh_first = ((void *)0); (&
kif->addrs)->tqh_last = &(&kif->addrs)->tqh_first
; } while (0);
837 TAILQ_INIT(&kif->arps)do { (&kif->arps)->tqh_first = ((void *)0); (&kif
->arps)->tqh_last = &(&kif->arps)->tqh_first
; } while (0);
838
839 if (RB_INSERT(kif_tree, &kit, kif)kif_tree_RB_INSERT(&kit, kif) != NULL((void *)0))
840 fatalx("kif_insert: RB_INSERT");
841
842 kr_state.ks_nkif++;
843 kr_state.ks_iflastchange = smi_getticks();
844
845 return (kif);
846}
847
848int
849kif_remove(struct kif_node *kif)
850{
851 struct kif_addr *ka;
852 struct kif_arp *kr;
853
854 if (RB_REMOVE(kif_tree, &kit, kif)kif_tree_RB_REMOVE(&kit, kif) == NULL((void *)0)) {
855 log_warnx("%s: RB_REMOVE failed", __func__);
856 return (-1);
857 }
858
859 while ((ka = TAILQ_FIRST(&kif->addrs)((&kif->addrs)->tqh_first)) != NULL((void *)0)) {
860 TAILQ_REMOVE(&kif->addrs, ka, entry)do { if (((ka)->entry.tqe_next) != ((void *)0)) (ka)->entry
.tqe_next->entry.tqe_prev = (ka)->entry.tqe_prev; else (
&kif->addrs)->tqh_last = (ka)->entry.tqe_prev; *
(ka)->entry.tqe_prev = (ka)->entry.tqe_next; ; ; } while
(0);
861 ka_remove(ka);
862 }
863 while ((kr = TAILQ_FIRST(&kif->arps)((&kif->arps)->tqh_first)) != NULL((void *)0)) {
864 karp_remove(kif, kr);
865 }
866 free(kif);
867
868 kr_state.ks_nkif--;
869 kr_state.ks_iflastchange = smi_getticks();
870
871 return (0);
872}
873
874void
875kif_clear(void)
876{
877 struct kif_node *kif;
878
879 while ((kif = RB_MIN(kif_tree, &kit)kif_tree_RB_MINMAX(&kit, -1)) != NULL((void *)0))
880 kif_remove(kif);
881 kr_state.ks_nkif = 0;
882 kr_state.ks_iflastchange = smi_getticks();
883}
884
885struct kif *
886kif_update(u_short if_index, int flags, struct if_data *ifd,
887 struct sockaddr_dl *sdl)
888{
889 struct kif_node *kif;
890 struct ether_addr *ea;
891 struct ifreq ifr;
892
893 if ((kif = kif_find(if_index)) == NULL((void *)0))
894 if ((kif = kif_insert(if_index)) == NULL((void *)0))
895 return (NULL((void *)0));
896
897 kif->k.if_flags = flags;
898 bcopy(ifd, &kif->k.if_data, sizeof(struct if_data));
899 kif->k.if_ticks = smi_getticks();
900
901 if (sdl && sdl->sdl_family == AF_LINK18) {
902 if (sdl->sdl_nlen >= sizeof(kif->k.if_name))
903 memcpy(kif->k.if_name, sdl->sdl_data,
904 sizeof(kif->k.if_name) - 1);
905 else if (sdl->sdl_nlen > 0)
906 memcpy(kif->k.if_name, sdl->sdl_data,
907 sdl->sdl_nlen);
908 /* string already terminated via calloc() */
909
910 if ((ea = (struct ether_addr *)LLADDR(sdl)((caddr_t)((sdl)->sdl_data + (sdl)->sdl_nlen))) != NULL((void *)0))
911 bcopy(&ea->ether_addr_octet, kif->k.if_lladdr,
912 ETHER_ADDR_LEN6);
913 }
914
915 bzero(&ifr, sizeof(ifr));
916 strlcpy(ifr.ifr_name, kif->k.if_name, sizeof(ifr.ifr_name));
917 ifr.ifr_dataifr_ifru.ifru_data = (caddr_t)&kif->k.if_descr;
918 if (ioctl(kr_state.ks_ifd, SIOCGIFDESCR(((unsigned long)0x80000000|(unsigned long)0x40000000) | ((sizeof
(struct ifreq) & 0x1fff) << 16) | ((('i')) <<
8) | ((129))), &ifr) == -1)
919 bzero(&kif->k.if_descr, sizeof(kif->k.if_descr));
920
921 return (&kif->k);
922}
923
924void
925ka_insert(u_short if_index, struct kif_addr *ka)
926{
927 if (ka->addr.sa.sa_len == 0)
928 return;
929
930 ka->if_index = if_index;
931 RB_INSERT(ka_tree, &kat, ka)ka_tree_RB_INSERT(&kat, ka);
932}
933
934struct kif_addr *
935ka_find(struct sockaddr *sa)
936{
937 struct kif_addr ka;
938
939 if (sa == NULL((void *)0))
940 return (RB_MIN(ka_tree, &kat)ka_tree_RB_MINMAX(&kat, -1));
941 bzero(&ka.addr, sizeof(ka.addr));
942 bcopy(sa, &ka.addr.sa, sa->sa_len);
943 return (RB_FIND(ka_tree, &kat, &ka)ka_tree_RB_FIND(&kat, &ka));
944}
945
946int
947ka_remove(struct kif_addr *ka)
948{
949 RB_REMOVE(ka_tree, &kat, ka)ka_tree_RB_REMOVE(&kat, ka);
950 free(ka);
951 return (0);
952}
953
954struct kif_addr *
955kr_getaddr(struct sockaddr *sa)
956{
957 return (ka_find(sa));
958}
959
960struct kif_addr *
961kr_getnextaddr(struct sockaddr *sa)
962{
963 struct kif_addr *ka;
964
965 if ((ka = ka_find(sa)) == NULL((void *)0))
966 return (NULL((void *)0));
967 if (sa)
968 ka = RB_NEXT(ka_tree, &kat, ka)ka_tree_RB_NEXT(ka);
969
970 return (ka);
971}
972
973/* misc */
974u_int8_t
975prefixlen_classful(in_addr_t ina)
976{
977 /* it hurt to write this. */
978
979 if (ina >= 0xf0000000U) /* class E */
980 return (32);
981 else if (ina >= 0xe0000000U) /* class D */
982 return (4);
983 else if (ina >= 0xc0000000U) /* class C */
984 return (24);
985 else if (ina >= 0x80000000U) /* class B */
986 return (16);
987 else /* class A */
988 return (8);
989}
990
991u_int8_t
992mask2prefixlen(in_addr_t ina)
993{
994 if (ina == 0)
995 return (0);
996 else
997 return (33 - ffs(ntohl(ina)(__uint32_t)(__builtin_constant_p(ina) ? (__uint32_t)(((__uint32_t
)(ina) & 0xff) << 24 | ((__uint32_t)(ina) & 0xff00
) << 8 | ((__uint32_t)(ina) & 0xff0000) >> 8 |
((__uint32_t)(ina) & 0xff000000) >> 24) : __swap32md
(ina))));
998}
999
1000in_addr_t
1001prefixlen2mask(u_int8_t prefixlen)
1002{
1003 if (prefixlen == 0)
1004 return (0);
1005
1006 return (htonl(0xffffffff << (32 - prefixlen))(__uint32_t)(__builtin_constant_p(0xffffffff << (32 - prefixlen
)) ? (__uint32_t)(((__uint32_t)(0xffffffff << (32 - prefixlen
)) & 0xff) << 24 | ((__uint32_t)(0xffffffff <<
(32 - prefixlen)) & 0xff00) << 8 | ((__uint32_t)(0xffffffff
<< (32 - prefixlen)) & 0xff0000) >> 8 | ((__uint32_t
)(0xffffffff << (32 - prefixlen)) & 0xff000000) >>
24) : __swap32md(0xffffffff << (32 - prefixlen))));
1007}
1008
1009u_int8_t
1010mask2prefixlen6(struct sockaddr_in6 *sa_in6)
1011{
1012 unsigned int l = 0;
1013 u_int8_t *ap, *ep;
1014
1015 /*
1016 * sin6_len is the size of the sockaddr so substract the offset of
1017 * the possibly truncated sin6_addr struct.
1018 */
1019 ap = (u_int8_t *)&sa_in6->sin6_addr;
1020 ep = (u_int8_t *)sa_in6 + sa_in6->sin6_len;
1021 for (; ap < ep; ap++) {
1022 /* this "beauty" is adopted from sbin/route/show.c ... */
1023 switch (*ap) {
1024 case 0xff:
1025 l += 8;
1026 break;
1027 case 0xfe:
1028 l += 7;
1029 goto done;
1030 case 0xfc:
1031 l += 6;
1032 goto done;
1033 case 0xf8:
1034 l += 5;
1035 goto done;
1036 case 0xf0:
1037 l += 4;
1038 goto done;
1039 case 0xe0:
1040 l += 3;
1041 goto done;
1042 case 0xc0:
1043 l += 2;
1044 goto done;
1045 case 0x80:
1046 l += 1;
1047 goto done;
1048 case 0x00:
1049 goto done;
1050 default:
1051 fatalx("non contiguous inet6 netmask");
1052 }
1053 }
1054
1055done:
1056 if (l > sizeof(struct in6_addr) * 8)
1057 fatalx("inet6 prefixlen out of bound");
1058 return (l);
1059}
1060
1061struct in6_addr *
1062prefixlen2mask6(u_int8_t prefixlen)
1063{
1064 static struct in6_addr mask;
1065 int i;
1066
1067 bzero(&mask, sizeof(mask));
1068 for (i = 0; i < prefixlen / 8; i++)
1069 mask.s6_addr__u6_addr.__u6_addr8[i] = 0xff;
1070 i = prefixlen % 8;
1071 if (i)
1072 mask.s6_addr__u6_addr.__u6_addr8[prefixlen / 8] = 0xff00 >> i;
1073
1074 return (&mask);
1075}
1076
1077#define ROUNDUP(a)((a) > 0 ? (1 + (((a) - 1) | (sizeof(long) - 1))) : sizeof
(long)) \
1078 ((a) > 0 ? (1 + (((a) - 1) | (sizeof(long) - 1))) : sizeof(long))
1079
1080void
1081get_rtaddrs(int addrs, struct sockaddr *sa, struct sockaddr **rti_info)
1082{
1083 int i;
1084
1085 for (i = 0; i < RTAX_MAX15; i++) {
1086 if (addrs & (1 << i)) {
1087 rti_info[i] = sa;
1088 sa = (struct sockaddr *)((char *)(sa) +
1089 ROUNDUP(sa->sa_len)((sa->sa_len) > 0 ? (1 + (((sa->sa_len) - 1) | (sizeof
(long) - 1))) : sizeof(long)));
1090 } else
1091 rti_info[i] = NULL((void *)0);
1092
1093 }
1094}
1095
1096void
1097if_change(u_short if_index, int flags, struct if_data *ifd,
1098 struct sockaddr_dl *sdl)
1099{
1100 if (kif_update(if_index, flags, ifd, sdl) == NULL((void *)0))
1101 log_warn("%s: interface %u update failed", __func__, if_index);
1102}
1103
1104void
1105if_newaddr(u_short if_index, struct sockaddr *ifa, struct sockaddr *mask,
1106 struct sockaddr *brd)
1107{
1108 struct kif_node *kif;
1109 struct kif_addr *ka;
1110
1111 if (ifa == NULL((void *)0))
1112 return;
1113 if ((kif = kif_find(if_index)) == NULL((void *)0)) {
1114 log_warnx("%s: corresponding if %u not found", __func__,
1115 if_index);
1116 return;
1117 }
1118 if ((ka = ka_find(ifa)) == NULL((void *)0)) {
1119 if ((ka = calloc(1, sizeof(struct kif_addr))) == NULL((void *)0))
1120 fatal("if_newaddr");
1121 bcopy(ifa, &ka->addr.sa, ifa->sa_len);
1122 TAILQ_INSERT_TAIL(&kif->addrs, ka, entry)do { (ka)->entry.tqe_next = ((void *)0); (ka)->entry.tqe_prev
= (&kif->addrs)->tqh_last; *(&kif->addrs)->
tqh_last = (ka); (&kif->addrs)->tqh_last = &(ka
)->entry.tqe_next; } while (0);
1123 ka_insert(if_index, ka);
1124 }
1125
1126 if (mask)
1127 bcopy(mask, &ka->mask.sa, mask->sa_len);
1128 else
1129 bzero(&ka->mask, sizeof(ka->mask));
1130 if (brd)
1131 bcopy(brd, &ka->dstbrd.sa, brd->sa_len);
1132 else
1133 bzero(&ka->dstbrd, sizeof(ka->dstbrd));
1134}
1135
1136void
1137if_deladdr(u_short if_index, struct sockaddr *ifa, struct sockaddr *mask,
1138 struct sockaddr *brd)
1139{
1140 struct kif_node *kif;
1141 struct kif_addr *ka;
1142
1143 if (ifa == NULL((void *)0))
1144 return;
1145 if ((kif = kif_find(if_index)) == NULL((void *)0)) {
1146 log_warnx("%s: corresponding if %u not found", __func__,
1147 if_index);
1148 return;
1149 }
1150 if ((ka = ka_find(ifa)) == NULL((void *)0))
1151 return;
1152
1153 TAILQ_REMOVE(&kif->addrs, ka, entry)do { if (((ka)->entry.tqe_next) != ((void *)0)) (ka)->entry
.tqe_next->entry.tqe_prev = (ka)->entry.tqe_prev; else (
&kif->addrs)->tqh_last = (ka)->entry.tqe_prev; *
(ka)->entry.tqe_prev = (ka)->entry.tqe_next; ; ; } while
(0);
1154 ka_remove(ka);
1155}
1156
1157void
1158if_announce(void *msg)
1159{
1160 struct if_announcemsghdr *ifan;
1161 struct kif_node *kif;
1162
1163 ifan = msg;
1164
1165 switch (ifan->ifan_what) {
1166 case IFAN_ARRIVAL0:
1167 kif = kif_insert(ifan->ifan_index);
1168 strlcpy(kif->k.if_name, ifan->ifan_name,
1169 sizeof(kif->k.if_name));
1170 break;
1171 case IFAN_DEPARTURE1:
1172 kif = kif_find(ifan->ifan_index);
1173 kif_remove(kif);
1174 break;
1175 }
1176}
1177
1178int
1179fetchtable(struct ktable *kt)
1180{
1181 int mib[7];
1182 size_t len;
1183 char *buf;
1184 int rv;
1185
1186 mib[0] = CTL_NET4;
1187 mib[1] = PF_ROUTE17;
1188 mib[2] = 0;
1189 mib[3] = AF_INET2;
1190 mib[4] = NET_RT_DUMP1;
1191 mib[5] = 0;
1192 mib[6] = kt->rtableid;
1193
1194 if (sysctl(mib, 7, NULL((void *)0), &len, NULL((void *)0), 0) == -1) {
1195 if (kt->rtableid != 0 && errno(*__errno()) == EINVAL22)
1196 /* table nonexistent */
1197 return (0);
1198 log_warn("%s: failed to fetch routing table %u size", __func__,
1199 kt->rtableid);
1200 return (-1);
1201 }
1202 if (len == 0)
1203 return (0);
1204 if ((buf = malloc(len)) == NULL((void *)0)) {
1205 log_warn("%s: malloc", __func__);
1206 return (-1);
1207 }
1208 if (sysctl(mib, 7, buf, &len, NULL((void *)0), 0) == -1) {
1209 log_warn("%s: failed to fetch routing table %u", __func__,
1210 kt->rtableid);
1211 free(buf);
1212 return (-1);
1213 }
1214
1215 rv = rtmsg_process(buf, len);
1216 free(buf);
1217
1218 return (rv);
1219}
1220
1221int
1222fetchifs(u_short if_index)
1223{
1224 size_t len;
1225 int mib[6];
1226 char *buf;
1227 int rv;
1228
1229 mib[0] = CTL_NET4;
1230 mib[1] = PF_ROUTE17;
1231 mib[2] = 0;
1232 mib[3] = 0; /* wildcard address family */
1233 mib[4] = NET_RT_IFLIST3;
1234 mib[5] = if_index;
1235
1236 if (sysctl(mib, 6, NULL((void *)0), &len, NULL((void *)0), 0) == -1) {
1237 log_warn("%s: failed to fetch address table size for %u",
1238 __func__, if_index);
1239 return (-1);
1240 }
1241 if ((buf = malloc(len)) == NULL((void *)0)) {
1242 log_warn("%s: malloc", __func__);
1243 return (-1);
1244 }
1245 if (sysctl(mib, 6, buf, &len, NULL((void *)0), 0) == -1) {
1246 log_warn("%s: failed to fetch address table for %u",
1247 __func__, if_index);
1248 free(buf);
1249 return (-1);
1250 }
1251
1252 rv = rtmsg_process(buf, len);
1253 free(buf);
1254
1255 return (rv);
1256}
1257
1258int
1259fetcharp(struct ktable *kt)
1260{
1261 size_t len;
1262 int mib[7];
1263 char *buf;
1264 int rv;
1265
1266 mib[0] = CTL_NET4;
1267 mib[1] = PF_ROUTE17;
1268 mib[2] = 0;
1269 mib[3] = AF_INET2;
1270 mib[4] = NET_RT_FLAGS2;
1271 mib[5] = RTF_LLINFO0x400;
1272 mib[6] = kt->rtableid;
1273
1274 if (sysctl(mib, 7, NULL((void *)0), &len, NULL((void *)0), 0) == -1) {
1275 log_warn("%s: failed to fetch arp table %u size", __func__,
1276 kt->rtableid);
1277 return (-1);
1278 }
1279 /* Empty table? */
1280 if (len == 0)
1281 return (0);
1282 if ((buf = malloc(len)) == NULL((void *)0)) {
1283 log_warn("%s: malloc", __func__);
1284 return (-1);
1285 }
1286 if (sysctl(mib, 7, buf, &len, NULL((void *)0), 0) == -1) {
1287 log_warn("%s: failed to fetch arp table %u", __func__,
1288 kt->rtableid);
1289 free(buf);
1290 return (-1);
1291 }
1292
1293 rv = rtmsg_process(buf, len);
1294 free(buf);
1295
1296 return (rv);
1297}
1298
1299/* ARGSUSED */
1300void
1301dispatch_rtmsg(int fd, short event, void *arg)
1302{
1303 char buf[RT_BUF_SIZE16384];
1304 ssize_t n;
1305
1306 if ((n = read(fd, &buf, sizeof(buf))) == -1) {
1307 log_warn("%s: read error", __func__);
1308 return;
1309 }
1310
1311 if (n == 0) {
1312 log_warnx("%s: routing socket closed", __func__);
1313 return;
1314 }
1315
1316 rtmsg_process(buf, n);
1317}
1318
1319int
1320rtmsg_process(char *buf, int len)
1321{
1322 struct ktable *kt;
1323 struct rt_msghdr *rtm;
1324 struct if_msghdr ifm;
1325 struct ifa_msghdr *ifam;
1326 struct sockaddr *sa, *rti_info[RTAX_MAX15];
1327 int offset;
1328 char *next;
1329
1330 for (offset = 0; offset < len; offset += rtm->rtm_msglen) {
1331 next = buf + offset;
1332 rtm = (struct rt_msghdr *)next;
1333 if (rtm->rtm_version != RTM_VERSION5)
1334 continue;
1335
1336 sa = (struct sockaddr *)(next + rtm->rtm_hdrlen);
1337 get_rtaddrs(rtm->rtm_addrs, sa, rti_info);
1338
1339 switch (rtm->rtm_type) {
1340 case RTM_ADD0x1:
1341 case RTM_GET0x4:
1342 case RTM_CHANGE0x3:
1343 case RTM_DELETE0x2:
1344 case RTM_RESOLVE0xb:
1345 if (rtm->rtm_errno) /* failed attempts */
1346 continue;
1347
1348 if ((kt = ktable_get(rtm->rtm_tableid)) == NULL((void *)0))
1349 continue;
1350
1351 if (dispatch_rtmsg_addr(kt, rtm, rti_info) == -1)
1352 return (-1);
1353 break;
1354 case RTM_IFINFO0xe:
1355 memcpy(&ifm, next, sizeof(ifm));
1356 if_change(ifm.ifm_index, ifm.ifm_flags, &ifm.ifm_data,
1357 (struct sockaddr_dl *)rti_info[RTAX_IFP4]);
1358 break;
1359 case RTM_DELADDR0xd:
1360 ifam = (struct ifa_msghdr *)rtm;
1361 if ((ifam->ifam_addrs & (RTA_NETMASK0x4 | RTA_IFA0x20 |
1362 RTA_BRD0x80)) == 0)
1363 break;
1364
1365 if_deladdr(ifam->ifam_index, rti_info[RTAX_IFA5],
1366 rti_info[RTAX_NETMASK2], rti_info[RTAX_BRD7]);
1367 break;
1368 case RTM_NEWADDR0xc:
1369 ifam = (struct ifa_msghdr *)rtm;
1370 if ((ifam->ifam_addrs & (RTA_NETMASK0x4 | RTA_IFA0x20 |
1371 RTA_BRD0x80)) == 0)
1372 break;
1373
1374 if_newaddr(ifam->ifam_index, rti_info[RTAX_IFA5],
1375 rti_info[RTAX_NETMASK2], rti_info[RTAX_BRD7]);
1376 break;
1377 case RTM_IFANNOUNCE0xf:
1378 if_announce(next);
1379 break;
1380 case RTM_DESYNC0x10:
1381 kr_shutdown();
1382 if (fetchifs(0) == -1)
1383 fatalx("rtmsg_process: fetchifs");
1384 ktable_init();
1385 break;
1386 default:
1387 /* ignore for now */
1388 break;
1389 }
1390 }
1391
1392 return (offset);
1393}
1394
1395int
1396dispatch_rtmsg_addr(struct ktable *kt, struct rt_msghdr *rtm,
1397 struct sockaddr *rti_info[RTAX_MAX15])
1398{
1399 struct sockaddr *sa, *psa;
1400 struct sockaddr_in *sa_in, *psa_in = NULL((void *)0);
1401 struct sockaddr_in6 *sa_in6, *psa_in6 = NULL((void *)0);
1402 struct sockaddr_dl *sa_dl;
1403 struct kroute_node *kr;
1404 struct kroute6_node *kr6;
1405 struct kif_arp *ka;
1406 int flags, mpath = 0;
1407 u_int16_t ifindex;
1408 u_int8_t prefixlen;
1409 u_int8_t prio;
1410
1411 flags = 0;
1412 ifindex = 0;
1413 prefixlen = 0;
1414
1415 if ((psa = rti_info[RTAX_DST0]) == NULL((void *)0))
1416 return (-1);
1417
1418 if (rtm->rtm_flags & RTF_STATIC0x800)
1419 flags |= F_STATIC0x0002;
1420 if (rtm->rtm_flags & RTF_BLACKHOLE0x1000)
1421 flags |= F_BLACKHOLE0x0004;
1422 if (rtm->rtm_flags & RTF_REJECT0x8)
1423 flags |= F_REJECT0x0008;
1424 if (rtm->rtm_flags & RTF_DYNAMIC0x10)
1425 flags |= F_DYNAMIC0x0010;
1426#ifdef RTF_MPATH0x40000
1427 if (rtm->rtm_flags & RTF_MPATH0x40000)
1428 mpath = 1;
1429#endif
1430
1431 prio = rtm->rtm_priority;
1432 switch (psa->sa_family) {
1433 case AF_INET2:
1434 psa_in = (struct sockaddr_in *)psa;
1435 sa_in = (struct sockaddr_in *)rti_info[RTAX_NETMASK2];
1436 if (sa_in != NULL((void *)0)) {
1437 if (sa_in->sin_len != 0)
1438 prefixlen = mask2prefixlen(
1439 sa_in->sin_addr.s_addr);
1440 } else if (rtm->rtm_flags & RTF_HOST0x4)
1441 prefixlen = 32;
1442 else
1443 prefixlen =
1444 prefixlen_classful(psa_in->sin_addr.s_addr);
1445 break;
1446 case AF_INET624:
1447 psa_in6 = (struct sockaddr_in6 *)psa;
1448 sa_in6 = (struct sockaddr_in6 *)rti_info[RTAX_NETMASK2];
1449 if (sa_in6 != NULL((void *)0)) {
1450 if (sa_in6->sin6_len != 0)
1451 prefixlen = mask2prefixlen6(sa_in6);
1452 } else if (rtm->rtm_flags & RTF_HOST0x4)
1453 prefixlen = 128;
1454 else
1455 fatalx("in6 net addr without netmask");
1456 break;
1457 default:
1458 return (0);
1459 }
1460
1461 if ((sa = rti_info[RTAX_GATEWAY1]) != NULL((void *)0))
1462 switch (sa->sa_family) {
1463 case AF_INET2:
1464 case AF_INET624:
1465 if (rtm->rtm_flags & RTF_CONNECTED0x800000) {
1466 flags |= F_CONNECTED0x0001;
1467 ifindex = rtm->rtm_index;
1468 }
1469 mpath = 0; /* link local stuff can't be mpath */
1470 break;
1471 case AF_LINK18:
1472 /*
1473 * Traditional BSD connected routes have
1474 * a gateway of type AF_LINK.
1475 */
1476 flags |= F_CONNECTED0x0001;
1477 ifindex = rtm->rtm_index;
1478 mpath = 0; /* link local stuff can't be mpath */
1479 break;
1480 }
1481
1482 if (rtm->rtm_type == RTM_DELETE0x2) {
1483 if (sa != NULL((void *)0) && sa->sa_family == AF_LINK18 &&
1484 (rtm->rtm_flags & RTF_HOST0x4) &&
1485 psa->sa_family == AF_INET2) {
1486 if ((ka = karp_find(psa, ifindex)) == NULL((void *)0))
1487 return (0);
1488 if (karp_remove(NULL((void *)0), ka) == -1)
1489 return (-1);
1490 return (0);
1491 } else if (sa == NULL((void *)0) && (rtm->rtm_flags & RTF_HOST0x4) &&
1492 psa->sa_family == AF_INET2) {
1493 if ((ka = karp_find(psa, ifindex)) != NULL((void *)0))
1494 karp_remove(NULL((void *)0), ka);
1495 /* Continue to the route section below */
1496 }
1497 switch (psa->sa_family) {
1498 case AF_INET2:
1499 sa_in = (struct sockaddr_in *)sa;
1500 if ((kr = kroute_find(kt, psa_in->sin_addr.s_addr,
1501 prefixlen, prio)) == NULL((void *)0))
1502 return (0);
1503
1504 if (mpath)
1505 /* get the correct route */
1506 if ((kr = kroute_matchgw(kr, sa_in)) == NULL((void *)0)) {
1507 log_warnx("%s[delete]: "
1508 "mpath route not found", __func__);
1509 return (0);
1510 }
1511
1512 if (kroute_remove(kt, kr) == -1)
1513 return (-1);
1514 break;
1515 case AF_INET624:
1516 sa_in6 = (struct sockaddr_in6 *)sa;
1517 if ((kr6 = kroute6_find(kt, &psa_in6->sin6_addr,
1518 prefixlen, prio)) == NULL((void *)0))
1519 return (0);
1520
1521 if (mpath)
1522 /* get the correct route */
1523 if ((kr6 = kroute6_matchgw(kr6, sa_in6)) ==
1524 NULL((void *)0)) {
1525 log_warnx("%s[delete]: "
1526 "IPv6 mpath route not found",
1527 __func__);
1528 return (0);
1529 }
1530
1531 if (kroute6_remove(kt, kr6) == -1)
1532 return (-1);
1533 break;
1534 }
1535 return (0);
1536 }
1537
1538 if (sa == NULL((void *)0) && !(flags & F_CONNECTED0x0001))
1539 return (0);
1540
1541 /* Add or update an ARP entry */
1542 if ((rtm->rtm_flags & RTF_LLINFO0x400) && (rtm->rtm_flags & RTF_HOST0x4) &&
1543 sa != NULL((void *)0) && sa->sa_family == AF_LINK18 &&
1544 psa->sa_family == AF_INET2) {
1545 sa_dl = (struct sockaddr_dl *)sa;
1546 /* ignore incomplete entries */
1547 if (!sa_dl->sdl_alen)
1548 return (0);
1549 /* ignore entries that do not specify an interface */
1550 if (ifindex == 0)
1551 return (0);
1552 if ((ka = karp_find(psa, ifindex)) != NULL((void *)0)) {
1553 memcpy(&ka->target.sdl, sa_dl, sa_dl->sdl_len);
1554 if (rtm->rtm_flags & RTF_PERMANENT_ARP0x2000)
1555 flags |= F_STATIC0x0002;
1556 ka->flags = flags;
1557 } else {
1558 if ((ka = calloc(1, sizeof(struct kif_arp))) == NULL((void *)0)) {
1559 log_warn("%s: calloc", __func__);
1560 return (-1);
1561 }
1562 memcpy(&ka->addr.sa, psa, psa->sa_len);
1563 memcpy(&ka->target.sdl, sa_dl, sa_dl->sdl_len);
1564 if (rtm->rtm_flags & RTF_PERMANENT_ARP0x2000)
1565 flags |= F_STATIC0x0002;
1566 ka->flags = flags;
1567 ka->if_index = ifindex;
1568 if (karp_insert(NULL((void *)0), ka)) {
1569 free(ka);
1570 log_warnx("%s: failed to insert", __func__);
1571 return (-1);
1572 }
1573 }
1574 return (0);
1575 }
1576
1577 switch (psa->sa_family) {
1578 case AF_INET2:
1579 sa_in = (struct sockaddr_in *)sa;
1580 if ((kr = kroute_find(kt, psa_in->sin_addr.s_addr, prefixlen,
1581 prio)) != NULL((void *)0)) {
1582 /* get the correct route */
1583 if (mpath && rtm->rtm_type == RTM_CHANGE0x3 &&
1584 (kr = kroute_matchgw(kr, sa_in)) == NULL((void *)0)) {
1585 log_warnx("%s[change]: "
1586 "mpath route not found", __func__);
1587 return (-1);
1588 } else if (mpath && rtm->rtm_type == RTM_ADD0x1)
1589 goto add4;
1590
1591 if (sa_in != NULL((void *)0))
1592 kr->r.nexthop.s_addr =
1593 sa_in->sin_addr.s_addr;
1594 else
1595 kr->r.nexthop.s_addr = 0;
1596 kr->r.flags = flags;
1597 kr->r.if_index = ifindex;
1598 kr->r.ticks = smi_getticks();
1599 } else {
1600add4:
1601 if ((kr = calloc(1,
1602 sizeof(struct kroute_node))) == NULL((void *)0)) {
1603 log_warn("%s: calloc", __func__);
1604 return (-1);
1605 }
1606 kr->r.prefix.s_addr = psa_in->sin_addr.s_addr;
1607 kr->r.prefixlen = prefixlen;
1608 if (sa_in != NULL((void *)0))
1609 kr->r.nexthop.s_addr = sa_in->sin_addr.s_addr;
1610 else
1611 kr->r.nexthop.s_addr = 0;
1612 kr->r.flags = flags;
1613 kr->r.if_index = ifindex;
1614 kr->r.ticks = smi_getticks();
1615 kr->r.priority = prio;
1616
1617 kroute_insert(kt, kr);
1618 }
1619 break;
1620 case AF_INET624:
1621 sa_in6 = (struct sockaddr_in6 *)sa;
1622 if ((kr6 = kroute6_find(kt, &psa_in6->sin6_addr, prefixlen,
1623 prio)) != NULL((void *)0)) {
1624 /* get the correct route */
1625 if (mpath && rtm->rtm_type == RTM_CHANGE0x3 &&
1626 (kr6 = kroute6_matchgw(kr6, sa_in6)) ==
1627 NULL((void *)0)) {
1628 log_warnx("%s[change]: "
1629 "IPv6 mpath route not found", __func__);
1630 return (-1);
1631 } else if (mpath && rtm->rtm_type == RTM_ADD0x1)
1632 goto add6;
1633
1634 if (sa_in6 != NULL((void *)0))
1635 memcpy(&kr6->r.nexthop,
1636 &sa_in6->sin6_addr,
1637 sizeof(struct in6_addr));
1638 else
1639 memcpy(&kr6->r.nexthop,
1640 &in6addr_any,
1641 sizeof(struct in6_addr));
1642
1643 kr6->r.flags = flags;
1644 kr6->r.if_index = ifindex;
1645 kr6->r.ticks = smi_getticks();
1646 } else {
1647add6:
1648 if ((kr6 = calloc(1,
1649 sizeof(struct kroute6_node))) == NULL((void *)0)) {
1650 log_warn("%s: calloc", __func__);
1651 return (-1);
1652 }
1653 memcpy(&kr6->r.prefix, &psa_in6->sin6_addr,
1654 sizeof(struct in6_addr));
1655 kr6->r.prefixlen = prefixlen;
1656 if (sa_in6 != NULL((void *)0))
1657 memcpy(&kr6->r.nexthop, &sa_in6->sin6_addr,
1658 sizeof(struct in6_addr));
1659 else
1660 memcpy(&kr6->r.nexthop, &in6addr_any,
1661 sizeof(struct in6_addr));
1662 kr6->r.flags = flags;
1663 kr6->r.if_index = ifindex;
1664 kr6->r.ticks = smi_getticks();
1665 kr6->r.priority = prio;
1666
1667 kroute6_insert(kt, kr6);
1668 }
1669 break;
1670 }
1671
1672 return (0);
1673}
1674
1675struct kroute *
1676kroute_first(void)
1677{
1678 struct kroute_node *kn;
1679 struct ktable *kt;
1680
1681 if ((kt = ktable_get(0)) == NULL((void *)0))
1682 return (NULL((void *)0));
1683 kn = RB_MIN(kroute_tree, &kt->krt)kroute_tree_RB_MINMAX(&kt->krt, -1);
1684 return (&kn->r);
1685}
1686
1687struct kroute *
1688kroute_getaddr(in_addr_t prefix, u_int8_t prefixlen, u_int8_t prio, int next)
1689{
1690 struct kroute_node *kn;
1691 struct ktable *kt;
1692
1693 if ((kt = ktable_get(0)) == NULL((void *)0))
1694 return (NULL((void *)0));
1695 kn = kroute_find(kt, prefix, prefixlen, prio);
1696 if (kn != NULL((void *)0) && next)
1697 kn = RB_NEXT(kroute_tree, &kt->krt, kn)kroute_tree_RB_NEXT(kn);
1698 if (kn != NULL((void *)0))
1699 return (&kn->r);
1700 else
1701 return (NULL((void *)0));
1702}