为什么在交换二叉树节点时 GDB 观察点会停在不相关的行上？

Question

我正在尝试交换二叉树中的两个节点A和B，以便它们实际存储在内存中的位置发生变化，但树拓扑结构没有改变。我添加了特殊处理来交换一个节点与其父节点，但它似乎仍然不起作用。我将 Valgrind 与 vgdb 一起使用，这样我就可以捕获内存错误并获得一致的地址。如果我有一棵像

这样的树

然后我尝试交换 A=40 和 B=5c，链接变得混乱。具体来说，40->right。在其上设置观察点 (watch -l)，我发现 40->right 被 memcpy 设置为 5c->right (NULL)，但随后此外，它后来被 if(a_l.left == b){ 更改为 A，这显然是不可能的。当我在汇编中使用 movq 而不是 movb 之前，我有一个观察点报告错误的行，但我很确定这次我的尺寸是正确的，因为我没有起初它没有通过任何交换，但我修复了它，现在它通过了大约一打。我在每次操作后都会对树进行理智检查，所以错误就在这里。这是我可以管理的最简单的演示：

#include <stdlib.h>
#include <string.h>
#include <assert.h>

typedef struct avl_node avl_node;
struct avl_node{
    avl_node *left, *right, *parent;
    signed char balance;
    char data[];
};

avl_node *avl_root(avl_node *n){
    while(n && n->parent){
        n = n->parent;
    }
    return n;
}

inline static int avl_check_links(avl_node *n){
    if(!n)return 1;
    if(n->left){
        if(n->left->parent != n){
            return 0;
        }
        if(!avl_check_links(n->left)){
            return 0;
        }
    }
    if(n->right){
        if(n->right->parent != n){
            return 0;
        }
        if(!avl_check_links(n->right)){
            return 0;
        }
    }
    return 1;
}

void avl_swap_nodes(avl_node *a, avl_node *b, size_t size){
    avl_node a_l = *a, b_l = *b;
    char tmp[sizeof(avl_node) + size];
    memcpy(tmp, a, sizeof(avl_node) + size);
    memcpy(a, b, sizeof(avl_node) + size);
    memcpy(b, tmp, sizeof(avl_node) + size);
    if(a_l.left){
        a_l.left->parent = b;
    }
    if(a_l.right){
        a_l.right->parent = b;
    }
    if(b_l.left){
        b_l.left->parent = a;
    }
    if(b_l.right){
        b_l.right->parent = a;
    }
    if(a_l.parent){
        if(a_l.parent->left == a){
            a_l.parent->left = b;
        }else{
            a_l.parent->right = b;
        }
    }
    if(b_l.parent){
        if(b_l.parent->left == b){
            b_l.parent->left = a;
        }else{
            b_l.parent->right = a;
        }
    }
    if(a_l.parent == b){
        if(b_l.left == a){
            b->left = a_l.left;
            a->left = b;
        }else{
            b->right = a_l.right;
            a->right = b;
        }
        a->parent = b_l.parent;
        b->parent = a;
    }else if(b_l.parent == a){//GDB stops here on a watch -l a->right
        if(a_l.left == b){
            a->left = b_l.left;
            b->left = a;
        }else{
            a->right = b_l.right;
            b->right = a;
        }
        b->parent = a_l.parent;
        a->parent = b;
    }
    assert(avl_check_links(avl_root(a)));
    assert(avl_check_links(avl_root(b)));
}

int main(void){
    avl_node a, b, c, d;
    a = (avl_node){.right=&b};
    b = (avl_node){.left=&c, .right=&d, .parent=&a};
    c = (avl_node){.parent=&b};
    d = (avl_node){.parent=&b};
    assert(avl_check_links(avl_root(&a)));
    avl_swap_nodes(&b, &c, 0);
}

为什么GDB停在错误的行上？我认为这可能与我使用 vgdb 的事实有关：当我单步执行时它也会跳过一些行。还有为什么 a->right 会第二次改变？谢谢。

您可以通过 gcc -g -o main main.c、valgrind --vgdb=yes --vgdb-error=0 ./main&、gdb main、[=30] 使用较新版本的 gcc、gdb 和 valgrind 将此文件复制到运行 =]、b avl_swap_nodes、c、watch -l a->right，然后通过重复执行 c 然后 Ctrl-d 或 kill 巧妙地摆脱 vgdb 进程] 然后 Ctrl-d.

Answer 1

我想通了，但这并不有趣，所以我要回答我自己的问题。节点交换代码错误。这是一个有效的版本

#include <stddef.h>
void avl_swap_nodes(avl_node *a, avl_node *b, size_t size){
    avl_node a_l = *a, b_l = *b;
    char tmp[offsetof(avl_node, data) + size];
    memcpy(tmp, a, offsetof(avl_node, data) + size);
    memcpy(a, b, offsetof(avl_node, data) + size);
    memcpy(b, tmp, offsetof(avl_node, data) + size);
    if(a_l.parent == b){
        if(b_l.left == a){
            a->left = b;
        }else{
            a->right = b;
        }
        b->parent = a;
        if(a->parent){
            if(a->parent->left == b){
                a->parent->left = a;
            }else{
                a->parent->right = a;
            }
        }
    }else if(b_l.parent == a){
        if(a_l.left == b){
            b->left = a;
        }else{
            b->right = a;
        }
        a->parent = b;
        if(b->parent){
            if(b->parent->left == a){
                b->parent->left = b;
            }else{
                b->parent->right = b;
            }
        }
    }else{
        if(a->parent){
            if(b->parent == a->parent){
                if(a->parent->left == b){
                    a->parent->left = a;
                    b->parent->right = b;
                }else{
                    a->parent->right = a;
                    b->parent->left = b;
                }
            }else{
                if(a->parent->left == b){
                    a->parent->left = a;
                }else{
                    a->parent->right = a;
                }
            }
        }
        if(b->parent && b->parent != a->parent){
            if(b->parent->left == a){
                b->parent->left = b;
            }else{
                b->parent->right = b;
            }
        }
    }
    if(a->left){
        a->left->parent = a;
    }
    if(a->right){
        a->right->parent = a;
    }
    if(b->left){
        b->left->parent = b;
    }
    if(b->right){
        b->right->parent = b;
    }
    ASSERT_ALL(avl_root(a));
    ASSERT_ALL(avl_root(b));
}

GDB 在错误的行上报告观察点的原因是因为先前的内存写入溢出。例如，当您在汇编中使用 movq 而不是 movb 时，或者当您在 C 中执行 char a; ((int*)&a) = (int)0; 时，或者当您 memcpy 超出预期时，就会发生这种情况。最后一个是导致我的代码出现问题的原因。考虑结构 struct A{int a; char b[];);。 sizeof(struct A) 可能是 8，因为结构填充，但 offsetof(struct A, b) 可能是 4。因此，如果我们通过添加数据大小为 sizeof(struct A)，我们将计算出比应有值大 4 个字节的值。解决方案是改用offsetof(struct A, b);。

GDB 跳行的原因是因为我使用的是 valgrind --vgdb=yes 而不是 valgrind --vgdb=full。

为什么在交换二叉树节点时 GDB 观察点会停在不相关的行上？

Why does a GDB watchpoint stop on an irrelevant line when swapping binary tree nodes?

c

binary-tree

gdb

valgrind

watchpoint