[ovs-dev] [PATCH] hmap: Make bad hash functions easier to find.
Ben Pfaff
blp at nicira.com
Tue Sep 24 21:51:53 UTC 2013
Thanks Keith and Justin, I applied this to master and branch-2.0.
On Tue, Sep 24, 2013 at 02:33:53PM -0700, Justin Pettit wrote:
> Acked-by: Justin Pettit <jpettit at nicira.com>
>
>
> On Sep 24, 2013, at 10:17 AM, Ben Pfaff <blp at 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 <keith at nicira.com>
> > Signed-off-by: Ben Pfaff <blp at 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 at openvswitch.org
> > http://openvswitch.org/mailman/listinfo/dev
>
More information about the dev
mailing list