0

我正在实施一个跳过列表。它是什么并不重要，但它现在适用于 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。无效的内存写入/读取发生在变量发生变化之后，至少我相信如此。这就是我添加完整性检查的原因。正如我所想的那样，在尝试访问密钥之前没有无效的内存写入/读取[9999999999999999999999]。但是该行只能运行 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

我什至没有使用 malloc。有指针操作，但是 valgrind 应该检测我是否做错了什么，对吗？如果我的内存不足，就会出现异常。我创建但从不访问/写入/更改的 int 怎么可能被修改？对不起，很长的帖子，但我不知道问题可能出在哪里。

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

第 155 行是 while (inputFile >> inputKey)

4

1 回答 1

0

这是 clang 的地址清理程序的输出（正确设置后）：

==15146==错误：AddressSanitizer：地址上的堆栈缓冲区溢出
0x7ffeb006bb80 在 pc 0x0000004e093c bp 0x7ffeb006ba60 sp 0x7ffeb006ba58

在 0x7ffeb006bb80 线程 T0 写入大小 8
    #0 0x4e093b in insertNode(int, int) skiplist.cpp:55:27
    #1 0x4e3385 在 skiplist.cpp:160:9
    #2 __libc_start_main 中的 0x7f40b2fcda3f (/lib/x86_64-linux-gnu/libc.so.6+0x20a3f)
    #3 0x419508 in _start (a.out+0x419508)

地址 0x7ffeb006bb80 位于线程 T0 的堆栈中，在帧中偏移 160
    #0 0x4e022f in insertNode(int, int) skiplist.cpp:35

  此框架有 1 个对象：
    [32, 160) 'update' <== 偏移 160 处的内存访问会溢出此变量

第 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)不再是最大值，而是上界（并表示级别数）。

于 2015-04-30T02:35:43.190 回答