DescriptorTable store descriptors in deterministic order#3614
Merged
sporksmith merged 1 commit intoshadow:mainfrom Jun 26, 2025
Merged
DescriptorTable store descriptors in deterministic order#3614sporksmith merged 1 commit intoshadow:mainfrom
sporksmith merged 1 commit intoshadow:mainfrom
Conversation
Contributor
Author
|
This also affects |
robgjansen
approved these changes
Jun 26, 2025
Member
robgjansen
left a comment
There was a problem hiding this comment.
Oops!
Maybe we should search for other internal uses of HashMap, since it seems to commonly cause determinism problems for us.
Contributor
Author
Yeah, I did that locally to some other ones that looked suspicious, but it didn't seem to help the particular determinism issues I'm running into. Maybe I still ought to clean up and merge them though to eliminate them from future scrutiny/trouble. |
Previously we were returning them in the `HashMap`'s arbitrary order, and then in `SyscallHandler::close_range` closing descriptors and pushing callbacks in that arbitrary order. Changing the data structure to `BTreeMap` ensures we process the descriptors in a deterministic (sorted) order. Alternatively we could just sort the vector returned by `DescriptorTable::remove_range`, but using a sorted data structure in the first place will make it harder for future subtle bugs of this nature to sneak back in. This seems to fix the nondeterministic scheduling (presumably due to callbacks being called in different order) and nondeterministic file descriptor assignments observed in shadow#3610.
79df1d4 to
e136c92
Compare
sporksmith
added a commit
to sporksmith/shadow
that referenced
this pull request
Jun 26, 2025
sporksmith
added a commit
to sporksmith/shadow
that referenced
this pull request
Jun 28, 2025
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
2 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Previously we were storing them in the
HashMap's arbitrary order, and them in that arbitrary orderDescriptorTable::remove_allandDescriptorTable::remove_range. Callers of both then close the descriptors and push callbacks in that arbitrary order..Changing the data structure to
BTreeMapensures we process the descriptors in a deterministic (sorted) order. Alternatively we could just sort the descriptors returned byDescriptorTable::remove_rangeandDescriptorTable::remov_all, but using a sorted data structure in the first place will make it harder for future subtle bugs of this nature to sneak back in.This seems to fix some of the nondeterministic scheduling (presumably due to callbacks being called in different order) and nondeterministic file descriptor assignments observed in #3610. Unfortunately not all of it though, and it's difficult to be sure whether it's actually making a difference due to the, err, nondeterministic nondeterminism.