kudzu
kudzu copied to clipboard
withoutboats
Is this correct?
Need to become more confident that implementation is actually concurrency safe and lacks UB. Currently I've just done very limited dummy testing that it doesn't obviously blow up (which it doesn't).
I'm sure there's also trivial UB of the sort that miri catches that is actually fine right now but is still UB and we need to work around it by writing the expressions slightly differently to satisfy the unsafe guidelines working group
I believe insert currently allows smuggling T: Sync + !Send items across threads, since the SkipList itself only requires T: Sync to share across threads. I think it needs to be:
unsafe impl<T: Send + Sync> Sync for SkipList<T> { }
I'm not sure if there's a similar problem with T: Send + !Sync, like sending some &mut SkipList to another thread and then getting &T from it. I suspect this is OK, since that's essentially the same as downgrading &mut T to &T in general.
I'll admit I always struggle to solve send/sync logic puzzles, but there's no way to go from &SkipList<T> to T, only to &T.. that is, this is a single ownership construct like Vec, not a shared ownership construct like Arc. I could be wrong!
but there's no way to go from
&SkipList<T>toT, only to&T
There is:
pub fn insert<'a>(&'a self, elem: T) -> Option<T>
This is both inserting a T from the current thread to a &self of unknown thread origin, and optionally returning any existing T that was in &self already. So in both directions, it's possible to move the ownership of an unsendable T across threads.
That said, I'm not sure if there's any realistic type with Sync but not Send. Perhaps there's something that could be shared across threads without trouble, but must be dropped on the same thread it was created due to some TLS or the like.
This is both inserting a T from the current thread to a &self of unknown thread origin, and optionally returning any existing T that was in &self already.
That's incorrect (and also why this library needs some docs)! This is the main difference between kudzu and other libraries: it does not support any sort of removal operation. It returns Some(T) when the object was already in the map, but it returns the value you tried to insert, not the value that's already there.
but it returns the value you tried to insert, not the value that's already there.
Ah, OK, that is indeed different and significant.
You do have IntoIterator for Set<T> though, which would let you get the T back out by value. The problem would also arise if you get around to adding map::IterMut (Item = (&K, &mut V)) for the value type in particular, or if you add the Entry API with &mut V access. Or even just dropping the SkipList will have sent every &mut T, once you TODO call destructors anyway.
You do have IntoIterator for Set<T> though, which would let you get the T back out by value.
This is true, and is probably a problem.
@withoutboats Already emailed you but might as well reply here too. I'm the author the Grand Concurrent Map Competition and kudzu causes heap corruption and a subsequent segfault on some machines. It works fine and dandy on everything up to 16C/32T machines but it dies consistently on the 96C/96T machine I got for benching. This leads me to believe that there is some bug that only occurs with heavy contention somewhere.
Can you provide more information about which architecture you're compiling for and also which revision of kudzu you're testing?
Sure! I am compiling for aarch64 aka ArmV8 and was using the latest from crates.io.
On Tue, Jul 2, 2019, 16:28 boats [email protected] wrote:
Can you provide more information about which architecture you're compiling for and also which revision of kudzu you're testing?
— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/withoutboats/kudzu/issues/4?email_source=notifications&email_token=AFANDB3CVV7GY2XFUKXCTODP5NQ2JA5CNFSM4H2ZHGNKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODZBO3ZI#issuecomment-507702757, or mute the thread https://github.com/notifications/unsubscribe-auth/AFANDBZIOMPTJFA26IUES4DP5NQ2JANCNFSM4H2ZHGNA .
I suspect this may have been the issue brought up on Reddit about the Relaxed load of the pointers, fixed in #9. If you have the ability, checking if the issue still exists in HEAD would be a great favor :) I don't have any ARM machines at all to test this on.
Will do. Testing takes a while and I will report back once I have results.
On Tue, Jul 2, 2019, 16:57 boats [email protected] wrote:
I suspect this may have been the issue brought up on Reddit about the Relaxed load of the pointers, fixed in #9 https://github.com/withoutboats/kudzu/pull/9. If you have the ability, checking if the issue still exists in HEAD would be a great favor :) I don't have any ARM machines at all to test this on.
— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/withoutboats/kudzu/issues/4?email_source=notifications&email_token=AFANDB6MH3IHO2YPGBNP47DP5NUFDA5CNFSM4H2ZHGNKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODZBRYVI#issuecomment-507714645, or mute the thread https://github.com/notifications/unsubscribe-auth/AFANDB4TFLSZGYZYVRGPZ6DP5NUFDANCNFSM4H2ZHGNA .
For the record, @xacrimon has said that changing all the orderings to SeqCst make the problem go away (but performance tanks). So it does seem to be an issue with atomics.
