The Big Picture

To conclude the discussion on UFS, we will step through an example where we allocate and then delete a /dir1/file1.dat file, which is 25,000 bytes in size, from a UFS2 file system.

File Allocation Example

The high-level process for creating the /dir1/file1.dat file is to locate the dir1 directory, create a directory entry, allocate an inode, and then allocate blocks for the file content. The exact ordering of allocating the different data structures might vary by OS, and the order presented here might not reflect an actual system. There are several data structures that keep lists of available fragment sizes and clusters that are ignored for simplicity in this example.

1. We read the superblock data structure, which is 2 KB in size and is located 64 KB into the file system. From processing this, we learn that the block size is 16KB and fragment size is 2KB. Each cylinder group has 32,776 fragments and 8,256 inodes. We also learn that the group descriptor is located 40 fragments, and the inode table is located 56 fragments into each cylinder group.
2. We need to locate the dir1 directory in the root directory, so we process inode 2. Using the number of inodes per group, we determine that inode 2 is in cylinder group 0. Therefore, the inode table for inode 2 will start in block 56.
3. We read the inode table from block 56 and process the third entry (the first entry is inode 0). The data in inode 2 shows that the directory entry structures for the root directory are located in block 1,096.
4. We read the root directory contents from block 1096 and process the contents as a list of directory entries. We advance ahead by using the reported record length of each entry (we don't care about deleted files) and find the entry named dir1. It has an inode value of 16,549. The A-time of the root directory is updated.
5. We determine where inode 16,549 is located by dividing it by the number of inodes per group and determine that it is in cylinder group 2. Group 2 starts in block 65,552, so its inode table starts in block 65,608. (If we were using a UFS1 file system, we would also need to calculate the base address for the group.)
6. We read the inode table from block 65,608 and process entry 37, which is the relative location of inode 16,549. The inode contents show us that the contents of dir1 are located in block 66,816.
7. We read the dir1 contents from block 66,816 and process the contents as a list of directory entries. We are looking for unused space in the directory. The file1.dat name is eight characters long and therefore the directory entry will require 16 bytes. We find space in between two allocated names, and the M- and C-times of the directory are updated. The space we took had been used by a deleted file.
8. We need to allocate an inode for the file, and it will be allocated in the same cylinder group as the parent directory, which is group 2. To locate the inode bitmap, we must first locate the group descriptor, which is 48 fragments from the start of the group. The group descriptor turns out to be in block 65,600, and it shows us that the inode bitmap is located 168 bytes into the group descriptor. The group descriptor also tells us that the last allocated inode entry was 16,650. We check the status of inode 16,651 and find it to be unallocated. We set its bit in the bitmap, update the last allocated inode value in the group descriptor, and decrement the number of free inodes value in the group descriptor and cylinder group summary area. The inode address is added to the file1.dat directory entry.
9. We locate inode 139 in the inode table, which is the relative location of inode 16,651, and initialize its values. The time values are set to the current time and the link value is set to 1. We also set the UID, GID, and mode fields.
10. The size of the file is 25,000 bytes, so we need to allocate one block and five fragments. We first need to process the group descriptor to find the offset of the fragment bitmap, which is located at byte offset 1,200. The group descriptor identifies block 67,896 as the last block allocated. We examine block 67,904 in the free fragment bitmap and determine that it is not allocated. The bit for this block is set to 0 to show that it is no longer free, and the count of available blocks is decremented. The last allocated pointer is also updated. The five available fragments are found using the bitmap (or one of the bookkeeping lists), and they are located in 74,242 to 74,246. Their bits are set to 0, and the proper bookkeeping values are updated. The address of the block and the starting fragment are added to the inode.
11. The file content of file1.dat is written to the allocated block and fragments.

The final state of the system can be found in Figure 16.8.

Figure 16.8. Final state after adding the 'dir1/file1.dat' file.

 

File Deletion Example

We will now delete the /dir1/file1.dat file using BSD-type methods. As mentioned in the previous section, the order of unallocating the data structures might vary by OS and the order presented here might not be the same as an actual OS.

1. We read the superblock data structure, which is 2 KB in size and is located 64 KB into the file system. From processing this, we learn that the block size is 16 KB and fragment size is 2 KB. Each cylinder group has 32,776 fragments and 8,256 inodes. We also learn that the group descriptor is located 40 fragments, and the inode table is located 56 fragments into each cylinder group.
2. We need to locate the dir1 directory in the root directory, so we process inode 2. Using the number of inodes per group, we determine that inode 2 is in cylinder group 0. Therefore, the inode table for inode 2 will start in block 56.
3. We read the inode table from block 56 and process the third entry (the first entry is inode 0). The data in inode 2 shows that the directory entry structures for the root directory are located in block 1,096.
4. We read the root directory contents from block 1,096 and process the contents as a list of directory entries. We advance ahead using the reported record length of each entry (we don't care about deleted files) and find the entry whose name is dir1. It has an inode value of 16,549. The A-time for the root directory is updated.
5. We determine where inode 16,549 is located by dividing it by the number of inodes per group and determine that it is in cylinder group 2. Group 2 starts in block 65,552, so its inode table starts in block 65,608.
6. We read the inode table from block 65,608 and process entry 37, which is the relative location of inode 16,549. The inode contents show us that the contents of dir1 are located in block 66,816.
7. We read the dir1 contents from block 66,816 and process the contents as a list of directory entries. We are looking the entry for the file1.dat file. We find its entry and observe that it has allocated inode entry 16,651. The directory entry is unallocated by adding its record length to the record length field in the previous directory entry, which belongs to the 12.jpg file. If the system were a Solaris system, the inode pointer would also be cleared. The M-time, A-time, and C-time are updated for dir1.
8. We process the contents of inode 16,651 from the group 2 inode table and decrement the link count by 1 to account for the name being deleted. The link count becomes 0, which means that the inode must be deallocated. To deallocate the inode, the corresponding bit in the inode bitmap is set to 0, and we update the free inode counts in the group descriptor and cylinder group summary area. The mode value in the inode is cleared.
9. We also need to deallocate the one block and five fragments that the file has allocated. For each block and fragment, the corresponding bit in the block and fragment bitmaps are set to 1, and the block pointer in the inode is cleared. The file size is decremented each time a block is deallocated, and it eventually reaches 0. The M-time and C-time are updated to reflect the inode changes. The free block and fragment counts are updated in the group descriptor and cylinder group summary area.

The final state of the file system can be seen in Figure 16.9. The bold lines and values represent the changes to the file system because of the deletion.

Figure 16.9. Final state after deleting the '/dir1/file1.dat' file.