This repo is completely unsound, code like [1] is pervasive and demonstrates a total misunderstanding of what guarantees are provided -- or, really, not provided -- by "atomic" reads of unsafe.Pointer values. Data races everywhere!
Not safe, do not pass go, do not collect $200, absolutely do not use.
Thank you for debunking it so I didn't have to. I don't think I've ever seen someone post a low-level/concurrent data structure in Go that wasn't wildly unsound, so I assumed this was too.
Any later mutation (for example `setValue`) writes through those shared pointers, so readers and historical snapshots are modified concurrently -- invalid, data race, memory model violation
Calling it twice on the same index flips the bit back to 0. During branch-creation on insert and during delete, this function is invoked multiple times on the same index, clearing a bit that should remain set and leaving orphaned children.
---
Invalid assumptions re: interior pointers
Only the root pointer is read with `atomic.LoadPointer`. All deeper fields like `children[pos]`, `bitmap`, and the byte-slice keys/values, are accessed directly after a successful CAS. Readers therefore race with writers that mutate these fields in place -- race condition, memory model violation, etc.
If another goroutine has already swapped in a different copy of `curr` (and mutated it) the CAS still succeeds because the pointer value is unchanged, merging incompatible sub-tries and corrupting the data
---
Use-after-free in sync.Pool
On CAS failure the freshly built `nodeCopy` is immediately returned to a `sync.Pool` -- undefined behavior
cMap.pool.PutNode(nodeCopy) // may race with outstanding readers
Other goroutines still holding references to that node can now access a reclaimed object, oops.
---
K/V Aliasing
Keys and values (both []byte slices, which are not safe for concurrent r/w access) are stored by reference, a mistake:
n.setKey(key)
n.setValue(value)
If the caller mutates those slices later (or concurrently in another goroutine), data races ahoy
---
Reader panics, etc.
- `getRecursive` accesses `children[pos]` without bounds or nil checks, concurrent shrink can make `pos` invalid
- `GetIndex` allows a negative `shiftSize` once `level >= 7` with `chunkSize = 5`, producing nonsense indices and potential slice-out-of-bounds
Hi, thank you for the in depth response. I really needed to hear these things. I have gone ahead and addressed almost all of the issues that you pointed out. I updated the root to be the only point for compare and swap and on mutations I do a clone instead of mutating the shared pointer. I updated set bit from xor to set and have an explicit clearbit fn for deletions. I also updated k/v aliasing to copy slices on write so that old copies do not share ref to same slice. The node pool has been removed completely for the time being as well. I added in additional tests to test for these cases and added in more concurrent tests as well. this was huge feedback and I really appreciate it.
> both []byte slices, which are not safe for concurrent r/w access
You must clone the slice on both write and read, right?
I get that cloning incurs a memory allocation and a copy operation, but this is the price for safety when concurrent access is possible or your data may be bodified outside your structure.
You could probably intern immutable keys, or avoid storing if keys already exist and are immutable, or use an object pool (like sync.Pool) to reduce allocations if this happens at scale. Anything else I am missing?
Performance comparisons are made against go sync.Map, with cmapv2 on par or sometimes exceeding is on different workloads. It is both lock-free and thread safe, using atomic operations. It also supports sharding out of the box. cmapv2 with 10m k/v pairs where keys and values are 64bytes was able to achieve 1.5m w/s and 3m r/s.
This repo is completely unsound, code like [1] is pervasive and demonstrates a total misunderstanding of what guarantees are provided -- or, really, not provided -- by "atomic" reads of unsafe.Pointer values. Data races everywhere!
Not safe, do not pass go, do not collect $200, absolutely do not use.
[1] https://github.com/sirgallo/cmapv2/blob/280e3017ae4ba212f6f8...
Thank you for debunking it so I didn't have to. I don't think I've ever seen someone post a low-level/concurrent data structure in Go that wasn't wildly unsound, so I assumed this was too.
Go is made by Google. Do they not have someone writing an equivalent of Java.util.concurrent.ConcurrentHashMap?
They do, there's a concurrent hashmap in the standard library. It doesn't get posted here or on Reddit, though.
There are many good implementations.
Be more specific? OK
---
CopyNode broken
`CopyNode` duplicates only the parent; every child pointer is still shared
https://github.com/sirgallo/cmapv2/blob/main/node.go#L11-L17Any later mutation (for example `setValue`) writes through those shared pointers, so readers and historical snapshots are modified concurrently -- invalid, data race, memory model violation
---
Bitmap corruption
`SetBit` uses XOR rather than “set”:
https://github.com/sirgallo/cmapv2/blob/main/utils.go#L41-L4...Calling it twice on the same index flips the bit back to 0. During branch-creation on insert and during delete, this function is invoked multiple times on the same index, clearing a bit that should remain set and leaving orphaned children.
---
Invalid assumptions re: interior pointers
Only the root pointer is read with `atomic.LoadPointer`. All deeper fields like `children[pos]`, `bitmap`, and the byte-slice keys/values, are accessed directly after a successful CAS. Readers therefore race with writers that mutate these fields in place -- race condition, memory model violation, etc.
https://github.com/sirgallo/cmapv2/blob/main/operation.go#L5...---
All xxxRecursive functions rely on those invalid interior pointer assumptions
Sequence in `putRecursive` / `deleteRecursive` is
https://github.com/sirgallo/cmapv2/blob/main/operation.go#L1...If another goroutine has already swapped in a different copy of `curr` (and mutated it) the CAS still succeeds because the pointer value is unchanged, merging incompatible sub-tries and corrupting the data
---
Use-after-free in sync.Pool
On CAS failure the freshly built `nodeCopy` is immediately returned to a `sync.Pool` -- undefined behavior
https://github.com/sirgallo/cmapv2/blob/main/operation.go#L1...Other goroutines still holding references to that node can now access a reclaimed object, oops.
---
K/V Aliasing
Keys and values (both []byte slices, which are not safe for concurrent r/w access) are stored by reference, a mistake:
If the caller mutates those slices later (or concurrently in another goroutine), data races ahoy---
Reader panics, etc.
Hi, thank you for the in depth response. I really needed to hear these things. I have gone ahead and addressed almost all of the issues that you pointed out. I updated the root to be the only point for compare and swap and on mutations I do a clone instead of mutating the shared pointer. I updated set bit from xor to set and have an explicit clearbit fn for deletions. I also updated k/v aliasing to copy slices on write so that old copies do not share ref to same slice. The node pool has been removed completely for the time being as well. I added in additional tests to test for these cases and added in more concurrent tests as well. this was huge feedback and I really appreciate it.
> both []byte slices, which are not safe for concurrent r/w access
You must clone the slice on both write and read, right?
I get that cloning incurs a memory allocation and a copy operation, but this is the price for safety when concurrent access is possible or your data may be bodified outside your structure.
You could probably intern immutable keys, or avoid storing if keys already exist and are immutable, or use an object pool (like sync.Pool) to reduce allocations if this happens at scale. Anything else I am missing?
> You must clone the slice on both write and read, right?
I haven't looked at the code, but that doesn't make sense to me. If you can't read the slice safely, you also can't clone it safely.
So, what are the solutions if they are indeed not safe to do read / write concurrently?
Like okay, I read "both []byte slices, which are not safe for concurrent r/w access", but then, what is the solution? If the claim is indeed true.
Some options:
- Make sure no one mutates the slice ever, making it safe to read
- Guarding the slice behind a mutex, requiring anyone who reads or writes it to lock the mutex first
- Using some kind of thread-safe slice implementation
Performance comparisons are made against go sync.Map, with cmapv2 on par or sometimes exceeding is on different workloads. It is both lock-free and thread safe, using atomic operations. It also supports sharding out of the box. cmapv2 with 10m k/v pairs where keys and values are 64bytes was able to achieve 1.5m w/s and 3m r/s.
I've been using this one for years, can you do comparisons against it?
https://github.com/cornelk/hashmap
Another good comparison would be against https://pkg.go.dev/github.com/puzpuzpuz/xsync/v3#Map
definitely, I can expand my comparisons and benchmarks
Honestly, if you're better than the rest, I would suggest collaborating with the existing solutions.
yes I can take a look, thanks for passing that along
Looks interesting, it would be nice to have the performance comparisons front and center on the readme.
sounds good, they are a bit hidden right now. also am most likely going to update the other docs.
Is it anywhere close to swisstables?
No because swisstables generally don't do concurrency (i.e. concurrency ==> atomics which are inherently more expensive due to HW reasons).