C++ 健全性检查失败：几个 variables/memory 位置被更改为垃圾，即使我从未访问过它们

Question

我正在实施一个跳过列表。它是什么并不重要，但它现在适用于 1000 个节点，但不适用于 10000 个节点。我得到了没有意义的 SegFaults，所以我打印了一些变量。令我惊讶的是，很多不应该改变的东西变成了垃圾值。例如，我在函数 insertNode 之前和之后打印了 inputValue。它有时会重置为零，而此时应该始终递增。看代码（跳过读取文件输入，问题发生在while循环）：

int main(int argc, char** argv) {
    string filename = "";

    if( argc == 2 )
      filename = argv[1];
    else
        return 0;

    list = new skiplist();

    fstream inputFile(filename.c_str(), ios_base::in);

    inputFile >> numberofnodes;
    inputFile >> list->minimumKey;
    inputFile >> list->maximumKey;

    printf("%d\n", numberofnodes);
    printf("%d\n", list->minimumKey);
    printf("%d\n", list->maximumKey);

    list->Maxlevel = 1;

    list->header = new node();
    list->tail = new node();
    list->header->key = list->minimumKey;
    list->tail->key = list->maximumKey;


    for ( int i=1; i<=MAXIMUMLEVEL; i++ ) {
       list->header->forward[i] = list->tail;
       list->tail->forward[i] = NULL;
    }

    int sanityCheck = 134153;
    // insert nodes
    int inputKey;
    int inputValue = 0;
    int * keys = new int[numberofnodes];
    while (inputFile >> inputKey)
    {
        inputValue++;
        keys[inputValue] = inputKey;
        insertNode(inputKey, inputValue);  
        if(sanityCheck != 134153)       // dark magic changes this value
            keys[9999999999999999999999]++;  // program crashes here
                                             // it would otherwise crash on while
    }
    printf("\n\nNodes inserted: %d\n\n",inputValue);

我运行 Valgrind。无效内存 writes/read 发生在变量发生变化之后，至少我相信是这样。这就是我添加完整性检查的原因。正如我所想，在尝试访问密钥 [9999999999999999999999] 之前没有无效内存 writes/read。但是那一行只能运行更改 int sanitycheck，我从来没有这样做过。

最后，这是 insertNode 的代码。我在上面看不到任何可能导致此问题的内容：

void insertNode(int newKey, int newValue){
    node * update[MAXIMUMLEVEL];
    node * auxNode = list->header;
    for(int i=list->Maxlevel; i >=1; i--) {
        while ( auxNode->forward[i]->key < newKey ) {
            auxNode = auxNode->forward[i];
        }
        update[i] = auxNode;
    }
    auxNode = auxNode->forward[1];
    if ( auxNode->key == newKey ) {
        auxNode->value = newValue;
    } else {
        int randomLevel = 1;
        while ( (rand() / double(RAND_MAX)) < LEVELPROBABILITY && randomLevel < MAXIMUMLEVEL ) {
            randomLevel++;
        }

        if ( randomLevel > list->Maxlevel ) {
            for ( int i = list->Maxlevel+1; i <= randomLevel; i++ ) {
                update[i] = list->header;
            }
            list->Maxlevel = randomLevel;
        }
        node * newNode = new node();
        newNode->key = newKey;
        newNode->value = newValue;
        for ( int i=1; i<=MAXIMUMLEVEL; i++ ) {
            newNode->forward[i] = NULL;
        }

        for ( int i=1; i<=list->Maxlevel; i++ ) {
            newNode->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = newNode;
        }
    }
}

以及结构：

typedef struct node {
    int key;
    int value;
    node * forward[MAXIMUMLEVEL+1];
}node;

struct skiplist {
    int minimumKey;
    int maximumKey;
    int Maxlevel;
    node * header;
    node * tail;
};

EDIT:
#define MAXIMUMLEVEL 16 
#define LEVELPROBABILITY 0.5

我什至没有使用 mallocs。有指针操作，但 valgrind 应该检测我是否做了坏事，对吗？如果我运行ning 内存不足，就会出现异常。我创建但从未 access/write/change 的 int 怎么可能被修改？很抱歉 post，但我不知道问题出在哪里。

没有完整性检查的 Valgrind 输出（键[999...9]）：http://pastebin.com/hWH3fri2

第 155 行是 while (inputFile >> inputKey)

Answer 1

这是 clang 地址清理器的输出（在 setting it up properly 之后）：

==15146==ERROR: AddressSanitizer: stack-buffer-overflow on address
0x7ffeb006bb80 at pc 0x0000004e093c bp 0x7ffeb006ba60 sp 0x7ffeb006ba58

WRITE of size 8 at 0x7ffeb006bb80 thread T0
    #0 0x4e093b in insertNode(int, int) skiplist.cpp:55:27
    #1 0x4e3385 in skiplist.cpp:160:9
    #2 0x7f40b2fcda3f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x20a3f)
    #3 0x419508 in _start (a.out+0x419508)

Address 0x7ffeb006bb80 is located in stack of thread T0 at offset 160 in frame
    #0 0x4e022f in insertNode(int, int) skiplist.cpp:35

  This frams has 1 object(s):
    [32, 160) 'update' <== Memory access at offset 160 overflows this variable

第55行指的是：

void insertNode(int newKey, int newValue){
    node * update[MAXIMUMLEVEL];
    node * auxNode = list->header;
    for(int i=list->Maxlevel; i >=1; i--) {
        while ( auxNode->forward[i]->key < newKey ) {
            auxNode = auxNode->forward[i];
        }
        update[i] = auxNode;
    }
    auxNode = auxNode->forward[1];
    if ( auxNode->key == newKey ) {
        auxNode->value = newValue;
    } else {
        int randomLevel = 1;
        while ( (rand() / double(RAND_MAX)) < LEVELPROBABILITY && randomLevel < MAXIMUMLEVEL ) {
            randomLevel++;
        }

        if ( randomLevel > list->Maxlevel ) {
            for ( int i = list->Maxlevel+1; i <= randomLevel; i++ ) {
                update[i] = list->header; // line 55 <===================
            }
            list->Maxlevel = randomLevel;
        }

循环

while ( (rand() / double(RAND_MAX)) < LEVELPROBABILITY && randomLevel < MAXIMUMLEVEL ) {
    randomLevel++;
}

保证 randomLevel <= MAXIMUMLEVEL。如果randomLevel == MAXIMUMLEVEL，并且MAXIMUMLEVEL > list->Maxlevel，那么第54行的循环变成：

for ( int i = list->Maxlevel+1; i <= MAXIMUMLEVEL; i++ ) {
    update[i] = list->header; // line 55 <===================
}

请注意，update 声明为 node * update[MAXIMUMLEVEL];。您将获得越界访问权限。

我不太明白为什么你的代码似乎没有访问数组的第 0 个元素。根据我的经验，使用 [0, length_of_array) 形式的右半开范围也容易得多，这会导致

形式的循环

for(int i = 0; i < length_of_array; ++i)

请注意 < 而不是 <=。持续使用右侧半开范围可以显着减少差一错误的数量。

一个快速解决方法是声明 update 就像 node::forward 一样

node * update[MAXIMUMLEVEL + 1];

注意 +1。

更好的解决方法可能是重写代码，使其使用右侧半开范围，其中 MAXIMUMLEVEL 从范围 [0, MAXIMUMLEVEL) 中获取它的解释并且不再是最大值，而是一个上确界（并表示层数）。

C++ 健全性检查失败：几个 variables/memory 位置被更改为垃圾，即使我从未访问过它们

C++ sanity check fails: several variables/memory positions are changed to garbage, even if I never acess them

c++

pointers

sanity-check

skip-lists