Linux-Kernel-Learning
Linux-Kernel-Learning copied to clipboard
hangc0276
## 从开机加电到执行main函数之前的过程  1.启动BIOS，准备实模式下中断向量表和中断服务程序 - 在按下电源按钮的瞬间，CPU硬件逻辑强制将CS：IP设置为0xFFFF:0x0000,指向内存地址的0xFFFF0位置，此位置属于BIOS的地址范围。关于硬件如何指向BIOS区，这是一个纯硬件动作，在RAM实地址空间中，属于BIOS地址空间部分为空，硬件只要见到CPU发出的地址属于BIOS地址范围，直接从硬件层次将访问重定向到BIOS的ROM区中。这也就是为什么RAM中存在空洞的原因。 - BIOS程序在内存最开始的位置（0x00000）用1KB的内存空间（0x00000~0x003FF）构建中断向量表，并在紧挨着它的位置用256个字节的内存空间构建BIOS数据区（0x00400~0x004FF）,大约在56KB以后的位置(0x0E2CE)加载了8KB左右的与中断向量表相对应的若干中断服务程序。 2.加载操作系统内核程序，并为保护模式做准备 - 加载操作系统的过程分为三步 - 由BIOS中断int 0x19把第一扇区bootsect的内容加载到内存 - 在bootsect的指挥下，把其后的四个扇区的内容加载至内存 - 在bootsect的指挥下，把随后的240个扇区内容加载至内存 - 加载第一部分代码---引导程序bootsect - int 0x19对应的中断服务程序的入口地址为0x0E6F2，这个中断服务程序的作用是将软盘的第一个扇区的程序(512B)加载到内存的指定位置，该服务程序是BIOS事先设计好的，与Linux操作系统无关。该服务程序将软驱0号磁头对应盘面的0磁道1扇区的内容拷贝至内存0x07C00处。该扇区的作用就是Linux操作系统的引导程序bootsect，其作用就是摆脱BIOS的限制，陆续将软盘中的操作系统程序载入到内存中。 - 加载第二部分代码---setup - bootsect的作用就是把第二批和第三批程序陆续加载到内存的适当位置。为了完成之一目标，bootsect首先要做的工作就是规划内存。 ``` SETUPLEN =...
在访问内核地址空间时，缺页异常可能被各种条件出发，如下所述： - 内核本身的程序设计错误导致访问不正确的地址，这个在稳定版本中永远不会发生，在开发版本中偶尔会发生 - 内核通过用户空间传递的参数访问了无效地址 - 访问使用vmalloc分配的区域，触发缺页异常 前两种情况是真正的错误，内核必须使用最后的手段---异常修正(exception fixup)机制来进行处理 vmalloc的情况是导致缺页异常的合理情况，必须加以校正。直至对应的缺页异常发生之前，vmalloc区域中的修改都不会传输到进程的页表中。因此在对vmalloc异常进行处理时，必须从主页表复制适当的访问权限信息到进程的页表中。 对于用户态发生的缺页异常，内核将使用按需调页机制，自动并透明地返回一个物理内存页；如果访问发生在内核态，则必须使用不同的手段进行校正。每次发生缺页异常时，将输出异常的原因和当前执行代码的地址。这使得内核可以编译一个列表，列出所有可能执行未授权内存访问操作处理(异常处理)的代码块。这就是"异常表"。 ``` struct exception_table_entry { unsigned long insn, fixup; }; ``` **insn**: 指定了内核在虚拟地址空间发生异常的位置 **fixup**：指定了进行异常处理代码的地址 fixup_exception用于搜索异常表： ``` int fixup_exception(struct pt_regs *regs)...
**_Motivation：**_有两种方法来满足内存分配请求： - 当有足够的空闲内存可用时，请求会被立刻满足 - 否则，内核会回收一些内存，并将发出请求的内核控制路径阻塞，直到有内存被释放 **但是**当请求内存时，一些内核控制路径不能被阻塞。比如在处理中断或执行临界区的代码时的原子请求。原子请求从来不会被阻塞：如果没有足够的空闲页，则仅仅是分配失败而已。 尽管内核无法保证一个原子内存分配请求绝不失败，但是内核会采取一些措施尽量减少这种不幸事件的发生。为此，内核为原子内存分配请求引入了_保留页框池_，保留页框池只在内存不足的时候才使用（具体的使用方式请参见`__alloc_pages_internel`中的`restart`段的分析）。 保留内存的数量（以KB为单位）存放在min_free_kbytes变量中。它的初始值在内核初始化时设置，并取决于直接映射到内核线性地址空间的第4个GB的物理内存的数量---也就是说，取决于包含在ZONE_DMA和ZONE_NORMAL内存管理区内的页框数目： ``` 保留池的大小 = [sqrt(16*直接映射内存)]（KB） (下取整) ``` 但是：128
进程复制的三个机制`fork`、`vfork`和`clone`最终都是调用`do_fork`来实现子进程的产生的，不同的产生方式通过传递给do_fork的不同参数来控制。其代码执行流程如下： 代码： ``` if (unlikely(clone_flags & CLONE_STOPPED)) { static int __read_mostly count = 100; if (count > 0 && printk_ratelimit()) { char comm[TASK_COMM_LEN]; count--; printk(KERN_INFO "fork(): process `%s' used deprecated...
对内存的管理涉及两个部分： - 对物理内存的管理 - 对虚拟内存的管理 _对物理内存的管理_ 是指对“RAM的管理”，_对虚拟内存的管理_ 是指对进程地址空间的管理，它们两者通过page fault(缺页处理)联系起来。在RAM管理部分，主要包括页框管理和内存区管理；内存管理包括内存区管理、内存映射、伙伴系统、slab和内存池等部分。 对于i386这种32位的处理器结构，Linux采用4KB页框大小作为标准的内存分配单元。内核必须记录每一个页框的当前状态，如：区分哪些页框包含的是属于进程的页，而哪些页框包含的是内核代码或内核数据。内核还必须确定动态内存中的页框是否空闲，如果动态内存的页框中不包含有用数据，则该页框是空闲的。在一下情况下页框是不空闲的：包含用户态进程的数据、某个软件高速缓存的数据、动态分配内存数据结构、设备驱动程序缓冲数据、内核模块的代码等。 为了对页框的管理，内核引入了一下两个的数据结构： ``` page：结构体类型定义，是页框描述符 mem_map：页框描述符数组，用于存放所有的页框描述符 ``` 数据结构布局图如下：  内核必须记录每个页框的当前状态，保存在**page页描述符**结构中，该结构包含两个重要的数据成员 ``` unsigned long flags ; atomic_t _count ; ``` - _count:页的引用计数，page_count（）返回_count+1之后的数值，就是该页使用者的数目。_count>=0的时候，该页非空闲。 -...
**Motivation**：当内核被解压到线性地址0x100000后，为了继续启动内核，即启动内核的第一个swapper进程，内核需要建立一张临时页表供其使用。 当内核从16位的实模式进入保护模式（通过在汇编代码中的setup函数中设置linux的cr0寄存器的PE位），内核要创建一个有限的地址空间，容纳内核的代码段、数据段、初始页表和用于存放动态数据结构的128KB大小的空间。程序设计者假定，内核使用的代码段、数据段、临时页表和128KB的内存范围可以全部存放到RAM的前8MB的空间内。于是我们需要做的工作就是建立一个页表映射使得可以对内存的前8MB的物理地址进行寻址。 进程的线性地址空间可分为两部分： 0x00000000~0xbfffffff (0~3G),无论进程运行于用户态还是内核态都可以访问的地址空间 0xc0000000~0xffffffff (3G~4G),只有处于内核态的进程才能访问该地址空间。 为了保证在实模式和保护模式下，进程都可以对这8MB的空间进行寻址，内核必须建立两个映射。将0x00000000~0x007fffff的线性地址和0xc0000000~0xc07fffff的线性地址都映射到0x00000000~的物理地址空间中。此时便可以通过与物理地址相同的线性地址或是通过从0xc0000000开始的8MB线性地址对RAM的前8MB进行寻址。 **建立内核临时页表** 采用二级页表的形式建立临时映射。由于要映射8MB的内核空间，一个页表有1024项，每一项页表对应一个4KB的页，8MB=2_1024_4KB，故需要两个全局页目录项和两张页表。 **建立页全局目录项** 一张页全局目录表有1024项，但我们只需要寻址8MB的地址空间，所以只需要2个页全局目录项即可。由于我们要同时保证进程处于用户空间和内核空间下都能对这8MB的内存空间进行寻址，所有我们需要4个页全局目录项分别寻址8MB的用户空间和8MB的内核空间。 _要建立页全局目录表，首先要知道页全局目录表存放的物理地址_，其中变量`swapper_pg_dir`存放了页全局目录的线性地址。我们可以通过swapper_pg_dir - __PAGE_OFFSET计算可以获得的swapper_pg_dir的物理地址（其中__PAGE_OFFSET = 0xc0000000是内核线性空间的起始地址） 知道了临时页全局目录的地址之后，下面便可以初始化临时页全局目录： ``` ENTRY(swapper_pg_dir) .fill 1024,4,0 ``` 这两行汇编代码执行了页全局目录表的初始化，它的意思是：从swapper_pg_dir开始，填充1024项，每一项为4字节，值为0，正好是4KB的页面 **_下面要对页全局目录进一步初始化，从而保证对页表的映射**_ 为了保证进程处于用户态和内核态下都能对8MB的物理地址进行寻址，内核需要填充全局页目录表(swapper_pg_dir)的第0、1、0x300(十进制768)、0x301(十进制769)(768和769是通过计算内核线性地址空间对应的页目录偏移量获得的，具体的计算方法请参见补充内容)项。前两项是给用户空间线性地址映射，后两项是给内核空间线性地址映射。内核会将swapper_gp_dir的第0项和第768项字段设置为pg0的物理地址(pg0中存放第一张页表的地址),第1项和第769项字段设置为pg1的物理地址(pg0+4K)。  **页表的建立** 要映射8MB的物理地址，8MB =...
## 了解Linux的锁与同步、原子加(atomic_add) 因为需要效率更高的互斥，linux中的atomic_add()可以实现这个需求。没有接触过内核，现在贴一些相关内容，有空看下。 > http://linux.chinaunix.net/bbs/thread-917343-1-1.html 怎么在用户态下调用atomic_add()。 > http://www.linuxforum.net/index.php 一个不错的linux论坛 > http://www.linuxforum.net/forum/showflat.php?Cat=&Board=linuxK&Number=660405&page=&view=&sb=&o=&vc=1 > http://www.linuxforum.net/forum/showthreaded.php?Cat=&Board=linuxK&Number=659645&page=&view=&sb=&o= > （下文转自：http://timyang.net/programming/linux-synchronization-lock/#postcomment） ### 了解Linux的锁与同步 上周看了Linux的进程与线程，对操作系统的底层有了更进一步的一些了解。我同时用Linux内核设计与实现和Solaris内核结构两本书对比着看，这样更容易产生对比和引发思考。现代操作系统很多思路都是相同的，比如抢占式的多线程及内核、虚拟内存管理等方面。但另外一方面还是有很多差异。在了解锁和同步之前，原子操作是所有一切底层实现的基础。 ### 原子操作Atomic 通常操作系统和硬件都提供特性，可以对一个字节进行原子操作的的读写，并且通常在此基础上来实现更高级的锁特性。 - atomic_t结构 原子操作通常针对int或bit类型的数据，但是Linux并不能直接对int进行原子操作，而只能通过atomic_t的数据结构来进行。目前了解到的原因有两个。 一是在老的Linux版本，atomic_t实际只有24位长，低8位用来做锁，如下图所示。这是由于Linux是一个跨平台的实现，可以运行在多种 CPU上，有些类型的CPU比如SPARC并没有原生的atomic指令支持，所以只能在32位int使用8位来做同步锁，避免多个线程同时访问。(最新版SPARC实现已经突破此限制)  另外一个原因是避免atomic_t传递到程序其他地方进行操作修改等。强制使用atomic_t，则避免被不恰当的误用。 ``` atomic_t...
### 一、 引言 --- 众所周知，为了保护共享数据,需要一些同步机制,如自旋锁(spinlock)，读写锁(rwlock)，它们使用起来非常简单,而且是一种很有效的同步机制，在UNIX系统和Linux系统中得到了广泛的使用。但是随着计算机硬件的快速发展，获得这种锁的开销相对于CPU的速度在成倍地增加，原因很简单，CPU的速度与访问内存的速度差距越来越大，而这种锁使用了原子操作指令，它需要原子地访问内存，也就说获得锁的开销与访存速度相关，另外在大部分非x86架构上获取锁使用了内存栅(Memory Barrier)，这会导致处理器流水线停滞或刷新，因此它的开销相对于CPU速度而言就越来越大。表1数据证明了这一点。  表1是在700MHz的奔腾III机器上的基本操作的开销，在该机器上一个时钟周期能够执行两条整数指令。在1.8GHz的奔腾4机器上, 原子加1指令的开销要比700MHz的奔腾III机器慢75纳秒(ns)，尽管CPU速度快两倍多。 这种锁机制的另一个问题在于其可扩展性，在多处理器系统上，可扩展性非常重要，否则根本无法发挥其性能。图1表明了Linux上各种锁的扩展性。 图 1 Linux的4种锁机制的扩展性  注：refcnt表示自旋锁与引用记数一起使用。 读写锁rwlock在两个CPU的情况下性能反倒比一个CPU的差，在四个CPU的情况下，refcnt的性能要高于rwlock，refcnt大约是理论性能的45%，而rwlock是理论性能的39%,自旋缩spinlock的性能明显好于refcnt和rwlock，但它也只达到了理性性能的57%，brlock（Big Reader Lock）性能可以线性扩展。Brlock是由Redhat的Ingo Molnar实现的一个高性能的rwlock，它适用于读特多而写特少的情况，读者获得brlock的开销很低，但写者获得锁的开销非常大，而且它只预定义了几个锁，用户无法随便定义并使用这种锁，它也需要为每个CPU定义一个锁状态数组，因此这种锁并没有被作为rwlock的替代方案广泛使用，只是在一些特别的地方使用到。 正是在这种背景下，一个高性能的锁机制RCU呼之欲出，它克服了以上锁的缺点，具有很好的扩展性，但是这种锁机制的使用范围比较窄，它只适用于读多写少的情况，如网络路由表的查询更新、设备状态表的维护、数据结构的延迟释放以及多径I/O设备的维护等。 RCU并不是新的锁机制，它只是对Linux内核而言是新的。早在二十世纪八十年代就有了这种机制，而且在生产系 统中使用了这种机制，但这种早期的实现并不太好，在二十世纪九十年代出现了一个比较高效的实现，而在linux中是在开发内核2.5.43中引入该技术的并正式包含在2.6内核中。 ### 二、RCU的原理 --- RCU(Read-Copy Update)，顾名思义就是读-拷贝修改，它是基于其原理命名的。对于被RCU保护的共享数据结构，读者不需要获得任何锁就可以访问它，但写者在访问它时首先拷贝一个副本，然后对副本进行修改，最后使用一个回调（callback）机制在适当的时机把指向原来数据的指针重新指向新的被修改的数据。这个时机就是所有引用该数据的CPU都退出对共享数据的操作。 因此RCU实际上是一种改进的rwlock，读者几乎没有什么同步开销，它不需要锁，不使用原子指令，而且在除alpha的所有架构上也不需要内存栅（Memory Barrier），因此不会导致锁竞争，内存延迟以及流水线停滞。不需要锁也使得使用更容易，因为死锁问题就不需要考虑了。写者的同步开销比较大，它需要延迟数据结构的释放，复制被修改的数据结构，它也必须使用某种锁机制同步并行的其它写者的修改操作。读者必须提供一个信号给写者以便写者能够确定数据可以被安全地释放或修改的时机。有一个专门的垃圾收集器来探测读者的信号，一旦所有的读者都已经发送信号告知它们都不在使用被RCU保护的数据结构，垃圾收集器就调用回调函数完成最后的数据释放或修改操作。 RCU与rwlock的不同之处是：它既允许多个读者同时访问被保护的数据，又允许多个读者和多个写者同时访问被保护的数据（注意：是否可以有多个写者并行访问取决于写者之间使用的同步机制），读者没有任何同步开销，而写者的同步开销则取决于使用的写者间同步机制。但RCU不能替代rwlock，因为如果写比较多时，对读者的性能提高不能弥补写者导致的损失。...
### 一、 引言  在现代操作系统里，同一时间可能有多个内核执行流在执行，因此内核其实象多进程多线程编程一样也需要一些同步机制来同步各执行单元对共享数据的访问。尤其是在多处理器系统上，更需要一些同步机制来同步不同处理器上的执行单元对共享的数据的访问。在主流的Linux内核中包含了几乎所有现代的操作系统具有的同步机制，这些同步机制包括：原子操作、信号量（semaphore）、读写信号量（rw_semaphore）、spinlock、BKL(Big Kernel Lock)、rwlock、brlock（只包含在2.4内核中）、RCU（只包含在2.6内核中）和seqlock（只包含在2.6内核中）。 本文的下面各章节将详细讲述每一种同步机制的原理、用途、API以及典型应用示例。 ### 二、原子操作  所谓原子操作，就是该操作绝不会在执行完毕前被任何其他任务或事件打断，也就说，它的最小的执行单位，不可能有比它更小的执行单位，因此这里的原子实际是使用了物理学里的物质微粒的概念。 原子操作需要硬件的支持，因此是架构相关的，其API和原子类型的定义都定义在内核源码树的include/asm/atomic.h文件中，它们都使用汇编语言实现，因为C语言并不能实现这样的操作。 原子操作主要用于实现资源计数，很多引用计数(refcnt)就是通过原子操作实现的。 原子类型定义如下： ``` typedef struct { volatile int counter; } atomic_t; volatile修饰字段告诉gcc不要对该类型的数据做优化处理，对它的访问都是对内存的访问，而不是对寄存器的访问。 原子操作API包括： atomic_read(atomic_t * v); 该函数对原子类型的变量进行原子读操作，它返回原子类型的变量v的值。 atomic_set(atomic_t *...
  前一段时间一直在Ubuntu 12.04下编译Linux kernel 2.6.24,但一直没 成功。其原因是高版本的Ubuntu自带的gcc编译器的版本比较高，一般在4.6以上。但2.6.24版本的内核相对于现在来说比较老，高版本的gcc对一些比较老的C语言和Make文件特性支持的不是很好，因此在编译的时候经常出错，解决这个问题的有两种方案，其一，重新安装一个比较低版本的gcc编译器，经测试，4.5.1版本的gcc能够编译成功2.6.26版本的内核。其二，观察编译内核过程中的错误信息，根据相关错误信息修改相应的.c文件盒Makefile文件，从而达到消除错误的目的，这个过程比较繁琐，工作量很大，而且特别耗时。 ### 出现的各种乱七八糟的问题：   我使用的是Fedora 14操作系统来编译2.6.26版本的内核，下面简述编译过程中遇到的相关问题及其解决方案和相关的编译步骤： - 问题1：编译过程中出现如下错误代码： ``` c It fails with the following error: Makefile:1550: *** mixed implicit and normal rules. Stop. make[1]:...