nest/neighbor.c

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