]>
git.ipfire.org Git - thirdparty/bird.git/blob - proto/ospf/lsupd.c
4 * (c) 2000--2004 Ondrej Filip <feela@network.cz>
6 * Can be freely distributed and used under the terms of the GNU GPL.
12 struct ospf_lsupd_packet
14 struct ospf_packet ospf_packet
;
15 u32 lsano
; /* Number of LSA's */
19 /* Beware of unaligned access */
20 void ospf_dump_lsahdr(struct proto
*p
, struct ospf_lsa_header
*lsa_n
)
22 struct ospf_lsa_header lsa
;
23 ntohlsah(lsa_n
, &lsa
);
25 log(L_TRACE
"%s: LSA Type: %04x, Id: %R, Rt: %R, Age: %u, Seq: %08x, Sum: %04x",
26 p
->name
, lsa
.type
, lsa
.id
, lsa
.rt
, lsa
.age
, lsa
.sn
, lsa
.checksum
);
29 void ospf_dump_common(struct proto
*p
, struct ospf_packet
*op
)
31 log(L_TRACE
"%s: length %d", p
->name
, ntohs(op
->length
));
32 log(L_TRACE
"%s: router %R", p
->name
, ntohl(op
->routerid
));
35 static void ospf_dump_lsupd(struct proto
*p
, struct ospf_lsupd_packet
*pkt
)
37 struct ospf_packet
*op
= &pkt
->ospf_packet
;
39 ASSERT(op
->type
== LSUPD_P
);
40 ospf_dump_common(p
, op
);
42 /* We know that ntohs(op->length) >= sizeof(struct ospf_lsa_header) */
44 unsigned int offset
= sizeof(struct ospf_lsupd_packet
);
45 unsigned int bound
= ntohs(op
->length
) - sizeof(struct ospf_lsa_header
);
46 unsigned int i
, j
, lsalen
;
48 j
= ntohl(pkt
->lsano
);
49 for (i
= 0; i
< j
; i
++)
53 log(L_TRACE
"%s: LSA invalid", p
->name
);
57 struct ospf_lsa_header
*lsa
= (void *) (pbuf
+ offset
);
58 ospf_dump_lsahdr(p
, lsa
);
59 lsalen
= ntohs(lsa
->length
);
62 if (((lsalen
% 4) != 0) || (lsalen
<= sizeof(struct ospf_lsa_header
)))
64 log(L_TRACE
"%s: LSA invalid", p
->name
);
74 ospf_lsa_flooding_allowed(struct ospf_lsa_header
*lsa
, u32 domain
, struct ospf_iface
*ifa
)
76 if (lsa
->type
== LSA_T_EXT
)
78 if (ifa
->type
== OSPF_IT_VLINK
)
80 if (!oa_is_ext(ifa
->oa
))
85 return ifa
->oa
->areaid
== domain
;
91 unknown_lsa_type(struct ospf_lsa_header
*lsa
)
111 ospf_lsa_flooding_allowed(struct ospf_lsa_header
*lsa
, u32 domain
, struct ospf_iface
*ifa
)
113 u32 scope
= LSA_SCOPE(lsa
);
116 if (unknown_lsa_type(lsa
) && !(lsa
->type
& LSA_UBIT
))
117 scope
= LSA_SCOPE_LINK
;
122 return ifa
->iface
->index
== domain
;
125 return ifa
->oa
->areaid
== domain
;
128 if (ifa
->type
== OSPF_IT_VLINK
)
130 if (!oa_is_ext(ifa
->oa
))
135 log(L_ERR
"LSA with invalid scope");
143 * ospf_lsupd_flood - send received or generated lsa to the neighbors
145 * @n: neighbor than sent this lsa (or NULL if generated)
146 * @hn: LSA header followed by lsa body in network endianity (may be NULL)
147 * @hh: LSA header in host endianity (must be filled)
148 * @domain: domain of LSA (must be filled)
149 * @rtl: add this LSA into retransmission list
152 * return value - was the LSA flooded back?
156 ospf_lsupd_flood(struct proto_ospf
*po
,
157 struct ospf_neighbor
*n
, struct ospf_lsa_header
*hn
,
158 struct ospf_lsa_header
*hh
, u32 domain
, int rtl
)
160 struct ospf_iface
*ifa
;
161 struct ospf_neighbor
*nn
;
162 struct top_hash_entry
*en
;
163 struct proto
*p
= &po
->proto
;
167 WALK_LIST(ifa
, po
->iface_list
)
172 if (! ospf_lsa_flooding_allowed(hh
, domain
, ifa
))
175 DBG("Wanted to flood LSA: Type: %u, ID: %R, RT: %R, SN: 0x%x, Age %u\n",
176 hh
->type
, hh
->id
, hh
->rt
, hh
->sn
, hh
->age
);
179 WALK_LIST(nn
, ifa
->neigh_list
)
182 if (nn
->state
< NEIGHBOR_EXCHANGE
)
186 if (nn
->state
< NEIGHBOR_FULL
)
188 if ((en
= ospf_hash_find_header(nn
->lsrqh
, domain
, hh
)) != NULL
)
190 DBG("That LSA found in lsreq list for neigh %R\n", nn
->rid
);
192 switch (lsa_comp(hh
, &en
->lsa
))
198 s_rem_node(SNODE en
);
199 if (en
->lsa_body
!= NULL
)
200 mb_free(en
->lsa_body
);
202 DBG("Removing from lsreq list for neigh %R\n", nn
->rid
);
203 ospf_hash_delete(nn
->lsrqh
, en
);
204 if (EMPTY_SLIST(nn
->lsrql
))
205 ospf_neigh_sm(nn
, INM_LOADDONE
);
209 s_rem_node(SNODE en
);
210 if (en
->lsa_body
!= NULL
)
211 mb_free(en
->lsa_body
);
213 DBG("Removing from lsreq list for neigh %R\n", nn
->rid
);
214 ospf_hash_delete(nn
->lsrqh
, en
);
215 if (EMPTY_SLIST(nn
->lsrql
))
216 ospf_neigh_sm(nn
, INM_LOADDONE
);
219 bug("Bug in lsa_comp?");
231 /* In OSPFv3, there should be check whether receiving router understand
232 that type of LSA (for LSA types with U-bit == 0). But as we does not support
233 any optional LSA types, this is not needed yet */
235 if ((en
= ospf_hash_find_header(nn
->lsrth
, domain
, hh
)) == NULL
)
237 en
= ospf_hash_get_header(nn
->lsrth
, domain
, hh
);
241 s_rem_node(SNODE en
);
243 s_add_tail(&nn
->lsrtl
, SNODE en
);
244 memcpy(&en
->lsa
, hh
, sizeof(struct ospf_lsa_header
));
245 DBG("Adding that LSA for flood to %I\n", nn
->ip
);
249 if ((en
= ospf_hash_find_header(nn
->lsrth
, domain
, hh
)) != NULL
)
251 s_rem_node(SNODE en
);
252 ospf_hash_delete(nn
->lsrth
, en
);
260 continue; /* pg 150 (2) */
262 if (n
&& (n
->ifa
== ifa
))
264 if ((n
->rid
== ifa
->drid
) || n
->rid
== ifa
->bdrid
)
265 continue; /* pg 150 (3) */
266 if (ifa
->state
== OSPF_IS_BACKUP
)
267 continue; /* pg 150 (4) */
273 struct ospf_lsupd_packet
*pk
;
274 struct ospf_packet
*op
;
275 struct ospf_lsa_header
*lh
;
277 pk
= ospf_tx_buffer(ifa
);
278 op
= &pk
->ospf_packet
;
280 ospf_pkt_fill_hdr(ifa
, pk
, LSUPD_P
);
281 pk
->lsano
= htonl(1);
283 lh
= (struct ospf_lsa_header
*) (pk
+ 1);
285 /* Copy LSA into the packet */
288 memcpy(lh
, hn
, ntohs(hn
->length
));
293 struct top_hash_entry
*en
;
296 help
= (u8
*) (lh
+ 1);
297 en
= ospf_hash_find_header(po
->gr
, domain
, hh
);
298 htonlsab(en
->lsa_body
, help
, hh
->length
- sizeof(struct ospf_lsa_header
));
301 len
= sizeof(struct ospf_lsupd_packet
) + ntohs(lh
->length
);
303 age
= ntohs(lh
->age
);
304 age
+= ifa
->inftransdelay
;
305 if (age
> LSA_MAXAGE
)
307 lh
->age
= htons(age
);
309 op
->length
= htons(len
);
311 OSPF_PACKET(ospf_dump_lsupd
, pk
, "LSUPD packet flooded via %s", ifa
->iface
->name
);
316 if ((ifa
->state
== OSPF_IS_BACKUP
) || (ifa
->state
== OSPF_IS_DR
))
317 ospf_send_to_all(ifa
);
318 else if (ifa
->cf
->real_bcast
)
319 ospf_send_to_bdr(ifa
);
321 ospf_send_to(ifa
, AllDRouters
);
325 if ((ifa
->state
== OSPF_IS_BACKUP
) || (ifa
->state
== OSPF_IS_DR
))
326 ospf_send_to_agt(ifa
, NEIGHBOR_EXCHANGE
);
328 ospf_send_to_bdr(ifa
);
332 ospf_send_to_all(ifa
);
336 ospf_send_to_agt(ifa
, NEIGHBOR_EXCHANGE
);
340 ospf_send_to(ifa
, ifa
->vip
);
344 bug("Bug in ospf_lsupd_flood()");
351 void /* I send all I received in LSREQ */
352 ospf_lsupd_send_list(struct ospf_neighbor
*n
, list
* l
)
354 struct ospf_area
*oa
= n
->ifa
->oa
;
355 struct proto
*p
= &oa
->po
->proto
;
356 struct l_lsr_head
*lsr
;
357 struct top_hash_entry
*en
;
358 struct ospf_lsupd_packet
*pkt
;
359 u32 len
, len2
, lsano
;
362 pkt
= ospf_tx_buffer(n
->ifa
);
366 while(NODE_NEXT(lsr
))
368 /* Prepare the packet */
369 ospf_pkt_fill_hdr(n
->ifa
, pkt
, LSUPD_P
);
370 len
= sizeof(struct ospf_lsupd_packet
);
373 /* Fill the packet with LSAs */
374 while(NODE_NEXT(lsr
))
376 u32 domain
= ospf_lsa_domain(lsr
->lsh
.type
, n
->ifa
);
377 en
= ospf_hash_find(oa
->po
->gr
, domain
, lsr
->lsh
.id
, lsr
->lsh
.rt
, lsr
->lsh
.type
);
380 /* Probably flushed LSA, this should not happen */
381 log(L_WARN
"OSPF: LSA disappeared (Type: %04x, Id: %R, Rt: %R)",
382 lsr
->lsh
.type
, lsr
->lsh
.id
, lsr
->lsh
.rt
);
383 lsr
= NODE_NEXT(lsr
);
387 len2
= len
+ en
->lsa
.length
;
388 if (len2
> ospf_pkt_maxsize(n
->ifa
))
390 /* The packet if full, stop adding LSAs and sent it */
394 /* LSA is larger than MTU, check buffer size */
395 if (len2
> ospf_pkt_bufsize(n
->ifa
))
397 /* Cannot fit in a tx buffer, skip that */
398 log(L_WARN
"OSPF: LSA too large to send (Type: %04x, Id: %R, Rt: %R)",
399 lsr
->lsh
.type
, lsr
->lsh
.id
, lsr
->lsh
.rt
);
400 lsr
= NODE_NEXT(lsr
);
405 /* Copy the LSA to the packet */
406 htonlsah(&(en
->lsa
), (struct ospf_lsa_header
*) (buf
+ len
));
407 htonlsab(en
->lsa_body
, buf
+ len
+ sizeof(struct ospf_lsa_header
),
408 en
->lsa
.length
- sizeof(struct ospf_lsa_header
));
411 lsr
= NODE_NEXT(lsr
);
417 /* Send the packet */
418 pkt
->lsano
= htonl(lsano
);
419 pkt
->ospf_packet
.length
= htons(len
);
420 OSPF_PACKET(ospf_dump_lsupd
, pkt
, "LSUPD packet sent to %I via %s",
421 n
->ip
, n
->ifa
->iface
->name
);
422 ospf_send_to(n
->ifa
, n
->ip
);
427 ospf_lsupd_receive(struct ospf_packet
*ps_i
, struct ospf_iface
*ifa
,
428 struct ospf_neighbor
*n
)
431 struct ospf_neighbor
*ntmp
;
432 struct proto_ospf
*po
= ifa
->oa
->po
;
433 struct proto
*p
= &po
->proto
;
434 unsigned int i
, max
, sendreq
= 1;
436 unsigned int size
= ntohs(ps_i
->length
);
437 if (size
< (sizeof(struct ospf_lsupd_packet
) + sizeof(struct ospf_lsa_header
)))
439 log(L_ERR
"OSPF: Bad LSUPD packet from %I - too short (%u B)", n
->ip
, size
);
443 struct ospf_lsupd_packet
*ps
= (void *) ps_i
;
444 OSPF_PACKET(ospf_dump_lsupd
, ps
, "LSUPD packet received from %I via %s", n
->ip
, ifa
->iface
->name
);
446 if (n
->state
< NEIGHBOR_EXCHANGE
)
448 OSPF_TRACE(D_PACKETS
, "Received lsupd in lesser state than EXCHANGE from (%I)", n
->ip
);
452 ospf_neigh_sm(n
, INM_HELLOREC
); /* Questionable */
454 unsigned int offset
= sizeof(struct ospf_lsupd_packet
);
455 unsigned int bound
= size
- sizeof(struct ospf_lsa_header
);
457 max
= ntohl(ps
->lsano
);
458 for (i
= 0; i
< max
; i
++)
460 struct ospf_lsa_header lsatmp
;
461 struct top_hash_entry
*lsadb
;
465 log(L_WARN
"Received lsupd from %I is too short!", n
->ip
);
466 ospf_neigh_sm(n
, INM_BADLSREQ
);
470 struct ospf_lsa_header
*lsa
= (void *) (((u8
*) ps
) + offset
);
471 unsigned int lsalen
= ntohs(lsa
->length
);
474 if ((offset
> size
) || ((lsalen
% 4) != 0) ||
475 (lsalen
<= sizeof(struct ospf_lsa_header
)))
477 log(L_WARN
"Received LSA from %I with bad length", n
->ip
);
478 ospf_neigh_sm(n
, INM_BADLSREQ
);
483 u16 chsum
= lsa
->checksum
;
484 if (chsum
!= lsasum_check(lsa
, NULL
))
486 log(L_WARN
"Received bad lsa checksum from %I: %x %x", n
->ip
, chsum
, lsa
->checksum
);
492 if ((lsa
->type
== 0) || (lsa
->type
== 6) || (lsa
->type
> LSA_T_NSSA
))
494 log(L_WARN
"Unknown LSA type from %I", n
->ip
);
499 if ((lsa
->type
== LSA_T_EXT
) && !oa_is_ext(ifa
->oa
))
501 log(L_WARN
"Received External LSA in stub area from %I", n
->ip
);
506 if ((LSA_SCOPE(lsa
) == LSA_SCOPE_AS
) && !oa_is_ext(ifa
->oa
))
508 log(L_WARN
"Received LSA with AS scope in stub area from %I", n
->ip
);
513 if ((LSA_SCOPE(lsa
) == LSA_SCOPE_RES
))
515 log(L_WARN
"Received LSA with invalid scope from %I", n
->ip
);
520 ntohlsah(lsa
, &lsatmp
);
522 DBG("Update Type: %u ID: %R RT: %R, Sn: 0x%08x Age: %u, Sum: %u\n",
523 lsatmp
.type
, lsatmp
.id
, lsatmp
.rt
, lsatmp
.sn
, lsatmp
.age
, lsatmp
.checksum
);
525 /* FIXME domain should be link id for unknown LSA types with zero Ubit */
526 u32 domain
= ospf_lsa_domain(lsatmp
.type
, ifa
);
527 lsadb
= ospf_hash_find_header(po
->gr
, domain
, &lsatmp
);
531 DBG("I have Type: %u ID: %R RT: %R, Sn: 0x%08x Age: %u, Sum: %u\n",
532 lsadb
->lsa
.type
, lsadb
->lsa
.id
, lsadb
->lsa
.rt
,
533 lsadb
->lsa
.sn
, lsadb
->lsa
.age
, lsadb
->lsa
.checksum
);
537 if ((lsatmp
.age
== LSA_MAXAGE
) && (lsadb
== NULL
) && can_flush_lsa(po
))
539 ospf_lsack_enqueue(n
, lsa
, ACKL_DIRECT
);
544 if ((lsadb
== NULL
) || (lsa_comp(&lsatmp
, &lsadb
->lsa
) == CMP_NEWER
))
546 struct ospf_iface
*ift
= NULL
;
547 int self
= (lsatmp
.rt
== po
->router_id
);
549 DBG("PG143(5): Received LSA is newer\n");
552 /* 13.4 - check self-originated LSAs of NET type */
553 if ((!self
) && (lsatmp
.type
== LSA_T_NET
))
555 struct ospf_iface
*nifa
;
556 WALK_LIST(nifa
, po
->iface_list
)
560 if (ipa_equal(nifa
->addr
->ip
, ipa_from_u32(lsatmp
.id
)))
569 /* pg 145 (5f) - premature aging of self originated lsa */
572 if ((lsatmp
.age
== LSA_MAXAGE
) && (lsatmp
.sn
== LSA_MAXSEQNO
))
574 ospf_lsack_enqueue(n
, lsa
, ACKL_DIRECT
);
578 OSPF_TRACE(D_EVENTS
, "Received old self-originated LSA (Type: %04x, Id: %R, Rt: %R)",
579 lsatmp
.type
, lsatmp
.id
, lsatmp
.rt
);
583 OSPF_TRACE(D_EVENTS
, "Reflooding new self-originated LSA with newer sequence number");
584 lsadb
->lsa
.sn
= lsatmp
.sn
+ 1;
588 lsasum_calculate(&lsadb
->lsa
, lsadb
->lsa_body
);
589 ospf_lsupd_flood(po
, NULL
, NULL
, &lsadb
->lsa
, domain
, 1);
593 OSPF_TRACE(D_EVENTS
, "Premature aging it");
594 lsatmp
.age
= LSA_MAXAGE
;
595 lsatmp
.sn
= LSA_MAXSEQNO
;
596 lsa
->age
= htons(LSA_MAXAGE
);
597 lsa
->sn
= htonl(LSA_MAXSEQNO
);
598 lsasum_check(lsa
, (lsa
+ 1)); /* It also calculates chsum! */
599 lsatmp
.checksum
= ntohs(lsa
->checksum
);
600 ospf_lsupd_flood(po
, NULL
, lsa
, &lsatmp
, domain
, 0);
606 if (lsadb
&& ((now
- lsadb
->inst_t
) <= MINLSARRIVAL
)) /* FIXME: test for flooding? */
608 OSPF_TRACE(D_EVENTS
, "Skipping LSA received in less that MINLSARRIVAL");
613 /* Remove old from all ret lists */
615 /* Must be done before (5b), otherwise it also removes the new entries from (5b) */
617 WALK_LIST(ift
, po
->iface_list
)
618 WALK_LIST(ntmp
, ift
->neigh_list
)
620 struct top_hash_entry
*en
;
621 if (ntmp
->state
> NEIGHBOR_EXSTART
)
622 if ((en
= ospf_hash_find_header(ntmp
->lsrth
, domain
, &lsadb
->lsa
)) != NULL
)
624 s_rem_node(SNODE en
);
625 ospf_hash_delete(ntmp
->lsrth
, en
);
630 if (ospf_lsupd_flood(po
, n
, lsa
, &lsatmp
, domain
, 1) == 0)
632 DBG("Wasn't flooded back\n"); /* ps 144(5e), pg 153 */
633 if (ifa
->state
== OSPF_IS_BACKUP
)
635 if (ifa
->drid
== n
->rid
)
636 ospf_lsack_enqueue(n
, lsa
, ACKL_DELAY
);
639 ospf_lsack_enqueue(n
, lsa
, ACKL_DELAY
);
642 if ((lsatmp
.age
== LSA_MAXAGE
) && (lsatmp
.sn
== LSA_MAXSEQNO
)
643 && lsadb
&& can_flush_lsa(po
))
645 flush_lsa(lsadb
, po
);
651 void *body
= mb_alloc(p
->pool
, lsatmp
.length
- sizeof(struct ospf_lsa_header
));
652 ntohlsab(lsa
+ 1, body
, lsatmp
.length
- sizeof(struct ospf_lsa_header
));
654 /* We will do validation check after flooding and
655 acknowledging given LSA to minimize problems
656 when communicating with non-validating peer */
657 if (lsa_validate(&lsatmp
, body
) == 0)
659 log(L_WARN
"Received invalid LSA from %I", n
->ip
);
664 lsadb
= lsa_install_new(po
, &lsatmp
, domain
, body
);
665 DBG("New LSA installed in DB\n");
668 /* Events 6,7 from RFC5340 4.4.3. */
669 if ((lsatmp
.type
== LSA_T_LINK
) &&
670 (ifa
->state
== OSPF_IS_DR
))
671 schedule_net_lsa(ifa
);
677 /* FIXME pg145 (6) */
680 if (lsa_comp(&lsatmp
, &lsadb
->lsa
) == CMP_SAME
)
682 struct top_hash_entry
*en
;
683 DBG("PG145(7) Got the same LSA\n");
684 if ((en
= ospf_hash_find_header(n
->lsrth
, lsadb
->domain
, &lsadb
->lsa
)) != NULL
)
687 s_rem_node(SNODE en
);
688 ospf_hash_delete(n
->lsrth
, en
);
690 if (ifa
->state
== OSPF_IS_BACKUP
)
692 if (n
->rid
== ifa
->drid
)
693 ospf_lsack_enqueue(n
, lsa
, ACKL_DELAY
);
699 ospf_lsack_enqueue(n
, lsa
, ACKL_DIRECT
);
706 if ((lsadb
->lsa
.age
== LSA_MAXAGE
) && (lsadb
->lsa
.sn
== LSA_MAXSEQNO
))
713 struct l_lsr_head ll
;
715 ll
.lsh
.id
= lsadb
->lsa
.id
;
716 ll
.lsh
.rt
= lsadb
->lsa
.rt
;
717 ll
.lsh
.type
= lsadb
->lsa
.type
;
718 add_tail(&l
, NODE
& ll
);
719 ospf_lsupd_send_list(n
, &l
);
723 /* Send direct LSAs */
724 ospf_lsack_send(n
, ACKL_DIRECT
);
726 if (sendreq
&& (n
->state
== NEIGHBOR_LOADING
))
728 ospf_lsreq_send(n
); /* Ask for another part of neighbor's database */
733 ospf_lsupd_flush_nlsa(struct proto_ospf
*po
, struct top_hash_entry
*en
)
735 struct ospf_lsa_header
*lsa
= &en
->lsa
;
736 struct proto
*p
= &po
->proto
;
738 lsa
->age
= LSA_MAXAGE
;
739 lsa
->sn
= LSA_MAXSEQNO
;
740 lsasum_calculate(lsa
, en
->lsa_body
);
741 OSPF_TRACE(D_EVENTS
, "Premature aging self originated lsa!");
742 OSPF_TRACE(D_EVENTS
, "Type: %04x, Id: %R, Rt: %R", lsa
->type
, lsa
->id
, lsa
->rt
);
743 ospf_lsupd_flood(po
, NULL
, NULL
, lsa
, en
->domain
, 0);