From d32b24c8d7eaf888075a200b4094d9f6d09d0464 Mon Sep 17 00:00:00 2001 From: claudio Date: Thu, 20 Sep 2018 07:46:39 +0000 Subject: [PATCH] Switch prefixset to an RB_TREE instead of a SIMPLEQ. This allows to trigger on duplicates (which are only reported) but is needed as a preparation step for roa-sets. OK benno@ denis@ --- usr.sbin/bgpd/bgpd.c | 8 +++--- usr.sbin/bgpd/bgpd.h | 12 +++++---- usr.sbin/bgpd/config.c | 56 ++++++++++++++++++++++++++++++++++----- usr.sbin/bgpd/parse.y | 31 +++++++++++++++++++--- usr.sbin/bgpd/printconf.c | 4 +-- 5 files changed, 90 insertions(+), 21 deletions(-) diff --git a/usr.sbin/bgpd/bgpd.c b/usr.sbin/bgpd/bgpd.c index c06100781c9..239eccebdac 100644 --- a/usr.sbin/bgpd/bgpd.c +++ b/usr.sbin/bgpd/bgpd.c @@ -1,4 +1,4 @@ -/* $OpenBSD: bgpd.c,v 1.198 2018/09/09 11:00:51 benno Exp $ */ +/* $OpenBSD: bgpd.c,v 1.199 2018/09/20 07:46:39 claudio Exp $ */ /* * Copyright (c) 2003, 2004 Henning Brauer @@ -437,7 +437,7 @@ reconfigure(char *conffile, struct bgpd_config *conf, struct peer **peer_l) struct rde_rib *rr; struct rdomain *rd; struct prefixset *ps; - struct prefixset_item *psi; + struct prefixset_item *psi, *npsi; if (reconfpending) { log_info("previous reload still running"); @@ -510,8 +510,8 @@ reconfigure(char *conffile, struct bgpd_config *conf, struct peer **peer_l) if (imsg_compose(ibuf_rde, IMSG_RECONF_PREFIXSET, 0, 0, -1, ps->name, sizeof(ps->name)) == -1) return (-1); - while ((psi = SIMPLEQ_FIRST(&ps->psitems)) != NULL) { - SIMPLEQ_REMOVE_HEAD(&ps->psitems, entry); + RB_FOREACH_SAFE(psi, prefixset_tree, &ps->psitems, npsi) { + RB_REMOVE(prefixset_tree, &ps->psitems, psi); if (imsg_compose(ibuf_rde, IMSG_RECONF_PREFIXSETITEM, 0, 0, -1, psi, sizeof(*psi)) == -1) return (-1); diff --git a/usr.sbin/bgpd/bgpd.h b/usr.sbin/bgpd/bgpd.h index f60372f2aa3..cad8b49714b 100644 --- a/usr.sbin/bgpd/bgpd.h +++ b/usr.sbin/bgpd/bgpd.h @@ -1,4 +1,4 @@ -/* $OpenBSD: bgpd.h,v 1.341 2018/09/18 15:14:07 claudio Exp $ */ +/* $OpenBSD: bgpd.h,v 1.342 2018/09/20 07:46:39 claudio Exp $ */ /* * Copyright (c) 2003, 2004 Henning Brauer @@ -958,15 +958,15 @@ struct roa_set { }; struct prefixset_item { - struct filter_prefix p; - SIMPLEQ_ENTRY(prefixset_item) entry; + struct filter_prefix p; + RB_ENTRY(prefixset_item) entry; }; -SIMPLEQ_HEAD(prefixset_items_h, prefixset_item); +RB_HEAD(prefixset_tree, prefixset_item); struct prefixset { int sflags; char name[SET_NAME_LEN]; - struct prefixset_items_h psitems; + struct prefixset_tree psitems; SIMPLEQ_ENTRY(prefixset) entry; }; @@ -1090,6 +1090,8 @@ void filterlist_free(struct filter_head *); int host(const char *, struct bgpd_addr *, u_int8_t *); void copy_filterset(struct filter_set_head *, struct filter_set_head *); void expand_networks(struct bgpd_config *); +int prefixset_cmp(struct prefixset_item *, struct prefixset_item *); +RB_PROTOTYPE(prefixset_tree, prefixset_item, entry, prefixset_cmp); /* kroute.c */ int kr_init(void); diff --git a/usr.sbin/bgpd/config.c b/usr.sbin/bgpd/config.c index 1c0984facaf..b34d7aaec5e 100644 --- a/usr.sbin/bgpd/config.c +++ b/usr.sbin/bgpd/config.c @@ -1,4 +1,4 @@ -/* $OpenBSD: config.c,v 1.73 2018/09/09 11:00:51 benno Exp $ */ +/* $OpenBSD: config.c,v 1.74 2018/09/20 07:46:39 claudio Exp $ */ /* * Copyright (c) 2003, 2004, 2005 Henning Brauer @@ -120,16 +120,15 @@ void free_prefixsets(struct prefixset_head *psh) { struct prefixset *ps; - struct prefixset_item *psi; + struct prefixset_item *psi, *npsi; if (psh == NULL) return; while (!SIMPLEQ_EMPTY(psh)) { ps = SIMPLEQ_FIRST(psh); - while (!SIMPLEQ_EMPTY(&ps->psitems)) { - psi = SIMPLEQ_FIRST(&ps->psitems); - SIMPLEQ_REMOVE_HEAD(&ps->psitems, entry); + RB_FOREACH_SAFE(psi, prefixset_tree, &ps->psitems, npsi) { + RB_REMOVE(prefixset_tree, &ps->psitems, psi); free(psi); } SIMPLEQ_REMOVE_HEAD(psh, entry); @@ -529,7 +528,7 @@ expand_networks(struct bgpd_config *c) == NULL) fatal("%s: prefixset %s not found", __func__, n->net.psname); - SIMPLEQ_FOREACH(psi, &ps->psitems, entry) { + RB_FOREACH(psi, prefixset_tree, &ps->psitems) { if ((m = calloc(1, sizeof(struct network))) == NULL) fatal(NULL); @@ -546,3 +545,48 @@ expand_networks(struct bgpd_config *c) } } } + +int +prefixset_cmp(struct prefixset_item *a, struct prefixset_item *b) +{ + int i; + + if (a->p.addr.aid < b->p.addr.aid) + return (-1); + if (a->p.addr.aid > b->p.addr.aid) + return (1); + + switch (a->p.addr.aid) { + case AID_INET: + if (ntohl(a->p.addr.v4.s_addr) < ntohl(b->p.addr.v4.s_addr)) + return (-1); + if (ntohl(a->p.addr.v4.s_addr) > ntohl(b->p.addr.v4.s_addr)) + return (1); + break; + case AID_INET6: + i = memcmp(&a->p.addr.v6, &b->p.addr.v6, + sizeof(struct in6_addr)); + if (i > 0) + return (1); + if (i < 0) + return (-1); + break; + default: + fatalx("%s: unknown af", __func__); + } + if (a->p.len < b->p.len) + return (-1); + if (a->p.len > b->p.len) + return (1); + if (a->p.len_min < b->p.len_min) + return (-1); + if (a->p.len_min > b->p.len_min) + return (1); + if (a->p.len_max < b->p.len_max) + return (-1); + if (a->p.len_max > b->p.len_max) + return (1); + return (0); +} + +RB_GENERATE(prefixset_tree, prefixset_item, entry, prefixset_cmp); diff --git a/usr.sbin/bgpd/parse.y b/usr.sbin/bgpd/parse.y index 4c4fec3ad1a..31266d2dde0 100644 --- a/usr.sbin/bgpd/parse.y +++ b/usr.sbin/bgpd/parse.y @@ -1,4 +1,4 @@ -/* $OpenBSD: parse.y,v 1.353 2018/09/14 10:22:11 claudio Exp $ */ +/* $OpenBSD: parse.y,v 1.354 2018/09/20 07:46:39 claudio Exp $ */ /* * Copyright (c) 2002, 2003, 2004 Henning Brauer @@ -443,14 +443,37 @@ prefixset : PREFIXSET STRING '{' optnl { } prefixset_l : prefixset_item { - SIMPLEQ_INSERT_TAIL(&curpset->psitems, $1, entry); + struct prefixset_item *psi; + psi = RB_INSERT(prefixset_tree, &curpset->psitems, $1); + if (psi != NULL) { + if (cmd_opts & BGPD_OPT_VERBOSE2) + log_warnx("warning: duplicate entry in " + "prefixset \"%s\" for %s/%u", + curpset->name, + log_addr(&$1->p.addr), $1->p.len); + free($1); + } } | prefixset_l comma prefixset_item { - SIMPLEQ_INSERT_TAIL(&curpset->psitems, $3, entry); + struct prefixset_item *psi; + psi = RB_INSERT(prefixset_tree, &curpset->psitems, $3); + if (psi != NULL) { + if (cmd_opts & BGPD_OPT_VERBOSE2) + log_warnx("warning: duplicate entry in " + "prefixset \"%s\" for %s/%u", + curpset->name, + log_addr(&$3->p.addr), $3->p.len); + free($3); + } } ; prefixset_item : prefix prefixlenop { + if ($2.op != OP_NONE && $2.op != OP_RANGE) { + yyerror("unsupported prefixlen operation in " + "prefix-set"); + YYERROR; + } if (($$ = calloc(1, sizeof(*$$))) == NULL) fatal(NULL); memcpy(&$$->p.addr, &$1.prefix, sizeof($$->p.addr)); @@ -4223,6 +4246,6 @@ new_prefix_set(char *name) name, sizeof(curpset->name) - 1); return -1; } - SIMPLEQ_INIT(&curpset->psitems); + RB_INIT(&curpset->psitems); return 0; } diff --git a/usr.sbin/bgpd/printconf.c b/usr.sbin/bgpd/printconf.c index 48b1404b47b..43d4b31060e 100644 --- a/usr.sbin/bgpd/printconf.c +++ b/usr.sbin/bgpd/printconf.c @@ -1,4 +1,4 @@ -/* $OpenBSD: printconf.c,v 1.119 2018/09/13 11:25:41 claudio Exp $ */ +/* $OpenBSD: printconf.c,v 1.120 2018/09/20 07:46:39 claudio Exp $ */ /* * Copyright (c) 2003, 2004 Henning Brauer @@ -451,7 +451,7 @@ print_prefixsets(struct prefixset_head *psh) SIMPLEQ_FOREACH(ps, psh, entry) { int count = 0; printf("prefix-set \"%s\" {", ps->name); - SIMPLEQ_FOREACH(psi, &ps->psitems, entry) { + RB_FOREACH(psi, prefixset_tree, &ps->psitems) { if (count++ % 2 == 0) printf("\n\t"); else -- 2.20.1