Data Structures with regard to File Systems

[Mucman]

I would really like to know the low-low-low level details on how the HD file structure works. We just touched on the subject in one of my classes which mentioned the B-Trees is used heavily in file system architecture.

I would like to know what is acually contained in the MBR, and what does the FAT look like? Does the analogy work : FAT is to file names as DNS is to domain names?

Does the FAT point to the starting block of a file? Is that a node in a B-Tree? What happens when you type del *.*? Is it just removing a bunch of pointers? Is that how undelete works? Does the data still exist on the HD but it does not have any pointers pointing at it?

As you can see I am really confused about this topic, but I would really like to get into the nitty gritty of it. If anyone has any good links I would appreciate it.

Thanks in advance!

 

[CTho9305]

the mbr contains some CPU instructions (generally a jump instruction, which jumps to the start of the actual operating system) and information about the drive/partiton.

I can speculate about filesystems... they must have two things
1. a map of used/unused space. how this is done without wasting 1/8th the hard drive space is beyond me. well, actually if you consider the way its done with clusters, you only need like 1/128k of the space of the drive (not that bad - 2 meg for a 30 gig hd)
3. a DNS-style lookup saying "this file starts here and continues here, there, and somewhere else"

 

[Mucman]

nice quote

Would the jump instruction be to the boot.ini file? How does it know where the boot.ini file is though?

 

[Noriaki]

<< What happens when you type del *.*? Is it just removing a bunch of pointers? >>

Essentially, yes.



<< Is that how undelete works? Does the data still exist on the HD but it does not have any pointers pointing at it? >>

That is exactly how undelete works. No data is deleted when you delete a file. You delete the file that space is marked as free, and eventually will get written over. Until it does get written over the bits are still the same as what was in the file.


Ok that stuff (at least for FAT) I know is true...I'll toss out some thoughts here...I'm not 100% sure on this stuff though:
The FAT contains a pointer to the beginning of a file.
I'm not sure if the FAT tells you were every piece of the file is though. The trailing bits of a cluster could be a pointer to the next cluster in the file. I'm not sure which way it works on current file systems though.


I think which data structure is used depends on the file system, but B-Tree seems a likely candidate for current systems.

 

[thorin]

&quot;Does the FAT point to the starting block of a file?&quot;

Yes it lists the first block and the last few bits of that block list the location of the next block, etc etc...

&quot;What happens when you type del *.*? Is it just removing a bunch of pointers? Is that how undelete works?&quot;

The first character of the file name is changed, I don't remember what it is changed to but it's like a ! or ?

&quot;Does the data still exist on the HD but it does not have any pointers pointing at it?&quot;

Yes the data isn't actually removed, the entry in the FAT for that file is simply ignored because it start with ! or ? (as mentioned above). When you &quot;undelete&quot; a file you simply rename it back to what it originally was (of course this only works if the file or portions of it have not been over written in the mean time).

Thorin

 

[Mucman]

Thanks for the replies! So how exactly does a B-Tree hold all the info?
Does a node equate to an entire file? What would the pointers point to?

I found a really good site on someones filesystem they created
www.namesys.com

I got a lot of reading to do!

 

[Mapidus]

The FAT (File Allocation Table) is not implemented as a B-Tree structure. I believe it is implemented as an indexed table.

The NTFS equivalent to the FAT is the MFT. I believe the MFT is implemented with a B-Tree structure.

Macintosh HFS uses a B-Tree structure also I think.

 

[Mapidus]

To elaborate further about FAT:

The FAT is a table stored at the beginning of each partition. It is an indexed table with one entry for each disk block. A directory entry stores the first block of the file. Each entry in the FAT table can be thought of as a linked-list pointer. Knowing the first block of a file, one can use the FAT to find all blocks of the file.


Lets say you have a FAT like this:

index 1 2 3 4 5 6 7 8 9
entry 0 0 4 5 6 9 8 e e

If your files first block is 3, then from the FAT you can determine that the disk blocks that make up your file are: 3, 4, 5, 6, and 9.

 

[RedBeard0531]

You should read the AT FAQs about defrag and partitioning.

 

[OhioDude]

Hi, Mucman --

Just a little more info for you on the MBR. I didn't see where anybody answered your follow-up question so I'll give it a stab. (Keep in mind that this explanation applies to x86 architecture and vanilla single boot installations. Multi-boot scenarios or installations where special partitioning software is installed (like Partition Magic) complicate the boot sequence slightly.)

The MBR contains the disk signature, the partition table, and the MBR code that CTho referred to. The MBR code performs about four functions. It locates the boot partition from the data stored in the partition table, then locates the first sector contained in the boot partition, makes a copy of that sector in memory, and then transfers control to the code stored in that sector. (BTW the first sector in the boot partition is referred to as the boot sector.) The boot sector code is nothing more that yet another small set of instructions that finds and loads the basic boot code for the installed operating system and transfers execution to that code.

Now, what subsequent code is located and loaded by the boot sector code depends entirely on the OS installed on the disk. If there is no OS loaded, you'll probably see that familiar &quot;Non-system disk or disk error&quot; message you get when you leave a non-OS floppy in your diskette drive and reboot. If MS-DOS is the OS, the boot sector code will locate and load IO.SYS. NT and Win2k boot sector code will locate and load NTLDR. (I don't know off hand what it would be on Linux and other Xnix'es.)

If you're really interested in the actual structure of the partition table and the disk signature, there are some excellent articles in the MS knowledge base. Just search the MS site for &quot;MBR&quot; and/or &quot;boot sector&quot;.

Hope this helps you out some.

 

[CTho9305]

for most linux people, the MBR would load LILO, which loads the linux kernel (or others, in multi-boot situations) and can pass it parameters

 

[Mucman]

Thanks OhioDude! That was very informative.

I am still wondering how the actual Data Structure of the file system looks like though. If it is a tree, what is contained in the node? Is a node a block, or is it an entire file... I am going to check the MS Knowledge base and see what I can find on that...

 

[Mapidus]

Mucman:
As in my post earlier, FAT is not a tree. Also I gave a description of the data stored in the FAT.

As to the question about what data is stored in the nodes of a tree based system, it depends on the file system. Generally, most of these systems, only store information about the blocks of a file, this is to keep the table or tree small enough to cache in memory for reasonable random access performance. There are cases where data is stored in the nodes entries themselves as can be seen where if the file is smaller than 4K in an NTFS system, it is stored directly in the MFT. The reason for this is the pointer information is already 4K or greater, so storing the data somewhere else and then pointing to it would take up more space then storing it right in the node. Larger files are stored in other places though.

 

[CTho9305]

FAT looks more like a linked-list than a tree to me... although I wonder where/how it stores directory info. I can think of one way to do it (a tree, of course), but the issue there is that if a pointer breaks in a near-root branch, that whole branch goes off to never-never land).