Re: bgpd: more RB tree less simpleq
ok benno@
Claudio Jeker(cje...@diehard.n-r-g.com) on 2018.09.19 10:15:22 +0200:
> 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.c9 Sep 2018 11:00:51 - 1.198
> +++ bgpd.c19 Sep 2018 06:34:11 -
> @@ -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(>psitems)) != NULL) {
> - SIMPLEQ_REMOVE_HEAD(>psitems, entry);
> + RB_FOREACH_SAFE(psi, prefixset_tree, >psitems, npsi) {
> + RB_REMOVE(prefixset_tree, >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.h14 Sep 2018 10:22:11 - 1.340
> +++ bgpd.h19 Sep 2018 06:32:47 -
> @@ -953,15 +953,15 @@ struct filter_set {
> };
>
> struct prefixset_item {
> - struct filter_prefix p;
> - SIMPLEQ_ENTRY(prefixset_item)entry;
> + struct filter_prefixp;
> + 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_treepsitems;
> SIMPLEQ_ENTRY(prefixset) entry;
> };
>
> @@ -1085,6 +1085,8 @@ voidfilterlist_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 - 1.73
> +++ config.c 19 Sep 2018 06:35:49 -
> @@ -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(>psitems)) {
> - psi = SIMPLEQ_FIRST(>psitems);
> - SIMPLEQ_REMOVE_HEAD(>psitems, entry);
> + RB_FOREACH_SAFE(psi, prefixset_tree, >psitems, npsi) {
> + RB_REMOVE(prefixset_tree, >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, >psitems, entry) {
> + RB_FOREACH(psi, prefixset_tree, >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
Re: bgpd: more RB tree less simpleq
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.c9 Sep 2018 11:00:51 - 1.198
> > > +++ bgpd.c19 Sep 2018 06:34:11 -
> > > @@ -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(>psitems)) != NULL) {
> > > - SIMPLEQ_REMOVE_HEAD(>psitems, entry);
> > > + RB_FOREACH_SAFE(psi, prefixset_tree, >psitems, npsi) {
> > > + RB_REMOVE(prefixset_tree, >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.h14 Sep 2018 10:22:11 - 1.340
> > > +++ bgpd.h19 Sep 2018 06:32:47 -
> > > @@ -953,15 +953,15 @@ struct filter_set {
> > > };
> > >
> > > struct prefixset_item {
> > > - struct filter_prefix p;
> > > - SIMPLEQ_ENTRY(prefixset_item)entry;
> > > + struct filter_prefixp;
> > > + 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_treepsitems;
> > > SIMPLEQ_ENTRY(prefixset) entry;
> > > };
> > >
> > > @@ -1085,6 +1085,8 @@ voidfilterlist_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 - 1.73
> > > +++ config.c 19 Sep 2018 06:35:49 -
> > > @@ -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(>psitems)) {
> > > - psi = SIMPLEQ_FIRST(>psitems);
> > > - SIMPLEQ_REMOVE_HEAD(>psitems, entry);
> > > + RB_FOREACH_SAFE(psi, prefixset_tree, >psitems, npsi) {
> > > + RB_REMOVE(prefixset_tree, >psitems, psi);
> > > free(psi);
> > > }
> > > SIMPLEQ_REMOVE_HEAD(psh, entry);
> >
Re: bgpd: more RB tree less simpleq
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 - 1.198
> > +++ bgpd.c 19 Sep 2018 06:34:11 -
> > @@ -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(>psitems)) != NULL) {
> > - SIMPLEQ_REMOVE_HEAD(>psitems, entry);
> > + RB_FOREACH_SAFE(psi, prefixset_tree, >psitems, npsi) {
> > + RB_REMOVE(prefixset_tree, >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 - 1.340
> > +++ bgpd.h 19 Sep 2018 06:32:47 -
> > @@ -953,15 +953,15 @@ struct filter_set {
> > };
> >
> > struct prefixset_item {
> > - struct filter_prefix p;
> > - SIMPLEQ_ENTRY(prefixset_item)entry;
> > + struct filter_prefixp;
> > + 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_treepsitems;
> > SIMPLEQ_ENTRY(prefixset) entry;
> > };
> >
> > @@ -1085,6 +1085,8 @@ void filterlist_free(struct filter_head
> > inthost(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 *);
> > +intprefixset_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.c9 Sep 2018 11:00:51 - 1.73
> > +++ config.c19 Sep 2018 06:35:49 -
> > @@ -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(>psitems)) {
> > - psi = SIMPLEQ_FIRST(>psitems);
> > - SIMPLEQ_REMOVE_HEAD(>psitems, entry);
> > + RB_FOREACH_SAFE(psi, prefixset_tree, >psitems, npsi) {
> > + RB_REMOVE(prefixset_tree, >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);
> > -
Re: bgpd: more RB tree less simpleq
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.
> --
> :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.c9 Sep 2018 11:00:51 - 1.198
> +++ bgpd.c19 Sep 2018 06:34:11 -
> @@ -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(>psitems)) != NULL) {
> - SIMPLEQ_REMOVE_HEAD(>psitems, entry);
> + RB_FOREACH_SAFE(psi, prefixset_tree, >psitems, npsi) {
> + RB_REMOVE(prefixset_tree, >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.h14 Sep 2018 10:22:11 - 1.340
> +++ bgpd.h19 Sep 2018 06:32:47 -
> @@ -953,15 +953,15 @@ struct filter_set {
> };
>
> struct prefixset_item {
> - struct filter_prefix p;
> - SIMPLEQ_ENTRY(prefixset_item)entry;
> + struct filter_prefixp;
> + 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_treepsitems;
> SIMPLEQ_ENTRY(prefixset) entry;
> };
>
> @@ -1085,6 +1085,8 @@ voidfilterlist_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 - 1.73
> +++ config.c 19 Sep 2018 06:35:49 -
> @@ -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(>psitems)) {
> - psi = SIMPLEQ_FIRST(>psitems);
> - SIMPLEQ_REMOVE_HEAD(>psitems, entry);
> + RB_FOREACH_SAFE(psi, prefixset_tree, >psitems, npsi) {
> + RB_REMOVE(prefixset_tree, >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, >psitems, entry) {
> + RB_FOREACH(psi, prefixset_tree, >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
