lsalib.c 11.2 KB
Newer Older
1 2 3
/*
 *	BIRD -- OSPF
 *
4
 *	(c) 1999--2004 Ondrej Filip <feela@network.cz>
5 6 7 8 9 10
 *
 *	Can be freely distributed and used under the terms of the GNU GPL.
 */

#include "ospf.h"

Ondřej Filip's avatar
Ondřej Filip committed
11
void
Ondřej Filip's avatar
Ondřej Filip committed
12
flush_lsa(struct top_hash_entry *en, struct ospf_area *oa)
Ondřej Filip's avatar
Ondřej Filip committed
13
{
Ondřej Filip's avatar
Ondřej Filip committed
14 15 16 17
  struct proto *p = &oa->po->proto;
  OSPF_TRACE(D_EVENTS,
	     "Going to remove node Type: %u, Id: %I, Rt: %I, Age: %u",
	     en->lsa.type, en->lsa.id, en->lsa.rt, en->lsa.age);
Ondřej Filip's avatar
Ondřej Filip committed
18
  s_rem_node(SNODE en);
Ondřej Filip's avatar
Ondřej Filip committed
19 20 21 22
  if (en->lsa_body != NULL)
    mb_free(en->lsa_body);
  en->lsa_body = NULL;
  ospf_hash_delete(oa->gr, en);
Ondřej Filip's avatar
Ondřej Filip committed
23 24
}

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

Ondřej Filip's avatar
Ondřej Filip committed
48 49
  OSPF_TRACE(D_EVENTS, "Running ospf_age");

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

93 94 95
void
htonlsah(struct ospf_lsa_header *h, struct ospf_lsa_header *n)
{
Ondřej Filip's avatar
Ondřej Filip committed
96 97 98 99 100 101 102 103
  n->age = htons(h->age);
  n->options = h->options;
  n->type = h->type;
  n->id = htonl(h->id);
  n->rt = htonl(h->rt);
  n->sn = htonl(h->sn);
  n->checksum = htons(h->checksum);
  n->length = htons(h->length);
104 105 106 107 108
};

void
ntohlsah(struct ospf_lsa_header *n, struct ospf_lsa_header *h)
{
Ondřej Filip's avatar
Ondřej Filip committed
109 110 111 112 113 114 115 116
  h->age = ntohs(n->age);
  h->options = n->options;
  h->type = n->type;
  h->id = ntohl(n->id);
  h->rt = ntohl(n->rt);
  h->sn = ntohl(n->sn);
  h->checksum = ntohs(n->checksum);
  h->length = ntohs(n->length);
117 118 119 120 121 122
};

void
htonlsab(void *h, void *n, u8 type, u16 len)
{
  unsigned int i;
Ondřej Filip's avatar
Ondřej Filip committed
123
  switch (type)
124
  {
Ondřej Filip's avatar
Ondřej Filip committed
125
  case LSA_T_RT:
126 127
    {
      struct ospf_lsa_rt *hrt, *nrt;
Ondřej Filip's avatar
Ondřej Filip committed
128
      struct ospf_lsa_rt_link *hrtl, *nrtl;
129
      u16 links;
130

Ondřej Filip's avatar
Ondřej Filip committed
131 132 133
      nrt = n;
      hrt = h;
      links = hrt->links;
134

Ondřej Filip's avatar
Ondřej Filip committed
135 136 137 138 139 140
      nrt->veb.byte = hrt->veb.byte;
      nrt->padding = 0;
      nrt->links = htons(hrt->links);
      nrtl = (struct ospf_lsa_rt_link *) (nrt + 1);
      hrtl = (struct ospf_lsa_rt_link *) (hrt + 1);
      for (i = 0; i < links; i++)
141
      {
Ondřej Filip's avatar
Ondřej Filip committed
142 143 144 145 146
	(nrtl + i)->id = htonl((hrtl + i)->id);
	(nrtl + i)->data = htonl((hrtl + i)->data);
	(nrtl + i)->type = (hrtl + i)->type;
	(nrtl + i)->notos = (hrtl + i)->notos;
	(nrtl + i)->metric = htons((hrtl + i)->metric);
147 148 149
      }
      break;
    }
Ondřej Filip's avatar
Ondřej Filip committed
150
  case LSA_T_NET:
151
    {
Ondřej Filip's avatar
Ondřej Filip committed
152
      u32 *hid, *nid;
153

Ondřej Filip's avatar
Ondřej Filip committed
154 155
      nid = n;
      hid = h;
156

Ondřej Filip's avatar
Ondřej Filip committed
157
      for (i = 0; i < (len / sizeof(u32)); i++)
158
      {
Ondřej Filip's avatar
Ondřej Filip committed
159
	*(nid + i) = htonl(*(hid + i));
160 161 162
      }
      break;
    }
Ondřej Filip's avatar
Ondřej Filip committed
163 164
  case LSA_T_SUM_NET:
  case LSA_T_SUM_RT:
165 166 167 168
    {
      struct ospf_lsa_summ *hs, *ns;
      struct ospf_lsa_summ_net *hn, *nn;

Ondřej Filip's avatar
Ondřej Filip committed
169 170
      hs = h;
      ns = n;
171

Ondřej Filip's avatar
Ondřej Filip committed
172
      ns->netmask = hs->netmask;
173
      ipa_hton(ns->netmask);
174

Ondřej Filip's avatar
Ondřej Filip committed
175 176
      hn = (struct ospf_lsa_summ_net *) (hs + 1);
      nn = (struct ospf_lsa_summ_net *) (ns + 1);
177

Ondřej Filip's avatar
Ondřej Filip committed
178 179
      for (i = 0; i < ((len - sizeof(struct ospf_lsa_summ)) /
		       sizeof(struct ospf_lsa_summ_net)); i++)
180
      {
Ondřej Filip's avatar
Ondřej Filip committed
181 182 183
	(nn + i)->tos = (hn + i)->tos;
	(nn + i)->metric = htons((hn + i)->metric);
	(nn + i)->padding = 0;
184 185 186
      }
      break;
    }
Ondřej Filip's avatar
Ondřej Filip committed
187
  case LSA_T_EXT:
188 189 190 191
    {
      struct ospf_lsa_ext *he, *ne;
      struct ospf_lsa_ext_tos *ht, *nt;

Ondřej Filip's avatar
Ondřej Filip committed
192 193
      he = h;
      ne = n;
194

Ondřej Filip's avatar
Ondřej Filip committed
195
      ne->netmask = he->netmask;
196
      ipa_hton(ne->netmask);
197

Ondřej Filip's avatar
Ondřej Filip committed
198 199
      ht = (struct ospf_lsa_ext_tos *) (he + 1);
      nt = (struct ospf_lsa_ext_tos *) (ne + 1);
200

Ondřej Filip's avatar
Ondřej Filip committed
201 202
      for (i = 0; i < ((len - sizeof(struct ospf_lsa_ext)) /
		       sizeof(struct ospf_lsa_ext_tos)); i++)
203
      {
Ondřej Filip's avatar
Ondřej Filip committed
204 205 206 207 208 209
	(nt + i)->etos = (ht + i)->etos;
	(nt + i)->padding = 0;
	(nt + i)->metric = htons((ht + i)->metric);
	(nt + i)->fwaddr = (ht + i)->fwaddr;
	ipa_hton((nt + i)->fwaddr);
	(nt + i)->tag = htonl((ht + i)->tag);
210 211 212
      }
      break;
    }
Ondřej Filip's avatar
Ondřej Filip committed
213 214
  default:
    bug("(hton): Unknown LSA");
215 216 217 218 219 220 221
  }
};

void
ntohlsab(void *n, void *h, u8 type, u16 len)
{
  unsigned int i;
Ondřej Filip's avatar
Ondřej Filip committed
222
  switch (type)
223
  {
Ondřej Filip's avatar
Ondřej Filip committed
224
  case LSA_T_RT:
225 226
    {
      struct ospf_lsa_rt *hrt, *nrt;
Ondřej Filip's avatar
Ondřej Filip committed
227
      struct ospf_lsa_rt_link *hrtl, *nrtl;
228
      u16 links;
229

Ondřej Filip's avatar
Ondřej Filip committed
230 231
      nrt = n;
      hrt = h;
232

Ondřej Filip's avatar
Ondřej Filip committed
233 234 235 236 237 238
      hrt->veb.byte = nrt->veb.byte;
      hrt->padding = 0;
      links = hrt->links = ntohs(nrt->links);
      nrtl = (struct ospf_lsa_rt_link *) (nrt + 1);
      hrtl = (struct ospf_lsa_rt_link *) (hrt + 1);
      for (i = 0; i < links; i++)
239
      {
Ondřej Filip's avatar
Ondřej Filip committed
240 241 242 243 244
	(hrtl + i)->id = ntohl((nrtl + i)->id);
	(hrtl + i)->data = ntohl((nrtl + i)->data);
	(hrtl + i)->type = (nrtl + i)->type;
	(hrtl + i)->notos = (nrtl + i)->notos;
	(hrtl + i)->metric = ntohs((nrtl + i)->metric);
245 246 247
      }
      break;
    }
Ondřej Filip's avatar
Ondřej Filip committed
248
  case LSA_T_NET:
249
    {
Ondřej Filip's avatar
Ondřej Filip committed
250
      u32 *hid, *nid;
251

Ondřej Filip's avatar
Ondřej Filip committed
252 253
      hid = h;
      nid = n;
254

Ondřej Filip's avatar
Ondřej Filip committed
255
      for (i = 0; i < (len / sizeof(u32)); i++)
256
      {
Ondřej Filip's avatar
Ondřej Filip committed
257
	*(hid + i) = ntohl(*(nid + i));
258 259 260
      }
      break;
    }
Ondřej Filip's avatar
Ondřej Filip committed
261 262
  case LSA_T_SUM_NET:
  case LSA_T_SUM_RT:
263 264 265 266
    {
      struct ospf_lsa_summ *hs, *ns;
      struct ospf_lsa_summ_net *hn, *nn;

Ondřej Filip's avatar
Ondřej Filip committed
267 268
      hs = h;
      ns = n;
269

Ondřej Filip's avatar
Ondřej Filip committed
270
      hs->netmask = ns->netmask;
271
      ipa_ntoh(hs->netmask);
272

Ondřej Filip's avatar
Ondřej Filip committed
273 274
      hn = (struct ospf_lsa_summ_net *) (hs + 1);
      nn = (struct ospf_lsa_summ_net *) (ns + 1);
275

Ondřej Filip's avatar
Ondřej Filip committed
276 277
      for (i = 0; i < ((len - sizeof(struct ospf_lsa_summ)) /
		       sizeof(struct ospf_lsa_summ_net)); i++)
278
      {
Ondřej Filip's avatar
Ondřej Filip committed
279 280 281
	(hn + i)->tos = (nn + i)->tos;
	(hn + i)->metric = ntohs((nn + i)->metric);
	(hn + i)->padding = 0;
282 283 284
      }
      break;
    }
Ondřej Filip's avatar
Ondřej Filip committed
285
  case LSA_T_EXT:
286 287 288 289
    {
      struct ospf_lsa_ext *he, *ne;
      struct ospf_lsa_ext_tos *ht, *nt;

Ondřej Filip's avatar
Ondřej Filip committed
290 291
      he = h;
      ne = n;
292

Ondřej Filip's avatar
Ondřej Filip committed
293
      he->netmask = ne->netmask;
294
      ipa_ntoh(he->netmask);
295

Ondřej Filip's avatar
Ondřej Filip committed
296 297
      ht = (struct ospf_lsa_ext_tos *) (he + 1);
      nt = (struct ospf_lsa_ext_tos *) (ne + 1);
298

Ondřej Filip's avatar
Ondřej Filip committed
299 300
      for (i = 0; i < ((len - sizeof(struct ospf_lsa_ext)) /
		       sizeof(struct ospf_lsa_ext_tos)); i++)
301
      {
Ondřej Filip's avatar
Ondřej Filip committed
302 303 304 305 306 307
	(ht + i)->etos = (nt + i)->etos;
	(ht + i)->padding = 0;
	(ht + i)->metric = ntohs((nt + i)->metric);
	(ht + i)->fwaddr = (nt + i)->fwaddr;
	ipa_ntoh((ht + i)->fwaddr);
	(ht + i)->tag = ntohl((nt + i)->tag);
308 309 310
      }
      break;
    }
Ondřej Filip's avatar
Ondřej Filip committed
311 312
  default:
    bug("(ntoh): Unknown LSA");
313 314 315
  }
};

316 317 318 319 320 321 322 323
#define MODX 4102		/* larges signed value without overflow */

/* Fletcher Checksum -- Refer to RFC1008. */
#define MODX                 4102
#define LSA_CHECKSUM_OFFSET    15

/* FIXME This is VERY uneficient, I have huge endianity problems */
void
Ondřej Filip's avatar
Ondřej Filip committed
324
lsasum_calculate(struct ospf_lsa_header *h, void *body, struct proto_ospf *po)
325 326 327
{
  u16 length;

Ondřej Filip's avatar
Ondřej Filip committed
328 329 330 331
  length = h->length;

  htonlsah(h, h);
  htonlsab(body, body, h->type, length - sizeof(struct ospf_lsa_header));
332

Ondřej Filip's avatar
Ondřej Filip committed
333 334 335 336
  (void) lsasum_check(h, body, po);

  ntohlsah(h, h);
  ntohlsab(body, body, h->type, length - sizeof(struct ospf_lsa_header));
337 338 339 340 341 342 343
}

/*
 * Note, that this function expects that LSA is in big endianity
 * It also returns value in big endian
 */
u16
Ondřej Filip's avatar
Ondřej Filip committed
344
lsasum_check(struct ospf_lsa_header *h, void *body, struct proto_ospf *po)
345 346 347 348
{
  u8 *sp, *ep, *p, *q, *b;
  int c0 = 0, c1 = 0;
  int x, y;
349
  u16 length;
350

351
  b = body;
352
  sp = (char *) &h->options;
Ondřej Filip's avatar
Ondřej Filip committed
353
  length = ntohs(h->length) - 2;
354
  h->checksum = 0;
355 356

  for (ep = sp + length; sp < ep; sp = q)
Ondřej Filip's avatar
Ondřej Filip committed
357
  {				/* Actually MODX is very large, do we need the for-cyclus? */
358
    q = sp + MODX;
Ondřej Filip's avatar
Ondřej Filip committed
359 360
    if (q > ep)
      q = ep;
361
    for (p = sp; p < q; p++)
362
    {
363 364 365 366 367 368
      /* 
       * I count with bytes from header and than from body
       * but if there is no body, it's appended to header
       * (probably checksum in update receiving) and I go on
       * after header
       */
Ondřej Filip's avatar
Ondřej Filip committed
369
      if ((b == NULL) || (p < (u8 *) (h + 1)))
370
      {
Ondřej Filip's avatar
Ondřej Filip committed
371
	c0 += *p;
372 373 374
      }
      else
      {
Ondřej Filip's avatar
Ondřej Filip committed
375
	c0 += *(b + (p - sp) - sizeof(struct ospf_lsa_header) + 2);
376 377 378
      }

      c1 += c0;
379
    }
380 381 382
    c0 %= 255;
    c1 %= 255;
  }
383 384

  x = ((length - LSA_CHECKSUM_OFFSET) * c0 - c1) % 255;
Ondřej Filip's avatar
Ondřej Filip committed
385 386
  if (x <= 0)
    x += 255;
387
  y = 510 - c0 - x;
Ondřej Filip's avatar
Ondřej Filip committed
388 389
  if (y > 255)
    y -= 255;
390

Ondřej Filip's avatar
Ondřej Filip committed
391 392
  ((u8 *) & h->checksum)[0] = x;
  ((u8 *) & h->checksum)[1] = y;
393
  return h->checksum;
394 395
}

Ondřej Filip's avatar
Ondřej Filip committed
396 397
int
lsa_comp(struct ospf_lsa_header *l1, struct ospf_lsa_header *l2)
398
			/* Return codes from point of view of l1 */
Ondřej Filip's avatar
Ondřej Filip committed
399
{
Ondřej Filip's avatar
Ondřej Filip committed
400
  u32 sn1, sn2;
401

Ondřej Filip's avatar
Ondřej Filip committed
402 403
  sn1 = l1->sn - LSA_INITSEQNO + 1;
  sn2 = l2->sn - LSA_INITSEQNO + 1;
404

Ondřej Filip's avatar
Ondřej Filip committed
405 406 407 408
  if (sn1 > sn2)
    return CMP_NEWER;
  if (sn1 < sn2)
    return CMP_OLDER;
Ondřej Filip's avatar
Ondřej Filip committed
409

Ondřej Filip's avatar
Ondřej Filip committed
410 411
  if (l1->checksum != l2->checksum)
    return l1->checksum < l2->checksum ? CMP_OLDER : CMP_NEWER;
Ondřej Filip's avatar
Ondřej Filip committed
412

Ondřej Filip's avatar
Ondřej Filip committed
413 414 415 416
  if ((l1->age == LSA_MAXAGE) && (l2->age != LSA_MAXAGE))
    return CMP_NEWER;
  if ((l2->age == LSA_MAXAGE) && (l1->age != LSA_MAXAGE))
    return CMP_OLDER;
Ondřej Filip's avatar
Ondřej Filip committed
417

Ondřej Filip's avatar
Ondřej Filip committed
418 419
  if (ABS(l1->age - l2->age) > LSA_MAXAGEDIFF)
    return l1->age < l2->age ? CMP_NEWER : CMP_OLDER;
Ondřej Filip's avatar
Ondřej Filip committed
420 421

  return CMP_SAME;
Ondřej Filip's avatar
Ondřej Filip committed
422 423
}

424 425 426
/**
 * lsa_install_new - install new LSA into database
 * @lsa: LSA header
Martin Mareš's avatar
Martin Mareš committed
427
 * @body: pointer to LSA body
428 429 430
 * @oa: current ospf_area
 *
 * This function ensures installing new LSA into LSA database. Old instance is
Ondřej Filip's avatar
Ondřej Filip committed
431
 * replaced. Several actions are taken to detect if new routing table
432 433
 * calculation is necessary. This is described in 13.2 of RFC 2328.
 */
434
struct top_hash_entry *
435
lsa_install_new(struct ospf_lsa_header *lsa, void *body, struct ospf_area *oa)
436
{
437
  /* LSA can be temporarrily, but body must be mb_allocated. */
Ondřej Filip's avatar
Ondřej Filip committed
438
  int change = 0;
439
  unsigned i;
440
  struct top_hash_entry *en;
441
  struct proto_ospf *po = oa->po;
442

Ondřej Filip's avatar
Ondřej Filip committed
443
  if ((en = ospf_hash_find_header(oa->gr, lsa)) == NULL)
444
  {
Ondřej Filip's avatar
Ondřej Filip committed
445 446
    en = ospf_hash_get_header(oa->gr, lsa);
    change = 1;
447 448 449
  }
  else
  {
Ondřej Filip's avatar
Ondřej Filip committed
450 451 452
    if ((en->lsa.length != lsa->length) || (en->lsa.options != lsa->options)
	|| ((en->lsa.age == LSA_MAXAGE) || (lsa->age == LSA_MAXAGE)))
      change = 1;
453 454
    else
    {
Ondřej Filip's avatar
Ondřej Filip committed
455 456
      u8 *k = en->lsa_body, *l = body;
      for (i = 0; i < (lsa->length - sizeof(struct ospf_lsa_header)); i++)
457
      {
Ondřej Filip's avatar
Ondřej Filip committed
458
	if (*(k + i) != *(l + i))
459
	{
Ondřej Filip's avatar
Ondřej Filip committed
460
	  change = 1;
461 462 463
	  break;
	}
      }
464
    }
465
    s_rem_node(SNODE en);
466 467
  }

468
  DBG("Inst lsa: Id: %I, Rt: %I, Type: %u, Age: %u, Sum: %u, Sn: 0x%x\n",
Ondřej Filip's avatar
Ondřej Filip committed
469
      lsa->id, lsa->rt, lsa->type, lsa->age, lsa->checksum, lsa->sn);
470

471
  s_add_tail(&oa->lsal, SNODE en);
Ondřej Filip's avatar
Ondřej Filip committed
472 473 474 475 476 477 478 479
  en->inst_t = now;
  if (en->lsa_body != NULL)
    mb_free(en->lsa_body);
  en->lsa_body = body;
  memcpy(&en->lsa, lsa, sizeof(struct ospf_lsa_header));
  en->ini_age = en->lsa.age;

  if (change)
480
  {
481
    schedule_rtcalc(po);
482
  }
Ondřej Filip's avatar
Ondřej Filip committed
483

484 485
  return en;
}