Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (47.7 KB)

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