Saturday, January 29, 2011

First Chance Exception, Second Chance Exception, WinDBG

所有Managed异常的HRESULT都是0xE0434352(无法用Error Lookup找到这个Error Code)。
通常在Event Log或者WinDBG所见到的Managed异常如下:
CLR exception - code e0434352

通常情况下First Chance Exception不是真正能导致程序Crash的异常,通常这个异常可以通过try…catch来捕获。只有当这个异常无法被捕获时才会升级为Second Chance Exception,这个异常会导致Crash。

可以用过WinDBG的命令sxe e0434352来使Debugger在First Chance Exception的时候Break。

image

继续Debug

image

可以看出Thread 4出现了一个System.Exception,还能看出这是一个First Chance Exception。

image

WinDBG报了Second Chance Exception,这导致了程序Crash。

慢慢玩儿,有点意思。

Monday, January 3, 2011

Managed Object Memory Layout

汇总学到的知识才是对上一年最好的总结。
CLR中的Object的Memory Layout是由一个4 byte的Syncblk,一个4 byte的TypeHandle以及之后的Instance Fields之类组成的。TypeHandle中又包含了重要的MethodTable和EEClass数据结构,这两个数据结构的实例对一个Type来说都只有一个。
通过Windbg来观察这个Object,首先找到这个Object的reference:
windbg
然后dd 0x0184274 - 0x4,ObjetRef实际上是指向TypeHandle而非Syncblck,所以需要减4。
windbg
这里可以看出Syncblk的值是08000001,TypeHandle是00233090,之后的三个是instance的值,分别是10,5,10。
TypeHandle是一个指向MethodTable的指针。
再一次通过Windbg来看这个指针的内容:
windbg
通过观察可以发现示意图似乎不准确,可能实现细节改过了。00232c5c才是一个指向EEClass的指针,002312a8是一个指向Module的指针。之后似乎又有4个连续的指针地址:594f6a90 -> 595674c0,这四个其实是4个method。看过Raw memory之后再用过sos来看看这个MethodTable
windbg
又见到了594f6a90这个地址,先看看这个的MSIL:
windbg
似乎是一个ToString(),再来看看sos:
windbg
两者一致。继续用sos来观察这个EEClass和Module两个数据结构。
windbg
windbg
这只是所有Managed Object中的一小部分,很多内容还有待挖掘。

Friday, November 26, 2010

归来的饭否

饭否正式回归。时隔近2年,饭否还是那个饭否,我却不再是过去的我了。

内牛满面和抒情不合适我,上图才有真相:

饭否

Saturday, October 9, 2010

对和平奖的亵渎?

外交部发言人马朝旭在回应刘晓波获奖时说:“刘晓波是因触犯中国法律而被中国司法机关判处徒刑的罪犯,其所作所为与诺贝尔和平奖的宗旨背道而驰。诺委会把和平奖授予这样一个人,完全违背了该奖项的宗旨,也是对和平奖的亵渎。”

中国的法律是对和平的尊重么?

Sunday, August 15, 2010

全国哀悼日

2010年8月15日(GMT+8)是全国哀悼舟曲泥石流遇难者日。这边厢我朝大小衙门需要下半旗;子民须停止一切娱乐活动并且要举行默哀仪式。那边厢SB会依然热情款待着全世界来朝的人民,明天还是一年一度的七夕节。
又一次形式主义的宣传,再一次抓住次要矛盾忽略主要矛盾。这所谓的“天灾”哪一次不是人祸?这边救灾还在进行那边就忙着大肆宣传“英雄”的“杰出”事迹,再深究祸事就似是对“不识大体,不顾大局”。我真的很不明白到底是生活在一个身边都是“英雄”的险恶地方好,还是生活在一个身边都是“常人”的安全地方好。随着时间的流逝,追究事件原因的声音也在变小,终究会到大家都麻木的时候。鲁迅的讽刺现在依然适用,而且对应得是那么得贴切。衙门就好似阿Q,别人欺侮阿Q,阿Q则欺侮比自己更弱小的小尼姑。

Thursday, July 15, 2010

Windbg学习笔记之一:构建环境

Debug是每一个合格的开发人员都必备的技能。(我惭愧了,我不合格)
Windbg是Windows平台上功能极度全面的Debug工具,此乃居家旅行,杀人越货之必备产品。
在学习如何使用Windbg之前,首先要有个实验的环境,但是安装Windbg,并且使Windbg正常工作不是件容易事。通过这几天的研究,我将列举出安装Windbg和使用Windbg初期常见的问题。

问题一:哪里下载?
回答: https://www.microsoft.com/whdc/DevTools/Debugging/default.mspx上面的链接通常是一个web installer,但是也提供了ISO下载。这套工具中包括了kd,ntsd, cdb,和万能的Windbg,当然也包含了很多其他常见的工具。

问题二:装完之后怎么用?
回答:Windbg自然是用来Debug的,但是它也可以用来观察系统是如何运作的。要让Windbg正常的工作起来,还是有一定难度的,首先要做的一件事情就是把symbol path设定好。
什么是symbol path?编译原理中提到的符号表就是编译器用来找符号对应地址时候用的,同时在debug的时候,符号也能够用来帮助我们定位变量和函数的具体位置。如今的软件动辄几个GB,为了不增加最终用户磁盘空间的压力,所以把符号表和其他相关的信息存储到了另一个文件上(通常是dbg或pdb文件)。这样就确保最终编译出来的文件又小又快。
Windbg有很多中设定symbol path的方法,这里只需要介绍两种。
方法一:_NT_SYMBOL_PATH
把_NT_SYMBOL_PATH添加到环境变量中去,如_NT_SYMBOL_PATH=SRV*d:\symbols\7600*http://msdl.microsoft.com/download/symbols
其中d:\symbols\7600是缓存,而http://msdl.microsoft.com/download/symbols是符号的下载地址。这里需要注意的是一定要使用管理员权限去打开debugger,否则无法读出环境变量。 方法二:.sympath
在任意个一个debugger中的命令行中键入:.sympath SRV*d:\symbols\7600*http://msdl.microsoft.com/download/symbols 也能达到同样的效果。
直接通过下载符号可以保证符号是正确的,但是这也造成了不小的负担,所以可以先下载已有的符号当缓存用:http://www.microsoft.com/whdc/devtools/debugging/symbolpkg.mspx但是这个缓存通常不是最新的,这也就是设定网络路径的好处了。
通过使用命令:!sym noisy可以使debugger把查询符号的位置和是否匹配的结果列出来。这样可以马上知道什么原因无法找到符号。比如ntdll.dll时常更新,7600里面的版本号和新的ntdll不匹配会导致无法找到符号。

Monday, June 21, 2010

写给自己看之三:AVL树的插入

当初没有学会,考试似乎也不考,所以没放在心上。但是心血来潮一下,搞了一下这个东西。
AVL树(平衡树)的定义:
  • 每个节点左子树的高度和右子树的高度差的绝对值小于2.即:| h(left[x]) - h(right[x]) | < 2。
  • 这样做的好处就是把二叉树的树高严格控制在log(N)上。从而杜绝成为链表的情况。
    如何才能做到这点呢?
    我读的教材所采用的方法是多设一个节点信息叫BF(Balance Factor)作为枚举类型。三个值分别为:LH(Left High),EH(Equal High)和RH(Right High)并采用递归插入。说实话,作者能写出这么牛的递归并且保证正确相信难倒了不少学生(包括我)。
    还有一本经典教材,采取不同的方法解决这个问题:节点增设高度信息。然后对插入路径进行高度平衡。我比较青睐这种做法。
    然而这种做法却需要一个额外的节点来表示空节点,否则无法正确处理高度差。所以自然而然想到了null object这个模式。
    好了,现在开始解决插入中最麻烦的问题:平衡高度。
    一共4中情况(OMG!)但是都只需要知道失去平衡的最小的祖先节点就可以了(这就是回溯插入路径):
    1. 受影响的节点从1增加到2,左子树的树高是1。也就是插入的这个左子树的左边。这种情况只要对高度差为2的节点进行一次向右旋转就可以了。
    2. 受影响的节点从-1增加到-2,右子树的树高是-1。也就是插入这个右子树右边。这种情况需要对高度差为2的节点进行一次向左的旋转。
    3. 受影响的节点从1增加到2,左子树的树高是-1.也就是插入的是这个左子树的右边。这种情况比较复杂。为了保持中序遍历的正确性(很重要),需要先对这个左子树做一次向左的旋转。然后问题转化为1的情况。
    4. 受影响的节点从-1增加到-2,右子树树高是1.也就是插入这个右子树的左边。这种情况需要对这个右子树做一次向右的旋转,转化为情况2。
    晕了么?我是晕了。但是通过画图就知道是怎么回事了。还有就是看教材上的图片,教材上的图应该能解释一下问题。还有一点非常好的地方就是不存在别的情况(教材上说了就那么4种,再多就是不正常的了)。
    现在的问题是怎么旋转?
    先看图:
    Before rotation
    对这种情况下的x节点做一次向左的旋转。
    结果图:
    After rotation
    从结果可以看出唯一一个需要变动的字节点就是q,别的节点原来在什么位置现在还在什么位置。一开始听到旋转我马上就晕眩了。现在把图画出来自己研究一下,也就只需要变动一个节点,这样的操作显然不是很困难。但是边界检查很重要。这时有两种情况:
    1. x的父节点是空。也就是x本身是root,那么把root指向y就可以了。
    2. q是个空节点。这是不需要对q的parent节点进行操作。
    左旋转的代码:
    private void Rotate_to_Left(Node x)
    {
        Node y = x.RChild;
        Node z = x.Parent;
        Node q = y.LChild;
    
        if (z == NULL_NODE)
        {
            this.root = y;
        }
        else
        {
            if (z.LChild == x)
            {
                z.LChild = y;
            }
            else
            {
                z.RChild = y;
            }
        }
        y.Parent = z;
    
        y.LChild = x;
        x.Parent = y;
    
        x.RChild = q;
        if (q != NULL_NODE)
        {
            q.Parent = x;
        }
    }
    
    右旋转也一样只有一个子节点需要改变,代码如下:
        private void Rotate_to_Right(Node x)
        {
            Node y = x.LChild;
            Node z = x.Parent;
            Node q = y.RChild;
    
            if (z == NULL_NODE)
            {
                this.root = y;
            }
            else
            {
                if (z.LChild == x)
                {
                    z.LChild = y;
                }
                else
                {
                    z.RChild = y;
                }
            }
            y.Parent = z;
    
            y.RChild = x;
            x.Parent = y;
    
            x.LChild = q;
            if (q != NULL_NODE)
            {
                q.Parent = x;
            };
        }
    
    接着的关键问题就是如何计算节点的高度了,问题不难,但是注意我有一个null object: NULL_NODE。这个节点没有父,左,右和高度信息。
        public int Height
        {
            get
            {
                if (this == NULL_NODE)
                {
                    return 0;
                }
    
                List< Node > nodes = new List< Node >() { this };
                List< List < Node > > height = new List< List< Node > >() { nodes };
    
                while (true)
                {
                    nodes = new List< Node >();
                    foreach (Node n in height[height.Count - 1])
                    {
                        if (n.LChild != NULL_NODE)
                        {
                            nodes.Add(n.LChild);
                        }
                        if(n.RChild != NULL_NODE)
                        {
                            nodes.Add(n.RChild);
                        }
                    }
    
                    if (nodes.Count != 0)
                    {
                        height.Add(nodes);
                    }
                    else
                    {
                        break;
                    }
                }
    
                return height.Count;
            }
        }
    
    下面处理如何使这颗树回复平衡:
        private void balance(Node x)
        {
            int balance_factor = x.LChild.Height - x.RChild.Height;
            //There are 4 cases:
            //1. balance factor increased form 1 to 2; do a roatation toward right can address the problem
            //2. balance factor increased from -1 to -2; do a rotation toward left can address the problem
    
            if (balance_factor == 2)
            {
                if (x.LChild.LChild.Height < x.LChild.RChild.Height)
                {
                    this.Rotate_to_Left(x.LChild);
                }
                this.Rotate_to_Right(x);
            }
    
            if (balance_factor == -2)
            {
                if (x.RChild.LChild.Height > x.RChild.RChild.Height)
                {
                    this.Rotate_to_Right(x.RChild);
                }
                this.Rotate_to_Left(x);
            }
        }
    
    和二叉搜索树插入唯一不同的一点就是在插入结束的时候回溯到根节点:
        public void Add(Node n)
        {
            Node p = this.root;
            Node q = NULL_NODE;
    
            if (p == NULL_NODE)
            {
                this.root = n;
            }
            else
            {
                while (p != NULL_NODE)
                {
                    q = p;
                    if (n.Key > p.Key)
                    {
                        p = p.RChild;
                    }
                    else
                    {
                        p = p.LChild;
                    }
                }
    
                if (n.Key > q.Key)
                {
                    q.RChild = n;
                }
                else
                {
                    q.LChild = n;
                }
                n.Parent = q;
            }
            n = n.Parent;
            while (n != NULL_NODE)
            {
                balance(n);
                n = n.Parent;
            }
        }