我试图在Linux上的x86-64汇编程序中实现快速排序。由于我还没有完全适应它,所以我用C编写了分区算法。它似乎可以工作,但必须关闭,因为在我的C代码中添加对fprintf
的调用( Asm调用到的)会导致分段错误。我想我一定是搞砸了堆栈,或者没有遵守调用约定,但我不知道在哪里。
值得注意的是,只有当额外的参数传递给printf时,分段错误才会发生。如果只传递格式字符串,它就能正常工作。
有两个文件:quicksort.s
和quicksort.c
。我在GCC 9.4.0上用命令gcc quicksort.c quicksort.s -o quicksort
在Ubuntu20.04.1下编译了它们,然后使用./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);
}
然后将其转换为x86-64汇编程序,得到如下结果:
# quicksort.s
# Takes an array of integers in %rsi
# Takes the size of the array in %rsi
.global quicksort
quicksort:
cmpq $1, %rsi
jle early_exit
pushq %rbp
movq %rsp, %rbp
# rbx, r12 and r13 are callee-saved
pushq %rbx
pushq %r12
pushq %r13
# put arguments in callee-saved registers for later use
movq %rdi, %rbx
movq %rsi, %r12
# p = partition(arr, n)
call partition
# put result of partition in callee-saved register for later use
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
#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
void quicksort(int* arr, size_t n);
size_t partition(int* arr, size_t n) {
// commenting the next line fixes the segfault
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');
}
发布于 2022-06-27 23:48:48
你没有维护堆栈对齐。ABI指出,%rsp
必须总是在call
指令之前为16的倍数。call
本身推送一个8字节的数量(返回地址),因此堆栈指针在函数输入时总是与8 (mod 16)一致,在进行另一次调用之前修复它是您的责任。
只有当对fprintf
的调用没有注释时,这才会导致崩溃,因为fprintf
实际上正在做一些利用ABI需求的事情(具体来说,使用一些x86-64矢量指令,可能是为了加速二进制到十进制的转换)。partition
本身并没有做任何关心的事情。
对您来说,最简单的修复方法是丢弃帧指针。在x86-64上它不是必需的,这样你就会推出一个奇数的寄存器,这会给你适当的堆栈对齐作为一个副作用。
发布于 2022-06-27 23:43:36
对于call partition
,堆栈没有对齐,这意味着它在fprintf
中也不会对齐,该函数依赖于哪个(因为ABI授权每个函数)。在此之前执行sub $8, %rsp
或多一个虚拟push
来对齐它,然后再撤消它。
https://stackoverflow.com/questions/72779267
复制相似问题