summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--src/ioq.c33
1 files changed, 21 insertions, 12 deletions
diff --git a/src/ioq.c b/src/ioq.c
index f23b62f..74e2587 100644
--- a/src/ioq.c
+++ b/src/ioq.c
@@ -171,8 +171,11 @@ typedef atomic uintptr_t ioq_slot;
/** Someone might be waiting on this slot. */
#define IOQ_BLOCKED ((uintptr_t)1)
+
+/** Bit for IOQ_SKIP. */
+#define IOQ_SKIP_BIT (UINTPTR_WIDTH - 1)
/** The next push(es) should skip this slot. */
-#define IOQ_SKIP ((uintptr_t)1 << (UINTPTR_WIDTH - 1))
+#define IOQ_SKIP ((uintptr_t)1 << IOQ_SKIP_BIT)
/** Amount to add for an additional skip. */
#define IOQ_SKIP_ONE (~IOQ_BLOCKED)
@@ -309,24 +312,30 @@ static void ioq_slot_wake(struct ioqq *ioqq, ioq_slot *slot) {
cond_broadcast(&monitor->cond);
}
+/** Branch-free (slot & IOQ_SKIP) ? ~IOQ_BLOCKED : 0 */
+static uintptr_t ioq_skip_mask(uintptr_t slot) {
+ return -(slot >> IOQ_SKIP_BIT) << 1;
+}
+
/** Push an entry into a slot. */
static bool ioq_slot_push(struct ioqq *ioqq, ioq_slot *slot, struct ioq_ent *ent) {
uintptr_t prev = load(slot, relaxed);
+
while (true) {
- uintptr_t next;
- if (prev & IOQ_SKIP) {
- // skip(1) → empty
- // skip(n) → skip(n - 1)
- next = (prev - IOQ_SKIP_ONE) & ~IOQ_BLOCKED;
- } else if (prev > IOQ_BLOCKED) {
+ size_t skip_mask = ioq_skip_mask(prev);
+ size_t full_mask = ~skip_mask & ~IOQ_BLOCKED;
+ if (prev & full_mask) {
// full(ptr) → wait
prev = ioq_slot_wait(ioqq, slot, prev);
continue;
- } else {
- // empty → full(ptr)
- next = (uintptr_t)ent >> 1;
}
+ // empty → full(ptr)
+ uintptr_t next = ((uintptr_t)ent >> 1) & full_mask;
+ // skip(1) → empty
+ // skip(n) → skip(n - 1)
+ next |= (prev - IOQ_SKIP_ONE) & skip_mask;
+
if (compare_exchange_weak(slot, &prev, next, release, relaxed)) {
break;
}
@@ -349,7 +358,7 @@ static struct ioq_ent *ioq_slot_pop(struct ioqq *ioqq, ioq_slot *slot, bool bloc
uintptr_t next = prev + IOQ_SKIP_ONE;
// skip(n) → ~IOQ_BLOCKED
// full(ptr) → 0
- next &= (next & IOQ_SKIP) ? ~IOQ_BLOCKED : 0;
+ next &= ioq_skip_mask(next);
if (block && next) {
prev = ioq_slot_wait(ioqq, slot, prev);
@@ -368,7 +377,7 @@ static struct ioq_ent *ioq_slot_pop(struct ioqq *ioqq, ioq_slot *slot, bool bloc
// empty → 0
// skip(n) → 0
// full(ptr) → ptr
- prev &= (prev & IOQ_SKIP) ? 0 : ~IOQ_BLOCKED;
+ prev &= ioq_skip_mask(~prev);
return (struct ioq_ent *)(prev << 1);
}