[PATCH 2/9] Nest changes to support SADR.
Dean Luga
dluga93 at gmail.com
Tue Mar 7 00:56:26 CET 2017
From: dean <dluga93 at gmail.com>
When SADR is enabled, fib_node contains source address prefix
and prefix length.
A data structure addr_data was added to be passed to
fib_{get|find|route} and net_{get|find} functions and allow
the same call syntax for the functions, independently of
whether SADR is enabled. Two functions were also added that
return an addr_data object initialized to zero or with the
data from a fib_node object.
The fib_* and net_* functions where duplicated to sfib_* snet_*
(the 's' standing for sadr) and to fib_*2 net_*2.
The sfib_* and snet_* versions exist if SADR is enabled and take
both source and destination addresses as arguments. They do the
lookup/routing considering both the source and destination.
The fib_*2 and net_*2 versions call the correct fib_ or sfib_
function depending on whether SADR is enabled. They take an addr_data
argument instead of addresses, so that the syntax of the function
call is the same independently of whether SADR is enabled or not.
Unchanged protocols will call the same fib_ and net_ functions even
if SADR is enabled. In this case, the call is redirected to the
sfib_ version using 0::/0 as source address. This is to avoid source
specific routes being used by protocols that don't know about them.
A part of the rte_validate function was duplicated to check the
source prefix for correctness.
---
nest/route.h | 46 +++++++++++++++
nest/rt-fib.c | 172 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
nest/rt-table.c | 11 ++++
3 files changed, 229 insertions(+)
diff --git a/nest/route.h b/nest/route.h
index 2fcb189..d828ad8 100644
--- a/nest/route.h
+++ b/nest/route.h
@@ -40,8 +40,26 @@ struct fib_node {
byte x0, x1; /* User-defined */
u32 uid; /* Unique ID based on hash */
ip_addr prefix; /* In host order */
+ #ifdef SADR_OSPF
+ ip_addr src_prefix;
+ byte src_pxlen;
+ #endif
};
+typedef struct addr_data {
+ ip_addr* prefix;
+
+ #ifdef SADR_OSPF
+ ip_addr* src_prefix;
+ #endif
+
+ byte pxlen;
+
+ #ifdef SADR_OSPF
+ byte src_pxlen;
+ #endif
+} addr_data;
+
struct fib_iterator { /* See lib/slists.h for an explanation */
struct fib_iterator *prev, *next; /* Must be synced with struct fib_node! */
byte efef; /* 0xff to distinguish between iterator and node */
@@ -68,6 +86,25 @@ void fib_init(struct fib *, pool *, unsigned node_size, unsigned hash_order, fib
void *fib_find(struct fib *, ip_addr *, int); /* Find or return NULL if doesn't exist */
void *fib_get(struct fib *, ip_addr *, int); /* Find or create new if nonexistent */
void *fib_route(struct fib *, ip_addr, int); /* Longest-match routing lookup */
+
+// same as above but take addr_data argument, and can handle both SADR and non-SADR
+void *fib_find2(struct fib *, addr_data);
+void *fib_get2(struct fib *, addr_data);
+void *fib_route2(struct fib *, addr_data);
+
+static inline addr_data addr_data_init_empty(void) {
+ addr_data addr;
+ memset(&addr, 0, sizeof(addr));
+ return addr;
+}
+
+addr_data addr_data_fn_init(struct fib_node *fn);
+
+#ifdef SADR_OSPF
+void *sfib_find(struct fib *, ip_addr *, int, ip_addr*, int); /* Find or return NULL if doesn't exist */
+void *sfib_get(struct fib *, ip_addr *, int, ip_addr*, int); /* Find or create new if nonexistent */
+void *sfib_route(struct fib *, ip_addr, int, ip_addr, int); /* Longest-match routing lookup */
+#endif
void fib_delete(struct fib *, void *); /* Remove fib entry */
void fib_free(struct fib *); /* Destroy the fib */
void fib_check(struct fib *); /* Consistency check for debugging */
@@ -268,8 +305,17 @@ void rt_commit(struct config *new, struct config *old);
void rt_lock_table(rtable *);
void rt_unlock_table(rtable *);
void rt_setup(pool *, rtable *, char *, struct rtable_config *);
+
static inline net *net_find(rtable *tab, ip_addr addr, unsigned len) { return (net *) fib_find(&tab->fib, &addr, len); }
static inline net *net_get(rtable *tab, ip_addr addr, unsigned len) { return (net *) fib_get(&tab->fib, &addr, len); }
+
+static inline net *net_find2(rtable* tab, addr_data addr) { return (net *) fib_find2(&tab->fib, addr); }
+static inline net *net_get2(rtable* tab, addr_data addr) { return (net *) fib_get2(&tab->fib, addr); }
+
+#ifdef SADR_OSPF
+static inline net *snet_find(rtable *tab, ip_addr addr, unsigned len, ip_addr saddr, unsigned slen) { return (net *) sfib_find(&tab->fib, &addr, len, &saddr, slen); }
+static inline net *snet_get(rtable *tab, ip_addr addr, unsigned len, ip_addr saddr, unsigned slen) { return (net *) sfib_get(&tab->fib, &addr, len, &saddr, slen); }
+#endif
rte *rte_find(net *net, struct rte_src *src);
rte *rte_get_temp(struct rta *);
void rte_update2(struct announce_hook *ah, net *net, rte *new, struct rte_src *src);
diff --git a/nest/rt-fib.c b/nest/rt-fib.c
index a73de1f..7b44e43 100644
--- a/nest/rt-fib.c
+++ b/nest/rt-fib.c
@@ -153,6 +153,15 @@ fib_rehash(struct fib *f, int step)
fib_ht_free(m);
}
+void *
+fib_find2(struct fib *f, addr_data addr) {
+ #ifdef SADR_OSPF
+ return sfib_find(f, addr.prefix, addr.pxlen, addr.src_prefix, addr.src_pxlen);
+ #else
+ return fib_find(f, addr.prefix, addr.pxlen);
+ #endif
+}
+
/**
* fib_find - search for FIB node by prefix
* @f: FIB to search in
@@ -165,6 +174,12 @@ fib_rehash(struct fib *f, int step)
void *
fib_find(struct fib *f, ip_addr *a, int len)
{
+ #ifdef SADR_OSPF
+ // if SADR is enabled, protocols who don't use it should
+ // only search for entries with source address 0::/0
+ return sfib_find(f, a, len, &IPA_NONE, 0);
+ #endif
+
struct fib_node *e = f->hash_table[fib_hash(f, a)];
while (e && (e->pxlen != len || !ipa_equal(*a, e->prefix)))
@@ -172,6 +187,19 @@ fib_find(struct fib *f, ip_addr *a, int len)
return e;
}
+#ifdef SADR_OSPF
+void *
+sfib_find(struct fib *f, ip_addr *a, int len, ip_addr *sa, int slen)
+{
+ struct fib_node *e = f->hash_table[fib_hash(f, a)];
+
+ while (e && (e->pxlen != len || !ipa_equal(*a, e->prefix) ||
+ e->src_pxlen != slen || !ipa_equal(*sa, e->src_prefix)))
+ e = e->next;
+ return e;
+}
+#endif
+
/*
int
fib_histogram(struct fib *f)
@@ -194,6 +222,15 @@ fib_histogram(struct fib *f)
}
*/
+void *
+fib_get2(struct fib* f, addr_data addr) {
+ #ifdef SADR_OSPF
+ return sfib_get(f, addr.prefix, addr.pxlen, addr.src_prefix, addr.src_pxlen);
+ #else
+ return fib_get(f, addr.prefix, addr.pxlen);
+ #endif
+}
+
/**
* fib_get - find or create a FIB node
* @f: FIB to work with
@@ -206,6 +243,10 @@ fib_histogram(struct fib *f)
void *
fib_get(struct fib *f, ip_addr *a, int len)
{
+ #ifdef SADR_OSPF
+ return sfib_get(f, a, len, &IPA_NONE, 0);
+ #endif
+
uint h = ipa_hash(*a);
struct fib_node **ee = f->hash_table + (h >> f->hash_shift);
struct fib_node *g, *e = *ee;
@@ -236,6 +277,73 @@ fib_get(struct fib *f, ip_addr *a, int len)
e = sl_alloc(f->fib_slab);
e->prefix = *a;
e->pxlen = len;
+
+ #ifdef SADR_OSPF
+ // if sadr is enabled, but we don't care about src info, we should
+ // still set the values to zero
+ e->src_prefix = IPA_NONE;
+ e->src_pxlen = 0;
+ #endif
+
+ e->next = *ee;
+ e->uid = uid;
+ *ee = e;
+ e->readers = NULL;
+ f->init(e);
+ if (f->entries++ > f->entries_max)
+ fib_rehash(f, HASH_HI_STEP);
+
+ return e;
+}
+
+#ifdef SADR_OSPF
+/**
+ * sfib_get - find or create a FIB node (taking into account src)
+ * @f: FIB to work with
+ * @a: pointer to IP address of the prefix
+ * @len: prefix length
+ * @sa: pointer to IP address of the source prefix
+ * @slen: source prefix length
+ *
+ * Search for a FIB node corresponding to the given prefix and
+ * return a pointer to it. If no such node exists, create it.
+ */
+void *
+sfib_get(struct fib *f, ip_addr *a, int len, ip_addr* sa, int slen)
+{
+ uint h = ipa_hash(*a);
+ struct fib_node **ee = f->hash_table + (h >> f->hash_shift);
+ struct fib_node *g, *e = *ee;
+ u32 uid = h << 16;
+
+ while (e && (e->pxlen != len || !ipa_equal(*a, e->prefix)
+ || e->src_pxlen != slen || !ipa_equal(*sa, e->src_prefix)))
+ e = e->next;
+ if (e)
+ return e;
+#ifdef DEBUGGING
+ if (len < 0 || len > BITS_PER_IP_ADDRESS || !ip_is_prefix(*a,len))
+ bug("fib_get() called for invalid address");
+#endif
+
+ while ((g = *ee) && g->uid < uid)
+ ee = &g->next;
+ while ((g = *ee) && g->uid == uid)
+ {
+ ee = &g->next;
+ uid++;
+ }
+
+ if ((uid >> 16) != h)
+ log(L_ERR "FIB hash table chains are too long");
+
+ // log (L_WARN "FIB_GET %I %x %x", *a, h, uid);
+
+ e = sl_alloc(f->fib_slab);
+ e->prefix = *a;
+ e->pxlen = len;
+ e->src_prefix = *sa;
+ e->src_pxlen = slen;
e->next = *ee;
e->uid = uid;
*ee = e;
@@ -246,6 +354,17 @@ fib_get(struct fib *f, ip_addr *a, int len)
return e;
}
+#endif
+
+void *
+fib_route2(struct fib *f, addr_data addr)
+{
+ #ifdef SADR_OSPF
+ return sfib_route(f, *addr.prefix, addr.pxlen, *addr.src_prefix, addr.src_pxlen);
+ #else
+ return fib_route(f, *addr.prefix, addr.pxlen);
+ #endif
+}
/**
* fib_route - CIDR routing lookup
@@ -260,6 +379,10 @@ fib_get(struct fib *f, ip_addr *a, int len)
void *
fib_route(struct fib *f, ip_addr a, int len)
{
+ #ifdef SADR_OSPF
+ sfib_route(f, a, len, IPA_NONE, 0);
+ #endif
+
ip_addr a0;
void *t;
@@ -274,6 +397,55 @@ fib_route(struct fib *f, ip_addr a, int len)
return NULL;
}
+#ifdef SADR_OSPF
+void *
+sfib_route(struct fib *f, ip_addr a, int len, ip_addr sa, int slen)
+{
+ ip_addr a0, sa0;
+ void *t;
+ int slent;
+
+ while (len >= 0)
+ {
+ a0 = ipa_and(a, ipa_mkmask(len));
+
+ // fib_find unconstrained by source address
+ struct fib_node *e = f->hash_table[fib_hash(f, &a)];
+ while (e && (e->pxlen != len || !ipa_equal(a, e->prefix)))
+ e = e->next;
+
+ t = e;
+
+ if (t) {
+ slent = slen;
+ while (slent >= 0) {
+ sa0 = ipa_and(sa, ipa_mkmask(slent));
+ t = sfib_find(f, &a0, len, &sa0, slent);
+ if (t)
+ return t;
+ slent--;
+ }
+ }
+ len--;
+ }
+ return NULL;
+}
+#endif
+
+addr_data addr_data_fn_init(struct fib_node *fn) {
+ addr_data addr = {
+ .prefix = &fn->prefix,
+ .pxlen = fn->pxlen
+ };
+
+ #ifdef SADR_OSPF
+ addr.src_prefix = &fn->src_prefix;
+ addr.src_pxlen = fn->src_pxlen;
+ #endif
+
+ return addr;
+}
+
static inline void
fib_merge_readers(struct fib_iterator *i, struct fib_node *to)
{
diff --git a/nest/rt-table.c b/nest/rt-table.c
index d3aba08..309c48c 100644
--- a/nest/rt-table.c
+++ b/nest/rt-table.c
@@ -817,6 +817,17 @@ rte_validate(rte *e)
return 0;
}
+ #ifdef SADR_OSPF
+ // validation for source address data
+ if ((n->n.src_pxlen > BITS_PER_IP_ADDRESS) ||
+ !ip_is_prefix(n->n.src_prefix,n->n.src_pxlen))
+ {
+ log(L_WARN "Ignoring bogus prefix %I/%d received via %s",
+ n->n.src_prefix, n->n.src_pxlen, e->sender->proto->name);
+ return 0;
+ }
+ #endif
+
return 1;
}
--
2.7.4
More information about the Bird-users
mailing list