On Fri, Dec 18, 2020 at 11:36:33AM +0100, Claudio Jeker wrote:
> In preparation for RTR support this diff changes the internal
> representation of roa-set to a simple RB tree based on struct roa.
> The big difference is that overlapping roas, e.g.
> 10/8 source-as 3
> 10/8 maxlen 24 source-as 3
> are now merged in the RDE and so bgpd -nv will show both entries instead
> of only the second one.
>
> On my testbox there is no difference in OVS state between a -current bgpd
> and the one with this diff applied. More testing welcome.
Ping. I would like to get this in so I can reduce the size of my RTR work
in progress diff.
--
:wq Claudio
Index: bgpd.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/bgpd.c,v
retrieving revision 1.230
diff -u -p -r1.230 bgpd.c
--- bgpd.c 5 Nov 2020 11:52:59 -0000 1.230
+++ bgpd.c 18 Dec 2020 10:27:44 -0000
@@ -502,6 +502,7 @@ send_config(struct bgpd_config *conf)
struct as_set *aset;
struct prefixset *ps;
struct prefixset_item *psi, *npsi;
+ struct roa *roa, *nroa;
reconfpending = 2; /* one per child */
@@ -567,7 +568,6 @@ send_config(struct bgpd_config *conf)
if (imsg_compose(ibuf_rde, IMSG_RECONF_PREFIX_SET_ITEM,
0, 0, -1, psi, sizeof(*psi)) == -1)
return (-1);
- set_free(psi->set);
free(psi);
}
free(ps);
@@ -579,23 +579,12 @@ send_config(struct bgpd_config *conf)
if (imsg_compose(ibuf_rde, IMSG_RECONF_ORIGIN_SET, 0, 0, -1,
ps->name, sizeof(ps->name)) == -1)
return (-1);
- RB_FOREACH_SAFE(psi, prefixset_tree, &ps->psitems, npsi) {
- struct roa_set *rs;
- size_t i, l, n;
- RB_REMOVE(prefixset_tree, &ps->psitems, psi);
- rs = set_get(psi->set, &n);
- for (i = 0; i < n; i += l) {
- l = (n - i > 1024 ? 1024 : n - i);
- if (imsg_compose(ibuf_rde,
- IMSG_RECONF_ROA_SET_ITEMS,
- 0, 0, -1, rs + i, l * sizeof(*rs)) == -1)
- return -1;
- }
- if (imsg_compose(ibuf_rde, IMSG_RECONF_PREFIX_SET_ITEM,
- 0, 0, -1, psi, sizeof(*psi)) == -1)
+ RB_FOREACH_SAFE(roa, roa_tree, &ps->roaitems, nroa) {
+ RB_REMOVE(roa_tree, &conf->roa, roa);
+ if (imsg_compose(ibuf_rde, IMSG_RECONF_ROA_ITEM, 0, 0,
+ -1, roa, sizeof(*roa)) == -1)
return (-1);
- set_free(psi->set);
- free(psi);
+ free(roa);
}
free(ps);
}
@@ -604,23 +593,12 @@ send_config(struct bgpd_config *conf)
if (imsg_compose(ibuf_rde, IMSG_RECONF_ROA_SET, 0, 0, -1,
NULL, 0) == -1)
return (-1);
- RB_FOREACH_SAFE(psi, prefixset_tree, &conf->roa, npsi) {
- struct roa_set *rs;
- size_t i, l, n;
- RB_REMOVE(prefixset_tree, &conf->roa, psi);
- rs = set_get(psi->set, &n);
- for (i = 0; i < n; i += l) {
- l = (n - i > 1024 ? 1024 : n - i);
- if (imsg_compose(ibuf_rde,
- IMSG_RECONF_ROA_SET_ITEMS,
- 0, 0, -1, rs + i, l * sizeof(*rs)) == -1)
- return -1;
- }
- if (imsg_compose(ibuf_rde, IMSG_RECONF_PREFIX_SET_ITEM,
- 0, 0, -1, psi, sizeof(*psi)) == -1)
+ RB_FOREACH_SAFE(roa, roa_tree, &conf->roa, nroa) {
+ RB_REMOVE(roa_tree, &conf->roa, roa);
+ if (imsg_compose(ibuf_rde, IMSG_RECONF_ROA_ITEM, 0, 0,
+ -1, roa, sizeof(*roa)) == -1)
return (-1);
- set_free(psi->set);
- free(psi);
+ free(roa);
}
}
Index: bgpd.h
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/bgpd.h,v
retrieving revision 1.405
diff -u -p -r1.405 bgpd.h
--- bgpd.h 5 Nov 2020 11:52:59 -0000 1.405
+++ bgpd.h 18 Dec 2020 10:27:21 -0000
@@ -264,6 +264,21 @@ struct rde_prefixset {
};
SIMPLEQ_HEAD(rde_prefixset_head, rde_prefixset);
+struct roa {
+ RB_ENTRY(roa) entry;
+ uint8_t aid;
+ uint8_t prefixlen;
+ uint8_t maxlen;
+ uint8_t pad;
+ uint32_t asnum;
+ union {
+ struct in_addr inet;
+ struct in6_addr inet6;
+ } prefix;
+};
+
+RB_HEAD(roa_tree, roa);
+
struct set_table;
struct as_set;
SIMPLEQ_HEAD(as_set_head, as_set);
@@ -280,7 +295,7 @@ struct bgpd_config {
struct mrt_head *mrt;
struct prefixset_head prefixsets;
struct prefixset_head originsets;
- struct prefixset_tree roa;
+ struct roa_tree roa;
struct rde_prefixset_head rde_prefixsets;
struct rde_prefixset_head rde_originsets;
struct rde_prefixset rde_roa;
@@ -492,7 +507,7 @@ enum imsg_type {
IMSG_RECONF_AS_SET_DONE,
IMSG_RECONF_ORIGIN_SET,
IMSG_RECONF_ROA_SET,
- IMSG_RECONF_ROA_SET_ITEMS,
+ IMSG_RECONF_ROA_ITEM,
IMSG_RECONF_DRAIN,
IMSG_RECONF_DONE,
IMSG_UPDATE,
@@ -1035,13 +1050,13 @@ struct roa_set {
struct prefixset_item {
struct filter_prefix p;
RB_ENTRY(prefixset_item) entry;
- struct set_table *set;
};
struct prefixset {
int sflags;
char name[SET_NAME_LEN];
struct prefixset_tree psitems;
+ struct roa_tree roaitems;
SIMPLEQ_ENTRY(prefixset) entry;
};
@@ -1181,12 +1196,13 @@ void free_config(struct bgpd_config *);
void free_prefixsets(struct prefixset_head *);
void free_rde_prefixsets(struct rde_prefixset_head *);
void free_prefixtree(struct prefixset_tree *);
+void free_roatree(struct roa_tree *);
void filterlist_free(struct filter_head *);
int host(const char *, struct bgpd_addr *, u_int8_t *);
u_int32_t get_bgpid(void);
void expand_networks(struct bgpd_config *);
-int prefixset_cmp(struct prefixset_item *, struct prefixset_item *);
RB_PROTOTYPE(prefixset_tree, prefixset_item, entry, prefixset_cmp);
+RB_PROTOTYPE(roa_tree, roa, entry, roa_cmp);
/* kroute.c */
int kr_init(int *);
@@ -1287,8 +1303,7 @@ int set_equal(const struct
set_table
/* rde_trie.c */
int trie_add(struct trie_head *, struct bgpd_addr *, u_int8_t, u_int8_t,
u_int8_t);
-int trie_roa_add(struct trie_head *, struct bgpd_addr *, u_int8_t,
- struct set_table *);
+int trie_roa_add(struct trie_head *, struct roa *);
void trie_free(struct trie_head *);
int trie_match(struct trie_head *, struct bgpd_addr *, u_int8_t, int);
int trie_roa_check(struct trie_head *, struct bgpd_addr *, u_int8_t,
Index: config.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/config.c,v
retrieving revision 1.95
diff -u -p -r1.95 config.c
--- config.c 14 Feb 2020 13:54:31 -0000 1.95
+++ config.c 18 Dec 2020 10:28:00 -0000
@@ -117,6 +117,7 @@ free_prefixsets(struct prefixset_head *p
while (!SIMPLEQ_EMPTY(psh)) {
ps = SIMPLEQ_FIRST(psh);
+ free_roatree(&ps->roaitems);
free_prefixtree(&ps->psitems);
SIMPLEQ_REMOVE_HEAD(psh, entry);
free(ps);
@@ -146,12 +147,22 @@ free_prefixtree(struct prefixset_tree *p
RB_FOREACH_SAFE(psi, prefixset_tree, p, npsi) {
RB_REMOVE(prefixset_tree, p, psi);
- set_free(psi->set);
free(psi);
}
}
void
+free_roatree(struct roa_tree *r)
+{
+ struct roa *roa, *nroa;
+
+ RB_FOREACH_SAFE(roa, roa_tree, r, nroa) {
+ RB_REMOVE(roa_tree, r, roa);
+ free(roa);
+ }
+}
+
+void
free_config(struct bgpd_config *conf)
{
struct peer *p, *next;
@@ -166,7 +177,7 @@ free_config(struct bgpd_config *conf)
free_rde_prefixsets(&conf->rde_prefixsets);
free_rde_prefixsets(&conf->rde_originsets);
as_sets_free(&conf->as_sets);
- free_prefixtree(&conf->roa);
+ free_roatree(&conf->roa);
while ((la = TAILQ_FIRST(conf->listen_addrs)) != NULL) {
TAILQ_REMOVE(conf->listen_addrs, la, entry);
@@ -230,7 +241,7 @@ merge_config(struct bgpd_config *xconf,
mrt_mergeconfig(xconf->mrt, conf->mrt);
/* switch the roa, first remove the old one */
- free_prefixtree(&xconf->roa);
+ free_roatree(&xconf->roa);
/* then move the RB tree root */
RB_ROOT(&xconf->roa) = RB_ROOT(&conf->roa);
RB_ROOT(&conf->roa) = NULL;
@@ -527,7 +538,7 @@ expand_networks(struct bgpd_config *c)
}
}
-int
+static inline int
prefixset_cmp(struct prefixset_item *a, struct prefixset_item *b)
{
int i;
@@ -571,3 +582,20 @@ prefixset_cmp(struct prefixset_item *a,
}
RB_GENERATE(prefixset_tree, prefixset_item, entry, prefixset_cmp);
+
+static inline int
+roa_cmp(struct roa *a, struct roa *b)
+{
+ size_t len = 4 + sizeof(a->asnum);
+
+ if (a->aid == b->aid) {
+ if (a->aid == AID_INET)
+ len += sizeof(a->prefix.inet);
+ else
+ len += sizeof(a->prefix.inet6);
+ }
+
+ return memcmp(&a->aid, &b->aid, len);
+}
+
+RB_GENERATE(roa_tree, roa, entry, roa_cmp);
Index: parse.y
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/parse.y,v
retrieving revision 1.410
diff -u -p -r1.410 parse.y
--- parse.y 27 Oct 2020 19:13:34 -0000 1.410
+++ parse.y 18 Dec 2020 08:40:44 -0000
@@ -94,7 +94,7 @@ static struct peer *curgroup;
static struct rde_rib *currib;
static struct l3vpn *curvpn;
static struct prefixset *curpset, *curoset;
-static struct prefixset_tree *curpsitree;
+static struct roa_tree *curroatree;
static struct filter_head *filter_l;
static struct filter_head *peerfilter_l;
static struct filter_head *groupfilter_l;
@@ -498,9 +498,9 @@ prefixset_item : prefix prefixlenop
{
;
roa_set : ROASET '{' optnl {
- curpsitree = &conf->roa;
+ curroatree = &conf->roa;
} roa_set_l optnl '}' {
- curpsitree = NULL;
+ curroatree = NULL;
}
| ROASET '{' optnl '}' /* nothing */
;
@@ -510,12 +510,12 @@ origin_set : ORIGINSET STRING '{' optnl
free($2);
YYERROR;
}
- curpsitree = &curoset->psitems;
+ curroatree = &curoset->roaitems;
free($2);
} roa_set_l optnl '}' {
SIMPLEQ_INSERT_TAIL(&conf->originsets, curoset, entry);
curoset = NULL;
- curpsitree = NULL;
+ curroatree = NULL;
}
| ORIGINSET STRING '{' optnl '}' {
if ((curoset = new_prefix_set($2, 1)) == NULL) {
@@ -525,7 +525,7 @@ origin_set : ORIGINSET STRING '{' optnl
free($2);
SIMPLEQ_INSERT_TAIL(&conf->originsets, curoset, entry);
curoset = NULL;
- curpsitree = NULL;
+ curroatree = NULL;
}
;
@@ -537,6 +537,7 @@ roa_set_l : prefixset_item SOURCEAS as4n
YYERROR;
}
add_roa_set($1, $3, $1->p.len_max);
+ free($1);
}
| roa_set_l comma prefixset_item SOURCEAS as4number_any {
if ($3->p.len_min != $3->p.len) {
@@ -546,6 +547,7 @@ roa_set_l : prefixset_item SOURCEAS as4n
YYERROR;
}
add_roa_set($3, $5, $3->p.len_max);
+ free($3);
}
;
@@ -4502,7 +4504,7 @@ new_prefix_set(char *name, int is_roa)
struct prefixset *pset;
if (is_roa) {
- type = "roa-set";
+ type = "origin-set";
sets = &conf->originsets;
}
@@ -4520,38 +4522,35 @@ new_prefix_set(char *name, int is_roa)
return NULL;
}
RB_INIT(&pset->psitems);
+ RB_INIT(&pset->roaitems);
return pset;
}
static void
add_roa_set(struct prefixset_item *npsi, u_int32_t as, u_int8_t max)
{
- struct prefixset_item *psi;
- struct roa_set rs, *rsp;
+ struct roa *roa, *r;
- /* no prefixlen option in this tree */
- npsi->p.op = OP_NONE;
- npsi->p.len_max = npsi->p.len_min = npsi->p.len;
- psi = RB_INSERT(prefixset_tree, curpsitree, npsi);
- if (psi == NULL)
- psi = npsi;
- else
- free(npsi);
+ if ((roa = calloc(1, sizeof(*roa))) == NULL)
+ fatal("add_roa_set");
- if (psi->set == NULL)
- if ((psi->set = set_new(1, sizeof(rs))) == NULL)
- fatal("set_new");
-
- /* merge sets with same key, longer maxlen wins */
- if ((rsp = set_match(psi->set, as)) != NULL) {
- if (rsp->maxlen < max)
- rsp->maxlen = max;
- } else {
- rs.as = as;
- rs.maxlen = max;
- if (set_add(psi->set, &rs, 1) != 0)
- fatal("as_set_new");
- /* prep data so that set_match works */
- set_prep(psi->set);
+ roa->aid = npsi->p.addr.aid;
+ roa->prefixlen = npsi->p.len;
+ roa->maxlen = max;
+ roa->asnum = as;
+ switch (roa->aid) {
+ case AID_INET:
+ roa->prefix.inet = npsi->p.addr.v4;
+ break;
+ case AID_INET6:
+ roa->prefix.inet6 = npsi->p.addr.v6;
+ break;
+ default:
+ fatalx("Bad address family for roa_set address");
}
+
+ r = RB_INSERT(roa_tree, curroatree, roa);
+ if (r != NULL)
+ /* just ignore duplicates */
+ free(roa);
}
Index: printconf.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/printconf.c,v
retrieving revision 1.143
diff -u -p -r1.143 printconf.c
--- printconf.c 5 Nov 2020 11:51:13 -0000 1.143
+++ printconf.c 18 Dec 2020 08:40:44 -0000
@@ -41,7 +41,7 @@ void print_network(struct network_conf
void print_as_sets(struct as_set_head *);
void print_prefixsets(struct prefixset_head *);
void print_originsets(struct prefixset_head *);
-void print_roa(struct prefixset_tree *p);
+void print_roa(struct roa_tree *);
void print_peer(struct peer_config *, struct bgpd_config *,
const char *);
const char *print_auth_alg(u_int8_t);
@@ -535,46 +535,42 @@ void
print_originsets(struct prefixset_head *psh)
{
struct prefixset *ps;
- struct prefixset_item *psi;
- struct roa_set *rs;
- size_t i, n;
+ struct roa *roa;
+ struct bgpd_addr addr;
SIMPLEQ_FOREACH(ps, psh, entry) {
printf("origin-set \"%s\" {", ps->name);
- RB_FOREACH(psi, prefixset_tree, &ps->psitems) {
- rs = set_get(psi->set, &n);
- for (i = 0; i < n; i++) {
- printf("\n\t");
- print_prefix(&psi->p);
- if (psi->p.len != rs[i].maxlen)
- printf(" maxlen %u", rs[i].maxlen);
- printf(" source-as %u", rs[i].as);
- }
+ RB_FOREACH(roa, roa_tree, &ps->roaitems) {
+ printf("\n\t");
+ addr.aid = roa->aid;
+ addr.v6 = roa->prefix.inet6;
+ printf("%s/%u", log_addr(&addr), roa->prefixlen);
+ if (roa->prefixlen != roa->maxlen)
+ printf(" maxlen %u", roa->maxlen);
+ printf(" source-as %u", roa->asnum);
}
printf("\n}\n\n");
}
}
void
-print_roa(struct prefixset_tree *p)
+print_roa(struct roa_tree *r)
{
- struct prefixset_item *psi;
- struct roa_set *rs;
- size_t i, n;
+ struct roa *roa;
+ struct bgpd_addr addr;
- if (RB_EMPTY(p))
+ if (RB_EMPTY(r))
return;
printf("roa-set {");
- RB_FOREACH(psi, prefixset_tree, p) {
- rs = set_get(psi->set, &n);
- for (i = 0; i < n; i++) {
- printf("\n\t");
- print_prefix(&psi->p);
- if (psi->p.len != rs[i].maxlen)
- printf(" maxlen %u", rs[i].maxlen);
- printf(" source-as %u", rs[i].as);
- }
+ RB_FOREACH(roa, roa_tree, r) {
+ printf("\n\t");
+ addr.aid = roa->aid;
+ addr.v6 = roa->prefix.inet6;
+ printf("%s/%u", log_addr(&addr), roa->prefixlen);
+ if (roa->prefixlen != roa->maxlen)
+ printf(" maxlen %u", roa->maxlen);
+ printf(" source-as %u", roa->asnum);
}
printf("\n}\n\n");
}
Index: rde.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde.c,v
retrieving revision 1.507
diff -u -p -r1.507 rde.c
--- rde.c 4 Dec 2020 11:57:13 -0000 1.507
+++ rde.c 18 Dec 2020 08:40:44 -0000
@@ -614,10 +614,10 @@ rde_dispatch_imsg_parent(struct imsgbuf
{
static struct rde_prefixset *last_prefixset;
static struct as_set *last_as_set;
- static struct set_table *last_set;
static struct l3vpn *vpn;
struct imsg imsg;
struct mrt xmrt;
+ struct roa roa;
struct rde_rib rr;
struct filterstate state;
struct imsgbuf *i;
@@ -813,24 +813,18 @@ rde_dispatch_imsg_parent(struct imsgbuf
entry);
}
last_prefixset = ps;
- last_set = NULL;
break;
case IMSG_RECONF_ROA_SET:
strlcpy(nconf->rde_roa.name, "RPKI ROA",
sizeof(nconf->rde_roa.name));
last_prefixset = &nconf->rde_roa;
- last_set = NULL;
break;
- case IMSG_RECONF_ROA_SET_ITEMS:
- nmemb = imsg.hdr.len - IMSG_HEADER_SIZE;
- nmemb /= sizeof(struct roa_set);
- if (last_set == NULL) {
- last_set = set_new(1, sizeof(struct roa_set));
- if (last_set == NULL)
- fatal(NULL);
- }
- if (set_add(last_set, imsg.data, nmemb) != 0)
- fatal(NULL);
+ case IMSG_RECONF_ROA_ITEM:
+ if (imsg.hdr.len - IMSG_HEADER_SIZE !=
+ sizeof(roa))
+ fatalx("IMSG_RECONF_PREFIX_SET_ITEM bad len");
+ memcpy(&roa, imsg.data, sizeof(roa));
+ rv = trie_roa_add(&last_prefixset->th, &roa);
break;
case IMSG_RECONF_PREFIX_SET_ITEM:
if (imsg.hdr.len - IMSG_HEADER_SIZE !=
@@ -839,16 +833,9 @@ rde_dispatch_imsg_parent(struct imsgbuf
memcpy(&psi, imsg.data, sizeof(psi));
if (last_prefixset == NULL)
fatalx("King Bula has no prefixset");
- if (last_set) {
- set_prep(last_set);
- rv = trie_roa_add(&last_prefixset->th,
- &psi.p.addr, psi.p.len, last_set);
- last_set = NULL;
- } else {
- rv = trie_add(&last_prefixset->th,
- &psi.p.addr, psi.p.len,
- psi.p.len_min, psi.p.len_max);
- }
+ rv = trie_add(&last_prefixset->th,
+ &psi.p.addr, psi.p.len,
+ psi.p.len_min, psi.p.len_max);
if (rv == -1)
log_warnx("trie_add(%s) %s/%u) failed",
last_prefixset->name, log_addr(&psi.p.addr),
Index: rde_trie.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde_trie.c,v
retrieving revision 1.10
diff -u -p -r1.10 rde_trie.c
--- rde_trie.c 26 Oct 2018 16:53:55 -0000 1.10
+++ rde_trie.c 18 Dec 2020 08:40:44 -0000
@@ -378,30 +378,30 @@ trie_add(struct trie_head *th, struct bg
* is a match.
*/
int
-trie_roa_add(struct trie_head *th, struct bgpd_addr *prefix, u_int8_t plen,
- struct set_table *set)
+trie_roa_add(struct trie_head *th, struct roa *roa)
{
struct tentry_v4 *n4;
struct tentry_v6 *n6;
struct set_table **stp;
+ struct roa_set rs, *rsp;
/* ignore possible default route since it does not make sense */
- switch (prefix->aid) {
+ switch (roa->aid) {
case AID_INET:
- if (plen > 32)
+ if (roa->prefixlen > 32)
return -1;
- n4 = trie_add_v4(th, &prefix->v4, plen);
+ n4 = trie_add_v4(th, &roa->prefix.inet, roa->prefixlen);
if (n4 == NULL)
return -1;
stp = &n4->set;
break;
case AID_INET6:
- if (plen > 128)
+ if (roa->prefixlen > 128)
return -1;
- n6 = trie_add_v6(th, &prefix->v6, plen);
+ n6 = trie_add_v6(th, &roa->prefix.inet6, roa->prefixlen);
if (n6 == NULL)
return -1;
stp = &n6->set;
@@ -411,10 +411,22 @@ trie_roa_add(struct trie_head *th, struc
return -1;
}
- /* set_table already set, error out */
- if (*stp != NULL)
- return -1;
- *stp = set;
+ if (*stp == NULL)
+ if ((*stp = set_new(1, sizeof(rs))) == NULL)
+ return -1;
+
+ /* merge sets with same key, longer maxlen wins */
+ if ((rsp = set_match(*stp, roa->asnum)) != NULL) {
+ if (rsp->maxlen < roa->maxlen)
+ rsp->maxlen = roa->maxlen;
+ } else {
+ rs.as = roa->asnum;
+ rs.maxlen = roa->maxlen;
+ if (set_add(*stp, &rs, 1) != 0)
+ return -1;
+ /* prep data so that set_match works */
+ set_prep(*stp);
+ }
return 0;
}
