Annotation of embedaddon/bird/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: *
! 6: * Can be freely distributed and used under the terms of the GNU GPL.
! 7: */
! 8:
! 9: /**
! 10: * DOC: Neighbor cache
! 11: *
! 12: * Most routing protocols need to associate their internal state data with
! 13: * neighboring routers, check whether an address given as the next hop
! 14: * attribute of a route is really an address of a directly connected host
! 15: * and which interface is it connected through. Also, they often need to
! 16: * be notified when a neighbor ceases to exist or when their long awaited
! 17: * neighbor becomes connected. The neighbor cache is there to solve all
! 18: * these problems.
! 19: *
! 20: * The neighbor cache maintains a collection of neighbor entries. Each
! 21: * entry represents one IP address corresponding to either our directly
! 22: * connected neighbor or our own end of the link (when the scope of the
! 23: * address is set to %SCOPE_HOST) together with per-neighbor data belonging to a
! 24: * single protocol.
! 25: *
! 26: * Active entries represent known neighbors and are stored in a hash
! 27: * table (to allow fast retrieval based on the IP address of the node) and
! 28: * two linked lists: one global and one per-interface (allowing quick
! 29: * processing of interface change events). Inactive entries exist only
! 30: * when the protocol has explicitly requested it via the %NEF_STICKY
! 31: * flag because it wishes to be notified when the node will again become
! 32: * a neighbor. Such entries are enqueued in a special list which is walked
! 33: * whenever an interface changes its state to up.
! 34: *
! 35: * When a neighbor event occurs (a neighbor gets disconnected or a sticky
! 36: * inactive neighbor becomes connected), the protocol hook neigh_notify()
! 37: * is called to advertise the change.
! 38: */
! 39:
! 40: #undef LOCAL_DEBUG
! 41:
! 42: #include "nest/bird.h"
! 43: #include "nest/iface.h"
! 44: #include "nest/protocol.h"
! 45: #include "lib/resource.h"
! 46:
! 47: #define NEIGH_HASH_SIZE 256
! 48:
! 49: static slab *neigh_slab;
! 50: static list sticky_neigh_list, neigh_hash_table[NEIGH_HASH_SIZE];
! 51:
! 52: static inline uint
! 53: neigh_hash(struct proto *p, ip_addr *a)
! 54: {
! 55: return (p->hash_key ^ ipa_hash(*a)) & (NEIGH_HASH_SIZE-1);
! 56: }
! 57:
! 58: static int
! 59: if_connected(ip_addr *a, struct iface *i, struct ifa **ap)
! 60: {
! 61: struct ifa *b;
! 62:
! 63: if (!(i->flags & IF_UP))
! 64: {
! 65: *ap = NULL;
! 66: return -1;
! 67: }
! 68:
! 69: WALK_LIST(b, i->addrs)
! 70: {
! 71: *ap = b;
! 72:
! 73: if (ipa_equal(*a, b->ip))
! 74: return SCOPE_HOST;
! 75: if (b->flags & IA_PEER)
! 76: {
! 77: if (ipa_equal(*a, b->opposite))
! 78: return b->scope;
! 79: }
! 80: else
! 81: {
! 82: if (ipa_in_net(*a, b->prefix, b->pxlen))
! 83: {
! 84: #ifndef IPV6
! 85: if ((b->pxlen < (BITS_PER_IP_ADDRESS - 1)) &&
! 86: (ipa_equal(*a, b->prefix) || /* Network address */
! 87: ipa_equal(*a, b->brd))) /* Broadcast */
! 88: {
! 89: *ap = NULL;
! 90: return -1;
! 91: }
! 92: #endif
! 93:
! 94: return b->scope;
! 95: }
! 96: }
! 97: }
! 98:
! 99: *ap = NULL;
! 100: return -1;
! 101: }
! 102:
! 103: /**
! 104: * neigh_find - find or create a neighbor entry.
! 105: * @p: protocol which asks for the entry.
! 106: * @a: pointer to IP address of the node to be searched for.
! 107: * @flags: 0 or %NEF_STICKY if you want to create a sticky entry.
! 108: *
! 109: * Search the neighbor cache for a node with given IP address. If
! 110: * it's found, a pointer to the neighbor entry is returned. If no
! 111: * such entry exists and the node is directly connected on
! 112: * one of our active interfaces, a new entry is created and returned
! 113: * to the caller with protocol-dependent fields initialized to zero.
! 114: * If the node is not connected directly or *@a is not a valid unicast
! 115: * IP address, neigh_find() returns %NULL.
! 116: */
! 117: neighbor *
! 118: neigh_find(struct proto *p, ip_addr *a, unsigned flags)
! 119: {
! 120: return neigh_find2(p, a, NULL, flags);
! 121: }
! 122:
! 123:
! 124: neighbor *
! 125: neigh_find2(struct proto *p, ip_addr *a, struct iface *ifa, unsigned flags)
! 126: {
! 127: neighbor *n;
! 128: int class, scope = -1;
! 129: uint h = neigh_hash(p, a);
! 130: struct iface *i;
! 131: struct ifa *addr;
! 132:
! 133: WALK_LIST(n, neigh_hash_table[h]) /* Search the cache */
! 134: if (n->proto == p && ipa_equal(*a, n->addr) && (!ifa || (ifa == n->iface)))
! 135: return n;
! 136:
! 137: class = ipa_classify(*a);
! 138: if (class < 0) /* Invalid address */
! 139: return NULL;
! 140: if (((class & IADDR_SCOPE_MASK) == SCOPE_HOST) ||
! 141: (((class & IADDR_SCOPE_MASK) == SCOPE_LINK) && (ifa == NULL)) ||
! 142: !(class & IADDR_HOST))
! 143: return NULL; /* Bad scope or a somecast */
! 144:
! 145: if (ifa)
! 146: {
! 147: scope = if_connected(a, ifa, &addr);
! 148: flags |= NEF_BIND;
! 149:
! 150: if ((scope < 0) && (flags & NEF_ONLINK))
! 151: scope = class & IADDR_SCOPE_MASK;
! 152: }
! 153: else
! 154: WALK_LIST(i, iface_list)
! 155: if ((scope = if_connected(a, i, &addr)) >= 0)
! 156: {
! 157: ifa = i;
! 158: break;
! 159: }
! 160:
! 161: /* scope < 0 means i don't know neighbor */
! 162: /* scope >= 0 implies ifa != NULL */
! 163:
! 164: if ((scope < 0) && !(flags & NEF_STICKY))
! 165: return NULL;
! 166:
! 167: n = sl_alloc(neigh_slab);
! 168: n->addr = *a;
! 169: if (scope >= 0)
! 170: {
! 171: add_tail(&neigh_hash_table[h], &n->n);
! 172: add_tail(&ifa->neighbors, &n->if_n);
! 173: }
! 174: else
! 175: {
! 176: add_tail(&sticky_neigh_list, &n->n);
! 177: scope = -1;
! 178: }
! 179: n->iface = ifa;
! 180: n->ifa = addr;
! 181: n->proto = p;
! 182: n->data = NULL;
! 183: n->aux = 0;
! 184: n->flags = flags;
! 185: n->scope = scope;
! 186: return n;
! 187: }
! 188:
! 189: /**
! 190: * neigh_dump - dump specified neighbor entry.
! 191: * @n: the entry to dump
! 192: *
! 193: * This functions dumps the contents of a given neighbor entry
! 194: * to debug output.
! 195: */
! 196: void
! 197: neigh_dump(neighbor *n)
! 198: {
! 199: debug("%p %I ", n, n->addr);
! 200: if (n->iface)
! 201: debug("%s ", n->iface->name);
! 202: else
! 203: debug("[] ");
! 204: debug("%s %p %08x scope %s", n->proto->name, n->data, n->aux, ip_scope_text(n->scope));
! 205: if (n->flags & NEF_STICKY)
! 206: debug(" STICKY");
! 207: debug("\n");
! 208: }
! 209:
! 210: /**
! 211: * neigh_dump_all - dump all neighbor entries.
! 212: *
! 213: * This function dumps the contents of the neighbor cache to
! 214: * debug output.
! 215: */
! 216: void
! 217: neigh_dump_all(void)
! 218: {
! 219: neighbor *n;
! 220: int i;
! 221:
! 222: debug("Known neighbors:\n");
! 223: WALK_LIST(n, sticky_neigh_list)
! 224: neigh_dump(n);
! 225: for(i=0; i<NEIGH_HASH_SIZE; i++)
! 226: WALK_LIST(n, neigh_hash_table[i])
! 227: neigh_dump(n);
! 228: debug("\n");
! 229: }
! 230:
! 231: static void
! 232: neigh_up(neighbor *n, struct iface *i, int scope, struct ifa *a)
! 233: {
! 234: n->iface = i;
! 235: n->ifa = a;
! 236: n->scope = scope;
! 237: add_tail(&i->neighbors, &n->if_n);
! 238: rem_node(&n->n);
! 239: add_tail(&neigh_hash_table[neigh_hash(n->proto, &n->addr)], &n->n);
! 240: DBG("Waking up sticky neighbor %I\n", n->addr);
! 241: if (n->proto->neigh_notify && n->proto->core_state != FS_FLUSHING)
! 242: n->proto->neigh_notify(n);
! 243: }
! 244:
! 245: static void
! 246: neigh_down(neighbor *n)
! 247: {
! 248: DBG("Flushing neighbor %I on %s\n", n->addr, n->iface->name);
! 249: rem_node(&n->if_n);
! 250: if (! (n->flags & NEF_BIND))
! 251: n->iface = NULL;
! 252: n->ifa = NULL;
! 253: n->scope = -1;
! 254: if (n->proto->neigh_notify && n->proto->core_state != FS_FLUSHING)
! 255: n->proto->neigh_notify(n);
! 256: rem_node(&n->n);
! 257: if (n->flags & NEF_STICKY)
! 258: {
! 259: add_tail(&sticky_neigh_list, &n->n);
! 260:
! 261: /* Respawn neighbor if there is another matching prefix */
! 262: struct iface *i;
! 263: struct ifa *a;
! 264: int scope;
! 265:
! 266: if (!n->iface)
! 267: WALK_LIST(i, iface_list)
! 268: if ((scope = if_connected(&n->addr, i, &a)) >= 0)
! 269: {
! 270: neigh_up(n, i, scope, a);
! 271: return;
! 272: }
! 273: }
! 274: else
! 275: sl_free(neigh_slab, n);
! 276: }
! 277:
! 278:
! 279: /**
! 280: * neigh_if_up: notify neighbor cache about interface up event
! 281: * @i: interface in question
! 282: *
! 283: * Tell the neighbor cache that a new interface became up.
! 284: *
! 285: * The neighbor cache wakes up all inactive sticky neighbors with
! 286: * addresses belonging to prefixes of the interface @i.
! 287: */
! 288: void
! 289: neigh_if_up(struct iface *i)
! 290: {
! 291: struct ifa *a;
! 292: neighbor *n, *next;
! 293: int scope;
! 294:
! 295: WALK_LIST_DELSAFE(n, next, sticky_neigh_list)
! 296: if ((!n->iface || n->iface == i) &&
! 297: ((scope = if_connected(&n->addr, i, &a)) >= 0))
! 298: neigh_up(n, i, scope, a);
! 299: }
! 300:
! 301: /**
! 302: * neigh_if_down - notify neighbor cache about interface down event
! 303: * @i: the interface in question
! 304: *
! 305: * Notify the neighbor cache that an interface has ceased to exist.
! 306: *
! 307: * It causes all entries belonging to neighbors connected to this interface
! 308: * to be flushed.
! 309: */
! 310: void
! 311: neigh_if_down(struct iface *i)
! 312: {
! 313: node *x, *y;
! 314:
! 315: WALK_LIST_DELSAFE(x, y, i->neighbors)
! 316: neigh_down(SKIP_BACK(neighbor, if_n, x));
! 317: }
! 318:
! 319: /**
! 320: * neigh_if_link - notify neighbor cache about interface link change
! 321: * @i: the interface in question
! 322: *
! 323: * Notify the neighbor cache that an interface changed link state.
! 324: * All owners of neighbor entries connected to this interface are
! 325: * notified.
! 326: */
! 327: void
! 328: neigh_if_link(struct iface *i)
! 329: {
! 330: node *x, *y;
! 331:
! 332: WALK_LIST_DELSAFE(x, y, i->neighbors)
! 333: {
! 334: neighbor *n = SKIP_BACK(neighbor, if_n, x);
! 335: if (n->proto->neigh_notify && n->proto->core_state != FS_FLUSHING)
! 336: n->proto->neigh_notify(n);
! 337: }
! 338: }
! 339:
! 340: /**
! 341: * neigh_ifa_update: notify neighbor cache about interface address add or remove event
! 342: * @a: interface address in question
! 343: *
! 344: * Tell the neighbor cache that an address was added or removed.
! 345: *
! 346: * The neighbor cache wakes up all inactive sticky neighbors with
! 347: * addresses belonging to prefixes of the interface belonging to @ifa
! 348: * and causes all unreachable neighbors to be flushed.
! 349: */
! 350: void
! 351: neigh_ifa_update(struct ifa *a)
! 352: {
! 353: struct iface *i = a->iface;
! 354: node *x, *y;
! 355:
! 356: /* Remove all neighbors whose scope has changed */
! 357: WALK_LIST_DELSAFE(x, y, i->neighbors)
! 358: {
! 359: struct ifa *aa;
! 360: neighbor *n = SKIP_BACK(neighbor, if_n, x);
! 361: if (if_connected(&n->addr, i, &aa) != n->scope)
! 362: neigh_down(n);
! 363: }
! 364:
! 365: /* Wake up all sticky neighbors that are reachable now */
! 366: neigh_if_up(i);
! 367: }
! 368:
! 369: static inline void
! 370: neigh_prune_one(neighbor *n)
! 371: {
! 372: if (n->proto->proto_state != PS_DOWN)
! 373: return;
! 374: rem_node(&n->n);
! 375: if (n->scope >= 0)
! 376: rem_node(&n->if_n);
! 377: sl_free(neigh_slab, n);
! 378: }
! 379:
! 380: /**
! 381: * neigh_prune - prune neighbor cache
! 382: *
! 383: * neigh_prune() examines all neighbor entries cached and removes those
! 384: * corresponding to inactive protocols. It's called whenever a protocol
! 385: * is shut down to get rid of all its heritage.
! 386: */
! 387: void
! 388: neigh_prune(void)
! 389: {
! 390: neighbor *n;
! 391: node *m;
! 392: int i;
! 393:
! 394: DBG("Pruning neighbors\n");
! 395: for(i=0; i<NEIGH_HASH_SIZE; i++)
! 396: WALK_LIST_DELSAFE(n, m, neigh_hash_table[i])
! 397: neigh_prune_one(n);
! 398: WALK_LIST_DELSAFE(n, m, sticky_neigh_list)
! 399: neigh_prune_one(n);
! 400: }
! 401:
! 402: /**
! 403: * neigh_init - initialize the neighbor cache.
! 404: * @if_pool: resource pool to be used for neighbor entries.
! 405: *
! 406: * This function is called during BIRD startup to initialize
! 407: * the neighbor cache module.
! 408: */
! 409: void
! 410: neigh_init(pool *if_pool)
! 411: {
! 412: int i;
! 413:
! 414: neigh_slab = sl_new(if_pool, sizeof(neighbor));
! 415: init_list(&sticky_neigh_list);
! 416: for(i=0; i<NEIGH_HASH_SIZE; i++)
! 417: init_list(&neigh_hash_table[i]);
! 418: }
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 / bird / nest