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