Немного о строках в Си, или несколько вариантов оптимизировать неоптимизируемое12.04.2017 16:04

Хабра, привет!

f39ded9ad02d48f59d5fefb5f816ab5e.jpg Не так давно у со мной произошел довольно-таки интересный инцидент, в котором был замешан один из преподавателей одного колледжа информатики.

Разговор о программировании под Linux медленно перешел к тому, что этот человек стал утверждать, что сложность системного программирования на самом деле сильно преувеличена. Что язык Си прост как спичка, собственно как и ядро Linux (с его слов).

У меня был с собой ноутбук с Linux, на котором присутствовал джентльменский набор утилит для разработки на языке Си (gcc, vim, make, valgrind, gdb). Я уже не помню, какую цель мы тогда перед собой поставили, но через пару минут мой оппонент оказался за этим ноутбуком, полностью готовый решать задачу.

И буквально на первых же строках он допустил серьезную ошибку при аллоцировании памяти под… строку. 

char *str = (char *)malloc(sizeof(char) * strlen(buffer));

buffer — стековая переменная, в которую заносились данные с клавиатуры.

Я думаю, определенно найдутся люди, которые спросят: «Разве что-то тут может быть не так?».
Поверьте, может.

А что именно — читайте по катом.

Немного теории — своеобразный ЛикБез.


Если знаете — листайте до следующего хэдера.

Строка в C — это массив символов, который по-хорошему всегда должен заканчиваться '\0' — символом конца строки. Строки на стеке (статичные) объявляются вот так: 

char str[n] = { 0 };

n — размер массива символов, то же, что и длина строки.

Присваивание { 0 } — «зануление» строки (опционально, объявлять можно и без него). Результат такой же, как у выполнения функций memset (str, 0, sizeof (str)) и bzero (str, sizeof (str)). Используется, чтобы в неинициализированных переменных не валялся мусор.

Так же на стеке можно сразу проинициализировать строку: 

char buf[BUFSIZE] = "default buffer text\n";

Помимо этого строку можно объявить указателем и выделить под нее память на куче (heap): 
char *str = malloc(size);

size — количество байт, которые мы выделяем под строку. Такие строки называются динамическими (вследствие того, что нужный размер вычисляется динамически + выделенный размер памяти можно в любой момент увеличить с помощью функции realloc ()).

В случае со стековой переменной, для определения размера массива я использовал обозначение n, в случае с переменной на куче — я использовал обозначение size. И это прекрасно отражает истинную суть отличия объявления на стеке от объявление с аллоцированием памяти на куче, ведь n как правило используется тогда, когда говорят о количестве элементов. А size — это уже совсем другая история…

Думаю. пока хватит. Идем дальше.

Нам поможет valgrind


В своей предыдущей статье я также упоминал о нем. Valgrind (раз — вики-статья, два — небольшой how-to) — очень полезная программа, которая помогает программисту отслеживать утечки памяти и ошибки контекста — как раз те вещи, которые чаще всего всплывают при работе со строками.

Давайте рассмотрим небольшой листинг, в котором реализовано что-то похожее на упомянутую мной программу, и прогоним ее через valgrind: 

#include 
#include 
#include 

#define HELLO_STRING "Hello, Habr!\n"

void main() {
  char *str = malloc(sizeof(char) * strlen(HELLO_STRING));
  strcpy(str, HELLO_STRING);
  printf("->\t%s", str);
  free(str);
}

И, собственно, результат работы программы: 
[indever@localhost public]$ gcc main.c 
[indever@localhost public]$ ./a.out 
->	Hello, Habr!

Пока ничего необычного. А теперь давайте запустим эту программу с valgrind! 
[indever@localhost public]$ valgrind --tool=memcheck ./a.out 
==3892== Memcheck, a memory error detector
==3892== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==3892== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==3892== Command: ./a.out
==3892== 
==3892== Invalid write of size 2
==3892==    at 0x4005B4: main (in /home/indever/prg/C/public/a.out)
==3892==  Address 0x520004c is 12 bytes inside a block of size 13 alloc'd
==3892==    at 0x4C2DB9D: malloc (vg_replace_malloc.c:299)
==3892==    by 0x400597: main (in /home/indever/prg/C/public/a.out)
==3892== 
==3892== Invalid read of size 1
==3892==    at 0x4C30BC4: strlen (vg_replace_strmem.c:454)
==3892==    by 0x4E89AD0: vfprintf (in /usr/lib64/libc-2.24.so)
==3892==    by 0x4E90718: printf (in /usr/lib64/libc-2.24.so)
==3892==    by 0x4005CF: main (in /home/indever/prg/C/public/a.out)
==3892==  Address 0x520004d is 0 bytes after a block of size 13 alloc'd
==3892==    at 0x4C2DB9D: malloc (vg_replace_malloc.c:299)
==3892==    by 0x400597: main (in /home/indever/prg/C/public/a.out)
==3892== 
->	Hello, Habr!
==3892== 
==3892== HEAP SUMMARY:
==3892==     in use at exit: 0 bytes in 0 blocks
==3892==   total heap usage: 2 allocs, 2 frees, 1,037 bytes allocated
==3892== 
==3892== All heap blocks were freed -- no leaks are possible
==3892== 
==3892== For counts of detected and suppressed errors, rerun with: -v
==3892== ERROR SUMMARY: 3 errors from 2 contexts (suppressed: 0 from 0)

==3892== All heap blocks were freed — no leaks are possible — утечек нет, и это радует. Но стоит опустить глаза чуть пониже (хотя, хочу заметить, это лишь итог, основная информация немного в другом месте):

==3892== ERROR SUMMARY: 3 errors from 2 contexts (suppressed: 0 from 0)
3 ошибки. В 2х контекстах. В такой простой программе. Как?!

Да очень просто. Весь «прикол» в том, что функция strlen не учитывает символ конца строки — '\0'. Даже если его явно указать во входящей строке (#define HELLO_STRING «Hello, Habr!\n\0»), он будет проигнорирован.

Чуть выше результата исполнения программы, строки → Hello, Habr! есть подробный отчет, что и где не понравилось нашему драгоценному valgrind. Предлагаю самостоятельно посмотреть эти строчки и сделать выводы.

Собственно, правильная версия программы будет выглядеть так: 

#include 
#include 
#include 

#define HELLO_STRING "Hello, Habr!\n"

void main() {
  char *str = malloc(sizeof(char) * (strlen(HELLO_STRING) + 1));
  strcpy(str, HELLO_STRING);
  printf("->\t%s", str);
  free(str);
}

Пропускаем через valgrind: 
[indever@localhost public]$ valgrind --tool=memcheck ./a.out 
->	Hello, Habr!
==3435== 
==3435== HEAP SUMMARY:
==3435==     in use at exit: 0 bytes in 0 blocks
==3435==   total heap usage: 2 allocs, 2 frees, 1,038 bytes allocated
==3435== 
==3435== All heap blocks were freed -- no leaks are possible
==3435== 
==3435== For counts of detected and suppressed errors, rerun with: -v
==3435== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Отлично. Ошибок нет, +1 байт выделяемой памяти помог решить проблему.

Что интересно, в большинстве случаев и первая и вторая программа будут работать одинаково, но если память, выделенная под строку, в которую не влез символ окончания, не была занулена, то функция printf (), при выводе такой строки, выведет и весь мусор после этой строки — будет выведено все, пока на пути printf () не встанет символ окончания строки.

Однако, знаете, (strlen (str) + 1) — такое себе решение. Перед нами встают 2 проблемы:

  1. А если нам надо выделить память под формируемую с помощью, например, s (n)printf (…) строку? Аргументы мы не поддерживаем.
  2. Внешний вид. Строка с объявлением переменной выглядит просто ужасно. Некоторые ребята к malloc еще и (char *) умудряются прикручивать, будто под плюсами пишут. В программе где регулярно требуется обрабатывать строки есть смысл найти более изящное решение.

Давайте придумаем такое решение, которое удовлетворит и нас, и valgrind.

snprintf ()


int snprintf(char *str, size_t size, const char *format, ...); — функция — расширение sprintf, которая форматирует строку и записывает ее по указателю, переданному в качестве первого аргумента. От sprintf () она отличается тем, что в str не будет записано байт больше, чем указано в size.

Функция имеет одну интересную особенность — она в любом случае возвращает размер формируемой строки (без учета символа конца строки). Если строка пустая, то возвращается 0.

Одна из описанных мною проблем использования strlen связана с функциями sprintf () и snprintf (). Предположим, что нам надо что-то записать в строку str. Конечная строка содержит значения других переменных. Наша запись должна быть примерно такой: 

char * str = /* тут аллоцируем память */;
sprintf(str, "Hello, %s\n", "Habr!");

Встает вопрос: как определить, сколько памяти надо выделить под строку str? 
char * str = malloc(sizeof(char) * (strlen(str, "Hello, %s\n", "Habr!") + 1));
 — не прокатит. Прототип функции strlen () выглядит так: 
#include 
size_t strlen(const char *s);

const char *s не подразумевает, что передаваемая в s строка может быть строкой формата с переменным количеством аргументов.

Тут нам поможет то полезное свойство функции snprintf (), о котором я говорил выше. Давайте посмотрим на код следующей программы: 

#include 
#include 
#include 

void main() {
/* Т.к. snprintf() не учитывает символ конца строки, прибавляем его размер к результату */
  size_t needed_mem = snprintf(NULL, 0, "Hello, %s!\n", "Habr") + sizeof('\0'); 
  char *str = malloc(needed_mem);
  snprintf(str, needed_mem, "Hello, %s!\n", "Habr");
  printf("->\t%s", str);
  free(str);
}

Запускаем программу в valgrind: 
[indever@localhost public]$ valgrind --tool=memcheck ./a.out 
->	Hello, Habr!
==4132== 
==4132== HEAP SUMMARY:
==4132==     in use at exit: 0 bytes in 0 blocks
==4132==   total heap usage: 2 allocs, 2 frees, 1,041 bytes allocated
==4132== 
==4132== All heap blocks were freed -- no leaks are possible
==4132== 
==4132== For counts of detected and suppressed errors, rerun with: -v
==4132== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
[indever@localhost public]$

Отлично. Поддержка аргументов у нас есть. Благодаря тому, что мы в качестве второго аргумента в функцию snprintf () передаем ноль, запись по нулевому указателю никогда не приведет к Seagfault. Однако, несмотря на это функция все равно вернет необходимый под строку размер.

Но с другой стороны, нам пришлось завести дополнительную переменную, да и конструкция 

size_t needed_mem = snprintf(NULL, 0, "Hello, %s!\n", "Habr") + sizeof('\0');

выглядит еще хуже, чем в случае с strlen ().

Вообще, + sizeof ('\0') можно убрать, если в конце строки формата явно указать '\0' (size_t needed_mem = snprintf (NULL, 0, «Hello, %s!\n\0», «Habr»);), но это возможно отнюдь не всегда (в зависимости от механизма обработки строк мы можем выделить лишний байт).

Надо что-то сделать. Я немного подумал и решил, что сейчас настал час воззвать к мудрости древних. Опишем макрофункцию, которая будет вызывать snprintf () с нулевым указателем в качестве первого аргумента, и нулем, в качестве второго. Да и про конец строки не забудем! 

#define strsize(args...) snprintf(NULL, 0, args) + sizeof('\0')

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

Проверим наше решение на практике: 

#include 
#include 
#include 

#define strsize(args...) snprintf(NULL, 0, args) + sizeof('\0')

void main() {
  char *str = malloc(strsize("Hello, %s\n", "Habr!"));
  sprintf(str, "Hello, %s\n", "Habr!");
  printf("->\t%s", str);
  free(str);
}

Запускаем с valgrund: 
[indever@localhost public]$ valgrind --tool=memcheck ./a.out 
->	Hello, Habr!
==6432== 
==6432== HEAP SUMMARY:
==6432==     in use at exit: 0 bytes in 0 blocks
==6432==   total heap usage: 2 allocs, 2 frees, 1,041 bytes allocated
==6432== 
==6432== All heap blocks were freed -- no leaks are possible
==6432== 
==6432== For counts of detected and suppressed errors, rerun with: -v
==6432== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Да, ошибок нет. Все корректно. И valgrind доволен, и программист наконец может пойти поспать.

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

Речь идет о функции asprintf: 

#define _GNU_SOURCE         /* See feature_test_macros(7) */
#include 

int asprintf(char **strp, const char *fmt, ...);

В качестве первого аргумента она принимает указатель на строку (**strp) и аллоцирует память по разыменованному указателю.

Наша программа, написанная с использованием asprintf () будет выглядеть так: 

#include 
#include 
#include 

void main() {
  char *str;
  asprintf(&str, "Hello, %s!\n", "Habr");
  printf("->\t%s", str);
  free(str);
}

И, собственно, в valgrind: 
[indever@localhost public]$ valgrind --tool=memcheck ./a.out 
->	Hello, Habr!
==6674== 
==6674== HEAP SUMMARY:
==6674==     in use at exit: 0 bytes in 0 blocks
==6674==   total heap usage: 3 allocs, 3 frees, 1,138 bytes allocated
==6674== 
==6674== All heap blocks were freed -- no leaks are possible
==6674== 
==6674== For counts of detected and suppressed errors, rerun with: -v
==6674== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Все отлично, но, как видите, памяти всего было выделено больше, да и alloc’ов теперь три, а не два. На слабых встраиваемых системах использование это функции нежелательно.
К тому же, если мы напишем в консоли man asprintf, то увидим: 
CONFORMING TO
       These functions are GNU extensions, not in C or POSIX.  They are also available under *BSD.  The FreeBSD implementation sets strp to  NULL on error.

Отсюда ясно, что данная функция доступна только в исходниках GNU.

Заключение


В заключение я хочу сказать, что работа со строками в C — это очень сложная тема, которая имеет ряд нюансов. Например, для написания «безопасного» кода при динамическом выделении памяти рекомендуется все же использовать функцию calloc () вместо malloc () — calloc забивает выделяемую память нулями. Ну или после выделения памяти использовать функцию memset (). Иначе мусор, который изначально лежал на выделяемом участке памяти, может вызвать вопросы при дебаге, а иногда и при работе со строкой.

Больше половины моих знакомых си-программистов (большинство из них — начинающие), решивших по моей просьбе задачу с выделением памяти под строки, сделали это так, что в конечном итоге это привело к ошибкам контекста. В одном случае — даже к утечке памяти (ну, забыл человек сделать free (str), с кем не бывает). Собственно говоря, это и сподвигло меня на создание сего творения, которое вы только что прочитали.

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

Я верю, что после прочтения этой статьи ваш код станет чуточку лучше:)
Удачи, Хабр!

Комментарии (13)

  • 12 апреля 2017 в 15:05

    –1

    ↑

    ↓

    После совета лепить везде calloc вместо malloc некоторый критический к производительности код станет чуточку ХУЖЕ. Предварительное забивание памяти нулем из соображений «как бы чего не вышло» гораздо хуже программирования без ошибок.

    А такие низкоуровневые системные места нужно формально доказывать, а не проверять при помощи VALGRIND.

    • 12 апреля 2017 в 15:07

      –1

      ↑

      ↓

      А такие низкоуровневые системные места нужно формально доказывать, а не проверять при помощи VALGRIND.

      Покажите, какой-нибудь интересный низкоуровневый код, правильность которого вы формально доказали

      • 12 апреля 2017 в 15:14

        0

        ↑

        ↓

        Если вы хотите знать метод доказательства, или подход к доказательству, то он описан Дейкстрой еще в 70е годы.

        1. Берем все системные функции за аксиомы, то есть считаем, что они работают в соответствии со своей спецификацией.

        2. Предполагаем, что компилятор работает строго в соответствии со стандартом языка.

        3. Исходя из этого, формально доказываем, что для всех входных данных программа работает в соответствии со своей спецификацией.

        Если удалось доказать — ура, новых багов мы не внесли.

        • 12 апреля 2017 в 15:15

          –1

          ↑

          ↓

          Если вы хотите знать метод доказательства, или подход к доказательству

          Нет, хочу посмотреть на интересный низкоуровневый код, правильность которого вы формально доказали

          • 12 апреля 2017 в 15:17

            –1

            ↑

            ↓

            Это такой странный формат аргумента «сперва добейся»? Извините, я в таких переходах на личности участия не принимаю. Спасибо.

            • 12 апреля 2017 в 15:25

              +1

              ↑

              ↓

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

        • 12 апреля 2017 в 15:35

          +2

          ↑

          ↓

          Другими словами, сами вы этого ни когда не делали. Или я не правильно понял, и вы сможете (за определённую плату) выполнять формальное доказательство, для каждого изменения кода программы. Если можете, то хотелось бы подробностей, как это делается на практике.

          • 12 апреля 2017 в 16:03

            0

            ↑

            ↓

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

    • 12 апреля 2017 в 15:08

      0

      ↑

      ↓

      Например, для написания »безопасного» кода при динамическом выделении памяти рекомендуется все же использовать функцию calloc () вместо malloc ()
      .

      Речь шла о безопасном коде, а не производительном в данном случае.

      • 12 апреля 2017 в 15:15

        0

        ↑

        ↓

        Как забивка нулями повышает безопасность? Мусор вылезет сразу, а нули будут маскировать реальную ошибку.

        • 12 апреля 2017 в 15:25

          0

          ↑

          ↓

          Отнюдь.
          Рассмотрим ситуацию, когда кусок памяти, выделяемой под строку (допустим, тот же «Hello, Habr!\n»), выглядит вот так:
          0x602010: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
          0x602018: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00

          Тогда после записи туда строки «Hello, Habr!\n» (без символа конца строки), этот кусок будет выглядеть так:
          0x602010: 0x48 0x65 0x6c 0x6c 0x6f 0x2c 0x20 0x48
          0x602018: 0x61 0x62 0x72 0x21 0x0a 0x00 0x00 0x00

          Проблем нет, если мы попробуем распечатать эту строку функцией printf (), которая выводит все символы до тех пор, пока не встретить нулевой символ (конец строки), то она дойдет до первого куска памяти, в котором есть 0×00 (14 символ), и интерпретирует его как конец строки.

          Теперь история с мусором:
          0x602010: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
          0x602018: 0x00 0x00 0x00 0x00 0x65 0x65 0x65 0x00

          Собственно, после записи:
          0x602010: 0x48 0x65 0x6c 0x6c 0x6f 0x2c 0x20 0x48
          0x602018: 0x61 0x62 0x72 0x21 0x0a 0x65 0x65 0x00

          Вывод программы:
          → Hello, Habr!
          ee

          Примерно так:)

          • 12 апреля 2017 в 15:45

            +3

            ↑

            ↓

            Запись в буфер строки без символа конца строки — это явная логическая ошибка в программе.

            • 12 апреля 2017 в 15:55

              0

              ↑

              ↓

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

              А мусор по адресу бывает нередко «похож на правду». Очень часто это может запутать.

              По поводу вашего предыдущего комментария — я, очевидно, не так прочел. Я соглашусь, что мусор вылезет сразу, а нули могут замаскировать ошибку. Тем не менее, зануление памяти в Си — очень полезная штука. Это не C# и не Java, здесь занулением никто, кроме программиста заниматься не будет.

              Проверка на пустоту массива, например, когда в нем лежит мусор будет некорректной и посчитает только что аллоцированный массив заполненным :)

© Habrahabr.ru