Repository: oneapi-src/oneTBB (language: python)

Issue:
Deadlock in tbb::concurrent_vector
# Summary
Deadlock in tbb::concurrent_vector occurs in simplest example

# Version
2021.13

# Environment
The following information is important:
* Intel Xeon Gold 6248R CPU
* Windows 10 Enterprise LTSC
* Microsoft Visual Studio Version 17.9.7

# Observed Behavior
deadlock occurs in simplest example
![deadlock](https://github.com/user-attachments/assets/d9758df4-831d-4417-aec5-bdaaa115f057)

# Expected Behavior
absence of deadlock

# Steps To Reproduce
Code example

#include "random"
#include "oneapi/tbb/parallel_for.h"
#include "oneapi/tbb/concurrent_vector.h"

std::mt19937_64 gen;

int main()
{
    constexpr int max_grow_by = 32;
    constexpr int n_inserts = 1024;
    constexpr int n_repits = 1024*128;// *1024;
    auto rand = std::bind(std::uniform_int_distribution <int>{1, max_grow_by }, std::ref(gen));

    std::vector<int> n_grow_by(n_inserts);
    for (int iter = 0; iter < n_repits; ++iter) {
        std::generate(n_grow_by.begin(), n_grow_by.end(), rand);
        tbb::concurrent_vector<double> vec;
        tbb::parallel_for<int>(0, n_inserts, [&](int i) {
            vec.grow_by(n_grow_by[i]);
        });
    }

    return 0;
}



Discussion / hints:

Fix patch:
diff --git a/include/oneapi/tbb/concurrent_vector.h b/include/oneapi/tbb/concurrent_vector.h
index 2a2cb1e4bf..27cdc47355 100644
--- a/include/oneapi/tbb/concurrent_vector.h
+++ b/include/oneapi/tbb/concurrent_vector.h
@@ -1,5 +1,5 @@
 /*
-    Copyright (c) 2005-2022 Intel Corporation
+    Copyright (c) 2005-2024 Intel Corporation
 
     Licensed under the Apache License, Version 2.0 (the "License");
     you may not use this file except in compliance with the License.
@@ -593,7 +593,7 @@ class concurrent_vector
 
             segment_type disabled_segment = nullptr;
             if (table[0].compare_exchange_strong(disabled_segment, new_segment)) {
-                this->extend_table_if_necessary(table, 0, first_block_size);
+                this->extend_table_if_necessary(table, /*start_index*/0, /*end_index*/first_block_size);
                 for (size_type i = 1; i < first_block; ++i) {
                     table[i].store(new_segment, std::memory_order_release);
                 }
@@ -826,8 +826,8 @@ class concurrent_vector
 
     template <typename... Args>
     iterator internal_grow( size_type start_idx, size_type end_idx, const Args&... args ) {
-        this->assign_first_block_if_necessary(this->segment_index_of(end_idx - 1) + 1);
         size_type seg_index = this->segment_index_of(end_idx - 1);
+        this->assign_first_block_if_necessary(seg_index + 1);
         segment_table_type table = this->get_table();
         this->extend_table_if_necessary(table, start_idx, end_idx);
 
diff --git a/include/oneapi/tbb/detail/_segment_table.h b/include/oneapi/tbb/detail/_segment_table.h
index 1a31d8a17d..7fbf1cc0f9 100644
--- a/include/oneapi/tbb/detail/_segment_table.h
+++ b/include/oneapi/tbb/detail/_segment_table.h
@@ -1,5 +1,5 @@
 /*
-    Copyright (c) 2005-2022 Intel Corporation
+    Copyright (c) 2005-2024 Intel Corporation
 
     Licensed under the Apache License, Version 2.0 (the "License");
     you may not use this file except in compliance with the License.
@@ -260,34 +260,49 @@ class segment_table {
         }
     }
 
+    void destroy_and_deallocate_table(segment_table_type table, size_type num_segments) {
+        auto& alloc = get_allocator();
+        for (size_type seg_idx = 0; seg_idx < num_segments; ++seg_idx) {
+            segment_table_allocator_traits::destroy(alloc, &table[seg_idx]);
+        }
+        segment_table_allocator_traits::deallocate(alloc, table, num_segments);
+    }
+
     void clear_table() {
         segment_table_type current_segment_table = get_table();
         if (current_segment_table != my_embedded_table) {
             // If the active table is not the embedded one - deallocate the active table
-            for (size_type i = 0; i != pointers_per_long_table; ++i) {
-                segment_table_allocator_traits::destroy(my_segment_table_allocator, &current_segment_table[i]);
-            }
-
-            segment_table_allocator_traits::deallocate(my_segment_table_allocator, current_segment_table, pointers_per_long_table);
+            destroy_and_deallocate_table(current_segment_table, pointers_per_long_table);
             my_segment_table.store(my_embedded_table, std::memory_order_relaxed);
             zero_table(my_embedded_table, pointers_per_embedded_table);
         }
     }
 
     void extend_table_if_necessary(segment_table_type& table, size_type start_index, size_type end_index) {
-        // extend_segment_table if an active table is an embedded table
-        // and the requested index is not in the embedded table
+        // Extend segment table if an active table is an embedded one and the requested index is
+        // outside it
         if (table == my_embedded_table && end_index > embedded_table_size) {
             if (start_index <= embedded_table_size) {
+                // More than one thread can get here: the one that has assigned the first block and
+                // is in the process of allocating it now, and the one that saw the first block has
+                // been assigned already, but not yet allocated. This latter thread decides not to
+                // wait for the first one and extend the table itself.
                 try_call([&] {
-                    table = self()->allocate_long_table(my_embedded_table, start_index);
-                    // It is possible that the table was extended by the thread that allocated first_block.
-                    // In this case it is necessary to re-read the current table.
-
-                    if (table) {
-                        my_segment_table.store(table, std::memory_order_release);
-                    } else {
-                        table = my_segment_table.load(std::memory_order_acquire);
+                    segment_table_type new_table =
+                        self()->allocate_long_table(my_embedded_table, start_index);
+                    // It is possible that the table was extended by the thread that allocated first
+                    // block. In this case, the below CAS fails and re-reads the new table pointer.
+                    if (my_segment_table.compare_exchange_strong(
+                            table, new_table,
+                            /*memory order in case of a success*/std::memory_order_release,
+                            /*memory order in case of a failure*/std::memory_order_acquire))
+                    {
+                        // CAS was successful, update the local table pointer with now actual
+                        table = new_table;
+                    } else if (new_table) {
+                        // Other thread was the first to replace the segment table. Current thread's
+                        // table is not needed anymore, so destroying it.
+                        destroy_and_deallocate_table(new_table, pointers_per_long_table);
                     }
                 }).on_exception([&] {
                     my_segment_table_allocation_failed.store(true, std::memory_order_relaxed);


Test patch:
diff --git a/test/tbb/test_concurrent_vector.cpp b/test/tbb/test_concurrent_vector.cpp
index afb37ab49c..0237102e17 100644
--- a/test/tbb/test_concurrent_vector.cpp
+++ b/test/tbb/test_concurrent_vector.cpp
@@ -1,5 +1,5 @@
 /*
-    Copyright (c) 2005-2022 Intel Corporation
+    Copyright (c) 2005-2024 Intel Corporation
 
     Licensed under the Apache License, Version 2.0 (the "License");
     you may not use this file except in compliance with the License.
@@ -33,6 +33,7 @@
 #include <tbb/parallel_for.h>
 #include <algorithm>
 #include <cmath>
+#include <random>
 
 //! \file test_concurrent_vector.cpp
 //! \brief Test for [containers.concurrent_vector] specification
@@ -692,14 +693,36 @@ TEST_CASE("swap with not always equal allocators"){
 // or fail with the assertion in debug mode.
 //! \brief \ref regression
 TEST_CASE("Testing vector in a highly concurrent environment") {
-    for (std::size_t i = 0; i < 10000; ++i) {
-        tbb::concurrent_vector<int> test_vec;
-
-        tbb::parallel_for(tbb::blocked_range<std::size_t>(0, 10000), [&] (const tbb::blocked_range<std::size_t>&) {
-            test_vec.grow_by(1);
-        }, tbb::static_partitioner{});
+    std::uniform_int_distribution<> uniform_dist(1, 32); // grow by from 1 to 32 randomly
+    std::mt19937_64 gen(/*seed*/1); // Constructing with seed to have reproducible results
+    constexpr int num_repeats = 10000, num_inserts = 256;
+    std::vector<int> grow_by_vals(num_inserts);
+
+    for (int i = 0; i < num_repeats; ++i) {
+        int expected_size = 0, expected_sum = 0;
+        std::generate(grow_by_vals.begin(), grow_by_vals.end(),
+                      [&gen, &uniform_dist, &expected_size, &expected_sum]() {
+                          const int random_value = uniform_dist(gen);
+                          expected_size += random_value;
+                          expected_sum += random_value * random_value;
+                          return random_value;
+                      });
 
-        REQUIRE(test_vec.size() == utils::get_platform_max_threads());
+        tbb::concurrent_vector<int> test_vec;
+        tbb::parallel_for(0, num_inserts, [&] (int j) {
+            tbb::concurrent_vector<int>::iterator start_it = test_vec.grow_by(grow_by_vals[j]);
+            tbb::concurrent_vector<int>::iterator end_it = start_it + grow_by_vals[j];
+            do {
+                *start_it = grow_by_vals[j];
+            } while (++start_it != end_it);
+        });
+
+        REQUIRE(test_vec.size() == expected_size);
+        int actual_sum = 0;
+        for (int j = 0; j < expected_size; ++j) {
+            actual_sum += test_vec[j];
+        }
+        REQUIRE(expected_sum == actual_sum);
     }
 }