• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    深度科技的anything快速檢索技術(shù)研究

    2018-02-07 02:02:52張木梁
    信息安全研究 2018年1期
    關(guān)鍵詞:字符串偏移量內(nèi)核

    張木梁 張 磊 秦 娣

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

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

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

    1 基礎(chǔ)索引設(shè)計(jì)

    1.1 簡要分析

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

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

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

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

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

    總的來說,anything的設(shè)計(jì)理論上快速的主要原因是:

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

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

    1.2 內(nèi)部存儲(chǔ)設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

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

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

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

    1.3 理論對(duì)比與實(shí)際測試

    在進(jìn)行實(shí)際測試驗(yàn)證之前,首先作理論對(duì)比.

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

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

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

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

    為了進(jìn)一步確定上述猜測是否正確,我們開發(fā)了3個(gè)程序來實(shí)際驗(yàn)證我們的理論設(shè)計(jì).

    程序2:遍歷目錄時(shí)建立樹狀結(jié)構(gòu)后,再基于內(nèi)存樹存儲(chǔ)進(jìn)行搜索.

    程序3:遍歷目錄時(shí)構(gòu)建基礎(chǔ)索引完成后,再基于基礎(chǔ)索引進(jìn)行搜索.

    這3個(gè)程序的關(guān)鍵源碼分別參見程序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)建好基礎(chǔ)索引后再搜索 (需使用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;

    }

    在程序里單獨(dú)在搜索前后調(diào)用gettimeofday獲取時(shí)間戳,進(jìn)行差分比較,在有緩存的情況下,3種方法搜索的耗時(shí)分別為:

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

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

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

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

    2 二級(jí)索引設(shè)計(jì)

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

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

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

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

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

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

    測試環(huán)境中4個(gè)搜索方法的對(duì)比如下:

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

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

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

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

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

    因此,除非是在對(duì)文件名搜索速度非常關(guān)鍵的場所或者離線搜索的場景下,不然使用基礎(chǔ)索引進(jìn)行文件名搜索即可滿足要求.這將是anything應(yīng)用于其他場景的擴(kuò)展能力,不在本文介紹.

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

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

    everything對(duì)于文件系統(tǒng)變更的追蹤相對(duì)簡單一些,因?yàn)樗苯右蕾囉赪indows下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下,管理員或者用戶對(duì)于文件系統(tǒng)的選擇較多,并且可以深入調(diào)整文件系統(tǒng)的參數(shù),例如去掉日志,因此僅依賴于文件系統(tǒng)日志檢查文件系統(tǒng)的變更是不太可靠的.

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

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

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

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

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

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

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

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

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

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

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

    本文使用一個(gè)簡單但仍有典型意義的文件搜索來完成以下對(duì)比測試:

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

    測試方法如下:

    1) 使用sysctl -w vm.drop_caches=3清空緩存,然后運(yùn)行find-name ″*hellfire*,耗時(shí)約39.9 s.

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

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

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

    在處理器支持上,已經(jīng)驗(yàn)證anything能完全支持X86和自主可控CPU平臺(tái),包括龍芯和ARM處理器,支持較新的申威(對(duì)部分?jǐn)U展指令集有要求).

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

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

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

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

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

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

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

    [7]Zhao J. 探索Everything背后的技術(shù)[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)變化通知機(jī)制—inotify[OL]. [2017-12-15]. http://blog.csdn.net/zhangskd/article/details/7572320

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

    猜你喜歡
    字符串偏移量內(nèi)核
    萬物皆可IP的時(shí)代,我們當(dāng)夯實(shí)的IP內(nèi)核是什么?
    基于格網(wǎng)坐標(biāo)轉(zhuǎn)換法的矢量數(shù)據(jù)脫密方法研究
    強(qiáng)化『高新』內(nèi)核 打造農(nóng)業(yè)『硅谷』
    基于嵌入式Linux內(nèi)核的自恢復(fù)設(shè)計(jì)
    Linux內(nèi)核mmap保護(hù)機(jī)制研究
    攪拌針不同偏移量對(duì)6082-T6鋁合金接頭勞性能的影響
    基于最小二乘平差的全極化SAR配準(zhǔn)偏移量估計(jì)方法
    測繪工程(2017年3期)2017-12-22 03:24:50
    一種新的基于對(duì)稱性的字符串相似性處理算法
    依據(jù)字符串匹配的中文分詞模型研究
    基于Andriod多屏互動(dòng)的遙控器設(shè)計(jì)
    50天的宝宝边吃奶边哭怎么回事| 亚洲aⅴ乱码一区二区在线播放 | 级片在线观看| 19禁男女啪啪无遮挡网站| 亚洲av成人av| 国产主播在线观看一区二区| 一进一出好大好爽视频| 人人妻人人爽人人添夜夜欢视频| 在线永久观看黄色视频| 婷婷六月久久综合丁香| 一进一出好大好爽视频| 五月开心婷婷网| 91成年电影在线观看| 国产有黄有色有爽视频| 成年人免费黄色播放视频| 国产亚洲av高清不卡| 国产亚洲av高清不卡| 日韩欧美一区视频在线观看| 国产亚洲精品久久久久5区| 一进一出抽搐动态| 色综合婷婷激情| 欧美亚洲日本最大视频资源| 一二三四社区在线视频社区8| 中文字幕另类日韩欧美亚洲嫩草| 中国美女看黄片| av网站免费在线观看视频| 久久精品亚洲精品国产色婷小说| 国产精品野战在线观看 | 岛国在线观看网站| 精品福利观看| 精品久久久精品久久久| 欧美激情久久久久久爽电影 | 亚洲人成网站在线播放欧美日韩| 免费在线观看影片大全网站| 亚洲少妇的诱惑av| 午夜a级毛片| 美女高潮喷水抽搐中文字幕| 欧美激情极品国产一区二区三区| 满18在线观看网站| 欧美日韩视频精品一区| 亚洲成国产人片在线观看| 搡老乐熟女国产| 一边摸一边抽搐一进一出视频| 国产三级在线视频| 日韩欧美免费精品| 色婷婷av一区二区三区视频| 国产亚洲精品一区二区www| 欧美日韩亚洲高清精品| 亚洲久久久国产精品| 18美女黄网站色大片免费观看| 自拍欧美九色日韩亚洲蝌蚪91| 欧美日韩国产mv在线观看视频| 色哟哟哟哟哟哟| 岛国视频午夜一区免费看| 在线观看午夜福利视频| 两个人看的免费小视频| 欧美成人午夜精品| 日韩欧美一区二区三区在线观看| 99riav亚洲国产免费| 日本三级黄在线观看| 亚洲va日本ⅴa欧美va伊人久久| 国产男靠女视频免费网站| 成人免费观看视频高清| 国产欧美日韩一区二区精品| 99精品在免费线老司机午夜| 午夜精品国产一区二区电影| 久久久久久久午夜电影 | 国产不卡一卡二| 日韩欧美三级三区| 国产成年人精品一区二区 | 视频区图区小说| 午夜精品在线福利| 一区二区三区精品91| 桃红色精品国产亚洲av| e午夜精品久久久久久久| 亚洲欧洲精品一区二区精品久久久| 美女福利国产在线| 国产免费男女视频| 少妇 在线观看| 男人舔女人的私密视频| avwww免费| 午夜免费观看网址| netflix在线观看网站| 欧美国产精品va在线观看不卡| 午夜激情av网站| 免费看a级黄色片| 长腿黑丝高跟| 18禁美女被吸乳视频| bbb黄色大片| 性少妇av在线| av天堂久久9| 国产1区2区3区精品| 亚洲精品在线美女| 午夜精品国产一区二区电影| 国产三级黄色录像| 欧美人与性动交α欧美精品济南到| 高清在线国产一区| 美女国产高潮福利片在线看| 欧美日本亚洲视频在线播放| av有码第一页| 亚洲五月天丁香| 9热在线视频观看99| 丰满人妻熟妇乱又伦精品不卡| 国产亚洲精品综合一区在线观看 | 亚洲精品国产区一区二| 免费av毛片视频| 免费观看人在逋| 一进一出抽搐动态| 97超级碰碰碰精品色视频在线观看| 欧美最黄视频在线播放免费 | 亚洲熟妇中文字幕五十中出 | 免费一级毛片在线播放高清视频 | 久久 成人 亚洲| 欧美最黄视频在线播放免费 | 人人妻人人爽人人添夜夜欢视频| 淫秽高清视频在线观看| 午夜亚洲福利在线播放| 午夜福利免费观看在线| 亚洲av片天天在线观看| 国产精品99久久99久久久不卡| 自线自在国产av| 国产免费av片在线观看野外av| 露出奶头的视频| 18禁裸乳无遮挡免费网站照片 | 99久久久亚洲精品蜜臀av| 美女午夜性视频免费| 久久精品人人爽人人爽视色| 两性夫妻黄色片| svipshipincom国产片| 欧美性长视频在线观看| 大型黄色视频在线免费观看| 成人亚洲精品av一区二区 | 黑人猛操日本美女一级片| 看黄色毛片网站| 日韩中文字幕欧美一区二区| 亚洲欧美日韩无卡精品| 色综合站精品国产| 国产色视频综合| 老司机福利观看| 精品久久久精品久久久| 三上悠亚av全集在线观看| 宅男免费午夜| 国产成人精品无人区| 久久久精品国产亚洲av高清涩受| 亚洲情色 制服丝袜| 岛国在线观看网站| 新久久久久国产一级毛片| 午夜福利,免费看| 中国美女看黄片| 高清av免费在线| 黄色成人免费大全| 99热只有精品国产| 国产亚洲欧美98| 一边摸一边抽搐一进一出视频| 午夜免费观看网址| 97超级碰碰碰精品色视频在线观看| www日本在线高清视频| 精品国产美女av久久久久小说| 后天国语完整版免费观看| 在线国产一区二区在线| 欧美午夜高清在线| 黄色片一级片一级黄色片| 国产亚洲精品一区二区www| av在线播放免费不卡| 男人的好看免费观看在线视频 | 亚洲精品中文字幕一二三四区| 免费久久久久久久精品成人欧美视频| 每晚都被弄得嗷嗷叫到高潮| 久久中文字幕一级| 国产精品 欧美亚洲| 激情视频va一区二区三区| 啦啦啦 在线观看视频| 亚洲成a人片在线一区二区| 色老头精品视频在线观看| 午夜免费观看网址| 日本撒尿小便嘘嘘汇集6| 99国产精品一区二区三区| 午夜福利一区二区在线看| 欧美精品一区二区免费开放| 午夜福利影视在线免费观看| 18禁国产床啪视频网站| aaaaa片日本免费| 一边摸一边抽搐一进一出视频| 亚洲,欧美精品.| 视频区图区小说| 欧美性长视频在线观看| 久久中文看片网| 国产精品秋霞免费鲁丝片| 老司机亚洲免费影院| 亚洲精品一二三| 别揉我奶头~嗯~啊~动态视频| 在线观看舔阴道视频| 国产不卡一卡二| 中文欧美无线码| 中文字幕高清在线视频| 午夜福利一区二区在线看| 久久香蕉激情| 水蜜桃什么品种好| 精品久久久久久久毛片微露脸| 狂野欧美激情性xxxx| 亚洲精品成人av观看孕妇| 国产午夜精品久久久久久| 久久久久久亚洲精品国产蜜桃av| 中文亚洲av片在线观看爽| 国产免费现黄频在线看| 国产精品永久免费网站| 国产精品影院久久| 国产精品成人在线| 无限看片的www在线观看| 丰满的人妻完整版| 欧美中文日本在线观看视频| 黄色 视频免费看| 久久中文字幕一级| 日日夜夜操网爽| 日韩 欧美 亚洲 中文字幕| 久久九九热精品免费| av电影中文网址| 80岁老熟妇乱子伦牲交| 91成年电影在线观看| 欧洲精品卡2卡3卡4卡5卡区| 亚洲专区中文字幕在线| 狠狠狠狠99中文字幕| 黄色怎么调成土黄色| 村上凉子中文字幕在线| 一区在线观看完整版| 日韩国内少妇激情av| 午夜福利,免费看| 夜夜夜夜夜久久久久| 水蜜桃什么品种好| 亚洲av日韩精品久久久久久密| 精品日产1卡2卡| 亚洲精品中文字幕在线视频| 丝袜美腿诱惑在线| 成年女人毛片免费观看观看9| 黄色成人免费大全| 久久香蕉国产精品| 亚洲精品国产色婷婷电影| 嫩草影视91久久| 最近最新免费中文字幕在线| 欧美国产精品va在线观看不卡| 一二三四社区在线视频社区8| 久久久久国产一级毛片高清牌| 精品一区二区三区视频在线观看免费 | 黄色视频不卡| 国产成人欧美在线观看| 每晚都被弄得嗷嗷叫到高潮| 亚洲av美国av| 国产区一区二久久| 91字幕亚洲| 国产黄色免费在线视频| 亚洲片人在线观看| 性少妇av在线| 一进一出抽搐gif免费好疼 | 伊人久久大香线蕉亚洲五| 亚洲七黄色美女视频| 我的亚洲天堂| 嫩草影视91久久| 午夜福利在线免费观看网站| 国产成人影院久久av| 国产片内射在线| 欧美性长视频在线观看| 日韩成人在线观看一区二区三区| 露出奶头的视频| 日本一区二区免费在线视频| 国产精品野战在线观看 | 在线观看免费午夜福利视频| 老司机福利观看| 欧美激情久久久久久爽电影 | 久久精品国产清高在天天线| 十八禁人妻一区二区| 黄色a级毛片大全视频| 亚洲一区二区三区色噜噜 | 精品久久蜜臀av无| 欧美乱色亚洲激情| 男人舔女人下体高潮全视频| 国产精品av久久久久免费| 老司机福利观看| 国产亚洲av高清不卡| 长腿黑丝高跟| 午夜老司机福利片| 搡老熟女国产l中国老女人| 午夜a级毛片| 欧美日韩视频精品一区| 黑人操中国人逼视频| 精品一品国产午夜福利视频| 久久性视频一级片| 99国产精品99久久久久| 国产深夜福利视频在线观看| 久久精品影院6| 欧美亚洲日本最大视频资源| 久久国产乱子伦精品免费另类| 亚洲人成77777在线视频| 国产精品亚洲av一区麻豆| 国产精品 欧美亚洲| 老汉色∧v一级毛片| 久久狼人影院| 免费一级毛片在线播放高清视频 | 女同久久另类99精品国产91| 精品人妻在线不人妻| 国产一区二区三区在线臀色熟女 | 一边摸一边做爽爽视频免费| 男女床上黄色一级片免费看| 一级作爱视频免费观看| 看片在线看免费视频| 最好的美女福利视频网| 久久精品国产亚洲av高清一级| 国产av一区在线观看免费| 身体一侧抽搐| 国产精品av久久久久免费| 免费av中文字幕在线| 日本黄色视频三级网站网址| 久久精品人人爽人人爽视色| 成年女人毛片免费观看观看9| 亚洲精品成人av观看孕妇| 亚洲熟妇熟女久久| 国产精品亚洲av一区麻豆| 亚洲五月色婷婷综合| 久久香蕉国产精品| 国产亚洲欧美精品永久| 亚洲精品中文字幕在线视频| 久久中文字幕人妻熟女| 国产精品永久免费网站| 亚洲精品一卡2卡三卡4卡5卡| 香蕉丝袜av| 男男h啪啪无遮挡| 亚洲精品一二三| 亚洲国产中文字幕在线视频| 国产真人三级小视频在线观看| 真人一进一出gif抽搐免费| 亚洲欧美精品综合一区二区三区| 国产成人精品久久二区二区91| 91九色精品人成在线观看| 欧美激情极品国产一区二区三区| 99精品在免费线老司机午夜| 久久精品影院6| 久久热在线av| 亚洲成人国产一区在线观看| 国产aⅴ精品一区二区三区波| 亚洲国产看品久久| 亚洲第一欧美日韩一区二区三区| 亚洲国产精品sss在线观看 | 亚洲 国产 在线| 欧美精品一区二区免费开放| 国产一区二区三区视频了| 又大又爽又粗| 亚洲三区欧美一区| 在线观看午夜福利视频| 一级a爱视频在线免费观看| 亚洲av第一区精品v没综合| 国产成人免费无遮挡视频| 宅男免费午夜| 国内久久婷婷六月综合欲色啪| 亚洲成人精品中文字幕电影 | 亚洲 欧美 日韩 在线 免费| 又大又爽又粗| av电影中文网址| 久久婷婷成人综合色麻豆| 这个男人来自地球电影免费观看| 久久精品亚洲熟妇少妇任你| 黄色视频,在线免费观看| 亚洲情色 制服丝袜| 亚洲视频免费观看视频| 成人影院久久| 久久天堂一区二区三区四区| 久久国产精品人妻蜜桃| 国产免费av片在线观看野外av| 免费av中文字幕在线| 亚洲片人在线观看| 在线播放国产精品三级| 18禁国产床啪视频网站| 精品久久久久久久久久免费视频 | 老司机福利观看| 成人三级黄色视频| 欧美丝袜亚洲另类 | 天堂动漫精品| xxx96com| 88av欧美| 免费一级毛片在线播放高清视频 | 国产成人影院久久av| 变态另类成人亚洲欧美熟女 | 国产av一区在线观看免费| 在线视频色国产色| 久久久国产一区二区| 午夜福利欧美成人| 黑人猛操日本美女一级片| 日韩欧美一区二区三区在线观看| 国产精品一区二区在线不卡| 亚洲男人天堂网一区| 国产日韩一区二区三区精品不卡| 亚洲,欧美精品.| xxx96com| 久久久水蜜桃国产精品网| 高潮久久久久久久久久久不卡| 日韩欧美三级三区| 淫妇啪啪啪对白视频| 人人妻人人爽人人添夜夜欢视频| 免费观看精品视频网站| videosex国产| 久久国产亚洲av麻豆专区| 美女高潮到喷水免费观看| 黑人欧美特级aaaaaa片| 久久久水蜜桃国产精品网| 啦啦啦在线免费观看视频4| 日本黄色日本黄色录像| 国产免费av片在线观看野外av| 久久久精品欧美日韩精品| 一级毛片高清免费大全| 久久久精品欧美日韩精品| 99久久99久久久精品蜜桃| 国产av精品麻豆| 国产亚洲精品一区二区www| 欧美激情高清一区二区三区| 好看av亚洲va欧美ⅴa在| 中文字幕人妻丝袜一区二区| 看免费av毛片| 亚洲人成77777在线视频| 一本大道久久a久久精品| 欧美日韩亚洲综合一区二区三区_| 无限看片的www在线观看| 国产成人精品久久二区二区91| 日韩精品中文字幕看吧| 欧美在线一区亚洲| 亚洲色图综合在线观看| 五月开心婷婷网| 99久久综合精品五月天人人| 村上凉子中文字幕在线| 国产精品成人在线| 国产精品久久久久成人av| 亚洲激情在线av| 午夜福利在线观看吧| 看片在线看免费视频| 操出白浆在线播放| 99国产精品99久久久久| 日韩欧美三级三区| 国产精品一区二区在线不卡| 国产xxxxx性猛交| 很黄的视频免费| 在线观看66精品国产| 成人免费观看视频高清| 国产高清国产精品国产三级| 波多野结衣高清无吗| 麻豆av在线久日| www国产在线视频色| 12—13女人毛片做爰片一| 99riav亚洲国产免费| 国产精品国产高清国产av| 国产一区二区三区综合在线观看| 高清av免费在线| 亚洲全国av大片| 久久久久九九精品影院| 在线观看66精品国产| 黑丝袜美女国产一区| 国产日韩一区二区三区精品不卡| 成人18禁在线播放| 色综合站精品国产| 精品久久蜜臀av无| 99久久久亚洲精品蜜臀av| 欧美成人性av电影在线观看| 精品国产国语对白av| 99热只有精品国产| 可以免费在线观看a视频的电影网站| 女性生殖器流出的白浆| 美女扒开内裤让男人捅视频| 午夜福利欧美成人| 97超级碰碰碰精品色视频在线观看| 老汉色∧v一级毛片| 18美女黄网站色大片免费观看| 亚洲色图av天堂| 中亚洲国语对白在线视频| 成年版毛片免费区| 国产精品九九99| 亚洲五月天丁香| 超碰成人久久| 久久人妻福利社区极品人妻图片| 精品高清国产在线一区| 长腿黑丝高跟| 日日夜夜操网爽| 国产亚洲欧美在线一区二区| 国产aⅴ精品一区二区三区波| 亚洲视频免费观看视频| 亚洲欧美激情综合另类| 亚洲国产精品sss在线观看 | 十分钟在线观看高清视频www| 午夜影院日韩av| 久久草成人影院| 色在线成人网| 国产区一区二久久| 精品久久久久久,| www国产在线视频色| 一区福利在线观看| 欧洲精品卡2卡3卡4卡5卡区| 丁香欧美五月| 久久久久国产一级毛片高清牌| 亚洲自拍偷在线| 欧美成人免费av一区二区三区| 亚洲第一av免费看| 成人18禁在线播放| 免费在线观看亚洲国产| 国产成人啪精品午夜网站| 国产无遮挡羞羞视频在线观看| 如日韩欧美国产精品一区二区三区| 可以在线观看毛片的网站| 亚洲精品国产精品久久久不卡| 成人精品一区二区免费| 久久久精品欧美日韩精品| 国产亚洲精品一区二区www| 在线天堂中文资源库| 50天的宝宝边吃奶边哭怎么回事| 99国产精品免费福利视频| 看免费av毛片| 国产一区二区在线av高清观看| 欧美最黄视频在线播放免费 | 欧美国产精品va在线观看不卡| 在线观看一区二区三区激情| 女人精品久久久久毛片| 久热爱精品视频在线9| a级毛片在线看网站| 在线观看免费视频日本深夜| 最近最新免费中文字幕在线| 色婷婷久久久亚洲欧美| 国产精品九九99| 窝窝影院91人妻| 亚洲精品美女久久av网站| 多毛熟女@视频| 国产一区在线观看成人免费| 亚洲免费av在线视频| 黑人巨大精品欧美一区二区蜜桃| 亚洲欧美激情在线| 日韩欧美免费精品| 夜夜躁狠狠躁天天躁| 男女做爰动态图高潮gif福利片 | 欧美黑人欧美精品刺激| 操出白浆在线播放| 老司机靠b影院| 又大又爽又粗| 国产精品99久久99久久久不卡| 国产精品 国内视频| 欧美人与性动交α欧美软件| 天堂中文最新版在线下载| 一级毛片高清免费大全| 亚洲精品国产精品久久久不卡| 丰满迷人的少妇在线观看| 一边摸一边做爽爽视频免费| 麻豆av在线久日| 一本大道久久a久久精品| 国产精品自产拍在线观看55亚洲| 亚洲精品久久午夜乱码| 悠悠久久av| cao死你这个sao货| 免费日韩欧美在线观看| 淫秽高清视频在线观看| 国产精品一区二区免费欧美| 国产免费av片在线观看野外av| 国产精品亚洲av一区麻豆| 亚洲国产精品999在线| 黄色片一级片一级黄色片| 国产精品综合久久久久久久免费 | 亚洲激情在线av| 丰满迷人的少妇在线观看| av在线播放免费不卡| 色综合欧美亚洲国产小说| 97碰自拍视频| 在线av久久热| 久久久国产欧美日韩av| 女人精品久久久久毛片| av天堂在线播放| 欧美中文日本在线观看视频| 日韩欧美国产一区二区入口| 久久久久久亚洲精品国产蜜桃av| 精品人妻1区二区| 免费不卡黄色视频| 午夜免费成人在线视频| 国产色视频综合| 悠悠久久av| 午夜精品久久久久久毛片777| 国产精品亚洲一级av第二区| 久久天躁狠狠躁夜夜2o2o| 欧美 亚洲 国产 日韩一| 国产成人精品无人区| 91九色精品人成在线观看| 久久久久久久午夜电影 | 91麻豆精品激情在线观看国产 | 波多野结衣高清无吗| 在线观看日韩欧美| 水蜜桃什么品种好| a在线观看视频网站| www日本在线高清视频| 亚洲黑人精品在线| 久久香蕉精品热| 嫁个100分男人电影在线观看| 老汉色∧v一级毛片| 男人操女人黄网站| 亚洲欧美精品综合一区二区三区| 最近最新免费中文字幕在线| 国产亚洲精品一区二区www| 亚洲第一青青草原| av福利片在线| 大型黄色视频在线免费观看| 在线观看日韩欧美| 成人特级黄色片久久久久久久| 中亚洲国语对白在线视频| 黄色 视频免费看| 日本wwww免费看| 丁香欧美五月| 午夜成年电影在线免费观看| 亚洲男人天堂网一区| 男女做爰动态图高潮gif福利片 | 亚洲专区字幕在线| 亚洲精品久久成人aⅴ小说| 自拍欧美九色日韩亚洲蝌蚪91| 久久欧美精品欧美久久欧美| 国产av又大| 12—13女人毛片做爰片一| 日韩有码中文字幕| 精品国产亚洲在线|