-
Notifications
You must be signed in to change notification settings - Fork 5
/
Copy patha3.html
261 lines (171 loc) · 15.9 KB
/
a3.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>Assignment 3 - File Systems</title>
<meta name="author" content="Karen Reid">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<!--
<link href="http://www.cdf.toronto.edu/~csc369h/winter/assets/themes/bootstrap/resources/bootstrap/css/bootstrap.min.css" rel="stylesheet">
<link href="http://www.cdf.toronto.edu/~csc369h/winter//assets/css/mystyle.css" rel="stylesheet">
-->
<link href="http://www.cdf.toronto.edu/~csc369h/winter//assets/css/stripped.css" rel="stylesheet">
<!--[if lt IE 9]>
<script src="http://www.cdf.toronto.edu/~csc369h/winter/assets/themes/bootstrap/resources/respond/Respond.min.js"></script>
<![endif]-->
<link href="/atom.xml" type="application/atom+xml" rel="alternate" title="Sitewide ATOM Feed">
<link href="/rss.xml" type="application/rss+xml" rel="alternate" title="Sitewide RSS Feed">
</head>
<body>
<nav class="navbar navbar-default" role="navigation">
<div class="container">
<div class="navbar-header">
<button type="button" class="navbar-toggle" data-toggle="collapse" data-target=".navbar-ex1-collapse">
<span class="sr-only">Toggle navigation</span>
<span class="icon-bar"></span>
<span class="icon-bar"></span>
<span class="icon-bar"></span>
</button>
<a class="navbar-brand" href="http://www.cdf.toronto.edu/~csc369h/winter/index.html">CSC369H: Operating Systems</a>
</div>
<div class="collapse navbar-collapse navbar-ex1-collapse">
<ul class="nav navbar-nav">
<!-- <li><a href="http://www.cdf.toronto.edu/~csc369h/winter/info.html" target="_blank">Syllabus</a></li>
-->
<li><a href="http://www.cdf.toronto.edu/~csc369h/winter/info.html">Syllabus</a></li>
<!-- <li><a href="http://www.cdf.toronto.edu/~csc369h/winter/lectures.html" target="_blank">Lectures</a></li>
-->
<li><a href="http://www.cdf.toronto.edu/~csc369h/winter/lectures.html">Lectures</a></li>
<!-- <li><a href="http://www.cdf.toronto.edu/~csc369h/winter/assignments.html" target="_blank">Assignments</a></li>
-->
<li><a href="http://www.cdf.toronto.edu/~csc369h/winter/assignments.html">Assignments</a></li>
<!-- <li><a href="http://www.cdf.toronto.edu/~csc369h/winter/tests.html" target="_blank">Tests</a></li>
-->
<li><a href="http://www.cdf.toronto.edu/~csc369h/winter/tests.html">Tests</a></li>
<!-- <li><a href="http://www.cdf.toronto.edu/~csc369h/winter/grades.html" target="_blank">Grades</a></li>
-->
<li><a href="http://www.cdf.toronto.edu/~csc369h/winter/grades.html">Grades</a></li>
<!-- <li><a href="http://www.cdf.toronto.edu/~csc369h/winter/feedback.html" target="_blank">Anonymous Feedback</a></li>
-->
<li><a href="http://www.cdf.toronto.edu/~csc369h/winter/feedback.html">Anonymous Feedback</a></li>
<!-- <li><a href="http://piazza.com/utoronto.ca/winter2015/csc369/home" target="_blank">Piazza</a></li>
-->
<li><a href="http://piazza.com/utoronto.ca/winter2015/csc369/home">Piazza</a></li>
<!-- <li><a href="https://markus.cdf.toronto.edu/csc369-2015-01/" target="_blank">MarkUs</a></li>
-->
<li><a href="https://markus.cdf.toronto.edu/csc369-2015-01/">MarkUs</a></li>
</ul>
</div>
</div>
</nav>
<div class="container">
<div class="page-header">
<h1>Assignment 3 - File Systems </h1>
</div>
<div class="row">
<div class="col-xs-12">
<p><b>Due</b>: Thursday April 2, 10 p.m.</p>
<h2>Introduction</h2>
<p>In this assignment, you will explore the implementation of a particular file system, ext2, and will write tools to modify ext2-format virtual disks. To do this work, you will need to be comfortable working with binary data and will need to learn about the ext2 filesystem.</p>
<p>You may work in pairs for this assignment. MarkUs will only create the appropriate directory in your repository when you log into MarkUs and either create your group, or declare that you will work alone. The groups will get a new shared repository, and the students working solo may also get a new repository. Please log into MarkUs well before the deadline to take these steps. (If you create the directory in svn, then MarkUs won't know about it and we won't be able to see your work.)</p>
<h3>Requirements</h3>
<p>Your task is to write five programs (in C) that operate on an ext2 formatted virtual disk. The executables must be named <tt>ext2_ls</tt>, <tt>ext2_cp</tt>, <tt>ext2_mkdir</tt>, <tt>ext2_ln</tt>, and <tt>ext2_rm</tt> and must take the specified arguments.</p>
<ul>
<li><tt>ext2_ls</tt>: This program takes two command line arguments. The first is the name of an ext2 formatted virtual disk. The second is an absolute path on the ext2 formatted disk. The program should work like <tt>ls -1</tt>, printing each directory entry on a separate line. Unlike <tt>ls -1</tt>, it should also print <tt>.</tt> and <tt>..</tt>. In other words, it will print one line for every directory entry in the directory specified by the absolute path. If the directory does not exist print "No such file or diretory".</li>
<li><tt>ext2_cp</tt>: This program takes three command line arguments. The first is the name of an ext2 formatted virtual disk. The second is the path to a file on your native operating system, and the third is an absolute path on your ext2 formatted disk. The program should work like <tt>cp</tt>, copying the file on your native file system onto the specified location on the disk. If the specified file or target location does not exist, then your program should return the appropriate error (ENOENT). </li>
<li><tt>ext2_mkdir</tt>: This program takes two command line arguments. The first is the name of an ext2 formatted virtual disk. The second is an absolute path on your ext2 formatted disk. The program should work like <tt>mkdir</tt>, creating the final directory on the specified path on the disk. If any component on the path to the location where the final directory is to be created does not exist or if the specified directory already exists, then your program should return the appropriate error (ENOENT or EEXIST).</li>
<li><tt>ext2_ln</tt>: This program takes three command line arguments. The first is the name of an ext2 formatted virtual disk. The other two are absolute paths on your ext2 formatted disk. The program should work like <tt>ln</tt>, creating a link from the first specified file to the second specified path. If the first location does not exist (ENOENT), if the second location already exists (EEXIST), or if either location refers to a directory (EISDIR), then your program should return the appropriate error. Note that this version of <tt>ln</tt> only works with files.</li>
<li><tt>ext2_rm</tt>: This program takes two command line arguments. The first is the name of an ext2 formatted virtual disk, and the second is an absolute path to a file or link (not a directory) on that disk. The program should work like <tt>rm</tt>, removing the specified file from the disk. If the file does not exist or if it is a directory, then your program should return the appropriate error.</li>
</ul>
<p>All of these programs should be minimalist. Don't implement what isn't specified: only provide the required functionality and specified errors. (For example, don't implement wildcards. Also, can't delete directories? Too bad!)</p>
<p>You will find it <i>very</i> useful for these programs to share code. You will want a function that performs a path walk, for example. You will also want a function that opens a specific directory entry and writes to it. <p>
<h2>Learning about the Filesystem</h2>
<p>Here are several sample virtual disk images:<p>
<ul>
<li><a href="./images/emptydisk.img">emptydisk</a>: An empty virtual disk.</li>
<li><a href="./images/onefile.img">onefile</a>: A single text file has been added to emptydisk.</li>
<li><a href="./images/deletedfile.img">deletedfile</a>: The file from onefile has been removed.</li>
<li><a href="./images/onedirectory.img">onedirectory</a>: A single directory containing a text file has been added to emptydisk.</li>
<li><a href="./images/hardlink.img">hardlink</a>: A hard link to the textfile in onedirectory was added.</li>
<li><a href="./images/deleteddirectory.img">deleteddirectory</a>: A recursive remove was used to remove the directory and file from onedirectory.</li>
<li><a href="./images/twolevel.img">twolevel</a>: The root directory contains a directory called <code>level1</code> and a file called <code>afile</code>. <code>level1</code> contains a directory called <code>level2</code>, and <code>level2</code> contains a file called <code>bfile</code>.</li>
<li><a href="./images/largefile.img">largefile</a>: A file larger than 13KB (13440 bytes) is in the root directory. This file requires the single indirect block in the inode.</li>
</ul>
<p>These disks were each created and formatted in the same way (on an ubuntu virtual machine):<p>
<pre>% dd if=/dev/zero of=~/DISKNAME.img bs=1024 count=128
% mke2fs -N 32 DISKNAME.img
% sudo mount -o loop ~/DISKNAME.img /home/reid/mntpoint
% cd /home/reid/mntpoint
% ...... normal linux commands to add/remove files/directories/links .....
% cd ~
% umount /home/reid/mntpoint</pre>
<p>Since we are creating images with mke2fs, the disks are formatted with the <a href="http://en.wikipedia.org/wiki/Ext2">ext2 file system</a>. You may wish to read about this system before doing some exploration. The <a href="http://en.wikipedia.org/wiki/Ext2">wikipedia page for ext2</a> provides a good overview, but the <a href="http://wiki.osdev.org/Ext2">Ext2 wiki</a> and Dave Poirer's <a href="http://www.nongnu.org/ext2-doc/index.html">Second Extended File System</a> article provide more detail on how the system places data onto a disk. It's a good reference to keep on hand as you explore. </p>
<p>We are restricting ourselves to some simple parameters, so you can make the following assumptions when you write your code:</p>
<ul>
<li>A disk is 128 blocks where the block size is 1024 bytes.</li>
<li>There is only one block group.</li>
<li>There are 32 inodes.</li>
<li>You do not have to worry about permissions or modified time fields in the inodes. You should set the type (in <code>i_mode</code>), <code>i_size</code>, <code>i_links_count</code>, <code>i_blocks</code>(disk sectors), and the <code>i_block</code> array.</li>
</ul>
<p>We will <em>not</em> test your code on anything other than disk images that follow this specification, or on corrupted disk images.</p>
<p>Other tips:</p>
<ul>
<li>Inode and disk block numbering starts at 1 instead of 0.</li>
<li>The root inode is inode number 2 (at index 1)</li>
<li>The first 11 inodes are reserved.</li>
<li>There is always a lost+found directory in the root directory.</li>
<li>Disk sectors are 512 bytes. (This is relevant for the i_blocks field of the inode.)</li>
<li>You should be able to handle directories that require more than one block.</li>
<li>You should be able to handle a file that needs a single indirection</li>
<li>Although you can contruct your own structs from the information in the documentation above, you are welcome to use the <a href="./ext2.h"><tt>ext2.h</tt></a> file that I used for the test code. I took out a bunch of components that we aren't using, but there are still quite a few fields that are irrelevant for our purposes.</li>
</ul>
<p>However, you will probably also want to explore the disk images to get an intuitive sense of how they are structured. (The next three exercises will also help you explore the disk images and get started on the assignment.)</p>
<p>There are two good ways to interface with these images. The first way is to interact with it like a user by mounting the file system so that you can use standard commands (mkdir, cp, rm, ln) to interact with it. Details of how to do this are below. The second way is to interact with the disk as if it is a flat binary file. Use <tt>xxd</tt> to create hex dumps, <tt>diff</tt> to look for differences between the dumps, and your favorite text editor to view the diffs. For example (YMMV):</p>
<pre>% diff <(xxd emptydisk.img) <(xxd onefile.img) > empty-onefile.diff
% vimdiff empty-onefile.diff</pre>
<p>You should be able to use a combination of these techniques to understand how files are placed on disk and how they are removed. For example, you can create a new disk image, use <tt>mount</tt> to place files of various sizes on it, unmount it, and then use <tt>xxd</tt> and <tt>diff</tt> to see how the image differs from the other images you have.</p>
<h3>Mounting a file system</h3>
<p>If you have root access on a Linux machine (or Linux virtual machine), you can use <tt>mount</tt> to mount the disk into your file system and to peruse its contents. (Note: this requires <tt>sudo</tt>, so you will need to do this on a machine (or virtual machine) that you administer.</p>
<p>On CDF, you can use a tool called FUSE that allows you to mount a file system at user-level (from your regular account). It may not work on an NFS mounted file system, so this will only work on the CDF workstations.
</p>
<p>Note: <CDFID> should be replaced with your own CDF user id below.</p>
<pre>
# create a directory in /tmp and go there
mkdir -m 700 /tmp/<CDFID>-csc369h
cd /tmp/<CDFID>-csc369h
# to create your own disk image
dd if=/dev/zero of=DISKNAME.img bs=1024 count=128
/sbin/mke2fs -N 32 -F DISKNAME.img
# create a mount point and mount the image
# CWD is /tmp/<CDFID>-csc369h
mkdir mnt
fuseext2 -o rw+ DISKNAME.img mnt
# check to see if it is mounted
df -hl
# now you can use the mounted file system, for example
mkdir mnt/test
# unmount the image
fusermount -u mnt
</pre>
<p>You can use the same strategy to mount one of the images provided above.</p>
<h2>Submission</h2>
<p>The assignment should be submitted to an <tt>a3</tt> directory in your svn repository. Don't forget to add and commit all of the code for the required programs. Please also provide a Makefile that will create all of the programs if <tt>make</tt> is invoked without arguments. (There should be no error or warnings when -Wall is used.) We will pull the last commit before the deadline for marking.</p>
<p>If you are unable to complete all aspects of this assignment, please add a <tt>README</tt> file (text or pdf format only) to your <tt>a3</tt> folder that explains what is not implemented and describes what features you have completed. You can receive partial credit for functionality that is implemented but that does not complete one of the five required programs.</p>
</div>
</div>
<hr>
<footer>
<p>
© 2015 Karen Reid
<span class="pull-right text-muted">
powered by
<a href="http://jekyllbootstrap3.tk" target="_blank" title="The Definitive Jekyll Blogging Framework">Jekyll-Bootstrap-3</a>
and <a href="http://getbootstrap.com" target="_blank">Twitter Bootstrap 3.0.3</a>
</span>
</p>
</footer>
</div>
<script src="http://www.cdf.toronto.edu/~csc369h/winter/assets/themes/bootstrap/resources/jquery/jquery.min.js"></script>
<script src="http://www.cdf.toronto.edu/~csc369h/winter/assets/themes/bootstrap/resources/bootstrap/js/bootstrap.min.js"></script>
</body>
</html>