Revision 145368f5

View differences:

doc/bird.sgml
2291 2291
	stub router <switch>;
2292 2292
	tick <num>;
2293 2293
	ecmp <switch> [limit <num>];
2294
	merge external <switch>;
2294 2295
	area <id> {
2295 2296
		stub;
2296 2297
		nssa;
......
2396 2397
	nexthops in one route. By default, ECMP is disabled. If enabled,
2397 2398
	default	value of the limit is 16.
2398 2399

  
2400
	<tag>merge external <M>switch</M></tag>
2401
	This option specifies whether OSPF should merge external routes from
2402
	different routers/LSAs for the same destination. When enabled together
2403
	with <cf/ecmp/, equal-cost external routes will be combined to multipath
2404
	routes in the same way as regular routes. When disabled, external routes
2405
	from different LSAs are treated as separate even if they represents the
2406
	same destination. Default value is no.
2407

  
2399 2408
	<tag>area <M>id</M></tag>
2400 2409
	This defines an OSPF area with given area ID (an integer or an IPv4
2401 2410
	address, similarly to a router ID). The most important area is the
proto/ospf/config.Y
132 132
CF_KEYWORDS(RX, BUFFER, LARGE, NORMAL, STUBNET, HIDDEN, SUMMARY, TAG, EXTERNAL)
133 133
CF_KEYWORDS(WAIT, DELAY, LSADB, ECMP, LIMIT, WEIGHT, NSSA, TRANSLATOR, STABILITY)
134 134
CF_KEYWORDS(GLOBAL, LSID, ROUTER, SELF, INSTANCE, REAL, NETMASK, TX, PRIORITY, LENGTH)
135
CF_KEYWORDS(SECONDARY)
135
CF_KEYWORDS(SECONDARY, MERGE)
136 136

  
137 137
%type <t> opttext
138 138
%type <ld> lsadb_args
......
162 162
 | STUB ROUTER bool { OSPF_CFG->stub_router = $3; }
163 163
 | ECMP bool { OSPF_CFG->ecmp = $2 ? DEFAULT_ECMP_LIMIT : 0; }
164 164
 | ECMP bool LIMIT expr { OSPF_CFG->ecmp = $2 ? $4 : 0; if ($4 < 0) cf_error("ECMP limit cannot be negative"); }
165
 | MERGE EXTERNAL bool { OSPF_CFG->merge_external = $3; }
165 166
 | TICK expr { OSPF_CFG->tick = $2; if($2<=0) cf_error("Tick must be greater than zero"); }
166 167
 | ospf_area
167 168
 ;
proto/ospf/ospf.c
234 234
  po->router_id = proto_get_router_id(p->cf);
235 235
  po->rfc1583 = c->rfc1583;
236 236
  po->stub_router = c->stub_router;
237
  po->merge_external = c->merge_external;
237 238
  po->ebit = 0;
238 239
  po->ecmp = c->ecmp;
239 240
  po->tick = c->tick;
......
742 743
    return 0;
743 744

  
744 745
  po->stub_router = new->stub_router;
746
  po->merge_external = new->merge_external;
745 747
  po->ecmp = new->ecmp;
746 748
  po->tick = new->tick;
747 749
  po->disp_timer->recurrent = po->tick;
proto/ospf/ospf.h
81 81
  unsigned tick;
82 82
  byte rfc1583;
83 83
  byte stub_router;
84
  byte merge_external;
84 85
  byte abr;
85 86
  int ecmp;
86 87
  list area_list;		/* list of struct ospf_area_config */
......
777 778
  struct fib rtf;		/* Routing table */
778 779
  byte rfc1583;			/* RFC1583 compatibility */
779 780
  byte stub_router;		/* Do not forward transit traffic */
781
  byte merge_external;		/* Should i merge external routes? */
780 782
  byte ebit;			/* Did I originate any ext lsa? */
781 783
  byte ecmp;			/* Maximal number of nexthops in ECMP route, or 0 */
782 784
  struct ospf_area *backbone;	/* If exists */
proto/ospf/rt.c
37 37
}
38 38

  
39 39
static inline int
40
unresolved_vlink(struct mpnh *nhs)
40
nh_is_vlink(struct mpnh *nhs)
41 41
{
42
  return nhs && !nhs->iface;
42
  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);
43 49
}
44 50

  
45 51
static inline struct mpnh *
......
54 60
}
55 61

  
56 62
static inline struct mpnh *
57
copy_nexthop(struct proto_ospf *po, struct mpnh *src)
63
copy_nexthop(struct proto_ospf *po, const struct mpnh *src)
58 64
{
59 65
  struct mpnh *nh = lp_alloc(po->nhpool, sizeof(struct mpnh));
60 66
  nh->gw = src->gw;
......
64 70
  return nh;
65 71
}
66 72

  
67

  
68
/* If new is better return 1 */
73
/* Compare nexthops during merge.
74
   We need to maintain nhs sorted to eliminate duplicities */
69 75
static int
70
ri_better(struct proto_ospf *po, orta *new, orta *old)
76
cmp_nhs(struct mpnh *s1, struct mpnh *s2)
71 77
{
72
  if (old->type == RTS_DUMMY)
73
    return 1;
78
  int r;
74 79

  
75
  if (new->type < old->type)
80
  if (!s1)
76 81
    return 1;
77 82

  
78
  if (new->type > old->type)
79
    return 0;
83
  if (!s2)
84
    return -1;
80 85

  
81
  if (new->metric1 < old->metric1)
82
    return 1;
86
  r = ((int) s2->weight) - ((int) s1->weight);
87
  if (r)
88
    return r;
83 89

  
84
  if (new->metric1 > old->metric1)
85
    return 0;
90
  r = ipa_compare(s1->gw, s2->gw);
91
  if (r)
92
    return r;
86 93

  
87
  return 0;
94
  return ((int) s1->iface->index) - ((int) s2->iface->index);
88 95
}
89 96

  
97
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;
90 103

  
91
/* Whether the ASBR or the forward address destination is preferred
92
   in AS external route selection according to 16.4.1. */
104
  /*
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 */
93 143
static inline int
94
epath_preferred(orta *ep)
144
has_device_nexthops(const struct mpnh *n)
95 145
{
96
  return (ep->type == RTS_OSPF) && (ep->oa->areaid != 0);
146
  for (; n; n = n->next)
147
    if (ipa_zero(n->gw))
148
      return 1;
149

  
150
  return 0;
97 151
}
98 152

  
99
/* 16.4. (3), return 1 if new is better */
100
static int
101
ri_better_asbr(struct proto_ospf *po, orta *new, orta *old)
153
/* 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)
102 156
{
103
  if (old->type == RTS_DUMMY)
104
    return 1;
157
  struct mpnh *root1 = NULL;
158
  struct mpnh *root2 = NULL;
159
  struct mpnh **nn1 = &root1;
160
  struct mpnh **nn2 = &root2;
105 161

  
106
  if (!po->rfc1583)
107
  {
108
    int new_pref = epath_preferred(new);
109
    int old_pref = epath_preferred(old);
162
  /* 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. */
110 165

  
111
    if (new_pref > old_pref)
112
      return 1;
166
  for (; n; n = n->next)
167
  {
168
    struct mpnh *nn = new_nexthop(po, ipa_zero(n->gw) ? gw : n->gw, n->iface, n->weight);
113 169

  
114
    if (new_pref < old_pref)
115
      return 0;
170
    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
    }
116 180
  }
117 181

  
118
  if (new->metric1 < old->metric1)
119
    return 1;
182
  return merge_nexthops(po, root1, root2, 1, 1);
183
}
120 184

  
121
  if (new->metric1 > old->metric1)
122
    return 0;
123 185

  
124
  /* Larger area ID is preferred */
125
  if (new->oa->areaid > old->oa->areaid)
126
    return 1;
186
/* 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
}
127 193

  
128
  return 0;
194
/* 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);
129 199
}
130 200

  
201
/* 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 */
131 203
static int
132
orta_prio(orta *nf)
204
orta_prio(const orta *nf)
133 205
{
134 206
  /* RFC 3103 2.5 (6e) priorities */
135 207
  u32 opts = nf->options & (ORTA_NSSA | ORTA_PROP);
......
145 217
  return 0;
146 218
}
147 219

  
148
/* 16.4. (6), return 1 if new is better */
220
/* 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
 */
149 237
static int
150
ri_better_ext(struct proto_ospf *po, orta *new, orta *old)
238
orta_compare(const struct proto_ospf *po, const orta *new, const orta *old)
151 239
{
240
  int r;
241

  
152 242
  if (old->type == RTS_DUMMY)
153 243
    return 1;
154 244

  
155
  /* 16.4. (6a) */
156
  if (new->type < old->type)
245
  /* 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)
157 266
    return 1;
267
  if (nh_is_vlink(new->nhs))
268
    return -1;
269
  if (nh_is_vlink(old->nhs))
270
    return 1;
271

  
158 272

  
159
  if (new->type > old->type)
273
  if (po->ecmp)
160 274
    return 0;
161 275

  
162
  /* 16.4. (6b), same type */
163
  if (new->type == RTS_OSPF_EXT2)
164
  {
165
    if (new->metric2 < old->metric2)
166
      return 1;
276
  /* 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
}
167 282

  
168
    if (new->metric2 > old->metric2)
169
      return 0;
170
  }
283
/*
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;
171 295

  
172
  /* 16.4. (6c) */
173 296
  if (!po->rfc1583)
174 297
  {
175
    u32 new_pref = new->options & ORTA_PREF;
176
    u32 old_pref = old->options & ORTA_PREF;
177

  
178
    if (new_pref > old_pref)
179
      return 1;
180

  
181
    if (new_pref < old_pref)
182
      return 0;
298
    r = epath_preferred(new) - epath_preferred(old);
299
    if (r) return r;
183 300
  }
184 301

  
185
  /* 16.4. (6d) */
186
  if (new->metric1 < old->metric1)
302
  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)
187 307
    return 1;
188 308

  
189
  if (new->metric1 > old->metric1)
190
    return 0;
309
  /* There is just one ASBR of that RID per area, so tie is not possible */
310
  return -1;
311
}
191 312

  
192
  /* RFC 3103, 2.5. (6e) */
193
  int new_prio = orta_prio(new);
194
  int old_prio = orta_prio(old);
313
/*
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;
195 322

  
196
  if (new_prio > old_prio)
323
  if (old->type == RTS_DUMMY)
197 324
    return 1;
198 325

  
199
  if (old_prio > new_prio)
326
  /* 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)
200 350
    return 0;
201 351

  
202
  /* make it more deterministic */
203
  if (new->rid > old->rid)
352
  /*
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))
204 359
    return 1;
205 360

  
206
  return 0;
361
  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;
207 384
}
208 385

  
386
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

  
209 417
static inline void
210
ri_install_net(struct proto_ospf *po, ip_addr prefix, int pxlen, orta *new)
418
ri_install_net(struct proto_ospf *po, ip_addr prefix, int pxlen, const orta *new)
211 419
{
212 420
  ort *old = (ort *) fib_get(&po->rtf, &prefix, pxlen);
213
  if (ri_better(po, new, &old->n))
214
    memcpy(&old->n, new, sizeof(orta));
421
  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);
215 427
}
216 428

  
217 429
static inline void
218
ri_install_rt(struct ospf_area *oa, u32 rid, orta *new)
430
ri_install_rt(struct ospf_area *oa, u32 rid, const orta *new)
219 431
{
220 432
  ip_addr addr = ipa_from_rid(rid);
221 433
  ort *old = (ort *) fib_get(&oa->rtr, &addr, MAX_PREFIX_LENGTH);
222
  if (ri_better(oa->po, new, &old->n))
223
    memcpy(&old->n, new, sizeof(orta));
434
  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);
224 440
}
225 441

  
226 442
static inline void
227
ri_install_asbr(struct proto_ospf *po, ip_addr *addr, orta *new)
443
ri_install_asbr(struct proto_ospf *po, ip_addr *addr, const orta *new)
228 444
{
229 445
  ort *old = (ort *) fib_get(&po->backbone->rtr, addr, MAX_PREFIX_LENGTH);
230
  if (ri_better_asbr(po, new, &old->n))
231
    memcpy(&old->n, new, sizeof(orta));
446
  if (orta_compare_asbr(po, new, &old->n) > 0)
447
    ort_replace(old, new);
232 448
}
233 449

  
234 450
static inline void
235
ri_install_ext(struct proto_ospf *po, ip_addr prefix, int pxlen, orta *new)
451
ri_install_ext(struct proto_ospf *po, ip_addr prefix, int pxlen, const orta *new)
236 452
{
237 453
  ort *old = (ort *) fib_get(&po->rtf, &prefix, pxlen);
238
  if (ri_better_ext(po, new, &old->n))
239
    memcpy(&old->n, new, sizeof(orta));
454
  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);
240 460
}
241 461

  
242 462
static inline struct ospf_iface *
......
842 1062

  
843 1063
    /* 16.3. (5) */
844 1064
    if ((metric < re->n.metric1) || 
845
	((metric == re->n.metric1) && unresolved_vlink(re->n.nhs)))
1065
	((metric == re->n.metric1) && unresolved_vlink(re)))
846 1066
    {
847 1067
      /* We want to replace the next-hop even if the metric is equal
848 1068
	 to replace a virtual next-hop through vlink with a real one.
......
1129 1349
  struct area_net *anet;
1130 1350
  ort *nf, *default_nf;
1131 1351

  
1352
  /* 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

  
1132 1363
  FIB_WALK(&po->rtf, nftmp)
1133 1364
  {
1134 1365
    nf = (ort *) nftmp;
1135 1366

  
1136 1367

  
1137
    /* RFC 2328 G.3 - incomplete resolution of virtual next hops */
1138
    if (nf->n.type && unresolved_vlink(nf->n.nhs))
1368
    /* RFC 2328 G.3 - incomplete resolution of virtual next hops - networks */
1369
    if (nf->n.type && unresolved_vlink(nf))
1139 1370
      reset_ri(nf);
1140 1371

  
1141 1372

  
......
1361 1592
ospf_ext_spf(struct proto_ospf *po)
1362 1593
{
1363 1594
  ort *nf1, *nf2;
1364
  orta nfa;
1595
  orta nfa = {};
1365 1596
  struct top_hash_entry *en;
1366 1597
  struct proto *p = &po->proto;
1367 1598
  struct ospf_lsa_ext *le;
......
1369 1600
  ip_addr ip, rtid, rt_fwaddr;
1370 1601
  u32 br_metric, rt_metric, rt_tag;
1371 1602
  struct ospf_area *atmp;
1372
  struct mpnh* nhs = NULL;
1373 1603

  
1374 1604
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation for ext routes");
1375 1605

  
......
1465 1695
    if (!rt_fwaddr_valid)
1466 1696
    {
1467 1697
      nf2 = nf1;
1468
      nhs = nf1->n.nhs;
1698
      nfa.nhs = nf1->n.nhs;
1469 1699
      br_metric = nf1->n.metric1;
1470 1700
    }
1471 1701
    else
......
1491 1721
      if (!nf2->n.nhs)
1492 1722
	continue;
1493 1723

  
1494
      nhs = nf2->n.nhs;
1495
      /* If gw is zero, it is a device route */
1496
      if (ipa_zero(nhs->gw))
1497
	nhs = new_nexthop(po, rt_fwaddr, nhs->iface, nhs->weight);
1724
      nfa.nhs = nf2->n.nhs;
1498 1725
      br_metric = nf2->n.metric1;
1726

  
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
      }
1499 1733
    }
1500 1734

  
1501 1735
    if (ebit)
......
1526 1760
    nfa.tag = rt_tag;
1527 1761
    nfa.rid = en->lsa.rt;
1528 1762
    nfa.oa = atmp; /* undefined in RFC 2328 */
1529
    nfa.voa = NULL;
1530
    nfa.nhs = nhs;
1531 1763
    nfa.en = en; /* store LSA for later (NSSA processing) */
1532 1764

  
1533 1765
    ri_install_ext(po, ip, pxlen, &nfa);
......
1745 1977
  return NULL;
1746 1978
}
1747 1979

  
1748
/* Compare nexthops during merge.
1749
   We need to maintain nhs sorted to eliminate duplicities */
1750
static int
1751
cmp_nhs(struct mpnh *s1, struct mpnh *s2)
1752
{
1753
  int r;
1754

  
1755
  if (!s1)
1756
    return 1;
1757

  
1758
  if (!s2)
1759
    return -1;
1760

  
1761
  r = ((int) s2->weight) - ((int) s1->weight);
1762
  if (r)
1763
    return r;
1764

  
1765
  r = ipa_compare(s1->gw, s2->gw);
1766
  if (r)
1767
    return r;
1768

  
1769
  return ((int) s1->iface->index) - ((int) s2->iface->index);
1770
}
1771

  
1772
static void
1773
merge_nexthops(struct proto_ospf *po, struct top_hash_entry *en,
1774
	       struct top_hash_entry *par, struct mpnh *new)
1775
{
1776
  if (en->nhs == new)
1777
    return;
1778

  
1779
  int r1 = en->nhs_reuse;
1780
  int r2 = (par->nhs != new);
1781
  int count = po->ecmp;
1782
  struct mpnh *s1 = en->nhs;
1783
  struct mpnh *s2 = new;
1784
  struct mpnh **n = &(en->nhs);
1785

  
1786
  /*
1787
   * r1, r2 signalize whether we can reuse nexthops from s1, s2.
1788
   * New nexthops (s2, new) can be reused if they are not inherited
1789
   * from the parent (i.e. it is allocated in calc_next_hop()).
1790
   * Current nexthops (s1, en->nhs) can be reused if they weren't
1791
   * inherited in previous steps (that is stored in nhs_reuse,
1792
   * i.e. created by merging or allocalted in calc_next_hop()).
1793
   *
1794
   * Generally, a node first inherits shared nexthops from its
1795
   * parent and later possibly gets reusable copy during merging.
1796
   */
1797

  
1798
  while ((s1 || s2) && count--)
1799
  {
1800
    int cmp = cmp_nhs(s1, s2);
1801
    if (cmp < 0)
1802
    {
1803
      *n = r1 ? s1 : copy_nexthop(po, s1);
1804
      s1 = s1->next;
1805
    }
1806
    else if (cmp > 0)
1807
    {
1808
      *n = r2 ? s2 : copy_nexthop(po, s2);
1809
      s2 = s2->next;
1810
    }
1811
    else
1812
    {
1813
      *n = r1 ? s1 : (r2 ? s2 : copy_nexthop(po, s1));
1814
      s1 = s1->next;
1815
      s2 = s2->next;
1816
    }
1817
    n = &((*n)->next);
1818
  }
1819
  *n = NULL;
1820

  
1821
  en->nhs_reuse=1;
1822
}
1823 1980

  
1824 1981
/* Add LSA into list of candidates in Dijkstra's algorithm */
1825 1982
static void
......
1866 2023
    return;
1867 2024
  }
1868 2025

  
1869
  if (dist == en->dist)
2026
  /* We know that en->color == CANDIDATE and en->nhs is defined. */
2027

  
2028
  if ((dist == en->dist) && !nh_is_vlink(en->nhs))
1870 2029
  {
1871 2030
    /*
1872
     * For multipath, we should merge nexthops. We do not mix dummy
1873
     * vlink nexthops, device nexthops and gateway nexthops. We merge
1874
     * gateway nexthops only. We prefer device nexthops over gateway
1875
     * nexthops and gateway nexthops over vlink nexthops. We either
1876
     * keep old nexthops, merge old and new, or replace old with new.
1877
     * 
1878
     * We know that en->color == CANDIDATE and en->nhs is defined.
2031
     * 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.
1879 2042
     */
1880
    struct mpnh *onhs = en->nhs;
1881 2043

  
1882 2044
    /* Keep old ones */
1883
    if (!po->ecmp || !nhs->iface || (onhs->iface && ipa_zero(onhs->gw)))
2045
    if (!po->ecmp || nh_is_vlink(nhs) || (nhs == en->nhs))
1884 2046
      return;
1885 2047

  
1886 2048
    /* Merge old and new */
1887
    if (ipa_nonzero(nhs->gw) && ipa_nonzero(onhs->gw))
1888
    {
1889
      merge_nexthops(po, en, par, nhs);
1890
      return;
1891
    }
1892

  
1893
    /* Fallback to replace old ones */
2049
    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;
1894 2053
  }
1895 2054

  
1896 2055
  DBG("     Adding candidate: rt: %R, id: %R, type: %u\n",
proto/ospf/rt.h
16 16

  
17 17
typedef struct orta
18 18
{
19
  int type;
19
  u8 type;			/* RTS_OSPF_* */
20
  u8 nhs_reuse;			/* Whether nhs nodes can be reused during merging */
20 21
  u32 options;
21 22
  /*
22 23
   * For ORT_ROUTER routes, options field are router-LSA style
......
93 94
 * - n.metric1 may be at most a small multiple of LSINFINITY,
94 95
 *   therefore sums do not overflow
95 96
 * - n.oa is always non-NULL
96
 * - n.nhs is always non-NULL with one exception - configured stubnet
97
 *   nodes (in po->rtf).
97
 * - n.nhs is always non-NULL unless it is configured stubnet
98
 * - n.en is non-NULL for external routes, NULL for intra/inter area routes.
98 99
 * - oa->rtr does not contain calculating router itself
99 100
 *
100
 * There are three types of nexthops in nhs fields:
101
 * There are four types of nexthops in nhs fields:
101 102
 * - gateway nexthops (non-NULL iface, gw != IPA_NONE)
102 103
 * - device nexthops (non-NULL iface, gw == IPA_NONE)
103 104
 * - dummy vlink nexthops (NULL iface, gw == IPA_NONE)
104
 * These three types don't mix, nhs field contains either
105
 * one device, one vlink node, or one/more gateway nodes.
105
 * - configured stubnets (nhs is NULL, only RTS_OSPF orta nodes in po->rtf)
106
 *
107
 * Dummy vlink nexthops and configured stubnets cannot be mixed with
108
 * regular ones, nhs field contains either list of gateway+device nodes,
109
 * one vlink node, or NULL for configured stubnet.
110
 *
111
 * Dummy vlink nexthops can appear in both network (rtf) and backbone area router
112
 * (rtr) tables for regular and inter-area routes, but only if areano > 1. They are
113
 * replaced in ospf_rt_sum_tr() and removed in ospf_rt_abr1(), therefore cannot
114
 * appear in ASBR pre-selection and external routes processing.
106 115
 */
107 116

  
108 117
void ospf_rt_spf(struct proto_ospf *po);

Also available in: Unified diff