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