Lab 11: Dynamic Memory Allocation
Skip navigation Computer Systems & Organisation School of Computing Search query Search ANU web, staff & maps Search current site content Search Menu Search query Search ENGN2219/COMP6719 Lectures Labs Deliverables Resources Practice Search ANU web, staff & maps Search current site content ENGN2219/COMP6719 Lectures Labs Deliverables Resources Practice menu Search query Search Search ENGN2219/COMP6719 Search query Search Labs Lab 1: Introduction Lab 2: Arithmetic and Logic Unit (ALU) Lab 3: State and Registers Lab 4: CPU, Part I: Manual Execution Lab 5: CPU, Part II: Automatic Execution Lab 6: CPU, Part III: Conditional Execution Lab 7: Practicing QuAC Assembly Lab 8: Introduction to C, Part I Lab 9: Introduction to C, Part II Lab 10: Data Structures in C Lab 11: Dynamic Memory Allocation Related sites Piazza Streams Wattle SoCo Homepage You are here » Labs » Lab 11: Dynamic Memory Allocation Table of Contents Outline Preparation Introduction Exercise 1: Statically Allocated Memory Exercise 2: Dynamic Memory Allocation Exercise 3: Two-Dimensional Array Exercise 4: Linked List with Dynamic Memory Exercise 5: Memory Bugs Outline In this week’s lab you will: Learn about dynamically allocating memory on the C heap Learn about common memory-related bugs (e.g., leaks) and learn to fix/avoid them Practice writing code that involves dynamic memory allocation with malloc() and free() Preparation Do an upstream pull to get the latest changes to the lab repository. git fetch upstream
git pull --no-ff --no-edit upstream master
Open the lab11 folder in VS Code. Introduction So far, we have only allocated memory for variables, arrays, and data structures on the call stack or simply the stack. In this tutorial, we will see how we can allocate memory in the global data segment and the heap. Recall the following diagram from the lectures showing the memory map of a typical program. If you do not understand the diagram below, then this is a good time to review the relevant lecture slides. Exercise 1: Statically Allocated Memory Objects declared in file scope in C have static storage duration. Such objects (scalar variables, arrays, and data structures) are allocated in the global data segment of the process’ address space. The benefit of declaring variables with global scope is that they can be accessed from anywhere in the source code. The storage duration of such variables lasts the entire execution of the program. If you are not familiar with address spaces, processes, memory maps, and the global data segment, then this is a good time to review the lecture slides (weeks 9 and 10). Open the program src/static-array.c and familiarise yourself with the program. Once you have understood the example program, answer the following questions: Where are the inc function’s variables static_int and stack_int stored? What is the difference between a variable allocated inside the main function and a variable allocated at the file scope, outside of any function? The global_array is globally visible to any function in the source program. Unfortunately, it’s length is fixed at compile time. What should we do if we want a globally visible variable-length array? What are the disadvantages of allocating very large arrays on the stack frame? What are some of the limitations of allocating objects on the stack frame? Check your answers with a tutor in your lab. Exercise 2: Dynamic Memory Allocation We hope you understand the motivation for the program heap while answering the questions above and reviewing lecture slides. Now, we will show you and practice dynamically allocating memory on the program heap. Dynamically allocated memory is used when the exact memory requirements of a program are unknown at compile time. An easy example of a program that does not know its memory requirements at compile time is a text editor - the program does not know how many words the user is going to type. The C standard library defines memory management functions for allocating and deallocating (freeing) heap memory. The functions we are concerned with include malloc and free. The malloc function allocates space for an object of a specified size. The size is specified in terms of the number of bytes of memory to be allocated. The malloc function returns a pointer to the starting address of the newly allocated memory. The sizeof operator is really useful for specifying the size of memory to be allocated. The following examples allocate memory on the heap for ten integers, ten characters, and ten structures. struct student {
int id;
char name[20];
};
typedef struct student student_t;
int *int_array = (int *) malloc(10 * sizeof(int));
char *char_array = (char *) malloc(10 * sizeof(char));
student_t *struct_array = (student_t *) malloc(10 * sizeof(student_t));
The malloc function returns NULL if the heap is full. Otherwise, it returns a (void) pointer to the allocated space. Note that in each case in the example above, we cast the pointer returned by malloc to a pointer to the type of the declared object. A careful programmer must deallocate dynamically allocated memory when it’s no longer needed by calling the free function. Why is it important to deallocate unused heap memory? Open the program src/item-array.c and read the code. How big is item_t? What is the total amount of memory consumed by the item_array? Recalculate the consumption accounting for the sizes of individual members contained in each item in the item_array. Can you draw how the item_array looks like on the heap? Exercise 3: Two-Dimensional Array We will now dynamically allocate a 2-dimensional array (matrix) with N rows and M columns on the heap. We provide the partial code for the exercise in src/2-dim-array.c. Your task is to initialize each array element to a calculated value, then free the array from memory. This exercise is fairly similar to the previous exercise, with a subtle difference in its solution when freeing memory that is both severely consequential and easy to miss. Follow the instructions in src/2-dim-array.c and complete the program. Check your solution with a tutor when complete. Exercise 4: Linked List with Dynamic Memory We will now revisit the linked list program from the previous lab. We have rewritten the program to ask the user if there is another student to be added to the list. If the user types 1, we then ask for additional details regarding the student’s record, and create and add a new student to the linked list. At any point, if the user types a -1, we terminate the program. This program demonstrates the true power of dynamic allocation. Indeed, we have no clue at compile time, how many students the user intends to add to the linked list. We dynamically allocate memory for each student’s record as the user wishes. If the user types 2, the program asks for the details of the student’s record and removes the appropriate element from the list. In order to create and destroy linked list elements, you will need to use malloc and free respectively. There are a few other subtle differences from last week’s lab that are worth noting: The insert and delete operate on the list head, which is a globally defined variable. Thus it is no longer passed as a function argument, and can be modified from within the function. Because head is globally defined and modifiable by functions, you should be able to delete any element of the list - including the first element. head is initially a NULL pointer - Your insert function should not assume that head -> next exists, as it will not exist when the list is empty. Open the program src/linked-list.c and complete the definitions of insert() and delete(). Check your implementation with a lab tutor when you think you have completed the exercise, or if you are completely stuck. Most students have solved the linked list exercise with an iterative program using loops. Consider - could you solve the exercise using recursion? Exercise 5: Memory Bugs The C programming language requires manual memory management (unlike languages such as Java and Python which offer automatic memory management or garbage collection). The programmer needs to keep track of when an object is no longer needed and can be safely freed. Not freeing memory no longer needed leads to memory leaks and the inefficient use of physical (main) memory. Memory leaks can even lead to dreadful out-of-memory errors. Unfortunately, programmers frequently make mistakes and either forget to free memory or free memory prematurely. We have comprehensively discussed common memory errors in C programs in the lecture slides. Your task in this section is to identify and fix all the memory errors the provided program. The program is attempting to initialize three arrays at run-time with malloc, initialize them all to zero, then free them. There are many bugs in the program! Open src/bug-galore.c, identify, and correct, all bugs in the program. Updated: 17 May 2022 / Responsible Officer: Director, School of Computing / Page Contact: Shoaib Akram Contact ANU Copyright Disclaimer Privacy Freedom of Information +61 2 6125 5111 The Australian National University, Canberra CRICOS Provider : 00120C ABN : 52 234 063 906 You appear to be using Internet Explorer 7, or have compatibility view turned on. Your browser is not supported by ANU web styles. » Learn how to fix this » Ignore this warning in future
