首页 > 其他分享 >第五周学习笔记

第五周学习笔记

时间：2023-10-15 09:46:03浏览次数：32  
标签：count 笔记 学习 索引 第五 u32 inode 节点 block

EXT2文件系统

EXT2文件系统数据结构

使用mkfs创建虚拟磁盘

linux命令为

mke2fs [-b blksize -N ninodes] device nblocks

具体使用例：

dd if=/dev/zero of=vdisk bs=1024 count=1440
mke2fs vdisk 1440

虚拟磁盘布局

Block#0：引导块
B0是引导块(Boot Block)，文件系统不会使用它。它用于容纳从磁盘引导操作系统的引导程序。
Block#1：超级块
超级块(Super Block)描述整个分区的文件系统信息，如inode/block的大小、总量、使用量、剩余量，以及文件系统的格式与相关信息。超级块在每个块组的开头都有一份拷贝（第一个块组必须有，后面的块组可以没有）。
超级块记录的信息有：
1. block 与 inode 的总量（分区内所有Block Group的block和inode总量）；
2. 未使用与已使用的 inode / block 数量；
3. block 与 inode 的大小 (block 为 1, 2, 4K，inode 为 128 bytes)；
4. filesystem 的挂载时间、最近一次写入数据的时间、最近一次检验磁盘 (fsck) 的时间等文件系统的相关信息；
5. 一个 valid bit 数值，若此文件系统已被挂载，则 valid bit 为 0 ，若未被挂载，则 valid bit 为 1 。

struct ext2_guper_block {
   u32 s_inodes_count; /* Inodes count */
   u32 s_blocks_count; /* Blocks count*/
   u32 s_r_blocks_count; /* Reserved blocks count */
   u32 s_free_blocks_count; / * Free blocks count */
   u32 s_free_inodes_count; /* Free inodes count */
   u32 s_first__data_blook; /* First Data Block */
   u32 s_log_block_size; /* Block size */
   u32 s_log_cluster_size; /* Allocation cluster size */
   u32 s_blocks_per_group; /* # Blocks per group*/
   u32 s_clusters_per_group; /*# Fragments per group */
   u32 s_inodes_per_group; /* # Inodes per group*/
   u32 s_mtime;u32 s_wtime; /* Mount time */
   u16 s_mnt_count; /* Write time */
   s16 s_max_mnt_count; /_Mount_count/L
   u16 8_magic; /* Magic signature */
   // more non-essential fields
   u16 s_inode_size; /* size of inode structure*/
}

Block#2：块组描述符块

  • 块组描述符块(GD)由很多块组描述符组成，整个分区分成多个块组就对应有多少个块组描述符。
  • 每个块组描述符存储一个块组的描述信息，如在这个块组中从哪里开始是inode Table，从哪里开始是Data Blocks，空闲的inode和数据块还有多少个等等。块组描述符在每个块组的开头都有一份拷贝。
struct ext2_group_desc {
	u32 bg_block_bitmap; // Bmap block number
	u32 bg_inode_bitmap; // Imap block number
	u32 bg_inode_table; // Inodes begin block number
	u16 bg_free_blocks_count; // THESE are OBVIOUS
	u16 bg_free_inodes_count;
	ul6 bg_used_dirs_count;
	u16 bg_pad; // ignore these
	u32 bg_reserved[3];
}；

Block#8：块位图
块位图(Block Bitmap)用来描述整个块组中哪些块已用哪些块空闲。块位图本身占一个块，其中的每个bit代表本块组的一个block，这个bit为1代表该块正在使用，0表示空闲可用。由于Block#0未被使用，位图只有1439个有效位。
Block#9：索引节点位图
一个索引节点就是用来表示一个文件的数据结构。EXT2文件系统是使用有限数量的索引节点创建的。各索引节点的状态用B9的Imap中的一个位表示。
Block#10：索引（开始）节点块
每个文件都用一个128字节（EXT4中是256字节）的唯一索引节点结构体表示。

#该结构体中i_mode为u16或者2字节无符号整数#
struct ext2_inode {
	u16 i_mode; // 16 bits=|tttt |ugs|rwx|rwx|rwxl|
	ul6 i_uid; // owner uid
	u32 i_size; // file size in bytes
	u32 i_atime; // time fields in seconds
	u32 1_ctime; // since 00:00:00,1-1-1970
	u32 i_mtime;
	u32 i_dtime;
	i_gid; // group ID u16
	u16 i_links_count; // hard-link count
	u32 i_blocks;u32 i_flags; // number of 512-byte sectors
	u32 i_reservedl; // IGNORE // IGNORE
	u32 i_block[15]; // See details below
	u32 i_pad[7]; // for inode size = 128 bytes
}

i_mode前四位指定了文件类型，tttt=1000表示REG文件，0100表示DIR文件。ugs三位表示文件特殊用法，后九位是权限位。
i_size表示文件大小。
i_bolck[15]数据包含指向文件磁盘块的指针，磁盘块有

  • 直接块：i_block[0]至i_block[11]指向直接磁块盘
  • 间接块：i_block[12]指向一个包含256个块编号的磁盘块，每个- 块编号指向一个磁盘块
  • 双重间接块：i_block[13]指向一个指向256个块的块，每个块指向256个磁盘块
  • 三重间接块：i_block[14]对于小型EXT2文件可忽略

数据块紧跟在索引节点块之后。
目录条目
目录包含 dir_entry 结构

struct ext2_dir_entry_2(){
   u32 inode;
   u16 rec_len;
   u8  name_len;
   u8  file_type;
   char name[EXT2_NAME_LEN];
};

dir_entry 结构也是可扩充结构，名称字段包含1-255个字符，不含终止NULL。

邮差算法

一个城市有 M 个街区，编号从 0 到 M-1 ，每个街区又有 N 座房子，编号从 0 到 N-1。我们可以用 BA =（街区，房子）表示每一栋房子的位置，同时我们也可以使用线性方法将房子编为 0,1,...,N 等。

#只有从0开始计数式，转换才是有效的#
Linear_address LA = N*block + house;
Block_address BA = (LA / N, LA % N);

C语言中的 Test-Set-Clear 位
buf[1024]有1024个字节，用i表示，共有8129个位，已知位号BIT求求在哪个字节的第几位。

i=BIT / 8;
j= BIT % 8;

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;

将索引节点号转换为磁盘上的索引节点

在 EXT2文件系统中，每个文件都有一个唯一的索引节点结构。在文件系统磁盘上，索引节点从inode table块开始。每个磁盘块包含：

INODES_PER_BLOCK = BLoCK_SIZE/sizeof（INODE）

个索引节点。每个索引节点都有一个唯一的索引节点号，ino=1，2，…，从1开始线性计数。已知一个ino，如1234，那么哪个磁盘块包含该索引节点，以及哪个索引节点在该块中呢?我们需要知道磁盘块号，因为需要通过块来读/写一个真正的磁盘。

blcok = (info - 1) * INODES_PER_BLCOK + inode_table;
inode = (info - 1) % INODES_PER_BLCOK

显示超级块

以下C程序显示了EXT2文件系统的超级块。基本方法如下。

  1. 打开虚拟磁盘读取：int fd =open(“vidsk”.O_RDONLY)。
  2. 将超级块（Block#1或1KB的1024偏移量位置）读入char buf[1024]中。
  3. 让ext2_super_block *sp 结构体指向buf[]。然后，利用 sp->field 访问超级块结构体的各个字段。
/*********** superblock.c program ************/
#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>
// Cypedef u8, ul6, u32 SUPER for convenience typedef typedef typedef
typedef unsigned char u8;
typedef unsigned short ul6;
typedef unsigned int u32;
typedef struct ext2_super_block SUPER;
SUPER *sp;
char buf[1024];
int fd, blksize, inodesize;
int print(char *s, u32 x)
{
    printf("%-30s = %8d\n", s, x);
}
int super(char *device)
{
    fd = open(device, O_RDONLY);
    if (fd < 0) 
    {
        printf("open %s failed\n", device); 
        exit(1);
    }
    lseek(fd, (long)1024*1, 0);	// block 1 or offset 1024
    read(fd, buf, 1024);
    sp = (SUPER *)buf;	// as a super block structure
    // check for EXT2 FS magic number
    printf("%-30s = %8x ", "s_magic", sp->s_magic);
    if (sp->s_magic != 0xEF53)
    {
        printf("NOT an EXT2 FS\n"); exit(2);
    }
    printf("EXT2 FS OK\n"); 
    print("s_inodes_count",  sp->s_inodes_count);
    print("s_blocks _count", sp->s_blocks_count); 
    print("s_r_blocks_count", sp->s_r_blocks_count);
    print("s_free_inodes_count", sp->s_free_inodes_count);
    print("s_free_blocks_count", sp->s_free_blocks_count);
    print("s_first_data_blcok", sp->s_first_data_block); 
    print("s_log_block_s i z e", sp->s_log_block_size);
    print("s_blocks_per_group", sp->s_blocks_per_group); 
    print("s_inodes_per_group", sp-> s_inodes_per_group); 
    print("s_mnt_count", sp->s_mnt_count);
    print("s_max_mnt_count", sp-> s_max_mnt_count);

    printf("%-30s = %8x\n", "s_magic", sp->s_magic); 

    printf ("s_mtime = %s\n", ctime ((const time_t *)&sp->s_mtime)); 
    printf ("s_wtime = %s", ctime ((const time_t *)&sp->s_wtime)); 
    blksize = 1024 * (1 << sp->s_log_block_size);
    printf("block size = %d\n", blksize);
    printf("inode size = %d\n", sp->s_inode_size);
}

char *device = "vdisk";	// default device name
int main(int argc, char *argv[])
{
    if (argc>1)
        device = argv[1];
    super(device);
}

显示位图

以十六进制心事显示索引节点位图。

/************** imap program **************/
#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 = "vdisk";
int main(int argc, char*argv[])
{
    if(argc>1) dev = argv[1];
    imap(dev);
}

显示根索引节点

/******** innode.c file ********/
#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>
#define BLKSIZE 1024
typedef struct ext2_group_desc GD;
typedef struct ext2_super_block SUPER;
typedef struct ext2_dir_entry_2 DIR;
typedef struct ext2_inode INODE;
SUPER *sp;
GD *gp;
INODE *ip;
DIR *dp;
char buf[BLKSIZE];
int fd,firstdata, inodesize ,blksize, iblock;
char *dev = "vdisk";

int get_block(int fd, int blk, char *buf)
{
    lseek(fd, blk*BLKSIZE, SEEK_SET);
    return read(fd, buf, BLKSIZE);
}

int inode (char *dev)
{
    int i;
    fd = open(dev, O_RDONLY);
    if(fd < 0)
    {
        printf("open faild\n");
        exit(1);
    }
    get_block(fd, 2, buf);
    gp = (GD *)buf;
    printf("bmap_block=%d imap_block=%d inodes_table=%d \n", 
            gp->bg_block_bitmap,
            gp->bg_inode_bitmap,
            gp->bg_inode_table);
    iblock = gp->bg_inode_table;
    printf("----root inode information----\n");
    get_block(fd, iblock, buf);
    ip = (INODE *)buf;
    ip++;
    printf("mode = %4x ",ip->i_mode);
    printf("uid = %d gid = %d\n", ip->i_uid, ip->i_gid);
    printf("size = %d\n", ip->i_size);
    
    //unsigned int tmp = ip->i_ctime;
    printf("ctime = %s",ctime((const time_t *)&ip->i_ctime));
    printf("links = %d\n", ip->i_links_count);
    for ( i = 0; i < 15; i++)
    {
        if(ip->i_block[i])
        {
            printf("i_block[%d] = %d\n", i, ip->i_block[i]);
        }
    }
}
int main(int argc, char *argv[])
{
    if(argc>1) dev = argv[1];
    inode(dev);
}

显示目录条目

********Algorithm to step through entries in a DIR data block ********/
struct ext2_dir_entry_2 *dp;
char *cp;
int blk = a data block (number) of a DIR (e.g. i_block[0]);
char buf[BLKSIZE],temp[256];
get_block(fd, blk, buf);
// dir_entry pointer
//char pointer
// get data block into buf[]
dp= (struct ext2_dir_entry_2 *)buf;
cp=buf;
//as dir_entry
while(cp < buf + BLKSIZE){
strncpy(temp, dp->name, dp->name_len); // make name a string
temp [dp->name_len]= 0;
//ensure NULL at end
printf("%d %d %d %s\n", dp->inode, dp->rec_len, dp->name_len, temp);
cp += dp->rec_len;
dp = (struct ext2_dir_entry_2 *)cp;
//advance cp by rec_len
//pull dp to next entry
}

遍历 EXT2 文件系统树

  1. 读取超级块。检查幻数 s_magic（0xEF53），验证它确实是 EXT2 FS。
  2. 读取块组描述符块（1 +s_first_data_block），以访问组0描述符。从块组描述符的bg_inode_table条目中找到索引节点的起始块编号，并将其称为InodesBeginBlock。
  3. （3）读取 InodeBeginBlock，获取/的索引节点，即 INODE#2。
  4. 将路径名标记为组件字符串，假设组件数量为n。例如，如果路径名=/a/b/c，则组件字符串是"a""b""c"，其中n=3。用name[0]，name[1]，…，name[n-1]来表示组件。
  5. 从（3）中的根索引节点开始，在其数据块中搜索name[0]。为简单起见，我们可以假设某个目录中的条目数量很少，因此一个目录索引节点只有12个直接数据块。有了这个假设，就可以在12个（非零）直接块中搜索name[0]。目录索引节点的每个数据块都包含以下形式的 dir_entry 结构体;
    [ino rec_len name_len NAME] [ino rec_len name_len NAME]....
    其中 NAME 是一系列 nlen 字符，不含终止 NULL。对于每个数据块，将该块读入内存并使用 dir_entry *dp 指向加载的数据块。然后使用 name_len将 NAME 提取为字符串，并与 name[0] 进行比较。如果它们不匹配，则通过以下代码转到下一个 dir_entry:
    dp =(dir_entry*)((char *)dp + dp->rec_len);
    继续搜索。如果存在 name[0]，则可以找到它的 dir_entry，从而找到它的索引节点号。
  6. 使用索引节点号ino来定位相应的索引节点。回想前面的内容，ino 从1开始计数。使用邮差算法计算包含索引节点的磁盘块及其在该块中的偏移量。
blk =(ino - 1) / INODE8_PER_BLOCK + InodesBeginBlock;
offset = (ino - 1) % INODES_PER_BLOCK;

然后在索引节点中读取/a，从中确定它是否是一个目录（DIR）。如果/a不是目录，则不能有/a/b，因此搜索失败。如果它是目录，并且有更多需要搜索的组件，那么继续搜索下一个组件 name[1]。现在的问题是∶在索引节点中搜索/a的 name[1]，与第（5）步完全相同。
7. 由于（5）～（6）步将会重复n次，所以最好编写一个搜索函数∶

u32 search (INODE *inodePtr, char *name)
{
  // search for name in the data blocks of current DIR inode 
  // if found, return its ino; else return 0 )
}

然后我们只需调用 search()n次，如下所示。

Assume:n,name[0],....,name[n-1] are globals 
INODE *ip points at INODE of   /
for（i=0; i<n; i++）
{
  ino = search(ip, name[4])
  if(!ino){ // can't find name[i], exit;}
  use ino to zead in INODE and let ip point to INODE
}

如果搜索循环成功结束，ip必须指向路径名的索引节点。遍历有多个组的大型 EXT2/3 文件系统也是类似操作。

EXT2 文件系统的实现

(1)是当前运行进程的PROC结构体。在实际系统中，每个文件操作都是由当前执行的进程决定的。每个进程都有一个cwd，指向进程当前工作目录（CWD）的内存索引节点。
它还有一个文件描述符数组fa[]，指向打开的文件实例。
(2)是文件系统的根指针。它指向内存中的根索引节点。当系统启动时，选择其中一个设备作为根设备，它必须是有效的 EXT2 文件系统。根设备的根索引节点（inode #2）作为文件系统的根（/）加载到内存中。该操作称为"挂载根文件系统"
(3)是一个 openTable 条目。当某个进程打开文件时，进程fd数组的某个条目会指向openTable, openTable 指向打开文件的内存索引节点。
(4)是内存索引节点。当需要某个文件时，会把它的索引节点加载到minode槽中以供使用。因为索引节点是唯一的，所以在任何时候每个索引节点在内存中都只能有一个副本。在minode中，(dev, ino）会确定索引节点的来源，以便将修改后的索引节点写回磁盘。refCount字段会记录使用minode的进程数。
dirty字段表示索引节点是否已被修改。挂载标志表示索引节点是否已被挂载，如果已被挂载，mntabPtr将指向挂载文件系统的挂载表条目。lock字段用于确保内存索引节点一次只能由一个进程访问，例如在修改索引节点时，或者在读／写操作过程中。
(5)是已挂载的文件系统表。对于每个挂载的文件系统，挂载表中的条目用于记录挂载的文件系统信息，例如挂载的文件系统设备号。在挂载点的内存索引节点中，挂载标志打开，mntabPtr 指向挂载表条目。在挂载表条目中，mntPointPtr指向挂载点的内存索引节点。

第1级别实现了基本文件系统树，以实现指定函数，第2级别实现了文件内容的读/写函数，第3级别实现了文件系统的挂载、卸载和文件保护。

标签：count,笔记,学习,索引,第五,u32,inode,节点,block
From： https://www.cnblogs.com/qi-yu-lin/p/17765257.html

相关文章

  • 2023-2024-1 20231410刘珈岐 《计算机基础与程序设计》第3周学习总结
    2023-2024-120231410《计算机基础与程序设计》第3周学习总结•作业信息这个作业属于哪个课程https://edu.cnblogs.com/campus/besti/2023-2024-1-CFAP这个作业要求在哪里https://www.cnblogs.com/rocedu/p/9577842.html#WEEK03这个作业的目标自学计算机科学概论第......
  • 2023-2024-1学期 20231302邱之钊 《计算机基础与程序设计》第三周学习总结
    作业信息作业属于的课程2023-2024-1-计算机基础与程序设计作业要求2023-2024-1计算机基础与程序设计第一周作业作业目标数字分类与计数法、位置计数法、进制转换、模拟数据与数字数据、压缩与解压、数字化、信息安全作业正文2023-2024-1学期20231302邱之钊《......
  • [学习笔记]强连通分量
    定义什么是强连通分量？直白地说就是在一个有向图中，有一块区域，每个点都可以互相抵达。这里用一张图来说明一下。图中的\(1,2,3\)是一个强连通分量，因为他们可以互相抵达。Tarjan算法如何求强连通分量，最有名且最常用的就是Tarjan算法。先给出如下定义：\(dfn_u\)：深搜时被......
  • Javascript、axios、vue基础命令快速学习
    1.js:JavaScript基础学习JavaScript基础学习简单案例1.点击img1，则展示img1图片默认，点击img2则展示img2图片2.输入框鼠标聚焦onfocus后，显示小写toLowerCase()，失去焦点onblur后显示大写toUpperCase()3.点击全选按钮，所有复选框为被选中状态，点击反选则取消勾选状态JavaScrip......
  • 2023-2024-1 20231406 《计算机基础与程序设计》第3周学习总结
    2023-2024-120231406《计算机基础与程序设计》第3周学习总结作业信息这个作业属于哪个课程<班级的链接>（如[2023-2024-1-计算机基础与程序设计](https://edu.cnblogs.com/campus/besti/2023-2024-1-CFAP）这个作业要求在哪里<作业要求的链接>(如2023-2024-1计算机基础......
  • 学习笔记五
    第11章EXT2文件系统EXT2文件系统数据结构：EXT2文件系统使用一些关键的数据结构来组织文件和目录的存储和访问。以下是EXT2文件系统中常见的数据结构：超级块（Superblock）：是文件系统的起始部分，包含关键的元数据，如文件系统的大小、块的数量、inode（索引节点）的数量等信息。块组描......
  • 2023-2024-1 20231329《计算机基础与程序设计》第3周学习总结
    作业信息这个作业属于哪个课程https://edu.cnblogs.com/campus/besti/2023-2024-1-CFAP这个作业要求在哪里https://www.cnblogs.com/rocedu/p/9577842.html#WEEK03这个作业的目标 计算机科学概论第2章，第3章并完成云班课测试《C语言程序设计》第2章并完成云班课......
  • 2023_10_14_MYSQL_DAY_05_笔记
    2023_10_14_MYSQL_DAY_05_笔记https://www.cnblogs.com/tdskee/p/16536166.html{MySQL的优化多种方法（至少15条）}#查看触发器showtriggers;#删除触发器droptrigger触发器名;#建立触发器droptriggerifexistsdept_del;createtriggerdept_delafterdeleteon......
  • Linux该如何学习，给你支招
    如果你已经确定对Linux产生了兴趣，那么接下来我们介绍一下学习Linux的方法。这只是自己关于学习Linux的建议。一、如何去学习学习大多类似庖丁解牛，对事物的认识一般都是由浅入深、由表及里的过程，循序才能渐进。学习Linux同样要有一定的顺序和方法，当然这也是你学习本教程的意义......
  • 2023-2024-1 20231424 《计算机基础与程序设计》第3周学习总结
    作业信息作业课程2022-2023-1-计算机基础与程序设计作业要求2022-2023-1计算机基础与程序设计第一周作业这个作业的目标自学《计算机科学概论》第2章，第3章和《C语言程序设计》第2章作业正文链接https://www.cnblogs.com/2004lby/p/17764649.html教材学习内......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99