OSDev.org

I need some abstract viewpoints here... lately I've been thinking of files, when stored, on the HDD. I've been thinking of a different way to do it, but there is one thing I don't know that I need to know.

When a file is stored in different sectors, how are they sorted when a file is located? Basically the filesystem would suggest that a new address is stored somewhere to load each sector, but as the file gets larger, then that means more addresses would need to be added to the list.

How would an OS find all the addresses for a file's sectors? It sounds to me like there would be a maximum file size limit if this is the case?

How are file sectors organized logically?

How does a file's sectors get stored so it can be loaded later?

Storing the list of data sectors/fragments is one of the primary jobs of an inode. Different filesystems use different structures to store this list, but in general a B-tree-like structure is the most common, because it allows O(logn) seek times to an arbitrary block and takes advantage of spatial locality within blocks well. Frequently though, many fragments are stored within the inode block itself, because small files with just a couple blocks are common. I think simpler filesystems like FAT use a linked list instead of a B-tree, with the natural performance hit for seeking into a large file.

Storing the information within the data sectors would be highly inefficient. Suppose you wanted to seek to the middle of a large file occupying several hundred sectors. You would have to read all of those sectors in turn. In practice the link information is stored in a separate area - inodes, FAT, etc. This linking data will occupy fewer sectors, so a seek can be much more efficiently.

Okay, but for an inode to be stored, it would be stored in a table I presume?

I can see the uses, and how it would work, but an inode would have to be stored in order for the partitions to be listed, therefore there would be a set limit to how much can be stored, and would depend on the size of the HDD itself?

The addresses for each inode would have to be stored in another table which size can vary depending on how many inodes are created?

I recommend you read how ext2 works at http://www.nongnu.org/ext2-doc/ext2.html - This is a good introduction to how real Unix filesystems work at the data structure level. Once you understand the data structure, you're well on your way.

"I want to implement file systems differently but I don't know what file systems are."

LadyTemoshi wrote:therefore there would be a set limit to how much can be stored, and would depend on the size of the HDD itself?

Correct. For all file systems ever invented there is a set limit to how much can be stored and that depends, intimately, on the size of the HDD itself. Solve that problem and you will have a place in the computing Hall of Fame.

"Practical File System Design with the Be File System" should help you. It is available for free download here: http://www.nobius.org/~dbg/

Love4Boobies wrote:"I want to implement file systems differently but I don't know what file systems are."

I do know what file systems are, but I have never read up on them. I have my own idea of a file system. I am asking these questions to understand how other file systems work, trying to learn, not remain stupid.

I just figured I'd ask here since I'm starting to read up on it.

I have no problem with you wanting to learn about them. Good for you. I was pointing out that you said that you wanted to implement them differently although you don't yet know how they are currently implemented. That doesn't make sense.

Craze Frog wrote:"Practical File System Design with the Be File System" should help you. It is available for free download here: http://www.nobius.org/~dbg/

Start by reading this. All the basics are laid out well in that book.

That's a nice book but it unfortunately serves as an example, for the most part. It doesn't tell the whole story; only the story of BFS. You should* use it as a supplement to an operating system design book (for context) and then go even further down the rabbit hole with research papers and/or existing file system designs.

Examples of topics not covered in that book: distributed file systems, transactional file systems, database file systems, clustered file systems, versioning, compression, encryption, and file systems that target less popular storage devices (e.g., tapes).

* - This obviously depends on your goals. I assumed you want a deep understanding of current file system technologies, since you said you might want to implement something different.

Love4Boobies wrote:Examples of topics not covered in that book: distributed file systems,

Not necessary for beginner's overview of how filesystems work.

Love4Boobies wrote:transactional file systems, database file systems, clustered file systems, versioning, compression, encryption, and file systems that target less popular storage devices (e.g., tapes).

Ditto.

Love4Boobies wrote:* - This obviously depends on your goals. I assumed you want a deep understanding of current file system technologies, since you said you might want to implement something different.

Learn to walk before you learn to run.

Of course a beginner doesn't need to know everything; that's why I included the footnote. Mentioning a few technologies not covered in the book might serve as a good starting point for his future research on the topic. I obviously didn't mean that's all novice stuff.

Why did you break my enumeration in two if you had the same thing to say about all items?

Love4Boobies wrote:Of course a beginner doesn't need to know everything; that's why I included the footnote. Mentioning a few technologies not covered in the book might serve as a good starting point for his future research on the topic. I obviously didn't mean that's all novice stuff.

Why did you break my enumeration in two if you had the same thing to say about all items?

I had intended to go over each one of them separately, but then folded 'em all into a head and a tail.