c Valgrind Invalid read of size 4 -> segmentation fault

Question

I'm trying to implement a skip list but I'm having problems with the insert part of it. Valgrind gives me invalid read of size 4 at row 44 which is this line:

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

And it's the node->next_pointers[i] which gives it.

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;
    }
}
}

Here are my structs:

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

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

And this is the valgrind trace that i got:

==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)

EDIT I got forward thanks to jlcin but I got now still a problem with this.

The code is now:

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;
    }
}

And valgrind:

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

That line is:

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

Thanks again!

Answer 1

I see off-by-one bug, you can find

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

and

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;
}

In the declaration, the updated array has only 0 to max_level index, and totally has max_level+1 elements. But in the code level = skip_list->max_level + 1;, the value of level is max_level+1, which is an wrong index of the array.

And I don't know the exact meaning of skip_list->max_level. Is it the maximum index or maximum size of next_pointers?

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

If it is the maximum size, then it mean next_pointers only has index 0 to max_level-1, therefore, next_pointers[i] where i = skip_list->max_level is a wrong index I think.

And the error of line 50

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

node pointer is NULL and trying to get (NULL)->value is invalid and causes the segfault.