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.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
>
