From ece0e6efa7bae5272461471bab51dbb3bfc3053a Mon Sep 17 00:00:00 2001 From: Donald Sharp Date: Tue, 28 Jul 2020 10:58:47 -0400 Subject: [PATCH] vtysh: Speed up output of configuration across daemons With a config that contains a large number of prefix-lists a 'show run' command was an expensive operation: sharpd@eva ~/frr_internal2 ((cl4.1.0))> time vtysh -c "show run" | grep ACTIVE | wc -l 32397 ________________________________________________________ Executed in 14.53 secs fish external usr time 14.45 secs 591.00 micros 14.45 secs sys time 0.03 secs 189.00 micros 0.03 secs sharpd@eva ~/frr_internal2 ((cl4.1.0))> Effectively we are keeping a linked list of data to store the configuration. When we received a new item we would look in the list to see if it already does, by doing a string search across each element in the list. Add to the master configuration a hash of items for O(1) lookup. Keep the list for order so we don't mangle that up. New time: sharpd@eva ~/frr_internal1 (dev)> time vtysh -c "show run" | grep ACTIVE | wc -l 32397 ________________________________________________________ Executed in 277.94 millis fish external usr time 237.46 millis 20.53 millis 216.93 millis sys time 14.31 millis 0.00 millis 14.31 millis Signed-off-by: Donald Sharp --- vtysh/vtysh_config.c | 65 +++++++++++++++++++++++++++++++------------- 1 file changed, 46 insertions(+), 19 deletions(-) diff --git a/vtysh/vtysh_config.c b/vtysh/vtysh_config.c index 61bcf3b658..85221b8b45 100644 --- a/vtysh/vtysh_config.c +++ b/vtysh/vtysh_config.c @@ -35,6 +35,7 @@ DEFINE_MTYPE_STATIC(MVTYSH, VTYSH_CONFIG_LINE, "Vtysh configuration line") vector configvec; PREDECL_LIST(config_master); +PREDECL_HASH(config_master_hash); struct config { /* Configuration node name. */ @@ -51,6 +52,7 @@ struct config { /* Node entry for the typed Red-black tree */ struct config_master_item rbt_item; + struct config_master_hash_item hash_item; }; struct list *config_top; @@ -79,29 +81,49 @@ static void config_del(struct config *config) XFREE(MTYPE_VTYSH_CONFIG, config); } +static int config_cmp(const struct config *c1, const struct config *c2) +{ + return strcmp(c1->name, c2->name); +} + +static uint32_t config_hash(const struct config *c) +{ + return string_hash_make(c->name); +} + DECLARE_LIST(config_master, struct config, rbt_item) +DECLARE_HASH(config_master_hash, struct config, hash_item, config_cmp, + config_hash) + +/* + * The config_master_head is a list for order of receipt + * The hash is for quick lookup under this NODE + */ +struct configuration { + struct config_master_head master; + struct config_master_hash_head hash_master; +}; static struct config *config_get(int index, const char *line) { struct config *config, *config_loop; - struct config_master_head *master; + struct configuration *configuration; + struct config lookup; config = config_loop = NULL; - master = vector_lookup_ensure(configvec, index); + configuration = vector_lookup_ensure(configvec, index); - if (!master) { - master = XMALLOC(MTYPE_VTYSH_CONFIG, sizeof(struct config_master_head)); - config_master_init(master); - vector_set_index(configvec, index, master); + if (!configuration) { + configuration = XMALLOC(MTYPE_VTYSH_CONFIG, + sizeof(struct configuration)); + config_master_init(&configuration->master); + config_master_hash_init(&configuration->hash_master); + vector_set_index(configvec, index, configuration); } - frr_each (config_master, master, config_loop) { - if (strcmp(config_loop->name, line) == 0) { - config = config_loop; - break; - } - } + lookup.name = (char *)line; + config = config_master_hash_find(&configuration->hash_master, &lookup); if (!config) { config = config_new(); @@ -110,7 +132,8 @@ static struct config *config_get(int index, const char *line) config->line->cmp = (int (*)(void *, void *))line_cmp; config->name = XSTRDUP(MTYPE_VTYSH_CONFIG_LINE, line); config->index = index; - config_master_add_tail(master, config); + config_master_add_tail(&configuration->master, config); + config_master_hash_add(&configuration->hash_master, config); } return config; } @@ -438,7 +461,7 @@ void vtysh_config_dump(void) struct listnode *node, *nnode; struct listnode *mnode, *mnnode; struct config *config; - struct config_master_head *master; + struct configuration *configuration; char *line; unsigned int i; @@ -448,8 +471,11 @@ void vtysh_config_dump(void) vty_out(vty, "!\n"); for (i = 0; i < vector_active(configvec); i++) - if ((master = vector_slot(configvec, i)) != NULL) { - while ((config = config_master_pop(master))) { + if ((configuration = vector_slot(configvec, i)) != NULL) { + while ((config = config_master_pop( + &configuration->master))) { + config_master_hash_del( + &configuration->hash_master, config); /* Don't print empty sections for interface. * Route maps on the * other hand could have a legitimate empty @@ -477,9 +503,10 @@ void vtysh_config_dump(void) } for (i = 0; i < vector_active(configvec); i++) - if ((master = vector_slot(configvec, i)) != NULL) { - config_master_fini(master); - XFREE(MTYPE_VTYSH_CONFIG, master); + if ((configuration = vector_slot(configvec, i)) != NULL) { + config_master_fini(&configuration->master); + config_master_hash_fini(&configuration->hash_master); + XFREE(MTYPE_VTYSH_CONFIG, configuration); vector_slot(configvec, i) = NULL; } list_delete_all_node(config_top); -- 2.39.5