Непрерывная замена строки вызывает недопустимое чтение в C

Question

Я пытаюсь реализовать функцию replace в C.

У меня есть replace_str(char *str, char *sub, char *replacement) функция, которая возвращает char * в измененную строку.

Вот функции:

#define ALLOC(size, type) (type *) calloc(size, sizeof(type))
#define REALLOC(ptr, new_size, type) (type *) realloc(ptr, new_size * sizeof(type))

/**
 * Replaces all occurrences of given substring in string with given replacement.
 * @param str A dynamically allocated string that will be modified.
 * @param sub Old substring to be replaced.
 * @param replacement New substring.
 * @return The modified string.
 */
char *replace_str(char *str, char *sub, char *replacement) {
    unsigned long len_sub = strlen(sub);
    unsigned long len_rep = strlen(replacement);

    if (len_sub != len_rep) {
        unsigned long new_len = strlen(str) + (len_rep - len_sub) * count_substring(str, sub) + 1;
        str = REALLOC(str, new_len, char);
    }

    char *ptr = strstr(str, sub);
    while (ptr != NULL) {
        char *str_tail = ptr + len_sub;
        char *temp_tail = ALLOC(strlen(str_tail) + 1, char);
        strcpy(temp_tail, str_tail);
        strcpy(ptr, replacement);
        strcat(str, temp_tail);
        free(temp_tail);
        ptr = strstr(ptr + len_rep, sub);
    }

    return str;
}

/* Counts number of non-overlapping times given substring mentioned in string. */
unsigned int count_substring(char *str, char *sub) {
    unsigned int count = 0;
    unsigned long sub_len = strlen(sub);

    while (*str != '\0') {
        if (strncmp(str++, sub, sub_len) != false)
            continue;
        str += sub_len - 1;
        count++;
    }

    return count;
}

Это работает хорошо, но когда у меня что-то вроде этого:

char *a = ALLOC(11, char);
strcpy(a, "\n\n\n\n\n\n\n\n\n\n");

while (CONTAINS(a, "\n\n")) {
    a = replace_str(a, "\n\n", "\n");
}

free(a);

Valgrind жалуется, что есть недопустимые чтения:

==896== Memcheck, a memory error detector
==896== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==896== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==896== Command: /mnt/d/archive/education/hu/assignments/fall2019/assignment1/cmake-build-debug/matrixman ../inputs/arrays ../inputs/IO/commands1.txt output1.txt
==896==
==896== Invalid read of size 1
==896==    at 0x4C32D04: strlen (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==896==    by 0x1091F2: replace_str (strutils.h:140)
==896==    by 0x109496: main (main.c:33)
==896==  Address 0x522d096 is 0 bytes after a block of size 6 alloc'd
==896==    at 0x4C31D2F: realloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==896==    by 0x1091B7: replace_str (strutils.h:134)
==896==    by 0x109496: main (main.c:33)
==896==
{
   <insert_a_suppression_name_here>
   Memcheck:Addr1
   fun:strlen
   fun:replace_str
   fun:main
}
==896== Invalid read of size 1
==896==    at 0x4C32E03: strcpy (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==896==    by 0x10921A: replace_str (strutils.h:141)
==896==    by 0x109496: main (main.c:33)
==896==  Address 0x522d096 is 0 bytes after a block of size 6 alloc'd
==896==    at 0x4C31D2F: realloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==896==    by 0x1091B7: replace_str (strutils.h:134)
==896==    by 0x109496: main (main.c:33)
==896==
{
   <insert_a_suppression_name_here>
   Memcheck:Addr1
   fun:strcpy
   fun:replace_str
   fun:main
}
==896== Invalid read of size 1
==896==    at 0x4C32CF2: strlen (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==896==    by 0x1091F2: replace_str (strutils.h:140)
==896==    by 0x109496: main (main.c:33)
==896==  Address 0x522d272 is 0 bytes after a block of size 2 alloc'd
==896==    at 0x4C31D2F: realloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==896==    by 0x1091B7: replace_str (strutils.h:134)
==896==    by 0x109496: main (main.c:33)
==896==
{
   <insert_a_suppression_name_here>
   Memcheck:Addr1
   fun:strlen
   fun:replace_str
   fun:main
}
==896== Invalid read of size 1
==896==    at 0x4FB7950: __strcpy_ssse3 (strcpy-ssse3.S:32)
==896==    by 0x10921A: replace_str (strutils.h:141)
==896==    by 0x109496: main (main.c:33)
==896==  Address 0x522d272 is 0 bytes after a block of size 2 alloc'd
==896==    at 0x4C31D2F: realloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==896==    by 0x1091B7: replace_str (strutils.h:134)
==896==    by 0x109496: main (main.c:33)
==896==
{
   <insert_a_suppression_name_here>
   Memcheck:Addr1
   fun:__strcpy_ssse3
   fun:replace_str
   fun:main
}
==896==
==896== HEAP SUMMARY:
==896==     in use at exit: 0 bytes in 0 blocks
==896==   total heap usage: 9 allocs, 9 frees, 34 bytes allocated
==896==
==896== All heap blocks were freed -- no leaks are possible
==896==
==896== For counts of detected and suppressed errors, rerun with: -v
==896== ERROR SUMMARY: 6 errors from 4 contexts (suppressed: 0 from 0)

Это также происходит, когда яиспользуйте replace_str в рекурсивной функции.

Как я могу решить эту проблему? Что я не вижу?

Answer 1

Ниже я использую термин needle, означающий аргумент sub, переданный функции replace_str.

unsigned long new_len = strlen(str) + (len_rep - len_sub) * count_substring(str, sub) + 1;
str = REALLOC(str, new_len, char);

len_rep равен strlen("\n"), поэтому 1.
len_sub равно strlen("\n\n"), то есть 2.

То есть (len_rep - len_sub) равно -1, поэтому оно равно:

unsigned long new_len = strlen(str) + (-1) * count_substring(str, sub) + 1;

Предполагается, что count_substring делает то, что говоритда, вы realloc делаете строку меньшего размера, даже не обращаясь к ней, поэтому вы аннулируете все байты после new_len. Это означает, что если строка "\n\n\n\n\n\n\n\n\n\n", а needle - "\n\n", существует 5 таких последовательностей, вы просто перераспределяете строку на 6 байтов. Таким образом, результирующий массив составляет всего 6 байтов \n: {'\n,'\n','\n','\n','\n','\n'}. Все байты после индекса 5 являются недопустимыми, и доступ к ним является неопределенным поведением. Valgrind точно ошибается, когда вы обращаетесь к байтам после выделенной памяти:

==896==  Address 0x522d096 is 0 bytes after a block of size 6 alloc'd
==896==    at 0x4C31D2F: realloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)

Что вы должны сделать, это если строка замены короче стрелки, переместить realloc после цикла. Если замена длиннее, чем стрелка, сделайте realloc перед циклом.

if (len_rep > len_sub) {
    // WE NEED MORE PLACE
    const size_t new_len = strlen(str) + (len_rep - len_sub) * count_substring(str, sub) + 1;
    str = REALLOC(str, new_len, char);
    if (str == NULL) abort();
}

while (strstr(str, needle)) {
    // your loop is here
}

if (len_rep < len_sub) {
    // WE NEED LESS PLACE
    const size_t new_len = strlen(str) + (len_rep - len_sub) * count_substring(str, sub) + 1;
    str = REALLOC(str, new_len, char);
    if (str == NULL) abort();
}

Примечания:

• Не забудьте проверить наличие ошибок выделения.
• Objectразмер и длина строки представлены с использованием типа size_t.
• Ваша функция работает странно. Нет необходимости делать malloc внутри while, вам не нужна временная строка. Просто memove части строки, которые вы должны сохранить. И memcpy иголка внутри струны там, где она вам нужна. Прямо как while (str = strstr(str, needle), str) { memmove( <move str forth or back depending if len_rep is greater or smaller or equal to len_sub> ); memcpy(str, needle, strlen(needle)); str += strlen(needle); }.