c Valgrind 大小 4 的读取无效 -> 段错误

Question

我正在尝试实现一个跳过列表，但我在插入部分时遇到问题。 Valgrind 在第 44 行给了我无效的大小 4 的读取，即这一行:

while(node->next_pointers[i] != NULL && node->next_pointers[i]->value < value)

它是由node->next_pointers[i]给出的。

void insert_to_skip_list(SkipList *skip_list, int value) {
SkipListNode* updated[skip_list->max_level + 1];
SkipListNode* node = skip_list->header;
int i;
for(i = skip_list->max_level;i >=0; i--) {
    while(node->next_pointers[i] != NULL && node->next_pointers[i]->value < value) {
        node = node->next_pointers[i];
    }
    updated[i] = node;
}
node = node->next_pointers[0];
if(node->value == value) {
    return;
}else {
    int level = decide_level(skip_list->max_level);
    if(level > skip_list->max_level) {
        level = skip_list->max_level + 1;
        skip_list->max_level = level;
        updated[level] = skip_list->header;
    }
    node->levels = level;
    node->value = value;
    for(i = 0; i <= skip_list->max_level; i++) {
        node->next_pointers[i] = updated[i]->next_pointers[i];
        updated[i]->next_pointers[i] = node;
    }
}
}

这是我的结构:

typedef struct skiplistNode {
    int value;
    int levels;
    struct skiplistNode **next_pointers;
    struct skiplistNode **prev_pointers;
} SkipListNode;

typedef struct {
   int max_level;
   SkipListNode *header;
} SkipList;

这是我得到的 valgrind 跟踪:

==5746== Invalid read of size 4
==5746==    at 0x804B56D: insert_to_skip_list (skiplist.c:44)
==5746==    by 0x404A7DA: srunner_run (check_run.c:396)
==5746==    by 0x404A892: srunner_run_all (check_run.c:587)
==5746==  Address 0x4256c34 is 0 bytes after a block of size 12 alloc'd
==5746==    at 0x402CE68: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==5746==    by 0x404A7DA: srunner_run (check_run.c:396)
==5746==    by 0x404A892: srunner_run_all (check_run.c:587)
==5746== Invalid read of size 4
==5746==    at 0x804B5AE: insert_to_skip_list (skiplist.c:50)
==5746==    by 0x404A7DA: srunner_run (check_run.c:396)
==5746==    by 0x404A892: srunner_run_all (check_run.c:587)
==5746==  Address 0x0 is not stack'd, malloc'd or (recently) free'd
==5746==
==5746==
==5746== Process terminating with default action of signal 11 (SIGSEGV)
==5746==  Access not within mapped region at address 0x0
==5746==    at 0x804B5AE: insert_to_skip_list (skiplist.c:50)
==5746==    by 0x404A7DA: srunner_run (check_run.c:396)
==5746==    by 0x404A892: srunner_run_all (check_run.c:587)
==5746==  If you believe this happened as a result of a stack
==5746==  overflow in your program's main thread (unlikely but
==5746==  possible), you can try to increase the size of the
==5746==  main thread stack using the --main-stacksize= flag.
==5746==  The main thread stack size used in this run was 8388608.
==5746==
==5746== HEAP SUMMARY:
==5746==     in use at exit: 3,542 bytes in 196 blocks
==5746==   total heap usage: 260 allocs, 64 frees, 39,914 bytes allocated
==5746==
==5746== LEAK SUMMARY:
==5746==    definitely lost: 12 bytes in 1 blocks
==5746==    indirectly lost: 0 bytes in 0 blocks
==5746==      possibly lost: 0 bytes in 0 blocks
==5746==    still reachable: 3,530 bytes in 195 blocks
==5746==         suppressed: 0 bytes in 0 blocks
==5746== Rerun with --leak-check=full to see details of leaked memory
==5746==
==5746== For counts of detected and suppressed errors, rerun with: -v
==5746== Use --track-origins=yes to see where uninitialised values come from
==5746== ERROR SUMMARY: 6 errors from 3 contexts (suppressed: 0 from 0)

编辑 感谢 jlcin，我得以转发，但我现在仍然遇到问题。

现在的代码是:

SkipListNode* updated[skip_list->max_level + 1];
SkipListNode* node = skip_list->header;
int i;
for(i = skip_list->max_level - 1; i >=0; i--) {
    while(node->next_pointers[i] != NULL && value > node->next_pointers[i]->value) {
        node = node->next_pointers[i];
    }
    updated[i] = node;
}
if(node->next_pointers[0] != NULL && node->next_pointers[0]->value == value) {
    return;
}else {
    int level = decide_level(skip_list->max_level);
    if(level > skip_list->max_level) {
        level = skip_list->max_level + 1;
        skip_list->max_level = level;
        updated[level] = skip_list->header;
    }
    for(i = skip_list->max_level -1; i >=0; i--) {
        node->next_pointers[i] = updated[i]->next_pointers[i];
        updated[i]->next_pointers[i] = node;
    }
}

还有 valgrind:

==8844== Invalid write of size 4   ==8844==    at 0x804B6D8: insert_to_skip_list (skiplist.c:59)

该行是:

node->next_pointers[i] = updated[i]->next_pointers[i];

再次感谢!

Answer 1

我看到了相差一的错误，你可以找到

SkipListNode* updated[skip_list->max_level + 1];

和

int level = decide_level(skip_list->max_level);
if(level > skip_list->max_level) {
    level = skip_list->max_level + 1;
    skip_list->max_level = level;
    updated[level] = skip_list->header;
}

在声明中，updated数组只有0到max_level索引，总共有max_level+1个元素。但在代码 level = Skip_list->max_level + 1; 中，level 的值为 max_level+1，这是一个错误的索引数组。

而且我不知道skip_list->max_level的确切含义。它是 next_pointers 的最大索引或最大大小吗？

for(i = skip_list->max_level;i >=0; i--)
    while(node->next_pointers[i]

如果是最大大小，则意味着 next_pointers 的索引只有 0 到 max_level-1，因此 next_pointers[i] 其中 i = Skip_list ->max_level 我认为是一个错误的索引。

以及第50行的错误

49 node = node->next_pointers[0];
50 if(node->value == value)

node 指针为 NULL，尝试获取 (NULL)->value 无效并导致段错误。