lsalib.c 10.4 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
    }
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(po, NULL, NULL, &en->lsa, en->domain, 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
  n->age = htons(h->age);
99
#ifdef OSPFv2
Ondřej Filip's avatar
Ondřej Filip committed
100
  n->options = h->options;
101
#endif
102
  n->type = htont(h->type);
Ondřej Filip's avatar
Ondřej Filip committed
103 104 105 106 107
  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);
108 109 110 111 112
};

void
ntohlsah(struct ospf_lsa_header *n, struct ospf_lsa_header *h)
{
Ondřej Filip's avatar
Ondřej Filip committed
113
  h->age = ntohs(n->age);
114
#ifdef OSPFv2
Ondřej Filip's avatar
Ondřej Filip committed
115
  h->options = n->options;
116
#endif
117
  h->type = ntoht(n->type);
Ondřej Filip's avatar
Ondřej Filip committed
118 119 120 121 122
  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);
123 124 125
};

void
126
htonlsab(void *h, void *n, u16 type, u16 len)
127 128
{
  unsigned int i;
129

Ondřej Filip's avatar
Ondřej Filip committed
130
  switch (type)
131
  {
Ondřej Filip's avatar
Ondřej Filip committed
132
  case LSA_T_RT:
133 134
    {
      struct ospf_lsa_rt *hrt, *nrt;
Ondřej Filip's avatar
Ondřej Filip committed
135
      struct ospf_lsa_rt_link *hrtl, *nrtl;
136
      u16 links;
137

Ondřej Filip's avatar
Ondřej Filip committed
138 139
      nrt = n;
      hrt = h;
140

141 142
#ifdef OSPFv2
      links = hrt->links;
143 144
      nrt->options = htons(hrt->options);
      nrt->links = htons(hrt->links);
145
#else /* OSPFv3 */
146
      nrt->options = htonl(hrt->options);
147 148 149 150
      links = (len - sizeof(struct ospf_lsa_rt)) /
	sizeof(struct ospf_lsa_rt_link);
#endif

Ondřej Filip's avatar
Ondřej Filip committed
151 152 153
      nrtl = (struct ospf_lsa_rt_link *) (nrt + 1);
      hrtl = (struct ospf_lsa_rt_link *) (hrt + 1);
      for (i = 0; i < links; i++)
154
      {
155 156 157 158 159 160 161 162 163 164 165 166 167 168
#ifdef OSPFv2
	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);
#else /* OSPFv3 */
	nrtl[i].type = hrtl[i].type;
	nrtl[i].padding = 0;
	nrtl[i].metric = htons(hrtl[i].metric);
	nrtl[i].lif = htonl(hrtl[i].lif);
	nrtl[i].nif = htonl(hrtl[i].nif);
	nrtl[i].id = htonl(hrtl[i].id);
#endif
169 170 171
      }
      break;
    }
Ondřej Filip's avatar
Ondřej Filip committed
172
  case LSA_T_NET:
173 174 175
  case LSA_T_SUM_NET:
  case LSA_T_SUM_RT:
  case LSA_T_EXT:
176 177 178 179
#ifdef OSPFv3
  case LSA_T_LINK:
  case LSA_T_PREFIX:
#endif
180
    {
Ondřej Filip's avatar
Ondřej Filip committed
181
      u32 *hid, *nid;
182

Ondřej Filip's avatar
Ondřej Filip committed
183 184
      nid = n;
      hid = h;
185

Ondřej Filip's avatar
Ondřej Filip committed
186
      for (i = 0; i < (len / sizeof(u32)); i++)
187
      {
Ondřej Filip's avatar
Ondřej Filip committed
188
	*(nid + i) = htonl(*(hid + i));
189 190 191 192
      }
      break;
    }

Ondřej Filip's avatar
Ondřej Filip committed
193 194
  default:
    bug("(hton): Unknown LSA");
195 196 197 198
  }
};

void
199
ntohlsab(void *n, void *h, u16 type, u16 len)
200 201
{
  unsigned int i;
Ondřej Filip's avatar
Ondřej Filip committed
202
  switch (type)
203
  {
Ondřej Filip's avatar
Ondřej Filip committed
204
  case LSA_T_RT:
205 206
    {
      struct ospf_lsa_rt *hrt, *nrt;
Ondřej Filip's avatar
Ondřej Filip committed
207
      struct ospf_lsa_rt_link *hrtl, *nrtl;
208
      u16 links;
209

Ondřej Filip's avatar
Ondřej Filip committed
210 211
      nrt = n;
      hrt = h;
212

213
#ifdef OSPFv2
214
      hrt->options = ntohs(nrt->options);
Ondřej Filip's avatar
Ondřej Filip committed
215
      links = hrt->links = ntohs(nrt->links);
216 217 218 219 220 221
#else /* OSPFv3 */
      hrt->options = ntohl(nrt->options);
      links = (len - sizeof(struct ospf_lsa_rt)) /
	sizeof(struct ospf_lsa_rt_link);
#endif

Ondřej Filip's avatar
Ondřej Filip committed
222 223 224
      nrtl = (struct ospf_lsa_rt_link *) (nrt + 1);
      hrtl = (struct ospf_lsa_rt_link *) (hrt + 1);
      for (i = 0; i < links; i++)
225
      {
226 227 228 229 230 231 232 233 234 235 236 237 238 239
#ifdef OSPFv2
	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);
#else /* OSPFv3 */
	hrtl[i].type = nrtl[i].type;
	hrtl[i].padding = 0;
	hrtl[i].metric = ntohs(nrtl[i].metric);
	hrtl[i].lif = ntohl(nrtl[i].lif);
	hrtl[i].nif = ntohl(nrtl[i].nif);
	hrtl[i].id = ntohl(nrtl[i].id);
#endif
240 241 242
      }
      break;
    }
Ondřej Filip's avatar
Ondřej Filip committed
243
  case LSA_T_NET:
244 245 246
  case LSA_T_SUM_NET:
  case LSA_T_SUM_RT:
  case LSA_T_EXT:
247 248 249 250
#ifdef OSPFv3
  case LSA_T_LINK:
  case LSA_T_PREFIX:
#endif
251
    {
Ondřej Filip's avatar
Ondřej Filip committed
252
      u32 *hid, *nid;
253

Ondřej Filip's avatar
Ondřej Filip committed
254 255
      hid = h;
      nid = n;
256

Ondřej Filip's avatar
Ondřej Filip committed
257
      for (i = 0; i < (len / sizeof(u32)); i++)
258
      {
259
	hid[i] = ntohl(nid[i]);
260 261 262
      }
      break;
    }
Ondřej Filip's avatar
Ondřej Filip committed
263 264
  default:
    bug("(ntoh): Unknown LSA");
265 266 267
  }
};

268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296
void
buf_dump(const char *hdr, const byte *buf, int blen)
{
  char b2[1024];
  char *bp;
  int first = 1;
  int i;

  const char *lhdr = hdr;

  bp = b2;
  for(i = 0; i < blen; i++)
    {
      if ((i > 0) && ((i % 16) == 0))
	{
	      *bp = 0;
	      log(L_WARN "%s\t%s", lhdr, b2);
	      lhdr = "";
	      bp = b2;
	}

      bp += snprintf(bp, 1022, "%02x ", buf[i]);

    }

  *bp = 0;
  log(L_WARN "%s\t%s", lhdr, b2);
}

297 298 299 300 301 302 303 304
#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
305
lsasum_calculate(struct ospf_lsa_header *h, void *body)
306
{
307 308
  u16 length = h->length;
  u16 type = h->type;
Ondřej Filip's avatar
Ondřej Filip committed
309

310
  //  log(L_WARN "Checksum %R %R %d start (len %d)", h->id, h->rt, h->type, length);
Ondřej Filip's avatar
Ondřej Filip committed
311
  htonlsah(h, h);
312 313
  htonlsab(body, body, type, length - sizeof(struct ospf_lsa_header));

314
  /*
315 316 317 318
  char buf[1024];
  memcpy(buf, h, sizeof(struct ospf_lsa_header));
  memcpy(buf + sizeof(struct ospf_lsa_header), body, length - sizeof(struct ospf_lsa_header));
  buf_dump("CALC", buf, length);
319
  */
320

321
  (void) lsasum_check(h, body);
Ondřej Filip's avatar
Ondřej Filip committed
322

323
  //  log(L_WARN "Checksum result %4x", h->checksum);
324

Ondřej Filip's avatar
Ondřej Filip committed
325
  ntohlsah(h, h);
326
  ntohlsab(body, body, type, length - sizeof(struct ospf_lsa_header));
327 328 329 330 331 332 333
}

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

341
  b = body;
342
  sp = (char *) h;
343
  sp += 2; /* Skip Age field */
Ondřej Filip's avatar
Ondřej Filip committed
344
  length = ntohs(h->length) - 2;
345
  h->checksum = 0;
346 347

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

      c1 += c0;
370
    }
371 372 373
    c0 %= 255;
    c1 %= 255;
  }
374 375

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

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

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

Ondřej Filip's avatar
Ondřej Filip committed
393 394
  sn1 = l1->sn - LSA_INITSEQNO + 1;
  sn2 = l2->sn - LSA_INITSEQNO + 1;
395

Ondřej Filip's avatar
Ondřej Filip committed
396 397 398 399
  if (sn1 > sn2)
    return CMP_NEWER;
  if (sn1 < sn2)
    return CMP_OLDER;
Ondřej Filip's avatar
Ondřej Filip committed
400

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

Ondřej Filip's avatar
Ondřej Filip committed
404 405 406 407
  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
408

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

  return CMP_SAME;
413 414
}

415 416
/**
 * lsa_install_new - install new LSA into database
417
 * @po: OSPF protocol
418
 * @lsa: LSA header
419
 * @domain: domain of LSA
Martin Mareš's avatar
Martin Mareš committed
420
 * @body: pointer to LSA body
421

422 423
 *
 * This function ensures installing new LSA into LSA database. Old instance is
Ondřej Filip's avatar
Ondřej Filip committed
424
 * replaced. Several actions are taken to detect if new routing table
425 426
 * calculation is necessary. This is described in 13.2 of RFC 2328.
 */
427
struct top_hash_entry *
428
lsa_install_new(struct proto_ospf *po, struct ospf_lsa_header *lsa, u32 domain, void *body)
429
{
430
  /* LSA can be temporarrily, but body must be mb_allocated. */
Ondřej Filip's avatar
Ondřej Filip committed
431
  int change = 0;
432 433
  struct top_hash_entry *en;

434
  if ((en = ospf_hash_find_header(po->gr, domain, lsa)) == NULL)
435
  {
436
    en = ospf_hash_get_header(po->gr, domain, lsa);
Ondřej Filip's avatar
Ondřej Filip committed
437
    change = 1;
438 439 440
  }
  else
  {
441 442 443 444 445 446 447
    if ((en->lsa.length != lsa->length)
#ifdef OSPFv2       
	|| (en->lsa.options != lsa->options)
#endif
	|| (en->lsa.age == LSA_MAXAGE)
	|| (lsa->age == LSA_MAXAGE)
	|| memcmp(en->lsa_body, body, lsa->length - sizeof(struct ospf_lsa_header)))
Ondřej Filip's avatar
Ondřej Filip committed
448
      change = 1;
449

450
    s_rem_node(SNODE en);
451 452
  }

453 454
  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);
455

456
  s_add_tail(&po->lsal, SNODE en);
Ondřej Filip's avatar
Ondřej Filip committed
457 458 459 460 461 462 463 464
  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)
465
    schedule_rtcalc(po);
Ondřej Filip's avatar
Ondřej Filip committed
466

467 468
  return en;
}