This diff extends the existing trie code for prefix-set to also work with
roa-set. Unlike prefix-set there is no need for a prefixlen mask during
lookup, instead the source-as needs to be checked and also if the
prefixlen of the prefix is allowed.
The lookup can return 3 states:
ROA_UNKNONW: prefix is not covered by any entry
ROA_VALID: prefix is covered and the source-as matches as does the prefixlen
ROA_INVALID: there was a covering ROA entry that did not match source-as
or prefixlen
The source-as check is done with an as_set and should therefor scale well.
In general these lookups need to be quick since all prefixes will go
through roa lookups.
The frontend code (parse.y and imsg passing) is missing, since this is
already fairly large and it is tested by the unit tests I decided to send
this out as an idividual step.
Cheers
--
:wq Claudio
Index: usr.sbin/bgpd/bgpd.h
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/bgpd.h,v
retrieving revision 1.340
diff -u -p -r1.340 bgpd.h
--- usr.sbin/bgpd/bgpd.h 14 Sep 2018 10:22:11 -0000 1.340
+++ usr.sbin/bgpd/bgpd.h 14 Sep 2018 14:08:49 -0000
@@ -952,6 +952,11 @@ struct filter_set {
enum action_types type;
};
+struct roa_set {
+ u_int32_t as; /* must be first */
+ u_int32_t maxlen; /* change type for better struct layout */
+};
+
struct prefixset_item {
struct filter_prefix p;
SIMPLEQ_ENTRY(prefixset_item) entry;
Index: usr.sbin/bgpd/rde.h
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde.h,v
retrieving revision 1.190
diff -u -p -r1.190 rde.h
--- usr.sbin/bgpd/rde.h 9 Sep 2018 12:33:51 -0000 1.190
+++ usr.sbin/bgpd/rde.h 14 Sep 2018 14:08:22 -0000
@@ -36,6 +36,12 @@ enum peer_state {
PEER_ERR /* error occurred going to PEER_DOWN state */
};
+enum roa_state {
+ ROA_UNKNOWN,
+ ROA_INVALID,
+ ROA_VALID
+};
+
/*
* How do we identify peers between the session handler and the rde?
* Currently I assume that we can do that with the neighbor_ip...
@@ -332,7 +338,8 @@ struct rde_prefixset {
char name[SET_NAME_LEN];
struct trie_head th;
SIMPLEQ_ENTRY(rde_prefixset) entry;
- int dirty;
+ int dirty;
+ int roa;
};
SIMPLEQ_HEAD(rde_prefixset_head, rde_prefixset);
@@ -578,8 +585,12 @@ int up_dump_mp_reach(u_char *, u_int16
/* 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 as_set *);
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,
+ u_int32_t);
void trie_dump(struct trie_head *);
int trie_equal(struct trie_head *, struct trie_head *);
Index: usr.sbin/bgpd/rde_trie.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde_trie.c,v
retrieving revision 1.5
diff -u -p -r1.5 rde_trie.c
--- usr.sbin/bgpd/rde_trie.c 10 Sep 2018 13:15:50 -0000 1.5
+++ usr.sbin/bgpd/rde_trie.c 14 Sep 2018 14:08:22 -0000
@@ -57,22 +57,20 @@
*/
struct tentry_v4 {
struct tentry_v4 *trie[2];
+ struct as_set *aset; /* for roa source-as set */
struct in_addr addr;
struct in_addr plenmask;
u_int8_t plen;
u_int8_t node;
-
- /* roa source-as list pointer */
};
struct tentry_v6 {
struct tentry_v6 *trie[2];
+ struct as_set *aset; /* for roa source-as set */
struct in6_addr addr;
struct in6_addr plenmask;
u_int8_t plen;
u_int8_t node;
-
- /* roa source-as list pointer */
};
/*
@@ -143,37 +141,14 @@ inet6setbit(struct in6_addr *addr, u_int
addr->s6_addr[bit / 8] |= (0x80 >> (bit % 8));
}
-static int
-trie_add_v4(struct trie_head *th, struct in_addr *prefix, u_int8_t plen,
- u_int8_t min, u_int8_t max)
+static struct tentry_v4 *
+trie_add_v4(struct trie_head *th, struct in_addr *prefix, u_int8_t plen)
{
struct tentry_v4 *n, *new, *b, **prev;
- struct in_addr p, plenmask;
- u_int8_t i;
-
- /*
- * check for default route, this is special cased since prefixlen 0
- * can't be checked in the prefixlen mask plenmask. Also there is only
- * one default route so using a flag for this works.
- */
- if (min == 0) {
- th->match_default_v4 = 1;
- if (max == 0) /* just the default route */
- return 0;
- min = 1;
- }
+ struct in_addr p;
inet4applymask(&p, prefix, plen);
- /*
- * The prefixlen mask goes from 1 to 32 but the bitmask
- * starts at 0 and so all bits are set with an offset of 1.
- * The default /0 route is handled specially above.
- */
- memset(&plenmask, 0, sizeof(plenmask));
- for (i = min; i <= max; i++)
- inet4setbit(&plenmask, i - 1);
-
/* walk tree finding spot to insert */
prev = &th->root_v4;
n = *prev;
@@ -189,7 +164,7 @@ trie_add_v4(struct trie_head *th, struct
* np and n, then insert n and new node there
*/
if ((b = calloc(1, sizeof(*b))) == NULL)
- return -1;
+ return NULL;
b->plen = inet4findmsb(&n->addr, &mp);
inet4applymask(&b->addr, &n->addr, b->plen);
@@ -213,8 +188,7 @@ trie_add_v4(struct trie_head *th, struct
if (n->plen == plen) {
/* matching node, adjust */
n->node = 1;
- n->plenmask.s_addr |= plenmask.s_addr;
- return 0;
+ return n;
}
/* no need to check for n->plen == 32 because of above if */
@@ -227,10 +201,9 @@ trie_add_v4(struct trie_head *th, struct
/* create new node */
if ((new = calloc(1, sizeof(*new))) == NULL)
- return -1;
+ return NULL;
new->addr = p;
new->plen = plen;
- new->plenmask = plenmask;
new->node = 1;
/* link node */
@@ -241,40 +214,17 @@ trie_add_v4(struct trie_head *th, struct
else
new->trie[0] = n;
}
- return 0;
+ return new;
}
-static int
-trie_add_v6(struct trie_head *th, struct in6_addr *prefix, u_int8_t plen,
- u_int8_t min, u_int8_t max)
+static struct tentry_v6 *
+trie_add_v6(struct trie_head *th, struct in6_addr *prefix, u_int8_t plen)
{
struct tentry_v6 *n, *new, *b, **prev;
- struct in6_addr p, plenmask;
- u_int8_t i;
-
- /*
- * check for default route, this is special cased since prefixlen 0
- * can't be checked in the prefixlen mask plenmask. Also there is only
- * one default route so using a flag for this works.
- */
- if (min == 0) {
- th->match_default_v6 = 1;
- if (max == 0) /* just the default route */
- return 0;
- min = 1;
- }
+ struct in6_addr p;
inet6applymask(&p, prefix, plen);
- /*
- * The prefixlen mask goes from 1 to 128 but the bitmask
- * starts at 0 and so all bits are set with an offset of 1.
- * The default /0 route is handled specially above.
- */
- memset(&plenmask, 0, sizeof(plenmask));
- for (i = min; i <= max; i++)
- inet6setbit(&plenmask, i - 1);
-
/* walk tree finding spot to insert */
prev = &th->root_v6;
n = *prev;
@@ -290,7 +240,7 @@ trie_add_v6(struct trie_head *th, struct
* np and n, then insert n and new node there
*/
if ((b = calloc(1, sizeof(*b))) == NULL)
- return -1;
+ return NULL;
b->plen = inet6findmsb(&n->addr, &mp);
inet6applymask(&b->addr, &n->addr, b->plen);
@@ -314,9 +264,7 @@ trie_add_v6(struct trie_head *th, struct
if (n->plen == plen) {
/* matching node, adjust */
n->node = 1;
- for (i = 0; i < sizeof(plenmask); i++)
- n->plenmask.s6_addr[i] |= plenmask.s6_addr[i];
- return 0;
+ return n;
}
/* no need to check for n->plen == 128 because of above if */
@@ -329,10 +277,9 @@ trie_add_v6(struct trie_head *th, struct
/* create new node */
if ((new = calloc(1, sizeof(*new))) == NULL)
- return -1;
+ return NULL;
new->addr = p;
new->plen = plen;
- new->plenmask = plenmask;
new->node = 1;
/* link node */
@@ -343,30 +290,125 @@ trie_add_v6(struct trie_head *th, struct
else
new->trie[0] = n;
}
- return 0;
+ return new;
}
+/*
+ * Insert prefix/plen into the trie with a prefixlen mask covering min - max.
+ * If plen == min == max then only the prefix/plen will match and no longer
+ * match is possible. Else all prefixes under prefix/plen with a prefixlen
+ * between min and max will match.
+ */
int
trie_add(struct trie_head *th, struct bgpd_addr *prefix, u_int8_t plen,
u_int8_t min, u_int8_t max)
{
+ struct tentry_v4 *n4;
+ struct tentry_v6 *n6;
+ u_int8_t i;
+
/* precondition plen <= min <= max */
if (plen > min || min > max)
return -1;
+ if (prefix->aid != AID_INET && prefix->aid != AID_INET6)
+ return -1;
+
+ /*
+ * Check for default route, this is special cased since prefixlen 0
+ * can't be checked in the prefixlen mask plenmask. Also there is
+ * only one default route so using a flag for this works.
+ */
+ if (min == 0) {
+ if (prefix->aid == AID_INET)
+ th->match_default_v4 = 1;
+ else
+ th->match_default_v6 = 1;
+
+ if (max == 0) /* just the default route */
+ return 0;
+ min = 1;
+ }
switch (prefix->aid) {
case AID_INET:
if (max > 32)
return -1;
- return trie_add_v4(th, &prefix->v4, plen, min, max);
+
+ n4 = trie_add_v4(th, &prefix->v4, plen);
+ if (n4 == NULL)
+ return -1;
+ /*
+ * The prefixlen min - max goes from 1 to 32 but the bitmask
+ * starts at 0 and so all bits are set with an offset of -1.
+ * The default /0 route is handled specially above.
+ */
+ for (i = min; i <= max; i++)
+ inet4setbit(&n4->plenmask, i - 1);
+ break;
case AID_INET6:
if (max > 128)
return -1;
- return trie_add_v6(th, &prefix->v6, plen, min, max);
+
+ n6 = trie_add_v6(th, &prefix->v6, plen);
+ if (n6 == NULL)
+ return -1;
+
+ /* See above for the - 1 reason. */
+ for (i = min; i <= max; i++)
+ inet6setbit(&n6->plenmask, i - 1);
+ break;
+ }
+ return 0;
+}
+
+/*
+ * Insert a ROA entry for prefix/plen. The prefix will insert an as_set with
+ * source_as and the maxlen as data. This makes it possible to validate if a
+ * prefix is matching this ROA record. It is possible to insert prefixes with
+ * source_as = 0. These entries will never return ROA_VALID on check and can
+ * be used to cover a large prefix as ROA_INVALID unless a more specific route
+ * is a match.
+ */
+int
+trie_roa_add(struct trie_head *th, struct bgpd_addr *prefix, u_int8_t plen,
+ struct as_set *aset)
+{
+ struct tentry_v4 *n4;
+ struct tentry_v6 *n6;
+ struct as_set **ap;
+
+ /* ignore possible default route since it does not make sense */
+
+ switch (prefix->aid) {
+ case AID_INET:
+ if (plen > 32)
+ return -1;
+
+ n4 = trie_add_v4(th, &prefix->v4, plen);
+ if (n4 == NULL)
+ return -1;
+ ap = &n4->aset;
+ break;
+ case AID_INET6:
+ if (plen > 128)
+ return -1;
+
+ n6 = trie_add_v6(th, &prefix->v6, plen);
+ if (n6 == NULL)
+ return -1;
+ ap = &n6->aset;
+ break;
default:
/* anything else fails */
return -1;
}
+
+ /* aset already set, error out */
+ if (*ap != NULL)
+ return -1;
+ *ap = aset;
+
+ return 0;
}
static void
@@ -376,6 +418,7 @@ trie_free_v4(struct tentry_v4 *n)
return;
trie_free_v4(n->trie[0]);
trie_free_v4(n->trie[1]);
+ as_set_free(n->aset);
free(n);
}
@@ -386,6 +429,7 @@ trie_free_v6(struct tentry_v6 *n)
return;
trie_free_v6(n->trie[0]);
trie_free_v6(n->trie[1]);
+ as_set_free(n->aset);
free(n);
}
@@ -490,6 +534,123 @@ trie_match(struct trie_head *th, struct
default:
/* anything else is no match */
return 0;
+ }
+}
+
+static int
+trie_roa_check_v4(struct trie_head *th, struct in_addr *prefix, u_int8_t plen,
+ u_int32_t as)
+{
+ struct tentry_v4 *n;
+ struct roa_set *rs;
+ int validity = ROA_UNKNOWN;
+
+ /* ignore possible default route since it does not make sense */
+
+ n = th->root_v4;
+ while (n) {
+ struct in_addr mp;
+
+ if (n->plen > plen)
+ break; /* too specific, no match possible */
+
+ inet4applymask(&mp, prefix, n->plen);
+ if (n->addr.s_addr != mp.s_addr)
+ break; /* off path, no other match possible */
+
+ if (n->node) {
+ /*
+ * The prefix is covered by this roa node
+ * therefor invalid unless roa_set matches.
+ */
+ validity = ROA_INVALID;
+
+ /* Treat AS 0 as NONE which can never be matched */
+ if (as != 0) {
+ rs = as_set_match(n->aset, as);
+ if (rs && plen <= rs->maxlen)
+ return ROA_VALID;
+ }
+ }
+
+ if (n->plen == 32)
+ break; /* can't go deeper */
+ if (inet4isset(prefix, n->plen))
+ n = n->trie[1];
+ else
+ n = n->trie[0];
+ }
+
+ return validity;
+}
+
+static int
+trie_roa_check_v6(struct trie_head *th, struct in6_addr *prefix, u_int8_t plen,
+ u_int32_t as)
+{
+ struct tentry_v6 *n;
+ struct roa_set *rs;
+ int validity = ROA_UNKNOWN;
+
+ /* ignore possible default route since it does not make sense */
+
+ n = th->root_v6;
+ while (n) {
+ struct in6_addr mp;
+
+ if (n->plen > plen)
+ break; /* too specific, no match possible */
+
+ inet6applymask(&mp, prefix, n->plen);
+ if (memcmp(&n->addr, &mp, sizeof(mp)) != 0)
+ break; /* off path, no other match possible */
+
+ if (n->node) {
+ /*
+ * This prefix is covered by this roa node.
+ * Therefor invalid unless proven otherwise.
+ */
+ validity = ROA_INVALID;
+
+ /* Treat AS 0 as NONE which can never be matched */
+ if (as != 0) {
+ if ((rs = as_set_match(n->aset, as)) != NULL)
+ if (plen == n->plen || plen <= rs->maxlen)
+ return ROA_VALID;
+ }
+ }
+
+ if (n->plen == 128)
+ break; /* can't go deeper */
+ if (inet6isset(prefix, n->plen))
+ n = n->trie[1];
+ else
+ n = n->trie[0];
+ }
+
+ return validity;
+}
+
+/*
+ * Do a ROA (Route Origin Validation) check. Look for elements in the trie
+ * which cover prefix "prefix/plen" and match the source-as as.
+ * AS 0 is treated here like AS NONE and should be used when the source-as
+ * is unknown (e.g. AS_SET). In other words the check will then only return
+ * ROA_UNKNOWN or ROA_INVALID depending if the prefix is covered by the ROA.
+ */
+int
+trie_roa_check(struct trie_head *th, struct bgpd_addr *prefix, u_int8_t plen,
+ u_int32_t as)
+{
+ /* valid, invalid, unknow */
+ switch (prefix->aid) {
+ case AID_INET:
+ return trie_roa_check_v4(th, &prefix->v4, plen, as);
+ case AID_INET6:
+ return trie_roa_check_v6(th, &prefix->v6, plen, as);
+ default:
+ /* anything else is unkown */
+ return ROA_UNKNOWN;
}
}
Index: regress/usr.sbin/bgpd/unittests/Makefile
===================================================================
RCS file: /cvs/src/regress/usr.sbin/bgpd/unittests/Makefile,v
retrieving revision 1.3
diff -u -p -r1.3 Makefile
--- regress/usr.sbin/bgpd/unittests/Makefile 10 Sep 2018 20:51:59 -0000
1.3
+++ regress/usr.sbin/bgpd/unittests/Makefile 14 Sep 2018 14:10:05 -0000
@@ -18,13 +18,15 @@ run-regress-rde_sets_test: rde_sets_test
./rde_sets_test
SRCS_rde_trie_test= rde_trie_test.c rde_trie.c util.c rde_sets.c
-TRIE_TESTS=1 2 3 4
+TRIE_TESTS=1 2 3 4 5
+TRIE4_FLAGS=-o
+TRIE5_FLAGS=-r
.for n in ${TRIE_TESTS}
TRIE_TARGETS+=run-regress-rde_trie_test-${n}
run-regress-rde_trie_test-${n}: rde_trie_test
- ./rde_trie_test ${.CURDIR}/rde_trie_test.${n}.in \
+ ./rde_trie_test ${TRIE${n}_FLAGS} ${.CURDIR}/rde_trie_test.${n}.in \
${.CURDIR}/rde_trie_test.${n}.check | \
diff -u ${.CURDIR}/rde_trie_test.${n}.out /dev/stdin
.endfor
Index: regress/usr.sbin/bgpd/unittests/rde_trie_test.1.out
===================================================================
RCS file: /cvs/src/regress/usr.sbin/bgpd/unittests/rde_trie_test.1.out,v
retrieving revision 1.2
diff -u -p -r1.2 rde_trie_test.1.out
--- regress/usr.sbin/bgpd/unittests/rde_trie_test.1.out 10 Sep 2018 20:51:59
-0000 1.2
+++ regress/usr.sbin/bgpd/unittests/rde_trie_test.1.out 14 Sep 2018 14:10:05
-0000
@@ -1,11 +1,11 @@
-62.48.0.0/19 MATCH 0
-62.48.0.0/18 miss 0
-62.48.0.0/20 miss 0
-62.48.3.0/24 MATCH 0
-62.48.2.0/24 miss 0
-62.48.2.0/25 MATCH 0
-62.48.2.0/26 MATCH 0
-10.0.0.0/8 MATCH 0
-10.0.0.0/24 MATCH 0
-192.168.3.0/24 miss 0
-192.168.3.66/30 MATCH 0
+62.48.0.0/19 MATCH
+62.48.0.0/18 miss
+62.48.0.0/20 miss
+62.48.3.0/24 MATCH
+62.48.2.0/24 miss
+62.48.2.0/25 MATCH
+62.48.2.0/26 MATCH
+10.0.0.0/8 MATCH
+10.0.0.0/24 MATCH
+192.168.3.0/24 miss
+192.168.3.66/30 MATCH
Index: regress/usr.sbin/bgpd/unittests/rde_trie_test.2.out
===================================================================
RCS file: /cvs/src/regress/usr.sbin/bgpd/unittests/rde_trie_test.2.out,v
retrieving revision 1.2
diff -u -p -r1.2 rde_trie_test.2.out
--- regress/usr.sbin/bgpd/unittests/rde_trie_test.2.out 10 Sep 2018 20:51:59
-0000 1.2
+++ regress/usr.sbin/bgpd/unittests/rde_trie_test.2.out 14 Sep 2018 14:10:05
-0000
@@ -1,14 +1,14 @@
-46.21.0.0/20 MATCH 0
-87.253.240.0/20 MATCH 0
-185.108.8.0/22 MATCH 0
-193.41.124.0/23 MATCH 0
-195.110.26.0/23 MATCH 0
-213.135.192.0/21 MATCH 0
-2a01:7f8::/32 MATCH 0
-199.185.136.0/23 miss 0
-199.185.178.0/24 miss 0
-199.185.230.0/23 miss 0
-204.174.115.0/24 miss 0
-204.209.252.0/24 miss 0
-204.209.253.0/24 miss 0
-2620:3d:c000::/48 miss 0
+46.21.0.0/20 MATCH
+87.253.240.0/20 MATCH
+185.108.8.0/22 MATCH
+193.41.124.0/23 MATCH
+195.110.26.0/23 MATCH
+213.135.192.0/21 MATCH
+2a01:7f8::/32 MATCH
+199.185.136.0/23 miss
+199.185.178.0/24 miss
+199.185.230.0/23 miss
+204.174.115.0/24 miss
+204.209.252.0/24 miss
+204.209.253.0/24 miss
+2620:3d:c000::/48 miss
Index: regress/usr.sbin/bgpd/unittests/rde_trie_test.3.out
===================================================================
RCS file: /cvs/src/regress/usr.sbin/bgpd/unittests/rde_trie_test.3.out,v
retrieving revision 1.2
diff -u -p -r1.2 rde_trie_test.3.out
--- regress/usr.sbin/bgpd/unittests/rde_trie_test.3.out 10 Sep 2018 20:51:59
-0000 1.2
+++ regress/usr.sbin/bgpd/unittests/rde_trie_test.3.out 14 Sep 2018 14:10:05
-0000
@@ -1,143 +1,143 @@
-82.130.64.0/18 MATCH 0
-86.119.0.0/16 MATCH 0
-89.206.64.0/18 MATCH 0
-128.178.0.0/15 MATCH 0
-129.129.0.0/16 MATCH 0
-129.132.0.0/16 MATCH 0
-129.194.0.0/15 MATCH 0
-130.59.0.0/16 MATCH 0
-130.60.0.0/16 MATCH 0
-130.82.0.0/16 MATCH 0
-130.92.0.0/16 MATCH 0
-130.125.0.0/16 MATCH 0
-130.223.0.0/16 MATCH 0
-131.152.0.0/16 MATCH 0
-134.21.0.0/16 MATCH 0
-138.131.0.0/16 MATCH 0
-141.249.0.0/16 MATCH 0
-144.200.0.0/16 MATCH 0
-146.136.0.0/16 MATCH 0
-147.86.0.0/16 MATCH 0
-147.87.0.0/16 MATCH 0
-147.88.0.0/16 MATCH 0
-148.187.0.0/16 MATCH 0
-148.196.0.0/16 MATCH 0
-152.88.0.0/16 MATCH 0
-152.96.0.0/16 MATCH 0
-153.109.0.0/16 MATCH 0
-155.105.0.0/16 MATCH 0
-155.228.0.0/16 MATCH 0
-156.25.0.0/16 MATCH 0
-156.135.0.0/21 MATCH 0
-156.135.12.0/22 MATCH 0
-156.135.16.0/21 MATCH 0
-156.135.28.0/22 MATCH 0
-156.135.32.0/19 MATCH 0
-156.135.64.0/18 MATCH 0
-156.135.128.0/17 MATCH 0
-157.26.0.0/16 MATCH 0
-160.85.0.0/16 MATCH 0
-160.98.0.0/16 MATCH 0
-161.62.0.0/16 MATCH 0
-185.51.68.0/22 MATCH 0
-185.133.44.0/22 MATCH 0
-185.144.36.0/22 MATCH 0
-185.194.180.0/22 MATCH 0
-185.225.92.0/22 MATCH 0
-192.12.247.0/24 MATCH 0
-192.26.28.0/22 MATCH 0
-192.26.32.0/21 MATCH 0
-192.26.40.0/22 MATCH 0
-192.26.44.0/24 MATCH 0
-192.26.46.0/23 MATCH 0
-192.33.87.0/24 MATCH 0
-192.33.88.0/21 MATCH 0
-192.33.96.0/21 MATCH 0
-192.33.104.0/22 MATCH 0
-192.33.108.0/23 MATCH 0
-192.33.110.0/24 MATCH 0
-192.33.118.0/23 MATCH 0
-192.33.120.0/21 MATCH 0
-192.33.192.0/19 MATCH 0
-192.33.224.0/21 MATCH 0
-192.41.132.0/22 MATCH 0
-192.41.136.0/24 MATCH 0
-192.41.149.0/24 MATCH 0
-192.41.150.0/23 MATCH 0
-192.41.152.0/21 MATCH 0
-192.41.160.0/24 MATCH 0
-192.42.42.0/23 MATCH 0
-192.42.44.0/22 MATCH 0
-192.42.180.0/22 MATCH 0
-192.42.184.0/21 MATCH 0
-192.42.192.0/21 MATCH 0
-192.42.200.0/23 MATCH 0
-192.43.192.0/22 MATCH 0
-192.43.196.0/24 MATCH 0
-192.47.244.0/22 MATCH 0
-192.47.248.0/23 MATCH 0
-192.65.92.0/23 MATCH 0
-192.101.176.0/24 MATCH 0
-192.135.150.0/23 MATCH 0
-192.135.151.0/24 MATCH 0
-192.135.152.0/21 MATCH 0
-192.152.98.0/24 MATCH 0
-193.5.22.0/24 MATCH 0
-193.5.26.0/23 MATCH 0
-193.5.54.0/23 MATCH 0
-193.5.58.0/24 MATCH 0
-193.5.60.0/24 MATCH 0
-193.5.80.0/21 MATCH 0
-193.5.152.0/22 MATCH 0
-193.5.168.0/22 MATCH 0
-193.5.180.0/24 MATCH 0
-193.5.182.0/24 MATCH 0
-193.5.186.0/24 MATCH 0
-193.5.188.0/24 MATCH 0
-193.8.136.0/23 MATCH 0
-193.36.32.0/24 MATCH 0
-193.73.125.0/24 MATCH 0
-193.134.200.0/21 MATCH 0
-193.134.216.0/21 MATCH 0
-193.135.168.0/22 MATCH 0
-193.135.172.0/24 MATCH 0
-193.135.240.0/21 MATCH 0
-193.138.69.0/24 MATCH 0
-193.222.112.0/20 MATCH 0
-193.222.241.0/24 MATCH 0
-193.222.242.0/23 MATCH 0
-193.222.244.0/22 MATCH 0
-193.222.248.0/23 MATCH 0
-193.222.250.0/24 MATCH 0
-193.246.121.0/24 MATCH 0
-193.246.124.0/23 MATCH 0
-193.246.176.0/20 MATCH 0
-193.247.190.0/23 MATCH 0
-193.247.203.0/24 MATCH 0
-193.247.240.0/22 MATCH 0
-193.247.248.0/23 MATCH 0
-193.247.254.0/24 MATCH 0
-194.153.96.0/24 MATCH 0
-195.176.0.0/17 MATCH 0
-195.176.160.0/19 MATCH 0
-195.176.224.0/19 MATCH 0
-198.21.18.0/24 miss 0
-2001:620::/29 MATCH 0
-2001:620::/32 MATCH 0
-2001:678:678::/48 MATCH 0
-2001:67c:10ec::/48 MATCH 0
-2001:67c:13c0::/48 MATCH 0
-2001:67c:16dc::/48 MATCH 0
-2a02:7dc0::/32 MATCH 0
-2a07:290a::/32 MATCH 0
-2a07:3e00::/29 MATCH 0
-2a07:6b40::/29 MATCH 0
-2a0a:4ec0::/29 MATCH 0
-2a0b:2040::/29 MATCH 0
-199.185.136.0/23 miss 0
-199.185.178.0/24 miss 0
-199.185.230.0/23 miss 0
-204.174.115.0/24 miss 0
-204.209.252.0/24 miss 0
-204.209.253.0/24 miss 0
-2620:3d:c000::/48 miss 0
+82.130.64.0/18 MATCH
+86.119.0.0/16 MATCH
+89.206.64.0/18 MATCH
+128.178.0.0/15 MATCH
+129.129.0.0/16 MATCH
+129.132.0.0/16 MATCH
+129.194.0.0/15 MATCH
+130.59.0.0/16 MATCH
+130.60.0.0/16 MATCH
+130.82.0.0/16 MATCH
+130.92.0.0/16 MATCH
+130.125.0.0/16 MATCH
+130.223.0.0/16 MATCH
+131.152.0.0/16 MATCH
+134.21.0.0/16 MATCH
+138.131.0.0/16 MATCH
+141.249.0.0/16 MATCH
+144.200.0.0/16 MATCH
+146.136.0.0/16 MATCH
+147.86.0.0/16 MATCH
+147.87.0.0/16 MATCH
+147.88.0.0/16 MATCH
+148.187.0.0/16 MATCH
+148.196.0.0/16 MATCH
+152.88.0.0/16 MATCH
+152.96.0.0/16 MATCH
+153.109.0.0/16 MATCH
+155.105.0.0/16 MATCH
+155.228.0.0/16 MATCH
+156.25.0.0/16 MATCH
+156.135.0.0/21 MATCH
+156.135.12.0/22 MATCH
+156.135.16.0/21 MATCH
+156.135.28.0/22 MATCH
+156.135.32.0/19 MATCH
+156.135.64.0/18 MATCH
+156.135.128.0/17 MATCH
+157.26.0.0/16 MATCH
+160.85.0.0/16 MATCH
+160.98.0.0/16 MATCH
+161.62.0.0/16 MATCH
+185.51.68.0/22 MATCH
+185.133.44.0/22 MATCH
+185.144.36.0/22 MATCH
+185.194.180.0/22 MATCH
+185.225.92.0/22 MATCH
+192.12.247.0/24 MATCH
+192.26.28.0/22 MATCH
+192.26.32.0/21 MATCH
+192.26.40.0/22 MATCH
+192.26.44.0/24 MATCH
+192.26.46.0/23 MATCH
+192.33.87.0/24 MATCH
+192.33.88.0/21 MATCH
+192.33.96.0/21 MATCH
+192.33.104.0/22 MATCH
+192.33.108.0/23 MATCH
+192.33.110.0/24 MATCH
+192.33.118.0/23 MATCH
+192.33.120.0/21 MATCH
+192.33.192.0/19 MATCH
+192.33.224.0/21 MATCH
+192.41.132.0/22 MATCH
+192.41.136.0/24 MATCH
+192.41.149.0/24 MATCH
+192.41.150.0/23 MATCH
+192.41.152.0/21 MATCH
+192.41.160.0/24 MATCH
+192.42.42.0/23 MATCH
+192.42.44.0/22 MATCH
+192.42.180.0/22 MATCH
+192.42.184.0/21 MATCH
+192.42.192.0/21 MATCH
+192.42.200.0/23 MATCH
+192.43.192.0/22 MATCH
+192.43.196.0/24 MATCH
+192.47.244.0/22 MATCH
+192.47.248.0/23 MATCH
+192.65.92.0/23 MATCH
+192.101.176.0/24 MATCH
+192.135.150.0/23 MATCH
+192.135.151.0/24 MATCH
+192.135.152.0/21 MATCH
+192.152.98.0/24 MATCH
+193.5.22.0/24 MATCH
+193.5.26.0/23 MATCH
+193.5.54.0/23 MATCH
+193.5.58.0/24 MATCH
+193.5.60.0/24 MATCH
+193.5.80.0/21 MATCH
+193.5.152.0/22 MATCH
+193.5.168.0/22 MATCH
+193.5.180.0/24 MATCH
+193.5.182.0/24 MATCH
+193.5.186.0/24 MATCH
+193.5.188.0/24 MATCH
+193.8.136.0/23 MATCH
+193.36.32.0/24 MATCH
+193.73.125.0/24 MATCH
+193.134.200.0/21 MATCH
+193.134.216.0/21 MATCH
+193.135.168.0/22 MATCH
+193.135.172.0/24 MATCH
+193.135.240.0/21 MATCH
+193.138.69.0/24 MATCH
+193.222.112.0/20 MATCH
+193.222.241.0/24 MATCH
+193.222.242.0/23 MATCH
+193.222.244.0/22 MATCH
+193.222.248.0/23 MATCH
+193.222.250.0/24 MATCH
+193.246.121.0/24 MATCH
+193.246.124.0/23 MATCH
+193.246.176.0/20 MATCH
+193.247.190.0/23 MATCH
+193.247.203.0/24 MATCH
+193.247.240.0/22 MATCH
+193.247.248.0/23 MATCH
+193.247.254.0/24 MATCH
+194.153.96.0/24 MATCH
+195.176.0.0/17 MATCH
+195.176.160.0/19 MATCH
+195.176.224.0/19 MATCH
+198.21.18.0/24 miss
+2001:620::/29 MATCH
+2001:620::/32 MATCH
+2001:678:678::/48 MATCH
+2001:67c:10ec::/48 MATCH
+2001:67c:13c0::/48 MATCH
+2001:67c:16dc::/48 MATCH
+2a02:7dc0::/32 MATCH
+2a07:290a::/32 MATCH
+2a07:3e00::/29 MATCH
+2a07:6b40::/29 MATCH
+2a0a:4ec0::/29 MATCH
+2a0b:2040::/29 MATCH
+199.185.136.0/23 miss
+199.185.178.0/24 miss
+199.185.230.0/23 miss
+204.174.115.0/24 miss
+204.209.252.0/24 miss
+204.209.253.0/24 miss
+2620:3d:c000::/48 miss
Index: regress/usr.sbin/bgpd/unittests/rde_trie_test.4.check
===================================================================
RCS file: /cvs/src/regress/usr.sbin/bgpd/unittests/rde_trie_test.4.check,v
retrieving revision 1.1
diff -u -p -r1.1 rde_trie_test.4.check
--- regress/usr.sbin/bgpd/unittests/rde_trie_test.4.check 11 Sep 2018
08:55:49 -0000 1.1
+++ regress/usr.sbin/bgpd/unittests/rde_trie_test.4.check 14 Sep 2018
14:10:05 -0000
@@ -1,148 +1,148 @@
-23.128.23.0/28 1
-23.128.23.16/28 1
-23.128.23.192/28 1
-82.130.64.0/18 1
-86.119.0.0/16 1
-89.206.64.0/18 1
-128.178.0.0/15 1
-129.129.0.0/16 1
-129.132.0.0/16 1
-129.194.0.0/15 1
-130.59.0.0/16 1
-130.60.0.0/16 1
-130.82.0.0/16 1
-130.92.0.0/16 1
-130.125.0.0/16 1
-130.223.0.0/16 1
-131.152.0.0/16 1
-134.21.0.0/16 1
-138.131.0.0/16 1
-141.249.0.0/16 1
-144.200.0.0/16 1
-146.136.0.0/16 1
-147.86.0.0/16 1
-147.87.0.0/16 1
-147.88.0.0/16 1
-148.187.0.0/16 1
-148.196.0.0/16 1
-152.88.0.0/16 1
-152.96.0.0/16 1
-153.109.0.0/16 1
-155.105.0.0/16 1
-155.228.0.0/16 1
-156.25.0.0/16 1
-156.135.0.0/21 1
-156.135.12.0/22 1
-156.135.16.0/21 1
-156.135.28.0/22 1
-156.135.32.0/19 1
-156.135.64.0/18 1
-156.135.128.0/17 1
-157.26.0.0/16 1
-160.85.0.0/16 1
-160.98.0.0/16 1
-161.62.0.0/16 1
-185.51.68.0/22 1
-185.133.44.0/22 1
-185.144.36.0/22 1
-185.194.180.0/22 1
-185.225.92.0/22 1
-192.12.247.0/24 1
-192.26.28.0/22 1
-192.26.32.0/21 1
-192.26.40.0/22 1
-192.26.44.0/24 1
-192.26.46.0/23 1
-192.33.87.0/24 1
-192.33.88.0/21 1
-192.33.96.0/21 1
-192.33.104.0/22 1
-192.33.108.0/23 1
-192.33.110.0/24 1
-192.33.118.0/23 1
-192.33.120.0/21 1
-192.33.192.0/19 1
-192.33.224.0/21 1
-192.41.132.0/22 1
-192.41.136.0/24 1
-192.41.149.0/24 1
-192.41.150.0/23 1
-192.41.152.0/21 1
-192.41.160.0/24 1
-192.42.42.0/23 1
-192.42.44.0/22 1
-192.42.180.0/22 1
-192.42.184.0/21 1
-192.42.192.0/21 1
-192.42.200.0/23 1
-192.43.192.0/22 1
-192.43.196.0/24 1
-192.47.244.0/22 1
-192.47.248.0/23 1
-192.65.92.0/23 1
-192.101.176.0/24 1
-192.135.150.0/23 1
-192.135.151.0/24 1
-192.135.152.0/21 1
-192.152.98.0/24 1
-193.5.22.0/24 1
-193.5.26.0/23 1
-193.5.54.0/23 1
-193.5.58.0/24 1
-193.5.60.0/24 1
-193.5.80.0/21 1
-193.5.152.0/22 1
-193.5.168.0/22 1
-193.5.180.0/24 1
-193.5.182.0/24 1
-193.5.186.0/24 1
-193.5.188.0/24 1
-193.8.136.0/23 1
-193.36.32.0/24 1
-193.73.125.0/24 1
-193.134.200.0/21 1
-193.134.216.0/21 1
-193.135.168.0/22 1
-193.135.172.0/24 1
-193.135.240.0/21 1
-193.138.69.0/24 1
-193.222.112.0/20 1
-193.222.241.0/24 1
-193.222.242.0/23 1
-193.222.244.0/22 1
-193.222.248.0/23 1
-193.222.250.0/24 1
-193.246.121.0/24 1
-193.246.124.0/23 1
-193.246.176.0/20 1
-193.247.190.0/23 1
-193.247.203.0/24 1
-193.247.240.0/22 1
-193.247.248.0/23 1
-193.247.254.0/24 1
-194.153.96.0/24 1
-195.176.0.0/17 1
-195.176.160.0/19 1
-195.176.224.0/19 1
-198.21.18.0/24 1
-2001:620::/29 1
-2001:620::/32 1
-2001:678:678::/48 1
-2001:67c:10ec::/48 1
-2001:67c:13c0::/48 1
-2001:67c:16dc::/48 1
-2a02:7dc0::/32 1
-2a07:290a::/32 1
-2a07:3e00::/29 1
-2a07:6b40::/29 1
-2a0a:4ec0::/29 1
-2a0b:2040::/29 1
-199.185.136.0/23 1
-199.185.178.0/24 1
-199.185.230.0/23 1
-204.174.115.0/24 1
-204.209.252.0/24 1
-204.209.253.0/24 1
-2620:3d:c000::/48 1
-2a0c:fffe::2/127 1 1
-2a0c:fffd::/127 1
\ No newline at end of file
+23.128.23.0/28
+23.128.23.16/28
+23.128.23.192/28
+82.130.64.0/18
+86.119.0.0/16
+89.206.64.0/18
+128.178.0.0/15
+129.129.0.0/16
+129.132.0.0/16
+129.194.0.0/15
+130.59.0.0/16
+130.60.0.0/16
+130.82.0.0/16
+130.92.0.0/16
+130.125.0.0/16
+130.223.0.0/16
+131.152.0.0/16
+134.21.0.0/16
+138.131.0.0/16
+141.249.0.0/16
+144.200.0.0/16
+146.136.0.0/16
+147.86.0.0/16
+147.87.0.0/16
+147.88.0.0/16
+148.187.0.0/16
+148.196.0.0/16
+152.88.0.0/16
+152.96.0.0/16
+153.109.0.0/16
+155.105.0.0/16
+155.228.0.0/16
+156.25.0.0/16
+156.135.0.0/21
+156.135.12.0/22
+156.135.16.0/21
+156.135.28.0/22
+156.135.32.0/19
+156.135.64.0/18
+156.135.128.0/17
+157.26.0.0/16
+160.85.0.0/16
+160.98.0.0/16
+161.62.0.0/16
+185.51.68.0/22
+185.133.44.0/22
+185.144.36.0/22
+185.194.180.0/22
+185.225.92.0/22
+192.12.247.0/24
+192.26.28.0/22
+192.26.32.0/21
+192.26.40.0/22
+192.26.44.0/24
+192.26.46.0/23
+192.33.87.0/24
+192.33.88.0/21
+192.33.96.0/21
+192.33.104.0/22
+192.33.108.0/23
+192.33.110.0/24
+192.33.118.0/23
+192.33.120.0/21
+192.33.192.0/19
+192.33.224.0/21
+192.41.132.0/22
+192.41.136.0/24
+192.41.149.0/24
+192.41.150.0/23
+192.41.152.0/21
+192.41.160.0/24
+192.42.42.0/23
+192.42.44.0/22
+192.42.180.0/22
+192.42.184.0/21
+192.42.192.0/21
+192.42.200.0/23
+192.43.192.0/22
+192.43.196.0/24
+192.47.244.0/22
+192.47.248.0/23
+192.65.92.0/23
+192.101.176.0/24
+192.135.150.0/23
+192.135.151.0/24
+192.135.152.0/21
+192.152.98.0/24
+193.5.22.0/24
+193.5.26.0/23
+193.5.54.0/23
+193.5.58.0/24
+193.5.60.0/24
+193.5.80.0/21
+193.5.152.0/22
+193.5.168.0/22
+193.5.180.0/24
+193.5.182.0/24
+193.5.186.0/24
+193.5.188.0/24
+193.8.136.0/23
+193.36.32.0/24
+193.73.125.0/24
+193.134.200.0/21
+193.134.216.0/21
+193.135.168.0/22
+193.135.172.0/24
+193.135.240.0/21
+193.138.69.0/24
+193.222.112.0/20
+193.222.241.0/24
+193.222.242.0/23
+193.222.244.0/22
+193.222.248.0/23
+193.222.250.0/24
+193.246.121.0/24
+193.246.124.0/23
+193.246.176.0/20
+193.247.190.0/23
+193.247.203.0/24
+193.247.240.0/22
+193.247.248.0/23
+193.247.254.0/24
+194.153.96.0/24
+195.176.0.0/17
+195.176.160.0/19
+195.176.224.0/19
+198.21.18.0/24
+2001:620::/29
+2001:620::/32
+2001:678:678::/48
+2001:67c:10ec::/48
+2001:67c:13c0::/48
+2001:67c:16dc::/48
+2a02:7dc0::/32
+2a07:290a::/32
+2a07:3e00::/29
+2a07:6b40::/29
+2a0a:4ec0::/29
+2a0b:2040::/29
+199.185.136.0/23
+199.185.178.0/24
+199.185.230.0/23
+204.174.115.0/24
+204.209.252.0/24
+204.209.253.0/24
+2620:3d:c000::/48
+2a0c:fffe::2/127
+2a0c:fffd::/127
Index: regress/usr.sbin/bgpd/unittests/rde_trie_test.4.out
===================================================================
RCS file: /cvs/src/regress/usr.sbin/bgpd/unittests/rde_trie_test.4.out,v
retrieving revision 1.1
diff -u -p -r1.1 rde_trie_test.4.out
--- regress/usr.sbin/bgpd/unittests/rde_trie_test.4.out 11 Sep 2018 08:55:49
-0000 1.1
+++ regress/usr.sbin/bgpd/unittests/rde_trie_test.4.out 14 Sep 2018 14:10:05
-0000
@@ -1,148 +1,148 @@
-23.128.23.0/28 MATCH 1
-23.128.23.16/28 MATCH 1
-23.128.23.192/28 miss 1
-82.130.64.0/18 MATCH 1
-86.119.0.0/16 MATCH 1
-89.206.64.0/18 MATCH 1
-128.178.0.0/15 MATCH 1
-129.129.0.0/16 MATCH 1
-129.132.0.0/16 MATCH 1
-129.194.0.0/15 MATCH 1
-130.59.0.0/16 MATCH 1
-130.60.0.0/16 MATCH 1
-130.82.0.0/16 MATCH 1
-130.92.0.0/16 MATCH 1
-130.125.0.0/16 MATCH 1
-130.223.0.0/16 MATCH 1
-131.152.0.0/16 MATCH 1
-134.21.0.0/16 MATCH 1
-138.131.0.0/16 MATCH 1
-141.249.0.0/16 MATCH 1
-144.200.0.0/16 MATCH 1
-146.136.0.0/16 MATCH 1
-147.86.0.0/16 MATCH 1
-147.87.0.0/16 MATCH 1
-147.88.0.0/16 MATCH 1
-148.187.0.0/16 MATCH 1
-148.196.0.0/16 MATCH 1
-152.88.0.0/16 MATCH 1
-152.96.0.0/16 MATCH 1
-153.109.0.0/16 MATCH 1
-155.105.0.0/16 MATCH 1
-155.228.0.0/16 MATCH 1
-156.25.0.0/16 MATCH 1
-156.135.0.0/21 MATCH 1
-156.135.12.0/22 MATCH 1
-156.135.16.0/21 MATCH 1
-156.135.28.0/22 MATCH 1
-156.135.32.0/19 MATCH 1
-156.135.64.0/18 MATCH 1
-156.135.128.0/17 MATCH 1
-157.26.0.0/16 MATCH 1
-160.85.0.0/16 MATCH 1
-160.98.0.0/16 MATCH 1
-161.62.0.0/16 MATCH 1
-185.51.68.0/22 MATCH 1
-185.133.44.0/22 MATCH 1
-185.144.36.0/22 MATCH 1
-185.194.180.0/22 MATCH 1
-185.225.92.0/22 MATCH 1
-192.12.247.0/24 MATCH 1
-192.26.28.0/22 MATCH 1
-192.26.32.0/21 MATCH 1
-192.26.40.0/22 MATCH 1
-192.26.44.0/24 MATCH 1
-192.26.46.0/23 MATCH 1
-192.33.87.0/24 MATCH 1
-192.33.88.0/21 MATCH 1
-192.33.96.0/21 MATCH 1
-192.33.104.0/22 MATCH 1
-192.33.108.0/23 MATCH 1
-192.33.110.0/24 MATCH 1
-192.33.118.0/23 MATCH 1
-192.33.120.0/21 MATCH 1
-192.33.192.0/19 MATCH 1
-192.33.224.0/21 MATCH 1
-192.41.132.0/22 MATCH 1
-192.41.136.0/24 MATCH 1
-192.41.149.0/24 MATCH 1
-192.41.150.0/23 MATCH 1
-192.41.152.0/21 MATCH 1
-192.41.160.0/24 MATCH 1
-192.42.42.0/23 MATCH 1
-192.42.44.0/22 MATCH 1
-192.42.180.0/22 MATCH 1
-192.42.184.0/21 MATCH 1
-192.42.192.0/21 MATCH 1
-192.42.200.0/23 MATCH 1
-192.43.192.0/22 MATCH 1
-192.43.196.0/24 MATCH 1
-192.47.244.0/22 MATCH 1
-192.47.248.0/23 MATCH 1
-192.65.92.0/23 MATCH 1
-192.101.176.0/24 MATCH 1
-192.135.150.0/23 MATCH 1
-192.135.151.0/24 MATCH 1
-192.135.152.0/21 MATCH 1
-192.152.98.0/24 MATCH 1
-193.5.22.0/24 MATCH 1
-193.5.26.0/23 MATCH 1
-193.5.54.0/23 MATCH 1
-193.5.58.0/24 MATCH 1
-193.5.60.0/24 MATCH 1
-193.5.80.0/21 MATCH 1
-193.5.152.0/22 MATCH 1
-193.5.168.0/22 MATCH 1
-193.5.180.0/24 MATCH 1
-193.5.182.0/24 MATCH 1
-193.5.186.0/24 MATCH 1
-193.5.188.0/24 MATCH 1
-193.8.136.0/23 MATCH 1
-193.36.32.0/24 MATCH 1
-193.73.125.0/24 MATCH 1
-193.134.200.0/21 MATCH 1
-193.134.216.0/21 MATCH 1
-193.135.168.0/22 MATCH 1
-193.135.172.0/24 MATCH 1
-193.135.240.0/21 MATCH 1
-193.138.69.0/24 MATCH 1
-193.222.112.0/20 MATCH 1
-193.222.241.0/24 MATCH 1
-193.222.242.0/23 MATCH 1
-193.222.244.0/22 MATCH 1
-193.222.248.0/23 MATCH 1
-193.222.250.0/24 MATCH 1
-193.246.121.0/24 MATCH 1
-193.246.124.0/23 MATCH 1
-193.246.176.0/20 MATCH 1
-193.247.190.0/23 MATCH 1
-193.247.203.0/24 MATCH 1
-193.247.240.0/22 MATCH 1
-193.247.248.0/23 MATCH 1
-193.247.254.0/24 MATCH 1
-194.153.96.0/24 MATCH 1
-195.176.0.0/17 MATCH 1
-195.176.160.0/19 MATCH 1
-195.176.224.0/19 MATCH 1
-198.21.18.0/24 miss 1
-2001:620::/29 MATCH 1
-2001:620::/32 MATCH 1
-2001:678:678::/48 MATCH 1
-2001:67c:10ec::/48 MATCH 1
-2001:67c:13c0::/48 MATCH 1
-2001:67c:16dc::/48 MATCH 1
-2a02:7dc0::/32 MATCH 1
-2a07:290a::/32 MATCH 1
-2a07:3e00::/29 MATCH 1
-2a07:6b40::/29 MATCH 1
-2a0a:4ec0::/29 MATCH 1
-2a0b:2040::/29 MATCH 1
-199.185.136.0/23 miss 1
-199.185.178.0/24 miss 1
-199.185.230.0/23 miss 1
-204.174.115.0/24 miss 1
-204.209.252.0/24 miss 1
-204.209.253.0/24 miss 1
-2620:3d:c000::/48 miss 1
-2a0c:fffe::2/127 MATCH 1
-2a0c:fffd::/127 miss 1
+23.128.23.0/28 MATCH
+23.128.23.16/28 MATCH
+23.128.23.192/28 miss
+82.130.64.0/18 MATCH
+86.119.0.0/16 MATCH
+89.206.64.0/18 MATCH
+128.178.0.0/15 MATCH
+129.129.0.0/16 MATCH
+129.132.0.0/16 MATCH
+129.194.0.0/15 MATCH
+130.59.0.0/16 MATCH
+130.60.0.0/16 MATCH
+130.82.0.0/16 MATCH
+130.92.0.0/16 MATCH
+130.125.0.0/16 MATCH
+130.223.0.0/16 MATCH
+131.152.0.0/16 MATCH
+134.21.0.0/16 MATCH
+138.131.0.0/16 MATCH
+141.249.0.0/16 MATCH
+144.200.0.0/16 MATCH
+146.136.0.0/16 MATCH
+147.86.0.0/16 MATCH
+147.87.0.0/16 MATCH
+147.88.0.0/16 MATCH
+148.187.0.0/16 MATCH
+148.196.0.0/16 MATCH
+152.88.0.0/16 MATCH
+152.96.0.0/16 MATCH
+153.109.0.0/16 MATCH
+155.105.0.0/16 MATCH
+155.228.0.0/16 MATCH
+156.25.0.0/16 MATCH
+156.135.0.0/21 MATCH
+156.135.12.0/22 MATCH
+156.135.16.0/21 MATCH
+156.135.28.0/22 MATCH
+156.135.32.0/19 MATCH
+156.135.64.0/18 MATCH
+156.135.128.0/17 MATCH
+157.26.0.0/16 MATCH
+160.85.0.0/16 MATCH
+160.98.0.0/16 MATCH
+161.62.0.0/16 MATCH
+185.51.68.0/22 MATCH
+185.133.44.0/22 MATCH
+185.144.36.0/22 MATCH
+185.194.180.0/22 MATCH
+185.225.92.0/22 MATCH
+192.12.247.0/24 MATCH
+192.26.28.0/22 MATCH
+192.26.32.0/21 MATCH
+192.26.40.0/22 MATCH
+192.26.44.0/24 MATCH
+192.26.46.0/23 MATCH
+192.33.87.0/24 MATCH
+192.33.88.0/21 MATCH
+192.33.96.0/21 MATCH
+192.33.104.0/22 MATCH
+192.33.108.0/23 MATCH
+192.33.110.0/24 MATCH
+192.33.118.0/23 MATCH
+192.33.120.0/21 MATCH
+192.33.192.0/19 MATCH
+192.33.224.0/21 MATCH
+192.41.132.0/22 MATCH
+192.41.136.0/24 MATCH
+192.41.149.0/24 MATCH
+192.41.150.0/23 MATCH
+192.41.152.0/21 MATCH
+192.41.160.0/24 MATCH
+192.42.42.0/23 MATCH
+192.42.44.0/22 MATCH
+192.42.180.0/22 MATCH
+192.42.184.0/21 MATCH
+192.42.192.0/21 MATCH
+192.42.200.0/23 MATCH
+192.43.192.0/22 MATCH
+192.43.196.0/24 MATCH
+192.47.244.0/22 MATCH
+192.47.248.0/23 MATCH
+192.65.92.0/23 MATCH
+192.101.176.0/24 MATCH
+192.135.150.0/23 MATCH
+192.135.151.0/24 MATCH
+192.135.152.0/21 MATCH
+192.152.98.0/24 MATCH
+193.5.22.0/24 MATCH
+193.5.26.0/23 MATCH
+193.5.54.0/23 MATCH
+193.5.58.0/24 MATCH
+193.5.60.0/24 MATCH
+193.5.80.0/21 MATCH
+193.5.152.0/22 MATCH
+193.5.168.0/22 MATCH
+193.5.180.0/24 MATCH
+193.5.182.0/24 MATCH
+193.5.186.0/24 MATCH
+193.5.188.0/24 MATCH
+193.8.136.0/23 MATCH
+193.36.32.0/24 MATCH
+193.73.125.0/24 MATCH
+193.134.200.0/21 MATCH
+193.134.216.0/21 MATCH
+193.135.168.0/22 MATCH
+193.135.172.0/24 MATCH
+193.135.240.0/21 MATCH
+193.138.69.0/24 MATCH
+193.222.112.0/20 MATCH
+193.222.241.0/24 MATCH
+193.222.242.0/23 MATCH
+193.222.244.0/22 MATCH
+193.222.248.0/23 MATCH
+193.222.250.0/24 MATCH
+193.246.121.0/24 MATCH
+193.246.124.0/23 MATCH
+193.246.176.0/20 MATCH
+193.247.190.0/23 MATCH
+193.247.203.0/24 MATCH
+193.247.240.0/22 MATCH
+193.247.248.0/23 MATCH
+193.247.254.0/24 MATCH
+194.153.96.0/24 MATCH
+195.176.0.0/17 MATCH
+195.176.160.0/19 MATCH
+195.176.224.0/19 MATCH
+198.21.18.0/24 miss
+2001:620::/29 MATCH
+2001:620::/32 MATCH
+2001:678:678::/48 MATCH
+2001:67c:10ec::/48 MATCH
+2001:67c:13c0::/48 MATCH
+2001:67c:16dc::/48 MATCH
+2a02:7dc0::/32 MATCH
+2a07:290a::/32 MATCH
+2a07:3e00::/29 MATCH
+2a07:6b40::/29 MATCH
+2a0a:4ec0::/29 MATCH
+2a0b:2040::/29 MATCH
+199.185.136.0/23 miss
+199.185.178.0/24 miss
+199.185.230.0/23 miss
+204.174.115.0/24 miss
+204.209.252.0/24 miss
+204.209.253.0/24 miss
+2620:3d:c000::/48 miss
+2a0c:fffe::2/127 MATCH
+2a0c:fffd::/127 miss
Index: regress/usr.sbin/bgpd/unittests/rde_trie_test.5.check
===================================================================
RCS file: regress/usr.sbin/bgpd/unittests/rde_trie_test.5.check
diff -N regress/usr.sbin/bgpd/unittests/rde_trie_test.5.check
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ regress/usr.sbin/bgpd/unittests/rde_trie_test.5.check 14 Sep 2018
14:10:05 -0000
@@ -0,0 +1,37 @@
+2a01:c00::/24 source-as 6805
+2a01:c00::/24 source-as 42
+2a01:c00::/26 source-as 6805
+2a01:c00::/26 source-as 42
+2a01:c00::/28 source-as 6805
+2a01:c00::/28 source-as 42
+2a01:c50::/28 source-as 12479
+2a01:c500::/31 source-as 12479
+2a01:c500::/32 source-as 12479
+2a01:c500::/42 source-as 12479
+2a01:c500::/42 source-as 6805
+2a01:c500::/42 source-as 42
+2a01:c500::/46 source-as 12479
+2a01:c500::/48 source-as 12479
+2a01:c500::/48 source-as 6805
+2a01:c500::/48 source-as 42
+80.128.0.0/11
+80.128.0.0/11 source-as 3320
+80.128.0.0/11 source-as 42
+80.128.0.0/12 source-as 3320
+80.128.0.0/12 source-as 42
+80.128.0.0/13 source-as 3320
+80.128.0.0/13 source-as 42
+80.144.0.0/13 source-as 3320
+80.144.0.0/14 source-as 3320
+80.157.16.0/20 source-as 3320
+80.157.16.0/21 source-as 3320
+80.158.0.0/17 source-as 34086
+80.158.120.0/21 source-as 34086
+80.158.0.0/17 source-as 3320
+80.158.120.0/21 source-as 42
+80.159.224.0/19 source-as 2792
+80.159.225.0/24 source-as 2792
+80.159.224.0/19 source-as 3320
+80.159.225.0/24 source-as 3320
+80.159.224.0/19 source-as 42
+80.159.225.0/24 source-as 42
Index: regress/usr.sbin/bgpd/unittests/rde_trie_test.5.in
===================================================================
RCS file: regress/usr.sbin/bgpd/unittests/rde_trie_test.5.in
diff -N regress/usr.sbin/bgpd/unittests/rde_trie_test.5.in
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ regress/usr.sbin/bgpd/unittests/rde_trie_test.5.in 14 Sep 2018 14:10:05
-0000
@@ -0,0 +1,47 @@
+source-as 6805
+prefix 2a01:c00::/26
+source-as 12479 maxlen 46
+prefix 2a01:c500::/28
+source-as 12479 maxlen 42
+prefix 2a01:c500::/31
+source-as 3215 maxlen 48
+prefix 2a01:c910::/29
+source-as 51964 maxlen 48
+prefix 2a01:ce80::/26
+source-as 20603 maxlen 48
+prefix 2a01:cf00::/40
+source-as 2278 maxlen 48
+prefix 2a01:cf00::/42
+source-as 2278
+prefix 2a01:cf00:f::/48
+source-as 12322 maxlen 32
+prefix 2a01:e00::/26
+source-as 12322
+prefix 2a01:e00::/32
+source-as 12322
+prefix 2a01:e01::/32
+source-as 12322
+prefix 2a01:e02::/32
+source-as 12322
+prefix 2a01:e0a::/38
+source-as 0 maxlen 11
+source-as 3320
+prefix 80.128.0.0/11
+source-as 3320
+prefix 80.128.0.0/12
+source-as 3320
+prefix 80.144.0.0/13
+source-as 3320
+prefix 80.152.0.0/14
+source-as 3320
+prefix 80.156.0.0/16
+source-as 3320
+prefix 80.157.0.0/16
+source-as 3320
+prefix 80.157.16.0/20
+source-as 3320
+prefix 80.157.8.0/21
+source-as 34086 maxlen 21
+prefix 80.158.0.0/17
+source-as 2792 maxlen 24
+prefix 80.159.224.0/19
Index: regress/usr.sbin/bgpd/unittests/rde_trie_test.5.out
===================================================================
RCS file: regress/usr.sbin/bgpd/unittests/rde_trie_test.5.out
diff -N regress/usr.sbin/bgpd/unittests/rde_trie_test.5.out
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ regress/usr.sbin/bgpd/unittests/rde_trie_test.5.out 14 Sep 2018 14:10:05
-0000
@@ -0,0 +1,37 @@
+2a01:c00::/24 source-as 6805 is not found
+2a01:c00::/24 source-as 42 is not found
+2a01:c00::/26 source-as 6805 is VALID
+2a01:c00::/26 source-as 42 is invalid
+2a01:c00::/28 source-as 6805 is invalid
+2a01:c00::/28 source-as 42 is invalid
+2a01:c50::/28 source-as 12479 is not found
+2a01:c500::/31 source-as 12479 is VALID
+2a01:c500::/32 source-as 12479 is VALID
+2a01:c500::/42 source-as 12479 is VALID
+2a01:c500::/42 source-as 6805 is invalid
+2a01:c500::/42 source-as 42 is invalid
+2a01:c500::/46 source-as 12479 is VALID
+2a01:c500::/48 source-as 12479 is invalid
+2a01:c500::/48 source-as 6805 is invalid
+2a01:c500::/48 source-as 42 is invalid
+80.128.0.0/11 source-as 0 is invalid
+80.128.0.0/11 source-as 3320 is invalid
+80.128.0.0/11 source-as 42 is invalid
+80.128.0.0/12 source-as 3320 is invalid
+80.128.0.0/12 source-as 42 is invalid
+80.128.0.0/13 source-as 3320 is invalid
+80.128.0.0/13 source-as 42 is invalid
+80.144.0.0/13 source-as 3320 is invalid
+80.144.0.0/14 source-as 3320 is invalid
+80.157.16.0/20 source-as 3320 is invalid
+80.157.16.0/21 source-as 3320 is invalid
+80.158.0.0/17 source-as 34086 is VALID
+80.158.120.0/21 source-as 34086 is VALID
+80.158.0.0/17 source-as 3320 is invalid
+80.158.120.0/21 source-as 42 is invalid
+80.159.224.0/19 source-as 2792 is VALID
+80.159.225.0/24 source-as 2792 is VALID
+80.159.224.0/19 source-as 3320 is invalid
+80.159.225.0/24 source-as 3320 is invalid
+80.159.224.0/19 source-as 42 is invalid
+80.159.225.0/24 source-as 42 is invalid
Index: regress/usr.sbin/bgpd/unittests/rde_trie_test.c
===================================================================
RCS file: /cvs/src/regress/usr.sbin/bgpd/unittests/rde_trie_test.c,v
retrieving revision 1.3
diff -u -p -r1.3 rde_trie_test.c
--- regress/usr.sbin/bgpd/unittests/rde_trie_test.c 10 Sep 2018 20:51:59
-0000 1.3
+++ regress/usr.sbin/bgpd/unittests/rde_trie_test.c 14 Sep 2018 14:10:05
-0000
@@ -20,6 +20,7 @@
#include <sys/socket.h>
#include <err.h>
+#include <limits.h>
#include <netdb.h>
#include <string.h>
#include <stdlib.h>
@@ -30,9 +31,11 @@
#include "bgpd.h"
#include "rde.h"
+int roa;
+int orlonger;
static int
-host_v4(const char *s, struct bgpd_addr *h, u_int8_t *len, int *orl)
+host_v4(const char *s, struct bgpd_addr *h, u_int8_t *len)
{
struct in_addr ina = { 0 };
int bits = 32;
@@ -52,7 +55,7 @@ host_v4(const char *s, struct bgpd_addr
}
static int
-host_v6(const char *s, struct bgpd_addr *h, u_int8_t *len, int *orl)
+host_v6(const char *s, struct bgpd_addr *h, u_int8_t *len)
{
struct addrinfo hints, *res;
const char *errstr;
@@ -85,21 +88,11 @@ host_v6(const char *s, struct bgpd_addr
}
static int
-host_l(char *s, struct bgpd_addr *h, u_int8_t *len, int *orl)
+host_l(char *s, struct bgpd_addr *h, u_int8_t *len)
{
- char *c, *t;
-
- *orl = 0;
- if ((c = strchr(s, '\t')) != NULL) {
- if (c[1] == '1') {
- *orl = 1;
- }
- *c = '\0';
- }
-
- if (host_v4(s, h, len, orl))
+ if (host_v4(s, h, len))
return (1);
- if (host_v6(s, h, len, orl))
+ if (host_v6(s, h, len))
return (1);
return (0);
}
@@ -127,34 +120,31 @@ parse_file(FILE *in, struct trie_head *t
const char *errstr;
char *line, *s;
struct bgpd_addr prefix;
- u_int8_t plen, min, max, maskmax;
- int foo;
+ u_int8_t plen;
while ((line = fparseln(in, NULL, NULL, NULL, FPARSELN_UNESCALL))) {
int state = 0;
- while ((s = strsep(&line, " \t"))) {
+ u_int8_t min = 255, max = 255, maskmax = 0;
+
+ while ((s = strsep(&line, " \t\n"))) {
if (*s == '\0')
- break;
+ continue;
switch (state) {
case 0:
- if (!host_l(s, &prefix, &plen, &foo))
- errx(1, "could not parse prefix \"%s\"",
- s);
- break;
- case 1:
+ if (!host_l(s, &prefix, &plen))
+ errx(1, "%s: could not parse "
+ "prefix \"%s\"", __func__, s);
if (prefix.aid == AID_INET6)
maskmax = 128;
else
maskmax = 32;
+ break;
+ case 1:
min = strtonum(s, 0, maskmax, &errstr);
if (errstr != NULL)
errx(1, "min is %s: %s", errstr, s);
break;
case 2:
- if (prefix.aid == AID_INET6)
- maskmax = 128;
- else
- maskmax = 32;
max = strtonum(s, 0, maskmax, &errstr);
if (errstr != NULL)
errx(1, "max is %s: %s", errstr, s);
@@ -164,6 +154,12 @@ parse_file(FILE *in, struct trie_head *t
}
state++;
}
+ if (state == 0)
+ continue;
+ if (max == 255)
+ max = maskmax;
+ if (min == 255)
+ min = plen;
if (trie_add(th, &prefix, plen, min, max) != 0)
errx(1, "trie_add(%s, %u, %u, %u) failed",
@@ -174,21 +170,142 @@ parse_file(FILE *in, struct trie_head *t
}
static void
+parse_roa_file(FILE *in, struct trie_head *th)
+{
+ const char *errstr;
+ char *line, *s;
+ struct as_set *aset = NULL;
+ struct roa_set rs;
+ struct bgpd_addr prefix;
+ u_int8_t plen;
+
+ while ((line = fparseln(in, NULL, NULL, NULL, FPARSELN_UNESCALL))) {
+ int state = 0;
+ u_int32_t as;
+ u_int8_t max = 0;
+
+ while ((s = strsep(&line, " \t\n"))) {
+ if (*s == '\0')
+ continue;
+ if (strcmp(s, "source-as") == 0) {
+ state = 4;
+ continue;
+ }
+ if (strcmp(s, "maxlen") == 0) {
+ state = 2;
+ continue;
+ }
+ if (strcmp(s, "prefix") == 0) {
+ state = 0;
+ continue;
+ }
+ switch (state) {
+ case 0:
+ if (!host_l(s, &prefix, &plen))
+ errx(1, "%s: could not parse "
+ "prefix \"%s\"", __func__, s);
+ break;
+ case 2:
+ max = strtonum(s, 0, 128, &errstr);
+ if (errstr != NULL)
+ errx(1, "max is %s: %s", errstr, s);
+ break;
+ case 4:
+ as = strtonum(s, 0, UINT_MAX, &errstr);
+ if (errstr != NULL)
+ errx(1, "source-as is %s: %s", errstr,
+ s);
+ break;
+ default:
+ errx(1, "could not parse \"%s\", confused", s);
+ }
+ }
+
+ if (state == 0) {
+ as_set_prep(aset);
+ if (trie_roa_add(th, &prefix, plen, aset) != 0)
+ errx(1, "trie_roa_add(%s, %u) failed",
+ print_prefix(&prefix), plen);
+ aset = NULL;
+ } else {
+ if (aset == NULL) {
+ if ((aset = as_set_new("", 1, sizeof(rs))) ==
+ NULL)
+ err(1, "as_set_new");
+ }
+ rs.as = as;
+ rs.maxlen = max;
+ if (as_set_add(aset, &rs, 1) != 0)
+ err(1, "as_set_add");
+ }
+
+ free(line);
+ }
+}
+
+static void
test_file(FILE *in, struct trie_head *th)
{
char *line;
struct bgpd_addr prefix;
u_int8_t plen;
- int orlonger;
while ((line = fparseln(in, NULL, NULL, NULL, FPARSELN_UNESCALL))) {
- if (!host_l(line, &prefix, &plen, &orlonger))
- errx(1, "could not parse prefix \"%s\"", line);
- printf("%s ", line);
+ if (!host_l(line, &prefix, &plen))
+ errx(1, "%s: could not parse prefix \"%s\"",
+ __func__, line);
+ printf("%s/%u ", print_prefix(&prefix), plen);
if (trie_match(th, &prefix, plen, orlonger))
- printf("MATCH %i\n", orlonger);
+ printf("MATCH\n");
else
- printf("miss %i\n", orlonger);
+ printf("miss\n");
+ free(line);
+ }
+}
+
+static void
+test_roa_file(FILE *in, struct trie_head *th)
+{
+ const char *errstr;
+ char *line, *s;
+ struct bgpd_addr prefix;
+ u_int8_t plen;
+ u_int32_t as;
+ int r;
+
+ while ((line = fparseln(in, NULL, NULL, NULL, FPARSELN_UNESCALL))) {
+ s = strchr(line, ' ');
+ if (s)
+ *s++ = '\0';
+ if (!host_l(line, &prefix, &plen))
+ errx(1, "%s: could not parse prefix \"%s\"",
+ __func__, line);
+ if (s)
+ s = strstr(s, "source-as");
+ if (s) {
+ s += strlen("source-as");
+ as = strtonum(s, 0, UINT_MAX, &errstr);
+ if (errstr != NULL)
+ errx(1, "source-as is %s: %s", errstr, s);
+ } else
+ as = 0;
+ printf("%s/%u source-as %u is ",
+ print_prefix(&prefix), plen, as);
+ r = trie_roa_check(th, &prefix, plen, as);
+ switch (r) {
+ case ROA_UNKNOWN:
+ printf("not found\n");
+ break;
+ case ROA_VALID:
+ printf("VALID\n");
+ break;
+ case ROA_INVALID:
+ printf("invalid\n");
+ break;
+ default:
+ printf("UNEXPECTED %d\n", r);
+ break;
+ }
free(line);
}
}
@@ -197,7 +314,7 @@ static void
usage(void)
{
extern char *__progname;
- fprintf(stderr, "usage: %s prefixfile testfile\n", __progname);
+ fprintf(stderr, "usage: %s [-or] prefixfile testfile\n", __progname);
exit(1);
}
@@ -208,21 +325,43 @@ main(int argc, char **argv)
FILE *in, *tin;
int ch;
- if (argc != 3)
+ while ((ch = getopt(argc, argv, "or")) != -1) {
+ switch (ch) {
+ case 'o':
+ orlonger = 1;
+ break;
+ case 'r':
+ roa = 1;
+ break;
+ default:
+ usage();
+ /* NOTREACHED */
+ }
+ }
+ argc -= optind;
+ argv += optind;
+
+ if (argc != 2)
usage();
- in = fopen(argv[1], "r");
+ in = fopen(argv[0], "r");
if (in == NULL)
err(1, "fopen(%s)", argv[0]);
- tin = fopen(argv[2], "r");
+ tin = fopen(argv[1], "r");
if (tin == NULL)
err(1, "fopen(%s)", argv[1]);
- parse_file(in, &th);
+ if (roa)
+ parse_roa_file(in, &th);
+ else
+ parse_file(in, &th);
/* trie_dump(&th); */
if (trie_equal(&th, &th) == 0)
errx(1, "trie_equal failure");
- test_file(tin, &th);
+ if (roa)
+ test_roa_file(tin, &th);
+ else
+ test_file(tin, &th);
trie_free(&th);
}
