search

rust-lang / futures-rs

Zero-cost asynchronous programming in Rust
https://rust-lang.github.io/futures-rs/
Apache License 2.0
5.4k stars 626 forks source link

fix FuturesOrdered #2664

Closed conradludgate closed 1 year ago

conradludgate commented 1 year ago

fixes #2663

taiki-e commented 1 year ago

Thanks for the PR! Considering the overflow of isize (which can actually happen on 32-bit targets), this still seems broken, but this seems more correct than the current one.

conradludgate commented 1 year ago

Yeah. I have some ideas how to fix the overflow too, but it's not as trivial a fix

https://github.com/conradludgate/futures-buffered/blob/7db2b4ca822ee95bb53871fee7867b420a04a7fa/src/futures_ordered_bounded.rs#L216-L231

Essentially, if the next_outgoing_index has the MSB set, then it flips the MSB of every task/output. This preserves the order and ensures that the outgoing is <= isize::MAX. The length of the queue would have to be another isize::MAX+1 in order to overflow, but you'd OOM before that.

Reason this is correct Let's say our system is 16-bit. So we can have a theoretical maximum memory of 65536 bytes. Our futures are `[(usize, F)]` which is at least 2 bytes assuming ZST future. Our ready queue similarly stores `[(usize, F::Output)]` which is also at least 2 bytes with a ZST output. In total, we can only fit 65536/2 entries into memory, ignoring any extra necessary overhead. Therefore, we only need to be able to store at maximum `(usize::MAX+1)/2` entries. In our `FuturesOrdered`, we have `next_outgoing_index` as the head, and `next_incoming_index` as the tail. ``` [_, _, .., _, _, _, _, _, .., _, _] ^ head. ^ tail ``` If our head gets over half way through our usize, then to store our theoretical maximum, tail can be at most usize::MAX+1, which is 0. We can't insert any more without OOM as shown, so this index is never read or compared against. Since all other indices must be `head <= x < tail`, then we know that they all have the MSB set, so flipping the MSB will be the same as `x - (usize::MAX+1)/2` which must preserve the order of the queues.

It should be possible to implement here too, but it might not be super efficient with the task linked list

taiki-e commented 1 year ago

Thanks! Opened https://github.com/rust-lang/futures-rs/issues/2689 to track overflow issue.