Hang with AtomicMemory and single-thread

[vchuravy]

A smaller reproducer that deadlocks:

 julia -e "a=AtomicMemory{NTuple{3,Int64}}(undef,2);@atomic a[1] = (-1,-1,-1); @atomic a[2]=(-1,-1,-1);"

Originally posted by @bbrehm in #58993

This seems rather concerning, since it occurs on a single thread, it reproduced for me on 1.12-rc1.

julia> a=AtomicMemory{NTuple{3,Int64}}(undef,2)
2-element AtomicMemory{Tuple{Int64, Int64, Int64}}:
 (0, 0, 0)
 (0, 0, 0)

julia> @atomic a[2]=(-1,-1,-1)
(-1, -1, -1)

julia> @atomic a[1]=(-1,-1,-1)
(-1, -1, -1)

julia> @atomic a[2]=(-1,-1,-1)
^C^C^C^C^CWARNING: Force throwing a SIGINT

[bbrehm]

#58997 should fix this as well, and is already planned for backporting, right?

I constructed the example as a reproducer of #58993 : The offset calculations for the locks in AtomicMemory are wrong, and sometimes julia believes that a lock is placed at the point where data is placed.

So I put a bit-pattern in a[1] that looks like a taken lock, and then @atomic a[2] will spin forever on trying to access that lock.

The entire issue is quite concerning, since (even read-only) access can corrupt memory (even when running single-threaded):

julia> A=0x4242424242424242; a=AtomicMemory{NTuple{3,UInt64}}(undef,2);@atomic a[1] = (A,0,A); display(( (@atomic a[1]), (@atomic a[2]), (@atomic a[1])));
((0x4242424242424242, 0x0000000000000000, 0x4242424242424242), (0x0000000000000000, 0x0000000000000000, 0x0000000000000000), (0x4242424242424242, 0x0000000000000000, 0x4242424200000000))

I would not be terribly surprised if some programs existed where this leads to an exploitable security vuln; but that would be very specific to the targeted program, and a bit of work.

The original issue demonstrated how this can lead to pointer corruption: We can relatively reliably zero the least significant 32 bits of an object reference.

[bbrehm]

Damn, #58997 doesn't fix it for me :(

[bbrehm]

Best I can tell, the following is the memory layouts on 1.11.6:

julia> t=NTuple{33, Int8};a=AtomicMemory{t}(undef, 1); g(a)=@inbounds a[101]; @code_llvm g(a)
; Function Signature: g(GenericMemory{:atomic, NTuple{33, Int8}, Core.AddrSpace{Core}(0x00)})
;  @ REPL[1]:1 within `g`
define void @julia_g_881(ptr noalias nocapture noundef nonnull sret([33 x i8]) align 1 dereferenceable(33) %sret_return, ptr noundef nonnull align 8 dereferenceable(16) %"a::GenericMemory") #0 {
top:
  %aggregate_load_box = alloca [33 x i8], align 1
; ┌ @ essentials.jl:399 within `getindex`
   %.data_ptr = getelementptr inbounds { i64, ptr }, ptr %"a::GenericMemory", i64 0, i32 1
   %0 = load ptr, ptr %.data_ptr, align 8
   %1 = getelementptr inbounds [33 x i8], ptr %0, i64 100
   %2 = getelementptr inbounds [33 x i8], ptr %0, i64 100, i64 16
   call void @jl_lock_field(ptr nonnull %1)
   call void @llvm.memcpy.p0.p0.i64(ptr noundef nonnull align 1 dereferenceable(33) %aggregate_load_box, ptr noundef nonnull align 1 dereferenceable(33) %2, i64 33, i1 false)
   call void @jl_unlock_field(ptr nonnull %1)
   call void @llvm.memcpy.p0.p0.i64(ptr noundef nonnull align 1 dereferenceable(33) %sret_return, ptr noundef nonnull align 1 dereferenceable(33) %aggregate_load_box, i64 33, i1 false)
   ret void
; └
}
julia> sizeof(a)
49

This is horribly broken: The lock sits in the middle of the item.

On master, we have

julia> t=NTuple{33, Int8};a=AtomicMemory{t}(undef, 1); g(a)=@inbounds a[101]; @code_llvm g(a)
; Function Signature: g(GenericMemory{:atomic, NTuple{33, Int8}, Core.AddrSpace{Core}(0x00)})
;  @ REPL[1]:1 within `g`
define void @julia_g_1319(ptr noalias nocapture noundef nonnull sret([33 x i8]) align 1 dereferenceable(33) %sret_return, ptr noundef nonnull align 8 dereferenceable(16) %"a::GenericMemory") local_unnamed_addr #0 {
top:
  %0 = alloca [33 x i8], align 1
; ┌ @ essentials.jl:398 within `getindex`
   %memory_data_ptr = getelementptr inbounds nuw i8, ptr %"a::GenericMemory", i64 8
   %memory_data = load ptr, ptr %memory_data_ptr, align 8
   %memoryref_data = getelementptr inbounds nuw i8, ptr %memory_data, i64 3300
   %1 = getelementptr inbounds nuw i8, ptr %memory_data, i64 3316
   call void @jl_lock_field(ptr nonnull %memoryref_data)
   call void @llvm.memcpy.p0.p0.i64(ptr noundef nonnull align 1 dereferenceable(33) %0, ptr noundef nonnull align 1 dereferenceable(33) %1, i64 33, i1 false)
   call void @jl_unlock_field(ptr nonnull %memoryref_data)
   call void @llvm.memcpy.p0.p0.i64(ptr noundef nonnull align 1 dereferenceable(33) %sret_return, ptr noundef nonnull align 1 dereferenceable(33) %0, i64 33, i1 false)
   ret void
; └
}
julia> sizeof(a)
49

This is also horribly broken: The lock overlaps with the trailing 16 bytes of the previous item.

(oh yes, we also pass an invalid-because-misaligned jl_mutex* to jl_lock_field)

As far as I can tell, AtomicMemory with locks never ever worked. Not just in the sense of "be atomic", but in the sense of "when single-threaded, have a good chance of reading data that was actually written, without deadlocking", in the sense of "anybody has ever used this successfully in a unit test".

I cannot even unambiguously figure out the intended memory layout of AtomicMemory. Let's assume that somehow the pointer calculations are buggy code, but the allocation size is correct. I get 49 bytes per element for the above, so due to alignment constraints, the intended layout must be:

Have a bunch of locks. Then have a bunch of items. (it cannot be first items, then locks, due to alignment)

So the locks are not interleaved with the items (one extra cache line touched), nor are they padded (concurrent read-only access to a[1] and a[2] leads to two cores playing tug-of-war with the cache-line that spans the first 4 locks).

I think we should take the time to reconsider locking strategies. Nobody relies on any behavior yet (since the feature "AtomicMemory of arbitrary datatypes via locks" afaict never existed); we could quickly backport "throw an error when somebody tries to instantiate such a thing with non-zero length" to 1.11; and, in order to not delay 1.12, do the same.

Then we should have a discussion and benchmarks about alternatives:

1. Don't support that, just error.
2. RCU (read-copy-update), i.e. just box the item and do atomics on the pointers. I don't hate that! We have a garbage collector, after all.
3. Interleave locks with items, or have them at the end?
4. Use a sane lock that doesn't take exclusive control of a cache-line for read access. I.e. use a seqlock.
5. Don't have one lock per item. Instead have some global array of seqlocks; and which of these is responsible for an item depends on the address of the item. Hence, many of these locks will serve many different items. We can do that because these are what https://docs.julialang.org/en/v1/devdocs/locks/#Locks calls "leaf-locks". As a bonus, this should mostly avoid false sharing between adjacent AtomicMemory elements, at the cost of some probabilistic false sharing or false contention between elements of different AtomicMemory instances. I think this would be my preferred approach.

If we go for (5), we have an additional advantage: AtomicMemory becomes superfluous, because it does not affect memory layout anymore, and we can simply support @atomic ops on any Memory, just like in java via VarHandle. (Of course for us, concurrent access with at least one writer and at least one non-atomic would be "UB, spawn bats in your nose or corrupt memory and pop a shell", not "hard to predict and buggy, but there are limits on what you'll see")

[vtjnash]

I implemented 3, since that was only a 2 line fix which makes it most concise. I agree these should consider using seqlock, since right now they have quite a bit of overhead for reading (it is the same for mutable struct fields), but that is a minor implementation change since it would occupy the same amount of memory. The other alternative is to change this lock to a single byte, which is more space efficient than a seqlock, but less efficient at readonly use.

[bbrehm]

Also don't forget alignment -- AtomicMemory is wrong even in absence of internal mutextes:

julia> a=AtomicMemory{NTuple{3, Int8}}(undef, 2); @atomic a[1]=ntuple(i->1, 3); @atomic a[2] = ntuple(i->1, 3);  @atomic a[1]=ntuple(i->1, 3); a
2-element AtomicMemory{Tuple{Int8, Int8, Int8}}:
 (1, 1, 1)
 (0, 1, 1)

The store to a[1] ends up with store atomic i32 %1, ptr %memoryref_data5 seq_cst, align 4 and zeros the first byte of a[2].

[vtjnash]

As far as I can tell, AtomicMemory with locks never ever worked

FWIW, these bugs were introduced later by well-meaning (but incorrect) PRs. Only the GC segfault was in the original PR, so it originally should have worked with isbits data of any size, and those only stopped working later on.

[vtjnash]

Fixed by #58997