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.
  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 }