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