Recursion in assembly?

Question

I'm trying to get a better grasp of assembly, and I am a little confused about how to recursively call functions when I have to deal with registers, popping/pushing, etc.

I am embedding x86 assembly in C++. Here I am trying to make a method which given an array of integers will build a linked list containing these integers in the order they appear in the array.

I am doing this by calling a recursive function:

insertElem (struct elem *head, struct elem *newElem, int data) 

-head: head of the list

-data: the number that will be inserted at the end of a list

-newElem: points to the location in memory where I will store the new element (data field)

My problem is that I keep overwriting the registers instead of a typical linked list. For example, if I give it an array {2,3,1,8,3,9} my linked-list will return the first element (head) and only the last element, because the elements keep overwriting each other after head is no longer null.

So here my linked list looks something like: 2-->9 instead of 2-->3-->1-->8-->3-->9

I feel like I don't have a grasp on how to organize and handle the registers. newElem is in EBX and just keeps getting rewritten. Thanks in advance!

Solution 1

It's difficult to give an answer without having seen your asm code. My first thought is that there's no need for recursive functions when dealing with linked lists.

Anyway, the general way to preserve registers across function calls is to push them on the stack and pop them afterwards:

;
; ebx = current element
;
TraverseList:

   ; If this is the end of the list we can skip the recursive invocation
   cmp [ebx+next], 0
   je NoNextElement

   push ebx               ; Save current element (ebx) on stack
     mov ebx, [ebx+next]  ; Put next element in ebx
     call TraverseList    ; Recursive invocation
   pop ebx                ; Restore current element (ebx) from stack

NoNextElement:

   ; Do stuff with the current element (ebx)
   ...
   ret

Solution 2

The most generic answer to any assembler-related "how to" question is: gcc -S. If you're in doubt about anything, just take a look on how a decent C compiler translates this into a lower-level code.

In your case, you need to maintain your local variables on a stack frame. Use registers only for values that need not to survive after any external subroutine call.