CSK.Blog--个人原创Weblog

intel x86提供的Branch Trace Store的功能

写给转载者:

转载请保留作者信息

来源: http://www.csksoft.net/blog

作者:陈士凯

介绍

Branch Trace Store(BTS)是目前广泛被intel CPU所提供的一种硬件辅助调试功能,因为在MSRA项目需要,所以作了一些基于它的应用。虽然Intel的CPU开发手册[1]提供了比较详细的使用方法,但是由于比较笼统,且缺少win32下的相关资料。所以我打算把其中的一些tricky的事情和大家分享下。这些内容当然也是我自己查找公开资料得到的,因此也不算什么秘密吧 :-)

 

BTS简单的说就是允许CPU将自己实际执行到的分支指令(jmp/jxx/call/int/etc.)的相关信息保存下来的功能。一般CPU都会保存每个分支指令的源地址和目标地址,该地址在保护模式下是虚拟地址形式表示的。利用这个功能,可以实时地了解当前CPU正在执行代码的实际流程情况,很多分析软件,如Intel的Vtune或者profiling库,如*nix平台下的perfmon[2]都用它来做一些程序性能分析。当然,还可以做很多其他有趣的事,比如逆向工程,具体我就不说了。

 

不过目前很少有资料具体介绍如何在win32下开启该功能并实现一个可用的BTS捕捉引擎。当然可以参考perfmon的代码,但BTS在其中只是很小一个部分,同时为了实现跨平台,对于新手来说难度较大。因此我这里重点介绍对于单核心的NetBurst构架的CPU(通俗地说就是P4这类)在win32下的具体实现细节。其他的构架,比如现在的Core Due,大家可以参考intel的开发手册举一反三。

 

工作框架

实际上,上面所说的BTS只是intel对于分支指令信息捕获机制的一个分支,就P4而言,大致提供了下列几种分支指令的捕获手段

Last Branch Record(LBR)

故名思意,该方式将记录最后几个分支信息,实际上NetBurst CPU中内建了若干个MSR寄存器用于记录Last Branch Record,称为LBR Stack。在该模式下运行的CPU会采用Round Robin的方式循环填充那几个MSR寄存器。

该方式常用在调试器的Call Stack分析上,我们这里就不涉及了

 

Branch Trace Messages

该方式和我们将介绍的Branch Trace Store大致类似,与LBR不同的是,CPU会把分支信息发送到系统总线上供第三方硬件在总线上接收数据。而BTS则直接将数据保存到由程序制定的内存单元中。我们这里也不讨论该方式。

 

Branch Trace Store

简单的说,BTS就是将分支信息保存到了有程序(实际就是我们)制定的一块内存空间中。而当这块内存用尽时,CPU可以采用Round Robin的方式循环填充,这就和LBR类似,但可以指定内存块的大小来决定最大捕捉量。另一种处理方式是在内存快用尽的时候,一个事先由我们设定的处理中断将触发来完成对当前内存块中BTS数据的保存工作。这样就可以记录任意多的分支信息了。我们这里主要考虑的就是这种方式的BTS。

 

 

按照intel开发手册的描述,BTS开启后的CPU执行模式如下图所示:

 

每当CPU执行到一个分支指令后,它就会产生一个如上左图的BTS记录项。这里举个例子:

0x80001234   mov eax,[esp]

0x80001238   or eax,eax

0x80001240   jnz 0x80002000

0x80001245   nop

...

 

当执行上面这段执行,其中遇到了jnz指令,如果他的跳转条件成立,那么将产生一个从0x80001240到0x80002000的跳转,那么产生的BTS记录项就是{From:0x80001240,To:0x80002000,...}

 

对于P4的CPU,这个BTS记录项的结构如下:

struct BTS_ITEM_BLOCK_P4{
    ULONG   dwBranchFrom;
    ULONG   dwBranchTo;
    ULONG   dwFlags;
};

每次CPU执行到分支指令的时候,只要BTS开启,它就会产生一个如上结构得数据块,然后把它存储到事先定义好的一块内存当中去。而这块内存是比较灵活的,如上图所示,CPU需要知道这块内存的起始地址、结束地址、以及当记录到第几个记录时候需要触发一个中断程序来负责将现有的BTS记录保存下来防止内存溢出。当BTS记录存储到图中那个灰底色的“BTS记录#m”时,就会触发中断,可以发现它往往并不是整块记录内存的末端,具体原因就不解释了。

 

为了让CPU知道我们设置的内存空间的信息,需要提供一个叫做DS_BUFFER_MGR_BLOCK的结构来描述这块内存,他包括的内容如图所示,然后我们需要设置一个名为IA32_DS_AREA的MSR寄存器来指向这个DS_BUFFER_MGR_BLOCK数据的地址。

 

P4下DS_BUFFER_MGR_BLOCK的完整结构是:

struct DS_BUFFER_MGR_BLOCK_P4{
    PVOID   pBTSBufferBase;
    PVOID   pBTSBufferIndex;
    PVOID   pBTSMaxSize;
    PVOID   pBTSIntThresold;
    PVOID   pPEBSBufferBase;
    PVOID   pPEBSIndex;
    PVOID   pPEBSMaxSize;
    PVOID   pPEBSIntThresold;
    ULONG   dwPEBSCounterReset;
    ULONG   Reserved;
};

 

注意上面黑体的条目,这些部分是BTS需要设置的,后面的是PEBS采用机制所需要的信息,这里我们忽略他们。这些条目需要设置成保存BTS内存的相关地址(虚拟内存地址)。

 

同时,还需要让CPU知道用于处理BTS溢出的中断号。目前的Local APIC控制器上有一个称为Performance Mon. Counter的寄存器项。当BTS记录项接近溢出时,就会通过这个记录项中存储的中断向量值去触发对应的中断程序。这个Performance Mon. Counter的格式如下图所示(图片来自intel手册):

由于APIC芯片寄存器映射到了物理内存空间0xFEE00000H处,因此,对于其中寄存器的读写操作可以像标准内存操作那样进行。不过,由于采用虚拟内存的操作系统环境下,需要将该空间映射到对应的虚拟内存地址下,同时要避免操作系统的缓存行为。该部分细节我会在后面介绍。对于APIC芯片和LVT的一些具体细节可以参考intel手册[3]。

 

以上便是整个BTS工作的框架,如果不考虑具体的操作系统环境,对于他们的设置不存在很大的难度。不过由于OS引入了各类抽象机制或者保护手段,所以有一些tricky的问题需要处理。下面我讲介绍一个具体的实现流程。

Win32下BTS机制的开启和相关框架

经过上面的分析,对于Win32下进行BTS捕捉,需要进行如下的操作

  1. 初始化用于存放BTS记录的内存空间
  2. 设置对于上述内存空间的描述信息,即DS_BUFFER_MGR_BLOCK,并将其地址值写入IA32_DS_AREA MSR寄存器
  3. 编写处理BTS溢出操作的中断服务程序,并在IDT表中设立表项,创建一个中断服务
  4. 设置Local APIC的Performance mon. Counter项,指向上述IDT表中我们创建的中断项
  5. 通过对专门的MSR寄存器读写开启BTS功能

下面我就每个过程的关键问题具体展开介绍,同时给出些示例代码(不保证能运行)。同时,因为涉及到了底层的硬件控制,这里的代码自然就是在Kernel模式下执行的,如果对WinDDK的开发不熟悉,可以先参考相关文献。

 

初始化用于存放BTS记录的内存空间

这部分就不具体介绍了,直接可以使用内核的ExAllocatePool来分配内存单元,需要注意的是,对所分配的内存必须位于系统的Nonpage pool中。在这里假设所创建的内存空间用符号pBtsBuffer表示:

BTS_ITEM_BLOCK_P4 *pBtsBuffer;

 

设置DS_BUFFER_MGR_BLOCK

对于DS_BUFFER_MGR_BLOCK的设置只需要关注BTS部分,假设已经分配了2000个BTS记录的内存空间,且希望当记录到第1900项时触发中断,那么初始化代码可以是:

DS_BUFFER_MGR_BLOCK *pDSBlk = <some allocating code>;

pDSBlk->pBTSBufferBase = pBtsBuffer;
pDSBlk->pBTSBufferIndex =  pDSBlk->pBTSBufferBase;

pDSBlk->pBTSMaxSize = &pBtsBuffer[2000];
pDSBlk->pBTSIntThresold = &pBtsBuffer[1900];

在设置好了数据后,就要将DS_BUFFER_MGR_BLOCK的地址写入IA32_DS_AREA :

        mov ecx,IA32_DS_AREA
        mov eax, pDSBlk
        WRMSR

其中, IA32_DS_AREA为值:0x600

 

编写BTS溢出处理中断服务程序

在Windows下添加中断处理程序的具体方式这里就不介绍了,可以参照Undocumented Windows NT[4]。这里需要注意几个问题:

  1. 在进入中断后以关闭BTS为宜
  2. 在中断退出前,需要设置pDSBlk->pBTSBufferIndex到初始状态,即pDSBlk->pBTSBufferIndex =  pDSBlk->pBTSBufferBase;
  3. 当BTS中断触发后,CPU将在Local APCI中的Performance Mon. Counter寄存器项上打开屏蔽位,从而阻止对中断的二次触发,所以需要在中断结束前关闭该屏蔽位
  4. 给APIC发送EOI命令,通知该中断结束服务

 对于BTS的开关操作,将在后续介绍。对于清除Performance Mon. Counter寄存器的屏蔽位,可以通过简单的对其进行重设达到效果,因此可以参考后面介绍的方法。

下面给出一个简单的中断处理过程代码:

 

void __declspec( naked )    BTS_handler(void)

     //保存当前线程状态,恢复内核模式相关寄存器
     __asm
    {  
        cli
        pushad
        pushfd
        push fs
        push ds
        push es
        push gs

        mov     ebx,0x30
        mov     eax,0x23
        mov     fs,bx
        mov     ds,ax
        mov     es,ax
    }
    //关闭BTS,具体见后文
    __asm{
        mov ecx,MSR_DEBUGCTL
        RDMSR
        mov tmp_old_msr_bts,eax
        xor eax,eax
        WRMSR
    }
    //相关操作,如保存BTS到磁盘
   
    //结束中断处理--------------------------------------
    pDSBlk->pBTSBufferIndex =  pDSBlk->pBTSBufferBase; //重设BTS记录指针
   
    //开启BTS,具体见后文
    __asm
    {
        //restore BTS
        mov ecx,MSR_DEBUGCTL
        mov eax,tmp_old_msr_bts
        WRMSR
    }
    //清除local apic中preformance mon. counter的屏蔽位,具体间后文
    local_apic->lvt_pc.mask=0;
    //发送eoi指令字
    local_apic->eoi.eoi = 0;
   
    //恢复当前线程环境
    __asm{
        sti
        pop gs
        pop es
        pop ds
        pop fs
        popfd
        popad
        iretd      
    }
}

 

其中,对于BTS的开启关闭,将在后文介绍。这里主要讨论对于local apic的操作。在前一章中已经知道,pc中将该芯片的寄存器映射到了物理地址的0xFEE00000H处。而按照Microsoft Windows Internals[5]中的描述,该地址在windows中被映射到了虚拟地址:0xFFFFD000H处。

经过我的验证,的确如此,但是估计因为内核的保护机制,对这块映射的内存地址并不能直接操作。首先是对于很多寄存器,比如发送EOI的EOI寄存器,对它的写入操作将导致BSOD。同时,我也发现内核采取了缓存的手段。

这里采用来自Micah Richert[6]的方法。同时感谢他提供的local apic结构声明[7]。不通过windows内核映射的空间,而是直接重新将那块物理地址进行映射:

    PHYSICAL_ADDRESS    pa;

    pa.HighPart = 0;
    pa.LowPart = 0xFEE00000; // 原始物理地址
    local_apic = (PAPIC)MmMapIoSpace(pa,sizeof(APIC), MmNonCached);

注意其中的黑体参数。今后便可以直接操作local_apic 。同时,Micah Richert定义了很完善的local apic寄存器结构,可以直接用结构体定义完成操作。

按照intel手册的描述,在中断完成后需要发送eoi指令,否则该中断将得不到再次触发。具体做法就是给local apic中的eoi寄存器清零。具体代码见上文。

 

安装中断服务程序并设置Performance Mon. Counter 寄存器

 对于中断服务程序的安装(注册)可以参考很多现有的文章,比如[4]。其中,我选用了ID为0x28的中断,因为win32中该中断项往往是闲置的。具体的手段就是修改IDT表,这部分内容这里不再涉及。

在完成中断的安装后,需要设置Performance Mon. Counter 寄存器。比如我设置int 0x28为BTS溢出中断,那么Performance Mon. Counter需要如下设置:

local_apci->lvt_pc = 0x28;

 

BTS功能的开关

对于NetBurst构架下,将通过MSR_DEBUGCTL MSR进行BTS的开关操作,下图为该MSR我们所关心的位:

 

换句话说,我们只需要往该MSR中写入0x1c即可开启BTS。而清零则可关闭。

//开启BTS

        mov ecx,MSR_DEBUGCTL
        mov eax,0x1c
        WRMSR

 

//关闭BTS

        mov ecx,MSR_DEBUGCTL
        xor  eax,eax
        WRMSR

 

其他问题

上述办法仅针对但核心的P4处理器有效。如果面对多核环境或者多处理器环境,需要分别设置每个逻辑处理单元的local apic。同时可能要考虑潜在的竞争情况。

通过上述办法捕捉到的BTS将包含整个系统的分支信息,其中不但混杂着用户态、内核态(甚至虚拟化技术的Hypervisor模式),同时不同线程也将混合在一起。因此对于实用的分析,需要作额外的处理。比如要知道线程切换的信息。这里可以参考Pjf关于线程切换信息的捕获方式[8]。

另一个需要注意的问题是如果直接在中断处理程序中进行对BTS写入文件将严重影响当前线程的执行。同时如果执行在不同的线程上下文中将使得诸如ZwWriteFile等导致系统锁死。

 

小结

经过上述的设置过程,即可实现win32下的BTS功能开启。目前BTS已经广泛的存在intel各系列CPU中。同时也被其他各类CPU所采用。除了目前性能分析软件使用外,BTS对系统分析、逆向工程等均有很大

参考文献

[1] Chapter 18.6, Intel 64 and IA-32 Architectures Software Developer’s Manual, Volume 3B: System Programming Guide, Part 2

[2] perfmon2, the hardware-based performance monitoring interface for Linux, http://perfmon2.sourceforge.net

[3] Chapter 9.4, Intel 64 and IA-32 Architectures Software Developer’s Manual, Volume 3A: System Programming Guide, Part 1
[4] Prasad Dabak, Sandeep Phadke, Milind Borate, Undocumented Windows NT, Chapter 10

[5] Mark E. Russinovich and David A. Solomon, Microsoft Windows Internals, 4th Edition

[6] Micah Richert, http://www.snl.salk.edu/~micah/

[7] Micah Richert, RTInterrupt, http://www.snl.salk.edu/~micah/RTInterrupt/

[8] Pjf, http://www.blogcn.com/user17/pjf/blog/4331410.html

VC编写Demo Scene的一些可能技巧

本来也不是专门为了写这篇文章,只不过觉得已这样的形式发表比较合适。同时好久都没有写过教程了,以往都以简单的发表作品或者通报一些事情为主。总的来说这篇文章还是有点参考价值的,希望能有所帮助。

 

转载注意:

请注明原文出处: http://www.csksoft.net/blog/post/demo_scene_tip1.html

 

Demo Scene我就不想再介绍了,对他还不了解或者听说过但不明白原理和背景的可以参考我以前写的一些文章:

Demo Scene:Principles,Techniques,and Tools (http://www.csksoft.net/blog/post/154.html)

模块音乐(Mod)的制作和使用,Demo程序的主体之一 (http://www.csksoft.net/blog/post/intro2track_music.html)

 

目前国内Demo Scene基本处在0起步的阶段,已经有了一些小团体打算去参加欧洲的比赛,但是还没有一定的规模。同时,对于制作这类程序网上也没有系统的资料。使得制作Demo Scene被看成一种高深的事情。

下面我就说说目前在Windows平台下,使用最常用的开发工具(Visual C++)如何来制作一个符合64kb demo的程序框架和常用技巧。当然这只是一些次要手法,最核心的还是3d引擎、mod音乐的设计。因为那些资料很好找。所以就不再涉及。

 

我将介绍下面几个方面的技术:

 

1.如何产生体积最小的程序

2.如何不使用C运行库开发程序

3.如何实现高速GDI绘图

4.对于NT5.0提供的LayeredWindow的使用--不规则窗体、窗口的AlphaBlend渲染、鼠标事件穿透

5.如何将所有数据(代码、图片等)整合在一个C文件中

6.其他的一些编译技巧

7.一个完整的示例程序代码

问题和需求

Scene Demo中有一个项目为4kb-intro 或者 64kb-intro。 他要求Demo的程序体积必须小于或者正好等于4/64kb。而往往正是这类Demo程序在国内流传最广。因为大家都认为那么小的体积能播放长时间的高品质3d动画和音乐是不可思议得。甚至有人将45分钟的demo动画看成是avi视频,45分钟的音乐算作44KHz采样的wav。计算出将他们压缩到64kb完全是不可能的(见farbrausch的作品: the product 中的说明字幕)。当然这只是忽悠外行的吓人话。其实写过游戏引擎的人都知道那只是通过实时渲染的到的,而音乐本身就是体积在12kb左右的mod音乐序列(见我以前写过的文章)。

 

目前很多机器都已安装最新版本的DirectX,而OpenGL是windows的默认库之一。这样Demo Scene设计者一般就不需要自己去编写基本的3d引擎。动画部分几个基本特效的代码不会超过30kb(这里假设开发者具有较高的设计素质),而一些复杂网格模型的纹理贴图即时采用bmp保存,也在100kb-300kb左右。加上mod音乐和其播放引擎。一个64kb DemoScence程序的原始体积一般应在600kb。而不是通过用等效为avi文件计算方法算出的几个G的天文数字。

 

不过,问题就产生了,实际程序体积只有64kb。在这600kb->64kb还是有相当距离的。如何尽可能的去减少这部分文件大小,以及其中伴随的一些技巧就是本文所要讨论的。

....

请点击文章查看完整内容

还算看得过去,我的CG实践作业及代码

(略文,请点标题进入) 告别了2007,好安心做点正事了。不过恐怕还是安心不下来,因为近期需要完成的任务太多太紧,我有点担心自己的能力了。CG作业已经完成了,我花了3天时间写完了光照渲染、2天时间写掉了光栅图形生成的Demo。虽然不是特别快,但长时间的身心疲惫,能有这样的结果我已很满足了。可能是自己喜欢追求完美,对接下来的网络作业我坚持要做到自己满意,所以还是要坚持在linux下开发sniffer。(或许有人认为我是自讨苦吃,让他们说去吧)。 好了,来说说这个作业吧。发布它的原因不是我觉得做得好,是因为 1. 这些都是Demo性质的作业,今后不会有什么特别应用,不过如果刚学习CG可以当作参考 2. 程序构架上我还是花了不少精力的,特别一些代码片断,比如仿造Photoshop的色彩选择器、演示光栅绘图的框架代码、基于PS2.0 ASM的渲染框架,这些今后如果各位需要作类似的东西,不妨拿去直接用。一些手法也可以作为参考(当然我保留版权)。

------------ 1.光照模型的实现 2.光栅图形生成

gift:多彩Console输出函数

什么是多彩Console输出?就是上篇文章中benchmark的效果图

其实windows有专门的console API实现这样效果,.Net里面也有封装,但是VC要实现还真是麻烦。所以在写CiperLib时候我顺便写了个帮助库,提供下面几个函数,使用很方便。

BOOL clr_foregnd(WORD clr);//设置文字颜色
BOOL clr_bkgnd(WORD clr);//设置背景色

BOOL clr_underline(BOOL bUnderLine=TRUE);//文字有下划线
BOOL clr_highlight(BOOL bHighlight=TRUE, BOOL foregnd = TRUE);//是否高亮度显示
BOOL clr_reverse();//背景和前景交换色彩
VOID clr_restore();//恢复默认的显示格式
VOID con_cls();//清屏幕

 

要注意适用时需要using namespace consolehelper;

使用方法是,调用了格式设定函数后,在之后的输出都会采用设定的色彩或者格式。

比如

clr_foregnd(CON_CLR.RED);

printf("Red Text");

 

对于颜色,提供了结构:

struct CON_CLR
{
    static const WORD RED  =  FOREGROUND_RED;
    static const WORD GREEN = FOREGROUND_GREEN;
    static const WORD BLUE = FOREGROUND_BLUE;

};

 

还可以这样使用:clr_foregnd(CON_CLR.RED | CON_CLR.GREEN);那么就是显示黄颜色了。

 

clr_highlight严格的说是区分正常色彩和低亮度色彩。

如果将3中元色和亮度组合,那么可以显示16种色彩。

 

con_cls();等同于system("cls");但是速度快

 

如果下载过ciplib的代吗,那么本函数库以及包括了,否则可以单独下载:

 

教育网:

ftp://great_csk:public@public.sjtu.edu.cn/public-files/console_hlper.rar

http://www.csksoft.net/data/legacyftp/Products/code_and_lib/console_hlper.rar

我写的大整数以及素域运算库

这个库叫做CiperLib,是我暑假在密码学实验室作的作品。比较工程化的东西,不过比较实用,所以就公布了。

下面是他的简介,我直接从他的说明文档中复制了,如果你完全知道他的作用,那么直接去文章末尾的链接下载。

 

 

CipherLib是一个使用C++和汇编代码实现的用于多精度大整数运算和密码学领域素域基本运算的函数库。由陈士凯(CSK)开发。
这个函数库实现的操作有:

  1. 支持任意精度的大整数:精度可以通过代码设定,支持符号数
  2. 对大整数的四则运算和求模运算,以及2进制化的移位操作
  3. 使用类将大整数加以封装,支持直接用传统运算符进行大整数的运算代码编写
  4. 支持从文本串和系统内置整型数据中读取大整数,支持将大整数输出为2进制、8进制、10进制和16进制文本串
  5. 实现了Marsaglia & Zaman的长周期随机数(本机支持的整型格式)
  6. 支持模加、模乘、模幂计算
  7. 支持Rabin-Miller方法的素性验证
  8. 支持大素数产生

 简单的说可以利用这个库实现一些高精度计算和密码算法,比如RSA。


 

该函数库在设计上参考了mircal库,在核心的运算操作上使用了x86汇编语言和C语言2种版本代码编写。默认采用汇编语言执行。因而具有很高的运行效率(具体见Benchmark部分)
 
CipherLib的一些技术信息:
项目
说明
运行环境
32x86指令系统下的windows环境
开发环境
VC++ 2005版本
是否多线程安全
函数库形式
静态链接库或者直接嵌入代码
第三方库依赖
需要C运行库

 

Benchmark

 

下面是我写的对于CipherLib和mircal的一个运行效率比较(不过不是很科学,但是基本可以说明问题):

使用附带的程序CiperBench进行测试。
         测试程序在开发者电脑环境:Intel Pentium M 1.6G ,2G RAM,WinXP sp2环境中,对于静态库的本函数库和Mircal进行比较。
 
         由于采用了timeGetTime() API获取时间,因此精度可能会受偶尔系统调度的影响。
下面是对1000次的四则运算的执行时间对比,本函数库表现较优:

对于乘法的实测情况

对于加法的实测情况

对于减法的实测情况

对于除法的实测情况

对于求大素数的实测情况

 

 

 

 

对于素域运算,使用了产生一个大素数的运算作为衡量指标,因为其中需要进行素性验证和模乘和模幂运算。本函数库效率较低,原因是没有针对素性验证是的模幂运算单独进行优化。


我用于求模幂的算法是Koch提出的Sliding Window法。但是对于求素性验证来说不是最优的。

 


 使用范例

 

下面是用本函数库求解1000!的代码,从代码风格上可以看出他的易用性,具体代码和使用办法见文章末尾给出的文件中的操作手册。

#include "CiperLib.h"
#include <iostream>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
    Integer::Init(409600);
    char output[20000];
    Integer Base(1000),Ans(1);
    while(!Base.isZero())
    {
        Ans *= Base;
        Base -= 1;
    }
    Ans.toString(output,20000);
    cout<<"Finished, Ans is:"<<endl<<output <<endl;
    system("pause");
}

 

下面很简单的说下实现的细节

大整数是采用2^32进制保存的,也就是用一个DWORD存储一个“位”。对于四则运算均使用汇编优化,其中算法参见Knuth的the Art of Computer Program 第二卷的多精度计算。

对于素域的计算,主要采用的就是窗口法求模幂,素性验证使用了Rabin-Miller法,并且进行了100次判断,可以确保相当高的正确概率。

注意的是,我不能保证潜在的bug,同时一些算法并不是最优的,所以使用时请自己注意。而且今后基本无法维护了。对于具体的实现,可以看代码注释以及我附在其中的实习报告

代码/Demo/文档的下载:

http://www.csksoft.net/data/legacyftp/Products/code_and_lib/CiperLib_release_by_csk.rar

教育网:ftp://great_csk:public@public.sjtu.edu.cn/public-files/CiperLib_release_by_csk.rar

Intercessor-Super Task Manager

 

这学期Windows的大作业,和Messiah一起合作的东西。

看界面就知道他的作用了吧,是一个进程管理器,他的优点在于

直接扫描物理内存中的EPROCESS结构来获取进程列表,并且对于大部分进程信息获取工作都是直接读取内存进行了。因而理论上他可以探测大部分的隐藏进程,应该说功能还是很强劲的。

对于进程管理方面,Intercessor直接调用了内核态的NtTerminateProcess来关闭进程,所以杀伤力也很大。

 

我个人的评价是在进程显示方面比如今的Iceword差不多,而且有些方面比较人性化。同时该程序也作了防止非法关闭的处理。具体间附带的文档。

 

如果喜欢可以下载过来使用,程序使用WTL进行界面开发,体积比较小巧。

 

下载地址:http://www.csksoft.net/data/legacyftp/Products/APP/intercessor_bin.rar

 

原理和核心驱动代码下载:http://www.csksoft.net/data/legacyftp/Products/APP/Intercessor_report_src_bin.rar

 

由于这是一个课程大作业,所以今后恐怕没时间维护了,所以如果你希望继续开发完善她的话。可以试着与我联系获取源代码。但如果你是有其他目的的,那就不用来找我了。

 

实时ASCII图像显示

今年5月劳动节休假作的一个小程序。当时为了要实现人脸识别等一些CV的东西顺便做的。可以实时的将摄像头中的画面转化成ASCII字符显示,效果像下面这样:

将视频画面实时转为ASCII效果图

 

算法还没有专门优化过,不过目前达到12fps还是没问题的. 暑假随着继续作CV的东西有望能发布出个像样的玩艺儿来..

 

写了一个GRE单词背诵辅助程序

标题没有表达清楚。情况是这样的。

相信各位G友都看过杨鹏写的《17天搞定GRE单词》,说来惭愧,我可能算是进度很慢的了,现在还没搞定红宝书...

这本书实际上就是对艾宾浩斯记忆曲线的应用,每当新背诵一批word list以后,应当在今后的1、2、4、7、15天后复习,以达到最快且最佳的背诵效果。但我不是什么聪明的人,我不可能记住每天背诵的list应当何时是最佳复习时间。当然我可以按照杨鹏书上说的那样列一个表格。

但这样十分不灵活,比如很有可能某天我要忙着做其他事情,导致当日任务无法完成,从而整个表格就要变动。而且我也懒得去列这个表格。

作为一名CS学生,这类事情应当动动脑子写个程序了,所以就有了这个东西。

下面是他的截图:

这是一个用asp写的程序,作用是按照设定,它可以告诉你每天需要复习和新背诵的wordlist。同时会提示你某项list是处于第几轮复习状态。

如果当天完成了某个项目,可以点"proceed"通过,如果没有点击,则系统自动安排顺延。

你可能会说这年头这种程序不是多得是吗?的确,我写这个东西还有个目的,就是可以使用手机访问。这样不用天天开那个电脑...因此在我上课或自修时候,先用手机登陆网站核对下任务就可以开始学习了。而且也是为了锻炼写程序....

如果你对这个程序感兴趣,不妨用我给出的代码作一定修改。

只需要asp支持,算法写的很傻,不用去研究了

在第一次使用时候,将代码line 151的注释

'init_conf 51,3,8

去除注释。这个函数表示初始化配置文件,第一个参数表示总共的word list数,第二个是每天新背诵的word list数,第三个暂时没有实现,是最多的任务条目,我觉得这个参数还是不去处理为好

这个设定就是杨鹏书上推荐的做法,当然你可以按照你的喜好设定。同时稍微修改代码,就可以从你当前背诵的进度开始执行任务了。不过我比较懒,宁愿从头开始背...

好了,废话就写这么多,如果这个程序能对你派上用场。不妨留言告诉我,我会很开心~

下载地址:

http://www.csksoft.net/data/legacyftp/Products/code_and_lib/src_gre_tracer.rar

关于linux kernel课程中semaphore计数作业

好久没写blog了啊,来篇技术点的

最近一直忙着做linux kernel的作业,难度到是不大,就是每次重新编译内核要30分钟,实在吃不消。

刚做好一个task.要求是这样的:

    • Add wait_times, wait_duration, 2 new data members into definition of data struct semaphore; Every time to wait(Sleep) for every lock being free, increase wait_times.After getting the lock, calc the wait duration and add itinto wait_duration;

    • Add use_times, use_duration, 2 new data members into definition of data struct semaphore; Every time after getting the sema, inc use_times. After releasing the sema, calc the utilization duration and add it into use_duration;
    • Use tsc to calc time;

    • Add function register_sema(struct *semaphore): Add sema_perf_list, a global var and a list_head to record all sema registered by register_sema;

    • choose a list of sema and register them before using them;

    • Export the 4 data and sema address of the registered sema list by proc;

最终要求作出的效果是在proc下导出文件semadata,显示如下内容:

#cat /proc/semadata
0xa0000000 1001 56890 2002 89765
0xa000ff00 401 6890 888 9765

-----------------------------------------

下面是我的解题思路和解决办法

关于这个问题网上也有不少的解法,其中我参考了

http://bbs.ss.pku.edu.cn/ss/index.php/6122/action_viewspace_itemid_9362.html

的办法,不过其中也有不少问题,所以我把我的修正点和不同的做法写出,一些基本的做法就看上文的链接

好了,下面说我的具体做法

1.在semaphore.h中增加4个规定的变量

由于要求用rdtsc指令记录时间,所以采用rdtscll宏,这个宏实质就是wrap了x86的rstsc指令,返回一个64bit的数据记录CPU的clock数

所以我用u64类型(unsigned long long)记录use_duration和wait_duration

1.在struct semaphore中增加:

 unsigned long wait_times;
 u64 wait_duration;
 unsigned long use_times;
 u64  use_duration;

2.然后在struct semaphore中增加增加:

 struct task_struct * structlst[10];
 u64 tsk_start_using[10];

为什么增加这2个成员呢?考虑到同一个semaphore在用一个时刻可以被不同process调用(执行down() ),所以考虑到需要记录不同process使用该semaphore的开始时间。

intel给我们的tips要求的是在task_struct中增加一个u64 start_time[10];

他的思路正好和上面的办法颠倒,是让每个task记住自己使用一个semaphore的开始时间。

同时因为考虑到一个process可以嵌套的调用很多semapore。

比如:

processA:

Down(sema1);

//some codes

Down(sema2);

//some codes

Up(sema2);

Up(sema1);

这样一来必须记录每个semaphore的开始时间。然后用一个int pos来跟踪嵌套调用down()的深度(好比是堆栈指针)

但是这也有个问题(多谢xris提醒)

考虑下面的调用顺序:

processA:

Down(sema1);

//some codes

Up(sema2);

Down(sema2);

//some codes

Up(sema1);

每个semapore是交错调用的,这样用前面stack数据结构来记录肯定失效了

所以我原先的做法是在task_struct中加入下面2个成员:

u64 start_time[10];

struct semaphore * used_sema_handle[10];

这样一来就能解决上面的问题,但是要求每次先从used_sema_handle里面找到对应semaphore的下标,然后在操作上面的start_time数组。

(用10个元素只是近似情况。同时这个办法也有问题,比如同一个semaphore可以连续down();2次,这样这个方法也实效,如果你有更好的办法欢迎告诉我)

那么为什么我最终没有修改task_struct而是在semaphore里面加了2个对应的变量呢?

那只是因为之前这个办法编译没有通过,提示task_struct在semaphore.h中是unreferenced (我还是不太习惯gcc,没办法,汗...),所以只好在struct semahore里面加2个对应的变量,可以起到同样效果

3.在semahore.h中增加下面函数:

static inline void reg_and_settime (struct semaphore *sem, u64 qw_start)
{
 struct task_struct *tsk = current;
 int npos = 0;
 for (;npos < 10;npos++)
 {
  if (sem->structlst[npos] == NULL)
  {
   sem->structlst[npos] =tsk;
   sem->tsk_start_using[npos] = qw_start;
   break;
  }

 }
}
static inline u64 rm_and_rdtime (struct semaphore *sem)
{
 int npos = 0;
 struct task_struct *tsk = current;
 for (;npos < 10; npos ++){

  if (sem->structlst[npos] == tsk)
  {
   sem->structlst[npos] = NULL;
   return sem->tsk_start_using[npos];
  }

 }
 return 0;/* oops~ not found */
}

这2个函数就是操作那对structlst和tsk_start_using成员的,reg_and_settime将当前的task指针记录到structlst,并找到一个位置存放此时的start_time。rm_and_rdtime则将当前task对应的start_time读出,然后把自身记录抹去。具体就不解释了

4.在down,down_interruptible,down_trylock加入下面代码:

 u64 qw_start_time;
 sem->use_times++;
 rdtscll(qw_start_time);
 reg_and_settime(sem,qw_start_time);

5.在up中第一行加入:

 u64 qw_current_time,qw_start_time;
 rdtscll(qw_current_time);
 qw_start_time = rm_and_rdtime(sem);
 if (qw_start_time != 0){  /* ensure the process invoked down before this up*/
  sem->use_duration += qw_current_time- qw_start_time;

 }

6.按照参考文章的办法修改lib/semaphore_sleeper.c。以及为了修改fs/proc/proc_misc.c所作的所有操作

7.在proc_misc.c中,修正参考文章的问题

unregister_sema修改为:

int unregister_sema(struct semaphore *sema)
{
        int ret;
        ret = 0;
        struct list_head *pos;
        struct list_head *next;
        struct list_head *prev;
 struct semaperf_list *psema;
        pos = container_of(sema, struct semaperf_list, sema_list);
       
        __list_for_each(pos, &g_semaperf_head.sema_list)
    {
     psema = container_of(pos, struct semaperf_list, sema_list);
    
     if (psema->semaperf == sema)
     {
  next = pos->next;
         prev = pos->prev;
         __list_del(prev, next);
  
  kfree(psema);
         --g_regist_count;
     }
    }

       return ret;
}

原文的办法,通过container_of宏查找semaphore *所在的struct semaperf_list指针是行不通的,这样只会造成调用该函数访问空地址,造成内核崩溃,当然我的修改也很愚蠢...

get_semaperf_list中的显示函数的打印语句改为:

     length += sprintf(buffer, "0x%x %ld %llu %ld %llu\n", (unsigned int)psema->semaperf,
     psema->semaperf->wait_times,
     psema->semaperf->wait_duration, 
     psema->semaperf->use_times,
     psema->semaperf->use_duration);
     strcat(page, buffer);

这个不用多做解释,use_duration这些是u64的

8.编写module

写module有2个功能

1).通过module创建n个semaphore,然后调用register_sema,以便显示

2).提供能够由ring 3的程序调用的down和up

其中第一个功能很容易实现,第二个很明显就是要用systemcall。但是这是一个module,不可能通过常规手段修改内核代码添加systemcall(除非你把这2个systemcall编译进内核)

我采取的办法是在module启动时候获取IDRT向量表,然后找到system call的int 80表向,最终找到system_call数组表,然后动态替换2个无用system_call实现增加systemcall的手段(对了,就是流氓软件hook system call的办法)

module的代码很长,我把它附在文章的末尾

9.编写测试程序调用module提供的systemcall

下面是我写的程序:

int main(void)
{

 while(1)
 {
  syscall_sema_dw(0); //enter critical region
  usleep(500); //sleep for 500 milliseconds
  syscall_sema_up(0); //leave critical region
  usleep(200);
 }

}

把程序编译为mutex_racer,然后同时执行2个该程序。可以看成使对一个critical_region的访问操作。

其中syscall_sema_dw和syscall_sema_up是module提供的systemcall,参数0表示使用module创建的第一个semaphore

最终编译好这些代码,进入新的内核,就可以看到效果了:

starting sema dump... total: 4
0xf8c3618c 0 0 0 0
0xf8c360e8 0 0 0 0
0xf8c36044 0 0 0 0
0xf8c35fa0 27198 119425837 29922 71715898387
----------------------
 dump completed

因为只使用了1个semaphore,所以前3项都是0

好了,到此任务大功告成,当然你也可以写其他的测试程序,比如模拟PV操作看效果。

最后附上我写的module代码:

/*
 Semaphore debug helper module
 BY CSK
 csk@live.com
*/

#include<linux/kernel.h>
#include<linux/module.h>
#include<linux/init.h>
#include<linux/unistd.h>


#include<asm/uaccess.h> // for copy_to_user
#include<linux/sched.h> // for current macro

#include <linux/sema_helper.h>

/* index 223 and 285 is not used in kernel 2.6.20.3 */
#define __NR_HELPER_SEMA_UP 223

#define __NR_HELPER_SEMA_DW 285

long * systable; /* location to store system_call_table */

static int (*saved_223)(void);
static int (*saved_285)(void);

#define HELPER_SEMA_NUM 4
static struct semaphore pSema_lst[HELPER_SEMA_NUM];

/* init semaphore */

static void init_env()
{
 int pos = 0;
 /* init each sema */
 for (;pos<HELPER_SEMA_NUM ; pos++)
 {
  sema_init(pSema_lst + pos , 1); //mutex-style sema
  memset(pSema_lst[pos].structlst,NULL,10*sizeof(struct task_struct *));
  register_sema(pSema_lst + pos);
 }


}

static void release_env()
{
 int pos = 0;
 for (; pos<HELPER_SEMA_NUM; pos++)
 {
  unregister_sema(pSema_lst + pos );
 }

}

/* new syscall */

asmlinkage int helper_down_sema(int sema_id)
{
//struct timeval ktv;
//do_gettimeofday(&ktv);
//copy_to_user(tv,&ktv,sizeof(ktv));
 down(pSema_lst + sema_id );
// printk(KERN_ALERT"<helper_down_sema>PID %ld called ,with value %d.\n",(long)current->pid,sema_id);
 return 0;
}


asmlinkage int helper_up_sema(int sema_id)
{
//struct timeval ktv;
//do_gettimeofday(&ktv);
//copy_to_user(tv,&ktv,sizeof(ktv));
//printk(KERN_ALERT"<helper_up_sema>PID %ld called ,with value %d.\n",(long)current->pid,sema_id);
 up(pSema_lst + sema_id);
return 0;
}


/* Begin hacking code ;-) */
//IDTR
struct {
    unsigned short limit;
    unsigned int base;
} __attribute__((packed)) idtr;


// IDT
struct {
    unsigned short off1;
    unsigned short sel;
    unsigned char none, flags;
    unsigned short off2;
} __attribute__((packed)) idt;

 

// find the address of sys_call_tb
void disp_sys_call_table(void)
{
    unsigned int sys_call_off;
    unsigned int sys_call_table;
    char* p;
    int i;


    asm("sidt %0":"=m"(idtr));
    printk("addr of idtr: %x\n", &idtr);

  
    memcpy(&idt, idtr.base+8*0x80, sizeof(idt));
    sys_call_off=((idt.off2<<16)|idt.off1);
    printk("addr of idt 0x80: %x\n", sys_call_off);


    p=sys_call_off;
    for (i=0; i<100; i++)
    {
        if (p[i]=='\xff' && p[i+1]=='\x14' && p[i+2]=='\x85')
        {
            sys_call_table=*(unsigned int*)(p+i+3);
            systable = (long *)sys_call_table;
      printk("addr of sys_call_table: %x\n", sys_call_table);
            return ;
        }
    }
}


/* end of hacking code ;-) */

 

 

int syscall(void)
{
/* init semaphore data */

init_env();


/* start kernel hacking! */
disp_sys_call_table();
//save old entiry before replace
saved_223=(int(*)(void))(systable[__NR_HELPER_SEMA_UP]);
saved_285=(int(*)(void))(systable[__NR_HELPER_SEMA_DW]);
//ok, replace them
systable[__NR_HELPER_SEMA_UP]=(unsigned long)helper_up_sema;
systable[__NR_HELPER_SEMA_DW]=(unsigned long)helper_down_sema;

return 0;
}

void exit_syscall(void)
{
release_env();
//save back
systable[__NR_HELPER_SEMA_UP]=(unsigned long)saved_223;
systable[__NR_HELPER_SEMA_DW]=(unsigned long)saved_285;
}

module_init(syscall);
module_exit(exit_syscall);

-----------------------

写的虎头蛇尾,如果觉得哪里不正确欢迎指出

CSK 2007-4-22

MMX指令优化的32bit AlphaBlend

前一段时间再进行一个目前保密的项目:Prototype A (哈哈,知道的人不要说阿)

其中需要较高的运行效率,所以就写了一个将32bit位图渲染到目标32bit位图的AlphaBlend。支持Alpha通道。

代码指令参照了http://dev.gameres.com/Program/Visual/2D/mmxaddalpha.htm提供的代码,在此表示感谢。由于第一次写汇编优化。所以不知道这样写是不是最高效的。

如果对位深没有要求,可以采用intel提供的16bit的alphablend,网上很多了,这个号称是目前最快的.

参数:

pDest:目标渲染buffer,32bit的,通道情况:ARGB

wlined:pDest的扫描线宽(即横向的像素个数,即实际宽度/4)

hlined:pDest的扫描线行数,可以理解成实际高度

startX:pDest的开始坐标X

startY:pDest的开始坐标Y,采用倒置坐标系

pSrc:要渲染得图片,通道情况:ARGB

wlines,hlines和前面类似

Alpha:对pSrc做得整体alphaBlend,0-255级

返回:

如果图片得到渲染,返回TRUE

用在Prototype A中效果还好,采用GDI渲染一个100*100的图片可以有1000fps*

代码:

BOOL AlphaBlt(BYTE *pDest,DWORD wlined,DWORD hlined,int startX,int startY,BYTE *pSrc,DWORD wlines,DWORD hlines,DWORD Alpha)
{
 int Xd,Yd,Xs=0,Ys=0;
 int loopH,loopW;
 if (startX>=(int)wlined) return FALSE;
 if (startY>=(int)hlined) return FALSE;
 
 if (startX + (int)wlines <=0) return FALSE;
 if (startY + (int)hlines <=0) return FALSE;
 
 Xd = startX;
 Yd = startY;
 loopW = (startX + wlines);
 loopH = (startY + hlines);
 if (loopH>hlined) loopH = hlined;
 if (loopW>wlined) loopW = wlined;
 if (startX<0)
 {
  Xd = 0;
  Xs = -startX;
 }
 if (startY<0)
 {
  Yd = 0;
  Ys = -startY; 
 }
 
 DWORD factorA = hlines-Ys+Yd-1;
 for (DWORD j= Yd ; j< loopH ; j++)
 {
  DWORD dwOffSrc,dwOffDest;
  dwOffSrc = (factorA-j)*wlines;
  
  dwOffDest = (hlined-j-1)*wlined;
  DWORD srcPosX = Xs;
  for (DWORD i = Xd ; i< loopW ; i++)
  {
  
   BYTE *BufSrc = pSrc + (dwOffSrc + srcPosX)*4;
   DWORD dwSrc =((DWORD)BufSrc[3] << 24) |((DWORD)BufSrc[2] << 16) | ((WORD)BufSrc[1] << 8) | (BufSrc[0]);
   DWORD *dwpDest = (DWORD *)pDest + dwOffDest + i;
    __asm{
     pxor mm2,mm2

     mov edx,dwpDest
     movd mm0,[edx]
     movd mm1,dwSrc
     punpcklbw mm0,mm2
     punpcklbw mm1,mm2

     movq mm3,mm1
     punpckhwd mm3,mm3
     punpckhdq mm3,mm3

     movd mm4,Alpha

     punpcklwd mm4,mm4

     punpckldq mm4,mm4

     pmullw mm3,mm4 //Alpha * SrcAlpha
     psrlw mm3,8

     movq mm4,mm0

     movq mm5,mm1

     psubusw mm4,mm1

     psubusw mm5,mm0

     pmullw mm4,mm3

     pmullw mm5,mm3

     psrlw mm4,8

     psrlw mm5,8

     paddusw mm0,mm5

     psubusw mm0,mm4

     packuswb mm0,mm0


     movd [edx],mm0 //保存结果

     emms

   }


   srcPosX++;
  }
 }
 return TRUE;
}

分页:[«][1]2[3][4][5][»]

日历

<< 2015-6 >>

Sun

Mon

Tue

Wed

Thu

Fri

Sat

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

Copyright Shikai Chen 2000-2012. Powered By Z-Blog(CSK Modified)