Stack implemented using linked list in x86_64 assembly

Question

I wrote a stack implementation using a singly linked list in x86_64 assembly. This stack supports the usual push/pop operations as well as first/next for iterating over each element.

I'm looking for general feedback.

Here are the stack subroutines:

; Stack Structure
;   Pointer Head
;   Pointer Current

; Stack Node
;   Pointer Next
;   Pointer Value

; input
;   void
; output
;   stack or 0 on error
StackCreate:
  mov rdi, 24
  call malloc
  test rax,rax
  jz StackCreate_end
  xor rdi, rdi
  mov [rax], rdi
  mov [rax+8], rdi
  ret
StackCreate_end:
  add rsp, 8
  ret

; input
;   stack
; output
;   void
StackDestroy:
  call free
  ret

; input
;   stack
;   value
; output
;   0 on error
StackPush:
  push rdi
  push rsi
  mov rdi, 16
  call malloc
  test rax,rax
  jz StackPush_end
  pop rsi
  pop rdi
  mov rdx, [rdi]
  mov [rax], rdx
  mov [rax+8], rsi
  mov [rdi], rax
  ret
StackPush_end:
  add rsp, 16
  ret

; input
;   stack
; output
;   value or 0 if empty
StackPop:
  mov rsi, rdi
  mov rdi, [rdi]
  test rdi, rdi
  jz StackPop_end
  mov rax, [rdi]
  mov [rsi], rax
  mov rax, [rdi+8]
  push rax
  call free
  pop rax
  ret
StackPop_end:
  xor rax, rax
  ret
  nop;e

; input
;   stack
; output
;   value or 0 if empty
StackFirst:
  mov rax, [rdi]
  test rax, rax
  jz StackFirst_end
  mov rsi, [rax]
  mov [rdi+8], rsi
  mov rax, [rax+8]
StackFirst_end:
  ret

; input
;   stack
; output
;   value or 0 if end
StackNext:
  mov rsi, [rdi+8]
  test rsi, rsi
  jz StackNext_end
  mov rax, [rsi]
  mov [rdi+8], rax
  mov rax, [rsi+8]
  ret
StackNext_end:
  xor rax, rax
  ret

Here is a driver:

[extern puts]
[extern malloc]
[extern free]

[SECTION .data]

arguments:
  db "Incorrect arguments.",10,"Expected: stackme <string1> <string2> ...",0

[SECTION .text]
BITS 64
global main

wrong_arguments:
  mov rdi, arguments
  call puts
  jmp main_end

main:
  cmp rdi, 1
  jle wrong_arguments

  lea r12, [rsi+8]
  lea r13, [rdi-1]

  call StackCreate
  test rax, rax
  jz main_end
  mov r14, rax

pushing_loop:
  test r13, r13
  jz pushing_done
  mov rdi, r14
  mov rsi, [r12]
  call StackPush
  add r12, 8
  dec r13
  jmp pushing_loop
pushing_done:

  mov rdi, r14
  call StackFirst
print_loop:
  test rax, rax
  jz print_done
  mov rdi, rax
  call puts
  mov rdi, r14
  call StackNext
  jmp print_loop
print_done:

stack_delete:
  mov rdi, r14
  call StackPop
  test rax, rax
  jnz stack_delete
stack_delete_done:
  mov rdi, r14
  call StackDestroy

main_end:
  xor eax, eax
  ret

Assembling/Linking

nasm -f elf64 -l stackme.lst stackme.asm
gcc -o stackme stackme.o

Answer 1

The code is generally well written and easy to understand, but I have a few comments on it that could help improve it.

Eliminate "magic numbers"

In the StackCreate routine, the first instruction is mov rdi,24 but it's not clear what 24 signifies in this context. Either a comment or a named constant or both would help with that.

Add more meaningful comments

The stack structure is not very clear from the comments. We can infer that the stack consists of nodes, but it's not easy to tell from the code or the comments.

Also, consider the user of the stack code. There isn't currently enough within the code to understand the calling sequence, register usage or return values. All of those would be useful to have in the comments. If you're intending to use a standard ABI, it would be useful to say which one.

Use rep ret as appropriate

The gcc compiler emits rep ret when the ret could be the target of a jump. This seems weird (and it is!) but the reason is that the branch prediction logic on both AMD and Intel processors works better when the ret is not the target of branch. So this means the StackFirst_end label in your code should actually have a rep prefix just before the ret.

Use struc as appropriate

Because your stack uses two structures, it would benefit from using NASM's struc/endstruc macros. This would both make it more clear when the code is manipulating data structures and also eliminate quite a few of the "magic numbers" I mentioned earlier.

Consider refactoring StackFirst and StackNext

Other than minor differences in specific register selection, the StackFirst and StackNext routines are very similar. It may be possible to combine them to eliminate some code.

Reduce use of malloc and free

The malloc and free calls tend to be relatively computationally expensive, especially relative to the assembly code you've got. For that reason, it would probably make more sense to either allocate and manage a block rather than calling malloc for every stack push, or to replace calls to malloc and free with some other memory allocation scheme that might be user-replaceable for speed.

Rearrange the loop to avoid unconditional jumps

The current pushing_loop looks like this:

    pushing_loop:
      test r13, r13
      jz pushing_done
      mov rdi, r14
      mov rsi, [r12]
      call StackPush
      add r12, 8
      dec r13
      jmp pushing_loop
    pushing_done:

However, it could be slightly rearranged to eliminate one of the jumps:

      inc r13
      jmp push_test

    pushing_loop:
      mov rdi, r14
      mov rsi, [r12]
      call StackPush
      add r12, 8
    push_test:
      dec r13
      jnz pushing_loop

The unconditional jump is only made once at the top of the loop and all other iterations use only the conditional test at the bottom of the loop. There are a few other places in the code this could be applied.