Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (10.7 KB)

1
/*
2
 *        BIRD -- OSPF
3
 *
4
 *        (c) 1999 - 2000 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 ospf_area *oa)
13
{
14
  struct proto *p=&oa->po->proto;
15
  OSPF_TRACE(D_EVENTS, "Going to remove node Type: %u, Id: %I, Rt: %I, Age: %u",
16
    en->lsa.type, en->lsa.id, en->lsa.rt, en->lsa.age);
17
  s_rem_node(SNODE en);
18
  ospf_hash_delete(oa->gr,en);
19
}
20

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

    
44
  OSPF_TRACE(D_EVENTS, "Running ospf_age");
45

    
46
  WALK_SLIST_DELSAFE(en,nxt,oa->lsal)
47
  {
48
    if(oa->calcrt)
49
    {
50
      en->color=OUTSPF;
51
      en->dist=LSINFINITY;
52
      en->nhi=NULL;
53
      en->nh=ipa_from_u32(0);
54
      DBG("Infinitying Type: %u, Id: %I, Rt: %I\n", en->lsa.type, en->lsa.id,
55
        en->lsa.rt);
56
    }
57
    if(en->lsa.age==LSA_MAXAGE)
58
    {
59
      if(flush) flush_lsa(en,oa);
60
      continue;
61
    }
62
    if((en->lsa.rt==p->cf->global->router_id)&&(en->lsa.age>=LSREFRESHTIME))
63
    {
64
       OSPF_TRACE(D_EVENTS, "Refreshing my LSA: Type: %u, Id: %I, Rt: %I",
65
         en->lsa.type, en->lsa.id, en->lsa.rt);
66
       en->lsa.sn++;
67
       en->lsa.age=0;
68
       en->inst_t=now;
69
       en->ini_age=0;
70
       lsasum_calculate(&en->lsa,en->lsa_body,po);
71
       flood_lsa(NULL,NULL,&en->lsa,po,NULL,oa,1);
72
       continue;
73
    }
74
    if((en->lsa.age=(en->ini_age+(now-en->inst_t)))>=LSA_MAXAGE)
75
    {
76
      if(flush)
77
      {
78
        flush_lsa(en,oa);
79
        schedule_rtcalc(oa);
80
      }
81
      else en->lsa.age=LSA_MAXAGE;
82
    }
83
  }
84
}
85

    
86
void
87
htonlsah(struct ospf_lsa_header *h, struct ospf_lsa_header *n)
88
{
89
  n->age=htons(h->age);
90
  n->options=h->options;
91
  n->type=h->type;
92
  n->id=htonl(h->id);
93
  n->rt=htonl(h->rt);
94
  n->sn=htonl(h->sn);
95
  n->checksum=htons(h->checksum);
96
  n->length=htons(h->length);
97
};
98

    
99
void
100
ntohlsah(struct ospf_lsa_header *n, struct ospf_lsa_header *h)
101
{
102
  h->age=ntohs(n->age);
103
  h->options=n->options;
104
  h->type=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, u8 type, u16 len)
114
{
115
  unsigned int i;
116
  switch(type)
117
  {
118
    case LSA_T_RT:
119
    {
120
      struct ospf_lsa_rt *hrt, *nrt;
121
      struct ospf_lsa_rt_link *hrtl,*nrtl;
122
      u16 links;
123

    
124
      nrt=n;
125
      hrt=h;
126
      links=hrt->links;
127

    
128
      nrt->veb.byte=hrt->veb.byte;
129
      nrt->padding=0;
130
      nrt->links=htons(hrt->links);
131
      nrtl=(struct ospf_lsa_rt_link *)(nrt+1);
132
      hrtl=(struct ospf_lsa_rt_link *)(hrt+1);
133
      for(i=0;i<links;i++)
134
      {
135
        (nrtl+i)->id=htonl((hrtl+i)->id);
136
        (nrtl+i)->data=htonl((hrtl+i)->data);
137
        (nrtl+i)->type=(hrtl+i)->type;
138
        (nrtl+i)->notos=(hrtl+i)->notos;
139
        (nrtl+i)->metric=htons((hrtl+i)->metric);
140
      }
141
      break;
142
    }
143
    case LSA_T_NET:
144
    {
145
      u32 *hid,*nid;
146

    
147
      nid=n;
148
      hid=h;
149

    
150
      for(i=0;i<(len/sizeof(u32));i++)
151
      {
152
        *(nid+i)=htonl(*(hid+i));
153
      }
154
      break;
155
    }
156
    case LSA_T_SUM_NET:
157
    case LSA_T_SUM_RT:
158
    {
159
      struct ospf_lsa_summ *hs, *ns;
160
      struct ospf_lsa_summ_net *hn, *nn;
161

    
162
      hs=h;
163
      ns=n;
164

    
165
      ns->netmask=hs->netmask;
166
      ipa_hton(ns->netmask);
167

    
168
      hn=(struct ospf_lsa_summ_net *)(hs+1);
169
      nn=(struct ospf_lsa_summ_net *)(ns+1);
170

    
171
      for(i=0;i<((len-sizeof(struct ospf_lsa_summ))/
172
        sizeof(struct ospf_lsa_summ_net));i++)
173
      {
174
        (nn+i)->tos=(hn+i)->tos;
175
        (nn+i)->metric=htons((hn+i)->metric);
176
        (nn+i)->padding=0;
177
      }
178
      break;
179
    }
180
    case LSA_T_EXT:
181
    {
182
      struct ospf_lsa_ext *he, *ne;
183
      struct ospf_lsa_ext_tos *ht, *nt;
184

    
185
      he=h;
186
      ne=n;
187

    
188
      ne->netmask=he->netmask;
189
      ipa_hton(ne->netmask);
190

    
191
      ht=(struct ospf_lsa_ext_tos *)(he+1);
192
      nt=(struct ospf_lsa_ext_tos *)(ne+1);
193

    
194
      for(i=0;i<((len-sizeof(struct ospf_lsa_ext))/
195
        sizeof(struct ospf_lsa_ext_tos));i++)
196
      {
197
        (nt+i)->etos=(ht+i)->etos;
198
        (nt+i)->padding=0;
199
        (nt+i)->metric=htons((ht+i)->metric);
200
        (nt+i)->fwaddr=(ht+i)->fwaddr;
201
        ipa_hton((nt+i)->fwaddr);
202
        (nt+i)->tag=htonl((ht+i)->tag);
203
      }
204
      break;
205
    }
206
    default: bug("(hton): Unknown LSA");
207
  }
208
};
209

    
210
void
211
ntohlsab(void *n, void *h, u8 type, u16 len)
212
{
213
  unsigned int i;
214
  switch(type)
215
  {
216
    case LSA_T_RT:
217
    {
218
      struct ospf_lsa_rt *hrt, *nrt;
219
      struct ospf_lsa_rt_link *hrtl,*nrtl;
220
      u16 links;
221

    
222
      nrt=n;
223
      hrt=h;
224

    
225
      hrt->veb.byte=nrt->veb.byte;
226
      hrt->padding=0;
227
      links=hrt->links=ntohs(nrt->links);
228
      nrtl=(struct ospf_lsa_rt_link *)(nrt+1);
229
      hrtl=(struct ospf_lsa_rt_link *)(hrt+1);
230
      for(i=0;i<links;i++)
231
      {
232
        (hrtl+i)->id=ntohl((nrtl+i)->id);
233
        (hrtl+i)->data=ntohl((nrtl+i)->data);
234
        (hrtl+i)->type=(nrtl+i)->type;
235
        (hrtl+i)->notos=(nrtl+i)->notos;
236
        (hrtl+i)->metric=ntohs((nrtl+i)->metric);
237
      }
238
      break;
239
    }
240
    case LSA_T_NET:
241
    {
242
      u32 *hid,*nid;
243

    
244
      hid=h;
245
      nid=n;
246

    
247
      for(i=0;i<(len/sizeof(u32));i++)
248
      {
249
        *(hid+i)=ntohl(*(nid+i));
250
      }
251
      break;
252
    }
253
    case LSA_T_SUM_NET:
254
    case LSA_T_SUM_RT:
255
    {
256
      struct ospf_lsa_summ *hs, *ns;
257
      struct ospf_lsa_summ_net *hn, *nn;
258

    
259
      hs=h;
260
      ns=n;
261

    
262
      hs->netmask=ns->netmask;
263
      ipa_ntoh(hs->netmask);
264

    
265
      hn=(struct ospf_lsa_summ_net *)(hs+1);
266
      nn=(struct ospf_lsa_summ_net *)(ns+1);
267

    
268
      for(i=0;i<((len-sizeof(struct ospf_lsa_summ))/
269
        sizeof(struct ospf_lsa_summ_net));i++)
270
      {
271
        (hn+i)->tos=(nn+i)->tos;
272
        (hn+i)->metric=ntohs((nn+i)->metric);
273
        (hn+i)->padding=0;
274
      }
275
      break;
276
    }
277
    case LSA_T_EXT:
278
    {
279
      struct ospf_lsa_ext *he, *ne;
280
      struct ospf_lsa_ext_tos *ht, *nt;
281

    
282
      he=h;
283
      ne=n;
284

    
285
      he->netmask=ne->netmask;
286
      ipa_ntoh(he->netmask);
287

    
288
      ht=(struct ospf_lsa_ext_tos *)(he+1);
289
      nt=(struct ospf_lsa_ext_tos *)(ne+1);
290

    
291
      for(i=0;i<((len-sizeof(struct ospf_lsa_ext))/
292
        sizeof(struct ospf_lsa_ext_tos));i++)
293
      {
294
        (ht+i)->etos=(nt+i)->etos;
295
        (ht+i)->padding=0;
296
        (ht+i)->metric=ntohs((nt+i)->metric);
297
        (ht+i)->fwaddr=(nt+i)->fwaddr;
298
        ipa_ntoh((ht+i)->fwaddr);
299
        (ht+i)->tag=ntohl((nt+i)->tag);
300
      }
301
      break;
302
    }
303
    default: bug("(ntoh): Unknown LSA");
304
  }
305
};
306

    
307
#define MODX 4102                /* larges signed value without overflow */
308

    
309
/* Fletcher Checksum -- Refer to RFC1008. */
310
#define MODX                 4102
311
#define LSA_CHECKSUM_OFFSET    15
312

    
313
/* FIXME This is VERY uneficient, I have huge endianity problems */
314
void
315
lsasum_calculate(struct ospf_lsa_header *h,void *body,struct proto_ospf *po)
316
{
317
  u16 length;
318
  
319
  length=h->length;
320

    
321
  htonlsah(h,h);
322
  htonlsab(body,body,h->type,length-sizeof(struct ospf_lsa_header));
323

    
324
  (void)lsasum_check(h,body,po);
325
  
326
  ntohlsah(h,h);
327
  ntohlsab(body,body,h->type,length-sizeof(struct ospf_lsa_header));
328
}
329

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

    
342
  b = body;
343
  sp = (char *) &h->options;
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) q = ep;
351
    for (p = sp; p < q; p++)
352
    {
353
      /* 
354
       * I count with bytes from header and than from body
355
       * but if there is no body, it's appended to header
356
       * (probably checksum in update receiving) and I go on
357
       * after header
358
       */
359
      if((b==NULL) || (p<(u8 *)(h+1)))
360
      {
361
              c0 += *p;
362
      }
363
      else
364
      {
365
              c0 += *(b+(p-sp)-sizeof(struct ospf_lsa_header)+2);
366
      }
367

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

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

    
379
  ((u8*)&h->checksum)[0] = x;
380
  ((u8*)&h->checksum)[1] = y;
381
  return h->checksum;
382
}
383

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

    
390
  sn1=l1->sn-LSA_INITSEQNO+1;
391
  sn2=l2->sn-LSA_INITSEQNO+1;
392

    
393
  if(sn1>sn2) return CMP_NEWER;
394
  if(sn1<sn2) return CMP_OLDER;
395

    
396
  if(l1->checksum!=l2->checksum)
397
    return l1->checksum<l2->checksum ? CMP_OLDER : CMP_NEWER;
398

    
399
  if((l1->age==LSA_MAXAGE)&&(l2->age!=LSA_MAXAGE)) return CMP_NEWER;
400
  if((l2->age==LSA_MAXAGE)&&(l1->age!=LSA_MAXAGE)) return CMP_OLDER;
401

    
402
  if(ABS(l1->age-l2->age)>LSA_MAXAGEDIFF)
403
    return l1->age<l2->age ? CMP_NEWER : CMP_OLDER;
404

    
405
  return CMP_SAME;
406
}
407

    
408
/**
409
 * lsa_install_new - install new LSA into database
410
 * @lsa: LSA header
411
 * @body: pointer to LSA body
412
 * @oa: current ospf_area
413
 *
414
 * This function ensures installing new LSA into LSA database. Old instance is
415
 * replaced. Several actions are taken to detect if new routing table
416
 * calculation is necessary. This is described in 13.2 of RFC 2328.
417
 */
418
struct top_hash_entry *
419
lsa_install_new(struct ospf_lsa_header *lsa, void *body, struct ospf_area *oa)
420
{
421
  /* LSA can be temporarrily, but body must be mb_alloced. */
422
  struct proto *p=&oa->po->proto;
423
  int change=0;
424
  unsigned i;
425
  struct top_hash_entry *en;
426

    
427
  if((en=ospf_hash_find_header(oa->gr,lsa))==NULL)
428
  {
429
    en=ospf_hash_get_header(oa->gr,lsa);
430
    change=1;
431
  }
432
  else
433
  {
434
    if((en->lsa.length!=lsa->length)||(en->lsa.options!=lsa->options)||
435
      ((en->lsa.age==LSA_MAXAGE)||(lsa->age==LSA_MAXAGE))) change=1;
436
    else
437
    {
438
      u8 *k=en->lsa_body,*l=body;
439
      for(i=0;i<(lsa->length-sizeof(struct ospf_lsa_header));i++)
440
      {
441
        if(*(k+i)!=*(l+i))
442
        {
443
          change=1;
444
          break;
445
        }
446
      }
447
    }
448
    s_rem_node(SNODE en);
449
  }
450

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

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

    
461
  if(change)
462
  {
463
    schedule_rtcalc(oa);
464
  }
465
  
466
  return en;
467
}