File: | src/libexec/snmpd/snmpd_metrics/kroute.c |
Warning: | line 1165, column 3 Null pointer passed as 1st argument to string copy function |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | /* $OpenBSD: kroute.c,v 1.3 2023/03/08 04:43:06 guenther 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 | ||||
47 | struct ktable **krt; | |||
48 | u_int krt_size; | |||
49 | ||||
50 | struct { | |||
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 | ||||
59 | struct 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 | ||||
65 | struct 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 | ||||
71 | struct 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 | ||||
78 | int kroute_compare(struct kroute_node *, struct kroute_node *); | |||
79 | int kroute6_compare(struct kroute6_node *, struct kroute6_node *); | |||
80 | int kif_compare(struct kif_node *, struct kif_node *); | |||
81 | ||||
82 | void ktable_init(void); | |||
83 | int ktable_new(u_int, u_int); | |||
84 | void ktable_free(u_int); | |||
85 | int ktable_exists(u_int, u_int *); | |||
86 | struct ktable *ktable_get(u_int); | |||
87 | int ktable_update(u_int); | |||
88 | ||||
89 | struct kroute_node *kroute_find(struct ktable *, in_addr_t, u_int8_t, | |||
90 | u_int8_t); | |||
91 | struct kroute_node *kroute_matchgw(struct kroute_node *, | |||
92 | struct sockaddr_in *); | |||
93 | int kroute_insert(struct ktable *, struct kroute_node *); | |||
94 | int kroute_remove(struct ktable *, struct kroute_node *); | |||
95 | void kroute_clear(struct ktable *); | |||
96 | ||||
97 | struct kroute6_node *kroute6_find(struct ktable *, const struct in6_addr *, | |||
98 | u_int8_t, u_int8_t); | |||
99 | struct kroute6_node *kroute6_matchgw(struct kroute6_node *, | |||
100 | struct sockaddr_in6 *); | |||
101 | int kroute6_insert(struct ktable *, struct kroute6_node *); | |||
102 | int kroute6_remove(struct ktable *, struct kroute6_node *); | |||
103 | void kroute6_clear(struct ktable *); | |||
104 | ||||
105 | struct kif_arp *karp_find(struct sockaddr *, u_short); | |||
106 | int karp_insert(struct kif_node *, struct kif_arp *); | |||
107 | int karp_remove(struct kif_node *, struct kif_arp *); | |||
108 | ||||
109 | struct kif_node *kif_find(u_short); | |||
110 | struct kif_node *kif_insert(u_short); | |||
111 | int kif_remove(struct kif_node *); | |||
112 | void kif_clear(void); | |||
113 | struct kif *kif_update(u_short, int, struct if_data *, | |||
114 | struct sockaddr_dl *); | |||
115 | ||||
116 | int ka_compare(struct kif_addr *, struct kif_addr *); | |||
117 | void ka_insert(u_short, struct kif_addr *); | |||
118 | struct kif_addr *ka_find(struct sockaddr *); | |||
119 | int ka_remove(struct kif_addr *); | |||
120 | ||||
121 | u_int8_t prefixlen_classful(in_addr_t); | |||
122 | u_int8_t mask2prefixlen(in_addr_t); | |||
123 | in_addr_t prefixlen2mask(u_int8_t); | |||
124 | u_int8_t mask2prefixlen6(struct sockaddr_in6 *); | |||
125 | struct in6_addr *prefixlen2mask6(u_int8_t); | |||
126 | void get_rtaddrs(int, struct sockaddr *, struct sockaddr **); | |||
127 | void if_change(u_short, int, struct if_data *, struct sockaddr_dl *); | |||
128 | void if_newaddr(u_short, struct sockaddr *, struct sockaddr *, | |||
129 | struct sockaddr *); | |||
130 | void if_deladdr(u_short, struct sockaddr *, struct sockaddr *, | |||
131 | struct sockaddr *); | |||
132 | void if_announce(void *); | |||
133 | ||||
134 | int fetchtable(struct ktable *); | |||
135 | int fetchifs(u_short); | |||
136 | int fetcharp(struct ktable *); | |||
137 | void dispatch_rtmsg(int, short, void *); | |||
138 | int rtmsg_process(char *, int); | |||
139 | int dispatch_rtmsg_addr(struct ktable *, struct rt_msghdr *, | |||
140 | struct sockaddr *[RTAX_MAX15]); | |||
141 | ||||
142 | RB_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); | |||
143 | RB_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 | ||||
145 | RB_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); | |||
146 | RB_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 | ||||
148 | RB_HEAD(kif_tree, kif_node)struct kif_tree { struct kif_node *rbh_root; } kit; | |||
149 | RB_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); | |||
150 | RB_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 | ||||
152 | RB_HEAD(ka_tree, kif_addr)struct ka_tree { struct kif_addr *rbh_root; } kat; | |||
153 | RB_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 ); | |||
154 | RB_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 | ||||
156 | void | |||
157 | kr_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 | ||||
209 | void | |||
210 | ktable_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 | ||||
219 | int | |||
220 | ktable_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 | ||||
267 | void | |||
268 | ktable_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 | ||||
283 | struct ktable * | |||
284 | ktable_get(u_int rtableid) | |||
285 | { | |||
286 | if (rtableid >= krt_size) | |||
287 | return (NULL((void *)0)); | |||
288 | return (krt[rtableid]); | |||
289 | } | |||
290 | ||||
291 | int | |||
292 | ktable_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 | ||||
314 | int | |||
315 | ktable_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 | ||||
342 | void | |||
343 | kr_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 | ||||
352 | u_int | |||
353 | kr_ifnumber(void) | |||
354 | { | |||
355 | return (kr_state.ks_nkif); | |||
356 | } | |||
357 | ||||
358 | u_long | |||
359 | kr_iflastchange(void) | |||
360 | { | |||
361 | return (kr_state.ks_iflastchange); | |||
362 | } | |||
363 | ||||
364 | int | |||
365 | kr_updateif(u_int if_index) | |||
366 | { | |||
367 | return (fetchifs(if_index)); | |||
368 | } | |||
369 | ||||
370 | u_long | |||
371 | kr_routenumber(void) | |||
372 | { | |||
373 | return (kr_state.ks_nroutes); | |||
374 | } | |||
375 | ||||
376 | /* rb-tree compare */ | |||
377 | int | |||
378 | kroute_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 | ||||
399 | int | |||
400 | kroute6_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 | ||||
426 | int | |||
427 | kif_compare(struct kif_node *a, struct kif_node *b) | |||
428 | { | |||
429 | return (a->k.if_index - b->k.if_index); | |||
430 | } | |||
431 | ||||
432 | int | |||
433 | ka_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 */ | |||
443 | struct kroute_node * | |||
444 | kroute_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 | ||||
468 | struct kroute_node * | |||
469 | kroute_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 | ||||
488 | int | |||
489 | kroute_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 | ||||
505 | int | |||
506 | kroute_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 | ||||
548 | void | |||
549 | kroute_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 | ||||
557 | struct kroute6_node * | |||
558 | kroute6_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 | ||||
582 | struct kroute6_node * | |||
583 | kroute6_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 | ||||
602 | int | |||
603 | kroute6_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 | ||||
619 | int | |||
620 | kroute6_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 | ||||
664 | void | |||
665 | kroute6_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 | ||||
673 | static inline int | |||
674 | karp_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)) > | |||
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 | ||||
686 | static inline struct kif_arp * | |||
687 | karp_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)) { | |||
692 | switch (karp_compare(ka, pivot)) { | |||
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 | ||||
703 | struct kif_arp * | |||
704 | karp_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) { | |||
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)) { | |||
719 | if ((ka = karp_search(kn, &s)) != NULL((void *)0)) | |||
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 | ||||
730 | int | |||
731 | karp_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 | ||||
754 | int | |||
755 | karp_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 | ||||
766 | struct kif_arp * | |||
767 | karp_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 | ||||
776 | struct kif_arp * | |||
777 | karp_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)) | |||
782 | return (NULL((void *)0)); | |||
783 | return (next ? TAILQ_NEXT(ka, entry)((ka)->entry.tqe_next) : ka); | |||
784 | } | |||
785 | ||||
786 | struct kif_node * | |||
787 | kif_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 | ||||
800 | struct kif * | |||
801 | kr_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 | ||||
812 | struct kif * | |||
813 | kr_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 | ||||
827 | struct kif_node * | |||
828 | kif_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 | ||||
848 | int | |||
849 | kif_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 | ||||
874 | void | |||
875 | kif_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 | ||||
885 | struct kif * | |||
886 | kif_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 | ||||
924 | void | |||
925 | ka_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 | ||||
934 | struct kif_addr * | |||
935 | ka_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 | ||||
946 | int | |||
947 | ka_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 | ||||
954 | struct kif_addr * | |||
955 | kr_getaddr(struct sockaddr *sa) | |||
956 | { | |||
957 | return (ka_find(sa)); | |||
958 | } | |||
959 | ||||
960 | struct kif_addr * | |||
961 | kr_getnextaddr(struct sockaddr *sa) | |||
962 | { | |||
963 | struct kif_addr ka; | |||
964 | ||||
965 | bzero(&ka.addr, sizeof(ka.addr)); | |||
966 | bcopy(sa, &ka.addr.sa, sa->sa_len); | |||
967 | return RB_NFIND(ka_tree, &kat, &ka)ka_tree_RB_NFIND(&kat, &ka); | |||
968 | } | |||
969 | ||||
970 | /* misc */ | |||
971 | u_int8_t | |||
972 | prefixlen_classful(in_addr_t ina) | |||
973 | { | |||
974 | /* it hurt to write this. */ | |||
975 | ||||
976 | if (ina >= 0xf0000000U) /* class E */ | |||
977 | return (32); | |||
978 | else if (ina >= 0xe0000000U) /* class D */ | |||
979 | return (4); | |||
980 | else if (ina >= 0xc0000000U) /* class C */ | |||
981 | return (24); | |||
982 | else if (ina >= 0x80000000U) /* class B */ | |||
983 | return (16); | |||
984 | else /* class A */ | |||
985 | return (8); | |||
986 | } | |||
987 | ||||
988 | u_int8_t | |||
989 | mask2prefixlen(in_addr_t ina) | |||
990 | { | |||
991 | if (ina == 0) | |||
992 | return (0); | |||
993 | else | |||
994 | 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)))); | |||
995 | } | |||
996 | ||||
997 | in_addr_t | |||
998 | prefixlen2mask(u_int8_t prefixlen) | |||
999 | { | |||
1000 | if (prefixlen == 0) | |||
1001 | return (0); | |||
1002 | ||||
1003 | 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)))); | |||
1004 | } | |||
1005 | ||||
1006 | u_int8_t | |||
1007 | mask2prefixlen6(struct sockaddr_in6 *sa_in6) | |||
1008 | { | |||
1009 | unsigned int l = 0; | |||
1010 | u_int8_t *ap, *ep; | |||
1011 | ||||
1012 | /* | |||
1013 | * sin6_len is the size of the sockaddr so subtract the offset of | |||
1014 | * the possibly truncated sin6_addr struct. | |||
1015 | */ | |||
1016 | ap = (u_int8_t *)&sa_in6->sin6_addr; | |||
1017 | ep = (u_int8_t *)sa_in6 + sa_in6->sin6_len; | |||
1018 | for (; ap < ep; ap++) { | |||
1019 | /* this "beauty" is adopted from sbin/route/show.c ... */ | |||
1020 | switch (*ap) { | |||
1021 | case 0xff: | |||
1022 | l += 8; | |||
1023 | break; | |||
1024 | case 0xfe: | |||
1025 | l += 7; | |||
1026 | goto done; | |||
1027 | case 0xfc: | |||
1028 | l += 6; | |||
1029 | goto done; | |||
1030 | case 0xf8: | |||
1031 | l += 5; | |||
1032 | goto done; | |||
1033 | case 0xf0: | |||
1034 | l += 4; | |||
1035 | goto done; | |||
1036 | case 0xe0: | |||
1037 | l += 3; | |||
1038 | goto done; | |||
1039 | case 0xc0: | |||
1040 | l += 2; | |||
1041 | goto done; | |||
1042 | case 0x80: | |||
1043 | l += 1; | |||
1044 | goto done; | |||
1045 | case 0x00: | |||
1046 | goto done; | |||
1047 | default: | |||
1048 | fatalx("non contiguous inet6 netmask"); | |||
1049 | } | |||
1050 | } | |||
1051 | ||||
1052 | done: | |||
1053 | if (l > sizeof(struct in6_addr) * 8) | |||
1054 | fatalx("inet6 prefixlen out of bound"); | |||
1055 | return (l); | |||
1056 | } | |||
1057 | ||||
1058 | struct in6_addr * | |||
1059 | prefixlen2mask6(u_int8_t prefixlen) | |||
1060 | { | |||
1061 | static struct in6_addr mask; | |||
1062 | int i; | |||
1063 | ||||
1064 | bzero(&mask, sizeof(mask)); | |||
1065 | for (i = 0; i < prefixlen / 8; i++) | |||
1066 | mask.s6_addr__u6_addr.__u6_addr8[i] = 0xff; | |||
1067 | i = prefixlen % 8; | |||
1068 | if (i) | |||
1069 | mask.s6_addr__u6_addr.__u6_addr8[prefixlen / 8] = 0xff00 >> i; | |||
1070 | ||||
1071 | return (&mask); | |||
1072 | } | |||
1073 | ||||
1074 | #define ROUNDUP(a)((a) > 0 ? (1 + (((a) - 1) | (sizeof(long) - 1))) : sizeof (long)) \ | |||
1075 | ((a) > 0 ? (1 + (((a) - 1) | (sizeof(long) - 1))) : sizeof(long)) | |||
1076 | ||||
1077 | void | |||
1078 | get_rtaddrs(int addrs, struct sockaddr *sa, struct sockaddr **rti_info) | |||
1079 | { | |||
1080 | int i; | |||
1081 | ||||
1082 | for (i = 0; i < RTAX_MAX15; i++) { | |||
1083 | if (addrs & (1 << i)) { | |||
1084 | rti_info[i] = sa; | |||
1085 | sa = (struct sockaddr *)((char *)(sa) + | |||
1086 | ROUNDUP(sa->sa_len)((sa->sa_len) > 0 ? (1 + (((sa->sa_len) - 1) | (sizeof (long) - 1))) : sizeof(long))); | |||
1087 | } else | |||
1088 | rti_info[i] = NULL((void *)0); | |||
1089 | ||||
1090 | } | |||
1091 | } | |||
1092 | ||||
1093 | void | |||
1094 | if_change(u_short if_index, int flags, struct if_data *ifd, | |||
1095 | struct sockaddr_dl *sdl) | |||
1096 | { | |||
1097 | if (kif_update(if_index, flags, ifd, sdl) == NULL((void *)0)) | |||
1098 | log_warn("%s: interface %u update failed", __func__, if_index); | |||
1099 | } | |||
1100 | ||||
1101 | void | |||
1102 | if_newaddr(u_short if_index, struct sockaddr *ifa, struct sockaddr *mask, | |||
1103 | struct sockaddr *brd) | |||
1104 | { | |||
1105 | struct kif_node *kif; | |||
1106 | struct kif_addr *ka; | |||
1107 | ||||
1108 | if (ifa == NULL((void *)0)) | |||
1109 | return; | |||
1110 | if ((kif = kif_find(if_index)) == NULL((void *)0)) { | |||
1111 | log_warnx("%s: corresponding if %u not found", __func__, | |||
1112 | if_index); | |||
1113 | return; | |||
1114 | } | |||
1115 | if ((ka = ka_find(ifa)) == NULL((void *)0)) { | |||
1116 | if ((ka = calloc(1, sizeof(struct kif_addr))) == NULL((void *)0)) | |||
1117 | fatal("if_newaddr"); | |||
1118 | bcopy(ifa, &ka->addr.sa, ifa->sa_len); | |||
1119 | 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); | |||
1120 | ka_insert(if_index, ka); | |||
1121 | } | |||
1122 | ||||
1123 | if (mask) | |||
1124 | bcopy(mask, &ka->mask.sa, mask->sa_len); | |||
1125 | else | |||
1126 | bzero(&ka->mask, sizeof(ka->mask)); | |||
1127 | if (brd) | |||
1128 | bcopy(brd, &ka->dstbrd.sa, brd->sa_len); | |||
1129 | else | |||
1130 | bzero(&ka->dstbrd, sizeof(ka->dstbrd)); | |||
1131 | } | |||
1132 | ||||
1133 | void | |||
1134 | if_deladdr(u_short if_index, struct sockaddr *ifa, struct sockaddr *mask, | |||
1135 | struct sockaddr *brd) | |||
1136 | { | |||
1137 | struct kif_node *kif; | |||
1138 | struct kif_addr *ka; | |||
1139 | ||||
1140 | if (ifa == NULL((void *)0)) | |||
1141 | return; | |||
1142 | if ((kif = kif_find(if_index)) == NULL((void *)0)) { | |||
1143 | log_warnx("%s: corresponding if %u not found", __func__, | |||
1144 | if_index); | |||
1145 | return; | |||
1146 | } | |||
1147 | if ((ka = ka_find(ifa)) == NULL((void *)0)) | |||
1148 | return; | |||
1149 | ||||
1150 | 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); | |||
1151 | ka_remove(ka); | |||
1152 | } | |||
1153 | ||||
1154 | void | |||
1155 | if_announce(void *msg) | |||
1156 | { | |||
1157 | struct if_announcemsghdr *ifan; | |||
1158 | struct kif_node *kif; | |||
1159 | ||||
1160 | ifan = msg; | |||
1161 | ||||
1162 | switch (ifan->ifan_what) { | |||
1163 | case IFAN_ARRIVAL0: | |||
1164 | kif = kif_insert(ifan->ifan_index); | |||
1165 | strlcpy(kif->k.if_name, ifan->ifan_name, | |||
| ||||
1166 | sizeof(kif->k.if_name)); | |||
1167 | break; | |||
1168 | case IFAN_DEPARTURE1: | |||
1169 | kif = kif_find(ifan->ifan_index); | |||
1170 | kif_remove(kif); | |||
1171 | break; | |||
1172 | } | |||
1173 | } | |||
1174 | ||||
1175 | int | |||
1176 | fetchtable(struct ktable *kt) | |||
1177 | { | |||
1178 | int mib[7]; | |||
1179 | size_t len; | |||
1180 | char *buf; | |||
1181 | int rv; | |||
1182 | ||||
1183 | mib[0] = CTL_NET4; | |||
1184 | mib[1] = PF_ROUTE17; | |||
1185 | mib[2] = 0; | |||
1186 | mib[3] = AF_INET2; | |||
1187 | mib[4] = NET_RT_DUMP1; | |||
1188 | mib[5] = 0; | |||
1189 | mib[6] = kt->rtableid; | |||
1190 | ||||
1191 | if (sysctl(mib, 7, NULL((void *)0), &len, NULL((void *)0), 0) == -1) { | |||
1192 | if (kt->rtableid != 0 && errno(*__errno()) == EINVAL22) | |||
1193 | /* table nonexistent */ | |||
1194 | return (0); | |||
1195 | log_warn("%s: failed to fetch routing table %u size", __func__, | |||
1196 | kt->rtableid); | |||
1197 | return (-1); | |||
1198 | } | |||
1199 | if (len == 0) | |||
1200 | return (0); | |||
1201 | if ((buf = malloc(len)) == NULL((void *)0)) { | |||
1202 | log_warn("%s: malloc", __func__); | |||
1203 | return (-1); | |||
1204 | } | |||
1205 | if (sysctl(mib, 7, buf, &len, NULL((void *)0), 0) == -1) { | |||
1206 | log_warn("%s: failed to fetch routing table %u", __func__, | |||
1207 | kt->rtableid); | |||
1208 | free(buf); | |||
1209 | return (-1); | |||
1210 | } | |||
1211 | ||||
1212 | rv = rtmsg_process(buf, len); | |||
1213 | free(buf); | |||
1214 | ||||
1215 | return (rv); | |||
1216 | } | |||
1217 | ||||
1218 | int | |||
1219 | fetchifs(u_short if_index) | |||
1220 | { | |||
1221 | size_t len; | |||
1222 | int mib[6]; | |||
1223 | char *buf; | |||
1224 | int rv; | |||
1225 | ||||
1226 | mib[0] = CTL_NET4; | |||
1227 | mib[1] = PF_ROUTE17; | |||
1228 | mib[2] = 0; | |||
1229 | mib[3] = 0; /* wildcard address family */ | |||
1230 | mib[4] = NET_RT_IFLIST3; | |||
1231 | mib[5] = if_index; | |||
1232 | ||||
1233 | if (sysctl(mib, 6, NULL((void *)0), &len, NULL((void *)0), 0) == -1) { | |||
1234 | log_warn("%s: failed to fetch address table size for %u", | |||
1235 | __func__, if_index); | |||
1236 | return (-1); | |||
1237 | } | |||
1238 | if ((buf = malloc(len)) == NULL((void *)0)) { | |||
1239 | log_warn("%s: malloc", __func__); | |||
1240 | return (-1); | |||
1241 | } | |||
1242 | if (sysctl(mib, 6, buf, &len, NULL((void *)0), 0) == -1) { | |||
1243 | log_warn("%s: failed to fetch address table for %u", | |||
1244 | __func__, if_index); | |||
1245 | free(buf); | |||
1246 | return (-1); | |||
1247 | } | |||
1248 | ||||
1249 | rv = rtmsg_process(buf, len); | |||
1250 | free(buf); | |||
1251 | ||||
1252 | return (rv); | |||
1253 | } | |||
1254 | ||||
1255 | int | |||
1256 | fetcharp(struct ktable *kt) | |||
1257 | { | |||
1258 | size_t len; | |||
1259 | int mib[7]; | |||
1260 | char *buf; | |||
1261 | int rv; | |||
1262 | ||||
1263 | mib[0] = CTL_NET4; | |||
1264 | mib[1] = PF_ROUTE17; | |||
1265 | mib[2] = 0; | |||
1266 | mib[3] = AF_INET2; | |||
1267 | mib[4] = NET_RT_FLAGS2; | |||
1268 | mib[5] = RTF_LLINFO0x400; | |||
1269 | mib[6] = kt->rtableid; | |||
1270 | ||||
1271 | if (sysctl(mib, 7, NULL((void *)0), &len, NULL((void *)0), 0) == -1) { | |||
1272 | log_warn("%s: failed to fetch arp table %u size", __func__, | |||
1273 | kt->rtableid); | |||
1274 | return (-1); | |||
1275 | } | |||
1276 | /* Empty table? */ | |||
1277 | if (len == 0) | |||
1278 | return (0); | |||
1279 | if ((buf = malloc(len)) == NULL((void *)0)) { | |||
1280 | log_warn("%s: malloc", __func__); | |||
1281 | return (-1); | |||
1282 | } | |||
1283 | if (sysctl(mib, 7, buf, &len, NULL((void *)0), 0) == -1) { | |||
1284 | log_warn("%s: failed to fetch arp table %u", __func__, | |||
1285 | kt->rtableid); | |||
1286 | free(buf); | |||
1287 | return (-1); | |||
1288 | } | |||
1289 | ||||
1290 | rv = rtmsg_process(buf, len); | |||
1291 | free(buf); | |||
1292 | ||||
1293 | return (rv); | |||
1294 | } | |||
1295 | ||||
1296 | void | |||
1297 | dispatch_rtmsg(int fd, short event, void *arg) | |||
1298 | { | |||
1299 | char buf[RT_BUF_SIZE16384]; | |||
1300 | ssize_t n; | |||
1301 | ||||
1302 | if ((n = read(fd, &buf, sizeof(buf))) == -1) { | |||
| ||||
1303 | log_warn("%s: read error", __func__); | |||
1304 | return; | |||
1305 | } | |||
1306 | ||||
1307 | if (n == 0) { | |||
1308 | log_warnx("%s: routing socket closed", __func__); | |||
1309 | return; | |||
1310 | } | |||
1311 | ||||
1312 | rtmsg_process(buf, n); | |||
1313 | } | |||
1314 | ||||
1315 | int | |||
1316 | rtmsg_process(char *buf, int len) | |||
1317 | { | |||
1318 | struct ktable *kt; | |||
1319 | struct rt_msghdr *rtm; | |||
1320 | struct if_msghdr ifm; | |||
1321 | struct ifa_msghdr *ifam; | |||
1322 | struct sockaddr *sa, *rti_info[RTAX_MAX15]; | |||
1323 | int offset; | |||
1324 | char *next; | |||
1325 | ||||
1326 | for (offset = 0; offset
| |||
1327 | next = buf + offset; | |||
1328 | rtm = (struct rt_msghdr *)next; | |||
1329 | if (rtm->rtm_version != RTM_VERSION5) | |||
1330 | continue; | |||
1331 | ||||
1332 | sa = (struct sockaddr *)(next + rtm->rtm_hdrlen); | |||
1333 | get_rtaddrs(rtm->rtm_addrs, sa, rti_info); | |||
1334 | ||||
1335 | switch (rtm->rtm_type) { | |||
1336 | case RTM_ADD0x1: | |||
1337 | case RTM_GET0x4: | |||
1338 | case RTM_CHANGE0x3: | |||
1339 | case RTM_DELETE0x2: | |||
1340 | case RTM_RESOLVE0xb: | |||
1341 | if (rtm->rtm_errno) /* failed attempts */ | |||
1342 | continue; | |||
1343 | ||||
1344 | if ((kt = ktable_get(rtm->rtm_tableid)) == NULL((void *)0)) | |||
1345 | continue; | |||
1346 | ||||
1347 | if (dispatch_rtmsg_addr(kt, rtm, rti_info) == -1) | |||
1348 | return (-1); | |||
1349 | break; | |||
1350 | case RTM_IFINFO0xe: | |||
1351 | memcpy(&ifm, next, sizeof(ifm)); | |||
1352 | if_change(ifm.ifm_index, ifm.ifm_flags, &ifm.ifm_data, | |||
1353 | (struct sockaddr_dl *)rti_info[RTAX_IFP4]); | |||
1354 | break; | |||
1355 | case RTM_DELADDR0xd: | |||
1356 | ifam = (struct ifa_msghdr *)rtm; | |||
1357 | if ((ifam->ifam_addrs & (RTA_NETMASK0x4 | RTA_IFA0x20 | | |||
1358 | RTA_BRD0x80)) == 0) | |||
1359 | break; | |||
1360 | ||||
1361 | if_deladdr(ifam->ifam_index, rti_info[RTAX_IFA5], | |||
1362 | rti_info[RTAX_NETMASK2], rti_info[RTAX_BRD7]); | |||
1363 | break; | |||
1364 | case RTM_NEWADDR0xc: | |||
1365 | ifam = (struct ifa_msghdr *)rtm; | |||
1366 | if ((ifam->ifam_addrs & (RTA_NETMASK0x4 | RTA_IFA0x20 | | |||
1367 | RTA_BRD0x80)) == 0) | |||
1368 | break; | |||
1369 | ||||
1370 | if_newaddr(ifam->ifam_index, rti_info[RTAX_IFA5], | |||
1371 | rti_info[RTAX_NETMASK2], rti_info[RTAX_BRD7]); | |||
1372 | break; | |||
1373 | case RTM_IFANNOUNCE0xf: | |||
1374 | if_announce(next); | |||
1375 | break; | |||
1376 | case RTM_DESYNC0x10: | |||
1377 | kr_shutdown(); | |||
1378 | if (fetchifs(0) == -1) | |||
1379 | fatalx("rtmsg_process: fetchifs"); | |||
1380 | ktable_init(); | |||
1381 | break; | |||
1382 | default: | |||
1383 | /* ignore for now */ | |||
1384 | break; | |||
1385 | } | |||
1386 | } | |||
1387 | ||||
1388 | return (offset); | |||
1389 | } | |||
1390 | ||||
1391 | int | |||
1392 | dispatch_rtmsg_addr(struct ktable *kt, struct rt_msghdr *rtm, | |||
1393 | struct sockaddr *rti_info[RTAX_MAX15]) | |||
1394 | { | |||
1395 | struct sockaddr *sa, *psa; | |||
1396 | struct sockaddr_in *sa_in, *psa_in = NULL((void *)0); | |||
1397 | struct sockaddr_in6 *sa_in6, *psa_in6 = NULL((void *)0); | |||
1398 | struct sockaddr_dl *sa_dl; | |||
1399 | struct kroute_node *kr; | |||
1400 | struct kroute6_node *kr6; | |||
1401 | struct kif_arp *ka; | |||
1402 | int flags, mpath = 0; | |||
1403 | u_int16_t ifindex; | |||
1404 | u_int8_t prefixlen; | |||
1405 | u_int8_t prio; | |||
1406 | ||||
1407 | flags = 0; | |||
1408 | ifindex = 0; | |||
1409 | prefixlen = 0; | |||
1410 | ||||
1411 | if ((psa = rti_info[RTAX_DST0]) == NULL((void *)0)) | |||
1412 | return (-1); | |||
1413 | ||||
1414 | if (rtm->rtm_flags & RTF_STATIC0x800) | |||
1415 | flags |= F_STATIC0x0002; | |||
1416 | if (rtm->rtm_flags & RTF_BLACKHOLE0x1000) | |||
1417 | flags |= F_BLACKHOLE0x0004; | |||
1418 | if (rtm->rtm_flags & RTF_REJECT0x8) | |||
1419 | flags |= F_REJECT0x0008; | |||
1420 | if (rtm->rtm_flags & RTF_DYNAMIC0x10) | |||
1421 | flags |= F_DYNAMIC0x0010; | |||
1422 | #ifdef RTF_MPATH0x40000 | |||
1423 | if (rtm->rtm_flags & RTF_MPATH0x40000) | |||
1424 | mpath = 1; | |||
1425 | #endif | |||
1426 | ||||
1427 | prio = rtm->rtm_priority; | |||
1428 | switch (psa->sa_family) { | |||
1429 | case AF_INET2: | |||
1430 | psa_in = (struct sockaddr_in *)psa; | |||
1431 | sa_in = (struct sockaddr_in *)rti_info[RTAX_NETMASK2]; | |||
1432 | if (sa_in != NULL((void *)0)) { | |||
1433 | if (sa_in->sin_len != 0) | |||
1434 | prefixlen = mask2prefixlen( | |||
1435 | sa_in->sin_addr.s_addr); | |||
1436 | } else if (rtm->rtm_flags & RTF_HOST0x4) | |||
1437 | prefixlen = 32; | |||
1438 | else | |||
1439 | prefixlen = | |||
1440 | prefixlen_classful(psa_in->sin_addr.s_addr); | |||
1441 | break; | |||
1442 | case AF_INET624: | |||
1443 | psa_in6 = (struct sockaddr_in6 *)psa; | |||
1444 | sa_in6 = (struct sockaddr_in6 *)rti_info[RTAX_NETMASK2]; | |||
1445 | if (sa_in6 != NULL((void *)0)) { | |||
1446 | if (sa_in6->sin6_len != 0) | |||
1447 | prefixlen = mask2prefixlen6(sa_in6); | |||
1448 | } else if (rtm->rtm_flags & RTF_HOST0x4) | |||
1449 | prefixlen = 128; | |||
1450 | else | |||
1451 | fatalx("in6 net addr without netmask"); | |||
1452 | break; | |||
1453 | default: | |||
1454 | return (0); | |||
1455 | } | |||
1456 | ||||
1457 | if ((sa = rti_info[RTAX_GATEWAY1]) != NULL((void *)0)) | |||
1458 | switch (sa->sa_family) { | |||
1459 | case AF_INET2: | |||
1460 | case AF_INET624: | |||
1461 | if (rtm->rtm_flags & RTF_CONNECTED0x800000) { | |||
1462 | flags |= F_CONNECTED0x0001; | |||
1463 | ifindex = rtm->rtm_index; | |||
1464 | } | |||
1465 | mpath = 0; /* link local stuff can't be mpath */ | |||
1466 | break; | |||
1467 | case AF_LINK18: | |||
1468 | /* | |||
1469 | * Traditional BSD connected routes have | |||
1470 | * a gateway of type AF_LINK. | |||
1471 | */ | |||
1472 | flags |= F_CONNECTED0x0001; | |||
1473 | ifindex = rtm->rtm_index; | |||
1474 | mpath = 0; /* link local stuff can't be mpath */ | |||
1475 | break; | |||
1476 | } | |||
1477 | ||||
1478 | if (rtm->rtm_type == RTM_DELETE0x2) { | |||
1479 | if (sa != NULL((void *)0) && sa->sa_family == AF_LINK18 && | |||
1480 | (rtm->rtm_flags & RTF_HOST0x4) && | |||
1481 | psa->sa_family == AF_INET2) { | |||
1482 | if ((ka = karp_find(psa, ifindex)) == NULL((void *)0)) | |||
1483 | return (0); | |||
1484 | if (karp_remove(NULL((void *)0), ka) == -1) | |||
1485 | return (-1); | |||
1486 | return (0); | |||
1487 | } else if (sa == NULL((void *)0) && (rtm->rtm_flags & RTF_HOST0x4) && | |||
1488 | psa->sa_family == AF_INET2) { | |||
1489 | if ((ka = karp_find(psa, ifindex)) != NULL((void *)0)) | |||
1490 | karp_remove(NULL((void *)0), ka); | |||
1491 | /* Continue to the route section below */ | |||
1492 | } | |||
1493 | switch (psa->sa_family) { | |||
1494 | case AF_INET2: | |||
1495 | sa_in = (struct sockaddr_in *)sa; | |||
1496 | if ((kr = kroute_find(kt, psa_in->sin_addr.s_addr, | |||
1497 | prefixlen, prio)) == NULL((void *)0)) | |||
1498 | return (0); | |||
1499 | ||||
1500 | if (mpath) | |||
1501 | /* get the correct route */ | |||
1502 | if ((kr = kroute_matchgw(kr, sa_in)) == NULL((void *)0)) { | |||
1503 | log_warnx("%s[delete]: " | |||
1504 | "mpath route not found", __func__); | |||
1505 | return (0); | |||
1506 | } | |||
1507 | ||||
1508 | if (kroute_remove(kt, kr) == -1) | |||
1509 | return (-1); | |||
1510 | break; | |||
1511 | case AF_INET624: | |||
1512 | sa_in6 = (struct sockaddr_in6 *)sa; | |||
1513 | if ((kr6 = kroute6_find(kt, &psa_in6->sin6_addr, | |||
1514 | prefixlen, prio)) == NULL((void *)0)) | |||
1515 | return (0); | |||
1516 | ||||
1517 | if (mpath) | |||
1518 | /* get the correct route */ | |||
1519 | if ((kr6 = kroute6_matchgw(kr6, sa_in6)) == | |||
1520 | NULL((void *)0)) { | |||
1521 | log_warnx("%s[delete]: " | |||
1522 | "IPv6 mpath route not found", | |||
1523 | __func__); | |||
1524 | return (0); | |||
1525 | } | |||
1526 | ||||
1527 | if (kroute6_remove(kt, kr6) == -1) | |||
1528 | return (-1); | |||
1529 | break; | |||
1530 | } | |||
1531 | return (0); | |||
1532 | } | |||
1533 | ||||
1534 | if (sa == NULL((void *)0) && !(flags & F_CONNECTED0x0001)) | |||
1535 | return (0); | |||
1536 | ||||
1537 | /* Add or update an ARP entry */ | |||
1538 | if ((rtm->rtm_flags & RTF_LLINFO0x400) && (rtm->rtm_flags & RTF_HOST0x4) && | |||
1539 | sa != NULL((void *)0) && sa->sa_family == AF_LINK18 && | |||
1540 | psa->sa_family == AF_INET2) { | |||
1541 | sa_dl = (struct sockaddr_dl *)sa; | |||
1542 | /* ignore incomplete entries */ | |||
1543 | if (!sa_dl->sdl_alen) | |||
1544 | return (0); | |||
1545 | /* ignore entries that do not specify an interface */ | |||
1546 | if (ifindex == 0) | |||
1547 | return (0); | |||
1548 | if ((ka = karp_find(psa, ifindex)) != NULL((void *)0)) { | |||
1549 | memcpy(&ka->target.sdl, sa_dl, sa_dl->sdl_len); | |||
1550 | if (rtm->rtm_flags & RTF_PERMANENT_ARP0x2000) | |||
1551 | flags |= F_STATIC0x0002; | |||
1552 | ka->flags = flags; | |||
1553 | } else { | |||
1554 | if ((ka = calloc(1, sizeof(struct kif_arp))) == NULL((void *)0)) { | |||
1555 | log_warn("%s: calloc", __func__); | |||
1556 | return (-1); | |||
1557 | } | |||
1558 | memcpy(&ka->addr.sa, psa, psa->sa_len); | |||
1559 | memcpy(&ka->target.sdl, sa_dl, sa_dl->sdl_len); | |||
1560 | if (rtm->rtm_flags & RTF_PERMANENT_ARP0x2000) | |||
1561 | flags |= F_STATIC0x0002; | |||
1562 | ka->flags = flags; | |||
1563 | ka->if_index = ifindex; | |||
1564 | if (karp_insert(NULL((void *)0), ka)) { | |||
1565 | free(ka); | |||
1566 | log_warnx("%s: failed to insert", __func__); | |||
1567 | return (-1); | |||
1568 | } | |||
1569 | } | |||
1570 | return (0); | |||
1571 | } | |||
1572 | ||||
1573 | switch (psa->sa_family) { | |||
1574 | case AF_INET2: | |||
1575 | sa_in = (struct sockaddr_in *)sa; | |||
1576 | if ((kr = kroute_find(kt, psa_in->sin_addr.s_addr, prefixlen, | |||
1577 | prio)) != NULL((void *)0)) { | |||
1578 | /* get the correct route */ | |||
1579 | if (mpath && rtm->rtm_type == RTM_CHANGE0x3 && | |||
1580 | (kr = kroute_matchgw(kr, sa_in)) == NULL((void *)0)) { | |||
1581 | log_warnx("%s[change]: " | |||
1582 | "mpath route not found", __func__); | |||
1583 | return (-1); | |||
1584 | } else if (mpath && rtm->rtm_type == RTM_ADD0x1) | |||
1585 | goto add4; | |||
1586 | ||||
1587 | if (sa_in != NULL((void *)0)) | |||
1588 | kr->r.nexthop.s_addr = | |||
1589 | sa_in->sin_addr.s_addr; | |||
1590 | else | |||
1591 | kr->r.nexthop.s_addr = 0; | |||
1592 | kr->r.flags = flags; | |||
1593 | kr->r.if_index = ifindex; | |||
1594 | kr->r.ticks = smi_getticks(); | |||
1595 | } else { | |||
1596 | add4: | |||
1597 | if ((kr = calloc(1, | |||
1598 | sizeof(struct kroute_node))) == NULL((void *)0)) { | |||
1599 | log_warn("%s: calloc", __func__); | |||
1600 | return (-1); | |||
1601 | } | |||
1602 | kr->r.prefix.s_addr = psa_in->sin_addr.s_addr; | |||
1603 | kr->r.prefixlen = prefixlen; | |||
1604 | if (sa_in != NULL((void *)0)) | |||
1605 | kr->r.nexthop.s_addr = sa_in->sin_addr.s_addr; | |||
1606 | else | |||
1607 | kr->r.nexthop.s_addr = 0; | |||
1608 | kr->r.flags = flags; | |||
1609 | kr->r.if_index = ifindex; | |||
1610 | kr->r.ticks = smi_getticks(); | |||
1611 | kr->r.priority = prio; | |||
1612 | ||||
1613 | kroute_insert(kt, kr); | |||
1614 | } | |||
1615 | break; | |||
1616 | case AF_INET624: | |||
1617 | sa_in6 = (struct sockaddr_in6 *)sa; | |||
1618 | if ((kr6 = kroute6_find(kt, &psa_in6->sin6_addr, prefixlen, | |||
1619 | prio)) != NULL((void *)0)) { | |||
1620 | /* get the correct route */ | |||
1621 | if (mpath && rtm->rtm_type == RTM_CHANGE0x3 && | |||
1622 | (kr6 = kroute6_matchgw(kr6, sa_in6)) == | |||
1623 | NULL((void *)0)) { | |||
1624 | log_warnx("%s[change]: " | |||
1625 | "IPv6 mpath route not found", __func__); | |||
1626 | return (-1); | |||
1627 | } else if (mpath && rtm->rtm_type == RTM_ADD0x1) | |||
1628 | goto add6; | |||
1629 | ||||
1630 | if (sa_in6 != NULL((void *)0)) | |||
1631 | memcpy(&kr6->r.nexthop, | |||
1632 | &sa_in6->sin6_addr, | |||
1633 | sizeof(struct in6_addr)); | |||
1634 | else | |||
1635 | memcpy(&kr6->r.nexthop, | |||
1636 | &in6addr_any, | |||
1637 | sizeof(struct in6_addr)); | |||
1638 | ||||
1639 | kr6->r.flags = flags; | |||
1640 | kr6->r.if_index = ifindex; | |||
1641 | kr6->r.ticks = smi_getticks(); | |||
1642 | } else { | |||
1643 | add6: | |||
1644 | if ((kr6 = calloc(1, | |||
1645 | sizeof(struct kroute6_node))) == NULL((void *)0)) { | |||
1646 | log_warn("%s: calloc", __func__); | |||
1647 | return (-1); | |||
1648 | } | |||
1649 | memcpy(&kr6->r.prefix, &psa_in6->sin6_addr, | |||
1650 | sizeof(struct in6_addr)); | |||
1651 | kr6->r.prefixlen = prefixlen; | |||
1652 | if (sa_in6 != NULL((void *)0)) | |||
1653 | memcpy(&kr6->r.nexthop, &sa_in6->sin6_addr, | |||
1654 | sizeof(struct in6_addr)); | |||
1655 | else | |||
1656 | memcpy(&kr6->r.nexthop, &in6addr_any, | |||
1657 | sizeof(struct in6_addr)); | |||
1658 | kr6->r.flags = flags; | |||
1659 | kr6->r.if_index = ifindex; | |||
1660 | kr6->r.ticks = smi_getticks(); | |||
1661 | kr6->r.priority = prio; | |||
1662 | ||||
1663 | kroute6_insert(kt, kr6); | |||
1664 | } | |||
1665 | break; | |||
1666 | } | |||
1667 | ||||
1668 | return (0); | |||
1669 | } | |||
1670 | ||||
1671 | struct kroute * | |||
1672 | kroute_first(void) | |||
1673 | { | |||
1674 | struct kroute_node *kn; | |||
1675 | struct ktable *kt; | |||
1676 | ||||
1677 | if ((kt = ktable_get(0)) == NULL((void *)0)) | |||
1678 | return (NULL((void *)0)); | |||
1679 | kn = RB_MIN(kroute_tree, &kt->krt)kroute_tree_RB_MINMAX(&kt->krt, -1); | |||
1680 | return (&kn->r); | |||
1681 | } | |||
1682 | ||||
1683 | struct kroute * | |||
1684 | kroute_getaddr(in_addr_t prefix, u_int8_t prefixlen, u_int8_t prio, int next) | |||
1685 | { | |||
1686 | struct kroute_node *kn; | |||
1687 | struct ktable *kt; | |||
1688 | ||||
1689 | if ((kt = ktable_get(0)) == NULL((void *)0)) | |||
1690 | return (NULL((void *)0)); | |||
1691 | kn = kroute_find(kt, prefix, prefixlen, prio); | |||
1692 | if (kn != NULL((void *)0) && next) | |||
1693 | kn = RB_NEXT(kroute_tree, &kt->krt, kn)kroute_tree_RB_NEXT(kn); | |||
1694 | if (kn != NULL((void *)0)) | |||
1695 | return (&kn->r); | |||
1696 | else | |||
1697 | return (NULL((void *)0)); | |||
1698 | } |