CS 111 Lecture 12 File System Implementation

Chang Zhao 304138441

Luyang Liu 304050396

Zongsheng Li 804126172

 

Levels of a traditional file system

How does file name work?

Multiple file systems

Keeping track of free space

 

Levels of a traditional file system

partition

block    8192 bytes                           Fragmentation(Batching)

sector   512 bytes(1956-2014)         4096 bytes(2014- )

 

Problem: what is the down side of huge block:

1. Lack of flexibility

2. If your apps like random accessing, it will do to much I/O

 

Actual file system: suppose we have multiple file systems.

How do we use multiple file systems at the same time?

example:

             cp /usr/bin/sh (ext2)     home/eggert/junk/sh (ext4)

             int ifd = open("/usr/nom/sh" O_RDONLY…)

             int ofd = open("/home/eggert/junk/sh", O_WRONLY/O_CREAT, 0666)

 

How does file name work?

directory for /

                       

directory for /usr

                       

directory for usr/bin

    

also an inode table full of inode entries

 

Special case:

Example: //abc/def

some file systems treat things after double slash as host name. Other treat it just like slash.

 

Problems:

Problem: open /aq2/bin/sh, what if aq2 doesn't exist?

        Ans:   process failed, open filed, returns -1, set enrno = ENOENT

Problem: try to interpolate a file name, but it is not a directory. e.g. aq2/bin/sh, where aq2 is not a directory

       Ans: set enrno = ENOTDIR

Problem: suppose name doesn't start with a  '/' . e.g. home/eggert/junk/sh

       Ans: we can't start with root. Therefore, we strait with working directory

Problem: How do the kernel know my working directory. e.g. my working directory is in ode 39267

      Ans: The kernel know the in ode number because it keep store the working directory in ode number into process table entry.

 

System call: chdir

example  chdir("/bin")      

what does it do?

It change the inode number of current process to the inode number that the director you want it change to.

 

Is there any problem?

Yes, it might cause a classic UNIX bug:

            chdirc int main(int argc, char** argv){

                        if(arg!=2)

                                    error();

                        if(chdir(argv[1]!=0){ //change failed

                                    perror(argv[1]);                                            

                                    return 1;

                        }

                        return 0;

            }                     

            This won't work because it change the directory of the change cmd itself, but not the shell directory.

 

How to solve it?

Make a shell feature (it's actually a built-in now)

 

System call: chroot

example: chroot("/home/eggert/junk");

――it changes the root directory to my directory

 

There is a small problem: you can't access the file above that. Suppose after you do chroot, you wanna do execvp ("/usr/bin/sh"), it will quit.

 

Another problem is: This will cause a security problem.

Suppose I created file

/home/eggert/junk/etc/passwd

/home/eggert/junk/etc/shadow

I then evoke chroot, and run su, sudo. It will check the passwd under the file I specified, so it will fool the system.

To solve this problem: chroot is a privilege system call, it always failed winless you are root.

 

So why root want to do chroot?

It uses it to creat chroot jail!

            example:

            fork()

            chroot("/a/b")

            chdir("/")

            setuid("apache")

            execvp("/usr/bin/apache")

                             

         

All run in the Jail. Web service provider uses it to support multiple web users.

 

                                                           

Multiple file systems

How can we use different file systems for different directory?

 

directory entry stored as

on disk.

 

In kernel RAM, there is a mount table which stores inode number and corresponding file system type.

 

 

parent and child can have different types of file system. We can not cross file system boundary if you are at mount point.

 

       Inode numbers are local to file systems that they are in, therefore to uniquely identify a file, we should use inode number(ino_t) and file system number(dev_t). So finally directory entry looks as below.

 

       Example:

 

Hard link: two different directory entries point at same file

 

Another example:

ln /home/eggert             /home/eggert/junk

This is not allowed in linux. Can not create hard link to directory, leaves can be shared.

Creating links to directory will result in infinite loop when calling find.

 

Keeping track of free space

Recall that BSD file system lay out is as follows:

 

       To keep track of free space, we need to make 3 modifications at the same time.Bitmap,  inode table last modified, data.

This means 3 seeks and 3 writes.

       Can we improve efficiency?

       Yes, in situations that lots of applications are going in parallel.

We can combine two writes together. This means we can decrease 6 writes and 6 seeks to 4 writes and 3 seeks. In 4 writes, one for bitmap(both app1, app2), one for last modified(both app1,app2),one for data of app1, the last for data of app2. 3 seeks are, one for bitmap, one for last modified, last one for data(benefit form allocating block next to each other)