Statistics
| Branch: | Revision:

iof-bird-daemon / proto / ospf / rt.c @ 145368f5

History | View | Annotate | Download (52.8 KB)

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