x86-64汇编实现快排 调用含fprintf的C函数触发段错误

问题现象 #

在Linux平台用x86-64汇编实现快速排序，partition子逻辑用C编写，程序初始可正常运行。但在C实现的partition函数中加入fprintf调用后会触发段错误：

• 仅当给printf/fprintf这类可变参数函数传入格式字符串之外的额外参数时才会崩溃
• 仅传入格式字符串时，函数可正常执行

环境与编译运行方式 #

• 系统：Ubuntu 20.04.1
• 编译器：GCC 9.4.0
• 编译命令：gcc quicksort.c quicksort.s -o quicksort
• 运行命令：./quicksort

相关代码 #

C版本快排基准逻辑：

void quicksort(int* arr, size_t n) {
    if (n <= 1) return;
    int p = partition(arr, n);
    quicksort(arr, p);
    p += 1;
    quicksort(arr+p, n-p);
}

汇编实现quicksort.s：

# quicksort.s
# 原注释存在笔误：第一个参数（数组指针）存于%rdi，第二个参数（数组长度）存于%rsi
.global quicksort
quicksort:
    cmpq $1, %rsi
    jle early_exit

    pushq %rbp
    movq %rsp, %rbp

    # rbx、r12、r13为被调用者保存寄存器
    pushq %rbx
    pushq %r12
    pushq %r13

    # 将入参存入被调用者保存寄存器，避免子函数调用覆盖
    movq %rdi, %rbx
    movq %rsi, %r12

    # 调用p = partition(arr, n)
    call partition
    movq %rax, %r13

    # 递归调用quicksort(arr, p)
    movq %rbx, %rdi
    movq %r13, %rsi
    call quicksort

    # p += 1
    addq $1, %r13

    # 递归调用quicksort(arr+p*sizeof(int), n-p)
    leaq (%rbx, %r13, 4), %rdi
    movq %r12, %rsi
    subq %r13, %rsi
    call quicksort

    # 恢复寄存器
    popq %r13
    popq %r12
    popq %rbx

    movq %rbp, %rsp
    popq %rbp

early_exit:
    ret

C实现quicksort.c，注释fprintf行时段错误消失：

// quicksort.c
#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>

void quicksort(int* arr, size_t n);

size_t partition(int* arr, size_t n) {
    // 注释掉下一行段错误即消失
    fprintf(stderr, "%d", 10);

    size_t l = 1;
    size_t r = n;
    int p = arr[0];

    while (l < r) {
        while (l < r && arr[l] <= p) l++;
        while (l < r && arr[r-1] > p) r--;
        if (l == r) break;
        int temp = arr[l];
        arr[l] = arr[r-1];
        arr[r-1] = temp;
        l++;
        r--;
    }
    arr[0] = arr[r-1];
    arr[r-1] = p;
    return r-1;
}

int main() {
    #define LEN 100
    int arr[LEN] = { };

    for (int i = 0; i < LEN; ++i)
        arr[i] = rand();

    quicksort(arr, LEN);

    for (int i = 0; i < LEN; ++i)
        printf(" %d", arr[i]);
    putchar('\n');
}

根因 #

问题出在没有遵守x86-64 System V ABI的函数调用约定：调用任何函数前，栈指针%rsp必须保持16字节对齐。
栈对齐的计算逻辑：

1. 执行call指令调用函数时，硬件会自动压入8字节的返回地址，因此函数入口处%rsp的值模16余8，这是所有函数的初始栈状态
2. 原汇编代码进入quicksort后，首先压入8字节的%rbp，此时%rsp模16为0，栈是对齐的
3. 之后连续压入%rbx、%r12、%r13三个8字节寄存器，合计24字节，此时%rsp总共偏移了8（返回地址）+8（%rbp）+24（三个寄存器）=40字节，40模16余8，栈处于不对齐状态
4. 此时调用partition，如果partition内部调用可变参数函数时需要处理额外传入的参数，GCC生成的代码会使用movaps等要求内存地址16字节对齐的SSE指令，栈不对齐时这类指令会直接触发段错误；如果仅传入格式字符串、没有额外可变参数，函数不会执行这类对齐敏感的操作，因此可以正常运行。

修复方法 #

在函数序言阶段调整栈指针，保证所有子函数调用点的%rsp满足16字节对齐要求。最简单的修复是在压入三个被调用者保存寄存器前，额外预留8字节栈空间，保证栈总偏移为16的整数倍。
修正后的汇编代码序言和尾声部分：

quicksort:
    cmpq $1, %rsi
    jle early_exit

    pushq %rbp
    movq %rsp, %rbp
    subq $8, %rsp  # 额外预留8字节，保证后续压栈后栈对齐

    pushq %rbx
    pushq %r12
    pushq %r13

    # 中间逻辑不变

    popq %r13
    popq %r12
    popq %rbx
    addq $8, %rsp  # 释放之前预留的8字节空间

    movq %rbp, %rsp
    popq %rbp

early_exit:
    ret

修复后栈总偏移为8（返回地址）+8（%rbp）+8（预留空间）+24（三个寄存器）=48字节，48是16的整数倍，满足对齐要求，段错误即可消除。

内容的提问来源于stack exchange，提问作者Sebastián Mestre