Reading 08: Dynamic Memory

Readings

The readings for Monday, March 27 are:

  1. From Beej's Guide to C Programming:

  2. From C Programming Boot Camp

TL;DR

The focus of this reading is to introduce you to dynamic memory and structs in C. In particular, you should become familiar with malloc and free.

Optional Resources

  1. What is "the stack"?

  2. A Little C Primer - C Dynamic Memory Allocation & Deallocation

  3. Learn C - Dynamic allocation

  4. GNU C Library - Memory Allocation

Activities

  1. Given the following lines of code in C99:

    struct point {
    double x;
    double y;
};

...

1. int            i = 0;
2. int          a[] = {4, 6, 6, 3, 7};
3. char          *s = "pgui";
4. struct point   p = {0, 0};
5. struct point  *q = NULL;
6. struct point  *x = malloc(sizeof(struct point));
7. struct point  *y = malloc(10*sizeof(struct point));
8. struct point **z = malloc(10*sizeof(struct point *));

    How much memory (in terms of bytes) is allocated or reserved for each of the 8 declarations above (assume a 64 bit Linux machine such as the student machines)?

    Note: Remember that each variable declaration is a memory allocation.

  2. Given the following C99 file duplicates.c:

    /* duplicates.c */

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

const int NITEMS = 1<<10;
const int TRIALS = 100;

bool contains(int *a, int n, int k) {
    /* TODO: Search through array to see if there is an element that matches key */
    return false;
}

bool duplicates(int n) {
    int *randoms = malloc(n);

    for (int i = 0; i < n; i++)
        randoms[i] = rand();

    for (int i = 0; i < n; i++) {
        /* TODO: Use contains to search array for duplicate */
        if (true) {
            return true;
        }
    }

    free(randoms);
    return false;
}

int main(int argc, char *argv[]) {
    srand(time(NULL));

    for (int i = 0; i < TRIALS; i++)
        if (duplicates(NITEMS))
            puts("Duplicates detected!");

    return 0;
}

    Task 0: Download starter code

    First, download the duplicates.c and Makefile.reading08 starter code:

    # Download duplicates.c
$ curl -L https://www3.nd.edu/~pbui/teaching/cse.20289.sp17/static/c/duplicates.c > duplicates.c

# Download Makefile.reading08
$ curl -L https://www3.nd.edu/~pbui/teaching/cse.20289.sp17/static/txt/Makefile.reading08 > Makefile

    Task 1: contains

    Implement the contains function:

    Given an integer array a, its size n, and a key k, this returns whether or not a contains an element with the same k value.

    Task 2: duplicates

    Complete the duplicates function:

    Given an integer n, this function generates n random integers and stores them into an randoms array. It then uses the contains function to check if each element in the array has a duplicate. It returns true if a duplicate is found and false if there are no duplicates.

    Note: Simply replace the if (true) with something in the form if (contains(...)).

    Task 3: Memory Errors

    Once you are confident in your implementations of contains and duplicates, use the Makefile to build and test your code:

    # Build and run test
$ make test
gcc -g -gdwarf-2 -Wall -std=gnu99 -c -o duplicates.o duplicates.c
gcc -L.  -o duplicates duplicates.o
Testing duplicates...
make: *** [Makefile:17: test] Error 1

    Most likely, the test will fail. To view the error output from valgrind, you can look at the test.log file the Makefile generates during testing:

    # View Valgrind log
$ cat test.log
==16711== Memcheck, a memory error detector
==16711== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==16711== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==16711== Command: ./duplicates
==16711==
==16711== Invalid write of size 4
==16711==    at 0x4006AB: duplicates (duplicates.c:20)
==16711==    by 0x40071B: main (duplicates.c:37)
==16711==  Address 0x51d5440 is 0 bytes after a block of size 1,024 alloc'd
==16711==    at 0x4C2AC00: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==16711==    by 0x400683: duplicates (duplicates.c:17)
==16711==    by 0x40071B: main (duplicates.c:37)
==16711==
--16711-- VALGRIND INTERNAL ERROR: Valgrind received a signal 7 (SIGBUS) - exiting
--16711-- si_code=128;  Faulting address: 0x0;  sp: 0x802ca9e30
....

    You should see something like the above output. Debug this memory error (and any other errors) so that make test passes.

    Note: You should not need to add any free statements to fix this memory error.

    Task 4: Memory Leaks

    Once your code is passing the test, modify the following line of code:

    randoms[i] = rand();

    To the following:

    randoms[i] = rand() % 1000;

    Run make test again:

    # Build and run test
$ make test
gcc -g -gdwarf-2 -Wall -std=gnu99 -c -o duplicates.o duplicates.c
gcc -L.  -o duplicates duplicates.o
Testing duplicates...
make: *** [Makefile:17: test] Error 1

    Most likely, the test will fail. Once again, view the error output from valgrind:

    $ tail -n 20 test.log
Duplicates detected!
==17270==
==17270== HEAP SUMMARY:
==17270==     in use at exit: 409,600 bytes in 100 blocks
==17270==   total heap usage: 101 allocs, 1 frees, 413,696 bytes allocated
==17270==
==17270== 409,600 bytes in 100 blocks are definitely lost in loss record 1 of 1
==17270==    at 0x4C2AC00: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==17270==    by 0x400687: duplicates (duplicates.c:17)
==17270==    by 0x40071F: main (duplicates.c:37)
==17270==
==17270== LEAK SUMMARY:
==17270==    definitely lost: 409,600 bytes in 100 blocks
==17270==    indirectly lost: 0 bytes in 0 blocks
==17270==      possibly lost: 0 bytes in 0 blocks
==17270==    still reachable: 0 bytes in 0 blocks
==17270==         suppressed: 0 bytes in 0 blocks
==17270==
==17270== For counts of detected and suppressed errors, rerun with: -v
==17270== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

    You should see something like the above output. Debug this memory leak (and any other errors) so that make test passes.

    Task 5: README.md

    In your README.md, answer the following questions:

    1. Describe what the memory error was in Task 3 and how you fixed it.

    2. Describe what the memory leak was in Task 4 and how you fixed it.

Feedback

If you have any questions, comments, or concerns regarding the course, please provide your feedback at the end of your response.

Submission

To submit your assignment, please commit your work to the reading08 folder in your assignments GitLab repository. Your reading08 folder should only contain the following files: