On Wed, Sep 19, 2018 at 10:41:15PM +0200, Claudio Jeker wrote:
> 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.
Then OK denis@
> --
> :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
> > >
> >
>
