Annotation of embedaddon/bird2/nest/neighbor.c, revision 1.1
1.1 ! misho 1: /*
! 2: * BIRD -- Neighbor Cache
! 3: *
! 4: * (c) 1998--2000 Martin Mares <mj@ucw.cz>
! 5: * (c) 2008--2018 Ondrej Zajicek <santiago@crfreenet.org>
! 6: * (c) 2008--2018 CZ.NIC z.s.p.o.
! 7: *
! 8: * Can be freely distributed and used under the terms of the GNU GPL.
! 9: */
! 10:
! 11: /**
! 12: * DOC: Neighbor cache
! 13: *
! 14: * Most routing protocols need to associate their internal state data with
! 15: * neighboring routers, check whether an address given as the next hop attribute
! 16: * of a route is really an address of a directly connected host and which
! 17: * interface is it connected through. Also, they often need to be notified when
! 18: * a neighbor ceases to exist or when their long awaited neighbor becomes
! 19: * connected. The neighbor cache is there to solve all these problems.
! 20: *
! 21: * The neighbor cache maintains a collection of neighbor entries. Each entry
! 22: * represents one IP address corresponding to either our directly connected
! 23: * neighbor or our own end of the link (when the scope of the address is set to
! 24: * %SCOPE_HOST) together with per-neighbor data belonging to a single protocol.
! 25: * A neighbor entry may be bound to a specific interface, which is required for
! 26: * link-local IP addresses and optional for global IP addresses.
! 27: *
! 28: * Neighbor cache entries are stored in a hash table, which is indexed by triple
! 29: * (protocol, IP, requested-iface), so if both regular and iface-bound neighbors
! 30: * are requested, they are represented by two neighbor cache entries. Active
! 31: * entries are also linked in per-interface list (allowing quick processing of
! 32: * interface change events). Inactive entries exist only when the protocol has
! 33: * explicitly requested it via the %NEF_STICKY flag because it wishes to be
! 34: * notified when the node will again become a neighbor. Such entries are instead
! 35: * linked in a special list, which is walked whenever an interface changes its
! 36: * state to up. Neighbor entry VRF association is implied by respective
! 37: * protocol.
! 38: *
! 39: * Besides the already mentioned %NEF_STICKY flag, there is also %NEF_ONLINK,
! 40: * which specifies that neighbor should be considered reachable on given iface
! 41: * regardless of associated address ranges, and %NEF_IFACE, which represents
! 42: * pseudo-neighbor entry for whole interface (and uses %IPA_NONE IP address).
! 43: *
! 44: * When a neighbor event occurs (a neighbor gets disconnected or a sticky
! 45: * inactive neighbor becomes connected), the protocol hook neigh_notify() is
! 46: * called to advertise the change.
! 47: */
! 48:
! 49: #undef LOCAL_DEBUG
! 50:
! 51: #include "nest/bird.h"
! 52: #include "nest/iface.h"
! 53: #include "nest/protocol.h"
! 54: #include "lib/hash.h"
! 55: #include "lib/resource.h"
! 56:
! 57: #define NEIGH_HASH_SIZE 256
! 58: #define NEIGH_HASH_OFFSET 24
! 59:
! 60: static slab *neigh_slab;
! 61: static list neigh_hash_table[NEIGH_HASH_SIZE], sticky_neigh_list;
! 62:
! 63: static inline uint
! 64: neigh_hash(struct proto *p, ip_addr a, struct iface *i)
! 65: {
! 66: return (p->hash_key ^ ipa_hash(a) ^ ptr_hash(i)) >> NEIGH_HASH_OFFSET;
! 67: }
! 68:
! 69: static int
! 70: if_connected(ip_addr a, struct iface *i, struct ifa **ap, uint flags)
! 71: {
! 72: struct ifa *b;
! 73:
! 74: /* Handle iface pseudo-neighbors */
! 75: if (flags & NEF_IFACE)
! 76: return *ap = NULL, (i->flags & IF_UP) ? SCOPE_HOST : -1;
! 77:
! 78: /* Host addresses match even if iface is down */
! 79: WALK_LIST(b, i->addrs)
! 80: if (ipa_equal(a, b->ip))
! 81: return *ap = b, SCOPE_HOST;
! 82:
! 83: /* Rest do not match if iface is down */
! 84: if (!(i->flags & IF_UP))
! 85: return *ap = NULL, -1;
! 86:
! 87: /* Regular neighbors */
! 88: WALK_LIST(b, i->addrs)
! 89: {
! 90: if (b->flags & IA_PEER)
! 91: {
! 92: if (ipa_equal(a, b->opposite))
! 93: return *ap = b, b->scope;
! 94: }
! 95: else
! 96: {
! 97: if (ipa_in_netX(a, &b->prefix))
! 98: {
! 99: /* Do not allow IPv4 network and broadcast addresses */
! 100: if (ipa_is_ip4(a) &&
! 101: (net_pxlen(&b->prefix) < (IP4_MAX_PREFIX_LENGTH - 1)) &&
! 102: (ipa_equal(a, net_prefix(&b->prefix)) || /* Network address */
! 103: ipa_equal(a, b->brd))) /* Broadcast */
! 104: return *ap = NULL, -1;
! 105:
! 106: return *ap = b, b->scope;
! 107: }
! 108: }
! 109: }
! 110:
! 111: /* Handle ONLINK flag */
! 112: if (flags & NEF_ONLINK)
! 113: return *ap = NULL, ipa_classify(a) & IADDR_SCOPE_MASK;
! 114:
! 115: return *ap = NULL, -1;
! 116: }
! 117:
! 118: static inline int
! 119: if_connected_any(ip_addr a, struct iface *vrf, uint vrf_set, struct iface **iface, struct ifa **addr, uint flags)
! 120: {
! 121: struct iface *i;
! 122: struct ifa *b;
! 123: int s, scope = -1;
! 124:
! 125: *iface = NULL;
! 126: *addr = NULL;
! 127:
! 128: /* Get first match, but prefer SCOPE_HOST to other matches */
! 129: WALK_LIST(i, iface_list)
! 130: if ((!vrf_set || vrf == i->master) && ((s = if_connected(a, i, &b, flags)) >= 0))
! 131: if ((scope < 0) || ((scope > SCOPE_HOST) && (s == SCOPE_HOST)))
! 132: {
! 133: *iface = i;
! 134: *addr = b;
! 135: scope = s;
! 136: }
! 137:
! 138: return scope;
! 139: }
! 140:
! 141: /**
! 142: * neigh_find - find or create a neighbor entry
! 143: * @p: protocol which asks for the entry
! 144: * @a: IP address of the node to be searched for
! 145: * @iface: optionally bound neighbor to this iface (may be NULL)
! 146: * @flags: %NEF_STICKY for sticky entry, %NEF_ONLINK for onlink entry
! 147: *
! 148: * Search the neighbor cache for a node with given IP address. Iface can be
! 149: * specified for link-local addresses or for cases, where neighbor is expected
! 150: * on given interface. If it is found, a pointer to the neighbor entry is
! 151: * returned. If no such entry exists and the node is directly connected on one
! 152: * of our active interfaces, a new entry is created and returned to the caller
! 153: * with protocol-dependent fields initialized to zero. If the node is not
! 154: * connected directly or *@a is not a valid unicast IP address, neigh_find()
! 155: * returns %NULL.
! 156: */
! 157: neighbor *
! 158: neigh_find(struct proto *p, ip_addr a, struct iface *iface, uint flags)
! 159: {
! 160: neighbor *n;
! 161: int class, scope = -1;
! 162: uint h = neigh_hash(p, a, iface);
! 163: struct iface *ifreq = iface;
! 164: struct ifa *addr = NULL;
! 165:
! 166: WALK_LIST(n, neigh_hash_table[h]) /* Search the cache */
! 167: if ((n->proto == p) && ipa_equal(n->addr, a) && (n->ifreq == iface))
! 168: return n;
! 169:
! 170: if (flags & NEF_IFACE)
! 171: {
! 172: if (ipa_nonzero(a) || !iface)
! 173: return NULL;
! 174: }
! 175: else
! 176: {
! 177: class = ipa_classify(a);
! 178: if (class < 0) /* Invalid address */
! 179: return NULL;
! 180: if (((class & IADDR_SCOPE_MASK) == SCOPE_HOST) ||
! 181: (((class & IADDR_SCOPE_MASK) == SCOPE_LINK) && !iface) ||
! 182: !(class & IADDR_HOST))
! 183: return NULL; /* Bad scope or a somecast */
! 184: }
! 185:
! 186: if ((flags & NEF_ONLINK) && !iface)
! 187: return NULL;
! 188:
! 189: if (iface)
! 190: {
! 191: scope = if_connected(a, iface, &addr, flags);
! 192: iface = (scope < 0) ? NULL : iface;
! 193: }
! 194: else
! 195: scope = if_connected_any(a, p->vrf, p->vrf_set, &iface, &addr, flags);
! 196:
! 197: /* scope < 0 means i don't know neighbor */
! 198: /* scope >= 0 <=> iface != NULL */
! 199:
! 200: if ((scope < 0) && !(flags & NEF_STICKY))
! 201: return NULL;
! 202:
! 203: n = sl_alloc(neigh_slab);
! 204: memset(n, 0, sizeof(neighbor));
! 205:
! 206: add_tail(&neigh_hash_table[h], &n->n);
! 207: add_tail((scope >= 0) ? &iface->neighbors : &sticky_neigh_list, &n->if_n);
! 208: n->addr = a;
! 209: n->ifa = addr;
! 210: n->iface = iface;
! 211: n->ifreq = ifreq;
! 212: n->proto = p;
! 213: n->flags = flags;
! 214: n->scope = scope;
! 215:
! 216: return n;
! 217: }
! 218:
! 219: /**
! 220: * neigh_dump - dump specified neighbor entry.
! 221: * @n: the entry to dump
! 222: *
! 223: * This functions dumps the contents of a given neighbor entry to debug output.
! 224: */
! 225: void
! 226: neigh_dump(neighbor *n)
! 227: {
! 228: debug("%p %I %s %s ", n, n->addr,
! 229: n->iface ? n->iface->name : "[]",
! 230: n->ifreq ? n->ifreq->name : "[]");
! 231: debug("%s %p %08x scope %s", n->proto->name, n->data, n->aux, ip_scope_text(n->scope));
! 232: if (n->flags & NEF_STICKY)
! 233: debug(" STICKY");
! 234: if (n->flags & NEF_ONLINK)
! 235: debug(" ONLINK");
! 236: debug("\n");
! 237: }
! 238:
! 239: /**
! 240: * neigh_dump_all - dump all neighbor entries.
! 241: *
! 242: * This function dumps the contents of the neighbor cache to debug output.
! 243: */
! 244: void
! 245: neigh_dump_all(void)
! 246: {
! 247: neighbor *n;
! 248: int i;
! 249:
! 250: debug("Known neighbors:\n");
! 251: for(i=0; i<NEIGH_HASH_SIZE; i++)
! 252: WALK_LIST(n, neigh_hash_table[i])
! 253: neigh_dump(n);
! 254: debug("\n");
! 255: }
! 256:
! 257: static inline void
! 258: neigh_notify(neighbor *n)
! 259: {
! 260: if (n->proto->neigh_notify && (n->proto->proto_state != PS_STOP))
! 261: n->proto->neigh_notify(n);
! 262: }
! 263:
! 264: static void
! 265: neigh_up(neighbor *n, struct iface *i, struct ifa *a, int scope)
! 266: {
! 267: DBG("Waking up sticky neighbor %I\n", n->addr);
! 268: n->iface = i;
! 269: n->ifa = a;
! 270: n->scope = scope;
! 271:
! 272: rem_node(&n->if_n);
! 273: add_tail(&i->neighbors, &n->if_n);
! 274:
! 275: neigh_notify(n);
! 276: }
! 277:
! 278: static void
! 279: neigh_down(neighbor *n)
! 280: {
! 281: DBG("Flushing neighbor %I on %s\n", n->addr, n->iface->name);
! 282: n->iface = NULL;
! 283: n->ifa = NULL;
! 284: n->scope = -1;
! 285:
! 286: rem_node(&n->if_n);
! 287: add_tail(&sticky_neigh_list, &n->if_n);
! 288:
! 289: neigh_notify(n);
! 290: }
! 291:
! 292: static inline void
! 293: neigh_free(neighbor *n)
! 294: {
! 295: rem_node(&n->n);
! 296: rem_node(&n->if_n);
! 297: sl_free(neigh_slab, n);
! 298: }
! 299:
! 300: /**
! 301: * neigh_update: update neighbor entry w.r.t. change on specific iface
! 302: * @n: neighbor to update
! 303: * @iface: changed iface
! 304: *
! 305: * The function recalculates state of the neighbor entry @n assuming that only
! 306: * the interface @iface may changed its state or addresses. Then, appropriate
! 307: * actions are executed (the neighbor goes up, down, up-down, or just notified).
! 308: */
! 309: void
! 310: neigh_update(neighbor *n, struct iface *iface)
! 311: {
! 312: struct proto *p = n->proto;
! 313: struct ifa *ifa = NULL;
! 314: int scope = -1;
! 315:
! 316: /* Iface-bound neighbors ignore other ifaces */
! 317: if (n->ifreq && (n->ifreq != iface))
! 318: return;
! 319:
! 320: /* VRF-bound neighbors ignore changes in other VRFs */
! 321: if (p->vrf_set && (p->vrf != iface->master))
! 322: return;
! 323:
! 324: scope = if_connected(n->addr, iface, &ifa, n->flags);
! 325:
! 326: /* When neighbor is going down, try to respawn it on other ifaces */
! 327: if ((scope < 0) && (n->scope >= 0) && !n->ifreq && (n->flags & NEF_STICKY))
! 328: scope = if_connected_any(n->addr, p->vrf, p->vrf_set, &iface, &ifa, n->flags);
! 329:
! 330: /* No change or minor change - ignore or notify */
! 331: if ((scope == n->scope) && (iface == n->iface))
! 332: {
! 333: if (ifa != n->ifa)
! 334: {
! 335: n->ifa = ifa;
! 336: neigh_notify(n);
! 337: }
! 338:
! 339: return;
! 340: }
! 341:
! 342: /* Major change - going down and/or going up */
! 343:
! 344: if (n->scope >= 0)
! 345: neigh_down(n);
! 346:
! 347: if ((n->scope < 0) && !(n->flags & NEF_STICKY))
! 348: {
! 349: neigh_free(n);
! 350: return;
! 351: }
! 352:
! 353: if (scope >= 0)
! 354: neigh_up(n, iface, ifa, scope);
! 355: }
! 356:
! 357:
! 358: /**
! 359: * neigh_if_up: notify neighbor cache about interface up event
! 360: * @i: interface in question
! 361: *
! 362: * Tell the neighbor cache that a new interface became up.
! 363: *
! 364: * The neighbor cache wakes up all inactive sticky neighbors with
! 365: * addresses belonging to prefixes of the interface @i.
! 366: */
! 367: void
! 368: neigh_if_up(struct iface *i)
! 369: {
! 370: neighbor *n;
! 371: node *x, *y;
! 372:
! 373: WALK_LIST2_DELSAFE(n, x, y, sticky_neigh_list, if_n)
! 374: neigh_update(n, i);
! 375: }
! 376:
! 377: /**
! 378: * neigh_if_down - notify neighbor cache about interface down event
! 379: * @i: the interface in question
! 380: *
! 381: * Notify the neighbor cache that an interface has ceased to exist.
! 382: *
! 383: * It causes all neighbors connected to this interface to be updated or removed.
! 384: */
! 385: void
! 386: neigh_if_down(struct iface *i)
! 387: {
! 388: neighbor *n;
! 389: node *x, *y;
! 390:
! 391: WALK_LIST2_DELSAFE(n, x, y, i->neighbors, if_n)
! 392: neigh_update(n, i);
! 393: }
! 394:
! 395: /**
! 396: * neigh_if_link - notify neighbor cache about interface link change
! 397: * @i: the interface in question
! 398: *
! 399: * Notify the neighbor cache that an interface changed link state. All owners of
! 400: * neighbor entries connected to this interface are notified.
! 401: */
! 402: void
! 403: neigh_if_link(struct iface *i)
! 404: {
! 405: neighbor *n;
! 406: node *x, *y;
! 407:
! 408: WALK_LIST2_DELSAFE(n, x, y, i->neighbors, if_n)
! 409: neigh_notify(n);
! 410: }
! 411:
! 412: /**
! 413: * neigh_ifa_update: notify neighbor cache about interface address add or remove event
! 414: * @a: interface address in question
! 415: *
! 416: * Tell the neighbor cache that an address was added or removed.
! 417: *
! 418: * The neighbor cache wakes up all inactive sticky neighbors with
! 419: * addresses belonging to prefixes of the interface belonging to @ifa
! 420: * and causes all unreachable neighbors to be flushed.
! 421: */
! 422: void
! 423: neigh_ifa_update(struct ifa *a)
! 424: {
! 425: struct iface *i = a->iface;
! 426: neighbor *n;
! 427: node *x, *y;
! 428:
! 429: /* Update all neighbors whose scope has changed */
! 430: WALK_LIST2_DELSAFE(n, x, y, i->neighbors, if_n)
! 431: neigh_update(n, i);
! 432:
! 433: /* Wake up all sticky neighbors that are reachable now */
! 434: WALK_LIST2_DELSAFE(n, x, y, sticky_neigh_list, if_n)
! 435: neigh_update(n, i);
! 436: }
! 437:
! 438: static inline void
! 439: neigh_prune_one(neighbor *n)
! 440: {
! 441: if (n->proto->proto_state != PS_DOWN)
! 442: return;
! 443:
! 444: neigh_free(n);
! 445: }
! 446:
! 447: /**
! 448: * neigh_prune - prune neighbor cache
! 449: *
! 450: * neigh_prune() examines all neighbor entries cached and removes those
! 451: * corresponding to inactive protocols. It's called whenever a protocol
! 452: * is shut down to get rid of all its heritage.
! 453: */
! 454: void
! 455: neigh_prune(void)
! 456: {
! 457: neighbor *n;
! 458: node *m;
! 459: int i;
! 460:
! 461: DBG("Pruning neighbors\n");
! 462: for(i=0; i<NEIGH_HASH_SIZE; i++)
! 463: WALK_LIST_DELSAFE(n, m, neigh_hash_table[i])
! 464: neigh_prune_one(n);
! 465: }
! 466:
! 467: /**
! 468: * neigh_init - initialize the neighbor cache.
! 469: * @if_pool: resource pool to be used for neighbor entries.
! 470: *
! 471: * This function is called during BIRD startup to initialize
! 472: * the neighbor cache module.
! 473: */
! 474: void
! 475: neigh_init(pool *if_pool)
! 476: {
! 477: neigh_slab = sl_new(if_pool, sizeof(neighbor));
! 478:
! 479: for(int i = 0; i < NEIGH_HASH_SIZE; i++)
! 480: init_list(&neigh_hash_table[i]);
! 481:
! 482: init_list(&sticky_neigh_list);
! 483: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to neighbor.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird2 / nest