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