Statistics
| Branch: | Revision:

iof-bird-daemon / proto / ospf / lsalib.c @ 506fa1a7

History | View | Annotate | Download (12.2 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
  WALK_SLIST_DELSAFE(en, nxt, po->lsal)
49
  {
50
    if (en->lsa.age == LSA_MAXAGE)
51
    {
52
      if (flush)
53
        flush_lsa(en, po);
54
      continue;
55
    }
56
    if ((en->lsa.rt == po->router_id) && (en->lsa.age >= LSREFRESHTIME))
57
    {
58
      OSPF_TRACE(D_EVENTS, "Refreshing my LSA: Type: %u, Id: %R, Rt: %R",
59
                 en->lsa.type, en->lsa.id, en->lsa.rt);
60
      en->lsa.sn++;
61
      en->lsa.age = 0;
62
      en->inst_t = now;
63
      en->ini_age = 0;
64
      lsasum_calculate(&en->lsa, en->lsa_body);
65
      ospf_lsupd_flood(po, NULL, NULL, &en->lsa, en->domain, 1);
66
      continue;
67
    }
68
    if ((en->lsa.age = (en->ini_age + (now - en->inst_t))) >= LSA_MAXAGE)
69
    {
70
      if (flush)
71
      {
72
        flush_lsa(en, po);
73
        schedule_rtcalc(po);
74
      }
75
      else
76
        en->lsa.age = LSA_MAXAGE;
77
    }
78
  }
79
}
80

    
81
#ifndef CPU_BIG_ENDIAN
82
void
83
htonlsah(struct ospf_lsa_header *h, struct ospf_lsa_header *n)
84
{
85
  n->age = htons(h->age);
86
#ifdef OSPFv2
87
  n->options = h->options;
88
#endif
89
  n->type = htont(h->type);
90
  n->id = htonl(h->id);
91
  n->rt = htonl(h->rt);
92
  n->sn = htonl(h->sn);
93
  n->checksum = htons(h->checksum);
94
  n->length = htons(h->length);
95
}
96

    
97
void
98
ntohlsah(struct ospf_lsa_header *n, struct ospf_lsa_header *h)
99
{
100
  h->age = ntohs(n->age);
101
#ifdef OSPFv2
102
  h->options = n->options;
103
#endif
104
  h->type = ntoht(n->type);
105
  h->id = ntohl(n->id);
106
  h->rt = ntohl(n->rt);
107
  h->sn = ntohl(n->sn);
108
  h->checksum = ntohs(n->checksum);
109
  h->length = ntohs(n->length);
110
}
111

    
112
void
113
htonlsab(void *h, void *n, u16 len)
114
{
115
  u32 *hid = h;
116
  u32 *nid = n;
117
  unsigned i;
118

    
119
  for (i = 0; i < (len / sizeof(u32)); i++)
120
    nid[i] = htonl(hid[i]);
121
}
122

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

    
130
  for (i = 0; i < (len / sizeof(u32)); i++)
131
    hid[i] = ntohl(nid[i]);
132
}
133
#endif /* little endian */
134

    
135
/*
136
void
137
buf_dump(const char *hdr, const byte *buf, int blen)
138
{
139
  char b2[1024];
140
  char *bp;
141
  int first = 1;
142
  int i;
143

144
  const char *lhdr = hdr;
145

146
  bp = b2;
147
  for(i = 0; i < blen; i++)
148
    {
149
      if ((i > 0) && ((i % 16) == 0))
150
        {
151
              *bp = 0;
152
              log(L_WARN "%s\t%s", lhdr, b2);
153
              lhdr = "";
154
              bp = b2;
155
        }
156

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

159
    }
160

161
  *bp = 0;
162
  log(L_WARN "%s\t%s", lhdr, b2);
163
}
164
*/
165

    
166
#define MODX 4102                /* larges signed value without overflow */
167

    
168
/* Fletcher Checksum -- Refer to RFC1008. */
169
#define MODX                 4102
170
#define LSA_CHECKSUM_OFFSET    15
171

    
172
/* FIXME This is VERY uneficient, I have huge endianity problems */
173
void
174
lsasum_calculate(struct ospf_lsa_header *h, void *body)
175
{
176
  u16 length = h->length;
177

    
178
  //  log(L_WARN "Checksum %R %R %d start (len %d)", h->id, h->rt, h->type, length);
179
  htonlsah(h, h);
180
  htonlsab1(body, length - sizeof(struct ospf_lsa_header));
181

    
182
  /*
183
  char buf[1024];
184
  memcpy(buf, h, sizeof(struct ospf_lsa_header));
185
  memcpy(buf + sizeof(struct ospf_lsa_header), body, length - sizeof(struct ospf_lsa_header));
186
  buf_dump("CALC", buf, length);
187
  */
188

    
189
  (void) lsasum_check(h, body);
190

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

    
193
  ntohlsah(h, h);
194
  ntohlsab1(body, length - sizeof(struct ospf_lsa_header));
195
}
196

    
197
/*
198
 * Note, that this function expects that LSA is in big endianity
199
 * It also returns value in big endian
200
 */
201
u16
202
lsasum_check(struct ospf_lsa_header *h, void *body)
203
{
204
  u8 *sp, *ep, *p, *q, *b;
205
  int c0 = 0, c1 = 0;
206
  int x, y;
207
  u16 length;
208

    
209
  b = body;
210
  sp = (char *) h;
211
  sp += 2; /* Skip Age field */
212
  length = ntohs(h->length) - 2;
213
  h->checksum = 0;
214

    
215
  for (ep = sp + length; sp < ep; sp = q)
216
  {                                /* Actually MODX is very large, do we need the for-cyclus? */
217
    q = sp + MODX;
218
    if (q > ep)
219
      q = ep;
220
    for (p = sp; p < q; p++)
221
    {
222
      /* 
223
       * I count with bytes from header and than from body
224
       * but if there is no body, it's appended to header
225
       * (probably checksum in update receiving) and I go on
226
       * after header
227
       */
228
      if ((b == NULL) || (p < (u8 *) (h + 1)))
229
      {
230
        c0 += *p;
231
      }
232
      else
233
      {
234
        c0 += *(b + (p - sp) - sizeof(struct ospf_lsa_header) + 2);
235
      }
236

    
237
      c1 += c0;
238
    }
239
    c0 %= 255;
240
    c1 %= 255;
241
  }
242

    
243
  x = (int)((length - LSA_CHECKSUM_OFFSET) * c0 - c1) % 255;
244
  if (x <= 0)
245
    x += 255;
246
  y = 510 - c0 - x;
247
  if (y > 255)
248
    y -= 255;
249

    
250
  ((u8 *) & h->checksum)[0] = x;
251
  ((u8 *) & h->checksum)[1] = y;
252
  return h->checksum;
253
}
254

    
255
int
256
lsa_comp(struct ospf_lsa_header *l1, struct ospf_lsa_header *l2)
257
                        /* Return codes from point of view of l1 */
258
{
259
  u32 sn1, sn2;
260

    
261
  sn1 = l1->sn - LSA_INITSEQNO + 1;
262
  sn2 = l2->sn - LSA_INITSEQNO + 1;
263

    
264
  if (sn1 > sn2)
265
    return CMP_NEWER;
266
  if (sn1 < sn2)
267
    return CMP_OLDER;
268

    
269
  if (l1->checksum != l2->checksum)
270
    return l1->checksum < l2->checksum ? CMP_OLDER : CMP_NEWER;
271

    
272
  if ((l1->age == LSA_MAXAGE) && (l2->age != LSA_MAXAGE))
273
    return CMP_NEWER;
274
  if ((l2->age == LSA_MAXAGE) && (l1->age != LSA_MAXAGE))
275
    return CMP_OLDER;
276

    
277
  if (ABS(l1->age - l2->age) > LSA_MAXAGEDIFF)
278
    return l1->age < l2->age ? CMP_NEWER : CMP_OLDER;
279

    
280
  return CMP_SAME;
281
}
282

    
283
#define HDRLEN sizeof(struct ospf_lsa_header)
284

    
285
static int
286
lsa_validate_rt(struct ospf_lsa_header *lsa, struct ospf_lsa_rt *body)
287
{
288
  unsigned int i, max;
289

    
290
  if (lsa->length < (HDRLEN + sizeof(struct ospf_lsa_rt)))
291
    return 0;
292

    
293
  struct ospf_lsa_rt_link *rtl = (struct ospf_lsa_rt_link *) (body + 1);
294
  max = lsa_rt_count(lsa);
295

    
296
#ifdef OSPFv2
297
  if (body->links != max)
298
    return 0;
299
#endif  
300

    
301
  for (i = 0; i < max; i++)
302
  {
303
    u8 type = rtl[i].type;
304
    if (!((type == LSART_PTP) ||
305
          (type == LSART_NET) ||
306
#ifdef OSPFv2
307
          (type == LSART_STUB) ||
308
#endif
309
          (type == LSART_VLNK)))
310
      return 0;
311
  }
312
  return 1;
313
}
314

    
315
static int
316
lsa_validate_net(struct ospf_lsa_header *lsa, struct ospf_lsa_net *body UNUSED)
317
{
318
  if (lsa->length < (HDRLEN + sizeof(struct ospf_lsa_net)))
319
    return 0;
320

    
321
  return 1;
322
}
323

    
324
#ifdef OSPFv2
325

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

    
332
  /* First field should have TOS = 0, we ignore other TOS fields */
333
  if ((body->metric & LSA_SUM_TOS) != 0)
334
    return 0;
335

    
336
  return 1;
337
}
338
#define lsa_validate_sum_net(A,B) lsa_validate_sum(A,B)
339
#define lsa_validate_sum_rt(A,B)  lsa_validate_sum(A,B)
340

    
341
static int
342
lsa_validate_ext(struct ospf_lsa_header *lsa, struct ospf_lsa_ext *body)
343
{
344
  if (lsa->length < (HDRLEN + sizeof(struct ospf_lsa_ext)))
345
    return 0;
346

    
347
  /* First field should have TOS = 0, we ignore other TOS fields */
348
  if ((body->metric & LSA_EXT_TOS) != 0)
349
    return 0;
350

    
351
  return 1;
352
}
353

    
354
#else /* OSPFv3 */
355

    
356
static inline int
357
pxlen(u32 *buf)
358
{
359
  return *buf >> 24;
360
}
361

    
362
static int
363
lsa_validate_sum_net(struct ospf_lsa_header *lsa, struct ospf_lsa_sum_net *body)
364
{
365
  if (lsa->length < (HDRLEN + sizeof(struct ospf_lsa_sum_net) + 4))
366
    return 0;
367

    
368
  u8 pxl = pxlen(body->prefix);
369
  if (pxl > MAX_PREFIX_LENGTH)
370
    return 0;
371

    
372
  if (lsa->length != (HDRLEN + sizeof(struct ospf_lsa_sum_net) + 
373
                      IPV6_PREFIX_SPACE(pxl)))
374
    return 0;
375

    
376
  return 1;
377
}
378

    
379

    
380
static int
381
lsa_validate_sum_rt(struct ospf_lsa_header *lsa, struct ospf_lsa_sum_rt *body)
382
{
383
  if (lsa->length != (HDRLEN + sizeof(struct ospf_lsa_sum_rt)))
384
    return 0;
385

    
386
  return 1;
387
}
388

    
389
static int
390
lsa_validate_ext(struct ospf_lsa_header *lsa, struct ospf_lsa_ext *body)
391
{
392
  if (lsa->length < (HDRLEN + sizeof(struct ospf_lsa_ext) + 4))
393
    return 0;
394

    
395
  u8 pxl = pxlen(body->rest);
396
  if (pxl > MAX_PREFIX_LENGTH)
397
    return 0;
398

    
399
  int len = IPV6_PREFIX_SPACE(pxl);
400
  if (body->metric & LSA_EXT_FBIT) // forwardinf address
401
    len += 16;
402
  if (body->metric & LSA_EXT_TBIT) // route tag
403
    len += 4;
404
  if (*body->rest & 0xFFFF) // referenced LS type field
405
    len += 4;
406

    
407
  if (lsa->length != (HDRLEN + sizeof(struct ospf_lsa_ext) + len))
408
    return 0;
409

    
410
  return 1;
411
}
412

    
413
static int
414
lsa_validate_pxlist(struct ospf_lsa_header *lsa, u32 pxcount, unsigned int offset, u8 *pbuf)
415
{
416
  unsigned int bound = lsa->length - HDRLEN - 4;
417
  u32 i;
418

    
419
  for (i = 0; i < pxcount; i++)
420
    {
421
      if (offset > bound)
422
        return 0;
423

    
424
      u8 pxl = pxlen((u32 *) (pbuf + offset));
425
      if (pxl > MAX_PREFIX_LENGTH)
426
        return 0;
427
  
428
      offset += IPV6_PREFIX_SPACE(pxl);
429
    }
430

    
431
  if (lsa->length != (HDRLEN + offset))
432
    return 0;
433

    
434
  return 1;
435
}
436

    
437
static int
438
lsa_validate_link(struct ospf_lsa_header *lsa, struct ospf_lsa_link *body)
439
{
440
  if (lsa->length < (HDRLEN + sizeof(struct ospf_lsa_link)))
441
    return 0;
442

    
443
  return lsa_validate_pxlist(lsa, body->pxcount, sizeof(struct ospf_lsa_link), (u8 *) body);
444
}
445

    
446
static int
447
lsa_validate_prefix(struct ospf_lsa_header *lsa, struct ospf_lsa_prefix *body)
448
{
449
  if (lsa->length < (HDRLEN + sizeof(struct ospf_lsa_prefix)))
450
    return 0;
451

    
452
  return lsa_validate_pxlist(lsa, body->pxcount, sizeof(struct ospf_lsa_prefix), (u8 *) body);
453
}
454

    
455
#endif
456

    
457

    
458
/**
459
 * lsa_validate - check whether given LSA is valid
460
 * @lsa: LSA header
461
 * @body: pointer to LSA body
462
 *
463
 * Checks internal structure of given LSA body (minimal length,
464
 * consistency). Returns true if valid.
465
 */
466

    
467
int
468
lsa_validate(struct ospf_lsa_header *lsa, void *body)
469
{
470
  switch (lsa->type)
471
    {
472
    case LSA_T_RT:
473
      return lsa_validate_rt(lsa, body);
474
    case LSA_T_NET:
475
      return lsa_validate_net(lsa, body);
476
    case LSA_T_SUM_NET:
477
      return lsa_validate_sum_net(lsa, body);
478
    case LSA_T_SUM_RT:
479
      return lsa_validate_sum_rt(lsa, body);
480
    case LSA_T_EXT:
481
      return lsa_validate_ext(lsa, body);
482
#ifdef OSPFv3
483
    case LSA_T_LINK:
484
      return lsa_validate_link(lsa, body);
485
    case LSA_T_PREFIX:
486
      return lsa_validate_prefix(lsa, body);
487
#endif
488
    default:
489
      /* In OSPFv3, unknown LSAs are OK,
490
         In OSPFv2, unknown LSAs are already rejected
491
      */
492
      return 1;
493
    }
494
}
495

    
496
/**
497
 * lsa_install_new - install new LSA into database
498
 * @po: OSPF protocol
499
 * @lsa: LSA header
500
 * @domain: domain of LSA
501
 * @body: pointer to LSA body
502

503
 *
504
 * This function ensures installing new LSA into LSA database. Old instance is
505
 * replaced. Several actions are taken to detect if new routing table
506
 * calculation is necessary. This is described in 13.2 of RFC 2328.
507
 */
508
struct top_hash_entry *
509
lsa_install_new(struct proto_ospf *po, struct ospf_lsa_header *lsa, u32 domain, void *body)
510
{
511
  /* LSA can be temporarrily, but body must be mb_allocated. */
512
  int change = 0;
513
  struct top_hash_entry *en;
514

    
515
  if ((en = ospf_hash_find_header(po->gr, domain, lsa)) == NULL)
516
  {
517
    en = ospf_hash_get_header(po->gr, domain, lsa);
518
    change = 1;
519
  }
520
  else
521
  {
522
    if ((en->lsa.length != lsa->length)
523
#ifdef OSPFv2       
524
        || (en->lsa.options != lsa->options)
525
#endif
526
        || (en->lsa.age == LSA_MAXAGE)
527
        || (lsa->age == LSA_MAXAGE)
528
        || memcmp(en->lsa_body, body, lsa->length - sizeof(struct ospf_lsa_header)))
529
      change = 1;
530

    
531
    s_rem_node(SNODE en);
532
  }
533

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

    
537
  s_add_tail(&po->lsal, SNODE en);
538
  en->inst_t = now;
539
  if (en->lsa_body != NULL)
540
    mb_free(en->lsa_body);
541
  en->lsa_body = body;
542
  memcpy(&en->lsa, lsa, sizeof(struct ospf_lsa_header));
543
  en->ini_age = en->lsa.age;
544

    
545
  if (change)
546
    schedule_rtcalc(po);
547

    
548
  return en;
549
}