Statistics
| Branch: | Revision:

iof-bird-daemon / proto / ospf / lsalib.c @ 061ab802

History | View | Annotate | Download (10.5 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 node Type: %u, Id: %R, Rt: %R, Age: %u, SN: 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 == p->cf->global->router_id) &&
69
        (en->lsa.age >= LSREFRESHTIME))
70
    {
71
      OSPF_TRACE(D_EVENTS, "Refreshing my LSA: Type: %u, Id: %R, Rt: %R",
72
                 en->lsa.type, en->lsa.id, en->lsa.rt);
73
      en->lsa.sn++;
74
      en->lsa.age = 0;
75
      en->inst_t = now;
76
      en->ini_age = 0;
77
      lsasum_calculate(&en->lsa, en->lsa_body);
78
      ospf_lsupd_flood(po, NULL, NULL, &en->lsa, en->domain, 1);
79
      continue;
80
    }
81
    if ((en->lsa.age = (en->ini_age + (now - en->inst_t))) >= LSA_MAXAGE)
82
    {
83
      if (flush)
84
      {
85
        flush_lsa(en, po);
86
        schedule_rtcalc(po);
87
      }
88
      else
89
        en->lsa.age = LSA_MAXAGE;
90
    }
91
  }
92
  po->cleanup = 0;
93
}
94

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

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

    
125
void
126
htonlsab(void *h, void *n, u16 type, u16 len)
127
{
128
  unsigned int i;
129
  switch (type)
130
  {
131
  case LSA_T_RT:
132
    {
133
      struct ospf_lsa_rt *hrt, *nrt;
134
      struct ospf_lsa_rt_link *hrtl, *nrtl;
135
      u16 links;
136

    
137
      nrt = n;
138
      hrt = h;
139

    
140
#ifdef OSPFv2
141
      nrt->veb.byte = hrt->veb.byte;
142
      nrt->padding = 0;
143
      nrt->links = htons(hrt->links);
144
      links = hrt->links;
145
#else /* OSPFv3 */
146
      nrt->options = htonl(hrt->options);
147
      links = (len - sizeof(struct ospf_lsa_rt)) /
148
        sizeof(struct ospf_lsa_rt_link);
149
#endif
150

    
151
      nrtl = (struct ospf_lsa_rt_link *) (nrt + 1);
152
      hrtl = (struct ospf_lsa_rt_link *) (hrt + 1);
153
      for (i = 0; i < links; i++)
154
      {
155
#ifdef OSPFv2
156
        nrtl[i].id = htonl(hrtl[i].id);
157
        nrtl[i].data = htonl(hrtl[i].data);
158
        nrtl[i].type = hrtl[i].type;
159
        nrtl[i].notos = hrtl[i].notos;
160
        nrtl[i].metric = htons(hrtl[i].metric);
161
#else /* OSPFv3 */
162
        nrtl[i].type = hrtl[i].type;
163
        nrtl[i].padding = 0;
164
        nrtl[i].metric = htons(hrtl[i].metric);
165
        nrtl[i].lif = htonl(hrtl[i].lif);
166
        nrtl[i].nif = htonl(hrtl[i].nif);
167
        nrtl[i].id = htonl(hrtl[i].id);
168
#endif
169
      }
170
      break;
171
    }
172
  case LSA_T_NET:
173
  case LSA_T_SUM_NET:
174
  case LSA_T_SUM_RT:
175
  case LSA_T_EXT:
176
#ifdef OSPFv3
177
  case LSA_T_LINK:
178
  case LSA_T_PREFIX:
179
#endif
180
    {
181
      u32 *hid, *nid;
182

    
183
      nid = n;
184
      hid = h;
185

    
186
      for (i = 0; i < (len / sizeof(u32)); i++)
187
      {
188
        *(nid + i) = htonl(*(hid + i));
189
      }
190
      break;
191
    }
192

    
193
  default:
194
    bug("(hton): Unknown LSA");
195
  }
196
};
197

    
198
void
199
ntohlsab(void *n, void *h, u16 type, u16 len)
200
{
201
  unsigned int i;
202
  switch (type)
203
  {
204
  case LSA_T_RT:
205
    {
206
      struct ospf_lsa_rt *hrt, *nrt;
207
      struct ospf_lsa_rt_link *hrtl, *nrtl;
208
      u16 links;
209

    
210
      nrt = n;
211
      hrt = h;
212

    
213
#ifdef OSPFv2
214
      hrt->veb.byte = nrt->veb.byte;
215
      hrt->padding = 0;
216
      links = hrt->links = ntohs(nrt->links);
217
#else /* OSPFv3 */
218
      hrt->options = ntohl(nrt->options);
219
      links = (len - sizeof(struct ospf_lsa_rt)) /
220
        sizeof(struct ospf_lsa_rt_link);
221
#endif
222

    
223
      nrtl = (struct ospf_lsa_rt_link *) (nrt + 1);
224
      hrtl = (struct ospf_lsa_rt_link *) (hrt + 1);
225
      for (i = 0; i < links; i++)
226
      {
227
#ifdef OSPFv2
228
        hrtl[i].id = ntohl(nrtl[i].id);
229
        hrtl[i].data = ntohl(nrtl[i].data);
230
        hrtl[i].type = nrtl[i].type;
231
        hrtl[i].notos = nrtl[i].notos;
232
        hrtl[i].metric = ntohs(nrtl[i].metric);
233
#else /* OSPFv3 */
234
        hrtl[i].type = nrtl[i].type;
235
        hrtl[i].padding = 0;
236
        hrtl[i].metric = ntohs(nrtl[i].metric);
237
        hrtl[i].lif = ntohl(nrtl[i].lif);
238
        hrtl[i].nif = ntohl(nrtl[i].nif);
239
        hrtl[i].id = ntohl(nrtl[i].id);
240
#endif
241
      }
242
      break;
243
    }
244
  case LSA_T_NET:
245
  case LSA_T_SUM_NET:
246
  case LSA_T_SUM_RT:
247
  case LSA_T_EXT:
248
#ifdef OSPFv3
249
  case LSA_T_LINK:
250
  case LSA_T_PREFIX:
251
#endif
252
    {
253
      u32 *hid, *nid;
254

    
255
      hid = h;
256
      nid = n;
257

    
258
      for (i = 0; i < (len / sizeof(u32)); i++)
259
      {
260
        hid[i] = ntohl(nid[i]);
261
      }
262
      break;
263
    }
264
  default:
265
    bug("(ntoh): Unknown LSA");
266
  }
267
};
268

    
269
void
270
buf_dump(const char *hdr, const byte *buf, int blen)
271
{
272
  char b2[1024];
273
  char *bp;
274
  int first = 1;
275
  int i;
276

    
277
  const char *lhdr = hdr;
278

    
279
  bp = b2;
280
  for(i = 0; i < blen; i++)
281
    {
282
      if ((i > 0) && ((i % 16) == 0))
283
        {
284
              *bp = 0;
285
              log(L_WARN "%s\t%s", lhdr, b2);
286
              lhdr = "";
287
              bp = b2;
288
        }
289

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

    
292
    }
293

    
294
  *bp = 0;
295
  log(L_WARN "%s\t%s", lhdr, b2);
296
}
297

    
298
#define MODX 4102                /* larges signed value without overflow */
299

    
300
/* Fletcher Checksum -- Refer to RFC1008. */
301
#define MODX                 4102
302
#define LSA_CHECKSUM_OFFSET    15
303

    
304
/* FIXME This is VERY uneficient, I have huge endianity problems */
305
void
306
lsasum_calculate(struct ospf_lsa_header *h, void *body)
307
{
308
  u16 length = h->length;
309
  u16 type = h->type;
310

    
311
  log(L_WARN "Checksum %R %R %d start (len %d)", h->id, h->rt, h->type, length);
312
  htonlsah(h, h);
313

    
314
  htonlsab(body, body, type, length - sizeof(struct ospf_lsa_header));
315

    
316
  char buf[1024];
317
  memcpy(buf, h, sizeof(struct ospf_lsa_header));
318
  memcpy(buf + sizeof(struct ospf_lsa_header), body, length - sizeof(struct ospf_lsa_header));
319
  buf_dump("CALC", buf, length);
320

    
321
  (void) lsasum_check(h, body);
322

    
323
  log(L_WARN "Checksum result %4x", h->checksum);
324

    
325
  ntohlsah(h, h);
326
  ntohlsab(body, body, type, length - sizeof(struct ospf_lsa_header));
327
}
328

    
329
/*
330
 * Note, that this function expects that LSA is in big endianity
331
 * It also returns value in big endian
332
 */
333
u16
334
lsasum_check(struct ospf_lsa_header *h, void *body)
335
{
336
  u8 *sp, *ep, *p, *q, *b;
337
  int c0 = 0, c1 = 0;
338
  int x, y;
339
  u16 length;
340

    
341
  b = body;
342
  sp = (char *) h;
343
  sp += 2; /* Skip Age field */
344
  length = ntohs(h->length) - 2;
345
  h->checksum = 0;
346

    
347
  for (ep = sp + length; sp < ep; sp = q)
348
  {                                /* Actually MODX is very large, do we need the for-cyclus? */
349
    q = sp + MODX;
350
    if (q > ep)
351
      q = ep;
352
    for (p = sp; p < q; p++)
353
    {
354
      /* 
355
       * I count with bytes from header and than from body
356
       * but if there is no body, it's appended to header
357
       * (probably checksum in update receiving) and I go on
358
       * after header
359
       */
360
      if ((b == NULL) || (p < (u8 *) (h + 1)))
361
      {
362
        c0 += *p;
363
      }
364
      else
365
      {
366
        c0 += *(b + (p - sp) - sizeof(struct ospf_lsa_header) + 2);
367
      }
368

    
369
      c1 += c0;
370
    }
371
    c0 %= 255;
372
    c1 %= 255;
373
  }
374

    
375
  x = ((length - LSA_CHECKSUM_OFFSET) * c0 - c1) % 255;
376
  if (x <= 0)
377
    x += 255;
378
  y = 510 - c0 - x;
379
  if (y > 255)
380
    y -= 255;
381

    
382
  ((u8 *) & h->checksum)[0] = x;
383
  ((u8 *) & h->checksum)[1] = y;
384
  return h->checksum;
385
}
386

    
387
int
388
lsa_comp(struct ospf_lsa_header *l1, struct ospf_lsa_header *l2)
389
                        /* Return codes from point of view of l1 */
390
{
391
  u32 sn1, sn2;
392

    
393
  sn1 = l1->sn - LSA_INITSEQNO + 1;
394
  sn2 = l2->sn - LSA_INITSEQNO + 1;
395

    
396
  if (sn1 > sn2)
397
    return CMP_NEWER;
398
  if (sn1 < sn2)
399
    return CMP_OLDER;
400

    
401
  if (l1->checksum != l2->checksum)
402
    return l1->checksum < l2->checksum ? CMP_OLDER : CMP_NEWER;
403

    
404
  if ((l1->age == LSA_MAXAGE) && (l2->age != LSA_MAXAGE))
405
    return CMP_NEWER;
406
  if ((l2->age == LSA_MAXAGE) && (l1->age != LSA_MAXAGE))
407
    return CMP_OLDER;
408

    
409
  if (ABS(l1->age - l2->age) > LSA_MAXAGEDIFF)
410
    return l1->age < l2->age ? CMP_NEWER : CMP_OLDER;
411

    
412
  return CMP_SAME;
413
}
414

    
415
/**
416
 * lsa_install_new - install new LSA into database
417
 * @po: OSPF protocol
418
 * @lsa: LSA header
419
 * @domain: domain of LSA
420
 * @body: pointer to LSA body
421

422
 *
423
 * This function ensures installing new LSA into LSA database. Old instance is
424
 * replaced. Several actions are taken to detect if new routing table
425
 * calculation is necessary. This is described in 13.2 of RFC 2328.
426
 */
427
struct top_hash_entry *
428
lsa_install_new(struct proto_ospf *po, struct ospf_lsa_header *lsa, u32 domain, void *body)
429
{
430
  /* LSA can be temporarrily, but body must be mb_allocated. */
431
  int change = 0;
432
  struct top_hash_entry *en;
433

    
434
  if ((en = ospf_hash_find_header(po->gr, domain, lsa)) == NULL)
435
  {
436
    en = ospf_hash_get_header(po->gr, domain, lsa);
437
    change = 1;
438
  }
439
  else
440
  {
441
    if ((en->lsa.length != lsa->length)
442
#ifdef OSPFv2       
443
        || (en->lsa.options != lsa->options)
444
#endif
445
        || (en->lsa.age == LSA_MAXAGE)
446
        || (lsa->age == LSA_MAXAGE)
447
        || memcmp(en->lsa_body, body, lsa->length - sizeof(struct ospf_lsa_header)))
448
      change = 1;
449

    
450
    s_rem_node(SNODE en);
451
  }
452

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

    
456
  s_add_tail(&po->lsal, SNODE en);
457
  en->inst_t = now;
458
  if (en->lsa_body != NULL)
459
    mb_free(en->lsa_body);
460
  en->lsa_body = body;
461
  memcpy(&en->lsa, lsa, sizeof(struct ospf_lsa_header));
462
  en->ini_age = en->lsa.age;
463

    
464
  if (change)
465
  {
466
    schedule_rtcalc(po);
467
  }
468

    
469
  return en;
470
}