Почему valgrind сообщает, что glibc tsearch () случайным образом теряет память? - PullRequest
Новая
       12

Почему valgrind сообщает, что glibc tsearch () случайным образом теряет память?

0 голосов
/ 10 октября 2018

Я использую семейство API glibc tsearch() для хранения динамически размещаемых блоков данных в примере программы.

Я обнаружил, что когда я использую tsearch(), чтобы добавить несколькоmalloc() редактирует блоки в дереве, затем valgrind сообщает, что некоторые из этих блоков "возможно потеряны".Хотя «возможно потеряно» не совсем то же самое, что «определенно потеряно», предыдущий совет SO , как правило, заключается в том, чтобы выяснить причину этого.

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

#include <stdio.h>
#include <search.h>
#include <stdlib.h>
#include <signal.h>

struct data {
    int id;
    char *str;
};

static int
compare (const void *a, const void *b) {
    const struct data *data_a = a, *data_b = b;

    if (data_a->id < data_b->id) {
        return -1;
    } else if (data_a->id > data_b->id) {
        return 1;
    } else {
        return 0;
    }
}

int main (int argc, char **argv) {
    void *tree = NULL;
    struct data *d1, *d2, *d3, *d4;

    d1 = malloc(sizeof(struct data));
    d1->id = 10;
    d1->str = "Hello";
    tsearch(d1, &tree, compare);

    d2 = malloc(sizeof(struct data));
    d2->id = 30;
    d2->str = "Goodbye";
    tsearch(d2, &tree, compare);

    d3 = malloc(sizeof(struct data));
    d3->id = 20;
    d3->str = "Thanks";
    tsearch(d3, &tree, compare);

    d4 = malloc(sizeof(struct data));
    d4->id = 40;
    d4->str = "OK";
    tsearch(d4, &tree, compare);

    raise(SIGINT);

    return 0;
}

Обратите внимание, что я звоню raise(SIGINT) в конце main(), чтобы valgrind все еще мог анализировать выделенные блоки, прежде чем они неявно будут free() d.

Якомпиляция и запуск под valgrind следующим образом: 

$ gcc ts.c -o ts
$ valgrind --leak-check=full ./ts
==2091== Memcheck, a memory error detector
==2091== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==2091== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==2091== Command: ./ts
==2091== 
==2091== 
==2091== Process terminating with default action of signal 2 (SIGINT)
==2091==    at 0x4E7AE97: raise (raise.c:51)
==2091==    by 0x1088CE: main (in /home/ubuntu/ts)
==2091== 
==2091== HEAP SUMMARY:
==2091==     in use at exit: 160 bytes in 8 blocks
==2091==   total heap usage: 8 allocs, 0 frees, 160 bytes allocated
==2091== 
==2091== 24 bytes in 1 blocks are possibly lost in loss record 8 of 8
==2091==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2091==    by 0x4F59483: tsearch (tsearch.c:338)
==2091==    by 0x108801: main (in /home/ubuntu/ts)
==2091== 
==2091== LEAK SUMMARY:
==2091==    definitely lost: 0 bytes in 0 blocks
==2091==    indirectly lost: 0 bytes in 0 blocks
==2091==      possibly lost: 24 bytes in 1 blocks
==2091==    still reachable: 136 bytes in 7 blocks
==2091==         suppressed: 0 bytes in 0 blocks
==2091== Reachable blocks (those to which a pointer was found) are not shown.
==2091== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==2091== 
==2091== For counts of detected and suppressed errors, rerun with: -v
==2091== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

$

Valgrind сообщает, что один 24-байтовый блок потерян.Если я переместу raise(SIGINT) перед выделением d4 и добавлением дерева, то не будет потеряно ни одного блока.

Почему один блок теряется при добавлении 4 блоков, даже если ни один не теряется при добавлении 3 блоков

1 Ответ

0 голосов
/ 10 октября 2018

Оказывается, реализация glibc tsearch() немного капризна и может вертеть младшие разряды в указателях на блоки, которые она хранит в дереве двоичного поиска.Он использует биты младшего разряда в указателях для хранения флагов: https://code.woboq.org/userspace/glibc/misc/tsearch.c.html#341

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

#define SETRED(N) (N)->left_node |= ((uintptr_t) 0x1)
#define SETBLACK(N) (N)->left_node &= ~((uintptr_t) 0x1)

Указатели эффективно увеличиваются, что заставляет valgrind думать, что эти действительные указатели (которые хранятся в дереве tsearch()) были перезаписаны и, следовательно, могут быть потеряны .Но это не потерянные блоки - они успешно сохраняются в дереве двоичного поиска по модулю младшего бита.tsearch() выполнит необходимую маскировку этих битов при доступе к дереву.tsearch () может сделать это, потому что malloc() блоки ed обычно выровнены по крайней мере по четным адресам.

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

...