rt.c 47.8 KB
Newer Older
1
/*
2
 *	BIRD -- OSPF
3
 *
4 5 6
 *	(c) 2000--2004 Ondrej Filip <feela@network.cz>
 *	(c) 2009--2014 Ondrej Zajicek <santiago@crfreenet.org>
 *	(c) 2009--2014 CZ.NIC z.s.p.o.
7
 *
8
 *	Can be freely distributed and used under the terms of the GNU GPL.
9 10 11
 */

#include "ospf.h"
12

13
static void add_cand(list * l, struct top_hash_entry *en,
14
		     struct top_hash_entry *par, u32 dist,
15
		     struct ospf_area *oa, int i);
16
static void rt_sync(struct ospf_proto *p);
17 18


19
static inline void reset_ri(ort *ort)
20
{
21
  bzero(&ort->n, sizeof(orta));
22
}
23

24
void
25
ospf_rt_initort(struct fib_node *fn)
26
{
27
  ort *ri = (ort *) fn;
28 29
  reset_ri(ri);
  ri->old_rta = NULL;
30
  ri->fn.flags = 0;
31
}
32

33
static inline int
34
nh_is_vlink(struct mpnh *nhs)
35
{
36 37 38 39 40 41 42
  return !nhs->iface;
}

static inline int
unresolved_vlink(ort *ort)
{
  return ort->n.nhs && nh_is_vlink(ort->n.nhs);
43 44 45
}

static inline struct mpnh *
Pavel Tvrdík's avatar
Pavel Tvrdík committed
46
new_nexthop(struct ospf_proto *p, ip_addr gw, struct iface *iface, byte weight)
47
{
48
  struct mpnh *nh = lp_alloc(p->nhpool, sizeof(struct mpnh));
49 50 51 52 53 54 55
  nh->gw = gw;
  nh->iface = iface;
  nh->next = NULL;
  nh->weight = weight;
  return nh;
}

56
/* Returns true if there are device nexthops in n */
57
static inline int
58
has_device_nexthops(const struct mpnh *n)
59
{
60 61 62 63 64
  for (; n; n = n->next)
    if (ipa_zero(n->gw))
      return 1;

  return 0;
65 66
}

67 68
/* Replace device nexthops with nexthops to gw */
static struct mpnh *
69
fix_device_nexthops(struct ospf_proto *p, const struct mpnh *n, ip_addr gw)
70
{
71 72 73 74
  struct mpnh *root1 = NULL;
  struct mpnh *root2 = NULL;
  struct mpnh **nn1 = &root1;
  struct mpnh **nn2 = &root2;
75

76 77 78
  if (!p->ecmp)
    return new_nexthop(p, gw, n->iface, n->weight);

79 80 81
  /* This is a bit tricky. We cannot just copy the list and update n->gw,
     because the list should stay sorted, so we create two lists, one with new
     gateways and one with old ones, and then merge them. */
82

83 84
  for (; n; n = n->next)
  {
85
    struct mpnh *nn = new_nexthop(p, ipa_zero(n->gw) ? gw : n->gw, n->iface, n->weight);
86

87 88 89 90 91 92 93 94 95 96
    if (ipa_zero(n->gw))
    {
      *nn1 = nn;
      nn1 = &(nn->next);
    }
    else
    {
      *nn2 = nn;
      nn2 = &(nn->next);
    }
97
  }
Ondřej Filip's avatar
Ondřej Filip committed
98

99
  return mpnh_merge(root1, root2, 1, 1, p->ecmp, p->nhpool);
100
}
101 102


103 104 105 106 107 108 109
/* Whether the ASBR or the forward address destination is preferred
   in AS external route selection according to 16.4.1. */
static inline int
epath_preferred(const orta *ep)
{
  return (ep->type == RTS_OSPF) && (ep->oa->areaid != 0);
}
110

111 112 113 114 115
/* Whether the ext route has ASBR/next_hop marked as preferred. */
static inline int
orta_pref(const orta *nf)
{
  return !!(nf->options & ORTA_PREF);
116 117
}

118 119
/* Classify orta entries according to RFC 3101 2.5 (6e) priorities:
   Type-7 LSA with P-bit, Type-5 LSA, Type-7 LSA without P-bit */
120
static int
121
orta_prio(const orta *nf)
122 123 124 125 126 127 128 129 130 131 132 133 134 135 136
{
  /* RFC 3103 2.5 (6e) priorities */
  u32 opts = nf->options & (ORTA_NSSA | ORTA_PROP);

  /* A Type-7 LSA with the P-bit set */
  if (opts == (ORTA_NSSA | ORTA_PROP))
    return 2;

  /* A Type-5 LSA */
  if (opts == 0)
    return 1;

  return 0;
}

137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153
/* Whether the route is better according to RFC 3101 2.5 (6e):
   Prioritize Type-7 LSA with P-bit, then Type-5 LSA, then higher router ID */
static int
orta_prefer_lsa(const orta *new, const orta *old)
{
  int pn = orta_prio(new);
  int po = orta_prio(old);

  return (pn > po) || ((pn == po) && (new->en->lsa.rt > old->en->lsa.rt));
}

/*
 * Compare an existing routing table entry with a new one. Applicable for
 * intra-area routes, inter-area routes and router entries. Returns integer
 * <, = or > than 0 if the new orta is less, equal or more preferred than
 * the old orta.
 */
154
static int
155
orta_compare(const struct ospf_proto *p, const orta *new, const orta *old)
156
{
157 158
  int r;

159 160 161
  if (old->type == RTS_DUMMY)
    return 1;

162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182
  /* Prefer intra-area to inter-area to externals */
  r = ((int) old->type) - ((int) new->type);
  if (r) return r;

  /* Prefer lowest type 1 metric */
  r = ((int) old->metric1) - ((int) new->metric1);
  if (r) return r;


  /* Rest is BIRD-specific */

  /* Area-wide routes should not mix next-hops from different areas.
     This generally should not happen unless there is some misconfiguration. */
  if (new->oa->areaid != old->oa->areaid)
    return (new->oa->areaid > old->oa->areaid) ? 1 : -1;

  /* Prefer routes for configured stubnets (!nhs) to regular routes to dummy
     vlink nexthops. We intentionally return -1 if both are stubnets or vlinks. */
  if (!old->nhs)
    return -1;
  if (!new->nhs)
183
    return 1;
184 185 186 187 188
  if (nh_is_vlink(new->nhs))
    return -1;
  if (nh_is_vlink(old->nhs))
    return 1;

189

190
  if (p->ecmp)
191 192
    return 0;

193 194 195
  /* Prefer routes with higher Router ID, just to be more deterministic */
  if (new->rid > old->rid)
    return 1;
196

197 198
  return -1;
}
199

200 201 202 203 204 205
/*
 * Compare ASBR routing table entry with a new one, used for precompute ASBRs
 * for AS external route selection (RFC 2328 16.4 (3)), Returns integer < or >
 * than 0 if the new ASBR is less or more preferred than the old ASBR.
 */
static int
206
orta_compare_asbr(const struct ospf_proto *p, const orta *new, const orta *old)
207 208 209 210 211
{
  int r;

  if (old->type == RTS_DUMMY)
    return 1;
Ondřej Filip's avatar
Ondřej Filip committed
212

213
  if (!p->rfc1583)
214
  {
215 216
    r = epath_preferred(new) - epath_preferred(old);
    if (r) return r;
217 218
  }

219 220 221 222 223
  r = ((int) old->metric1) - ((int) new->metric1);
  if (r) return r;

  /* Larger area ID is preferred */
  if (new->oa->areaid > old->oa->areaid)
224 225
    return 1;

226 227 228
  /* There is just one ASBR of that RID per area, so tie is not possible */
  return -1;
}
229

230 231 232 233 234 235
/*
 * Compare a routing table entry with a new one, for AS external routes
 * (RFC 2328 16.4) and NSSA routes (RFC 3103 2.5), Returns integer <, = or >
 * than 0 if the new orta is less, equal or more preferred than the old orta.
 */
static int
236
orta_compare_ext(const struct ospf_proto *p, const orta *new, const orta *old)
237 238
{
  int r;
239

240
  if (old->type == RTS_DUMMY)
241 242
    return 1;

243 244 245 246 247 248 249 250 251 252 253 254
  /* 16.4 (6a) - prefer routes with lower type */
  r = ((int) old->type) - ((int) new->type);
  if (r) return r;

  /* 16.4 (6b) - prefer routes with lower type 2 metric */
  if (new->type == RTS_OSPF_EXT2)
  {
    r = ((int) old->metric2) - ((int) new->metric2);
    if (r) return r;
  }

  /* 16.4 (6c) - if not RFC1583, prefer routes with preferred ASBR/next_hop */
255
  if (!p->rfc1583)
256 257 258 259 260 261 262 263 264 265
  {
    r = orta_pref(new) - orta_pref(old);
    if (r) return r;
  }

  /* 16.4 (6d) - prefer routes with lower type 1 metric */
  r = ((int) old->metric1) - ((int) new->metric1);
  if (r) return r;


266
  if (p->ecmp && p->merge_external)
267 268
    return 0;

269 270 271 272 273 274 275
  /*
   * RFC 3101 2.5 (6e) - prioritize Type-7 LSA with P-bit, then Type-5 LSA, then
   * LSA with higher router ID. Although this should apply just to functionally
   * equivalent LSAs (i.e. ones with the same non-zero forwarding address), we
   * use it also to disambiguate otherwise equally preferred nexthops.
   */
  if (orta_prefer_lsa(new, old))
276
    return 1;
277

278 279 280 281 282 283 284 285 286 287 288
  return -1;
}


static inline void
ort_replace(ort *o, const orta *new)
{
  memcpy(&o->n, new, sizeof(orta));
}

static void
289
ort_merge(struct ospf_proto *p, ort *o, const orta *new)
290 291 292 293 294
{
  orta *old = &o->n;

  if (old->nhs != new->nhs)
  {
295 296
    old->nhs = mpnh_merge(old->nhs, new->nhs, old->nhs_reuse, new->nhs_reuse,
			  p->ecmp, p->nhpool);
297 298 299 300 301
    old->nhs_reuse = 1;
  }

  if (old->rid < new->rid)
    old->rid = new->rid;
302
}
303

304
static void
305
ort_merge_ext(struct ospf_proto *p, ort *o, const orta *new)
306 307 308 309 310
{
  orta *old = &o->n;

  if (old->nhs != new->nhs)
  {
311 312
    old->nhs = mpnh_merge(old->nhs, new->nhs, old->nhs_reuse, new->nhs_reuse,
			  p->ecmp, p->nhpool);
313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335
    old->nhs_reuse = 1;
  }

  if (old->tag != new->tag)
    old->tag = 0;

  /*
   * Even with multipath, we store only one LSA in orta.en for the purpose of
   * NSSA/ext translation. Therefore, we apply procedures from RFC 3101 2.5 (6e)
   * to all chosen LSAs for given network, not just to functionally equivalent
   * ones (i.e. ones with the same non-zero forwarding address).
   */
  if (orta_prefer_lsa(new, old))
  {
    old->options = new->options;
    old->rid = new->rid;
    old->oa = new->oa;
    old->en = new->en;
  }
}



336
static inline void
337
ri_install_net(struct ospf_proto *p, ip_addr prefix, int pxlen, const orta *new)
338
{
339 340
  ort *old = (ort *) fib_get(&p->rtf, &prefix, pxlen);
  int cmp = orta_compare(p, new, &old->n);
341 342 343 344

  if (cmp > 0)
    ort_replace(old, new);
  else if (cmp == 0)
345
    ort_merge(p, old, new);
346 347
}

348
static inline void
349
ri_install_rt(struct ospf_area *oa, u32 rid, const orta *new)
350
{
351 352
  ip_addr addr = ipa_from_rid(rid);
  ort *old = (ort *) fib_get(&oa->rtr, &addr, MAX_PREFIX_LENGTH);
353 354 355 356 357 358
  int cmp = orta_compare(oa->po, new, &old->n);

  if (cmp > 0)
    ort_replace(old, new);
  else if (cmp == 0)
    ort_merge(oa->po, old, new);
359
}
360

361
static inline void
362
ri_install_asbr(struct ospf_proto *p, ip_addr *addr, const orta *new)
363
{
364 365
  ort *old = (ort *) fib_get(&p->backbone->rtr, addr, MAX_PREFIX_LENGTH);
  if (orta_compare_asbr(p, new, &old->n) > 0)
366
    ort_replace(old, new);
367
}
Ondřej Filip's avatar
Ondřej Filip committed
368

369
static inline void
370
ri_install_ext(struct ospf_proto *p, ip_addr prefix, int pxlen, const orta *new)
371
{
372 373
  ort *old = (ort *) fib_get(&p->rtf, &prefix, pxlen);
  int cmp = orta_compare_ext(p, new, &old->n);
374 375 376 377

  if (cmp > 0)
    ort_replace(old, new);
  else if (cmp == 0)
378
    ort_merge_ext(p, old, new);
379 380
}

381 382
static inline struct ospf_iface *
rt_pos_to_ifa(struct ospf_area *oa, int pos)
383
{
384
  struct ospf_iface *ifa;
385

386
  WALK_LIST(ifa, oa->po->iface_list)
387
    if (ifa->oa == oa && pos >= ifa->rt_pos_beg && pos < ifa->rt_pos_end)
388
      return ifa;
389

390 391 392
  return NULL;
}

393 394
static inline struct ospf_iface *
px_pos_to_ifa(struct ospf_area *oa, int pos)
395
{
396
  struct ospf_iface *ifa;
397

398
  WALK_LIST(ifa, oa->po->iface_list)
399
    if (ifa->oa == oa && pos >= ifa->px_pos_beg && pos < ifa->px_pos_end)
400
      return ifa;
401

402 403 404
  return NULL;
}

405

406
static void
407
add_network(struct ospf_area *oa, ip_addr px, int pxlen, int metric, struct top_hash_entry *en, int pos)
408
{
409 410
  struct ospf_proto *p = oa->po;

411 412 413 414 415 416 417 418
  orta nf = {
    .type = RTS_OSPF,
    .options = 0,
    .metric1 = metric,
    .metric2 = LSINFINITY,
    .tag = 0,
    .rid = en->lsa.rt,
    .oa = oa,
419
    .nhs = en->nhs
420
  };
421

422 423 424
  if (pxlen < 0 || pxlen > MAX_PREFIX_LENGTH)
  {
    log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
425
	p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
426 427 428
    return;
  }

429 430
  if (en == oa->rt)
  {
431
    /*
432 433 434
     * Local stub networks do not have proper iface in en->nhi (because they all
     * have common top_hash_entry en). We have to find iface responsible for
     * that stub network. Configured stubnets do not have any iface. They will
435
     * be removed in rt_sync().
436 437
     */

438
    struct ospf_iface *ifa;
439 440 441 442 443 444 445
    ifa = ospf_is_v2(p) ? rt_pos_to_ifa(oa, pos) : px_pos_to_ifa(oa, pos);
    nf.nhs = ifa ? new_nexthop(p, IPA_NONE, ifa->iface, ifa->ecmp_weight) : NULL;
  }

  ri_install_net(p, px, pxlen, &nf);
}

446

447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479

static inline void
spfa_process_rt(struct ospf_proto *p, struct ospf_area *oa, struct top_hash_entry *act)
{
  struct ospf_lsa_rt *rt = act->lsa_body;
  struct ospf_lsa_rt_walk rtl;
  struct top_hash_entry *tmp;
  ip_addr prefix;
  int pxlen, i;

  if (rt->options & OPT_RT_V)
    oa->trcap = 1;

  /*
   * In OSPFv3, all routers are added to per-area routing
   * tables. But we use it just for ASBRs and ABRs. For the
   * purpose of the last step in SPF - prefix-LSA processing in
   * spfa_process_prefixes(), we use information stored in LSA db.
   */
  if (((rt->options & OPT_RT_E) || (rt->options & OPT_RT_B))
      && (act->lsa.rt != p->router_id))
  {
    orta nf = {
      .type = RTS_OSPF,
      .options = rt->options,
      .metric1 = act->dist,
      .metric2 = LSINFINITY,
      .tag = 0,
      .rid = act->lsa.rt,
      .oa = oa,
      .nhs = act->nhs
    };
    ri_install_rt(oa, act->lsa.rt, &nf);
480 481
  }

482 483
  /* Errata 2078 to RFC 5340 4.8.1 - skip links from non-routing nodes */
  if (ospf_is_v3(p) && (act != oa->rt) && !(rt->options & OPT_R))
484
    return;
485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521

  /* Now process Rt links */
  for (lsa_walk_rt_init(p, act, &rtl), i = 0; lsa_walk_rt(&rtl); i++)
  {
    tmp = NULL;

    switch (rtl.type)
    {
    case LSART_STUB:

      /* Should not happen, LSART_STUB is not defined in OSPFv3 */
      if (ospf_is_v3(p))
	break;

      /*
       * RFC 2328 in 16.1. (2a) says to handle stub networks in an
       * second phase after the SPF for an area is calculated. We get
       * the same result by handing them here because add_network()
       * will keep the best (not the first) found route.
       */
      prefix = ipa_from_u32(rtl.id & rtl.data);
      pxlen = u32_masklen(rtl.data);
      add_network(oa, prefix, pxlen, act->dist + rtl.metric, act, i);
      break;

    case LSART_NET:
      tmp = ospf_hash_find_net(p->gr, oa->areaid, rtl.id, rtl.nif);
      break;

    case LSART_VLNK:
    case LSART_PTP:
      tmp = ospf_hash_find_rt(p->gr, oa->areaid, rtl.id);
      break;
    }

    add_cand(&oa->cand, tmp, act, act->dist + rtl.metric, oa, i);
  }
522 523
}

524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548
static inline void
spfa_process_net(struct ospf_proto *p, struct ospf_area *oa, struct top_hash_entry *act)
{
  struct ospf_lsa_net *ln = act->lsa_body;
  struct top_hash_entry *tmp;
  ip_addr prefix;
  int pxlen, i, cnt;

  if (ospf_is_v2(p))
  {
    prefix = ipa_from_u32(act->lsa.id & ln->optx);
    pxlen = u32_masklen(ln->optx);
    add_network(oa, prefix, pxlen, act->dist, act, -1);
  }

  cnt = lsa_net_count(&act->lsa);
  for (i = 0; i < cnt; i++)
  {
    tmp = ospf_hash_find_rt(p->gr, oa->areaid, ln->routers[i]);
    add_cand(&oa->cand, tmp, act, act->dist, oa, -1);
  }
}

static inline void
spfa_process_prefixes(struct ospf_proto *p, struct ospf_area *oa)
549 550 551 552 553 554 555 556 557 558
{
  struct top_hash_entry *en, *src;
  struct ospf_lsa_prefix *px;
  ip_addr pxa;
  int pxlen;
  u8 pxopts;
  u16 metric;
  u32 *buf;
  int i;

559
  WALK_SLIST(en, p->lsal)
560
  {
561
    if (en->lsa_type != LSA_T_PREFIX)
562 563 564 565 566 567 568 569 570
      continue;

    if (en->domain != oa->areaid)
      continue;

    if (en->lsa.age == LSA_MAXAGE)
      continue;

    px = en->lsa_body;
571 572 573

    /* For router prefix-LSA, we would like to find the first router-LSA */
    if (px->ref_type == LSA_T_RT)
574
      src = ospf_hash_find_rt(p->gr, oa->areaid, px->ref_rt);
575
    else
576
      src = ospf_hash_find(p->gr, oa->areaid, px->ref_id, px->ref_rt, px->ref_type);
577 578 579 580

    if (!src)
      continue;

581 582 583 584
    /* Reachable in SPF */
    if (src->color != INSPF)
      continue;

585
    if ((src->lsa_type != LSA_T_RT) && (src->lsa_type != LSA_T_NET))
586 587 588 589 590
      continue;

    buf = px->rest;
    for (i = 0; i < px->pxcount; i++)
      {
591
	buf = lsa_get_ipv6_prefix(buf, &pxa, &pxlen, &pxopts, &metric);
592 593 594 595

	if (pxopts & OPT_PX_NU)
	  continue;

596 597 598 599
	/* Store the first global address to use it later as a vlink endpoint */
	if ((pxopts & OPT_PX_LA) && ipa_zero(src->lb))
	  src->lb = pxa;

600
	add_network(oa, pxa, pxlen, src->dist + metric, src, i);
601 602 603
      }
  }
}
604

605
/* RFC 2328 16.1. calculating shortest paths for an area */
606
static void
607
ospf_rt_spfa(struct ospf_area *oa)
608
{
609 610
  struct ospf_proto *p = oa->po;
  struct top_hash_entry *act;
Ondřej Filip's avatar
Ondřej Filip committed
611 612
  node *n;

Ondřej Filip's avatar
Ondřej Filip committed
613 614
  if (oa->rt == NULL)
    return;
615 616
  if (oa->rt->lsa.age == LSA_MAXAGE)
    return;
617

618
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation for area %R", oa->areaid);
619

620
  /* 16.1. (1) */
621
  init_list(&oa->cand);		/* Empty list of candidates */
Ondřej Filip's avatar
Ondřej Filip committed
622
  oa->trcap = 0;
623

624 625
  DBG("LSA db prepared, adding me into candidate list.\n");

Ondřej Filip's avatar
Ondřej Filip committed
626 627
  oa->rt->dist = 0;
  oa->rt->color = CANDIDATE;
628
  add_head(&oa->cand, &oa->rt->cn);
629
  DBG("RT LSA: rt: %R, id: %R, type: %u\n",
630
      oa->rt->lsa.rt, oa->rt->lsa.id, oa->rt->lsa_type);
631

Ondřej Filip's avatar
Ondřej Filip committed
632
  while (!EMPTY_LIST(oa->cand))
633
  {
Ondřej Filip's avatar
Ondřej Filip committed
634 635
    n = HEAD(oa->cand);
    act = SKIP_BACK(struct top_hash_entry, cn, n);
636 637
    rem_node(n);

638
    DBG("Working on LSA: rt: %R, id: %R, type: %u\n",
639
	act->lsa.rt, act->lsa.id, act->lsa_type);
640

Ondřej Filip's avatar
Ondřej Filip committed
641
    act->color = INSPF;
642
    switch (act->lsa_type)
643
    {
Ondřej Filip's avatar
Ondřej Filip committed
644
    case LSA_T_RT:
645
      spfa_process_rt(p, oa, act);
Ondřej Filip's avatar
Ondřej Filip committed
646
      break;
647

648 649
    case LSA_T_NET:
      spfa_process_net(p, oa, act);
Ondřej Filip's avatar
Ondřej Filip committed
650
      break;
651 652 653

    default:
      log(L_WARN "%s: Unknown LSA type in SPF: %d", p->p.name, act->lsa_type);
654
    }
655
  }
Ondřej Filip's avatar
Ondřej Filip committed
656

657 658
  if (ospf_is_v3(p))
    spfa_process_prefixes(p, oa);
Ondřej Filip's avatar
Ondřej Filip committed
659 660 661
}

static int
662
link_back(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry *par)
Ondřej Filip's avatar
Ondřej Filip committed
663
{
664 665
  struct ospf_proto *p = oa->po;
  struct ospf_lsa_rt_walk rtl;
666
  struct top_hash_entry *tmp;
667 668
  struct ospf_lsa_net *ln;
  u32 i, cnt;
Ondřej Filip's avatar
Ondřej Filip committed
669

670 671
  if (!en || !par) return 0;

Ondřej Zajíček's avatar
Ondřej Zajíček committed
672 673 674 675 676 677 678
  /* We should check whether there is a link back from en to par,
     this is used in SPF calc (RFC 2328 16.1. (2b)). According to RFC 2328
     note 23, we don't have to find the same link that is used for par
     to en, any link is enough. This we do for ptp links. For net-rt
     links, we have to find the same link to compute proper lb/lb_id,
     which may be later used as the next hop. */

679
  /* In OSPFv2, en->lb is set here. In OSPFv3, en->lb is just cleared here,
Ondřej Zajíček's avatar
Ondřej Zajíček committed
680
     it is set in process_prefixes() to any global address in the area */
681

682
  en->lb = IPA_NONE;
683
  en->lb_id = 0;
684 685

  switch (en->lsa_type)
Ondřej Filip's avatar
Ondřej Filip committed
686
  {
687 688 689 690 691
  case LSA_T_RT:
    lsa_walk_rt_init(p, en, &rtl);
    while (lsa_walk_rt(&rtl))
    {
      switch (rtl.type)
Ondřej Filip's avatar
Ondřej Filip committed
692
      {
693 694 695 696 697 698
      case LSART_STUB:
	break;

      case LSART_NET:
	tmp = ospf_hash_find_net(p->gr, oa->areaid, rtl.id, rtl.nif);
	if (tmp == par)
Ondřej Filip's avatar
Ondřej Filip committed
699
	{
700 701 702 703 704 705
	  if (ospf_is_v2(p))
	    en->lb = ipa_from_u32(rtl.data);
	  else
	    en->lb_id = rtl.lif;

	  return 1;
Ondřej Filip's avatar
Ondřej Filip committed
706
	}
707 708 709 710 711 712
	break;

      case LSART_VLNK:
      case LSART_PTP:
	/* Not necessary the same link, see RFC 2328 [23] */
	tmp = ospf_hash_find_rt(p->gr, oa->areaid, rtl.id);
713
	if (tmp == par)
714 715
	  return 1;
	break;
Ondřej Filip's avatar
Ondřej Filip committed
716
      }
717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732
    }
    break;

  case LSA_T_NET:
    ln = en->lsa_body;
    cnt = lsa_net_count(&en->lsa);
    for (i = 0; i < cnt; i++)
    {
      tmp = ospf_hash_find_rt(p->gr, oa->areaid, ln->routers[i]);
      if (tmp == par)
	return 1;
    }
    break;

  default:
    log(L_WARN "%s: Unknown LSA type in SPF: %d", p->p.name, en->lsa_type);
Ondřej Filip's avatar
Ondřej Filip committed
733 734 735 736
  }
  return 0;
}

737

738
/* RFC 2328 16.2. calculating inter-area routes */
Ondřej Filip's avatar
Ondřej Filip committed
739
static void
740
ospf_rt_sum(struct ospf_area *oa)
Ondřej Filip's avatar
Ondřej Filip committed
741
{
742
  struct ospf_proto *p = oa->po;
Ondřej Filip's avatar
Ondřej Filip committed
743
  struct top_hash_entry *en;
744 745
  ip_addr ip, abrip;
  u32 dst_rid, metric, options;
746
  ort *abr;
747
  int pxlen = -1, type = -1;
748
  u8 pxopts;
749

Ondřej Filip's avatar
Ondřej Filip committed
750

751
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation for inter-area (area %R)", oa->areaid);
Ondřej Filip's avatar
Ondřej Filip committed
752

753
  WALK_SLIST(en, p->lsal)
Ondřej Filip's avatar
Ondřej Filip committed
754
  {
755
    if ((en->lsa_type != LSA_T_SUM_RT) && (en->lsa_type != LSA_T_SUM_NET))
756
      continue;
757 758 759 760

    if (en->domain != oa->areaid)
      continue;

761
    /* 16.2. (1a) */
Ondřej Filip's avatar
Ondřej Filip committed
762 763
    if (en->lsa.age == LSA_MAXAGE)
      continue;
764

765
    /* 16.2. (2) */
766
    if (en->lsa.rt == p->router_id)
Ondřej Filip's avatar
Ondřej Filip committed
767 768
      continue;

769
    /* 16.2. (3) is handled later in ospf_rt_abr() by resetting such rt entry */
770

771
    if (en->lsa_type == LSA_T_SUM_NET)
Ondřej Filip's avatar
Ondřej Filip committed
772
    {
773
      lsa_parse_sum_net(en, ospf_is_v2(p), &ip, &pxlen, &pxopts, &metric);
774

775 776 777
      if (pxopts & OPT_PX_NU)
	continue;

778 779 780
      if (pxlen < 0 || pxlen > MAX_PREFIX_LENGTH)
      {
	log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
781
	    p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
782 783 784
	continue;
      }

785
      options = 0;
Ondřej Filip's avatar
Ondřej Filip committed
786 787
      type = ORT_NET;
    }
788
    else /* LSA_T_SUM_RT */
Ondřej Filip's avatar
Ondřej Filip committed
789
    {
790
      lsa_parse_sum_rt(en, ospf_is_v2(p), &dst_rid, &metric, &options);
791

792
      /* We don't want local router in ASBR routing table */
793
      if (dst_rid == p->router_id)
794
	continue;
795 796

      options |= ORTA_ASBR;
Ondřej Filip's avatar
Ondřej Filip committed
797 798
      type = ORT_ROUTER;
    }
799

800 801 802
    /* 16.2. (1b) */
    if (metric == LSINFINITY)
      continue;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
803

804
    /* 16.2. (4) */
805
    abrip = ipa_from_rid(en->lsa.rt);
806 807 808
    abr = (ort *) fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH);
    if (!abr || !abr->n.type)
      continue;
Ondřej Filip's avatar
Ondřej Filip committed
809

810 811 812
    if (!(abr->n.options & ORTA_ABR))
      continue;

813 814 815 816
    /* This check is not mentioned in RFC 2328 */
    if (abr->n.type != RTS_OSPF)
      continue;

817 818 819 820 821 822 823 824 825
    /* 16.2. (5) */
    orta nf = {
      .type = RTS_OSPF_IA,
      .options = options,
      .metric1 = abr->n.metric1 + metric,
      .metric2 = LSINFINITY,
      .tag = 0,
      .rid = en->lsa.rt, /* ABR ID */
      .oa = oa,
826
      .nhs = abr->n.nhs
827 828 829
    };

    if (type == ORT_NET)
830
      ri_install_net(p, ip, pxlen, &nf);
831 832
    else
      ri_install_rt(oa, dst_rid, &nf);
Ondřej Filip's avatar
Ondřej Filip committed
833
  }
834
}
835 836

/* RFC 2328 16.3. examining summary-LSAs in transit areas */
Ondřej Filip's avatar
Ondřej Filip committed
837
static void
838
ospf_rt_sum_tr(struct ospf_area *oa)
Ondřej Filip's avatar
Ondřej Filip committed
839
{
840 841
  struct ospf_proto *p = oa->po;
  struct ospf_area *bb = p->backbone;
Ondřej Filip's avatar
Ondřej Filip committed
842
  struct top_hash_entry *en;
843 844 845 846 847
  ort *re, *abr;
  ip_addr ip, abrip;
  u32 dst_rid, metric, options;
  int pxlen;
  u8 pxopts;
848

849

850 851
  if (!bb)
    return;
852

853
  WALK_SLIST(en, p->lsal)
Ondřej Filip's avatar
Ondřej Filip committed
854
  {
855
    if ((en->lsa_type != LSA_T_SUM_RT) && (en->lsa_type != LSA_T_SUM_NET))
856 857 858
      continue;

    if (en->domain != oa->areaid)
859
      continue;
860

861
    /* 16.3 (1a) */
Ondřej Filip's avatar
Ondřej Filip committed
862 863
    if (en->lsa.age == LSA_MAXAGE)
      continue;
864

865
    /* 16.3 (2) */
866
    if (en->lsa.rt == p->router_id)
Ondřej Filip's avatar
Ondřej Filip committed
867 868
      continue;

869
    if (en->lsa_type == LSA_T_SUM_NET)
Ondřej Filip's avatar
Ondřej Filip committed
870
    {
871
      lsa_parse_sum_net(en, ospf_is_v2(p), &ip, &pxlen, &pxopts, &metric);
872

873 874 875
      if (pxopts & OPT_PX_NU)
	continue;

876 877 878
      if (pxlen < 0 || pxlen > MAX_PREFIX_LENGTH)
      {
	log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
879
	    p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
880 881 882
	continue;
      }

883
      re = fib_find(&p->rtf, &ip, pxlen);
Ondřej Filip's avatar
Ondřej Filip committed
884
    }
885
    else // en->lsa_type == LSA_T_SUM_RT
Ondřej Filip's avatar
Ondřej Filip committed
886
    {
887 888 889
      lsa_parse_sum_rt(en, ospf_is_v2(p), &dst_rid, &metric, &options);

      ip = ipa_from_rid(dst_rid);
890
      re = fib_find(&bb->rtr, &ip, MAX_PREFIX_LENGTH);
Ondřej Filip's avatar
Ondřej Filip committed
891 892
    }

893 894 895
    /* 16.3 (1b) */
    if (metric == LSINFINITY)
      continue;
896

897 898 899
    /* 16.3 (3) */
    if (!re || !re->n.type)
      continue;
900

901 902
    if (re->n.oa->areaid != 0)
      continue;
903

904 905
    if ((re->n.type != RTS_OSPF) && (re->n.type != RTS_OSPF_IA))
      continue;
906

907 908 909 910 911
    /* 16.3. (4) */
    abrip = ipa_from_rid(en->lsa.rt);
    abr = fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH);
    if (!abr || !abr->n.type)
      continue;
912

913
    metric = abr->n.metric1 + metric; /* IAC */
Ondřej Filip's avatar
Ondřej Filip committed
914

915
    /* 16.3. (5) */
916
    if ((metric < re->n.metric1) ||
917
	((metric == re->n.metric1) && unresolved_vlink(re)))
Ondřej Filip's avatar
Ondřej Filip committed
918
    {
919
      /* We want to replace the next-hop even if the metric is equal
920 921 922 923 924
	 to replace a virtual next-hop through vlink with a real one.
	 Proper ECMP would merge nexthops here, but we do not do that.
	 We restrict nexthops to fit one area to simplify check
	 12.4.3 p4 in decide_sum_lsa() */

925
      re->n.metric1 = metric;
926 927
      re->n.voa = oa;
      re->n.nhs = abr->n.nhs;
Ondřej Filip's avatar
Ondřej Filip committed
928 929
    }
  }
930
}
931

Ondřej Zajíček's avatar
Ondřej Zajíček committed
932
/* Decide about originating or flushing summary LSAs for condensed area networks */
933 934 935
static int
decide_anet_lsa(struct ospf_area *oa, struct area_net *anet, struct ospf_area *anet_oa)
{
936 937
  /* 12.4.3.1. - for stub/NSSA areas, originating summary routes is configurable */
  if (!oa_is_ext(oa) && !oa->ac->summary)
938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953
    return 0;

  if (oa == anet_oa)
    return 0;

  /* Do not condense routing info when exporting from backbone to the transit area */
  if ((anet_oa == oa->po->backbone) && oa->trcap)
    return 0;

  return (anet->active && !anet->hidden);
}

/* Decide about originating or flushing summary LSAs (12.4.3) */
static int
decide_sum_lsa(struct ospf_area *oa, ort *nf, int dest)
{
954 955
  /* 12.4.3.1. - for stub/NSSA areas, originating summary routes is configurable */
  if (!oa_is_ext(oa) && !oa->ac->summary)
956 957 958 959 960 961 962 963 964 965 966 967 968 969 970
    return 0;

  /* Invalid field - no route */
  if (!nf->n.type)
    return 0;

  /* 12.4.3 p2 */
  if (nf->n.type > RTS_OSPF_IA)
    return 0;

  /* 12.4.3 p3 */
  if ((nf->n.oa->areaid == oa->areaid))
    return 0;

  /* 12.4.3 p4 */
971
  if (nf->n.voa && (nf->n.voa->areaid == oa->areaid))
972 973 974 975 976 977 978 979 980 981 982
    return 0;

  /* 12.4.3 p5 */
  if (nf->n.metric1 >= LSINFINITY)
    return 0;

  /* 12.4.3 p6 - AS boundary router */
  if (dest == ORT_ROUTER)
  {
    /* We call decide_sum_lsa() on preferred ASBR entries, no need for 16.4. (3) */
    /* 12.4.3 p1 */
983
    return oa_is_ext(oa) && (nf->n.options & ORTA_ASBR);
984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001
  }

  /* 12.4.3 p7 - inter-area route */
  if (nf->n.type == RTS_OSPF_IA)
  {
    /* Inter-area routes are not repropagated into the backbone */
    return (oa != oa->po->backbone);
  }

  /* 12.4.3 p8 - intra-area route */

  /* Do not condense routing info when exporting from backbone to the transit area */
  if ((nf->n.oa == oa->po->backbone) && oa->trcap)
    return 1;

  struct area_net *anet = (struct area_net *)
    fib_route(&nf->n.oa->net_fib, nf->fn.prefix, nf->fn.pxlen);

1002
  /* Condensed area network found */
1003 1004 1005 1006 1007 1008 1009 1010
  if (anet)
    return 0;

  return 1;
}

/* RFC 2328 16.7. p1 - originate or flush summary LSAs */
static inline void
1011
check_sum_net_lsa(struct ospf_proto *p, ort *nf)
1012 1013
{
  struct area_net *anet = NULL;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
1014
  struct ospf_area *anet_oa = NULL;
1015

1016
  if (nf->area_net)
1017 1018 1019 1020 1021 1022
  {
    /* It is a default route for stub areas, handled entirely in ospf_rt_abr() */
    if (nf->fn.pxlen == 0)
      return;

    /* Find that area network */
1023
    WALK_LIST(anet_oa, p->area_list)
1024 1025 1026 1027 1028 1029 1030 1031
    {
      anet = (struct area_net *) fib_find(&anet_oa->net_fib, &nf->fn.prefix, nf->fn.pxlen);
      if (anet)
	break;
    }
  }

  struct ospf_area *oa;
1032
  WALK_LIST(oa, p->area_list)
1033 1034
  {
    if (anet && decide_anet_lsa(oa, anet, anet_oa))
1035
      ospf_originate_sum_net_lsa(p, oa, nf, anet->metric);
1036
    else if (decide_sum_lsa(oa, nf, ORT_NET))
1037
      ospf_originate_sum_net_lsa(p, oa, nf, nf->n.metric1);
1038 1039 1040 1041
  }
}

static inline void
1042
check_sum_rt_lsa(struct ospf_proto *p, ort *nf)
1043 1044
{
  struct ospf_area *oa;
1045
  WALK_LIST(oa, p->area_list)
1046
    if (decide_sum_lsa(oa, nf, ORT_ROUTER))
1047
      ospf_originate_sum_rt_lsa(p, oa, nf, nf->n.metric1, nf->n.options);
1048 1049
}

1050
static inline int
1051
decide_nssa_lsa(struct ospf_proto *p UNUSED4 UNUSED6, ort *nf, struct ospf_lsa_ext_local *rt)
1052 1053 1054 1055 1056 1057 1058
{
  struct ospf_area *oa = nf->n.oa;
  struct top_hash_entry *en = nf->n.en;

  if (!rt_is_nssa(nf) || !oa->translate)
    return 0;

1059
  /* Condensed area network found */
1060 1061 1062
  if (fib_route(&oa->enet_fib, nf->fn.prefix, nf->fn.pxlen))
    return 0;

1063
  if (!en || (en->lsa_type != LSA_T_NSSA))
1064 1065 1066
    return 0;

  /* We do not store needed data in struct orta, we have to parse the LSA */
1067
  lsa_parse_ext(en, ospf_is_v2(p), rt);
1068

1069
  if (rt->pxopts & OPT_PX_NU)
1070 1071
    return 0;

1072
  if (!rt->propagate || ipa_zero(rt->fwaddr))
1073 1074 1075 1076 1077 1078 1079
    return 0;

  return 1;
}

/* RFC 3103 3.2 - translating Type-7 LSAs into Type-5 LSAs */
static inline void
1080
check_nssa_lsa(struct ospf_proto *p, ort *nf)
1081 1082 1083
{
  struct area_net *anet = NULL;
  struct ospf_area *oa = NULL;
1084
  struct ospf_lsa_ext_local rt;
1085 1086

  /* Do not translate LSA if there is already the external LSA from route export */
1087
  if (nf->external_rte)
1088 1089
    return;

1090
  if (nf->area_net)
1091 1092
  {
    /* Find that area network */
1093
    WALK_LIST(oa, p->area_list)
1094
    {
1095
      anet = (struct area_net *) fib_find(&oa->enet_fib, &nf->fn.prefix, nf->fn.pxlen);
1096 1097 1098 1099 1100 1101 1102
      if (anet)
	break;
    }
  }

  /* RFC 3103 3.2 (3) - originate the aggregated address range */
  if (anet && anet->active && !anet->hidden && oa->translate)
1103
    ospf_originate_ext_lsa(p, NULL, nf, LSA_M_RTCALC, anet->metric,
1104
			   (anet->metric & LSA_EXT3_EBIT), IPA_NONE, anet->tag, 0);
1105 1106

  /* RFC 3103 3.2 (2) - originate the same network */
1107
  else if (decide_nssa_lsa(p, nf, &rt))
1108
    ospf_originate_ext_lsa(p, NULL, nf, LSA_M_RTCALC, rt.metric, rt.ebit, rt.fwaddr, rt.tag, 0);
1109
}
1110 1111

/* RFC 2328 16.7. p2 - find new/lost vlink endpoints */
1112
static void
1113
ospf_check_vlinks(struct ospf_proto *p)
1114
{
1115
  struct ospf_iface *ifa;
1116
  WALK_LIST(ifa, p->iface_list)
1117
  {
1118
    if (ifa->type == OSPF_IT_VLINK)
1119 1120
    {
      struct top_hash_entry *tmp;
1121
      tmp = ospf_hash_find_rt(p->gr, ifa->voa->areaid, ifa->vid);
1122

1123
      if (tmp && (tmp->color == INSPF) && ipa_nonzero(tmp->lb) && tmp->nhs)
1124
      {
1125
	struct ospf_iface *nhi = ospf_iface_find(p, tmp->nhs->iface);
1126

1127
	if ((ifa->state != OSPF_IS_PTP)
1128 1129
	    || (ifa->vifa != nhi)
	    || !ipa_equal(ifa->vip, tmp->lb))
1130
	{
1131
	  OSPF_TRACE(D_EVENTS, "Vlink peer %R found", ifa->vid);
1132
	  ospf_iface_sm(ifa, ISM_DOWN);
1133 1134 1135
	  ifa->vifa = nhi;
	  ifa->addr = nhi->addr;
	  ifa->cost = tmp->dist;
1136 1137 1138
	  ifa->vip = tmp->lb;
	  ospf_iface_sm(ifa, ISM_UP);
	}
1139
	else if ((ifa->state == OSPF_IS_PTP) && (ifa->cost != tmp->dist))
1140
	{
1141
	  ifa->cost = tmp->dist;
1142 1143 1144

	  /* RFC 2328 12.4 Event 8 - vlink state change */
	  ospf_notify_rt_lsa(ifa->oa);
1145 1146 1147 1148
	}
      }
      else
      {
1149 1150 1151
	if (ifa->state > OSPF_IS_DOWN)
	{
	  OSPF_TRACE(D_EVENTS, "Vlink peer %R lost", ifa->vid);
1152
	  ospf_iface_sm(ifa, ISM_DOWN);
1153
	}
1154 1155 1156 1157 1158
      }
    }
  }
}

1159

1160 1161
/* Miscellaneous route processing that needs to be done by ABRs */
static void
1162
ospf_rt_abr1(struct ospf_proto *p)
1163 1164
{
  struct area_net *anet;
1165
  ort *nf, *default_nf;
1166

1167
  /* RFC 2328 G.3 - incomplete resolution of virtual next hops - routers */
1168
  FIB_WALK(&p->backbone->rtr, nftmp)
1169 1170 1171 1172 1173 1174 1175 1176 1177
  {
    nf = (ort *) nftmp;

    if (nf->n.type && unresolved_vlink(nf))
      reset_ri(nf);
  }
  FIB_WALK_END;


1178
  FIB_WALK(&p->rtf, nftmp)
Ondřej Filip's avatar
Ondřej Filip committed
1179
  {
1180 1181 1182
    nf = (ort *) nftmp;


1183 1184
    /* RFC 2328 G.3 - incomplete resolution of virtual next hops - networks */
    if (nf->n.type && unresolved_vlink(nf))
1185
      reset_ri(nf);
1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198


    /* Compute condensed area networks */
    if (nf->n.type == RTS_OSPF)
    {
      anet = (struct area_net *) fib_route(&nf->n.oa->net_fib, nf->fn.prefix, nf->fn.pxlen);
      if (anet)
      {
	if (!anet->active)
	{
	  anet->active = 1;

	  /* Get a RT entry and mark it to know that it is an area network */
1199
	  ort *nfi = (ort *) fib_get(&p->rtf, &anet->fn.prefix, anet->fn.pxlen);
1200
	  nfi->area_net = 1;
1201 1202 1203

	  /* 16.2. (3) */
	  if (nfi->n.type == RTS_OSPF_IA)
1204
	    reset_ri(nfi);
1205 1206 1207 1208 1209 1210 1211 1212 1213 1214
	}

	if (anet->metric < nf->n.metric1)
	  anet->metric = nf->n.metric1;
      }
    }
  }
  FIB_WALK_END;

  ip_addr addr = IPA_NONE;
1215
  default_nf = (ort *) fib_get(&p->rtf, &addr, 0);
1216
  default_nf->area_net = 1;
1217 1218

  struct ospf_area *oa;
1219
  WALK_LIST(oa, p->area_list)
1220 1221
  {

1222 1223
    /* 12.4.3.1. - originate or flush default route for stub/NSSA areas */
    if (oa_is_stub(oa) || (oa_is_nssa(oa) && !oa->ac->summary))
1224
      ospf_originate_sum_net_lsa(p, oa, default_nf, oa->ac->default_cost);
1225

1226 1227 1228 1229 1230 1231 1232 1233 1234 1235
    /*
     * Originate type-7 default route for NSSA areas
     *
     * Because type-7 default LSAs are originated by ABRs, they do not
     * collide with other type-7 LSAs (as ABRs generate type-5 LSAs
     * for both external route export or external-NSSA translation),
     * so we use 0 for the src arg.
     */

    if (oa_is_nssa(oa) && oa->ac->default_nssa)
1236
      ospf_originate_ext_lsa(p, oa, default_nf, LSA_M_RTCALC, oa->ac->default_cost,
1237
			     (oa->ac->default_cost & LSA_EXT3_EBIT), IPA_NONE, 0, 0);
1238 1239

    /* RFC 2328 16.4. (3) - precompute preferred ASBR entries */
1240
    if (oa_is_ext(oa))
1241
    {
1242 1243 1244 1245
      FIB_WALK(&oa->rtr, nftmp)
      {
	nf = (ort *) nftmp;
	if (nf->n.options & ORTA_ASBR)
1246
	  ri_install_asbr(p, &nf->fn.prefix, &nf->n);
1247 1248
      }
      FIB_WALK_END;
1249 1250 1251 1252
    }
  }


1253
  /* Originate or flush ASBR summary LSAs */
1254
  FIB_WALK(&p->backbone->rtr, nftmp)
1255
  {