使用内联RISC-V汇编实现链表归并排序：合并阶段崩溃问题

我用内联RISC-V汇编实现链表归并排序，其余部分运行正常，但编写链表合并逻辑时遇到问题：取消注释sw a0, 8(t1);后程序直接崩溃。

函数代码 #

typedef struct Node {
  int data;
  struct Node *next;
} Node;

// Merge two sorted linked lists
Node *mergeSortedLists(Node *a, Node *b) {
  Node *result = NULL;
  Node *tail = NULL;

  asm volatile(
      // init
      "mv t2, %2;" // t2 = a
      "mv t3, %3;" // t3 = b

      "merge_sort:"
      "beqz t2, b_rest;" // if a is empty, put b at the end of list
      "beqz t3, a_rest;" // if b is empty, put a at the end of list

      // take the head elements of a and b
      "lw a2, 0(t2);" // a2 = t2(a) -> data
      "lw a3, 0(t3);" // a3 = t3(b) -> data

      "ble a2, a3, select_a;"
      // select b
      "mv a1, a3;"
      "lw t3, 8(t3);"
      "j post_select;"

      // select a
      "select_a:"
      "mv a1, a2;"
      "lw t2, 8(t2);"

      // post select process
      "post_select:"
      "beqz t0, set_head;" // if head is nullptr, it should be set
      "li a0, 16;"         // set new node (a0) size
      "call malloc;"       // malloc new node (a0)
      "sw a1, 0(a0);"      // a0 -> data = a1
      // everything crush if I uncomment these 2 line
      // "sw a0, 8(t1);"      // t1(tail) -> next = a1
      // "mv t1, a0;"         // t1(tail) = t1(tail) -> next
      "j merge_sort;"

      // set_head
      "set_head:"
      "li t1, 16;"
      "call malloc;"
      "sw a1, 0(t1);"
      "mv t0, t1;"
      // "mv %0, t0;"
      // "mv t1, a0;"
      "j merge_sort;"

      // put a at the end of list
      "a_rest:"
      // "sw t3, 8(t1);"
      "j merge_end;"

      // pub b at the end of list
      "b_rest:"
      // "sw t4, 8(t1);"

      "merge_end:"
      "mv %0, t0;"
      "mv %1, t1;"
      : "=r"(result), "=r"(tail)
      : "r"(a), "r"(b)
      : "t0", "t1", "t2", "t3", "t4", "t5", "t6", "a0", "a1", "a2", "a3",
        "memory");

  return result;
}

崩溃时的寄存器输出 #

z  0000000000000000 ra 0000000000010656 sp 0000003ffffff840 gp 000000000008e0a0
tp 0000000000093760 t0 00000000000957d0 t1 000000000000000f t2 00000000000957d0
s0 0000003ffffff880 s1 0000000000000002 a0 0000000000094bd0 a1 0000000000000000
a2 000000000008cc90 a3 000000000008c690 a4 0000000000000000 a5 0000000000000000
a6 0000000000000003 a7 0000000000000001 s2 0000000000000002 s3 0000003ffffffb38
s4 0000003ffffffb50 s5 0000000000000002 s6 0000000000010472 s7 0000000000010200
s8 000000000000003a s9 0000000000092680 sA 0000000000000000 sB 0000000000000000
t3 0000000000000000 t4 000000000008cc80 t5 0000000000000008 t6 000000000008d778
pc 000000000001065a va/inst 0000000000000017 sr 8000000200006620
User store segfault @ 0x0000000000000017

已尝试的方法 #

• 复用原节点：触发段错误
• 重置取出节点的next成员：出现无限循环，输出结果为abababab

环境信息 #

• 编译：riscv64-unknown-linux-gnu-gcc
• 测试：spike --isa=RV64GCV $RISCV/riscv64-unknown-linux-gnu/bin/pk

问题排查与修复 #

核心错误点

1. t1寄存器初始化逻辑错误：set_head块中li t1, 16把节点大小直接赋值给t1，而非让t1指向malloc返回的新节点。这导致后续sw a0, 8(t1)尝试往地址0x10+8=0x17写数据，正好对应崩溃信息中的地址。
2. malloc调用参数错误：set_head块中调用malloc前未正确设置a0为节点大小，反而错误地用t1传参，违反RISC-V调用约定。
3. 新节点next字段未初始化：分配新节点后未将next置为nullptr，会导致野指针问题。
4. 剩余节点拼接逻辑缺失：a_rest和b_rest块的代码被注释，无法将剩余链表接到结果尾部。
5. 尾节点更新注释错误：注释中写t1(tail) -> next = a1，但a1是数据值而非节点地址，实际应该写入a0（新节点地址）。

修复后的汇编核心代码

// init
"mv t2, %2;" // t2 = a
"mv t3, %3;" // t3 = b
"mv t0, zero;" // 显式初始化结果头指针为null
"mv t1, zero;" // 显式初始化尾指针为null

"merge_sort:"
"beqz t2, b_rest;" // a为空，拼接剩余b
"beqz t3, a_rest;" // b为空，拼接剩余a

// 取a、b的头节点数据
"lw a2, 0(t2);" // a2 = a->data
"lw a3, 0(t3);" // a3 = b->data

"ble a2, a3, select_a;"
// 选择b的节点
"mv a1, a3;"
"lw t3, 8(t3);" // b移动到下一个节点
"j post_select;"

// 选择a的节点
"select_a:"
"mv a1, a2;"
"lw t2, 8(t2);" // a移动到下一个节点

// 处理选中的节点
"post_select:"
"beqz t0, set_head;" // 结果为空则设置头节点

// 分配新节点
"li a0, 16;"         // 节点大小传入a0
"call malloc;"       // a0 = 新节点地址
"sw a1, 0(a0);"      // 新节点写入数据
"sw zero, 8(a0);"    // 初始化next为nullptr

// 更新尾节点
"sw a0, 8(t1);"      // 尾节点的next指向新节点
"mv t1, a0;"         // 尾节点移动到新节点
"j merge_sort;"

// 设置结果头节点
"set_head:"
"li a0, 16;"         // 节点大小传入a0
"call malloc;"       // a0 = 新节点地址
"sw a1, 0(a0);"      // 新节点写入数据
"sw zero, 8(a0);"    // 初始化next为nullptr
"mv t0, a0;"         // 头指针指向新节点
"mv t1, a0;"         // 尾指针也指向新节点
"j merge_sort;"

// 拼接剩余a链表
"a_rest:"
"beqz t1, merge_end;" // 结果为空则直接结束（此时a为空）
"sw t2, 8(t1);"      // 尾节点next指向剩余a
"j merge_end;"

// 拼接剩余b链表
"b_rest:"
"beqz t1, set_rest_head;" // 结果为空时，b直接作为头节点
"sw t3, 8(t1);"      // 尾节点next指向剩余b
"j merge_end;"

// 结果为空时设置b为头节点，并更新尾指针到b的末尾
"set_rest_head:"
"mv t0, t3;"         // 头指针指向b
"mv t1, t0;"         // 尾指针初始指向b
"rest_loop:"
"lw t4, 8(t1);"
"beqz t4, merge_end;"
"mv t1, t4;"
"j rest_loop;"

"merge_end:"
"mv %0, t0;"
"mv %1, t1;"

额外注意事项

• 遵循RISC-V调用约定：a0-a7用于参数传递和返回值，调用malloc时必须将大小传入a0，返回的节点地址存在a0中。
• 边界情况处理：必须考虑输入链表为空、结果链表为空的场景，避免空指针访问。
• 野指针预防：所有新分配或复用的节点，必须确保next字段被正确初始化（置为nullptr或指向合法节点）。

内容的提问来源于stack exchange，提问作者澪人桐