CSC369 – Lab 8
Ext2 overview (metadata and files)
Starter code explained
Lab Exercises 8 and 9 (no handout, they’re online)
Copyright By PowCoder代写 加微信 powcoder
Learning objectives
By the end of this lab you should be able to:
Explain the structure of a basic ext2 file system
Access key metadata / data structures in a basic ext2 file system Superblock
Group descriptor Inode table
Directories
Lab exercises – goals
●Exercise TE8 – access and print file system information from the block descriptor ○Very simple task (we know you have A3 to wrap up)
●Exercise TE9 – access and block and inode bitmaps, and inode info
○A bit more complex, requires bitwise operations (see refresher in Lab0 at the start of term)
●Exercise TE10 – access and print directory structures ○More exposure to file system structures that you need for A4
●The sooner you complete these, the sooner you can start on A4
○A4 is time-consuming, but you get practical experience with file systems in the process!
Ext2 overview
● Ext2 splits the HD into blocks of 1024 bytes. Think of it as an array of blocks! 1024 1024 1024 1024 1024 1024 1024 1024
● And assigns different semantics to each of them.
Always empty!
Metadata for the filesystem
Metadata Metadata for the for filesystem directories
User file contents
Don’t use this order as reference, this
is merely illustrative.
Ext2 overview
● Ext2 splits the HD into blocks of 1024 bytes. Think of it as an array of blocks! 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024
Always empty!
Metadata for the filesystem
Metadata Metadata for the for filesystem directories
User file contents
Ext2 overview
● Ext2 splits the HD into blocks of 1024 bytes. Think of it as an array of blocks! 1024 1024 1024 1024 1024 1024 1024 1024
● And assigns different semantics to each of them.
Block group 1
1024 1024 1024 1024 1024 1024 1024 1024
● Ext2 groups blocks into block groups
○ For A4, you can assume only one block group.
● Each file has an associated inode.
○ This does not contain the file itself!
Ext2 overview
● A data structure with information about the file! Which information?
What is this? There are important details you must know in order to complete this assignment.
What is this? There are important details you must know in order to complete this assignment.
Check the documentation!! http://www.nongnu.org/ext2- doc/ext2.html#I-LINKS- COUNT
Another pitfall here… check the documentation!
The most important part of the inode! An array of block numbers, telling you in which blocks the contents of the file are located!
If this is a text file with contents “Hello world”,
and i_block[0] = 10,
then the text is located in the 10th block, byte number 10*1024 = 10240.
Read the documentation, there is much more to this than what I’ve just described.
● Each file has an associated inode.
○ This is does not contain the file itself!
Ext2 overview
● A data structure with information about the file! Which information?
● For each block group, Ext2 will allocate a constant number of consecutive
blocks to serve as an array of inodes: the inode table. ○ (notice each inode has a fixed size)
● Each file has an associated inode.
○ This is does not contain the file itself!
Ext2 overview
● A data structure with information about the file! Which information?
● For each block group, Ext2 will allocate a constant number of consecutive
blocks to serve as an array of inodes: the inode table.
○ (notice each inode has a fixed size)
○ In A4, what does that mean for the number of inodes available?
● Each file has an associated inode.
○ This is does not contain the file itself!
Ext2 overview
● A data structure with information about the file! Which information?
● For each block group, Ext2 will allocate a constant number of consecutive
blocks to serve as an array of inodes: the inode table. ○ (notice each inode has a fixed size)
○ In A4, what does that mean for the number of inodes available?
○ You have a very limited number of inodes, and therefore a maximum number of
files you can store!
○ Some inodes are reserved… documentation!
● Suppose you have a pointer to your disk:
char *disk; //Suppose, for now, that your disk is in memory.
Ext2 overview
● Suppose you have a pointer to your disk:
char *disk; //Suppose, for now, that your disk is in memory.
Ext2 overview
● Suppose your inode table is at block 10,
struct ext2_inode *inodes = (struct ext2_inode *)(disk + 1024 * 10);
● Suppose you have a pointer to your disk:
char *disk; //Suppose, for now, that your disk is in memory.
Ext2 overview
● Suppose your inode table is at block 10,
struct ext2_inode *inodes = (struct ext2_inode *)(disk + 1024 * 10);
● and you want to print the contents of the 7th inode… printf(“Size in bytes = %d”, inodes[6].i_size);
Ext2 overview
● Suppose Ext2 has 32 inodes in total. When you create a file, you need grab a free inode to store the file’s metadata.
Ext2 overview
● Suppose Ext2 has 32 inodes in total. When you create a file, you need grab a free inode to store the file’s metadata.
● How do we find a free inode?
○ Iterate over the inode table? But the inode structure doesn’t have a member
indicating whether it is associated with a file… It could be filled with garbage values…
Ext2 overview
● Suppose Ext2 has 32 inodes in total. When you create a file, you need grab a free inode to store the file’s metadata.
● How do we find a free inode?
○ Iterate over the inode table? But the inode structure doesn’t have a member
indicating whether it is associated with a file… It could be filled with garbage values…
● Ext2 allocates a block to be the inode bitmap!
○ A vector of bits, where inode_bitmap[i] = 1 iff the i-th inode is in use.
● Suppose your inode bitmap is located at block 4.
Ext2 overview
Ext2 overview
● Suppose your inode bitmap is located at block 4. unsigned char *inode_bits = (unsigned char *)(disk + 1024 * 4);
Ext2 overview
● Suppose your inode bitmap is located at block 4. unsigned char *inode_bits = (unsigned char *)(disk + 1024 * 4);
● From the documentation:
○ The first inode of this block group is represented by bit 0 of byte 0, the second by
bit 1 of byte 0. The 8th inode is represented by bit 7 (most significant bit) of byte 0 while the 9th inode is represented by bit 0 (least significant bit) of byte 1.
Ext2 overview
● Suppose your inode bitmap is located at block 4. unsigned char *inode_bits = (unsigned char *)(disk + 1024 * 4);
● From the documentation:
○ The first inode of this block group is represented by bit 0 of byte 0, the second by
bit 1 of byte 0. The 8th inode is represented by bit 7 (most significant bit) of byte 0 while the 9th inode is represented by bit 0 (least significant bit) of byte 1.
● If you have 32 inodes, you are looking at the first 32 bits, i.e., the first 4 bytes of the bitmap:
for (byte = 0; byte < 32 / 8; byte++)
for (bit = 0; bit < 8; bit++)
in_use = inode_bits[byte] & (1 << bit);
Ext2 overview
● Recall that file contents are also stored in blocks.
● So when you add a new file, you also need find free blocks for it.
Ext2 overview
● Recall that file contents are also stored in blocks.
● So when you add a new file, you also need find free blocks for it.
● Just like for inodes, Ext2 will allocate a special block to be the block bitmap!
● How do we find:
○ The inode table?
○ The block bitmap?
○ The inode bitmap?
Ext2 overview
● How do we find:
○ The inode table?
○ The block bitmap?
○ The inode bitmap?
Ext2 overview
● How do we find:
○ The inode table?
○ The block bitmap?
○ The inode bitmap?
Ext2 overview
● Ext2 has a special block called block group descriptor table. ○ An array of block group descriptors
● How do we find:
○ The inode table?
○ The block bitmap?
○ The inode bitmap?
Ext2 overview
● Ext2 has a special block called block group descriptor table. ○ An array of block group descriptors
● How do we find:
○ The inode table?
○ The block bitmap?
○ The inode bitmap?
Ext2 overview
● Ext2 has a special block called block group descriptor table.
○ An array of block group descriptors
○ Recall that there is only one block group in the disks used in A4.
Ext2 overview
● How do we find:
○ The inode table?
○ The block bitmap?
○ The inode bitmap?
Ext2 overview
● Ext2 has a special block called block group descriptor table.
○ An array of block group descriptors
○ Recall that there is only one block group in the disks used in A4.
● How do we find this block?
○ It is, for this assignment, the third block in the disk.
Ext2 overview
● There is one last important data structure: the superblock.
● It contains information about the whole filesystem:
○ number available inodes/blocks across all groups,
○ constants related to sizes, etc.
○ the code is too big to paste here, but it is the ext2_super_block struct in the
Ext2 overview
● What does your typical A4 disk image actually look like:
Ext2 overview
● What does your typical A4 disk image actually look like:
1024 Empty space
1024 1024 Empty space
Superblock
Ext2 overview
● What does your typical A4 disk image actually look like:
1024 1024 1024 Empty space
Superblock
Block group descriptor table
Ext2 overview
● What does your typical A4 disk image actually look like:
1024 1024 1024 1024 1024 Empty space
Superblock
Block Inode bitmap bitmap
Block group descriptor table
Ext2 overview
● What does your typical A4 disk image actually look like:
Ext2 overview
● What does your typical A4 disk image actually look like:
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 Empty space
Superblock
Block Inode bitmap bitmap
Block group descriptor table
Inode table
char *disk;
Starter code
Exercises 8 and 9
● Print some attributes of the block group descriptor. ○ Exercise 8
● Print some attributes of each inode that is being used. ○ Exercise 9
○ Some inodes are reserved and should be ignored. Which ones? Look at the documentation.
Looking at dumps: debugging your code
● It will be useful to examine the images you create/modify using external tools.
● Dump the files emptydisk.img and onefile.img
○ xxd -c 1 emptydisk.img emptydisk.dump
○ xxd -c 1 onefile.img onefile.dump
● This dumps one byte per line. You can change this, but I find it useful to have line numbers matching the byte number you have.
Looking at dumps: debugging your code
● It will be useful to examine the images you create/modify using external tools.
● Dump the files emptydisk.img and onefile.img
○ xxd -c 1 emptydisk.img emptydisk.dump
○ xxd -c 1 onefile.img onefile.dump
● This dumps one byte per line. You can change this, but I find it useful to have line numbers matching the byte number you have.
● Now open your files with:
○ vimdiff emptydisk.dump onefile.dump
free blocks count free inodes count
Mind the endianness!
Looking at dumps: debugging your code
Vim uses 1 based indexing for lines, so we’re one byte off (you can simply delete the first line to fix that...)
● A directory is represented just like a file: ○ An inode + some data blocks.
Directories
● While the data blocks for a file store its contents, a directory data block stores a linked list of directory entries.
● An entry must ALWAYS have a length that is a multiple of 4.
○ The last entry must always occupy the remaining space of the block.
Directories
● An entry must ALWAYS have a length that is a multiple of 4.
○ The last entry must always occupy the remaining space of the block.
● This is why we have two “length” fields:
○ To jump to the following record, just do base + rec_len (how do you tell when you
have reached the last entry?).
○ To print the name, we use name_len.
● Suppose some directory stores its contents in block 9.
Directories
● Suppose some directory stores its contents in block 9.
● How do you find the name of the first entry?
○ char* name = disk + 1024 * 9 + sizeof(ext2_dir_entry)
○ ... problems?
Directories
● Suppose some directory stores its contents in block 9.
● How do you find the name of the first entry?
○ char* name = disk + 1024 * 9 + sizeof(ext2_dir_entry)
Directories
○ ... problems?
○ Isn’t this “eating” the first 4 bytes (or however many bytes a pointer needs) of the
● Suppose some directory stores its contents in block 9.
Directories
● How do you find the name of the first entry?
○ char* name = disk + 1024 * 9 + sizeof(ext2_dir_entry)
○ Isn’t this “eating” the first 4 bytes (or however many bytes a pointer needs) of the
○ No! In C, declaring char name[]; is an indication that the struct will have variable
size. That member has “size” 0!
● char* name = disk + 1024 * 9 + sizeof(ext2_dir_entry)
● How do we print this? This is not NULL terminated.
Directories
● char* name = disk + 1024 * 9 + sizeof(ext2_dir_entry)
● How do we print this? This is not NULL terminated.
○ ext2_dir_entry *entry = (ext2_dir_entry*) disk + 1024* 9;
○ printf("%.*s", entry->name_len, name);
Directories
● char* name = disk + 1024 * 9 + sizeof(ext2_dir_entry)
● How do we print this? This is not NULL terminated.
○ ext2_dir_entry *entry = (ext2_dir_entry*) disk + 1024* 9;
○ printf(“%.*s”, entry->name_len, name);
● The next entry is located at…?
Directories
● char* name = disk + 1024 * 9 + sizeof(ext2_dir_entry)
● How do we print this? This is not NULL terminated.
○ ext2_dir_entry *entry = (ext2_dir_entry*) disk + 1024* 9;
○ printf(“%.*s”, entry->name_len, name);
● The next entry is located at…? ○ ((char*) entry)+ entry->rec_len;
Directories
● Iterate over all inodes.
Exercise 10
● If the inode is being used, and if it is related to a directory,
○ Access the directory data blocks and print each directory entry.
● Some pitfalls:
○ How do you detect deleted entries? Do you need to?
○ What if there is a deleted entry as the very first entry of the block?
○ Again… check the documentation for answers (or ask me next week).
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com