Assignment 4: The Very Simple File System
Data structure作业 | os代写 | shell | project | Python代做 | assignment代做 – 这是os进行训练的代写, 对文件系统的实现流程进行训练解析, 是比较典型的Data structure/bash/shell/os等代写方向, 该题目是值得借鉴的assignment代写的题目
In this assignment, you implement a version (Section 2) of the Very Simple File System (VSFS) from the OSTEP textbook and our lectures. This assignment uses FUSE, which allows you to implement a file system in user space by implementing the callback functions that thelibfuselibrary will call. The Tutorial 7 exercise should give you some practice using FUSE.We highly recommend starting there.
If you would like to learn more about FUSE:
- GitHub repository
- FUSE API header file for the version were using
- FUSE wiki
Contents
1 Logistics 2 1.1 Setting up your repository…………………………….. 2 1.2 Working in your repository……………………………. 2 1.3 Submitting changes to your repository………………………. 2
2 Assumptions, limits, and implementation details 3
3 Background 5 3.1 Disk images……………………………………. 5 3.2 Consistency checkers……………………………….. 5
4 Formatting 6 4.1 Automated running and testing………………………….. 6
5 Mounting 7 5.1 Understanding the starter code………………………….. 7 5.2 Recommended progression…………………………….. 8 5.3 Testing and debugging recommendations……………………… 9 5.4 Automated running and testing………………………….. 9
1 Logistics
Before starting to program, we highly recommend reading the entirety of this handout. This section describes how to acquire the starter files, compile code, and submit the assignment.
1.1 Setting up your repository
Your assignment is downloaded from, and submitted to, MarkUs usinggit. Login to MarkUs and navigate to CSC369. From there, navigate to a4, where you can see (among other things) the URL of the repository. Before cloning the repository, click Add Starter Files to Repository. Now you can clone the repository.
1.2 Working in your repository
Once you have cloned your repository you should find the starter files in the a4 subdirectory. Start by reading theREADME.mdin that subdirectory, which includes instructions on how to compile everything. The majority of your (graded) work should be done ina4/src/mkfs.c anda4/src/vsfs.c, which correspond to two different executables. Scripts are provided to run these executables in thea4/scripts directory (Sections 4.1 and 5.4). In addition, you can (and are encouraged to) add unit tests using Python ina4/tests(Section 5.4).
1.3 Submitting changes to your repository
You can find the files you have modified by running thegit statuscommand. You can commit modified files to your local repository. For example, assuming you are in thea4/srcdirectory and have saved changes tomkfs.c:
git add mkfs.c git commit -m "My useful commit message"
We suggest committing your changes frequently by rerunning the commands above (with different meaningful messages to the commit command), so that you can go back to see the changes you have made over time. Once you have tested your code, and committed it locally (check that by running git status), you cangit pushit back to MarkUs. You should also do this frequently. We collect and grade the last version pushed to MarkUs before the due date, up to the maximum late penalty. Please see the Syllabus and MarkUs for more details on the late penalty.
2 Assumptions, limits, and implementation details
We will not be testing your code under extreme circumstances so dont get carried away by thinking about corner cases. However, we do expect you to properly handle out of space conditions in your code. Any operation that cannot be completed because there are not enough free blocks or inodes must be cleanly aborted – no blocks or inodes can leak in the process. The simplest way to ensure this is to check that there is enough space to complete the operation before modifying any file system metadata. The formatting program (Section 4) must also check that the image file is large enough to accommodate the requested number of inodes.
Here are some hints and assumptions:
- The maximum number of inodes in the system is a parameter tomkfs.vsfs, the image size is also known to it, and the block size isVSFS_BLOCK_SIZE(4096 bytes – declared invsfs.h). Many parameters of your file system can be computed from these three values.
- We will not test your code on an image smaller than 64 KiB (16 blocks) with 4 inodes.
You should be able to fit the root directory and a non-empty file in an image of this size and
configuration. You shouldnt pre-allocate additional space for metadata (beyond the fixed meta-
data definced for VSFS, the space needed to store the inode table and the root directory) in your
mkfs.vsfsimplementation.Indirect blocks should only be allocated on demand, when a
file or directory grows large enough to need it.
- The maximum path component length isVSFS_NAME_MAX(252 bytes including the null termina- tor).
This value is chosen to fit the directory entry structure into 256 bytes (seevsfs.h). Names stored
in directory entries are null-terminated strings so that you can use standard C string functions
on them.
- The maximum full path length is_POSIX_PATH_MAX(4096 bytes including the null terminator).
This allows you to use fixed-size buffers for operations like splitting a path into a directory name
and a file name.
- The maximum file size is based on the number of direct block pointers in an inode (VSFS_NUM_DIRECT) and the number of block pointers in an indirect block (VSFS_BLOCK_SIZE / sizeof(vsfs_blk_t)).
- The number of directory entries is limited by the maximum number of directory entry data blocks (same as the limit on file blocks).
- The number of blocks in your file system is limited by the number of bits in a single VSFS block, since we use only 1 block for the data bitmap.
- You can assume that read and write operations are performed one block at a time.
Submitting changes to your repository 4
Eachreadandwritecall your file system receives will only cover a range within a single block.
Note: this does not apply totruncate- a single call needs to be able to extend or shrink a file
by an arbitrary number of blocks.
Sample disk configurations that must work include:
- 64KiB size and 4 inodes
- 64KiB size and 16 inodes
- 1MiB size and 64 inodes
- 128MiB size and 512 inodes
Other implementation notes:
- Although the . and .. directory entries can be manually listed by thevsfs_readdircallback (as in the starter code), you should create actual entries for these when you initialize the root directory inmkfs.
- The only timestamp you need to store for each file and directory is mtime (modification time)
- you dont need to store atime and ctime. You can use thetouchcommand to set the modification timestamp of a file or directory to current time.
- Any data and metadata blocks (other than the fixed metadata) should only be allocated on demand.
- Read and write I/O should be performed by reading/writing the virtual memory where the disk image is mmapd. It should NOT be performed byte-by-byte (which is very inefficient); use memcpy.
- Your implementation shouldnt use any floating point arithmetic. See the helper functions in util.h- if you need other, similar, functions (like floor), they can also be easily implemented using integer arithmetic.
3 Background
Unlike the passthrough file system of the tutorial exercise, your VSFS file system will operate on a disk image file. A disk image is an ordinary file that holds the content of a disk partition or storage device. We covered disk images in Lecture 18. In this assignment you work on two executables: mkfs.vsfs andvsfs. Themkfs.vsfsexecutable is responsible for formatting a disk image (Section 4). Thevsfs executable mounts a disk image to a mount point (Section 5), allowing the user to perform operations (likels).
3.1 Disk images
To allow you to test file system operations independently ofmkfs, we have provided some simple VSFS-formatted disk images at/u/csc369h/winter/pub/a4:
- vsfs-empty.disk – Small, empty file system (64 inodes, 1 MB size). Contains just root directory with . and .. entries.
- vsfs-1file.disk – Small file system (64 inodes, 1 MB size) containing a single small file (only 1 data block) in the root directory.
- vsfs-3file.disk – Medium file system (128 inodes, 16 MB size) containing 3 files (small – only direct blocks, medium – some indirect blocks, and maximum VSFS file size).
- vsfs-many.disk – Small file system (256 inodes, 2 MB size) containing lots of small files (root directory inode uses indirect block pointer).
- vsfs-maxfs.disk – Maximum size VSFS file system (512 inodes, 128 MB size). Contains just root directory with . and .. entries.
You will need to make your own copiesof these disk images to use them, since you will need to be able to write to them.
3.2 Consistency checkers
The namefsckcomes from the common tool for checking the consistency of file systems in Unix- like operating systems. Available on the teach.csmachines are two executables for checking the consistency of images. The first executable,fsck.mkfs, is useful in ensuring yourmkfsimplementation correctly formats the disk. The second executable,fsck.vsfs, is useful in ensuring that your code that was called during different file system operations has not corrupted the disk somehow.
4 Formatting
This part of the assignment does not need FUSE at all. You need to write part of themkfs.cprogram. To better understand how to complete this part of the assignment, make sure you have carefully read Chapter 40. You should also refer to Section 2 for simplifying assumptions you can make.
You will find it helpful to read the code to see how we access parts of the file system after usingmmapto map the entire disk image into the process virtual address space. Our goal is to support the following use case:
truncate -s
The truncate command will create a file (if it doesnt exist) and will set its size. Themkfs.vsfs executable (i.e., your executable) formats that file into a vsfs file system (i.e., a disk or a disk image). Once complete, we can check the consistency of file usingfsck.mkfs.
4.1 Automated running and testing
The process of creating a file, formatting it, and then checking its consistency has been automated for you. The scripta4/scripts/run_mkfs.shdoes each step, redirecting the output of these executables to files. For example, from the script:
Excerpt from runmkfs.sh
test_mkfs "mkfs_small" 1048576 64 # 1 MB
test_mkfs "mkfs_medium" 16777216 128 # 16 MB
Consider adding more calls totest_mkfsin this script, varying the file size and number of inodes. The disk images already provided to you (Section 3) may help give you some ideas. You can find the test_mkfs shell 代做 script代写”> bash function inutil.sh. To run the script itself, you must provide a single argument: the path to your build directory where you have compiled your project. For example, assuming you are in thea4directory and have built your project ina4/cmake-build-debug:
csc369$ ./scripts/run_mkfs.sh cmake-build-debug
- exec Creating the image file cmake-build-debug/test_mkfs/mkfs_small.disk Making a file system with 64 inodes. Checking consistency. Done. See cmake-build-debug/test_mkfs for all redirected output files. Creating the image file cmake-build-debug/test_mkfs/mkfs_medium.disk Making a file system with 128 inodes. Checking consistency. Done. See cmake-build-debug/test_mkfs for all redirected output files.
5 Mounting
Once you have a formatted vsfs disk image (one of ours, or your own) the next step is to mount your file system. Our goal is to support the following use case:./vsfs
The image file is the disk image formatted by mkfs.vsfs. Not only doesvsfsmount the disk image into the local file system, it also sets up callbacks and then callsfuse_mainso that FUSE can do its work. That is, after the file system is mounted, you can access it using standard tools (ls, cp, rm, etc.). To unmount the file system, run: fusermount -u
5.1 Understanding the starter code
You should read the starter code to understand how it fits together, and find useful helper functions. Here is a brief summary of the relevant files for mounting:
- vsfs.h- contains the Data structure definitions and constants needed for the file system. You may add other definitions or constants that you find useful, but you should not change the file system metadata. That is, do not add or modify fields in the superblock, inode, or direntry structures and do not change the existing definitions.
- vsfs.c- contains the program used to mount your file system. This includes the callback functions that will implement the underlying file system operations. Each function that you will implement is preceded by detailed comments and has a TODO in it. Please read this file carefully.
Note: It is very important to return the correct error codes (or 0 on success) from all the FUSE
callback functions, according to the Errors section in the comment above the function. The
FUSE library, the kernel, and the user-space tools used to access the file system all rely on these
return codes for correctness of operation.
Note: You will see many lines like (void)fs;. Their purpose is to prevent the compiler from warning
about unused variables. You should delete these lines as you make use of the variables.
- fs_ctx.handfs_ctx.c- Thefs_ctxstruct contains runtime state of your mounted file system. Any time you think you need a global variable, it should go in this struct instead. We have cached some useful global state in this structure already (e.g. pointers to superblock, bitmaps, and inode table), but you may find there is additional state that you want to add, instead of recomputing it on every operation.
- map.handmap.c- contain themap_filefunction used by vsfs and mkfs.vsfs to map the image file into memory and determine its size. You should not need to change anything here, or make any additional calls to themap_filefunction beyond what is in the starter code.
- options.handoptions.c- contain the code to parse command line arguments for the vsfs program. You should not need to change anything here.
Recommended progression 8
- util.h- contains some handy functions.
- bitmap.handbitmap.c- contain code to initialize bitmaps, and to allocate or free items tracked by the bitmaps. You will use these to allocate and free inodes and data blocks, so make sure you read the functions and understand how to use them. You may notice that thebitmap_alloc function can be slow, since it always starts the search for a 0 bit from the start of the bitmap. You are free to improve on this if you wish, but you do not need to.
5.2 Recommended progression
There are a lot of places where you can start for mounting in terms of writing code. However, there is an incremental order of operations that makes it much easier to test things. To help, we have already implementedvsfs_statfsbecause it is very useful for testing. Next, we recommend you follow this order:
- Implementvsfs_getattr. You have probably seen from the tutorial exercise that FUSE calls getattra lot. Implementing this function is the key to the rest of the operations.
You will want to write a helper function that takes a path and returns a pointer to the inode (or
the inode number) for the last component in the path. Remember (Section 2) that you only need
to handle paths that are of the form / or /somefile - all paths are absolute and there are no
subdirectories in our vsfs file systems.
- Implement vsfs_readdir. Once done correctly, you can runls -la on the root directory when the root directory entries fit within a single data block. You should be able to mount vsfs-empty.disk, vsfs-maxfs.disk, vsfs-1file.diskandvsfs-3file.diskand list their root directories on completion of this step.
- Add the ability to create empty files by implementingvsfs_create. On completion of this step, you should be able to mountvsfs-empty.diskand use touch to create a new empty file. The new file should be visible and the mode and timestamps should be appropriate when youls -l on the root directory.
- Add the ability to write to, and read from, small files. First focus on the case where the data is stored in a single data block. Then the case where the data can be stored using only the direct block pointers in the inode. Implementvsfs_truncatefirst, thenvsfs_writeandvsfs_read.
- Add the ability to remove small files (where the file data uses only the direct block pointer in the inode).
- Enhance your implementation ofvsfs_readdirto list large directories, where the directory in- odes indirect block is needed to read all of the directory data blocks. You should be able to mountvsfs-many.diskand list its root directory on completion of this step.
- Enhance your implementations ofvsfs_truncate,vsfs_write,vsfs_read, andvsfs_unlinkto support large files, where the indirect block in the files inode is used to locate some of the files data blocks.
While making changes and supporting more operations, here are some tips:
- Remember to update fields in the superblock (e.g. free_inodes,free_blocks) as you operate on the file system.
Testing and debugging recommendations 9
- Check that there is enough spacebeforemaking any changes to the file system. This will save you from having to roll back changes if you discover that an operation cannot be completed due to lack of space.
- Comment your code well. It will help you keep track of what is implemented and your under- standing of how things work. Refactor your code during development (not after) and keep your functions short and well-structured.
5.3 Testing and debugging recommendations
You can use standard Unix tools to manipulate directories and files in a mounted vsfs image in order to test your implementation. System call tracing withstracecan help understand what syscalls they invoke to access the file system. You can, in general, use the behaviour of the host file system (ext4) as a reference – yourvsfsshould have the same observable behaviour for operations thatvsfsneeds to support.
You will find it useful to runvsfsundergdb:gdb –args ./vsfs
You might also find it useful to view the binary contents of your vsfs image files using xxd. See man 1 xxdfor documentation.
To avoid errors when mounting the file system, make sure that the mount point is not in use (e.g., by a previous vsfs mount that didnt finish cleanly). Iffusermountfails to unmount because the mount point directory is busy, you can use thelsofcommand (seeman lsof) to identify the process that keeps it open. One common error message you might see when running operations on the mounted file system is transport endpoint is not connected. This error usually means that the file system is still mounted, but thevsfsprogram has terminated (e.g. crashed). In this case you need to manually unmount it withfusermount.
One of the most common errors you might see at the early stages of the implementation isls -la reporting an I/O error and displaying ??? entries. This error usually means that yourgetattr callback returns invalid data in the stat structure and/or an invalid return value.
You can also write your own C programs that invoke relevant syscalls directly, or use Python unit tests (Section 5.4). In order to test reads and writes at an offset, you can either use thetailcommand (its -coption; seeman 1 tail). Or write your own C programs that usepreadandpwrite.
5.4 Automated running and testing
The process of mounting an image, running operations, and unmounting (and, finally, checking the con- sistency of the image) has been automated for you in two ways. The scripta4/scripts/run_vsfs.sh does each step, redirecting the output of these executables to files. For example, from the script:
Automated running and testing 10
Excerpt from runvsfs.sh
test_vsfs "vsfs-empty" "$CSC369_A4_DISK_DIR/vsfs-empty.disk" 64 "$TESTS_DIR"
test_vsfs "vsfs-1file" "$CSC369_A4_DISK_DIR/vsfs-1file.disk" 64 "$TESTS_DIR"
However, the script does not know which operations to try on the file system. Instead, it runs pyteston thea4/testsdirectory, providing some useful command line arguments. You can find thetest_vsfsbash function inscripts/util.sh(find the line that begins withpython3). Inspect a4/tests/conftest.pyfor a better understanding of whatpytestis provided by therun_vsfs.sh script. Then take a look attest_statvfs.py, which includes test cases for validating the correctness of thestatfsoperation.
To run the script itself, you must provide two arguments: the path to your build directory and the tests directory. For example, assuming you are in thea4directory and have built your project in a4/cmake-build-debug:
csc369$ ./scripts/run_vsfs.sh cmake-build-debug/ tests/
- exec Starting vsfs-empty test Mounting /u/csc369h/winter/pub/a4/vsfs-empty.disk at /tmp/mbadr Running pytest tests in tests/. Unmounting /tmp/mbadr Checking consistency. Done. See cmake-build-debug//test_vsfs for all redirected output files. …
There are several other files ina4/testsfor testing different operations. However, they are (mostly) empty skeletons. You can add tests to the existing files, and we have provided some hints for you for some operations. If you are adding a new test to a file, remember that the function must have the prefixtest_. If you are adding a new file to test a different operation, remember that the file must also have the prefixtest_.
Please note that your test cases are not assessed. However, reading, understanding, and writing test cases is incredibly important for this assignment. As a result, we encourage you toshare your tests on Piazza.To do so, create a new Piazza post with a subject that contains the name of the file (e.g., marsbars testreaddir.py). Then, share the contents of that file using the Markdown editor and backticks (dont use an attachment):
# paste your code here
Other students (and your instructor) can now see your test cases, reason about their validity, and make suggestions. If you make changes that you want to share,edit your original post. Students are free to use each others test cases. Outside of Python test cases, however, no sharing of files is allowed. If you have a question or doubt about academic integrity, please ask your instructor.