lsalib.c 13.3 KB
Newer Older
1 2 3
/*
 *	BIRD -- OSPF
 *
4
 *	(c) 1999--2004 Ondrej Filip <feela@network.cz>
5 6
 *	(c) 2009--2015 Ondrej Zajicek <santiago@crfreenet.org>
 *	(c) 2009--2015 CZ.NIC z.s.p.o.
7 8 9 10 11 12
 *
 *	Can be freely distributed and used under the terms of the GNU GPL.
 */

#include "ospf.h"

13
#include "lib/fletcher16.h"
14

15
#ifndef CPU_BIG_ENDIAN
16
void
17
lsa_hton_hdr(struct ospf_lsa_header *h, struct ospf_lsa_header *n)
18
{
Ondřej Filip's avatar
Ondřej Filip committed
19
  n->age = htons(h->age);
20
  n->type_raw = htons(h->type_raw);
Ondřej Filip's avatar
Ondřej Filip committed
21 22 23 24 25
  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);
26
}
27 28

void
29
lsa_ntoh_hdr(struct ospf_lsa_header *n, struct ospf_lsa_header *h)
30
{
Ondřej Filip's avatar
Ondřej Filip committed
31
  h->age = ntohs(n->age);
32
  h->type_raw = ntohs(n->type_raw);
Ondřej Filip's avatar
Ondřej Filip committed
33 34 35 36 37
  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);
38
}
39 40

void
41
lsa_hton_body(void *h, void *n, u16 len)
42
{
43 44
  u32 *hid = h;
  u32 *nid = n;
45
  uint i;
46

47 48 49
  for (i = 0; i < (len / sizeof(u32)); i++)
    nid[i] = htonl(hid[i]);
}
50 51

void
52
lsa_ntoh_body(void *n, void *h, u16 len)
53
{
54 55
  u32 *nid = n;
  u32 *hid = h;
56
  uint i;
57

58 59 60
  for (i = 0; i < (len / sizeof(u32)); i++)
    hid[i] = ntohl(nid[i]);
}
61
#endif /* little endian */
62

63 64 65 66


int
lsa_flooding_allowed(u32 type, u32 domain, struct ospf_iface *ifa)
67
{
68 69 70
  /* Handle inactive vlinks */
  if (ifa->state == OSPF_IS_DOWN)
    return 0;
71

72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153
  /* 4.5.2 (Case 2) */
  switch (LSA_SCOPE(type))
  {
  case LSA_SCOPE_LINK:
    return ifa->iface_id == domain;

  case LSA_SCOPE_AREA:
    return ifa->oa->areaid == domain;

  case LSA_SCOPE_AS:
    if (ifa->type == OSPF_IT_VLINK)
      return 0;
    if (!oa_is_ext(ifa->oa))
      return 0;
    return 1;

  default:
    log(L_ERR "OSPF: LSA with invalid scope");
    return 0;
  }
}


static int
unknown_lsa_type(u32 type)
{
  switch (type)
  {
  case LSA_T_RT:
  case LSA_T_NET:
  case LSA_T_SUM_NET:
  case LSA_T_SUM_RT:
  case LSA_T_EXT:
  case LSA_T_NSSA:
  case LSA_T_LINK:
  case LSA_T_PREFIX:
    return 0;

  default:
    return 1;
  }
}

#define LSA_V2_TMAX 8
static const u16 lsa_v2_types[LSA_V2_TMAX] =
  {0, LSA_T_RT, LSA_T_NET, LSA_T_SUM_NET, LSA_T_SUM_RT, LSA_T_EXT, 0, LSA_T_NSSA};

void
lsa_get_type_domain_(u32 itype, struct ospf_iface *ifa, u32 *otype, u32 *domain)
{
  if (ospf_is_v2(ifa->oa->po))
  {
    itype = itype & LSA_T_V2_MASK;
    itype = (itype < LSA_V2_TMAX) ? lsa_v2_types[itype] : 0;
  }
  else
  {
    /* For unkown LSAs without U-bit change scope to LSA_SCOPE_LINK */
    if (unknown_lsa_type(itype) && !(itype & LSA_UBIT))
      itype = itype & ~LSA_SCOPE_MASK;
  }

  *otype = itype;

  switch (LSA_SCOPE(itype))
  {
  case LSA_SCOPE_LINK:
    *domain = ifa->iface_id;
    return;

  case LSA_SCOPE_AREA:
    *domain = ifa->oa->areaid;
    return;

  case LSA_SCOPE_AS:
  default:
    *domain = 0;
    return;
  }
}


154
void
155
lsa_generate_checksum(struct ospf_lsa_header *lsa, const u8 *body)
156
{
157 158 159
  struct fletcher16_context ctx;
  struct ospf_lsa_header hdr;
  u16 len = lsa->length;
160

161
  /*
162 163 164
   * lsa and body are in the host order, we need to compute Fletcher-16 checksum
   * for data in the network order. We also skip the initial age field.
   */
165

166 167
  lsa_hton_hdr(lsa, &hdr);
  hdr.checksum = 0;
Ondřej Filip's avatar
Ondřej Filip committed
168

169 170 171 172
  fletcher16_init(&ctx);
  fletcher16_update(&ctx, (u8 *) &hdr + 2, sizeof(struct ospf_lsa_header) - 2);
  fletcher16_update_n32(&ctx, body, len - sizeof(struct ospf_lsa_header));
  lsa->checksum = fletcher16_final(&ctx, len, OFFSETOF(struct ospf_lsa_header, checksum));
173 174 175
}

u16
176
lsa_verify_checksum(const void *lsa_n, int lsa_len)
177
{
178
  struct fletcher16_context ctx;
179

180
  /* The whole LSA is at lsa_n in net order, we just skip initial age field */
181

182 183
  fletcher16_init(&ctx);
  fletcher16_update(&ctx, (u8 *) lsa_n + 2, lsa_len - 2);
184

185
  return fletcher16_compute(&ctx) == 0;
186 187
}

188

189 190
int
lsa_comp(struct ospf_lsa_header *l1, struct ospf_lsa_header *l2)
191
			/* Return codes from point of view of l1 */
192
{
Ondřej Filip's avatar
Ondřej Filip committed
193
  u32 sn1, sn2;
194

Ondřej Filip's avatar
Ondřej Filip committed
195 196
  sn1 = l1->sn - LSA_INITSEQNO + 1;
  sn2 = l2->sn - LSA_INITSEQNO + 1;
197

Ondřej Filip's avatar
Ondřej Filip committed
198 199 200 201
  if (sn1 > sn2)
    return CMP_NEWER;
  if (sn1 < sn2)
    return CMP_OLDER;
Ondřej Filip's avatar
Ondřej Filip committed
202

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

Ondřej Filip's avatar
Ondřej Filip committed
206 207 208 209
  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
210

Ondřej Filip's avatar
Ondřej Filip committed
211 212
  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
213 214

  return CMP_SAME;
215 216
}

217

218 219
static inline int
lsa_walk_rt2(struct ospf_lsa_rt_walk *rt)
220
{
221
  if (rt->buf >= rt->bufend)
222 223
    return 0;

224 225
  struct ospf_lsa_rt2_link *l = rt->buf;
  rt->buf += sizeof(struct ospf_lsa_rt2_link) + l->no_tos * sizeof(struct ospf_lsa_rt2_tos);
226

227 228 229 230 231 232
  rt->type = l->type;
  rt->metric = l->metric;
  rt->id = l->id;
  rt->data = l->data;
  return 1;
}
233

234 235 236 237
static inline int
lsa_walk_rt3(struct ospf_lsa_rt_walk *rt)
{
  while (rt->buf >= rt->bufend)
238
  {
239 240
    rt->en = ospf_hash_find_rt3_next(rt->en);
    if (!rt->en)
241
      return 0;
242 243 244 245

    rt->buf = rt->en->lsa_body;
    rt->bufend = rt->buf + rt->en->lsa.length - sizeof(struct ospf_lsa_header);
    rt->buf += sizeof(struct ospf_lsa_rt);
246
  }
247 248 249 250 251 252 253 254 255

  struct ospf_lsa_rt3_link *l = rt->buf;
  rt->buf += sizeof(struct ospf_lsa_rt3_link);

  rt->type = l->type;
  rt->metric = l->metric;
  rt->lif = l->lif;
  rt->nif = l->nif;
  rt->id = l->id;
256 257 258
  return 1;
}

259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282
void
lsa_walk_rt_init(struct ospf_proto *p, struct top_hash_entry *act, struct ospf_lsa_rt_walk *rt)
{
  rt->ospf2 = ospf_is_v2(p);
  rt->id = rt->data = rt->lif = rt->nif = 0;

  if (rt->ospf2)
    rt->en = act;
  else
    rt->en = ospf_hash_find_rt3_first(p->gr, act->domain, act->lsa.rt);

  rt->buf = rt->en->lsa_body;
  rt->bufend = rt->buf + rt->en->lsa.length - sizeof(struct ospf_lsa_header);
  rt->buf += sizeof(struct ospf_lsa_rt);
}

int
lsa_walk_rt(struct ospf_lsa_rt_walk *rt)
{
  return rt->ospf2 ? lsa_walk_rt2(rt) : lsa_walk_rt3(rt);
}


void
283
lsa_parse_sum_net(struct top_hash_entry *en, int ospf2, int af, net_addr *net, u8 *pxopts, u32 *metric)
284 285 286 287
{
  if (ospf2)
  {
    struct ospf_lsa_sum2 *ls = en->lsa_body;
288
    net_fill_ip4(net, ip4_from_u32(en->lsa.id & ls->netmask), u32_masklen(ls->netmask));
289 290 291 292 293 294
    *pxopts = 0;
    *metric = ls->metric & LSA_METRIC_MASK;
  }
  else
  {
    struct ospf_lsa_sum3_net *ls = en->lsa_body;
295
    ospf3_get_prefix(ls->prefix, af, net, pxopts, NULL);
296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319
    *metric = ls->metric & LSA_METRIC_MASK;
  }
}

void
lsa_parse_sum_rt(struct top_hash_entry *en, int ospf2, u32 *drid, u32 *metric, u32 *options)
{
  if (ospf2)
  {
    struct ospf_lsa_sum2 *ls = en->lsa_body;
    *drid = en->lsa.id;
    *metric = ls->metric & LSA_METRIC_MASK;
    *options = 0;
  }
  else
  {
    struct ospf_lsa_sum3_rt *ls = en->lsa_body;
    *drid = ls->drid;
    *metric = ls->metric & LSA_METRIC_MASK;
    *options = ls->options & LSA_OPTIONS_MASK;
  }
}

void
320
lsa_parse_ext(struct top_hash_entry *en, int ospf2, int af, struct ospf_lsa_ext_local *rt)
321 322 323 324
{
  if (ospf2)
  {
    struct ospf_lsa_ext2 *ext = en->lsa_body;
325 326 327
    net_fill_ip4(&rt->net,
		 ip4_from_u32(en->lsa.id & ext->netmask),
		 u32_masklen(ext->netmask));
328 329 330 331 332 333 334 335 336 337 338 339 340
    rt->pxopts = 0;
    rt->metric = ext->metric & LSA_METRIC_MASK;
    rt->ebit = ext->metric & LSA_EXT2_EBIT;

    rt->fbit = ext->fwaddr;
    rt->fwaddr = ipa_from_u32(ext->fwaddr);

    rt->tag = ext->tag;
    rt->propagate = lsa_get_options(&en->lsa) & OPT_P;
  }
  else
  {
    struct ospf_lsa_ext3 *ext = en->lsa_body;
341
    u32 *buf = ospf3_get_prefix(ext->rest, af, &rt->net, &rt->pxopts, NULL);
342 343 344 345 346
    rt->metric = ext->metric & LSA_METRIC_MASK;
    rt->ebit = ext->metric & LSA_EXT3_EBIT;

    rt->fbit = ext->metric & LSA_EXT3_FBIT;
    if (rt->fbit)
347
      buf = ospf3_get_addr(buf, af, &rt->fwaddr);
348
    else
349 350 351 352 353 354 355 356 357
      rt->fwaddr = IPA_NONE;

    rt->tag = (ext->metric & LSA_EXT3_TBIT) ? *buf++ : 0;
    rt->propagate = rt->pxopts & OPT_PX_P;
  }
}

#define HDRLEN sizeof(struct ospf_lsa_header)

358
static int
359
lsa_validate_rt2(struct ospf_lsa_header *lsa, struct ospf_lsa_rt *body)
360
{
361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385
  if (lsa->length < (HDRLEN + sizeof(struct ospf_lsa_rt)))
    return 0;

  uint i = 0;
  void *buf = body;
  void *bufend = buf + lsa->length - HDRLEN;
  buf += sizeof(struct ospf_lsa_rt);

  while (buf < bufend)
  {
    struct ospf_lsa_rt2_link *l = buf;
    buf += sizeof(struct ospf_lsa_rt2_link) + l->no_tos * sizeof(struct ospf_lsa_rt2_tos);
    i++;

    if (buf > bufend)
      return 0;

    if (!((l->type == LSART_PTP) ||
	  (l->type == LSART_NET) ||
	  (l->type == LSART_STUB) ||
	  (l->type == LSART_VLNK)))
      return 0;
  }

  if ((body->options & LSA_RT2_LINKS) != i)
386 387 388 389 390 391 392
    return 0;

  return 1;
}


static int
393
lsa_validate_rt3(struct ospf_lsa_header *lsa, struct ospf_lsa_rt *body)
394
{
395
  if (lsa->length < (HDRLEN + sizeof(struct ospf_lsa_rt)))
396 397
    return 0;

398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421
  void *buf = body;
  void *bufend = buf + lsa->length - HDRLEN;
  buf += sizeof(struct ospf_lsa_rt);

  while (buf < bufend)
  {
    struct ospf_lsa_rt3_link *l = buf;
    buf += sizeof(struct ospf_lsa_rt3_link);

    if (buf > bufend)
      return 0;

    if (!((l->type == LSART_PTP) ||
	  (l->type == LSART_NET) ||
	  (l->type == LSART_VLNK)))
      return 0;
  }
  return 1;
}

static int
lsa_validate_net(struct ospf_lsa_header *lsa, struct ospf_lsa_net *body UNUSED)
{
  if (lsa->length < (HDRLEN + sizeof(struct ospf_lsa_net)))
422 423 424 425 426 427
    return 0;

  return 1;
}

static int
428
lsa_validate_sum2(struct ospf_lsa_header *lsa, struct ospf_lsa_sum2 *body)
429
{
430
  if (lsa->length < (HDRLEN + sizeof(struct ospf_lsa_sum2)))
431 432 433
    return 0;

  /* First field should have TOS = 0, we ignore other TOS fields */
434
  if ((body->metric & LSA_SUM2_TOS) != 0)
435 436 437 438 439 440 441 442 443 444 445 446
    return 0;

  return 1;
}

static inline int
pxlen(u32 *buf)
{
  return *buf >> 24;
}

static int
447
lsa_validate_sum3_net(struct ospf_lsa_header *lsa, struct ospf_lsa_sum3_net *body)
448
{
449
  if (lsa->length < (HDRLEN + sizeof(struct ospf_lsa_sum3_net) + 4))
450 451 452
    return 0;

  u8 pxl = pxlen(body->prefix);
453
  if (pxl > IP6_MAX_PREFIX_LENGTH)
454 455
    return 0;

456
  if (lsa->length != (HDRLEN + sizeof(struct ospf_lsa_sum3_net) +
457 458 459 460 461 462
		      IPV6_PREFIX_SPACE(pxl)))
    return 0;

  return 1;
}

463
static int
464
lsa_validate_sum3_rt(struct ospf_lsa_header *lsa, struct ospf_lsa_sum3_rt *body UNUSED)
465 466 467 468 469 470
{
  if (lsa->length != (HDRLEN + sizeof(struct ospf_lsa_sum3_rt)))
    return 0;

  return 1;
}
471 472

static int
473
lsa_validate_ext2(struct ospf_lsa_header *lsa, struct ospf_lsa_ext2 *body)
474
{
475 476 477 478 479
  if (lsa->length < (HDRLEN + sizeof(struct ospf_lsa_ext2)))
    return 0;

  /* First field should have TOS = 0, we ignore other TOS fields */
  if ((body->metric & LSA_EXT2_TOS) != 0)
480 481 482 483 484 485
    return 0;

  return 1;
}

static int
486
lsa_validate_ext3(struct ospf_lsa_header *lsa, struct ospf_lsa_ext3 *body)
487
{
488
  if (lsa->length < (HDRLEN + sizeof(struct ospf_lsa_ext3) + 4))
489 490 491
    return 0;

  u8 pxl = pxlen(body->rest);
492
  if (pxl > IP6_MAX_PREFIX_LENGTH)
493 494 495
    return 0;

  int len = IPV6_PREFIX_SPACE(pxl);
496
  if (body->metric & LSA_EXT3_FBIT) // forwarding address
497
    len += 16;
498
  if (body->metric & LSA_EXT3_TBIT) // route tag
499 500 501 502
    len += 4;
  if (*body->rest & 0xFFFF) // referenced LS type field
    len += 4;

503
  if (lsa->length != (HDRLEN + sizeof(struct ospf_lsa_ext3) + len))
504 505 506 507 508 509
    return 0;

  return 1;
}

static int
510
lsa_validate_pxlist(struct ospf_lsa_header *lsa, u32 pxcount, uint offset, u8 *pbuf)
511
{
512
  uint bound = lsa->length - HDRLEN - 4;
513 514 515 516 517 518 519 520
  u32 i;

  for (i = 0; i < pxcount; i++)
    {
      if (offset > bound)
	return 0;

      u8 pxl = pxlen((u32 *) (pbuf + offset));
521
      if (pxl > IP6_MAX_PREFIX_LENGTH)
522
	return 0;
523

524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554
      offset += IPV6_PREFIX_SPACE(pxl);
    }

  if (lsa->length != (HDRLEN + offset))
    return 0;

  return 1;
}

static int
lsa_validate_link(struct ospf_lsa_header *lsa, struct ospf_lsa_link *body)
{
  if (lsa->length < (HDRLEN + sizeof(struct ospf_lsa_link)))
    return 0;

  return lsa_validate_pxlist(lsa, body->pxcount, sizeof(struct ospf_lsa_link), (u8 *) body);
}

static int
lsa_validate_prefix(struct ospf_lsa_header *lsa, struct ospf_lsa_prefix *body)
{
  if (lsa->length < (HDRLEN + sizeof(struct ospf_lsa_prefix)))
    return 0;

  return lsa_validate_pxlist(lsa, body->pxcount, sizeof(struct ospf_lsa_prefix), (u8 *) body);
}


/**
 * lsa_validate - check whether given LSA is valid
 * @lsa: LSA header
555 556
 * @lsa_type: internal LSA type (%LSA_T_xxx)
 * @ospf2: %true for OSPFv2, %false for OSPFv3
557 558 559 560 561 562
 * @body: pointer to LSA body
 *
 * Checks internal structure of given LSA body (minimal length,
 * consistency). Returns true if valid.
 */
int
563
lsa_validate(struct ospf_lsa_header *lsa, u32 lsa_type, int ospf2, void *body)
564
{
565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586
  if (ospf2)
  {
    switch (lsa_type)
    {
    case LSA_T_RT:
      return lsa_validate_rt2(lsa, body);
    case LSA_T_NET:
      return lsa_validate_net(lsa, body);
    case LSA_T_SUM_NET:
      return lsa_validate_sum2(lsa, body);
    case LSA_T_SUM_RT:
      return lsa_validate_sum2(lsa, body);
    case LSA_T_EXT:
    case LSA_T_NSSA:
      return lsa_validate_ext2(lsa, body);
    default:
      return 0;	/* Should not happen, unknown LSAs are already rejected */
    }
  }
  else
  {
    switch (lsa_type)
587 588
    {
    case LSA_T_RT:
589
      return lsa_validate_rt3(lsa, body);
590 591 592
    case LSA_T_NET:
      return lsa_validate_net(lsa, body);
    case LSA_T_SUM_NET:
593
      return lsa_validate_sum3_net(lsa, body);
594
    case LSA_T_SUM_RT:
595
      return lsa_validate_sum3_rt(lsa, body);
596
    case LSA_T_EXT:
597
    case LSA_T_NSSA:
598
      return lsa_validate_ext3(lsa, body);
599 600 601 602 603
    case LSA_T_LINK:
      return lsa_validate_link(lsa, body);
    case LSA_T_PREFIX:
      return lsa_validate_prefix(lsa, body);
    default:
604
      return 1;	/* Unknown LSAs are OK in OSPFv3 */
605
    }
606
  }
607
}