aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/ck_ec.c425
-rw-r--r--src/ck_ec_timeutil.h150
-rw-r--r--src/ck_hs.c7
-rw-r--r--src/ck_ht.c3
4 files changed, 581 insertions, 4 deletions
diff --git a/src/ck_ec.c b/src/ck_ec.c
new file mode 100644
index 000000000000..9b24e762947c
--- /dev/null
+++ b/src/ck_ec.c
@@ -0,0 +1,425 @@
+#include <ck_ec.h>
+#include <ck_limits.h>
+
+#include "ck_ec_timeutil.h"
+
+#define DEFAULT_BUSY_LOOP_ITER 100U
+
+/*
+ * The 2ms, 8x/iter default parameter hit 1.024 seconds after 3
+ * iterations.
+ */
+#define DEFAULT_INITIAL_WAIT_NS 2000000L /* Start at 2 ms */
+/* Grow the wait time 8x/iteration. */
+#define DEFAULT_WAIT_SCALE_FACTOR 8
+#define DEFAULT_WAIT_SHIFT_COUNT 0
+
+struct ck_ec32_slow_path_state {
+ struct ck_ec32 *ec;
+ uint32_t flagged_word;
+};
+
+#ifdef CK_F_EC64
+struct ck_ec64_slow_path_state {
+ struct ck_ec64 *ec;
+ uint64_t flagged_word;
+};
+#endif
+
+/* Once we've waited for >= 1 sec, go for the full deadline. */
+static const struct timespec final_wait_time = {
+ .tv_sec = 1
+};
+
+void
+ck_ec32_wake(struct ck_ec32 *ec, const struct ck_ec_ops *ops)
+{
+ /* Spurious wake-ups are OK. Clear the flag before futexing. */
+ ck_pr_and_32(&ec->counter, (1U << 31) - 1);
+ ops->wake32(ops, &ec->counter);
+ return;
+}
+
+int
+ck_ec32_wait_slow(struct ck_ec32 *ec,
+ const struct ck_ec_ops *ops,
+ uint32_t old_value,
+ const struct timespec *deadline)
+{
+ return ck_ec32_wait_pred_slow(ec, ops, old_value,
+ NULL, NULL, deadline);
+}
+
+#ifdef CK_F_EC64
+void
+ck_ec64_wake(struct ck_ec64 *ec, const struct ck_ec_ops *ops)
+{
+ ck_pr_and_64(&ec->counter, ~1);
+ ops->wake64(ops, &ec->counter);
+ return;
+}
+
+int
+ck_ec64_wait_slow(struct ck_ec64 *ec,
+ const struct ck_ec_ops *ops,
+ uint64_t old_value,
+ const struct timespec *deadline)
+{
+ return ck_ec64_wait_pred_slow(ec, ops, old_value,
+ NULL, NULL, deadline);
+}
+#endif
+
+int
+ck_ec_deadline_impl(struct timespec *new_deadline,
+ const struct ck_ec_ops *ops,
+ const struct timespec *timeout)
+{
+ struct timespec now;
+ int r;
+
+ if (timeout == NULL) {
+ new_deadline->tv_sec = TIME_MAX;
+ new_deadline->tv_nsec = NSEC_MAX;
+ return 0;
+ }
+
+ r = ops->gettime(ops, &now);
+ if (r != 0) {
+ return -1;
+ }
+
+ *new_deadline = timespec_add(now, *timeout);
+ return 0;
+}
+
+/* The rest of the file implements wait_pred_slow. */
+
+/*
+ * Returns a timespec value for deadline_ptr. If deadline_ptr is NULL,
+ * returns a timespec far in the future.
+ */
+static struct timespec
+canonical_deadline(const struct timespec *deadline_ptr)
+{
+
+ if (deadline_ptr == NULL) {
+ return (struct timespec) { .tv_sec = TIME_MAX };
+ }
+
+ return *deadline_ptr;
+}
+
+/*
+ * Really slow (sleeping) path for ck_ec_wait. Drives the exponential
+ * backoff scheme to sleep for longer and longer periods of time,
+ * until either the sleep function returns true (the eventcount's
+ * value has changed), or the predicate returns non-0 (something else
+ * has changed).
+ *
+ * If deadline is ever reached, returns -1 (timeout).
+ *
+ * TODO: add some form of randomisation to the intermediate timeout
+ * values.
+ */
+static int
+exponential_backoff(struct ck_ec_wait_state *wait_state,
+ bool (*sleep)(const void *sleep_state,
+ const struct ck_ec_wait_state *wait_state,
+ const struct timespec *partial_deadline),
+ const void *sleep_state,
+ int (*pred)(const struct ck_ec_wait_state *state,
+ struct timespec *deadline),
+ const struct timespec *deadline)
+{
+ struct timespec begin;
+ struct timespec stop_backoff;
+ const struct ck_ec_ops *ops = wait_state->ops;
+ const uint32_t scale_factor = (ops->wait_scale_factor != 0)
+ ? ops->wait_scale_factor
+ : DEFAULT_WAIT_SCALE_FACTOR;
+ const uint32_t shift_count = (ops->wait_shift_count != 0)
+ ? ops->wait_shift_count
+ : DEFAULT_WAIT_SHIFT_COUNT;
+ uint32_t wait_ns = (ops->initial_wait_ns != 0)
+ ? ops->initial_wait_ns
+ : DEFAULT_INITIAL_WAIT_NS;
+ bool first = true;
+
+ for (;;) {
+ struct timespec now;
+ struct timespec partial_deadline;
+
+ if (check_deadline(&now, ops, *deadline) == true) {
+ /* Timeout. Bail out. */
+ return -1;
+ }
+
+ if (first) {
+ begin = now;
+ wait_state->start = begin;
+ stop_backoff = timespec_add(begin, final_wait_time);
+ first = false;
+ }
+
+ wait_state->now = now;
+ if (timespec_cmp(now, stop_backoff) >= 0) {
+ partial_deadline = *deadline;
+ } else {
+ do {
+ partial_deadline =
+ timespec_add_ns(begin, wait_ns);
+ wait_ns =
+ wait_time_scale(wait_ns,
+ scale_factor,
+ shift_count);
+ } while (timespec_cmp(partial_deadline, now) <= 0);
+ }
+
+ if (pred != NULL) {
+ int r = pred(wait_state, &partial_deadline);
+ if (r != 0) {
+ return r;
+ }
+ }
+
+ /* Canonicalize deadlines in the far future to NULL. */
+ if (sleep(sleep_state, wait_state,
+ ((partial_deadline.tv_sec == TIME_MAX)
+ ? NULL : &partial_deadline)) == true) {
+ return 0;
+ }
+ }
+}
+
+/*
+ * Loops up to BUSY_LOOP_ITER times, or until ec's counter value
+ * (including the flag) differs from old_value.
+ *
+ * Returns the new value in ec.
+ */
+#define DEF_WAIT_EASY(W) \
+ static uint##W##_t ck_ec##W##_wait_easy(struct ck_ec##W* ec, \
+ const struct ck_ec_ops *ops, \
+ uint##W##_t expected) \
+ { \
+ uint##W##_t current = ck_pr_load_##W(&ec->counter); \
+ size_t n = (ops->busy_loop_iter != 0) \
+ ? ops->busy_loop_iter \
+ : DEFAULT_BUSY_LOOP_ITER; \
+ \
+ for (size_t i = 0; \
+ i < n && current == expected; \
+ i++) { \
+ ck_pr_stall(); \
+ current = ck_pr_load_##W(&ec->counter); \
+ } \
+ \
+ return current; \
+ }
+
+DEF_WAIT_EASY(32)
+#ifdef CK_F_EC64
+DEF_WAIT_EASY(64)
+#endif
+#undef DEF_WAIT_EASY
+/*
+ * Attempts to upgrade ec->counter from unflagged to flagged.
+ *
+ * Returns true if the event count has changed. Otherwise, ec's
+ * counter word is equal to flagged on return, or has been at some
+ * time before the return.
+ */
+#define DEF_UPGRADE(W) \
+ static bool ck_ec##W##_upgrade(struct ck_ec##W* ec, \
+ uint##W##_t current, \
+ uint##W##_t unflagged, \
+ uint##W##_t flagged) \
+ { \
+ uint##W##_t old_word; \
+ \
+ if (current == flagged) { \
+ /* Nothing to do, no change. */ \
+ return false; \
+ } \
+ \
+ if (current != unflagged) { \
+ /* We have a different counter value! */ \
+ return true; \
+ } \
+ \
+ /* \
+ * Flag the counter value. The CAS only fails if the \
+ * counter is already flagged, or has a new value. \
+ */ \
+ return (ck_pr_cas_##W##_value(&ec->counter, \
+ unflagged, flagged, \
+ &old_word) == false && \
+ old_word != flagged); \
+ }
+
+DEF_UPGRADE(32)
+#ifdef CK_F_EC64
+DEF_UPGRADE(64)
+#endif
+#undef DEF_UPGRADE
+
+/*
+ * Blocks until partial_deadline on the ck_ec. Returns true if the
+ * eventcount's value has changed. If partial_deadline is NULL, wait
+ * forever.
+ */
+static bool
+ck_ec32_wait_slow_once(const void *vstate,
+ const struct ck_ec_wait_state *wait_state,
+ const struct timespec *partial_deadline)
+{
+ const struct ck_ec32_slow_path_state *state = vstate;
+ const struct ck_ec32 *ec = state->ec;
+ const uint32_t flagged_word = state->flagged_word;
+
+ wait_state->ops->wait32(wait_state, &ec->counter,
+ flagged_word, partial_deadline);
+ return ck_pr_load_32(&ec->counter) != flagged_word;
+}
+
+#ifdef CK_F_EC64
+static bool
+ck_ec64_wait_slow_once(const void *vstate,
+ const struct ck_ec_wait_state *wait_state,
+ const struct timespec *partial_deadline)
+{
+ const struct ck_ec64_slow_path_state *state = vstate;
+ const struct ck_ec64 *ec = state->ec;
+ const uint64_t flagged_word = state->flagged_word;
+
+ /* futex_wait will only compare the low 32 bits. Perform a
+ * full comparison here to maximise the changes of catching an
+ * ABA in the low 32 bits.
+ */
+ if (ck_pr_load_64(&ec->counter) != flagged_word) {
+ return true;
+ }
+
+ wait_state->ops->wait64(wait_state, &ec->counter,
+ flagged_word, partial_deadline);
+ return ck_pr_load_64(&ec->counter) != flagged_word;
+}
+#endif
+
+/*
+ * The full wait logic is a lot of code (> 1KB). Encourage the
+ * compiler to lay this all out linearly with LIKELY annotations on
+ * every early exit.
+ */
+#define WAIT_SLOW_BODY(W, ec, ops, pred, data, deadline_ptr, \
+ old_value, unflagged, flagged) \
+ do { \
+ struct ck_ec_wait_state wait_state = { \
+ .ops = ops, \
+ .data = data \
+ }; \
+ const struct ck_ec##W##_slow_path_state state = { \
+ .ec = ec, \
+ .flagged_word = flagged \
+ }; \
+ const struct timespec deadline = \
+ canonical_deadline(deadline_ptr); \
+ \
+ /* Detect infinite past deadlines. */ \
+ if (CK_CC_LIKELY(deadline.tv_sec <= 0)) { \
+ return -1; \
+ } \
+ \
+ for (;;) { \
+ uint##W##_t current; \
+ int r; \
+ \
+ current = ck_ec##W##_wait_easy(ec, ops, unflagged); \
+ \
+ /* \
+ * We're about to wait harder (i.e., \
+ * potentially with futex). Make sure the \
+ * counter word is flagged. \
+ */ \
+ if (CK_CC_LIKELY( \
+ ck_ec##W##_upgrade(ec, current, \
+ unflagged, flagged) == true)) { \
+ ck_pr_fence_acquire(); \
+ return 0; \
+ } \
+ \
+ /* \
+ * By now, ec->counter == flagged_word (at \
+ * some point in the past). Spin some more to \
+ * heuristically let any in-flight SP inc/add \
+ * to retire. This does not affect \
+ * correctness, but practically eliminates \
+ * lost wake-ups. \
+ */ \
+ current = ck_ec##W##_wait_easy(ec, ops, flagged); \
+ if (CK_CC_LIKELY(current != flagged_word)) { \
+ ck_pr_fence_acquire(); \
+ return 0; \
+ } \
+ \
+ r = exponential_backoff(&wait_state, \
+ ck_ec##W##_wait_slow_once, \
+ &state, \
+ pred, &deadline); \
+ if (r != 0) { \
+ return r; \
+ } \
+ \
+ if (ck_ec##W##_value(ec) != old_value) { \
+ ck_pr_fence_acquire(); \
+ return 0; \
+ } \
+ \
+ /* Spurious wake-up. Redo the slow path. */ \
+ } \
+ } while (0)
+
+int
+ck_ec32_wait_pred_slow(struct ck_ec32 *ec,
+ const struct ck_ec_ops *ops,
+ uint32_t old_value,
+ int (*pred)(const struct ck_ec_wait_state *state,
+ struct timespec *deadline),
+ void *data,
+ const struct timespec *deadline_ptr)
+{
+ const uint32_t unflagged_word = old_value;
+ const uint32_t flagged_word = old_value | (1UL << 31);
+
+ if (CK_CC_UNLIKELY(ck_ec32_value(ec) != old_value)) {
+ return 0;
+ }
+
+ WAIT_SLOW_BODY(32, ec, ops, pred, data, deadline_ptr,
+ old_value, unflagged_word, flagged_word);
+}
+
+#ifdef CK_F_EC64
+int
+ck_ec64_wait_pred_slow(struct ck_ec64 *ec,
+ const struct ck_ec_ops *ops,
+ uint64_t old_value,
+ int (*pred)(const struct ck_ec_wait_state *state,
+ struct timespec *deadline),
+ void *data,
+ const struct timespec *deadline_ptr)
+{
+ const uint64_t unflagged_word = old_value << 1;
+ const uint64_t flagged_word = unflagged_word | 1;
+
+ if (CK_CC_UNLIKELY(ck_ec64_value(ec) != old_value)) {
+ return 0;
+ }
+
+ WAIT_SLOW_BODY(64, ec, ops, pred, data, deadline_ptr,
+ old_value, unflagged_word, flagged_word);
+}
+#endif
+
+#undef WAIT_SLOW_BODY
diff --git a/src/ck_ec_timeutil.h b/src/ck_ec_timeutil.h
new file mode 100644
index 000000000000..50cfb67bf4a4
--- /dev/null
+++ b/src/ck_ec_timeutil.h
@@ -0,0 +1,150 @@
+#ifndef CK_EC_TIMEUTIL_H
+#define CK_EC_TIMEUTIL_H
+#include <ck_cc.h>
+#include <ck_ec.h>
+#include <ck_limits.h>
+#include <ck_stdint.h>
+#include <sys/time.h>
+
+#define TIME_MAX ((time_t)((1ULL << ((sizeof(time_t) * CHAR_BIT) - 1)) - 1))
+#define NSEC_MAX ((1000L * 1000 * 1000) - 1)
+
+/*
+ * Approximates (nsec * multiplier) >> shift. Clamps to UINT32_MAX on
+ * overflow.
+ */
+CK_CC_UNUSED static uint32_t
+wait_time_scale(uint32_t nsec,
+ uint32_t multiplier,
+ unsigned int shift)
+{
+ uint64_t temp = (uint64_t)nsec * multiplier;
+ uint64_t max = (uint64_t)UINT32_MAX << shift;
+
+ if (temp >= max) {
+ return UINT32_MAX;
+ }
+
+ return temp >> shift;
+}
+
+
+/*
+ * Returns ts + ns. ns is clamped to at most 1 second. Clamps the
+ * return value to TIME_MAX, NSEC_MAX on overflow.
+ *
+ */
+CK_CC_UNUSED static struct timespec timespec_add_ns(const struct timespec ts,
+ uint32_t ns)
+{
+ struct timespec ret = {
+ .tv_sec = TIME_MAX,
+ .tv_nsec = NSEC_MAX
+ };
+ time_t sec;
+ uint32_t sum_ns;
+
+ if (ns > (uint32_t)NSEC_MAX) {
+ if (ts.tv_sec >= TIME_MAX) {
+ return ret;
+ }
+
+ ret.tv_sec = ts.tv_sec + 1;
+ ret.tv_nsec = ts.tv_nsec;
+ return ret;
+ }
+
+ sec = ts.tv_sec;
+ sum_ns = ns + ts.tv_nsec;
+ if (sum_ns > NSEC_MAX) {
+ if (sec >= TIME_MAX) {
+ return ret;
+ }
+
+ sec++;
+ sum_ns -= (NSEC_MAX + 1);
+ }
+
+ ret.tv_sec = sec;
+ ret.tv_nsec = sum_ns;
+ return ret;
+}
+
+
+/*
+ * Returns ts + inc. If inc is negative, it is normalized to 0.
+ * Clamps the return value to TIME_MAX, NSEC_MAX on overflow.
+ */
+CK_CC_UNUSED static struct timespec timespec_add(const struct timespec ts,
+ const struct timespec inc)
+{
+ /* Initial return value is clamped to infinite future. */
+ struct timespec ret = {
+ .tv_sec = TIME_MAX,
+ .tv_nsec = NSEC_MAX
+ };
+ time_t sec;
+ unsigned long nsec;
+
+ /* Non-positive delta is a no-op. Invalid nsec is another no-op. */
+ if (inc.tv_sec < 0 || inc.tv_nsec < 0 || inc.tv_nsec > NSEC_MAX) {
+ return ts;
+ }
+
+ /* Detect overflow early. */
+ if (inc.tv_sec > TIME_MAX - ts.tv_sec) {
+ return ret;
+ }
+
+ sec = ts.tv_sec + inc.tv_sec;
+ /* This sum can't overflow if the inputs are valid.*/
+ nsec = (unsigned long)ts.tv_nsec + inc.tv_nsec;
+
+ if (nsec > NSEC_MAX) {
+ if (sec >= TIME_MAX) {
+ return ret;
+ }
+
+ sec++;
+ nsec -= (NSEC_MAX + 1);
+ }
+
+ ret.tv_sec = sec;
+ ret.tv_nsec = nsec;
+ return ret;
+}
+
+/* Compares two timespecs. Returns -1 if x < y, 0 if x == y, and 1 if x > y. */
+CK_CC_UNUSED static int timespec_cmp(const struct timespec x,
+ const struct timespec y)
+{
+ if (x.tv_sec != y.tv_sec) {
+ return (x.tv_sec < y.tv_sec) ? -1 : 1;
+ }
+
+ if (x.tv_nsec != y.tv_nsec) {
+ return (x.tv_nsec < y.tv_nsec) ? -1 : 1;
+ }
+
+ return 0;
+}
+
+/*
+ * Overwrites now with the current CLOCK_MONOTONIC time, and returns
+ * true if the current time is greater than or equal to the deadline,
+ * or the clock is somehow broken.
+ */
+CK_CC_UNUSED static bool check_deadline(struct timespec *now,
+ const struct ck_ec_ops *ops,
+ const struct timespec deadline)
+{
+ int r;
+
+ r = ops->gettime(ops, now);
+ if (r != 0) {
+ return true;
+ }
+
+ return timespec_cmp(*now, deadline) >= 0;
+}
+#endif /* !CK_EC_TIMEUTIL_H */
diff --git a/src/ck_hs.c b/src/ck_hs.c
index a7e15eaddbeb..246bceb2a0ab 100644
--- a/src/ck_hs.c
+++ b/src/ck_hs.c
@@ -106,9 +106,11 @@ ck_hs_map_signal(struct ck_hs_map *map, unsigned long h)
}
static bool
-_ck_hs_next(struct ck_hs *hs, struct ck_hs_map *map, struct ck_hs_iterator *i, void **key)
+_ck_hs_next(struct ck_hs *hs, struct ck_hs_map *map,
+ struct ck_hs_iterator *i, void **key)
{
void *value;
+
if (i->offset >= map->capacity)
return false;
@@ -143,6 +145,7 @@ ck_hs_iterator_init(struct ck_hs_iterator *iterator)
bool
ck_hs_next(struct ck_hs *hs, struct ck_hs_iterator *i, void **key)
{
+
return _ck_hs_next(hs, hs->map, i, key);
}
@@ -150,9 +153,11 @@ bool
ck_hs_next_spmc(struct ck_hs *hs, struct ck_hs_iterator *i, void **key)
{
struct ck_hs_map *m = i->map;
+
if (m == NULL) {
m = i->map = ck_pr_load_ptr(&hs->map);
}
+
return _ck_hs_next(hs, m, i, key);
}
diff --git a/src/ck_ht.c b/src/ck_ht.c
index 48b04c9678d9..66c7315038c1 100644
--- a/src/ck_ht.c
+++ b/src/ck_ht.c
@@ -30,9 +30,6 @@
/*
* This implementation borrows several techniques from Josh Dybnis's
* nbds library which can be found at http://code.google.com/p/nbds
- *
- * This release currently only includes support for 64-bit platforms.
- * We can address 32-bit platforms in a future release.
*/
#include <ck_cc.h>
#include <ck_md.h>