How is it possible to have null defernce if null is checked before-CodePudding

I have this function that searches an element in a skip list. I don't understand the error given by address sanitaizer:

==5461==ERROR: AddressSanitizer: SEGV on unknown address 0x000000000010 (pc 0x555555555e28 bp 0x7fffffffdeb0 sp 0x7fffffffde90 T0)
==5461==The signal is caused by a READ memory access.
==5461==Hint: address points to the zero page.
    #0 0x555555555e28 in search_skip_list (/home/matteo/Scrivania/Algo/laboratorio-algoritmi-2021-2022-main/Esercizio 2/ex2/build/main 0x1e28)
    #1 0x5555555556fb in main (/home/matteo/Scrivania/Algo/laboratorio-algoritmi-2021-2022-main/Esercizio 2/ex2/build/main 0x16fb)
    #2 0x7ffff73c3d8f in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #3 0x7ffff73c3e3f in __libc_start_main_impl ../csu/libc-start.c:392
    #4 0x5555555552e4 in _start (/home/matteo/Scrivania/Algo/laboratorio-algoritmi-2021-2022-main/Esercizio 2/ex2/build/main 0x12e4)

AddressSanitizer can not provide additional info.
SUMMARY: AddressSanitizer: SEGV (/home/matteo/Scrivania/Algo/laboratorio-algoritmi-2021-2022-main/Esercizio 2/ex2/build/main 0x1e28) in search_skip_list
==5461==ABORTING
[Inferior 1 (process 5461) exited with code 01]

There is a segmentation fault that I don't catch in my code. I'm new in C and I don't know how to use gdb correctly to find the problem. I put here the funtion and the way the structure are inizialized, full code is too long and the items are take by a file.

void* search_skip_list(SkipList *list, void* item){
    if(list == NULL || item == NULL ) return NULL;

    Node *x = list->head;
    
    for (int i = list->max_level-1; i >= 0; i--)
    {   
        while (x->next[i]!=NULL && strcmp(item,x->next[i]->item) < 0)
        {
           x = x->next[i];
        }  
     }
    x = x->next[0];

    if(strcmp(item,x->item) == 0) return x->item;
    else{
        return "failure";
    } 
}

struct _SkipList {
    Node *head;
    unsigned int max_level;
    int (*compare)(void*, void*);
};
struct _Node {
    Node **next;
    unsigned int size;
    void *item;
};

SkipList* create_skip_list(){
    SkipList *list = malloc(sizeof(SkipList));
    list->max_level = 0;
    list->compare = NULL;
    list->head = create_head_node(NULL,MAX_HEIGHT);
    return list;
}

Node* create_head_node(void* item, int level){
    if(level <1)
        return NULL;

    Node *node = malloc(sizeof(Node));
    if(node == NULL){
        printf("error malloc node\r\n");
        /* Returning here prevent the program from accessing non allocated
         * memory. */
        return NULL;
    }

    node->item = item;
    node->size = level;

    node->next = (Node**)malloc(level * sizeof(Node *));
    if (!node->next) {
        printf("error malloc node next\r\n");
        free(node);
        return NULL;
    }

    for (int i = 0; i < level; i  )
    {
        node->next[i] = NULL;
    }

    return node;
}

I find out that could be a deference of a NULL pointer but I don't understand how is it possible.But i think is strange cause I check first of all if there is NULL value. There is other problem that could give this error? How can I use correctly GBD to find the exactly row where the problem is?

I run gdb with a breakpoint before the function and seems to stop the first time it enter in the function, as if the first element is NULL and deference to a NULL pointer.

EDIT: i changed the create_head_node as the answer but still have the same problem.

EDIT: this is the print modified search function given in the answer

 node=0x603000000130   item=attuava

 node=0x6030000001c0   item=diguazzata

 node=0x603000000220   item=negativi
 node=0x603000000160   item=riconfessa

 node=0x603000000100   item=riparleremo

 node=0x6030000001f0   item=sparente

 node=0x6030000000d0   item=taglino
item: 0x563ae2c3e0c0
x: 0x603000000070
i: 3
x->next[3]: 0x603000000160
x->next[3]->item: 0x60c000000340
x: 0x603000000160
i: 2
i: 1
x->next[1]: 0x6030000001f0
x->next[1]->item: 0x60c0000004c0
x: 0x6030000001f0
i: 0
x->next[0]: 0x6030000000d0
x->next[0]->item: 0x60c000000100
x: 0x6030000000d0
x: 0x6030000000d0
x: (nil)
AddressSanitizer:DEADLYSIGNAL
=================================================================
==9041==ERROR: AddressSanitizer: SEGV on unknown address 0x000000000010 (pc 0x563ae2c3df03 bp 0x7ffd25e1f260 sp 0x7ffd25e1f240 T0)
==9041==The signal is caused by a READ memory access.
==9041==Hint: address points to the zero page.

CodePudding user response：

In order to prevent memory access error, I advise you to rewrite your function this way:

Node* create_head_node(void* item, int level){
    if(level <1)
        return NULL;

    Node *node = malloc(sizeof(Node));
    if(node == NULL){
        printf("error malloc node\r\n");
        /* Returning here prevent the program from accessing non allocated
         * memory. */
        return NULL;
    }

    node->item = item;
    node->size = level;

    node->next = (Node**)malloc(level * sizeof(Node *));
    if (!node->next) {
        printf("error malloc node next\r\n");
        free(node);
        return NULL;
    }

    for (int i = 0; i < level; i  )
    {
        node->next[i] = NULL;
    }

    return node;
}

Let's summarize what has changed in this snipped code:

the function returns NULL if it has not successfully allocated the node. As compared to what you have in your question, in case of allocation failure you still do access the non allocated memory and setup item and size entries.
the function checks the allocation status of the next array. In case it has failed, it frees the previously allocated memory and stops here by returning NULL.
next being an array of Node *, the data type has been set accordingly in the malloc function.

NOTE:

You also use strcmp to compare the two void *. If you want to compare array of char then you may want to cast those to char * to help read your code. Otherwise, since strcmp stops upon the first NULL byte, you should rather use memcmp and specify the size of the memory to compare.

EDIT:

Can you give the result of this slightly edited code so that we can see how it goes?

void* search_skip_list(SkipList *list, void* item){
    if(list == NULL || item == NULL ) return NULL;

    Node *x = list->head;
    if (!x) {
        printf("x is NULL\r\n");
        return NULL;
    }

    printf("item: %p\r\n", item);
    printf("x: %p\r\n", x);

    for (int i = list->max_level-1; i >= 0; i--) {
        printf("i: %d\r\n", i);

        while (x->next[i]!=NULL && strcmp(item, x->next[i]->item) < 0) {
            printf("x->next[%d]: %p\r\n", i, x->next[%d]);
            printf("x->next[%d]->item: %p\r\n", i, x->next[i]->item);

            x = x->next[i];
            printf("x: %p\r\n", x);
        }
    }
    printf("x: %p\r\n", x);

    x = x->next[0];
    printf("x: %p\r\n", x);

    if(strcmp(item,x->item) == 0) return x->item;
    else return "failure";
}

EDIT:

As per the details you provided based on my request, I understand your issue.

At the very end of the loop, you override x with x = x->next[0];. However, upon this last assignment x gets NULL (cf. the last print of the value of x). As per your structure definition, item is at offset 0x10. So accessing the value of item starting from 0 goes to 0x000000000010. There goes the error triggered by Valgrind \o/