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 <bit>
17 : #include <cstdint>
18 :
19 : namespace boost::corosio::detail {
20 :
21 : // A queue entry is a tagged pointer: low bit selects the node kind, the rest
22 : // is the address. We steal a LOW bit (guaranteed zero by alignment), never a
23 : // high bit (which would depend on a fragile platform canonical-address
24 : // assumption). Both node types are >= 8-aligned, so the low 3 bits are free.
25 : static_assert(alignof(scheduler_op) >= 2);
26 : static_assert(alignof(capy::continuation) >= 2);
27 : static_assert(sizeof(void*) == sizeof(std::uintptr_t));
28 : static_assert(sizeof(capy::continuation::reserved) >= sizeof(void*));
29 :
30 : inline constexpr std::uintptr_t ready_cont_bit = 1;
31 :
32 : /// Return true if a queue entry refers to a continuation (vs a scheduler_op).
33 : inline bool
34 HIT 2704613 : ready_is_continuation(std::uintptr_t e) noexcept
35 : {
36 2704613 : return (e & ready_cont_bit) != 0;
37 : }
38 :
39 : /// Recover the scheduler_op from an op-tagged entry.
40 : inline scheduler_op*
41 2534226 : ready_as_op(std::uintptr_t e) noexcept
42 : {
43 2534226 : return std::bit_cast<scheduler_op*>(e & ~ready_cont_bit);
44 : }
45 :
46 : /// Recover the continuation from a continuation-tagged entry.
47 : inline capy::continuation*
48 60370 : ready_as_cont(std::uintptr_t e) noexcept
49 : {
50 60370 : return std::bit_cast<capy::continuation*>(e & ~ready_cont_bit);
51 : }
52 :
53 : /** A unified intrusive FIFO of scheduler_ops and continuations.
54 :
55 : Carries both completion handlers (`scheduler_op`, dispatched via
56 : `(*op)()`) and posted coroutine resumptions (`capy::continuation`,
57 : dispatched via `h.resume()`) in one ordered queue, with no per-entry
58 : allocation. The next-link lives in the node: `scheduler_op::q_next_`
59 : for ops, `capy::continuation::reserved` for continuations.
60 :
61 : @par Thread Safety
62 : Not thread-safe; external synchronization required (the schedulers
63 : hold their dispatch mutex while touching it).
64 : */
65 : class ready_queue
66 : {
67 : std::uintptr_t head_ = 0; // tagged first entry, 0 when empty
68 : std::uintptr_t tail_ = 0; // tagged last entry, 0 when empty
69 :
70 : // Read a node's next-link by value. A continuation's link lives in its
71 : // void* `reserved` slot; bit_cast keeps us from forming a uintptr_t
72 : // lvalue over that void* object (which would violate strict aliasing).
73 : //
74 : // GCC 12/13 false-positive: when inlining proves an entry refers to a
75 : // continuation, -Warray-bounds still diagnoses the untaken scheduler_op
76 : // branch against the smaller object. Fixed in GCC 14.
77 : BOOST_COROSIO_GCC_WARNING_PUSH
78 : BOOST_COROSIO_GCC_WARNING_DISABLE("-Warray-bounds")
79 : static std::uintptr_t
80 648368 : next_of(std::uintptr_t e) noexcept
81 : {
82 648368 : if (ready_is_continuation(e))
83 15095 : return std::bit_cast<std::uintptr_t>(ready_as_cont(e)->reserved);
84 633273 : return ready_as_op(e)->q_next_;
85 : }
86 :
87 : static void
88 1058145 : set_next(std::uintptr_t e, std::uintptr_t nxt) noexcept
89 : {
90 1058145 : if (ready_is_continuation(e))
91 30180 : ready_as_cont(e)->reserved = std::bit_cast<void*>(nxt);
92 : else
93 1027965 : ready_as_op(e)->q_next_ = nxt;
94 1058145 : }
95 : BOOST_COROSIO_GCC_WARNING_POP
96 :
97 : void
98 648368 : push_entry(std::uintptr_t e) noexcept
99 : {
100 648368 : set_next(e, 0);
101 648368 : if (tail_)
102 290955 : set_next(tail_, e);
103 : else
104 357413 : head_ = e;
105 648368 : tail_ = e;
106 648368 : }
107 :
108 : public:
109 2137 : ready_queue() = default;
110 :
111 : ready_queue(ready_queue&& o) noexcept
112 : : head_(o.head_)
113 : , tail_(o.tail_)
114 : {
115 : o.head_ = 0;
116 : o.tail_ = 0;
117 : }
118 :
119 : ready_queue(ready_queue const&) = delete;
120 : ready_queue& operator=(ready_queue const&) = delete;
121 : ready_queue& operator=(ready_queue&&) = delete;
122 :
123 : /// Return true if the queue holds no entries.
124 1874001 : bool empty() const noexcept { return head_ == 0; }
125 :
126 : /// Append a scheduler_op to the back of the queue.
127 633273 : void push(scheduler_op* op) noexcept
128 : {
129 633273 : push_entry(std::bit_cast<std::uintptr_t>(op));
130 633273 : }
131 :
132 : /// Append a continuation to the back of the queue.
133 15095 : void push(capy::continuation& c) noexcept
134 : {
135 15095 : push_entry(std::bit_cast<std::uintptr_t>(&c) | ready_cont_bit);
136 15095 : }
137 :
138 : /// Move all entries of @p other to the back in O(1); @p other is emptied.
139 369790 : void splice(ready_queue& other) noexcept
140 : {
141 369790 : if (other.empty())
142 30920 : return;
143 338870 : if (tail_)
144 118822 : set_next(tail_, other.head_);
145 : else
146 220048 : head_ = other.head_;
147 338870 : tail_ = other.tail_;
148 338870 : other.head_ = 0;
149 338870 : other.tail_ = 0;
150 : }
151 :
152 : /// Remove and return the front entry as a tagged value, or 0 when empty.
153 889304 : std::uintptr_t pop() noexcept
154 : {
155 889304 : auto e = head_;
156 889304 : if (!e)
157 240936 : return 0;
158 648368 : head_ = next_of(e);
159 648368 : if (!head_)
160 238591 : tail_ = 0;
161 648368 : return e;
162 : }
163 : };
164 :
165 : } // namespace boost::corosio::detail
166 :
167 : #endif
|
