Annotation of embedaddon/bird2/proto/ospf/topology.c, revision 1.1
1.1 ! misho 1: /*
! 2: * BIRD -- OSPF Topological Database
! 3: *
! 4: * (c) 1999 Martin Mares <mj@ucw.cz>
! 5: * (c) 1999--2004 Ondrej Filip <feela@network.cz>
! 6: * (c) 2009--2014 Ondrej Zajicek <santiago@crfreenet.org>
! 7: * (c) 2009--2014 CZ.NIC z.s.p.o.
! 8: *
! 9: * Can be freely distributed and used under the terms of the GNU GPL.
! 10: */
! 11:
! 12: #include "nest/bird.h"
! 13: #include "lib/string.h"
! 14:
! 15: #include "ospf.h"
! 16:
! 17:
! 18: #define HASH_DEF_ORDER 6
! 19: #define HASH_HI_MARK *4
! 20: #define HASH_HI_STEP 2
! 21: #define HASH_HI_MAX 16
! 22: #define HASH_LO_MARK /5
! 23: #define HASH_LO_STEP 2
! 24: #define HASH_LO_MIN 8
! 25:
! 26: static inline void * lsab_flush(struct ospf_proto *p);
! 27: static inline void lsab_reset(struct ospf_proto *p);
! 28:
! 29:
! 30: /**
! 31: * ospf_install_lsa - install new LSA into database
! 32: * @p: OSPF protocol instance
! 33: * @lsa: LSA header
! 34: * @type: type of LSA
! 35: * @domain: domain of LSA
! 36: * @body: pointer to LSA body
! 37: *
! 38: * This function ensures installing new LSA received in LS update into LSA
! 39: * database. Old instance is replaced. Several actions are taken to detect if
! 40: * new routing table calculation is necessary. This is described in 13.2 of RFC
! 41: * 2328. This function is for received LSA only, locally originated LSAs are
! 42: * installed by ospf_originate_lsa().
! 43: *
! 44: * The LSA body in @body is expected to be mb_allocated by the caller and its
! 45: * ownership is transferred to the LSA entry structure.
! 46: */
! 47: struct top_hash_entry *
! 48: ospf_install_lsa(struct ospf_proto *p, struct ospf_lsa_header *lsa, u32 type, u32 domain, void *body)
! 49: {
! 50: struct top_hash_entry *en;
! 51: int change = 0;
! 52:
! 53: en = ospf_hash_get(p->gr, domain, lsa->id, lsa->rt, type);
! 54:
! 55: if (!SNODE_VALID(en))
! 56: s_add_tail(&p->lsal, SNODE en);
! 57:
! 58: if ((en->lsa_body == NULL) || /* No old LSA */
! 59: (en->lsa.length != lsa->length) ||
! 60: (en->lsa.type_raw != lsa->type_raw) || /* Check for OSPFv2 options */
! 61: (en->lsa.age == LSA_MAXAGE) ||
! 62: (lsa->age == LSA_MAXAGE) ||
! 63: memcmp(en->lsa_body, body, lsa->length - sizeof(struct ospf_lsa_header)))
! 64: change = 1;
! 65:
! 66: if ((en->lsa.age == LSA_MAXAGE) && (lsa->age == LSA_MAXAGE))
! 67: change = 0;
! 68:
! 69: mb_free(en->lsa_body);
! 70: en->lsa_body = body;
! 71: en->lsa = *lsa;
! 72: en->init_age = en->lsa.age;
! 73: en->inst_time = current_time();
! 74: en->gr_dirty = p->gr_recovery && (lsa->rt == p->router_id);
! 75:
! 76: /*
! 77: * We do not set en->mode. It is either default LSA_M_BASIC, or in a special
! 78: * case when en is local but flushed, there is postponed LSA, self-originated
! 79: * LSA is received and ospf_install_lsa() is called from ospf_advance_lse(),
! 80: * then we have en->mode from the postponed LSA origination.
! 81: */
! 82:
! 83: OSPF_TRACE(D_EVENTS, "Installing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x, Age: %u",
! 84: en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn, en->lsa.age);
! 85:
! 86: if (change)
! 87: {
! 88: ospf_neigh_lsadb_changed(p, en);
! 89: ospf_schedule_rtcalc(p);
! 90: }
! 91:
! 92: return en;
! 93: }
! 94:
! 95: /**
! 96: * ospf_advance_lsa - handle received unexpected self-originated LSA
! 97: * @p: OSPF protocol instance
! 98: * @en: current LSA entry or NULL
! 99: * @lsa: new LSA header
! 100: * @type: type of LSA
! 101: * @domain: domain of LSA
! 102: * @body: pointer to LSA body
! 103: *
! 104: * This function handles received unexpected self-originated LSA (@lsa, @body)
! 105: * by either advancing sequence number of the local LSA instance (@en) and
! 106: * propagating it, or installing the received LSA and immediately flushing it
! 107: * (if there is no local LSA; i.e., @en is NULL or MaxAge).
! 108: *
! 109: * The LSA body in @body is expected to be mb_allocated by the caller and its
! 110: * ownership is transferred to the LSA entry structure or it is freed.
! 111: */
! 112: void
! 113: ospf_advance_lsa(struct ospf_proto *p, struct top_hash_entry *en, struct ospf_lsa_header *lsa, u32 type, u32 domain, void *body)
! 114: {
! 115: /* RFC 2328 13.4 */
! 116:
! 117: if (en && (en->lsa.age < LSA_MAXAGE))
! 118: {
! 119: if (lsa->sn != LSA_MAXSEQNO)
! 120: {
! 121: /*
! 122: * We simply advance current LSA to have higher seqnum than received LSA.
! 123: * The received LSA is ignored and the advanced LSA is propagated instead.
! 124: *
! 125: * Although this is an origination of distinct LSA instance and therefore
! 126: * should be limited by MinLSInterval, we do not enforce it here. Fast
! 127: * reaction is needed and we are already limited by MinLSArrival.
! 128: */
! 129:
! 130: mb_free(body);
! 131:
! 132: en->lsa.sn = lsa->sn + 1;
! 133: en->lsa.age = 0;
! 134: en->init_age = 0;
! 135: en->inst_time = current_time();
! 136: lsa_generate_checksum(&en->lsa, en->lsa_body);
! 137:
! 138: OSPF_TRACE(D_EVENTS, "Advancing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
! 139: en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn);
! 140: }
! 141: else
! 142: {
! 143: /*
! 144: * Received LSA has maximal sequence number, so we cannot simply override
! 145: * it. We have to install it to the database, immediately flush it to
! 146: * implement sequence number wrapping, and schedule our current LSA to be
! 147: * originated after the received instance is flushed.
! 148: */
! 149:
! 150: if (en->next_lsa_body == NULL)
! 151: {
! 152: /* Schedule current LSA */
! 153: en->next_lsa_blen = en->lsa.length - sizeof(struct ospf_lsa_header);
! 154: en->next_lsa_body = en->lsa_body;
! 155: en->next_lsa_opts = ospf_is_v2(p) ? lsa_get_options(&en->lsa) : 0;
! 156: }
! 157: else
! 158: {
! 159: /* There is already scheduled LSA, so we just free current one */
! 160: mb_free(en->lsa_body);
! 161: }
! 162:
! 163: en->lsa_body = body;
! 164: en->lsa = *lsa;
! 165: en->lsa.age = LSA_MAXAGE;
! 166: en->init_age = lsa->age;
! 167: en->inst_time = current_time();
! 168:
! 169: OSPF_TRACE(D_EVENTS, "Resetting LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
! 170: en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn);
! 171: OSPF_TRACE(D_EVENTS, "Postponing LSA: Type: %04x, Id: %R, Rt: %R",
! 172: en->lsa_type, en->lsa.id, en->lsa.rt);
! 173: }
! 174: }
! 175: else
! 176: {
! 177: /*
! 178: * We do not have received LSA in the database. We have to flush the
! 179: * received LSA. It has to be installed in the database to secure
! 180: * retransmissions. Note that the received LSA may already be MaxAge.
! 181: * Also note that en->next_lsa_* may be defined.
! 182: */
! 183:
! 184: lsa->age = LSA_MAXAGE;
! 185: en = ospf_install_lsa(p, lsa, type, domain, body);
! 186: }
! 187:
! 188: /*
! 189: * We flood the updated LSA. Although in some cases the to-be-flooded LSA is
! 190: * the same as the received LSA, and therefore we should propagate it as
! 191: * regular received LSA (send the acknowledgement instead of the update to
! 192: * the neighbor we received it from), we cheat a bit here.
! 193: */
! 194:
! 195: ospf_flood_lsa(p, en, NULL);
! 196: }
! 197:
! 198:
! 199: static int
! 200: ospf_do_originate_lsa(struct ospf_proto *p, struct top_hash_entry *en, void *lsa_body, u16 lsa_blen, u16 lsa_opts)
! 201: {
! 202: /* Enforce MinLSInterval */
! 203: if (!en->init_age && en->inst_time && (lsa_inst_age(en) < MINLSINTERVAL))
! 204: return 0;
! 205:
! 206: /* Handle wrapping sequence number */
! 207: if (en->lsa.sn == LSA_MAXSEQNO)
! 208: {
! 209: /* Prepare to flush old LSA */
! 210: if (en->lsa.age != LSA_MAXAGE)
! 211: {
! 212: OSPF_TRACE(D_EVENTS, "Resetting LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
! 213: en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn);
! 214:
! 215: en->lsa.age = LSA_MAXAGE;
! 216: ospf_flood_lsa(p, en, NULL);
! 217: return 0;
! 218: }
! 219:
! 220: /* Already flushing */
! 221: if ((p->padj != 0) || (en->ret_count != 0))
! 222: return 0;
! 223:
! 224: /* Flush done, just clean up seqnum, lsa_body is freed below */
! 225: en->lsa.sn = LSA_ZEROSEQNO;
! 226: }
! 227:
! 228: /*
! 229: * lsa.type_raw is initialized by ospf_hash_get() to OSPFv3 LSA type.
! 230: * lsa_set_options() implicitly converts it to OSPFv2 LSA type, assuming that
! 231: * old type is just new type masked by 0xff. That holds for most OSPFv2 types,
! 232: * but we have to fix it for opaque LSAs.
! 233: */
! 234:
! 235: if (ospf_is_v2(p))
! 236: {
! 237: if (lsa_is_opaque(en->lsa_type))
! 238: en->lsa.type_raw = LSA_T_V2_OPAQUE_ + LSA_SCOPE_ORDER(en->lsa_type);
! 239:
! 240: lsa_set_options(&en->lsa, lsa_opts);
! 241: }
! 242:
! 243: mb_free(en->lsa_body);
! 244: en->lsa_body = lsa_body;
! 245: en->lsa.length = sizeof(struct ospf_lsa_header) + lsa_blen;
! 246: en->lsa.sn++;
! 247: en->lsa.age = 0;
! 248: en->init_age = 0;
! 249: en->inst_time = current_time();
! 250: en->gr_dirty = 0;
! 251: lsa_generate_checksum(&en->lsa, en->lsa_body);
! 252:
! 253: OSPF_TRACE(D_EVENTS, "Originating LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
! 254: en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn);
! 255:
! 256: ospf_flood_lsa(p, en, NULL);
! 257:
! 258: if (en->mode == LSA_M_BASIC)
! 259: {
! 260: ospf_neigh_lsadb_changed(p, en);
! 261: ospf_schedule_rtcalc(p);
! 262: }
! 263:
! 264: return 1;
! 265: }
! 266:
! 267: /**
! 268: * ospf_originate_lsa - originate new LSA
! 269: * @p: OSPF protocol instance
! 270: * @lsa: New LSA specification
! 271: *
! 272: * This function prepares a new LSA, installs it into the LSA database and
! 273: * floods it. If the new LSA cannot be originated now (because the old instance
! 274: * was originated within MinLSInterval, or because the LSA seqnum is currently
! 275: * wrapping), the origination is instead scheduled for later. If the new LSA is
! 276: * equivalent to the current LSA, the origination is skipped. In all cases, the
! 277: * corresponding LSA entry is returned. The new LSA is based on the LSA
! 278: * specification (@lsa) and the LSA body from lsab buffer of @p, which is
! 279: * emptied after the call. The opposite of this function is ospf_flush_lsa().
! 280: */
! 281: struct top_hash_entry *
! 282: ospf_originate_lsa(struct ospf_proto *p, struct ospf_new_lsa *lsa)
! 283: {
! 284: struct top_hash_entry *en = NULL;
! 285: void *lsa_body = p->lsab;
! 286: u16 lsa_blen = p->lsab_used;
! 287: u16 lsa_length = sizeof(struct ospf_lsa_header) + lsa_blen;
! 288:
! 289: /* RFC 3623 2 (1) - do not originate topology LSAs during graceful restart */
! 290: if (p->gr_recovery && (LSA_FUNCTION(lsa->type) <= LSA_FUNCTION(LSA_T_NSSA)))
! 291: goto drop;
! 292:
! 293: /* For OSPFv2 Opaque LSAs, LS ID consists of Opaque Type and Opaque ID */
! 294: if (ospf_is_v2(p) && lsa_is_opaque(lsa->type))
! 295: lsa->id |= (u32) lsa_get_opaque_type(lsa->type) << 24;
! 296:
! 297: en = ospf_hash_get(p->gr, lsa->dom, lsa->id, p->router_id, lsa->type);
! 298:
! 299: if (!SNODE_VALID(en))
! 300: s_add_tail(&p->lsal, SNODE en);
! 301:
! 302: if (!en->nf || !en->lsa_body)
! 303: en->nf = lsa->nf;
! 304:
! 305: if (en->nf != lsa->nf)
! 306: {
! 307: log(L_ERR "%s: LSA ID collision for %N",
! 308: p->p.name, lsa->nf->fn.addr);
! 309:
! 310: en = NULL;
! 311: goto drop;
! 312: }
! 313:
! 314: if (en->mode != lsa->mode)
! 315: en->mode = lsa->mode;
! 316:
! 317: if (en->next_lsa_body)
! 318: {
! 319: /* Ignore the new LSA if it is the same as the scheduled one */
! 320: if ((lsa_blen == en->next_lsa_blen) &&
! 321: !memcmp(lsa_body, en->next_lsa_body, lsa_blen) &&
! 322: (!ospf_is_v2(p) || (lsa->opts == en->next_lsa_opts)))
! 323: goto drop;
! 324:
! 325: /* Free scheduled LSA */
! 326: mb_free(en->next_lsa_body);
! 327: en->next_lsa_body = NULL;
! 328: en->next_lsa_blen = 0;
! 329: en->next_lsa_opts = 0;
! 330: }
! 331:
! 332: /* Ignore the the new LSA if is the same as the current one */
! 333: if ((en->lsa.age < LSA_MAXAGE) &&
! 334: (lsa_length == en->lsa.length) &&
! 335: !memcmp(lsa_body, en->lsa_body, lsa_blen) &&
! 336: (!ospf_is_v2(p) || (lsa->opts == lsa_get_options(&en->lsa))) &&
! 337: !en->gr_dirty)
! 338: goto drop;
! 339:
! 340: lsa_body = lsab_flush(p);
! 341:
! 342: if (! ospf_do_originate_lsa(p, en, lsa_body, lsa_blen, lsa->opts))
! 343: {
! 344: OSPF_TRACE(D_EVENTS, "Postponing LSA: Type: %04x, Id: %R, Rt: %R",
! 345: en->lsa_type, en->lsa.id, en->lsa.rt);
! 346:
! 347: en->next_lsa_body = lsa_body;
! 348: en->next_lsa_blen = lsa_blen;
! 349: en->next_lsa_opts = lsa->opts;
! 350: }
! 351:
! 352: return en;
! 353:
! 354: drop:
! 355: lsab_reset(p);
! 356: return en;
! 357: }
! 358:
! 359: static void
! 360: ospf_originate_next_lsa(struct ospf_proto *p, struct top_hash_entry *en)
! 361: {
! 362: /* Called by ospf_update_lsadb() to handle scheduled origination */
! 363:
! 364: if (! ospf_do_originate_lsa(p, en, en->next_lsa_body, en->next_lsa_blen, en->next_lsa_opts))
! 365: return;
! 366:
! 367: en->next_lsa_body = NULL;
! 368: en->next_lsa_blen = 0;
! 369: en->next_lsa_opts = 0;
! 370: }
! 371:
! 372: static void
! 373: ospf_refresh_lsa(struct ospf_proto *p, struct top_hash_entry *en)
! 374: {
! 375: /*
! 376: * Called by ospf_update_lsadb() for periodic LSA refresh.
! 377: *
! 378: * We know that lsa.age < LSA_MAXAGE and lsa.rt is our router ID. We can also
! 379: * assume that there is no scheduled LSA, because inst_time is deep in past,
! 380: * therefore ospf_originate_next_lsa() called before would either succeed or
! 381: * switched lsa.age to LSA_MAXAGE.
! 382: */
! 383:
! 384: OSPF_TRACE(D_EVENTS, "Refreshing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
! 385: en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn);
! 386:
! 387: ASSERT(en->next_lsa_body == NULL);
! 388:
! 389: /* Handle wrapping sequence number */
! 390: if (en->lsa.sn == LSA_MAXSEQNO)
! 391: {
! 392: /* Copy LSA body as next LSA to get automatic origination after flush is finished */
! 393: en->next_lsa_blen = en->lsa.length - sizeof(struct ospf_lsa_header);
! 394: en->next_lsa_body = mb_alloc(p->p.pool, en->next_lsa_blen);
! 395: memcpy(en->next_lsa_body, en->lsa_body, en->next_lsa_blen);
! 396: en->next_lsa_opts = ospf_is_v2(p) ? lsa_get_options(&en->lsa) : 0;
! 397:
! 398: en->lsa.age = LSA_MAXAGE;
! 399: ospf_flood_lsa(p, en, NULL);
! 400: return;
! 401: }
! 402:
! 403: en->lsa.sn++;
! 404: en->lsa.age = 0;
! 405: en->init_age = 0;
! 406: en->inst_time = current_time();
! 407: lsa_generate_checksum(&en->lsa, en->lsa_body);
! 408: ospf_flood_lsa(p, en, NULL);
! 409: }
! 410:
! 411: /**
! 412: * ospf_flush_lsa - flush LSA from OSPF domain
! 413: * @p: OSPF protocol instance
! 414: * @en: LSA entry to flush
! 415: *
! 416: * This function flushes @en from the OSPF domain by setting its age to
! 417: * %LSA_MAXAGE and flooding it. That also triggers subsequent events in LSA
! 418: * lifecycle leading to removal of the LSA from the LSA database (e.g. the LSA
! 419: * content is freed when flushing is acknowledged by neighbors). The function
! 420: * does nothing if the LSA is already being flushed. LSA entries are not
! 421: * immediately removed when being flushed, the caller may assume that @en still
! 422: * exists after the call. The function is the opposite of ospf_originate_lsa()
! 423: * and is supposed to do the right thing even in cases of postponed
! 424: * origination.
! 425: */
! 426: void
! 427: ospf_flush_lsa(struct ospf_proto *p, struct top_hash_entry *en)
! 428: {
! 429: en->nf = NULL;
! 430: en->gr_dirty = 0;
! 431:
! 432: if (en->next_lsa_body)
! 433: {
! 434: mb_free(en->next_lsa_body);
! 435: en->next_lsa_body = NULL;
! 436: en->next_lsa_blen = 0;
! 437: en->next_lsa_opts = 0;
! 438: }
! 439:
! 440: if (en->lsa.age == LSA_MAXAGE)
! 441: return;
! 442:
! 443: OSPF_TRACE(D_EVENTS, "Flushing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
! 444: en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn);
! 445:
! 446: en->lsa.age = LSA_MAXAGE;
! 447: ospf_flood_lsa(p, en, NULL);
! 448:
! 449: if (en->mode == LSA_M_BASIC)
! 450: {
! 451: ospf_neigh_lsadb_changed(p, en);
! 452: ospf_schedule_rtcalc(p);
! 453: }
! 454:
! 455: en->mode = LSA_M_BASIC;
! 456: }
! 457:
! 458: static void
! 459: ospf_clear_lsa(struct ospf_proto *p, struct top_hash_entry *en)
! 460: {
! 461: /*
! 462: * Called by ospf_update_lsadb() as part of LSA flushing process.
! 463: * Flushed LSA was acknowledged by neighbors and we can free its content.
! 464: * The log message is for 'remove' - we hide empty LSAs from users.
! 465: */
! 466:
! 467: OSPF_TRACE(D_EVENTS, "Removing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
! 468: en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn);
! 469:
! 470: if (en->lsa.sn == LSA_MAXSEQNO)
! 471: en->lsa.sn = LSA_ZEROSEQNO;
! 472:
! 473: mb_free(en->lsa_body);
! 474: en->lsa_body = NULL;
! 475: }
! 476:
! 477: static void
! 478: ospf_remove_lsa(struct ospf_proto *p, struct top_hash_entry *en)
! 479: {
! 480: /*
! 481: * Called by ospf_update_lsadb() as part of LSA flushing process.
! 482: * Both lsa_body and next_lsa_body are NULL.
! 483: */
! 484:
! 485: s_rem_node(SNODE en);
! 486: ospf_hash_delete(p->gr, en);
! 487: }
! 488:
! 489: /**
! 490: * ospf_update_lsadb - update LSA database
! 491: * @p: OSPF protocol instance
! 492: *
! 493: * This function is periodicaly invoked from ospf_disp(). It does some periodic
! 494: * or postponed processing related to LSA entries. It originates postponed LSAs
! 495: * scheduled by ospf_originate_lsa(), It continues in flushing processes started
! 496: * by ospf_flush_lsa(). It also periodically refreshs locally originated LSAs --
! 497: * when the current instance is older %LSREFRESHTIME, a new instance is originated.
! 498: * Finally, it also ages stored LSAs and flushes ones that reached %LSA_MAXAGE.
! 499: *
! 500: * The RFC 2328 says that a router should periodically check checksums of all
! 501: * stored LSAs to detect hardware problems. This is not implemented.
! 502: */
! 503: void
! 504: ospf_update_lsadb(struct ospf_proto *p)
! 505: {
! 506: struct top_hash_entry *en, *nxt;
! 507: btime now_ = current_time();
! 508: int real_age;
! 509:
! 510: WALK_SLIST_DELSAFE(en, nxt, p->lsal)
! 511: {
! 512: if (en->next_lsa_body)
! 513: ospf_originate_next_lsa(p, en);
! 514:
! 515: real_age = en->init_age + (now_ - en->inst_time) TO_S;
! 516:
! 517: if (en->lsa.age == LSA_MAXAGE)
! 518: {
! 519: if (en->lsa_body && (p->padj == 0) && (en->ret_count == 0))
! 520: ospf_clear_lsa(p, en);
! 521:
! 522: if ((en->lsa_body == NULL) && (en->next_lsa_body == NULL) &&
! 523: ((en->lsa.rt != p->router_id) || (real_age >= LSA_MAXAGE)))
! 524: ospf_remove_lsa(p, en);
! 525:
! 526: continue;
! 527: }
! 528:
! 529: if ((en->lsa.rt == p->router_id) && (real_age >= LSREFRESHTIME))
! 530: {
! 531: ospf_refresh_lsa(p, en);
! 532: continue;
! 533: }
! 534:
! 535: if (real_age >= LSA_MAXAGE)
! 536: {
! 537: ospf_flush_lsa(p, en);
! 538: continue;
! 539: }
! 540:
! 541: en->lsa.age = real_age;
! 542: }
! 543: }
! 544:
! 545: void
! 546: ospf_feed_begin(struct channel *C, int initial UNUSED)
! 547: {
! 548: struct ospf_proto *p = (struct ospf_proto *) C->proto;
! 549: struct top_hash_entry *en;
! 550:
! 551: /* Mark all external LSAs as stale */
! 552: WALK_SLIST(en, p->lsal)
! 553: if (en->mode == LSA_M_EXPORT)
! 554: en->mode = LSA_M_EXPORT_STALE;
! 555: }
! 556:
! 557: void
! 558: ospf_feed_end(struct channel *C)
! 559: {
! 560: struct ospf_proto *p = (struct ospf_proto *) C->proto;
! 561: struct top_hash_entry *en;
! 562:
! 563: /* Flush stale LSAs */
! 564: WALK_SLIST(en, p->lsal)
! 565: if (en->mode == LSA_M_EXPORT_STALE)
! 566: ospf_flush_lsa(p, en);
! 567: }
! 568:
! 569: static u32
! 570: ort_to_lsaid(struct ospf_proto *p, ort *nf)
! 571: {
! 572: /*
! 573: * In OSPFv2, We have to map IP prefixes to u32 in such manner that resulting
! 574: * u32 interpreted as IP address is a member of given prefix. Therefore, /32
! 575: * prefix has to be mapped on itself. All received prefixes have to be mapped
! 576: * on different u32s.
! 577: *
! 578: * We have an assumption that if there is nontrivial (non-/32) network prefix,
! 579: * then there is not /32 prefix for the first and the last IP address of the
! 580: * network (these are usually reserved, therefore it is not an important
! 581: * restriction). The network prefix is mapped to the first or the last IP
! 582: * address in the manner that disallow collisions - we use the IP address that
! 583: * cannot be used by the parent prefix.
! 584: *
! 585: * For example:
! 586: * 192.168.0.0/24 maps to 192.168.0.255
! 587: * 192.168.1.0/24 maps to 192.168.1.0
! 588: * because 192.168.0.0 and 192.168.1.255 might be used by 192.168.0.0/23 .
! 589: *
! 590: * Appendig E of RFC 2328 suggests different algorithm, that tries to maximize
! 591: * both compatibility and subnetting. But as it is not possible to have both
! 592: * reliably and the suggested algorithm was unnecessary complicated and it
! 593: * does crazy things like changing LSA ID for a network because different
! 594: * network appeared, we choose a different way.
! 595: *
! 596: * In OSPFv3, it is simpler. There is not a requirement for membership of the
! 597: * result in the input network, so we just allocate a unique ID from ID map
! 598: * and store it in nf->lsa_id for further reference.
! 599: */
! 600:
! 601: if (ospf_is_v3(p))
! 602: {
! 603: if (!nf->lsa_id)
! 604: nf->lsa_id = idm_alloc(&p->idm);
! 605:
! 606: return nf->lsa_id;
! 607: }
! 608:
! 609: net_addr_ip4 *net = (void *) nf->fn.addr;
! 610: u32 id = ip4_to_u32(net->prefix);
! 611: int pxlen = net->pxlen;
! 612:
! 613: if ((pxlen == 0) || (pxlen == 32))
! 614: return id;
! 615:
! 616: if (id & (1 << (32 - pxlen)))
! 617: return id;
! 618: else
! 619: return id | ~u32_mkmask(pxlen);
! 620: }
! 621:
! 622:
! 623: static void *
! 624: lsab_alloc(struct ospf_proto *p, uint size)
! 625: {
! 626: uint offset = p->lsab_used;
! 627: p->lsab_used += size;
! 628: if (p->lsab_used > p->lsab_size)
! 629: {
! 630: p->lsab_size = MAX(p->lsab_used, 2 * p->lsab_size);
! 631: p->lsab = p->lsab ? mb_realloc(p->lsab, p->lsab_size):
! 632: mb_alloc(p->p.pool, p->lsab_size);
! 633: }
! 634: return ((byte *) p->lsab) + offset;
! 635: }
! 636:
! 637: static inline void *
! 638: lsab_allocz(struct ospf_proto *p, uint size)
! 639: {
! 640: void *r = lsab_alloc(p, size);
! 641: bzero(r, size);
! 642: return r;
! 643: }
! 644:
! 645: static inline void *
! 646: lsab_flush(struct ospf_proto *p)
! 647: {
! 648: void *r = mb_alloc(p->p.pool, p->lsab_used);
! 649: memcpy(r, p->lsab, p->lsab_used);
! 650: p->lsab_used = 0;
! 651: return r;
! 652: }
! 653:
! 654: static inline void
! 655: lsab_reset(struct ospf_proto *p)
! 656: {
! 657: p->lsab_used = 0;
! 658: }
! 659:
! 660: static inline void *
! 661: lsab_offset(struct ospf_proto *p, uint offset)
! 662: {
! 663: return ((byte *) p->lsab) + offset;
! 664: }
! 665:
! 666: static inline void * UNUSED
! 667: lsab_end(struct ospf_proto *p)
! 668: {
! 669: return ((byte *) p->lsab) + p->lsab_used;
! 670: }
! 671:
! 672:
! 673: /*
! 674: * Router-LSA handling
! 675: * Type = LSA_T_RT
! 676: */
! 677:
! 678: static int
! 679: configured_stubnet(struct ospf_area *oa, struct ifa *a)
! 680: {
! 681: /* Does not work for IA_PEER addresses, but it is not called on these */
! 682: struct ospf_stubnet_config *sn;
! 683: WALK_LIST(sn, oa->ac->stubnet_list)
! 684: {
! 685: if (sn->summary)
! 686: {
! 687: if (net_in_netX(&a->prefix, &sn->prefix))
! 688: return 1;
! 689: }
! 690: else
! 691: {
! 692: if (net_equal(&a->prefix, &sn->prefix))
! 693: return 1;
! 694: }
! 695: }
! 696:
! 697: return 0;
! 698: }
! 699:
! 700: static int
! 701: bcast_net_active(struct ospf_iface *ifa)
! 702: {
! 703: struct ospf_neighbor *neigh;
! 704:
! 705: if (ifa->state == OSPF_IS_WAITING)
! 706: return 0;
! 707:
! 708: WALK_LIST(neigh, ifa->neigh_list)
! 709: {
! 710: if (neigh->state == NEIGHBOR_FULL)
! 711: {
! 712: if (neigh->rid == ifa->drid)
! 713: return 1;
! 714:
! 715: if (ifa->state == OSPF_IS_DR)
! 716: return 1;
! 717: }
! 718: }
! 719:
! 720: return 0;
! 721: }
! 722:
! 723: static inline u32
! 724: get_rt_options(struct ospf_proto *p, struct ospf_area *oa, int bitv)
! 725: {
! 726: u32 opts = 0;
! 727:
! 728: if (p->areano > 1)
! 729: opts |= OPT_RT_B;
! 730:
! 731: if ((p->areano > 1) && oa_is_nssa(oa) && oa->ac->translator)
! 732: opts |= OPT_RT_NT;
! 733:
! 734: if (p->asbr && !oa_is_stub(oa))
! 735: opts |= OPT_RT_E;
! 736:
! 737: if (bitv)
! 738: opts |= OPT_RT_V;
! 739:
! 740: return opts;
! 741: }
! 742:
! 743: static inline void
! 744: add_rt2_lsa_link(struct ospf_proto *p, u8 type, u32 id, u32 data, u16 metric)
! 745: {
! 746: struct ospf_lsa_rt2_link *ln = lsab_alloc(p, sizeof(struct ospf_lsa_rt2_link));
! 747: ln->type = type;
! 748: ln->id = id;
! 749: ln->data = data;
! 750: ln->metric = metric;
! 751: ln->no_tos = 0;
! 752: }
! 753:
! 754: static void
! 755: prepare_rt2_lsa_body(struct ospf_proto *p, struct ospf_area *oa)
! 756: {
! 757: struct ospf_iface *ifa;
! 758: int i = 0, bitv = 0;
! 759: struct ospf_neighbor *neigh;
! 760:
! 761: ASSERT(p->lsab_used == 0);
! 762: lsab_allocz(p, sizeof(struct ospf_lsa_rt));
! 763: /* ospf_lsa_rt header will be filled later */
! 764:
! 765: WALK_LIST(ifa, p->iface_list)
! 766: {
! 767: int net_lsa = 0;
! 768: u32 link_cost = p->stub_router ? 0xffff : ifa->cost;
! 769:
! 770: if ((ifa->type == OSPF_IT_VLINK) && (ifa->voa == oa) &&
! 771: (!EMPTY_LIST(ifa->neigh_list)))
! 772: {
! 773: neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
! 774: if ((neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
! 775: bitv = 1;
! 776: }
! 777:
! 778: if ((ifa->oa != oa) || (ifa->state == OSPF_IS_DOWN))
! 779: continue;
! 780:
! 781: ifa->rt_pos_beg = i;
! 782:
! 783: /* RFC 2328 - 12.4.1.1-4 */
! 784: switch (ifa->type)
! 785: {
! 786: case OSPF_IT_PTP:
! 787: case OSPF_IT_PTMP:
! 788: WALK_LIST(neigh, ifa->neigh_list)
! 789: if (neigh->state == NEIGHBOR_FULL)
! 790: {
! 791: /*
! 792: * ln->data should be ifa->iface_id in case of no/ptp
! 793: * address (ifa->addr->flags & IA_PEER) on PTP link (see
! 794: * RFC 2328 12.4.1.1.), but the iface ID value has no use,
! 795: * while using IP address even in this case is here for
! 796: * compatibility with some broken implementations that use
! 797: * this address as a next-hop.
! 798: */
! 799: add_rt2_lsa_link(p, LSART_PTP, neigh->rid, ipa_to_u32(ifa->addr->ip), link_cost);
! 800: i++;
! 801: }
! 802: break;
! 803:
! 804: case OSPF_IT_BCAST:
! 805: case OSPF_IT_NBMA:
! 806: if (bcast_net_active(ifa))
! 807: {
! 808: add_rt2_lsa_link(p, LSART_NET, ipa_to_u32(ifa->drip), ipa_to_u32(ifa->addr->ip), link_cost);
! 809: i++;
! 810: net_lsa = 1;
! 811: }
! 812: break;
! 813:
! 814: case OSPF_IT_VLINK:
! 815: neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
! 816: if ((!EMPTY_LIST(ifa->neigh_list)) && (neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
! 817: add_rt2_lsa_link(p, LSART_VLNK, neigh->rid, ipa_to_u32(ifa->addr->ip), link_cost), i++;
! 818: break;
! 819:
! 820: default:
! 821: log(L_BUG "OSPF: Unknown interface type");
! 822: break;
! 823: }
! 824:
! 825: ifa->rt_pos_end = i;
! 826:
! 827: /* Now we will originate stub area if there is no primary */
! 828: if (net_lsa ||
! 829: (ifa->type == OSPF_IT_VLINK) ||
! 830: ((ifa->addr->flags & IA_PEER) && ! ifa->cf->stub) ||
! 831: configured_stubnet(oa, ifa->addr))
! 832: continue;
! 833:
! 834: /* Host or network stub entry */
! 835: if ((ifa->addr->flags & IA_HOST) ||
! 836: (ifa->state == OSPF_IS_LOOP) ||
! 837: (ifa->type == OSPF_IT_PTMP))
! 838: add_rt2_lsa_link(p, LSART_STUB, ipa_to_u32(ifa->addr->ip), 0xffffffff, 0);
! 839: else
! 840: add_rt2_lsa_link(p, LSART_STUB, ip4_to_u32(net4_prefix(&ifa->addr->prefix)),
! 841: u32_mkmask(net4_pxlen(&ifa->addr->prefix)), ifa->cost);
! 842: i++;
! 843:
! 844: ifa->rt_pos_end = i;
! 845: }
! 846:
! 847: struct ospf_stubnet_config *sn;
! 848: WALK_LIST(sn, oa->ac->stubnet_list)
! 849: if (!sn->hidden)
! 850: add_rt2_lsa_link(p, LSART_STUB, ip4_to_u32(net4_prefix(&sn->prefix)),
! 851: u32_mkmask(net4_pxlen(&sn->prefix)), sn->cost), i++;
! 852:
! 853: struct ospf_lsa_rt *rt = p->lsab;
! 854: /* Store number of links in lower half of options */
! 855: rt->options = get_rt_options(p, oa, bitv) | (u16) i;
! 856: }
! 857:
! 858: static inline void
! 859: add_rt3_lsa_link(struct ospf_proto *p, u8 type, struct ospf_iface *ifa, u32 nif, u32 id)
! 860: {
! 861: struct ospf_lsa_rt3_link *ln = lsab_alloc(p, sizeof(struct ospf_lsa_rt3_link));
! 862: ln->type = type;
! 863: ln->padding = 0;
! 864: ln->metric = ifa->cost;
! 865: ln->lif = ifa->iface_id;
! 866: ln->nif = nif;
! 867: ln->id = id;
! 868: }
! 869:
! 870: static void
! 871: prepare_rt3_lsa_body(struct ospf_proto *p, struct ospf_area *oa)
! 872: {
! 873: struct ospf_iface *ifa;
! 874: struct ospf_neighbor *neigh;
! 875: int bitv = 0;
! 876: int i = 0;
! 877:
! 878: ASSERT(p->lsab_used == 0);
! 879: lsab_allocz(p, sizeof(struct ospf_lsa_rt));
! 880: /* ospf_lsa_rt header will be filled later */
! 881:
! 882: WALK_LIST(ifa, p->iface_list)
! 883: {
! 884: if ((ifa->type == OSPF_IT_VLINK) && (ifa->voa == oa) &&
! 885: (!EMPTY_LIST(ifa->neigh_list)))
! 886: {
! 887: neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
! 888: if ((neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
! 889: bitv = 1;
! 890: }
! 891:
! 892: if ((ifa->oa != oa) || (ifa->state == OSPF_IS_DOWN))
! 893: continue;
! 894:
! 895: ifa->rt_pos_beg = i;
! 896:
! 897: /* RFC 5340 - 4.4.3.2 */
! 898: switch (ifa->type)
! 899: {
! 900: case OSPF_IT_PTP:
! 901: case OSPF_IT_PTMP:
! 902: WALK_LIST(neigh, ifa->neigh_list)
! 903: if (neigh->state == NEIGHBOR_FULL)
! 904: add_rt3_lsa_link(p, LSART_PTP, ifa, neigh->iface_id, neigh->rid), i++;
! 905: break;
! 906:
! 907: case OSPF_IT_BCAST:
! 908: case OSPF_IT_NBMA:
! 909: if (bcast_net_active(ifa))
! 910: add_rt3_lsa_link(p, LSART_NET, ifa, ifa->dr_iface_id, ifa->drid), i++;
! 911: break;
! 912:
! 913: case OSPF_IT_VLINK:
! 914: neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
! 915: if ((!EMPTY_LIST(ifa->neigh_list)) && (neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
! 916: add_rt3_lsa_link(p, LSART_VLNK, ifa, neigh->iface_id, neigh->rid), i++;
! 917: break;
! 918:
! 919: default:
! 920: log(L_BUG "OSPF: Unknown interface type");
! 921: break;
! 922: }
! 923:
! 924: ifa->rt_pos_end = i;
! 925: }
! 926:
! 927: struct ospf_lsa_rt *rt = p->lsab;
! 928: rt->options = get_rt_options(p, oa, bitv) | (oa->options & LSA_OPTIONS_MASK);
! 929: }
! 930:
! 931: static void
! 932: ospf_originate_rt_lsa(struct ospf_proto *p, struct ospf_area *oa)
! 933: {
! 934: struct ospf_new_lsa lsa = {
! 935: .type = LSA_T_RT,
! 936: .dom = oa->areaid,
! 937: .id = ospf_is_v2(p) ? p->router_id : 0,
! 938: .opts = oa->options
! 939: };
! 940:
! 941: OSPF_TRACE(D_EVENTS, "Updating router state for area %R", oa->areaid);
! 942:
! 943: if (ospf_is_v2(p))
! 944: prepare_rt2_lsa_body(p, oa);
! 945: else
! 946: prepare_rt3_lsa_body(p, oa);
! 947:
! 948: oa->rt = ospf_originate_lsa(p, &lsa);
! 949: }
! 950:
! 951:
! 952: /*
! 953: * Net-LSA handling
! 954: * Type = LSA_T_NET
! 955: */
! 956:
! 957: static void
! 958: prepare_net2_lsa_body(struct ospf_proto *p, struct ospf_iface *ifa)
! 959: {
! 960: struct ospf_lsa_net *net;
! 961: struct ospf_neighbor *n;
! 962: int nodes = ifa->fadj + 1;
! 963: u16 i = 1;
! 964:
! 965: ASSERT(p->lsab_used == 0);
! 966: net = lsab_alloc(p, sizeof(struct ospf_lsa_net) + 4 * nodes);
! 967:
! 968: net->optx = u32_mkmask(ifa->addr->prefix.pxlen);
! 969: net->routers[0] = p->router_id;
! 970:
! 971: WALK_LIST(n, ifa->neigh_list)
! 972: {
! 973: if (n->state == NEIGHBOR_FULL)
! 974: {
! 975: net->routers[i] = n->rid;
! 976: i++;
! 977: }
! 978: }
! 979: ASSERT(i == nodes);
! 980: }
! 981:
! 982: static void
! 983: prepare_net3_lsa_body(struct ospf_proto *p, struct ospf_iface *ifa)
! 984: {
! 985: struct ospf_lsa_net *net;
! 986: int nodes = ifa->fadj + 1;
! 987: u32 options = 0;
! 988: u16 i = 1;
! 989:
! 990: ASSERT(p->lsab_used == 0);
! 991: net = lsab_alloc(p, sizeof(struct ospf_lsa_net) + 4 * nodes);
! 992:
! 993: net->routers[0] = p->router_id;
! 994:
! 995: struct ospf_neighbor *n;
! 996: WALK_LIST(n, ifa->neigh_list)
! 997: {
! 998: if (n->state == NEIGHBOR_FULL)
! 999: {
! 1000: /* In OSPFv3, we would like to merge options from Link LSAs of added neighbors */
! 1001:
! 1002: struct top_hash_entry *en =
! 1003: ospf_hash_find(p->gr, ifa->iface_id, n->iface_id, n->rid, LSA_T_LINK);
! 1004:
! 1005: if (en)
! 1006: options |= ((struct ospf_lsa_link *) en->lsa_body)->options;
! 1007:
! 1008: net->routers[i] = n->rid;
! 1009: i++;
! 1010: }
! 1011: }
! 1012: ASSERT(i == nodes);
! 1013:
! 1014: net->optx = options & LSA_OPTIONS_MASK;
! 1015: }
! 1016:
! 1017: static void
! 1018: ospf_originate_net_lsa(struct ospf_proto *p, struct ospf_iface *ifa)
! 1019: {
! 1020: struct ospf_new_lsa lsa = {
! 1021: .type = LSA_T_NET,
! 1022: .dom = ifa->oa->areaid,
! 1023: .id = ospf_is_v2(p) ? ipa_to_u32(ifa->addr->ip) : ifa->iface_id,
! 1024: .opts = ifa->oa->options,
! 1025: .ifa = ifa
! 1026: };
! 1027:
! 1028: OSPF_TRACE(D_EVENTS, "Updating network state for %s (Id: %R)", ifa->ifname, lsa.id);
! 1029:
! 1030: if (ospf_is_v2(p))
! 1031: prepare_net2_lsa_body(p, ifa);
! 1032: else
! 1033: prepare_net3_lsa_body(p, ifa);
! 1034:
! 1035: ifa->net_lsa = ospf_originate_lsa(p, &lsa);
! 1036: }
! 1037:
! 1038:
! 1039: /*
! 1040: * (Net|Rt)-summary-LSA handling
! 1041: * (a.k.a. Inter-Area-(Prefix|Router)-LSA)
! 1042: * Type = LSA_T_SUM_NET, LSA_T_SUM_RT
! 1043: */
! 1044:
! 1045: static inline void
! 1046: prepare_sum2_lsa_body(struct ospf_proto *p, uint pxlen, u32 metric)
! 1047: {
! 1048: struct ospf_lsa_sum2 *sum;
! 1049:
! 1050: sum = lsab_allocz(p, sizeof(struct ospf_lsa_sum2));
! 1051: sum->netmask = u32_mkmask(pxlen);
! 1052: sum->metric = metric;
! 1053: }
! 1054:
! 1055: static inline void
! 1056: prepare_sum3_net_lsa_body(struct ospf_proto *p, ort *nf, u32 metric)
! 1057: {
! 1058: struct ospf_lsa_sum3_net *sum;
! 1059:
! 1060: sum = lsab_allocz(p, sizeof(struct ospf_lsa_sum3_net) +
! 1061: IPV6_PREFIX_SPACE(nf->fn.addr->pxlen));
! 1062: sum->metric = metric;
! 1063: ospf3_put_prefix(sum->prefix, nf->fn.addr, 0, 0);
! 1064: }
! 1065:
! 1066: static inline void
! 1067: prepare_sum3_rt_lsa_body(struct ospf_proto *p, u32 drid, u32 metric, u32 options)
! 1068: {
! 1069: struct ospf_lsa_sum3_rt *sum;
! 1070:
! 1071: sum = lsab_allocz(p, sizeof(struct ospf_lsa_sum3_rt));
! 1072: sum->options = options;
! 1073: sum->metric = metric;
! 1074: sum->drid = drid;
! 1075: }
! 1076:
! 1077: void
! 1078: ospf_originate_sum_net_lsa(struct ospf_proto *p, struct ospf_area *oa, ort *nf, int metric)
! 1079: {
! 1080: struct ospf_new_lsa lsa = {
! 1081: .type = LSA_T_SUM_NET,
! 1082: .mode = LSA_M_RTCALC,
! 1083: .dom = oa->areaid,
! 1084: .id = ort_to_lsaid(p, nf),
! 1085: .opts = oa->options,
! 1086: .nf = nf
! 1087: };
! 1088:
! 1089: if (ospf_is_v2(p))
! 1090: prepare_sum2_lsa_body(p, nf->fn.addr->pxlen, metric);
! 1091: else
! 1092: prepare_sum3_net_lsa_body(p, nf, metric);
! 1093:
! 1094: ospf_originate_lsa(p, &lsa);
! 1095: }
! 1096:
! 1097: void
! 1098: ospf_originate_sum_rt_lsa(struct ospf_proto *p, struct ospf_area *oa, u32 drid, int metric, u32 options)
! 1099: {
! 1100: struct ospf_new_lsa lsa = {
! 1101: .type = LSA_T_SUM_RT,
! 1102: .mode = LSA_M_RTCALC,
! 1103: .dom = oa->areaid,
! 1104: .id = drid, /* Router ID of ASBR, irrelevant for OSPFv3 */
! 1105: .opts = oa->options
! 1106: };
! 1107:
! 1108: if (ospf_is_v2(p))
! 1109: prepare_sum2_lsa_body(p, 0, metric);
! 1110: else
! 1111: prepare_sum3_rt_lsa_body(p, drid, metric, options & LSA_OPTIONS_MASK);
! 1112:
! 1113: ospf_originate_lsa(p, &lsa);
! 1114: }
! 1115:
! 1116:
! 1117: /*
! 1118: * AS-external-LSA and NSSA-LSA handling
! 1119: * Type = LSA_T_EXT, LSA_T_NSSA
! 1120: */
! 1121:
! 1122: static inline void
! 1123: prepare_ext2_lsa_body(struct ospf_proto *p, uint pxlen,
! 1124: u32 metric, u32 ebit, ip_addr fwaddr, u32 tag)
! 1125: {
! 1126: struct ospf_lsa_ext2 *ext;
! 1127:
! 1128: ext = lsab_allocz(p, sizeof(struct ospf_lsa_ext2));
! 1129: ext->metric = metric & LSA_METRIC_MASK;
! 1130: ext->netmask = u32_mkmask(pxlen);
! 1131: ext->fwaddr = ipa_to_u32(fwaddr);
! 1132: ext->tag = tag;
! 1133:
! 1134: if (ebit)
! 1135: ext->metric |= LSA_EXT2_EBIT;
! 1136: }
! 1137:
! 1138: static inline void
! 1139: prepare_ext3_lsa_body(struct ospf_proto *p, ort *nf,
! 1140: u32 metric, u32 ebit, ip_addr fwaddr, u32 tag, int pbit, int dn)
! 1141: {
! 1142: struct ospf_lsa_ext3 *ext;
! 1143: int bsize = sizeof(struct ospf_lsa_ext3)
! 1144: + IPV6_PREFIX_SPACE(nf->fn.addr->pxlen)
! 1145: + (ipa_nonzero(fwaddr) ? 16 : 0)
! 1146: + (tag ? 4 : 0);
! 1147:
! 1148: ext = lsab_allocz(p, bsize);
! 1149: ext->metric = metric & LSA_METRIC_MASK;
! 1150: u32 *buf = ext->rest;
! 1151:
! 1152: uint flags = (pbit ? OPT_PX_P : 0) | (dn ? OPT_PX_DN : 0);
! 1153: buf = ospf3_put_prefix(buf, nf->fn.addr, flags, 0);
! 1154:
! 1155: if (ebit)
! 1156: ext->metric |= LSA_EXT3_EBIT;
! 1157:
! 1158: if (ipa_nonzero(fwaddr))
! 1159: {
! 1160: ext->metric |= LSA_EXT3_FBIT;
! 1161: buf = ospf3_put_addr(buf, fwaddr);
! 1162: }
! 1163:
! 1164: if (tag)
! 1165: {
! 1166: ext->metric |= LSA_EXT3_TBIT;
! 1167: *buf++ = tag;
! 1168: }
! 1169: }
! 1170:
! 1171: /**
! 1172: * originate_ext_lsa - new route received from nest and filters
! 1173: * @p: OSPF protocol instance
! 1174: * @oa: ospf_area for which LSA is originated
! 1175: * @nf: network prefix and mask
! 1176: * @mode: the mode of the LSA (LSA_M_EXPORT or LSA_M_RTCALC)
! 1177: * @metric: the metric of a route
! 1178: * @ebit: E-bit for route metric (bool)
! 1179: * @fwaddr: the forwarding address
! 1180: * @tag: the route tag
! 1181: * @pbit: P-bit for NSSA LSAs (bool), ignored for external LSAs
! 1182: *
! 1183: * If I receive a message that new route is installed, I try to originate an
! 1184: * external LSA. If @oa is an NSSA area, NSSA-LSA is originated instead.
! 1185: * @oa should not be a stub area. @src does not specify whether the LSA
! 1186: * is external or NSSA, but it specifies the source of origination -
! 1187: * the export from ospf_rt_notify(), or the NSSA-EXT translation.
! 1188: */
! 1189: void
! 1190: ospf_originate_ext_lsa(struct ospf_proto *p, struct ospf_area *oa, ort *nf, u8 mode,
! 1191: u32 metric, u32 ebit, ip_addr fwaddr, u32 tag, int pbit, int dn)
! 1192: {
! 1193: struct ospf_new_lsa lsa = {
! 1194: .type = oa ? LSA_T_NSSA : LSA_T_EXT,
! 1195: .mode = mode, /* LSA_M_EXPORT or LSA_M_RTCALC */
! 1196: .dom = oa ? oa->areaid : 0,
! 1197: .id = ort_to_lsaid(p, nf),
! 1198: .opts = (oa ? (pbit ? OPT_P : 0) : OPT_E) | (dn ? OPT_DN : 0),
! 1199: .nf = nf
! 1200: };
! 1201:
! 1202: if (ospf_is_v2(p))
! 1203: prepare_ext2_lsa_body(p, nf->fn.addr->pxlen, metric, ebit, fwaddr, tag);
! 1204: else
! 1205: prepare_ext3_lsa_body(p, nf, metric, ebit, fwaddr, tag, oa && pbit, dn);
! 1206:
! 1207: ospf_originate_lsa(p, &lsa);
! 1208: }
! 1209:
! 1210: static struct top_hash_entry *
! 1211: ospf_hash_find_(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type);
! 1212:
! 1213: static void
! 1214: ospf_flush_ext_lsa(struct ospf_proto *p, struct ospf_area *oa, ort *nf)
! 1215: {
! 1216: struct top_hash_entry *en;
! 1217:
! 1218: u32 type = oa ? LSA_T_NSSA : LSA_T_EXT;
! 1219: u32 dom = oa ? oa->areaid : 0;
! 1220: u32 id = ort_to_lsaid(p, nf);
! 1221:
! 1222: en = ospf_hash_find_(p->gr, dom, id, p->router_id, type);
! 1223:
! 1224: if (!en || (en->nf != nf))
! 1225: return;
! 1226:
! 1227: ospf_flush_lsa(p, en);
! 1228: }
! 1229:
! 1230: static inline int
! 1231: use_gw_for_fwaddr(struct ospf_proto *p, ip_addr gw, struct iface *iface)
! 1232: {
! 1233: struct ospf_iface *ifa;
! 1234:
! 1235: if (ipa_zero(gw) || ipa_is_link_local(gw))
! 1236: return 0;
! 1237:
! 1238: WALK_LIST(ifa, p->iface_list)
! 1239: if ((ifa->iface == iface) &&
! 1240: (!ospf_is_v2(p) || ipa_in_netX(gw, &ifa->addr->prefix)))
! 1241: return 1;
! 1242:
! 1243: return 0;
! 1244: }
! 1245:
! 1246: static inline ip_addr
! 1247: find_surrogate_fwaddr(struct ospf_proto *p, struct ospf_area *oa)
! 1248: {
! 1249: struct ospf_iface *ifa;
! 1250: struct ifa *a, *cur_addr = NULL;
! 1251: int np, cur_np = 0;
! 1252:
! 1253: /* RFC 3101 2.3 - surrogate forwarding address selection */
! 1254:
! 1255: WALK_LIST(ifa, p->iface_list)
! 1256: {
! 1257: if ((ifa->oa != oa) ||
! 1258: (ifa->type == OSPF_IT_VLINK))
! 1259: continue;
! 1260:
! 1261: if (ospf_is_v2(p))
! 1262: {
! 1263: a = ifa->addr;
! 1264: if (a->flags & IA_PEER)
! 1265: continue;
! 1266:
! 1267: np = (a->flags & IA_HOST) ? 3 : (ifa->stub ? 2 : 1);
! 1268: if (np > cur_np)
! 1269: {
! 1270: cur_addr = a;
! 1271: cur_np = np;
! 1272: }
! 1273: }
! 1274: else /* OSPFv3 */
! 1275: {
! 1276: WALK_LIST(a, ifa->iface->addrs)
! 1277: {
! 1278: if ((a->prefix.type != ospf_get_af(p)) ||
! 1279: (a->flags & IA_SECONDARY) ||
! 1280: (a->flags & IA_PEER) ||
! 1281: (a->scope <= SCOPE_LINK))
! 1282: continue;
! 1283:
! 1284: np = (a->flags & IA_HOST) ? 3 : (ifa->stub ? 2 : 1);
! 1285: if (np > cur_np)
! 1286: {
! 1287: cur_addr = a;
! 1288: cur_np = np;
! 1289: }
! 1290: }
! 1291: }
! 1292: }
! 1293:
! 1294: return cur_addr ? cur_addr->ip : IPA_NONE;
! 1295: }
! 1296:
! 1297: void
! 1298: ospf_rt_notify(struct proto *P, struct channel *ch UNUSED, net *n, rte *new, rte *old UNUSED)
! 1299: {
! 1300: struct ospf_proto *p = (struct ospf_proto *) P;
! 1301: struct ospf_area *oa = NULL; /* non-NULL for NSSA-LSA */
! 1302: ort *nf;
! 1303:
! 1304: /*
! 1305: * There are several posibilities:
! 1306: * 1) router in regular area - originate external LSA with global scope
! 1307: * 2) router in NSSA area - originate area-specific NSSA-LSA
! 1308: * 3) router in stub area - cannot export routes
! 1309: * 4) area border router - same as (1), it is attached to backbone
! 1310: */
! 1311:
! 1312: if ((p->areano == 1) && oa_is_nssa(HEAD(p->area_list)))
! 1313: oa = HEAD(p->area_list);
! 1314:
! 1315: if (!new)
! 1316: {
! 1317: nf = fib_find(&p->rtf, n->n.addr);
! 1318:
! 1319: if (!nf || !nf->external_rte)
! 1320: return;
! 1321:
! 1322: ospf_flush_ext_lsa(p, oa, nf);
! 1323: nf->external_rte = 0;
! 1324:
! 1325: /* Old external route might blocked some NSSA translation */
! 1326: if ((p->areano > 1) && rt_is_nssa(nf) && nf->n.oa->translate)
! 1327: ospf_schedule_rtcalc(p);
! 1328:
! 1329: return;
! 1330: }
! 1331:
! 1332: ASSERT(p->asbr);
! 1333:
! 1334: /* Get route attributes */
! 1335: rta *a = new->attrs;
! 1336: eattr *m1a = ea_find(a->eattrs, EA_OSPF_METRIC1);
! 1337: eattr *m2a = ea_find(a->eattrs, EA_OSPF_METRIC2);
! 1338: uint m1 = m1a ? m1a->u.data : 0;
! 1339: uint m2 = m2a ? m2a->u.data : 10000;
! 1340:
! 1341: if (m1 > LSINFINITY)
! 1342: {
! 1343: log(L_WARN "%s: Invalid ospf_metric1 value %u for route %N",
! 1344: p->p.name, m1, n->n.addr);
! 1345: m1 = LSINFINITY;
! 1346: }
! 1347:
! 1348: if (m2 > LSINFINITY)
! 1349: {
! 1350: log(L_WARN "%s: Invalid ospf_metric2 value %u for route %N",
! 1351: p->p.name, m2, n->n.addr);
! 1352: m2 = LSINFINITY;
! 1353: }
! 1354:
! 1355: /* Ensure monotonicity of metric if both m1 and m2 are used */
! 1356: if ((m1 > 0) && (m2 < LSINFINITY))
! 1357: m2++;
! 1358:
! 1359: uint ebit = m2a || !m1a;
! 1360: uint metric = ebit ? m2 : m1;
! 1361: uint tag = ea_get_int(a->eattrs, EA_OSPF_TAG, 0);
! 1362:
! 1363: ip_addr fwd = IPA_NONE;
! 1364: if ((a->dest == RTD_UNICAST) && use_gw_for_fwaddr(p, a->nh.gw, a->nh.iface))
! 1365: fwd = a->nh.gw;
! 1366:
! 1367: /* NSSA-LSA with P-bit set must have non-zero forwarding address */
! 1368: if (oa && ipa_zero(fwd))
! 1369: {
! 1370: fwd = find_surrogate_fwaddr(p, oa);
! 1371:
! 1372: if (ipa_zero(fwd))
! 1373: {
! 1374: log(L_ERR "%s: Cannot find forwarding address for NSSA-LSA %N",
! 1375: p->p.name, n->n.addr);
! 1376: return;
! 1377: }
! 1378: }
! 1379:
! 1380: nf = fib_get(&p->rtf, n->n.addr);
! 1381: ospf_originate_ext_lsa(p, oa, nf, LSA_M_EXPORT, metric, ebit, fwd, tag, 1, p->vpn_pe);
! 1382: nf->external_rte = 1;
! 1383: }
! 1384:
! 1385:
! 1386: /*
! 1387: * Link-LSA handling (assume OSPFv3)
! 1388: * Type = LSA_T_LINK
! 1389: */
! 1390:
! 1391: static inline void
! 1392: lsab_put_prefix(struct ospf_proto *p, net_addr *n, u32 cost)
! 1393: {
! 1394: void *buf = lsab_alloc(p, IPV6_PREFIX_SPACE(net_pxlen(n)));
! 1395: uint max = (n->type == NET_IP4) ? IP4_MAX_PREFIX_LENGTH : IP6_MAX_PREFIX_LENGTH;
! 1396: u8 flags = (net_pxlen(n) < max) ? 0 : OPT_PX_LA;
! 1397: ospf3_put_prefix(buf, n, flags, cost);
! 1398: }
! 1399:
! 1400: static void
! 1401: prepare_link_lsa_body(struct ospf_proto *p, struct ospf_iface *ifa)
! 1402: {
! 1403: ip_addr nh = ospf_is_ip4(p) ? IPA_NONE : ifa->addr->ip;
! 1404: int i = 0;
! 1405:
! 1406: /* Preallocating space for header */
! 1407: ASSERT(p->lsab_used == 0);
! 1408: lsab_allocz(p, sizeof(struct ospf_lsa_link));
! 1409:
! 1410: struct ifa *a;
! 1411: WALK_LIST(a, ifa->iface->addrs)
! 1412: {
! 1413: if ((a->prefix.type != ospf_get_af(p)) ||
! 1414: (a->flags & IA_SECONDARY) ||
! 1415: (a->scope <= SCOPE_LINK))
! 1416: continue;
! 1417:
! 1418: if (ospf_is_ip4(p) && ipa_zero(nh))
! 1419: nh = a->ip;
! 1420:
! 1421: lsab_put_prefix(p, &a->prefix, 0);
! 1422: i++;
! 1423: }
! 1424:
! 1425: /* Filling the preallocated header */
! 1426: struct ospf_lsa_link *ll = p->lsab;
! 1427: ll->options = ifa->oa->options | (ifa->priority << 24);
! 1428: ll->lladdr = ospf_is_ip4(p) ? ospf3_4to6(ipa_to_ip4(nh)) : ipa_to_ip6(nh);
! 1429: ll->pxcount = i;
! 1430:
! 1431: if (ipa_zero(nh))
! 1432: log(L_ERR "%s: Cannot find next hop address for %s", p->p.name, ifa->ifname);
! 1433: }
! 1434:
! 1435: static void
! 1436: ospf_originate_link_lsa(struct ospf_proto *p, struct ospf_iface *ifa)
! 1437: {
! 1438: if (ospf_is_v2(p))
! 1439: return;
! 1440:
! 1441: struct ospf_new_lsa lsa = {
! 1442: .type = LSA_T_LINK,
! 1443: .dom = ifa->iface_id,
! 1444: .id = ifa->iface_id,
! 1445: .ifa = ifa
! 1446: };
! 1447:
! 1448: OSPF_TRACE(D_EVENTS, "Updating link state for %s (Id: %R)", ifa->ifname, lsa.id);
! 1449:
! 1450: prepare_link_lsa_body(p, ifa);
! 1451:
! 1452: ifa->link_lsa = ospf_originate_lsa(p, &lsa);
! 1453: }
! 1454:
! 1455:
! 1456: /*
! 1457: * Prefix-Rt-LSA handling (assume OSPFv3)
! 1458: * Type = LSA_T_PREFIX, referred type = LSA_T_RT
! 1459: */
! 1460:
! 1461: static void
! 1462: prepare_prefix_rt_lsa_body(struct ospf_proto *p, struct ospf_area *oa)
! 1463: {
! 1464: struct ospf_config *cf = (struct ospf_config *) (p->p.cf);
! 1465: struct ospf_iface *ifa;
! 1466: struct ospf_lsa_prefix *lp;
! 1467: uint max = ospf_is_ip4(p) ? IP4_MAX_PREFIX_LENGTH : IP6_MAX_PREFIX_LENGTH;
! 1468: int host_addr = 0;
! 1469: int net_lsa;
! 1470: int i = 0;
! 1471:
! 1472: ASSERT(p->lsab_used == 0);
! 1473: lp = lsab_allocz(p, sizeof(struct ospf_lsa_prefix));
! 1474: lp->ref_type = LSA_T_RT;
! 1475: lp->ref_id = 0;
! 1476: lp->ref_rt = p->router_id;
! 1477: lp = NULL; /* buffer might be reallocated later */
! 1478:
! 1479: WALK_LIST(ifa, p->iface_list)
! 1480: {
! 1481: if ((ifa->oa != oa) || (ifa->type == OSPF_IT_VLINK) || (ifa->state == OSPF_IS_DOWN))
! 1482: continue;
! 1483:
! 1484: ifa->px_pos_beg = i;
! 1485:
! 1486: if ((ifa->type == OSPF_IT_BCAST) ||
! 1487: (ifa->type == OSPF_IT_NBMA))
! 1488: net_lsa = bcast_net_active(ifa);
! 1489: else
! 1490: net_lsa = 0;
! 1491:
! 1492: struct ifa *a;
! 1493: WALK_LIST(a, ifa->iface->addrs)
! 1494: {
! 1495: if ((a->prefix.type != ospf_get_af(p)) ||
! 1496: (a->flags & IA_SECONDARY) ||
! 1497: (a->flags & IA_PEER) ||
! 1498: (a->scope <= SCOPE_LINK))
! 1499: continue;
! 1500:
! 1501: if (((a->prefix.pxlen < max) && net_lsa) ||
! 1502: configured_stubnet(oa, a))
! 1503: continue;
! 1504:
! 1505: if ((a->flags & IA_HOST) ||
! 1506: (ifa->state == OSPF_IS_LOOP) ||
! 1507: (ifa->type == OSPF_IT_PTMP))
! 1508: {
! 1509: net_addr net;
! 1510: if (a->prefix.type == NET_IP4)
! 1511: net_fill_ip4(&net, ipa_to_ip4(a->ip), IP4_MAX_PREFIX_LENGTH);
! 1512: else
! 1513: net_fill_ip6(&net, ipa_to_ip6(a->ip), IP6_MAX_PREFIX_LENGTH);
! 1514:
! 1515: lsab_put_prefix(p, &net, 0);
! 1516: host_addr = 1;
! 1517: }
! 1518: else
! 1519: lsab_put_prefix(p, &a->prefix, ifa->cost);
! 1520: i++;
! 1521: }
! 1522:
! 1523: ifa->px_pos_end = i;
! 1524: }
! 1525:
! 1526: struct ospf_stubnet_config *sn;
! 1527: WALK_LIST(sn, oa->ac->stubnet_list)
! 1528: if (!sn->hidden)
! 1529: {
! 1530: lsab_put_prefix(p, &sn->prefix, sn->cost);
! 1531: if (sn->prefix.pxlen == max)
! 1532: host_addr = 1;
! 1533: i++;
! 1534: }
! 1535:
! 1536: /* If there are some configured vlinks, find some global address
! 1537: (even from another area), which will be used as a vlink endpoint. */
! 1538: if (!EMPTY_LIST(cf->vlink_list) && !host_addr && ospf_is_ip6(p))
! 1539: {
! 1540: WALK_LIST(ifa, p->iface_list)
! 1541: {
! 1542: if ((ifa->type == OSPF_IT_VLINK) || (ifa->state == OSPF_IS_DOWN))
! 1543: continue;
! 1544:
! 1545: struct ifa *a;
! 1546: WALK_LIST(a, ifa->iface->addrs)
! 1547: {
! 1548: if ((a->prefix.type != NET_IP6) ||
! 1549: (a->flags & IA_SECONDARY) ||
! 1550: (a->scope <= SCOPE_LINK))
! 1551: continue;
! 1552:
! 1553: /* Found some IP */
! 1554: net_addr_ip6 net = NET_ADDR_IP6(a->ip, IP6_MAX_PREFIX_LENGTH);
! 1555: lsab_put_prefix(p, (net_addr *) &net, 0);
! 1556: i++;
! 1557: goto done;
! 1558: }
! 1559: }
! 1560: }
! 1561:
! 1562: done:
! 1563: lp = p->lsab;
! 1564: lp->pxcount = i;
! 1565: }
! 1566:
! 1567: static void
! 1568: ospf_originate_prefix_rt_lsa(struct ospf_proto *p, struct ospf_area *oa)
! 1569: {
! 1570: if (ospf_is_v2(p))
! 1571: return;
! 1572:
! 1573: struct ospf_new_lsa lsa = {
! 1574: .type = LSA_T_PREFIX,
! 1575: .dom = oa->areaid,
! 1576: .id = 0
! 1577: };
! 1578:
! 1579: prepare_prefix_rt_lsa_body(p, oa);
! 1580:
! 1581: ospf_originate_lsa(p, &lsa);
! 1582: }
! 1583:
! 1584:
! 1585: /*
! 1586: * Prefix-Net-LSA handling (assume OSPFv3)
! 1587: * Type = LSA_T_PREFIX, referred type = LSA_T_NET
! 1588: */
! 1589:
! 1590: static inline int
! 1591: prefix_space(u32 *buf)
! 1592: {
! 1593: int pxl = *buf >> 24;
! 1594: return IPV6_PREFIX_SPACE(pxl);
! 1595: }
! 1596:
! 1597: static inline int
! 1598: prefix_same(u32 *b1, u32 *b2)
! 1599: {
! 1600: int pxl1 = *b1 >> 24;
! 1601: int pxl2 = *b2 >> 24;
! 1602: int pxs, i;
! 1603:
! 1604: if (pxl1 != pxl2)
! 1605: return 0;
! 1606:
! 1607: pxs = IPV6_PREFIX_WORDS(pxl1);
! 1608: for (i = 1; i < pxs; i++)
! 1609: if (b1[i] != b2[i])
! 1610: return 0;
! 1611:
! 1612: return 1;
! 1613: }
! 1614:
! 1615: static inline u32 *
! 1616: prefix_advance(u32 *buf)
! 1617: {
! 1618: int pxl = *buf >> 24;
! 1619: return buf + IPV6_PREFIX_WORDS(pxl);
! 1620: }
! 1621:
! 1622: /* FIXME eliminate items with LA bit set? see 4.4.3.9 */
! 1623: static void
! 1624: add_prefix(struct ospf_proto *p, u32 *px, int offset, int *pxc)
! 1625: {
! 1626: u32 *pxl = lsab_offset(p, offset);
! 1627: int i;
! 1628: for (i = 0; i < *pxc; pxl = prefix_advance(pxl), i++)
! 1629: if (prefix_same(px, pxl))
! 1630: {
! 1631: /* Options should be logically OR'ed together */
! 1632: *pxl |= (*px & 0x00FF0000);
! 1633: return;
! 1634: }
! 1635:
! 1636: ASSERT(pxl == lsab_end(p));
! 1637:
! 1638: int pxspace = prefix_space(px);
! 1639: pxl = lsab_alloc(p, pxspace);
! 1640: memcpy(pxl, px, pxspace);
! 1641: *pxl &= 0xFFFF0000; /* Set metric to zero */
! 1642: (*pxc)++;
! 1643: }
! 1644:
! 1645: static void
! 1646: add_link_lsa(struct ospf_proto *p, struct ospf_lsa_link *ll, int offset, int *pxc)
! 1647: {
! 1648: u32 *pxb = ll->rest;
! 1649: uint j;
! 1650:
! 1651: for (j = 0; j < ll->pxcount; pxb = prefix_advance(pxb), j++)
! 1652: {
! 1653: u8 pxlen = (pxb[0] >> 24);
! 1654: u8 pxopts = (pxb[0] >> 16);
! 1655:
! 1656: /* Skip NU or LA prefixes */
! 1657: if (pxopts & (OPT_PX_NU | OPT_PX_LA))
! 1658: continue;
! 1659:
! 1660: /* Skip link-local prefixes */
! 1661: if (ospf_is_ip6(p) && (pxlen >= 10) && ((pxb[1] & 0xffc00000) == 0xfe800000))
! 1662: continue;
! 1663:
! 1664: add_prefix(p, pxb, offset, pxc);
! 1665: }
! 1666: }
! 1667:
! 1668: static void
! 1669: prepare_prefix_net_lsa_body(struct ospf_proto *p, struct ospf_iface *ifa)
! 1670: {
! 1671: struct ospf_lsa_prefix *lp;
! 1672: struct ospf_neighbor *n;
! 1673: struct top_hash_entry *en;
! 1674: int pxc, offset;
! 1675:
! 1676: ASSERT(p->lsab_used == 0);
! 1677: lp = lsab_allocz(p, sizeof(struct ospf_lsa_prefix));
! 1678: lp->ref_type = LSA_T_NET;
! 1679: lp->ref_id = ifa->net_lsa->lsa.id;
! 1680: lp->ref_rt = p->router_id;
! 1681: lp = NULL; /* buffer might be reallocated later */
! 1682:
! 1683: pxc = 0;
! 1684: offset = p->lsab_used;
! 1685:
! 1686: /* Find all Link LSAs associated with the link and merge their prefixes */
! 1687: if (en = ifa->link_lsa)
! 1688: add_link_lsa(p, en->next_lsa_body ?: en->lsa_body, offset, &pxc);
! 1689:
! 1690: WALK_LIST(n, ifa->neigh_list)
! 1691: if ((n->state == NEIGHBOR_FULL) &&
! 1692: (en = ospf_hash_find(p->gr, ifa->iface_id, n->iface_id, n->rid, LSA_T_LINK)))
! 1693: add_link_lsa(p, en->lsa_body, offset, &pxc);
! 1694:
! 1695: lp = p->lsab;
! 1696: lp->pxcount = pxc;
! 1697: }
! 1698:
! 1699: static void
! 1700: ospf_originate_prefix_net_lsa(struct ospf_proto *p, struct ospf_iface *ifa)
! 1701: {
! 1702: if (ospf_is_v2(p))
! 1703: return;
! 1704:
! 1705: struct ospf_new_lsa lsa = {
! 1706: .type = LSA_T_PREFIX,
! 1707: .dom = ifa->oa->areaid,
! 1708: .id = ifa->iface_id,
! 1709: .ifa = ifa
! 1710: };
! 1711:
! 1712: prepare_prefix_net_lsa_body(p, ifa);
! 1713:
! 1714: ifa->pxn_lsa = ospf_originate_lsa(p, &lsa);
! 1715: }
! 1716:
! 1717:
! 1718: /*
! 1719: * Grace LSA handling
! 1720: * Type = LSA_T_GR, opaque type = LSA_OT_GR
! 1721: */
! 1722:
! 1723: static inline void
! 1724: ospf_add_gr_period_tlv(struct ospf_proto *p, uint period)
! 1725: {
! 1726: struct ospf_tlv *tlv = lsab_allocz(p, sizeof(struct ospf_tlv) + sizeof(u32));
! 1727: tlv->type = LSA_GR_PERIOD;
! 1728: tlv->length = 4;
! 1729: tlv->data[0] = period;
! 1730: }
! 1731:
! 1732: static inline void
! 1733: ospf_add_gr_reason_tlv(struct ospf_proto *p, uint reason)
! 1734: {
! 1735: struct ospf_tlv *tlv = lsab_allocz(p, sizeof(struct ospf_tlv) + sizeof(u32));
! 1736: tlv->type = LSA_GR_REASON;
! 1737: tlv->length = 1;
! 1738: tlv->data[0] = reason << 24;
! 1739: }
! 1740:
! 1741: static inline void
! 1742: ospf_add_gr_address_tlv(struct ospf_proto *p, ip4_addr addr)
! 1743: {
! 1744: struct ospf_tlv *tlv = lsab_allocz(p, sizeof(struct ospf_tlv) + sizeof(u32));
! 1745: tlv->type = LSA_GR_ADDRESS;
! 1746: tlv->length = 4;
! 1747: tlv->data[0] = ip4_to_u32(addr);
! 1748: }
! 1749:
! 1750: void
! 1751: ospf_originate_gr_lsa(struct ospf_proto *p, struct ospf_iface *ifa)
! 1752: {
! 1753: struct ospf_new_lsa lsa = {
! 1754: .type = LSA_T_GR,
! 1755: .dom = ifa->iface_id,
! 1756: .id = ospf_is_v2(p) ? 0 : ifa->iface_id,
! 1757: .ifa = ifa
! 1758: };
! 1759:
! 1760: ospf_add_gr_period_tlv(p, p->gr_time);
! 1761: ospf_add_gr_reason_tlv(p, 0);
! 1762:
! 1763: uint t = ifa->type;
! 1764: if (ospf_is_v2(p) && ((t == OSPF_IT_BCAST) || (t == OSPF_IT_NBMA) || (t == OSPF_IT_PTMP)))
! 1765: ospf_add_gr_address_tlv(p, ipa_to_ip4(ifa->addr->ip));
! 1766:
! 1767: ospf_originate_lsa(p, &lsa);
! 1768: }
! 1769:
! 1770:
! 1771: /*
! 1772: * Router Information LSA handling
! 1773: * Type = LSA_T_RI_AREA, opaque type = LSA_OT_RI
! 1774: */
! 1775:
! 1776: void
! 1777: ospf_add_ric_tlv(struct ospf_proto *p)
! 1778: {
! 1779: struct ospf_tlv *ri = lsab_allocz(p, sizeof(struct ospf_tlv) + sizeof(u32));
! 1780: ri->type = LSA_RI_RIC;
! 1781: ri->length = sizeof(struct ospf_tlv) + sizeof(u32);
! 1782:
! 1783: BIT32R_SET(ri->data, LSA_RIC_STUB_ROUTER);
! 1784: }
! 1785:
! 1786: void
! 1787: ospf_originate_ri_lsa(struct ospf_proto *p, struct ospf_area *oa)
! 1788: {
! 1789: struct ospf_new_lsa lsa = {
! 1790: .type = LSA_T_RI_AREA,
! 1791: .dom = oa->areaid,
! 1792: .id = p->instance_id
! 1793: };
! 1794:
! 1795: ospf_add_ric_tlv(p);
! 1796:
! 1797: ospf_originate_lsa(p, &lsa);
! 1798: }
! 1799:
! 1800:
! 1801: /*
! 1802: * Generic topology code
! 1803: */
! 1804:
! 1805: static inline int breaks_minlsinterval(struct top_hash_entry *en)
! 1806: { return en && (en->lsa.age < LSA_MAXAGE) && (lsa_inst_age(en) < MINLSINTERVAL); }
! 1807:
! 1808: void
! 1809: ospf_update_topology(struct ospf_proto *p)
! 1810: {
! 1811: struct ospf_area *oa;
! 1812: struct ospf_iface *ifa;
! 1813:
! 1814: /* No LSA reorigination during GR recovery */
! 1815: if (p->gr_recovery)
! 1816: return;
! 1817:
! 1818: WALK_LIST(oa, p->area_list)
! 1819: {
! 1820: if (oa->update_rt_lsa)
! 1821: {
! 1822: /*
! 1823: * Generally, MinLSInterval is enforced in ospf_do_originate_lsa(), but
! 1824: * origination of (prefix) router LSA is a special case. We do not want to
! 1825: * prepare a new router LSA body and then postpone it in en->next_lsa_body
! 1826: * for later origination, because there are side effects (updates of
! 1827: * rt_pos_* and px_pos_* in ospf_iface structures) during that, which may
! 1828: * confuse routing table calculation if executed after LSA body
! 1829: * preparation but before final LSA origination (as rtcalc would use
! 1830: * current rt_pos_* indexes but the old router LSA body).
! 1831: *
! 1832: * Here, we ensure that MinLSInterval is observed and we do not even try
! 1833: * to originate these LSAs if it is not. Therefore, origination, when
! 1834: * requested, will succeed unless there is also a seqnum wrapping, which
! 1835: * is not a problem because in that case rtcalc is blocked by MaxAge.
! 1836: */
! 1837:
! 1838: if (breaks_minlsinterval(oa->rt) || breaks_minlsinterval(oa->pxr_lsa))
! 1839: continue;
! 1840:
! 1841: ospf_originate_rt_lsa(p, oa);
! 1842: ospf_originate_prefix_rt_lsa(p, oa);
! 1843: // ospf_originate_ri_lsa(p, oa);
! 1844: oa->update_rt_lsa = 0;
! 1845: }
! 1846: }
! 1847:
! 1848: WALK_LIST(ifa, p->iface_list)
! 1849: {
! 1850: if (ifa->type == OSPF_IT_VLINK)
! 1851: continue;
! 1852:
! 1853: if (ifa->update_link_lsa)
! 1854: {
! 1855: if ((ifa->state > OSPF_IS_LOOP) && !ifa->link_lsa_suppression)
! 1856: ospf_originate_link_lsa(p, ifa);
! 1857: else
! 1858: ospf_flush2_lsa(p, &ifa->link_lsa);
! 1859:
! 1860: ifa->update_link_lsa = 0;
! 1861: }
! 1862:
! 1863: if (ifa->update_net_lsa)
! 1864: {
! 1865: if ((ifa->state == OSPF_IS_DR) && (ifa->fadj > 0))
! 1866: {
! 1867: ospf_originate_net_lsa(p, ifa);
! 1868: ospf_originate_prefix_net_lsa(p, ifa);
! 1869: }
! 1870: else
! 1871: {
! 1872: ospf_flush2_lsa(p, &ifa->net_lsa);
! 1873: ospf_flush2_lsa(p, &ifa->pxn_lsa);
! 1874: }
! 1875:
! 1876: ifa->update_net_lsa = 0;
! 1877: }
! 1878: }
! 1879: }
! 1880:
! 1881:
! 1882: static void
! 1883: ospf_top_ht_alloc(struct top_graph *f)
! 1884: {
! 1885: f->hash_size = 1 << f->hash_order;
! 1886: f->hash_mask = f->hash_size - 1;
! 1887: if (f->hash_order > HASH_HI_MAX - HASH_HI_STEP)
! 1888: f->hash_entries_max = ~0;
! 1889: else
! 1890: f->hash_entries_max = f->hash_size HASH_HI_MARK;
! 1891: if (f->hash_order < HASH_LO_MIN + HASH_LO_STEP)
! 1892: f->hash_entries_min = 0;
! 1893: else
! 1894: f->hash_entries_min = f->hash_size HASH_LO_MARK;
! 1895: DBG("Allocating OSPF hash of order %d: %d hash_entries, %d low, %d high\n",
! 1896: f->hash_order, f->hash_size, f->hash_entries_min, f->hash_entries_max);
! 1897: f->hash_table =
! 1898: mb_alloc(f->pool, f->hash_size * sizeof(struct top_hash_entry *));
! 1899: bzero(f->hash_table, f->hash_size * sizeof(struct top_hash_entry *));
! 1900: }
! 1901:
! 1902: static inline void
! 1903: ospf_top_ht_free(struct top_hash_entry **h)
! 1904: {
! 1905: mb_free(h);
! 1906: }
! 1907:
! 1908: static inline u32
! 1909: ospf_top_hash_u32(u32 a)
! 1910: {
! 1911: /* Shamelessly stolen from IP address hashing in ipv4.h */
! 1912: a ^= a >> 16;
! 1913: a ^= a << 10;
! 1914: return a;
! 1915: }
! 1916:
! 1917: static uint
! 1918: ospf_top_hash(struct top_graph *f, u32 domain, u32 lsaid, u32 rtrid, u32 type)
! 1919: {
! 1920: /* In OSPFv2, we don't know Router ID when looking for network LSAs.
! 1921: In OSPFv3, we don't know LSA ID when looking for router LSAs.
! 1922: In both cases, there is (usually) just one (or small number)
! 1923: appropriate LSA, so we just clear unknown part of key. */
! 1924:
! 1925: return (((f->ospf2 && (type == LSA_T_NET)) ? 0 : ospf_top_hash_u32(rtrid)) +
! 1926: ((!f->ospf2 && (type == LSA_T_RT)) ? 0 : ospf_top_hash_u32(lsaid)) +
! 1927: type + domain) & f->hash_mask;
! 1928:
! 1929: /*
! 1930: return (ospf_top_hash_u32(lsaid) + ospf_top_hash_u32(rtrid) +
! 1931: type + areaid) & f->hash_mask;
! 1932: */
! 1933: }
! 1934:
! 1935: /**
! 1936: * ospf_top_new - allocated new topology database
! 1937: * @p: OSPF protocol instance
! 1938: * @pool: pool for allocation
! 1939: *
! 1940: * This dynamically hashed structure is used for keeping LSAs. Mainly it is used
! 1941: * for the LSA database of the OSPF protocol, but also for LSA retransmission
! 1942: * and request lists of OSPF neighbors.
! 1943: */
! 1944: struct top_graph *
! 1945: ospf_top_new(struct ospf_proto *p, pool *pool)
! 1946: {
! 1947: struct top_graph *f;
! 1948:
! 1949: f = mb_allocz(pool, sizeof(struct top_graph));
! 1950: f->pool = pool;
! 1951: f->hash_slab = sl_new(f->pool, sizeof(struct top_hash_entry));
! 1952: f->hash_order = HASH_DEF_ORDER;
! 1953: ospf_top_ht_alloc(f);
! 1954: f->hash_entries = 0;
! 1955: f->hash_entries_min = 0;
! 1956: f->ospf2 = ospf_is_v2(p);
! 1957: return f;
! 1958: }
! 1959:
! 1960: void
! 1961: ospf_top_free(struct top_graph *f)
! 1962: {
! 1963: rfree(f->hash_slab);
! 1964: ospf_top_ht_free(f->hash_table);
! 1965: mb_free(f);
! 1966: }
! 1967:
! 1968: static void
! 1969: ospf_top_rehash(struct top_graph *f, int step)
! 1970: {
! 1971: struct top_hash_entry **n, **oldt, **newt, *e, *x;
! 1972: uint oldn, oldh;
! 1973:
! 1974: oldn = f->hash_size;
! 1975: oldt = f->hash_table;
! 1976: DBG("re-hashing topology hash from order %d to %d\n", f->hash_order,
! 1977: f->hash_order + step);
! 1978: f->hash_order += step;
! 1979: ospf_top_ht_alloc(f);
! 1980: newt = f->hash_table;
! 1981:
! 1982: for (oldh = 0; oldh < oldn; oldh++)
! 1983: {
! 1984: e = oldt[oldh];
! 1985: while (e)
! 1986: {
! 1987: x = e->next;
! 1988: n = newt + ospf_top_hash(f, e->domain, e->lsa.id, e->lsa.rt, e->lsa_type);
! 1989: e->next = *n;
! 1990: *n = e;
! 1991: e = x;
! 1992: }
! 1993: }
! 1994: ospf_top_ht_free(oldt);
! 1995: }
! 1996:
! 1997: static struct top_hash_entry *
! 1998: ospf_hash_find_(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type)
! 1999: {
! 2000: struct top_hash_entry *e;
! 2001: e = f->hash_table[ospf_top_hash(f, domain, lsa, rtr, type)];
! 2002:
! 2003: while (e && (e->lsa.id != lsa || e->lsa.rt != rtr ||
! 2004: e->lsa_type != type || e->domain != domain))
! 2005: e = e->next;
! 2006:
! 2007: return e;
! 2008: }
! 2009:
! 2010: struct top_hash_entry *
! 2011: ospf_hash_find(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type)
! 2012: {
! 2013: struct top_hash_entry *e = ospf_hash_find_(f, domain, lsa, rtr, type);
! 2014:
! 2015: /* Hide hash entry with empty lsa_body */
! 2016: return (e && e->lsa_body) ? e : NULL;
! 2017: }
! 2018:
! 2019: /* In OSPFv2, lsa.id is the same as lsa.rt for router LSA. In OSPFv3, we don't know
! 2020: lsa.id when looking for router LSAs. We return matching LSA with smallest lsa.id. */
! 2021: struct top_hash_entry *
! 2022: ospf_hash_find_rt(struct top_graph *f, u32 domain, u32 rtr)
! 2023: {
! 2024: struct top_hash_entry *rv = NULL;
! 2025: struct top_hash_entry *e;
! 2026: /* We can put rtr for lsa.id to hash fn, it is ignored in OSPFv3 */
! 2027: e = f->hash_table[ospf_top_hash(f, domain, rtr, rtr, LSA_T_RT)];
! 2028:
! 2029: while (e)
! 2030: {
! 2031: if (e->lsa.rt == rtr && e->lsa_type == LSA_T_RT && e->domain == domain && e->lsa_body)
! 2032: {
! 2033: if (f->ospf2 && (e->lsa.id == rtr))
! 2034: return e;
! 2035: if (!f->ospf2 && (!rv || e->lsa.id < rv->lsa.id))
! 2036: rv = e;
! 2037: }
! 2038: e = e->next;
! 2039: }
! 2040:
! 2041: return rv;
! 2042: }
! 2043:
! 2044: /*
! 2045: * ospf_hash_find_rt3_first() and ospf_hash_find_rt3_next() are used exclusively
! 2046: * for lsa_walk_rt_init(), lsa_walk_rt(), therefore they skip MaxAge entries.
! 2047: */
! 2048: static inline struct top_hash_entry *
! 2049: find_matching_rt3(struct top_hash_entry *e, u32 domain, u32 rtr)
! 2050: {
! 2051: while (e && (e->lsa.rt != rtr || e->lsa_type != LSA_T_RT ||
! 2052: e->domain != domain || e->lsa.age == LSA_MAXAGE))
! 2053: e = e->next;
! 2054: return e;
! 2055: }
! 2056:
! 2057: struct top_hash_entry *
! 2058: ospf_hash_find_rt3_first(struct top_graph *f, u32 domain, u32 rtr)
! 2059: {
! 2060: struct top_hash_entry *e;
! 2061: e = f->hash_table[ospf_top_hash(f, domain, 0, rtr, LSA_T_RT)];
! 2062: return find_matching_rt3(e, domain, rtr);
! 2063: }
! 2064:
! 2065: struct top_hash_entry *
! 2066: ospf_hash_find_rt3_next(struct top_hash_entry *e)
! 2067: {
! 2068: return find_matching_rt3(e->next, e->domain, e->lsa.rt);
! 2069: }
! 2070:
! 2071: /* In OSPFv2, we don't know Router ID when looking for network LSAs.
! 2072: There should be just one, so we find any match. */
! 2073: struct top_hash_entry *
! 2074: ospf_hash_find_net2(struct top_graph *f, u32 domain, u32 id)
! 2075: {
! 2076: struct top_hash_entry *e;
! 2077: e = f->hash_table[ospf_top_hash(f, domain, id, 0, LSA_T_NET)];
! 2078:
! 2079: while (e && (e->lsa.id != id || e->lsa_type != LSA_T_NET ||
! 2080: e->domain != domain || e->lsa_body == NULL))
! 2081: e = e->next;
! 2082:
! 2083: return e;
! 2084: }
! 2085:
! 2086:
! 2087: struct top_hash_entry *
! 2088: ospf_hash_get(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type)
! 2089: {
! 2090: struct top_hash_entry **ee;
! 2091: struct top_hash_entry *e;
! 2092:
! 2093: ee = f->hash_table + ospf_top_hash(f, domain, lsa, rtr, type);
! 2094: e = *ee;
! 2095:
! 2096: while (e && (e->lsa.id != lsa || e->lsa.rt != rtr ||
! 2097: e->lsa_type != type || e->domain != domain))
! 2098: e = e->next;
! 2099:
! 2100: if (e)
! 2101: return e;
! 2102:
! 2103: e = sl_alloc(f->hash_slab);
! 2104: bzero(e, sizeof(struct top_hash_entry));
! 2105:
! 2106: e->color = OUTSPF;
! 2107: e->dist = LSINFINITY;
! 2108: e->lsa.type_raw = type;
! 2109: e->lsa.id = lsa;
! 2110: e->lsa.rt = rtr;
! 2111: e->lsa.sn = LSA_ZEROSEQNO;
! 2112: e->lsa_type = type;
! 2113: e->domain = domain;
! 2114: e->next = *ee;
! 2115: *ee = e;
! 2116: if (f->hash_entries++ > f->hash_entries_max)
! 2117: ospf_top_rehash(f, HASH_HI_STEP);
! 2118: return e;
! 2119: }
! 2120:
! 2121: void
! 2122: ospf_hash_delete(struct top_graph *f, struct top_hash_entry *e)
! 2123: {
! 2124: struct top_hash_entry **ee = f->hash_table +
! 2125: ospf_top_hash(f, e->domain, e->lsa.id, e->lsa.rt, e->lsa_type);
! 2126:
! 2127: while (*ee)
! 2128: {
! 2129: if (*ee == e)
! 2130: {
! 2131: *ee = e->next;
! 2132: sl_free(f->hash_slab, e);
! 2133: if (f->hash_entries-- < f->hash_entries_min)
! 2134: ospf_top_rehash(f, -HASH_LO_STEP);
! 2135: return;
! 2136: }
! 2137: ee = &((*ee)->next);
! 2138: }
! 2139: bug("ospf_hash_delete() called for invalid node");
! 2140: }
! 2141:
! 2142: /*
! 2143: static void
! 2144: ospf_dump_lsa(struct top_hash_entry *he, struct proto *p)
! 2145: {
! 2146:
! 2147: struct ospf_lsa_rt *rt = NULL;
! 2148: struct ospf_lsa_rt_link *rr = NULL;
! 2149: struct ospf_lsa_net *ln = NULL;
! 2150: u32 *rts = NULL;
! 2151: u32 i, max;
! 2152:
! 2153: OSPF_TRACE(D_EVENTS, "- %1x %-1R %-1R %4u 0x%08x 0x%04x %-1R",
! 2154: he->lsa.type, he->lsa.id, he->lsa.rt, he->lsa.age, he->lsa.sn,
! 2155: he->lsa.checksum, he->domain);
! 2156:
! 2157:
! 2158: switch (he->lsa.type)
! 2159: {
! 2160: case LSA_T_RT:
! 2161: rt = he->lsa_body;
! 2162: rr = (struct ospf_lsa_rt_link *) (rt + 1);
! 2163:
! 2164: for (i = 0; i < lsa_rt_items(&he->lsa); i++)
! 2165: OSPF_TRACE(D_EVENTS, " - %1x %-1R %-1R %5u",
! 2166: rr[i].type, rr[i].id, rr[i].data, rr[i].metric);
! 2167: break;
! 2168:
! 2169: case LSA_T_NET:
! 2170: ln = he->lsa_body;
! 2171: rts = (u32 *) (ln + 1);
! 2172:
! 2173: for (i = 0; i < lsa_net_items(&he->lsa); i++)
! 2174: OSPF_TRACE(D_EVENTS, " - %-1R", rts[i]);
! 2175: break;
! 2176:
! 2177: default:
! 2178: break;
! 2179: }
! 2180: }
! 2181:
! 2182: void
! 2183: ospf_top_dump(struct top_graph *f, struct proto *p)
! 2184: {
! 2185: uint i;
! 2186: OSPF_TRACE(D_EVENTS, "Hash entries: %d", f->hash_entries);
! 2187:
! 2188: for (i = 0; i < f->hash_size; i++)
! 2189: {
! 2190: struct top_hash_entry *e;
! 2191: for (e = f->hash_table[i]; e != NULL; e = e->next)
! 2192: ospf_dump_lsa(e, p);
! 2193: }
! 2194: }
! 2195: */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to topology.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird2 / proto / ospf