likely: new module

diff --git a/ccan/likely/_info b/ccan/likely/_info
new file mode 100644 (file)
index 0000000..d72aa55
--- /dev/null
+++ b/ccan/likely/_info
@@ -0,0 +1,44 @@
+#include <string.h>
+#include <stdio.h>
+#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 <ccan/likely/likely.h>
+ *     #include <stdio.h>
+ *
+ *     int main(int argc, char *argv[])
+ *     {
+ *             // This example is silly: the compiler knows exit() is unlikely.
+ *             if (unlikely(argc == 1)) {
+ *                     fprintf(stderr, "Usage: %s <args>...\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 (file)
index 0000000..e4bee71
--- /dev/null
+++ b/ccan/likely/likely.c
@@ -0,0 +1,139 @@
+#ifdef DEBUG
+#include <ccan/likely/likely.h>
+#include <ccan/hash/hash.h>
+#include <ccan/hashtable/hashtable.h>
+#include <stdlib.h>
+#include <stdio.h>
+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 (file)
index 0000000..815ee22
--- /dev/null
+++ b/ccan/likely/likely.h
@@ -0,0 +1,129 @@
+#ifndef CCAN_LIKELY_H
+#define CCAN_LIKELY_H
+#include "config.h"
+#include <ccan/str/str.h>
+#include <stdbool.h>
+
+#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 (file)
index 0000000..198ac5b
--- /dev/null
+++ b/ccan/likely/test/run-debug.c
@@ -0,0 +1,87 @@
+#define DEBUG 1
+#include <ccan/likely/likely.c>
+#include <ccan/likely/likely.h>
+#include <ccan/tap/tap.h>
+#include <stdlib.h>
+
+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 (file)
index 0000000..b6413b1
--- /dev/null
+++ b/ccan/likely/test/run.c
@@ -0,0 +1,36 @@
+#include <ccan/likely/likely.c>
+#include <ccan/likely/likely.h>
+#include <ccan/tap/tap.h>
+#include <stdlib.h>
+
+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 d8504ce6530a7eeeb8301017f14c6d8292ef391c..f3cdddf4d9ced75a65d3956af9befa9f0dfb296b 100644 (file)
--- a/config.h
+++ b/config.h
@@ -1,5 +1,6 @@
 /* Simple config.h for gcc. */
 #define HAVE_ALIGNOF 1
 /* 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
 #define HAVE_ATTRIBUTE_PRINTF 1
 #define HAVE_BIG_ENDIAN 0
 #define HAVE_BUILTIN_CHOOSE_EXPR 1