问题  

   上周开始，我们一个已经在线运行了快2年的游戏突然频繁宕机，宕机前刚好上了一个资料片，提交了大批量的代码。
比较麻烦的是宕机的core文件里没有任何有效CallStack信息。在随后的多次宕机core文件里也都找不到有效的CallStack信息，定位问题变得无从入手。

原因
 

   根据经验，这是一个典型的栈破坏问题。一旦栈破坏了函数返回值后，堆栈完全是错乱的，得不到任何有效信息。
最开始我建议项目组的同事查看最近提交的代码，看看能否找到线索。不过由于近一个月提交的代码实在太多，大海捞针了一段时间后，
毫无头绪。
   栈覆盖一般是因为memcpy或者是循环赋值语句导致的，一般栈覆盖的层次不会太多，所以从底部往上找，应该能找到些有效的线索。
不过，由于服务器函数经常会有Package的临时变量，导致函数栈很大，从下往上找线索也很困难，很多似是而非的合法地址很容易分散精力。

解决

  按照上面的分析，从底部往上找是大海捞针，那么从顶部往下找如何呢？
这里先说明下一般函数堆栈帧的建立(未优化情况下的用户函数):
push rbp
mov rbp, rsp
从这里可以看出，本层函数的返回值是存储在 [rbp + 8]，而上层函数的rbp地址则存储在 [rbp]。
所以，从下网上找的时候，可以根据rbp逐步找到上层函数和上层函数的堆栈帧。

那么如何往下找呢，假如知道了一个上层函数的rbp，如何获取下层函数呢，
这里有个小窍门，gdb7.X的版本有一个find功能，可以在内存区域搜索数值，
从上往下找的时候，可以在堆栈查找本层 rbp的存放地址，从而确定下层函数rbp的存放地址。
举个例子:

#0  0x00007ffff77d7830 in nanosleep () from /lib/x86_64-linux-gnu/libc.so.6

#1  0x00007ffff77d76ec in sleep () from /lib/x86_64-linux-gnu/libc.so.6

#2  0x000000000040070a in test1 () at main.cpp:9

#3  0x0000000000400715 in test () at main.cpp:14

#4  0x000000000040072b in main (argc=1, argv=0x7fffffffe648) at main.cpp:19

这是一个典型的CallStack,让我们先找到0x000000000040072b的堆栈信息吧。
先 info r 查看当前的寄存器信息:

得到 rsp为0x7fffffffe358

find $rsp, +0x300, 0x000000000040072b

0x7fffffffe548

1 pattern found.

只有一个地址，那么存放rbp的地址就是0x7fffffffe540了，

继续 find $rsp, +0x300, 0x7fffffffe540

0x7fffffffe530

1 pattern found.
验证下是否正确：
x/10xg 0x7fffffffe530

0x7fffffffe530: 0x00007fffffffe540      0x0000000000400715

0x7fffffffe540: 0x00007fffffffe560      0x000000000040072b

0x7fffffffe550: 0x00007fffffffe648      0x0000000100000000

看到了吧，就是这样找到了下一级的函数。
真实环境中往往没这么简单，有时候会找到好几个地址，这个时候需要自己逐个去伪存真了。

 

  写这篇文章是对自己2011bug战斗时光一个交代，随着时间的推移，当初印象深刻的痛苦和压力慢慢消逝，到现在甚至是需要很长时间来弄清楚这中间的关系，趁着现在头脑还算清楚，记录下吧。

场景管理

问题表现  

原因

 

 

 

        2011已经谢幕了，现在都流行总结，要是让我总结2011，可以用2个词来概括，辛苦、刺激。
辛苦是因为2011基本上是加了一年班，从过完年开始，到2012年过年前最后一周，这一年来，是我感觉最辛苦的一年，好在最终
项目算是打了个翻身仗，心里总算有了些慰藉。

       2011年游戏经历从技术封测、内测、公测到整改、重新内测公测，一路走来，遇到无数稀奇古怪的Bug，
有时候压力大的时候，晚上都睡不着，脑子里回想着现场的一丝丝蛛丝马迹，希望能找到bug的原因，经历过无数次绝望到重生的喜悦，也有被猜忌不信任的痛苦，活脱脱就是一部部侦探剧情。
  没有从事过游戏开发或者游戏没上线的同学很难理解:bug有这么难找吗？的确，如果是简单的空指针宕机，当然是好找的，用我们的话，这类问题是个傻子都能解决(其实不然，很多时候直接原因是空指针，
真正的原因隐藏很深)，但是更多的是隐藏很深的问题，需要反复的分析现场，假设剧情才能得到灵感，然后推演，才可能得到结果，当然，这个和游戏逻辑的复杂度是分不开的。
  具体的bug细节不便在此分析，但是大部分的问题，其实都是因为不正常的设计引起的，所以其实我一直在思考，在软件开发领域，其实也存在着"道",说通俗点叫客观规律，不按照道行事，迟早是要受到惩罚的。
但是在游戏后台开发中，很多时候存在不同技术方案的矛盾，难以让人取舍，这些矛盾都是真实在很多项目存在的。

动态内存还是静态内存

      很多开发者由于担心内存泄露，在项目中禁止使用动态内存(当然这实际上几乎是做不到的)，使用对象池来避免动态内存，就是预先创建预计最大数量的对象，后续申请和归还的时候，都是操作对象池，
避免动态new和delete。这样的项目还不少，我见过的就好几个。对象池的好处是显而易见的，基本上可以避免内存泄露。但是实际上，这种方式是把双刃剑，个人觉得在游戏项目中，这种方式弊大于利。
主要弊端有下面几点：
1、开发不方便，导致需要添加很多的对象池管理类，即使有模板帮忙，也是非常繁琐的。实际开发中，几乎不可能对这些小对象类都搞一个对象池管理类。

2、由于采用预先生成对象，一般会预估一个对象可能存在的最大数量，然后按照最大数量来创建，浪费内存。
  的确，你没有内存泄露，但是你启动的时候就需要好几个G的内存，这个是内存浪费，好在现在server开发基本都是64位，没有地址空间的困扰了，但是，在大部分情况下浪费好几个G的内存，
光想想都有点心疼。

3、引入了新的风险，由于采用对象池，申请新对象的时候，只是简单的pop一个空闲对象就可以了，很容易漏掉对象初始化的工作，在回收对象的时候，大部分开发者也很容易漏掉清理工作，或者初始化和
清理工作过于简单，这样容易导致新对象被历史操作影响。曾经遇到过一个新FB所有传送点都打不开的问题，就是因为历史对象回收时数据没清理导致的。

    回头来看对象池的优点，很多开发者坚持是为了解决内存碎片和内存泄露。先说内存碎片，暂且不说内存碎片真的是否有这么严重，退一步，其实内存碎片已经有很多的成熟解决方案了，自己重载smallObject还是
采用标准的tcmalloc解决，都是非常轻松的。至于内存泄露，个人觉得这个问题其实是很好查的，也是c++程序员的基本要求。

分模块针对接口编程还是一锅粥

     这个问题单独提出来，几乎所有人都会说，当然是分模块针对接口开发了。和天下所有的事情一样，知易行难。由于游戏逻辑项目影响的地方非常多，比如死亡的时候，既需要判断死亡掉落，又需要处理任务状态，
如果在战场和竞技场中，还要判断基数和得分等等，这就导致很多开发者不假思索的把所有的东西都揉在一起，你中有我，我中有你，我改你的代码你改我的。
一个最简单的例子，我在项目中开发掉落功能，当把物品添加到玩家背包后，发现客户端没有更新背包，一查，居然还需要掉落的开发者自己构造数据包同步客户端，其实作为其他模块，根本不关心背包数据同步的细节。
这个其实在现实生活中很常见，我委托背包模块添加一个物品，具体的细节是被由被委托人来负责的。将过多的细节交给其他模块处理，会导致复杂度增加，容易出现问题，对其他人来说，也是一个精力浪费，如果是一个复杂
模块，你会发现需要了解太多的细节，修改太多自己不熟悉的代码，进而导致风险。还有一种观点，认为一锅粥的开发方式有助于了解游戏的各个业务模块，对这种观点，我是不以为然的，每天陷入到繁琐的细节，真的对熟悉业务有好处吗？或许闲下来玩玩游戏更有帮助，而且，这么乱的代码，看起来也是非常累的。分模块开发，具体的办法，游戏编程精粹5上有篇文章写得很好，这里不扩展了。

真的需要禁用STL吗

  不止一次在和其他项目交流的资料里看到对方很威严的宣称在项目里禁止使用STL。说实话，我还真没觉得STL有什么不好。见过太多这类项目自己重复实现一个个蹩脚的排序算法、容器等等。
大部分人一般都会根据经验选择使用自己熟悉的技术，这个无可厚非，但是像这样明着禁止使用STL，真不知道如何能理直气壮。其实大部分不用STL的理由，基本上都是不熟悉，完全没有足够的理由禁止使用。

游戏开发无技术含量？
 
    曾经多次听到行业内的兄弟有此感慨，确实，游戏逻辑复杂度非常高，架构上大部分都是类似的。但是这并不说明游戏后台开发复杂度不高，如何将游戏开发逻辑复杂剥离开来，做到稳定高效开发，其实还是有很多
东西可以探讨的，看看那些项目，大部分都是一锅粥，需要什么功能就蛮干，加上去，这样确实毫无技术含量，都是蛮干。所以，一件事情是否有技术含量，不光是看事情本身，还要看怎么干，蛮干和苦干，那是最没有技术
含量的方式了，程序员还是要有强烈的“偷懒”意识。

 

 问题

   最近游戏开始技术封测了，不过刚刚上线3个小时，Server就挂了，挂在框架代码里，一个不可能挂的地方。
从CallStack看，是在获取数据时发送请求包的时候挂的，由于框架部分是其他部门的同事开发的，所以查问题的时候就拉上他们了，
大家折腾了2天，没有实质性的进展，服务器还是基本上每3个小时宕机一次。由于上层逻辑大部分都在我那，所以压力比较大，宕机的直接原因是hashtable的一个桶的指针异常，
这个hashtable是框架代码的一个内部成员，按道理我们是无从破坏的，只有可能是多线程环境下迭代器损坏导致的。
但是框架代码在这个地方确实无懈可击，所以真正的原因应该还是上层代码破坏了堆内存，很可能是一个memcpy越界导致的。这毕竟是个猜想，如何找到证据呢，这是个问题。
把所有代码里的memcpy浏览了一遍，没有发现明显问题。

猜测

  一般游戏中比较容易出现但是不好查的问题很多时候都是脚本（lua）导致的，我们的脚本部分是一个同事几年前写的，在几个产品中都使用过，按道理没这么脆弱，不过老大还是和最初开发这个模块的部门沟通了下，
还真发现问题了，赶紧拿了新的版本更新上去。经过一天的观察，服务器没有宕机了，OK，问题碰巧解决了,背了这么久的黑锅，终于放下来了。

PageHeap

   假如没有碰巧解决了这个问题，正常的思路该如何解决这个问题呢，这个时候我怀念windows了，在windows下有PageHeap来解决这类写越界的问题。基本思路就是每次分配内存的时候，都将内存的结尾放在页的边缘，紧接着这块内存分配一块不能写的内存，这样，一旦写越界，就会写异常，导致宕机。linux下没有现成的工具，但是linux提供了mmap功能，我们可以自己实现这样一个功能，当然，这一切都不用自己动手了，tcmalloc已经包含了
这个功能了，不过在文档里基本没有介绍，我也是在阅读tcmalloc代码时看到的，这个功能默认是关闭的，打开这个开关需要改写代码：

这个代码在debugallocation.cc里：

DEFINE_bool(malloc_page_fence,
            EnvToBool("TCMALLOC_PAGE_FENCE", false),
            "Enables putting of memory allocations at page boundaries "
            "with a guard page following the allocation (to catch buffer "
            "overruns right when they happen).");
把false改成true就可以了。
想要在项目里加入PageHeap功能，只需要链接的时候加上 -ltcmalloc_debug即可。把它加入项目中，试着运行下，直接挂了，
仔细一看，原来是项目中很多成员变量没有初始化导致的，tcmalloc_debug会自动将new 和malloc出来的内存初始化为指定值，这样，一旦变量没有初始化，很容易就暴露了。
修改完这个问题后，编译，再运行，还是挂，这个是mprotect的时候挂的，错误是内存不够，这怎么可能呢，其实是达到了资源限制了。
echo 128000 > /proc/sys/vm/max_map_count
把map数量限制加大,再运行，OK了！
 
  但是游戏Server启动后，发现一个问题，CPU长期处于100%，导致登陆一个玩家都很困难，gdb中断后，info thread，发现大部分的操作都在mmap和mprotect,最开始
怀疑我的linux版本有问题，导致这2个AP慢，写了测试程序试了下，发现其实API不慢，估计是频繁调用导致的。
所以得换种思路优化下才可以，其实大部分情况下，我们free的时候，无需将页面munmap掉，可以先cache进来，下次分配的时候，如果有，直接拿来用就可以了。
最简单的cache算法就是定义一个void* s_pageCache[50000]数组，页面数相同的内存组成一个链表，挂在一个数组项下，这个很像STL的小内存处理，我们可以将mmap出来的内存的
前面几个字节(一个指针大小)用于索引下一个freePage。当然这个过程需要加锁，不能用pthread的锁（因为他们会调用malloc等内存分配函数），必须用spinlock，从linux源码里直接抄一个过来即可。
static void*   s_pagePool[MAX_PAGE_ALLOC]={0};

malloc的时候，先从pagePool里面获取:
// 先从pagePool找
 void* pFreePage = NULL;
 spin_lock(&s_pageHeapLock);
 assert(nPageNum < MAX_PAGE_ALLOC);
 if(s_pagePool[nPageNum])
 {
   pFreePage = s_pagePool[nPageNum];
   void* pNextFreePage = *((void**)pFreePage);
   s_pagePool[nPageNum] = pNextFreePage;
 }
 spin_unlock(&s_pageHeapLock);

free内存的时候，直接放到pagePoll里:
spin_lock(&s_pageHeapLock);
 assert(nPageNum < MAX_PAGE_ALLOC);
 void* pNextFree = s_pagePool[nPageNum];
 *(void**)pAddress = pNextFree;
 s_pagePool[nPageNum] = pAddress;
 
 spin_unlock(&s_pageHeapLock);

编译、运行,OK了，CPU迅速降下来了，空载的时候不到1%,而且也能达到检测写溢出的问题。

  最近项目开始集中测试了，服务器程序经常crash，由于服务器一般情况下都是关闭了core的，所以好几次都只能通过杂乱的日志来定位问题。
当然，我们可以通过ulimit来打开core开关，不过这可能带来新的问题：我们的服务器程序每个core文件大概有1G多，测试期间如果频繁crash,没有注意及时清理，一不小心就会把磁盘写满，
而且core文件毕竟是和进程程序相关的，有时候找相应版本也是个麻烦事。

能否在程序crash的时候，将callStack以及参数和局部变量都记录到日志里？
这个技术其实在游戏客户端已经用了很多年了，一般游戏客户端crash后，都会弹出一个是否发送错误的选择框，其实就是发送的CallStack的日志和MiniDUmp文件。
要想记录CallStack就必然涉及到Stack的遍历，linux下的Stack遍历使用很简单，简单的backtrace就可以搞定，man backtrace就有现成的例子，
这比windows下复杂的头疼的StackWalk好用的多。

解决了Stack遍历问题后，还剩下一个问题：如何在程序crash的时候得到通知执行我们自己的dump代码？
在Windwos下有SEH异常来实现这个功能，而linux下可以通过使用信号在进程crash的时候执行自己的处理代码。

好了，开始写个简单代码测试下:
首先设置几个主要crash信号的处理函数
signal(SIGSEGV, &DumpHelper::OnCrash);
signal(SIGABRT, &DumpHelper::OnCrash);
signal(SIGFPE, &DumpHelper::OnCrash);

在OnCrash里我们用前面提到的backtrace系列函数，来记录堆栈:
void* szStackFrame[100];
int nFrameCount = backtrace(szStackFrame, 100);
char** strFrameInfo = backtrace_symbols(szStackFrame, nFrameCount); 
char szDumpFileName[1024] = {0};
snprintf(szDumpFileName, sizeof(szDumpFileName), "dump_%u.log", (unsigned int)time(NULL) );
FILE* pFile = fopen(szDumpFileName, "wb");
if(!pFile) return;
for(int i = 0; i < nFrameCount; i++)
{
    fprintf(pFile, "%s\n", strFrameInfo[i]);
}
fclose(pFile);
free(strFrameInfo);

接着，设置几个嵌套调用的函数：
void fun()
{
 //assert(0);
 int* p = NULL;
 *p =3;
}

void fun1()
{
 fun();
}

void fun2()
{
 fun1();
}

void fun3()
{
 fun2();
}

最后，我们在main函数里执行fun3,注意编译的时候带上-rdynamic 选项。

运行下，果然可以打印基本的堆栈，不过马上，发现了新的问题：这个堆栈信息也太简陋了，只有调用函数的名字，其余的参数、局部变量完全没有，
这个和gdb能看到的callStack差距也太大了。
解决这个问题最简单的办法就是用gdb来打印堆栈,在这里，gdb和其他程序有区别，如果你试图通过 echo "bt"|gdb -p XXX>a.txt来获得堆栈，那将会非常失望，
根本不起作用，google了下，基本没什么解决办法。
不过gdb 可以从文件读入指令，例如 gdb XXX<cmddata，这给了我们机会，
system("echo  \"bt full|gcore\">testcmd");
  char dbx[160]={0};
     sprintf(dbx, "gdb -p %d ./main<testcmd >gdbdump_%d.log", getpid(), getpid() );
  system(dbx);

测试运行，发现可以打印详细的堆栈，不过，要求机器上有gdb.
上面的命令还dump了一个core文件，不过这个core文件的堆栈信息是错误的，我不知道为什么。。。。

多线程环境下使用上述办法，只能输出一个线程的堆栈，需要先获取线程数目，然后逐个线程打印堆栈。

最后，为了避免影响正常的coredump,要在OnCrash的处理函数里将信号的处理函数设置为默认。
如果我一定要有core呢，setrlimit吧，去掉core限制即可。

   我们的新项目是在linux平台下运行的，本人是Linux和windows下都开发过，我呆的2个linux后台项目都是所有代码放在一块，编译成一个可
执行文件，基本不考虑编译成动态库，所有代码的头文件依赖也是一团糟，随着项目的增大，编译速度越来越慢，到后来编译一个项目4进程同时编译都需要10来分钟。
 
  其实分析下可以发现，主要的编译速度损耗在头文件上，尤其是模板相关的头文件。VC有一个预编译头文件技术，将常用的公共头文件放在一起，预先编译成pch文件，这样
可以加快编译速度。gcc到底有没有类似技术呢，打开gcc的手册搜索了precompiled，发现还真有相关介绍，使用方法也很简单。
 
主要是以下步骤：
  1、在项目下建立一个 stdafx.h的文件，包含了大部分公共头文件。在每个cpp最开始都#include "stdafx.h"。cpp文件包含了这个预编译头文件后，就可以将原来和
stdafx .h 里头文件重复的内容删除了，尤其是模板相关的头文件，另外，非PCH的头文件里尽量少包含其他头文件。     
  2、修改makefile文件, 加入OBJ对 gch的依赖,用一个简单的项目做示例，一看就明白
   
    完成以上内容后，make clean,再重新编译，初步估计只需要2分钟！！  整整优化了4-5倍。
      

  最新换了个项目组，阅读代码后，发现Server端代码居然没有事件和定时器。由于没有事件，所以各个模块代码互相调用的地方特别多，导致代码结构混乱，所有代码都放在一块，乱成一锅粥了。
没有定时器，所有需要定时的任务，都只能添加类似OnUpdate的函数，在主循环的时候执行。定时需求少的时候，看不出明显的问题，但是一旦这种需求多了，尤其是很多内部对象有定时需求的时候，
这个问题就比较明显了，写好了OnUpdate后，还要建立一条从主循环MainLoop到自身OnUpdate的调用链。
 
  事件其实就是一个广播和订阅的关系，Delegate就是实现这样一套机制的利器，目前Delegate的实现主要有2种，一种是CodeProject上的一个FastDelegate实现，另外一个比较典型的实现就是boost的
实现了，无论采取哪种实现方案，实现难度都不算太大。
  Server当前框架对定时器无任何支持，只有一个DoMainLoop的函数可以派生来运行自己的定时逻辑。
  我原来都是用的ACE封装的组件，用了一段时间也没发现明显问题，不过ACE的定时器不太适合在这个新项目用，主要原因有如下几点：
  1、ACE库太大了，不想仅仅为了定时器引入一个这么庞大的库。
  2、ACE的定时器需要额外启动一个定时器线程，定时任务是在定时器线程跑的，而我们的项目逻辑其实是在单个线程运行的，如果直接采用ACE定时器，会给逻辑带来额外的复杂度。由于整个逻辑线程的框架是公共模块，手头也没有代码，所以将定时器线程的任务发送到主逻辑线程运行也是不可行的。
  3、ACE的定时器有很多种，TIMER_QUEUE、TIMER_WHELL、TIMER_HEAP等，个人感觉这些定时器的插入、取消操作都比较耗时，加以改装放到主线程run的带价将会很大。

其实linux内核就有一个比较高性能的定时器，代码在kernel/Timer.c里， 2.6内核的定时器代码更是简洁。
linux的定时任务都是以jiffie 为单位的，linux将所有定时任务分为5个阶梯，
struct tvec {
    struct list_head vec[TVN_SIZE];
};

struct tvec_root {
    struct list_head vec[TVR_SIZE];
};

struct tvec_base {
    spinlock_t lock;
    struct timer_list *running_timer;
    unsigned long timer_jiffies;
    struct tvec_root tv1;
    struct tvec tv2;
    struct tvec tv3;
    struct tvec tv4;
    struct tvec tv5;
} ____cacheline_aligned;

对一个新的定时任务，处理方法如下:
static void internal_add_timer(struct tvec_base *base, struct timer_list *timer)
{
    unsigned long expires = timer->expires;
    unsigned long idx = expires - base->timer_jiffies;
    struct list_head *vec;

    if (idx < TVR_SIZE) {
        int i = expires & TVR_MASK;
        vec = base->tv1.vec + i;
    } else if (idx < 1 << (TVR_BITS + TVN_BITS)) {
        int i = (expires >> TVR_BITS) & TVN_MASK;
        vec = base->tv2.vec + i;
    } else if (idx < 1 << (TVR_BITS + 2 * TVN_BITS)) {
        int i = (expires >> (TVR_BITS + TVN_BITS)) & TVN_MASK;
        vec = base->tv3.vec + i;
    } else if (idx < 1 << (TVR_BITS + 3 * TVN_BITS)) {
        int i = (expires >> (TVR_BITS + 2 * TVN_BITS)) & TVN_MASK;
        vec = base->tv4.vec + i;
    } else if ((signed long) idx < 0) {
        /*
         * Can happen if you add a timer with expires == jiffies,
         * or you set a timer to go off in the past
         */
        vec = base->tv1.vec + (base->timer_jiffies & TVR_MASK);
    } else {
        int i;
        /* If the timeout is larger than 0xffffffff on 64-bit
         * architectures then we use the maximum timeout:
         */
        if (idx > 0xffffffffUL) {
            idx = 0xffffffffUL;
            expires = idx + base->timer_jiffies;
        }
        i = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK;
        vec = base->tv5.vec + i;
    }
    /*
     * Timers are FIFO:
     */
    list_add_tail(&timer->entry, vec);
}
从上可以看到Linux对定时器的处理：对即将在TVR_SIZE 个jiffies内到达的定时任务，将它挂到第一组tv1 下，具体就是挂到expires & TVR_MASK 对应的列表上去。
同一个jiffies到达的定时器是挂在同一个链表的。
同理，挂到第二个组的是 到期时间小于 1 << (TVR_BITS + TVN_BITS) jiffies的。
挂到第三个组的是 到期时间小于1 << (TVR_BITS + 2 * TVN_BITS) jiffies的。
挂到第四个组的是 到期时间小于 1 << (TVR_BITS + 3 * TVN_BITS) jiffies的。
超过1 << (TVR_BITS + 3 * TVN_BITS) 的挂到第五组。
这样，所有到期的任务都会在第一组。任何时刻都可以直接通过当前jiffies&TVR_SIZE 来找到需要运行的定时器任务列表，定时器的插入效率就是O(1)。

下面是定时器的运行代码：
static int cascade(struct tvec_base *base, struct tvec *tv, int index)
{
    /* cascade all the timers from tv up one level */
    struct timer_list *timer, *tmp;
    struct list_head tv_list;

    list_replace_init(tv->vec + index, &tv_list);

    /*
     * We are removing _all_ timers from the list, so we
     * don't have to detach them individually.
     */
    list_for_each_entry_safe(timer, tmp, &tv_list, entry) {
        BUG_ON(tbase_get_base(timer->base) != base);
        internal_add_timer(base, timer);
    }

    return index;
}

#define INDEX(N) ((base->timer_jiffies >> (TVR_BITS + (N) * TVN_BITS)) & TVN_MASK)

/**
 * __run_timers - run all expired timers (if any) on this CPU.
 * @base: the timer vector to be processed.
 *
 * This function cascades all vectors and executes all expired timer
 * vectors.
 */
static inline void __run_timers(struct tvec_base *base)
{
    struct timer_list *timer;

    spin_lock_irq(&base->lock);
    while (time_after_eq(jiffies, base->timer_jiffies)) {
        struct list_head work_list;
        struct list_head *head = &work_list;
        int index = base->timer_jiffies & TVR_MASK;

        /*
         * Cascade timers:
         */
        if (!index &&
            (!cascade(base, &base->tv2, INDEX(0))) &&
                (!cascade(base, &base->tv3, INDEX(1))) &&
                    !cascade(base, &base->tv4, INDEX(2)))
            cascade(base, &base->tv5, INDEX(3));
        ++base->timer_jiffies;
        list_replace_init(base->tv1.vec + index, &work_list);
        while (!list_empty(head)) {
            void (*fn)(unsigned long);
            unsigned long data;

            timer = list_first_entry(head, struct timer_list,entry);
            fn = timer->function;
            data = timer->data;

            timer_stats_account_timer(timer);

            set_running_timer(base, timer);
            detach_timer(timer, 1);
            spin_unlock_irq(&base->lock);
            {
                int preempt_count = preempt_count();
                fn(data);
                if (preempt_count != preempt_count()) {
                    printk(KERN_ERR "huh, entered %p "
                           "with preempt_count %08x, exited"
                           " with %08x?\n",
                           fn, preempt_count,
                           preempt_count());
                    BUG();
                }
            }
            spin_lock_irq(&base->lock);
        }
    }
    set_running_timer(base, NULL);
    spin_unlock_irq(&base->lock);
}
当第一组运行完一轮后，需要将tv2的一组新的定时任务加到第一组。这就好比时钟的指针，秒针运行一圈后，分针步进一格，后续的调整都是类似。
cascade 就是负责将下一组的定时任务添加到前面的任务阶梯。只有当第一轮的定时任务全部运行完毕后，才会需要从第二轮调入新的任务，只有第二级别的任务都调入完毕后，才需要从第三轮的定时任务调入新的任务：
 if (!index &&
            (!cascade(base, &base->tv2, INDEX(0))) &&
                (!cascade(base, &base->tv3, INDEX(1))) &&
                    !cascade(base, &base->tv4, INDEX(2)))
            cascade(base, &base->tv5, INDEX(3));

这就是负责调整的代码，相当的简洁。
参照上述代码实现一个定时器后，加入4000个定时任务：
    for(int i = 1; i < 4000; i++)
    {
        g_TimerHandle[i] = g_timerManager.setTimer(&tmpSink1, i, i*10, "ss");
    }
从10毫秒到4000*10毫秒,运行后，测试下性能，
函数名                                    执行次数    最小时间     平均时间       最大时间
TimerManager::runTimer    2170566        10              10               3046   
可以看到，除了个别时间是因为线程切换导致数据比较大外,平均每次运行runTimer的时间是10微秒。
这个时间还包括每个定时器的执行消耗，效率还是不错的。

  最近游戏又要封测了，工作比较紧张，晚上下班了比较累，回家懒得写代码了，不过顺便倒是继续完成了对 新剑侠情缘（和月影传说的资源格式相同）的资源逆向。完成了资源逆向后，突然兴致来了，写了个简单的地图查看器，到目前为止，一切运行正常。后来做了个简单的Demo，实现了基本的寻路和技能动画播放，其实新剑侠情缘原本的技能效果以今天的眼光看起来也还可以，即便如此，我还是集成了hge的粒子系统进去，试了下效果，还是挺奇怪的。
做完了这些之后，本想为我的PSP山寨一个新剑侠情缘。不料后来连续加了好几天班，加了几天班之后，人也懒了，山寨游戏的事情也就无疾而终了。
前面写过几篇逆向工程的文章，前几天翻出来看了下，感觉像是另一个人写的天书，我自己看自己的文章尚且如此，别人就更不用说了，其实对大部分人而言，关心的只是逆向的成果。对新剑侠情缘的资源和相关渲染感兴趣的朋友可以单独Email我。
  开始阅读Ogre代码正是在这百无聊赖的状态下开始的，Ogre推出来很多年了，貌似05年就听说朋友说起过这个项目，不过我一向是专注服务端开发，对客户端开发经验不是很多，在3D领域就完全是的新手了，所以一直也没仔细研究。这几天拿起原来下载的一个版本，简单读了下代码。
Ogre的结构还是很清晰的，和手册上说的一样，主要就是那几个对象，Demo大部分也很简单，代码量不多，看起来很振奋人心。
但是对我这样的新手来说，首先想了解的当然是渲染流程。 Ogre的渲染流程确实会让3D新手不适应，它是从RenderTarget开始的，一个RenderTarget可以有几个ViewPort，每个ViewPort都有一个独立的摄像机，这可以实现同屏幕多个渲染。
通过ViewPort对象的update调用
 mCamera->_renderScene(this, mShowOverlays);
来执行场景渲染，而场景渲染里，最重要的要算_findVisibleObjects了，
这个函数将可见的物体添加到渲染队列里，这个函数非常的绕，里面还用到了Vistor,精神不好容易被绕晕，好在我挺住了，熬过来了。
熟悉了大致的渲染流程后，我觉得该写点东西来实战了。
3D教程的开始一般会教大家画三角形，所以我也想用Ogre画个三角形玩玩，
一开始，我也想从像那些Demo一样从ExampleApplication继承，不过我发现这样启动太慢了，而且我不需要加载那么多的材质，
所以自己手动Configure了，代码如下:
Ogre::LogManager* pLogManager = new Ogre::LogManager;
    Ogre::Log* pLog = pLogManager->createLog("ogreLearn1.log");
    pLog->setDebugOutputEnabled(true);

    Ogre::Root* pRootObject = new Ogre::Root;
    pRootObject->loadPlugin("RenderSystem_Direct3D9_d.dll");
    pRootObject->loadPlugin("Plugin_OctreeSceneManager_d.dll");
    
    Ogre::RenderSystem* pRenderSystem = pRootObject->getRenderSystemByName("Direct3D9 Rendering Subsystem");
    pRenderSystem->setConfigOption("Full Screen", "False");
    pRootObject->setRenderSystem(pRenderSystem);   
    Ogre::RenderWindow* pRenderWindow = pRootObject->initialise(true);

编译测试了下，可以正常运行，不过发现屏幕是花的，我还没有创建场景呢，继续添加摄像机和ViewPort以及场景
// 创建场景和摄像机以及ViewPort
    Ogre::SceneManager* pSceneManager = pRootObject->createSceneManager(Ogre::ST_GENERIC, "OgreLearn1");
    Ogre::Camera* pCamera = pSceneManager->createCamera("MainCamara");
    pCamera->setPosition(0.0, 0.0, -20.0);
    pCamera->lookAt(0, 0, 0);
    pCamera->setNearClipDistance(2);

    Ogre::Viewport* pViewPort = pRenderWindow->addViewport(pCamera);
    pViewPort->setBackgroundColour(Ogre::ColourValue(0, 0, 0, 1.0f) );
    pCamera->setAspectRatio(pViewPort->getActualWidth()/pViewPort->getActualHeight() );

最后加上pRootObject->startRendering();
编译运行，一切正常，屏幕颜色也变成了想要的黑色，恩，下一步该添加三角形了，我不太喜欢用OgreManualObject，一堆的繁琐操作。这里用自定义的Mesh来绘制3角形。
pSceneManager->setAmbientLight(Ogre::ColourValue(0.2, 0.2, 0.2) );
        Ogre::MeshPtr pMeshData = Ogre::MeshManager::getSingleton().createManual("Learn", Ogre::ResourceGroupManager::DEFAULT_RESOURCE_GROUP_NAME);
        Ogre::SubMesh* pSubMesh = pMeshData->createSubMesh();
        pSubMesh->useSharedVertices = false;
        pSubMesh->vertexData = new Ogre::VertexData;
        pSubMesh->vertexData->vertexStart = 0;
        pSubMesh->vertexData->vertexCount = 3;

先设置了环境光(其实没啥用，我后面会禁止)，然后创建了一个自定义的Mesh,
紧接着的是创建一个SubMesh，要知道Ogre中最小的网格就是SubMesh,创建好SubMesh后，要填充网格结构了，
创建了一个VertexData,设置顶点数目为3（也就是一个三角形），下面该定义顶点格式了，
Ogre::VertexDeclaration* pDecle = pSubMesh->vertexData->vertexDeclaration;
        size_t sOffset = 0;
        pDecle->addElement(0, sOffset, Ogre::VET_FLOAT3, Ogre::VES_POSITION);
        sOffset += Ogre::VertexElement::getTypeSize(Ogre::VET_FLOAT3);
        pDecle->addElement(0, sOffset, Ogre::VET_COLOUR, Ogre::VES_DIFFUSE);
        sOffset += Ogre::VertexElement::getTypeSize(Ogre::VET_COLOUR);

上述代码定义了顶点格式，只有基本的坐标和颜色。
下一步将是申请显存，填充顶点结构。
Ogre::HardwareVertexBufferSharedPtr vBuf = Ogre::HardwareBufferManager::getSingleton().createVertexBuffer(sOffset, 3, Ogre::HardwareBuffer::HBU_STATIC_WRITE_ONLY);
        float* pReal = static_cast<float*>(vBuf->lock(Ogre::HardwareBuffer::HBL_DISCARD));
        Ogre::RGBA* pColor = NULL;

        *pReal++ = -2.0f;
        *pReal++ = 0.0f;
        *pReal++ = 0.0f;
        pColor = (Ogre::RGBA*)pReal;
        pRenderSystem->convertColourValue(Ogre::ColourValue(1.0f, 0.0, 0, 0.0f), pColor);
        pReal = (float*)(pColor+1);
        
        *pReal++ = 0.0f;
        *pReal++ = 2.0f;
        *pReal++ = 0.0f;
        pColor = (Ogre::RGBA*)pReal;
        pRenderSystem->convertColourValue(Ogre::ColourValue(0.0f, 0, 1.0, 1.0f), pColor);
        pReal = (float*)(pColor+1);


        *pReal++ = 2.0f;
        *pReal++ = 0.0f;
        *pReal++ = 0.0f;
        pColor = (Ogre::RGBA*)pReal;
        pRenderSystem->convertColourValue(Ogre::ColourValue(1.0f, 0, 0, 1.0f), pColor);
        pReal = (float*)(pColor+1);
        vBuf->unlock();
        pSubMesh->vertexData->vertexBufferBinding->setBinding(0, vBuf);
       
        pMeshData->load();
        pMeshData->_setBounds(Ogre::AxisAlignedBox(-2, 0, -1, 2, 2, 1) );
填充顶点后，设置网格包围盒，这样一个自定义的网格就创建好了，接下来要创建一个使用该网格的实体了
    Ogre::Entity* pEntity = pSceneManager->createEntity("TestEntity", "Learn");
        pEntity->setMaterialName("BaseWhiteNoLighting");

        pSceneManager->getRootSceneNode()->createChildSceneNode()->attachObject(pEntity);
        pEntity->getParentNode()->setPosition(3, 0, 0);
        pEntity->getParentNode()->rotate(Ogre::Quaternion(1.0f, 1.0f, 0, 1.0f) );

好了，这样实体也创建好了，接下来执行渲染吧：
pRootObject->startRendering();

遇到的问题

  上述代码是运行正常的，但是一开始，我执行的结果是看不到任何东西，跟踪了下，发现实体每次都被摄像机裁剪了，才发觉自定义Mesh要自己设置包围盒子，
设置可包围盒子。
 设置了包围盒后，数据已经进入了D3D的渲染管道，但是还是没看到三角形，仔细观察，原来摄像机对着的是三角形的背面。。。
调整摄像机后，终于能看到一个三角形了，不过是白色的。。。
从这个症状看，应该是没有关闭光照导致的，但是我明明主动调用RenderSystem关闭光照了啊，仔细跟踪了下原来是材质在捣乱，
默认的材质是开启了光照的，所以在渲染前的SceneManager::_setPass 的时候，开启了光照。
这好办，主动设置了关闭光照的材质"BaseWhiteNoLighting" 后，终于看到了彩色三角形了。

  在前面的文章里，我发布了修改版的boor到http://download.csdn.net/source/2578241 ,
支持中文pdf和中文txt,能正确显示中文目录。

问题

不过，有的朋友反映打开大的pdf文件时，容易死机。
这几天看了下，果然发现问题了。 为了加快读取pdf页面速度，bookr一开始就加载了所有的pageTree到内存中，
这样显示特定页面的时候，就无需查找该页面的PageObject了，这在PC机上一般没什么问题，PC机有虚拟内存，即使pdf文件很大，无非是加载pageTree慢点，
不过在PSP上就不行了，PSP的内存是有限的，而且没有虚拟内存，所以如果PageTree很大，那么很可能会导致内存不够，直接死机了。。。。

解决办法

解决办法其实也很简单，bookr启动的时候不加载PageTree，而是在每次显示的时候，从Root开始便利PageTree查询PageObject对象，任意一时刻，内存中只有一个PageObject对象。
这样就就基本解决了内存问题。下一个问题是查询效率的问题，这个问题其实不那么严重，PageTree本来就是一个树形结构，pdf的PageObject查询可以优化成一个树查询，这样应该会很快，实际编码测试，
根本感觉不到修改前后翻页速度有明显变化。
修改后用 金庸全集三联版.pdf(48.6M)测试OK。

下载

  1、下载http://download.csdn.net/source/2578241  
      解压到psp/game目录下。
  2、从http://www.cppblog.com/Files/feixuwu/EBOOT.rar 下载，解压后，覆盖原来bookr目录下的EBOOT.PBP文件即可。

  PSP上的阅读软件我所知道的有bookr和XReader（没用过）等，我比较喜欢bookr，不过bookr在阅读很多pdf时，中文会显示成乱码，阅读txt时，根本就无法显示中文，
这确实很让人不爽。
过年前闲着没事，顺便解决了bookr中文问题，本文记录了那段时间的工作：如何从官方版bookr修改，解决pdf中文乱码问题，支持txt中文、中文目录显示的问题，抛砖引玉和大家分享下整个的思路
和问题的解决方式，解决过程比较丑陋，希望高手多多指点。
貌似这里不能贴超过2M的附件，这里就不贴出修改后的bookr的发布文件了，在PSP2000测试通过，最近也一直在用,需要的同学可以email问我要。
注：已经上传到csdn:http://download.csdn.net/source/2578241
内置了少量字体，大家可以自行扩展字体。

准备工作

  1、搭建PSP开发环境。sourceforge上集成的安装包，下载下来直接安装即可，这里不多说了。
  2、下载bookr源码，我下载的是0.7.1版本。可以用SVN下载最新的，也可以在sourceForge下载打包的源码包。

解决PDF中文问题

  bookr的代码结果很清晰，由于是用c++开发的，所以代码很好理解，BKLayer 是基础的显示类，BKDocument是基础的文档处理类。
bookr支持pdf、txt、html和 PalmDoc(我没用过这种)，分别由从BKDocument的派生类来处理。
pdf是由BKPDF来处理的。解决pdf中文问题的关键就在BKPDF类了。

   1、如何调试

       PSP开发首先遇到的问题是调试，PSP并不能实时调试，这确实是个问题。好在Bookr源码级支持了跨平台，在windows下，使用Makefile.cygwin 就可以编译一个windows版本
的Bookr了。一般来说，在windows下bookr运行正常，大致在PSP上的版本也是正常的，当然，在细节上其实是有差别的。另外，还可以通过日志来实现跟踪。

   2、解决字体问题

      实际上，有些中文pdf用bookr打开时是正常的，比如Programming_In_Lua.pdf,但是在打开经常温习的金庸全集的时候，就出现乱码了。
注意到Bookr的pdf显示其实是主要是mudpf来实现的。那么bookr中文显示问题到底是bookr自身的还是mupdf的呢？
为了确认这个问题，先从sourceforge下载mupdf，建立一个vs2005的项目，编译，OK，可以运行了，打开金庸全集一看，还是乱码，这下基本可以确认，这个
问题是从mupdf就存在了。要定位中文显示乱码的问题，自然需要了解pdf的内部格式，从adobe的官网下载了最新的pdf手册，打开一看，一共700多页。。。
好在我们不需要从头开始阅读，只要挑关键的地方看就可以了，中文问题一般是因为字体引起的。

所以我们可以直接挑Text的字体相关部分看。
mupdf的字体加载在pdf_loadfont里，从pdf手册可知，pdf支持了若干种字体，反正我是没什么耐心看下去，直接打开金庸全集单步调试了下，
发现问题在TrueType字体的加载里，TrueType字体的加载是loadsimplefont来处理的，通过跟踪可知，在获取字体的FontDescriptor的时候失败了，然后就是用内置的默认字体来处理了。
默认字体都不支持中文，所以自然就显示成乱码了。
最简单的办法就是只要是TrueType字体，不管具体是什么字体，都强制从硬盘加载一种指定字体（例如黑体），当然，这样会导致我们看到的pdf和实际应该显示的样子有差别，只有一种字体了。
让我们先这样试试吧：在发现pdf_loadfontdescriptor 加载失败后，强制用loadCustomFont 加载硬盘指定字体"font/simhei.ttf",这样字体加载的问题貌似解决了。
编译，运行，发现还是有问题，这次的问题在文字编码了。

   3、编码问题

    一般显示不正常的中文pdf都是GBK编码的，mupdf的显示是通过如下两个步骤来做的：
   首先解码，将文字内容全部转化成cid，然后将要显示的cid全部push到一个队列，然后遍历cid,将cid转化成gid(对trueType就是转成unicode)，接着显示。
mupdf本身有一个比较优雅的办法来解码，通过pdf_lookupcmap来得到unicode，我用了比较笨的办法：自己暴力做GBK到unicode的转换。
一般在windows和linux下都有库或者API来完成编码转换问题。不过在PSP下却没有这样的API,只好自己做一个编码转换了，
在http://unicode.org/Public/MAPPINGS/VENDORS/MICSFT/WINDOWS/CP936.TXT 找到了转换表，复制粘贴到txt文本，用lua脚本处理下，生成一个.c文件，分别将GBK和unicode值存储到2个数组里，
现在你一定知道怎么转换了：二分查找到指定GBK值在GBK数组的下标，然后直接在unicode数组用这个下标，可以得到对应的unicode值。
编译测试，OK了，终于能正常显示中文了。
不过到现在为止，整个页面只有一种字体，要解决这个问题，我们可以根据名字匹配来找到指定的字体，名字匹配不到的，使用默认的字体（我是用的simsun.ttf）。

 txt中文问题

   相对来说txt的中文问题比较好解决了，基本都是些常规开发，从FzFont.cpp代码可知，txt显示不了中文主要是字体加载的时候，只加载了前面的256个字形。那么我们只要做2件事情就可以显示中文了：
  1、文字解码，现在大部分的txt电子书都是gbk编码的，这样比较省空间，解码算法前面已经提过了。
  2、中文文字纹理管理和效率问题。一般在PC游戏中，中文字体一般都是将多个连续的汉字按照存储到一张64X64的纹理中，这样可以节省显存，降低渲染批次(3D菜鸟的简单推测)。
不过如果在psp也这样做，会发现显示页面是在太慢，最后发现，最简单的办法居然是每个汉字一个纹理，当然要实际用到的时候才生成该汉字纹理。
  3、显示页分割。bookr阅读txt的时候，会自己将电子书分割成若干页面，并且支持书签功能，因此，不可避免的涉及到页面分割问题，引入中文显示后，这里稍微有点不同，要注意不能拆分一个汉字，
当然，还有其他细节需要处理，这里不多说了。

目录中文问题

  必须承认，这是我遇到的最痛苦的问题了，原因是从API上就有问题了，读取出来的目录名居然是Shift-jis编码的，谁让PSP是索尼产的呢，我尝试过将PSP的语言设置、时间等本地化设置改成中文、中国等。
发现读取到的目录名还是shift-jis编码。我先将目录名从shift-jis转回gb2312，然后显示，结果发现很多汉字丢失，因为从gb2312转到shift-jis的时候已经失真了，转回来显示很多字体就显示不了了。
看上去这个问题无法解决了，其实不然，PSP的API提供了打开记忆卡设备的功能，这样，我们自己做一个FAT32驱动（叫驱动不合适，其实就是自己读取FAT32文件系统管理文件）就可以了，FAT32的文档
到处都是，linux下也有vfat文件系统的实现，不过我偷懒了，我直接从PMP Player的代码里拷贝了FAT32相关文件，直接移植过来，修改了FzScreenPsp.cpp文件里目录相关的目录读取函数，
然后修改目录相关显示代码后，编码显示，一切终于解决了。。。