[ovs-dev] [PATCH 1/3] Optimise shash disposal

Dumitru Ceara dceara at redhat.com
Fri Aug 7 11:09:36 UTC 2020


On 7/31/20 11:23 AM, anton.ivanov at cambridgegreys.com wrote:
> From: Anton Ivanov <anton.ivanov at cambridgegreys.com>
> 
> SHASH as written at present relies on HMAP and iterator macros
> to dispose of all of its elements.
> 
> This results in a lot of unnecessary hash comparisons and walk
> attempts which simply return the next item.
> 
> This patch switches this to direct removal where the whole shash
> is cleared at once in O(N) without any hash recomputations and
> comparisons.
> 
> Signed-off-by: Anton Ivanov <anton.ivanov at cambridgegreys.com>
> ---
>  lib/shash.c | 48 +++++++++++++++++++++++++++++++++++++-----------
>  1 file changed, 37 insertions(+), 11 deletions(-)
> 
> diff --git a/lib/shash.c b/lib/shash.c
> index a8433629a..09505b73d 100644
> --- a/lib/shash.c
> +++ b/lib/shash.c
> @@ -68,27 +68,53 @@ shash_moved(struct shash *sh)
>  void
>  shash_clear(struct shash *sh)
>  {
> -    struct shash_node *node, *next;
> +    struct shash_node *node;
> +    struct hmap_node *hn;
> +
> +    int i;
>  
> -    SHASH_FOR_EACH_SAFE (node, next, sh) {
> -        hmap_remove(&sh->map, &node->node);
> -        free(node->name);
> -        free(node);
> +    if (sh->map.n == 0) {
> +        return;
> +    }
> +
> +    for (i = 0; i <= sh->map.mask; i++) {
> +        hn = sh->map.buckets[i];
> +        while (hn != NULL) {
> +            node = CONTAINER_OF(hn, struct shash_node, node);
> +            hn = hn->next;
> +            free(node->name);
> +            free(node);
> +        }
> +        sh->map.buckets[i] = NULL;
>      }
> +    sh->map.n = 0;
>  }
>  
>  /* Like shash_clear(), but also free() each node's 'data'. */
>  void
>  shash_clear_free_data(struct shash *sh)
>  {
> -    struct shash_node *node, *next;
> +    struct shash_node *node;
> +    struct hmap_node *hn;
> +
> +    int i;
>  
> -    SHASH_FOR_EACH_SAFE (node, next, sh) {
> -        hmap_remove(&sh->map, &node->node);
> -        free(node->data);
> -        free(node->name);
> -        free(node);
> +    if (sh->map.n == 0) {
> +        return;
> +    }
> +
> +    for (i = 0; i <= sh->map.mask; i++) {
> +        hn = sh->map.buckets[i];
> +        while (hn != NULL) {
> +            node = CONTAINER_OF(hn, struct shash_node, node);
> +            hn = hn->next;
> +            free(node->data);
> +            free(node->name);
> +            free(node);
> +        }
> +        sh->map.buckets[i] = NULL;
>      }
> +    sh->map.n = 0;
>  }
>  
>  bool
> 

Hi Anton,

With this we're now using hmap internals in shash.c. Wouldn't it be
better for hmap to expose an API to clear (maybe with a handler per node)?

Thanks,
Dumitru



More information about the dev mailing list