From 9f8c65b28acba8e5eabea5d7abd98b19e62d06fe Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Tue, 11 May 2010 12:04:35 +0930 Subject: [PATCH] likely: new module --- ccan/likely/_info | 44 +++++++++++ ccan/likely/likely.c | 139 +++++++++++++++++++++++++++++++++++ ccan/likely/likely.h | 129 ++++++++++++++++++++++++++++++++ ccan/likely/test/run-debug.c | 87 ++++++++++++++++++++++ ccan/likely/test/run.c | 36 +++++++++ config.h | 1 + 6 files changed, 436 insertions(+) create mode 100644 ccan/likely/_info create mode 100644 ccan/likely/likely.c create mode 100644 ccan/likely/likely.h create mode 100644 ccan/likely/test/run-debug.c create mode 100644 ccan/likely/test/run.c diff --git a/ccan/likely/_info b/ccan/likely/_info new file mode 100644 index 00000000..d72aa558 --- /dev/null +++ b/ccan/likely/_info @@ -0,0 +1,44 @@ +#include +#include +#include "config.h" + +/** + * likely - macros for annotating likely/unlikely branches in the code + * + * Inspired by Andi Kleen's macros for the Linux Kernel, these macros + * help you annotate rare paths in your code for the convenience of the + * compiler and the reader. + * + * Licence: LGPL (2 or any later version) + * + * Example: + * #include + * #include + * + * int main(int argc, char *argv[]) + * { + * // This example is silly: the compiler knows exit() is unlikely. + * if (unlikely(argc == 1)) { + * fprintf(stderr, "Usage: %s ...\n", argv[0]); + * return 1; + * } + * for (argc++; argv[argc]; argc++) + * printf("%s\n", argv[argc]); + * return 0; + * } + */ +int main(int argc, char *argv[]) +{ + /* Expect exactly one argument */ + if (argc != 2) + return 1; + + if (strcmp(argv[1], "depends") == 0) { + printf("ccan/str\n"); + printf("ccan/hashtable\n"); + printf("ccan/hash\n"); + return 0; + } + + return 1; +} diff --git a/ccan/likely/likely.c b/ccan/likely/likely.c new file mode 100644 index 00000000..e4bee71b --- /dev/null +++ b/ccan/likely/likely.c @@ -0,0 +1,139 @@ +#ifdef DEBUG +#include +#include +#include +#include +#include +static struct hashtable *htable; + +struct trace { + const char *condstr; + const char *file; + unsigned int line; + bool expect; + unsigned long count, right; +}; + +/* We hash the pointers, which will be identical for same call. */ +static unsigned long hash_trace(const struct trace *trace) +{ + return hash_pointer(trace->condstr, + hash_pointer(trace->file, + trace->line + trace->expect)); +} + +static bool hash_cmp(const void *htelem, void *cmpdata) +{ + 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 unsigned long rehash(const void *elem, void *priv) +{ + return hash_trace(elem); +} + +static void init_trace(struct trace *trace, + const char *condstr, const char *file, unsigned int line, + bool expect) +{ + trace->condstr = condstr; + trace->file = file; + trace->line = line; + trace->expect = expect; + trace->count = trace->right = 0; +} + +static struct trace *add_trace(const char *condstr, + const char *file, unsigned int line, bool expect) +{ + struct trace *trace = malloc(sizeof(*trace)); + init_trace(trace, condstr, file, line, expect); + hashtable_add(htable, hash_trace(trace), trace); + return trace; +} + +long _likely_trace(bool cond, bool expect, + const char *condstr, + const char *file, unsigned int line) +{ + struct trace *p, trace; + + if (!htable) + htable = hashtable_new(rehash, NULL); + + init_trace(&trace, condstr, file, line, expect); + p = hashtable_find(htable, hash_trace(&trace), hash_cmp, &trace); + if (!p) + p = add_trace(condstr, file, line, expect); + + p->count++; + if (cond == expect) + p->right++; + + 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 bool get_stats(void *elem, void *vinfo) +{ + struct trace *trace = elem; + struct get_stats_info *info = vinfo; + + if (trace->count < info->min_hits) + return false; + + if (right_ratio(trace) < info->worst_ratio) { + info->worst = trace; + info->worst_ratio = right_ratio(trace); + } + return false; +} + +const char *likely_stats(unsigned int min_hits, unsigned int percent) +{ + struct get_stats_info info; + char *ret; + + if (!htable) + return NULL; + + info.min_hits = min_hits; + info.worst = NULL; + info.worst_ratio = 2; + + /* This is O(n), but it's not likely called that often. */ + hashtable_traverse(htable, get_stats, &info); + + if (info.worst_ratio * 100 > percent) + return NULL; + + ret = malloc(strlen(info.worst->condstr) + + strlen(info.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); + + hashtable_del(htable, hash_trace(info.worst), info.worst); + free(info.worst); + + return ret; +} +#endif /*DEBUG*/ diff --git a/ccan/likely/likely.h b/ccan/likely/likely.h new file mode 100644 index 00000000..815ee228 --- /dev/null +++ b/ccan/likely/likely.h @@ -0,0 +1,129 @@ +#ifndef CCAN_LIKELY_H +#define CCAN_LIKELY_H +#include "config.h" +#include +#include + +#ifndef DEBUG +#if HAVE_BUILTIN_EXPECT +/** + * likely - indicate that a condition is likely to be true. + * @cond: the condition + * + * This uses a compiler extension where available to indicate a likely + * code path and optimize appropriately; it's also useful for readers + * to quickly identify exceptional paths through functions. The + * threshold for "likely" is usually considered to be between 90 and + * 99%; marginal cases should not be marked either way. + * + * See Also: + * unlikely(), unlikely_func, likely_stats() + * + * Example: + * // Returns false if we overflow. + * static inline bool inc_int(unsigned int *val) + * { + * *(val)++; + * if (likely(*val)) + * return true; + * return false; + * } + */ +#define likely(cond) __builtin_expect(!!(cond), 1) + +/** + * unlikely - indicate that a condition is unlikely to be true. + * @cond: the condition + * + * This uses a compiler extension where available to indicate an unlikely + * code path and optimize appropriately; see likely() above. + * + * See Also: + * likely(), unlikely_func, likely_stats() + * + * Example: + * // Prints a warning if we overflow. + * static inline void inc_int(unsigned int *val) + * { + * *(val)++; + * if (unlikely(*val == 0)) + * fprintf(stderr, "Overflow!"); + * } + */ +#define unlikely(cond) __builtin_expect(!!(cond), 0) +#else +#define likely(cond) (!!(cond)) +#define unlikely(cond) (!!(cond)) +#endif +#else /* DEBUG versions */ +#define likely(cond) \ + (_likely_trace(!!(cond), 1, stringify(cond), __FILE__, __LINE__)) +#define unlikely(cond) \ + (_likely_trace(!!(cond), 0, stringify(cond), __FILE__, __LINE__)) + +long _likely_trace(bool cond, bool expect, + const char *condstr, + const char *file, unsigned int line); +#endif + +#if HAVE_ATTRIBUTE_COLD +/** + * unlikely_func - indicate that a function is unlikely to be called. + * + * This uses a compiler extension where available to indicate an unlikely + * code path and optimize appropriately; see unlikely() above. + * + * It is usually used on logging or error routines. + * + * See Also: + * unlikely() + * + * Example: + * void unlikely_func die_moaning(const char *reason) + * { + * fprintf(stderr, "Dying: %s\n", reason); + * exit(1); + * } + */ +#define unlikely_func __attribute__((cold)) +#else +#define unlikely_func +#endif + +#ifdef DEBUG +/** + * likely_stats - return description of abused likely()/unlikely() + * @min_hits: minimum number of hits + * @percent: maximum percentage correct + * + * When DEBUG is defined, likely() and unlikely() trace their results: this + * causes a significant slowdown, but allows analysis of whether the stats + * are correct (unlikely_func can't traced). + * + * This function returns a malloc'ed description of the least-correct + * usage of likely() or unlikely(). It ignores places which have been + * called less than @min_hits times, and those which were predicted + * correctly more than @percent of the time. It returns NULL when + * nothing meets those criteria. + * + * Note that this call is destructive; the returned offender is + * removed from the trace so that the next call to likely_stats() will + * return the next-worst likely()/unlikely() usage. + * + * Example: + * // Print every place hit more than twice which was wrong > 5%. + * static void report_stats(void) + * { + * #ifdef DEBUG + * const char *bad; + * + * while ((bad = likely_stats(2, 95)) != NULL) { + * printf("Suspicious likely: %s", bad); + * free(bad); + * } + * #endif + * } + */ +const char *likely_stats(unsigned int min_hits, unsigned int percent); +#endif /* DEBUG */ +#endif /* CCAN_LIKELY_H */ diff --git a/ccan/likely/test/run-debug.c b/ccan/likely/test/run-debug.c new file mode 100644 index 00000000..198ac5b7 --- /dev/null +++ b/ccan/likely/test/run-debug.c @@ -0,0 +1,87 @@ +#define DEBUG 1 +#include +#include +#include +#include + +static bool one_seems_likely(unsigned int val) +{ + if (likely(val == 1)) + return true; + return false; +} + +static bool one_seems_unlikely(unsigned int val) +{ + if (unlikely(val == 1)) + return true; + return false; +} + +static bool likely_one_unlikely_two(unsigned int val1, unsigned int val2) +{ + /* Same line, check we don't get confused! */ + if (likely(val1 == 1) && unlikely(val2 == 2)) + return true; + return false; +} + +int main(int argc, char *argv[]) +{ + const char *bad; + + plan_tests(13); + + /* Correct guesses. */ + one_seems_likely(1); + ok1(likely_stats(0, 90) == NULL); + one_seems_unlikely(2); + ok1(likely_stats(0, 90) == NULL); + + /* Incorrect guesses. */ + one_seems_likely(0); + one_seems_likely(2); + /* Hasn't been hit 4 times, so this fails */ + ok1(!likely_stats(4, 90)); + bad = likely_stats(3, 90); + ok(strends(bad, "run-debug.c:9:likely(val == 1) correct 33% (1/3)"), + "likely_stats returned %s", bad); + + /* Nothing else above 90% */ + ok1(!likely_stats(0, 90)); + + /* This should get everything. */ + bad = likely_stats(0, 100); + ok(strends(bad, "run-debug.c:16:unlikely(val == 1) correct 100% (1/1)"), + "likely_stats returned %s", bad); + + /* Nothing left (table is actually cleared) */ + ok1(!likely_stats(0, 100)); + + /* Make sure unlikely works */ + one_seems_unlikely(0); + one_seems_unlikely(2); + one_seems_unlikely(1); + + bad = likely_stats(0, 90); + ok(strends(bad, "run-debug.c:16:unlikely(val == 1) correct 66% (2/3)"), + "likely_stats returned %s", bad); + ok1(!likely_stats(0, 100)); + + likely_one_unlikely_two(1, 1); + likely_one_unlikely_two(1, 1); + likely_one_unlikely_two(1, 1); + ok1(!likely_stats(0, 90)); + likely_one_unlikely_two(1, 2); + + bad = likely_stats(0, 90); + ok(strends(bad, "run-debug.c:24:unlikely(val2 == 2) correct 75% (3/4)"), + "likely_stats returned %s", 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); + + ok1(!likely_stats(0, 100)); + + exit(exit_status()); +} diff --git a/ccan/likely/test/run.c b/ccan/likely/test/run.c new file mode 100644 index 00000000..b6413b15 --- /dev/null +++ b/ccan/likely/test/run.c @@ -0,0 +1,36 @@ +#include +#include +#include +#include + +static bool one_seems_likely(unsigned int val) +{ + if (likely(val == 1)) + return true; + return false; +} + +static bool one_seems_unlikely(unsigned int val) +{ + if (unlikely(val == 1)) + return true; + return false; +} + +static unlikely_func bool calling_is_unlikely(void) +{ + return true; +} + +int main(int argc, char *argv[]) +{ + plan_tests(5); + + /* Without debug, we can only check that it doesn't effect functions. */ + ok1(one_seems_likely(1)); + ok1(!one_seems_likely(2)); + ok1(one_seems_unlikely(1)); + ok1(!one_seems_unlikely(2)); + ok1(calling_is_unlikely()); + exit(exit_status()); +} diff --git a/config.h b/config.h index d8504ce6..f3cdddf4 100644 --- a/config.h +++ b/config.h @@ -1,5 +1,6 @@ /* Simple config.h for gcc. */ #define HAVE_ALIGNOF 1 +#define HAVE_ATTRIBUTE_COLD 1 #define HAVE_ATTRIBUTE_PRINTF 1 #define HAVE_BIG_ENDIAN 0 #define HAVE_BUILTIN_CHOOSE_EXPR 1 -- 2.39.2