TLA Line data Source code
1 : //
2 : // Copyright (c) 2026 Steve Gerbino
3 : //
4 : // Distributed under the Boost Software License, Version 1.0. (See accompanying
5 : // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 : //
7 : // Official repository: https://github.com/cppalliance/corosio
8 : //
9 :
10 : #ifndef BOOST_COROSIO_DETAIL_READY_QUEUE_HPP
11 : #define BOOST_COROSIO_DETAIL_READY_QUEUE_HPP
12 :
13 : #include <boost/corosio/detail/scheduler_op.hpp>
14 : #include <boost/capy/continuation.hpp>
15 :
16 : #include <cstdint>
17 :
18 : namespace boost::corosio::detail {
19 :
20 : // A queue entry is a tagged pointer: low bit selects the node kind, the rest
21 : // is the address. We steal a LOW bit (guaranteed zero by alignment), never a
22 : // high bit (which would depend on a fragile platform canonical-address
23 : // assumption). Both node types are >= 8-aligned, so the low 3 bits are free.
24 : static_assert(alignof(scheduler_op) >= 2);
25 : static_assert(alignof(capy::continuation) >= 2);
26 : static_assert(sizeof(void*) == sizeof(std::uintptr_t));
27 : static_assert(sizeof(capy::continuation::reserved) >= sizeof(void*));
28 :
29 : inline constexpr std::uintptr_t ready_cont_bit = 1;
30 :
31 : /// Return true if a queue entry refers to a continuation (vs a scheduler_op).
32 : inline bool
33 HIT 3337851 : ready_is_continuation(void* e) noexcept
34 : {
35 3337851 : return (reinterpret_cast<std::uintptr_t>(e) & ready_cont_bit) != 0;
36 : }
37 :
38 : /// Recover the scheduler_op from an op-tagged entry.
39 : inline scheduler_op*
40 1967542 : ready_as_op(void* e) noexcept
41 : {
42 : // NOLINTNEXTLINE(performance-no-int-to-ptr)
43 : return reinterpret_cast<scheduler_op*>(
44 1967542 : reinterpret_cast<std::uintptr_t>(e) & ~ready_cont_bit);
45 : }
46 :
47 : /// Recover the continuation from a continuation-tagged entry.
48 : inline capy::continuation*
49 1005534 : ready_as_cont(void* e) noexcept
50 : {
51 : // NOLINTNEXTLINE(performance-no-int-to-ptr)
52 : return reinterpret_cast<capy::continuation*>(
53 1005534 : reinterpret_cast<std::uintptr_t>(e) & ~ready_cont_bit);
54 : }
55 :
56 : /** A unified intrusive FIFO of scheduler_ops and continuations.
57 :
58 : Carries both completion handlers (`scheduler_op`, dispatched via
59 : `(*op)()`) and posted coroutine resumptions (`capy::continuation`,
60 : dispatched via `h.resume()`) in one ordered queue, with no per-entry
61 : allocation. The next-link lives in the node: `scheduler_op::q_next_`
62 : for ops, `capy::continuation::reserved` for continuations.
63 :
64 : @par Thread Safety
65 : Not thread-safe; external synchronization required (the schedulers
66 : hold their dispatch mutex while touching it).
67 : */
68 : class ready_queue
69 : {
70 : void* head_ = nullptr; // tagged first entry, nullptr when empty
71 : void* tail_ = nullptr; // tagged last entry, nullptr when empty
72 :
73 : // Read a node's next-link by value. A continuation's link lives in its
74 : // void* `reserved` slot.
75 : //
76 : // GCC 12/13 false-positive: when inlining proves an entry refers to a
77 : // continuation, -Warray-bounds still diagnoses the untaken scheduler_op
78 : // branch against the smaller object. Fixed in GCC 14.
79 : BOOST_COROSIO_GCC_WARNING_PUSH
80 : BOOST_COROSIO_GCC_WARNING_DISABLE("-Warray-bounds")
81 748425 : static void* next_of(void* e) noexcept
82 : {
83 748425 : if (ready_is_continuation(e))
84 251907 : return ready_as_cont(e)->reserved;
85 496518 : return ready_as_op(e)->q_next_;
86 : }
87 :
88 1437358 : static void set_next(void* e, void* nxt) noexcept
89 : {
90 1437358 : if (ready_is_continuation(e))
91 501720 : ready_as_cont(e)->reserved = nxt;
92 : else
93 935638 : ready_as_op(e)->q_next_ = nxt;
94 1437358 : }
95 : BOOST_COROSIO_GCC_WARNING_POP
96 :
97 748425 : void push_entry(void* e) noexcept
98 : {
99 748425 : set_next(e, nullptr);
100 748425 : if (tail_)
101 346951 : set_next(tail_, e);
102 : else
103 401474 : head_ = e;
104 748425 : tail_ = e;
105 748425 : }
106 :
107 : public:
108 17160 : ready_queue() = default;
109 :
110 : ready_queue(ready_queue&& o) noexcept : head_(o.head_), tail_(o.tail_)
111 : {
112 : o.head_ = nullptr;
113 : o.tail_ = nullptr;
114 : }
115 :
116 : ready_queue(ready_queue const&) = delete;
117 : ready_queue& operator=(ready_queue const&) = delete;
118 : ready_queue& operator=(ready_queue&&) = delete;
119 :
120 : /// Return true if the queue holds no entries.
121 2079247 : bool empty() const noexcept
122 : {
123 2079247 : return head_ == nullptr;
124 : }
125 :
126 : /// Append a scheduler_op to the back of the queue.
127 496518 : void push(scheduler_op* op) noexcept
128 : {
129 496518 : push_entry(reinterpret_cast<void*>(op));
130 496518 : }
131 :
132 : /// Append a continuation to the back of the queue.
133 251907 : void push(capy::continuation& c) noexcept
134 : {
135 251907 : push_entry(
136 : // NOLINTNEXTLINE(performance-no-int-to-ptr)
137 : reinterpret_cast<void*>(
138 251907 : reinterpret_cast<std::uintptr_t>(&c) | ready_cont_bit));
139 251907 : }
140 :
141 : /// Move all entries of @p other to the back in O(1); @p other is emptied.
142 626496 : void splice(ready_queue& other) noexcept
143 : {
144 626496 : if (other.empty())
145 262727 : return;
146 363769 : if (tail_)
147 341982 : set_next(tail_, other.head_);
148 : else
149 21787 : head_ = other.head_;
150 363769 : tail_ = other.tail_;
151 363769 : other.head_ = nullptr;
152 363769 : other.tail_ = nullptr;
153 : }
154 :
155 : /// Remove and return the front entry as a tagged value, or nullptr when empty.
156 796137 : void* pop() noexcept
157 : {
158 796137 : auto e = head_;
159 796137 : if (!e)
160 47712 : return nullptr;
161 748425 : head_ = next_of(e);
162 748425 : if (!head_)
163 59492 : tail_ = nullptr;
164 748425 : return e;
165 : }
166 : };
167 :
168 : } // namespace boost::corosio::detail
169 :
170 : #endif
|
