Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (48.9 KB)

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