張木梁 張 磊 秦 娣

1(武漢深之度科技有限公司技術部 北京 100080) 2(武漢深之度科技有限公司研發(fā)中心 北京 100080) 3(武漢深之度科技有限公司市場部 北京 100080) (zhangmuliang@deepin.com)

為了能夠向用戶提供一個高速的、基于文件名搜索的離線文件搜索功能，我們引入了“anything快速檢索”技術.對于“anything”的定義是Something like everything, but nothing is really like anything….

而anything之所以叫anything，是受到了Windows下everything軟件的啟發(fā)[1].原來在Linux中有一個類似的rlocate程序[2]，但是那個程序有點太老了，效率低下，效率方面的設計與當前時代不相稱.主要是出于與Linux傳統(tǒng)桌面結(jié)合得比較緊密，優(yōu)化起來對系統(tǒng)其他組件影響都很大，很多發(fā)行版就不會在這方面進行優(yōu)化.

1 基礎索引設計

1.1 簡要分析

在Linux下，最常用的文件搜索軟件是find，它會遞歸遍歷每個目錄，針對每個目錄與文件按照用戶給出的參數(shù)過濾出符合條件的目錄與文件，并打印出來.

在命令行模式下，find使用很廣，功能強大，不僅可以根據(jù)文件名查找文件，還可以根據(jù)文件類型、權限、修改時間、大小，甚至與其他軟件配合對文件進行過濾.但是在圖形界面下，用戶最常用的仍是根據(jù)文件名對文件進行查找，這是anything面向的核心問題.

使用find搜索時，如果已經(jīng)搜索過，則對應的文件與目錄信息將會被緩存在內(nèi)存中，可以大大加速搜索.當然，root用戶可以運行sysctl -w vm.drop_caches=3來清除這些緩存.但是，即使使用了緩存，在僅使用文件名搜索的前提下，find的搜索速度仍然是不理想的.

find搜索會通過系統(tǒng)調(diào)用遍歷每個目錄的內(nèi)容，讀取其中的文件列表，再根據(jù)文件列表中的inode號找到對應的inode信息，接著讀取inode類型為目錄中的文件內(nèi)容……如此遞歸查找.可以看到這個查找過程經(jīng)過多重遞歸，會不斷打開目錄(需要系統(tǒng)調(diào)用與內(nèi)存復制)，而且文件名在其中與inode信息夾雜在一起，會嚴重減緩純粹基于文件名的查找[3].

anything設計是與find完全不同的，不同之處在其內(nèi)部僅保存了文件(目錄)名以及必要的歸屬關系，以便進行雙向的查找.所有的數(shù)據(jù)都存放在用戶態(tài)空間，沒有額外的系統(tǒng)調(diào)用開銷與內(nèi)存復制開銷.此外，考慮到數(shù)據(jù)訪問的最大可能性，相鄰數(shù)據(jù)是最有可能被一起訪問的數(shù)據(jù)，因此anything可以最大限度利用處理器的高速緩存，使得軟件的運行性能更好.

總的來說，anything的設計理論上快速的主要原因是：

1) 相比于find，它不依賴于額外的系統(tǒng)調(diào)用與函數(shù)調(diào)用，減少了大量的系統(tǒng)調(diào)用開銷與內(nèi)存復制開銷；

2) 它使用的文件系統(tǒng)存儲結(jié)構(gòu)的設計針對性極強，內(nèi)容非常緊湊，使用也很高效.

1.2 內(nèi)部存儲設計

在經(jīng)典設計中，文件系統(tǒng)應該使用數(shù)據(jù)結(jié)構(gòu)中的樹來存儲.樹中的每個節(jié)點有一個字符串作為名稱，有N個指針指向其N個子節(jié)點，還有一個指針指向其父節(jié)點，以支持從上至下以及從下至上的雙向樹遍歷.這種結(jié)構(gòu)的優(yōu)點是修改很方便，不管是刪除、添加還是重命名每個節(jié)點都很快.但是在遍歷讀取時卻因為需要不停的指針跳轉(zhuǎn)，會導致處理器的高速緩存頻頻失效，從而使得訪問速度降低，而又因為各個節(jié)點都是分散的，無法體現(xiàn)出相鄰節(jié)點的訪問相關性，所以也難以進行有效的內(nèi)存訪問優(yōu)化.

下面是上述樹型設計數(shù)據(jù)結(jié)構(gòu)內(nèi)存消耗的分析.為簡單起見，先假設文件系統(tǒng)是一棵深度為D、分叉為N(N>1)的完全樹，這樣，在整棵樹中一共有葉節(jié)點ND-1個、非葉節(jié)點N0+N1+N2+…+ND-2=(ND-1-1)(N-1)個.對于每個葉節(jié)點而言，忽略其文件名，其他部分的內(nèi)存僅包括一個指向其自身上一級的指針；對于每個非葉節(jié)點而言，忽略其文件名，其他部分的內(nèi)存也包含一個指向其自身上一級的指針(假設根節(jié)點也有一個父節(jié)點指針，但是其值為空)，以及N個指向子節(jié)點的指針，指針數(shù)一共是P=ND-1+(N+1)(ND-1-1)(N-1)=(2×ND-N-1)(N-1)個，對于64 b系統(tǒng)而言，需要的內(nèi)存是8×P個字節(jié).

在anything內(nèi)部存儲結(jié)構(gòu)設計的早期階段，使用樹來保存文件系統(tǒng)結(jié)構(gòu)也曾被考慮過，但是顧及高速緩存失效與指針過大的問題，顯然在此處使用線性存儲設計更好.所以就有了下面anything的數(shù)據(jù)結(jié)構(gòu)來保存文件系統(tǒng)數(shù)據(jù)的內(nèi)部存儲結(jié)構(gòu).

從表1可以看出，anything內(nèi)部文件系統(tǒng)存儲頭部為4 B的MAGIC和4 B的緩存區(qū)，之所以使用4 B，而不是64 b系統(tǒng)上的8 B是因為對于1 000萬個文件與目錄的文件系統(tǒng)而言，使用上述結(jié)構(gòu)僅需約250 MB內(nèi)存，因此不需要8 B的長度與偏移量，從而可以節(jié)約一半的指針長度.在8 B之后是一個C語言風格的字符串，對應的是此文件系統(tǒng)樹的根目錄名，例如“”或者“homedeepin”，這個根目錄要求“”開頭，“”結(jié)尾，整個字符串以空字符結(jié)尾.

表1 anything的數(shù)據(jù)結(jié)構(gòu)

在上述頭部數(shù)據(jù)之后即為正式的文件樹結(jié)構(gòu)，每個文件或者目錄名均是一個C語言風格的、以空字符結(jié)尾的字符串.表1中大寫的TAG標簽代表一個目錄的結(jié)束，并且包含了自身父目錄節(jié)點的偏移量；小寫的tag標簽代表一個文件信息的結(jié)束，并且以標簽長度代表自身是文件還是目錄.在每個字符串之后是一個標簽(tag)，對于文件來說，此標簽占據(jù)1 B，標識這是一個文件.對于目錄而言，此標簽占據(jù)4 B，標識這是一個目錄，而且記錄了這個目錄中第1個文件的偏移量，按照之前的分析，這個偏移量僅需要4 B就夠了，通過目錄的這個4 B標簽就可以向下遍歷.如此反復，直到此目錄結(jié)束，將是一個單獨的值為0的字節(jié)，其后又是一個4 B的標簽(TAG)，此標簽除了標識目錄結(jié)束之外，還記錄了本級目錄的父節(jié)點的偏移量，如此，就可以通過這個標簽支持向上遍歷.此外，當本級目錄結(jié)束之后將開始下級目錄的存儲，這樣即可以使得1棵目錄樹的數(shù)據(jù)是緊緊相鄰的，在讀取時非常高效，在刪除時也非常方便.

上述結(jié)構(gòu)不斷重復，直到整個文件樹結(jié)束.

由上述結(jié)構(gòu)可以看出，相鄰的節(jié)點，即同級目錄下的文件都存儲在一起，這樣有利于內(nèi)存訪問優(yōu)化.而且將8 B指針優(yōu)化為4 B偏移量，也節(jié)省了存儲空間，減少了無效數(shù)據(jù)的存儲與無效內(nèi)存的訪問，此外，線性存儲也便于數(shù)據(jù)文件的存盤與讀盤.

對于每個葉節(jié)點，需要耗費1 B存儲標簽，對于每個非葉節(jié)點需要消耗4 B存儲子節(jié)點的偏移量，還有4 B用來存儲其所有子節(jié)點指向其本身的偏移量，則一共需要ND-1+8×(ND-1-1)(N-1)=(ND+7×ND-1-8)(N-1)個字節(jié)，對比之前樹需要耗費的8×P=8×(2×ND-N-1)(N-1)個字節(jié)，易知在最好情況下是其內(nèi)存的116，在最差情況下是其內(nèi)存的13.

當使用此結(jié)構(gòu)進行搜索時不需要再通過樹狀搜索，而可以使用線性搜索，從前至后進行字符串匹配，并跳過數(shù)據(jù)量較小的標簽即可，這樣也方便進行搜索分頁.

當搜索到某個名稱符合要求時，即可使用目錄結(jié)尾的標簽定位到父目錄的偏移量，繼而構(gòu)成完整的路徑，返回給調(diào)用者.

在這里也可以發(fā)現(xiàn)，其實對于搜索而言，程序并不需要保存子節(jié)點的偏移量，只需要父節(jié)點的偏移量即可，這樣還可以把額外的內(nèi)存再節(jié)省約一半，但是這會導致文件系統(tǒng)更改(文件與目錄刪除、添加、重命名)時變更速度較慢.若僅需使用離線搜索，即不考慮文件系統(tǒng)改動的問題，則內(nèi)存消耗確實還可通過使用上述方法進一步減少.

此外，由于需要至少1位來標識文件或者目錄，因此最大的偏移量不可能是232，即最多能存儲231或2 GB內(nèi)存的數(shù)據(jù).為了可擴展性考慮，在內(nèi)部其實保留了2位數(shù)據(jù)以進行文件標識，因此，最多可以使用1 GB內(nèi)存作為內(nèi)部存儲.根據(jù)之前的測試估算，大約能保存4 000萬個文件或目錄，在目前看來是足夠的.

1.3 理論對比與實際測試

在進行實際測試驗證之前，首先作理論對比.

在預估為包含38.7萬個文件(目錄)、其中有大約4萬個目錄的情況下：

2) 若使用樹進行數(shù)據(jù)存儲與搜索，在遍歷過程中需要持續(xù)生成節(jié)點，在搜索過程中需要遞歸遍歷(遞歸函數(shù)調(diào)用)各個節(jié)點，然后對每個節(jié)點調(diào)用strstr函數(shù)，即需要有4萬次遞歸函數(shù)調(diào)用以及38.7萬次strstr函數(shù)調(diào)用.當然，在此期間高速緩存也會頻頻失效.在搜索過程中，由于不再需要系統(tǒng)調(diào)用，以及額外的從內(nèi)核態(tài)到用戶態(tài)的內(nèi)存復制(這個開銷相對較小)，這種搜索方法應該會至少比find快一個數(shù)量級.

3) 使用anything也首先需要進行目錄樹遍歷，但是在搜索過程中需要從前向后，反復在線性存儲空間中調(diào)用strstr即可，即大約需要38.7萬次strstr調(diào)用.沒有系統(tǒng)調(diào)用開銷，沒有內(nèi)存復制開銷，而且由于內(nèi)存緊湊，又是單向內(nèi)存順序訪問，因此內(nèi)存訪問進入高速緩存浪費極少，非常自然，使用也很流暢，比目錄樹狀遞歸跳轉(zhuǎn)顯然要高效很多.

可以看出，從理論設計來看，anything的效率要明顯優(yōu)于前2種設計方案.

為了進一步確定上述猜測是否正確，我們開發(fā)了3個程序來實際驗證我們的理論設計.

程序2：遍歷目錄時建立樹狀結(jié)構(gòu)后，再基于內(nèi)存樹存儲進行搜索.

程序3：遍歷目錄時構(gòu)建基礎索引完成后，再基于基礎索引進行搜索.

這3個程序的關鍵源碼分別參見程序1～3.

程序1. 遞歸遍歷直接搜索文件名.

void walkdir (const char* path, const char* query, int* count)

{

DIR* dir=opendir(path);

if (0==dir)

return;

struct dirent* de=0;

while ((de=readdir(dir))!=0) {

if (strcmp(de->d_name, ″.″)==0‖strcmp(de->d_name, ″..″)==0)

continue;

if (de->d_type!=DT_DIR &&

de->d_type!=DT_REG &&

de->d_type!=DT_LNK)

continue;

if (strstr(de->d_name, query)!=0) {

if (*count<10)

*count, path, de->d_name);

*count=*count+1;

}

if (de->d_type==DT_DIR) {

char fullpath[PATH_MAX];

de->d_name);

walkdir(fullpath, query, count);

}

}

closedir(dir);

}

程序2. 遞歸遍歷建立樹后再搜索.

typedef struct __fs_tree_item__ {

char* name;

int kids_count;

struct __fs_tree_item__* parent;

struct __fs_tree_item__** kids;

} fs_tree_item;

void walkdir(const char* path, fs_tree_item* fti)

{

DIR* dir=opendir(path);

if (0==dir)

return;

struct dirent* de=0;

while ((de=readdir(dir))!=0) {

if (strcmp(de->d_name, ″.″)==0‖strcmp(de->d_name, ″..″)==0)

continue;

if (de->d_type!=DT_DIR && de->

d_type!=DT_REG && de->d_type

!=DT_LNK)

continue;

fs_tree_item*kid=calloc(1, sizeof(

fs_tree_item));

if (kid==0) {

printf(″kid malloc error, path: %s,

name: %s, count: %d ″, path,

de->d_name, fti->kids_count);

continue;

}

kid->name=strdup(de->d_name);

if (kid->name==0) {

free(kid);

printf(″kid strdup error, path: %s,

name: %s, count: %d ″, path,

de->d_name, fti->kids_count);

continue;

}

kid->parent=fti;

fs_tree_item** kids=realloc(

fti->kids, (fti->kids_count+1)*

sizeof(void*));

if (kids==0) {

free(kid->name);

free(kid);

printf(″kids realloc error, path: %s,

name: %s, count: %d ″, path,

de->d_name, fti->kids_count);

continue;

}

fti->kids=kids;

fti->kids[fti->kids_count]=kid;

fti->kids_count++;

if (de->d_type==DT_DIR) {

char fullpath[PATH_MAX];

de->d_name);

walkdir(fullpath, kid);

}

}

closedir(dir);

}

void search_tree(const char* path, fs_tree_item* root, const char* query, int* count)

{

if (strstr(root->name, query)!=0) {

if (*count<10)

path, root->name);

*count=*count+1;

}

char fullpath[PATH_MAX];

root->name);

for (int i=0;ikids_count;i++)

search_tree(fullpath, root->kids[i],

query, count);

}

程序3. 遞歸遍歷構(gòu)建好基礎索引后再搜索 (需使用anything庫與頭文件).

static int walkdir(const char* name, fs_buf* fsbuf, uint32_t parent_off)

{

DIR* dir=opendir(name);

if (0==dir)

return EMPTY_DIR;

uint32_t start=get_tail(fsbuf);

struct dirent* de=0;

while ((de=readdir(dir))!=0) {

if (strcmp(de->d_name, ″.″)==0‖strcmp(de->d_name, ″..″)==0)

continue;

if (de->d_type!=DT_DIR &&

de->d_type!=DT_REG &&

de->d_type!=DT_LNK)

continue;

append_new_name(fsbuf, de->

d_name, de->d_type==

DT_DIR);

}

closedir(dir);

if (start==get_tail(fsbuf))

return EMPTY_DIR;

uint32_t end=get_tail(fsbuf);

append_parent(fsbuf, parent_off);

uint32_t off=start;

while (off

if (is_file(fsbuf, off)) {

off=next_name(fsbuf, off);

continue;

}

set_kids_off(fsbuf, off, get_tail(fsbuf));

char path[PATH_MAX];

get_name(fsbuf, off));

if (walkdir(path, fsbuf, off)==

EMPTY_DIR)

set_kids_off(fsbuf, off, 0);

off=next_name(fsbuf, off);

}

return NONEMPTY_DIR;

}

#define MAX_RESULTS 10

static uint32_t search_by_fsbuf(fs_buf*fsbuf, const char* query)

{

uint32_t name_offs[MAX_RESULTS], end_off=get_tail(fsbuf);

uint32_t count=MAX_RESULTS,

start_off=first_name(fsbuf);

search_files(fsbuf, &start_off, end_off,

query, name_offs, &count);

char path[PATH_MAX];

for (uint32_t i=0; i

char *p=get_path_by_name_off(fsbuf,

name_offs[i], path, sizeof(path));

printf(″%’u: %c %s ″, i+1, is_file(fsbuf, name_offs[i]) ? ′F′ : ′D′, p);

}

uint32_t total=count;

while(count==MAX_RESULTS) {

search_files(fsbuf,&start_off, end_off, query, name_offs,&count);

total+=count;

}

return total;

}

在程序里單獨在搜索前后調(diào)用gettimeofday獲取時間戳，進行差分比較，在有緩存的情況下，3種方法搜索的耗時分別為：

1) 邊遞歸遍歷目錄邊匹配(類find)，10.1 s；

2) 遞歸遍歷目錄后用樹存儲目錄結(jié)構(gòu)再搜索，77 ms；

3) 遞歸遍歷目錄后用基礎索引存儲目錄結(jié)構(gòu)再搜索，8 ms.

如果使用perf,strace與google perftools進行性能剖析，可以看出在第1個程序里主要的程序耗時(88%)都花在了opendir()的調(diào)用上.第2、第3個程序在搜索階段運行沒有與內(nèi)核交互，而且時間過短，采樣過少，因此沒有有意義的數(shù)據(jù)產(chǎn)生，但是可以看出使用基礎索引技術比使用樹的方法快了接近10倍.

2 二級索引設計

上述基礎索引的設計已經(jīng)大大提高了基于文件名的搜索速度(相對于find而言)，但這種搜索方法仍然需要從前至后遍歷每個文件名進行搜索[4].從表面上看，因為需要對每個文件名進行檢查，以得知其是否匹配搜索串，理論上不會有更快的方法了.但事實上，我們還可以做得更好，那就是使用倒排索引(inverted index)實現(xiàn)二級索引.

倒排索引的原理是對目標字符串進行切割，得到其所有的子字符串，然后將這些子字符串存放到對應的索引數(shù)據(jù)結(jié)構(gòu)中，當用戶輸入對應的子字符串時能立刻找到相應的原始字符串[5].

例如原始字符串為china，則可以得到c,h,i,n,a,ch,hi,in,na,chi,hin,ina,chin,hina與china，一共5+4+3+2+1=15個子字符串，假設china這個字符串的偏移量(或者指針)是100，則可以得到{“c”→100}, {“h”→100}, …, {“china”→100}等25個索引.當用戶輸入hi時，即可以立刻得到{“hi”→100}這個索引，然后將100返回給調(diào)用者，由調(diào)用者通過這個偏移量或者指針得到“china”這個字符串.

在簡單的倒排索引設計中，一般使用Hash鏈表或者Trie樹作為索引數(shù)據(jù)結(jié)構(gòu)[6].anything使用的是Hash鏈表，其工作原理是，當用戶輸入某個查詢字符串(如hi)時，anything將首先對字符串進行一次Hash運算，得到Hash數(shù)組中的下標值，然后根據(jù)下標值即可得到對應的索引數(shù)組，在索引數(shù)組里順序查找即可得到對應的索引(即hi)，從而可以獲取到所有的包含hi字符串的原始字符串的偏移量，將其返回給調(diào)用者.

對于38.7萬個文件與目錄遍歷的實測表明，其索引內(nèi)存占用將超過2 GB，這完全是不可接受的.而對anything在對二級索引進行優(yōu)化后，內(nèi)存消耗可以大幅度減少.在對上述含有38.7萬個文件與目錄的遍歷表明，其索引大約有600萬個，索引占用內(nèi)存約230 MB，程序占據(jù)內(nèi)存不超過500 MB(因為動態(tài)內(nèi)存分配需要大量的額外內(nèi)存空間)，基本可以接受.

在基礎索引中，如果是38.7萬文件與目錄，則一共需要進行38.7萬次strstr的調(diào)用以完成一次完整的查找.在二級索引中，如果使用了Hash鏈表，每次查找時就可以大大減少strcmp的次數(shù).在這里，anything采用了質(zhì)數(shù)模的方法作為Hash函數(shù).對比基礎索引搜索需要的38.7萬個strstr調(diào)用，可以提高數(shù)10倍的性能.

測試環(huán)境中4個搜索方法的對比如下：

1) find——10.1 s，系統(tǒng)緩存增加260 MB;

2) 樹搜索——77 ms，存儲數(shù)據(jù)內(nèi)存需要30 MB;

3) 基礎索引搜索——8 ms，存儲數(shù)據(jù)程序內(nèi)存需要7 MB;

4) 二級索引搜索——0.4 ms，存儲數(shù)據(jù)程序內(nèi)存需要230 MB.

當然，二級索引的問題仍然是其占用內(nèi)存實在太大，對于38.7萬個文件與目錄的文件數(shù)來說，基礎索引約占用7 MB內(nèi)存，而二級索引則需要占用約230 MB內(nèi)存.其次，當發(fā)生文件系統(tǒng)變更時，基礎索引的變更比較容易實現(xiàn)，但是二級索引的更新就相當繁復了，需要遍歷所有的索引，找到對應的原始字符串偏移量進行修改.此外，二級索引的文件保存與載入也較為麻煩，因為需要將整個Hash鏈表序列化與反序列化，而且當文件系統(tǒng)變更時，一旦變更了索引，則需要進行數(shù)百兆甚至上吉數(shù)據(jù)的重新序列化，也會增大磁盤壓力.

因此，除非是在對文件名搜索速度非常關鍵的場所或者離線搜索的場景下，不然使用基礎索引進行文件名搜索即可滿足要求.這將是anything應用于其他場景的擴展能力，不在本文介紹.

3 文件系統(tǒng)監(jiān)控

從以上可以看出，搜索提速最重要的原因是省去系統(tǒng)調(diào)用，但是文件系統(tǒng)是會不停變化的.因此anything需要對文件系統(tǒng)進行監(jiān)控，在變化時及時對內(nèi)部的基礎索引進行修改才能保證搜索的正確性與實時性.

everything對于文件系統(tǒng)變更的追蹤相對簡單一些，因為它直接依賴于Windows下NTFS文件系統(tǒng)的日志[7].但是在Linux下，首先文件系統(tǒng)繁多，例如RHEL 7CentOS 7采用的缺省文件系統(tǒng)是XFS，但是Debian與RHEL 6CentOS 6使用的缺省文件系統(tǒng)卻是ext4，而且這兩者的文件系統(tǒng)日志都沒有NTFS信息完全[8].除此之外還有btrfs等一系列的其他文件系統(tǒng).其次是在Linux下，管理員或者用戶對于文件系統(tǒng)的選擇較多，并且可以深入調(diào)整文件系統(tǒng)的參數(shù)，例如去掉日志，因此僅依賴于文件系統(tǒng)日志檢查文件系統(tǒng)的變更是不太可靠的.

另外，由于Linux本身沒有全局的文件創(chuàng)建、刪除與重命名的用戶態(tài)接口(比較接近的inotify無法遞歸監(jiān)控目錄)[9]，因此要解決此問題，只能使用獨立的模塊監(jiān)聽文件的創(chuàng)建、刪除與重命名，并通知相應的用戶態(tài)程序更新文件系統(tǒng)數(shù)據(jù)與索引數(shù)據(jù).

在Linux下，監(jiān)控整個文件系統(tǒng)的變化可以采用下列方法：

1) 使用preload庫，監(jiān)控glibc對應函數(shù)的參數(shù)與返回值，包括open,fopen,creat,mkdir,rmdir,rename等.這種方式的優(yōu)點是不依賴于內(nèi)核，但是它會對所有依賴于glibc庫的程序都造成影響，影響面大，工作量也不小(函數(shù)較多，參數(shù)處理較多)，而且具有較大的安全隱患，此外，對于靜態(tài)編譯libc庫的程序以及不依賴于libc庫的程序(雖然這種程序很少)無法監(jiān)控.

2) 使用審計系統(tǒng)，加入對相應系統(tǒng)調(diào)用(open,creat,mkdir等)的審計，通過審計日志檢查系統(tǒng)調(diào)用的結(jié)果，根據(jù)結(jié)果更新文件系統(tǒng)數(shù)據(jù).其優(yōu)點是不依賴于內(nèi)核，系統(tǒng)調(diào)用數(shù)量較少，但是缺點是需要依賴于審計系統(tǒng)，而且事后處理日志的方式會缺少關鍵的場景信息，例如之前的文件或者目錄是否存在.

4) 編寫內(nèi)核模塊，使用內(nèi)核熱補丁技術(livepatch)替換內(nèi)核函數(shù).與上述技術路線類似，不需要自己考慮替換內(nèi)核函數(shù)指針的問題，缺點是需要重新實現(xiàn)或者調(diào)用原始函數(shù)，以保證功能的正確，而且熱補丁技術對內(nèi)核特性要求較高，龍芯申威內(nèi)核現(xiàn)在并沒有實現(xiàn)相應的功能.此外，如果相應的函數(shù)由于出現(xiàn)了問題需要使用熱補丁修復，將會帶來一些維護上的問題，雖然可能性較小.

5) 編寫內(nèi)核模塊，使用內(nèi)核tracepoint特性對系統(tǒng)調(diào)用入口與出口進行事件跟蹤，并記錄處理結(jié)果，缺點是會對所有的系統(tǒng)調(diào)用進行跟蹤，因此需要自己過濾，而且系統(tǒng)調(diào)用路徑較長，可能會導致較多的資源占用.

6) 編寫內(nèi)核模塊，通過kprobes對內(nèi)核函數(shù)進行掛鉤，在函數(shù)入口和出口處進行參數(shù)與返回值的檢查，當發(fā)現(xiàn)滿足要求的文件事件時將事件信息記錄下來，其缺點是對比tracepoint來說，kprobes從理論上依賴的函數(shù)變化的可能性更大一些，當內(nèi)核升級時可能會帶來維護的問題[10].

anything選擇了最后一種解決方法，雖然它要求內(nèi)核支持kprobes特性，但這是一個較容易實現(xiàn)的特性，而且anything要監(jiān)控的內(nèi)核函數(shù)也相對穩(wěn)定.

具體到需要跟蹤的內(nèi)核函數(shù)，主要就是VFS的文件系統(tǒng)變更函數(shù)，包括vfs_create等.為了確保只有當函數(shù)成功返回時才進行記錄，anything需要使用kretprobes進行函數(shù)跟蹤.

需要注意的是，使用kretprobes有一個與架構(gòu)相關的問題，那就是要在函數(shù)入口處得到函數(shù)各參數(shù)的值，而在這里，kretprobes沒有給開發(fā)者提供很多便利，需要根據(jù)不同CPU架構(gòu)的內(nèi)核寄存器結(jié)構(gòu)體(pt_regs)制定的函數(shù)調(diào)用規(guī)約才能獲取相關的參數(shù)值.例如對于X86來說，其64 b系統(tǒng)的函數(shù)調(diào)用規(guī)約是從第1個參數(shù)開始，分別使用rdi,rsi,rdx,rcx,r8與r9寄存器保存參數(shù)，從第7個參數(shù)開始使用棧來保存剩余的參數(shù).這些代碼都被封裝到源碼的kernelmodarg_extractor.c中.因此，當需要擴展架構(gòu)支持時，主要在這里進行修改即可.此外，在實際使用中，anything現(xiàn)在僅用到前4個參數(shù)，因此只要處理n等于1～4的情況即可.

4 測試驗證與結(jié)論

本文使用一個簡單但仍有典型意義的文件搜索來完成以下對比測試：

首先是測試環(huán)境.測試環(huán)境物理機為ThinkPad x230(8 GB內(nèi)存+機械硬盤).虛擬機為運行在VirtualBox里完整安裝的Deepin 15.4(分配虛擬單核處理器2.9 GHz，虛擬內(nèi)存2 GB).

測試方法如下：

1) 使用sysctl -w vm.drop_caches=3清空緩存，然后運行find-name ″*hellfire*，耗時約39.9 s.

3) 使用anything的基礎索引搜索hellfire，耗時約6 ms，基礎索引占用內(nèi)存約7 MB，測試程序占用內(nèi)存約14 MB.

4) 使用anything的二級索引搜索hellfire，耗時0 ms，二級索引占用內(nèi)存約230 MB，測試程序占用內(nèi)存約500 MB.

通過多次測試的結(jié)果表明，使用基礎索引比使用帶緩存的find搜索要快大約500倍甚至更多.若在忽略內(nèi)存等附加消耗的情況下，使用全內(nèi)存式的二級索引，anything的搜索速度會比使用基礎索引搜索速度再快20倍以上(但是占用內(nèi)存將增長35倍).是否引入二級索引需要根據(jù)實際的應用場景來取舍，這是典型的時間空間復雜度互換的問題.

在處理器支持上，已經(jīng)驗證anything能完全支持X86和自主可控CPU平臺，包括龍芯和ARM處理器，支持較新的申威(對部分擴展指令集有要求).

anything是一個小巧的軟件，其功能很單一.但是它達到了為文件名搜索提供一個高效快速實現(xiàn)的目標，而且對現(xiàn)有的系統(tǒng)侵入很小.同時，anything開源，希望有興趣的人能為它提交補丁，特別是對其他文件系統(tǒng)以及架構(gòu)的支持，當然也包括對程序本身的修正和改進.

[1]萬立夫. 讓Everything支持網(wǎng)盤目錄搜索[J]. 電腦迷: 技巧與實踐Software, 2012 (2): 77

[2]Rasto L. About rlocate官方文檔[OL]. [2017-12-15]. http://rlocate.sourceforge.net/

[3]Wbruce C, Donald M, Trevor S. 計算機科學叢書：搜索引擎信息檢索實踐[M]. 劉挺, 秦冰, 張宇, 等譯. 1版. 北京: 機械工業(yè)出版社, 2010

[4]周磊. 十五個經(jīng)典算法研究與總結(jié)[OL]. [2017-12-15]. http://blog.csdn.net/v_JULY_v

[5]沈東良. Linux內(nèi)核中鏈表和散列表的實現(xiàn)原理揭秘[OL]. [2017-12-15]. http://blog.csdn.net/shendl

[6]嚴浪. 倒排文件技術設計[J]. 計算機與數(shù)字工程, 2011 (3): 168-170

[7]Zhao J. 探索Everything背后的技術[OL]. [2017-12-15]. https://wenku.baidu.com/view/76bb29da80eb6294dd886cb7.html

[8]Harley Q. Linux和Windows的遍歷目錄下所有文件的方法[OL]. [2017-12-15]. https://www.cnblogs.com/Harley-Quinn/p/6367425.html

[9]Zhang S. Linux文件系統(tǒng)變化通知機制—inotify[OL]. [2017-12-15]. http://blog.csdn.net/zhangskd/article/details/7572320

[10]潘風云. Linux內(nèi)核kprobe機制[OL]. [2017-12-15]. http://blog.csdn.net/panfengyun12345/article/details/19480567