今天到公司比较早,其他同事都还没来,就随手打开网页上上网,习惯性的在浏览器地址栏输入几个字母,突然在自动补全最下面看到了一个久违的网站—— CFan BBS。回想起来我大概有一年没有登录过这个网站了吧,幸好浏览器自动保存了账号密码,赶紧登录一下,逛了逛这个对现在的我来说熟悉又陌生的地方。

大概是在高中注册的账号,这个论坛陪伴我度过了大一、大二几乎所有的课余时光,那个时候的校园网特别慢,我当时是办的校外的电信网,一个月好像是90还是120个小时的样子,宝贵的上网时间得计划着用,那个时候每天下了晚自习回到宿舍,打开电脑登录论坛灌灌水,有的时候第一天发了帖子问问题,第二天便会迫不及待的登录论坛看看谁给我回复了,也因此结识了一帮共同爱好的朋友;有时候也为在论坛上学了点新知识而沾沾自喜。可以说每天上网的时候是我最开心的时候,而CFan论坛也成了我获取计算机知识一个重要的地方。同一时期网上也有很多其他的技术论坛,但是我偏偏只在这儿安家了,为什么呢? 我也说不清楚。

当年的编程技术讨论区还是比较火热的,如今人走茶凉,荒草丛生,连每月一次的精华帖依然停留在2011年,我对CFan编程版的记忆也停留在2011年,那一年,哥大学毕业。

虽然高中也捣鼓过程序,但走的是野路子。刚进大学的时候我对编程一知半解,编程语言、算法、数据结构对我来说都是全新的东西。大学为我打开了一扇门,让我知道了学编程要学这么多东西,而路要自己去探索,这也许就是大学的意义所在。翻一翻我曾经发过的帖子,现在看来真的很幼稚,代码写的乱七八糟也非常自信的发到论坛,还被加了精华,要是哪天某个好事者把我发的帖子扒出来黑我的话,脸都不知道往哪搁。但就是凭着这份初生牛犊不怕死的精神,经常在论坛里灌水,因此结识了一帮好友,也充实了大学的课余时光。试想一下,与其在宿舍和同学打游戏看黄片,还不如在论坛发点精华帖来的有意义。

看着我以前发的帖子,虽然幼稚,但是却隐隐约约透过屏幕让我感觉到了那份久违的满腔热血,而这份满腔热血正是我渐渐被时间所磨灭的东西。几天前,我在18摸实习时认识的内核大神 Xiao Guangrong 也重新开张了他的博客,在新博客中他写道“路漫漫其修远兮,吾将上下而求索”,大神都如此,我等更应当加倍努力。

我是一个意志力薄弱的人,经常给自己定了目标最后又不了了之,所以有必要把一些思绪记录下来,提醒自己不忘初心。

44 views

博客荒废了很久,从现在开始要好好写博客了,思绪来得快走的也快,不记录下来就没了。
好在现在工作定下了,以后上班下班按部就班,目标要在技术上有所成长,毕竟年纪也不小了。

668 views

如何把一个已排序的数组(或者单链表)转化成一个BST ?

最简单最容易想到的方法是每次取中间的节点作为 root,把数组/链表分成左右子树,然后递归。

(more…)

503 views

深度优先搜索一般用递归的方法实现,但是怎么写好一个递归程序对于我来说挺难的。
每隔一段时间写又会犯各种错误,思绪来得快也走得快,有必要记录一下。

首先用一个问题来引出 DFS:给定一个字符串,要求用空格来分割,生成它的所有可能的分割方法。
比如给定 “abc”, 那么可能的分割是
“a” “b” “c”
或者 “ab” “c”
或者 “a” “bc”

这些题目都是给一个字符串,生成符合题意要求的分割后的结果。 既然解法类似,那么代码肯定也是类似了,只是会多加一些判断条件。

我们先回到一开始的问题:如何生成所有可能的分割?
(more…)

3,742 views

如果你稍微了解过Linux内核的内存管理,那么对内存分区的概念一定不陌生,Linux内核把物理内存分成了3个区,
0 – 16M 为ZONE_DMA区,
16M – 896M 为ZONE_NORMAL区,
高于896M 为ZONE_HIGHMEM区

我没有去考证过为什么要取896这个数字,但是可以肯定的是这样的划分在当时看来是合理的,然而计算机行业的发展今非昔比,现在4G的物理内存已经成为PC的标配了,CPU也进入了64位时代,很多事情都发生着改变。 (more…)

12,024 views

貌似2013年写的技术文章只有个位数,实在是不应该啊! 最近几天看了些Linux Kernel的内存管理,就写点东西吧。

我们知道Linux内核内存管理最底层的是伙伴系统,伙伴系统解决是的内存外碎片问题,而不能解决内碎片问题,因此在伙伴系统之上,有Slub/Slab/Slob 三种内存分配策略(有的书上叫高速缓存,我个人很不喜欢这个名字,因为很容易与硬件的高速缓存TLB混淆),不过内核同时只能使用这三种中的一种,Slub 是现在内核默认的选项,无论是我们安装在自己电脑上的Linux系统,还是运行在服务器上的系统,都是用的Slub; Slab 作为鼻祖曾经辉煌一时,现在退居二线了; Slob 则是主要用于内存非常小的嵌入式系统,只有在编译内核的时候配置了 Embedded System 选项,才可以选择使用Slob。

(more…)

12,671 views

再不更新真的是太对不起观众了。

整个六月、七月都非常的忙碌。首先是在IBM实习的时候,组内给我分配了一个任务,即为perf添加对Power7 的PMU事件名称的支持,Power7支持多达500多个事件,所以我需要在内核源码里面添加500多项(行)。单从数量上来说这个改动还是蛮大的(实际上只是重复的体力劳动啦 ^_^),如果我能完成了这个patch并且被接受的话,就能在Linux Kernel源码里面留下我的大名了。

没过多久我就完成了第一版,经过组内的内部review后发到社区,收到反馈以后改,然后再发,直到发到v4,差不多结束了,接下来就是等待patch被merge到一级一级的分支中去,最终并入主线内核。中间还有几个小插曲:社区的某个人对这个patch提出质疑,认为不应该加入到内核,而应该放在用户态,然后IBM在澳大利亚的一个搞Power的大牛出来争论,甚至最后还用了F开头的单词,最终也就这么不了了之了。这些都是后话,如果有时间我将在以后的博客里面介绍。

patch的链接在这里

(more…)

16,696 views

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

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

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

(more…)

Tags: . 7,794 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: ,. 21,130 views

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

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

Tags: ,. 28,009 views

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

20,544 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…)

8,818 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…)

7,443 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…)

40,059 views

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

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

(more…)

Tags: . 26,428 views