The exam will be on WebCT. It must be completed by next Wednesday and once you start it you must finish within three hours.
FAT File System
FAT 12 used 3 nibble numbers which were hard to deal with. You move away from that with FAT 16, although the basics of FAT 12 and 16 are the same. With 12 and 16, you have a fixed size root directory.
With FAT 32, the root directory is out in the data area and may grow as it needs to (so it may be fragmented, etc. though it'll start in cluster 2).
What does a directory look like? It's a bunch of 32-byte records, and each record represents either what we'd consider to be a DOS directory entry (file or directory) or a long file name. It contains all of the information you need about the file except for the long file name. The LFN is an add-on/hack that Microsoft came up with. LFNs came along in FAT 16 and backtracked into FAT 12 with what we call the vFAT. Entries in vFAT are identified with an invalid flag byte.
A normal directory entry contains the short name, file size, starting cluster, and temporal information (time/date stamps). When we're looking at that information it will be all collected together in the 32 byte directory. The only missing element is the long file name.
Each directory entry points to a starting cluster and to a place in the FAT where the cluster chain for the rest of the file is located.
What kind of non-numerical numbers do you find in the FAT? End-of-file (EOF) and bad block markers are common.
What marks the cluster as being available? A zero (0) in the cluster chain shows that the cluster is available for the OS to choose to save a new file.
When you delete a file, the short file name entry is marked with a 0xE5, and the cluster chain is zeroed out. The clusters themselves are not wiped on normal file deletion. That gives us a good chance to recover the files. All of the information needed to locate the file is still in the directory, but it is hidden to the user.
The only time you normally have problems is when a deleted file is fragmented.
The Boot Sector
The information about the file system, including cluster size, sector size, etc. is located in the boot sector.
File Slack: For a four-cluster sector and a very, very small file, it could have file slack in the following form:
Also, when you start to get up to 32k clusters, small files start to take up 32k when they only need a few hundred bytes. Over a whole disk you can have a lot of waste and inefficiency because of this.
In NTFS, you'll still have a boot sector with cluster sizes and other fundamental information about the file system. Some of the stuff in the FAT model that's "fudged" gets pulled apart.
Windows 2000 put the Master File Table at the front of the drive, with a mirror file in the middle of the drive with only the first directory containing critical information.
The Bitmap is used to determine allocation/unallocation of clusters.
Deleting Files on NTFS
You go into the Master File Table, find the cluster markings, and unallocate them. The operating system maintains a pointer to the first available slot. The second that you decide to create a new directory or new file, that's the slot that will be assigned. Stuff that has entries high up in the table, that record will be written over very quickly.
The Master File Table
The idea behind the Master File Table (it started out as 32 entries and then jumped to 64 and on up as long as it's full and needs more space) is that the system reserves a chunk of space in which the master file table lives and it won't likely outgrow the reserved space. All directories are non-resident and may be fragmented.
NTFS uses a first-available allocation strategy, and deletions before where the first-available pointer is will change the first-available pointer to point to the deleted file's space on the drive.
Linux, Unix File Systems
Linux defaults to EXT3, but it also uses EXT2 and RIZR? Linux will mount NTFS volumes read-only. The kernels are not yet stable in terms of writing to NTFS (there are some beta programs out there that do it but they can hose the system if they screw up).
EXT3 is a journaling file system, where EXT2 does not do journaling. Journaling keeps track of the major steps taken during the last sessions with a file. That way if the system crashes, you can boot back up to the last known good configuration and recover to the point of the crash. The EXT2 and 3 file systems are based on UFS (Unix File System). UFS is much more complicated than EXT2 and 3. UFS gets to be archaic because it was designed for smaller systems.
UFS is designed to be both fast and reliable, and to be very efficient with small files. Home systems tend to have a lot of small files (~10-12 clusters).
Important Data Structures
Copies of them are stored throughout the system. Just like the MFT is mirrored in the middle of the drive on NTFS, important data structures are copied and scattered throughout the system. The whole files are mirrored, too — not just the first little part of them.
The boot record in Linux is called a Superblock. Linux divides the drive up into block groups and you'll frequently find a copy of the Superblock at the beginning of these block groups. Linux installations use sparse by default, which only puts the copies at the beginning of selected block groups.
On EXT3 drives, changes made to Superblocks are recorded in the journal (so you may find 150 Superblocks in the journal!).
The idea that we're trying to move away from is the amount of drive head movement there is. That's because the information associated with a file isn't stored near the file. You have to go through the global data structure (in NTFS, it's the MFT). In Linux, there is a chunk of information for each block group. It keeps the information in the files local so that head movement is minimized.
Linux also distributes information fairly evenly across the drive (it doesn't use a first-come-first-serve file allocation method).
Partitions still exist in Linux, but now when we have a partition we may lay a file system down on it. That file system will likely be EXT2 or EXT3.
Files may be actual files or hard links, and it's impossible to tell which is which (i.e. two files may point to the same data). There is a counter that keeps track of the number of files that point to a certain piece of data. You will only know whether more than one file points to data by looking into the Inode information.
There are three categories of optional features these file systems may have:
- Compatible Features — existence of a journal. You can mount an EXT3 as an EXT2 (just ignore the journal). A compatible feature will say "this is a feature I can ignore if I have to, but I can still mount and access the files on this system."
- Incompatible Features — e.g. Compression. You might not be able to mount it if you do not understand the compression. These features will disallow the File System from being moutned.
- Read-Only compatible — Under these circumstances you can mount a system read-only but you can't write to it. The type of thing you would find here is large file support. Certain kinds of large file support is read-only compatible (read and understand but not write). Directory structures are not required to be sorted. If you were to mount one that had sorted directories and you tried to write but you didn't know how to use sorted directories, you would mess up some stuff!
The first data structure we should be concered with is the Superblock (analogous to the Boot Record). It is located 1024 bytes from the beginning of the drive. Unlike the boot record, there is no boot code in the Superblock. In the 1024 bytes before the Superblock contains the boot code. Its contents are basic size and configuration information. You'll find copies of it at the beginning of many (if not all) of the block groups.
The Superblock has a signature, which you can search for and find candidate 1024 byte blocks in case the first one got corrupted. Copies of the Superblock arent' all updated at the same time. On top of that, they contain information about which block group they're in so they won't have the same hash value. You must find them by signature and location.
What do we need to know about a block if it's a collection of sectors? How many sectors are in there?? In a 1.44 floppy, there's one sector per cluster and in a 720k floppy there are 2. So it affects your computation there just as it does here. The typical block sizes that you'll find are 1024, 24GB, 4096.
- The total number of blocks in the whole file system…
- the number of blocks per block group…
- the number of reserved blocks preceding the first block group…
- the total number of inodes in the system…
- number of inodes per block group…
- and number of sectors per block are all located in the Superblock.
There is more information in the Superblock, but these are the most important pieces of data for now.
0xEF53 is in bytes 56 and 57. This is on page 405 in the white text book.
The block bitmap manages just the blocks in the Block Group. The Inode Bitmap manages the allocation status of the inodes in the table. The group descriptor contains information describes the group just like the superblock describes the drive (how many free blocks are in the group, how many inodes are free, where the block and inode bitmaps start, etc). If you delete a file in a busy block and it doesn't free up enough information to make the block less than average on the busy scale, that block won't be overwritten for a long time (with some exceptions, of course).
The first issue about inodes is one you'd probably expect: they're all the same size. The size is be defined in the superblock. One inode will be allocated to each file and/or directory. Everything has at least one primary inode. Each inode has a number. No two inodes will have the same number as another (they're numbered sequentially down the drive).
In the first group, inodes 1-10 are reserved. The first non-reserved inode will typically point to the superblock. #2 out of the reserved inodes points to the root directory. Inode #1 keeps track of bad blocks. This used to be an interesting place to hide stuff because imaging tools ignored the bad inode group. Bad guys can make inodes in the bad inode block point to good blocks and the tools didn't pick up on this. Now, tools check to see if bad blocks are really bad. If you're on EXT3, inode #8 points to the journal. It's easy to ignore #8 if you want to.
Each inode is the same size and also has the same break-down (fields). It is possible for extended attributes to be set, and if that's the case they'll be stored outside the inode. There will have to be a flag set to show that there are extended attributes. Inside the inode you'll find:
- File size
- Ownership indicator (like GUID number) *Can find the owner in the password file… See Password Data, below.
- Temporal information like MAC (Modify, Access, Change — NOT create!) times and deletion time. *See Time Data below.
- Mode field — typically contains stuff like the file type or link type, if applicable
- Basic permissions — in typical *nix systems, users are members of groups. You can set Read, Write, Execute access for a particular User, Group, and All Users. There are user and group owners, which may have different permissions.
- Link Count — the number of directory entries identifying this inode as the head node for a file. Only hard links affect the link count.
The password information is in /etc/passwd. Ownership in an inode doesn't necessarily reflect the fact that the user created the file or even knows it's there because there's a change ownership function you can use to change the ownership of a file.
You may go to the passwd file and there's nothing there. The ID number may not have a user associated with it. Somebody probably went to the web and pulled down a tarball and opened it and the files had ownership associated with them for users on another system.
Access (A) time indicates the time the file was last accessed. Last Modify (M) time is the last time the file content was modified. Last Changed (C) time is the last time the metadata was changed. There's also a deletion time.
Notice that there are no file names in the inodes. One of the reasons is that file names may be allowed to be dynamic linked and there's no room in the inodes for dynamic links. You can't go outside the inode like you can with a non-resident entry in an MFT record. You won't see dynamic things in the inode.
Directory entries are located close to their data. Hopefully, if a directory is in a group, the files will be in the group as well.
In addition to the above, "primary" or "direct" Inodes have 12 direct pointers to content blocks. They will have 1 indirect pointer, 1 double indirect pointer, and 1 triple indirect pointer.
Indirect pointers are pointing to 12 other inodes. A double indirect points to an inode that points to 12 other inodes. By the time you get out to the triple (which points to 12 doubles), you have 124 blocks being pointed to.
A fairly simplistic and incomplete version of this:
Files are typically grouped in the same group with a parent directory. This prevents having to move the read head a lot. If it is a new directory, you use that "search for a less used group" function and the file/directory is put there.
With the move command, the data doesn't actually move. The old directory entry is killed and a new one is created.
File Deletion under EXT2/3
When you delete a file, the inode status is set to zero. If a process has a hold of the file, it doesn't unallocate the inode. It breaks the link between the directory entry and the inode. Now you have a file without a parent (an orphan). There's an inode orphan list in the Superblock. When you reboot the computer, the orphans will be unallocated. If you catch it before the reboot, nothing's gone.
There's a difference between EXT2 and EXT3 in terms of unallocating an inode. In EXT3, the file size is set to 0 and the data pointers are wiped. If you recover the inode, you'll have a heck of a time finding the content blocks because the pointers are wiped. EXT2 doesn't wipe the pointers or the file size (similar to FAT).
M, C, and D time are updated to reflect the time of deletion. If the deletion is due to a Move, the A time will be updated as well. If you move a file to another volume, the M time is changed to reflect that.