Linux学习笔记(1)

os 启动第一步
1． bios
cpu 的初始化
? 主机加电后，启动时钟发生器，在总线上产生powergood信号
? cpu收到reset信号，进入初始化过程
cpu转入8086实模式
ds = es = fs = gs = ss = 0
cs = 0xffff
ip = 0xfff0
进入bios加电自检过程（power on self test）
bios初始化
关中断，进行所有的post检测
将中断向量表的起始地址设为0x0000h
0x0000h~0x03ffh中存放了256个中断
建立了实模式下的中断向量表
bios的启动程序调用int 19h中断
将控制权转移给boot loader
? int 19h中断的功能
 int? 19h按照bios中的启动设备顺序查询每个启动设备
 在软盘的启动扇区或者硬盘的mbr中有boot? loader，那么这个扇区的最后两个字节必然为0xaa55。bios将这个扇区（512个字节）读入内存的0000:7c00开始的位置，然后跳转到内存0000:7c00的地方开始执行
? 如果在所有的启动设备上都找不到boot loader，那么就调用int 18h，将控制权交给bios rom basic，锁定机器，并且在屏幕上显示no boot device ***ailable
? 结论
 boot? loader应当存放在启动设备的第一个扇区中，对于硬盘是mbr，对于软盘是启动扇区
 安装了boot? loader的启动扇区的最后两个字节必须为0xaa55
 bios在post过程结束以后，调用int 19h中断，将boot? loader读入内存0000:7c00处。然后释放控制权，跳转到0000:7c00开始执行boot loader的代码
2． 最简单的boot loader：fdisk /mbr
硬盘的分区表结构
a) 第一个扇区为mbr
b) 一个硬盘上最多有4个主分区
c) 第一个主分区一般从cylinder 0, head 1, sector 1开始
d) cylinder 0, head 0, sector 2~n一般来说保留不用
e) 其余的主分区一般从cylinder x, head 0, sector 1开始

master boot record
f) 位于硬盘的cylinder 0, head 0, sector 1的位置
g) 大小为512字节
h) 其中存放了4个主分区的入口，每个入口占16个字节（这就是为什么一个磁盘最多只能有4个主分区的原因）
i) 最后两位为启动标志，如果mbr中有boot loader的话，则为0xaa55
j) 留给boot loader的空间为512-16x4-2=446字节
mbr中的boot loader的功能
k) 初始化，将自身搬移到0000:0600的位置
l) 在主分区入口表中寻找活动的分区
m) 调用int 13h ah=02将活动的分区的启动扇区读入内存0000:7c00处
n) 跳转到0000:7c00处执行活动分区的启动扇区中的代码
初始化，将自身搬移到0000:0600的位置

0000:7c00 cli 关中断
0000:7c01 xor ax,ax
0000:7c03 mov ss,ax 将堆栈段(ss)设为0
0000:7c05 mov sp,7c00 将栈顶指针(sp)设置为7c00
0000:7c08 mov si,sp 将si也设为7c00
0000:7c0a push ax
0000:7c0b pop es 将es设为0000
0000:7c0c push ax
0000:7c0d pop ds 将ds设为0000
0000:7c0e sti 开中断
0000:7c0f cld
0000:7c10 mov di,0600 将di设为0600
0000:7c13 mov cx,0100 准备移动256个字(512字节)
0000:7c16 repnz
0000:7c17 movsw 将mbr从0000:7c00移动到0000:0600
0000:7c18 jmp 0000:061d 开始搜索主分区入口表
? 在主分区入口表中寻找活动的分区

0000:061d mov si,07be si指向分区表入口（在总共512byte的主引导记录中，mbr的引导程序占了其中的前446个字节(偏移0h~偏移1bdh)，随后的64个字节(偏移1beh~偏移1fdh)为dpt(disk partitiontable，硬盘分区表)，最后的两个字节“55 aa”(偏移1feh~偏移1ffh)是分区有效结束标志）
0000:0620 mov bl,04 一共有4个表项
0000:0622 cmp byte ptr [si],80 是否为活动分区
0000:0625 jz found_active 找到了一个活动表项
0000:0627 cmp byte ptr [si],00 是否为非活动分区
0000:062a jnz not_active 不可识别的分区标识
0000:062c add si,+10 指向下一个表项(+16)
0000:062f dec bl 循环标志减一
0000:0631 jnz 0000:061d 继续循环
0000:0633 int 18 未找到可启动的分区，转到rom basic

对于磁盘结构可以详看 http://www.datasoon.com/fat32-1.htm

? 调用int13 ah = 02h读取启动扇区

0000:0635 mov dx,[si] 设置int 13调用中head和driver的值
0000:0637 mov cx,[si+02] 设置int 13调用中cylinder的值
0000:063a mov bp,si 保存活动分区入口表项地址
…
0000:065d mov di,0005 设置读取的重试次数
0000:0660 mov bx,7c00 将启动扇区读取到0000:7c00(es:bx)
0000:0663 mov ax,0201 准备调用int 13读取一个扇区al = 01
0000:0666 push di 保存重试次数di
0000:0667 int 13 调用int 13读取一个扇区到0000:7c00
0000:0669 pop di 恢复重试次数di
0000:066a jnb int13ok 如果读取成功，则跳转至启动代码
0000:066c xor ax,ax 准备int 13 ah = 0复位磁盘
0000:066e int 13 调用int 13复位磁盘
0000:0670 dec di 重试次数减一
0000:0671 jnz 0000:0660 进行下一次重试

? 运行启动扇区中的代码

0000:067b mov di,7dfe 指向启动扇区中的启动标识
0000:067e cmp word ptr [di],aa55 检查启动表识是否为0xaa55
0000:0682 jnz display_msg 如果不是，则保错
0000:0684 mov si,bp 恢复si，指向活动分区入口表项
0000:0686 jmp 0000:7c00 跳转至启动扇区的代码

? 结论
 boot loader放在可启动设备的第一个扇区中?
 boot? loader的大小受扇区大小和其他附加信息的限制。在mbr中，为446字节
 boot? loader在从bios中接手cpu的控制权时，位于内存地址0000:7c00处
 fdisk /mbr产生的boot? loader不具备启动os的能力，其本质上是一个chain loader，用于引导一个有启动os能力的boot loader
3．如何引导os：dos boot loader
? boot sector的结构
 boot sector位于每个分区的第一个扇区?
 boot? sector的第一个部分是一个跳转指令和一个nop，以跳转实际的boot loader的代码中
 bios parameter? block中存放了和这个分区相关的一系列参数
 bpb之后就是实际的boot loader的代码?
? 最后是一个可启动分区标识0xaa55
? 使用format /s对boot sector做的修改
 在0x000h处写入bpb?
? 在0x03eh处写入dos boot loader的代码
 在0x1feh处写入0xaa55标识?
? 此外，format /s还要
? 初始化fat表
 将io.sys和msdos.sys写入，占据fat表前两个表项?
? dos boot loader的功能
? 初始化
 计算根目录所在的fat表的扇区号?
 读取根目录的第一个扇区到0000:0500?
? 检查前两个表项是否为io.sys和msdos.sys
 将io.sys的前3个扇区读入0000:0700或者0070:0000的位置中?
? 在寄存器中保留一些信息，然后跳转到0070:0000处执行操作系统代码
 dos boot loader和mbr中的boot? loader的最大区别在于对于文件系统的理解
? mbr中的boot loader不理解文件系统，所以无法启动特定的os
? dos boot loader提供了对于fat文件系统的支持，所以能够启动在fat文件系统上的dos
? dos boot loader知道os的内核文件的位置，其主要的工作就是将内核文件读入内存，然后将控制权转交给os
4．硬盘寻址方式：chs vs lba
? 最早期的chs寻址
 最早期的磁盘寻址是通过cylinder/head/sector进行的，int? 13h中给出的chs参数直接指定了数据的物理位置
 例：int 13h ah = 02?
? ah = 02 al = 读入的扇区数目
? ch = cylinder低8位 cl = cylinder高两位
? dh = head dl = 操作的磁盘（80h for c:）
? 限制：
? cylinder <= 1024
? head <= 16
? sector <= 63
? 总容量 < 1024 x 16 x 63 x 512b = 528mb
? l-chs & p-chs
? 为了解决直接寻址的问题，现代的hd中，chs只有逻辑上的意义，不表达物理上的实际位置
 l-chs用在支持chs? translation的bois的int 13 ah = 0xh的调用中
? cylinder <= 1024
? head <= 256
? sector <= 63
? 总容量 <= 1024 x 256 x 63 x 512b = 8gb
? p-chs用在hd的接口上
? cylinder <= 65535
? head <= 16
? sector <= 63
? 总容量 <= 65535 x 16 x 63 x 512b = 136gb
? lba：large block addressing
? lba的出现是为了解决chs模式地址受限的问题
? lba提供了一种线性的寻址方式：cylinder 0，head 0，sector 1相当于lba地址0。往后每增加一个扇区，lba地址加一
? lba地址和chs地址可以通过如下公式转换
? lba = ( (cylinder * heads_per_cylinder + heads ) * sectors_per_track ) + sector - 1
? 新型的bois提供了int 13h ah = 4xh的扩展磁盘调用以支持lba模式
? lba：large block addressing
 int 13h ah = 42h?
? ah = 42h dl = 操作的磁盘（80h for c:）
? ds:si = disk address packet
 disk address packet的格式?

? 结论：寻址方式和boot loader的关系
 bios在post过程以后调用int 19h，使用的是chs寻址?
 如果一个os自身的boot? loader使用的是chs寻址模式，那么在老式bios上不能启动528mb以后的分区，在新式bios上不能启动8g以后的分区（lilo的问题）
? 只有支持lba的boot loader才能支持启动8g以后分区上的os
4．支持多os引导的boot loader
? 支持多os引导的boot loader是：
 一段在启动时被bios int 19调用的代码?
 能够理解系统中安装的多个不同的os?
? 用户可以选择启动特定的os
 程序根据用户选择，通过直接载入或者chain load的方法，启动选中的os?
? 支持多os引导的boot loader需要：
 自身足够的小，或者支持多阶段载入，以能够安装在mbr或者boot sector中?
? 能够理解多种文件系统的格式，以便能够找到存放在不同文件系统下的系统内核
? 能够理解多种文件格式(elf/a.out)，以便能够正确的载入不同的系统内核
? 支持chs和lba两种磁盘访问模式，以便能够正确的启动8g以后的分区
 支持chain loader，以便通过特定的boot? loader载入os
? 支持多os引导的boot loader在执行32位os的内核代码前，需要构建的机器状态：
? cs必须是一个32位的可读可执行的代码段，偏移为0，上限为0xffffffff
 ds, es, fs,? gs和ss必须为32位的可读写段，偏移为0，上限为0xffffffff
 2?0号地址线必须在32位地址空间中可用（初始固定为0）
? 分页机制必须被关闭
 处理器中断标记被关闭?
 eax的值为0x2badb002?
 ebx中存放了一个32位的地址，指向由boot? loader填充的一系列启动信息
引自：multiboot specification

5．实例分析：grub
? grub是：
? grand unified bootloader的缩写
 是一个灵活而强大的boot loader?
? 其能够理解多种不同的文件系统和可执行文件格式，从而能够引导多种os
 通过将boot? loader所需要的功能封装成一套脚本语言，从而能够按照特定的方式引导os
? grub的i/o
 支持chs和lba两种磁盘访问模式?
? (device[,part-num][,bsd-subpart-letter])的方式访问设备：(hd0), (hd1, 0), (hd0, a), (hd0, 1, a)
 文件访问?
? 通过路径形式访问：/boot/grub/menu.lst
? 通过扇区形式访问：0+1，200+1，300+300
? grub的脚本：
 root指定一个启动的设备?
? kernel指定操作系统的内核
 boot正式启动一个os?
 makeactive激活一个分区?
? chainloader调用启动设备上的boot loader
? 启动linux
 root (hd0,0)?
 kernel? /vmlinuz root=/dev/hda1
 boot?
? 启动windows
 root (hd0,0)?
? chainloader +1
 makeactive?
 boot?
? grub的组成
 stage1?
? grub的第一部分，安装在mbr或者boot sector中
? 用于引导stage2或者stage1.5
 stage2?
? grub的核心影像，用于提供grub的主要功能
 stage1.5?
? stage1与stage2之间的桥梁，安装在0磁道上第一个扇区之后
? stage1不理解文件系统，但是stage1.5可以
? stage1.5最终调用stage2
 nbgrub/pxegrub?
? grub的网络启动模块
? stage1的结构
? 为了保持和fat/hpfs bios的兼容性，所以保存bpb
 在bpb之后的stage1配置数据区，在安装的时候被填写?
? 在数据区之后，才是代码段
 最后是0xaa55启动扇区标志?
?
? stage1的流程
? 在stage1的配置数据区中存放了stage2所在的磁盘号、lba地址以及stage2的载入地址
? stage1不需要理解任何的文件系统，只需要根据给出的扇区号，读入stage2的第一个扇区即可
 stage1相当于前面分析的mbr中的boot? loader
? stage2的第一部分start.s
 start.s存放在stage2文件的第一个扇区里面?
? stage2剩余部分的lba地址和内存的载入地址是放在start.s的firstlist和lastlist之间的，这个数据段位于start.s代码的尾部，在安装的时候被写入，称为block list
 block list以全0项结尾?
? stage2的第一部分start.s
? 在start.s的代码开始执行的时候，ds:si所指向的内存地址的内容是stage1中准备好的，用于为int 13h调用准备参数
? start.s的功能就是根据block list，将stage2剩余的部分读入内存，然后跳转到0x8200h处执行stage2的功能代码
? stage2的第二部分asm.s
 在asm.s中定义了一系列的函数的实现，包括grub得主入口函数main?
? 在main函数中，完成了如下的工作：
? ds = es = ss = 0
? 建立实模式/bios栈，esp = 0x2000 - 0x10，向低地址方向增长
? 转入保护模式
? 建立并清空保护模式栈
? 调用cmain，进入grub的c代码中（stage2.c）
? 在cmain中，完成了如下的工作：
? 设法打开/boot/grub/menu.lst这个配置文件
 根据配置文件，构建用户菜单?
 如果菜单构建成功，则调用run_menu?
? 如果菜单构建失败，则调用enter_cmdline
? 问题：文件系统
 在这个时候，grub已经开始访问文件系统?
? grub如何对付不同的文件系统？
? grub中的文件系统层：disk_io.c
 grub中为每一个文件系统提供了一个抽象层?
? 文件系统用fsys_entry描述（filesys.h）
struct fsys_entry
{
char *name;
int (*mount_func) (void);
int (*read_func) (char *buf, int len);
int (*dir_func) (char *dirname);
void (*close_func) (void);
int (*embed_func) (int *start_sector, int needed_sectors);
};
? 全局变量fsys_table包含了grub支持所有文件系统，通过fsys_table和fsys_type，从而可以以统一的方式访问不同的文件系统
? grub中的命令处理：buildin
 grub支持的每个命令，均有一个buildin和其对应?
? 这些buildin被定义在buildins.c中
 分析以下3个命令：?
 chainloader?
 kernel?
? boot

? chainloader
 检查--force标记?
 调用grub_open打开文件，这里的文件用block? list表示（+1）
 调用grub_read读入一个扇区到0000:7c00的位置?
 检查启动扇区标志0xaa55?
? kernel
 检查--type和--no_mem_option标志?
 调用load_image，读入指定的内核文件?
? load_image中处理了elf和a.out的各种变形
? load_image通过对于内核文件的分析，识别出被启动的os的种类（通过内核文件的magic number）
? load_image针对不同种类的os的内核提供了特定的载入代码（这里的代码异常复杂，牵涉到了不同的os的实现细节，未作分析）
? 最终填充mbi (multiboot information)结构
? boot
? 通过执行chainloader或者kernel以后，当前需要启动的内核的类型已经确定了
? 在执行boot的时候，根据确定的内核类型，每一种内核均有一种启动的方法
? 对于linux，最后调用了stop函数实现控制权的转移
? 对于chainloader，最后也是调用了stop函数实现控制权的转移
? boot
? 通过执行chainloader或者kernel以后，当前需要启动的内核的类型已经确定了
? 在执行boot的时候，根据确定的内核类型，每一种内核均有一种启动的方法
? 对于linux，最后调用了stop函数实现控制权的转移
? 对于chainloader，最后也是调用了stop函数实现控制权的转移

 

 

内存管理之段页机制 by lxwpp

内存管理(memory management)
?内存地址空间
?分段机制
?分页机制
?cpu多任务和保护模式

内存地址空间概念

->逻辑地址：是指由程序产生的由段选择符和段内偏移地址两个部分组成的地址。
->线形地址：是逻辑地址到物理地址变换之间的中间层，是处理器可寻址的内存空间（称为线性地址空间）中的地址。32位，4gb
->物理地址：是指出现在cpu 外部地址总线上的寻址物理内存的地址信号，是地址变换的最终结果地址。32位无符号整数表示 n虚拟内存：是指计算机呈现出要比实际拥有的内存大得多的内存量。

 

分段机制
段是定义内存区域的另一种机制，与页类似。这两种机制可以重叠：地址一定在某一页面内，也可能处于段内。 n

段的描述符：描述段的属性的一个8字节存储单元

段描述符的一般格式
 
保存描述符项的描述符表
gdt:主要的基本描述符表，该表可被所有程序用于引用访问一个内存段。
idt:保存有定义中断或异常处理过程的段描述符
ldt:该表应用于多任务系统中，通常每个任务使用一个ldt 表

段选择符
 
分段机制
逻辑地址通过分段机制自动映射（变换）到中间层4g线形地址空间（32位的）

寻址的步骤：
1）在段选择符中装入16位数，同时给出32位地址偏移量（比如在es1,edi中）
2）根据段选择符中的索引值、ti及rpl值，再根据相应描述符表寄存器中的段地址和段界限，进行一系列合法性检查（如特权级、界限检查）
如果段无问题，就取出相应的描述符放入段描述符高速缓冲寄存器中
3）将描述符中的32位段基地址和放在 esi、edi等中的32位有效地址相加，形成了32位物理地址

cpu 进行地址变换（映射）的主要目的是为了解决虚拟内存空间到物理内存空间的映射问题。

实模式和保护模式寻址
实模式：寻址一个内存地址主要是使用段和偏移值，段值被存放在段寄存器中（例如ds），并且段的长度被固定为64kb。段内偏移地址存放在任意一个可用于寻址的寄存器中（例如si）。因此，根据段寄存器和偏移寄存器中的值，就可以算出实际指向的内存地址
 

相比：
1）和实模式下的寻址相比，段寄存器值换成了段描述符表中相应段描述符的索引值以及段表选择位和特权级－－段选择符
2）偏移值还是使用了原实模式下的概念

保护模式
1）段寄存器中存放的不再是被寻址段的基地址，而是一个段描述符表（segment descriptor table）中某一描述符项在表中的索引值
2）段的长度可变，由描述符中的内容指定
 

分页机制
分页机制功能是把由段机制转换而来的线性地址转换位物理地址

转化过程如图：
 

转换步骤
1）cr3包含着页目录的起始地址，用32位线性地址的最高10位a31~a22作为页目录的页目录项的索引，将它乘以4，与cr3中的页目录的起始地址相加，形成相应页表的地址
2）从指定地址中取出32位页目录项，它的低12位为00，这32位是页表的起始地址用32位线性地址中的a21-a22位作为页表中的页面索引，将它乘以4，与页表的起始地址相加，形成32位页面地址。
3）将a11-a0作为相对于页面地址的偏移量，与32位页面地址相加，形成23位页面物理地址。

扩展分页
页的大小为4mb（2的22次方），扩展前是4kb
线性地址分为两个域：最高10位的目录域和其余22位的偏移量，如图
【图】
 

虚拟内存管理的数据结构
?linux中页目录(pgd) 、页面中间目录(pmd)、页表(pt)，分别由数据结构pgd_t，pmd_t，pte_t来表示。
?typedef struct { unsigned long pmd; }pmd_t;
?typedef struct { unsigned long pte; } pte_t;
?typedef struct { unsigned long pgd; } pgd_t;
?typedef struct { unsigned long pgprot; }pgprot_t;

#define page_shift 12
//偏移量的位数，因此页面大小为4kb n#define page_size(1ul<<page_shift) n#define page_mask (~(page_size-1)
//值定义为0xfffff000,用以屏蔽掉偏移量域的所有位

定义页目录大小、页目录掩码等信息的代码如下：
?#define pgdir_shift 22 //线性地址中页目录偏移量位数
?#define pgdir_size (1ul<< pgdir_shift) ?//一个页目录项的地址空间(4m) ?#define pgdir_mask (~(pgdir_size-1)) ?//页目录掩码
?#define ptrs_per_pgd 1024 ?//页目录表项个数

其中当时提到的一个问题就是：虚拟地址和逻辑地址究竟有和区别？

 

 

 

内存初始化和分配回收

1 内存初始化
2 内存的分配和回收（伙伴算法,slab,cache)

内存初始化

startup_32 函数
start_kernel 函数

startup_32 函数
本函数完全用汇编语言实现，主要功能是启用分页机制。 l当linux启动时，首先运行在实模式下（对物理地址操作），随后就要转到保护模式下（对虚拟地址操作）运行,linux内核代码的入口点就是/arch/i386/kernel/head.s中的startup_32。

startup_32主要做的工作：l

编译内核过程中，首先初始化一个页目录swapper_pg_dir，和前8m物理地址空间的页表pg0，pg1。这样，初始状态下，用户空间和内核空间都只映射了开头的两个目录项，即8m的空间，并且有着相同的映射。 l内核开始运行后运行在内核空间，那末，为什么把用户空间的低区（8m）也进行映射呢？简而言之，[为了实模式到保护模式的平稳过渡]这是因为刚开启页面映射时，（并不说明linux内核真正进入了保护模式）指令寄存器eip仍指向地址，仍会以物理地址取指令，如果页目录只映射内核空间，而不映射用户空间的低区，则一旦开启页映射机制后就不能继续执行了。

初始页目录swapper_pg_dir的映射图
【图，要插入】

当startup_32将页目录swapper_pg_dir的物理地址装入控制寄存器cr3，并把cr0的最高位置1，即开启了分页机制。随后，编译程序使所有的符号地址都在虚拟地址空间中，指令寄存器eip指向虚拟地址空间的某个地址，就使cpu转入了内核空间，完成从实模式到保护模式的过渡。 函数setup_arch确定start_kernel中内存初 始化的起始地址start_mem和结束地址end_mem。 start_mem是内存映像的结束地址_end对应的核心态当startup_32将页目录swapper_pg_dir的物理地址装入控制寄存器cr3，并把cr0的最高位置1，即开启了分页机制。随后，编译程序使所有的符号地址都在虚拟地址空间中，指令寄存器eip指向虚拟地址空间的某个地址，就使cpu转入了内核空间，完成从实模式到保护模式的过渡。 函数setup_arch确定start_kernel中内存初 始化的起始地址start_mem和结束地址end_mem。 start_mem是内存映像的结束地址_end对应的核心态虚拟地址，end_mem是将bios自检时确定的物理内存大小转换成核心态的虚拟地址

ps：在pc中，最初1mb的存储空间的使用很特殊。开头640kb（0x0~0x9ffff）为ram，从0xa0000开始的空间用于cga、ega、vga等各种图形卡。从0xf0000到0xfffff（最高的4kb）是在eprom或flash存储器中的bios。 l l这个阶段初始化后的，物理内存初始化的内核映像见后图：

start_kernel函数l

本函数实现整个linux内核的初始化，有关内存初始化的部分介绍如下： paging_init函数初始化页表；页描述符的建立由free_area_init函数完成；mem_init函数设置物理页面的标志位，整理空闲区； kmem_cache_init kmem_cache_sizes_init函数初始化cache_cache，通用cache，slab分配器  startup_32和start_kernel函数完成后物理内存的初始化情况：
【图要插入】

内存分配和回收之伙伴算法(buddy)
产生背景： 内核应该为分配一组连续的物理页而建立一种稳定、高效的分配策略。为此，必须解决内存管理中的外部碎片问题。频繁的请求和释放不同大小的一组连续页，必然导致在已分配物理页的块内分散许多小块的空闲页。这样，即使有足够的页满足请求，要分配一个大块的连续页就可能无法满足。 【备注】这是在物理存储器上分配内存【/备注】
算法工作原理： linux的伙伴算法把所有的空闲物理页分组为10个块链表，每个块链表分别包含大小为1，2，4，8，16，32，64，128，256和512个连续的页（2的幂次方）。每个块的第一个页的物理地址也是该块大小的整数倍。分配一个块（例128个连续页）时，首先在对应的链表中查找空闲块。如果找到，则直接分配；否则，查找下一个更大的块，将其中的一部分分配给进程，剩余部分插入相应的块链表中。

满足以下条件的两个块就称为伙伴：
1）两个块的大小相同 l2）两个块的物理地址连续 l伙伴算法把满足以上条件的两个块合并为一个块，算法是迭代算法

伙伴算法的数据结构

伙伴系统的数据结构是free_area_struct: l struct free_area_struct{ l struct page *next; //双向链表指针，链 l //表每个成员是一个块的第一个物理页描述符 l struct page *prev; l unsigned int *map; //指向对应的位图 l unsigned long count;//链表元素个数 l }

数据结构的分析：free_area[0]到free_area[9]都是free_area_struct类型的结构，分别对应不同大小块的链表，并且分别对应一个位图。
位图的大小取决于系统物理页面的数量。第k项位图的每一位描述大小为2k的物理页的两个伙伴块的状态。如果位图的某一位为0，表示一对伙伴块中或者都忙或者都空闲；如果为1，肯定有一块为忙。当伙伴块都空闲时，内核把他们当作一个大小为2k+1的块来处理。例如，一个128mb的ram，可以分成32768个页，16384个大小为2个页的块，…，则free_area[0]的位图有16384位，free_area[1]的有8192位…

伙伴系统数据结构图
【图】

slab分配机制

为什么要提出slab机制l原因：
伙伴系统采用页作为基本内存区，适合于对大块内存的请求。但是如果请求内存的大小与分配给它的大小不匹配，容易产生内部碎片。 l

解决之道：
linux2.0采用的方法是：linux提供按几何分布的内存区大小，即建立了13个按几何分布的空闲内存链表，大小从32到131056字节。伙伴系统的调用，既为了获得额外所需的物理页以存放新的内存区，也为了释放不再包含内存区的物理页。
linux2.2起采用了slab分配模式
linux采用slab分配器模式管理内存区。它把内存区看作对象，对象有一组数据结构和构造、析构函数组成，但为提高效率，指向构造和析构函数的指针都为null。 slab分配器把对象分组放进高速缓存。每个高速缓存存放着同一种类型的对象。高速缓存被划分成多个slab，每个slab由一个或多个连续的物理页组成。这些页中包含已分配的对象，也包含空闲对象 linux中引入slab主要目的是减少对伙伴算法的调用次数

slab分配器的组成：
注意：这里的高速缓存不是cpu中的高速缓存。它实际存在于物理内存中，由于分配速度相对于伙伴系统比较快，称谓高速缓存。
【图】
实际上，缓冲区就是主存中的一片区域，把这片区域划分为多个块，每块就是一个slab，每个slab由一个或多个页面组成，每个slab中存放的就是对象

cache的数据结构l l
struct kmem_cache_s { l kmem_slab_t *c_freep;//指向第一个含有 l //空闲对象的slab的指针 l
unsigned long c_flags; //描述cache静态特性的标志，例如slab（object）描述符的 存储位置，外部存储还是内部存储 l
unsigned long c_offset; //cache中对象的大 小（如果要求对象的起始地址必须是在 l //内存对齐，就可以对这个大小取整）

lunsigned long c_magic; //从一组预先定义好的数值中选出的一个魔数，用于检查高速缓存的当前状态和一致性
lunsigned long c_inuse; /* kept at zero */ lkmem_slab_t *c_firstp; //slab链表表头 lkmem_slab_t *c_lastp; //slab链表表尾
lspinlock_t c_spinlock;//多个处理器同时访问cache 时起保护作用的旋转锁 lunsigned long c_growing; lunsigned long c_dflags;//描述cache动态特性的标志，例如内核是否正在为cache分配新的slab

size_t c_org_size; lunsigned long c_gfporder;//每个slab包含的连续页面数目为2c_gfporder个 lvoid (*c_ctor)(void *, kmem_cache_t *, unsigned long); //构造函数 lvoid (*c_dtor)(void*, kmem_cache_t*, unsigned long); //析构函数 lunsigned long c_align; //对象的对齐因子 lsize_t c_colour; /* cache colouring range */ lsize_t c_colour_next;/* cache colouring */

unsigned long c_failures; lconst char *c_name; //cache名 lstruct kmem_cache_s *c_nextp; l //指向下一个cache l kmem_cache_t *c_index_cachep; l //指向外部对象描述符所在的高速缓存 l //的高速缓存描述符 l};

高速缓存分为两种类型：通用和专用。前者只由slab分配器用于自己使用，后者由内核其余部分使用。 l 通用高速缓存是： l （1）第一个高速缓存包含由内核使用的其余高速缓存的高速缓存描述符。cache_cache变量包含第一个高速缓存的描述符。 l （2）第二个高速缓存包含没有存放在slab内的slab描述符。cache_slabp变量指向第二个高速缓存描述符。

（3）13个高速缓存包含几何分布的内存区。cache_sizes数组元素分别指向13个高速缓存描述符，与其相关的内存区大小为32，64，…，131072字节。 l 系统初始化时调用kmem_cache_init和kmem_cache_sizes_init建立通用高速缓存，调用kmem_cache_create创建专用高速缓存。

slab的数据结构
typedef struct kmem_slab_s { struct kmem_bufctl_s *s_freep; //指向slab //中第一个空闲对象的指针 struct kmem_bufctl_s *s_index;//指向外 //部对象描述符所在的内存区 unsigned long s_magic; unsigned long s_inuse;//slab中当前分配 //的对象数目 struct kmem_slab_s *s_nextp;//指向同一 //个cache中与该slab相邻的两个slab的指针 struct kmem_slab_s *s_prevp;//构成双向链表

l unsigned long _offset:slab_offset_bits, l s_dma:1; l} kmem_slab_t;

对象的数据结构l对象数据结构如下： ltypedef struct kmem_bufctl_s { l union { l struct kmem_bufctl_s *buf_nextp; l //指向下一个空闲对象 l kmem_slab_t *buf_slabp; //对象被分配， l //且对象描述符在外面，指向对象所在的 l //slab的slab描述符 l void * buf_objp; //对象被分配，且对象描 l //述符在外面，则指向该对象 l } u; l} kmem_bufctl_t;

对象描述符可以存放在slab内部，紧接描述符所描述的对象之后； 如果存放在slab之外，存放在由cache_sizes指向的一个通用高速缓存中。对象本身所在的高速缓存，通过cache的c_index_cachep和slab的s_index两个域被连到它们的描述符所在的高速缓存。

slab分配器所管理的对象可以在内存对齐，也就是说，存放它们的起始物理地址是一个给定常数的倍数，这个常数叫做对齐因子，存放在cache的c_align域中。 存放对象大小的c_offset域要考虑增加填充字节数来对齐。如果对象大小大于高速缓存行的一半，就在ram中把这个对象的大小对齐到ll_cache_bytes的倍数，也就是行的开始。否则，这个对象的大小就是ll_cache_bytes的因子取整。

slab着色的产生背景：由于相同大小的对象很可能存放于高速缓存的相同的偏移量处，在不同slab内具有相同偏移量的对象最终可能映射在同一高速缓存行中。slab分配器使用slab着色的策略解决这个问题。 slab分配器利用空闲未用的字节来对slab着色，可用颜色个数为空闲字节数/c_align+1。

如果用颜色col对一个slab着色，那末，第一个对象偏移量（相对于slab起始地址）等于col*c_align。这个值存放在slab的s_offset域。
【图】

 

slab内存分配机制：
作用：分配内核内存（小内存）
几何分布的内存区大小
内碎片小于50%
32-131072 共13级
1． 所存放数据类型影响分配区
2． 内核函数倾向于反复请求同一类型内存区
3． 请求根据发生频率分类
4． 引入对象若不是按几何分布，可以用硬件高速缓存
5． 尽量限制使用伙伴系统

3种相关数据结构
slab_s 一个slab块的管理信息
list: slab链表
colouroff: 染色偏移
s_mem: 指向第一个对象
inuse: 活动的对象数（已分配）
free: 第一个空闲对象号

kmem_bufctl_t 其实就是unsigned int，形成数组，用于标识slab中的每个对象是否已用，并形成空闲对象链

kmeme_cache_s 缓存块管理信息
slabs
firstnotfull
objsize 对象大小
flags
num 一个slab中对象个数
spinlock
gfporder每个slab的页面数的对数
colour colour_off colour_next 染色相关变量
slabp_cache 对off slab方式使用，指乡向公共的cache_slabp,它存放每个slab的slab_t
构造，析构函数
name
next

结构：在cache_cache中分配，存放所有的cache，这些cache中，有cache_slabp，专门分配off slab模式的slab_t与kmem_bufctl_t数组，也有由cache_sizes指针数组所指向的一些通用cache，另有一些独立的专用cache
每个cache管理一组slab，每个slab管理一组对象，这些slab中的对象大小，个数，都相同，占用的空间也相同，只是存放的起示位置不同N两种方式：
on slab 小对象用，<512
偏移 | slab_t | kmem_bufctl_t数组 | 对象 | 剩余空间
off slab >=512 slab_t kmem_bufctl_t数组都由cache_slabp统一分配，于是，结构为
染色机制：
页的统一偏移，可能映射到硬件cache的同一块，而每个slab中的开始部分，是访问频率最高的，所以使用染色机制，使每个slab中起始部分偏移不一样，从而充分利用硬件cache

cache结构中的colour为最大偏移调整计数，colour_off为每次调整的数值，colour_next为计数值，0到colour

对齐
字对齐，高速缓存行对齐

缓存区创建
kmem_cache_create()
1． 错误检查
2． 从cache_cache中分配一个对象做为新建的这个cache
3． 完成对齐，字对齐，高速缓存行对齐
4． >512，选off slab方式，反之为on slab
5． 找出一个slab的大小（页的倍数）满足3个条件，至少可以容纳一个对象，内存浪费不至于太大，slab块不至于太大
6． 可能因为剩余空间够大，能放入slab_t和kmem_bufctl_t，于是改回on slab方式
7． 设置染色相关数据。colour与剩余空间大小有关
8． 设置参数，slab链表构造（指向自身），firstnotfull指向这个slab
9． 将这个cache插入cache_sizes的指针表，并插入管理chche的链表cache_chain

缓存区释放，扩充与收缩

对象分配与释放

 

内核空间
2005－07－07

物理内存区：
简单的说：可以减去一个偏移或使用virt_to_phys（）函数完成。
由get_free_page或kmalloc函数所分配的连续内存都陷于物理映射区域，所以它们返回的内核虚拟地址和实际物理地址仅仅是相差一个偏移量（page_offset），你可以很方便的将其转化为物理内存地址，同时内核也提供了virt_to_phys（）函数将内核虚拟空间中的物理映射区地址转化为物理地址。要知道，物理内存映射区中的地址与内核页表是有序对应，系统中的每个物理页框都可以找到它对应的内核虚拟地址（在物理内存映射区中的）。

虚拟内存分配区
它的问题相对要复杂些，这是因为其分配的内核虚拟内存空间并非直接操作页框，而是分配的是vm_struct结构。该结构逻辑上连续但对应的物理内存并非连续，也就是说它vamlloc分配的内核空间地址所对应的物理地址并非可通过简单线性运算获得。

如何映射？
每个非连续区的描述符
struct vm_struct{ n unsigned long flags;
void *addr;
unsigned long size;
struct vm_struct *next; n};

vmlist
物理内存区 8m 内存区4k内存区4k

vm_struct->get_vm_area()

nstruct vm_struct *get_vm_area(unsigned long size)
{
};

函数首先调用kmalloc()为描述符分配一个内存区，然后查找一个可用的的线性地址区间，如果存在，就初始化这个描述符的所有域，返回内存区的起始地址。

vm_struct->get_vm_area->vmalloc()
分配内存区
void * vmalloc(unsigned long size)
{ n void *addr;
struct vm_struct *area;
size=(size+page_size-1)&page_mask;
if(!seze||size>(num_physpages<<page_shift))
return null;
area=get_vm_area(size);
if(!area)
return null;
if (vmalloc_area_pages(unsigned long)addr,size)
{
vfree(addr);
return null;
}
return addr;
}

vm_struct->get_vm_area()->vmalloc()->vmalloc_area_pages()
inline int vmalloc_area_pages(unsigned long address,unsigned long size,int gfp_mask,pgprot_t prot)
{
pgd_t *dir;
unsigned long end=address+size;
int ret;
dir=pgd_offset_k(address);//导出内存区起始地址在页目录中的目录项；
spin_lock(&init_mm.page_table_lock);
do{ pmd_t *pmd;
pmd=pmd_alloc(&init_mm,dir,address);//为新的内存区创建一个中间页目录项
ret=-enomem;
if(alloc_area_pmd(pmd,address,end-address,gfp_mask,prot)) n break;
address=(address+pgdir_size)&pgdir_mask;
dir++; n ….
}while(address && (address<end)); n nreturn ret; n} nalloc_area_pmd为新的中间页目录分配所有相关页表，并更新页的总目录，调用pte_alloc_kernel()函数来分配一个新的页表，之后调用alloc_area_pte()为页表项分配具体的物理页面 n

至此，完成了非连续内存区到物理页面的映射

 

固定映射
vaddr=_fix_to_virt(_end_of_fixed_addresses-1)&pmd_mask; nfixrange_init(vaddr,0,pgdbase);
枚举类型_end_of_fixed_addresses用作索引， _fix_to_virt宏返回给定索引的虚地址。函数fixrange_init()为这些虚地址创建合适的页表项，再由set_fixmap()函数完成地址的映射

vaddr=pkmap_base(0xfe000000)4g-32mb
fixrange_init(vaddr,vaddr+page_size*last_pkmap,pgd_base);
pgd＝swapper_pg_dir+_pgd_offset(vaddr);
pmd＝pmd_offset(pgd，vaddr);
pte=pte_offset(pmd,vaddr);

highmem映射nlinux内核使用highmem接口将高位内存动态映射到内核地址空间的一小部分（这部分就是4m专门保留用来实现这个目的），以此提供间接访问。这部分内核地址空间就是所谓的kmap段

include/linux/highmem.h
void *kmap(struct page *page)
{ return page_address(page);}
#define page_address(page) ((page)->virtual)

 

 

管理区zone
为了对物理页面进行有效的管理，linux把物理页面划为3个区

专供dma使用的zone_dma区（小于16mb)
常规的zone_normal区（大于16mb小于896mb）
内核不能直接映射的zone_highme区（大于896mb)

【图】
n2）在标准配置下, 物理区最大长度为896m,系统的物理内存被顺序映射在物理区中,在支持扩展页长(pse)和全局页面(pge)的机器上,物理区使用4m页面并作为全局页面来处理. 当系统物理内存大于896m时,超过物理区的那部分内存称为高端内存,低端内存和高端内存用highmem_start_page变量来定界,内核在存取高端内存时必须将它们映射到"高端页面映射区".

3） linux保留内核空间最顶部128k区域作为保留区,紧接保留区以下的一段区域为专用页面映射区,它的总尺寸和每一页的用途由fixed_address枚举结构在编绎时预定义,用__fix_to_virt(index)可获取专用区内预定义页面的逻辑地址.在专用页面区内为每个cpu预定义了一张高端内存映射页,用于在中断处理中高端页面的映射操作.（高端内存映射区属于固定内存区的一种，见下页代码）
4） 距离内核空间顶部32m, 长度为4m的一段区域为高端内存映射区,它正好占用1个页帧表所表示的物理内存总量, 它可以缓冲1024个高端页面的映射.在物理区和高端映射区之间为虚存内存分配区, 用于vmalloc()函数,它的前部与物理区有8m隔离带, 后部与高端映射区有8k的隔离带

enum fixed_addresses
{
#ifdef config_x86_local_apic nfix_apic_base, /* local (cpu) apic) -- required for smp or not */
#endif

#ifdef config_x86_io_apic nfix_io_apic_base_0, nfix_io_apic_base_end = fix_io_apic_base_0 + max_io_apics-1,
#endif
#ifdef config_x86_visws_apic nfix_co_cpu, /* cobalt timer */ fix_co_apic, /* cobalt apic redirection table */ nfix_li_pcia, /* lithium pci bridge a */ nfix_li_pcib, /* lithium pci bridge b */
#endif
#ifdef config_highmem nfix_kmap_begin, /* reserved pte’s for temporary kernel mappings */ nfix_kmap_end = fix_kmap_begin+(km_type_nr*nr_cpus)-1
#endif n__end_of_fixed_addresses

在一般情况下，linux在初始化时，总是尽可能的将所有的物理内存映射到内核地址空间中去。如果内核地址空间起始于0xc0000000，为vmalloc保留的虚拟地址空间是128ｍ，那么最多只能有(1g-128m)的物理内存直接映射到内核空间中，内核可以直接访问。如果还有更多的内存，就称为高端内存，内核不能直接访问，只能通过修改页表映射后才能进行访问。

内存分区可以使内核页分配更加合理。当系统物理内存大于1g时，内核不能将所有的物理内存都预先映射到内核空间中，这样就产生了高端内存，高端内存最适于映射到用户进程空间中。预映射的部分可直接用于内核缓冲区，其中有一小块可用于dma操作的内存，留给dma操作分配用，一般不会轻易分配。内存分区还可以适应不连续的物理内存分布，是非一致性内存存取体系(numa)的基础

先看看代码中的注释:
in linux\include\linux\mmzone.h(version 2.4.16, line 67)
/*
* on machines where it is needed (eg pcs) we divide physical memory
* into multiple physical zones. on a pc we have 3 zones:
*
* zone_dma < 16 mb isa dma capable memory
* zone_normal16-896 mb direct mapped by the kernel
* zone_highmem > 896 mb only page cache and user processes
*/ n高端页面的映射
1)
高端物理页面共享一块4m的映射区域，该区域对齐于4m页边界，并用一张页表(pkmap_page_table)来完成映射操作。高端页面的映射地址由其页结构中virtual成员给出。
（void *virtual)（page结构）
2)
高端映射区逻辑页面的分配结构用分配表(pkmap_count)来描述，它有1024项，对应于映射区内不同的逻辑页面。当分配项的值等于零时为自由项，等于1时为缓冲项，大于1时为映射项。映射页面的分配基于分配表的扫描，当所有的自由项都用完时，系统将清除所有的缓冲项，如果连缓冲项都用完时，系统将进入等待状态。
3)
页缓冲尽可能地使用高端页面，当通过块结构刷新高端页面时，系统会在提交块设备<br>> ,原请求块，同时中转块被释放。

 

 

tlb(翻译后援存储器）

时间：2005-07-05
地点：同济大学科技园

by lxwpp Z7br" SS{ +f lV[ 本_资_料_来_源_于_贵_州_学_习_网 电脑课堂LINUX教程 Http://wwW.gzU521.coM )Z7br" SS{ +f lV

reson
由于页表尺寸较大，因此许多分页方案都只能把它保存在内存中，但这种设计对性能有很大的影响。（分页的时候，系统性能下降2/3 n 计算机设计者们发现：大部分程序倾向于对较少的页面进行大量的访问。因此只有一小部分页表项经常被用到，其他的很少被使用。

concept
tlb使个小的虚拟寻址的缓存，不需要经过页表就能把虚拟地址转换为物理地址的小的硬件设备

components
一个用来访问tlb的虚拟地址组成部分
【图】
tlb寄存器是由虚拟页号，有效位，保护位等组成

steps
1 cpu产生一个虚拟地址
2 mmu从tlb中取出相应的pte，如果命中转3；如果不命中，进行常规页表查找，用找到的pte淘汰tlb中的一个条目
3 mmu将这个虚拟地址翻译成物理地址并且把它发送到高速缓存/主存
4 高速缓存/主存将所有的请求的数据字节返回给cpu

figure1（tlb命中）
 
figure2（tlb不命中）

example
前提：虚拟地址14位，物理地址12位，页面大小64字节，tlb共有16个条目，缓存16个组 n给定虚拟地址0x3d4

flush－software
软件管理tlb
刚刚介绍的tlb故障处理都是由mmu硬件完成的。
现在的管理工作是由软件完成的。tlb条目由os显式装入，在没有命中的时候,mmu不是到页表中找到并装入信息而是产生一个故障交给os，os找到页面，淘汰一个条目，装入新条目 ntlb取一个合理的尺寸以减少不命中的频率，software管理tlb的效率高 n性能提高：实行预装入机制

essence
无论软件管理还是硬件管理，在tlb没命中的时候，都是对页表执行索引操作找出所引用的页面，然后把pte加入到tlb中。

flush
完成的工作：
（1）保证在任何时刻内存管理硬件所看到的进程的内核映射和内核页表一致
（2）如果负责内核管理的内核代码对于用户进程页面进行了修改，那么用户的进程在被允许继续执行前，要求必须在缓存中看到正确的数据

function
flush_cache_foo()
flush_tlb_foo()
地址空间改变前必须刷新缓存，防止缓存中存在非法的空映射。在刷新地址后，由于页表的改变，必须刷新tlb以便硬件可以把新的页表信息装入tlb nvoid flush_cache_all(void)
void flush_tlb_all(void)
用来通知相应机制，内核地址空间的映射已经被改变，意味着所有的进程都已经改变

 

 

vfs概述 nvfs的的数据结构
超级块（super_block)
索引节点(inode)
目录项(dentry)
文件(file) n与进程相关的文件结构 n
文件系统的安装
n文件系统的注册
根文件系统的安装
普通文件系统的安装
n目录项的缓冲
路径名到目标节点的转换

vfs概述
虚拟文件系统（vfs）的所有数据结构都是在运行之后建立的，在卸载时删除，而在磁盘上没有这些数据结构。
vfs不是真正的文件系统。与vfs相对应的ext2,msdos等称为具体的文件系统

linux系统中vfs和具体文件系统关系图
[图]

vfs的作用:
对具体文件系统的数据结构进行抽象，以一种统一的数据结构进行管理
接受用户层的系统调用，如read(),write(),open()等
支持多种具体文件系统之间的相互访问
接受内核其他子系统的操作请求，比如内存管理子系统，进程管理子系统

超级块（super_block)

对具体文件系统的超级块是文件系统中最重要的数据结构，它用来描述整个文件系统信息【组织结构和管理信息】。不涉及文件系统的内容
vfs超级块是各种具体文件系统在安装时建立的，并在这些文件系统卸载时自动删除。
vfs超级块实际上应该说成是某个具体文件系统的vfs超级块
超级块对象由super_block结构组成

super_block结构主要包括以下一些域:

描述文件系统整体信息的域
用于管理超级块的域 n
与具体文件系统相联系的域

描述文件系统整体信息的域：

kdev_t s_dev 具体文件系统的块设备标识符 n
unsigned long s_blocksize 具体文件系统的数据块大小
unsigned char s_blocksize_bits
块大小占用的位数，例如，块大小1024字节，则该值为10
unsigned long long s_maxbytes 文件最大长度
unsigned long s_flags 超级块标识
unsigned long s_magic 魔数

用于管理超级块的域:
struct list_head s_list 用于形成超级块链表
struct semaphore s_lock 锁
struct rw_semaphore s_umount 读写超级块时进行同步
unsigned char s_dirt 该超级块修改标识
struct dentry *s_root 指向该文件系统安装目录的dentry结构
int s_count 对超级块的使用记数
struct list_head s_dirty “脏”索引节点链表的头节点
struct list_head s_locked_inodes 要同步的索引节点链表的头节点
struct list_head s_files 该超级块上的所有打开文件链表头节点

与具体文件系统相联系的域：
struct file_system_type *s_type 指向具体文件系统file_system_struct结构的指针 struct super_operations *s_op 指向具体文件系统super_operations结构的指针 n struct dquot_operations *dq_op 指向具体文件系统用于限额操作的dquot_operations结构的指针
union u 各种文件系统的特定信息。

超级块链表
所有超级块对象，以双向循环链表的形式连接在一起，链表头节点保存在super_blocks变量（定义在fs/super.c）：
[图]

索引节点对象(inode)

文件系统处理文件所需的信息
索引节点对文件是唯一的
具体文件系统的索引节点存储在磁盘上，使用的时候，必须调入内存，填写vfs的索引节点。所以vfs的索引节点是动态节点。

inode结构主要包括以下一些域

描述文件信息的域
用于索引节点管理的域
用于索引节点操作的域
其他

kdev_t i_dev 设备标识号
umode_t i_mode 文件类型和访问权限
link_t i_nlink 与该索引节点建立的连接数
uid_t i_uid 文件所有者号
gid_t i_gid 所有者所在组号
kdev_t i_rdev 实际设备号
off_t i_size 文件大小（字节）
unsigned long i_blksize 块大小
unsigned long i_blocks 该文件占用块数
time_t i_atime 文件最后访问时间
time_t i_mtime 文件最后修改时间
time_t i_ctime 节点修改时间
unsigned long i_version 版本号
struct semaphore i_zombie 僵死索引节点的信号量 JCV x8c !y!h-[转 贴 于 我 的 学 习 网 电脑课堂LINUX教程 HTtp://wwW.gzU521.coM)JCV x8c !y!h-

用于索引节点管理的域
struct list_head i_hash 形成哈希链表
struct list_head i_list 形成索引节点链表
struct list_head i_dentry 目录项链表的头节点

用于索引节点操作的域：
struct inode_operations *i_op 索引节点的操作
struct super_block *i_sb 指向该文件系统的超级块
atomic_t i_count 使用该节点的进程数
struct file_operations *i_fop 文件操作
unsigned char i_lock 用于同步操作，锁定节点
struct semaphore i_sem 用于同步的信号量
wait_queue_head_t *i_wait 指向索引节点等待队列
unsigned char i_dirt 修改标识
struct file_lock *i_flock 指向文件加锁链表的指针
struct dquot *i_dquot[maxquotas] 索引节点的磁盘限额

其它域
unsigned long i_state 索引节点的状态标识
unsigned int i_flags 文件系统的安装标识
atomic_t i_writecount 写进程的引用计数
unsigned int i_attr_flags 文件创建标识
union u 共同体

索引节点链表

索引节点至少在下列链表之一：
（1）未用索引节点链表 链表头节点保存在inode_unused变量，i_count=0; n （2）正在使用索引节点链表 链表头节点保存在inode_in_use变量，i_count>0, i_nlink>0
（3）每个超级块的脏索引节点链表
链表头节点保存在相应超级块的s_dirty，i_count>0, i_nlink>0, i_state & i_dirty

未用索引节点链表[图]
正在使用索引节点链表[图]
脏索引节点链表[图]

目录项（dentry)

每个文件除了有一个索引节点结构外，还有目录项dentry结构。

dentry结构代表的是逻辑意义上的文件，在磁盘上没有对应的映象。而inode结构代表的是物理意义上的文件，对于一个具体的文件系统，在磁盘上有对应的映象。

一个dentry结构必有一个inode结构，而一个inode可能对应多个dentry结构。
由于从磁盘读入一个文件并构造相应的目录项需要花费大量的时间，而在完成对目录项的操作后，可能后面还会用到，所以在内存中要保留它。

dentry结构定义在include/linux/dcache.h中

dentry的域

atomic_t d_count 目录项引用计数
unsigned int d_flags 目录项标识
struct inode * d_inode 与文件名关联的索引节点
struct dentry * d_parent 父目录的目录项
struct list_head d_hash 形成目录项哈希链表
struct list_head d_lru 未使用的目录项链表
struct list_head d_child 形成父目录的子目录项链表
struct list_head d_subdirs 子目录链表的头节点
struct list_head d_alias 形成索引节点别名链表
int d_mounted 该目录项安装文件系统数目
struct qstr d_name 目录项名（快速查找）
unsigned long d_time 由d_revalidate函数使用
struct dentry_operations *d_op 目录项操作函数
struct super_block * d_sb 所在文件系统的
void * d_fsdata 具体文件系统的数据，目前只为nfs所用
unsigned char d_iname[dname_inline_len] 短文件名，24个字符

目录项的状态

每个目录项属于以下4种状态之一：
空闲状态：目录项不包含有效信息，未被vfs使用，由slab分配器进行管理。
未使用状态：目录项还没有被使用，d_count为null，但是其d_inode仍然指向相关的索引节点。该目录项包含有效信息，但必要时，其内容可以被丢弃。
正在使用状态：目录项正在被使用，d_count>0，d_inode指向相关的索引节点，包含有效信息，不能被丢弃。
负状态：与目录项相关索引节点已不存在，d_inode为null

未用目录项链表
目录项哈希管理
父子目录关系
目录项与索引节点

file对象

在include/linux/fs.h中定义了file结构，用于保存文件位置等对文件的操作信息。描述的是进程怎样与一个打开文件的交互过程
file对象是在文件打开描述符创建。
多个file结构可以指向同一个文件。

file域

struct file { /* 定义在include/linux/fs.h */
struct list_head f_list; /*形成链表*/
struct dentry *f_dentry; /*文件对应的dentry结构*/
struct vfsmount *f_vfsmnt; /*文件所在文件系统的vfsmount结构*/
struct file_operations *f_op; /*文件操作函数结构*/
atomic_t f_count; /*引用计数*/ n unsigned int f_flags; /*文件标识*/
mode_t f_mode; /*文件打开方式*/
loff_t f_pos; /*文件当前位置*/
unsigned long f_reada, f_ramax, f_raend, f_ralen, f_rawin; n /*预读标识、预读最多页面数，上次预读后的文件指针、预读字节数、预读页面数*/
struct fown_struct f_owner; /*异步i/o消息的文件拥有者*/
unsigned int f_uid, f_gid; /*赋予当前进程的uid和gid*/
int f_error; /*网络写操作的错误码*/
unsigned long f_version; /*版本号*/
void *private_data; /*文件私有数据区*/

file 对象

每个文件对象总是包含在下列链表之一：

以打开的文件链表：超级块的s_files作为头节点，链入属于该文件系统的已打开的文件
“未使用”文件对象链表：既可以用作文件对象的内存高速缓存，又可以当作超级用户的备用存储器，即使系统动态内存用完，也允许超级用户打开文件。

在这个链表中的对象，f_count总是null，链表首元素地址放在free_list(定义在fs/file_table.c中)。该链表至少包含nr_reserved_files(定义在include/linux/fs.h，默认为10)个对象。 n

新分配文件对象链表：每个元素至少有一个进程使用，f_count!= n null，首元素地址存放在anon_list(定义在fs/file_table.c中)。

当需要分配一个新文件对象时，调用get_empty_filp (定义在fs/ file_table.c中) ，如果未使用链表中的元素个数多于nr_reserved_files，则为新文件使用其中一个元素，否则进入正常内存分配。

文件系统打开的文件链表

与进程相关的文件结构
files_struct
fs_struct

files_struct:进程打开文件表

对于每个进程，包含一个files_struct结构，用来记录文件描述符的使用情况，定义在include/linux/sched.h

files_struct

struct files_struct {
atomic_t count; /*使用该表的进程数*/
rwlock_t file_lock; /*锁*/
int max_fds; /*当前文件对象的最大数*/
int max_fdset; /*当前文件描述符最大数*/
int next_fd; /*数值最小的最近关闭文件的文件描述符*/
struct file ** fd; /*指向文件对象数组的指针*/
fd_set *close_on_exec; /*指向执行exec时需要关闭的文件描述符*/
fd_set *open_fds; /*指向文件描述符屏蔽字集合*/
fd_set close_on_exec_init;/*执行exec时需要关闭的文件描述符初值集合*/
fd_set open_fds_init; /*文件描述符的屏蔽字集合*/
struct file * fd_array[nr_open_default];/*文件对象指针数组*/
}; /*nr_open_default=32*/

fd指向文件对象的指针数组，数组长度存放在max_fds中。通常，fd指向fd_array，fd_array大小为32。如果进程打开的文件数多于32，内核就分配一个新的更大的文件指针数组，其地址放入fd，同时更新max_fds。
open_fds指向open_fds_init，open_fds_init表示当前打开文件的文件描述符屏蔽字。max_fdset存放屏蔽字的位数，默认是1024，需要的时候可以通过expand_fdset( )函数扩展到1024*1024。

可以通过fget( )函数，将文件对象与描述符链接起来

文件系统信息fs_struct

用来描述文件系统信息的fs_struct结构，定义在include/linux/fs_struct.h:
struct fs_struct {
atomic_t count; /*使用该结构的进程数*/
rwlock_t lock; /*读写锁*/
int umask; /*初始文件许可权*/
struct dentry * root, * pwd, * altroot;
/*根目录、当前目录、替换根目录的目录项*/
struct vfsmount * rootmnt, * pwdmnt, * altrootmnt;
/*根目录、当前目录、替换根目录的vfsmount结构*/ n};
umask由umask( )系统调用使用，文件打开的实际权限为期望的权限&umask。 n
该结构的一个作用是用于路径定位时，提供根目录、当前目录和替换根目录。

与进程有关的文件结构间的关系

文件系统注册

文件系统是指可能会被挂载到目录树中的各个实际文件系统
注册过程实际上将表示各实际文件系统的 struct file_system_type 数据结构的实例化，然后形成一个链表，内核中用一个名为 file_systems 的全局变量来指向该链表的表头

file_system_type
struct file_system_type {
const char *name; /*文件系统名，出现在/proc/filesystems中，且唯一*/
int fs_flags; /*文件系统标识*/
struct super_block *(*read_super) (struct super_block *, void *, int); /*读取该文件系统在设备上的超级块*/
struct module *owner; /*如果是由模块载入的，则指向该模块；否则，为null*/ n
struct file_system_type * next; /*用于形成注册文件系统链表*/
struct list_head fs_supers; /*超级块链表*/

文件系统的安装
根文件系统的安装

1）建立临时的inode和file对象，在其中填入信息，如设备号，根据文件系统安装标志设置file的f_mode域等
－>调用blkdev_open()函数，完成设备的准备工作
－>顺序搜索表file_systems中的每一个注册的文件系统，用自己的read_super函数读取root_dev超级块，如果成功，获得根文件系统的超级块和根目录的inode和其目录结构
－>把pwd设置为根目录的目录项对象
－>调用add_vfsmnt()把第一个元素插入到已安装文件系统链表中

安装常规文件系统
系统安装了根文件系统后，就可以安装其他文件系统。每个文件系统安装在系统目录树的一个目录上。
安装一个文件系统可以通过系统调用mount实现。
mount系统调用在内核的实现函数是sys_mount( ) 。（fs/namespace.c）

整个安装过程中最核心的函数就是do_kern_mount()了，为了创建一个新安装点（vfsmount）,该函数需要做一下几件事情：

1 检查安装设备的权利，只有root权限才有能力执行该操作。
2 get_fs_type()在文件链表中取得相应文件系统类型（注册时被填加到练表中）。
3 alloc_vfsmnt()调用slab分配器为vfsmount结构体分配存储空间，并把它的地址存放在mnt局部变量中。
4 初始化mnt->mnt_devname域

5 5 分配新的超级块并初始化它。do_kern_mount( )检查file_system_type描述符中的标志以决定如何进行如下操作：根据文件系统的标志位，选择相应的方法读取超级块(比如对ext2,romfs这类文件系统调用get_sb_dev()；对于这种没有实际设备的虚拟文件系统如 ramfs调用get_sb_nodev())——读取超级块最终要使用文件系统类型中的read_super方法

目录项缓存
引言
/home/user/src/foo.c
每次对foo.c访问，vfs都要沿着嵌套目录依次解析全部路径：/、home、user、src和foo.c
为了避免每次访问该路径名都要进行此操作，vfs会在目录项缓存中搜索路径名，如果找到了就无需花费力气解析
相反如果节点该目录项缓存中不存在，vfs就必须解析，完毕后将目录项对象加入到dcache中

目录项缓存包括的主要部分
被使用的目录项链表
该链表通过索引节点对象i_dentry项链接，因为一个给定的索引节点可能有多个链接，所以可能就有多个目录项对象，因此用一个链表链接它们 最近使用的双向链表
该链表含有未被使用的和负状态的目录项对象。由于该链以时间顺序插入，所以最后释放的目录项对象放在链表首部，最近最少使用的目录项对象总是靠近链表尾部。一旦目录项的告诉缓存空间开始变小的的时候，内核就从链表的尾部删除元素，使得多数最近经常使用的对象得以保留。 哈希表和相应的哈希函数快速地将给定的路径名解析未相关的目录项对象。

哈希表石由数组dentry_hashtable表示，其中每一个元素都是指向一组具有相同链值的目录项对象的指针。通过d_lookup()函数在缓存中查找，如果访问的对象不在目录项高速缓存中，哈希函数返回一个空值

从路径名到目标节点CSAyD V
Guf3$",XY(本 文来 源于 我 的学 习网电脑课堂LINUX教程 htTP://WWw.GZu521.COm]CSAyD V
Guf3$",XY

ext2

ext2磁盘布局在逻辑空间中的映象

超级块
ext2超级块是用来描述ext2文件系统整体信息的数据结构，是ext2的核心所在。它是个ext2_super_block数据结构

一些域的解释

文件系统中并非所有的块都可以使用，有些块是保留的，给超级块专用，块的数目在i_r_blocks_count定义。一旦空闲块总数等于保留块，普通用户就无法申请数据快了。如果保留块也被使用，则系统就可能无法使用了。 逻辑快是从0号开始，对块大小为1kb的文件系统，s_first_block为1，对其它文件系统，则为0 s_log_block_size以2的幂次方表示块的大小，单位1024字节 ext2要定期检查自己的状态，s_lastcheck记录最近一次检查状态的时间，而s_checkinterval则规定了两次检查状态的最大允许时间间隔 如果检查到文件系统有错误，则对s_errors赋一个错误的值

ext2_sb_info
每个文件系统自己的特性信息
[图]

ext2索引节点
[图]

解释:
逻辑块－>物理块
ext2通过索引节点中的数据块指针数组进行逻辑块到物理块的映射。指针数组15项，前12个为直接块指针，后3个分别为“一次间接块指针”，“二次间接块指针”，“三次间接块指针”。

索引12中的元素包含一个块的逻辑号，这个块代表逻辑块号的一个二级数组。数组对应的文件快号从12到b/4+11,b是文件系统块的大小 索引13中的元素包含一个块的逻辑号，这个块代表逻辑块号的一个三级数组。数组对应的文件快号从b/4+12到(b/4)^2+(b/4)+11 索引14中的元素包含一个块的逻辑号，这个块代表逻辑块号的一个四级数组。数组对应的文件快号从 (b/4)^2+(b/4)+12到(b/4)^3+(b/4)^2+(b/4)+11

组描述符

ext2_group_desc的数据结构
struct ext2_group_desc{ ? _u32 bg_block_bitmap;//块位图所在的块号_u32 bg_inode_bitmap;索引节点位图所在的块号
_u32 bg_inode_table; 索引节点表的首块号
_u16 bg_free_blocks_count;空闲块号
_u16 bg_free_inodes_count; 空闲索引节点数
_u16 bg_used_dirs_count; 分配给目录的节点数
_u16 bg_pad; 填充，对齐到字；
_32 [3] bg_reserved;用null填充12个字节 ?}

每个块组都有一个相应的组描述符描述它，所有组描述符形成一个组描述符表，组描述符可能占多个数据块。 作用大。一旦描述符破坏，整个组块无法使用，再每个组块中备份

位图
数据块位图：每一位表示数据块的使用情况，1表示已分配，0表示空闲 索引位图也类似

用高速缓存管理位图块 每个高速缓存最多同时只能装入ext2_max_grop_loaded个位图块或索引块 采用类似lru算法管理高速缓存 ext2_sb_info中的四个域来管理这两个高速缓存s_block_bitmap_number[]存放进入高速缓存的块号（块组号），s_block_bitmap[]存放了相应块在高速缓存中的地址

load_block_bitmap()调入指定的数据块位图

1）如果指定的块组号大于块组数，出错，结束
?2）通过搜索s_block_bitmap_number[]数组可知位图块是否进入了高速缓存，如果进入，则结束，否则，继续 ?
3）如果块组数不大于ext2_max_grop_loaded，高速缓存就可以同时装入所有块组数据块位图，无论采用什么算法，只要从s_block_bitmap_number[]找到一个空闲的元素，将块组号写入，然后将位图块调入高速缓存，最后将它在高速缓存中的地址写入s_block_bitmap[]数组中

4）如果块组数大于ext2_max_grop_loaded，则需要采用一下算法：
首先通过s_block_bitmap_number[]数组判断高速缓存是否已满，若未满，则操作过程类似上面的步骤，不同的事要将s_block_bitmap_number[]数组各元素后移一位，用空出的第一个元素存储块组号，s_block_bitmap[]做同样的处理 如果高速缓存已满，将s_block_bitmap[]数组最后一项所指的位图块从高速缓存中交换出去，然后调入指定的位图块，最后对这两个数组操作类似上面相同的操作

索引节点表
每个块组中索引节点都存储在各自的索引节点表中，并且按照索引节点号依次存储。索引节点表一般要占好几个数据块 所有索引节点的大小，128字节。所以1024字节的数据块可以包含8个索引节点 计算索引节点表占用的块数：一个块组中索引节点总数/每个块中的索引节点数。
块组中索引节点总数放在超级块中的s_inode_per_group域

索引节点的域
_u16 i_mode 文件类型和访问权限
_u16 i_uid 文件所有者的标志符 ?
_u32 i_size 以字节为单位的文件长度
_u32 i_atime
_u32 i_ctime 时间信息 ?
_u32 i_dtime
_u16 i_links_count 硬链接计数器
_u32 i_blocks 文件的数据块数

ext2目录项
目录是一种特殊的文件，它是由ext2_dir_entry这个结构组成的列表。 结构是变长的，这样可以减少磁盘空间的浪费。 长度有限制：
文件名最长只能为255个字符
一般自动变成为4的倍数，不足补null 目录中有文件和子目录，每一项对应一个ext2_dir_entry

ext2_dir_entry结构

struct ext2_dir_entry{
_u32 inode; //节点号
_u16 rec_len; // 目录项的长度
_u8 name_len; //名字长度
char name[ext2_name_len];//文件名 };

各类文件使用数据块

常规文件
在创建的时候是空的，不需要数据块，只有在开始有数据的时候才需要数据块 目录
ext2以一种特殊的文件实现了目录，文件的数据块存放了文件名和相应的索引节点号 符号链：如果路径名不大于60个字符，就把它存放在索引节点的i_blocks域中，因此无需数据块。否则就需要一个单独的数据块

设备文件，管道和套接字
不需要数据块，所有必要的信息都存放在索引节点中。

ext2的文件类型

文件类型 描述
0 未知
1 正规文件
2 目录
3 字符设备
4 块设备
5 命名管道
6 套接字
7 符号链

创建索引节点

函数为ext2_new_inode()
参数为：dir,mode
新创建节点必须插到一个目录中，参数dir指的是这个目录的索引节点对象的地址 -----const struct inode *dir
mode指的是创建索引节点的类型

步骤
调用get_empty_inode()分配一个新的索引节点对象分配一个新的索引节点对象，并sb=dir->i_sb; 调用lock_super()获得超级块对象的互斥访问 如果新创建的索引节点是目录，，则要考虑将来是否能将其属下的文件都容纳在一个块组中。所以应该找个其空闲索引节点的数量超过整个设备上的平均值这么一个块组，而不惜离开父节点所在的块组，另起炉灶^_^ 如果新创建的节点是文件，首先考虑将其索引节点分配在其目录所在的块组，若无空闲索引节点，则沿着此块组往下继续查找。若还是没有，则从第一个块组从头开始查找。

确定了索引节点分配在哪个的块组，就要从索引节点位图中分配一个节点，（调用load_inode_bitmap())，从中寻找第一个空位，这样就得到了第一个空闲磁盘索引节点号 分配磁盘索引节点：把索引节点位图的相应位设置好，并把含有这个位图的缓冲区标记为“脏” 把块描述符的bg_free_inodes_count域减1。如果新的索引节点是个目录，则增加bg_used_dirs_count

把磁盘超级块的s_free_inodes_count减1， 初始化索引节点的域，如设置i_ino, 把新的索引节点插入到inode_hashtable。 调用mark_inode_dirty()把这个索引节点对象移到超级块的脏索引节点链表 调用unlock_super()释放超级块对象 返回新索引节点对象的地址

创建文件系统ext2

初始化超级块和组描述符 检查是否有缺陷的块，如果有，创建有缺陷块的链表 对每个块组，保留存放超级块、组描述符、索引节点表以及两个位图所需要的磁盘 把索引节点位图和每个块组的数据映射位图初始化为0 初始化每个块组的索引节点链表 创建/root目录 创建lost+found目录（有缺失和缺陷的） 更新这个两个块组中的位图 把有缺陷的块组织起来放在lost+found目录中