Changeset b2ec5cf in mainline for kernel/generic/include/atomic.h

Timestamp:

2023-04-15T16:47:54Z (13 months ago)

Author:

Jiří Zárevúcky <zarevucky.jiri@…>

Branches:

master, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

169815e

Parents:

dd218ea

git-author:

Jiří Zárevúcky <zarevucky.jiri@…> (2023-04-15 11:54:58)

git-committer:

Jiří Zárevúcky <zarevucky.jiri@…> (2023-04-15 16:47:54)

Message:

Implement atomic_time_stat_t for lockless timekeeping

We keep monotonically increasing temporal statistics in several places.
They are frequently written from the thread that owns them, and rarely
read from other threads in certain syscalls. This new code serves the
purpose of avoiding the need for synchronization on the writer side.
On 64b system, we can simply assume that 64b writes are indivisible,
and relaxed atomic read/writes simply serve to formally prevent C
undefined behavior from data races (they translate to regular memory
reads/writes in assembly).

On 32b systems, we use the same algorithm that's been used for userspace
clock access, using three fields and some memory barriers to maintain
consistency of reads when the upper half changes. Only readers always
synchronize though. For writers, barriers are avoided in the common case
when the upper half remains unchanged.

File:

• kernel/generic/include/atomic.h (modified) (1 diff)

kernel/generic/include/atomic.h

@@ -63 +63 @@
             (new_val), memory_order_relaxed)
 
+#if __64_BITS__
+
+typedef struct {
+        atomic_uint_fast64_t value;
+} atomic_time_stat_t;
+
+#define ATOMIC_TIME_INITIALIZER() (atomic_time_stat_t) {}
+
+static inline void atomic_time_increment(atomic_time_stat_t *time, int a)
+{
+        /*
+         * We require increments to be synchronized with each other, so we
+         * can use ordinary reads and writes instead of a more expensive atomic
+         * read-modify-write operations.
+         */
+        uint64_t v = atomic_load_explicit(&time->value, memory_order_relaxed);
+        atomic_store_explicit(&time->value, v + a, memory_order_relaxed);
+}
+
+static inline uint64_t atomic_time_read(atomic_time_stat_t *time)
+{
+        return atomic_load_explicit(&time->value, memory_order_relaxed);
+}
+
+#else
+
+/**
+ * A monotonically increasing 64b time statistic.
+ * Increments must be synchronized with each other (or limited to a single
+ * thread/CPU), but reads can be performed from any thread.
+ *
+ */
+typedef struct {
+        uint64_t true_value;
+        atomic_uint_fast32_t high1;
+        atomic_uint_fast32_t high2;
+        atomic_uint_fast32_t low;
+} atomic_time_stat_t;
+
+#define ATOMIC_TIME_INITIALIZER() (atomic_time_stat_t) {}
+
+static inline void atomic_time_increment(atomic_time_stat_t *time, int a)
+{
+        /*
+         * On 32b architectures, we can't rely on 64b memory reads/writes being
+         * architecturally atomic, but we also don't want to pay the cost of
+         * emulating atomic reads/writes, so instead we split value in half
+         * and perform some ordering magic to make sure readers always get
+         * consistent value.
+         */
+
+        /* true_value is only used by the writer, so this need not be atomic. */
+        uint64_t val = time->true_value;
+        uint32_t old_high = val >> 32;
+        val += a;
+        uint32_t new_high = val >> 32;
+        time->true_value = val;
+
+        /* Tell GCC that the first branch is far more likely than the second. */
+        if (__builtin_expect(old_high == new_high, 1)) {
+                /* If the high half didn't change, we need not bother with barriers. */
+                atomic_store_explicit(&time->low, (uint32_t) val, memory_order_relaxed);
+        } else {
+                /*
+                 * If both halves changed, extra ordering is necessary.
+                 * The idea is that if reader reads high1 and high2 with the same value,
+                 * it is guaranteed that they read the correct low half for that value.
+                 *
+                 * This is the same sequence that is used by userspace to read clock.
+                 */
+                atomic_store_explicit(&time->high1, new_high, memory_order_relaxed);
+                atomic_store_explicit(&time->low, (uint32_t) val, memory_order_release);
+                atomic_store_explicit(&time->high2, new_high, memory_order_release);
+        }
+}
+
+static inline uint64_t atomic_time_read(atomic_time_stat_t *time)
+{
+        uint32_t high2 = atomic_load_explicit(&time->high2, memory_order_acquire);
+        uint32_t low = atomic_load_explicit(&time->low, memory_order_acquire);
+        uint32_t high1 = atomic_load_explicit(&time->high1, memory_order_relaxed);
+
+        if (high1 != high2)
+                low = 0;
+
+        /* If the values differ, high1 is always the newer value. */
+        return (uint64_t) high1 << 32 | (uint64_t) low;
+}
+
+#endif /* __64_BITS__ */
+
 #endif