lsalib.c 11 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"

11
void
12
flush_lsa(struct top_hash_entry *en, struct proto_ospf *po)
13
{
14 15
  struct proto *p = &po->proto;

Ondřej Filip's avatar
Ondřej Filip committed
16
  OSPF_TRACE(D_EVENTS,
17 18
	     "Going to remove node Type: %u, Id: %R, Rt: %R, Age: %u, SN: 0x%x",
	     en->lsa.type, en->lsa.id, en->lsa.rt, en->lsa.age, en->lsa.sn);
19
  s_rem_node(SNODE en);
Ondřej Filip's avatar
Ondřej Filip committed
20 21 22
  if (en->lsa_body != NULL)
    mb_free(en->lsa_body);
  en->lsa_body = NULL;
23
  ospf_hash_delete(po->gr, en);
24 25
}

26 27
/**
 * ospf_age
28
 * @po: ospf protocol
29
 *
30
 * This function is periodicaly invoked from ospf_disp(). It computes the new
31 32 33
 * 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.
34
 *
35 36
 * 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.
37
 *
38
 * If routing table calculation is scheduled, it also invalidates the old routing
39
 * table calculation results.
40
 */
41
void
42
ospf_age(struct proto_ospf *po)
43
{
44
  struct proto *p = &po->proto;
Ondřej Filip's avatar
Ondřej Filip committed
45
  struct top_hash_entry *en, *nxt;
46
  int flush = can_flush_lsa(po);
Ondřej Filip's avatar
Ondřej Filip committed
47

48
  if (po->cleanup) OSPF_TRACE(D_EVENTS, "Running ospf_age cleanup");
Ondřej Filip's avatar
Ondřej Filip committed
49

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

95 96 97
void
htonlsah(struct ospf_lsa_header *h, struct ospf_lsa_header *n)
{
Ondřej Filip's avatar
Ondřej Filip committed
98 99 100 101 102 103 104 105
  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);
106 107 108 109 110
};

void
ntohlsah(struct ospf_lsa_header *n, struct ospf_lsa_header *h)
{
Ondřej Filip's avatar
Ondřej Filip committed
111 112 113 114 115 116 117 118
  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);
119 120 121 122 123 124
};

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

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

Ondřej Filip's avatar
Ondřej Filip committed
137 138 139 140 141 142
      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++)
143
      {
Ondřej Filip's avatar
Ondřej Filip committed
144 145 146 147 148
	(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);
149 150 151
      }
      break;
    }
Ondřej Filip's avatar
Ondřej Filip committed
152
  case LSA_T_NET:
153
    {
Ondřej Filip's avatar
Ondřej Filip committed
154
      u32 *hid, *nid;
155

Ondřej Filip's avatar
Ondřej Filip committed
156 157
      nid = n;
      hid = h;
158

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

Ondřej Filip's avatar
Ondřej Filip committed
171 172
      hs = h;
      ns = n;
173

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

Ondřej Filip's avatar
Ondřej Filip committed
177 178
      hn = (union ospf_lsa_sum_tm *) (hs + 1);
      nn = (union ospf_lsa_sum_tm *) (ns + 1);
179

Ondřej Filip's avatar
Ondřej Filip committed
180 181
      for (i = 0; i < ((len - sizeof(struct ospf_lsa_sum)) /
		       sizeof(union ospf_lsa_sum_tm)); i++)
182
      {
Ondřej Filip's avatar
Ondřej Filip committed
183
	(nn + i)->metric = htonl((hn + i)->metric);
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
	(nt + i)->etm.metric = htonl((ht + i)->etm.metric);
Ondřej Filip's avatar
Ondřej Filip committed
205 206 207
	(nt + i)->fwaddr = (ht + i)->fwaddr;
	ipa_hton((nt + i)->fwaddr);
	(nt + i)->tag = htonl((ht + i)->tag);
208 209 210
      }
      break;
    }
Ondřej Filip's avatar
Ondřej Filip committed
211 212
  default:
    bug("(hton): Unknown LSA");
213 214 215 216 217 218 219
  }
};

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

Ondřej Filip's avatar
Ondřej Filip committed
228 229
      nrt = n;
      hrt = h;
230

Ondřej Filip's avatar
Ondřej Filip committed
231 232 233 234 235 236
      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++)
237
      {
Ondřej Filip's avatar
Ondřej Filip committed
238 239 240 241 242
	(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);
243 244 245
      }
      break;
    }
Ondřej Filip's avatar
Ondřej Filip committed
246
  case LSA_T_NET:
247
    {
Ondřej Filip's avatar
Ondřej Filip committed
248
      u32 *hid, *nid;
249

Ondřej Filip's avatar
Ondřej Filip committed
250 251
      hid = h;
      nid = n;
252

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

Ondřej Filip's avatar
Ondřej Filip committed
265 266
      hs = h;
      ns = n;
267

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

Ondřej Filip's avatar
Ondřej Filip committed
271 272
      hn = (union ospf_lsa_sum_tm *) (hs + 1);
      nn = (union ospf_lsa_sum_tm *) (ns + 1);
273

Ondřej Filip's avatar
Ondřej Filip committed
274 275
      for (i = 0; i < ((len - sizeof(struct ospf_lsa_sum)) /
		       sizeof(union ospf_lsa_sum_tm)); i++)
276
      {
Ondřej Filip's avatar
Ondřej Filip committed
277
	(hn + i)->metric = ntohl((nn + i)->metric);
278 279 280
      }
      break;
    }
Ondřej Filip's avatar
Ondřej Filip committed
281
  case LSA_T_EXT:
282 283 284 285
    {
      struct ospf_lsa_ext *he, *ne;
      struct ospf_lsa_ext_tos *ht, *nt;

Ondřej Filip's avatar
Ondřej Filip committed
286 287
      he = h;
      ne = n;
288

Ondřej Filip's avatar
Ondřej Filip committed
289
      he->netmask = ne->netmask;
290
      ipa_ntoh(he->netmask);
291

Ondřej Filip's avatar
Ondřej Filip committed
292 293
      ht = (struct ospf_lsa_ext_tos *) (he + 1);
      nt = (struct ospf_lsa_ext_tos *) (ne + 1);
294

Ondřej Filip's avatar
Ondřej Filip committed
295 296
      for (i = 0; i < ((len - sizeof(struct ospf_lsa_ext)) /
		       sizeof(struct ospf_lsa_ext_tos)); i++)
297
      {
Ondřej Filip's avatar
Ondřej Filip committed
298
	(ht + i)->etm.metric = ntohl((nt + i)->etm.metric);
Ondřej Filip's avatar
Ondřej Filip committed
299 300 301
	(ht + i)->fwaddr = (nt + i)->fwaddr;
	ipa_ntoh((ht + i)->fwaddr);
	(ht + i)->tag = ntohl((nt + i)->tag);
302 303 304
      }
      break;
    }
Ondřej Filip's avatar
Ondřej Filip committed
305 306
  default:
    bug("(ntoh): Unknown LSA");
307 308 309
  }
};

310 311 312 313 314 315 316 317
#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
318
lsasum_calculate(struct ospf_lsa_header *h, void *body)
319 320 321
{
  u16 length;

Ondřej Filip's avatar
Ondřej Filip committed
322 323 324 325
  length = h->length;

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

327
  (void) lsasum_check(h, body);
Ondřej Filip's avatar
Ondřej Filip committed
328 329 330

  ntohlsah(h, h);
  ntohlsab(body, body, h->type, length - sizeof(struct ospf_lsa_header));
331 332 333 334 335 336 337
}

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

345
  b = body;
346
  sp = (char *) &h->options;
Ondřej Filip's avatar
Ondřej Filip committed
347
  length = ntohs(h->length) - 2;
348
  h->checksum = 0;
349 350

  for (ep = sp + length; sp < ep; sp = q)
Ondřej Filip's avatar
Ondřej Filip committed
351
  {				/* Actually MODX is very large, do we need the for-cyclus? */
352
    q = sp + MODX;
Ondřej Filip's avatar
Ondřej Filip committed
353 354
    if (q > ep)
      q = ep;
355
    for (p = sp; p < q; p++)
356
    {
357 358 359 360 361 362
      /* 
       * 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
363
      if ((b == NULL) || (p < (u8 *) (h + 1)))
364
      {
Ondřej Filip's avatar
Ondřej Filip committed
365
	c0 += *p;
366 367 368
      }
      else
      {
Ondřej Filip's avatar
Ondřej Filip committed
369
	c0 += *(b + (p - sp) - sizeof(struct ospf_lsa_header) + 2);
370 371 372
      }

      c1 += c0;
373
    }
374 375 376
    c0 %= 255;
    c1 %= 255;
  }
377 378

  x = ((length - LSA_CHECKSUM_OFFSET) * c0 - c1) % 255;
Ondřej Filip's avatar
Ondřej Filip committed
379 380
  if (x <= 0)
    x += 255;
381
  y = 510 - c0 - x;
Ondřej Filip's avatar
Ondřej Filip committed
382 383
  if (y > 255)
    y -= 255;
384

Ondřej Filip's avatar
Ondřej Filip committed
385 386
  ((u8 *) & h->checksum)[0] = x;
  ((u8 *) & h->checksum)[1] = y;
387
  return h->checksum;
388 389
}

390 391
int
lsa_comp(struct ospf_lsa_header *l1, struct ospf_lsa_header *l2)
392
			/* Return codes from point of view of l1 */
393
{
Ondřej Filip's avatar
Ondřej Filip committed
394
  u32 sn1, sn2;
395

Ondřej Filip's avatar
Ondřej Filip committed
396 397
  sn1 = l1->sn - LSA_INITSEQNO + 1;
  sn2 = l2->sn - LSA_INITSEQNO + 1;
398

Ondřej Filip's avatar
Ondřej Filip committed
399 400 401 402
  if (sn1 > sn2)
    return CMP_NEWER;
  if (sn1 < sn2)
    return CMP_OLDER;
Ondřej Filip's avatar
Ondřej Filip committed
403

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

Ondřej Filip's avatar
Ondřej Filip committed
407 408 409 410
  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
411

Ondřej Filip's avatar
Ondřej Filip committed
412 413
  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
414 415

  return CMP_SAME;
416 417
}

418 419 420
/**
 * lsa_install_new - install new LSA into database
 * @lsa: LSA header
Martin Mareš's avatar
Martin Mareš committed
421
 * @body: pointer to LSA body
422 423 424
 * @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
425
 * replaced. Several actions are taken to detect if new routing table
426 427
 * calculation is necessary. This is described in 13.2 of RFC 2328.
 */
428
struct top_hash_entry *
429
lsa_install_new(struct ospf_lsa_header *lsa, void *body, struct ospf_area *oa)
430
{
431
  /* LSA can be temporarrily, but body must be mb_allocated. */
Ondřej Filip's avatar
Ondřej Filip committed
432
  int change = 0;
433
  unsigned i;
434
  struct top_hash_entry *en;
435
  struct proto_ospf *po = oa->po;
436

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

462 463
  DBG("Inst lsa: Id: %R, Rt: %R, Type: %u, Age: %u, Sum: %u, Sn: 0x%x\n",
      lsa->id, lsa->rt, lsa->type, lsa->age, lsa->checksum, lsa->sn);
464

465
  s_add_tail(&po->lsal, SNODE en);
Ondřej Filip's avatar
Ondřej Filip committed
466 467 468 469 470 471 472 473
  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)
474
  {
475
    schedule_rtcalc(po);
476
  }
Ondřej Filip's avatar
Ondřej Filip committed
477

478 479
  return en;
}