What impact could extra push do to assembly program?

Question

Given:

typedef struct __attribute__((packed)) _Node{
    int data;
    struct _Node *left;
    struct _Node *right;
} Node;

and the following assembly code which searches for a value in a tree. (Same code as How this assembly code will be translated into c?)

.section .text
.global _start

_start:
    mov $8, %esi
    mov $A, %rdi
    call func
    movq $60, %rax
    movq $0, %rdi
    syscall
    
func:
    pushq %rbp
    movq %rsp, %rbp
    cmp (%rdi), %esi
    jne continue
    mov $1, %eax
    jmp finish
    
continue: # go left
    cmpq $0, 4(%rdi)
    je next
    pushq %rdi # 3
    mov 4(%rdi), %rdi
    call func
    pop %rdi # 4
    cmp $1, %eax
    je finish

next: # go right
    cmpq $0, 12(%rdi)
    je fail
    pushq %rdi # 1
    mov 12(%rdi), %rdi
    call func
    pop %rdi # 2
    cmp $1, %eax
    je finish
   
fail:
    mov $0, %rax

finish:
    leave
    ret

I want to know what will be the impact of this change and if it will cause the program to not work as expected:

adding push %rdi right after continue.

From what I understand this will cause a problem since we are pushing some extra value to the stack so the caller for this iteration might pop a wrong value of %rdi for example the caller in this case:

    pushq %rdi # 1
    mov 12(%rdi), %rdi
    call func
    pop %rdi # 2

might pop 12+%rdi instead of poping %rdi, But I ran many tests and all of them seem to return correct value in RAX, why is that?

---

Note: can this line cause stack overflow too? I think the answer is probably yes.

Answer 1

Note the leave in the epilogue: it restores RSP before ret, undoing any extra pushes. If it wasn't there, extra pushes would make your function crash (e.g. popping a copy of RDI into RIP), not successfully return but with RSP pointing at the wrong place.

---

might pop 12+%rdi instead of poping %rdi

No, that's not possible. Push happens before RDI is modified so you're pushing the original value, and pop reads it back. call has no net effect on RSP, i.e. RSP is call-preserved. (If you broke your stack, ret would pop the wrong thing instead of a return address, so you'd crash instead of returning at all. So unless you purposely copy your return address somewhere else, you can't return with RSP modified).

Also, the contents of memory at RDI+12 are not the same thing as RDI+12. And if you literally meant pop 12(%rdi) (i.e. pop into memory), no obviously not; pop %rdi always writes the register, regardless of what data is being popped.

---

Like I just commented on your last question while you were posting this, leave in the epilogue covers up any problems of unbalanced pushes (whether that's from adding an extra push, or from removing a pop) as long as the push/pop operations that actually need to get the right value to the right register are still there. (saving RDI around the first call). Your function doesn't need the node pointer again after the 2nd call, so it's pointless, and would be better to just leave / mov 12(%rdi), %rdi / jmp func. But any extra pushes before that 2nd call don't matter.

The only thing that would be a problem would be an extra pop that removes your return address from the stack before the last call, so it gets overwritten. (An unbalance pop after the last call would leave your return address below RSP, but that's safe in user-space in the x86-64 System V ABI, because it guarantees a red-zone below RSP that's safe from asynchronously getting clobbered by signal handlers and whatnot. So leave would still point RSP back to where it should be, letting ret pop the return address.

Remember, leave is equivalent to mov %rbp, %rsp / pop %rbp, so it resets RSP for itself and later stack operations.

Any extra pushes before a recursive call mean 8 extra bytes of stack space used per depth of stack, but Linux user-space stacks default to 8MiB so it would take a pretty deep tree to get anywhere near actually overflowing it.

---

Single-step your code in a debugger (such as GDB) to see how it runs.

Use display /x *(long (*)[5])$rsp to dump the top 5 qwords from the stack after every single step (by casting it to pointer-to-array and dereferencing). Then stepi through your code and see how it changes, especially at leave.