rt.c 47.6 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


Ondřej Zajíček's avatar
Ondřej Zajíček committed
19
static inline void reset_ri(ort *ort)
20
{
Ondřej Zajíček's avatar
Ondřej Zajíček committed
21
  bzero(&ort->n, sizeof(orta));
22
}
23

Ondřej Zajíček's avatar
Ondřej Zajíček committed
24
static inline int
25
nh_is_vlink(struct mpnh *nhs)
Ondřej Zajíček's avatar
Ondřej Zajíček committed
26
{
27 28 29 30 31 32 33
  return !nhs->iface;
}

static inline int
unresolved_vlink(ort *ort)
{
  return ort->n.nhs && nh_is_vlink(ort->n.nhs);
Ondřej Zajíček's avatar
Ondřej Zajíček committed
34 35 36
}

static inline struct mpnh *
Pavel Tvrdík's avatar
Pavel Tvrdík committed
37
new_nexthop(struct ospf_proto *p, ip_addr gw, struct iface *iface, byte weight)
Ondřej Zajíček's avatar
Ondřej Zajíček committed
38
{
39
  struct mpnh *nh = lp_alloc(p->nhpool, sizeof(struct mpnh));
Ondřej Zajíček's avatar
Ondřej Zajíček committed
40 41 42 43 44 45 46
  nh->gw = gw;
  nh->iface = iface;
  nh->next = NULL;
  nh->weight = weight;
  return nh;
}

47
/* Returns true if there are device nexthops in n */
48
static inline int
49
has_device_nexthops(const struct mpnh *n)
50
{
51 52 53 54 55
  for (; n; n = n->next)
    if (ipa_zero(n->gw))
      return 1;

  return 0;
56 57
}

58 59
/* Replace device nexthops with nexthops to gw */
static struct mpnh *
60
fix_device_nexthops(struct ospf_proto *p, const struct mpnh *n, ip_addr gw)
61
{
62 63 64 65
  struct mpnh *root1 = NULL;
  struct mpnh *root2 = NULL;
  struct mpnh **nn1 = &root1;
  struct mpnh **nn2 = &root2;
66

67 68 69
  if (!p->ecmp)
    return new_nexthop(p, gw, n->iface, n->weight);

70 71 72
  /* 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. */
73

74 75
  for (; n; n = n->next)
  {
76
    struct mpnh *nn = new_nexthop(p, ipa_zero(n->gw) ? gw : n->gw, n->iface, n->weight);
77

78 79 80 81 82 83 84 85 86 87
    if (ipa_zero(n->gw))
    {
      *nn1 = nn;
      nn1 = &(nn->next);
    }
    else
    {
      *nn2 = nn;
      nn2 = &(nn->next);
    }
88
  }
Ondřej Filip's avatar
Ondřej Filip committed
89

90
  return mpnh_merge(root1, root2, 1, 1, p->ecmp, p->nhpool);
91
}
92 93


94 95 96 97 98 99 100
/* 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);
}
101

102 103 104 105 106
/* Whether the ext route has ASBR/next_hop marked as preferred. */
static inline int
orta_pref(const orta *nf)
{
  return !!(nf->options & ORTA_PREF);
107 108
}

109 110
/* 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 */
111
static int
112
orta_prio(const orta *nf)
113 114 115 116 117 118 119 120 121 122 123 124 125 126 127
{
  /* 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;
}

128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144
/* 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.
 */
145
static int
146
orta_compare(const struct ospf_proto *p, const orta *new, const orta *old)
147
{
148 149
  int r;

150 151 152
  if (old->type == RTS_DUMMY)
    return 1;

153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173
  /* 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)
174
    return 1;
175 176 177 178 179
  if (nh_is_vlink(new->nhs))
    return -1;
  if (nh_is_vlink(old->nhs))
    return 1;

180

181
  if (p->ecmp)
182 183
    return 0;

184 185 186
  /* Prefer routes with higher Router ID, just to be more deterministic */
  if (new->rid > old->rid)
    return 1;
187

188 189
  return -1;
}
190

191 192 193 194 195 196
/*
 * 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
197
orta_compare_asbr(const struct ospf_proto *p, const orta *new, const orta *old)
198 199 200 201 202
{
  int r;

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

204
  if (!p->rfc1583)
205
  {
206 207
    r = epath_preferred(new) - epath_preferred(old);
    if (r) return r;
208 209
  }

210 211 212 213 214
  r = ((int) old->metric1) - ((int) new->metric1);
  if (r) return r;

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

217 218 219
  /* There is just one ASBR of that RID per area, so tie is not possible */
  return -1;
}
220

221 222 223 224 225 226
/*
 * 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
227
orta_compare_ext(const struct ospf_proto *p, const orta *new, const orta *old)
228 229
{
  int r;
230

231
  if (old->type == RTS_DUMMY)
232 233
    return 1;

234 235 236 237 238 239 240 241 242 243 244 245
  /* 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 */
246
  if (!p->rfc1583)
247 248 249 250 251 252 253 254 255 256
  {
    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;


257
  if (p->ecmp && p->merge_external)
258 259
    return 0;

260 261 262 263 264 265 266
  /*
   * 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))
267
    return 1;
268

269 270 271 272 273 274 275 276 277 278 279
  return -1;
}


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

static void
280
ort_merge(struct ospf_proto *p, ort *o, const orta *new)
281 282 283 284 285
{
  orta *old = &o->n;

  if (old->nhs != new->nhs)
  {
286 287
    old->nhs = mpnh_merge(old->nhs, new->nhs, old->nhs_reuse, new->nhs_reuse,
			  p->ecmp, p->nhpool);
288 289 290 291 292
    old->nhs_reuse = 1;
  }

  if (old->rid < new->rid)
    old->rid = new->rid;
293
}
294

295
static void
296
ort_merge_ext(struct ospf_proto *p, ort *o, const orta *new)
297 298 299 300 301
{
  orta *old = &o->n;

  if (old->nhs != new->nhs)
  {
302 303
    old->nhs = mpnh_merge(old->nhs, new->nhs, old->nhs_reuse, new->nhs_reuse,
			  p->ecmp, p->nhpool);
304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326
    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;
  }
}



327
static inline void
328
ri_install_net(struct ospf_proto *p, net_addr *net, const orta *new)
329
{
330
  ort *old = fib_get(&p->rtf, net);
331
  int cmp = orta_compare(p, new, &old->n);
332 333 334 335

  if (cmp > 0)
    ort_replace(old, new);
  else if (cmp == 0)
336
    ort_merge(p, old, new);
337 338
}

339
static inline void
340
ri_install_rt(struct ospf_area *oa, u32 rid, const orta *new)
341
{
342 343
  net_addr_ip4 nrid = net_from_rid(rid);
  ort *old = fib_get(&oa->rtr, (net_addr *) &nrid);
344 345 346 347 348 349
  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);
350
}
351

352
static inline void
353
ri_install_asbr(struct ospf_proto *p, u32 rid, const orta *new)
354
{
355 356 357
  net_addr_ip4 nrid = net_from_rid(rid);
  ort *old = fib_get(&p->backbone->rtr, (net_addr *) &nrid);

358
  if (orta_compare_asbr(p, new, &old->n) > 0)
359
    ort_replace(old, new);
360
}
Ondřej Filip's avatar
Ondřej Filip committed
361

362
static inline void
363
ri_install_ext(struct ospf_proto *p, net_addr *net, const orta *new)
364
{
365
  ort *old = fib_get(&p->rtf, net);
366
  int cmp = orta_compare_ext(p, new, &old->n);
367 368 369 370

  if (cmp > 0)
    ort_replace(old, new);
  else if (cmp == 0)
371
    ort_merge_ext(p, old, new);
372 373
}

374 375
static inline struct ospf_iface *
rt_pos_to_ifa(struct ospf_area *oa, int pos)
376
{
377
  struct ospf_iface *ifa;
378

379
  WALK_LIST(ifa, oa->po->iface_list)
380
    if (ifa->oa == oa && pos >= ifa->rt_pos_beg && pos < ifa->rt_pos_end)
381
      return ifa;
382

383 384 385
  return NULL;
}

386 387
static inline struct ospf_iface *
px_pos_to_ifa(struct ospf_area *oa, int pos)
388
{
389
  struct ospf_iface *ifa;
390

391
  WALK_LIST(ifa, oa->po->iface_list)
392
    if (ifa->oa == oa && pos >= ifa->px_pos_beg && pos < ifa->px_pos_end)
393
      return ifa;
394

395 396 397
  return NULL;
}

398

399
static void
400
add_network(struct ospf_area *oa, net_addr *net, int metric, struct top_hash_entry *en, int pos)
401
{
402 403
  struct ospf_proto *p = oa->po;

404 405 406 407 408 409 410 411
  orta nf = {
    .type = RTS_OSPF,
    .options = 0,
    .metric1 = metric,
    .metric2 = LSINFINITY,
    .tag = 0,
    .rid = en->lsa.rt,
    .oa = oa,
Ondřej Zajíček's avatar
Ondřej Zajíček committed
412
    .nhs = en->nhs
413
  };
414

415
  if (!ospf_valid_prefix(net))
Ondřej Zajíček's avatar
Ondřej Zajíček committed
416 417
  {
    log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
418
	p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
Ondřej Zajíček's avatar
Ondřej Zajíček committed
419 420 421
    return;
  }

422 423
  if (en == oa->rt)
  {
424
    /*
425 426 427
     * Local stub networks does 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.
428 429
     * Configured stubnets does not have any iface. They will
     * be removed in rt_sync().
430 431
     */

432
    struct ospf_iface *ifa;
433 434 435 436
    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;
  }

437
  ri_install_net(p, net, &nf);
438 439
}

440

441 442 443 444 445 446 447

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;
448
  int i;
449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472

  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);
473 474
  }

475 476
  /* 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))
477
    return;
478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497

  /* 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.
       */
498 499 500 501
      net_addr_ip4 net =
	NET_ADDR_IP4(ip4_from_u32(rtl.id & rtl.data), u32_masklen(rtl.data));

      add_network(oa, (net_addr *) &net, act->dist + rtl.metric, act, i);
502 503 504 505 506 507 508 509 510 511 512 513 514 515
      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);
  }
516 517
}

518 519 520 521 522
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;
523
  int i, cnt;
524 525 526

  if (ospf_is_v2(p))
  {
527 528 529 530
    net_addr_ip4 net =
      NET_ADDR_IP4(ip4_from_u32(act->lsa.id & ln->optx), u32_masklen(ln->optx));

    add_network(oa, (net_addr *) &net, act->dist, act, -1);
531 532 533 534 535 536 537 538 539 540 541 542
  }

  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)
543 544 545 546 547 548
{
  struct top_hash_entry *en, *src;
  struct ospf_lsa_prefix *px;
  u32 *buf;
  int i;

549
  WALK_SLIST(en, p->lsal)
550
  {
551
    if (en->lsa_type != LSA_T_PREFIX)
552 553 554 555 556 557 558 559 560
      continue;

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

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

    px = en->lsa_body;
561 562 563

    /* For router prefix-LSA, we would like to find the first router-LSA */
    if (px->ref_type == LSA_T_RT)
564
      src = ospf_hash_find_rt(p->gr, oa->areaid, px->ref_rt);
565
    else
566
      src = ospf_hash_find(p->gr, oa->areaid, px->ref_id, px->ref_rt, px->ref_type);
567 568 569 570

    if (!src)
      continue;

571 572 573 574
    /* Reachable in SPF */
    if (src->color != INSPF)
      continue;

575
    if ((src->lsa_type != LSA_T_RT) && (src->lsa_type != LSA_T_NET))
576 577 578 579
      continue;

    buf = px->rest;
    for (i = 0; i < px->pxcount; i++)
580 581 582 583
    {
      net_addr_ip6 net;
      u8 pxopts;
      u16 metric;
584

585
      buf = ospf_get_ipv6_prefix(buf, (net_addr *) &net, &pxopts, &metric);
586

587 588
      if (pxopts & OPT_PX_NU)
	continue;
589

590 591 592 593 594 595
      /* Store the first global address to use it later as a vlink endpoint */
      if ((pxopts & OPT_PX_LA) && ipa_zero(src->lb))
	src->lb = ipa_from_ip6(net.prefix);

      add_network(oa, (net_addr *) &net, src->dist + metric, src, i);
    }
596 597
  }
}
598

599
/* RFC 2328 16.1. calculating shortest paths for an area */
600
static void
601
ospf_rt_spfa(struct ospf_area *oa)
602
{
603 604
  struct ospf_proto *p = oa->po;
  struct top_hash_entry *act;
Ondřej Filip's avatar
Ondřej Filip committed
605 606
  node *n;

Ondřej Filip's avatar
Ondřej Filip committed
607 608
  if (oa->rt == NULL)
    return;
609 610
  if (oa->rt->lsa.age == LSA_MAXAGE)
    return;
611

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

614
  /* 16.1. (1) */
615
  init_list(&oa->cand);		/* Empty list of candidates */
Ondřej Filip's avatar
Ondřej Filip committed
616
  oa->trcap = 0;
617

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

Ondřej Filip's avatar
Ondřej Filip committed
620 621
  oa->rt->dist = 0;
  oa->rt->color = CANDIDATE;
622
  add_head(&oa->cand, &oa->rt->cn);
623
  DBG("RT LSA: rt: %R, id: %R, type: %u\n",
624
      oa->rt->lsa.rt, oa->rt->lsa.id, oa->rt->lsa_type);
625

Ondřej Filip's avatar
Ondřej Filip committed
626
  while (!EMPTY_LIST(oa->cand))
627
  {
Ondřej Filip's avatar
Ondřej Filip committed
628 629
    n = HEAD(oa->cand);
    act = SKIP_BACK(struct top_hash_entry, cn, n);
630 631
    rem_node(n);

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

Ondřej Filip's avatar
Ondřej Filip committed
635
    act->color = INSPF;
636
    switch (act->lsa_type)
637
    {
Ondřej Filip's avatar
Ondřej Filip committed
638
    case LSA_T_RT:
639
      spfa_process_rt(p, oa, act);
Ondřej Filip's avatar
Ondřej Filip committed
640
      break;
641

642 643
    case LSA_T_NET:
      spfa_process_net(p, oa, act);
Ondřej Filip's avatar
Ondřej Filip committed
644
      break;
645 646 647

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

651 652
  if (ospf_is_v3(p))
    spfa_process_prefixes(p, oa);
Ondřej Filip's avatar
Ondřej Filip committed
653 654 655
}

static int
Ondřej Zajíček's avatar
Ondřej Zajíček committed
656
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
657
{
658 659
  struct ospf_proto *p = oa->po;
  struct ospf_lsa_rt_walk rtl;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
660
  struct top_hash_entry *tmp;
661 662
  struct ospf_lsa_net *ln;
  u32 i, cnt;
Ondřej Filip's avatar
Ondřej Filip committed
663

Ondřej Zajíček's avatar
Ondřej Zajíček committed
664 665
  if (!en || !par) return 0;

Ondřej Zajíček's avatar
Ondřej Zajíček committed
666 667 668 669 670 671 672
  /* 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. */

673 674 675
  /* In OSPFv2, en->lb is set here. In OSPFv3, en->lb is just cleared here,
     it is set in process_prefixes() to any global addres in the area */

Ondřej Zajíček's avatar
Ondřej Zajíček committed
676
  en->lb = IPA_NONE;
677
  en->lb_id = 0;
678 679

  switch (en->lsa_type)
Ondřej Filip's avatar
Ondřej Filip committed
680
  {
681 682 683 684 685
  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
686
      {
687 688 689 690 691 692
      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
693
	{
694 695 696 697 698 699
	  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
700
	}
701 702 703 704 705 706
	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);
Ondřej Zajíček's avatar
Ondřej Zajíček committed
707
	if (tmp == par)
708 709
	  return 1;
	break;
Ondřej Filip's avatar
Ondřej Filip committed
710
      }
711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726
    }
    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
727 728 729 730
  }
  return 0;
}

731

732
/* RFC 2328 16.2. calculating inter-area routes */
Ondřej Filip's avatar
Ondřej Filip committed
733
static void
734
ospf_rt_sum(struct ospf_area *oa)
Ondřej Filip's avatar
Ondřej Filip committed
735
{
736
  struct ospf_proto *p = oa->po;
Ondřej Filip's avatar
Ondřej Filip committed
737
  struct top_hash_entry *en;
738
  net_addr net;
739
  u32 dst_rid, metric, options;
740
  ort *abr;
741
  int type;
742
  u8 pxopts;
743

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

746
  WALK_SLIST(en, p->lsal)
Ondřej Filip's avatar
Ondřej Filip committed
747
  {
748
    if ((en->lsa_type != LSA_T_SUM_RT) && (en->lsa_type != LSA_T_SUM_NET))
749
      continue;
750 751 752 753

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

754
    /* 16.2. (1a) */
Ondřej Filip's avatar
Ondřej Filip committed
755 756
    if (en->lsa.age == LSA_MAXAGE)
      continue;
757

758
    /* 16.2. (2) */
759
    if (en->lsa.rt == p->router_id)
Ondřej Filip's avatar
Ondřej Filip committed
760 761
      continue;

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

764
    if (en->lsa_type == LSA_T_SUM_NET)
Ondřej Filip's avatar
Ondřej Filip committed
765
    {
766
      lsa_parse_sum_net(en, ospf_is_v2(p), &net, &pxopts, &metric);
767

768
      if (!ospf_valid_prefix(&net))
Ondřej Zajíček's avatar
Ondřej Zajíček committed
769 770
      {
	log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
771
	    p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
Ondřej Zajíček's avatar
Ondřej Zajíček committed
772 773 774
	continue;
      }

775 776 777
      if (pxopts & OPT_PX_NU)
	continue;

778
      options = 0;
Ondřej Filip's avatar
Ondřej Filip committed
779 780
      type = ORT_NET;
    }
781
    else /* LSA_T_SUM_RT */
Ondřej Filip's avatar
Ondřej Filip committed
782
    {
783
      lsa_parse_sum_rt(en, ospf_is_v2(p), &dst_rid, &metric, &options);
784

785
      /* We don't want local router in ASBR routing table */
786
      if (dst_rid == p->router_id)
787
	continue;
788 789

      options |= ORTA_ASBR;
Ondřej Filip's avatar
Ondřej Filip committed
790 791
      type = ORT_ROUTER;
    }
792

793 794 795
    /* 16.2. (1b) */
    if (metric == LSINFINITY)
      continue;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
796

797
    /* 16.2. (4) */
798 799
    net_addr_ip4 nrid = net_from_rid(en->lsa.rt);
    abr = fib_find(&oa->rtr, (net_addr *) &nrid);
800 801
    if (!abr || !abr->n.type)
      continue;
Ondřej Filip's avatar
Ondřej Filip committed
802

803 804 805
    if (!(abr->n.options & ORTA_ABR))
      continue;

806 807 808 809
    /* This check is not mentioned in RFC 2328 */
    if (abr->n.type != RTS_OSPF)
      continue;

810 811 812 813 814 815 816 817 818
    /* 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,
Ondřej Zajíček's avatar
Ondřej Zajíček committed
819
      .nhs = abr->n.nhs
820 821 822
    };

    if (type == ORT_NET)
823
      ri_install_net(p, &net, &nf);
824 825
    else
      ri_install_rt(oa, dst_rid, &nf);
Ondřej Filip's avatar
Ondřej Filip committed
826
  }
827
}
828 829

/* RFC 2328 16.3. examining summary-LSAs in transit areas */
Ondřej Filip's avatar
Ondřej Filip committed
830
static void
831
ospf_rt_sum_tr(struct ospf_area *oa)
Ondřej Filip's avatar
Ondřej Filip committed
832
{
833 834
  struct ospf_proto *p = oa->po;
  struct ospf_area *bb = p->backbone;
Ondřej Filip's avatar
Ondřej Filip committed
835
  struct top_hash_entry *en;
836
  ort *re, *abr;
837
  u32 metric;
838

839 840
  if (!bb)
    return;
841

842
  WALK_SLIST(en, p->lsal)
Ondřej Filip's avatar
Ondřej Filip committed
843
  {
844
    if ((en->lsa_type != LSA_T_SUM_RT) && (en->lsa_type != LSA_T_SUM_NET))
845 846 847
      continue;

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

850
    /* 16.3 (1a) */
Ondřej Filip's avatar
Ondřej Filip committed
851 852
    if (en->lsa.age == LSA_MAXAGE)
      continue;
853

854
    /* 16.3 (2) */
855
    if (en->lsa.rt == p->router_id)
Ondřej Filip's avatar
Ondřej Filip committed
856 857
      continue;

858
    if (en->lsa_type == LSA_T_SUM_NET)
Ondřej Filip's avatar
Ondřej Filip committed
859
    {
860 861 862 863
      net_addr net;
      u8 pxopts;

      lsa_parse_sum_net(en, ospf_is_v2(p), &net, &pxopts, &metric);
864

865
      if (!ospf_valid_prefix(&net))
Ondřej Zajíček's avatar
Ondřej Zajíček committed
866 867
      {
	log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
868
	    p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
Ondřej Zajíček's avatar
Ondřej Zajíček committed
869 870 871
	continue;
      }

872 873 874
      if (pxopts & OPT_PX_NU)
	continue;

875
      re = fib_find(&p->rtf, &net);
Ondřej Filip's avatar
Ondřej Filip committed
876
    }
877
    else // en->lsa_type == LSA_T_SUM_RT
Ondřej Filip's avatar
Ondřej Filip committed
878
    {
879 880
      u32 dst_rid, options;

881 882
      lsa_parse_sum_rt(en, ospf_is_v2(p), &dst_rid, &metric, &options);

883 884
      net_addr_ip4 nrid = net_from_rid(dst_rid);
      re = fib_find(&bb->rtr, (net_addr *) &nrid);
Ondřej Filip's avatar
Ondřej Filip committed
885 886
    }

887 888 889
    /* 16.3 (1b) */
    if (metric == LSINFINITY)
      continue;
890

891 892 893
    /* 16.3 (3) */
    if (!re || !re->n.type)
      continue;
894

895 896
    if (re->n.oa->areaid != 0)
      continue;
897

898 899
    if ((re->n.type != RTS_OSPF) && (re->n.type != RTS_OSPF_IA))
      continue;
900

901
    /* 16.3. (4) */
902 903
    net_addr_ip4 nrid = net_from_rid(en->lsa.rt);
    abr = fib_find(&oa->rtr, (net_addr *) &nrid);
904 905
    if (!abr || !abr->n.type)
      continue;
906

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

909
    /* 16.3. (5) */
910
    if ((metric < re->n.metric1) ||
911
	((metric == re->n.metric1) && unresolved_vlink(re)))
Ondřej Filip's avatar
Ondřej Filip committed
912
    {
913
      /* We want to replace the next-hop even if the metric is equal
Ondřej Zajíček's avatar
Ondřej Zajíček committed
914 915 916 917 918
	 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() */

919
      re->n.metric1 = metric;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
920 921
      re->n.voa = oa;
      re->n.nhs = abr->n.nhs;
Ondřej Filip's avatar
Ondřej Filip committed
922 923
    }
  }
924
}
925

926 927 928 929
/* Decide about originating or flushing summary LSAs for condended area networks */
static int
decide_anet_lsa(struct ospf_area *oa, struct area_net *anet, struct ospf_area *anet_oa)
{
930 931
  /* 12.4.3.1. - for stub/NSSA areas, originating summary routes is configurable */
  if (!oa_is_ext(oa) && !oa->ac->summary)
932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947
    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)
{
948 949
  /* 12.4.3.1. - for stub/NSSA areas, originating summary routes is configurable */
  if (!oa_is_ext(oa) && !oa->ac->summary)
Ondřej Zajíček's avatar