summaryrefslogtreecommitdiff
path: root/nest/neighbor.c
diff options
context:
space:
mode:
Diffstat (limited to 'nest/neighbor.c')
-rw-r--r--nest/neighbor.c475
1 files changed, 239 insertions, 236 deletions
diff --git a/nest/neighbor.c b/nest/neighbor.c
index 4f93e29e..87253857 100644
--- a/nest/neighbor.c
+++ b/nest/neighbor.c
@@ -2,6 +2,8 @@
* BIRD -- Neighbor Cache
*
* (c) 1998--2000 Martin Mares <mj@ucw.cz>
+ * (c) 2008--2018 Ondrej Zajicek <santiago@crfreenet.org>
+ * (c) 2008--2018 CZ.NIC z.s.p.o.
*
* Can be freely distributed and used under the terms of the GNU GPL.
*/
@@ -10,32 +12,38 @@
* DOC: Neighbor cache
*
* Most routing protocols need to associate their internal state data with
- * neighboring routers, check whether an address given as the next hop
- * attribute of a route is really an address of a directly connected host
- * and which interface is it connected through. Also, they often need to
- * be notified when a neighbor ceases to exist or when their long awaited
- * neighbor becomes connected. The neighbor cache is there to solve all
- * these problems.
+ * neighboring routers, check whether an address given as the next hop attribute
+ * of a route is really an address of a directly connected host and which
+ * interface is it connected through. Also, they often need to be notified when
+ * a neighbor ceases to exist or when their long awaited neighbor becomes
+ * connected. The neighbor cache is there to solve all these problems.
*
- * The neighbor cache maintains a collection of neighbor entries. Each
- * entry represents one IP address corresponding to either our directly
- * connected neighbor or our own end of the link (when the scope of the
- * address is set to %SCOPE_HOST) together with per-neighbor data belonging to a
- * single protocol.
+ * The neighbor cache maintains a collection of neighbor entries. Each entry
+ * represents one IP address corresponding to either our directly connected
+ * neighbor or our own end of the link (when the scope of the address is set to
+ * %SCOPE_HOST) together with per-neighbor data belonging to a single protocol.
+ * A neighbor entry may be bound to a specific interface, which is required for
+ * link-local IP addresses and optional for global IP addresses.
*
- * Active entries represent known neighbors and are stored in a hash
- * table (to allow fast retrieval based on the IP address of the node) and
- * two linked lists: one global and one per-interface (allowing quick
- * processing of interface change events). Inactive entries exist only
- * when the protocol has explicitly requested it via the %NEF_STICKY
- * flag because it wishes to be notified when the node will again become
- * a neighbor. Such entries are enqueued in a special list which is walked
- * whenever an interface changes its state to up. Neighbor entry VRF
- * association is implied by respective protocol.
+ * Neighbor cache entries are stored in a hash table, which is indexed by triple
+ * (protocol, IP, requested-iface), so if both regular and iface-bound neighbors
+ * are requested, they are represented by two neighbor cache entries. Active
+ * entries are also linked in per-interface list (allowing quick processing of
+ * interface change events). Inactive entries exist only when the protocol has
+ * explicitly requested it via the %NEF_STICKY flag because it wishes to be
+ * notified when the node will again become a neighbor. Such entries are instead
+ * linked in a special list, which is walked whenever an interface changes its
+ * state to up. Neighbor entry VRF association is implied by respective
+ * protocol.
+ *
+ * Besides the already mentioned %NEF_STICKY flag, there is also %NEF_ONLINK,
+ * which specifies that neighbor should be considered reachable on given iface
+ * regardless of associated address ranges, and %NEF_IFACE, which represents
+ * pseudo-neighbor entry for whole interface (and uses %IPA_NONE IP address).
*
* When a neighbor event occurs (a neighbor gets disconnected or a sticky
- * inactive neighbor becomes connected), the protocol hook neigh_notify()
- * is called to advertise the change.
+ * inactive neighbor becomes connected), the protocol hook neigh_notify() is
+ * called to advertise the change.
*/
#undef LOCAL_DEBUG
@@ -43,126 +51,151 @@
#include "nest/bird.h"
#include "nest/iface.h"
#include "nest/protocol.h"
+#include "lib/hash.h"
#include "lib/resource.h"
#define NEIGH_HASH_SIZE 256
#define NEIGH_HASH_OFFSET 24
static slab *neigh_slab;
-static list sticky_neigh_list, iface_neigh_list, neigh_hash_table[NEIGH_HASH_SIZE];
+static list neigh_hash_table[NEIGH_HASH_SIZE], sticky_neigh_list;
static inline uint
-neigh_hash(struct proto *p, ip_addr *a)
+neigh_hash(struct proto *p, ip_addr a, struct iface *i)
{
- return (p->hash_key ^ ipa_hash(*a)) >> NEIGH_HASH_OFFSET;
+ return (p->hash_key ^ ipa_hash(a) ^ ptr_hash(i)) >> NEIGH_HASH_OFFSET;
}
static int
-if_connected(ip_addr *a, struct iface *i, struct ifa **ap)
+if_connected(ip_addr a, struct iface *i, struct ifa **ap, uint flags)
{
struct ifa *b;
+ /* Handle iface pseudo-neighbors */
+ if (flags & NEF_IFACE)
+ return *ap = NULL, (i->flags & IF_UP) ? SCOPE_HOST : -1;
+
+ /* Host addresses match even if iface is down */
+ WALK_LIST(b, i->addrs)
+ if (ipa_equal(a, b->ip))
+ return *ap = b, SCOPE_HOST;
+
+ /* Rest do not match if iface is down */
if (!(i->flags & IF_UP))
- {
- *ap = NULL;
- return -1;
- }
+ return *ap = NULL, -1;
+ /* Regular neighbors */
WALK_LIST(b, i->addrs)
+ {
+ if (b->flags & IA_PEER)
{
- *ap = b;
-
- if (ipa_equal(*a, b->ip))
- return SCOPE_HOST;
- if (b->flags & IA_PEER)
- {
- if (ipa_equal(*a, b->opposite))
- return b->scope;
- }
- else
- {
- if (ipa_in_netX(*a, &b->prefix))
- {
- /* Do not allow IPv4 network and broadcast addresses */
- if (ipa_is_ip4(*a) &&
- (net_pxlen(&b->prefix) < (IP4_MAX_PREFIX_LENGTH - 1)) &&
- (ipa_equal(*a, net_prefix(&b->prefix)) || /* Network address */
- ipa_equal(*a, b->brd))) /* Broadcast */
- {
- *ap = NULL;
- return -1;
- }
-
- return b->scope;
- }
- }
+ if (ipa_equal(a, b->opposite))
+ return *ap = b, b->scope;
+ }
+ else
+ {
+ if (ipa_in_netX(a, &b->prefix))
+ {
+ /* Do not allow IPv4 network and broadcast addresses */
+ if (ipa_is_ip4(a) &&
+ (net_pxlen(&b->prefix) < (IP4_MAX_PREFIX_LENGTH - 1)) &&
+ (ipa_equal(a, net_prefix(&b->prefix)) || /* Network address */
+ ipa_equal(a, b->brd))) /* Broadcast */
+ return *ap = NULL, -1;
+
+ return *ap = b, b->scope;
}
+ }
+ }
+
+ /* Handle ONLINK flag */
+ if (flags & NEF_ONLINK)
+ return *ap = NULL, ipa_classify(a) & IADDR_SCOPE_MASK;
- *ap = NULL;
- return -1;
+ return *ap = NULL, -1;
}
-/**
- * neigh_find - find or create a neighbor entry.
- * @p: protocol which asks for the entry.
- * @a: pointer to IP address of the node to be searched for.
- * @flags: 0 or %NEF_STICKY if you want to create a sticky entry.
- *
- * Search the neighbor cache for a node with given IP address. If
- * it's found, a pointer to the neighbor entry is returned. If no
- * such entry exists and the node is directly connected on
- * one of our active interfaces, a new entry is created and returned
- * to the caller with protocol-dependent fields initialized to zero.
- * If the node is not connected directly or *@a is not a valid unicast
- * IP address, neigh_find() returns %NULL.
- */
-neighbor *
-neigh_find(struct proto *p, ip_addr *a, unsigned flags)
+static inline int
+if_connected_any(ip_addr a, struct iface *vrf, struct iface **iface, struct ifa **addr, uint flags)
{
- return neigh_find2(p, a, NULL, flags);
-}
+ struct iface *i;
+ struct ifa *b;
+ int s, scope = -1;
+
+ *iface = NULL;
+ *addr = NULL;
+
+ /* Get first match, but prefer SCOPE_HOST to other matches */
+ WALK_LIST(i, iface_list)
+ if ((!vrf || vrf == i->master) && ((s = if_connected(a, i, &b, flags)) >= 0))
+ if ((scope < 0) || ((scope > SCOPE_HOST) && (s == SCOPE_HOST)))
+ {
+ *iface = i;
+ *addr = b;
+ scope = s;
+ }
+ return scope;
+}
+/**
+ * neigh_find - find or create a neighbor entry
+ * @p: protocol which asks for the entry
+ * @a: IP address of the node to be searched for
+ * @iface: optionally bound neighbor to this iface (may be NULL)
+ * @flags: %NEF_STICKY for sticky entry, %NEF_ONLINK for onlink entry
+ *
+ * Search the neighbor cache for a node with given IP address. Iface can be
+ * specified for link-local addresses or for cases, where neighbor is expected
+ * on given interface. If it is found, a pointer to the neighbor entry is
+ * returned. If no such entry exists and the node is directly connected on one
+ * of our active interfaces, a new entry is created and returned to the caller
+ * with protocol-dependent fields initialized to zero. If the node is not
+ * connected directly or *@a is not a valid unicast IP address, neigh_find()
+ * returns %NULL.
+ */
neighbor *
-neigh_find2(struct proto *p, ip_addr *a, struct iface *ifa, unsigned flags)
+neigh_find(struct proto *p, ip_addr a, struct iface *iface, uint flags)
{
neighbor *n;
int class, scope = -1;
- uint h = neigh_hash(p, a);
- struct iface *i;
- struct ifa *addr;
+ uint h = neigh_hash(p, a, iface);
+ struct iface *ifreq = iface;
+ struct ifa *addr = NULL;
WALK_LIST(n, neigh_hash_table[h]) /* Search the cache */
- if (n->proto == p && ipa_equal(*a, n->addr) && (!ifa || (ifa == n->iface)))
+ if ((n->proto == p) && ipa_equal(n->addr, a) && (n->ifreq == iface))
return n;
- class = ipa_classify(*a);
- if (class < 0) /* Invalid address */
- return NULL;
- if (((class & IADDR_SCOPE_MASK) == SCOPE_HOST) ||
- (((class & IADDR_SCOPE_MASK) == SCOPE_LINK) && (ifa == NULL)) ||
- !(class & IADDR_HOST))
- return NULL; /* Bad scope or a somecast */
+ if (flags & NEF_IFACE)
+ {
+ if (ipa_nonzero(a) || !iface)
+ return NULL;
+ }
+ else
+ {
+ class = ipa_classify(a);
+ if (class < 0) /* Invalid address */
+ return NULL;
+ if (((class & IADDR_SCOPE_MASK) == SCOPE_HOST) ||
+ (((class & IADDR_SCOPE_MASK) == SCOPE_LINK) && !iface) ||
+ !(class & IADDR_HOST))
+ return NULL; /* Bad scope or a somecast */
+ }
- if (ifa)
- {
- scope = if_connected(a, ifa, &addr);
- flags |= NEF_BIND;
+ if ((flags & NEF_ONLINK) && !iface)
+ return NULL;
- if ((scope < 0) && (flags & NEF_ONLINK))
- scope = class & IADDR_SCOPE_MASK;
- }
+ if (iface)
+ {
+ scope = if_connected(a, iface, &addr, flags);
+ iface = (scope < 0) ? NULL : iface;
+ }
else
- WALK_LIST(i, iface_list)
- if ((!p->vrf || p->vrf == i->master) &&
- ((scope = if_connected(a, i, &addr)) >= 0))
- {
- ifa = i;
- break;
- }
+ scope = if_connected_any(a, p->vrf, &iface, &addr, flags);
/* scope < 0 means i don't know neighbor */
- /* scope >= 0 implies ifa != NULL */
+ /* scope >= 0 <=> iface != NULL */
if ((scope < 0) && !(flags & NEF_STICKY))
return NULL;
@@ -170,52 +203,15 @@ neigh_find2(struct proto *p, ip_addr *a, struct iface *ifa, unsigned flags)
n = sl_alloc(neigh_slab);
memset(n, 0, sizeof(neighbor));
- n->addr = *a;
- if (scope >= 0)
- {
- add_tail(&neigh_hash_table[h], &n->n);
- add_tail(&ifa->neighbors, &n->if_n);
- }
- else
- {
- add_tail(&sticky_neigh_list, &n->n);
- scope = -1;
- }
- n->iface = ifa;
+ add_tail(&neigh_hash_table[h], &n->n);
+ add_tail((scope >= 0) ? &iface->neighbors : &sticky_neigh_list, &n->if_n);
+ n->addr = a;
n->ifa = addr;
+ n->iface = iface;
+ n->ifreq = ifreq;
n->proto = p;
- n->data = NULL;
- n->aux = 0;
n->flags = flags;
n->scope = scope;
- return n;
-}
-
-neighbor *
-neigh_find_iface(struct proto *p, struct iface *ifa)
-{
- neighbor *n;
- node *nn;
-
- /* We keep neighbors with NEF_IFACE foremost in ifa->neighbors list */
- WALK_LIST2(n, nn, ifa->neighbors, if_n)
- {
- if (! (n->flags & NEF_IFACE))
- break;
-
- if (n->proto == p)
- return n;
- }
-
- n = sl_alloc(neigh_slab);
- memset(n, 0, sizeof(neighbor));
-
- add_tail(&iface_neigh_list, &n->n);
- add_head(&ifa->neighbors, &n->if_n);
- n->iface = ifa;
- n->proto = p;
- n->flags = NEF_IFACE;
- n->scope = (ifa->flags & IF_UP) ? SCOPE_HOST : -1;
return n;
}
@@ -224,30 +220,26 @@ neigh_find_iface(struct proto *p, struct iface *ifa)
* neigh_dump - dump specified neighbor entry.
* @n: the entry to dump
*
- * This functions dumps the contents of a given neighbor entry
- * to debug output.
+ * This functions dumps the contents of a given neighbor entry to debug output.
*/
void
neigh_dump(neighbor *n)
{
- debug("%p %I ", n, n->addr);
- if (n->iface)
- debug("%s ", n->iface->name);
- else
- debug("[] ");
+ debug("%p %I %s %s ", n, n->addr,
+ n->iface ? n->iface->name : "[]",
+ n->ifreq ? n->ifreq->name : "[]");
debug("%s %p %08x scope %s", n->proto->name, n->data, n->aux, ip_scope_text(n->scope));
if (n->flags & NEF_STICKY)
debug(" STICKY");
- if (n->flags & NEF_IFACE)
- debug(" IFACE");
+ if (n->flags & NEF_ONLINK)
+ debug(" ONLINK");
debug("\n");
}
/**
* neigh_dump_all - dump all neighbor entries.
*
- * This function dumps the contents of the neighbor cache to
- * debug output.
+ * This function dumps the contents of the neighbor cache to debug output.
*/
void
neigh_dump_all(void)
@@ -256,73 +248,109 @@ neigh_dump_all(void)
int i;
debug("Known neighbors:\n");
- WALK_LIST(n, sticky_neigh_list)
- neigh_dump(n);
- WALK_LIST(n, iface_neigh_list)
- neigh_dump(n);
for(i=0; i<NEIGH_HASH_SIZE; i++)
WALK_LIST(n, neigh_hash_table[i])
neigh_dump(n);
debug("\n");
}
+static inline void
+neigh_notify(neighbor *n)
+{
+ if (n->proto->neigh_notify && (n->proto->proto_state != PS_STOP))
+ n->proto->neigh_notify(n);
+}
+
static void
-neigh_up(neighbor *n, struct iface *i, int scope, struct ifa *a)
+neigh_up(neighbor *n, struct iface *i, struct ifa *a, int scope)
{
DBG("Waking up sticky neighbor %I\n", n->addr);
n->iface = i;
n->ifa = a;
n->scope = scope;
- if (! (n->flags & NEF_IFACE))
- {
- add_tail(&i->neighbors, &n->if_n);
- rem_node(&n->n);
- add_tail(&neigh_hash_table[neigh_hash(n->proto, &n->addr)], &n->n);
- }
+ rem_node(&n->if_n);
+ add_tail(&i->neighbors, &n->if_n);
- if (n->proto->neigh_notify && (n->proto->proto_state != PS_STOP))
- n->proto->neigh_notify(n);
+ neigh_notify(n);
}
static void
neigh_down(neighbor *n)
{
DBG("Flushing neighbor %I on %s\n", n->addr, n->iface->name);
- if (! (n->flags & (NEF_BIND | NEF_IFACE)))
- n->iface = NULL;
+ n->iface = NULL;
n->ifa = NULL;
n->scope = -1;
- if (! (n->flags & NEF_IFACE))
- {
- rem_node(&n->if_n);
- rem_node(&n->n);
- }
+ rem_node(&n->if_n);
+ add_tail(&sticky_neigh_list, &n->if_n);
- if (n->proto->neigh_notify && (n->proto->proto_state != PS_STOP))
- n->proto->neigh_notify(n);
+ neigh_notify(n);
+}
- if (n->flags & NEF_STICKY)
+static inline void
+neigh_free(neighbor *n)
+{
+ rem_node(&n->n);
+ rem_node(&n->if_n);
+ sl_free(neigh_slab, n);
+}
+
+/**
+ * neigh_update: update neighbor entry w.r.t. change on specific iface
+ * @n: neighbor to update
+ * @iface: changed iface
+ *
+ * The function recalculates state of the neighbor entry @n assuming that only
+ * the interface @iface may changed its state or addresses. Then, appropriate
+ * actions are executed (the neighbor goes up, down, up-down, or just notified).
+ */
+void
+neigh_update(neighbor *n, struct iface *iface)
+{
+ struct ifa *ifa = NULL;
+ int scope = -1;
+
+ /* Iface-bound neighbors ignore other ifaces */
+ if (n->ifreq && (n->ifreq != iface))
+ return;
+
+ /* VRF-bound neighbors ignore changes in other VRFs */
+ if (n->proto->vrf && (n->proto->vrf != iface->master))
+ return;
+
+ scope = if_connected(n->addr, iface, &ifa, n->flags);
+
+ /* When neighbor is going down, try to respawn it on other ifaces */
+ if ((scope < 0) && (n->scope >= 0) && !n->ifreq && (n->flags & NEF_STICKY))
+ scope = if_connected_any(n->addr, n->proto->vrf, &iface, &ifa, n->flags);
+
+ /* No change or minor change - ignore or notify */
+ if ((scope == n->scope) && (iface == n->iface))
+ {
+ if (ifa != n->ifa)
{
- add_tail(&sticky_neigh_list, &n->n);
-
- /* Respawn neighbor if there is another matching prefix */
- struct iface *i;
- struct ifa *a;
- int scope;
-
- if (!n->iface)
- WALK_LIST(i, iface_list)
- if ((scope = if_connected(&n->addr, i, &a)) >= 0)
- {
- neigh_up(n, i, scope, a);
- return;
- }
+ n->ifa = ifa;
+ neigh_notify(n);
}
- if (! (n->flags & (NEF_STICKY | NEF_IFACE)))
- sl_free(neigh_slab, n);
+ return;
+ }
+
+ /* Major change - going down and/or going up */
+
+ if (n->scope >= 0)
+ neigh_down(n);
+
+ if ((n->scope < 0) && !(n->flags & NEF_STICKY))
+ {
+ neigh_free(n);
+ return;
+ }
+
+ if (scope >= 0)
+ neigh_up(n, iface, ifa, scope);
}
@@ -338,21 +366,11 @@ neigh_down(neighbor *n)
void
neigh_if_up(struct iface *i)
{
- struct ifa *a;
neighbor *n;
node *x, *y;
- int scope;
- /* Wake up all iface neighbors */
- WALK_LIST2_DELSAFE(n, x, y, i->neighbors, if_n)
- if ((n->scope < 0) && (n->flags & NEF_IFACE))
- neigh_up(n, i, SCOPE_HOST, NULL);
-
- /* Wake up appropriate sticky neighbors */
- WALK_LIST_DELSAFE(n, x, sticky_neigh_list)
- if ((!n->iface || n->iface == i) &&
- ((scope = if_connected(&n->addr, i, &a)) >= 0))
- neigh_up(n, i, scope, a);
+ WALK_LIST2_DELSAFE(n, x, y, sticky_neigh_list, if_n)
+ neigh_update(n, i);
}
/**
@@ -361,8 +379,7 @@ neigh_if_up(struct iface *i)
*
* Notify the neighbor cache that an interface has ceased to exist.
*
- * It causes all entries belonging to neighbors connected to this interface
- * to be flushed.
+ * It causes all neighbors connected to this interface to be updated or removed.
*/
void
neigh_if_down(struct iface *i)
@@ -371,16 +388,15 @@ neigh_if_down(struct iface *i)
node *x, *y;
WALK_LIST2_DELSAFE(n, x, y, i->neighbors, if_n)
- neigh_down(n);
+ neigh_update(n, i);
}
/**
* neigh_if_link - notify neighbor cache about interface link change
* @i: the interface in question
*
- * Notify the neighbor cache that an interface changed link state.
- * All owners of neighbor entries connected to this interface are
- * notified.
+ * Notify the neighbor cache that an interface changed link state. All owners of
+ * neighbor entries connected to this interface are notified.
*/
void
neigh_if_link(struct iface *i)
@@ -389,8 +405,7 @@ neigh_if_link(struct iface *i)
node *x, *y;
WALK_LIST2_DELSAFE(n, x, y, i->neighbors, if_n)
- if (n->proto->neigh_notify && (n->proto->proto_state != PS_STOP))
- n->proto->neigh_notify(n);
+ neigh_notify(n);
}
/**
@@ -407,21 +422,16 @@ void
neigh_ifa_update(struct ifa *a)
{
struct iface *i = a->iface;
- struct ifa *aa;
- node *x, *y;
neighbor *n;
- int scope;
+ node *x, *y;
- /* Remove all neighbors whose scope has changed */
+ /* Update all neighbors whose scope has changed */
WALK_LIST2_DELSAFE(n, x, y, i->neighbors, if_n)
- if (n->ifa && (if_connected(&n->addr, i, &aa) != n->scope))
- neigh_down(n);
+ neigh_update(n, i);
/* Wake up all sticky neighbors that are reachable now */
- WALK_LIST_DELSAFE(n, x, sticky_neigh_list)
- if ((!n->iface || n->iface == i) &&
- ((scope = if_connected(&n->addr, i, &aa)) >= 0))
- neigh_up(n, i, scope, aa);
+ WALK_LIST2_DELSAFE(n, x, y, sticky_neigh_list, if_n)
+ neigh_update(n, i);
}
static inline void
@@ -429,10 +439,8 @@ neigh_prune_one(neighbor *n)
{
if (n->proto->proto_state != PS_DOWN)
return;
- rem_node(&n->n);
- if (n->if_n.next)
- rem_node(&n->if_n);
- sl_free(neigh_slab, n);
+
+ neigh_free(n);
}
/**
@@ -453,10 +461,6 @@ neigh_prune(void)
for(i=0; i<NEIGH_HASH_SIZE; i++)
WALK_LIST_DELSAFE(n, m, neigh_hash_table[i])
neigh_prune_one(n);
- WALK_LIST_DELSAFE(n, m, sticky_neigh_list)
- neigh_prune_one(n);
- WALK_LIST_DELSAFE(n, m, iface_neigh_list)
- neigh_prune_one(n);
}
/**
@@ -471,9 +475,8 @@ neigh_init(pool *if_pool)
{
neigh_slab = sl_new(if_pool, sizeof(neighbor));
- init_list(&sticky_neigh_list);
- init_list(&iface_neigh_list);
-
for(int i = 0; i < NEIGH_HASH_SIZE; i++)
init_list(&neigh_hash_table[i]);
+
+ init_list(&sticky_neigh_list);
}