Statistics
| Branch: | Revision:

iof-bird-daemon / proto / ospf / topology.c @ a97122a3

History | View | Annotate | Download (23.6 KB)

1
/*
2
 *        BIRD -- OSPF Topological Database
3
 *
4
 *        (c) 1999       Martin Mares <mj@ucw.cz>
5
 *        (c) 1999--2004 Ondrej Filip <feela@network.cz>
6
 *
7
 *        Can be freely distributed and used under the terms of the GNU GPL.
8
 */
9

    
10
#include "nest/bird.h"
11
#include "lib/string.h"
12

    
13
#include "ospf.h"
14

    
15
#define HASH_DEF_ORDER 6
16
#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
int ptp_unnumbered_stub_lsa = 0;
24

    
25
static void *
26
originate_rt_lsa_body(struct ospf_area *oa, u16 * length)
27
{
28
  struct proto_ospf *po = oa->po;
29
  struct ospf_iface *ifa;
30
  int j = 0, k = 0;
31
  u16 i = 0;
32
  struct ospf_lsa_rt *rt;
33
  struct ospf_lsa_rt_link *ln, *ln_after;
34
  struct ospf_neighbor *neigh;
35

    
36
  DBG("%s: Originating RT_lsa body for area \"%I\".\n", po->proto.name,
37
      oa->areaid);
38

    
39
  WALK_LIST(ifa, po->iface_list)
40
  {
41
    if ((ifa->oa == oa) && (ifa->state != OSPF_IS_DOWN))
42
    {
43
      i++;
44
      if ((ifa->type == OSPF_IT_PTP) && (ifa->state == OSPF_IS_PTP) &&
45
                (ptp_unnumbered_stub_lsa || !(ifa->iface->addr->flags & IA_UNNUMBERED)))
46
        i++;
47
    }
48
  }
49
  rt = mb_allocz(po->proto.pool, sizeof(struct ospf_lsa_rt) +
50
                 i * sizeof(struct ospf_lsa_rt_link));
51
  if (po->areano > 1)
52
    rt->veb.bit.b = 1;
53
  if ((po->ebit) && (!oa->stub))
54
    rt->veb.bit.e = 1;
55
  ln = (struct ospf_lsa_rt_link *) (rt + 1);
56
  ln_after = ln + i;
57

    
58
  WALK_LIST(ifa, po->iface_list)
59
  {
60
    if ((ifa->type == OSPF_IT_VLINK) && (ifa->voa == oa) && (!EMPTY_LIST(ifa->neigh_list)))
61
    {
62
      neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
63
      if ((neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
64
        rt->veb.bit.v = 1;
65
    }
66

    
67
    if ((ifa->oa != oa) || (ifa->state == OSPF_IS_DOWN))
68
      continue;
69

    
70
    if (ln == ln_after)
71
      die("LSA space overflow");
72

    
73
    if (ifa->state == OSPF_IS_LOOP)
74
    {
75
      ln->type = 3;
76
      ln->id = ipa_to_u32(ifa->iface->addr->ip);
77
      ln->data = 0xffffffff;
78
      ln->metric = 0;
79
      ln->notos = 0;
80
    }
81
    else
82
    {
83
      switch (ifa->type)
84
      {
85
      case OSPF_IT_PTP:        /* rfc2328 - pg126 */
86
        neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
87
        if ((!EMPTY_LIST(ifa->neigh_list)) && (neigh->state == NEIGHBOR_FULL))
88
        {
89
          ln->type = LSART_PTP;
90
          ln->id = neigh->rid;
91
          ln->metric = ifa->cost;
92
          ln->notos = 0;
93
          if (ifa->iface->addr->flags & IA_UNNUMBERED)
94
          {
95
            ln->data = ifa->iface->index;
96
          }
97
          else
98
          {
99
            ln->data = ipa_to_u32(ifa->iface->addr->ip);
100
          }
101
        }
102
        else
103
        {
104
          ln--;
105
          i--;                /* No link added */
106
        }
107

    
108
        if ((ifa->state == OSPF_IS_PTP) && 
109
            (ptp_unnumbered_stub_lsa || !(ifa->iface->addr->flags & IA_UNNUMBERED)))
110
        {
111
          ln++;
112
          if (ln == ln_after)
113
            die("LSA space overflow");
114

    
115
          ln->type = LSART_STUB;
116
          ln->metric = ifa->cost;
117
          ln->notos = 0;
118
          if (ifa->iface->addr->flags & IA_UNNUMBERED)
119
          {
120
            ln->id = ipa_to_u32(ifa->iface->addr->opposite);
121
            ln->data = 0xffffffff;
122
          }
123
          else
124
          {
125
            ln->data = ipa_to_u32(ipa_mkmask(ifa->iface->addr->pxlen));
126
            ln->id = ipa_to_u32(ifa->iface->addr->prefix) & ln->data;
127
          }
128
        }
129
        break;
130
      case OSPF_IT_BCAST:
131
      case OSPF_IT_NBMA:
132
        if (ifa->state == OSPF_IS_WAITING)
133
        {
134
          ln->type = LSART_STUB;
135
          ln->data = ipa_to_u32(ipa_mkmask(ifa->iface->addr->pxlen));
136
          ln->id = ipa_to_u32(ifa->iface->addr->prefix) & ln->data;
137
          ln->metric = ifa->cost;
138
          ln->notos = 0;
139
        }
140
        else
141
        {
142
          j = 0, k = 0;
143
          WALK_LIST(neigh, ifa->neigh_list)
144
          {
145
            if ((neigh->rid == ifa->drid) && (neigh->state == NEIGHBOR_FULL))
146
              k = 1;
147
            if (neigh->state == NEIGHBOR_FULL)
148
              j = 1;
149
          }
150
          if (((ifa->state == OSPF_IS_DR) && (j == 1)) || (k == 1))
151
          {
152
            ln->type = LSART_NET;
153
            ln->id = ipa_to_u32(ifa->drip);
154
            ln->data = ipa_to_u32(ifa->iface->addr->ip);
155
            ln->metric = ifa->cost;
156
            ln->notos = 0;
157
          }
158
          else
159
          {
160
            ln->type = LSART_STUB;
161
            ln->data = ipa_to_u32(ipa_mkmask(ifa->iface->addr->pxlen));
162
            ln->id = ipa_to_u32(ifa->iface->addr->prefix) & ln->data;
163
            ln->metric = ifa->cost;
164
            ln->notos = 0;
165
          }
166
        }
167
        break;
168
      case OSPF_IT_VLINK:
169
        neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
170
        if ((!EMPTY_LIST(ifa->neigh_list)) && (neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
171
        {
172
          ln->type = LSART_VLNK;
173
          ln->id = neigh->rid;
174
          ln->metric = ifa->cost;
175
          ln->notos = 0;
176
        }
177
        else
178
        {
179
          ln--;
180
          i--;                /* No link added */
181
        }
182
        break;
183
      default:
184
        ln--;
185
        i--;                /* No link added */
186
        log("Unknown interface type %s", ifa->iface->name);
187
        break;
188
      }
189
    }
190
    ln++;
191
  }
192
  rt->links = i;
193
  *length = i * sizeof(struct ospf_lsa_rt_link) + sizeof(struct ospf_lsa_rt) +
194
    sizeof(struct ospf_lsa_header);
195
  return rt;
196
}
197

    
198
/**
199
 * originate_rt_lsa - build new instance of router LSA
200
 * @oa: ospf_area which is LSA built to
201
 *
202
 * It builds router LSA walking through all OSPF interfaces in
203
 * specified OSPF area. This function is mostly called from
204
 * area_disp(). Builds new LSA, increases sequence number (if old
205
 * instance exists) and sets age of LSA to zero.
206
 */
207
void
208
originate_rt_lsa(struct ospf_area *oa)
209
{
210
  struct ospf_lsa_header lsa;
211
  struct proto_ospf *po = oa->po;
212
  struct proto *p = &po->proto;
213
  u32 rtid = po->proto.cf->global->router_id;
214
  struct top_hash_entry *en;
215
  void *body;
216

    
217
  if ((oa->rt) && ((oa->rt->inst_t + MINLSINTERVAL)) > now)
218
    return;
219
  /*
220
   * Tick is probably set to very low value. We cannot
221
   * originate new LSA before MINLSINTERVAL. We will
222
   * try to do it next tick.
223
   */
224

    
225
  OSPF_TRACE(D_EVENTS, "Originating RT_lsa for area \"%I\".", oa->areaid);
226

    
227
  lsa.age = 0;
228
  lsa.id = rtid;
229
  lsa.type = LSA_T_RT;
230
  lsa.rt = rtid;
231
  lsa.options = oa->opt.byte;
232
  if (oa->rt == NULL)
233
  {
234
    lsa.sn = LSA_INITSEQNO;
235
  }
236
  else
237
  {
238
    lsa.sn = oa->rt->lsa.sn + 1;
239
  }
240
  body = originate_rt_lsa_body(oa, &lsa.length);
241
  lsasum_calculate(&lsa, body);
242
  en = lsa_install_new(&lsa, body, oa);
243
  oa->rt = en;
244
  ospf_lsupd_flood(NULL, NULL, &oa->rt->lsa, NULL, oa, 1);
245
  schedule_rtcalc(po);
246
  oa->origrt = 0;
247
}
248

    
249
static void *
250
originate_net_lsa_body(struct ospf_iface *ifa, u16 * length,
251
                       struct proto_ospf *po)
252
{
253
  u16 i = 1;
254
  struct ospf_neighbor *n;
255
  u32 *body;
256
  struct ospf_lsa_net *net;
257

    
258
  net = mb_alloc(po->proto.pool, sizeof(u32) * (ifa->fadj + 1) +
259
                 sizeof(struct ospf_lsa_net));
260
  net->netmask = ipa_mkmask(ifa->iface->addr->pxlen);
261

    
262
  body = (u32 *) (net + 1);
263
  i = 1;
264
  *body = po->proto.cf->global->router_id;
265
  WALK_LIST(n, ifa->neigh_list)
266
  {
267
    if (n->state == NEIGHBOR_FULL)
268
    {
269
      *(body + i) = n->rid;
270
      i++;
271
    }
272
  }
273
  *length = i * sizeof(u32) + sizeof(struct ospf_lsa_header) +
274
    sizeof(struct ospf_lsa_net);
275
  return net;
276
}
277

    
278
/**
279
 * originate_net_lsa - originates of deletes network LSA
280
 * @ifa: interface which is LSA originated for
281
 *
282
 * Interface counts number of adjacent neighbors. If this number is
283
 * lower than one or interface is not in state %OSPF_IS_DR it deletes
284
 * and premature ages instance of network LSA for specified interface.
285
 * In other case, new instance of network LSA is originated.
286
 */
287
void
288
originate_net_lsa(struct ospf_iface *ifa)
289
{
290
  struct proto_ospf *po = ifa->oa->po;
291
  struct ospf_lsa_header lsa;
292
  u32 rtid = po->proto.cf->global->router_id;
293
  struct proto *p = &po->proto;
294
  void *body;
295

    
296
  if (ifa->nlsa && ((ifa->nlsa->inst_t + MINLSINTERVAL) > now))
297
    return;
298
  /*
299
   * It's too early to originate new network LSA. We will
300
   * try to do it next tick
301
   */
302

    
303
  if ((ifa->state != OSPF_IS_DR) || (ifa->fadj == 0))
304
  {
305
    if (ifa->nlsa == NULL)
306
      return;
307

    
308
    OSPF_TRACE(D_EVENTS, "Deleting Net lsa for iface \"%s\".",
309
               ifa->iface->name);
310
    ifa->nlsa->lsa.sn += 1;
311
    ifa->nlsa->lsa.age = LSA_MAXAGE;
312
    ospf_lsupd_flood(NULL, NULL, &ifa->nlsa->lsa, NULL, ifa->oa, 0);
313
    s_rem_node(SNODE ifa->nlsa);
314
    if (ifa->nlsa->lsa_body != NULL)
315
      mb_free(ifa->nlsa->lsa_body);
316
    ifa->nlsa->lsa_body = NULL;
317
    ospf_hash_delete(po->gr, ifa->nlsa);
318
    schedule_rtcalc(po);
319
    ifa->nlsa = NULL;
320
    return;
321
  }
322

    
323
  OSPF_TRACE(D_EVENTS, "Originating Net lsa for iface \"%s\".",
324
             ifa->iface->name);
325

    
326
  lsa.age = 0;
327
  lsa.id = ipa_to_u32(ifa->iface->addr->ip);
328
  lsa.type = LSA_T_NET;
329
  lsa.rt = rtid;
330
  lsa.options = ifa->oa->opt.byte;
331
  if (ifa->nlsa == NULL)
332
  {
333
    lsa.sn = LSA_INITSEQNO;
334
  }
335
  else
336
  {
337
    lsa.sn = ifa->nlsa->lsa.sn + 1;
338
  }
339

    
340
  body = originate_net_lsa_body(ifa, &lsa.length, po);
341
  lsasum_calculate(&lsa, body);
342
  ifa->nlsa = lsa_install_new(&lsa, body, ifa->oa);
343
  ospf_lsupd_flood(NULL, NULL, &ifa->nlsa->lsa, NULL, ifa->oa, 1);
344
  ifa->orignet = 0;
345
}
346

    
347

    
348
static void *
349
originate_ext_lsa_body(net * n, rte * e, struct proto_ospf *po,
350
                       struct ea_list *attrs)
351
{
352
  struct proto *p = &po->proto;
353
  struct ospf_lsa_ext *ext;
354
  struct ospf_lsa_ext_tos *et;
355
  u32 m1 = ea_get_int(attrs, EA_OSPF_METRIC1, LSINFINITY);
356
  u32 m2 = ea_get_int(attrs, EA_OSPF_METRIC2, 10000);
357
  u32 tag = ea_get_int(attrs, EA_OSPF_TAG, 0);
358
  int inas = 0;
359

    
360
  ext = mb_alloc(p->pool, sizeof(struct ospf_lsa_ext) +
361
                 sizeof(struct ospf_lsa_ext_tos));
362
  ext->netmask = ipa_mkmask(n->n.pxlen);
363

    
364
  et = (struct ospf_lsa_ext_tos *) (ext + 1);
365

    
366
  if (m1 != LSINFINITY)
367
  {
368
    et->etm.metric = m1;
369
    et->etm.etos.tos = 0;
370
    et->etm.etos.ebit = 0;
371
  }
372
  else
373
  {
374
    et->etm.metric = m2;
375
    et->etm.etos.tos = 0;
376
    et->etm.etos.ebit = 1;
377
  }
378
  et->tag = tag;
379
  if (!ipa_equal(e->attrs->gw, IPA_NONE))
380
  {
381
    if (ospf_iface_find((struct proto_ospf *) p, e->attrs->iface) != NULL)
382
      inas = 1;
383
  }
384

    
385
  if (!inas)
386
    et->fwaddr = IPA_NONE;
387
  else
388
    et->fwaddr = e->attrs->gw;
389
  return ext;
390
}
391

    
392
/**
393
 * max_ext_lsa - calculate the maximum amount of external networks
394
 * possible for the given prefix length.
395
 * @pxlen: network prefix length
396
 *
397
 * This is a fix for the previous static use of MAXNETS which did
398
 * only work correct if MAXNETS < possible IPs for given prefix.
399
 * This solution is kind of a hack as there can now only be one
400
 * route for /32 type entries but this is better than the crashes
401
 * I did experience whith close together /32 routes originating
402
 * on different hosts.
403
 */
404

    
405
int
406
max_ext_lsa(unsigned pxlen)
407
{
408
  int i;
409
  for (i = 1; pxlen < BITS_PER_IP_ADDRESS; pxlen++, i <<= 1)
410
    if (i >= MAXNETS)
411
      return MAXNETS;
412
  return i;
413
}
414

    
415
void
416
flush_sum_lsa(struct ospf_area *oa, struct fib_node *fn, int type)
417
{
418
  struct proto_ospf *po = oa->po;
419
  struct proto *p = &po->proto;
420
  struct top_hash_entry *en;
421
  u32 rtid = po->proto.cf->global->router_id;
422
  struct ospf_lsa_header lsa;
423
  int max, i;
424
  struct ospf_lsa_sum *sum = NULL;
425

    
426
  lsa.rt = rtid;
427
  lsa.type = LSA_T_SUM_NET;
428
  if (type == ORT_ROUTER)
429
    lsa.type = LSA_T_SUM_RT;
430

    
431
  max = max_ext_lsa(fn->pxlen);
432

    
433
  for (i = 0; i < max; i++)
434
  {
435
    lsa.id = ipa_to_u32(fn->prefix) + i;
436
    if ((en = ospf_hash_find_header(po->gr, oa->areaid, &lsa)) != NULL)
437
    {
438
      sum = en->lsa_body;
439
      if ((type == ORT_ROUTER) || (fn->pxlen == ipa_mklen(sum->netmask)))
440
      {
441
        en->lsa.age = LSA_MAXAGE;
442
        en->lsa.sn = LSA_MAXSEQNO;
443
        lsasum_calculate(&en->lsa, sum);
444
        OSPF_TRACE(D_EVENTS, "Flushing summary lsa. (id=%I, type=%d)", en->lsa.id, en->lsa.type);
445
        ospf_lsupd_flood(NULL, NULL, &en->lsa, NULL, oa, 1);
446
        if (can_flush_lsa(po)) flush_lsa(en, po);
447
        break;
448
      }
449
    }
450
  }
451
}
452

    
453
void
454
originate_sum_lsa(struct ospf_area *oa, struct fib_node *fn, int type, int metric)
455
{
456
  struct proto_ospf *po = oa->po;
457
  struct proto *p = &po->proto;
458
  struct top_hash_entry *en;
459
  u32 rtid = po->proto.cf->global->router_id;
460
  struct ospf_lsa_header lsa;
461
  int i, max, mlen = fn->pxlen, free = 0;
462
  u32 freeid = 0xFFFF;
463
  struct ospf_lsa_sum *sum = NULL;
464
  union ospf_lsa_sum_tm *tm;
465
  lsa.type = LSA_T_SUM_NET;
466

    
467
  if (type == ORT_ROUTER)
468
  {
469
    lsa.type = LSA_T_SUM_RT;
470
    mlen = 0;
471
  }
472

    
473
  lsa.age = 0;
474
  lsa.rt = rtid;
475
  lsa.sn = LSA_INITSEQNO;
476
  lsa.length = sizeof(struct ospf_lsa_sum) + sizeof(union ospf_lsa_sum_tm) +
477
    sizeof(struct ospf_lsa_header);
478
  lsa.options = oa->opt.byte;
479

    
480
  max = max_ext_lsa(fn->pxlen);
481
  for (i = 0; i < max; i++)
482
  {
483
    lsa.id = ipa_to_u32(fn->prefix) + i;
484
    if ((en = ospf_hash_find_header(po->gr, oa->areaid, &lsa)) == NULL)
485
    {
486
      if (!free)
487
      {
488
        freeid = lsa.id;
489
        free = 1;
490
      }
491
    }
492
    else
493
    {
494
      sum = en->lsa_body;
495
      if (mlen == ipa_mklen(sum->netmask))
496
      {
497
        tm = (union ospf_lsa_sum_tm *) (sum + 1);
498
        if (tm->metric == (unsigned) metric) return;        /* No reason for origination */
499
        lsa.sn = en->lsa.sn + 1;
500
        freeid = en->lsa.id;
501
        free = 1;
502
        break;
503
      }
504
    }
505
  }
506

    
507
  if(!free)
508
  {
509
    log("%s: got more routes for one /%d network then %d, ignoring", p->name,
510
        fn->pxlen, max);
511
    return;
512
  }
513
  lsa.id = freeid;
514
  
515
  OSPF_TRACE(D_EVENTS, "Originating summary (type %d) lsa for %I/%d (met %d).", lsa.type, fn->prefix,
516
             fn->pxlen, metric);
517

    
518
  sum = mb_alloc(p->pool, sizeof(struct ospf_lsa_sum) + sizeof(union ospf_lsa_sum_tm));
519
  sum->netmask = ipa_mkmask(mlen);
520
  tm = (union ospf_lsa_sum_tm *) (sum + 1);
521
  tm->metric = metric;
522
  tm->tos.tos = 0;
523

    
524
  lsasum_calculate(&lsa, sum);
525
  en = lsa_install_new(&lsa, sum, oa);
526
  ospf_lsupd_flood(NULL, NULL, &en->lsa, NULL, oa, 1);
527
}
528

    
529
void
530
check_sum_lsa(struct proto_ospf *po, ort *nf, int dest)
531
{
532
  struct ospf_area *oa;
533
  int flush, mlen;
534
  ip_addr ip;
535

    
536
  if (po->areano < 2) return;
537

    
538
  if ((nf->n.type > RTS_OSPF_IA) && (nf->o.type > RTS_OSPF_IA)) return;
539

    
540
#ifdef LOCAL_DEBUG
541
  DBG("Checking...dest = %d, %I/%d", dest, nf->fn.prefix, nf->fn.pxlen);
542
  if (nf->n.oa) DBG("New: met=%d, oa=%d", nf->n.metric1, nf->n.oa->areaid);
543
  if (nf->o.oa) DBG("Old: met=%d, oa=%d", nf->o.metric1, nf->o.oa->areaid);
544
#endif
545

    
546
  WALK_LIST(oa, po->area_list)
547
  {
548
    flush = 0;
549
    if ((nf->n.metric1 >= LSINFINITY) || (nf->n.type > RTS_OSPF_IA))
550
      flush = 1;
551
    if ((dest == ORT_ROUTER) && (!(nf->n.capa & ORTA_ASBR)))
552
      flush = 1;
553
    if ((!nf->n.oa) || (nf->n.oa->areaid == oa->areaid))
554
      flush = 1;
555

    
556
    if (nf->n.ifa) {
557
      if (nf->n.ifa->oa->areaid == oa->areaid)
558
        flush = 1;
559
      }
560
    else flush = 1;
561

    
562
    /* Don't send summary into stub areas
563
     * We send just default route (and later) */
564
    if (oa->stub)
565
      flush = 1;
566
    
567
    mlen = nf->fn.pxlen;
568
    ip = ipa_and(nf->fn.prefix, ipa_mkmask(mlen));
569

    
570
    if ((oa == po->backbone) && (nf->n.type == RTS_OSPF_IA)) flush = 1;        /* Only intra-area can go to the backbone */
571

    
572
    if ((!flush) && (dest == ORT_NET) && fib_route(&nf->n.oa->net_fib, ip, mlen))        /* The route fits into area networks */
573
    {
574
      flush = 1;
575
      if ((nf->n.oa == po->backbone) && (oa->trcap)) flush = 0;
576
    }
577

    
578
    if(flush)
579
      flush_sum_lsa(oa, &nf->fn, dest);
580
    else
581
      originate_sum_lsa(oa, &nf->fn, dest, nf->n.metric1);
582
  }
583
}
584

    
585
/**
586
 * originate_ext_lsa - new route received from nest and filters
587
 * @n: network prefix and mask
588
 * @e: rte
589
 * @po: current instance of OSPF
590
 * @attrs: list of extended attributes
591
 *
592
 * If I receive a message that new route is installed, I try to originate an
593
 * external LSA. The LSA header of such LSA does not contain information about
594
 * prefix length, so if I have to originate multiple LSAs for route with
595
 * different prefixes I try to increment prefix id to find a "free" one.
596
 *
597
 * The function also sets flag ebit. If it's the first time, the new router lsa
598
 * origination is necessary.
599
 */
600
void
601
originate_ext_lsa(net * n, rte * e, struct proto_ospf *po,
602
                  struct ea_list *attrs)
603
{
604
  struct ospf_lsa_header lsa;
605
  u32 rtid = po->proto.cf->global->router_id;
606
  struct top_hash_entry *en = NULL;
607
  void *body = NULL;
608
  struct proto *p = &po->proto;
609
  struct ospf_area *oa;
610
  struct ospf_lsa_ext *ext1, *ext2;
611
  int i, max;
612

    
613
  OSPF_TRACE(D_EVENTS, "Originating Ext lsa for %I/%d.", n->n.prefix,
614
             n->n.pxlen);
615

    
616
  lsa.age = 0;
617
  lsa.id = ipa_to_u32(n->n.prefix);
618
  lsa.type = LSA_T_EXT;
619
  lsa.rt = rtid;
620
  lsa.sn = LSA_INITSEQNO;
621
  lsa.options = 0;
622

    
623
  body = originate_ext_lsa_body(n, e, po, attrs);
624
  lsa.length = sizeof(struct ospf_lsa_ext) + sizeof(struct ospf_lsa_ext_tos) +
625
    sizeof(struct ospf_lsa_header);
626
  ext1 = body;
627
  max = max_ext_lsa(n->n.pxlen);
628

    
629
  for (i = 0; i < max; i++)
630
  {
631
    if ((en = ospf_hash_find_header(po->gr, 0 , &lsa)) != NULL)
632
    {
633
      ext2 = en->lsa_body;
634
      if (ipa_compare(ext1->netmask, ext2->netmask) != 0)
635
        lsa.id++;
636
      else
637
        break;
638
    }
639
    else
640
      break;
641
  }
642

    
643
  if (i == max)
644
  {
645
    log("%s: got more routes for one /%d network then %d, ignoring", p->name,
646
        n->n.pxlen, max);
647
    mb_free(body);
648
    return;
649
  }
650
  lsasum_calculate(&lsa, body);
651
  WALK_LIST(oa, po->area_list)
652
  {
653
    if (!oa->stub)
654
    {
655
      en = lsa_install_new(&lsa, body, oa);
656
      ospf_lsupd_flood(NULL, NULL, &en->lsa, NULL, oa, 1);
657
      body = originate_ext_lsa_body(n, e, po, attrs);
658
    }
659
  }
660
  mb_free(body);
661

    
662
  if (po->ebit == 0)
663
  {
664
    po->ebit = 1;
665
    WALK_LIST(oa, po->area_list)
666
    {
667
      schedule_rt_lsa(oa);
668
    }
669
  }
670
}
671

    
672

    
673
static void
674
ospf_top_ht_alloc(struct top_graph *f)
675
{
676
  f->hash_size = 1 << f->hash_order;
677
  f->hash_mask = f->hash_size - 1;
678
  if (f->hash_order > HASH_HI_MAX - HASH_HI_STEP)
679
    f->hash_entries_max = ~0;
680
  else
681
    f->hash_entries_max = f->hash_size HASH_HI_MARK;
682
  if (f->hash_order < HASH_LO_MIN + HASH_LO_STEP)
683
    f->hash_entries_min = 0;
684
  else
685
    f->hash_entries_min = f->hash_size HASH_LO_MARK;
686
  DBG("Allocating OSPF hash of order %d: %d hash_entries, %d low, %d high\n",
687
      f->hash_order, f->hash_size, f->hash_entries_min, f->hash_entries_max);
688
  f->hash_table =
689
    mb_alloc(f->pool, f->hash_size * sizeof(struct top_hash_entry *));
690
  bzero(f->hash_table, f->hash_size * sizeof(struct top_hash_entry *));
691
}
692

    
693
static inline void
694
ospf_top_ht_free(struct top_hash_entry **h)
695
{
696
  mb_free(h);
697
}
698

    
699
static inline u32
700
ospf_top_hash_u32(u32 a)
701
{
702
  /* Shamelessly stolen from IP address hashing in ipv4.h */
703
  a ^= a >> 16;
704
  a ^= a << 10;
705
  return a;
706
}
707

    
708
static inline unsigned
709
ospf_top_hash(struct top_graph *f, u32 areaid, u32 lsaid, u32 rtrid, u32 type)
710
{
711
#if 1                                /* Dirty patch to make rt table calculation work. */
712
  return (ospf_top_hash_u32(lsaid) +
713
          ospf_top_hash_u32((type ==
714
                             LSA_T_NET) ? lsaid : rtrid) + type +
715
          (type == LSA_T_EXT ? 0 : areaid)) & f->hash_mask;
716
#else
717
  return (ospf_top_hash_u32(lsaid) + ospf_top_hash_u32(rtrid) +
718
          type + areaid) & f->hash_mask;
719
#endif
720
}
721

    
722
/**
723
 * ospf_top_new - allocated new topology database
724
 * @p: current instance of OSPF
725
 *
726
 * This dynamically hashed structure is often used for keeping LSAs. Mainly
727
 * its used in @ospf_area structure.
728
 */
729
struct top_graph *
730
ospf_top_new(pool *pool)
731
{
732
  struct top_graph *f;
733

    
734
  f = mb_allocz(pool, sizeof(struct top_graph));
735
  f->pool = pool;
736
  f->hash_slab = sl_new(f->pool, sizeof(struct top_hash_entry));
737
  f->hash_order = HASH_DEF_ORDER;
738
  ospf_top_ht_alloc(f);
739
  f->hash_entries = 0;
740
  f->hash_entries_min = 0;
741
  return f;
742
}
743

    
744
void
745
ospf_top_free(struct top_graph *f)
746
{
747
  rfree(f->hash_slab);
748
  ospf_top_ht_free(f->hash_table);
749
  mb_free(f);
750
}
751

    
752
static void
753
ospf_top_rehash(struct top_graph *f, int step)
754
{
755
  unsigned int oldn, oldh;
756
  struct top_hash_entry **n, **oldt, **newt, *e, *x;
757

    
758
  oldn = f->hash_size;
759
  oldt = f->hash_table;
760
  DBG("Re-hashing topology hash from order %d to %d\n", f->hash_order,
761
      f->hash_order + step);
762
  f->hash_order += step;
763
  ospf_top_ht_alloc(f);
764
  newt = f->hash_table;
765

    
766
  for (oldh = 0; oldh < oldn; oldh++)
767
  {
768
    e = oldt[oldh];
769
    while (e)
770
    {
771
      x = e->next;
772
      n = newt + ospf_top_hash(f, e->oa->areaid, e->lsa.id, e->lsa.rt, e->lsa.type);
773
      e->next = *n;
774
      *n = e;
775
      e = x;
776
    }
777
  }
778
  ospf_top_ht_free(oldt);
779
}
780

    
781
struct top_hash_entry *
782
ospf_hash_find_header(struct top_graph *f, u32 areaid, struct ospf_lsa_header *h)
783
{
784
  return ospf_hash_find(f, areaid, h->id, h->rt, h->type);
785
}
786

    
787
struct top_hash_entry *
788
ospf_hash_get_header(struct top_graph *f, struct ospf_area *oa, struct ospf_lsa_header *h)
789
{
790
  return ospf_hash_get(f, oa, h->id, h->rt, h->type);
791
}
792

    
793
struct top_hash_entry *
794
ospf_hash_find(struct top_graph *f, u32 areaid, u32 lsa, u32 rtr, u32 type)
795
{
796
  struct top_hash_entry *e;
797

    
798
  e = f->hash_table[ospf_top_hash(f, areaid, lsa, rtr, type)];
799

    
800
  /* Dirty patch to make rt table calculation work. */
801
  if (type == LSA_T_NET)
802
  {
803
    while (e && (e->lsa.id != lsa || e->lsa.type != LSA_T_NET || e->oa->areaid != areaid))
804
      e = e->next;
805
  }
806
  else if (type == LSA_T_EXT)
807
  {
808
    while (e && (e->lsa.id != lsa || e->lsa.type != type || e->lsa.rt != rtr))
809
      e = e->next;
810
  }
811
  else
812
  {
813
    while (e && (e->lsa.id != lsa || e->lsa.type != type || e->lsa.rt != rtr || e->oa->areaid != areaid))
814
      e = e->next;
815
  }
816

    
817
  return e;
818
}
819

    
820
struct top_hash_entry *
821
ospf_hash_get(struct top_graph *f, struct ospf_area *oa, u32 lsa, u32 rtr, u32 type)
822
{
823
  struct top_hash_entry **ee;
824
  struct top_hash_entry *e;
825
  u32 nareaid = (type == LSA_T_EXT ? 0 : oa->areaid);
826

    
827
  ee = f->hash_table + ospf_top_hash(f, nareaid, lsa, rtr, type);
828
  e = *ee;
829

    
830
  if (type == LSA_T_EXT)
831
  {
832
    while (e && (e->lsa.id != lsa || e->lsa.rt != rtr || e->lsa.type != type))
833
      e = e->next;
834
  }
835
  else
836
  {
837
    while (e && (e->lsa.id != lsa || e->lsa.rt != rtr || e->lsa.type != type || e->oa->areaid != nareaid))
838
      e = e->next;
839
  }
840

    
841
  if (e)
842
    return e;
843

    
844
  e = sl_alloc(f->hash_slab);
845
  e->color = OUTSPF;
846
  e->dist = LSINFINITY;
847
  e->nhi = NULL;
848
  e->nh = IPA_NONE;
849
  e->lb = IPA_NONE;
850
  e->lsa.id = lsa;
851
  e->lsa.rt = rtr;
852
  e->lsa.type = type;
853
  e->lsa_body = NULL;
854
  e->nhi = NULL;
855
  e->oa = oa;
856
  e->next = *ee;
857
  *ee = e;
858
  if (f->hash_entries++ > f->hash_entries_max)
859
    ospf_top_rehash(f, HASH_HI_STEP);
860
  return e;
861
}
862

    
863
void
864
ospf_hash_delete(struct top_graph *f, struct top_hash_entry *e)
865
{
866
  struct top_hash_entry **ee = f->hash_table + 
867
    ospf_top_hash(f, e->oa->areaid, e->lsa.id, e->lsa.rt, e->lsa.type);
868

    
869
  while (*ee)
870
  {
871
    if (*ee == e)
872
    {
873
      *ee = e->next;
874
      sl_free(f->hash_slab, e);
875
      if (f->hash_entries-- < f->hash_entries_min)
876
        ospf_top_rehash(f, -HASH_LO_STEP);
877
      return;
878
    }
879
    ee = &((*ee)->next);
880
  }
881
  bug("ospf_hash_delete() called for invalid node");
882
}
883

    
884
static void
885
ospf_dump_lsa(struct top_hash_entry *he, struct proto *p)
886
{
887
  struct ospf_lsa_rt *rt = NULL;
888
  struct ospf_lsa_rt_link *rr = NULL;
889
  struct ospf_lsa_net *ln = NULL;
890
  u32 *rts = NULL;
891
  u32 i, max;
892

    
893
  OSPF_TRACE(D_EVENTS, "- %1x %-1I %-1I %4u 0x%08x 0x%04x %-1I",
894
        he->lsa.type, he->lsa.id, he->lsa.rt, he->lsa.age,
895
        he->lsa.sn, he->lsa.checksum, he->oa ? he->oa->areaid : 0 );
896

    
897
  switch (he->lsa.type)
898
    {
899
    case LSA_T_RT:
900
      rt = he->lsa_body;
901
      rr = (struct ospf_lsa_rt_link *) (rt + 1);
902

    
903
      for (i = 0; i < rt->links; i++)
904
        OSPF_TRACE(D_EVENTS, "  - %1x %-1I %-1I %5u", rr[i].type, rr[i].id, rr[i].data, rr[i].metric);
905
      break;
906

    
907
    case LSA_T_NET:
908
      ln = he->lsa_body;
909
      rts = (u32 *) (ln + 1);
910
      max = (he->lsa.length - sizeof(struct ospf_lsa_header) -                                                                                                               
911
                sizeof(struct ospf_lsa_net)) / sizeof(u32);
912

    
913
      for (i = 0; i < max; i++)
914
        OSPF_TRACE(D_EVENTS, "  - %-1I", rts[i]);
915
      break;
916

    
917
    default:
918
      break;
919
    }
920
}
921

    
922
void
923
ospf_top_dump(struct top_graph *f, struct proto *p)
924
{
925
  unsigned int i;
926
  OSPF_TRACE(D_EVENTS, "Hash entries: %d", f->hash_entries);
927

    
928
  for (i = 0; i < f->hash_size; i++)
929
  {
930
    struct top_hash_entry *e;
931
    for (e = f->hash_table[i]; e != NULL; e = e->next)
932
      ospf_dump_lsa(e, p);
933
  }
934
}
935

    
936
/* This is very inefficient, please don't call it often */
937

    
938
/* I should also test for every LSA if it's in some link state
939
 * retransmission list for every neighbor. I will not test it.
940
 * It could happen that I'll receive some strange ls ack's.
941
 */
942

    
943
int
944
can_flush_lsa(struct proto_ospf *po)
945
{
946
  struct ospf_iface *ifa;
947
  struct ospf_neighbor *n;
948

    
949
  WALK_LIST(ifa, po->iface_list)
950
  {
951
    WALK_LIST(n, ifa->neigh_list)
952
    {
953
      if ((n->state == NEIGHBOR_EXCHANGE) || (n->state == NEIGHBOR_LOADING))
954
        return 0;
955

    
956
      break;
957
    }
958
  }
959

    
960
  return 1;
961
}