問題  

   上周開始，我們一個已經在線運行了快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.shnenglu.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文件里目錄相關的目錄讀取函數，
然后修改目錄相關顯示代碼后，編碼顯示，一切終于解決了。。。