COMP 211-002 | Spring 2023 (Bakita)
These steps were last updated .
Tuesday, March 28th, 1:59 PM.
This assignment allows for free late submissions up until 1:59 PM on April 18th.
The collaboration policy on this assignment is also relaxed. You are welcome to discuss more specific components of the assignment with friends, rather than only abstract concepts. You are also allowed to use another’s keyboard to interact with tools and utilities, such as man, valgrind, or gdb. You should still never be copying code.
Catastrophe! In attempting to delete some falsified Tetris quicksaves, we accidentally deleted all of them! Even worse, in attempting to clean up some of vim’s autosaves (swap files), we accidentally deleted verify.c—the file containing our work-in-progress code for detecting falsified quicksaves! Fortunately, we were storing all our Tetris quicksaves on a flash drive, and so we quickly yanked it out as soon as we realized that the delete was happening. In an additional stroke of luck, we built our falsification detection program with gcc’s -save-temps option, so we still have the temporary object file (.o file) for verify.c—verify.o.
You have been given verify.o, and a disk image of the flash drive with partially-deleted saves. Your task is to:
verify.o, catching and recovering from any faults that occur.Part 1:
Part 2:
verify.o UsefulYou’ll need to understand how to:
man 7 signal, and man 2 signal or man sigaction)man sigsetjmp)You can find verify.o in /playpen/a4/verify.o on the course server, or you can download it from this link. You will also want an updated copy of tetris.h. You can find that at /playpen/a4/tetris.h, or you can download it from this link. Move copies of these files into wherever you will be working on your implementation.
Your program is to be called check, and will be implemented in the C file check.c. In order to link with verify.o, you need to tell gcc to use it as an input file. If you copied verify.o into your current directory, you could do this via gcc verify.o check.c -o check. The autograder will provide tetris.h and verify.o in the same directory as your code.
Our autograding infrastructure will compile your code as gcc verify.o check*.c -o check.
The verification function in verify.o which will sometimes segfault has the function signature:
void is_legitimate(TetrisGameState* game, int* is_legit);It will set the integer pointed to by is_legit to 1 if the game is likely legitimate (from a human player) and 0 otherwise. You will need to make sure to declare the function in check.c so that gcc can link to the implementation of is_legitimate() in verify.o.
Since we hadn’t quite finished verify.o when we deleted verify.c, is_legitimate() will sometimes segfault (specifically, if the save is legitimate) after completing all the verification operations. You need to set up a signal handler to catch the segfault (SIGSEGV) and resume execution of your program after it occurs. You can use sigsetjmp() to mark the location you want to jump to, and siglongjmp() to jump to it from your signal handler.
check is to take one argument, the path to a Tetris quicksave. Your program should terminate with a help message on stderr if it is run with less than or more than one argument.
The passed Tetris quicksave is of the same format as in prior assignments—just read it into a TetrisGameState as declared in tetris.h.
On stdout, check should print a single line containing the text “is legitimate” if the quicksave is legitimate and “is not legitimate” if the quicksave is not legitimate.
On stderr, you are encouraged to print error messages if any C library functions fail.
See the tetris quicksaves from Assignment 3 in /playpen/a3/ The saves in /playpen/a3/test_data/team_quicksaves and /playpen/a3/test_data/tetris_quicksaves are legitimate, everything else is randomly generated.
A legitimate quicksave:
jbakita@comp211-2sp23:~$ ./check /playpen/a3/test_cases/team_quicksaves/andrew/save2.bin
The quicksave /playpen/a3/test_cases/test_256/random_test_98.bin is legitimate.A faked quicksave:
jbakita@comp211-2sp23:~$ ./check /playpen/a3/test_cases/test_256/random_test_98.bin
The quicksave /playpen/a3/test_cases/test_256/random_test_98.bin is not legitimate.Note that in the above examples I chose to print a more complicated output message than the specification requires, but it contains the words “is legitimate” or “is not legitimate”, which is sufficient for the autograder.
Since is_legitimate() only crashes when a quicksave is legitimate, first implement the part of check.c which verifies arguments, loads the Tetris quicksave, calls is_legitimate(), and prints the result. Only test this with illigitimate quicksaves for now.
Next, add a signal handler for SIGSEGV and test that it is called when you try testing with a legitimate quicksave.
Finally, add in sigsetjmp() and siglongjmp(). When you call siglongjmp() from your signal handler, execution jumps to as though sigsetjmp() had just been called. The second argument you pass to siglongjmp() dictates what the return value of sigsetjmp() will be the second time. You will likely want to use this value to prevent your program from calling is_legitimate() a second time.
Read File System Forensics page 153, and read any other sections which have info you’d like.
I’ll try to work out the minimum set of sections which covers what you need to know soon. -Prof. Bakita
You can copy SanityCheckState() from tetris.c, and use this to verify if the data you loaded into a TetrisGameState is valid.
Your data-recovery program is to be called recover, and will be implemented in the C file recover.c. You may use multiple source files if you would like, the autograder will compile your code as gcc recover*.c verify.o -o recover.
We only deleted the user-generated (legitimate) quicksaves, and so only recover those. Use is_legitimate() from Part 1 to check if a recovered quicksave is legitimate.
The autograder will provide tetris.h and verify.o in the same directory as your code. See the description of Part 1 for information on where you can get the latest copies of these files.
recover is to take one argument, the path to a disk image. Your program should terminate with a help message on stderr if it is run with less than or more than one argument.
The passed disk image is a binary file containing every byte (in order) that was stored on our flash drive at the time it was pulled from the computer. The flash drive was formatted using the ext4 filesystem with a 4096 byte block size.
Each recovered quicksave should be stored in its own file, which your program will create with a generated name. All of these files should be stored in a subdirectory, also of your creation.
On stdout, recover should print the path at which you have stored each recovered quicksave.
Extra credit opportunity: Rather than simply generating names for the recovered files, recover the original filenames and paths. See Extra Credit Opportunities for details.
On stderr, you are encouraged to print error messages if any library functions fail. (The perror() function is very helpful for reading, interpreting, and printing error codes stored in errno. See man 3 errno and man perror.) You are also welcome to print progress messages to stderr, if so desired. (Note that you can use terminal escape sequences to move and overwrite the last line printed—this avoids filling the full screen with progress messages.)
The disk image you are to recover files from is /playpen/a4/a4_disk.img on the course server.
There are a total of 200356 valid quicksaves in this disk image, but only 100 are legitimate quicksaves.
jbakita@comp211-2sp23:~$ ./recover /playpen/a4/a4_disk.img
./output/recovered_1.bin
./output/recovered_2.bin
... [not all lines shown in this example]
./output/recovered_100.binWhere the 100 recovered legitimate quicksaves are in the directory output created by my program, and files recovered_1.bin through recovered_100.bin. Your files may be named differently, the autograder will just look at the file locations you print.
Start by making sure that you can open the passed disk image file and read blocks from it.
Then try casting the block pointer to a TetrisGameState*, pass it to your copy of SanityCheckState(). If that passes, try printing the block index of this valid quicksave for testing.
Next, add in a call to is_legitimate() (with appropriate signal handling as in check.c). If that also passes, you have a valid, legitimate quicksave, and should save it to a file of randomly generated name. (snprintf() may be helpful for generating the file name.) If this is the first file you are saving, also create a subdirectory to save the files in (see man 2 mkdir). Then print the path of each file you save, and that should be it!
The top-level folder structure before the delete was:
jbakita@comp211-2sp23:~$ tree -L 2 /media/a4_disk
/media/a4_disk
├── lost+found
├── real_saves
│ ├── answer_cases
│ └── test_cases
├── synthetic_saves
│ ├── answer_cases
│ └── test_cases
└── tetris.h
7 directories, 1 fileThe folder I accidentally deleted was real_saves/test_cases. Recover the names and paths of the files and folders in that directory, and use those for your output file names.
If you would like to see what else is on the disk, /playpen/a4/a4_disk.img is mounted read-only at /media/a4_disk on the course server.
In case it’s relevant, the disk was originally formatted as mkfs.ext4 -T small -m 0 <path to block device for disk>, with the part in <> substituted for the disk location.
I have yet to find an excellent document laying out how ext4 works, but it merely adds a few features to ext2 and ext3. Pgs. 738-766 in Understanding the Linux Kernel (3rd Ed) thoroughly lay out how ext2 works, which should be enough.
Also see File System Forensics, which has sections which should much more clearly show you how to recover the data.
While poking around the disk, you may want to also check for any other recently deleted files…
You will submit via Gradescope. We will not be posting an autograder for this assignment, but will curve the results from our internal autograder when computing your final score.
Use submit_a4 on the course server to submit your implementations of check.c and recover.c. This program will also check that your code successfully compiles before uploading it.
Please remember to include the honor code pledge on the first line of both check.c and recover.c, following the same format as with prior assignments.
Note that when you test your code in valgrind for this assignment, it will complain about an invalid read of size 4 in is_legitimate()—this is expected, and you should ignore it.