0xMiden / 0xMiden/compiler

SmallDeque leaks its elements, and a deque built from a SmallVec frees some of them twice

オープン
#1,375 コメント 1 件 リアクション 0 件 担当者 0 名 GitHub で見る
主要言語
Rust
スター
115
フォーク
84
平均マージ
1日 8時間
マージ済み PR(30日)
15

説明

### Packages versions

`compiler` at 52abe7d76d5757dae3ca074b16a3cea361fa5a4e on `next`, which is also the `v0.10.0` tag.

### Bug description

`SmallDeque` has no `Drop` impl, so dropping one runs only the backing `SmallVec`'s drop, which
drops `SmallVec::len()` elements. For a deque built with `new()` that length is 0 — the deque
writes its elements through raw pointers and never maintains it, the same bookkeeping gap as in
#1374 — so none of the elements are dropped at all.

https://github.com/0xMiden/compiler/blob/52abe7d76d5757dae3ca074b16a3cea361fa5a4e/hir/src/adt/smalldeque.rs#L24-L37

The conversion from `SmallVec` keeps the vector's length instead, and that length then stops
following the deque:

https://github.com/0xMiden/compiler/blob/52abe7d76d5757dae3ca074b16a3cea361fa5a4e/hir/src/adt/smalldeque.rs#L1771-L1774

So once an element has been moved out with `pop_front`, `pop_back` or `remove`, the `SmallVec`
still drops that physical slot when the deque goes out of scope, and the element is dropped twice.
`from_iter` builds through the same conversion:

https://github.com/0xMiden/compiler/blob/52abe7d76d5757dae3ca074b16a3cea361fa5a4e/hir/src/adt/smalldeque.rs#L2657

Both are reachable through `hir::adt`, which re-exports `SmallDeque` and `SmallPriorityQueue`, and
the priority queue's own `from_iter` and `From` construct through that path:

https://github.com/0xMiden/compiler/blob/52abe7d76d5757dae3ca074b16a3cea361fa5a4e/hir/src/adt/smallprio.rs#L149

https://github.com/0xMiden/compiler/blob/52abe7d76d5757dae3ca074b16a3cea361fa5a4e/hir/src/adt/smallprio.rs#L164

The in-tree queue does hold elements with destructors — `InsertionInfoItem` wraps an
`Rc` — but it is built with `new()`, so it takes the leaking path rather than the
double-free one:

https://github.com/0xMiden/compiler/blob/52abe7d76d5757dae3ca074b16a3cea361fa5a4e/hir/src/ir/dominance/nca.rs#L804-L806

The existing drop coverage does not reach either case: `test_vec_deque_truncate_drop` empties the
deque with `truncate(0)` before it goes out of scope, so the deque is never dropped with elements
still in it.

https://github.com/0xMiden/compiler/blob/52abe7d76d5757dae3ca074b16a3cea361fa5a4e/hir/src/adt/smalldeque.rs#L3706

This is separate from #1374 and the fix I have for that one does not address it.

### How can this be reproduced?

With an element type that has a destructor and is not zero-sized — a ZST takes a different path
through the deque:

```rust
struct Elem(Box);
impl Drop for Elem {
fn drop(&mut self) { /* count */ }
}

let mut deque = SmallDeque::::new();
for i in 0..4 {
deque.push_back(Elem(Box::new(i)));
}
drop(deque); // no destructor runs

let sv: SmallVec<[Elem; 8]> = (0..4).map(|i| Elem(Box::new(i))).collect();
let mut deque = SmallDeque::::from(sv);
deque.pop_front();
drop(deque); // aborts
```

### Relevant log output

after pop_front (expect 1): 1
free(): double free detected in tcache 2
process didn't exit successfully (signal: 6, SIGABRT)

and under Miri:

error: Undefined Behavior: memory access failed: alloc53265 has been freed, so this pointer
is dangling

コントリビューションガイド

コントリビューションガイドを開く

調査の方向性

The bug is in hir/src/adt/smalldeque.rs and hir/src/adt/smallprio.rs. Start by reading the SmallDeque struct and its From conversion. Write a test with a Drop type to reproduce the leak and double-free. The fix likely involves implementing Drop for SmallDeque to drop elements correctly and updating the length tracking. Run existing tests and Miri to verify.

索引モデルが issue の本文から書いたものです。

評価

技術スタック
rust
領域
compilers
issue の種類
バグ
難易度
3/5
見積もり時間
1〜2日
活発さ
活発
明瞭さ
明確に書かれている
初心者へのやさしさ
65/100

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。