#c #multithreading #g #clang #thread-sanitizer
#c #многопоточность #g #clang #средство очистки потоков
Вопрос:
Я реализовал заблокированную хэш-таблицу и создал аналогичный модульный тест для проверки одновременного чтения / записи в таблицу. После очистки потока с помощью clang (AppleClang) он не сообщает об ошибках, но GCC (g 8), с другой стороны, выдает строки, которые я считаю ложными срабатываниями. Или они могут быть подлинными? Я тестировал код большое количество раз с помощью clang для того же самого и не смог найти логическую ошибку.
Заблокированный код таблицы подстановки:
template <typename Key, typename Value, typename Hash = std::hash<Key>>
class LockedLookupTable
{
class bucket_type;
public:
typedef Key key_type;
typedef Value mapped_type;
typedef Hash hash_type;
LockedLookupTable(unsigned num_buckets = 19, const Hash amp;hasher_ = Hash())
: _buckets(num_buckets), hasher(hasher_)
{
for (unsigned i = 0; i < num_buckets; i)
_buckets[i].reset(new bucket_type);
}
LockedLookupTable(const LockedLookupTable amp;other) = delete;
LockedLookupTable amp;operator=(const LockedLookupTable amp;other) = delete;
Value at(Key const amp;key, Value const amp;default_value = Value()) const
{
return get_bucket(key).at(key, default_value);
}
void insert(const Key amp;key, const Value amp;value)
{
get_bucket(key).insert(key, value);
}
void erase(const Key amp;key)
{
get_bucket(key).erase(key);
}
std::map<Key, Value> get_map() const
{
std::map<Key, Value> res;
for (unsigned i = 0; i < _buckets.size(); i) {
boost::unique_lock<boost::shared_mutex> lock(_buckets[i]->_mutex);
for (typename bucket_type::bucket_iterator it = _buckets[i]->data.begin();
it != _buckets[i]->data.end();
it) {
res.insert(*it);
}
}
return res;
}
int max_collisions() { return _buckets[0]->data.size() ? _buckets[0]->data.size() - 1 : 0; }
std::size_t size()
{
std::size_t count = 0;
for (unsigned i = 0; i < _buckets.size(); i) {
boost::unique_lock<boost::shared_mutex> lock(_buckets[i]->_mutex);
for (typename bucket_type::bucket_iterator it = _buckets[i]->data.begin();
it != _buckets[i]->data.end();
it) {
count ;
}
}
return count;
}
private:
std::vector<std::unique_ptr<bucket_type>> _buckets;
Hash hasher;
bucket_type amp;get_bucket(Key const amp;key) const
{
const std::size_t bucket_index = hasher(key) % _buckets.size();
return *_buckets[bucket_index];
}
class bucket_type
{
typedef std::pair<Key, Value> bucket_value;
typedef std::vector<bucket_value> bucket_data;
public:
typedef typename bucket_data::iterator bucket_iterator;
Value at(Key const amp;key, Value const amp;default_value)
{
boost::shared_lock<boost::shared_mutex> lock(_mutex);
bucket_iterator const found_entry = find_entry_for(key);
return (found_entry == data.end()) ? default_value : found_entry->second;
}
void insert(Key const amp;key, Value const amp;value)
{
boost::unique_lock<boost::shared_mutex> lock(_mutex);
bucket_iterator found_entry = find_entry_for(key);
if (found_entry != data.end())
data.erase(found_entry);
data.push_back(bucket_value(key, value));
}
void erase(Key const amp;key)
{
boost::unique_lock<boost::shared_mutex> lock(_mutex);
bucket_iterator const found_entry = find_entry_for(key);
if (found_entry != data.end())
data.erase(found_entry);
}
bucket_data data;
mutable boost::shared_mutex _mutex;
private:
bucket_iterator find_entry_for(Key const amp;key)
{
return std::find_if(data.begin(), data.end(),
[amp;](bucket_value const amp;item)
{
return item.first == key;
});
}
};
};
Тестовый код:
BOOST_AUTO_TEST_CASE(LockedLookupTableTest)
{
clock_t int_begin = clock();
LockedLookupTable<int, int> table(MAX_BUCKETS);
std::atomic<bool> go{false}, done_read{false}, done_write{false}, fail{false};
std::thread *r[MAX_THREADS], *w[MAX_THREADS];
#if SPLIT_THREADS
printf("Dividing work between %d reader %d writer threads: %d per thread.n", MAX_THREADS, MAX_THREADS, (MAX_TABLE_SIZE/MAX_THREADS));
#endif
// Populate for reading
for (int j = 0; j < MAX_TABLE_SIZE; j )
table.insert(j, j);
// Readers
for (int i = 0; i < MAX_THREADS; i ) {
r[i] = new std::thread([amp;go, amp;table, amp;done_read, amp;fail, i] () {
#if SPLIT_THREADS
int start = MAX_TABLE_SIZE / MAX_THREADS * i;
int end = start MAX_TABLE_SIZE / MAX_THREADS;
#else
int start = 0;
int end = MAX_TABLE_SIZE;
#endif
while (!go);
clock_t t_begin = clock();
for (int j = start; j < end; j ) {
int val = table.at(j);
if (j != val) {
char output[256];
sprintf(output, "INT/INT not equal: %d != %dn", j, val);
done_read = true;
fail = true;
return;
}
}
done_read = true;
printf("INT/INT Thread #%d - Read Time %.5fsn", i, double(clock() - t_begin) / CLOCKS_PER_SEC);
});
}
// Writers
for (int i = 0; i < MAX_THREADS; i ) {
w[i] = new std::thread([amp;go, amp;table, amp;done_write, i] () {
#if SPLIT_THREADS
int start = MAX_TABLE_SIZE / MAX_THREADS * i;
int end = start MAX_TABLE_SIZE / MAX_THREADS;
#else
int start = 0;
int end = MAX_TABLE_SIZE;
#endif
while (!go);
clock_t t_begin = clock();
for (int j = start; j < end; j )
table.insert(j, j);
done_write = true;
printf("INT/INT Thread #%d - Write Time %.5fsn", i, double(clock() - t_begin) / CLOCKS_PER_SEC);
});
}
go.exchange(true);
while (table.size() < MAX_TABLE_SIZE amp;amp; !done_read amp;amp; !done_write);
if (fail)
BOOST_FAIL("Failed read.");
printf("INT/INT Read/Write Test Finished in %0.5fsn", double(clock() - int_begin) / CLOCKS_PER_SEC);
int_begin = clock();
// Map Iteration
std::map<int, int> map = table.get_map();
int i = 0;
for (auto c : map) {
BOOST_CHECK_EQUAL(i, c.second);
i ;
}
printf("INT/INT Map Iteration Test Finished in %0.5fsn", double(clock() - int_begin) / CLOCKS_PER_SEC);
// Final Integrity Check
for (int j = 0; j < MAX_TABLE_SIZE; j )
BOOST_CHECK_EQUAL(j, table.at(j));
printf("INT/INT Finished in %0.5fsn", double(clock() - int_begin) / CLOCKS_PER_SEC);
for (int i = 0; i < MAX_THREADS; i ) {
if (r[i]->joinable()) r[i]->join();
if (w[i]->joinable()) w[i]->join();
delete r[i];
delete w[i];
}
done_read.exchange(false);
done_write.exchange(false);
go.exchange(false);
// Erase table contents.
for (int i = 0; i < MAX_THREADS; i ) {
w[i] = new std::thread([amp;go, amp;table, i] () {
#if SPLIT_THREADS
int start = MAX_TABLE_SIZE / MAX_THREADS * i;
int end = start MAX_TABLE_SIZE / MAX_THREADS;
#else
int start = 0;
int end = MAX_TABLE_SIZE;
#endif
while (!go);
clock_t t_begin = clock();
for (int j = start; j < end; j )
table.erase(j);
printf("INT/INT Thread #%d - Erase Time %.5fsn", i, double(clock() - t_begin) / CLOCKS_PER_SEC);
});
}
go.exchange(true);
while (table.size() > 0);
printf("INT/INT Collisions: %dn", table.max_collisions());
for (int i = 0; i < MAX_THREADS; i ) {
if (w[i]->joinable()) w[i]->join();
delete w[i];
}
}
Ошибки TSan в GCC-8:https://travis-ci.org/horizonxyz/horizon/jobs/507336127#L1424
Ошибки AppleClang:https://travis-ci.org/horizonxyz/horizon/jobs/507336131#L2950
Комментарии:
1. Этот код огромен. Пожалуйста, сведите это к минимуму до такой степени, чтобы было легко рассуждать. Начните с удаления функций, которые не нужны для воспроизведения, и не участвуйте в компиляции примера
2. @MichaelVeksler хорошо, я удалил часть теста, которая проверяет таблицу строковых ключей, поскольку код в основном тот же.
3. Можете ли вы также опубликовать ошибку? Ссылка бесполезна: этот журнал слишком длинный для отображения. Пожалуйста, уменьшите детализацию вашей сборки или загрузите необработанный журнал.
4. Кроме того, код по-прежнему большой
5. @MichaelVeksler В GCC большое количество ошибок, я не уверен, какие из них опубликовать здесь, поэтому я разместил ссылку и ответственный код здесь.