summaryrefslogtreecommitdiff
path: root/nest
diff options
context:
space:
mode:
Diffstat (limited to 'nest')
-rw-r--r--nest/a-path_test.c30
-rw-r--r--nest/a-set.c130
-rw-r--r--nest/a-set_test.c51
-rw-r--r--nest/attrs.h6
-rw-r--r--nest/cmds.c46
-rw-r--r--nest/config.Y53
-rw-r--r--nest/iface.c2
-rw-r--r--nest/route.h58
-rw-r--r--nest/rt-fib.c2
-rw-r--r--nest/rt-show.c84
-rw-r--r--nest/rt-table.c867
11 files changed, 1130 insertions, 199 deletions
diff --git a/nest/a-path_test.c b/nest/a-path_test.c
index 9ed0a786..e007a450 100644
--- a/nest/a-path_test.c
+++ b/nest/a-path_test.c
@@ -23,8 +23,6 @@
static int
t_as_path_match(void)
{
- resource_init();
-
int round;
for (round = 0; round < TESTS_NUM; round++)
{
@@ -32,14 +30,13 @@ t_as_path_match(void)
struct adata *as_path = &empty_as_path;
u32 first_prepended, last_prepended;
first_prepended = last_prepended = 0;
- struct linpool *lp = lp_new_default(&root_pool);
struct f_path_mask *mask = alloca(sizeof(struct f_path_mask) + AS_PATH_LENGTH * sizeof(struct f_path_mask_item));
mask->len = AS_PATH_LENGTH;
for (int i = AS_PATH_LENGTH - 1; i >= 0; i--)
{
u32 val = bt_random();
- as_path = as_path_prepend(lp, as_path, val);
+ as_path = as_path_prepend(tmp_linpool, as_path, val);
bt_debug("Prepending ASN: %10u \n", val);
if (i == 0)
@@ -61,7 +58,7 @@ t_as_path_match(void)
bt_assert(as_path_get_last(as_path, &asn));
bt_assert_msg(asn == first_prepended, "as_path_get_last() should return the first prepended ASN");
- rfree(lp);
+ tmp_flush();
}
return 1;
@@ -70,16 +67,13 @@ t_as_path_match(void)
static int
t_path_format(void)
{
- resource_init();
-
struct adata empty_as_path = {};
struct adata *as_path = &empty_as_path;
- struct linpool *lp = lp_new_default(&root_pool);
uint i;
for (i = 4294967285; i <= 4294967294; i++)
{
- as_path = as_path_prepend(lp, as_path, i);
+ as_path = as_path_prepend(tmp_linpool, as_path, i);
bt_debug("Prepending ASN: %10u \n", i);
}
@@ -97,7 +91,7 @@ t_path_format(void)
as_path_format(as_path, buf2, SMALL_BUFFER_SIZE);
bt_assert_msg(strcmp(buf2, "4294967294 42...") == 0, "Small Buffer(%zu): '%s'", strlen(buf2), buf2);
- rfree(lp);
+ tmp_flush();
return 1;
}
@@ -116,11 +110,8 @@ count_asn_in_array(const u32 *array, u32 asn)
static int
t_path_include(void)
{
- resource_init();
-
struct adata empty_as_path = {};
struct adata *as_path = &empty_as_path;
- struct linpool *lp = lp_new_default(&root_pool);
u32 as_nums[AS_PATH_LENGTH] = {};
int i;
@@ -128,7 +119,7 @@ t_path_include(void)
{
u32 val = bt_random();
as_nums[i] = val;
- as_path = as_path_prepend(lp, as_path, val);
+ as_path = as_path_prepend(tmp_linpool, as_path, val);
}
for (i = 0; i < AS_PATH_LENGTH; i++)
@@ -136,8 +127,8 @@ t_path_include(void)
int counts_of_contains = count_asn_in_array(as_nums, as_nums[i]);
bt_assert_msg(as_path_contains(as_path, as_nums[i], counts_of_contains), "AS Path should contains %d-times number %d", counts_of_contains, as_nums[i]);
- bt_assert(as_path_filter(lp, as_path, NULL, as_nums[i], 0) != NULL);
- bt_assert(as_path_filter(lp, as_path, NULL, as_nums[i], 1) != NULL);
+ bt_assert(as_path_filter(tmp_linpool, as_path, NULL, as_nums[i], 0) != NULL);
+ bt_assert(as_path_filter(tmp_linpool, as_path, NULL, as_nums[i], 1) != NULL);
}
for (i = 0; i < 10000; i++)
@@ -152,7 +143,7 @@ t_path_include(void)
bt_assert_msg(result == 0, "As path should not contain the number %u", test_val);
}
- rfree(lp);
+ tmp_flush();
return 1;
}
@@ -161,16 +152,13 @@ t_path_include(void)
static int
t_as_path_converting(void)
{
- resource_init();
-
struct adata empty_as_path = {};
struct adata *as_path = &empty_as_path;
- struct linpool *lp = lp_new_default(&root_pool);
#define AS_PATH_LENGTH_FOR_CONVERTING_TEST 10
int i;
for (i = 0; i < AS_PATH_LENGTH_FOR_CONVERTING_TEST; i++)
- as_path = as_path_prepend(lp, as_path, i);
+ as_path = as_path_prepend(tmp_linpool, as_path, i);
bt_debug("data length: %u \n", as_path->length);
diff --git a/nest/a-set.c b/nest/a-set.c
index 1186eb56..71fbac94 100644
--- a/nest/a-set.c
+++ b/nest/a-set.c
@@ -516,6 +516,48 @@ int_set_sort(struct linpool *pool, const struct adata *src)
return dst;
}
+int
+int_set_min(const struct adata *list, u32 *val)
+{
+ if (!list)
+ return 0;
+
+ u32 *l = (u32 *) list->data;
+ int len = int_set_get_size(list);
+ int i;
+
+ if (len < 1)
+ return 0;
+
+ *val = *l++;
+ for (i = 1; i < len; i++, l++)
+ if (int_set_cmp(val, l) > 0)
+ *val = *l;
+
+ return 1;
+}
+
+int
+int_set_max(const struct adata *list, u32 *val)
+{
+ if (!list)
+ return 0;
+
+ u32 *l = (u32 *) list->data;
+ int len = int_set_get_size(list);
+ int i;
+
+ if (len < 1)
+ return 0;
+
+ *val = *l++;
+ for (i = 1; i < len; i++, l++)
+ if (int_set_cmp(val, l) < 0)
+ *val = *l;
+
+ return 1;
+}
+
static int
ec_set_cmp(const void *X, const void *Y)
@@ -541,6 +583,50 @@ ec_set_sort_x(struct adata *set)
qsort(set->data, set->length / 8, 8, ec_set_cmp);
}
+int
+ec_set_min(const struct adata *list, u64 *val)
+{
+ if (!list)
+ return 0;
+
+ u32 *l = int_set_get_data(list);
+ int len = int_set_get_size(list);
+ int i;
+
+ if (len < 1)
+ return 0;
+
+ u32 *res = l; l += 2;
+ for (i = 2; i < len; i += 2, l += 2)
+ if (ec_set_cmp(res, l) > 0)
+ res = l;
+
+ *val = ec_generic(res[0], res[1]);
+ return 1;
+}
+
+int
+ec_set_max(const struct adata *list, u64 *val)
+{
+ if (!list)
+ return 0;
+
+ u32 *l = int_set_get_data(list);
+ int len = int_set_get_size(list);
+ int i;
+
+ if (len < 1)
+ return 0;
+
+ u32 *res = l; l += 2;
+ for (i = 2; i < len; i += 2, l += 2)
+ if (ec_set_cmp(res, l) < 0)
+ res = l;
+
+ *val = ec_generic(res[0], res[1]);
+ return 1;
+}
+
static int
lc_set_cmp(const void *X, const void *Y)
@@ -563,3 +649,47 @@ lc_set_sort(struct linpool *pool, const struct adata *src)
qsort(dst->data, dst->length / LCOMM_LENGTH, LCOMM_LENGTH, lc_set_cmp);
return dst;
}
+
+int
+lc_set_min(const struct adata *list, lcomm *val)
+{
+ if (!list)
+ return 0;
+
+ u32 *l = int_set_get_data(list);
+ int len = int_set_get_size(list);
+ int i;
+
+ if (len < 1)
+ return 0;
+
+ u32 *res = l; l += 3;
+ for (i = 3; i < len; i += 3, l += 3)
+ if (lc_set_cmp(res, l) > 0)
+ res = l;
+
+ *val = (lcomm) { res[0], res[1], res[2] };
+ return 1;
+}
+
+int
+lc_set_max(const struct adata *list, lcomm *val)
+{
+ if (!list)
+ return 0;
+
+ u32 *l = int_set_get_data(list);
+ int len = int_set_get_size(list);
+ int i;
+
+ if (len < 1)
+ return 0;
+
+ u32 *res = l; l += 3;
+ for (i = 3; i < len; i += 3, l += 3)
+ if (lc_set_cmp(res, l) < 0)
+ res = l;
+
+ *val = (lcomm) { res[0], res[1], res[2] };
+ return 1;
+}
diff --git a/nest/a-set_test.c b/nest/a-set_test.c
index 96b6a727..904e6764 100644
--- a/nest/a-set_test.c
+++ b/nest/a-set_test.c
@@ -25,8 +25,6 @@ static byte buf[BUFFER_SIZE] = {};
#define SET_SIZE_FOR_FORMAT_OUTPUT 10
-struct linpool *lp;
-
enum set_type
{
SET_TYPE_INT,
@@ -38,24 +36,23 @@ generate_set_sequence(enum set_type type, int len)
{
struct adata empty_as_path = {};
set_sequence = set_sequence_same = set_sequence_higher = set_random = &empty_as_path;
- lp = lp_new_default(&root_pool);
int i;
for (i = 0; i < len; i++)
{
if (type == SET_TYPE_INT)
{
- set_sequence = int_set_add(lp, set_sequence, i);
- set_sequence_same = int_set_add(lp, set_sequence_same, i);
- set_sequence_higher = int_set_add(lp, set_sequence_higher, i + SET_SIZE);
- set_random = int_set_add(lp, set_random, bt_random());
+ set_sequence = int_set_add(tmp_linpool, set_sequence, i);
+ set_sequence_same = int_set_add(tmp_linpool, set_sequence_same, i);
+ set_sequence_higher = int_set_add(tmp_linpool, set_sequence_higher, i + SET_SIZE);
+ set_random = int_set_add(tmp_linpool, set_random, bt_random());
}
else if (type == SET_TYPE_EC)
{
- set_sequence = ec_set_add(lp, set_sequence, i);
- set_sequence_same = ec_set_add(lp, set_sequence_same, i);
- set_sequence_higher = ec_set_add(lp, set_sequence_higher, i + SET_SIZE);
- set_random = ec_set_add(lp, set_random, (bt_random() << 32 | bt_random()));
+ set_sequence = ec_set_add(tmp_linpool, set_sequence, i);
+ set_sequence_same = ec_set_add(tmp_linpool, set_sequence_same, i);
+ set_sequence_higher = ec_set_add(tmp_linpool, set_sequence_higher, i + SET_SIZE);
+ set_random = ec_set_add(tmp_linpool, set_random, (bt_random() << 32 | bt_random()));
}
else
bt_abort_msg("This should be unreachable");
@@ -71,7 +68,6 @@ t_set_int_contains(void)
{
int i;
- resource_init();
generate_set_sequence(SET_TYPE_INT, SET_SIZE);
bt_assert(int_set_get_size(set_sequence) == SET_SIZE);
@@ -85,33 +81,29 @@ t_set_int_contains(void)
for (i = 0; i < SET_SIZE; i++)
bt_assert_msg(data[i] == i, "(data[i] = %d) == i = %d)", data[i], i);
- rfree(lp);
return 1;
}
static int
t_set_int_union(void)
{
- resource_init();
generate_set_sequence(SET_TYPE_INT, SET_SIZE);
const struct adata *set_union;
- set_union = int_set_union(lp, set_sequence, set_sequence_same);
+ set_union = int_set_union(tmp_linpool, set_sequence, set_sequence_same);
bt_assert(int_set_get_size(set_union) == SET_SIZE);
bt_assert(int_set_format(set_union, 0, 2, buf, BUFFER_SIZE) == 0);
- set_union = int_set_union(lp, set_sequence, set_sequence_higher);
+ set_union = int_set_union(tmp_linpool, set_sequence, set_sequence_higher);
bt_assert_msg(int_set_get_size(set_union) == SET_SIZE*2, "int_set_get_size(set_union) %d, SET_SIZE*2 %d", int_set_get_size(set_union), SET_SIZE*2);
bt_assert(int_set_format(set_union, 0, 2, buf, BUFFER_SIZE) == 0);
- rfree(lp);
return 1;
}
static int
t_set_int_format(void)
{
- resource_init();
generate_set_sequence(SET_TYPE_INT, SET_SIZE_FOR_FORMAT_OUTPUT);
bt_assert(int_set_format(set_sequence, 0, 0, buf, BUFFER_SIZE) == 0);
@@ -125,21 +117,19 @@ t_set_int_format(void)
bt_assert(int_set_format(set_sequence, 1, 0, buf, BUFFER_SIZE) == 0);
bt_assert(strcmp(buf, "(0,0) (0,1) (0,2) (0,3) (0,4) (0,5) (0,6) (0,7) (0,8) (0,9)") == 0);
- rfree(lp);
return 1;
}
static int
t_set_int_delete(void)
{
- resource_init();
generate_set_sequence(SET_TYPE_INT, SET_SIZE);
const struct adata *deleting_sequence = set_sequence;
u32 i;
for (i = 0; i < SET_SIZE; i++)
{
- deleting_sequence = int_set_del(lp, deleting_sequence, i);
+ deleting_sequence = int_set_del(tmp_linpool, deleting_sequence, i);
bt_assert_msg(int_set_get_size(deleting_sequence) == (int) (SET_SIZE-1-i),
"int_set_get_size(deleting_sequence) %d == SET_SIZE-1-i %d",
int_set_get_size(deleting_sequence),
@@ -160,7 +150,6 @@ t_set_ec_contains(void)
{
u32 i;
- resource_init();
generate_set_sequence(SET_TYPE_EC, SET_SIZE);
bt_assert(ec_set_get_size(set_sequence) == SET_SIZE);
@@ -174,62 +163,54 @@ t_set_ec_contains(void)
// for (i = 0; i < SET_SIZE; i++)
// bt_assert_msg(data[i] == (SET_SIZE-1-i), "(data[i] = %d) == ((SET_SIZE-1-i) = %d)", data[i], SET_SIZE-1-i);
- rfree(lp);
return 1;
}
static int
t_set_ec_union(void)
{
- resource_init();
generate_set_sequence(SET_TYPE_EC, SET_SIZE);
const struct adata *set_union;
- set_union = ec_set_union(lp, set_sequence, set_sequence_same);
+ set_union = ec_set_union(tmp_linpool, set_sequence, set_sequence_same);
bt_assert(ec_set_get_size(set_union) == SET_SIZE);
bt_assert(ec_set_format(set_union, 0, buf, BUFFER_SIZE) == 0);
- set_union = ec_set_union(lp, set_sequence, set_sequence_higher);
+ set_union = ec_set_union(tmp_linpool, set_sequence, set_sequence_higher);
bt_assert_msg(ec_set_get_size(set_union) == SET_SIZE*2, "ec_set_get_size(set_union) %d, SET_SIZE*2 %d", ec_set_get_size(set_union), SET_SIZE*2);
bt_assert(ec_set_format(set_union, 0, buf, BUFFER_SIZE) == 0);
- rfree(lp);
return 1;
}
static int
t_set_ec_format(void)
{
- resource_init();
-
const struct adata empty_as_path = {};
set_sequence = set_sequence_same = set_sequence_higher = set_random = &empty_as_path;
- lp = lp_new_default(&root_pool);
u64 i = 0;
- set_sequence = ec_set_add(lp, set_sequence, i);
+ set_sequence = ec_set_add(tmp_linpool, set_sequence, i);
for (i = 1; i < SET_SIZE_FOR_FORMAT_OUTPUT; i++)
- set_sequence = ec_set_add(lp, set_sequence, i + ((i%2) ? ((u64)EC_RO << 48) : ((u64)EC_RT << 48)));
+ set_sequence = ec_set_add(tmp_linpool, set_sequence, i + ((i%2) ? ((u64)EC_RO << 48) : ((u64)EC_RT << 48)));
bt_assert(ec_set_format(set_sequence, 0, buf, BUFFER_SIZE) == 0);
bt_assert_msg(strcmp(buf, "(unknown 0x0, 0, 0) (ro, 0, 1) (rt, 0, 2) (ro, 0, 3) (rt, 0, 4) (ro, 0, 5) (rt, 0, 6) (ro, 0, 7) (rt, 0, 8) (ro, 0, 9)") == 0,
"ec_set_format() returns '%s'", buf);
- rfree(lp);
return 1;
}
static int
t_set_ec_delete(void)
{
- resource_init();
generate_set_sequence(SET_TYPE_EC, SET_SIZE);
const struct adata *deleting_sequence = set_sequence;
u32 i;
for (i = 0; i < SET_SIZE; i++)
{
- deleting_sequence = ec_set_del(lp, deleting_sequence, i);
+ deleting_sequence = ec_set_del(tmp_linpool, deleting_sequence, i);
bt_assert_msg(ec_set_get_size(deleting_sequence) == (int) (SET_SIZE-1-i),
"ec_set_get_size(deleting_sequence) %d == SET_SIZE-1-i %d",
ec_set_get_size(deleting_sequence), SET_SIZE-1-i);
diff --git a/nest/attrs.h b/nest/attrs.h
index 50da817b..ef2b95e6 100644
--- a/nest/attrs.h
+++ b/nest/attrs.h
@@ -218,6 +218,12 @@ struct adata *ec_set_del_nontrans(struct linpool *pool, const struct adata *set)
struct adata *int_set_sort(struct linpool *pool, const struct adata *src);
struct adata *ec_set_sort(struct linpool *pool, const struct adata *src);
struct adata *lc_set_sort(struct linpool *pool, const struct adata *src);
+int int_set_min(const struct adata *list, u32 *val);
+int ec_set_min(const struct adata *list, u64 *val);
+int lc_set_min(const struct adata *list, lcomm *val);
+int int_set_max(const struct adata *list, u32 *val);
+int ec_set_max(const struct adata *list, u64 *val);
+int lc_set_max(const struct adata *list, lcomm *val);
void ec_set_sort_x(struct adata *set); /* Sort in place */
diff --git a/nest/cmds.c b/nest/cmds.c
index 18f39eb5..8481bf96 100644
--- a/nest/cmds.c
+++ b/nest/cmds.c
@@ -67,31 +67,63 @@ cmd_show_symbols(struct sym_show_data *sd)
}
}
-static void
-print_size(char *dsc, size_t val)
+#define SIZE_SUFFIX " kMGT"
+#define SIZE_FORMAT "% 4u.%1u % 1cB"
+#define SIZE_ARGS(a) (a).val, (a).decimal, SIZE_SUFFIX[(a).magnitude]
+
+struct size_args {
+ u64 val:48;
+ u64 decimal:8;
+ u64 magnitude:8;
+};
+
+static struct size_args
+get_size_args(u64 val)
{
- char *px = " kMG";
- int i = 0;
- while ((val >= 10000) && (i < 3))
+#define VALDEC 10 /* One decimal place */
+ val *= VALDEC;
+
+ uint i = 0;
+ while ((val >= 10000 * VALDEC) && (i < 4))
{
val = (val + 512) / 1024;
i++;
}
- cli_msg(-1018, "%-17s %4u %cB", dsc, (unsigned) val, px[i]);
+ return (struct size_args) {
+ .val = (val / VALDEC),
+ .decimal = (val % VALDEC),
+ .magnitude = i,
+ };
+}
+
+static void
+print_size(char *dsc, struct resmem vals)
+{
+ struct size_args effective = get_size_args(vals.effective);
+ struct size_args overhead = get_size_args(vals.overhead);
+
+ cli_msg(-1018, "%-17s " SIZE_FORMAT " " SIZE_FORMAT, dsc, SIZE_ARGS(effective), SIZE_ARGS(overhead));
}
extern pool *rt_table_pool;
extern pool *rta_pool;
+extern uint *pages_kept;
void
cmd_show_memory(void)
{
cli_msg(-1018, "BIRD memory usage");
+ cli_msg(-1018, "%-17s Effective Overhead", "");
print_size("Routing tables:", rmemsize(rt_table_pool));
print_size("Route attributes:", rmemsize(rta_pool));
print_size("Protocols:", rmemsize(proto_pool));
- print_size("Total:", rmemsize(&root_pool));
+ struct resmem total = rmemsize(&root_pool);
+#ifdef HAVE_MMAP
+ print_size("Standby memory:", (struct resmem) { .overhead = page_size * *pages_kept });
+ total.overhead += page_size * *pages_kept;
+#endif
+ print_size("Total:", total);
cli_msg(0, "");
}
diff --git a/nest/config.Y b/nest/config.Y
index a1d901ab..1bebc084 100644
--- a/nest/config.Y
+++ b/nest/config.Y
@@ -17,6 +17,7 @@ CF_HDR
CF_DEFINES
+static struct rtable_config *this_table;
static struct proto_config *this_proto;
static struct channel_config *this_channel;
static struct iface_patt *this_ipatt;
@@ -117,13 +118,14 @@ CF_KEYWORDS(IPV4, IPV6, VPN4, VPN6, ROA4, ROA6, FLOW4, FLOW6, SADR, MPLS)
CF_KEYWORDS(RECEIVE, LIMIT, ACTION, WARN, BLOCK, RESTART, DISABLE, KEEP, FILTERED, RPKI)
CF_KEYWORDS(PASSWORD, KEY, FROM, PASSIVE, TO, ID, EVENTS, PACKETS, PROTOCOLS, CHANNELS, INTERFACES)
CF_KEYWORDS(ALGORITHM, KEYED, HMAC, MD5, SHA1, SHA256, SHA384, SHA512, BLAKE2S128, BLAKE2S256, BLAKE2B256, BLAKE2B512)
-CF_KEYWORDS(PRIMARY, STATS, COUNT, BY, FOR, COMMANDS, PREEXPORT, NOEXPORT, EXPORTED, GENERATE)
-CF_KEYWORDS(BGP, PASSWORDS, DESCRIPTION, SORTED)
+CF_KEYWORDS(PRIMARY, STATS, COUNT, BY, FOR, IN, COMMANDS, PREEXPORT, NOEXPORT, EXPORTED, GENERATE)
+CF_KEYWORDS(BGP, PASSWORDS, DESCRIPTION)
CF_KEYWORDS(RELOAD, IN, OUT, MRTDUMP, MESSAGES, RESTRICT, MEMORY, IGP_METRIC, CLASS, DSCP)
CF_KEYWORDS(TIMEFORMAT, ISO, SHORT, LONG, ROUTE, PROTOCOL, BASE, LOG, S, MS, US)
CF_KEYWORDS(GRACEFUL, RESTART, WAIT, MAX, FLUSH, AS)
CF_KEYWORDS(MIN, IDLE, RX, TX, INTERVAL, MULTIPLIER, PASSIVE)
CF_KEYWORDS(CHECK, LINK)
+CF_KEYWORDS(SORTED, TRIE, MIN, MAX, SETTLE, TIME)
/* For r_args_channel */
CF_KEYWORDS(IPV4, IPV4_MC, IPV4_MPLS, IPV6, IPV6_MC, IPV6_MPLS, IPV6_SADR, VPN4, VPN4_MC, VPN4_MPLS, VPN6, VPN6_MC, VPN6_MPLS, ROA4, ROA6, FLOW4, FLOW6, MPLS, PRI, SEC)
@@ -141,7 +143,7 @@ CF_ENUM_PX(T_ENUM_AF, AF_, AFI_, IPV4, IPV6)
%type <s> optproto
%type <ra> r_args
%type <sd> sym_args
-%type <i> proto_start echo_mask echo_size debug_mask debug_list debug_flag mrtdump_mask mrtdump_list mrtdump_flag export_mode limit_action net_type table_sorted tos password_algorithm
+%type <i> proto_start echo_mask echo_size debug_mask debug_list debug_flag mrtdump_mask mrtdump_list mrtdump_flag export_mode limit_action net_type tos password_algorithm
%type <ps> proto_patt proto_patt2
%type <cc> channel_start proto_channel
%type <cl> limit_spec
@@ -206,16 +208,37 @@ CF_ENUM(T_ENUM_NETTYPE, NET_, IP4, IP6, VPN4, VPN6, ROA4, ROA6, FLOW4, FLOW6, IP
conf: table ;
+table: table_start table_sorted table_opt_list ;
+
+table_start: net_type TABLE symbol {
+ this_table = rt_new_table($3, $1);
+ }
+ ;
+
table_sorted:
- { $$ = 0; }
- | SORTED { $$ = 1; }
+ /* empty */
+ | SORTED { this_table->sorted = 1; }
;
-table: net_type TABLE symbol table_sorted {
- struct rtable_config *cf;
- cf = rt_new_table($3, $1);
- cf->sorted = $4;
+table_opt:
+ SORTED bool { this_table->sorted = $2; }
+ | TRIE bool {
+ if (!net_val_match(this_table->addr_type, NB_IP | NB_VPN | NB_ROA | NB_IP6_SADR))
+ cf_error("Trie option not supported for %s table", net_label[this_table->addr_type]);
+ this_table->trie_used = $2;
}
+ | MIN SETTLE TIME expr_us { this_table->min_settle_time = $4; }
+ | MAX SETTLE TIME expr_us { this_table->max_settle_time = $4; }
+ ;
+
+table_opts:
+ /* empty */
+ | table_opts table_opt ';'
+ ;
+
+table_opt_list:
+ /* empty */
+ | '{' table_opts '}'
;
@@ -622,14 +645,22 @@ r_args:
$$ = $1;
if ($$->addr) cf_error("Only one prefix expected");
$$->addr = $2;
+ $$->addr_mode = RSD_ADDR_EQUAL;
}
| r_args FOR r_args_for {
$$ = $1;
if ($$->addr) cf_error("Only one prefix expected");
- $$->show_for = 1;
$$->addr = $3;
+ $$->addr_mode = RSD_ADDR_FOR;
+ }
+ | r_args IN net_any {
+ $$ = $1;
+ if ($$->addr) cf_error("Only one prefix expected");
+ if (!net_type_match($3, NB_IP)) cf_error("Only IP networks accepted for 'in' argument");
+ $$->addr = $3;
+ $$->addr_mode = RSD_ADDR_IN;
}
- | r_args TABLE CF_SYM_KNOWN {
+| r_args TABLE CF_SYM_KNOWN {
cf_assert_symbol($3, SYM_TABLE);
$$ = $1;
rt_show_add_table($$, $3->table->table);
diff --git a/nest/iface.c b/nest/iface.c
index 83a633a3..682340c5 100644
--- a/nest/iface.c
+++ b/nest/iface.c
@@ -591,7 +591,7 @@ ifa_update(struct ifa *a)
if (ipa_equal(b->brd, a->brd) &&
ipa_equal(b->opposite, a->opposite) &&
b->scope == a->scope &&
- !((b->flags ^ a->flags) & IA_PEER))
+ !((b->flags ^ a->flags) & (IA_SECONDARY | IA_PEER | IA_HOST)))
{
b->flags |= IA_UPDATED;
return b;
diff --git a/nest/route.h b/nest/route.h
index 9baaeda0..98d030a9 100644
--- a/nest/route.h
+++ b/nest/route.h
@@ -20,7 +20,10 @@ struct proto;
struct rte_src;
struct symbol;
struct timer;
+struct fib;
struct filter;
+struct f_trie;
+struct f_trie_walk_state;
struct cli;
/*
@@ -49,7 +52,7 @@ struct fib_iterator { /* See lib/slists.h for an explanation */
uint hash;
};
-typedef void (*fib_init_fn)(void *);
+typedef void (*fib_init_fn)(struct fib *, void *);
struct fib {
pool *fib_pool; /* Pool holding all our data */
@@ -149,6 +152,7 @@ struct rtable_config {
int gc_min_time; /* Minimum time between two consecutive GC runs */
byte sorted; /* Routes of network are sorted according to rte_better() */
byte internal; /* Internal table of a protocol */
+ byte trie_used; /* Rtable has attached trie */
btime min_settle_time; /* Minimum settle time for notifications */
btime max_settle_time; /* Maximum settle time for notifications */
};
@@ -159,6 +163,7 @@ typedef struct rtable {
pool *rp; /* Resource pool to allocate everything from, including itself */
struct slab *rte_slab; /* Slab to allocate route objects */
struct fib fib;
+ struct f_trie *trie; /* Trie of prefixes defined in fib */
char *name; /* Name of this table */
list channels; /* List of attached channels (struct channel) */
uint addr_type; /* Type of address data stored in table (NET_*) */
@@ -180,14 +185,21 @@ typedef struct rtable {
btime gc_time; /* Time of last GC */
int gc_counter; /* Number of operations since last GC */
byte prune_state; /* Table prune state, 1 -> scheduled, 2-> running */
+ byte prune_trie; /* Prune prefix trie during next table prune */
byte hcu_scheduled; /* Hostcache update is scheduled */
byte nhu_state; /* Next Hop Update state */
struct fib_iterator prune_fit; /* Rtable prune FIB iterator */
struct fib_iterator nhu_fit; /* Next Hop Update FIB iterator */
+ struct f_trie *trie_new; /* New prefix trie defined during pruning */
+ struct f_trie *trie_old; /* Old prefix trie waiting to be freed */
+ u32 trie_lock_count; /* Prefix trie locked by walks */
+ u32 trie_old_lock_count; /* Old prefix trie locked by walks */
struct tbf rl_pipe; /* Rate limiting token buffer for pipe collisions */
list subscribers; /* Subscribers for notifications */
struct timer *settle_timer; /* Settle time for notifications */
+ list flowspec_links; /* List of flowspec links, src for NET_IPx and dst for NET_FLOWx */
+ struct f_trie *flowspec_trie; /* Trie for evaluation of flowspec notifications */
} rtable;
struct rt_subscription {
@@ -197,6 +209,13 @@ struct rt_subscription {
void *data;
};
+struct rt_flowspec_link {
+ node n;
+ rtable *src;
+ rtable *dst;
+ u32 uc;
+};
+
#define NHU_CLEAN 0
#define NHU_SCHEDULED 1
#define NHU_RUNNING 2
@@ -262,7 +281,10 @@ struct rte_storage {
#define REF_MODIFY 16 /* Route is scheduled for modify */
/* Route is valid for propagation (may depend on other flags in the future), accepts NULL */
-static inline int rte_is_valid(rte *r) { return r && !(r->flags & REF_FILTERED); }
+static inline int rte_is_valid_rte(rte *r) { return r && !(r->flags & REF_FILTERED); }
+static inline int rte_is_valid_storage(struct rte_storage *r) { return r && rte_is_valid_rte(&r->rte); }
+
+#define rte_is_valid(r) _Generic((*r), rte: rte_is_valid_rte, struct rte_storage: rte_is_valid_storage)(r)
/* Route just has REF_FILTERED flag */
static inline int rte_is_filtered(rte *r) { return !!(r->flags & REF_FILTERED); }
@@ -323,8 +345,12 @@ void rt_preconfig(struct config *);
void rt_commit(struct config *new, struct config *old);
void rt_lock_table(rtable *);
void rt_unlock_table(rtable *);
+struct f_trie * rt_lock_trie(rtable *tab);
+void rt_unlock_trie(rtable *tab, struct f_trie *trie);
void rt_subscribe(rtable *tab, struct rt_subscription *s);
void rt_unsubscribe(struct rt_subscription *s);
+void rt_flowspec_link(rtable *src, rtable *dst);
+void rt_flowspec_unlink(rtable *src, rtable *dst);
rtable *rt_setup(pool *, struct rtable_config *);
static inline void rt_shutdown(rtable *r) { rfree(r->rp); }
@@ -332,7 +358,8 @@ static inline net *net_find(rtable *tab, const net_addr *addr) { return (net *)
static inline net *net_find_valid(rtable *tab, const net_addr *addr)
{ net *n = net_find(tab, addr); return (n && n->routes && rte_is_valid(&n->routes->rte)) ? n : NULL; }
static inline net *net_get(rtable *tab, const net_addr *addr) { return (net *) fib_get(&tab->fib, addr); }
-void *net_route(rtable *tab, const net_addr *n);
+net *net_get(rtable *tab, const net_addr *addr);
+net *net_route(rtable *tab, const net_addr *n);
int net_roa_check(rtable *tab, const net_addr *n, u32 asn);
int rt_examine(rtable *t, net_addr *a, struct channel *c, const struct filter *filter);
rte *rt_export_merged(struct channel *c, net *net, linpool *pool, int silent);
@@ -354,6 +381,18 @@ void rt_prune_sync(rtable *t, int all);
int rte_update_out(struct channel *c, const net_addr *n, rte *new, rte *old, struct rte_storage **old_exported);
struct rtable_config *rt_new_table(struct symbol *s, uint addr_type);
+static inline int rt_is_ip(rtable *tab)
+{ return (tab->addr_type == NET_IP4) || (tab->addr_type == NET_IP6); }
+
+static inline int rt_is_vpn(rtable *tab)
+{ return (tab->addr_type == NET_VPN4) || (tab->addr_type == NET_VPN6); }
+
+static inline int rt_is_roa(rtable *tab)
+{ return (tab->addr_type == NET_ROA4) || (tab->addr_type == NET_ROA6); }
+
+static inline int rt_is_flow(rtable *tab)
+{ return (tab->addr_type == NET_FLOW4) || (tab->addr_type == NET_FLOW6); }
+
/* Default limit for ECMP next hops, defined in sysdep code */
extern const int rt_default_ecmp;
@@ -370,6 +409,8 @@ struct rt_show_data {
struct rt_show_data_rtable *tab; /* Iterator over table list */
struct rt_show_data_rtable *last_table; /* Last table in output */
struct fib_iterator fit; /* Iterator over networks in table */
+ struct f_trie_walk_state *walk_state; /* Iterator over networks in trie */
+ struct f_trie *walk_lock; /* Locked trie for walking */
int verbose, tables_defined_by;
const struct filter *filter;
struct proto *show_protocol;
@@ -377,9 +418,10 @@ struct rt_show_data {
struct channel *export_channel;
struct config *running_on_config;
struct krt_proto *kernel;
- int export_mode, primary_only, filtered, stats, show_for;
+ int export_mode, addr_mode, primary_only, filtered, stats;
int table_open; /* Iteration (fit) is open */
+ int trie_walk; /* Current table is iterated using trie */
int net_counter, rt_counter, show_counter, table_counter;
int net_counter_last, rt_counter_last, show_counter_last;
};
@@ -396,6 +438,11 @@ struct rt_show_data_rtable * rt_show_add_table(struct rt_show_data *d, rtable *t
#define RSD_TDB_SET 0x1 /* internal: show empty tables */
#define RSD_TDB_NMN 0x2 /* internal: need matching net */
+/* Value of addr_mode */
+#define RSD_ADDR_EQUAL 1 /* Exact query - show route <addr> */
+#define RSD_ADDR_FOR 2 /* Longest prefix match - show route for <addr> */
+#define RSD_ADDR_IN 3 /* Interval query - show route in <addr> */
+
/* Value of export_mode in struct rt_show_data */
#define RSEM_NONE 0 /* Export mode not used */
#define RSEM_PREEXPORT 1 /* Routes ready for export, before filtering */
@@ -707,6 +754,9 @@ rta_set_recursive_next_hop(rtable *dep, rta *a, rtable *tab, ip_addr gw, ip_addr
static inline void rt_lock_hostentry(struct hostentry *he) { if (he) he->uc++; }
static inline void rt_unlock_hostentry(struct hostentry *he) { if (he) he->uc--; }
+int rt_flowspec_check(rtable *tab_ip, rtable *tab_flow, const net_addr *n, rta *a, int interior);
+
+
/*
* Default protocol preferences
*/
diff --git a/nest/rt-fib.c b/nest/rt-fib.c
index a7f70371..1690a8f6 100644
--- a/nest/rt-fib.c
+++ b/nest/rt-fib.c
@@ -331,7 +331,7 @@ fib_get(struct fib *f, const net_addr *a)
memset(b, 0, f->node_offset);
if (f->init)
- f->init(b);
+ f->init(f, b);
if (f->entries++ > f->entries_max)
fib_rehash(f, HASH_HI_STEP);
diff --git a/nest/rt-show.c b/nest/rt-show.c
index ae5000f5..7b05c64e 100644
--- a/nest/rt-show.c
+++ b/nest/rt-show.c
@@ -15,6 +15,7 @@
#include "nest/cli.h"
#include "nest/iface.h"
#include "filter/filter.h"
+#include "filter/data.h"
#include "sysdep/unix/krt.h"
static void
@@ -109,10 +110,9 @@ rt_show_net(struct cli *c, net *n, struct rt_show_data *d)
ASSUME(!d->export_mode || ec);
int first = 1;
+ int first_show = 1;
int pass = 0;
- bsnprintf(ia, sizeof(ia), "%N", n->n.addr);
-
for (struct rte_storage *er = n->routes; er; er = er->next)
{
if (rte_is_filtered(&er->rte) != d->filtered)
@@ -185,10 +185,17 @@ rt_show_net(struct cli *c, net *n, struct rt_show_data *d)
goto skip;
if (d->stats < 2)
+ {
+ if (first_show)
+ net_format(n->n.addr, ia, sizeof(ia));
+ else
+ ia[0] = 0;
+
rt_show_rte(c, ia, &e, d, (n->routes == er));
+ first_show = 0;
+ }
d->show_counter++;
- ia[0] = 0;
skip:
lp_flush(c->show_pool);
@@ -205,9 +212,12 @@ rt_show_cleanup(struct cli *c)
struct rt_show_data_rtable *tab;
/* Unlink the iterator */
- if (d->table_open)
+ if (d->table_open && !d->trie_walk)
fit_get(&d->tab->table->fib, &d->fit);
+ if (d->walk_lock)
+ rt_unlock_trie(d->tab->table, d->walk_lock);
+
/* Unlock referenced tables */
WALK_LIST(tab, d->tables)
rt_unlock_table(tab->table);
@@ -217,12 +227,13 @@ static void
rt_show_cont(struct cli *c)
{
struct rt_show_data *d = c->rover;
+ struct rtable *tab = d->tab->table;
#ifdef DEBUGGING
unsigned max = 4;
#else
unsigned max = 64;
#endif
- struct fib *fib = &d->tab->table->fib;
+ struct fib *fib = &tab->fib;
struct fib_iterator *it = &d->fit;
if (d->running_on_config && (d->running_on_config != config))
@@ -233,7 +244,22 @@ rt_show_cont(struct cli *c)
if (!d->table_open)
{
- FIB_ITERATE_INIT(&d->fit, &d->tab->table->fib);
+ /* We use either trie-based walk or fib-based walk */
+ d->trie_walk = tab->trie &&
+ (d->addr_mode == RSD_ADDR_IN) &&
+ net_val_match(tab->addr_type, NB_IP);
+
+ if (d->trie_walk && !d->walk_state)
+ d->walk_state = lp_allocz(c->parser_pool, sizeof (struct f_trie_walk_state));
+
+ if (d->trie_walk)
+ {
+ d->walk_lock = rt_lock_trie(tab);
+ trie_walk_init(d->walk_state, tab->trie, d->addr);
+ }
+ else
+ FIB_ITERATE_INIT(&d->fit, &tab->fib);
+
d->table_open = 1;
d->table_counter++;
d->kernel = rt_show_get_kernel(d);
@@ -246,16 +272,44 @@ rt_show_cont(struct cli *c)
rt_show_table(c, d);
}
- FIB_ITERATE_START(fib, it, net, n)
+ if (d->trie_walk)
+ {
+ /* Trie-based walk */
+ net_addr addr;
+ while (trie_walk_next(d->walk_state, &addr))
+ {
+ net *n = net_find(tab, &addr);
+ if (!n)
+ continue;
+
+ rt_show_net(c, n, d);
+
+ if (!--max)
+ return;
+ }
+
+ rt_unlock_trie(tab, d->walk_lock);
+ d->walk_lock = NULL;
+ }
+ else
{
- if (!max--)
+ /* fib-based walk */
+ FIB_ITERATE_START(fib, it, net, n)
{
- FIB_ITERATE_PUT(it);
- return;
+ if ((d->addr_mode == RSD_ADDR_IN) && (!net_in_netX(n->n.addr, d->addr)))
+ goto next;
+
+ if (!max--)
+ {
+ FIB_ITERATE_PUT(it);
+ return;
+ }
+ rt_show_net(c, n, d);
+
+ next:;
}
- rt_show_net(c, n, d);
+ FIB_ITERATE_END;
}
- FIB_ITERATE_END;
if (d->stats)
{
@@ -264,7 +318,7 @@ rt_show_cont(struct cli *c)
cli_printf(c, -1007, "%d of %d routes for %d networks in table %s",
d->show_counter - d->show_counter_last, d->rt_counter - d->rt_counter_last,
- d->net_counter - d->net_counter_last, d->tab->table->name);
+ d->net_counter - d->net_counter_last, tab->name);
}
d->kernel = NULL;
@@ -395,7 +449,7 @@ rt_show(struct rt_show_data *d)
rt_show_prepare_tables(d);
- if (!d->addr)
+ if (!d->addr || (d->addr_mode == RSD_ADDR_IN))
{
WALK_LIST(tab, d->tables)
rt_lock_table(tab->table);
@@ -413,7 +467,7 @@ rt_show(struct rt_show_data *d)
d->tab = tab;
d->kernel = rt_show_get_kernel(d);
- if (d->show_for)
+ if (d->addr_mode == RSD_ADDR_FOR)
n = net_route(tab->table, d->addr);
else
n = net_find(tab->table, d->addr);
diff --git a/nest/rt-table.c b/nest/rt-table.c
index 6851b4bc..36414ed4 100644
--- a/nest/rt-table.c
+++ b/nest/rt-table.c
@@ -26,6 +26,66 @@
* (see the route attribute module for a precise explanation) holding the
* remaining route attributes which are expected to be shared by multiple
* routes in order to conserve memory.
+ *
+ * There are several mechanisms that allow automatic update of routes in one
+ * routing table (dst) as a result of changes in another routing table (src).
+ * They handle issues of recursive next hop resolving, flowspec validation and
+ * RPKI validation.
+ *
+ * The first such mechanism is handling of recursive next hops. A route in the
+ * dst table has an indirect next hop address, which is resolved through a route
+ * in the src table (which may also be the same table) to get an immediate next
+ * hop. This is implemented using structure &hostcache attached to the src
+ * table, which contains &hostentry structures for each tracked next hop
+ * address. These structures are linked from recursive routes in dst tables,
+ * possibly multiple routes sharing one hostentry (as many routes may have the
+ * same indirect next hop). There is also a trie in the hostcache, which matches
+ * all prefixes that may influence resolving of tracked next hops.
+ *
+ * When a best route changes in the src table, the hostcache is notified using
+ * rt_notify_hostcache(), which immediately checks using the trie whether the
+ * change is relevant and if it is, then it schedules asynchronous hostcache
+ * recomputation. The recomputation is done by rt_update_hostcache() (called
+ * from rt_event() of src table), it walks through all hostentries and resolves
+ * them (by rt_update_hostentry()). It also updates the trie. If a change in
+ * hostentry resolution was found, then it schedules asynchronous nexthop
+ * recomputation of associated dst table. That is done by rt_next_hop_update()
+ * (called from rt_event() of dst table), it iterates over all routes in the dst
+ * table and re-examines their hostentries for changes. Note that in contrast to
+ * hostcache update, next hop update can be interrupted by main loop. These two
+ * full-table walks (over hostcache and dst table) are necessary due to absence
+ * of direct lookups (route -> affected nexthop, nexthop -> its route).
+ *
+ * The second mechanism is for flowspec validation, where validity of flowspec
+ * routes depends of resolving their network prefixes in IP routing tables. This
+ * is similar to the recursive next hop mechanism, but simpler as there are no
+ * intermediate hostcache and hostentries (because flows are less likely to
+ * share common net prefix than routes sharing a common next hop). In src table,
+ * there is a list of dst tables (list flowspec_links), this list is updated by
+ * flowpsec channels (by rt_flowspec_link() and rt_flowspec_unlink() during
+ * channel start/stop). Each dst table has its own trie of prefixes that may
+ * influence validation of flowspec routes in it (flowspec_trie).
+ *
+ * When a best route changes in the src table, rt_flowspec_notify() immediately
+ * checks all dst tables from the list using their tries to see whether the
+ * change is relevant for them. If it is, then an asynchronous re-validation of
+ * flowspec routes in the dst table is scheduled. That is also done by function
+ * rt_next_hop_update(), like nexthop recomputation above. It iterates over all
+ * flowspec routes and re-validates them. It also recalculates the trie.
+ *
+ * Note that in contrast to the hostcache update, here the trie is recalculated
+ * during the rt_next_hop_update(), which may be interleaved with IP route
+ * updates. The trie is flushed at the beginning of recalculation, which means
+ * that such updates may use partial trie to see if they are relevant. But it
+ * works anyway! Either affected flowspec was already re-validated and added to
+ * the trie, then IP route change would match the trie and trigger a next round
+ * of re-validation, or it was not yet re-validated and added to the trie, but
+ * will be re-validated later in this round anyway.
+ *
+ * The third mechanism is used for RPKI re-validation of IP routes and it is the
+ * simplest. It is just a list of subscribers in src table, who are notified
+ * when any change happened, but only after a settle time. Also, in RPKI case
+ * the dst is not a table, but a channel, who refeeds routes through a filter.
*/
#undef LOCAL_DEBUG
@@ -44,6 +104,11 @@
#include "lib/hash.h"
#include "lib/string.h"
#include "lib/alloca.h"
+#include "lib/flowspec.h"
+
+#ifdef CONFIG_BGP
+#include "proto/bgp/bgp.h"
+#endif
pool *rt_table_pool;
@@ -57,41 +122,184 @@ static void rt_update_hostcache(rtable *tab);
static void rt_next_hop_update(rtable *tab);
static inline void rt_prune_table(rtable *tab);
static inline void rt_schedule_notify(rtable *tab);
+static void rt_flowspec_notify(rtable *tab, net *net);
+
+
+static void
+net_init_with_trie(struct fib *f, void *N)
+{
+ rtable *tab = SKIP_BACK(rtable, fib, f);
+ net *n = N;
+ if (tab->trie)
+ trie_add_prefix(tab->trie, n->n.addr, n->n.addr->pxlen, n->n.addr->pxlen);
+
+ if (tab->trie_new)
+ trie_add_prefix(tab->trie_new, n->n.addr, n->n.addr->pxlen, n->n.addr->pxlen);
+}
+
+static inline net *
+net_route_ip4_trie(rtable *t, const net_addr_ip4 *n0)
+{
+ TRIE_WALK_TO_ROOT_IP4(t->trie, n0, n)
+ {
+ net *r;
+ if (r = net_find_valid(t, (net_addr *) &n))
+ return r;
+ }
+ TRIE_WALK_TO_ROOT_END;
+
+ return NULL;
+}
+
+static inline net *
+net_route_vpn4_trie(rtable *t, const net_addr_vpn4 *n0)
+{
+ TRIE_WALK_TO_ROOT_IP4(t->trie, (const net_addr_ip4 *) n0, px)
+ {
+ net_addr_vpn4 n = NET_ADDR_VPN4(px.prefix, px.pxlen, n0->rd);
+
+ net *r;
+ if (r = net_find_valid(t, (net_addr *) &n))
+ return r;
+ }
+ TRIE_WALK_TO_ROOT_END;
+
+ return NULL;
+}
+
+static inline net *
+net_route_ip6_trie(rtable *t, const net_addr_ip6 *n0)
+{
+ TRIE_WALK_TO_ROOT_IP6(t->trie, n0, n)
+ {
+ net *r;
+ if (r = net_find_valid(t, (net_addr *) &n))
+ return r;
+ }
+ TRIE_WALK_TO_ROOT_END;
+
+ return NULL;
+}
+
+static inline net *
+net_route_vpn6_trie(rtable *t, const net_addr_vpn6 *n0)
+{
+ TRIE_WALK_TO_ROOT_IP6(t->trie, (const net_addr_ip6 *) n0, px)
+ {
+ net_addr_vpn6 n = NET_ADDR_VPN6(px.prefix, px.pxlen, n0->rd);
+
+ net *r;
+ if (r = net_find_valid(t, (net_addr *) &n))
+ return r;
+ }
+ TRIE_WALK_TO_ROOT_END;
+
+ return NULL;
+}
-/* Like fib_route(), but skips empty net entries */
static inline void *
-net_route_ip4(rtable *t, net_addr_ip4 *n)
+net_route_ip6_sadr_trie(rtable *t, const net_addr_ip6_sadr *n0)
{
+ TRIE_WALK_TO_ROOT_IP6(t->trie, (const net_addr_ip6 *) n0, px)
+ {
+ net_addr_ip6_sadr n = NET_ADDR_IP6_SADR(px.prefix, px.pxlen, n0->src_prefix, n0->src_pxlen);
+ net *best = NULL;
+ int best_pxlen = 0;
+
+ /* We need to do dst first matching. Since sadr addresses are hashed on dst
+ prefix only, find the hash table chain and go through it to find the
+ match with the longest matching src prefix. */
+ for (struct fib_node *fn = fib_get_chain(&t->fib, (net_addr *) &n); fn; fn = fn->next)
+ {
+ net_addr_ip6_sadr *a = (void *) fn->addr;
+
+ if (net_equal_dst_ip6_sadr(&n, a) &&
+ net_in_net_src_ip6_sadr(&n, a) &&
+ (a->src_pxlen >= best_pxlen))
+ {
+ best = fib_node_to_user(&t->fib, fn);
+ best_pxlen = a->src_pxlen;
+ }
+ }
+
+ if (best)
+ return best;
+ }
+ TRIE_WALK_TO_ROOT_END;
+
+ return NULL;
+}
+
+static inline net *
+net_route_ip4_fib(rtable *t, const net_addr_ip4 *n0)
+{
+ net_addr_ip4 n;
+ net_copy_ip4(&n, n0);
+
net *r;
+ while (r = net_find_valid(t, (net_addr *) &n), (!r) && (n.pxlen > 0))
+ {
+ n.pxlen--;
+ ip4_clrbit(&n.prefix, n.pxlen);
+ }
+
+ return r;
+}
+
+static inline net *
+net_route_vpn4_fib(rtable *t, const net_addr_vpn4 *n0)
+{
+ net_addr_vpn4 n;
+ net_copy_vpn4(&n, n0);
- while (r = net_find_valid(t, (net_addr *) n), (!r) && (n->pxlen > 0))
+ net *r;
+ while (r = net_find_valid(t, (net_addr *) &n), (!r) && (n.pxlen > 0))
{
- n->pxlen--;
- ip4_clrbit(&n->prefix, n->pxlen);
+ n.pxlen--;
+ ip4_clrbit(&n.prefix, n.pxlen);
}
return r;
}
-static inline void *
-net_route_ip6(rtable *t, net_addr_ip6 *n)
+static inline net *
+net_route_ip6_fib(rtable *t, const net_addr_ip6 *n0)
{
+ net_addr_ip6 n;
+ net_copy_ip6(&n, n0);
+
net *r;
+ while (r = net_find_valid(t, (net_addr *) &n), (!r) && (n.pxlen > 0))
+ {
+ n.pxlen--;
+ ip6_clrbit(&n.prefix, n.pxlen);
+ }
+
+ return r;
+}
- while (r = net_find_valid(t, (net_addr *) n), (!r) && (n->pxlen > 0))
+static inline net *
+net_route_vpn6_fib(rtable *t, const net_addr_vpn6 *n0)
+{
+ net_addr_vpn6 n;
+ net_copy_vpn6(&n, n0);
+
+ net *r;
+ while (r = net_find_valid(t, (net_addr *) &n), (!r) && (n.pxlen > 0))
{
- n->pxlen--;
- ip6_clrbit(&n->prefix, n->pxlen);
+ n.pxlen--;
+ ip6_clrbit(&n.prefix, n.pxlen);
}
return r;
}
static inline void *
-net_route_ip6_sadr(rtable *t, net_addr_ip6_sadr *n)
+net_route_ip6_sadr_fib(rtable *t, const net_addr_ip6_sadr *n0)
{
- struct fib_node *fn;
+ net_addr_ip6_sadr n;
+ net_copy_ip6_sadr(&n, n0);
while (1)
{
@@ -100,13 +308,13 @@ net_route_ip6_sadr(rtable *t, net_addr_ip6_sadr *n)
/* We need to do dst first matching. Since sadr addresses are hashed on dst
prefix only, find the hash table chain and go through it to find the
- match with the smallest matching src prefix. */
- for (fn = fib_get_chain(&t->fib, (net_addr *) n); fn; fn = fn->next)
+ match with the longest matching src prefix. */
+ for (struct fib_node *fn = fib_get_chain(&t->fib, (net_addr *) &n); fn; fn = fn->next)
{
net_addr_ip6_sadr *a = (void *) fn->addr;
- if (net_equal_dst_ip6_sadr(n, a) &&
- net_in_net_src_ip6_sadr(n, a) &&
+ if (net_equal_dst_ip6_sadr(&n, a) &&
+ net_in_net_src_ip6_sadr(&n, a) &&
(a->src_pxlen >= best_pxlen))
{
best = fib_node_to_user(&t->fib, fn);
@@ -117,38 +325,52 @@ net_route_ip6_sadr(rtable *t, net_addr_ip6_sadr *n)
if (best)
return best;
- if (!n->dst_pxlen)
+ if (!n.dst_pxlen)
break;
- n->dst_pxlen--;
- ip6_clrbit(&n->dst_prefix, n->dst_pxlen);
+ n.dst_pxlen--;
+ ip6_clrbit(&n.dst_prefix, n.dst_pxlen);
}
return NULL;
}
-void *
+net *
net_route(rtable *tab, const net_addr *n)
{
ASSERT(tab->addr_type == n->type);
- net_addr *n0 = alloca(n->length);
- net_copy(n0, n);
-
switch (n->type)
{
case NET_IP4:
+ if (tab->trie)
+ return net_route_ip4_trie(tab, (net_addr_ip4 *) n);
+ else
+ return net_route_ip4_fib (tab, (net_addr_ip4 *) n);
+
case NET_VPN4:
- case NET_ROA4:
- return net_route_ip4(tab, (net_addr_ip4 *) n0);
+ if (tab->trie)
+ return net_route_vpn4_trie(tab, (net_addr_vpn4 *) n);
+ else
+ return net_route_vpn4_fib (tab, (net_addr_vpn4 *) n);
case NET_IP6:
+ if (tab->trie)
+ return net_route_ip6_trie(tab, (net_addr_ip6 *) n);
+ else
+ return net_route_ip6_fib (tab, (net_addr_ip6 *) n);
+
case NET_VPN6:
- case NET_ROA6:
- return net_route_ip6(tab, (net_addr_ip6 *) n0);
+ if (tab->trie)
+ return net_route_vpn6_trie(tab, (net_addr_vpn6 *) n);
+ else
+ return net_route_vpn6_fib (tab, (net_addr_vpn6 *) n);
case NET_IP6_SADR:
- return net_route_ip6_sadr(tab, (net_addr_ip6_sadr *) n0);
+ if (tab->trie)
+ return net_route_ip6_sadr_trie(tab, (net_addr_ip6_sadr *) n);
+ else
+ return net_route_ip6_sadr_fib (tab, (net_addr_ip6_sadr *) n);
default:
return NULL;
@@ -157,7 +379,35 @@ net_route(rtable *tab, const net_addr *n)
static int
-net_roa_check_ip4(rtable *tab, const net_addr_ip4 *px, u32 asn)
+net_roa_check_ip4_trie(rtable *tab, const net_addr_ip4 *px, u32 asn)
+{
+ int anything = 0;
+
+ TRIE_WALK_TO_ROOT_IP4(tab->trie, px, px0)
+ {
+ net_addr_roa4 roa0 = NET_ADDR_ROA4(px0.prefix, px0.pxlen, 0, 0);
+
+ struct fib_node *fn;
+ for (fn = fib_get_chain(&tab->fib, (net_addr *) &roa0); fn; fn = fn->next)
+ {
+ net_addr_roa4 *roa = (void *) fn->addr;
+ net *r = fib_node_to_user(&tab->fib, fn);
+
+ if (net_equal_prefix_roa4(roa, &roa0) && rte_is_valid(r->routes))
+ {
+ anything = 1;
+ if (asn && (roa->asn == asn) && (roa->max_pxlen >= px->pxlen))
+ return ROA_VALID;
+ }
+ }
+ }
+ TRIE_WALK_TO_ROOT_END;
+
+ return anything ? ROA_INVALID : ROA_UNKNOWN;
+}
+
+static int
+net_roa_check_ip4_fib(rtable *tab, const net_addr_ip4 *px, u32 asn)
{
struct net_addr_roa4 n = NET_ADDR_ROA4(px->prefix, px->pxlen, 0, 0);
struct fib_node *fn;
@@ -170,7 +420,7 @@ net_roa_check_ip4(rtable *tab, const net_addr_ip4 *px, u32 asn)
net_addr_roa4 *roa = (void *) fn->addr;
net *r = fib_node_to_user(&tab->fib, fn);
- if (net_equal_prefix_roa4(roa, &n) && r->routes && rte_is_valid(&r->routes->rte))
+ if (net_equal_prefix_roa4(roa, &n) && rte_is_valid(r->routes))
{
anything = 1;
if (asn && (roa->asn == asn) && (roa->max_pxlen >= px->pxlen))
@@ -189,7 +439,35 @@ net_roa_check_ip4(rtable *tab, const net_addr_ip4 *px, u32 asn)
}
static int
-net_roa_check_ip6(rtable *tab, const net_addr_ip6 *px, u32 asn)
+net_roa_check_ip6_trie(rtable *tab, const net_addr_ip6 *px, u32 asn)
+{
+ int anything = 0;
+
+ TRIE_WALK_TO_ROOT_IP6(tab->trie, px, px0)
+ {
+ net_addr_roa6 roa0 = NET_ADDR_ROA6(px0.prefix, px0.pxlen, 0, 0);
+
+ struct fib_node *fn;
+ for (fn = fib_get_chain(&tab->fib, (net_addr *) &roa0); fn; fn = fn->next)
+ {
+ net_addr_roa6 *roa = (void *) fn->addr;
+ net *r = fib_node_to_user(&tab->fib, fn);
+
+ if (net_equal_prefix_roa6(roa, &roa0) && rte_is_valid(r->routes))
+ {
+ anything = 1;
+ if (asn && (roa->asn == asn) && (roa->max_pxlen >= px->pxlen))
+ return ROA_VALID;
+ }
+ }
+ }
+ TRIE_WALK_TO_ROOT_END;
+
+ return anything ? ROA_INVALID : ROA_UNKNOWN;
+}
+
+static int
+net_roa_check_ip6_fib(rtable *tab, const net_addr_ip6 *px, u32 asn)
{
struct net_addr_roa6 n = NET_ADDR_ROA6(px->prefix, px->pxlen, 0, 0);
struct fib_node *fn;
@@ -202,7 +480,7 @@ net_roa_check_ip6(rtable *tab, const net_addr_ip6 *px, u32 asn)
net_addr_roa6 *roa = (void *) fn->addr;
net *r = fib_node_to_user(&tab->fib, fn);
- if (net_equal_prefix_roa6(roa, &n) && r->routes && rte_is_valid(&r->routes->rte))
+ if (net_equal_prefix_roa6(roa, &n) && rte_is_valid(r->routes))
{
anything = 1;
if (asn && (roa->asn == asn) && (roa->max_pxlen >= px->pxlen))
@@ -239,9 +517,19 @@ int
net_roa_check(rtable *tab, const net_addr *n, u32 asn)
{
if ((tab->addr_type == NET_ROA4) && (n->type == NET_IP4))
- return net_roa_check_ip4(tab, (const net_addr_ip4 *) n, asn);
+ {
+ if (tab->trie)
+ return net_roa_check_ip4_trie(tab, (const net_addr_ip4 *) n, asn);
+ else
+ return net_roa_check_ip4_fib (tab, (const net_addr_ip4 *) n, asn);
+ }
else if ((tab->addr_type == NET_ROA6) && (n->type == NET_IP6))
- return net_roa_check_ip6(tab, (const net_addr_ip6 *) n, asn);
+ {
+ if (tab->trie)
+ return net_roa_check_ip6_trie(tab, (const net_addr_ip6 *) n, asn);
+ else
+ return net_roa_check_ip6_fib (tab, (const net_addr_ip6 *) n, asn);
+ }
else
return ROA_UNKNOWN; /* Should not happen */
}
@@ -546,7 +834,7 @@ rt_notify_accepted(struct channel *c, net *net, rte *new_changed, rte *old_chang
old_best = old_changed;
else
{
- for (struct rte_storage *r = net->routes; r && rte_is_valid(&r->rte); r = r->next)
+ for (struct rte_storage *r = net->routes; rte_is_valid(r); r = r->next)
{
if (bmap_test(&c->export_map, r->rte.id))
{
@@ -564,7 +852,7 @@ rt_notify_accepted(struct channel *c, net *net, rte *new_changed, rte *old_chang
if ((new_changed == old_changed) || (old_best == old_changed))
{
/* Feed or old_best changed -> find first accepted by filters */
- for (struct rte_storage *r = net->routes; r && rte_is_valid(&r->rte); r = r->next)
+ for (struct rte_storage *r = net->routes; rte_is_valid(r); r = r->next)
if (new_best = export_filter(c, ((nb0 = r->rte), &nb0), 0))
break;
}
@@ -599,7 +887,7 @@ rt_export_merged(struct channel *c, net *net, linpool *pool, int silent)
struct rte_storage *best0 = net->routes;
rte *best;
- if (!best0 || !rte_is_valid(&best0->rte))
+ if (!rte_is_valid(best0))
return NULL;
best = export_filter_(c, ((rme = best0->rte), &rme), pool, silent);
@@ -717,16 +1005,16 @@ static void
rte_announce(rtable *tab, uint type, net *net, struct rte_storage *new, struct rte_storage *old,
struct rte_storage *new_best, struct rte_storage *old_best)
{
- if (!new || !rte_is_valid(&new->rte))
+ if (!rte_is_valid(new))
new = NULL;
- if (!old || !rte_is_valid(&old->rte))
+ if (!rte_is_valid(old))
old = NULL;
- if (!new_best || !rte_is_valid(&new_best->rte))
+ if (!rte_is_valid(new_best))
new_best = NULL;
- if (!old_best || !rte_is_valid(&old_best->rte))
+ if (!rte_is_valid(old_best))
old_best = NULL;
if (!new && !old && !new_best && !old_best)
@@ -741,6 +1029,9 @@ rte_announce(rtable *tab, uint type, net *net, struct rte_storage *new, struct r
if (tab->hostcache)
rt_notify_hostcache(tab, net);
+
+ if (!EMPTY_LIST(tab->flowspec_links))
+ rt_flowspec_notify(tab, net);
}
rt_schedule_notify(tab);
@@ -803,6 +1094,10 @@ rte_validate(rte *e)
if (net_type_match(n, NB_DEST) == !e->attrs->dest)
{
+ /* Exception for flowspec that failed validation */
+ if (net_is_flow(n) && (e->attrs->dest == RTD_UNREACHABLE))
+ return 1;
+
log(L_WARN "Ignoring route %N with invalid dest %d received via %s",
n, e->attrs->dest, e->sender->proto->name);
return 0;
@@ -1248,14 +1543,11 @@ rt_examine(rtable *t, net_addr *a, struct channel *c, const struct filter *filte
{
net *n = net_find(t, a);
- if (!n || !n->routes)
+ if (!n || !rte_is_valid(n->routes))
return 0;
rte rt = n->routes->rte;
- if (!rte_is_valid(&rt))
- return 0;
-
rte_update_lock();
/* Rest is stripped down export_filter() */
@@ -1520,6 +1812,90 @@ rt_unsubscribe(struct rt_subscription *s)
rt_unlock_table(s->tab);
}
+static struct rt_flowspec_link *
+rt_flowspec_find_link(rtable *src, rtable *dst)
+{
+ struct rt_flowspec_link *ln;
+ WALK_LIST(ln, src->flowspec_links)
+ if ((ln->src == src) && (ln->dst == dst))
+ return ln;
+
+ return NULL;
+}
+
+void
+rt_flowspec_link(rtable *src, rtable *dst)
+{
+ ASSERT(rt_is_ip(src));
+ ASSERT(rt_is_flow(dst));
+
+ struct rt_flowspec_link *ln = rt_flowspec_find_link(src, dst);
+
+ if (!ln)
+ {
+ rt_lock_table(src);
+ rt_lock_table(dst);
+
+ ln = mb_allocz(src->rp, sizeof(struct rt_flowspec_link));
+ ln->src = src;
+ ln->dst = dst;
+ add_tail(&src->flowspec_links, &ln->n);
+ }
+
+ ln->uc++;
+}
+
+void
+rt_flowspec_unlink(rtable *src, rtable *dst)
+{
+ struct rt_flowspec_link *ln = rt_flowspec_find_link(src, dst);
+
+ ASSERT(ln && (ln->uc > 0));
+
+ ln->uc--;
+
+ if (!ln->uc)
+ {
+ rem_node(&ln->n);
+ mb_free(ln);
+
+ rt_unlock_table(src);
+ rt_unlock_table(dst);
+ }
+}
+
+static void
+rt_flowspec_notify(rtable *src, net *net)
+{
+ /* Only IP tables are src links */
+ ASSERT(rt_is_ip(src));
+
+ struct rt_flowspec_link *ln;
+ WALK_LIST(ln, src->flowspec_links)
+ {
+ rtable *dst = ln->dst;
+ ASSERT(rt_is_flow(dst));
+
+ /* No need to inspect it further if recalculation is already active */
+ if ((dst->nhu_state == NHU_SCHEDULED) || (dst->nhu_state == NHU_DIRTY))
+ continue;
+
+ if (trie_match_net(dst->flowspec_trie, net->n.addr))
+ rt_schedule_nhu(dst);
+ }
+}
+
+static void
+rt_flowspec_reset_trie(rtable *tab)
+{
+ linpool *lp = tab->flowspec_trie->lp;
+ int ipv4 = tab->flowspec_trie->ipv4;
+
+ lp_flush(lp);
+ tab->flowspec_trie = f_new_trie(lp, 0);
+ tab->flowspec_trie->ipv4 = ipv4;
+}
+
static void
rt_free(resource *_r)
{
@@ -1584,18 +1960,33 @@ rt_setup(pool *pp, struct rtable_config *cf)
fib_init(&t->fib, p, t->addr_type, sizeof(net), OFFSETOF(net, n), 0, NULL);
+ if (cf->trie_used)
+ {
+ t->trie = f_new_trie(lp_new_default(p), 0);
+ t->trie->ipv4 = net_val_match(t->addr_type, NB_IP4 | NB_VPN4 | NB_ROA4);
+
+ t->fib.init = net_init_with_trie;
+ }
+
+ init_list(&t->channels);
+ init_list(&t->flowspec_links);
+ init_list(&t->subscribers);
+
if (!(t->internal = cf->internal))
{
- init_list(&t->channels);
hmap_init(&t->id_map, p, 1024);
hmap_set(&t->id_map, 0);
- init_list(&t->subscribers);
-
t->rt_event = ev_new_init(p, rt_event, t);
t->last_rt_change = t->gc_time = current_time();
t->rl_pipe = (struct tbf) TBF_DEFAULT_LOG_LIMITS;
+
+ if (rt_is_flow(t))
+ {
+ t->flowspec_trie = f_new_trie(lp_new_default(p), 0);
+ t->flowspec_trie->ipv4 = (t->addr_type == NET_FLOW4);
+ }
}
return t;
@@ -1657,23 +2048,30 @@ rt_prune_table(rtable *tab)
FIB_ITERATE_INIT(fit, &tab->fib);
tab->prune_state = 2;
+
+ if (tab->prune_trie)
+ {
+ /* Init prefix trie pruning */
+ tab->trie_new = f_new_trie(lp_new_default(tab->rp), 0);
+ tab->trie_new->ipv4 = tab->trie->ipv4;
+ }
}
again:
FIB_ITERATE_START(&tab->fib, fit, net, n)
{
rescan:
+ if (limit <= 0)
+ {
+ FIB_ITERATE_PUT(fit);
+ ev_schedule(tab->rt_event);
+ return;
+ }
+
for (struct rte_storage *e=n->routes; e; e=e->next)
{
if (e->rte.sender->flush_active || (e->rte.flags & REF_DISCARD))
{
- if (limit <= 0)
- {
- FIB_ITERATE_PUT(fit);
- ev_schedule(tab->rt_event);
- return;
- }
-
rte_discard(n, &e->rte);
limit--;
@@ -1682,13 +2080,6 @@ again:
if (e->rte.flags & REF_MODIFY)
{
- if (limit <= 0)
- {
- FIB_ITERATE_PUT(fit);
- ev_schedule(tab->rt_event);
- return;
- }
-
rte_modify(n, &e->rte);
limit--;
@@ -1702,6 +2093,12 @@ again:
fib_delete(&tab->fib, n);
goto again;
}
+
+ if (tab->trie_new)
+ {
+ trie_add_prefix(tab->trie_new, n->n.addr, n->n.addr->pxlen, n->n.addr->pxlen);
+ limit--;
+ }
}
FIB_ITERATE_END;
@@ -1715,6 +2112,37 @@ again:
/* state change 2->0, 3->1 */
tab->prune_state &= 1;
+ if (tab->trie_new)
+ {
+ /* Finish prefix trie pruning */
+
+ if (!tab->trie_lock_count)
+ {
+ rfree(tab->trie->lp);
+ }
+ else
+ {
+ ASSERT(!tab->trie_old);
+ tab->trie_old = tab->trie;
+ tab->trie_old_lock_count = tab->trie_lock_count;
+ tab->trie_lock_count = 0;
+ }
+
+ tab->trie = tab->trie_new;
+ tab->trie_new = NULL;
+ tab->prune_trie = 0;
+ }
+ else
+ {
+ /* Schedule prefix trie pruning */
+ if (tab->trie && !tab->trie_old && (tab->trie->prefix_count > (2 * tab->fib.entries)))
+ {
+ /* state change 0->1, 2->3 */
+ tab->prune_state |= 1;
+ tab->prune_trie = 1;
+ }
+ }
+
if (tab->prune_state > 0)
ev_schedule(tab->rt_event);
@@ -1732,6 +2160,72 @@ again:
return;
}
+/**
+ * rt_lock_trie - lock a prefix trie of a routing table
+ * @tab: routing table with prefix trie to be locked
+ *
+ * The prune loop may rebuild the prefix trie and invalidate f_trie_walk_state
+ * structures. Therefore, asynchronous walks should lock the prefix trie using
+ * this function. That allows the prune loop to rebuild the trie, but postpones
+ * its freeing until all walks are done (unlocked by rt_unlock_trie()).
+ *
+ * Return a current trie that will be locked, the value should be passed back to
+ * rt_unlock_trie() for unlocking.
+ *
+ */
+struct f_trie *
+rt_lock_trie(rtable *tab)
+{
+ ASSERT(tab->trie);
+
+ tab->trie_lock_count++;
+ return tab->trie;
+}
+
+/**
+ * rt_unlock_trie - unlock a prefix trie of a routing table
+ * @tab: routing table with prefix trie to be locked
+ * @trie: value returned by matching rt_lock_trie()
+ *
+ * Done for trie locked by rt_lock_trie() after walk over the trie is done.
+ * It may free the trie and schedule next trie pruning.
+ */
+void
+rt_unlock_trie(rtable *tab, struct f_trie *trie)
+{
+ ASSERT(trie);
+
+ if (trie == tab->trie)
+ {
+ /* Unlock the current prefix trie */
+ ASSERT(tab->trie_lock_count);
+ tab->trie_lock_count--;
+ }
+ else if (trie == tab->trie_old)
+ {
+ /* Unlock the old prefix trie */
+ ASSERT(tab->trie_old_lock_count);
+ tab->trie_old_lock_count--;
+
+ /* Free old prefix trie that is no longer needed */
+ if (!tab->trie_old_lock_count)
+ {
+ rfree(tab->trie_old->lp);
+ tab->trie_old = NULL;
+
+ /* Kick prefix trie pruning that was postponed */
+ if (tab->trie && (tab->trie->prefix_count > (2 * tab->fib.entries)))
+ {
+ tab->prune_trie = 1;
+ rt_schedule_prune(tab);
+ }
+ }
+ }
+ else
+ log(L_BUG "Invalid arg to rt_unlock_trie()");
+}
+
+
void
rt_preconfig(struct config *c)
{
@@ -1747,21 +2241,6 @@ rt_preconfig(struct config *c)
* triggered by rt_schedule_nhu().
*/
-static inline int
-rta_next_hop_outdated(rta *a)
-{
- struct hostentry *he = a->hostentry;
-
- if (!he)
- return 0;
-
- if (!he->src)
- return a->dest != RTD_UNREACHABLE;
-
- return (a->dest != he->dest) || (a->igp_metric != he->igp_metric) ||
- (!he->nexthop_linkable) || !nexthop_same(&(a->nh), &(he->src->nh));
-}
-
void
rta_apply_hostentry(rta *a, struct hostentry *he, mpls_label_stack *mls)
{
@@ -1853,9 +2332,27 @@ no_nexthop:
}
}
+static inline int
+rta_next_hop_outdated(rta *a)
+{
+ struct hostentry *he = a->hostentry;
+
+ if (!he)
+ return 0;
+
+ if (!he->src)
+ return a->dest != RTD_UNREACHABLE;
+
+ return (a->dest != he->dest) || (a->igp_metric != he->igp_metric) ||
+ (!he->nexthop_linkable) || !nexthop_same(&(a->nh), &(he->src->nh));
+}
+
static inline struct rte_storage *
rt_next_hop_update_rte(rtable *tab, net *n, rte *old)
{
+ if (!rta_next_hop_outdated(old->attrs))
+ return NULL;
+
rta *a = alloca(RTA_MAX_SIZE);
memcpy(a, old->attrs, rta_size(old->attrs));
@@ -1871,18 +2368,168 @@ rt_next_hop_update_rte(rtable *tab, net *n, rte *old)
return rte_store(&e0, n, tab);
}
+
+#ifdef CONFIG_BGP
+
+static inline int
+net_flow_has_dst_prefix(const net_addr *n)
+{
+ ASSUME(net_is_flow(n));
+
+ if (n->pxlen)
+ return 1;
+
+ if (n->type == NET_FLOW4)
+ {
+ const net_addr_flow4 *n4 = (void *) n;
+ return (n4->length > sizeof(net_addr_flow4)) && (n4->data[0] == FLOW_TYPE_DST_PREFIX);
+ }
+ else
+ {
+ const net_addr_flow6 *n6 = (void *) n;
+ return (n6->length > sizeof(net_addr_flow6)) && (n6->data[0] == FLOW_TYPE_DST_PREFIX);
+ }
+}
+
+static inline int
+rta_as_path_is_empty(rta *a)
+{
+ eattr *e = ea_find(a->eattrs, EA_CODE(PROTOCOL_BGP, BA_AS_PATH));
+ return !e || (as_path_getlen(e->u.ptr) == 0);
+}
+
+static inline u32
+rta_get_first_asn(rta *a)
+{
+ eattr *e = ea_find(a->eattrs, EA_CODE(PROTOCOL_BGP, BA_AS_PATH));
+ u32 asn;
+
+ return (e && as_path_get_first_regular(e->u.ptr, &asn)) ? asn : 0;
+}
+
+int
+rt_flowspec_check(rtable *tab_ip, rtable *tab_flow, const net_addr *n, rta *a, int interior)
+{
+ ASSERT(rt_is_ip(tab_ip));
+ ASSERT(rt_is_flow(tab_flow));
+ ASSERT(tab_ip->trie);
+
+ /* RFC 8955 6. a) Flowspec has defined dst prefix */
+ if (!net_flow_has_dst_prefix(n))
+ return 0;
+
+ /* RFC 9117 4.1. Accept AS_PATH is empty (fr */
+ if (interior && rta_as_path_is_empty(a))
+ return 1;
+
+
+ /* RFC 8955 6. b) Flowspec and its best-match route have the same originator */
+
+ /* Find flowspec dst prefix */
+ net_addr dst;
+ if (n->type == NET_FLOW4)
+ net_fill_ip4(&dst, net4_prefix(n), net4_pxlen(n));
+ else
+ net_fill_ip6(&dst, net6_prefix(n), net6_pxlen(n));
+
+ /* Find best-match BGP unicast route for flowspec dst prefix */
+ net *nb = net_route(tab_ip, &dst);
+ const rte *rb = nb ? &nb->routes->rte : NULL;
+
+ /* Register prefix to trie for tracking further changes */
+ int max_pxlen = (n->type == NET_FLOW4) ? IP4_MAX_PREFIX_LENGTH : IP6_MAX_PREFIX_LENGTH;
+ trie_add_prefix(tab_flow->flowspec_trie, &dst, (nb ? nb->n.addr->pxlen : 0), max_pxlen);
+
+ /* No best-match BGP route -> no flowspec */
+ if (!rb || (rb->attrs->source != RTS_BGP))
+ return 0;
+
+ /* Find ORIGINATOR_ID values */
+ u32 orig_a = ea_get_int(a->eattrs, EA_CODE(PROTOCOL_BGP, BA_ORIGINATOR_ID), 0);
+ u32 orig_b = ea_get_int(rb->attrs->eattrs, EA_CODE(PROTOCOL_BGP, BA_ORIGINATOR_ID), 0);
+
+ /* Originator is either ORIGINATOR_ID (if present), or BGP neighbor address (if not) */
+ if ((orig_a != orig_b) || (!orig_a && !orig_b && !ipa_equal(a->from, rb->attrs->from)))
+ return 0;
+
+
+ /* Find ASN of the best-match route, for use in next checks */
+ u32 asn_b = rta_get_first_asn(rb->attrs);
+ if (!asn_b)
+ return 0;
+
+ /* RFC 9117 4.2. For EBGP, flowspec and its best-match route are from the same AS */
+ if (!interior && (rta_get_first_asn(a) != asn_b))
+ return 0;
+
+ /* RFC 8955 6. c) More-specific routes are from the same AS as the best-match route */
+ TRIE_WALK(tab_ip->trie, subnet, &dst)
+ {
+ net *nc = net_find_valid(tab_ip, &subnet);
+ if (!nc)
+ continue;
+
+ const rte *rc = &nc->routes->rte;
+ if (rc->attrs->source != RTS_BGP)
+ return 0;
+
+ if (rta_get_first_asn(rc->attrs) != asn_b)
+ return 0;
+ }
+ TRIE_WALK_END;
+
+ return 1;
+}
+
+#endif /* CONFIG_BGP */
+
+static struct rte_storage *
+rt_flowspec_update_rte(rtable *tab, net *n, rte *r)
+{
+#ifdef CONFIG_BGP
+ if (r->attrs->source != RTS_BGP)
+ return NULL;
+
+ struct bgp_channel *bc = (struct bgp_channel *) r->sender;
+ if (!bc->base_table)
+ return NULL;
+
+ struct bgp_proto *p = (void *) r->src->proto;
+ int valid = rt_flowspec_check(bc->base_table, tab, n->n.addr, r->attrs, p->is_interior);
+ int dest = valid ? RTD_NONE : RTD_UNREACHABLE;
+
+ if (dest == r->attrs->dest)
+ return NULL;
+
+ rta *a = alloca(RTA_MAX_SIZE);
+ memcpy(a, r->attrs, rta_size(r->attrs));
+ a->dest = dest;
+ a->cached = 0;
+
+ rte new;
+ memcpy(&new, r, sizeof(rte));
+ new.attrs = a;
+
+ return rte_store(&new, n, tab);
+#else
+ return NULL;
+#endif
+}
+
+
static inline int
rt_next_hop_update_net(rtable *tab, net *n)
{
struct rte_storage *new;
int count = 0;
+ int is_flow = net_is_flow(n->n.addr);
struct rte_storage *old_best = n->routes;
if (!old_best)
return 0;
for (struct rte_storage *e, **k = &n->routes; e = *k; k = &e->next)
- if (rta_next_hop_outdated(e->rte.attrs))
+ if (is_flow || rta_next_hop_outdated(e->rte.attrs))
count++;
if (!count)
@@ -1894,9 +2541,11 @@ rt_next_hop_update_net(rtable *tab, net *n)
int pos = 0;
for (struct rte_storage *e, **k = &n->routes; e = *k; k = &e->next)
- if (rta_next_hop_outdated(e->rte.attrs))
+ if (is_flow || rta_next_hop_outdated(e->rte.attrs))
{
- struct rte_storage *new = rt_next_hop_update_rte(tab, n, &e->rte);
+ struct rte_storage *new = is_flow
+ ? rt_flowspec_update_rte(tab, n, &e->rte)
+ : rt_next_hop_update_rte(tab, n, &e->rte);
/* Call a pre-comparison hook */
/* Not really an efficient way to compute this */
@@ -1960,6 +2609,9 @@ rt_next_hop_update(rtable *tab)
{
FIB_ITERATE_INIT(fit, &tab->fib);
tab->nhu_state = NHU_RUNNING;
+
+ if (tab->flowspec_trie)
+ rt_flowspec_reset_trie(tab);
}
FIB_ITERATE_START(&tab->fib, fit, net, n)
@@ -2048,6 +2700,22 @@ rt_unlock_table(rtable *r)
}
}
+static int
+rt_reconfigure(rtable *tab, struct rtable_config *new, struct rtable_config *old)
+{
+ if ((new->addr_type != old->addr_type) ||
+ (new->sorted != old->sorted) ||
+ (new->trie_used != old->trie_used))
+ return 0;
+
+ DBG("\t%s: same\n", new->name);
+ new->table = tab;
+ tab->name = new->name;
+ tab->config = new;
+
+ return 1;
+}
+
static struct rtable_config *
rt_find_table_config(struct config *cf, char *name)
{
@@ -2077,28 +2745,19 @@ rt_commit(struct config *new, struct config *old)
{
WALK_LIST(o, old->tables)
{
- rtable *ot = o->table;
- if (!ot->deleted)
- {
- r = rt_find_table_config(new, o->name);
- if (r && (r->addr_type == o->addr_type) && !new->shutdown)
- {
- DBG("\t%s: same\n", o->name);
- r->table = ot;
- ot->name = r->name;
- ot->config = r;
- if (o->sorted != r->sorted)
- log(L_WARN "Reconfiguration of rtable sorted flag not implemented");
- }
- else
- {
- DBG("\t%s: deleted\n", o->name);
- ot->deleted = old;
- config_add_obstacle(old);
- rt_lock_table(ot);
- rt_unlock_table(ot);
- }
- }
+ rtable *tab = o->table;
+ if (tab->deleted)
+ continue;
+
+ r = rt_find_table_config(new, o->name);
+ if (r && !new->shutdown && rt_reconfigure(tab, r, o))
+ continue;
+
+ DBG("\t%s: deleted\n", o->name);
+ tab->deleted = old;
+ config_add_obstacle(old);
+ rt_lock_table(tab);
+ rt_unlock_table(tab);
}
}
@@ -2163,7 +2822,7 @@ rt_feed_channel(struct channel *c)
if ((c->ra_mode == RA_OPTIMAL) ||
(c->ra_mode == RA_ACCEPTED) ||
(c->ra_mode == RA_MERGED))
- if (e && rte_is_valid(&e->rte))
+ if (rte_is_valid(e))
{
/* In the meantime, the protocol may fell down */
if (c->export_state != ES_FEEDING)
@@ -2180,7 +2839,7 @@ rt_feed_channel(struct channel *c)
if (c->export_state != ES_FEEDING)
goto done;
- if (!rte_is_valid(&e->rte))
+ if (!rte_is_valid(e))
continue;
do_feed_channel(c, n, &e->rte);
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-15 22:47:57 +0000