Внимание! Опасный баг в реализации C++ std::map::merge и std::set::merge в Visual Studio 2017

    Если Вы используете стандарт C++17 в MS Visual Studio 2017 — будьте осторожны: текущая версия содержит критический баг в реализации std::map::merge и std::set::merge. Подробности — под катом.

    Как проявляется баг?


    1. Сложность std::map::merge и std::set::merge вместо заявленной стандартом N*log(size()+N)), где N — размер добавляемой части, оказывается примерно N в квадрате.
    2. Если с помощью merge был добавлен контейнер с достаточно большим количеством элементов — при уничтожении результирующего контейнера получим stack overflow.
    3. Контейнер после работы merge приходит в некорректное состояние, поэтому возможны и другие проявления.

    Что говорит Microsoft?


    Багрепорт был отправлен мной в Microsoft почти 2 месяца назад.
    В Visual Studio 2019 Update 2 Preview 2 должны были исправить.

    А вот в текущей версии Visual Studio 2017 15.9.12 не исправлено до сих пор, и, судя по последним сообщениям, ждать еще долго…

    Баг заключается в некорректной маркировке цвета добавленных узлов в реализации красно-чёрного дерева.

    Как воспроизвести?


    //#include "pch.h"
    
    #include <chrono>
    #include <string>
    #include <iostream>
    #include <map>
    #include <set>
    
    
    const size_t mainSize = 50'000;
    const size_t additionSize = mainSize;
    
    
    auto getMainMap()
    {
      std::map<size_t, std::string> result;
      while( result.size() < mainSize )
        result.emplace(result.size(), "SomeText");
    
      return result;
    }
    
    
    auto getAdditionMap()
    {
      std::map<size_t, std::string> result;
      while ( result.size() < additionSize )
        result.emplace(mainSize + result.size(), "SomeAdditionText");
    
      return result;
    }
    
    
    int main()
    {
      {
        auto mainMap = getMainMap();
        auto addition = getAdditionMap();
    
        auto start = std::chrono::steady_clock::now();
        for ( auto const &elem : addition )
          mainMap.emplace(elem);
        auto end = std::chrono::steady_clock::now();
    
        std::cout << "manual insertion with copy: "
                  << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count()
                  << std::endl;
      }
    
      {
        auto mainMap = getMainMap();
        auto addition = getAdditionMap();
    
        auto start = std::chrono::steady_clock::now();
        mainMap.merge(addition);
        auto end = std::chrono::steady_clock::now();
    
        std::cout << "std::map::merge: "
                  << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count()
                  << std::endl;
      } // <---- and stack overflow here because of incorrect mainMap after merge
    
      return 0;
    }
    

    Варьируя значение mainSize, можно получать разные результаты — либо только медленное выполнение, либо еще и крах.

    Что делать?


    Пересмотреть свой код и заменить обращения к merge ручной вставкой. Либо перейти на VS 2019.
    А если скомпилированный код уже ушёл к заказчику… Оххх…
    Поделиться публикацией

    Похожие публикации

    Комментарии 34

      0
      Интересно… QuickCheck-style тестирование с проверками на корректность состояния бы таки помогли, да?
        0

        Тоже очень любопытно про property based testing. Обычного fuzzing в проектах уже не хватает.

        +2
        Для выявления этого бага даже внутреннее состояние проверять не обязательно — оно же просто крошится при очень небольшой нагрузке (порядка десятков тысяч элементов).
        И опасный баг. Ох опасный. Т.к. зависит от того, какое количество данных пользователь надумает обработать.
          +1
          не часто в юнит тестах пишут размерны тесты. тем более никто не пишет тест «скормить рандом и посмотреть что не упало» — ну кроме случая когда поймали уже такую вещь.
          квикчек это сила.

          даже интересно (студии нынче нет у меня) — если скормить github.com/emil-e/rapidcheck вот этому, баг изловится?
            +3
            никто не пишет тест «скормить рандом и посмотреть что не упало»

            Кто хочет подобных ляпов — пусть не тестирует. А я свои алгоритмы обычно прогоняю в том числе и на случайных данных. Более того, проверяю не просто «чтоб не упало», а еще и «чтобы результат обработки случайных данных совпал с ожидаемым» (да-да, при формировании случайной тестовой выборки зачастую можно сформировать и ожидаемый результат).
              0
              Всё, что может быть автоматизировано — должно быть автоматизировано. Тестирование тоже.
                0

                Особенно в этом случае. Например, если загнать данные в rb-tree, а потом их оттуда прочитать, то мы должны получить искомый список, но отсортированный. У меня в моём решении задачек из purely functional data structures есть тесты вида


                property $ \(list :: [Int]) -> RB.toList (RB.fromList list) == sort list

                QC сам найдёт, если и где это опровергается.


                Ну а потом уже можно какие-то там инварианты проверять, типа


                property $ \(lst :: [Int]) -> RB.isSearchTree $ RB.toList list
                property $ \(lst :: [Int]) -> RB.noRedRedPath $ RB.toList list
                property $ \(lst :: [Int]) -> RB.sameBlackCount $ RB.toList list

                Можно, конечно, доказывать корректность, но это сложнее и уж точно не на плюсах.

                  +1
                  А сортированность в данном случае и не нарушается. И мапа даже продолжает работать, почти как живая — производит вставки, ищет, итерирует. И это тоже часть опасности бага: прикладной разработчик, доверяющий реализации STL, может даже ничего и не заметить, если работает с небольшим количеством данных.
                    0

                    Так для этого три следующих теста.

                    0
                    Дык там возникает перекособоченное дерево. Как раз беда именно в том, что нарушаются гарантии по сложности, всё остальное работает.

                    А креши возникают потому что гарантии по сложности влияют на необходимую глубину стека. Был бы стек побольше — оно и с миллионами элементов работало бы…
                      0
                      гарантии по сложности влияют на необходимую глубину стека

                      Нет. На необходимую глубину стека влияет тот факт, что Майкрософт при уничтожении мапы использует рекурсивный алгоритм.
                        0
                        Дык ему должно быть пофигу в какие цвета там вершины расскрашены, разве нет?

                        Проблема в том, что если мапара «перекособоченная» — то грубина рекурсии оказывается такой, как она ни при каких данных, без ошибки, оказаться бы не смогла.

                        Или я чего-то не понял?
                          0
                          грубина рекурсии оказывается такой, как она ни при каких данных, без ошибки, оказаться бы не смогла

                          Да.
                          Но:
                          А креши возникают потому что гарантии по сложности влияют на необходимую глубину стека

                          Нет. Они влияют только на скорость. Как они могут влиять на глубину стека?
                          Прогоните деструктор на больной вижле под дебаггером — станет понятнее, что там происходит.
                            0
                            Нет. Они влияют только на скорость. Как они могут влиять на глубину стека?
                            Очень просто: если у вас мапа — это красно-чёрное дерево, то там количество уровней — порядка логарифма от количества элементов. А если оно выродилось в список — то у вас там могут быть тысячи уровней для тысяч элементов… что в сбалансированном дереве не может случиться даже при количестве данных порядка эксабайтов…
                              0
                              Это понятно.
                              Мапа должа быть деревом, а глючный алгоритм мержа сломал дерево и добавленную часть выпрямил в линию.
                              В результате поиск по линии превратился из логарифмического в линейный, что нарушило соглашения о сложности поиска.
                              Не понятна только Ваша фраза:
                              А креши возникают потому что гарантии по сложности влияют на необходимую глубину стека

                              Если бы в деструкторе был применён нерекурсивный алгоритм, то деструктор даже на такой поломанной мапе не крошился бы. И даже работал бы с нормальной скоростью, т.к. его сложность что так, что эдак линейная.
                                0
                                Мапа должа быть деревом, а глючный алгоритм мержа сломал дерево и добавленную часть выпрямил в линию.
                                Линия — это тоже дерево. Ваш К.О.

                                Если бы в деструкторе был применён нерекурсивный алгоритм, то деструктор даже на такой поломанной мапе не крошился бы. И даже работал бы с нормальной скоростью, т.к. его сложность что так, что эдак линейная.
                                С другой стороны если бы дерево оставалось красно-чёрным, то ни при каких разумных объёмах (влезающих а адресное пространтство x86-64 CPU) глубина стека не перешла бы 100, так что не очень понятно — имеет ли смысл усложнять алгоритм чтобы поддерживать версию либы в которой очевидная ошибка…
                  0
                  Мне вот сейчас еще одна нестыковка в голову пришла.
                  В реализации RBTree от Microsoft в дебаге производится проверка корректности работы оператора сравнения. Я как-то раз вместо «operator<» подсунул «operator<=» — оно в итоге выкрошилось с вразумительной диагностикой.
                  Так вот. Проверка целостности внутреннего состояния (требования чередования «красный-чёрный») в дебаге выглядит даже более логичной, чем проверка внешнего оператора сравнения. Но не производится.
                  А это не позволило бы багу случиться.
                    0
                    Проверка целостности внутреннего состояния (требования чередования «красный-чёрный») в дебаге выглядит даже более логичной, чем проверка внешнего оператора сравнения. Но не производится.
                    Что значит «более логичной»? Внешний оператор сравнения если вы подсовываете кривой — то у вас будут проблемы даже при идеально написанном дереве. Потому эта проверка помогает стороннему разработчику. А требования красно-чёрности — это чисто проверка на валидность реализации самого дерева… при правильно написанной реализации это никому, кроме разработчиков самой библиотеки, не нужно.

                    В GNU библиотеках есть так называемый «Maintainer Mode» — вот там такие проверки были бы уместны…
                      0
                      при правильно написанной реализации

                      Проблема в том, что мы тут обсуждаем именно неправильную реализацию. И даже не просто неправильную реализацию, а факт её выхода в релизную версию средства разработки. И разговор как-то пошёл в ключе «а как разработчики до такого докатились» и «что они должны были сделать, чтобы это предотвратить».
                        0
                        Ну уж вставлять странные проверки в код, которые будет запускать пользователь всяко не стоит.

                        А вот сделать тесты, которые будут проверять что дерево осталось красно-чёрным деревом поиска и скрестить их с фаззингом — самое то.
                0
                Зачем в коде для воспроизведения бага chrono и замеры времени? Код для воспроизведения должен быть минимальным.
                  +2
                  Одним из проявлений бага является медленное исполнение. Как предлагаете его проверять без chrono? С секундомером сидеть?
                    –1
                    Во-первых, главный баг — это креш, а он воспроизводится и без таймеров. Во-вторых, как предполагается оценить замедление по этому коду? Ну, выведет он «100 микросекунд» — а как понять хорошо это или плохо?
                      +5
                      А Вы этот код запускали? Он не одну цифру выведет, а две. И конкретно в приведённом коде они будут различаться раз так в 400-500.
                      Упадёт ли код в stack overflow, зависит от размера стэка. Чтобы код гарантированно упал при любом разумном размере стэка, надо бахнуть эдак миллион элементов, которые будут мержиться проблемным алгоритмом минут 30.
                        0
                        Две-то две, но что они покажут? Сравнение работы «emplace в цикле» и «merge». А стандарт нигде не говорит, что эти операции должны быть как-то связаны. Да, есть оценка О для обеих, но там могут быть совершенно разные коэфициенты.

                        Я бы сказал, что если уж браться за замеры времени, то нужно показать рост времени с ростом размера выборки для «emplace в цикле» и для merge. Тогда будет видно, что один логарифмичный, а второй квадратичный.
                          +8
                          В данном случае такая дотошность определённо излишняя.
                          Этот код вполне убедил Microsoft, что баг у них есть.
                          И этот код позволяет в течение минуты любому читателю статьи проверить, содержится ли этот баг в его инструменте.
                          По-моему, именно это от тестового кода и требуется.
                        0
                        Падение еще и от битности зависит. При размере стэка по умолчанию в x64 16'000 еще проходят, а 17'000 — уже нет.
                        А в x86 43'000 проходят, а 44'000 — уже нет.
                    +7
                    Тот редкий случай, когда на собеседовании нужно было попросить разрабочика развернуть на доске красно-чёрное дерево :)
                      +2
                      это еще что. Вот когда вин10 была еще в стадии анонсов, и ее можно было погонять вместе с анонсированным VS2015 (записавшись в «программу инсайдеров» — вам можно было скачать билды до их официального релиза) в очередном билде они выкатили ошибку в strlcat (ЕМНИП не работала конкатенация, если первая строка нулевой длины).
                      Хотя казалось бы — ну ладно, кто-то жестоко протупил, но зачем вообще надо было трогать тот код?
                        +4
                        У меня нет VS2015, чтобы проверить, но могу предположить что «потрогать» код решили из-за поддержки SSE4.2.

                        Инструкции STTNI (входящие в SSE4.2) позволяют ускорить строковые функции — причём хорошо так ускорить, разика 2-3… однако только для длинных строк.

                        Чтобы производительность на коротких строках не упала «ниже плинтуса» (а strlcat и на коротких строках используют тоже) нужен довольно-таки большой шаманский бубен…

                        Видимо у Microsoft шаман был не проспавшимся, когда этот бубен прилаживал…
                          0
                          … просто от функции уровня strlcat я такого не ожидал.
                          в отличии от комментатора ниже, я все же не думаю, что "индустрия катится в бездну", но я был ранее уверен, что там более полные тесты стандартных либ CRL\STL.
                            0

                            На самом деле она катится, но это явно не вопрос этого топика (посмотрите только на количество кода на каком-нибудь гитхабе в разрезе его качества).

                              0
                              Все считают, что уж что-то, а стандартную библиотеку кто-нибудь протестирует… кто-нибудь другой.

                              Дима Вьюков рассказывает, как они фаззят всякие вещи, но при этом стандартная библиотка… заменяется загрушками (и считается, что с ней всё в порядке априори).

                              Есть, правда, и тесты на стандартную библиотеку отдельные, но иногда да — таки получается эффект «у семи нянек — дитя без глазу».
                        –2

                        Вы своей статьей разрушили мой внутренний мир. Я-то думал, что реализация STL в MSVC эталонная и ей как минимум можно доверять. Оказыватся, что нет. Я считаю, что это просто вопиющий случай безалаберности и показывает как наша индустрия катится в бездну.

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

                        Самое читаемое