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
