neighbor.c 10.3 KB
Newer Older
1 2 3 4 5 6 7 8
/*
 *	BIRD -- Neighbor Cache
 *
 *	(c) 1998--2000 Martin Mares <mj@ucw.cz>
 *
 *	Can be freely distributed and used under the terms of the GNU GPL.
 */

Martin Mareš's avatar
Martin Mareš committed
9 10 11 12 13 14 15 16 17 18 19 20 21 22
/**
 * DOC: Neighbor cache
 *
 * Most routing protocols need to associate their internal state data with
 * neighboring routers, check whether an address given as the next hop
 * attribute of a route is really an address of a directly connected host
 * and which interface is it connected through. Also, they often need to
 * be notified when a neighbor ceases to exist or when their long awaited
 * neighbor becomes connected. The neighbor cache is there to solve all
 * these problems.
 *
 * The neighbor cache maintains a collection of neighbor entries. Each
 * entry represents one IP address corresponding to either our directly
 * connected neighbor or our own end of the link (when the scope of the
Martin Mareš's avatar
Martin Mareš committed
23
 * address is set to %SCOPE_HOST) together with per-neighbor data belonging to a
Martin Mareš's avatar
Martin Mareš committed
24 25 26
 * single protocol.
 *
 * Active entries represent known neighbors and are stored in a hash
Martin Mareš's avatar
Martin Mareš committed
27
 * table (to allow fast retrieval based on the IP address of the node) and
Martin Mareš's avatar
Martin Mareš committed
28 29 30 31 32
 * two linked lists: one global and one per-interface (allowing quick
 * processing of interface change events). Inactive entries exist only
 * when the protocol has explicitly requested it via the %NEF_STICKY
 * flag because it wishes to be notified when the node will again become
 * a neighbor. Such entries are enqueued in a special list which is walked
33 34
 * whenever an interface changes its state to up. Neighbor entry VRF
 * association is implied by respective protocol.
Martin Mareš's avatar
Martin Mareš committed
35 36 37 38 39 40
 *
 * When a neighbor event occurs (a neighbor gets disconnected or a sticky
 * inactive neighbor becomes connected), the protocol hook neigh_notify()
 * is called to advertise the change.
 */

41
#undef LOCAL_DEBUG
42 43 44 45 46 47 48 49 50 51 52

#include "nest/bird.h"
#include "nest/iface.h"
#include "nest/protocol.h"
#include "lib/resource.h"

#define NEIGH_HASH_SIZE 256

static slab *neigh_slab;
static list sticky_neigh_list, neigh_hash_table[NEIGH_HASH_SIZE];

Pavel Tvrdík's avatar
Pavel Tvrdík committed
53
static inline uint
54 55 56 57 58
neigh_hash(struct proto *p, ip_addr *a)
{
  return (p->hash_key ^ ipa_hash(*a)) & (NEIGH_HASH_SIZE-1);
}

59
static int
60
if_connected(ip_addr *a, struct iface *i, struct ifa **ap)
61 62 63 64
{
  struct ifa *b;

  if (!(i->flags & IF_UP))
65 66
  {
    *ap = NULL;
67
    return -1;
68 69
  }

70 71
  WALK_LIST(b, i->addrs)
    {
72 73
      *ap = b;

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 82 83 84
	}
      else
	{
	  if (ipa_in_net(*a, b->prefix, b->pxlen))
	    {
85 86 87 88
#ifndef IPV6
	      if ((b->pxlen < (BITS_PER_IP_ADDRESS - 1)) &&
		  (ipa_equal(*a, b->prefix) ||	/* Network address */
		   ipa_equal(*a, b->brd)))	/* Broadcast */
89 90
	      {
		*ap = NULL;
91
		return -1;
92
	      }
93 94
#endif

95
	      return b->scope;
96 97 98
	    }
	}
      }
99 100

  *ap = NULL;
101
  return -1;
102 103
}

Martin Mareš's avatar
Martin Mareš committed
104 105 106 107 108 109 110 111 112 113 114 115 116 117
/**
 * neigh_find - find or create a neighbor entry.
 * @p: protocol which asks for the entry.
 * @a: pointer to IP address of the node to be searched for.
 * @flags: 0 or %NEF_STICKY if you want to create a sticky entry.
 *
 * Search the neighbor cache for a node with given IP address. If
 * it's found, a pointer to the neighbor entry is returned. If no
 * such entry exists and the node is directly connected on
 * one of our active interfaces, a new entry is created and returned
 * to the caller with protocol-dependent fields initialized to zero.
 * If the node is not connected directly or *@a is not a valid unicast
 * IP address, neigh_find() returns %NULL.
 */
118 119
neighbor *
neigh_find(struct proto *p, ip_addr *a, unsigned flags)
120 121 122
{
  return neigh_find2(p, a, NULL, flags);
}
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;
Pavel Tvrdík's avatar
Pavel Tvrdík committed
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 137 138 139 140
      return n;

  class = ipa_classify(*a);
  if (class < 0)			/* Invalid address */
    return NULL;
141 142
  if (((class & IADDR_SCOPE_MASK) == SCOPE_HOST) ||
      (((class & IADDR_SCOPE_MASK) == SCOPE_LINK) && (ifa == NULL)) ||
143 144 145
      !(class & IADDR_HOST))
    return NULL;			/* Bad scope or a somecast */

146
  if (ifa)
147
    {
148
      scope = if_connected(a, ifa, &addr);
149
      flags |= NEF_BIND;
150 151 152 153

      if ((scope < 0) && (flags & NEF_ONLINK))
	scope = class & IADDR_SCOPE_MASK;
    }
154 155
  else
    WALK_LIST(i, iface_list)
156 157 158
      if ((!p->vrf || p->vrf == i->master) &&
	  ((scope = if_connected(a, i, &addr)) >= 0))
        {
159 160 161 162
	  ifa = i;
	  break;
	}

163 164 165 166
  /* scope < 0 means i don't know neighbor */
  /* scope >= 0 implies ifa != NULL */

  if ((scope < 0) && !(flags & NEF_STICKY))
167 168 169 170
    return NULL;

  n = sl_alloc(neigh_slab);
  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 184 185 186
  n->proto = p;
  n->data = NULL;
  n->aux = 0;
  n->flags = flags;
187
  n->scope = scope;
188 189 190
  return n;
}

Martin Mareš's avatar
Martin Mareš committed
191 192 193 194 195 196 197
/**
 * neigh_dump - dump specified neighbor entry.
 * @n: the entry to dump
 *
 * This functions dumps the contents of a given neighbor entry
 * to debug output.
 */
198 199 200 201 202 203 204 205
void
neigh_dump(neighbor *n)
{
  debug("%p %I ", n, n->addr);
  if (n->iface)
    debug("%s ", n->iface->name);
  else
    debug("[] ");
206
  debug("%s %p %08x scope %s", n->proto->name, n->data, n->aux, ip_scope_text(n->scope));
207 208 209 210 211
  if (n->flags & NEF_STICKY)
    debug(" STICKY");
  debug("\n");
}

Martin Mareš's avatar
Martin Mareš committed
212 213 214 215 216 217
/**
 * neigh_dump_all - dump all neighbor entries.
 *
 * This function dumps the contents of the neighbor cache to
 * debug output.
 */
218 219 220 221 222 223 224 225 226 227
void
neigh_dump_all(void)
{
  neighbor *n;
  int i;

  debug("Known neighbors:\n");
  WALK_LIST(n, sticky_neigh_list)
    neigh_dump(n);
  for(i=0; i<NEIGH_HASH_SIZE; i++)
228 229
    WALK_LIST(n, neigh_hash_table[i])
      neigh_dump(n);
230 231 232
  debug("\n");
}

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 239 240 241 242 243 244 245 246 247 248 249
  n->scope = scope;
  add_tail(&i->neighbors, &n->if_n);
  rem_node(&n->n);
  add_tail(&neigh_hash_table[neigh_hash(n->proto, &n->addr)], &n->n);
  DBG("Waking up sticky neighbor %I\n", n->addr);
  if (n->proto->neigh_notify && n->proto->core_state != FS_FLUSHING)
    n->proto->neigh_notify(n);
}

static void
neigh_down(neighbor *n)
{
250
  DBG("Flushing neighbor %I on %s\n", n->addr, n->iface->name);
251
  rem_node(&n->if_n);
252 253
  if (! (n->flags & NEF_BIND))
    n->iface = NULL;
254
  n->ifa = NULL;
255
  n->scope = -1;
256 257 258 259
  if (n->proto->neigh_notify && n->proto->core_state != FS_FLUSHING)
    n->proto->neigh_notify(n);
  rem_node(&n->n);
  if (n->flags & NEF_STICKY)
260 261 262 263 264
    {
      add_tail(&sticky_neigh_list, &n->n);

      /* Respawn neighbor if there is another matching prefix */
      struct iface *i;
265
      struct ifa *a;
266 267 268 269
      int scope;

      if (!n->iface)
	WALK_LIST(i, iface_list)
270
	  if ((scope = if_connected(&n->addr, i, &a)) >= 0)
271
	    {
272
	      neigh_up(n, i, scope, a);
273 274 275
	      return;
	    }
    }
276 277 278 279 280
  else
    sl_free(neigh_slab, n);
}


Martin Mareš's avatar
Martin Mareš committed
281 282 283 284 285 286 287 288 289
/**
 * neigh_if_up: notify neighbor cache about interface up event
 * @i: interface in question
 *
 * Tell the neighbor cache that a new interface became up.
 *
 * The neighbor cache wakes up all inactive sticky neighbors with
 * addresses belonging to prefixes of the interface @i.
 */
290 291 292
void
neigh_if_up(struct iface *i)
{
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 300
	((scope = if_connected(&n->addr, i, &a)) >= 0))
      neigh_up(n, i, scope, a);
301 302
}

Martin Mareš's avatar
Martin Mareš committed
303 304 305 306 307 308 309 310 311
/**
 * neigh_if_down - notify neighbor cache about interface down event
 * @i: the interface in question
 *
 * Notify the neighbor cache that an interface has ceased to exist.
 *
 * It causes all entries belonging to neighbors connected to this interface
 * to be flushed.
 */
312 313 314 315 316 317
void
neigh_if_down(struct iface *i)
{
  node *x, *y;

  WALK_LIST_DELSAFE(x, y, i->neighbors)
318
    neigh_down(SKIP_BACK(neighbor, if_n, x));
319 320
}

321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341
/**
 * neigh_if_link - notify neighbor cache about interface link change
 * @i: the interface in question
 *
 * Notify the neighbor cache that an interface changed link state.
 * All owners of neighbor entries connected to this interface are
 * notified.
 */
void
neigh_if_link(struct iface *i)
{
  node *x, *y;

  WALK_LIST_DELSAFE(x, y, i->neighbors)
    {
      neighbor *n = SKIP_BACK(neighbor, if_n, x);
      if (n->proto->neigh_notify && n->proto->core_state != FS_FLUSHING)
	n->proto->neigh_notify(n);
    }
}

342 343
/**
 * neigh_ifa_update: notify neighbor cache about interface address add or remove event
344
 * @a: interface address in question
345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360
 *
 * Tell the neighbor cache that an address was added or removed.
 *
 * The neighbor cache wakes up all inactive sticky neighbors with
 * addresses belonging to prefixes of the interface belonging to @ifa
 * and causes all unreachable neighbors to be flushed.
 */
void
neigh_ifa_update(struct ifa *a)
{
  struct iface *i = a->iface;
  node *x, *y;
 
  /* Remove all neighbors whose scope has changed */
  WALK_LIST_DELSAFE(x, y, i->neighbors)
    {
361
      struct ifa *aa;
362
      neighbor *n = SKIP_BACK(neighbor, if_n, x);
363
      if (if_connected(&n->addr, i, &aa) != n->scope)
364 365 366 367 368 369 370
	neigh_down(n);
    }

  /* Wake up all sticky neighbors that are reachable now */
  neigh_if_up(i);
}

371 372 373
static inline void
neigh_prune_one(neighbor *n)
{
374
  if (n->proto->proto_state != PS_DOWN)
375 376
    return;
  rem_node(&n->n);
377
  if (n->scope >= 0)
378 379 380 381
    rem_node(&n->if_n);
  sl_free(neigh_slab, n);
}

Martin Mareš's avatar
Martin Mareš committed
382 383 384 385 386 387 388
/**
 * neigh_prune - prune neighbor cache
 *
 * neigh_prune() examines all neighbor entries cached and removes those
 * corresponding to inactive protocols. It's called whenever a protocol
 * is shut down to get rid of all its heritage.
 */
389 390 391 392 393 394 395 396 397 398
void
neigh_prune(void)
{
  neighbor *n;
  node *m;
  int i;

  DBG("Pruning neighbors\n");
  for(i=0; i<NEIGH_HASH_SIZE; i++)
    WALK_LIST_DELSAFE(n, m, neigh_hash_table[i])
399 400 401
      neigh_prune_one(n);
  WALK_LIST_DELSAFE(n, m, sticky_neigh_list)
    neigh_prune_one(n);
402 403
}

Martin Mareš's avatar
Martin Mareš committed
404 405 406 407 408 409 410
/**
 * neigh_init - initialize the neighbor cache.
 * @if_pool: resource pool to be used for neighbor entries.
 *
 * This function is called during BIRD startup to initialize
 * the neighbor cache module.
 */
411 412 413 414 415 416 417 418 419 420
void
neigh_init(pool *if_pool)
{
  int i;

  neigh_slab = sl_new(if_pool, sizeof(neighbor));
  init_list(&sticky_neigh_list);
  for(i=0; i<NEIGH_HASH_SIZE; i++)
    init_list(&neigh_hash_table[i]);
}