diff options
Diffstat (limited to 'ospfd')
| -rw-r--r-- | ospfd/ospf_lsa.h | 7 | ||||
| -rw-r--r-- | ospfd/ospf_lsdb.c | 15 | ||||
| -rw-r--r-- | ospfd/ospf_lsdb.h | 2 | ||||
| -rw-r--r-- | ospfd/ospf_spf.c | 107 | ||||
| -rw-r--r-- | ospfd/ospf_spf.h | 6 |
5 files changed, 59 insertions, 78 deletions
diff --git a/ospfd/ospf_lsa.h b/ospfd/ospf_lsa.h index a381cf714..5e3dabc27 100644 --- a/ospfd/ospf_lsa.h +++ b/ospfd/ospf_lsa.h @@ -69,6 +69,8 @@ struct lsa_header { uint16_t length; }; +struct vertex; + /* OSPF LSA. */ struct ospf_lsa { /* LSA origination flag. */ @@ -95,10 +97,7 @@ struct ospf_lsa { int lock; /* Flags for the SPF calculation. */ - int stat; -#define LSA_SPF_NOT_EXPLORED -1 -#define LSA_SPF_IN_SPFTREE -2 - /* If stat >= 0, stat is LSA position in candidates heap. */ + struct vertex *stat; /* References to this LSA in neighbor retransmission lists*/ int retransmit_counter; diff --git a/ospfd/ospf_lsdb.c b/ospfd/ospf_lsdb.c index 2e850c4e2..86eb14131 100644 --- a/ospfd/ospf_lsdb.c +++ b/ospfd/ospf_lsdb.c @@ -169,21 +169,6 @@ void ospf_lsdb_delete_all(struct ospf_lsdb *lsdb) } } -void ospf_lsdb_clean_stat(struct ospf_lsdb *lsdb) -{ - struct route_table *table; - struct route_node *rn; - struct ospf_lsa *lsa; - int i; - - for (i = OSPF_MIN_LSA; i < OSPF_MAX_LSA; i++) { - table = lsdb->type[i].db; - for (rn = route_top(table); rn; rn = route_next(rn)) - if ((lsa = (rn->info)) != NULL) - lsa->stat = LSA_SPF_NOT_EXPLORED; - } -} - struct ospf_lsa *ospf_lsdb_lookup(struct ospf_lsdb *lsdb, struct ospf_lsa *lsa) { struct route_table *table; diff --git a/ospfd/ospf_lsdb.h b/ospfd/ospf_lsdb.h index 65c7e28fe..5cf5d0544 100644 --- a/ospfd/ospf_lsdb.h +++ b/ospfd/ospf_lsdb.h @@ -67,8 +67,6 @@ extern void ls_prefix_set(struct prefix_ls *lp, struct ospf_lsa *lsa); extern void ospf_lsdb_add(struct ospf_lsdb *, struct ospf_lsa *); extern void ospf_lsdb_delete(struct ospf_lsdb *, struct ospf_lsa *); extern void ospf_lsdb_delete_all(struct ospf_lsdb *); -/* Set all stats to -1 (LSA_SPF_NOT_EXPLORED). */ -extern void ospf_lsdb_clean_stat(struct ospf_lsdb *lsdb); extern struct ospf_lsa *ospf_lsdb_lookup(struct ospf_lsdb *, struct ospf_lsa *); extern struct ospf_lsa *ospf_lsdb_lookup_by_id(struct ospf_lsdb *, uint8_t, struct in_addr, struct in_addr); diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c index 6e03fa9bd..296a05bdf 100644 --- a/ospfd/ospf_spf.c +++ b/ospfd/ospf_spf.c @@ -30,7 +30,6 @@ #include "table.h" #include "log.h" #include "sockunion.h" /* for inet_ntop () */ -#include "pqueue.h" #include "ospfd/ospfd.h" #include "ospfd/ospf_interface.h" @@ -53,6 +52,11 @@ static unsigned int spf_reason_flags = 0; +/* dummy vertex to flag "in spftree" */ +static const struct vertex vertex_in_spftree = {}; +#define LSA_SPF_IN_SPFTREE (struct vertex *)&vertex_in_spftree +#define LSA_SPF_NOT_EXPLORED NULL + static void ospf_clear_spf_reason_flags(void) { spf_reason_flags = 0; @@ -72,35 +76,36 @@ static struct list vertex_list = {.del = ospf_vertex_free}; /* Heap related functions, for the managment of the candidates, to * be used with pqueue. */ -static int cmp(void *node1, void *node2) +static int vertex_cmp(const struct vertex *v1, const struct vertex *v2) { - struct vertex *v1 = (struct vertex *)node1; - struct vertex *v2 = (struct vertex *)node2; - if (v1 != NULL && v2 != NULL) { - /* network vertices must be chosen before router vertices of - * same - * cost in order to find all shortest paths - */ - if (((v1->distance - v2->distance) == 0) - && (v1->type != v2->type)) { - switch (v1->type) { - case OSPF_VERTEX_NETWORK: - return -1; - case OSPF_VERTEX_ROUTER: - return 1; - } - } else - return (v1->distance - v2->distance); + if (v1->distance != v2->distance) + return v1->distance - v2->distance; + + if (v1->type != v2->type) { + switch (v1->type) { + case OSPF_VERTEX_NETWORK: + return -1; + case OSPF_VERTEX_ROUTER: + return 1; + } } return 0; } +DECLARE_SKIPLIST_NONUNIQ(vertex_pqueue, struct vertex, pqi, vertex_cmp) -static void update_stat(void *node, int position) +static void lsdb_clean_stat(struct ospf_lsdb *lsdb) { - struct vertex *v = node; - - /* Set the status of the vertex, when its position changes. */ - *(v->stat) = position; + struct route_table *table; + struct route_node *rn; + struct ospf_lsa *lsa; + int i; + + for (i = OSPF_MIN_LSA; i < OSPF_MAX_LSA; i++) { + table = lsdb->type[i].db; + for (rn = route_top(table); rn; rn = route_next(rn)) + if ((lsa = (rn->info)) != NULL) + lsa->stat = LSA_SPF_NOT_EXPLORED; + } } static struct vertex_nexthop *vertex_nexthop_new(void) @@ -179,7 +184,6 @@ static struct vertex *ospf_vertex_new(struct ospf_lsa *lsa) new = XCALLOC(MTYPE_OSPF_VERTEX, sizeof(struct vertex)); new->flags = 0; - new->stat = &(lsa->stat); new->type = lsa->data->type; new->id = lsa->data->id; new->lsa = lsa->data; @@ -187,6 +191,9 @@ static struct vertex *ospf_vertex_new(struct ospf_lsa *lsa) new->parents = list_new(); new->parents->del = vertex_parent_free; new->parents->cmp = vertex_parent_cmp; + new->lsa_p = lsa; + + lsa->stat = new; listnode_add(&vertex_list, new); @@ -786,7 +793,8 @@ static unsigned int ospf_nexthop_calculation(struct ospf_area *area, * path is found to a vertex already on the candidate list, store the new cost. */ static void ospf_spf_next(struct vertex *v, struct ospf *ospf, - struct ospf_area *area, struct pqueue *candidate) + struct ospf_area *area, + struct vertex_pqueue_head *candidate) { struct ospf_lsa *w_lsa = NULL; uint8_t *p; @@ -935,13 +943,11 @@ static void ospf_spf_next(struct vertex *v, struct ospf *ospf, /* Calculate nexthop to W. */ if (ospf_nexthop_calculation(area, v, w, l, distance, lsa_pos)) - pqueue_enqueue(w, candidate); + vertex_pqueue_add(candidate, w); else if (IS_DEBUG_OSPF_EVENT) zlog_debug("Nexthop Calc failed"); - } else if (w_lsa->stat >= 0) { - /* Get the vertex from candidates. */ - w = candidate->array[w_lsa->stat]; - + } else if (w_lsa->stat != LSA_SPF_IN_SPFTREE) { + w = w_lsa->stat; /* if D is greater than. */ if (w->distance < distance) { continue; @@ -962,18 +968,10 @@ static void ospf_spf_next(struct vertex *v, struct ospf *ospf, * which * will flush the old parents */ - if (ospf_nexthop_calculation(area, v, w, l, - distance, lsa_pos)) - /* Decrease the key of the node in the - * heap. - * trickle-sort it up towards root, just - * in case this - * node should now be the new root due - * the cost change. - * (next pqueu_{de,en}queue will fully - * re-heap the queue). - */ - trickle_up(w_lsa->stat, candidate); + vertex_pqueue_del(candidate, w); + ospf_nexthop_calculation(area, v, w, l, + distance, lsa_pos); + vertex_pqueue_add(candidate, w); } } /* end W is already on the candidate list */ } /* end loop over the links in V's LSA */ @@ -1169,7 +1167,7 @@ static void ospf_spf_calculate(struct ospf *ospf, struct ospf_area *area, struct route_table *new_table, struct route_table *new_rtrs) { - struct pqueue *candidate; + struct vertex_pqueue_head candidate; struct vertex *v; if (IS_DEBUG_OSPF_EVENT) { @@ -1194,11 +1192,9 @@ static void ospf_spf_calculate(struct ospf *ospf, struct ospf_area *area, /* This function scans all the LSA database and set the stat field to * LSA_SPF_NOT_EXPLORED. */ - ospf_lsdb_clean_stat(area->lsdb); + lsdb_clean_stat(area->lsdb); /* Create a new heap for the candidates. */ - candidate = pqueue_create(); - candidate->cmp = cmp; - candidate->update = update_stat; + vertex_pqueue_init(&candidate); /* Initialize the shortest-path tree to only the root (which is the router doing the calculation). */ @@ -1207,7 +1203,7 @@ static void ospf_spf_calculate(struct ospf *ospf, struct ospf_area *area, /* Set LSA position to LSA_SPF_IN_SPFTREE. This vertex is the root of * the * spanning tree. */ - *(v->stat) = LSA_SPF_IN_SPFTREE; + v->lsa_p->stat = LSA_SPF_IN_SPFTREE; /* Set Area A's TransitCapability to FALSE. */ area->transit = OSPF_TRANSIT_FALSE; @@ -1215,23 +1211,22 @@ static void ospf_spf_calculate(struct ospf *ospf, struct ospf_area *area, for (;;) { /* RFC2328 16.1. (2). */ - ospf_spf_next(v, ospf, area, candidate); + ospf_spf_next(v, ospf, area, &candidate); /* RFC2328 16.1. (3). */ /* If at this step the candidate list is empty, the shortest- path tree (of transit vertices) has been completely built and this stage of the procedure terminates. */ - if (candidate->size == 0) - break; - /* Otherwise, choose the vertex belonging to the candidate list that is closest to the root, and add it to the shortest-path tree (removing it from the candidate list in the process). */ /* Extract from the candidates the node with the lower key. */ - v = (struct vertex *)pqueue_dequeue(candidate); + v = vertex_pqueue_pop(&candidate); + if (!v) + break; /* Update stat field in vertex. */ - *(v->stat) = LSA_SPF_IN_SPFTREE; + v->lsa_p->stat = LSA_SPF_IN_SPFTREE; ospf_vertex_add_parent(v); @@ -1255,7 +1250,7 @@ static void ospf_spf_calculate(struct ospf *ospf, struct ospf_area *area, ospf_spf_process_stubs(area, area->spf, new_table, 0); /* Free candidate queue. */ - pqueue_delete(candidate); + //vertex_pqueue_fini(&candidate); ospf_vertex_dump(__func__, area->spf, 0, 1); /* Free nexthop information, canonical versions of which are attached diff --git a/ospfd/ospf_spf.h b/ospfd/ospf_spf.h index 85f42bcd1..09a0b6f1b 100644 --- a/ospfd/ospf_spf.h +++ b/ospfd/ospf_spf.h @@ -22,6 +22,8 @@ #ifndef _QUAGGA_OSPF_SPF_H #define _QUAGGA_OSPF_SPF_H +#include "typesafe.h" + /* values for vertex->type */ #define OSPF_VERTEX_ROUTER 1 /* for a Router-LSA */ #define OSPF_VERTEX_NETWORK 2 /* for a Network-LSA */ @@ -31,13 +33,15 @@ /* The "root" is the node running the SPF calculation */ +PREDECL_SKIPLIST_NONUNIQ(vertex_pqueue) /* A router or network in an area */ struct vertex { + struct vertex_pqueue_item pqi; uint8_t flags; uint8_t type; /* copied from LSA header */ struct in_addr id; /* copied from LSA header */ + struct ospf_lsa *lsa_p; struct lsa_header *lsa; /* Router or Network LSA */ - int *stat; /* Link to LSA status. */ uint32_t distance; /* from root to this vertex */ struct list *parents; /* list of parents in SPF tree */ struct list *children; /* list of children in SPF tree*/ |