On Wed, Sep 19, 2018 at 08:50:41PM +0200, Denis Fondras wrote:
> On Wed, Sep 19, 2018 at 10:15:22AM +0200, Claudio Jeker wrote:
> > 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?
>
> I don't know if the case is relevant but
>
> prefix-set plop {
> 192.0.2.0/24 prefixlen 25
> 192.0.2.0/25
> 192.0.2.128/25
> }
>
> do not yield duplicate.
They are no real duplicates.
192.0.2.0/24 prefixlen 25
is different from
192.0.2.0/25
these are different nodes in the tree even though the cover the same
address range in the end.
Duplicates will only trigger on exactly duplicate lines (same prefix and
prefixlen bits).
Hope this makes sense.
--
:wq Claudio
> > --
> > :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
> >
>
