. /include/boost/corosio /detail /ready_queue.hpp
100.00% Lines (48/48) 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   15  
16   #include <bit> 16   #include <bit>
17   #include <cstdint> 17   #include <cstdint>
18   18  
19   namespace boost::corosio::detail { 19   namespace boost::corosio::detail {
20   20  
21   // A queue entry is a tagged pointer: low bit selects the node kind, the rest 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 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 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. 24   // assumption). Both node types are >= 8-aligned, so the low 3 bits are free.
25   static_assert(alignof(scheduler_op) >= 2); 25   static_assert(alignof(scheduler_op) >= 2);
26   static_assert(alignof(capy::continuation) >= 2); 26   static_assert(alignof(capy::continuation) >= 2);
27   static_assert(sizeof(void*) == sizeof(std::uintptr_t)); 27   static_assert(sizeof(void*) == sizeof(std::uintptr_t));
28   static_assert(sizeof(capy::continuation::reserved) >= sizeof(void*)); 28   static_assert(sizeof(capy::continuation::reserved) >= sizeof(void*));
29   29  
30   inline constexpr std::uintptr_t ready_cont_bit = 1; 30   inline constexpr std::uintptr_t ready_cont_bit = 1;
31   31  
32   /// Return true if a queue entry refers to a continuation (vs a scheduler_op). 32   /// Return true if a queue entry refers to a continuation (vs a scheduler_op).
33   inline bool 33   inline bool
HITCBC 34   3468798 ready_is_continuation(std::uintptr_t e) noexcept 34   3467393 ready_is_continuation(std::uintptr_t e) noexcept
35   { 35   {
HITCBC 36   3468798 return (e & ready_cont_bit) != 0; 36   3467393 return (e & ready_cont_bit) != 0;
37   } 37   }
38   38  
39   /// Recover the scheduler_op from an op-tagged entry. 39   /// Recover the scheduler_op from an op-tagged entry.
40   inline scheduler_op* 40   inline scheduler_op*
HITCBC 41   3237265 ready_as_op(std::uintptr_t e) noexcept 41   3242902 ready_as_op(std::uintptr_t e) noexcept
42   { 42   {
HITCBC 43   3237265 return std::bit_cast<scheduler_op*>(e & ~ready_cont_bit); 43   3242902 return std::bit_cast<scheduler_op*>(e & ~ready_cont_bit);
44   } 44   }
45   45  
46   /// Recover the continuation from a continuation-tagged entry. 46   /// Recover the continuation from a continuation-tagged entry.
47   inline capy::continuation* 47   inline capy::continuation*
HITCBC 48   95587 ready_as_cont(std::uintptr_t e) noexcept 48   95725 ready_as_cont(std::uintptr_t e) noexcept
49   { 49   {
HITCBC 50   95587 return std::bit_cast<capy::continuation*>(e & ~ready_cont_bit); 50   95725 return std::bit_cast<capy::continuation*>(e & ~ready_cont_bit);
51   } 51   }
52   52  
53   /** A unified intrusive FIFO of scheduler_ops and continuations. 53   /** A unified intrusive FIFO of scheduler_ops and continuations.
54   54  
55   Carries both completion handlers (`scheduler_op`, dispatched via 55   Carries both completion handlers (`scheduler_op`, dispatched via
56   `(*op)()`) and posted coroutine resumptions (`capy::continuation`, 56   `(*op)()`) and posted coroutine resumptions (`capy::continuation`,
57   dispatched via `h.resume()`) in one ordered queue, with no per-entry 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_` 58   allocation. The next-link lives in the node: `scheduler_op::q_next_`
59   for ops, `capy::continuation::reserved` for continuations. 59   for ops, `capy::continuation::reserved` for continuations.
60   60  
61   @par Thread Safety 61   @par Thread Safety
62   Not thread-safe; external synchronization required (the schedulers 62   Not thread-safe; external synchronization required (the schedulers
63   hold their dispatch mutex while touching it). 63   hold their dispatch mutex while touching it).
64   */ 64   */
65   class ready_queue 65   class ready_queue
66   { 66   {
67 - std::uintptr_t head_ = 0; // tagged first entry, 0 when empty 67 + std::uintptr_t head_ = 0; // tagged first entry, 0 when empty
68 - std::uintptr_t tail_ = 0; // tagged last entry, 0 when empty 68 + std::uintptr_t tail_ = 0; // tagged last entry, 0 when empty
69   69  
70   // Read a node's next-link by value. A continuation's link lives in its 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 71   // void* `reserved` slot; bit_cast keeps us from forming a uintptr_t
72   // lvalue over that void* object (which would violate strict aliasing). 72   // lvalue over that void* object (which would violate strict aliasing).
73   // 73   //
74   // GCC 12/13 false-positive: when inlining proves an entry refers to a 74   // GCC 12/13 false-positive: when inlining proves an entry refers to a
75   // continuation, -Warray-bounds still diagnoses the untaken scheduler_op 75   // continuation, -Warray-bounds still diagnoses the untaken scheduler_op
76   // branch against the smaller object. Fixed in GCC 14. 76   // branch against the smaller object. Fixed in GCC 14.
77   BOOST_COROSIO_GCC_WARNING_PUSH 77   BOOST_COROSIO_GCC_WARNING_PUSH
78   BOOST_COROSIO_GCC_WARNING_DISABLE("-Warray-bounds") 78   BOOST_COROSIO_GCC_WARNING_DISABLE("-Warray-bounds")
HITGIC 79 - static std::uintptr_t 79 + 831860 static std::uintptr_t next_of(std::uintptr_t e) noexcept
DCB 80 - 830174 next_of(std::uintptr_t e) noexcept  
81   { 80   {
HITCBC 82   830174 if (ready_is_continuation(e)) 81   831860 if (ready_is_continuation(e))
HITCBC 83   23909 return std::bit_cast<std::uintptr_t>(ready_as_cont(e)->reserved); 82   23940 return std::bit_cast<std::uintptr_t>(ready_as_cont(e)->reserved);
HITCBC 84   806265 return ready_as_op(e)->q_next_; 83   807920 return ready_as_op(e)->q_next_;
85   } 84   }
86   85  
HITGIC 87 - static void 86 + 1348920 static void set_next(std::uintptr_t e, std::uintptr_t nxt) noexcept
DCB 88 - 1350529 set_next(std::uintptr_t e, std::uintptr_t nxt) noexcept  
89   { 87   {
HITCBC 90   1350529 if (ready_is_continuation(e)) 88   1348920 if (ready_is_continuation(e))
HITCBC 91   47769 ready_as_cont(e)->reserved = std::bit_cast<void*>(nxt); 89   47845 ready_as_cont(e)->reserved = std::bit_cast<void*>(nxt);
92   else 90   else
HITCBC 93   1302760 ready_as_op(e)->q_next_ = nxt; 91   1301075 ready_as_op(e)->q_next_ = nxt;
HITCBC 94   1350529 } 92   1348920 }
95   BOOST_COROSIO_GCC_WARNING_POP 93   BOOST_COROSIO_GCC_WARNING_POP
96   94  
HITGIC 97 - void 95 + 831860 void push_entry(std::uintptr_t e) noexcept
DCB 98 - 830174 push_entry(std::uintptr_t e) noexcept  
99   { 96   {
HITCBC 100   830174 set_next(e, 0); 97   831860 set_next(e, 0);
HITCBC 101   830174 if (tail_) 98   831860 if (tail_)
HITCBC 102   382061 set_next(tail_, e); 99   385775 set_next(tail_, e);
103   else 100   else
HITCBC 104   448113 head_ = e; 101   446085 head_ = e;
HITCBC 105   830174 tail_ = e; 102   831860 tail_ = e;
HITCBC 106   830174 } 103   831860 }
107   104  
108   public: 105   public:
HITCBC 109   4092 ready_queue() = default; 106   4100 ready_queue() = default;
110   107  
111 - ready_queue(ready_queue&& o) noexcept 108 + ready_queue(ready_queue&& o) noexcept : head_(o.head_), tail_(o.tail_)
112 - : head_(o.head_)  
113 - , tail_(o.tail_)  
114   { 109   {
115   o.head_ = 0; 110   o.head_ = 0;
116   o.tail_ = 0; 111   o.tail_ = 0;
117   } 112   }
118   113  
119   ready_queue(ready_queue const&) = delete; 114   ready_queue(ready_queue const&) = delete;
120   ready_queue& operator=(ready_queue const&) = delete; 115   ready_queue& operator=(ready_queue const&) = delete;
121   ready_queue& operator=(ready_queue&&) = delete; 116   ready_queue& operator=(ready_queue&&) = delete;
122   117  
123   /// Return true if the queue holds no entries. 118   /// Return true if the queue holds no entries.
HITCBC 124 - 2112338 bool empty() const noexcept { return head_ == 0; } 119 + 2112863 bool empty() const noexcept
  120 + {
HITGNC   121 + 2112863 return head_ == 0;
  122 + }
125   123  
126   /// Append a scheduler_op to the back of the queue. 124   /// Append a scheduler_op to the back of the queue.
HITCBC 127   806265 void push(scheduler_op* op) noexcept 125   807920 void push(scheduler_op* op) noexcept
128   { 126   {
HITCBC 129   806265 push_entry(std::bit_cast<std::uintptr_t>(op)); 127   807920 push_entry(std::bit_cast<std::uintptr_t>(op));
HITCBC 130   806265 } 128   807920 }
131   129  
132   /// Append a continuation to the back of the queue. 130   /// Append a continuation to the back of the queue.
HITCBC 133   23909 void push(capy::continuation& c) noexcept 131   23940 void push(capy::continuation& c) noexcept
134   { 132   {
HITCBC 135   23909 push_entry(std::bit_cast<std::uintptr_t>(&c) | ready_cont_bit); 133   23940 push_entry(std::bit_cast<std::uintptr_t>(&c) | ready_cont_bit);
HITCBC 136   23909 } 134   23940 }
137   135  
138   /// Move all entries of @p other to the back in O(1); @p other is emptied. 136   /// Move all entries of @p other to the back in O(1); @p other is emptied.
HITCBC 139   466686 void splice(ready_queue& other) noexcept 137   463887 void splice(ready_queue& other) noexcept
140   { 138   {
HITCBC 141   466686 if (other.empty()) 139   463887 if (other.empty())
HITCBC 142   35148 return; 140   34292 return;
HITCBC 143   431538 if (tail_) 141   429595 if (tail_)
HITCBC 144   138294 set_next(tail_, other.head_); 142   131285 set_next(tail_, other.head_);
145   else 143   else
HITCBC 146   293244 head_ = other.head_; 144   298310 head_ = other.head_;
HITCBC 147 - 431538 tail_ = other.tail_; 145 + 429595 tail_ = other.tail_;
HITCBC 148   431538 other.head_ = 0; 146   429595 other.head_ = 0;
HITCBC 149   431538 other.tail_ = 0; 147   429595 other.tail_ = 0;
150   } 148   }
151   149  
152   /// Remove and return the front entry as a tagged value, or 0 when empty. 150   /// Remove and return the front entry as a tagged value, or 0 when empty.
HITCBC 153   1154257 std::uintptr_t pop() noexcept 151   1159955 std::uintptr_t pop() noexcept
154   { 152   {
HITCBC 155   1154257 auto e = head_; 153   1159955 auto e = head_;
HITCBC 156   1154257 if (!e) 154   1159955 if (!e)
HITCBC 157   324083 return 0; 155   328095 return 0;
HITCBC 158   830174 head_ = next_of(e); 156   831860 head_ = next_of(e);
HITCBC 159   830174 if (!head_) 157   831860 if (!head_)
HITCBC 160   309819 tail_ = 0; 158   314800 tail_ = 0;
HITCBC 161   830174 return e; 159   831860 return e;
162   } 160   }
163   }; 161   };
164   162  
165   } // namespace boost::corosio::detail 163   } // namespace boost::corosio::detail
166   164  
167   #endif 165   #endif