Archive for the ‘Code杂谈’ category

setjmp和longjmp的另类使用

February 3rd, 2016

C语言的运行控制模型,是一个基于栈结构的指令执行序列,表现出来就是call/return: call调用一个函数,然后return从 一个函数返回。在这种运行控制模型中,每个函数调用都会对应着一个栈帧,其中保存了这个函数的参数、返回值地址、局部变量以及控制信息等内容。当调用一个 函数时,系统会创建一个对应的栈帧压入栈中,而从一个函数返回时,则系统会将该函数对应的栈帧从栈顶退出。正常的函数跳转就是这样从栈顶一个一个栈帧逐级地返回。

setjmp的返回值:直接调用该函数,则返回0;若由longjmp的调用,导致setjmp被调用,则返回val(longjmp的第二个参数)。

之前看APEU的相关章节,setjmp和longjmp只是一个跨函数跳转的库函数调用,可以作为后悔药使用,但是今天我发现这个库函数可以作为协程使用。协程我之前一直不理解,认为有了进程线程就可以了,没有必要存在协程,但是发现在不支持这些多线程多进程的操作系统平台上协程意义重大。

这个时候协程就可以派上用场了,我们可以依赖协程模拟多进程这种需求,我们需要写一个thread库供协程调用,具体的thread工作步骤就是:

  1. 存储当前线程所在上下文,设置一个存储队列专门存储thread context
  2. 为每个线程分配一个stack空间
  3. 将esp指向栈顶,eip指向要执行代码的entry,当然包括参数arg,arg具体调用方式就是(current->entry(current->arg)),这一个非常相似于c++中的委托
  4. 当需要调度线程时,将当前执行代码设置setjmp,保存线程结构体中的thread context到具体全局的数组
  5. 如果需要调度另外一个线程,使用longjmp跳入到线程结构thread context

当然了在linux下有glibc提供相关库函数实现跳转,咱们不必再次造轮子,但是在裸机上,或者一种新的体系结构中,我们必须自行实现setjmp和longjmp,这其中不可避免的会使用到asm。比如setjmp,首先要将返回地址和frame pointer压入栈,考虑到栈自高地址向低地址方向生长,故esp-8,然后再压入其他通用寄存器。而longjmp恢复某个线程·的上下文环境,必须指定存储context位置 ,然后将返回地址复制给eax,然后执行跳转。

struct jmp_buf
{
       unsigned j_sp;  // 堆栈指针寄存器
       unsigned j_ss;  // 堆栈段
       unsigned j_flag;  // 标志寄存器
       unsigned j_cs;  // 代码段
       unsigned eip;  // 指令指针寄存器
       unsigned ebp; // 基址指针
       unsigned edi;  // 目的指针
       unsigned j_es; // 附加段
       unsigned j_si;  // 源变址
       unsigned j_ds; // 数据段
};

具体线程切换伪代码:

void wthread_yield()
{
   ...
   if(current){
        if(setjmp(current->...)!=0)
             return;
        push(...)
   }
   current = next;
   longjmp(current->...)
}

考虑到执行setjmp和longjmp必须是一个控制main线程,必须由控制线程控制调用线程切换,其他线程可以主动让出时间片。这时我们必须定义一个全局变量保存线程上下文,然后维护这个数组,至于具体的逻辑形式可以是队列可以是环形队列队列等。编写thread库务必保证线程安全,不能破坏线程返回地址,否则容易core dump。

另外在linux下,可以使用这两个系统调用实现C下的异常处理try/catch,至于在setjmp和longjmp之前存在的变量务必使用volatile声明。

 

 参考:

http://stackoverflow.com/questions/2560792/multitasking-using-setjmp-longjmp#comment33335405_2560792
http://www.cnblogs.com/lq0729/archive/2011/10/23/2222117.html
http://www.cnblogs.com/lienhua34/archive/2012/04/22/2464859.html

gnuplot 尝鲜

January 12th, 2016

gnuplot是一款画图软件,可以将数据以一定的方式显示在坐标系中,可以生成二维三维的数据分布。我们依赖这种数据可视化做到对于数据的分析。在各种操作系统性能分析中,该工具也占有举足轻重的位置。这篇文章默认你已经懂得了gnuplot基本操作,我们试着将数据集以可视化的方式表现出来。

在linux终端下,输入gnuplot,可以直接进入到该软件操作界面下:

➜  Desktop  gnuplot         

	G N U P L O T
	Version 5.0 patchlevel 0    last modified 2015-01-01 

	Copyright (C) 1986-1993, 1998, 2004, 2007-2015
	Thomas Williams, Colin Kelley and many others

	gnuplot home:     http://www.gnuplot.info
	faq, bugs, etc:   type "help FAQ"
	immediate help:   type "help"  (plot window: hit 'h')

Terminal type set to 'qt'
gnuplot> 

一般情况下,我们可以在命令行中断直接一步一步设置我们需要设置的图像,但是这里我们直接使用bash脚本方式生成图像,其中脚本模板如下:

#!/bin/bash
gnuplot<<FFF
...

FFF
exit 0

中间省略号的部分就是我们在命令行中输入的,比如set terminal png truecolor 就是设置gnuplot因该采用什么样的格式;set autoscale代表让gnuplot自己计算x轴y轴范围。如果x轴是特殊的数值,比如时间那么使用%d %n %y

set xdata time
set timefmt "%H:%M:%S"

来定义x轴数据格式

如果我们在一个二维坐标系中画多条折线图,有两种方式,我们可以在每个文件中定义一条折线的坐标值。然后使用下面这种方式,一个filename对应一条折线,title是关键字,代表折线名字,with也是关键字,代表图的类型,这里是表示由线组成的点,pointtype 4表示用空心方块中重点标示每个点。你可以修改后面的数字,这样会得到不同的线型。

plot 'filename' title 'Sequential Read' with linespoints pointtype 4,'filename2' title '...' with linespoints pointtype 4

第二种也是一种方式,但是我不太常用。第二种方式主要把每个filename中的数据都放在同一个文件中,每一列数据代表一组线,他们的纵坐标都是同第一列。每一列数据中间用空格分离,使用using 关键字。比如using 1:2,表示使用第1列作为x轴,绘制第2列数据。

plot 'test.log' using 1:2 title "line 1",using 1:3 title "line 2"

如果对图像要求比较高,还可以设置网格 set grid;设置x轴y轴范围set xrange [“13:00:00″:”17:00:00”] set yrange[“…”:”…”]设置x轴y轴标签 set xlabel “…” set ylabel “…”

以上都是折线图,下面我们来尝试画一个柱状图:

对于柱状图,其实只需要设置set style data histograms 就可以生成图形,但是我们必须对图形进行微调。gnuplot 按以下次序绘制框的边框:顶、底、左和右,值分别为 1、2、4、8。要想删除一条或多条边框线,只需提供相应值的和。在这个示例中,使用 -1 选项删除底部边框线。指定 fill 选项就会用默认颜色填充框:

set style fill solid 1.00 border -1

对于 x 坐标,这里不使用时间,而是使用组名称。使用 xtic 选项让 gnuplot 沿着 x 轴放置 tic 和数据标签(第 1 列)。在这里就是组名称。但是,有时候标签包含许多字符,或者 xtic 的时间格式在图形上的 tic 之间放不下。这时就会看到标签相互重叠。为了避免这个问题,把标签旋转 90 度(通过试验找到合适的角度),让它们垂直显示。可以使用以下命令来实现这种效果:

set xtic rotate by 90

其中这个90度可以为负。

第 2 列中的数据使用第 1 列(x 数据)作为参照:

2:xtic (1)

最后生成的柱状图是:

static

如果多个柱状图为一个x轴为参考点,那么可以使用

plot "disk.txt"  using 2:xtic(1) title "Oct-09 data growth(gb)", '' using 3 title "Nov-09 data growth(gb)", '' using 4 title "Dec-09 data growth(gb)"

diskimage

参考:

gnuplot 入门教程1   : http://blog.csdn.net/liyuanbhu/article/details/8502383

gnuplot 入门教程2   : http://blog.csdn.net/liyuanbhu/article/details/8502418

 gnuplot 入门教程3   : http://blog.csdn.net/liyuanbhu/article/details/8502450

gnuplot 入门教程4   : http://blog.csdn.net/liyuanbhu/article/details/8502461

gnuplot 让您的数据可视化  : http://www.ibm.com/developerworks/cn/linux/l-gnuplot/index.html

 使用 gnuplot 在网页中显示数据   : http://www.ibm.com/developerworks/cn/aix/library/au-gnuplot/index.html

浅谈APIC timer

January 9th, 2016

最近在写毕业论文,博客比较荒废,下面我们来谈一下APIC timer吧。

因为我的毕业论文涉及benchmark,所以测试性能与时间紧密相关,我必须调整操作系统的时钟频率,操作本身计时器不够精确,所以必须手动调整Local APIC时钟触发时间中断间隔(每秒触发多少时间中断)。硬件实现上每个Local APIC连接一个CPU core。

所以在编写APIC timer驱动的时候,提供了2-3种模式来实现,第一种和第二种分别是周期模式和one-shot模式,被所有的Local APIC支持,第三种叫TSC-Deadline mode,是最近的CPU型号支持,比如在MCA的君主模式中,我看到时间戳通常使用第三种定时器模式。

周期模式

驱动可以通过设置初始count值作为发生时间中断的依据,每当这个count值减为0,就会产生一次timer IRQ,然后重新设置为初始count值,重新开始自减,所以这种模式下Local APIC产生中断的间隔取决于初始count值,而自减频率与CPU的外频和步长(divided by the value)相关,步长值存储在“Divide Configuration Register” 寄存器中。

举个例子2.4GHz CPU拥有外频800MHZ,如果步长为4,初始count值为123456,那么Local APIC将以200MHZ的速率自减couns值,每个timer IRQ中断间隔为617.28us,时间中断频率则是1620.01Hz。

one-shot模式

这个模式和周期模式很类似,不同的是他不会重置初始count值,也就是说驱动必须亲自重置这个count值,如果内核想要更多的IRQ中断。这种模式的优势是驱动可以更加精确地控制timer IRQ的产生。举个例子,内核切换进程时可以依赖新进程的优先级(Priority),这样可以动态改变IRQ时钟频率。一些内核可以使用这种方式实现更加精确地timer服务。

比如当前运行的进程应该抢先1234纳秒,而同时一个睡眠进程要在333纳秒后醒来,时间中断将会在44444纳秒后到来。那么初始count值可以设置为333纳秒,那是内核发生Timer IRQ,内核知道当前进程还有901纳秒被调度,同时下次Timer IRQ将在441111纳秒后到来。

这种模式的缺点在于很难跟踪实时进程,并且需要避免竞争条件,特别是新的count值在旧count值结束前被设置。

TSC-Deadline 模式

这种模式和前两种完全不同,他不是使用外频/总线频率降低count数值,而是通过软件设置deadline,当CPU时间戳计数大于deadline时,Local APIC产生timer IRQ。这种方式相比one-shot模式,Timer IRQ可以有更高的精度,因为时间戳是以CPU主频的方式自增,这个明显高于外频,也避免了竞争条件。

 

参考:

http://wiki.osdev.org/APIC_timer

http://www.cs.columbia.edu/~junfeng/11sp-w4118/lectures/trap.pdf

使用git生成patch文件

November 29th, 2015

经过两个月的奋战,我的找工作之旅告于段落,博客也荒废了,现在开始逐渐更新…

之前与CRIU团队交流的时候,团队成员发给我一个patch,让我打在git master分支上,直接使用。我当时还没有意识到可以使用git am命令,傻乎乎的使用patch < 操作patch,费力不讨好。。。

$git am -3 -i xxx.patch
Commit Body is:
--------------------------
commit message....
--------------------------
Apply? [y]es/[n]o/[e]dit/[v]iew patch/[a]ccept all  y
applied: commit message....

但是这个文件文件是如何生成的呢?其实也非常简单,只需要使用git format-patch 命令即可生成,其中 -1 就是以HEAD指针为基准的几个commit提交打成patch,非常类似于HEAD^ 或者是HEAD^^:

$git format-patch -1

这个时候在git目录下,生成0001-commit-message.patch类型的patch,如果使用vim打开看的话,可以发现除了常规的patch文件,还存在git commit 信息,这些信息比起单纯的diff命令多了一些内容,可以被合并到git分支中。

如果我们使用git am 合并失败的话,会进入单步执行模式如果我们要退出这次合并,直接使用git am –abord,然后就可以再次使用git am进行合并。如果我们没有退出这个模式,再次使用am合并,会出现下面的错误提示信息,在.git/rebase-apply/ 中存在文件,如果am成功,则这个文件不存在。

.git/rebase-apply still exists but mbox given.

如果你发现这个冲突是无法解决的, 要撤销整个am的东西。 可以运行git am –abort,如果你想只是忽略这一个patch,可以运行git am –skip来跳过这个patch.

 

 

参考:

http://blog.csdn.net/xzongyuan/article/details/9425739
http://blog.csdn.net/wh_19910525/article/details/19416857

Documentation/SubmittingPatches

DRAM页映射到BANK中的两种形式

July 4th, 2015

在之前的一篇博文上,我分析了DRAM的物理结构与从bank中存取数据的方式。这里我继续这个话题,并引入一种新式的内存存取数据的方式:Permutation-based Page Interleaving。

当CPU发送物理内存地址给内存的时候需要首先发送给memory controller,然后由memory controller将其翻译成内存地址,也就是以DIMM Rank Chip Bank为单位的地址形式,如下图所示:20150421162433 我们知道CPU对Memory的读写要经过cache,在这里可以认为CPU与cache是一体的,读到了cache也就等于被CPU使用。传统的memory与cache的关系是多路并联、单路并联,也就是说一系列的内存物理地址,被分割成了tag段,每个tag段内的每个内存地址映射到不同cache line中。

cache-related

也就是说不同tag段的相同set index会被映射到同一个cache line中,而最后的block offset正是cache line的大小,也就是说这个物理地址中的内容放到cache line中正是cache line的大小,然后我们将这个位数变化一下,就是传统物理地址对应三个部分,page index,bank index,page offset。而其中bank index的信息是具体的硬件实现(硬件生产商不会对外公布这种参数),一般我们使用软件的方式来测试bank位!

这里的page不是我们常规意义上的物理页,而是第一个图中以bank 与row组成的一行称为page。

下面我们来做一个推定:比如tag值不同,后面set index,block offset两个字段相同的两个物理地址,必定映射同一个cache line。转换到下面的DRAM的页模式,set index相同,那么bank index一定相同,也就是说两个数据处于同一个bank中,又因为tag不同,那么page index不同,意味着不属于同一个row,而每个bank只有一个row buffer,这样必然导致L3(CPU最后一级cache)无法命中,导致 L3 cache conflict miss!

举例:

double x[T], y[T], sum;
for(i = 0; i < T; i++);
     sum += x[i] * y[i];

若x[0] 和y[0] 的距离是L3 cache 大小的倍数,必然会导致读取x[i],y[i]发生L3 cache conflict miss!CPU不得不每次讲L3 cache清空,读取新的数据,这样必然大大增加了数据访问的延迟!

为了避免这种情况工程师提出了一种新的内存page交叉访问方式Permutation-based Page Interleaving Scheme,首先我们看这个算法如何降低了 L3 cache conflict miss。

permutation

 

他在传统物理地址对应的banks存取上,使用tag的一些位与bank index做异或运算,这样就可以大大降低内存页交叉访问带来的L3 conflict miss,不同tag的相同bank index会被映射到不同的bank中!

DRAM

而我们知道每个bank都有一个row buffer,只要我们保证程序局部性存取的数据在不同row buffer中,这样就意味着row buffer的数据可以长时间存在,不同频繁的清空,当需要这些数据,直接从row buffer中读取到memory controller就可以了。而程序的局部性并没有被破坏,仍然存在在一个DRAM page!

DRAM_bank

 

这两种方式长时间存在于DRAM交叉存取bank中,有时候我们在测试Bank位会遇到这两种方式,因此我们必须使用特定工具去检测决定bank位的index,如过检测bank index非常多,就要考虑是否是XOR交叉存取方式了!

 

 

论文:http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=898056