include/DetourModKit/detail/profile_ring.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #ifndef DETOURMODKIT_DETAIL_PROFILE_RING_HPP | ||
| 2 | #define DETOURMODKIT_DETAIL_PROFILE_RING_HPP | ||
| 3 | |||
| 4 | /** | ||
| 5 | * @file profile_ring.hpp | ||
| 6 | * @brief The sample slot, the saturating tick conversion, and the ticket publication protocol behind | ||
| 7 | * @ref DetourModKit::Profiler. | ||
| 8 | */ | ||
| 9 | |||
| 10 | #include <atomic> | ||
| 11 | #include <cstddef> | ||
| 12 | #include <cstdint> | ||
| 13 | #include <memory> | ||
| 14 | #include <new> | ||
| 15 | |||
| 16 | namespace DetourModKit::detail | ||
| 17 | { | ||
| 18 | /** | ||
| 19 | * @brief Computes `remainder * multiplier / divisor` exactly, without a wide integer type. | ||
| 20 | * @return The truncated quotient, or 0 when @p divisor is 0. | ||
| 21 | * @pre `remainder < divisor`. A larger numerator wraps, and the result is meaningless. | ||
| 22 | */ | ||
| 23 | [[nodiscard]] inline constexpr std::uint64_t | ||
| 24 | 13 | multiply_fraction(std::uint64_t remainder, std::uint64_t multiplier, std::uint64_t divisor) noexcept | |
| 25 | { | ||
| 26 | 13 | if (remainder == 0 || multiplier == 0 || divisor == 0) | |
| 27 | { | ||
| 28 | 4 | return 0; | |
| 29 | } | ||
| 30 | |||
| 31 | 9 | std::uint64_t quotient = 0; | |
| 32 | 9 | std::uint64_t reduced = 0; | |
| 33 | |||
| 34 | 9 | std::uint64_t bit = std::uint64_t{1} << 63; | |
| 35 | 456 | while ((bit & multiplier) == 0) | |
| 36 | { | ||
| 37 | 447 | bit >>= 1; | |
| 38 | } | ||
| 39 | |||
| 40 | 138 | for (; bit != 0; bit >>= 1) | |
| 41 | { | ||
| 42 | 129 | quotient *= 2; | |
| 43 | 129 | if (reduced >= divisor - reduced) | |
| 44 | { | ||
| 45 | 85 | reduced -= divisor - reduced; | |
| 46 | 85 | ++quotient; | |
| 47 | } | ||
| 48 | else | ||
| 49 | { | ||
| 50 | 44 | reduced += reduced; | |
| 51 | } | ||
| 52 | |||
| 53 | 129 | if ((bit & multiplier) == 0) | |
| 54 | { | ||
| 55 | 83 | continue; | |
| 56 | } | ||
| 57 | 46 | if (reduced >= divisor - remainder) | |
| 58 | { | ||
| 59 | 26 | reduced -= divisor - remainder; | |
| 60 | 26 | ++quotient; | |
| 61 | } | ||
| 62 | else | ||
| 63 | { | ||
| 64 | 20 | reduced += remainder; | |
| 65 | } | ||
| 66 | } | ||
| 67 | 9 | return quotient; | |
| 68 | } | ||
| 69 | |||
| 70 | /** @brief One ring slot: a committed timing sample plus the ticket word that publishes it. */ | ||
| 71 | struct ProfileSample | ||
| 72 | { | ||
| 73 | /** | ||
| 74 | * @brief Publication word `((ticket + 1) << 1) | busy`, where `ticket` is the ring write position that owns | ||
| 75 | * the slot. | ||
| 76 | * @details Zero means that no writer committed the slot. Odd means a write is in flight, so readers skip the | ||
| 77 | * slot. The encoded ticket increases on every reuse, so the same word before and after a payload copy | ||
| 78 | * proves one committed sample. | ||
| 79 | */ | ||
| 80 | std::atomic<std::uint64_t> state{0}; | ||
| 81 | /** | ||
| 82 | * @brief Non-owning sample name. A committed slot can hold null, and export skips such a slot. | ||
| 83 | * @note The name must outlive the process, because the exporter reads it asynchronously. | ||
| 84 | */ | ||
| 85 | const char *name{nullptr}; | ||
| 86 | /// QPC tick count at scope entry. | ||
| 87 | std::int64_t start_ticks{0}; | ||
| 88 | /// Duration in microseconds, saturated at UINT32_MAX (about 71 minutes). | ||
| 89 | std::uint32_t duration_us{0}; | ||
| 90 | /// Win32 thread ID of the thread that recorded the sample. | ||
| 91 | std::uint32_t thread_id{0}; | ||
| 92 | /** @brief Byte count of @ref name, published with it. The exporter never scans for a terminator. */ | ||
| 93 | std::uint32_t name_length{0}; | ||
| 94 | |||
| 95 | 2686994 | ProfileSample() noexcept = default; | |
| 96 | ProfileSample(const ProfileSample &) = delete; | ||
| 97 | ProfileSample &operator=(const ProfileSample &) = delete; | ||
| 98 | ProfileSample(ProfileSample &&) = delete; | ||
| 99 | ProfileSample &operator=(ProfileSample &&) = delete; | ||
| 100 | }; | ||
| 101 | |||
| 102 | /** | ||
| 103 | * @brief Converts a QPC tick interval to microseconds without overflow or undefined behavior. | ||
| 104 | * @param frequency Ticks per second. | ||
| 105 | * @return Microseconds, saturated at UINT32_MAX. The function accepts any tick values. A non-increasing interval or | ||
| 106 | * a non-positive @p frequency returns 0. | ||
| 107 | */ | ||
| 108 | [[nodiscard]] inline std::uint32_t | ||
| 109 | 375488 | ticks_to_microseconds(std::int64_t start_ticks, std::int64_t end_ticks, std::int64_t frequency) noexcept | |
| 110 | { | ||
| 111 | 375488 | constexpr std::uint64_t US_PER_SECOND = 1'000'000; | |
| 112 | 375488 | constexpr std::uint64_t MAX_US = UINT32_MAX; | |
| 113 | |||
| 114 | 375488 | if (frequency <= 0 || end_ticks <= start_ticks) | |
| 115 | { | ||
| 116 | ✗ | return 0; | |
| 117 | } | ||
| 118 | |||
| 119 | 377428 | const std::uint64_t delta = static_cast<std::uint64_t>(end_ticks) - static_cast<std::uint64_t>(start_ticks); | |
| 120 | 377428 | const auto ticks_per_second = static_cast<std::uint64_t>(frequency); | |
| 121 | |||
| 122 | 377428 | const std::uint64_t whole_seconds = delta / ticks_per_second; | |
| 123 | 377428 | if (whole_seconds > MAX_US / US_PER_SECOND) | |
| 124 | { | ||
| 125 | 6 | return static_cast<std::uint32_t>(MAX_US); | |
| 126 | } | ||
| 127 | |||
| 128 | 377422 | const std::uint64_t remainder = delta % ticks_per_second; | |
| 129 | const std::uint64_t fraction_us = (remainder <= UINT64_MAX / US_PER_SECOND) | ||
| 130 | 377422 | ? (remainder * US_PER_SECOND) / ticks_per_second | |
| 131 | 377422 | : multiply_fraction(remainder, US_PER_SECOND, ticks_per_second); | |
| 132 | |||
| 133 | 375231 | const std::uint64_t micros = whole_seconds * US_PER_SECOND + fraction_us; | |
| 134 | 375231 | return static_cast<std::uint32_t>(micros > MAX_US ? MAX_US : micros); | |
| 135 | } | ||
| 136 | |||
| 137 | /** | ||
| 138 | * @brief Fixed-capacity sample ring with lock-free claim/publish and drop-on-collision. | ||
| 139 | * @details @ref claim refuses a slot that another writer still owns or that a later writer already committed, and | ||
| 140 | * counts a drop. See docs/design/events.md "Profiler" for the torn-payload rationale. | ||
| 141 | * | ||
| 142 | * **Thread safety:** `claim` / `publish` are lock-free and callable from any thread. `visit_committed` can run | ||
| 143 | * concurrently with them. | ||
| 144 | */ | ||
| 145 | class ProfileRing | ||
| 146 | { | ||
| 147 | public: | ||
| 148 | /** @brief A slot reservation. */ | ||
| 149 | struct Claim | ||
| 150 | { | ||
| 151 | /// Ring slot index owned by the claim. | ||
| 152 | std::size_t index{0}; | ||
| 153 | /// Global write position represented by the claim. | ||
| 154 | std::uint64_t ticket{0}; | ||
| 155 | /// True only when the slot was reserved successfully. | ||
| 156 | bool owned{false}; | ||
| 157 | }; | ||
| 158 | |||
| 159 | /** | ||
| 160 | * @brief Allocates @p capacity slots, which must be a power of two. | ||
| 161 | * @details Zero, a non-power-of-two, or an allocation failure yields an inert ring that drops every claim. | ||
| 162 | */ | ||
| 163 | 51 | explicit ProfileRing(std::size_t capacity) noexcept | |
| 164 | 51 | { | |
| 165 | 51 | if (capacity == 0 || (capacity & (capacity - 1)) != 0) | |
| 166 | { | ||
| 167 | 2 | return; | |
| 168 | } | ||
| 169 | 2687043 | m_slots.reset(::new (std::nothrow) ProfileSample[capacity]); | |
| 170 | 49 | if (m_slots) | |
| 171 | { | ||
| 172 | 47 | m_capacity = capacity; | |
| 173 | 47 | m_mask = capacity - 1; | |
| 174 | } | ||
| 175 | } | ||
| 176 | |||
| 177 | ProfileRing(const ProfileRing &) = delete; | ||
| 178 | ProfileRing &operator=(const ProfileRing &) = delete; | ||
| 179 | ProfileRing(ProfileRing &&) = delete; | ||
| 180 | ProfileRing &operator=(ProfileRing &&) = delete; | ||
| 181 | 8 | ~ProfileRing() noexcept = default; | |
| 182 | |||
| 183 | /// Takes the next ring position and does not inspect its slot. @ref claim_at completes the reservation. | ||
| 184 | 369141 | [[nodiscard]] std::uint64_t reserve_position() noexcept | |
| 185 | { | ||
| 186 | 738282 | return m_write_pos.fetch_add(1, std::memory_order_relaxed); | |
| 187 | } | ||
| 188 | |||
| 189 | /// Reserves the next slot, or returns a refused claim and counts a drop. | ||
| 190 | 367746 | [[nodiscard]] Claim claim() noexcept { return claim_at(reserve_position()); } | |
| 191 | |||
| 192 | /** | ||
| 193 | * @brief Completes a reservation for a @p position that @ref reserve_position returned. | ||
| 194 | * @pre Pass each reserved position exactly once. This function does not advance the ring. | ||
| 195 | */ | ||
| 196 | 373637 | [[nodiscard]] Claim claim_at(std::uint64_t position) noexcept | |
| 197 | { | ||
| 198 | 373637 | if (m_capacity == 0 || position > MAX_POSITION) | |
| 199 | { | ||
| 200 | 4 | m_dropped.fetch_add(1, std::memory_order_relaxed); | |
| 201 | 4 | return Claim{}; | |
| 202 | } | ||
| 203 | |||
| 204 | 382545 | const auto index = static_cast<std::size_t>(position & m_mask); | |
| 205 | 382545 | std::atomic<std::uint64_t> &state = m_slots[index].state; | |
| 206 | |||
| 207 | // Refuse every collision. An odd word means another writer still owns the slot. A committed ticket above | ||
| 208 | // ours means a later writer published here, and an equal ticket means a repeated claim of this position. | ||
| 209 | 356200 | std::uint64_t observed = state.load(std::memory_order_acquire); | |
| 210 | 353377 | const std::uint64_t encoded_ticket = position + TICKET_OFFSET; | |
| 211 | 353377 | if ((observed & BUSY_BIT) != 0 || (observed != EMPTY_STATE && (observed >> 1) >= encoded_ticket)) | |
| 212 | { | ||
| 213 | 7 | m_dropped.fetch_add(1, std::memory_order_relaxed); | |
| 214 | 7 | return Claim{}; | |
| 215 | } | ||
| 216 | |||
| 217 | 353370 | const std::uint64_t owned_word = state_word(position, true); | |
| 218 | 736976 | if (!state.compare_exchange_strong( | |
| 219 | observed, | ||
| 220 | owned_word, | ||
| 221 | std::memory_order_acq_rel, | ||
| 222 | std::memory_order_relaxed | ||
| 223 | )) | ||
| 224 | { | ||
| 225 | ✗ | m_dropped.fetch_add(1, std::memory_order_relaxed); | |
| 226 | ✗ | return Claim{}; | |
| 227 | } | ||
| 228 | return Claim{ | ||
| 229 | .index = index, | ||
| 230 | .ticket = position, | ||
| 231 | .owned = true, | ||
| 232 | 381105 | }; | |
| 233 | } | ||
| 234 | |||
| 235 | /// Writes the payload into a claimed slot and commits it. A refused claim publishes nothing. | ||
| 236 | 370590 | void publish( | |
| 237 | const Claim &claim, | ||
| 238 | const char *name, | ||
| 239 | std::uint32_t name_length, | ||
| 240 | std::int64_t start_ticks, | ||
| 241 | std::uint32_t duration_us, | ||
| 242 | std::uint32_t thread_id | ||
| 243 | ) noexcept | ||
| 244 | { | ||
| 245 | 370590 | if (!claim.owned) | |
| 246 | { | ||
| 247 | 2 | return; | |
| 248 | } | ||
| 249 | 370588 | ProfileSample &slot = m_slots[claim.index]; | |
| 250 | |||
| 251 | // The exporter reads these fields concurrently, so they go through std::atomic_ref. The release store on | ||
| 252 | // the ticket word below orders them for a reader that accepts the slot. | ||
| 253 | 361917 | std::atomic_ref<const char *>(slot.name).store(name, std::memory_order_relaxed); | |
| 254 | 387889 | std::atomic_ref<std::uint32_t>(slot.name_length).store(name_length, std::memory_order_relaxed); | |
| 255 | 397388 | std::atomic_ref<std::int64_t>(slot.start_ticks).store(start_ticks, std::memory_order_relaxed); | |
| 256 | 394590 | std::atomic_ref<std::uint32_t>(slot.duration_us).store(duration_us, std::memory_order_relaxed); | |
| 257 | 399421 | std::atomic_ref<std::uint32_t>(slot.thread_id).store(thread_id, std::memory_order_relaxed); | |
| 258 | |||
| 259 | 382379 | slot.state.store(state_word(claim.ticket, false), std::memory_order_release); | |
| 260 | } | ||
| 261 | |||
| 262 | /** | ||
| 263 | * @brief Invokes @p visitor for each committed sample in ring traversal order. | ||
| 264 | * @param visitor Called as `visitor(name, name_length, start_ticks, duration_us, thread_id)`. | ||
| 265 | */ | ||
| 266 | 35 | template <typename Visitor> void visit_committed(Visitor &&visitor) const | |
| 267 | { | ||
| 268 | 35 | const std::uint64_t total = m_write_pos.load(std::memory_order_relaxed); | |
| 269 | 35 | const std::uint64_t resident = total < m_capacity ? total : m_capacity; | |
| 270 | 35 | const std::size_t start = total > m_capacity ? static_cast<std::size_t>(total & m_mask) : 0; | |
| 271 | |||
| 272 | 130791 | for (std::uint64_t i = 0; i < resident; ++i) | |
| 273 | { | ||
| 274 | 130756 | ProfileSample &slot = m_slots[(start + static_cast<std::size_t>(i)) & m_mask]; | |
| 275 | |||
| 276 | 130756 | const std::uint64_t before = slot.state.load(std::memory_order_acquire); | |
| 277 | 130756 | if (before == EMPTY_STATE || (before & BUSY_BIT) != 0) | |
| 278 | { | ||
| 279 | 4 | continue; | |
| 280 | } | ||
| 281 | 130752 | const char *const name = std::atomic_ref<const char *>(slot.name).load(std::memory_order_relaxed); | |
| 282 | 130752 | if (name == nullptr) | |
| 283 | { | ||
| 284 | ✗ | continue; | |
| 285 | } | ||
| 286 | const auto name_length = | ||
| 287 | 130752 | std::atomic_ref<std::uint32_t>(slot.name_length).load(std::memory_order_relaxed); | |
| 288 | const auto start_ticks = | ||
| 289 | 130752 | std::atomic_ref<std::int64_t>(slot.start_ticks).load(std::memory_order_relaxed); | |
| 290 | const auto duration_us = | ||
| 291 | 130752 | std::atomic_ref<std::uint32_t>(slot.duration_us).load(std::memory_order_relaxed); | |
| 292 | 130752 | const auto thread_id = std::atomic_ref<std::uint32_t>(slot.thread_id).load(std::memory_order_relaxed); | |
| 293 | |||
| 294 | std::atomic_thread_fence(std::memory_order_acquire); | ||
| 295 | 261504 | if (slot.state.load(std::memory_order_relaxed) != before) | |
| 296 | { | ||
| 297 | 3 | continue; | |
| 298 | } | ||
| 299 | 130749 | visitor(name, name_length, start_ticks, duration_us, thread_id); | |
| 300 | } | ||
| 301 | 35 | } | |
| 302 | |||
| 303 | /// Discards every sample and restarts the ticket sequence. Requires that no claim or visit is in flight. | ||
| 304 | 77 | void reset() noexcept | |
| 305 | { | ||
| 306 | 77 | m_write_pos.store(0, std::memory_order_relaxed); | |
| 307 | 77 | m_dropped.store(0, std::memory_order_relaxed); | |
| 308 | 4784207 | for (std::size_t i = 0; i < m_capacity; ++i) | |
| 309 | { | ||
| 310 | 4784130 | ProfileSample &slot = m_slots[i]; | |
| 311 | 4784130 | std::atomic_ref<const char *>(slot.name).store(nullptr, std::memory_order_relaxed); | |
| 312 | 4784130 | std::atomic_ref<std::uint32_t>(slot.name_length).store(0, std::memory_order_relaxed); | |
| 313 | 4784130 | std::atomic_ref<std::int64_t>(slot.start_ticks).store(0, std::memory_order_relaxed); | |
| 314 | 4784130 | std::atomic_ref<std::uint32_t>(slot.duration_us).store(0, std::memory_order_relaxed); | |
| 315 | 4784130 | std::atomic_ref<std::uint32_t>(slot.thread_id).store(0, std::memory_order_relaxed); | |
| 316 | 4784130 | slot.state.store(0, std::memory_order_relaxed); | |
| 317 | } | ||
| 318 | 77 | } | |
| 319 | |||
| 320 | /// Slot count, or 0 for an inert ring. | ||
| 321 | 15 | [[nodiscard]] std::size_t capacity() const noexcept { return m_capacity; } | |
| 322 | |||
| 323 | /// Claims attempted since construction or the last @ref reset. Refused claims count too. | ||
| 324 | 78 | [[nodiscard]] std::uint64_t claims() const noexcept { return m_write_pos.load(std::memory_order_relaxed); } | |
| 325 | |||
| 326 | /// Claims refused because the slot was owned, already newer, or the ring is inert. | ||
| 327 | 24 | [[nodiscard]] std::uint64_t dropped() const noexcept { return m_dropped.load(std::memory_order_relaxed); } | |
| 328 | |||
| 329 | /// Committed samples still resident. Exact when no claim is in flight. | ||
| 330 | 49 | [[nodiscard]] std::uint64_t resident() const noexcept | |
| 331 | { | ||
| 332 | 49 | const std::uint64_t dropped_now = m_dropped.load(std::memory_order_relaxed); | |
| 333 | 49 | const std::uint64_t claims_now = m_write_pos.load(std::memory_order_relaxed); | |
| 334 | 49 | const std::uint64_t committed = claims_now > dropped_now ? claims_now - dropped_now : 0; | |
| 335 | 49 | return committed < m_capacity ? committed : m_capacity; | |
| 336 | } | ||
| 337 | |||
| 338 | private: | ||
| 339 | static constexpr std::uint64_t BUSY_BIT{1}; | ||
| 340 | static constexpr std::uint64_t TICKET_OFFSET{1}; | ||
| 341 | static constexpr std::uint64_t EMPTY_STATE{0}; | ||
| 342 | static constexpr std::uint64_t MAX_POSITION{(UINT64_MAX >> 1) - 1}; | ||
| 343 | |||
| 344 | 706759 | [[nodiscard]] static constexpr std::uint64_t state_word(std::uint64_t position, bool busy) noexcept | |
| 345 | { | ||
| 346 | 706759 | return ((position + TICKET_OFFSET) << 1) | static_cast<std::uint64_t>(busy); | |
| 347 | } | ||
| 348 | |||
| 349 | static_assert((TICKET_OFFSET << 1) != EMPTY_STATE, "the first committed ticket must differ from an empty slot"); | ||
| 350 | static_assert( | ||
| 351 | std::atomic<std::uint64_t>::is_always_lock_free, | ||
| 352 | "the profile ring requires lock-free 64-bit atomics" | ||
| 353 | ); | ||
| 354 | static_assert( | ||
| 355 | std::atomic_ref<const char *>::is_always_lock_free, | ||
| 356 | "the profile ring requires lock-free pointer publication" | ||
| 357 | ); | ||
| 358 | static_assert( | ||
| 359 | std::atomic_ref<std::int64_t>::is_always_lock_free, | ||
| 360 | "the profile ring requires lock-free 64-bit payload publication" | ||
| 361 | ); | ||
| 362 | static_assert( | ||
| 363 | std::atomic_ref<std::uint32_t>::is_always_lock_free, | ||
| 364 | "the profile ring requires lock-free 32-bit payload publication" | ||
| 365 | ); | ||
| 366 | |||
| 367 | alignas(64) std::atomic<std::uint64_t> m_write_pos{0}; | ||
| 368 | std::atomic<std::uint64_t> m_dropped{0}; | ||
| 369 | std::unique_ptr<ProfileSample[]> m_slots; | ||
| 370 | std::size_t m_capacity{0}; | ||
| 371 | std::size_t m_mask{0}; | ||
| 372 | }; | ||
| 373 | } // namespace DetourModKit::detail | ||
| 374 | |||
| 375 | #endif // DETOURMODKIT_DETAIL_PROFILE_RING_HPP | ||
| 376 |