Acked-by: Justin Pettit <jpet...@nicira.com>
On Sep 24, 2013, at 10:17 AM, Ben Pfaff <b...@nicira.com> wrote:
> The hmap code has for a long time incremented a counter when a hash bucket
> grew to have many entries. This can let a developer know that some hash
> function is performing poorly, but doesn't give any hint as to which one.
> This commit improves the situation by adding rate-limited debug logging
> that points out a particular line of code as the source of the poor hash
> behavior. It should make issues easier to track down.
>
> Bug #19926.
> CC: Keith Amidon <ke...@nicira.com>
> Signed-off-by: Ben Pfaff <b...@nicira.com>
> ---
> lib/hmap.c | 38 ++++++++++++++++++++++++++++----------
> lib/hmap.h | 31 +++++++++++++++++++++++--------
> 2 files changed, 51 insertions(+), 18 deletions(-)
>
> diff --git a/lib/hmap.c b/lib/hmap.c
> index f15e72c..a559a77 100644
> --- a/lib/hmap.c
> +++ b/lib/hmap.c
> @@ -21,6 +21,9 @@
> #include "coverage.h"
> #include "random.h"
> #include "util.h"
> +#include "vlog.h"
> +
> +VLOG_DEFINE_THIS_MODULE(hmap);
>
> COVERAGE_DEFINE(hmap_pathological);
> COVERAGE_DEFINE(hmap_expand);
> @@ -85,7 +88,7 @@ hmap_moved(struct hmap *hmap)
> }
>
> static void
> -resize(struct hmap *hmap, size_t new_mask)
> +resize(struct hmap *hmap, size_t new_mask, const char *where)
> {
> struct hmap tmp;
> size_t i;
> @@ -109,7 +112,10 @@ resize(struct hmap *hmap, size_t new_mask)
> count++;
> }
> if (count > 5) {
> + static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(10, 10);
> COVERAGE_INC(hmap_pathological);
> + VLOG_DBG_RL(&rl, "%s: %d nodes in bucket (%zu nodes, %zu
> buckets)",
> + where, count, hmap->n, hmap->mask + 1);
> }
> }
> hmap_swap(hmap, &tmp);
> @@ -136,38 +142,50 @@ calc_mask(size_t capacity)
> return mask;
> }
>
> -/* Expands 'hmap', if necessary, to optimize the performance of searches. */
> +/* Expands 'hmap', if necessary, to optimize the performance of searches.
> + *
> + * ('where' is used in debug logging. Commonly one would use hmap_expand()
> to
> + * automatically provide the caller's source file and line number for
> + * 'where'.) */
> void
> -hmap_expand(struct hmap *hmap)
> +hmap_expand_at(struct hmap *hmap, const char *where)
> {
> size_t new_mask = calc_mask(hmap->n);
> if (new_mask > hmap->mask) {
> COVERAGE_INC(hmap_expand);
> - resize(hmap, new_mask);
> + resize(hmap, new_mask, where);
> }
> }
>
> -/* Shrinks 'hmap', if necessary, to optimize the performance of iteration. */
> +/* Shrinks 'hmap', if necessary, to optimize the performance of iteration.
> + *
> + * ('where' is used in debug logging. Commonly one would use hmap_shrink()
> to
> + * automatically provide the caller's source file and line number for
> + * 'where'.) */
> void
> -hmap_shrink(struct hmap *hmap)
> +hmap_shrink_at(struct hmap *hmap, const char *where)
> {
> size_t new_mask = calc_mask(hmap->n);
> if (new_mask < hmap->mask) {
> COVERAGE_INC(hmap_shrink);
> - resize(hmap, new_mask);
> + resize(hmap, new_mask, where);
> }
> }
>
> /* Expands 'hmap', if necessary, to optimize the performance of searches when
> * it has up to 'n' elements. (But iteration will be slow in a hash map whose
> - * allocated capacity is much higher than its current number of nodes.) */
> + * allocated capacity is much higher than its current number of nodes.)
> + *
> + * ('where' is used in debug logging. Commonly one would use hmap_reserve()
> to
> + * automatically provide the caller's source file and line number for
> + * 'where'.) */
> void
> -hmap_reserve(struct hmap *hmap, size_t n)
> +hmap_reserve_at(struct hmap *hmap, size_t n, const char *where)
> {
> size_t new_mask = calc_mask(n);
> if (new_mask > hmap->mask) {
> COVERAGE_INC(hmap_reserve);
> - resize(hmap, new_mask);
> + resize(hmap, new_mask, where);
> }
> }
>
> diff --git a/lib/hmap.h b/lib/hmap.h
> index ab7d3ae..76a73ac 100644
> --- a/lib/hmap.h
> +++ b/lib/hmap.h
> @@ -1,5 +1,5 @@
> /*
> - * Copyright (c) 2008, 2009, 2010, 2012 Nicira, Inc.
> + * Copyright (c) 2008, 2009, 2010, 2012, 2013 Nicira, Inc.
> *
> * Licensed under the Apache License, Version 2.0 (the "License");
> * you may not use this file except in compliance with the License.
> @@ -78,14 +78,24 @@ static inline size_t hmap_count(const struct hmap *);
> static inline bool hmap_is_empty(const struct hmap *);
>
> /* Adjusting capacity. */
> -void hmap_expand(struct hmap *);
> -void hmap_shrink(struct hmap *);
> -void hmap_reserve(struct hmap *, size_t capacity);
> +void hmap_expand_at(struct hmap *, const char *where);
> +#define hmap_expand(HMAP) hmap_expand_at(HMAP, SOURCE_LOCATOR)
> +
> +void hmap_shrink_at(struct hmap *, const char *where);
> +#define hmap_shrink(HMAP) hmap_shrink_at(HMAP, SOURCE_LOCATOR)
> +
> +void hmap_reserve_at(struct hmap *, size_t capacity, const char *where);
> +#define hmap_reserve(HMAP, CAPACITY) \
> + hmap_reserve_at(HMAP, CAPACITY, SOURCE_LOCATOR)
>
> /* Insertion and deletion. */
> +static inline void hmap_insert_at(struct hmap *, struct hmap_node *,
> + size_t hash, const char *where);
> +#define hmap_insert(HMAP, NODE, HASH) \
> + hmap_insert_at(HMAP, NODE, HASH, SOURCE_LOCATOR)
> +
> static inline void hmap_insert_fast(struct hmap *,
> struct hmap_node *, size_t hash);
> -static inline void hmap_insert(struct hmap *, struct hmap_node *, size_t
> hash);
> static inline void hmap_remove(struct hmap *, struct hmap_node *);
>
> void hmap_node_moved(struct hmap *, struct hmap_node *, struct hmap_node *);
> @@ -199,13 +209,18 @@ hmap_insert_fast(struct hmap *hmap, struct hmap_node
> *node, size_t hash)
> }
>
> /* Inserts 'node', with the given 'hash', into 'hmap', and expands 'hmap' if
> - * necessary to optimize search performance. */
> + * necessary to optimize search performance.
> + *
> + * ('where' is used in debug logging. Commonly one would use hmap_insert()
> to
> + * automatically provide the caller's source file and line number for
> + * 'where'.) */
> static inline void
> -hmap_insert(struct hmap *hmap, struct hmap_node *node, size_t hash)
> +hmap_insert_at(struct hmap *hmap, struct hmap_node *node, size_t hash,
> + const char *where)
> {
> hmap_insert_fast(hmap, node, hash);
> if (hmap->n / 2 > hmap->mask) {
> - hmap_expand(hmap);
> + hmap_expand_at(hmap, where);
> }
> }
>
> --
> 1.7.10.4
>
> _______________________________________________
> dev mailing list
> dev@openvswitch.org
> http://openvswitch.org/mailman/listinfo/dev
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
