. /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   15  
16   #include <cstdint> 16   #include <cstdint>
17   17  
18   namespace boost::corosio::detail { 18   namespace boost::corosio::detail {
19   19  
20   // 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
21   // 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
22   // high bit (which would depend on a fragile platform canonical-address 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. 23   // assumption). Both node types are >= 8-aligned, so the low 3 bits are free.
24   static_assert(alignof(scheduler_op) >= 2); 24   static_assert(alignof(scheduler_op) >= 2);
25   static_assert(alignof(capy::continuation) >= 2); 25   static_assert(alignof(capy::continuation) >= 2);
26   static_assert(sizeof(void*) == sizeof(std::uintptr_t)); 26   static_assert(sizeof(void*) == sizeof(std::uintptr_t));
27   static_assert(sizeof(capy::continuation::reserved) >= sizeof(void*)); 27   static_assert(sizeof(capy::continuation::reserved) >= sizeof(void*));
28   28  
29   inline constexpr std::uintptr_t ready_cont_bit = 1; 29   inline constexpr std::uintptr_t ready_cont_bit = 1;
30   30  
31   /// 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).
32   inline bool 32   inline bool
HITCBC 33   3497436 ready_is_continuation(void* e) noexcept 33   3157757 ready_is_continuation(void* e) noexcept
34   { 34   {
HITCBC 35   3497436 return (reinterpret_cast<std::uintptr_t>(e) & ready_cont_bit) != 0; 35   3157757 return (reinterpret_cast<std::uintptr_t>(e) & ready_cont_bit) != 0;
36   } 36   }
37   37  
38   /// Recover the scheduler_op from an op-tagged entry. 38   /// Recover the scheduler_op from an op-tagged entry.
39   inline scheduler_op* 39   inline scheduler_op*
HITCBC 40   2201628 ready_as_op(void* e) noexcept 40   1871481 ready_as_op(void* e) noexcept
41   { 41   {
42   // NOLINTNEXTLINE(performance-no-int-to-ptr) 42   // NOLINTNEXTLINE(performance-no-int-to-ptr)
43   return reinterpret_cast<scheduler_op*>( 43   return reinterpret_cast<scheduler_op*>(
HITCBC 44   2201628 reinterpret_cast<std::uintptr_t>(e) & ~ready_cont_bit); 44   1871481 reinterpret_cast<std::uintptr_t>(e) & ~ready_cont_bit);
45   } 45   }
46   46  
47   /// Recover the continuation from a continuation-tagged entry. 47   /// Recover the continuation from a continuation-tagged entry.
48   inline capy::continuation* 48   inline capy::continuation*
HITCBC 49   943582 ready_as_cont(void* e) noexcept 49   943609 ready_as_cont(void* e) noexcept
50   { 50   {
51   // NOLINTNEXTLINE(performance-no-int-to-ptr) 51   // NOLINTNEXTLINE(performance-no-int-to-ptr)
52   return reinterpret_cast<capy::continuation*>( 52   return reinterpret_cast<capy::continuation*>(
HITCBC 53   943582 reinterpret_cast<std::uintptr_t>(e) & ~ready_cont_bit); 53   943609 reinterpret_cast<std::uintptr_t>(e) & ~ready_cont_bit);
54   } 54   }
55   55  
56   /** A unified intrusive FIFO of scheduler_ops and continuations. 56   /** A unified intrusive FIFO of scheduler_ops and continuations.
57   57  
58   Carries both completion handlers (`scheduler_op`, dispatched via 58   Carries both completion handlers (`scheduler_op`, dispatched via
59   `(*op)()`) and posted coroutine resumptions (`capy::continuation`, 59   `(*op)()`) and posted coroutine resumptions (`capy::continuation`,
60   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
61   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_`
62   for ops, `capy::continuation::reserved` for continuations. 62   for ops, `capy::continuation::reserved` for continuations.
63   63  
64   @par Thread Safety 64   @par Thread Safety
65   Not thread-safe; external synchronization required (the schedulers 65   Not thread-safe; external synchronization required (the schedulers
66   hold their dispatch mutex while touching it). 66   hold their dispatch mutex while touching it).
67   */ 67   */
68   class ready_queue 68   class ready_queue
69   { 69   {
70   void* head_ = nullptr; // tagged first entry, nullptr when empty 70   void* head_ = nullptr; // tagged first entry, nullptr when empty
71   void* tail_ = nullptr; // tagged last entry, nullptr when empty 71   void* tail_ = nullptr; // tagged last entry, nullptr when empty
72   72  
73   // 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
74   // void* `reserved` slot. 74   // void* `reserved` slot.
75   // 75   //
76   // 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
77   // continuation, -Warray-bounds still diagnoses the untaken scheduler_op 77   // continuation, -Warray-bounds still diagnoses the untaken scheduler_op
78   // branch against the smaller object. Fixed in GCC 14. 78   // branch against the smaller object. Fixed in GCC 14.
79   BOOST_COROSIO_GCC_WARNING_PUSH 79   BOOST_COROSIO_GCC_WARNING_PUSH
80   BOOST_COROSIO_GCC_WARNING_DISABLE("-Warray-bounds") 80   BOOST_COROSIO_GCC_WARNING_DISABLE("-Warray-bounds")
HITCBC 81   812055 static void* next_of(void* e) noexcept 81   709270 static void* next_of(void* e) noexcept
82   { 82   {
HITCBC 83   812055 if (ready_is_continuation(e)) 83   709270 if (ready_is_continuation(e))
HITCBC 84   236426 return ready_as_cont(e)->reserved; 84   236421 return ready_as_cont(e)->reserved;
HITCBC 85   575629 return ready_as_op(e)->q_next_; 85   472849 return ready_as_op(e)->q_next_;
86   } 86   }
87   87  
HITCBC 88   1482478 static void set_next(void* e, void* nxt) noexcept 88   1362134 static void set_next(void* e, void* nxt) noexcept
89   { 89   {
HITCBC 90   1482478 if (ready_is_continuation(e)) 90   1362134 if (ready_is_continuation(e))
HITCBC 91   470730 ready_as_cont(e)->reserved = nxt; 91   470767 ready_as_cont(e)->reserved = nxt;
92   else 92   else
HITCBC 93   1011748 ready_as_op(e)->q_next_ = nxt; 93   891367 ready_as_op(e)->q_next_ = nxt;
HITCBC 94   1482478 } 94   1362134 }
95   BOOST_COROSIO_GCC_WARNING_POP 95   BOOST_COROSIO_GCC_WARNING_POP
96   96  
HITCBC 97   812055 void push_entry(void* e) noexcept 97   709270 void push_entry(void* e) noexcept
98   { 98   {
HITCBC 99   812055 set_next(e, nullptr); 99   709270 set_next(e, nullptr);
HITCBC 100   812055 if (tail_) 100   709270 if (tail_)
HITCBC 101   344459 set_next(tail_, e); 101   338865 set_next(tail_, e);
102   else 102   else
HITCBC 103   467596 head_ = e; 103   370405 head_ = e;
HITCBC 104   812055 tail_ = e; 104   709270 tail_ = e;
HITCBC 105   812055 } 105   709270 }
106   106  
107   public: 107   public:
HITCBC 108   17648 ready_queue() = default; 108   17533 ready_queue() = default;
109   109  
110   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_)
111   { 111   {
112   o.head_ = nullptr; 112   o.head_ = nullptr;
113   o.tail_ = nullptr; 113   o.tail_ = nullptr;
114   } 114   }
115   115  
116   ready_queue(ready_queue const&) = delete; 116   ready_queue(ready_queue const&) = delete;
117   ready_queue& operator=(ready_queue const&) = delete; 117   ready_queue& operator=(ready_queue const&) = delete;
118   ready_queue& operator=(ready_queue&&) = delete; 118   ready_queue& operator=(ready_queue&&) = delete;
119   119  
120   /// Return true if the queue holds no entries. 120   /// Return true if the queue holds no entries.
HITCBC 121   2267027 bool empty() const noexcept 121   1963027 bool empty() const noexcept
122   { 122   {
HITCBC 123   2267027 return head_ == nullptr; 123   1963027 return head_ == nullptr;
124   } 124   }
125   125  
126   /// Append a scheduler_op to the back of the queue. 126   /// Append a scheduler_op to the back of the queue.
HITCBC 127   575629 void push(scheduler_op* op) noexcept 127   472849 void push(scheduler_op* op) noexcept
128   { 128   {
HITCBC 129   575629 push_entry(reinterpret_cast<void*>(op)); 129   472849 push_entry(reinterpret_cast<void*>(op));
HITCBC 130   575629 } 130   472849 }
131   131  
132   /// Append a continuation to the back of the queue. 132   /// Append a continuation to the back of the queue.
HITCBC 133   236426 void push(capy::continuation& c) noexcept 133   236421 void push(capy::continuation& c) noexcept
134   { 134   {
HITCBC 135   236426 push_entry( 135   236421 push_entry(
136   // NOLINTNEXTLINE(performance-no-int-to-ptr) 136   // NOLINTNEXTLINE(performance-no-int-to-ptr)
137   reinterpret_cast<void*>( 137   reinterpret_cast<void*>(
HITCBC 138   236426 reinterpret_cast<std::uintptr_t>(&c) | ready_cont_bit)); 138   236421 reinterpret_cast<std::uintptr_t>(&c) | ready_cont_bit));
HITCBC 139   236426 } 139   236421 }
140   140  
141   /// 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 142   687819 void splice(ready_queue& other) noexcept 142   589430 void splice(ready_queue& other) noexcept
143   { 143   {
HITCBC 144   687819 if (other.empty()) 144   589430 if (other.empty())
HITCBC 145   338133 return; 145   251481 return;
HITCBC 146   349686 if (tail_) 146   337949 if (tail_)
HITCBC 147   325964 set_next(tail_, other.head_); 147   313999 set_next(tail_, other.head_);
148   else 148   else
HITCBC 149   23722 head_ = other.head_; 149   23950 head_ = other.head_;
HITCBC 150   349686 tail_ = other.tail_; 150   337949 tail_ = other.tail_;
HITCBC 151   349686 other.head_ = nullptr; 151   337949 other.head_ = nullptr;
HITCBC 152   349686 other.tail_ = nullptr; 152   337949 other.tail_ = nullptr;
153   } 153   }
154   154  
155   /// Remove and return the front entry as a tagged value, or nullptr when empty. 155   /// Remove and return the front entry as a tagged value, or nullptr when empty.
HITCBC 156   859703 void* pop() noexcept 156   752712 void* pop() noexcept
157   { 157   {
HITCBC 158   859703 auto e = head_; 158   752712 auto e = head_;
HITCBC 159   859703 if (!e) 159   752712 if (!e)
HITCBC 160   47648 return nullptr; 160   43442 return nullptr;
HITCBC 161   812055 head_ = next_of(e); 161   709270 head_ = next_of(e);
HITCBC 162   812055 if (!head_) 162   709270 if (!head_)
HITCBC 163   141632 tail_ = nullptr; 163   56406 tail_ = nullptr;
HITCBC 164   812055 return e; 164   709270 return e;
165   } 165   }
166   }; 166   };
167   167  
168   } // namespace boost::corosio::detail 168   } // namespace boost::corosio::detail
169   169  
170   #endif 170   #endif