跳表搜索函数空指针解引用致Segmentation Fault问题求助

问题背景 #

编写跳表元素搜索函数时遇到AddressSanitizer（ASAN）报出的段错误，无法定位具体问题。ASAN错误信息如下：

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

刚接触C语言，不会用GDB定位问题，已在函数开头做空值检查，但仍出现空指针解引用。相关代码如下：

搜索函数 #

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

调试补充打印信息 #

修改后添加打印，输出显示最终x变为空指针：

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.

问题原因分析 #

从打印信息可以明确：

1. 循环结束后执行x = x->next[0]，此时x变为空指针(nil)
2. 后续调用strcmp(item,x->item)时，尝试访问空指针的item成员（偏移地址0x10，与ASAN报错地址一致），直接触发段错误

另外还有一个潜在风险：create_skip_list中初始化list->max_level = 0，但头节点的层级是MAX_HEIGHT，若未在插入节点时更新max_level，会导致搜索循环的i从-1开始，触发x->next[-1]数组越界访问。

修复方案 #

修改搜索函数，在访问x->item前先检查x是否为空：

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(x != NULL && strcmp(item,x->item) == 0) {
        return x->item;
    } else {
        return "failure";
    } 
}

同时需确保在跳表插入节点时，正确更新list->max_level的值，避免出现层级不匹配的问题。

GDB定位问题的正确步骤 #

• 编译时添加调试信息：编译代码时加上-g参数保留调试符号，示例命令：

  gcc -g -fsanitize=address your_code.c -o main
  

• 启动GDB：运行gdb ./main进入调试环境
• 设置断点：在搜索函数入口设置断点，输入b search_skip_list
• 运行程序：输入run启动程序，程序会在断点处暂停
• 单步执行：
  • 输入n（next）执行下一行代码
  • 输入s（step）进入函数调用（比如进入strcmp）
• 查看变量值：
  • 输入p x查看指针x的值
  • 输入p x->next[0]查看next指针内容
  • 输入p x->item查看节点存储的元素
• 程序崩溃后：输入bt（backtrace）查看调用栈，确认崩溃发生的具体行

内容的提问来源于stack exchange，提问作者Matteo Pagliarello