Import timeouts.c directly from William Ahern's git.

Imported from here: https://github.com/wahern/timeout

Imported as of upstream e5a9e8bfaa9c631bdc54002181795931b65bdc1a.

All sources unmodified.

11 files changed, 1228 insertions, 0 deletions

diff --git a/src/ext/timeouts/bench/Rules.mk b/src/ext/timeouts/bench/Rules.mk
new file mode 100644
index 0000000000..3ee72f3eff
--- /dev/null
+++ b/src/ext/timeouts/bench/Rules.mk
@@ -0,0 +1,49 @@
+BENCH_MODS = bench.so $(BENCH_ALGOS:%=bench-%.so)
+BENCH_ALGOS = wheel heap llrb
+BENCH_OPS = add del expire
+
+$(top_builddir)/bench/bench.so: $(top_srcdir)/bench/bench.c
+$(top_builddir)/bench/bench-wheel.so: $(top_srcdir)/bench/bench-wheel.c
+$(top_builddir)/bench/bench-heap.so: $(top_srcdir)/bench/bench-heap.c
+$(top_builddir)/bench/bench-llrb.so: $(top_srcdir)/bench/bench-llrb.c
+
+$(BENCH_MODS:%=$(top_builddir)/bench/%): $(top_srcdir)/timeout.h $(top_srcdir)/timeout.c $(top_srcdir)/bench/bench.h
+	mkdir -p $(@D)
+	@$(SHRC); echo_cmd $(CC) -o $@ $(top_srcdir)/bench/$(@F:%.so=%.c) $(ALL_CPPFLAGS) $(ALL_CFLAGS) $(ALL_SOFLAGS) $(ALL_LDFLAGS) $(ALL_LIBS)
+
+$(BENCH_OPS:%=$(top_builddir)/bench/wheel-%.dat): $(top_builddir)/bench/bench-wheel.so $(top_builddir)/bench/bench.so $(top_srcdir)/bench/bench-aux.lua
+$(BENCH_OPS:%=$(top_builddir)/bench/heap-%.dat): $(top_builddir)/bench/bench-heap.so $(top_builddir)/bench/bench.so $(top_srcdir)/bench/bench-aux.lua
+$(BENCH_OPS:%=$(top_builddir)/bench/llrb-%.dat): $(top_builddir)/bench/bench-llrb.so $(top_builddir)/bench/bench.so $(top_srcdir)/bench/bench-aux.lua
+
+$(BENCH_ALGOS:%=$(top_builddir)/bench/%-add.dat): $(top_srcdir)/bench/bench-add.lua
+	@$(SHRC); echo_cmd cd $(@D) && echo_cmd $(LUA) $${top_srcdir}/bench/bench-add.lua $${top_builddir}/bench/bench-$(@F:%-add.dat=%).so > $(@F).tmp
+	mv $@.tmp $@
+
+$(BENCH_ALGOS:%=$(top_builddir)/bench/%-del.dat): $(top_srcdir)/bench/bench-del.lua
+	@$(SHRC); echo_cmd cd $(@D) && echo_cmd $(LUA) $${top_srcdir}/bench/bench-del.lua $${top_builddir}/bench/bench-$(@F:%-del.dat=%).so > $(@F).tmp
+	mv $@.tmp $@
+
+$(BENCH_ALGOS:%=$(top_builddir)/bench/%-expire.dat): $(top_srcdir)/bench/bench-expire.lua
+	@$(SHRC); echo_cmd cd $(@D) && echo_cmd $(LUA) $${top_srcdir}/bench/bench-expire.lua $${top_builddir}/bench/bench-$(@F:%-expire.dat=%).so > $(@F).tmp
+	mv $@.tmp $@
+
+$(top_builddir)/bench/bench.eps: \
+	$(BENCH_OPS:%=$(top_builddir)/bench/wheel-%.dat) \
+	$(BENCH_OPS:%=$(top_builddir)/bench/heap-%.dat)
+#	$(BENCH_OPS:%=$(top_builddir)/bench/llrb-%.dat)
+
+$(top_builddir)/bench/bench.eps: $(top_srcdir)/bench/bench.plt
+	@$(SHRC); echo_cmd cd $(@D) && echo_cmd gnuplot $${top_srcdir}/bench/bench.plt > $(@F).tmp
+	mv $@.tmp $@
+
+$(top_builddir)/bench/bench.pdf: $(top_builddir)/bench/bench.eps
+	@$(SHRC); echo_cmd ps2pdf $${top_builddir}/bench/bench.eps $@
+
+bench-mods: $(BENCH_MODS:%=$(top_builddir)/bench/%)
+
+bench-all: $(top_builddir)/bench/bench.pdf
+
+bench-clean:
+	$(RM) -r $(top_builddir)/bench/*.so $(top_builddir)/bench/*.dSYM
+	$(RM) $(top_builddir)/bench/*.dat $(top_builddir)/bench/*.tmp
+	$(RM) $(top_builddir)/bench/bench.{eps,pdf}
diff --git a/src/ext/timeouts/bench/bench-add.lua b/src/ext/timeouts/bench/bench-add.lua
new file mode 100755
index 0000000000..64a921d3de
--- /dev/null
+++ b/src/ext/timeouts/bench/bench-add.lua
@@ -0,0 +1,30 @@
+#!/usr/bin/env lua
+
+local bench = require"bench"
+local aux = require"bench-aux"
+
+local lib = ... or aux.optenv("BENCH_L", "bench-wheel.so")
+local limit = tonumber(aux.optenv("BENCH_N", 1000000))
+local step  = tonumber(aux.optenv("BENCH_S", limit / 100))
+local exp_step = tonumber(aux.optenv("BENCH_E", 1.0))
+local verbose = aux.toboolean(os.getenv("BENCH_V", false))
+
+local B = bench.new(lib, count, nil, verbose)
+local fill_count, fill_last = B:fill(limit)
+
+for i=0,limit,step do
+	local exp_elapsed, fill_elapsed, fill_rate
+
+	-- expire all timeouts
+	--exp_elapsed = aux.time(B.expire, B, fill_count, fill_last * exp_step)
+	exp_elapsed = aux.time(B.del, B, 0, fill_count)
+	assert(B:empty())
+
+	-- add i timeouts
+	fill_elapsed, fill_count, fill_last = aux.time(B.fill, B, i)
+	assert(fill_count == i)
+	fill_rate = fill_elapsed > 0 and (fill_count / fill_elapsed) or 0
+
+	local fmt = verbose and "%d\t%f\t(%d/s)\t(exp:%f)" or "%d\t%f"
+	aux.say(fmt, i, fill_elapsed, fill_rate, exp_elapsed)
+end
diff --git a/src/ext/timeouts/bench/bench-aux.lua b/src/ext/timeouts/bench/bench-aux.lua
new file mode 100644
index 0000000000..6321247421
--- /dev/null
+++ b/src/ext/timeouts/bench/bench-aux.lua
@@ -0,0 +1,30 @@
+local bench = require"bench"
+local clock = bench.clock
+
+local aux = {}
+
+local function time_return(begun, ...)
+	local duration = clock() - begun
+	return duration, ...
+end
+
+function aux.time(f, ...)
+	local begun = clock()
+	return time_return(begun, f(...))
+end
+
+function aux.say(...)
+	print(string.format(...))
+end
+
+function aux.toboolean(s)
+	return tostring(s):match("^[1TtYy]") and true or false
+end
+
+function aux.optenv(k, def)
+	local s = os.getenv(k)
+
+	return (s and #s > 0 and s) or def
+end
+
+return aux
diff --git a/src/ext/timeouts/bench/bench-del.lua b/src/ext/timeouts/bench/bench-del.lua
new file mode 100755
index 0000000000..4306745f21
--- /dev/null
+++ b/src/ext/timeouts/bench/bench-del.lua
@@ -0,0 +1,25 @@
+#!/usr/bin/env lua
+
+local bench = require"bench"
+local aux = require"bench-aux"
+
+local lib = ... or aux.optenv("BENCH_L", "bench-wheel.so")
+local limit = tonumber(aux.optenv("BENCH_N", 1000000))
+local step  = tonumber(aux.optenv("BENCH_S", limit / 100))
+local verbose = aux.toboolean(os.getenv("BENCH_V", false))
+
+local B = bench.new(lib, count)
+
+for i=0,limit,step do
+	-- add i timeouts
+	local fill_elapsed, fill_count = aux.time(B.fill, B, i, 60 * 1000000)
+	assert(i == fill_count)
+
+	--- delete i timeouts
+	local del_elapsed = aux.time(B.del, B, 0, fill_count)
+	assert(B:empty())
+	local del_rate = i > 0 and i / del_elapsed or 0
+
+	local fmt = verbose and "%d\t%f\t(%d/s)\t(fill:%f)" or "%d\t%f"
+	aux.say(fmt, i, del_elapsed, del_rate, fill_elapsed)
+end
diff --git a/src/ext/timeouts/bench/bench-expire.lua b/src/ext/timeouts/bench/bench-expire.lua
new file mode 100755
index 0000000000..3e6374ed52
--- /dev/null
+++ b/src/ext/timeouts/bench/bench-expire.lua
@@ -0,0 +1,29 @@
+#!/usr/bin/env lua
+
+local bench = require"bench"
+local aux = require"bench-aux"
+
+local lib = ... or aux.optenv("BENCH_L", "bench-wheel.so")
+local limit = tonumber(aux.optenv("BENCH_N", 1000000))
+local step  = tonumber(aux.optenv("BENCH_S", limit / 100))
+-- expire 1/1000 * #timeouts per clock update
+local exp_step = tonumber(aux.optenv("BENCH_E", 0.0001)) 
+local verbose = aux.toboolean(os.getenv("BENCH_V", false))
+
+local B = require"bench".new(lib, count)
+
+for i=0,limit,step do
+	-- add i timeouts
+	local fill_elapsed, fill_count, fill_last  = aux.time(B.fill, B, i)
+
+	-- expire timeouts by iteratively updating clock. exp_step is the
+	-- approximate number of timeouts (as a fraction of the total number
+	-- of timeouts) that will expire per update.
+	local exp_elapsed, exp_count = aux.time(B.expire, B, fill_count, math.floor(fill_last * exp_step))
+	assert(exp_count == i)
+	assert(B:empty())
+	local exp_rate = i > 0 and i / exp_elapsed or 0
+
+	local fmt = verbose and "%d\t%f\t(%d/s)\t(fill:%f)" or "%d\t%f"
+	aux.say(fmt, i, exp_elapsed, exp_rate, fill_elapsed)
+end
diff --git a/src/ext/timeouts/bench/bench-heap.c b/src/ext/timeouts/bench/bench-heap.c
new file mode 100644
index 0000000000..f1166a4d7e
--- /dev/null
+++ b/src/ext/timeouts/bench/bench-heap.c
@@ -0,0 +1,236 @@
+/*
+ * Copyright (c) 2006 Maxim Yegorushkin <maxim.yegorushkin@gmail.com>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. The name of the author may not be used to endorse or promote products
+ *    derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+#ifndef _MIN_HEAP_H_
+#define _MIN_HEAP_H_
+
+#include <stdlib.h>
+#include <err.h>
+#include "timeout.h"
+#include "bench.h"
+
+#define min_heap_idx interval
+
+typedef timeout_t min_heap_idx_t;
+
+typedef struct min_heap
+{
+    struct timeout** p;
+    unsigned n, a;
+    timeout_t curtime;
+} min_heap_t;
+
+static inline void           min_heap_ctor(min_heap_t* s);
+static inline void           min_heap_dtor(min_heap_t* s);
+static inline void           min_heap_elem_init(struct timeout* e);
+static inline int            min_heap_elem_greater(struct timeout *a, struct timeout *b);
+static inline int            min_heap_empty(min_heap_t* s);
+static inline unsigned       min_heap_size(min_heap_t* s);
+static inline struct timeout*  min_heap_top(min_heap_t* s);
+static inline int            min_heap_reserve(min_heap_t* s, unsigned n);
+static inline int            min_heap_push(min_heap_t* s, struct timeout* e);
+static inline struct timeout*  min_heap_pop(min_heap_t* s);
+static inline int            min_heap_erase(min_heap_t* s, struct timeout* e);
+static inline void           min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct timeout* e);
+static inline void           min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct timeout* e);
+
+int min_heap_elem_greater(struct timeout *a, struct timeout *b)
+{
+    return a->expires > b->expires;
+}
+
+void min_heap_ctor(min_heap_t* s) { s->p = 0; s->n = 0; s->a = 0; }
+void min_heap_dtor(min_heap_t* s) { if(s->p) free(s->p); }
+void min_heap_elem_init(struct timeout* e) { e->min_heap_idx = -1; }
+int min_heap_empty(min_heap_t* s) { return 0u == s->n; }
+unsigned min_heap_size(min_heap_t* s) { return s->n; }
+struct timeout* min_heap_top(min_heap_t* s) { return s->n ? *s->p : 0; }
+
+int min_heap_push(min_heap_t* s, struct timeout* e)
+{
+    if(min_heap_reserve(s, s->n + 1))
+        return -1;
+    min_heap_shift_up_(s, s->n++, e);
+    return 0;
+}
+
+struct timeout* min_heap_pop(min_heap_t* s)
+{
+    if(s->n)
+    {
+        struct timeout* e = *s->p;
+        min_heap_shift_down_(s, 0u, s->p[--s->n]);
+        e->min_heap_idx = -1;
+        return e;
+    }
+    return 0;
+}
+
+int min_heap_erase(min_heap_t* s, struct timeout* e)
+{
+    if(((min_heap_idx_t)-1) != e->min_heap_idx)
+    {
+        struct timeout *last = s->p[--s->n];
+        unsigned parent = (e->min_heap_idx - 1) / 2;
+	/* we replace e with the last element in the heap.  We might need to
+	   shift it upward if it is less than its parent, or downward if it is
+	   greater than one or both its children. Since the children are known
+	   to be less than the parent, it can't need to shift both up and
+	   down. */
+        if (e->min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))
+             min_heap_shift_up_(s, e->min_heap_idx, last);
+        else
+             min_heap_shift_down_(s, e->min_heap_idx, last);
+        e->min_heap_idx = -1;
+        return 0;
+    }
+    return -1;
+}
+
+int min_heap_reserve(min_heap_t* s, unsigned n)
+{
+    if(s->a < n)
+    {
+        struct timeout** p;
+        unsigned a = s->a ? s->a * 2 : 8;
+        if(a < n)
+            a = n;
+        if(!(p = (struct timeout**)realloc(s->p, a * sizeof *p)))
+            return -1;
+        s->p = p;
+        s->a = a;
+    }
+    return 0;
+}
+
+void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct timeout* e)
+{
+    unsigned parent = (hole_index - 1) / 2;
+    while(hole_index && min_heap_elem_greater(s->p[parent], e))
+    {
+        (s->p[hole_index] = s->p[parent])->min_heap_idx = hole_index;
+        hole_index = parent;
+        parent = (hole_index - 1) / 2;
+    }
+    (s->p[hole_index] = e)->min_heap_idx = hole_index;
+}
+
+void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct timeout* e)
+{
+    unsigned min_child = 2 * (hole_index + 1);
+    while(min_child <= s->n)
+	{
+        min_child -= min_child == s->n || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]);
+        if(!(min_heap_elem_greater(e, s->p[min_child])))
+            break;
+        (s->p[hole_index] = s->p[min_child])->min_heap_idx = hole_index;
+        hole_index = min_child;
+        min_child = 2 * (hole_index + 1);
+	}
+    min_heap_shift_up_(s, hole_index,  e);
+}
+
+#endif /* _MIN_HEAP_H_ */
+
+
+static void *init(struct timeout *timeout, size_t count, int verbose) {
+    min_heap_t *H;
+    size_t i;
+
+    H = calloc(1, sizeof *H);
+
+    min_heap_ctor(H);
+    if (0 != min_heap_reserve(H, count))
+        err(1, "realloc");
+
+    for (i = 0; i < count; i++) {
+        min_heap_elem_init(&timeout[i]);
+    }
+
+    return H;
+} /* init() */
+
+
+static void add(void *ctx, struct timeout *to, timeout_t expires) {
+    min_heap_t *H = ctx;
+    min_heap_erase(H, to);
+    to->expires = H->curtime + expires;
+    if (0 != min_heap_push(H, to))
+        err(1, "realloc");
+} /* add() */
+
+
+static void del(void *ctx, struct timeout *to) {
+    min_heap_erase(ctx, to);
+} /* del() */
+
+
+static struct timeout *get(void *ctx) {
+    min_heap_t *H = ctx;
+    struct timeout *to;
+
+    if ((to = min_heap_top(H)) && to->expires <= H->curtime)
+        return min_heap_pop(H);
+
+    return NULL;
+} /* get() */
+
+
+static void update(void *ctx, timeout_t ts) {
+    min_heap_t *H = ctx;
+    H->curtime = ts;
+} /* update() */
+
+
+static void check(void *ctx) {
+    return;
+} /* check() */
+
+
+static int empty(void *ctx) {
+    min_heap_t *H = ctx;
+
+    return (NULL == min_heap_top(H));
+} /* empty() */
+
+
+static void destroy(void *H) {
+    free(H);
+    return;
+} /* destroy() */
+
+
+const struct benchops benchops = {
+    .init    = &init,
+    .add     = &add,
+    .del     = &del,
+    .get     = &get,
+    .update  = &update,
+    .check   = &check,
+    .empty   = &empty,
+    .destroy = &destroy,
+};
+
diff --git a/src/ext/timeouts/bench/bench-llrb.c b/src/ext/timeouts/bench/bench-llrb.c
new file mode 100644
index 0000000000..bdb02f0704
--- /dev/null
+++ b/src/ext/timeouts/bench/bench-llrb.c
@@ -0,0 +1,425 @@
+/* ==========================================================================
+ * llrb.h - Iterative Left-leaning Red-Black Tree.
+ * --------------------------------------------------------------------------
+ * Copyright (c) 2011, 2013  William Ahern <william@25thandClement.com>
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the
+ * "Software"), to deal in the Software without restriction, including
+ * without limitation the rights to use, copy, modify, merge, publish,
+ * distribute, sublicense, and/or sell copies of the Software, and to permit
+ * persons to whom the Software is furnished to do so, subject to the
+ * following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included
+ * in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN
+ * NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
+ * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
+ * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
+ * USE OR OTHER DEALINGS IN THE SOFTWARE.
+ * --------------------------------------------------------------------------
+ * CREDITS:
+ * 	o Algorithm courtesy of Robert Sedgewick, "Left-leaning Red-Black
+ * 	  Trees" (September 2008); and Robert Sedgewick and Kevin Wayne,
+ * 	  Algorithms (4th ed. 2011).
+ *
+ * 	  Sedgewick touts the simplicity of the recursive implementation,
+ * 	  but at least for the 2-3 tree variant the iterative approach is
+ * 	  almost line-for-line identical. The magic of C pointers helps;
+ * 	  it'd be uglier with Java.
+ *
+ * 	  A couple of missing NULL checks were added to Sedgewick's deletion
+ * 	  example, and insert was optimized to short-circuit rotations when
+ * 	  walking up the tree.
+ * 
+ * 	o Code implemented in the fashion of Niels Provos' excellent *BSD
+ * 	  sys/tree.h pre-processor library.
+ *
+ * 	  Regarding relative performance, I've refrained from sharing my own
+ * 	  benchmarks. Differences in run-time speed were too correlated to
+ * 	  compiler options and other external factors.
+ *
+ * 	  Provos' delete implementation doesn't need to start at the root of
+ * 	  the tree. However, RB_REMOVE must be passed the actual node to be
+ * 	  removed. LLRB_REMOVE merely requires a key, much like
+ * 	  RB_FIND/LLRB_FIND.
+ * ==========================================================================
+ */
+#ifndef LLRB_H
+#define LLRB_H
+
+#define LLRB_VENDOR "william@25thandClement.com"
+#define LLRB_VERSION 0x20130925
+
+#ifndef LLRB_STATIC
+#ifdef __GNUC__
+#define LLRB_STATIC __attribute__((__unused__)) static
+#else
+#define LLRB_STATIC static
+#endif
+#endif
+
+#define LLRB_HEAD(name, type) \
+struct name { struct type *rbh_root; }
+
+#define LLRB_INITIALIZER(root) { 0 }
+
+#define LLRB_INIT(root) do { (root)->rbh_root = 0; } while (0)
+
+#define LLRB_BLACK 0
+#define LLRB_RED   1
+
+#define LLRB_ENTRY(type) \
+struct { struct type *rbe_left, *rbe_right, *rbe_parent; _Bool rbe_color; }
+
+#define LLRB_LEFT(elm, field) (elm)->field.rbe_left
+#define LLRB_RIGHT(elm, field) (elm)->field.rbe_right
+#define LLRB_PARENT(elm, field) (elm)->field.rbe_parent
+#define LLRB_EDGE(head, elm, field) (((elm) == LLRB_ROOT(head))? &LLRB_ROOT(head) : ((elm) == LLRB_LEFT(LLRB_PARENT((elm), field), field))? &LLRB_LEFT(LLRB_PARENT((elm), field), field) : &LLRB_RIGHT(LLRB_PARENT((elm), field), field))
+#define LLRB_COLOR(elm, field) (elm)->field.rbe_color
+#define LLRB_ROOT(head) (head)->rbh_root
+#define LLRB_EMPTY(head) ((head)->rbh_root == 0)
+#define LLRB_ISRED(elm, field) ((elm) && LLRB_COLOR((elm), field) == LLRB_RED)
+
+#define LLRB_PROTOTYPE(name, type, field, cmp) \
+	LLRB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
+#define LLRB_PROTOTYPE_STATIC(name, type, field, cmp) \
+	LLRB_PROTOTYPE_INTERNAL(name, type, field, cmp, LLRB_STATIC)
+#define LLRB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
+attr struct type *name##_LLRB_INSERT(struct name *, struct type *); \
+attr struct type *name##_LLRB_DELETE(struct name *, struct type *); \
+attr struct type *name##_LLRB_FIND(struct name *, struct type *); \
+attr struct type *name##_LLRB_MIN(struct type *); \
+attr struct type *name##_LLRB_MAX(struct type *); \
+attr struct type *name##_LLRB_NEXT(struct type *);
+
+#define LLRB_GENERATE(name, type, field, cmp) \
+	LLRB_GENERATE_INTERNAL(name, type, field, cmp,)
+#define LLRB_GENERATE_STATIC(name, type, field, cmp) \
+	LLRB_GENERATE_INTERNAL(name, type, field, cmp, LLRB_STATIC)
+#define LLRB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
+static inline void name##_LLRB_ROTL(struct type **pivot) { \
+	struct type *a = *pivot; \
+	struct type *b = LLRB_RIGHT(a, field); \
+	if ((LLRB_RIGHT(a, field) = LLRB_LEFT(b, field))) \
+		LLRB_PARENT(LLRB_RIGHT(a, field), field) = a; \
+	LLRB_LEFT(b, field) = a; \
+	LLRB_COLOR(b, field) = LLRB_COLOR(a, field); \
+	LLRB_COLOR(a, field) = LLRB_RED; \
+	LLRB_PARENT(b, field) = LLRB_PARENT(a, field); \
+	LLRB_PARENT(a, field) = b; \
+	*pivot = b; \
+} \
+static inline void name##_LLRB_ROTR(struct type **pivot) { \
+	struct type *b = *pivot; \
+	struct type *a = LLRB_LEFT(b, field); \
+	if ((LLRB_LEFT(b, field) = LLRB_RIGHT(a, field))) \
+		LLRB_PARENT(LLRB_LEFT(b, field), field) = b; \
+	LLRB_RIGHT(a, field) = b; \
+	LLRB_COLOR(a, field) = LLRB_COLOR(b, field); \
+	LLRB_COLOR(b, field) = LLRB_RED; \
+	LLRB_PARENT(a, field) = LLRB_PARENT(b, field); \
+	LLRB_PARENT(b, field) = a; \
+	*pivot = a; \
+} \
+static inline void name##_LLRB_FLIP(struct type *root) { \
+	LLRB_COLOR(root, field) = !LLRB_COLOR(root, field); \
+	LLRB_COLOR(LLRB_LEFT(root, field), field) = !LLRB_COLOR(LLRB_LEFT(root, field), field); \
+	LLRB_COLOR(LLRB_RIGHT(root, field), field) = !LLRB_COLOR(LLRB_RIGHT(root, field), field); \
+} \
+static inline void name##_LLRB_FIXUP(struct type **root) { \
+	if (LLRB_ISRED(LLRB_RIGHT(*root, field), field) && !LLRB_ISRED(LLRB_LEFT(*root, field), field)) \
+		name##_LLRB_ROTL(root); \
+	if (LLRB_ISRED(LLRB_LEFT(*root, field), field) && LLRB_ISRED(LLRB_LEFT(LLRB_LEFT(*root, field), field), field)) \
+		name##_LLRB_ROTR(root); \
+	if (LLRB_ISRED(LLRB_LEFT(*root, field), field) && LLRB_ISRED(LLRB_RIGHT(*root, field), field)) \
+		name##_LLRB_FLIP(*root); \
+} \
+attr struct type *name##_LLRB_INSERT(struct name *head, struct type *elm) { \
+	struct type **root = &LLRB_ROOT(head); \
+	struct type *parent = 0; \
+	while (*root) { \
+		int comp = (cmp)((elm), (*root)); \
+		parent = *root; \
+		if (comp < 0) \
+			root = &LLRB_LEFT(*root, field); \
+		else if (comp > 0) \
+			root = &LLRB_RIGHT(*root, field); \
+		else \
+			return *root; \
+	} \
+	LLRB_LEFT((elm), field) = 0; \
+	LLRB_RIGHT((elm), field) = 0; \
+	LLRB_COLOR((elm), field) = LLRB_RED; \
+	LLRB_PARENT((elm), field) = parent; \
+	*root = (elm); \
+	while (parent && (LLRB_ISRED(LLRB_LEFT(parent, field), field) || LLRB_ISRED(LLRB_RIGHT(parent, field), field))) { \
+		root = LLRB_EDGE(head, parent, field); \
+		parent = LLRB_PARENT(parent, field); \
+		name##_LLRB_FIXUP(root); \
+	} \
+	LLRB_COLOR(LLRB_ROOT(head), field) = LLRB_BLACK; \
+	return 0; \
+} \
+static inline void name##_LLRB_MOVL(struct type **pivot) { \
+	name##_LLRB_FLIP(*pivot); \
+	if (LLRB_ISRED(LLRB_LEFT(LLRB_RIGHT(*pivot, field), field), field)) { \
+		name##_LLRB_ROTR(&LLRB_RIGHT(*pivot, field)); \
+		name##_LLRB_ROTL(pivot); \
+		name##_LLRB_FLIP(*pivot); \
+	} \
+} \
+static inline void name##_LLRB_MOVR(struct type **pivot) { \
+	name##_LLRB_FLIP(*pivot); \
+	if (LLRB_ISRED(LLRB_LEFT(LLRB_LEFT(*pivot, field), field), field)) { \
+		name##_LLRB_ROTR(pivot); \
+		name##_LLRB_FLIP(*pivot); \
+	} \
+} \
+static inline struct type *name##_DELETEMIN(struct name *head, struct type **root) { \
+	struct type **pivot = root, *deleted, *parent; \
+	while (LLRB_LEFT(*pivot, field)) { \
+		if (!LLRB_ISRED(LLRB_LEFT(*pivot, field), field) && !LLRB_ISRED(LLRB_LEFT(LLRB_LEFT(*pivot, field), field), field)) \
+			name##_LLRB_MOVL(pivot); \
+		pivot = &LLRB_LEFT(*pivot, field); \
+	} \
+	deleted = *pivot; \
+	parent = LLRB_PARENT(*pivot, field); \
+	*pivot = 0; \
+	while (root != pivot) { \
+		pivot = LLRB_EDGE(head, parent, field); \
+		parent = LLRB_PARENT(parent, field); \
+		name##_LLRB_FIXUP(pivot); \
+	} \
+	return deleted; \
+} \
+attr struct type *name##_LLRB_DELETE(struct name *head, struct type *elm) { \
+	struct type **root = &LLRB_ROOT(head), *parent = 0, *deleted = 0; \
+	int comp; \
+	while (*root) { \
+		parent = LLRB_PARENT(*root, field); \
+		comp = (cmp)(elm, *root); \
+		if (comp < 0) { \
+			if (LLRB_LEFT(*root, field) && !LLRB_ISRED(LLRB_LEFT(*root, field), field) && !LLRB_ISRED(LLRB_LEFT(LLRB_LEFT(*root, field), field), field)) \
+				name##_LLRB_MOVL(root); \
+			root = &LLRB_LEFT(*root, field); \
+		} else { \
+			if (LLRB_ISRED(LLRB_LEFT(*root, field), field)) { \
+				name##_LLRB_ROTR(root); \
+				comp = (cmp)(elm, *root); \
+			} \
+			if (!comp && !LLRB_RIGHT(*root, field)) { \
+				deleted = *root; \
+				*root = 0; \
+				break; \
+			} \
+			if (LLRB_RIGHT(*root, field) && !LLRB_ISRED(LLRB_RIGHT(*root, field), field) && !LLRB_ISRED(LLRB_LEFT(LLRB_RIGHT(*root, field), field), field)) { \
+				name##_LLRB_MOVR(root); \
+				comp = (cmp)(elm, *root); \
+			} \
+			if (!comp) { \
+				struct type *orphan = name##_DELETEMIN(head, &LLRB_RIGHT(*root, field)); \
+				LLRB_COLOR(orphan, field) = LLRB_COLOR(*root, field); \
+				LLRB_PARENT(orphan, field) = LLRB_PARENT(*root, field); \
+				if ((LLRB_RIGHT(orphan, field) = LLRB_RIGHT(*root, field))) \
+					LLRB_PARENT(LLRB_RIGHT(orphan, field), field) = orphan; \
+				if ((LLRB_LEFT(orphan, field) = LLRB_LEFT(*root, field))) \
+					LLRB_PARENT(LLRB_LEFT(orphan, field), field) = orphan; \
+				deleted = *root; \
+				*root = orphan; \
+				parent = *root; \
+				break; \
+			} else \
+				root = &LLRB_RIGHT(*root, field); \
+		} \
+	} \
+	while (parent) { \
+		root = LLRB_EDGE(head, parent, field); \
+		parent = LLRB_PARENT(parent, field); \
+		name##_LLRB_FIXUP(root); \
+	} \
+	if (LLRB_ROOT(head)) \
+		LLRB_COLOR(LLRB_ROOT(head), field) = LLRB_BLACK; \
+	return deleted; \
+} \
+attr struct type *name##_LLRB_FIND(struct name *head, struct type *key) { \
+	struct type *elm = LLRB_ROOT(head); \
+	while (elm) { \
+		int comp = (cmp)(key, elm); \
+		if (comp < 0) \
+			elm = LLRB_LEFT(elm, field); \
+		else if (comp > 0) \
+			elm = LLRB_RIGHT(elm, field); \
+		else \
+			return elm; \
+	} \
+	return 0; \
+} \
+attr struct type *name##_LLRB_MIN(struct type *elm) { \
+	while (elm && LLRB_LEFT(elm, field)) \
+		elm = LLRB_LEFT(elm, field); \
+	return elm; \
+} \
+attr struct type *name##_LLRB_MAX(struct type *elm) { \
+	while (elm && LLRB_RIGHT(elm, field)) \
+		elm = LLRB_RIGHT(elm, field); \
+	return elm; \
+} \
+attr struct type *name##_LLRB_NEXT(struct type *elm) { \
+	if (LLRB_RIGHT(elm, field)) { \
+		return name##_LLRB_MIN(LLRB_RIGHT(elm, field)); \
+	} else if (LLRB_PARENT(elm, field)) { \
+		if (elm == LLRB_LEFT(LLRB_PARENT(elm, field), field)) \
+			return LLRB_PARENT(elm, field); \
+		while (LLRB_PARENT(elm, field) && elm == LLRB_RIGHT(LLRB_PARENT(elm, field), field)) \
+			elm = LLRB_PARENT(elm, field); \
+		return LLRB_PARENT(elm, field); \
+	} else return 0; \
+}
+
+#define LLRB_INSERT(name, head, elm) name##_LLRB_INSERT((head), (elm))
+#define LLRB_DELETE(name, head, elm) name##_LLRB_DELETE((head), (elm))
+#define LLRB_REMOVE(name, head, elm) name##_LLRB_DELETE((head), (elm))
+#define LLRB_FIND(name, head, elm) name##_LLRB_FIND((head), (elm))
+#define LLRB_MIN(name, head) name##_LLRB_MIN(LLRB_ROOT((head)))
+#define LLRB_MAX(name, head) name##_LLRB_MAX(LLRB_ROOT((head)))
+#define LLRB_NEXT(name, head, elm) name##_LLRB_NEXT((elm))
+
+#define LLRB_FOREACH(elm, name, head) \
+for ((elm) = LLRB_MIN(name, head); (elm); (elm) = name##_LLRB_NEXT((elm)))
+
+#endif /* LLRB_H */
+
+
+#include <stdlib.h>
+
+#include "timeout.h"
+#include "bench.h"
+
+
+struct rbtimeout {
+	timeout_t expires;
+
+	int pending;
+
+	LLRB_ENTRY(rbtimeout) rbe;
+};
+
+struct rbtimeouts {
+	timeout_t curtime;
+	LLRB_HEAD(tree, rbtimeout) tree;
+};
+
+
+static int timeoutcmp(struct rbtimeout *a, struct rbtimeout *b) {
+	if (a->expires < b->expires) {
+		return -1;
+	} else if (a->expires > b->expires) {
+		return 1;
+	} else if (a < b) {
+		return -1;
+	} else if (a > b) {
+		return 1;
+	} else {
+		return 0;
+	}
+} /* timeoutcmp() */
+
+LLRB_GENERATE_STATIC(tree, rbtimeout, rbe, timeoutcmp)
+
+static void *init(struct timeout *timeout, size_t count, int verbose) {
+	struct rbtimeouts *T;
+	size_t i;
+
+	T = malloc(sizeof *T);
+	T->curtime = 0;
+	LLRB_INIT(&T->tree);
+
+	for (i = 0; i < count; i++) {
+		struct rbtimeout *to = (void *)&timeout[i];
+		to->expires = 0;
+		to->pending = 0;
+	}
+
+	return T;
+} /* init() */
+
+
+static void add(void *ctx, struct timeout *_to, timeout_t expires) {
+	struct rbtimeouts *T = ctx;
+	struct rbtimeout *to = (void *)_to;
+
+	if (to->pending)
+		LLRB_REMOVE(tree, &T->tree, to);
+
+	to->expires = T->curtime + expires;
+	LLRB_INSERT(tree, &T->tree, to);
+	to->pending = 1;
+} /* add() */
+
+
+static void del(void *ctx, struct timeout *_to) {
+	struct rbtimeouts *T = ctx;
+	struct rbtimeout *to = (void *)_to;
+
+	LLRB_REMOVE(tree, &T->tree, to);
+	to->pending = 0;
+	to->expires = 0;
+} /* del() */
+
+
+static struct timeout *get(void *ctx) {
+	struct rbtimeouts *T = ctx;
+	struct rbtimeout *to;
+
+	if ((to = LLRB_MIN(tree, &T->tree)) && to->expires <= T->curtime) {
+		LLRB_REMOVE(tree, &T->tree, to);
+		to->pending = 0;
+		to->expires = 0;
+
+		return (void *)to;
+	}
+
+	return NULL;
+} /* get() */
+
+
+static void update(void *ctx, timeout_t ts) {
+	struct rbtimeouts *T = ctx;
+	T->curtime = ts;
+} /* update() */
+
+
+static void check(void *ctx) {
+	return;
+} /* check() */
+
+
+static int empty(void *ctx) {
+	struct rbtimeouts *T = ctx;
+
+	return LLRB_EMPTY(&T->tree);
+} /* empty() */
+
+
+static void destroy(void *ctx) {
+	free(ctx);
+	return;
+} /* destroy() */
+
+
+const struct benchops benchops = {
+	.init    = &init,
+	.add     = &add,
+	.del     = &del,
+	.get     = &get,
+	.update  = &update,
+	.check   = &check,
+	.empty   = &empty,
+	.destroy = &destroy,
+};
+
diff --git a/src/ext/timeouts/bench/bench-wheel.c b/src/ext/timeouts/bench/bench-wheel.c
new file mode 100644
index 0000000000..0cba1af83e
--- /dev/null
+++ b/src/ext/timeouts/bench/bench-wheel.c
@@ -0,0 +1,81 @@
+#include <stdlib.h>
+
+#define TIMEOUT_PUBLIC static
+
+#include "timeout.h"
+#include "timeout.c"
+#include "bench.h"
+
+
+static void *init(struct timeout *timeout, size_t count, int verbose) {
+	struct timeouts *T;
+	size_t i;
+	int error;
+
+	T = timeouts_open(TIMEOUT_mHZ, &error);
+
+	for (i = 0; i < count; i++) {
+		timeout_init(&timeout[i], 0);
+	}
+
+#if TIMEOUT_DEBUG - 0
+	timeout_debug = verbose;
+#endif
+
+	return T;
+} /* init() */
+
+
+static void add(void *T, struct timeout *to, timeout_t expires) {
+	timeouts_add(T, to, expires);
+} /* add() */
+
+
+static void del(void *T, struct timeout *to) {
+	timeouts_del(T, to);
+} /* del() */
+
+
+static struct timeout *get(void *T) {
+	return timeouts_get(T);
+} /* get() */
+
+
+static void update(void *T, timeout_t ts) {
+	timeouts_update(T, ts);
+} /* update() */
+
+
+static void (check)(void *T) {
+	if (!timeouts_check(T, stderr))
+		_Exit(1);
+} /* check() */
+
+
+static int empty(void *T) {
+	return !(timeouts_pending(T) || timeouts_expired(T));
+} /* empty() */
+
+
+static struct timeout *next(void *T, struct timeouts_it *it) {
+	return timeouts_next(T, it);
+} /* next() */
+
+
+static void destroy(void *T) {
+	timeouts_close(T);
+} /* destroy() */
+
+
+const struct benchops benchops = {
+	.init    = &init,
+	.add     = &add,
+	.del     = &del,
+	.get     = &get,
+	.update  = &update,
+	.check   = &check,
+	.empty   = &empty,
+	.next    = &next,
+	.destroy = &destroy
+};
+
diff --git a/src/ext/timeouts/bench/bench.c b/src/ext/timeouts/bench/bench.c
new file mode 100644
index 0000000000..0d4cee44a0
--- /dev/null
+++ b/src/ext/timeouts/bench/bench.c
@@ -0,0 +1,293 @@
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+#include <errno.h>
+#include <unistd.h>
+#include <dlfcn.h>
+
+#if __APPLE__
+#include <mach/mach_time.h>
+#endif
+
+#include <lua.h>
+#include <lualib.h>
+#include <lauxlib.h>
+
+#include "timeout.h"
+#include "bench.h"
+
+#if LUA_VERSION_NUM < 502
+static int lua_absindex(lua_State *L, int idx) {
+	return (idx > 0 || idx <= LUA_REGISTRYINDEX)? idx : lua_gettop(L) + idx + 1;
+} /* lua_absindex() */
+
+static void luaL_setfuncs(lua_State *L, const luaL_Reg *l, int nup) {
+	int i, t = lua_absindex(L, -1 - nup);
+
+	for (; l->name; l++) {
+		for (i = 0; i < nup; i++)
+			lua_pushvalue(L, -nup);
+		lua_pushcclosure(L, l->func, nup);
+		lua_setfield(L, t, l->name);
+	}
+
+	lua_pop(L, nup);
+} /* luaL_setfuncs() */
+
+#define luaL_newlibtable(L, l) \
+	lua_createtable(L, 0, (sizeof (l) / sizeof *(l)) - 1)
+
+#define luaL_newlib(L, l) \
+	(luaL_newlibtable((L), (l)), luaL_setfuncs((L), (l), 0))
+#endif
+
+#ifndef MAX
+#define MAX(a, b) (((a) > (b))? (a) : (b))
+#endif
+
+
+struct bench {
+	const char *path;
+	void *solib;
+	size_t count;
+	timeout_t timeout_max;
+	int verbose;
+
+	void *state;
+	struct timeout *timeout;
+	struct benchops ops;
+	timeout_t curtime;
+}; /* struct bench */
+
+
+#if __APPLE__
+static mach_timebase_info_data_t timebase;
+#endif
+
+
+static int long long monotime(void) {
+#if __APPLE__
+	unsigned long long abt;
+
+	abt = mach_absolute_time();
+	abt = abt * timebase.numer / timebase.denom;
+
+	return abt / 1000LL;
+#else
+	struct timespec ts;
+
+	clock_gettime(CLOCK_MONOTONIC, &ts);
+
+	return (ts.tv_sec * 1000000L) + (ts.tv_nsec / 1000L);
+#endif
+} /* monotime() */
+
+
+static int bench_clock(lua_State *L) {
+	lua_pushnumber(L, (double)monotime() / 1000000L);
+
+	return 1;
+} /* bench_clock() */
+
+
+static int bench_new(lua_State *L) {
+	const char *path = luaL_checkstring(L, 1);
+	size_t count = luaL_optinteger(L, 2, 1000000);
+	timeout_t timeout_max = luaL_optinteger(L, 3, 300 * 1000000L);
+	int verbose = (lua_isnone(L, 4))? 0 : lua_toboolean(L, 4);
+	struct bench *B;
+	struct benchops *ops;
+
+	B = lua_newuserdata(L, sizeof *B);
+	memset(B, 0, sizeof *B);
+
+	luaL_getmetatable(L, "BENCH*");
+	lua_setmetatable(L, -2);
+
+	B->count = count;
+	B->timeout_max = timeout_max;
+	B->verbose = verbose;
+
+	if (!(B->timeout = calloc(count, sizeof *B->timeout)))
+		return luaL_error(L, "%s", strerror(errno));
+
+	if (!(B->solib = dlopen(path, RTLD_NOW|RTLD_LOCAL)))
+		return luaL_error(L, "%s: %s", path, dlerror());
+
+	if (!(ops = dlsym(B->solib, "benchops")))
+		return luaL_error(L, "%s: %s", path, dlerror());
+
+	B->ops = *ops;
+	B->state = B->ops.init(B->timeout, B->count, B->verbose);
+
+	return 1;
+} /* bench_new() */
+
+
+static int bench_add(lua_State *L) {
+	struct bench *B = lua_touserdata(L, 1);
+	unsigned i;
+	timeout_t t;
+
+	i = (lua_isnoneornil(L, 2))? random() % B->count : (unsigned)luaL_checkinteger(L, 2);
+	t = (lua_isnoneornil(L, 3))? random() % B->timeout_max : (unsigned)luaL_checkinteger(L, 3);
+
+	B->ops.add(B->state, &B->timeout[i], t);
+
+	return 0;
+} /* bench_add() */
+
+
+static int bench_del(lua_State *L) {
+	struct bench *B = lua_touserdata(L, 1);
+	size_t i = luaL_optinteger(L, 2, random() % B->count);
+	size_t j = luaL_optinteger(L, 3, i);
+
+	while (i <= j && i < B->count) {
+		B->ops.del(B->state, &B->timeout[i]);
+		++i;
+	}
+
+	return 0;
+} /* bench_del() */
+
+
+static int bench_fill(lua_State *L) {
+	struct bench *B = lua_touserdata(L, 1);
+	size_t count = luaL_optinteger(L, 2, B->count);
+	long timeout_inc = luaL_optinteger(L, 3, -1), timeout_max = 0, timeout;
+	size_t i;
+
+	if (timeout_inc < 0) {
+		for (i = 0; i < count; i++) {
+			timeout = random() % B->timeout_max;
+			B->ops.add(B->state, &B->timeout[i], timeout);
+			timeout_max = MAX(timeout, timeout_max);
+		}
+	} else {
+		for (i = 0; i < count; i++) {
+			timeout = timeout_inc + i;
+			B->ops.add(B->state, &B->timeout[i], timeout_inc + i);
+			timeout_max = MAX(timeout, timeout_max);
+		}
+	}
+
+	lua_pushinteger(L, (lua_Integer)count);
+	lua_pushinteger(L, (lua_Integer)timeout_max);
+
+	return 2;
+} /* bench_fill() */
+
+
+static int bench_expire(lua_State *L) {
+	struct bench *B = lua_touserdata(L, 1);
+	unsigned count = luaL_optinteger(L, 2, B->count);
+	unsigned step = luaL_optinteger(L, 3, 300000);
+	size_t i = 0;
+
+	while (i < count && !B->ops.empty(B->state)) {
+		B->curtime += step;
+		B->ops.update(B->state, B->curtime);
+
+		while (B->ops.get(B->state))
+			i++;
+	}
+
+	lua_pushinteger(L, (lua_Integer)i);
+
+	return 1;
+} /* bench_expire() */
+
+
+static int bench_empty(lua_State *L) {
+	struct bench *B = lua_touserdata(L, 1);
+
+	lua_pushboolean(L, B->ops.empty(B->state));
+
+	return 1;
+} /* bench_empty() */
+
+
+static int bench__next(lua_State *L) {
+	struct bench *B = lua_touserdata(L, lua_upvalueindex(1));
+	struct timeouts_it *it = lua_touserdata(L, lua_upvalueindex(2));
+	struct timeout *to;
+
+	if (!B->ops.next || !(to = B->ops.next(B->state, it)))
+		return 0;
+
+	lua_pushinteger(L, luaL_optinteger(L, 2, 0) + 1);
+
+	lua_newtable(L);
+	lua_pushinteger(L, to->expires);
+	lua_setfield(L, -2, "expires");
+
+	return 2;
+} /* bench__next() */
+
+static int bench__pairs(lua_State *L) {
+	struct timeouts_it *it;
+
+	lua_settop(L, 1);
+
+	it = lua_newuserdata(L, sizeof *it);
+	TIMEOUTS_IT_INIT(it, TIMEOUTS_ALL);
+
+	lua_pushcclosure(L, &bench__next, 2);
+	lua_pushvalue(L, 1);
+	lua_pushinteger(L, 0);
+
+	return 3;
+} /* bench__pairs() */
+
+
+static int bench__gc(lua_State *L) {
+	struct bench *B = lua_touserdata(L, 1);
+
+	if (B->state) {
+		B->ops.destroy(B->state);
+		B->state = NULL;
+	}
+
+	return 0;
+} /* bench__gc() */
+
+
+static const luaL_Reg bench_methods[] = {
+	{ "add",    &bench_add },
+	{ "del",    &bench_del },
+	{ "fill",   &bench_fill },
+	{ "expire", &bench_expire },
+	{ "empty",  &bench_empty },
+	{ "close",  &bench__gc },
+	{ NULL,     NULL }
+};
+
+static const luaL_Reg bench_metatable[] = {
+	{ "__pairs", &bench__pairs },
+	{ "__gc",    &bench__gc },
+	{ NULL,      NULL }
+};
+
+static const luaL_Reg bench_globals[] = {
+	{ "new",   &bench_new },
+	{ "clock", &bench_clock },
+	{ NULL,  NULL }
+};
+
+int luaopen_bench(lua_State *L) {
+#if __APPLE__
+	mach_timebase_info(&timebase);
+#endif
+
+	if (luaL_newmetatable(L, "BENCH*")) {
+		luaL_setfuncs(L, bench_metatable, 0);
+		luaL_newlib(L, bench_methods);
+		lua_setfield(L, -2, "__index");
+	}
+
+	luaL_newlib(L, bench_globals);
+
+	return 1;
+} /* luaopen_bench() */
+
diff --git a/src/ext/timeouts/bench/bench.h b/src/ext/timeouts/bench/bench.h
new file mode 100644
index 0000000000..bc1f7cf177
--- /dev/null
+++ b/src/ext/timeouts/bench/bench.h
@@ -0,0 +1,11 @@
+struct benchops {
+	void *(*init)(struct timeout *, size_t, int);
+	void (*add)(void *, struct timeout *, timeout_t);
+	void (*del)(void *, struct timeout *);
+	struct timeout *(*get)(void *);
+	void (*update)(void *, timeout_t);
+	void (*check)(void *);
+	int (*empty)(void *);
+	struct timeout *(*next)(void *, struct timeouts_it *);
+	void (*destroy)(void *);
+}; /* struct benchops() */
diff --git a/src/ext/timeouts/bench/bench.plt b/src/ext/timeouts/bench/bench.plt
new file mode 100644
index 0000000000..6e143c65e1
--- /dev/null
+++ b/src/ext/timeouts/bench/bench.plt
@@ -0,0 +1,19 @@
+set terminal postscript color
+
+set key top left
+set xlabel "Number of timeouts"
+set ylabel "Time\n(microseconds)"
+#set logscale x
+
+set title "Time spent installing timeouts" font ",20"
+plot 'heap-add.dat' using 1:($2*1000000) title "min-heap" with lines ls 1 lw 3 lc "red", \
+     'wheel-add.dat' using 1:($2*1000000) title "hierarchical wheel" with lines ls 1 lw 3 lc "forest-green"
+
+set title "Time spent deleting timeouts" font ",20"
+plot 'heap-del.dat' using 1:($2*1000000) title "min-heap" with lines ls 1 lw 3 lc "red", \
+     'wheel-del.dat' using 1:($2*1000000) title "hierarchical wheel" with lines ls 1 lw 3 lc "forest-green"
+
+set title "Time spent expiring timeouts\n(by iteratively updating clock ~1000 times)" font ",20"
+plot 'heap-expire.dat' using 1:($2*1000000) title "min-heap" with lines ls 1 lw 3 lc "red", \
+     'wheel-expire.dat' using 1:($2*1000000) title "hierarchical wheel" with lines ls 1 lw 3 lc "forest-green"
+