NVIDIA / NVIDIA/stdexec

Bwos Queue bug

Open
#1,755 5 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
C++
Stars
2.4k
Forks
270
Avg merge
3d 6h
Merged PRs (30d)
39

Description

The issue began when I wanted to use static_thread_pool in a production environment, which is limited to C++17. Therefore, I implemented a minimal version into my environment. Subsequently, I discovered that there was a certain probability of tasks being lost. My first step was to use TSAN to check the issue. TSAN did not report a data race in the x86 environment, but it did report a data race on the Apple M3 machine in the steal_front function and bulk_put function. After investigating, I realized that inappropriate memory ordering was the cause. I modified operations involving thief_block_, tail_, and steal_tail_ to use acquire-release semantics, which resolved the TSAN errors. However, tasks still got lost in the x86 environment. After extensive investigation, I discovered a sequence of timing events that could cause a block's tasks to never be executed.

1.The thief calls advance_steal_index to prepare to enter the next block, named 'a', and pauses between is_stealable and modifying thief_block_.
2.The owner takes over block 'a', finds that the block hasn't been stolen, and successfully takes it over.
3.The thief modifies thief_block_ and successfully enters block 'a'.
4.The thief sees steal_tail == block_size and assumes the block is full, then attempts to call advance_steal_index.
5.The owner pushes a large number of tasks into block 'a', then moves forward to block 'a+2' or farther.
6.The thief finds block a+1 is stealable and successfully enters block 'a+1'.

At this point, the strange issue occurs where the tasks in block 'a' disappear.

I believe the issue can be fixed by using steal_head_ within the steal function to determine Done and Empty, instead of steal_tail_.

https://github.com/NVIDIA/stdexec/pull/1752

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Read the static_thread_pool queue implementation, especially steal_front, bulk_put, advance_steal_index, and steal. Reproduce the reported block-interleaving sequence with TSAN on the affected platforms, then verify whether the proposed steal_head_-based Done and Empty handling prevents lost tasks. Check PR 1752 for work already underway.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
backend
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.