| 0/0 |
2026/11/17 07:44 |
flow |
assessment-kcsan |
4m
Results: map[Benign:true Explanation:### Race Summary
`__sbitmap_get_word` (via `test_and_set_bit_lock`) vs `__sbitmap_get_word` (via
`find_next_zero_bit` / `_find_next_zero_bit`) on `sbitmap_word::word`.
### Synchronization Context
`sbitmap` is designed as a lockless, scalable bitmap allocator (used in `blk-mq`
and SCSI queue budgeting). It avoids global locking by having threads search for
available bits locklessly and claim them using atomic bitops:
- Task 6223 performs an atomic read-modify-write (`test_and_set_bit_lock(nr,
word)`) to claim bit `nr` in `sbitmap_word::word`.
- Task 6224 concurrently performs a plain read in `find_next_zero_bit(word,
depth, hint)` to find a candidate zero bit.
No locks are held during bit discovery, allowing the plain load in
`find_next_zero_bit()` to race with concurrent atomic updates on `word`.
### Final Classification
**BENIGN**
### Reasoning
This is a classic optimistic scan pattern (test-and-test-and-set):
1. **Heuristic Scan with Atomic Re-check:** `find_next_zero_bit()` performs an
optimistic lockless scan across `map->word` to locate a potential candidate zero
bit `nr`. The found bit is immediately re-checked and claimed atomically using
`test_and_set_bit_lock(nr, word)`. If another thread has already set that bit,
`test_and_set_bit_lock()` returns non-zero (failure), causing the loop to
advance `hint = nr + 1` and scan again. Two threads cannot claim the same bit.
2. **No Tearing:** `map->word` is an aligned machine word (`unsigned long`,
located at the start of cacheline-aligned `struct sbitmap_word`). Word-sized
aligned scalar loads and stores are atomic at the hardware level and cannot tear
on any architecture supported by Linux.
3. **No Fused or Hoisted Accesses:** `_find_next_zero_bit()` is an out-of-line
function call in `lib/find_bit.c`. Furthermore, every loop iteration executes
`test_and_set_bit_lock()`, which provides volatile assembly and compiler memory
clobbers, preventing the compiler from caching or hoisting the load out of the
loop.
4. **Ordering & Safety:** `test_and_set_bit_lock()` provides acquire barrier
semantics, properly ordering all accesses to the resource associated with the
acquired bit after the bit acquisition.
### Recommended Annotations
To suppress the benign KCSAN report, `__sbitmap_get_word()` can either read
`*word` with `READ_ONCE()` into a local variable before passing its address to
`find_next_zero_bit()` (matching the approach in commit `6ad0d7e0f4b6` for
`__sbitmap_queue_get_batch()`), or wrap the call with `data_race()`:
```c
nr = data_race(find_next_zero_bit(word, depth, hint));
``` FailureDetectableBy:]
|
| 1/1 |
2026/11/17 07:44 |
action |
kernel-checkouter |
0m
Results: map[KernelSrc:/app/workdir/cache/src/6d0c4d912ac4c28457116fbfe153047fb3052961/data]
|
| 2/1 |
2026/11/17 07:44 |
action |
kernel-builder |
0m
Results: map[KernelObj:/app/workdir/cache/build/4fc9cb093f0faa8b5951a9949e7cc5ff4ce76564/data]
|
| 3/1 |
2026/11/17 07:44 |
action |
codesearch-prepare |
0m
Results: map[Index:codesearch-index]
|
| 4/1 |
2026/11/17 07:44 |
agent |
expert |
4m
Model:
Results: map[Benign:true FailureDetectableBy:]
Instruction: # KCSAN Data Race Severity Analysis Protocol
You are an expert Linux kernel concurrency engineer analyzing a Kernel
Concurrency Sanitizer (KCSAN) data race report to determine if it is
**BENIGN** or **HARMFUL**.
## 1. CLASSIFICATIONS
### **BENIGN (Truly Benign)**
The logic is sound and structurally tolerant to compiler optimizations or
stale reads (or benign tearing on diagnostics/stats).
- **Diagnostics/Stats:** Reads or non-critical updates used only for `/proc`,
`/sys`, counters, timestamps, or `pr_info`.
- **Heuristic Hints:** A "hint" flag or threshold where an old value only
causes a slightly delayed update or a sub-optimal but safe fast-path.
- **Single-Writer Flag Updates:** A single writer updating flags where the
concurrent read is a simple bitwise check (e.g., `flags & MASK`). These are
historically tolerated, assuming neither "Fused Accesses" nor "Ordering
Violations" are relevant in this context.
- **Marked Reloads & Lock Re-checks:** A load feeding into a `cmpxchg()` loop,
checked against a later `READ_ONCE()` reload, or re-verified under a lock
(assuming no "Ordering Violations" on the lockless fast-path).
- **Safe Overwrites & Plain Scalar Accesses:** Writing the same value already
present, or aligned word-sized scalar accesses (e.g., `read (marked)` vs
plain `write`) where observing either the old or new value is safe.
### **HARMFUL (Logic Bug or Marking Required)**
The race causes incorrect behavior due to a synchronization failure or
because missing annotations allow the compiler or CPU to break the algorithm.
**Marking Required for Correctness:**
Do **not** classify a race as HARMFUL merely because an access lacks
`READ_ONCE()`/`WRITE_ONCE()`; you must prove one of these concrete hazards:
- **Fused Accesses:** The compiler hoists a plain load out of a tight
barrier-free spin loop causing a livelock (note: non-inlined calls,
`schedule()`, and locks act as compiler barriers), or reloads a pointer/index
between check and use (TOCTOU).
- **Torn Accesses:** An access larger than word size (e.g., 64-bit on 32-bit
arch, or multi-word structs; aligned `<= sizeof(long)` scalars and pointers
do not tear) is split into multiple non-atomic accesses. Note that
`READ_ONCE()` does **not** guarantee atomicity for 64-bit variables on 32-bit
architectures.
- **Ordering Violations:** The race breaks a required "happens-before"
relationship between dependent memory accesses (requires primitives with
implied or explicit memory barriers).
**Logic Bugs:**
A fundamental synchronization failure. Marking accesses will **not** fix it;
the logic itself must change.
- **Pointers/Lifecycle:** The racing variable is a pointer being dereferenced
or a refcount governing object lifecycle (Use-After-Free risk).
- **Control Flow:** The variable guards a critical section, memory allocation,
or hardware command.
- **Bitfields:** Concurrent writes to different bits in the same word.
Compilers often use non-atomic read-modify-write sequences, meaning a
write to `bit_A` can "clobber" a concurrent write to `bit_B`. However,
do not blindly assume all bitfield accesses are harmful; you must prove
that a concurrent write actually clobbers another in a way that breaks
logic.
- **Complex Structures:** Races on shared lists, trees, or hashmaps.
- **Lossy Updates:** Concurrent plain RMW operations (e.g., `var++`) on
non-diagnostic variables where every increment must be preserved.
- **State Machines:** Races allowing a state machine to bypass transitions
or enter an invalid state.
- **Adjacent Unsynchronized Operations:** Consider races happening at the
same time. For example, if both threads execute `struct->has_elements = true;
list_add(node, &struct->list);`, the race on `has_elements` implies an
adjacent race on `list_head`, which is HARMFUL.
## 2. RESEARCH & ANALYSIS WORKFLOW
1. **Locate the Race:** Find the exact variables and functions in the stack
traces. Do not speculate about hypothetical compiler
behaviors or theoretical dangers (e.g., dismissing something as
"fundamentally unsafe") without tracing the actual data flow to a crash.
2. **Contextualize:** Identify held locks, RCU sections, or interrupt
contexts. Explain why the race is possible (e.g., "Thread A holds `lock`,
but Thread B is a lockless reader").
3. **Data Flow:** Follow the racing variable into its subsequent uses. If
the reader sees a stale or torn value, what branch is taken? Does it lead
to a pointer dereference or `BUG_ON()`? **You must prove harm via this
data flow.**
4. **Failure Sequencing (if HARMFUL):** Construct a two-column execution trace
demonstrating the failure.
*Example format:*
```text
CPU0 CPU1
function_a()
// lockless read
ptr = global_ptr
<PREEMPT>
function_b()
lock(&my_lock)
global_ptr = NULL
unlock(&my_lock)
kfree(ptr)
if (ptr)
*ptr = 1; // -> Use-After-Free!
```
## 3. OUTPUT FORMAT
- **Race Summary:** `[Function A]` vs `[Function B]` on `[Variable/Field]`.
- **Synchronization context:** List held locks and explain the lack of mutual
exclusion.
- **Final Classification:** **BENIGN** or **HARMFUL**.
**If BENIGN:**
- **Reasoning:** Briefly explain why the race is structurally tolerant to stale
reads (or benign tearing on diagnostics/stats).
- **Recommended Annotations:** Suggest appropriate annotations (e.g.,
`READ_ONCE()`, `WRITE_ONCE()`, `data_race()`).
**If HARMFUL:**
- **Failure Reasoning:** Explain and provide a two-column interleaving showing
exactly how the race leads to a failure such as corruption or kernel crash.
- **FailureDetectableBy:** One of:
- `"kasan"`: memory safety bug (use-after-free, out-of-bounds, double-free).
- `"kmsan"`: uninitialized memory read/exposure (e.g. missing publish/subscribe ordering).
- `"any"`: kernel crash/hang (`BUG_ON`, `WARN_ON`, NULL deref, GPF, deadlock).
- `"user"`: user-visible ABI/semantic corruption detectable by userspace without a kernel crash.
- `"none"`: purely internal kernel state/accounting bug without crash or user-visible invariant violation.
- **Recommended Fix (ONLY if fix is trivial):** Suggest a structural fix (e.g.,
"Hold `mapping->i_pages` lock", "Convert to `atomic_t`") or required memory
ordering annotations (e.g., "Wrap in `READ_ONCE()`", "Use
`smp_load_acquire()`").
Don't make assumptions about the kernel source code (it may be different from what you assume it is).
Extensively use the provided code access tools (codesearch-*, git-*, grepper, etc)
to examine the actual source code, and confirm any assumptions.
Prefer calling several tools at the same time to save round-trips.
Use set-results tool to provide results of the analysis.
It must be called exactly once before the final reply.
Ignore results of this tool.
Prompt:
The data race report is:
==================================================================
BUG: KCSAN: data-race in _find_next_zero_bit / sbitmap_find_bit
read-write (marked) to 0xffff8881003e0080 of 8 bytes by task 6223 on cpu 1:
instrument_atomic_read_write include/linux/instrumented.h:113 [inline]
test_and_set_bit_lock include/asm-generic/bitops/instrumented-lock.h:57 [inline]
__sbitmap_get_word lib/sbitmap.c:181 [inline]
sbitmap_find_bit_in_word lib/sbitmap.c:200 [inline]
sbitmap_find_bit+0x240/0x420 lib/sbitmap.c:245
__sbitmap_get lib/sbitmap.c:277 [inline]
sbitmap_get+0xa3/0x1a0 lib/sbitmap.c:291
scsi_dev_queue_ready drivers/scsi/scsi_lib.c:1414 [inline]
scsi_mq_get_budget+0x40/0x280 drivers/scsi/scsi_lib.c:1836
blk_mq_get_dispatch_budget block/blk-mq.h:276 [inline]
__blk_mq_do_dispatch_sched block/blk-mq-sched.c:112 [inline]
blk_mq_do_dispatch_sched block/blk-mq-sched.c:182 [inline]
__blk_mq_sched_dispatch_requests+0x3bf/0xd00 block/blk-mq-sched.c:307
blk_mq_sched_dispatch_requests+0xad/0x160 block/blk-mq-sched.c:329
blk_mq_run_hw_queue+0x163/0x200 block/blk-mq.c:2380
blk_mq_dispatch_list+0x8bc/0xac0 arch/x86/include/asm/bitops.h:-1
blk_mq_flush_plug_list+0x2cd/0x320 block/blk-mq.c:2990
__blk_flush_plug+0x22f/0x2b0 block/blk-core.c:1274
blk_finish_plug+0x47/0x70 block/blk-core.c:1301
swap_cluster_readahead+0x381/0x460 mm/swap_state.c:920
swapin_readahead+0xf5/0x890 mm/swap_state.c:1061
do_swap_page+0x3f6/0x21b0 mm/memory.c:5083
handle_pte_fault mm/memory.c:6668 [inline]
__handle_mm_fault mm/memory.c:6817 [inline]
handle_mm_fault+0xb84/0x3880 mm/memory.c:6984
do_user_addr_fault+0x3ce/0xde0 arch/x86/mm/fault.c:1343
handle_page_fault arch/x86/mm/fault.c:1483 [inline]
exc_page_fault+0x62/0xa0 arch/x86/mm/fault.c:1536
asm_exc_page_fault+0x26/0x30 arch/x86/include/asm/idtentry.h:595
read to 0xffff8881003e0080 of 8 bytes by task 6224 on cpu 0:
_find_next_zero_bit+0x29/0xa0 lib/find_bit.c:215
find_next_zero_bit include/linux/find.h:190 [inline]
__sbitmap_get_word lib/sbitmap.c:167 [inline]
sbitmap_find_bit_in_word lib/sbitmap.c:200 [inline]
sbitmap_find_bit+0x205/0x420 lib/sbitmap.c:245
__sbitmap_get lib/sbitmap.c:277 [inline]
sbitmap_get+0xa3/0x1a0 lib/sbitmap.c:291
scsi_dev_queue_ready drivers/scsi/scsi_lib.c:1414 [inline]
scsi_mq_get_budget+0x40/0x280 drivers/scsi/scsi_lib.c:1836
blk_mq_get_dispatch_budget block/blk-mq.h:276 [inline]
__blk_mq_do_dispatch_sched block/blk-mq-sched.c:112 [inline]
blk_mq_do_dispatch_sched block/blk-mq-sched.c:182 [inline]
__blk_mq_sched_dispatch_requests+0x3bf/0xd00 block/blk-mq-sched.c:307
blk_mq_sched_dispatch_requests+0xad/0x160 block/blk-mq-sched.c:329
blk_mq_run_hw_queue+0x163/0x200 block/blk-mq.c:2380
blk_mq_dispatch_list+0x8bc/0xac0 arch/x86/include/asm/bitops.h:-1
blk_mq_flush_plug_list+0x2cd/0x320 block/blk-mq.c:2990
__blk_flush_plug+0x22f/0x2b0 block/blk-core.c:1274
blk_finish_plug+0x47/0x70 block/blk-core.c:1301
lru_gen_shrink_lruvec mm/vmscan.c:5427 [inline]
shrink_lruvec mm/vmscan.c:6199 [inline]
shrink_node_memcgs mm/vmscan.c:6438 [inline]
shrink_node+0x9f6/0x4600 mm/vmscan.c:6482
shrink_zones mm/vmscan.c:6701 [inline]
do_try_to_free_pages+0x310/0xb80 mm/vmscan.c:6763
try_to_free_mem_cgroup_pages+0x201/0x450 mm/vmscan.c:7044
mem_cgroup_force_empty mm/memcontrol-v1.c:1502 [inline]
mem_cgroup_force_empty_write+0x6b/0x160 mm/memcontrol-v1.c:1518
cgroup_file_write+0x197/0x350 kernel/cgroup/cgroup.c:4426
kernfs_fop_write_iter+0x1d2/0x2e0 fs/kernfs/file.c:345
new_sync_write fs/read_write.c:575 [inline]
vfs_write+0x57a/0x9b0 fs/read_write.c:667
ksys_write+0xdc/0x1a0 fs/read_write.c:719
__do_sys_write fs/read_write.c:730 [inline]
__se_sys_write fs/read_write.c:727 [inline]
__x64_sys_write+0x40/0x50 fs/read_write.c:727
x64_sys_call+0x154e/0x2550 arch/x86/include/generated/asm/syscalls_64.h:2
do_syscall_x64 arch/x86/entry/syscall_64.c:61 [inline]
do_syscall_64+0x11e/0x3a0 arch/x86/entry/syscall_64.c:89
entry_SYSCALL_64_after_hwframe+0x77/0x7f
value changed: 0x00000003ffffffff -> 0x0000000fffffffff
Reported by Kernel Concurrency Sanitizer on:
CPU: 0 UID: 0 PID: 6224 Comm: syz.5.721 Not tainted syzkaller #0 PREEMPT(lazy)
Hardware name: Google Google Compute Engine/Google Compute Engine, BIOS Google 11/06/2026
==================================================================
Reply: ### Race Summary
`__sbitmap_get_word` (via `test_and_set_bit_lock`) vs `__sbitmap_get_word` (via `find_next_zero_bit` / `_find_next_zero_bit`) on `sbitmap_word::word`.
### Synchronization Context
`sbitmap` is designed as a lockless, scalable bitmap allocator (used in `blk-mq` and SCSI queue budgeting). It avoids global locking by having threads search for available bits locklessly and claim them using atomic bitops:
- Task 6223 performs an atomic read-modify-write (`test_and_set_bit_lock(nr, word)`) to claim bit `nr` in `sbitmap_word::word`.
- Task 6224 concurrently performs a plain read in `find_next_zero_bit(word, depth, hint)` to find a candidate zero bit.
No locks are held during bit discovery, allowing the plain load in `find_next_zero_bit()` to race with concurrent atomic updates on `word`.
### Final Classification
**BENIGN**
### Reasoning
This is a classic optimistic scan pattern (test-and-test-and-set):
1. **Heuristic Scan with Atomic Re-check:** `find_next_zero_bit()` performs an optimistic lockless scan across `map->word` to locate a potential candidate zero bit `nr`. The found bit is immediately re-checked and claimed atomically using `test_and_set_bit_lock(nr, word)`. If another thread has already set that bit, `test_and_set_bit_lock()` returns non-zero (failure), causing the loop to advance `hint = nr + 1` and scan again. Two threads cannot claim the same bit.
2. **No Tearing:** `map->word` is an aligned machine word (`unsigned long`, located at the start of cacheline-aligned `struct sbitmap_word`). Word-sized aligned scalar loads and stores are atomic at the hardware level and cannot tear on any architecture supported by Linux.
3. **No Fused or Hoisted Accesses:** `_find_next_zero_bit()` is an out-of-line function call in `lib/find_bit.c`. Furthermore, every loop iteration executes `test_and_set_bit_lock()`, which provides volatile assembly and compiler memory clobbers, preventing the compiler from caching or hoisting the load out of the loop.
4. **Ordering & Safety:** `test_and_set_bit_lock()` provides acquire barrier semantics, properly ordering all accesses to the resource associated with the acquired bit after the bit acquisition.
### Recommended Annotations
To suppress the benign KCSAN report, `__sbitmap_get_word()` can either read `*word` with `READ_ONCE()` into a local variable before passing its address to `find_next_zero_bit()` (matching the approach in commit `6ad0d7e0f4b6` for `__sbitmap_queue_get_batch()`), or wrap the call with `data_race()`:
```c
nr = data_race(find_next_zero_bit(word, depth, hint));
```
|
| 5/2 |
2026/11/17 07:44 |
llm |
expert |
0m
Model:
Tokens:
input: 8080
output: 35
thoughts: 509
Thoughts: **Analyzing the KCSAN Data Race Report**
Okay, so I've got this KCSAN data race report, and it looks like a read-write conflict on an 8-byte region at address `0xffff8881003e0080`. The first access is a read-write from task 6223 on CPU 1, and the second is a read from task 6224 on CPU 0. Crucially, the report notes that the value changed, going from `0x00000003ffffffff` to `0x0000000fffffffff`. This suggests a potential bit manipulation race.
The stack traces point me towards `lib/sbitmap.c`, specifically `sbitmap_find_bit` and functions it calls. Looks like the critical functions are: `sbitmap_find_bit_in_word`, `__sbitmap_get_word`, `__sbitmap_get`, `sbitmap_get`, and related routines in that area.
I need to understand what's happening around that memory location. Based on this callstack, it looks like `sbitmap` is likely involved in managing a bitmap or some kind of sparse array. My gut tells me this race is likely related to the atomic read/write of a bit within the bitmap. Let's focus on the `sbitmap_find_bit` function, it's a good place to start.
I'm going to pull up `lib/sbitmap.c` right away, and I'll focus on lines 160-250 to start. The traces suggest that the issue lies in the locking or atomicity of bit access. I'll read through that section carefully, particularly looking for potential issues with how bits are read and modified in this context.
|
| 6/2 |
2026/11/17 07:44 |
tool |
read-file |
0m
Args: map[File:lib/sbitmap.c FirstLine:150 LineCount:100]
Results: map[Contents: 150: for (i = 0; i < sb->map_nr; i++)
151: sbitmap_deferred_clear(&sb->map[i], 0, 0, 0);
152:
153: sb->depth = depth;
154: sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word);
155: }
156: EXPORT_SYMBOL_GPL(sbitmap_resize);
157:
158: static int __sbitmap_get_word(unsigned long *word, unsigned long depth,
159: unsigned int hint, bool wrap)
160: {
161: int nr;
162:
163: /* don't wrap if starting from 0 */
164: wrap = wrap && hint;
165:
166: while (1) {
167: nr = find_next_zero_bit(word, depth, hint);
168: if (unlikely(nr >= depth)) {
169: /*
170: * We started with an offset, and we didn't reset the
171: * offset to 0 in a failure case, so start from 0 to
172: * exhaust the map.
173: */
174: if (hint && wrap) {
175: hint = 0;
176: continue;
177: }
178: return -1;
179: }
180:
181: if (!test_and_set_bit_lock(nr, word))
182: break;
183:
184: hint = nr + 1;
185: if (hint >= depth - 1)
186: hint = 0;
187: }
188:
189: return nr;
190: }
191:
192: static int sbitmap_find_bit_in_word(struct sbitmap_word *map,
193: unsigned int depth,
194: unsigned int alloc_hint,
195: bool wrap)
196: {
197: int nr;
198:
199: do {
200: nr = __sbitmap_get_word(&map->word, depth,
201: alloc_hint, wrap);
202: if (nr != -1)
203: break;
204: if (!sbitmap_deferred_clear(map, depth, alloc_hint, wrap))
205: break;
206: } while (1);
207:
208: return nr;
209: }
210:
211: static unsigned int __map_depth_with_shallow(const struct sbitmap *sb,
212: int index,
213: unsigned int shallow_depth)
214: {
215: u64 shallow_word_depth;
216: unsigned int word_depth, reminder;
217:
218: word_depth = __map_depth(sb, index);
219: if (shallow_depth >= sb->depth)
220: return word_depth;
221:
222: shallow_word_depth = word_depth * shallow_depth;
223: reminder = do_div(shallow_word_depth, sb->depth);
224:
225: if (reminder >= (index + 1) * word_depth)
226: shallow_word_depth++;
227:
228: return (unsigned int)shallow_word_depth;
229: }
230:
231: static int sbitmap_find_bit(struct sbitmap *sb,
232: unsigned int shallow_depth,
233: unsigned int index,
234: unsigned int alloc_hint,
235: bool wrap)
236: {
237: unsigned int i;
238: int nr = -1;
239:
240: for (i = 0; i < sb->map_nr; i++) {
241: unsigned int depth = __map_depth_with_shallow(sb, index,
242: shallow_depth);
243:
244: if (depth)
245: nr = sbitmap_find_bit_in_word(&sb->map[index], depth,
246: alloc_hint, wrap);
247: if (nr != -1) {
248: nr += index << sb->shift;
249: break;
]
|
| 7/2 |
2026/11/17 07:44 |
llm |
expert |
0m
Model:
Tokens:
input: 10373
output: 34
thoughts: 934
Thoughts: **Analyzing Potential Race Conditions in `__sbitmap_get_word`**
Okay, let's dissect this. I'm looking at the `__sbitmap_get_word` function, specifically how it interacts with the `test_and_set_bit_lock` operation. I see Task 6223 on CPU 1 is calling `test_and_set_bit_lock` on `word`, which I understand is an atomic read-modify-write on a bit within an `unsigned long`. Simultaneously, Task 6224 on CPU 0 is calling `find_next_zero_bit` on the *same* `word`.
The key observation is that `find_next_zero_bit` performs a *plain read* of the `word` data. This immediately raises a red flag in my mind: we have a classic scenario of potential data races. `find_next_zero_bit` isn't using any atomic or marked access methods, while `test_and_set_bit_lock` *is* atomic, which means the latter is ensuring that another process/core doesn't change it.
It looks like the intent is a form of test-and-test-and-set, or perhaps an optimistic scan before atomic test-and-set. Task 6224 uses `find_next_zero_bit` to locate a potential zero bit. It then *conditionally* uses `test_and_set_bit_lock` to atomically set that bit *only if* the bit remains unset.
However, here's where the concern solidifies. If Task 6224 reads a stale value of `word`, say `0x00000003ffffffff`, and Task 6223 has already set bits 38 and 39, Task 6224 still believes bit 38 is zero. Task 6224 will then proceed to `test_and_set_bit_lock(38, word)`. If 6223 has indeed set that bit, `test_and_set_bit_lock` will return 1, and the loop will continue from the next zero bit.
But this raises a critical question: what happens if `find_next_zero_bit` reads a "torn" value of `word`? Although it *shouldn't* occur on x86_64, because `word` is an 8-byte, word-aligned `unsigned long` on x86, it's still good to verify the layout to ensure this won't happen. Let's make sure the definition and structure of `sbitmap_word` make this case impossible!
|
| 8/2 |
2026/11/17 07:44 |
tool |
codesearch-definition-source |
0m
Args: map[ContextFile:lib/sbitmap.c Name:sbitmap_word]
Results: map[SourceCode: 26: /**
27: * struct sbitmap_word - Word in a &struct sbitmap.
28: */
29: struct sbitmap_word {
30: /**
31: * @word: word holding free bits
32: */
33: unsigned long word;
34:
35: /**
36: * @cleared: word holding cleared bits
37: */
38: unsigned long cleared ____cacheline_aligned_in_smp;
39:
40: /**
41: * @swap_lock: serializes simultaneous updates of ->word and ->cleared
42: */
43: raw_spinlock_t swap_lock;
44: } ____cacheline_aligned_in_smp;
SourceFile:include/linux/sbitmap.h]
|
| 9/2 |
2026/11/17 07:44 |
llm |
expert |
0m
Model:
Tokens:
input: 12171
output: 35
thoughts: 122
Thoughts: Okay, here's my breakdown of this structure, thinking through the implications as I go:
**Analyzing the sbitmap_word Structure**
Alright, let's dissect this `sbitmap_word` structure. We've got `sbitmap_word` and within it, the members are defined as: `word` is an `unsigned long`, so that's a standard word-sized integer, naturally aligned, which is exactly what I'd expect. Then we have `cleared`, also an `unsigned long` and aligned, but the name implies it's tracking cleared bits or states, and it's marked as `____cacheline_aligned_in_smp`. That suggests we're dealing with a multi-processor environment and potential cache-line contention. We want to avoid false sharing. Interesting. Finally, we see `swap_lock`, which is a `raw_spinlock_t`. Ah, so we have a lock to protect concurrent access to the `word`. That makes perfect sense given the `cleared` member.
Now, a critical point, a bit I need to check: how does this thing find the next zero bit? This is where efficiency comes in, so it looks like I need to dig into the implementation of `_find_next_zero_bit`. Right, let's head over to `lib/find_bit.c`. This is where the real mechanics are probably defined. This is what's going to tell me if this structure is used well or if there are performance issues here.
|
| 10/2 |
2026/11/17 07:45 |
tool |
read-file |
0m
Args: map[File:lib/find_bit.c FirstLine:205 LineCount:40]
Results: map[Contents: 205: {
206: return FIND_NEXT_BIT(addr1[idx] | addr2[idx], /* nop */, nbits, start);
207: }
208: EXPORT_SYMBOL(_find_next_or_bit);
209: #endif
210:
211: #ifndef find_next_zero_bit
212: unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long nbits,
213: unsigned long start)
214: {
215: return FIND_NEXT_BIT(~addr[idx], /* nop */, nbits, start);
216: }
217: EXPORT_SYMBOL(_find_next_zero_bit);
218: #endif
219:
220: #ifndef find_last_bit
221: unsigned long _find_last_bit(const unsigned long *addr, unsigned long size)
222: {
223: if (size) {
224: unsigned long val = BITMAP_LAST_WORD_MASK(size);
225: unsigned long idx = (size-1) / BITS_PER_LONG;
226:
227: do {
228: val &= addr[idx];
229: if (val)
230: return idx * BITS_PER_LONG + __fls(val);
231:
232: val = ~0ul;
233: } while (idx--);
234: }
235: return size;
236: }
237: EXPORT_SYMBOL(_find_last_bit);
238: #endif
239:
240: unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr,
241: unsigned long size, unsigned long offset)
242: {
243: offset = find_next_bit(addr, size, offset);
244: if (offset == size)
]
|
| 11/2 |
2026/11/17 07:45 |
llm |
expert |
0m
Model:
Tokens:
input: 13231
output: 34
thoughts: 37
Thoughts: Okay, here's my take on those thoughts, tailored for an expert audience:
**Investigating `FIND_NEXT_BIT` Implementation**
Alright, time to get to the heart of this `FIND_NEXT_BIT` business. I need to refresh my memory on the underlying mechanics, so let's zero in on the macro or, more likely, its actual implementation. I suspect it's not a simple one-liner, and efficiency is paramount in these low-level bit manipulation routines. My initial thought is to navigate directly to where the heavy lifting is being done, so `lib/find_bit.c` is the obvious starting point. I'll focus on lines 1-100, which is usually a safe bet for the core function definition and any immediately relevant auxiliary functions or initial setup. This should give me a solid understanding of its algorithmic approach, any bitwise tricks being employed, and the general context in which it operates. Let's see if this reveals the performance profile I'm expecting or if there's room for optimization.
|
| 12/2 |
2026/11/17 07:45 |
tool |
read-file |
0m
Args: map[File:lib/find_bit.c FirstLine:1 LineCount:100]
Results: map[Contents: 1: // SPDX-License-Identifier: GPL-2.0-or-later
2: /* bit search implementation
3: *
4: * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
5: * Written by David Howells (dhowells@redhat.com)
6: *
7: * Copyright (C) 2008 IBM Corporation
8: * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au>
9: * (Inspired by David Howell's find_next_bit implementation)
10: *
11: * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease
12: * size and improve performance, 2015.
13: */
14:
15: #include <linux/bitops.h>
16: #include <linux/bitmap.h>
17: #include <linux/export.h>
18: #include <linux/math.h>
19: #include <linux/minmax.h>
20: #include <linux/swab.h>
21: #include <linux/random.h>
22:
23: /*
24: * Common helper for find_bit() function family
25: * @FETCH: The expression that fetches and pre-processes each word of bitmap(s)
26: * @MUNGE: The expression that post-processes a word containing found bit (may be empty)
27: * @size: The bitmap size in bits
28: */
29: #define FIND_FIRST_BIT(FETCH, MUNGE, size) \
30: ({ \
31: unsigned long idx, val, sz = (size); \
32: \
33: for (idx = 0; idx * BITS_PER_LONG < sz; idx++) { \
34: val = (FETCH); \
35: if (val) { \
36: sz = min(idx * BITS_PER_LONG + __ffs(MUNGE(val)), sz); \
37: break; \
38: } \
39: } \
40: \
41: sz; \
42: })
43:
44: /*
45: * Common helper for find_next_bit() function family
46: * @FETCH: The expression that fetches and pre-processes each word of bitmap(s)
47: * @MUNGE: The expression that post-processes a word containing found bit (may be empty)
48: * @size: The bitmap size in bits
49: * @start: The bitnumber to start searching at
50: */
51: #define FIND_NEXT_BIT(FETCH, MUNGE, size, start) \
52: ({ \
53: unsigned long mask, idx, tmp, sz = (size), __start = (start); \
54: \
55: if (unlikely(__start >= sz)) \
56: goto out; \
57: \
58: mask = MUNGE(BITMAP_FIRST_WORD_MASK(__start)); \
59: idx = __start / BITS_PER_LONG; \
60: \
61: for (tmp = (FETCH) & mask; !tmp; tmp = (FETCH)) { \
62: if ((idx + 1) * BITS_PER_LONG >= sz) \
63: goto out; \
64: idx++; \
65: } \
66: \
67: sz = min(idx * BITS_PER_LONG + __ffs(MUNGE(tmp)), sz); \
68: out: \
69: sz; \
70: })
71:
72: #define FIND_NTH_BIT(FETCH, size, num) \
73: ({ \
74: unsigned long sz = (size), nr = (num), idx, w, tmp = 0; \
75: \
76: for (idx = 0; (idx + 1) * BITS_PER_LONG <= sz; idx++) { \
77: if (idx * BITS_PER_LONG + nr >= sz) \
78: goto out; \
79: \
80: tmp = (FETCH); \
81: w = hweight_long(tmp); \
82: if (w > nr) \
83: goto found; \
84: \
85: nr -= w; \
86: } \
87: \
88: if (sz % BITS_PER_LONG) \
89: tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz); \
90: found: \
91: sz = idx * BITS_PER_LONG + fns(tmp, nr); \
92: out: \
93: sz; \
94: })
95:
96: #ifndef find_first_bit
97: /*
98: * Find the first set bit in a memory region.
99: */
100: unsigned long _find_first_bit(const unsigned long *addr, unsigned long size)
]
|
| 13/2 |
2026/11/17 07:45 |
llm |
expert |
0m
Model:
Tokens:
input: 15007
output: 43
thoughts: 122
Thoughts: **Delving into the `__sbitmap_get_word` Function**
Okay, so I'm in `__sbitmap_get_word`, looking at this `find_next_zero_bit` call. Interesting, it's using a `hint`. I immediately see it's operating on a `word` within the `sbitmap`. But wait a second... isn't each `sbitmap_word` only *one* `unsigned long word`? That seems... straightforward, almost suspiciously so. I need to be sure. Let me confirm that.
Alright, what's this `depth` parameter then? I need to understand that fully in the context of `sbitmap_word`. Time to jump over to `sbitmap.c` to see how the whole thing is set up and used. My immediate thought is to check `sbitmap_init_node` or where `sb->map` is initially configured. I need to fully grok what `depth` actually means here. And, critically, what's `bits_per_word`? I bet that's key to figuring out the overall storage and access strategy of the bitmap. Understanding the relationship between these two is the next step!
|
| 14/2 |
2026/11/17 07:45 |
tool |
grepper |
0m
Args: map[Expression:bits_per_word PathPrefixes:[lib/sbitmap.c include/linux/sbitmap.h]]
Results: map[Output:lib/sbitmap.c=101=int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift,
--
lib/sbitmap.c-104-{
lib/sbitmap.c:105: unsigned int bits_per_word;
lib/sbitmap.c-106- int i;
--
lib/sbitmap.c-110-
lib/sbitmap.c:111: bits_per_word = 1U << shift;
lib/sbitmap.c:112: if (bits_per_word > BITS_PER_LONG)
lib/sbitmap.c-113- return -EINVAL;
--
lib/sbitmap.c-116- sb->depth = depth;
lib/sbitmap.c:117: sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word);
lib/sbitmap.c-118- sb->round_robin = round_robin;
--
lib/sbitmap.c=145=void sbitmap_resize(struct sbitmap *sb, unsigned int depth)
lib/sbitmap.c-146-{
lib/sbitmap.c:147: unsigned int bits_per_word = 1U << sb->shift;
lib/sbitmap.c-148- unsigned int i;
--
lib/sbitmap.c-153- sb->depth = depth;
lib/sbitmap.c:154: sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word);
lib/sbitmap.c-155-}
--
lib/sbitmap.c=380=void sbitmap_show(struct sbitmap *sb, struct seq_file *m)
--
lib/sbitmap.c-384- seq_printf(m, "cleared=%u\n", sbitmap_cleared(sb));
lib/sbitmap.c:385: seq_printf(m, "bits_per_word=%u\n", 1U << sb->shift);
lib/sbitmap.c-386- seq_printf(m, "map_nr=%u\n", sb->map_nr);
]
|
| 15/2 |
2026/11/17 07:45 |
llm |
expert |
0m
Model:
Tokens:
input: 15987
output: 42
thoughts: 973
Thoughts: **Analyzing Potential Race Conditions in sbitmap Allocation**
Okay, let's break this down. I see that `bits_per_word` is limited to `BITS_PER_LONG`, which makes sense given that each `sbitmap_word` in the `sb->map` is backed by an `unsigned long`. This means a single word holds at most `BITS_PER_LONG` bits, nothing surprising there.
Now, focusing on `__sbitmap_get_word`, I'm looking at how it acquires a bit within a word. It uses `find_next_zero_bit` to find a zero bit and then atomically claims it with `test_and_set_bit_lock`. The key is the interaction between these two functions and the fact that `depth` is at most `BITS_PER_LONG`. `find_next_zero_bit` starts at the `hint` and, if `wrap` is set, loops.
Here's where it gets interesting. `find_next_zero_bit` *reads* the `word` using a simple read, not an atomic operation. It uses this read to find a zero bit. If it succeeds, it returns a potential bit. The calling function calls `test_and_set_bit_lock` on the bit to atomically reserve it.
My concern is clear: `find_next_zero_bit` reads `word` *concurrently* with `test_and_set_bit_lock` potentially writing to the same word. In the specific case where `depth` is less than or equal to `BITS_PER_LONG`, `find_next_zero_bit` just reads the *single* `unsigned long` word, potentially while another thread is updating it. This is a classic race condition. Task 6223 could be calling `test_and_set_bit_lock`, while Task 6224 may be calling `find_next_zero_bit`, which reads the word.
`find_next_zero_bit` reads a snapshot of the word, but that snapshot might be stale. The `test_and_set_bit_lock` may modify the data meanwhile!
Therefore, `find_next_zero_bit` is subject to a *read-write* race condition! The implications are significant: a potential double allocation of the same bit if the read in `find_next_zero_bit` precedes the atomic write in `test_and_set_bit_lock`.
I'm now going to dig into the git log and look for any mentions of `__sbitmap_get_word` or `sbitmap` to see if there have been prior discussions, commits, or KCSAN annotations related to this. There is clearly a critical concurrency bug that I think needs to be addressed.
|
| 16/2 |
2026/11/17 07:45 |
tool |
git-log |
0m
Args: map[CodeRegexp:find_next_zero_bit.*test_and_set PathPrefix:lib/sbitmap.c]
Results:
|
| 17/2 |
2026/11/17 07:45 |
llm |
expert |
0m
Model:
Tokens:
input: 17614
output: 36
thoughts: 34
Thoughts: Okay, here's my attempt at summarizing those thoughts from a first-person, expert perspective, focusing on the mental process:
**Diving into Potential Concurrency Issues in `lib/sbitmap.c`**
Right, let's get down to it. I need to figure out what's going on with the `lib/sbitmap.c` code. My gut tells me there's potentially some interesting, possibly concurrency-related, issues lurking within. My immediate thought is to start with a deep dive into the commit history. I want to see how the code has evolved, and if anyone's been touching things that might introduce or expose data races, or even if there's been any explicit work being done to address them.
Specifically, I'm thinking about searching the commit history for a few key terms. The first thing that comes to mind is the function `find_next_zero_bit`. It's a fundamental bit manipulation function and is often a good place to start when investigating concurrency bugs involving shared data structures. A naive implementation could definitely have race conditions.
Beyond that, I'm going to explicitly look for terms like "data-race" or "KCSAN." These are like signal flares for me. The presence of those terms in commit messages would immediately flag past attempts to diagnose or mitigate potential concurrency problems. Seeing those mentions will provide a great context on how to get started. I need to be efficient and these keywords will help get me to the right places fast.
|
| 18/2 |
2026/11/17 07:45 |
tool |
git-log |
0m
Args: map[CodeRegexp:find_next_zero_bit PathPrefix:lib/sbitmap.c]
Results: map[Output:678418c6128f sbitmap: add sbitmap_find_bit to remove repeat code in __sbitmap_get/__sbitmap_get_shallow
27fae429acee sbitmap: don't loop for find_next_zero_bit() for !round_robin
c05e66733788 sbitmap: add sbitmap_get_shallow() operation
88459642cba4 blk-mq: abstract tag allocation out into sbitmap library
]
|
| 19/2 |
2026/11/17 07:45 |
llm |
expert |
0m
Model:
Tokens:
input: 18131
output: 34
thoughts: 25
Thoughts: Okay, here's my take on those thoughts, tailored for an expert audience:
**Investigating Potential Race Conditions in `lib/sbitmap.c`**
Alright, time to get to work. My initial hunch is that there might be some race conditions lurking within `lib/sbitmap.c`. Given its role in managing bitmaps, it's a prime target for concurrency issues. To get started, I'm going to search through the commit messages for that specific file. My search terms are pretty targeted: "race" and "kcsan". "Race" is obvious; it's a direct indicator of the problem I'm looking for. "kcsan" (Kernel Concurrency Sanitizer) is more of a signal. If the developers were running kcsan and documenting issues, that will give me a head start. This should give me some context about previous race conditions that were investigated, their resolution (or lack thereof), and maybe reveal some areas I need to focus on. I'm expecting this initial search to provide a good roadmap.
|
| 20/2 |
2026/11/17 07:45 |
tool |
git-log |
0m
Args: map[MessageRegexps:[kcsan|race] PathPrefix:lib/sbitmap.c]
Results:
|
| 21/2 |
2026/11/17 07:45 |
llm |
expert |
0m
Model:
Tokens:
input: 18424
output: 23
thoughts: 15
Thoughts: Okay, here's my take on those thoughts, tailored for an expert audience, presented in the first person:
**Diving into Kernel Sbitmap Usage**
Alright, let's get down to brass tacks. I'm thinking I need to refresh my memory, or perhaps, explore some new aspects of the kernel's implementation around "sbitmap." It's been a while since I last did a deep dive on this specific data structure, and my spidey-sense is telling me it's time to re-familiarize myself.
My initial approach is to immediately jump into action and see examples of how sbitmap is being used in the current kernel code base. Searching commit messages is always a good starting point to gauge how it's being used, how it's being changed, and possibly learn about recent bug fixes or optimizations. Using the phrase "sbitmap" in commit messages will provide context on exactly where it's employed, allowing me to start constructing an understanding. The code is the ultimate documentation, so finding real-world examples in commits will be a good starting point for learning what I need to. I'm hoping I'll quickly come up with an overview of what the changes have been and where its use is prominent.
|
| 22/2 |
2026/11/17 07:46 |
tool |
git-log |
0m
Args: map[MessageRegexps:[sbitmap.*kcsan]]
Results:
|
| 23/2 |
2026/11/17 07:46 |
llm |
expert |
0m
Model:
Tokens:
input: 18735
output: 27
thoughts: 26
Thoughts: Here's my summary, as though I'm thinking through this process:
**Investigating Recent Changes in `lib/sbitmap.c`**
Okay, so I need to understand the recent history of `lib/sbitmap.c`. The most direct approach, as always, is to dive straight into the Git log. But I want the *full* picture. I don't want any message filtering or sanitization; I need to see *everything* that's gone on with this file lately. Let's fire up `git log` and specify the file path, `lib/sbitmap.c`. And definitely no message restrictions this time, gotta check the full commit history and understand the rationale behind each revision.
|
| 24/2 |
2026/11/17 07:46 |
tool |
git-log |
0m
Args: map[Count:20 PathPrefix:lib/sbitmap.c]
Results: map[Output:45fa9f97e652 lib/sbitmap: make sbitmap_get_shallow() internal
42e6c6ce03fd lib/sbitmap: convert shallow_depth from one word to the whole sbitmap
65f666c62036 lib/sbitmap: define swap_lock as raw_spinlock_t
72d04bdcf3f7 sbitmap: fix io hung due to race on sbitmap_word::cleared
6ad0d7e0f4b6 sbitmap: use READ_ONCE to access map->word
5c7fa5c8ad79 sbitmap: remove stale comment in sbq_calc_wake_batch
106397376c03 sbitmap: fix batching wakeup
b5fcf7871acb sbitmap: correct wake_batch recalculation to avoid potential IO hung
678418c6128f sbitmap: add sbitmap_find_bit to remove repeat code in __sbitmap_get/__sbitmap_get_shallow
08470a98a7d7 sbitmap: rewrite sbitmap_find_bit_in_index to reduce repeat code
903e86f3a64d sbitmap: remove redundant check in __sbitmap_queue_get_batch
f1591a8bb3e0 sbitmap: remove unnecessary calculation of alloc_hint in __sbitmap_get_shallow
8032bf1233a7 treewide: use get_random_u32_below() instead of deprecated function
26edb30dd1c0 sbitmap: Try each queue to wake up at least one waiter
976570b4ecd3 sbitmap: Advance the queue index before waking up a queue
4f8126bb2308 sbitmap: Use single per-bitmap counting to wake up queued tags
8b3ccbc1f1f9 treewide: use prandom_u32_max() when possible, part 2
81895a65ec63 treewide: use prandom_u32_max() when possible, part 1
30514bd2dd4e sbitmap: fix lockup while swapping
4acb83417cad sbitmap: fix batched wait_cnt accounting
]
|
| 25/2 |
2026/11/17 07:46 |
llm |
expert |
0m
Model:
Tokens:
input: 19496
output: 26
thoughts: 45
Thoughts: Here's my analysis of the commit, presented as a first-person account:
**Analyzing a Key SBitmap Optimization**
Okay, let's dive in. Commit `6ad0d7e0f4b6` β that's the one titled "sbitmap: use READ_ONCE to access map->word." I remember this patch, it was a subtle, but potentially crucial, optimization. I should take a look at it using `git show` to be sure. My initial thought is that `READ_ONCE` is being introduced here to improve the memory model interactions related to accessing the `map->word` member. I want to confirm whether this is about preventing compiler optimizations that might reorder reads/writes across multiple threads, or perhaps ensuring that the CPU's load/store unit is not re-ordering the loads/stores across multiple CPUs. The use of `READ_ONCE` here suggests a concern for cache coherency and visibility of updates across different CPUs that might be manipulating the sbitmap data structure concurrently. Understanding the exact context and reasoning is important. Iβll make sure I pay close attention to the lock, if any, that protects the `map->word` or related data, to understand the interactions further. This commit might be related to atomicity as well, or at least a way to provide a baseline for atomic operation. It is important to know if it's necessary in this case or if it is just a "defensive" coding practice.
|
| 26/2 |
2026/11/17 07:46 |
tool |
git-show |
0m
Args:
Results: map[Output:commit 6ad0d7e0f4b68f87a98ea2b239123b7d865df86b
Author: linke li <lilinke99@qq.com>
Date: Fri Apr 26 18:34:44 2024 +0800
sbitmap: use READ_ONCE to access map->word
In __sbitmap_queue_get_batch(), map->word is read several times, and
update atomically using atomic_long_try_cmpxchg(). But the first two read
of map->word is not protected.
This patch moves the statement val = READ_ONCE(map->word) forward,
eliminating unprotected accesses to map->word within the function.
It is aimed at reducing the number of benign races reported by KCSAN in
order to focus future debugging effort on harmful races.
Signed-off-by: linke li <lilinke99@qq.com>
Link: https://lore.kernel.org/r/tencent_0B517C25E519D3D002194E8445E86C04AD0A@qq.com
Signed-off-by: Jens Axboe <axboe@kernel.dk>
diff --git a/lib/sbitmap.c b/lib/sbitmap.c
index 92c6b1fd8989..1e453f825c05 100644
--- a/lib/sbitmap.c
+++ b/lib/sbitmap.c
@@ -494,18 +494,18 @@ unsigned long __sbitmap_queue_get_batch(struct sbitmap_queue *sbq, int nr_tags,
struct sbitmap_word *map = &sb->map[index];
unsigned long get_mask;
unsigned int map_depth = __map_depth(sb, index);
+ unsigned long val;
sbitmap_deferred_clear(map);
- if (map->word == (1UL << (map_depth - 1)) - 1)
+ val = READ_ONCE(map->word);
+ if (val == (1UL << (map_depth - 1)) - 1)
goto next;
- nr = find_first_zero_bit(&map->word, map_depth);
+ nr = find_first_zero_bit(&val, map_depth);
if (nr + nr_tags <= map_depth) {
atomic_long_t *ptr = (atomic_long_t *) &map->word;
- unsigned long val;
get_mask = ((1UL << nr_tags) - 1) << nr;
- val = READ_ONCE(map->word);
while (!atomic_long_try_cmpxchg(ptr, &val,
get_mask | val))
;
]
|
| 27/2 |
2026/11/17 07:46 |
llm |
expert |
0m
Model:
Tokens:
input: 20620
output: 34
thoughts: 2434
Thoughts: **KCSAN Data Race Analysis: `__sbitmap_get_word` and `find_next_zero_bit`**
Okay, so I see this commit aims to reduce benign KCSAN reports, focusing on harmful races. That's good, but my radar is up around `__sbitmap_get_word`. Let's see what's going on in that function.
The code itself looks straightforward: find a zero bit, atomically set it. The `while` loop with `find_next_zero_bit` and `test_and_set_bit_lock` is the key. The function finds a zero bit (or tries), and then atomically claims it.
My first thought: Why does `__sbitmap_get_word` pass `&map->word` to `find_next_zero_bit`? Itβs because `find_next_zero_bit` expects `const unsigned long *addr`, an array pointer. It reads from that address. The backtrace shows `_find_next_zero_bit` being called, so the depth isn't a compile time constant.
Now, KCSAN flagged a data race on `0xffff8881003e0080`. One thread is reading and one is writing: `test_and_set_bit_lock` does the atomic write, and `find_next_zero_bit` does the read. It's a plain load, no `READ_ONCE` or atomic semantics. This is the crux of the issue. The former is marked, the latter isn't; KCSAN triggers on this.
But, is this a benign or harmful race? That's what I have to determine.
Let's carefully examine the possible hazards. First, "Marked Reloads & Lock Re-checks". I see a clear match here: `find_next_zero_bit` is loading the value that `test_and_set_bit_lock` might modify. The flow is: `find_next_zero_bit` finds an index, `test_and_set_bit_lock` claims that bit (atomically), if the bit was 0, it is claimed and exits. If it wasn't, the while loop finds another. If all bits are set, and we're wrapping, we try again. If there are no free bits, `-1` is returned.
If `nr` is not set by a concurrent access between the `find_next_zero_bit` load and the `test_and_set_bit_lock` execution, then the bit is locked.
If the bit *is* concurrently set, the loop just picks another index. If the other thread does a `test_and_set_bit_lock` on the *same* bit, the loop will detect the concurrent write because the check fails, the if condition fails, the hint will be updated, and the loop continues, so no big deal (but it's still a data race). If bits are concurrently modified to be non-zero, the loop will find another available bit.
Next, I need to check for compiler hazards. Can the compiler reorder or optimize the load? Could it hoist the `find_next_zero_bit` call? No. `test_and_set_bit_lock` is an atomic RMW and is a compiler barrier because of its "memory" clobber, so the read cannot be moved out of the loop.
Torn accesses? The `word` is an aligned `unsigned long` on all supported architectures. 8 bytes on 64-bit, 4 bytes on 32-bit. It's a word-sized read, so it can't tear.
Finally, out-of-bounds reads in `find_next_zero_bit`? `word` points to `map->word`. `depth` dictates the boundary, but `depth` is `__map_depth_with_shallow(...)`. So it can't read past the end of the word. `__map_depth_with_shallow` can be derived.
So, this data race IS benign: The concurrent access, detected by KCSAN is fine. The plain read doesn't lead to incorrect results or any memory corruption. The worst that can happen is the loop taking an extra iteration. We will report it to KCSAN, so that the team will know there is a potential race, but it does not lead to harmful corruption.
|
| 28/2 |
2026/11/17 07:46 |
tool |
codesearch-definition-source |
0m
Args: map[ContextFile:lib/sbitmap.c Name:__map_depth]
Results: map[SourceCode: 173: /* sbitmap internal helper */
174: static inline unsigned int __map_depth(const struct sbitmap *sb, int index)
175: {
176: if (index == sb->map_nr - 1)
177: return sb->depth - (index << sb->shift);
178: return 1U << sb->shift;
179: }
SourceFile:include/linux/sbitmap.h]
|
| 29/2 |
2026/11/17 07:46 |
llm |
expert |
0m
Model:
Tokens:
input: 24190
output: 29
thoughts: 1254
Thoughts: **Analyzing the Sbitmap Concurrency Issue**
Okay, let me think this through. I see the core problem lies in concurrent access to the `sbitmap` data structure, specifically during bit manipulation. It looks like `1U << sb->shift` gives us `bits_per_word`, which has been pre-checked to be within the bounds of `BITS_PER_LONG`, so the `depth` parameter is guaranteed to be less than or equal to `BITS_PER_LONG`.
Let's break down the `find_next_zero_bit` function. The size check (`sz = depth <= BITS_PER_LONG`) is straightforward. The index initialization `idx = 0` (derived from `hint < depth`) is also understandable. The key section is this loop: `for (tmp = (FETCH) & mask; !tmp; tmp = (FETCH))`. If `idx` is 0, the body runs once. If `!tmp` is true the loop terminates immediately, and the `idx` value is never incremented beyond 0. It seems the code is only reading `word[0]`.
But could `find_next_zero_bit` return a bit number greater than or equal to `depth`? Looking at the `sz` calculation, if no zero bit is found, it returns `sz`, which can be equal to `depth`. In `__sbitmap_get_word`, a return value >= `depth` triggers a retry with a wrapped hint, or a `-1` error. If `nr < depth`, `test_and_set_bit_lock` is called, and, since `nr < depth <= BITS_PER_LONG`, this will access a single bit within `word[0]`.
Now, the report mentions bit 38 vs bit 39. `0x00000003ffffffff` has 38 bits set, and `0x0000000fffffffff` has 40 bits set, so bits 38 and 39 are the key bits. So, Task 6223 is calling `test_and_set_bit_lock` (setting a bit), and Task 6224 is reading the `word` concurrently in `find_next_zero_bit`.
The critical question now becomes: can that read return an inconsistent value? On x86, and most modern CPUs, 8-byte aligned memory accesses are atomic at the hardware level due to the cache coherence protocol (MESI). Thus, reads should either see the value before `test_and_set_bit_lock` or after the lock, but not some intermediate state. Even if the compiler were to somehow introduce reordering, the compiled function in `lib/find_bit.c` is doing an aligned 8-byte load, so it *should* be atomic.
If Task 6224 sees the value *before* the bit is set (e.g., bit 38 is zero), it might choose that bit. Then it executes `test_and_set_bit_lock(38, word)`. Since Task 6223 already set bit 38, the lock will return 1, indicating that the bit was already set. Task 6224 then advances the `hint` and re-reads.
If Task 6224 sees the value *after* the bit is set, it will detect that bit 38 is one and proceed to find another zero bit. But what happens if multiple threads call `test_and_set_bit_lock` on the same bit? The `test_and_set_bit_lock` function provides atomicity. Only *one* caller will see the original zero value, succeed, and return 0. The others will see a 1 and fail. Thus, contention on *the same* bit is properly serialized.
Now, what about concurrent execution of `test_and_set_bit_lock` on *different* bits within the same word? The Linux kernel's atomic bit operations are fully atomic and serialized by hardware cache coherence. The writes will not clobber each other.
Okay, I need to consider clearing bits as well. How are bits cleared in sbitmap? I should search for functions that modify the `word` or `cleared` data within the `sbitmap` structures. This seems like it should be the key to understanding the full concurrency picture.
|
| 30/2 |
2026/11/17 07:47 |
tool |
grepper |
0m
Args: map[Expression:->word PathPrefixes:[lib/sbitmap.c]]
Results: map[Output:lib/sbitmap.c=63=static inline bool sbitmap_deferred_clear(struct sbitmap_word *map,
--
lib/sbitmap.c-84-
lib/sbitmap.c:85: return (READ_ONCE(map->word) & word_mask) != word_mask;
lib/sbitmap.c-86- }
--
lib/sbitmap.c-95- */
lib/sbitmap.c:96: atomic_long_andnot(mask, (atomic_long_t *)&map->word);
lib/sbitmap.c:97: BUILD_BUG_ON(sizeof(atomic_long_t) != sizeof(map->word));
lib/sbitmap.c-98- return true;
--
lib/sbitmap.c=192=static int sbitmap_find_bit_in_word(struct sbitmap_word *map,
--
lib/sbitmap.c-199- do {
lib/sbitmap.c:200: nr = __sbitmap_get_word(&map->word, depth,
lib/sbitmap.c-201- alloc_hint, wrap);
--
lib/sbitmap.c=353=static unsigned int __sbitmap_weight(const struct sbitmap *sb, bool set)
--
lib/sbitmap.c-361- if (set)
lib/sbitmap.c:362: weight += bitmap_weight(&word->word, word_depth);
lib/sbitmap.c-363- else
--
lib/sbitmap.c=515=unsigned long __sbitmap_queue_get_batch(struct sbitmap_queue *sbq, int nr_tags,
--
lib/sbitmap.c-537- sbitmap_deferred_clear(map, 0, 0, 0);
lib/sbitmap.c:538: val = READ_ONCE(map->word);
lib/sbitmap.c-539- if (val == (1UL << (map_depth - 1)) - 1)
--
lib/sbitmap.c-543- if (nr + nr_tags <= map_depth) {
lib/sbitmap.c:544: atomic_long_t *ptr = (atomic_long_t *) &map->word;
lib/sbitmap.c-545-
]
|
| 31/2 |
2026/11/17 07:47 |
llm |
expert |
0m
Model:
Tokens:
input: 27027
output: 33
thoughts: 30
Thoughts: Okay, let's dive into this. Here's my take on those lines of code:
**Analyzing `sbitmap_deferred_clear` in `lib/sbitmap.c`**
Alright, I need to get a handle on this `sbitmap_deferred_clear` function. Time to focus on lines 60 through 100 in `lib/sbitmap.c`. I'm expecting this function deals with clearing bits within an `sbitmap`, but the "deferred" part immediately flags my attention. This suggests we're not clearing the bits *immediately*. There's likely some sort of mechanism for batching or delaying the actual bit manipulations.
I'll be looking for clues about the data structures being used. I'll need to see how the "deferred" aspect is implemented. Are we talking about a list, queue, or something else to track the bits to be cleared? Is there an associated flush mechanism? I want to see if this defers clearing to an interrupt context, a different thread, or perhaps a timer callback.
I need to understand what triggered the deferral. Is there a specific use-case driving this design? Why not an immediate clear? Is it related to performance, synchronization, or a desire to avoid certain locking scenarios? Is there a reason we're concerned with doing this asynchronously? I'll be looking for comments that would indicate this rationale. What are the preconditions for this function's execution? Are there any invariants maintained around the sbitmap state? I'll also be trying to spot potential race conditions, locking issues, or any other concurrency considerations in the logic.
Ultimately, I want to form a complete understanding of how this "deferred clear" mechanism is implemented, what its purpose is, and its performance characteristics in comparison to a direct clear approach.
|
| 32/2 |
2026/11/17 07:47 |
tool |
read-file |
0m
Args: map[File:lib/sbitmap.c FirstLine:60 LineCount:45]
Results: map[Contents: 60: /*
61: * See if we have deferred clears that we can batch move
62: */
63: static inline bool sbitmap_deferred_clear(struct sbitmap_word *map,
64: unsigned int depth, unsigned int alloc_hint, bool wrap)
65: {
66: unsigned long mask, word_mask;
67:
68: guard(raw_spinlock_irqsave)(&map->swap_lock);
69:
70: if (!map->cleared) {
71: if (depth == 0)
72: return false;
73:
74: word_mask = (~0UL) >> (BITS_PER_LONG - depth);
75: /*
76: * The current behavior is to always retry after moving
77: * ->cleared to word, and we change it to retry in case
78: * of any free bits. To avoid an infinite loop, we need
79: * to take wrap & alloc_hint into account, otherwise a
80: * soft lockup may occur.
81: */
82: if (!wrap && alloc_hint)
83: word_mask &= ~((1UL << alloc_hint) - 1);
84:
85: return (READ_ONCE(map->word) & word_mask) != word_mask;
86: }
87:
88: /*
89: * First get a stable cleared mask, setting the old mask to 0.
90: */
91: mask = xchg(&map->cleared, 0);
92:
93: /*
94: * Now clear the masked bits in our free word
95: */
96: atomic_long_andnot(mask, (atomic_long_t *)&map->word);
97: BUILD_BUG_ON(sizeof(atomic_long_t) != sizeof(map->word));
98: return true;
99: }
100:
101: int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift,
102: gfp_t flags, int node, bool round_robin,
103: bool alloc_hint)
104: {
]
|
| 33/2 |
2026/11/17 07:47 |
llm |
expert |
0m
Model:
Tokens:
input: 28102
output: 37
thoughts: 2646
Thoughts: **Analysis of the sbitmap Bit Allocation Algorithm and KCSAN Data Race Report**
Okay, here's the deal. I've been dissecting the `sbitmap_deferred_clear` function, and the way it handles bit allocation is pretty interesting. I see that `map->word` is the target of multiple atomic updates: `atomic_long_andnot`, `test_and_set_bit_lock`, and `atomic_long_try_cmpxchg`. This screams atomicity, which is good. However, KCSAN is flagging a potential data race due to a plain read within `_find_next_zero_bit`, which is called by `__sbitmap_get_word`. Let's break this down.
The core of the issue is this "test-and-test-and-set" optimization pattern. It's a clever way to allocate bits. The initial `find_next_zero_bit(word, depth, hint)` performs a non-atomic read to *find* a candidate bit. This bit's index, `nr`, is then used in a `test_and_set_bit_lock(nr, word)` which is an atomic read-modify-write operation. If that atomic operation succeeds (returning 0), the bit is claimed. If it fails (returns 1), we iterate. This minimizes contention.
The data race is triggered because KCSAN is flagging the plain read in `find_next_zero_bit` as a concurrent read with the atomic writes performed via `test_and_set_bit_lock`. The problem is `find_next_zero_bit` reads a shared memory location without using `READ_ONCE()` or atomics.
Now, does this *actually* cause a problem? I'm examining this to see if it fits the criteria to be ignored.
1. **Diagnostics/Stats:** Not relevant here.
2. **Heuristic Hints:** Bingo! This read is acting as a heuristic hint. The `find_next_zero_bit` is *optimistically* trying to find a free bit, but then `test_and_set_bit_lock` provides the *actual* claim and validation. This is a very important point!
3. **Single-Writer Flag Updates:** Not relevant here.
4. **Marked Reloads & Lock Re-checks:** The `test_and_set_bit_lock` *is* the re-check! If `test_and_set_bit_lock` fails, the `find_next_zero_bit` is re-run, so it's a re-check! The atomic operation makes sure the read is *always* consistent, as there is an acquire-barrier.
5. **Safe Overwrites & Plain Scalar Accesses:** Irrelevant.
It is acting as a heuristic/optimistic search feeding into an atomic re-check / claim (`test_and_set_bit_lock`). The return from `test_and_set_bit_lock` is verified. So the algorithm *correctly* re-verifies the state of the memory with acquire semantics.
Crucially, `test_and_set_bit_lock` is *also* an atomic instruction (likely `lock bts`), which implies a memory barrier.
Could a compiler optimization mess this up? Not likely. `find_next_zero_bit` can return a valid index. The pointer `word` is passed to the function, so caching the load wouldn't work across calls. The function is also re-called within a loop, so the compiler has to re-read the word! If `test_and_set_bit_lock` *fails*, then, even though it didn't change the bit it re-establishes a memory barrier to force re-loads. Furthermore, `word` is cacheline-aligned and of size `sizeof(unsigned long)`: this means that reads/writes are atomic on most architectures, and the loads/stores do not tear.
Also, it is used by blk-mq for tag allocation and I bet there are similar patterns in other subsystems, but I should probably check that this pattern is well-understood and common in the kernel. Let's see if this pattern is used elsewhere with a quick grep!
In conclusion, while KCSAN flags a data race, it's a false positive in this case. The plain read in `find_next_zero_bit` is part of an optimistic search, and the `test_and_set_bit_lock` provides the atomic re-check and memory ordering needed to ensure correctness. No harm, no foul.
|
| 34/2 |
2026/11/17 07:47 |
tool |
grepper |
0m
Args: map[Expression:test_and_set_bit_lock PathPrefixes:[lib/ block/]]
Results: map[Output:block/blk-mq.c=3755=static int blk_mq_hctx_notify_offline(unsigned int cpu, struct hlist_node *node)
--
block/blk-mq.c-3767- * The smp_mb__after_atomic() Pairs with the implied barrier in
block/blk-mq.c:3768: * test_and_set_bit_lock in sbitmap_get(). Ensures the inactive flag is
block/blk-mq.c-3769- * seen once we return from the tag allocator.
--
lib/sbitmap.c=158=static int __sbitmap_get_word(unsigned long *word, unsigned long depth,
--
lib/sbitmap.c-180-
lib/sbitmap.c:181: if (!test_and_set_bit_lock(nr, word))
lib/sbitmap.c-182- break;
--
lib/sbitmap.c=676=void sbitmap_queue_clear(struct sbitmap_queue *sbq, unsigned int nr,
--
lib/sbitmap.c-694- * proper ordering of clear_bit_unlock()/waitqueue_active() in the waker
lib/sbitmap.c:695: * and test_and_set_bit_lock()/prepare_to_wait()/finish_wait() in the
lib/sbitmap.c-696- * waiter. See the comment on waitqueue_active().
]
|
| 35/2 |
2026/11/17 07:47 |
llm |
expert |
0m
Model:
Tokens:
input: 32157
output: 34
thoughts: 48
Thoughts: Okay, here's my take on those thoughts, tailored for an expert audience:
**Diving into sbitmap.c**
Alright, that comment at line 694 in `lib/sbitmap.c` is intriguing. It's usually a good sign when there's an in-code note, especially at that line number. I'm going to pull up the surrounding context to get the full picture. Let's use `read-file` to grab lines 670 through 710. That should give me enough of a window to understand the intent of the comment and the code it's describing. I'm hoping it reveals some edge case handling or perhaps a key optimization within that portion of the `sbitmap` implementation that might be worth considering further. I'm prepared to examine any unusual bit-fiddling or tricky logic that's in play.
|
| 36/2 |
2026/11/17 07:47 |
tool |
read-file |
0m
Args: map[File:lib/sbitmap.c FirstLine:670 LineCount:45]
Results: map[Contents: 670: smp_mb__after_atomic();
671: sbitmap_queue_wake_up(sbq, nr_tags);
672: sbitmap_update_cpu_hint(&sbq->sb, raw_smp_processor_id(),
673: tags[nr_tags - 1] - offset);
674: }
675:
676: void sbitmap_queue_clear(struct sbitmap_queue *sbq, unsigned int nr,
677: unsigned int cpu)
678: {
679: /*
680: * Once the clear bit is set, the bit may be allocated out.
681: *
682: * Orders READ/WRITE on the associated instance(such as request
683: * of blk_mq) by this bit for avoiding race with re-allocation,
684: * and its pair is the memory barrier implied in __sbitmap_get_word.
685: *
686: * One invariant is that the clear bit has to be zero when the bit
687: * is in use.
688: */
689: smp_mb__before_atomic();
690: sbitmap_deferred_clear_bit(&sbq->sb, nr);
691:
692: /*
693: * Pairs with the memory barrier in set_current_state() to ensure the
694: * proper ordering of clear_bit_unlock()/waitqueue_active() in the waker
695: * and test_and_set_bit_lock()/prepare_to_wait()/finish_wait() in the
696: * waiter. See the comment on waitqueue_active().
697: */
698: smp_mb__after_atomic();
699: sbitmap_queue_wake_up(sbq, 1);
700: sbitmap_update_cpu_hint(&sbq->sb, cpu, nr);
701: }
702: EXPORT_SYMBOL_GPL(sbitmap_queue_clear);
703:
704: void sbitmap_queue_wake_all(struct sbitmap_queue *sbq)
705: {
706: int i, wake_index;
707:
708: /*
709: * Pairs with the memory barrier in set_current_state() like in
710: * sbitmap_queue_wake_up().
711: */
712: smp_mb();
713: wake_index = atomic_read(&sbq->wake_index);
714: for (i = 0; i < SBQ_WAIT_QUEUES; i++) {
]
|
| 37/2 |
2026/11/17 07:47 |
llm |
expert |
0m
Model:
Tokens:
input: 33180
output: 40
thoughts: 1513
Thoughts: **Analyzing the sbitmap Concurrency Issue**
Alright, let's break this down. My initial focus is on those lines of code (680-685) and the implications of the `sbitmap_deferred_clear_bit` function. I immediately recognize this as a critical section concerning bit allocation within an sbitmap. The comment clearly highlights the need for ordering READ/WRITE operations on the associated instance (e.g., blk_mq) relative to the clear bit operation to avoid re-allocation races. The memory barrier `smp_mb__before_atomic()` is there, logically, to enforce the proper ordering. It also pairs with one in `__sbitmap_get_word`, which makes sense. I see the invariant: the bit must be zero *before* it's in use. This looks like a classic reader/writer problem. Then the comment about the memory barrier relating `clear_bit_unlock()/waitqueue_active()` and `test_and_set_bit_lock()/prepare_to_wait()/finish_wait()` in the waker/waiter respectively jumps out at me, this is important to ensure ordering between wait queues and bit operations.
Now, I'm going to look at that KCSAN report and the stack traces. Two tasks, 6223 and 6224, on different CPUs are triggering something interesting. They're both calling `sbitmap_get()`. The traces are nearly identical, and they're converging in the same place; both threads appear to be going through `sbitmap_get()` via `scsi_dev_queue_ready`, `scsi_mq_get_budget`, down to `blk_mq_get_dispatch_budget`, all the way down to `swap_cluster_readahead` and `lru_gen_shrink_lruvec`.
So, *both* tasks are hitting the `sbitmap_get()` function on the SCSI device queue's sbitmap budget map. I'll need to confirm that `scsi_dev_queue_ready` is indeed the caller. I'm going to quickly check `drivers/scsi/scsi_lib.c:1414` to see exactly how and when this budget map is being used. And then, I will check the interaction in `sbitmap_get` with the comments noted at the top. This is shaping up to be a race condition in how the SCSI device queue is managing its budget bits within the sbitmap structure, and my goal is to figure out the exact ordering and synchronization issue to develop a fix.
|
| 38/2 |
2026/11/17 07:48 |
tool |
read-file |
0m
Args: map[File:drivers/scsi/scsi_lib.c FirstLine:1405 LineCount:25]
Results: map[Contents:1405: */
1406: static inline int scsi_dev_queue_ready(struct request_queue *q,
1407: struct scsi_device *sdev)
1408: {
1409: int token;
1410:
1411: if (!sdev->budget_map.map)
1412: return INT_MAX;
1413:
1414: token = sbitmap_get(&sdev->budget_map);
1415: if (token < 0)
1416: return -1;
1417:
1418: if (!atomic_read(&sdev->device_blocked))
1419: return token;
1420:
1421: /*
1422: * Only unblock if no other commands are pending and
1423: * if device_blocked has decreased to zero
1424: */
1425: if (scsi_device_busy(sdev) > 1 ||
1426: atomic_dec_return(&sdev->device_blocked) > 0) {
1427: sbitmap_put(&sdev->budget_map, token);
1428: return -1;
1429: }
]
|
| 39/2 |
2026/11/17 07:48 |
llm |
expert |
0m
Model:
Tokens:
input: 35640
output: 34
thoughts: 66
Thoughts: Here's a breakdown of my thought process:
**Concurrent Budget Allocation: Exploring sbitmap**
Okay, so I'm looking at these two tasks and they're both trying to grab a budget token from `sdev->budget_map` concurrently. My initial instinct is to dig deeper because I'm seeing a potential race condition here. This sounds like something that requires careful management. And then, a thought jumps out: `sbitmap`! I remember that thing; it's *specifically* designed for lockless and concurrent bit allocation. That sparks my interest. This could be the solution, or at least a tool that's being *used* to solve this.
I need to confirm. My next move is clear. I'm heading straight for the source code to get the specifics. I'm diving into the headers. I'll need to check `include/linux/sbitmap.h` and the corresponding comments in `lib/sbitmap.c`. I need to review the architecture, the intended use-cases, and confirm whether it is actually what's happening here. The comments and structure will clarify whether we are using a correct implementation and what caveats apply.
|
| 40/2 |
2026/11/17 07:48 |
tool |
read-file |
0m
Args: map[File:include/linux/sbitmap.h FirstLine:1 LineCount:50]
Results: map[Contents: 1: /* SPDX-License-Identifier: GPL-2.0-only */
2: /*
3: * Fast and scalable bitmaps.
4: *
5: * Copyright (C) 2016 Facebook
6: * Copyright (C) 2013-2014 Jens Axboe
7: */
8:
9: #ifndef __LINUX_SCALE_BITMAP_H
10: #define __LINUX_SCALE_BITMAP_H
11:
12: #include <linux/atomic.h>
13: #include <linux/bitops.h>
14: #include <linux/cache.h>
15: #include <linux/list.h>
16: #include <linux/log2.h>
17: #include <linux/minmax.h>
18: #include <linux/percpu.h>
19: #include <linux/slab.h>
20: #include <linux/smp.h>
21: #include <linux/types.h>
22: #include <linux/wait.h>
23:
24: struct seq_file;
25:
26: /**
27: * struct sbitmap_word - Word in a &struct sbitmap.
28: */
29: struct sbitmap_word {
30: /**
31: * @word: word holding free bits
32: */
33: unsigned long word;
34:
35: /**
36: * @cleared: word holding cleared bits
37: */
38: unsigned long cleared ____cacheline_aligned_in_smp;
39:
40: /**
41: * @swap_lock: serializes simultaneous updates of ->word and ->cleared
42: */
43: raw_spinlock_t swap_lock;
44: } ____cacheline_aligned_in_smp;
45:
46: /**
47: * struct sbitmap - Scalable bitmap.
48: *
49: * A &struct sbitmap is spread over multiple cachelines to avoid ping-pong. This
50: * trades off higher memory usage for better scalability.
]
|
| 41/2 |
2026/11/17 07:48 |
llm |
expert |
0m
Model:
Tokens:
input: 36620
output: 35
thoughts: 50
Thoughts: Okay, here's my assessment of this information, from my perspective as someone well-versed in memory management and data structures:
**Deconstructing sbitmap's Design**
Alright, so I'm looking at this `sbitmap` implementation, and the description immediately catches my eye: "Fast and scalable bitmaps... spread over multiple cachelines to avoid ping-pong. This trades off higher memory usage for better scalability." That's a classic engineering trade-off! We're prioritizing throughput and reduced contention β crucial for any concurrent data structure β even if it means we're throwing more memory at the problem. I'm already mentally running through the implications: potentially wider cache lines, more complex access patterns. I'll need to drill down into the specific implementation to see if it's been done elegantly, or if they've opened up avenues for new problems.
Now, let's peek into the `__sbitmap_get` function.
|
| 42/2 |
2026/11/17 07:48 |
tool |
codesearch-definition-source |
0m
Args: map[ContextFile:lib/sbitmap.c Name:__sbitmap_get]
Results: map[SourceCode: 261: static int __sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint)
262: {
263: unsigned int index;
264:
265: index = SB_NR_TO_INDEX(sb, alloc_hint);
266:
267: /*
268: * Unless we're doing round robin tag allocation, just use the
269: * alloc_hint to find the right word index. No point in looping
270: * twice in find_next_zero_bit() for that case.
271: */
272: if (sb->round_robin)
273: alloc_hint = SB_NR_TO_BIT(sb, alloc_hint);
274: else
275: alloc_hint = 0;
276:
277: return sbitmap_find_bit(sb, UINT_MAX, index, alloc_hint,
278: !sb->round_robin);
279: }
SourceFile:lib/sbitmap.c]
|
| 43/2 |
2026/11/17 07:48 |
llm |
expert |
0m
Model:
Tokens:
input: 37215
output: 35
thoughts: 1752
Thoughts: **Analyzing the Atomic Bit Allocation in sbitmap**
Okay, let's break this down. I'm looking at the `__sbitmap_get_word` function and how it handles concurrent bit allocation. My goal is to ensure this is thread-safe and doesn't lead to any nasty race conditions.
First, I'm tracing the logic flow. Two tasks, A and B, want a bit. They both run `__sbitmap_get_word` on the same `map->word`. The core operation is `find_next_zero_bit` followed by `test_and_set_bit_lock`. The key here is `test_and_set_bit_lock` β it's atomic.
Let's look at the critical interleaving. If A reads a free bit (e.g., bit 38) and B *also* reads that same bit as free before A can lock it, then A will lock bit 38, succeed, and B is going to fail in its lock attempt on bit 38. That means B correctly sets its hint to 39 and finds a free bit on the next iteration. This scenario is handled correctly.
Now, what about concurrent reads? Can a read of `map->word` be torn? No, it's an aligned `unsigned long`, so single machine word reads are atomic. Can the read be garbage? Also no; It sees the value *before* A's write or *after* A's write, so either bit 38 fails because it's still zero, or bit 38 is one and B's hint is set correctly. So it's safe.
What if all the bits are full in a word? `find_next_zero_bit` returns a value that's out of range. Then the function returns -1, which is correct and the `sbitmap_deferred_clear` and `sbitmap_find_bit` handles it appropriately.
Okay, what if `test_and_set_bit_lock` sets the last bit *just* as another thread is calling `find_next_zero_bit`? If the other thread sees the old word (with the last bit free): it calls `test_and_set_bit_lock` on that bit. The atomic operation fails (returns 1) and so it advances the `hint` and returns `-1`. If the other thread sees the new word, all bits set, `find_next_zero_bit` immediately returns `-1`, which is correct.
What about *concurrent* clearing of bits? That's done with `atomic_long_andnot`. If `find_next_zero_bit` runs concurrently, it can *either* see the bit before it's cleared (still 1) and skip it β a slightly stale read, but fine, or see the bit after it's cleared (0) and it's able to acquire it. It should be correct.
Now, let's run through the common failure modes. *Use-after-free*? No, the `map->word` is managed with the queue's life cycle. *Out-of-bounds*? No, `nr < depth <= BITS_PER_LONG`. *Livelock*? No, the `hint` advances on failure. The loop is guaranteed to terminate because the size of a word is limited. *Deadlock*? No locks are held in this function. *Double allocation*? No, `test_and_set_bit_lock` is atomic, so only one thread can win. *Lost wakeups*? The waitqueues and memory barriers are correctly handled. *Missing memory ordering*? The `test_and_set_bit_lock` has ACQUIRE semantics, so accesses after a successful lock are correctly ordered.
Finally, what about the compiler? Could it be optimizing this code in a dangerous way? I'll need to check the definition of `find_next_zero_bit` to be sure.
|
| 44/2 |
2026/11/17 07:48 |
tool |
grepper |
0m
Args: map[Expression:find_next_zero_bit PathPrefixes:[include/linux/find.h]]
Results: map[Output:include/linux/find.h=17=unsigned long _find_next_or_bit(const unsigned long *addr1, const unsigned long *addr2,
include/linux/find.h-18- unsigned long nbits, unsigned long start);
include/linux/find.h:19:unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long nbits,
include/linux/find.h-20- unsigned long start);
--
include/linux/find.h=38=unsigned long _find_first_zero_bit_le(const unsigned long *addr, unsigned long size);
include/linux/find.h:39:unsigned long _find_next_zero_bit_le(const unsigned long *addr, unsigned
include/linux/find.h-40- long size, unsigned long offset);
--
include/linux/find.h=148=unsigned long find_next_or_bit(const unsigned long *addr1,
--
include/linux/find.h-165-
include/linux/find.h:166:#ifndef find_next_zero_bit
include/linux/find.h-167-/**
include/linux/find.h:168: * find_next_zero_bit - find the next cleared bit in a memory region
include/linux/find.h-169- * @addr: The address to base the search on
--
include/linux/find.h=176=static __always_inline
include/linux/find.h:177:unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
include/linux/find.h-178- unsigned long offset)
--
include/linux/find.h-189-
include/linux/find.h:190: return _find_next_zero_bit(addr, size, offset);
include/linux/find.h-191-}
--
include/linux/find.h=507=static __always_inline
include/linux/find.h:508:unsigned long find_next_zero_bit_le(const void *addr, unsigned long size, unsigned long offset)
include/linux/find.h-509-{
include/linux/find.h:510: return find_next_zero_bit(addr, size, offset);
include/linux/find.h-511-}
--
include/linux/find.h=520=unsigned long find_first_zero_bit_le(const void *addr, unsigned long size)
--
include/linux/find.h-526-
include/linux/find.h:527:#ifndef find_next_zero_bit_le
include/linux/find.h-528-static __always_inline
include/linux/find.h:529:unsigned long find_next_zero_bit_le(const void *addr, unsigned
include/linux/find.h-530- long size, unsigned long offset)
--
include/linux/find.h-541-
include/linux/find.h:542: return _find_next_zero_bit_le(addr, size, offset);
include/linux/find.h-543-}
--
include/linux/find.h=562=unsigned long find_next_bit_le(const void *addr, unsigned
--
include/linux/find.h-606- for ((bit) = 0; \
include/linux/find.h:607: (bit) = find_next_zero_bit((addr), (size), (bit)), (bit) < (size); \
include/linux/find.h-608- (bit)++)
--
include/linux/find.h-611-#define for_each_clear_bit_from(bit, addr, size) \
include/linux/find.h:612: for (; (bit) = find_next_zero_bit((addr), (size), (bit)), (bit) < (size); (bit)++)
include/linux/find.h-613-
--
include/linux/find.h-623- (b) = find_next_bit((addr), (size), b), \
include/linux/find.h:624: (e) = find_next_zero_bit((addr), (size), (b) + 1), \
include/linux/find.h-625- (b) < (size); \
--
include/linux/find.h-637- (b) = find_next_bit((addr), (size), (b)), \
include/linux/find.h:638: (e) = find_next_zero_bit((addr), (size), (b) + 1), \
include/linux/find.h-639- (b) < (size); \
--
include/linux/find.h-650- for ((b) = 0; \
include/linux/find.h:651: (b) = find_next_zero_bit((addr), (size), (b)), \
include/linux/find.h-652- (e) = find_next_bit((addr), (size), (b) + 1), \
--
include/linux/find.h-664- for (; \
include/linux/find.h:665: (b) = find_next_zero_bit((addr), (size), (b)), \
include/linux/find.h-666- (e) = find_next_bit((addr), (size), (b) + 1), \
]
|
| 45/2 |
2026/11/17 07:48 |
llm |
expert |
0m
Model:
Tokens:
input: 41280
output: 35
thoughts: 23
Thoughts: Here's a summary of my thought process, as requested:
**Diving into `find.h`**
Okay, so I need to refresh my memory on the implementation details of the kernel's search functions, particularly those related to finding bits or sequences. Time to open up the `include/linux/find.h` file. Let's start with lines 170-195. I'm expecting to find some crucial macros or inline functions here. Likely something to do with optimized bit manipulation, and probably some architecture-specific implementations or at least conditional compilation based on the target architecture's capabilities. I'm particularly interested in seeing how they handle word-at-a-time searches versus bit-at-a-time approaches. Are they using prefetch hints? What about the loop unrolling? And how do they deal with potential alignment issues? I need to analyze this to understand the performance characteristics and potential trade-offs within the kernel's search algorithms.
|
| 46/2 |
2026/11/17 07:48 |
tool |
read-file |
0m
Args: map[File:include/linux/find.h FirstLine:170 LineCount:25]
Results: map[Contents: 170: * @size: The bitmap size in bits
171: * @offset: The bitnumber to start searching at
172: *
173: * Returns the bit number of the next zero bit
174: * If no bits are zero, returns @size.
175: */
176: static __always_inline
177: unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
178: unsigned long offset)
179: {
180: if (small_const_nbits(size)) {
181: unsigned long val;
182:
183: if (unlikely(offset >= size))
184: return size;
185:
186: val = *addr | ~GENMASK(size - 1, offset);
187: return val == ~0UL ? size : ffz(val);
188: }
189:
190: return _find_next_zero_bit(addr, size, offset);
191: }
192: #endif
193:
194: #ifndef find_first_bit
]
|
| 47/2 |
2026/11/17 07:48 |
llm |
expert |
0m
Model:
Tokens:
input: 41890
output: 15
thoughts: 2586
Thoughts: **Analysis of the Lockless Bitmap Race in `__sbitmap_get_word`**
Okay, here's the breakdown of this race condition in `__sbitmap_get_word`. I'm looking at `_find_next_zero_bit`, and then `FIND_NEXT_BIT`, and it's all about how we're finding free bits in this lockless bitmap, the `sbitmap`. I'm trying to decide if this is actually a data race and whether it is BENIGN. I'm going through the list to classify the BENIGN races, like diagnostics, hints, single-writer flags, marked reloads, or safe overwrites.
It looks like `find_next_zero_bit` is performing a scan, acting as a heuristic, to find a candidate zero bit. This candidate is then atomically checked and claimed using `test_and_set_bit_lock`. If another thread gets there first, `test_and_set_bit_lock` fails, and the scan continues. `test_and_set_bit_lock` takes care of the memory ordering, using acquire semantics. The word is an aligned `unsigned long` inside `struct sbitmap_word`, which means it cannot tear. The compiler can't mess things up, because it's a call to an out-of-line function, and also because `test_and_set_bit_lock` in the loop has the necessary compiler memory clobbers.
My first thought: Should we use `READ_ONCE` or `data_race` here? This `find_next_zero_bit` is used across the kernel, and `READ_ONCE` isn't needed here. But wait... Looking at commit `6ad0d7e0f4b6`, in `__sbitmap_queue_get_batch`, they used `READ_ONCE` before `find_first_zero_bit` to suppress KCSAN reports on similar code, where they intentionally introduced such BENIGN data races. This was to reduce noise.
In `__sbitmap_get_word`, a similar approach using `READ_ONCE` or wrapping the `find_next_zero_bit` call with `data_race()` would also suppress the report, but the developers recognized this as BENIGN.
Let's do a sanity check: I'm checking to make sure it works fine on both 32- and 64-bit architectures. On 32-bit, the `unsigned long` is 4 bytes and it's aligned, which means it's atomic and there's no tearing. Also, I need to check the memory ordering between claiming the bit and using the resource after. `test_and_set_bit_lock` provides acquire memory barrier semantics: operations after `test_and_set_bit_lock` cannot be reordered before it.
Okay, let's look at the failure detectable. Since this is BENIGN, `FailureDetectableBy` isn't needed. The `set-results` tool just needs `Benign: true`.
Here's my final breakdown:
- **Race Summary**: `__sbitmap_get_word` (via `test_and_set_bit_lock`) vs `__sbitmap_get_word` (via `find_next_zero_bit`) on `sbitmap_word::word`.
- **Synchronization context**:
`sbitmap` is designed as a scalable lockless bitmap. Bits are claimed concurrently without global locks.
Writer (Task 6223) executes `test_and_set_bit_lock(nr, word)` to atomically claim a free bit in `map->word`.
Reader (Task 6224) executes `find_next_zero_bit(word, depth, hint)` which performs a plain, lockless read of `map->word` to optimistically locate a candidate zero bit.
- **Final Classification**: **BENIGN**
- **Reasoning**:
1. Optimistic heuristic scan: `find_next_zero_bit()` performs an optimistic lockless search for a zero bit. Any bit found is merely a candidate and is immediately verified and claimed via `test_and_set_bit_lock()`.
2. Atomic claim & re-check: If a concurrent thread modifies or claims that bit in the interim, `test_and_set_bit_lock()` fails (returns 1). The loop advances `hint = nr + 1` and retries. If no zero bit is found or the word is full, `__sbitmap_get_word()` returns -1.
3. No tearing: `map->word` is an aligned word-sized scalar (`unsigned
|
| 48/2 |
2026/11/17 07:48 |
tool |
set-results |
0m
Args:
Results: map[Benign:true FailureDetectableBy:]
|
| 49/2 |
2026/11/17 07:48 |
llm |
expert |
0m
Model:
Tokens:
input: 45536
output: 704
thoughts: 19
Thoughts: Here's my attempt at summarizing the thought process, tailored for an expert audience:
**Finalizing the Response**
Okay, the tool's output is exactly what I anticipated. No surprises there. Now, the core task is to meticulously craft the final response, ensuring absolute adherence to the established protocol. Clarity is paramount, and any ambiguity is unacceptable. I need to be precise, concise, and leave no room for misinterpretation. This isn't just about delivering the information; it's about doing so in a way that demonstrates rigorous methodology and professional communication standards. The final output must be exemplary.
|
| 50/1 |
2026/11/17 07:49 |
action |
format-explanation |
0m
Results: map[Explanation:### Race Summary
`__sbitmap_get_word` (via `test_and_set_bit_lock`) vs `__sbitmap_get_word` (via
`find_next_zero_bit` / `_find_next_zero_bit`) on `sbitmap_word::word`.
### Synchronization Context
`sbitmap` is designed as a lockless, scalable bitmap allocator (used in `blk-mq`
and SCSI queue budgeting). It avoids global locking by having threads search for
available bits locklessly and claim them using atomic bitops:
- Task 6223 performs an atomic read-modify-write (`test_and_set_bit_lock(nr,
word)`) to claim bit `nr` in `sbitmap_word::word`.
- Task 6224 concurrently performs a plain read in `find_next_zero_bit(word,
depth, hint)` to find a candidate zero bit.
No locks are held during bit discovery, allowing the plain load in
`find_next_zero_bit()` to race with concurrent atomic updates on `word`.
### Final Classification
**BENIGN**
### Reasoning
This is a classic optimistic scan pattern (test-and-test-and-set):
1. **Heuristic Scan with Atomic Re-check:** `find_next_zero_bit()` performs an
optimistic lockless scan across `map->word` to locate a potential candidate zero
bit `nr`. The found bit is immediately re-checked and claimed atomically using
`test_and_set_bit_lock(nr, word)`. If another thread has already set that bit,
`test_and_set_bit_lock()` returns non-zero (failure), causing the loop to
advance `hint = nr + 1` and scan again. Two threads cannot claim the same bit.
2. **No Tearing:** `map->word` is an aligned machine word (`unsigned long`,
located at the start of cacheline-aligned `struct sbitmap_word`). Word-sized
aligned scalar loads and stores are atomic at the hardware level and cannot tear
on any architecture supported by Linux.
3. **No Fused or Hoisted Accesses:** `_find_next_zero_bit()` is an out-of-line
function call in `lib/find_bit.c`. Furthermore, every loop iteration executes
`test_and_set_bit_lock()`, which provides volatile assembly and compiler memory
clobbers, preventing the compiler from caching or hoisting the load out of the
loop.
4. **Ordering & Safety:** `test_and_set_bit_lock()` provides acquire barrier
semantics, properly ordering all accesses to the resource associated with the
acquired bit after the bit acquisition.
### Recommended Annotations
To suppress the benign KCSAN report, `__sbitmap_get_word()` can either read
`*word` with `READ_ONCE()` into a local variable before passing its address to
`find_next_zero_bit()` (matching the approach in commit `6ad0d7e0f4b6` for
`__sbitmap_queue_get_batch()`), or wrap the call with `data_race()`:
```c
nr = data_race(find_next_zero_bit(word, depth, hint));
```]
|