Introduction

Hello Readers,

Welcome to FilesystemsForYou (FFY). In this journal we shall explore the world of file systems which is made out to be one of the most complex sub systems of an operating system. It is rich with varieties of file systems varying in their complexity, performance, reliabilty, popularity, and the target devices they are deployed on, to name a few differentiators.

This journal is primarity meant to serve fellow platform enthusiasts like myself to start learning this file systems from absolute basics. So I intend to cover this subject by building a strong base and not attaching the sub system to a particular operating system but understand file system alone as a independent sub system trying to a solve a particular problem. However, once the basic understanding is obtained, I wish to delve into operating system specific nuances of the file system and I choose linux as a case study for the following reasons.

1. Linux has and will continue to support all the file systems. File systems are just too many in numbers. Each with a distinct advantage and trade offs. There is not a single file system that is suitable for all purposes. Linux has been designed to plug in any file system. Thus studying file systems under the linux umbrella will help appreciate the breadth the file system and it's varying requirements.

2.  Linux frame work is completely object oriented. The framework abstracts lower level variations and complexities of the file systems through a layer called virtual file system. This abstrastion maximises user experience.No matter what filesystems are used underneath, for a linux user it seems there is no difference. There are many such abstractions in linux that makes it the reliable, fast, secure and easy to use operating system.

3. Linux evolves and evolves at a very fast rate. Thanks to the developer community that is helping us in this evolution by constantly updating and adapting the operating to system to cater to users accross the globe. A chance to study such a project will be exciting.

4. The application areas of linux is vast. Right from consumer front to research community, everyone these days is using linux. Study of file systems under linux enables us to see what makes linux so friendly.

This project is supposed to build file systems knowledge of a person ground up. So please read the journal from chapter one through the end. However if you have had some prior knowledge and are looking to study a particular aspect of file systems or something specific to linux file systems, you shall do so by jumping to the particular chapter by referring to the index. I will try my best to keep the chapters more cohesive and less coupled and provide hyperlinks as much as possible so that browsing the journal would be easy.

In the coming chapters we shall approach a particular engineering problem and solve it through the files systems. Let's start.

Continue to next post.

Problem

First thing towards solving a problem is to understand it. It is the
understanding of this problem we attempt to do in this chapter. We will see why we need some thing called as a file system. We will then see what is a file system and where it should be placed in the system inorder to solve our problem. The rest of the study as to 'how' and 'which' of the file systems will be dealt with in the future chapters.

Data retention

In computing, we have a procedure, a flow of logic, called a process which is a thread of execution with finite set of instructions to be executed. And we have data that the procedure acts upon to manipulate and transform it into something tangible. The most native method of making a processor execute such a process and to manipulate data is by storing code and data in a special container called as memory. We call it random access memory, RAM. RAM is a semi conductor device capable of storing binary information. At a very fundamental level a semiconductor memory is a decoder chip which decodes a block of bits called address into one or more bits of data.

There is circuitary built to connect such a memory device to processor by binding the address lines and data lines of the processor and of the memory together. Having a such a simple set up would enable to perform only a limited operations on the processor since semiconductor memory such as RAM is a volatile memory and it loses data upon reset. There are situations in almost all practical applications to have data to be retained across resets of the computer.

One part of the problem has been established. We need data retention upon resets.

Large data

Assuming a macro-system capable of multitasking each process is assigned a virtual address space. This space for a few programs might suffice but there are engineering problems that involve data of magnitudes quite larger than the address spaces allocated to a process. This calls for a need to store the data of larger magnitudes elsewhere (Not in RAM). The next part of the problem is Large data.

Concurrency

Another common requirement in multi-tasking environment is ability to share data among processes concurrently. If data is localised to process address space this sharing would be difficult to achieve. So concurrency is the another part of the problem.

We should mark that file system attends these problems by providing a framework to store data on a persistent medium.  This infra-structure should made use of appropriately by other programs in order to provide good user experience.

Having understood the problem we conclude that we must design a system that would help us retain data on a persistant physical medium with a larger capacity and also help us have concurrent access to it. And such a system is called a file system. The reason to call such data as files is simple. If you observe the problem's outlined, it is something that's been dealt with in our lives. It is to do about keeping notes.

Let me elaborate -

Data rerention – Some really blessed people with extra ordinary memory will probably not agree to this but most of us forget things. There is a limit for how long we can remember.

Large Data:

In a social system there are offices, industries,schools and government organisations at work. These systems have to store and operate on enormous amount of data. There is a limit to how much humans can remember.

Concurrency:

Obviously the data should be out in public for those who'd want to see and interpret it. It should made open to all.

The solution we have found in our social system is to keep the data in what are called as files(a piece of paper). We have enforced some rules about organising the data when we write to the files. We index the files and group them based on some common characterisitics and place them under a wrapper and call it a directory. Even inside a file we have mandated to follow a common structure while writing the data on it. So the problem we have outlined earlier has beed solved already in the society and what we should do is to simply copy the principles and apply them in the computer system. We hence call it a file system.

Now. We have addressed why and what of file systems. Let us see as to where we can place the file system in the computing environment. Needless to say the very nature of the file system is to provide generic interfaces for users. File systems interact closely with the hardware that retains the data. All file systems must implement common interfaces and abstract the underlying differences in the type of hardware. All these charecteristics conform to be of system services in nature. Thus file systems go in to a system as one of the sub systems in an operating system.

Files – User view part -1

In this chapter and two more to follow, we study the user view of the files. This part of the study should help a platform developer in the process of designing file system to elucidate requirements from the users.

Files by defintiion are and abstraction mechanism. They provide a way to store information on the disk and read it back later. This must be done in such a way as to shield the users from the differences in the type of hardware, how data is stored and organised.

Let us take different charachteristics of the file and examine them one by one.

First is naminig of the file.

This is a requirement for the file system designer for he must know a way to unambigously resolve a file based on a identity and the best identity at a user level must be something in a readable and friendly form. Thus an important desing consideration is the attributes is file name such as

1. length of the file name : This attribute helps designer to keep appropriate place holder in the data structures in the platform

2. Character sets allowed in the file name: This attribute helps designer to help parse the file name while seeking it through the disks. Limited set implies less effort in parsing but user experience takes a hit and vice versa.

3. Case sensitivity: This attribute helps designer code his logic about resolving the file names. MS-DOS has a view of ignoring the case while UNIX like systems prefer to be case sensitive.

Moving on we dissect the file names into to two parts seperated by '.' (period). As <filename>.<extension>. In practise the <filename> could be anything. A string of literals supported by the file system and <extension> is a string of literals again mostly confined to five numbers tops.

Examples are

Sherlock.mp3, Watson.mpg, MrsHudon.txt.

The extensions are primarily for the user to interpret, to know what sort of files they are. It would wrong to mention “Types of files” in this context as from the platform perspective “Types” of files bear a particular meaning and the files mentioned above fall under the type of files called the “regular files”. Anyways, coming back to user view, the extension serve minimal input to the filesystem while it is important to the user level applications.

For the system having a GUI there is a mechanism by which user can register a particular extention of file to a particular program. This is the mechanism by which GUI launchers help open the files with appropriate programs. In the command line mode we invoke the program and supply the file as parameter and this manner there is no need for the extension to be present. While in GUI mode we assert on a data file and appropriate program is automatically launched. Extensions are here to help users and gurantee that user knows what he is doing. Windows is file extensions aware while UNIX like systems is not.

However some application programs mandate the extensions. This is more so in softwares such as compilers where extensions matter the most in helping the compiler stages to unambigously pick up files for pre-processing, compiling and linking the programs. And for build tools such as Make.

Next we see how the files are really structured.

Strictly speaking filesystem need not worry about the contents of the file. For the contents matter only for the user level programs which operate on it. Hence, modern file systems keep the data raw in the files as written and render the same to user application when read from. This method provides maximum flexibity and most operating systems work this way.

However special cases are present where the files are written into and read from in units called as records. This is of historic signicance where the earlier mainframes used 80 column punch cards. For our design sake we consider unstructured byte streams.

Moving on we have the types of files.

Like mentioned earlier the “type” of file means something particular in file systems domain. I am presenting a super set of file types and this set maps to the types of files in the linux file system. The list however need not be same in every operating system. Idea of this column is to familiarise overselves with taxonamy of files.

While it is reasonably safe to suppose that everything you encounter on a Linux system is a file, there are some exceptions.

1. Regular files: These are regualr user files. Like music, texts, video et cetara.

2. Directories: files that are lists of other files.

3. Special files: the mechanism used for input and output. Most special files are in /dev, we will discuss them later.

4. Links: a system to make a file or directory visible in multiple parts of the system's file tree. We will talk about links in detail.

5. (Domain) sockets: a special file type, similar to TCP/IP sockets, providing inter-process networking protected by the file system's access control.

6. Named pipes: act more or less like sockets and form a way for processes to communicate with each other, without using network socket semantics.

Files – User view part -2

In this chapter will continue to look through the lens of the user and see some more characterics.

File Access.

Historically, when magnetic tapes were the devices used as persitent media, the way to access these devices was sequential. One could not skip to a particular section in the media to access information but has to always start from the beginning and read data in order until desired position. They could be rewound however.

With the introduction of magnetic disks, sequential files became obsolete and random access files dawned. In this method there were explicit indices or keys use to locate the records on the media.

We'd never have to deal with sequential files. We will only be using random access files mostly. There are two ways to specify the position to start reading in the file.

1. The read operation is performed and for every read the position is specified.

2. Using seek operation the position is set and the read operation is performed.

This piece of information bears no significance to a designer now. We all are going to design file systems with Random Access Files.

Next. Although all through the last post and the current we were seeing attributes of files, there are still many special attributes assigned to a file that provide different options to the user. The following is the list.

1. Protection mode: Dictates can access the file.

2. Password: Password if the file is password protected.

3. Creator: Id of the creator of the file.

4. Owner: Id of the current owner of the file.

5. Readonly or read/write

6. Hidden or not

7. System file or a normal file

8. ASCII or binary file

9. Random access or sequential

10. Temporary or permanent

11. Creation time

12. Time of last access

13. Time of last change

14. Current size

15. Maximum size:

Attributes 11 to 13 are useful in scenarios where a tool such as Make must know if there was a change in the source file after it's last build. Then the file will be considered for compilation

Files – User view part -3

We did finalise that file system be from the realm of platform sub systems and in this post we see how as users we can avail the services of the file system as a system service. Or in other words we look at the user level APIs, the platform designers must consider providing to the users. Also called as system calls relating to files.

1. Create. The file is created with no data. The purpose of the call is to announce that the file is coming and to set some of the attributes.
2. Delete. When the file is no longer needed, it must be deleted to free up space on the disk space.
3. Open. Before using a file, a process must open it. The purpose of the call is to allow the file system to fetch the attributes and list of the disk addresses into main memory for rapid access on later calls.
4. Close. When all the accesses are finished, the attributes and disk addresses are no longer needed, so the file should be closed to free up internal table space reserved for the file in the RAM and to leave the file complete with all the data until last set written on the secondary storage.
5. Read. Data is read from file. The bytes are read from the current position. The caller must specify the number of bytes to be read the target buffer in the RAM.
6. Write. Data is written on to the file. The current position matters here too. If the current position is the EOF(End Of File), the file size is increased. If the current position is in the middle, the data is over written.
7. Append. This call is a restricted form of write. It can only add data to the end of the file. Systems that provide a minimal set of system calls do not support this but most of the systems do.
8. Seek. For random access files, a method is needed to specify from where to take the data. One common approach is a system call seek, that repositions the file pointer to a specific place in the file. After this has completedm data can be read from, or written to, that position.
9. Get Attributes. Quite often, processes' involve looking up of some file attributes. Example, Make too. The make tool will need to look at the timestamps of the source files to keep compilation restricted only to those which have been changed.
10. Set Attributes. Some of the attributes are user settable and can be changed after creation. Example, protection mode attribute and file names.
11. Rename. Special case of set attributes dedicated to changing of the name. Not a “must have” command. 

Memory Mapped Files

Having studied the requirements of the users towards managing the files we take a small detour in this chapter to introduce ourselves to a concept called the memory mapped files.

If you're acquainted with the concept of memory mapped I/O this concept is easy to understand. It was found that programmers prefer to read/write on the system memory than to operate on files that are on the external I/O realm. Which is quite justifiable for the simplicity and time effeciency memory read/write offers as against the I/O read/write.

Many operating systems have provided a way to map files into the address space of a running process. Conecptually, we can imagine existence of two system calls, map and unmap. Used to map files into the virtual address space, and unmap them when done processing.

For example, suppose that a file, f, of the length 64 KB, is mapped into the virtual address starting at address 512K. Then any machine instruction that reads the contents of the byte at 512k byte 0 of the file, and so on. Similarly, a write to address 512k + 21000 modifies byte 21000 of the file. When the process terminates file is left on the disk, just as though it had been changes by a combination of seek and write system calls.

What actually happens is that the system's internal tables are changed to make the file become the backing store for the memory region between 512k to 576k. Thus a read from 512k causes a page fault, bringing in page 0 of the file. Similarly, a write to 512k + 1100 causes a page fault, bringing in the page containing that address, after which the write to memory can take place. If that page is evicted by page replacement algorithm, it is written back to the appropriate place in the file. When the process finishes, all mapped, modified pages are written back to their files.

File mapping works the best in a system supporting segmentation. In such a system, each file can be mapped into its own segment and mapped into the virtual address space of the running process so that, byte k in the file corresponds to byte k of the segment. Suppose that a process has to copy contents of a certain file abc to another xyz. The process had two segments, program text and data. The process will map file abc into a particular segment and then creates another segment xyz. Now we need only to copy contents from segment to anothe through a simple copy loop. No need of read write I/O system calls to be made. When it is all done, we can execute the unmap system call and remove the file the address space and exit. The output file xyz is now assured to be present.

Now. The limitations of using memory map for files.

1. From our example, it is hard to know the exact size of the target file in terms of numbet of bytes. Since the unit of data being copied is a page and we could tell only the precise number of pages written. Suppose that the program only uses page 0 and after execution all the bytes are zeroes. We do not know for sure if the number of zeroes actually to be present are 10, 100 or 500.
2. A second problem can occur if a file opened in by one process and opened for conventional reading by another. If the first process modifies a page, that change will not be reflected in the file on disk until the page is evicted. The system has to take great care to make sure the two processes do not see inconsistent versions of file.
3. A third problem is that the file may be larger than a segment, or even larger than entire virtual address space. The only way out is to arrange the map system call to be able to map a portion of a file, rather than a entire file at once. Although this works, it is clearly less satisfactory than mapping the entire file.