Statistics
| Branch: | Revision:

iof-bird-daemon / proto / ospf / lsalib.c @ 6567e6cf

History | View | Annotate | Download (10.6 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 new
26
 * age of all LSAs and old (@age is higher than %LSA_MAXAGE) are flushed
27
 * when ever possible. If some LSA originated by router itself is older
28
 * than %LSREFRESHTIME new instance is originated.
29
 *
30
 * RFC says, that router should check checksum of every LSA to detect some
31
 * hardware problem. BIRD does not do it to minimalize CPU utilization.
32
 *
33
 * If routing table calculation is scheduled, it also invalidates 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
  WALK_SLIST_DELSAFE(en,nxt,oa->lsal)
45
  {
46
    if(oa->calcrt)
47
    {
48
      en->color=OUTSPF;
49
      en->dist=LSINFINITY;
50
      en->nhi=NULL;
51
      en->nh=ipa_from_u32(0);
52
      DBG("Infinitying Type: %u, Id: %I, Rt: %I\n", en->lsa.type, en->lsa.id,
53
        en->lsa.rt);
54
    }
55
    if(en->lsa.age==LSA_MAXAGE)
56
    {
57
      if(flush) flush_lsa(en,oa);
58
      continue;
59
    }
60
    if((en->lsa.rt==p->cf->global->router_id)&&(en->lsa.age>=LSREFRESHTIME))
61
    {
62
       OSPF_TRACE(D_EVENTS, "Refreshing my LSA: Type: %u, Id: %I, Rt: %I",
63
         en->lsa.type, en->lsa.id, en->lsa.rt);
64
       en->lsa.sn++;
65
       en->lsa.age=0;
66
       lsasum_calculate(&en->lsa,en->lsa_body,po);
67
       flood_lsa(NULL,NULL,&en->lsa,po,NULL,oa,1);
68
       continue;
69
    }
70
    if((en->lsa.age=(en->ini_age+(now-en->inst_t)))>=LSA_MAXAGE)
71
    {
72
      if(flush)
73
      {
74
        flush_lsa(en,oa);
75
        schedule_rtcalc(oa);
76
      }
77
      else en->lsa.age=LSA_MAXAGE;
78
    }
79
  }
80
}
81

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

    
95
void
96
ntohlsah(struct ospf_lsa_header *n, struct ospf_lsa_header *h)
97
{
98
  h->age=ntohs(n->age);
99
  h->options=n->options;
100
  h->type=n->type;
101
  h->id=ntohl(n->id);
102
  h->rt=ntohl(n->rt);
103
  h->sn=ntohl(n->sn);
104
  h->checksum=ntohs(n->checksum);
105
  h->length=ntohs(n->length);
106
};
107

    
108
void
109
htonlsab(void *h, void *n, u8 type, u16 len)
110
{
111
  unsigned int i;
112
  switch(type)
113
  {
114
    case LSA_T_RT:
115
    {
116
      struct ospf_lsa_rt *hrt, *nrt;
117
      struct ospf_lsa_rt_link *hrtl,*nrtl;
118
      u16 links;
119

    
120
      nrt=n;
121
      hrt=h;
122
      links=hrt->links;
123

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

    
143
      nid=n;
144
      hid=h;
145

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

    
158
      hs=h;
159
      ns=n;
160

    
161
      ns->netmask=hs->netmask;
162
      ipa_hton(ns->netmask);
163

    
164
      hn=(struct ospf_lsa_summ_net *)(hs+1);
165
      nn=(struct ospf_lsa_summ_net *)(ns+1);
166

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

    
181
      he=h;
182
      ne=n;
183

    
184
      ne->netmask=he->netmask;
185
      ipa_hton(ne->netmask);
186

    
187
      ht=(struct ospf_lsa_ext_tos *)(he+1);
188
      nt=(struct ospf_lsa_ext_tos *)(ne+1);
189

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

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

    
218
      nrt=n;
219
      hrt=h;
220

    
221
      hrt->VEB=nrt->VEB;
222
      hrt->padding=0;
223
      links=hrt->links=ntohs(nrt->links);
224
      nrtl=(struct ospf_lsa_rt_link *)(nrt+1);
225
      hrtl=(struct ospf_lsa_rt_link *)(hrt+1);
226
      for(i=0;i<links;i++)
227
      {
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
      }
234
      break;
235
    }
236
    case LSA_T_NET:
237
    {
238
      u32 *hid,*nid;
239

    
240
      hid=h;
241
      nid=n;
242

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

    
255
      hs=h;
256
      ns=n;
257

    
258
      hs->netmask=ns->netmask;
259
      ipa_ntoh(hs->netmask);
260

    
261
      hn=(struct ospf_lsa_summ_net *)(hs+1);
262
      nn=(struct ospf_lsa_summ_net *)(ns+1);
263

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

    
278
      he=h;
279
      ne=n;
280

    
281
      he->netmask=ne->netmask;
282
      ipa_ntoh(he->netmask);
283

    
284
      ht=(struct ospf_lsa_ext_tos *)(he+1);
285
      nt=(struct ospf_lsa_ext_tos *)(ne+1);
286

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

    
303
#define MODX 4102                /* larges signed value without overflow */
304

    
305
/* Fletcher Checksum -- Refer to RFC1008. */
306
#define MODX                 4102
307
#define LSA_CHECKSUM_OFFSET    15
308

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

    
317
  htonlsah(h,h);
318
  htonlsab(body,body,h->type,length-sizeof(struct ospf_lsa_header));
319

    
320
  (void)lsasum_check(h,body,po);
321
  
322
  ntohlsah(h,h);
323
  ntohlsab(body,body,h->type,length-sizeof(struct ospf_lsa_header));
324
}
325

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

    
338
  b=body;
339
  sp = (char *) &h->options;
340
  length=ntohs(h->length)-2;
341
  h->checksum = 0;
342

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

    
364
      c1 += c0;
365
    }
366
    c0 %= 255;
367
    c1 %= 255;
368
  }
369

    
370
  x = ((length - LSA_CHECKSUM_OFFSET) * c0 - c1) % 255;
371
  if (x <= 0) x += 255;
372
  y = 510 - c0 - x;
373
  if (y > 255) y -= 255;
374

    
375
  chsum= x + (y << 8);
376
  h->checksum = chsum;
377
  return chsum;
378
}
379

    
380
int
381
lsa_comp(struct ospf_lsa_header *l1, struct ospf_lsa_header *l2)
382
                        /* Return codes from point of view of l1 */
383
{
384
  u32 sn1,sn2;
385

    
386
  sn1=l1->sn-LSA_INITSEQNO+1;
387
  sn2=l2->sn-LSA_INITSEQNO+1;
388

    
389
  if(sn1>sn2) return CMP_NEWER;
390
  if(sn1<sn2) return CMP_OLDER;
391

    
392
  if(l1->checksum!=l2->checksum)
393
    return l1->checksum<l2->checksum ? CMP_OLDER : CMP_NEWER;
394

    
395
  if((l1->age==LSA_MAXAGE)&&(l2->age!=LSA_MAXAGE)) return CMP_NEWER;
396
  if((l2->age==LSA_MAXAGE)&&(l1->age!=LSA_MAXAGE)) return CMP_OLDER;
397

    
398
  if(abs(l1->age-l2->age)>LSA_MAXAGEDIFF)
399
    return l1->age<l2->age ? CMP_NEWER : CMP_OLDER;
400

    
401
  return CMP_SAME;
402
}
403

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

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

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

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

    
457
  if(change)
458
  {
459
    schedule_rtcalc(oa);
460
  }
461
  
462
  return en;
463
}