Skip to content

/rust

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

BinaryHeap is not exception safe #25842

Closed
bluss opened this Issue May 27, 2015 · 5 comments

Comments

Assignees
No one assigned
Labels
I-nominated T-libs
Projects
None yet
Milestone
No milestone
4 participants
@bluss @Gankro @alexcrichton @rust-highfive
@bluss
Copy link
Contributor

bluss commented May 27, 2015

BinaryHeap is using zeroed() and may not be exception safe. I.e. it is in an inconsistent state after being recovered after panic. See issue #25662 and others.

Relevant code is BinaryHeap::sift_up, sift_down_range

cc @cmr
@bluss

This comment has been minimized.

Sign in to view
Copy link
Contributor Author

bluss commented May 27, 2015

My immediate ideas are one of

  • Use PPYP and set vector length to zero temporarily. Panicing in comparison functions will leak all elements in the heap
  • Use more swaps
@bluss

This comment has been minimized.

Sign in to view
Copy link
Contributor Author

bluss commented May 27, 2015

@Gankro's got the idea: https://botbot.me/mozilla/rust-internals/2015-03-24/?msg=34945483&page=6
@Gankro

This comment has been minimized.

Sign in to view
Copy link
Contributor

Gankro commented May 27, 2015

Long ago I suggested two other strategies:

  • A two-pass phase where you do all comparisons first, then once you've found the Final Destination you actually do the swaps (which requires no untrusted code to run).
  • A panic guard which on drop puts the "working" element back in the "uninit" location in the array
@alexcrichton

This comment has been minimized.

Sign in to view
Copy link
Member

alexcrichton commented May 27, 2015

triage: I-nominated, T-libs

@rust-highfive rust-highfive added the I-nominated label May 27, 2015

@alexcrichton alexcrichton added the T-libs label May 27, 2015

@bluss

This comment has been minimized.

Sign in to view
Copy link
Contributor Author

bluss commented May 27, 2015

I'm trying gankro's panic guard idea.

bluss pushed a commit to bluss/rust that referenced this issue May 28, 2015

Ulrik Sverdrup
collections: Make BinaryHeap panic safe in sift_up / sift_down 
Use a struct called Hole that keeps track of an invalid location
in the vector and fills the hole on drop.

I include a run-pass test that the current BinaryHeap fails, and the new
one passes.

Fixes rust-lang#25842
5f44f5b

@bluss bluss referenced this issue May 28, 2015

Merged

collections: Make BinaryHeap panic safe in sift_up / sift_down #25856

bluss pushed a commit to bluss/rust that referenced this issue May 28, 2015

Ulrik Sverdrup
collections: Make BinaryHeap panic safe in sift_up / sift_down 
Use a struct called Hole that keeps track of an invalid location
in the vector and fills the hole on drop.

I include a run-pass test that the current BinaryHeap fails, and the new
one passes.

Fixes rust-lang#25842
b221853

bluss pushed a commit to bluss/rust that referenced this issue May 28, 2015

Ulrik Sverdrup
collections: Make BinaryHeap panic safe in sift_up / sift_down 
Use a struct called Hole that keeps track of an invalid location
in the vector and fills the hole on drop.

I include a run-pass test that the current BinaryHeap fails, and the new
one passes.

Fixes rust-lang#25842
c41a5cc

bluss pushed a commit to bluss/rust that referenced this issue May 28, 2015

Ulrik Sverdrup
collections: Make BinaryHeap panic safe in sift_up / sift_down 
Use a struct called Hole that keeps track of an invalid location
in the vector and fills the hole on drop.

I include a run-pass test that the current BinaryHeap fails, and the new
one passes.

Fixes rust-lang#25842
5249cbb

bors added a commit that referenced this issue May 28, 2015

@bors
Auto merge of #25856 - bluss:binary-heap-hole, r=Gankro 
collections: Make BinaryHeap panic safe in sift_up / sift_down

Use a struct called Hole that keeps track of an invalid location
in the vector and fills the hole on drop.

I include a run-pass test that the current BinaryHeap fails, and the new
one passes.

NOTE: The BinaryHeap will still be inconsistent after a comparison fails. It will
not have the heap property. What we fix is just that elements will be valid
values.

This is actually a performance win -- the new code does not bother to write in `zeroed()`
values in the holes, it just leaves them as they were.

Net result is something like a 5% decrease in runtime for `BinaryHeap::from_vec`. This
can be further improved by using unchecked indexing (I confirmed it makes a difference,
not a surprise with the non-sequential access going on), but let's leave that for another PR.
Safety first 😉 

Fixes #25842
Loading status checks…
efebe45

@bors bors closed this in #25856 May 28, 2015

XMPPwocky added a commit to XMPPwocky/rust that referenced this issue May 29, 2015

Ulrik Sverdrup @XMPPwocky
collections: Make BinaryHeap panic safe in sift_up / sift_down 
Use a struct called Hole that keeps track of an invalid location
in the vector and fills the hole on drop.

I include a run-pass test that the current BinaryHeap fails, and the new
one passes.

Fixes rust-lang#25842
4b74286

alexcrichton added a commit to alexcrichton/rust that referenced this issue Jun 10, 2015

Ulrik Sverdrup @alexcrichton
collections: Make BinaryHeap panic safe in sift_up / sift_down 
Use a struct called Hole that keeps track of an invalid location
in the vector and fills the hole on drop.

I include a run-pass test that the current BinaryHeap fails, and the new
one passes.

Fixes rust-lang#25842
2cc6e8f
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.