Blog

最近用一些零碎的时间学习KVM，算算大概也快有一个月了吧，进度还是很缓慢的，感觉该写一些类似读书笔记的东西了。欢迎大家来讨论。 KVM 即 Kernel Based Virtual Machine, 是一个内核模块，使用它需要CPU支持虚拟化。加载KVM模块后，系统中会有一个 /dev/kvm 设备，这个设备提供 ioctl 和 mmap操作。 目前，KVM还必须和修改过的Qemu配合起来使用（这样说是不准确的，因为已经有一个叫 native kvm tool的东东了），KVM 使用Qemu做I/O模拟，虽然Qemu也提供CPU的模拟，但是KVM没有使用，也许这正是KVM+Qemu比单纯用Qemu进行虚拟化性能高的原因吧。 运行在Qemu中的虚拟机被称为Guest，运行Qemu的物理机称为Host， 每一个guest是host上的一个进程，guest的每一个cpu对应进程中的一个线程。 Qemu和KVM之间通过ioctl进行交互，KVM和guest之间通过VM Entry和VM Exit进行切换。 那么什么时候会发生VM Entry和VM Exit呢？ 先从虚拟化这个概念说起，其实通常的进程/线程也是一种虚拟化。Intel把CPU的优先级分了4层，ring0完整的暴露了CPU的各个接口，运行在ring0的操作系统可以任意使用CPU提供的所有功能，相比之下，运行在ring3的应用程序只能看到较少的CPU接口。 在这种情况下，操作系统担任的角色就是类似VMM（Virtual Machine Monitor）。运行在ring3的应用程序，自以为自己掌握所有的计算机资源，比如CPU资源，4GB的内存等等。众多傻乎乎的应用程序（用户态进程）在自己的虚拟世界里玩的不亦乐乎，而操作系统默默的在背后处理各个进程CPU相关的数据的保存和恢复，比如修改cr3寄存器，修改页表等等。 所以，操作系统完成了对ring3环境下的CPU的虚拟化，而KVM则是实现了一个完整的CPU虚拟化（所以这种类型的虚拟化，能运行不经任过何修改操作系统）。 kvm是一个内核模块，用kvm虚拟化技术创建的虚拟机，如果guest OS 执行的是与访问全局资源无关的指令，那么这些指令是直接运行在物理CPU上的； 当执行到了访问全局资源的指令，比如产生缺页错误，或者设备I/O，则guest OS产生VM Exit退出到KVM中，然后KVM再根据退出的原因，决定是由自己来处理还是交给Qemu。 当发生VM Entry和VM Exit 时必须要有一个结构体来保存当前CPU的上下文，这个结构就是VMCS (Virtual Machine Control Structure)，而前面提到的，使用KVM必须要有CPU硬件上的支持，指的就是CPU硬件必须提供一种功能，能自动根据VMCS的内容完成VM和VMM之间的状态切换。 从原博客拷贝的评论 Davelv： 写的不错，让我这种没研究KVM技术的人都看懂了。 不过有一点比较容易让人疑惑，在这里没有说清楚qemu是什么。 qemu在这里就是qemu-kvm这个修改版，他是一个单独的程序，运行起来是一个进程。 就是你说的使用KVM技术的qemu，这个进程的一些IO操作是像原始的qemu一样做模拟，但是和处理机相关模拟则会调用的kvm内核模块的功能（而不是像旧的qemu一样全部自己模拟）。kvm内核模块是一个运行在ring0的系统模块（驱动）本身没有独立的进程，依附于系统内核存在，作为操作系统(ring0层）的一部分 给应用程序（ring3层）如qemu-kvm相应支持。

首先需要安装一下额外的工具包，一个是 libc6-dbg，这是带有debug symbol信息的 libc.so；另一个是libc6-dev，这是glibc的源代码，获取之后我们就可以在gdb中查看代码了。 在Ubuntu/Debian 系统上，我们可以通过以下2条命令获得： $sudo apt-get install libc6-dbg $sudo apt-get source libc6-dev 在Fedora/Red Hat 系的OS上，需要安装的软件包的名字不叫 libc6-dbg，libc6-dev，貌似应该是glibc-debuginfo。 之后，以一段小程序为例来演示整个过程，小程序包含了一个系统调用fork()，一个库函数printf() int main(){ pid_t son; if((son=fork())==0) printf("I am son\n"); else printf("I am farther\n"); return 0; } 接着，编译产生带有调试信息的可执行文件 $gcc -g -o f fork.c 然后开启gdb调试 $gdb fork 在开始调试之前，需要指定一下刚刚获得的带有libc6-dev源码文件夹的路径，比如我把这些源码放在了 ~/glibc/lib 文件夹下，通常一般程序需要的是stdio-common这个目录内的文件， 于是输入 (gdb) directory ~/glibc/lib/stdio-common 注意看其中几条命令的用法。 程序在调用fork函数后，其实执行的是glibc包装过的__libc_fork ，并且我们可以查看其源代码。 这里有几个常用命令： s 单步执行； list 查看源代码； start 程序开始执行，并在main函数处停下，相当于在main处加断点。 但是在执行了几步之后出现了这样的错误： _IO_list_lock () at genops.c:1299 1299 genops.c: No such file or directory. in genops.c ...

时间倒回到2011年5月的一天，大学的最后一门课《计算机信息安全技术》，讲到《缓冲区溢出》这一章，并且给出了一段示例代码来演示缓冲区溢出，回到宿舍后出于好奇我运行了一下这段代码，发现结果并不是书上所说的那样，当时在人人网也发过一篇吐槽的日志，但是一直拖到现在都没有仔细的去研究过，正好现在十一放假没事，就花点时间搞搞啦。 书第136页-137页。代码如下，出于简单考虑（其实书上的C++代码格式也是错的），我除去了头文件和cout函数，这样就跟纯C语言代码是一样了。 void function(int a) { char buffer[5]; char *ret; ret = buffer + 12; *ret += 8; } int main() { int x; x = 10; function(7); x = 1; return 0; } 书上说最后x的值是10，不是1，而我的结果恰恰相反。 接着用gcc产生汇编代码，在这里用 gcc -O0 -S命令告诉编译器不采用任何优化措施，产生最原始的汇编代码，这样有利于我们分析，即使是采用-O1级优化的时候，汇编代码已经很难读了，大家可以试一试。 function: pushl %ebp movl %esp, %ebp subl $16, %esp leal -9(%ebp), %eax addl $12, %eax movl %eax, -4(%ebp) movl -4(%ebp), %eax movzbl (%eax), %eax addl $8, %eax movl %eax, %edx movl -4(%ebp), %eax movb %dl, (%eax) leave main: pushl %ebp movl %esp, %ebp subl $20, %esp movl $10, -4(%ebp) movl $7, (%esp) call function movl $1, -4(%ebp) leave ret 书上详细的解释了为什么结果是10，下面我来逐条分析。首先画一张内存图，同样处于简洁考虑，只画function函数附近的内存分布，不影响分析。 ...

Table {:toc} 问题 有一个数组 31,-41,59,26,-53,58,97,-93,-23,84 。现在要求出它的连续子串的最大值。 比如，31,-41,59,26是它的一个连续的子串，他们的和为75。但是75并不是最大值，有一个子串 59,26,-53,58,97它们的和187才是最大的。 解答 《Programming Pearls》第77页开始一共给出了4种解法，前两种非常简单，是大多数人思考几分钟就能想出的方法，但是复杂度却很高，分别为O(n^3)和O(n^2)。后两种解法则非常巧妙，更神奇的是第四种方法居然只有线性复杂度O(n) 解法1、解法2略。 解法 3：分治法 复杂度为O(nlogn)。 分治法在结构上是递归的，在保证不改变原问题的条件下，将问题的规模减小，生成多个子问题，并多次递归调用自身来解决子问题，之后再将子问题的求解结果合并成原问题的解。 对于case1，我们只要比较 ma 和 mb 的大小就可以得出原数组的最大子串的和了。 对于case2, 只要把ma和mb相加即可。以上只是将问题一次分解的过程，我们还需要将问题再分解直到不能在分解或是能直接得出结果为止。 什么时候能直接得出结果？当子数组只有一个元素的时候，此时ma就是它本身（为负数时我们让它为0）。 因此，原数组的最大和 = 2个子数组中最大和的较大者，或者，包括中间分界线的一段连续区域的和。 即，maxsum(orignial)=max(mc，maxsum(a)，maxsum(b)) 递归结束的条件是，子数组只有一个元素，如果是正返回它本身，为负返回0 代码如下。 int maxSubArray(std::vector<int>& nums) { return maxsum(nums, 0, nums.size()-1); } int maxsum(std::vector<int> &nums, int left, int right) { if (left > right) { return 0; } if (left == right) { return nums[left]; } int mid = (left + right)/2; int left_max = INT_MIN, right_max = INT_MIN; int tmp_max = 0; for (int i = mid; i >= left; i--) { tmp_max += nums[i]; left_max = std::max(left_max, tmp_max); } tmp_max = 0; for (int i = mid+1; i <= right; i++) { tmp_max += nums[i]; right_max = std::max(right_max, tmp_max); } return std::max(left_max+right_max, std::max(maxsum(nums, left, mid), maxsum(nums, mid+1, right))); } 解法4：扫描法 一次扫描数组即可得出答案，复杂度O(n)。这种方法用文字描述不容易说清楚，下面用每一步运算的图示来表达。伪代码如下： ...

泡了N久论坛，看了N多帖子以后终于成功的把 iPhone 3G 有内置卡贴的手机成功的破解，并且抽出了卡贴，越狱成功，可以用任何移动运营商的手机卡了！ 哦耶！散花庆祝！（如果不懂什么是“越狱”请自行补习相关知识 ） 说一下我的经验心得： 1、我主要是根据这个教程做的 http://bbs.weiphone.com/read.php?tid=401812，当然，之前也学习过其他的帖子，如果你也准备动手的话，请先泡泡论坛，多学习学习，也要注意一下那些失败的家伙是怎么折腾的，等功力大成之后，再动手不迟~（不要草率，先多学点注意事项，毕竟你要整的是贵重脆弱的东西啊） 2、下面说下我这次破解跟别人的不同之处。如果你的iPhone也非常不幸的是内置卡贴的话，可以参考我的方法，不用拆开手机。我是用了一根绣花针（一定要细小，但是要结实），在放SIM卡的开口处挑的，先用很薄的小刀沿着SIM卡开口把卡贴（一般是一根屎黄色的带子）划断，很容易划断的，然后用针一点一点把它的挑出来，你挑不出来的部分就让他在里面，没事的，关键是要把挡在SIM下面的卡贴去掉，下图就有这个万恶的卡贴！！（这个过程如有疑问欢迎通过邮件联系我^_^） 下面放图，分享一下～～ 先来一张万恶的卡贴：

话说，我是在8月13号左右申请的，9月10号收到光盘的，花了4个多星期，比官方说的6—10周快了一点，毕竟，人家是从荷兰不远万里的寄来的光盘，哈哈。 如果你也想申请，点这个链接https://shipit.ubuntu.com/ 任何人都可以申请哦，不分国界，不分性别….这就是“Ubuntu精神”。 “Ubuntu”is an ancient African word that means “humanity to otherts”.This Linux distribution brings the spirit of Ubuntu to the software world. 下面贴几张图吧~（点击图片放大） 这是邮件的包裹，没拆开之前

论文的原文在这里 Dune: Safe User-level Access to Privileged CPU Features 1. Introduction Dune 的目标是让用户态程序直接使用硬件特性（例如，获得更好的硬件加速等），不过所谓的 “直接” 还是在虚拟化的环境中。Dune 利用现代 CPU 的虚拟化功能，提供给用户一个 进程的抽象， 而不是一个 虚拟机的抽象。 Dune 是一个内核模块，可以在需要的时候加载到标准的 linux 内核中。 于是一个普通进程可以进入 “Dune Mode”，在这个模式下的进程可以直接访问页表、中断、系统调用表等等。 特点： Dune 进程是一个普通的 linux 进程，唯一的区别是它用 VMCALL 指令进入系统调用。 Dune 内核模块只提供进程级别的抽象，因此相对于 KVM 来说要简单得多。 3. Kernel Support for Dune Dune mode 下的进程运行在 VMX non-root 模式，可以安全的访问特权级硬件。然后看一下 Dune 的整个架构图。 {:height=“300” width=“300”} 如果说前面 1、2 小节读下来仍然云里雾里的话，一看到这个图立刻觉得特别清晰了，因为太像 KVM 的架构了！ 同样也是利用 CPU 提供的 VT-x 技术，Dune 更像是一个轻量级的 KVM。 在后续的章节中，作者也提到了 Dune 项目的原型就是在 KVM 的基础上修改的，特别是对 VT-x 操作的部分。 ...

在实现的时候发现这张状态转换图非常重要。整个 raft 的运行就是围绕着这张图发生一系列状态转换。 因此，第一步实现一个状态机就成了关键。 参考资料 Go 并发、管道

论文原文链接 In Search of an Understandable Consensus Algorithm Raft 保证一致性的 4 个重要组成部分： 领导人的选举，日志复制，安全性，集群成员的变化。 Raft 是一个强领导者算法，意思就是所有的数据以当前领导者（Leader）上的为准，领导者上有的就是正确的，领导者上没有的就是错误的。 5.1 Raft 的基本术语和概念 任期的概念：任期(term) 用来区分时间轴上不同的领导者，当领导者换了，日期也也立刻变更。raft 算法用 term 来表示一个 逻辑时钟，而不是用传统的几月几日几点几分几秒，term 是一个递增的整数，当领导者变了，term 也 +1。 集群中的每一个服务器都存储了一个 currentTerm，任意两个 server 要相互通信时都需要包含各自的 currentTerm。如果一个 server 的 currentTerm 值小于对方，那么它需要更新自己的值。如果 candidate 或者 leader 发现他们自己的 currentTerm 比其他人的要小，那个立马变成 follower。如果收到的请求包含一个旧的 currentTerm，直接忽略。 原论文的图 2 包含了大量的信息，我自己制作了下面四个图片。 5.2 领导人的选举 领导人不断的向集群中其他人发送心跳包，当集群中一个 server 在一段时间里没有收到领导人的心跳包，那么他就要起义，自己竞选当领导人。 开始一次选举 Follower 把自己的 term+1，身份转变成 Candidate，向集群中其他 server 发起请求投票 RPC，当他获得大多数选票时，就成功当选。 问题：他怎么知道 “大多数” 是多少？（etcd 的实现似乎是每个 server 知道集群里面有多少台服务器） ...

投票的过程 日志的复制 一旦选举成功，所有的 Client 请求最终都会交给 Leader 处理。 当 Client 请求到 Leader后，Leader 首先将该请求转化成 LogEntry，然后添加到自己的 log[] 中，并且把对应的 index 值存到 LogEntry 的 index 中，这样 LogEntry 中就包含了当前 Leader 的 term 信息和在 log[] 中的index信息，这两个信息在发给 Follower 以后会用到。 所以一旦一个节点成为 Leader 以后，那么它的 log[] 保存的这一组 LogEntry 就代表了整个集群中的最终一致的数据。用 raft 论文的话来说就是，节点是一个状态机，LogEntry 是指令集，任何一个节点，只要逐个执行这一串指令，最后状态机的状态都一样。 先看看与日志复制相关的几个数据结构，首先是 raft 结构，其中相关的有以下几个变量： type Raft struct { .... log []LogEntry commitIndex int // 所有机器 lastApplied int nextIndex []int // 只在 leader matchIndex []int ..... } nextIndex 和 matchIndex，这两个数组只有当这个 raft 是 Leader 的时候才有效，否则这两个数组的内容无效。 ...