Использование realloc для расширения буфера при чтении из файла дает сбой

Я пишу код, который должен читать файлы fasta, поэтому часть моего кода (приведена ниже) это парсер фаста. Поскольку одна последовательность может охватывать несколько строк в формате fasta, мне нужно объединить несколько последовательных строк, считанных из файла, в одну строку. Я делаю это, перераспределяя строковый буфер после прочтения каждой строки, чтобы получить текущую длину последовательности плюс длину прочитанной строки. Я делаю еще кое-что, например, удаляю пробелы и т. Д. первая последовательность, но файлы fasta могут содержать несколько последовательностей. Точно так же у меня есть динамический массив структур с двумя строками (заголовок и фактическая последовательность), являющимися «char *». Опять же, когда я встречаю новый заголовок (представленный строкой, начинающейся с '>'), я увеличиваю количество последовательностей и перераспределяю буфер списка последовательностей. Сбой перераспределения при выделении пространства для второй последовательности с

*** glibc detected *** ./stackoverflow: malloc(): memory corruption: 0x09fd9210 ***
Aborted

Да хоть убей, я не понимаю почему. Я запустил его через gdb, и все вроде работает (т.е. все инициализировано, значения кажутся нормальными) ... Вот код:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>
#include <errno.h>

//a struture to keep a record of sequences read in from file, and their titles
typedef struct {
    char *title;
    char *sequence;
} sequence_rec;

//string convenience functions

//checks whether a string consists entirely of white space
int empty(const char *s) {
    int i;
    i = 0;
    while (s[i] != 0) {
        if (!isspace(s[i])) return 0;
        i++;
    }
    return 1;
}

//substr allocates and returns a new string which is a substring of s from i to
//j exclusive, where i < j; If i or j are negative they refer to distance from
//the end of the s
char *substr(const char *s, int i, int j) {
    char *ret;
    if (i < 0) i = strlen(s)-i;
    if (j < 0) j = strlen(s)-j;
    ret = malloc(j-i+1);
    strncpy(ret,s,j-i);
    return ret;
}

//strips white space from either end of the string
void strip(char **s) {
    int i, j, len;
    char *tmp = *s;
    len = strlen(*s);
    i = 0;
    while ((isspace(*(*s+i)))&&(i < len)) {
        i++;
    }
    j = strlen(*s)-1;
    while ((isspace(*(*s+j)))&&(j > 0)) {
        j--;
    }
    *s = strndup(*s+i, j-i);
    free(tmp);
}


int main(int argc, char**argv) {
    sequence_rec *sequences = NULL;
    FILE *f = NULL;
    char *line = NULL;
    size_t linelen;
    int rcount;
    int numsequences = 0;

    f = fopen(argv[1], "r");
    if (f == NULL) {
        fprintf(stderr, "Error opening %s: %s\n", argv[1], strerror(errno));
        return EXIT_FAILURE;
    }
    rcount = getline(&line, &linelen, f);
    while (rcount != -1) {
        while (empty(line)) rcount = getline(&line, &linelen, f);
        if (line[0] != '>') {
            fprintf(stderr,"Sequence input not in valid fasta format\n");
            return EXIT_FAILURE;
        }

        numsequences++;
        sequences = realloc(sequences,sizeof(sequence_rec)*numsequences);
        sequences[numsequences-1].title = strdup(line+1); strip(&sequences[numsequences-1].title);
        rcount = getline(&line, &linelen, f);
        sequences[numsequences-1].sequence = malloc(1); sequences[numsequences-1].sequence[0] = 0;
        while ((!empty(line))&&(line[0] != '>')) {
            strip(&line);
            sequences[numsequences-1].sequence = realloc(sequences[numsequences-1].sequence, strlen(sequences[numsequences-1].sequence)+strlen(line)+1);
            strcat(sequences[numsequences-1].sequence,line);
            rcount = getline(&line, &linelen, f);
        }
    }
    return EXIT_SUCCESS;
}

person sirlark    schedule 23.01.2012    source источник
comment
Спасибо за все комментарии о подпрограмме подстроки. Я исправил это в своем коде. Однако я также заметил, что мой подход к отрицательным индексам был неправильным. Я должен добавлять отрицательный индекс, а не вычитать его. При этом я также понял, что скопировал функцию substr по ошибке, так как не называю ее в остальной части вставленного кода.   -  person sirlark    schedule 23.01.2012
comment
strip() тоже глючит. Он будет делать плохие вещи со строками нулевой длины. Похоже, вы не вызываете это с такими строками, но я думаю, что было бы хорошо исправить, когда он используется в другом месте.   -  person Michael Burr    schedule 23.01.2012


Ответы (3)


Я думаю, что проблема повреждения памяти может быть результатом того, как вы обрабатываете данные, используемые в ваших getline() вызовах. По сути, line перераспределяется через strndup() в вызовах strip(), поэтому размер буфера, отслеживаемый в linelen с помощью getline(), больше не будет точным. getline() может переполнить буфер.

while ((!empty(line))&&(line[0] != '>')) {

    strip(&line);    // <-- assigns a `strndup()` allocation to `line`

    sequences[numsequences-1].sequence = realloc(sequences[numsequences-1].sequence, strlen(sequences[numsequences-1].sequence)+strlen(line)+1);
    strcat(sequences[numsequences-1].sequence,line);

    rcount = getline(&line, &linelen, f);   // <-- the buffer `line` points to might be
                                            //      smaller than `linelen` bytes

}
person Michael Burr    schedule 23.01.2012
comment
Вы можете получить несколько хороших, простых, проверенных функций для обрезки строк на месте здесь: stackoverflow.com/a/2452438/12711 Использование trim() по этой ссылке решит эту проблему (и другие скрытые ошибки в функции strip()). - person Michael Burr; 23.01.2012
comment
Я исправил все проблемы с полосой (и substr), и проблема все еще оставалась. Взаимодействие с getline и linelen определенно было проблемой. Спасибо за помощь - person sirlark; 26.01.2012

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

struct string {
    int len;
    char *ptr;
};

Это предотвращает ошибки strncpy, подобные тем, которые вы, кажется, видели, и позволяет быстрее выполнять strcat и друзей.

Вы также должны использовать массив удвоения для каждой строки. Это предотвращает слишком большое количество распределений и memcpys. Что-то вроде этого:

int sstrcat(struct string *a, struct string *b)
{
    int len = a->len + b->len;
    int alen = a->len;
    if (a->len < len) {
        while (a->len < len) {
            a->len *= 2;
        }
        a->ptr = realloc(a->ptr, a->len);
        if (a->ptr == NULL) {
            return ENOMEM;
        }
    }
    memcpy(&a->ptr[alen], b->ptr, b->len);
    return 0;
}

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

struct string {
    int len;
    char ptr[0];
};

Таким образом, когда вы выделяете строковый объект, вы вызываете malloc(sizeof(struct string) + len) и избегаете второго вызова malloc. Это немного больше работы, но должно ощутимо помочь с точки зрения скорости, а также фрагментации памяти.

Наконец, если это на самом деле не является источником ошибки, похоже, что у вас есть какое-то повреждение. Valgrind поможет вам обнаружить это в случае сбоя GDB.

person leif    schedule 23.01.2012
comment
@lief: потребление памяти - это больше проблема, чем скорость. Я не хочу выделять дублирующими частями и тратить пространство впустую. По общему признанию, это проблема не в парсере fasta, больше в обработке. - person sirlark; 23.01.2012
comment
Из-за внутренней фрагментации malloc вы можете использовать слишком много памяти, даже если не запрашиваете ее. Дублирующим массивам очень доверяют, но если они слишком пугающие, пожалуйста, по крайней мере используйте что-то вроде malloc_usable_size для измерения вашей фрагментации. Если вы выберете удвоение массивов и мое второе предложение о распределении длины и строкового буфера вместе, будьте осторожны, включив длину в расчет размера, иначе вы можете получить ужасную фрагментацию (если вы выделите 2 ^ n + sizeof int , Например). - person leif; 23.01.2012
comment
char ptr[0]; недействителен C. Вы имеете в виду char ptr[];, но, вероятно, сейчас это плохое имя для элемента, поскольку это массив, а не указатель. Я бы назвал это data или contents или что-то в этом роде. - person R.. GitHub STOP HELPING ICE; 23.01.2012
comment
И нет причин думать, что выделение 2^n+sizeof int должно привести к большей фрагментации, чем выделение 2^n. Полномочия двоих особого статуса здесь не имеют. (Если вы говорите о выделениях, которые настолько велики, что их может обслуживать виртуальная машина, например mmap, они достаточно велики, чтобы даже трата целой страницы была крошечной тратой в процентном отношении, может быть, ~ 2%). - person R.. GitHub STOP HELPING ICE; 23.01.2012
comment
Если вы собираетесь реализовать свой собственный строковый тип данных более высокого уровня, вы можете рассмотреть возможность оценки большого количества существующих библиотек, которые это делают. Вот довольно хороший список некоторых из наиболее известных: and.org/vstr/comparison - person Michael Burr; 23.01.2012
comment
char p [0] работает во всех компиляторах, которые я видел. Большинство распределителей (jemalloc, dlmalloc) имеют мощность классов распределения с двумя ячейками, поэтому выделение 2 ^ n + 1 приведет к почти 100% накладным расходам фрагментации почти для всех n. - person leif; 24.01.2012

Одна потенциальная проблема здесь:

strncpy(ret,s,j-i);
return ret;

ret может не получить нулевой терминатор. См. man strncpy:

       char *strncpy(char *dest, const char *src, size_t n);

       ...

       The strncpy() function is similar, except that at most n bytes  of  src
       are  copied.  Warning: If there is no null byte among the first n bytes
       of src, the string placed in dest will not be null terminated.

Здесь также есть ошибка:

j = strlen(*s)-1;
while ((isspace(*(*s+j)))&&(j > 0)) {

Что, если strlen(*s) равно 0? Вы закончите читать (*s)[-1].

Вы также не проверяете strip(), что строка не состоит полностью из пробелов. Если это так, вы получите j < i.

edit: Только что заметил, что ваша substr() функция на самом деле не вызывается.

person NPE    schedule 23.01.2012