Statistics
| Branch: | Revision:

iof-bird-daemon / proto / ospf / lsupd.c @ 23d67029

History | View | Annotate | Download (14.2 KB)

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

    
9
#include "ospf.h"
10

    
11
/**
12
 * ospf_lsupd_flood - send received or generated lsa to the neighbors
13
 * @n: neighbor than sent this lsa (or NULL if generated)
14
 * @hn: LSA header followed by lsa body in network endianity (may be NULL) 
15
 * @hh: LSA header in host endianity (must be filled)
16
 * @iff: interface which received this LSA (or NULL if LSA is generated)
17
 * @oa: ospf_area which is the LSA generated for
18
 * @rtl: add this LSA into retransmission list
19
 *
20
 * return value - was the LSA flooded back?
21
 */
22

    
23
int
24
ospf_lsupd_flood(struct ospf_neighbor *n, struct ospf_lsa_header *hn,
25
                 struct ospf_lsa_header *hh, struct ospf_iface *iff,
26
                 struct ospf_area *oa, int rtl)
27
{
28
  struct ospf_iface *ifa;
29
  struct ospf_neighbor *nn;
30
  struct top_hash_entry *en;
31
  struct proto_ospf *po = oa->po;
32
  struct proto *p = &po->proto;
33
  int ret, retval = 0;
34

    
35
  /* pg 148 */
36
  WALK_LIST(ifa, po->iface_list)
37
  {
38
    if (ifa->stub)
39
      continue;
40

    
41
    if (hh->type == LSA_T_EXT)
42
    {
43
      if (ifa->type == OSPF_IT_VLINK)
44
        continue;
45
      if (ifa->oa->stub)
46
        continue;
47
    }
48
    else
49
    {
50
      if (ifa->oa != oa)
51
        continue;
52
    }
53

    
54
    DBG("Wanted to flood LSA: Type: %u, ID: %I, RT: %I, SN: 0x%x, Age %u\n",
55
        hh->type, hh->id, hh->rt, hh->sn, hh->age);
56

    
57
    ret = 0;
58
    WALK_LIST(nn, ifa->neigh_list)
59
    {
60
      if (nn->state < NEIGHBOR_EXCHANGE)
61
        continue;
62
      if (nn->state < NEIGHBOR_FULL)
63
      {
64
        if ((en = ospf_hash_find_header(nn->lsrqh, nn->ifa->oa->areaid, hh)) != NULL)
65
        {
66
          DBG("That LSA found in lsreq list for neigh %I\n", nn->rid);
67

    
68
          switch (lsa_comp(hh, &en->lsa))
69
          {
70
          case CMP_OLDER:
71
            continue;
72
            break;
73
          case CMP_SAME:
74
            s_rem_node(SNODE en);
75
            if (en->lsa_body != NULL)
76
              mb_free(en->lsa_body);
77
            en->lsa_body = NULL;
78
            DBG("Removing from lsreq list for neigh %I\n", nn->rid);
79
            ospf_hash_delete(nn->lsrqh, en);
80
            if (EMPTY_SLIST(nn->lsrql))
81
              ospf_neigh_sm(nn, INM_LOADDONE);
82
            continue;
83
            break;
84
          case CMP_NEWER:
85
            s_rem_node(SNODE en);
86
            if (en->lsa_body != NULL)
87
              mb_free(en->lsa_body);
88
            en->lsa_body = NULL;
89
            DBG("Removing from lsreq list for neigh %I\n", nn->rid);
90
            ospf_hash_delete(nn->lsrqh, en);
91
            if (EMPTY_SLIST(nn->lsrql))
92
              ospf_neigh_sm(nn, INM_LOADDONE);
93
            break;
94
          default:
95
            bug("Bug in lsa_comp?");
96
          }
97
        }
98
      }
99

    
100
      if (nn == n)
101
        continue;
102

    
103
      if (rtl)
104
      {
105
        if ((en = ospf_hash_find_header(nn->lsrth, nn->ifa->oa->areaid, hh)) == NULL)
106
        {
107
          en = ospf_hash_get_header(nn->lsrth, nn->ifa->oa, hh);
108
        }
109
        else
110
        {
111
          s_rem_node(SNODE en);
112
        }
113
        s_add_tail(&nn->lsrtl, SNODE en);
114
        memcpy(&en->lsa, hh, sizeof(struct ospf_lsa_header));
115
        DBG("Adding that LSA for flood to %I\n", nn->ip);
116
      }
117
      else
118
      {
119
        if ((en = ospf_hash_find_header(nn->lsrth, nn->ifa->oa->areaid, hh)) != NULL)
120
        {
121
          s_rem_node(SNODE en);
122
          if (en->lsa_body != NULL)
123
            mb_free(en->lsa_body);
124
          en->lsa_body = NULL;
125
          ospf_hash_delete(nn->lsrth, en);
126
        }
127
      }
128

    
129
      ret = 1;
130
    }
131

    
132
    if (ret == 0)
133
      continue;                        /* pg 150 (2) */
134

    
135
    if (ifa == iff)
136
    {
137
      if ((n->rid == iff->drid) || n->rid == iff->bdrid)
138
        continue;                /* pg 150 (3) */
139
      if (iff->state == OSPF_IS_BACKUP)
140
        continue;                /* pg 150 (4) */
141
      retval = 1;
142
    }
143

    
144
    {
145
      sock *sk;
146
      u16 len, age;
147
      struct ospf_lsupd_packet *pk;
148
      struct ospf_packet *op;
149
      struct ospf_lsa_header *lh;
150

    
151
      if ((ifa->type == OSPF_IT_NBMA) || (ifa->type == OSPF_IT_VLINK))
152
        sk = ifa->ip_sk;
153
      else
154
        sk = ifa->hello_sk;
155

    
156
      pk = (struct ospf_lsupd_packet *) sk->tbuf;
157
      op = (struct ospf_packet *) sk->tbuf;
158

    
159
      ospf_pkt_fill_hdr(ifa, pk, LSUPD_P);
160
      pk->lsano = htonl(1);
161

    
162
      lh = (struct ospf_lsa_header *) (pk + 1);
163

    
164
      /* Copy LSA into the packet */
165
      if (hn)
166
      {
167
        memcpy(lh, hn, ntohs(hn->length));
168
      }
169
      else
170
      {
171
        u8 *help;
172
        struct top_hash_entry *en;
173

    
174
        htonlsah(hh, lh);
175
        help = (u8 *) (lh + 1);
176
        en = ospf_hash_find_header(po->gr, oa->areaid, hh);
177
        htonlsab(en->lsa_body, help, hh->type, hh->length
178
                 - sizeof(struct ospf_lsa_header));
179
      }
180

    
181
      len = sizeof(struct ospf_lsupd_packet) + ntohs(lh->length);
182

    
183
      age = ntohs(lh->age);
184
      age += ifa->inftransdelay;
185
      if (age > LSA_MAXAGE)
186
        age = LSA_MAXAGE;
187
      lh->age = htons(age);
188

    
189
      op->length = htons(len);
190
      OSPF_TRACE(D_PACKETS, "LS upd flooded via %s", ifa->iface->name);
191
      DBG("ID=%I, AGE=%d, SEQ=%x\n", ntohl(lh->id), ntohs(lh->age),
192
          ntohl(lh->sn));
193

    
194
      switch (ifa->type)
195
      {
196
      case OSPF_IT_NBMA:
197
        if ((ifa->state == OSPF_IS_BACKUP) || (ifa->state == OSPF_IS_DR))
198
          ospf_send_to_agt(sk, ifa, NEIGHBOR_EXCHANGE);
199
        else
200
          ospf_send_to_bdr(sk, ifa);
201
        break;
202

    
203
      case OSPF_IT_VLINK:
204
        ospf_send_to(sk, ifa->vip, ifa);
205
        break;
206

    
207
      default:
208
        if ((ifa->state == OSPF_IS_BACKUP) || (ifa->state == OSPF_IS_DR) ||
209
            (ifa->type == OSPF_IT_PTP))
210
          ospf_send_to(sk, AllSPFRouters, ifa);
211
        else
212
          ospf_send_to(sk, AllDRouters, ifa);
213
      }
214
    }
215
  }
216
  return retval;
217
}
218

    
219
void                                /* I send all I received in LSREQ */
220
ospf_lsupd_send_list(struct ospf_neighbor *n, list * l)
221
{
222
  struct l_lsr_head *llsh;
223
  u16 len;
224
  u32 lsano;
225
  struct top_hash_entry *en;
226
  struct ospf_lsupd_packet *pk;
227
  struct ospf_packet *op;
228
  struct ospf_area *oa = n->ifa->oa;
229
  struct proto_ospf *po = oa->po;
230
  struct proto *p = &po->proto;
231
  void *pktpos;
232

    
233
  if (EMPTY_LIST(*l))
234
    return;
235

    
236
  pk = (struct ospf_lsupd_packet *) n->ifa->ip_sk->tbuf;
237
  op = (struct ospf_packet *) n->ifa->ip_sk->tbuf;
238

    
239
  DBG("LSupd: 1st packet\n");
240

    
241
  ospf_pkt_fill_hdr(n->ifa, pk, LSUPD_P);
242
  len = sizeof(struct ospf_lsupd_packet);
243
  lsano = 0;
244
  pktpos = (pk + 1);
245

    
246
  WALK_LIST(llsh, *l)
247
  {
248
    if ((en = ospf_hash_find(po->gr, oa->areaid, llsh->lsh.id, llsh->lsh.rt,
249
                             llsh->lsh.type)) == NULL)
250
      continue;                        /* Probably flushed LSA */
251
    /* FIXME This is a bug! I cannot flush LSA that is in lsrt */
252

    
253
    DBG("Sending LSA: Type=%u, ID=%I, RT=%I, SN: 0x%x, Age: %u\n",
254
        llsh->lsh.type, llsh->lsh.id, llsh->lsh.rt, en->lsa.sn, en->lsa.age);
255
    if (((u32) (len + en->lsa.length)) > ospf_pkt_maxsize(n->ifa))
256
    {
257
      pk->lsano = htonl(lsano);
258
      op->length = htons(len);
259

    
260
      ospf_send_to(n->ifa->ip_sk, n->ip, n->ifa);
261
      OSPF_TRACE(D_PACKETS, "LS upd sent to %I (%d LSAs)", n->ip, lsano);
262

    
263
      DBG("LSupd: next packet\n");
264
      ospf_pkt_fill_hdr(n->ifa, pk, LSUPD_P);
265
      len = sizeof(struct ospf_lsupd_packet);
266
      lsano = 0;
267
      pktpos = (pk + 1);
268
    }
269
    htonlsah(&(en->lsa), pktpos);
270
    pktpos = pktpos + sizeof(struct ospf_lsa_header);
271
    htonlsab(en->lsa_body, pktpos, en->lsa.type, en->lsa.length
272
             - sizeof(struct ospf_lsa_header));
273
    pktpos = pktpos + en->lsa.length - sizeof(struct ospf_lsa_header);
274
    len += en->lsa.length;
275
    lsano++;
276
  }
277
  if (lsano > 0)
278
  {
279
    pk->lsano = htonl(lsano);
280
    op->length = htons(len);
281

    
282
    OSPF_TRACE(D_PACKETS, "LS upd sent to %I (%d LSAs)", n->ip, lsano);
283
    ospf_send_to(n->ifa->ip_sk, n->ip, n->ifa);
284
  }
285
}
286

    
287
void
288
ospf_lsupd_receive(struct ospf_lsupd_packet *ps,
289
                   struct ospf_iface *ifa, struct ospf_neighbor *n)
290
{
291
  u32 area;
292
  struct ospf_neighbor *ntmp;
293
  struct ospf_lsa_header *lsa;
294
  struct ospf_area *oa;
295
  struct proto_ospf *po = ifa->oa->po;
296
  struct proto *p = &po->proto;
297
  unsigned int i, sendreq = 1, size = ntohs(ps->ospf_packet.length);
298

    
299
  if (n->state < NEIGHBOR_EXCHANGE)
300
  {
301
    OSPF_TRACE(D_PACKETS,
302
               "Received lsupd in lesser state than EXCHANGE from (%I)",
303
               n->ip);
304
    return;
305
  }
306

    
307
  if (size <=
308
      (sizeof(struct ospf_lsupd_packet) + sizeof(struct ospf_lsa_header)))
309
  {
310
    log(L_WARN "Received lsupd from %I is too short!", n->ip);
311
    return;
312
  }
313

    
314
  OSPF_TRACE(D_PACKETS, "Received LS upd from %I", n->ip);
315
  ospf_neigh_sm(n, INM_HELLOREC);        /* Questionable */
316

    
317
  lsa = (struct ospf_lsa_header *) (ps + 1);
318
  area = htonl(ps->ospf_packet.areaid);
319
  oa = ospf_find_area((struct proto_ospf *) p, area);
320

    
321
  for (i = 0; i < ntohl(ps->lsano); i++,
322
       lsa = (struct ospf_lsa_header *) (((u8 *) lsa) + ntohs(lsa->length)))
323
  {
324
    struct ospf_lsa_header lsatmp;
325
    struct top_hash_entry *lsadb;
326
    unsigned diff = ((u8 *) lsa) - ((u8 *) ps), lenn = ntohs(lsa->length);
327
    u16 chsum;
328

    
329
    if (((diff + sizeof(struct ospf_lsa_header)) >= size)
330
        || ((lenn + diff) > size))
331
    {
332
      log(L_WARN "Received lsupd from %I is too short!", n->ip);
333
      ospf_neigh_sm(n, INM_BADLSREQ);
334
      break;
335
    }
336

    
337
    if ((lenn <= sizeof(struct ospf_lsa_header))
338
        || (lenn != (4 * (lenn / 4))))
339
    {
340
      log(L_WARN "Received LSA from %I with bad length", n->ip);
341
      ospf_neigh_sm(n, INM_BADLSREQ);
342
      break;
343
    }
344

    
345
    /* pg 143 (1) */
346
    chsum = lsa->checksum;
347
    if (chsum != lsasum_check(lsa, NULL))
348
    {
349
      log(L_WARN "Received bad lsa checksum from %I", n->ip);
350
      continue;
351
    }
352

    
353
    /* pg 143 (2) */
354
    if ((lsa->type < LSA_T_RT) || (lsa->type > LSA_T_EXT))
355
    {
356
      log(L_WARN "Unknown LSA type from %I", n->ip);
357
      continue;
358
    }
359

    
360
    /* pg 143 (3) */
361
    if ((lsa->type == LSA_T_EXT) && oa->stub)
362
    {
363
      log(L_WARN "Received External LSA in stub area from %I", n->ip);
364
      continue;
365
    }
366

    
367
    ntohlsah(lsa, &lsatmp);
368

    
369
    DBG("Update Type: %u ID: %I RT: %I, Sn: 0x%08x Age: %u, Sum: %u\n",
370
        lsatmp.type, lsatmp.id, lsatmp.rt, lsatmp.sn, lsatmp.age,
371
        lsatmp.checksum);
372

    
373
    lsadb = ospf_hash_find_header(po->gr, oa->areaid, &lsatmp);
374

    
375
#ifdef LOCAL_DEBUG
376
    if (lsadb)
377
      DBG("I have Type: %u ID: %I RT: %I, Sn: 0x%08x Age: %u, Sum: %u\n",
378
          lsadb->lsa.type, lsadb->lsa.id, lsadb->lsa.rt, lsadb->lsa.sn,
379
          lsadb->lsa.age, lsadb->lsa.checksum);
380
#endif
381

    
382
    /* pg 143 (4) */
383
    if ((lsatmp.age == LSA_MAXAGE) && (lsadb == NULL) && can_flush_lsa(po))
384
    {
385
      ospf_lsack_enqueue(n, lsa, ACKL_DIRECT);
386
      continue;
387
    }
388

    
389
    /* pg 144 (5) */
390
    if ((lsadb == NULL) || (lsa_comp(&lsatmp, &lsadb->lsa) == CMP_NEWER))
391
    {
392
      struct ospf_iface *ift = NULL;
393
      void *body;
394
      struct ospf_iface *nifa;
395
      int self = (lsatmp.rt == p->cf->global->router_id);
396

    
397
      DBG("PG143(5): Received LSA is newer\n");
398

    
399
      /* pg 145 (5f) - premature aging of self originated lsa */
400
      if ((!self) && (lsatmp.type == LSA_T_NET))
401
      {
402
        WALK_LIST(nifa, po->iface_list)
403
        {
404
          if (!nifa->iface)
405
            continue;
406
          if (ipa_equal(nifa->iface->addr->ip, ipa_from_u32(lsatmp.id)))
407
          {
408
            self = 1;
409
            break;
410
          }
411
        }
412
      }
413

    
414
      if (self)
415
      {
416
        struct top_hash_entry *en;
417

    
418
        if ((lsatmp.age == LSA_MAXAGE) && (lsatmp.sn == LSA_MAXSEQNO))
419
        {
420
          ospf_lsack_enqueue(n, lsa, ACKL_DIRECT);
421
          continue;
422
        }
423

    
424
        lsatmp.age = LSA_MAXAGE;
425
        lsatmp.sn = LSA_MAXSEQNO;
426
        lsa->age = htons(LSA_MAXAGE);
427
        lsa->sn = htonl(LSA_MAXSEQNO);
428
        OSPF_TRACE(D_EVENTS, "Premature aging self originated lsa.");
429
        OSPF_TRACE(D_EVENTS, "Type: %d, Id: %I, Rt: %I", lsatmp.type,
430
                   lsatmp.id, lsatmp.rt);
431
        lsasum_check(lsa, (lsa + 1));        /* It also calculates chsum! */
432
        lsatmp.checksum = ntohs(lsa->checksum);
433
        ospf_lsupd_flood(NULL, lsa, &lsatmp, NULL, oa, 0);
434
        if (en = ospf_hash_find_header(po->gr, oa->areaid, &lsatmp))
435
        {
436
          ospf_lsupd_flood(NULL, NULL, &en->lsa, NULL, oa, 1);
437
        }
438
        continue;
439
      }
440

    
441
      /* pg 144 (5a) */
442
      if (lsadb && ((now - lsadb->inst_t) <= MINLSARRIVAL))        /* FIXME: test for flooding? */
443
      {
444
        DBG("I got it in less that MINLSARRIVAL\n");
445
        sendreq = 0;
446
        continue;
447
      }
448

    
449
      if (ospf_lsupd_flood(n, lsa, &lsatmp, ifa, ifa->oa, 1) == 0)
450
      {
451
        DBG("Wasn't flooded back\n");        /* ps 144(5e), pg 153 */
452
        if (ifa->state == OSPF_IS_BACKUP)
453
        {
454
          if (ifa->drid == n->rid)
455
            ospf_lsack_enqueue(n, lsa, ACKL_DELAY);
456
        }
457
        else
458
          ospf_lsack_enqueue(n, lsa, ACKL_DELAY);
459
      }
460

    
461
      /* Remove old from all ret lists */
462
      /* pg 144 (5c) */
463
      if (lsadb)
464
        WALK_LIST(ift, po->iface_list)
465
          WALK_LIST(ntmp, ift->neigh_list)
466
      {
467
        struct top_hash_entry *en;
468
        if (ntmp->state > NEIGHBOR_EXSTART)
469
          if ((en = ospf_hash_find_header(ntmp->lsrth, ntmp->ifa->oa->areaid, &lsadb->lsa)) != NULL)
470
          {
471
            s_rem_node(SNODE en);
472
            if (en->lsa_body != NULL)
473
              mb_free(en->lsa_body);
474
            en->lsa_body = NULL;
475
            ospf_hash_delete(ntmp->lsrth, en);
476
          }
477
      }
478

    
479
      if ((lsatmp.age == LSA_MAXAGE) && (lsatmp.sn == LSA_MAXSEQNO)
480
          && lsadb && can_flush_lsa(po))
481
      {
482
        flush_lsa(lsadb, po);
483
        schedule_rtcalc(po);
484
        continue;
485
      }                                /* FIXME lsack? */
486

    
487
      /* pg 144 (5d) */
488
      body =
489
        mb_alloc(p->pool, lsatmp.length - sizeof(struct ospf_lsa_header));
490
      ntohlsab(lsa + 1, body, lsatmp.type,
491
               lsatmp.length - sizeof(struct ospf_lsa_header));
492
      lsadb = lsa_install_new(&lsatmp, body, oa);
493
      DBG("New LSA installed in DB\n");
494

    
495
      continue;
496
    }
497

    
498
    /* FIXME pg145 (6) */
499

    
500
    /* pg145 (7) */
501
    if (lsa_comp(&lsatmp, &lsadb->lsa) == CMP_SAME)
502
    {
503
      struct top_hash_entry *en;
504
      DBG("PG145(7) Got the same LSA\n");
505
      if ((en = ospf_hash_find_header(n->lsrth, n->ifa->oa->areaid, &lsadb->lsa)) != NULL)
506
      {
507
        /* pg145 (7a) */
508
        s_rem_node(SNODE en);
509
        if (en->lsa_body != NULL)
510
          mb_free(en->lsa_body);
511
        en->lsa_body = NULL;
512
        ospf_hash_delete(n->lsrth, en);
513
        if (ifa->state == OSPF_IS_BACKUP)
514
        {
515
          if (n->rid == ifa->drid)
516
            ospf_lsack_enqueue(n, lsa, ACKL_DELAY);
517
        }
518
      }
519
      else
520
      {
521
        /* pg145 (7b) */
522
        ospf_lsack_enqueue(n, lsa, ACKL_DIRECT);
523
      }
524
      sendreq = 0;
525
      continue;
526
    }
527

    
528
    /* pg145 (8) */
529
    if ((lsadb->lsa.age == LSA_MAXAGE) && (lsadb->lsa.sn == LSA_MAXSEQNO))
530
    {
531
      continue;
532
    }
533

    
534
    {
535
      list l;
536
      struct l_lsr_head ll;
537
      init_list(&l);
538
      ll.lsh.id = lsadb->lsa.id;
539
      ll.lsh.rt = lsadb->lsa.rt;
540
      ll.lsh.type = lsadb->lsa.type;
541
      add_tail(&l, NODE & ll);
542
      ospf_lsupd_send_list(n, &l);
543
    }
544
  }
545

    
546
  /* Send direct LSAs */
547
  ospf_lsack_send(n, ACKL_DIRECT);
548

    
549
  if (sendreq && (n->state == NEIGHBOR_LOADING))
550
  {
551
    ospf_lsreq_send(n);                /* Ask for another part of neighbor's database */
552
  }
553
}
554

    
555
void
556
ospf_lsupd_flush_nlsa(struct top_hash_entry *en, struct ospf_area *oa)
557
{
558
  struct ospf_lsa_header *lsa = &en->lsa;
559
  struct proto_ospf *po = oa->po;
560
  struct proto *p = &po->proto;
561

    
562
  lsa->age = LSA_MAXAGE;
563
  lsa->sn = LSA_MAXSEQNO;
564
  lsasum_calculate(lsa, en->lsa_body);
565
  OSPF_TRACE(D_EVENTS, "Premature aging self originated lsa!");
566
  OSPF_TRACE(D_EVENTS, "Type: %d, Id: %I, Rt: %I", lsa->type,
567
             lsa->id, lsa->rt);
568
  ospf_lsupd_flood(NULL, NULL, lsa, NULL, oa, 0);
569
}