# MP4 – File System
# Team10
## Team member:李侑庭(110062172), 盧思樺(110062272)
| 部分 | 李侑庭 | 盧思樺 |
| --- | --- | --- |
| Trace code | 50% | 50% |
| Implement | 70% | 30% |
| Report | 70% | 30% |
| Testing | 30% | 70% |
# Part I. Understanding NachOS file system
## (1) How does the NachOS FS manage and find free block space? Where is this information stored on the raw disk (which sector)?
* Use OpenFile* object freeMapFile in FileSystem.
```
class FileSystem
{
...
OpenFile *freeMapFile;
...
};
```
* In the constructor of FileSystem, it will open freeMapFile from the FreeMapSector.
Or use Mark() function to mark the sector 0 for the file's header of bitmap, allocate space to bitmap files and write the file's header and file back to disk.
```
FileSystem::FileSystem(bool format)
{
if (format)
{
...
FileHeader *mapHdr = new FileHeader;
PersistentBitmap *freeMap = new PersistentBitmap(NumSectors);
freeMap->Mark(FreeMapSector);
ASSERT(mapHdr->Allocate(freeMap, FreeMapFileSize));
mapHdr->WriteBack(FreeMapSector);
freeMapFile = new OpenFile(FreeMapSector);
freeMap->WriteBack(freeMapFile);
}
else
{
freeMapFile = new OpenFile(FreeMapSector);
...
}
}
```
* When we want to allocate a space for some data, we will use freeMapFile to construct freeMap object to manage free block map.
```
PersistentBitmap *freeMap;
freeMap = new PersistentBitmap(freeMapFile, NumSectors);
```
* In Allocate() function. It will use FindAndSet() function to find a unmark bit which indicated a free sector can be used and mark the bit to 1.
* In Deallocate() function. It will use Clear() function to reset the bit to 0.
* The free block file's header store in sector 0.
## (2) What is the maximum disk size that can be handled by the current implementation? Explain why.
* SectorSize * SectorsPerTrack * NumTracks = 128B * 32 * 32 = 128KB(define in disk.h)
## (3) How does the NachOS FS manage the directory data structure? Where is this information stored on the raw disk (which sector)?
* Use OpenFile* object directoryFile in FileSystem. directoryFile indicated the root directory.
```
class FileSystem
{
...
OpenFile* directoryFile;
...
};
```
* Like freeMapFile we will open it from disk or create one and write back to disk.
```
FileSystem::FileSystem(bool format)
{
if (format)
{
...
FileHeader *dirHdr = new FileHeader;
freeMap->Mark(DirectorySector);
ASSERT(dirHdr->Allocate(freeMap, DirectoryFileSize));
dirHdr->WriteBack(DirectorySector);
directoryFile = new OpenFile(DirectorySector);
directory->WriteBack(directoryFile);
}
else
{
directoryFile = new OpenFile(DirectorySector);
...
}
}
```
* In directory.h, it define Directory and the DirectoryEntry(file).
```
class Directory {
...
int tableSize;
DirectoryEntry *table;
int FindIndex(char *name);
};
class DirectoryEntry {
public:
bool inUse;
int sector;
char name[FileNameMaxLen + 1];
};
```
A directory is a table of pairs: <file name, sector #>.
When add a file to the directory, Add() function will find a free sector to store the file's header in first. And then find a DirectoryEntry which is not used to record the file name and the sector.
When remove a file from the directory, Remove() function will find the DirectoryEntry in table and change DirectoryEntry's isUse to false.
The directoryFile fileheader store in sector 1.
## (4) What information is stored in an inode? Use a figure to illustrate the disk allocation scheme of the current implementation.
```
class FileHeader {
...
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
};
```
The disk allocation scheme of the current implementation is indexed allocation. That means each dataSector contains a sector number which the data it store in.
## (5) What is the maximum file size that can be handled by the current implementation? Explain why.
MaxFileSize = (NumDirect * SectorSize) = (128 - 8) / 4 * 128B = 3840 B
# Part 2:Implement
## (1)Combine your MP1 file system call interface with NachOS FS to implement five system calls:
### exception.cc
* Like mp1, We pass the parameters stored in registers to the corresponding function in ksyscall.h. After that, update the program counter value.
```
#else
case SC_Create:
val = kernel->machine->ReadRegister(4);
{
char *filename = &(kernel->machine->mainMemory[val]);
// cout << filename << endl;
status = SysCreate(filename, kernel->machine->ReadRegister(5));
kernel->machine->WriteRegister(2, (int)status);
}
kernel->machine->WriteRegister(PrevPCReg, kernel->machine->ReadRegister(PCReg));
kernel->machine->WriteRegister(PCReg, kernel->machine->ReadRegister(PCReg) + 4);
kernel->machine->WriteRegister(NextPCReg, kernel->machine->ReadRegister(PCReg) + 4);
return;
ASSERTNOTREACHED();
break;
case SC_Open:
val = kernel->machine->ReadRegister(4);
{
char *filename = &(kernel->machine->mainMemory[val]);
status = SysOpen(filename);
kernel->machine->WriteRegister(2, (int)status);
}
kernel->machine->WriteRegister(PrevPCReg, kernel->machine->ReadRegister(PCReg));
kernel->machine->WriteRegister(PCReg, kernel->machine->ReadRegister(PCReg) + 4);
kernel->machine->WriteRegister(NextPCReg, kernel->machine->ReadRegister(PCReg) + 4);
return;
ASSERTNOTREACHED();
break;
case SC_Write:
val = kernel->machine->ReadRegister(4);
{
char *filename = &(kernel->machine->mainMemory[val]);
status = SysWrite(filename, (int)kernel->machine->ReadRegister(5), (OpenFileId)kernel->machine->ReadRegister(6));
kernel->machine->WriteRegister(2, (int)status);
}
kernel->machine->WriteRegister(PrevPCReg, kernel->machine->ReadRegister(PCReg));
kernel->machine->WriteRegister(PCReg, kernel->machine->ReadRegister(PCReg) + 4);
kernel->machine->WriteRegister(NextPCReg, kernel->machine->ReadRegister(PCReg) + 4);
return;
ASSERTNOTREACHED();
break;
case SC_Read:
val = kernel->machine->ReadRegister(4);
{
char *filename = &(kernel->machine->mainMemory[val]);
status = SysRead(filename, (int)kernel->machine->ReadRegister(5), (OpenFileId)kernel->machine->ReadRegister(6));
kernel->machine->WriteRegister(2, (int)status);
}
kernel->machine->WriteRegister(PrevPCReg, kernel->machine->ReadRegister(PCReg));
kernel->machine->WriteRegister(PCReg, kernel->machine->ReadRegister(PCReg) + 4);
kernel->machine->WriteRegister(NextPCReg, kernel->machine->ReadRegister(PCReg) + 4);
return;
ASSERTNOTREACHED();
break;
case SC_Close:
{
// cout << filename << endl;
status = SysClose((OpenFileId)kernel->machine->ReadRegister(4));
kernel->machine->WriteRegister(2, (int)status);
}
kernel->machine->WriteRegister(PrevPCReg, kernel->machine->ReadRegister(PCReg));
kernel->machine->WriteRegister(PCReg, kernel->machine->ReadRegister(PCReg) + 4);
kernel->machine->WriteRegister(NextPCReg, kernel->machine->ReadRegister(PCReg) + 4);
return;
ASSERTNOTREACHED();
break;
```
### ksyscall.h
* Interface for the system calls.We only call the function and pass the parameters to filesys.h.
```
#else
int SysCreate(char *filename, int size)
{
kernel->fileSystem->Create(filename, size);
return 1;
}
OpenFileId SysOpen(char *filename)
{
return kernel->fileSystem->OpenAFile(filename);;
}
int SysRead(char *buf, int size, OpenFileId id)
{
return kernel->fileSystem->Read(buf, size, id);
}
int SysWrite(char *buf, int size, OpenFileId id)
{
return kernel->fileSystem->Write(buf, size, id);
}
int SysClose(OpenFileId id)
{
return kernel->fileSystem->Close(id);
}
#endif
```
### filesys.h
* Implement our file operations in filesys.h via OpenFile data structure.
```
...
OpenFileId OpenAFile(char *name){
fileDescriptor = Open(name);
return 1;
};
int Read(char *buf, int size, OpenFileId id){
return fileDescriptor->Read(buf, size);
};
int Write(char *buf, int size, OpenFileId id){
return fileDescriptor->Write(buf, size);
};
int Close(OpenFileId id){
fileDescriptor->~OpenFile();
fileDescriptor = NULL;
return 1;
};
OpenFile* fileDescriptor;
...
```
## (2) Enhance the FS to let it support up to 32KB file size
We use linked scheme to support up to 32KB file size.
### filehdr.h
* We add a in disk information next_fileheader_sector to store the sector number to the next file header.
* Because we used a sector to store the next sector number, we need to subtract NumDirect by 1.
```
#define NumDirect ((SectorSize - 3 * sizeof(int)) / sizeof(int))
//1 block for the next fileheader sector number
public:
FileHeader *get_next_fileheader() { return next_fileheader; };
int get_numBytes() { return numBytes; };
int get_numSectors() { return numSectors; };
private:
FileHeader *next_fileheader; //in core
int next_fileheader_sector; //in disk
```
### filehdr.cc
* In Allocate() function, we use freeMap->FindAndSet() to find a free sector space to each dataSector. After find the sector, we need write back the empty data to reset this sector.
* If fileSize larger than MaxFileSize, we need to use freeMap->FindAndSet() to find a free sector space to the next file header sector and call() next_fileheader->Allocate(freeMap, fileSize) to allocate the remaining file.
```
FileHeader::FileHeader()
{
...
next_fileheader = NULL;
next_fileheader_sector = -1;
}
bool FileHeader::Allocate(PersistentBitmap *freeMap, int fileSize)
{
if (fileSize >= MaxFileSize)
{
numBytes = MaxFileSize;
}
else
{
numBytes = fileSize;
}
numSectors = divRoundUp(numBytes, SectorSize);
if (freeMap->NumClear() < numSectors)
return FALSE; // not enough space
for (int i = 0; i < numSectors; i++)
{
dataSectors[i] = freeMap->FindAndSet();
char *clean_data = new char[SectorSize]();
kernel->synchDisk->WriteSector(dataSectors[i], clean_data);
delete clean_data;
}
fileSize -= numBytes;
if (fileSize > 0)
{
next_fileheader_sector = freeMap->FindAndSet();
if (next_fileheader_sector == -1)
{
return false;
}
next_fileheader = new FileHeader();
if (!next_fileheader->Allocate(freeMap, fileSize))
{
return false;
}
}
return TRUE;
}
```
* In Deallocate() function, if next_fileheader_sector != -1(there exist next file header), then we need to call Deallocate() to the next file header.
* Same as FetchFrom(),WriteBack() and ByteToSector() functions.
```
void FileHeader::Deallocate(PersistentBitmap *freeMap)
{
for (int i = 0; i < numSectors; i++)
{
freeMap->Clear((int)dataSectors[i]);
}
if (next_fileheader_sector != -1)
{
next_fileheader->Deallocate(freeMap);
}
}
void FileHeader::FetchFrom(int sector)
{
//don't need to fetch next_fileheader
kernel->synchDisk->ReadSector(sector, (char *)this + sizeof(FileHeader*));
if(next_fileheader_sector != -1){
next_fileheader = new FileHeader();
next_fileheader->FetchFrom(next_fileheader_sector);
}
}
void FileHeader::WriteBack(int sector)
{
//don't need to write next_fileheader back to disk
kernel->synchDisk->WriteSector(sector, (char *)this + sizeof(FileHeader*));
if(next_fileheader_sector != -1){
kernel->synchDisk->WriteSector(next_fileheader_sector, (char*)this);
next_fileheader->WriteBack(next_fileheader_sector);
}
}
int FileHeader::ByteToSector(int offset)
{
int sector_idx = offset / SectorSize;
if(sector_idx >= NumDirect){
return next_fileheader->ByteToSector(offset - MaxFileSize);
}
else{
return (dataSectors[offset / SectorSize]);
}
}
```
### openfile.cc
* We change the Length() function in openfile.cc to handle the larger file.
```
int OpenFile::Length()
{
int len = 0;
FileHeader* nextHdr = hdr;
while(nextHdr){
len += nextHdr->FileLength();
nextHdr = nextHdr->get_next_fileheader();
}
return len;
}
int OpenFile::WriteAt(char *from, int numBytes, int position)
{
int fileLength = Length();
...
}
int OpenFile::ReadAt(char *from, int numBytes, int position)
{
int fileLength = Length();
...
}
```
# Part III. Modify the file system code to support the subdirectory
## (1) Implement the subdirectory structure
### main.cc
* We call the function in file system and pass the parameter to handle -r,-mkdir and -lr commands.
```
int main(){
...
#ifndef FILESYS_STUB
if (removeFileName != NULL)
{
if(recursiveListFlag){
kernel->fileSystem->RemoveDir(removeFileName);
}
else{
kernel->fileSystem->Remove(removeFileName);
}
}
if (dirListFlag)
{
if(recursiveListFlag){
kernel->fileSystem->recursiveList();
}
else{
kernel->fileSystem->List();
}
}
}
static void CreateDirectory(char *name)
{
kernel->fileSystem->CreateDir(name);
}
```
### directory.h
* Add a attribute isDir to support -lr command.
```
class DirectoryEntry
{
public:
...
bool isDir;
};
```
### directory.cc
* In Add() function, we add a parameter to indicate the file is a file or dir.
* In RecursiveList() function, we pass a depth parameter to use indentation.
When for loop find a dir, we print the name of dir and the type, call its RecursiveList() funtion.
* If it is a file, we only print the name and the type.
```
Directory::Directory(int size)
{
...
table[i].isDir = FALSE;
...
}
bool Directory::Add(char *name, int newSector, bool isDir)
{
...
table[i].isDir = isDir;
...
}
void Directory::RecursiveList(int depth)
{
Directory *subdir = new Directory(NumDirEntries);
OpenFile *sub_openfile;
for (int i = 0; i < tableSize; i++)
{
if (table[i].inUse)
{
for (int j = 0; j < depth * 4; j++)
{
printf(" ");
}
if (table[i].isDir)
{
printf("[D] %s\n", table[i].name);
sub_openfile = new OpenFile(table[i].sector);
subdir->FetchFrom(sub_openfile);
subdir->RecursiveList(depth + 1);
}
else
{
printf("[F] %s\n", table[i].name);
}
}
}
}
```
### filesys.h
* Add some functions we need.
```
bool CreateDir(char *name);
bool Remove(char *name, bool is_recursive);
void recursiveList();
```
### filesys.cc
* In Create() function, we use strtok() function to get the name of directory of each level from root.
* We fetch the directory fileheader by the name from disk until it is not exist in this directory.
* Use freeMap->FindAndSet() to find a sector to store the file header.
* Use directory->Add(dirname, sector, FALSE) to add a file to this directory.
* Use hdr->Allocate(freeMap, initialSize) to allocate data blocks for this file.
* Write back freeMap, directory and hdr.
* In CreateDir() function, we only change the file size and call directory->Add(dirname, sector, TRUE).
```
bool FileSystem::Create(char *name, int initialSize)
{
Directory *directory;
PersistentBitmap *freeMap;
FileHeader *hdr;
int sector;
bool success;
directory = new Directory(NumDirEntries);
directory->FetchFrom(directoryFile);
OpenFile *tempOpen = directoryFile;
char *dirname = strtok(name, "/");
char *pre_dirname = dirname;
while (dirname != NULL)
{
sector = directory->Find(dirname);
if (sector == -1)
{
break;
}
tempOpen = new OpenFile(sector);
directory->FetchFrom(tempOpen);
pre_dirname = dirname;
dirname = strtok(NULL, "/");
}
if (directory->Find(dirname) != -1)
success = FALSE; // file is already in directory
else
{
freeMap = new PersistentBitmap(freeMapFile, NumSectors);
sector = freeMap->FindAndSet(); // find a sector to hold the file header
if (sector == -1)
success = FALSE; // no free block for file header
else if (!directory->Add(dirname, sector, FALSE))
success = FALSE; // no space in directory
else
{
hdr = new FileHeader;
if (!hdr->Allocate(freeMap, initialSize))
success = FALSE; // no space on disk for data
else
{
success = TRUE;
// everthing worked, flush all changes back to disk
hdr->WriteBack(sector);
directory->WriteBack(tempOpen);
freeMap->WriteBack(freeMapFile);
}
delete hdr;
}
delete freeMap;
}
delete directory;
return success;
}
bool FileSystem::CreateDir(char *name)
{
Directory *directory = new Directory(NumDirEntries);
PersistentBitmap *freeMap;
FileHeader *hdr;
int sector;
bool success;
directory->FetchFrom(directoryFile);
OpenFile *tempOpen = directoryFile;
char *dirname = strtok(name, "/");
while (dirname != NULL)
{
sector = directory->Find(dirname);
if (sector == -1)
{
break;
}
tempOpen = new OpenFile(sector);
directory->FetchFrom(tempOpen);
dirname = strtok(NULL, "/");
}
if (directory->Find(dirname) != -1)
success = FALSE; // file is already in directory
else
{
freeMap = new PersistentBitmap(freeMapFile, NumSectors);
sector = freeMap->FindAndSet(); // find a sector to hold the file header
if (sector == -1)
success = FALSE; // no free block for file header
else if (!directory->Add(dirname, sector, TRUE))
success = FALSE; // no space in directory
else
{
hdr = new FileHeader;
if (!hdr->Allocate(freeMap, DirectoryFileSize))
success = FALSE; // no space on disk for data
else
{
success = TRUE;
// everthing worked, flush all changes back to disk
hdr->WriteBack(sector);
directory->WriteBack(tempOpen);
freeMap->WriteBack(freeMapFile);
}
delete hdr;
}
delete freeMap;
}
delete directory;
return success;
}
```
* In Open() function, like Create(), but we return the openFile in the last level.
* In recursiveList() function, it will call RecursiveList() function or List() function in the last level depends on is_recursive.
```
OpenFile *FileSystem::Open(char *name)
{
Directory *directory = new Directory(NumDirEntries);
OpenFile *openFile = NULL;
int sector;
DEBUG(dbgFile, "Opening file" << name);
directory->FetchFrom(directoryFile);
char *dirname = strtok(name, "/");
while (dirname != NULL)
{
sector = directory->Find(dirname);
openFile = new OpenFile(sector);
directory->FetchFrom(openFile);
dirname = strtok(NULL, "/");
}
delete directory;
return openFile; // return NULL if not found
}
void FileSystem::recursiveList(char *name, bool is_recursive)
{
Directory *directory = new Directory(NumDirEntries);
OpenFile *openFile = directoryFile;
directory->FetchFrom(directoryFile);
int sector;
char *dirname = strtok(name, "/");
char *prev_dirname = dirname;
while (dirname != NULL)
{
sector = directory->Find(dirname);
openFile = new OpenFile(sector);
directory->FetchFrom(openFile);
prev_dirname = dirname;
dirname = strtok(NULL, "/");
}
if(dirname == NULL){
dirname = prev_dirname;
}
if (is_recursive)
{
directory->RecursiveList(0);
cout << "\n";
}
else
{
directory->List();
}
delete directory;
}
```
* In Remove() function, like Create() function, but we need to store the OpenFile of upper directory.
* Call freeMap->FindAndSet() to find a sector to store the file header.
* Call directory->Remove(dirname) to remove from this directory.
* Call freeMap->Clear(sector) to remove file header block.
* Call hdr->Deallocate(freeMap, initialSize) to remove data blocks.
* Write back freeMap and directory.
```
bool FileSystem::Remove(char *name, bool is_recursive)
{
Directory *directory = new Directory(NumDirEntries);;
PersistentBitmap *freeMap = new PersistentBitmap(freeMapFile, NumSectors);;
FileHeader *fileHdr = new FileHeader;
int sector;
OpenFile *openFile = NULL;
OpenFile *pre_openFile = openFile;
directory->FetchFrom(directoryFile);
char *dirname = strtok(name, "/");
char* pre_dirname = dirname;
while (dirname != NULL)
{
sector = directory->Find(dirname);
pre_openFile = openFile;
openFile = new OpenFile(sector);
directory->FetchFrom(openFile);
pre_dirname = dirname;
dirname = strtok(NULL, "/");
}
dirname = pre_dirname;
if(!pre_openFile){
pre_openFile = directoryFile;
}
directory->FetchFrom(pre_openFile);
fileHdr->FetchFrom(sector);
fileHdr->Deallocate(freeMap); // remove data blocks
freeMap->Clear(sector); // remove header block
directory->Remove(dirname);
freeMap->WriteBack(freeMapFile); // flush to disk
directory->WriteBack(pre_openFile); // flush to disk
delete fileHdr;
delete directory;
delete freeMap;
return TRUE;
}
```
## (2) Support up to 64 files/subdirectories per directory
### filesys.cc
```
#define NumDirEntries 64
```
# bouns
## bouns I
Our design already support 64MB file, but needs 20min. So we only change the disk size.
disk.cc
```
const int NumTracks = 16384; //64MB = 1024 * 1024 * 64 B = 16384 * 128 * 32 B
```
## bouns II
* We show the file size and the file header sector.
### filesys.cc
```
void FileSystem::Print()
{
Directory *directory = new Directory(NumDirEntries);
directory->FetchFrom(directoryFile);
directory->Print();
}
```
### filehdr.cc
```
void FileHeader::Print()
{
printf("FileHeader sector: %d\n", find_length());
printf("FileHeader contents. File size: %d\n", find_size());
}
int FileHeader::find_length(){
int length = 1;
if(next_fileheader){
length += next_fileheader->find_length();
}
return length;
}
int FileHeader::find_size(){
int length = FileLength();
if(next_fileheader){
length += next_fileheader->find_size();
}
return length;
}
```
## bouns III
Google Drive
Gist
Clipboard
Sign in with Wallet
