代做CSc 360、代写Operating Systems、Python程序设计调试、代写Python

日期：2019-11-24 07:49

CSc 360: Operating Systems (Fall 2019)

Programming Assignment 3 (P3): A Simple File System (SFS)

Spec out: Nov 1, 2019

Due Date: Nov 29, 2019

1 1 Introduction

2 So far, you have built a shell environment and a multi-thread scheduler with process synchronization. Excellent job!

3 What is still missing for a “real” operating system? A file system! In this assignment, you will implement utilities

4 that perform operations on a file system similar to Microsoft’s FAT file system with some improvement.

5 1.1 Sample File Systems

6 You will be given a test file system disk image for self-testing, but you can create your own image following the

7 specification, and your submission may be tested against other disk images following the same specification.

8 You should get comfortable examining the raw, binary data in the file system images using the program xxd.

9 VERY IMPORTANT: since you are dealing with binary data, functions intended for string ma-

10 nipulation such as strcpy() do NOT work (since binary data may contain binary ‘0’ anywhere), and

11 you should use functions intended for binary data such as memcpy().

12 2 Tutorial Schedule

13 In order to help you finish this programming assignment on time successfully, the schedule of the lectures and

14 the tutorials has been adjusted. There are two tutorials and one help session arranged during the course of this

15 assignment. NOTE: Please do attend the tutorials and follow the tutorial schedule closely.

Date Tutorial Milestones

Nov 5/7/8 P3 spec and practice questions go-through design done

Nov 12/14/15 reading break, no tutorials coding half done

Nov 19/21/22 more on design and implementation coding done

Nov 26/28/29 no tutorials but a help session final deliverable

16 3 Requirements

17 3.1 Part I (3 points)

18 In part I, you will write a program that displays information about the file system. In order to complete part I, you

19 will need to read the file system super block and use the information in the super block to read the FAT.

20 Your program for part I will be invoked as follows (output value here just for illustration purposes):

./diskinfo test.img

21 Sample output:

Super block information:

Block size: 512

Block count: 5120

FAT starts: 1

1

FAT blocks: 40

Root directory start: 41

Root directory blocks: 8

FAT information:

Free Blocks: 5071

Reserved Blocks: 41

Allocated Blocks: 8

22 Please be sure to use the exact same output format as shown above.

23 3.2 Part II (3 points)

24 In part II, you will write a program, with the routines already implemented for part I, that displays the contents of

25 the root directory or a given sub-directory in the file system.

26 Your program for part II will be invoked as follows:

./disklist test.img /sub_dir

27 The directory listing should be formatted as follows:

28 1. The first column will contain:

29 (a) F for regular files, or

30 (b) D for directories;

31 followed by a single space

32 2. then 10 characters to show the file size, followed by a single space

33 3. then 30 characters for the file name, followed by a single space

34 4. then the file modification date (we will not display the file creation date).

For example:

F 2560 foo.txt 2005/11/15 12:00:00

F 5120 foo2.txt 2005/11/15 12:00:00

F 48127 makefs 2005/11/15 12:00:00

F 8 foo3.txt 2005/11/15 12:00:00

35 3.3 Part III (3 points)

36 In part III, you will write a program that copies a file from the file system to the current directory in Linux. If the

37 specified file is not found in the root directory or a given sub-directory of the file system, you should output the

38 message File not found. and exit.

39 Your program for part III will be invoked as follows:

./diskget test.img /sub_dir/foo2.txt foo.txt

40 3.4 Part IV (3 points)

41 In part IV, you will write a program that copies a file from the current Linux directory into the file system, at the

42 root directory or a given sub-directory. If the specified file is not found, you should output the message File not

43 found. on a single line and exit.

44 Your program for part IV will be invoked as follows:

./diskput test.img foo.txt /sub_dir/foo3.txt

2

45 3.5 Part V (3 points)

46 From time to time, the disk image may get corrupted due to wrong or incomplete operations, including what happened

47 to the test image, although it does not affect the first four parts. Your fifth part is to go through the disk image

48 according to the file system specification, including the super block, FDT, FAT and data blocks, find inconsistent

49 information among them and fix these issues when possible. For example, a block indicated as reserved (for FAT

50 and root directory) in FAT might be mistakenly used as a data block. In this case, the data shall be relocated, and

51 the FAT and possibly FDT are updated accordingly. Also, a block indicated as allocated in FAT does not belong to

52 any files. In this case, the entry in FAT is fixed to available. Further, a block is the last block of a file according

53 to its size, but it is not indicated by -1 in FAT. In this case, the FAT entry is updated to -1. On the other hand, a

54 block is not the last block of a file according to its size, but it is indicated by -1 in FAT, so the file is truncated up

55 to this last block. Your program needs to be able to handle at least these three cases.

56 Your program for part V will be invoked as follows:

./diskfix test.img

57 and output the problems that you identified and possibly fixed, e.g.,

Block 5 indicated reserved in FAT but used by foo.txt; foo.txt relocated

Block 1005 indicated allocated in FAT but not used by any files; fixed to available

Block 2005 is the last block of foo2.txt but not indicated -1 in FAT; fixed to -1

Block 3005 is not the last block of foo3.txt but indicated -1 in FAT; foo3.txt truncated to 4096 bytes

58 4 File System Specification

59 The FAT file system has three major components:

60 1. the super block,

61 2. the directory structure.

62 3. the File Allocation Table (informally referred to as the FAT),

63 Each of these three components is described in the subsections below.

64 4.1 File System Superblock

65 The first block (512 bytes) is reserved to contain information about the file system. The layout of the superblock is

66 as follows:

Description Size Default Value

File system identifier 8 bytes CSC360FS

Block Size 2 bytes 0x200

File system size (in blocks) 4 bytes 0x00001400

Block where FAT starts 4 bytes 0x00000001

Number of blocks in FAT 4 bytes 0x00000028

Block where root directory starts 4 bytes 0x00000029

Number of blocks in root dir 4 bytes 0x00000008

Figure 1: Superblock Fields

67 Note: Block number starts from 0 in the file system.

68 4.2 Directory Entries

69 Each directory entry takes up 64 bytes, which implies there are 8 directory entries per 512 byte block.

70 Each directory entry has the following structure:

71 The description of each field follows:

3

Description Size

Status 1 byte

Starting Block 4 bytes

Number of Blocks 4 bytes

File Size (in bytes) 4 bytes

Create Time 7 bytes

Modify Time 7 bytes

File Name 31 bytes

unused (set to 0xFF) 6 bytes

Figure 2: Directory Entry

Bit 0 set to 0 if this directory entry is available,

set to 1 if it is in use

Bit 1 set to 1 if this entry is a normal file

Bit 2 set to 1 if this entry is a directory

Figure 3: Format of Status Field

72 Status This is bit mask that is used to describe the status of the file. Currently only 3 of the bits are used.

73 It is implied that only one of bit 2 or bit 1 can be set to 1. That is, an entry is either a normal file or it is a

74 directory, not both.

75 Starting Block This is the location on disk of the first block in the file

76 Number of Blocks The total number of blocks in this file

File Size The size of the file, in bytes. The size of this field implies that the largest file we can support is 232

77 bytes

78 long.

79 Create Time The date and time when this file was created. The file system stores the system times as integer

80 values in the format:

Figure 4: Format of Date-Time Field

82 Modify Time The last time this file was modified. Stored in the same format as the Create Time shown above.

83 File Name The file name, null terminated. Because of the null terminator, the maximum length of any filename is

84 30 bytes.

85 Valid characters are upper and lower case letters (a-z, A-Z), digits (0-9) and the underscore character ( ).

4

86 4.3 File Allocation Table (FAT)

87 Each directory entry contains the starting block number for a file, let’s say it is block number X. To find the next

88 block in the file, you should look at entry X in the FAT. If the value you find there does not indicate End-of-File

89 (see below) then that value, call it Y, is the next block number in the file.

90 That is, the first block is at block number X, you look in the FAT table at entry X and find the value Y. The

91 second data block is at block number Y. Then you look in the FAT at entry Y to find the next data block number...

92 continue this until you find the special value in the FAT entry indicating that you are at the last FAT entry of the

93 file.

94 The FAT is really just a linked list, which the head of the list being stored in the “Starting Block” field in the

95 directory entry, and the ‘next pointers’ being stored in the FAT entries.

96 FAT entries are 4 bytes long (32 bits), which implies there are 128 FAT entries per block.

Special values for FAT entries are described in Figure 5.

Value Meaning

0x00000000 This block is available

0x00000001 This block is reserved

0x00000002–

0xFFFFFF00 Allocated blocks as part of files

0xFFFFFFFF This is the last block in a file

Figure 5: Value of FAT entry

97

98 5 Byte Ordering

99 Different hardware architectures store multi-byte data (like integers) in different orders. Consider the large integer:

100 0xDEADBEEF

101 On the Intel architecture (Little Endian), it would be stored in memory as:

102 EF BE AD DE

103 On the PowerPC (Big Endian), it would be stored in memory as:

104 DE AD BE EF

105 Our file system will use Big Endian for storage. This will make debugging the file system by examining the raw

106 data much easier.

107 This will mean that you have to convert all your integer values to Big Endian before writing them to disk. There

108 are utility functions in netinit/in.h that do exactly that. (When sending data over the network, it is expected the

109 data is in Big Endian format.)

110 See the functions htons, htonl, ntohs and ntohl.

111 The side effect of using these functions will be that your code will work on multiple platforms. (On machines

112 that natively store integers in Big Endian format, like the Mac (not the Intel-based ones), the above functions don’t

113 actually do anything but you should still use them!)

114 6 Submission Requirements

115 What to hand in: You need to hand in a .tar.gz file containing all your source code and a Makefile that produces

116 the executables for parts I – V.

117 Please include a readme.txt file that explains your design and implementation.

118 The file is submitted through connex.csc.uvic.ca site.

5

119 A An Exercise

120 Q1 Consider the superblock shown below:

121 0000000: 4353 4333 3630 4653 0200 0000 1400 0000 CSC360FS........

122 0000010: 0001 0000 0028 0000 0029 0000 0008 0000 .....(...)......

123 0000020: 0000 0000 0000 0000 0000 0000 0000 0000 ................

124 (a) What block does the FAT start on? How many blocks are used for the FAT?

125 (b) What block does the root directory start on? How many blocks are used for the root directory?

6

126 Q2 Consider the following block from the root directory:

127 0005200: 0300 0000 3100 0000 0500 000a 0007 d50b ....1...........

128 0005210: 0f0c 0000 07d5 0b0f 0c00 0066 6f6f 2e74 ...........foo.t

129 0005220: 7874 0000 0000 0000 0000 0000 0000 0000 xt..............

130 0005230: 0000 0000 0000 0000 0000 00ff ffff ffff ................

131 0005240: 0300 0000 3600 0000 0a00 0014 0007 d50b ....6...........

132 0005250: 0f0c 0000 07d5 0b0f 0c00 0066 6f6f 322e ...........foo2.

133 0005260: 7478 7400 0000 0000 0000 0000 0000 0000 txt.............

134 0005270: 0000 0000 0000 0000 0000 00ff ffff ffff ................

135 0005280: 0300 0000 4000 0000 5e00 00bb ff07 d50b ....@...^.......

136 0005290: 0f0c 0000 07d5 0b0f 0c00 006d 616b 6566 ...........makef

137 00052a0: 7300 0000 0000 0000 0000 0000 0000 0000 s...............

138 00052b0: 0000 0000 0000 0000 0000 00ff ffff ffff ................

139 00052c0: 0300 0000 9e00 0000 0100 0000 0807 d50b ................

140 00052d0: 0f0c 0000 07d5 0b0f 0c00 0066 6f6f 332e ...........foo3.

141 00052e0: 7478 7400 0000 0000 0000 0000 0000 0000 txt.............

142 00052f0: 0000 0000 0000 0000 0000 00ff ffff ffff ................

143 (a) How many files are allocated in this directory? What are their names?

144 (b) How many blocks does the file makefs occupy on the disk?

7

145 Q3 Given the root directory information from the previous question and the FAT table shown below:

146 0000200: 0000 0001 0000 0001 0000 0001 0000 0001 ................

147 0000210: 0000 0001 0000 0001 0000 0001 0000 0001 ................

148 0000220: 0000 0001 0000 0001 0000 0001 0000 0001 ................

149 0000230: 0000 0001 0000 0001 0000 0001 0000 0001 ................

150 0000240: 0000 0001 0000 0001 0000 0001 0000 0001 ................

151 0000250: 0000 0001 0000 0001 0000 0001 0000 0001 ................

152 0000260: 0000 0001 0000 0001 0000 0001 0000 0001 ................

153 0000270: 0000 0001 0000 0001 0000 0001 0000 0001 ................

154 0000280: 0000 0001 0000 0001 0000 0001 0000 0001 ................

155 0000290: 0000 0001 0000 0001 0000 0001 0000 0001 ................

156 00002a0: 0000 0001 0000 002a 0000 002b 0000 002c .......*...+...,

157 00002b0: 0000 002d 0000 002e 0000 002f 0000 0030 ...-......./...0

158 00002c0: ffff ffff 0000 0032 0000 0033 0000 0034 .......2...3...4

159 00002d0: 0000 0035 ffff ffff 0000 0037 0000 0038 ...5.......7...8

160 00002e0: 0000 0039 0000 003a 0000 003b 0000 003c ...9...:...;...<

161 00002f0: 0000 003d 0000 003e 0000 003f ffff ffff ...=...>...?....

162 (a) What blocks does the file foo.txt occupy on the disk?

163 (b) What blocks does the file foo2.txt occupy on the disk?

8