ok.
Claudio Jeker([email protected]) on 2020.12.29 10:23:53 +0100: > 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; > } >
