Construction .so avec une fonction récursive à l'intérieur

Question

Pendant le travail sur un projet, j'ai rencontré un problème : je n'arrive pas à construire une bibliothèque . J'ai reçu l'erreur suivante : relocation R_X86_64_PC32 par rapport au symbole '' ne peut pas être utilisé lors de la création d'un objet partagé ; recompilez avec -fPIC Finalement, j'ai réussi à trouver la cause racine. Et c'était la fonction récursive dans la bibliothèque. Par exemple, j'ai l'exemple bien connu suivant:

.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  #c'est ainsi que nous passons l'argument à la fonction
    call factorial
    pop %rbx
    inc %rbx
    imul %rbx,%rax
end_factorial:
    mov %rbp, %rsp
    pop %rbp
    ret

Maintenant, essayons de construire la bibliothèque partagée :

as  -g -o fact.o fact.s
ld -shared fact.o -o libfact.so
ld: fact.o: relocation R_X86_64_PC32 par rapport au symbole `factorial' ne peut pas être utilisé lors de la création d'un objet partagé ; recompilez avec -fPIC

Si j'encapsule la fonction factorial, comme ceci :

.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  #c'est ainsi que nous passons l'argument à la fonction
    call factorial
    pop %rbx
    inc %rbx
    imul %rbx,%rax
end_factorial:
    mov %rbp, %rsp
    pop %rbp
    ret

Je peux construire la bibliothèque sans erreurs.

---

La question est : pourquoi ai-je une erreur lors de la construction d'une bibliothèque partagée qui contient une fonction récursive? P.S. Le lien statique fonctionne bien dans ce cas. Merci !

Answer 1

factoriel est une étiquette globale, donc elle peut être sujette à interposition de symboles. Voir L'état désolant des bibliothèques dynamiques sur Linux. (Aussi, un exemple d'interposition de malloc avec LD_PRELOAD, et quelques docs).

Lors de la création d'une bibliothèque partagée, la cible de l'instruction call factorial n'est pas supposée être l'étiquette factoriel: définie dans le même fichier. C'est parce que vous avez utilisé .globl factorial.

Comme Jester le souligne, vous devriez définir une étiquette locale séparée pour la cible du call afin de pouvoir conserver le nom global factoriel.

Vous pouvez créer une fonction "helper" plus simple qui utilise sa propre convention d'appel personnalisée et ne crée pas de cadres de pile avec %rbp pour la partie récursive, si vous le souhaitez. (Mais passer un argument sur la pile est déjà non standard pour x86-64).

---

Vous pourriez appeler via la PLT ou indirectement en mémoire via le GOT, mais ne le faites pas; vous ne voulez pas de surcharge supplémentaire à chaque call, et vous ne voulez pas que l'interposition de symboles remplace votre implémentation de convention d'appel non standard par une normale qui passe le premier argument entier dans %rdi.

En parlant de cela, passer un argument sur la pile est lent. Vous devez sauvegarder/restaurer quelque chose, à moins que vous modifiez la récursion pour être récursive terminale, comme factorial_helper(accumulateur*n, n-1). Mais vous n'avez pas besoin non plus de créer un cadre de pile avec %rbp à chaque fois.

Vous ne maintenez pas un alignement de pile de 16 octets avant le call, mais vous n'avez pas besoin de cela lorsque vous appelez vos propres fonctions privées qui ne se soucient pas de cela.

Bien sûr, si vous vous souciez un minimum des performances, vous n'utiliseriez pas une implémentation récursive en premier lieu, car la seule raison de le faire pour le factoriel est comme exercice d'apprentissage. Réécrire en récursivité terminale vous permet (ou le compilateur si vous écrivez en C) de transformer l'instruction call / ret en un jmp, qui devient bien sûr une boucle.

---

En relation : Quels sont de bons exemples qui motivent réellement l'étude de la récursion?. Une traversée d'arbre binaire, ou la fonction d'Ackermann, sont plus faciles à implémenter de manière récursive qu'itérative, mais le factoriel ou Fibonacci sont plus difficiles (et dans le cas de Fibonacci, beaucoup plus lents).