1*5b133f3fSguenther /* $OpenBSD: rde_lsdb.c,v 1.48 2023/03/08 04:43:14 guenther Exp $ */
2a1a4e97bSnorby
3a1a4e97bSnorby /*
4a1a4e97bSnorby * Copyright (c) 2004, 2005 Claudio Jeker <claudio@openbsd.org>
5a1a4e97bSnorby *
6a1a4e97bSnorby * Permission to use, copy, modify, and distribute this software for any
7a1a4e97bSnorby * purpose with or without fee is hereby granted, provided that the above
8a1a4e97bSnorby * copyright notice and this permission notice appear in all copies.
9a1a4e97bSnorby *
10a1a4e97bSnorby * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11a1a4e97bSnorby * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12a1a4e97bSnorby * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13a1a4e97bSnorby * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14a1a4e97bSnorby * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15a1a4e97bSnorby * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16a1a4e97bSnorby * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17a1a4e97bSnorby */
18a1a4e97bSnorby
19a1a4e97bSnorby #include <sys/types.h>
20a1a4e97bSnorby #include <sys/tree.h>
21a1a4e97bSnorby #include <stdlib.h>
22a1a4e97bSnorby #include <string.h>
23a1a4e97bSnorby #include <unistd.h>
24a1a4e97bSnorby
25a1a4e97bSnorby #include "ospf6.h"
26a1a4e97bSnorby #include "ospf6d.h"
27a1a4e97bSnorby #include "rde.h"
28a1a4e97bSnorby #include "log.h"
29a1a4e97bSnorby
30db8ae7dcSstsp struct vertex *vertex_get(struct lsa *, struct rde_nbr *, struct lsa_tree *);
31a1a4e97bSnorby
324139c605Sclaudio int lsa_link_check(struct lsa *, u_int16_t);
334139c605Sclaudio int lsa_intra_a_pref_check(struct lsa *, u_int16_t);
3468681923Sclaudio int lsa_asext_check(struct lsa *, u_int16_t);
35a1a4e97bSnorby void lsa_timeout(int, short, void *);
36a1a4e97bSnorby void lsa_refresh(struct vertex *);
37a1a4e97bSnorby int lsa_equal(struct lsa *, struct lsa *);
388cd84907Sclaudio int lsa_get_prefix(void *, u_int16_t, struct rt_prefix *);
39a1a4e97bSnorby
RB_GENERATE(lsa_tree,vertex,entry,lsa_compare)40a1a4e97bSnorby RB_GENERATE(lsa_tree, vertex, entry, lsa_compare)
41a1a4e97bSnorby
42a1a4e97bSnorby void
43a1a4e97bSnorby lsa_init(struct lsa_tree *t)
44a1a4e97bSnorby {
45a1a4e97bSnorby RB_INIT(t);
46a1a4e97bSnorby }
47a1a4e97bSnorby
48a1a4e97bSnorby int
lsa_compare(struct vertex * a,struct vertex * b)49a1a4e97bSnorby lsa_compare(struct vertex *a, struct vertex *b)
50a1a4e97bSnorby {
51a1a4e97bSnorby if (a->type < b->type)
52a1a4e97bSnorby return (-1);
53a1a4e97bSnorby if (a->type > b->type)
54a1a4e97bSnorby return (1);
55a1a4e97bSnorby if (a->adv_rtr < b->adv_rtr)
56a1a4e97bSnorby return (-1);
57a1a4e97bSnorby if (a->adv_rtr > b->adv_rtr)
58a1a4e97bSnorby return (1);
599c28f3bfSclaudio if (a->ls_id < b->ls_id)
609c28f3bfSclaudio return (-1);
619c28f3bfSclaudio if (a->ls_id > b->ls_id)
629c28f3bfSclaudio return (1);
63a1a4e97bSnorby return (0);
64a1a4e97bSnorby }
65a1a4e97bSnorby
66a1a4e97bSnorby
67a1a4e97bSnorby struct vertex *
vertex_get(struct lsa * lsa,struct rde_nbr * nbr,struct lsa_tree * tree)68db8ae7dcSstsp vertex_get(struct lsa *lsa, struct rde_nbr *nbr, struct lsa_tree *tree)
69a1a4e97bSnorby {
70a1a4e97bSnorby struct vertex *v;
71a1a4e97bSnorby struct timespec tp;
72a1a4e97bSnorby
73a1a4e97bSnorby if ((v = calloc(1, sizeof(struct vertex))) == NULL)
74a1a4e97bSnorby fatal(NULL);
75a1a4e97bSnorby TAILQ_INIT(&v->nexthop);
76a1a4e97bSnorby v->area = nbr->area;
77a1a4e97bSnorby v->peerid = nbr->peerid;
78a1a4e97bSnorby v->lsa = lsa;
79a1a4e97bSnorby clock_gettime(CLOCK_MONOTONIC, &tp);
80a1a4e97bSnorby v->changed = v->stamp = tp.tv_sec;
81a1a4e97bSnorby v->cost = LS_INFINITY;
82a1a4e97bSnorby v->ls_id = ntohl(lsa->hdr.ls_id);
83a1a4e97bSnorby v->adv_rtr = ntohl(lsa->hdr.adv_rtr);
8431505e9fSclaudio v->type = ntohs(lsa->hdr.type);
85db8ae7dcSstsp v->lsa_tree = tree;
86a1a4e97bSnorby
87a1a4e97bSnorby if (!nbr->self)
88a1a4e97bSnorby v->flooded = 1; /* XXX fix me */
89a1a4e97bSnorby v->self = nbr->self;
90a1a4e97bSnorby
91a1a4e97bSnorby evtimer_set(&v->ev, lsa_timeout, v);
92a1a4e97bSnorby
93a1a4e97bSnorby return (v);
94a1a4e97bSnorby }
95a1a4e97bSnorby
96a1a4e97bSnorby void
vertex_free(struct vertex * v)97a1a4e97bSnorby vertex_free(struct vertex *v)
98a1a4e97bSnorby {
99db8ae7dcSstsp RB_REMOVE(lsa_tree, v->lsa_tree, v);
10085be3f1aSdenis
101a1a4e97bSnorby (void)evtimer_del(&v->ev);
10285be3f1aSdenis vertex_nexthop_clear(v);
103a1a4e97bSnorby free(v->lsa);
104a1a4e97bSnorby free(v);
105a1a4e97bSnorby }
106a1a4e97bSnorby
10785be3f1aSdenis void
vertex_nexthop_clear(struct vertex * v)10885be3f1aSdenis vertex_nexthop_clear(struct vertex *v)
10985be3f1aSdenis {
11085be3f1aSdenis struct v_nexthop *vn;
11185be3f1aSdenis
11285be3f1aSdenis while ((vn = TAILQ_FIRST(&v->nexthop))) {
11385be3f1aSdenis TAILQ_REMOVE(&v->nexthop, vn, entry);
11485be3f1aSdenis free(vn);
11585be3f1aSdenis }
11685be3f1aSdenis }
11785be3f1aSdenis
11885be3f1aSdenis void
vertex_nexthop_add(struct vertex * dst,struct vertex * parent,const struct in6_addr * nexthop,u_int32_t ifindex)11985be3f1aSdenis vertex_nexthop_add(struct vertex *dst, struct vertex *parent,
12085be3f1aSdenis const struct in6_addr *nexthop, u_int32_t ifindex)
12185be3f1aSdenis {
12285be3f1aSdenis struct v_nexthop *vn;
12385be3f1aSdenis
12485be3f1aSdenis if ((vn = calloc(1, sizeof(*vn))) == NULL)
12585be3f1aSdenis fatal("vertex_nexthop_add");
12685be3f1aSdenis
12785be3f1aSdenis vn->prev = parent;
12885be3f1aSdenis if (nexthop)
12985be3f1aSdenis vn->nexthop = *nexthop;
13085be3f1aSdenis vn->ifindex = ifindex;
13185be3f1aSdenis
13285be3f1aSdenis TAILQ_INSERT_TAIL(&dst->nexthop, vn, entry);
13385be3f1aSdenis }
13485be3f1aSdenis
135a1a4e97bSnorby /* returns -1 if a is older, 1 if newer and 0 if equal to b */
136a1a4e97bSnorby int
lsa_newer(struct lsa_hdr * a,struct lsa_hdr * b)137a1a4e97bSnorby lsa_newer(struct lsa_hdr *a, struct lsa_hdr *b)
138a1a4e97bSnorby {
139a1a4e97bSnorby int32_t a32, b32;
140a1a4e97bSnorby u_int16_t a16, b16;
141a1a4e97bSnorby int i;
142a1a4e97bSnorby
143a1a4e97bSnorby if (a == NULL)
144a1a4e97bSnorby return (-1);
145a1a4e97bSnorby if (b == NULL)
146a1a4e97bSnorby return (1);
147a1a4e97bSnorby
148a1a4e97bSnorby /*
149a1a4e97bSnorby * The sequence number is defined as signed 32-bit integer,
150a1a4e97bSnorby * no idea how IETF came up with such a stupid idea.
151a1a4e97bSnorby */
152a1a4e97bSnorby a32 = (int32_t)ntohl(a->seq_num);
153a1a4e97bSnorby b32 = (int32_t)ntohl(b->seq_num);
154a1a4e97bSnorby
155a1a4e97bSnorby if (a32 > b32)
156a1a4e97bSnorby return (1);
157a1a4e97bSnorby if (a32 < b32)
158a1a4e97bSnorby return (-1);
159a1a4e97bSnorby
160a1a4e97bSnorby a16 = ntohs(a->ls_chksum);
161a1a4e97bSnorby b16 = ntohs(b->ls_chksum);
162a1a4e97bSnorby
163a1a4e97bSnorby if (a16 > b16)
164a1a4e97bSnorby return (1);
165a1a4e97bSnorby if (a16 < b16)
166a1a4e97bSnorby return (-1);
167a1a4e97bSnorby
168a1a4e97bSnorby a16 = ntohs(a->age);
169a1a4e97bSnorby b16 = ntohs(b->age);
170a1a4e97bSnorby
171a1a4e97bSnorby if (a16 >= MAX_AGE && b16 >= MAX_AGE)
172a1a4e97bSnorby return (0);
173a1a4e97bSnorby if (b16 >= MAX_AGE)
174a1a4e97bSnorby return (-1);
175a1a4e97bSnorby if (a16 >= MAX_AGE)
176a1a4e97bSnorby return (1);
177a1a4e97bSnorby
178a1a4e97bSnorby i = b16 - a16;
179a1a4e97bSnorby if (abs(i) > MAX_AGE_DIFF)
180a1a4e97bSnorby return (i > 0 ? 1 : -1);
181a1a4e97bSnorby
182a1a4e97bSnorby return (0);
183a1a4e97bSnorby }
184a1a4e97bSnorby
185a1a4e97bSnorby int
lsa_check(struct rde_nbr * nbr,struct lsa * lsa,u_int16_t len)186a1a4e97bSnorby lsa_check(struct rde_nbr *nbr, struct lsa *lsa, u_int16_t len)
187a1a4e97bSnorby {
188a1a4e97bSnorby u_int32_t metric;
189a1a4e97bSnorby
190a1a4e97bSnorby if (len < sizeof(lsa->hdr)) {
191a1a4e97bSnorby log_warnx("lsa_check: bad packet size");
192a1a4e97bSnorby return (0);
193a1a4e97bSnorby }
194a1a4e97bSnorby if (ntohs(lsa->hdr.len) != len) {
195b67f69b5Sdenis log_warnx("lsa_check: bad packet length");
196a1a4e97bSnorby return (0);
197a1a4e97bSnorby }
198a1a4e97bSnorby
199a1a4e97bSnorby if (iso_cksum(lsa, len, 0)) {
200a1a4e97bSnorby log_warnx("lsa_check: bad packet checksum");
201a1a4e97bSnorby return (0);
202a1a4e97bSnorby }
203a1a4e97bSnorby
204a1a4e97bSnorby /* invalid ages */
205a1a4e97bSnorby if ((ntohs(lsa->hdr.age) < 1 && !nbr->self) ||
206a1a4e97bSnorby ntohs(lsa->hdr.age) > MAX_AGE) {
207a1a4e97bSnorby log_warnx("lsa_check: bad age");
208a1a4e97bSnorby return (0);
209a1a4e97bSnorby }
210a1a4e97bSnorby
211a1a4e97bSnorby /* invalid sequence number */
212a1a4e97bSnorby if (ntohl(lsa->hdr.seq_num) == RESV_SEQ_NUM) {
21358a7a39dSsthen log_warnx("lsa_check: bad seq num");
214a1a4e97bSnorby return (0);
215a1a4e97bSnorby }
216a1a4e97bSnorby
21719f3adaeSnorby switch (ntohs(lsa->hdr.type)) {
21819f3adaeSnorby case LSA_TYPE_LINK:
2194139c605Sclaudio if (!lsa_link_check(lsa, len))
2204139c605Sclaudio return (0);
22119f3adaeSnorby break;
222a1a4e97bSnorby case LSA_TYPE_ROUTER:
2234139c605Sclaudio if (len < sizeof(lsa->hdr) + sizeof(struct lsa_rtr)) {
2244139c605Sclaudio log_warnx("lsa_check: bad LSA rtr packet");
225a1a4e97bSnorby return (0);
2264139c605Sclaudio }
2274139c605Sclaudio len -= sizeof(lsa->hdr) + sizeof(struct lsa_rtr);
2284139c605Sclaudio if (len % sizeof(struct lsa_rtr_link)) {
2294139c605Sclaudio log_warnx("lsa_check: bad LSA rtr packet");
2304139c605Sclaudio return (0);
2314139c605Sclaudio }
232a1a4e97bSnorby break;
233a1a4e97bSnorby case LSA_TYPE_NETWORK:
234a1a4e97bSnorby if ((len % sizeof(u_int32_t)) ||
235a1a4e97bSnorby len < sizeof(lsa->hdr) + sizeof(u_int32_t)) {
23647cb1ae0Sdenis log_warnx("lsa_check: bad LSA network packet");
237a1a4e97bSnorby return (0);
238a1a4e97bSnorby }
239a1a4e97bSnorby break;
24019f3adaeSnorby case LSA_TYPE_INTER_A_PREFIX:
2414139c605Sclaudio if (len < sizeof(lsa->hdr) + sizeof(lsa->data.pref_sum)) {
2424139c605Sclaudio log_warnx("lsa_check: bad LSA prefix summary packet");
243a1a4e97bSnorby return (0);
244a1a4e97bSnorby }
2454139c605Sclaudio metric = ntohl(lsa->data.pref_sum.metric);
2464139c605Sclaudio if (metric & ~LSA_METRIC_MASK) {
247b67f69b5Sdenis log_warnx("lsa_check: bad LSA prefix summary metric");
2484139c605Sclaudio return (0);
2494139c605Sclaudio }
2504139c605Sclaudio if (lsa_get_prefix(((char *)lsa) + sizeof(lsa->hdr) +
2514139c605Sclaudio sizeof(lsa->data.pref_sum),
2524139c605Sclaudio len - sizeof(lsa->hdr) + sizeof(lsa->data.pref_sum),
2534139c605Sclaudio NULL) == -1) {
2544139c605Sclaudio log_warnx("lsa_check: "
2554139c605Sclaudio "invalid LSA prefix summary packet");
2564139c605Sclaudio return (0);
2574139c605Sclaudio }
2584139c605Sclaudio break;
2594139c605Sclaudio case LSA_TYPE_INTER_A_ROUTER:
2604139c605Sclaudio if (len < sizeof(lsa->hdr) + sizeof(lsa->data.rtr_sum)) {
2614139c605Sclaudio log_warnx("lsa_check: bad LSA router summary packet");
2624139c605Sclaudio return (0);
2634139c605Sclaudio }
2644139c605Sclaudio metric = ntohl(lsa->data.rtr_sum.metric);
265a1a4e97bSnorby if (metric & ~LSA_METRIC_MASK) {
266b67f69b5Sdenis log_warnx("lsa_check: bad LSA router summary metric");
267a1a4e97bSnorby return (0);
268a1a4e97bSnorby }
269a1a4e97bSnorby break;
27019f3adaeSnorby case LSA_TYPE_INTRA_A_PREFIX:
2714139c605Sclaudio if (!lsa_intra_a_pref_check(lsa, len))
2724139c605Sclaudio return (0);
27319f3adaeSnorby break;
274a1a4e97bSnorby case LSA_TYPE_EXTERNAL:
275a1a4e97bSnorby /* AS-external-LSA are silently discarded in stub areas */
2764ae44e47Sclaudio if (nbr->area->stub)
277a1a4e97bSnorby return (0);
27868681923Sclaudio if (!lsa_asext_check(lsa, len))
27968681923Sclaudio return (0);
280a1a4e97bSnorby break;
281a1a4e97bSnorby default:
2824139c605Sclaudio log_warnx("lsa_check: unknown type %x", ntohs(lsa->hdr.type));
283a1a4e97bSnorby return (0);
284a1a4e97bSnorby }
285a1a4e97bSnorby
286a1a4e97bSnorby /* MaxAge handling */
2874ae44e47Sclaudio if (lsa->hdr.age == htons(MAX_AGE) && !nbr->self && lsa_find(nbr->iface,
288a1a4e97bSnorby lsa->hdr.type, lsa->hdr.ls_id, lsa->hdr.adv_rtr) == NULL &&
2894ae44e47Sclaudio !rde_nbr_loading(nbr->area)) {
290a1a4e97bSnorby /*
291a1a4e97bSnorby * if no neighbor in state Exchange or Loading
292a1a4e97bSnorby * ack LSA but don't add it. Needs to be a direct ack.
293a1a4e97bSnorby */
294a1a4e97bSnorby rde_imsg_compose_ospfe(IMSG_LS_ACK, nbr->peerid, 0, &lsa->hdr,
295a1a4e97bSnorby sizeof(struct lsa_hdr));
296a1a4e97bSnorby return (0);
297a1a4e97bSnorby }
298a1a4e97bSnorby
299a1a4e97bSnorby return (1);
300a1a4e97bSnorby }
301a1a4e97bSnorby
302a1a4e97bSnorby int
lsa_link_check(struct lsa * lsa,u_int16_t len)3034139c605Sclaudio lsa_link_check(struct lsa *lsa, u_int16_t len)
304a1a4e97bSnorby {
305a1a4e97bSnorby char *buf = (char *)lsa;
3064139c605Sclaudio struct lsa_link *llink;
3074139c605Sclaudio u_int32_t i, off, npref;
3084139c605Sclaudio int rv;
309a1a4e97bSnorby
3104139c605Sclaudio llink = (struct lsa_link *)(buf + sizeof(lsa->hdr));
3114139c605Sclaudio off = sizeof(lsa->hdr) + sizeof(struct lsa_link);
312a1a4e97bSnorby if (off > len) {
3134139c605Sclaudio log_warnx("lsa_link_check: invalid LSA link packet, "
3144139c605Sclaudio "short header");
315a1a4e97bSnorby return (0);
316a1a4e97bSnorby }
317a1a4e97bSnorby
3184139c605Sclaudio len -= off;
3194139c605Sclaudio npref = ntohl(llink->numprefix);
32025e30039Snorby
3214139c605Sclaudio for (i = 0; i < npref; i++) {
3224139c605Sclaudio rv = lsa_get_prefix(buf + off, len, NULL);
3234139c605Sclaudio if (rv == -1) {
3244139c605Sclaudio log_warnx("lsa_link_check: invalid LSA link packet");
3254139c605Sclaudio return (0);
3264139c605Sclaudio }
3274139c605Sclaudio off += rv;
3284139c605Sclaudio len -= rv;
3294139c605Sclaudio }
33025e30039Snorby
3314139c605Sclaudio return (1);
3324139c605Sclaudio }
3334139c605Sclaudio
3344139c605Sclaudio int
lsa_intra_a_pref_check(struct lsa * lsa,u_int16_t len)3354139c605Sclaudio lsa_intra_a_pref_check(struct lsa *lsa, u_int16_t len)
3364139c605Sclaudio {
3374139c605Sclaudio char *buf = (char *)lsa;
3384139c605Sclaudio struct lsa_intra_prefix *iap;
3394139c605Sclaudio u_int32_t i, off, npref;
3404139c605Sclaudio int rv;
3414139c605Sclaudio
3424139c605Sclaudio iap = (struct lsa_intra_prefix *)(buf + sizeof(lsa->hdr));
3434139c605Sclaudio off = sizeof(lsa->hdr) + sizeof(struct lsa_intra_prefix);
344a1a4e97bSnorby if (off > len) {
3454139c605Sclaudio log_warnx("lsa_intra_a_pref_check: "
3464139c605Sclaudio "invalid LSA intra area prefix packet, short header");
347a1a4e97bSnorby return (0);
348a1a4e97bSnorby }
349a1a4e97bSnorby
3504139c605Sclaudio len -= off;
351bd4e879fSstsp npref = ntohs(iap->numprefix);
3524139c605Sclaudio
3534139c605Sclaudio for (i = 0; i < npref; i++) {
3544139c605Sclaudio rv = lsa_get_prefix(buf + off, len, NULL);
3554139c605Sclaudio if (rv == -1) {
3564139c605Sclaudio log_warnx("lsa_intra_a_pref_check: "
3574139c605Sclaudio "invalid LSA intra area prefix packet");
358a1a4e97bSnorby return (0);
359a1a4e97bSnorby }
3604139c605Sclaudio off += rv;
3614139c605Sclaudio len -= rv;
3624139c605Sclaudio }
3634139c605Sclaudio
364a1a4e97bSnorby return (1);
365a1a4e97bSnorby }
366a1a4e97bSnorby
367a1a4e97bSnorby int
lsa_asext_check(struct lsa * lsa,u_int16_t len)36868681923Sclaudio lsa_asext_check(struct lsa *lsa, u_int16_t len)
36968681923Sclaudio {
37068681923Sclaudio char *buf = (char *)lsa;
37168681923Sclaudio struct lsa_asext *asext;
37268681923Sclaudio struct in6_addr fw_addr;
37368681923Sclaudio u_int32_t metric;
37468681923Sclaudio u_int16_t ref_ls_type;
37568681923Sclaudio int rv;
37668681923Sclaudio u_int16_t total_len;
37768681923Sclaudio
37868681923Sclaudio asext = (struct lsa_asext *)(buf + sizeof(lsa->hdr));
37968681923Sclaudio
38068681923Sclaudio if ((len % sizeof(u_int32_t)) ||
38168681923Sclaudio len < sizeof(lsa->hdr) + sizeof(*asext)) {
382b67f69b5Sdenis log_warnx("lsa_asext_check: bad LSA as-external packet size");
38368681923Sclaudio return (0);
38468681923Sclaudio }
38568681923Sclaudio
38668681923Sclaudio total_len = sizeof(lsa->hdr) + sizeof(*asext);
38768681923Sclaudio rv = lsa_get_prefix(&asext->prefix, len, NULL);
38868681923Sclaudio if (rv == -1) {
38968681923Sclaudio log_warnx("lsa_asext_check: bad LSA as-external packet");
39068681923Sclaudio return (0);
39168681923Sclaudio }
39268681923Sclaudio total_len += rv - sizeof(struct lsa_prefix);
39368681923Sclaudio
39468681923Sclaudio metric = ntohl(asext->metric);
39568681923Sclaudio if (metric & LSA_ASEXT_F_FLAG) {
39668681923Sclaudio if (total_len + sizeof(fw_addr) < len) {
39768681923Sclaudio bcopy(buf + total_len, &fw_addr, sizeof(fw_addr));
39868681923Sclaudio if (IN6_IS_ADDR_UNSPECIFIED(&fw_addr) ||
39968681923Sclaudio IN6_IS_ADDR_LINKLOCAL(&fw_addr)) {
40068681923Sclaudio log_warnx("lsa_asext_check: bad LSA "
40168681923Sclaudio "as-external forwarding address");
40268681923Sclaudio return (0);
40368681923Sclaudio }
40468681923Sclaudio }
40568681923Sclaudio total_len += sizeof(fw_addr);
40668681923Sclaudio }
40768681923Sclaudio
40868681923Sclaudio if (metric & LSA_ASEXT_T_FLAG)
40968681923Sclaudio total_len += sizeof(u_int32_t);
41068681923Sclaudio
41168681923Sclaudio ref_ls_type = asext->prefix.metric;
41268681923Sclaudio if (ref_ls_type != 0)
41368681923Sclaudio total_len += sizeof(u_int32_t);
41468681923Sclaudio
41568681923Sclaudio if (len != total_len) {
41668681923Sclaudio log_warnx("lsa_asext_check: bad LSA as-external length");
41768681923Sclaudio return (0);
41868681923Sclaudio }
41968681923Sclaudio
42068681923Sclaudio return (1);
42168681923Sclaudio }
42268681923Sclaudio
42368681923Sclaudio int
lsa_self(struct rde_nbr * nbr,struct lsa * lsa,struct vertex * v)424b67f69b5Sdenis lsa_self(struct rde_nbr *nbr, struct lsa *lsa, struct vertex *v)
425a1a4e97bSnorby {
426b67f69b5Sdenis struct lsa *dummy;
427d5af5c98Sstsp
428b67f69b5Sdenis if (nbr->self)
429b67f69b5Sdenis return (0);
43060a9bb12Sstsp
431b67f69b5Sdenis if (rde_router_id() != lsa->hdr.adv_rtr)
432b67f69b5Sdenis return (0);
433b67f69b5Sdenis
434b67f69b5Sdenis if (v == NULL) {
435b67f69b5Sdenis /* LSA is no longer announced, remove by premature aging.
43660a9bb12Sstsp * The LSA may not be altered because the caller may still
43760a9bb12Sstsp * use it, so a copy needs to be added to the LSDB.
43860a9bb12Sstsp * The copy will be reflooded via the default timeout handler.
43960a9bb12Sstsp */
440b67f69b5Sdenis if ((dummy = malloc(ntohs(lsa->hdr.len))) == NULL)
441b67f69b5Sdenis fatal("lsa_self");
442b67f69b5Sdenis memcpy(dummy, lsa, ntohs(lsa->hdr.len));
443b67f69b5Sdenis dummy->hdr.age = htons(MAX_AGE);
444b67f69b5Sdenis /*
445b67f69b5Sdenis * The clue is that by using the remote nbr as originator
446b67f69b5Sdenis * the dummy LSA will be reflooded via the default timeout
447b67f69b5Sdenis * handler.
448b67f69b5Sdenis */
449b67f69b5Sdenis (void)lsa_add(rde_nbr_self(nbr->area), dummy);
450b67f69b5Sdenis return (1);
45160a9bb12Sstsp }
45260a9bb12Sstsp
45360a9bb12Sstsp /*
454b67f69b5Sdenis * LSA is still originated, just reflood it. But we need to create
455b67f69b5Sdenis * a new instance by setting the LSA sequence number equal to the
456b67f69b5Sdenis * one of new and calling lsa_refresh(). Flooding will be done by the
457b67f69b5Sdenis * caller.
458a1a4e97bSnorby */
459b67f69b5Sdenis v->lsa->hdr.seq_num = lsa->hdr.seq_num;
460a1a4e97bSnorby lsa_refresh(v);
461b67f69b5Sdenis return (1);
462a1a4e97bSnorby }
463a1a4e97bSnorby
464a1a4e97bSnorby int
lsa_add(struct rde_nbr * nbr,struct lsa * lsa)465a1a4e97bSnorby lsa_add(struct rde_nbr *nbr, struct lsa *lsa)
466a1a4e97bSnorby {
467a1a4e97bSnorby struct lsa_tree *tree;
468a1a4e97bSnorby struct vertex *new, *old;
469a1a4e97bSnorby struct timeval tv, now, res;
470dc6b949cSjan int update = 1;
471a1a4e97bSnorby
4724139c605Sclaudio if (LSA_IS_SCOPE_AS(ntohs(lsa->hdr.type)))
473a1a4e97bSnorby tree = &asext_tree;
4744139c605Sclaudio else if (LSA_IS_SCOPE_AREA(ntohs(lsa->hdr.type)))
475a1a4e97bSnorby tree = &nbr->area->lsa_tree;
4764139c605Sclaudio else if (LSA_IS_SCOPE_LLOCAL(ntohs(lsa->hdr.type)))
4774139c605Sclaudio tree = &nbr->iface->lsa_tree;
4784139c605Sclaudio else
479b67f69b5Sdenis fatalx("%s: unknown scope type", __func__);
480a1a4e97bSnorby
481db8ae7dcSstsp new = vertex_get(lsa, nbr, tree);
482a1a4e97bSnorby old = RB_INSERT(lsa_tree, tree, new);
483a1a4e97bSnorby
484a1a4e97bSnorby if (old != NULL) {
485a1a4e97bSnorby if (old->deleted && evtimer_pending(&old->ev, &tv)) {
486a1a4e97bSnorby /* new update added before hold time expired */
487a1a4e97bSnorby gettimeofday(&now, NULL);
488a1a4e97bSnorby timersub(&tv, &now, &res);
489a1a4e97bSnorby
490a1a4e97bSnorby /* remove old LSA and insert new LSA with delay */
491a1a4e97bSnorby vertex_free(old);
492a1a4e97bSnorby RB_INSERT(lsa_tree, tree, new);
493a1a4e97bSnorby new->deleted = 1;
494a1a4e97bSnorby
495a1a4e97bSnorby if (evtimer_add(&new->ev, &res) != 0)
496a1a4e97bSnorby fatal("lsa_add");
497a1a4e97bSnorby return (1);
498a1a4e97bSnorby }
499dc6b949cSjan if (lsa_equal(new->lsa, old->lsa))
500dc6b949cSjan update = 0;
501a1a4e97bSnorby vertex_free(old);
502a1a4e97bSnorby RB_INSERT(lsa_tree, tree, new);
503dc6b949cSjan }
504dc6b949cSjan
505dc6b949cSjan if (update) {
5068e1674f3Sbluhm if (ntohs(lsa->hdr.type) == LSA_TYPE_LINK)
5078e1674f3Sbluhm orig_intra_area_prefix_lsas(nbr->area);
50831505e9fSclaudio if (ntohs(lsa->hdr.type) != LSA_TYPE_EXTERNAL)
509a1a4e97bSnorby nbr->area->dirty = 1;
510a1a4e97bSnorby start_spf_timer();
511a1a4e97bSnorby }
512a1a4e97bSnorby
513a1a4e97bSnorby /* timeout handling either MAX_AGE or LS_REFRESH_TIME */
514a1a4e97bSnorby timerclear(&tv);
515a1a4e97bSnorby
516a1a4e97bSnorby if (nbr->self && ntohs(new->lsa->hdr.age) == DEFAULT_AGE)
517a1a4e97bSnorby tv.tv_sec = LS_REFRESH_TIME;
518a1a4e97bSnorby else
519a1a4e97bSnorby tv.tv_sec = MAX_AGE - ntohs(new->lsa->hdr.age);
520a1a4e97bSnorby
521a1a4e97bSnorby if (evtimer_add(&new->ev, &tv) != 0)
522b67f69b5Sdenis fatal("lsa_add: evtimer_add()");
523a1a4e97bSnorby return (0);
524a1a4e97bSnorby }
525a1a4e97bSnorby
526a1a4e97bSnorby void
lsa_del(struct rde_nbr * nbr,struct lsa_hdr * lsa)527a1a4e97bSnorby lsa_del(struct rde_nbr *nbr, struct lsa_hdr *lsa)
528a1a4e97bSnorby {
529a1a4e97bSnorby struct vertex *v;
530a1a4e97bSnorby struct timeval tv;
531a1a4e97bSnorby
5324ae44e47Sclaudio v = lsa_find(nbr->iface, lsa->type, lsa->ls_id, lsa->adv_rtr);
533a1a4e97bSnorby if (v == NULL)
534a1a4e97bSnorby return;
535a1a4e97bSnorby
536a1a4e97bSnorby v->deleted = 1;
537a1a4e97bSnorby /* hold time to make sure that a new lsa is not added premature */
538a1a4e97bSnorby timerclear(&tv);
539a1a4e97bSnorby tv.tv_sec = MIN_LS_INTERVAL;
540a1a4e97bSnorby if (evtimer_add(&v->ev, &tv) == -1)
541a1a4e97bSnorby fatal("lsa_del");
542a1a4e97bSnorby }
543a1a4e97bSnorby
544a1a4e97bSnorby void
lsa_age(struct vertex * v)545a1a4e97bSnorby lsa_age(struct vertex *v)
546a1a4e97bSnorby {
547a1a4e97bSnorby struct timespec tp;
548a1a4e97bSnorby time_t now;
549a1a4e97bSnorby int d;
550a1a4e97bSnorby u_int16_t age;
551a1a4e97bSnorby
552a1a4e97bSnorby clock_gettime(CLOCK_MONOTONIC, &tp);
553a1a4e97bSnorby now = tp.tv_sec;
554a1a4e97bSnorby
555a1a4e97bSnorby d = now - v->stamp;
556a1a4e97bSnorby /* set stamp so that at least new calls work */
557a1a4e97bSnorby v->stamp = now;
558a1a4e97bSnorby
559a1a4e97bSnorby if (d < 0) {
560a1a4e97bSnorby log_warnx("lsa_age: time went backwards");
561a1a4e97bSnorby return;
562a1a4e97bSnorby }
563a1a4e97bSnorby
564a1a4e97bSnorby age = ntohs(v->lsa->hdr.age);
565a1a4e97bSnorby if (age + d > MAX_AGE)
566a1a4e97bSnorby age = MAX_AGE;
567a1a4e97bSnorby else
568a1a4e97bSnorby age += d;
569a1a4e97bSnorby
570a1a4e97bSnorby v->lsa->hdr.age = htons(age);
571a1a4e97bSnorby }
572a1a4e97bSnorby
573a1a4e97bSnorby struct vertex *
lsa_find(struct iface * iface,u_int16_t type,u_int32_t ls_id,u_int32_t adv_rtr)5744ae44e47Sclaudio lsa_find(struct iface *iface, u_int16_t type, u_int32_t ls_id,
5754ae44e47Sclaudio u_int32_t adv_rtr)
576a1a4e97bSnorby {
577a1a4e97bSnorby struct lsa_tree *tree;
578a1a4e97bSnorby
579eff6b354Sstsp if (LSA_IS_SCOPE_AS(ntohs(type)))
580a1a4e97bSnorby tree = &asext_tree;
581d18517d2Sdenis else if (LSA_IS_SCOPE_AREA(ntohs(type)))
58277fbfa19Sdenis tree = &iface->area->lsa_tree;
583d18517d2Sdenis else if (LSA_IS_SCOPE_LLOCAL(ntohs(type)))
5844ae44e47Sclaudio tree = &iface->lsa_tree;
585a1a4e97bSnorby else
5864ae44e47Sclaudio fatalx("unknown scope type");
587a1a4e97bSnorby
588eff6b354Sstsp return lsa_find_tree(tree, type, ls_id, adv_rtr);
589eff6b354Sstsp
590eff6b354Sstsp }
591eff6b354Sstsp
592eff6b354Sstsp struct vertex *
lsa_find_tree(struct lsa_tree * tree,u_int16_t type,u_int32_t ls_id,u_int32_t adv_rtr)593eff6b354Sstsp lsa_find_tree(struct lsa_tree *tree, u_int16_t type, u_int32_t ls_id,
594eff6b354Sstsp u_int32_t adv_rtr)
595eff6b354Sstsp {
596eff6b354Sstsp struct vertex key;
597eff6b354Sstsp struct vertex *v;
598eff6b354Sstsp
599eff6b354Sstsp key.ls_id = ntohl(ls_id);
600eff6b354Sstsp key.adv_rtr = ntohl(adv_rtr);
601eff6b354Sstsp key.type = ntohs(type);
602eff6b354Sstsp
603a1a4e97bSnorby v = RB_FIND(lsa_tree, tree, &key);
604a1a4e97bSnorby
605a1a4e97bSnorby /* LSA that are deleted are not findable */
606a1a4e97bSnorby if (v && v->deleted)
607a1a4e97bSnorby return (NULL);
608a1a4e97bSnorby
609a1a4e97bSnorby if (v)
610a1a4e97bSnorby lsa_age(v);
611a1a4e97bSnorby
612a1a4e97bSnorby return (v);
613a1a4e97bSnorby }
614a1a4e97bSnorby
615a1a4e97bSnorby struct vertex *
lsa_find_rtr(struct area * area,u_int32_t rtr_id)616f1ef0307Sstsp lsa_find_rtr(struct area *area, u_int32_t rtr_id)
617f1ef0307Sstsp {
618c78f753bSstsp return lsa_find_rtr_frag(area, rtr_id, 0);
619c78f753bSstsp }
620c78f753bSstsp
621c78f753bSstsp struct vertex *
lsa_find_rtr_frag(struct area * area,u_int32_t rtr_id,unsigned int n)622c78f753bSstsp lsa_find_rtr_frag(struct area *area, u_int32_t rtr_id, unsigned int n)
623c78f753bSstsp {
624f1ef0307Sstsp struct vertex *v;
625c78f753bSstsp struct vertex key;
626c78f753bSstsp unsigned int i;
627f1ef0307Sstsp
628c78f753bSstsp key.ls_id = 0;
629c78f753bSstsp key.adv_rtr = ntohl(rtr_id);
630c78f753bSstsp key.type = LSA_TYPE_ROUTER;
631f1ef0307Sstsp
632c78f753bSstsp i = 0;
633c78f753bSstsp v = RB_NFIND(lsa_tree, &area->lsa_tree, &key);
634c78f753bSstsp while (v) {
635c78f753bSstsp if (v->type != LSA_TYPE_ROUTER ||
636c78f753bSstsp v->adv_rtr != ntohl(rtr_id)) {
637c78f753bSstsp /* no more interesting LSAs */
638c78f753bSstsp v = NULL;
639c78f753bSstsp break;
640f1ef0307Sstsp }
641c78f753bSstsp if (!v->deleted) {
642c78f753bSstsp if (i >= n)
643c78f753bSstsp break;
644c78f753bSstsp i++;
645c78f753bSstsp }
646c78f753bSstsp v = RB_NEXT(lsa_tree, &area->lsa_tree, v);
647f1ef0307Sstsp }
648f1ef0307Sstsp
649c78f753bSstsp if (v) {
650c78f753bSstsp if (i == n)
651c78f753bSstsp lsa_age(v);
652c78f753bSstsp else
653c78f753bSstsp v = NULL;
654c78f753bSstsp }
655f1ef0307Sstsp
656c78f753bSstsp return (v);
657f1ef0307Sstsp }
658f1ef0307Sstsp
659e0dd50a7Sclaudio u_int32_t
lsa_find_lsid(struct lsa_tree * tree,int (* cmp)(struct lsa *,struct lsa *),struct lsa * lsa)660b67f69b5Sdenis lsa_find_lsid(struct lsa_tree *tree, int (*cmp)(struct lsa *, struct lsa *),
661b67f69b5Sdenis struct lsa *lsa)
662e0dd50a7Sclaudio {
663e0dd50a7Sclaudio #define MIN(x, y) ((x) < (y) ? (x) : (y))
664e0dd50a7Sclaudio struct vertex *v;
665e0dd50a7Sclaudio struct vertex key;
666e0dd50a7Sclaudio u_int32_t min, cur;
667e0dd50a7Sclaudio
668e0dd50a7Sclaudio key.ls_id = 0;
669b67f69b5Sdenis key.adv_rtr = ntohl(lsa->hdr.adv_rtr);
670b67f69b5Sdenis key.type = ntohs(lsa->hdr.type);
671e0dd50a7Sclaudio
672e0dd50a7Sclaudio cur = 0;
673e0dd50a7Sclaudio min = 0xffffffffU;
674e0dd50a7Sclaudio v = RB_NFIND(lsa_tree, tree, &key);
675e0dd50a7Sclaudio while (v) {
676e0dd50a7Sclaudio if (v->type != key.type ||
677e0dd50a7Sclaudio v->adv_rtr != key.adv_rtr) {
678e0dd50a7Sclaudio /* no more interesting LSAs */
679e0dd50a7Sclaudio min = MIN(min, cur + 1);
680e0dd50a7Sclaudio return (htonl(min));
681e0dd50a7Sclaudio }
682e0dd50a7Sclaudio if (cmp(lsa, v->lsa) == 0) {
683e0dd50a7Sclaudio /* match, return this ls_id */
684e0dd50a7Sclaudio return (htonl(v->ls_id));
685e0dd50a7Sclaudio }
686e0dd50a7Sclaudio if (v->ls_id > cur + 1)
687e0dd50a7Sclaudio min = cur + 1;
688e0dd50a7Sclaudio cur = v->ls_id;
689e0dd50a7Sclaudio if (cur + 1 < cur)
690e0dd50a7Sclaudio fatalx("King Bula sez: somebody got to many LSA");
691e0dd50a7Sclaudio v = RB_NEXT(lsa_tree, tree, v);
692e0dd50a7Sclaudio }
693e0dd50a7Sclaudio min = MIN(min, cur + 1);
694e0dd50a7Sclaudio return (htonl(min));
695e0dd50a7Sclaudio #undef MIN
696e0dd50a7Sclaudio }
697e0dd50a7Sclaudio
698a1a4e97bSnorby u_int16_t
lsa_num_links(struct vertex * v)699a1a4e97bSnorby lsa_num_links(struct vertex *v)
700a1a4e97bSnorby {
701c78f753bSstsp unsigned int n = 1;
702c78f753bSstsp u_int16_t nlinks = 0;
703c78f753bSstsp
704a1a4e97bSnorby switch (v->type) {
705a1a4e97bSnorby case LSA_TYPE_ROUTER:
706c78f753bSstsp do {
707c78f753bSstsp nlinks += ((ntohs(v->lsa->hdr.len) -
708c78f753bSstsp sizeof(struct lsa_hdr) - sizeof(struct lsa_rtr)) /
709c78f753bSstsp sizeof(struct lsa_rtr_link));
710c78f753bSstsp v = lsa_find_rtr_frag(v->area, htonl(v->adv_rtr), n++);
711c78f753bSstsp } while (v);
712c78f753bSstsp return nlinks;
713a1a4e97bSnorby case LSA_TYPE_NETWORK:
7141393dc49Sstsp return ((ntohs(v->lsa->hdr.len) - sizeof(struct lsa_hdr) -
7151393dc49Sstsp sizeof(struct lsa_net)) / sizeof(struct lsa_net_link));
716a1a4e97bSnorby default:
717a1a4e97bSnorby fatalx("lsa_num_links: invalid LSA type");
718a1a4e97bSnorby }
719a1a4e97bSnorby
720a1a4e97bSnorby return (0);
721a1a4e97bSnorby }
722a1a4e97bSnorby
723a1a4e97bSnorby void
lsa_snap(struct rde_nbr * nbr)72447cb1ae0Sdenis lsa_snap(struct rde_nbr *nbr)
725a1a4e97bSnorby {
7266d00ce58Sstsp struct lsa_tree *tree = &nbr->area->lsa_tree;
727a1a4e97bSnorby struct vertex *v;
728a1a4e97bSnorby
729a1a4e97bSnorby do {
730a1a4e97bSnorby RB_FOREACH(v, lsa_tree, tree) {
731a1a4e97bSnorby if (v->deleted)
732a1a4e97bSnorby continue;
733a1a4e97bSnorby lsa_age(v);
7344139c605Sclaudio if (ntohs(v->lsa->hdr.age) >= MAX_AGE) {
73547cb1ae0Sdenis rde_imsg_compose_ospfe(IMSG_LS_SNAP,
73647cb1ae0Sdenis nbr->peerid, 0, &v->lsa->hdr,
73747cb1ae0Sdenis ntohs(v->lsa->hdr.len));
7384139c605Sclaudio } else {
73947cb1ae0Sdenis rde_imsg_compose_ospfe(IMSG_DB_SNAPSHOT,
74047cb1ae0Sdenis nbr->peerid, 0, &v->lsa->hdr,
74147cb1ae0Sdenis sizeof(struct lsa_hdr));
742a1a4e97bSnorby }
7434139c605Sclaudio }
7446d00ce58Sstsp if (tree == &asext_tree)
745a1a4e97bSnorby break;
7466ba455a5Sclaudio if (tree == &nbr->area->lsa_tree)
7476d00ce58Sstsp tree = &nbr->iface->lsa_tree;
7486ba455a5Sclaudio else
749a1a4e97bSnorby tree = &asext_tree;
750a1a4e97bSnorby } while (1);
751a1a4e97bSnorby }
752a1a4e97bSnorby
753a1a4e97bSnorby void
lsa_dump(struct lsa_tree * tree,int imsg_type,pid_t pid)754a1a4e97bSnorby lsa_dump(struct lsa_tree *tree, int imsg_type, pid_t pid)
755a1a4e97bSnorby {
756a1a4e97bSnorby struct vertex *v;
757a1a4e97bSnorby
758a1a4e97bSnorby RB_FOREACH(v, lsa_tree, tree) {
759a1a4e97bSnorby if (v->deleted)
760a1a4e97bSnorby continue;
761a1a4e97bSnorby lsa_age(v);
762a1a4e97bSnorby switch (imsg_type) {
763a1a4e97bSnorby case IMSG_CTL_SHOW_DATABASE:
76426a5862cSjan break;
765a1a4e97bSnorby case IMSG_CTL_SHOW_DB_SELF:
766a1a4e97bSnorby if (v->lsa->hdr.adv_rtr == rde_router_id())
767a1a4e97bSnorby break;
768a1a4e97bSnorby continue;
769a1a4e97bSnorby case IMSG_CTL_SHOW_DB_EXT:
770a1a4e97bSnorby if (v->type == LSA_TYPE_EXTERNAL)
771a1a4e97bSnorby break;
772a1a4e97bSnorby continue;
773d913b22eSclaudio case IMSG_CTL_SHOW_DB_LINK:
774d913b22eSclaudio if (v->type == LSA_TYPE_LINK)
775d913b22eSclaudio break;
776d913b22eSclaudio continue;
777a1a4e97bSnorby case IMSG_CTL_SHOW_DB_NET:
778a1a4e97bSnorby if (v->type == LSA_TYPE_NETWORK)
779a1a4e97bSnorby break;
780a1a4e97bSnorby continue;
781a1a4e97bSnorby case IMSG_CTL_SHOW_DB_RTR:
782a1a4e97bSnorby if (v->type == LSA_TYPE_ROUTER)
783a1a4e97bSnorby break;
784a1a4e97bSnorby continue;
785d5dafa54Sstsp case IMSG_CTL_SHOW_DB_INTRA:
786d5dafa54Sstsp if (v->type == LSA_TYPE_INTRA_A_PREFIX)
787d5dafa54Sstsp break;
788e96904e7Sjan continue;
789a1a4e97bSnorby case IMSG_CTL_SHOW_DB_SUM:
79019f3adaeSnorby if (v->type == LSA_TYPE_INTER_A_PREFIX)
791a1a4e97bSnorby break;
792a1a4e97bSnorby continue;
793a1a4e97bSnorby case IMSG_CTL_SHOW_DB_ASBR:
79419f3adaeSnorby if (v->type == LSA_TYPE_INTER_A_ROUTER)
795a1a4e97bSnorby break;
796a1a4e97bSnorby continue;
797a1a4e97bSnorby default:
798a1a4e97bSnorby log_warnx("lsa_dump: unknown imsg type");
799a1a4e97bSnorby return;
800a1a4e97bSnorby }
801a1a4e97bSnorby rde_imsg_compose_ospfe(imsg_type, 0, pid, &v->lsa->hdr,
802a1a4e97bSnorby ntohs(v->lsa->hdr.len));
803a1a4e97bSnorby }
804a1a4e97bSnorby }
805a1a4e97bSnorby
806a1a4e97bSnorby void
lsa_timeout(int fd,short event,void * bula)807a1a4e97bSnorby lsa_timeout(int fd, short event, void *bula)
808a1a4e97bSnorby {
809a1a4e97bSnorby struct vertex *v = bula;
810a1a4e97bSnorby struct timeval tv;
811a1a4e97bSnorby
812a1a4e97bSnorby lsa_age(v);
813a1a4e97bSnorby
814a1a4e97bSnorby if (v->deleted) {
815a1a4e97bSnorby if (ntohs(v->lsa->hdr.age) >= MAX_AGE) {
816a1a4e97bSnorby vertex_free(v);
817a1a4e97bSnorby } else {
818a1a4e97bSnorby v->deleted = 0;
819a1a4e97bSnorby
820a1a4e97bSnorby /* schedule recalculation of the RIB */
8218e1674f3Sbluhm if (ntohs(v->lsa->hdr.type) == LSA_TYPE_LINK)
8228e1674f3Sbluhm orig_intra_area_prefix_lsas(v->area);
82374faaed2Sbluhm if (ntohs(v->lsa->hdr.type) != LSA_TYPE_EXTERNAL)
824a1a4e97bSnorby v->area->dirty = 1;
825a1a4e97bSnorby start_spf_timer();
826a1a4e97bSnorby
827a1a4e97bSnorby rde_imsg_compose_ospfe(IMSG_LS_FLOOD, v->peerid, 0,
828a1a4e97bSnorby v->lsa, ntohs(v->lsa->hdr.len));
829a1a4e97bSnorby
830a1a4e97bSnorby /* timeout handling either MAX_AGE or LS_REFRESH_TIME */
831a1a4e97bSnorby timerclear(&tv);
832a1a4e97bSnorby if (v->self)
833a1a4e97bSnorby tv.tv_sec = LS_REFRESH_TIME;
834a1a4e97bSnorby else
835a1a4e97bSnorby tv.tv_sec = MAX_AGE - ntohs(v->lsa->hdr.age);
836a1a4e97bSnorby
837a1a4e97bSnorby if (evtimer_add(&v->ev, &tv) != 0)
8383af4e127Snorby fatal("lsa_timeout");
839a1a4e97bSnorby }
840a1a4e97bSnorby return;
841a1a4e97bSnorby }
842a1a4e97bSnorby
843a1a4e97bSnorby if (v->self && ntohs(v->lsa->hdr.age) < MAX_AGE)
844a1a4e97bSnorby lsa_refresh(v);
845a1a4e97bSnorby
846a1a4e97bSnorby rde_imsg_compose_ospfe(IMSG_LS_FLOOD, v->peerid, 0,
847a1a4e97bSnorby v->lsa, ntohs(v->lsa->hdr.len));
848a1a4e97bSnorby }
849a1a4e97bSnorby
850a1a4e97bSnorby void
lsa_refresh(struct vertex * v)851a1a4e97bSnorby lsa_refresh(struct vertex *v)
852a1a4e97bSnorby {
853a1a4e97bSnorby struct timeval tv;
854a1a4e97bSnorby struct timespec tp;
855a1a4e97bSnorby u_int32_t seqnum;
856a1a4e97bSnorby u_int16_t len;
857a1a4e97bSnorby
858a1a4e97bSnorby /* refresh LSA by increasing sequence number by one */
85989db4f92Sbluhm if (v->self && ntohs(v->lsa->hdr.age) >= MAX_AGE)
86089db4f92Sbluhm /* self originated network that is currently beeing removed */
86189db4f92Sbluhm v->lsa->hdr.age = htons(MAX_AGE);
86289db4f92Sbluhm else
863a1a4e97bSnorby v->lsa->hdr.age = htons(DEFAULT_AGE);
864a1a4e97bSnorby seqnum = ntohl(v->lsa->hdr.seq_num);
865a1a4e97bSnorby if (seqnum++ == MAX_SEQ_NUM)
866a1a4e97bSnorby /* XXX fix me */
867a1a4e97bSnorby fatalx("sequence number wrapping");
868a1a4e97bSnorby v->lsa->hdr.seq_num = htonl(seqnum);
869a1a4e97bSnorby
870a1a4e97bSnorby /* recalculate checksum */
871a1a4e97bSnorby len = ntohs(v->lsa->hdr.len);
872a1a4e97bSnorby v->lsa->hdr.ls_chksum = 0;
873a1a4e97bSnorby v->lsa->hdr.ls_chksum = htons(iso_cksum(v->lsa, len, LS_CKSUM_OFFSET));
874a1a4e97bSnorby
875a1a4e97bSnorby clock_gettime(CLOCK_MONOTONIC, &tp);
876a1a4e97bSnorby v->changed = v->stamp = tp.tv_sec;
877a1a4e97bSnorby
878a1a4e97bSnorby timerclear(&tv);
879a1a4e97bSnorby tv.tv_sec = LS_REFRESH_TIME;
880a1a4e97bSnorby if (evtimer_add(&v->ev, &tv) == -1)
881a1a4e97bSnorby fatal("lsa_refresh");
882a1a4e97bSnorby }
883a1a4e97bSnorby
884a1a4e97bSnorby void
lsa_merge(struct rde_nbr * nbr,struct lsa * lsa,struct vertex * v)885a1a4e97bSnorby lsa_merge(struct rde_nbr *nbr, struct lsa *lsa, struct vertex *v)
886a1a4e97bSnorby {
887a1a4e97bSnorby struct timeval tv;
888a1a4e97bSnorby struct timespec tp;
889a1a4e97bSnorby time_t now;
890a1a4e97bSnorby u_int16_t len;
891a1a4e97bSnorby
892a1a4e97bSnorby if (v == NULL) {
893a1a4e97bSnorby if (lsa_add(nbr, lsa))
894a1a4e97bSnorby /* delayed update */
895a1a4e97bSnorby return;
896a1a4e97bSnorby rde_imsg_compose_ospfe(IMSG_LS_FLOOD, nbr->peerid, 0,
897a1a4e97bSnorby lsa, ntohs(lsa->hdr.len));
898a1a4e97bSnorby return;
899a1a4e97bSnorby }
900a1a4e97bSnorby
901a1a4e97bSnorby /* set the seq_num to the current one. lsa_refresh() will do the ++ */
902a1a4e97bSnorby lsa->hdr.seq_num = v->lsa->hdr.seq_num;
903a1a4e97bSnorby /* recalculate checksum */
904a1a4e97bSnorby len = ntohs(lsa->hdr.len);
905a1a4e97bSnorby lsa->hdr.ls_chksum = 0;
906a1a4e97bSnorby lsa->hdr.ls_chksum = htons(iso_cksum(lsa, len, LS_CKSUM_OFFSET));
907a1a4e97bSnorby
908a1a4e97bSnorby /* compare LSA most header fields are equal so don't check them */
909a1a4e97bSnorby if (lsa_equal(lsa, v->lsa)) {
910a1a4e97bSnorby free(lsa);
911a1a4e97bSnorby return;
912a1a4e97bSnorby }
913a1a4e97bSnorby
914a1a4e97bSnorby /* overwrite the lsa all other fields are unaffected */
915a1a4e97bSnorby free(v->lsa);
916a1a4e97bSnorby v->lsa = lsa;
9178e1674f3Sbluhm if (v->type == LSA_TYPE_LINK)
9188e1674f3Sbluhm orig_intra_area_prefix_lsas(nbr->area);
91931505e9fSclaudio if (v->type != LSA_TYPE_EXTERNAL)
920a1a4e97bSnorby nbr->area->dirty = 1;
9218e1674f3Sbluhm start_spf_timer();
922a1a4e97bSnorby
923a1a4e97bSnorby /* set correct timeout for reflooding the LSA */
924a1a4e97bSnorby clock_gettime(CLOCK_MONOTONIC, &tp);
925a1a4e97bSnorby now = tp.tv_sec;
926a1a4e97bSnorby timerclear(&tv);
927a1a4e97bSnorby if (v->changed + MIN_LS_INTERVAL >= now)
928a1a4e97bSnorby tv.tv_sec = MIN_LS_INTERVAL;
929a1a4e97bSnorby if (evtimer_add(&v->ev, &tv) == -1)
930a1a4e97bSnorby fatal("lsa_merge");
931a1a4e97bSnorby }
932a1a4e97bSnorby
933a1a4e97bSnorby void
lsa_remove_invalid_sums(struct area * area)934a1a4e97bSnorby lsa_remove_invalid_sums(struct area *area)
935a1a4e97bSnorby {
936a1a4e97bSnorby struct lsa_tree *tree = &area->lsa_tree;
937a1a4e97bSnorby struct vertex *v, *nv;
938a1a4e97bSnorby
939a1a4e97bSnorby /* XXX speed me up */
940a1a4e97bSnorby for (v = RB_MIN(lsa_tree, tree); v != NULL; v = nv) {
941a1a4e97bSnorby nv = RB_NEXT(lsa_tree, tree, v);
94231505e9fSclaudio if ((v->type == LSA_TYPE_INTER_A_PREFIX ||
94331505e9fSclaudio v->type == LSA_TYPE_INTER_A_ROUTER) &&
944a1a4e97bSnorby v->self && v->cost == LS_INFINITY &&
945a1a4e97bSnorby v->deleted == 0) {
946a1a4e97bSnorby /*
947a1a4e97bSnorby * age the lsa and call lsa_timeout() which will
948a1a4e97bSnorby * actually remove it from the database.
949a1a4e97bSnorby */
950a1a4e97bSnorby v->lsa->hdr.age = htons(MAX_AGE);
951a1a4e97bSnorby lsa_timeout(0, 0, v);
952a1a4e97bSnorby }
953a1a4e97bSnorby }
954a1a4e97bSnorby }
955a1a4e97bSnorby
956a1a4e97bSnorby int
lsa_equal(struct lsa * a,struct lsa * b)957a1a4e97bSnorby lsa_equal(struct lsa *a, struct lsa *b)
958a1a4e97bSnorby {
959a1a4e97bSnorby /*
960a1a4e97bSnorby * compare LSA that already have same type, adv_rtr and ls_id
961a1a4e97bSnorby * so not all header need to be compared
962a1a4e97bSnorby */
963a1a4e97bSnorby if (a == NULL || b == NULL)
964a1a4e97bSnorby return (0);
965a1a4e97bSnorby if (a->hdr.len != b->hdr.len)
966a1a4e97bSnorby return (0);
96789db4f92Sbluhm /* LSAs with age MAX_AGE are never equal */
968a1a4e97bSnorby if (a->hdr.age == htons(MAX_AGE) || b->hdr.age == htons(MAX_AGE))
969a1a4e97bSnorby return (0);
970a1a4e97bSnorby if (memcmp(&a->data, &b->data, ntohs(a->hdr.len) -
971a1a4e97bSnorby sizeof(struct lsa_hdr)))
972a1a4e97bSnorby return (0);
973a1a4e97bSnorby
974a1a4e97bSnorby return (1);
975a1a4e97bSnorby }
976a1a4e97bSnorby
9774139c605Sclaudio int
lsa_get_prefix(void * buf,u_int16_t len,struct rt_prefix * p)9788cd84907Sclaudio lsa_get_prefix(void *buf, u_int16_t len, struct rt_prefix *p)
9794139c605Sclaudio {
9808cd84907Sclaudio struct lsa_prefix *lp = buf;
9818cd84907Sclaudio u_int32_t *buf32, *addr = NULL;
9824139c605Sclaudio u_int8_t prefixlen;
98390a9ab06Sclaudio u_int16_t consumed;
9844139c605Sclaudio
9858cd84907Sclaudio if (len < sizeof(*lp))
9864139c605Sclaudio return (-1);
9874139c605Sclaudio
9888cd84907Sclaudio prefixlen = lp->prefixlen;
9894139c605Sclaudio
9904139c605Sclaudio if (p) {
9914139c605Sclaudio bzero(p, sizeof(*p));
9928cd84907Sclaudio p->prefixlen = lp->prefixlen;
9938cd84907Sclaudio p->options = lp->options;
9948cd84907Sclaudio p->metric = ntohs(lp->metric);
9954139c605Sclaudio addr = (u_int32_t *)&p->prefix;
9964139c605Sclaudio }
9978cd84907Sclaudio
9988cd84907Sclaudio buf32 = (u_int32_t *)(lp + 1);
99990a9ab06Sclaudio consumed = sizeof(*lp);
10004139c605Sclaudio
100190a9ab06Sclaudio for (prefixlen = LSA_PREFIXSIZE(prefixlen) / sizeof(u_int32_t);
100290a9ab06Sclaudio prefixlen > 0; prefixlen--) {
10038fa0670bSclaudio if (len < consumed + sizeof(u_int32_t))
10044139c605Sclaudio return (-1);
10054139c605Sclaudio if (addr)
10064139c605Sclaudio *addr++ = *buf32++;
10078fa0670bSclaudio consumed += sizeof(u_int32_t);
10084139c605Sclaudio }
10094139c605Sclaudio
10108fa0670bSclaudio return (consumed);
10114139c605Sclaudio }
1012