From 0e5d0e30b30bb07b6605843e5ff224210d8083d8 Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Tue, 27 Sep 2011 15:58:43 +0930 Subject: [PATCH 1/1] likely: use htable_type Also general cleanups: (1) Don't assume that strings are folded by the compiler. (2) Implement likely_stats_reset(). (3) Return non-const string from likely_stats(), as caller must free it. (4) Don't use struct info indirection (that was from when we used callbacks?) (5) Close memory leak in run-debug.c --- ccan/likely/likely.c | 120 +++++++++++++++++------------------ ccan/likely/likely.h | 11 +++- ccan/likely/test/run-debug.c | 17 ++++- 3 files changed, 81 insertions(+), 67 deletions(-) diff --git a/ccan/likely/likely.c b/ccan/likely/likely.c index faa2bd8e..1114efc2 100644 --- a/ccan/likely/likely.c +++ b/ccan/likely/likely.c @@ -2,11 +2,9 @@ #ifdef CCAN_LIKELY_DEBUG #include #include -#include +#include #include #include -static struct htable *htable; - struct trace { const char *condstr; const char *file; @@ -15,27 +13,27 @@ struct trace { unsigned long count, right; }; -/* We hash the pointers, which will be identical for same call. */ -static unsigned long hash_trace(const struct trace *trace) +static size_t hash_trace(const struct trace *trace) { - return hash_pointer(trace->condstr, - hash_pointer(trace->file, - trace->line + trace->expect)); + return hash(trace->condstr, strlen(trace->condstr), + hash(trace->file, strlen(trace->file), + trace->line + trace->expect)); } -static bool hash_cmp(const void *htelem, void *cmpdata) +static bool trace_eq(const struct trace *t1, const struct trace *t2) { - const struct trace *t1 = htelem, *t2 = cmpdata; return t1->condstr == t2->condstr && t1->file == t2->file && t1->line == t2->line && t1->expect == t2->expect; } -static size_t rehash(const void *elem, void *priv) -{ - return hash_trace(elem); -} +/* struct thash */ +HTABLE_DEFINE_TYPE(struct trace, (const struct trace *), hash_trace, trace_eq, + thash); + +static struct thash htable += { HTABLE_INITIALIZER(htable.raw, thash_hash, NULL) }; static void init_trace(struct trace *trace, const char *condstr, const char *file, unsigned int line, @@ -48,12 +46,11 @@ static void init_trace(struct trace *trace, trace->count = trace->right = 0; } -static struct trace *add_trace(const char *condstr, - const char *file, unsigned int line, bool expect) +static struct trace *add_trace(const struct trace *t) { struct trace *trace = malloc(sizeof(*trace)); - init_trace(trace, condstr, file, line, expect); - htable_add(htable, hash_trace(trace), trace); + *trace = *t; + thash_add(&htable, trace); return trace; } @@ -63,13 +60,10 @@ long _likely_trace(bool cond, bool expect, { struct trace *p, trace; - if (!htable) - htable = htable_new(rehash, NULL); - init_trace(&trace, condstr, file, line, expect); - p = htable_get(htable, hash_trace(&trace), hash_cmp, &trace); + p = thash_get(&htable, &trace); if (!p) - p = add_trace(condstr, file, line, expect); + p = add_trace(&trace); p->count++; if (cond == expect) @@ -78,65 +72,65 @@ long _likely_trace(bool cond, bool expect, return cond; } -struct get_stats_info { - struct trace *worst; - unsigned int min_hits; - double worst_ratio; -}; - static double right_ratio(const struct trace *t) { return (double)t->right / t->count; } -static void get_stats(struct trace *trace, struct get_stats_info *info) +char *likely_stats(unsigned int min_hits, unsigned int percent) { - if (trace->count < info->min_hits) - return; - - if (right_ratio(trace) < info->worst_ratio) { - info->worst = trace; - info->worst_ratio = right_ratio(trace); - } -} - -const char *likely_stats(unsigned int min_hits, unsigned int percent) -{ - struct get_stats_info info; - struct htable_iter i; + struct trace *worst; + double worst_ratio; + struct thash_iter i; char *ret; - struct trace *trace; - - if (!htable) - return NULL; + struct trace *t; - info.min_hits = min_hits; - info.worst = NULL; - info.worst_ratio = 2; + worst = NULL; + worst_ratio = 2; /* This is O(n), but it's not likely called that often. */ - for (trace = htable_first(htable, &i); - trace; - trace = htable_next(htable,&i)) { - get_stats(trace, &info); + for (t = thash_first(&htable, &i); t; t = thash_next(&htable, &i)) { + if (t->count >= min_hits) { + if (right_ratio(t) < worst_ratio) { + worst = t; + worst_ratio = right_ratio(t); + } + } } - if (info.worst_ratio * 100 > percent) + if (worst_ratio * 100 > percent) return NULL; - ret = malloc(strlen(info.worst->condstr) + - strlen(info.worst->file) + + ret = malloc(strlen(worst->condstr) + + strlen(worst->file) + sizeof(long int) * 8 + sizeof("%s:%u:%slikely(%s) correct %u%% (%lu/%lu)")); sprintf(ret, "%s:%u:%slikely(%s) correct %u%% (%lu/%lu)", - info.worst->file, info.worst->line, - info.worst->expect ? "" : "un", info.worst->condstr, - (unsigned)(info.worst_ratio * 100), - info.worst->right, info.worst->count); + worst->file, worst->line, + worst->expect ? "" : "un", worst->condstr, + (unsigned)(worst_ratio * 100), + worst->right, worst->count); - htable_del(htable, hash_trace(info.worst), info.worst); - free(info.worst); + thash_del(&htable, worst); + free(worst); return ret; } + +void likely_stats_reset(void) +{ + struct thash_iter i; + struct trace *t; + + /* This is a bit better than O(n^2), but we have to loop since + * first/next during delete is unreliable. */ + while ((t = thash_first(&htable, &i)) != NULL) { + for (; t; t = thash_next(&htable, &i)) { + thash_del(&htable, t); + free(t); + } + } + + thash_clear(&htable); +} #endif /*CCAN_LIKELY_DEBUG*/ diff --git a/ccan/likely/likely.h b/ccan/likely/likely.h index 5e4fc831..410772db 100644 --- a/ccan/likely/likely.h +++ b/ccan/likely/likely.h @@ -74,7 +74,7 @@ long _likely_trace(bool cond, bool expect, * @percent: maximum percentage correct * * When CCAN_LIKELY_DEBUG is defined, likely() and unlikely() trace their - * results: this causes a significant slowdown, but allows analysis of + * results: this causes a significant slowdown, but allows analysis of * whether the branches are labelled correctly. * * This function returns a malloc'ed description of the least-correct @@ -101,6 +101,13 @@ long _likely_trace(bool cond, bool expect, * #endif * } */ -const char *likely_stats(unsigned int min_hits, unsigned int percent); +char *likely_stats(unsigned int min_hits, unsigned int percent); + +/** + * likely_stats_reset - free up memory of likely()/unlikely() branches. + * + * This can also plug memory leaks. + */ +void likely_stats_reset(void); #endif /* CCAN_LIKELY_DEBUG */ #endif /* CCAN_LIKELY_H */ diff --git a/ccan/likely/test/run-debug.c b/ccan/likely/test/run-debug.c index df786192..afb21e2b 100644 --- a/ccan/likely/test/run-debug.c +++ b/ccan/likely/test/run-debug.c @@ -28,9 +28,9 @@ static bool likely_one_unlikely_two(unsigned int val1, unsigned int val2) int main(int argc, char *argv[]) { - const char *bad; + char *bad; - plan_tests(13); + plan_tests(14); /* Correct guesses. */ one_seems_likely(1); @@ -46,6 +46,7 @@ int main(int argc, char *argv[]) bad = likely_stats(3, 90); ok(strends(bad, "run-debug.c:9:likely(val == 1) correct 33% (1/3)"), "likely_stats returned %s", bad); + free(bad); /* Nothing else above 90% */ ok1(!likely_stats(0, 90)); @@ -54,6 +55,7 @@ int main(int argc, char *argv[]) bad = likely_stats(0, 100); ok(strends(bad, "run-debug.c:16:unlikely(val == 1) correct 100% (1/1)"), "likely_stats returned %s", bad); + free(bad); /* Nothing left (table is actually cleared) */ ok1(!likely_stats(0, 100)); @@ -66,6 +68,7 @@ int main(int argc, char *argv[]) bad = likely_stats(0, 90); ok(strends(bad, "run-debug.c:16:unlikely(val == 1) correct 66% (2/3)"), "likely_stats returned %s", bad); + free(bad); ok1(!likely_stats(0, 100)); likely_one_unlikely_two(1, 1); @@ -77,9 +80,19 @@ int main(int argc, char *argv[]) bad = likely_stats(0, 90); ok(strends(bad, "run-debug.c:24:unlikely(val2 == 2) correct 75% (3/4)"), "likely_stats returned %s", bad); + free(bad); bad = likely_stats(0, 100); ok(strends(bad, "run-debug.c:24:likely(val1 == 1) correct 100% (4/4)"), "likely_stats returned %s", bad); + free(bad); + + ok1(!likely_stats(0, 100)); + + /* Check that reset works! */ + one_seems_unlikely(0); + one_seems_unlikely(2); + one_seems_unlikely(1); + likely_stats_reset(); ok1(!likely_stats(0, 100)); -- 2.39.2