topology.c 51.3 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
 *	(c) 2009--2014 Ondrej Zajicek <santiago@crfreenet.org>
 *	(c) 2009--2014 CZ.NIC z.s.p.o.
8 9 10 11 12
 *
 *	Can be freely distributed and used under the terms of the GNU GPL.
 */

#include "nest/bird.h"
13
#include "lib/string.h"
14 15 16

#include "ospf.h"

17

18
#define HASH_DEF_ORDER 6
19 20 21 22 23 24 25
#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

26 27
static inline void * lsab_flush(struct ospf_proto *p);
static inline void lsab_reset(struct ospf_proto *p);
28 29


30 31 32 33
/**
 * ospf_install_lsa - install new LSA into database
 * @p: OSPF protocol instance
 * @lsa: LSA header
34
 * @type: type of LSA
35 36 37 38 39 40 41 42
 * @domain: domain of LSA
 * @body: pointer to LSA body
 *
 * This function ensures installing new LSA received in LS update into LSA
 * database. Old instance is replaced. Several actions are taken to detect if
 * new routing table calculation is necessary. This is described in 13.2 of RFC
 * 2328. This function is for received LSA only, locally originated LSAs are
 * installed by ospf_originate_lsa().
43 44 45
 *
 * The LSA body in @body is expected to be mb_allocated by the caller and its
 * ownership is transferred to the LSA entry structure.
46 47 48 49 50 51
 */
struct top_hash_entry *
ospf_install_lsa(struct ospf_proto *p, struct ospf_lsa_header *lsa, u32 type, u32 domain, void *body)
{
  struct top_hash_entry *en;
  int change = 0;
52

53
  en = ospf_hash_get(p->gr, domain, lsa->id, lsa->rt, type);
54

55 56 57 58 59 60 61 62 63 64 65
  if (!SNODE_VALID(en))
    s_add_tail(&p->lsal, SNODE en);

  if ((en->lsa_body == NULL) ||			/* No old LSA */
      (en->lsa.length != lsa->length) ||
      (en->lsa.type_raw != lsa->type_raw) ||	/* Check for OSPFv2 options */
      (en->lsa.age == LSA_MAXAGE) ||
      (lsa->age == LSA_MAXAGE) ||
      memcmp(en->lsa_body, body, lsa->length - sizeof(struct ospf_lsa_header)))
    change = 1;

66 67
  if ((en->lsa.age == LSA_MAXAGE) && (lsa->age == LSA_MAXAGE))
    change = 0;
68 69 70 71 72 73 74

  mb_free(en->lsa_body);
  en->lsa_body = body;
  en->lsa = *lsa;
  en->init_age = en->lsa.age;
  en->inst_time = now;

75 76 77 78 79 80 81 82 83 84
  /*
   * We do not set en->mode. It is either default LSA_M_BASIC, or in a special
   * case when en is local but flushed, there is postponed LSA, self-originated
   * LSA is received and ospf_install_lsa() is called from ospf_advance_lse(),
   * then we have en->mode from the postponed LSA origination.
   */

  OSPF_TRACE(D_EVENTS, "Installing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x, Age: %u",
	     en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn, en->lsa.age);

85
  if (change)
86
    ospf_schedule_rtcalc(p);
87 88 89 90

  return en;
}

91 92 93 94 95
/**
 * ospf_advance_lsa - handle received unexpected self-originated LSA
 * @p: OSPF protocol instance
 * @en: current LSA entry or NULL
 * @lsa: new LSA header
96
 * @type: type of LSA
97 98 99 100 101 102 103 104 105 106 107
 * @domain: domain of LSA
 * @body: pointer to LSA body
 *
 * This function handles received unexpected self-originated LSA (@lsa, @body)
 * by either advancing sequence number of the local LSA instance (@en) and
 * propagating it, or installing the received LSA and immediately flushing it
 * (if there is no local LSA; i.e., @en is NULL or MaxAge).
 *
 * The LSA body in @body is expected to be mb_allocated by the caller and its
 * ownership is transferred to the LSA entry structure or it is freed.
 */
108 109 110
void
ospf_advance_lsa(struct ospf_proto *p, struct top_hash_entry *en, struct ospf_lsa_header *lsa, u32 type, u32 domain, void *body)
{
111
  /* RFC 2328 13.4 */
112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131

  if (en && (en->lsa.age < LSA_MAXAGE))
  {
    if (lsa->sn != LSA_MAXSEQNO)
    {
      /*
       * We simply advance current LSA to have higher seqnum than received LSA.
       * The received LSA is ignored and the advanced LSA is propagated instead.
       *
       * Although this is an origination of distinct LSA instance and therefore
       * should be limited by MinLSInterval, we do not enforce it here. Fast
       * reaction is needed and we are already limited by MinLSArrival.
       */

      mb_free(body);

      en->lsa.sn = lsa->sn + 1;
      en->lsa.age = 0;
      en->init_age = 0;
      en->inst_time = now;
132
      lsa_generate_checksum(&en->lsa, en->lsa_body);
133 134 135

      OSPF_TRACE(D_EVENTS, "Advancing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
		 en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn);
136 137 138
    }
    else
    {
139
      /*
140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163
       * Received LSA has maximal sequence number, so we cannot simply override
       * it. We have to install it to the database, immediately flush it to
       * implement sequence number wrapping, and schedule our current LSA to be
       * originated after the received instance is flushed.
       */

      if (en->next_lsa_body == NULL)
      {
	/* Schedule current LSA */
	en->next_lsa_blen = en->lsa.length - sizeof(struct ospf_lsa_header);
	en->next_lsa_body = en->lsa_body;
	en->next_lsa_opts = ospf_is_v2(p) ? lsa_get_options(&en->lsa) : 0;
      }
      else
      {
	/* There is already scheduled LSA, so we just free current one */
	mb_free(en->lsa_body);
      }

      en->lsa_body = body;
      en->lsa = *lsa;
      en->lsa.age = LSA_MAXAGE;
      en->init_age = lsa->age;
      en->inst_time = now;
164 165 166 167 168

      OSPF_TRACE(D_EVENTS, "Resetting LSA:  Type: %04x, Id: %R, Rt: %R, Seq: %08x",
		 en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn);
      OSPF_TRACE(D_EVENTS, "Postponing LSA: Type: %04x, Id: %R, Rt: %R",
		 en->lsa_type, en->lsa.id, en->lsa.rt);
169 170
    }
  }
171
  else
172 173 174 175 176
  {
    /*
     * We do not have received LSA in the database. We have to flush the
     * received LSA. It has to be installed in the database to secure
     * retransmissions. Note that the received LSA may already be MaxAge.
177
     * Also note that en->next_lsa_* may be defined.
178 179 180 181 182 183
     */

    lsa->age = LSA_MAXAGE;
    en = ospf_install_lsa(p, lsa, type, domain, body);
  }

184
  /*
185 186
   * We flood the updated LSA. Although in some cases the to-be-flooded LSA is
   * the same as the received LSA, and therefore we should propagate it as
187
   * regular received LSA (send the acknowledgement instead of the update to
188 189 190
   * the neighbor we received it from), we cheat a bit here.
   */

191
  ospf_flood_lsa(p, en, NULL);
192 193 194
}


195 196
static int
ospf_do_originate_lsa(struct ospf_proto *p, struct top_hash_entry *en, void *lsa_body, u16 lsa_blen, u16 lsa_opts)
197
{
198 199 200 201 202 203 204 205 206 207
  /* Enforce MinLSInterval */
  if ((en->init_age == 0) && en->inst_time && ((en->inst_time + MINLSINTERVAL) > now))
    return 0;

  /* Handle wrapping sequence number */
  if (en->lsa.sn == LSA_MAXSEQNO)
  {
    /* Prepare to flush old LSA */
    if (en->lsa.age != LSA_MAXAGE)
    {
208 209
      OSPF_TRACE(D_EVENTS, "Resetting LSA:  Type: %04x, Id: %R, Rt: %R, Seq: %08x",
		 en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn);
210 211

      en->lsa.age = LSA_MAXAGE;
212
      ospf_flood_lsa(p, en, NULL);
213 214 215 216 217 218 219 220 221 222 223
      return 0;
    }

    /* Already flushing */
    if ((p->padj != 0) || (en->ret_count != 0))
      return 0;

    /* Flush done, just clean up seqnum, lsa_body is freed below */
    en->lsa.sn = LSA_ZEROSEQNO;
  }

224
  /*
225 226 227 228
   * lsa.type_raw is initialized by ospf_hash_get() to OSPFv3 LSA type.
   * lsa_set_options() implicitly converts it to OSPFv2 LSA type, assuming that
   * old type is just new type masked by 0xff.  That is not universally true,
   * but it holds for all OSPFv2 types currently supported by BIRD.
229
   */
230 231 232 233 234 235 236 237 238 239 240

  if (ospf_is_v2(p))
    lsa_set_options(&en->lsa, lsa_opts);

  mb_free(en->lsa_body);
  en->lsa_body = lsa_body;
  en->lsa.length = sizeof(struct ospf_lsa_header) + lsa_blen;
  en->lsa.sn++;
  en->lsa.age = 0;
  en->init_age = 0;
  en->inst_time = now;
241
  lsa_generate_checksum(&en->lsa, en->lsa_body);
242

243 244 245 246 247 248 249
  OSPF_TRACE(D_EVENTS, "Originating LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
	     en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn);

  ospf_flood_lsa(p, en, NULL);

  if (en->mode == LSA_M_BASIC)
    ospf_schedule_rtcalc(p);
250 251

  return 1;
252 253
}

254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274
/**
 * ospf_originate_lsa - originate new LSA
 * @p: OSPF protocol instance
 * @lsa: New LSA specification
 *
 * This function prepares a new LSA, installs it into the LSA database and
 * floods it. If the new LSA cannot be originated now (because the old instance
 * was originated within MinLSInterval, or because the LSA seqnum is currently
 * wrapping), the origination is instead scheduled for later. If the new LSA is
 * equivalent to the current LSA, the origination is skipped. In all cases, the
 * corresponding LSA entry is returned. The new LSA is based on the LSA
 * specification (@lsa) and the LSA body from lsab buffer of @p, which is
 * emptied after the call. The opposite of this function is ospf_flush_lsa().
 */
struct top_hash_entry *
ospf_originate_lsa(struct ospf_proto *p, struct ospf_new_lsa *lsa)
{
  struct top_hash_entry *en;
  void *lsa_body = p->lsab;
  u16 lsa_blen = p->lsab_used;
  u16 lsa_length = sizeof(struct ospf_lsa_header) + lsa_blen;
275

276
  en = ospf_hash_get(p->gr, lsa->dom, lsa->id, p->router_id, lsa->type);
277

278 279 280
  if (!SNODE_VALID(en))
    s_add_tail(&p->lsal, SNODE en);

281
  if (!en->nf || !en->lsa_body)
282 283 284 285 286 287
    en->nf = lsa->nf;

  if (en->nf != lsa->nf)
  {
    log(L_ERR "%s: LSA ID collision for %I/%d",
	p->p.name, lsa->nf->fn.prefix, lsa->nf->fn.pxlen);
288 289

    en = NULL;
290 291 292
    goto drop;
  }

293 294
  if (en->mode != lsa->mode)
    en->mode = lsa->mode;
295 296 297 298

  if (en->next_lsa_body)
  {
    /* Ignore the new LSA if it is the same as the scheduled one */
299 300 301
    if ((lsa_blen == en->next_lsa_blen) &&
	!memcmp(lsa_body, en->next_lsa_body, lsa_blen) &&
	(!ospf_is_v2(p) || (lsa->opts == en->next_lsa_opts)))
302 303 304 305 306 307 308 309 310 311
      goto drop;

    /* Free scheduled LSA */
    mb_free(en->next_lsa_body);
    en->next_lsa_body = NULL;
    en->next_lsa_blen = 0;
    en->next_lsa_opts = 0;
  }

  /* Ignore the the new LSA if is the same as the current one */
312 313 314 315
  if ((en->lsa.age < LSA_MAXAGE) &&
      (lsa_length == en->lsa.length) &&
      !memcmp(lsa_body, en->lsa_body, lsa_blen) &&
      (!ospf_is_v2(p) || (lsa->opts == lsa_get_options(&en->lsa))))
316 317 318 319 320 321
    goto drop;

  lsa_body = lsab_flush(p);

  if (! ospf_do_originate_lsa(p, en, lsa_body, lsa_blen, lsa->opts))
  {
322 323 324
    OSPF_TRACE(D_EVENTS, "Postponing LSA: Type: %04x, Id: %R, Rt: %R",
	       en->lsa_type, en->lsa.id, en->lsa.rt);

325 326 327 328 329 330 331 332 333 334 335 336 337 338
    en->next_lsa_body = lsa_body;
    en->next_lsa_blen = lsa_blen;
    en->next_lsa_opts = lsa->opts;
  }

  return en;

 drop:
  lsab_reset(p);
  return en;
}

static void
ospf_originate_next_lsa(struct ospf_proto *p, struct top_hash_entry *en)
339
{
340 341 342 343
  /* Called by ospf_update_lsadb() to handle scheduled origination */

  if (! ospf_do_originate_lsa(p, en, en->next_lsa_body, en->next_lsa_blen, en->next_lsa_opts))
    return;
344

345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361
  en->next_lsa_body = NULL;
  en->next_lsa_blen = 0;
  en->next_lsa_opts = 0;
}

static void
ospf_refresh_lsa(struct ospf_proto *p, struct top_hash_entry *en)
{
  /*
   * Called by ospf_update_lsadb() for periodic LSA refresh.
   *
   * We know that lsa.age < LSA_MAXAGE and lsa.rt is our router ID. We can also
   * assume that there is no scheduled LSA, because inst_time is deep in past,
   * therefore ospf_originate_next_lsa() called before would either succeed or
   * switched lsa.age to LSA_MAXAGE.
   */

362 363
  OSPF_TRACE(D_EVENTS, "Refreshing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
	     en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn);
364 365 366 367 368 369 370 371 372 373 374 375 376

  ASSERT(en->next_lsa_body == NULL);

  /* Handle wrapping sequence number */
  if (en->lsa.sn == LSA_MAXSEQNO)
  {
    /* Copy LSA body as next LSA to get automatic origination after flush is finished */
    en->next_lsa_blen = en->lsa.length - sizeof(struct ospf_lsa_header);
    en->next_lsa_body = mb_alloc(p->p.pool, en->next_lsa_blen);
    memcpy(en->next_lsa_body, en->lsa_body, en->next_lsa_blen);
    en->next_lsa_opts = ospf_is_v2(p) ? lsa_get_options(&en->lsa) : 0;

    en->lsa.age = LSA_MAXAGE;
377
    ospf_flood_lsa(p, en, NULL);
378 379 380 381 382 383 384
    return;
  }

  en->lsa.sn++;
  en->lsa.age = 0;
  en->init_age = 0;
  en->inst_time = now;
385
  lsa_generate_checksum(&en->lsa, en->lsa_body);
386
  ospf_flood_lsa(p, en, NULL);
387 388 389 390 391 392 393 394 395 396 397 398 399 400 401
}

/**
 * ospf_flush_lsa - flush LSA from OSPF domain
 * @p: OSPF protocol instance
 * @en: LSA entry to flush
 *
 * This function flushes @en from the OSPF domain by setting its age to
 * %LSA_MAXAGE and flooding it. That also triggers subsequent events in LSA
 * lifecycle leading to removal of the LSA from the LSA database (e.g. the LSA
 * content is freed when flushing is acknowledged by neighbors). The function
 * does nothing if the LSA is already being flushed. LSA entries are not
 * immediately removed when being flushed, the caller may assume that @en still
 * exists after the call. The function is the opposite of ospf_originate_lsa()
 * and is supposed to do the right thing even in cases of postponed
402
 * origination.
403 404 405 406 407 408 409 410 411 412 413 414 415 416 417
 */
void
ospf_flush_lsa(struct ospf_proto *p, struct top_hash_entry *en)
{
  if (en->next_lsa_body)
  {
    mb_free(en->next_lsa_body);
    en->next_lsa_body = NULL;
    en->next_lsa_blen = 0;
    en->next_lsa_opts = 0;
  }

  if (en->lsa.age == LSA_MAXAGE)
    return;

418 419 420
  OSPF_TRACE(D_EVENTS, "Flushing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
	     en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn);

421
  en->lsa.age = LSA_MAXAGE;
422 423 424 425 426 427
  ospf_flood_lsa(p, en, NULL);

  if (en->mode == LSA_M_BASIC)
    ospf_schedule_rtcalc(p);

  en->mode = LSA_M_BASIC;
428 429 430 431 432 433 434 435
}

static void
ospf_clear_lsa(struct ospf_proto *p, struct top_hash_entry *en)
{
  /*
   * Called by ospf_update_lsadb() as part of LSA flushing process.
   * Flushed LSA was acknowledged by neighbors and we can free its content.
436
   * The log message is for 'remove' - we hide empty LSAs from users.
437 438
   */

439 440 441
  OSPF_TRACE(D_EVENTS, "Removing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
	     en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn);

442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506
  if (en->lsa.sn == LSA_MAXSEQNO)
    en->lsa.sn = LSA_ZEROSEQNO;

  mb_free(en->lsa_body);
  en->lsa_body = NULL;
}

static void
ospf_remove_lsa(struct ospf_proto *p, struct top_hash_entry *en)
{
  /*
   * Called by ospf_update_lsadb() as part of LSA flushing process.
   * Both lsa_body and next_lsa_body are NULL.
   */

  s_rem_node(SNODE en);
  ospf_hash_delete(p->gr, en);
}

/**
 * ospf_update_lsadb - update LSA database
 * @p: OSPF protocol instance
 *
 * This function is periodicaly invoked from ospf_disp(). It does some periodic
 * or postponed processing related to LSA entries. It originates postponed LSAs
 * scheduled by ospf_originate_lsa(), It continues in flushing processes started
 * by ospf_flush_lsa(). It also periodically refreshs locally originated LSAs --
 * when the current instance is older %LSREFRESHTIME, a new instance is originated.
 * Finally, it also ages stored LSAs and flushes ones that reached %LSA_MAXAGE.
 *
 * The RFC 2328 says that a router should periodically check checksums of all
 * stored LSAs to detect hardware problems. This is not implemented.
 */
void
ospf_update_lsadb(struct ospf_proto *p)
{
  struct top_hash_entry *en, *nxt;
  bird_clock_t real_age;

  WALK_SLIST_DELSAFE(en, nxt, p->lsal)
  {
    if (en->next_lsa_body)
      ospf_originate_next_lsa(p, en);

    real_age = en->init_age + (now - en->inst_time);

    if (en->lsa.age == LSA_MAXAGE)
    {
      if (en->lsa_body && (p->padj == 0) && (en->ret_count == 0))
	ospf_clear_lsa(p, en);

      if ((en->lsa_body == NULL) && (en->next_lsa_body == NULL) &&
	  ((en->lsa.rt != p->router_id) || (real_age >= LSA_MAXAGE)))
	ospf_remove_lsa(p, en);

      continue;
    }

    if ((en->lsa.rt == p->router_id) && (real_age >= LSREFRESHTIME))
    {
      ospf_refresh_lsa(p, en);
      continue;
    }

    if (real_age >= LSA_MAXAGE)
507
    {
508 509
      ospf_flush_lsa(p, en);
      continue;
510
    }
511 512 513 514 515 516 517

    en->lsa.age = real_age;
  }
}


static inline u32
518
ort_to_lsaid(struct ospf_proto *p UNUSED4 UNUSED6, ort *nf)
519 520 521 522 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 555 556 557 558 559 560 561 562 563 564 565 566 567
{
  /*
   * In OSPFv2, 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 the IP address that
   * cannot be used by the 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 .
   *
   * 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.
   *
   * 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 (p->rtf).
   */

  if (ospf_is_v3(p))
    return nf->fn.uid;

  u32 id = ipa_to_u32(nf->fn.prefix);
  int pxlen = nf->fn.pxlen;

  if ((pxlen == 0) || (pxlen == 32))
    return id;

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


static void *
568
lsab_alloc(struct ospf_proto *p, uint size)
569
{
570
  uint offset = p->lsab_used;
571 572 573 574 575 576 577 578
  p->lsab_used += size;
  if (p->lsab_used > p->lsab_size)
  {
    p->lsab_size = MAX(p->lsab_used, 2 * p->lsab_size);
    p->lsab = p->lsab ? mb_realloc(p->lsab, p->lsab_size):
      mb_alloc(p->p.pool, p->lsab_size);
  }
  return ((byte *) p->lsab) + offset;
579 580 581
}

static inline void *
582
lsab_allocz(struct ospf_proto *p, uint size)
583
{
584
  void *r = lsab_alloc(p, size);
585 586 587 588 589
  bzero(r, size);
  return r;
}

static inline void *
590
lsab_flush(struct ospf_proto *p)
591
{
592 593 594
  void *r = mb_alloc(p->p.pool, p->lsab_used);
  memcpy(r, p->lsab, p->lsab_used);
  p->lsab_used = 0;
595 596 597
  return r;
}

598 599
static inline void
lsab_reset(struct ospf_proto *p)
600
{
601
  p->lsab_used = 0;
602 603 604
}

static inline void *
605
lsab_offset(struct ospf_proto *p, uint offset)
606
{
607
  return ((byte *) p->lsab) + offset;
608 609
}

610
static inline void * UNUSED
611
lsab_end(struct ospf_proto *p)
612
{
613
  return ((byte *) p->lsab) + p->lsab_used;
614 615
}

616

617 618 619 620 621
/*
 *	Router-LSA handling
 *	Type = LSA_T_RT
 */

622 623 624
static int
configured_stubnet(struct ospf_area *oa, struct ifa *a)
{
625
  /* Does not work for IA_PEER addresses, but it is not called on these */
626 627
  struct ospf_stubnet_config *sn;
  WALK_LIST(sn, oa->ac->stubnet_list)
628 629
  {
    if (sn->summary)
630
    {
631 632
      if (ipa_in_net(a->prefix, sn->px.addr, sn->px.len) && (a->pxlen >= sn->px.len))
	return 1;
633
    }
634 635 636 637 638 639 640
    else
    {
      if (ipa_equal(a->prefix, sn->px.addr) && (a->pxlen == sn->px.len))
	return 1;
    }
  }

641 642
  return 0;
}
643

644
static int
645 646 647 648 649 650 651 652
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)
653 654
  {
    if (neigh->state == NEIGHBOR_FULL)
655
    {
656 657
      if (neigh->rid == ifa->drid)
	return 1;
658

659 660
      if (ifa->state == OSPF_IS_DR)
	return 1;
661
    }
662
  }
663 664 665 666

  return 0;
}

667 668 669 670
static inline u32
get_rt_options(struct ospf_proto *p, struct ospf_area *oa, int bitv)
{
  u32 opts = 0;
671

672 673
  if (p->areano > 1)
    opts |= OPT_RT_B;
674

675 676
  if ((p->areano > 1) && oa_is_nssa(oa) && oa->ac->translator)
    opts |= OPT_RT_NT;
677

678 679
  if (p->asbr && !oa_is_stub(oa))
    opts |= OPT_RT_E;
680

681 682
  if (bitv)
    opts |= OPT_RT_V;
683

684 685
  return opts;
}
686

687 688 689 690 691 692 693 694 695 696
static inline void
add_rt2_lsa_link(struct ospf_proto *p, u8 type, u32 id, u32 data, u16 metric)
{
  struct ospf_lsa_rt2_link *ln = lsab_alloc(p, sizeof(struct ospf_lsa_rt2_link));
  ln->type = type;
  ln->id = id;
  ln->data = data;
  ln->metric = metric;
  ln->no_tos = 0;
}
697

698 699 700 701 702 703
static void
prepare_rt2_lsa_body(struct ospf_proto *p, struct ospf_area *oa)
{
  struct ospf_iface *ifa;
  int i = 0, bitv = 0;
  struct ospf_neighbor *neigh;
704

705 706 707
  ASSERT(p->lsab_used == 0);
  lsab_allocz(p, sizeof(struct ospf_lsa_rt));
  /* ospf_lsa_rt header will be filled later */
Ondřej Filip's avatar
Ondřej Filip committed
708

709
  WALK_LIST(ifa, p->iface_list)
710
  {
711
    int net_lsa = 0;
712
    u32 link_cost = p->stub_router ? 0xffff : ifa->cost;
713 714 715

    if ((ifa->type == OSPF_IT_VLINK) && (ifa->voa == oa) &&
	(!EMPTY_LIST(ifa->neigh_list)))
716 717 718
    {
      neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
      if ((neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
719
	bitv = 1;
720
    }
721 722

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

725 726
    ifa->rt_pos_beg = i;

727
    /* RFC 2328 - 12.4.1.1-4 */
728
    switch (ifa->type)
729 730 731 732 733
    {
    case OSPF_IT_PTP:
    case OSPF_IT_PTMP:
      WALK_LIST(neigh, ifa->neigh_list)
	if (neigh->state == NEIGHBOR_FULL)
Ondřej Filip's avatar
Ondřej Filip committed
734
	{
735 736 737 738 739 740 741 742 743
	  /*
	   * ln->data should be ifa->iface_id in case of no/ptp
	   * address (ifa->addr->flags & IA_PEER) on PTP link (see
	   * RFC 2328 12.4.1.1.), but the iface ID value has no use,
	   * while using IP address even in this case is here for
	   * compatibility with some broken implementations that use
	   * this address as a next-hop.
	   */
	  add_rt2_lsa_link(p, LSART_PTP, neigh->rid, ipa_to_u32(ifa->addr->ip), link_cost);
744
	  i++;
745 746
	}
      break;
747

748 749 750 751 752 753 754
    case OSPF_IT_BCAST:
    case OSPF_IT_NBMA:
      if (bcast_net_active(ifa))
      {
	add_rt2_lsa_link(p, LSART_NET, ipa_to_u32(ifa->drip), ipa_to_u32(ifa->addr->ip), link_cost);
	i++;
	net_lsa = 1;
755
      }
756 757 758 759 760 761 762 763 764
      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))
	add_rt2_lsa_link(p, LSART_VLNK, neigh->rid, ipa_to_u32(ifa->addr->ip), link_cost), i++;
      break;

    default:
765
      log(L_BUG "OSPF: Unknown interface type");
766 767
      break;
    }
768

769 770
    ifa->rt_pos_end = i;

771 772 773
    /* Now we will originate stub area if there is no primary */
    if (net_lsa ||
	(ifa->type == OSPF_IT_VLINK) ||
774
	((ifa->addr->flags & IA_PEER) && ! ifa->cf->stub) ||
775 776
	configured_stubnet(oa, ifa->addr))
      continue;
777

778
      /* Host or network stub entry */
779 780 781
    if ((ifa->addr->flags & IA_HOST) ||
	(ifa->state == OSPF_IS_LOOP) ||
	(ifa->type == OSPF_IT_PTMP))
782
      add_rt2_lsa_link(p, LSART_STUB, ipa_to_u32(ifa->addr->ip), 0xffffffff, 0);
783
    else
784
      add_rt2_lsa_link(p, LSART_STUB, ipa_to_u32(ifa->addr->prefix), u32_mkmask(ifa->addr->pxlen), ifa->cost);
785
    i++;
786 787

    ifa->rt_pos_end = i;
788
  }
789

790
  struct ospf_stubnet_config *sn;
791 792 793
  WALK_LIST(sn, oa->ac->stubnet_list)
    if (!sn->hidden)
      add_rt2_lsa_link(p, LSART_STUB, ipa_to_u32(sn->px.addr), u32_mkmask(sn->px.len), sn->cost), i++;
794

795
  struct ospf_lsa_rt *rt = p->lsab;
796
  /* Store number of links in lower half of options */
797
  rt->options = get_rt_options(p, oa, bitv) | (u16) i;
798
}
799

800 801
static inline void
add_rt3_lsa_link(struct ospf_proto *p, u8 type, struct ospf_iface *ifa, u32 nif, u32 id)
802
{
803
  struct ospf_lsa_rt3_link *ln = lsab_alloc(p, sizeof(struct ospf_lsa_rt3_link));
804 805 806
  ln->type = type;
  ln->padding = 0;
  ln->metric = ifa->cost;
807
  ln->lif = ifa->iface_id;
808 809 810 811
  ln->nif = nif;
  ln->id = id;
}

812 813
static void
prepare_rt3_lsa_body(struct ospf_proto *p, struct ospf_area *oa)
814 815
{
  struct ospf_iface *ifa;
816
  struct ospf_neighbor *neigh;
817
  int bitv = 0;
818
  int i = 0;
819

820 821 822
  ASSERT(p->lsab_used == 0);
  lsab_allocz(p, sizeof(struct ospf_lsa_rt));
  /* ospf_lsa_rt header will be filled later */
823

824
  WALK_LIST(ifa, p->iface_list)
825 826 827 828 829 830 831 832 833 834 835 836
  {
    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;

837 838
    ifa->rt_pos_beg = i;

839
    /* RFC 5340 - 4.4.3.2 */
840
    switch (ifa->type)
841 842 843 844 845 846 847
    {
    case OSPF_IT_PTP:
    case OSPF_IT_PTMP:
      WALK_LIST(neigh, ifa->neigh_list)
	if (neigh->state == NEIGHBOR_FULL)
	  add_rt3_lsa_link(p, LSART_PTP, ifa, neigh->iface_id, neigh->rid), i++;
      break;
848

849 850 851 852 853
    case OSPF_IT_BCAST:
    case OSPF_IT_NBMA:
      if (bcast_net_active(ifa))
	add_rt3_lsa_link(p, LSART_NET, ifa, ifa->dr_iface_id, ifa->drid), i++;
      break;
854

855 856 857 858 859 860 861
    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))
	add_rt3_lsa_link(p, LSART_VLNK, ifa, neigh->iface_id, neigh->rid), i++;
      break;

    default:
862
      log(L_BUG "OSPF: Unknown interface type");
863
      break;
864 865
    }

866 867
    ifa->rt_pos_end = i;
  }
868

869 870 871
  struct ospf_lsa_rt *rt = p->lsab;
  rt->options = get_rt_options(p, oa, bitv) | (oa->options & LSA_OPTIONS_MASK);
}
872

873 874
static void
ospf_originate_rt_lsa(struct ospf_proto *p, struct ospf_area *oa)
875
{
876 877 878 879 880 881
  struct ospf_new_lsa lsa = {
    .type = LSA_T_RT,
    .dom  = oa->areaid,
    .id   = ospf_is_v2(p) ? p->router_id : 0,
    .opts = oa->options
  };
882

883 884
  OSPF_TRACE(D_EVENTS, "Updating router state for area %R", oa->areaid);

885 886 887 888
  if (ospf_is_v2(p))
    prepare_rt2_lsa_body(p, oa);
  else
    prepare_rt3_lsa_body(p, oa);
Ondřej Filip's avatar
Ondřej Filip committed
889

890 891
  oa->rt = ospf_originate_lsa(p, &lsa);
}
892

893

894 895 896 897
/*
 *	Net-LSA handling
 *	Type = LSA_T_NET
 */
898

899 900
static void
prepare_net2_lsa_body(struct ospf_proto *p, struct ospf_iface *ifa)
901
{
902 903 904 905
  struct ospf_lsa_net *net;
  struct ospf_neighbor *n;
  int nodes = ifa->fadj + 1;
  u16 i = 1;
906

907 908
  ASSERT(p->lsab_used == 0);
  net = lsab_alloc(p, sizeof(struct ospf_lsa_net) + 4 * nodes);
909

910 911
  net->optx = u32_mkmask(ifa->addr->pxlen);
  net->routers[0] = p->router_id;
912

913 914 915 916 917 918 919 920 921
  WALK_LIST(n, ifa->neigh_list)
  {
    if (n->state == NEIGHBOR_FULL)
    {
      net->routers[i] = n->rid;
      i++;
    }
  }
  ASSERT(i == nodes);
922 923
}

924 925
static void
prepare_net3_lsa_body(struct ospf_proto *p, struct ospf_iface *ifa)
926
{
927
  struct ospf_lsa_net *net;
928 929
  int nodes = ifa->fadj + 1;
  u32 options = 0;
930 931 932 933
  u16 i = 1;

  ASSERT(p->lsab_used == 0);
  net = lsab_alloc(p, sizeof(struct ospf_lsa_net) + 4 * nodes);
934

935
  net->routers[0] = p->router_id;
936

937
  struct ospf_neighbor *n;
Ondřej Filip's avatar
Ondřej Filip committed
938
  WALK_LIST(n, ifa->neigh_list)
939
  {
Ondřej Filip's avatar
Ondřej Filip committed
940
    if (n->state == NEIGHBOR_FULL)
941
    {
942 943 944 945 946
      /* In OSPFv3, we would like to merge options from Link LSAs of added neighbors */

      struct top_hash_entry *en =
	ospf_hash_find(p->gr, ifa->iface_id, n->iface_id, n->rid, LSA_T_LINK);

947 948 949 950
      if (en)
	options |= ((struct ospf_lsa_link *) en->lsa_body)->options;

      net->routers[i] = n->rid;
951 952 953
      i++;
    }
  }
954 955
  ASSERT(i == nodes);

956
  net->optx = options & LSA_OPTIONS_MASK;
957 958
}

959 960 961 962 963 964 965 966 967 968 969
static void
ospf_originate_net_lsa(struct ospf_proto *p, struct ospf_iface *ifa)
{
  struct ospf_new_lsa lsa = {
    .type = LSA_T_NET,
    .dom  = ifa->oa->areaid,
    .id   = ospf_is_v2(p) ? ipa_to_u32(ifa->addr->ip) : ifa->iface_id,
    .opts = ifa->oa->options,
    .ifa  = ifa
  };

970 971
  OSPF_TRACE(D_EVENTS, "Updating network state for %s (Id: %R)", ifa->ifname, lsa.id);

972 973
  if (ospf_is_v2(p))
    prepare_net2_lsa_body(p, ifa);
974
  else
975
    prepare_net3_lsa_body(p, ifa);
976

977
  ifa->net_lsa = ospf_originate_lsa(p, &lsa);
978 979
}

980

981 982 983 984 985
/*
 *	(Net|Rt)-summary-LSA handling
 *	(a.k.a. Inter-Area-(Prefix|Router)-LSA)
 *	Type = LSA_T_SUM_NET, LSA_T_SUM_RT
 */
986

987 988
static inline void
prepare_sum2_lsa_body(struct ospf_proto *p, uint pxlen, u32 metric)
989
{
990
  struct ospf_lsa_sum2 *sum;
991

992 993
  sum = lsab_allocz(p, sizeof(struct ospf_lsa_sum2));
  sum->netmask = u32_mkmask(pxlen);
994 995 996
  sum->metric = metric;
}

997 998
static inline void
prepare_sum3_net_lsa_body(struct ospf_proto *p, ort *nf, u32 metric)
999
{
1000
  struct ospf_lsa_sum3_net *sum;
1001

1002 1003 1004
  sum = lsab_allocz(p, sizeof(struct ospf_lsa_sum3_net) + IPV6_PREFIX_SPACE(nf->fn.pxlen));
  sum->metric = metric;
  put_ipv6_prefix(sum->prefix, nf->fn.prefix, nf->fn.pxlen, 0, 0);
1005 1006
}

1007 1008
static inline void
prepare_sum3_rt_lsa_body(struct ospf_proto *p, u32 drid, u32 metric, u32 options)
1009
{
1010
  struct ospf_lsa_sum3_rt *sum;
1011

1012
  sum = lsab_allocz(p, sizeof(struct ospf_lsa_sum3_rt));
1013
  sum->options = options;
1014 1015
  sum->metric = metric;
  sum->drid = drid;
1016 1017
}

Ondřej Filip's avatar
Ondřej Filip committed
1018
void
1019
ospf_originate_sum_net_lsa(struct ospf_proto *p, struct ospf_area *oa, ort *nf, int metric)
Ondřej Filip's avatar
Ondřej Filip committed
1020
{
1021 1022
  struct ospf_new_lsa lsa = {
    .type = LSA_T_SUM_NET,
1023
    .mode = LSA_M_RTCALC,
1024 1025 1026 1027 1028
    .dom  = oa->areaid,
    .id   = ort_to_lsaid(p, nf),
    .opts = oa->options,
    .nf   = nf
  };
1029

1030 1031 1032 1033
  if (ospf_is_v2(p))
    prepare_sum2_lsa_body(p, nf->fn.pxlen, metric);
  else
    prepare_sum3_net_lsa_body(p, nf, metric);
1034

1035
  ospf_originate_lsa(p, &lsa);
1036
}
1037

1038
void
1039
ospf_originate_sum_rt_lsa(struct ospf_proto *p, struct ospf_area *oa, ort *nf, int metric, u32 options)
1040
{
1041 1042
  struct ospf_new_lsa lsa = {
    .type = LSA_T_SUM_RT,
1043
    .mode = LSA_M_RTCALC,
1044
    .dom  = oa->areaid,
1045
    .id   = ipa_to_rid(nf->fn.prefix),	/* Router ID of ASBR, irrelevant for OSPFv3 */
1046 1047
    .opts = oa->options
  };
Ondřej Filip's avatar
Ondřej Filip committed
1048

1049 1050
  if (ospf_is_v2(p))
    prepare_sum2_lsa_body(p, 0, metric);
1051
  else
1052
    prepare_sum3_rt_lsa_body(p, lsa.id, metric, options & LSA_OPTIONS_MASK);
1053

1054
  ospf_originate_lsa(p, &lsa);
Ondřej Filip's avatar
Ondřej Filip committed
1055 1056
}

1057

1058
/*
1059 1060
 *	AS-external-LSA and NSSA-LSA handling
 *	Type = LSA_T_EXT, LSA_T_NSSA
1061
 */
1062

1063 1064 1065
static inline void
prepare_ext2_lsa_body(struct ospf_proto *p, uint pxlen,
		      u32 metric, u32 ebit, ip_addr fwaddr, u32 tag)
1066
{
1067
  struct ospf_lsa_ext2 *ext;
1068

1069 1070 1071 1072 1073
  ext = lsab_allocz(p, sizeof(struct ospf_lsa_ext2));
  ext->metric = metric & LSA_METRIC_MASK;
  ext->netmask = u32_mkmask(pxlen);
  ext->fwaddr = ipa_to_u32(fwaddr);
  ext->tag = tag;
1074

1075 1076
  if (ebit)
    ext->metric |= LSA_EXT2_EBIT;
1077
}
1078

1079 1080 1081
static inline void
prepare_ext3_lsa_body(struct ospf_proto *p, ort *nf,
		      u32 metric, u32 ebit, ip_addr fwaddr, u32 tag, int pbit)
1082
{
1083 1084 1085
  struct ospf_lsa_ext3 *ext;
  int bsize = sizeof(struct ospf_lsa_ext3)
    + IPV6_PREFIX_SPACE(nf->fn.pxlen)
1086 1087 1088
    + (ipa_nonzero(fwaddr) ? 16 : 0)
    + (tag ? 4 : 0);

1089 1090 1091
  ext = lsab_allocz(p, bsize);
  ext->metric = metric & LSA_METRIC_MASK;
  u32 *buf = ext->rest;
1092

1093
  buf = put_ipv6_prefix(buf, nf->fn.prefix, nf->fn.pxlen, pbit ? OPT_PX_P : 0, 0);
1094

1095 1096
  if (ebit)
    ext->metric |= LSA_EXT3_EBIT;
1097

1098 1099
  if (ipa_nonzero(fwaddr))
  {
1100
    ext->metric |= LSA_EXT3_FBIT;
1101 1102
    buf = put_ipv6_addr(buf, fwaddr);
  }
1103 1104

  if (tag)
1105
  {
1106
    ext->metric |= LSA_EXT3_TBIT;
1107 1108
    *buf++ = tag;
  }
1109 1110
}

1111 1112
/**
 * originate_ext_lsa - new route received from nest and filters
1113
 * @p: OSPF protocol instance
1114 1115
 * @oa: ospf_area for which LSA is originated
 * @nf: network prefix and mask
1116 1117 1118
 * @mode: the mode of the LSA (LSA_M_EXPORT or LSA_M_RTCALC)
 * @metric: the metric of a route
 * @ebit: E-bit for route metric (bool)
1119 1120
 * @fwaddr: the forwarding address
 * @tag: the route tag
1121
 * @pbit: P-bit for NSSA LSAs (bool), ignored for external LSAs
1122 1123 1124 1125
 *
 * If I receive a message that new route is installed, I try to originate an
 * external LSA. If @oa is an NSSA area, NSSA-LSA is originated instead.
 * @oa should not be a stub area. @src does not specify whether the LSA
1126
 * is external or NSSA, but it specifies the source of origination -
1127 1128 1129
 * the export from ospf_rt_notify(), or the NSSA-EXT translation.
 */
void
1130
ospf_originate_ext_lsa(struct ospf_proto *p, struct ospf_area *oa, ort *nf, u8 mode,
1131
		       u32 metric, u32 ebit, ip_addr fwaddr, u32 tag, int pbit)
1132
{
1133 1134
  struct ospf_new_lsa lsa = {
    .type = oa ? LSA_T_NSSA : LSA_T_EXT,
1135
    .mode = mode, /* LSA_M_EXPORT or LSA_M_RTCALC */
1136 1137 1138 1139 1140
    .dom  = oa ? oa->areaid : 0,
    .id   = ort_to_lsaid(p, nf),
    .opts = oa ? (pbit ? OPT_P : 0) : OPT_E,
    .nf   = nf
  };
1141

1142 1143 1144 1145
  if (ospf_is_v2(p))
    prepare_ext2_lsa_body(p, nf->fn.pxlen, metric, ebit, fwaddr, tag);
  else
    prepare_ext3_lsa_body(p, nf, metric, ebit, fwaddr, tag, oa && pbit);
1146

1147
  ospf_originate_lsa(p, &lsa);
1148 1149
}

1150 1151 1152
static struct top_hash_entry *
ospf_hash_find_(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type);

1153 1154 1155 1156
static void
ospf_flush_ext_lsa(struct ospf_proto *p, struct ospf_area *oa, ort *nf)
{
  struct top_hash_entry *en;
1157

1158 1159 1160
  u32 type = oa ? LSA_T_NSSA : LSA_T_EXT;
  u32 dom = oa ? oa->areaid : 0;
  u32 id = ort_to_lsaid(p, nf);
1161

1162
  en = ospf_hash_find_(p->gr, dom, id, p->router_id, type);
1163

1164 1165
  if (!en || (en->nf != nf))
    return;
1166

1167
  ospf_flush_lsa(p, en);
1168 1169
}

1170 1171 1172 1173 1174 1175 1176
static inline int
use_gw_for_fwaddr(struct ospf_proto *p, ip_addr gw, struct iface *iface)
{
  struct ospf_iface *ifa;

  if (ipa_zero(gw) || ipa_is_link_local(gw))
    return 0;
1177

1178 1179
  WALK_LIST(ifa, p->iface_list)
    if ((ifa->iface == iface) &&
1180
	(!ospf_is_v2(p) || ipa_in_net(gw, ifa->addr->prefix, ifa->addr->pxlen)))
1181 1182 1183 1184
      return 1;

  return 0;
}
1185

1186
static inline ip_addr
1187
find_surrogate_fwaddr(struct ospf_proto *p, struct ospf_area *oa)
1188 1189 1190 1191 1192
{
  struct ospf_iface *ifa;
  struct ifa *a, *cur_addr = NULL;
  int np, cur_np = 0;

1193 1194 1195
  /* RFC 3101 2.3 - surrogate forwarding address selection */

  WALK_LIST(ifa, p->iface_list)
1196 1197 1198 1199 1200
  {
    if ((ifa->oa != oa) ||
	(ifa->type == OSPF_IT_VLINK))
      continue;

1201
    if (ospf_is_v2(p))
1202
    {
1203 1204
      a = ifa->addr;
      if (a->flags & IA_PEER)
1205 1206
	continue;

1207
      np = (a->flags & IA_HOST) ? 3 : (ifa->stub ? 2 : 1);
1208 1209 1210 1211 1212 1213
      if (np > cur_np)
      {
	cur_addr = a;
	cur_np = np;
      }
    }
1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230
    else /* OSPFv3 */
    {
      WALK_LIST(a, ifa->iface->addrs)
      {
	if ((a->flags & IA_SECONDARY) ||
	    (a->flags & IA_PEER) ||
	    (a->scope <= SCOPE_LINK))
	  continue;

	np = (a->flags & IA_HOST) ? 3 : (ifa->stub ? 2 : 1);
	if (np > cur_np)
	{
	  cur_addr = a;
	  cur_np = np;
	}
      }
    }
1231 1232 1233 1234 1235
  }

  return cur_addr ? cur_addr->ip : IPA_NONE;
}

1236
void
1237
ospf_rt_notify(struct proto *P, rtable *tbl UNUSED, net *n, rte *new, rte *old UNUSED, ea_list *ea)
1238
{
1239 1240 1241
  struct ospf_proto *p = (struct ospf_proto *) P;
  struct ospf_area *oa = NULL;	/* non-NULL for NSSA-LSA */
  ort *nf;
1242

1243 1244 1245 1246 1247 1248 1249
  /*
   * There are several posibilities:
   * 1) router in regular area - originate external LSA with global scope
   * 2) router in NSSA area - originate area-specific NSSA-LSA
   * 3) router in stub area - cannot export routes
   * 4) area border router - same as (1), it is attached to backbone
   */
Ondřej Filip's avatar
Ondřej Filip committed
1250

1251 1252
  if ((p->areano == 1) && oa_is_nssa(HEAD(p->area_list)))
    oa = HEAD(p->area_list);
1253

1254
  if (!new)
1255
  {
1256
    nf = (ort *) fib_find(&p->rtf, &n->n.prefix, n->n.pxlen);
1257

1258
    if (!nf || !nf->external_rte)
1259
      return;
1260

1261 1262
    ospf_flush_ext_lsa(p, oa, nf);
    nf->external_rte = 0;
1263

1264 1265
    /* Old external route might blocked some NSSA translation */
    if ((p->areano > 1) && rt_is_nssa(nf) && nf->n.oa->translate)
1266
      ospf_schedule_rtcalc(p);
1267

1268 1269
    return;
  }
1270

1271
  ASSERT(p->asbr);
1272

1273 1274 1275 1276 1277 1278 1279 1280
  /* Get route attributes */
  rta *a = new->attrs;
  u32 m1 = ea_get_int(ea, EA_OSPF_METRIC1, LSINFINITY);
  u32 m2 = ea_get_int(ea, EA_OSPF_METRIC2, 10000);
  int ebit = (m1 == LSINFINITY);
  u32 metric = ebit ? m2 : m1;
  u32 tag = ea_get_int(ea, EA_OSPF_TAG, 0);
  ip_addr fwd = IPA_NONE;
1281

1282

1283 1284
  if ((a->dest == RTD_ROUTER) && use_gw_for_fwaddr(p, a->gw, a->iface))
    fwd = a->gw;
1285

1286 1287 1288 1289
  /* NSSA-LSA with P-bit set must have non-zero forwarding address */
  if (oa && ipa_zero(fwd))
  {
    fwd = find_surrogate_fwaddr(p, oa);
1290

1291
    if (ipa_zero(fwd))
1292
    {
1293 1294 1295
      log(L_ERR "%s: Cannot find forwarding address for NSSA-LSA %I/%d",
	  p->p.name, n->n.prefix, n->n.pxlen);
      return;
1296
    }
1297 1298 1299
  }

  nf = (ort *) fib_get(&p->rtf, &n->n.prefix, n->n.pxlen);
1300
  ospf_originate_ext_lsa(p, oa, nf, LSA_M_EXPORT, metric, ebit, fwd, tag, 1);
1301
  nf->external_rte = 1;
1302 1303 1304
}


1305 1306 1307 1308
/*
 *	Link-LSA handling (assume OSPFv3)
 *	Type = LSA_T_LINK
 */
1309

1310 1311 1312 1313 1314 1315 1316 1317 1318 1319
static inline void
lsab_put_prefix(struct ospf_proto *p, ip_addr prefix, u32 pxlen, u32 cost)
{
  void *buf = lsab_alloc(p, IPV6_PREFIX_SPACE(pxlen));
  u8 flags = (pxlen < MAX_PREFIX_LENGTH) ? 0 : OPT_PX_LA;
  put_ipv6_prefix(buf, prefix, pxlen, flags, cost);
}

static void
prepare_link_lsa_body(struct ospf_proto *p, struct ospf_iface *ifa)
1320 1321 1322 1323
{
  struct ospf_lsa_link *ll;
  int i = 0;

1324 1325
  ASSERT(p->lsab_used == 0);
  ll = lsab_allocz(p, sizeof(struct ospf_lsa_link));
1326
  ll->options = ifa->oa->options | (ifa->priority << 24);
1327
  ll->lladdr = ipa_to_ip6(ifa->addr->ip);
1328 1329 1330 1331
  ll = NULL; /* buffer might be reallocated later */

  struct ifa *a;
  WALK_LIST(a, ifa->iface->addrs)
1332 1333 1334 1335
  {
    if ((a->flags & IA_SECONDARY) ||
	(a->scope < SCOPE_SITE))
      continue;
1336

1337 1338 1339
    lsab_put_prefix(p, a->prefix, a->pxlen, 0);
    i++;
  }
1340

1341
  ll = p->lsab;
1342 1343 1344
  ll->pxcount = i;
}

1345 1346
static void
ospf_originate_link_lsa(struct ospf_proto *p, struct ospf_iface *ifa)
1347
{
1348
  if (ospf_is_v2(p))
1349 1350
    return;

1351 1352 1353 1354 1355 1356
  struct ospf_new_lsa lsa = {
    .type = LSA_T_LINK,
    .dom  = ifa->iface_id,
    .id   = ifa->iface_id,
    .ifa  = ifa
  };
1357

1358 1359
  OSPF_TRACE(D_EVENTS, "Updating link state for %s (Id: %R)", ifa->ifname, lsa.id);

1360
  prepare_link_lsa_body(p, ifa);
1361

1362
  ifa->link_lsa = ospf_originate_lsa(p, &lsa);
1363 1364 1365
}


1366 1367 1368 1369
/*
 *	Prefix-Rt-LSA handling (assume OSPFv3)
 *	Type = LSA_T_PREFIX, referred type = LSA_T_RT
 */
1370

1371 1372
static void
prepare_prefix_rt_lsa_body(struct ospf_proto *p, struct ospf_area *oa)