CMSC216 Lab04: Debugging Memory Problems

                           _________________

                            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.


A Bit of Debugging
==================

  This lab 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 he 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 HP 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 HP 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 HP is
  |   2: Bulbasaur 318 Grass
  | 
  | >> ./mon_main mon-top5.txt Water
  | Sorted array:
  |   0: Squirtle     314 Water       
  |   1: Psyduck      320 Water       
  | Median HP is
  |   1: Psyduck 320 Water
  | 
  | >> ./mon_main mon-top5.txt Ground
  | No elements left after filtering on 'Ground'
  `----

  Unfortunately the behavior of the program in its present stat 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 QUIZ
  questions that follow relate to some of Error messages that will be
  produced in the tests. The ultimate goals is to correct the code so
  that it passes the test cases provided.


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-code' or `make test-code
  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 that 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
  - ( ) It gives the source code line which should be changed to correct
    the error / fix the memory problem.

  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.


CODE Repair mon_main.c
======================

  As indicated above, continue debugging mon_main.c until all tests
  pass.