This is NACHOS#1

Nachos模拟了一个硬盘，实现的文件系统比较简单，该实验将熟悉一些文件系统的操作命令，观察这些命令对硬盘（DISK）的影响，根据结果分析理解Nachos文件系统的实现原理。

该实验中需要理解一些Nachos文件的基本知识，特别是文件头（FCB或索引节点）的结构与作用，空闲块的标识方法，空闲块的分配与回收过程等。

文件的扩展实质上是从一个给定的位置开始对文件进行写操作，涉及到文件的打开、定位，空闲块的分配等操作，写操作结束后还需要将文件头、空闲块位示图写到硬盘中，以保存修改后的信息。

该实验完成后，需要你：

• 理解Nachos硬盘是如何创建的
• 熟悉查看Nachos硬盘上的内容的方法
• 理解硬盘初始化的过程（如何在硬盘上创建一个文件系统）
• 了解Nachos文件系统提供了哪些命令，哪些命令已经实现，哪些需要你自己实现
• 理解已经实现的文件系统命令的实现原理
• 理解硬盘空闲块的管理方法
• 理解目录文件的结构与管理
• 理解文件的结构与文件数据块的分配方法
• 了解一个文件系统命令执行后，硬盘的布局
• 分析目前Nachos不能对文件进行扩展的原因，考虑解决方案

理解Nachos创建硬盘的过程与方法

../lab5/main.cc调用了../threads/system.cc中的Initialize()创建了硬盘DISK

SynchDisk的初始化函数如下：

// ../filesys/synchdisk.cc
SynchDisk::SynchDisk(char* name)
{
    semaphore = new Semaphore("synch disk", 0);
    lock = new Lock("synch disk lock");
    disk = new Disk(name, DiskRequestDone, (_int) this);
}

初始化了物理硬盘的同步接口：用于同步的信号量和互斥锁

创建了模拟硬盘，其初始化函数如下：

// ../machine/disk.cc
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;
}

打开一个UNIX文件（若不存在则创建）用于读写，向该文件写入一个magicNum来标识该文件是一个硬盘存储文件，并在该文件最末尾写入0标记文件结束，腾出存储空间

了解Nachos文件系统提供的命令并测试

分析../lab5/main.cc

Nachos文件系统提供的命令有：

• -cp：复制UNIX文件到Nachos文件（正确运行）
• -ap：将UNIX文件内容增加到Nachos文件后（未正确运行）
• -hap：将Nachos文件内容剪掉后半部分再将UNIX文件内容增至其后（未正确运行）
• -nap：将Nachos文件内容增加到Nachos文件后（未正确运行）
• -p：打印Nachos文件内容（正确运行）
• -r：删除Nachos文件（正确运行）
• -l：列出Nachos文件列表（正确运行）
• -D：打印整个文件系统（正确运行）
• -t：性能测试（未正确运行）

理解Nachos硬盘格式化（创建文件系统）的处理过程

分析../filesys/filesys.cc中的构造函数FileSystem::FileSystem(..)

// ../filesys/filesys.cc
FileSystem::FileSystem(bool format)
{ 
    DEBUG('f', "Initializing the file system.\n");
    if (format) {
        BitMap *freeMap = new BitMap(NumSectors);
        Directory *directory = new Directory(NumDirEntries);
        FileHeader *mapHdr = new FileHeader;
        FileHeader *dirHdr = new FileHeader;

        DEBUG('f', "Formatting the file system.\n");

    // First, allocate space for FileHeaders for the directory and bitmap
    // (make sure no one else grabs these!)
	freeMap->Mark(FreeMapSector);	    
	freeMap->Mark(DirectorySector);

    // Second, allocate space for the data blocks containing the contents
    // of the directory and bitmap files.  There better be enough space!

	ASSERT(mapHdr->Allocate(freeMap, FreeMapFileSize));
	ASSERT(dirHdr->Allocate(freeMap, DirectoryFileSize));

    // Flush the bitmap and directory FileHeaders back to disk
    // We need to do this before we can "Open" the file, since open
    // reads the file header off of disk (and currently the disk has garbage
    // on it!).

        DEBUG('f', "Writing headers back to disk.\n");
	mapHdr->WriteBack(FreeMapSector);    
	dirHdr->WriteBack(DirectorySector);

    // OK to open the bitmap and directory files now
    // The file system operations assume these two files are left open
    // while Nachos is running.

        freeMapFile = new OpenFile(FreeMapSector);
        directoryFile = new OpenFile(DirectorySector);
     
    // Once we have the files "open", we can write the initial version
    // of each file back to disk.  The directory at this point is completely
    // empty; but the bitmap has been changed to reflect the fact that
    // sectors on the disk have been allocated for the file headers and
    // to hold the file data for the directory and bitmap.

        DEBUG('f', "Writing bitmap and directory back to disk.\n");
	freeMap->WriteBack(freeMapFile);	 // flush changes to disk
	directory->WriteBack(directoryFile);

	if (DebugIsEnabled('f')) {
	    freeMap->Print();
	    directory->Print();

        delete freeMap; 
	delete directory; 
	delete mapHdr; 
	delete dirHdr;
	}
    } else {
    // if we are not formatting the disk, just open the files representing
    // the bitmap and directory; these are left open while Nachos is running
        freeMapFile = new OpenFile(FreeMapSector);
        directoryFile = new OpenFile(DirectorySector);
    }
}

参数format表示是否将硬盘格式化，当命令行输入-f后则置其为true

需要初始化磁盘使其包含一个空的目录directory和空闲块位图freeMap

Nachos模拟的硬盘DISK共有32个道，每个道有32个扇区，每个扇区128个字节，每个盘块仅包含一个扇区，所以共有1024个盘块，所以位图共1024位

Nachos文件系统采用单级目录结构，根目录中只有10个目录项，意味着Nachos的硬盘中最多可创建10个文件

而这两个也被视作文件，同样需要文件头mapHdr dirHdr

1. 为这两个文件头分配空间，位图的文件头被分配在0号扇区，目录的文件头被分配在1号扇区

思考：为什么将空闲块管理的位示图文件头与目录表文件头存放在0号和1号这两个特殊的扇区中？

初始化文件系统时，将这两个特殊的扇区设置为已使用，确保其他文件不会访问到。而对于一个真正的操作系统，由于系统启动时需要根据目录文件的文件头访问根目录，所以为了便于系统启动时从已知的、固定的位置访问它们，将这两个特殊的结构分配到0号和1号两个特殊的扇区中。

1. 为目录和位图的数据块分配空间，同时更新对应的文件头内容

文件头内容包含：

• numBytes文件大小
• numSectors分配给文件的块数
• dataSector[]文件每个数据块对应的扇区号

位图文件大小为1024/8=128B，目录文件大小为目录项大小*10=20*10=200B

目录项内容包含：

• inUser该目录项是否已分配
• sector文件头所在的扇区号
• name文件名

1. 将目录和位图的文件头内容写回到磁盘（0号和1号扇区）中
2. 打开目录和位图文件
3. 将位图的数据内容写回磁盘中，因为刚刚的初始化分配了空闲块，位图发生了变化，而目录仍然为空
4. 文件系统创建完毕

理解文件系统管理涉及的数据结构组织与使用

利用命令hexdump –C DISK查看硬盘格式化后硬盘的布局，分析如下：

• 0x0~0x3：起始的4个字节为磁盘标识，设置为magicNum=0x456789ab

• 0x4~0x83：0号扇区，共128个字节，存放位图的文件头，细分如下：

  • 0x4~0x7：4个字节，位图所占的字节数。值为0x80，表示位图大小为128字节

  • 0x8~0xB：4个字节，系统为位图数据所分配的扇区数。值为0x1，表示位图数据只需1个扇区

  • 0xC~0XF：位图数据块所在的扇区号。值为0x2，表示系统将位图数据保存在2号扇区中

  • 0x10~0x83：空，因为位图数据只占1个扇区。

    每个扇区号占4个字节，所以0xC~0x83最多能存放30个扇区号，所以一个文件大小最大为30*128=3840B

• 0x84~0x103：1号扇区，共128个字节，存放目录的文件头，细分如下：

  • 0x84~0x87：4个字节，目录所占的字节数。值为0xc8，表示目录大小为200字节
  • 0x88~0x8B：4个字节，系统为目录数据所分配的扇区数。值为0x2，表示目录数据需要2个扇区
  • 0x8C~0x8F：系统为目录数据分配的第一个扇区号，值为0x3
  • 0x90~0x93：系统为目录数据分配的第二个扇区号，值为0x4
  • 0x94~0x103：空

• 0x104~0x183：2号扇区，共128个字节，存放位图的数据部分，值为0x1f，表示扇区0,1,2,3,4已被分配

• 0x184~0x203：3号扇区 + 0x204~0x283：4号扇区

  这两个扇区存放目录表，目前为空，值为0x0

理解创建一个文件后相关的结构在硬盘上的存储布局

利用命令nachos –cp ./test/small samll复制small文件硬盘DISK中

利用命令hexdump –C DISK查看新建一个文件后的硬盘布局，分析如下：

• 0x0~0x3：磁盘标识符，不变

• 0x4~0x83：0号扇区，存放位图文件头，内容不变

• 0x84~0x103：1号扇区，存放目录文件头，内容不变

• 0x104~0x183：2号扇区，存放位图数据部分，由0x1f变为0x7f，说明5号和6号扇区也被分配使用，即分配给small文件头和文件内容

• 0x184~0x203：3号扇区，存放目录表，发生改变。因为新建了文件small，所以需要在一个空闲的目录项中添加small对应的信息：

  • 0x184~0x187：4个字节，inUse该目录项是否已被使用（虽然为bool类型，但为了对齐，分配4个字节）。值为0x1，说明该目录项正被一个文件使用
  • 0x188~0x18B：4个字节，sector该目录项所记录的文件的文件头所在的扇区号。值为0x5，说明small文件的文件头在5号扇区，若要考察small的详细信息，则要到5号扇区访问其文件头

  • 0x18C~0x195：10个字节，name文件名（文件名占用9个字节，最后一个字节是字符串结束符\0）。这里的文件名经过转码为small

  • 0x196~0x203：其余目录项为空

• 0x204~0x283：4号扇区，存放目录表，依旧为空

• 0x284~0x303：5号扇区，存放small的文件头

  • 0x284~0x287：4个字节，文件所占的字节数。值为`0xc54，表示small文件大小为84字节
  • 0x288~0x28B：4个字节，系统为文件数据所分配的扇区数。值为0x1，表示small数据需要1个扇区
  • 0x28C~0x28F：系统为文件数据分配的扇区号。值为0x6，表示系统将small数据保存在6号扇区中
  • 0x290~0x303：为空

• 0x304~0x383：6号扇区，存放small的文件数据

分析文件系统的管理策略

复制文件medium, big到DISK中

然后删除small文件

利用hexdump –C DISK查看文件的布局

• 0x104~0x183：2号扇区，存放位图数据部分。值为0x3f9f，二进制为11111110011111，表示5号和6号扇区空闲，即为small文件的文件头和数据部分占用的扇区
• 0x184~0x203：3号扇区，存放目录表。0x184字节处变为0x0，表示为small分配的目录项的inUse位变为0，即为small文件分配的目录项空闲。而该目录项的其他内容不变
• 0x284~0x303：5号扇区，存放small的文件头，不变
• 0x304~0x383：6号扇区，存放small的文件数据，不变

分析删除small文件的过程：该文件的目录表中的文件头所在扇区号和文件名、文件头信息、文件数据均未被清除；只是在位图中将该文件的扇区置为空闲，在目录表中将该文件的目录项置为空闲

因此，要恢复一个被删除的文件，只要该文件的相关信息未被覆盖，就可以根据文件名在目录表中找到该文件对应的目录项，将inUse恢复为1，并在位图中恢复文件头占用的扇区号，再根据文件头的信息恢复文件数据占用的扇区号。

这种删除文件的策略为恢复文件带来了极大的便利。