[TOC]
前言
「Linux 0.11」内核于 1991 年 9 月 3 日发布,代码总量只有 10,000 行左右,但是麻雀虽小,五脏俱全。0.11版本的内核已经具备了基本的文件系统、进程管理等。
仅仅支持 x86 架构(Intel 80386 处理器),原因是因为 Linus Torvalds 使用的电脑为这台,因此他首先针对这一体系结构进行了开发。该版本的内核仅支持单个处理器,不支持对称多处理(SMP)。
需要较少的内存才能运行。通常,它需要至少2MB的物理内存,但可以在更小的系统上运行。这个版本不支持虚拟内存(交换空间),因此所有的内存管理都发生在物理内存中。
支持基本的文件系统,最初它使用的是Minix文件系统。硬盘大小通常非常有限,远远小于今天的标准。硬盘驱动程序和文件系统支持仅适用于有限的硬件。
有基本的输入和输出支持。它可以与键盘和显示器进行简单的交互,但不支持图形界面。它还可以与串口通信进行简单的终端交互。
Linux 0.11 最初不支持网络,因此没有网络堆栈。网络功能被后续版本添加到内核中。
简介
本篇以文档为主,记录我阅读闪客的「Linux源码趣读」过程中对每一回的笔记以及总结,所以有可能最后这篇文章会非常的冗余并且没有章法。
为了保证内容看起来不算太冗余,一部分一部分的记录。
正文
第二部分 “大战”前期的初始化工作
第 11 回 整个操作系统就二十几行代码
1 | void main(void) /* This really IS void, no error here. */ |
第 12 回 管理内存前先划分出 3 个边界值
在 main 函数的第一部分,ROOT_DEV为系统的根文件设备号,drive_info 为之前 setup.s 程序获取并存储在内存 0x90000 处的设备信息。
而在之后的操作是对整个内存进行划分,main_memory 和 buffer_memory。
第 13 回 主内存初始化
主内存的初始化与缓冲区内存的初始化分别在两块部分中,mem_init 初始化了主内存。
整个函数中就是对 mem_map[3840] 数组的各个元素进行复制,未被使用的内存赋值为 0,使用的内存赋值上使用次数。
最终 1MB 以下的内存区域没有记录,因为这是内核所在的区域,1MB ~ 2MB 是缓冲区标记为 USED,2MB以上是主内存,目前没有程序使用标记为 0。
1 | /* |
这是像主内存中申请一页空闲内存并返回物理内存页所在地址的函数。
针对 80386 架构的汇编代码,用于获取一个空闲页面的物理地址,并将该页面标记为已用。这是 Linux 内核 0.11 版本的代码,用于管理内存分页。
以下是代码的详细解释:
__asm__("std ; repne ; scasb\n\t"
: 这是内联汇编的开始,它执行一系列的汇编指令。std
指令将方向标志位设置为向下,repne
迭代scasb
指令,直到找到一个非空的字节。这段代码是在搜索一个未被使用的页面。"jne 1f\n\t"
: 如果未找到空闲页面,跳转到标签1
,这个标签是在函数的最后定义的。"movb $1,1(%%edi)\n\t"
: 找到一个未使用的页面后,将该页面标记为已用,这里将地址edi
处的字节设置为 1。"sall $12,%%ecx\n\t"
: 将ecx
寄存器的值左移 12 位,相当于乘以 4096,以获得页面的物理地址。"addl %2,%%ecx\n\t"
: 将LOW_MEM
的值(%2
,可能是一个常数)加到ecx
中,以获取实际的页面物理地址。"movl %%ecx,%%edx\n\t"
: 将页面物理地址存储在edx
寄存器中。"movl $1024,%%ecx\n\t"
: 设置ecx
寄存器的值为 1024,即页面表中的页数。"leal 4092(%%edx),%%edi\n\t"
: 计算页表的地址,从物理地址edx
的开始,每个页面表项大小为 4 字节,因此乘以 4,然后加上 4092(这可能是页面表的末尾,因为一个页面表包含 1024 个表项,每个表项 4 字节,总共 4 KB)。"rep ; stosl\n\t"
: 使用rep
指令重复执行stosl
,将eax
的内容存储到edi
指向的地址,重复次数为ecx
寄存器的值(1024),这将初始化页表项,将它们标记为已用。"movl %%edx,%%eax\n"
: 将页面的物理地址存储在返回值寄存器eax
中。"1:"
: 这是前面提到的标签,如果没有找到未使用的页面,则跳到这里。整体而言,这段代码的功能是从一组页面中找到一个未使用的页面,标记它为已用,然后返回该页面的物理地址。如果没有可用的页面,它将返回 0。此代码用于管理物理内存中的分页,通常在内存分配期间使用。
第 14 回 中断初始化 trap_init
在这个函数流程中,将中断号以及中断服务函数通过内联汇编方式绑定。
1 |
比如set_trap_gate(0, ÷_error)
设置了 0 号中断,对应的中断处理程序是 divide_error。
而中断号 17 ~ 48 号都被暂时批量设置为 reserverd 中断处理程序,之后会在 tty_init 中初始化 0x21 中断用来使键盘生效。
sti 同名汇编指令,表示允许中断。
system 与 trap 的区别仅仅在于设置的中断描述符的特权级不同,前者是 0(内核态),后者是3(用户态)。
第 15 回 块设备请求项初始化 blk_dev_init
在初始化 blk_dev 的过程中并不复杂,只是对同时块I/O请求支持的最大数量进行初始化。
1 | struct request { |
dev
: 表示设备编号,如果没有请求则设置为 -1。cmd
: 表示命令类型,可以是READ
或WRITE
。errors
: 表示请求期间遇到的错误次数。sector
: 指定 I/O 操作的起始扇区。nr_sectors
: 指定参与 I/O 操作的扇区数。buffer
: 指向 I/O 操作的数据缓冲区。waiting
: 指向等待 I/O 操作完成的任务,可以表示一个进程,表示是哪个进程发起的请求。bh
: 指向与请求关联的缓冲头。next
: 指向队列中的下一个请求。
这个结构体定义了当系统对硬盘I/O操作时的一些必要的变量,而 hb 与 next 是要基于后面的电梯算法使用。
request[32] 数组是块设备驱动程序与内存缓冲区的桥梁,通过它表示一个块设备读写操作要做的事。
第 16 回 控制台初始化 tty_init
1 | void tty_init(void) |
初始化包含两步,一个是串口设备初始化一个是对 console 控制台的初始化。
1 | void rs_init(void) |
- 设置中断门: 使用
set_intr_gate
函数为串口1和串口2设置中断门,分别为 0x24 和 0x23。中断门是中断处理程序的入口,这里分别设置了串口1和串口2的中断处理函数为rs1_interrupt
和rs2_interrupt
。 - 初始化 tty 队列: 调用
init
函数初始化 tty 表中索引为1和2的串口对应的读队列。tty_table[1].read_q.data
和tty_table[2].read_q.data
分别表示串口1和串口2的读队列。 - 屏蔽中断: 使用
outb
函数修改 8259A 芯片的中断屏蔽寄存器,将串口1和串口2的中断屏蔽位置0。这样就允许了串口1和串口2的中断。原来的值通过inb_p(0x21)
读取,然后使用& 0xE7
将第3位(从低到高数)清零。
1 | /* |
- 设置控制台基本参数: 设置了控制台的列数、每行的字节数、行数、起始页面和擦除字符。
- 判断显示类型: 根据
ORIG_VIDEO_MODE
的值判断当前的显示类型,是单色(monochrome)还是彩色(color)。单色显示和彩色显示的内存起始地址、端口寄存器和端口值都有所不同。从 0x900006 处获取,判断完成后就可以映射相应的内存区域。 - 显示类型描述: 用字符串描述当前显示的类型,并显示在屏幕的右上角。
- 滚动初始化: 初始化用于滚动的变量,包括屏幕起始地址、屏幕结束地址、顶部和底部。
- 定位光标、键盘中断初始化: 从 0x90000 处获取光标位置定位光标,设置键盘中断处理程序为
keyboard_interrupt
,并屏蔽 8259A 芯片上的键盘中断。 - 声音初始化: 通过 0x61 端口控制发声器。
根据显示类型的不同,在内存中有一块与显存相映射的区域,当向该区域内写入数据时就等同于写入显存中,就会以一定格式输出到控制台最后在屏幕上打印。
而这些常用的变量的定义早在第 5 回说过的以 0x90000 起始的空间处存放,如显示模式、光标位置、显示页面等等信息。
第 17 回 时间初始化 time_init
1 |
|
CMOS 为主板上的一块可读写的 RAM 芯片,这段代码通过对 CMOS 的寄存器进行读操作,将秒、分、时、日、月、年等信息读出,并通过BCD_TO_BIN
转化成二进制。
传入kernel_mktime
函数,将 1970 年 1 月 1 日 0 时起作为开机时间,并不断累加。
第 18 回 进程调度初始化 sched_init
1 | void sched_init(void) |
设置 TSS 和 LDT 描述符:
set_tss_desc
和set_ldt_desc
用于设置 TSS(Task State Segment)和 LDT(Local Descriptor Table)的描述符。TSS 存储任务的状态信息,而 LDT 存储局部描述符表的信息。init_task.task.tss
存储了任务 0(即内核任务)的 TSS 信息。init_task.task.ldt
存储了任务 0 的 LDT 信息。- 并将 task_stauct 这个结构的数组中的第一个元素赋上 init_task.init 这个具体值,作为未来进程 0 的初始信息。
初始化 task_struct[64] 结构体数组为 NULL。其中包含了类似进程的状态、优先级、对应的终端等等必要信息。
其中 LDT (局部描述符表)与先前的 GDT(全局描述符表)相对应,内核态的代码用的是 GDT 中的数据段和代码段,而各个进程用的是属于进程自己的 LDT。
TSS(任务状态段)用于保存和恢复进程的上下文,所谓上下文其实在对结构体查看以后就是各个寄存器在当前状态时的寄存器信息。
未来进程调度机制一建立起来,正在执行的代码会化身成进程 0 的代码。
初始化全局描述符表 GDT:
- GDT 存储了系统中所有任务的描述符信息。
- 通过循环初始化 TSS 和 LDT 描述符的后续部分,这些描述符对应任务 1 到任务
NR_TASKS - 1
。
清除 NT 标志位:
__asm__("pushfl ; andl $0xffffbfff,(%esp) ; popfl");
用于清除 EFLAGS 寄存器的 NT(Nested Task)标志位,确保不会在后续任务切换中产生问题。
加载 TSS 和 LDT:
ltr(0)
用于加载 TSS,lldt(0)
用于加载 LDT。
初始化 PIT(Programmable Interval Timer):
- 设置 PIT 工作在二进制计数、模式 3(square wave generator),并设定计数器初始值(LATCH)。
outb_p(0x36, 0x43)
用于设置 PIT 工作模式。outb_p(LATCH & 0xff, 0x40)
和outb(LATCH >> 8, 0x40)
分别用于设置计数器初值的低 8 位和高 8 位。
设置时钟中断处理函数:
set_intr_gate(0x20, &timer_interrupt)
用于设置时钟中断的中断门,指定了中断处理函数为timer_interrupt
。
开启定时器,持续地、以一定频率地向CPU发送中断信号。
屏蔽 IRQ0 中断:
outb(inb_p(0x21) & ~0x01, 0x21)
用于将 IRQ0 的中断屏蔽位清零,允许时钟中断。
设置系统调用中断处理函数:
set_system_gate(0x80, &system_call)
用于设置系统调用中断的中断门,指定了中断处理函数为system_call
。
用户态程序想要调用内核中提供的代码,需要基于 0x80 中断号提供的系统调用中断进行。
第 19 回 缓冲区初始化 buffer_init
1 | void buffer_init(long buffer_end) |
令人疑惑的 end 符号。
首先,这个 end 符号用来确定了内核模块数据段结尾的位置,而这之后的内存刚巧是可以用来操作的,于是就以此为 buffer 的头。
那既然代码中没有初始化这个符号,它是怎么来的呢?
end 是内核模块链接期间有链接程序(ld)设置的一个值,内核代码没有定义这个符号。当在链接生成 system 模块时,ld 程序的 digest_symbols() 函数会产生此符号。该函数主要用于对全局变量进行引用赋值,并且计算每个被链接文件的起始和大小,其中也设置了 end 的值,它等于 data_start + datasize + bss_size,也就是内核模块的末端。
struct buffer_head * h = start_buffer;
:定义一个指向struct buffer_head
结构的指针h
,并将其初始化为start_buffer
,start_buffer
是一个指向struct buffer_head
的全局指针,指向内核数据段的结尾。void * b;
:定义一个通用指针b
,用于指向分配的内存块。if (buffer_end == 1<<20)
:检查buffer_end
是否等于 1MB。- 如果是,将
b
初始化为指向地址640*1024
,即 640KB。这是因为在 1MB 的物理内存中,前 640KB 通常是给 DOS 保留的,而 Linux 内核从640KB
开始使用。 - 如果不是,将
b
初始化为buffer_end
。
- 如果是,将
while ( (b -= BLOCK_SIZE) >= ((void *) (h+1)) )
:循环,逐渐减小b
,直到它小于等于(h+1)
。这个循环用于为缓冲区中的每个块分配内存。h->b_dev = 0;
:将缓冲块的设备号初始化为 0。h->b_dirt = 0;
:将缓冲块的脏标志(表示是否被修改过)初始化为 0。h->b_count = 0;
:将缓冲块的引用计数初始化为 0。h->b_lock = 0;
:将缓冲块的锁定标志初始化为 0。h->b_uptodate = 0;
:将缓冲块的更新标志初始化为 0。h->b_wait = NULL;
:将缓冲块的等待队列初始化为 NULL。h->b_next = NULL;
:将缓冲块的下一个指针初始化为 NULL。h->b_prev = NULL;
:将缓冲块的前一个指针初始化为 NULL。h->b_data = (char *) b;
:将缓冲块的数据区指针初始化为b
。h->b_prev_free = h-1;
:将缓冲块的前一个空闲块指针初始化为前一个缓冲块。h->b_next_free = h+1;
:将缓冲块的下一个空闲块指针初始化为下一个缓冲块。h++;
:指向下一个缓冲块。NR_BUFFERS++;
:增加缓冲块数量的计数。
上述步骤会反复执行,直到
b
小于(h+1)
。h--;
:将h
指向最后一个初始化的缓冲块。free_list = start_buffer;
:将空闲缓冲块列表的头指针free_list
初始化为start_buffer
。free_list->b_prev_free = h;
:将空闲缓冲块列表的尾指针的前一个指针指向最后一个初始化的缓冲块。h->b_next_free = free_list;
:将最后一个初始化的缓冲块的下一个空闲块指针指向空闲缓冲块列表的头指针。for (i=0; i<NR_HASH; i++) hash_table[i] = NULL;
:将哈希表中的所有项初始化为 NULL。
这个函数的作用是初始化一系列缓冲块,这些缓冲块将被用于磁盘 I/O 操作,提高磁盘读写速率。
在计算机通过了下面这段代码。
1 | while ((b -= BLOCK_SIZE) >= ((void *) (h + 1))) { |
在内存中的 2MB 的缓冲区空间中就实现了上下各存在一个缓冲块 b 对应一个缓冲头 h 的布局,同时缓冲头的结构是双向链表,就实现了通过 free_list 开始遍历找到其余其他所有前后的缓冲头以及其对应的缓冲块。
所以,缓冲头就是具体缓冲块的管理结构,而 free_list 开头的双向链表又是缓冲头的管理结构。
当然,为了更方便的管理整个缓冲区,整个 buffer_init 代码的最后一部,是将一个 hash_table 全初始化为 NULL。为了弥补链式查找的速率问题,使用了哈希表的结构实现了O(1)的复杂度快速查找。
即哈希表中的元素存放的是一个 h 缓冲头的指针,先通过哈希函数计算哈希值,再解决哈希冲突的问题,是整个双向链表更加高效。
总的来说,缓冲区作为用户进程的内存和硬盘之间的桥梁就初始化完毕了。
第 20 回 硬盘初始化 hd_init
1 | void hd_init(void) |
blk_dev[MAJOR_NR].request_fn = DEVICE_REQUEST;
:blk_dev
是一个数组,用于存储块设备的信息。MAJOR_NR
是主设备号,表示设备的类型,这里可能是硬盘的主设备号。request_fn
是块设备的请求函数,这里设置为DEVICE_REQUEST
,表明在块设备上执行请求时会调用DEVICE_REQUEST
函数。
set_intr_gate(0x2E,&hd_interrupt);
:set_intr_gate
是设置中断门的宏,用于设置中断描述符表 (IDT) 中的中断门。0x2E
是硬盘的中断号,hd_interrupt
是中断服务例程。- 这行代码将硬盘的中断服务例程
hd_interrupt
注册到中断描述符表,以便在硬盘中断发生时执行相应的处理。
outb_p(inb_p(0x21)&0xfb,0x21);
和outb(inb_p(0xA1)&0xbf,0xA1);
:- 这两行代码用于屏蔽(禁用)硬盘控制器的中断。具体来说:
0x21
是主片 8259A 中断控制器的端口,0xA1
是从片 8259A 中断控制器的端口。inb_p
用于读取端口的值,outb
用于向端口写入值。0xfb
和0xbf
分别是用于屏蔽 8259A 中断控制器上的硬盘中断的位。通过将相应的位设置为 0,禁用了硬盘中断。
- 这两行代码用于屏蔽(禁用)硬盘控制器的中断。具体来说:
总体来说,这段代码的作用是初始化硬盘,并设置硬盘中断的处理函数。在初始化过程中,还屏蔽了硬盘中断,以免在初始化期间发生不必要的中断。
参考
什么是LBA块地址?
LBA(Logical Block Addressing)块地址是一种磁盘寻址方法,用于在硬盘或固态硬盘上定位数据块的位置。在 LBA 寻址中,整个磁盘被划分为连续编号的逻辑块,每个逻辑块包含一定数量的扇区。扇区是磁盘上最小的可寻址数据单元。
LBA 是一种线性寻址方式,通过一个简单的整数(LBA 地址)来标识磁盘上的特定数据块。这个整数对应于磁盘上的逻辑块号。使用 LBA 可以简化磁盘寻址,不再需要考虑磁头、柱面等传统的 CHS(Cylinder-Head-Sector)寻址方式,因此更容易管理和实现。
具体来说,LBA 地址是一个非负整数,表示从磁盘起始位置开始的逻辑块号。例如,LBA 地址为0表示磁盘上的第一个逻辑块,LBA 地址为1表示磁盘上的第二个逻辑块,以此类推。在大多数现代计算机系统中,LBA 是主要的磁盘寻址方式,因为它更灵活、简单,并且支持更大容量的磁盘。
18回 BCD 码与 BIN 码的区别?
BIN码就是二进制编码。比如十进制数的11,用BIN码表示就是1011;左边的1表示十制的8,左边第三位的1表示十制的2,左边第四位的1表示十制的1, (即 8+2+1=11)
BCD码就是用四位二进制数表示一位十进制数的编码,比如十进制数11用BCE码表示就是00010001;前面的0001表示十进制的十位的1,后面买的0001表示十进制的个位的1.
19回 为什么可以使用h++对下一个结构体进行访问,h++会将结构体的大小加上么
在C语言中,对指针执行
++
操作时,指针会自动增加相应数据类型的大小。这是因为在C中,指针的移动是按照其指向的数据类型的大小进行的。在这段代码中,
h
是一个指向struct buffer_head
结构体的指针。当执行h++
时,h
会自动增加sizeof(struct buffer_head)
的大小,使其指向下一个struct buffer_head
。这种行为是由C语言的语法规定的,确保指针的操作是类型安全的。这样,即使结构体中包含了不同类型的成员,指针的增加操作也会正确地跨越整个结构体的大小。
19回 什么是LRU算法
LRU(Least Recently Used)算法是一种缓存淘汰策略,用于管理缓存中的数据项。该算法基于这样的思想:最近最久未使用的数据项在未来也更有可能不被使用,因此优先淘汰这些数据项,留下近期被使用的数据。
LRU算法的核心思想是维护一个访问顺序链表或类似的数据结构,将最近访问的数据项移动到链表的前部,而最久未使用的数据项则位于链表的末尾。当需要淘汰数据项时,选择链表末尾的数据项进行淘汰。
具体实现LRU算法的数据结构可以是一个双向链表,也可以是使用数组和哈希表的组合。当一个数据项被访问时,将其移动到链表的前部。当需要淘汰数据项时,选择链表末尾的数据项进行移除。这样就能够保持链表的顺序反映了数据项的访问顺序。
LRU算法的应用范围广泛,特别是在缓存系统中,用于有效管理缓存的有限空间,提高缓存命中率。