/*
- * Copyright (C) 1999 Yasuhiro Ohara
+ * Copyright (C) 2003 Yasuhiro Ohara
*
* This file is part of GNU Zebra.
*
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* General Public License for more details.
*
- * You should have received a copy of the GNU General Public License
- * along with GNU Zebra; see the file COPYING. If not, write to the
- * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
- * Boston, MA 02111-1307, USA.
+ * You should have received a copy of the GNU General Public License along
+ * with this program; see the file COPYING; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
*/
#ifndef OSPF6_SPF_H
#define OSPF6_SPF_H
-#include "prefix.h"
+#include "typesafe.h"
+#include "ospf6_top.h"
+/* Debug option */
+extern unsigned char conf_debug_ospf6_spf;
+#define OSPF6_DEBUG_SPF_PROCESS 0x01
+#define OSPF6_DEBUG_SPF_TIME 0x02
+#define OSPF6_DEBUG_SPF_DATABASE 0x04
+#define OSPF6_DEBUG_SPF_ON(level) (conf_debug_ospf6_spf |= (level))
+#define OSPF6_DEBUG_SPF_OFF(level) (conf_debug_ospf6_spf &= ~(level))
+#define IS_OSPF6_DEBUG_SPF(level) \
+ (conf_debug_ospf6_spf & OSPF6_DEBUG_SPF_##level)
+
+PREDECL_SKIPLIST_NONUNIQ(vertex_pqueue)
/* Transit Vertex */
-struct ospf6_vertex
-{
- /* type of this vertex */
- u_int8_t type;
+struct ospf6_vertex {
+ /* type of this vertex */
+ uint8_t type;
- /* Vertex Identifier */
- struct prefix_ls vertex_id;
+ /* Vertex Identifier */
+ struct prefix vertex_id;
- /* Identifier String */
- char string[128];
+ struct vertex_pqueue_item pqi;
- /* Associated LSA */
- struct ospf6_lsa *lsa;
+ /* Identifier String */
+ char name[128];
- /* Distance from Root (Cost) */
- u_int16_t distance;
+ /* Associated Area */
+ struct ospf6_area *area;
- /* Depth of this node */
- u_char depth;
+ /* Associated LSA */
+ struct ospf6_lsa *lsa;
- /* nexthops to this node */
- struct linklist *nexthop_list;
+ /* Distance from Root (i.e. Cost) */
+ uint32_t cost;
- /* upper nodes in spf tree */
- list parent_list;
+ /* Router hops to this node */
+ uint8_t hops;
- /* lower nodes in spf tree */
- list path_list;
+ /* capability bits */
+ uint8_t capability;
- /* capability bits */
- u_char capability_bits;
+ /* Optional capabilities */
+ uint8_t options[3];
- /* Optional capabilities */
- u_char opt_capability[3];
+ /* For tree display */
+ struct ospf6_vertex *parent;
+ struct list *child_list;
+
+ /* nexthops to this node */
+ struct list *nh_list;
+ uint32_t link_id;
};
#define OSPF6_VERTEX_TYPE_ROUTER 0x01
#define OSPF6_VERTEX_TYPE_NETWORK 0x02
-
-struct ospf6_spftree
+#define VERTEX_IS_TYPE(t, v) ((v)->type == OSPF6_VERTEX_TYPE_##t ? 1 : 0)
+
+/* What triggered the SPF? */
+#define OSPF6_SPF_FLAGS_ROUTER_LSA_ADDED (1 << 0)
+#define OSPF6_SPF_FLAGS_ROUTER_LSA_REMOVED (1 << 1)
+#define OSPF6_SPF_FLAGS_NETWORK_LSA_ADDED (1 << 2)
+#define OSPF6_SPF_FLAGS_NETWORK_LSA_REMOVED (1 << 3)
+#define OSPF6_SPF_FLAGS_LINK_LSA_ADDED (1 << 4)
+#define OSPF6_SPF_FLAGS_LINK_LSA_REMOVED (1 << 5)
+#define OSPF6_SPF_FLAGS_ROUTER_LSA_ORIGINATED (1 << 6)
+#define OSPF6_SPF_FLAGS_NETWORK_LSA_ORIGINATED (1 << 7)
+
+static inline void ospf6_set_spf_reason(struct ospf6 *ospf, unsigned int reason)
{
- /* calculation thread */
- struct thread *t_spf_calculation;
-
- /* root of this tree */
- struct ospf6_vertex *root;
-
- /* list for search */
- list list;
-
- /* statistics */
- u_int32_t timerun;
-
- struct timeval runtime_total;
- struct timeval runtime_min;
- struct timeval runtime_max;
+ ospf->spf_reason |= reason;
+}
- struct timeval updated_time;
- struct timeval interval_total;
- struct timeval interval_min;
- struct timeval interval_max;
-};
-
-int ospf6_spf_calculate_route (void *);
-
-void
-ospf6_spf_calculation_schedule (u_int32_t area_id);
-struct ospf6_spftree *ospf6_spftree_create ();
-void
-ospf6_spf_statistics_show (struct vty *vty, struct ospf6_spftree *spf_tree);
-void ospf6_spftree_delete (struct ospf6_spftree *spf_tree);
-
-void ospf6_spf_database_hook (struct ospf6_lsa *old, struct ospf6_lsa *new);
+static inline void ospf6_reset_spf_reason(struct ospf6 *ospf)
+{
+ ospf->spf_reason = 0;
+}
-void ospf6_spf_init ();
+static inline unsigned int ospf6_lsadd_to_spf_reason(struct ospf6_lsa *lsa)
+{
+ unsigned int reason = 0;
+
+ switch (ntohs(lsa->header->type)) {
+ case OSPF6_LSTYPE_ROUTER:
+ reason = OSPF6_SPF_FLAGS_ROUTER_LSA_ADDED;
+ break;
+ case OSPF6_LSTYPE_NETWORK:
+ reason = OSPF6_SPF_FLAGS_NETWORK_LSA_ADDED;
+ break;
+ case OSPF6_LSTYPE_LINK:
+ reason = OSPF6_SPF_FLAGS_LINK_LSA_ADDED;
+ break;
+ default:
+ break;
+ }
+ return (reason);
+}
+
+static inline unsigned int ospf6_lsremove_to_spf_reason(struct ospf6_lsa *lsa)
+{
+ unsigned int reason = 0;
+
+ switch (ntohs(lsa->header->type)) {
+ case OSPF6_LSTYPE_ROUTER:
+ reason = OSPF6_SPF_FLAGS_ROUTER_LSA_REMOVED;
+ break;
+ case OSPF6_LSTYPE_NETWORK:
+ reason = OSPF6_SPF_FLAGS_NETWORK_LSA_REMOVED;
+ break;
+ case OSPF6_LSTYPE_LINK:
+ reason = OSPF6_SPF_FLAGS_LINK_LSA_REMOVED;
+ break;
+ default:
+ break;
+ }
+ return (reason);
+}
+
+extern void ospf6_spf_table_finish(struct ospf6_route_table *result_table);
+extern void ospf6_spf_calculation(uint32_t router_id,
+ struct ospf6_route_table *result_table,
+ struct ospf6_area *oa);
+extern void ospf6_spf_schedule(struct ospf6 *ospf, unsigned int reason);
+
+extern void ospf6_spf_display_subtree(struct vty *vty, const char *prefix,
+ int rest, struct ospf6_vertex *v);
+
+extern void ospf6_spf_config_write(struct vty *vty);
+extern int config_write_ospf6_debug_spf(struct vty *vty);
+extern void install_element_ospf6_debug_spf(void);
+extern void ospf6_spf_init(void);
+extern void ospf6_spf_reason_string(unsigned int reason, char *buf, int size);
+extern struct ospf6_lsa *ospf6_create_single_router_lsa(struct ospf6_area *area,
+ struct ospf6_lsdb *lsdb,
+ uint32_t adv_router);
+extern void ospf6_remove_temp_router_lsa(struct ospf6_area *area);
#endif /* OSPF6_SPF_H */
-