neighbor.c 14.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 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90
static inline int
ifa_better(struct ifa *a, struct ifa *b)
{
  return a && (!b || (a->prefix.pxlen > b->prefix.pxlen));
}

static inline int
scope_better(int sa, int sb)
{
  /* Order per preference: -1 unknown, 0 for remote, 1 for local */
  sa = (sa < 0) ? sa : !sa;
  sb = (sb < 0) ? sb : !sb;

  return sa > sb;
}

static inline int
scope_remote(int sa, int sb)
{
  return (sa > SCOPE_HOST) && (sb > SCOPE_HOST);
}

91
static int
92
if_connected(ip_addr a, struct iface *i, struct ifa **ap, uint flags)
93
{
94
  struct ifa *b, *addr = NULL;
95

96 97 98 99 100 101 102 103 104 105
  /* 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 */
106
  if (!(i->flags & IF_UP))
107
    return *ap = NULL, -1;
108

109
  /* Regular neighbors */
110
  WALK_LIST(b, i->addrs)
111 112
  {
    if (b->flags & IA_PEER)
113
    {
114 115
      if (ipa_equal(a, b->opposite) && ifa_better(b, addr))
	addr = b;
116 117 118
    }
    else
    {
119
      if (ipa_in_netX(a, &b->prefix) && ifa_better(b, addr))
120 121 122 123 124 125 126 127
      {
	/* 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;

128
	addr = b;
129
      }
130 131 132
    }
  }

133 134 135 136
  /* Return found address */
  if (addr)
    return *ap = addr, addr->scope;

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

141
  return *ap = NULL, -1;
142 143
}

144
static inline int
145
if_connected_any(ip_addr a, struct iface *vrf, uint vrf_set, struct iface **iface, struct ifa **addr, uint flags)
146
{
147 148 149 150 151 152 153
  struct iface *i;
  struct ifa *b;
  int s, scope = -1;

  *iface = NULL;
  *addr = NULL;

154
  /* Prefer SCOPE_HOST or longer prefix */
155
  WALK_LIST(i, iface_list)
156
    if ((!vrf_set || vrf == i->master) && ((s = if_connected(a, i, &b, flags)) >= 0))
157
      if (scope_better(s, scope) || (scope_remote(s, scope) && ifa_better(b, *addr)))
158 159 160 161 162
      {
	*iface = i;
	*addr = b;
	scope = s;
      }
163

164 165
  return scope;
}
166

167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193
/* Is ifa @a subnet of any ifa on iface @ib ? */
static inline int
ifa_intersect(struct ifa *a, struct iface *ib)
{
  struct ifa *b;

  WALK_LIST(b, ib->addrs)
    if (net_in_netX(&a->prefix, &b->prefix))
      return 1;

  return 0;
}

/* Is any ifa of iface @ia subnet of any ifa on iface @ib ? */
static inline int
if_intersect(struct iface *ia, struct iface *ib)
{
  struct ifa *a, *b;

  WALK_LIST(a, ia->addrs)
    WALK_LIST(b, ib->addrs)
    if (net_in_netX(&a->prefix, &b->prefix))
      return 1;

  return 0;
}

194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209
/**
 * 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.
 */
210
neighbor *
211
neigh_find(struct proto *p, ip_addr a, struct iface *iface, uint flags)
212 213
{
  neighbor *n;
214
  int class, scope = -1;
215 216 217
  uint h = neigh_hash(p, a, iface);
  struct iface *ifreq = iface;
  struct ifa *addr = NULL;
218 219

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

223 224 225 226 227 228 229 230 231 232 233 234 235 236 237
  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 */
  }
238

239 240
  if ((flags & NEF_ONLINK) && !iface)
      return NULL;
241

242 243 244 245 246
  if (iface)
  {
    scope = if_connected(a, iface, &addr, flags);
    iface = (scope < 0) ? NULL : iface;
  }
247
  else
248
    scope = if_connected_any(a, p->vrf, p->vrf_set, &iface, &addr, flags);
249

250
  /* scope < 0 means i don't know neighbor */
251
  /* scope >= 0  <=>  iface != NULL */
252 253

  if ((scope < 0) && !(flags & NEF_STICKY))
254 255 256
    return NULL;

  n = sl_alloc(neigh_slab);
257 258
  memset(n, 0, sizeof(neighbor));

259 260 261
  add_tail(&neigh_hash_table[h], &n->n);
  add_tail((scope >= 0) ? &iface->neighbors : &sticky_neigh_list, &n->if_n);
  n->addr = a;
262
  n->ifa = addr;
263 264
  n->iface = iface;
  n->ifreq = ifreq;
265 266
  n->proto = p;
  n->flags = flags;
267
  n->scope = scope;
268 269 270 271

  return n;
}

Martin Mareš's avatar
Martin Mareš committed
272 273 274 275
/**
 * neigh_dump - dump specified neighbor entry.
 * @n: the entry to dump
 *
276
 * This functions dumps the contents of a given neighbor entry to debug output.
Martin Mareš's avatar
Martin Mareš committed
277
 */
278 279 280
void
neigh_dump(neighbor *n)
{
281 282 283
  debug("%p %I %s %s ", n, n->addr,
	n->iface ? n->iface->name : "[]",
	n->ifreq ? n->ifreq->name : "[]");
284
  debug("%s %p %08x scope %s", n->proto->name, n->data, n->aux, ip_scope_text(n->scope));
285 286
  if (n->flags & NEF_STICKY)
    debug(" STICKY");
287 288
  if (n->flags & NEF_ONLINK)
    debug(" ONLINK");
289 290 291
  debug("\n");
}

Martin Mareš's avatar
Martin Mareš committed
292 293 294
/**
 * neigh_dump_all - dump all neighbor entries.
 *
295
 * This function dumps the contents of the neighbor cache to debug output.
Martin Mareš's avatar
Martin Mareš committed
296
 */
297 298 299 300 301 302 303 304
void
neigh_dump_all(void)
{
  neighbor *n;
  int i;

  debug("Known neighbors:\n");
  for(i=0; i<NEIGH_HASH_SIZE; i++)
305 306
    WALK_LIST(n, neigh_hash_table[i])
      neigh_dump(n);
307 308 309
  debug("\n");
}

310 311 312 313 314 315 316
static inline void
neigh_notify(neighbor *n)
{
  if (n->proto->neigh_notify && (n->proto->proto_state != PS_STOP))
    n->proto->neigh_notify(n);
}

317
static void
318
neigh_up(neighbor *n, struct iface *i, struct ifa *a, int scope)
319
{
320
  DBG("Waking up sticky neighbor %I\n", n->addr);
321
  n->iface = i;
322
  n->ifa = a;
323
  n->scope = scope;
324

325 326
  rem_node(&n->if_n);
  add_tail(&i->neighbors, &n->if_n);
327

328
  neigh_notify(n);
329 330 331 332 333
}

static void
neigh_down(neighbor *n)
{
334
  DBG("Flushing neighbor %I on %s\n", n->addr, n->iface->name);
335
  n->iface = NULL;
336
  n->ifa = NULL;
337
  n->scope = -1;
338

339 340
  rem_node(&n->if_n);
  add_tail(&sticky_neigh_list, &n->if_n);
341

342 343
  neigh_notify(n);
}
344

345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364
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)
{
365
  struct proto *p = n->proto;
366 367 368 369 370 371 372 373
  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 */
374
  if (p->vrf_set && (p->vrf != iface->master))
375 376 377 378
    return;

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

379 380 381 382 383 384 385 386 387 388 389 390 391 392
  /* Update about already assigned iface, or some other iface */
  if (iface == n->iface)
  {
    /* 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, p->vrf, p->vrf_set, &iface, &ifa, n->flags);
  }
  else
  {
    /* Continue only if the new variant is better than the existing one */
    if (! (scope_better(scope, n->scope) ||
	   (scope_remote(scope, n->scope) && ifa_better(ifa, n->ifa))))
      return;
  }
393 394 395 396 397

  /* No change or minor change - ignore or notify */
  if ((scope == n->scope) && (iface == n->iface))
  {
    if (ifa != n->ifa)
398
    {
399 400
      n->ifa = ifa;
      neigh_notify(n);
401
    }
402

403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418
    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);
419 420 421
}


Martin Mareš's avatar
Martin Mareš committed
422 423 424 425 426 427 428 429 430
/**
 * 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.
 */
431 432 433
void
neigh_if_up(struct iface *i)
{
434
  struct iface *ii;
435 436
  neighbor *n;
  node *x, *y;
437

438 439 440 441 442 443
  /* Update neighbors that might be better off with the new iface */
  WALK_LIST(ii, iface_list)
    if (!EMPTY_LIST(ii->neighbors) && (ii != i) && if_intersect(i, ii))
      WALK_LIST2_DELSAFE(n, x, y, ii->neighbors, if_n)
	neigh_update(n, i);

444 445
  WALK_LIST2_DELSAFE(n, x, y, sticky_neigh_list, if_n)
    neigh_update(n, i);
446 447
}

Martin Mareš's avatar
Martin Mareš committed
448 449 450 451 452 453
/**
 * 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.
 *
454
 * It causes all neighbors connected to this interface to be updated or removed.
Martin Mareš's avatar
Martin Mareš committed
455
 */
456 457 458
void
neigh_if_down(struct iface *i)
{
459
  neighbor *n;
460 461
  node *x, *y;

462
  WALK_LIST2_DELSAFE(n, x, y, i->neighbors, if_n)
463
    neigh_update(n, i);
464 465
}

466 467 468 469
/**
 * neigh_if_link - notify neighbor cache about interface link change
 * @i: the interface in question
 *
470 471
 * Notify the neighbor cache that an interface changed link state. All owners of
 * neighbor entries connected to this interface are notified.
472 473 474 475
 */
void
neigh_if_link(struct iface *i)
{
476
  neighbor *n;
477 478
  node *x, *y;

479
  WALK_LIST2_DELSAFE(n, x, y, i->neighbors, if_n)
480
    neigh_notify(n);
481 482
}

483 484
/**
 * neigh_ifa_update: notify neighbor cache about interface address add or remove event
485
 * @a: interface address in question
486 487 488 489 490 491 492 493
 *
 * 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
494
neigh_ifa_up(struct ifa *a)
495
{
496
  struct iface *i = a->iface, *ii;
497
  neighbor *n;
498
  node *x, *y;
499

500 501 502 503 504
  /* Update neighbors that might be better off with the new ifa */
  WALK_LIST(ii, iface_list)
    if (!EMPTY_LIST(ii->neighbors) && ifa_intersect(a, ii))
      WALK_LIST2_DELSAFE(n, x, y, ii->neighbors, if_n)
	neigh_update(n, i);
505 506

  /* Wake up all sticky neighbors that are reachable now */
507 508
  WALK_LIST2_DELSAFE(n, x, y, sticky_neigh_list, if_n)
    neigh_update(n, i);
509 510
}

511 512 513 514 515 516 517 518 519 520 521 522 523
void
neigh_ifa_down(struct ifa *a)
{
  struct iface *i = a->iface;
  neighbor *n;
  node *x, *y;

  /* Update all neighbors whose scope has changed */
  WALK_LIST2_DELSAFE(n, x, y, i->neighbors, if_n)
    if (n->ifa == a)
      neigh_update(n, i);
}

524 525 526
static inline void
neigh_prune_one(neighbor *n)
{
Ondřej Zajíček's avatar
Ondřej Zajíček committed
527
  if (n->proto->proto_state != PS_DOWN)
528
    return;
529 530

  neigh_free(n);
531 532
}

Martin Mareš's avatar
Martin Mareš committed
533 534 535 536 537 538 539
/**
 * 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.
 */
540 541 542 543 544 545 546 547 548 549
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])
550
      neigh_prune_one(n);
551 552
}

Martin Mareš's avatar
Martin Mareš committed
553 554 555 556 557 558 559
/**
 * 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.
 */
560 561 562 563
void
neigh_init(pool *if_pool)
{
  neigh_slab = sl_new(if_pool, sizeof(neighbor));
564 565

  for(int i = 0; i < NEIGH_HASH_SIZE; i++)
566
    init_list(&neigh_hash_table[i]);
567 568

  init_list(&sticky_neigh_list);
569
}