YmVM3c9U

1---------------------------------------------------------------------------------------------------------------------------
2Assignment 1 - Hijacking System Calls and Monitoring Processes
3Due: Oct 2, at 10:00pm
4
5Overview
6In this assignment, you will achieve the goal of hijacking (intercepting) system calls by writing and installing a very basic kernel module to the Linux kernel.
7
8Here is what "hijacking (intercepting) a system call" means. You will implement a new system call named my_syscall, which will allow you to send commands from userspace, to intercept another pre-existing system call (like read, write, open, etc.). After a system call is intercepted, the intercepted system call would log a message first before continuing performing what it was supposed to do.
9
10For example, if we call my_syscall with command REQUEST_SYSCALL_INTERCEPT and target system call number __NR_mkdir (which is the macro representing the system call mkdir) as parameters, then the mkdir system call would be intercepted; then, when another process calls mkdir, mkdir would log some message (e.g., "muhahaha") first, then perform what it was supposed to do (i.e., make a directory).
11
12But wait, that's not the whole story yet. Actually we don't want mkdir to log a message whenever any process calls it. Instead, we only want mkdir to log a message when a certain set of processes (PIDs) are calling mkdir. In other words, we want to monitor a set of PIDs for the system call mkdir. Therefore, you will need to keep track, for each intercepted system call, of the list of monitored PIDs. Our new system call will support two additional commands to add/remove PIDs to/from the list.
13
14When we want to stop hijacking a system call (let's say mkdir but it can be any of the previously hijacked system calls), we can invoke the interceptor (my_syscall), with a REQUEST_SYSCALL_RELEASE command as an argument and the system call number that we want to release. This will stop intercepting the target system call mkdir, and the behaviour of mkdir should go back to normal like nothing happened.
15
16Checklist
17First of all, DO NOT MANUALLY CREATE A NEW DIRECTORY 'A1' IN YOUR REPOSITORY! An empty directory called 'A1' should be created for you automatically when you log into MarkUs and go on your A1 link. Next, you should see the newly-created 'A1' directory in your repository. Please make sure in advance that you can access your A1 directory, to avoid last-minute surprises.
18
19Here is a checklist that should help get you started, and to make sure that you won't forget the important things:
20
21Find your GIT repository on MarkUs (see "Submission"), and make sure you can access it. The starter code files can be found on cslinux, under /student/cslec/369/assignments/A1-starter-code/starter_code.tgz
22Test that you have access to the VM in the labs.
23Download the disk image for the virtual machine (gzipped) on your own machine.
24On the host computer (e.g., your laptop or the lab machine), use a virtual machine software (VirtualBox or VMware) to create a virtual machine using the disk image provided.
25Read and understand the existing code in the starter code. This is an important step of this assignment, and you should not start writing your own code before you have a good understanding of the starter code.
26Implement the new kernel module by completing source file "interceptor.c". Sections that need to be completed are marked with the TODO tag). Do NOT modify the header file "interceptor.h".
27Make sure to test as you go. You should first make sure that the commands to intercept and de-intercept work well, before attempting to implement the monitoring commands.
28Testing and debugging (must be done in the virtual machine):
29Clone your code inside the virtual machine.
30Type make to compile your kernel module. Make sure there is no error or warning.
31Implement the intercept and release commands.
32Compile the test_intercept.c program using gcc.
33Test your code using sudo ./test_intercept, and make sure that all tests pass.
34Implement the monitoring/un-monitoring commands.
35Compile the test_full.c program using gcc.
36Test your code using sudo ./test_full, and make sure that all tests pass.
37Submit your code on time. See "Submission" for more details.
38Congratulations! You now have some good hands-on experience with the Linux kernel and system calls! You can now be proud of having programmed a Linux kernel module. You know what else are commonly implemented as kernel modules? Device drivers! Although they are more complex, you now technically have the basis to try to write one. Isn't that cool?
39Goal
40The goal of this assignment is to learn more about system calls and to use synchronization mechanisms. For this assignment you will be writing a very basic kernel module that intercepts system calls and monitors processes on demand.
41
42Requirements
43In order to be able to issue our own hijacking commands from userspace, we need a new system call that takes as parameters the command, the system call number (to be intercepted), and (for monitoring) a pid.
44
45Instead of adding a new system call, which can be tricky, our new system call my_syscall will be installed in place of an unused system call in the system call table. We will connect my_syscall to the entry number MY_CUSTOM_SYSCALL (in effect, entry 0 which is mostly unused). The new system call my_syscall, defined as follows:
46
47int my_syscall(int cmd, int syscall, int pid); 
48
49will serve as an interceptor and will receive the following commands from userspace:
50
51REQUEST_SYSCALL_INTERCEPT: intercept the system call syscall
52REQUEST_SYSCALL_RELEASE: de-intercept the system call syscall
53REQUEST_START_MONITORING: start monitoring process pid for system call syscall, i.e., add pid to the syscall's list of monitored PIDs. A special case is that if pid is 0 then all processes are monitored for syscall, but only root has the permission to issue this command (see the comments for my_syscall in the starter code for more details).
54REQUEST_STOP_MONITORING: stop monitoring process pid for system call syscall, i.e., remove pid from the syscall's list of monitored PIDs.
55Kernel module operation
56
57Your kernel module must, upon initialization, replace the system call table entry for the MY_CUSTOM_SYSCALL number, with the my_syscall function. When the module is released, it must restore this system call to its original routine.
58
59As a result, when your kernel module is loaded, any subsequent invocations of the system call number MY_CUSTOM_SYSCALL from userspace, will issue four types of commands, to intercept or release a given system call, and to start and stop monitoring a pid for a specific syscall. You must implement the my_syscall function accordingly.
60
611. REQUEST_SYSCALL_INTERCEPT and REQUEST_SYSCALL_RELEASE.
62When an intercept command is issued, the corresponding entry in the system call table will be replaced with a generic interceptor function (discussed later) and the original system call will be saved. When a REQUEST_SYSCALL_RELEASE command is issued, the original saved system call is restored in the system call table in its corresponding position.
63
642. REQUEST_START_MONITORING and REQUEST_STOP_MONITORING
65Monitoring a process consists of the module logging into userspace some information about the process and the system call: the system call number, the parameters of the system call, and the pid of the process.
66
67When a REQUEST_START_MONITORING command comes through our custom system call, the kernel module must record internally that the pid passed as a parameter should be monitored for the syscall number (passed as a parameter as well). The monitoring can be done for a specific pid, or for all pids (in which case the pid parameter for my_syscall will be 0).
68
69Ok, but I still don't understand, what does it mean to monitor a pid? And what does the generic interceptor function do?
70
71Let's start with the monitoring. We have established that once the user issues a monitoring command, the kernel module records internally that pid should be monitored whenever it issues system call number syscall (it will be placed in a monitored list - see details in starter code).
72
73We have also established that the generic interceptor function is what each intercepted system call will reach. In other words, whenever we reach the generic interceptor, we know that the system call is being intercepted (otherwise we would not reach this). If the pid of the process issuing the system call is being monitored, that means that we must print some information to a log. The log message will simply contain the system call number and the arguments, as well as the calling process's pid. 
74We have provided you in the starter code with a log_message macro, which takes care of sending a message to the system log. You can check the log using the dmesg command.
75
76As you might expect, regardless if a pid is monitored or not, the generic interceptor must eventually (once it's done logging, if applicable), call the original system call to allow normal operation of all processes in the system.
77
78Alright, but what if a process exits before the user can issue a system call to stop monitoring it? 
79Good question! When your kernel module initializes, you should also hijack the exit_group system call (with number __NR_exit_group), by replacing it in the system call table with your own custom function my_exit_group. Of course, make sure to save the original exit_group function, and to restore it when your kernel module is unloaded. 
80Implementing the my_exit_group function should be simple: all you have to do is to remove the pid of the exiting process from all kernel module's internal bookkeeping on monitored processes, then call the original exit_group function.
81
82Error Conditions
83You must make sure to check any possible misuse of the commands. In case of a misuse, you should return a proper error code (e.g., -EINVAL, -EPERM, google "Linux error code" for more information on error codes). Here is a list of things you should keep in mind:
84
85For each of the commands, check that the arguments are valid (-EINVAL):
86The syscall number must be valid: not negative, not > NR_syscalls-1 (the last syscall number in the table), and not MY_CUSTOM_SYSCALL itself (for obvious reasons).
87The pid must be valid for the monitoring commands. It cannot be a negative integer, and it must be an existing pid (except for the case when it's 0, indicating that we want to start/stop monitoring for all pids).
88If a pid belongs to a valid process, then the following call is not NULL:
89    pid_task(find_vpid(pid), PIDTYPE_PID)
90Check that the called has the right permissions (-EPERM):
91For the first two commands, we must be root (see the current_uid() macro), to be able to intercept or release system calls.
92For the last two commands, the following logic applies:
93Is the calling process root? if so, all is good, no doubts about permissions.
94If it is not, then check if the pid requested is owned by the calling process
95Also, if pid is 0 and the calling process is not root, then access is denied (monitoring all pids should only be allowed for a superuser, for obvious reasons).
96Check for correct context of commands (-EINVAL):
97Cannot de-intercept a system call that has not been intercepted yet.
98Cannot stop monitoring for a pid that is not being monitored, or if the system call has not been intercepted yet. If the system call has not been intercepted yet, a command to start monitoring a pid for that syscall is also invalid.
99Check for -EBUSY conditions:
100If intercepting a system call that is already intercepted.
101If monitoring a pid that is already being monitored.
102If a pid cannot be added to a monitored list, due to no memory being available, an -ENOMEM error code should be returned. The starter code provides a set of functions that enable operation with kernel lists.
103What if a stop monitoring request comes in for a specific PID (let's call it P), for a syscall that monitors all PIDs? Is that an error or should we treat this as a special case? For this assignment, you can assume that this is an error and simply return -EINVAL. 
104BONUS (5% applicable to marks lost elsewhere on this assignment): Instead of ignoring this case and returning -EINVAL, you can optionally treat this as a special case. If we already monitor all PIDs for a syscall, then you might have to think of a solution to make sure that you can keep monitoring all the PIDs in the system, except for P. Please keep in mind that some processes that will be monitored may not have even started their execution. Also, please keep in mind that we might have other stop monitoring requests for the same syscall, in which case, you might have to think of how to use the list of monitored pids in a smart way. One possibility is turning the list of monitored pids into a "blacklist" (keeping track of the pids that are not being monitored).
105
106General information
107You must use the starter code provided, which gives you detailed instructions on what you need to implement. Please make sure to implement all the parts indicated using detailed TODO comments. Please make sure to first attend the tutorial which will help you write a simple kernel module and show you how to use printk statements for debugging. See the tutorial notes as well.
108Your assignment will be tested on a virtual machine, since the work you will be doing can potentially crash the kernel. You can access this virtual machine from your account, or you can download the provided virtual machine disk image and install it on your personal computer through a virtualization solution (for example, free software include VMWare Player, VirtualBox, Qemu-kvm, etc.)
109We strongly recommend that you do NOT use the virtual machine for development, but rather only for testing and debugging. While working on this assignment, it is quite likely you will crash the kernel and although you can kill and restart the VM, there will be no guarantee that your code will still be there (no guarantee you get safe snapshots). To prevent your hard work from possible data corruption, either git clone inside the VM and use your repository to commit+push your code periodically from within the VM, or make sure to at least back up your code periodically (e.g., by scp-ing it back to your host machine or to your lab account).
110Accessing the Virtual Machine in the labs
111Guidelines for accessing the VM on the lab machines will be provided during the tutorial. Please make sure to attend the tutorial and follow the TA's instructions carefully.
112Setup VM On Your Own Machine
113Note: Your assignment has to ultimately be tested on a lab machine. However, if you wish to develop it and test it first on your own machine, using virtualization software (*do not test your assignment directly on your computer even if you're using Linux, just use the VM!*), then we will provide some basic instructions on how to do so.
114
115Since VirtualBox is one of the most portable (as well as free) virtualization software, here and here are some basic guidelines on how to install the VM image in VirtualBox on your computer (of course, many tutorials can be found online as well, so feel free to consult other sources if something does not work well for your own machine).
116
117Additionally you could set up VMWare Player on your machine, in a similar fashion and use the provided disk image (the vmdk file). Similar instructions can be found here.
118
119Implementation details
120Since the number of system calls is rather small (~300), and for performance reasons, you must maintain the system call information in an array. Each array element will contain information, as described in the mytable struct: 
121typedef struct {
122    asmlinkage long (*f)(struct pt_regs);
123    int intercepted;
124    int monitored;
125    int listcount;
126    struct list_head my_list;
127} mytable; 
128You must use a linked list for storing information about the monitored processes; using an array of fixed size is entirely inadequate (because the search time will be the same as a linked list, the implementation complexity will be the same, but the size of the array will limit the number of entries).
129The system call table is exported by the void* sys_call_table[NR_syscalls], present in one of the kernel source files from the VM image. If you wish to configure your own kernel image and re-compile it, you can modify the source code by adding the following two lines in the /usr/src/linux-source-2.6.32/arch/x86/kernel/i386_ksyms_32.c file:
130    extern void* sys_call_table[];
131    EXPORT_SYMBOL(sys_call_table);
132then recompile the kernel. Again, our virtual machine image already has these changes in place. Keep in mind though that later kernels have changed quite a bit so it may not be as easy to export the system call table and use it from the interceptor module.
133Since the 2.6 kernel (and later ones) is preemptive, you must protect access to shared data. You will be using spinlocks for this purpose. The use of spinlocks is fairly simple and you have been shown some examples in one of the tutorials.
134You must use the system call number 0 for MY_CUSTOM_SYSCALL. Do not attempt to use a different existing system call number, as that may result in the kernel misbehaving (to say the least). Remember that lots of services running in your OS make use of these system calls.
135Logging the system call will be done using the log_message macro, defined in the interceptor.h header file.
136For testing, you can use the provided tester programs. After you compile a test program (the provided Makefile only compiles your interceptor module, not any tester!), remember to run the tester using sudo privileges in the VM. 
137To facilitate your testing, you should first try to implement the commands to intercept and release system calls. When you are ready to test these, use the test_intercept.c tester.
138Once all tests pass, you can proceed to implementing the monitoring commands. To test all commands (both related to intercepting and to monitoring), you can use the test_full.c tester.
139Testing your code
140To help you test your code, we have provided two testers, which you will also find in your repositories. To encourage you to test as you go, we are providing you with two testers:
141test_intercept.c - tests if your intercept and de-intercept commands work correctly. You should first implement these and make sure the tester passes all cases.
142test_full.c - tests if all commands (including intercept, release, and both monitoring commands) work properly. This is a superset of the first tester, and you should only use once your code passes the first tester.
143The tester loads your module and tests some basic functionality. It is by no means a comprehensive tool to ensure your code works for every corner case. To ensure that your code works correctly in all possible scenarios, you should add more test cases by modifying the testers (see code comments in main). However, please do not submit your own tester files, because they will not be marked. The tester will also not catch synchronization bugs, except for blatant deadlocks. It is your responsibility to ensure that your code is not likely to run into synchonization problems. Finally, when testing, you will likely see the tester crash on various tests, due to bugs in your module. During your debugging, please feel free to go in each tester, and comment out some of the system calls being tested, if you wish to debug each test case in isolation.
144Other Useful Tips
145Again, run tests ONLY in the virtual machine, NOT native computer, unless you hate your laptop.
146Once more, we strongly recommend that you do NOT use the virtual machine for development, but rather only for testing and debugging. Since it is quite likely you will crash the kernel and there will be no guarantee that your code will be intact. To prevent your hard work from possible data corruption, either git clone inside the VM and commit+push your code periodically, or make sure to at least back up your code periodically.
147Reading and understanding code is as important as (if not more important than) writing code.
148The comments in the starter code have a lot of information, make sure to read them carefully.
149Remember that when we de-intercept a syscall, the original system call must be restored in the system call table. For that you must properly store the original system call before replacing it.
150For debugging, learn how to use the printk function, which prints messages to kernel log. See tutorial notes as well.
151Use dmesg command to check the kernel log.
152Submission
153You will submit the interceptor.c file that contains your implementation, along with the files required to build your program (including the provided interceptor.h, Makefile, and Kbuild, which you should not modify). Do not submit executables, or tester files!
154
155For those working in pairs, please make sure to commit to the group repository. If you previously had trouble forming groups on A0, please contact me in advance. Do not leave this to the last minute, technical trouble with your repository will not get you an extension!
156
157Additionally, you must submit an INFO.txt file, which contains as the first 2 lines the following:
158
159your name(s)
160your UtorID(s)
161If you want us to grade an earlier revision of your assignment for whatever reason (for example, for saving some grace tokens if you had a stable submission before the deadline, tried to add new functionality after the deadline but broke your submission irreparably), then you may specify the git hash for the earlier revision you want marked. 
162As a general rule, by default we will always take the last revision before the deadline (or last one after the deadline, up to your remaining unused grace tokens), so you should not be including a line with the git commit hash, except in the exceptional circumstances where it makes sense. So in general, please avoid using this option and just make sure that the last revision (either before the deadline if you submit on time, or up to a subset of your remaining grace tokens if you submit late) is the one you want graded.
163Aside from this, please feel free to describe in a separate paragraph(s), any problems you've encountered, what isn't fully implemented (or doesn't work fully), any special design decisions you've taken (as long as they conform to the assignment specs), etc.
164
165Finally, whether you work individually or in pairs with a partner, you must submit a plagiarism.txt file in your repo, with the following statement:
166"All members of this group reviewed all the code being submitted and have a good understanding of it. All members of this group declare that no code other than their own has been submitted. We both acknowledge that not understanding our own work will result in a zero on this assignment, and that if the code is detected to be plagiarised, severe academic penalties will be applied when the case is brought forward to the Dean."
167
168Make sure your code compiles without any errors or warnings.
169Code that does not compile will receive zero marks!
170
171Marking scheme
172We will be marking based on correctness (90%), and coding style (10%). Make sure to write legible code, properly indented, and to include comments where appropriate (excessive comments are just as bad as not providing enough comments). Code structure and clarity will be marked strictly!
173Once again: code that does not compile will receive 0 marks! More details on the marking scheme:
174
175Correctness - init/exit module: 10% (correct functionality of init/exit_module)
176Correctness - exit_group: 5%
177Correctness - interceptor: 5%
178Correctness - my_syscall: 60% (each of the four operations are worth 15 marks: 8 for functionality, 7 for checking validity of arguments, special conditions, etc.)
179Synchronization: 10% (Correct use of synchronization primitives. Even if code does not deadlock or cause race conditions during testing, if the code looks like it has the potential to do so, marks will be deducted accordingly.)
180Code style and organization: 10% - code design/organization (modularity, code readability, reasonable variable names, avoid code duplication, appropriate comments where necessary, proper indentation and spacing, etc.)
181In order to be able to run tests on your work, we must trust that your submission follows a set of requirements (please be careful about these deductions!):
182Code does not compile -100% for *any* mistake, for example: missing source file necessary for building your code (including Kbuild, Makefile, provided source files, etc.), typos, any compilation error, etc.
183No plagiarism.txt file: -100% (we will assume that your code is plagiarised, if this file is missing)
184Missing or incorrect INFO.txt: -10%
185Warnings: -10%
186Extra output (other than the function that logs messages): -20%
187Code placed in subdirectories: -20% (only place your code directly under your A1 directory)
188To check that your assignment submission is complete, please reserve time in advance to do the following:
189
190create an empty temporary directory in your account (not in a subdirectory of your repo!)
191check out a copy of your repository for this assignment
192verify that all the required files are included (double-check the submission instructions above)
193ensure that you are able to build your code without any errors or warnings (This is an excellent way to verify that the right source files have been committed to the repo.)
194run a few tests to ensure that your code behaves as you expect, in case you made last minute changes.
195make sure to clean up any unnecessary files (e.g., executables), and make sure your files are directly under the A1/ directory (no subdirectories like "starter_code" or anything like that!)
196congratulate yourself and enjoy a well-earned break, knowing that your strategy and hard work will pay off!
197Keep in mind again: Code that does not compile, for whatever reason, will receive zero marks!
198---------------------------------------------------------------------------------------------------------------------------
199Assignment 2 - Synchronization
200Due: Oct 23, at 10:00pm
201
202It was such a relief to program in user mode for a change. 
203-- Linus Torvalds, to Git mailing list
204Overview
205For this assignment, we're going back to the realm of user mode programming. In this assignment, you will work with synchronization primitives to implement a traffic monitoring and guidance system.
206
207Autonomous (Self-driving) cars are increasingly becoming more reliable, as development of smart technologies help better guide the vehicle through its environment safely. Autonomous cars depend on several sensors and complex logic to coordinate with other vehicles in a safe manner. At an intersection for example, cars must have a policy to coordinate crossing the intersection in order to avoid crashes and to ensure that everyone goes through the intersection eventually.
208
209Your job is to implement a traffic system that coordinates cars going through an intersection, by enforcing ordering between car arrivals in the same direction, avoiding potential crashes, and avoiding deadlocks.
210
211Details
212Consider the structure of the intersection, as shown in the figure below. There are four entrances/exits to the intersection, each corresponding to a cardinal direction: North (N), South (S), East (E) and West (W). Each entrance into the intersection is referred to as a lane and is represented by a fixed sized buffer. Exits from the intersection are represented by a simple linked list for each exit direction. The starter code can be found on cslinux, under: /student/cslec/369/assignments/A2-starter-code/starter_code.tgz 
213The intersection itself is broken into quadrants, each represented by a lock.
214
215Cars are represented by a 3-tuple (id, in_dir, out_dir) where id is a car's unique id, in_dir is the direction from which the car enters the intersection and out_dir is the direction the car leaves the intersection.
216
217The traffic system enforces the policy for cars to pass through the intersection safely and in an orderly fashion. You will implement the traffic system using a monitor.
218
219Policies:
2201. Once a car approaches an intersection, it is placed in the corresponding lane. The car can only cross the intersection when all other cars already in the lane have crossed.
221
2222. Once a car is the first in the lane, it can begin to cross the intersection. Before the car can enter the intersection it must guarantee that it has a completely clear path to its destination.
223
224Implementation
225Your task is to implement the methods for the monitor, given to you in the starter code. The monitor has 3 methods that you must fill:
226
227/* Initialize all the monitor attributes */
228void init_intersection();
229
230/* Car approaches the intersection, must be added to the lane */
231void *car_arrive(void *arg);
232
233/* Car enters the intersection, must check for clear path */
234void *car_cross(void *arg);
235Additionally, the monitor contains the helper function below (which you must also fill in), and which will assist in making decisions about how cars cross the intersection.
236
237/* given two directions returns the path a car would take through the intersection */
238int *compute_path(enum direction in_dir, enum direction out_dir);
239There are two threads per cardinal direction, one which executes
240
241car_arrive()
242and another which executes
243car_cross()
244You must use the starter code provided, which gives you detailed instructions on what you need to implement. Please make sure to implement all the parts indicated using detailed TODO comments.
245
246The starter code contains a program (traffic.c) that serves as the entry point for the assignment. The traffic program takes the configuration of the approaching cars from a file, which contains a series of rows each corresponding to a car. Each row is formatted as follows:
247
248id, in_dir, out_dir
249
250ex.
2511 0 2
2522 1 2
2533 1 3
2544 0 1
255For additional clarification check the definitions and comments in traffic.h, as well as the provided sample input file (schedule.txt).
256You must ensure that there are no memory leaks in your code. DO NOT free the out_cars array because we will be inspecting its contents in the autotester, to verify some integrity constraints regarding the correctness of your implementation.
257
258Testing
259Testing programs that involve synchronization primitives is difficult. Data races, deadlocks, and other synchronization problems may occur during one run but not the next, which makes detection of synchronization-related bugs a tedious (and frustrating) task. As computer scientists, solving frustrating bugs is your bread and butter though, right? Well, it doesn't have to be. Luckily, many share the same frustration of having to deal with complicated synchronization bugs for days at a time. As a result, automated tools for detecting possible synchronization problems are being developed and perfected, in order to assist programmers with developing parallel code.
260
261One such tool is valgrind, which you may have used before in checking other problems in your code (e.g., memory leaks). Valgrind's instrumentation framework contains a set of tools which performs various debugging, profiling, and other tasks to help developers improve their code.
262
263One of valgrind's tools is called helgrind, a synchronization error checker (for the lack of a better word), which is tasked with helping developers identify synchronization bugs in programs that use POSIX pthreads primitives. You are encouraged to read through the Documentation for helgrind, in order to understand the kinds of synchronization errors it can detect and how each of these are reported.
264
265The simplest example on how to use helgrind is as follows:
266
267valgrind --tool=helgrind ./traffic schedule.txt
268However, before you start testing your assignment code, you might want to consider trying it out on much simpler code, like the samples provided in lecture. For example, try testing helgrind on the producer-consumer solution with condition variables: prodcons As you can see, no synchronization errors are reported, and you should get a report that ends similarly to the one below:
269
270==9395== 
271==9395== For counts of detected and suppressed errors, rerun with: -v
272==9395== Use --history-level=approx or =none to gain increased speed, at
273==9395== the cost of reduced accuracy of conflicting-access information
274==9395== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 94 from 25)
275For the most part, you can ignore most suppressed errors, but you might find it useful to enable the verbose flag (-v) to enable more detailed reports. Please consider reading the documentation for more information on this.
276Although the documentation examples should be reasonably easy to follow, in order to practice your understanding of what is being reported for various synchronization bugs, you might want to consider trying to intentionally introduce various synchronization errors in the producer-consumer code and understanding the resulting helgrind report. For example, comment out in the producer function the line which acquires the region_mutex. What does the helgrind report tell you?
277
278Warning: do not rely solely on this tool for writing correct code! Assistance from tools like helgrind should not be a substitute for carefully thinking through what your code is doing and what problems may arise. Although in this assignment the helgrind tool is probably sufficient for detecting most mistakes you could run into, it is not a "catch-all" solution for synchronization bugs and it is constantly being enhanced with more features. Once again, for the types of errors detected by helgrind, please read the Documentation carefully.
279
280Basic tester
281We are also providing in the starter code, a "self-tester" binary, which checks some basic properties of your code. The tester will check that all cars from a given lane enter the intersection in the right order (cars don't skip over others), by inspecting your output (see the comments from the starter code on what output format is expected). The tester will also check that all cars make it out of the intersection in the right quadrant, according to their out_dir. This is why you should not free the out_cars, and you should not modify the traffic code.
282
283An example of how to run the student tester: $ ./student_tester schedule_file1 schedule_file2 etc.. The result of your run will be placed in a file called results.txt. If there are no errors in the result file, then your code passes some basic sanity checks. You should use more complex schedules than the one we gave you, and carefully-tailored schedules that capture various corner cases.
284
285Once again, this tester is just a basic checker and should not preclude you from using valgrind to track down concurrency bugs, as well as thoroughly testing your code!
286
287Submission
288First of all, DO NOT MANUALLY CREATE A NEW DIRECTORY 'A2' IN YOUR REPOSITORY! An empty directory called 'A2' should be created for you automatically when you log into MarkUs and go on your A2 link. Next, you should see the newly-created 'A2' directory in your repository. Please make sure in advance that you can access your A2 directory, to avoid last-minute surprises.
289
290You will submit the cars.c file that contains your implementation, along with the files required to build your program (including the provided traffic.h, Makefile, and traffic.c, which you should not modify). Do not submit executables or object files!
291
292Additionally, you must submit an INFO.txt file, which contains as the first 2 lines the following:
293
294your name(s)
295your UtorID(s)
296If you want us to grade an earlier revision of your assignment for whatever reason (for example, for saving some grace tokens if you had a stable submission before the deadline, tried to add new functionality after the deadline but broke your submission irreparably), then you may specify the git hash for the earlier revision you want marked. 
297As a general rule, by default we will always take the last revision before the deadline (or last one after the deadline, up to your remaining unused grace tokens), so you should not be including a line with the git commit hash, except in the exceptional circumstances where it makes sense. So in general, please avoid using this option and just make sure that the last revision (either before the deadline if you submit on time, or up to a subset of your remaining grace tokens if you submit late) is the one you want graded.
298Next, you must add in the same INFO.txt file
299
300A paragraph titled "Discussion", where you discuss whether starvation can happen when using this monitor. To make the discussion more interesting, you must assume that cars keep arriving at the intersection, rather than the number of cars being finite (as given in the schedule input file). Describe your rationale.
301Aside from this, please feel free to describe in a separate paragraph(s), any problems you've encountered, what isn't fully implemented (or doesn't work fully), any special design decisions you've taken (as long as they conform to the assignment specs), etc.
302Finally, whether you work individually or in pairs with a partner, you must submit a plagiarism.txt file, with the following statement:
303"All members of this group reviewed all the code being submitted and have a good understanding of it. All members of this group declare that no code other than their own has been submitted. We both acknowledge that not understanding our own work will result in a zero on this assignment, and that if the code is detected to be plagiarised, severe academic penalties will be applied when the case is brought forward to the Dean."
304
305A missing INFO.txt file will result in a 10% deduction (on top of an inherent penalty if we do not end up grading the revision you expect). Any missing code files or Makefile will result in a 0 on this assignment! Please reserve enough time before the deadline to ensure correct submission of your files. No remark requests will be addressed due to an incomplete or incorrect submission!
306
307Again, make sure your code compiles without any errors or warnings.
308Code that does not compile will receive zero marks!
309
310Marking scheme
311We will be marking based on correctness (90%), and coding style (10%). Make sure to write legible code, properly indented, and to include comments where appropriate (excessive comments are just as bad as not providing enough comments). Code structure and clarity will be marked strictly!
312Once again: code that does not compile will receive 0 marks! More details on the marking scheme:
313
314init_intersection: 10% (initializing the intersection structures correctly and completely.)
315car_arrive: 30% (correctly and *efficiently* implementing car_arrive - no big locks, cars arriving in waves, etc.)
316car_cross + compute_path: 40% (correctly and *efficiently* implementing car_cross)
317Starvation discussion: 10% (correct discussion and supporting your argument clearly, in detail)
318Code style and organization: 10% - code design/organization (modularity, code readability, reasonable variable names, avoid code duplication, appropriate comments where necessary, proper indentation and spacing, etc.)
319In order to be able to run tests on your work, we must trust that your submission follows a set of requirements (please be careful about these deductions!):
320Code does not compile -100% for *any* mistake, for example: missing source file necessary for building your code (including Makefile, provided source files, etc.), typos, any compilation error, etc.
321No plagiarism.txt file: -100% (we will assume that your code is plagiarised, if this file is missing)
322Missing or incorrect INFO.txt: -10%
323Warnings: -10%
324Extra output (other than the printf statement indicated in the comments): -20%
325Code placed in subdirectories: -20% (only place your code directly under your A2 directory)
326---------------------------------------------------------------------------------------------------------------------------
327Assignment 3 - Page Tables and Replacement Algorithms
328Due: Nov 11, at 10:00 p.m.
329
330Introduction
331In this assignment, you will have to simulate the operation of page tables and page replacement. As I keep saying: the way to gain a solid understanding of the theory is by applying the concepts in practice.
332
333You have two tasks in this assignment, which will be based on a virtual memory simulator. The first task is to implement virtual-to-physical address translation and demand paging using a two-level page table. The second task is to implement four different page replacement algorithms: FIFO, Clock, exact LRU, and OPT.
334
335Before you start work, you should complete the set of readings about memory, if you haven't done so already:
336Paging: Introduction
337Requirements
338Setup
339You will find the starter code on cslinux, under: /student/cslec/369/assignments/A3-starter-code/starter_code.tgz 
340It is your responsibility to add the code in your repository and make sure that you submit all the necessary files!
341
342DO NOT MANUALLY CREATE A NEW DIRECTORY 'A3' IN YOUR REPOSITORY! An empty directory called 'A3' should be created for you automatically when you log into MarkUs and go on your A3 link. Next, you should see the newly-created 'A3' directory in your repository. As usual, please make sure in advance that you can access your A3 directory, to avoid last-minute surprises.
343
344Note that you may be generating some large trace files and must NOT commit any of the trace files that you generate to your repository or you will run into serious problems with disk quota. Most of the trace programs should be familiar to you from the online exercise, which you should complete first, to get used to the traces. We have added a blocked version of matrix multiply, blocked.c which should exhibit fewer page faults under at least some of the page replacement algorithms. The Makefile shows you exactly how to compile and run the traces. Note that it takes quite a while to run the trace collection.
345
346Compile the trace programs and generate the traces.
347
348You may have noticed while doing the Exercise that the traces generated by Valgrind are enormous since they contain every memory reference from the entire execution. We have provided a program, fastslim.py to reduce the traces by removing repeated references to the same page that occur within a small window of each other while preserving the important characteristics for virtual memory simulation. (For example, a sequence of references to pages A and B such as "ABABABABAB...AB" are reduced to just "AB".) The runit script pipes the output of valgrind through this program to create the reduced trace. If you wish, you can experiment with fastslim.py to try omitting the instruction references from the trace or using a smaller or larger window (fastslim.py --help). You may also want to create traces from other programs, and you will definitely want to create small manual traces for testing.
349
350Task 1 - Address Translation and Paging
351Implement virtual-to-physical address translation and demand paging using a two-level pagetable.
352
353The main driver for the memory simulator, sim.c, reads memory reference traces in the format produced by the fastslim.py tool from valgrind memory traces. For each line in the trace, the program asks for the simulated physical address that corresponds to the given virtual address by calling find_physpage, and then reads from that location. If the access type is a write ("M" for modify or "S" for store), it will also write to the location. You should read sim.c so that you understand how it works but you should not have to modify it..
354
355The simulator is executed as ./sim -f <tracefile> -m <memory size> -s <swapfile size> -a <replacement algorithm> where memory size and swapfile size are the number of frames of simulated physical memory and the number of pages that can be stored in the swapfile, respectively. The swapfile size should be as large as the number of unique virtual pages in the trace, which you should be able to determine easily.
356
357There are four main data structures that are used:
358
359char *physmem: This is the space for our simulated physical memory. We define a simulated page size (and hence frame size) of SIMPAGESIZE and allocate SIMPAGESIZE * "memory size" bytes for physmem.
360struct frame *coremap: The coremap array represents the state of (simulated) physical memory. Each element of the array represents a physical page frame. It records if the physical frame is in use and, if so, a pointer to the page table entry for the virtual page that is using it.
361pgdir_entry_t pgdir[PTRS_PER_PGDIR]: We are using a two-level page table design; the top-level is referred to as the page directory, which is represented by this array. Each page directory entry (pde_t) holds a pointer to a second-level page table (which we refer to simply as page tables, for short). We use the low-order bit in this pointer to record whether the entry is valid or not. The page tables are arrays of page table entries (pte_t), which consist of a frame number if the page is in (simulated) physical memory and an offset into the swap file if the page has been written out to swap. The format of a page table entry is shown here: 
362
363Note that the frame number and status bits share a word, with the low-order PAGE_SHIFT bits (12 in our implementation) used for status (we only have 4 status bits, but you can add more if you find it useful). Thus, for a given physical frame number (e.g. 7), remember to shift it over to leave room for the status bits (e.g., 7 << PAGE_SHIFT) when storing into the pte and to shift it back when retrieving a frame number from a pte (e.g., p->frame >> PAGE_SHIFT).
364swap.c: The swapfile functions are all implemented in this file, along with bitmap functions to track free and used space in the swap file, and to move virtual pages between the swapfile and (simulated) physical memory. The swap_pagein and swap_pageout functions take a frame number and a swap offset as arguments. Be careful not to pass the frame field from a page table entry (pte_t) directly, since that would include the extra status bits. The simulator code creates a temporary file in the current directory where it is executed to use as the swapfile, and removes this file as part of the cleanup when it completes. It does not, however, remove the temporary file if the simulator crashes or exits early due to a detected error. You must manually remove the swapfile.XXXXXX files in this case.
365To complete this task, you will have to write code in pagetable.c. Read the code and comments in this file -- it should be clear where implementation work is needed and what it needs to do. The rand replacement algorithm is already implemented for you, so you can test your translation and paging functionality independently of implementing the replacement algorithms.
366
367Task 2
368Using the starter code, implement each of the four different page replacement algorithms: FIFO, exact LRU, CLOCK (with one ref-bit), OPT.
369
370You will find that you want to add fields to the struct frame for the different page replacement algorithms. You can add them in pagetable.h, but please label them clearly. You may NOT modify the pgtbl_entry_t or pgdir_entry_t structures.
371
372Once you're done implementing the algorithms, run all three programs from the provided traceprogs, plus a fourth program of your choosing with interesting memory reference behaviour, using each of your algorithms (include rand as well). For each algorithm, run the programs on memory sizes 50, 100, 150, and 200. Use the data from these runs to create a set of tables that include the following columns. (Please label your columns in the following order,)
373
374Hit rate
375Hit count
376Miss count
377Overall eviction count
378Clean eviction count
379Dirty eviction count
380Efficiency: Page replacement algorithms must be fast, since page replacement operations can be critical to performance. Consequently, you must implement these policies with efficiency in mind. 
381For example, we will give you the expected complexities for some of the policies: 
382FIFO: init, evict, ref: O(1) in time and space
383LRU: evict, ref: O(1) in time and space; init: O(M) in time and space, where M = size of memory
384CLOCK: init, ref: O(1) in time and space; evict: O(M) in time, O(1) in space, where M = size of memory
385Write up
386Include a file called README.pdf that includes the following information.
387
388The tables prepared in Task 2
389Describe the fourth program of your choice and explain what you found interesting about its memory reference behaviour.
390One paragraph comparing the various algorithms in terms of the results you see in the tables. Do you notice any trends? Which ones are doing better in each case? Think about why and discuss.
391A second paragraph explaining the data you obtained for FIFO and LRU as the size of memory increases. Specifically, comment on what you notice about the hit rate (does it increase or decrease?) when using different memory sizes. Do you notice any anomalies?
392For both paragraphs, explain in detail your thought process and support your arguments in order to generate some insight into the relative behaviour of the replacement policies.
393Finally, whether you work individually or in pairs with a partner, you must submit a plagiarism.txt file, with the following statement:
394"All members of this group reviewed all the code being submitted and have a good understanding of it. All members of this group declare that no code other than their own has been submitted. We both acknowledge that not understanding our own work will result in a zero on this assignment, and that if the code is detected to be plagiarised, severe academic penalties will be applied when the case is brought forward to the Dean."
395
396Marking Scheme
397Task 1: 35%
398Task 2:
399FIFO 5%
400LRU 10%
401CLOCK 10%
402OPT 15%
403(must be able to run all traces in a reasonable amount of time)
404Tables 5%
405Fourth program choice 5%
406Comparison paragraph 5%
407FIFO/LRU discussion 5%
408Program readability and organization 5%
409In order to be able to run tests on your work, we must trust that your submission follows a set of requirements (please be careful about these deductions!):
410Code does not compile -100% for *any* mistake, for example: missing source file necessary for building your code (including Makefile, provided source files, etc.), typos, any compilation error, etc.
411No plagiarism.txt file: -100% (we will assume that your code is plagiarised, if this file is missing)
412Missing or incorrect INFO.txt: -10%
413Warnings: -10%
414Extra output (other than what sim.c produces): -20%
415Code placed in subdirectories: -20% (only place your code directly under your A3 directory)
416Submission
417The assignment must be pushed to the A3 directory in your git repository (again, please do not create this directory manually, MarkUs should create that for you). Don't forget to push your updated simulator code, Makefile and your README.pdf (in text or pdf format). We will retrieve the last revision before the deadline for marking.
418
419Additionally, you must submit an INFO.txt file, which contains as the first 2 lines the following:
420
421your name(s)
422your UtorID(s)
423If you want us to grade an earlier revision of your assignment for whatever reason (for example, for saving some grace tokens if you had a stable submission before the deadline, tried to add new functionality after the deadline but broke your submission irreparably), then you may specify the git hash for the earlier revision you want marked. 
424As a general rule, by default we will always take the last revision before the deadline (or last one after the deadline, up to your remaining unused grace tokens), so you should not be including a line with the git commit hash, except in the exceptional circumstances where it makes sense. So in general, please avoid using this option and just make sure that the last revision (either before the deadline if you submit on time, or up to a subset of your remaining grace tokens if you submit late) is the one you want graded.
425Aside from this, please feel free to describe in a separate paragraph(s), any problems you've encountered, what isn't fully implemented (or doesn't work fully), any special design decisions you've taken (as long as they conform to the assignment specs), etc.
426
427Make sure that you do not leave any other printf messages, other than what sim.c is printing. This will affect marking, so if you don't follow this requirement, you will be deducted 20% for leaving extra output in your final submission.
428Make sure your code compiles without any errors or warnings.
429Code that does not compile will receive zero marks!
430
431As previously, to check that your assignment submission is complete, please reserve time in advance to do the following:
432
433create an empty temporary directory in your account (not in a subdirectory of your repo)
434check out a copy of your repository for this assignment
435verify that all the required files are included (double-check the submission instructions above)
436run make and ensure that you are able to build sim without any errors or warnings (This is an excellent way to verify that the right source files have been committed to the repo.)
437run a few tests using the same traces you used to create the tables in your README.pdf, to ensure that your code behaves as you expect
438make sure to clean up any unnecessary files (executables, traces, etc.), and make sure your files are directly under the A3 directory (no subdirectories!)
439congratulate yourself and enjoy a well-earned break, knowing that your strategy and hard work will pay off!
440Keep in mind again: Code that does not compile, for whatever reason, will receive zero marks!
441---------------------------------------------------------------------------------------------------------------------------
442Assignment 4 - File Systems
443Due: Dec 2, at 10 p.m. (Do not leave this assignment until the last few days, or you will NOT be able to complete it! Work together with your partner, do not split up the tasks since lots of common code may be reusable if you design your code together!)
444
445Introduction
446In this assignment, you will explore the implementation of a particular file system, ext2, and will write tools to modify ext2-format virtual disks. To do this work, you will need to be comfortable working with binary data and will need to learn about the ext2 filesystem.
447
448You can work in pairs for this assignment. MarkUs will only create the appropriate A4 directory in your repository when you log into MarkUs and either invite a partner, or declare that you will work alone. As usual, please log into MarkUs well before the deadline to make sure you can access your repository. (Do not create an A4 the directory in your git repo, otherwise MarkUs won't know about it and we won't be able to see your work.)
449
450This assignment contains some bonus features. Implementing a bonus will compensate for any possible marks lost in another section of the assignment, but can also give you more than 100% if implemented correctly. For implementing any additional functionality which is not specified in the handout, or if you are unsure whether to handle some inode parameters in specific cases (after having read the documentation!), please ask on the discussion board.
451
452Requirements
453Your task is to write a set of programs (in C) that operate on an ext2 formatted virtual disk. The executables must be named exactly as listed below, and must take the specified arguments. 
454Important: Remember to read the rest of the assignment, especially the general notes, simplifying assumptions, other tips, etc., before you start your implementation.
455
456ext2_mkdir: This program takes two command line arguments. The first is the name of an ext2 formatted virtual disk. The second is an absolute path on your ext2 formatted disk. The program should work like mkdir, creating the final directory on the specified path on the disk. If any component on the path to the location where the final directory is to be created does not exist (or is not a directory) then your program should return an appropriate error: ENOENT. If the specified directory already exists, then your program should return EEXIST. Note:
457Please read the specifications to make sure you're implementing everything correctly (e.g., directory entries should be aligned to 4B, entry names are not null-terminated, etc.).
458When you allocate a new inode or data block, you *must use the next one available* from the corresponding bitmap (excluding reserved inodes, of course). Failure to do so will result in deductions, so please be careful about this requirement.
459When adding a new directory entry to the parent, you must always append after the last entry in the last used block of the parent. That is, you should not be looking to "fill existing gaps" left by removed directory entries in the past.
460Be careful to consider trailing slashes in paths. These will show up during testing so it's your responsibility to make your code as robust as possible by capturing corner cases.
461Here are just a few examples of how to handle some cases: 
462./ext2_mkdir image.img /foo/bar/blah, where both "foo" and "bar" exist but blah does not, should succeed in creating a new directory called "blah" with the given path in the image. Same thing if blah had a trailing "/".
463./ext2_mkdir image.img /foo/bar/blah, where the path is valid up to "blah" and "blah" is an already existing directory, returns EEXIST. Same thing if blah had a trailing "/".
464./ext2_mkdir image.img /foo/bar/blah/, where both "foo" and "bar" exist but blah is an existing file, should return ENOENT.
465./ext2_mkdir image.img /foo/bar/blah, where foo does not exist, or bar is a file, should return ENOENT.
466
467ext2_cp: This program takes three command line arguments. The first is the name of an ext2 formatted virtual disk. The second is the path to a file on your native operating system, and the third is an absolute path on your ext2 formatted disk. The program should work like cp, copying the file on your native file system onto the specified location on the disk. If the source file does not exist or the target is an invalid path, then your program should return the appropriate error (ENOENT). If the target is a file with the same name that already exists, you should not overwrite it (as cp would), just return EEXIST instead. 
468Note:
469Please read the specifications of ext2 carefully, some things you will not need to worry about (like permissions, gid, uid, etc.), while setting other information in the inodes may be important (e.g., i_dtime).
470When you allocate a new inode or data block, you *must use the next one available* from the corresponding bitmap (excluding reserved inodes, of course). Failure to do so will result in deductions, so please be careful about this requirement.
471When adding a new directory entry to the parent, you must always append after the last entry in the last used block of the parent. That is, you should not be looking to "fill existing gaps" left by removed directory entries in the past.
472Be careful to consider trailing slashes in paths. These will show up during testing so it's your responsibility to make your code as robust as possible by capturing corner cases.
473Here are just a few examples of how to handle some cases. We'll use a source file called "doh" as the file being copied, although an absolute path works too, since it'll be on your local file system anyway (make sure the file actually exists, otherwise you cannot copy it, and that it is not a directory). 
474./ext2_cp image.img doh /foo/bar/blah, where the target path is valid and blah does not already exist, will copy the source file "doh" into a new file called "blah" in the image in the indicated path.
475./ext2_cp image.img doh /foo/bar/blah, where either foo or bar does not exist, or either foo or bar is a file, then ENOENT.
476./ext2_cp image.img doh /foo/bar/blah, where the target path is valid but file "blah" exists, then EEXIST and no overwriting.
477./ext2_cp image.img doh /foo/bar/blah, where the target path is valid but "blah" is a directory, the file "doh" will be copied as "doh" under directory "blah".
478./ext2_cp image.img doh /foo/bar/blah/, where the target path is valid and a file "doh" does not already exist under "blah", the file "doh" will be copied under directory "blah".
479./ext2_cp image.img doh /foo/bar/blah/, where the path is valid and a file "doh" already exists under "blah", the file "doh" will not be overwritten and EEXIST will be returned.
480
481ext2_ln: This program takes three command line arguments. The first is the name of an ext2 formatted virtual disk. The other two are absolute paths on your ext2 formatted disk. The program should work like ln, creating a hard link to the given source path. For example, the following command will create within image.img a hard link called "foo" (aka the hard link) to the file called "bar" (aka the source file or target file), both of them being located in /level1/level2 path: 
482ext2_ln image.img /level1/level2/bar /level1/level2/foo 
483This program should handle any exceptional circumstances, for example:
484ENOENT: if the source contains an invalid path (for example, if level2 does not exist, or if level1 is a file, etc.),
485ENOENT: if the source name does not exist (for example, if bar does not exist),
486EISDIR: if the source refers to a directory (for example, if bar is a directory), etc.
487EEXIST: if the hard link is a file which already exists (for example, if foo already exists),
488To simplify your work, we will slightly deviate from the behaviour of regular ln. If the hard link name "foo" exists and happens to be a directory, regular ln would actually create a hardlink with the name given by the source ("bar"), inside the directory "foo". For ext2_ln, you must simply return EISDIR if the target is an existing directory. 
489Additionally, this command may take a "-s" flag, after the disk image argument. When this flag is used, your program must create a symlink instead (other arguments remain the same). 
490Note:
491For symbolic links, you will see that the specs mention that if the path is short enough, it can be stored in the inode in the space that would otherwise be occupied by block pointers - these are called fast symlinks. Do *not* implement fast symlinks, just store the path in a data block regardless of length, to keep things uniform in your implementation, and to facilitate testing.
492If in doubt about correct operation of links, use the ext2 specs and ask on the discussion board.
493Similarly to "ln -s", for ext2_ln the source path for a symbolic link doesn't have to be a valid path. No error is expected, the invalid source path will just be stored in the target symlink. This is different from hard links where an invalid source path would result in an error.
494Similarly to hard links, for ext2_ln we'll simplify your task for the case when the target is an existing directory, by just returning EISDIR, rather than creating a symlink inside the target directory.
495Remember that for a symlink if the source is a directory, then the symlink can be created, unlike for hard links where this is not allowed.
496Same observations from ext2_cp and ext2_mkdir apply with respect to using the next available inode and/or data block, and regarding appending new directory entries instead of trying to fill existing gaps.
497
498ext2_rm: This program takes two command line arguments. The first is the name of an ext2 formatted virtual disk, and the second is an absolute path to a regular file or link (not a directory) on that disk. The program should work like rm, removing the specified file from the disk. Your program should return the appropriate error in exceptional circumstances. For example, if the path to the file is invalid or if it's valid but the file does not exist, then ENOENT is the right error code. If the path does not end in a trailing "/", but the last name in the path is actually a directory, then EISDIR must be returned (see exception for the bonus below). Once again, please read the specifications of ext2 carefully, to figure out what needs to actually happen when a file or link is removed (e.g., no need to zero out data blocks, must set i_dtime in the inode, removing a directory entry must adjust its predecessor to indicate the next valid directory entry, etc.). 
499BONUS: Implement an additional "-r" flag (after the disk image argument), which allows removing directories as well (except for the root directory and for lost+found, which you can assume are special cases that we will not be testing). In this case, you will have to recursively remove all the contents of the directory specified in the last argument. If "-r" is used with a regular file or link, then it should be ignored (the ext2_rm operation should be carried out as if the flag had not been entered). If you decide to do the bonus, make sure first that your ext2_rm works, then create a new copy of it and rename it to ext2_rm_bonus.c, and implement the additional functionality in this separate source file! See the submission instructions to make sure you've added all the right build targets in the Makefile!
500
501ext2_restore: This program takes two command line arguments. The first is the name of an ext2 formatted virtual disk, and the second is an absolute path to a file or link (not a directory!) on that disk. The program should be the exact opposite of rm, restoring the specified file that has been previous removed. As usual, your program should handle exceptional cases and return the appropriate error. For example, if the path to the file is invalid (ENOENT), if file cannot be found (ENOENT), or if the restore target is a directory (EISDIR, except for restore bonus, see below). 
502Hint: The file to be restored will not appear in the directory entries of the parent directory, unless you search the "gaps" left when files get removed. The directory entry structure is the key to finding out these gaps and searching for the removed file. 
503A few important notes:
504If the directory entry for the file has not been overwritten, you will still need to make sure that the inode has not been reused, and that none of its data blocks have been reallocated. You may assume that the bitmaps are reliable indicators of such fact. If the file cannot be fully restored, your program should terminate with ENOENT, indicating that the operation was unsuccessful.
505For testing, you should focus primarily on restoring files that you've removed using your ext2_rm implementation, since ext2_restore should undo the exact changes made by ext2_rm. While there are some removed entries already present in some of the image files provided, the respective files have been removed on a non-ext2 file system, which is not doing the removal the same way that ext2 would. In ext2, when you do "rm", the inode's i_blocks do not get zeroed, and you can do full recovery, as stated in the assignment (which deals solely with ext2 images, hence why you only have to worry about this type of (simpler) recovery). In other FSs things work differently. In ext3, when you rm a file, the data block indexes from its inode do get zeroed, so recovery is not as trivial. For example, there are some removed files in deletedfile.img, which have their blocks zero-ed out (due to how these images were created). There are also some unrecoverable entries in images like twolevel.img, largefile.img, etc. In such cases, your code should still work, but simply recover a file as an empty file (with no data blocks), or discard the entry if it is unrecoverable for other reasons. However, for the most part, try to recover files that you've ext2_rm-ed yourself, to make sure that you can restore data blocks as well. We will not be testing recovery of files removed with a non-ext2 tool.
506We will not try to recover files that had hardlinks at the time of removal. This is because when trying to restore a file, if its inode is already in use, there are two options: the file we're trying to restore previously had other hardlinks (and hence its inode never really got invalidated), _or_ its inode has been re-allocated to a completely new file. Since there is no way to tell between these two possibilities, recovery in this case should not be attempted.
507BONUS: Implement an additional "-r" flag (after the disk image argument), which allows restoring directories as well (except for the root directory and for lost+found, which you can assume are special cases that we will not be testing). In this case, you will have to recursively restore all the contents of the directory specified in the last argument. If "-r" is used with a regular file or link, then it should be ignored (the restore operation should be carried out as if the flag had not been entered). If you decide to do the bonus, make sure first that your ext2_restore works, then create a new copy of it and rename it to ext2_restore_bonus.c, and implement the additional functionality in this separate source file. See the submission instructions to make sure you've added all the right build targets in the Makefile!
508
509ext2_checker: This program takes only one command line argument: the name of an ext2 formatted virtual disk. The program should implement a lightweight file system checker, which detects a small subset of possible file system inconsistencies and takes appropriate actions to fix them (as well as counts the number of fixes), as follows:
510the superblock and block group counters for free blocks and free inodes must match the number of free inodes and data blocks as indicated in the respective bitmaps. If an inconsistency is detected, the checker will trust the bitmaps and update the counters. Once such an inconsistency is fixed, your program should output the following message: "Fixed: X's Y counter was off by Z compared to the bitmap", where X stands for either "superblock" or "block group", Y is either "free blocks" or "free inodes", and Z is the difference (in absolute value). The Z values should be added to the total number of fixes.
511for each file, directory, or symlink, you must check if its inode's i_mode matches the directory entry file_type. If it does not, then you shall trust the inode's i_mode and fix the file_type to match. Once such an inconsistency is repaired, your program should output the following message: "Fixed: Entry type vs inode mismatch: inode [I]", where I is the inode number for the respective file system object. Each inconsistency counts towards to total number of fixes.
512for each file, directory or symlink, you must check that its inode is marked as allocated in the inode bitmap. If it isn't, then the inode bitmap must be updated to indicate that the inode is in use. You should also update the corresponding counters in the block group and superblock (they should be consistent with the bitmap at this point). Once such an inconsistency is repaired, your program should output the following message: "Fixed: inode [I] not marked as in-use", where I is the inode number. Each inconsistency counts towards to total number of fixes.
513for each file, directory, or symlink, you must check that its inode's i_dtime is set to 0. If it isn't, you must reset (to 0), to indicate that the file should not be marked for removal. Once such an inconsistency is repaired, your program should output the following message: "Fixed: valid inode marked for deletion: [I]", where I is the inode number. Each inconsistency counts towards to total number of fixes.
514for each file, directory, or symlink, you must check that all its data blocks are allocated in the data bitmap. If any of its blocks is not allocated, you must fix this by updating the data bitmap. You should also update the corresponding counters in the block group and superblock, (they should be consistent with the bitmap at this point). Once such an inconsistency is fixed, your program should output the following message: "Fixed: D in-use data blocks not marked in data bitmap for inode: [I]", where D is the number of data blocks fixed, and I is the inode number. Each inconsistency counts towards to total number of fixes.
515Your program must count all the fixed inconsistencies, and produce one last message: either "N file system inconsistencies repaired!", where N is the number of fixes made, or "No file system inconsistencies detected!". 
516You may limit your consistency checks to only regular files, directories and symlinks. 
517Note: You must tackle the consistency checks in the exact order specified above. You must fix the counters based on the bitmaps, as a one-time step before attempting to fix any other type of inconsistency. Even if initially trusting the bitmaps may not be the way to go (since they could be corrupted), the counters should get readjusted in the later steps anyway, whenever the bitmaps get updated. The Z values from point a) should be added to the tally of fixes, but do not include any further superblock or block group counter adjustments from points c) and e) (since technically these may be just correcting the adjustments made in point a)).
518Functionality and error checks - general notes: 
519All of these programs should be minimalist in terms of the functionality. Don't implement what isn't specified: only provide the required functionality. For example, don't implement wildcards. Also, can't delete directories? Too bad! Unless you want the bonus! :) 
520However, it is your responsibility to make your code as robust as possible by capturing corner cases for the functionality that you need to implement. For example, be careful to consider trailing slashes in paths (e.g., ext2_cp, ext2_mkdir, etc.). Such things will show up in our tests, so you need to test your code properly! For any of the above, if you cannot create a new inode or add a new data block due to lack of space on the disk image, then returning ENOSPC is expected. Keep in mind that we don't want to overload this handout to make it unreadable, so it is your responsibility to consider error checks where appropriate. As a general rule, whenever in doubt, check the ext2 documentation and confirm your doubts by asking questions on the discussion board.
521
522Simplifying assumptions that you can make in your implementation:
523
524Given the small size of the images, you may assume that you have to support direct block pointers and only the first indirect pointer for files, and only support direct block pointers for directories.
525You may assume that a path will not include symlinks in the middle, so you won't have to expand them or anything like that. Furthermore, although you do have to check if a path inside an ext2 image is absolute (otherwise, a relative path would not make sense, since we don't have the concept of a "current working directory" within the image), you can use a simplifying assumption that in the middle of a path pointing within an image you will not find a "." or ".." (for example, you do not need to support something like /foo/../bar, or /foo/././././bar). 
526However, keep in mind that a path may be invalid (e.g., an entry in the middle of the path may be a file instead of a directory, or may not even exist), so you do need to check every entry along the path for validity.
527You may assume that for recovery purposes, you will not be asked to recover files with hardlinks. When attempting to restore a file, if its inode is marked as in-use in the inode bitmap, then you can safely assume that the file is not recoverable.
528If a file that gets removed happens to be the only entry in the last directory block of a directory, then you do not need to "reclaim" this directory block.
529When creating a file or directory, you should always create an entry at the end of the last block of the parent directory, or in a new block if there is no space. You should not attempt to create a new entry in a "gap" resulted from a previously removed entry.
530Additionally, please be careful in following the specifications. When in doubt about how to handle a specific case, please ask on the discussion board. For example, a tricky corner case arises if a directory has more than one block and you are removing a file or directory which happens to be the first entry in a block other than the first. In this case, you do not have "." and ".." to change the rec_len for. In order to avoid losing track of any potential subsequent entries, you should take the approach described in the specs. You should be able to infer from the specs that in this special case, your must zero the inode and adjust the rec_len to the next entry (or the end of the block). In this case, this file will become unrecoverable and that's ok.
531
532You will find it very useful for these programs to share code. You will want a function that performs a path walk, for example. You will also want a function that opens a specific directory entry and writes to it.
533
534To help you visualize your file system, we are giving you an already built tool, called ext2_ls. This program takes two command line arguments. 
535- The first is the name of an ext2 formatted virtual disk. 
536- The second is an absolute path on the ext2 formatted disk. 
537The program works like ls -1a (that's number one "1", not lowercase letter "L"): it prints one line for every directory entry (including "." and "..") from the directory specified by the absolute path. If the path does not exist, it prints "No such file or directory". If the path is a file or link, the tool simply prints the full path on a single line.
538
539We are also giving you a tool called ext2_dump, which dumps all the raw information about the image contents. This is very similar to the readimage program that you have to implement for the tutorial exercises that give you practice with ext2 images. Once again, we encourage you to work on the tutorial exercises first, to gain experience with extracting various bits of information from an ext2 image.
540
541We are also giving you a tool called ext2_corruptor, which corrupts file system images, introducing various inconsistencies like the ones that you have to fix. This tool has limited capabilities, and is solely to help you with basic testing. You are welcome to develop your own corruptor tool as well.
542
543Finally, to help you in determine some basic correctness, we are giving you some sample test cases: running a set of commands and their expected outputs (image dumps). These self-tester details, test cases, and expected results are found on cslinux, under this directory: /student/cslec/369/assignments/A4-self-test/
544
545Learning about the Filesystem
546Here are several sample virtual disk images:
547
548emptydisk: An empty virtual disk.
549onefile: A single text file has been added to emptydisk.
550deletedfile: The file from onefile has been removed.
551onedirectory: A single directory containing a text file has been added to emptydisk.
552hardlink: A hard link to the textfile in onedirectory was added.
553deleteddirectory: A recursive remove was used to remove the directory and file from onedirectory.
554twolevel: The root directory contains a directory called level1 and a file called afile. level1 contains a directory called level2, and level2 contains a file called bfile.
555twolevel-corrupt: Same as twolevel, except that the image contains file system inconsistencies that you will have to repair with the checker.
556twolevel-norestore-afile: Same as twolevel, except that /afile has been removed, and its inode number has been reused. This image can be used for testing the case when a file cannot be restored.
557largefile: A file larger than 13KB (13440 bytes) is in the root directory. This file requires the single indirect block in the inode.
558These disks were each created and formatted in the same way (on an ubuntu virtual machine):
559
560% dd if=/dev/zero of=~/DISKNAME.img bs=1024 count=128
561% mke2fs -N 32 DISKNAME.img
562% sudo mount -o loop ~/DISKNAME.img /home/bogdan/mntpoint
563% cd /home/bogdan/mntpoint
564% ...... normal linux commands to add/remove files/directories/links .....
565% cd ~
566% umount /home/bogdan/mntpoint
567Since we are creating images with mke2fs, the disks are formatted with the ext2 file system. You may wish to read about this system before doing some exploration. The wikipedia page for ext2 provides a good overview, but the Ext2 wiki and Dave Poirer's Second Extended File System article provide more detail on how the system places data onto a disk. It's a good reference to keep on hand as you explore.
568
569We are restricting ourselves to some simple parameters, so you can make the following assumptions when you write your code:
570
571A disk is 128 blocks where the block size is 1024 bytes.
572There is only one block group.
573There are 32 inodes.
574You do not have to worry about permissions or modified time fields in the inodes. You should set the type (in i_mode), i_size, i_links_count, i_blocks(disk sectors), and the i_block array.
575We will not test your code on anything other than disk images that follow this specification, or on corrupted disk images (except for the checker, of course).
576
577Other tips:
578
579Inode and disk block numbering starts at 1 instead of 0.
580The root inode is inode number 2 (at index 1)
581The first 11 inodes are reserved.
582There is always a lost+found directory in the root directory.
583Disk sectors are 512 bytes. (This is relevant for the i_blocks field of the inode.)
584You should be able to handle directories that require more than one block.
585You should be able to handle a file that needs a single indirection
586Although you can construct your own structs from the information in the documentation above, we recommend you use the ext2.h file that we used for the test code. A bunch of components that we aren't using have been taken out, but there are still quite a few fields in various data structures which are irrelevant for the assignment purposes.
587You will probably also want to explore the disk images to get an intuitive sense of how they are structured (the three tutorial exercises will also help you explore the disk images and get started on the assignment).
588
589There are two good ways to interface with these images. The first way is to interact with it like a user by mounting the file system so that you can use standard commands (mkdir, cp, rm, ln) to interact with it. Details of how to do this are below. The second way is to interact with the disk as if it is a flat binary file. Use xxd to create hex dumps, diff to look for differences between the dumps, and your favorite text editor to view the diffs. For example (YMMV):
590
591% diff <(xxd emptydisk.img) <(xxd onefile.img) > empty-onefile.diff
592% vimdiff empty-onefile.diff
593You should be able to use a combination of these techniques to understand how files are placed on disk and how they are removed. For example, you can create a new disk image, use mount to place files of various sizes on it, unmount it, and then use xxd and diff to see how the image differs from the other images you have.
594
595Mounting a file system
596If you have root access on a Linux machine (or Linux virtual machine), you can use mount to mount the disk into your file system and to peruse its contents. (Note: this requires sudo, so you will need to do this on a machine (or virtual machine) that you administer.
597
598On the lab machines, you can use a tool called FUSE that allows you to mount a file system at user-level (from your regular account). It may not work on an NFS mounted file system, so this will only work on the lab workstations (it may not work via ssh-ing remotely).
599
600Note: <UtorID> should be replaced with your own UtorID below.
601
602# create a directory in /tmp and go there
603mkdir -m 700 /tmp/<UtorID>-csc369h
604cd /tmp/<UtorID>-csc369h
605
606# to create your own disk image
607dd if=/dev/zero of=DISKNAME.img bs=1024 count=128
608/sbin/mke2fs -N 32 -F DISKNAME.img
609
610# create a mount point and mount the image
611# CWD is /tmp/<UtorID>-csc369h
612mkdir mnt
613fuseext2 -o rw+ DISKNAME.img mnt
614
615# check to see if it is mounted
616df -hl
617
618# now you can use the mounted file system, for example
619mkdir mnt/test
620
621# unmount the image
622fusermount -u mnt
623You can use the same strategy to mount one of the images provided above.
624
625Marking scheme
626ext2_cp: 12%
627ext2_mkdir: 12%
628ext2_ln: 12%
629ext2_rm: 14% (+5% bonus)
630ext2_restore: 20% (+5% bonus)
631ext2_checker: 20%
632Code style and organization: 10% - code design/organization (modularity, code readability, reasonable variable names, avoid code duplication, appropriate comments where necessary, proper indentation and spacing, etc.)
633In order to be able to run tests on your work, we must trust that your submission follows a set of requirements (please be careful about these deductions!):
634Code does not compile -100% for *any* mistake, for example: missing source file necessary for building your code (including Makefile, provided ext2.h header, etc.), wrong Makefile target names, typos, any compilation error, etc.
635No plagiarism.txt file: -100% (we will assume that your code is plagiarised, if this file is missing)
636Missing or incorrect INFO.txt: -10%
637Warnings: -10%
638Extra output to stdout: -20%
639Code placed in subdirectories: -20% (only place your code directly under your A4 directory)
640See additional instructions/reminders at the end of this handout.
641Submission
642The assignment should be submitted to an A4 directory in your git repository. Don't forget to add and commit+push all of the code for the required programs. Please also provide a Makefile that will create your programs. Your Makefile should use -Wall, and produce no warnings. Please make sure that your Makefile includes the following separate targets:
643
644ext2_cp: compiles and produces the ext2_cp executable
645ext2_mkdir: compiles and produces the ext2_mkdir executable
646ext2_ln: compiles and produces the ext2_ln executable
647ext2_rm: compiles and produces the ext2_rm executable
648ext2_rm_bonus (optional) compiles and produces the ext2_rm_bonus executable (optional, for bonus)
649ext2_restore: compiles and produces the ext2_restore executable
650ext2_restore_bonus (optional): compiles and produces the ext2_restore_bonus executable (optional, for bonus)
651ext2_checker: compiles and produces the ext2_checker executable
652Additionally, invoking make without arguments must compile all the targets. 
653Please consider separating the bonus parts as indicated above, in order to make it easier for us to determine if you did the bonus or not. The bonus source files and their counterparts may include large portions of the same code. This will make it easier for you as well, to make sure that at the very least the baseline implementation works, even if the bonus part may have problems or crash your baseline (non-bonus) implementation. 
654Additionally, you must submit an INFO.txt file, which contains as the first 2 lines the following:
655
656your name(s)
657your UtorID(s)
658If you want us to grade an earlier revision of your assignment for whatever reason (for example, for saving some grace tokens if you had a stable submission before the deadline, tried to add new functionality after the deadline but broke your submission irreparably), then you may specify the git hash for the earlier revision you want marked. 
659As a general rule, by default we will always take the last revision before the deadline (or last one after the deadline, up to your remaining unused grace tokens), so you should not be including a line with the git commit hash, except in the exceptional circumstances where it makes sense. So in general, please avoid using this option and just make sure that the last revision (either before the deadline if you submit on time, or up to a subset of your remaining grace tokens if you submit late) is the one you want graded.
660Aside from this, please feel free to describe in a separate paragraph(s), any problems you've encountered, what isn't fully implemented (or doesn't work fully), any special design decisions you've taken (as long as they conform to the assignment specs), etc. Feel free to explain what is not implemented and describe what features you have completed. You may receive partial credit for functionality that is implemented but that does not complete one of the five required programs successfully.
661
662Finally, whether you work individually or in pairs with a partner, you must submit a plagiarism.txt file, with the following statement:
663"All members of this group reviewed all the code being submitted and have a good understanding of it. All members of this group declare that no code other than their own has been submitted. We both acknowledge that not understanding our own work will result in a zero on this assignment, and that if the code is detected to be plagiarised, severe academic penalties will be applied when the case is brought forward to the Dean."
664
665Very important reminders (see also marking scheme and submission instructions above): 
666- Assignments missing a Makefile will receive a 0, as if the code did not compile!
667- You must make sure that your Makefile compiles all of your files, including possible helper files, depending on your design, and that you have included all the necessary targets specified above.
668- You must make sure that the source files that are mandatory are named exactly as indicated in the handout, and that the Makefile produces executables with the same name excluding the .c extension (for example: compiling ext2_cp.c should generate an executable named ext2_cp - do not submit the executables though).
669- Missing files due to submission mistakes (forgot to add files, forgot to commit last version, etc.), will not be considered!
670- It is your responsibility to ensure that your code works exactly as you expect it to, on the lab machines!
671---------------------------------------------------------------------------------------------------------------------------