topology.c 43.5 KB
Newer Older
1 2 3
/*
 *	BIRD -- OSPF Topological Database
 *
Ondřej Filip's avatar
Ondřej Filip committed
4 5
 *	(c) 1999       Martin Mares <mj@ucw.cz>
 *	(c) 1999--2004 Ondrej Filip <feela@network.cz>
6 7 8 9 10
 *
 *	Can be freely distributed and used under the terms of the GNU GPL.
 */

#include "nest/bird.h"
11
#include "lib/string.h"
12 13 14

#include "ospf.h"

Ondřej Filip's avatar
Ondřej Filip committed
15
#define HASH_DEF_ORDER 6
16 17 18 19 20 21 22
#define HASH_HI_MARK *4
#define HASH_HI_STEP 2
#define HASH_HI_MAX 16
#define HASH_LO_MARK /5
#define HASH_LO_STEP 2
#define HASH_LO_MIN 8

23 24
void originate_prefix_rt_lsa(struct ospf_area *oa);
void originate_prefix_net_lsa(struct ospf_iface *ifa);
25
void flush_prefix_net_lsa(struct ospf_iface *ifa);
26 27 28 29 30 31 32

#ifdef OSPFv2
#define ipa_to_rid(x) _I(x)
#else /* OSPFv3 */
#define ipa_to_rid(x) _I3(x)
#endif

33

34
#ifdef OSPFv2
35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78
static inline u32
fibnode_to_lsaid(struct proto_ospf *po, struct fib_node *fn)
{
  /* We have to map IP prefixes to u32 in such manner that resulting
     u32 interpreted as IP address is a member of given
     prefix. Therefore, /32 prefix have to be mapped on itself.
     All received prefixes have to be mapped on different u32s.

     We have an assumption that if there is nontrivial (non-/32)
     network prefix, then there is not /32 prefix for the first
     and the last IP address of the network (these are usually
     reserved, therefore it is not an important restriction).
     The network prefix is mapped to the first or the last
     IP address in the manner that disallow collisions - we
     use IP address that cannot be used by parent prefix.

     For example:
     192.168.0.0/24 maps to 192.168.0.255
     192.168.1.0/24 maps to 192.168.1.0
     because 192.168.0.0 and 192.168.1.255 might be used by
     192.168.0.0/23 .

     This is not compatible with older RFC 1583, so we have an option
     to the RFC 1583 compatible assignment (that always uses the first
     address) which disallows subnetting.

     Appendig E of RFC 2328 suggests different algorithm, that tries
     to maximize both compatibility and subnetting. But as it is not
     possible to have both reliably and the suggested algorithm was
     unnecessary complicated and it does crazy things like changing
     LSA ID for a network because different network appeared, we
     choose a different way. */

  u32 id = _I(fn->prefix);

  if ((po->rfc1583) || (fn->pxlen == 0) || (fn->pxlen == 32))
    return id;

  if (id & (1 << (32 - fn->pxlen)))
    return id;
  else
    return id | ~u32_mkmask(fn->pxlen);
}

79
#else /* OSPFv3 */
80 81 82 83

static inline u32
fibnode_to_lsaid(struct proto_ospf *po, struct fib_node *fn)
{
84 85 86 87 88 89 90 91
  /*
   * In OSPFv3, it is simpler. There is not a requirement for
   * membership of the result in the input network, so we just use a
   * hash-based unique ID of a routing table entry for a route that
   * originated given LSA. For ext-LSA, it is an imported route in the
   * nest's routing table (p->table). For summary-LSA, it is a
   * 'source' route in the protocol internal routing table (po->rtf).
   */
92 93 94
  return fn->uid;
}

95 96 97
#endif


98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121
static void *
lsab_alloc(struct proto_ospf *po, unsigned size)
{
  unsigned offset = po->lsab_used;
  po->lsab_used += size;
  if (po->lsab_used > po->lsab_size)
    {
      po->lsab_size = MAX(po->lsab_used, 2 * po->lsab_size);
      po->lsab = mb_realloc(po->proto.pool, po->lsab, po->lsab_size);
    }
  return ((byte *) po->lsab) + offset;
}

static inline void *
lsab_allocz(struct proto_ospf *po, unsigned size)
{
  void *r = lsab_alloc(po, size);
  bzero(r, size);
  return r;
}

static inline void *
lsab_flush(struct proto_ospf *po)
{
122
  void *r = mb_alloc(po->proto.pool, po->lsab_used);
123 124 125 126 127
  memcpy(r, po->lsab, po->lsab_used);
  po->lsab_used = 0;
  return r;
}

128 129 130 131 132 133 134 135 136 137 138 139
static inline void *
lsab_offset(struct proto_ospf *po, unsigned offset)
{
  return ((byte *) po->lsab) + offset;
}

static inline void *
lsab_end(struct proto_ospf *po)
{
  return ((byte *) po->lsab) + po->lsab_used;
}

140 141 142 143 144 145 146 147
static s32
get_seqnum(struct top_hash_entry *en)
{
  if (!en)
    return LSA_INITSEQNO;

  if (en->lsa.sn == LSA_MAXSEQNO)
  {
148
    log(L_WARN "OSPF: Premature origination of LSA (Type: %04x, Id: %R, Rt: %R)",
149 150 151 152 153 154 155
	en->lsa.type, en->lsa.id, en->lsa.rt);
    return LSA_INITSEQNO;
  }

  return en->lsa.sn++;
}

156

157 158 159
static int
configured_stubnet(struct ospf_area *oa, struct ifa *a)
{
160 161 162
  if (!oa->ac)
    return 0;

163
  /* Does not work for IA_PEER addresses, but it is not called on these */
164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179
  struct ospf_stubnet_config *sn;
  WALK_LIST(sn, oa->ac->stubnet_list)
    {
      if (sn->summary)
	{
	  if (ipa_in_net(a->prefix, sn->px.addr, sn->px.len) && (a->pxlen >= sn->px.len))
	    return 1;
	}
      else
	{
	  if (ipa_equal(a->prefix, sn->px.addr) && (a->pxlen == sn->px.len))
	    return 1;
	}
    }
  return 0;
}
180

181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206
int
bcast_net_active(struct ospf_iface *ifa)
{
  struct ospf_neighbor *neigh;

  if (ifa->state == OSPF_IS_WAITING)
    return 0;

  WALK_LIST(neigh, ifa->neigh_list)
    {
      if (neigh->state == NEIGHBOR_FULL)
	{
	  if (neigh->rid == ifa->drid)
	    return 1;

	  if (ifa->state == OSPF_IS_DR)
	    return 1;
	}
    }

  return 0;
}


#ifdef OSPFv2

207
static void *
208
originate_rt_lsa_body(struct ospf_area *oa, u16 *length)
209
{
Ondřej Filip's avatar
Ondřej Filip committed
210
  struct proto_ospf *po = oa->po;
211
  struct ospf_iface *ifa;
212
  int i = 0, bitv = 0;
213
  struct ospf_lsa_rt *rt;
214
  struct ospf_lsa_rt_link *ln;
215 216
  struct ospf_neighbor *neigh;

217 218
  ASSERT(po->lsab_used == 0);
  rt = lsab_allocz(po, sizeof(struct ospf_lsa_rt));
219

220
  rt->options = 0;
221

Ondřej Filip's avatar
Ondřej Filip committed
222
  if (po->areano > 1)
223 224
    rt->options |= OPT_RT_B;

225
  if (po->ebit && !oa_is_stub(oa))
226 227
    rt->options |= OPT_RT_E;

228
  rt = NULL; /* buffer might be reallocated later */
Ondřej Filip's avatar
Ondřej Filip committed
229 230

  WALK_LIST(ifa, po->iface_list)
231
  {
232
    int net_lsa = 0;
233 234 235

    if ((ifa->type == OSPF_IT_VLINK) && (ifa->voa == oa) &&
	(!EMPTY_LIST(ifa->neigh_list)))
236 237 238
    {
      neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
      if ((neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
239
	bitv = 1;
240
    }
241 242

    if ((ifa->oa != oa) || (ifa->state == OSPF_IS_DOWN))
Ondřej Filip's avatar
Ondřej Filip committed
243
      continue;
Ondřej Filip's avatar
Ondřej Filip committed
244

245 246
    ifa->rt_pos_beg = i;

247
    /* RFC2328 - 12.4.1.1-4 */
248
    switch (ifa->type)
249
      {
250 251 252 253 254 255 256 257
      case OSPF_IT_PTP:
      case OSPF_IT_PTMP:
	WALK_LIST(neigh, ifa->neigh_list)
	  if (neigh->state == NEIGHBOR_FULL)
	  {
	    ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link));
	    ln->type = LSART_PTP;
	    ln->id = neigh->rid;
258
	    ln->data = (ifa->addr->flags & IA_PEER) ?
259 260 261 262 263
	      ifa->iface->index : ipa_to_u32(ifa->addr->ip);
	    ln->metric = ifa->cost;
	    ln->padding = 0;
	    i++;
	  }
Ondřej Filip's avatar
Ondřej Filip committed
264
	break;
265

266
      case OSPF_IT_BCAST:
Ondřej Filip's avatar
Ondřej Filip committed
267
      case OSPF_IT_NBMA:
268
	if (bcast_net_active(ifa))
Ondřej Filip's avatar
Ondřej Filip committed
269
	  {
270
	    ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link));
Ondřej Filip's avatar
Ondřej Filip committed
271 272
	    ln->type = LSART_NET;
	    ln->id = ipa_to_u32(ifa->drip);
273
	    ln->data = ipa_to_u32(ifa->addr->ip);
Ondřej Filip's avatar
Ondřej Filip committed
274
	    ln->metric = ifa->cost;
275
	    ln->padding = 0;
276
	    i++;
277
	    net_lsa = 1;
Ondřej Filip's avatar
Ondřej Filip committed
278 279
	  }
	break;
280

281
      case OSPF_IT_VLINK:
Ondřej Filip's avatar
Ondřej Filip committed
282 283 284
	neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
	if ((!EMPTY_LIST(ifa->neigh_list)) && (neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
	{
285
	  ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link));
Ondřej Filip's avatar
Ondřej Filip committed
286 287
	  ln->type = LSART_VLNK;
	  ln->id = neigh->rid;
288
	  ln->data = ipa_to_u32(ifa->addr->ip);
Ondřej Filip's avatar
Ondřej Filip committed
289
	  ln->metric = ifa->cost;
290
	  ln->padding = 0;
291
	  i++;
292 293
        }
        break;
294

295
      default:
296
        log("Unknown interface type %s", ifa->iface->name);
Ondřej Filip's avatar
Ondřej Filip committed
297
        break;
298
      }
299

300 301
    ifa->rt_pos_end = i;

302 303 304
    /* Now we will originate stub area if there is no primary */
    if (net_lsa ||
	(ifa->type == OSPF_IT_VLINK) ||
305
	(ifa->addr->flags & IA_PEER) ||
306 307
	configured_stubnet(oa, ifa->addr))
      continue;
308

309
    ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link));
310 311 312
    if ((ifa->addr->flags & IA_HOST) ||
	(ifa->state == OSPF_IS_LOOP) ||
	(ifa->type == OSPF_IT_PTMP))
313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329
    {
      /* Host stub entry */
      ln->type = LSART_STUB;
      ln->id = ipa_to_u32(ifa->addr->ip);
      ln->data = 0xffffffff;
      ln->metric = 0;
      ln->padding = 0;
    }
    else 
    {
      /* Network stub entry */
      ln->type = LSART_STUB;
      ln->id = ipa_to_u32(ifa->addr->prefix);
      ln->data = ipa_to_u32(ipa_mkmask(ifa->addr->pxlen));
      ln->metric = ifa->cost;
      ln->padding = 0;
    }
330
    i++;
331 332

    ifa->rt_pos_end = i;
333
  }
334

335
  struct ospf_stubnet_config *sn;
336 337 338
  if (oa->ac)
    WALK_LIST(sn, oa->ac->stubnet_list)
      if (!sn->hidden)
339 340 341 342 343 344
      {
	ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link));
	ln->type = LSART_STUB;
	ln->id = ipa_to_u32(sn->px.addr);
	ln->data = ipa_to_u32(ipa_mkmask(sn->px.len));
	ln->metric = sn->cost;
345
	ln->padding = 0;
346 347 348
	i++;
      }

349
  rt = po->lsab;
Ondřej Filip's avatar
Ondřej Filip committed
350
  rt->links = i;
351 352 353 354

  if (bitv) 
    rt->options |= OPT_RT_V;

355 356
  *length = po->lsab_used + sizeof(struct ospf_lsa_header);
  return lsab_flush(po);
357
}
Ondřej Filip's avatar
Ondřej Filip committed
358

359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377
#else /* OSPFv3 */

static void
add_lsa_rt_link(struct proto_ospf *po, struct ospf_iface *ifa, u8 type, u32 nif, u32 id)
{
  struct ospf_lsa_rt_link *ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link));
  ln->type = type;
  ln->padding = 0;
  ln->metric = ifa->cost;
  ln->lif = ifa->iface->index;
  ln->nif = nif;
  ln->id = id;
}

static void *
originate_rt_lsa_body(struct ospf_area *oa, u16 *length)
{
  struct proto_ospf *po = oa->po;
  struct ospf_iface *ifa;
378
  int bitv = 0;
379
  int i = 0;
380 381 382 383 384 385 386 387 388 389 390
  struct ospf_lsa_rt *rt;
  struct ospf_neighbor *neigh;

  ASSERT(po->lsab_used == 0);
  rt = lsab_allocz(po, sizeof(struct ospf_lsa_rt));

  rt->options = oa->options & OPTIONS_MASK;

  if (po->areano > 1)
    rt->options |= OPT_RT_B;

391
  if (po->ebit && !oa_is_stub(oa))
392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408
    rt->options |= OPT_RT_E;

  rt = NULL; /* buffer might be reallocated later */

  WALK_LIST(ifa, po->iface_list)
  {
    if ((ifa->type == OSPF_IT_VLINK) && (ifa->voa == oa) &&
	(!EMPTY_LIST(ifa->neigh_list)))
    {
      neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
      if ((neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
	bitv = 1;
    }

    if ((ifa->oa != oa) || (ifa->state == OSPF_IS_DOWN))
      continue;

409 410
    ifa->rt_pos_beg = i;

411 412 413 414
    /* RFC5340 - 4.4.3.2 */
    switch (ifa->type)
      {
      case OSPF_IT_PTP:
415 416 417
      case OSPF_IT_PTMP:
	WALK_LIST(neigh, ifa->neigh_list)
	  if (neigh->state == NEIGHBOR_FULL)
418
	    add_lsa_rt_link(po, ifa, LSART_PTP, neigh->iface_id, neigh->rid), i++;
419 420 421 422 423
	break;

      case OSPF_IT_BCAST:
      case OSPF_IT_NBMA:
	if (bcast_net_active(ifa))
424
	  add_lsa_rt_link(po, ifa, LSART_NET, ifa->dr_iface_id, ifa->drid), i++;
425 426 427 428 429
	break;

      case OSPF_IT_VLINK:
	neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
	if ((!EMPTY_LIST(ifa->neigh_list)) && (neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
430
	  add_lsa_rt_link(po, ifa, LSART_VLNK, neigh->iface_id, neigh->rid), i++;
431 432 433 434 435 436
        break;

      default:
        log("Unknown interface type %s", ifa->iface->name);
        break;
      }
437 438

    ifa->rt_pos_end = i;
439 440 441 442 443 444 445 446 447 448 449 450 451 452
  }

  if (bitv)
    {
      rt = po->lsab;
      rt->options |= OPT_RT_V;
    }

  *length = po->lsab_used + sizeof(struct ospf_lsa_header);
  return lsab_flush(po);
}

#endif

453 454 455 456 457 458 459 460 461
/**
 * originate_rt_lsa - build new instance of router LSA
 * @oa: ospf_area which is LSA built to
 *
 * It builds router LSA walking through all OSPF interfaces in
 * specified OSPF area. This function is mostly called from
 * area_disp(). Builds new LSA, increases sequence number (if old
 * instance exists) and sets age of LSA to zero.
 */
Ondřej Filip's avatar
Ondřej Filip committed
462
void
463
originate_rt_lsa(struct ospf_area *oa)
464 465
{
  struct ospf_lsa_header lsa;
Ondřej Filip's avatar
Ondřej Filip committed
466 467
  struct proto_ospf *po = oa->po;
  struct proto *p = &po->proto;
468 469
  void *body;

470
  OSPF_TRACE(D_EVENTS, "Originating router-LSA for area %R", oa->areaid);
Ondřej Filip's avatar
Ondřej Filip committed
471 472 473

  lsa.age = 0;
  lsa.type = LSA_T_RT;
474 475 476
  
#ifdef OSPFv2
  lsa.options = oa->options;
477
  lsa.id = po->router_id;
478 479 480 481
#else /* OSPFv3 */
  lsa.id = 0;
#endif

482
  lsa.rt = po->router_id;
483
  lsa.sn = get_seqnum(oa->rt);
484 485
  u32 dom = oa->areaid;

Ondřej Filip's avatar
Ondřej Filip committed
486
  body = originate_rt_lsa_body(oa, &lsa.length);
Ondřej Filip's avatar
Ondřej Filip committed
487
  lsasum_calculate(&lsa, body);
488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505
  oa->rt = lsa_install_new(po, &lsa, dom, body);
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
}

void
update_rt_lsa(struct ospf_area *oa)
{
  struct proto_ospf *po = oa->po;

  if ((oa->rt) && ((oa->rt->inst_t + MINLSINTERVAL)) > now)
    return;
  /*
   * Tick is probably set to very low value. We cannot
   * originate new LSA before MINLSINTERVAL. We will
   * try to do it next tick.
   */

  originate_rt_lsa(oa);
506
#ifdef OSPFv3
507
  originate_prefix_rt_lsa(oa);
508
#endif
509

510
  schedule_rtcalc(po);
Ondřej Filip's avatar
Ondřej Filip committed
511
  oa->origrt = 0;
512 513
}

514
static void *
515
originate_net_lsa_body(struct ospf_iface *ifa, u16 *length,
Ondřej Filip's avatar
Ondřej Filip committed
516
		       struct proto_ospf *po)
Ondřej Filip's avatar
Ondřej Filip committed
517
{
Ondřej Filip's avatar
Ondřej Filip committed
518
  u16 i = 1;
Ondřej Filip's avatar
Ondřej Filip committed
519
  struct ospf_neighbor *n;
520
  struct ospf_lsa_net *net;
521 522 523 524
  int nodes = ifa->fadj + 1;

  net = mb_alloc(po->proto.pool, sizeof(struct ospf_lsa_net)
		 + nodes * sizeof(u32));
Ondřej Filip's avatar
Ondřej Filip committed
525

526
#ifdef OSPFv2
527
  net->netmask = ipa_mkmask(ifa->addr->pxlen);
528 529 530 531 532 533 534 535
#endif

#ifdef OSPFv3
  /* In OSPFv3, we would like to merge options from Link LSAs of added neighbors */
  struct top_hash_entry *en;
  u32 options = 0;
#endif

536
  net->routers[0] = po->router_id;
537

Ondřej Filip's avatar
Ondřej Filip committed
538
  WALK_LIST(n, ifa->neigh_list)
Ondřej Filip's avatar
Ondřej Filip committed
539
  {
Ondřej Filip's avatar
Ondřej Filip committed
540
    if (n->state == NEIGHBOR_FULL)
Ondřej Filip's avatar
Ondřej Filip committed
541
    {
542
#ifdef OSPFv3
543
      en = ospf_hash_find(po->gr, ifa->iface->index, n->iface_id, n->rid, LSA_T_LINK);
544 545 546 547 548
      if (en)
	options |= ((struct ospf_lsa_link *) en->lsa_body)->options;
#endif

      net->routers[i] = n->rid;
Ondřej Filip's avatar
Ondřej Filip committed
549 550 551
      i++;
    }
  }
552 553 554 555 556 557 558 559
  ASSERT(i == nodes);

#ifdef OSPFv3
  net->options = options & OPTIONS_MASK;
#endif
  
  *length = sizeof(struct ospf_lsa_header) + sizeof(struct ospf_lsa_net)
    + nodes * sizeof(u32);
560
  return net;
Ondřej Filip's avatar
Ondřej Filip committed
561 562
}

563

564 565 566 567
/**
 * originate_net_lsa - originates of deletes network LSA
 * @ifa: interface which is LSA originated for
 *
Ondřej Filip's avatar
Ondřej Filip committed
568 569
 * Interface counts number of adjacent neighbors. If this number is
 * lower than one or interface is not in state %OSPF_IS_DR it deletes
570 571 572
 * and premature ages instance of network LSA for specified interface.
 * In other case, new instance of network LSA is originated.
 */
Ondřej Filip's avatar
Ondřej Filip committed
573
void
574
originate_net_lsa(struct ospf_iface *ifa)
Ondřej Filip's avatar
Ondřej Filip committed
575
{
576
  struct proto_ospf *po = ifa->oa->po;
577
  struct proto *p = &po->proto;
Ondřej Filip's avatar
Ondřej Filip committed
578
  struct ospf_lsa_header lsa;
579
  u32 dom = ifa->oa->areaid;
580
  
Ondřej Filip's avatar
Ondřej Filip committed
581 582
  void *body;

583
  OSPF_TRACE(D_EVENTS, "Originating network-LSA for iface %s",
Ondřej Filip's avatar
Ondřej Filip committed
584 585 586 587
	     ifa->iface->name);

  lsa.age = 0;
  lsa.type = LSA_T_NET;
588 589 590

#ifdef OSPFv2
  lsa.options = ifa->oa->options;
591
  lsa.id = ipa_to_u32(ifa->addr->ip);
592 593 594 595
#else /* OSPFv3 */
  lsa.id = ifa->iface->index;
#endif

596
  lsa.rt = po->router_id;
597
  lsa.sn = get_seqnum(ifa->net_lsa);
598

Ondřej Filip's avatar
Ondřej Filip committed
599
  body = originate_net_lsa_body(ifa, &lsa.length, po);
Ondřej Filip's avatar
Ondřej Filip committed
600
  lsasum_calculate(&lsa, body);
601 602
  ifa->net_lsa = lsa_install_new(po, &lsa, dom, body);
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
Ondřej Filip's avatar
Ondřej Filip committed
603 604
}

605 606 607 608 609 610 611 612 613 614
void
flush_net_lsa(struct ospf_iface *ifa)
{
  struct proto_ospf *po = ifa->oa->po;
  struct proto *p = &po->proto;
  u32 dom = ifa->oa->areaid;

  if (ifa->net_lsa == NULL)
    return;

615
  OSPF_TRACE(D_EVENTS, "Flushing network-LSA for iface %s",
616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639
	     ifa->iface->name);
  ifa->net_lsa->lsa.sn += 1;
  ifa->net_lsa->lsa.age = LSA_MAXAGE;
  lsasum_calculate(&ifa->net_lsa->lsa, ifa->net_lsa->lsa_body);
  ospf_lsupd_flood(po, NULL, NULL, &ifa->net_lsa->lsa, dom, 0);
  flush_lsa(ifa->net_lsa, po);
  ifa->net_lsa = NULL;
}

void
update_net_lsa(struct ospf_iface *ifa)
{
  struct proto_ospf *po = ifa->oa->po;
 
  if (ifa->net_lsa && ((ifa->net_lsa->inst_t + MINLSINTERVAL) > now))
    return;
  /*
   * It's too early to originate new network LSA. We will
   * try to do it next tick
   */

  if ((ifa->state != OSPF_IS_DR) || (ifa->fadj == 0))
    {
      flush_net_lsa(ifa);
640
#ifdef OSPFv3
641
      flush_prefix_net_lsa(ifa);
642
#endif
643 644 645 646
    }
  else
    {
      originate_net_lsa(ifa);
647
#ifdef OSPFv3
648
      originate_prefix_net_lsa(ifa);
649
#endif
650 651 652 653 654
    }

  schedule_rtcalc(po);
  ifa->orignet = 0;
}
Ondřej Filip's avatar
Ondřej Filip committed
655

656 657
#ifdef OSPFv2

658
static inline void *
659
originate_sum_lsa_body(struct proto_ospf *po, u16 *length, u32 mlen, u32 metric)
Ondřej Filip's avatar
Ondřej Filip committed
660
{
661 662
  struct ospf_lsa_sum *sum = mb_alloc(po->proto.pool, sizeof(struct ospf_lsa_sum));
  *length = sizeof(struct ospf_lsa_header) + sizeof(struct ospf_lsa_sum);
Ondřej Filip's avatar
Ondřej Filip committed
663

664 665
  sum->netmask = ipa_mkmask(mlen);
  sum->metric = metric;
Ondřej Filip's avatar
Ondřej Filip committed
666

667 668
  return sum;
}
Martin Mareš's avatar
Martin Mareš committed
669

670 671
#define originate_sum_net_lsa_body(po,length,fn,metric) \
  originate_sum_lsa_body(po, length, (fn)->pxlen, metric)
Ondřej Filip's avatar
Ondřej Filip committed
672

673 674
#define originate_sum_rt_lsa_body(po,length,drid,metric,options) \
  originate_sum_lsa_body(po, length, 0, metric)
Ondřej Filip's avatar
Ondřej Filip committed
675

676 677 678 679
static inline int
check_sum_net_lsaid_collision(struct fib_node *fn, struct top_hash_entry *en)
{
  struct ospf_lsa_sum *sum = en->lsa_body;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
680
  return fn->pxlen != ipa_mklen(sum->netmask);
681 682 683
}

static inline int
684
check_sum_lsa_same(struct top_hash_entry *en, u32 metric)
685
{
686 687
  /* Netmask already checked in check_sum_net_lsaid_collision() */
  struct ospf_lsa_sum *sum = en->lsa_body;
688
  return (en->lsa.sn != LSA_MAXSEQNO) && (sum->metric == metric);
689 690
}

691 692 693 694 695 696 697
#define check_sum_net_lsa_same(en,metric) \
  check_sum_lsa_same(en, metric)

#define check_sum_rt_lsa_same(en,drid,metric,options) \
  check_sum_lsa_same(en, metric)


698
#else /* OSPFv3 */
699

700
static inline void *
701
originate_sum_net_lsa_body(struct proto_ospf *po, u16 *length, struct fib_node *fn, u32 metric)
702
{
703 704 705 706 707 708 709 710 711 712
  int size = sizeof(struct ospf_lsa_sum_net) + IPV6_PREFIX_SPACE(fn->pxlen);
  struct ospf_lsa_sum_net *sum = mb_alloc(po->proto.pool, size);
  *length = sizeof(struct ospf_lsa_header) + size;

  sum->metric = metric;
  put_ipv6_prefix(sum->prefix, fn->prefix, fn->pxlen, 0, 0);

  return sum;
}

713 714 715 716 717 718 719 720 721 722 723 724 725 726
static inline int
check_sum_net_lsaid_collision(struct fib_node *fn, struct top_hash_entry *en)
{
  struct ospf_lsa_sum_net *sum = en->lsa_body;
  ip_addr prefix;
  int pxlen;
  u8 pxopts;
  u16 rest;

  lsa_get_ipv6_prefix(sum->prefix, &prefix, &pxlen, &pxopts, &rest);
  return (fn->pxlen != pxlen) || !ipa_equal(fn->prefix, prefix);
}

static inline int
727
check_sum_net_lsa_same(struct top_hash_entry *en, u32 metric)
728
{
729 730
  /* Prefix already checked in check_sum_net_lsaid_collision() */
  struct ospf_lsa_sum_net *sum = en->lsa_body;
731
  return (en->lsa.sn != LSA_MAXSEQNO) && (sum->metric == metric);
732 733 734
}

static inline void *
735 736 737 738 739
originate_sum_rt_lsa_body(struct proto_ospf *po, u16 *length, u32 drid, u32 metric, u32 options)
{
  struct ospf_lsa_sum_rt *sum = mb_alloc(po->proto.pool, sizeof(struct ospf_lsa_sum_rt));
  *length = sizeof(struct ospf_lsa_header) + sizeof(struct ospf_lsa_sum_rt);

740
  sum->options = options;
741 742 743 744
  sum->metric = metric;
  sum->drid = drid;

  return sum;
745 746
}

747 748 749 750
static inline int
check_sum_rt_lsa_same(struct top_hash_entry *en, u32 drid, u32 metric, u32 options)
{
  struct ospf_lsa_sum_rt *sum = en->lsa_body;
751 752
  return (en->lsa.sn != LSA_MAXSEQNO) && (sum->options == options) &&
    (sum->metric == metric) && (sum->drid == drid);
753 754
}

755 756
#endif

Ondřej Filip's avatar
Ondřej Filip committed
757
void
758
originate_sum_net_lsa(struct ospf_area *oa, struct fib_node *fn, int metric)
Ondřej Filip's avatar
Ondřej Filip committed
759 760 761 762
{
  struct proto_ospf *po = oa->po;
  struct proto *p = &po->proto;
  struct top_hash_entry *en;
763
  u32 dom = oa->areaid;
Ondřej Filip's avatar
Ondřej Filip committed
764
  struct ospf_lsa_header lsa;
765
  void *body;
Ondřej Filip's avatar
Ondřej Filip committed
766

767 768
  OSPF_TRACE(D_EVENTS, "Originating net-summary-LSA for %I/%d (metric %d)",
	     fn->prefix, fn->pxlen, metric);
769

770
  /* options argument is used in ORT_NET and OSPFv3 only */
771 772 773 774
  lsa.age = 0;
#ifdef OSPFv2
  lsa.options = oa->options;
#endif
775 776
  lsa.type = LSA_T_SUM_NET;
  lsa.id = fibnode_to_lsaid(po, fn);
777
  lsa.rt = po->router_id;
Ondřej Filip's avatar
Ondřej Filip committed
778

779 780 781
  if ((en = ospf_hash_find_header(po->gr, dom, &lsa)) != NULL)
  {
    if (check_sum_net_lsaid_collision(fn, en))
782 783 784 785 786 787 788 789
    {
      log(L_ERR, "%s: LSAID collision for %I/%d",
	  p->name, fn->prefix, fn->pxlen);
      return;
    }

    if (check_sum_net_lsa_same(en, metric))
      return;
790
  }
791
  lsa.sn = get_seqnum(en);
792

793 794 795 796 797
  body = originate_sum_net_lsa_body(po, &lsa.length, fn, metric);
  lsasum_calculate(&lsa, body);
  en = lsa_install_new(po, &lsa, dom, body);
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
}
798

799
void
800
originate_sum_rt_lsa(struct ospf_area *oa, struct fib_node *fn, int metric, u32 options UNUSED)
801 802 803 804
{
  struct proto_ospf *po = oa->po;
  struct proto *p = &po->proto;
  struct top_hash_entry *en;
805 806
  u32 dom = oa->areaid;
  u32 rid = ipa_to_rid(fn->prefix);
807 808
  struct ospf_lsa_header lsa;
  void *body;
809

810
  OSPF_TRACE(D_EVENTS, "Originating rt-summary-LSA for %R (metric %d)",
811
	     rid, metric);
812 813 814 815 816 817 818

  lsa.age = 0;
#ifdef OSPFv2
  lsa.options = oa->options;
#endif
  lsa.type = LSA_T_SUM_RT;
  /* In OSPFv3, LSA ID is meaningless, but we still use Router ID of ASBR */
819
  lsa.id = rid;
820
  lsa.rt = po->router_id;
821

822
  options &= OPTIONS_MASK;
823
  if ((en = ospf_hash_find_header(po->gr, dom, &lsa)) != NULL)
824 825 826 827
  {
    if (check_sum_rt_lsa_same(en, lsa.id, metric, options))
      return;
  }
828
  lsa.sn = get_seqnum(en);
829

830
  body = originate_sum_rt_lsa_body(po, &lsa.length, lsa.id, metric, options);
831 832 833
  lsasum_calculate(&lsa, body);
  en = lsa_install_new(po, &lsa, dom, body);
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
Ondřej Filip's avatar
Ondřej Filip committed
834 835 836
}

void
837
flush_sum_lsa(struct ospf_area *oa, struct fib_node *fn, int type)
Ondřej Filip's avatar
Ondřej Filip committed
838 839 840 841 842 843
{
  struct proto_ospf *po = oa->po;
  struct proto *p = &po->proto;
  struct top_hash_entry *en;
  struct ospf_lsa_header lsa;

844
  lsa.rt = po->router_id;
845
  if (type == ORT_NET)
Ondřej Filip's avatar
Ondřej Filip committed
846
    {
847
      lsa.id = fibnode_to_lsaid(po, fn);
848
      lsa.type = LSA_T_SUM_NET;
Ondřej Filip's avatar
Ondřej Filip committed
849
    }
850
  else
Ondřej Filip's avatar
Ondřej Filip committed
851
    {
852
      /* In OSPFv3, LSA ID is meaningless, but we still use Router ID of ASBR */
853 854
      lsa.id = ipa_to_rid(fn->prefix);
      lsa.type = LSA_T_SUM_RT;
Ondřej Filip's avatar
Ondřej Filip committed
855 856
    }

857
  if ((en = ospf_hash_find_header(po->gr, oa->areaid, &lsa)) != NULL)
858
    {
859 860 861 862 863 864 865
      if ((type == ORT_NET) && check_sum_net_lsaid_collision(fn, en))
	{
	  log(L_ERR, "%s: LSAID collision for %I/%d",
	      p->name, fn->prefix, fn->pxlen);
	  return;
	}

866 867 868 869 870
      struct ospf_lsa_sum *sum = en->lsa_body;
      en->lsa.age = LSA_MAXAGE;
      en->lsa.sn = LSA_MAXSEQNO;
      lsasum_calculate(&en->lsa, sum);

871
      OSPF_TRACE(D_EVENTS, "Flushing summary-LSA (id=%R, type=%d)",
872 873 874 875
		 en->lsa.id, en->lsa.type);
      ospf_lsupd_flood(po, NULL, NULL, &en->lsa, oa->areaid, 1);
      if (can_flush_lsa(po)) flush_lsa(en, po);
    }
Ondřej Filip's avatar
Ondřej Filip committed
876 877
}

878
#ifdef OSPFv2
879

880 881 882
static inline void *
originate_ext_lsa_body(struct proto_ospf *po, u16 *length, net *n,
		       u32 metric, ip_addr fwaddr, u32 tag)
883
{
884 885
  struct ospf_lsa_ext *ext = mb_alloc(po->proto.pool, sizeof(struct ospf_lsa_ext));
  *length = sizeof(struct ospf_lsa_header) + sizeof(struct ospf_lsa_ext);
886

887 888 889 890
  ext->metric = metric; 
  ext->netmask = ipa_mkmask(n->n.pxlen);
  ext->fwaddr = fwaddr;
  ext->tag = tag;
891

892 893
  return ext;
}
894

895 896 897 898 899 900 901 902 903 904 905 906 907
/*
 * check_ext_lsa() combines functions of check_*_lsaid_collision() and
 * check_*_lsa_same(). 'en' is existing ext LSA, and rest parameters
 * are parameters of new ext route.  Function returns -1 if there is
 * LSAID collision, returns 1 if the existing LSA is the same and
 * returns 0 otherwise (in that case, we need to originate a new LSA).
 *
 * Really, checking for the same parameters is not as important as in
 * summary LSA origination, because in most cases the duplicate
 * external route propagation would be stopped by the nest. But there
 * are still some cases (route reload, the same route propagated through
 * different protocol) so it is also done here.
 */
908

909 910 911 912 913 914 915 916 917
static inline int
check_ext_lsa(struct top_hash_entry *en, struct fib_node *fn, u32 metric, ip_addr fwaddr, u32 tag)
{
  struct ospf_lsa_ext *ext = en->lsa_body;

  /* LSAID collision */
  if  (fn->pxlen != ipa_mklen(ext->netmask))
    return -1;

918 919
  return (en->lsa.sn != LSA_MAXSEQNO) && (ext->metric == metric) &&
    (ext->tag == tag) && ipa_equal(ext->fwaddr,fwaddr);
920
}
921 922

#else /* OSPFv3 */
923 924 925 926 927 928 929 930 931 932 933 934 935 936 937

static inline void *
originate_ext_lsa_body(struct proto_ospf *po, u16 *length, net *n,
		       u32 metric, ip_addr fwaddr, u32 tag)
{
  int size = sizeof(struct ospf_lsa_ext)
    + IPV6_PREFIX_SPACE(n->n.pxlen)
    + (ipa_nonzero(fwaddr) ? 16 : 0)
    + (tag ? 4 : 0);

  struct ospf_lsa_ext *ext = mb_alloc(po->proto.pool, size);
  *length = sizeof(struct ospf_lsa_header) + size;

  ext->metric = metric;

938
  u32 *buf = ext->rest;
939 940
  buf = put_ipv6_prefix(buf, n->n.prefix, n->n.pxlen, 0, 0);

941 942 943 944 945
  if (ipa_nonzero(fwaddr))
  {
    ext->metric |= LSA_EXT_FBIT;
    buf = put_ipv6_addr(buf, fwaddr);
  }
946 947

  if (tag)
948 949 950 951
  {
    ext->metric |= LSA_EXT_TBIT;
    *buf++ = tag;
  }
952 953 954 955

  return ext;
}

956 957 958 959 960 961 962 963 964 965 966 967 968 969 970
static inline int
check_ext_lsa(struct top_hash_entry *en, struct fib_node *fn, u32 metric, ip_addr fwaddr, u32 tag)
{
  struct ospf_lsa_ext *ext = en->lsa_body;
  ip_addr prefix;
  int pxlen;
  u8 pxopts;
  u16 rest;

  u32 *buf = lsa_get_ipv6_prefix(ext->rest, &prefix, &pxlen, &pxopts, &rest);

  /* LSAID collision */
  if ((fn->pxlen != pxlen) || !ipa_equal(fn->prefix, prefix))
    return -1;

971 972 973
  if (en->lsa.sn == LSA_MAXSEQNO)
    return 0;

974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989
  u32 rt_metric = ext->metric & METRIC_MASK;
  ip_addr rt_fwaddr = IPA_NONE;
  u32 rt_tag = 0;

  if (ext->metric & LSA_EXT_FBIT)
    buf = lsa_get_ipv6_addr(buf, &rt_fwaddr);

  if (ext->metric & LSA_EXT_TBIT)
    rt_tag = *buf++;

  return (rt_metric == metric) && ipa_equal(rt_fwaddr, fwaddr) && (rt_tag == tag);
}


#endif

990
/**
Ondřej Filip's avatar
Ondřej Filip committed
991
 * originate_ext_lsa - new route received from nest and filters
992
 * @oa: ospf_area for which LSA is originated
993 994 995 996
 * @n: network prefix and mask
 * @e: rte
 * @attrs: list of extended attributes
 *
Ondřej Filip's avatar
Ondřej Filip committed
997
 * If I receive a message that new route is installed, I try to originate an
998 999
 * external LSA. If @oa is an NSSA area, NSSA-LSA is originated instead.
 * @oa should not be stub area.
1000
 *
Ondřej Filip's avatar
Ondřej Filip committed
1001
 * The function also sets flag ebit. If it's the first time, the new router lsa
1002
 * origination is necessary.
1003
 */
Ondřej Filip's avatar
Ondřej Filip committed
1004
void
1005
originate_ext_lsa(struct ospf_area *oa, net *n, rte *e, struct ea_list *attrs)
Ondřej Filip's avatar
Ondřej Filip committed
1006
{
1007
  struct proto_ospf *po = oa->po;
1008
  struct proto *p = &po->proto;
1009
  struct fib_node *fn = &n->n;
Ondřej Filip's avatar
Ondřej Filip committed
1010
  struct ospf_lsa_header lsa;
Ondřej Filip's avatar
Ondřej Filip committed
1011
  struct top_hash_entry *en = NULL;
1012
  void *body;
1013 1014 1015 1016
  int nssa = oa_is_nssa(oa);
  u32 dom = nssa ? oa->areaid : 0;

  // FIXME NSSA - handle P bit
Ondřej Filip's avatar
Ondřej Filip committed
1017

1018 1019
  OSPF_TRACE(D_EVENTS, "Originating %s-LSA for %I/%d",
	     nssa ? "NSSA" : "AS-external", fn->prefix, fn->pxlen);
Ondřej Filip's avatar
Ondřej Filip committed
1020 1021

  lsa.age = 0;
1022
#ifdef OSPFv2
1023
  lsa.options = oa->options;
1024
#endif
1025
  lsa.type = nssa ? LSA_T_NSSA : LSA_T_EXT;
1026
  lsa.id = fibnode_to_lsaid(po, fn);
1027
  lsa.rt = po->router_id;
1028

1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041
  /* Compute LSA content */
  u32 m1 = ea_get_int(attrs, EA_OSPF_METRIC1, LSINFINITY);
  u32 m2 = ea_get_int(attrs, EA_OSPF_METRIC2, 10000);
  u32 metric = (m1 != LSINFINITY) ? m1 : (m2 | LSA_EXT_EBIT);
  u32 tag = ea_get_int(attrs, EA_OSPF_TAG, 0);
  ip_addr gw = IPA_NONE;
  // FIXME check for gw should be per ifa, not per iface
  if ((e->attrs->dest == RTD_ROUTER) &&
      ipa_nonzero(e->attrs->gw) &&
      !ipa_has_link_scope(e->attrs->gw) &&
      (ospf_iface_find((struct proto_ospf *) p, e->attrs->iface) != NULL))
    gw = e->attrs->gw;

1042 1043 1044 1045 1046 1047
  if (nssa)
  {
    // FIXME NSSA Add check for gw, update option
  }

  if ((en = ospf_hash_find_header(po->gr, dom, &lsa)) != NULL)
1048 1049 1050
  {
    int rv = check_ext_lsa(