4 ms·

Be more specific? OK --- CopyNode broken `CopyNode` duplicates only the parent; every child pointer is still shared nodeCopy.setChildren(make([]*node, l

by kiitos 1y ago

Be more specific? OK --- CopyNode broken `CopyNode` duplicates only the parent; every child pointer is still shared nodeCopy.setChildren(make([]*node, len(n.children))) copy(nodeCopy.children, n.children) // pointers reused https://github.com/sirgallo/cmapv2/blob/main/node.go#L11-L17 https://github.com/sirgallo/cmapv2/blob/main/node.go#L11-L17 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 --- Bitmap corruption `SetBit` uses XOR rather than “set”: func SetBit(bitmap uint32, position int) uint32 { return bitmap ^ (1 << position) } https://github.com/sirgallo/cmapv2/blob/main/utils.go#L41-L46 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. pos := cMap.getPosition(node.Bitmap(), hash, level) if node.Child(pos).IsLeaf() && bytes.Equal(key, node.Child(pos).Key()) { return node.Child(pos).Value() } https://github.com/sirgallo/cmapv2/blob/main/operation.go#L59-L67 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 1. `curr := atomic.LoadPointer(ptr)` 2. Build `nodeCopy` 3. Recurse; grandchildren are mutated in place 4. `atomic.CompareAndSwap(ptr, curr, nodeCopy)` https://github.com/sirgallo/cmapv2/blob/main/operation.go#L18-L57 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 cMap.pool.PutNode(nodeCopy) // may race with outstanding readers https://github.com/sirgallo/cmapv2/blob/main/operation.go#L119-L126 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: 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

johnisgood 1y ago
> 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?
- sapiogram 1y ago
  > 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.
  - johnisgood 1y ago
    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.
    - sapiogram 1y ago
      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
      - sirgallo 1y ago
        I went with option 1. On a mutation, I do a complete node copy where I also copy the key/value slices. When I set a child node for the first time or update a child, I create a branch new leaf node with a copy of the key/value. This way previous nodes maintain the original copy.

by kiitos 1y ago

johnisgood 1y ago

> 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?

sapiogram 1y ago
> 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.
- johnisgood 1y ago
  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.
  - sapiogram 1y ago
    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
    - sirgallo 1y ago
      I went with option 1. On a mutation, I do a complete node copy where I also copy the key/value slices. When I set a child node for the first time or update a child, I create a branch new leaf node with a copy of the key/value. This way previous nodes maintain the original copy.