Switch the prefixset simpleq into an RB trie. This allows to spot
duplicates in the parser and is a requirement for roa-sets where
conflicts need to be specially handled.
OK?
--
:wq Claudio
Index: bgpd.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/bgpd.c,v
retrieving revision 1.198
diff -u -p -r1.198 bgpd.c
--- bgpd.c 9 Sep 2018 11:00:51 -0000 1.198
+++ bgpd.c 19 Sep 2018 06:34:11 -0000
@@ -437,7 +437,7 @@ reconfigure(char *conffile, struct bgpd_
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_
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);
Index: bgpd.h
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/bgpd.h,v
retrieving revision 1.340
diff -u -p -r1.340 bgpd.h
--- bgpd.h 14 Sep 2018 10:22:11 -0000 1.340
+++ bgpd.h 19 Sep 2018 06:32:47 -0000
@@ -953,15 +953,15 @@ struct filter_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;
};
@@ -1085,6 +1085,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);
Index: config.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/config.c,v
retrieving revision 1.73
diff -u -p -r1.73 config.c
--- config.c 9 Sep 2018 11:00:51 -0000 1.73
+++ config.c 19 Sep 2018 06:35:49 -0000
@@ -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);
Index: parse.y
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/parse.y,v
retrieving revision 1.353
diff -u -p -r1.353 parse.y
--- parse.y 14 Sep 2018 10:22:11 -0000 1.353
+++ parse.y 19 Sep 2018 06:35:02 -0000
@@ -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;
}
Index: printconf.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/printconf.c,v
retrieving revision 1.119
diff -u -p -r1.119 printconf.c
--- printconf.c 13 Sep 2018 11:25:41 -0000 1.119
+++ printconf.c 19 Sep 2018 06:32:47 -0000
@@ -451,7 +451,7 @@ print_prefixsets(struct prefixset_head *
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
