diff options
| -rw-r--r-- | isisd/isis_misc.c | 21 | ||||
| -rw-r--r-- | isisd/isis_misc.h | 1 | ||||
| -rw-r--r-- | isisd/isis_spf.c | 330 | ||||
| -rw-r--r-- | isisd/isis_spf.h | 49 | ||||
| -rw-r--r-- | isisd/isisd.c | 45 | ||||
| -rw-r--r-- | lib/hash.c | 39 | ||||
| -rw-r--r-- | lib/prefix.c | 13 | ||||
| -rw-r--r-- | lib/prefix.h | 2 | ||||
| -rw-r--r-- | lib/table.c | 15 |
9 files changed, 296 insertions, 219 deletions
diff --git a/isisd/isis_misc.c b/isisd/isis_misc.c index 4d7b4c381a..c872774da8 100644 --- a/isisd/isis_misc.c +++ b/isisd/isis_misc.c @@ -601,3 +601,24 @@ void vty_multiline(struct vty *vty, const char *prefix, const char *format, ...) XFREE(MTYPE_TMP, p); } + +void vty_out_timestr(struct vty *vty, time_t uptime) +{ + struct tm *tm; + time_t difftime = time(NULL); + difftime -= uptime; + tm = gmtime(&difftime); + +#define ONE_DAY_SECOND 60*60*24 +#define ONE_WEEK_SECOND 60*60*24*7 + if (difftime < ONE_DAY_SECOND) + vty_out(vty, "%02d:%02d:%02d", tm->tm_hour, tm->tm_min, + tm->tm_sec); + else if (difftime < ONE_WEEK_SECOND) + vty_out(vty, "%dd%02dh%02dm", tm->tm_yday, tm->tm_hour, + tm->tm_min); + else + vty_out(vty, "%02dw%dd%02dh", tm->tm_yday / 7, + tm->tm_yday - ((tm->tm_yday / 7) * 7), tm->tm_hour); + vty_out(vty, " ago"); +} diff --git a/isisd/isis_misc.h b/isisd/isis_misc.h index 7de534ec7b..5a19a1ffa0 100644 --- a/isisd/isis_misc.h +++ b/isisd/isis_misc.h @@ -84,4 +84,5 @@ void log_multiline(int priority, const char *prefix, const char *format, ...) struct vty; void vty_multiline(struct vty *vty, const char *prefix, const char *format, ...) PRINTF_ATTRIBUTE(3, 4); +void vty_out_timestr(struct vty *vty, time_t uptime); #endif diff --git a/isisd/isis_spf.c b/isisd/isis_spf.c index 740f087ee7..9acbc21838 100644 --- a/isisd/isis_spf.c +++ b/isisd/isis_spf.c @@ -35,6 +35,7 @@ #include "if.h" #include "table.h" #include "spf_backoff.h" +#include "jhash.h" #include "isis_constants.h" #include "isis_common.h" @@ -55,6 +56,160 @@ DEFINE_MTYPE_STATIC(ISISD, ISIS_SPF_RUN, "ISIS SPF Run Info"); +enum vertextype { + VTYPE_PSEUDO_IS = 1, + VTYPE_PSEUDO_TE_IS, + VTYPE_NONPSEUDO_IS, + VTYPE_NONPSEUDO_TE_IS, + VTYPE_ES, + VTYPE_IPREACH_INTERNAL, + VTYPE_IPREACH_EXTERNAL, + VTYPE_IPREACH_TE, + VTYPE_IP6REACH_INTERNAL, + VTYPE_IP6REACH_EXTERNAL +}; + +#define VTYPE_IS(t) ((t) >= VTYPE_PSEUDO_IS && (t) <= VTYPE_NONPSEUDO_TE_IS) +#define VTYPE_ES(t) ((t) == VTYPE_ES) +#define VTYPE_IP(t) ((t) >= VTYPE_IPREACH_INTERNAL && (t) <= VTYPE_IP6REACH_EXTERNAL) + +/* + * Triple <N, d(N), {Adj(N)}> + */ +struct isis_vertex { + enum vertextype type; + + union { + u_char id[ISIS_SYS_ID_LEN + 1]; + struct prefix prefix; + } N; + + u_int32_t d_N; /* d(N) Distance from this IS */ + u_int16_t depth; /* The depth in the imaginary tree */ + struct list *Adj_N; /* {Adj(N)} next hop or neighbor list */ + struct list *parents; /* list of parents for ECMP */ + struct list *children; /* list of children used for tree dump */ +}; + +/* Vertex Queue and associated functions */ + +struct isis_vertex_queue { + struct list *list; + struct hash *hash; +}; + +static unsigned isis_vertex_queue_hash_key(void *vp) +{ + struct isis_vertex *vertex = vp; + + if (VTYPE_IP(vertex->type)) + return prefix_hash_key(&vertex->N.prefix); + + return jhash(vertex->N.id, ISIS_SYS_ID_LEN + 1, 0x55aa5a5a); +} + +static int isis_vertex_queue_hash_cmp(const void *a, const void *b) +{ + const struct isis_vertex *va = a, *vb = b; + + if (va->type != vb->type) + return 0; + + if (VTYPE_IP(va->type)) + return prefix_cmp(&va->N.prefix, &vb->N.prefix) == 0; + + return memcmp(va->N.id, vb->N.id, ISIS_SYS_ID_LEN + 1) == 0; +} + +static void isis_vertex_queue_init(struct isis_vertex_queue *queue, const char *name) +{ + queue->list = list_new(); + queue->hash = hash_create(isis_vertex_queue_hash_key, + isis_vertex_queue_hash_cmp, + name); +} + +static void isis_vertex_del(struct isis_vertex *vertex); + +static void isis_vertex_queue_clear(struct isis_vertex_queue *queue) +{ + hash_clean(queue->hash, NULL); + + queue->list->del = (void (*)(void *))isis_vertex_del; + list_delete_all_node(queue->list); + queue->list->del = NULL; +} + +static void isis_vertex_queue_free(struct isis_vertex_queue *queue) +{ + isis_vertex_queue_clear(queue); + + hash_free(queue->hash); + queue->hash = NULL; + + list_delete(queue->list); + queue->list = NULL; +} + +static unsigned int isis_vertex_queue_count(struct isis_vertex_queue *queue) +{ + return listcount(queue->list); +} + +static void isis_vertex_queue_add(struct isis_vertex_queue *queue, + struct isis_vertex *vertex) +{ + listnode_add(queue->list, vertex); + + struct isis_vertex *inserted; + + inserted = hash_get(queue->hash, vertex, hash_alloc_intern); + assert(inserted == vertex); +} + +static struct isis_vertex *isis_vertex_queue_pop(struct isis_vertex_queue *queue) +{ + struct listnode *node; + + node = listhead(queue->list); + if (!node) + return NULL; + + struct isis_vertex *rv = listgetdata(node); + + list_delete_node(queue->list, node); + hash_release(queue->hash, rv); + + return rv; +} + +static void isis_vertex_queue_delete(struct isis_vertex_queue *queue, + struct isis_vertex *vertex) +{ + listnode_delete(queue->list, vertex); + hash_release(queue->hash, vertex); +} + +#define ALL_QUEUE_ELEMENTS_RO(queue, node, data) \ + ALL_LIST_ELEMENTS_RO((queue)->list, node, data) + + +/* End of vertex queue definitions */ + +struct isis_spftree { + struct isis_vertex_queue paths; /* the SPT */ + struct isis_vertex_queue tents; /* TENT */ + struct isis_area *area; /* back pointer to area */ + unsigned int runcount; /* number of runs since uptime */ + time_t last_run_timestamp; /* last run timestamp for scheduling */ + time_t last_run_duration; /* last run duration in msec */ + + uint16_t mtid; + int family; + int level; +}; + + /* * supports the given af ? */ @@ -174,12 +329,8 @@ static const char *vid2string(struct isis_vertex *vertex, char *buff, int size) return "UNKNOWN"; } -static struct isis_vertex *isis_vertex_new(void *id, enum vertextype vtype) +static void isis_vertex_id_init(struct isis_vertex *vertex, void *id, enum vertextype vtype) { - struct isis_vertex *vertex; - - vertex = XCALLOC(MTYPE_ISIS_VERTEX, sizeof(struct isis_vertex)); - vertex->type = vtype; if (VTYPE_IS(vtype) || VTYPE_ES(vtype)) { @@ -190,6 +341,15 @@ static struct isis_vertex *isis_vertex_new(void *id, enum vertextype vtype) } else { zlog_err("WTF!"); } +} + +static struct isis_vertex *isis_vertex_new(void *id, enum vertextype vtype) +{ + struct isis_vertex *vertex; + + vertex = XCALLOC(MTYPE_ISIS_VERTEX, sizeof(struct isis_vertex)); + + isis_vertex_id_init(vertex, id, vtype); vertex->Adj_N = list_new(); vertex->parents = list_new(); @@ -237,8 +397,8 @@ struct isis_spftree *isis_spftree_new(struct isis_area *area) return NULL; } - tree->tents = list_new(); - tree->paths = list_new(); + isis_vertex_queue_init(&tree->tents, "IS-IS SPF tents"); + isis_vertex_queue_init(&tree->paths, "IS-IS SPF paths"); tree->area = area; tree->last_run_timestamp = 0; tree->last_run_duration = 0; @@ -248,15 +408,8 @@ struct isis_spftree *isis_spftree_new(struct isis_area *area) void isis_spftree_del(struct isis_spftree *spftree) { - - spftree->tents->del = (void (*)(void *))isis_vertex_del; - list_delete(spftree->tents); - spftree->tents = NULL; - - spftree->paths->del = (void (*)(void *))isis_vertex_del; - list_delete(spftree->paths); - spftree->paths = NULL; - + isis_vertex_queue_free(&spftree->tents); + isis_vertex_queue_free(&spftree->paths); XFREE(MTYPE_ISIS_SPFTREE, spftree); return; @@ -266,12 +419,13 @@ static void isis_spftree_adj_del(struct isis_spftree *spftree, struct isis_adjacency *adj) { struct listnode *node; + struct isis_vertex *v; if (!adj) return; - for (node = listhead(spftree->tents); node; node = listnextnode(node)) - isis_vertex_adj_del(listgetdata(node), adj); - for (node = listhead(spftree->paths); node; node = listnextnode(node)) - isis_vertex_adj_del(listgetdata(node), adj); + for (ALL_QUEUE_ELEMENTS_RO(&spftree->tents, node, v)) + isis_vertex_adj_del(v, adj); + for (ALL_QUEUE_ELEMENTS_RO(&spftree->paths, node, v)) + isis_vertex_adj_del(v, adj); return; } @@ -384,7 +538,7 @@ static struct isis_vertex *isis_spf_add_root(struct isis_spftree *spftree, spftree->area->oldmetric ? VTYPE_NONPSEUDO_IS : VTYPE_NONPSEUDO_TE_IS); - listnode_add(spftree->paths, vertex); + isis_vertex_queue_add(&spftree->paths, vertex); #ifdef EXTREME_DEBUG zlog_debug("ISIS-Spf: added this IS %s %s depth %d dist %d to PATHS", @@ -396,35 +550,13 @@ static struct isis_vertex *isis_spf_add_root(struct isis_spftree *spftree, return vertex; } -static struct isis_vertex *isis_find_vertex(struct list *list, void *id, +static struct isis_vertex *isis_find_vertex(struct isis_vertex_queue *queue, void *id, enum vertextype vtype) { - struct listnode *node; - struct isis_vertex *vertex; - struct prefix *p1, *p2; + struct isis_vertex querier; - for (ALL_LIST_ELEMENTS_RO(list, node, vertex)) { - if (vertex->type != vtype) - continue; - if (VTYPE_IS(vertex->type) || VTYPE_ES(vertex->type)) { - if (memcmp((u_char *)id, vertex->N.id, - ISIS_SYS_ID_LEN + 1) - == 0) - return vertex; - } - if (VTYPE_IP(vertex->type)) { - p1 = (struct prefix *)id; - p2 = (struct prefix *)&vertex->N.id; - if (p1->family == p2->family - && p1->prefixlen == p2->prefixlen - && !memcmp(&p1->u.prefix, &p2->u.prefix, - PSIZE(p1->prefixlen))) { - return vertex; - } - } - } - - return NULL; + isis_vertex_id_init(&querier, id, vtype); + return hash_lookup(queue->hash, &querier); } /* @@ -442,6 +574,30 @@ static bool tent_cmp(struct isis_vertex *current, struct isis_vertex *candidate) return false; } +static void isis_vertex_queue_insert(struct isis_vertex_queue *queue, + struct isis_vertex *vertex) +{ + struct listnode *node; + struct isis_vertex *v; + + /* XXX: This cant use the standard ALL_LIST_ELEMENTS macro */ + for (node = listhead(queue->list); node; node = listnextnode(node)) { + v = listgetdata(node); + if (tent_cmp(v, vertex)) { + listnode_add_before(queue->list, node, vertex); + break; + } + } + + if (node == NULL) + listnode_add(queue->list, vertex); + + struct isis_vertex *inserted; + + inserted = hash_get(queue->hash, vertex, hash_alloc_intern); + assert(inserted == vertex); +} + /* * Add a vertex to TENT sorted by cost and by vertextype on tie break situation */ @@ -451,15 +607,15 @@ static struct isis_vertex *isis_spf_add2tent(struct isis_spftree *spftree, struct isis_adjacency *adj, struct isis_vertex *parent) { - struct isis_vertex *vertex, *v; + struct isis_vertex *vertex; struct listnode *node; struct isis_adjacency *parent_adj; #ifdef EXTREME_DEBUG char buff[PREFIX2STR_BUFFER]; #endif - assert(isis_find_vertex(spftree->paths, id, vtype) == NULL); - assert(isis_find_vertex(spftree->tents, id, vtype) == NULL); + assert(isis_find_vertex(&spftree->paths, id, vtype) == NULL); + assert(isis_find_vertex(&spftree->tents, id, vtype) == NULL); vertex = isis_vertex_new(id, vtype); vertex->d_N = cost; vertex->depth = depth; @@ -485,23 +641,7 @@ static struct isis_vertex *isis_spf_add2tent(struct isis_spftree *spftree, vertex->d_N, listcount(vertex->Adj_N)); #endif /* EXTREME_DEBUG */ - if (list_isempty(spftree->tents)) { - listnode_add(spftree->tents, vertex); - return vertex; - } - - /* XXX: This cant use the standard ALL_LIST_ELEMENTS macro */ - for (node = listhead(spftree->tents); node; node = listnextnode(node)) { - v = listgetdata(node); - if (tent_cmp(v, vertex)) { - listnode_add_before(spftree->tents, node, vertex); - break; - } - } - - if (node == NULL) - listnode_add(spftree->tents, vertex); - + isis_vertex_queue_insert(&spftree->tents, vertex); return vertex; } @@ -512,7 +652,7 @@ static void isis_spf_add_local(struct isis_spftree *spftree, { struct isis_vertex *vertex; - vertex = isis_find_vertex(spftree->tents, id, vtype); + vertex = isis_find_vertex(&spftree->tents, id, vtype); if (vertex) { /* C.2.5 c) */ @@ -536,7 +676,7 @@ static void isis_spf_add_local(struct isis_spftree *spftree, /* f) */ struct listnode *pnode, *pnextnode; struct isis_vertex *pvertex; - listnode_delete(spftree->tents, vertex); + isis_vertex_queue_delete(&spftree->tents, vertex); assert(listcount(vertex->children) == 0); for (ALL_LIST_ELEMENTS(vertex->parents, pnode, pnextnode, pvertex)) @@ -579,7 +719,7 @@ static void process_N(struct isis_spftree *spftree, enum vertextype vtype, } /* c) */ - vertex = isis_find_vertex(spftree->paths, id, vtype); + vertex = isis_find_vertex(&spftree->paths, id, vtype); if (vertex) { #ifdef EXTREME_DEBUG zlog_debug( @@ -591,7 +731,7 @@ static void process_N(struct isis_spftree *spftree, enum vertextype vtype, return; } - vertex = isis_find_vertex(spftree->tents, id, vtype); + vertex = isis_find_vertex(&spftree->tents, id, vtype); /* d) */ if (vertex) { /* 1) */ @@ -626,7 +766,7 @@ static void process_N(struct isis_spftree *spftree, enum vertextype vtype, } else { struct listnode *pnode, *pnextnode; struct isis_vertex *pvertex; - listnode_delete(spftree->tents, vertex); + isis_vertex_queue_delete(&spftree->tents, vertex); assert(listcount(vertex->children) == 0); for (ALL_LIST_ELEMENTS(vertex->parents, pnode, pnextnode, pvertex)) @@ -1056,9 +1196,9 @@ static void add_to_paths(struct isis_spftree *spftree, { char buff[PREFIX2STR_BUFFER]; - if (isis_find_vertex(spftree->paths, vertex->N.id, vertex->type)) + if (isis_find_vertex(&spftree->paths, vertex->N.id, vertex->type)) return; - listnode_add(spftree->paths, vertex); + isis_vertex_queue_add(&spftree->paths, vertex); #ifdef EXTREME_DEBUG zlog_debug("ISIS-Spf: added %s %s %s depth %d dist %d to PATHS", @@ -1087,11 +1227,8 @@ static void add_to_paths(struct isis_spftree *spftree, static void init_spt(struct isis_spftree *spftree, int mtid, int level, int family) { - spftree->tents->del = spftree->paths->del = - (void (*)(void *))isis_vertex_del; - list_delete_all_node(spftree->tents); - list_delete_all_node(spftree->paths); - spftree->tents->del = spftree->paths->del = NULL; + isis_vertex_queue_clear(&spftree->tents); + isis_vertex_queue_clear(&spftree->paths); spftree->mtid = mtid; spftree->level = level; @@ -1103,7 +1240,6 @@ static int isis_run_spf(struct isis_area *area, int level, int family, u_char *sysid) { int retval = ISIS_OK; - struct listnode *node; struct isis_vertex *vertex; struct isis_vertex *root_vertex; struct isis_spftree *spftree = NULL; @@ -1158,15 +1294,14 @@ static int isis_run_spf(struct isis_area *area, int level, int family, /* * C.2.7 Step 2 */ - if (listcount(spftree->tents) == 0) { + if (isis_vertex_queue_count(&spftree->tents) == 0) { zlog_warn("ISIS-Spf: TENT is empty SPF-root:%s", print_sys_hostname(sysid)); goto out; } - while (listcount(spftree->tents) > 0) { - node = listhead(spftree->tents); - vertex = listgetdata(node); + while (isis_vertex_queue_count(&spftree->tents)) { + vertex = isis_vertex_queue_pop(&spftree->tents); #ifdef EXTREME_DEBUG zlog_debug( @@ -1175,8 +1310,6 @@ static int isis_run_spf(struct isis_area *area, int level, int family, vtype2string(vertex->type), vertex->depth, vertex->d_N); #endif /* EXTREME_DEBUG */ - /* Remove from tent list and add to paths list */ - list_delete_node(spftree->tents, node); add_to_paths(spftree, vertex); if (VTYPE_IS(vertex->type)) { memcpy(lsp_id, vertex->N.id, ISIS_SYS_ID_LEN + 1); @@ -1303,7 +1436,7 @@ int isis_spf_schedule(struct isis_area *area, int level) return ISIS_OK; } -static void isis_print_paths(struct vty *vty, struct list *paths, +static void isis_print_paths(struct vty *vty, struct isis_vertex_queue *queue, u_char *root_sysid) { struct listnode *node; @@ -1315,7 +1448,7 @@ static void isis_print_paths(struct vty *vty, struct list *paths, vty_out(vty, "Vertex Type Metric Next-Hop Interface Parent\n"); - for (ALL_LIST_ELEMENTS_RO(paths, node, vertex)) { + for (ALL_QUEUE_ELEMENTS_RO(queue, node, vertex)) { if (memcmp(vertex->N.id, root_sysid, ISIS_SYS_ID_LEN) == 0) { vty_out(vty, "%-20s %-12s %-6s", print_sys_hostname(root_sysid), "", ""); @@ -1399,22 +1532,22 @@ DEFUN (show_isis_topology, continue; if (area->ip_circuits > 0 && area->spftree[level - 1] - && area->spftree[level - 1]->paths->count > 0) { + && isis_vertex_queue_count(&area->spftree[level - 1]->paths) > 0) { vty_out(vty, "IS-IS paths to level-%d routers that speak IP\n", level); isis_print_paths( - vty, area->spftree[level - 1]->paths, + vty, &area->spftree[level - 1]->paths, isis->sysid); vty_out(vty, "\n"); } if (area->ipv6_circuits > 0 && area->spftree6[level - 1] - && area->spftree6[level - 1]->paths->count > 0) { + && isis_vertex_queue_count(&area->spftree6[level - 1]->paths) > 0) { vty_out(vty, "IS-IS paths to level-%d routers that speak IPv6\n", level); isis_print_paths( - vty, area->spftree6[level - 1]->paths, + vty, &area->spftree6[level - 1]->paths, isis->sysid); vty_out(vty, "\n"); } @@ -1430,3 +1563,16 @@ void isis_spf_cmds_init() { install_element(VIEW_NODE, &show_isis_topology_cmd); } + +void isis_spf_print(struct isis_spftree *spftree, struct vty *vty) +{ + vty_out(vty, " last run elapsed : "); + vty_out_timestr(vty, spftree->last_run_timestamp); + vty_out(vty, "\n"); + + vty_out(vty, " last run duration : %u usec\n", + (u_int32_t)spftree->last_run_duration); + + vty_out(vty, " run count : %u\n", + spftree->runcount); +} diff --git a/isisd/isis_spf.h b/isisd/isis_spf.h index c7a505489f..84e07861d2 100644 --- a/isisd/isis_spf.h +++ b/isisd/isis_spf.h @@ -24,53 +24,7 @@ #ifndef _ZEBRA_ISIS_SPF_H #define _ZEBRA_ISIS_SPF_H -enum vertextype { - VTYPE_PSEUDO_IS = 1, - VTYPE_PSEUDO_TE_IS, - VTYPE_NONPSEUDO_IS, - VTYPE_NONPSEUDO_TE_IS, - VTYPE_ES, - VTYPE_IPREACH_INTERNAL, - VTYPE_IPREACH_EXTERNAL, - VTYPE_IPREACH_TE, - VTYPE_IP6REACH_INTERNAL, - VTYPE_IP6REACH_EXTERNAL -}; - -#define VTYPE_IS(t) ((t) >= VTYPE_PSEUDO_IS && (t) <= VTYPE_NONPSEUDO_TE_IS) -#define VTYPE_ES(t) ((t) == VTYPE_ES) -#define VTYPE_IP(t) ((t) >= VTYPE_IPREACH_INTERNAL && (t) <= VTYPE_IP6REACH_EXTERNAL) - -/* - * Triple <N, d(N), {Adj(N)}> - */ -struct isis_vertex { - enum vertextype type; - - union { - u_char id[ISIS_SYS_ID_LEN + 1]; - struct prefix prefix; - } N; - - u_int32_t d_N; /* d(N) Distance from this IS */ - u_int16_t depth; /* The depth in the imaginary tree */ - struct list *Adj_N; /* {Adj(N)} next hop or neighbor list */ - struct list *parents; /* list of parents for ECMP */ - struct list *children; /* list of children used for tree dump */ -}; - -struct isis_spftree { - struct list *paths; /* the SPT */ - struct list *tents; /* TENT */ - struct isis_area *area; /* back pointer to area */ - unsigned int runcount; /* number of runs since uptime */ - time_t last_run_timestamp; /* last run timestamp for scheduling */ - time_t last_run_duration; /* last run duration in msec */ - - uint16_t mtid; - int family; - int level; -}; +struct isis_spftree; struct isis_spftree *isis_spftree_new(struct isis_area *area); void isis_spftree_del(struct isis_spftree *spftree); @@ -79,4 +33,5 @@ void spftree_area_del(struct isis_area *area); void spftree_area_adj_del(struct isis_area *area, struct isis_adjacency *adj); int isis_spf_schedule(struct isis_area *area, int level); void isis_spf_cmds_init(void); +void isis_spf_print(struct isis_spftree *spftree, struct vty *vty); #endif /* _ZEBRA_ISIS_SPF_H */ diff --git a/isisd/isisd.c b/isisd/isisd.c index 05797fb73a..60b9367da9 100644 --- a/isisd/isisd.c +++ b/isisd/isisd.c @@ -1231,27 +1231,6 @@ DEFUN (show_hostname, return CMD_SUCCESS; } -static void vty_out_timestr(struct vty *vty, time_t uptime) -{ - struct tm *tm; - time_t difftime = time(NULL); - difftime -= uptime; - tm = gmtime(&difftime); - -#define ONE_DAY_SECOND 60*60*24 -#define ONE_WEEK_SECOND 60*60*24*7 - if (difftime < ONE_DAY_SECOND) - vty_out(vty, "%02d:%02d:%02d", tm->tm_hour, tm->tm_min, - tm->tm_sec); - else if (difftime < ONE_WEEK_SECOND) - vty_out(vty, "%dd%02dh%02dm", tm->tm_yday, tm->tm_hour, - tm->tm_min); - else - vty_out(vty, "%02dw%dd%02dh", tm->tm_yday / 7, - tm->tm_yday - ((tm->tm_yday / 7) * 7), tm->tm_hour); - vty_out(vty, " ago"); -} - DEFUN (show_isis_spf_ietf, show_isis_spf_ietf_cmd, "show isis spf-delay-ietf", @@ -1308,7 +1287,6 @@ DEFUN (show_isis_summary, { struct listnode *node, *node2; struct isis_area *area; - struct isis_spftree *spftree; int level; if (isis == NULL) { @@ -1349,7 +1327,6 @@ DEFUN (show_isis_summary, continue; vty_out(vty, " Level-%d:\n", level); - spftree = area->spftree[level - 1]; if (area->spf_timer[level - 1]) vty_out(vty, " SPF: (pending)\n"); else @@ -1363,28 +1340,10 @@ DEFUN (show_isis_summary, vty_out(vty, "\n"); vty_out(vty, " IPv4 route computation:\n"); - vty_out(vty, " last run elapsed : "); - vty_out_timestr(vty, spftree->last_run_timestamp); - vty_out(vty, "\n"); - - vty_out(vty, " last run duration : %u usec\n", - (u_int32_t)spftree->last_run_duration); + isis_spf_print(area->spftree[level - 1], vty); - vty_out(vty, " run count : %d\n", - spftree->runcount); - - spftree = area->spftree6[level - 1]; vty_out(vty, " IPv6 route computation:\n"); - - vty_out(vty, " last run elapsed : "); - vty_out_timestr(vty, spftree->last_run_timestamp); - vty_out(vty, "\n"); - - vty_out(vty, " last run duration : %llu msec\n", - (unsigned long long)spftree->last_run_duration); - - vty_out(vty, " run count : %d\n", - spftree->runcount); + isis_spf_print(area->spftree6[level - 1], vty); } } vty_out(vty, "\n"); diff --git a/lib/hash.c b/lib/hash.c index e74e4355dc..1621d2a820 100644 --- a/lib/hash.c +++ b/lib/hash.c @@ -358,33 +358,26 @@ DEFUN(show_hash_stats, /* Summary statistics calculated are: * - * - Load factor: This is the number of elements in the table divided by - * the - * number of buckets. Since this hash table implementation uses - * chaining, - * this value can be greater than 1. This number provides information - * on - * how 'full' the table is, but does not provide information on how - * evenly - * distributed the elements are. Notably, a load factor >= 1 does not - * imply - * that every bucket has an element; with a pathological hash - * function, all - * elements could be in a single bucket. + * - Load factor: This is the number of elements in the table divided + * by the number of buckets. Since this hash table implementation + * uses chaining, this value can be greater than 1. + * This number provides information on how 'full' the table is, but + * does not provide information on how evenly distributed the + * elements are. + * Notably, a load factor >= 1 does not imply that every bucket has + * an element; with a pathological hash function, all elements could + * be in a single bucket. * * - Full load factor: this is the number of elements in the table - * divided by - * the number of buckets that have some elements in them. + * divided by the number of buckets that have some elements in them. * * - Std. Dev.: This is the standard deviation calculated from the - * relevant - * load factor. If the load factor is the mean of number of elements - * per - * bucket, the standard deviation measures how much any particular - * bucket - * is likely to deviate from the mean. As a rule of thumb this number - * should be less than 2, and ideally <= 1 for optimal performance. A - * number larger than 3 generally indicates a poor hash function. + * relevant load factor. If the load factor is the mean of number of + * elements per bucket, the standard deviation measures how much any + * particular bucket is likely to deviate from the mean. + * As a rule of thumb this number should be less than 2, and ideally + * <= 1 for optimal performance. A number larger than 3 generally + * indicates a poor hash function. */ double lf; // load factor diff --git a/lib/prefix.c b/lib/prefix.c index 0ba0025c68..47e16dbf8b 100644 --- a/lib/prefix.c +++ b/lib/prefix.c @@ -26,6 +26,7 @@ #include "sockunion.h" #include "memory.h" #include "log.h" +#include "jhash.h" DEFINE_MTYPE_STATIC(LIB, PREFIX, "Prefix") @@ -1335,3 +1336,15 @@ char *prefix_mac2str(const struct ethaddr *mac, char *buf, int size) (uint8_t)mac->octet[4], (uint8_t)mac->octet[5]); return ptr; } + +unsigned prefix_hash_key(void *pp) +{ + struct prefix copy; + + /* make sure *all* unused bits are zero, particularly including + * alignment / + * padding and unused prefix bytes. */ + memset(©, 0, sizeof(copy)); + prefix_copy(©, (struct prefix *)pp); + return jhash(©, sizeof(copy), 0x55aa5a5a); +} diff --git a/lib/prefix.h b/lib/prefix.h index ce13dcfa0a..4f1f0b22d7 100644 --- a/lib/prefix.h +++ b/lib/prefix.h @@ -323,6 +323,8 @@ extern const char *inet6_ntoa(struct in6_addr); extern int prefix_str2mac(const char *str, struct ethaddr *mac); extern char *prefix_mac2str(const struct ethaddr *mac, char *buf, int size); +extern unsigned prefix_hash_key(void *pp); + static inline int ipv6_martian(struct in6_addr *addr) { struct in6_addr localhost_addr; diff --git a/lib/table.c b/lib/table.c index 007d41778e..833adb9a37 100644 --- a/lib/table.c +++ b/lib/table.c @@ -27,7 +27,6 @@ #include "table.h" #include "memory.h" #include "sockunion.h" -#include "jhash.h" DEFINE_MTYPE(LIB, ROUTE_TABLE, "Route table") DEFINE_MTYPE(LIB, ROUTE_NODE, "Route node") @@ -35,18 +34,6 @@ DEFINE_MTYPE(LIB, ROUTE_NODE, "Route node") static void route_node_delete(struct route_node *); static void route_table_free(struct route_table *); -static unsigned route_table_hash_key(void *pp) -{ - struct prefix copy; - - /* make sure *all* unused bits are zero, particularly including - * alignment / - * padding and unused prefix bytes. */ - memset(©, 0, sizeof(copy)); - prefix_copy(©, (struct prefix *)pp); - return jhash(©, sizeof(copy), 0x55aa5a5a); -} - static int route_table_hash_cmp(const void *a, const void *b) { const struct prefix *pa = a, *pb = b; @@ -63,7 +50,7 @@ route_table_init_with_delegate(route_table_delegate_t *delegate) rt = XCALLOC(MTYPE_ROUTE_TABLE, sizeof(struct route_table)); rt->delegate = delegate; - rt->hash = hash_create(route_table_hash_key, route_table_hash_cmp, + rt->hash = hash_create(prefix_hash_key, route_table_hash_cmp, "route table hash"); return rt; } |