sys/contrib/ck/src/ck_ec.c

   1 #include <ck_ec.h>
   2 #include <ck_limits.h>
   3
   4 #include "ck_ec_timeutil.h"
   5
   6 #define DEFAULT_BUSY_LOOP_ITER 100U
   7
   8 /*
   9  * The 2ms, 8x/iter default parameter hit 1.024 seconds after 3
  10  * iterations.
  11  */
  12 #define DEFAULT_INITIAL_WAIT_NS 2000000L  /* Start at 2 ms */
  13 /* Grow the wait time 8x/iteration. */
  14 #define DEFAULT_WAIT_SCALE_FACTOR 8
  15 #define DEFAULT_WAIT_SHIFT_COUNT 0
  16
  17 struct ck_ec32_slow_path_state {
  18         struct ck_ec32 *ec;
  19         uint32_t flagged_word;
  20 };
  21
  22 #ifdef CK_F_EC64
  23 struct ck_ec64_slow_path_state {
  24         struct ck_ec64 *ec;
  25         uint64_t flagged_word;
  26 };
  27 #endif
  28
  29 /* Once we've waited for >= 1 sec, go for the full deadline. */
  30 static const struct timespec final_wait_time = {
  31         .tv_sec = 1
  32 };
  33
  34 void
  35 ck_ec32_wake(struct ck_ec32 *ec, const struct ck_ec_ops *ops)
  36 {
  37         /* Spurious wake-ups are OK. Clear the flag before futexing. */
  38         ck_pr_and_32(&ec->counter, (1U << 31) - 1);
  39         ops->wake32(ops, &ec->counter);
  40         return;
  41 }
  42
  43 int
  44 ck_ec32_wait_slow(struct ck_ec32 *ec,
  45     const struct ck_ec_ops *ops,
  46     uint32_t old_value,
  47     const struct timespec *deadline)
  48 {
  49         return ck_ec32_wait_pred_slow(ec, ops, old_value,
  50                                       NULL, NULL, deadline);
  51 }
  52
  53 #ifdef CK_F_EC64
  54 void
  55 ck_ec64_wake(struct ck_ec64 *ec, const struct ck_ec_ops *ops)
  56 {
  57         ck_pr_and_64(&ec->counter, ~1);
  58         ops->wake64(ops, &ec->counter);
  59         return;
  60 }
  61
  62 int
  63 ck_ec64_wait_slow(struct ck_ec64 *ec,
  64     const struct ck_ec_ops *ops,
  65     uint64_t old_value,
  66     const struct timespec *deadline)
  67 {
  68         return ck_ec64_wait_pred_slow(ec, ops, old_value,
  69                                       NULL, NULL, deadline);
  70 }
  71 #endif
  72
  73 int
  74 ck_ec_deadline_impl(struct timespec *new_deadline,
  75     const struct ck_ec_ops *ops,
  76     const struct timespec *timeout)
  77 {
  78         struct timespec now;
  79         int r;
  80
  81         if (timeout == NULL) {
  82                 new_deadline->tv_sec = TIME_MAX;
  83                 new_deadline->tv_nsec = NSEC_MAX;
  84                 return 0;
  85         }
  86
  87         r = ops->gettime(ops, &now);
  88         if (r != 0) {
  89                 return -1;
  90         }
  91
  92         *new_deadline = timespec_add(now, *timeout);
  93         return 0;
  94 }
  95
  96 /* The rest of the file implements wait_pred_slow. */
  97
  98 /*
  99  * Returns a timespec value for deadline_ptr. If deadline_ptr is NULL,
 100  * returns a timespec far in the future.
 101  */
 102 static struct timespec
 103 canonical_deadline(const struct timespec *deadline_ptr)
 104 {
 105
 106         if (deadline_ptr == NULL) {
 107                 return (struct timespec) { .tv_sec = TIME_MAX };
 108         }
 109
 110         return *deadline_ptr;
 111 }
 112
 113 /*
 114  * Really slow (sleeping) path for ck_ec_wait.  Drives the exponential
 115  * backoff scheme to sleep for longer and longer periods of time,
 116  * until either the sleep function returns true (the eventcount's
 117  * value has changed), or the predicate returns non-0 (something else
 118  * has changed).
 119  *
 120  * If deadline is ever reached, returns -1 (timeout).
 121  *
 122  * TODO: add some form of randomisation to the intermediate timeout
 123  * values.
 124  */
 125 static int
 126 exponential_backoff(struct ck_ec_wait_state *wait_state,
 127     bool (*sleep)(const void *sleep_state,
 128         const struct ck_ec_wait_state *wait_state,
 129         const struct timespec *partial_deadline),
 130     const void *sleep_state,
 131     int (*pred)(const struct ck_ec_wait_state *state,
 132         struct timespec *deadline),
 133     const struct timespec *deadline)
 134 {
 135         struct timespec begin;
 136         struct timespec stop_backoff;
 137         const struct ck_ec_ops *ops = wait_state->ops;
 138         const uint32_t scale_factor = (ops->wait_scale_factor != 0)
 139             ? ops->wait_scale_factor
 140             : DEFAULT_WAIT_SCALE_FACTOR;
 141         const uint32_t shift_count = (ops->wait_shift_count != 0)
 142             ? ops->wait_shift_count
 143             : DEFAULT_WAIT_SHIFT_COUNT;
 144         uint32_t wait_ns = (ops->initial_wait_ns != 0)
 145             ? ops->initial_wait_ns
 146             : DEFAULT_INITIAL_WAIT_NS;
 147         bool first = true;
 148
 149         for (;;) {
 150                 struct timespec now;
 151                 struct timespec partial_deadline;
 152
 153                 if (check_deadline(&now, ops, *deadline) == true) {
 154                         /* Timeout. Bail out. */
 155                         return -1;
 156                 }
 157
 158                 if (first) {
 159                         begin = now;
 160                         wait_state->start = begin;
 161                         stop_backoff = timespec_add(begin, final_wait_time);
 162                         first = false;
 163                 }
 164
 165                 wait_state->now = now;
 166                 if (timespec_cmp(now, stop_backoff) >= 0) {
 167                         partial_deadline = *deadline;
 168                 } else {
 169                         do {
 170                                 partial_deadline =
 171                                     timespec_add_ns(begin, wait_ns);
 172                                 wait_ns =
 173                                     wait_time_scale(wait_ns,
 174                                                     scale_factor,
 175                                                     shift_count);
 176                         } while (timespec_cmp(partial_deadline, now) <= 0);
 177                 }
 178
 179                 if (pred != NULL) {
 180                         int r = pred(wait_state, &partial_deadline);
 181                         if (r != 0) {
 182                                 return r;
 183                         }
 184                 }
 185
 186                 /* Canonicalize deadlines in the far future to NULL. */
 187                 if (sleep(sleep_state, wait_state,
 188                           ((partial_deadline.tv_sec == TIME_MAX)
 189                            ? NULL :  &partial_deadline)) == true) {
 190                         return 0;
 191                 }
 192         }
 193 }
 194
 195 /*
 196  * Loops up to BUSY_LOOP_ITER times, or until ec's counter value
 197  * (including the flag) differs from old_value.
 198  *
 199  * Returns the new value in ec.
 200  */
 201 #define DEF_WAIT_EASY(W)                                                \
 202         static uint##W##_t ck_ec##W##_wait_easy(struct ck_ec##W* ec,    \
 203                                                 const struct ck_ec_ops *ops, \
 204                                                 uint##W##_t expected)   \
 205         {                                                               \
 206                 uint##W##_t current = ck_pr_load_##W(&ec->counter);     \
 207                 size_t n = (ops->busy_loop_iter != 0)                   \
 208                     ? ops->busy_loop_iter                               \
 209                     : DEFAULT_BUSY_LOOP_ITER;                           \
 210                                                                         \
 211                 for (size_t i = 0;                                      \
 212                      i < n && current == expected;                      \
 213                      i++) {                                             \
 214                         ck_pr_stall();                                  \
 215                         current = ck_pr_load_##W(&ec->counter);         \
 216                 }                                                       \
 217                                                                         \
 218                 return current;                                         \
 219         }
 220
 221 DEF_WAIT_EASY(32)
 222 #ifdef CK_F_EC64
 223 DEF_WAIT_EASY(64)
 224 #endif
 225 #undef DEF_WAIT_EASY
 226 /*
 227  * Attempts to upgrade ec->counter from unflagged to flagged.
 228  *
 229  * Returns true if the event count has changed. Otherwise, ec's
 230  * counter word is equal to flagged on return, or has been at some
 231  * time before the return.
 232  */
 233 #define DEF_UPGRADE(W)                                                  \
 234         static bool ck_ec##W##_upgrade(struct ck_ec##W* ec,             \
 235                                        uint##W##_t current,             \
 236                                        uint##W##_t unflagged,           \
 237                                        uint##W##_t flagged)             \
 238         {                                                               \
 239                 uint##W##_t old_word;                                   \
 240                                                                         \
 241                 if (current == flagged) {                               \
 242                         /* Nothing to do, no change. */                 \
 243                         return false;                                   \
 244                 }                                                       \
 245                                                                         \
 246                 if (current != unflagged) {                             \
 247                         /* We have a different counter value! */        \
 248                         return true;                                    \
 249                 }                                                       \
 250                                                                         \
 251                 /*                                                      \
 252                  * Flag the counter value. The CAS only fails if the    \
 253                  * counter is already flagged, or has a new value.      \
 254                  */                                                     \
 255                 return (ck_pr_cas_##W##_value(&ec->counter,             \
 256                                               unflagged, flagged,       \
 257                                               &old_word) == false &&    \
 258                         old_word != flagged);                           \
 259         }
 260
 261 DEF_UPGRADE(32)
 262 #ifdef CK_F_EC64
 263 DEF_UPGRADE(64)
 264 #endif
 265 #undef DEF_UPGRADE
 266
 267 /*
 268  * Blocks until partial_deadline on the ck_ec. Returns true if the
 269  * eventcount's value has changed. If partial_deadline is NULL, wait
 270  * forever.
 271  */
 272 static bool
 273 ck_ec32_wait_slow_once(const void *vstate,
 274     const struct ck_ec_wait_state *wait_state,
 275     const struct timespec *partial_deadline)
 276 {
 277         const struct ck_ec32_slow_path_state *state = vstate;
 278         const struct ck_ec32 *ec = state->ec;
 279         const uint32_t flagged_word = state->flagged_word;
 280
 281         wait_state->ops->wait32(wait_state, &ec->counter,
 282                                 flagged_word, partial_deadline);
 283         return ck_pr_load_32(&ec->counter) != flagged_word;
 284 }
 285
 286 #ifdef CK_F_EC64
 287 static bool
 288 ck_ec64_wait_slow_once(const void *vstate,
 289     const struct ck_ec_wait_state *wait_state,
 290     const struct timespec *partial_deadline)
 291 {
 292         const struct ck_ec64_slow_path_state *state = vstate;
 293         const struct ck_ec64 *ec = state->ec;
 294         const uint64_t flagged_word = state->flagged_word;
 295
 296         /* futex_wait will only compare the low 32 bits. Perform a
 297          * full comparison here to maximise the changes of catching an
 298          * ABA in the low 32 bits.
 299          */
 300         if (ck_pr_load_64(&ec->counter) != flagged_word) {
 301                 return true;
 302         }
 303
 304         wait_state->ops->wait64(wait_state, &ec->counter,
 305                                 flagged_word, partial_deadline);
 306         return ck_pr_load_64(&ec->counter) != flagged_word;
 307 }
 308 #endif
 309
 310 /*
 311  * The full wait logic is a lot of code (> 1KB). Encourage the
 312  * compiler to lay this all out linearly with LIKELY annotations on
 313  * every early exit.
 314  */
 315 #define WAIT_SLOW_BODY(W, ec, ops, pred, data, deadline_ptr,            \
 316                        old_value, unflagged, flagged)                   \
 317         do {                                                            \
 318                 struct ck_ec_wait_state wait_state = {                  \
 319                         .ops = ops,                                     \
 320                         .data = data                                    \
 321                 };                                                      \
 322                 const struct ck_ec##W##_slow_path_state state = {       \
 323                         .ec = ec,                                       \
 324                         .flagged_word = flagged                         \
 325                 };                                                      \
 326                 const struct timespec deadline =                        \
 327                         canonical_deadline(deadline_ptr);               \
 328                                                                         \
 329                 /* Detect infinite past deadlines. */                   \
 330                 if (CK_CC_LIKELY(deadline.tv_sec <= 0)) {               \
 331                         return -1;                                      \
 332                 }                                                       \
 333                                                                         \
 334                 for (;;) {                                              \
 335                         uint##W##_t current;                            \
 336                         int r;                                          \
 337                                                                         \
 338                         current = ck_ec##W##_wait_easy(ec, ops, unflagged); \
 339                                                                         \
 340                         /*                                              \
 341                          * We're about to wait harder (i.e.,            \
 342                          * potentially with futex). Make sure the       \
 343                          * counter word is flagged.                     \
 344                          */                                             \
 345                         if (CK_CC_LIKELY(                               \
 346                                 ck_ec##W##_upgrade(ec, current,         \
 347                                         unflagged, flagged) == true)) { \
 348                                 ck_pr_fence_acquire();                  \
 349                                 return 0;                               \
 350                         }                                               \
 351                                                                         \
 352                         /*                                              \
 353                          * By now, ec->counter == flagged_word (at      \
 354                          * some point in the past). Spin some more to   \
 355                          * heuristically let any in-flight SP inc/add   \
 356                          * to retire. This does not affect              \
 357                          * correctness, but practically eliminates      \
 358                          * lost wake-ups.                               \
 359                          */                                             \
 360                         current = ck_ec##W##_wait_easy(ec, ops, flagged); \
 361                         if (CK_CC_LIKELY(current != flagged_word)) {    \
 362                                 ck_pr_fence_acquire();                  \
 363                                 return 0;                               \
 364                         }                                               \
 365                                                                         \
 366                         r = exponential_backoff(&wait_state,            \
 367                                                 ck_ec##W##_wait_slow_once, \
 368                                                 &state,                 \
 369                                                 pred, &deadline); \
 370                         if (r != 0) {                                   \
 371                                 return r;                               \
 372                         }                                               \
 373                                                                         \
 374                         if (ck_ec##W##_value(ec) != old_value) {        \
 375                                 ck_pr_fence_acquire();                  \
 376                                 return 0;                               \
 377                         }                                               \
 378                                                                         \
 379                         /* Spurious wake-up. Redo the slow path. */     \
 380                 }                                                       \
 381         } while (0)
 382
 383 int
 384 ck_ec32_wait_pred_slow(struct ck_ec32 *ec,
 385     const struct ck_ec_ops *ops,
 386     uint32_t old_value,
 387     int (*pred)(const struct ck_ec_wait_state *state,
 388         struct timespec *deadline),
 389     void *data,
 390     const struct timespec *deadline_ptr)
 391 {
 392         const uint32_t unflagged_word = old_value;
 393         const uint32_t flagged_word = old_value | (1UL << 31);
 394
 395         if (CK_CC_UNLIKELY(ck_ec32_value(ec) != old_value)) {
 396                 return 0;
 397         }
 398
 399         WAIT_SLOW_BODY(32, ec, ops, pred, data, deadline_ptr,
 400                        old_value, unflagged_word, flagged_word);
 401 }
 402
 403 #ifdef CK_F_EC64
 404 int
 405 ck_ec64_wait_pred_slow(struct ck_ec64 *ec,
 406     const struct ck_ec_ops *ops,
 407     uint64_t old_value,
 408     int (*pred)(const struct ck_ec_wait_state *state,
 409         struct timespec *deadline),
 410     void *data,
 411     const struct timespec *deadline_ptr)
 412 {
 413         const uint64_t unflagged_word = old_value << 1;
 414         const uint64_t flagged_word = unflagged_word | 1;
 415
 416         if (CK_CC_UNLIKELY(ck_ec64_value(ec) != old_value)) {
 417                 return 0;
 418         }
 419
 420         WAIT_SLOW_BODY(64, ec, ops, pred, data, deadline_ptr,
 421                        old_value, unflagged_word, flagged_word);
 422 }
 423 #endif
 424
 425 #undef WAIT_SLOW_BODY