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_UNNUMBERED)
  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               if (ipa_equal(*a, b->prefix) ||   /* Network address */
  79                   ipa_equal(*a, b->brd))        /* Broadcast */
  80                 return -1;
  81               return b->scope;
  82             }
  83         }
  84       }
  85   return -1;
  86 }
  87
  88 /**
  89  * neigh_find - find or create a neighbor entry.
  90  * @p: protocol which asks for the entry.
  91  * @a: pointer to IP address of the node to be searched for.
  92  * @flags: 0 or %NEF_STICKY if you want to create a sticky entry.
  93  *
  94  * Search the neighbor cache for a node with given IP address. If
  95  * it's found, a pointer to the neighbor entry is returned. If no
  96  * such entry exists and the node is directly connected on
  97  * one of our active interfaces, a new entry is created and returned
  98  * to the caller with protocol-dependent fields initialized to zero.
  99  * If the node is not connected directly or *@a is not a valid unicast
 100  * IP address, neigh_find() returns %NULL.
 101  */
 102
 103 neighbor *
 104 neigh_find(struct proto *p, ip_addr *a, unsigned flags)
 105 {
 106   neighbor *n;
 107   int class, scope = SCOPE_HOST;
 108   unsigned int h = neigh_hash(p, a);
 109   struct iface *i, *j;
 110
 111   WALK_LIST(n, neigh_hash_table[h])     /* Search the cache */
 112     if (n->proto == p && ipa_equal(*a, n->addr))
 113       return n;
 114
 115   class = ipa_classify(*a);
 116   if (class < 0)                        /* Invalid address */
 117     return NULL;
 118   if ((class & IADDR_SCOPE_MASK) < SCOPE_SITE ||
 119       !(class & IADDR_HOST))
 120     return NULL;                        /* Bad scope or a somecast */
 121
 122   j = NULL;
 123   WALK_LIST(i, iface_list)
 124     if ((scope = if_connected(a, i)) >= 0)
 125       {
 126         j = i;
 127         break;
 128       }
 129   if (!j && !(flags & NEF_STICKY))
 130     return NULL;
 131
 132   n = sl_alloc(neigh_slab);
 133   n->addr = *a;
 134   n->iface = j;
 135   if (j)
 136     {
 137       add_tail(&neigh_hash_table[h], &n->n);
 138       add_tail(&j->neighbors, &n->if_n);
 139     }
 140   else
 141     {
 142       add_tail(&sticky_neigh_list, &n->n);
 143       scope = 0;
 144     }
 145   n->proto = p;
 146   n->data = NULL;
 147   n->aux = 0;
 148   n->flags = flags;
 149   n->scope = scope;
 150   return n;
 151 }
 152
 153 /**
 154  * neigh_dump - dump specified neighbor entry.
 155  * @n: the entry to dump
 156  *
 157  * This functions dumps the contents of a given neighbor entry
 158  * to debug output.
 159  */
 160 void
 161 neigh_dump(neighbor *n)
 162 {
 163   debug("%p %I ", n, n->addr);
 164   if (n->iface)
 165     debug("%s ", n->iface->name);
 166   else
 167     debug("[] ");
 168   debug("%s %p %08x scope %s", n->proto->name, n->data, n->aux, ip_scope_text(n->scope));
 169   if (n->flags & NEF_STICKY)
 170     debug(" STICKY");
 171   debug("\n");
 172 }
 173
 174 /**
 175  * neigh_dump_all - dump all neighbor entries.
 176  *
 177  * This function dumps the contents of the neighbor cache to
 178  * debug output.
 179  */
 180 void
 181 neigh_dump_all(void)
 182 {
 183   neighbor *n;
 184   int i;
 185
 186   debug("Known neighbors:\n");
 187   WALK_LIST(n, sticky_neigh_list)
 188     neigh_dump(n);
 189   for(i=0; i<NEIGH_HASH_SIZE; i++)
 190     WALK_LIST(n, neigh_hash_table[i])
 191       neigh_dump(n);
 192   debug("\n");
 193 }
 194
 195 /**
 196  * neigh_if_up: notify neighbor cache about interface up event
 197  * @i: interface in question
 198  *
 199  * Tell the neighbor cache that a new interface became up.
 200  *
 201  * The neighbor cache wakes up all inactive sticky neighbors with
 202  * addresses belonging to prefixes of the interface @i.
 203  */
 204 void
 205 neigh_if_up(struct iface *i)
 206 {
 207   neighbor *n, *next;
 208   int scope;
 209
 210   WALK_LIST_DELSAFE(n, next, sticky_neigh_list)
 211     if ((scope = if_connected(&n->addr, i)) >= 0)
 212       {
 213         n->iface = i;
 214         n->scope = scope;
 215         add_tail(&i->neighbors, &n->if_n);
 216         rem_node(&n->n);
 217         add_tail(&neigh_hash_table[neigh_hash(n->proto, &n->addr)], &n->n);
 218         DBG("Waking up sticky neighbor %I\n", n->addr);
 219         if (n->proto->neigh_notify && n->proto->core_state != FS_FLUSHING)
 220           n->proto->neigh_notify(n);
 221       }
 222 }
 223
 224 /**
 225  * neigh_if_down - notify neighbor cache about interface down event
 226  * @i: the interface in question
 227  *
 228  * Notify the neighbor cache that an interface has ceased to exist.
 229  *
 230  * It causes all entries belonging to neighbors connected to this interface
 231  * to be flushed.
 232  */
 233 void
 234 neigh_if_down(struct iface *i)
 235 {
 236   node *x, *y;
 237
 238   WALK_LIST_DELSAFE(x, y, i->neighbors)
 239     {
 240       neighbor *n = SKIP_BACK(neighbor, if_n, x);
 241       DBG("Flushing neighbor %I on %s\n", n->addr, i->name);
 242       rem_node(&n->if_n);
 243       n->iface = NULL;
 244       if (n->proto->neigh_notify && n->proto->core_state != FS_FLUSHING)
 245         n->proto->neigh_notify(n);
 246       rem_node(&n->n);
 247       if (n->flags & NEF_STICKY)
 248         add_tail(&sticky_neigh_list, &n->n);
 249       else
 250         sl_free(neigh_slab, n);
 251     }
 252 }
 253
 254 static inline void
 255 neigh_prune_one(neighbor *n)
 256 {
 257   if (n->proto->proto_state != PS_DOWN)
 258     return;
 259   rem_node(&n->n);
 260   if (n->iface)
 261     rem_node(&n->if_n);
 262   sl_free(neigh_slab, n);
 263 }
 264
 265 /**
 266  * neigh_prune - prune neighbor cache
 267  *
 268  * neigh_prune() examines all neighbor entries cached and removes those
 269  * corresponding to inactive protocols. It's called whenever a protocol
 270  * is shut down to get rid of all its heritage.
 271  */
 272 void
 273 neigh_prune(void)
 274 {
 275   neighbor *n;
 276   node *m;
 277   int i;
 278
 279   DBG("Pruning neighbors\n");
 280   for(i=0; i<NEIGH_HASH_SIZE; i++)
 281     WALK_LIST_DELSAFE(n, m, neigh_hash_table[i])
 282       neigh_prune_one(n);
 283   WALK_LIST_DELSAFE(n, m, sticky_neigh_list)
 284     neigh_prune_one(n);
 285 }
 286
 287 /**
 288  * neigh_init - initialize the neighbor cache.
 289  * @if_pool: resource pool to be used for neighbor entries.
 290  *
 291  * This function is called during BIRD startup to initialize
 292  * the neighbor cache module.
 293  */
 294 void
 295 neigh_init(pool *if_pool)
 296 {
 297   int i;
 298
 299   neigh_slab = sl_new(if_pool, sizeof(neighbor));
 300   init_list(&sticky_neigh_list);
 301   for(i=0; i<NEIGH_HASH_SIZE; i++)
 302     init_list(&neigh_hash_table[i]);
 303 }