CS202 Operating Systems - Lab 4: File Recovery
FAT has been around for nearly 50 years. Because of its simplicity, it is the most widely compatible le system. Although recent computers have adopted newer le systems, FAT32 (and its variant, exFAT) is still dominant in SD cards and USB ash drives due to its compatibility.
Have you ever accidentally deleted a le? Do you know that it could be recovered? In this lab, you will build a FAT32 le recovery tool called Need You to Undelete my FILE, or for short.
Through this lab, you will:
Learn the internals of the FAT32 le system.
Learn how to access and recover les from a raw disk.
Get a better understanding of key le system concepts.
Be a better C programmer. Learn how to write code that manipulates
data at the byte level and understand the alignment issue.
In this lab, you will work on the data stored in the FAT32 le system directly, without the OS le system support. You will implement a tool that recovers a deleted le specied by the user.
For simplicity, you can assume that the deleted le is in the root directory. Therefore, you don’t need to search subdirectories.
Before going through the details of this lab, let’s rst create a FAT32 disk image. Follow these steps:
On Linux, is a special le that provides as many \0 as are read from it. The dd command performs low-level copying of raw data. Therefore, you can use it to generate an arbitrary-size le full of zeros.
For example, to create a 256KB empty le named :
Read for its usage. You will use this le as the disk image.
You can use the command to create a FAT32 le system. The most basic usage is:
(You can ignore the warning of not enough clusters.) You can specify a variety of options. For example:
Here are the meanings of each option:
-F : type of FAT (FAT12, FAT16, or FAT32).
/dev/zero
fat32.disk
[root@... cs202]# dd if=/dev/zero of=fat32.disk bs=256k count=1
man dd
mkfs.fat
[root@... cs202]# mkfs.fat -F 32 fat32.disk
[root@... cs202]# mkfs.fat -F 32 -f 2 -S 512 -s 1 -R 32 fat32.disk
https://cs.nyu.edu/courses/fall24/CSCI-UA.0202-001/nyufile
2/18
11/15/24, 7:22 PM Lab 4: File Recovery
-f : number of FATs.
-S : number of bytes per sector.
-s : number of sectors per cluster.
-R : number of reserved sectors.
The command can check and repair FAT le systems. You can invoke it with -v to see the FAT details. For example:
You can see that there are 2 FATs, 512 bytes per sector, 512 bytes per cluster, and 32 reserved sectors. These numbers match our specied options in Step 2. You can try different options yourself.
fsck.fat
[root@... cs202]# fsck.fat -v fat32.disk
fsck.fat 4.1 (2017-01-24)
Checking we can access the last sector of the filesystem
Warning: Filesystem is FAT32 according to fat_length and fat32_length fields,
but has only 472 clusters, less than the required minimum of 65525.
This may lead to problems on some systems.
Boot sector contents:
System ID "mkfs.fat"
Media byte 0xf8 (hard disk)
512 bytes per logical sector
512 bytes per cluster
32 reserved sectors
First FAT starts at byte 16384 (sector 32)
2 FATs, 32 bit entries
2048 bytes per FAT (= 4 sectors)
Root directory start at cluster 2 (arbitrary size)
Data area starts at byte 20480 (sector 40)
472 data clusters (241664 bytes)
32 sectors/track, 64 heads
0 hidden sectors
512 sectors total
Checking for unused clusters.
Checking free cluster summary.
fat32.disk: 0 files, 1/472 clustersYou can use the command to mount a le system to a mount point. The mount point can be any empty directory. For example, you can create one at /mnt/disk :
Then, you can mount at that mount point:
After the le system is mounted, you can do whatever you like on it, such as creating les, editing les, or deleting les. In order to avoid the hassle of having long lenames in your directory entries, it is recommended that you use only 8.3 lenames, which means:
The lename contains at most eight characters, followed optionally by a
. andatmostthreemorecharacters.
The lename contains only uppercase letters, numbers, and the
following special characters: .
For example, you can create a le named :
For the purpose of this lab, after you write anything to the disk, make sure to ush the le system cache using the sync command:
mount
[root@... cs202]# mkdir /mnt/disk
fat32.disk
[root@... cs202]# mount fat32.disk /mnt/disk! # $ % &' ( )- @^ _ `{ }~
HELLO.TXT
[root@... cs202]# echo "Hello, world." > /mnt/disk/HELLO.TXT
[root@... cs202]# mkdir /mnt/disk/DIR
[root@... cs202]# touch /mnt/disk/EMPTY(Otherwise, if you create a le and immediately delete it, the le may not be written to the disk at all and is unrecoverable.)
When you nish playing with the le system, you can unmount it:
You can examine the le system using the xxd command. You can specify a range using the -s (starting offset) and -l (length) options.
For example, to examine the root directory:
(It’s normal that the bytes containing timestamps are different from the example above.)
To examine the contents of :
[root@... cs202]# umount /mnt/disk
metsys el eht enimaxe :7 petS
metsys el eht tnuomnu :6 petS
[root@... cs202]# xxd -s 20480 -l 96 fat32.disk
00005000: 4845 4c4c 4f20 2020 5458 5420 0000 0000 HELLO TXT ....
00005010: 6e53 6e53 0000 0000 6e53 0300 0e00 0000 nSnS....nS......
00005020: 4449 5220 2020 2020 2020 2010 0000 0000 DIR .....
00005030: 6e53 6e53 0000 0000 6e53 0400 0000 0000 nSnS....nS......
00005040: 454d 5054 5920 2020 2020 2020 0000 0000 EMPTY ....
00005050: 6e53 6e53 0000 0000 6e53 0000 0000 0000 nSnS....nS......
HELLO.TXT
[root@... cs202]# xxd -s 20992 -l 14 fat32.disk
0005200: 4865 6c6c 6f2c 2077 6f72 6c64 2e0a Hello, world..
[root@... cs202]# syncNote that the offsets may vary depending on how the le system is formatted.
Important: before running your program, please make sure that your FAT32 disk is unmounted.
There are several ways to invoke your program. Here is its usage:
The rst argument is the lename of the disk image. After that, the options can be one of the following:
-i -l
You need to check if the command-line arguments are valid. If not, your program should print the above usage information verbatim and exit.
If your program is invoked with option -i , it should print the following information about the FAT32 le system:
nyufile
nyufile
[root@... cs202]# ./nyufile
Usage: ./nyufile disk <options>
-i Print the file system information.
-l List the root directory.
-r filename [-s sha1] Recover a contiguous file.
-R filename -s sha1 Recover a possibly non-contiguous file.
-r filename
-r filename -s sha1
-R filename -s sha1nyufile
Number of FATs;
Number of bytes per sector;
Number of sectors per cluster;
Number of reserved sectors.
Your output should be in the following format:
For all milestones, you can assume that
is invoked while the disk is
unmounted.
If your program is invoked with option -l , it should list all valid
entries in the root directory with the following information:
Filename. Similar to /bin/ls -p , if the entry is a directory, you should append a / indicator.
File size if the entry is a le (not a directory). Starting cluster if the entry is not an empty le.
You should also print the total number of entries at the end. Your output should be in the following format:
Here are a few assumptions:
[root@... cs202]# ./nyufile fat32.disk -i
Number of FATs = 2
Number of bytes per sector = 512
Number of sectors per cluster = 1
Number of reserved sectors = 32
nyufile
nyufile
[root@... cs202]# ./nyufile fat32.disk -l
HELLO.TXT (size = 14, starting cluster = 3)
DIR/ (starting cluster = 4)
EMPTY (size = 0)
Total number of entries = 3You should not list entries marked as deleted.
You don’t need to print the details inside subdirectories.
For all milestones, there will be no long lename (LFN) entries. (If you
have accidentally created LFN entries when you test your program,
don’t worry. You can just skip the LFN entries and print only the 8.3
lename entries.)
Any le or directory, including the root directory, may span more than
one cluster.
There may be empty les.
If your program is invoked with option , it should recover the deleted le with the specied name. The workow is better illustrated through an example:
For all milestones, you only need to recover regular les (including empty les, but not directory les) in the root directory. When the le is successfully recovered, your program should print
(replace with the actual le
name).
For all milestones, you can assume that no other les or directories are created or modied since the deletion of the target le. However, multiple les may be deleted.
Besides, for all milestones, you don’t need to update the structure because most operating systems don’t care about it.
filename: successfully recovered
filename
FSINFO
[root@... cs202]# mount fat32.disk /mnt/disk
[root@... cs202]# ls -p /mnt/disk
DIR/ EMPTY HELLO.TXT
[root@... cs202]# cat /mnt/disk/HELLO.TXT
Hello, world.
[root@... cs202]# rm /mnt/disk/HELLO.TXT
rm: remove regular file '/mnt/disk/HELLO.TXT'? y
[root@... cs202]# ls -p /mnt/disk
DIR/ EMPTY
[root@... cs202]# umount /mnt/disk
[root@... cs202]# ./nyufile fat32.disk -l
DIR/ (starting cluster = 4)
EMPTY (size = 0)
Total number of entries = 2
[root@... cs202]# ./nyufile fat32.disk -r HELLO
HELLO: file not found
[root@... cs202]# ./nyufile fat32.disk -r HELLO.TXT
HELLO.TXT: successfully recovered
[root@... cs202]# ./nyufile fat32.disk -l
HELLO.TXT (size = 14, starting cluster = 3)
DIR/ (starting cluster = 4)
EMPTY (size = 0)
Total number of entries = 3
[root@... cs202]# mount fat32.disk /mnt/disk
[root@... cs202]# ls -p /mnt/disk
DIR/ EMPTY HELLO.TXT
[root@... cs202]# cat /mnt/disk/HELLO.TXT
Hello, world.Here are a few assumptions specically for Milestone 4:
The size of the deleted le is no more than the size of a cluster.
At most one deleted directory entry matches the given lename. If no
such entry exists, your program should print
(replace with the actual le name).
Now, you will recover a le that is larger than one cluster. Nevertheless, for Milestone 5, you can assume that such a le is allocated contiguously. You can continue to assume that at most one deleted directory entry matches the given lename. If no such entry exists, your program should print
(replace with the actual le name).
In Milestones 4 and 5, you assumed that at most one deleted directory entry matches the given lename. However, multiple les whose names differ only in the rst character would end up having the same name when deleted. Therefore, you may encounter more than one deleted directory entry matching the given lename. When that happens, your program should print (replace with the actual le name) and abort.
This scenario is illustrated in the following example:
filename: file not found
filename
filename: file not found
filename
filename: multiple candidates found
filename
[root@... cs202]# mount fat32.disk /mnt/disk
[root@... cs202]# echo "My last name is Tang." > /mnt/disk/TANG.TXT
[root@... cs202]# echo "My first name is Yang." > /mnt/disk/YANG.TXT
[root@... cs202]# sync
[root@... cs202]# rm /mnt/disk/TANG.TXT /mnt/disk/YANG.TXT
rm: remove regular file '/mnt/disk/TANG.TXT'? y
rm: remove regular file '/mnt/disk/YANG.TXT'? y
[root@... cs202]# umount /mnt/disk
[root@... cs202]# ./nyufile fat32.disk -r TANG.TXT
TANG.TXT: multiple candidates foundhsah 1-AHS
To solve the aforementioned ambiguity, the user can provide a SHA-1 hash
via command-line option to help identify which deleted directory
entry should be the target le.
In short, a SHA-1 hash is a 160-bit ngerprint of a le, often represented as 40 hexadecimal digits. For the purpose of this lab, you can assume that identical les always have the same SHA-1 hash, and different les always have vastly different SHA-1 hashes. Therefore, even if multiple candidates are found during recovery, at most one will match the given SHA-1 hash.
This scenario is illustrated in the following example:
When the le is successfully recovered with SHA-1, your program should print (replace with the actual le name).
Note that you can use the command to compute the SHA-1 hash of a le:
c
-s sha1
[root@... cs202]# ./nyufile fat32.disk -r TANG.TXT -s c91761a2cc1562d36585614
TANG.TXT: successfully recovered with SHA-1
[root@... cs202]# ./nyufile fat32.disk -l
HELLO.TXT (size = 14, starting cluster = 3)
DIR/ (starting cluster = 4)
EMPTY (size = 0)
TANG.TXT (size = 22, starting cluster = 5)
Total number of entries = 4
|
|||
filename: successfully recovered with SHA-1
filename
sha1sum
[root@... cs202]# sha1sum /mnt/disk/TANG.TXT
c91761a2cc1562d36585614c8c680ecf5712e875 /mnt/disk/TANG.TXTAlso note that it is possible that the le is empty or occupies only one cluster. The SHA-1 hash for an empty le is
.
If no such le matches the given SHA-1 hash, your program should print (replace with the actual le name). For
example:
The OpenSSL library provides a function , which computes the SHA- 1 hash of and stores the result in :
You need to add the linker option to link with the OpenSSL library.
Finally, the clusters of a le are no longer assumed to be contiguous. You have to try every permutation of unallocated clusters on the le system in order to nd the one that matches the SHA-1 hash.
The command-line option is . The SHA-1 hash must be given.
Note that it is possible that the le is empty or occupies only one cluster. If so, -R behaves the same as -r , as described in Milestone 7.
7
da39a3ee5e6b4b0d3255bfef95601890afd80709
filename: file not found
filename
[root@... cs202]# ./nyufile fat32.disk -r TANG.TXT -s 0123456789abcdef0123456
TANG.TXT: file not found
|
|||
SHA1()
d[0...n-1]
md[0...SHA_DIGEST_LENGTH-1]
#include <openssl/sha.h>
#define SHA_DIGEST_LENGTH 20
unsigned char *SHA1(const unsigned char *d, size_t n, unsigned char *md);
-lcrypto
-R filename -s sha1
For Milestone 8, you can assume that the entire le is within the rst 20 clusters, and the le content occupies no more than 5 clusters, so a brute- force search is feasible.
If you cannot nd a le that matches the given SHA-1 hash, your program should print (replace with the actual le name).
For your convenience, here are some data structures that you can copy and paste. Please refer to the lecture slides and FAT: General Overview of On- Disk Format for details on the FAT32 le system layout.
filename: file not found
filename
rotces tooB
|
#pragma pack(push,1) typedef struct BootEntry { unsigned char BS_jmpBoot[3]; unsigned char BS_OEMName[8]; unsigned short BPB_BytsPerSec; unsigned char BPB_SecPerClus; unsigned short BPB_RsvdSecCnt; unsigned char BPB_NumFATs; unsigned short BPB_RootEntCnt; unsigned short BPB_TotSec16; unsigned char BPB_Media; unsigned short BPB_FATSz16; unsigned short BPB_SecPerTrk; unsigned short BPB_NumHeads; // Assembly instruction to jump to boot c
// OEM Name in ASCII
// Bytes per sector. Allowed values inclu
// Sectors per cluster (data unit). Allow
// Size in sectors of the reserved area
// Number of FATs
// Maximum number of files in the root di
// 16-bit value of number of sectors in f
// Media type
// 16-bit size in sectors of each FAT for
// Sectors per track of storage device
// Number of heads in storage device
// Number of sectors before the start of
// 32-bit value of number of sectors in f
// 32-bit size in sectors of one FAT
// A flag for FAT
// The major and minor version number
// Cluster where the root directory can b
// Sector where FSINFO structure can be f
// Sector where backup copy of boot secto
unsigned int } BootEntry; #pragma pack(pop) BPB_HiddSec; BPB_TotSec32; BPB_FATSz32; unsigned char BS_DrvNum; // BIOS INT13h drive number
// Not used
// Extended boot signature to identify if
// Volume serial number
// Volume label in ASCII. User defines wh
|
|||
o
d e
r i
p i
e o r
e
https://cs.nyu.edu/courses/fall24/CSCI-UA.0202-001/nyufile
14/18
11/15/24, 7:22 PM Lab 4: File Recovery
#pragma pack(push,1) typedef struct DirEntry {
unsigned char DIR_Name[11];
unsigned char DIR_Attr;
unsigned char DIR_NTRes;
unsigned char DIR_CrtTimeTenth; // Created time (tenths of second)
unsigned short DIR_CrtTime; unsigned short DIR_CrtDate; unsigned short DIR_LstAccDate; unsigned short DIR_FstClusHI; unsigned short DIR_WrtTime; unsigned short DIR_WrtDate; unsigned short DIR_FstClusLO; unsigned int DIR_FileSize;
} DirEntry; #pragma pack(pop)
// Created time (hours, minutes, seconds)
// Created day
// Accessed day
// High 2 bytes of the first cluster addr
// Written time (hours, minutes, seconds
// Written day
// Low 2 bytes of the first cluster addre
// File size in bytes. (0 for directories
// File name
// File attributes
// Reserved
We will grade your submission in an x86_64 Rocky Linux 8 container on Gradescope. We will compile your program using gcc 12.1.1 with the C17 standard and GNU extensions.
You must provide a executable le named you need to add example of the
, and by running make , it should generate an in the current working directory. Note that
to your . (Refer to Lab 1 for an
.)
To get started with testing, you can download a sample FAT32 disk and expand it with the following command:
e
s )
Makefile
nyufile
LDFLAGS=-lcrypto
Makefile
Makefile
gnitseT
noitalipmoC
yrtne yrotceriD
[root@... cs202]# unxz fat32.disk.xz
https://cs.nyu.edu/courses/fall24/CSCI-UA.0202-001/nyufile
15/18
11/15/24, 7:22 PM Lab 4: File Recovery
There are a few les on this disk:
– a small text le. DIR –anemptydirectory. – an empty le.
– a large contiguously-allocated le.
– a large non-contiguously allocated le.
You should make your own test cases and test your program thoroughly. Make sure to test your program with disks formatted with different parameters.
We are providing a sample autograder with a few test cases. Please extract
them in your Docker container and follow the instructions in the
le. (Refer to Lab 1 for how to extract a le.)
Note that the test cases are not exhaustive. The numbered test cases on Gradescope are the same as those in the sample autograder, while the lettered test cases are “hidden” test cases that will not be disclosed. If your program passed the former but failed the latter, please double-check if it can handle all corner cases correctly. Do not try to hack or exploit the autograder.
You must submit a .zip archive containing all les needed to compile
in the root of the archive. You can create the archive le with the
following command in the Docker container:
Note that other le formats (e.g., rar ) will not be accepted.
HELLO.TXT
EMPTY.TXT
CONT.TXT
NON_CONT.TXT
README
.tar.xz
noissimbuS
redargotua ehT
nyufile
$ zip nyufile.zip Makefile *.h *.c
https://cs.nyu.edu/courses/fall24/CSCI-UA.0202-001/nyufile
16/18
11/15/24, 7:22 PM Lab 4: File Recovery
You need to upload the .zip archive to Gradescope. If you need to acknowledge any inuences per our academic integrity policy, write them as comments in your source code.
The total of this lab is 100 points, mapped to 15% of your nal grade of this course.
Milestone 1: validate usage. (40 points)
Milestone 2: print the le system information. (5 points)
Milestone 3: list the root directory. (10 points)
Milestone 4: recover a small le. (15 points)
Milestone 5: recover a large contiguously-allocated le. (10 points)
Milestone 6: detect ambiguous le recovery requests. (5 points)
Milestone 7a: recover a small le with SHA-1 hash. (5 points)
Milestone 7b: recover a large contiguously-allocated le with SHA-1
hash. (5 points)
Milestone 8: recover a non-contiguously allocated le. (5 points)
This lab requires signicant programming effort. Therefore, start as early as possible! Don’t wait until the last week.
Before you start, use xxd to examine the disk image to get an idea of
the FAT32 layout. Keep a backup of the hexdump.
After you create a le or delete a le, use xxd to compare the hexdump
of the disk image against your backup to see what has changed.
You can also use to convert a hexdump back to a binary le. You can use it to “hack” a disk image. In this way, you can try recovering a le
manually before writing a program to do it. You can also create a non-
contiguously allocated le articially for testing in this way.
Always umount before using xxd or running your program.
When updating FAT, remember to update all FATs.
Using
to access the disk image is more convenient than
or
. You may need to open the disk image with
and map
it with
underlying le. Once you have mapped your disk image, you can cast any
address to the FAT32 data structure type, such as
and in order to update the . You can also cast the FAT to
for easy access.
The milestones have diminishing returns. Easier milestones are worth
more points. Make sure you get them right before trying to tackle the harder ones.
This lab has borrowed some ideas from Dr. T. Y. Wong.
nyufile
mmap()
read()
fread()
O_RDWR
PROT_READ | PROT_WRITE
MAP_SHARED
(DirEntry *)(mapped_address + 0x5000)
int[]
