A New Beginning

Registered a new blog hellopatz, focusing on computer techniques, NO personal stuff.

机会

机会的一个特征是：一件事情，如果所有人都认为是个难题却必须解决。

One symptom of opportunity is that every one thinks it’s difficult but need to be resolved.

SRM. 484

Today I took part in the TopCoder SRM. 484. Got up early since it’s +8 here, but feels good.

In the contest, there’s a question like this:

We say a number x is a Rabbit Number if it satisfied S(x)*S(x) = S(x*x), where function S means the sum of every digit of the number x. Find out the number of Rabbit Number in a given range. (0~1,000,000,000)

I didn’t figure it out, but after reading other ppl’s solution, finally I came up with the way to solve it.

Suppose there’s a number X=ab, i.e., a*10 + b. And it’s a Rabbit Number. Then we have:

S(X)*S(X) = (a+b)*(a+b) = a^2 + 2ab + b^2

and

S(X*X) =   a               b
               *    a               b
——————————–
                     ab             b^2
        a^2     ab

Clearly enough, if these two expressions are equal, then in the 2nd expression, the b^2 won’t have a carry. (And so is the 2ab) Thus, the Rabbit Number must be ended with a digit no greater than 4, since 4^2 = 16, which produces a carry.

BTW, the number 1,000,000,000^2 is still in the range of type long long. So, take a DFS or BFS as you like.

ManalSadek’s clean & neat code helps me quite a lot. Many thanks!

Live Space关闭了

　　很遗憾听到MS打算关闭Live Space的服务。Live Space也许不是做的最好的BSP，但却十分令我中意。

　　仍记得，若干年前，Live Space初次推出HTML自定义模块的时候，当时还未对中国用户开放，但网上已经充满了各种各样的教程帮你获取一个How To Make Love自定义模块——甚至两个。利用它，不但删掉了Live Space那个从来没让我注意过（因为被浏览器直接嚓咔）的广告banner，而且还能把整个页面改的面目全非，让人几乎认不出来实在Live Space建立的blog。

　　当时尚在念中学，周末除了贡献给游戏和课业的时光之外，就剩下半夜之后能剩下一些时间留给Live Space。除了描绘一下生活，最喜欢做的事情就是顺着“最近更新的blog”链表，一个一个blog追踪下去。遇到精彩的就加个书签，乏味的就从它上面的“最近更新”跳走。至今浏览器书签中“@MSN”栏目下仍存有大量书签，只是其中一些已经很久没有更新，另一些（甚至包括曾经的一些以MSN Space教程出名的blog）则被设置成为了限制访问。

　　时至今日，国内各种BSP大行其道，世界各种BSP叹息奈何。而Live Space退出世界，无疑让身在墙内的我又少了一种选择。

随感

……“既然空气可以循环利用，苍天可以由白变黑，那么，土地收归国有，岂不也是合理的吗？”猫公针砭时弊，道出了一串串永远耐人寻味的警句名言，诸如：“咱家不清楚使地球旋转的究竟是什么力量，但是知道使社会转动的确实是金钱……连太阳能够平安地从东方升起，又平安地落在西方，也完全是托了资本家的福。”“官吏本是人民的公仆、代理人，为了办事方便，人民才给他们一定的权力。但是，他们却摇身一变，认为那权力是自身固有而不容人民置喙。”猫公批评爱国精神说：“因为是精神，才常常恍恍惚惚。开国元勋有爱国精神，要价渔民有爱国精神，骗子、拐子、杀人犯也都有爱国精神。‘爱国精神！’中国人喊罢，像肺病患者似的咳嗽起来，百米之外，吭的一声。”猫公还敢于蔑视权贵，鼓励创新。他描画乌鸦在某伟人的石像上便溺，把雷锋的照片倒贴在墙上。他说：“不从胯下倒看莎士比亚，文学就会灭亡……”

——改编自于雷译夏目漱石《我是猫》前言

WRK: 对后备列表（Lookaside List）的机制分析

　　在Windows下开发内核程序，后备列表（Lookaside List）提供了一个比较简单的提高小块内存分配和申请效率的机制。根据DDK上的描述，后备列表用来进行固定大小内存块的动态申请和释放。并且在很多资料上，（比如KmdTut）在描述后备列表时会提到，Windows每一秒会对后备列表进行一次调整，根据后备列表的使用频度调整其深度。

　　原理

　　后备列表的原理很简单，就是一个控制结构头和一个由相同大小的内存块构成的单链表组成。在控制结构中，记录着当前后备列表的深度和最大深度。在通过ExAllocateFrom(N)PagedLookasideList申请内存的时候，如果单链表不为空，那么就从头部摘出一块返回，否则使用ExAllocatePoolWithTag或者在初始化后备列表时提供的分配函数申请一个内存块返回给用户；在通过ExFreeTo(N)PagedLookasideList释放之前申请的内存块时，如果后备列表当前的深度没有超过最大深度，那么插入到内存块头部，否则使用ExFreePoolWithTag或在初始化后备列表时提供的释放函数释放内存块。

　　由上可以看出，在调整后备列表深度时，只需调整管理结构的最大深度就可以了。事实上，在WRK中就是这么做的。初始化后备列表时，仅仅初始化了管理结构，至于内存块链表里的内存块，都是应用程序释放后加入的。

　　实现

　　先看一下数据结构，由于都是自注释的，就不解释了，反正就算有看不懂的也没涉及。

typedef struct DECLSPEC_CACHEALIGN _GENERAL_LOOKASIDE {

    SLIST_HEADER ListHead;
    USHORT Depth;
    USHORT MaximumDepth;
    ULONG TotalAllocates;
    union {
        ULONG AllocateMisses;
        ULONG AllocateHits;
    };

    ULONG TotalFrees;
    union {
        ULONG FreeMisses;
        ULONG FreeHits;
    };

    POOL_TYPE Type;
    ULONG Tag;
    ULONG Size;
    PALLOCATE_FUNCTION Allocate;
    PFREE_FUNCTION Free;
    LIST_ENTRY ListEntry;
    ULONG LastTotalAllocates;
    union {
        ULONG LastAllocateMisses;
        ULONG LastAllocateHits;
    };

    ULONG Future[2];
} GENERAL_LOOKASIDE, *PGENERAL_LOOKASIDE;

typedef struct _PP_LOOKASIDE_LIST {
    struct _GENERAL_LOOKASIDE *P;
    struct _GENERAL_LOOKASIDE *L;
} PP_LOOKASIDE_LIST, *PPP_LOOKASIDE_LIST;

　　在WRK中，后备列表相关的函数实现位于base\ntos\ex\lookasid.c；GENERAL_LOOKASIDE结构的定义位于base\ntos\inc\ex.h，这里包含了一个后备列表的管理信息；PP_LOOKASIDE_LIST结构定义于base\ntos\inc\ntosdef.h，在PRCB（处理器控制块，Processor Control Block）中用来提高内核内存池处理内存申请和分配的效率。

FORCEINLINE VOID ExpComputeLookasideDepth ( IN PGENERAL_LOOKASIDE Lookaside, IN ULONG Misses, IN ULONG ScanPeriod )

　　调整后备列表深度的函数见上，其大致原理为：

　　如果ExMinimumLookasideDepth为0，则说明使用了Verifier，在这种情况下后备列表将被禁用，其深度将被设置为0；

　　如果ExMinimumLookasideDepth不为0，那么：

if Allocates < (ScanPeriod * MINIMUM_ALLOCATION_THRESHOLD) then
    Depth = min(Depth-10, MINIMUM_ALLOCATION_DEPTH);
else
    Allocates = Lookaside->TotalAllocates – Lookaside->LastTotalAllocates;
    Ratio = Misses * 1000 / Allocates;
    if Ratio < 5 then
        Depth = min(Depth-1, MINIMUM_LOOKASIDE_DEPTH);
    else
        Delta = min(30, Ratio *(MaximumDepth – Depth)/2000 + 5;
        Depth = min(Depth+delta, MaximumDepth);

　　那么，ExpComputeLookasideDepth是如何找到所有的后备列表呢？在base\ntos\ex\lookasid.c定义了四个单链表：ExNPagedLookasideListHead、ExPagedLookasideListHead、ExPoolLookasideListHead和ExSystemLookasideListHead。

　　Ex(N)PagedLookasideListHead用来保存用户定义的后备列表，（此操作在初始化后备列表的管理结构时进行，ExInitialize(N)PagedLookasideList）ExPoolLookasideListHead用来保存PRCB中的PP(N)PagedLookasideList，ExSystemLookasideListHead用来保存PRCB中的PPLookasideList和其它一些后备列表。

　　调整后备列表的操作由Balance Set Manager（base\ntos\ke\balmgr.c）在一个单独的系统进程中调用，它每一秒调用一次ExAdjustLookasideDepth。ExAdjustLookasideDepth按3秒为一个周期，分别对ExPagedLookasideListHead、ExNPagedLookasideListHead和系统后备列表进行调整。系统后备列表不仅包括上文提到的ExPoolLookasideListHead和ExSystemLookasideListHead，还包括在base\ntos\ex\lookasid.c定义的ExpSmall(N)PagedPoolLookasideLists两个链表。

　　调整的算法如前所述，其中比较奇怪的一点是，ExPoolLookasideListHead并未在ExAdjustLookasideDepth被引用，而是直接引用PRCB中的PP(N)PagedLookasideList；另外在PP_LOOKASIDE_LIST结构中有两个GENERAL_LOOKASIDE指针P&L，但却只对PRCB里PP(N)PagedLookasideList中P指向的后备列表进行深度调整。

　　在Kernel Memory Pool中的使用

　　在使用ExAllocatePoolWithTag申请内存时，系统会首先尝试从PRCB中的PP(N)PagedLookasideList。PRCB中的后备列表中保存了大小从0 × 8B到POOL_SMALL_LISTS(32) × 8B的后备列表。在分配内存时，后备列表中的内存块只满足大小符合的要求，否则不予处理。（申请的大小先按8字节对齐）

　　因为在PRCB中使用的每个PP_LOOKASIDE_LIST有两个指针P&L，在申请时将先尝试P指向的GENERAL_LOOKASIDE，失败后再尝试L指向的GENERAL_LOOOKASIDE；如果再失败，则通过正常方式从内存池中申请内存。在释放内存时也是同样。

　　其他的一些说明

　　ExMinimumLookasideDepth是一个全局变量，用来控制后备列表的最小深度，后备列表在初始化时的深度会被设为此值。

　　PRCB中的PP(N)PagedLookasideList在Phase 0使用ExpSmall(N)PagedPoolLookasideLists进行初始化，每一项的P&L都指向同一个GENERAL_LOOKASIDE；在Phase 1的时候，PP(N)PagedLookasideList会被重新初始化，这时P&L将指向两个不同的后备列表。

　　Verifier的介绍请参见Windows Internal一书，本文暂不做说明，留到写Memory Pool一文再做说明。

　　PS. 后备列表的译名来自KmdTut，潘爱民书中的“快查表”和软件调试中的“旁视列表”两个翻译实在太难听了。

事关工作

　　终于，我到某外资网游公司，开始了久违的实习。

　　上班时间倒是宽裕，每天早上九点半之前到即可，五分钟内的迟到不算数；下班时间是一小时午餐时间加上八小时工作时间。即使像我每天的通勤时间在两小时，早上七点前起床也绰绰有余。

　　但是最近下班时间却越来越晚，从初始的八点，渐渐到九点才离开公司，现在已经变成了九点半到十点才站起来。而上周日，还搭乘了最后一班地铁——结果倒车时被告知另一条线没车，只好打车回学校。

　　一直告诉自己，工作之后也要抓紧时间学习，要多看书，多思考。不过照现在这个样子，每天过半的时间在工作和通勤中度过，还能不能学点什么、想点什么，倒是一个值得怀疑的问题。

　　以后早上六点半起床，看看书写点文字，八点出发；晚上八点下班，最迟八点半，回来后还能看会书，做点毕设工作。

　　要坚持可持续发展，保重身体要紧。

实习开始——入职第二天

　　昨天入职，上午办手续，下午学习了公司组织结构，然后是TeamBuilding。只是一同入职的人太多，最后没能认识几个人。

　　实习待遇还可以，只是石景山万达广场虽然繁华，但周围东西太贵。昨天中午吃的KFC，今天中午吃的吉野家，一顿饭都要二十块钱左右，量却只刚好。现在我能理解为什么在学校有那么多在周围工作的人来挤着吃饭。至于晚餐，公司提供工作餐还凑合，只是肉类总是炸的肉条和丸子。

　　今天的培训介绍了公司的文化和制度。制度貌似比较简单，除了个别比较复杂的条目。至于文化，主要就是十六个字：

主动·执行 团结·进步 坚持·挑战 传承·制度

　　说实话，在大学别的没学到，唯一学到的东西——或正在学到的东西——就是独立思考，尤其是“毛泽东思想 邓小平理论和三个代表重要思想”这门课，因此我对“洗脑”的抗性还算蛮高。大一时参加过华硕公司文化的培训，去年找工作也参加了一些宣讲会。和这些公司文化相比较，总而言之，它们的共同点就是：做个好员工。:P

　　比如“主动”指的是先知先觉，而这一条正好和华硕的“常山蛇”（注意不是“长山蛇” XD）精神相吻合。

　　有区别的地方多是提出的方式、比喻的对象，以及各家公司可能对于个别细节的重视程度。

　　在公司理论课上我学到：公司文化理论——为什么需要有公司文化。任何一家公司，为人处世有它独有的统一的方式，因此它需要它的员工能够认同它所秉承的文化。（虽然大多时候都是“公司利益至上”）不然各走各路，人心散了，队伍也就不好带了。因此，一家公司做大之后，一定要将其文化形于文字、形于口号，这样才能维持员工的向心力和一致性。

　　培训时Garry说：进入一家公司，如果你能认同它的文化，那么你会有很大收获；如果你不能认同它的文化，那么你需要想想你要从这家公司得到什么。

　　我认同搜狐畅游的公司文化吗？当然了，公司文化不可能和做一个“五讲四美不热爱”的人所需要的品质相背离。（也许除了“公司利益至上”，但这条却符合我的利益，因为我是它的员工）

　　哦，对了。等这周培训完入职后，应该需要玩一周的“天龙八部”。嘿嘿，工作需要。

　　另外，会分到哪个部门呢？希望是反木马外挂。（有这个组吗？）

Google不作惡，誰做了？

　　不久之前，Google在其官方blog發布了一篇日志，文中提到將就信息審查的事情同中國大陸政府磋商，倘若磋商失敗，Google將退出中國。此文一出，在世界范圍內激起千層浪。

　　眾所周知，Google是一家以奉行“Don’t Do Evil”出名的商業公司。因此Google詞份聲明一發出，對中國大陸政府的聲討是不絕于耳。尤其是對于聲明中關于Google所提到的全球若干大公司受到網路攻擊以及Google的智慧產權被盜事件，更是出現了若干不同版本的演繹。

　　對于這些受到網路攻擊的公司以及知識產權被盜的Google，作為一個中國人，我感到十分遺憾。

　　但因為Google不作惡，它就一定站在正面立場嗎？我認為，這個推論是錯誤的，因為前提是錯誤的。Google真的不作惡嗎？

　　用GTalk，我找了個只有一個可執行文件的版本。剛打開，提示我版本過期，是否要更新。我選暫不更新。但下次再登入GTalk，Comodo Firewall的Defence+卻提示我是否允許GTalk的安裝程序運行。允許運行后，GTalk自動在%ProgramFiles%下安家落戶。這是一家號稱“Don’t Do Evil”的公司所應該有的作為嗎？在用戶選擇不更新后由后臺自動下載安裝，那么用戶的選擇還有什么用。

　　也許GTalk的事情算不了什么，但Android呢？Android是一個開放源代碼的操作系統，而且能夠和GTalk、GMail、Youtube等Google提供的服務進行無縫整合。一個網友下載了Android的源代碼，然后整合進了GTalk、GMail、Youtube等Google提供的服務后作為一個新的發行版供公眾下載，卻收到了Google的律師函，要求發行版中移去GTalk、GMail、Youtube等服務。移除了這些服務，Android還是那個Android嗎？這也是“Don’t Do Evild”？

　　我一向相信：“人之初，性本利”，而且從不憚以最壞的惡意來猜測別人。因此Google所謂的“Don’t Do Evil”只不過是它用來生利的一個方法——雖然它多數時候的行為還是能夠符合這一準則，但卻并不能將Google樹立成為一個正面立場的標桿。因此，看到有些人因為中國大陸政府和Google作對就拼盡全身力氣批判中國大陸政府，我真是覺得可笑。這些人口口聲聲說著為了自由民主，自己卻都未養成獨立思考的習慣。中國的民主之路還有很長要走。

　　Google退出中國這件事，中國大陸政府的錯不在于站到了Google的對立面，而在于其實行的信息封鎖政策。哪怕用中國的傳統思維，官是父母官。作為一家之長，卻不允許說家長不喜歡的話、不允許想家長禁止想的事。每當思想政治課程上總說過去如何獨裁，可如今自己卻又隱隱站在人民對立面上。

　　改革開放這么多年，卻似乎又走回去了。現在我國除了比北朝鮮人生活好些、出國容易些，和北朝鮮的大體環境似乎差別不大。

深入Windows – WRK学习手记（1）：实验环境搭建

　　WRK: Windows Research Kernel，微软开放的Windows 2003 Server 32-bit和Windows XP 64-bit内核源代码，用于教学目的，and all rights reserved by Microsoft。MSDNAA注册用户可以从网上下载。（至于非注册用户距离其有google一步之遥）

　　首先搭建一个实验平台，我使用的环境如下：WRK-v1.2，Windows 2003 Server 32-bit，VMWare Workstation。编译内核很简单，按照说明文件一步一步来就可以了，所有需要的文件都在WRK中。或者直接使用如下的批处理文件，需要注意%wrk%为WRK路径，而且路径中不能有空格，不然make时会出错：

set wrk=D:\SourceCode\WRK\wrk-v1.2
set arch=x86
path %wrk%\tools\%arch%;%path%
cd %wrk%\base\ntos
nmake -nologo %arch%=

　　Make之后，会在%wrk%\base\ntos\build\exe产生wrkx86.exe和wrkx86.pdb两个文件。wrkx86.exe就是需要的内核文件，wrkx86.pdb是符号表。然后在虚拟机命令行中，使用如下命令：

link -dump -all \WINDOWS\system32\hal.dll | findstr pdb

　　查看Guest OS的HAL类型，其对应关系如下：

halacpi.pdb   -> halacpim.dll          ACPI PIC-based PC  [used by VirtualPC]
halaacpi.pdb -> halmacpi.dll          ACPI APIC-based PC
halapic.pdb   -> halmps.dll            MPS

　　例如在我的虚拟机中运行后输出如下：

C:\x86>link -dump -all \WINDOWS\system32\hal.dll | findstr pdb
  80011350: 70 64 62 00 00 00 00 00 00 00 00 00 00 00 00 00  pdb………….
    42435B34 cv           24 00001330      730    Format: RSDS, {5665606C-2986-4
14A-94A0-34287C395D2B}, 1, halacpi.pdb

　　那么我所需要的就是halacpim.dll

　　然后从%wrk%\WS03SP1HALS\x86中复制相应的dll和wrkx86.exe复制到Guest OS的%windows%\system32下，修改boot.ini，添加一行（主要是”/kernel=wrkx86.exe /hal=halacpim.dll”）：

multi(0)disk(0)rdisk(0)partition(1)\WINDOWS="WRK 1.2" /kernel=wrkx86.exe /hal=halacpim.dll

　　重启，启动菜单中会多出来一个“WRK 1.2”的选项。选中后回车，如果能成功启动则说明编译的WRK成功。

　　接下来创建双机调试环境。

　　首先在VMWare中修改虚拟机选项，在Hardware Tab中添加新串口，选择“Output to a named pipe”，名字输入\\.\pipe\dk_2k3。然后在Guest的设备管理器中设置添加的COM1，波特率设为115200。然后编辑boot.ini，在复制刚才添加的那一行，在末尾加上（debugport按实际com端口而设）：

/kernel=wrkx86.exe /hal=halmacpi.dll /debug /debugport=com1 /baudrate=115200

　　在Host的WinDBG中创建快捷方式，加入如下参数：

-b -k com:pipe,port=\\.\pipe\dk_2k3,baud=115200,reconnect -y D:\Symbols\WindowsWRK;srv*D:\Symbols\WindowsWRK*http://msdl.microsoft.com/download/symbols -srcpath "D:\SourceCode\WRK\wrk-v1.2\base"

　　部分参数含义如下：

-b：一旦主机与目标机建立连接则中断目标机。
-k：内核调试。
com：设置通信端口和波特率。
-y：设置文件符号路径。

　　然后重启Guest，选择刚才添加的DEBUG启动选项，并打开刚才创建的快捷方式。如果连接建立，就能看见Guest被中断下来，并在WinDBG中看到断点处对应的源代码。

　　Enjoy it, and have a sweet dream~