Statistics
| Branch: | Revision:

iof-bird-daemon / proto / ospf / lsalib.c @ 035f6acb

History | View | Annotate | Download (10.8 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
  if(en->lsa_body!=NULL) mb_free(en->lsa_body);
19
  en->lsa_body=NULL;
20
  ospf_hash_delete(oa->gr,en);
21
}
22

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

    
46
  OSPF_TRACE(D_EVENTS, "Running ospf_age");
47

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

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

    
101
void
102
ntohlsah(struct ospf_lsa_header *n, struct ospf_lsa_header *h)
103
{
104
  h->age=ntohs(n->age);
105
  h->options=n->options;
106
  h->type=n->type;
107
  h->id=ntohl(n->id);
108
  h->rt=ntohl(n->rt);
109
  h->sn=ntohl(n->sn);
110
  h->checksum=ntohs(n->checksum);
111
  h->length=ntohs(n->length);
112
};
113

    
114
void
115
htonlsab(void *h, void *n, u8 type, u16 len)
116
{
117
  unsigned int i;
118
  switch(type)
119
  {
120
    case LSA_T_RT:
121
    {
122
      struct ospf_lsa_rt *hrt, *nrt;
123
      struct ospf_lsa_rt_link *hrtl,*nrtl;
124
      u16 links;
125

    
126
      nrt=n;
127
      hrt=h;
128
      links=hrt->links;
129

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

    
149
      nid=n;
150
      hid=h;
151

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

    
164
      hs=h;
165
      ns=n;
166

    
167
      ns->netmask=hs->netmask;
168
      ipa_hton(ns->netmask);
169

    
170
      hn=(struct ospf_lsa_summ_net *)(hs+1);
171
      nn=(struct ospf_lsa_summ_net *)(ns+1);
172

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

    
187
      he=h;
188
      ne=n;
189

    
190
      ne->netmask=he->netmask;
191
      ipa_hton(ne->netmask);
192

    
193
      ht=(struct ospf_lsa_ext_tos *)(he+1);
194
      nt=(struct ospf_lsa_ext_tos *)(ne+1);
195

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

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

    
224
      nrt=n;
225
      hrt=h;
226

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

    
246
      hid=h;
247
      nid=n;
248

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

    
261
      hs=h;
262
      ns=n;
263

    
264
      hs->netmask=ns->netmask;
265
      ipa_ntoh(hs->netmask);
266

    
267
      hn=(struct ospf_lsa_summ_net *)(hs+1);
268
      nn=(struct ospf_lsa_summ_net *)(ns+1);
269

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

    
284
      he=h;
285
      ne=n;
286

    
287
      he->netmask=ne->netmask;
288
      ipa_ntoh(he->netmask);
289

    
290
      ht=(struct ospf_lsa_ext_tos *)(he+1);
291
      nt=(struct ospf_lsa_ext_tos *)(ne+1);
292

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

    
309
#define MODX 4102                /* larges signed value without overflow */
310

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

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

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

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

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

    
344
  b = body;
345
  sp = (char *) &h->options;
346
  length = ntohs(h->length)-2;
347
  h->checksum = 0;
348

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

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

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

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

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

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

    
395
  if(sn1>sn2) return CMP_NEWER;
396
  if(sn1<sn2) return CMP_OLDER;
397

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

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

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

    
407
  return CMP_SAME;
408
}
409

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

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

    
453
  DBG("Inst lsa: Id: %I, Rt: %I, 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(&oa->lsal, SNODE en);
457
  en->inst_t=now;
458
  if(en->lsa_body!=NULL) mb_free(en->lsa_body);
459
  en->lsa_body=body;
460
  memcpy(&en->lsa,lsa,sizeof(struct ospf_lsa_header));
461
  en->ini_age=en->lsa.age;
462

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