пятница, 17 февраля 2017 г.

std::vector is non-reentrant

Я говорил, что, в отличие от разработчиков Boost, разработчики STL хотя бы люди? Я хочу взять свои слова назад.

Это история ловли одного бага, которая заняла свыше трех недель. При этом баг не воспроизводился, в лабораторных условиях воссоздать его не удалось, а документация и прочие источники не дали ничего вразумительного.

Взгляните на код:

 void processdata()  
 {  
      std::vector<std::string> inToken;  
   
  // Some stuff  
   
  for (size_t i = 1; i < v_max; i++) {  
     // Some stuff  
                     inToken.push_back(token);  
      }  
                       
  // Some stuff  
   
 }
  
 int main(int argc, char* argv[])  
 {  
   
  // Some stuff  
    
      while (!std::cin.eof()) {  
           /* Start processing threads */  
           for (size_t i = 0; i < v_max_threads; i++) {  
                threads.push_back(std::thread([]() {  
                     processdata();  
                }));  
           }  
           /* Finish all threads */  
           std::for_each(threads.begin(), threads.end(), [](std::thread &t) {  
                t.join();  
           });  
           threads.clear();  
      }  
      /*-------------Main Loop----------------*/  
      return 0;  
 }  

Все красиво, не правда ли? Полностью локальный вектор в тредовой процедуре. В этой процедуре вектор используется для парсинга строк (std::string) переменной длины. Конкретно - строка разбивается на токены, причем первый токен коротенький, и его длина не превышает нескольких символов, второй может варьироваться от 20 до 2048 символов, изредка - более.

 Все хорошо и прекрасно, но иногда, вне какой либо связи с нагрузкой или любыми другими видимыми событиями, данное приложение сегфолтилось. Причем GDB при обратной трассировке показывал только выход из процессингового треда по join() (приложение было собрано с ключом -g), а DBX давал странную трассировку:

 t@336 (l@336) terminated by signal SEGV (no mapping at the fault address)  
 Current function is std::__detail::_Executor<__gnu_cxx::__normal_iterator<const char*, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::allocator<std::__cxx11::sub_match<__gnu_cxx::__normal_iterator<const char*, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > > > >, std::__cxx11::regex_traits<char>, true>::_M_dfs  
  795     { return *(this->_M_impl._M_start + __n); }  
 
 (dbx) where  
 current thread: t@336  
 =>[1] std::__detail::_Executor<__gnu_cxx::__normal_iterator<const char*, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::allocator<std::__cxx11::sub_match<__gnu_cxx::__normal_iterator<const char*, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > > > >, std::__cxx11::regex_traits<char>, true>::_M_dfs(this = 0xfffffd7ffea90ef0, __match_mode = _Match_mode::_Prefix, __i = 17), line 795 in "stl_vector.h"  
  [2] std::__detail::_Executor<__gnu_cxx::__normal_iterator<const char*, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::allocator<std::__cxx11::sub_match<__gnu_cxx::__normal_iterator<const char*, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > > > >, std::__cxx11::regex_traits<char>, true>::_M_dfs(this = 0xfffffd7ffea90ef0, __match_mode = <value unavailable>, __i = <value unavailable>), line 267 in "regex_executor.tcc"  

Смотрите очень внимательно. Regex тут не при чем. Дамп в принципе не содержит отсылки к коду приложения, то есть исключение прилетает не оттуда. Что-то с аллокатором, да? Какой-то контейнер вызывает проблему.


Опущу историю ловли бага. Беда в том, что он проявлялся спорадически. Иногда несколько раз за день, иногда - ни разу. Никакой системы не было. Воспроизвести в контролируемых условиях, как я сказал выше, не удалось.

Посмотрите на код еще раз.

Так вот. несмотря на то, что тип вектор - является, по заявлению разработчиков, потокобезопасным - то есть читатель читателю в разных тредах не мешает, писатель читателю в разных тредах не мешает, а в нашем случае, раз вектор локальный, вообще никаких проблем быть не должно - он не является реентрантным.

Говоря простым языком, у контейнера std::vector есть аллокатор памяти, который общий для всех векторов, которые вы определяете - неважно, локальные или глобальные.

И, когда происходит push_back в вектор, иногда перераспределяется память (помните, я говорил выше, что вектор используется для строк переменной длины?). Так вот, поскольку реализация аллокатора сделана не совсем людьми, никто о реентрантности и не думал. Более того, в разных системах, с разными libc и разными реализациями вышеприведенный код может вести себя как угодно. Если какие-нибудь алиены в дистрибутиве Бла-Бла-Бла-Линукс вдруг озаботились реентрантностью, они могли использовать примитивы синхронизации в аллокаторе контейнеров. Хорошо, если мьютексы. Много хуже, если спин-локи. Если не озаботились - получайте сегфолт в любой момент времени. На одной платформе мы не получали сегфолтов, но процессор взлетал в момент вызова аллокатора до 50 или 100% резким и кратковременным пиком. Что сказывалось на работе всего сервера, поскольку происходило достаточно часто.

В нашем случае, когда в двух разных асинхронных тредах одновременно происходил push_back в два - напоминаю, разных локальных вектора - в случае, если вставляемые строки сильно отличались по размеру, в одном из тредов или в двух одновременно происходил вызов нереентрантнолго аллокатора, что приводило к повреждению памяти, повреждению вставляемых строк и обычно оба треда падали в дамп (они обычно попарно и падали, сегфолты почти всегда происходили парами).


Окей, чтобы убедиться что я прав, давайте закостылим:

 std::mutex vec_mtx;  
   
 void processdata()  
 {  
      std::vector<std::string> inToken;  
   
  // Some stuff  
   
  for (size_t i = 1; i < v_max; i++) {  
     // Some stuff  
                {  
                     std::lock_guard<std::mutex> lock(vec_mtx);  
                     inToken.push_back(token);  
                }  
   
      }  
                       
  // Some stuff  
   
      }  
   
 int main(int argc, char* argv[])  
 {  
   
  // Some stuff  
    
      while (!std::cin.eof()) {  
           /* Start processing threads */  
           for (size_t i = 0; i < v_max_threads; i++) {  
                threads.push_back(std::thread([]() {  
                     processdata();  
                }));  
           }  
           /* Finish all threads */  
           std::for_each(threads.begin(), threads.end(), [](std::thread &t) {  
                t.join();  
           });  
           threads.clear();  
      }  
      /*-------------Main Loop----------------*/  
      return 0;  
 }  

Обернем push_back в мьютекс.

Ой! Что мы видим! Сегфолт ушел!

Одно плохо. Скорость выполнения тоже ухудшилась. Примерно в 3-30 раз. В зависимости от данных.

Не говорите мне, что надо было делать вызов Вектор.reserve() перед вставками. Во-первых, это не помогает, а во-вторых, это не имеет отношения к проблеме. К производительности push_back - может быть, но не к реентрантности.

Решение плохое во всех отношениях. Точка сериализации. Конкуренция блокировок.

Рассматривались разные варианты. Распределять контейнер самописным аллокатором, использовать динамический массив, использовать другой тип контейнеров.

Все было коряво, дьявольски усложняло алгоритмику, вело к утечкам (потенциальным) памяти итд. итп.

В конечном итоге проблему удалось решить радикально, переписав процедуру processdata() полностью без векторов, с использованием лишь наиболее примитивных контейнеров. Мне повезло, что в векторе могло быть от 1 до 4 элементов. Поэтому я отделался малой кровью лишь слегка изменив алгоритм и затолкав элементы в нумерованные переменные типа строка.



Но представьте себе, что вам надо обработать в потоке больше 100 элементов? Представили? Я как-то плохо представляю себе подобное без массив-подобных структур. Более того, я очень плохо представляю себе потоковую обработку, где я ограничен самыми примитивными типами данных из-за реентрантности.

Тщательный (очень тщательный поиск!) привел лишь к одной-единственной ссылке, где в принципе упоминалась теоретическая возможность (лишь возможность!) подобной ситуации. При этом все гуру СПО/GCC/STL всюду вещают, что контейнеры - и векторы в частности - потокобезопасные, нигде не сообщая, что они могут оказаться нереентрантными. (я умолчу о том, что в СПО в принципе дело плохо с документированием. Читайте исходники. Вы видели исходники STL? :)).

Да, я знаю, что можно обойти проблему, написав поток на C и на самом низком уровне - строки как цепочки указателей на символы, или написать свой аллокатор - реентрантный - для одного-единственного приложения.

Вся суть проблемы совершенно понятна - мышление уровня IBM PC с одним-единственным процессором Pentium-D ведет к тому, что программист, пишущий инструментальные средства, принципиально не задумывается, во-первых, обо всех возможных вариантах программирования, а, во-вторых, не представляет, что код может исполняться более, чем в один поток более, чем одним процессорным ядром. Не стоит говорить - "пиши иначе". В данной конкретной задаче иначе - не получится. Надо работать с локальными векторами и баста. И у меня все равно не укладывается в голове, как можно иметь локальную структуру, которая заявлена как потокобезопасная, но имеет глобальный некопируемый аллокатор, который никаким вывертом невозможно сделать локальным. И ради одной небольшой подпрограммы надо либо писать собственный класс контейнера + аллокатор. Если это прелести объектно-ориентированного программирования, то я - за процедурный подход.

Резюмируя вышенаписанное, я утверждаю, что разработчики STL - это дети осла, свиньи и Чужого из фильма "Чужой-4" (таким образом, они лишь на 1/3 генетически люди):


Поздоровайтесь с родителем, упыри! Это один из ваших отцов.