Carleton University School of Computer Science
COMP 3000 (WINTER 2021) OPERATING SYSTEMS ASSIGNMENT 3 (SOLUTIONS)
Questions – part 1 [10] (File systems)
The following questions (where applicable) will be based on the original 3000test.c in Tutorial 5:
When the logical size is greater than the physical size, we can say the file has “holes”. Create a sparse file (file with “holes”) with:
truncate -s 256M myfile1
Create another one:
Create a third one:
Examine the size of the files with
1. [3] Explain why the logical size and the physical size are what they are now, for myfile1, myfile2 and myfile3 respectively. Hint: make proper use of man pages for the commands/devices involved. Try to provide the answer this way: based on what the command (and the device if applicable) does, then considering the specified arguments, explain why the logical size is this and why the physical size is that.
-myfile1: the truncate command adjusts the size of a file to the specified size, which is 256M here. It extends the file (if shorter than specified) with “holes”. As myfile1 does not exist (size=0), the whole file will be filled with “holes”. Hence the physical size is 0, although logical is 268435456.
-myfile2: the device /dev/zero is a data sink which always returns ‘\0’ for reads (so they are real bytes). The “real” bytes account for 1x1M bytes. Seeking by an offset of 255x1M bytes creates “holes” So the composition is: 1M (physical) + 255x1M (holes) = 268435456. -myfile3: the device /dev/null is also a data sink but it returns “end of file” (EOF) for reads. So the reads just ends there. Seek by an offset of 256x1M bytes creates “holes”. So the composition is: 0 (physical) + 256x1M(holes) = 268435456.
2. [3] Add a function to so that it prints a line to indicate whether the file has “holes”,
dd if=/dev/zero of=myfile2 bs=1M count=1 seek=255
dd if=/dev/null of=myfile3 bs=1M count=1 seek=256
ls -lais
e.g., “
”. You can name the function as you like (e.g., ) but it must be a single function called in main().
3000test.c
This file has/does not have holes
sparsecheck()
It should only be called if the file is a regular file. In the case of a symbolic link, stat() will automatically follow (dereference) it to the target file.
Hint: you can compare the two sizes to achieve the purpose.
Make sure your code works by testing it with at least a few typical files.
See the function below:
void sparsecheck(struct stat *statbuf)
{
if (statbuf->st_size > statbuf->st_blocks * 512) printf(“This file has holes!\n”);
else }
printf(“This file does not have holes!\n”);
3. [1] Whatisthebenefitof here(thepurposeofline59)?Hint:youwilllikelyrealizethe answer once you start working on the next question (P1Q4).
It maps the content of the file into the address space of 3000test so that it can be accessed (read/write) like memory.
4. [3]Thelines54–79aretocounttheoccurrencesofthecharacter‘a’ifthefileisaregularfile. Change the code to avoid using mmap() (line 59) but not affect the current behavior. So, the program should still output the right number of ‘a’s in a regular file. Hint: consider read(2) or pread(2).
Caveat: pay attention to performance. If it’s extremely slower than the original, you may lose marks. Use of malloc() is recommended (otherwise you may have issues with static memory allocation). One extreme: Make sure not to read too few bytes for too many iterations as system calls (read/write) impose heavy performance overhead. The other extreme: Don’t attempt to read the entire file in one shot (e.g., in one array), as you can’t pre-allocate that much even though
mmap()
you can read the file size. See the reference code here.
Questions – part 2 [8] (Concurrency)
The following questions (where applicable) will be based on the original 3000pc.zip in Tutorial 6:
1. [3] Describehowyoucangraduallyfindoutthelengthofthebufferforunnamedpipesjustby manipulating the arguments to ./3000pc-fifo [2/3]. After your attempt, provide this length in bytes [1/3]. (Although the exact value is expected, a range with an error ±256 bytes is also accepted.) Hint in Lecture 15.
Our computer is fast enough that if one party waits for one second the other party can finish all it can do until it has to wait. Therefore, specifying 1 (waiting for a second every 1 event) effectively removes that party for long enough. As the buffer starts empty, removing the producer does not make sense (or the consumer will wait endlessly), so we will remove the consumer (specifying 1 as the last argument). Then if the number of events (2nd argument) is less than or equal to the buffer length, the producer will finish at the very beginning; if the number of events is greater than the length, the producer has to wait until the consumer comes back, at least for the last event. This way, we can probe for the buffer length.
You will see 4096 allows the producer to finish early but not 4097. So the length is 4096 x WORDSIZE = 4096 x 16 = 65,536 = 64KiB
2. [3]Makeminimalchangesto3000pc-fifosothatit:
– Takes as the last command line argument a named pipe (FIFO) that replaces the unnamed one (pipe(pipefd)), for example:
– Uses this named pipe for the producer to write to, whose fd replacing
./3000pc-fifo 1000 0 0 /home/student/myfifo
pipefd_write
– Uses this named pipe for the consumer to read from, whose fd replacing
3000pc-fifo should still work the same as before.
The substitution is straightforward, except that one party cannot close the shared fd before the other finishes (if we don’t bother to sync, just leave it open). See the diff here.
3. [1] In3000pc-rendezvous,whyarethelasttwoargumentsofsem_init()setto“1,1”(line 319)?
The first “1” ensures that this semaphore is shared (accessible) between processes as the consumer and the producer are two processes. The second “1” is because we initialize the
pipefd_read
2
semaphore to serve as a lock/mutex. Recall: 0 for condition variable and 1 for mutex.
4. [1] In 3000pc-rendezvous (line 349), why is the second last argument of mmap() set to -1 (as opposed to the fd in 3000test)?
Because in this case mmap() is used for memory sharing (anonymous), not backed by a file. Sometimes it’s ignored sometimes required to be -1 due to .
MAP_ANONYMOUS
Bonus question [6] (no partial marks)
Setup:
Run setup.sh in a directory of your choice. This script creates an image file foo, formats it to ext4 (pay attention to the block size), similar to what was done in Tutorial 5, and creates a number of empty
files and directories. Question:
Provide a specific set of commands (show calculation where needed) that you can use to corrupt the filesystem foo such that after repaired with fsck, /mnt/victimdir/victim ends up in lost+found, but other inodes are unaffected. Your commands should be 100% reproducible by the TA, after running
. No points will be awarded if any additional files besides /mnt/victimdir/victim end up in .
setup.sh
lost+found
• The set of commands can only be a combination of ls, and dd. No other commands are allowed.
• If a command is only used to get information for your calculation, describe which number/part of the output you need for the next step.
• The required effect above must be reproducible by the TA, by following your set of commands and repairing with fsck.
dumpe2fs
You will be achieving the corruption as you’ve seen in the midterm question where file1 – file 5 lost their names due to one corrupted directory inode.
Note: When you try to mount the already-corrupted filesystem foo, there will be no error as the superblock is still good, until you try to access /mnt/victimdir/victim.
Also note: This will need some advanced understanding of how inodes/blocks are organized in an ext4 filesystem (NOT directly mentioned in the lectures/tutorials yet, hence the bonus). Refer to https://ext4.wiki.kernel.org/index.php/Ext4_Disk_Layout#Finding_an_Inode as a hint. Basically, you just need to locate the inode in question and overwrite it with dd.
– When the image is still mounted, use ` ` to find the inode number of victimdir: This should be 4097
– Run `dumpe2fs foo` to find: inode size, inodes per group, block size: Inode size = 128, inodes per group = 2048, block size = 1024
– Calculate inode group number:
inode group = floor((inode num – 1) / (inodes per group))
= floor(4096 / 2048)
= group 2
– Run ` ` to find the inode table location for group 2:
ls -lai
dumpe2fs foo
3
blocks 781-1036
– Calculate the offset of the inode within the table:
offset = (inode num – 1) % (inodes per group) = 4096 % 2048
=0
– Calculate the offset of the inode:
offset = (block index) * (block size / inode size) + (offset within table) = 781 * (1024 / 128) + 0
= 6248
– So the command we need to run to corrupt the file system is:
`dd if=/dev/zero of=foo bs=128 conv=notrunc count=1 seek=6248`
4