2021/7/25 COMP 3430 - Operating systems
https://universityofmanitoba.desire2learn.com/content/enforced3/436172-1104.1105.1106.1495.1724.202150.XL/assignments/assignment4/assig… 1/11
COMP 3430 - Operating systems
Assignment 4
Franklin Bristow
Summer 2021
Description
General submission requirements
Question 1 - Implementing a File System reader
exFAT documentation
Volumes
Required commands
info list get
Implementation notes
Sectors ↔︎ clusters
Root directory and cluster number offsets
Directory entries
Unicode and ASCII
Binary files
Evaluation
Implementation
Submitting your assignment
General Advice
Description
For assignment 4, we’re looking for you to be able to write software that works
with a file system.
Specifically, you’re going to be writing code that can read an exFAT file system,
and extract files from that file system.
Listen
2021/7/25 COMP 3430 - Operating systems
https://universityofmanitoba.desire2learn.com/content/enforced3/436172-1104.1105.1106.1495.1724.202150.XL/assignments/assignment4/assig… 2/11
Assignment 4 is due Friday, August 13th
, 2021 at 4:30pm CDT (Winnipeg time).
General submission requirements
Submissions that violate any of the following will not be evaluated (i.e., you will
receive a score of 0 for the assignment):
All solutions must be written in C. No other languages are accepted.
All solutions must include a working Makefile.
Forget how to make a Makefile? Never knew how to make a Makefile?
Thankfully, you can go to https://makefiletutorial.com and find some
very easy to use basic examples.
Your Makefile should contain a clean rule. When
is run in your directory, all the temporary files, including the executable
should be removed (e.g., rm -f my_prog).
All solutions must be compiled by issuing the command make in the directory
containing the Makefile. No other build commands are acceptable, even if
documented in the README.md.
All solutions must include a Markdown-formatted README.md file that
minimally describes how to run your submission.
Forget how to make a README.md? Never knew how to make README.md?
Thankfully, you can go to https://readme.so/ and build a nice,
Markdown-formatted README.md with a nice preview and some handy
buttons to help you build it.
All solutions must run to successful completion. Premature termination for
any reason (no obvious output, Segmentation Fault, Bus Error, etc.) is
considered to be a solution implementation that does not run.
Code that runs for an unreasonably long time (e.g., > 30 seconds) without
terminating is also considered to be a solution implementation that does not
run.
All solutions must compile. Code that does not compile will not be evaluated.
Programs must produce no errors when compiled with all of the flags
make clean
2021/7/25 COMP 3430 - Operating systems
https://universityofmanitoba.desire2learn.com/content/enforced3/436172-1104.1105.1106.1495.1724.202150.XL/assignments/assignment4/assig… 3/11 -Wall -Wpedantic -Wextra -Werror
Note that -Werror prevents your code from being compiled when warnings
are present.
If all of these flags are not in your Makefile, your submission will be treated
as though it does not compile.
Your code must compile and run on a machine on aviary.cs.umanitoba.ca.
No late submissions will be accepted. The assignment deadline is enforced
electronically. Submissions will not be accepted by e-mail.
Reminder: All submitted code will be evaluated using an automated similarity
testing tool, alongside commonly available online solutions for problems.
Question 1 - Implementing a File
System reader
In this question, you will write a program that reads an exFAT-formatted volume.
For this assignment you are provided with a couple of volume images, but you are
encouraged to read a USB flash, SDHC, or SDXC drive as a raw device (e.g.,
/dev/sda3), provided that you have physical access to a Linux machine.
exFAT documentation
The general structure of the exFAT file system was discussed in class (lecture 16),
so you should take the time to review this general structure if you haven’t already.
You should also open Microsoft’s exFAT file system specification. This document
comprehensively describes the exFAT format, and this should be your universal
source of truth for exFAT.
Volumes
Two volumes have been prepared for you to use to test your program. The two
volumes are distributed as a packaged zip file that contains a README.md
describing the two volumes, a text file with a list of all files that are in the
volumes, and the two volumes themselves.
The graders may not use this same pair of volumes to evaluate your work.
2021/7/25 COMP 3430 - Operating systems
https://universityofmanitoba.desire2learn.com/content/enforced3/436172-1104.1105.1106.1495.1724.202150.XL/assignments/assignment4/assig… 4/11
Required commands
You should implement 3 commands that are all part of the same program: info,
list, and get. info
The info command will print information about the volume. The command,
assuming your program is named exfat, would be
./exfat imagename info
Print out the following:
Volume label.
Volume serial number.
Free space on the volume in KB.
The cluster size, both in sectors and in bytes OR KB.
Note: 1KB ↔︎ 1024 bytes.
Volume label
The volume label is encoded as a directory entry in the root directory. You can
find information about the volume label in section 7.3 Volume Label Directory
Entry.
The Volume label is a Unicode-formatted string, please see Unicode and ASCII at
the bottom for some additional information.
Volume serial number
The volume serial number is in the boot sector, and you can find information
about it both in sections 3.1 Main and Backup Boot Sector Sub-regions, and in
section 3.1.11 VolumeSerialNumber Field.
You should print this out as a numeric value (i.e., "%u", explicitly unsigned).
Free space
exFAT uses allocation structures (bitmaps) to represent used and unused
clusters. You can use these allocation bitmaps to calculate the free space in the
volume (the number of unset/0 bits is the number of unallocated clusters).
If you would like a challenge for this, try to figure out how to use the popcount
instruction to help you calculate this value.
2021/7/25 COMP 3430 - Operating systems
https://universityofmanitoba.desire2learn.com/content/enforced3/436172-1104.1105.1106.1495.1724.202150.XL/assignments/assignment4/assig… 5/11
The allocation bitmap is encoded as a directory entry in the root directory. You
can find information about the allocation bitmap in section 7.1 Allocation Bitmap
Directory Entry.
Cluster size
The cluster size in sectors and the sector size in bytes can be found in the boot
sector. You can find more information about both of these fields in 3.1 Main and
Backup Boot Sector Sub-regions.
Note: These fields are called ___Shift because you can use the left shift operator
(<<) to quickly compute powers of two:
list
The list command will recursively print all files and directories in the volume.
The output should look roughly like the output from tree (try running tree $YOUR_A2 on aviary.cs.umanitoba.ca).
You explicitly do not have to print out fancy Extended ASCII characters, but
instead can use the - symbol to denote depth, where the number of - characters
indicates the depth of the file/folder.
The command, assuming your program is named exfat, would be
./exfat imagename list
Output should look something like:
In this example, the root directory contains references to two files: file.txt and
file2.txt, and one directory: folder. The folder directory contains a reference
to one folder: folder2. The folder2 directory contains a reference to one folder:
folder3. The folder3 directory contains a reference to one file: thefile.txt. uint8_t x = 0x1 << 3; // 2^3 -> 8 egret.cs.umanitoba.ca 101% ./exfat image list File: file.txt Directory: folder - Directory: folder2 -- Directory: folder3 --- File: thefile.txt File: file2.txt
2021/7/25 COMP 3430 - Operating systems
https://universityofmanitoba.desire2learn.com/content/enforced3/436172-1104.1105.1106.1495.1724.202150.XL/assignments/assignment4/assig… 6/11
Order of files is not important (you don’t have to print all files before directories,
for example). The recommended strategy here is to just print out files and folders
in the same order that they are in in terms of the sequence of DirectoryEntry in
the folders. Likewise, the sequence of directories that you follow is also not
important. You’re going to have to do this recursively, but it’s up to you if you
want to do a breadth-first or a depth-first implementation.
get
The get command will extract a complete file from the volume. The command,
assuming your program is named exfat would be
./exfat imagename get path/to/file.txt
The path you pass to your program is assumed to be an absolute path (it starts at
the root directory), even if it doesn’t have a leading /.
The path you pass to your program should be written out as a file to the same
directory as your program with the same name as the file in the exFAT image. If
the example above is executed, you should write the contents of the file at
path/to/file.txt from the disk image to a file named file.txt in the same
directory as the ./exfat binary executable.
Implementation notes
The exFAT file system specification is fairly comprehensive and generally very
good, but some parts of the documentation are not straightforward. Additionally,
exFAT explicitly supports Unicode characters, and while that’s an excellent
property of a file system, working with Unicode characters in C isn’t a great
experience.
Below is some additional information that you can use to help guide you through
working with exFAT.
Sectors ↔︎ clusters
The first chunk of the file system (3.1 Main and Backup Boot Sector Sub-regions)
are organized explicitly by sectors, regardless of the number of sectors per
cluster.
The FATs are also organized in sectors, but a single FAT may span multiple
sectors.
2021/7/25 COMP 3430 - Operating systems
https://universityofmanitoba.desire2learn.com/content/enforced3/436172-1104.1105.1106.1495.1724.202150.XL/assignments/assignment4/assig… 7/11
The data heap itself is organized by clusters, which may or may not be the same
size as a sector. Make sure that you’re using the right units in the right regions!
You should consider writing a utility function or macro that quickly converts
from cluster number to bytes or from sector number to bytes.
Root directory and cluster number offsets
An easily overlooked statement in 5.1 Cluster Heap Sub-region is
Importantly, the first cluster of the Cluster Heap has index two, which
directly corresponds to the index of FatEntry[2].
That effectively means that cluster indexing is effectively a 2-based array (what
kind of a maniac came up with this?). This means that if, for example, the value
in the boot sector for the root directory is 5, then the root directory is actually
stored starting at cluster number 3 (5 − 2 = 3).
Directory entries
Files, directories, and some FS metadata are encoded as directory entries in the
data heap region. The description of how to interpret types of directory entries is
not great (what the heck does “Benign primary” even mean???).
An admittedly spammy looking page selling some software called “Active
UNDELETE” has a nice list of the exFAT directory entry types that includes
actual numeric values that you can use for comparing against the EntryType field
in the directory entry.
The directory entries that correspond to one single file will exist as three
separate, but sequential/contiguous directory entries:
1. A file directory entry.
2. Exactly 1 stream extension directory entry.
3. At least 1 file name directory entry.
You need to read all of those directory entries to be able to get the name of the file
that you’re looking for.
Unicode and ASCII
Many fields in this file system are defined as 16-bit Unicode strings. That
means that characters are 16 bits wide instead of 8 bits wide. Provided that your
Unicode string consists only of ASCII characters (so unfortunately اللغة أتحدث ال العربية, 沒有中文, ਕੋਈ ਪੰਜਾਬੀ ਨਹੀਂ, and no emoji 🦖), you can trivially convert a
Unicode string into a regular C string by stripping off the top 8 bits:
2021/7/25 COMP 3430 - Operating systems
https://universityofmanitoba.desire2learn.com/content/enforced3/436172-1104.1105.1106.1495.1724.202150.XL/assignments/assignment4/assig… 8/11 /*** Convert a Unicode-formatted string containing only ASCII characters * into a regular ASCII-formatted string (16 bit chars to 8 bit * chars). ** NOTE: this function does a heap allocation for the string it * returns, caller is responsible for `free`-ing the allocation * when necessary. ** uint16_t *unicode_string: the Unicode-formatted string to be * converted. * uint8_t length: the length of the Unicode-formatted string (in * characters). ** returns: a heap allocated ASCII-formatted string. */ static char *unicode2ascii( uint16_t *unicode_string, uint8_t length ) { assert( unicode_string != NULL ); assert( length > 0 ); char *ascii_string = NULL; if ( unicode_string != NULL && length > 0 ) { // +1 for a NULL terminator ascii_string = calloc( sizeof(char), length + 1); if ( ascii_string ) { // strip the top 8 bits from every character in the // unicode string for ( uint8_t i = 0 ; i < length; i++ ) { ascii_string[i] = (char) unicode_string[i]; }// stick a null terminator at the end of the string. ascii_string[length] = '\0'; } }return ascii_string; }
2021/7/25 COMP 3430 - Operating systems
https://universityofmanitoba.desire2learn.com/content/enforced3/436172-1104.1105.1106.1495.1724.202150.XL/assignments/assignment4/assig… 9/11
You are explicitly permitted to use this code fragment in your submission.
Binary files
Remember that the volumes that have been shared with you are binary files. With
that in mind, you can (and should!) use all of the same tools that you used for
parsing an ELF-formatted binary file in A1. As a brief reminder, those tools
include
The uintX_t family of integers from stdint.h.
The hexdump command-line tool.
In assignment 1 we were working with binary files where the layout of the
structures in the file conditionally changed based on the type of file that it was
(e.g., 32-bit vs 64-bit files). The exFAT file system does not have any structures
that are sized conditionally. That means that you can actually use (and are
recommended to use) the “read the entire struct” strategy. Remember: this
means that you need to use preprocessor directives (#pragma pack) to make sure
that the compiler doesn’t change the layout of your struct.
Evaluation
Implementation
5 points are awarded for code quality and design:
Level Description
0
The code is very poor quality (e.g., no comments at all, no functions,
poor naming conventions for variables, etc).
1–3
The code is low quality, while some coding standards are applied, their
uses is inconsistent (e.g., inconsistent use of comments, some
functions but functions might do too much, code is repeated that
should be in a function, etc).
This is the maximum level you can earn if the implementation of your
program is substantially incomplete.
4–5
The code is high quality, coding standards are applied consistently
throughout the code base.
Each command (info, list, and get) will be graded out of 5 points, for a total of
15 points (5 × 3):
2021/7/25 COMP 3430 - Operating systems
https://universityofmanitoba.desire2learn.com/content/enforced3/436172-1104.1105.1106.1495.1724.202150.XL/assignments/assignment4/assi… 10/11
Level Level Criteria Criteria
0
No attempt is made to answer this question or code does not run or
compile.
1–2
The submitted code is substantially incomplete. Many of the
requirements for the assignment are not fully implemented.
3–4
The submitted code is substantially complete, but some minor parts
are still missing.
5
The submitted code is complete, all major functionality works as
expected.
Submitting your assignment
Submissions will be made using the handin command available on all CS UNIX
systems.
You should be submitting at least the following files:
A Makefile.
A README.md that includes a summary of how to compile and run your
program (compiling should be “run make”, but you should explicitly tell the
grader how to run your program, e.g., what arguments to pass to the program
on the command line).
Your solution for question 1 (probably just 1 .c file).
Please do not include any disk images in your submission.
If your files are in a folder named my_a4, you would run the command:
If you need more information, you can see man handin.
General Advice
Here’s some general advice that you can choose to follow or ignore:
1. The debugger is your best friend. Don’t even start trying to solve this
problem until you’re comfortable with a debugger (either lldb or gdb). The
first question I’m going to ask you when you come to ask me for help is:
handin 3430 a4 my_a4
2021/7/25 COMP 3430 - Operating systems
https://universityofmanitoba.desire2learn.com/content/enforced3/436172-1104.1105.1106.1495.1724.202150.XL/assignments/assignment4/assi… 11/11
“Have you tried running it through the debugger yet?” If you answer “no”, I’ll
ask you (politely!) to do that first, then come back.
2. Source control is your second best friend. The department hosts an instance
of GitLab that you can use to store private projects. You’re also welcome to
use private repositories on GitHub.