Statistics
| Branch: | Revision:

iof-bird-daemon / proto / ospf / lsalib.c @ e81b440f

History | View | Annotate | Download (12.4 KB)

1
/*
2
 *        BIRD -- OSPF
3
 *
4
 *        (c) 1999--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
void
12
flush_lsa(struct top_hash_entry *en, struct proto_ospf *po)
13
{
14
  struct proto *p = &po->proto;
15

    
16
  OSPF_TRACE(D_EVENTS,
17
             "Going to remove LSA Type: %04x, Id: %R, Rt: %R, Age: %u, Seqno: 0x%x",
18
             en->lsa.type, en->lsa.id, en->lsa.rt, en->lsa.age, en->lsa.sn);
19
  s_rem_node(SNODE en);
20
  if (en->lsa_body != NULL)
21
    mb_free(en->lsa_body);
22
  en->lsa_body = NULL;
23
  ospf_hash_delete(po->gr, en);
24
}
25

    
26
/**
27
 * ospf_age
28
 * @po: ospf protocol
29
 *
30
 * This function is periodicaly invoked from ospf_disp(). It computes the new
31
 * age of all LSAs and old (@age is higher than %LSA_MAXAGE) LSAs are flushed
32
 * whenever possible. If an LSA originated by the router itself is older
33
 * than %LSREFRESHTIME a new instance is originated.
34
 *
35
 * The RFC says that a router should check the checksum of every LSA to detect
36
 * hardware problems. BIRD does not do this to minimalize CPU utilization.
37
 *
38
 * If routing table calculation is scheduled, it also invalidates the old routing
39
 * table calculation results.
40
 */
41
void
42
ospf_age(struct proto_ospf *po)
43
{
44
  struct proto *p = &po->proto;
45
  struct top_hash_entry *en, *nxt;
46
  int flush = can_flush_lsa(po);
47

    
48
  if (po->cleanup) OSPF_TRACE(D_EVENTS, "Running ospf_age cleanup");
49

    
50
  WALK_SLIST_DELSAFE(en, nxt, po->lsal)
51
  {
52
    if (po->cleanup)
53
    {
54
      en->color = OUTSPF;
55
      en->dist = LSINFINITY;
56
      en->nhi = NULL;
57
      en->nh = IPA_NONE;
58
      en->lb = IPA_NONE;
59
      DBG("Infinitying Type: %u, Id: %R, Rt: %R\n", en->lsa.type,
60
          en->lsa.id, en->lsa.rt);
61
    }
62
    if (en->lsa.age == LSA_MAXAGE)
63
    {
64
      if (flush)
65
        flush_lsa(en, po);
66
      continue;
67
    }
68
    if ((en->lsa.rt == po->router_id) && (en->lsa.age >= LSREFRESHTIME))
69
    {
70
      OSPF_TRACE(D_EVENTS, "Refreshing my LSA: Type: %u, Id: %R, Rt: %R",
71
                 en->lsa.type, en->lsa.id, en->lsa.rt);
72
      en->lsa.sn++;
73
      en->lsa.age = 0;
74
      en->inst_t = now;
75
      en->ini_age = 0;
76
      lsasum_calculate(&en->lsa, en->lsa_body);
77
      ospf_lsupd_flood(po, NULL, NULL, &en->lsa, en->domain, 1);
78
      continue;
79
    }
80
    if ((en->lsa.age = (en->ini_age + (now - en->inst_t))) >= LSA_MAXAGE)
81
    {
82
      if (flush)
83
      {
84
        flush_lsa(en, po);
85
        schedule_rtcalc(po);
86
      }
87
      else
88
        en->lsa.age = LSA_MAXAGE;
89
    }
90
  }
91
  po->cleanup = 0;
92
}
93

    
94
void
95
htonlsah(struct ospf_lsa_header *h, struct ospf_lsa_header *n)
96
{
97
  n->age = htons(h->age);
98
#ifdef OSPFv2
99
  n->options = h->options;
100
#endif
101
  n->type = htont(h->type);
102
  n->id = htonl(h->id);
103
  n->rt = htonl(h->rt);
104
  n->sn = htonl(h->sn);
105
  n->checksum = htons(h->checksum);
106
  n->length = htons(h->length);
107
}
108

    
109
void
110
ntohlsah(struct ospf_lsa_header *n, struct ospf_lsa_header *h)
111
{
112
  h->age = ntohs(n->age);
113
#ifdef OSPFv2
114
  h->options = n->options;
115
#endif
116
  h->type = ntoht(n->type);
117
  h->id = ntohl(n->id);
118
  h->rt = ntohl(n->rt);
119
  h->sn = ntohl(n->sn);
120
  h->checksum = ntohs(n->checksum);
121
  h->length = ntohs(n->length);
122
}
123

    
124
void
125
htonlsab(void *h, void *n, u16 len)
126
{
127
  u32 *hid = h;
128
  u32 *nid = n;
129
  unsigned i;
130

    
131
  for (i = 0; i < (len / sizeof(u32)); i++)
132
    nid[i] = htonl(hid[i]);
133
}
134

    
135
void
136
ntohlsab(void *n, void *h, u16 len)
137
{
138
  u32 *nid = n;
139
  u32 *hid = h;
140
  unsigned i;
141

    
142
  for (i = 0; i < (len / sizeof(u32)); i++)
143
    hid[i] = ntohl(nid[i]);
144
}
145

    
146
/*
147
void
148
buf_dump(const char *hdr, const byte *buf, int blen)
149
{
150
  char b2[1024];
151
  char *bp;
152
  int first = 1;
153
  int i;
154

155
  const char *lhdr = hdr;
156

157
  bp = b2;
158
  for(i = 0; i < blen; i++)
159
    {
160
      if ((i > 0) && ((i % 16) == 0))
161
        {
162
              *bp = 0;
163
              log(L_WARN "%s\t%s", lhdr, b2);
164
              lhdr = "";
165
              bp = b2;
166
        }
167

168
      bp += snprintf(bp, 1022, "%02x ", buf[i]);
169

170
    }
171

172
  *bp = 0;
173
  log(L_WARN "%s\t%s", lhdr, b2);
174
}
175
*/
176

    
177
#define MODX 4102                /* larges signed value without overflow */
178

    
179
/* Fletcher Checksum -- Refer to RFC1008. */
180
#define MODX                 4102
181
#define LSA_CHECKSUM_OFFSET    15
182

    
183
/* FIXME This is VERY uneficient, I have huge endianity problems */
184
void
185
lsasum_calculate(struct ospf_lsa_header *h, void *body)
186
{
187
  u16 length = h->length;
188

    
189
  //  log(L_WARN "Checksum %R %R %d start (len %d)", h->id, h->rt, h->type, length);
190
  htonlsah(h, h);
191
  htonlsab(body, body, length - sizeof(struct ospf_lsa_header));
192

    
193
  /*
194
  char buf[1024];
195
  memcpy(buf, h, sizeof(struct ospf_lsa_header));
196
  memcpy(buf + sizeof(struct ospf_lsa_header), body, length - sizeof(struct ospf_lsa_header));
197
  buf_dump("CALC", buf, length);
198
  */
199

    
200
  (void) lsasum_check(h, body);
201

    
202
  //  log(L_WARN "Checksum result %4x", h->checksum);
203

    
204
  ntohlsah(h, h);
205
  ntohlsab(body, body, length - sizeof(struct ospf_lsa_header));
206
}
207

    
208
/*
209
 * Note, that this function expects that LSA is in big endianity
210
 * It also returns value in big endian
211
 */
212
u16
213
lsasum_check(struct ospf_lsa_header *h, void *body)
214
{
215
  u8 *sp, *ep, *p, *q, *b;
216
  int c0 = 0, c1 = 0;
217
  int x, y;
218
  u16 length;
219

    
220
  b = body;
221
  sp = (char *) h;
222
  sp += 2; /* Skip Age field */
223
  length = ntohs(h->length) - 2;
224
  h->checksum = 0;
225

    
226
  for (ep = sp + length; sp < ep; sp = q)
227
  {                                /* Actually MODX is very large, do we need the for-cyclus? */
228
    q = sp + MODX;
229
    if (q > ep)
230
      q = ep;
231
    for (p = sp; p < q; p++)
232
    {
233
      /* 
234
       * I count with bytes from header and than from body
235
       * but if there is no body, it's appended to header
236
       * (probably checksum in update receiving) and I go on
237
       * after header
238
       */
239
      if ((b == NULL) || (p < (u8 *) (h + 1)))
240
      {
241
        c0 += *p;
242
      }
243
      else
244
      {
245
        c0 += *(b + (p - sp) - sizeof(struct ospf_lsa_header) + 2);
246
      }
247

    
248
      c1 += c0;
249
    }
250
    c0 %= 255;
251
    c1 %= 255;
252
  }
253

    
254
  x = ((length - LSA_CHECKSUM_OFFSET) * c0 - c1) % 255;
255
  if (x <= 0)
256
    x += 255;
257
  y = 510 - c0 - x;
258
  if (y > 255)
259
    y -= 255;
260

    
261
  ((u8 *) & h->checksum)[0] = x;
262
  ((u8 *) & h->checksum)[1] = y;
263
  return h->checksum;
264
}
265

    
266
int
267
lsa_comp(struct ospf_lsa_header *l1, struct ospf_lsa_header *l2)
268
                        /* Return codes from point of view of l1 */
269
{
270
  u32 sn1, sn2;
271

    
272
  sn1 = l1->sn - LSA_INITSEQNO + 1;
273
  sn2 = l2->sn - LSA_INITSEQNO + 1;
274

    
275
  if (sn1 > sn2)
276
    return CMP_NEWER;
277
  if (sn1 < sn2)
278
    return CMP_OLDER;
279

    
280
  if (l1->checksum != l2->checksum)
281
    return l1->checksum < l2->checksum ? CMP_OLDER : CMP_NEWER;
282

    
283
  if ((l1->age == LSA_MAXAGE) && (l2->age != LSA_MAXAGE))
284
    return CMP_NEWER;
285
  if ((l2->age == LSA_MAXAGE) && (l1->age != LSA_MAXAGE))
286
    return CMP_OLDER;
287

    
288
  if (ABS(l1->age - l2->age) > LSA_MAXAGEDIFF)
289
    return l1->age < l2->age ? CMP_NEWER : CMP_OLDER;
290

    
291
  return CMP_SAME;
292
}
293

    
294
#define HDRLEN sizeof(struct ospf_lsa_header)
295

    
296
static int
297
lsa_validate_rt(struct ospf_lsa_header *lsa, struct ospf_lsa_rt *body)
298
{
299
  unsigned int i, max;
300

    
301
  if (lsa->length < (HDRLEN + sizeof(struct ospf_lsa_rt)))
302
    return 0;
303

    
304
  struct ospf_lsa_rt_link *rtl = (struct ospf_lsa_rt_link *) (body + 1);
305
  max = lsa_rt_count(lsa);
306

    
307
#ifdef OSPFv2
308
  if (body->links != max)
309
    return 0;
310
#endif  
311

    
312
  for (i = 0; i < max; i++)
313
  {
314
    u8 type = rtl[i].type;
315
    if (!((type == LSART_PTP) ||
316
          (type == LSART_NET) ||
317
#ifdef OSPFv2
318
          (type == LSART_STUB) ||
319
#endif
320
          (type == LSART_VLNK)))
321
      return 0;
322
  }
323
  return 1;
324
}
325

    
326
static int
327
lsa_validate_net(struct ospf_lsa_header *lsa, struct ospf_lsa_net *body UNUSED)
328
{
329
  if (lsa->length < (HDRLEN + sizeof(struct ospf_lsa_net)))
330
    return 0;
331

    
332
  return 1;
333
}
334

    
335
#ifdef OSPFv2
336

    
337
static int
338
lsa_validate_sum(struct ospf_lsa_header *lsa, struct ospf_lsa_sum *body)
339
{
340
  if (lsa->length < (HDRLEN + sizeof(struct ospf_lsa_sum)))
341
    return 0;
342

    
343
  /* First field should have TOS = 0, we ignore other TOS fields */
344
  if ((body->metric & LSA_SUM_TOS) != 0)
345
    return 0;
346

    
347
  return 1;
348
}
349
#define lsa_validate_sum_net(A,B) lsa_validate_sum(A,B)
350
#define lsa_validate_sum_rt(A,B)  lsa_validate_sum(A,B)
351

    
352
static int
353
lsa_validate_ext(struct ospf_lsa_header *lsa, struct ospf_lsa_ext *body)
354
{
355
  if (lsa->length < (HDRLEN + sizeof(struct ospf_lsa_ext)))
356
    return 0;
357

    
358
  /* First field should have TOS = 0, we ignore other TOS fields */
359
  if ((body->metric & LSA_EXT_TOS) != 0)
360
    return 0;
361

    
362
  return 1;
363
}
364

    
365
#else /* OSPFv3 */
366

    
367
static inline int
368
pxlen(u32 *buf)
369
{
370
  return *buf >> 24;
371
}
372

    
373
static int
374
lsa_validate_sum_net(struct ospf_lsa_header *lsa, struct ospf_lsa_sum_net *body)
375
{
376
  if (lsa->length < (HDRLEN + sizeof(struct ospf_lsa_sum_net) + 4))
377
    return 0;
378

    
379
  u8 pxl = pxlen(body->prefix);
380
  if (pxl > MAX_PREFIX_LENGTH)
381
    return 0;
382

    
383
  if (lsa->length != (HDRLEN + sizeof(struct ospf_lsa_sum_net) + 
384
                      IPV6_PREFIX_SPACE(pxl)))
385
    return 0;
386

    
387
  return 1;
388
}
389

    
390

    
391
static int
392
lsa_validate_sum_rt(struct ospf_lsa_header *lsa, struct ospf_lsa_sum_rt *body)
393
{
394
  if (lsa->length != (HDRLEN + sizeof(struct ospf_lsa_sum_rt)))
395
    return 0;
396

    
397
  return 1;
398
}
399

    
400
static int
401
lsa_validate_ext(struct ospf_lsa_header *lsa, struct ospf_lsa_ext *body)
402
{
403
  if (lsa->length < (HDRLEN + sizeof(struct ospf_lsa_ext) + 4))
404
    return 0;
405

    
406
  u8 pxl = pxlen(body->rest);
407
  if (pxl > MAX_PREFIX_LENGTH)
408
    return 0;
409

    
410
  int len = IPV6_PREFIX_SPACE(pxl);
411
  if (body->metric & LSA_EXT_FBIT) // forwardinf address
412
    len += 16;
413
  if (body->metric & LSA_EXT_TBIT) // route tag
414
    len += 4;
415
  if (*body->rest & 0xFFFF) // referenced LS type field
416
    len += 4;
417

    
418
  if (lsa->length != (HDRLEN + sizeof(struct ospf_lsa_ext) + len))
419
    return 0;
420

    
421
  return 1;
422
}
423

    
424
static int
425
lsa_validate_pxlist(struct ospf_lsa_header *lsa, u32 pxcount, unsigned int offset, u8 *pbuf)
426
{
427
  unsigned int bound = lsa->length - HDRLEN - 4;
428
  u32 i;
429

    
430
  for (i = 0; i < pxcount; i++)
431
    {
432
      if (offset > bound)
433
        return 0;
434

    
435
      u8 pxl = pxlen((u32 *) (pbuf + offset));
436
      if (pxl > MAX_PREFIX_LENGTH)
437
        return 0;
438
  
439
      offset += IPV6_PREFIX_SPACE(pxl);
440
    }
441

    
442
  if (lsa->length != (HDRLEN + offset))
443
    return 0;
444

    
445
  return 1;
446
}
447

    
448
static int
449
lsa_validate_link(struct ospf_lsa_header *lsa, struct ospf_lsa_link *body)
450
{
451
  if (lsa->length < (HDRLEN + sizeof(struct ospf_lsa_link)))
452
    return 0;
453

    
454
  return lsa_validate_pxlist(lsa, body->pxcount, sizeof(struct ospf_lsa_link), (u8 *) body);
455
}
456

    
457
static int
458
lsa_validate_prefix(struct ospf_lsa_header *lsa, struct ospf_lsa_prefix *body)
459
{
460
  if (lsa->length < (HDRLEN + sizeof(struct ospf_lsa_prefix)))
461
    return 0;
462

    
463
  return lsa_validate_pxlist(lsa, body->pxcount, sizeof(struct ospf_lsa_prefix), (u8 *) body);
464
}
465

    
466
#endif
467

    
468

    
469
/**
470
 * lsa_validate - check whether given LSA is valid
471
 * @lsa: LSA header
472
 * @body: pointer to LSA body
473
 *
474
 * Checks internal structure of given LSA body (minimal length,
475
 * consistency). Returns true if valid.
476
 */
477

    
478
int
479
lsa_validate(struct ospf_lsa_header *lsa, void *body)
480
{
481
  switch (lsa->type)
482
    {
483
    case LSA_T_RT:
484
      return lsa_validate_rt(lsa, body);
485
    case LSA_T_NET:
486
      return lsa_validate_net(lsa, body);
487
    case LSA_T_SUM_NET:
488
      return lsa_validate_sum_net(lsa, body);
489
    case LSA_T_SUM_RT:
490
      return lsa_validate_sum_rt(lsa, body);
491
    case LSA_T_EXT:
492
      return lsa_validate_ext(lsa, body);
493
#ifdef OSPFv3
494
    case LSA_T_LINK:
495
      return lsa_validate_link(lsa, body);
496
    case LSA_T_PREFIX:
497
      return lsa_validate_prefix(lsa, body);
498
#endif
499
    default:
500
      /* In OSPFv3, unknown LSAs are OK,
501
         In OSPFv2, unknown LSAs are already rejected
502
      */
503
      return 1;
504
    }
505
}
506

    
507
/**
508
 * lsa_install_new - install new LSA into database
509
 * @po: OSPF protocol
510
 * @lsa: LSA header
511
 * @domain: domain of LSA
512
 * @body: pointer to LSA body
513

514
 *
515
 * This function ensures installing new LSA into LSA database. Old instance is
516
 * replaced. Several actions are taken to detect if new routing table
517
 * calculation is necessary. This is described in 13.2 of RFC 2328.
518
 */
519
struct top_hash_entry *
520
lsa_install_new(struct proto_ospf *po, struct ospf_lsa_header *lsa, u32 domain, void *body)
521
{
522
  /* LSA can be temporarrily, but body must be mb_allocated. */
523
  int change = 0;
524
  struct top_hash_entry *en;
525

    
526
  if ((en = ospf_hash_find_header(po->gr, domain, lsa)) == NULL)
527
  {
528
    en = ospf_hash_get_header(po->gr, domain, lsa);
529
    change = 1;
530
  }
531
  else
532
  {
533
    if ((en->lsa.length != lsa->length)
534
#ifdef OSPFv2       
535
        || (en->lsa.options != lsa->options)
536
#endif
537
        || (en->lsa.age == LSA_MAXAGE)
538
        || (lsa->age == LSA_MAXAGE)
539
        || memcmp(en->lsa_body, body, lsa->length - sizeof(struct ospf_lsa_header)))
540
      change = 1;
541

    
542
    s_rem_node(SNODE en);
543
  }
544

    
545
  DBG("Inst lsa: Id: %R, Rt: %R, Type: %u, Age: %u, Sum: %u, Sn: 0x%x\n",
546
      lsa->id, lsa->rt, lsa->type, lsa->age, lsa->checksum, lsa->sn);
547

    
548
  s_add_tail(&po->lsal, SNODE en);
549
  en->inst_t = now;
550
  if (en->lsa_body != NULL)
551
    mb_free(en->lsa_body);
552
  en->lsa_body = body;
553
  memcpy(&en->lsa, lsa, sizeof(struct ospf_lsa_header));
554
  en->ini_age = en->lsa.age;
555

    
556
  if (change)
557
    schedule_rtcalc(po);
558

    
559
  return en;
560
}