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