Assembly: malloc() and free()

The program loader of the ULM initializes %2 with the number of byte loaded. For convenience it also sets %3 with the value of %2 rounded up to the next multiple of 8. This can be used for an aligned break pointer, i.e. an address right after the data and BSS segment.

For this quiz we will use this break pointer a simple malloc() and free() implementation:

Function _start first copied the value of %3 into a global variable break. Then it initializes the stack pointer and calls main().
Function malloc expects one parameter for the block size that should be allocated. It makes a copy of the current break pointer in a local variable oldBreak. It then increments the global variable break by size and also rounds up the result to the next multiple of eight.
Function free would return and not release any memory. We therefore actually do not implement it in the exercise and also do not call it.

In the quiz you can test the implementation of malloc() with a program that generates a list from user input.

Quiz 17: Dynamic Single Linked List

The following C program is kind of a blue print for what you should implement in assembly:

session16/list/dyn_list.c

#include <stdio.h>
#include <stdlib.h>

struct ListNode
{
    struct ListNode *next;
    char ch;
};

void
printList(const struct ListNode *listNode)
{
    for (; listNode; listNode = listNode->next) {
        putchar(listNode->ch);
    }
}

void
printListReverse(const struct ListNode *listNode)
{
    if (!listNode) {
        return;
    }
    printListReverse(listNode->next);
    putchar(listNode->ch);
}

int
main(void)
{
    // begin with empty list
    struct ListNode *list = 0;
    char ch;

    while ((ch = getchar()) != '\n') {
        struct ListNode *p = malloc(sizeof(*p));
        // normally we would check if p is the null pointer

        // prepend to current list
        p->next = list;
        p->ch = ch;
        list = p;
    }

    printf("calling: printList(list)\n");
    printList(list);
    putchar('\n');

    printf("calling: printListReverse(list)\n");
    printListReverse(list);
    putchar('\n');
}

The program reads in characters from stdin until it gets a newline. For each character before the newline it creates a new list node that can store a single character. New nodes are prepended to a list that initially is empty.

Before the program terminates it prints the characters stored in the list by first calling function printList() then function printListReverse(). Both print function expect as parameter a pointer to the first list node:

If the list is not empty function printList() prints the character stored in the first node. It then proceed analogously with the next list node.
If the list is not empty function printListReverse() first calls printListReverse() recursively by passing a pointer to the next node, i.e. characters in successor nodes will be printed first. When the recursive function call returns it prints the character stored in its node.

Here a test run with input “abc123”:

theon$ gcc -o dyn_list dyn_list.c
theon$ echo "abc123" | ./dyn_list
calling: printList(list)
321cba
calling: printListReverse(list)
abc123
theon$

The following skeleton can be used for a port to assembly:

session16/list/dyn_list_quiz16.s

    # calling conventions
    .equ    FP,         1
    .equ    SP,         2
    .equ    RET_ADDR,   3

    .equ    ret,        0
    .equ    fp,         ret + 8
    .equ    rval,       fp + 8
    .equ    fparam0,    rval + 8
    .equ    fparam1,    fparam0 + 8

    .equ    local0,     -8
    .equ    local1,     local0 - 8
    .equ    local2,     local1 - 8

//------------------------------------------------------------------------------

    /*
     * global variable .break for break pointer
     */

    .data
    .align  8
break
    .quad   0

//------------------------------------------------------------------------------

    /*
     * function: _start
     */
_start:
    .text
    # store break pointer in global variable break
    ldpa    .start.pool,    %4
    ldfp    (%4),           %4
    movq    %3,             (%4)

    # initialize stack pointer
    ldzwq   0,              %SP

    # call: int main(void)
    subq    8 * (3 + 0),    %SP,        %SP
    ldzwq   main,           %4
    call    %4,             %RET_ADDR
    movq    rval(%SP),      %4                  # return value in %4
    addq    8 * (3 + 0),    %SP,        %SP


    halt    %4                                  # halt with return value

#
#   pool for _start
#
    .text
    .align  8
.start.pool
    .quad   break


//------------------------------------------------------------------------------

    /*
     * function: int main(void)
     */
    .text
#
#   pool for main
#
    .align  8
.main.pool:
.main.pool.malloc:
    .quad   malloc
.main.pool.printList:
    .quad   printList
.main.pool.printListReverse
    .quad   printListReverse

#
#   offsets for pool members
#
    .equ    .malloc,            (.main.pool.malloc - .main.pool) / 8
    .equ    .printList,         (.main.pool.printList - .main.pool) / 8
    .equ    .printListReverse,  (.main.pool.printListReverse - .main.pool) / 8

    .text
main:
    // prologue
    movq    %RET_ADDR,      ret(%SP)
    movq    %FP,            fp(%SP)
    movq    %SP,            %FP
    subq    8 * 3,          %SP,            %SP

    .equ    pList,          local0
    .equ    pNode,          local1
    .equ    ch,             local2

    # offset for struct ListNode
    .equ    next,           0
    .equ    elem,           8

    // body

    # pList = 0;
    movq    %0,             pList(%FP)

.main.while
    # while ((ch = getchar()) != '\n') {

    # ... ch = getchar();                         # part of while

    # ... if (ch == '\n') goto .main.while.done;  # part of while

    # pNode = malloc(9)

    # pNode->next = pList;

    # pNode->elem = ch;

    # pList = pNode

    jmp     .main.while
    # } // while
.main.while.done:

    #   printList(pList);
    subq    8 * (3 + 1),    %SP,        %SP
    movq    pList(%FP),     %4
    movq    %4,             fparam0(%SP)
    ldpa    .main.pool,     %4
    ldfp    .printList(%4), %4
    call    %4,             %RET_ADDR
    addq    8 * (3 + 1),    %SP,        %SP

    putc    '\n'

    #   printListReverse(pList);
    subq    8 * (3 + 1),    %SP,        %SP
    movq    pList(%FP),     %4
    movq    %4,             fparam0(%SP)
    ldpa    .main.pool,     %4
    ldfp    .printListReverse(%4), %4
    call    %4,             %RET_ADDR
    addq    8 * (3 + 1),    %SP,        %SP

    putc    '\n'

#   return 0;
    movq    %0,             rval(%FP)

.main.ret
    // epilogue
    movq    %FP,            %SP
    movq    fp(%SP),        %FP
    movq    ret(%SP),       %RET_ADDR
    ret     %RET_ADDR

//------------------------------------------------------------------------------

    /*
     * function: int malloc(size_t size)
     */
#
#   pool for malloc
#
    .align  8
.malloc.pool
    .quad   break

    .text
malloc:
    // prologue
    movq    %RET_ADDR,      ret(%SP)
    movq    %FP,            fp(%SP)
    movq    %SP,            %FP
    subq    8 * 0,          %SP,        %SP

    .equ    size,           fparam0
    .equ    oldBreak,       local0

    // body

    # oldBreak = break;

    # break = (oldBreak + size + 7) / 8 * 8

    # return oldBreak;

    // epilogue
    movq    %FP,            %SP
    movq    fp(%SP),        %FP
    movq    ret(%SP),       %RET_ADDR
    ret     %RET_ADDR

//------------------------------------------------------------------------------

    /*
     * function: int printList(const struct ListNode *listNode)
     */
    .text
printList:
    // prologue
    movq    %RET_ADDR,      ret(%SP)
    movq    %FP,            fp(%SP)
    movq    %SP,            %FP
    subq    8 * 0,          %SP,        %SP

    .equ    listNode,       fparam0

    // body

#   for (; listNode; listNode = listNode->next) {

#   init: -

.printList.for:

#   check: listNode
    movq    listNode(%FP),  %4
    subq    0,              %4,         %0
    je      .printList.done

#   putchar(listNode->id);
    movq    listNode(%FP),  %4
    movzbq  8(%4),          %4
    putc    %4

#   update: listNode = listNode->next
    movq    listNode(%FP),  %4
    movq    0(%4),          %5
    movq    %5,             listNode(%FP)

    jmp     .printList.for

#   }
.printList.done:

.printList.ret:
#   return 1;
    ldzwq   1,              %4
    movq    %4,             rval(%FP)

    // epilogue
    movq    %FP,            %SP
    movq    fp(%SP),        %FP
    movq    ret(%SP),       %RET_ADDR
    ret     %RET_ADDR

//------------------------------------------------------------------------------

    /*
     * function: int printListReverse(const struct ListNode *listNode)
     */
    .text
#
#   pool for printListReverse
#
    .align  8
.printListReverse.pool
    .quad   printListReverse

printListReverse:
    // prologue
    movq    %RET_ADDR,      ret(%SP)
    movq    %FP,            fp(%SP)
    movq    %SP,            %FP
    subq    8 * 0,          %SP,        %SP

    .equ    listNode,       fparam0

    // body

    # if (!listNode) return; 

    #   printListReverse(listNode->next);

    #putchar(listNode->id);

.printListReverse.ret:
    #   return 1;
    ldzwq   1,              %4
    movq    %4,             rval(%FP)

    // epilogue
    movq    %FP,            %SP
    movq    fp(%SP),        %FP
    movq    ret(%SP),       %RET_ADDR
    ret     %RET_ADDR

You just have tom complete the blanks in function main(), malloc() and printListReverse().

1	submit hpc quiz17 isa.txt dyn_list.s