/n COMP 310 Please read the entire PDF before starting. It is very important that you follow the directions as closely as possible. The directions, while perhaps tedious, are designed to

make it as easy as possible for us to run and grade your code. This assignment will count for 20% of your final grade. To get full marks, you must follow all directions below: • You must write your code in the C programming language. We use C in this class because most practical contemporary OS kernels are written in C/C++ (e.g., Mac, Linux, Windows and others). • Make sure that all filenames and any specified functions/data structures are spelled exactly as described in this document; otherwise, the code will likely receive a zero. You are free to modify function signatures. ⚫ The output from your program must exactly match the output that we specify, except for spaces. Make sure that your code compiles. Code that does not compile will likely result in a zero. • • Write your name and student ID in a comment at the top of all files modified from the starter code. • Your code must follow our style guidelines, which are listed on the next page. Up to 30% can be removed for code that does not comply to our style guidelines. Hints & tips • Start early. Programming projects always take more time than you estimate! • You are free to include any header files from the C standard library that are available for including by default in the given Docker image. • Do not wait until the last minute to submit your code. Submit early and often a good rule of thumb is to submit every time you finish writing and testing a function. • Write your code incrementally. Don't try to write everything at once. That never works well. Start off with something small and make sure that it works, then add to it gradually, making sure that it works every step of the way. • Seek help when you get stuck! Check our discussion board first to see if your question has already been asked and answered. Ask your question on the discussion board if it hasn't been asked already. Talk to a TA during office hours if you are having difficulties with programming. Go to the instructor's office hours if you need extra help with understanding a part of the course material. Note that small amounts of code can be posted on the discussion board as private posts, which only the instructors and T.A.'s can see. But if more than a few lines of code are in question, then it is better to seek help in person. Often the problem requires a different approach such as proper use of the debugger, and the discussion board is a poor medium for this kind of help. (You could also post a single line of code and error message (error traceback) as a public post.) • If you come to see us in office hours, please do not ask "Here is my program. What's wrong with it?" We expect you to at least make an effort to start to debug your own code, a skill which you are meant to learn as part of this course. Reading through someone else's code is a difficult process-we just don't have the time to read through and understand even a fraction of everyone's code in detail. However, if you show us the work that you've done to narrow down the problem to a specific section of the code, why you think it doesn't work, and what you've tried in order to fix it, it will be much easier to provide you with the specific help you require and we will be happy to do so. Policy on Academic Integrity See section 5 of our syllabus for our course policies on academic integrity. In short, you must write the assignment on your own (or with a partner, if you have registered them as such). Do not copy someone else's work, nor share your work with someone else. Do not copy from any online sources. Late policy Late assignments will be accepted up to two days late and will be penalized by 10 points out of 100 per day. Note that if you submit one minute late, it is equivalent to submitting 23 hours and 59 minutes late, etc. So, make sure you are nowhere near that threshold when you submit. Style guidelines As students at the 300 and 400 level, it is expected that you code at the level of a beginner software engineer. Please follow the brief coding style below in all your OS assignments. • Indentation: All blocks of code must be indented by a minimum of 4 spaces, or with a 1-tab. (Pretend you are writing Python code.) • • Horizontal spacing: Parts of the code that are logically different should be separated by a blank line. Comments: Provide useful explanations to the reader of the code. We do not expect you to comment all your code, but we do expect explanations for more complex parts. In other words, do not write comments that just restate the code; here are some situations where a comment may be appropriate: describing the purpose of a function - explaining the high-level steps of a function - explaining magic numbers - describing side-effects of a function • Names: Name your variables, constants, functions, objects, methods, data structures and files appro- priately. The purpose of each should be obvious from the name and can save you from writing a comment. Page 2 Compilation environment Because of the many different versions of gcc and C library implementations, we will ask you to use a stan- dardized testing environment when compiling and testing your code. We will be using the same environment when grading your code, so it's important that we all use the same one. If your code does not compile in this environment, you will receive a very low mark, and possibly a zero. We will use Docker for our testing environment. Here are the steps you should follow: 1. Install Docker by following the steps at https://docs.docker.com/get-docker. Docker is available for Mac, Linux and Windows. Note: You do not need to sign up for a Docker account. You can skip that step. 2. Open up a command line and enter the following command: docker pull gcc:13.2 3. cd to the directory containing your assignment code files (*.c, *.h and Makefile). Then enter the following command to run a Docker shell. This command is long, so you may want to alias it: docker run --rm -it --mount type=bind, source=., target=/code --entrypoint /bin/bash -w /code gcc: 13.2 4. Once you are in the Docker shell, you should find yourself in the /code directory by default. This directory will contain all the files in the folder you were in before launching the shell. You can now run make to compile your code. (Don't forget to pass the framesize=X and varmemsize=Y arguments.) Note: Any changes made to your files here (including the creation of your executable) will be reflected in your original folder (on your hard drive). So, be careful not to delete any files from within Docker. You are also free to modify the Docker image by adding additional packages (such as vim) to it, as long as these packages do not change the compilation environment (e.g., by adding a new compiler or new libraries). You can add packages by doing the following: 1. Create a file called Dockerfile with the following contents. This one installs vim and valgrind: FROM gcc:13.2 RUN apt-get update && apt-get install -y --no-install-recommends vim valgrind 2. In the command line, cd to the folder containing your Dockerfile and enter the following command: docker build . -t 310 -f Dockerfile 3. Then run the same command as in step 3 above (first cd'ing to your code folder), but replace gcc:13.2 by 310 at the end of the command. Submitting your code and running the public tests For each question, we provide examples of how your code should behave. All examples are given as if you were to run the commands while inside the shell. During grading, we will run these examples and verify that your code outputs the same as given in the examples. Part of your assignment mark will be determined by the results of these tests. We will also run additional, private tests on your code. Therefore, it is your responsibility to make sure your code/functions work for any inputs, not just the ones shown in the examples. You are free to handle corner cases as you wish, unless we explicitly mention how to handle such a case. To run your code on our public tests, as well as to submit your code for grading, please check post #72 (Submission instructions) on Ed. For submission of late assignments (within the two-day late period), check post #274. Page 3 In this assignment we will write functions that operate on a filesystem. We provide starter code for this assignment which contains our solution for Assignment 2 as well as our filesystem implementation. We begin by describing the properties of our filesystem, the new shell commands, the list of new files included in the starter code, an example of how to use the filesystem and a note about using your own A2 solution code. We then discuss your tasks for the assignment. Filesystem architecture Our filesystem has a similar structure to the simple filesystem discussed in class. So if you attended the lectures and did the practice filesystem problems, you are already in a good position to understand some part of our implementation. If not, you are strongly suggested to catch up on those lectures before beginning this assignment. First, we will store our filesystem inside a single file on our computer. We will call this file the hard drive file or disk image. A regular hard drive has sectors that are read from and written to; our hard drive file will also have 'sectors' (of size 512 bytes) which are really just bytes in the file. Sector 0 will be the first 512 bytes of the file; sector 1 will be from bytes 512 to 1024, and so on. In this way, we can approximate a real hard drive by using this one file. Our shell will be able to use only one disk image at a time. The file will be specified as the first argument to the myshell executable. For instance, to run the shell with blank.dsk, which is a disk image of size 1MB provided with the starter code, you can run ./myshell blank.dsk A disk image by itself is just an empty file with some metadata at the beginning (sector 0) relating to partitions. In order for our shell to use it, we must first format it for our filesystem. To do this, we must pass the -f flag to myshell, as follows: ./myshell blank.sk -f Note that formatting will destroy any metadata already existing in the disk image. So if your disk image already has some files on it and you then format it by passing the -f flag, your files will no longer be accessible. Now for the basics of the filesystem. The filesystem stores a file by creating an inode for it in a free sector, and then stores the data of the file in other sectors (called the data blocks); the inode for a file will store the sector numbers for the file's data blocks. = In particular, the inode will directly store 123 sector numbers for data blocks (recall that each sector is 512 bytes, so that means that 123 * 512 62,976 bytes can be addressed by these direct block pointers). If a file needs more than that, the filesystem will create (in a new sector) an indirect block which has space for another 128 sector numbers (pointing to data blocks). If a file still needs more, it will create (in a new sector) a double indirect block, which will hold 128 sector numbers that each point to indirect blocks (each allocated as needed). Note that this scheme is very similar to the one discussed in class. See Figure 1 (next page) for an illustration. When making a new file, space on disk must be found for the inode and for the data blocks (and possibly the indirect block(s)). Finding free space is accomplished by checking the free space bitmap, which itself is written to disk in a reserved sector near the start of the disk. The data blocks for a file do not have to be all stored in one contiguous chunk, so a file's data blocks may be spread across the disk. The filesystem has both on-disk and in-memory data structures. For example, the on-disk inode stores the block sectors. There is also an in-memory inode, into which the on-disk inode is loaded when a file is accessed; the in-memory inode also contains some additional information. Page 4 Inode 123 pointers Data Data Indirect block Double indirect block data data 512 bytes each Block of pointers Block of data ... data 128 data blocks Block of pointers ... 512 bytes each pointers Block of pointers 128 blocks of pointers data ... data 128 data blocks 512 bytes each Figure 1: On-disk inode struct (defined in inode.h) Also as discussed in class, the filesystem has a write-behind cache for both inodes and data blocks. When a request is made to read a block, the cache is checked first before we go to the hard disk. If the block is not in the cache, then we read it from the hard disk (disk image) and put it in the cache. Similarly, if we write a block, we put it in the cache. The cache has a limited size, so when it is full, we evict another block (writing to disk if needed), and on the close of the shell we flush all blocks to disk. Finally, although our filesystem supports directories, we will assume that all files are stored in the root directory. Shell commands To make our shell work with this new filesystem, we have added shell commands which we describe below. Note that some of these commands had already existed, but they operated on your real filesystem and not a disk image and its filesystem as described above; we have replaced those implementations with versions that do operate on the disk image. (Note that we've also renamed commands to remove their my_ prefix.) • ls: Lists all files (in the root directory). • cat fname: Displays the contents of the specified file. • rm fname: Removes the specified file. • create fname size: Creates a (blank) file with the given filename and initial size. ... • write fname datal ...: Writes data into the specified file. (Spaces are supported; any reasonable number of tokens can be given.) Note that any write will move forward the current offset of the file, so subsequent reads/writes will take place after the written data. read fname bytes: Displays the given number of bytes of the specified file. Note that any read will move forward the current offset of the file, so subsequent reads/writes will take place after the written data. • size fname: Displays the number of bytes taken up in data blocks by the given file. • seek fname offset: Updates the given file's offset to the given amount, to be used for subsequent reads/writes. • freespace: Prints out the number of free sectors on the disk. (You will implement some further commands.) Page 5