summaryrefslogtreecommitdiff
path: root/usr.sbin
diff options
context:
space:
mode:
Diffstat (limited to 'usr.sbin')
-rw-r--r--usr.sbin/ospfd/Makefile4
-rw-r--r--usr.sbin/ospfd/ospf.h18
-rw-r--r--usr.sbin/ospfd/ospfd.c6
-rw-r--r--usr.sbin/ospfd/ospfd.conf.524
-rw-r--r--usr.sbin/ospfd/ospfd.h74
-rw-r--r--usr.sbin/ospfd/ospfe.c10
-rw-r--r--usr.sbin/ospfd/parse.y30
-rw-r--r--usr.sbin/ospfd/rde.c26
-rw-r--r--usr.sbin/ospfd/rde.h41
-rw-r--r--usr.sbin/ospfd/rde_lsdb.c38
-rw-r--r--usr.sbin/ospfd/rde_spf.c715
11 files changed, 932 insertions, 54 deletions
diff --git a/usr.sbin/ospfd/Makefile b/usr.sbin/ospfd/Makefile
index fc5ff114ec6..bc34712525d 100644
--- a/usr.sbin/ospfd/Makefile
+++ b/usr.sbin/ospfd/Makefile
@@ -1,11 +1,11 @@
-# $OpenBSD: Makefile,v 1.2 2005/02/02 21:22:28 norby Exp $
+# $OpenBSD: Makefile,v 1.3 2005/02/27 08:21:15 norby Exp $
PROG= ospfd
SRCS= area.c auth.c buffer.c config.c control.c database.c hello.c \
imsg.c in_cksum.c interface.c iso_cksum.c kroute.c lsack.c \
lsreq.c lsupdate.c log.c neighbor.c ospfd.c ospfe.c packet.c \
- parse.y rde.c rde_lsdb.c
+ parse.y rde.c rde_lsdb.c rde_spf.c
MAN= ospfd.8 ospfd.conf.5
diff --git a/usr.sbin/ospfd/ospf.h b/usr.sbin/ospfd/ospf.h
index 5cd333ffd71..40570137ef6 100644
--- a/usr.sbin/ospfd/ospf.h
+++ b/usr.sbin/ospfd/ospf.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: ospf.h,v 1.7 2005/02/08 21:52:48 norby Exp $ */
+/* $OpenBSD: ospf.h,v 1.8 2005/02/27 08:21:15 norby Exp $ */
/*
* Copyright (c) 2004, 2005 Esben Norby <norby@openbsd.org>
@@ -60,6 +60,14 @@
#define DEFAULT_NBR_TMOUT 86400 /* 24 hours */
+#define DEFAULT_SPF_DELAY 1
+#define MIN_SPF_DELAY 1
+#define MAX_SPF_DELAY 10
+
+#define DEFAULT_SPF_HOLDTIME 5
+#define MIN_SPF_HOLDTIME 1
+#define MAX_SPF_HOLDTIME 5
+
/* OSPF compatibility flags */
#define OSPF_OPTION_E 0x02
#define OSPF_OPTION_MC 0x04
@@ -160,6 +168,10 @@ struct ls_upd_hdr {
#define LSA_METRIC_MASK 0x00ffffff /* only for sum & as-ext */
#define LSA_ASEXT_E_FLAG 0x80000000
+#define OSPF_RTR_B 0x01
+#define OSPF_RTR_E 0x02
+#define OSPF_RTR_V 0x04
+
struct lsa_rtr {
u_int8_t flags;
u_int8_t dummy;
@@ -179,6 +191,10 @@ struct lsa_net {
u_int32_t att_rtr[1];
};
+struct lsa_net_link {
+ u_int32_t att_rtr;
+};
+
struct lsa_sum {
u_int32_t mask;
u_int32_t metric; /* only lower 24 bit */
diff --git a/usr.sbin/ospfd/ospfd.c b/usr.sbin/ospfd/ospfd.c
index 44549f1386b..165f859ee27 100644
--- a/usr.sbin/ospfd/ospfd.c
+++ b/usr.sbin/ospfd/ospfd.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ospfd.c,v 1.5 2005/02/24 16:28:43 claudio Exp $ */
+/* $OpenBSD: ospfd.c,v 1.6 2005/02/27 08:21:15 norby Exp $ */
/*
* Copyright (c) 2005 Claudio Jeker <claudio@openbsd.org>
@@ -367,6 +367,10 @@ main_dispatch_rde(int fd, short event, void *bula)
break;
switch (imsg.hdr.type) {
+ case IMSG_KROUTE_CHANGE:
+ if (kr_change(imsg.data))
+ log_warn("main_dispatch_rde: error changing route");
+ break;
default:
log_debug("main_dispatch_rde: error handling imsg %d",
imsg.hdr.type);
diff --git a/usr.sbin/ospfd/ospfd.conf.5 b/usr.sbin/ospfd/ospfd.conf.5
index 0e7913c974b..b0329e12726 100644
--- a/usr.sbin/ospfd/ospfd.conf.5
+++ b/usr.sbin/ospfd/ospfd.conf.5
@@ -1,4 +1,4 @@
-.\" $OpenBSD: ospfd.conf.5,v 1.4 2005/02/07 05:51:00 david Exp $
+.\" $OpenBSD: ospfd.conf.5,v 1.5 2005/02/27 08:21:15 norby Exp $
.\"
.\" Copyright (c) 2005 Esben Norby <norby@openbsd.org>
.\" Copyright (c) 2004 Claudio Jeker <claudio@openbsd.org>
@@ -89,17 +89,17 @@ The default is
.It Ic router-id Ar address
Set the router ID; if not specified, the lowest IP address of the router
will be used.
-.\".It Ic spf-delay Ar seconds
-.\"Set SPF delay in seconds.
-.\"The delay between receiving an update to the link
-.\"state database and starting the shortest path first calculation.
-.\"The default value is 1; valid range is 1\-10 seconds.
-.\".Pp
-.\".It Ic spf-holdtime Ar seconds
-.\"Set the SPF holdtime in seconds.
-.\"The minimum time between two consecutive
-.\"shortest path first calculations.
-.\"The default value is 5 seconds; the valid is range 1\-5 seconds.
+.It Ic spf-delay Ar seconds
+Set SPF delay in seconds.
+The delay between receiving an update to the link
+state database and starting the shortest path first calculation.
+The default value is 1; valid range is 1\-10 seconds.
+.Pp
+.It Ic spf-holdtime Ar seconds
+Set the SPF holdtime in seconds.
+The minimum time between two consecutive
+shortest path first calculations.
+The default value is 5 seconds; the valid is range 1\-5 seconds.
.El
.Sh AREAS
Areas are used for grouping interfaces.
diff --git a/usr.sbin/ospfd/ospfd.h b/usr.sbin/ospfd/ospfd.h
index fafaf3e8e2f..1c338dcd448 100644
--- a/usr.sbin/ospfd/ospfd.h
+++ b/usr.sbin/ospfd/ospfd.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: ospfd.h,v 1.10 2005/02/24 16:28:43 claudio Exp $ */
+/* $OpenBSD: ospfd.h,v 1.11 2005/02/27 08:21:15 norby Exp $ */
/*
* Copyright (c) 2004 Esben Norby <norby@openbsd.org>
@@ -29,9 +29,9 @@
#include <event.h>
#include <stdbool.h>
-#define CONF_FILE "/etc/ospfd.conf"
-#define OSPFD_SOCKET "/var/run/ospfd.sock"
-#define OSPFD_USER "_ospfd"
+#define CONF_FILE "/etc/ospfd.conf"
+#define OSPFD_SOCKET "/var/run/ospfd.sock"
+#define OSPFD_USER "_ospfd"
#define NBR_HASHSIZE 128
#define LSA_HASHSIZE 512
@@ -95,6 +95,8 @@ enum imsg_type {
IMSG_CTL_FIB_DECOUPLE,
IMSG_CTL_AREA,
IMSG_CTL_END,
+ IMSG_KROUTE_CHANGE,
+ IMSG_KROUTE_DELETE,
IMSG_IFINFO,
IMSG_NEIGHBOR_UP,
IMSG_NEIGHBOR_DOWN,
@@ -134,24 +136,24 @@ struct rde_nbr;
RB_HEAD(lsa_tree, vertex);
struct area {
- LIST_ENTRY(area) entry;
- struct in_addr id;
-
- struct lsa_tree lsa_tree;
- LIST_HEAD(, iface) iface_list;
- LIST_HEAD(, rde_nbr) nbr_list;
-/* list addr_range_list; */
- u_int32_t stub_default_cost;
-
- u_int32_t dead_interval;
- u_int16_t transfer_delay;
- u_int16_t hello_interval;
- u_int16_t rxmt_interval;
- u_int16_t metric;
- u_int8_t priority;
-
- bool transit;
- bool stub;
+ LIST_ENTRY(area) entry;
+ struct in_addr id;
+
+ struct lsa_tree lsa_tree;
+ LIST_HEAD(, iface) iface_list;
+ LIST_HEAD(, rde_nbr) nbr_list;
+/* list addr_range_list; */
+ u_int32_t stub_default_cost;
+
+ u_int32_t dead_interval;
+ u_int16_t transfer_delay;
+ u_int16_t hello_interval;
+ u_int16_t rxmt_interval;
+ u_int16_t metric;
+ u_int8_t priority;
+
+ bool transit;
+ bool stub;
};
/* interface states */
@@ -213,6 +215,28 @@ enum auth_type {
AUTH_CRYPT
};
+/* spf states */
+enum spf_state {
+ SPF_IDLE,
+ SPF_DELAY,
+ SPF_HOLD,
+ SPF_HOLDQUEUE
+};
+
+enum path_type {
+ PT_INTRA_AREA,
+ PT_INTER_AREA,
+ PT_TYPE1_EXT,
+ PT_TYPE2_EXT
+};
+
+static const char * const path_type_names[] = {
+ "Intra-Area",
+ "Inter-Area",
+ "Type 1 external",
+ "Type 2 external"
+};
+
/* lsa list used in RDE and OE */
TAILQ_HEAD(lsa_head, lsa_entry);
@@ -265,6 +289,7 @@ enum {
struct ospfd_conf {
struct event ev;
+ struct event spf_timer;
struct in_addr rtr_id;
u_int32_t opts;
#define OSPFD_OPT_VERBOSE 0x00000001
@@ -272,8 +297,11 @@ struct ospfd_conf {
#define OSPFD_OPT_NOACTION 0x00000004
int maxdepth;
LIST_HEAD(, area) area_list;
-
+ LIST_HEAD(, vertex) cand_list;
struct lsa_tree lsa_tree;
+ u_int32_t spf_delay;
+ u_int32_t spf_hold_time;
+ int spf_state;
int ospf_socket;
int flags;
int options; /* OSPF options */
diff --git a/usr.sbin/ospfd/ospfe.c b/usr.sbin/ospfd/ospfe.c
index 77f92bfbdd6..a1ba93f5311 100644
--- a/usr.sbin/ospfd/ospfe.c
+++ b/usr.sbin/ospfd/ospfe.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ospfe.c,v 1.7 2005/02/19 10:19:56 norby Exp $ */
+/* $OpenBSD: ospfe.c,v 1.8 2005/02/27 08:21:15 norby Exp $ */
/*
* Copyright (c) 2005 Claudio Jeker <claudio@openbsd.org>
@@ -340,7 +340,7 @@ ospfe_dispatch_rde(int fd, short event, void *bula)
if (nbr == NULL)
fatalx("ospfe_dispatch_rde: "
"neighbor not found");
-
+
nbr->dd_pending--;
if (nbr->dd_pending == 0 && nbr->state & NBR_STA_LOAD) {
if (ls_req_list_empty(nbr))
@@ -660,7 +660,7 @@ orig_rtr_lsa(struct area *area)
num_links++;
if (buf_add(buf, &rtr_link, sizeof(rtr_link)))
fatalx("orig_rtr_lsa: buf_add failed");
-
+
LIST_FOREACH(nbr, &iface->nbr_list, entry) {
if (nbr != iface->self &&
nbr->state & NBR_STA_FULL) {
@@ -692,7 +692,7 @@ orig_rtr_lsa(struct area *area)
}
/* LSA router header */
- lsa_rtr.flags = 0; /* XXX */
+ lsa_rtr.flags = oeconf->flags; /* XXX */
lsa_rtr.dummy = 0;
lsa_rtr.nlinks = htons(num_links);
memcpy(buf_seek(buf, sizeof(lsa_hdr), sizeof(lsa_rtr)),
@@ -712,7 +712,7 @@ orig_rtr_lsa(struct area *area)
chksum = htons(iso_cksum(buf->buf, buf->wpos, LS_CKSUM_OFFSET));
memcpy(buf_seek(buf, LS_CKSUM_OFFSET, sizeof(chksum)),
&chksum, sizeof(chksum));
-
+
if (self)
imsg_compose(ibuf_rde, IMSG_LS_UPD,
self->peerid, 0, -1, buf->buf, buf->wpos);
diff --git a/usr.sbin/ospfd/parse.y b/usr.sbin/ospfd/parse.y
index fb37b166b74..fca2dd01d5f 100644
--- a/usr.sbin/ospfd/parse.y
+++ b/usr.sbin/ospfd/parse.y
@@ -1,7 +1,7 @@
-/* $OpenBSD: parse.y,v 1.4 2005/02/02 21:02:25 norby Exp $ */
+/* $OpenBSD: parse.y,v 1.5 2005/02/27 08:21:15 norby Exp $ */
/*
- * Copyright (c) 2004 Esben Norby <norby@openbsd.org>
+ * Copyright (c) 2004, 2005 Esben Norby <norby@openbsd.org>
* Copyright (c) 2004 Ryan McBride <mcbride@openbsd.org>
* Copyright (c) 2002, 2003, 2004 Henning Brauer <henning@openbsd.org>
* Copyright (c) 2001 Markus Friedl. All rights reserved.
@@ -98,6 +98,7 @@ typedef struct {
%}
%token AREA INTERFACE ROUTERID FIBUPDATE
+%token SPFDELAY SPFHOLDTIME
%token AUTHKEY AUTHTYPE
%token METRIC PASSIVE
%token HELLOINTERVAL TRANSMITDELAY
@@ -229,6 +230,24 @@ conf_main : METRIC number {
else
conf->flags &= ~OSPFD_FLAG_NO_FIB_UPDATE;
}
+ | SPFDELAY number {
+ if ($2 < MIN_SPF_DELAY || $2 > MAX_SPF_DELAY) {
+ yyerror("spf-delay out of range "
+ "(%d-%d)", MIN_SPF_DELAY,
+ MAX_SPF_DELAY);
+ YYERROR;
+ }
+ conf->spf_delay = $2;
+ }
+ | SPFHOLDTIME number {
+ if ($2 < MIN_SPF_HOLDTIME || $2 > MAX_SPF_HOLDTIME) {
+ yyerror("spf-holdtime out of range "
+ "(%d-%d)", MIN_SPF_HOLDTIME,
+ MAX_SPF_HOLDTIME);
+ YYERROR;
+ }
+ conf->spf_hold_time = $2;
+ }
;
authtype : AUTHTYPE STRING {
@@ -466,7 +485,9 @@ lookup(char *s)
{"router-dead-time", ROUTERDEADTIME},
{"router-id", ROUTERID},
{"router-priority", ROUTERPRIORITY},
- {"transmit-delay", TRANSMITDELAY},
+ {"spf-delay", SPFDELAY},
+ {"spf-holdtime", SPFHOLDTIME},
+ {"transmit-delay", TRANSMITDELAY}
};
const struct keywords *p;
@@ -689,6 +710,9 @@ parse_config(char *filename, int opts)
defaults.priority = DEFAULT_PRIORITY;
conf->options = OSPF_OPTION_E;
+ conf->spf_delay = DEFAULT_SPF_DELAY;
+ conf->spf_hold_time = DEFAULT_SPF_HOLDTIME;
+ conf->spf_state = SPF_IDLE;
if ((fin = fopen(filename, "r")) == NULL) {
warn("%s", filename);
diff --git a/usr.sbin/ospfd/rde.c b/usr.sbin/ospfd/rde.c
index a0125141205..5d79486695c 100644
--- a/usr.sbin/ospfd/rde.c
+++ b/usr.sbin/ospfd/rde.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: rde.c,v 1.6 2005/02/10 14:05:48 claudio Exp $ */
+/* $OpenBSD: rde.c,v 1.7 2005/02/27 08:21:15 norby Exp $ */
/*
* Copyright (c) 2004, 2005 Claudio Jeker <claudio@openbsd.org>
@@ -142,6 +142,10 @@ rde(struct ospfd_conf *xconf, int pipe_parent2rde[2], int pipe_ospfe2rde[2],
ibuf_main->handler, ibuf_main);
event_add(&ibuf_main->ev, NULL);
+ evtimer_set(&rdeconf->spf_timer, spf_timer, rdeconf);
+ cand_list_init();
+ rt_init();
+
event_dispatch();
rde_shutdown();
@@ -153,8 +157,8 @@ rde(struct ospfd_conf *xconf, int pipe_parent2rde[2], int pipe_ospfe2rde[2],
void
rde_shutdown(void)
{
-
- /* ... */
+ stop_spf_timer(rdeconf);
+ cand_list_clr();
msgbuf_write(&ibuf_ospfe->w);
msgbuf_clear(&ibuf_ospfe->w);
@@ -356,6 +360,7 @@ rde_dispatch_imsg(int fd, short event, void *bula)
if (nbr->self) {
lsa_merge(nbr, lsa, v);
+ start_spf_timer(rdeconf);
break;
}
@@ -379,6 +384,10 @@ rde_dispatch_imsg(int fd, short event, void *bula)
v->nbr->peerid, 0, -1,
v->lsa, ntohs(v->lsa->hdr.len));
/* TODO LSA on req list -> BadLSReq */
+
+ /* start spf_timer */
+ log_debug("rde_dispatch_imsg: start spf_timer");
+ start_spf_timer(rdeconf);
} else if (r < 0) {
/* new LSA older than DB */
if (ntohl(db_hdr->seq_num) == MAX_SEQ_NUM &&
@@ -463,7 +472,18 @@ rde_router_id(void)
return (rdeconf->rtr_id.s_addr);
}
+void
+rde_send_kroute(struct rt_node *r)
+{
+ struct kroute kr;
+
+ bzero(&kr, sizeof(kr));
+ kr.prefix.s_addr = r->prefix.s_addr;
+ kr.nexthop.s_addr = r->nexthop.s_addr;
+ kr.prefixlen = r->prefixlen;
+ imsg_compose(ibuf_main, IMSG_KROUTE_CHANGE, 0, 0, -1, &kr, sizeof(kr));
+}
LIST_HEAD(rde_nbr_head, rde_nbr);
diff --git a/usr.sbin/ospfd/rde.h b/usr.sbin/ospfd/rde.h
index 80e70023491..72ca6893b2a 100644
--- a/usr.sbin/ospfd/rde.h
+++ b/usr.sbin/ospfd/rde.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: rde.h,v 1.4 2005/02/09 22:58:08 claudio Exp $ */
+/* $OpenBSD: rde.h,v 1.5 2005/02/27 08:21:15 norby Exp $ */
/*
* Copyright (c) 2004, 2005 Esben Norby <norby@openbsd.org>
@@ -28,6 +28,7 @@
struct vertex {
RB_ENTRY(vertex) entry;
+ TAILQ_ENTRY(vertex) cand;
struct event ev;
struct in_addr nexthop;
struct vertex *prev;
@@ -54,12 +55,22 @@ struct rde_nbr {
int self;
};
+struct rt_node {
+ RB_ENTRY(rt_node) entry;
+ struct in_addr prefix;
+ u_int8_t prefixlen;
+ struct in_addr nexthop;
+ enum path_type p_type;
+ u_int32_t cost;
+};
+
/* rde.c */
pid_t rde(struct ospfd_conf *, int [2], int [2], int [2]);
int rde_imsg_compose_parent(int, pid_t, void *, u_int16_t);
int rde_imsg_compose_ospfe(int, u_int32_t, pid_t, void *,
u_int16_t);
u_int32_t rde_router_id(void);
+void rde_send_kroute(struct rt_node *);
void rde_nbr_del(struct rde_nbr *);
int rde_nbr_loading(struct area *);
struct rde_nbr *rde_nbr_self(struct area *);
@@ -74,10 +85,38 @@ int lsa_self(struct rde_nbr *, struct lsa *, struct vertex *);
void lsa_add(struct rde_nbr *, struct lsa *);
void lsa_del(struct rde_nbr *, struct lsa_hdr *);
struct vertex *lsa_find(struct area *, u_int8_t, u_int32_t, u_int32_t);
+struct vertex *lsa_find_net(struct area *area, u_int32_t);
+int lsa_num_links(struct vertex *);
void lsa_snap(struct area *, u_int32_t);
void lsa_dump(struct lsa_tree *, pid_t);
void lsa_merge(struct rde_nbr *, struct lsa *, struct vertex *);
+/* rde_spf.c */
+void spf_calc(struct area *);
+void spf_tree_clr(struct area *);
+
+void cand_list_init(void);
+void cand_list_add(struct vertex *);
+struct vertex *cand_list_pop(void);
+bool cand_list_present(struct vertex *);
+void cand_list_clr(void);
+bool cand_list_empty(void);
+
+void spf_timer(int, short, void *);
+int start_spf_timer(struct ospfd_conf *);
+int stop_spf_timer(struct ospfd_conf *);
+int start_spf_holdtimer(struct ospfd_conf *);
+
+void rt_init(void);
+int rt_compare(struct rt_node *, struct rt_node *);
+struct rt_node *rt_find(in_addr_t, u_int8_t);
+int rt_insert(struct rt_node *);
+int rt_remove(struct rt_node *);
+void rt_clear(void);
+
+struct lsa_rtr_link *get_rtr_link(struct vertex *, int);
+struct lsa_net_link *get_net_link(struct vertex *, int);
+
RB_PROTOTYPE(lsa_tree, vertex, entry, lsa_compare)
#endif /* _RDE_H_ */
diff --git a/usr.sbin/ospfd/rde_lsdb.c b/usr.sbin/ospfd/rde_lsdb.c
index 79af6ed4c61..a7ed88df490 100644
--- a/usr.sbin/ospfd/rde_lsdb.c
+++ b/usr.sbin/ospfd/rde_lsdb.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: rde_lsdb.c,v 1.9 2005/02/09 22:58:08 claudio Exp $ */
+/* $OpenBSD: rde_lsdb.c,v 1.10 2005/02/27 08:21:15 norby Exp $ */
/*
* Copyright (c) 2004, 2005 Claudio Jeker <claudio@openbsd.org>
@@ -424,6 +424,38 @@ lsa_find(struct area *area, u_int8_t type, u_int32_t ls_id, u_int32_t adv_rtr)
return (v);
}
+struct vertex *
+lsa_find_net(struct area *area, u_int32_t ls_id)
+{
+ struct lsa_tree *tree = &area->lsa_tree;
+ struct vertex *v;
+
+ RB_FOREACH(v, lsa_tree, tree) {
+ if ((v->lsa->hdr.type == LSA_TYPE_NETWORK) &&
+ (v->lsa->hdr.ls_id == (ls_id))) {
+ return (v);
+ }
+ }
+
+ return (NULL);
+}
+
+int
+lsa_num_links(struct vertex *v)
+{
+ switch (v->type) {
+ case LSA_TYPE_ROUTER:
+ return (ntohs(v->lsa->data.rtr.nlinks));
+ case LSA_TYPE_NETWORK:
+ return ((ntohs(v->lsa->hdr.len) - sizeof(struct lsa_hdr)
+ - sizeof(u_int32_t)) / sizeof(struct lsa_net_link));
+ default:
+ fatalx("lsa_num_links: invalid LSA type");
+ }
+
+ return (0);
+}
+
void
lsa_snap(struct area *area, u_int32_t peerid)
{
@@ -520,11 +552,11 @@ lsa_merge(struct rde_nbr *nbr, struct lsa *lsa, struct vertex *v)
/* overwrite the lsa all other fields are unaffected */
free(v->lsa);
v->lsa = lsa;
-
+
/* set correct timeout for reflooding the LSA */
now = time(NULL);
timerclear(&tv);
- if (v->changed + MIN_LS_ARRIVAL >= now)
+ if (v->changed + MIN_LS_ARRIVAL >= now)
tv.tv_sec = MIN_LS_ARRIVAL;
evtimer_add(&v->ev, &tv);
}
diff --git a/usr.sbin/ospfd/rde_spf.c b/usr.sbin/ospfd/rde_spf.c
new file mode 100644
index 00000000000..25423a5cb5e
--- /dev/null
+++ b/usr.sbin/ospfd/rde_spf.c
@@ -0,0 +1,715 @@
+/* $OpenBSD: rde_spf.c,v 1.1 2005/02/27 08:21:15 norby Exp $ */
+
+/*
+ * Copyright (c) 2005 Esben Norby <norby@openbsd.org>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <sys/types.h>
+#include <sys/socket.h>
+#include <netinet/in.h>
+#include <arpa/inet.h>
+#include <err.h>
+#include <stdlib.h>
+
+#include "ospfd.h"
+#include "ospf.h"
+#include "log.h"
+#include "rde.h"
+
+extern struct ospfd_conf *rdeconf;
+TAILQ_HEAD(, vertex) cand_list;
+RB_HEAD(rt_tree, rt_node) rt_tree, rt;
+RB_PROTOTYPE(rt_tree, rt_node, entry, rt_compare)
+RB_GENERATE(rt_tree, rt_node, entry, rt_compare)
+struct vertex *spf_root = NULL;
+
+void spf_dump(struct area *); /* XXX */
+void rt_dump(void); /* XXX */
+void cand_list_dump(void); /* XXX */
+void calc_next_hop(struct vertex *, struct vertex *);
+void rt_update(struct in_addr, u_int8_t, struct in_addr, u_int32_t, u_int8_t);
+bool linked(struct vertex *, struct vertex *);
+u_int8_t mask2prefixlen(in_addr_t);
+
+void
+spf_dump(struct area *area)
+{
+ struct lsa_tree *tree = &area->lsa_tree;
+ struct vertex *v;
+ struct vertex *p; /* parent */
+ struct in_addr addr;
+
+ log_debug("spf_dump:");
+ RB_FOREACH(v, lsa_tree, tree) {
+ addr.s_addr = htonl(v->ls_id);
+ log_debug(" id %s type %d cost %d", inet_ntoa(addr),
+ v->type, v->cost);
+ log_debug(" nexthop: %s", inet_ntoa(v->nexthop));
+
+#if 1
+ log_debug(" --------------------------------------------");
+ p = v->prev;
+ while (p != NULL) {
+ addr.s_addr = htonl(p->ls_id);
+ log_debug(" id %15s type %d cost %d",
+ inet_ntoa(addr), p->type, p->cost);
+ p = p->prev;
+ }
+ log_debug("");
+#endif
+ }
+
+ return;
+}
+
+void
+rt_dump(void)
+{
+ struct rt_node *r;
+ int i = 0;
+
+ log_debug("rt_dump:");
+
+ RB_FOREACH(r, rt_tree, &rt) {
+ log_debug("net: %s/%d", inet_ntoa(r->prefix), r->prefixlen);
+ log_debug(" nexthop: %s cost: %d type: %s",
+ inet_ntoa(r->nexthop), r->cost, path_type_names[r->p_type]);
+ i++;
+
+ rde_send_kroute(r);
+ }
+
+ log_debug("count: %d", i);
+}
+
+void
+spf_calc(struct area *area)
+{
+ struct lsa_tree *tree = &area->lsa_tree;
+ struct vertex *v, *w;
+ struct lsa_rtr_link *rtr_link = NULL;
+ struct lsa_net_link *net_link = NULL;
+ u_int32_t d;
+ int i;
+ struct in_addr addr;
+
+ log_debug("spf_calc: calculation started, area ID %s",
+ inet_ntoa(area->id));
+
+ /* clear SPF tree */
+ spf_tree_clr(area);
+ cand_list_clr();
+
+ /* initialize SPF tree */
+ if ((v = spf_root = lsa_find(area, LSA_TYPE_ROUTER, rde_router_id(),
+ rde_router_id())) == NULL)
+ fatalx("spf_calc: cannot find self originated router LSA");
+ area->transit = false;
+ spf_root->cost = 0;
+ w = NULL;
+
+ /* calculate SPF tree */
+ do {
+ /* loop links */
+ for (i = 0; i < lsa_num_links(v); i++) {
+ switch (v->type) {
+ case LSA_TYPE_ROUTER:
+ rtr_link = get_rtr_link(v, i);
+ switch (rtr_link->type) {
+ case LINK_TYPE_STUB_NET:
+ /* skip */
+ continue;
+ case LINK_TYPE_POINTTOPOINT:
+ case LINK_TYPE_VIRTUAL:
+ /* find router LSA */
+ w = lsa_find(area, LSA_TYPE_ROUTER,
+ rtr_link->id, rtr_link->id);
+ break;
+ case LINK_TYPE_TRANSIT_NET:
+ /* find network LSA */
+ w = lsa_find_net(area, rtr_link->id);
+ break;
+ default:
+ fatalx("spf_calc: invalid link type");
+ }
+ break;
+ case LSA_TYPE_NETWORK:
+ net_link = get_net_link(v, i);
+ /* find router LSA */
+ w = lsa_find(area, LSA_TYPE_ROUTER,
+ net_link->att_rtr, net_link->att_rtr);
+ break;
+ default:
+ fatalx("spf_calc: invalid LSA type");
+ }
+
+ if (w == NULL) {
+ log_debug("spf_calc: w = NULL");
+ continue;
+ }
+
+ if (w->lsa->hdr.age == MAX_AGE) {
+ log_debug("spf_calc: age = MAX_AGE");
+ continue;
+ }
+
+ if (!linked(w, v)) {
+ log_debug("spf_calc: w has no link to v");
+ continue;
+ }
+#if 0
+ if ((w->cost != LS_INFINITY) && (v->prev != NULL)) {
+ log_debug("spf_calc: w already in SPF tree");
+ continue;
+ }
+#endif
+ if (v->type == LSA_TYPE_ROUTER)
+ d = v->cost + ntohs(rtr_link->metric);
+ else
+ d = v->cost;
+
+ if (cand_list_present(w)) {
+ if (d > w->cost)
+ continue;
+
+ if (d == w->cost) {
+ /* calc next hop */
+ calc_next_hop(w, v);
+ }
+
+ if (d < w->cost) {
+ /* calc next hop */
+ calc_next_hop(w, v);
+
+ w->cost = d;
+ w->prev = v;
+ }
+ } else {
+ if (w->cost == LS_INFINITY) {
+ w->cost = 0;
+ w->cost += d;
+
+ cand_list_add(w);
+ w->prev = v;
+
+ /* calc next hop */
+ calc_next_hop(w, v);
+ }
+ }
+ }
+
+ cand_list_dump();
+
+ /* get next vertex */
+ v = cand_list_pop();
+ w = NULL;
+
+ } while (v != NULL);
+
+ /* calculate route table */
+ RB_FOREACH(v, lsa_tree, tree) {
+ if (ntohs(v->lsa->hdr.age) == MAX_AGE)
+ continue;
+
+ switch (v->type) {
+ case LSA_TYPE_ROUTER:
+ /* stub networks */
+ if ((v->cost == LS_INFINITY) ||
+ (v->nexthop.s_addr == 0))
+ continue;
+
+ for (i = 0; i < lsa_num_links(v); i++) {
+ rtr_link = get_rtr_link(v, i);
+ if (rtr_link->type != LINK_TYPE_STUB_NET)
+ continue;
+
+ addr.s_addr = rtr_link->id;
+
+ rt_update(addr, mask2prefixlen(rtr_link->data),
+ v->nexthop, v->cost +
+ ntohs(rtr_link->metric), PT_INTRA_AREA);
+ }
+ break;
+ case LSA_TYPE_NETWORK:
+ if ((v->cost == LS_INFINITY) ||
+ (v->nexthop.s_addr == 0))
+ continue;
+
+ addr.s_addr = htonl(v->ls_id) & v->lsa->data.net.mask;
+ rt_update(addr, mask2prefixlen(v->lsa->data.net.mask),
+ v->nexthop, v->cost, PT_INTRA_AREA);
+ break;
+ case LSA_TYPE_SUM_NETWORK:
+ if (rdeconf->flags & OSPF_RTR_B)
+ continue;
+
+ if ((w = lsa_find(area, LSA_TYPE_ROUTER,
+ htonl(v->adv_rtr),
+ htonl(v->adv_rtr))) == NULL)
+ continue;
+
+ v->nexthop = w->nexthop;
+ v->cost = w->cost +
+ ntohl(v->lsa->data.sum.metric);
+
+ if (v->nexthop.s_addr == 0)
+ continue;
+
+ addr.s_addr = htonl(v->ls_id) & v->lsa->data.sum.mask;
+ rt_update(addr, mask2prefixlen(v->lsa->data.sum.mask),
+ v->nexthop, v->cost, PT_INTER_AREA);
+ break;
+ case LSA_TYPE_SUM_ROUTER:
+ break;
+ case LSA_TYPE_EXTERNAL:
+ break;
+ default:
+ fatalx("spf_calc: invalid LSA type");
+ }
+ }
+
+ spf_dump(area);
+ rt_dump();
+ log_debug("spf_calc: calculation ended, area ID %s",
+ inet_ntoa(area->id));
+
+ start_spf_timer(rdeconf);
+
+ return ;
+}
+
+void
+spf_tree_clr(struct area *area)
+{
+ struct lsa_tree *tree = &area->lsa_tree;
+ struct vertex *v;
+
+ RB_FOREACH(v, lsa_tree, tree) {
+ v->cost = LS_INFINITY;
+ v->prev = NULL;
+ v->nexthop.s_addr = 0;
+ }
+}
+
+void
+calc_next_hop(struct vertex *dst, struct vertex *parent)
+{
+ struct lsa_rtr_link *rtr_link = NULL;
+ int i;
+
+ /* case 1 */
+ if (parent == spf_root) {
+ switch (dst->type) {
+ case LSA_TYPE_ROUTER:
+ /* XXX */
+ log_debug("calc_next_hop: router not handled");
+ break;
+ case LSA_TYPE_NETWORK:
+ /* XXX */
+ log_debug("calc_next_hop: net not handled");
+ break;
+ default:
+ fatalx("calc_next_hop: invalid dst type");
+ }
+
+ return ;
+ }
+
+ /* case 2 */
+ if (parent->type == LSA_TYPE_NETWORK && dst->type == LSA_TYPE_ROUTER &&
+ dst->prev == parent && parent->prev == spf_root) {
+ for (i = 0; i < lsa_num_links(dst); i++) {
+ rtr_link = get_rtr_link(dst, i);
+ if ((rtr_link->type == LINK_TYPE_TRANSIT_NET) &&
+ (rtr_link->data & parent->lsa->data.net.mask) ==
+ (htonl(parent->ls_id) & parent->lsa->data.net.mask))
+ dst->nexthop.s_addr = rtr_link->data;
+ }
+
+ return ;
+ }
+ /* case 3 */
+ dst->nexthop = parent->nexthop;
+
+ return ;
+}
+
+/* candidate list */
+void
+cand_list_init(void)
+{
+ TAILQ_INIT(&cand_list);
+}
+
+void
+cand_list_add(struct vertex *v)
+{
+ struct vertex *c = NULL;
+
+ /* XXX TODO: network vertex takes precedence over router vertex */
+ TAILQ_FOREACH(c, &cand_list, cand) {
+ if (c->cost > v->cost) {
+ TAILQ_INSERT_BEFORE(c, v, cand);
+ return;
+ }
+ }
+ TAILQ_INSERT_TAIL(&cand_list, v, cand);
+
+ return ;
+}
+
+void
+cand_list_dump(void)
+{
+ struct vertex *c = NULL;
+ struct in_addr addr;
+
+ log_debug("cand_list_dump:");
+ TAILQ_FOREACH(c, &cand_list, cand) {
+ addr.s_addr = htonl(c->ls_id);
+ log_debug(" id %s type %d cost %d", inet_ntoa(addr),
+ c->type, c->cost);
+ }
+ log_debug("");
+}
+
+struct vertex *
+cand_list_pop(void)
+{
+ struct vertex *c;
+
+ if ((c = TAILQ_FIRST(&cand_list)) != NULL) {
+ TAILQ_REMOVE(&cand_list, c, cand);
+ }
+
+ return (c);
+}
+
+bool
+cand_list_present(struct vertex *v)
+{
+ struct vertex *c;
+
+ TAILQ_FOREACH(c, &cand_list, cand) {
+ if (c == v)
+ return (true);
+ }
+
+ return (false);
+}
+
+void
+cand_list_clr(void)
+{
+ struct vertex *c;
+
+ while ((c = TAILQ_FIRST(&cand_list)) != NULL) {
+ TAILQ_REMOVE(&cand_list, c, cand);
+ }
+}
+
+bool
+cand_list_empty(void)
+{
+ return (TAILQ_EMPTY(&cand_list));
+}
+
+/* timers */
+void
+spf_timer(int fd, short event, void *arg)
+{
+ struct ospfd_conf *conf = arg;
+ struct area *area;
+
+ log_debug("spf_timer:");
+
+ switch (conf->spf_state) {
+ case SPF_IDLE:
+ fatalx("spf_timer: invalid state IDLE");
+ case SPF_HOLDQUEUE:
+ log_debug("spf_timer: HOLDQUEUE -> DELAY");
+ conf->spf_state = SPF_DELAY;
+ /* FALLTHROUGH */
+ case SPF_DELAY:
+ rt_clear(); /* XXX we should save to old rt! */
+ LIST_FOREACH(area, &conf->area_list, entry) {
+ spf_calc(area);
+ }
+ start_spf_holdtimer(rdeconf);
+ break;
+ case SPF_HOLD:
+ log_debug("spf_timer: state HOLD -> IDLE");
+ conf->spf_state = SPF_IDLE;
+ break;
+ default:
+ fatalx("spf_timer: unknown state");
+ }
+}
+
+int
+start_spf_timer(struct ospfd_conf *conf)
+{
+ struct timeval tv;
+
+ log_debug("start_spf_timer:");
+
+ switch (conf->spf_state) {
+ case SPF_IDLE:
+ log_debug("start_spf_timer: IDLE -> DELAY");
+ timerclear(&tv);
+ tv.tv_sec = conf->spf_delay;
+ conf->spf_state = SPF_DELAY;
+ return (evtimer_add(&conf->spf_timer, &tv));
+ case SPF_DELAY:
+ /* ignore */
+ break;
+ case SPF_HOLD:
+ log_debug("start_spf_timer: HOLD -> HOLDQUEUE");
+ conf->spf_state = SPF_HOLDQUEUE;
+ break;
+ case SPF_HOLDQUEUE:
+ break;
+ default:
+ fatalx("start_spf_timer: invalid spf_state");
+ }
+
+ return (1);
+}
+
+int
+stop_spf_timer(struct ospfd_conf *conf)
+{
+ return (evtimer_del(&conf->spf_timer));
+}
+
+int
+start_spf_holdtimer(struct ospfd_conf *conf)
+{
+ struct timeval tv;
+
+ switch (conf->spf_state) {
+ case SPF_DELAY:
+ timerclear(&tv);
+ tv.tv_sec = conf->spf_hold_time;
+ conf->spf_state = SPF_HOLD;
+ log_debug("spf_start_holdtimer: DELAY -> HOLD");
+ return (evtimer_add(&conf->spf_timer, &tv));
+ case SPF_IDLE:
+ case SPF_HOLD:
+ case SPF_HOLDQUEUE:
+ fatalx("start_spf_holdtimer: invalid state");
+ default:
+ fatalx("spf_start_holdtimer: unknown state");
+ }
+
+ return (1);
+}
+
+/* route table */
+void
+rt_init(void)
+{
+ RB_INIT(&rt);
+}
+
+int
+rt_compare(struct rt_node *a, struct rt_node *b)
+{
+ if (ntohl(a->prefix.s_addr) < ntohl(b->prefix.s_addr))
+ return (-1);
+ if (ntohl(a->prefix.s_addr) > ntohl(b->prefix.s_addr))
+ return (1);
+ if (a->prefixlen < b->prefixlen)
+ return (-1);
+ if (a->prefixlen > b->prefixlen)
+ return (1);
+ return (0);
+}
+
+struct rt_node *
+rt_find(in_addr_t prefix, u_int8_t prefixlen)
+{
+ struct rt_node s;
+
+ s.prefix.s_addr = prefix;
+ s.prefixlen = prefixlen;
+
+ return (RB_FIND(rt_tree, &rt, &s));
+}
+
+int
+rt_insert(struct rt_node *r)
+{
+ if (RB_INSERT(rt_tree, &rt, r) != NULL) {
+ log_warnx("rt_insert failed for %s/%u",
+ inet_ntoa(r->prefix), r->prefixlen);
+ free(r);
+ return (-1);
+ }
+
+ return (0);
+}
+
+int
+rt_remove(struct rt_node *r)
+{
+ if (RB_REMOVE(rt_tree, &rt, r) == NULL) {
+ log_warnx("rt_remove failed for %s/%u",
+ inet_ntoa(r->prefix), r->prefixlen);
+ return (-1);
+ }
+
+ free(r);
+ return (0);
+}
+
+void
+rt_clear(void)
+{
+ struct rt_node *r;
+
+ while ((r = RB_MIN(rt_tree, &rt)) != NULL)
+ rt_remove(r);
+}
+
+void
+rt_update(struct in_addr prefix, u_int8_t prefixlen, struct in_addr nexthop,
+ u_int32_t cost, u_int8_t p_type)
+{
+ struct rt_node *rte;
+
+ if ((rte = rt_find(prefix.s_addr, prefixlen)) == NULL) {
+ log_debug("rt_update: creating %s/%d", inet_ntoa(prefix),
+ prefixlen);
+ if ((rte = calloc(1, sizeof(struct rt_node))) == NULL)
+ fatalx("rt_update");
+ rte->prefix.s_addr = prefix.s_addr;
+ rte->prefixlen = prefixlen;
+ rte->nexthop.s_addr = nexthop.s_addr;
+ rte->cost = cost;
+ rte->p_type = p_type;
+
+ rt_insert(rte);
+ } else {
+ log_debug("rt_update: updating %s/%d", inet_ntoa(prefix),
+ prefixlen);
+
+ /* XXX better route ? */
+ /* consider intra vs. inter */
+ if (cost < rte->cost) {
+ rte->nexthop.s_addr = nexthop.s_addr;
+ rte->cost = cost;
+ rte->p_type = p_type;
+ }
+ }
+}
+
+/* router LSA links */
+struct lsa_rtr_link *
+get_rtr_link(struct vertex *v, int idx)
+{
+ struct lsa_rtr_link *rtr_link = NULL;
+ char *buf = (char *)v->lsa;
+ u_int16_t i, off, nlinks;
+
+ if (v->type != LSA_TYPE_ROUTER)
+ fatalx("get_rtr_link: invalid LSA type");
+
+ off = sizeof(v->lsa->hdr) + sizeof(struct lsa_rtr);
+
+ nlinks = lsa_num_links(v);
+ for (i = 0; i < nlinks; i++) {
+ rtr_link = (struct lsa_rtr_link *)(buf + off);
+ if (i == idx)
+ return (rtr_link);
+
+ off += sizeof(struct lsa_rtr_link) +
+ rtr_link->num_tos * sizeof(u_int32_t);
+ }
+
+ return (NULL);
+}
+
+/* network LSA links */
+struct lsa_net_link *
+get_net_link(struct vertex *v, int idx)
+{
+ struct lsa_net_link *net_link = NULL;
+ char *buf = (char *)v->lsa;
+ u_int16_t i, off, nlinks;
+
+ if (v->type != LSA_TYPE_NETWORK)
+ fatalx("get_net_link: invalid LSA type");
+
+ off = sizeof(v->lsa->hdr) + sizeof(u_int32_t);
+
+ nlinks = lsa_num_links(v);
+ for (i = 0; i < nlinks; i++) {
+ net_link = (struct lsa_net_link *)(buf + off);
+ if (i == idx)
+ return (net_link);
+
+ off += sizeof(struct lsa_net_link);
+ }
+
+ return (NULL);
+}
+
+/* misc */
+bool
+linked(struct vertex *w, struct vertex *v)
+{
+ struct lsa_rtr_link *rtr_link = NULL;
+ struct lsa_net_link *net_link = NULL;
+ int i;
+
+ switch (w->type) {
+ case LSA_TYPE_ROUTER:
+ for (i = 0; i < lsa_num_links(w); i++) {
+ rtr_link = get_rtr_link(w, i);
+ switch (v->type) {
+ case LSA_TYPE_ROUTER:
+ if (rtr_link->type == LINK_TYPE_POINTTOPOINT &&
+ rtr_link->id == htonl(v->ls_id))
+ return (true);
+ break;
+ case LSA_TYPE_NETWORK:
+ if (rtr_link->id == htonl(v->ls_id))
+ return (true);
+ break;
+ default:
+ fatalx("spf_calc: invalid type");
+ }
+ }
+ return (false);
+ case LSA_TYPE_NETWORK:
+ for (i = 0; i < lsa_num_links(w); i++) {
+ net_link = get_net_link(w, i);
+ switch (v->type) {
+ case LSA_TYPE_ROUTER:
+ if (net_link->att_rtr == htonl(v->ls_id))
+ return (true);
+ break;
+ default:
+ fatalx("spf_calc: invalid type");
+ }
+ }
+ return (false);
+ default:
+ fatalx("spf_calc: invalid LSA type");
+ }
+
+ return (false);
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-29 06:01:31 +0000