neighbor.c 12.6 KB
Newer Older
1 2 3 4
/*
 *	BIRD -- Neighbor Cache
 *
 *	(c) 1998--2000 Martin Mares <mj@ucw.cz>
5 6
 *	(c) 2008--2018 Ondrej Zajicek <santiago@crfreenet.org>
 *	(c) 2008--2018 CZ.NIC z.s.p.o.
7 8 9 10
 *
 *	Can be freely distributed and used under the terms of the GNU GPL.
 */

Martin Mareš's avatar
Martin Mareš committed
11 12 13 14
/**
 * DOC: Neighbor cache
 *
 * Most routing protocols need to associate their internal state data with
15 16 17 18 19
 * 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.
Martin Mareš's avatar
Martin Mareš committed
20
 *
21 22 23 24 25 26
 * 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 address is set to
 * %SCOPE_HOST) together with per-neighbor data belonging to a single protocol.
 * A neighbor entry may be bound to a specific interface, which is required for
 * link-local IP addresses and optional for global IP addresses.
Martin Mareš's avatar
Martin Mareš committed
27
 *
28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
 * Neighbor cache entries are stored in a hash table, which is indexed by triple
 * (protocol, IP, requested-iface), so if both regular and iface-bound neighbors
 * are requested, they are represented by two neighbor cache entries. Active
 * entries are also linked in per-interface list (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 instead
 * linked in a special list, which is walked whenever an interface changes its
 * state to up. Neighbor entry VRF association is implied by respective
 * protocol.
 *
 * Besides the already mentioned %NEF_STICKY flag, there is also %NEF_ONLINK,
 * which specifies that neighbor should be considered reachable on given iface
 * regardless of associated address ranges, and %NEF_IFACE, which represents
 * pseudo-neighbor entry for whole interface (and uses %IPA_NONE IP address).
Martin Mareš's avatar
Martin Mareš committed
43 44
 *
 * When a neighbor event occurs (a neighbor gets disconnected or a sticky
45 46
 * inactive neighbor becomes connected), the protocol hook neigh_notify() is
 * called to advertise the change.
Martin Mareš's avatar
Martin Mareš committed
47 48
 */

49
#undef LOCAL_DEBUG
50 51 52 53

#include "nest/bird.h"
#include "nest/iface.h"
#include "nest/protocol.h"
54
#include "lib/hash.h"
55 56 57
#include "lib/resource.h"

#define NEIGH_HASH_SIZE 256
58
#define NEIGH_HASH_OFFSET 24
59 60

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

Pavel Tvrdík's avatar
Pavel Tvrdík committed
63
static inline uint
64
neigh_hash(struct proto *p, ip_addr a, struct iface *i)
65
{
66
  return (p->hash_key ^ ipa_hash(a) ^ ptr_hash(i)) >> NEIGH_HASH_OFFSET;
67 68
}

69
static int
70
if_connected(ip_addr a, struct iface *i, struct ifa **ap, uint flags)
71 72 73
{
  struct ifa *b;

74 75 76 77 78 79 80 81 82 83
  /* Handle iface pseudo-neighbors */
  if (flags & NEF_IFACE)
    return *ap = NULL, (i->flags & IF_UP) ? SCOPE_HOST : -1;

  /* Host addresses match even if iface is down */
  WALK_LIST(b, i->addrs)
    if (ipa_equal(a, b->ip))
      return *ap = b, SCOPE_HOST;

  /* Rest do not match if iface is down */
84
  if (!(i->flags & IF_UP))
85
    return *ap = NULL, -1;
86

87
  /* Regular neighbors */
88
  WALK_LIST(b, i->addrs)
89 90
  {
    if (b->flags & IA_PEER)
91
    {
92 93 94 95 96 97 98 99 100 101 102 103 104 105 106
      if (ipa_equal(a, b->opposite))
	return *ap = b, b->scope;
    }
    else
    {
      if (ipa_in_netX(a, &b->prefix))
      {
	/* Do not allow IPv4 network and broadcast addresses */
	if (ipa_is_ip4(a) &&
	    (net_pxlen(&b->prefix) < (IP4_MAX_PREFIX_LENGTH - 1)) &&
	    (ipa_equal(a, net_prefix(&b->prefix)) ||	/* Network address */
	     ipa_equal(a, b->brd)))			/* Broadcast */
	  return *ap = NULL, -1;

	return *ap = b, b->scope;
107
      }
108 109 110 111 112 113
    }
  }

  /* Handle ONLINK flag */
  if (flags & NEF_ONLINK)
    return *ap = NULL, ipa_classify(a) & IADDR_SCOPE_MASK;
114

115
  return *ap = NULL, -1;
116 117
}

118 119
static inline int
if_connected_any(ip_addr a, struct iface *vrf, struct iface **iface, struct ifa **addr, uint flags)
120
{
121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136
  struct iface *i;
  struct ifa *b;
  int s, scope = -1;

  *iface = NULL;
  *addr = NULL;

  /* Get first match, but prefer SCOPE_HOST to other matches */
  WALK_LIST(i, iface_list)
    if ((!vrf || vrf == i->master) && ((s = if_connected(a, i, &b, flags)) >= 0))
      if ((scope < 0) || ((scope > SCOPE_HOST) && (s == SCOPE_HOST)))
      {
	*iface = i;
	*addr = b;
	scope = s;
      }
137

138 139
  return scope;
}
140

141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156
/**
 * neigh_find - find or create a neighbor entry
 * @p: protocol which asks for the entry
 * @a: IP address of the node to be searched for
 * @iface: optionally bound neighbor to this iface (may be NULL)
 * @flags: %NEF_STICKY for sticky entry, %NEF_ONLINK for onlink entry
 *
 * Search the neighbor cache for a node with given IP address. Iface can be
 * specified for link-local addresses or for cases, where neighbor is expected
 * on given interface. If it is 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.
 */
157
neighbor *
158
neigh_find(struct proto *p, ip_addr a, struct iface *iface, uint flags)
159 160
{
  neighbor *n;
161
  int class, scope = -1;
162 163 164
  uint h = neigh_hash(p, a, iface);
  struct iface *ifreq = iface;
  struct ifa *addr = NULL;
165 166

  WALK_LIST(n, neigh_hash_table[h])	/* Search the cache */
167
    if ((n->proto == p) && ipa_equal(n->addr, a) && (n->ifreq == iface))
168 169
      return n;

170 171 172 173 174 175 176 177 178 179 180 181 182 183 184
  if (flags & NEF_IFACE)
  {
    if (ipa_nonzero(a) || !iface)
      return NULL;
  }
  else
  {
    class = ipa_classify(a);
    if (class < 0)			/* Invalid address */
      return NULL;
    if (((class & IADDR_SCOPE_MASK) == SCOPE_HOST) ||
	(((class & IADDR_SCOPE_MASK) == SCOPE_LINK) && !iface) ||
	!(class & IADDR_HOST))
      return NULL;			/* Bad scope or a somecast */
  }
185

186 187
  if ((flags & NEF_ONLINK) && !iface)
      return NULL;
188

189 190 191 192 193
  if (iface)
  {
    scope = if_connected(a, iface, &addr, flags);
    iface = (scope < 0) ? NULL : iface;
  }
194
  else
195
    scope = if_connected_any(a, p->vrf, &iface, &addr, flags);
196

197
  /* scope < 0 means i don't know neighbor */
198
  /* scope >= 0  <=>  iface != NULL */
199 200

  if ((scope < 0) && !(flags & NEF_STICKY))
201 202 203
    return NULL;

  n = sl_alloc(neigh_slab);
204 205
  memset(n, 0, sizeof(neighbor));

206 207 208
  add_tail(&neigh_hash_table[h], &n->n);
  add_tail((scope >= 0) ? &iface->neighbors : &sticky_neigh_list, &n->if_n);
  n->addr = a;
209
  n->ifa = addr;
210 211
  n->iface = iface;
  n->ifreq = ifreq;
212 213
  n->proto = p;
  n->flags = flags;
214
  n->scope = scope;
215 216 217 218

  return n;
}

Martin Mareš's avatar
Martin Mareš committed
219 220 221 222
/**
 * neigh_dump - dump specified neighbor entry.
 * @n: the entry to dump
 *
223
 * This functions dumps the contents of a given neighbor entry to debug output.
Martin Mareš's avatar
Martin Mareš committed
224
 */
225 226 227
void
neigh_dump(neighbor *n)
{
228 229 230
  debug("%p %I %s %s ", n, n->addr,
	n->iface ? n->iface->name : "[]",
	n->ifreq ? n->ifreq->name : "[]");
231
  debug("%s %p %08x scope %s", n->proto->name, n->data, n->aux, ip_scope_text(n->scope));
232 233
  if (n->flags & NEF_STICKY)
    debug(" STICKY");
234 235
  if (n->flags & NEF_ONLINK)
    debug(" ONLINK");
236 237 238
  debug("\n");
}

Martin Mareš's avatar
Martin Mareš committed
239 240 241
/**
 * neigh_dump_all - dump all neighbor entries.
 *
242
 * This function dumps the contents of the neighbor cache to debug output.
Martin Mareš's avatar
Martin Mareš committed
243
 */
244 245 246 247 248 249 250 251
void
neigh_dump_all(void)
{
  neighbor *n;
  int i;

  debug("Known neighbors:\n");
  for(i=0; i<NEIGH_HASH_SIZE; i++)
252 253
    WALK_LIST(n, neigh_hash_table[i])
      neigh_dump(n);
254 255 256
  debug("\n");
}

257 258 259 260 261 262 263
static inline void
neigh_notify(neighbor *n)
{
  if (n->proto->neigh_notify && (n->proto->proto_state != PS_STOP))
    n->proto->neigh_notify(n);
}

264
static void
265
neigh_up(neighbor *n, struct iface *i, struct ifa *a, int scope)
266
{
267
  DBG("Waking up sticky neighbor %I\n", n->addr);
268
  n->iface = i;
269
  n->ifa = a;
270
  n->scope = scope;
271

272 273
  rem_node(&n->if_n);
  add_tail(&i->neighbors, &n->if_n);
274

275
  neigh_notify(n);
276 277 278 279 280
}

static void
neigh_down(neighbor *n)
{
281
  DBG("Flushing neighbor %I on %s\n", n->addr, n->iface->name);
282
  n->iface = NULL;
283
  n->ifa = NULL;
284
  n->scope = -1;
285

286 287
  rem_node(&n->if_n);
  add_tail(&sticky_neigh_list, &n->if_n);
288

289 290
  neigh_notify(n);
}
291

292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332
static inline void
neigh_free(neighbor *n)
{
  rem_node(&n->n);
  rem_node(&n->if_n);
  sl_free(neigh_slab, n);
}

/**
 * neigh_update: update neighbor entry w.r.t. change on specific iface
 * @n: neighbor to update
 * @iface: changed iface
 *
 * The function recalculates state of the neighbor entry @n assuming that only
 * the interface @iface may changed its state or addresses. Then, appropriate
 * actions are executed (the neighbor goes up, down, up-down, or just notified).
 */
void
neigh_update(neighbor *n, struct iface *iface)
{
  struct ifa *ifa = NULL;
  int scope = -1;

  /* Iface-bound neighbors ignore other ifaces */
  if (n->ifreq && (n->ifreq != iface))
    return;

  /* VRF-bound neighbors ignore changes in other VRFs */
  if (n->proto->vrf && (n->proto->vrf != iface->master))
    return;

  scope = if_connected(n->addr, iface, &ifa, n->flags);

  /* When neighbor is going down, try to respawn it on other ifaces */
  if ((scope < 0) && (n->scope >= 0) && !n->ifreq && (n->flags & NEF_STICKY))
    scope = if_connected_any(n->addr, n->proto->vrf, &iface, &ifa, n->flags);

  /* No change or minor change - ignore or notify */
  if ((scope == n->scope) && (iface == n->iface))
  {
    if (ifa != n->ifa)
333
    {
334 335
      n->ifa = ifa;
      neigh_notify(n);
336
    }
337

338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353
    return;
  }

  /* Major change - going down and/or going up */

  if (n->scope >= 0)
    neigh_down(n);

  if ((n->scope < 0) && !(n->flags & NEF_STICKY))
  {
    neigh_free(n);
    return;
  }

  if (scope >= 0)
    neigh_up(n, iface, ifa, scope);
354 355 356
}


Martin Mareš's avatar
Martin Mareš committed
357 358 359 360 361 362 363 364 365
/**
 * 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.
 */
366 367 368
void
neigh_if_up(struct iface *i)
{
369 370
  neighbor *n;
  node *x, *y;
371

372 373
  WALK_LIST2_DELSAFE(n, x, y, sticky_neigh_list, if_n)
    neigh_update(n, i);
374 375
}

Martin Mareš's avatar
Martin Mareš committed
376 377 378 379 380 381
/**
 * 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.
 *
382
 * It causes all neighbors connected to this interface to be updated or removed.
Martin Mareš's avatar
Martin Mareš committed
383
 */
384 385 386
void
neigh_if_down(struct iface *i)
{
387
  neighbor *n;
388 389
  node *x, *y;

390
  WALK_LIST2_DELSAFE(n, x, y, i->neighbors, if_n)
391
    neigh_update(n, i);
392 393
}

394 395 396 397
/**
 * neigh_if_link - notify neighbor cache about interface link change
 * @i: the interface in question
 *
398 399
 * Notify the neighbor cache that an interface changed link state. All owners of
 * neighbor entries connected to this interface are notified.
400 401 402 403
 */
void
neigh_if_link(struct iface *i)
{
404
  neighbor *n;
405 406
  node *x, *y;

407
  WALK_LIST2_DELSAFE(n, x, y, i->neighbors, if_n)
408
    neigh_notify(n);
409 410
}

411 412
/**
 * neigh_ifa_update: notify neighbor cache about interface address add or remove event
413
 * @a: interface address in question
414 415 416 417 418 419 420 421 422 423 424
 *
 * 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;
425
  neighbor *n;
426
  node *x, *y;
427

428
  /* Update all neighbors whose scope has changed */
429
  WALK_LIST2_DELSAFE(n, x, y, i->neighbors, if_n)
430
    neigh_update(n, i);
431 432

  /* Wake up all sticky neighbors that are reachable now */
433 434
  WALK_LIST2_DELSAFE(n, x, y, sticky_neigh_list, if_n)
    neigh_update(n, i);
435 436
}

437 438 439
static inline void
neigh_prune_one(neighbor *n)
{
440
  if (n->proto->proto_state != PS_DOWN)
441
    return;
442 443

  neigh_free(n);
444 445
}

Martin Mareš's avatar
Martin Mareš committed
446 447 448 449 450 451 452
/**
 * 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.
 */
453 454 455 456 457 458 459 460 461 462
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])
463
      neigh_prune_one(n);
464 465
}

Martin Mareš's avatar
Martin Mareš committed
466 467 468 469 470 471 472
/**
 * 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.
 */
473 474 475 476
void
neigh_init(pool *if_pool)
{
  neigh_slab = sl_new(if_pool, sizeof(neighbor));
477 478

  for(int i = 0; i < NEIGH_HASH_SIZE; i++)
479
    init_list(&neigh_hash_table[i]);
480 481

  init_list(&sticky_neigh_list);
482
}