Skip to content

Commit 792e134

Browse files
authored
ci: run the bwos lifo_queue tests on i386 under UBSan (#2328)
* ci: add a 32-bit gcc 14 row No CI job builds for a 32-bit target, so code that assumes 64-bit pointers or a 64-bit std::size_t is never compiled or tested. The new "CPU (gcc 14, Debug, 32-bit)" row builds and tests everything with -m32 (arch: 32). For that row: - g++-14-multilib and gcc-multilib are installed first. gcc-multilib provides /usr/include/asm, which g++-14-multilib only recommends; without it every -m32 compile fails on <linux/errno.h>. - STDEXEC_ENABLE_TBB is off, and -D_GLIBCXX_USE_TBB_PAR_BACKEND=0 keeps libstdc++ from selecting its TBB backend because the image's 64-bit oneTBB headers are present; there is no 32-bit libtbb to link. A test is added that keeps pushing, stealing and popping across several hundred wraps of an 8-block lifo_queue ring. CI failure is expected as no fixes have been made yet. * io_uring: convert pointers through std::uintptr_t, not bit_cast io_uring_context stored pointers in __u64 fields (user_data, addr) with bit_cast<__u64>(pointer) and read them back with bit_cast<__task*>. A bit_cast needs both types to have the same size, so this does not compile where pointers are 4 bytes. The conversions now go through std::uintptr_t, which is the same value on 64-bit targets and widens correctly on 32-bit ones. With this change the 32-bit row builds. * style: clang-format the bwos and io_uring changes * bwos: count the queue-level blocks linearly in 64 bits lifo_queue packed a round into the upper 32 bits of its queue-level block counters (last_block_, start_block_ and the values derived from them) but declared them std::size_t. Where std::size_t is 32 bits wide (i386, wasm32) every shift by 32 on them is undefined: UBSan reports "shift exponent 32 is too large for 32-bit type 'std::size_t'" from steal_front(), the queue refuses pushes as if full (i386) or never terminates (wasm32), and in a reproducer static_thread_pool ran none of 12000 tasks. The counters are now a linear std::uint64_t block counter, counter = round * num_blocks() + index. num_blocks() is a power of two, so the index is counter & mask_ and the round is counter >> round_shift_. The next and previous blocks are counter + 1 and counter - 1, and the round changes exactly when the index wraps, which removes increase_block_counter and decrease_block_counter. The counter is 64 bits wide on every target, so the round keeps 32 bits and wraps in step with the block-level rounds.
1 parent f6cf394 commit 792e134

4 files changed

Lines changed: 128 additions & 74 deletions

File tree

‎.github/workflows/ci.cpu.yml‎

Lines changed: 10 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -43,6 +43,7 @@ jobs:
4343
- { name: "CPU (gcc 12, Release, TSAN)", build: "Release", tag: gcc12-cuda12.9, cxxstd: "20", cxxflags: "-fsanitize=thread" }
4444
- { name: "CPU (gcc 13, Debug)", build: "Debug", tag: gcc13-cuda12.9, cxxstd: "20", cxxflags: "", }
4545
- { name: "CPU (gcc 14, Debug)", build: "Debug", tag: gcc14-cuda12.9, cxxstd: "20", cxxflags: "", }
46+
- { name: "CPU (gcc 14, Debug, 32-bit)", build: "Debug", tag: gcc14-cuda12.9, cxxstd: "20", cxxflags: "-m32 -D_GLIBCXX_USE_TBB_PAR_BACKEND=0", arch: 32 }
4647
- { name: "CPU (gcc 14, Debug, ASAN)", build: "Debug", tag: gcc14-cuda12.9, cxxstd: "20", cxxflags: "-fsanitize=address" }
4748
- { name: "CPU (gcc 14, Debug, TSAN)", build: "Debug", tag: gcc14-cuda12.9, cxxstd: "20", cxxflags: "-fsanitize=thread" }
4849
- { name: "CPU (gcc 14, Release, ASAN)", build: "Release", tag: gcc14-cuda12.9, cxxstd: "20", cxxflags: "-fsanitize=address" }
@@ -186,6 +187,14 @@ jobs:
186187
aws-region: us-east-2
187188
role-duration-seconds: 28800 # 8 hours
188189
role-to-assume: arn:aws:iam::279114543810:role/gha-oidc-NVIDIA
190+
# gcc-multilib provides /usr/include/asm for -m32; g++-14-multilib only
191+
# recommends it.
192+
- if: ${{ matrix.arch == 32 }}
193+
name: Install the 32-bit toolchain
194+
shell: bash
195+
run: |
196+
apt-get update
197+
DEBIAN_FRONTEND=noninteractive apt-get install -y --no-install-recommends g++-14-multilib gcc-multilib
189198
- name: Build and test CPU schedulers
190199
env:
191200
ASAN_OPTIONS: alloc_dealloc_mismatch=0
@@ -229,7 +238,7 @@ jobs:
229238
cmake -S . -B build -GNinja \
230239
-DCMAKE_BUILD_TYPE=${{ matrix.build }} \
231240
-DCMAKE_CXX_FLAGS="${{ matrix.cxxflags }}" \
232-
-DSTDEXEC_ENABLE_TBB:BOOL=${{ !contains(matrix.cxxflags, '-fsanitize') && !contains(matrix.name, 'modules') }} \
241+
-DSTDEXEC_ENABLE_TBB:BOOL=${{ !contains(matrix.cxxflags, '-fsanitize') && !contains(matrix.name, 'modules') && matrix.arch != 32 }} \
233242
-DSTDEXEC_ENABLE_TASKFLOW:BOOL=${{ matrix.name == 'CPU (clang 22, Debug)' }} \
234243
-DSTDEXEC_ENABLE_ASIO:BOOL=TRUE \
235244
-DSTDEXEC_ASIO_IMPLEMENTATION:STRING=boost \

‎include/exec/detail/bwos_lifo_queue.hpp‎

Lines changed: 62 additions & 64 deletions
Original file line numberDiff line numberDiff line change
@@ -41,19 +41,22 @@ import stdexec;
4141
*
4242
* BLOCK COUNTER ENCODING:
4343
* ----------------------
44-
* Block counters (last_block_, start_block_, and internal counters) are 64-bit values with:
45-
* - Bits [63:32]: Round number (32-bit unsigned, wraps on overflow)
46-
* - Bits [31:0]: Block index within the circular block array (masked by mask_)
44+
* The queue-level block counters (last_block_, start_block_) count blocks
45+
* linearly: counter = round * num_blocks() + index. Because num_blocks() is a
46+
* power of two, the index is (counter & mask_) and the round is
47+
* (counter >> round_shift_). Moving to the next or previous block is counter + 1
48+
* or counter - 1; the round changes exactly when the index wraps.
4749
*
48-
* The round number increments each time the index wraps around from mask_ to 0.
49-
* This encoding allows:
50+
* The counters are std::uint64_t regardless of the width of std::size_t, so the
51+
* round always has at least 32 bits and wraps in step with the 32-bit block-level
52+
* rounds below. This encoding allows:
5053
* - Direct comparison of counters to determine relative order
5154
* - ABA problem prevention through round tracking
52-
* - Efficient atomic operations on a single 64-bit value
55+
* - Atomic operations on a single 64-bit value
5356
*
5457
* TWO-LEVEL ROUND SYSTEM:
5558
* ----------------------
56-
* 1. Queue-level rounds: Tracked in last_block_/start_block_ upper 32 bits
59+
* 1. Queue-level rounds: counter >> round_shift_ of last_block_/start_block_
5760
* - Increments when the owner wraps around the circular block array
5861
* - Passed to blocks during reclaim() to initialize block-level rounds
5962
*
@@ -176,31 +179,38 @@ namespace experimental::execution::bwos
176179
std::vector<Tp, Allocator> ring_buffer_;
177180
};
178181

179-
auto advance_get_index(std::size_t& owner, std::size_t owner_index) noexcept -> bool;
180-
auto advance_steal_index(std::size_t& thief) noexcept -> bool;
181-
auto advance_put_index(std::size_t& owner) noexcept -> bool;
182+
// Linear block counter, see BLOCK COUNTER ENCODING. Deliberately not
183+
// std::size_t: the round must keep 32 bits on 32-bit targets.
184+
using block_counter = std::uint64_t;
182185

183-
auto increase_block_counter(std::size_t counter) const noexcept -> std::size_t;
184-
auto decrease_block_counter(std::size_t counter) const noexcept -> std::size_t;
186+
auto advance_get_index(block_counter& owner, std::size_t owner_index) noexcept -> bool;
187+
auto advance_steal_index(block_counter& thief) noexcept -> bool;
188+
auto advance_put_index(block_counter& owner) noexcept -> bool;
185189

186-
// Block counter (round in upper 32 bits, index in lower bits) for the most
190+
auto index_of(block_counter counter) const noexcept -> std::size_t;
191+
auto round_of(block_counter counter) const noexcept -> std::uint32_t;
192+
193+
// Linear block counter (see BLOCK COUNTER ENCODING) for the most
187194
// recent block owned by push/pop operations. Modified only by the owner
188195
// thread.
189-
alignas(hardware_destructive_interference_size) STDEXEC::__std::atomic<std::size_t> last_block_{
190-
0};
196+
alignas(
197+
hardware_destructive_interference_size) STDEXEC::__std::atomic<block_counter> last_block_{0};
191198

192199
// Block counter for the oldest block available for stealing. Modified only
193200
// by the owner thread when it advances to a new block and needs to reclaim
194201
// the block at start_block_ position.
195202
alignas(
196-
hardware_destructive_interference_size) STDEXEC::__std::atomic<std::size_t> start_block_{0};
203+
hardware_destructive_interference_size) STDEXEC::__std::atomic<block_counter> start_block_{0};
197204

198205
// Circular array of blocks. Size is always a power of 2 for efficient
199206
// masking.
200207
std::vector<block_type, allocator_of_t<block_type>> blocks_{};
201208

202209
// Bitmask (blocks_.size() - 1) for extracting block index from counters.
203210
std::size_t mask_{};
211+
212+
// log2(blocks_.size()) for extracting the round from counters.
213+
int round_shift_{};
204214
};
205215

206216
//////////////////////////////////////////////////////////////////////////////
@@ -214,18 +224,19 @@ namespace experimental::execution::bwos
214224
block_type(block_size, allocator),
215225
allocator_of_t<block_type>(allocator))
216226
, mask_(blocks_.size() - 1)
227+
, round_shift_(std::countr_zero(blocks_.size()))
217228
{
218229
blocks_[0].reclaim(0);
219230
}
220231

221232
template <class Tp, class Allocator>
222233
auto lifo_queue<Tp, Allocator>::pop_back() noexcept -> Tp
223234
{
224-
std::size_t owner = last_block_.load(STDEXEC::__std::memory_order_relaxed);
225-
std::size_t owner_index{};
235+
block_counter owner = last_block_.load(STDEXEC::__std::memory_order_relaxed);
236+
std::size_t owner_index{};
226237
do
227238
{
228-
owner_index = owner & mask_;
239+
owner_index = index_of(owner);
229240
block_type& current_block = blocks_[owner_index];
230241
auto [ec, value] = current_block.get();
231242
if (ec == lifo_queue_error_code::success)
@@ -245,11 +256,11 @@ namespace experimental::execution::bwos
245256
template <class Tp, class Allocator>
246257
auto lifo_queue<Tp, Allocator>::steal_front() noexcept -> Tp
247258
{
248-
std::size_t thief = start_block_.load(STDEXEC::__std::memory_order_relaxed);
259+
block_counter thief = start_block_.load(STDEXEC::__std::memory_order_relaxed);
249260
do
250261
{
251-
auto const thief_round = static_cast<std::uint32_t>(thief >> 32);
252-
std::size_t const thief_index = thief & mask_;
262+
auto const thief_round = round_of(thief);
263+
std::size_t const thief_index = index_of(thief);
253264
block_type& block = blocks_[thief_index];
254265
fetch_result result = block.steal(thief_round);
255266
while (result.status != lifo_queue_error_code::done)
@@ -273,10 +284,10 @@ namespace experimental::execution::bwos
273284
template <class Tp, class Allocator>
274285
auto lifo_queue<Tp, Allocator>::push_back(Tp value) noexcept -> bool
275286
{
276-
std::size_t owner = last_block_.load(STDEXEC::__std::memory_order_relaxed);
287+
block_counter owner = last_block_.load(STDEXEC::__std::memory_order_relaxed);
277288
do
278289
{
279-
std::size_t owner_index = owner & mask_;
290+
std::size_t owner_index = index_of(owner);
280291
block_type& current_block = blocks_[owner_index];
281292
auto ec = current_block.put(value);
282293
if (ec == lifo_queue_error_code::success)
@@ -293,10 +304,10 @@ namespace experimental::execution::bwos
293304
template <class Iterator, class Sentinel>
294305
auto lifo_queue<Tp, Allocator>::push_back(Iterator first, Sentinel last) noexcept -> Iterator
295306
{
296-
std::size_t owner = last_block_.load(STDEXEC::__std::memory_order_relaxed);
307+
block_counter owner = last_block_.load(STDEXEC::__std::memory_order_relaxed);
297308
do
298309
{
299-
std::size_t owner_index = owner & mask_;
310+
std::size_t owner_index = index_of(owner);
300311
block_type& current_block = blocks_[owner_index];
301312
first = current_block.bulk_put(first, last);
302313
}
@@ -317,45 +328,32 @@ namespace experimental::execution::bwos
317328
}
318329

319330
template <class Tp, class Allocator>
320-
auto lifo_queue<Tp, Allocator>::increase_block_counter(std::size_t counter) const noexcept
321-
-> std::size_t
331+
auto lifo_queue<Tp, Allocator>::index_of(block_counter counter) const noexcept -> std::size_t
322332
{
323-
std::uint32_t round = static_cast<std::uint32_t>(counter >> 32);
324-
std::size_t index = counter & mask_;
325-
std::size_t next_index = (index + 1) & mask_;
326-
std::uint32_t next_round = round + static_cast<std::uint32_t>(next_index == 0);
327-
return (static_cast<std::size_t>(next_round) << 32) | next_index;
333+
return static_cast<std::size_t>(counter) & mask_;
328334
}
329335

330336
template <class Tp, class Allocator>
331-
auto lifo_queue<Tp, Allocator>::decrease_block_counter(std::size_t counter) const noexcept
332-
-> std::size_t
337+
auto lifo_queue<Tp, Allocator>::round_of(block_counter counter) const noexcept -> std::uint32_t
333338
{
334-
std::uint32_t round = static_cast<std::uint32_t>(counter >> 32);
335-
std::size_t index = counter & mask_;
336-
std::size_t prev_index = static_cast<std::size_t>(static_cast<std::ptrdiff_t>(index) - 1)
337-
& mask_;
338-
std::uint32_t prev_round = round - static_cast<std::uint32_t>(index == 0);
339-
return (static_cast<std::size_t>(prev_round) << 32) | prev_index;
339+
return static_cast<std::uint32_t>(counter >> round_shift_);
340340
}
341341

342342
template <class Tp, class Allocator>
343-
auto
344-
lifo_queue<Tp, Allocator>::advance_get_index(std::size_t& owner, std::size_t owner_index) noexcept
345-
-> bool
343+
auto lifo_queue<Tp, Allocator>::advance_get_index(block_counter& owner,
344+
std::size_t owner_index) noexcept -> bool
346345
{
347-
std::size_t start = start_block_.load(STDEXEC::__std::memory_order_relaxed);
346+
block_counter start = start_block_.load(STDEXEC::__std::memory_order_relaxed);
348347
if (start == owner)
349348
{
350349
// Cannot move backward past start_block_ - queue is empty
351350
return false;
352351
}
353-
// Move to predecessor block, properly decrementing round if wrapping
354-
// backward
355-
std::size_t predecessor = decrease_block_counter(owner);
356-
std::size_t predecessor_index = predecessor & mask_;
357-
block_type& previous_block = blocks_[predecessor_index];
358-
block_type& current_block = blocks_[owner_index];
352+
// Move to predecessor block; the round drops when the index wraps backward
353+
block_counter predecessor = owner - 1;
354+
std::size_t predecessor_index = index_of(predecessor);
355+
block_type& previous_block = blocks_[predecessor_index];
356+
block_type& current_block = blocks_[owner_index];
359357
current_block.reduce_round();
360358
previous_block.takeover();
361359
last_block_.store(predecessor, STDEXEC::__std::memory_order_relaxed);
@@ -364,43 +362,43 @@ namespace experimental::execution::bwos
364362
}
365363

366364
template <class Tp, class Allocator>
367-
auto lifo_queue<Tp, Allocator>::advance_put_index(std::size_t& owner) noexcept -> bool
365+
auto lifo_queue<Tp, Allocator>::advance_put_index(block_counter& owner) noexcept -> bool
368366
{
369-
std::size_t next_index = (owner + 1ul) & mask_;
370-
std::size_t owner_index = owner & mask_;
367+
block_counter next = owner + 1;
368+
std::size_t next_index = index_of(next);
369+
std::size_t owner_index = index_of(owner);
371370
if (next_index == owner_index)
372371
{
373372
// Wrap-around would hit the same block - queue is full
374373
return false;
375374
}
376-
// Calculate next round, incrementing when wrapping to index 0
377-
std::uint32_t next_round = static_cast<std::uint32_t>(owner >> 32)
378-
+ static_cast<std::uint32_t>(next_index == 0);
379-
block_type& next_block = blocks_[next_index];
375+
// The round increments exactly when next_index wraps to 0
376+
std::uint32_t next_round = round_of(next);
377+
block_type& next_block = blocks_[next_index];
380378
if (!next_block.is_writable(next_round))
381379
{
382380
// Block is not yet safe to reuse (thieves still accessing previous generation)
383381
return false;
384382
}
385-
std::size_t first = start_block_.load(STDEXEC::__std::memory_order_relaxed);
386-
std::size_t first_index = first & mask_;
383+
block_counter first = start_block_.load(STDEXEC::__std::memory_order_relaxed);
384+
std::size_t first_index = index_of(first);
387385
if (next_index == first_index)
388386
{
389387
// About to reuse the block at start_block_, so advance start_block_ forward
390-
start_block_.store(increase_block_counter(first), STDEXEC::__std::memory_order_relaxed);
388+
start_block_.store(first + 1, STDEXEC::__std::memory_order_relaxed);
391389
}
392390
block_type& current_block = blocks_[owner_index];
393391
current_block.grant();
394-
owner = (static_cast<std::size_t>(next_round) << 32) | next_index;
392+
owner = next;
395393
next_block.reclaim(next_round);
396394
last_block_.store(owner, STDEXEC::__std::memory_order_relaxed);
397395
return true;
398396
}
399397

400398
template <class Tp, class Allocator>
401-
auto lifo_queue<Tp, Allocator>::advance_steal_index(std::size_t& thief) noexcept -> bool
399+
auto lifo_queue<Tp, Allocator>::advance_steal_index(block_counter& thief) noexcept -> bool
402400
{
403-
thief = increase_block_counter(thief);
401+
++thief;
404402
return thief < last_block_.load(STDEXEC::__std::memory_order_relaxed);
405403
}
406404

‎include/exec/linux/io_uring_context.hpp‎

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -201,7 +201,7 @@ namespace experimental::execution
201201
{
202202
::io_uring_cqe __cqe{};
203203
__cqe.res = -ECANCELED;
204-
__cqe.user_data = bit_cast<__u64>(__op);
204+
__cqe.user_data = static_cast<__u64>(reinterpret_cast<std::uintptr_t>(__op));
205205
__op->__vtable_->__complete_(__op, __cqe);
206206
}
207207

@@ -268,7 +268,7 @@ namespace experimental::execution
268268
}
269269
else
270270
{
271-
__sqe.user_data = bit_cast<__u64>(__op);
271+
__sqe.user_data = static_cast<__u64>(reinterpret_cast<std::uintptr_t>(__op));
272272
__array_[__index] = __index;
273273
++__result.__n_submitted;
274274
++__tail;
@@ -321,7 +321,7 @@ namespace experimental::execution
321321
{
322322
__u32 const __index = __head & __mask_;
323323
::io_uring_cqe const & __cqe = __entries_[__index];
324-
auto* __op = bit_cast<__task*>(__cqe.user_data);
324+
auto* __op = reinterpret_cast<__task*>(static_cast<std::uintptr_t>(__cqe.user_data));
325325
__op->__vtable_->__complete_(__op, __cqe);
326326
++__head;
327327
++__count;
@@ -332,7 +332,7 @@ namespace experimental::execution
332332
{
333333
__task* __op = __ready.pop_front();
334334
::io_uring_cqe __dummy_cqe{};
335-
__dummy_cqe.user_data = bit_cast<__u64>(__op);
335+
__dummy_cqe.user_data = static_cast<__u64>(reinterpret_cast<std::uintptr_t>(__op));
336336
__op->__vtable_->__complete_(__op, __dummy_cqe);
337337
}
338338
return __count;
@@ -362,7 +362,7 @@ namespace experimental::execution
362362
__wakeup_operation& __self = *static_cast<__wakeup_operation*>(__pointer);
363363
__entry = ::io_uring_sqe{};
364364
__entry.fd = __self.__eventfd_;
365-
__entry.addr = bit_cast<__u64>(&__self.__buffer_);
365+
__entry.addr = static_cast<__u64>(reinterpret_cast<std::uintptr_t>(&__self.__buffer_));
366366
# ifdef STDEXEC_HAS_IORING_OP_READ
367367
__entry.opcode = IORING_OP_READ;
368368
__entry.len = sizeof(__self.__buffer_);
@@ -918,7 +918,7 @@ namespace experimental::execution
918918
{
919919
std::memset(&__sqe, 0, sizeof(__sqe));
920920
__sqe.opcode = IORING_OP_ASYNC_CANCEL;
921-
__sqe.addr = bit_cast<__u64>(__op_->__parent_);
921+
__sqe.addr = static_cast<__u64>(reinterpret_cast<std::uintptr_t>(__op_->__parent_));
922922
}
923923
# else
924924
__op_->submit_stop(__sqe);
@@ -1193,14 +1193,14 @@ namespace experimental::execution
11931193
# ifdef STDEXEC_HAS_IO_URING_ASYNC_CANCELLATION
11941194
::io_uring_sqe __sqe_{};
11951195
__sqe_.opcode = IORING_OP_TIMEOUT;
1196-
__sqe_.addr = bit_cast<__u64>(&__duration_);
1196+
__sqe_.addr = static_cast<__u64>(reinterpret_cast<std::uintptr_t>(&__duration_));
11971197
__sqe_.len = 1;
11981198
__sqe = __sqe_;
11991199
# else
12001200
::io_uring_sqe __sqe_{};
12011201
__sqe_.opcode = IORING_OP_READV;
12021202
__sqe_.fd = __timerfd_;
1203-
__sqe_.addr = bit_cast<__u64>(&__iov_);
1203+
__sqe_.addr = static_cast<__u64>(reinterpret_cast<std::uintptr_t>(&__iov_));
12041204
__sqe_.len = 1;
12051205
__sqe = __sqe_;
12061206
# endif

0 commit comments

Comments
 (0)