c - 为什么valgrind报告glibc tsearch()随机泄漏内存？

我正在使用glibc tsearch() API系列在示例程序中存储动态分配的数据块。

我发现当我使用tsearch()向树中添加几个malloc() ed块时，valgrind将其中一些块报告为“可能丢失”。虽然“可能丢失”与“绝对丢失”并不完全相同，但是previous SO advice通常是调查造成这些错误的原因。

我的示例程序如下:

#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个块也没有丢失？

最佳答案

事实证明，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()树中)已经是overwritten and therefore possibly lost。但是，这些不是丢失的块-它们以低位为模，已成功存储在二进制搜索树中。当访问树时，tsearch()将对这些位进行必要的屏蔽。 tsearch()可以执行此操作，因为malloc()编码的块通常至少与偶数地址对齐。

只有在二进制树中标记为“红色”节点的块才设置了此位，因此其模式是否“可能丢失”完全取决于实现过程中如何将块归类为“红色”或“黑色”添加，删除和重新平衡操作。

因此tsearch()的混乱使valgrind错误地认为这些块已丢失。在这种情况下，valgrind报告了误报。