9.1: Heap Dynamic Memory

Last updated
Save as PDF

Page ID: 27148

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

Before beginning a discussion of arrays, a third type of program data memory is introduced. So far in this text static (data) and stack dynamic memory have been discussed. The third type of memory introduced here is heap dynamic memory.

Arrays can exist in any type of memory, static, stack, or heap. However, when they are stored in static or stack memory, their size is fixed when the program is compiled and cannot change. Most programs that use arrays will need arrays that adjust in size depending on the size of the input data, and this requires heap memory.

9.1.1 What is heap memory

Heap memory was shown in Figure 2.3. As this figure shows, the heap memory segment begins in the program process space immediately after static memory, and grows upward in memory until theoretically it reaches the stack memory segment. In reality most systems limit the amount of heap a process can request to protect against incorrect programs that might be allocating heap inappropriately. Generally, these limits on heap size can be increased if they need to be larger than the default (for example, the Java interpreter can be run with the -Xms or -Xmx parameters to change the heap size).

Heap memory is dynamic, like stack memory, in that it is allocated at run time. However unlike stack memory which is automatically allocated and de-allocated when subprograms are entered and exited, heap memory is allocated based on a request from the programmer, normally using a new operator. The new operator allocates the requested amount of memory, and initializes it to a default value (normally zero). Because heap memory is allocated when requested by the user at run time, and the amount of memory can be determined at run time.

Memory in the heap is generally de-allocated when it is no longer needed by the programmer. How this de-allocation is done is dependent on the environment in which the program is being run. For example in C/C++ memory is de-allocated using either the free() function call or the delete operator. Java, C#, and other modern languages use memory managers which automatically free the memory when it is no longer used.

The biggest issue with heap memory is since it is allocated and de-allocated in non-fixed sized pieces, as the memory is de-allocated it leaves numerous holes in the memory that are of various sizes. This makes memory allocation and de-allocation difficult to deal with. Heap memory is much more complicated to manage than static and stack memory, and entire books have been written on heap management.

Because of the complexity of dealing with managing the de-allocation of heap memory, this text will only deal with the allocation of the memory. Any heap memory that is allocated cannot be reused.

9.1.2 Allocating heap memory example – PromptString subprogram

The first example subprogram presented here for using heap memory is a function that allows a programmer to prompt for strings without having to create a blank string variable in the .data section of the program. The subprogram first allocates a string variable large enough to hold the string the user is being prompted for, and then uses the syscall service 8 to read a value into that string.

Program 9-1: PromptString subprogram showing heap allocation

.text
main:

    la $a0, prompt1        # Read and print first string
    li $a1, 80
    jal PromptString
    move $a0, $v0
    jal PrintString
    
    la $a0, prompt2        # Read and print first string
    li $a1, 80
    jal PromptString
    move $a0, $v0
    jal PrintString
    
    jal Exit

.data
    prompt1: .asciiz "Enter the first string: "
    prompt2: .asciiz "Enter the second string: "

.text
# Subprogram:    PromptString
# Author:        Charles Kann
# Purpose:       To prompt for a string, allocate the string and return the string to the calling subprogram.
#  Input:        $a0 - The prompt
                 $a1 - The maximum size of the string
#  Output:       $v0 - The address of the user entered string

PromptString:
    addi $sp, $sp, -12    # Push stack
    sw $ra, 0($sp)
    sw $a1, 4($sp)
    sw $s0, 8($sp)
    
    li $v0, 4             # Print the prompt
    syscall               # in the function, so we know $a0 still has
                          # the pointer to the prompt.
    
    li $v0, 9             # Allocate memory
    lw $a0, 4($sp)
    syscall
    move $s0, $v0
    
    move $a0, $v0         # Read the string
    li $v0, 8
    lw $a1, 4($sp)
    syscall
    
    move $v0, $a0         # Save string address to return
    
    lw $ra, 0($sp)        # Pop stack
    lw $s0, 8($sp)
    addi $sp, $sp, 12
    jr $ra

.include "utils.asm"

9.1.3 Commentary on PromptString Subprogram

To allocate heap memory, the syscall service 9 is used. The address of the memory returned from this heap allocation syscall is in $v0. $v0 is moved to $a0 to be used in the syscall service 8 to read a string. The address of the memory containing the string is now in $a0, and is moved to $v0 to be returned to the main subprogram.
Data which is expect to be unchanged across subprogram calls (including syscall) should always be stored in a save register ($s0 in this example), or on the stack ($a1 in this example). Do not use any other registers (such as temporary registers like $t0) or memory as the values of cannot be guaranteed across subprogram calls.
The value of $s0 is saved when this subprogram is entered, and restored to its original value when the subprogram is left. All save registers must have the same value when leaving a subprogram as when it is entered. Any other registers ($t0, $a0, $v0, etc.) can be used with disregard to restoring their original values when the sub program exits.
The main subprogram in this example will shows two strings being read. This is to show how the allocated strings exist in heap memory. In the MARS screen shot below, note that the heap memory is now being displayed. In the heap memory the two strings entered (“This is a first test”, and “This is a second test”) are shown, with each taking up 80 bytes of memory.
Figure 9-1: Heap memory example