Statistics
| Branch: | Revision:

iof-bird-daemon / proto / ospf / topology.c @ 48e5f32d

History | View | Annotate | Download (45.7 KB)

1 6ba36f06 Martin Mares
/*
2
 *        BIRD -- OSPF Topological Database
3
 *
4 98ac6176 Ondrej Filip
 *        (c) 1999       Martin Mares <mj@ucw.cz>
5
 *        (c) 1999--2004 Ondrej Filip <feela@network.cz>
6 6ba36f06 Martin Mares
 *
7
 *        Can be freely distributed and used under the terms of the GNU GPL.
8
 */
9
10
#include "nest/bird.h"
11 221135d6 Martin Mares
#include "lib/string.h"
12 6ba36f06 Martin Mares
13
#include "ospf.h"
14
15 8d56febe Ondrej Filip
#define HASH_DEF_ORDER 6
16 6ba36f06 Martin Mares
#define HASH_HI_MARK *4
17
#define HASH_HI_STEP 2
18
#define HASH_HI_MAX 16
19
#define HASH_LO_MARK /5
20
#define HASH_LO_STEP 2
21
#define HASH_LO_MIN 8
22
23 b49e6f5a Ondrej Zajicek
void originate_prefix_rt_lsa(struct ospf_area *oa);
24
void originate_prefix_net_lsa(struct ospf_iface *ifa);
25 061ab802 Ondrej Zajicek
void flush_prefix_net_lsa(struct ospf_iface *ifa);
26 b49e6f5a Ondrej Zajicek
27
#ifdef OSPFv2
28
#define ipa_to_rid(x) _I(x)
29
#else /* OSPFv3 */
30
#define ipa_to_rid(x) _I3(x)
31
#endif
32
33 d82fc18d Ondrej Zajicek
34 b49e6f5a Ondrej Zajicek
#ifdef OSPFv2
35 d82fc18d Ondrej Zajicek
static inline u32
36
fibnode_to_lsaid(struct proto_ospf *po, struct fib_node *fn)
37
{
38
  /* We have to map IP prefixes to u32 in such manner that resulting
39
     u32 interpreted as IP address is a member of given
40
     prefix. Therefore, /32 prefix have to be mapped on itself.
41
     All received prefixes have to be mapped on different u32s.
42

43
     We have an assumption that if there is nontrivial (non-/32)
44
     network prefix, then there is not /32 prefix for the first
45
     and the last IP address of the network (these are usually
46
     reserved, therefore it is not an important restriction).
47
     The network prefix is mapped to the first or the last
48
     IP address in the manner that disallow collisions - we
49
     use IP address that cannot be used by parent prefix.
50

51
     For example:
52
     192.168.0.0/24 maps to 192.168.0.255
53
     192.168.1.0/24 maps to 192.168.1.0
54
     because 192.168.0.0 and 192.168.1.255 might be used by
55
     192.168.0.0/23 .
56

57
     This is not compatible with older RFC 1583, so we have an option
58
     to the RFC 1583 compatible assignment (that always uses the first
59
     address) which disallows subnetting.
60

61
     Appendig E of RFC 2328 suggests different algorithm, that tries
62
     to maximize both compatibility and subnetting. But as it is not
63
     possible to have both reliably and the suggested algorithm was
64
     unnecessary complicated and it does crazy things like changing
65
     LSA ID for a network because different network appeared, we
66
     choose a different way. */
67
68
  u32 id = _I(fn->prefix);
69
70
  if ((po->rfc1583) || (fn->pxlen == 0) || (fn->pxlen == 32))
71
    return id;
72
73
  if (id & (1 << (32 - fn->pxlen)))
74
    return id;
75
  else
76
    return id | ~u32_mkmask(fn->pxlen);
77
}
78
79 b49e6f5a Ondrej Zajicek
#else /* OSPFv3 */
80 d82fc18d Ondrej Zajicek
81
static inline u32
82
fibnode_to_lsaid(struct proto_ospf *po, struct fib_node *fn)
83
{
84 6384c7d7 Ondrej Zajicek
  /*
85
   * In OSPFv3, it is simpler. There is not a requirement for
86
   * membership of the result in the input network, so we just use a
87
   * hash-based unique ID of a routing table entry for a route that
88
   * originated given LSA. For ext-LSA, it is an imported route in the
89
   * nest's routing table (p->table). For summary-LSA, it is a
90
   * 'source' route in the protocol internal routing table (po->rtf).
91
   */
92 d82fc18d Ondrej Zajicek
  return fn->uid;
93
}
94
95 b49e6f5a Ondrej Zajicek
#endif
96
97
98 9831e591 Martin Mares
static void *
99 3d15dcdb Ondrej Zajicek
lsab_alloc(struct proto_ospf *po, unsigned size)
100
{
101
  unsigned offset = po->lsab_used;
102
  po->lsab_used += size;
103
  if (po->lsab_used > po->lsab_size)
104
    {
105
      po->lsab_size = MAX(po->lsab_used, 2 * po->lsab_size);
106 6a8d3f1c Ondrej Zajicek
      po->lsab = po->lsab ? mb_realloc(po->lsab, po->lsab_size):
107
        mb_alloc(po->proto.pool, po->lsab_size);
108 3d15dcdb Ondrej Zajicek
    }
109
  return ((byte *) po->lsab) + offset;
110
}
111
112
static inline void *
113
lsab_allocz(struct proto_ospf *po, unsigned size)
114
{
115
  void *r = lsab_alloc(po, size);
116
  bzero(r, size);
117
  return r;
118
}
119
120
static inline void *
121
lsab_flush(struct proto_ospf *po)
122
{
123 f0160f0e Ondrej Zajicek
  void *r = mb_alloc(po->proto.pool, po->lsab_used);
124 3d15dcdb Ondrej Zajicek
  memcpy(r, po->lsab, po->lsab_used);
125
  po->lsab_used = 0;
126
  return r;
127
}
128
129 c3226991 Ondrej Zajicek
static inline void *
130
lsab_offset(struct proto_ospf *po, unsigned offset)
131
{
132
  return ((byte *) po->lsab) + offset;
133
}
134
135
static inline void *
136
lsab_end(struct proto_ospf *po)
137
{
138
  return ((byte *) po->lsab) + po->lsab_used;
139
}
140
141 52572e94 Ondrej Zajicek
static s32
142
get_seqnum(struct top_hash_entry *en)
143
{
144
  if (!en)
145
    return LSA_INITSEQNO;
146
147
  if (en->lsa.sn == LSA_MAXSEQNO)
148
  {
149 d395fe48 Ondrej Zajicek
    log(L_WARN "OSPF: Premature origination of LSA (Type: %04x, Id: %R, Rt: %R)",
150 52572e94 Ondrej Zajicek
        en->lsa.type, en->lsa.id, en->lsa.rt);
151
    return LSA_INITSEQNO;
152
  }
153
154 74add5df Ondrej Zajicek
  return en->lsa.sn + 1;
155 52572e94 Ondrej Zajicek
}
156
157 c3226991 Ondrej Zajicek
158 38675202 Ondrej Zajicek
static int
159
configured_stubnet(struct ospf_area *oa, struct ifa *a)
160
{
161 5cdf264f Ondrej Zajicek
  if (!oa->ac)
162
    return 0;
163
164 52a43ae3 Ondrej Zajicek
  /* Does not work for IA_PEER addresses, but it is not called on these */
165 38675202 Ondrej Zajicek
  struct ospf_stubnet_config *sn;
166
  WALK_LIST(sn, oa->ac->stubnet_list)
167
    {
168
      if (sn->summary)
169
        {
170
          if (ipa_in_net(a->prefix, sn->px.addr, sn->px.len) && (a->pxlen >= sn->px.len))
171
            return 1;
172
        }
173
      else
174
        {
175
          if (ipa_equal(a->prefix, sn->px.addr) && (a->pxlen == sn->px.len))
176
            return 1;
177
        }
178
    }
179
  return 0;
180
}
181 3d15dcdb Ondrej Zajicek
182 c3226991 Ondrej Zajicek
int
183
bcast_net_active(struct ospf_iface *ifa)
184
{
185
  struct ospf_neighbor *neigh;
186
187
  if (ifa->state == OSPF_IS_WAITING)
188
    return 0;
189
190
  WALK_LIST(neigh, ifa->neigh_list)
191
    {
192
      if (neigh->state == NEIGHBOR_FULL)
193
        {
194
          if (neigh->rid == ifa->drid)
195
            return 1;
196
197
          if (ifa->state == OSPF_IS_DR)
198
            return 1;
199
        }
200
    }
201
202
  return 0;
203
}
204
205
206
#ifdef OSPFv2
207
208 3d15dcdb Ondrej Zajicek
static void *
209 c3226991 Ondrej Zajicek
originate_rt_lsa_body(struct ospf_area *oa, u16 *length)
210 ce17d4c1 Ondrej Filip
{
211 b9ed99f7 Ondrej Filip
  struct proto_ospf *po = oa->po;
212 ce17d4c1 Ondrej Filip
  struct ospf_iface *ifa;
213 c3226991 Ondrej Zajicek
  int i = 0, bitv = 0;
214 ce17d4c1 Ondrej Filip
  struct ospf_lsa_rt *rt;
215 3d15dcdb Ondrej Zajicek
  struct ospf_lsa_rt_link *ln;
216 ce17d4c1 Ondrej Filip
  struct ospf_neighbor *neigh;
217
218 3d15dcdb Ondrej Zajicek
  ASSERT(po->lsab_used == 0);
219
  rt = lsab_allocz(po, sizeof(struct ospf_lsa_rt));
220 c3226991 Ondrej Zajicek
221 f9c799a0 Ondrej Zajicek
  rt->options = 0;
222 c3226991 Ondrej Zajicek
223 b9ed99f7 Ondrej Filip
  if (po->areano > 1)
224 c3226991 Ondrej Zajicek
    rt->options |= OPT_RT_B;
225
226 4160a9dd Ondrej Zajicek
  if ((po->areano > 1) && oa_is_nssa(oa) && oa->ac->translator)
227
    rt->options |= OPT_RT_NT;
228
229 41b612c3 Ondrej Zajicek
  if (po->ebit && !oa_is_stub(oa))
230 c3226991 Ondrej Zajicek
    rt->options |= OPT_RT_E;
231
232 3d15dcdb Ondrej Zajicek
  rt = NULL; /* buffer might be reallocated later */
233 b9ed99f7 Ondrej Filip
234
  WALK_LIST(ifa, po->iface_list)
235 ce17d4c1 Ondrej Filip
  {
236 353729f5 Ondrej Zajicek
    int net_lsa = 0;
237 f623ab98 Ondrej Zajicek
    u32 link_cost = po->stub_router ? 0xffff : ifa->cost;
238 3d15dcdb Ondrej Zajicek
239
    if ((ifa->type == OSPF_IT_VLINK) && (ifa->voa == oa) &&
240
        (!EMPTY_LIST(ifa->neigh_list)))
241 5d3f5552 Ondrej Filip
    {
242
      neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
243
      if ((neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
244 3d15dcdb Ondrej Zajicek
        bitv = 1;
245 5d3f5552 Ondrej Filip
    }
246 3b16080c Ondrej Filip
247
    if ((ifa->oa != oa) || (ifa->state == OSPF_IS_DOWN))
248 b9ed99f7 Ondrej Filip
      continue;
249 3b580a23 Ondrej Filip
250 e7b4948c Ondrej Zajicek
    ifa->rt_pos_beg = i;
251
252 919f5411 Ondrej Zajicek
    /* RFC2328 - 12.4.1.1-4 */
253 3d15dcdb Ondrej Zajicek
    switch (ifa->type)
254 ce17d4c1 Ondrej Filip
      {
255 919f5411 Ondrej Zajicek
      case OSPF_IT_PTP:
256
      case OSPF_IT_PTMP:
257
        WALK_LIST(neigh, ifa->neigh_list)
258
          if (neigh->state == NEIGHBOR_FULL)
259
          {
260
            ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link));
261
            ln->type = LSART_PTP;
262
            ln->id = neigh->rid;
263 6cadbf32 Ondrej Zajicek
264
            /*
265
             * ln->data should be ifa->iface_id in case of no/ptp
266
             * address (ifa->addr->flags & IA_PEER) on PTP link (see
267
             * RFC 2328 12.4.1.1.), but the iface ID value has no use,
268
             * while using IP address even in this case is here for
269
             * compatibility with some broken implementations that use
270
             * this address as a next-hop.
271
             */
272
            ln->data = ipa_to_u32(ifa->addr->ip);
273 f623ab98 Ondrej Zajicek
            ln->metric = link_cost;
274 919f5411 Ondrej Zajicek
            ln->padding = 0;
275
            i++;
276
          }
277 b9ed99f7 Ondrej Filip
        break;
278 3d15dcdb Ondrej Zajicek
279 919f5411 Ondrej Zajicek
      case OSPF_IT_BCAST:
280 b9ed99f7 Ondrej Filip
      case OSPF_IT_NBMA:
281 c3226991 Ondrej Zajicek
        if (bcast_net_active(ifa))
282 b9ed99f7 Ondrej Filip
          {
283 3d15dcdb Ondrej Zajicek
            ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link));
284 b9ed99f7 Ondrej Filip
            ln->type = LSART_NET;
285
            ln->id = ipa_to_u32(ifa->drip);
286 353729f5 Ondrej Zajicek
            ln->data = ipa_to_u32(ifa->addr->ip);
287 f623ab98 Ondrej Zajicek
            ln->metric = link_cost;
288 c15e5690 Ondrej Zajicek
            ln->padding = 0;
289 3d15dcdb Ondrej Zajicek
            i++;
290 353729f5 Ondrej Zajicek
            net_lsa = 1;
291 b9ed99f7 Ondrej Filip
          }
292
        break;
293 3d15dcdb Ondrej Zajicek
294 919f5411 Ondrej Zajicek
      case OSPF_IT_VLINK:
295 98ac6176 Ondrej Filip
        neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
296
        if ((!EMPTY_LIST(ifa->neigh_list)) && (neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
297
        {
298 3d15dcdb Ondrej Zajicek
          ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link));
299 98ac6176 Ondrej Filip
          ln->type = LSART_VLNK;
300
          ln->id = neigh->rid;
301 353729f5 Ondrej Zajicek
          ln->data = ipa_to_u32(ifa->addr->ip);
302 f623ab98 Ondrej Zajicek
          ln->metric = link_cost;
303 c15e5690 Ondrej Zajicek
          ln->padding = 0;
304 3d15dcdb Ondrej Zajicek
          i++;
305 12dd8dc8 Ondrej Filip
        }
306
        break;
307 3d15dcdb Ondrej Zajicek
308 12dd8dc8 Ondrej Filip
      default:
309 48e5f32d Ondrej Zajicek
        log("Unknown interface type %s", ifa->ifname);
310 98ac6176 Ondrej Filip
        break;
311 ce17d4c1 Ondrej Filip
      }
312 3d15dcdb Ondrej Zajicek
313 e7b4948c Ondrej Zajicek
    ifa->rt_pos_end = i;
314
315 0aad2b92 Ondrej Zajicek
    /* Now we will originate stub area if there is no primary */
316
    if (net_lsa ||
317
        (ifa->type == OSPF_IT_VLINK) ||
318 a55a90fa Ondrej Zajicek
        ((ifa->addr->flags & IA_PEER) && ! ifa->cf->stub) ||
319 0aad2b92 Ondrej Zajicek
        configured_stubnet(oa, ifa->addr))
320
      continue;
321 3d15dcdb Ondrej Zajicek
322 0aad2b92 Ondrej Zajicek
    ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link));
323 52a43ae3 Ondrej Zajicek
    if ((ifa->addr->flags & IA_HOST) ||
324
        (ifa->state == OSPF_IS_LOOP) ||
325
        (ifa->type == OSPF_IT_PTMP))
326 d9e7e1b1 Ondrej Zajicek
    {
327
      /* Host stub entry */
328
      ln->type = LSART_STUB;
329
      ln->id = ipa_to_u32(ifa->addr->ip);
330
      ln->data = 0xffffffff;
331
      ln->metric = 0;
332
      ln->padding = 0;
333
    }
334
    else 
335
    {
336
      /* Network stub entry */
337
      ln->type = LSART_STUB;
338
      ln->id = ipa_to_u32(ifa->addr->prefix);
339
      ln->data = ipa_to_u32(ipa_mkmask(ifa->addr->pxlen));
340
      ln->metric = ifa->cost;
341
      ln->padding = 0;
342
    }
343 0aad2b92 Ondrej Zajicek
    i++;
344 e7b4948c Ondrej Zajicek
345
    ifa->rt_pos_end = i;
346 ce17d4c1 Ondrej Filip
  }
347 3d15dcdb Ondrej Zajicek
348 38675202 Ondrej Zajicek
  struct ospf_stubnet_config *sn;
349 5cdf264f Ondrej Zajicek
  if (oa->ac)
350
    WALK_LIST(sn, oa->ac->stubnet_list)
351
      if (!sn->hidden)
352 38675202 Ondrej Zajicek
      {
353
        ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link));
354
        ln->type = LSART_STUB;
355
        ln->id = ipa_to_u32(sn->px.addr);
356
        ln->data = ipa_to_u32(ipa_mkmask(sn->px.len));
357
        ln->metric = sn->cost;
358 c15e5690 Ondrej Zajicek
        ln->padding = 0;
359 38675202 Ondrej Zajicek
        i++;
360
      }
361
362 3d15dcdb Ondrej Zajicek
  rt = po->lsab;
363 b9ed99f7 Ondrej Filip
  rt->links = i;
364 c3226991 Ondrej Zajicek
365
  if (bitv) 
366
    rt->options |= OPT_RT_V;
367
368 3d15dcdb Ondrej Zajicek
  *length = po->lsab_used + sizeof(struct ospf_lsa_header);
369
  return lsab_flush(po);
370 ce17d4c1 Ondrej Filip
}
371 c45f48fb Ondrej Filip
372 c3226991 Ondrej Zajicek
#else /* OSPFv3 */
373
374
static void
375
add_lsa_rt_link(struct proto_ospf *po, struct ospf_iface *ifa, u8 type, u32 nif, u32 id)
376
{
377
  struct ospf_lsa_rt_link *ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link));
378
  ln->type = type;
379
  ln->padding = 0;
380
  ln->metric = ifa->cost;
381 dd4da6f6 Ondrej Zajicek
  ln->lif = ifa->iface_id;
382 c3226991 Ondrej Zajicek
  ln->nif = nif;
383
  ln->id = id;
384
}
385
386
static void *
387
originate_rt_lsa_body(struct ospf_area *oa, u16 *length)
388
{
389
  struct proto_ospf *po = oa->po;
390
  struct ospf_iface *ifa;
391 b49e6f5a Ondrej Zajicek
  int bitv = 0;
392 e7b4948c Ondrej Zajicek
  int i = 0;
393 c3226991 Ondrej Zajicek
  struct ospf_lsa_rt *rt;
394
  struct ospf_neighbor *neigh;
395
396
  ASSERT(po->lsab_used == 0);
397
  rt = lsab_allocz(po, sizeof(struct ospf_lsa_rt));
398
399
  rt->options = oa->options & OPTIONS_MASK;
400
401
  if (po->areano > 1)
402
    rt->options |= OPT_RT_B;
403
404 4160a9dd Ondrej Zajicek
  if ((po->areano > 1) && oa_is_nssa(oa) && oa->ac->translator)
405
    rt->options |= OPT_RT_NT;
406
407 41b612c3 Ondrej Zajicek
  if (po->ebit && !oa_is_stub(oa))
408 c3226991 Ondrej Zajicek
    rt->options |= OPT_RT_E;
409
410
  rt = NULL; /* buffer might be reallocated later */
411
412
  WALK_LIST(ifa, po->iface_list)
413
  {
414
    if ((ifa->type == OSPF_IT_VLINK) && (ifa->voa == oa) &&
415
        (!EMPTY_LIST(ifa->neigh_list)))
416
    {
417
      neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
418
      if ((neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
419
        bitv = 1;
420
    }
421
422
    if ((ifa->oa != oa) || (ifa->state == OSPF_IS_DOWN))
423
      continue;
424
425 e7b4948c Ondrej Zajicek
    ifa->rt_pos_beg = i;
426
427 c3226991 Ondrej Zajicek
    /* RFC5340 - 4.4.3.2 */
428
    switch (ifa->type)
429
      {
430
      case OSPF_IT_PTP:
431 919f5411 Ondrej Zajicek
      case OSPF_IT_PTMP:
432
        WALK_LIST(neigh, ifa->neigh_list)
433
          if (neigh->state == NEIGHBOR_FULL)
434 e7b4948c Ondrej Zajicek
            add_lsa_rt_link(po, ifa, LSART_PTP, neigh->iface_id, neigh->rid), i++;
435 c3226991 Ondrej Zajicek
        break;
436
437
      case OSPF_IT_BCAST:
438
      case OSPF_IT_NBMA:
439
        if (bcast_net_active(ifa))
440 e7b4948c Ondrej Zajicek
          add_lsa_rt_link(po, ifa, LSART_NET, ifa->dr_iface_id, ifa->drid), i++;
441 c3226991 Ondrej Zajicek
        break;
442
443
      case OSPF_IT_VLINK:
444
        neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
445
        if ((!EMPTY_LIST(ifa->neigh_list)) && (neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
446 e7b4948c Ondrej Zajicek
          add_lsa_rt_link(po, ifa, LSART_VLNK, neigh->iface_id, neigh->rid), i++;
447 c3226991 Ondrej Zajicek
        break;
448
449
      default:
450 48e5f32d Ondrej Zajicek
        log("Unknown interface type %s", ifa->ifname);
451 c3226991 Ondrej Zajicek
        break;
452
      }
453 e7b4948c Ondrej Zajicek
454
    ifa->rt_pos_end = i;
455 c3226991 Ondrej Zajicek
  }
456
457
  if (bitv)
458
    {
459
      rt = po->lsab;
460
      rt->options |= OPT_RT_V;
461
    }
462
463
  *length = po->lsab_used + sizeof(struct ospf_lsa_header);
464
  return lsab_flush(po);
465
}
466
467
#endif
468
469 7ab3ff6a Ondrej Filip
/**
470
 * originate_rt_lsa - build new instance of router LSA
471
 * @oa: ospf_area which is LSA built to
472
 *
473
 * It builds router LSA walking through all OSPF interfaces in
474
 * specified OSPF area. This function is mostly called from
475
 * area_disp(). Builds new LSA, increases sequence number (if old
476
 * instance exists) and sets age of LSA to zero.
477
 */
478 9bc1808a Ondrej Filip
void
479 70a38319 Ondrej Filip
originate_rt_lsa(struct ospf_area *oa)
480 d8852b36 Ondrej Filip
{
481
  struct ospf_lsa_header lsa;
482 b9ed99f7 Ondrej Filip
  struct proto_ospf *po = oa->po;
483
  struct proto *p = &po->proto;
484 d8852b36 Ondrej Filip
  void *body;
485
486 be862406 Ondrej Zajicek
  OSPF_TRACE(D_EVENTS, "Originating router-LSA for area %R", oa->areaid);
487 b9ed99f7 Ondrej Filip
488
  lsa.age = 0;
489
  lsa.type = LSA_T_RT;
490 c3226991 Ondrej Zajicek
  
491
#ifdef OSPFv2
492
  lsa.options = oa->options;
493 8a70a13e Ondrej Zajicek
  lsa.id = po->router_id;
494 cf31112f Ondrej Zajicek
#else /* OSPFv3 */
495
  lsa.id = 0;
496
#endif
497
498 8a70a13e Ondrej Zajicek
  lsa.rt = po->router_id;
499 52572e94 Ondrej Zajicek
  lsa.sn = get_seqnum(oa->rt);
500 c3226991 Ondrej Zajicek
  u32 dom = oa->areaid;
501
502 b9ed99f7 Ondrej Filip
  body = originate_rt_lsa_body(oa, &lsa.length);
503 d5d9693c Ondrej Filip
  lsasum_calculate(&lsa, body);
504 b49e6f5a Ondrej Zajicek
  oa->rt = lsa_install_new(po, &lsa, dom, body);
505
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
506
}
507
508
void
509
update_rt_lsa(struct ospf_area *oa)
510
{
511
  struct proto_ospf *po = oa->po;
512
513
  if ((oa->rt) && ((oa->rt->inst_t + MINLSINTERVAL)) > now)
514
    return;
515
  /*
516
   * Tick is probably set to very low value. We cannot
517
   * originate new LSA before MINLSINTERVAL. We will
518
   * try to do it next tick.
519
   */
520
521
  originate_rt_lsa(oa);
522 f9c799a0 Ondrej Zajicek
#ifdef OSPFv3
523 b49e6f5a Ondrej Zajicek
  originate_prefix_rt_lsa(oa);
524 f9c799a0 Ondrej Zajicek
#endif
525 b49e6f5a Ondrej Zajicek
526 b8f17cf1 Ondrej Filip
  schedule_rtcalc(po);
527 b9ed99f7 Ondrej Filip
  oa->origrt = 0;
528 ab56f6b1 Ondrej Filip
}
529
530 9831e591 Martin Mares
static void *
531 c3226991 Ondrej Zajicek
originate_net_lsa_body(struct ospf_iface *ifa, u16 *length,
532 b9ed99f7 Ondrej Filip
                       struct proto_ospf *po)
533 0bf2f203 Ondrej Filip
{
534 b9ed99f7 Ondrej Filip
  u16 i = 1;
535 0bf2f203 Ondrej Filip
  struct ospf_neighbor *n;
536 d345cda5 Ondrej Filip
  struct ospf_lsa_net *net;
537 c3226991 Ondrej Zajicek
  int nodes = ifa->fadj + 1;
538
539
  net = mb_alloc(po->proto.pool, sizeof(struct ospf_lsa_net)
540
                 + nodes * sizeof(u32));
541 0bf2f203 Ondrej Filip
542 c3226991 Ondrej Zajicek
#ifdef OSPFv2
543 353729f5 Ondrej Zajicek
  net->netmask = ipa_mkmask(ifa->addr->pxlen);
544 c3226991 Ondrej Zajicek
#endif
545
546
#ifdef OSPFv3
547
  /* In OSPFv3, we would like to merge options from Link LSAs of added neighbors */
548
  struct top_hash_entry *en;
549
  u32 options = 0;
550
#endif
551
552 8a70a13e Ondrej Zajicek
  net->routers[0] = po->router_id;
553 d345cda5 Ondrej Filip
554 b9ed99f7 Ondrej Filip
  WALK_LIST(n, ifa->neigh_list)
555 0bf2f203 Ondrej Filip
  {
556 b9ed99f7 Ondrej Filip
    if (n->state == NEIGHBOR_FULL)
557 0bf2f203 Ondrej Filip
    {
558 c3226991 Ondrej Zajicek
#ifdef OSPFv3
559 dd4da6f6 Ondrej Zajicek
      en = ospf_hash_find(po->gr, ifa->iface_id, n->iface_id, n->rid, LSA_T_LINK);
560 c3226991 Ondrej Zajicek
      if (en)
561
        options |= ((struct ospf_lsa_link *) en->lsa_body)->options;
562
#endif
563
564
      net->routers[i] = n->rid;
565 0bf2f203 Ondrej Filip
      i++;
566
    }
567
  }
568 c3226991 Ondrej Zajicek
  ASSERT(i == nodes);
569
570
#ifdef OSPFv3
571
  net->options = options & OPTIONS_MASK;
572
#endif
573
  
574
  *length = sizeof(struct ospf_lsa_header) + sizeof(struct ospf_lsa_net)
575
    + nodes * sizeof(u32);
576 d345cda5 Ondrej Filip
  return net;
577 0bf2f203 Ondrej Filip
}
578
579 b49e6f5a Ondrej Zajicek
580 7ab3ff6a Ondrej Filip
/**
581
 * originate_net_lsa - originates of deletes network LSA
582
 * @ifa: interface which is LSA originated for
583
 *
584 baa5dd6c Ondrej Filip
 * Interface counts number of adjacent neighbors. If this number is
585
 * lower than one or interface is not in state %OSPF_IS_DR it deletes
586 7ab3ff6a Ondrej Filip
 * and premature ages instance of network LSA for specified interface.
587
 * In other case, new instance of network LSA is originated.
588
 */
589 9bc1808a Ondrej Filip
void
590 7ab3ff6a Ondrej Filip
originate_net_lsa(struct ospf_iface *ifa)
591 0bf2f203 Ondrej Filip
{
592 86c84d76 Ondrej Filip
  struct proto_ospf *po = ifa->oa->po;
593 8a70a13e Ondrej Zajicek
  struct proto *p = &po->proto;
594 0bf2f203 Ondrej Filip
  struct ospf_lsa_header lsa;
595 c3226991 Ondrej Zajicek
  u32 dom = ifa->oa->areaid;
596 8a70a13e Ondrej Zajicek
  
597 0bf2f203 Ondrej Filip
  void *body;
598
599 48e5f32d Ondrej Zajicek
  OSPF_TRACE(D_EVENTS, "Originating network-LSA for iface %s", ifa->ifname);
600 b9ed99f7 Ondrej Filip
601
  lsa.age = 0;
602
  lsa.type = LSA_T_NET;
603 c3226991 Ondrej Zajicek
604
#ifdef OSPFv2
605
  lsa.options = ifa->oa->options;
606 353729f5 Ondrej Zajicek
  lsa.id = ipa_to_u32(ifa->addr->ip);
607 c3226991 Ondrej Zajicek
#else /* OSPFv3 */
608 dd4da6f6 Ondrej Zajicek
  lsa.id = ifa->iface_id;
609 c3226991 Ondrej Zajicek
#endif
610
611 8a70a13e Ondrej Zajicek
  lsa.rt = po->router_id;
612 52572e94 Ondrej Zajicek
  lsa.sn = get_seqnum(ifa->net_lsa);
613 3dd8f983 Ondrej Filip
614 b9ed99f7 Ondrej Filip
  body = originate_net_lsa_body(ifa, &lsa.length, po);
615 d5d9693c Ondrej Filip
  lsasum_calculate(&lsa, body);
616 c3226991 Ondrej Zajicek
  ifa->net_lsa = lsa_install_new(po, &lsa, dom, body);
617
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
618 0bf2f203 Ondrej Filip
}
619
620 b49e6f5a Ondrej Zajicek
void
621
flush_net_lsa(struct ospf_iface *ifa)
622
{
623
  struct proto_ospf *po = ifa->oa->po;
624
  struct proto *p = &po->proto;
625
  u32 dom = ifa->oa->areaid;
626
627
  if (ifa->net_lsa == NULL)
628
    return;
629
630 48e5f32d Ondrej Zajicek
  OSPF_TRACE(D_EVENTS, "Flushing network-LSA for iface %s", ifa->ifname);
631 b49e6f5a Ondrej Zajicek
  ifa->net_lsa->lsa.sn += 1;
632
  ifa->net_lsa->lsa.age = LSA_MAXAGE;
633
  lsasum_calculate(&ifa->net_lsa->lsa, ifa->net_lsa->lsa_body);
634
  ospf_lsupd_flood(po, NULL, NULL, &ifa->net_lsa->lsa, dom, 0);
635
  flush_lsa(ifa->net_lsa, po);
636
  ifa->net_lsa = NULL;
637
}
638
639
void
640
update_net_lsa(struct ospf_iface *ifa)
641
{
642
  struct proto_ospf *po = ifa->oa->po;
643
 
644
  if (ifa->net_lsa && ((ifa->net_lsa->inst_t + MINLSINTERVAL) > now))
645
    return;
646
  /*
647
   * It's too early to originate new network LSA. We will
648
   * try to do it next tick
649
   */
650
651
  if ((ifa->state != OSPF_IS_DR) || (ifa->fadj == 0))
652
    {
653
      flush_net_lsa(ifa);
654 f9c799a0 Ondrej Zajicek
#ifdef OSPFv3
655 b49e6f5a Ondrej Zajicek
      flush_prefix_net_lsa(ifa);
656 f9c799a0 Ondrej Zajicek
#endif
657 b49e6f5a Ondrej Zajicek
    }
658
  else
659
    {
660
      originate_net_lsa(ifa);
661 f9c799a0 Ondrej Zajicek
#ifdef OSPFv3
662 b49e6f5a Ondrej Zajicek
      originate_prefix_net_lsa(ifa);
663 f9c799a0 Ondrej Zajicek
#endif
664 b49e6f5a Ondrej Zajicek
    }
665
666
  schedule_rtcalc(po);
667
  ifa->orignet = 0;
668
}
669 98ac6176 Ondrej Filip
670 c3226991 Ondrej Zajicek
#ifdef OSPFv2
671
672 9727681a Ondrej Zajicek
static inline void *
673 c3226991 Ondrej Zajicek
originate_sum_lsa_body(struct proto_ospf *po, u16 *length, u32 mlen, u32 metric)
674 e8085aba Ondrej Filip
{
675 c3226991 Ondrej Zajicek
  struct ospf_lsa_sum *sum = mb_alloc(po->proto.pool, sizeof(struct ospf_lsa_sum));
676
  *length = sizeof(struct ospf_lsa_header) + sizeof(struct ospf_lsa_sum);
677 e8085aba Ondrej Filip
678 c3226991 Ondrej Zajicek
  sum->netmask = ipa_mkmask(mlen);
679
  sum->metric = metric;
680 e8085aba Ondrej Filip
681 c3226991 Ondrej Zajicek
  return sum;
682
}
683 5919c66e Martin Mares
684 c3226991 Ondrej Zajicek
#define originate_sum_net_lsa_body(po,length,fn,metric) \
685
  originate_sum_lsa_body(po, length, (fn)->pxlen, metric)
686 b9ed99f7 Ondrej Filip
687 c3226991 Ondrej Zajicek
#define originate_sum_rt_lsa_body(po,length,drid,metric,options) \
688
  originate_sum_lsa_body(po, length, 0, metric)
689 e8085aba Ondrej Filip
690 9727681a Ondrej Zajicek
static inline int
691
check_sum_net_lsaid_collision(struct fib_node *fn, struct top_hash_entry *en)
692
{
693
  struct ospf_lsa_sum *sum = en->lsa_body;
694 98955023 Ondrej Zajicek
  return fn->pxlen != ipa_mklen(sum->netmask);
695 9727681a Ondrej Zajicek
}
696
697
static inline int
698 7ff5803b Ondrej Zajicek
check_sum_lsa_same(struct top_hash_entry *en, u32 metric)
699 9727681a Ondrej Zajicek
{
700 7ff5803b Ondrej Zajicek
  /* Netmask already checked in check_sum_net_lsaid_collision() */
701
  struct ospf_lsa_sum *sum = en->lsa_body;
702 d395fe48 Ondrej Zajicek
  return (en->lsa.sn != LSA_MAXSEQNO) && (sum->metric == metric);
703 9727681a Ondrej Zajicek
}
704
705 7ff5803b Ondrej Zajicek
#define check_sum_net_lsa_same(en,metric) \
706
  check_sum_lsa_same(en, metric)
707
708
#define check_sum_rt_lsa_same(en,drid,metric,options) \
709
  check_sum_lsa_same(en, metric)
710
711
712 c3226991 Ondrej Zajicek
#else /* OSPFv3 */
713 0077aab4 Martin Mares
714 9727681a Ondrej Zajicek
static inline void *
715 c3226991 Ondrej Zajicek
originate_sum_net_lsa_body(struct proto_ospf *po, u16 *length, struct fib_node *fn, u32 metric)
716 0077aab4 Martin Mares
{
717 c3226991 Ondrej Zajicek
  int size = sizeof(struct ospf_lsa_sum_net) + IPV6_PREFIX_SPACE(fn->pxlen);
718
  struct ospf_lsa_sum_net *sum = mb_alloc(po->proto.pool, size);
719
  *length = sizeof(struct ospf_lsa_header) + size;
720
721
  sum->metric = metric;
722
  put_ipv6_prefix(sum->prefix, fn->prefix, fn->pxlen, 0, 0);
723
724
  return sum;
725
}
726
727 9727681a Ondrej Zajicek
static inline int
728
check_sum_net_lsaid_collision(struct fib_node *fn, struct top_hash_entry *en)
729
{
730
  struct ospf_lsa_sum_net *sum = en->lsa_body;
731
  ip_addr prefix;
732
  int pxlen;
733
  u8 pxopts;
734
  u16 rest;
735
736
  lsa_get_ipv6_prefix(sum->prefix, &prefix, &pxlen, &pxopts, &rest);
737
  return (fn->pxlen != pxlen) || !ipa_equal(fn->prefix, prefix);
738
}
739
740
static inline int
741 7ff5803b Ondrej Zajicek
check_sum_net_lsa_same(struct top_hash_entry *en, u32 metric)
742 9727681a Ondrej Zajicek
{
743 7ff5803b Ondrej Zajicek
  /* Prefix already checked in check_sum_net_lsaid_collision() */
744
  struct ospf_lsa_sum_net *sum = en->lsa_body;
745 d395fe48 Ondrej Zajicek
  return (en->lsa.sn != LSA_MAXSEQNO) && (sum->metric == metric);
746 9727681a Ondrej Zajicek
}
747
748
static inline void *
749 c3226991 Ondrej Zajicek
originate_sum_rt_lsa_body(struct proto_ospf *po, u16 *length, u32 drid, u32 metric, u32 options)
750
{
751
  struct ospf_lsa_sum_rt *sum = mb_alloc(po->proto.pool, sizeof(struct ospf_lsa_sum_rt));
752
  *length = sizeof(struct ospf_lsa_header) + sizeof(struct ospf_lsa_sum_rt);
753
754 7ff5803b Ondrej Zajicek
  sum->options = options;
755 c3226991 Ondrej Zajicek
  sum->metric = metric;
756
  sum->drid = drid;
757
758
  return sum;
759 0077aab4 Martin Mares
}
760
761 7ff5803b Ondrej Zajicek
static inline int
762
check_sum_rt_lsa_same(struct top_hash_entry *en, u32 drid, u32 metric, u32 options)
763
{
764
  struct ospf_lsa_sum_rt *sum = en->lsa_body;
765 d395fe48 Ondrej Zajicek
  return (en->lsa.sn != LSA_MAXSEQNO) && (sum->options == options) &&
766
    (sum->metric == metric) && (sum->drid == drid);
767 7ff5803b Ondrej Zajicek
}
768
769 c3226991 Ondrej Zajicek
#endif
770
771 98ac6176 Ondrej Filip
void
772 9727681a Ondrej Zajicek
originate_sum_net_lsa(struct ospf_area *oa, struct fib_node *fn, int metric)
773 98ac6176 Ondrej Filip
{
774
  struct proto_ospf *po = oa->po;
775
  struct proto *p = &po->proto;
776
  struct top_hash_entry *en;
777 9727681a Ondrej Zajicek
  u32 dom = oa->areaid;
778 98ac6176 Ondrej Filip
  struct ospf_lsa_header lsa;
779 c3226991 Ondrej Zajicek
  void *body;
780 98ac6176 Ondrej Filip
781 9727681a Ondrej Zajicek
  OSPF_TRACE(D_EVENTS, "Originating net-summary-LSA for %I/%d (metric %d)",
782
             fn->prefix, fn->pxlen, metric);
783 c3226991 Ondrej Zajicek
784 9727681a Ondrej Zajicek
  /* options argument is used in ORT_NET and OSPFv3 only */
785 c3226991 Ondrej Zajicek
  lsa.age = 0;
786
#ifdef OSPFv2
787
  lsa.options = oa->options;
788
#endif
789 9727681a Ondrej Zajicek
  lsa.type = LSA_T_SUM_NET;
790
  lsa.id = fibnode_to_lsaid(po, fn);
791 8a70a13e Ondrej Zajicek
  lsa.rt = po->router_id;
792 98ac6176 Ondrej Filip
793 9727681a Ondrej Zajicek
  if ((en = ospf_hash_find_header(po->gr, dom, &lsa)) != NULL)
794
  {
795
    if (check_sum_net_lsaid_collision(fn, en))
796 7ff5803b Ondrej Zajicek
    {
797 35c875f0 Ondrej Zajicek
      log(L_ERR "%s: LSAID collision for %I/%d",
798 7ff5803b Ondrej Zajicek
          p->name, fn->prefix, fn->pxlen);
799
      return;
800
    }
801
802
    if (check_sum_net_lsa_same(en, metric))
803
      return;
804 9727681a Ondrej Zajicek
  }
805 52572e94 Ondrej Zajicek
  lsa.sn = get_seqnum(en);
806 c3226991 Ondrej Zajicek
807 9727681a Ondrej Zajicek
  body = originate_sum_net_lsa_body(po, &lsa.length, fn, metric);
808
  lsasum_calculate(&lsa, body);
809 d494df63 Ondrej Zajicek
  lsa_install_new(po, &lsa, dom, body);
810 9727681a Ondrej Zajicek
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
811
}
812 c3226991 Ondrej Zajicek
813 9727681a Ondrej Zajicek
void
814 e81b440f Ondrej Zajicek
originate_sum_rt_lsa(struct ospf_area *oa, struct fib_node *fn, int metric, u32 options UNUSED)
815 9727681a Ondrej Zajicek
{
816
  struct proto_ospf *po = oa->po;
817
  struct proto *p = &po->proto;
818
  struct top_hash_entry *en;
819 353729f5 Ondrej Zajicek
  u32 dom = oa->areaid;
820
  u32 rid = ipa_to_rid(fn->prefix);
821 9727681a Ondrej Zajicek
  struct ospf_lsa_header lsa;
822
  void *body;
823 c3226991 Ondrej Zajicek
824 9727681a Ondrej Zajicek
  OSPF_TRACE(D_EVENTS, "Originating rt-summary-LSA for %R (metric %d)",
825 353729f5 Ondrej Zajicek
             rid, metric);
826 9727681a Ondrej Zajicek
827
  lsa.age = 0;
828
#ifdef OSPFv2
829
  lsa.options = oa->options;
830
#endif
831
  lsa.type = LSA_T_SUM_RT;
832
  /* In OSPFv3, LSA ID is meaningless, but we still use Router ID of ASBR */
833 353729f5 Ondrej Zajicek
  lsa.id = rid;
834 8a70a13e Ondrej Zajicek
  lsa.rt = po->router_id;
835 9727681a Ondrej Zajicek
836 7ff5803b Ondrej Zajicek
  options &= OPTIONS_MASK;
837 9727681a Ondrej Zajicek
  if ((en = ospf_hash_find_header(po->gr, dom, &lsa)) != NULL)
838 7ff5803b Ondrej Zajicek
  {
839
    if (check_sum_rt_lsa_same(en, lsa.id, metric, options))
840
      return;
841
  }
842 52572e94 Ondrej Zajicek
  lsa.sn = get_seqnum(en);
843 c3226991 Ondrej Zajicek
844 9727681a Ondrej Zajicek
  body = originate_sum_rt_lsa_body(po, &lsa.length, lsa.id, metric, options);
845 c3226991 Ondrej Zajicek
  lsasum_calculate(&lsa, body);
846 d494df63 Ondrej Zajicek
  lsa_install_new(po, &lsa, dom, body);
847 c3226991 Ondrej Zajicek
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
848 98ac6176 Ondrej Filip
}
849
850 9727681a Ondrej Zajicek
void
851 c3226991 Ondrej Zajicek
flush_sum_lsa(struct ospf_area *oa, struct fib_node *fn, int type)
852 98ac6176 Ondrej Filip
{
853
  struct proto_ospf *po = oa->po;
854
  struct proto *p = &po->proto;
855
  struct top_hash_entry *en;
856
  struct ospf_lsa_header lsa;
857
858 8a70a13e Ondrej Zajicek
  lsa.rt = po->router_id;
859 c3226991 Ondrej Zajicek
  if (type == ORT_NET)
860 98ac6176 Ondrej Filip
    {
861 d82fc18d Ondrej Zajicek
      lsa.id = fibnode_to_lsaid(po, fn);
862 c3226991 Ondrej Zajicek
      lsa.type = LSA_T_SUM_NET;
863 98ac6176 Ondrej Filip
    }
864 c3226991 Ondrej Zajicek
  else
865 98ac6176 Ondrej Filip
    {
866 9727681a Ondrej Zajicek
      /* In OSPFv3, LSA ID is meaningless, but we still use Router ID of ASBR */
867 c3226991 Ondrej Zajicek
      lsa.id = ipa_to_rid(fn->prefix);
868
      lsa.type = LSA_T_SUM_RT;
869 98ac6176 Ondrej Filip
    }
870
871 b49e6f5a Ondrej Zajicek
  if ((en = ospf_hash_find_header(po->gr, oa->areaid, &lsa)) != NULL)
872 c3226991 Ondrej Zajicek
    {
873 bbcfd5a0 Ondrej Zajicek
      OSPF_TRACE(D_EVENTS, "Flushing summary-LSA (id=%R, type=%d)",
874
                 en->lsa.id, en->lsa.type);
875
876 9727681a Ondrej Zajicek
      if ((type == ORT_NET) && check_sum_net_lsaid_collision(fn, en))
877
        {
878 35c875f0 Ondrej Zajicek
          log(L_ERR "%s: LSAID collision for %I/%d",
879 9727681a Ondrej Zajicek
              p->name, fn->prefix, fn->pxlen);
880
          return;
881
        }
882
883 c3226991 Ondrej Zajicek
      struct ospf_lsa_sum *sum = en->lsa_body;
884
      en->lsa.age = LSA_MAXAGE;
885
      en->lsa.sn = LSA_MAXSEQNO;
886
      lsasum_calculate(&en->lsa, sum);
887
      ospf_lsupd_flood(po, NULL, NULL, &en->lsa, oa->areaid, 1);
888
      if (can_flush_lsa(po)) flush_lsa(en, po);
889
    }
890 98ac6176 Ondrej Filip
}
891
892 7ff5803b Ondrej Zajicek
#ifdef OSPFv2
893 c3226991 Ondrej Zajicek
894 7ff5803b Ondrej Zajicek
static inline void *
895 ed317862 Ondrej Zajicek
originate_ext_lsa_body(struct proto_ospf *po, u16 *length, struct fib_node *fn,
896 2918e610 Ondrej Zajicek
                       u32 metric, ip_addr fwaddr, u32 tag, int pbit UNUSED)
897 c3226991 Ondrej Zajicek
{
898 7ff5803b Ondrej Zajicek
  struct ospf_lsa_ext *ext = mb_alloc(po->proto.pool, sizeof(struct ospf_lsa_ext));
899
  *length = sizeof(struct ospf_lsa_header) + sizeof(struct ospf_lsa_ext);
900 c3226991 Ondrej Zajicek
901 7ff5803b Ondrej Zajicek
  ext->metric = metric; 
902 ed317862 Ondrej Zajicek
  ext->netmask = ipa_mkmask(fn->pxlen);
903 7ff5803b Ondrej Zajicek
  ext->fwaddr = fwaddr;
904
  ext->tag = tag;
905 c3226991 Ondrej Zajicek
906 7ff5803b Ondrej Zajicek
  return ext;
907
}
908 c3226991 Ondrej Zajicek
909 7ff5803b Ondrej Zajicek
/*
910
 * check_ext_lsa() combines functions of check_*_lsaid_collision() and
911
 * check_*_lsa_same(). 'en' is existing ext LSA, and rest parameters
912
 * are parameters of new ext route.  Function returns -1 if there is
913
 * LSAID collision, returns 1 if the existing LSA is the same and
914
 * returns 0 otherwise (in that case, we need to originate a new LSA).
915
 *
916
 * Really, checking for the same parameters is not as important as in
917
 * summary LSA origination, because in most cases the duplicate
918
 * external route propagation would be stopped by the nest. But there
919
 * are still some cases (route reload, the same route propagated through
920
 * different protocol) so it is also done here.
921
 */
922 c3226991 Ondrej Zajicek
923 7ff5803b Ondrej Zajicek
static inline int
924
check_ext_lsa(struct top_hash_entry *en, struct fib_node *fn, u32 metric, ip_addr fwaddr, u32 tag)
925
{
926
  struct ospf_lsa_ext *ext = en->lsa_body;
927
928
  /* LSAID collision */
929
  if  (fn->pxlen != ipa_mklen(ext->netmask))
930
    return -1;
931
932 d395fe48 Ondrej Zajicek
  return (en->lsa.sn != LSA_MAXSEQNO) && (ext->metric == metric) &&
933
    (ext->tag == tag) && ipa_equal(ext->fwaddr,fwaddr);
934 7ff5803b Ondrej Zajicek
}
935 c3226991 Ondrej Zajicek
936
#else /* OSPFv3 */
937 7ff5803b Ondrej Zajicek
938
static inline void *
939 ed317862 Ondrej Zajicek
originate_ext_lsa_body(struct proto_ospf *po, u16 *length, struct fib_node *fn,
940 2918e610 Ondrej Zajicek
                       u32 metric, ip_addr fwaddr, u32 tag, int pbit)
941 7ff5803b Ondrej Zajicek
{
942
  int size = sizeof(struct ospf_lsa_ext)
943 2918e610 Ondrej Zajicek
    + IPV6_PREFIX_SPACE(fn->pxlen)
944 7ff5803b Ondrej Zajicek
    + (ipa_nonzero(fwaddr) ? 16 : 0)
945
    + (tag ? 4 : 0);
946
947
  struct ospf_lsa_ext *ext = mb_alloc(po->proto.pool, size);
948
  *length = sizeof(struct ospf_lsa_header) + size;
949
950
  ext->metric = metric;
951
952 e81b440f Ondrej Zajicek
  u32 *buf = ext->rest;
953 2918e610 Ondrej Zajicek
  buf = put_ipv6_prefix(buf, fn->prefix, fn->pxlen, pbit ? OPT_PX_P : 0, 0);
954 c3226991 Ondrej Zajicek
955 7ff5803b Ondrej Zajicek
  if (ipa_nonzero(fwaddr))
956
  {
957
    ext->metric |= LSA_EXT_FBIT;
958
    buf = put_ipv6_addr(buf, fwaddr);
959
  }
960 c3226991 Ondrej Zajicek
961
  if (tag)
962 7ff5803b Ondrej Zajicek
  {
963
    ext->metric |= LSA_EXT_TBIT;
964
    *buf++ = tag;
965
  }
966 c3226991 Ondrej Zajicek
967
  return ext;
968
}
969
970 7ff5803b Ondrej Zajicek
static inline int
971
check_ext_lsa(struct top_hash_entry *en, struct fib_node *fn, u32 metric, ip_addr fwaddr, u32 tag)
972
{
973
  struct ospf_lsa_ext *ext = en->lsa_body;
974
  ip_addr prefix;
975
  int pxlen;
976
  u8 pxopts;
977
  u16 rest;
978
979
  u32 *buf = lsa_get_ipv6_prefix(ext->rest, &prefix, &pxlen, &pxopts, &rest);
980
981
  /* LSAID collision */
982
  if ((fn->pxlen != pxlen) || !ipa_equal(fn->prefix, prefix))
983
    return -1;
984
985 d395fe48 Ondrej Zajicek
  if (en->lsa.sn == LSA_MAXSEQNO)
986
    return 0;
987
988 7ff5803b Ondrej Zajicek
  u32 rt_metric = ext->metric & METRIC_MASK;
989
  ip_addr rt_fwaddr = IPA_NONE;
990
  u32 rt_tag = 0;
991
992
  if (ext->metric & LSA_EXT_FBIT)
993
    buf = lsa_get_ipv6_addr(buf, &rt_fwaddr);
994
995
  if (ext->metric & LSA_EXT_TBIT)
996
    rt_tag = *buf++;
997
998
  return (rt_metric == metric) && ipa_equal(rt_fwaddr, fwaddr) && (rt_tag == tag);
999
}
1000
1001
1002
#endif
1003
1004 2918e610 Ondrej Zajicek
static inline ip_addr
1005
find_surrogate_fwaddr(struct ospf_area *oa)
1006
{
1007
  struct proto_ospf *po = oa->po;
1008
  struct ospf_iface *ifa;
1009
  struct ifa *a, *cur_addr = NULL;
1010
  int np, cur_np = 0;
1011
1012
  WALK_LIST(ifa, po->iface_list)
1013
  {
1014
    if ((ifa->oa != oa) ||
1015
        (ifa->type == OSPF_IT_VLINK))
1016
      continue;
1017
1018
#ifdef OSPFv2
1019
    a = ifa->addr;
1020
    if (a->flags & IA_PEER)
1021
      continue;
1022
1023
    np = ((a->flags & IA_HOST) || ifa->stub) ? 2 : 1;
1024
    if (np > cur_np)
1025
    {
1026
      cur_addr = a;
1027
      cur_np = np;
1028
    }
1029
1030
#else /* OSPFv3 */
1031
    WALK_LIST(a, ifa->iface->addrs)
1032
    {
1033
      if ((a->flags & IA_SECONDARY) ||
1034
          (a->flags & IA_PEER) ||
1035
          (a->scope <= SCOPE_LINK))
1036
        continue;
1037
1038
      np = ((a->flags & IA_HOST) || ifa->stub) ? 2 : 1;
1039
      if (np > cur_np)
1040
      {
1041
        cur_addr = a;
1042
        cur_np = np;
1043
      }
1044
    }
1045
#endif
1046
  }
1047
1048
  return cur_addr ? cur_addr->ip : IPA_NONE;
1049
}
1050
1051
1052 0077aab4 Martin Mares
/**
1053 baa5dd6c Ondrej Filip
 * originate_ext_lsa - new route received from nest and filters
1054 41b612c3 Ondrej Zajicek
 * @oa: ospf_area for which LSA is originated
1055 ed317862 Ondrej Zajicek
 * @fn: network prefix and mask
1056 2918e610 Ondrej Zajicek
 * @src: the source of origination of the LSA (EXT_EXPORT/EXT_NSSA)
1057 ed317862 Ondrej Zajicek
 * @metric: the metric of a route
1058
 * @fwaddr: the forwarding address
1059
 * @tag: the route tag
1060 2918e610 Ondrej Zajicek
 * @pbit: P-bit for NSSA LSAs, ignored for external LSAs
1061 7ab3ff6a Ondrej Filip
 *
1062 baa5dd6c Ondrej Filip
 * If I receive a message that new route is installed, I try to originate an
1063 41b612c3 Ondrej Zajicek
 * external LSA. If @oa is an NSSA area, NSSA-LSA is originated instead.
1064 2918e610 Ondrej Zajicek
 * @oa should not be a stub area. @src does not specify whether the LSA
1065
 * is external or NSSA, but it specifies the source of origination - 
1066
 * the export from ospf_rt_notify(), or the NSSA-EXT translation.
1067 fdb19982 Ondrej Filip
 *
1068 baa5dd6c Ondrej Filip
 * The function also sets flag ebit. If it's the first time, the new router lsa
1069 fdb19982 Ondrej Filip
 * origination is necessary.
1070 7ab3ff6a Ondrej Filip
 */
1071 e8085aba Ondrej Filip
void
1072 2918e610 Ondrej Zajicek
originate_ext_lsa(struct ospf_area *oa, struct fib_node *fn, int src,
1073
                  u32 metric, ip_addr fwaddr, u32 tag, int pbit)
1074 e8085aba Ondrej Filip
{
1075 41b612c3 Ondrej Zajicek
  struct proto_ospf *po = oa->po;
1076 be862406 Ondrej Zajicek
  struct proto *p = &po->proto;
1077 e8085aba Ondrej Filip
  struct ospf_lsa_header lsa;
1078 b9ed99f7 Ondrej Filip
  struct top_hash_entry *en = NULL;
1079 c3226991 Ondrej Zajicek
  void *body;
1080 41b612c3 Ondrej Zajicek
  int nssa = oa_is_nssa(oa);
1081
  u32 dom = nssa ? oa->areaid : 0;
1082
1083
  OSPF_TRACE(D_EVENTS, "Originating %s-LSA for %I/%d",
1084
             nssa ? "NSSA" : "AS-external", fn->prefix, fn->pxlen);
1085 b9ed99f7 Ondrej Filip
1086
  lsa.age = 0;
1087 c3226991 Ondrej Zajicek
#ifdef OSPFv2
1088 2918e610 Ondrej Zajicek
  lsa.options = nssa ? (pbit ? OPT_P : 0) : OPT_E;
1089 c3226991 Ondrej Zajicek
#endif
1090 41b612c3 Ondrej Zajicek
  lsa.type = nssa ? LSA_T_NSSA : LSA_T_EXT;
1091 9727681a Ondrej Zajicek
  lsa.id = fibnode_to_lsaid(po, fn);
1092 8a70a13e Ondrej Zajicek
  lsa.rt = po->router_id;
1093 273fd2c1 Ondrej Filip
1094 2918e610 Ondrej Zajicek
  if (nssa && pbit && ipa_zero(fwaddr))
1095 41b612c3 Ondrej Zajicek
  {
1096 2918e610 Ondrej Zajicek
    /* NSSA-LSA with P-bit set must have non-zero forwarding address */
1097
1098
    fwaddr = find_surrogate_fwaddr(oa);
1099
    if (ipa_zero(fwaddr))
1100
    {
1101 35c875f0 Ondrej Zajicek
      log(L_ERR "%s: Cannot find forwarding address for NSSA-LSA %I/%d",
1102 2918e610 Ondrej Zajicek
          p->name, fn->prefix, fn->pxlen);
1103
      return;
1104
    }
1105 41b612c3 Ondrej Zajicek
  }
1106
1107
  if ((en = ospf_hash_find_header(po->gr, dom, &lsa)) != NULL)
1108 7ff5803b Ondrej Zajicek
  {
1109 ed317862 Ondrej Zajicek
    int rv = check_ext_lsa(en, fn, metric, fwaddr, tag);
1110 7ff5803b Ondrej Zajicek
    if (rv < 0)
1111 273fd2c1 Ondrej Filip
    {
1112 35c875f0 Ondrej Zajicek
      log(L_ERR "%s: LSAID collision for %I/%d",
1113 7ff5803b Ondrej Zajicek
          p->name, fn->prefix, fn->pxlen);
1114
      return;
1115 273fd2c1 Ondrej Filip
    }
1116
1117 7ff5803b Ondrej Zajicek
    if (rv > 0)
1118
      return;
1119
  }
1120 52572e94 Ondrej Zajicek
  lsa.sn = get_seqnum(en);
1121 7ff5803b Ondrej Zajicek
1122 2918e610 Ondrej Zajicek
  body = originate_ext_lsa_body(po, &lsa.length, fn, metric, fwaddr, tag, pbit);
1123 d5d9693c Ondrej Filip
  lsasum_calculate(&lsa, body);
1124 c3226991 Ondrej Zajicek
1125 2918e610 Ondrej Zajicek
  if (src) 
1126
    fn->x1 = src;
1127
1128 d494df63 Ondrej Zajicek
  lsa_install_new(po, &lsa, dom, body);
1129 41b612c3 Ondrej Zajicek
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
1130 fdb19982 Ondrej Filip
1131 b9ed99f7 Ondrej Filip
  if (po->ebit == 0)
1132 fdb19982 Ondrej Filip
  {
1133 b9ed99f7 Ondrej Filip
    po->ebit = 1;
1134 fdb19982 Ondrej Filip
    WALK_LIST(oa, po->area_list)
1135
    {
1136
      schedule_rt_lsa(oa);
1137
    }
1138
  }
1139 e8085aba Ondrej Filip
}
1140
1141 c3226991 Ondrej Zajicek
void
1142 bbcfd5a0 Ondrej Zajicek
flush_ext_lsa(struct ospf_area *oa, struct fib_node *fn, int nssa)
1143 c3226991 Ondrej Zajicek
{
1144 41b612c3 Ondrej Zajicek
  struct proto_ospf *po = oa->po;
1145 be862406 Ondrej Zajicek
  struct proto *p = &po->proto;
1146 c3226991 Ondrej Zajicek
  struct top_hash_entry *en;
1147 be862406 Ondrej Zajicek
1148 41b612c3 Ondrej Zajicek
  u32 dom = nssa ? oa->areaid : 0;
1149
  u32 type = nssa ? LSA_T_NSSA : LSA_T_EXT;
1150 9727681a Ondrej Zajicek
  u32 lsaid = fibnode_to_lsaid(po, fn);
1151 c3226991 Ondrej Zajicek
1152 41b612c3 Ondrej Zajicek
  if (en = ospf_hash_find(po->gr, dom, lsaid, po->router_id, type))
1153 c3226991 Ondrej Zajicek
    {
1154 bbcfd5a0 Ondrej Zajicek
      OSPF_TRACE(D_EVENTS, "Flushing %s-LSA for %I/%d",
1155
                 nssa ? "NSSA" : "AS-external", fn->prefix, fn->pxlen);
1156
1157 7ff5803b Ondrej Zajicek
      if (check_ext_lsa(en, fn, 0, IPA_NONE, 0) < 0)
1158 c3226991 Ondrej Zajicek
        {
1159 35c875f0 Ondrej Zajicek
          log(L_ERR "%s: LSAID collision for %I/%d",
1160 9727681a Ondrej Zajicek
              p->name, fn->prefix, fn->pxlen);
1161
          return;
1162 c3226991 Ondrej Zajicek
        }
1163 9727681a Ondrej Zajicek
1164 ed317862 Ondrej Zajicek
      fn->x1 = 0;
1165 9727681a Ondrej Zajicek
      ospf_lsupd_flush_nlsa(po, en);
1166 c3226991 Ondrej Zajicek
    }
1167
}
1168
1169
1170
#ifdef OSPFv3
1171
1172
static void *
1173
originate_link_lsa_body(struct ospf_iface *ifa, u16 *length)
1174
{
1175
  struct proto_ospf *po = ifa->oa->po;
1176
  struct ospf_lsa_link *ll;
1177
  int i = 0;
1178
  u8 flags;
1179
1180
  ASSERT(po->lsab_used == 0);
1181
  ll = lsab_allocz(po, sizeof(struct ospf_lsa_link));
1182
  ll->options = ifa->oa->options | (ifa->priority << 24);
1183 353729f5 Ondrej Zajicek
  ll->lladdr = ifa->addr->ip;
1184 c3226991 Ondrej Zajicek
  ll = NULL; /* buffer might be reallocated later */
1185
1186
  struct ifa *a;
1187
  WALK_LIST(a, ifa->iface->addrs)
1188
    {
1189
      if ((a->flags & IA_SECONDARY) ||
1190
          (a->scope < SCOPE_SITE))
1191
        continue;
1192
1193
      flags = (a->pxlen < MAX_PREFIX_LENGTH) ? 0 : OPT_PX_LA;
1194
      put_ipv6_prefix(lsab_alloc(po, IPV6_PREFIX_SPACE(a->pxlen)),
1195
                      a->ip, a->pxlen, flags, 0);
1196
      i++;
1197
    }
1198
1199
  ll = po->lsab;
1200
  ll->pxcount = i;
1201
  *length = po->lsab_used + sizeof(struct ospf_lsa_header);
1202
  return lsab_flush(po);
1203
}
1204
1205
void
1206
originate_link_lsa(struct ospf_iface *ifa)
1207
{
1208
  struct ospf_lsa_header lsa;
1209
  struct proto_ospf *po = ifa->oa->po;
1210
  struct proto *p = &po->proto;
1211
  void *body;
1212
1213 48e5f32d Ondrej Zajicek
  /* Vlinks do not have link-LSAs */
1214
  if (ifa->type == OSPF_IT_VLINK)
1215
    return;
1216
1217
  OSPF_TRACE(D_EVENTS, "Originating link-LSA for iface %s", ifa->ifname);
1218 c3226991 Ondrej Zajicek
1219
  lsa.age = 0;
1220
  lsa.type = LSA_T_LINK;
1221 dd4da6f6 Ondrej Zajicek
  lsa.id = ifa->iface_id;
1222 8a70a13e Ondrej Zajicek
  lsa.rt = po->router_id;
1223 52572e94 Ondrej Zajicek
  lsa.sn = get_seqnum(ifa->link_lsa);
1224 dd4da6f6 Ondrej Zajicek
  u32 dom = ifa->iface_id;
1225 c3226991 Ondrej Zajicek
1226
  body = originate_link_lsa_body(ifa, &lsa.length);
1227
  lsasum_calculate(&lsa, body);
1228
  ifa->link_lsa = lsa_install_new(po, &lsa, dom, body);
1229
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
1230 be862406 Ondrej Zajicek
1231
  /* Just to be sure to not forget on our link LSA */
1232
  if (ifa->state == OSPF_IS_DR)
1233
    schedule_net_lsa(ifa);
1234 c3226991 Ondrej Zajicek
}
1235
1236 b49e6f5a Ondrej Zajicek
void
1237
update_link_lsa(struct ospf_iface *ifa)
1238
{
1239
  if (ifa->link_lsa && ((ifa->link_lsa->inst_t + MINLSINTERVAL) > now))
1240
    return;
1241
  /*
1242
   * It's too early to originate new link LSA. We will
1243
   * try to do it next tick
1244
   */
1245
  originate_link_lsa(ifa);
1246
  ifa->origlink = 0;
1247
}
1248 c3226991 Ondrej Zajicek
1249 d9e7e1b1 Ondrej Zajicek
static inline void
1250
lsa_put_prefix(struct proto_ospf *po, ip_addr prefix, u32 pxlen, u32 cost)
1251
{
1252
  put_ipv6_prefix(lsab_alloc(po, IPV6_PREFIX_SPACE(pxlen)), prefix, pxlen,
1253
                  (pxlen < MAX_PREFIX_LENGTH) ? 0 : OPT_PX_LA, cost);
1254
}
1255
1256 c3226991 Ondrej Zajicek
static void *
1257
originate_prefix_rt_lsa_body(struct ospf_area *oa, u16 *length)
1258
{
1259
  struct proto_ospf *po = oa->po;
1260 8e48831a Ondrej Zajicek
  struct ospf_config *cf = (struct ospf_config *) (po->proto.cf);
1261 c3226991 Ondrej Zajicek
  struct ospf_iface *ifa;
1262
  struct ospf_lsa_prefix *lp;
1263 3b89a232 Ondrej Zajicek
  int host_addr = 0;
1264 c3226991 Ondrej Zajicek
  int net_lsa;
1265
  int i = 0;
1266
1267
  ASSERT(po->lsab_used == 0);
1268
  lp = lsab_allocz(po, sizeof(struct ospf_lsa_prefix));
1269
  lp->ref_type = LSA_T_RT;
1270
  lp->ref_id = 0;
1271 8a70a13e Ondrej Zajicek
  lp->ref_rt = po->router_id;
1272 c3226991 Ondrej Zajicek
  lp = NULL; /* buffer might be reallocated later */
1273
1274
  WALK_LIST(ifa, po->iface_list)
1275
  {
1276 e4404cef Ondrej Zajicek
    if ((ifa->oa != oa) || (ifa->type == OSPF_IT_VLINK) || (ifa->state == OSPF_IS_DOWN))
1277 c3226991 Ondrej Zajicek
      continue;
1278
1279 e7b4948c Ondrej Zajicek
    ifa->px_pos_beg = i;
1280
1281 c3226991 Ondrej Zajicek
    if ((ifa->type == OSPF_IT_BCAST) ||
1282
        (ifa->type == OSPF_IT_NBMA))
1283
      net_lsa = bcast_net_active(ifa);
1284
    else
1285
      net_lsa = 0;
1286
1287
    struct ifa *a;
1288
    WALK_LIST(a, ifa->iface->addrs)
1289
      {
1290 3b89a232 Ondrej Zajicek
        if ((a->flags & IA_SECONDARY) ||
1291 52a43ae3 Ondrej Zajicek
            (a->flags & IA_PEER) ||
1292 3b89a232 Ondrej Zajicek
            (a->scope <= SCOPE_LINK))
1293
          continue;
1294
1295
        if (((a->pxlen < MAX_PREFIX_LENGTH) && net_lsa) ||
1296 c3226991 Ondrej Zajicek
            configured_stubnet(oa, a))
1297
          continue;
1298
1299 52a43ae3 Ondrej Zajicek
        if ((a->flags & IA_HOST) ||
1300
            (ifa->state == OSPF_IS_LOOP) ||
1301
            (ifa->type == OSPF_IT_PTMP))
1302
        {
1303 d9e7e1b1 Ondrej Zajicek
          lsa_put_prefix(po, a->ip, MAX_PREFIX_LENGTH, 0);
1304 52a43ae3 Ondrej Zajicek
          host_addr = 1;
1305
        }
1306 d9e7e1b1 Ondrej Zajicek
        else
1307
          lsa_put_prefix(po, a->prefix, a->pxlen, ifa->cost);
1308 c3226991 Ondrej Zajicek
        i++;
1309
      }
1310 e7b4948c Ondrej Zajicek
1311
    ifa->px_pos_end = i;
1312 c3226991 Ondrej Zajicek
  }
1313
1314
  struct ospf_stubnet_config *sn;
1315 5cdf264f Ondrej Zajicek
  if (oa->ac)
1316
    WALK_LIST(sn, oa->ac->stubnet_list)
1317
      if (!sn->hidden)
1318 c3226991 Ondrej Zajicek
      {
1319 d9e7e1b1 Ondrej Zajicek
        lsa_put_prefix(po, sn->px.addr, sn->px.len, sn->cost);
1320 e4404cef Ondrej Zajicek
        if (sn->px.len == MAX_PREFIX_LENGTH)
1321
          host_addr = 1;
1322
        i++;
1323
      }
1324
1325
  /* If there are some configured vlinks, find some global address
1326
     (even from another area), which will be used as a vlink endpoint. */
1327
  if (!EMPTY_LIST(cf->vlink_list) && !host_addr)
1328
  {
1329
    WALK_LIST(ifa, po->iface_list)
1330
    {
1331
      if ((ifa->type == OSPF_IT_VLINK) || (ifa->state == OSPF_IS_DOWN))
1332
        continue;
1333
1334
      struct ifa *a;
1335
      WALK_LIST(a, ifa->iface->addrs)
1336
      {
1337
        if ((a->flags & IA_SECONDARY) || (a->scope <= SCOPE_LINK))
1338
          continue;
1339
1340
        /* Found some IP */
1341
        lsa_put_prefix(po, a->ip, MAX_PREFIX_LENGTH, 0);
1342 c3226991 Ondrej Zajicek
        i++;
1343 e4404cef Ondrej Zajicek
        goto done;
1344 c3226991 Ondrej Zajicek
      }
1345 e4404cef Ondrej Zajicek
    }
1346
  }
1347 c3226991 Ondrej Zajicek
1348 e4404cef Ondrej Zajicek
 done:
1349 c3226991 Ondrej Zajicek
  lp = po->lsab;
1350
  lp->pxcount = i;
1351
  *length = po->lsab_used + sizeof(struct ospf_lsa_header);
1352
  return lsab_flush(po);
1353
}
1354
1355
void
1356
originate_prefix_rt_lsa(struct ospf_area *oa)
1357
{
1358
  struct proto_ospf *po = oa->po;
1359 be862406 Ondrej Zajicek
  struct proto *p = &po->proto;  
1360
  struct ospf_lsa_header lsa;
1361 c3226991 Ondrej Zajicek
  void *body;
1362
1363 be862406 Ondrej Zajicek
  OSPF_TRACE(D_EVENTS, "Originating router prefix-LSA for area %R", oa->areaid);
1364
1365 c3226991 Ondrej Zajicek
  lsa.age = 0;
1366
  lsa.type = LSA_T_PREFIX;
1367 be862406 Ondrej Zajicek
  lsa.id = 0;
1368 8a70a13e Ondrej Zajicek
  lsa.rt = po->router_id;
1369 52572e94 Ondrej Zajicek
  lsa.sn = get_seqnum(oa->pxr_lsa);
1370 c3226991 Ondrej Zajicek
  u32 dom = oa->areaid;
1371
1372
  body = originate_prefix_rt_lsa_body(oa, &lsa.length);
1373
  lsasum_calculate(&lsa, body);
1374
  oa->pxr_lsa = lsa_install_new(po, &lsa, dom, body);
1375
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
1376
}
1377
1378
1379
static inline int
1380
prefix_space(u32 *buf)
1381
{
1382
  int pxl = *buf >> 24;
1383
  return IPV6_PREFIX_SPACE(pxl);
1384
}
1385
1386
static inline int
1387
prefix_same(u32 *b1, u32 *b2)
1388
{
1389
  int pxl1 = *b1 >> 24;
1390
  int pxl2 = *b2 >> 24;
1391
  int pxs, i;
1392
  
1393
  if (pxl1 != pxl2)
1394
    return 0;
1395
1396
  pxs = IPV6_PREFIX_WORDS(pxl1);
1397
  for (i = 1; i < pxs; i++)
1398
    if (b1[i] != b2[i])
1399
      return 0;
1400
1401
  return 1;
1402
}
1403
1404
static inline u32 *
1405
prefix_advance(u32 *buf)
1406
{
1407 be862406 Ondrej Zajicek
  int pxl = *buf >> 24;
1408
  return buf + IPV6_PREFIX_WORDS(pxl);
1409 c3226991 Ondrej Zajicek
}
1410
1411 2918e610 Ondrej Zajicek
/* FIXME eliminate items with LA bit set? see 4.4.3.9 */
1412 c3226991 Ondrej Zajicek
static void
1413 be862406 Ondrej Zajicek
add_prefix(struct proto_ospf *po, u32 *px, int offset, int *pxc)
1414 c3226991 Ondrej Zajicek
{
1415 be862406 Ondrej Zajicek
  u32 *pxl = lsab_offset(po, offset);
1416 c3226991 Ondrej Zajicek
  int i;
1417 e4404cef Ondrej Zajicek
  for (i = 0; i < *pxc; pxl = prefix_advance(pxl), i++)
1418
    if (prefix_same(px, pxl))
1419 c3226991 Ondrej Zajicek
    {
1420 e4404cef Ondrej Zajicek
      /* Options should be logically OR'ed together */
1421
      *pxl |= (*px & 0x00FF0000);
1422
      return;
1423 c3226991 Ondrej Zajicek
    }
1424
1425
  ASSERT(pxl == lsab_end(po));
1426
1427
  int pxspace = prefix_space(px);
1428
  pxl = lsab_alloc(po, pxspace);
1429
  memcpy(pxl, px, pxspace);
1430 e4404cef Ondrej Zajicek
  *pxl &= 0xFFFF0000;        /* Set metric to zero */
1431 c3226991 Ondrej Zajicek
  (*pxc)++;
1432
}
1433
1434 be862406 Ondrej Zajicek
static void
1435
add_link_lsa(struct proto_ospf *po, struct top_hash_entry *en, int offset, int *pxc)
1436
{
1437
  struct ospf_lsa_link *ll = en->lsa_body;
1438
  u32 *pxb = ll->rest;
1439
  int j;
1440
1441 e4404cef Ondrej Zajicek
  for (j = 0; j < ll->pxcount; pxb = prefix_advance(pxb), j++)
1442
  {
1443
    u8 pxlen = (pxb[0] >> 24);
1444
    u8 pxopts = (pxb[0] >> 16);
1445
1446
    /* Skip NU or LA prefixes */
1447
    if (pxopts & (OPT_PX_NU | OPT_PX_LA))
1448
      continue;
1449
1450
    /* Skip link-local prefixes */
1451
    if ((pxlen >= 10) && ((pxb[1] & 0xffc00000) == 0xfe800000))
1452
      continue;
1453
1454
    add_prefix(po, pxb, offset, pxc);
1455
  }
1456 be862406 Ondrej Zajicek
}
1457
1458
1459 c3226991 Ondrej Zajicek
1460
static void *
1461
originate_prefix_net_lsa_body(struct ospf_iface *ifa, u16 *length)
1462
{
1463
  struct proto_ospf *po = ifa->oa->po;
1464
  struct ospf_lsa_prefix *lp;
1465
  struct ospf_neighbor *n;
1466
  struct top_hash_entry *en;
1467 be862406 Ondrej Zajicek
  int pxc, offset;
1468 c3226991 Ondrej Zajicek
1469
  ASSERT(po->lsab_used == 0);
1470
  lp = lsab_allocz(po, sizeof(struct ospf_lsa_prefix));
1471
  lp->ref_type = LSA_T_NET;
1472
  lp->ref_id = ifa->net_lsa->lsa.id;
1473 8a70a13e Ondrej Zajicek
  lp->ref_rt = po->router_id;
1474 c3226991 Ondrej Zajicek
  lp = NULL; /* buffer might be reallocated later */
1475
1476 be862406 Ondrej Zajicek
  pxc = 0;
1477 c3226991 Ondrej Zajicek
  offset = po->lsab_used;
1478
1479 be862406 Ondrej Zajicek
  /* Find all Link LSAs associated with the link and merge their prefixes */
1480
  if (ifa->link_lsa)
1481
    add_link_lsa(po, ifa->link_lsa, offset, &pxc);
1482
1483 c3226991 Ondrej Zajicek
  WALK_LIST(n, ifa->neigh_list)
1484
    if ((n->state == NEIGHBOR_FULL) &&
1485 dd4da6f6 Ondrej Zajicek
              (en = ospf_hash_find(po->gr, ifa->iface_id, n->iface_id, n->rid, LSA_T_LINK)))
1486 be862406 Ondrej Zajicek
      add_link_lsa(po, en, offset, &pxc);
1487 c3226991 Ondrej Zajicek
1488
  lp = po->lsab;
1489 be862406 Ondrej Zajicek
  lp->pxcount = pxc;
1490 c3226991 Ondrej Zajicek
  *length = po->lsab_used + sizeof(struct ospf_lsa_header);
1491
  return lsab_flush(po);
1492
}
1493
1494
void
1495
originate_prefix_net_lsa(struct ospf_iface *ifa)
1496
{
1497
  struct proto_ospf *po = ifa->oa->po;
1498 be862406 Ondrej Zajicek
  struct proto *p = &po->proto;
1499
  struct ospf_lsa_header lsa;
1500 c3226991 Ondrej Zajicek
  void *body;
1501
1502 48e5f32d Ondrej Zajicek
  OSPF_TRACE(D_EVENTS, "Originating network prefix-LSA for iface %s", ifa->ifname);
1503 be862406 Ondrej Zajicek
1504 c3226991 Ondrej Zajicek
  lsa.age = 0;
1505
  lsa.type = LSA_T_PREFIX;
1506 dd4da6f6 Ondrej Zajicek
  lsa.id = ifa->iface_id;
1507 8a70a13e Ondrej Zajicek
  lsa.rt = po->router_id;
1508 52572e94 Ondrej Zajicek
  lsa.sn = get_seqnum(ifa->pxn_lsa);
1509 c3226991 Ondrej Zajicek
  u32 dom = ifa->oa->areaid;
1510
1511
  body = originate_prefix_net_lsa_body(ifa, &lsa.length);
1512
  lsasum_calculate(&lsa, body);
1513
  ifa->pxn_lsa = lsa_install_new(po, &lsa, dom, body);
1514
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
1515
}
1516
1517 061ab802 Ondrej Zajicek
void
1518
flush_prefix_net_lsa(struct ospf_iface *ifa)
1519
{
1520
  struct proto_ospf *po = ifa->oa->po;
1521
  struct proto *p = &po->proto;
1522
  struct top_hash_entry *en = ifa->pxn_lsa;
1523
  u32 dom = ifa->oa->areaid;
1524
1525
  if (en == NULL)
1526
    return;
1527
1528 48e5f32d Ondrej Zajicek
  OSPF_TRACE(D_EVENTS, "Flushing network prefix-LSA for iface %s", ifa->ifname);
1529 be862406 Ondrej Zajicek
1530 061ab802 Ondrej Zajicek
  en->lsa.sn += 1;
1531
  en->lsa.age = LSA_MAXAGE;
1532
  lsasum_calculate(&en->lsa, en->lsa_body);
1533
  ospf_lsupd_flood(po, NULL, NULL, &en->lsa, dom, 0);
1534
  flush_lsa(en, po);
1535
  ifa->pxn_lsa = NULL;
1536
}
1537
1538
1539 c3226991 Ondrej Zajicek
#endif
1540 e8085aba Ondrej Filip
1541 b49e6f5a Ondrej Zajicek
1542 6ba36f06 Martin Mares
static void
1543
ospf_top_ht_alloc(struct top_graph *f)
1544
{
1545
  f->hash_size = 1 << f->hash_order;
1546
  f->hash_mask = f->hash_size - 1;
1547
  if (f->hash_order > HASH_HI_MAX - HASH_HI_STEP)
1548
    f->hash_entries_max = ~0;
1549
  else
1550
    f->hash_entries_max = f->hash_size HASH_HI_MARK;
1551
  if (f->hash_order < HASH_LO_MIN + HASH_LO_STEP)
1552
    f->hash_entries_min = 0;
1553
  else
1554
    f->hash_entries_min = f->hash_size HASH_LO_MARK;
1555
  DBG("Allocating OSPF hash of order %d: %d hash_entries, %d low, %d high\n",
1556
      f->hash_order, f->hash_size, f->hash_entries_min, f->hash_entries_max);
1557 b9ed99f7 Ondrej Filip
  f->hash_table =
1558
    mb_alloc(f->pool, f->hash_size * sizeof(struct top_hash_entry *));
1559 6ba36f06 Martin Mares
  bzero(f->hash_table, f->hash_size * sizeof(struct top_hash_entry *));
1560
}
1561
1562
static inline void
1563
ospf_top_ht_free(struct top_hash_entry **h)
1564
{
1565
  mb_free(h);
1566
}
1567
1568
static inline u32
1569
ospf_top_hash_u32(u32 a)
1570
{
1571
  /* Shamelessly stolen from IP address hashing in ipv4.h */
1572
  a ^= a >> 16;
1573
  a ^= a << 10;
1574
  return a;
1575
}
1576
1577
static inline unsigned
1578 c3226991 Ondrej Zajicek
ospf_top_hash(struct top_graph *f, u32 domain, u32 lsaid, u32 rtrid, u32 type)
1579
{
1580 be862406 Ondrej Zajicek
  /* In OSPFv2, we don't know Router ID when looking for network LSAs.
1581 9f0ba7b1 Ondrej Zajicek
     In OSPFv3, we don't know LSA ID when looking for router LSAs.
1582
     In both cases, there is (usually) just one (or small number)
1583
     appropriate LSA, so we just clear unknown part of key. */
1584 c3226991 Ondrej Zajicek
1585 9f0ba7b1 Ondrej Zajicek
  return (
1586 c3226991 Ondrej Zajicek
#ifdef OSPFv2
1587
          ((type == LSA_T_NET) ? 0 : ospf_top_hash_u32(rtrid)) +
1588 9f0ba7b1 Ondrej Zajicek
          ospf_top_hash_u32(lsaid) + 
1589 c3226991 Ondrej Zajicek
#else /* OSPFv3 */
1590
          ospf_top_hash_u32(rtrid) +
1591 9f0ba7b1 Ondrej Zajicek
          ((type == LSA_T_RT) ? 0 : ospf_top_hash_u32(lsaid)) +
1592 c3226991 Ondrej Zajicek
#endif
1593 9f0ba7b1 Ondrej Zajicek
          type + domain) & f->hash_mask;
1594 c3226991 Ondrej Zajicek
1595
  /*
1596 b9ed99f7 Ondrej Filip
  return (ospf_top_hash_u32(lsaid) + ospf_top_hash_u32(rtrid) +
1597 86c84d76 Ondrej Filip
          type + areaid) & f->hash_mask;
1598 c3226991 Ondrej Zajicek
  */
1599 6ba36f06 Martin Mares
}
1600
1601 7ab3ff6a Ondrej Filip
/**
1602
 * ospf_top_new - allocated new topology database
1603 c3226991 Ondrej Zajicek
 * @p: current instance of ospf
1604 7ab3ff6a Ondrej Filip
 *
1605 c3226991 Ondrej Zajicek
 * this dynamically hashed structure is often used for keeping lsas. mainly
1606 baa5dd6c Ondrej Filip
 * its used in @ospf_area structure.
1607 7ab3ff6a Ondrej Filip
 */
1608 6ba36f06 Martin Mares
struct top_graph *
1609 d5d9693c Ondrej Filip
ospf_top_new(pool *pool)
1610 6ba36f06 Martin Mares
{
1611
  struct top_graph *f;
1612
1613 035f6acb Ondrej Filip
  f = mb_allocz(pool, sizeof(struct top_graph));
1614
  f->pool = pool;
1615 6ba36f06 Martin Mares
  f->hash_slab = sl_new(f->pool, sizeof(struct top_hash_entry));
1616
  f->hash_order = HASH_DEF_ORDER;
1617
  ospf_top_ht_alloc(f);
1618
  f->hash_entries = 0;
1619
  f->hash_entries_min = 0;
1620
  return f;
1621
}
1622
1623
void
1624
ospf_top_free(struct top_graph *f)
1625
{
1626
  rfree(f->hash_slab);
1627
  ospf_top_ht_free(f->hash_table);
1628
  mb_free(f);
1629
}
1630
1631
static void
1632
ospf_top_rehash(struct top_graph *f, int step)
1633
{
1634
  unsigned int oldn, oldh;
1635
  struct top_hash_entry **n, **oldt, **newt, *e, *x;
1636
1637
  oldn = f->hash_size;
1638
  oldt = f->hash_table;
1639 b49e6f5a Ondrej Zajicek
  DBG("re-hashing topology hash from order %d to %d\n", f->hash_order,
1640 b9ed99f7 Ondrej Filip
      f->hash_order + step);
1641 6ba36f06 Martin Mares
  f->hash_order += step;
1642
  ospf_top_ht_alloc(f);
1643
  newt = f->hash_table;
1644
1645 b9ed99f7 Ondrej Filip
  for (oldh = 0; oldh < oldn; oldh++)
1646
  {
1647
    e = oldt[oldh];
1648
    while (e)
1649 6ba36f06 Martin Mares
    {
1650 b9ed99f7 Ondrej Filip
      x = e->next;
1651 c3226991 Ondrej Zajicek
      n = newt + ospf_top_hash(f, e->domain, e->lsa.id, e->lsa.rt, e->lsa.type);
1652 b9ed99f7 Ondrej Filip
      e->next = *n;
1653
      *n = e;
1654
      e = x;
1655 6ba36f06 Martin Mares
    }
1656 b9ed99f7 Ondrej Filip
  }
1657 6ba36f06 Martin Mares
  ospf_top_ht_free(oldt);
1658
}
1659
1660 f9c799a0 Ondrej Zajicek
#ifdef OSPFv2
1661
1662
u32
1663
ospf_lsa_domain(u32 type, struct ospf_iface *ifa)
1664
{
1665
  return (type == LSA_T_EXT) ? 0 : ifa->oa->areaid;
1666
}
1667
1668
#else /* OSPFv3 */
1669
1670 b49e6f5a Ondrej Zajicek
u32
1671
ospf_lsa_domain(u32 type, struct ospf_iface *ifa)
1672
{
1673
  switch (type & LSA_SCOPE_MASK)
1674
    {
1675
    case LSA_SCOPE_LINK:
1676 dd4da6f6 Ondrej Zajicek
      return ifa->iface_id;
1677 b49e6f5a Ondrej Zajicek
1678
    case LSA_SCOPE_AREA:
1679
      return ifa->oa->areaid;
1680
1681
    case LSA_SCOPE_AS:
1682
    default:
1683
      return 0;
1684
    }
1685
}
1686
1687 f9c799a0 Ondrej Zajicek
#endif
1688
1689 6ba36f06 Martin Mares
struct top_hash_entry *
1690 b49e6f5a Ondrej Zajicek
ospf_hash_find_header(struct top_graph *f, u32 domain, struct ospf_lsa_header *h)
1691 921a93f2 Ondrej Filip
{
1692 b49e6f5a Ondrej Zajicek
  return ospf_hash_find(f, domain, h->id, h->rt, h->type);
1693 921a93f2 Ondrej Filip
}
1694 d8852b36 Ondrej Filip
1695
struct top_hash_entry *
1696 b49e6f5a Ondrej Zajicek
ospf_hash_get_header(struct top_graph *f, u32 domain, struct ospf_lsa_header *h)
1697 d8852b36 Ondrej Filip
{
1698 b49e6f5a Ondrej Zajicek
  return ospf_hash_get(f, domain, h->id, h->rt, h->type);
1699 d8852b36 Ondrej Filip
}
1700
1701 921a93f2 Ondrej Filip
struct top_hash_entry *
1702 b49e6f5a Ondrej Zajicek
ospf_hash_find(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type)
1703 6ba36f06 Martin Mares
{
1704 86c84d76 Ondrej Filip
  struct top_hash_entry *e;
1705 c3226991 Ondrej Zajicek
  e = f->hash_table[ospf_top_hash(f, domain, lsa, rtr, type)];
1706 86c84d76 Ondrej Filip
1707 9f0ba7b1 Ondrej Zajicek
  while (e && (e->lsa.id != lsa || e->lsa.type != type || e->lsa.rt != rtr || e->domain != domain))
1708
    e = e->next;
1709
1710
  return e;
1711
}
1712
1713
1714 c3226991 Ondrej Zajicek
#ifdef OSPFv2
1715
1716 9f0ba7b1 Ondrej Zajicek
/* In OSPFv2, sometimes we don't know Router ID when looking for network LSAs.
1717
   There should be just one, so we find any match. */
1718
struct top_hash_entry *
1719
ospf_hash_find_net(struct top_graph *f, u32 domain, u32 lsa)
1720
{
1721
  struct top_hash_entry *e;
1722
  e = f->hash_table[ospf_top_hash(f, domain, lsa, 0, LSA_T_NET)];
1723
1724
  while (e && (e->lsa.id != lsa || e->lsa.type != LSA_T_NET || e->domain != domain))
1725
    e = e->next;
1726
1727
  return e;
1728
}
1729 86c84d76 Ondrej Filip
1730 c3226991 Ondrej Zajicek
#endif
1731
1732
1733 9f0ba7b1 Ondrej Zajicek
#ifdef OSPFv3
1734
1735
/* In OSPFv3, usually we don't know LSA ID when looking for router
1736
   LSAs. We return matching LSA with smallest LSA ID. */
1737
struct top_hash_entry *
1738
ospf_hash_find_rt(struct top_graph *f, u32 domain, u32 rtr)
1739
{
1740
  struct top_hash_entry *rv = NULL;
1741
  struct top_hash_entry *e;
1742
  e = f->hash_table[ospf_top_hash(f, domain, 0, rtr, LSA_T_RT)];
1743
  
1744
  while (e)
1745
    {
1746
      if (e->lsa.rt == rtr && e->lsa.type == LSA_T_RT && e->domain == domain)
1747
        if (!rv || e->lsa.id < rv->lsa.id)
1748
          rv = e;
1749
      e = e->next;
1750
    }
1751
1752
  return rv;
1753
}
1754
1755
static inline struct top_hash_entry *
1756
find_matching_rt(struct top_hash_entry *e, u32 domain, u32 rtr)
1757
{
1758
  while (e && (e->lsa.rt != rtr || e->lsa.type != LSA_T_RT || e->domain != domain))
1759
    e = e->next;
1760 6ba36f06 Martin Mares
  return e;
1761
}
1762
1763
struct top_hash_entry *
1764 9f0ba7b1 Ondrej Zajicek
ospf_hash_find_rt_first(struct top_graph *f, u32 domain, u32 rtr)
1765
{
1766
  struct top_hash_entry *e;
1767
  e = f->hash_table[ospf_top_hash(f, domain, 0, rtr, LSA_T_RT)];
1768
  return find_matching_rt(e, domain, rtr);
1769
}
1770
1771
struct top_hash_entry *
1772
ospf_hash_find_rt_next(struct top_hash_entry *e)
1773
{
1774
  return find_matching_rt(e->next, e->domain, e->lsa.rt);
1775
}
1776
1777
#endif
1778
1779
1780
struct top_hash_entry *
1781 b49e6f5a Ondrej Zajicek
ospf_hash_get(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type)
1782 6ba36f06 Martin Mares
{
1783 86c84d76 Ondrej Filip
  struct top_hash_entry **ee;
1784
  struct top_hash_entry *e;
1785
1786 c3226991 Ondrej Zajicek
  ee = f->hash_table + ospf_top_hash(f, domain, lsa, rtr, type);
1787 86c84d76 Ondrej Filip
  e = *ee;
1788
1789 c3226991 Ondrej Zajicek
  while (e && (e->lsa.id != lsa || e->lsa.rt != rtr || e->lsa.type != type || e->domain != domain))
1790
    e = e->next;
1791 6ba36f06 Martin Mares
1792
  if (e)
1793
    return e;
1794 933bfdde Ondrej Filip
1795 6ba36f06 Martin Mares
  e = sl_alloc(f->hash_slab);
1796 933bfdde Ondrej Filip
  e->color = OUTSPF;
1797
  e->dist = LSINFINITY;
1798 57c574d8 Ondrej Zajicek
  e->nhs = NULL;
1799 3b16080c Ondrej Filip
  e->lb = IPA_NONE;
1800 ce17d4c1 Ondrej Filip
  e->lsa.id = lsa;
1801
  e->lsa.rt = rtr;
1802
  e->lsa.type = type;
1803
  e->lsa_body = NULL;
1804 c3226991 Ondrej Zajicek
  e->domain = domain;
1805 933bfdde Ondrej Filip
  e->next = *ee;
1806 b9ed99f7 Ondrej Filip
  *ee = e;
1807 6ba36f06 Martin Mares
  if (f->hash_entries++ > f->hash_entries_max)
1808
    ospf_top_rehash(f, HASH_HI_STEP);
1809
  return e;
1810
}
1811
1812
void
1813
ospf_hash_delete(struct top_graph *f, struct top_hash_entry *e)
1814
{
1815 86c84d76 Ondrej Filip
  struct top_hash_entry **ee = f->hash_table + 
1816 c3226991 Ondrej Zajicek
    ospf_top_hash(f, e->domain, e->lsa.id, e->lsa.rt, e->lsa.type);
1817 6ba36f06 Martin Mares
1818
  while (*ee)
1819 b9ed99f7 Ondrej Filip
  {
1820
    if (*ee == e)
1821 6ba36f06 Martin Mares
    {
1822 b9ed99f7 Ondrej Filip
      *ee = e->next;
1823
      sl_free(f->hash_slab, e);
1824
      if (f->hash_entries-- < f->hash_entries_min)
1825
        ospf_top_rehash(f, -HASH_LO_STEP);
1826
      return;
1827 6ba36f06 Martin Mares
    }
1828 b9ed99f7 Ondrej Filip
    ee = &((*ee)->next);
1829
  }
1830 6ba36f06 Martin Mares
  bug("ospf_hash_delete() called for invalid node");
1831
}
1832
1833 e81b440f Ondrej Zajicek
/*
1834 226cb2bc Ondrej Filip
static void
1835
ospf_dump_lsa(struct top_hash_entry *he, struct proto *p)
1836
{
1837 e81b440f Ondrej Zajicek

1838 226cb2bc Ondrej Filip
  struct ospf_lsa_rt *rt = NULL;
1839
  struct ospf_lsa_rt_link *rr = NULL;
1840
  struct ospf_lsa_net *ln = NULL;
1841
  u32 *rts = NULL;
1842
  u32 i, max;
1843

1844 3aab39f5 Ondrej Zajicek
  OSPF_TRACE(D_EVENTS, "- %1x %-1R %-1R %4u 0x%08x 0x%04x %-1R",
1845
             he->lsa.type, he->lsa.id, he->lsa.rt, he->lsa.age, he->lsa.sn,
1846 c3226991 Ondrej Zajicek
             he->lsa.checksum, he->domain);
1847 226cb2bc Ondrej Filip

1848 b49e6f5a Ondrej Zajicek

1849 226cb2bc Ondrej Filip
  switch (he->lsa.type)
1850
    {
1851
    case LSA_T_RT:
1852
      rt = he->lsa_body;
1853
      rr = (struct ospf_lsa_rt_link *) (rt + 1);
1854

1855 c3226991 Ondrej Zajicek
      for (i = 0; i < lsa_rt_items(&he->lsa); i++)
1856 3aab39f5 Ondrej Zajicek
        OSPF_TRACE(D_EVENTS, "  - %1x %-1R %-1R %5u",
1857
                   rr[i].type, rr[i].id, rr[i].data, rr[i].metric);
1858 226cb2bc Ondrej Filip
      break;
1859

1860
    case LSA_T_NET:
1861
      ln = he->lsa_body;
1862
      rts = (u32 *) (ln + 1);
1863

1864 c3226991 Ondrej Zajicek
      for (i = 0; i < lsa_net_items(&he->lsa); i++)
1865 3aab39f5 Ondrej Zajicek
        OSPF_TRACE(D_EVENTS, "  - %-1R", rts[i]);
1866 226cb2bc Ondrej Filip
      break;
1867

1868
    default:
1869
      break;
1870
    }
1871
}
1872

1873 6ba36f06 Martin Mares
void
1874 992705f6 Ondrej Filip
ospf_top_dump(struct top_graph *f, struct proto *p)
1875 6ba36f06 Martin Mares
{
1876 89ba9a18 Ondrej Filip
  unsigned int i;
1877 992705f6 Ondrej Filip
  OSPF_TRACE(D_EVENTS, "Hash entries: %d", f->hash_entries);
1878 6ba36f06 Martin Mares

1879 b9ed99f7 Ondrej Filip
  for (i = 0; i < f->hash_size; i++)
1880
  {
1881 226cb2bc Ondrej Filip
    struct top_hash_entry *e;
1882
    for (e = f->hash_table[i]; e != NULL; e = e->next)
1883
      ospf_dump_lsa(e, p);
1884 b9ed99f7 Ondrej Filip
  }
1885 6ba36f06 Martin Mares
}
1886 e81b440f Ondrej Zajicek
*/
1887 de30342f Ondrej Filip
1888 baa5dd6c Ondrej Filip
/* This is very inefficient, please don't call it often */
1889 ad5453b5 Ondrej Filip
1890
/* I should also test for every LSA if it's in some link state
1891 baa5dd6c Ondrej Filip
 * retransmission list for every neighbor. I will not test it.
1892
 * It could happen that I'll receive some strange ls ack's.
1893 ad5453b5 Ondrej Filip
 */
1894
1895
int
1896 86c84d76 Ondrej Filip
can_flush_lsa(struct proto_ospf *po)
1897 ad5453b5 Ondrej Filip
{
1898
  struct ospf_iface *ifa;
1899
  struct ospf_neighbor *n;
1900
1901 86c84d76 Ondrej Filip
  WALK_LIST(ifa, po->iface_list)
1902 ad5453b5 Ondrej Filip
  {
1903 86c84d76 Ondrej Filip
    WALK_LIST(n, ifa->neigh_list)
1904 ad5453b5 Ondrej Filip
    {
1905 86c84d76 Ondrej Filip
      if ((n->state == NEIGHBOR_EXCHANGE) || (n->state == NEIGHBOR_LOADING))
1906
        return 0;
1907
1908 b9ed99f7 Ondrej Filip
      break;
1909 ad5453b5 Ondrej Filip
    }
1910
  }
1911
1912 9e48d717 Ondrej Filip
  return 1;
1913 ad5453b5 Ondrej Filip
}