Browsed by
分类:计算机系统原理

[Linux 0.11] Draft 6 IA32架构下多任务的硬件支持

[Linux 0.11] Draft 6 IA32架构下多任务的硬件支持

Overview

支持多任务的硬件结构为 Task Register (TR) Task State Segment (TSS), LDT 以及 Task Gate。而最核心的,存储任务上下文信息的就是 Task State Segment, 下面对其进行详细的说明

TSS基本数据结构

  • GDT, LDT
  • TSS(Task State Segment)  has its own descriptor called TSS Descriptor
  • Structure of 32 bit TSS, store the context and link to previous task, and 3 different privileged Stack

下面对一些比较关键的部分进行介绍

  • Previous Task Link: 存储的是上一个任务的选择符
  • LDT Segment Selector: 存储的是这个Task使用的LDT
  • I/O Map Base Address: I/O Map的基地址(要对 I/O Map 是什么进行进一步的解读: I/O Map 包含一个权限Map和一个Interrupt redirect Map)

TSS 描述符的一些说明

  • TSS Descriptor 用于描述 Task State Segment 的描述符,当选择符的TI Flag被置位的时候(即指向当前LDT)不可以访问TSS, 这种情况下,使用 CALL, JMP 会引发GP#, 使用IRET 会引发#TS(Invalid TSS Exception), TSS Descriptor只能被放在 GDT 中,不可以放在 LDT IDT 中
  • 下面是TSS描述符的结构

 Type 有两种 1001 1011, 前者表示该TSSD对应的Task处于 inactive 状态下,后者表示该 TSSD 对应的Task正处于Busy状态下

 

  • 每一个Task只能有一个TSS Descriptor对应
  • Task Gate Descriptor  做切换的时候不需要检查 CPL

 

任务切换过程

任务切换发生在下面几种情况下:

  • 当前运行的任务 JMP / CALL 了GDT中的一个TSS , 当 CALL / JMP 以 FAR 模式被调用的时候,如果 Segement Selector 指向的选择符是一个 TSSD, 那么就会发生 Task Switch, 忽略掉 CALL / JMP 的 offset。
  • 同样的,如果调用 JMP / CALL 而且 Selector 为 GDT / LDT 中的一个 Task Gate Descriptor(任务门描述符)也会发生 Task Switch
  • 发生中断/异常,且中断向量指向一个Task Gate Descriptor
  • IRET 指令被调用且 EFLAGS 寄存器的 NT Flag 被置位

 

任务切换过程比较繁琐,这里简单说明其过程

 

  1. 获取 TSS 的 Segment Selector, 如果是 JMP / CALL 则是直接给出的, 或者是通过中断指向的 Task Gate Descriptor 给出,如果是 IRET 指令,则查看当前 TSS 的 Previous Task Link (见上图 TSS结构图)获得 Selector
  2. 检查特权级别, 如果是 CALL / JMP 则需要检查特权级别,中断 和 IRET 不需要检查, INT n 指令引发的中断调用,会检查特权级别
  3. 检查 TSS 的合法性,以及其他必要检查
  4. 清除或者设置相应的标志位
  5. 将当前(old)任务状态保存到当前的TSS内,
  6. 如果任务切换不是因为 IRET 引起的,则将新任务的 TSSD 的 Busy 位置位
  7. 装载新的 Task Descriptor(Selector) 到 Task Register
  8. 将新的 Task State Segment(TSS) 中的上下文装入通用寄存器,段寄存器, EIP EFLAGS 等寄存器(见上图 TSS结构)
  9. 上下文(context)已经设置好了,开始执行新的任务(此时的EIP, CS等 寄存器已经是该TSS中给定的寄存器了,之前的任务完全转移走了)

下一篇文章会对Linux0.11中如何实现任务切换进行介绍

[Linux 0.11] Draft 2 80386 System Architecture

[Linux 0.11] Draft 2 80386 System Architecture

此文对 Intel 80386 的系统架构进行一定程度的说明

80386 在系统层面支持下面的功能

  • 保护
  • 内存管理
  • 多任务
  • IO
  • 异常和中断
  • 初始化
  • 协处理器,多处理技术
  • 调试功能

上述均通过系统寄存器以及指令来支持,下面会对这些进行介绍

系统寄存器(Registers)

系统寄存器分为如下几类

  • EFLAGS
  • 内存管理寄存器
  • 控制寄存器 (Control Registers)
  • 调试寄存器 (Debug Registers)
  • 测试寄存器 (Test Registers)

下面对每一类寄存器进行说明

System FLAGS

EFLAGS 中的 System FLAG 可以控制如 IO, 可屏蔽中断,任务切换,调试等功能。

  • IF: 用来控制系统是否接受(可屏蔽的)外部中断请求 IF = 0 为屏蔽
  • NT: 此位用于控制 Chain interrupted 以及 called tasks, 该位会影响 IRET 指令的操作方式
  • RF: debug 有关的 flag
  • TF: debug 有关的 flag,将处理器设置为单步执行模式,在这个模式下,所有的指令CPU都会产生一个异常,可以在每一个指令处停下来进行调试
  • VM: 用于进入 Virtual 8086 Mode 的 flag 这里不做解释

内存管理寄存器

与内存分段管理相关的寄存器,如全局描述符表,中断描述符表,也就是 GDT, LDT, IDT 和 Task 的描述信息存储用的寄存器

  • GDTR
  • LDTR
  • IDTR
  • TR   上述三个不用介绍,这个为 Task Register,用于指向当前执行的 Task 的相关元信息

控制寄存器

控制寄存器有 CR0, CR1, CR2, CR3 其中 CR1  留作 Intel 以后使用,在80386中没有实际用途。其余三个都可以通过,而且仅可以通过 MOV 指令来进行操作,将其从通用寄存器中装入,或者存入通用寄存器

  • CR0 对整个系统控制,不针对某一个任务,CR0 可以控制协处理器相关的操作(EM, ET, MP) 以及 开启保护模式 (PE) 开启分页模式 (PG) 获取任务切换状态(TS)
  • CR2 用来处理缺页异常,CR2 中存储的是触发缺页异常的线性地址的值
  • CR3 用来指定当前任务中页表所在的地址

CR2, CR3 均是分页相关的寄存器

调试寄存器

暂略

测试寄存器

单独为了 TLB 提供支持的寄存器,TLB (Translation Lookaside Buffer) 又称内存快表

—–

下面再对通用寄存器进行说明

通用寄存器

通用寄存器分为三类

  • 通用寄存器 General Register
  • 段寄存器 Segment Register
  • 状态寄存器 & 指令寄存器

通用寄存器

  • 可以做 32bit, 16bit, 8bit的寄存器为 EAX EBX ECX EDX
  • 可以做 32bit,16bit的寄存器 EBP ESI EDI ESP

分段寄存器

  • CS Code Segment 当前代码段的地址
  • SS Stack Segment 类似上文
  • DS Data Segment
  • ES  FS GS  同样为 Data Segment

状态和指令寄存器

  • EFLAGS 存储着状态
  • EIP 为指令寄存器,指向要取的指令

Stack 操作

Stack 操作使用的寄存器为 SS, ESP, EBP 分别介绍他们的作用

这里先来介绍一下 80386 CPU 对Stack的实现

Stack 在内存中实现, 指定不同的 Stack 的时候依靠切换 SS 寄存器 ( SS 寄存器指向内存段)

ESP 指针指向当前栈顶

EBP 指向该栈栈底,EBP 用来引用栈内的参数如 EBP + 4 这种

 

 

[DFS #0] HDFS论文解读

[DFS #0] HDFS论文解读

参考论文: The Hadoop Distributed File System

分布式文件系统HDFS作为HBase的下层服务,以及众多存储服务的支持项目,已经被广泛使用,下面通过解读上述论文来记录并介绍一下HDFS的架构,以及功能,还有设计

整体架构 Overview

如图所示

 

document_2016-12-17_23-04-40-1

 

每一个HDFS集群由一个NameNode,多个DataNode,以及BackupNode, CheckpointNode组成,上图中的三角形为使用HDFS的客户端,客户端和DataNode之间的线表示客户端到DataNode的物理距离,对于这个架构,有下面几点要说的

  • 一个集群的NameNode只有一个,客户端想要使用这个HDFS的时候,一定是先和NameNode进行交流,获得需要的DataNode信息之后,才能和DataNode进行通信
  • 因为NameNode只有一个,所以NameNode如果出现单点故障可就不好玩惹,而且对于存储这种要求数据一致性很高的系统,也不能容忍NameNode出故障系统就瘫痪这种情况,因而使用CheckpointNode和BackupNode对NameNode进行备份,他们的区别和备份方式下文会详细说
  • NameNode不会主动去和DataNode通信,他们之间的通信是这样的: DataNode每隔一定时间发送heartbeat到NameNode(默认3s)(通知NameNode他还活着可以干活=w=(划掉 ,然后NameNode在这个时候会将要发送到DataNode的指令通过Response的形式发送到DataNode
  • Client对数据的操作精简来看,无非是读写两种,当Client想要读取HDFS的数据的时候,首先Client先去询问NameNode,哪些DataNode有他要的数据,并且选择距离他最近的DataNode,然后Client直接连接距离最近的DataNode并获取数据 e.g: 如上图的ClientA想要获取一个数据,且数据在DataNode A B C内都有存放,那么ClientA首先要和NameNode进行通信,获得DataNode列表(ordered by distance to the client)然后选择距离它最近的DataNode B进行通信获取数据
  • 当Client想要向一个文件写入数据的时候(无论文件存不存在),其他的Client会无法对此文件进行写入操作(以此来保证文件不会因为同时写而corrupt data)写入完毕之后,会将Block进行Replica复制到不同的DataNode上(默认为复制3份),具体会在下面介绍

 

模块 & 术语

NameNode

HDFS Namespace ,是存储着所有DataNode以及每一个DataNode上的文件的元信息的一个目录结构,NameNode通过inode的方式来表示每一个文件和文件夹。Namespace 就可以理解为Linux的目录树的inode list,每一个inode指向一个datablock,datablock存在datanode上 HDFS将整个Namespace放在RAM内,完整的文件系统信息(包含inode信息,以及每一个inode对应的Datablock list 元信息)称为Image, Image持久存储在NameNode本地存储里,称为一个Checkpoint, NameNode同时维护了数据操作的日志journal

DataNode

显然,这就是数据真正存放的地方,每一个Datablock由两个文件组成,该Block的数据,和该Block的[checksum,创建时间]信息组成的元数据

如下图

document_2016-12-18_01-35-54

一个占3个Block的文件存放在DataNode里的情况简图,该文件有三个block,每一个block的信息含有Data & MetaData,三个Block组成了整个文件file1, 然后在NameNode的某一个inode存储着信息对应着文件名file1,block数3,物理位置在该DataNode上

DataNode的Startup

 

  • 当DataNode Startup时,会和NameNode进行handshake,进行namespaceID(每一个HDFS都有一个唯一的NamespaceID,在创建HDFS的时候就确定了)&version的认证,二者必须均与NameNode完全一致,如果不一致的话,该DataNode就会停止工作。保证了不会因为错误的NameNode或者软件版本不兼容而导致数据出问题,
  • 如果这个DataNode没有保存任何Namespace信息,说明这是一个新的DataNode,没有任何Block数据,因而允许加入此HDFS cluster。
  • 当DataNode握手成功之后,会register自己到该NameNode,如果为第一次加入该NameNode,则会被NameNode分配一个唯一的StorageID,并且永远不会改变,DataNode会将此ID持久存在自己的storage中,这个StorageID保证了就算IP变动或者端口变动,NameNode仍然可以识别该DataNode的身份

DataNode与NameNode的通信

  • Block Report: Block Report是DataNode用于通知NameNode自己所持有的Block的信息(如blockid,block大小,generation stamp)的一种数据,因为这个数据是会随时改变的,所以需要定期发送Block Report给NameNode,使得NameNode能得到整个Block分布的信息。当DataNode注册到NameNode时,会立即发送一个Block Report,之后会每隔一段时间(1h)发送一次BlockReport
  • HeartBeat:  DataNode通过定期的心跳与NameNode进行通信,使NameNode确认DataNode存活,并且同时carry其他信息,如存储可用量,目前正在传输的数据量等信息,用于NameNode进行负载均衡。 NameNode则在收到DataNode心跳,对DataNode进行Response的时候进行通信,可以发送的指令有:
    • 将自己持有的数据块复制到其他DataNode
    • 移除该DataNode上的数据块
    • 重新注册、或者停止该DataNode
    • 使DataNode立即发送一个Block Report

Block Scanner

  • 每一个DataNode都有一个BlockScanner,周期性地对Block的完整性进行认证
  • 当Block Corrupt的时候,Scanner会通知NameNode该Block Corrupt了
  • Verification Time存储在日志内,对Block的扫描顺序是按照VerificationTime早的先扫描进行排序的(待定)

HDFS Client

Client的作用就是用来Access HDFS的文件信息的,功能即为文件系统的基本操作

  • 读: 如上文所说,读距离Client最近的DataNode
  • 写: 通过流水线,写入三个DataNode

Image & Journal

  • NameNode上的全部元数据信息称作该NameNode的一个Image,Image的本地备份称作Checkpoint
  • Journal的写入方式是write ahead即在进行相应操作前,先写日志,保证数据强一致,对于每一个操作,首先进行记录,然后将日志flush & sync到磁盘,之后才会进行相应的操作
  • NameNode不会改变Checkpoint文件,每一次Checkpoint改变的时候,都是完整的重写,将原本的Checkpoint替换掉
  • Checkpoint的生成是在系统重启的时候,或者Admin手动操作,或者CheckpointNode自行生成
  • 因为flush & sync操作的耗时,该操作成为性能瓶颈,优化的方法是: 将所有的操作作为一批任务保存下来,当某一个thread触发了flush的时候,将全部thread的操作进行flush&sync(这样会不会不能保证数据的持久性?)
  • =A=因为Journal/Image丢了一个都会对存储造成影响,所以,将这些数据备份多份是一个好的选择,最好还要再NFS上备份一个

CheckpointNode & BackupNode

CheckpointNode

  • CheckpointNode就是一个对NameNode的快照,定期对NameNode的journal和checkpoint进行备份,并且将journal应用在Image上之后,清空journal,然后将新的Checkpoint发送给NameNode
  • CheckpointNode清理journal使得不会出现巨大的journal,巨大的journal文件出现corrupt的可能性较大,论文作者建议我们每天创建一个Checkpoint

BackupNode

  • BackupNode也会创建Checkpoint,具有和Checkpoint一样的功能,在此之上,BackupNode还可以实时的将NameNode Image同步到自己的内存中,保证了实时的同步性
  • 实现方式:BackupNode可以读取到NameNode的实时日志流,将日志存到本地,并且将日志里的每一个操作在自己的Image上进行操作
  • 当BackupNode创建Checkpoint的时候,不需要从NameNode下载Image和Journal,它本身就已经是和NameNode同步的了,只需要将Image存到本地,效率比CheckpointNode高很多
  • BackupNode可以看做是一个ReadOnly NameNode

Comparation

  • BackupNode具有CheckpointNode的全部功能
  • BackupNode还具有实时快照NameNode的功能,可以使Checkpoint的创建效率提升

Upgrade & File System SnapShots

系统升级的时候,数据丢失问题出现的可能性会增加,为了减小在升级的时候对数据损伤的可能性,HDFS引入了File System Snapshot,即一个全局的,唯一的,能够描述整个HDFScluster的所有信息的Snapshot

  • Snapshot在系统启动的时候Admin可以决定是否创建
  • 当选择创建Snapshot的时候,在NameNode启动时会对目前的NameNode Image生成Checkpoint,这个Checkpoint不会覆盖掉旧的Checkpoint,会存在另一个位置
  • 在DataNode与NameNode进行handshake的时候,NameNode通知DataNode,创建一个Snapshot,DataNode很显然不能复制每一个数据的内容一个副本,备份使用的方式是创建到每一个block的hardlink,当对数据进行修改时,使用COW,将被修改的数据生成一个新的副本,这样可以保证原来的所有block不会被修改
  • Rollback: 在系统重启的时候,Admin可以选择回滚到上一个Snapshot

功能及实现

文件读写

HDFS的Datablock在写入并关闭(Close the file)掉后不可以进行修改,除非这个修改是可以通过对原文件进行append就可以完成的, HDFS实现的为多读单写模型

  • 当客户端发起对数据的读的请求时,之前已经介绍了会找到最近的持有数据的Datanode进行读操作如果该操作失败,client会去读列表中的下一个Datanode
  • Checksum: 当Client读取一个Datablock时,会首先验证这个Datablock的Checksum是否和metadata吻合,如果不吻合,Client会通知DataNode当前读取的block corrupt了,并且去读取另一个DataNode上的该数据
  • 当读取一个正在被写入的文件时,Client首先询问最近的该文件的长度,然后再进行读取
  • Client读取一个正在被写入的文件时,被写入的那些修改HDFS不保证对Client可见

  • 当一个Client对文件进行写入的时候,该Client获得一个锁(lease),其他Client不能对此文件进行写入
  • 该锁有hardlimit和softlimit,正在写入的Client需要发送heartbeat到NameNode,未超过softlimimt时,该writer独占此文件的锁,超过softlimit之后,可以被其他client抢占此锁,超过hardlimit(即到了hardlimit writer也没有发送心跳也没有关闭文件,也没有人来抢占锁)HDFS认为client已经退出并且自动关闭文件,释放掉锁
  • 当写入需要分配新的Block的时候,NameNode会为该block分配一个新的blockID,并且决定哪几个DataNode会持有该Block的replica,这几个DataNode形成一个流水线(pipeline),然后Client通过向流水线写入数据,以TCPpacket的形式传递给每一个DataNode
  • Client发出一个packet不需要等待DataNode的ACK,可以继续发送packet,只要不超过packet窗口的大小即可
  • 正在被写入的数据HDFS不保证在Client读取的时候可以看到,不过可以通过hflush指令,将所有收到的Packet全部ACK响应之后,让数据对Client可见
  • 如下图,写入block数据的三个阶段
    • pipeline setup: Client将数据准备好,NameNode将要接受写入的NameNode准备好,并且建立pipeline
    • Data Streaming: Client传送packet到pipeline,DataNode对每一个packet发送ACK
    • close: 所有数据都已经发送完毕,ACK均接收到,关闭链接

pipeline

 

Replica管理

对于HDFS来说,每一个Block不能存储在所有的DataNode上一个副本,这样存储空间也十分有限,也造成了大量的不必要的重复和资源浪费,因而对Block的副本的管理就是很关键的一个问题,HDFS采用了如下的几个技术来对Replica进行管理

 

Block Placement

对于很大的集群,无法通过一个扁平的网络将其链接起来,而是将DataNode分布在多个rack里,一个rack里的所有Node使用一个交换机,rack与rack之间再通过交换机相连,构成树状结构。因而网络带宽在rack与rack之间和rack内部通信相比,通常是rack内的带宽更大。 HDFS给出的用于估计两个网络节点之间的带宽的方式是:将这两个节点到他们最近的公共祖先的距离加和

dn

如图,DN00 和 DN01之间的距离为2, DN00 和 DN12之间的距离为4

当DataNode注册到NameNode的时候,NameNode通过DataNode的IP以及设置好的脚本得出该DataNode在哪一个rack

Block replica的存放对于HDFS的数据的可靠性非常重要,默认的Replica placement policy是在cost和reliablility,以及bandiwidth 之间的一个tradeoff。具体的placement为:first replica on the node that client write to, second & third in a different rack , others randomly

Replication 管理

NameNode保证block的副本数是预期的数量,当过多or过少的时候,都会进行Replica Manage 通过多个策略对Block副本进行增加和删除,当Block过少的时候,会将该Block放入replica count越少优先级越高的优先队列里等待replicate,过多的时候则会根据一个策略在需要的时候对副本进行清理。

Balancer

HDFS的Block Placement策略没有考虑磁盘的利用情况,Block Placement策略的作用是防止数据集中分布在某几个DataNode上,却无法防止DataNode的磁盘利用不均匀的问题(可能出现一个DataNode有100GB数据,另一个却有1T数据)。Balancer就是为了解决此问题的工具

Balancer会对不均匀分布的数据进行移动,不过在移动的时候他也会保证满足Block Placement,即数据所分布的rack数不会减少,数据的replica不会减少,同时通过减少跨rack拷贝数据提高Balance效率

Balancer的带宽占用是可以config的,这样可以控制Balancer在不影响HDFS的正常运作的前提下移动数据

 

Decommission — DataNode退役

(即静默期)

  • 当一个DataNode被Admin标记为不能加入该集群(或者说退出该集群)时,该DataNode进入退役(Decommissioning)状态
  • 变为退役状态的DataNode不会再接收到Block Replica创建的请求,但是可以进行读取
  • NameNode会将该DataNode上的所有数据replicate到其他的DataNode上
  • 当Replicate结束时,这个节点进入到退役完毕(Decommissioned)状态,可以安全的移除

 

 

[Linux 文件系统]一张图解释什么是硬链接什么是软链接

[Linux 文件系统]一张图解释什么是硬链接什么是软链接

= = 不知道我有多久没更新博客了(观众: 这种好吃懒做不上进的博主赶紧打包卖到幻想乡被妖怪吃了吧) 我: 诶, 真不错诶! 快把我打包去幻想乡窝要见灵梦还有紫妈!    *&^X^(**啊窝错了&^#^@*#@(*不要这么对我*Y*)IH* [博主被打包中… 请稍后] 这么久没更新博客真的是很抱歉 各种事情加上自己最近也没有继续研究太多底层相关的东西, 公司的项目的体量有点大导致窝晚上回来没有好好码字学东西qwq, 好了闲话就说到这里, 下面是正文

Linux 文件系统里的硬链接(hard link) 和软(符号)链接 (softlink)

很多刚刚接触Linux文件系统的同学包括有些接触了文件系统一阵子的同学还是会对软链接和硬链接有疑问, (比如我, 划掉)那么下面我们就借助一个简单的例子来了解一下什么是软链接什么是硬链接, 概念我就不说了, 想要看这个文章,首先要懂得什么是inode, datablock, 下面我们在tmp文件夹下做一个小实验

好辣, 我们现在就已经创建了一个叫做void001的文件,以及她的软和硬两个链接, 窝们如何区分软硬链接呢? 首先, 软链接在ls的时候(–color=auto/always)会用特殊的颜色标明出来, 不过这不是本质区别啦= =, 本质的区别在于, 软链接会占用一个新的inode, 而硬链接, 不会占用新的inode, 只是在目录block中增添了一条目录项记录, 并且指向了void001对应的那个inode.

为了证明我们上述说的,我们用ls -ali来看一下(画外音: -ali 才不是阿里呢, 只不过凑巧被窝排成了这个顺序而已), 下面的输出结果为了与图片的信息完全匹配, inode index被窝处理过了, 只是把数字进行了一个替换而已, 不影响解释原理, 原本的数字用括号注明了

这里,我们可以看出, void001, 和其创建的hard link的inode index是一样的, 而void001.soft却是不同的,这正是软链接和硬链接的区别, 再看旁边的数字, 从void001 开始 从上到下 为 2 2 1, 这个叫引用计数,指有多少个目录项指向了当前的inode, 我们通过这个也可以看出来, 2033 这个inode被引用(指向)了两次, 而 2029 只有一次, 这也说明了void001.hard指向了2033这个inode, void001.soft没有指向它,因为如果void001.soft也指向了2033这个inode的话, 那么2033的引用计数就应该为3而不是2了, 那么 void001.soft 通过什么方式指向某一个文件呢, 它通过的方式就是保存文件名, 我们可以看到, void001.soft指向了一个新的inode, 这个inode又会指向一个新的数据块, 这个数据块内存储了, void001.soft指向的文件的路径名(绝对路径), 并且这个inode(2029)的属性为 soft link, 因而我们的文件系统以及相应程序,就可以通过这个路径名,再次找到那个文件的inode并且读取它

说了这么多, 还不如一张图来的直观, 我们来看一下这张图, 结合上述描述,在对照这个图片来看, 相信你就对硬链接和软链接有一个很好的了解了

 

图中紫色部分为inode数组, 绿色部分为数据块, 我们可以清晰地看出来, 2033的被指向了两次, 因而他的引用计数为2, 2029只被指向一次, 而且它还指向一个数据块,这个数据块内存着void001这个文件的绝对路径名

符号链接 软连接对比 (1)

指向它所在文件夹的hardlink

那么, 我们还会发现一个神奇的事情, 当我们想要给一个文件夹创建一个hard link的时候, 系统会提示 hard link not allowed for directory  这是为什么呢? 这也是有原因的, 我们看一下下图

符号链接 软连接对比

我们可以看出来, 这个图中, 我建立了一个hardlink指向这个文件夹本身, 那么这个会有什么后果呢?

首先我们要知道的是, hardlink和普通文件一样, 不同于soft link没有一个类型标识他为hard link, 所以系统会把这个hard link当做一个普通文件, 去访问它的inode

那么当我们要遍历目录查询文件(用find/grep之类的指令)或者是某些程序需要遍历目录的时候, 那么就会发生难以想象的灾难:

首先访问到/tmp/havefun这个文件夹, 然后 找到了 void001(硬链接的名字), 然后找到了对应的 2033 inode,发现是一个文件夹, 然后继续访问这个文件夹, 然后再次找到void001…

形成了死循环

这种环还会引起很多问题, 感兴趣的可以深入了解一下

因而, 在现在的系统中, 是不允许用户创建指向文件夹的硬链接的

这里以一个关于古时硬链接文件夹引起的悲剧小故事结束本文

当 Rich Stevens (APUE的作者) 在写硬链接的相应介绍时, 为了研究链接向自己的硬链接, 亲自在自己的系统上做了一个实验, 结果导致他的文件系统错误百出, 正常的fsck都不能修复问题, 为了修复文件系统,他不得不用了不推荐使用的工具clri和dcheck  — 摘自APUE

 

[不是科普向?] RE: 从零开始的操作系统开发 第二集

[不是科普向?] RE: 从零开始的操作系统开发 第二集

[本文概念性内容较多, 看图党慎入]

概要

Hmm, 第一集中我们已经学会了如何让计算机在启动的时候加载并运行我们写好的bootsector, 并且通过使用BIOS提供的中断控制显卡在屏幕上输出特定的字符串, 慢慢的我们已经熟悉了16bit下的底层程序的开发, 不过就如我们综述中所说, 16bit下我们能够访问的内存十分有限, 因此我们不得不离开这个我们熟悉但是却不好用(qwq)的16bit模式,切换到32bit下, 切换之后我们就可以在C语言内继续我们的操作系统的开发了, 我们的引导程序实际上做的事情就是, 将模式切换到32位,并且将操作系统所在的磁盘扇区装载到内存里, 然后call我们的操作系统的main函数所在的地址, 这样, 整个引导程序的使命就完成了, 下面的工作就是操作系统的事情了, 本文我们主要介绍如何切换到32bit下的具体操作, 以及在32bit下控制显卡输出特定的字符

本文最后实现的效果的具体代码在github上均可获得 代码仓库地址见第一集

全局描述符表(Global Descriptor Table GDT)

我们已经熟悉了16bit下的内存的分段结构以及逻辑地址转换为内存的物理地址的方式, 现在再来回顾一下, 16位下我们想访问内存需要提供两个信息, 段地址+偏移量,  这两个信息决定了物理内存的地址, 决定的方法是 Segment Addr * 16 + Segment Offset  这个可以在16进制上形象的表示为 Segaddr << 4 + Offset, 那么现在我们要切换到 32bit保护模式下, 之前的这个内存的段-偏移量模型已经不适用了, 取而代之使用的是个功能更加强大的模型, 支持对内存的某个部分进行保护, 权限控制, 以及提供虚拟地址访问的内存模型. 另外,在CPU由实模式(16bit, 下略)切换到保护模式(32bit, 下略)下后, 将逻辑地址映射到物地址的方式也发生了改变, 这个改变, 和我们这个小标题提到的GDT密切相关, 下面我们就来具体的介绍一下 GDT

 

什么是GDT

GDT是由多个SD组成的一个数据结构, 每一个SD, 称作Segment Descriptor, 包含了一个段的各种元信息如下:

  1.  基地址(BaseAddress) 定义了这个段在内存中的物理的起始地址
  2.  段上限(Segment Limit)定义了段的大小
  3. 标志位数组, 这些标志位向CPU说明CPU应该如何处理这个段中的内容, 如本段只读, 或者本段可执行等, 相当于这个Segment的属性

每一个SD是一个8Byte长的数据结构, 通过64个bit存储了所有上述信息, SD的结构如下:

GDT_Entry

我们可以看出来比较反人类的地方是这个数据结构存储的不同类型的数据信息并不是连续的= = 推测是因为为了向下兼容才这么做的, 具体的原因为何还没有调查过, 从上述结构中, 如果我们想查询出这个SD对应的段的基地址, 我们需要将SD的16 — 31 ,32 — 39 56 — 63位拼接到一起, 得到基地址的值. 我们再来看一下这个结构, 这个结构中描述了 BaseAddr, Limit 还有Flags& AccessByte, 其中的Flags & AccessByte如下图所示

SD(本图出自 该链接)

这里的Flag的bit位比较多, 我们挑几个重要的介绍一下

L位是表示我们的内存使用64bit的代码段模式还是32bit, 这里我们使用32位, 因而此为置零,

DPL 指的是该段的代码拥有的CPU的权限级别,因为我们现在要使用程序直接操作CPU, 编写的操作系统也要操作CPU的很多特权指令, 因而该段的权限设置为 最高权限(ring 0, highest privilidge)

P 指的是这个段在内存中是否存在(?待确定)

具体每一个位表示什么意思的细节我们先不深究,想要了解的孩子可以看 “Intel® 64 and IA-32 Architectures Developer’s Manual: Vol. 3A”, 下面我们要使用汇编语言定义整个由DATA_SEG和CODE_SEG组成的GDT, 代码如下

我们定义了两个段, 而且这两个段是重叠在一起的, 基地址相同, 大小也相同, 只不过一个是代码段一个数据段, 为了简便起见, 我们目前只需要这两个段即可, 通过代码我们可以看出来, 在两个段的上面还有一个全为0的段, 是用来做保护的,防止用户使用未初始化过的段寄存器访问内存获得随机脏数据. 具体为何说这个是用来保护的, 我们下面马上就要介绍

 

保护模式下的逻辑地址和物理地址的对应关系

在继续之前, 我们先补充一个刚刚没有说到的一个问题, 即目前的逻辑和物理地址是如何对应的.

在切换到保护模式下之后, 我们要指定访问的内存需要给出的是Segment Index + 偏移量, 之前在段寄存器中存储的是段地址, 目前这个地址变为了Segement Index,所谓的Segment Index的意思其实就是, 我们要访问第几个段, 然后, CPU会将GDT中对应段的描述符取出来, 找到这个段的基地址(Base Address),以及获得它的各种状态位, 然后加上提供的偏移量,最后对应到物理地址.  下面我们来解释一下为何要设置64bit的0在GDT的开头, 因为, 如果错误的使用了某个未初始化的段寄存器, 这个段寄存器的内容为 0 的话, 如果不设置64bit的0的话, 就会默认去找GDT里的第一个Entry 也就是我们定义的CODE_SEG段,这样就会读到开发者不期待得到的数据, 而且因为这个行为是合法的, 允许访问第零段,不会报错, 但是, 这个访问对于用户来说是没有意义的,因而这个地方会对之后的程序造成不可估量的影响, 那么合理的解决办法是, 我们让第零段变为无意义的段, 这样只要访问第零段就会直接报错, 因而我们将第零段设为了64bit全为零, CPU在访问到这里的时候就会panic而终止掉下面的执行

 

切换到保护模式需要做的另一项工作

设置好了GDT之后, 我们要将这个表使用lgdt装载, 为了装载GDT,我们需要一个用来描述我们GDT的结构, 叫做GDT-descriptor, 这个描述符只存储两个信息, 即GDT的地址, 以及GDT的size – 1, 为什么是size – 1 而不是size大家可以思考一下. [实际上, 我们不会将GDT descriptor的size属性设置为0,那样表示指向一个空的GDT, 没有意义, 而且, GDT Descriptor 能够表示的GDT的大小在 0 — 65535之间, 如果我们的GDT大小是65536的话, 就无法表示, 这样我们就可以做个平移, 让 GDT存储大小的时候 0 表示 1 , 65535表示 65536.]

设置好这个GDT Descriptor之后, 我们将这个地址作为操作数, 传递给 lgdt指令, 就可以将GDT装载好了

 

以上是我们切换到保护模式下要做的最重要的一步,  切换到保护模式下还要做一些其他的操作, 首先就是 “关中断” , 保护模式下中断的实现方式和实模式下的完全不同, 如果我们还使用由BIOS提供的这套简单的中断(实际上是提供的中断向量表), 就会出现问题, 因而在我们自己设置好中断向量表之前, 不应该允许中断的发生

关闭中断之后, 我们就可以装载我们上边准备了好久的GDT了, 装载了GDT之后, CPU才知道保护模式下该如何寻址

然后, 打开保护模式切换的开关, 我们要将控制寄存器 CR0的最低位置为 1 , 开启保护模式.

开启保护模式之后, CPU流水线中的所有在执行, 等待执行的指令, 或者缓存的微指令,这些信息都是实模式下的逻辑处理的, 而我们现在切换为了保护模式, 为了保证不让这些缓存影响CPU的正常运行, 我们需要flush缓存 ,  为了flush缓存,我们需要执行一个long jump,注意,这里跳多远不重要, 重要的是”如何跳”, 我们使用long jump跳到当前指令的下一条也可以, 跳到比较远的地方也可以, 但是 使用short jump跳到比较远的地方, 也不会flush缓存, 这里主要是为了让long jump对缓存的flush起作用 , 同时为了方便起见,这个long jump我们一般就直接跳到32bit模式下的入口代码的地址了~

为了完成以上操作, 实现的代码如下

 

在在保护模式下对显卡进行操作

现在我们已经切换到保护模式下了, 很明显我们不能使用中断来操作显卡了, 不过幸运的是, 我们可以直接操作显卡对应的内存控制显示的内容, 它在内存中被映射到0xb80000, 我们每次写两个Byte, 第一个Byte是要显示的字符的ASCII码, 第二个Byte是字符的颜色和背景颜色, 然后就可以显示在屏幕上了, 向0xb8000开始的不同地址写入不同的内容会在屏幕的不同坐标出显示相应的内容, 这里给出显示满屏的@符号的代码

 

完整的代码

实现到此,我们这一次的任务就完成了, 完整的代码在github的repo可以获得, commit id 为  7e6abac774439e0c234a1fe5a40755f609db780a  执行make boot即可看到效果哦~

欢迎大家在评论区对文章进行吐槽或者评价, 这样我就能和大家交流学到更多的东西了~ 不是很开心的事情嘛

[科普向?] Re: 从零开始的操作系统开发 第一集

[科普向?] Re: 从零开始的操作系统开发 第一集

Hmm, 果然还是开坑了~! 在学校智障的操作系统课设的发起下, 再加上每个程序员都有一个写一个自己的操作系统的公主梦(雾), 我们愉(作)快(死)地开坑啦~

以前曾经跟着 “30天自制操作系统” 玩过DIY操作系统, 不过那个书更像面向小白, 讲的东西也不够系统, 而且使用的是自己改过的nas汇编器, 因而不能算写过, 这一次则是真正的开坑啦~ (虽然课设时间很短写出一个完整的根本不可能不过慢慢写总会写完的你说对不喵~)

我们的开发过程在Bearychat上直播 neugeek.bearychat.com 的Toy-OS频道, 我们的git-repo 为 https://github.com/VOID001/toy-os 菊苣们不要喷, 既然挖了坑窝就不会不填(….你都已经挖了多少个坑了啊喂! (逃))

这个系列的文章将会记录在开发操作系统的整个过程中的一些经验&心得&吐槽 不知道会有多少集(

 

参考资料们:

  • MIT 的 XV6 源代码 & handbook
  • University of Birmingham 的 Writing an simple operating system from scratch
  • Quora, StackOverflow
  • Jiong Zhao Linux 0.11内核完全注释

 

我们使用的工具链:

  • GNU Assembler & GNU C Compiler
  • Qemu
  • Gdb
  • objcopy, objdump, binutils, elfutils
  • GNU Makefile

 

操作系统编写总览

什么是BIOS

参考阅读: http://whatis.techtarget.com/definition/BIOS-basic-input-output-system

我们的定位是写一个操作系统,那么首先我们应该了解,整个操作系统都应该由哪些模块构成, 那么就让我们从操作系统的启动说起, 说到这里就不得不说一下BIOS, BIOS是Basic Input and Output System, 是你的计算机加电运行后加载的第一个程序, 它是固化在你的EPROM内的一个程序片段

BIOS被加载之后, CPU便会去执行BIOS的代码,这时候, BIOS进行硬件自检, 保证硬件没有故障后, 就会加载操作系统, 同时BIOS也提供了一个通用的接口, 供我们用来与不同的外设如VGA显示器进行交互, 具体如何使用将会在下文中介绍

boot-sector

刚刚我们说到了, BIOS作为开机运行的第一个程序, 在进行硬件自检后, 便会装载操作系统, 可是这时候,操作系统还在磁盘(或者其他存储介质内), BIOS如何知道, 我们知道BIOS是由厂商写死在ROM上的, 我们的操作系统程序如果每次存放的位置都不一样的话, 岂不是每次都要去重新刷写EPROM? 当然没那么麻烦, BIOS和编写操作系统的程序员有一个约定, 那就是, 当自检完毕之后, BIOS会自动按顺序(你设定的Boot Sequence)检查每一个media的第一个扇区(0扇区)是不是Bootable,如果找到一个Bootable的扇区, 那么就加载这个扇区到内存中, 接下来会执行这个刚刚装入内存的程序, 这样, 我们就可以在这里执行对硬件初始化&装载操作系统程序等操作啦

对于CPU而言, 代码和数据都是二进制,那么如何区分这是一个bootable扇区呢? 流我们将bootable扇区称为 boot-sector,  为了让CPU能够识别这个扇区是boot-sector, 对boot-sector有如下的要求:

  •  必须是512Byte大小
  • 512Byte的末尾两个Byte应该被填充为0xaa55

拥有了这两个条件, 这个扇区才是一个boot-sector, BIOS才会去加载它, 下面是一个非常简单的,开机后就让CPU进入死循环的一个程序的binary文件, 这就是一个boot-sector

中间的0被省略,  因为little endian的原因 0xaa55 在实际存储的时候为 55 aa

切换到32bit-protected mode

上面我们的所有操作都是在16bit 实地址模式(即你访问的地址就是真实的物理地址)下进行的, 而 16bit的实地址模式可以访问的内存最大为 1.0615234375(数字是如何计算出来的, 参考内存分段管理的相关知识 0xffff * 16 + 0xffff) 只比 1MB多一点的空间, 这对于我们之后要写的操作系统, 以及我们要运行的程序是远远不够的, 那么接下来我们就要切换到32bit的虚拟地址模式下, 进行接下来的开发

操作系统的核心模块

在切换到32bit protect mode之后, 我们需要实现的是kernel system call, file system, multiprocess scheduling, 以及 支持我们的Keyboard和VGA Driver

其他(Misc)

为了让我们的操作系统可以交互, 我们需要实现一个Interactive Shell, 并且实现几个能够运行在我们的操作系统上的程序, 之后也许还会支持网络 & 图形界面, SDL Driver等

 

以上就是一个综述啦, 可以看出来这是一个不小的坑, 不过嘛, 很有趣对吧~!

 

我们的第一个Hello world 操作系统

AT&T汇编+GNU Assembler的一些比较坑爹的事

为了更好的和XV6产生一致性, 我们采用了 AT&T 汇编, 使用的为GNU Assembler 进行开发, 关于AT&T汇编与Intel汇编的区别, 这里有参考文章http://www.delorie.com/djgpp/doc/brennan/brennan_att_inline_djgpp.html

需要注意的问题是, 之前在使用nasm作为Assembler的时候可以直接通过 -f bin 指定输出的程序为 RAW格式的, 即为不含有任何ELF(Linux下的文件格式)的信息, 而使用as进行编译的时候, 目前我们还没有找到办法直接输出RAW binary文件, 而且, 在AT&T中貌似也没有可以方便的在0扇区的最末尾填充0xaa55的方法(Intel中我们通常使用 time 510-($-$$) db 0  来在整个扇区填满0,  之后 dw 0xaa55 ), 另外! 另外! 对于那些在Intel下的标号后定义的字符串, nasm可以轻松识别地址, 然而, 然而, 然而!(重要的事情说三遍)as 不会! as会认为那是一个外部符号, 等待链接的时候Relocate, 因而下面这段代码如果不进行链接的话, 这个’string’ 标号就会被用 0x0替换

导致结果出错

 

那么正确的姿势是什么呢, 下面这样可以生成一个正确的RAW binary image(假设我们的源文件叫做boot.s)

 

计算机刚刚启动之后的内存布局

上面的代码中的0x7c00 是什么鬼肯定有人要问, 我们下面就来解释一下, 在计算机启动完毕之后, 内存的布局如下:

 

Screenshot from 2016-07-05 20-06-57

(本图摘自Writing a Simple Operating System — from Scratch)

我们可以看到, 在低地址最下方有着中断向量表, 再上方就是BIOS的数据内容, 然后, 为了防止我们的boot-sector将BIOS Data/中断向量表的内容覆盖, BIOS将boot-sector加载到的地址为0x7c00处, 那么现在来解释一下为什么链接的时候要指定这个参数, 因为当你链接的时候, 那些需要Relocate的符号, 是按照一个实际地址 + 在本文件内的偏移量给定的, 而因为我们的boot-sector默认加载的位置为0x7c00, 那么我们的实际地址就应该为0x7c00, 这时候我们再想指定某个标签(如string) 就会在运行的时候将string Relocate到 0x7c00 + 在binary文件中的offset(可以通过hexdump看到)

Qemu with GDB

为了让我们的调试更愉.悦, 能够使用gdb对代码进行调试则是极好的 qemu支持远程调试功能, 在运行qemu的时候, 指定参数 -s(开启1234端口并且等待debugger链接) -S(先不要执行CPU指令) 后, 即可通过gdb连接到这个端口进行调试啦, 具体的操作方法如下

有了这个之后, 在操作系统的开发初期就能更好的看~代~码~啦

Writing our first Hello world OS

为了表示对LL的敬意, 我们准备在屏幕上输出 Hello Niconico, 之前已经说过了, BIOS提供了一部分通用的接口供我们和硬件打交道, 我们就不需要关心硬件的更具体的细节了, 这里我们就要用到这个接口, BIOS 将此接口通过中断的形式提供给我们. 为了在屏幕上输出一个字符, 我们通过给一些特定的寄存器赋值, 即汇编语言的参数传递, 类似C语言的参数传递. 一个简短的打印一个 字符’A’的代码如下:

我们为了实现打印一整串字符串,  一个稍微复杂点的程序如下:

这里注意, 我们被AT&T的汇编坑了好久的一个地方就是 mov $string, %bx . 刚开始, 我们写的是

mov string, %bx  这个代码一直没有办法打印出我们想要的字符串, 原因就是, 在ATT汇编中, 这句被解释为了, 将string 这个标号处对应的内容取来, 放到%bx中, 而我们想要实现的是: 将string这个标号对应的地址取来,放到bx中, 如果不加$, 所有的地址在ATT中都会被解释为”那个地方的内容” 一定要小心

以上代码可以在github获取到~ 这个版本对应的commit是  8c2f90aa8830edaf9ea10809797d14918efb463e  只要按照README装好需要的工具, 执行  make boot 就可以看到效果啦~

 

FisKyZcAmN3juq8lmTlENUyJ55tF

 

今天就到这里啦

setcap wine 遇到的问题解决

setcap wine 遇到的问题解决

之后为了让普通用户也能通过wine访问到网络接口,需要给wine的相关程序(wine-preloader 和 wineserver wine) 一些特权

 

参考  man capabilities 和 setcap

  •  首先需要给CAP_NET_RAW 权限 这个要给到 wine-preloader 上,不过在设置完这个权限之后,执行 wine XXX.exe 会报错

wine: error while loading shared libraries: libwine.so.1: cannot open shared object file: No such file or directory

这是因为特权模式的程序运行的时候是不会检测到相对路径的lib库的, 具体参考文章如下:http://stackoverflow.com/q/6493846/296473  解决方法在文中已有了 就不赘述了

  •  上述问题解决后,运行wine 会提示  Internal errors- Invalid parameters  , 而且winedbg不可以attach到进程, 这个问题的解决方法是给wineserver(不是wine-preloader)CAP_SYS_PTRACE权限

 

 

__attribute__ in C

__attribute__ in C

__atrribute__ in C

Take a look at this code for example (in Cygwin master branch /winsup/cygwin/winsup.h)

Then gcc xxx.c and then run the code it will print out “Hello World” ~

So why it works?

The code with constructor attribute run before main function and code with destructor attr run after main function

The __attribute__ can do more than above

Another usage of __attribute__ is to customize the section of a certain code , take a look at this example:

Then compile the code and run readelf tool to check the section in the code:
$ readelf -S a.out

You can see a section called my_custom_section and with AX acess(alloc + executable)

This proves that we can use __attribute__ to customize the section

Linking

Linking

Linking

Compiler Drivers

  • When you run gcc -O2 -g -o p main.c swap.c ,These things happen

    • First the C preprocessor translate main.cpp into main.i

      main.cpp—->(cpp)—->main.i

      cpp main.c /tmp/main.i

    • Then main.i was compiled by C Compiler (cc1) into main.s

      main.i—->(cc1)—->main.s

      cc1 /tmp/main.i main.c -O2 -o /tmp/main.s

    • Then the driver runs the assembler(as) and create a relocatable object file main.o
      main.s—->(as)—->main.o

      as -o /tmp/main.o /tmp/main.s

    • Same things are done for swap.c

    • Finally it runs the linker(ld) which combines main.o and swap.o and other necessary files to create excuteable object file p

      main.o + swap.o + other system object files —->(ld)—->p

  • What is Static Linking