《Unix/linux系统编程》教材第11章学习笔记

第11章：EXT2文件系统

EXT2文件系统
Linux一直使用EXT2作为默认文件系统。

EXT2文件系统数据结构

• 创建虚拟硬盘
  mke2fs [-b blksize -N ninodes] device nblocks
  eg：dd if=/dev/zero of=vdisk bs=1024 count=1440
mke2fs vdisk 1440
  在一个名为vdisk的虚拟磁盘文件上创建一个EXT2文件系统，有1440个大小为1KB的块。
  

• 虚拟磁盘布局
  
  Block#0：引导块

*超级块
Block#1：超级块，用于容纳整个文件系统的信息
下面是一些重要字段

• 块组描述符
  Block#2：块组描述符块
  

• 块和索引节点位图
  BLOCK#8：块位图（Bmap）
  BLOCK#9：索引节点位图（Lmap）

• 索引节点
  BLOCK#10：索引节点
  

i_block[15]数组指向文件磁盘块的指针，这些磁盘块有：
直接块：i_block[0]至i_block[11]，指向直接磁盘块。
间接块：
双重间接块：
三重间接块：

• 数据块
  紧跟在索引节点块后面的是文件存储数据块。

• 目录条目
  目录包含dir_entry结构，即：
  
  是一种可扩充结构。

邮差算法
在计算机系统中，经常出现下面这个问题。一个城市有M个街区，编号从0到M-1。每个街区有N座房子，编号从0到N-1。每座房子有一个唯一的街区地址，用（街区，房子）表示，其中0≤街区<M，0≤房子<N。来自外太空的外星人可能不熟悉地球上的街区寻址方案，倾向于采用线性方法将这些房子地址编为0，1，…，N-1，N，N+1等。已知某个街区地址BA=（街区，房子），怎么把它转换为线性地址LA，反过来，已知线性地址，怎么把它转换为街区地址?如果都从0开始计数，转换就会非常简单。

Linear_address LA = N*block + house;
Block_address BA = (LA / N, LA % N);

只有都从0开始计数时，转换才有效。如果有些条目不是从0开始计数的，则不能直接在转换公式中使用。我们把这种转换方法称为邮差算法。下面是邮差算法的几种应用。

• C语言中的Test-Set-Clear位
  标准C语言程序中，最小的可寻址单元是一个字符或字节。在一系列位组成的位图中，通常需要对位进行操作。考虑字符buf[1024]，它有1024个字节，用buf[i]表示，其中i = 0,1,...,1023。它还有8192个位，编号为0,1,2,...8191。已知一个位号BIT，例如1234，那么哪个字节i包含这个位，以及哪个位j在该字节中呢？
  i = BIT/8; j = BIT%8; //8 = number of bits in a byte.
  可以在C语言中结合使用邮差算法和位屏蔽来进行下面的位操作。
  .TST a bit for 1 or 0: if (buf[i] & (1 << j))
  .SET a bit to 1 : buf[i] |= (1 << j);
  .CLR a bit to 0 : buf[i] &= ~(1 << j);
  注意一些C语言编译器允许在结构体中指定位，如：
  struct bits{
  unsigned int bit0 : 1; //bit0 field is a single bit
  unsigned int bit123 : 3; //bit123 field is a range of 3 bits
  unsigned int otherbits : 27; //other bits field has 27 bits
  unsigned int bit31 : 1; //bit31 is the highest bit
  }var;
  该结构体将var.定义位一个32位无符号整数，具有单独的位或位范围。那么，var.bit0=0；将1赋值给第0位，则有var.bit123=5；将101赋值给第1位到第3位等。但是，生成的代码仍然依赖于邮差算法和位屏蔽来访问各个位。可以使用邮差算法直接操作位图中的位，无须定义复杂的C语言结构体。

• 将索引节点号转换为磁盘上的索引节点
  在EXT2文件系统中，每个文件都有一个唯一的索引节点结构。在文件系统磁盘上，索引节点从inode_table块开始。每个磁盘块包含
  INODES_PER_BLOCK = BLOCK_SIZE/sizeof(INODE)
  个索引节点。每个索引节点都有一个唯一的索引节点号，ino=1,2,...,从1开始线性计数，已知一个ino，如1234，那么哪个磁盘块包含该索引节点，以及哪个索引节点在该块中呢？我们需要知道磁盘块号，因为需要通过块来读/写一个真正的磁盘。

block = (ino - 1) / INODES_PER_BLOCK + inode_table;
inode = (ino - 1) % INODES_PER_BLOCK;

同样，将EXT2文件系统中的双重和三重间接逻辑块号转换为物理块号也依赖于邮差算法。
将线性磁盘块号转换为CHS = (柱面、磁头、扇区)格式：软盘和旧硬盘使用CHS寻址，但文件系统始终使用线性块寻址。在调用BIOS INT13时，可使用该算法将磁盘块号转换为CHS。

编程示例
访问和显示EXT2文件系统的内容，安装ext2fs.h头文件。
sudo apt-get install e2fslibs-dev e2fslibs-dev

• 显示超级块

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/io.h>
#include <ext2fs/ext2_fs.h>
typedef unsigned char u8;
typedef struct ext2_super_block SUPER;
typedef struct ext2_group_desc GD;
#define BLKSIZE 1024

SUPER *sp;
GD *gp;
char buf[BLKSIZE]; 
int fd;
// get_block() reads a disk block into a buf[]?
int get_block(int fd, int blk, char *buf)
{
    lseek(fd, (long)blk*BLKSIZE, SEEK_SET); 
    return read(fd, buf, BLKSIZE);
}

int imap(char *device)
{
    int i, ninodes, blksize, imapblk;
    fd = open(device, O_RDONLY);
    if (fd < 0) 
    {
        printf("open %s failed\n", device);
        exit(1);
    }
    get_block(fd, 1, buf);	// get superblock
    sp = (SUPER *)buf;
    // check magic number to ensure itz s an EXT2 FS ninodes = sp->s_inodes_count	//
    ninodes = sp->s_inodes_count;
    printf("ninodes = %d\n", ninodes);
    get_block(fd, 2, buf);	//
    gp = (GD *)buf;
    imapblk = gp->bg_inode_bitmap;	
    printf("imapblk = %d\n", imapblk);
    get_block(fd, imapblk, buf);	
    for ( i = 0; i <= ninodes/8; i++)
    {
        printf("%02x ", (u8)buf[i]);
    }
    printf("\n");
}
char *dev = "mydisk";
int main(int argc, char*argv[])
{
    if(argc>1) dev = argv[1];
    imap(dev);
}

• 显示位图
• 显示根索引节点
• 显示目录条目

3级文件系统

• 挂载算法
  挂载操作命令
  mount filesys mount_point
  可将某个文件系统挂载到mount_point目录上。

• 卸载算法
  卸载文件系统操作可卸载已挂载的文件系统。

• 交叉挂载点
  虽然可以轻松实现挂载和卸载，但是会有一定的影响。对于挂载，必须修改getino(pathname)函数来支持交叉挂载点。假设某文件系统newfs已被挂载到目录/a/b/c/上。当遍历一个路径名时，两个方向的挂载点可能会出现交叉。
  （1）向下遍历:当遍历路径名/a/b/c/x时，一旦到达/a/b/c的minode，就能看到minode已经被挂载（挂载标志=1)。我们不是在/a/b/c的索引节点中搜索x，而是必须要:
  跟随minode的mntPtr指针来定位挂载表条目。
  从挂载表的设备号中，将其根索引节点(ino=2)放入内存。
  然后，继续在挂载设备的根索引节点下搜索x。
  （2）向上遍历:假设在目录/a/b/c/x/上，然后向上遍历，例如cd ../../)，将会与挂载点/a/b/c交叉。当到达挂载文件系统的根索引节点时，就能看到它是一个根目录(ino=2)，但是它的设备号与实根的设备号不同，因此它现在还不是实根。可以使用它的设备号，找到它的挂载表条目，它指向/a/b/c的minode。然后，切换到/a/b/c的minode，继续向上遍历。因此，交叉挂载点就像一只猴子或松鼠从一棵树跳到另一棵树上，然后又跳了回来。

• 文件保护
  在Unix/Linux中，可通过文件索引节点中的权限位实现文件保护。每个文件的索引节点都有一个i_mode字段，其中下面的9位是权限。9个权限位为：
  
  前3位适用于文件所有人，中间3位适用于与所有人同一组的用户，最后3位适用于其他所有用户。对于目录，x位表示某进程是否可进入目录。每个进程都有一个uid和gid。当某进程试图访问某个文件时，文件系统会根据文件的权限位检查进程uid和gid，以确定它是否能以目标操作模式访问文件。如果该进程没有适当的权限，访问会被拒绝。为简单起见，可以忽略进程gid，只使用进程uid来检查访问权限。

学习过程中的问题

在安装ext2fs开发包时，使用书本上给出的代码显示无法定位软件包。
询问gpt

更改代码解决

gpt苏格拉底挑战

• ext2文件系统数据结构
  
  

• 3级文件系统
  
  

代码

#include <stdlib.h>
#include <time.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/io.h>
#include <ext2fs/ext2_fs.h>
typedef unsigned char u8;
typedef struct ext2_super_block SUPER;
typedef struct ext2_group_desc GD;
#define BLKSIZE 1024

SUPER *sp;
GD *gp;
char buf[BLKSIZE]; 
int fd;
// get_block() reads a disk block into a buf[]?
int get_block(int fd, int blk, char *buf)
{
    lseek(fd, (long)blk*BLKSIZE, SEEK_SET); 
    return read(fd, buf, BLKSIZE);
}

int imap(char *device)
{
    int i, ninodes, blksize, imapblk;
    fd = open(device, O_RDONLY);
    if (fd < 0) 
    {
        printf("open %s failed\n", device);
        exit(1);
    }
    get_block(fd, 1, buf);	// get superblock
    sp = (SUPER *)buf;
    // check magic number to ensure itz s an EXT2 FS ninodes = sp->s_inodes_count	//
    ninodes = sp->s_inodes_count;
    printf("ninodes = %d\n", ninodes);
    get_block(fd, 2, buf);	//
    gp = (GD *)buf;
    imapblk = gp->bg_inode_bitmap;	
    printf("imapblk = %d\n", imapblk);
    get_block(fd, imapblk, buf);	
    for ( i = 0; i <= ninodes/8; i++)
    {
        printf("%02x ", (u8)buf[i]);
    }
    printf("\n");
}
char *dev = "mydisk";
int main(int argc, char*argv[])
{
    if(argc>1) dev = argv[1];
    imap(dev);
}