proto/ospf/rt.c

   1 /*
   2  * BIRD -- OSPF
   3  *
   4  * (c) 2000--2004 Ondrej Filip <feela@network.cz>
   5  *
   6  * Can be freely distributed and used under the terms of the GNU GPL.
   7  */
   8
   9 #include "ospf.h"
  10
  11 static void add_cand(list * l, struct top_hash_entry *en,
  12                      struct top_hash_entry *par, u32 dist,
  13                      struct ospf_area *oa);
  14 static void calc_next_hop(struct ospf_area *oa,
  15                           struct top_hash_entry *en,
  16                           struct top_hash_entry *par);
  17 static void ospf_ext_spf(struct proto_ospf *po);
  18 static void rt_sync(struct proto_ospf *po);
  19
  20 /* In ospf_area->rtr we store paths to routers, but we use RID (and not IP address)
  21    as index, so we need to encapsulate RID to IP addresss */
  22 #ifdef OSPFv2
  23 #define ipa_from_rid(x) _MI(x)
  24 #else /* OSPFv3 */
  25 #define ipa_from_rid(x) _MI(0,0,0,x)
  26 #endif
  27
  28
  29 #ifdef OSPFv3
  30
  31 static inline u32 *
  32 get_ipv6_prefix(u32 *buf, ip_addr *addr, int *pxlen, u8 *pxopts, u16 *rest)
  33 {
  34   u8 pxl = (*buf >> 24);
  35   *pxopts = (*buf >> 16);
  36   *rest = *buf;
  37   *pxlen = pxl;
  38   buf++;
  39
  40   *addr = IPA_NONE;
  41
  42   if (pxl > 0)
  43     _I0(*addr) = *buf++;
  44   if (pxl > 32)
  45     _I1(*addr) = *buf++;
  46   if (pxl > 64)
  47     _I2(*addr) = *buf++;
  48   if (pxl > 96)
  49     _I3(*addr) = *buf++;
  50
  51   return buf;
  52 }
  53
  54 static inline u32 *
  55 get_ipv6_addr(u32 *buf, ip_addr *addr)
  56 {
  57   *addr = *(ip_addr *) buf;
  58   return buf + 4;
  59 }
  60
  61 #endif
  62
  63
  64 static void
  65 fill_ri(orta * orta)
  66 {
  67   orta->type = RTS_DUMMY;
  68   orta->options = 0;
  69   orta->oa = NULL;
  70   orta->metric1 = LSINFINITY;
  71   orta->metric2 = LSINFINITY;
  72   orta->nh = IPA_NONE;
  73   orta->ifa = NULL;
  74   orta->ar = NULL;
  75   orta->tag = 0;
  76 }
  77
  78 void
  79 ospf_rt_initort(struct fib_node *fn)
  80 {
  81   ort *ri = (ort *) fn;
  82   fill_ri(&ri->n);
  83   memcpy(&ri->o, &ri->n, sizeof(orta));
  84   ri->efn = NULL;
  85 }
  86
  87 /* If new is better return 1 */
  88
  89 /*
  90  * This is hard to understand:
  91  * If rfc1583 is set to 1, it work likes normal route_better()
  92  * But if it is set to 0, it prunes number of AS boundary
  93  * routes before it starts the router decision
  94  */
  95 static int
  96 ri_better(struct proto_ospf *po, orta * new, ort *nefn, orta * old, ort *oefn, int rfc1583)
  97 {
  98   int newtype = new->type;
  99   int oldtype = old->type;
 100
 101   if (old->type == RTS_DUMMY)
 102     return 1;
 103
 104   if (old->metric1 == LSINFINITY)
 105     return 1;
 106
 107   if (!rfc1583)
 108   {
 109     if ((new->type < RTS_OSPF_EXT1) && (new->oa->areaid == 0)) newtype = RTS_OSPF_IA;
 110     if ((old->type < RTS_OSPF_EXT2) && (old->oa->areaid == 0)) oldtype = RTS_OSPF_IA;
 111   }
 112
 113   if (newtype < oldtype)
 114     return 1;
 115
 116   if (newtype > oldtype)
 117     return 0;
 118
 119   /* Same type */
 120   if (new->type == RTS_OSPF_EXT2)
 121   {
 122     if (new->metric2 < old->metric2) return 1;
 123     if (new->metric2 > old->metric2) return 0;
 124   }
 125
 126   if (((new->type == RTS_OSPF_EXT2) || (new->type == RTS_OSPF_EXT1)) && (!po->rfc1583))
 127   {
 128     newtype = nefn->n.type;
 129     oldtype = oefn->n.type;
 130
 131     if (nefn->n.oa->areaid == 0) newtype = RTS_OSPF_IA;
 132     if (oefn->n.oa->areaid == 0) oldtype = RTS_OSPF_IA;
 133
 134     if (newtype < oldtype) return 1;
 135     if (newtype > oldtype) return 0;
 136   }
 137
 138   if (new->metric1 < old->metric1)
 139     return 1;
 140
 141   if (new->metric1 > old->metric1)
 142     return 0;
 143
 144   if (new->oa->areaid > old->oa->areaid) return 1;      /* Larger AREAID is preffered */
 145
 146   return 0;                     /* Old is shorter or same */
 147 }
 148
 149 static void
 150 ri_install(struct proto_ospf *po, ip_addr prefix, int pxlen, int dest,
 151            orta * new, ort * ipath)
 152 {
 153   struct ospf_area *oa = new->oa;
 154   ort *old;
 155
 156   if (dest == ORT_NET)
 157   {
 158     struct area_net *anet;
 159     old = (ort *) fib_get(&po->rtf, &prefix, pxlen);
 160     if (ri_better(po, new, ipath, &old->n, old->efn, 1))
 161     {
 162       memcpy(&old->n, new, sizeof(orta));
 163       old->efn = ipath;
 164       if ((new->type == RTS_OSPF) && (anet = (struct area_net *)fib_route(&oa->net_fib, prefix, pxlen)))
 165       {
 166         anet->active = 1;
 167         if (new->metric1 > anet->metric) anet->metric = new->metric1;
 168       }
 169     }
 170   }
 171   else
 172   {
 173     old = (ort *) fib_get(&oa->rtr, &prefix, pxlen);
 174
 175     if (ri_better(po, new, ipath, &old->n, old->efn, 1))
 176     {
 177       memcpy(&old->n, new, sizeof(orta));
 178       old->efn = ipath;
 179     }
 180   }
 181 }
 182
 183 static void
 184 add_network(struct ospf_area *oa, ip_addr px, int pxlen, int metric, struct top_hash_entry *en)
 185 {
 186   orta nf;
 187   nf.type = RTS_OSPF;
 188   nf.options = 0;
 189   nf.metric1 = metric;
 190   nf.metric2 = LSINFINITY;
 191   nf.tag = 0;
 192   nf.oa = oa;
 193   nf.ar = en;
 194   nf.nh = en->nh;
 195   nf.ifa = en->nhi;
 196
 197   /* FIXME check nf.ifa on stubs */
 198   ri_install(oa->po, px, pxlen, ORT_NET, &nf, NULL);
 199 }
 200
 201 #ifdef OSPFv3
 202 static void
 203 process_prefixes(struct ospf_area *oa)
 204 {
 205   struct proto_ospf *po = oa->po;
 206   struct proto *p = &po->proto;
 207   struct top_hash_entry *en, *src;
 208   struct ospf_lsa_prefix *px;
 209   ip_addr pxa;
 210   int pxlen;
 211   u8 pxopts;
 212   u16 metric;
 213   u32 *buf;
 214   int i;
 215
 216   WALK_SLIST(en, po->lsal)
 217   {
 218     if (en->lsa.type != LSA_T_PREFIX)
 219       continue;
 220
 221     if (en->domain != oa->areaid)
 222       continue;
 223
 224     if (en->lsa.age == LSA_MAXAGE)
 225       continue;
 226
 227     px = en->lsa_body;
 228     /* FIXME: for router LSA, we should find the first one */
 229     src = ospf_hash_find(po->gr, oa->areaid,
 230                          ((px->ref_type == LSA_T_RT) ? px->ref_rt : px->ref_id),
 231                          px->ref_rt, px->ref_type);
 232
 233     if (!src)
 234       continue;
 235
 236     if (src->lsa.age == LSA_MAXAGE)
 237       continue;
 238
 239     if ((src->lsa.type != LSA_T_RT) && (src->lsa.type != LSA_T_NET))
 240       continue;
 241
 242     buf = px->rest;
 243     for (i = 0; i < px->pxcount; i++)
 244       {
 245         buf = get_ipv6_prefix(buf, &pxa, &pxlen, &pxopts, &metric);
 246
 247         if (pxopts & OPT_PX_NU)
 248           continue;
 249
 250         add_network(oa, pxa, pxlen, src->dist + metric, src);
 251       }
 252   }
 253 }
 254 #endif
 255
 256 static void
 257 ospf_rt_spfa(struct ospf_area *oa)
 258 {
 259   u32 i, *rts;
 260   struct ospf_lsa_rt *rt;
 261   struct ospf_lsa_rt_link *rtl, *rr;
 262   struct proto *p = &oa->po->proto;
 263   struct proto_ospf *po = oa->po;
 264   struct ospf_lsa_net *ln;
 265   orta nf;
 266   struct ospf_iface *iface;
 267   struct top_hash_entry *act, *tmp;
 268   node *n;
 269
 270   if (oa->rt == NULL)
 271     return;
 272
 273   OSPF_TRACE(D_EVENTS, "Starting routing table calculation for area %R", oa->areaid);
 274
 275   if (oa->rt->dist != LSINFINITY)
 276     bug("Aging was not processed.");
 277
 278   /* 16.1. (1) */
 279   init_list(&oa->cand);         /* Empty list of candidates */
 280   oa->trcap = 0;
 281
 282   DBG("LSA db prepared, adding me into candidate list.\n");
 283
 284   oa->rt->dist = 0;
 285   oa->rt->color = CANDIDATE;
 286   add_head(&oa->cand, &oa->rt->cn);
 287   DBG("RT LSA: rt: %R, id: %R, type: %u\n",
 288       oa->rt->lsa.rt, oa->rt->lsa.id, oa->rt->lsa.type);
 289
 290   while (!EMPTY_LIST(oa->cand))
 291   {
 292     n = HEAD(oa->cand);
 293     act = SKIP_BACK(struct top_hash_entry, cn, n);
 294     rem_node(n);
 295
 296     DBG("Working on LSA: rt: %R, id: %R, type: %u\n",
 297         act->lsa.rt, act->lsa.id, act->lsa.type);
 298
 299     act->color = INSPF;
 300     switch (act->lsa.type)
 301     {
 302     case LSA_T_RT:
 303       /* FIXME - in OSPFv3 we should process all RT LSAs from that router */
 304       rt = (struct ospf_lsa_rt *) act->lsa_body;
 305       if (rt->options & OPT_RT_V)
 306         oa->trcap = 1;
 307
 308       /* FIXME - in OSPFv3, should we add all routers, or just ABRs an ASBRs? */
 309       if ((rt->options & OPT_RT_V) || (rt->options & OPT_RT_E))
 310         {
 311           nf.type = RTS_OSPF;
 312           nf.options = rt->options;
 313           nf.metric1 = act->dist;
 314           nf.metric2 = LSINFINITY;
 315           nf.tag = 0;
 316           nf.oa = oa;
 317           nf.ar = act;
 318           nf.nh = act->nh;
 319           nf.ifa = act->nhi;
 320           ri_install(po, ipa_from_rid(act->lsa.rt), MAX_PREFIX_LENGTH, ORT_ROUTER, &nf, NULL);
 321         }
 322
 323       rr = (struct ospf_lsa_rt_link *) (rt + 1);
 324       DBG("  Number of links: %u\n", rt->links);
 325       for (i = 0; i < lsa_rt_count(&act->lsa); i++)
 326       {
 327         tmp = NULL;
 328         rtl = (rr + i);
 329         DBG("     Working on link: %R (type: %u)  ", rtl->id, rtl->type);
 330         switch (rtl->type)
 331         {
 332 #ifdef OSPFv2
 333         case LSART_STUB:
 334           /*
 335            * This violates rfc2328! But it is mostly harmless.
 336            */
 337           DBG("\n");
 338
 339           nf.type = RTS_OSPF;
 340           nf.options = 0;
 341           nf.metric1 = act->dist + rtl->metric;
 342           nf.metric2 = LSINFINITY;
 343           nf.tag = 0;
 344           nf.oa = oa;
 345           nf.ar = act;
 346           nf.nh = act->nh;
 347           nf.ifa = act->nhi;
 348
 349           if (act == oa->rt)
 350           {
 351             struct ospf_iface *iff;
 352
 353             WALK_LIST(iff, po->iface_list)      /* Try to find corresponding interface */
 354             {
 355                if (iff->iface && (iff->type != OSPF_IT_VLINK) &&
 356                  (rtl->id == (ipa_to_u32(ipa_mkmask(iff->iface->addr->pxlen))
 357                  & ipa_to_u32(iff->iface->addr->prefix))))      /* No VLINK and IP must match */
 358                {
 359                  nf.ifa = iff;
 360                  break;
 361                }
 362             }
 363           }
 364
 365           if (!nf.ifa)
 366             continue;
 367
 368           ri_install(po, ipa_from_u32(rtl->id),
 369                      ipa_mklen(ipa_from_u32(rtl->data)), ORT_NET, &nf, NULL);
 370           break;
 371 #endif
 372         case LSART_NET:
 373 #ifdef OSPFv2
 374           /* In OSPFv2, rtl->id is IP addres of DR, router ID is not known */
 375           tmp = ospf_hash_find(po->gr, oa->areaid, rtl->id, 0, LSA_T_NET);
 376 #else /* OSPFv3 */
 377           tmp = ospf_hash_find(po->gr, oa->areaid, rtl->nif, rtl->id, LSA_T_NET);
 378 #endif
 379           if (tmp == NULL)
 380             DBG("Not found!\n");
 381           else
 382             DBG("Found. :-)\n");
 383           break;
 384
 385         case LSART_VLNK:
 386         case LSART_PTP:
 387           /* FIXME - in OSPFv3, find lowest LSA ID */
 388           tmp = ospf_hash_find(po->gr, oa->areaid, rtl->id, rtl->id, LSA_T_RT);
 389
 390           DBG("PTP found.\n");
 391           break;
 392         default:
 393           log("Unknown link type in router lsa. (rid = %R)", act->lsa.id);
 394           break;
 395         }
 396         if (tmp)
 397           DBG("Going to add cand, Mydist: %u, Req: %u\n",
 398               tmp->dist, act->dist + rtl->metric);
 399         add_cand(&oa->cand, tmp, act, act->dist + rtl->metric, oa);
 400       }
 401       break;
 402     case LSA_T_NET:
 403       ln = act->lsa_body;
 404
 405 #ifdef OSPFv2
 406       add_network(oa, ipa_and(ipa_from_u32(act->lsa.id), ln->netmask),
 407                   ipa_mklen(ln->netmask), act->dist, act);
 408 #endif
 409
 410       rts = (u32 *) (ln + 1);
 411       for (i = 0; i < lsa_net_count(&act->lsa); i++)
 412       {
 413         DBG("     Working on router %R ", rts[i]);
 414         /* FIXME - in OSPFv3, find any LSA ID */
 415         tmp = ospf_hash_find(po->gr, oa->areaid, rts[i], rts[i], LSA_T_RT);
 416         if (tmp != NULL)
 417           DBG("Found :-)\n");
 418         else
 419           DBG("Not found!\n");
 420         add_cand(&oa->cand, tmp, act, act->dist, oa);
 421       }
 422       break;
 423     }
 424   }
 425
 426 #ifdef OSPFv3
 427   process_prefixes(oa);
 428 #endif
 429
 430   /* Find new/lost VLINK peers */
 431   WALK_LIST(iface, po->iface_list)
 432   {
 433     if ((iface->type == OSPF_IT_VLINK) && (iface->voa == oa))
 434     {
 435       /* FIXME in OSPFv3, different LSAID */
 436       if ((tmp = ospf_hash_find(po->gr, oa->areaid, iface->vid, iface->vid, LSA_T_RT)) &&
 437         (!ipa_equal(tmp->lb, IPA_NONE)))
 438       {
 439         if ((iface->state != OSPF_IS_PTP) || (iface->iface != tmp->nhi->iface) || (!ipa_equal(iface->vip, tmp->lb)))
 440         {
 441           OSPF_TRACE(D_EVENTS, "Vlink peer %R found", tmp->lsa.id);
 442           ospf_iface_sm(iface, ISM_DOWN);
 443           iface->iface = tmp->nhi->iface;
 444           iface->vip = tmp->lb;
 445           ospf_iface_sm(iface, ISM_UP);
 446         }
 447       }
 448       else
 449       {
 450         if (iface->state > OSPF_IS_DOWN)
 451         {
 452           OSPF_TRACE(D_EVENTS, "Vlink peer %R lost", iface->vid);
 453           ospf_iface_sm(iface, ISM_DOWN);
 454         }
 455       }
 456     }
 457   }
 458 }
 459
 460 #if 0
 461 static int
 462 link_back(struct ospf_area *oa, struct top_hash_entry *fol, struct top_hash_entry *pre)
 463 {
 464   u32 i, *rts;
 465   struct ospf_lsa_net *ln;
 466   struct ospf_lsa_rt *rt;
 467   struct ospf_lsa_rt_link *rtl, *rr;
 468   struct proto_ospf *po = oa->po;
 469
 470   if (!pre) return 0;
 471   if (!fol) return 0;
 472   switch (fol->lsa.type)
 473   {
 474     case LSA_T_RT:
 475       rt = (struct ospf_lsa_rt *) fol->lsa_body;
 476       rr = (struct ospf_lsa_rt_link *) (rt + 1);
 477       for (i = 0; i < lsa_rt_count(&fol->lsa); i++)
 478       {
 479         rtl = (rr + i);
 480         switch (rtl->type)
 481         {
 482         case LSART_STUB:
 483           break;
 484         case LSART_NET:
 485           if (ospf_hash_find(po->gr, oa->areaid, rtl->id, rtl->id, LSA_T_NET) == pre)
 486           {
 487             fol->lb = ipa_from_u32(rtl->data);
 488             return 1;
 489           }
 490           break;
 491         case LSART_VLNK:
 492         case LSART_PTP:
 493           if (ospf_hash_find(po->gr, oa->areaid, rtl->id, rtl->id, LSA_T_RT) == pre)
 494           {
 495             fol->lb = ipa_from_u32(rtl->data);
 496             return 1;
 497           }
 498           break;
 499         default:
 500           log("Unknown link type in router lsa. (rid = %R)", fol->lsa.id);
 501           break;
 502         }
 503       }
 504       break;
 505     case LSA_T_NET:
 506       ln = fol->lsa_body;
 507       rts = (u32 *) (ln + 1);
 508       for (i = 0; i < lsa_net_count(&fol->lsa); i++)
 509       {
 510         if (ospf_hash_find(po->gr, oa->areaid, *(rts + i), *(rts + i), LSA_T_RT) == pre)
 511         {
 512           return 1;
 513         }
 514       }
 515       break;
 516     default:
 517       bug("Unknown lsa type. (id = %R)", fol->lsa.id);
 518   }
 519   return 0;
 520 }
 521 #endif
 522
 523 static void
 524 ospf_rt_sum_tr(struct ospf_area *oa)
 525 {
 526   struct proto *p = &oa->po->proto;
 527   struct proto_ospf *po = oa->po;
 528   struct ospf_area *bb = po->backbone;
 529   ip_addr ip, abrip;
 530   struct top_hash_entry *en;
 531   u32 dst_rid, metric, options;
 532   int pxlen = -1, type = -1;
 533   ort *re = NULL, *abr;
 534   orta nf;
 535
 536   if (!bb) return;
 537
 538   WALK_SLIST(en, po->lsal)
 539   {
 540     if ((en->lsa.type != LSA_T_SUM_RT) && (en->lsa.type != LSA_T_SUM_NET))
 541       continue;
 542
 543     if (en->domain != oa->areaid)
 544       continue;
 545
 546     if (en->lsa.age == LSA_MAXAGE)
 547       continue;
 548
 549     if (en->dist == LSINFINITY)
 550       continue;
 551
 552     if (en->lsa.rt == p->cf->global->router_id)
 553       continue;
 554
 555
 556     if (en->lsa.type == LSA_T_SUM_NET)
 557     {
 558 #ifdef OSPFv2
 559       struct ospf_lsa_sum *ls = en->lsa_body;
 560       pxlen = ipa_mklen(ls->netmask);
 561       ip = ipa_and(ipa_from_u32(en->lsa.id), ls->netmask);
 562 #else /* OSPFv3 */
 563       u8 pxopts;
 564       u16 rest;
 565       struct ospf_lsa_sum_net *ls = en->lsa_body;
 566       get_ipv6_prefix(ls->prefix, &ip, &pxlen, &pxopts, &rest);
 567
 568       if (pxopts & OPT_PX_NU)
 569         continue;
 570 #endif
 571
 572       metric = ls->metric & METRIC_MASK;
 573       options = 0;
 574       type = ORT_NET;
 575       re = (ort *) fib_find(&po->rtf, &ip, pxlen);
 576     }
 577     else if (en->lsa.type == LSA_T_SUM_RT)
 578     {
 579 #ifdef OSPFv2
 580       struct ospf_lsa_sum *ls = en->lsa_body;
 581       dst_rid = en->lsa.id;
 582       options = 0;
 583 #else /* OSPFv3 */
 584       struct ospf_lsa_sum_rt *ls = en->lsa_body;
 585       dst_rid = ls->drid;
 586       options = ls->options & OPTIONS_MASK;
 587 #endif
 588
 589       ip = ipa_from_rid(dst_rid);
 590       pxlen = MAX_PREFIX_LENGTH;
 591       metric = ls->metric & METRIC_MASK;
 592       options |= ORTA_ASBR;
 593       type = ORT_ROUTER;
 594       re = (ort *) fib_find(&bb->rtr, &ip, pxlen);
 595     }
 596
 597     if (!re) continue;
 598     if (re->n.oa->areaid != 0) continue;
 599     if ((re->n.type != RTS_OSPF) && (re->n.type != RTS_OSPF_IA)) continue;
 600
 601     abrip = ipa_from_rid(en->lsa.rt);
 602
 603     abr = fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH);
 604     if (!abr) continue;
 605
 606     nf.type = re->n.type;
 607     nf.options = options;
 608     nf.metric1 = abr->n.metric1 + metric;
 609     nf.metric2 = LSINFINITY;
 610     nf.tag = 0;
 611     nf.oa = oa;
 612     nf.ar = abr->n.ar;
 613     nf.nh = abr->n.nh;
 614     nf.ifa = abr->n.ifa;
 615     ri_install(po, ip, pxlen, type, &nf, NULL);
 616   }
 617 }
 618
 619
 620 static void
 621 ospf_rt_sum(struct ospf_area *oa)
 622 {
 623   struct proto_ospf *po = oa->po;
 624   struct proto *p = &po->proto;
 625   struct top_hash_entry *en;
 626   ip_addr ip, abrip;    /* abrIP is actually ID */
 627   u32 dst_rid, metric, options;
 628   struct area_net *anet;
 629   orta nf;
 630   ort *abr;
 631   int pxlen = -1, type = -1;
 632
 633   OSPF_TRACE(D_EVENTS, "Starting routing table calculation for inter-area (area %R)", oa->areaid);
 634
 635   WALK_SLIST(en, po->lsal)
 636   {
 637     if ((en->lsa.type != LSA_T_SUM_RT) && (en->lsa.type != LSA_T_SUM_NET))
 638       continue;
 639
 640     if (en->domain != oa->areaid)
 641       continue;
 642
 643     /* Page 169 (1) */
 644     if (en->lsa.age == LSA_MAXAGE)
 645       continue;
 646
 647     /* Page 169 (2) */
 648     if (en->lsa.rt == p->cf->global->router_id)
 649       continue;
 650
 651
 652     if (en->lsa.type == LSA_T_SUM_NET)
 653     {
 654       struct ospf_area *oaa;
 655       int skip = 0;
 656
 657 #ifdef OSPFv2
 658       struct ospf_lsa_sum *ls = en->lsa_body;
 659       pxlen = ipa_mklen(ls->netmask);
 660       ip = ipa_and(ipa_from_u32(en->lsa.id), ls->netmask);
 661 #else /* OSPFv3 */
 662       u8 pxopts;
 663       u16 rest;
 664       struct ospf_lsa_sum_net *ls = en->lsa_body;
 665       get_ipv6_prefix(ls->prefix, &ip, &pxlen, &pxopts, &rest);
 666
 667       if (pxopts & OPT_PX_NU)
 668         continue;
 669 #endif
 670
 671       metric = ls->metric & METRIC_MASK;
 672       options = 0;
 673       type = ORT_NET;
 674
 675       /* Page 169 (3) */
 676       WALK_LIST(oaa, po->area_list)
 677       {
 678         if ((anet = fib_find(&oaa->net_fib, &ip, pxlen)) && anet->active)
 679         {
 680           skip = 1;
 681           break;
 682         }
 683       }
 684       if (skip) continue;
 685     }
 686     else
 687     {
 688 #ifdef OSPFv2
 689       struct ospf_lsa_sum *ls = en->lsa_body;
 690       dst_rid = en->lsa.id;
 691       options = 0;
 692 #else /* OSPFv3 */
 693       struct ospf_lsa_sum_rt *ls = en->lsa_body;
 694       dst_rid = ls->drid;
 695       options = ls->options & OPTIONS_MASK;
 696 #endif
 697
 698       ip = ipa_from_rid(dst_rid);
 699       pxlen = MAX_PREFIX_LENGTH;
 700       metric = ls->metric & METRIC_MASK;
 701       options |= ORTA_ASBR;
 702       type = ORT_ROUTER;
 703     }
 704
 705     /* Page 169 (1) */
 706     if (metric == LSINFINITY)
 707       continue;
 708
 709     /* Page 169 (4) */
 710     abrip = ipa_from_rid(en->lsa.rt);
 711     if (!(abr = (ort *) fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH))) continue;
 712     if (abr->n.metric1 == LSINFINITY) continue;
 713     if (!(abr->n.options & ORTA_ABR)) continue;
 714
 715     nf.type = RTS_OSPF_IA;
 716     nf.options = options;
 717     nf.metric1 = abr->n.metric1 + metric;
 718     nf.metric2 = LSINFINITY;
 719     nf.tag = 0;
 720     nf.oa = oa;
 721     nf.ar = abr->n.ar;
 722     nf.nh = abr->n.nh;
 723     nf.ifa = abr->n.ifa;
 724     ri_install(po, ip, pxlen, type, &nf, NULL);
 725   }
 726 }
 727
 728 /**
 729  * ospf_rt_spf - calculate internal routes
 730  * @po: OSPF protocol
 731  *
 732  * Calculation of internal paths in an area is described in 16.1 of RFC 2328.
 733  * It's based on Dijkstra's shortest path tree algorithms.
 734  * This function is invoked from ospf_disp().
 735  */
 736 void
 737 ospf_rt_spf(struct proto_ospf *po)
 738 {
 739   struct proto *p = &po->proto;
 740   struct ospf_area *oa;
 741   ort *ri;
 742   struct area_net *anet;
 743
 744   if (po->areano == 0) return;
 745
 746   po->cleanup = 1;
 747
 748   OSPF_TRACE(D_EVENTS, "Starting routing table calculation");
 749
 750   /* 16. (1) - Invalidate old routing table */
 751   FIB_WALK(&po->rtf, nftmp)
 752   {
 753     ri = (ort *) nftmp;
 754     memcpy(&ri->o, &ri->n, sizeof(orta));       /* Backup old data */
 755     fill_ri(&ri->n);
 756   }
 757   FIB_WALK_END;
 758
 759
 760   WALK_LIST(oa, po->area_list)
 761   {
 762     FIB_WALK(&oa->rtr, nftmp)
 763     {
 764       ri = (ort *) nftmp;
 765       memcpy(&ri->o, &ri->n, sizeof(orta));     /* Backup old data */
 766       fill_ri(&ri->n);
 767     }
 768     FIB_WALK_END;
 769
 770     FIB_WALK(&oa->net_fib, nftmp)
 771     {
 772       anet = (struct area_net *) nftmp;
 773       anet->active = 0;
 774       anet->metric = 1;
 775     }
 776     FIB_WALK_END;
 777
 778     /* 16. (2) */
 779     ospf_rt_spfa(oa);
 780   }
 781
 782   /* 16. (3) */
 783   if ((po->areano == 1) || (!po->backbone))
 784   {
 785     ospf_rt_sum(HEAD(po->area_list));
 786   }
 787   else
 788   {
 789     ospf_rt_sum(po->backbone);
 790   }
 791
 792   /* 16. (4) */
 793   WALK_LIST(oa, po->area_list)
 794   {
 795     if (oa->trcap && (oa->areaid != 0))
 796     {
 797       ospf_rt_sum_tr(oa);
 798       break;
 799     }
 800   }
 801
 802   /* 16. (5) */
 803   ospf_ext_spf(po);
 804
 805   rt_sync(po);
 806
 807   po->calcrt = 0;
 808 }
 809
 810 /**
 811  * ospf_ext_spf - calculate external paths
 812  * @po: protocol
 813  *
 814  * After routing table for any area is calculated, calculation of external
 815  * path is invoked. This process is described in 16.4 of RFC 2328.
 816  * Inter- and Intra-area paths are always prefered over externals.
 817  */
 818 static void
 819 ospf_ext_spf(struct proto_ospf *po)
 820 {
 821   ort *nf1, *nf2, *nfh;
 822   orta nfa;
 823   struct top_hash_entry *en;
 824   struct proto *p = &po->proto;
 825   struct ospf_lsa_ext *le;
 826   int pxlen, ebit, rt_fwaddr_valid;
 827   ip_addr ip, nh, rtid, rt_fwaddr;
 828   struct ospf_iface *nhi = NULL;
 829   u32 br_metric, rt_metric, rt_tag;
 830   neighbor *nn;
 831   struct ospf_area *atmp;
 832
 833   OSPF_TRACE(D_EVENTS, "Starting routing table calculation for ext routes");
 834
 835   WALK_SLIST(en, po->lsal)
 836   {
 837     /* 16.4. (1) */
 838     if (en->lsa.type != LSA_T_EXT)
 839       continue;
 840     if (en->lsa.age == LSA_MAXAGE)
 841       continue;
 842
 843     /* 16.4. (2) */
 844     if (en->lsa.rt == p->cf->global->router_id)
 845       continue;
 846
 847     DBG("%s: Working on LSA. ID: %R, RT: %R, Type: %u\n",
 848         p->name, en->lsa.id, en->lsa.rt, en->lsa.type);
 849
 850     le = en->lsa_body;
 851
 852     rt_metric = le->metric & METRIC_MASK;
 853     ebit = le->metric & LSA_EXT_EBIT;
 854
 855     if (rt_metric == LSINFINITY)
 856       continue;
 857
 858 #ifdef OSPFv2
 859     ip = ipa_and(ipa_from_u32(en->lsa.id), le->netmask);
 860     pxlen = ipa_mklen(le->netmask);
 861     rt_fwaddr = le->fwaddr;
 862     rt_fwaddr_valid = !ipa_equal(rt_fwaddr, IPA_NONE);
 863     rt_tag = le->tag;
 864 #else /* OSPFv3 */
 865     u8 pxopts;
 866     u16 rest;
 867     u32 *buf = le->rest;
 868     buf = get_ipv6_prefix(buf, &ip, &pxlen, &pxopts, &rest);
 869
 870     if (pxopts & OPT_PX_NU)
 871       continue;
 872
 873     rt_fwaddr_valid = le->metric & LSA_EXT_FBIT;
 874     if (rt_fwaddr_valid)
 875       buf = get_ipv6_addr(buf, &rt_fwaddr);
 876     else
 877       rt_fwaddr = IPA_NONE;
 878
 879     if (le->metric & LSA_EXT_TBIT)
 880       rt_tag = *buf++;
 881     else
 882       rt_tag = 0;
 883 #endif
 884
 885     if (pxlen < 0)
 886     {
 887       log("%s: Invalid mask in LSA. ID: %R, RT: %R, Type: %u",
 888           p->name, en->lsa.id, en->lsa.rt, en->lsa.type);
 889       continue;
 890     }
 891     nhi = NULL;
 892     nh = IPA_NONE;
 893
 894     /* 16.4. (3) */
 895     rtid = ipa_from_rid(en->lsa.rt);
 896     nf1 = NULL;
 897     WALK_LIST(atmp, po->area_list)
 898     {
 899       nfh = fib_find(&atmp->rtr, &rtid, MAX_PREFIX_LENGTH);
 900       if (nfh == NULL) continue;
 901       if (nf1 == NULL) nf1 = nfh;
 902       else if (ri_better(po, &nfh->n, NULL, &nf1->n, NULL, po->rfc1583)) nf1 = nfh;
 903     }
 904
 905     if (!nf1)
 906       continue;                 /* No AS boundary router found */
 907
 908     if (nf1->n.metric1 == LSINFINITY)
 909       continue;                 /* distance is INF */
 910
 911     if (!(nf1->n.options & ORTA_ASBR))
 912       continue;                 /* It is not ASBR */
 913
 914     if (!rt_fwaddr_valid)
 915     {
 916       nh = nf1->n.nh;
 917       nhi = nf1->n.ifa;
 918       nfh = nf1;
 919       br_metric = nf1->n.metric1;
 920     }
 921     else
 922     {
 923       nf2 = fib_route(&po->rtf, rt_fwaddr, MAX_PREFIX_LENGTH);
 924
 925       if (!nf2)
 926       {
 927         DBG("Cannot find network route (GW=%I)\n", rt_fwaddr);
 928         continue;
 929       }
 930
 931       if ((nn = neigh_find(p, &rt_fwaddr, 0)) != NULL)
 932       {
 933         nh = rt_fwaddr;
 934         nhi = ospf_iface_find(po, nn->iface);
 935       }
 936       else
 937       {
 938         nh = nf2->n.nh;
 939         nhi = nf2->n.ifa;
 940       }
 941
 942       br_metric = nf2->n.metric1;
 943       if (br_metric == LSINFINITY)
 944         continue;                       /* distance is INF */
 945     }
 946
 947     if (ebit)
 948     {
 949       nfa.type = RTS_OSPF_EXT2;
 950       nfa.metric1 = br_metric;
 951       nfa.metric2 = rt_metric;
 952     }
 953     else
 954     {
 955       nfa.type = RTS_OSPF_EXT1;
 956       nfa.metric1 = br_metric + rt_metric;
 957       nfa.metric2 = LSINFINITY;
 958     }
 959
 960     nfa.options = 0;
 961     nfa.tag = rt_tag;
 962     nfa.oa = (po->backbone == NULL) ? HEAD(po->area_list) : po->backbone;
 963     nfa.ar = nf1->n.ar;
 964     nfa.nh = nh;
 965     nfa.ifa = nhi;
 966     ri_install(po, ip, pxlen, ORT_NET, &nfa, nfh);
 967   }
 968
 969 }
 970
 971 /* Add LSA into list of candidates in Dijkstra's algorithm */
 972 static void
 973 add_cand(list * l, struct top_hash_entry *en, struct top_hash_entry *par,
 974          u32 dist, struct ospf_area *oa)
 975 {
 976   node *prev, *n;
 977   int added = 0;
 978   struct top_hash_entry *act;
 979
 980   /* 16.1. (2b) */
 981   if (en == NULL)
 982     return;
 983   if (en->lsa.age == LSA_MAXAGE)
 984     return;
 985
 986 #ifdef OSPFv3
 987   if (en->lsa.type == LSA_T_RT)
 988     {
 989       struct ospf_lsa_rt *rt = en->lsa_body;
 990       if (!(rt->options & OPT_V6) || !(rt->options & OPT_R))
 991         return;
 992     }
 993 #endif
 994
 995   /* 16.1. (2c) */
 996   if (en->color == INSPF)
 997     return;
 998
 999   /* 16.1. (2d) */
1000   if (dist >= en->dist)
1001     return;
1002   /*
1003    * FIXME The line above (=) is not a bug, but we don't support multiple
1004    * next hops. I'll start as soon as nest will
1005    */
1006
1007   /* FIXME - fix link_back()
1008   if (!link_back(oa, en, par))
1009     return;
1010   */
1011
1012   DBG("     Adding candidate: rt: %R, id: %R, type: %u\n",
1013       en->lsa.rt, en->lsa.id, en->lsa.type);
1014
1015   calc_next_hop(oa, en, par);
1016
1017   if (!en->nhi)
1018     return;                     /* We cannot find next hop, ignore it */
1019
1020   if (en->color == CANDIDATE)
1021   {                             /* We found a shorter path */
1022     rem_node(&en->cn);
1023   }
1024   en->dist = dist;
1025   en->color = CANDIDATE;
1026
1027   prev = NULL;
1028
1029   if (EMPTY_LIST(*l))
1030   {
1031     add_head(l, &en->cn);
1032   }
1033   else
1034   {
1035     WALK_LIST(n, *l)
1036     {
1037       act = SKIP_BACK(struct top_hash_entry, cn, n);
1038       if ((act->dist > dist) ||
1039           ((act->dist == dist) && (act->lsa.type == LSA_T_NET)))
1040       /* FIXME - shouldn't be here LSA_T_RT ??? */
1041       {
1042         if (prev == NULL)
1043           add_head(l, &en->cn);
1044         else
1045           insert_node(&en->cn, prev);
1046         added = 1;
1047         break;
1048       }
1049       prev = n;
1050     }
1051
1052     if (!added)
1053     {
1054       add_tail(l, &en->cn);
1055     }
1056   }
1057 }
1058
1059
1060 static inline int
1061 match_dr(struct ospf_iface *ifa, struct top_hash_entry *en)
1062 {
1063 #ifdef OSPFv2
1064   return (ifa->drid == en->lsa.rt) && (ipa_to_u32(ifa->drip) == en->lsa.id);
1065 #else /* OSPFv3 */
1066   return (ifa->drid == en->lsa.rt) && (ifa->dr_iface_id == en->lsa.id);
1067 #endif
1068 }
1069
1070 static void
1071 calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
1072               struct top_hash_entry *par)
1073 {
1074   struct ospf_neighbor *neigh;
1075   struct proto *p = &oa->po->proto;
1076   struct proto_ospf *po = oa->po;
1077   struct ospf_iface *ifa;
1078
1079   en->nhi = NULL;
1080   en->nh = IPA_NONE;
1081
1082   /* 16.1.1. The next hop calculation */
1083   DBG("     Next hop called.\n");
1084   if (ipa_equal(par->nh, IPA_NONE))
1085   {
1086     DBG("     Next hop calculating for id: %R rt: %R type: %u\n",
1087         en->lsa.id, en->lsa.rt, en->lsa.type);
1088
1089     /* The parent vertex is the root */
1090     if (par == oa->rt)
1091     {
1092       if (en->lsa.type == LSA_T_NET)
1093       {
1094         WALK_LIST(ifa, po->iface_list)
1095           if (match_dr(ifa, en))
1096           {
1097               en->nhi = ifa;
1098               return;
1099           }
1100         return;
1101       }
1102       else
1103       {
1104         if ((neigh = find_neigh_noifa(po, en->lsa.rt)) == NULL)
1105           return;
1106         en->nhi = neigh->ifa;
1107         en->nh = neigh->ip;
1108         /* Yes, neighbor is it's own next hop */
1109         return;
1110       }
1111     }
1112
1113     /* The parent vertex is a network that directly connects the
1114        calculating router to the destination router. */
1115     if (par->lsa.type == LSA_T_NET)
1116     {
1117       if (en->lsa.type == LSA_T_NET)
1118         bug("Parent for net is net?");
1119       if ((en->nhi = par->nhi) == NULL)
1120         bug("Did not find next hop interface for INSPF lsa!");
1121
1122       if ((neigh = find_neigh_noifa(po, en->lsa.rt)) == NULL)
1123         return;
1124       en->nhi = neigh->ifa;
1125       en->nh = neigh->ip;
1126       /* Yes, neighbor is it's own next hop */
1127       return;
1128     }
1129     else
1130     {                           /* Parent is some RT neighbor */
1131       log(L_ERR "Router's parent has no next hop. (EN=%R, PAR=%R)",
1132           en->lsa.id, par->lsa.id);
1133       /* I hope this would never happen */
1134       return;
1135     }
1136   }
1137   en->nhi = par->nhi;
1138   en->nh = par->nh;
1139   DBG("     Next hop calculated: %I.\n", en->nh);
1140 }
1141
1142 static void
1143 rt_sync(struct proto_ospf *po)
1144 {
1145   struct proto *p = &po->proto;
1146   struct fib_iterator fit;
1147   struct fib *fib = &po->rtf;
1148   ort *nf;
1149   struct ospf_area *oa, *oaa;
1150   struct area_net *anet;
1151   int flush;
1152
1153   OSPF_TRACE(D_EVENTS, "Starting routing table synchronisation");
1154
1155   DBG("Now syncing my rt table with nest's\n");
1156   FIB_ITERATE_INIT(&fit, fib);
1157 again1:
1158   FIB_ITERATE_START(fib, &fit, nftmp)
1159   {
1160     nf = (ort *) nftmp;
1161     check_sum_lsa(po, nf, ORT_NET);
1162     if (memcmp(&nf->n, &nf->o, sizeof(orta)))
1163     {                           /* Some difference */
1164       net *ne;
1165       rta a0;
1166       rte *e;
1167
1168       bzero(&a0, sizeof(a0));
1169
1170       a0.proto = p;
1171       a0.source = nf->n.type;
1172       a0.scope = SCOPE_UNIVERSE;
1173       a0.cast = RTC_UNICAST;
1174       a0.dest = RTD_ROUTER;
1175       a0.flags = 0;
1176       a0.aflags = 0;
1177       a0.iface = NULL;
1178       if (nf->n.ifa) a0.iface = nf->n.ifa->iface;
1179       a0.gw = nf->n.nh;
1180
1181       if ((!ipa_equal(nf->n.nh, IPA_NONE)) && (!neigh_find(p, &nf->n.nh, 0)))
1182       {
1183         int found = 0;
1184         struct ospf_iface *ifa;
1185         struct top_hash_entry *en;
1186         OSPF_TRACE(D_EVENTS, "Trying to find correct next hop %I/%d via %I", nf->fn.prefix, nf->fn.pxlen, nf->n.nh);
1187         WALK_LIST(ifa, po->iface_list)
1188         {
1189           if ((ifa->type == OSPF_IT_VLINK) && ipa_equal(ifa->vip, nf->n.nh))
1190           {
1191             /* FIXME in OSPFv3, may be different LSA ID */
1192             if ((en = ospf_hash_find(po->gr, ifa->voa->areaid, ifa->vid, ifa->vid, LSA_T_RT))
1193               && (!ipa_equal(en->nh, IPA_NONE)))
1194             {
1195               a0.gw = en->nh;
1196               found = 1;
1197             }
1198             break;
1199           }
1200         }
1201         if (!found) nf->n.metric1 = LSINFINITY; /* Delete it */
1202       }
1203
1204       if (ipa_equal(nf->n.nh, IPA_NONE)) a0.dest = RTD_DEVICE;
1205
1206       if (!a0.iface)    /* Still no match? Can this really happen? */
1207         nf->n.metric1 = LSINFINITY;
1208
1209       ne = net_get(p->table, nf->fn.prefix, nf->fn.pxlen);
1210       if (nf->n.metric1 < LSINFINITY)
1211       {
1212         e = rte_get_temp(&a0);
1213         e->u.ospf.metric1 = nf->n.metric1;
1214         e->u.ospf.metric2 = nf->n.metric2;
1215         e->u.ospf.tag = nf->n.tag;
1216         e->pflags = 0;
1217         e->net = ne;
1218         e->pref = p->preference;
1219         DBG("Mod rte type %d - %I/%d via %I on iface %s, met %d\n",
1220           a0.source, nf->fn.prefix, nf->fn.pxlen, a0.gw, a0.iface ? a0.iface->name : "(none)", nf->n.metric1);
1221         rte_update(p->table, ne, p, p, e);
1222       }
1223       else
1224       {
1225         rte_update(p->table, ne, p, p, NULL);
1226         FIB_ITERATE_PUT(&fit, nftmp);
1227         fib_delete(fib, nftmp);
1228         goto again1;
1229       }
1230     }
1231   }
1232   FIB_ITERATE_END(nftmp);
1233
1234   WALK_LIST(oa, po->area_list)
1235   {
1236     FIB_ITERATE_INIT(&fit, &oa->rtr);
1237 again2:
1238     FIB_ITERATE_START(&oa->rtr, &fit, nftmp)
1239     {
1240       nf = (ort *) nftmp;
1241       if (memcmp(&nf->n, &nf->o, sizeof(orta)))
1242       {                         /* Some difference */
1243         check_sum_lsa(po, nf, ORT_ROUTER);
1244         if (nf->n.metric1 >= LSINFINITY)
1245         {
1246           FIB_ITERATE_PUT(&fit, nftmp);
1247           fib_delete(&oa->rtr, nftmp);
1248           goto again2;
1249         }
1250       }
1251     }
1252     FIB_ITERATE_END(nftmp);
1253
1254     /* Check condensed summary LSAs */
1255     FIB_WALK(&oa->net_fib, nftmp)
1256     {
1257       flush = 1;
1258       anet = (struct area_net *) nftmp;
1259       if ((!anet->hidden) && anet->active)
1260         flush = 0;
1261
1262       WALK_LIST(oaa, po->area_list)
1263       {
1264         int fl = flush;
1265
1266         if (oaa == oa) continue;
1267
1268         if ((oa == po->backbone) && oaa->trcap) fl = 1;
1269
1270         if (oaa->stub) fl = 1;
1271
1272         if (fl) flush_sum_lsa(oaa, &anet->fn, ORT_NET);
1273         else originate_sum_lsa(oaa, &anet->fn, ORT_NET, anet->metric, 0);
1274       }
1275     }
1276     FIB_WALK_END;
1277
1278     /* Check default summary LSA for stub areas
1279      * just for router connected to backbone */
1280     if (po->backbone)
1281     {
1282       struct fib_node fnn;
1283
1284       fnn.prefix = IPA_NONE;
1285       fnn.pxlen = 0;
1286       if (oa->stub) originate_sum_lsa(oa, &fnn, ORT_NET, oa->stub, 0);
1287       else flush_sum_lsa(oa, &fnn, ORT_NET);
1288     }
1289   }
1290 }