Statistics
| Branch: | Revision:

iof-bird-daemon / proto / ospf / lsalib.c @ 13b02be2

History | View | Annotate | Download (8.77 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 top_hash_entry *en, bird_clock_t delta, int flush,
20
  struct ospf_area *oa)
21
{
22
  struct proto *p=&oa->po->proto;
23
  if(en->lsa.age==LSA_MAXAGE)
24
  {
25
    if(flush) flush_lsa(en,oa);
26
    return;
27
  }
28
  if((en->lsa.rt==p->cf->global->router_id)&&(en->lsa.age>LSREFRESHTIME))
29
  {
30
     /* FIXME Reflood again my self originated LSA */
31
  }
32
  if((en->lsa.age+=delta)>LSA_MAXAGE)
33
  {
34
    if(flush) flush_lsa(en,oa);
35
    else en->lsa.age=LSA_MAXAGE;
36
    return;
37
  }
38
}
39

    
40
void
41
htonlsah(struct ospf_lsa_header *h, struct ospf_lsa_header *n)
42
{
43
  n->age=htons(h->age);
44
  n->options=h->options;
45
  n->type=h->type;
46
  n->id=htonl(h->id);
47
  n->rt=htonl(h->rt);
48
  n->sn=htonl(h->sn);
49
  n->checksum=htons(h->checksum);
50
  n->length=htons(h->length);
51
};
52

    
53
void
54
ntohlsah(struct ospf_lsa_header *n, struct ospf_lsa_header *h)
55
{
56
  h->age=ntohs(n->age);
57
  h->options=n->options;
58
  h->type=n->type;
59
  h->id=ntohl(n->id);
60
  h->rt=ntohl(n->rt);
61
  h->sn=ntohl(n->sn);
62
  h->checksum=ntohs(n->checksum);
63
  h->length=ntohs(n->length);
64
};
65

    
66
void
67
htonlsab(void *h, void *n, u8 type, u16 len)
68
{
69
  unsigned int i;
70
  switch(type)
71
  {
72
    case LSA_T_RT:
73
    {
74
      struct ospf_lsa_rt *hrt, *nrt;
75
      struct ospf_lsa_rt_link *hrtl,*nrtl;
76
      u16 links;
77

    
78
      nrt=n;
79
      hrt=h;
80
      links=hrt->links;
81

    
82
      nrt->VEB=hrt->VEB;
83
      nrt->padding=0;
84
      nrt->links=htons(hrt->links);
85
      nrtl=(struct ospf_lsa_rt_link *)(nrt+1);
86
      hrtl=(struct ospf_lsa_rt_link *)(hrt+1);
87
      for(i=0;i<links;i++)
88
      {
89
        (nrtl+i)->id=htonl((hrtl+i)->id);
90
        (nrtl+i)->data=htonl((hrtl+i)->data);
91
        (nrtl+i)->type=(hrtl+i)->type;
92
        (nrtl+i)->notos=(hrtl+i)->notos;
93
        (nrtl+i)->metric=htons((hrtl+i)->metric);
94
      }
95
      break;
96
    }
97
    case LSA_T_NET:
98
    {
99
      u32 *hid,*nid;
100

    
101
      nid=n;
102
      hid=h;
103

    
104
      for(i=0;i<(len/sizeof(u32));i++)
105
      {
106
        *(nid+i)=htonl(*(hid+i));
107
      }
108
      break;
109
    }
110
    case LSA_T_SUM_NET:
111
    case LSA_T_SUM_RT:
112
    {
113
      struct ospf_lsa_summ *hs, *ns;
114
      struct ospf_lsa_summ_net *hn, *nn;
115

    
116
      hs=h;
117
      ns=n;
118

    
119
      ns->netmask=hs->netmask;
120
      ipa_hton(ns->netmask);
121

    
122
      hn=(struct ospf_lsa_summ_net *)(hs+1);
123
      nn=(struct ospf_lsa_summ_net *)(ns+1);
124

    
125
      for(i=0;i<((len-sizeof(struct ospf_lsa_summ))/
126
        sizeof(struct ospf_lsa_summ_net));i++)
127
      {
128
        (nn+i)->tos=(hn+i)->tos;
129
        (nn+i)->metric=htons((hn+i)->metric);
130
        (nn+i)->padding=0;
131
      }
132
      break;
133
    }
134
    case LSA_T_EXT:
135
    {
136
      struct ospf_lsa_ext *he, *ne;
137
      struct ospf_lsa_ext_tos *ht, *nt;
138

    
139
      he=h;
140
      ne=n;
141

    
142
      ne->netmask=he->netmask;
143
      ipa_hton(ne->netmask);
144

    
145
      ht=(struct ospf_lsa_ext_tos *)(he+1);
146
      nt=(struct ospf_lsa_ext_tos *)(ne+1);
147

    
148
      for(i=0;i<((len-sizeof(struct ospf_lsa_ext))/
149
        sizeof(struct ospf_lsa_ext_tos));i++)
150
      {
151
        (nt+i)->etos=(ht+i)->etos;
152
        (nt+i)->padding=0;
153
        (nt+i)->metric=htons((ht+i)->metric);
154
        (nt+i)->fwaddr=(ht+i)->fwaddr;
155
        ipa_hton((nt+i)->fwaddr);
156
        (nt+i)->tag=htonl((ht+i)->tag);
157
      }
158
      break;
159
    }
160
    default: die("(hton): Unknown LSA\n");
161
  }
162
};
163

    
164
void
165
ntohlsab(void *n, void *h, u8 type, u16 len)
166
{
167
  unsigned int i;
168
  switch(type)
169
  {
170
    case LSA_T_RT:
171
    {
172
      struct ospf_lsa_rt *hrt, *nrt;
173
      struct ospf_lsa_rt_link *hrtl,*nrtl;
174
      u16 links;
175

    
176
      nrt=n;
177
      hrt=h;
178

    
179
      hrt->VEB=nrt->VEB;
180
      hrt->padding=0;
181
      links=hrt->links=ntohs(nrt->links);
182
      nrtl=(struct ospf_lsa_rt_link *)(nrt+1);
183
      hrtl=(struct ospf_lsa_rt_link *)(hrt+1);
184
      for(i=0;i<links;i++)
185
      {
186
        (hrtl+i)->id=ntohl((nrtl+i)->id);
187
        (hrtl+i)->data=ntohl((nrtl+i)->data);
188
        (hrtl+i)->type=(nrtl+i)->type;
189
        (hrtl+i)->notos=(nrtl+i)->notos;
190
        (hrtl+i)->metric=ntohs((nrtl+i)->metric);
191
      }
192
      break;
193
    }
194
    case LSA_T_NET:
195
    {
196
      u32 *hid,*nid;
197

    
198
      hid=h;
199
      nid=n;
200

    
201
      for(i=0;i<(len/sizeof(u32));i++)
202
      {
203
        *(hid+i)=ntohl(*(nid+i));
204
      }
205
      break;
206
    }
207
    case LSA_T_SUM_NET:
208
    case LSA_T_SUM_RT:
209
    {
210
      struct ospf_lsa_summ *hs, *ns;
211
      struct ospf_lsa_summ_net *hn, *nn;
212

    
213
      hs=h;
214
      ns=n;
215

    
216
      hs->netmask=ns->netmask;
217
      ipa_ntoh(hs->netmask);
218

    
219
      hn=(struct ospf_lsa_summ_net *)(hs+1);
220
      nn=(struct ospf_lsa_summ_net *)(ns+1);
221

    
222
      for(i=0;i<((len-sizeof(struct ospf_lsa_summ))/
223
        sizeof(struct ospf_lsa_summ_net));i++)
224
      {
225
        (hn+i)->tos=(nn+i)->tos;
226
        (hn+i)->metric=ntohs((nn+i)->metric);
227
        (hn+i)->padding=0;
228
      }
229
      break;
230
    }
231
    case LSA_T_EXT:
232
    {
233
      struct ospf_lsa_ext *he, *ne;
234
      struct ospf_lsa_ext_tos *ht, *nt;
235

    
236
      he=h;
237
      ne=n;
238

    
239
      he->netmask=ne->netmask;
240
      ipa_ntoh(he->netmask);
241

    
242
      ht=(struct ospf_lsa_ext_tos *)(he+1);
243
      nt=(struct ospf_lsa_ext_tos *)(ne+1);
244

    
245
      for(i=0;i<((len-sizeof(struct ospf_lsa_ext))/
246
        sizeof(struct ospf_lsa_ext_tos));i++)
247
      {
248
        (ht+i)->etos=(nt+i)->etos;
249
        (ht+i)->padding=0;
250
        (ht+i)->metric=ntohs((nt+i)->metric);
251
        (ht+i)->fwaddr=(nt+i)->fwaddr;
252
        ipa_ntoh((ht+i)->fwaddr);
253
        (ht+i)->tag=ntohl((nt+i)->tag);
254
      }
255
      break;
256
    }
257
    default: die("(ntoh): Unknown LSA\n");
258
  }
259
};
260

    
261
#define MODX 4102                /* larges signed value without overflow */
262

    
263
/* Fletcher Checksum -- Refer to RFC1008. */
264
#define MODX                 4102
265
#define LSA_CHECKSUM_OFFSET    15
266

    
267
/* FIXME This is VERY uneficient, I have huge endianity problems */
268
void
269
lsasum_calculate(struct ospf_lsa_header *h,void *body,struct proto_ospf *po)
270
{
271
  u16 length;
272
  
273
  length=h->length;
274

    
275
  htonlsah(h,h);
276
  htonlsab(body,body,h->type,length-sizeof(struct ospf_lsa_header));
277

    
278
  (void)lsasum_check(h,body,po);
279
  
280
  ntohlsah(h,h);
281
  ntohlsab(body,body,h->type,length-sizeof(struct ospf_lsa_header));
282
}
283

    
284
/*
285
 * Note, that this function expects that LSA is in big endianity
286
 * It also returns value in big endian
287
 */
288
u16
289
lsasum_check(struct ospf_lsa_header *h,void *body,struct proto_ospf *po)
290
{
291
  u8 *sp, *ep, *p, *q, *b;
292
  int c0 = 0, c1 = 0;
293
  int x, y;
294
  u16 length,chsum;
295

    
296
  b=body;
297
  sp = (char *) &h->options;
298
  length=ntohs(h->length)-2;
299
  h->checksum = 0;
300

    
301
  for (ep = sp + length; sp < ep; sp = q)
302
  {                /* Actually MODX is very large, do we need the for-cyclus? */
303
    q = sp + MODX;
304
    if (q > ep) q = ep;
305
    for (p = sp; p < q; p++)
306
    {
307
      /* 
308
       * I count with bytes from header and than from body
309
       * but if there is no body, it's appended to header
310
       * (probably checksum in update receiving) and I go on
311
       * after header
312
       */
313
      if((b==NULL) || (p<(u8 *)(h+1)))
314
      {
315
              c0 += *p;
316
      }
317
      else
318
      {
319
              c0 += *(b+(p-sp)-sizeof(struct ospf_lsa_header)+2);
320
      }
321

    
322
      c1 += c0;
323
    }
324
    c0 %= 255;
325
    c1 %= 255;
326
  }
327

    
328
  x = ((length - LSA_CHECKSUM_OFFSET) * c0 - c1) % 255;
329
  if (x <= 0) x += 255;
330
  y = 510 - c0 - x;
331
  if (y > 255) y -= 255;
332

    
333
  chsum= x + (y << 8);
334
  h->checksum = chsum;
335
  return chsum;
336
}
337

    
338
int
339
lsa_comp(struct ospf_lsa_header *l1, struct ospf_lsa_header *l2)
340
                        /* Return codes from point of view of l1 */
341
{
342
  if(l1->sn>l2->sn) return CMP_NEWER;
343
  if(l1->sn<l2->sn) return CMP_OLDER;
344

    
345
  if(l1->checksum=!l2->checksum)
346
    return l1->checksum<l2->checksum ? CMP_OLDER : CMP_NEWER;
347

    
348
  if((l1->age==LSA_MAXAGE)&&(l2->age!=LSA_MAXAGE)) return CMP_NEWER;
349
  if((l2->age==LSA_MAXAGE)&&(l1->age!=LSA_MAXAGE)) return CMP_OLDER;
350

    
351
  if(abs(l1->age-l2->age)>LSA_MAXAGEDIFF)
352
    return l1->age<l2->age ? CMP_NEWER : CMP_OLDER;
353

    
354
  return CMP_SAME;
355
}
356

    
357
/* LSA can be temporarrily, but body must be mb_alloced. */
358
struct top_hash_entry *
359
lsa_install_new(struct ospf_lsa_header *lsa, void *body, struct ospf_area *oa,
360
  struct proto *p)
361
{
362
  int change=0;
363
  unsigned i;
364
  struct top_hash_entry *en;
365

    
366
  if((en=ospf_hash_find_header(oa->gr,lsa))==NULL)
367
  {
368
    en=ospf_hash_get_header(oa->gr,lsa);
369
    change=1;
370
  }
371
  else
372
  {
373
    if((en->lsa.length!=lsa->length)||(en->lsa.options!=lsa->options)||
374
      ((en->lsa.age==LSA_MAXAGE)||(lsa->age==LSA_MAXAGE))) change=1;
375
    else
376
    {
377
      u8 *k=en->lsa_body,*l=body;
378
      for(i=0;i<(lsa->length-sizeof(struct ospf_lsa_header));i++)
379
      {
380
        if(*(k+i)!=*(l+i))
381
        {
382
          change=1;
383
          break;
384
        }
385
      }
386
    }
387
    if(change) s_rem_node(SNODE en);
388
  }
389

    
390
  if(change)
391
  {
392
    s_add_tail(&oa->lsal, SNODE en);
393
    en->inst_t=now;
394
    if(en->lsa_body!=NULL) mb_free(en->lsa_body);
395
    en->lsa_body=body;
396
    memcpy(&en->lsa,lsa,sizeof(struct ospf_lsa_header));
397
    /* FIXME decide if route calculation must be done and how */
398
    if(oa->rt!=NULL)
399
    {
400
      DBG("Starting routing table calculation.\n");
401
      ospf_rt_spfa(oa);
402
    }
403
  }
404
  
405
  return en;
406
}