Учимся рефакторить код на примере багов в TDengine, часть 2: макрос, пожирающий стек

Проверяя код проекта TDengine с помощью PVS-Studio, можно встретить код с запахом, канонические ошибки и опечатки. Многое из этого можно избежать, если изначально аккуратно оформлять код, делать логику простой и избегать макросов. Давайте рассмотрим некоторые фрагменты кода и подумаем, как можно провести его рефакторинг так, чтобы багам просто не было там места.

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

Если макрос можно не писать, то и не надо его писать. Конечно, я не призываю теперь заниматься Copy-Paste программированием, вместо того, чтобы использовать макросы :) Речь идёт о том, что если можно использовать другую конструкцию языка, позволяющую получить приблизительно такую же выразительность и краткость кода, то лучше использовать именно её.

Посмотрим на вот такую функцию сортировки в проекте TDengine:

void mndSortVnodeGid(SVgObj *pVgroup) {
  for (int32_t i = 0; i < pVgroup->replica; ++i) {
    for (int32_t j = 0; j < pVgroup->replica - 1 - i; ++j) {
      if (pVgroup->vnodeGid[j].dnodeId > pVgroup->vnodeGid[j + 1].dnodeId) {
        TSWAP(pVgroup->vnodeGid[j], pVgroup->vnodeGid[j + 1]);
      }
    }
  }
}

Видите проблему в коде?

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

Итак, вернёмся к спрятанному сюрпризу. Его сложно заметить на рефакторинге, так как всё смотрится логично. Тем не менее, анализатор PVS-Studio выдаёт следующее предупреждение:

V505 [CWE-770, CERT-MEM05-C] The 'alloca' function is used inside the loop. This can quickly overflow stack. mndVgroup.c 807

Почему? Вроде просто меняется содержимое двух объектов и ничего не вызывает подозрения:

TSWAP(pVgroup->vnodeGid[j], pVgroup->vnodeGid[j + 1]);

Высока вероятность, что при обзоре этого фрагмента кода никто не насторожится. Собственно, раз мы его рассматриваем, так и произошло :)

Чтобы понять, чем плох этот код, надо не полениться пойти в другой файл и посмотреть, что же такое TSWAP. И окажется, что это макрос с красивыми граблями внутри. Для обмена двух строк используется временный буфер, выделенный на стеке с помощью функции alloca.

#define TSWAP(a, b)                  \
  do {                               \
    char *__tmp = (char*)alloca(sizeof(a)); \
    (void)memcpy(__tmp, &(a), sizeof(a));  \
    (void)memcpy(&(a), &(b), sizeof(a));   \
    (void)memcpy(&(b), __tmp, sizeof(a));  \
  } while (0)

Описание функции alloca в Linux manual page.

Скорее всего, программист хотел оптимизировать скорость работы программы, поэтому выделял временный буфер памяти не в куче, а на стеке. Это быстрее. Плюс проще, так как не надо заботиться о проверке полученного указателя на NULL и писать код для освобождения памяти. Память на стеке освобождается сама в момент завершения функции. В общем, хотел сделать хорошо, а получилось плохо.

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

Сортируются элементы, представляющие собой структуры типа SVnodeGid:

typedef struct {
  int32_t    dnodeId;
  ESyncState syncState;
  int64_t    syncTerm;
  bool       syncRestore;
  bool       syncCanRead;
  int64_t    roleTimeMs;
  int64_t    startTimeMs;
  ESyncRole  nodeRole;
  int32_t    learnerProgress;
} SVnodeGid;

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

#define TSDB_MAX_REPLICA               5
#define TSDB_MAX_LEARNER_REPLICA       10
....
typedef struct {
  ....
  SVnodeGid vnodeGid[TSDB_MAX_REPLICA + TSDB_MAX_LEARNER_REPLICA];
  ....
} SVgObj;

Сейчас массив состоит всего из 15 элементов. Поэтому неэффективный вариант сортировки и выделения памяти на стеке почти наверняка не проявят себя.

В худшем случае сортировка пузырьком выполняется за (N - 1)*N/2 перестановок элементов. Значит в этом случае макрос TSWAP выполнится (15-1)*15/2 = 105 раз. А для выполнения этих перестановок на стеке будет выделено 105 * 48 = 5040 байт.

Не очень большое значение, и именно поэтому этот код, наверное, никогда не вызывал проблем исчерпания стека. Однако, как вы, возможно, догадываетесь, это свойство макроса пожирать память на стеке неожиданно может проявить себя, если понадобится увеличить размер массива vnodeGid.

Это никогда не понадобится? Кто знает, кто знает. Разработчики ракеты Ariane 4 тоже не предполагали, что их код затем будет повторно использован в Ariane 5, обладающей другими техническими характеристиками. Подробнее этот случай мы рассматривали в статье "Космическая ошибка: 370.000.000 $ за Integer overflow".

Предположим, что в будущем кому-то все же потребуется увеличить массив хотя бы до 100 элементов. Тогда в худшем случае на стеке будет выделено ((100-1)*100/2)*48 = 237 600 байт. Это может оказаться той соломинкой, которая переломит спину верблюду. Причём функция требует разное количество памяти в зависимости от входных данных. Программа может успешно проходить все тестовые сценарии, но отказать при работе с пользовательским данными.

Давайте улучшать код.

Я хотел начать с уменьшения размера структуры SVnodeGid за счёт перестановки полей (смотри приём, описанный в "Урок 23. Паттерн 15. Рост размеров структур"). Но в данном случае ничего не выйдет, так как из-за необходимости выравнивания останется такая же дырка для выравнивания данных, но не в начале, а уже в конце структуры. Зато если вы не знали про такой приём, то теперь знаете.

Дальше постараемся избавиться от макроса. Его можно и нужно заменить на функцию. В этом случае исчезает проблема, что стек может закончиться в самый неподходящий момент. В случае C++ это вообще не имело бы смысла обсуждать, так как есть std::swap, но у нас C. Можно предложить вот такую универсальную функцию перестановки двух элементов:

void tswap(void *a, void *b, size_t size) 
{
  char *__tmp = (char*)alloca(size);
  (void)memcpy(__tmp, a, size);
  (void)memcpy(a, b, size);
  (void)memcpy(b, __tmp, size);
}

Не могу сказать, что она красивая, но уже лучше. Кто-то может возразить, что с помощью макроса можно создать более эффективный код, так как не требуется вызов функции.

Не согласен с возражением:

• На фоне копирования структур туда-сюда, вызов функции — это такая мелочь, что её не стоит брать в расчёт.
• Современные оптимизирующие компиляторы вполне могут сами справиться с встраиванием функции в тело цикла. Высока вероятность, что компилятор и без вас сделает код таким же эффективным.
• Оптимизация не там. Намного больше пользы будет от использование эффективного алгоритма сортировки. От этого на порядок больше пользы, чем от попытки что-то оптимизировать, используя макрос.

После внесения правок код выглядит следующим образом:

void tswap(void *a, void *b, size_t size) 
{
  char *__tmp = (char*)alloca(size);
  (void)memcpy(__tmp, a, size);
  (void)memcpy(a, b, size);
  (void)memcpy(b, __tmp, size);
}

void mndSortVnodeGid(SVgObj *pVgroup) {
  for (int32_t i = 0; i < pVgroup->replica; ++i) {
    for (int32_t j = 0; j < pVgroup->replica - 1 - i; ++j) {
      if (pVgroup->vnodeGid[j].dnodeId > pVgroup->vnodeGid[j + 1].dnodeId) {
        tswap(&pVgroup->vnodeGid[j],
              &pVgroup->vnodeGid[j + 1], sizeof(SVnodeGid);
      }
    }
  }
}

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

Основную проблему, на мой взгляд, мы исправили. Однако есть ещё сортировка пузырьком, которая выполняет лишние копирования данных. Например, в худшем случае она выполняет в N/2 раза больше перестановок, чем сортировка выбором. А есть и другие, более эффективные алгоритмы. Обсуждение алгоритмов сортировки выходит за рамки это статьи, да и не имеет особого смысла, если речь идёт о массиве из 15 элементов.

Однако я бы не стал сам писать вообще какой-то код сортировки, а воспользовался функцией qsort. И вот почему:

• Чем меньше самописных велосипедов, тем меньше вероятность ошибиться.
• Реализации из стандартной библиотеки уже множество раз протестированы, а также могут содержать различные оптимизации.
• В случае использования стандартных алгоритмов вообще не нужен свой макрос или своя функция для перестановки элементов.
• Заранее решена проблема падения производительности, если в будущем потребуется увеличить количество элементов в массиве. Реализация внутри qsort точно лучше самодельного пузырька.

int CmpSVnodeGid(const void *a, const void *b)
{
  int32_t aId = ((const SVnodeGid *)(a))->dnodeId;
  int32_t bId = ((const SVnodeGid *)(b))->dnodeId;
  if (aId < bId) return -1;
  if (aId > bId) return 1;
  return 0;
}

void mndSortVnodeGid(SVgObj *pVgroup) {
  qsort(pVgroup->vnodeGid, pVgroup->replica,
        sizeof(SVnodeGid), CmpSVnodeGid);
}

Отлично: нет пожирания стека, быстро, масштабируемо, а ещё и не нужен макрос. Великая сила переиспользования готовых стандартных решений.

Дополнительные ссылки:

• Perl 5: как в макросах ошибки прятались
• Предупреждения помогают писать лаконичный код
• Главный вопрос программирования, рефакторинга и всего такого