Reading 11: Memory and Data Structures, File System

This Is Not The Course Website You Are Looking For

This course website is from a previous semester. If you are currently in the class, please make sure you are viewing the latest course website instead of this old one.

Everyone:

Next week, we will delve deeper into memory management and data structures in C. In particular, we will discuss how a typical address space is laid out, how to dynamically allocate memory using malloc (and how to release it with free), and how to create data structures with structs and unions.

After the Easter break, we will then explore using system calls to navigate and inspect the file system with a special focus on how to traverse directories and look at file system meta-data.

TL;DR

The focus of this reading is to explore memory management and data structures in C and learn how to use valgrind and gdb.

Likewise, you are to also to explore how to navigate the file system and look at meta-data.

Readings

The readings for this week are:

Optional References

Quiz

This week, the reading is split into two sections: the first part is a dredd quiz, while the second part involves one C program: str_title.c.

To test the C program, you will need to download the Makefile and test scripts:

$ git checkout master                 # Make sure we are in master branch
$ git pull --rebase                   # Make sure we are up-to-date with GitLab

$ git checkout -b reading11           # Create reading11 branch and check it out

$ cd reading11                        # Go into reading11 folder

# Download Reading 11 Makefile
$ curl -LO https://gitlab.com/nd-cse-20289-sp20/cse-20289-sp20-assignments/raw/master/reading11/Makefile

# Download, build, and execute tests
$ make test

Questions

Given the following C program, allocations.c, which simply declares a series of variables:

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

typedef struct {
    double x;
    double y;
} Point;

typedef union {
    char   c;
    int    i;
    float  f;
    double d;
} Block;

double GD = 3.14;

int main(int argc, char *argv[]) {
    int    a[]  = {4, 6, 6, 3, 7};
    char  *sp   = "Happy Kid";
    char   sa[] = "Frug";
    Block  b    = {0};

    Point   p0  = {0, 0};
    Point  *p1  = NULL;
    Point  *p2  = malloc(sizeof(Point));
    Point  *p3  = malloc(10*sizeof(Point));
    Point **p4  = malloc(10*sizeof(Point *));

    return 0;
}

And the following C program, str_title.c, which converts each command-line argument into title-case:

/* str_title: convert strings to title-case */

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

char *str_title(const char *s) {
    char *t = malloc(strlen(s));
    strncpy(t, s, strlen(t));

    char *c = t;
    while (*c) {
      *c = toupper(*c);
      while (*c && !isspace(*c++));
      while (*c &&  isspace(*c++));
    }

    return t;
}

int main(int argc, char *argv[]) {
    for (int i = 1; i <= argc; i++) {
      char *t = str_title(argv[i]);
      puts(t);
    }
    return 0;
}

Record the answers to the following Reading 11 Quiz questions in your reading11 branch:

Programs

Given the provided str_title.c and Makefile, you are to do the following:

Modify Makefile to include a rule for the str_title program. Be sure to use the CC and CFLAGS variables in your rule.

Note: Consider the use of automatic variables.
Modify str_title.c so that it no longer has any uninitialized memory accesses, memory leaks, invalid memory acceses, or logical errors.

Note: The str_title must not modify the original string (hence the const char *). Consider the use of strdup.

Debugging

Use this as an opportunity to utilize valgrind and gdb to debug str_title.c.

Once you have a working Makefile, you should be able to use the make command to run your recipes:

$ make clean                                  # Remove targets
rm -f str_title

$ make                                        # Build targets
gcc -Wall -std=gnu99 -g -o str_title str_title.c

$ ./str_title "harry potter"                  # Test manually
Harry Potter

$ make test                                   # Test scripts

Submission

To submit you work, follow the same process outlined in Reading 01:

#--------------------------------------------------
# BE SURE TO DO THE PREPARATION STEPS ABOVE
#--------------------------------------------------

$ cd reading11                        # Go into reading11 folder

$ $EDITOR answers.json                # Edit your answers.json file

$ ../.scripts/submit.py               # Check reading11 quiz
Submitting reading11 assignment ...
Submitting reading11 quiz ...
      Q1 1.50
      Q2 0.25
      Q3 0.25
      Q4 0.50
   Score 2.50

$ git add answers.json                # Add answers.json to staging area
$ git commit -m "Reading 11: Quiz"    # Commit work

$ $EDITOR str_title.c                 # Edit source code

$ make test                           # Build and Run tests
Testing str_title ...
 str_title (no arguments)                 ... Success
 str_title (no arguments) (valgrind)      ... Success
 str_title  harry potter                  ... Success
 str_title  harry potter  (valgrind)      ... Success
 str_title 'harry potter'                 ... Success
 str_title 'harry potter' (valgrind)      ... Success
 str_title  a b c d                       ... Success
 str_title  a b c d  (valgrind)           ... Success
 str_title 'a b c d'                      ... Success
 str_title 'a b c d' (valgrind)           ... Success
   Score 1.50

$ git add Makefile                    # Add Makefile to staging area
$ git add str_title.c                 # Add source code to staging area
$ git commit -m "Reading 11: Code"    # Commit work

$ git push -u origin reading11        # Push branch to GitLab

Merge Request

Remember to create a merge request and assign the appropriate TA from the Reading 11 TA List.

DO NOT MERGE your own merge request. The TAs use open merge requests to keep track of which assignments to grade. Closing them yourself will cause a delay in grading and confuse the TAs.