Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (9.07 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
  s_rem_node(SNODE en);
15
  ospf_hash_delete(oa->gr,en);
16
}
17

    
18
void
19
ospf_age(struct ospf_area *oa)
20
{
21
  struct proto *p=&oa->po->proto;
22
  struct proto_ospf *po=(struct proto_ospf *)p;
23
  struct top_hash_entry *en,*nxt;
24
  int flush=can_flush_lsa(oa);
25
  bird_clock_t delta=now-oa->lage;
26

    
27
  WALK_SLIST_DELSAFE(en,nxt,oa->lsal)
28
  {
29
    if(en->lsa.age==LSA_MAXAGE)
30
    {
31
      if(flush) flush_lsa(en,oa);
32
      continue;
33
    }
34
    if((en->lsa.rt==p->cf->global->router_id)&&(en->lsa.age>LSREFRESHTIME))
35
    {
36
       en->lsa.sn++;
37
       en->lsa.age=0;
38
       flood_lsa(NULL,NULL,&en->lsa,po,NULL,oa,1);
39
       lsasum_calculate(&en->lsa,en->lsa_body,po);
40
       return;
41
    }
42
    if((en->lsa.age+=delta)>=LSA_MAXAGE)
43
    {
44
      if(flush)
45
      {
46
        flush_lsa(en,oa);
47
        schedule_rtcalc(oa);
48
      }
49
      else en->lsa.age=LSA_MAXAGE;
50
    }
51
  }
52
  oa->lage=now;
53
}
54

    
55
void
56
htonlsah(struct ospf_lsa_header *h, struct ospf_lsa_header *n)
57
{
58
  n->age=htons(h->age);
59
  n->options=h->options;
60
  n->type=h->type;
61
  n->id=htonl(h->id);
62
  n->rt=htonl(h->rt);
63
  n->sn=htonl(h->sn);
64
  n->checksum=htons(h->checksum);
65
  n->length=htons(h->length);
66
};
67

    
68
void
69
ntohlsah(struct ospf_lsa_header *n, struct ospf_lsa_header *h)
70
{
71
  h->age=ntohs(n->age);
72
  h->options=n->options;
73
  h->type=n->type;
74
  h->id=ntohl(n->id);
75
  h->rt=ntohl(n->rt);
76
  h->sn=ntohl(n->sn);
77
  h->checksum=ntohs(n->checksum);
78
  h->length=ntohs(n->length);
79
};
80

    
81
void
82
htonlsab(void *h, void *n, u8 type, u16 len)
83
{
84
  unsigned int i;
85
  switch(type)
86
  {
87
    case LSA_T_RT:
88
    {
89
      struct ospf_lsa_rt *hrt, *nrt;
90
      struct ospf_lsa_rt_link *hrtl,*nrtl;
91
      u16 links;
92

    
93
      nrt=n;
94
      hrt=h;
95
      links=hrt->links;
96

    
97
      nrt->VEB=hrt->VEB;
98
      nrt->padding=0;
99
      nrt->links=htons(hrt->links);
100
      nrtl=(struct ospf_lsa_rt_link *)(nrt+1);
101
      hrtl=(struct ospf_lsa_rt_link *)(hrt+1);
102
      for(i=0;i<links;i++)
103
      {
104
        (nrtl+i)->id=htonl((hrtl+i)->id);
105
        (nrtl+i)->data=htonl((hrtl+i)->data);
106
        (nrtl+i)->type=(hrtl+i)->type;
107
        (nrtl+i)->notos=(hrtl+i)->notos;
108
        (nrtl+i)->metric=htons((hrtl+i)->metric);
109
      }
110
      break;
111
    }
112
    case LSA_T_NET:
113
    {
114
      u32 *hid,*nid;
115

    
116
      nid=n;
117
      hid=h;
118

    
119
      for(i=0;i<(len/sizeof(u32));i++)
120
      {
121
        *(nid+i)=htonl(*(hid+i));
122
      }
123
      break;
124
    }
125
    case LSA_T_SUM_NET:
126
    case LSA_T_SUM_RT:
127
    {
128
      struct ospf_lsa_summ *hs, *ns;
129
      struct ospf_lsa_summ_net *hn, *nn;
130

    
131
      hs=h;
132
      ns=n;
133

    
134
      ns->netmask=hs->netmask;
135
      ipa_hton(ns->netmask);
136

    
137
      hn=(struct ospf_lsa_summ_net *)(hs+1);
138
      nn=(struct ospf_lsa_summ_net *)(ns+1);
139

    
140
      for(i=0;i<((len-sizeof(struct ospf_lsa_summ))/
141
        sizeof(struct ospf_lsa_summ_net));i++)
142
      {
143
        (nn+i)->tos=(hn+i)->tos;
144
        (nn+i)->metric=htons((hn+i)->metric);
145
        (nn+i)->padding=0;
146
      }
147
      break;
148
    }
149
    case LSA_T_EXT:
150
    {
151
      struct ospf_lsa_ext *he, *ne;
152
      struct ospf_lsa_ext_tos *ht, *nt;
153

    
154
      he=h;
155
      ne=n;
156

    
157
      ne->netmask=he->netmask;
158
      ipa_hton(ne->netmask);
159

    
160
      ht=(struct ospf_lsa_ext_tos *)(he+1);
161
      nt=(struct ospf_lsa_ext_tos *)(ne+1);
162

    
163
      for(i=0;i<((len-sizeof(struct ospf_lsa_ext))/
164
        sizeof(struct ospf_lsa_ext_tos));i++)
165
      {
166
        (nt+i)->etos=(ht+i)->etos;
167
        (nt+i)->padding=0;
168
        (nt+i)->metric=htons((ht+i)->metric);
169
        (nt+i)->fwaddr=(ht+i)->fwaddr;
170
        ipa_hton((nt+i)->fwaddr);
171
        (nt+i)->tag=htonl((ht+i)->tag);
172
      }
173
      break;
174
    }
175
    default: die("(hton): Unknown LSA\n");
176
  }
177
};
178

    
179
void
180
ntohlsab(void *n, void *h, u8 type, u16 len)
181
{
182
  unsigned int i;
183
  switch(type)
184
  {
185
    case LSA_T_RT:
186
    {
187
      struct ospf_lsa_rt *hrt, *nrt;
188
      struct ospf_lsa_rt_link *hrtl,*nrtl;
189
      u16 links;
190

    
191
      nrt=n;
192
      hrt=h;
193

    
194
      hrt->VEB=nrt->VEB;
195
      hrt->padding=0;
196
      links=hrt->links=ntohs(nrt->links);
197
      nrtl=(struct ospf_lsa_rt_link *)(nrt+1);
198
      hrtl=(struct ospf_lsa_rt_link *)(hrt+1);
199
      for(i=0;i<links;i++)
200
      {
201
        (hrtl+i)->id=ntohl((nrtl+i)->id);
202
        (hrtl+i)->data=ntohl((nrtl+i)->data);
203
        (hrtl+i)->type=(nrtl+i)->type;
204
        (hrtl+i)->notos=(nrtl+i)->notos;
205
        (hrtl+i)->metric=ntohs((nrtl+i)->metric);
206
      }
207
      break;
208
    }
209
    case LSA_T_NET:
210
    {
211
      u32 *hid,*nid;
212

    
213
      hid=h;
214
      nid=n;
215

    
216
      for(i=0;i<(len/sizeof(u32));i++)
217
      {
218
        *(hid+i)=ntohl(*(nid+i));
219
      }
220
      break;
221
    }
222
    case LSA_T_SUM_NET:
223
    case LSA_T_SUM_RT:
224
    {
225
      struct ospf_lsa_summ *hs, *ns;
226
      struct ospf_lsa_summ_net *hn, *nn;
227

    
228
      hs=h;
229
      ns=n;
230

    
231
      hs->netmask=ns->netmask;
232
      ipa_ntoh(hs->netmask);
233

    
234
      hn=(struct ospf_lsa_summ_net *)(hs+1);
235
      nn=(struct ospf_lsa_summ_net *)(ns+1);
236

    
237
      for(i=0;i<((len-sizeof(struct ospf_lsa_summ))/
238
        sizeof(struct ospf_lsa_summ_net));i++)
239
      {
240
        (hn+i)->tos=(nn+i)->tos;
241
        (hn+i)->metric=ntohs((nn+i)->metric);
242
        (hn+i)->padding=0;
243
      }
244
      break;
245
    }
246
    case LSA_T_EXT:
247
    {
248
      struct ospf_lsa_ext *he, *ne;
249
      struct ospf_lsa_ext_tos *ht, *nt;
250

    
251
      he=h;
252
      ne=n;
253

    
254
      he->netmask=ne->netmask;
255
      ipa_ntoh(he->netmask);
256

    
257
      ht=(struct ospf_lsa_ext_tos *)(he+1);
258
      nt=(struct ospf_lsa_ext_tos *)(ne+1);
259

    
260
      for(i=0;i<((len-sizeof(struct ospf_lsa_ext))/
261
        sizeof(struct ospf_lsa_ext_tos));i++)
262
      {
263
        (ht+i)->etos=(nt+i)->etos;
264
        (ht+i)->padding=0;
265
        (ht+i)->metric=ntohs((nt+i)->metric);
266
        (ht+i)->fwaddr=(nt+i)->fwaddr;
267
        ipa_ntoh((ht+i)->fwaddr);
268
        (ht+i)->tag=ntohl((nt+i)->tag);
269
      }
270
      break;
271
    }
272
    default: die("(ntoh): Unknown LSA\n");
273
  }
274
};
275

    
276
#define MODX 4102                /* larges signed value without overflow */
277

    
278
/* Fletcher Checksum -- Refer to RFC1008. */
279
#define MODX                 4102
280
#define LSA_CHECKSUM_OFFSET    15
281

    
282
/* FIXME This is VERY uneficient, I have huge endianity problems */
283
void
284
lsasum_calculate(struct ospf_lsa_header *h,void *body,struct proto_ospf *po)
285
{
286
  u16 length;
287
  
288
  length=h->length;
289

    
290
  htonlsah(h,h);
291
  htonlsab(body,body,h->type,length-sizeof(struct ospf_lsa_header));
292

    
293
  (void)lsasum_check(h,body,po);
294
  
295
  ntohlsah(h,h);
296
  ntohlsab(body,body,h->type,length-sizeof(struct ospf_lsa_header));
297
}
298

    
299
/*
300
 * Note, that this function expects that LSA is in big endianity
301
 * It also returns value in big endian
302
 */
303
u16
304
lsasum_check(struct ospf_lsa_header *h,void *body,struct proto_ospf *po)
305
{
306
  u8 *sp, *ep, *p, *q, *b;
307
  int c0 = 0, c1 = 0;
308
  int x, y;
309
  u16 length,chsum;
310

    
311
  b=body;
312
  sp = (char *) &h->options;
313
  length=ntohs(h->length)-2;
314
  h->checksum = 0;
315

    
316
  for (ep = sp + length; sp < ep; sp = q)
317
  {                /* Actually MODX is very large, do we need the for-cyclus? */
318
    q = sp + MODX;
319
    if (q > ep) q = ep;
320
    for (p = sp; p < q; p++)
321
    {
322
      /* 
323
       * I count with bytes from header and than from body
324
       * but if there is no body, it's appended to header
325
       * (probably checksum in update receiving) and I go on
326
       * after header
327
       */
328
      if((b==NULL) || (p<(u8 *)(h+1)))
329
      {
330
              c0 += *p;
331
      }
332
      else
333
      {
334
              c0 += *(b+(p-sp)-sizeof(struct ospf_lsa_header)+2);
335
      }
336

    
337
      c1 += c0;
338
    }
339
    c0 %= 255;
340
    c1 %= 255;
341
  }
342

    
343
  x = ((length - LSA_CHECKSUM_OFFSET) * c0 - c1) % 255;
344
  if (x <= 0) x += 255;
345
  y = 510 - c0 - x;
346
  if (y > 255) y -= 255;
347

    
348
  chsum= x + (y << 8);
349
  h->checksum = chsum;
350
  return chsum;
351
}
352

    
353
int
354
lsa_comp(struct ospf_lsa_header *l1, struct ospf_lsa_header *l2)
355
                        /* Return codes from point of view of l1 */
356
{
357
  u32 sn1,sn2;
358

    
359
  sn1=l1->sn-LSA_INITSEQNO+1;
360
  sn2=l2->sn-LSA_INITSEQNO+1;
361

    
362
  if(sn1>sn2) return CMP_NEWER;
363
  if(sn1<sn2) return CMP_OLDER;
364

    
365
  if(l1->checksum!=l2->checksum)
366
    return l1->checksum<l2->checksum ? CMP_OLDER : CMP_NEWER;
367

    
368
  if((l1->age==LSA_MAXAGE)&&(l2->age!=LSA_MAXAGE)) return CMP_NEWER;
369
  if((l2->age==LSA_MAXAGE)&&(l1->age!=LSA_MAXAGE)) return CMP_OLDER;
370

    
371
  debug("Abs=%u\n",abs(l1->age-l2->age));
372
  if(abs(l1->age-l2->age)>LSA_MAXAGEDIFF)
373
    return l1->age<l2->age ? CMP_NEWER : CMP_OLDER;
374

    
375
  return CMP_SAME;
376
}
377

    
378
/* LSA can be temporarrily, but body must be mb_alloced. */
379
struct top_hash_entry *
380
lsa_install_new(struct ospf_lsa_header *lsa, void *body, struct ospf_area *oa,
381
  struct proto *p)
382
{
383
  int change=0;
384
  unsigned i;
385
  struct top_hash_entry *en;
386

    
387
  if(body==NULL) die("AA");
388

    
389
  if((en=ospf_hash_find_header(oa->gr,lsa))==NULL)
390
  {
391
    en=ospf_hash_get_header(oa->gr,lsa);
392
    change=1;
393
  }
394
  else
395
  {
396
    if((en->lsa.length!=lsa->length)||(en->lsa.options!=lsa->options)||
397
      ((en->lsa.age==LSA_MAXAGE)||(lsa->age==LSA_MAXAGE))) change=1;
398
    else
399
    {
400
      u8 *k=en->lsa_body,*l=body;
401
      for(i=0;i<(lsa->length-sizeof(struct ospf_lsa_header));i++)
402
      {
403
        if(*(k+i)!=*(l+i))
404
        {
405
          change=1;
406
          break;
407
        }
408
      }
409
    }
410
    if(change) s_rem_node(SNODE en);
411
  }
412

    
413
  s_add_tail(&oa->lsal, SNODE en);
414
  en->inst_t=now;
415
  if(en->lsa_body!=NULL) mb_free(en->lsa_body);
416
  en->lsa_body=body;
417
  memcpy(&en->lsa,lsa,sizeof(struct ospf_lsa_header));
418

    
419
  if(change)
420
  {
421
    schedule_rtcalc(oa);
422
  }
423
  
424
  return en;
425
}