CMSC216 Lab04: Valgrind and Makefiles

                           _________________

                            LAB04 QUESTIONS
                           _________________


Exercise Instructions
=====================

  Follow the instructions below to experiment with topics related to
  this exercise.
  - For sections marked QUIZ, fill in an (X) for the appropriate
    response in this file. Use the command `make test-quiz' to see if
    all of your answers are correct.
  - For sections marked CODE, complete the code indicated. Use the
    command `make test-code' to check if your code is complete.
  - DO NOT CHANGE any parts of this file except the QUIZ sections as it
    may interfere with the tests otherwise.
  - If your `QUESTIONS.txt' file seems corrupted, restore it by copying
    over the `QUESTIONS.txt.bk' backup file.
  - When you complete the exercises, check your answers with `make test'
    and if all is well, create a zip file with `make zip' and upload it
    to Gradescope. Ensure that the Autograder there reflects your local
    results.
  - IF YOU WORK IN A GROUP only one member needs to submit and then add
    the names of their group.


PROBLEM 1: A Bit of Debugging
=============================

  This problem will focus on debugging an existing C program which was
  written in a rather sloppy fashion leading to some serious flaws in it
  including memory problems.  This will be a chance to practice reading
  Valgrind error messages and using them to locate problems in the code
  and resolve them.


Context
~~~~~~~

  Your current supervisor has left the following note with the code and
  data files in the code pack.

  ,----
  | TRAINER: We have most of the data we needed in the mon-*.txt files but
  | we need to complete the analysis I promised Prof. Birch by the end of
  | the week.  We need the Median Base Points of the samples in the data
  | files. I've written a program in mon_main.c to calculate this in a
  | flexible way but it keeps crashing and I don't have time to debug
  | it. I'm leaving that to you: Sorry!  I've heard Valgrind may help to
  | diagnose the memory problems but I never learned to use it
  | myself. Please make corrections to the code to make it work so we can
  | determine the median Base Points for the samples outlined in the
  | tests.
  | 
  | -Prof. Oak
  `----


Intended Behavior
~~~~~~~~~~~~~~~~~

  The intended behavior of the program `mon_main' is to read data files
  formatted like `mon-top5.txt' which have 3 columns. It will store all
  the data in an array, sort it, and then print the median (middle)
  element.
  ,----
  | >> make
  | gcc -Wall -Werror -g  -c mon_main.c
  | gcc -Wall -Werror -g  -o mon_main mon_main.o
  | 
  | >> ./mon_main
  | usage: ./mon_main <input_file> [filter]
  | 
  | >> ./mon_main mon-top5.txt 
  | Sorted array:
  |   0: Charmander   309 Fire        
  |   1: Squirtle     314 Water       
  |   2: Bulbasaur    318 Grass       
  |   3: Pikachu      320 Electric    
  |   4: Psyduck      320 Water       
  | Median BASE_POINTS is
  |   2: Bulbasaur 318 Grass
  | 
  | >> ./mon_main mon-top5.txt Water
  | Sorted array:
  |   0: Squirtle     314 Water       
  |   1: Psyduck      320 Water       
  | Median BASE_POINTS is
  |   1: Psyduck 320 Water
  | 
  | >> ./mon_main mon-top5.txt Ground
  | No elements left after filtering on 'Ground'
  `----

  Unfortunately the behavior of the program at present is somewhat less
  helpful.
  ,----
  | >> ./mon_main mon-top5.txt 
  | Segmentation fault (core dumped)
  `----


Instructions
~~~~~~~~~~~~

  As is indicated (and is often the case with other people's code) the
  program has some bugs which will need to be corrected. The ultimate
  goals is to correct the code so that it passes the test cases
  provided.  The QUIZ questions in `QUESTIONS.txt' relate to some of
  Error messages that will be produced in the tests and are a good way
  to get started.


PROBLEM 1 QUIZ: Errors in mon_main.c
====================================

  Study the code and error messages produced by test cases or command
  line runs of the program to start determining where memory errors
  occur and how they may be corrected. Answer the following QUIZ
  questions.


First Test
~~~~~~~~~~

  Run the first test via `make test-prob1' or `make test-prob1
  testnum=1'. It will fail. Analyze its output, both the Side-by-Side
  diff output and the Valgrind Report which is lower in the results.

  Check all of the following that are relevant to the bugs reported.
  - ( ) Valgrind messages indicate that this is likely a bug in Valgrind
    itself which should be reported to the tool developers ASAP.
  - ( ) The Valgrind messages indicate that there is likely a memory
    problem with writing too far into a block of memory.
  - ( ) The Valgrind Report indicates that a memory Write is being done
    some distance BEFORE a malloc()'d block
  - ( ) The Valgrind Report indicates that a memory Write is being done
    some distance AFTER a malloc()'d block
  - ( ) The memory Write is problematic because the wrong C syntax is
    used in the program: no * or -> is used to dereference a pointer.
  - ( ) The memory Write is problematic because it is assuming a pointer
    to an array but not enough space has been allocated


  The following Valgrind Error message often appears in the VALGRIND
  REPORT towards the bottom of test results.
  ,----
  | ==85164== Invalid write of size 8
  | ==85164==    at 0x109762: main (mon_main.c:99)
  | ==85164==  Address 0x4a9e374 is 0 bytes after a block of size 132 alloc'd
  | ==85164==    at 0x48447A8: malloc (vg_replace_malloc.c:446)
  | ==85164==    by 0x109661: main (mon_main.c:83)
  `----
  Check ALL of the following that correspond to information in this
  message.
  - ( ) It reports that some variable / array element is being assigned
    (write-en to) but the pointer to the variable is out of bounds
  - ( ) It gives a source code line where the out of bounds access is
    occurring.
  - ( ) It shows the exact memory address that is being accessed that is
    out of bounds (in hexadecimal format)
  - ( ) It gives the relative position of the memory access as just
    after a block that was allocated using malloc() and the location in
    source code where that allocation occurred

  Make some code changes to correct this bug and check that any error
  messages change.


First Test Again
~~~~~~~~~~~~~~~~

  Run the first test again and check new error messages. Which part of
  the code seems to be problematic now?
  - ( ) The loop that reads data from the file into an array
  - ( ) The loop that prints out the contents of the sorted array
  - ( ) The insertion sort routine meant to sort the data
  - ( ) The indexing to determine the median (it accesses an
    out-of-bounds element)

  Use any nearby hints to fix the code and reduce the errors / generate
  new errors.


First Test AGAIN
~~~~~~~~~~~~~~~~

  If all has gone well, the output for the first test will now appear
  correct BUT there are additional problems reported by Valgrind. Check
  ALL of the following problems appear in the Valgrind report.

  - ( ) There are Invalid reads AFTER a heap-allocated block
  - ( ) There are Invalid writes BEFORE a heap-allocated block
  - ( ) Uninitialized memory used to determine a conditional jump/move
  - ( ) Memory is lost / leaked as it is not de-allocated before the end
    of the program

  One of the problems identified in the Valgrind output is associated
  with the following lines which illustrate a common beginner mistake
  (something one wouldn't expect the seasoned Prof. Oak to do but
  perhaps C isn't his strong suit...)
  ,----
  |   char *filter = malloc(sizeof(char));
  |   if(argc > 2){                 // filter present
  |     filter = argv[2];
  |   }
  |   else{                         // default to no filtering
  |     filter = NULL;
  |   }
  `----
  Why is the above code a memory error?
  - ( ) malloc()'ing memory for filter then re-assigning it to point
    elsewhere creates a memory leak: the malloc()'d block can never be
    free()'d
  - ( ) character pointers like filter should not be pointed to
    heap-allocated space with malloc()
  - ( ) When pointers should not be set to NULL as this will cause a
    segmentation fault
  - ( ) pointing filter at a string like argv[2] leads to problems later
    as argv[2] is not heap-allocated so the code that free()'s it will
    causes an error

  Use the error messages provided in the Valgrind Report to fix the
  remaining error messages associated with this test.

  Hint: there are 3 changes that need to be made.


FIRST TEST!
~~~~~~~~~~~

  The First test should now pass. In fact, a few more tests may pass.

  Carry on with this pattern of inspecting test results, especially the
  VALGRIND REPORT to continue diagnosing errors to correct them. A few
  hints:

  - Any attempt to access a NULL pointer will trigger a segmentation
    fault; this is reported as an "Invalid Read" or "Invalid Write" of
    the address 0x0. When working with pointers you know may be NULL,
    check whether they are NULL before attempting to dereference them.

  - All code paths of exiting must de-allocate all memory. If you are
    exiting the program early, make sure to free() an malloc()'d blocks
    and close any files.

  - Opening files can fail, often due to the wrong filename being typed
    in. Make sure to check for this condition and report appropriate
    errors. Attempting to work with unopened file is likely to end in
    crashes.


PROBLEM 1 CODE: Repair mon_main.c
=================================

  As indicated above, continue debugging mon_main.c until all tests
  pass. A completely corrected program should give the following results
  on running tests:

  ,----
  | >> make test-prob1
  | gcc -Wall -Werror -g -fstack-protector-all  -c mon_main.c
  | gcc -Wall -Werror -g -fstack-protector-all  -o mon_main mon_main.o
  | ./testy -o md test_mon_main.org 
  | =================================================
  | == test_mon_main.org : mon_main application tests
  | == Running 8 / 8 tests
  | 1) ./mon_main mon-lvl1.txt Fire      : ok
  | 2) ./mon_main mon-all.txt Grass      : ok
  | 3) ./mon_main mon-top5.txt           : ok
  | 4) ./mon_main mon-lvl1.txt           : ok
  | 5) ./mon_main mon-all.txt            : ok
  | 6) ./mon_main mon-all.txt Ground     : ok
  | 7) ./mon_main no-file.txt            : ok
  | 8) ./mon_main mon-lvl2.txt BadFilter : ok
  | =================================================
  | RESULTS: 8 / 8 tests passed
  `----


PROBLEM 2 QUIZ: Questions on Makefiles
======================================

  Review the presentation of `Makefile' basics in the lab description
  and analyze the examples provided in the demo directories
  `makeproblem-demo-little' and `makeproblem-demo-big'. Then answer the
  following questions.


Command Execution
~~~~~~~~~~~~~~~~~

  Which of the following best describes when the commands for a rule are
  run?
  - ( ) The commands for all targets in the Makefile are all run every
    time make is used
  - ( ) Only the commands associated with the target named on the
    command line are run; e.g. `make targ5` will run commands associated
    with targ5
  - ( ) Commands for a given rule execute only if make detects a its
    target is needed and then only if the target is missing or older
    than its dependencies


Rule Syntax
~~~~~~~~~~~

  Which of the following Rules correctly lays out the syntax for target,
  dependencies, and commands in a Makefile.
  ,----
  | # RULE A
  | target : dependency1 dependency2
  | 	command1
  | 	command2
  | 	command3
  | 
  | # RULE B
  | target : dependency1 dependency2
  | command1
  | command2
  | command3
  | 
  | # RULE C
  | dependency1 dependency2 : target 
  | 	command1
  | 	command2
  | 	command3
  | 
  | # RULE D
  | target :
  | 	command1
  | 	command2
  | 	command3
  | : dependency1 dependency2
  `----
  - ( ) RULE A
  - ( ) RULE B
  - ( ) RULE C
  - ( ) RULE D


Variance in Makefiles
~~~~~~~~~~~~~~~~~~~~~

  Check ALL that are true about Makefile features
  - ( ) Rules may have 0 dependencies
  - ( ) Rules may have 0 commands
  - ( ) Rules have no more than 1 command
  - ( ) Rules have no more than 1 dependency
  - ( ) Makefiles can set up explicit variables for use in rules
  - ( ) Makefiles provide a variety of automatic variables for use in
    rules
  - ( ) A Makefile can have deeply nested decencies: targA depends on
    targB depends on targC depends on targD etc.


Problem 2 CODE: makeproblem-create
==================================

  Complete the template in the subdirectory
  `makeproblem-create/Makefile' according to the comments there.  The
  essential idea is to build the linked list program from an earlier lab
  and add a few other targets.  Once you add rules for certain targets,
  you can test them interactively via commands like `make' and `make
  clean' in that directory. You can also run the automated tests of this
  via a problem test:

  ,----
  | >> cd lab04-code
  | >> make test-prob2   # run tests for Makefile under makeproblem-create
  | ...
  `----