“五一” 假期去了安徽省黄山市歙县,此行的目的是去参加表哥的婚礼的,也顺便趁着春暖花开之际去爬爬山。

第一天去山上的野生竹林里采了好多竹笋,野生的、纯天然的哦!!(可惜当时没带相机,所以也没拍照片了);第二天去山上采了好多茶叶,有不少是野生的茶树回来以后和爸妈摸索着用灶上的锅烘干,制成了真正的茶叶,我现在杯子里喝的就是呢!!

身处大山深处,远离城市的喧嚣,有一种世外桃源的感觉,于是我决定等以后不干IT这行了就归隐山林,过“采菊东篱下,悠然见南山”的日子。

(more…)

Tags: . 9,663 views

This post will introduce a funny way to access physical memory from user space, I will:

  • write a kernel module and load it. The module will allocate a page in kernel space and write some characters in this page.
  • write a user program, read the content of that page and print.
    What’s the difficulty in doing this ?

As we know, a user program (or process) has its own virtual address space, when it calls malloc() to apply a block of memory, the malloc will return the start address of the allocated virtual memory, user program doesn’t know the actual start address of physical memory.

Here, I will access the physicall address from a user program with the help of /dev/mem.

Firstly, let’s talk about /dev/mem, and enable access to /dev/mem

/dev/mem is a virtual device which provides a way to access to system physical memory, but unfortunately, in most Linux distributions, userspace(including root) can’t read /dev/mem by default [1]. So, if you want to use this feature, please compile a new kernel by yourself. I will show you step by step.

go to www.kernel.org download a latest version of linux kernel.
decompress it.

the following is in command line ( shell ):
$ sudo su //change to root
# make menuconfig // this will generate a .config file
# vim .config
set
CONFIG_STRICT_DEVMEM=n
CONFIG_X86_PAT=n
CONFIG_EXPERT=y

ok, continue to compile it.

# make -j4
# make modules
# make module_install
# make install

reboot my computer, and I will enter OS with a new kernel.

Secondly, let’s write a kernel module.

mmap.c :

to compile the kernel module, I need a Makefile:

# make
after make, a kernel module “mmap.ko” will appears in my current directory.
# insmod mmap.ko
then, look the “printk(“addr= 0x%08x\n”, (int)addr);” in `dmesg`
# dmesg

[80005.141345] addr= 0x77128000

Finally, write a user program using mmap() function.

the declaration of mmap is:

void *mmap(void *addr, size_t length, int prot, int flags,int fd, off_t offset);

`man 2 mmap` says:

The contents of a file mapping are initialized using `length` bytes starting at offset `offset` in the file (or other object) referred to by the file descriptor fd. `offset` must be a multiple of the page size.

so, I can use the address printed by mmap.ko (0x77128000) as the `offset` parameter.

user.c

Attention, the KERNEL_PHY_ADDR may vary every time you load the mmap.ko, so, if you copy the code and complie it on your own computer, please remember to change it.

ok, compile user.c
# gcc -o user user.c

make sure you are a super user
# ./user

the out put is:

With great power, comes great responsibility

That’s all.

References
[1] http://lwn.net/Articles/267427/
[2] http://stackoverflow.com/questions/9662193/how-to-access-kernel-space-from-user-spacein-linux
[3] http://hi.baidu.com/damonzhou/item/e15d06e9ae20f1f5e1a5d4a9

Tags: ,. 25,307 views

跳表(skiplist) 是一个非常有趣的、简单的数据结构, 应用也非常广泛, 著名的NoSQL内存数据库Redis, 就用到了skiplist作为排序集合的基础数据结构。 跳表最大的特点就是插入、删除操作的性能均为O(logn) 。

关于它的原理网上有一大堆,如果不了解的话,可以先看看文章末尾的【参考资料】, 或者动手google一下。 正好这里也有一篇我觉得写的不错的文章, 可以猛击此处 。
(more…)

Tags: ,. 29,947 views

This content is password protected. To view it please enter your password below:

23,577 views

KVM保证guest OS正确执行的手段就是当guest执行I/O指令或者其他特权指令时,引发处理器异常,从而进入到根操作模式(Intel 的VT-x技术)。

当guest OS执行一些特权指令或者外部事件时,比如I/O访问,对控制寄存器的操作,对MSR(Machine Special Register)的读写操作、数据包的到达等,都会引起CPU发生 VM Exit,发生VM Exit后,KVM 会将guest OS 的状态保存到VMCS中,把Host的状态装入物理CPU,处理器进入根操作模式。接着KVM会读取保存的VMCS中 VM_EXIT_REASON字段的内容,从而知道虚拟机退出的原因。如果由于I/O信号到达,则退出到用户模式,交给Qemu来处理,处理完毕后,再通过KVM重新进入guest OS运行;如果是外部中断,则有KVM做一些必要的处理再返回。

(more…)

10,259 views

最近用一些零碎的时间学习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进行切换。 (more…)

8,484 views

有一段非常非常非常简单的网络编程代码,C语言,C/S模式,相信每一个学习C语言网络编程的人都写过,正因为特别简单,所以发生错误时第一反应并不是我的代码错了,而是系统的BUG! 事实证明,这种想法真是 too young, too simple, sometime naive !

无论是系统调用还是库函数代码,全世界那么多人在用,经过这么多年的千锤百炼,发生错误的可能性是很小的,大多时候都是自己的粗心大意。本次乌龙事件最后查明的原因是传给recvfrom函数的最后一个参数 addrlen没有被初始化。

事情是这样的,一个非常简单的客户/服务器程序。
第一次运行 ./server 和 ./client 127.0.0.1 , 当client发送数据的时候,server收到了,但是显示client的IP地址是错误的,因为是错误的IP地址,所以server把回送的数据报发给了错误的地址,client当然就收不到了。

(more…)

42,410 views

以前看到过一个很文艺的话:“要么旅行要么读书,身体或者是心灵,总有一个需要在路上”,平时工作学习太累了,那么乘着假期风和日丽的好天气,环太湖挑战一下吧!

骑行路线从江苏吴江出发,顺时针环太湖一圈,下图是总路线。

(more…)

Tags: . 27,884 views

简单回顾一下OpenStack三大组件的用途:

OpenStack Compute (Nova),为云组织的控制器,它提供一个工具来部署云,包括运行实例、管理网络以及控制用户等等。
OpenStack Object Storage (Swift),是一个可扩展的对象存储系统。
OpenStack Image Service (Glance),是一个虚拟机镜像的存储、查询和检索系统。

(more…)

Tags: . 20,745 views

OpenStack Object Storage(Swift)是OpenStack开源云计算项目的子项目之一, 是整个OpenStack项目的一个模块。

Swift最适合的就是永久类型的静态数据的长期存储。
比如虚拟机的镜像啦,文档的备份啦,还有陈老师、李老师的艺术作品啦之类的。

先来熟悉一下Swift中的几个概念:
Account
出于访问安全性考虑,使用Swift系统,每个用户必须有一个账号(Account)。只有通过Swift验证的账号才能访问Swift系统中的数据。提供账号验证的节点被称为Account Server。Swift中由Swauth提供账号权限认证服务。用户通过账号验证后将获得一个验证字符串(authentication token.),后续的每次数据访问操作都需要传递这个字符串。

Container
Swift中的container可以类比Windows操作系统中的文件夹或者Unix类操作系统中的目录,用于组织管理数据,所不同的是container不能嵌套。数据都以Object的形式存放在container中

(more…)

Tags: . 221,707 views

I think it is the time to come back.

8,590 views

Linux Kernel实现的链表与众不同,大多数人所熟悉的方式应该是在“链表中包含结构体”,而Linux内核的实现方式则是所谓的“结构体中包含链表”。这样的说法听起来很玄乎,不如给出具体的定义和实例。

1 struct list_head {
2    struct list_head *next, *prev;
3 };

这就是内核代码中Linked List的结构体定义,从list_head定义可以看出,内核的链表是循环链表。我们可以这么用它:

(more…)

11,927 views

工欲善其事,必先利其器。
首先需要安装一下额外的工具包,一个是 libc6-dbg,这是带有debug symbol信息的 libc.so;另一个是libc6-dev,这是glibc的源代码,获取之后我们就可以在gdb中查看代码了。

在Ubuntu/Debian 系统上,我们可以通过以下2条命令获得: (more…)

Tags: ,. 22,040 views

本来没想现在去找实习的,不过既然腾讯来了,就去打一次酱油吧。这算是我第一次参加正式的招聘吧,虽然是实习生的,但是也有必要写篇博客记录一下。

1、流水帐
2、总结 (more…)

18,260 views

要求:模拟一个缓存管理器。给出的测试文件中包含50万个页面请求,每一行用(X,Y)表示,其中X=1表示对页面号为Y的页面写操作,X=0表示对页面号为Y的页面读操作。例如  0,6558     1,3024  等。
规定:磁盘上的页面大小等于Buffer的一个块大小,为4KB;磁盘上的数据库文件data.dbf包含5000个页面,缓冲区有1024个Buffer。设计一个缓存管理器,并统计页面请求的命中和不命中次数。

先说下我的思路,如图,问题牵涉到下面三个部分的协同工作,其中省略了磁盘的读写部分。

解释一下图中的各个部分:
1、Buffer的每一个块4KB,等于磁盘中的数据文件一页的大小,不同的是文件data.dbf有5000页,约193MB,Buffer只有1024块,因此不可能把文件全部加载到缓存中,所以需要有一种合适置换策略,尽量让访问最多的页面驻留在Buffer中,这样可以减少去磁盘读取的次数。

2、Buffer中的每一块都有一个相应的控制结构BCB,BCB详细的记录Buffer中块号(Frame ID)和这一块在文件中所对应的页面号(Page ID)。

3、先说Hash Table,然后再说Table。所有的BCB都散列在Hash Table中,对于每一个页面请求,先使用hash函数将请求的页面号(Page ID)定位到对应的bucket内,在bucket内是一串BCB组成的链表,逐个比较BCB结构内的页面号,如果有与所请求的页面相等的,则说明该页面在Buffer中,直接返回;如果没有搜索到,则说明该页面不再Buffer内,需要去data.dbf文件中将该页面读入,并且在Buffer中选择一个最久没有使用的块,将它的位置让给新的页面。

4、Table就是保存Buffer中每个块所对应的Page ID以及最近一次访问的时间,根据Table的内容,我们可以找出一个最久没有使用的块。

很显然的,如何有效的管理Table,使得我们可以高效的找出一个被替换出Buffer的牺牲页,是至关重要的。

如何来找呢?
老师给的实验参考上说要用LRU算法,因此我最先想到的是以引用时间为关键字,建立一个小根堆,一旦某一个页面被访问,立即更新它的引用时间,这样堆顶元素就是最久没有使用的块了。于是我写好了堆的算法,但是发现了一个致命的弱点:由于页面请求是随机的,因此无法根据请求的页面ID在堆中快速的找到相应的Page ID是在第几个位置(因为堆中元素是在不断调整的),除非逐个搜索,但是这样就变成线性查找了,失去了本来用堆的目的,因此放弃。用链表法?显然查找最小的时间的复杂度也是O(n)。

然后尝试使用FIFO,但是牵涉到是队列的调整(因为某个页面已经在队列中,这时它又被访问了,它的位置并不一定在队头,那么需要将它从队列中取出放到队尾,取出后其他元素也要前移,所以它的复杂度并不比线性查找要好。

之后,想到的是将Table与Buffer一一对应,即Table[1]记录Buffer[1]储存的是哪一个Page,已经访问的时间,但要寻找最小的时间时,遍历整个Table找到最小,时间复杂度是O(n),这个看似比较费时的操作在现在一般配置的机器上似乎并不慢,于是选择的是这种方法。

当我写好了以后,在CFAN的群里面和几位大牛讨论的时候还提到了一种NRU法,即最近未使用法,不过牵涉到对整个Table周期性的更新引用时间,我目前还没想好具体的做法,也许等写完这篇Blog后可以仔细的思考。
同样,程序的代码放在我的GitHub上,这里是运行结果:

Dave GG说,可以不使用引用时间。
的确,因为现在的计算机执行指令的速度超乎想象,在2次更新引用时间之间,即使是gettimeofday()函数取得微秒级的时间,也有可能是一样的,但是有没有什么更好的方法呢?用计数器似乎还有一个溢出的问题。

纸上得来终觉浅,绝知此事要躬行。确实是这样的,每一次写这样的程序都会有很多收获,也有更多疑惑,会发现很多跟书上讲的不一致的东西。不知道真正的数据库里是用的什么替换算法?是怎么实现的?操作系统里真正又是用的什么置换算法?又是怎么实现的?

9,332 views