diff options
Diffstat (limited to 'nest')
| -rw-r--r-- | nest/iface.h | 20 | ||||
| -rw-r--r-- | nest/neighbor.c | 475 | ||||
| -rw-r--r-- | nest/rt-table.c | 8 |
3 files changed, 246 insertions, 257 deletions
diff --git a/nest/iface.h b/nest/iface.h index ab3f8f35..bc241501 100644 --- a/nest/iface.h +++ b/nest/iface.h @@ -124,29 +124,21 @@ typedef struct neighbor { ip_addr addr; /* Address of the neighbor */ struct ifa *ifa; /* Ifa on related iface */ struct iface *iface; /* Interface it's connected to */ + struct iface *ifreq; /* Requested iface, NULL for any */ struct proto *proto; /* Protocol this belongs to */ void *data; /* Protocol-specific data */ - unsigned aux; /* Protocol-specific data */ - unsigned flags; - int scope; /* Address scope, -1 for unreachable sticky neighbors, + uint aux; /* Protocol-specific data */ + u16 flags; /* NEF_* flags */ + s16 scope; /* Address scope, -1 for unreachable neighbors, SCOPE_HOST when it's our own address */ } neighbor; #define NEF_STICKY 1 #define NEF_ONLINK 2 -#define NEF_BIND 4 /* Used internally for neighbors bound to an iface */ -#define NEF_IFACE 8 /* Neighbors bound to iface */ - +#define NEF_IFACE 4 /* Entry for whole iface */ -neighbor *neigh_find(struct proto *, ip_addr *, unsigned flags); -neighbor *neigh_find2(struct proto *p, ip_addr *a, struct iface *ifa, unsigned flags); -neighbor *neigh_find_iface(struct proto *p, struct iface *ifa); -static inline int neigh_connected_to(struct proto *p, ip_addr *a, struct iface *i) -{ - neighbor *n = neigh_find(p, a, 0); - return n && n->iface == i; -} +neighbor *neigh_find(struct proto *p, ip_addr a, struct iface *ifa, uint flags); void neigh_dump(neighbor *); void neigh_dump_all(void); 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); } diff --git a/nest/rt-table.c b/nest/rt-table.c index de7b05fc..0c0e365e 100644 --- a/nest/rt-table.c +++ b/nest/rt-table.c @@ -39,6 +39,7 @@ #include "lib/string.h" #include "conf/conf.h" #include "filter/filter.h" +#include "lib/hash.h" #include "lib/string.h" #include "lib/alloca.h" @@ -2220,13 +2221,6 @@ rt_feed_channel_abort(struct channel *c) } } -static inline unsigned -ptr_hash(void *ptr) -{ - uintptr_t p = (uintptr_t) ptr; - return p ^ (p << 8) ^ (p >> 16); -} - static inline u32 hc_hash(ip_addr a, rtable *dep) { |