Inspired by all of the lovely linked lists lately, I decided to implement one in assembly language.  This code maintains two linked lists - one is a free store and the other is the active linked list.  Rather than allocating memory whenever a new node is needed, the Node is pulled from the free list and all of the pointers updated.  The data is then copied into the newly allocated Node.  This program includes a test driver which reads a series of NUL terminated strings (C strings) from memory, calculates their lengths and then puts a pointer to the string and the length into each Node until the end of list is found.If there are not enough free nodes to hold all of the found strings, the program silently exits with an error code of 1.  If there is enough and there are no other errors, the program prints each of the found strings on a separate line and exits with a status code of 0.The output is this:AlfredBarbaraCarlosDeloresEdwardFrancesMy Makefile looks like this:%.o : %.asm        nasm -f elf64 -l foo.lst -g -F stabs -o $@ $<% : %.o        ld -g -o $@ $<The Makefile is invoked as make linky.The program, which I've place in a file named linky.asm is below:; 64-bit linked list implementation in Linux NASMglobal _start                         ; global entry point export for ldMAX_NODES   equ        300            ; this can easily be expandedsection .text_start:        ; first initialize the free node list        mov        rcx, MAX_NODES-1                mov        rdi, [freenode]        mov        rsi, linkedlist        mov        rax, Node_sizenodeclear:        add        rsi, rax        ; point to next node        mov        [rdi + Node.next], rsi        add        rdi, rax        ; advance pointer        loop        nodeclear        ; set the last link to NULL        mov        qword [rdi + Node.next], 0        ; start out pointing to our rootnode pointer        mov        rdi, rootnode        ; our string pointer starts at the beginning        mov        rbx, namestringslooptop:        ; fetch the next string        call        FetchString        ; skip to print function if we are at end of list        jrcxz        finish        ; insert the string into new node        call        NodeInsert        jmp        looptopfinish:        ; print all strings in the linked list        mov        rdi, rootnodemorenodes:        call        NodePrint        or        rdi,rdi        jnz     morenodes        ; (rdi is already 0 here)         ; normal exit with status 0exit:        mov        rax, 60            ; sys_exit        syscallerrorExit:        mov        rdi, 1             ; return 1 (error)        jmp        exit; NodePrint:;   advances to next node and prints if non-null; Entry:;   rdi points to memory location containing pointer;        to next node; Exit:;   rsi points to string just printed   ;   rdx is the length of the string just printed ;   rdi = 0 if we are at the end of the linked listNodePrint:        mov        rsi, [rdi]        mov        rdi, rsi        or        rdi, rdi        jz        retnow        mov        rsi, [rdi + Node.mydata + mydata.msgptr]        mov        rdx, [rdi + Node.mydata + mydata.msglen]        push        rdi        call        printstr        call        printeol        pop        rdiretnow:        ret        ; rsi = addr, rdx= len; NodeInsert:;   creates and populates new node in linked list; Entry:;   rdi points to memory location to which pointer;          to new node should be written;   rsi points to a string to be placed in the new Node;   rcx is the length of the string pointed to by rsiNodeInsert:        push        rax        push        rbx        ; steal a node from the freenode list        ;   [rootnode] = [freenode]        mov        rbx, freenode      ; rbx -> freenode        cmp        qword [rbx], 0     ; Q: nodes available?        je         errorExit          ;   N: nope, so leave        mov        rax, [rbx]         ;         mov        qword [rdi], rax   ;         mov        rdi, rax           ; rdi -> node        ;   [free] = [root.next]        mov        rax, [rdi + Node.next]         mov        [rbx], rax        ;   [root.next] = 0        mov        qword [rdi + Node.next], 0        pop     rbx        pop        rax        ;;  fall through to NodeAddData; NodeAddData:;   add string data to existing node; rdi points to an existing Node; rsi points to a string to be placed in the new Node; rcx is the length of the string pointed to by rsiNodeAddData:        mov        [rdi + Node.mydata + mydata.msglen], rcx        mov        [rdi + Node.mydata + mydata.msgptr], rsi        ret; FetchString:;   fetch NUL terminated string and calculate len; Entry:;   rbx points to start of NUL terminated string; Exit:;   rsi points to string start;   rcx contains length of string;   rbx points to next string (if any)FetchString:        push       rax        push       rdi        mov        rdi, rbx        ; copy pointer        mov        rcx, -1         ; max count in ecx        mov        al,0            ; look for NUL byte        cld                        ; count forward        repne      scasb           ; look for NUL        not        rcx             ; tricky math to get len        dec        rcx        mov        rsi, rbx        mov        rbx, rdi        ; recover original pointer        pop        rdi        pop        rax        retprinteol:        mov        rsi, eol        mov        edx, 1printstr:        mov        rax, 1                ; sys_write        mov        rdi, 1                ; stdout        syscall        ret; ==== data section ====section .data; this is the data that goes into a nodestruc        mydata        .msglen            resq 1        .msgptr            resq 1endstruc; this is a node of the linked liststruc        Node        .next            resq 1        .mydata            resb mydata_sizeendstruc         eol:        db  0x0a        namestrings:        db  'Alfred', 0                         db  'Barbara', 0                         db  'Carlos', 0                         db  'Delores', 0                        db  'Edward', 0                        db  'Frances', 0                        db  0,0rootnode    dq            0freenode    dq            linkedlistsection        .bsslinkedlist  resb    MAX_NODES * Node_size
Linux NASM assembly linked list implementation
linked list;linux;assembly
Just a few notes, mostly in micro-optimizations that even assembly language programmers probably ignore nowadays.    ; steal a node from the freenode list    ;   [rootnode] = [freenode]    mov        rbx, freenode      ; rbx -> freenode    cmp        qword [rbx], 0     ; Q: nodes available?    je         errorExit          ;   N: nope, so leave    mov        rax, [rbx]         ; To compare to 0, I prefer to use a test instruction:mov rbx, freenodemov rax, [rbx]test rax, raxjz errorExit; ...Likewise, in NodePrint you use an or to determine whether a value is 0:    or        rdi, rdi    jz        retnowAgain, a test is sufficient here. The difference is that or will normally affect not only the flags (which you want) but the register (which you don't). In this case, you haven't actually changed the value in the register, but some CPUs will assume you did, which can prevent some instruction level parallelism.When you're getting ready for the scasb in FetchString, you load a 0 into AL:    mov        rcx, -1         ; max count in ecx    mov        al,0            ; look for NUL byte    cld                        ; count forward    repne      scasb           ; look for NULAt least if memory serves, you'll get marginally smaller code with something like:xor rax, raxThis zeros the entirety of rax instead of just AL, but you don't seem to need/use the rest of rax afterward. Some processors also have a partial register stall that makes essentially any operation on AL relatively slow (though I don't remember if this applies to any 64-bit processors, so it may not matter in this case).Although it's minutely more fragile, I'd consider whether it's worth replacing this:    loop        nodeclear    ; set the last link to NULL    mov        qword [rdi + Node.next], 0...with code like:loop nodeclearmov qword [rdi+Node.next], rcxTaking advantage of the fact that immediately after executing a loop, we know rcx contains 0.I think it's worth noting, however, that all of these are really very minor. Overall, the code strikes me as quite clear and nicely written. 