构建具有递归功能的.so [英] Building .so with recursive function in it

问题描述

在进行某些项目期间，我遇到了无法构建库的问题.我遇到类似这样的错误:制作共享库时，不能使用针对符号''的 relocation R_X86_64_PC32；用-fPIC 重新编译 最终，我设法找到了根本原因.它是库中的递归函数.例如，我有以下众所周知的示例:

.section .text
.globl factorial
.type  factorial,STT_FUNC
factorial:
    push %rbp
    mov %rsp,%rbp

    mov 16(%rbp),%rax
    cmp $1,%rax
    je end_factorial
    dec %rax
    push %rax  #this is how we pass the argument to function
    call factorial
    pop %rbx
    inc %rbx
    imul %rbx,%rax
end_factorial:
    mov %rbp, %rsp
    pop %rbp
    ret

现在，让我们尝试构建共享库:

as  -g -o fact.o fact.s
ld -shared fact.o -o libfact.so
ld: fact.o: relocation R_X86_64_PC32 against symbol `factorial' can not be used when making a shared object; recompile with -fPIC

如果我包装阶乘函数，像这样:

.section .text
.globl fact
.type  fact,STT_FUNC
fact:
factorial:
    push %rbp
    mov %rsp,%rbp

    mov 16(%rbp),%rax
    cmp $1,%rax
    je end_factorial
    dec %rax
    push %rax  #this is how we pass the argument to function
    call factorial
    pop %rbx
    inc %rbx
    imul %rbx,%rax
end_factorial:
    mov %rbp, %rsp
    pop %rbp
    ret

我可以毫无错误地构建so库.

---

问题是:为什么在构建包含递归函数的共享库时出现错误? P.S.在这种情况下，静态链接可以正常工作. 谢谢！

解决方案

factorial是全局标签，因此可以进行符号插入.请参阅动态库的抱歉状态， Linux . (此外，将malloc与LD_PRELOAD插入的示例 ，以及一些文档).

制作共享库时，call factorial指令的目标不假定为同一文件中定义的factorial:标签.那是因为您使用了.globl factorial.

正如Jester所指出的，您应该为call目标定义一个单独的本地标签，以便保留全局factorial名称.

如果需要，可以创建一个更简单的"helper"函数，该函数使用其自己的自定义调用约定，并且不使用递归部分的%rbp生成堆栈框架. (但是在x86-64上，在堆栈上使用arg已经是非标准的.)

---

您可以可以通过PLT调用，也可以通过GOT间接调用内存，但是不要那样做；您不希望每个call都有额外的开销，也不想让符号插入用传递%rdi中第一个整数arg的普通代码代替您的非标准调用约定实现.

说到这，在堆栈上传递arg很慢.您确实需要保存/恢复某些内容，除非您将递归重写为尾递归，就像factorial_helper(accumulator*n, n-1) .但是，您也不必每次都使用%rbp创建堆栈框架.

您不必在call之前保持16字节的堆栈对齐，但是在调用自己的私有函数时不需要它.

当然，如果您根本不关心性能，那么您一开始就不会使用递归实现，因为对factorial这样做的唯一原因是作为学习练习.重写为尾递归允许您(或使用C编写的编译器)将call/ret变成jmp，这当然会变成循环.

---

相关:哪些是真正可以激发递归研究的好例子?.二叉树遍历或Ackermann函数比迭代更容易实现，但是factorial或Fibonacci较难(在Fibonacci的情况下，很多慢).

During working on some project, I faced the issue that I can't build so library. I have got the error like: relocation R_X86_64_PC32 against symbol '' can not be used when making a shared object; recompile with -fPIC Eventually I managed to find the root cause. And it was recursive function in the library. For example, I have the following well know example:

.section .text
.globl factorial
.type  factorial,STT_FUNC
factorial:
    push %rbp
    mov %rsp,%rbp

    mov 16(%rbp),%rax
    cmp $1,%rax
    je end_factorial
    dec %rax
    push %rax  #this is how we pass the argument to function
    call factorial
    pop %rbx
    inc %rbx
    imul %rbx,%rax
end_factorial:
    mov %rbp, %rsp
    pop %rbp
    ret

Now, let's try to build the shared library:

as  -g -o fact.o fact.s
ld -shared fact.o -o libfact.so
ld: fact.o: relocation R_X86_64_PC32 against symbol `factorial' can not be used when making a shared object; recompile with -fPIC

If I wrap the factorial function, like this:

.section .text
.globl fact
.type  fact,STT_FUNC
fact:
factorial:
    push %rbp
    mov %rsp,%rbp

    mov 16(%rbp),%rax
    cmp $1,%rax
    je end_factorial
    dec %rax
    push %rax  #this is how we pass the argument to function
    call factorial
    pop %rbx
    inc %rbx
    imul %rbx,%rax
end_factorial:
    mov %rbp, %rsp
    pop %rbp
    ret

I can build the so library with no errors.

---

The question is: why do I get an error while building shared library that contains recursive function? P.S. The static linking works fine in that case. Thanks!

解决方案

factorial is a global label, so it can be subject to symbol interposition. See Sorry state of dynamic libraries on Linux. (Also, an example of interposing malloc with LD_PRELOAD, and some docs).

When making a shared library, the target of the call factorial instruction is not assumed to be the factorial: label defined in the same file. That's because you used .globl factorial.

As Jester points out, you should define a separate local label for the call target so you can keep the global factorial name.

You can make a simpler "helper" function that uses its own custom calling convention and doesn't make stack frames with %rbp for the recursive part, if you want. (But taking an arg on the stack is already non-standard for x86-64).

---

You could call through the PLT or memory-indirect through the GOT, but don't do that; you don't want the extra overhead on each call, and you don't want symbol interposition to replace your non-standard-calling-convention implementation with a normal one that passes the first integer arg in %rdi.

Speaking of which, passing an arg on the stack is slow. You do need to save/restore something, unless you rewrite the recursion to be tail-recursive, like factorial_helper(accumulator*n, n-1). But you don't also need to make a stack frame with %rbp every time.

You're not maintaining 16-byte stack alignment before the call, but you don't need that when calling your own private functions that don't care about that.

Of course, if you care about performance at all, you wouldn't use a recursive implementation in the first place, because the only reason to do that for factorial is as a learning exercise. Rewriting to tail-recursive allows you (or the compiler if writing in C) to turn the call / ret into a jmp, which of course becomes a loop.

---

Related: What are good examples that actually motivate the study of recursion?. A binary tree traversal, or the Ackermann function, are easier to implement recursively than iteratively, but factorial or Fibonacci are harder (and in the case of Fibonacci, much slower).

这篇关于构建具有递归功能的.so的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！