CIS 212 Project 5
Instrumenting a program to produce a profile
Due at 11:59pm on Monday, 6 May 2019
This project requires that you instrument three source files of a program that I provide to you in order to determine the number of times each function is called and the total amount of elapsed time spent in each function.
Section 6.1.1 of the textbook describes how to use /usr/bin/time to obtain performance characteristics for a program’s execution from the shell. Section 6.1.2 discusses how to measure elapsed time of various portions of a program by inserting source code into the program. You will be inserting such instrumentation into a working version of the wordperline program from Project 4.
1 Requirements
The source files that you need to modify are jsheap.c, jsstring.c, and wordperline.c. Your inserted instrumentation will keep track of the number of calls and the elapsed time spent in each of the functions in jsheap.c and jsstring.c. Your inserted code in wordperline.c will perform any required initialization of global data structures after processing arguments, and after all processing has completed, will print out the performance summary for all of the instrumented functions on stderr.
The files stringADT.c, arraylist.c, and iterator.c have been edited to call routines in jsheap.c and jsstring.c. This way, as wordperline uses the functions in these files while doing its work, your instrumentation can observe those calls. As with Project 4, you may not modify the ADT .h or .c files provided to you; you will have to compile them and link them together with your modified jsheap.o, jsstring.o, and wordperline.o to produce the instrumented version of wordperline. The Makefile provided does the appropriate assembly of the program.
2 Starting files
In Canvas, in Files/Projects, you will find a gzipped tar archive named project5start.tgz; this file contains the following files:
• input–afilethatcontainstext;thisisthesamefileusedinProject1.
• input1, input2 – other files containing text; these are the same files used in
Projects 2 and 3.
• tscript–abashscriptfilethatperformsanumberoftestsofyourwordperline using input, input1, input2, and test*.out; invoking
./tscript
will execute all of the tests using your executable wordperline.
• test*.out–thecorrectoutputfilesforthetestsintscript. -1-
CIS 212 Project 5
• arraylist.[ch]–headerandsourcefilefortheArrayListADT
• stringADT.[ch]–headerandsourcefilefortheStringADT
• iterator.[ch]–headerandsourcefilefortheIteratorADT,neededby ArrayList
• jsheap.[ch]–wrapperfunctionsthatinvokemalloc()andfree()
• jsstring.[ch]–wrapperfunctionsthatinvokestrchr(),strcmp(),
strcpy(), strdup(), strlen(), strncmp(), and strstr()
• itest.c–asimpletestprogramshowinghowtoinstrumentsourcecode
• Makefile
3 Hints
I suggest that you thoroughly review Section 6.1 of the textbook on measuring running time. I have included additional information below showing how such instrumentation can be done on a single function in a single source file.
4 Checking that your solution works correctly
tscript takes zero or more arguments; if one or more arguments are specified, tscript will only perform those specific tests; if no arguments are specified, all of the tests are performed.
The tests that tscript performs are:
a Tests that the call and elapsed time data for processing input are correct.
b Tests that the call and elapsed time data for processing input1 are correct.
c Tests that the call and elapsed time data for processing input2 are correct.
d Tests that the call and elapsed time data for processing input1 and input2 are
correct.
e Tests that the call and elapsed time data for processing 5 copies of input are correct.
f Tests that the call and elapsed time data for processing 10 copies of input are correct.
g Tests that the call and elapsed time data for processing 20 copies ofinput are correct.
For each test, tscript prints out “Starting test
“Stopping test
If there is any output between the actual command line and the Stopping line for any test, the test has failed.
-2-
CIS 212 Project 5
You will submit your solutions electronically by uploading a gzipped tar archive2 via Canvas.
Your TGZ archive should be named
6 itest.c as an instrumentation example
This section provides annotated source code of a test program, provided in the start archive,
showing you how such instrumentation can be performed.
6.1 preliminaries
/* itest – show how to instrument a function and print the results
* usage: ./itest [–calls=
* the instrumented function will be called `calls’ times; default is 1000
5 Submission1
* outputs number of calls
* Author: Joe Sventek
*/
#include
#include
#include
#include
#include
and ms of elapsed time on stderr
/* for fprintf() */
/* for strncmp() */
/* for atoi() */
/* for struct timespec & nanosleep() */
/* for struct timeval & gettimeofday() */
#define USESTR “usage: %s [–calls=n]\n”
The comments describe what the program does and how to invoke the program.
The #include lines are to bring in needed structure definitions and function signatures,
noted in the comments to the right of each #include.
Finally, we #define a format string to use if the user has supplied illegal arguments.
1 If you do not follow these submission instruction, I will NOT mark your submission and you will receive a 0 for the project.
2 See section 7 of Canvas/Files/Projects/P1Handout.pdf for instructions if you do not remember how to create a gzipped tar archive. Obviously, the filenames used for this project will be different.
-3-
CIS 212 Project 5
6.2 Neededstructuredeclaration[s]andglobalvariables
typedef struct accumulator {
char *name;
long long calls;
long long musecs;
} Accumulator;
long nAccumulators = 0L;
Accumulator *accumulators[1000];
We define a structure (Accumulator) where we keep track of:
• the name of a function
• the number of calls on the function
• the elapsed time in the function in microseconds
There will be one of these structures for each function we are instrumenting.
We also declare two global variables in which we keep track of the accumulators:
• nAccumulators–thisisthenumberofaccumulatorsthathavebeen“registered” with the system
• accumulators–thisisanarrayofpointerstotheregisteredaccumulators We have sized this array to hold 1000 entries; this is more than enough to cope with this
project.
6.3 Theinstrumentedfunction
void instrumented_function(void) {
struct timeval t1, t2;
static int init = 1;
static Accumulator ac = {“instrumented_function”, 0LL, 0LL};
if (init) {
accumulators[nAccumulators++] = ∾
} init = 0;
(void)gettimeofday(&t1, NULL);
{
struct timespec oneMs = {0, 1000000L}; /* one millisecond */
} nanosleep(&oneMs, NULL);
(void)gettimeofday(&t2, NULL);
ac.musecs += 1000000 * (t2.tv_sec – t1.tv_sec)
+ (t2.tv_usec – t1.tv_usec);
ac.calls += 1LL;
}
The actual body of the function is the block that declares oneMs and calls nanosleep(); everything else is needed to register the accumulator, measure the elapsed time, and update the calls and musecs fields of the accumulator.
-4-
CIS 212 Project 5
6.3.1 Registering the accumulator
static int init = 1;
static Accumulator ac = {“instrumented_function”, 0LL, 0LL};
if (init) {
accumulators[nAccumulators++] = ∾
init = 0; }
The first two lines show you another use of the static keyword in C. Recall that when we use it on global variables and on functions in a particular source file, it hides the existence of those names from the linker, so that code in other source files that may be linked to this source file cannot access those entities.
This use of static causes variables declared inside of a block (in this case a function block) to be allocated in global memory but the names are hidden within the block – in this case, only visible in the function. Since these variables are in global memory, and not on the stack, they retain their value between calls of the function.
The first time the function is called, init has a value of 1, corresponding to True in C. We then execute the statements in the first if statement. Since the last of those statements sets init to 0 (False), and since init retains its value between calls to the function, subsequent calls to the function will not execute the statements in the first if statement.
The only other statement executed in that if clause is to register the accumulator – we simply copy the address of our accumulator into the global accumulators[] array, incrementing the nAccumulators variable.
6.3.2 Determining the start and stop times
(void)gettimeofday(&t1, NULL);
{
struct timespec oneMs = {0, 1000000L}; /* one millisecond */
} nanosleep(&oneMs, NULL);
(void)gettimeofday(&t2, NULL);
gettimeofday() returns the current time as seconds and microseconds since a particular time in the past. t1 contains the current time before executing the actual statements of our function, and t2 contains the current time after executing those statements.
6.3.3 Update the accumulator
ac.musecs += 1000000 * (t2.tv_sec – t1.tv_sec)
+ (t2.tv_usec – t1.tv_usec);
ac.calls += 1LL;
}
A struct timeval has two members: tv_sec which contains an integer representing seconds, and tv_usec, an integer representing number of microseconds. We compute the number of microseconds that have elapsed between t1 and t2, and add this to the musecs member of our accumulator. We also increment the calls member of our accumulator.
-5-
CIS 212 Project 5
6.4 Dumptheaccumulators
void dumpAccumulators(FILE *fd) {
long k;
for (k = 0L; k < nAccumulators; k++) {
Accumulator *ac = accumulators[k];
long long musecs = ac->musecs;
fprintf(fd, “%-20s “, ac->name);
fprintf(fd, “%12Ld calls “, ac->calls);
fprintf(fd, “%15Ld.%03dms\n”, musecs / 1000, (int)(musecs % 1000));
} }
This function simply goes through the list of accumulators, printing out the data found in each one. The format strings indicate that:
• the name of the function should be printed out left justified in a 20-character wide field;
• the number of calls should be printed out as a decimal integer right justified in a 12-
character wide field;
• the elapsed time should be printed out as the number of milliseconds right justified in a
15-character wide field, followed by a decimal point, followed by the number of microseconds left over in a 3-character wide field, using a ‘0’ to right justify that number in the field; the resulting printout looks like a floating point number with 3 decimal places.
6.5 Themain()function
int main(int argc, char *argv[]) {
int i, n = 1000;
for (i = 1; i < argc; i++) {
if (strncmp(argv[i], "--calls=", 8) == 0)
elsen{= atoi(argv[i]+8);
fprintf(stderr, "Illegal flag: %s\n", argv[i]);
fprintf(stderr, USESTR, argv[0]);
} } return 1;
/* initialize the instrumentation system – nothing to do */ for (i = 0; i < n; i++) {
} instrumented_function();
dumpAccumulators(stderr);
return 0; }
First we process command arguments. Note the use of strncmp() to process long flags.
Next we initialize the instrumentation system, if needed. Given the way we have constructed the global variables and the Accumulator registration in the instrumented function[s], there is nothing to do here.
-6-
CIS 212 Project 5
Next we perform the functionality of our program – in this case, it is simply to invoke the instrumented function the specified number of times.
Finally, we call dumpAccumulators() to display the collected information on stderr.
-7-
CIS 212 Project 5
Grading Rubric
Your submission will be marked on a 50 point scale. Substantial emphasis is placed upon WORKING submissions, and you will note that a large fraction of the points are reserved for this aspect. It is to your advantage to ensure that whatever you submit compiles, links, and runs correctly. The information returned to you will indicate the number of points awarded for the submission.
You must be sure that your code works correctly on the virtual machine under VirtualBox, regardless of which platform you use for development and testing. Leave enough time in your development to fully test on the virtual machine before submission.
The marking scheme is as follows:
Points
Description
5
Your report – honestly describes the state of your submission
3
3
3
3
3
3
3
3
3
1
2
5
10
Your submission passes test a.
Your submission passes test b.
Your submission passes test c.
Your submission passes test d.
Your submission passes test e.
Your submission passes test f.
Your submission passes test g.
modified wordperline.c, jsheap.c, and jsstring.c successfully compile modified wordperline.c, jsheap.c, and jsstring.c compile with no warnings The link phase to create wordperline is successful
The link phase to create wordperline is successful with no warnings There are no memory leaks in your program
The code could have worked with minor modification to the source.
Note that:
• Your report needs to be honest. Stating that everything works and then finding that it
doesn’t is offensive. The 5 points associated with the report are probably the easiest 5
points you will ever earn as long as you are honest.
• The 10 points for “could have worked” is the maximum awarded in this category; your
mark in this category may be lower depending upon how close you were to a working implementation.
-1-