anything is possible

简介

什么是anything呢?按照项目文档简介来说,它是Something like everything, but nothing is really like anything…

所以,anything名字的由来是受到了Windows下everything这个软件的启发。在文件管理器里,针对文件名进行搜索一个很常见的需求。但是GNU findutils里的find搜文件太慢,locate搜文件又会有很大的延迟,因此,anything目标就是为Linux用户提供一个快速的文件名搜索的功能。如果一定要说,其实在Linux中也有一个类似的叫rlocate的程序,但是那个程序有点太老了,而重写一个更好的也不难,因此我们就重新造了一个轮子。

为了说明anything的特性,先来做一个简单但仍有典型意义的文件搜索对比测试。

首先说明下测试环境,测试环境物理机为ThinkPad x230,8G内存,机械硬盘。虚拟机为运行在VirtualBox里的Deepin 15.4,内存为2G,处理器为单核2.9 GHz。在这里,使用虚拟机的主要原因是为了测试方便,因为anything涉及到内核开发,大家知道,内核编程很容易把系统挂掉的,使用虚拟机乃是内核开发的居家必备法宝之一。

虚拟机的文件系统排除/sys、/proc、/dev与/run目录后共有目录、链接与文件数约38.7万个,其中挂载了一个虚拟机外的文件系统以方便文件交换,在虚拟机内此文件系统类型为vboxsf,大约有11.5万个文件与目录。

测试方法如下:

  • 使用sysctl -w vm.drop_caches=3清空缓存,然后运行find / -name "*hellfire*,耗时约39.9秒
  • 带缓存再次运行find / -name "*hellfire*,耗时约10.1秒,通过运行free命令对比cache项得知新增的文件缓存约占用260MB内存
  • 使用anything的基础索引搜索hellfire,耗时约6毫秒,基础索引占用内存约7MB,测试程序占用内存约14MB
  • 使用anything的二级索引搜索hellfire,耗时0毫秒,二级索引占用内存约230MB,测试程序占用内存约500MB

经多次测试表明,使用基础索引比使用带缓存的find搜索要快大约500倍甚至更多。若使用全内存式的二级索引,anything的搜索速度是使用基础索引搜索速度的20倍以上,但是占用内存将增长35倍。若将二级索引存放在磁盘上,其内存占用将减少到近乎零,在大部分情况下仍然能够取得很好的搜索速度,仍比基础索引有明显的速度加快,但是在原始字符串较多的情况下,因为需要从索引文件中读取较大量的数据,就会显得比基础索引搜索还要慢了,这个是典型的时间空间复杂度互换的问题。

下面对anything设计与实现进行一个简单的分析。

基础索引设计

简要分析

在Linux下,最常用的文件搜索软件是find,它会递归遍历每个目录,针对每个目录与文件按照用户给出的参数过滤出符合条件的目录与文件并打印出来。

在命令行模式下,find使用很广,功能强大,不仅可以根据文件名查找文件,还可以根据文件类型、权限、修改时间、大小,甚至与其它软件配合对文件进行过滤。但是在图形界面下,用户最常用的仍是根据文件名对文件进行查找,这正好是anything的用武之地。

使用find搜索时,如果已经搜索过一遍,则对应的文件与目录信息将会被缓存在内存中,可以大大加速搜索。当然,root用户可以运行sysctl -w vm.drop_caches=3来清除这些缓存。但是,即使使用了缓存,在仅使用文件名搜索的前提下,find的搜索速度仍比anything至少慢两个数量级。

anything之所以这么快速主要是因为:

  • 相比于find,它不依赖于额外的系统调用与函数调用,减少了大量的系统调用开销与内存复制开销
  • 它使用的文件系统存储结构的设计针对性极强,内容非常紧凑,使用也很高效

find会通过系统调用遍历每个目录的内容,读取其中的文件列表,再根据文件列表中的inode号找到对应的inode信息,接着读取inode类型为目录中的的文件内容……如此递归查找。可以看到这个查找过程经过多重递归,会不断打开目录(需要系统调用与内存复制),而且文件名在其中与inode信息夹杂在一起,会严重减缓纯粹基于文件名的查找。

anything的不同之处在于在其内部仅保存了文件(目录)名以及必要的归属关系,以便进行双向的查找。所有的数据都存放在用户态空间,没有额外的系统调用开销与内存复制开销。此外,考虑到数据访问的最大可能性,相邻数据应是最有可能被一起访问的数据,因此可以最大限度利用处理器的高速缓存,使得软件的运行性能更好。

内部线性存储

在经典设计中,文件系统应该使用数据结构中的树来存储。树中的每个节点有一个字符串作为名称,有N个指针指向其N个子节点,还有一个指针指向其父节点以支持从上至下以及从下至上的双向树遍历。这种结构的优点是修改很方便,不管是删除、添加还是重命名一个节点都很快。但是在遍历读取的时候却因为需要不停的指针跳转,会导致处理器的高速缓存频频失效,从而使得访问速度降低,而又因为各个节点都是分散的,无法体现出相邻节点的访问相关性,所以也难以进行有效的内存访问优化。

下面是上述树设计数据结构内存消耗的分析。简单起见,先假设文件系统是一棵深度为D、分叉为N(N > 1)的完全树,这样,在整棵树中将一共有叶节点ND-1个,非叶节点N0 + N1 + N2 + …… + ND-2 = (ND-1 – 1)/(N – 1)个。对于每个叶节点而言,忽略其文件名,其它部分的内存仅包括一个指向父节点的指针。对于每个非叶节点而言,忽略其文件名,其它部分的内存包含一个指向父节点的指针(假设根节点也有一个父节点指针,但是其值为空),以及N个指向子节点的指针,一共的指针数是P =ND-1 + (N+1) x (ND-1 – 1)/(N – 1)= (2 x ND – N – 1)/(N-1)个,对于64位系统而言,需要的内存是8 x P个字节。

在anything内部存储结构设计的早期阶段,使用树来保存文件系统结构也曾被考虑过,但是顾及高速缓存失效与指针过大的问题,显然在此处使用线性存储设计更好,假设某目录下有d1与d2两个文件夹,d1下有两个文件f1与f2,还有一个空的子目录d3。而d2下有一个文件f3。如下图所示。

图1 示例目录树

对应的anything内部的线性存储如下图所示。

图2 anything目录树线性存储结构

从上述例子中可以看到,在d1的标签(T)中保存了一个偏移量,指向的是以f1开始的位置表示文件夹内容的开始,而在d3结束后,其标签也保存了一个偏移量,指向d1,表示父目录的位置。对于空目录,例如d3,其标签保存的偏移量为零。

由上述结构可以看出,相邻的节点,即同级目录下的文件,都存储在一起,这样有利于内存访问优化。而且将8字节指针优化为4字节偏移量,也节省了存储空间,减少了无效数据的存储与无效内存的访问,此外,线性存储也便于数据文件的存盘与读盘。

对于每个叶节点,需要耗费1个字节存储标签,对于每个非叶节点,需要消耗4个字节存储子节点的偏移量,还有4个字节用来存储其所有子节点指向其本身的偏移量,则一共需要ND-1+ 8 x (ND-1 – 1)/(N-1) = (ND + 7 x ND-1 – 8)/(N-1)个字节,对比之前树需要耗费的8 x P = 8 x (2 x ND – N – 1)/(N-1)个字节,易知在最好情况下是其内存的1/16,在最差情况下是其内存的1/3。

当使用此结构进行搜索时,不需要再通过树状搜索,而可以使用线性搜索,从前至后进行字符串匹配,并跳过数据量较小的标签即可,这样也方便进行搜索分页。

当搜索到某个名称符合要求时,即可使用目录结尾的标签定位到父目录的偏移量,继而构成完整的路径,返回给调用者。

在这里也可以发现,其实对于搜索而言,程序并不需要保存子节点的偏移量,只需要父节点的偏移量即可,这样还可以把额外的内存再节省约一半,但是这会导致文件系统更改(文件与目录删除、添加、重命名)时变更速度较慢。若仅需使用离线搜索,即不考虑文件系统改动的问题,则内存消耗确实还可通过使用上述方法进一步减少。

此外,由于需要至少一位来标识文件或者目录,因此最大的偏移量不可能是232,即最多能存储或2G内存的数据,为了可扩展性考虑,在内部其实保留了两位数据以进行文件标识,因此,最多可以使用1G内存作为内部存储。根据之前的测试估算,大约能保存4000万个文件或目录,在目前看来是足够的。

理论对比与实际测试

下面首先做理论对比,继而进行实际测试验证。测试环境仍包含38.7万个文件(目录),其中有大约4万个目录。

若使用经典的目录遍历方法,即使用opendir/readdir/closedir函数遍历目录,则需要调用大约4万次opendirclosedir,38.7万次readdir,这些都是系统调用,而其中readdir将读取一个struct dirent大小的数据,即大约274个字节的数据。即使这些数据都在缓存中,也只是节省了从磁盘到内存的数据读取,但是仍然无法节省从内核态到用户态的数据复制开销。再接着,需要对这38.7万个数据进行38.7万次strstr调用。这就是find的大致开销,其中完全忽略了磁盘访问。

若使用树进行数据存储与搜索,在遍历过程中需要持续生成节点,在搜索过程中需要递归遍历(递归函数调用)各个节点,然后对每个节点调用strstr函数,即需要有4万次递归函数调用,以及38.7万次strstr函数调用。当然,由于数据存储在内存中不连续,因此高速缓存失效较多。在搜索过程中,由于不再需要系统调用,以及额外的从内核态到用户态的内存复制(这个开销相对较小),这种搜索方法应该会至少比find快一个数量级。

使用anything也首先需要进行目录树遍历建立基础索引。一旦基础索引建立完毕后,在搜索过程中,只需要从前向后,反复在线性存储空间中调用strstr即可,即大约需要38.7万次strstr调用。没有系统调用开销,没有内存复制开销,而且由于内存紧凑,又是单向内存顺序访问,因此对高速缓存的利用率更高,空间与时间效率比目录树状递归查找都要更好。此外,使用线性结构的基础索引也方便数据的保存与读取,但是其偏移量的管理会更复杂一些。

为了进一步确定上述猜测是否正确,下面可以开发三个程序,第一个程序模仿find的做法,通过opendir/readdir/closedir函数遍历目录,同时调用strstr进行搜索。第二个程序遍历目录的时候建立树形结构后,再基于树形结构进行搜索。第三个程序遍历目录的时候构建基础索引完成后,再基于基础索引进行搜索。

程序一:递归搜索(类find

void walkdir(const char* path, const char* query, int* count)
{
    if (is_special_mount_point(path))
        return;

    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;

        // DT_REG: regular file/hardlinks, DT_LNK: softlinks
        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) {
                printf("%d: %s/%s\n", 1 + *count, path, de->d_name);
            } else {
                printf(".");
                if ((*count) % 10 == 0)
                    fflush(stdout);
            }
            *count = *count + 1;
        }

        if (de->d_type == DT_DIR) {
            char fullpath[PATH_MAX];
            sprintf(fullpath, "%s/%s", path, de->d_name);
            walkdir(fullpath, query, count);
        }
    }

    closedir(dir);
}

程序二:递归建立树结构后搜索

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)
{
    if (is_special_mount_point(path))
        return;

    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;

        // DT_REG: regular file/hardlinks, DT_LNK: softlinks
        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\n", 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\n", 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\n", 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];
            sprintf(fullpath, "%s/%s", path, de->d_name);
            walkdir(fullpath, kid);
        }
    }

    closedir(dir);
}

char fullpath[4096];

void print_path(int count, fs_tree_item* fti)
{
    int cur = sizeof(fullpath) - 1;
    while (fti) {
        int l = strlen(fti->name);
        cur -= l;
        memcpy(fullpath + cur, fti->name, l);
        cur--;
        fullpath[cur] = '/';
        fti = fti->parent;
    }
    printf("%d: %s\n", count+1, fullpath+cur);
}

void search_tree(fs_tree_item* fti, const char* query, int* count)
{
    if (strstr(fti->name, query) != 0) {
        if (*count < 10)
            print_path(*count, fti);
        *count = *count + 1;
    }

    for (int i = 0; i < fti->kids_count; i++)
        search_tree(fti->kids[i], query, count);
}

程序三:建立基础索引后对其进行搜索

static int match_str(const char* name, const void* arg)
{
    return strstr(name, (const char *)arg) != 0;
}

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, match_str, name_offs, &count);

    char path[PATH_MAX];
    for (uint32_t i = 0; i < count; i++) {
        char *p = get_path_by_name_off(fsbuf, name_offs[i], path, sizeof(path));
        printf("%'u: %c %s\n", 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, match_str, name_offs, &count);
        total += count;
    }
    return total;
}

在程序里单独在搜索前后调用gettimeofday获取时间戳,进行差分比较,在有缓存的情况下,三种方法搜索的耗时分别为:

  • 边递归遍历目录边匹配(类find):10.1秒
  • 递归遍历目录后用树存储目录结构再搜索:11毫秒
  • 递归遍历目录后用基础索引存储目录结构再搜索:8毫秒

下面是程序一的google-perftools性能剖析图。

图3 边遍历目录边搜索的程序性能剖析图

如果使用perfgoogle perftools进行性能剖析,可以看到在第一个程序里主要的程序耗时(60%)都花在了readdir函数上,17%的时间花在了opendir函数上。第二三个程序的主要耗时则是strstr函数与strlen函数,前者主要是为了进行字符串匹配,后者主要是为了遍历基础索引的线性存储空间中的文件名字符串,当然,strlen函数的调用仅出现第三个程序中,因此,相对于树形结构的程序来说第三个程序也有自己额外的性能开销。

下面是程序三的google-perftools性能剖析图。

图4 基于基础索引的搜索程序的性能剖析图

二级索引

上述基础索引的设计已经大大提高了基于文件名的搜索速度(相对于find而言),但这种搜索方法仍然需要从前至后遍历每个文件名进行搜索(即如性能剖析所示,调用strstr函数的开销)。从表面上看,因为需要对每个文件名进行检查,以得知其是否匹配搜索串,貌似很难更快了。但事实上,我们还可以做得更好,那就是使用倒排索引(inverted index)。

倒排索引的原理是对原字符串进行切割,得到其所有的子字符串,再将这些子字符串存放到对应的索引数据结构中,当用户输入对应的子字符串时能立刻找到相应的原始字符串。

例如原始字符串为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返回给调用者,由调用者通过这个偏移量或者指针得到”china”这个字符串。

在简单的倒排索引设计中,一般使用哈希链表或者Trie树作为索引数据结构。anything使用的是哈希链表。其工作原理是,当用户输入某个查询字符串(如hi)时,anything将首先对字符串进行一次哈希运算,得到哈希数组中的下标值,然后根据下标值即可得到对应的索引数组,在索引数组里顺序查找即可得到对应的索引(即hi),从而可以获取到所有的包含hi字符串的原始字符串的偏移量,将其返回给调用者。

关于倒排索引、哈希链表和Trie树的资料,网上和相关的书籍已经非常丰富了,在这里不再赘述。

下面是对二级索引内存消耗的分析,以及哈希链表设计问题的讨论。

对于长度为L的串,其生成的索引中,长度为1的子串有L个,长度为2的子串有L-1个,……,长度为L的子串有1个,则一共有L + (L-1) + …… + 1 = L x (L+1) / 2个子串,消耗的存储空间为1xL + 2x(L-1) + 3x(L-2) + … + Lx1 = Lx(L+1)x(L+2)/6,若考虑到字符串指针(在64位系统上为8字节)与字符串结尾的0字符,则额外需要Lx(L+1)/2x(8+1)个字节,合计为Lx(L+1)x(L+29)/6个字节。当然,其中字符串是可以被重用的,但是不一定能被重用,因为越长的串重复可能性越低。而且另一方面来说,这里的串是包括了中文字符的串,转成utf8后索引还会更长,此处的分析也忽略了这一点。下面是几个典型的数据:

  • 串长5时,占用170字节
  • 串长10时,占用715字节
  • 串长20时,占用3,430字节
  • 串长30时,占用9,145字节
  • 串长40时,占用18,860字节
  • 串长50时,占用33,575字节
  • 串长60时,占用54,290字节
  • 串长70时,占用82,005字节
  • 串长80时,占用117,720字节

可以发现一个串长80的文件名产生的空间占用就等效于164个串长为10的文件名,或者692个串长为5的文件名,虽然80仅是10的8倍,以及5的16倍。此外,真实的文件名还是有可能挺长的,比如.git目录下的文件名,以及debian的patch文件名等。在测试环境下,38.7万个文件(目录)中一共有12个长度超过80个字符的文件(目录)名,有1888个长度为67个字符的文件(目录)名,以及4013个长度为70个字符的文件(目录)名。

对于38.7万个文件与目录遍历的实测表明,其索引内存占用将超过2G,这完全是不可接受的。因此,二级索引需要进行优化。

anything使用的优化是对索引的最大长度加以限制。这是因为在实际使用中,用户真正输入的字符串不会很长,而且在索引串长到一定值之后,得到的原始字符串已经非常少,完全可以使用原始字符串进行二次匹配了。这样优化后,首先,索引数可以减少,其次,每个索引的长度也会减少,再加上使用的是4字节的偏移量,而不是8字节的指针,因此可以进一步减少内存消耗。下面是根据上述算法得到的内存消耗结果计算:

  • 串长5时,占用110字节
  • 串长10时,占用452字节
  • 串长20时,占用1,212字节
  • 串长30时,占用1,972字节
  • 串长40时,占用2,732字节
  • 串长50时,占用3,492字节
  • 串长60时,占用4,252字节
  • 串长70时,占用5,012字节
  • 串长80时,占用5,772字节

可以发现,内存消耗有了很大的减少,在对上述含有38.7万个文件与目录的遍历表明,其索引有大约六百万个,索引占用内存约230M,程序占据内存不超过500M(因为动态内存分配需要大量的额外内存空间),基本可以接受。

下面再来看哈希链表的设计。

在基础索引中,如果是38.7万文件与目录,则一共需要进行38.7万次strstr的调用以完成一次完整的查找。在二级索引中,如果没有哈希链表,则需要对所有生成的索引进行从前至后的strcmp调用,一共有约六百万个索引,则需要进行六百万次strcmp调用,如果考虑到还对索引进行了最大长度限制,还需要进行一定数量的strstr调用以进行二次确认。这样二级索引就完全成了一个笑话了,不仅耗费内存多,还会导致搜索慢,简直一无是处。

如果使用了哈希链表,可以将具有相等哈希值的索引存放到一个数组中,然后将这些数组再存放到一个更大的哈希数组中,使得这六百万个索引尽量均匀地分布开。这样每次查找的时候就可以大大减少strcmp的次数了。在这里,anything采用了质数模的方法作为哈希函数,程序里使用的质数模是一个梅森数,即131071,如果此哈希函数能将索引值完全均匀分布的话,大约每个哈希数上将会有6000/131 ≈ 46个索引,当然,在实际中哈希函数不可能绝对均匀,假设其较差的值为5000个,那也可以将strcmp的次数减少1200倍,是一个极大的性能提高了。在较差的情况下,假设有100个文件满足要求,则只需要进行一次哈希计算,5000个strcmp函数调用和100多个strstr函数调用即可找到满足条件的文件名了。对比基础索引搜索需要的38.7万个strstr调用,确实提高了数十倍的性能。

下面是在测试环境中四个搜索方法的简单对比:
* 类find:10.1秒,系统缓存增加260 MB
* 树搜索:11毫秒,存储数据内存需要30 MB
* 基础索引搜索:8毫秒,存储数据程序内存需要7 MB
* 二级索引搜索:0.4毫秒,存储数据程序内存需要230 MB

当然,二级索引的问题在于其占用内存实在太大,对于38.7万个文件与目录的文件数来说,基础索引约占用7 MB内存,而二级索引则需要占用约230 MB内存。其次,当发生文件系统变更的时候,基础索引的变更比较容易实现,但是二级索引的更新就相当繁复了,需要遍历所有的索引,找到对应的原始字符串偏移量进行修改。此外,二级索引的文件保存与载入也较为麻烦,因为需要将一整个哈希链表序列化与反序列化,而且当文件系统变更时,一旦变更了索引,则需要进行数百兆甚至上G数据的重新序列化,也会增大磁盘压力。

因此,除非是在对文件名搜索速度非常关键的场所或者离线搜索的场景下,不然使用基础索引进行文件名搜索即可满足要求了。

文件系统监控

在上面可以看到搜索提速最重要的原因是省去了系统调用,但是文件系统是会不停变化的,因此anything需要对文件系统进行监控,在其发生变化时对内部的基础索引进行修改,以保证搜索的正确性与实时性。

everything对于文件系统变更的追踪相对简单一些,因为它直接依赖于Windows下NTFS文件系统的日志。但是在Linux下,首先文件系统繁多,例如RHEL 7/CentOS 7采用的缺省文件系统是XFS,但是Debian与RHEL 6/CentOS 6使用的缺省文件系统却是ext4,而且这两者的文件系统日志都没有NTFS全,除此之外还有btrfs等一系列的其它文件系统。其次是在Linux下,管理员或者用户对于文件系统的选择较多,并且可以深入调整文件系统的参数,例如去掉日志,因此仅依赖于文件系统日志检查文件系统的变更是不太可靠的。

另外,由于Linux本身没有全局的文件创建、删除与重命名的用户态监听接口(比较接近的inotify无法递归监控目录),因此要解决此问题,只能使用独立的模块监听文件的创建、删除与重命名,并通知相应的用户态程序更新文件系统数据与索引数据。

在Linux下,监控整个文件系统的变化可以采用用户态或内核态的方法,其中用户态的方法包括:

  • 定时遍历文件系统,对整个文件系统的数据进行更新,这种方法需要每次都进行全量扫描,因此浪费极大,早期GNU findutils里的updatedb即提供了类似的功能
  • 使用preload库,监控glibc对应函数的参数与返回值,包括openfopencreatmkdirrmdirrename等。这种方式的优点是不依赖于内核,但是它会对所有依赖于glibc库的程序都造成影响,影响面大,工作量也不小(函数较多,参数处理较多),而且具有较大的安全隐患,此外,对于静态编译libc库的程序,以及不依赖于libc库的程序(虽然这种程序很少)无法监控
  • 使用inotify,递归监控所有子目录,监控资源消耗极大
  • 使用审计系统,加入对相应系统调用(opencreatmkdir等)的审计,通过审计日志检查系统调用的结果,根据结果更新文件系统数据。其优点是不依赖于内核,系统调用数量较少,但是缺点是需要依赖于审计系统,而且事后处理日志的方式会缺少关键的场景信息,例如之前的文件或者目录是否存在

除此之外,还可以采取编写内核模块的方法来进行监控:

  • 使用内核tracepoint特性对系统调用入口与出口进行事件跟踪,并记录处理结果,缺点是会对所有的系统调用进行跟踪,因此需要自己过滤,而且系统调用路径较长,可能会导致较多的资源占用
  • 通过kprobes对内核函数进行挂钩,在函数入口和出口处进行参数与返回值进行检查,当发现满足要求的文件事件时将事件信息记录下来,其缺点是对比tracepoint来说,kprobes从理论上来说依赖的函数变化的可能性更大一些,当内核升级时可能会带来维护的问题
  • 通过ftrace对内核函数进行挂钩,ftrace处理内核函数挂钩比kprobes更方便,没有架构相关的问题,而且不需要考虑kprobes中不能休眠的问题,但是ftrace较kprobes更新一些,需要更高版本的内核支持,部分架构的内核尚未提供完善的ftrace功能

anything现在选择的是kprobes功能,主要是考虑到kprobes的支持更广泛些,而且监控的内核函数也相对稳定。具体到需要跟踪的内核函数,主要就是VFS的文件系统变更函数,包括vfs_create等,为了确保只有当函数成功返回时才进行记录,anything需要使用kretprobes进行函数跟踪。

需要注意的是,使用kretprobes有一个与架构相关的问题,那就是要在函数入口处得到函数各参数的值,而在这里,kretprobes没有给开发者提供很多便利,需要根据内核的寄存器结构体(pt_regs)来根据架构的函数调用规约获取相关的参数值。例如对于x86来说,其64位系统的函数调用规约是从第一个参数开始分别使用rdi、rsi、rdx、rcx、r8与r9寄存器保存参数,从第七个参数开始使用栈来保存剩余的参数。这些代码都被封装到源码的kernelmod/arg_extractor.c里了,因此,当需要扩展架构支持时,主要在这里进行修改即可。此外,在实际使用中,anything现在仅用到了前四个参数,因此只要处理n等于1到4的情况就够了。

内核模块对外提供了/proc/vfs_changes文件以向用户态的应用程序提供文件系统更新信息的访问接口,当应用程序通过此文件获取到文件系统更新信息后,即可更新对应的基础索引数据了。由于基础索引的数据结构设计使得一个目录树被保存在连续的一段内存里,因此对文件系统的更改都非常方便,最大的开销就是memmove而已,这个变更速度在x86上,对于10M的内存,只需要耗费毫秒级的时间。

后记

anything是一个小巧的软件,它的功能很单一,开发时间也不长,总共的开发时间大概只有四个多星期,中间还经历了项目的打扰。但是它也达到了自己的目标,即为文件名搜索提供一个高效快速的实现,而且对现有的系统侵入很小。不过,由于时间的限制,二级索引的更新没有做完,留了一个尾巴,希望以后能有机会完成吧。

展望未来,我们认为anything可以在今后考虑下面的改进:

  • 使用ftrace代替kprobes,以避免处理kprobes中无法休眠的问题,以及与架构相关的处理逻辑
  • 索引全部落盘,而不是放在内存中,以提高伸缩性,比如可以支持数千万个文件的同时内存仅需要十兆左右
  • 兼容GNU findutils的locate命令的语法
  • 使用eBPF等功能对VFS函数进行跟踪,以避免使用内核模块

希望大家能喜欢这个开源软件,并能为它提交PR。当然,anything现在仅支持文件名搜索,如果需要进行使用其他文件元数据进行搜索,也是可行的。但如果是要支持全文检索,可能就需要使用全新的设计了,这就又是一个新的问题了。

到这里,就到这里吧。

发表评论

电子邮件地址不会被公开。 必填项已用*标注