Description
CSC 322 Systems Programming Lab Assignment 1
I. Goal
In the first lab, we will develop a system program which provides mathematical commands
using C language. It must be an errorless system program, in which user starts the program,
enter commands, see the desired result, and finishes it if he or she wants to quit. For students
who has the first time to use C language, this project will be a good initiator to learn a new
programming language. Students who already know C language also will have a good
opportunity to warm up their programming abilities and get prepared for the rest of labs.
II. Introduction
A. Basic Calculations
The system program provides four basic mathematical commands shown in the below table.
Each command presents an operator, and requires operands as parameters. For instance,
when user enters sum 4 2, the program returns the result 6 (= 4 + 2) in the next line. And
then it will go to the next prompt waiting for user’s next command. Note that each operator
should have two operands, and if a command has more than 2 parameters, it is an incorrect
syntax. The commands are following:
Command Description
sum Summation of parameters. For instance, sum 4 2 calculates 4 + 2.
mul Multiplication of parameters. For instance, mul 4 2 calculates 4 x 2.
sub Subtraction of parameters. The first parameter is minuend, and all other
parameters are subtrahends. For instance, sub 4 2 calculates 4 – 2.
div Diving two numbers. It will allow only two parameters. The first
parameter is dividend and the second parameter is divisor. For instance,
div 4 2 calculates 4 ÷ 2 = 2
B. Collatz Conjecture
The system program provides an advance mathematical command, which is called Collatz
conjecture. The Collatz conjecture concerns what happens when we take any positive integer
n and apply the following algorithm:
CSC322 Lab 1
2
The conjecture states that when this algorithm is continually applied, all positive integers
will eventually reach 1. For example, if n = 19, the sequence is following:
19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
The command has one parameter. If it has more than two parameters, it is an incorrect syntax.
Command Description
col Finding collatz conjecture of parameter. For instance, col 19 returns a
collatz sequence.
C. Program Design
The system program should run on Linux machine at cs.oswego.edu. Once it is compiled
and performed, it draws user to its own computing environment by showing prompt following
the format below.
yourID> $
Then user will enter a command and parameters if necessary. The syntax of the command is
following.
command [parameter]*
Note that some commands such as basic calculations need multiple parameters. When each
command finishes its own calculation, it will show the results on the screen as shown in the
Figure 1, and the new prompt follows for the next command.
[jwlee@deepwater:~]$ cc lab1_jwlee.c –o lab1
[jwlee@deepwater:~]$ ./lab1
jwlee> $ sum 3 2
5
jwlee> $ mul 5 7
35
jwlee> $ sub 6 7
-1
jwlee> $ div 4 2
2
jwlee> $ col 19
19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
jwlee> $ col 35
35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1
jwlee> $ bye
bye
[jwlee@deepwater:~]$
Figure 1. Example of project 1
CSC322 Lab 1
3
To quit the program, user should enter command bye without any parameters. Then the
program ends after a simple message bye, which notifies the end of the program. It has no
parameter, and if it has any parameter, it is an incorrect syntax.
Command Description
bye Finishing the program.
D. Extra work
Each basic mathematical command in the original program can calculate only two operands,
for instance, sum 3 5 will return 8 (=3 + 5). In the real world, however you may be asked to
calculate more complicated formula such as is 5 + (7 * (4 – 2)). Thus, you will enhance these
commands so that they can work for more complicated calculation as an extra work. The
example formula has three operators, four operands, and two pairs of parentheses. For
calculating the example, you will enter the following command:
sum 5 (mul 7 (sub 4 2))
For simplicity, the system program will restrict the maximum number of operators, so there
are no more than 7 operators.
This is not mandatory but optional. Therefore, it will give you 6 extra points, which is worth
30% of the assigned points. Those who have experiences of C before are strongly encouraged
to do this extra work.
III. Requirements
A. Developing environment
The program should be implemented in C only. The program in another language will not be
graded. And the program should be executable in CS Linux machine. The program which
cannot be compiled or executed in the CS Linux machine will be considered as incomplete
program, and will lose most points.
B. Handling exceptions
The program must detect errors while running. The errors may occur when user violates the
syntax of the command or enters wrong inputs (character, more than 2 numbers, etc.). Also
any mathematically incorrect calculations, for instance, div 3 0, must be detected. When
the program detects any error cases, it should handle properly by giving some error
messages to the user, and still be runnable. The program, which fails to detect such
errors and to properly handle them, will be taken off penalty points.
C. Readability of source code
The source code should be easy to read with good indentation and proper amount of
comments.
CSC322 Lab 1
4
D. Creating a readme file
The program should be submitted along with a readme file which has information such as
student ID, name, etc. It also may provide instruction to run this program if exists. Those who
complete extra work need to describe their progress and implementation in one short
paragraph for instructor to grade the extra work.
The source file and readme file should be named following the format below. Those who are
not following the naming rule will also be taken off penalty points.
lab1_yourID#.c
lab1_yourID#_readme.txt
E. Submitting by due
The program should be submitted to Blackboard within the two weeks after the project is
posted. Due is September 21. All submission by 11:59 PM on that day will be accepted
without any penalty. On the due date, Blackboard may be suffering of too much network
traffics and be unstable. There is no excuse about the issue, therefore you are strongly
recommended to submit earlier than the due date.
IV. Grading
This project is assigned 20 points, which is 10% of the final grade. Groups who complete
extra work will receive 6 additional points.
A.Grading criteria
The project will be graded by evaluating the requirement. Any missing and unsatisfiable
criteria will take off points. The tentative and brief criteria are below.
• Compilation: 5 points (25%)
• Execution: 10 points (50%)
• Error detection & others: 5 points (25%)
B. Late penalty
Late submission will take off 10% per day per week after due date. Thus, submission
after 10 weeks will not be accepted in any circumstances.
V. Academic Integrity
Any dishonest behaviors will not be tolerated in this class. Any form of plagiarism and
cheating will be dealt with according to the guidelines on the Academic Integrity Policy online at https://www.oswego.edu/integrity. For more information about university policies,
see the following online catalog at:
https://catalog.oswego.edu/content.php?catoid=2&navoid=47#stat_inte_inte
Student who is against the honor code will not have any credits in this project.
CSC322 Lab Assignment: Defusing a Binary Bomb
1 Introduction
The nefarious Dr. Evil has planted a slew of “binary bombs” on our class machines. A binary bomb is a
program that consists of a sequence of phases. Each phase expects you to type a particular string on stdin.
If you type the correct string, then the phase is defused and the bomb proceeds to the next phase. Otherwise,
the bomb explodes by printing “BOOM!!!” and then terminating. The bomb is defused when every phase
has been defused.
There are too many bombs for us to deal with, so we are giving each student a bomb to defuse. Your
mission, which you have no choice but to accept, is to defuse your bomb before the due date. Good luck,
and welcome to the bomb squad!
Step 1: Get Your Bomb
You can obtain your bomb by pointing your Web browser at:
https://pi.cs.oswego.edu:17322/
This will display a binary bomb request form for you to fill in. Enter your user name and email address and
hit the Submit button. The server will build your bomb and return it to your browser in a tar file called
bombk.tar, where k is the unique number of your bomb.
Save the bombk.tar file to a (protected) directory in which you plan to do your work. Then give the
command: tar -xvf bombk.tar. This will create a directory called ./bombk with the following
files:
• README: Identifies the bomb and its owners.
• bomb: The executable binary bomb.
• bomb.c: Source file with the bomb’s main routine and a friendly greeting from Dr. Evil.
• writeup.{pdf,ps}: The lab writeup.
1
If for some reason you request multiple bombs, this is not a problem. Choose one bomb to work on and
delete the rest.
Step 2: Defuse Your Bomb
Your job for this lab is to defuse your bomb.
You must do the assignment on one of the CS Linux machines. In fact, there is a rumor that Dr. Evil really
is evil, and the bomb will always blow up if run elsewhere. There are several other tamper-proofing devices
built into the bomb as well, or so we hear.
You can use many tools to help you defuse your bomb. Please look at the hints section for some tips and
ideas. The best way is to use your favorite debugger to step through the disassembled binary.
Each time your bomb explodes it notifies the bomblab server, and you lose 1/2 point (up to a max of 20
points) in the final score for the lab. So there are consequences to exploding the bomb. You must be careful!
The first four phases are worth 10 points each. Phases 5 and 6 are a little more difficult, so they are worth
15 points each. So the maximum score you can get is 70 points.
Although phases get progressively harder to defuse, the expertise you gain as you move from phase to phase
should offset this difficulty. However, the last phase will challenge even the best students, so please don’t
wait until the last minute to start.
The bomb ignores blank input lines. If you run your bomb with a command line argument, for example,
linux> ./bomb psol.txt
then it will read the input lines from psol.txt until it reaches EOF (end of file), and then switch over
to stdin. In a moment of weakness, Dr. Evil added this feature so you don’t have to keep retyping the
solutions to phases you have already defused.
To avoid accidentally detonating the bomb, you will need to learn how to single-step through the assembly
code and how to set breakpoints. You will also need to learn how to inspect both the registers and the
memory states. One of the nice side-effects of doing the lab is that you will get very good at using a
debugger. This is a crucial skill that will pay big dividends the rest of your career.
Logistics
This is an individual project. All handins are electronic. Clarifications and corrections will be posted as
needed.
Handin
There is no explicit handin. The bomb will notify your instructor automatically about your progress as you
work on it. You can keep track of how you are doing by looking at the class scoreboard at:
2
https://pi.cs.oswego.edu:17323/scoreboard
This web page is updated continuously to show the progress for each bomb.
Hints (Please read this!)
There are many ways of defusing your bomb. You can examine it in great detail without ever running the
program, and figure out exactly what it does. This is a useful technique, but it not always easy to do. You
can also run it under a debugger, watch what it does step by step, and use this information to defuse it. This
is probably the fastest way of defusing it.
We do make one request, please do not use brute force! You could write a program that will try every
possible key to find the right one. But this is no good for several reasons:
• You lose 1/2 point (up to a max of 20 points) every time you guess incorrectly and the bomb explodes.
• Every time you guess wrong, a message is sent to the bomblab server. You could very quickly saturate
the network with these messages, and cause the system administrators to revoke your computer access.
• We haven’t told you how long the strings are, nor have we told you what characters are in them. Even
if you made the (incorrect) assumptions that they all are less than 80 characters long and only contain
letters, then you will have 2680 guesses for each phase. This will take a very long time to run, and
you will not get the answer before the assignment is due.
There are many tools which are designed to help you figure out both how programs work, and what is wrong
when they don’t work. Here is a list of some of the tools you may find useful in analyzing your bomb, and
hints on how to use them.
• gdb
The GNU debugger, this is a command line debugger tool available on virtually every platform. You
can trace through a program line by line, examine memory and registers, look at both the source code
and assembly code (we are not giving you the source code for most of your bomb), set breakpoints,
set memory watch points, and write scripts.
The CS:APP web site
https://csapp.cs.cmu.edu/public/students.html
has a very handy single-page gdb summary that you can print out and use as a reference. Here are
some other tips for using gdb.
– To keep the bomb from blowing up every time you type in a wrong input, you’ll want to learn
how to set breakpoints.
– For online documentation, type “help” at the gdb command prompt, or type “man gdb”,
or “info gdb” at a Unix prompt. Some people also like to run gdb under gdb-mode in
emacs.
3
• objdump -t
This will print out the bomb’s symbol table. The symbol table includes the names of all functions and
global variables in the bomb, the names of all the functions the bomb calls, and their addresses. You
may learn something by looking at the function names!
• objdump -d
Use this to disassemble all of the code in the bomb. You can also just look at individual functions.
Reading the assembler code can tell you how the bomb works.
Although objdump -d gives you a lot of information, it doesn’t tell you the whole story. Calls to
system-level functions are displayed in a cryptic form. For example, a call to sscanf might appear
as:
8048c36: e8 99 fc ff ff call 80488d4 <_init+0x1a0>
To determine that the call was to sscanf, you would need to disassemble within gdb.
• strings
This utility will display the printable strings in your bomb.
Looking for a particular tool? How about documentation? Don’t forget, the commands apropos, man,
and info are your friends. In particular, man ascii might come in useful. info gas will give you
more than you ever wanted to know about the GNU Assembler. Also, the web may also be a treasure trove
of information. If you get stumped, feel free to ask your instructor for help.
4
CSC 322 Cache Lab: Understanding Cache Memories
Overview This lab will help you understand the impact that cache memories can have on the performance of your C programs. You will write a small C program that simulates the behavior of a cache memory. This is Part A. For those who want to extra work, you will optimize a small matrix transpose function, with the goal of minimizing the number of cache misses. This extra work will give you a good opportunity for optimizing a program. This is described in Part B. 3 Downloading the assignment Start by copying the file /home/jwlee/CSC322/cachelab-handout.tar to a protected Linux directory in which you plan to do your work. It is also uploaded in the Blackboard, so you may download it and put it into the Linux machine as well. Then give the command linux> tar xvf cachelab-handout.tar This will create a directory called cachelab-handout that contains a number of files. You will be modifying two files: csim.c which is the original lab (Part A) and trans.c which is the extra lab (Part B). To compile these files, type: linux> make clean linux> make 1 WARNING: Do not let the Windows WinZip program open up your .tar file (many Web browsers are set to do this automatically). Instead, save the file to your Linux directory and use the Linux tar program to extract the files. In general, for this class you should NEVER use any platform other than Linux to modify your files. Doing so can cause loss of data (and important work!). 4 Description The lab has two parts. In Part A you will implement a cache simulator, which is the mandatory and original lab. In Part B you will write a matrix transpose function that is optimized for cache performance as an extra and optional lab. 4.1 Reference Trace Files The traces subdirectory of the handout directory contains a collection of reference trace files that we will use to evaluate the correctness of the cache simulator you write in Part A. The trace files are generated by a Linux program called valgrind. For example, typing linux> valgrind –log-fd=1 –tool=lackey -v –trace-mem=yes ls -l on the command line runs the executable program “ls -l”, captures a trace of each of its memory accesses in the order they occur, and prints them on stdout. In the Oswego Linux machine, valgrind is not installed, but you can use the five reference files in the subdirectory. For evaluation, more trace files will be given. Valgrind memory traces have the following form: I 0400d7d4,8 M 0421c7f0,4 L 04f6b868,8 S 7ff0005c8,8 Each line denotes one or two memory accesses. The format of each line is [space]operation address,size The operation field denotes the type of memory access: “I” denotes an instruction load, “L” a data load, “S” a data store, and “M” a data modify (i.e., a data load followed by a data store). There is never a space before each “I”. There is always a space before each “M”, “L”, and “S”. The address field specifies a 64-bit hexadecimal memory address. The size field specifies the number of bytes accessed by the operation. 4.2 Part A: Writing a Cache Simulator In Part A you will write a cache simulator in csim.c that takes a valgrind memory trace as input, simulates the hit/miss behavior of a cache memory on this trace, and outputs the total number of hits, misses, and evictions. 2 We have provided you with the binary executable of a reference cache simulator, called csim-ref, that simulates the behavior of a cache with arbitrary size and associativity on a valgrind trace file. It uses the LRU (least-recently used) replacement policy when choosing which cache line to evict. The reference simulator takes the following command-line arguments: Usage: ./csim-ref [-hv] -s -E -b -t • -h: Optional help flag that prints usage info • -v: Optional verbose flag that displays trace info • -s : Number of set index bits (S = 2s is the number of sets) • -E : Associativity (number of lines per set) • -b : Number of block bits (B = 2b is the block size) • -t : Name of the valgrind trace to replay The command-line arguments are based on the notation (s, E, and b) from page 597 of the CS:APP2e textbook. For example: linux> ./csim-ref -s 4 -E 1 -b 4 -t traces/yi.trace hits:4 misses:5 evictions:3 The same example in verbose mode: linux> ./csim-ref -v -s 4 -E 1 -b 4 -t traces/yi.trace L 10,1 miss M 20,1 miss hit L 22,1 hit S 18,1 hit L 110,1 miss eviction L 210,1 miss eviction M 12,1 miss eviction hit hits:4 misses:5 evictions:3 Your job for Part A is to fill in the csim.c file so that it takes the same command line arguments and produces the identical output as the reference simulator. Notice that this file is almost completely empty. You’ll need to write it from scratch. Programming Rules for Part A • Include your name, ID and user account (login ID) in the header comment for csim.c. 3 • Your csim.c file must compile without warnings in order to receive credit. • Your simulator must work correctly for arbitrary s, E, and b. This means that you will need to allocate storage for your simulator’s data structures using the malloc function. Type “man malloc” for information about this function. • For this lab, we are interested only in data cache performance, so your simulator should ignore all instruction cache accesses (lines starting with “I”). Recall that valgrind always puts “I” in the first column (with no preceding space), and “M”, “L”, and “S” in the second column (with a preceding space). This may help you parse the trace. • To receive credit for Part A, you must call the function printSummary, with the total number of hits, misses, and evictions, at the end of your main function: printSummary(hit_count, miss_count, eviction_count); • For this this lab, you should assume that memory accesses are aligned properly, such that a single memory access never crosses block boundaries. By making this assumption, you can ignore the request sizes in the valgrind traces. 4.3 (extra work)Part B: Optimizing Matrix Transpose In Part B you will write a transpose function in trans.c that causes as few cache misses as possible. Let A denote a matrix, and Aij denote the component on the ith row and jth column. The transpose of A, denoted AT , is a matrix such that Aij = AT ji. To help you get started, we have given you an example transpose function in trans.c that computes the transpose of N × M matrix A and stores the results in M × N matrix B: char trans_desc[] = “Simple row-wise scan transpose”; void trans(int M, int N, int A[N][M], int B[M][N]) The example transpose function is correct, but it is inefficient because the access pattern results in relatively many cache misses. Your job in Part B is to write a similar function, called transpose_submit, that minimizes the number of cache misses across different sized matrices: char transpose_submit_desc[] = “Transpose submission”; void transpose_submit(int M, int N, int A[N][M], int B[M][N]); Do not change the description string (“Transpose submission”) for your transpose_submit function. The autograder searches for this string to determine which transpose function to evaluate for credit. 4 Programming Rules for Part B • Include your name, ID and user account (login ID) in the header comment for trans.c. • You need to mention that you complete Part B. If you do not mention, your program will be graded without the extra work. • Your code in trans.c must compile without warnings to receive credit. • You are allowed to define at most 12 local variables of type int per transpose function.1 • You are not allowed to side-step the previous rule by using any variables of type long or by using any bit tricks to store more than one value to a single variable. • Your transpose function may not use recursion. • If you choose to use helper functions, you may not have more than 12 local variables on the stack at a time between your helper functions and your top level transpose function. For example, if your transpose declares 8 variables, and then you call a function which uses 4 variables, which calls another function which uses 2, you will have 14 variables on the stack, and you will be in violation of the rule. • Your transpose function may not modify array A. You may, however, do whatever you want with the contents of array B. • You are NOT allowed to define any arrays in your code or to use any variant of malloc. 5 Evaluation This section describes how your work will be evaluated. The full score for this lab is 20 points and extra 10 points: • Part A: 20 Points (18 points for test cases, 2 points for compilation) • Part B: 8 Points 5.1 Evaluation for Part A For Part A, we will run your cache simulator using different cache parameters and traces. There are five test cases running for evaluation, and each worth 3 points. They are randomly chosen from below. ilnux> ./csim -s 1 -E 1 -b 1 -t traces/yi2.trace linux> ./csim -s 4 -E 2 -b 4 -t traces/yi.trace linux> ./csim -s 2 -E 1 -b 4 -t traces/dave.tracei 1The reason for this restriction is that our testing code is not able to count references to the stack. We want you to limit your references to the stack and focus on the access patterns of the source and destination arrays. 5 linux> ./csim -s 2 -E 1 -b 3 -t traces/trans.trace linux> ./csim -s 2 -E 2 -b 3 -t traces/trans.trace linux> ./csim -s 2 -E 4 -b 3 -t traces/trans.trace linux> ./csim -s 5 -E 1 -b 5 -t traces/trans.trace linux> ./csim -s 5 -E 1 -b 5 -t traces/long.trace You can use the reference simulator csim-ref to obtain the correct answer for each of these test cases. During debugging, use the -v option for a detailed record of each hit and miss. For each test case, outputting the correct number of cache hits, misses and evictions will give you full credit for that test case. Each of your reported number of hits, misses and evictions is worth 1/3 of the credit for that test case. That is, if a particular test case is worth 3 points, and your simulator outputs the correct number of hits and misses, but reports the wrong number of evictions, then you will earn 2 points. 5.2 Evaluation for Part B For Part B, we will evaluate the correctness and performance of your transpose_submit function on three different-sized output matrices: • 32 × 32 (M = 32, N = 32) • 64 × 64 (M = 64, N = 64) • 61 × 67 (M = 61, N = 67) 5.2.1 Performance (8 pts) For each matrix size, the performance of your transpose_submit function is evaluated by using valgrind to extract the address trace for your function, and then using the reference simulator to replay this trace on a cache with parameters (s = 5, E = 1, b = 5). Your performance score for each matrix size scales linearly with the number of misses, m, up to some threshold: • 32 × 32: 2 points if m < 300, 0 points if m > 600 • 64 × 64: 3 points if m < 1, 300, 0 points if m > 2, 000 • 61 × 67: 3 points if m < 2, 000, 0 points if m > 3, 000 Your code must be correct to receive any performance points for a particular size. Your code only needs to be correct for these three cases and you can optimize it specifically for these three cases. In particular, it is perfectly OK for your function to explicitly check for the input sizes and implement separate code optimized for each case. 6 6 Working on the Lab 6.1 Working on Part A We have provided you with an autograding program, called test-csim, that tests the correctness of your cache simulator on the reference traces. Be sure to compile your simulator before running the test: linux> make linux> ./test-csim Your simulator Reference simulator Points (s,E,b) Hits Misses Evicts Hits Misses Evicts 3 (1,1,1) 9 8 6 9 8 6 traces/yi2.trace 3 (4,2,4) 4 5 2 4 5 2 traces/yi.trace 3 (2,1,4) 2 3 1 2 3 1 traces/dave.trace 3 (2,1,3) 167 71 67 167 71 67 traces/trans.trace 3 (2,2,3) 201 37 29 201 37 29 traces/trans.trace 3 (2,4,3) 212 26 10 212 26 10 traces/trans.trace 3 (5,1,5) 231 7 0 231 7 0 traces/trans.trace 6 (5,1,5) 265189 21775 21743 265189 21775 21743 traces/long.trace 27 For each test, it shows the number of points you earned, the cache parameters, the input trace file, and a comparison of the results from your simulator and the reference simulator. And ignore Points column, since the points are automatically calculated by the default grading algorithm, which is not used for our lab. Here are some hints and suggestions for working on Part A: • Do your initial debugging on the small traces, such as traces/dave.trace. • The reference simulator takes an optional -v argument that enables verbose output, displaying the hits, misses, and evictions that occur as a result of each memory access. You are not required to implement this feature in your csim.c code, but we strongly recommend that you do so. It will help you debug by allowing you to directly compare the behavior of your simulator with the reference simulator on the reference trace files. • We recommend that you use the getopt function to parse your command line arguments. You’ll need the following header files: #include #include #include See “man 3 getopt” for details. • Each data load (L) or store (S) operation can cause at most one cache miss. The data modify operation (M) is treated as a load followed by a store to the same address. Thus, an M operation can result in two cache hits, or a miss and a hit plus a possible eviction. • If you would like to use C0-style contracts from 15-122, you can include contracts.h, which we have provided in the handout directory for your convenience. 7 6.2 Working on Part B We have provided you with an autograding program, called test-trans.c, that tests the correctness and performance of each of the transpose functions that you have registered with the autograder. You can register up to 100 versions of the transpose function in your trans.c file. Each transpose version has the following form: /* Header comment */ char trans_simple_desc[] = “A simple transpose”; void trans_simple(int M, int N, int A[N][M], int B[M][N]) { /* your transpose code here */ } Register a particular transpose function with the autograder by making a call of the form: registerTransFunction(trans_simple, trans_simple_desc); in the registerFunctions routine in trans.c. At runtime, the autograder will evaluate each registered transpose function and print the results. Of course, one of the registered functions must be the transpose_submit function that you are submitting for credit: registerTransFunction(transpose_submit, transpose_submit_desc); See the default trans.c function for an example of how this works. The autograder takes the matrix size as input. It uses valgrind to generate a trace of each registered transpose function. It then evaluates each trace by running the reference simulator on a cache with parameters (s = 5, E = 1, b = 5). For example, to test your registered transpose functions on a 32 × 32 matrix, rebuild test-trans, and then run it with the appropriate values for M and N: linux> make linux> ./test-trans -M 32 -N 32 Step 1: Evaluating registered transpose funcs for correctness: func 0 (Transpose submission): correctness: 1 func 1 (Simple row-wise scan transpose): correctness: 1 func 2 (column-wise scan transpose): correctness: 1 func 3 (using a zig-zag access pattern): correctness: 1 Step 2: Generating memory traces for registered transpose funcs. Step 3: Evaluating performance of registered transpose funcs (s=5, E=1, b=5) func 0 (Transpose submission): hits:1766, misses:287, evictions:255 func 1 (Simple row-wise scan transpose): hits:870, misses:1183, evictions:1151 func 2 (column-wise scan transpose): hits:870, misses:1183, evictions:1151 8 func 3 (using a zig-zag access pattern): hits:1076, misses:977, evictions:945 Summary for official submission (func 0): correctness=1 misses=287 In this example, we have registered four different transpose functions in trans.c. The test-trans program tests each of the registered functions, displays the results for each, and extracts the results for the official submission. Here are some hints and suggestions for working on Part B. • The test-trans program saves the trace for function i in file trace.fi. 2 These trace files are invaluable debugging tools that can help you understand exactly where the hits and misses for each transpose function are coming from. To debug a particular function, simply run its trace through the reference simulator with the verbose option: linux> ./csim-ref -v -s 5 -E 1 -b 5 -t trace.f0 S 68312c,1 miss L 683140,8 miss L 683124,4 hit L 683120,4 hit L 603124,4 miss eviction S 6431a0,4 miss … • Since your transpose function is being evaluated on a direct-mapped cache, conflict misses are a potential problem. Think about the potential for conflict misses in your code, especially along the diagonal. Try to think of access patterns that will decrease the number of these conflict misses. • Blocking is a useful technique for reducing cache misses. See https://csapp.cs.cmu.edu/public/waside/waside-blocking.pdf for more information. 6.3 Putting it all Together For those who completed both Part A and B, we have provided you with a driver program, called ./driver.py, that performs a complete evaluation of your simulator and transpose code. This is the same program your instructor uses to evaluate your handins. The driver uses test-csim to evaluate your simulator, and it uses test-trans to evaluate your submitted transpose function on the three matrix sizes. Then it prints a summary of your results and the points you have earned. Again, the points will be adjusted for your actual grade. To run the driver, type: linux> ./driver.py 2Because valgrind introduces many stack accesses that have nothing to do with your code, we have filtered out all stack accesses from the trace. This is why we have banned local arrays and placed limits on the number of local variables. 9 7 Handing in Your Work Each time you type make in the cachelab-handout directory, the Makefile creates a tarball, called userid-handin.tar, that contains your current csim.c and trans.c files. If you do not work on the extra work, do not have to worry about trans.c. Trans.c with presenting the extra work in the header file will be graded. Upload the created tarball to the Blackboard. IMPORTANT: Do not create the handin tarball on a Windows or Mac machine, and do not handin files in any other archive format, such as .zip, .gzip, or .tgz files. 10
CSC 322 Lab Assignment 4: Writing Your Own Unix Shell
Introduction The purpose of this assignment is to become more familiar with the concepts of process control and signalling. You’ll do this by writing a simple Unix shell program that supports job control. Logistics You may work in a group of up to two in solving the problems for this assignment. For naming the file to submit, you should read carefully the ”handin” section in the last page. Hand Out Instructions Start by copying the file /home/jwlee/CSC322/shlab-handout.tar to the protected directory in which you plan to do your work. It is also uploaded in the Blackboard, so you may download it and move it into the Linux machine as well. Then do the following: • Type the command tar xvf shlab-handout.tar to expand the tarfile. • Type the command make to compile and link some test routines. • Type your team member names and Andrew IDs in the header comment at the top of tsh.c. Looking at the tsh.c (tiny shell) file, you will see that it contains a functional skeleton of a simple Unix shell. To help you get started, we have already implemented the less interesting functions. Your assignment is to complete the remaining empty functions listed below. As a sanity check for you, we’ve listed the approximate number of lines of code for each of these functions in our reference solution (which includes lots of comments). 1 • eval: Main routine that parses and interprets the command line. [70 lines] • builtin cmd: Recognizes and interprets the built-in commands: quit, fg, bg, and jobs. [25 lines] • do bgfg: Implements the bg and fg built-in commands. [50 lines] • waitfg: Waits for a foreground job to complete. [20 lines] • sigchld handler: Catches SIGCHILD signals. 80 lines] • sigint handler: Catches SIGINT (ctrl-c) signals. [15 lines] • sigtstp handler: Catches SIGTSTP (ctrl-z) signals. [15 lines] Each time you modify your tsh.c file, type make to recompile it. To run your shell, type tsh to the command line: unix> ./tsh tsh> [type commands to your shell here] General Overview of Unix Shells A shell is an interactive command-line interpreter that runs programs on behalf of the user. A shell repeatedly prints a prompt, waits for a command line on stdin, and then carries out some action, as directed by the contents of the command line. The command line is a sequence of ASCII text words delimited by whitespace. The first word in the command line is either the name of a built-in command or the pathname of an executable file. The remaining words are command-line arguments. If the first word is a built-in command, the shell immediately executes the command in the current process. Otherwise, the word is assumed to be the pathname of an executable program. In this case, the shell forks a child process, then loads and runs the program in the context of the child. The child processes created as a result of interpreting a single command line are known collectively as a job. In general, a job can consist of multiple child processes connected by Unix pipes. If the command line ends with an ampersand ”&”, then the job runs in the background, which means that the shell does not wait for the job to terminate before printing the prompt and awaiting the next command line. Otherwise, the job runs in the foreground, which means that the shell waits for the job to terminate before awaiting the next command line. Thus, at any point in time, at most one job can be running in the foreground. However, an arbitrary number of jobs can run in the background. For example, typing the command line tsh> jobs causes the shell to execute the built-in jobs command. Typing the command line tsh> /bin/ls -l -d 2 runs the ls program in the foreground. By convention, the shell ensures that when the program begins executing its main routine int main(int argc, char *argv[]) the argc and argv arguments have the following values: • argc == 3, • argv[0] == ‘‘/bin/ls’’, • argv[1]== ‘‘-l’’, • argv[2]== ‘‘-d’’. Alternatively, typing the command line tsh> /bin/ls -l -d & runs the ls program in the background. Unix shells support the notion of job control, which allows users to move jobs back and forth between background and foreground, and to change the process state (running, stopped, or terminated) of the processes in a job. Typing ctrl-c causes a SIGINT signal to be delivered to each process in the foreground job. The default action for SIGINT is to terminate the process. Similarly, typing ctrl-z causes a SIGTSTP signal to be delivered to each process in the foreground job. The default action for SIGTSTP is to place a process in the stopped state, where it remains until it is awakened by the receipt of a SIGCONT signal. Unix shells also provide various built-in commands that support job control. For example: • jobs: List the running and stopped background jobs. • bg : Change a stopped background job to a running background job. • fg : Change a stopped or running background job to a running in the foreground. • kill : Terminate a job. The tsh Specification Your tsh shell should have the following features: • The prompt should be the string “tsh> ”. • The command line typed by the user should consist of a name and zero or more arguments, all separated by one or more spaces. If name is a built-in command, then tsh should handle it immediately and wait for the next command line. Otherwise, tsh should assume that name is the path of an executable file, which it loads and runs in the context of an initial child process (In this context, the term job refers to this initial child process). 3 • tsh need not support pipes (|) or I/O redirection (< and >). • Typing ctrl-c (ctrl-z) should cause a SIGINT (SIGTSTP) signal to be sent to the current foreground job, as well as any descendents of that job (e.g., any child processes that it forked). If there is no foreground job, then the signal should have no effect. • If the command line ends with an ampersand &, then tsh should run the job in the background. Otherwise, it should run the job in the foreground. • Each job can be identified by either a process ID (PID) or a job ID (JID), which is a positive integer assigned by tsh. JIDs should be denoted on the command line by the prefix ’%’. For example, “%5” denotes JID 5, and “5” denotes PID 5. (We have provided you with all of the routines you need for manipulating the job list.) • tsh should support the following built-in commands: – The quit command terminates the shell. – The jobs command lists all background jobs. – The bg command restarts by sending it a SIGCONT signal, and then runs it in the background. The argument can be either a PID or a JID. – The fg command restarts by sending it a SIGCONT signal, and then runs it in the foreground. The argument can be either a PID or a JID. • tsh should reap all of its zombie children. If any job terminates because it receives a signal that it didn’t catch, then tsh should recognize this event and print a message with the job’s PID and a description of the offending signal. Checking Your Work We have provided some tools to help you check your work. Reference solution. The Linux executable tshref is the reference solution for the shell. Run this program to resolve any questions you have about how your shell should behave. Your shell should emit output that is identical to the reference solution (except for PIDs, of course, which change from run to run). Shell driver. The sdriver.pl program executes a shell as a child process, sends it commands and signals as directed by a trace file, and captures and displays the output from the shell. Use the -h argument to find out the usage of sdriver.pl: unix> ./sdriver.pl -h Usage: sdriver.pl [-hv] -t -s -a Options: -h Print this message -v Be more verbose -t Trace file -s Shell program to test 4 -a Shell arguments -g Generate output for autograder We have also provided 16 trace files (trace{01-16}.txt) that you will use in conjunction with the shell driver to test the correctness of your shell. The lower-numbered trace files do very simple tests, and the higher-numbered tests do more complicated tests. You can run the shell driver on your shell using trace file trace01.txt (for instance) by typing: unix> ./sdriver.pl -t trace01.txt -s ./tsh -a “-p” (the -a “-p” argument tells your shell not to emit a prompt), or unix> make test01 Similarly, to compare your result with the reference shell, you can run the trace driver on the reference shell by typing: unix> ./sdriver.pl -t trace01.txt -s ./tshref -a “-p” or unix> make rtest01 For your reference, tshref.out gives the output of the reference solution on all races. This might be more convenient for you than manually running the shell driver on all trace files. The neat thing about the trace files is that they generate the same output you would have gotten had you run your shell interactively (except for an initial comment that identifies the trace). For example: bass> make test15 ./sdriver.pl -t trace15.txt -s ./tsh -a “-p” # # trace15.txt – Putting it all together # tsh> ./bogus ./bogus: Command not found. tsh> ./myspin 10 Job (9721) terminated by signal 2 tsh> ./myspin 3 & [1] (9723) ./myspin 3 & tsh> ./myspin 4 & [2] (9725) ./myspin 4 & tsh> jobs [1] (9723) Running ./myspin 3 & [2] (9725) Running ./myspin 4 & tsh> fg %1 Job [1] (9723) stopped by signal 20 tsh> jobs 5 [1] (9723) Stopped ./myspin 3 & [2] (9725) Running ./myspin 4 & tsh> bg %3 %3: No such job tsh> bg %1 [1] (9723) ./myspin 3 & tsh> jobs [1] (9723) Running ./myspin 3 & [2] (9725) Running ./myspin 4 & tsh> fg %1 tsh> quit bass> Hints • Read every word of Chapter 8 (Exceptional Control Flow) in your textbook. • Use the trace files to guide the development of your shell. Starting with trace01.txt, make sure that your shell produces the identical output as the reference shell. Then move on to trace file trace02.txt, and so on. • The waitpid, kill, fork, execve, setpgid, and sigprocmask functions will come in very handy. The WUNTRACED and WNOHANG options to waitpid will also be useful. • When you implement your signal handlers, be sure to send SIGINT and SIGTSTP signals to the entire foreground process group, using ”-pid” instead of ”pid” in the argument to the kill function. The sdriver.pl program tests for this error. • One of the tricky parts of the assignment is deciding on the allocation of work between the waitfg and sigchld handler functions. We recommend the following approach: – In waitfg, use a busy loop around the sleep function. – In sigchld handler, use exactly one call to waitpid. While other solutions are possible, such as calling waitpid in both waitfg and sigchld handler, these can be very confusing. It is simpler to do all reaping in the handler. • In eval, the parent must use sigprocmask to block SIGCHLD signals before it forks the child, and then unblock these signals, again using sigprocmask after it adds the child to the job list by calling addjob. Since children inherit the blocked vectors of their parents, the child must be sure to then unblock SIGCHLD signals before it execs the new program. The parent needs to block the SIGCHLD signals in this way in order to avoid the race condition where the child is reaped by sigchld handler (and thus removed from the job list) before the parent calls addjob. 6 • Programs such as more, less, vi, and emacs do strange things with the terminal settings. Don’t run these programs from your shell. Stick with simple text-based programs such as /bin/ls, /bin/ps, and /bin/echo. • When you run your shell from the standard Unix shell, your shell is running in the foreground process group. If your shell then creates a child process, by default that child will also be a member of the foreground process group. Since typing ctrl-c sends a SIGINT to every process in the foreground group, typing ctrl-c will send a SIGINT to your shell, as well as to every process that your shell created, which obviously isn’t correct. Here is the workaround: After the fork, but before the execve, the child process should call setpgid(0, 0), which puts the child in a new process group whose group ID is identical to the child’s PID. This ensures that there will be only one process, your shell, in the foreground process group. When you type ctrl-c, the shell should catch the resulting SIGINT and then forward it to the appropriate foreground job (or more precisely, the process group that contains the foreground job). Evaluation Your score will be computed out of a maximum of 90 points based on the following distribution: 80 Correctness: 16 trace files at 5 points each. 10 Style points. We expect you to have good comments (5 pts) and to check the return value of EVERY system call (5 pts). Your solution shell will be tested for correctness on a Linux machine, using the same shell driver and trace files that were included in your lab directory. Your shell should produce identical output on these traces as the reference shell, with only two exceptions: • The PIDs can (and will) be different. • The output of the /bin/ps commands in trace11.txt, trace12.txt, and trace13.txt will be different from run to run. However, the running states of any mysplit processes in the output of the /bin/ps command should be identical. Hand In Instructions • Make sure you have included your names and IDs in the header comment of tsh.c. • Create a team name of the form: – “ID” where ID is your ID, if you are working alone, or – “ID1+ID2” where ID1 is the ID of the first team member and ID2 is the ID of the second team member. The order does not matter. 7 I need you to create your team names in this way so that I can autograde your assignments. • Only one of the team member will submit tsh.c file in the Blackboard. • No late submission will be accepted for this lab due to time limitation. Good luck! 8
CS322 Data Lab: Manipulating Bits
1 Introduction
The purpose of this assignment is to become more familiar with bit-level representations of integers and
floating point numbers. You’ll do this by solving a series of programming “puzzles.” Many of these puzzles
are quite artificial, but you’ll find yourself thinking much more about bits in working your way through
them.
2 Logistics
This is an individual project, but not a mandatory assignment. All credits (worth 10% of the final grade)
earned from this will be added to your final grade. All handins are electronic. Clarifications and corrections
will be posted on the course shell in the Blackboard.
3 Handout Instructions
Start by copying /home/jwlee/CSC322/datalab-handout.tarto the protected directory in which
you plan to do your work. It is also uploaded in the Blackboard, so you may download it and move it into
the Linux machine as well. Then give the command
unix> tar xvf datalab-handout.tar.
This will cause a number of files to be unpacked in the directory. The only file you will be modifying and
turning in is bits.c.
The bits.c file contains a skeleton for each of the 10 programming puzzles. Your assignment is to
complete each function skeleton using only straightline code for the integer puzzles (i.e., no loops or conditionals) and a limited number of C arithmetic and logical operators. Specifically, you are only allowed to
use the following eight operators:
1
! ˜ & ˆ | + << >>
A few of the functions further restrict this list. Also, you are not allowed to use any constants longer than 8
bits. See the comments in bits.c for detailed rules and a discussion of the desired coding style.
When you work on your lab, you may have compile errors on your current machine, because of difference
of the Linux version. In this case, you need to login to pi machine.
unix> ssh pi.cs.oswego.edu
If you are oncampus, simply try this:
unix> ssh pi
4 The Puzzles
This section describes the puzzles that you will be solving in bits.c.
4.1 Bit Manipulations
Table 1 describes a set of functions that manipulate and test sets of bits. The “Rating” field gives the
difficulty rating (the number of points) for the puzzle, and the “Max ops” field gives the maximum number
of operators you are allowed to use to implement each function. See the comments in bits.c for more
details on the desired behavior of the functions. You may also refer to the test functions in tests.c. These
are used as reference functions to express the correct behavior of your functions, although they don’t satisfy
the coding rules for your functions.
Name Description Rating Max Ops
bitAnd(x,y) x & y using only | and ˜ 1 8
getByte(x,n) Get byte n from x. 2 6
logicalShift(x,n) Shift right logical. 3 20
bitCount(x) Count the number of 1’s in x. 4 40
bang(x) Compute !n without using ! operator. 4 12
Table 1: Bit-Level Manipulation Functions.
4.2 Two’s Complement Arithmetic
Table 2 describes a set of functions that make use of the two’s complement representation of integers. Again,
refer to the comments in bits.c and the reference versions in tests.c for more information.
2
Name Description Rating Max Ops
tmin() Most negative two’s complement integer 1 4
fitsBits(x,n) Does x fit in n bits? 2 15
divpwr2(x,n) Compute x/2
n 2 15
negate(x) -x without negation 2 5
isPositive(x) x > 0? 3 8
isLessOrEqual(x,y) x <= y? 3 24
ilog2(x) Compute ⌊log2
(x)⌋ 4 90
Table 2: Arithmetic Functions
4.3 Floating-Point Operations
For this part of the assignment, you will implement some common single-precision floating-point operations. In this section, you are allowed to use standard control structures (conditionals, loops), and you may
use both int and unsigned data types, including arbitrary unsigned and integer constants. You may
not use any unions, structs, or arrays. Most significantly, you may not use any floating point data types,
operations, or constants. Instead, any floating-point operand will be passed to the function as having type
unsigned, and any returned floating-point value will be of type unsigned. Your code should perform
the bit manipulations that implement the specified floating point operations.
Table 3 describes a set of functions that operate on the bit-level representations of floating-point numbers.
Refer to the comments in bits.c and the reference versions in tests.c for more information.
Name Description Rating Max Ops
float_neg(uf) Compute -f 2 10
float_i2f(x) Compute (float) x 4 30
float_twice(uf) Computer 2*f 4 30
Table 3: Floating-Point Functions. Value f is the floating-point number having the same bit representation
as the unsigned integer uf.
Functions float_neg and float_twice must handle the full range of possible argument values, including not-a-number (NaN) and infinity. The IEEE standard does not specify precisely how to handle
NaN’s, and the IA32 behavior is a bit obscure. We will follow a convention that for any function returning
a NaN value, it will return the one with bit representation 0x7FC00000.
The included program fshow helps you understand the structure of floating point numbers. To compile
fshow, switch to the handout directory and type:
unix> make
You can use fshow to see what an arbitrary pattern represents as a floating-point number:
unix> ./fshow 2080374784
3
Floating point value 2.658455992e+36
Bit Representation 0x7c000000, sign = 0, exponent = f8, fraction = 000000
Normalized. 1.0000000000 X 2ˆ(121)
You can also give fshow hexadecimal and floating point values, and it will decipher their bit structure.
5 Evaluation
Your score will be computed out of a maximum of 42 points based on the following distribution:
22 Correctness points.
20 Performance points.
Correctness points. The 10 puzzles you must solve have been given a difficulty rating between 1 and 4, such
that their weighted sum totals to 22. We will evaluate your functions using the btest program, which is
described in the next section. You will get full credit for a puzzle if it passes all of the tests performed by
btest, and no credit otherwise.
Performance points. Our main concern at this point in the course is that you can get the right answer.
However, we want to instill in you a sense of keeping things as short and simple as you can. Furthermore,
some of the puzzles can be solved by brute force, but we want you to be more clever. Thus, for each function
we’ve established a maximum number of operators that you are allowed to use for each function. This limit
is very generous and is designed only to catch egregiously inefficient solutions. You will receive two points
for each correct function that satisfies the operator limit.
The points will be converted into 10% of the final grade. For instance, 42 points in the lab will be converted
to 10 extra points in the final grade; 28 points becomes about 6.7 (= 10 * 28/42) extra points.
Autograding your work
We have included some autograding tools in the handout directory — btest, dlc, and driver.pl —
to help you check the correctness of your work.
• btest: This program checks the functional correctness of the functions in bits.c. To build and
use it, type the following two commands:
unix> make
unix> ./btest
Notice that you must rebuild btest each time you modify your bits.c file.
You’ll find it helpful to work through the functions one at a time, testing each one as you go. You can
use the -f flag to instruct btest to test only a single function:
4
unix> ./btest -f bitAnd
You can feed it specific function arguments using the option flags -1, -2, and -3:
unix> ./btest -f bitAnd -1 7 -2 0xf
Check the file README for documentation on running the btest program.
• dlc: This is a modified version of an ANSI C compiler from the MIT CILK group that you can use
to check for compliance with the coding rules for each puzzle. The typical usage is:
unix> ./dlc bits.c
The program runs silently unless it detects a problem, such as an illegal operator, too many operators,
or non-straightline code in the integer puzzles. Running with the -e switch:
unix> ./dlc -e bits.c
causes dlc to print counts of the number of operators used by each function. Type ./dlc -help
for a list of command line options.
• driver.pl: This is a driver program that uses btest and dlc to compute the correctness and
performance points for your solution. It takes no arguments:
unix> ./driver.pl
Your instructors will use driver.pl to evaluate your solution.
6 Handin Instructions
• Make sure you have included your names and IDs in the header comment of bits.c.
• Name your file of the following form: your login ID-bits.c, for example jlee-bits.c.
• No late submission will be accepted.
7 Advice
• Don’t include the <stdio.h> header file in your bits.c file, as it confuses dlc and results in
some non-intuitive error messages. You will still be able to use printf in your bits.c file for
debugging without including the <stdio.h> header, although gcc will print a warning that you
can ignore.
5
• The dlc program enforces a stricter form of C declarations than is the case for C++ or that is enforced
by gcc. In particular, any declaration must appear in a block (what you enclose in curly braces) before
any statement that is not a declaration. For example, it will complain about the following code:
int foo(int x)
{
int a = x;
a *= 3; /* Statement that is not a declaration */
int b = a; /* ERROR: Declaration not allowed here */
}
Good luck!
6
