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