Statistics
| Branch: | Revision:

iof-bird-daemon / proto / ospf / rt.c @ f623ab98

History | View | Annotate | Download (48.1 KB)

1 dfa9a53a Ondrej Filip
/*
2 1a61882d Ondrej Filip
 * 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 dfa9a53a Ondrej Filip
 */
8
9
#include "ospf.h"
10 5d3f5552 Ondrej Filip
11 b49e6f5a Ondrej Zajicek
static void add_cand(list * l, struct top_hash_entry *en, 
12
                     struct top_hash_entry *par, u32 dist,
13 e7b4948c Ondrej Zajicek
                     struct ospf_area *oa, int i);
14 1a61882d Ondrej Filip
static void rt_sync(struct proto_ospf *po);
15
16 c3226991 Ondrej Zajicek
/* In ospf_area->rtr we store paths to routers, but we use RID (and not IP address)
17 d82fc18d Ondrej Zajicek
   as index, so we need to encapsulate RID to IP address */
18 c3226991 Ondrej Zajicek
#ifdef OSPFv2
19
#define ipa_from_rid(x) _MI(x)
20
#else /* OSPFv3 */
21
#define ipa_from_rid(x) _MI(0,0,0,x)
22
#endif
23
24
25 57c574d8 Ondrej Zajicek
static inline void reset_ri(ort *ort)
26 1a61882d Ondrej Filip
{
27 57c574d8 Ondrej Zajicek
  bzero(&ort->n, sizeof(orta));
28 1a61882d Ondrej Filip
}
29 dfa9a53a Ondrej Filip
30
void
31 1a61882d Ondrej Filip
ospf_rt_initort(struct fib_node *fn)
32 a92847e7 Ondrej Filip
{
33 1a61882d Ondrej Filip
  ort *ri = (ort *) fn;
34 57c574d8 Ondrej Zajicek
  reset_ri(ri);
35
  ri->old_rta = NULL;
36 ed317862 Ondrej Zajicek
  ri->fn.x0 = ri->fn.x1 = 0;
37 1a61882d Ondrej Filip
}
38 a92847e7 Ondrej Filip
39 57c574d8 Ondrej Zajicek
static inline int
40
unresolved_vlink(struct mpnh *nhs)
41
{
42
  return nhs && !nhs->iface;
43
}
44
45
static inline struct mpnh *
46
new_nexthop(struct proto_ospf *po, ip_addr gw, struct iface *iface, unsigned char weight)
47
{
48
  struct mpnh *nh = lp_alloc(po->nhpool, sizeof(struct mpnh));
49
  nh->gw = gw;
50
  nh->iface = iface;
51
  nh->next = NULL;
52
  nh->weight = weight;
53
  return nh;
54
}
55
56
static inline struct mpnh *
57
copy_nexthop(struct proto_ospf *po, struct mpnh *src)
58
{
59
  struct mpnh *nh = lp_alloc(po->nhpool, sizeof(struct mpnh));
60
  nh->gw = src->gw;
61
  nh->iface = src->iface;
62
  nh->next = NULL;
63
  nh->weight = src->weight;
64
  return nh;
65
}
66
67 98ac6176 Ondrej Filip
68 3b89a232 Ondrej Zajicek
/* If new is better return 1 */
69 1a61882d Ondrej Filip
static int
70 3b89a232 Ondrej Zajicek
ri_better(struct proto_ospf *po, orta *new, orta *old)
71 1a61882d Ondrej Filip
{
72
  if (old->type == RTS_DUMMY)
73
    return 1;
74
75 3b89a232 Ondrej Zajicek
  if (new->type < old->type)
76
    return 1;
77
78
  if (new->type > old->type)
79
    return 0;
80
81
  if (new->metric1 < old->metric1)
82
    return 1;
83
84
  if (new->metric1 > old->metric1)
85
    return 0;
86
87
  return 0;
88
}
89
90
91 6384c7d7 Ondrej Zajicek
/* Whether the ASBR or the forward address destination is preferred
92
   in AS external route selection according to 16.4.1. */
93
static inline int
94
epath_preferred(orta *ep)
95
{
96
  return (ep->type == RTS_OSPF) && (ep->oa->areaid != 0);
97
}
98
99 3b89a232 Ondrej Zajicek
/* 16.4. (3), return 1 if new is better */
100
static int
101
ri_better_asbr(struct proto_ospf *po, orta *new, orta *old)
102
{
103 6384c7d7 Ondrej Zajicek
  if (old->type == RTS_DUMMY)
104
    return 1;
105 3b89a232 Ondrej Zajicek
106
  if (!po->rfc1583)
107 1a61882d Ondrej Filip
  {
108 3b89a232 Ondrej Zajicek
    int new_pref = epath_preferred(new);
109
    int old_pref = epath_preferred(old);
110
111
    if (new_pref > old_pref)
112
      return 1;
113
114
    if (new_pref < old_pref)
115
      return 0;
116 3b16080c Ondrej Filip
  }
117 98ac6176 Ondrej Filip
118 3b89a232 Ondrej Zajicek
  if (new->metric1 < old->metric1)
119 1a61882d Ondrej Filip
    return 1;
120
121 3b89a232 Ondrej Zajicek
  if (new->metric1 > old->metric1)
122 98ac6176 Ondrej Filip
    return 0;
123 1a61882d Ondrej Filip
124 3b89a232 Ondrej Zajicek
  /* Larger area ID is preferred */
125
  if (new->oa->areaid > old->oa->areaid)
126
    return 1;
127
128
  return 0;
129
}
130
131 ed317862 Ondrej Zajicek
static int
132
orta_prio(orta *nf)
133
{
134
  /* RFC 3103 2.5 (6e) priorities */
135
  u32 opts = nf->options & (ORTA_NSSA | ORTA_PROP);
136
137
  /* A Type-7 LSA with the P-bit set */
138
  if (opts == (ORTA_NSSA | ORTA_PROP))
139
    return 2;
140
141
  /* A Type-5 LSA */
142
  if (opts == 0)
143
    return 1;
144
145
  return 0;
146
}
147
148 3b89a232 Ondrej Zajicek
/* 16.4. (6), return 1 if new is better */
149
static int
150
ri_better_ext(struct proto_ospf *po, orta *new, orta *old)
151
{
152
  if (old->type == RTS_DUMMY)
153
    return 1;
154
155
  /* 16.4. (6a) */
156
  if (new->type < old->type)
157
    return 1;
158
159
  if (new->type > old->type)
160
    return 0;
161
162
  /* 16.4. (6b), same type */
163 a2d5b405 Ondrej Filip
  if (new->type == RTS_OSPF_EXT2)
164 98ac6176 Ondrej Filip
  {
165 3b89a232 Ondrej Zajicek
    if (new->metric2 < old->metric2)
166
      return 1;
167
168
    if (new->metric2 > old->metric2)
169
      return 0;
170 1a61882d Ondrej Filip
  }
171 98ac6176 Ondrej Filip
172 3b89a232 Ondrej Zajicek
  /* 16.4. (6c) */
173
  if (!po->rfc1583)
174 1a61882d Ondrej Filip
  {
175 3b89a232 Ondrej Zajicek
    u32 new_pref = new->options & ORTA_PREF;
176
    u32 old_pref = old->options & ORTA_PREF;
177 98ac6176 Ondrej Filip
178 3b89a232 Ondrej Zajicek
    if (new_pref > old_pref)
179
      return 1;
180 1a61882d Ondrej Filip
181 3b89a232 Ondrej Zajicek
    if (new_pref < old_pref)
182
      return 0;
183 1a61882d Ondrej Filip
  }
184
185 3b89a232 Ondrej Zajicek
  /* 16.4. (6d) */
186 1a61882d Ondrej Filip
  if (new->metric1 < old->metric1)
187
    return 1;
188
189
  if (new->metric1 > old->metric1)
190
    return 0;
191
192 ed317862 Ondrej Zajicek
  /* RFC 3103, 2.5. (6e) */
193
  int new_prio = orta_prio(new);
194
  int old_prio = orta_prio(old);
195
196
  if (new_prio > old_prio)
197
    return 1;
198
199
  if (old_prio > new_prio)
200
    return 0;
201
202
  /* make it more deterministic */
203
  if (new->rid > old->rid)
204
    return 1;
205 41b612c3 Ondrej Zajicek
206 3b89a232 Ondrej Zajicek
  return 0;
207
}
208 1a61882d Ondrej Filip
209 3b89a232 Ondrej Zajicek
static inline void
210
ri_install_net(struct proto_ospf *po, ip_addr prefix, int pxlen, orta *new)
211
{
212
  ort *old = (ort *) fib_get(&po->rtf, &prefix, pxlen);
213
  if (ri_better(po, new, &old->n))
214
    memcpy(&old->n, new, sizeof(orta));
215 a92847e7 Ondrej Filip
}
216
217 3b89a232 Ondrej Zajicek
static inline void
218
ri_install_rt(struct ospf_area *oa, u32 rid, orta *new)
219 aa1e082c Ondrej Filip
{
220 3b89a232 Ondrej Zajicek
  ip_addr addr = ipa_from_rid(rid);
221
  ort *old = (ort *) fib_get(&oa->rtr, &addr, MAX_PREFIX_LENGTH);
222
  if (ri_better(oa->po, new, &old->n))
223
    memcpy(&old->n, new, sizeof(orta));
224
}
225 1a61882d Ondrej Filip
226 3b89a232 Ondrej Zajicek
static inline void
227 6384c7d7 Ondrej Zajicek
ri_install_asbr(struct proto_ospf *po, ip_addr *addr, orta *new)
228 3b89a232 Ondrej Zajicek
{
229 6384c7d7 Ondrej Zajicek
  ort *old = (ort *) fib_get(&po->backbone->rtr, addr, MAX_PREFIX_LENGTH);
230
  if (ri_better_asbr(po, new, &old->n))
231 3b89a232 Ondrej Zajicek
    memcpy(&old->n, new, sizeof(orta));
232
}
233 98ac6176 Ondrej Filip
234 3b89a232 Ondrej Zajicek
static inline void
235 6384c7d7 Ondrej Zajicek
ri_install_ext(struct proto_ospf *po, ip_addr prefix, int pxlen, orta *new)
236 3b89a232 Ondrej Zajicek
{
237 6384c7d7 Ondrej Zajicek
  ort *old = (ort *) fib_get(&po->rtf, &prefix, pxlen);
238
  if (ri_better_ext(po, new, &old->n))
239
    memcpy(&old->n, new, sizeof(orta));
240 aa1e082c Ondrej Filip
}
241
242 e7b4948c Ondrej Zajicek
static inline struct ospf_iface *
243
rt_pos_to_ifa(struct ospf_area *oa, int pos)
244 e60d55be Ondrej Zajicek
{
245 e7b4948c Ondrej Zajicek
  struct ospf_iface *ifa;
246
  WALK_LIST(ifa, oa->po->iface_list)
247 9008579b Ondrej Zajicek
    if (ifa->oa == oa && pos >= ifa->rt_pos_beg && pos < ifa->rt_pos_end)
248 e7b4948c Ondrej Zajicek
      return ifa;
249 e60d55be Ondrej Zajicek
  return NULL;
250
}
251
252 e7b4948c Ondrej Zajicek
#ifdef OSPFv3
253
static inline struct ospf_iface *
254
px_pos_to_ifa(struct ospf_area *oa, int pos)
255 e60d55be Ondrej Zajicek
{
256 e7b4948c Ondrej Zajicek
  struct ospf_iface *ifa;
257
  WALK_LIST(ifa, oa->po->iface_list)
258 9008579b Ondrej Zajicek
    if (ifa->oa == oa && pos >= ifa->px_pos_beg && pos < ifa->px_pos_end)
259 e7b4948c Ondrej Zajicek
      return ifa;
260 e60d55be Ondrej Zajicek
  return NULL;
261
}
262
#endif
263
264 e7b4948c Ondrej Zajicek
265 1a61882d Ondrej Filip
static void
266 e7b4948c Ondrej Zajicek
add_network(struct ospf_area *oa, ip_addr px, int pxlen, int metric, struct top_hash_entry *en, int pos)
267 b49e6f5a Ondrej Zajicek
{
268 3b89a232 Ondrej Zajicek
  orta nf = {
269
    .type = RTS_OSPF,
270
    .options = 0,
271
    .metric1 = metric,
272
    .metric2 = LSINFINITY,
273
    .tag = 0,
274
    .rid = en->lsa.rt,
275
    .oa = oa,
276 57c574d8 Ondrej Zajicek
    .nhs = en->nhs
277 3b89a232 Ondrej Zajicek
  };
278 b49e6f5a Ondrej Zajicek
279 ab164971 Ondrej Zajicek
  if (pxlen < 0 || pxlen > MAX_PREFIX_LENGTH)
280
  {
281
    log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
282
        oa->po->proto.name, en->lsa.type, en->lsa.id, en->lsa.rt);
283
    return;
284
  }
285
286 e60d55be Ondrej Zajicek
  if (en == oa->rt)
287
  {
288
    /* 
289
     * Local stub networks does not have proper iface in en->nhi
290
     * (because they all have common top_hash_entry en).
291
     * We have to find iface responsible for that stub network.
292 e0a62ad0 Ondrej Zajicek
     * Configured stubnets does not have any iface. They will
293
     * be removed in rt_sync().
294 e60d55be Ondrej Zajicek
     */
295
296 e7b4948c Ondrej Zajicek
    struct ospf_iface *ifa;
297
#ifdef OSPFv2
298
    ifa = rt_pos_to_ifa(oa, pos);
299
#else /* OSPFv3 */
300
    ifa = px_pos_to_ifa(oa, pos);
301
#endif
302
303 57c574d8 Ondrej Zajicek
    nf.nhs = ifa ? new_nexthop(oa->po, IPA_NONE, ifa->iface, ifa->ecmp_weight) : NULL;
304 e60d55be Ondrej Zajicek
  }
305
306 3b89a232 Ondrej Zajicek
  ri_install_net(oa->po, px, pxlen, &nf);
307 b49e6f5a Ondrej Zajicek
}
308
309
#ifdef OSPFv3
310
static void
311
process_prefixes(struct ospf_area *oa)
312
{
313
  struct proto_ospf *po = oa->po;
314 ff2857b0 Ondrej Zajicek
  // struct proto *p = &po->proto;
315 b49e6f5a Ondrej Zajicek
  struct top_hash_entry *en, *src;
316
  struct ospf_lsa_prefix *px;
317
  ip_addr pxa;
318
  int pxlen;
319
  u8 pxopts;
320
  u16 metric;
321
  u32 *buf;
322
  int i;
323
324
  WALK_SLIST(en, po->lsal)
325
  {
326
    if (en->lsa.type != LSA_T_PREFIX)
327
      continue;
328
329
    if (en->domain != oa->areaid)
330
      continue;
331
332
    if (en->lsa.age == LSA_MAXAGE)
333
      continue;
334
335
    px = en->lsa_body;
336 9f0ba7b1 Ondrej Zajicek
337
    /* For router prefix-LSA, we would like to find the first router-LSA */
338
    if (px->ref_type == LSA_T_RT)
339
      src = ospf_hash_find_rt(po->gr, oa->areaid, px->ref_rt);
340
    else
341
      src = ospf_hash_find(po->gr, oa->areaid, px->ref_id, px->ref_rt, px->ref_type);
342 b49e6f5a Ondrej Zajicek
343
    if (!src)
344
      continue;
345
346 3b89a232 Ondrej Zajicek
    /* Reachable in SPF */
347
    if (src->color != INSPF)
348
      continue;
349
350 b49e6f5a Ondrej Zajicek
    if ((src->lsa.type != LSA_T_RT) && (src->lsa.type != LSA_T_NET))
351
      continue;
352
353
    buf = px->rest;
354
    for (i = 0; i < px->pxcount; i++)
355
      {
356 b66abe8e Ondrej Zajicek
        buf = lsa_get_ipv6_prefix(buf, &pxa, &pxlen, &pxopts, &metric);
357 b49e6f5a Ondrej Zajicek
358
        if (pxopts & OPT_PX_NU)
359
          continue;
360
361 3b89a232 Ondrej Zajicek
        /* Store the first global address to use it later as a vlink endpoint */
362
        if ((pxopts & OPT_PX_LA) && ipa_zero(src->lb))
363
          src->lb = pxa;
364
365 e7b4948c Ondrej Zajicek
        add_network(oa, pxa, pxlen, src->dist + metric, src, i);
366 b49e6f5a Ondrej Zajicek
      }
367
  }
368
}
369
#endif
370
371 9f0ba7b1 Ondrej Zajicek
372
static void
373
ospf_rt_spfa_rtlinks(struct ospf_area *oa, struct top_hash_entry *act, struct top_hash_entry *en)
374
{
375 e81b440f Ondrej Zajicek
  // struct proto *p = &oa->po->proto;
376 9f0ba7b1 Ondrej Zajicek
  struct proto_ospf *po = oa->po;
377 ab164971 Ondrej Zajicek
  ip_addr prefix UNUSED;
378
  int pxlen UNUSED, i;
379 9f0ba7b1 Ondrej Zajicek
380
  struct ospf_lsa_rt *rt = en->lsa_body;
381
  struct ospf_lsa_rt_link *rr = (struct ospf_lsa_rt_link *) (rt + 1);
382
383
  for (i = 0; i < lsa_rt_count(&en->lsa); i++)
384
    {
385
      struct ospf_lsa_rt_link *rtl = rr + i;
386
      struct top_hash_entry *tmp = NULL;
387
388
      DBG("     Working on link: %R (type: %u)  ", rtl->id, rtl->type);
389
      switch (rtl->type)
390
        {
391
#ifdef OSPFv2
392
        case LSART_STUB:
393 6d04ef89 Ondrej Zajicek
          /*
394
           * RFC 2328 in 16.1. (2a) says to handle stub networks in an
395
           * second phase after the SPF for an area is calculated. We get
396
           * the same result by handing them here because add_network()
397
           * will keep the best (not the first) found route.
398
           */
399 ab164971 Ondrej Zajicek
          prefix = ipa_from_u32(rtl->id & rtl->data);
400
          pxlen = ipa_mklen(ipa_from_u32(rtl->data));
401
          add_network(oa, prefix, pxlen, act->dist + rtl->metric, act, i);
402 9f0ba7b1 Ondrej Zajicek
          break;
403
#endif
404
405
        case LSART_NET:
406
#ifdef OSPFv2
407
          /* In OSPFv2, rtl->id is IP addres of DR, Router ID is not known */
408
          tmp = ospf_hash_find_net(po->gr, oa->areaid, rtl->id);
409
#else /* OSPFv3 */
410
          tmp = ospf_hash_find(po->gr, oa->areaid, rtl->nif, rtl->id, LSA_T_NET);
411
#endif
412
          break;
413
414
        case LSART_VLNK:
415
        case LSART_PTP:
416
          tmp = ospf_hash_find_rt(po->gr, oa->areaid, rtl->id);
417
          break;
418 e60d55be Ondrej Zajicek
419 9f0ba7b1 Ondrej Zajicek
        default:
420
          log("Unknown link type in router lsa. (rid = %R)", act->lsa.id);
421
          break;
422
        }
423 e60d55be Ondrej Zajicek
424 9f0ba7b1 Ondrej Zajicek
      if (tmp)
425
        DBG("Going to add cand, Mydist: %u, Req: %u\n",
426
            tmp->dist, act->dist + rtl->metric);
427 e7b4948c Ondrej Zajicek
      add_cand(&oa->cand, tmp, act, act->dist + rtl->metric, oa, i);
428 9f0ba7b1 Ondrej Zajicek
    }
429
}
430
431 3b89a232 Ondrej Zajicek
/* RFC 2328 16.1. calculating shortest paths for an area */
432 b49e6f5a Ondrej Zajicek
static void
433 a02c6c18 Ondrej Filip
ospf_rt_spfa(struct ospf_area *oa)
434 dfa9a53a Ondrej Filip
{
435 2e10a170 Ondrej Filip
  struct proto *p = &oa->po->proto;
436
  struct proto_ospf *po = oa->po;
437 9f0ba7b1 Ondrej Zajicek
  struct ospf_lsa_rt *rt;
438 d345cda5 Ondrej Filip
  struct ospf_lsa_net *ln;
439 98ac6176 Ondrej Filip
  struct top_hash_entry *act, *tmp;
440 ab164971 Ondrej Zajicek
  ip_addr prefix UNUSED;
441
  int pxlen UNUSED;
442 9f0ba7b1 Ondrej Zajicek
  u32 i, *rts;
443 98ac6176 Ondrej Filip
  node *n;
444
445 2e10a170 Ondrej Filip
  if (oa->rt == NULL)
446
    return;
447 102e3e0e Ondrej Filip
448 3aab39f5 Ondrej Zajicek
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation for area %R", oa->areaid);
449 1a61882d Ondrej Filip
450 c3226991 Ondrej Zajicek
  /* 16.1. (1) */
451 dfa9a53a Ondrej Filip
  init_list(&oa->cand);                /* Empty list of candidates */
452 2e10a170 Ondrej Filip
  oa->trcap = 0;
453 dfa9a53a Ondrej Filip
454 85195f1a Ondrej Filip
  DBG("LSA db prepared, adding me into candidate list.\n");
455
456 2e10a170 Ondrej Filip
  oa->rt->dist = 0;
457
  oa->rt->color = CANDIDATE;
458 85195f1a Ondrej Filip
  add_head(&oa->cand, &oa->rt->cn);
459 3aab39f5 Ondrej Zajicek
  DBG("RT LSA: rt: %R, id: %R, type: %u\n",
460
      oa->rt->lsa.rt, oa->rt->lsa.id, oa->rt->lsa.type);
461 dfa9a53a Ondrej Filip
462 2e10a170 Ondrej Filip
  while (!EMPTY_LIST(oa->cand))
463 dfa9a53a Ondrej Filip
  {
464 2e10a170 Ondrej Filip
    n = HEAD(oa->cand);
465
    act = SKIP_BACK(struct top_hash_entry, cn, n);
466 dfa9a53a Ondrej Filip
    rem_node(n);
467
468 3aab39f5 Ondrej Zajicek
    DBG("Working on LSA: rt: %R, id: %R, type: %u\n",
469
        act->lsa.rt, act->lsa.id, act->lsa.type);
470 85195f1a Ondrej Filip
471 2e10a170 Ondrej Filip
    act->color = INSPF;
472
    switch (act->lsa.type)
473 dfa9a53a Ondrej Filip
    {
474 2e10a170 Ondrej Filip
    case LSA_T_RT:
475
      rt = (struct ospf_lsa_rt *) act->lsa_body;
476 c3226991 Ondrej Zajicek
      if (rt->options & OPT_RT_V)
477 2e10a170 Ondrej Filip
        oa->trcap = 1;
478 b49e6f5a Ondrej Zajicek
479 3b89a232 Ondrej Zajicek
      /*
480
       * In OSPFv3, all routers are added to per-area routing
481
       * tables. But we use it just for ASBRs and ABRs. For the
482
       * purpose of the last step in SPF - prefix-LSA processing in
483
       * process_prefixes(), we use information stored in LSA db.
484
       */
485 6384c7d7 Ondrej Zajicek
      if (((rt->options & OPT_RT_E) || (rt->options & OPT_RT_B))
486
          && (act->lsa.rt != po->router_id))
487 3b89a232 Ondrej Zajicek
      {
488
        orta nf = {
489
          .type = RTS_OSPF,
490
          .options = rt->options,
491
          .metric1 = act->dist,
492
          .metric2 = LSINFINITY,
493
          .tag = 0,
494
          .rid = act->lsa.rt,
495
          .oa = oa,
496 57c574d8 Ondrej Zajicek
          .nhs = act->nhs
497 3b89a232 Ondrej Zajicek
        };
498
        ri_install_rt(oa, act->lsa.rt, &nf);
499
      }
500 b49e6f5a Ondrej Zajicek
501 c3226991 Ondrej Zajicek
#ifdef OSPFv2
502 9f0ba7b1 Ondrej Zajicek
      ospf_rt_spfa_rtlinks(oa, act, act);
503 c3226991 Ondrej Zajicek
#else /* OSPFv3 */
504 f623ab98 Ondrej Zajicek
      /* Errata 2078 to RFC 5340 4.8.1 - skip links from non-routing nodes */
505
      if ((act != oa->rt) && !(rt->options & OPT_R))
506
        break;
507
508 9f0ba7b1 Ondrej Zajicek
      for (tmp = ospf_hash_find_rt_first(po->gr, act->domain, act->lsa.rt);
509
           tmp; tmp = ospf_hash_find_rt_next(tmp))
510
        ospf_rt_spfa_rtlinks(oa, act, tmp);
511 c3226991 Ondrej Zajicek
#endif
512 b49e6f5a Ondrej Zajicek
513 2e10a170 Ondrej Filip
      break;
514
    case LSA_T_NET:
515
      ln = act->lsa_body;
516 b49e6f5a Ondrej Zajicek
517
#ifdef OSPFv2
518 ab164971 Ondrej Zajicek
      prefix = ipa_and(ipa_from_u32(act->lsa.id), ln->netmask);
519
      pxlen = ipa_mklen(ln->netmask);
520
      add_network(oa, prefix, pxlen, act->dist, act, -1);
521 b49e6f5a Ondrej Zajicek
#endif
522 1a61882d Ondrej Filip
523 2e10a170 Ondrej Filip
      rts = (u32 *) (ln + 1);
524 c3226991 Ondrej Zajicek
      for (i = 0; i < lsa_net_count(&act->lsa); i++)
525 2e10a170 Ondrej Filip
      {
526 3aab39f5 Ondrej Zajicek
        DBG("     Working on router %R ", rts[i]);
527 9f0ba7b1 Ondrej Zajicek
        tmp = ospf_hash_find_rt(po->gr, oa->areaid, rts[i]);
528 2e10a170 Ondrej Filip
        if (tmp != NULL)
529
          DBG("Found :-)\n");
530
        else
531
          DBG("Not found!\n");
532 e7b4948c Ondrej Zajicek
        add_cand(&oa->cand, tmp, act, act->dist, oa, -1);
533 2e10a170 Ondrej Filip
      }
534
      break;
535 dfa9a53a Ondrej Filip
    }
536 d345cda5 Ondrej Filip
  }
537 98ac6176 Ondrej Filip
538 b49e6f5a Ondrej Zajicek
#ifdef OSPFv3
539
  process_prefixes(oa);
540
#endif
541 98ac6176 Ondrej Filip
}
542
543
static int
544 9807690b Ondrej Zajicek
link_back(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry *par)
545 98ac6176 Ondrej Filip
{
546
  u32 i, *rts;
547
  struct ospf_lsa_net *ln;
548
  struct ospf_lsa_rt *rt;
549
  struct ospf_lsa_rt_link *rtl, *rr;
550 9807690b Ondrej Zajicek
  struct top_hash_entry *tmp;
551 86c84d76 Ondrej Filip
  struct proto_ospf *po = oa->po;
552 98ac6176 Ondrej Filip
553 9807690b Ondrej Zajicek
  if (!en || !par) return 0;
554
555 39847cda Ondrej Zajicek
  /* We should check whether there is a link back from en to par,
556
     this is used in SPF calc (RFC 2328 16.1. (2b)). According to RFC 2328
557
     note 23, we don't have to find the same link that is used for par
558
     to en, any link is enough. This we do for ptp links. For net-rt
559
     links, we have to find the same link to compute proper lb/lb_id,
560
     which may be later used as the next hop. */
561
562 3b89a232 Ondrej Zajicek
  /* In OSPFv2, en->lb is set here. In OSPFv3, en->lb is just cleared here,
563
     it is set in process_prefixes() to any global addres in the area */
564
565 9807690b Ondrej Zajicek
  en->lb = IPA_NONE;
566 6e806760 Ondrej Zajicek
#ifdef OSPFv3
567
  en->lb_id = 0;
568
#endif
569 9807690b Ondrej Zajicek
  switch (en->lsa.type)
570 98ac6176 Ondrej Filip
  {
571
    case LSA_T_RT:
572 9807690b Ondrej Zajicek
      rt = (struct ospf_lsa_rt *) en->lsa_body;
573 98ac6176 Ondrej Filip
      rr = (struct ospf_lsa_rt_link *) (rt + 1);
574 9807690b Ondrej Zajicek
      for (i = 0; i < lsa_rt_count(&en->lsa); i++)
575 98ac6176 Ondrej Filip
      {
576
        rtl = (rr + i);
577
        switch (rtl->type)
578
        {
579
        case LSART_STUB:
580
          break;
581
        case LSART_NET:
582 9807690b Ondrej Zajicek
#ifdef OSPFv2
583
          /* In OSPFv2, rtl->id is IP addres of DR, Router ID is not known */
584
          tmp = ospf_hash_find_net(po->gr, oa->areaid, rtl->id);
585
#else /* OSPFv3 */
586
          tmp = ospf_hash_find(po->gr, oa->areaid, rtl->nif, rtl->id, LSA_T_NET);
587
#endif
588
          if (tmp == par)
589 ba39197c Ondrej Zajicek
          {
590
#ifdef OSPFv2
591 cf0858c2 Ondrej Zajicek
            en->lb = ipa_from_u32(rtl->data);
592 6e806760 Ondrej Zajicek
#else /* OSPFv3 */
593
            en->lb_id = rtl->lif;
594 ba39197c Ondrej Zajicek
#endif
595
            return 1;
596
          }
597 9807690b Ondrej Zajicek
598 98ac6176 Ondrej Filip
          break;
599
        case LSART_VLNK:
600
        case LSART_PTP:
601 39847cda Ondrej Zajicek
          /* Not necessary the same link, see RFC 2328 [23] */
602 9807690b Ondrej Zajicek
          tmp = ospf_hash_find_rt(po->gr, oa->areaid, rtl->id);
603
          if (tmp == par)
604 98ac6176 Ondrej Filip
            return 1;
605 9807690b Ondrej Zajicek
606 98ac6176 Ondrej Filip
          break;
607
        default:
608 9807690b Ondrej Zajicek
          log(L_WARN "Unknown link type in router lsa. (rid = %R)", en->lsa.rt);
609 98ac6176 Ondrej Filip
          break;
610
        }
611
      }
612
      break;
613
    case LSA_T_NET:
614 9807690b Ondrej Zajicek
      ln = en->lsa_body;
615 98ac6176 Ondrej Filip
      rts = (u32 *) (ln + 1);
616 9807690b Ondrej Zajicek
      for (i = 0; i < lsa_net_count(&en->lsa); i++)
617 98ac6176 Ondrej Filip
      {
618 9807690b Ondrej Zajicek
        tmp = ospf_hash_find_rt(po->gr, oa->areaid, rts[i]);
619
        if (tmp == par)
620 98ac6176 Ondrej Filip
          return 1;
621
      }
622
      break;
623
    default:
624 9807690b Ondrej Zajicek
      bug("Unknown lsa type %x.", en->lsa.type);
625 98ac6176 Ondrej Filip
  }
626
  return 0;
627
}
628
629 3b89a232 Ondrej Zajicek
  
630
/* RFC 2328 16.2. calculating inter-area routes */
631 98ac6176 Ondrej Filip
static void
632 3b89a232 Ondrej Zajicek
ospf_rt_sum(struct ospf_area *oa)
633 98ac6176 Ondrej Filip
{
634
  struct proto_ospf *po = oa->po;
635 3b89a232 Ondrej Zajicek
  struct proto *p = &po->proto;
636 98ac6176 Ondrej Filip
  struct top_hash_entry *en;
637 3b89a232 Ondrej Zajicek
  ip_addr ip = IPA_NONE;
638
  u32 dst_rid = 0;
639
  u32 metric, options;
640
  ort *abr;
641 c3226991 Ondrej Zajicek
  int pxlen = -1, type = -1;
642 98ac6176 Ondrej Filip
643 3b89a232 Ondrej Zajicek
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation for inter-area (area %R)", oa->areaid);
644 98ac6176 Ondrej Filip
645 86c84d76 Ondrej Filip
  WALK_SLIST(en, po->lsal)
646 98ac6176 Ondrej Filip
  {
647 c3226991 Ondrej Zajicek
    if ((en->lsa.type != LSA_T_SUM_RT) && (en->lsa.type != LSA_T_SUM_NET))
648 86c84d76 Ondrej Filip
      continue;
649 c3226991 Ondrej Zajicek
650
    if (en->domain != oa->areaid)
651
      continue;
652
653 3b89a232 Ondrej Zajicek
    /* 16.2. (1a) */
654 98ac6176 Ondrej Filip
    if (en->lsa.age == LSA_MAXAGE)
655
      continue;
656 c3226991 Ondrej Zajicek
657 3b89a232 Ondrej Zajicek
    /* 16.2. (2) */
658 8a70a13e Ondrej Zajicek
    if (en->lsa.rt == po->router_id)
659 98ac6176 Ondrej Filip
      continue;
660
661 6384c7d7 Ondrej Zajicek
    /* 16.2. (3) is handled later in ospf_rt_abr() by resetting such rt entry */
662 3b89a232 Ondrej Zajicek
663 98ac6176 Ondrej Filip
    if (en->lsa.type == LSA_T_SUM_NET)
664
    {
665 c3226991 Ondrej Zajicek
#ifdef OSPFv2
666
      struct ospf_lsa_sum *ls = en->lsa_body;
667
      ip = ipa_and(ipa_from_u32(en->lsa.id), ls->netmask);
668 ab164971 Ondrej Zajicek
      pxlen = ipa_mklen(ls->netmask);
669 c3226991 Ondrej Zajicek
#else /* OSPFv3 */
670
      u8 pxopts;
671 b49e6f5a Ondrej Zajicek
      u16 rest;
672 c3226991 Ondrej Zajicek
      struct ospf_lsa_sum_net *ls = en->lsa_body;
673 b66abe8e Ondrej Zajicek
      lsa_get_ipv6_prefix(ls->prefix, &ip, &pxlen, &pxopts, &rest);
674 b49e6f5a Ondrej Zajicek
675 c3226991 Ondrej Zajicek
      if (pxopts & OPT_PX_NU)
676
        continue;
677
#endif
678
679 ab164971 Ondrej Zajicek
      if (pxlen < 0 || pxlen > MAX_PREFIX_LENGTH)
680
      {
681
        log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
682
            p->name, en->lsa.type, en->lsa.id, en->lsa.rt);
683
        continue;
684
      }
685
686 c3226991 Ondrej Zajicek
      metric = ls->metric & METRIC_MASK;
687
      options = 0;
688 98ac6176 Ondrej Filip
      type = ORT_NET;
689
    }
690 3b89a232 Ondrej Zajicek
    else /* LSA_T_SUM_RT */
691 98ac6176 Ondrej Filip
    {
692 c3226991 Ondrej Zajicek
#ifdef OSPFv2
693
      struct ospf_lsa_sum *ls = en->lsa_body;
694
      dst_rid = en->lsa.id;
695
      options = 0;
696
#else /* OSPFv3 */
697
      struct ospf_lsa_sum_rt *ls = en->lsa_body;
698
      dst_rid = ls->drid; 
699
      options = ls->options & OPTIONS_MASK;
700
#endif
701 6384c7d7 Ondrej Zajicek
      
702
      /* We don't want local router in ASBR routing table */
703
      if (dst_rid == po->router_id)
704
        continue;
705 c3226991 Ondrej Zajicek
706
      metric = ls->metric & METRIC_MASK;
707
      options |= ORTA_ASBR;
708 98ac6176 Ondrej Filip
      type = ORT_ROUTER;
709
    }
710 c3226991 Ondrej Zajicek
711 3b89a232 Ondrej Zajicek
    /* 16.2. (1b) */
712
    if (metric == LSINFINITY)
713
      continue;
714 99f5fc14 Ondrej Zajicek
715 3b89a232 Ondrej Zajicek
    /* 16.2. (4) */
716
    ip_addr abrip = ipa_from_rid(en->lsa.rt);
717
    abr = (ort *) fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH);
718
    if (!abr || !abr->n.type)
719
      continue;
720 98ac6176 Ondrej Filip
721 3b89a232 Ondrej Zajicek
    if (!(abr->n.options & ORTA_ABR))
722
      continue;
723
724 0ea8fb4a Ondrej Zajicek
    /* This check is not mentioned in RFC 2328 */
725
    if (abr->n.type != RTS_OSPF)
726
      continue;
727
728 3b89a232 Ondrej Zajicek
    /* 16.2. (5) */
729
    orta nf = {
730
      .type = RTS_OSPF_IA,
731
      .options = options,
732
      .metric1 = abr->n.metric1 + metric,
733
      .metric2 = LSINFINITY,
734
      .tag = 0,
735
      .rid = en->lsa.rt, /* ABR ID */
736
      .oa = oa,
737 57c574d8 Ondrej Zajicek
      .nhs = abr->n.nhs
738 3b89a232 Ondrej Zajicek
    };
739
740
    if (type == ORT_NET)
741
      ri_install_net(po, ip, pxlen, &nf);
742
    else
743
      ri_install_rt(oa, dst_rid, &nf);
744 98ac6176 Ondrej Filip
  }
745 fafe44b6 Ondrej Filip
}
746 3b89a232 Ondrej Zajicek
747
/* RFC 2328 16.3. examining summary-LSAs in transit areas */
748 98ac6176 Ondrej Filip
static void
749 3b89a232 Ondrej Zajicek
ospf_rt_sum_tr(struct ospf_area *oa)
750 98ac6176 Ondrej Filip
{
751 ab164971 Ondrej Zajicek
  struct proto *p = &oa->po->proto;
752 98ac6176 Ondrej Filip
  struct proto_ospf *po = oa->po;
753 3b89a232 Ondrej Zajicek
  struct ospf_area *bb = po->backbone;
754 6384c7d7 Ondrej Zajicek
  ip_addr abrip;
755 98ac6176 Ondrej Filip
  struct top_hash_entry *en;
756 6384c7d7 Ondrej Zajicek
  u32 dst_rid, metric;
757 3b89a232 Ondrej Zajicek
  ort *re = NULL, *abr;
758 fafe44b6 Ondrej Filip
759 3b89a232 Ondrej Zajicek
760
  if (!bb) return;
761 b8f17cf1 Ondrej Filip
762 86c84d76 Ondrej Filip
  WALK_SLIST(en, po->lsal)
763 98ac6176 Ondrej Filip
  {
764 c3226991 Ondrej Zajicek
    if ((en->lsa.type != LSA_T_SUM_RT) && (en->lsa.type != LSA_T_SUM_NET))
765
      continue;
766
767
    if (en->domain != oa->areaid)
768 86c84d76 Ondrej Filip
      continue;
769 c3226991 Ondrej Zajicek
770 3b89a232 Ondrej Zajicek
    /* 16.3 (1a) */
771 98ac6176 Ondrej Filip
    if (en->lsa.age == LSA_MAXAGE)
772
      continue;
773 c3226991 Ondrej Zajicek
774 3b89a232 Ondrej Zajicek
    /* 16.3 (2) */
775 8a70a13e Ondrej Zajicek
    if (en->lsa.rt == po->router_id)
776 98ac6176 Ondrej Filip
      continue;
777
778
    if (en->lsa.type == LSA_T_SUM_NET)
779
    {
780 6384c7d7 Ondrej Zajicek
      ip_addr ip;
781
      int pxlen;
782 c3226991 Ondrej Zajicek
#ifdef OSPFv2
783
      struct ospf_lsa_sum *ls = en->lsa_body;
784
      ip = ipa_and(ipa_from_u32(en->lsa.id), ls->netmask);
785 ab164971 Ondrej Zajicek
      pxlen = ipa_mklen(ls->netmask);
786 c3226991 Ondrej Zajicek
#else /* OSPFv3 */
787
      u8 pxopts;
788 b49e6f5a Ondrej Zajicek
      u16 rest;
789 c3226991 Ondrej Zajicek
      struct ospf_lsa_sum_net *ls = en->lsa_body;
790 b66abe8e Ondrej Zajicek
      lsa_get_ipv6_prefix(ls->prefix, &ip, &pxlen, &pxopts, &rest);
791 b49e6f5a Ondrej Zajicek
792 c3226991 Ondrej Zajicek
      if (pxopts & OPT_PX_NU)
793
        continue;
794
#endif
795
796 ab164971 Ondrej Zajicek
      if (pxlen < 0 || pxlen > MAX_PREFIX_LENGTH)
797
      {
798
        log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
799
            p->name, en->lsa.type, en->lsa.id, en->lsa.rt);
800
        continue;
801
      }
802
803 c3226991 Ondrej Zajicek
      metric = ls->metric & METRIC_MASK;
804 3b89a232 Ondrej Zajicek
      re = fib_find(&po->rtf, &ip, pxlen);
805 98ac6176 Ondrej Filip
    }
806 3b89a232 Ondrej Zajicek
    else // en->lsa.type == LSA_T_SUM_RT
807 98ac6176 Ondrej Filip
    {
808 c3226991 Ondrej Zajicek
#ifdef OSPFv2
809
      struct ospf_lsa_sum *ls = en->lsa_body;
810
      dst_rid = en->lsa.id;
811
#else /* OSPFv3 */
812
      struct ospf_lsa_sum_rt *ls = en->lsa_body;
813
      dst_rid = ls->drid; 
814
#endif
815
816
      metric = ls->metric & METRIC_MASK;
817 6384c7d7 Ondrej Zajicek
      ip_addr ip = ipa_from_rid(dst_rid);
818
      re = fib_find(&bb->rtr, &ip, MAX_PREFIX_LENGTH);
819 98ac6176 Ondrej Filip
    }
820
821 3b89a232 Ondrej Zajicek
    /* 16.3 (1b) */ 
822
    if (metric == LSINFINITY) 
823
      continue; 
824 1a61882d Ondrej Filip
825 3b89a232 Ondrej Zajicek
    /* 16.3 (3) */
826
    if (!re || !re->n.type)
827
      continue;
828 86c84d76 Ondrej Filip
829 3b89a232 Ondrej Zajicek
    if (re->n.oa->areaid != 0)
830
      continue;
831 1a61882d Ondrej Filip
832 3b89a232 Ondrej Zajicek
    if ((re->n.type != RTS_OSPF) && (re->n.type != RTS_OSPF_IA))
833
      continue;
834 1a61882d Ondrej Filip
835 3b89a232 Ondrej Zajicek
    /* 16.3. (4) */
836
    abrip = ipa_from_rid(en->lsa.rt);
837
    abr = fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH);
838
    if (!abr || !abr->n.type)
839
      continue;
840 1a61882d Ondrej Filip
841 3b89a232 Ondrej Zajicek
    metric = abr->n.metric1 + metric; /* IAC */
842 98ac6176 Ondrej Filip
843 3b89a232 Ondrej Zajicek
    /* 16.3. (5) */
844 57c574d8 Ondrej Zajicek
    if ((metric < re->n.metric1) || 
845
        ((metric == re->n.metric1) && unresolved_vlink(re->n.nhs)))
846 98ac6176 Ondrej Filip
    {
847 3b89a232 Ondrej Zajicek
      /* We want to replace the next-hop even if the metric is equal
848 57c574d8 Ondrej Zajicek
         to replace a virtual next-hop through vlink with a real one.
849
         Proper ECMP would merge nexthops here, but we do not do that.
850
         We restrict nexthops to fit one area to simplify check
851
         12.4.3 p4 in decide_sum_lsa() */
852
853 3b89a232 Ondrej Zajicek
      re->n.metric1 = metric;
854 57c574d8 Ondrej Zajicek
      re->n.voa = oa;
855
      re->n.nhs = abr->n.nhs;
856 98ac6176 Ondrej Filip
    }
857
  }
858 3b89a232 Ondrej Zajicek
}
859 1a61882d Ondrej Filip
860 6384c7d7 Ondrej Zajicek
/* Decide about originating or flushing summary LSAs for condended area networks */
861
static int
862
decide_anet_lsa(struct ospf_area *oa, struct area_net *anet, struct ospf_area *anet_oa)
863
{
864 41b612c3 Ondrej Zajicek
  /* 12.4.3.1. - for stub/NSSA areas, originating summary routes is configurable */
865
  if (!oa_is_ext(oa) && !oa->ac->summary)
866 6384c7d7 Ondrej Zajicek
    return 0;
867
868
  if (oa == anet_oa)
869
    return 0;
870
871
  /* Do not condense routing info when exporting from backbone to the transit area */
872
  if ((anet_oa == oa->po->backbone) && oa->trcap)
873
    return 0;
874
875
  return (anet->active && !anet->hidden);
876
}
877
878
/* Decide about originating or flushing summary LSAs (12.4.3) */
879
static int
880
decide_sum_lsa(struct ospf_area *oa, ort *nf, int dest)
881
{
882 41b612c3 Ondrej Zajicek
  /* 12.4.3.1. - for stub/NSSA areas, originating summary routes is configurable */
883
  if (!oa_is_ext(oa) && !oa->ac->summary)
884 6384c7d7 Ondrej Zajicek
    return 0;
885
886
  /* Invalid field - no route */
887
  if (!nf->n.type)
888
    return 0;
889
890
  /* 12.4.3 p2 */
891
  if (nf->n.type > RTS_OSPF_IA)
892
    return 0;
893
894
  /* 12.4.3 p3 */
895
  if ((nf->n.oa->areaid == oa->areaid))
896
    return 0;
897
898
  /* 12.4.3 p4 */
899 57c574d8 Ondrej Zajicek
  if (nf->n.voa && (nf->n.voa->areaid == oa->areaid))
900 6384c7d7 Ondrej Zajicek
    return 0;
901
902
  /* 12.4.3 p5 */
903
  if (nf->n.metric1 >= LSINFINITY)
904
    return 0;
905
906
  /* 12.4.3 p6 - AS boundary router */
907
  if (dest == ORT_ROUTER)
908
  {
909
    /* We call decide_sum_lsa() on preferred ASBR entries, no need for 16.4. (3) */
910
    /* 12.4.3 p1 */
911 41b612c3 Ondrej Zajicek
    return oa_is_ext(oa) && (nf->n.options & ORTA_ASBR);
912 6384c7d7 Ondrej Zajicek
  }
913
914
  /* 12.4.3 p7 - inter-area route */
915
  if (nf->n.type == RTS_OSPF_IA)
916
  {
917
    /* Inter-area routes are not repropagated into the backbone */
918
    return (oa != oa->po->backbone);
919
  }
920
921
  /* 12.4.3 p8 - intra-area route */
922
923
  /* Do not condense routing info when exporting from backbone to the transit area */
924
  if ((nf->n.oa == oa->po->backbone) && oa->trcap)
925
    return 1;
926
927
  struct area_net *anet = (struct area_net *)
928
    fib_route(&nf->n.oa->net_fib, nf->fn.prefix, nf->fn.pxlen);
929
930
  /* Condensed area network found */ 
931
  if (anet)
932
    return 0;
933
934
  return 1;
935
}
936
937
/* RFC 2328 16.7. p1 - originate or flush summary LSAs */
938
static inline void
939
check_sum_net_lsa(struct proto_ospf *po, ort *nf)
940
{
941
  struct area_net *anet = NULL;
942 9b061f7e Ondrej Zajicek
  struct ospf_area *anet_oa = NULL;
943 6384c7d7 Ondrej Zajicek
944
  /* RT entry marked as area network */
945
  if (nf->fn.x0)
946
  {
947
    /* It is a default route for stub areas, handled entirely in ospf_rt_abr() */
948
    if (nf->fn.pxlen == 0)
949
      return;
950
951
    /* Find that area network */
952
    WALK_LIST(anet_oa, po->area_list)
953
    {
954
      anet = (struct area_net *) fib_find(&anet_oa->net_fib, &nf->fn.prefix, nf->fn.pxlen);
955
      if (anet)
956
        break;
957
    }
958
  }
959
960
  struct ospf_area *oa;
961
  WALK_LIST(oa, po->area_list)
962
  {
963
    if (anet && decide_anet_lsa(oa, anet, anet_oa))
964
      originate_sum_net_lsa(oa, &nf->fn, anet->metric);
965
    else if (decide_sum_lsa(oa, nf, ORT_NET))
966
      originate_sum_net_lsa(oa, &nf->fn, nf->n.metric1);
967
    else
968
      flush_sum_lsa(oa, &nf->fn, ORT_NET);
969
  }
970
}
971
972
static inline void
973
check_sum_rt_lsa(struct proto_ospf *po, ort *nf)
974
{
975
  struct ospf_area *oa;
976
  WALK_LIST(oa, po->area_list)
977
  {
978
    if (decide_sum_lsa(oa, nf, ORT_ROUTER))
979
      originate_sum_rt_lsa(oa, &nf->fn, nf->n.metric1, nf->n.options);
980
    else
981
      flush_sum_lsa(oa, &nf->fn, ORT_ROUTER);
982
  }
983
}
984
985 ed317862 Ondrej Zajicek
static inline int
986
decide_nssa_lsa(ort *nf, u32 *rt_metric, ip_addr *rt_fwaddr, u32 *rt_tag)
987
{
988
  struct ospf_area *oa = nf->n.oa;
989
  struct top_hash_entry *en = nf->n.en;
990
  int propagate;
991
992
  if (!rt_is_nssa(nf) || !oa->translate)
993
    return 0;
994
995
  /* Condensed area network found */ 
996
  if (fib_route(&oa->enet_fib, nf->fn.prefix, nf->fn.pxlen))
997
    return 0;
998
999
  if (!en || (en->lsa.type != LSA_T_NSSA))
1000
    return 0;
1001
1002
  /* We do not store needed data in struct orta, we have to parse the LSA */
1003
  struct ospf_lsa_ext *le = en->lsa_body;
1004
1005
#ifdef OSPFv2
1006
  *rt_fwaddr = le->fwaddr;
1007
  *rt_tag = le->tag;
1008
  propagate = en->lsa.options & OPT_P;
1009
#else /* OSPFv3 */
1010
  u32 *buf = le->rest;
1011
  u8 pxlen = (*buf >> 24);
1012
  u8 pxopts = (*buf >> 16);
1013
  buf += IPV6_PREFIX_WORDS(pxlen);  /* Skip the IP prefix */
1014
1015
  if (pxopts & OPT_PX_NU)
1016
    return 0;
1017
1018
  if (le->metric & LSA_EXT_FBIT)
1019
    buf = lsa_get_ipv6_addr(buf, rt_fwaddr);
1020
  else
1021
    *rt_fwaddr = IPA_NONE;
1022
1023
  if (le->metric & LSA_EXT_TBIT)
1024
    *rt_tag = *buf++;
1025
  else
1026
    *rt_tag = 0;
1027
1028
  propagate = pxopts & OPT_PX_P;
1029
#endif
1030
1031
  if (!propagate || ipa_zero(*rt_fwaddr))
1032
    return 0;
1033
1034
  *rt_metric = le->metric & (METRIC_MASK | LSA_EXT_EBIT);
1035
  return 1;
1036
}
1037
1038
/* RFC 3103 3.2 - translating Type-7 LSAs into Type-5 LSAs */
1039
static inline void
1040
check_nssa_lsa(struct proto_ospf *po, ort *nf)
1041
{
1042
  struct fib_node *fn = &nf->fn;
1043
  struct area_net *anet = NULL;
1044
  struct ospf_area *oa = NULL;
1045
  u32 rt_metric, rt_tag;
1046
  ip_addr rt_fwaddr;
1047
1048
  /* Do not translate LSA if there is already the external LSA from route export */
1049
  if (fn->x1 == EXT_EXPORT)
1050
    return;
1051
1052
  /* RT entry marked as area network */
1053
  if (fn->x0)
1054
  {
1055
    /* Find that area network */
1056
    WALK_LIST(oa, po->area_list)
1057
    {
1058
      anet = (struct area_net *) fib_find(&oa->enet_fib, &fn->prefix, fn->pxlen);
1059
      if (anet)
1060
        break;
1061
    }
1062
  }
1063
1064
  /* RFC 3103 3.2 (3) - originate the aggregated address range */
1065
  if (anet && anet->active && !anet->hidden && oa->translate)
1066 2918e610 Ondrej Zajicek
    originate_ext_lsa(po->backbone, fn, EXT_NSSA, anet->metric, IPA_NONE, anet->tag, 0);
1067 ed317862 Ondrej Zajicek
1068
  /* RFC 3103 3.2 (2) - originate the same network */
1069
  else if (decide_nssa_lsa(nf, &rt_metric, &rt_fwaddr, &rt_tag))
1070 2918e610 Ondrej Zajicek
    originate_ext_lsa(po->backbone, fn, EXT_NSSA, rt_metric, rt_fwaddr, rt_tag, 0);
1071 ed317862 Ondrej Zajicek
1072
  else if (fn->x1 == EXT_NSSA)
1073 bbcfd5a0 Ondrej Zajicek
    flush_ext_lsa(po->backbone, fn, 0);
1074 ed317862 Ondrej Zajicek
}
1075 6384c7d7 Ondrej Zajicek
1076
/* RFC 2328 16.7. p2 - find new/lost vlink endpoints */
1077 3b89a232 Ondrej Zajicek
static void
1078 6384c7d7 Ondrej Zajicek
ospf_check_vlinks(struct proto_ospf *po)
1079 3b89a232 Ondrej Zajicek
{
1080 6384c7d7 Ondrej Zajicek
  struct proto *p = &po->proto;
1081
1082
  struct ospf_iface *iface;
1083
  WALK_LIST(iface, po->iface_list)
1084
  {
1085
    if (iface->type == OSPF_IT_VLINK)
1086
    {
1087
      struct top_hash_entry *tmp;
1088
      tmp = ospf_hash_find_rt(po->gr, iface->voa->areaid, iface->vid);
1089
1090 57c574d8 Ondrej Zajicek
      if (tmp && (tmp->color == INSPF) && ipa_nonzero(tmp->lb) && tmp->nhs)
1091 6384c7d7 Ondrej Zajicek
      {
1092 57c574d8 Ondrej Zajicek
        struct ospf_iface *nhi = ospf_iface_find(po, tmp->nhs->iface);
1093
1094 6384c7d7 Ondrej Zajicek
        if ((iface->state != OSPF_IS_PTP)
1095 57c574d8 Ondrej Zajicek
            || (iface->vifa != nhi)
1096 6384c7d7 Ondrej Zajicek
            || !ipa_equal(iface->vip, tmp->lb))
1097
        {
1098
          OSPF_TRACE(D_EVENTS, "Vlink peer %R found", tmp->lsa.id);
1099
          ospf_iface_sm(iface, ISM_DOWN);
1100 57c574d8 Ondrej Zajicek
          iface->vifa = nhi;
1101
          iface->iface = nhi->iface;
1102
          iface->addr = nhi->addr;
1103
          iface->sk = nhi->sk;
1104 6384c7d7 Ondrej Zajicek
          iface->cost = tmp->dist;
1105
          iface->vip = tmp->lb;
1106
          ospf_iface_sm(iface, ISM_UP);
1107
        }
1108
        else if ((iface->state == OSPF_IS_PTP) && (iface->cost != tmp->dist))
1109
        {
1110
          iface->cost = tmp->dist;
1111
          schedule_rt_lsa(po->backbone);
1112
        }
1113
      }
1114
      else
1115
      {
1116
        if (iface->state > OSPF_IS_DOWN)
1117
        {
1118
          OSPF_TRACE(D_EVENTS, "Vlink peer %R lost", iface->vid);
1119
          ospf_iface_sm(iface, ISM_DOWN);
1120
        }
1121
      }
1122
    }
1123
  }
1124
}
1125
1126 4160a9dd Ondrej Zajicek
1127 6384c7d7 Ondrej Zajicek
/* Miscellaneous route processing that needs to be done by ABRs */
1128
static void
1129 ed317862 Ondrej Zajicek
ospf_rt_abr1(struct proto_ospf *po)
1130 6384c7d7 Ondrej Zajicek
{
1131
  struct area_net *anet;
1132 ed317862 Ondrej Zajicek
  ort *nf, *default_nf;
1133 6384c7d7 Ondrej Zajicek
1134 3b89a232 Ondrej Zajicek
  FIB_WALK(&po->rtf, nftmp)
1135 98ac6176 Ondrej Filip
  {
1136 6384c7d7 Ondrej Zajicek
    nf = (ort *) nftmp;
1137
1138
1139
    /* RFC 2328 G.3 - incomplete resolution of virtual next hops */
1140 57c574d8 Ondrej Zajicek
    if (nf->n.type && unresolved_vlink(nf->n.nhs))
1141
      reset_ri(nf);
1142 6384c7d7 Ondrej Zajicek
1143
1144
    /* Compute condensed area networks */
1145
    if (nf->n.type == RTS_OSPF)
1146
    {
1147
      anet = (struct area_net *) fib_route(&nf->n.oa->net_fib, nf->fn.prefix, nf->fn.pxlen);
1148
      if (anet)
1149
      {
1150
        if (!anet->active)
1151
        {
1152
          anet->active = 1;
1153
1154
          /* Get a RT entry and mark it to know that it is an area network */
1155
          ort *nfi = (ort *) fib_get(&po->rtf, &anet->fn.prefix, anet->fn.pxlen);
1156
          nfi->fn.x0 = 1; /* mark and keep persistent, to have stable UID */
1157
1158
          /* 16.2. (3) */
1159
          if (nfi->n.type == RTS_OSPF_IA)
1160 57c574d8 Ondrej Zajicek
            reset_ri(nfi);
1161 6384c7d7 Ondrej Zajicek
        }
1162
1163
        if (anet->metric < nf->n.metric1)
1164
          anet->metric = nf->n.metric1;
1165
      }
1166
    }
1167
  }
1168
  FIB_WALK_END;
1169
1170
  ip_addr addr = IPA_NONE;
1171
  default_nf = (ort *) fib_get(&po->rtf, &addr, 0);
1172
  default_nf->fn.x0 = 1; /* keep persistent */
1173
1174
  struct ospf_area *oa;
1175
  WALK_LIST(oa, po->area_list)
1176
  {
1177
1178 41b612c3 Ondrej Zajicek
    /* 12.4.3.1. - originate or flush default route for stub/NSSA areas */
1179
    if (oa_is_stub(oa) || (oa_is_nssa(oa) && !oa->ac->summary))
1180 2918e610 Ondrej Zajicek
      originate_sum_net_lsa(oa, &default_nf->fn, oa->ac->default_cost);
1181 6384c7d7 Ondrej Zajicek
    else
1182
      flush_sum_lsa(oa, &default_nf->fn, ORT_NET);
1183
1184 2918e610 Ondrej Zajicek
    /*
1185
     * Originate type-7 default route for NSSA areas
1186
     *
1187
     * Because type-7 default LSAs are originated by ABRs, they do not
1188
     * collide with other type-7 LSAs (as ABRs generate type-5 LSAs
1189
     * for both external route export or external-NSSA translation),
1190
     * so we use 0 for the src arg.
1191
     */
1192
1193
    if (oa_is_nssa(oa) && oa->ac->default_nssa)
1194
      originate_ext_lsa(oa, &default_nf->fn, 0, oa->ac->default_cost, IPA_NONE, 0, 0);
1195
    else
1196 bbcfd5a0 Ondrej Zajicek
      flush_ext_lsa(oa, &default_nf->fn, 1);
1197 2918e610 Ondrej Zajicek
1198 6384c7d7 Ondrej Zajicek
1199
    /* RFC 2328 16.4. (3) - precompute preferred ASBR entries */
1200 41b612c3 Ondrej Zajicek
    if (oa_is_ext(oa))
1201 6384c7d7 Ondrej Zajicek
    {
1202 41b612c3 Ondrej Zajicek
      FIB_WALK(&oa->rtr, nftmp)
1203
      {
1204
        nf = (ort *) nftmp;
1205
        if (nf->n.options & ORTA_ASBR)
1206
          ri_install_asbr(po, &nf->fn.prefix, &nf->n);
1207
      }
1208
      FIB_WALK_END;
1209 6384c7d7 Ondrej Zajicek
    }
1210
  }
1211
1212
1213 ed317862 Ondrej Zajicek
  /* Originate or flush ASBR summary LSAs */
1214
  FIB_WALK(&po->backbone->rtr, nftmp)
1215
  {
1216
    check_sum_rt_lsa(po, (ort *) nftmp);
1217
  }
1218
  FIB_WALK_END;
1219
1220
1221
  /* RFC 2328 16.7. p2 - find new/lost vlink endpoints */
1222
  ospf_check_vlinks(po);
1223
}
1224
1225
1226
static void
1227
translator_timer_hook(timer *timer)
1228
{
1229
  struct ospf_area *oa = timer->data;
1230
  
1231
  if (oa->translate != TRANS_WAIT)
1232
    return;
1233
1234
  oa->translate = TRANS_OFF;
1235
  schedule_rtcalc(oa->po);
1236
}
1237
1238
static void
1239
ospf_rt_abr2(struct proto_ospf *po)
1240
{
1241
  struct ospf_area *oa;
1242
  struct top_hash_entry *en;
1243
  ort *nf, *nf2;
1244
1245
1246 4160a9dd Ondrej Zajicek
  /* RFC 3103 3.1 - type-7 translator election */
1247 ed317862 Ondrej Zajicek
  struct ospf_area *bb = po->backbone;
1248 4160a9dd Ondrej Zajicek
  WALK_LIST(oa, po->area_list)
1249
    if (oa_is_nssa(oa))
1250
    {
1251
      int translate = 1;
1252
1253
      if (oa->ac->translator)
1254
        goto decided;
1255
1256
      FIB_WALK(&oa->rtr, nftmp)
1257
      {
1258
        nf = (ort *) nftmp;
1259
        if (!nf->n.type || !(nf->n.options & ORTA_ABR))
1260
          continue;
1261
1262
        nf2 = fib_find(&bb->rtr, &nf->fn.prefix, MAX_PREFIX_LENGTH);
1263
        if (!nf2 || !nf2->n.type || !(nf2->n.options & ORTA_ABR))
1264
          continue;
1265
1266
        en = ospf_hash_find_rt(po->gr, oa->areaid, nf->n.rid);
1267
        if (!en || (en->color != INSPF))
1268
          continue;
1269
1270
        struct ospf_lsa_rt *rt = en->lsa_body;
1271
        /* There is better candidate - Nt-bit or higher Router ID */
1272
        if ((rt->options & OPT_RT_NT) || (po->router_id < nf->n.rid))
1273
        {
1274
          translate = 0;
1275
          goto decided;
1276
        }
1277
      }
1278
      FIB_WALK_END;
1279
1280
    decided:
1281
      if (translate && (oa->translate != TRANS_ON))
1282
      {
1283
        if (oa->translate == TRANS_WAIT)
1284
          tm_stop(oa->translator_timer);
1285
1286
        oa->translate = TRANS_ON;
1287
      }
1288
1289
      if (!translate && (oa->translate == TRANS_ON))
1290
      {
1291
        if (oa->translator_timer == NULL)
1292
          oa->translator_timer = tm_new_set(po->proto.pool, translator_timer_hook, oa, 0, 0);
1293
1294
        /* Schedule the end of translation */
1295
        tm_start(oa->translator_timer, oa->ac->transint);
1296
        oa->translate = TRANS_WAIT;
1297
      }
1298
    }
1299
1300
1301 ed317862 Ondrej Zajicek
  /* Compute condensed external networks */
1302
  FIB_WALK(&po->rtf, nftmp)
1303 6384c7d7 Ondrej Zajicek
  {
1304 ed317862 Ondrej Zajicek
    nf = (ort *) nftmp;
1305 2918e610 Ondrej Zajicek
    if (rt_is_nssa(nf) && (nf->n.options & ORTA_PROP))
1306 ed317862 Ondrej Zajicek
    {
1307
      struct area_net *anet = (struct area_net *)
1308
        fib_route(&nf->n.oa->enet_fib, nf->fn.prefix, nf->fn.pxlen);
1309
1310
      if (anet)
1311
      {
1312
        if (!anet->active)
1313
        {
1314
          anet->active = 1;
1315
1316
          /* Get a RT entry and mark it to know that it is an area network */
1317
          nf2 = (ort *) fib_get(&po->rtf, &anet->fn.prefix, anet->fn.pxlen);
1318
          nf2->fn.x0 = 1;
1319
        }
1320
1321
        u32 metric = (nf->n.type == RTS_OSPF_EXT1) ?
1322
          nf->n.metric1 : ((nf->n.metric2 + 1) | LSA_EXT_EBIT);
1323
1324
        if (anet->metric < metric)
1325
          anet->metric = metric;
1326
      }
1327
    }
1328 1a61882d Ondrej Filip
  }
1329 3b89a232 Ondrej Zajicek
  FIB_WALK_END;
1330 6384c7d7 Ondrej Zajicek
1331
1332 ed317862 Ondrej Zajicek
  FIB_WALK(&po->rtf, nftmp)
1333
  {
1334
    nf = (ort *) nftmp;
1335
1336
    check_sum_net_lsa(po, nf);
1337
    check_nssa_lsa(po, nf);
1338
  }
1339
  FIB_WALK_END;
1340 b8f17cf1 Ondrej Filip
}
1341
1342 ed317862 Ondrej Zajicek
1343 54818e9b Ondrej Zajicek
/* Like fib_route(), but ignores dummy rt entries */
1344
static void *
1345
ospf_fib_route(struct fib *f, ip_addr a, int len)
1346
{
1347
  ip_addr a0;
1348
  ort *nf;
1349
1350
  while (len >= 0)
1351
  {
1352
    a0 = ipa_and(a, ipa_mkmask(len));
1353
    nf = fib_find(f, &a0, len);
1354
    if (nf && nf->n.type)
1355
      return nf;
1356
    len--;
1357
  }
1358
  return NULL;
1359
}
1360 6384c7d7 Ondrej Zajicek
1361
/* RFC 2328 16.4. calculating external routes */
1362 b8f17cf1 Ondrej Filip
static void
1363 86c84d76 Ondrej Filip
ospf_ext_spf(struct proto_ospf *po)
1364 fafe44b6 Ondrej Filip
{
1365 3b89a232 Ondrej Zajicek
  ort *nf1, *nf2;
1366 1a61882d Ondrej Filip
  orta nfa;
1367
  struct top_hash_entry *en;
1368 2e10a170 Ondrej Filip
  struct proto *p = &po->proto;
1369 aa1e082c Ondrej Filip
  struct ospf_lsa_ext *le;
1370 41b612c3 Ondrej Zajicek
  int pxlen, ebit, rt_fwaddr_valid, rt_propagate;
1371 57c574d8 Ondrej Zajicek
  ip_addr ip, rtid, rt_fwaddr;
1372 c3226991 Ondrej Zajicek
  u32 br_metric, rt_metric, rt_tag;
1373 98ac6176 Ondrej Filip
  struct ospf_area *atmp;
1374 57c574d8 Ondrej Zajicek
  struct mpnh* nhs = NULL;
1375 aa1e082c Ondrej Filip
1376 1a61882d Ondrej Filip
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation for ext routes");
1377 aa1e082c Ondrej Filip
1378 86c84d76 Ondrej Filip
  WALK_SLIST(en, po->lsal)
1379 aa1e082c Ondrej Filip
  {
1380 c3226991 Ondrej Zajicek
    /* 16.4. (1) */
1381 41b612c3 Ondrej Zajicek
    if ((en->lsa.type != LSA_T_EXT) && (en->lsa.type != LSA_T_NSSA))
1382 2e10a170 Ondrej Filip
      continue;
1383 3b89a232 Ondrej Zajicek
1384 2e10a170 Ondrej Filip
    if (en->lsa.age == LSA_MAXAGE)
1385
      continue;
1386 c3226991 Ondrej Zajicek
1387
    /* 16.4. (2) */
1388 8a70a13e Ondrej Zajicek
    if (en->lsa.rt == po->router_id)
1389 2e10a170 Ondrej Filip
      continue;
1390 aa1e082c Ondrej Filip
1391 f9c799a0 Ondrej Zajicek
    DBG("%s: Working on LSA. ID: %R, RT: %R, Type: %u\n",
1392
        p->name, en->lsa.id, en->lsa.rt, en->lsa.type);
1393 273fd2c1 Ondrej Filip
1394 c3226991 Ondrej Zajicek
    le = en->lsa_body;
1395
1396
    rt_metric = le->metric & METRIC_MASK;
1397
    ebit = le->metric & LSA_EXT_EBIT;
1398
1399
    if (rt_metric == LSINFINITY)
1400 2e10a170 Ondrej Filip
      continue;
1401 c3226991 Ondrej Zajicek
1402
#ifdef OSPFv2
1403 2e10a170 Ondrej Filip
    ip = ipa_and(ipa_from_u32(en->lsa.id), le->netmask);
1404 c3226991 Ondrej Zajicek
    pxlen = ipa_mklen(le->netmask);
1405
    rt_fwaddr = le->fwaddr;
1406
    rt_fwaddr_valid = !ipa_equal(rt_fwaddr, IPA_NONE);
1407
    rt_tag = le->tag;
1408 41b612c3 Ondrej Zajicek
    rt_propagate = en->lsa.options & OPT_P;
1409 c3226991 Ondrej Zajicek
#else /* OSPFv3 */
1410
    u8 pxopts;
1411 b49e6f5a Ondrej Zajicek
    u16 rest;
1412 c3226991 Ondrej Zajicek
    u32 *buf = le->rest;
1413 b66abe8e Ondrej Zajicek
    buf = lsa_get_ipv6_prefix(buf, &ip, &pxlen, &pxopts, &rest);
1414 c3226991 Ondrej Zajicek
1415
    if (pxopts & OPT_PX_NU)
1416
      continue;
1417
1418
    rt_fwaddr_valid = le->metric & LSA_EXT_FBIT;
1419
    if (rt_fwaddr_valid)
1420 b66abe8e Ondrej Zajicek
      buf = lsa_get_ipv6_addr(buf, &rt_fwaddr);
1421 c3226991 Ondrej Zajicek
    else 
1422
      rt_fwaddr = IPA_NONE;
1423
1424
    if (le->metric & LSA_EXT_TBIT)
1425
      rt_tag = *buf++;
1426
    else
1427
      rt_tag = 0;
1428 41b612c3 Ondrej Zajicek
1429
    rt_propagate = pxopts & OPT_PX_P;
1430 c3226991 Ondrej Zajicek
#endif
1431
1432 ab164971 Ondrej Zajicek
    if (pxlen < 0 || pxlen > MAX_PREFIX_LENGTH)
1433 508c36ab Ondrej Filip
    {
1434 ab164971 Ondrej Zajicek
      log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
1435 34a877cc Ondrej Zajicek
          p->name, en->lsa.type, en->lsa.id, en->lsa.rt);
1436 4ee21789 Ondrej Filip
      continue;
1437 508c36ab Ondrej Filip
    }
1438 aa1e082c Ondrej Filip
1439 41b612c3 Ondrej Zajicek
1440 c3226991 Ondrej Zajicek
    /* 16.4. (3) */
1441 41b612c3 Ondrej Zajicek
    /* If there are more areas, we already precomputed preferred ASBR
1442 ed317862 Ondrej Zajicek
       entries in ospf_rt_abr1() and stored them in the backbone
1443 41b612c3 Ondrej Zajicek
       table. For NSSA, we examine the area to which the LSA is assigned */
1444
    if (en->lsa.type == LSA_T_EXT)
1445
      atmp = ospf_main_area(po);
1446
    else /* NSSA */
1447
      atmp = ospf_find_area(po, en->domain);
1448
1449
    if (!atmp)
1450
      continue;                        /* Should not happen */
1451
1452 c3226991 Ondrej Zajicek
    rtid = ipa_from_rid(en->lsa.rt);
1453 6384c7d7 Ondrej Zajicek
    nf1 = fib_find(&atmp->rtr, &rtid, MAX_PREFIX_LENGTH);
1454 3b89a232 Ondrej Zajicek
1455 6384c7d7 Ondrej Zajicek
    if (!nf1 || !nf1->n.type)
1456 1a61882d Ondrej Filip
      continue;                        /* No AS boundary router found */
1457 aa1e082c Ondrej Filip
1458 c3226991 Ondrej Zajicek
    if (!(nf1->n.options & ORTA_ASBR))
1459 1a61882d Ondrej Filip
      continue;                        /* It is not ASBR */
1460 508c36ab Ondrej Filip
1461 41b612c3 Ondrej Zajicek
    /* 16.4. (3) NSSA - special rule for default routes */
1462
    /* ABR should use default only if P-bit is set and summaries are active */
1463
    if ((en->lsa.type == LSA_T_NSSA) && ipa_zero(ip) && (pxlen == 0) &&
1464
        (po->areano > 1) && !(rt_propagate && atmp->ac->summary))
1465
      continue;
1466
1467 c3226991 Ondrej Zajicek
    if (!rt_fwaddr_valid)
1468 aa1e082c Ondrej Filip
    {
1469 3b89a232 Ondrej Zajicek
      nf2 = nf1;
1470 57c574d8 Ondrej Zajicek
      nhs = nf1->n.nhs;
1471 c3226991 Ondrej Zajicek
      br_metric = nf1->n.metric1;
1472 508c36ab Ondrej Filip
    }
1473 1a61882d Ondrej Filip
    else
1474 c3226991 Ondrej Zajicek
    {
1475 54818e9b Ondrej Zajicek
      nf2 = ospf_fib_route(&po->rtf, rt_fwaddr, MAX_PREFIX_LENGTH);
1476
      if (!nf2)
1477 2e10a170 Ondrej Filip
        continue;
1478 98ac6176 Ondrej Filip
1479 41b612c3 Ondrej Zajicek
      if (en->lsa.type == LSA_T_EXT)
1480
      {
1481
        /* For ext routes, we accept intra-area or inter-area routes */
1482
        if ((nf2->n.type != RTS_OSPF) && (nf2->n.type != RTS_OSPF_IA))
1483
          continue;
1484
      }
1485
      else /* NSSA */
1486
      {
1487
        /* For NSSA routes, we accept just intra-area in the same area */
1488
        if ((nf2->n.type != RTS_OSPF) || (nf2->n.oa != atmp))
1489
          continue;
1490
      }
1491 98ac6176 Ondrej Filip
1492 e0a62ad0 Ondrej Zajicek
      /* Next-hop is a part of a configured stubnet */
1493 57c574d8 Ondrej Zajicek
      if (!nf2->n.nhs)
1494 e0a62ad0 Ondrej Zajicek
        continue;
1495
1496 57c574d8 Ondrej Zajicek
      nhs = nf2->n.nhs;
1497
      /* If gw is zero, it is a device route */
1498
      if (ipa_zero(nhs->gw))
1499
        nhs = new_nexthop(po, rt_fwaddr, nhs->iface, nhs->weight);
1500 c3226991 Ondrej Zajicek
      br_metric = nf2->n.metric1;
1501 aa1e082c Ondrej Filip
    }
1502 508c36ab Ondrej Filip
1503 c3226991 Ondrej Zajicek
    if (ebit)
1504
    {
1505
      nfa.type = RTS_OSPF_EXT2;
1506
      nfa.metric1 = br_metric;
1507
      nfa.metric2 = rt_metric;
1508
    }
1509
    else
1510
    {
1511
      nfa.type = RTS_OSPF_EXT1;
1512
      nfa.metric1 = br_metric + rt_metric;
1513
      nfa.metric2 = LSINFINITY;
1514
    }
1515
1516 0ea8fb4a Ondrej Zajicek
    /* Mark the LSA as reachable */
1517
    en->color = INSPF;
1518
1519 3b89a232 Ondrej Zajicek
    /* Whether the route is preferred in route selection according to 16.4.1 */
1520
    nfa.options = epath_preferred(&nf2->n) ? ORTA_PREF : 0;
1521 ed317862 Ondrej Zajicek
    if (en->lsa.type == LSA_T_NSSA)
1522 2918e610 Ondrej Zajicek
    {
1523 ed317862 Ondrej Zajicek
      nfa.options |= ORTA_NSSA;
1524 2918e610 Ondrej Zajicek
      if (rt_propagate)
1525
        nfa.options |= ORTA_PROP;
1526
    }
1527 3b89a232 Ondrej Zajicek
1528 c3226991 Ondrej Zajicek
    nfa.tag = rt_tag;
1529 c27b2449 Ondrej Zajicek
    nfa.rid = en->lsa.rt;
1530 ed317862 Ondrej Zajicek
    nfa.oa = atmp; /* undefined in RFC 2328 */
1531 57c574d8 Ondrej Zajicek
    nfa.voa = NULL;
1532
    nfa.nhs = nhs;
1533 ed317862 Ondrej Zajicek
    nfa.en = en; /* store LSA for later (NSSA processing) */
1534 3b89a232 Ondrej Zajicek
1535
    ri_install_ext(po, ip, pxlen, &nfa);
1536
  }
1537
}
1538
1539 57c574d8 Ondrej Zajicek
/* Cleanup of routing tables and data */
1540 6384c7d7 Ondrej Zajicek
void
1541
ospf_rt_reset(struct proto_ospf *po)
1542 3b89a232 Ondrej Zajicek
{
1543 6384c7d7 Ondrej Zajicek
  struct ospf_area *oa;
1544
  struct top_hash_entry *en;
1545
  struct area_net *anet;
1546
  ort *ri;
1547 3b89a232 Ondrej Zajicek
1548 6384c7d7 Ondrej Zajicek
  /* Reset old routing table */
1549
  FIB_WALK(&po->rtf, nftmp)
1550 3b89a232 Ondrej Zajicek
  {
1551 6384c7d7 Ondrej Zajicek
    ri = (ort *) nftmp;
1552
    ri->fn.x0 = 0;
1553 57c574d8 Ondrej Zajicek
    reset_ri(ri);
1554 6384c7d7 Ondrej Zajicek
  }
1555
  FIB_WALK_END;
1556
1557
  /* Reset SPF data in LSA db */
1558
  WALK_SLIST(en, po->lsal)
1559
  {
1560
    en->color = OUTSPF;
1561
    en->dist = LSINFINITY;
1562 57c574d8 Ondrej Zajicek
    en->nhs = NULL;
1563 6384c7d7 Ondrej Zajicek
    en->lb = IPA_NONE;
1564
  }
1565
1566
  WALK_LIST(oa, po->area_list)
1567
  {
1568
    /* Reset ASBR routing tables */
1569
    FIB_WALK(&oa->rtr, nftmp)
1570 3b89a232 Ondrej Zajicek
    {
1571 6384c7d7 Ondrej Zajicek
      ri = (ort *) nftmp;
1572 57c574d8 Ondrej Zajicek
      reset_ri(ri);
1573 6384c7d7 Ondrej Zajicek
    }
1574
    FIB_WALK_END;
1575 3b89a232 Ondrej Zajicek
1576 6384c7d7 Ondrej Zajicek
    /* Reset condensed area networks */
1577
    if (po->areano > 1)
1578
    {
1579
      FIB_WALK(&oa->net_fib, nftmp)
1580 3b89a232 Ondrej Zajicek
      {
1581 6384c7d7 Ondrej Zajicek
        anet = (struct area_net *) nftmp;
1582
        anet->active = 0;
1583
        anet->metric = 0;
1584 3b89a232 Ondrej Zajicek
      }
1585 6384c7d7 Ondrej Zajicek
      FIB_WALK_END;
1586 ed317862 Ondrej Zajicek
1587
      FIB_WALK(&oa->enet_fib, nftmp)
1588
      {
1589
        anet = (struct area_net *) nftmp;
1590
        anet->active = 0;
1591
        anet->metric = 0;
1592
      }
1593
      FIB_WALK_END;
1594 3b89a232 Ondrej Zajicek
    }
1595
  }
1596
}
1597 6384c7d7 Ondrej Zajicek
1598 3b89a232 Ondrej Zajicek
/**
1599
 * ospf_rt_spf - calculate internal routes
1600
 * @po: OSPF protocol
1601
 *
1602
 * Calculation of internal paths in an area is described in 16.1 of RFC 2328.
1603
 * It's based on Dijkstra's shortest path tree algorithms.
1604
 * This function is invoked from ospf_disp().
1605
 */
1606
void
1607
ospf_rt_spf(struct proto_ospf *po)
1608
{
1609
  struct proto *p = &po->proto;
1610
  struct ospf_area *oa;
1611
1612 6384c7d7 Ondrej Zajicek
  if (po->areano == 0)
1613
    return;
1614 3b89a232 Ondrej Zajicek
1615
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation");
1616
1617 6384c7d7 Ondrej Zajicek
  /* 16. (1) */
1618
  ospf_rt_reset(po);
1619 3b89a232 Ondrej Zajicek
1620 6384c7d7 Ondrej Zajicek
  /* 16. (2) */
1621 3b89a232 Ondrej Zajicek
  WALK_LIST(oa, po->area_list)
1622
    ospf_rt_spfa(oa);
1623
1624
  /* 16. (3) */
1625 41b612c3 Ondrej Zajicek
  ospf_rt_sum(ospf_main_area(po));
1626 3b89a232 Ondrej Zajicek
1627
  /* 16. (4) */
1628
  WALK_LIST(oa, po->area_list)
1629
    if (oa->trcap && (oa->areaid != 0))
1630
      ospf_rt_sum_tr(oa);
1631
1632 6384c7d7 Ondrej Zajicek
  if (po->areano > 1)
1633 ed317862 Ondrej Zajicek
    ospf_rt_abr1(po);
1634 3b89a232 Ondrej Zajicek
1635
  /* 16. (5) */
1636
  ospf_ext_spf(po);
1637
1638 ed317862 Ondrej Zajicek
  if (po->areano > 1)
1639
    ospf_rt_abr2(po);
1640
1641 3b89a232 Ondrej Zajicek
  rt_sync(po);
1642 57c574d8 Ondrej Zajicek
  lp_flush(po->nhpool);
1643
  
1644 3b89a232 Ondrej Zajicek
  po->calcrt = 0;
1645 dfa9a53a Ondrej Filip
}
1646
1647 57c574d8 Ondrej Zajicek
1648
static inline int
1649
inherit_nexthops(struct mpnh *pn)
1650
{
1651
  /* Proper nexthops (with defined GW) or dummy vlink nexthops (without iface) */
1652
  return pn && (ipa_nonzero(pn->gw) || !pn->iface);
1653
}
1654
1655
static struct mpnh *
1656
calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
1657 e7b4948c Ondrej Zajicek
              struct top_hash_entry *par, int pos)
1658 57c574d8 Ondrej Zajicek
{
1659
  // struct proto *p = &oa->po->proto;
1660
  struct proto_ospf *po = oa->po;
1661
  struct mpnh *pn = par->nhs;
1662
  struct ospf_iface *ifa;
1663
  u32 rid = en->lsa.rt;
1664
1665
  /* 16.1.1. The next hop calculation */
1666
  DBG("     Next hop calculating for id: %R rt: %R type: %u\n",
1667
      en->lsa.id, en->lsa.rt, en->lsa.type);
1668
1669
  /* Usually, we inherit parent nexthops */
1670
  if (inherit_nexthops(pn))
1671
    return pn;
1672
1673
  /* 
1674
   * There are three cases:
1675
   * 1) en is a local network (and par is root)
1676
   * 2) en is a ptp or ptmp neighbor (and par is root)
1677
   * 3) en is a bcast or nbma neighbor (and par is local network)
1678
   */
1679
1680
  /* The first case - local network */
1681
  if ((en->lsa.type == LSA_T_NET) && (par == oa->rt))
1682
  {
1683 e7b4948c Ondrej Zajicek
    ifa = rt_pos_to_ifa(oa, pos);
1684
    if (!ifa)
1685
      return NULL;
1686 57c574d8 Ondrej Zajicek
1687 e7b4948c Ondrej Zajicek
    return new_nexthop(po, IPA_NONE, ifa->iface, ifa->ecmp_weight);
1688 57c574d8 Ondrej Zajicek
  }
1689
1690
  /* The second case - ptp or ptmp neighbor */
1691
  if ((en->lsa.type == LSA_T_RT) && (par == oa->rt))
1692
  {
1693 e7b4948c Ondrej Zajicek
    ifa = rt_pos_to_ifa(oa, pos);
1694
    if (!ifa)
1695
      return NULL;
1696
1697
    if (ifa->type == OSPF_IT_VLINK)
1698 57c574d8 Ondrej Zajicek
      return new_nexthop(po, IPA_NONE, NULL, 0);
1699
1700 e7b4948c Ondrej Zajicek
    struct ospf_neighbor *m = find_neigh(ifa, rid);
1701
    if (!m || (m->state != NEIGHBOR_FULL))
1702
      return NULL;
1703
1704
    return new_nexthop(po, m->ip, ifa->iface, ifa->ecmp_weight);
1705 57c574d8 Ondrej Zajicek
  }
1706
1707
  /* The third case - bcast or nbma neighbor */
1708
  if ((en->lsa.type == LSA_T_RT) && (par->lsa.type == LSA_T_NET))
1709
  {
1710
    /* par->nhi should be defined from parent's calc_next_hop() */
1711
    if (!pn)
1712
      goto bad;
1713
1714
#ifdef OSPFv2
1715
    /*
1716
     * In this case, next-hop is the same as link-back, which is
1717
     * already computed in link_back().
1718
     */
1719
    if (ipa_zero(en->lb))
1720
      goto bad;
1721
1722
    return new_nexthop(po, en->lb, pn->iface, pn->weight);
1723
1724
#else /* OSPFv3 */
1725
    /*
1726
     * Next-hop is taken from lladdr field of Link-LSA, en->lb_id
1727
     * is computed in link_back().
1728
     */
1729
    struct top_hash_entry *lhe;
1730
    lhe = ospf_hash_find(po->gr, pn->iface->index, en->lb_id, rid, LSA_T_LINK);
1731
1732
    if (!lhe)
1733
      return NULL;
1734
1735
    struct ospf_lsa_link *llsa = lhe->lsa_body;
1736
      
1737
    if (ipa_zero(llsa->lladdr))
1738
      return NULL;
1739
1740
    return new_nexthop(po, llsa->lladdr, pn->iface, pn->weight);
1741
#endif
1742
  }
1743
1744
 bad:
1745
  /* Probably bug or some race condition, we log it */
1746
  log(L_ERR "Unexpected case in next hop calculation");
1747
  return NULL;
1748
}
1749
1750
/* Compare nexthops during merge.
1751
   We need to maintain nhs sorted to eliminate duplicities */
1752
static int
1753
cmp_nhs(struct mpnh *s1, struct mpnh *s2)
1754
{
1755
  int r;
1756
1757
  if (!s1)
1758
    return 1;
1759
1760
  if (!s2)
1761
    return -1;
1762
1763
  r = ((int) s2->weight) - ((int) s1->weight);
1764
  if (r)
1765
    return r;
1766
1767
  r = ipa_compare(s1->gw, s2->gw);
1768
  if (r)
1769
    return r;
1770
1771
  return ((int) s1->iface->index) - ((int) s2->iface->index);
1772
}
1773
1774
static void
1775
merge_nexthops(struct proto_ospf *po, struct top_hash_entry *en,
1776
               struct top_hash_entry *par, struct mpnh *new)
1777
{
1778
  if (en->nhs == new)
1779
    return;
1780
1781
  int r1 = en->nhs_reuse;
1782
  int r2 = (par->nhs != new);
1783
  int count = po->ecmp;
1784
  struct mpnh *s1 = en->nhs;
1785
  struct mpnh *s2 = new;
1786
  struct mpnh **n = &(en->nhs);
1787
1788
  /*
1789
   * r1, r2 signalize whether we can reuse nexthops from s1, s2.
1790
   * New nexthops (s2, new) can be reused if they are not inherited
1791
   * from the parent (i.e. it is allocated in calc_next_hop()).
1792
   * Current nexthops (s1, en->nhs) can be reused if they weren't
1793
   * inherited in previous steps (that is stored in nhs_reuse,
1794
   * i.e. created by merging or allocalted in calc_next_hop()).
1795
   *
1796
   * Generally, a node first inherits shared nexthops from its
1797
   * parent and later possibly gets reusable copy during merging.
1798
   */
1799
1800
  while ((s1 || s2) && count--)
1801
  {
1802
    int cmp = cmp_nhs(s1, s2);
1803
    if (cmp < 0)
1804
    {
1805
      *n = r1 ? s1 : copy_nexthop(po, s1);
1806
      s1 = s1->next;
1807
    }
1808
    else if (cmp > 0)
1809
    {
1810
      *n = r2 ? s2 : copy_nexthop(po, s2);
1811
      s2 = s2->next;
1812
    }
1813
    else
1814
    {
1815
      *n = r1 ? s1 : (r2 ? s2 : copy_nexthop(po, s1));
1816
      s1 = s1->next;
1817
      s2 = s2->next;
1818
    }
1819
    n = &((*n)->next);
1820
  }
1821
  *n = NULL;
1822
1823
  en->nhs_reuse=1;
1824
}
1825
1826 baa5dd6c Ondrej Filip
/* Add LSA into list of candidates in Dijkstra's algorithm */
1827 b8f17cf1 Ondrej Filip
static void
1828 2e10a170 Ondrej Filip
add_cand(list * l, struct top_hash_entry *en, struct top_hash_entry *par,
1829 e7b4948c Ondrej Zajicek
         u32 dist, struct ospf_area *oa, int pos)
1830 dfa9a53a Ondrej Filip
{
1831 57c574d8 Ondrej Zajicek
  struct proto_ospf *po = oa->po;
1832 2e10a170 Ondrej Filip
  node *prev, *n;
1833
  int added = 0;
1834 e80e9d0d Ondrej Filip
  struct top_hash_entry *act;
1835 dfa9a53a Ondrej Filip
1836 b49e6f5a Ondrej Zajicek
  /* 16.1. (2b) */
1837 2e10a170 Ondrej Filip
  if (en == NULL)
1838
    return;
1839
  if (en->lsa.age == LSA_MAXAGE)
1840
    return;
1841 98ac6176 Ondrej Filip
1842 b49e6f5a Ondrej Zajicek
#ifdef OSPFv3
1843
  if (en->lsa.type == LSA_T_RT)
1844
    {
1845
      struct ospf_lsa_rt *rt = en->lsa_body;
1846 f623ab98 Ondrej Zajicek
      if (!(rt->options & OPT_V6))
1847 b49e6f5a Ondrej Zajicek
        return;
1848
    }
1849
#endif
1850
1851 c3226991 Ondrej Zajicek
  /* 16.1. (2c) */
1852 2e10a170 Ondrej Filip
  if (en->color == INSPF)
1853
    return;
1854 dfa9a53a Ondrej Filip
1855 6384c7d7 Ondrej Zajicek
  /* 16.1. (2d), also checks that dist < LSINFINITY */
1856 57c574d8 Ondrej Zajicek
  if (dist > en->dist)
1857 2e10a170 Ondrej Filip
    return;
1858 98ac6176 Ondrej Filip
1859 9807690b Ondrej Zajicek
  /* We should check whether there is a reverse link from en to par, */
1860 98ac6176 Ondrej Filip
  if (!link_back(oa, en, par))
1861
    return;
1862
1863 e7b4948c Ondrej Zajicek
  struct mpnh *nhs = calc_next_hop(oa, en, par, pos);
1864 57c574d8 Ondrej Zajicek
  if (!nhs)
1865 b76aeb82 Ondrej Zajicek
  {
1866
    log(L_WARN "Cannot find next hop for LSA (Type: %04x, Id: %R, Rt: %R)",
1867
        en->lsa.type, en->lsa.id, en->lsa.rt);
1868
    return;
1869
  }
1870
1871 57c574d8 Ondrej Zajicek
  if (dist == en->dist)
1872
  {
1873
    /*
1874
     * For multipath, we should merge nexthops. We do not mix dummy
1875
     * vlink nexthops, device nexthops and gateway nexthops. We merge
1876
     * gateway nexthops only. We prefer device nexthops over gateway
1877
     * nexthops and gateway nexthops over vlink nexthops. We either
1878
     * keep old nexthops, merge old and new, or replace old with new.
1879
     * 
1880
     * We know that en->color == CANDIDATE and en->nhs is defined.
1881
     */
1882
    struct mpnh *onhs = en->nhs;
1883
1884
    /* Keep old ones */
1885
    if (!po->ecmp || !nhs->iface || (onhs->iface && ipa_zero(onhs->gw)))
1886
      return;
1887
1888
    /* Merge old and new */
1889
    if (ipa_nonzero(nhs->gw) && ipa_nonzero(onhs->gw))
1890
    {
1891
      merge_nexthops(po, en, par, nhs);
1892
      return;
1893
    }
1894
1895
    /* Fallback to replace old ones */
1896
  }
1897
1898 3aab39f5 Ondrej Zajicek
  DBG("     Adding candidate: rt: %R, id: %R, type: %u\n",
1899
      en->lsa.rt, en->lsa.id, en->lsa.type);
1900 2e10a170 Ondrej Filip
1901 1a61882d Ondrej Filip
  if (en->color == CANDIDATE)
1902
  {                                /* We found a shorter path */
1903 e80e9d0d Ondrej Filip
    rem_node(&en->cn);
1904 dfa9a53a Ondrej Filip
  }
1905 57c574d8 Ondrej Zajicek
  en->nhs = nhs;
1906 2e10a170 Ondrej Filip
  en->dist = dist;
1907
  en->color = CANDIDATE;
1908 57c574d8 Ondrej Zajicek
  en->nhs_reuse = (par->nhs != nhs);
1909 dfa9a53a Ondrej Filip
1910 2e10a170 Ondrej Filip
  prev = NULL;
1911 dfa9a53a Ondrej Filip
1912 2e10a170 Ondrej Filip
  if (EMPTY_LIST(*l))
1913 e80e9d0d Ondrej Filip
  {
1914 2e10a170 Ondrej Filip
    add_head(l, &en->cn);
1915 85195f1a Ondrej Filip
  }
1916
  else
1917
  {
1918 2e10a170 Ondrej Filip
    WALK_LIST(n, *l)
1919 dfa9a53a Ondrej Filip
    {
1920 2e10a170 Ondrej Filip
      act = SKIP_BACK(struct top_hash_entry, cn, n);
1921
      if ((act->dist > dist) ||
1922 57c574d8 Ondrej Zajicek
          ((act->dist == dist) && (act->lsa.type == LSA_T_RT)))
1923 85195f1a Ondrej Filip
      {
1924 2e10a170 Ondrej Filip
        if (prev == NULL)
1925
          add_head(l, &en->cn);
1926
        else
1927
          insert_node(&en->cn, prev);
1928
        added = 1;
1929
        break;
1930 85195f1a Ondrej Filip
      }
1931 2e10a170 Ondrej Filip
      prev = n;
1932 85195f1a Ondrej Filip
    }
1933
1934 2e10a170 Ondrej Filip
    if (!added)
1935 85195f1a Ondrej Filip
    {
1936 2e10a170 Ondrej Filip
      add_tail(l, &en->cn);
1937 dfa9a53a Ondrej Filip
    }
1938
  }
1939
}
1940 468f2347 Ondrej Filip
1941 b49e6f5a Ondrej Zajicek
static inline int
1942 57c574d8 Ondrej Zajicek
ort_changed(ort *nf, rta *nr)
1943 b49e6f5a Ondrej Zajicek
{
1944 57c574d8 Ondrej Zajicek
  rta *or = nf->old_rta;
1945
  return !or ||
1946
    (nf->n.metric1 != nf->old_metric1) || (nf->n.metric2 != nf->old_metric2) ||
1947
    (nf->n.tag != nf->old_tag) || (nf->n.rid != nf->old_rid) ||
1948
    (nr->source != or->source) || (nr->dest != or->dest) ||
1949
    (nr->iface != or->iface) || !ipa_equal(nr->gw, or->gw) ||
1950
    !mpnh_same(nr->nexthops, or->nexthops);
1951 a92847e7 Ondrej Filip
}
1952 1a61882d Ondrej Filip
1953
static void
1954
rt_sync(struct proto_ospf *po)
1955
{
1956
  struct proto *p = &po->proto;
1957
  struct fib_iterator fit;
1958 98ac6176 Ondrej Filip
  struct fib *fib = &po->rtf;
1959 1a61882d Ondrej Filip
  ort *nf;
1960 6384c7d7 Ondrej Zajicek
  struct ospf_area *oa;
1961 98ac6176 Ondrej Filip
1962 f7574707 Ondrej Zajicek
  /* This is used for forced reload of routes */
1963
  int reload = (po->calcrt == 2);
1964
1965 98ac6176 Ondrej Filip
  OSPF_TRACE(D_EVENTS, "Starting routing table synchronisation");
1966 1a61882d Ondrej Filip
1967
  DBG("Now syncing my rt table with nest's\n");
1968
  FIB_ITERATE_INIT(&fit, fib);
1969 98ac6176 Ondrej Filip
again1:
1970 1a61882d Ondrej Filip
  FIB_ITERATE_START(fib, &fit, nftmp)
1971
  {
1972
    nf = (ort *) nftmp;
1973 3b89a232 Ondrej Zajicek
1974 57c574d8 Ondrej Zajicek
    /* Sanity check of next-hop addresses, failure should not happen */
1975
    if (nf->n.type)
1976 6384c7d7 Ondrej Zajicek
    {
1977 57c574d8 Ondrej Zajicek
      struct mpnh *nh;
1978
      for (nh = nf->n.nhs; nh; nh = nh->next)
1979
        if (ipa_nonzero(nh->gw))
1980
        {
1981
          neighbor *ng = neigh_find2(p, &nh->gw, nh->iface, 0);
1982
          if (!ng || (ng->scope == SCOPE_HOST))
1983
            { reset_ri(nf); break; }
1984
        }
1985 6384c7d7 Ondrej Zajicek
    }
1986 27a1e3ac Ondrej Filip
1987 e0a62ad0 Ondrej Zajicek
    /* Remove configured stubnets */
1988 57c574d8 Ondrej Zajicek
    if (!nf->n.nhs)
1989
      reset_ri(nf);
1990 e0a62ad0 Ondrej Zajicek
1991 57c574d8 Ondrej Zajicek
    if (nf->n.type) /* Add the route */
1992 6384c7d7 Ondrej Zajicek
    {
1993 57c574d8 Ondrej Zajicek
      rta a0 = {
1994
        .proto = p,
1995
        .source = nf->n.type,
1996
        .scope = SCOPE_UNIVERSE,
1997
        .cast = RTC_UNICAST,
1998
      };
1999
2000
      if (nf->n.nhs->next)
2001 98ac6176 Ondrej Filip
      {
2002 57c574d8 Ondrej Zajicek
        a0.dest = RTD_MULTIPATH;
2003
        a0.nexthops = nf->n.nhs;
2004
      }
2005
      else if (ipa_nonzero(nf->n.nhs->gw))
2006
      {
2007
        a0.dest = RTD_ROUTER;
2008
        a0.iface = nf->n.nhs->iface;
2009
        a0.gw = nf->n.nhs->gw;
2010
      }
2011
      else
2012
      {
2013
        a0.dest = RTD_DEVICE;
2014
        a0.iface = nf->n.nhs->iface;
2015
      }
2016 6384c7d7 Ondrej Zajicek
2017 57c574d8 Ondrej Zajicek
      if (reload || ort_changed(nf, &a0))
2018
      {
2019
        net *ne = net_get(p->table, nf->fn.prefix, nf->fn.pxlen);
2020
        rta *a = rta_lookup(&a0);
2021
        rte *e = rte_get_temp(a);
2022
2023
        rta_free(nf->old_rta);
2024
        nf->old_rta = rta_clone(a);
2025
        e->u.ospf.metric1 = nf->old_metric1 = nf->n.metric1;
2026
        e->u.ospf.metric2 = nf->old_metric2 = nf->n.metric2;
2027
        e->u.ospf.tag = nf->old_tag = nf->n.tag;
2028
        e->u.ospf.router_id = nf->old_rid = nf->n.rid;
2029 6384c7d7 Ondrej Zajicek
        e->pflags = 0;
2030
        e->net = ne;
2031
        e->pref = p->preference;
2032 57c574d8 Ondrej Zajicek
2033 6384c7d7 Ondrej Zajicek
        DBG("Mod rte type %d - %I/%d via %I on iface %s, met %d\n",
2034
            a0.source, nf->fn.prefix, nf->fn.pxlen, a0.gw, a0.iface ? a0.iface->name : "(none)", nf->n.metric1);
2035
        rte_update(p->table, ne, p, p, e);
2036 98ac6176 Ondrej Filip
      }
2037 57c574d8 Ondrej Zajicek
    }
2038
    else if (nf->old_rta)
2039
    {
2040
      /* Remove the route */
2041
      rta_free(nf->old_rta);
2042
      nf->old_rta = NULL;
2043
2044
      net *ne = net_get(p->table, nf->fn.prefix, nf->fn.pxlen);
2045
      rte_update(p->table, ne, p, p, NULL);
2046 6384c7d7 Ondrej Zajicek
    }
2047
2048
    /* Remove unused rt entry. Entries with fn.x0 == 1 are persistent. */
2049 ed317862 Ondrej Zajicek
    if (!nf->n.type && !nf->fn.x0 && !nf->fn.x1)
2050 6384c7d7 Ondrej Zajicek
    {
2051 3b89a232 Ondrej Zajicek
      FIB_ITERATE_PUT(&fit, nftmp);
2052
      fib_delete(fib, nftmp);
2053
      goto again1;
2054 1a61882d Ondrej Filip
    }
2055
  }
2056
  FIB_ITERATE_END(nftmp);
2057 98ac6176 Ondrej Filip
2058 3b89a232 Ondrej Zajicek
2059 98ac6176 Ondrej Filip
  WALK_LIST(oa, po->area_list)
2060
  {
2061 6384c7d7 Ondrej Zajicek
    /* Cleanup ASBR hash tables */
2062 98ac6176 Ondrej Filip
    FIB_ITERATE_INIT(&fit, &oa->rtr);
2063
again2:
2064
    FIB_ITERATE_START(&oa->rtr, &fit, nftmp)
2065
    {
2066
      nf = (ort *) nftmp;
2067
2068 6384c7d7 Ondrej Zajicek
      if (!nf->n.type)
2069 3b16080c Ondrej Filip
      {
2070 6384c7d7 Ondrej Zajicek
        FIB_ITERATE_PUT(&fit, nftmp);
2071
        fib_delete(&oa->rtr, nftmp);
2072
        goto again2;
2073 3b16080c Ondrej Filip
      }
2074 98ac6176 Ondrej Filip
    }
2075 6384c7d7 Ondrej Zajicek
    FIB_ITERATE_END(nftmp);
2076 98ac6176 Ondrej Filip
  }
2077 1a61882d Ondrej Filip
}