A simple file system in Nachos

We define two separate implementations of the file system.

The “STUB” version just re-defines the Nachos file system operations as operations on the native UNIX file system on the machine running the Nachos simulation. This is provided in case the multiprogramming and virtual memory assignments (which make use of the file system) are done before the file system assignment.

The other version is a “real” file system, built on top of a disk simulator. The disk is simulated using the native UNIX file system (in a file named “DISK”).

In the “real” implementation, there are two key data structures used in the file system. There is a single “root” directory, listing all of the files in the file system; unlike UNIX, the baseline system does not provide a hierarchical directory structure. In addition, there is a bitmap for allocating disk sectors. Both the root directory and the bitmap are themselves stored as files in the Nachos file system — this causes an interesting bootstrap problem when the simulated disk is initialized.

In filesys.h in filesys directory, we see:

#ifdef FILESYS_STUB 	// Temporarily implement file system calls as 
				// calls to UNIX, until the real file system implementation is available
// ...............................
#else // FILESYS
// ...............................

Grep to see:

~/OS/filesys# grep FILESYS_STUB *
grep: arch: Is a directory
filesys.h:#ifdef FILESYS_STUB           // Temporarily implement file system calls as 
Makefile.local:DEFINES := $(DEFINES:FILESYS_STUB=FILESYS)
openfile.h:#ifdef FILESYS_STUB                  // Temporarily implement calls to 
grep: test: Is a directory

FILESYS_STUB is not defined, so it uses FILESYS .

Reading Code

Disk Manager

Code in machine directory.

disk.cc

In first few lines we see:

#define MagicNumber		0x456789ab
#define MagicSize		sizeof(int)
#define DiskSize		(MagicSize + (NumSectors * SectorSize))

Disk::Disk(char* name, VoidFunctionPtr callWhenDone, _int callArg) {
    int magicNum;
    int tmp = 0;
    DEBUG('d', "Initializing the disk, 0x%x 0x%x\n", callWhenDone, callArg);
    handler = callWhenDone;
    handlerArg = callArg;
    lastSector = 0;
    bufferInit = 0;
    fileno = OpenForReadWrite(name, FALSE);
    if (fileno >= 0) {		// file exists, check magic number 
        Read(fileno, (char *) &magicNum, MagicSize);
		ASSERT(magicNum == MagicNumber);
    } else {				// file doesn't exist, create it
        fileno = OpenForWrite(name);
		magicNum = MagicNumber;  
		WriteFile(fileno, (char *) &magicNum, MagicSize); // write magic number
		// need to write at end of file, so that reads will not return EOF
        Lseek(fileno, DiskSize - sizeof(int), 0);	
		WriteFile(fileno, (char *)&tmp, sizeof(int));  
    }
    active = FALSE;
}

And also see define in disk.h :

#define SectorSize 		128	// number of bytes per disk sector
#define SectorsPerTrack 32	// number of sectors per disk track 
#define NumTracks 		32	// number of tracks per disk
#define NumSectors 		(SectorsPerTrack * NumTracks)

The first 4 bytes is MagicNumber (sizeof (int) , which is 4 bytes in both 32-bit and 64-bit systems) , implying that this is a Nachos Disk. The NumSectors * SectorSize is $(32\times32)\times128$ , every sector is 128 bytes. So the No. 0 Sector starts from 4, ends with 131.

And the Disk size is $4+1024\times128=128{\rm KB}={\rm 0x80KB}$ .

void Disk::ReadRequest(int sectorNumber, char* data)
void Disk::WriteRequest(int sectorNumber, char* data)

The two operations are similar: calculate how long it takes by its size, check if it’s ready then seek its sector and then read/write, update the sector position, report status and then open interrupt.

File System

The code is in filesys directory.

filehdr.h

class FileHeader {
private:
	int numBytes;				// Number of bytes in the file
	int numSectors;				// Number of data sectors in the file
	int dataSectors[NumDirect];	// Disk sector numbers for each data block in the file
};

We see three things in file header: the size of the file in bytes, how many sectors the file locates, and which sector each block of the file locates.

filesys.cc

FileSystem::FileSystem(bool format)

If format is true, it means the file system needs to be formatted: new BitMap, new Directory, associated with the file header. If not, just open the files representing the bitmap and directory.

bool FileSystem::Create(char *name, int initialSize)

It creates a new file with a new sector and some space with a filename, failed if filename already exists or no free entry or no free space. The default directory entry is 10.

OpenFile * FileSystem::Open(char *name)

It first finds the file from directory, the result returns its sector. If not found, return null.

FileSystem::Remove(char *name)

It deletes the space for its header, along with the space. And write back the change to directory, bitmap. Return TRUE if the file was deleted, FALSE if the file wasn’t in the file system.

directory.h

The directory is a table of fixed length entries. Each entry represents a single file, and contains the file name, and the location of the file header on disk.

class DirectoryEntry {
public:
	bool inUse;						// Is this directory entry in use?
	int sector;						// Location on disk to find the FileHeader for this file 
	char name[FileNameMaxLen + 1];	// Text name for file, with +1 for the trailing '\0'
};

class Directory {
private:
	int tableSize;				// Number of directory entries
	DirectoryEntry *table;		// Table of pairs:  <file name, file header location> 
	int FindIndex(char *name);	// Find the index into the directory table corresponding to "name"
};

So the directory is a 1-D array which contains the entries representing a file.

Commands

In main.cc in threads directory :

#ifdef FILESYS
	if (!strcmp(*argv, "-cp")) { 		// copy from UNIX to Nachos
	    ASSERT(argc > 2);
	    Copy(*(argv + 1), *(argv + 2));
	    argCount = 3;
	} else if (!strcmp(*argv, "-p")) {	// print a Nachos file
	    ASSERT(argc > 1);
	    Print(*(argv + 1));
	    argCount = 2;
	} else if (!strcmp(*argv, "-r")) {	// remove Nachos file
	    ASSERT(argc > 1);
	    fileSystem->Remove(*(argv + 1));
	    argCount = 2;
	} else if (!strcmp(*argv, "-l")) {	// list Nachos directory
            fileSystem->List();
	} else if (!strcmp(*argv, "-D")) {	// print entire filesystem
            fileSystem->Print();
	} else if (!strcmp(*argv, "-t")) {	// performance test
            PerformanceTest();
	}
#endif // FILESYS

-cp : copy a file to Nachos, similar to cp . -cp (from) (to) , copy a file in the host system, to somewhere in Nachos file system, also rename it.

-p : print the contents of a file, similar to cat . -p filename .

-r : remove a file by filename, similar to rm . -r filename .

-l : list all the filenames in the current directory, similar to ls .

-D : print the entire file system info.

-t : performance test.

and also -f , which I can’t find where it is:

-f : causes the physical disk to be formatted.

The Unix commands

od : Octal Dump. Displays a file in octal (base 8) format by default.

hexdump : Hexadecimal Dump. Displays the contents of binary files in hexadecimal, decimal, octal, or ASCII.

The experiment

Test file

In filesys/test , there are three test files, test them:

~/OS/filesys# od test/small
0000000 064124 071551 064440 020163 064164 020145 070163 064562
0000020 063556 067440 020146 072557 020162 064544 061563 067157
0000040 062564 072156 005056
0000046

~/OS/filesys# hexdump -c test/small
0000000   T   h   i   s       i   s       t   h   e       s   p   r   i
0000010   n   g       o   f       o   u   r       d   i   s   c   o   n
0000020   t   e   n   t   .  \n                                        
0000026

~/OS/filesys# hexdump -C test/small
00000000  54 68 69 73 20 69 73 20  74 68 65 20 73 70 72 69  |This is the spri|
00000010  6e 67 20 6f 66 20 6f 75  72 20 64 69 73 63 6f 6e  |ng of our discon|
00000020  74 65 6e 74 2e 0a                                 |tent..|
00000026

Also do the same to medium and big if you interest.

The Nachos file system

In filesys directory, make . Then do the follow:

1. Initialize the Disk.

   ~/OS/filesys# ./nachos -f

2. Show the disk info.

   ./nachos -D
   *** thread 0 looped 0 times
   *** thread 1 looped 0 times
   *** thread 0 looped 1 times
   *** thread 1 looped 1 times
   *** thread 0 looped 2 times
   *** thread 1 looped 2 times
   *** thread 0 looped 3 times
   *** thread 1 looped 3 times
   *** thread 0 looped 4 times
   *** thread 1 looped 4 times
   Bit map file header:
   FileHeader contents.  File size: 128.  File blocks:
   2 
   File contents:
   \1f\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0
   Directory file header:
   FileHeader contents.  File size: 200.  File blocks:
   3 4 
   File contents:
   \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0
   \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0
   Bitmap set:
   0, 1, 2, 3, 4, 
   Directory contents:
   
   No threads ready or runnable, and no pending interrupts.
   Assuming the program completed.
   Machine halting!
   
   Ticks: total 5420, idle 4990, system 430, user 0
   Disk I/O: reads 10, writes 0
   Console I/O: reads 0, writes 0
   Paging: faults 0
   Network I/O: packets received 0, sent 0
   
   Cleaning up...

3. Run OD :

   ~/OS/filesys# od DISK
   0000000 104653 042547 000200 000000 000001 000000 000002 000000
   0000020 000000 000000 000000 000000 000000 000000 000000 000000
   *
   0000200 000000 000000 000310 000000 000002 000000 000003 000000
   0000220 000004 000000 000000 000000 000000 000000 000000 000000
   0000240 000000 000000 000000 000000 000000 000000 000000 000000
   *
   0000400 000000 000000 000037 000000 000000 000000 000000 000000
   0000420 000000 000000 000000 000000 000000 000000 000000 000000
   *
   0400000 000000 000000
   0400004

4. Run hexdump :

   ~/OS/filesys# hexdump -c DISK
   0000000   � 211   g   E 200  \0  \0  \0 001  \0  \0  \0 002  \0  \0  \0
   0000010  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0
   *
   0000080  \0  \0  \0  \0   �  \0  \0  \0 002  \0  \0  \0 003  \0  \0  \0
   0000090 004  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0
   00000a0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0
   *
   0000100  \0  \0  \0  \0 037  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0
   0000110  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0
   *
   0020004

   ~/OS/filesys# hexdump -C DISK
   00000000  ab 89 67 45 80 00 00 00  01 00 00 00 02 00 00 00  |..gE............|
   00000010  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
   *
   00000080  00 00 00 00 c8 00 00 00  02 00 00 00 03 00 00 00  |................|
   00000090  04 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
   000000a0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
   *
   00000100  00 00 00 00 1f 00 00 00  00 00 00 00 00 00 00 00  |................|
   00000110  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
   *
   00020004

   Clearly we see nothing but the initial info.

5. Copy small :

   ~/OS/filesys# ./nachos -cp test/small small

   Check it by list :

   ~/OS/filesys# ./nachos -l
   *** thread 0 looped 0 times
   *** thread 1 looped 0 times
   *** thread 0 looped 1 times
   *** thread 1 looped 1 times
   *** thread 0 looped 2 times
   *** thread 1 looped 2 times
   *** thread 0 looped 3 times
   *** thread 1 looped 3 times
   *** thread 0 looped 4 times
   *** thread 1 looped 4 times
   small

   We see the filename: small.

6. Check the DISK :

   ~/OS/filesys# hexdump -C DISK
   00000000  ab 89 67 45 80 00 00 00  01 00 00 00 02 00 00 00  |..gE............|
   00000010  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
   *
   00000080  00 00 00 00 c8 00 00 00  02 00 00 00 03 00 00 00  |................|
   00000090  04 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
   000000a0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
   *
   00000100  00 00 00 00 7f 00 00 00  00 00 00 00 00 00 00 00  |................|
   00000110  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
   *
   00000180  00 00 00 00 01 00 00 00  05 00 00 00 73 6d 61 6c  |............smal|
   00000190  6c 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |l...............|
   000001a0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
   *
   00000280  00 00 00 00 26 00 00 00  01 00 00 00 06 00 00 00  |....&...........|
   00000290  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
   *
   00000300  00 00 00 00 54 68 69 73  20 69 73 20 74 68 65 20  |....This is the |
   00000310  73 70 72 69 6e 67 20 6f  66 20 6f 75 72 20 64 69  |spring of our di|
   00000320  73 63 6f 6e 74 65 6e 74  2e 0a 00 00 00 00 00 00  |scontent........|
   00000330  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
   *
   00020004

   from 0x184: 01 00 00 00 05 00 00 00 73 6d 61 6c 6c
0x01 stands for the sector is in use, 0x05 stands for the contents is in Sector 5, 0x736d616c6c is the ASCII code for its file name.

7. Remove small :

   ~/OS/filesys# ./nachos -r small

   Check it by list :

   ./nachos -l
   *** thread 0 looped 0 times
   *** thread 1 looped 0 times
   *** thread 0 looped 1 times
   *** thread 1 looped 1 times
   *** thread 0 looped 2 times
   *** thread 1 looped 2 times
   *** thread 0 looped 3 times
   *** thread 1 looped 3 times
   *** thread 0 looped 4 times
   *** thread 1 looped 4 times
   No threads ready or runnable, and no pending interrupts.

   Removed.

8. Check the DISK :

   ~/OS/filesys# hexdump -C DISK
   00000000  ab 89 67 45 80 00 00 00  01 00 00 00 02 00 00 00  |..gE............|
   00000010  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
   *
   00000080  00 00 00 00 c8 00 00 00  02 00 00 00 03 00 00 00  |................|
   00000090  04 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
   000000a0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
   *
   00000100  00 00 00 00 1f 00 00 00  00 00 00 00 00 00 00 00  |................|
   00000110  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
   *
   00000180  00 00 00 00 00 00 00 00  05 00 00 00 73 6d 61 6c  |............smal|
   00000190  6c 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |l...............|
   000001a0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
   *
   00000280  00 00 00 00 26 00 00 00  01 00 00 00 06 00 00 00  |....&...........|
   00000290  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
   *
   00000300  00 00 00 00 54 68 69 73  20 69 73 20 74 68 65 20  |....This is the |
   00000310  73 70 72 69 6e 67 20 6f  66 20 6f 75 72 20 64 69  |spring of our di|
   00000320  73 63 6f 6e 74 65 6e 74  2e 0a 00 00 00 00 00 00  |scontent........|
   00000330  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
   *
   00020004

   We see inuse is set to 0, but the contents remain.

9. Do the same for medium :

   ~/OS/filesys# ./nachos -cp test/medium medium
   ~/OS/filesys# hexdump -C DISK
   00000000  ab 89 67 45 80 00 00 00  01 00 00 00 02 00 00 00  |..gE............|
   00000010  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
   *
   00000080  00 00 00 00 c8 00 00 00  02 00 00 00 03 00 00 00  |................|
   00000090  04 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
   000000a0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
   *
   00000100  00 00 00 00 ff 00 00 00  00 00 00 00 00 00 00 00  |................|
   00000110  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
   *
   00000180  00 00 00 00 01 00 00 00  05 00 00 00 6d 65 64 69  |............medi|
   00000190  75 6d 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |um..............|
   000001a0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
   *
   00000280  00 00 00 00 98 00 00 00  02 00 00 00 06 00 00 00  |................|
   00000290  07 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
   000002a0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
   *
   00000300  00 00 00 00 54 68 69 73  20 69 73 20 74 68 65 20  |....This is the |
   00000310  73 70 72 69 6e 67 20 6f  66 20 6f 75 72 20 64 69  |spring of our di|
   00000320  73 63 6f 6e 74 65 6e 74  2e 0a 54 68 69 73 20 69  |scontent..This i|
   00000330  73 20 74 68 65 20 73 70  72 69 6e 67 20 6f 66 20  |s the spring of |
   00000340  6f 75 72 20 64 69 73 63  6f 6e 74 65 6e 74 2e 0a  |our discontent..|
   00000350  54 68 69 73 20 69 73 20  74 68 65 20 73 70 72 69  |This is the spri|
   00000360  6e 67 20 6f 66 20 6f 75  72 20 64 69 73 63 6f 6e  |ng of our discon|
   00000370  74 65 6e 74 2e 0a 54 68  69 73 20 69 73 20 74 68  |tent..This is th|
   00000380  65 20 73 70 72 69 6e 67  20 6f 66 20 6f 75 72 20  |e spring of our |
   00000390  64 69 73 63 6f 6e 74 65  6e 74 2e 0a 00 00 00 00  |discontent......|
   000003a0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
   *
   00020004

   It covers the sector not used by small.

Also big can be tested, but I don’t list the code because it just does the same thing. The result leading to thinking matters.