Return to topology.c CVS log | Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird2 / proto / ospf |
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: */