Bug Summary

File:src/usr.sbin/bgpd/rde_rib.c
Warning:line 254, column 29
Use of memory after it is freed

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple amd64-unknown-openbsd7.0 -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name rde_rib.c -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 1 -pic-is-pie -mframe-pointer=all -relaxed-aliasing -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -target-feature +retpoline-indirect-calls -target-feature +retpoline-indirect-branches -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/usr/src/usr.sbin/bgpd/obj -resource-dir /usr/local/lib/clang/13.0.0 -I /usr/src/usr.sbin/bgpd -internal-isystem /usr/local/lib/clang/13.0.0/include -internal-externc-isystem /usr/include -O2 -fdebug-compilation-dir=/usr/src/usr.sbin/bgpd/obj -ferror-limit 19 -fwrapv -D_RET_PROTECTOR -ret-protector -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -fno-builtin-malloc -fno-builtin-calloc -fno-builtin-realloc -fno-builtin-valloc -fno-builtin-free -fno-builtin-strdup -fno-builtin-strndup -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/ben/Projects/vmm/scan-build/2022-01-12-194120-40624-1 -x c /usr/src/usr.sbin/bgpd/rde_rib.c
1/* $OpenBSD: rde_rib.c,v 1.224 2021/08/09 08:15:35 claudio Exp $ */
2
3/*
4 * Copyright (c) 2003, 2004 Claudio Jeker <claudio@openbsd.org>
5 *
6 * Permission to use, copy, modify, and distribute this software for any
7 * purpose with or without fee is hereby granted, provided that the above
8 * copyright notice and this permission notice appear in all copies.
9 *
10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 */
18
19#include <sys/types.h>
20#include <sys/queue.h>
21
22#include <limits.h>
23#include <stdlib.h>
24#include <string.h>
25#include <siphash.h>
26#include <time.h>
27
28#include "bgpd.h"
29#include "rde.h"
30#include "log.h"
31
32/*
33 * BGP RIB -- Routing Information Base
34 *
35 * The RIB is build with one aspect in mind. Speed -- actually update speed.
36 * Therefore one thing needs to be absolutely avoided, long table walks.
37 * This is achieved by heavily linking the different parts together.
38 */
39u_int16_t rib_size;
40struct rib **ribs;
41
42struct rib_entry *rib_add(struct rib *, struct bgpd_addr *, int);
43static inline int rib_compare(const struct rib_entry *,
44 const struct rib_entry *);
45void rib_remove(struct rib_entry *);
46int rib_empty(struct rib_entry *);
47static void rib_dump_abort(u_int16_t);
48
49RB_PROTOTYPE(rib_tree, rib_entry, rib_e, rib_compare)void rib_tree_RB_INSERT_COLOR(struct rib_tree *, struct rib_entry
*); void rib_tree_RB_REMOVE_COLOR(struct rib_tree *, struct rib_entry
*, struct rib_entry *); struct rib_entry *rib_tree_RB_REMOVE
(struct rib_tree *, struct rib_entry *); struct rib_entry *rib_tree_RB_INSERT
(struct rib_tree *, struct rib_entry *); struct rib_entry *rib_tree_RB_FIND
(struct rib_tree *, struct rib_entry *); struct rib_entry *rib_tree_RB_NFIND
(struct rib_tree *, struct rib_entry *); struct rib_entry *rib_tree_RB_NEXT
(struct rib_entry *); struct rib_entry *rib_tree_RB_PREV(struct
rib_entry *); struct rib_entry *rib_tree_RB_MINMAX(struct rib_tree
*, int);;
50RB_GENERATE(rib_tree, rib_entry, rib_e, rib_compare)void rib_tree_RB_INSERT_COLOR(struct rib_tree *head, struct rib_entry
*elm) { struct rib_entry *parent, *gparent, *tmp; while ((parent
= (elm)->rib_e.rbe_parent) && (parent)->rib_e.
rbe_color == 1) { gparent = (parent)->rib_e.rbe_parent; if
(parent == (gparent)->rib_e.rbe_left) { tmp = (gparent)->
rib_e.rbe_right; if (tmp && (tmp)->rib_e.rbe_color
== 1) { (tmp)->rib_e.rbe_color = 0; do { (parent)->rib_e
.rbe_color = 0; (gparent)->rib_e.rbe_color = 1; } while (0
); elm = gparent; continue; } if ((parent)->rib_e.rbe_right
== elm) { do { (tmp) = (parent)->rib_e.rbe_right; if (((parent
)->rib_e.rbe_right = (tmp)->rib_e.rbe_left)) { ((tmp)->
rib_e.rbe_left)->rib_e.rbe_parent = (parent); } do {} while
(0); if (((tmp)->rib_e.rbe_parent = (parent)->rib_e.rbe_parent
)) { if ((parent) == ((parent)->rib_e.rbe_parent)->rib_e
.rbe_left) ((parent)->rib_e.rbe_parent)->rib_e.rbe_left
= (tmp); else ((parent)->rib_e.rbe_parent)->rib_e.rbe_right
= (tmp); } else (head)->rbh_root = (tmp); (tmp)->rib_e
.rbe_left = (parent); (parent)->rib_e.rbe_parent = (tmp); do
{} while (0); if (((tmp)->rib_e.rbe_parent)) do {} while (
0); } while (0); tmp = parent; parent = elm; elm = tmp; } do {
(parent)->rib_e.rbe_color = 0; (gparent)->rib_e.rbe_color
= 1; } while (0); do { (tmp) = (gparent)->rib_e.rbe_left;
if (((gparent)->rib_e.rbe_left = (tmp)->rib_e.rbe_right
)) { ((tmp)->rib_e.rbe_right)->rib_e.rbe_parent = (gparent
); } do {} while (0); if (((tmp)->rib_e.rbe_parent = (gparent
)->rib_e.rbe_parent)) { if ((gparent) == ((gparent)->rib_e
.rbe_parent)->rib_e.rbe_left) ((gparent)->rib_e.rbe_parent
)->rib_e.rbe_left = (tmp); else ((gparent)->rib_e.rbe_parent
)->rib_e.rbe_right = (tmp); } else (head)->rbh_root = (
tmp); (tmp)->rib_e.rbe_right = (gparent); (gparent)->rib_e
.rbe_parent = (tmp); do {} while (0); if (((tmp)->rib_e.rbe_parent
)) do {} while (0); } while (0); } else { tmp = (gparent)->
rib_e.rbe_left; if (tmp && (tmp)->rib_e.rbe_color ==
1) { (tmp)->rib_e.rbe_color = 0; do { (parent)->rib_e.
rbe_color = 0; (gparent)->rib_e.rbe_color = 1; } while (0)
; elm = gparent; continue; } if ((parent)->rib_e.rbe_left ==
elm) { do { (tmp) = (parent)->rib_e.rbe_left; if (((parent
)->rib_e.rbe_left = (tmp)->rib_e.rbe_right)) { ((tmp)->
rib_e.rbe_right)->rib_e.rbe_parent = (parent); } do {} while
(0); if (((tmp)->rib_e.rbe_parent = (parent)->rib_e.rbe_parent
)) { if ((parent) == ((parent)->rib_e.rbe_parent)->rib_e
.rbe_left) ((parent)->rib_e.rbe_parent)->rib_e.rbe_left
= (tmp); else ((parent)->rib_e.rbe_parent)->rib_e.rbe_right
= (tmp); } else (head)->rbh_root = (tmp); (tmp)->rib_e
.rbe_right = (parent); (parent)->rib_e.rbe_parent = (tmp);
do {} while (0); if (((tmp)->rib_e.rbe_parent)) do {} while
(0); } while (0); tmp = parent; parent = elm; elm = tmp; } do
{ (parent)->rib_e.rbe_color = 0; (gparent)->rib_e.rbe_color
= 1; } while (0); do { (tmp) = (gparent)->rib_e.rbe_right
; if (((gparent)->rib_e.rbe_right = (tmp)->rib_e.rbe_left
)) { ((tmp)->rib_e.rbe_left)->rib_e.rbe_parent = (gparent
); } do {} while (0); if (((tmp)->rib_e.rbe_parent = (gparent
)->rib_e.rbe_parent)) { if ((gparent) == ((gparent)->rib_e
.rbe_parent)->rib_e.rbe_left) ((gparent)->rib_e.rbe_parent
)->rib_e.rbe_left = (tmp); else ((gparent)->rib_e.rbe_parent
)->rib_e.rbe_right = (tmp); } else (head)->rbh_root = (
tmp); (tmp)->rib_e.rbe_left = (gparent); (gparent)->rib_e
.rbe_parent = (tmp); do {} while (0); if (((tmp)->rib_e.rbe_parent
)) do {} while (0); } while (0); } } (head->rbh_root)->
rib_e.rbe_color = 0; } void rib_tree_RB_REMOVE_COLOR(struct rib_tree
*head, struct rib_entry *parent, struct rib_entry *elm) { struct
rib_entry *tmp; while ((elm == ((void*)0) || (elm)->rib_e
.rbe_color == 0) && elm != (head)->rbh_root) { if (
(parent)->rib_e.rbe_left == elm) { tmp = (parent)->rib_e
.rbe_right; if ((tmp)->rib_e.rbe_color == 1) { do { (tmp)->
rib_e.rbe_color = 0; (parent)->rib_e.rbe_color = 1; } while
(0); do { (tmp) = (parent)->rib_e.rbe_right; if (((parent
)->rib_e.rbe_right = (tmp)->rib_e.rbe_left)) { ((tmp)->
rib_e.rbe_left)->rib_e.rbe_parent = (parent); } do {} while
(0); if (((tmp)->rib_e.rbe_parent = (parent)->rib_e.rbe_parent
)) { if ((parent) == ((parent)->rib_e.rbe_parent)->rib_e
.rbe_left) ((parent)->rib_e.rbe_parent)->rib_e.rbe_left
= (tmp); else ((parent)->rib_e.rbe_parent)->rib_e.rbe_right
= (tmp); } else (head)->rbh_root = (tmp); (tmp)->rib_e
.rbe_left = (parent); (parent)->rib_e.rbe_parent = (tmp); do
{} while (0); if (((tmp)->rib_e.rbe_parent)) do {} while (
0); } while (0); tmp = (parent)->rib_e.rbe_right; } if (((
tmp)->rib_e.rbe_left == ((void*)0) || ((tmp)->rib_e.rbe_left
)->rib_e.rbe_color == 0) && ((tmp)->rib_e.rbe_right
== ((void*)0) || ((tmp)->rib_e.rbe_right)->rib_e.rbe_color
== 0)) { (tmp)->rib_e.rbe_color = 1; elm = parent; parent
= (elm)->rib_e.rbe_parent; } else { if ((tmp)->rib_e.rbe_right
== ((void*)0) || ((tmp)->rib_e.rbe_right)->rib_e.rbe_color
== 0) { struct rib_entry *oleft; if ((oleft = (tmp)->rib_e
.rbe_left)) (oleft)->rib_e.rbe_color = 0; (tmp)->rib_e.
rbe_color = 1; do { (oleft) = (tmp)->rib_e.rbe_left; if ((
(tmp)->rib_e.rbe_left = (oleft)->rib_e.rbe_right)) { ((
oleft)->rib_e.rbe_right)->rib_e.rbe_parent = (tmp); } do
{} while (0); if (((oleft)->rib_e.rbe_parent = (tmp)->
rib_e.rbe_parent)) { if ((tmp) == ((tmp)->rib_e.rbe_parent
)->rib_e.rbe_left) ((tmp)->rib_e.rbe_parent)->rib_e.
rbe_left = (oleft); else ((tmp)->rib_e.rbe_parent)->rib_e
.rbe_right = (oleft); } else (head)->rbh_root = (oleft); (
oleft)->rib_e.rbe_right = (tmp); (tmp)->rib_e.rbe_parent
= (oleft); do {} while (0); if (((oleft)->rib_e.rbe_parent
)) do {} while (0); } while (0); tmp = (parent)->rib_e.rbe_right
; } (tmp)->rib_e.rbe_color = (parent)->rib_e.rbe_color;
(parent)->rib_e.rbe_color = 0; if ((tmp)->rib_e.rbe_right
) ((tmp)->rib_e.rbe_right)->rib_e.rbe_color = 0; do { (
tmp) = (parent)->rib_e.rbe_right; if (((parent)->rib_e.
rbe_right = (tmp)->rib_e.rbe_left)) { ((tmp)->rib_e.rbe_left
)->rib_e.rbe_parent = (parent); } do {} while (0); if (((tmp
)->rib_e.rbe_parent = (parent)->rib_e.rbe_parent)) { if
((parent) == ((parent)->rib_e.rbe_parent)->rib_e.rbe_left
) ((parent)->rib_e.rbe_parent)->rib_e.rbe_left = (tmp);
else ((parent)->rib_e.rbe_parent)->rib_e.rbe_right = (
tmp); } else (head)->rbh_root = (tmp); (tmp)->rib_e.rbe_left
= (parent); (parent)->rib_e.rbe_parent = (tmp); do {} while
(0); if (((tmp)->rib_e.rbe_parent)) do {} while (0); } while
(0); elm = (head)->rbh_root; break; } } else { tmp = (parent
)->rib_e.rbe_left; if ((tmp)->rib_e.rbe_color == 1) { do
{ (tmp)->rib_e.rbe_color = 0; (parent)->rib_e.rbe_color
= 1; } while (0); do { (tmp) = (parent)->rib_e.rbe_left; if
(((parent)->rib_e.rbe_left = (tmp)->rib_e.rbe_right)) {
((tmp)->rib_e.rbe_right)->rib_e.rbe_parent = (parent);
} do {} while (0); if (((tmp)->rib_e.rbe_parent = (parent
)->rib_e.rbe_parent)) { if ((parent) == ((parent)->rib_e
.rbe_parent)->rib_e.rbe_left) ((parent)->rib_e.rbe_parent
)->rib_e.rbe_left = (tmp); else ((parent)->rib_e.rbe_parent
)->rib_e.rbe_right = (tmp); } else (head)->rbh_root = (
tmp); (tmp)->rib_e.rbe_right = (parent); (parent)->rib_e
.rbe_parent = (tmp); do {} while (0); if (((tmp)->rib_e.rbe_parent
)) do {} while (0); } while (0); tmp = (parent)->rib_e.rbe_left
; } if (((tmp)->rib_e.rbe_left == ((void*)0) || ((tmp)->
rib_e.rbe_left)->rib_e.rbe_color == 0) && ((tmp)->
rib_e.rbe_right == ((void*)0) || ((tmp)->rib_e.rbe_right)->
rib_e.rbe_color == 0)) { (tmp)->rib_e.rbe_color = 1; elm =
parent; parent = (elm)->rib_e.rbe_parent; } else { if ((tmp
)->rib_e.rbe_left == ((void*)0) || ((tmp)->rib_e.rbe_left
)->rib_e.rbe_color == 0) { struct rib_entry *oright; if ((
oright = (tmp)->rib_e.rbe_right)) (oright)->rib_e.rbe_color
= 0; (tmp)->rib_e.rbe_color = 1; do { (oright) = (tmp)->
rib_e.rbe_right; if (((tmp)->rib_e.rbe_right = (oright)->
rib_e.rbe_left)) { ((oright)->rib_e.rbe_left)->rib_e.rbe_parent
= (tmp); } do {} while (0); if (((oright)->rib_e.rbe_parent
= (tmp)->rib_e.rbe_parent)) { if ((tmp) == ((tmp)->rib_e
.rbe_parent)->rib_e.rbe_left) ((tmp)->rib_e.rbe_parent)
->rib_e.rbe_left = (oright); else ((tmp)->rib_e.rbe_parent
)->rib_e.rbe_right = (oright); } else (head)->rbh_root =
(oright); (oright)->rib_e.rbe_left = (tmp); (tmp)->rib_e
.rbe_parent = (oright); do {} while (0); if (((oright)->rib_e
.rbe_parent)) do {} while (0); } while (0); tmp = (parent)->
rib_e.rbe_left; } (tmp)->rib_e.rbe_color = (parent)->rib_e
.rbe_color; (parent)->rib_e.rbe_color = 0; if ((tmp)->rib_e
.rbe_left) ((tmp)->rib_e.rbe_left)->rib_e.rbe_color = 0
; do { (tmp) = (parent)->rib_e.rbe_left; if (((parent)->
rib_e.rbe_left = (tmp)->rib_e.rbe_right)) { ((tmp)->rib_e
.rbe_right)->rib_e.rbe_parent = (parent); } do {} while (0
); if (((tmp)->rib_e.rbe_parent = (parent)->rib_e.rbe_parent
)) { if ((parent) == ((parent)->rib_e.rbe_parent)->rib_e
.rbe_left) ((parent)->rib_e.rbe_parent)->rib_e.rbe_left
= (tmp); else ((parent)->rib_e.rbe_parent)->rib_e.rbe_right
= (tmp); } else (head)->rbh_root = (tmp); (tmp)->rib_e
.rbe_right = (parent); (parent)->rib_e.rbe_parent = (tmp);
do {} while (0); if (((tmp)->rib_e.rbe_parent)) do {} while
(0); } while (0); elm = (head)->rbh_root; break; } } } if
(elm) (elm)->rib_e.rbe_color = 0; } struct rib_entry * rib_tree_RB_REMOVE
(struct rib_tree *head, struct rib_entry *elm) { struct rib_entry
*child, *parent, *old = elm; int color; if ((elm)->rib_e.
rbe_left == ((void*)0)) child = (elm)->rib_e.rbe_right; else
if ((elm)->rib_e.rbe_right == ((void*)0)) child = (elm)->
rib_e.rbe_left; else { struct rib_entry *left; elm = (elm)->
rib_e.rbe_right; while ((left = (elm)->rib_e.rbe_left)) elm
= left; child = (elm)->rib_e.rbe_right; parent = (elm)->
rib_e.rbe_parent; color = (elm)->rib_e.rbe_color; if (child
) (child)->rib_e.rbe_parent = parent; if (parent) { if ((parent
)->rib_e.rbe_left == elm) (parent)->rib_e.rbe_left = child
; else (parent)->rib_e.rbe_right = child; do {} while (0);
} else (head)->rbh_root = child; if ((elm)->rib_e.rbe_parent
== old) parent = elm; (elm)->rib_e = (old)->rib_e; if (
(old)->rib_e.rbe_parent) { if (((old)->rib_e.rbe_parent
)->rib_e.rbe_left == old) ((old)->rib_e.rbe_parent)->
rib_e.rbe_left = elm; else ((old)->rib_e.rbe_parent)->rib_e
.rbe_right = elm; do {} while (0); } else (head)->rbh_root
= elm; ((old)->rib_e.rbe_left)->rib_e.rbe_parent = elm
; if ((old)->rib_e.rbe_right) ((old)->rib_e.rbe_right)->
rib_e.rbe_parent = elm; if (parent) { left = parent; do { do {
} while (0); } while ((left = (left)->rib_e.rbe_parent)); }
goto color; } parent = (elm)->rib_e.rbe_parent; color = (
elm)->rib_e.rbe_color; if (child) (child)->rib_e.rbe_parent
= parent; if (parent) { if ((parent)->rib_e.rbe_left == elm
) (parent)->rib_e.rbe_left = child; else (parent)->rib_e
.rbe_right = child; do {} while (0); } else (head)->rbh_root
= child; color: if (color == 0) rib_tree_RB_REMOVE_COLOR(head
, parent, child); return (old); } struct rib_entry * rib_tree_RB_INSERT
(struct rib_tree *head, struct rib_entry *elm) { struct rib_entry
*tmp; struct rib_entry *parent = ((void*)0); int comp = 0; tmp
= (head)->rbh_root; while (tmp) { parent = tmp; comp = (rib_compare
)(elm, parent); if (comp < 0) tmp = (tmp)->rib_e.rbe_left
; else if (comp > 0) tmp = (tmp)->rib_e.rbe_right; else
return (tmp); } do { (elm)->rib_e.rbe_parent = parent; (elm
)->rib_e.rbe_left = (elm)->rib_e.rbe_right = ((void*)0)
; (elm)->rib_e.rbe_color = 1; } while (0); if (parent != (
(void*)0)) { if (comp < 0) (parent)->rib_e.rbe_left = elm
; else (parent)->rib_e.rbe_right = elm; do {} while (0); }
else (head)->rbh_root = elm; rib_tree_RB_INSERT_COLOR(head
, elm); return (((void*)0)); } struct rib_entry * rib_tree_RB_FIND
(struct rib_tree *head, struct rib_entry *elm) { struct rib_entry
*tmp = (head)->rbh_root; int comp; while (tmp) { comp = rib_compare
(elm, tmp); if (comp < 0) tmp = (tmp)->rib_e.rbe_left; else
if (comp > 0) tmp = (tmp)->rib_e.rbe_right; else return
(tmp); } return (((void*)0)); } struct rib_entry * rib_tree_RB_NFIND
(struct rib_tree *head, struct rib_entry *elm) { struct rib_entry
*tmp = (head)->rbh_root; struct rib_entry *res = ((void*)
0); int comp; while (tmp) { comp = rib_compare(elm, tmp); if (
comp < 0) { res = tmp; tmp = (tmp)->rib_e.rbe_left; } else
if (comp > 0) tmp = (tmp)->rib_e.rbe_right; else return
(tmp); } return (res); } struct rib_entry * rib_tree_RB_NEXT
(struct rib_entry *elm) { if ((elm)->rib_e.rbe_right) { elm
= (elm)->rib_e.rbe_right; while ((elm)->rib_e.rbe_left
) elm = (elm)->rib_e.rbe_left; } else { if ((elm)->rib_e
.rbe_parent && (elm == ((elm)->rib_e.rbe_parent)->
rib_e.rbe_left)) elm = (elm)->rib_e.rbe_parent; else { while
((elm)->rib_e.rbe_parent && (elm == ((elm)->rib_e
.rbe_parent)->rib_e.rbe_right)) elm = (elm)->rib_e.rbe_parent
; elm = (elm)->rib_e.rbe_parent; } } return (elm); } struct
rib_entry * rib_tree_RB_PREV(struct rib_entry *elm) { if ((elm
)->rib_e.rbe_left) { elm = (elm)->rib_e.rbe_left; while
((elm)->rib_e.rbe_right) elm = (elm)->rib_e.rbe_right;
} else { if ((elm)->rib_e.rbe_parent && (elm == (
(elm)->rib_e.rbe_parent)->rib_e.rbe_right)) elm = (elm)
->rib_e.rbe_parent; else { while ((elm)->rib_e.rbe_parent
&& (elm == ((elm)->rib_e.rbe_parent)->rib_e.rbe_left
)) elm = (elm)->rib_e.rbe_parent; elm = (elm)->rib_e.rbe_parent
; } } return (elm); } struct rib_entry * rib_tree_RB_MINMAX(struct
rib_tree *head, int val) { struct rib_entry *tmp = (head)->
rbh_root; struct rib_entry *parent = ((void*)0); while (tmp) {
parent = tmp; if (val < 0) tmp = (tmp)->rib_e.rbe_left
; else tmp = (tmp)->rib_e.rbe_right; } return (parent); };
51
52struct rib_context {
53 LIST_ENTRY(rib_context)struct { struct rib_context *le_next; struct rib_context **le_prev
; } entry;
54 struct rib_entry *ctx_re;
55 struct prefix *ctx_p;
56 u_int32_t ctx_id;
57 void (*ctx_rib_call)(struct rib_entry *, void *);
58 void (*ctx_prefix_call)(struct prefix *, void *);
59 void (*ctx_done)(void *, u_int8_t);
60 int (*ctx_throttle)(void *);
61 void *ctx_arg;
62 unsigned int ctx_count;
63 u_int8_t ctx_aid;
64};
65LIST_HEAD(, rib_context)struct { struct rib_context *lh_first; } rib_dumps = LIST_HEAD_INITIALIZER(rib_dumps){ ((void*)0) };
66
67static void prefix_dump_r(struct rib_context *);
68
69static inline struct rib_entry *
70re_lock(struct rib_entry *re)
71{
72 if (re->lock != 0)
73 log_warnx("%s: entry already locked", __func__);
74 re->lock = 1;
75 return re;
76}
77
78static inline struct rib_entry *
79re_unlock(struct rib_entry *re)
80{
81 if (re->lock == 0)
82 log_warnx("%s: entry already unlocked", __func__);
83 re->lock = 0;
84 return re;
85}
86
87static inline int
88re_is_locked(struct rib_entry *re)
89{
90 return (re->lock != 0);
91}
92
93static inline struct prefix *
94prefix_lock(struct prefix *p)
95{
96 if (p->flags & PREFIX_FLAG_LOCKED0x80)
97 fatalx("%s: locking locked prefix", __func__);
98 p->flags |= PREFIX_FLAG_LOCKED0x80;
99 return p;
100}
101
102static inline struct prefix *
103prefix_unlock(struct prefix *p)
104{
105 if ((p->flags & PREFIX_FLAG_LOCKED0x80) == 0)
106 fatalx("%s: unlocking unlocked prefix", __func__);
107 p->flags &= ~PREFIX_FLAG_LOCKED0x80;
108 return p;
109}
110
111static inline int
112prefix_is_locked(struct prefix *p)
113{
114 return (p->flags & PREFIX_FLAG_LOCKED0x80) != 0;
115}
116
117static inline int
118prefix_is_dead(struct prefix *p)
119{
120 return (p->flags & PREFIX_FLAG_DEAD0x04) != 0;
121}
122
123static inline struct rib_tree *
124rib_tree(struct rib *rib)
125{
126 return (&rib->tree);
127}
128
129static inline int
130rib_compare(const struct rib_entry *a, const struct rib_entry *b)
131{
132 return (pt_prefix_cmp(a->prefix, b->prefix));
133}
134
135/* RIB specific functions */
136struct rib *
137rib_new(char *name, u_int rtableid, u_int16_t flags)
138{
139 struct rib *new;
140 u_int16_t id;
141
142 for (id = 0; id < rib_size; id++) {
143 if (ribs[id] == NULL((void*)0))
144 break;
145 }
146
147 if (id >= rib_size) {
148 if ((ribs = recallocarray(ribs, id, id + 8,
149 sizeof(struct rib))) == NULL((void*)0))
150 fatal(NULL((void*)0));
151 rib_size = id + 8;
152 }
153
154 if ((new = calloc(1, sizeof(*new))) == NULL((void*)0))
155 fatal(NULL((void*)0));
156
157 strlcpy(new->name, name, sizeof(new->name));
158 RB_INIT(rib_tree(new))do { (rib_tree(new))->rbh_root = ((void*)0); } while (0);
159 new->state = RECONF_REINIT;
160 new->id = id;
161 new->flags = flags;
162 new->rtableid = rtableid;
163
164 new->in_rules = calloc(1, sizeof(struct filter_head));
165 if (new->in_rules == NULL((void*)0))
166 fatal(NULL((void*)0));
167 TAILQ_INIT(new->in_rules)do { (new->in_rules)->tqh_first = ((void*)0); (new->
in_rules)->tqh_last = &(new->in_rules)->tqh_first
; } while (0);
168
169 ribs[id] = new;
170
171 log_debug("%s: %s -> %u", __func__, name, id);
172 return (new);
173}
174
175/*
176 * This function is only called when the FIB information of a RIB changed.
177 * It will flush the FIB if there was one previously and change the fibstate
178 * from RECONF_NONE (nothing to do) to either RECONF_RELOAD (reload the FIB)
179 * or RECONF_REINIT (rerun the route decision process for every element)
180 * depending on the new flags.
181 */
182void
183rib_update(struct rib *rib)
184{
185 /* flush fib first if there was one */
186 if ((rib->flags & (F_RIB_NOFIB0x0004 | F_RIB_NOEVALUATE0x0002)) == 0)
187 rde_send_kroute_flush(rib);
188
189 /* if no evaluate changes then a full reinit is needed */
190 if ((rib->flags & F_RIB_NOEVALUATE0x0002) !=
191 (rib->flags_tmp & F_RIB_NOEVALUATE0x0002))
192 rib->fibstate = RECONF_REINIT;
193
194 rib->flags = rib->flags_tmp;
195 rib->rtableid = rib->rtableid_tmp;
196
197 /* reload fib if there is no reinit pending and there will be a fib */
198 if (rib->fibstate != RECONF_REINIT &&
199 (rib->flags & (F_RIB_NOFIB0x0004 | F_RIB_NOEVALUATE0x0002)) == 0)
200 rib->fibstate = RECONF_RELOAD;
201}
202
203struct rib *
204rib_byid(u_int16_t id)
205{
206 if (id == RIB_NOTFOUND0xffff || id >= rib_size || ribs[id] == NULL((void*)0))
207 return NULL((void*)0);
208 return ribs[id];
209}
210
211u_int16_t
212rib_find(char *name)
213{
214 u_int16_t id;
215
216 /* no name returns the first Loc-RIB */
217 if (name == NULL((void*)0) || *name == '\0')
218 return RIB_LOC_START1;
219
220 for (id = 0; id < rib_size; id++) {
221 if (ribs[id] != NULL((void*)0) && !strcmp(ribs[id]->name, name))
222 return id;
223 }
224
225 return RIB_NOTFOUND0xffff;
226}
227
228void
229rib_free(struct rib *rib)
230{
231 struct rib_entry *re, *xre;
232 struct prefix *p;
233
234 rib_dump_abort(rib->id);
235
236 /*
237 * flush the rib, disable route evaluation and fib sync to speed up
238 * the prefix removal. Nothing depends on this data anymore.
239 */
240 if ((rib->flags & (F_RIB_NOFIB0x0004 | F_RIB_NOEVALUATE0x0002)) == 0)
7
←
Assuming the condition is false
→
8
←
Taking false branch
→
241 rde_send_kroute_flush(rib);
242 rib->flags |= F_RIB_NOEVALUATE0x0002 | F_RIB_NOFIB0x0004;
243
244 for (re = RB_MIN(rib_tree, rib_tree(rib))rib_tree_RB_MINMAX(rib_tree(rib), -1); re != NULL((void*)0); re = xre) {
9
←
Assuming 're' is not equal to NULL
→
10
←
Loop condition is true. Entering loop body
→
245 xre = RB_NEXT(rib_tree, rib_tree(rib), re)rib_tree_RB_NEXT(re);
246
247 /*
248 * Removing the prefixes is tricky because the last one
249 * will remove the rib_entry as well and because we do
250 * an empty check in prefix_destroy() it is not possible to
251 * use the default for loop.
252 */
253 while ((p = LIST_FIRST(&re->prefix_h)((&re->prefix_h)->lh_first))) {
11
←
Loop condition is true. Entering loop body
→
18
←
Loop condition is true. Entering loop body
→
254 struct rde_aspath *asp = prefix_aspath(p);
19
←
Use of memory after it is freed
255 if (asp && asp->pftableid)
12
←
Assuming 'asp' is null
→
256 rde_pftable_del(asp->pftableid, p);
257 prefix_destroy(p);
13
←
Calling 'prefix_destroy'
→
17
←
Returning; memory was released via 1st parameter
→
258 }
259 }
260 if (rib->id <= RIB_LOC_START1)
261 return; /* never remove the default ribs */
262 filterlist_free(rib->in_rules_tmp);
263 filterlist_free(rib->in_rules);
264 ribs[rib->id] = NULL((void*)0);
265 free(rib);
266}
267
268void
269rib_shutdown(void)
270{
271 struct rib *rib;
272 u_int16_t id;
273
274 for (id = 0; id < rib_size; id++) {
1
Assuming 'id' is < 'rib_size'
→
2
←
Loop condition is true. Entering loop body
→
275 rib = rib_byid(id);
276 if (rib
2.1
'rib' is not equal to NULL
 == NULL((void*)0))
3
←
Taking false branch
→
277 continue;
278 if (!RB_EMPTY(rib_tree(ribs[id]))((rib_tree(ribs[id]))->rbh_root == ((void*)0))) {
4
←
Assuming field 'rbh_root' is not equal to null
→
5
←
Taking true branch
→
279 log_warnx("%s: rib %s is not empty", __func__,
280 ribs[id]->name);
281 }
282 rib_free(ribs[id]);
6
←
Calling 'rib_free'
→
283 }
284 for (id = 0; id <= RIB_LOC_START1; id++) {
285 rib = rib_byid(id);
286 if (rib == NULL((void*)0))
287 continue;
288 filterlist_free(rib->in_rules_tmp);
289 filterlist_free(rib->in_rules);
290 ribs[id] = NULL((void*)0);
291 free(rib);
292 }
293 free(ribs);
294}
295
296struct rib_entry *
297rib_get(struct rib *rib, struct bgpd_addr *prefix, int prefixlen)
298{
299 struct rib_entry xre, *re;
300 struct pt_entry *pte;
301
302 pte = pt_fill(prefix, prefixlen);
303 memset(&xre, 0, sizeof(xre));
304 xre.prefix = pte;
305
306 re = RB_FIND(rib_tree, rib_tree(rib), &xre)rib_tree_RB_FIND(rib_tree(rib), &xre);
307 if (re && re->rib_id != rib->id)
308 fatalx("%s: Unexpected RIB %u != %u.", __func__,
309 re->rib_id, rib->id);
310 return re;
311}
312
313struct rib_entry *
314rib_match(struct rib *rib, struct bgpd_addr *addr)
315{
316 struct rib_entry *re;
317 int i;
318
319 switch (addr->aid) {
320 case AID_INET1:
321 case AID_VPN_IPv43:
322 for (i = 32; i >= 0; i--) {
323 re = rib_get(rib, addr, i);
324 if (re != NULL((void*)0))
325 return (re);
326 }
327 break;
328 case AID_INET62:
329 case AID_VPN_IPv64:
330 for (i = 128; i >= 0; i--) {
331 re = rib_get(rib, addr, i);
332 if (re != NULL((void*)0))
333 return (re);
334 }
335 break;
336 default:
337 fatalx("%s: unknown af", __func__);
338 }
339 return (NULL((void*)0));
340}
341
342
343struct rib_entry *
344rib_add(struct rib *rib, struct bgpd_addr *prefix, int prefixlen)
345{
346 struct pt_entry *pte;
347 struct rib_entry *re;
348
349 pte = pt_get(prefix, prefixlen);
350 if (pte == NULL((void*)0))
351 pte = pt_add(prefix, prefixlen);
352
353 if ((re = calloc(1, sizeof(*re))) == NULL((void*)0))
354 fatal("rib_add");
355
356 LIST_INIT(&re->prefix_h)do { ((&re->prefix_h)->lh_first) = ((void*)0); } while
(0);
357 re->prefix = pt_ref(pte);
358 re->rib_id = rib->id;
359
360 if (RB_INSERT(rib_tree, rib_tree(rib), re)rib_tree_RB_INSERT(rib_tree(rib), re) != NULL((void*)0)) {
361 log_warnx("rib_add: insert failed");
362 free(re);
363 return (NULL((void*)0));
364 }
365
366
367 rdemem.rib_cnt++;
368
369 return (re);
370}
371
372void
373rib_remove(struct rib_entry *re)
374{
375 if (!rib_empty(re))
376 fatalx("rib_remove: entry not empty");
377
378 if (re_is_locked(re))
379 /* entry is locked, don't free it. */
380 return;
381
382 pt_unref(re->prefix);
383
384 if (RB_REMOVE(rib_tree, rib_tree(re_rib(re)), re)rib_tree_RB_REMOVE(rib_tree(re_rib(re)), re) == NULL((void*)0))
385 log_warnx("rib_remove: remove failed.");
386
387 free(re);
388 rdemem.rib_cnt--;
389}
390
391int
392rib_empty(struct rib_entry *re)
393{
394 return LIST_EMPTY(&re->prefix_h)(((&re->prefix_h)->lh_first) == ((void*)0));
395}
396
397static struct rib_entry *
398rib_restart(struct rib_context *ctx)
399{
400 struct rib_entry *re;
401
402 re = re_unlock(ctx->ctx_re);
403
404 /* find first non empty element */
405 while (re && rib_empty(re))
406 re = RB_NEXT(rib_tree, unused, re)rib_tree_RB_NEXT(re);
407
408 /* free the previously locked rib element if empty */
409 if (rib_empty(ctx->ctx_re))
410 rib_remove(ctx->ctx_re);
411 ctx->ctx_re = NULL((void*)0);
412 return (re);
413}
414
415static void
416rib_dump_r(struct rib_context *ctx)
417{
418 struct rib_entry *re, *next;
419 struct rib *rib;
420 unsigned int i;
421
422 rib = rib_byid(ctx->ctx_id);
423 if (rib == NULL((void*)0))
424 fatalx("%s: rib id %u gone", __func__, ctx->ctx_id);
425
426 if (ctx->ctx_re == NULL((void*)0))
427 re = RB_MIN(rib_tree, rib_tree(rib))rib_tree_RB_MINMAX(rib_tree(rib), -1);
428 else
429 re = rib_restart(ctx);
430
431 for (i = 0; re != NULL((void*)0); re = next) {
432 next = RB_NEXT(rib_tree, unused, re)rib_tree_RB_NEXT(re);
433 if (re->rib_id != ctx->ctx_id)
434 fatalx("%s: Unexpected RIB %u != %u.", __func__,
435 re->rib_id, ctx->ctx_id);
436 if (ctx->ctx_aid != AID_UNSPEC0 &&
437 ctx->ctx_aid != re->prefix->aid)
438 continue;
439 if (ctx->ctx_count && i++ >= ctx->ctx_count &&
440 !re_is_locked(re)) {
441 /* store and lock last element */
442 ctx->ctx_re = re_lock(re);
443 return;
444 }
445 ctx->ctx_rib_call(re, ctx->ctx_arg);
446 }
447
448 if (ctx->ctx_done)
449 ctx->ctx_done(ctx->ctx_arg, ctx->ctx_aid);
450 LIST_REMOVE(ctx, entry)do { if ((ctx)->entry.le_next != ((void*)0)) (ctx)->entry
.le_next->entry.le_prev = (ctx)->entry.le_prev; *(ctx)->
entry.le_prev = (ctx)->entry.le_next; ; ; } while (0);
451 free(ctx);
452}
453
454int
455rib_dump_pending(void)
456{
457 struct rib_context *ctx;
458
459 /* return true if at least one context is not throttled */
460 LIST_FOREACH(ctx, &rib_dumps, entry)for((ctx) = ((&rib_dumps)->lh_first); (ctx)!= ((void*)
0); (ctx) = ((ctx)->entry.le_next)) {
461 if (ctx->ctx_throttle && ctx->ctx_throttle(ctx->ctx_arg))
462 continue;
463 return 1;
464 }
465 return 0;
466}
467
468void
469rib_dump_runner(void)
470{
471 struct rib_context *ctx, *next;
472
473 LIST_FOREACH_SAFE(ctx, &rib_dumps, entry, next)for ((ctx) = ((&rib_dumps)->lh_first); (ctx) &&
((next) = ((ctx)->entry.le_next), 1); (ctx) = (next)) {
474 if (ctx->ctx_throttle && ctx->ctx_throttle(ctx->ctx_arg))
475 continue;
476 if (ctx->ctx_rib_call != NULL((void*)0))
477 rib_dump_r(ctx);
478 else
479 prefix_dump_r(ctx);
480 }
481}
482
483static void
484rib_dump_abort(u_int16_t id)
485{
486 struct rib_context *ctx, *next;
487
488 LIST_FOREACH_SAFE(ctx, &rib_dumps, entry, next)for ((ctx) = ((&rib_dumps)->lh_first); (ctx) &&
((next) = ((ctx)->entry.le_next), 1); (ctx) = (next)) {
489 if (id != ctx->ctx_id)
490 continue;
491 if (ctx->ctx_done)
492 ctx->ctx_done(ctx->ctx_arg, ctx->ctx_aid);
493 if (ctx->ctx_re && rib_empty(re_unlock(ctx->ctx_re)))
494 rib_remove(ctx->ctx_re);
495 if (ctx->ctx_p && prefix_is_dead(prefix_unlock(ctx->ctx_p)))
496 prefix_adjout_destroy(ctx->ctx_p);
497 LIST_REMOVE(ctx, entry)do { if ((ctx)->entry.le_next != ((void*)0)) (ctx)->entry
.le_next->entry.le_prev = (ctx)->entry.le_prev; *(ctx)->
entry.le_prev = (ctx)->entry.le_next; ; ; } while (0);
498 free(ctx);
499 }
500}
501
502void
503rib_dump_terminate(void *arg)
504{
505 struct rib_context *ctx, *next;
506
507 LIST_FOREACH_SAFE(ctx, &rib_dumps, entry, next)for ((ctx) = ((&rib_dumps)->lh_first); (ctx) &&
((next) = ((ctx)->entry.le_next), 1); (ctx) = (next)) {
508 if (ctx->ctx_arg != arg)
509 continue;
510 if (ctx->ctx_done)
511 ctx->ctx_done(ctx->ctx_arg, ctx->ctx_aid);
512 if (ctx->ctx_re && rib_empty(re_unlock(ctx->ctx_re)))
513 rib_remove(ctx->ctx_re);
514 if (ctx->ctx_p && prefix_is_dead(prefix_unlock(ctx->ctx_p)))
515 prefix_adjout_destroy(ctx->ctx_p);
516 LIST_REMOVE(ctx, entry)do { if ((ctx)->entry.le_next != ((void*)0)) (ctx)->entry
.le_next->entry.le_prev = (ctx)->entry.le_prev; *(ctx)->
entry.le_prev = (ctx)->entry.le_next; ; ; } while (0);
517 free(ctx);
518 }
519}
520
521int
522rib_dump_new(u_int16_t id, u_int8_t aid, unsigned int count, void *arg,
523 void (*upcall)(struct rib_entry *, void *), void (*done)(void *, u_int8_t),
524 int (*throttle)(void *))
525{
526 struct rib_context *ctx;
527
528 if ((ctx = calloc(1, sizeof(*ctx))) == NULL((void*)0))
529 return -1;
530 ctx->ctx_id = id;
531 ctx->ctx_aid = aid;
532 ctx->ctx_count = count;
533 ctx->ctx_arg = arg;
534 ctx->ctx_rib_call = upcall;
535 ctx->ctx_done = done;
536 ctx->ctx_throttle = throttle;
537
538 LIST_INSERT_HEAD(&rib_dumps, ctx, entry)do { if (((ctx)->entry.le_next = (&rib_dumps)->lh_first
) != ((void*)0)) (&rib_dumps)->lh_first->entry.le_prev
= &(ctx)->entry.le_next; (&rib_dumps)->lh_first
= (ctx); (ctx)->entry.le_prev = &(&rib_dumps)->
lh_first; } while (0);
539
540 /* requested a sync traversal */
541 if (count == 0)
542 rib_dump_r(ctx);
543
544 return 0;
545}
546
547/* path specific functions */
548
549static struct rde_aspath *path_lookup(struct rde_aspath *);
550static u_int64_t path_hash(struct rde_aspath *);
551static void path_link(struct rde_aspath *);
552static void path_unlink(struct rde_aspath *);
553
554struct path_table {
555 struct aspath_head *path_hashtbl;
556 u_int64_t path_hashmask;
557} pathtable;
558
559SIPHASH_KEY pathtablekey;
560
561#define PATH_HASH(x)&pathtable.path_hashtbl[x & pathtable.path_hashmask] &pathtable.path_hashtbl[x & pathtable.path_hashmask]
562
563static inline struct rde_aspath *
564path_ref(struct rde_aspath *asp)
565{
566 if ((asp->flags & F_ATTR_LINKED0x20000) == 0)
567 fatalx("%s: unlinked object", __func__);
568 asp->refcnt++;
569 rdemem.path_refs++;
570
571 return asp;
572}
573
574static inline void
575path_unref(struct rde_aspath *asp)
576{
577 if (asp == NULL((void*)0))
578 return;
579 if ((asp->flags & F_ATTR_LINKED0x20000) == 0)
580 fatalx("%s: unlinked object", __func__);
581 asp->refcnt--;
582 rdemem.path_refs--;
583 if (asp->refcnt <= 0)
584 path_unlink(asp);
585}
586
587void
588path_init(u_int32_t hashsize)
589{
590 u_int32_t hs, i;
591
592 for (hs = 1; hs < hashsize; hs <<= 1)
593 ;
594 pathtable.path_hashtbl = calloc(hs, sizeof(*pathtable.path_hashtbl));
595 if (pathtable.path_hashtbl == NULL((void*)0))
596 fatal("path_init");
597
598 for (i = 0; i < hs; i++)
599 LIST_INIT(&pathtable.path_hashtbl[i])do { ((&pathtable.path_hashtbl[i])->lh_first) = ((void
*)0); } while (0);
600
601 pathtable.path_hashmask = hs - 1;
602 arc4random_buf(&pathtablekey, sizeof(pathtablekey));
603}
604
605void
606path_shutdown(void)
607{
608 u_int32_t i;
609
610 for (i = 0; i <= pathtable.path_hashmask; i++)
611 if (!LIST_EMPTY(&pathtable.path_hashtbl[i])(((&pathtable.path_hashtbl[i])->lh_first) == ((void*)0
)))
612 log_warnx("path_free: free non-free table");
613
614 free(pathtable.path_hashtbl);
615}
616
617void
618path_hash_stats(struct rde_hashstats *hs)
619{
620 struct rde_aspath *a;
621 u_int32_t i;
622 int64_t n;
623
624 memset(hs, 0, sizeof(*hs));
625 strlcpy(hs->name, "path hash", sizeof(hs->name));
626 hs->min = LLONG_MAX9223372036854775807LL;
627 hs->num = pathtable.path_hashmask + 1;
628
629 for (i = 0; i <= pathtable.path_hashmask; i++) {
630 n = 0;
631 LIST_FOREACH(a, &pathtable.path_hashtbl[i], path_l)for((a) = ((&pathtable.path_hashtbl[i])->lh_first); (a
)!= ((void*)0); (a) = ((a)->path_l.le_next))
632 n++;
633 if (n < hs->min)
634 hs->min = n;
635 if (n > hs->max)
636 hs->max = n;
637 hs->sum += n;
638 hs->sumq += n * n;
639 }
640}
641
642int
643path_compare(struct rde_aspath *a, struct rde_aspath *b)
644{
645 int r;
646
647 if (a == NULL((void*)0) && b == NULL((void*)0))
648 return (0);
649 else if (b == NULL((void*)0))
650 return (1);
651 else if (a == NULL((void*)0))
652 return (-1);
653 if ((a->flags & ~F_ATTR_LINKED0x20000) > (b->flags & ~F_ATTR_LINKED0x20000))
654 return (1);
655 if ((a->flags & ~F_ATTR_LINKED0x20000) < (b->flags & ~F_ATTR_LINKED0x20000))
656 return (-1);
657 if (a->origin > b->origin)
658 return (1);
659 if (a->origin < b->origin)
660 return (-1);
661 if (a->med > b->med)
662 return (1);
663 if (a->med < b->med)
664 return (-1);
665 if (a->lpref > b->lpref)
666 return (1);
667 if (a->lpref < b->lpref)
668 return (-1);
669 if (a->weight > b->weight)
670 return (1);
671 if (a->weight < b->weight)
672 return (-1);
673 if (a->rtlabelid > b->rtlabelid)
674 return (1);
675 if (a->rtlabelid < b->rtlabelid)
676 return (-1);
677 if (a->pftableid > b->pftableid)
678 return (1);
679 if (a->pftableid < b->pftableid)
680 return (-1);
681
682 r = aspath_compare(a->aspath, b->aspath);
683 if (r > 0)
684 return (1);
685 if (r < 0)
686 return (-1);
687
688 return (attr_compare(a, b));
689}
690
691static u_int64_t
692path_hash(struct rde_aspath *asp)
693{
694 SIPHASH_CTX ctx;
695 u_int64_t hash;
696
697 SipHash24_Init(&ctx, &pathtablekey)SipHash_Init((&ctx), (&pathtablekey));
698 SipHash24_Update(&ctx, &asp->aspath_hashstart,SipHash_Update((&ctx), 2, 4, (&asp->med), ((char *
)&asp->others_len - (char *)&asp->med))
699 (char *)&asp->aspath_hashend - (char *)&asp->aspath_hashstart)SipHash_Update((&ctx), 2, 4, (&asp->med), ((char *
)&asp->others_len - (char *)&asp->med));
700
701 if (asp->aspath)
702 SipHash24_Update(&ctx, asp->aspath->data, asp->aspath->len)SipHash_Update((&ctx), 2, 4, (asp->aspath->data), (
asp->aspath->len));
703
704 hash = attr_hash(asp);
705 SipHash24_Update(&ctx, &hash, sizeof(hash))SipHash_Update((&ctx), 2, 4, (&hash), (sizeof(hash)));
706
707 return (SipHash24_End(&ctx)SipHash_End((&ctx), 2, 4));
708}
709
710static struct rde_aspath *
711path_lookup(struct rde_aspath *aspath)
712{
713 struct aspath_head *head;
714 struct rde_aspath *asp;
715 u_int64_t hash;
716
717 hash = path_hash(aspath);
718 head = PATH_HASH(hash)&pathtable.path_hashtbl[hash & pathtable.path_hashmask
];
719
720 LIST_FOREACH(asp, head, path_l)for((asp) = ((head)->lh_first); (asp)!= ((void*)0); (asp) =
((asp)->path_l.le_next)) {
721 if (asp->hash == hash && path_compare(aspath, asp) == 0)
722 return (asp);
723 }
724 return (NULL((void*)0));
725}
726
727/*
728 * Link this aspath into the global hash table.
729 * The asp had to be alloced with path_get.
730 */
731static void
732path_link(struct rde_aspath *asp)
733{
734 struct aspath_head *head;
735
736 asp->hash = path_hash(asp);
737 head = PATH_HASH(asp->hash)&pathtable.path_hashtbl[asp->hash & pathtable.path_hashmask
];
738
739 LIST_INSERT_HEAD(head, asp, path_l)do { if (((asp)->path_l.le_next = (head)->lh_first) != (
(void*)0)) (head)->lh_first->path_l.le_prev = &(asp
)->path_l.le_next; (head)->lh_first = (asp); (asp)->
path_l.le_prev = &(head)->lh_first; } while (0);
740 asp->flags |= F_ATTR_LINKED0x20000;
741}
742
743/*
744 * This function can only be called when all prefix have been removed first.
745 * Normally this happens directly out of the prefix removal functions.
746 */
747static void
748path_unlink(struct rde_aspath *asp)
749{
750 if (asp == NULL((void*)0))
751 return;
752
753 /* make sure no reference is hold for this rde_aspath */
754 if (asp->refcnt != 0)
755 fatalx("%s: still holds references", __func__);
756
757 LIST_REMOVE(asp, path_l)do { if ((asp)->path_l.le_next != ((void*)0)) (asp)->path_l
.le_next->path_l.le_prev = (asp)->path_l.le_prev; *(asp
)->path_l.le_prev = (asp)->path_l.le_next; ; ; } while (
0);
758 asp->flags &= ~F_ATTR_LINKED0x20000;
759
760 path_put(asp);
761}
762
763/*
764 * Copy asp to a new UNLINKED aspath.
765 * On dst either path_get() or path_prep() had to be called before.
766 */
767struct rde_aspath *
768path_copy(struct rde_aspath *dst, const struct rde_aspath *src)
769{
770 dst->aspath = src->aspath;
771 if (dst->aspath != NULL((void*)0)) {
772 dst->aspath->refcnt++;
773 rdemem.aspath_refs++;
774 }
775 dst->hash = 0; /* not linked so no hash and no refcnt */
776 dst->refcnt = 0;
777 dst->flags = src->flags & ~F_ATTR_LINKED0x20000;
778
779 dst->med = src->med;
780 dst->lpref = src->lpref;
781 dst->weight = src->weight;
782 dst->rtlabelid = rtlabel_ref(src->rtlabelid);
783 dst->pftableid = pftable_ref(src->pftableid);
784 dst->origin = src->origin;
785
786 attr_copy(dst, src);
787
788 return (dst);
789}
790
791/* initialize or pepare an aspath for use */
792struct rde_aspath *
793path_prep(struct rde_aspath *asp)
794{
795 memset(asp, 0, sizeof(*asp));
796 asp->origin = ORIGIN_INCOMPLETE2;
797 asp->lpref = DEFAULT_LPREF100;
798
799 return (asp);
800}
801
802/* alloc and initialize new entry. May not fail. */
803struct rde_aspath *
804path_get(void)
805{
806 struct rde_aspath *asp;
807
808 asp = malloc(sizeof(*asp));
809 if (asp == NULL((void*)0))
810 fatal("path_get");
811 rdemem.path_cnt++;
812
813 return (path_prep(asp));
814}
815
816/* clean up an asp after use (frees all references to sub-objects) */
817void
818path_clean(struct rde_aspath *asp)
819{
820 if (asp->flags & F_ATTR_LINKED0x20000)
821 fatalx("%s: linked object", __func__);
822
823 rtlabel_unref(asp->rtlabelid);
824 pftable_unref(asp->pftableid);
825 aspath_put(asp->aspath);
826 attr_freeall(asp);
827}
828
829/* free an unlinked element */
830void
831path_put(struct rde_aspath *asp)
832{
833 if (asp == NULL((void*)0))
834 return;
835
836 path_clean(asp);
837
838 rdemem.path_cnt--;
839 free(asp);
840}
841
842/* prefix specific functions */
843
844static int prefix_add(struct bgpd_addr *, int, struct rib *,
845 struct rde_peer *, u_int32_t, struct rde_aspath *,
846 struct rde_community *, struct nexthop *,
847 u_int8_t, u_int8_t);
848static int prefix_move(struct prefix *, struct rde_peer *,
849 struct rde_aspath *, struct rde_community *,
850 struct nexthop *, u_int8_t, u_int8_t);
851
852static void prefix_link(struct prefix *, struct rib_entry *,
853 struct rde_peer *, u_int32_t, struct rde_aspath *,
854 struct rde_community *, struct nexthop *,
855 u_int8_t, u_int8_t);
856static void prefix_unlink(struct prefix *);
857
858static struct prefix *prefix_alloc(void);
859static void prefix_free(struct prefix *);
860
861/* RB tree comparison function */
862static inline int
863prefix_cmp(struct prefix *a, struct prefix *b)
864{
865 if (a->eor != b->eor)
866 return a->eor - b->eor;
867 /* if EOR marker no need to check the rest also a->eor == b->eor */
868 if (a->eor)
869 return 0;
870
871 if (a->aspath != b->aspath)
872 return (a->aspath > b->aspath ? 1 : -1);
873 if (a->communities != b->communities)
874 return (a->communities > b->communities ? 1 : -1);
875 if (a->nexthop != b->nexthop)
876 return (a->nexthop > b->nexthop ? 1 : -1);
877 if (a->nhflags != b->nhflags)
878 return (a->nhflags > b->nhflags ? 1 : -1);
879 /* XXX path_id ??? */
880 return pt_prefix_cmp(a->pt, b->pt);
881}
882
883static inline int
884prefix_index_cmp(struct prefix *a, struct prefix *b)
885{
886 /* XXX path_id ??? */
887 return pt_prefix_cmp(a->pt, b->pt);
888}
889
890RB_GENERATE(prefix_tree, prefix, entry.tree.update, prefix_cmp)void prefix_tree_RB_INSERT_COLOR(struct prefix_tree *head, struct
prefix *elm) { struct prefix *parent, *gparent, *tmp; while (
(parent = (elm)->entry.tree.update.rbe_parent) && (
parent)->entry.tree.update.rbe_color == 1) { gparent = (parent
)->entry.tree.update.rbe_parent; if (parent == (gparent)->
entry.tree.update.rbe_left) { tmp = (gparent)->entry.tree.
update.rbe_right; if (tmp && (tmp)->entry.tree.update
.rbe_color == 1) { (tmp)->entry.tree.update.rbe_color = 0;
do { (parent)->entry.tree.update.rbe_color = 0; (gparent)
->entry.tree.update.rbe_color = 1; } while (0); elm = gparent
; continue; } if ((parent)->entry.tree.update.rbe_right ==
elm) { do { (tmp) = (parent)->entry.tree.update.rbe_right
; if (((parent)->entry.tree.update.rbe_right = (tmp)->entry
.tree.update.rbe_left)) { ((tmp)->entry.tree.update.rbe_left
)->entry.tree.update.rbe_parent = (parent); } do {} while (
0); if (((tmp)->entry.tree.update.rbe_parent = (parent)->
entry.tree.update.rbe_parent)) { if ((parent) == ((parent)->
entry.tree.update.rbe_parent)->entry.tree.update.rbe_left)
((parent)->entry.tree.update.rbe_parent)->entry.tree.update
.rbe_left = (tmp); else ((parent)->entry.tree.update.rbe_parent
)->entry.tree.update.rbe_right = (tmp); } else (head)->
rbh_root = (tmp); (tmp)->entry.tree.update.rbe_left = (parent
); (parent)->entry.tree.update.rbe_parent = (tmp); do {} while
(0); if (((tmp)->entry.tree.update.rbe_parent)) do {} while
(0); } while (0); tmp = parent; parent = elm; elm = tmp; } do
{ (parent)->entry.tree.update.rbe_color = 0; (gparent)->
entry.tree.update.rbe_color = 1; } while (0); do { (tmp) = (gparent
)->entry.tree.update.rbe_left; if (((gparent)->entry.tree
.update.rbe_left = (tmp)->entry.tree.update.rbe_right)) { (
(tmp)->entry.tree.update.rbe_right)->entry.tree.update.
rbe_parent = (gparent); } do {} while (0); if (((tmp)->entry
.tree.update.rbe_parent = (gparent)->entry.tree.update.rbe_parent
)) { if ((gparent) == ((gparent)->entry.tree.update.rbe_parent
)->entry.tree.update.rbe_left) ((gparent)->entry.tree.update
.rbe_parent)->entry.tree.update.rbe_left = (tmp); else ((gparent
)->entry.tree.update.rbe_parent)->entry.tree.update.rbe_right
= (tmp); } else (head)->rbh_root = (tmp); (tmp)->entry
.tree.update.rbe_right = (gparent); (gparent)->entry.tree.
update.rbe_parent = (tmp); do {} while (0); if (((tmp)->entry
.tree.update.rbe_parent)) do {} while (0); } while (0); } else
{ tmp = (gparent)->entry.tree.update.rbe_left; if (tmp &&
(tmp)->entry.tree.update.rbe_color == 1) { (tmp)->entry
.tree.update.rbe_color = 0; do { (parent)->entry.tree.update
.rbe_color = 0; (gparent)->entry.tree.update.rbe_color = 1
; } while (0); elm = gparent; continue; } if ((parent)->entry
.tree.update.rbe_left == elm) { do { (tmp) = (parent)->entry
.tree.update.rbe_left; if (((parent)->entry.tree.update.rbe_left
= (tmp)->entry.tree.update.rbe_right)) { ((tmp)->entry
.tree.update.rbe_right)->entry.tree.update.rbe_parent = (parent
); } do {} while (0); if (((tmp)->entry.tree.update.rbe_parent
= (parent)->entry.tree.update.rbe_parent)) { if ((parent)
== ((parent)->entry.tree.update.rbe_parent)->entry.tree
.update.rbe_left) ((parent)->entry.tree.update.rbe_parent)
->entry.tree.update.rbe_left = (tmp); else ((parent)->entry
.tree.update.rbe_parent)->entry.tree.update.rbe_right = (tmp
); } else (head)->rbh_root = (tmp); (tmp)->entry.tree.update
.rbe_right = (parent); (parent)->entry.tree.update.rbe_parent
= (tmp); do {} while (0); if (((tmp)->entry.tree.update.rbe_parent
)) do {} while (0); } while (0); tmp = parent; parent = elm; elm
= tmp; } do { (parent)->entry.tree.update.rbe_color = 0; (
gparent)->entry.tree.update.rbe_color = 1; } while (0); do
{ (tmp) = (gparent)->entry.tree.update.rbe_right; if (((gparent
)->entry.tree.update.rbe_right = (tmp)->entry.tree.update
.rbe_left)) { ((tmp)->entry.tree.update.rbe_left)->entry
.tree.update.rbe_parent = (gparent); } do {} while (0); if ((
(tmp)->entry.tree.update.rbe_parent = (gparent)->entry.
tree.update.rbe_parent)) { if ((gparent) == ((gparent)->entry
.tree.update.rbe_parent)->entry.tree.update.rbe_left) ((gparent
)->entry.tree.update.rbe_parent)->entry.tree.update.rbe_left
= (tmp); else ((gparent)->entry.tree.update.rbe_parent)->
entry.tree.update.rbe_right = (tmp); } else (head)->rbh_root
= (tmp); (tmp)->entry.tree.update.rbe_left = (gparent); (
gparent)->entry.tree.update.rbe_parent = (tmp); do {} while
(0); if (((tmp)->entry.tree.update.rbe_parent)) do {} while
(0); } while (0); } } (head->rbh_root)->entry.tree.update
.rbe_color = 0; } void prefix_tree_RB_REMOVE_COLOR(struct prefix_tree
*head, struct prefix *parent, struct prefix *elm) { struct prefix
*tmp; while ((elm == ((void*)0) || (elm)->entry.tree.update
.rbe_color == 0) && elm != (head)->rbh_root) { if (
(parent)->entry.tree.update.rbe_left == elm) { tmp = (parent
)->entry.tree.update.rbe_right; if ((tmp)->entry.tree.update
.rbe_color == 1) { do { (tmp)->entry.tree.update.rbe_color
= 0; (parent)->entry.tree.update.rbe_color = 1; } while (
0); do { (tmp) = (parent)->entry.tree.update.rbe_right; if
(((parent)->entry.tree.update.rbe_right = (tmp)->entry
.tree.update.rbe_left)) { ((tmp)->entry.tree.update.rbe_left
)->entry.tree.update.rbe_parent = (parent); } do {} while (
0); if (((tmp)->entry.tree.update.rbe_parent = (parent)->
entry.tree.update.rbe_parent)) { if ((parent) == ((parent)->
entry.tree.update.rbe_parent)->entry.tree.update.rbe_left)
((parent)->entry.tree.update.rbe_parent)->entry.tree.update
.rbe_left = (tmp); else ((parent)->entry.tree.update.rbe_parent
)->entry.tree.update.rbe_right = (tmp); } else (head)->
rbh_root = (tmp); (tmp)->entry.tree.update.rbe_left = (parent
); (parent)->entry.tree.update.rbe_parent = (tmp); do {} while
(0); if (((tmp)->entry.tree.update.rbe_parent)) do {} while
(0); } while (0); tmp = (parent)->entry.tree.update.rbe_right
; } if (((tmp)->entry.tree.update.rbe_left == ((void*)0) ||
((tmp)->entry.tree.update.rbe_left)->entry.tree.update
.rbe_color == 0) && ((tmp)->entry.tree.update.rbe_right
== ((void*)0) || ((tmp)->entry.tree.update.rbe_right)->
entry.tree.update.rbe_color == 0)) { (tmp)->entry.tree.update
.rbe_color = 1; elm = parent; parent = (elm)->entry.tree.update
.rbe_parent; } else { if ((tmp)->entry.tree.update.rbe_right
== ((void*)0) || ((tmp)->entry.tree.update.rbe_right)->
entry.tree.update.rbe_color == 0) { struct prefix *oleft; if (
(oleft = (tmp)->entry.tree.update.rbe_left)) (oleft)->entry
.tree.update.rbe_color = 0; (tmp)->entry.tree.update.rbe_color
= 1; do { (oleft) = (tmp)->entry.tree.update.rbe_left; if
(((tmp)->entry.tree.update.rbe_left = (oleft)->entry.tree
.update.rbe_right)) { ((oleft)->entry.tree.update.rbe_right
)->entry.tree.update.rbe_parent = (tmp); } do {} while (0)
; if (((oleft)->entry.tree.update.rbe_parent = (tmp)->entry
.tree.update.rbe_parent)) { if ((tmp) == ((tmp)->entry.tree
.update.rbe_parent)->entry.tree.update.rbe_left) ((tmp)->
entry.tree.update.rbe_parent)->entry.tree.update.rbe_left =
(oleft); else ((tmp)->entry.tree.update.rbe_parent)->entry
.tree.update.rbe_right = (oleft); } else (head)->rbh_root =
(oleft); (oleft)->entry.tree.update.rbe_right = (tmp); (tmp
)->entry.tree.update.rbe_parent = (oleft); do {} while (0)
; if (((oleft)->entry.tree.update.rbe_parent)) do {} while
(0); } while (0); tmp = (parent)->entry.tree.update.rbe_right
; } (tmp)->entry.tree.update.rbe_color = (parent)->entry
.tree.update.rbe_color; (parent)->entry.tree.update.rbe_color
= 0; if ((tmp)->entry.tree.update.rbe_right) ((tmp)->entry
.tree.update.rbe_right)->entry.tree.update.rbe_color = 0; do
{ (tmp) = (parent)->entry.tree.update.rbe_right; if (((parent
)->entry.tree.update.rbe_right = (tmp)->entry.tree.update
.rbe_left)) { ((tmp)->entry.tree.update.rbe_left)->entry
.tree.update.rbe_parent = (parent); } do {} while (0); if (((
tmp)->entry.tree.update.rbe_parent = (parent)->entry.tree
.update.rbe_parent)) { if ((parent) == ((parent)->entry.tree
.update.rbe_parent)->entry.tree.update.rbe_left) ((parent)
->entry.tree.update.rbe_parent)->entry.tree.update.rbe_left
= (tmp); else ((parent)->entry.tree.update.rbe_parent)->
entry.tree.update.rbe_right = (tmp); } else (head)->rbh_root
= (tmp); (tmp)->entry.tree.update.rbe_left = (parent); (parent
)->entry.tree.update.rbe_parent = (tmp); do {} while (0); if
(((tmp)->entry.tree.update.rbe_parent)) do {} while (0); }
while (0); elm = (head)->rbh_root; break; } } else { tmp =
(parent)->entry.tree.update.rbe_left; if ((tmp)->entry
.tree.update.rbe_color == 1) { do { (tmp)->entry.tree.update
.rbe_color = 0; (parent)->entry.tree.update.rbe_color = 1;
} while (0); do { (tmp) = (parent)->entry.tree.update.rbe_left
; if (((parent)->entry.tree.update.rbe_left = (tmp)->entry
.tree.update.rbe_right)) { ((tmp)->entry.tree.update.rbe_right
)->entry.tree.update.rbe_parent = (parent); } do {} while (
0); if (((tmp)->entry.tree.update.rbe_parent = (parent)->
entry.tree.update.rbe_parent)) { if ((parent) == ((parent)->
entry.tree.update.rbe_parent)->entry.tree.update.rbe_left)
((parent)->entry.tree.update.rbe_parent)->entry.tree.update
.rbe_left = (tmp); else ((parent)->entry.tree.update.rbe_parent
)->entry.tree.update.rbe_right = (tmp); } else (head)->
rbh_root = (tmp); (tmp)->entry.tree.update.rbe_right = (parent
); (parent)->entry.tree.update.rbe_parent = (tmp); do {} while
(0); if (((tmp)->entry.tree.update.rbe_parent)) do {} while
(0); } while (0); tmp = (parent)->entry.tree.update.rbe_left
; } if (((tmp)->entry.tree.update.rbe_left == ((void*)0) ||
((tmp)->entry.tree.update.rbe_left)->entry.tree.update
.rbe_color == 0) && ((tmp)->entry.tree.update.rbe_right
== ((void*)0) || ((tmp)->entry.tree.update.rbe_right)->
entry.tree.update.rbe_color == 0)) { (tmp)->entry.tree.update
.rbe_color = 1; elm = parent; parent = (elm)->entry.tree.update
.rbe_parent; } else { if ((tmp)->entry.tree.update.rbe_left
== ((void*)0) || ((tmp)->entry.tree.update.rbe_left)->
entry.tree.update.rbe_color == 0) { struct prefix *oright; if
((oright = (tmp)->entry.tree.update.rbe_right)) (oright)->
entry.tree.update.rbe_color = 0; (tmp)->entry.tree.update.
rbe_color = 1; do { (oright) = (tmp)->entry.tree.update.rbe_right
; if (((tmp)->entry.tree.update.rbe_right = (oright)->entry
.tree.update.rbe_left)) { ((oright)->entry.tree.update.rbe_left
)->entry.tree.update.rbe_parent = (tmp); } do {} while (0)
; if (((oright)->entry.tree.update.rbe_parent = (tmp)->
entry.tree.update.rbe_parent)) { if ((tmp) == ((tmp)->entry
.tree.update.rbe_parent)->entry.tree.update.rbe_left) ((tmp
)->entry.tree.update.rbe_parent)->entry.tree.update.rbe_left
= (oright); else ((tmp)->entry.tree.update.rbe_parent)->
entry.tree.update.rbe_right = (oright); } else (head)->rbh_root
= (oright); (oright)->entry.tree.update.rbe_left = (tmp);
(tmp)->entry.tree.update.rbe_parent = (oright); do {} while
(0); if (((oright)->entry.tree.update.rbe_parent)) do {} while
(0); } while (0); tmp = (parent)->entry.tree.update.rbe_left
; } (tmp)->entry.tree.update.rbe_color = (parent)->entry
.tree.update.rbe_color; (parent)->entry.tree.update.rbe_color
= 0; if ((tmp)->entry.tree.update.rbe_left) ((tmp)->entry
.tree.update.rbe_left)->entry.tree.update.rbe_color = 0; do
{ (tmp) = (parent)->entry.tree.update.rbe_left; if (((parent
)->entry.tree.update.rbe_left = (tmp)->entry.tree.update
.rbe_right)) { ((tmp)->entry.tree.update.rbe_right)->entry
.tree.update.rbe_parent = (parent); } do {} while (0); if (((
tmp)->entry.tree.update.rbe_parent = (parent)->entry.tree
.update.rbe_parent)) { if ((parent) == ((parent)->entry.tree
.update.rbe_parent)->entry.tree.update.rbe_left) ((parent)
->entry.tree.update.rbe_parent)->entry.tree.update.rbe_left
= (tmp); else ((parent)->entry.tree.update.rbe_parent)->
entry.tree.update.rbe_right = (tmp); } else (head)->rbh_root
= (tmp); (tmp)->entry.tree.update.rbe_right = (parent); (
parent)->entry.tree.update.rbe_parent = (tmp); do {} while
(0); if (((tmp)->entry.tree.update.rbe_parent)) do {} while
(0); } while (0); elm = (head)->rbh_root; break; } } } if
(elm) (elm)->entry.tree.update.rbe_color = 0; } struct prefix
* prefix_tree_RB_REMOVE(struct prefix_tree *head, struct prefix
*elm) { struct prefix *child, *parent, *old = elm; int color
; if ((elm)->entry.tree.update.rbe_left == ((void*)0)) child
= (elm)->entry.tree.update.rbe_right; else if ((elm)->
entry.tree.update.rbe_right == ((void*)0)) child = (elm)->
entry.tree.update.rbe_left; else { struct prefix *left; elm =
(elm)->entry.tree.update.rbe_right; while ((left = (elm)->
entry.tree.update.rbe_left)) elm = left; child = (elm)->entry
.tree.update.rbe_right; parent = (elm)->entry.tree.update.
rbe_parent; color = (elm)->entry.tree.update.rbe_color; if
(child) (child)->entry.tree.update.rbe_parent = parent; if
(parent) { if ((parent)->entry.tree.update.rbe_left == elm
) (parent)->entry.tree.update.rbe_left = child; else (parent
)->entry.tree.update.rbe_right = child; do {} while (0); }
else (head)->rbh_root = child; if ((elm)->entry.tree.update
.rbe_parent == old) parent = elm; (elm)->entry.tree.update
= (old)->entry.tree.update; if ((old)->entry.tree.update
.rbe_parent) { if (((old)->entry.tree.update.rbe_parent)->
entry.tree.update.rbe_left == old) ((old)->entry.tree.update
.rbe_parent)->entry.tree.update.rbe_left = elm; else ((old
)->entry.tree.update.rbe_parent)->entry.tree.update.rbe_right
= elm; do {} while (0); } else (head)->rbh_root = elm; ((
old)->entry.tree.update.rbe_left)->entry.tree.update.rbe_parent
= elm; if ((old)->entry.tree.update.rbe_right) ((old)->
entry.tree.update.rbe_right)->entry.tree.update.rbe_parent
= elm; if (parent) { left = parent; do { do {} while (0); } while
((left = (left)->entry.tree.update.rbe_parent)); } goto color
; } parent = (elm)->entry.tree.update.rbe_parent; color = (
elm)->entry.tree.update.rbe_color; if (child) (child)->
entry.tree.update.rbe_parent = parent; if (parent) { if ((parent
)->entry.tree.update.rbe_left == elm) (parent)->entry.tree
.update.rbe_left = child; else (parent)->entry.tree.update
.rbe_right = child; do {} while (0); } else (head)->rbh_root
= child; color: if (color == 0) prefix_tree_RB_REMOVE_COLOR(
head, parent, child); return (old); } struct prefix * prefix_tree_RB_INSERT
(struct prefix_tree *head, struct prefix *elm) { struct prefix
*tmp; struct prefix *parent = ((void*)0); int comp = 0; tmp =
(head)->rbh_root; while (tmp) { parent = tmp; comp = (prefix_cmp
)(elm, parent); if (comp < 0) tmp = (tmp)->entry.tree.update
.rbe_left; else if (comp > 0) tmp = (tmp)->entry.tree.update
.rbe_right; else return (tmp); } do { (elm)->entry.tree.update
.rbe_parent = parent; (elm)->entry.tree.update.rbe_left = (
elm)->entry.tree.update.rbe_right = ((void*)0); (elm)->
entry.tree.update.rbe_color = 1; } while (0); if (parent != (
(void*)0)) { if (comp < 0) (parent)->entry.tree.update.
rbe_left = elm; else (parent)->entry.tree.update.rbe_right
= elm; do {} while (0); } else (head)->rbh_root = elm; prefix_tree_RB_INSERT_COLOR
(head, elm); return (((void*)0)); } struct prefix * prefix_tree_RB_FIND
(struct prefix_tree *head, struct prefix *elm) { struct prefix
*tmp = (head)->rbh_root; int comp; while (tmp) { comp = prefix_cmp
(elm, tmp); if (comp < 0) tmp = (tmp)->entry.tree.update
.rbe_left; else if (comp > 0) tmp = (tmp)->entry.tree.update
.rbe_right; else return (tmp); } return (((void*)0)); } struct
prefix * prefix_tree_RB_NFIND(struct prefix_tree *head, struct
prefix *elm) { struct prefix *tmp = (head)->rbh_root; struct
prefix *res = ((void*)0); int comp; while (tmp) { comp = prefix_cmp
(elm, tmp); if (comp < 0) { res = tmp; tmp = (tmp)->entry
.tree.update.rbe_left; } else if (comp > 0) tmp = (tmp)->
entry.tree.update.rbe_right; else return (tmp); } return (res
); } struct prefix * prefix_tree_RB_NEXT(struct prefix *elm) {
if ((elm)->entry.tree.update.rbe_right) { elm = (elm)->
entry.tree.update.rbe_right; while ((elm)->entry.tree.update
.rbe_left) elm = (elm)->entry.tree.update.rbe_left; } else
{ if ((elm)->entry.tree.update.rbe_parent && (elm
== ((elm)->entry.tree.update.rbe_parent)->entry.tree.update
.rbe_left)) elm = (elm)->entry.tree.update.rbe_parent; else
{ while ((elm)->entry.tree.update.rbe_parent && (
elm == ((elm)->entry.tree.update.rbe_parent)->entry.tree
.update.rbe_right)) elm = (elm)->entry.tree.update.rbe_parent
; elm = (elm)->entry.tree.update.rbe_parent; } } return (elm
); } struct prefix * prefix_tree_RB_PREV(struct prefix *elm) {
if ((elm)->entry.tree.update.rbe_left) { elm = (elm)->
entry.tree.update.rbe_left; while ((elm)->entry.tree.update
.rbe_right) elm = (elm)->entry.tree.update.rbe_right; } else
{ if ((elm)->entry.tree.update.rbe_parent && (elm
== ((elm)->entry.tree.update.rbe_parent)->entry.tree.update
.rbe_right)) elm = (elm)->entry.tree.update.rbe_parent; else
{ while ((elm)->entry.tree.update.rbe_parent && (
elm == ((elm)->entry.tree.update.rbe_parent)->entry.tree
.update.rbe_left)) elm = (elm)->entry.tree.update.rbe_parent
; elm = (elm)->entry.tree.update.rbe_parent; } } return (elm
); } struct prefix * prefix_tree_RB_MINMAX(struct prefix_tree
*head, int val) { struct prefix *tmp = (head)->rbh_root; struct
prefix *parent = ((void*)0); while (tmp) { parent = tmp; if (
val < 0) tmp = (tmp)->entry.tree.update.rbe_left; else tmp
= (tmp)->entry.tree.update.rbe_right; } return (parent); }
891RB_GENERATE_STATIC(prefix_index, prefix, entry.tree.index, prefix_index_cmp)__attribute__((__unused__)) static void prefix_index_RB_INSERT_COLOR
(struct prefix_index *head, struct prefix *elm) { struct prefix
*parent, *gparent, *tmp; while ((parent = (elm)->entry.tree
.index.rbe_parent) && (parent)->entry.tree.index.rbe_color
== 1) { gparent = (parent)->entry.tree.index.rbe_parent; if
(parent == (gparent)->entry.tree.index.rbe_left) { tmp = (
gparent)->entry.tree.index.rbe_right; if (tmp && (
tmp)->entry.tree.index.rbe_color == 1) { (tmp)->entry.tree
.index.rbe_color = 0; do { (parent)->entry.tree.index.rbe_color
= 0; (gparent)->entry.tree.index.rbe_color = 1; } while (
0); elm = gparent; continue; } if ((parent)->entry.tree.index
.rbe_right == elm) { do { (tmp) = (parent)->entry.tree.index
.rbe_right; if (((parent)->entry.tree.index.rbe_right = (tmp
)->entry.tree.index.rbe_left)) { ((tmp)->entry.tree.index
.rbe_left)->entry.tree.index.rbe_parent = (parent); } do {
} while (0); if (((tmp)->entry.tree.index.rbe_parent = (parent
)->entry.tree.index.rbe_parent)) { if ((parent) == ((parent
)->entry.tree.index.rbe_parent)->entry.tree.index.rbe_left
) ((parent)->entry.tree.index.rbe_parent)->entry.tree.index
.rbe_left = (tmp); else ((parent)->entry.tree.index.rbe_parent
)->entry.tree.index.rbe_right = (tmp); } else (head)->rbh_root
= (tmp); (tmp)->entry.tree.index.rbe_left = (parent); (parent
)->entry.tree.index.rbe_parent = (tmp); do {} while (0); if
(((tmp)->entry.tree.index.rbe_parent)) do {} while (0); }
while (0); tmp = parent; parent = elm; elm = tmp; } do { (parent
)->entry.tree.index.rbe_color = 0; (gparent)->entry.tree
.index.rbe_color = 1; } while (0); do { (tmp) = (gparent)->
entry.tree.index.rbe_left; if (((gparent)->entry.tree.index
.rbe_left = (tmp)->entry.tree.index.rbe_right)) { ((tmp)->
entry.tree.index.rbe_right)->entry.tree.index.rbe_parent =
(gparent); } do {} while (0); if (((tmp)->entry.tree.index
.rbe_parent = (gparent)->entry.tree.index.rbe_parent)) { if
((gparent) == ((gparent)->entry.tree.index.rbe_parent)->
entry.tree.index.rbe_left) ((gparent)->entry.tree.index.rbe_parent
)->entry.tree.index.rbe_left = (tmp); else ((gparent)->
entry.tree.index.rbe_parent)->entry.tree.index.rbe_right =
(tmp); } else (head)->rbh_root = (tmp); (tmp)->entry.tree
.index.rbe_right = (gparent); (gparent)->entry.tree.index.
rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.tree
.index.rbe_parent)) do {} while (0); } while (0); } else { tmp
= (gparent)->entry.tree.index.rbe_left; if (tmp &&
(tmp)->entry.tree.index.rbe_color == 1) { (tmp)->entry
.tree.index.rbe_color = 0; do { (parent)->entry.tree.index
.rbe_color = 0; (gparent)->entry.tree.index.rbe_color = 1;
} while (0); elm = gparent; continue; } if ((parent)->entry
.tree.index.rbe_left == elm) { do { (tmp) = (parent)->entry
.tree.index.rbe_left; if (((parent)->entry.tree.index.rbe_left
= (tmp)->entry.tree.index.rbe_right)) { ((tmp)->entry.
tree.index.rbe_right)->entry.tree.index.rbe_parent = (parent
); } do {} while (0); if (((tmp)->entry.tree.index.rbe_parent
= (parent)->entry.tree.index.rbe_parent)) { if ((parent) ==
((parent)->entry.tree.index.rbe_parent)->entry.tree.index
.rbe_left) ((parent)->entry.tree.index.rbe_parent)->entry
.tree.index.rbe_left = (tmp); else ((parent)->entry.tree.index
.rbe_parent)->entry.tree.index.rbe_right = (tmp); } else (
head)->rbh_root = (tmp); (tmp)->entry.tree.index.rbe_right
= (parent); (parent)->entry.tree.index.rbe_parent = (tmp)
; do {} while (0); if (((tmp)->entry.tree.index.rbe_parent
)) do {} while (0); } while (0); tmp = parent; parent = elm; elm
= tmp; } do { (parent)->entry.tree.index.rbe_color = 0; (
gparent)->entry.tree.index.rbe_color = 1; } while (0); do {
(tmp) = (gparent)->entry.tree.index.rbe_right; if (((gparent
)->entry.tree.index.rbe_right = (tmp)->entry.tree.index
.rbe_left)) { ((tmp)->entry.tree.index.rbe_left)->entry
.tree.index.rbe_parent = (gparent); } do {} while (0); if (((
tmp)->entry.tree.index.rbe_parent = (gparent)->entry.tree
.index.rbe_parent)) { if ((gparent) == ((gparent)->entry.tree
.index.rbe_parent)->entry.tree.index.rbe_left) ((gparent)->
entry.tree.index.rbe_parent)->entry.tree.index.rbe_left = (
tmp); else ((gparent)->entry.tree.index.rbe_parent)->entry
.tree.index.rbe_right = (tmp); } else (head)->rbh_root = (
tmp); (tmp)->entry.tree.index.rbe_left = (gparent); (gparent
)->entry.tree.index.rbe_parent = (tmp); do {} while (0); if
(((tmp)->entry.tree.index.rbe_parent)) do {} while (0); }
while (0); } } (head->rbh_root)->entry.tree.index.rbe_color
= 0; } __attribute__((__unused__)) static void prefix_index_RB_REMOVE_COLOR
(struct prefix_index *head, struct prefix *parent, struct prefix
*elm) { struct prefix *tmp; while ((elm == ((void*)0) || (elm
)->entry.tree.index.rbe_color == 0) && elm != (head
)->rbh_root) { if ((parent)->entry.tree.index.rbe_left ==
elm) { tmp = (parent)->entry.tree.index.rbe_right; if ((tmp
)->entry.tree.index.rbe_color == 1) { do { (tmp)->entry
.tree.index.rbe_color = 0; (parent)->entry.tree.index.rbe_color
= 1; } while (0); do { (tmp) = (parent)->entry.tree.index
.rbe_right; if (((parent)->entry.tree.index.rbe_right = (tmp
)->entry.tree.index.rbe_left)) { ((tmp)->entry.tree.index
.rbe_left)->entry.tree.index.rbe_parent = (parent); } do {
} while (0); if (((tmp)->entry.tree.index.rbe_parent = (parent
)->entry.tree.index.rbe_parent)) { if ((parent) == ((parent
)->entry.tree.index.rbe_parent)->entry.tree.index.rbe_left
) ((parent)->entry.tree.index.rbe_parent)->entry.tree.index
.rbe_left = (tmp); else ((parent)->entry.tree.index.rbe_parent
)->entry.tree.index.rbe_right = (tmp); } else (head)->rbh_root
= (tmp); (tmp)->entry.tree.index.rbe_left = (parent); (parent
)->entry.tree.index.rbe_parent = (tmp); do {} while (0); if
(((tmp)->entry.tree.index.rbe_parent)) do {} while (0); }
while (0); tmp = (parent)->entry.tree.index.rbe_right; } if
(((tmp)->entry.tree.index.rbe_left == ((void*)0) || ((tmp
)->entry.tree.index.rbe_left)->entry.tree.index.rbe_color
== 0) && ((tmp)->entry.tree.index.rbe_right == ((
void*)0) || ((tmp)->entry.tree.index.rbe_right)->entry.
tree.index.rbe_color == 0)) { (tmp)->entry.tree.index.rbe_color
= 1; elm = parent; parent = (elm)->entry.tree.index.rbe_parent
; } else { if ((tmp)->entry.tree.index.rbe_right == ((void
*)0) || ((tmp)->entry.tree.index.rbe_right)->entry.tree
.index.rbe_color == 0) { struct prefix *oleft; if ((oleft = (
tmp)->entry.tree.index.rbe_left)) (oleft)->entry.tree.index
.rbe_color = 0; (tmp)->entry.tree.index.rbe_color = 1; do {
(oleft) = (tmp)->entry.tree.index.rbe_left; if (((tmp)->
entry.tree.index.rbe_left = (oleft)->entry.tree.index.rbe_right
)) { ((oleft)->entry.tree.index.rbe_right)->entry.tree.
index.rbe_parent = (tmp); } do {} while (0); if (((oleft)->
entry.tree.index.rbe_parent = (tmp)->entry.tree.index.rbe_parent
)) { if ((tmp) == ((tmp)->entry.tree.index.rbe_parent)->
entry.tree.index.rbe_left) ((tmp)->entry.tree.index.rbe_parent
)->entry.tree.index.rbe_left = (oleft); else ((tmp)->entry
.tree.index.rbe_parent)->entry.tree.index.rbe_right = (oleft
); } else (head)->rbh_root = (oleft); (oleft)->entry.tree
.index.rbe_right = (tmp); (tmp)->entry.tree.index.rbe_parent
= (oleft); do {} while (0); if (((oleft)->entry.tree.index
.rbe_parent)) do {} while (0); } while (0); tmp = (parent)->
entry.tree.index.rbe_right; } (tmp)->entry.tree.index.rbe_color
= (parent)->entry.tree.index.rbe_color; (parent)->entry
.tree.index.rbe_color = 0; if ((tmp)->entry.tree.index.rbe_right
) ((tmp)->entry.tree.index.rbe_right)->entry.tree.index
.rbe_color = 0; do { (tmp) = (parent)->entry.tree.index.rbe_right
; if (((parent)->entry.tree.index.rbe_right = (tmp)->entry
.tree.index.rbe_left)) { ((tmp)->entry.tree.index.rbe_left
)->entry.tree.index.rbe_parent = (parent); } do {} while (
0); if (((tmp)->entry.tree.index.rbe_parent = (parent)->
entry.tree.index.rbe_parent)) { if ((parent) == ((parent)->
entry.tree.index.rbe_parent)->entry.tree.index.rbe_left) (
(parent)->entry.tree.index.rbe_parent)->entry.tree.index
.rbe_left = (tmp); else ((parent)->entry.tree.index.rbe_parent
)->entry.tree.index.rbe_right = (tmp); } else (head)->rbh_root
= (tmp); (tmp)->entry.tree.index.rbe_left = (parent); (parent
)->entry.tree.index.rbe_parent = (tmp); do {} while (0); if
(((tmp)->entry.tree.index.rbe_parent)) do {} while (0); }
while (0); elm = (head)->rbh_root; break; } } else { tmp =
(parent)->entry.tree.index.rbe_left; if ((tmp)->entry.
tree.index.rbe_color == 1) { do { (tmp)->entry.tree.index.
rbe_color = 0; (parent)->entry.tree.index.rbe_color = 1; }
while (0); do { (tmp) = (parent)->entry.tree.index.rbe_left
; if (((parent)->entry.tree.index.rbe_left = (tmp)->entry
.tree.index.rbe_right)) { ((tmp)->entry.tree.index.rbe_right
)->entry.tree.index.rbe_parent = (parent); } do {} while (
0); if (((tmp)->entry.tree.index.rbe_parent = (parent)->
entry.tree.index.rbe_parent)) { if ((parent) == ((parent)->
entry.tree.index.rbe_parent)->entry.tree.index.rbe_left) (
(parent)->entry.tree.index.rbe_parent)->entry.tree.index
.rbe_left = (tmp); else ((parent)->entry.tree.index.rbe_parent
)->entry.tree.index.rbe_right = (tmp); } else (head)->rbh_root
= (tmp); (tmp)->entry.tree.index.rbe_right = (parent); (parent
)->entry.tree.index.rbe_parent = (tmp); do {} while (0); if
(((tmp)->entry.tree.index.rbe_parent)) do {} while (0); }
while (0); tmp = (parent)->entry.tree.index.rbe_left; } if
(((tmp)->entry.tree.index.rbe_left == ((void*)0) || ((tmp
)->entry.tree.index.rbe_left)->entry.tree.index.rbe_color
== 0) && ((tmp)->entry.tree.index.rbe_right == ((
void*)0) || ((tmp)->entry.tree.index.rbe_right)->entry.
tree.index.rbe_color == 0)) { (tmp)->entry.tree.index.rbe_color
= 1; elm = parent; parent = (elm)->entry.tree.index.rbe_parent
; } else { if ((tmp)->entry.tree.index.rbe_left == ((void*
)0) || ((tmp)->entry.tree.index.rbe_left)->entry.tree.index
.rbe_color == 0) { struct prefix *oright; if ((oright = (tmp)
->entry.tree.index.rbe_right)) (oright)->entry.tree.index
.rbe_color = 0; (tmp)->entry.tree.index.rbe_color = 1; do {
(oright) = (tmp)->entry.tree.index.rbe_right; if (((tmp)->
entry.tree.index.rbe_right = (oright)->entry.tree.index.rbe_left
)) { ((oright)->entry.tree.index.rbe_left)->entry.tree.
index.rbe_parent = (tmp); } do {} while (0); if (((oright)->
entry.tree.index.rbe_parent = (tmp)->entry.tree.index.rbe_parent
)) { if ((tmp) == ((tmp)->entry.tree.index.rbe_parent)->
entry.tree.index.rbe_left) ((tmp)->entry.tree.index.rbe_parent
)->entry.tree.index.rbe_left = (oright); else ((tmp)->entry
.tree.index.rbe_parent)->entry.tree.index.rbe_right = (oright
); } else (head)->rbh_root = (oright); (oright)->entry.
tree.index.rbe_left = (tmp); (tmp)->entry.tree.index.rbe_parent
= (oright); do {} while (0); if (((oright)->entry.tree.index
.rbe_parent)) do {} while (0); } while (0); tmp = (parent)->
entry.tree.index.rbe_left; } (tmp)->entry.tree.index.rbe_color
= (parent)->entry.tree.index.rbe_color; (parent)->entry
.tree.index.rbe_color = 0; if ((tmp)->entry.tree.index.rbe_left
) ((tmp)->entry.tree.index.rbe_left)->entry.tree.index.
rbe_color = 0; do { (tmp) = (parent)->entry.tree.index.rbe_left
; if (((parent)->entry.tree.index.rbe_left = (tmp)->entry
.tree.index.rbe_right)) { ((tmp)->entry.tree.index.rbe_right
)->entry.tree.index.rbe_parent = (parent); } do {} while (
0); if (((tmp)->entry.tree.index.rbe_parent = (parent)->
entry.tree.index.rbe_parent)) { if ((parent) == ((parent)->
entry.tree.index.rbe_parent)->entry.tree.index.rbe_left) (
(parent)->entry.tree.index.rbe_parent)->entry.tree.index
.rbe_left = (tmp); else ((parent)->entry.tree.index.rbe_parent
)->entry.tree.index.rbe_right = (tmp); } else (head)->rbh_root
= (tmp); (tmp)->entry.tree.index.rbe_right = (parent); (parent
)->entry.tree.index.rbe_parent = (tmp); do {} while (0); if
(((tmp)->entry.tree.index.rbe_parent)) do {} while (0); }
while (0); elm = (head)->rbh_root; break; } } } if (elm) (
elm)->entry.tree.index.rbe_color = 0; } __attribute__((__unused__
)) static struct prefix * prefix_index_RB_REMOVE(struct prefix_index
*head, struct prefix *elm) { struct prefix *child, *parent, *
old = elm; int color; if ((elm)->entry.tree.index.rbe_left
== ((void*)0)) child = (elm)->entry.tree.index.rbe_right;
else if ((elm)->entry.tree.index.rbe_right == ((void*)0))
child = (elm)->entry.tree.index.rbe_left; else { struct prefix
*left; elm = (elm)->entry.tree.index.rbe_right; while ((left
= (elm)->entry.tree.index.rbe_left)) elm = left; child = (
elm)->entry.tree.index.rbe_right; parent = (elm)->entry
.tree.index.rbe_parent; color = (elm)->entry.tree.index.rbe_color
; if (child) (child)->entry.tree.index.rbe_parent = parent
; if (parent) { if ((parent)->entry.tree.index.rbe_left ==
elm) (parent)->entry.tree.index.rbe_left = child; else (parent
)->entry.tree.index.rbe_right = child; do {} while (0); } else
(head)->rbh_root = child; if ((elm)->entry.tree.index.
rbe_parent == old) parent = elm; (elm)->entry.tree.index =
(old)->entry.tree.index; if ((old)->entry.tree.index.rbe_parent
) { if (((old)->entry.tree.index.rbe_parent)->entry.tree
.index.rbe_left == old) ((old)->entry.tree.index.rbe_parent
)->entry.tree.index.rbe_left = elm; else ((old)->entry.
tree.index.rbe_parent)->entry.tree.index.rbe_right = elm; do
{} while (0); } else (head)->rbh_root = elm; ((old)->entry
.tree.index.rbe_left)->entry.tree.index.rbe_parent = elm; if
((old)->entry.tree.index.rbe_right) ((old)->entry.tree
.index.rbe_right)->entry.tree.index.rbe_parent = elm; if (
parent) { left = parent; do { do {} while (0); } while ((left
= (left)->entry.tree.index.rbe_parent)); } goto color; } parent
= (elm)->entry.tree.index.rbe_parent; color = (elm)->entry
.tree.index.rbe_color; if (child) (child)->entry.tree.index
.rbe_parent = parent; if (parent) { if ((parent)->entry.tree
.index.rbe_left == elm) (parent)->entry.tree.index.rbe_left
= child; else (parent)->entry.tree.index.rbe_right = child
; do {} while (0); } else (head)->rbh_root = child; color:
if (color == 0) prefix_index_RB_REMOVE_COLOR(head, parent, child
); return (old); } __attribute__((__unused__)) static struct prefix
* prefix_index_RB_INSERT(struct prefix_index *head, struct prefix
*elm) { struct prefix *tmp; struct prefix *parent = ((void*)
0); int comp = 0; tmp = (head)->rbh_root; while (tmp) { parent
= tmp; comp = (prefix_index_cmp)(elm, parent); if (comp <
0) tmp = (tmp)->entry.tree.index.rbe_left; else if (comp >
0) tmp = (tmp)->entry.tree.index.rbe_right; else return (
tmp); } do { (elm)->entry.tree.index.rbe_parent = parent; (
elm)->entry.tree.index.rbe_left = (elm)->entry.tree.index
.rbe_right = ((void*)0); (elm)->entry.tree.index.rbe_color
= 1; } while (0); if (parent != ((void*)0)) { if (comp < 0
) (parent)->entry.tree.index.rbe_left = elm; else (parent)
->entry.tree.index.rbe_right = elm; do {} while (0); } else
(head)->rbh_root = elm; prefix_index_RB_INSERT_COLOR(head
, elm); return (((void*)0)); } __attribute__((__unused__)) static
struct prefix * prefix_index_RB_FIND(struct prefix_index *head
, struct prefix *elm) { struct prefix *tmp = (head)->rbh_root
; int comp; while (tmp) { comp = prefix_index_cmp(elm, tmp); if
(comp < 0) tmp = (tmp)->entry.tree.index.rbe_left; else
if (comp > 0) tmp = (tmp)->entry.tree.index.rbe_right;
else return (tmp); } return (((void*)0)); } __attribute__((__unused__
)) static struct prefix * prefix_index_RB_NFIND(struct prefix_index
*head, struct prefix *elm) { struct prefix *tmp = (head)->
rbh_root; struct prefix *res = ((void*)0); int comp; while (tmp
) { comp = prefix_index_cmp(elm, tmp); if (comp < 0) { res
= tmp; tmp = (tmp)->entry.tree.index.rbe_left; } else if (
comp > 0) tmp = (tmp)->entry.tree.index.rbe_right; else
return (tmp); } return (res); } __attribute__((__unused__)) static
struct prefix * prefix_index_RB_NEXT(struct prefix *elm) { if
((elm)->entry.tree.index.rbe_right) { elm = (elm)->entry
.tree.index.rbe_right; while ((elm)->entry.tree.index.rbe_left
) elm = (elm)->entry.tree.index.rbe_left; } else { if ((elm
)->entry.tree.index.rbe_parent && (elm == ((elm)->
entry.tree.index.rbe_parent)->entry.tree.index.rbe_left)) elm
= (elm)->entry.tree.index.rbe_parent; else { while ((elm)
->entry.tree.index.rbe_parent && (elm == ((elm)->
entry.tree.index.rbe_parent)->entry.tree.index.rbe_right))
elm = (elm)->entry.tree.index.rbe_parent; elm = (elm)->
entry.tree.index.rbe_parent; } } return (elm); } __attribute__
((__unused__)) static struct prefix * prefix_index_RB_PREV(struct
prefix *elm) { if ((elm)->entry.tree.index.rbe_left) { elm
= (elm)->entry.tree.index.rbe_left; while ((elm)->entry
.tree.index.rbe_right) elm = (elm)->entry.tree.index.rbe_right
; } else { if ((elm)->entry.tree.index.rbe_parent &&
(elm == ((elm)->entry.tree.index.rbe_parent)->entry.tree
.index.rbe_right)) elm = (elm)->entry.tree.index.rbe_parent
; else { while ((elm)->entry.tree.index.rbe_parent &&
(elm == ((elm)->entry.tree.index.rbe_parent)->entry.tree
.index.rbe_left)) elm = (elm)->entry.tree.index.rbe_parent
; elm = (elm)->entry.tree.index.rbe_parent; } } return (elm
); } __attribute__((__unused__)) static struct prefix * prefix_index_RB_MINMAX
(struct prefix_index *head, int val) { struct prefix *tmp = (
head)->rbh_root; struct prefix *parent = ((void*)0); while
(tmp) { parent = tmp; if (val < 0) tmp = (tmp)->entry.
tree.index.rbe_left; else tmp = (tmp)->entry.tree.index.rbe_right
; } return (parent); }
892
893/*
894 * search for specified prefix of a peer. Returns NULL if not found.
895 */
896struct prefix *
897prefix_get(struct rib *rib, struct rde_peer *peer, u_int32_t path_id,
898 struct bgpd_addr *prefix, int prefixlen)
899{
900 struct rib_entry *re;
901
902 re = rib_get(rib, prefix, prefixlen);
903 if (re == NULL((void*)0))
904 return (NULL((void*)0));
905 return (prefix_bypeer(re, peer, path_id));
906}
907
908/*
909 * lookup prefix in the peer prefix_index. Returns NULL if not found.
910 */
911struct prefix *
912prefix_lookup(struct rde_peer *peer, struct bgpd_addr *prefix,
913 int prefixlen)
914{
915 struct prefix xp;
916 struct pt_entry *pte;
917
918 memset(&xp, 0, sizeof(xp));
919 pte = pt_fill(prefix, prefixlen);
920 xp.pt = pte;
921
922 return RB_FIND(prefix_index, &peer->adj_rib_out, &xp)prefix_index_RB_FIND(&peer->adj_rib_out, &xp);
923}
924
925struct prefix *
926prefix_match(struct rde_peer *peer, struct bgpd_addr *addr)
927{
928 struct prefix *p;
929 int i;
930
931 switch (addr->aid) {
932 case AID_INET1:
933 case AID_VPN_IPv43:
934 for (i = 32; i >= 0; i--) {
935 p = prefix_lookup(peer, addr, i);
936 if (p != NULL((void*)0))
937 return p;
938 }
939 break;
940 case AID_INET62:
941 case AID_VPN_IPv64:
942 for (i = 128; i >= 0; i--) {
943 p = prefix_lookup(peer, addr, i);
944 if (p != NULL((void*)0))
945 return p;
946 }
947 break;
948 default:
949 fatalx("%s: unknown af", __func__);
950 }
951 return NULL((void*)0);
952}
953
954/*
955 * Update a prefix.
956 * Return 1 if prefix was newly added, 0 if it was just changed.
957 */
958int
959prefix_update(struct rib *rib, struct rde_peer *peer, u_int32_t path_id,
960 struct filterstate *state, struct bgpd_addr *prefix, int prefixlen,
961 u_int8_t vstate)
962{
963 struct rde_aspath *asp, *nasp = &state->aspath;
964 struct rde_community *comm, *ncomm = &state->communities;
965 struct prefix *p;
966
967 /*
968 * First try to find a prefix in the specified RIB.
969 */
970 if ((p = prefix_get(rib, peer, path_id, prefix, prefixlen)) != NULL((void*)0)) {
971 if (prefix_nexthop(p) == state->nexthop &&
972 prefix_nhflags(p) == state->nhflags &&
973 communities_equal(ncomm, prefix_communities(p)) &&
974 path_compare(nasp, prefix_aspath(p)) == 0) {
975 /* no change, update last change */
976 p->lastchange = getmonotime();
977 p->validation_state = vstate;
978 return (0);
979 }
980 }
981
982 /*
983 * Either the prefix does not exist or the path changed.
984 * In both cases lookup the new aspath to make sure it is not
985 * already in the RIB.
986 */
987 if ((asp = path_lookup(nasp)) == NULL((void*)0)) {
988 /* Path not available, create and link a new one. */
989 asp = path_copy(path_get(), nasp);
990 path_link(asp);
991 }
992
993 if ((comm = communities_lookup(ncomm)) == NULL((void*)0)) {
994 /* Communities not available, create and link a new one. */
995 comm = communities_link(ncomm);
996 }
997
998 /* If the prefix was found move it else add it to the RIB. */
999 if (p != NULL((void*)0))
1000 return (prefix_move(p, peer, asp, comm, state->nexthop,
1001 state->nhflags, vstate));
1002 else
1003 return (prefix_add(prefix, prefixlen, rib, peer, path_id, asp,
1004 comm, state->nexthop, state->nhflags, vstate));
1005}
1006
1007/*
1008 * Adds or updates a prefix.
1009 */
1010static int
1011prefix_add(struct bgpd_addr *prefix, int prefixlen, struct rib *rib,
1012 struct rde_peer *peer, u_int32_t path_id, struct rde_aspath *asp,
1013 struct rde_community *comm, struct nexthop *nexthop, u_int8_t nhflags,
1014 u_int8_t vstate)
1015{
1016 struct prefix *p;
1017 struct rib_entry *re;
1018
1019 re = rib_get(rib, prefix, prefixlen);
1020 if (re == NULL((void*)0))
1021 re = rib_add(rib, prefix, prefixlen);
1022
1023 p = prefix_alloc();
1024 prefix_link(p, re, peer, path_id, asp, comm, nexthop, nhflags, vstate);
1025 return (1);
1026}
1027
1028/*
1029 * Move the prefix to the specified as path, removes the old asp if needed.
1030 */
1031static int
1032prefix_move(struct prefix *p, struct rde_peer *peer,
1033 struct rde_aspath *asp, struct rde_community *comm,
1034 struct nexthop *nexthop, u_int8_t nhflags, u_int8_t vstate)
1035{
1036 struct prefix *np;
1037
1038 if (p->flags & PREFIX_FLAG_ADJOUT0x10)
1039 fatalx("%s: prefix with PREFIX_FLAG_ADJOUT hit", __func__);
1040
1041 if (peer != prefix_peer(p))
1042 fatalx("prefix_move: cross peer move");
1043
1044 /* add new prefix node */
1045 np = prefix_alloc();
1046 /* add reference to new AS path and communities */
1047 np->aspath = path_ref(asp);
1048 np->communities = communities_ref(comm);
1049 np->peer = peer;
1050 np->entry.list.re = prefix_re(p);
1051 np->pt = p->pt; /* skip refcnt update since ref is moved */
1052 np->path_id = p->path_id;
1053 np->validation_state = vstate;
1054 np->nhflags = nhflags;
1055 np->nexthop = nexthop_ref(nexthop);
1056 nexthop_link(np);
1057 np->lastchange = getmonotime();
1058
1059 /* add possible pftable reference from new aspath */
1060 if (asp && asp->pftableid)
1061 rde_pftable_add(asp->pftableid, np);
1062
1063 /*
1064 * no need to update the peer prefix count because we are only moving
1065 * the prefix without changing the peer.
1066 */
1067 prefix_evaluate(prefix_re(np), np, p);
1068
1069 /* remove possible pftable reference from old path first */
1070 if (p->aspath && p->aspath->pftableid)
1071 rde_pftable_del(p->aspath->pftableid, p);
1072
1073 /* remove old prefix node */
1074 nexthop_unlink(p);
1075 nexthop_unref(p->nexthop);
1076 communities_unref(p->communities);
1077 path_unref(p->aspath);
1078 p->communities = NULL((void*)0);
1079 p->nexthop = NULL((void*)0);
1080 p->aspath = NULL((void*)0);
1081 p->peer = NULL((void*)0);
1082 p->pt = NULL((void*)0);
1083 p->entry.list.re = NULL((void*)0);
1084 prefix_free(p);
1085
1086 return (0);
1087}
1088
1089/*
1090 * Removes a prefix from the specified RIB. If the parent objects -- rib_entry
1091 * or pt_entry -- become empty remove them too.
1092 */
1093int
1094prefix_withdraw(struct rib *rib, struct rde_peer *peer, u_int32_t path_id,
1095 struct bgpd_addr *prefix, int prefixlen)
1096{
1097 struct prefix *p;
1098 struct rde_aspath *asp;
1099
1100 p = prefix_get(rib, peer, path_id, prefix, prefixlen);
1101 if (p == NULL((void*)0)) /* Got a dummy withdrawn request. */
1102 return (0);
1103
1104 if (p->flags & PREFIX_FLAG_ADJOUT0x10)
1105 fatalx("%s: prefix with PREFIX_FLAG_ADJOUT hit", __func__);
1106 asp = prefix_aspath(p);
1107 if (asp && asp->pftableid)
1108 /* only prefixes in the local RIB were pushed into pf */
1109 rde_pftable_del(asp->pftableid, p);
1110
1111 prefix_destroy(p);
1112
1113 return (1);
1114}
1115
1116/*
1117 * Insert an End-of-RIB marker into the update queue.
1118 */
1119void
1120prefix_add_eor(struct rde_peer *peer, u_int8_t aid)
1121{
1122 struct prefix *p;
1123
1124 p = prefix_alloc();
1125 p->flags = PREFIX_FLAG_ADJOUT0x10 | PREFIX_FLAG_UPDATE0x02;
1126 p->eor = 1;
1127 if (RB_INSERT(prefix_tree, &peer->updates[aid], p)prefix_tree_RB_INSERT(&peer->updates[aid], p) != NULL((void*)0))
1128 /* no need to add if EoR marker already present */
1129 prefix_free(p);
1130 /* EOR marker is not inserted into the adj_rib_out index */
1131}
1132
1133/*
1134 * Put a prefix from the Adj-RIB-Out onto the update queue.
1135 */
1136int
1137prefix_adjout_update(struct rde_peer *peer, struct filterstate *state,
1138 struct bgpd_addr *prefix, int prefixlen, u_int8_t vstate)
1139{
1140 struct prefix_tree *prefix_head = NULL((void*)0);
1141 struct rde_aspath *asp;
1142 struct rde_community *comm;
1143 struct prefix *p;
1144 int created = 0;
1145
1146 if ((p = prefix_lookup(peer, prefix, prefixlen)) != NULL((void*)0)) {
1147 if ((p->flags & PREFIX_FLAG_ADJOUT0x10) == 0)
1148 fatalx("%s: prefix without PREFIX_FLAG_ADJOUT hit",
1149 __func__);
1150 /* prefix is already in the Adj-RIB-Out */
1151 if (p->flags & PREFIX_FLAG_WITHDRAW0x01) {
1152 created = 1; /* consider this a new entry */
1153 peer->up_wcnt--;
1154 prefix_head = &peer->withdraws[prefix->aid];
1155 RB_REMOVE(prefix_tree, prefix_head, p)prefix_tree_RB_REMOVE(prefix_head, p);
1156 } else if (p->flags & PREFIX_FLAG_DEAD0x04) {
1157 created = 1; /* consider this a new entry */
1158 } else {
1159 if (prefix_nhflags(p) == state->nhflags &&
1160 prefix_nexthop(p) == state->nexthop &&
1161 communities_equal(&state->communities,
1162 prefix_communities(p)) &&
1163 path_compare(&state->aspath, prefix_aspath(p)) ==
1164 0) {
1165 /* nothing changed */
1166 p->validation_state = vstate;
1167 p->lastchange = getmonotime();
1168 p->flags &= ~PREFIX_FLAG_STALE0x08;
1169 return 0;
1170 }
1171
1172 if (p->flags & PREFIX_FLAG_UPDATE0x02) {
1173 /* created = 0 so up_nlricnt is not increased */
1174 prefix_head = &peer->updates[prefix->aid];
1175 RB_REMOVE(prefix_tree, prefix_head, p)prefix_tree_RB_REMOVE(prefix_head, p);
1176 }
1177 }
1178 /* unlink from aspath and remove nexthop ref */
1179 nexthop_unref(p->nexthop);
1180 communities_unref(p->communities);
1181 path_unref(p->aspath);
1182 p->flags &= ~PREFIX_FLAG_MASK0x0f;
1183
1184 /* peer and pt remain */
1185 } else {
1186 p = prefix_alloc();
1187 p->flags |= PREFIX_FLAG_ADJOUT0x10;
1188 created = 1;
1189
1190 p->pt = pt_get(prefix, prefixlen);
1191 if (p->pt == NULL((void*)0))
1192 p->pt = pt_add(prefix, prefixlen);
1193 pt_ref(p->pt);
1194 p->peer = peer;
1195
1196 if (RB_INSERT(prefix_index, &peer->adj_rib_out, p)prefix_index_RB_INSERT(&peer->adj_rib_out, p) != NULL((void*)0))
1197 fatalx("%s: RB index invariant violated", __func__);
1198 }
1199
1200 if ((asp = path_lookup(&state->aspath)) == NULL((void*)0)) {
1201 /* Path not available, create and link a new one. */
1202 asp = path_copy(path_get(), &state->aspath);
1203 path_link(asp);
1204 }
1205
1206 if ((comm = communities_lookup(&state->communities)) == NULL((void*)0)) {
1207 /* Communities not available, create and link a new one. */
1208 comm = communities_link(&state->communities);
1209 }
1210
1211 p->aspath = path_ref(asp);
1212 p->communities = communities_ref(comm);
1213 p->nexthop = nexthop_ref(state->nexthop);
1214 p->nhflags = state->nhflags;
1215
1216 p->validation_state = vstate;
1217 p->lastchange = getmonotime();
1218
1219 if (p->flags & PREFIX_FLAG_MASK0x0f)
1220 fatalx("%s: bad flags %x", __func__, p->flags);
1221 p->flags |= PREFIX_FLAG_UPDATE0x02;
1222 if (RB_INSERT(prefix_tree, &peer->updates[prefix->aid], p)prefix_tree_RB_INSERT(&peer->updates[prefix->aid], p
) != NULL((void*)0))
1223 fatalx("%s: RB tree invariant violated", __func__);
1224
1225 return created;
1226}
1227
1228/*
1229 * Withdraw a prefix from the Adj-RIB-Out, this unlinks the aspath but leaves
1230 * the prefix in the RIB linked to the peer withdraw list.
1231 */
1232int
1233prefix_adjout_withdraw(struct rde_peer *peer, struct bgpd_addr *prefix,
1234 int prefixlen)
1235{
1236 struct prefix *p;
1237
1238 p = prefix_lookup(peer, prefix, prefixlen);
1239 if (p == NULL((void*)0)) /* Got a dummy withdrawn request. */
1240 return (0);
1241
1242 if ((p->flags & PREFIX_FLAG_ADJOUT0x10) == 0)
1243 fatalx("%s: prefix without PREFIX_FLAG_ADJOUT hit", __func__);
1244
1245 /* already a withdraw, shortcut */
1246 if (p->flags & PREFIX_FLAG_WITHDRAW0x01) {
1247 p->lastchange = getmonotime();
1248 p->flags &= ~PREFIX_FLAG_STALE0x08;
1249 return (0);
1250 }
1251 /* pending update just got withdrawn */
1252 if (p->flags & PREFIX_FLAG_UPDATE0x02)
1253 RB_REMOVE(prefix_tree, &peer->updates[p->pt->aid], p)prefix_tree_RB_REMOVE(&peer->updates[p->pt->aid]
, p);
1254 /* nothing needs to be done for PREFIX_FLAG_DEAD and STALE */
1255 p->flags &= ~PREFIX_FLAG_MASK0x0f;
1256
1257 /* remove nexthop ref ... */
1258 nexthop_unref(p->nexthop);
1259 p->nexthop = NULL((void*)0);
1260 p->nhflags = 0;
1261
1262 /* unlink from aspath ...*/
1263 path_unref(p->aspath);
1264 p->aspath = NULL((void*)0);
1265
1266 /* ... communities ... */
1267 communities_unref(p->communities);
1268 p->communities = NULL((void*)0);
1269 /* and unlink from aspath */
1270 path_unref(p->aspath);
1271 p->aspath = NULL((void*)0);
1272 /* re already NULL */
1273
1274 p->lastchange = getmonotime();
1275
1276 p->flags |= PREFIX_FLAG_WITHDRAW0x01;
1277 if (RB_INSERT(prefix_tree, &peer->withdraws[prefix->aid], p)prefix_tree_RB_INSERT(&peer->withdraws[prefix->aid]
, p) != NULL((void*)0))
1278 fatalx("%s: RB tree invariant violated", __func__);
1279 return (1);
1280}
1281
1282static struct prefix *
1283prefix_restart(struct rib_context *ctx)
1284{
1285 struct prefix *p;
1286
1287 p = prefix_unlock(ctx->ctx_p);
1288
1289 if (prefix_is_dead(p)) {
1290 struct prefix *next;
1291
1292 next = RB_NEXT(prefix_index, unused, p)prefix_index_RB_NEXT(p);
1293 prefix_adjout_destroy(p);
1294 p = next;
1295 }
1296 ctx->ctx_p = NULL((void*)0);
1297 return p;
1298}
1299
1300void
1301prefix_adjout_destroy(struct prefix *p)
1302{
1303 struct rde_peer *peer = prefix_peer(p);
1304
1305 if ((p->flags & PREFIX_FLAG_ADJOUT0x10) == 0)
1306 fatalx("%s: prefix without PREFIX_FLAG_ADJOUT hit", __func__);
1307
1308 if (p->eor) {
1309 /* EOR marker is not linked in the index */
1310 prefix_free(p);
1311 return;
1312 }
1313
1314 if (p->flags & PREFIX_FLAG_WITHDRAW0x01)
1315 RB_REMOVE(prefix_tree, &peer->withdraws[p->pt->aid], p)prefix_tree_RB_REMOVE(&peer->withdraws[p->pt->aid
], p);
1316 else if (p->flags & PREFIX_FLAG_UPDATE0x02)
1317 RB_REMOVE(prefix_tree, &peer->updates[p->pt->aid], p)prefix_tree_RB_REMOVE(&peer->updates[p->pt->aid]
, p);
1318 /* nothing needs to be done for PREFIX_FLAG_DEAD and STALE */
1319 p->flags &= ~PREFIX_FLAG_MASK0x0f;
1320
1321
1322 if (prefix_is_locked(p)) {
1323 /* remove nexthop ref ... */
1324 nexthop_unref(p->nexthop);
1325 p->nexthop = NULL((void*)0);
1326 /* ... communities ... */
1327 communities_unref(p->communities);
1328 p->communities = NULL((void*)0);
1329 /* and unlink from aspath */
1330 path_unref(p->aspath);
1331 p->aspath = NULL((void*)0);
1332 p->nhflags = 0;
1333 /* re already NULL */
1334
1335 /* finally mark prefix dead */
1336 p->flags |= PREFIX_FLAG_DEAD0x04;
1337 return;
1338 }
1339
1340 RB_REMOVE(prefix_index, &peer->adj_rib_out, p)prefix_index_RB_REMOVE(&peer->adj_rib_out, p);
1341
1342 prefix_unlink(p);
1343 prefix_free(p);
1344}
1345
1346static void
1347prefix_dump_r(struct rib_context *ctx)
1348{
1349 struct prefix *p, *next;
1350 struct rde_peer *peer;
1351 unsigned int i;
1352
1353 if ((peer = peer_get(ctx->ctx_id)) == NULL((void*)0))
1354 goto done;
1355
1356 if (ctx->ctx_p == NULL((void*)0))
1357 p = RB_MIN(prefix_index, &peer->adj_rib_out)prefix_index_RB_MINMAX(&peer->adj_rib_out, -1);
1358 else
1359 p = prefix_restart(ctx);
1360
1361 for (i = 0; p != NULL((void*)0); p = next) {
1362 next = RB_NEXT(prefix_index, unused, p)prefix_index_RB_NEXT(p);
1363 if (prefix_is_dead(p))
1364 continue;
1365 if (ctx->ctx_aid != AID_UNSPEC0 &&
1366 ctx->ctx_aid != p->pt->aid)
1367 continue;
1368 if (ctx->ctx_count && i++ >= ctx->ctx_count &&
1369 !prefix_is_locked(p)) {
1370 /* store and lock last element */
1371 ctx->ctx_p = prefix_lock(p);
1372 return;
1373 }
1374 ctx->ctx_prefix_call(p, ctx->ctx_arg);
1375 }
1376
1377done:
1378 if (ctx->ctx_done)
1379 ctx->ctx_done(ctx->ctx_arg, ctx->ctx_aid);
1380 LIST_REMOVE(ctx, entry)do { if ((ctx)->entry.le_next != ((void*)0)) (ctx)->entry
.le_next->entry.le_prev = (ctx)->entry.le_prev; *(ctx)->
entry.le_prev = (ctx)->entry.le_next; ; ; } while (0);
1381 free(ctx);
1382}
1383
1384int
1385prefix_dump_new(struct rde_peer *peer, u_int8_t aid, unsigned int count,
1386 void *arg, void (*upcall)(struct prefix *, void *),
1387 void (*done)(void *, u_int8_t), int (*throttle)(void *))
1388{
1389 struct rib_context *ctx;
1390
1391 if ((ctx = calloc(1, sizeof(*ctx))) == NULL((void*)0))
1392 return -1;
1393 ctx->ctx_id = peer->conf.id;
1394 ctx->ctx_aid = aid;
1395 ctx->ctx_count = count;
1396 ctx->ctx_arg = arg;
1397 ctx->ctx_prefix_call = upcall;
1398 ctx->ctx_done = done;
1399 ctx->ctx_throttle = throttle;
1400
1401 LIST_INSERT_HEAD(&rib_dumps, ctx, entry)do { if (((ctx)->entry.le_next = (&rib_dumps)->lh_first
) != ((void*)0)) (&rib_dumps)->lh_first->entry.le_prev
= &(ctx)->entry.le_next; (&rib_dumps)->lh_first
= (ctx); (ctx)->entry.le_prev = &(&rib_dumps)->
lh_first; } while (0);
1402
1403 /* requested a sync traversal */
1404 if (count == 0)
1405 prefix_dump_r(ctx);
1406
1407 return 0;
1408}
1409
1410/* dump a prefix into specified buffer */
1411int
1412prefix_write(u_char *buf, int len, struct bgpd_addr *prefix, u_int8_t plen,
1413 int withdraw)
1414{
1415 int totlen, psize;
1416
1417 switch (prefix->aid) {
1418 case AID_INET1:
1419 case AID_INET62:
1420 totlen = PREFIX_SIZE(plen)(((plen) + 7) / 8 + 1);
1421
1422 if (totlen > len)
1423 return (-1);
1424 *buf++ = plen;
1425 memcpy(buf, &prefix->ba, totlen - 1);
1426 return (totlen);
1427 case AID_VPN_IPv43:
1428 case AID_VPN_IPv64:
1429 totlen = PREFIX_SIZE(plen)(((plen) + 7) / 8 + 1) + sizeof(prefix->rd);
1430 psize = PREFIX_SIZE(plen)(((plen) + 7) / 8 + 1) - 1;
1431 plen += sizeof(prefix->rd) * 8;
1432 if (withdraw) {
1433 /* withdraw have one compat label as placeholder */
1434 totlen += 3;
1435 plen += 3 * 8;
1436 } else {
1437 totlen += prefix->labellen;
1438 plen += prefix->labellen * 8;
1439 }
1440
1441 if (totlen > len)
1442 return (-1);
1443 *buf++ = plen;
1444 if (withdraw) {
1445 /* magic compatibility label as per rfc8277 */
1446 *buf++ = 0x80;
1447 *buf++ = 0x0;
1448 *buf++ = 0x0;
1449 } else {
1450 memcpy(buf, &prefix->labelstack,
1451 prefix->labellen);
1452 buf += prefix->labellen;
1453 }
1454 memcpy(buf, &prefix->rd, sizeof(prefix->rd));
1455 buf += sizeof(prefix->rd);
1456 memcpy(buf, &prefix->ba, psize);
1457 return (totlen);
1458 default:
1459 return (-1);
1460 }
1461}
1462
1463int
1464prefix_writebuf(struct ibuf *buf, struct bgpd_addr *prefix, u_int8_t plen)
1465{
1466 int totlen;
1467 void *bptr;
1468
1469 switch (prefix->aid) {
1470 case AID_INET1:
1471 case AID_INET62:
1472 totlen = PREFIX_SIZE(plen)(((plen) + 7) / 8 + 1);
1473 break;
1474 case AID_VPN_IPv43:
1475 case AID_VPN_IPv64:
1476 totlen = PREFIX_SIZE(plen)(((plen) + 7) / 8 + 1) + sizeof(prefix->rd) +
1477 prefix->labellen;
1478 break;
1479 default:
1480 return (-1);
1481 }
1482
1483 if ((bptr = ibuf_reserve(buf, totlen)) == NULL((void*)0))
1484 return (-1);
1485 if (prefix_write(bptr, totlen, prefix, plen, 0) == -1)
1486 return (-1);
1487 return (0);
1488}
1489
1490/*
1491 * Searches in the prefix list of specified rib_entry for a prefix entry
1492 * belonging to the peer peer. Returns NULL if no match found.
1493 */
1494struct prefix *
1495prefix_bypeer(struct rib_entry *re, struct rde_peer *peer, u_int32_t path_id)
1496{
1497 struct prefix *p;
1498
1499 LIST_FOREACH(p, &re->prefix_h, entry.list.rib)for((p) = ((&re->prefix_h)->lh_first); (p)!= ((void
*)0); (p) = ((p)->entry.list.rib.le_next))
1500 if (prefix_peer(p) == peer && p->path_id == path_id)
1501 return (p);
1502 return (NULL((void*)0));
1503}
1504
1505static void
1506prefix_evaluate_all(struct prefix *p, enum nexthop_state state,
1507 enum nexthop_state oldstate)
1508{
1509 struct rib_entry *re = prefix_re(p);
1510
1511 /* Skip non local-RIBs or RIBs that are flagged as noeval. */
1512 if (re_rib(re)->flags & F_RIB_NOEVALUATE0x0002) {
1513 log_warnx("%s: prefix with F_RIB_NOEVALUATE hit", __func__);
1514 return;
1515 }
1516
1517 if (oldstate == state) {
1518 /*
1519 * The state of the nexthop did not change. The only
1520 * thing that may have changed is the true_nexthop
1521 * or other internal infos. This will not change
1522 * the routing decision so shortcut here.
1523 */
1524 if (state == NEXTHOP_REACH) {
1525 if ((re_rib(re)->flags & F_RIB_NOFIB0x0004) == 0 &&
1526 p == re->active)
1527 rde_send_kroute(re_rib(re), p, NULL((void*)0));
1528 }
1529 return;
1530 }
1531
1532 /* redo the route decision */
1533 prefix_evaluate(prefix_re(p), p, p);
1534}
1535
1536/* kill a prefix. */
1537void
1538prefix_destroy(struct prefix *p)
1539{
1540 /* make route decision */
1541 prefix_evaluate(prefix_re(p), NULL((void*)0), p);
1542
1543 prefix_unlink(p);
1544 prefix_free(p);
14
←
Calling 'prefix_free'
→
16
←
Returning; memory was released via 1st parameter
→
1545}
1546
1547/*
1548 * Link a prefix into the different parent objects.
1549 */
1550static void
1551prefix_link(struct prefix *p, struct rib_entry *re, struct rde_peer *peer,
1552 u_int32_t path_id, struct rde_aspath *asp, struct rde_community *comm,
1553 struct nexthop *nexthop, u_int8_t nhflags, u_int8_t vstate)
1554{
1555 if (p->flags & PREFIX_FLAG_ADJOUT0x10)
1556 fatalx("%s: prefix with PREFIX_FLAG_ADJOUT hit", __func__);
1557
1558 p->entry.list.re = re;
1559 p->aspath = path_ref(asp);
1560 p->communities = communities_ref(comm);
1561 p->peer = peer;
1562 p->pt = pt_ref(re->prefix);
1563 p->path_id = path_id;
1564 p->validation_state = vstate;
1565 p->nhflags = nhflags;
1566 p->nexthop = nexthop_ref(nexthop);
1567 nexthop_link(p);
1568 p->lastchange = getmonotime();
1569
1570 /* add possible pftable reference from aspath */
1571 if (asp && asp->pftableid)
1572 rde_pftable_add(asp->pftableid, p);
1573
1574 /* make route decision */
1575 prefix_evaluate(re, p, NULL((void*)0));
1576}
1577
1578/*
1579 * Unlink a prefix from the different parent objects.
1580 */
1581static void
1582prefix_unlink(struct prefix *p)
1583{
1584 struct rib_entry *re = prefix_re(p);
1585
1586 /* destroy all references to other objects */
1587 nexthop_unlink(p);
1588 nexthop_unref(p->nexthop);
1589 communities_unref(p->communities);
1590 path_unref(p->aspath);
1591 pt_unref(p->pt);
1592 p->communities = NULL((void*)0);
1593 p->nexthop = NULL((void*)0);
1594 p->aspath = NULL((void*)0);
1595 p->peer = NULL((void*)0);
1596 p->pt = NULL((void*)0);
1597
1598 if (re && rib_empty(re))
1599 rib_remove(re);
1600
1601 /*
1602 * It's the caller's duty to do accounting and remove empty aspath
1603 * structures. Also freeing the unlinked prefix is the caller's duty.
1604 */
1605}
1606
1607/* alloc and zero new entry. May not fail. */
1608static struct prefix *
1609prefix_alloc(void)
1610{
1611 struct prefix *p;
1612
1613 p = calloc(1, sizeof(*p));
1614 if (p == NULL((void*)0))
1615 fatal("prefix_alloc");
1616 rdemem.prefix_cnt++;
1617 return p;
1618}
1619
1620/* free a unlinked entry */
1621static void
1622prefix_free(struct prefix *p)
1623{
1624 rdemem.prefix_cnt--;
1625 free(p);
15
←
Memory is released
→
1626}
1627
1628/*
1629 * nexthop functions
1630 */
1631struct nexthop_head *nexthop_hash(struct bgpd_addr *);
1632struct nexthop *nexthop_lookup(struct bgpd_addr *);
1633
1634/*
1635 * In BGP there exist two nexthops: the exit nexthop which was announced via
1636 * BGP and the true nexthop which is used in the FIB -- forward information
1637 * base a.k.a kernel routing table. When sending updates it is even more
1638 * confusing. In IBGP we pass the unmodified exit nexthop to the neighbors
1639 * while in EBGP normally the address of the router is sent. The exit nexthop
1640 * may be passed to the external neighbor if the neighbor and the exit nexthop
1641 * reside in the same subnet -- directly connected.
1642 */
1643struct nexthop_table {
1644 LIST_HEAD(nexthop_head, nexthop)struct nexthop_head { struct nexthop *lh_first; } *nexthop_hashtbl;
1645 u_int32_t nexthop_hashmask;
1646} nexthoptable;
1647
1648SIPHASH_KEY nexthoptablekey;
1649
1650TAILQ_HEAD(nexthop_queue, nexthop)struct nexthop_queue { struct nexthop *tqh_first; struct nexthop
**tqh_last; } nexthop_runners;
1651
1652void
1653nexthop_init(u_int32_t hashsize)
1654{
1655 u_int32_t hs, i;
1656
1657 for (hs = 1; hs < hashsize; hs <<= 1)
1658 ;
1659 nexthoptable.nexthop_hashtbl = calloc(hs, sizeof(struct nexthop_head));
1660 if (nexthoptable.nexthop_hashtbl == NULL((void*)0))
1661 fatal("nextop_init");
1662
1663 TAILQ_INIT(&nexthop_runners)do { (&nexthop_runners)->tqh_first = ((void*)0); (&
nexthop_runners)->tqh_last = &(&nexthop_runners)->
tqh_first; } while (0);
1664 for (i = 0; i < hs; i++)
1665 LIST_INIT(&nexthoptable.nexthop_hashtbl[i])do { ((&nexthoptable.nexthop_hashtbl[i])->lh_first) = (
(void*)0); } while (0);
1666 arc4random_buf(&nexthoptablekey, sizeof(nexthoptablekey));
1667
1668 nexthoptable.nexthop_hashmask = hs - 1;
1669}
1670
1671void
1672nexthop_shutdown(void)
1673{
1674 u_int32_t i;
1675 struct nexthop *nh, *nnh;
1676
1677 for (i = 0; i <= nexthoptable.nexthop_hashmask; i++) {
1678 for (nh = LIST_FIRST(&nexthoptable.nexthop_hashtbl[i])((&nexthoptable.nexthop_hashtbl[i])->lh_first);
1679 nh != NULL((void*)0); nh = nnh) {
1680 nnh = LIST_NEXT(nh, nexthop_l)((nh)->nexthop_l.le_next);
1681 nh->state = NEXTHOP_UNREACH;
1682 nexthop_unref(nh);
1683 }
1684 if (!LIST_EMPTY(&nexthoptable.nexthop_hashtbl[i])(((&nexthoptable.nexthop_hashtbl[i])->lh_first) == ((void
*)0))) {
1685 nh = LIST_FIRST(&nexthoptable.nexthop_hashtbl[i])((&nexthoptable.nexthop_hashtbl[i])->lh_first);
1686 log_warnx("nexthop_shutdown: non-free table, "
1687 "nexthop %s refcnt %d",
1688 log_addr(&nh->exit_nexthop), nh->refcnt);
1689 }
1690 }
1691
1692 free(nexthoptable.nexthop_hashtbl);
1693}
1694
1695int
1696nexthop_pending(void)
1697{
1698 return !TAILQ_EMPTY(&nexthop_runners)(((&nexthop_runners)->tqh_first) == ((void*)0));
1699}
1700
1701void
1702nexthop_runner(void)
1703{
1704 struct nexthop *nh;
1705 struct prefix *p;
1706 u_int32_t j;
1707
1708 nh = TAILQ_FIRST(&nexthop_runners)((&nexthop_runners)->tqh_first);
1709 if (nh == NULL((void*)0))
1710 return;
1711
1712 /* remove from runnner queue */
1713 TAILQ_REMOVE(&nexthop_runners, nh, runner_l)do { if (((nh)->runner_l.tqe_next) != ((void*)0)) (nh)->
runner_l.tqe_next->runner_l.tqe_prev = (nh)->runner_l.tqe_prev
; else (&nexthop_runners)->tqh_last = (nh)->runner_l
.tqe_prev; *(nh)->runner_l.tqe_prev = (nh)->runner_l.tqe_next
; ; ; } while (0);
1714
1715 p = nh->next_prefix;
1716 for (j = 0; p != NULL((void*)0) && j < RDE_RUNNER_ROUNDS100; j++) {
1717 prefix_evaluate_all(p, nh->state, nh->oldstate);
1718 p = LIST_NEXT(p, entry.list.nexthop)((p)->entry.list.nexthop.le_next);
1719 }
1720
1721 /* prep for next run, if not finished readd to tail of queue */
1722 nh->next_prefix = p;
1723 if (p != NULL((void*)0))
1724 TAILQ_INSERT_TAIL(&nexthop_runners, nh, runner_l)do { (nh)->runner_l.tqe_next = ((void*)0); (nh)->runner_l
.tqe_prev = (&nexthop_runners)->tqh_last; *(&nexthop_runners
)->tqh_last = (nh); (&nexthop_runners)->tqh_last = &
(nh)->runner_l.tqe_next; } while (0);
1725 else
1726 log_debug("nexthop %s update finished",
1727 log_addr(&nh->exit_nexthop));
1728}
1729
1730void
1731nexthop_update(struct kroute_nexthop *msg)
1732{
1733 struct nexthop *nh;
1734
1735 nh = nexthop_lookup(&msg->nexthop);
1736 if (nh == NULL((void*)0)) {
1737 log_warnx("nexthop_update: non-existent nexthop %s",
1738 log_addr(&msg->nexthop));
1739 return;
1740 }
1741
1742 nh->oldstate = nh->state;
1743 if (msg->valid)
1744 nh->state = NEXTHOP_REACH;
1745 else
1746 nh->state = NEXTHOP_UNREACH;
1747
1748 if (nh->oldstate == NEXTHOP_LOOKUP)
1749 /* drop reference which was hold during the lookup */
1750 if (nexthop_unref(nh))
1751 return; /* nh lost last ref, no work left */
1752
1753 if (nh->next_prefix) {
1754 /*
1755 * If nexthop_runner() is not finished with this nexthop
1756 * then ensure that all prefixes are updated by setting
1757 * the oldstate to NEXTHOP_FLAPPED.
1758 */
1759 nh->oldstate = NEXTHOP_FLAPPED;
1760 TAILQ_REMOVE(&nexthop_runners, nh, runner_l)do { if (((nh)->runner_l.tqe_next) != ((void*)0)) (nh)->
runner_l.tqe_next->runner_l.tqe_prev = (nh)->runner_l.tqe_prev
; else (&nexthop_runners)->tqh_last = (nh)->runner_l
.tqe_prev; *(nh)->runner_l.tqe_prev = (nh)->runner_l.tqe_next
; ; ; } while (0);
1761 }
1762
1763 if (msg->connected) {
1764 nh->flags |= NEXTHOP_CONNECTED0x01;
1765 memcpy(&nh->true_nexthop, &nh->exit_nexthop,
1766 sizeof(nh->true_nexthop));
1767 } else
1768 memcpy(&nh->true_nexthop, &msg->gateway,
1769 sizeof(nh->true_nexthop));
1770
1771 memcpy(&nh->nexthop_net, &msg->net,
1772 sizeof(nh->nexthop_net));
1773 nh->nexthop_netlen = msg->netlen;
1774
1775 nh->next_prefix = LIST_FIRST(&nh->prefix_h)((&nh->prefix_h)->lh_first);
1776 if (nh->next_prefix != NULL((void*)0)) {
1777 TAILQ_INSERT_HEAD(&nexthop_runners, nh, runner_l)do { if (((nh)->runner_l.tqe_next = (&nexthop_runners)
->tqh_first) != ((void*)0)) (&nexthop_runners)->tqh_first
->runner_l.tqe_prev = &(nh)->runner_l.tqe_next; else
(&nexthop_runners)->tqh_last = &(nh)->runner_l
.tqe_next; (&nexthop_runners)->tqh_first = (nh); (nh)->
runner_l.tqe_prev = &(&nexthop_runners)->tqh_first
; } while (0);
1778 log_debug("nexthop %s update starting",
1779 log_addr(&nh->exit_nexthop));
1780 }
1781}
1782
1783void
1784nexthop_modify(struct nexthop *setnh, enum action_types type, u_int8_t aid,
1785 struct nexthop **nexthop, u_int8_t *flags)
1786{
1787 switch (type) {
1788 case ACTION_SET_NEXTHOP_REJECT:
1789 *flags = NEXTHOP_REJECT0x02;
1790 break;
1791 case ACTION_SET_NEXTHOP_BLACKHOLE:
1792 *flags = NEXTHOP_BLACKHOLE0x04;
1793 break;
1794 case ACTION_SET_NEXTHOP_NOMODIFY:
1795 *flags = NEXTHOP_NOMODIFY0x08;
1796 break;
1797 case ACTION_SET_NEXTHOP_SELF:
1798 *flags = NEXTHOP_SELF0x01;
1799 break;
1800 case ACTION_SET_NEXTHOP_REF:
1801 /*
1802 * it is possible that a prefix matches but has the wrong
1803 * address family for the set nexthop. In this case ignore it.
1804 */
1805 if (aid != setnh->exit_nexthop.aid)
1806 break;
1807 nexthop_unref(*nexthop);
1808 *nexthop = nexthop_ref(setnh);
1809 *flags = 0;
1810 break;
1811 default:
1812 break;
1813 }
1814}
1815
1816void
1817nexthop_link(struct prefix *p)
1818{
1819 if (p->nexthop == NULL((void*)0))
1820 return;
1821
1822 /* no need to link prefixes in RIBs that have no decision process */
1823 if (re_rib(prefix_re(p))->flags & F_RIB_NOEVALUATE0x0002)
1824 return;
1825
1826 p->flags |= PREFIX_NEXTHOP_LINKED0x40;
1827 LIST_INSERT_HEAD(&p->nexthop->prefix_h, p, entry.list.nexthop)do { if (((p)->entry.list.nexthop.le_next = (&p->nexthop
->prefix_h)->lh_first) != ((void*)0)) (&p->nexthop
->prefix_h)->lh_first->entry.list.nexthop.le_prev = &
(p)->entry.list.nexthop.le_next; (&p->nexthop->prefix_h
)->lh_first = (p); (p)->entry.list.nexthop.le_prev = &
(&p->nexthop->prefix_h)->lh_first; } while (0);
1828}
1829
1830void
1831nexthop_unlink(struct prefix *p)
1832{
1833 if (p->nexthop == NULL((void*)0) || (p->flags & PREFIX_NEXTHOP_LINKED0x40) == 0)
1834 return;
1835
1836 if (p == p->nexthop->next_prefix) {
1837 p->nexthop->next_prefix = LIST_NEXT(p, entry.list.nexthop)((p)->entry.list.nexthop.le_next);
1838 /* remove nexthop from list if no prefixes left to update */
1839 if (p->nexthop->next_prefix == NULL((void*)0)) {
1840 TAILQ_REMOVE(&nexthop_runners, p->nexthop, runner_l)do { if (((p->nexthop)->runner_l.tqe_next) != ((void*)0
)) (p->nexthop)->runner_l.tqe_next->runner_l.tqe_prev
= (p->nexthop)->runner_l.tqe_prev; else (&nexthop_runners
)->tqh_last = (p->nexthop)->runner_l.tqe_prev; *(p->
nexthop)->runner_l.tqe_prev = (p->nexthop)->runner_l
.tqe_next; ; ; } while (0);
1841 log_debug("nexthop %s update finished",
1842 log_addr(&p->nexthop->exit_nexthop));
1843 }
1844 }
1845
1846 p->flags &= ~PREFIX_NEXTHOP_LINKED0x40;
1847 LIST_REMOVE(p, entry.list.nexthop)do { if ((p)->entry.list.nexthop.le_next != ((void*)0)) (p
)->entry.list.nexthop.le_next->entry.list.nexthop.le_prev
= (p)->entry.list.nexthop.le_prev; *(p)->entry.list.nexthop
.le_prev = (p)->entry.list.nexthop.le_next; ; ; } while (0
);
1848}
1849
1850struct nexthop *
1851nexthop_get(struct bgpd_addr *nexthop)
1852{
1853 struct nexthop *nh;
1854
1855 nh = nexthop_lookup(nexthop);
1856 if (nh == NULL((void*)0)) {
1857 nh = calloc(1, sizeof(*nh));
1858 if (nh == NULL((void*)0))
1859 fatal("nexthop_alloc");
1860 rdemem.nexthop_cnt++;
1861
1862 LIST_INIT(&nh->prefix_h)do { ((&nh->prefix_h)->lh_first) = ((void*)0); } while
(0);
1863 nh->state = NEXTHOP_LOOKUP;
1864 nexthop_ref(nh); /* take reference for lookup */
1865 nh->exit_nexthop = *nexthop;
1866 LIST_INSERT_HEAD(nexthop_hash(nexthop), nh,do { if (((nh)->nexthop_l.le_next = (nexthop_hash(nexthop)
)->lh_first) != ((void*)0)) (nexthop_hash(nexthop))->lh_first
->nexthop_l.le_prev = &(nh)->nexthop_l.le_next; (nexthop_hash
(nexthop))->lh_first = (nh); (nh)->nexthop_l.le_prev = &
(nexthop_hash(nexthop))->lh_first; } while (0)
1867 nexthop_l)do { if (((nh)->nexthop_l.le_next = (nexthop_hash(nexthop)
)->lh_first) != ((void*)0)) (nexthop_hash(nexthop))->lh_first
->nexthop_l.le_prev = &(nh)->nexthop_l.le_next; (nexthop_hash
(nexthop))->lh_first = (nh); (nh)->nexthop_l.le_prev = &
(nexthop_hash(nexthop))->lh_first; } while (0);
1868
1869 rde_send_nexthop(&nh->exit_nexthop, 1);
1870 }
1871
1872 return nexthop_ref(nh);
1873}
1874
1875struct nexthop *
1876nexthop_ref(struct nexthop *nexthop)
1877{
1878 if (nexthop)
1879 nexthop->refcnt++;
1880 return (nexthop);
1881}
1882
1883int
1884nexthop_unref(struct nexthop *nh)
1885{
1886 if (nh == NULL((void*)0))
1887 return (0);
1888 if (--nh->refcnt > 0)
1889 return (0);
1890
1891 /* sanity check */
1892 if (!LIST_EMPTY(&nh->prefix_h)(((&nh->prefix_h)->lh_first) == ((void*)0)) || nh->state == NEXTHOP_LOOKUP)
1893 fatalx("%s: refcnt error", __func__);
1894
1895 /* is nexthop update running? impossible, that is a refcnt error */
1896 if (nh->next_prefix)
1897 fatalx("%s: next_prefix not NULL", __func__);
1898
1899 LIST_REMOVE(nh, nexthop_l)do { if ((nh)->nexthop_l.le_next != ((void*)0)) (nh)->nexthop_l
.le_next->nexthop_l.le_prev = (nh)->nexthop_l.le_prev; *
(nh)->nexthop_l.le_prev = (nh)->nexthop_l.le_next; ; ; }
while (0);
1900 rde_send_nexthop(&nh->exit_nexthop, 0);
1901
1902 rdemem.nexthop_cnt--;
1903 free(nh);
1904 return (1);
1905}
1906
1907int
1908nexthop_compare(struct nexthop *na, struct nexthop *nb)
1909{
1910 struct bgpd_addr *a, *b;
1911
1912 if (na == nb)
1913 return (0);
1914 if (na == NULL((void*)0))
1915 return (-1);
1916 if (nb == NULL((void*)0))
1917 return (1);
1918
1919 a = &na->exit_nexthop;
1920 b = &nb->exit_nexthop;
1921
1922 if (a->aid != b->aid)
1923 return (a->aid - b->aid);
1924
1925 switch (a->aid) {
1926 case AID_INET1:
1927 if (ntohl(a->v4.s_addr)(__uint32_t)(__builtin_constant_p(a->ba.v4.s_addr) ? (__uint32_t
)(((__uint32_t)(a->ba.v4.s_addr) & 0xff) << 24 |
((__uint32_t)(a->ba.v4.s_addr) & 0xff00) << 8 |
((__uint32_t)(a->ba.v4.s_addr) & 0xff0000) >> 8
| ((__uint32_t)(a->ba.v4.s_addr) & 0xff000000) >>
24) : __swap32md(a->ba.v4.s_addr)) > ntohl(b->v4.s_addr)(__uint32_t)(__builtin_constant_p(b->ba.v4.s_addr) ? (__uint32_t
)(((__uint32_t)(b->ba.v4.s_addr) & 0xff) << 24 |
((__uint32_t)(b->ba.v4.s_addr) & 0xff00) << 8 |
((__uint32_t)(b->ba.v4.s_addr) & 0xff0000) >> 8
| ((__uint32_t)(b->ba.v4.s_addr) & 0xff000000) >>
24) : __swap32md(b->ba.v4.s_addr)))
1928 return (1);
1929 if (ntohl(a->v4.s_addr)(__uint32_t)(__builtin_constant_p(a->ba.v4.s_addr) ? (__uint32_t
)(((__uint32_t)(a->ba.v4.s_addr) & 0xff) << 24 |
((__uint32_t)(a->ba.v4.s_addr) & 0xff00) << 8 |
((__uint32_t)(a->ba.v4.s_addr) & 0xff0000) >> 8
| ((__uint32_t)(a->ba.v4.s_addr) & 0xff000000) >>
24) : __swap32md(a->ba.v4.s_addr)) < ntohl(b->v4.s_addr)(__uint32_t)(__builtin_constant_p(b->ba.v4.s_addr) ? (__uint32_t
)(((__uint32_t)(b->ba.v4.s_addr) & 0xff) << 24 |
((__uint32_t)(b->ba.v4.s_addr) & 0xff00) << 8 |
((__uint32_t)(b->ba.v4.s_addr) & 0xff0000) >> 8
| ((__uint32_t)(b->ba.v4.s_addr) & 0xff000000) >>
24) : __swap32md(b->ba.v4.s_addr)))
1930 return (-1);
1931 return (0);
1932 case AID_INET62:
1933 return (memcmp(&a->v6ba.v6, &b->v6ba.v6, sizeof(struct in6_addr)));
1934 default:
1935 fatalx("nexthop_cmp: unknown af");
1936 }
1937 return (-1);
1938}
1939
1940struct nexthop *
1941nexthop_lookup(struct bgpd_addr *nexthop)
1942{
1943 struct nexthop *nh;
1944
1945 LIST_FOREACH(nh, nexthop_hash(nexthop), nexthop_l)for((nh) = ((nexthop_hash(nexthop))->lh_first); (nh)!= ((void
*)0); (nh) = ((nh)->nexthop_l.le_next)) {
1946 if (memcmp(&nh->exit_nexthop, nexthop,
1947 sizeof(struct bgpd_addr)) == 0)
1948 return (nh);
1949 }
1950 return (NULL((void*)0));
1951}
1952
1953struct nexthop_head *
1954nexthop_hash(struct bgpd_addr *nexthop)
1955{
1956 u_int32_t h = 0;
1957
1958 switch (nexthop->aid) {
1959 case AID_INET1:
1960 h = SipHash24(&nexthoptablekey, &nexthop->v4.s_addr,SipHash((&nexthoptablekey), 2, 4, (&nexthop->ba.v4
.s_addr), (sizeof(nexthop->ba.v4.s_addr)))
1961 sizeof(nexthop->v4.s_addr))SipHash((&nexthoptablekey), 2, 4, (&nexthop->ba.v4
.s_addr), (sizeof(nexthop->ba.v4.s_addr)));
1962 break;
1963 case AID_INET62:
1964 h = SipHash24(&nexthoptablekey, &nexthop->v6,SipHash((&nexthoptablekey), 2, 4, (&nexthop->ba.v6
), (sizeof(struct in6_addr)))
1965 sizeof(struct in6_addr))SipHash((&nexthoptablekey), 2, 4, (&nexthop->ba.v6
), (sizeof(struct in6_addr)));
1966 break;
1967 default:
1968 fatalx("nexthop_hash: unsupported AID %d", nexthop->aid);
1969 }
1970 return (&nexthoptable.nexthop_hashtbl[h & nexthoptable.nexthop_hashmask]);
1971}