Bug: index_gt::update releases an unacquired conditional lock under specific conditions, causing a data race

[yoonseok-kim]

Describe the bug

Hi, I have found another data race issue in index_gt::update.

USearch/include/usearch/index.hpp

Lines 4146 to 4154 in 13c3fd9

	// The trickiest part of update-heavy workloads is mitigating dead-locks
	// in connected nodes during traversal. A "good enough" solution would be
	// to skip concurrent access, assuming the other "close" node is gonna add
	// this one when forming reverse connections.
	bool failed_to_acquire = false;
	node_conditional_lock_t candidate_lock =
	node_try_conditional_lock_(candidate_slot, updated_slot != candidate_slot, failed_to_acquire);
	if (failed_to_acquire)
	continue;

index_gt::update uses conditional lock(node_try_conditional_lock_) instead of the hard lock(node_lock_) that index_gt::add use. When candidate_slot == updated_slot, the function deliberately skips atomic_set, but it still returns a node_conditional_lock_t whose destructor unconditionally calls atomic_reset.

USearch/include/usearch/index.hpp

Lines 3828 to 3841 in 13c3fd9

	struct node_conditional_lock_t {
	nodes_mutexes_t& mutexes;
	std::size_t slot;
	inline ~node_conditional_lock_t() noexcept {
	if (slot != std::numeric_limits<std::size_t>::max())
	mutexes.atomic_reset(slot);
	}
	};
	inline node_conditional_lock_t node_try_conditional_lock_(std::size_t slot, bool condition,
	bool& failed_to_acquire) const noexcept {
	failed_to_acquire = condition ? nodes_mutexes_.atomic_set(slot) : false;
	return {nodes_mutexes_, failed_to_acquire ? std::numeric_limits<std::size_t>::max() : slot};
	}

It clears the bit for a slot we never locked and can even unlock another thread’s live lock on the same node.
Eventually, two threads think they own the slot, they both mutate the same neighbors_ref_t buffer. it is data race.

For reference, index_gt::add never happen same problem because it always uses node_lock_, so only update suffers.

I’ve tried resolving this issue and submitted a bugfix PR.
I would appreciate it if you could take a look. :)

Steps to reproduce

1. Add 10,000 nodes (index_gt::add).
2. Update the same 10,000 nodes in parallel, modifying only their vector values (index_gt::update).
   The issue was reproduced in my environment with 16 threads, M = 32, and efConstruction = 128.
3. TSan sometimes detects a data race (non-deterministic, timing-dependent).

Expected behavior

index_gt::update is thread-safe.

USearch version

v2.21.2

Operating System

Red Hat Enterprise Linux release 8.6

Hardware architecture

x86

Which interface are you using?

C++ implementation

Contact Details

kys910524@gmail.com

Are you open to being tagged as a contributor?

• I am open to being mentioned in the project .git history as a contributor

Is there an existing issue for this?

• I have searched the existing issues

Code of Conduct

• I agree to follow this project's Code of Conduct

[yoonseok-kim]

Detailed scenario of how the issue occurs

struct node_conditional_lock_t {
    nodes_mutexes_t& mutexes;
    std::size_t slot;
    inline ~node_conditional_lock_t() noexcept {
        if (slot != std::numeric_limits<std::size_t>::max())
            mutexes.atomic_reset(slot);
    }
};

inline node_conditional_lock_t node_try_conditional_lock_(std::size_t slot, bool condition,
                                                          bool& failed_to_acquire) const noexcept {
    failed_to_acquire = condition ? nodes_mutexes_.atomic_set(slot) : false;
    return {nodes_mutexes_, failed_to_acquire ? std::numeric_limits<std::size_t>::max() : slot};
}

1. When candidate_slot == updated_slot, condition becomes false, so atomic_set is not called.`
2. Therefore, failed_to_acquire is set to false.
3. Since failed_to_acquire == false, the function returns {nodes_mutexes_, slot}.
4. In the destructor of node_conditional_lock_t, the slot is not std::numeric_limits<std::size_t>::max().
5. As a result, the destructor unconditionally calls `atomic_reset even though the slot was never locked.
   (If another thread was holding that lock, it ends up being unlocked.)

[yoonseok-kim]

Steps to reproduce

1. Add 10,000 nodes (index_gt::add).
2. Update the same 10,000 nodes in parallel, modifying only their vector values (index_gt::update).
   The issue was reproduced in my environment with 16 threads, M = 32, and efConstruction = 128.
3. TSan sometimes detects a data race (non-deterministic, timing-dependent).

Below is an example where tsan actually detected the data race.

• Thread T8: reads the size of a node’s neighbor list (read).
• Thread T3: appends a new neighbor to the node’s neighbor list (write).

(I will refer to this problematic node as node A.)

Thread T8

1205: WARNING: ThreadSanitizer: data race (pid=8056)
1205:   Read of size 4 at 0x724400052d0a by thread T8:
1205:     #0 unsigned int unum::usearch::misaligned_load<unsigned int>(void const*) /workspaces/dot/build.fedora43.asan/vcpkg_installed/project-target/include/usearch/index.hpp:209 (DotLife_AnnIndexUsearchRowidTest+0x2d8188) (BuildId: 295a900404f2e758ee036c3689020e29d9e908d0)
1205:     #1 unum::usearch::index_gt<float, unsigned long, unsigned int, std::allocator<char>, std::allocator<char> >::neighbors_ref_t::size() const /workspaces/dot/build.fedora43.asan/vcpkg_installed/project-target/include/usearch/index.hpp:2170 (DotLife_AnnIndexUsearchRowidTest+0x2d7c4f) (BuildId: 295a900404f2e758ee036c3689020e29d9e908d0)
1205:     #2 form_reverse_links_<float const*&, dot::life::ann_index_metric_t<(anonymous namespace)::mock_postings<dot::life::unsized_vector_codec<dot::life::primitive_codec<float> > >, unum::usearch::index_gt<float, long unsigned int, unsigned int>, dot::life::ann_index_updator_usearch_rowid<(anonymous namespace)::mock_postings<dot::life::unsized_vector_codec<dot::life::primitive_codec<float> > > > >&> /workspaces/dot/build.fedora43.asan/vcpkg_installed/project-target/include/usearch/index.hpp:3887 (DotLife_AnnIndexUsearchRowidTest+0x2a3304) (BuildId: 295a900404f2e758ee036c3689020e29d9e908d0)
1205:     #3 update<float const*, dot::life::ann_index_metric_t<(anonymous namespace)::mock_postings<dot::life::unsized_vector_codec<dot::life::primitive_codec<float> > >, unum::usearch::index_gt<float, long unsigned int, unsigned int>, dot::life::ann_index_updator_usearch_rowid<(anonymous namespace)::mock_postings<dot::life::unsized_vector_codec<dot::life::primitive_codec<float> > > > >&, dot::life::ann_index_updator_usearch_rowid<(anonymous namespace)::mock_postings<dot::life::unsized_vector_codec<dot::life::primitive_codec<float> > > >::add_point(uint64_t, void const*)::<lambda(member_ref_t)>&> /workspaces/dot/build.fedora43.asan/vcpkg_installed/project-target/include/usearch/index.hpp:2988 (DotLife_AnnIndexUsearchRowidTest+0x29dcdf) (BuildId: 295a900404f2e758ee036c3689020e29d9e908d0)
...

Thread T3

1205:   Previous write of size 4 at 0x724400052d0a by thread T3:
1205:     #0 void unum::usearch::misaligned_store<unsigned int>(void*, unsigned int) /workspaces/dot/build.fedora43.asan/vcpkg_installed/project-target/include/usearch/index.hpp:202 (DotLife_AnnIndexUsearchRowidTest+0x2d820b) (BuildId: 295a900404f2e758ee036c3689020e29d9e908d0)
1205:     #1 unum::usearch::index_gt<float, unsigned long, unsigned int, std::allocator<char>, std::allocator<char> >::neighbors_ref_t::push_back(unsigned int) /workspaces/dot/build.fedora43.asan/vcpkg_installed/project-target/include/usearch/index.hpp:2179 (DotLife_AnnIndexUsearchRowidTest+0x2d8301) (BuildId: 295a900404f2e758ee036c3689020e29d9e908d0)
1205:     #2 form_reverse_links_<float const*&, dot::life::ann_index_metric_t<(anonymous namespace)::mock_postings<dot::life::unsized_vector_codec<dot::life::primitive_codec<float> > >, unum::usearch::index_gt<float, long unsigned int, unsigned int>, dot::life::ann_index_updator_usearch_rowid<(anonymous namespace)::mock_postings<dot::life::unsized_vector_codec<dot::life::primitive_codec<float> > > > >&> /workspaces/dot/build.fedora43.asan/vcpkg_installed/project-target/include/usearch/index.hpp:3894 (DotLife_AnnIndexUsearchRowidTest+0x2a33ab) (BuildId: 295a900404f2e758ee036c3689020e29d9e908d0)
1205:     #3 update<float const*, dot::life::ann_index_metric_t<(anonymous namespace)::mock_postings<dot::life::unsized_vector_codec<dot::life::primitive_codec<float> > >, unum::usearch::index_gt<float, long unsigned int, unsigned int>, dot::life::ann_index_updator_usearch_rowid<(anonymous namespace)::mock_postings<dot::life::unsized_vector_codec<dot::life::primitive_codec<float> > > > >&, dot::life::ann_index_updator_usearch_rowid<(anonymous namespace)::mock_postings<dot::life::unsized_vector_codec<dot::life::primitive_codec<float> > > >::add_point(uint64_t, void const*)::<lambda(member_ref_t)>&> /workspaces/dot/build.fedora43.asan/vcpkg_installed/project-target/include/usearch/index.hpp:2988 (DotLife_AnnIndexUsearchRowidTest+0x29dcdf) (BuildId: 295a900404f2e758ee036c3689020e29d9e908d0)
...

Both T8 and T3 are updating other node that treats node A as a neighbor. In the code, it looks as if form_reverse_links_ correctly acquires a lock (node_lock_) on node A. However, the lock on node A can be unintentionally released by the thread that is updating node A itself. At that moment, either T8 or T3 may acquire the lock, and both threads end up accessing and mutating node A’s neighbor list concurrently, leading to a data race.

After applying PR#681, I confirmed that this data race no longer occurs.