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