首页 > 编程语言 >Overlay fs联合文件系统源码解析系列(一)挂载过程详解

Overlay fs联合文件系统源码解析系列(一)挂载过程详解

时间:2023-04-14 12:01:10浏览次数:53  
标签:fs Overlay mount mnt 文件系统 源码 挂载 ovl

作者:蒋卫峰 钟文清

<br>

引言

分析Overlay fs联合文件系统源自于培养OpenHarmony高端人才的动机,通过讲Overlay fs联合文件系统移植到Liteos_A内核的项目培养一批精通OpenHarmony内核的人才,也通过本文向各位热爱OpenHarmony内核的技术开发者和爱好者叙说一个复杂文件系统的具体实现过程和包含的软件思想,我们是一群热爱OpenHarmony,热爱开源,传递技术正能量的OpenHarmony开发工程师。

Overlay fs是一种联合文件系统,它以堆叠的形式将不同的目录挂载到同一个虚拟文件系统下。Overlayfs文件系统像其他文件系统一样,先被作为一种文件系统注册到Linux内核,而后用户通过Mount命令触发其挂载,然后才得以被用户使用。

需要注意的是,Overlay fs在Linux内核3.18后就被默认加入内核模块了,查看Linux内核版本可以使用如下命令:

uname -r

为了更好地帮助我们理解overlay fs的作用,可以在Linux上开启overlay模块,并做些简单的实验,再去阅读源码会有更好的效果。在Linux上开启overlay fs模块的方法主要有两种,具体如下所示:

  1. 使用如下命令进行加载overlay模块

    # 查看是否已加载overlay 模块
    lsmod | grep overlay
    
    # 若没有加载则可手动加载
    modprobe overlay
    
  2. overlay会在挂载的时候自动加载该文件系统,故可以直接使用如下命令进行overlay模块的安装和挂载

    # 直接继续overlay fs的挂载,自动加载overlay模块
    mount -t overlay overlay -o lowerdir=/lower,upperdir=/upper,workdir=/work  /merged
    

加载overlay模块后,就可以进行一些实验,而本文主要关注Overlay fs挂载流程,结合Linux内核源码分析挂载过程的执行过程,并通过将该过程中涉及到的主要数据结构之间的联系绘制成结构图,来尽可能清晰地为读者展现一张文件系统核心数据结构整体图。

鉴于作者知识有限,仅以个人视角,一孔窥豹,不成体系,读者还需实地阅读代码才能加深理解。

若发现文中错误,可以联系笔者进行修改。

<br>

1.Overlay fs挂载命令介绍

Overlay fs挂载命令格式如下:

# 该命令指定一个lower层,一个upper层
sudo mount -t overlay overlay -o lowerdir=/lower,upperdir=/upper,workdir=/work /merged

# 若需要指定多个lower层,可以使用如下命令
sudo mount -t overlay overlay -o lowerdir=/lower1:/lower2:/lower3,upperdir=/upper,workdir=/work  /merged

其中,overlay文件系统挂载的命令参数解释如下:

  • -t overlayfs,指定挂载Overlay fs联合文件系统;
  • -o lowerdir=/lower,upperdir=/upper,workdir=/work,即lower层目录为**/lower**,uppper层目录为**/upper**,工作目录为**/work**;
  • /merged为Overlay文件系统的合并层,其为upper和lower两个目录的堆叠,具体的堆叠规则稍后说明;

需要注意的几点:

  1. workdir=/work<u>不可为空或者省略</u>,否则会导致挂载失败。

  2. 在创建工作目录时,系统会默认在该目录下创建一个名称为WORK的新目录,<u>用于存放临时文件或者目录</u>。例如在删除由Lower层和Upper层目录合成的目录时,既需要删除Upper层同名的目录,又要中创建一个同名whiteout类型目录,要保证这个删除和创建两个操作的原子性,就要借助于WORK工作目录。现在WORK目录中创建临时目录,设置属性,然后将临时目录与目标目录rename,借助于Upper层文件系统保证rename的原子性,然后在删除交互到WORK目录下的目录,完成整个删除操作。即使这个过程,中间遇到突然关机的情况,在WORK目录中也是只有刚创建的临时文件或者交换过去的临时文件,在下一次系统挂载的过程中自动清空其中的内容。这样,就可以保证整个过程的原子性。

Overlay文件系统的不同层合并规则以及读写规则有如下几点:

  1. Overlay 对Upper层目录或者文件有写权限,对Lower层目录或者文件<u>仅具有读权限</u>;
  2. lowerdir和upperdir两个目录存在同名文件时,lowerdir的文件将会被隐藏,用户只能看到upperdir的文件;
  3. lowerdir低优先级的同目录同名文件将会被隐藏;
  4. 用户修改mergedir中来自upperdir的数据时,数据将直接写入upperdir中原来目录中,删除文件也同理;
  5. 用户修改mergedir中来自lowerdir的数据时,lowerdir中内容均不会发生任何改变;
  6. 如果某一个目录单纯来自lowerdir或者lowerdir和upperdir合并,默认无法进行rename系统调用

为了简要形象地说明Overlay文件系统挂载之后的堆叠(合并)规则,可以参考下图,图中含有一个lowedir和upperdir,两者合并成一个merged层

alt="合并演示"

这一小结中Overlay fs文件系统挂载的的命令行参数,就介绍到这里,下面主要关注Overlayfs的挂载过程。


2. mount系统调用过程

使能Linux内核Overlay fs文件系统编译选项CONFIG_OVERLAY_FS,或者以=y静态方式编译进内核,或者先以=m内核模块方式编译再加载该内核模块,在Linux内核层添加对Overlay fs联合文件系统的支持。 然后以mount -t overlay overlayfs,触发mount系统调用,进行挂载Overlayfs文件系统的流程。

mount系统调用挂载Overlay fs文件系统的过程如下:

SYSCALL_DEFINE5(mount,,,,,,,) // fs/namespace.c
|-> user_path_at(AT_FDCWD, dir_name, LOOKUP_FOLLOW, &path);
|-> do_mount(kernel_dev, dir_name, kernel_type, flags, options);
    |-> path_mount(dev_name, &path, type_page, flags, data_page);
        |-> do_new_mount()
            | // (1) 找到指定文件系统
            |-> type = get_fs_type(fstype);
            |           |-> find_filesystem(name, len)
            |           |-> for (p = &file_systems; *p; p = &(*p)->next)
            |           |-> strncmp((*p)->name, name, len) == 0
            |           |-> return p;
            |
            | // (2) 创建fc
            |-> fc = fs_context_for_mount(type, sb_flags);
            |        |-> alloc_fs_context(fs_type, NULL, sb_flags, 0, FS_CONTEXT_FOR_MOUNT);
            |                |-> fc = kzalloc(sizeof(struct fs_context), GFP_KERNEL);
            |                |-> fc->fs_type    = get_filesystem(fs_type);
            |                |-> legacy_init_fs_context(fc);
            |                    |-> fc->fs_private = kzalloc(sizeof(struct legacy_fs_context), GFP_KERNEL);
            |                    |-> fc->ops = &legacy_fs_context_ops;
            |
            | // (3) 将fc的root指针指向overlayfs挂载点根root目录
            |-> vfs_get_tree(fc)
            |   | // 通过fc的get_tree间接调用文件系统mount函数,以获得挂载节点root目录项(记录在fc中)
            |   | // fc->ops->get_tree(fc); => legacy_get_tree
            |   |-> legacy_get_tree(fc) // 将挂载点的root目录项赋值到fc的root
            |       |-> root = fc->fs_type->mount(fc->fs_type, fc->sb_flags, fc->source, ctx->legacy_data);
            |       |-> fc->root = root; // struct dentry *
            |
            | // (4) 创建mount实体,并将其挂载到supper_block的挂载链表中
            |-> do_new_mount_fc(fc, path, mnt_flags);// path的形参即为mountpoint,是实际文件系统中mount挂载目标路径
                |-> mnt = vfs_create_mount(fc);
                |         |-> mnt = alloc_vfsmnt(fc->source ?: "none");
                |         |-> mnt->mnt.mnt_sb       = fc->root->d_sb;
                |         |-> mnt->mnt.mnt_root = dget(fc->root);
                |         |-> mnt->mnt_mountpoint   = mnt->mnt.mnt_root;
                |         |-> mnt->mnt_parent       = mnt;
                |         |-> list_add_tail(&mnt->mnt_instance, &mnt->mnt.mnt_sb->s_mounts);
                |
                |-> do_add_mount(real_mount(mnt), mp, mountpoint, mnt_flags);

如上系统调用mount的简化调用堆栈中可以看出,整个mount流程可以总结为4个步骤: (1)根据文件系统名称fstype,在内核所支持的文件系统链表中,找到对应的文件系统,若没有找到则先加载该模块; (2)创建文件系统上下文空间,并初步初始化,对Overlay fs联合文件系统,fc的ops设置为legacy_fs_context_ops; (3)由文件系统fc间接调用文件系统的mount接口,对Overlay fs文件系统来说,该指针指向ovl_mount(),由该函数完成Overlay fs文件系统的挂载; (4)在Overlay fs文件系统挂载完成后,创建一个mount节点,并将其挂载到Overlayfs文件系统supper_block的挂载链表内;

上述几个步骤中**,关键结构体的链接情况**可以参考下图:

如上图,为了便于理解和记忆,可以将mount过程中的关键结构体抽象成4个层次,即mount层,fs_context层,fs文件系统层,以及目录项节点层。首先,从系统支持的文件系统链表中获得Overlayfs文件系统,然后创建fs_context对象,并以此间接地调用Overlay fs文件系统的mount接口函数。由ovl_mount()挂载函数完成Overlayfs文件系统所特有的挂载过程,有上图Overlayfs有一个独有的表示其文件系统结构的结构体类型struct ovl_fs,作为其super_block的私有数据,以有别与其他的文件系统。

在第3小结中,我们将详细地解析Overlay fs文件系统的挂载过程。


3. Overlay fs文件系挂载过程详解

如前文所述,真正实现Overlay fs联合文件系统挂载过程的函数是由fc_context间接调用的ovl_mount()过程,过程也比较简单,就是申请一个supper_block, 然后使用Overlayfs文件系系统的信息将其填充。 具体过程如下:

ovl_mount() // fs/overlayfs/super.c
|-> mount_nodev(fs_type, flags, raw_data, ovl_fill_super); // return "dentry* s_root"
    | // (1) 为新挂载点创建superblock
    |-> s = sget() // struct super_block *
    |       |-> s = alloc_super(type, (flags & ~SB_SUBMOUNT), user_ns); 
    |       |-> list_add_tail(&s->s_list, &super_blocks);
    |
    | // fill_super()
    |-> ovl_fill_super(s, data, flags & SB_SILENT ? 1 : 0)
        |-> struct ovl_fs *ofs; // private information held for overlayfs's superblock
        |-> struct ovl_layer *layers;
        |
        |-> ofs = kzalloc(sizeof(struct ovl_fs), GFP_KERNEL);
        |-> sb->s_d_op = &ovl_dentry_operations;
        |-> ovl_parse_opt((char *) data, &ofs->config);
        |-> numlower = ovl_split_lowerdirs(splitlower);
        |
        | // 创建联合文件系统层级数组
        |-> layers = kcalloc(numlower + 1, sizeof(struct ovl_layer), GFP_KERNEL);
        |-> ofs->layers = layers;
        |
        |-> sb->s_op = &ovl_super_operations;
        |
        | // 设置upperlayer:设置layer的trap执行upperpath目录的inode;依据upperpath在实际文件系统中的挂载点填充layer的挂载点(ovl挂载的root为实际文件系统中一指定目录);
        |-> ovl_get_upper(sb, ofs, &layers[0], &upperpath);
        |   | // 获得upperlayer目录在实际文件系统上路径:若路径未打开过,则创建路径上的所有节点的dentry与inode
        |   |-> ovl_mount_dir(ofs->config.upperdir, upperpath);
        |   | // 为挂载点创建一个inode,保存在trap中:新inode的private数据指向实际文件系统中挂载点目录的inode
        |   |-> ovl_setup_trap(sb, upperpath->dentry, &upper_layer->trap,  "upperdir");
        |   | // 拷贝upper层实际文件系统路径的挂载点为虚拟堆叠文件系统一个层次的新mount节点,且新的mount节点的root目录为uppper目录;
        |   |-> upper_mnt = clone_private_mount(upperpath);
        |   |-> upper_layer->mnt = upper_mnt;
        |
        | // 创建workdir: workbasedir为指定的实际文件系统内的目录,workbasedir_trap对workbasedir的inode的trap;workdir为workbasedir下创建的默认名称为“work”的目录
        |-> ovl_get_workdir(sb, ofs, &upperpath);
        |   |-> ofs->workbasedir = dget(workpath.dentry);
        |   | // 申请一个ovl_inode,使其private指向实际文件系统inode,新对象地址保存在ofs->workbasedir_trap内
        |   |-> ovl_setup_trap(sb, ofs->workbasedir, &ofs->workbasedir_trap, "workdir");
        |   |
        |   |-> ovl_make_workdir(sb, ofs, &workpath);
        |
        | // 逐个获取lower层,检查是否已经有打上“trap”标记的inode,同时为每个lower层的root inode打上“trap”标记
        |-> oe = ovl_get_lowerstack(sb, splitlower, numlower, ofs, layers);
        |
        | // 对每个层对应root inode的parent递归检查是否已经打上“trap”标记,重叠层可能是互为祖先关系
        |-> ovl_check_overlapping_layers(sb, ofs);
        |
        |-> sb->s_fs_info = ofs;
        |
        |-> root_dentry = ovl_get_root(sb, upperpath.dentry, oe);
        |
        |-> sb->s_root = root_dentry;

由于Overlay fs文件系统叠层联合文件系统,那么在执行mount命令时指定upper目录、lower目录及work目录,是如何在Overlayfs内被组织利用,进而实现层叠联合文件系统的呢?该过程为Overlayfs文件挂载的核心过程,主要在ovl_fill_super()函数内完成。

在ovl_fill_super()的主要过程为: (1)从overlayfs挂载命令中获取Lower层的个数,并以此分配layers空间; (2)解析Upper层,包括挂载路径,原系统的挂载节点、挂载目录等; (3)解析Work工作目录,并做必要合法性检测; (4)解析lower层,可能包含多个叠层,需要对每一层都进行解析,并将解析结果保存layers中; (5)设置overlayfs系统根目录;

其中,比较复杂而且关系到Overlayfs整个实现机制的步骤为(2)、(4)和(5),在下面的内容中将着重介绍这些内容,之后便可以对整个Overlay fs联合文件系统的挂载过程形成一个整体蓝图。

3.1 Upper层过程解析

Overlay fs对upper层目录的解析过程在ovl_get_upper()函数中完成,主要分为3个步骤:

(1)查找upper层目标目录的路径,是根据挂载Overlayfs提供的upperdir路径,层层查找得到; (2)设置upper_layer的trap,trap即为Overlayfs文件系统中的一个inode,其私有数据指向upper目录在实际文件系统中的inode; (3)创建一个upper层目录挂载节点的克隆体,并设置为upper_layer的mnt成员;

如下为ovl_get_upper()函数的调用堆栈:

ovl_get_upper(sb, ofs, &layers[0], &upperpath);
|-> struct vfsmount *upper_mnt;
| // (1)解析upper目录:沿着用户指定的upper目录路径解析,直至找到目录的目录项
|-> ovl_mount_dir(ofs->config.upperdir, upperpath);
|   |-> tmp = kstrdup(name, GFP_KERNEL);
|   |-> ovl_mount_dir_noesc(tmp, path);
|       |-> kern_path(name, LOOKUP_FOLLOW, path);
|           |-> filename_lookup(AT_FDCWD, getname_kernel(name), flags, path, NULL);
|
| // (2)设置upper_layer的trap:即从Overlayfs超级块新申请一个inode,并将upper目录的inode设置为其私有数据
|-> ovl_setup_trap(sb, upperpath->dentry, &upper_layer->trap,  "upperdir");
|   |-> trap = ovl_get_trap_inode(sb, dir);
|   |          |-> struct inode *key = d_inode(dir);
|   |          |-> struct inode *trap;
|   |          |-> trap = iget5_locked(sb, (unsigned long) key, ovl_inode_test, ovl_inode_set, key);
|   |          |-> return trap;
|   |-> *ptrap = trap;
|
| // (3)创建一个upper层目录挂载节点clone体,并赋值给upper_layer的mnt成员
|-> upper_mnt = clone_private_mount(upperpath);
|               |-> struct mount *old_mnt = real_mount(path->mnt);
|               |-> struct mount *new_mnt;
|               | // 创建一个upper层的mount节点的clone体,并且将其挂载到upper层超级块的挂载点链表上
|               |-> new_mnt = clone_mnt(old_mnt, path->dentry, CL_PRIVATE);
|               |             |-> struct super_block *sb = old->mnt.mnt_sb;
|               |             |-> struct mount *mnt;
|               |             |
|               |             |-> mnt = alloc_vfsmnt(old->mnt_devname);
|               |             |-> mnt->mnt.mnt_sb = sb;
|               |             |-> mnt->mnt.mnt_root = dget(root);
|               |             |-> list_add_tail(&mnt->mnt_instance, &sb->s_mounts);
|               |
|               |-> return &new_mnt->mnt;
|-> upper_layer->mnt = upper_mnt;

为方便理解,将ovl_get_upper()中涉及的结构类型ovl_layer、mount、dentry和inode等的关联关系绘制成如下图形:

image-20230213193839714

3.2 lower层过程解析

Overlayfs对upper层目录的解析过程在ovl_get_lowerstack()函数中完成,lower层与upper层不同是lower层可能有多个目录叠加在一起,需要对lower层 目录做批量处理,过程有些类似于ovl_get_upper()对upper层的解析过程:

static struct ovl_entry *
ovl_get_lowerstack(struct super_block *sb, const char *lower, unsigned int numlower, struct ovl_fs *ofs, struct ovl_layer *layers)
|-> struct path *stack = NULL;
|-> struct ovl_entry *oe;
|
| // (1)分配并初始化深度与lower层目录树对应的path数组
|-> stack = kcalloc(numlower, sizeof(struct path), GFP_KERNEL);
|-> for (i = 0; i < numlower; i++) {
|       // 依次解析所有lower层目录
|->     err = ovl_lower_dir(lower, &stack[i], ofs, &sb->s_stack_depth);
|-> }
|
| // 根据lower层目录数组设置Overlayfs文件系统及其layers
|-> ovl_get_layers(sb, ofs, stack, numlower, layers);
|   |-> ofs->fs = kcalloc(numlower + 1, sizeof(struct ovl_sb), GFP_KERNEL);
|   |
|   |-> ofs->fs[0].sb = ovl_upper_mnt(ofs)->mnt_sb;
|   |-> ofs->fs[0].is_lower = false;
|   |
|   |-> for (i = 0; i < numlower; i++) {
|   |->     ovl_setup_trap(sb, stack[i].dentry, &trap, "lowerdir");
|   |->     mnt = clone_private_mount(&stack[i]);
|   |->     layers[ofs->numlayer].trap = trap;
|   |->     layers[ofs->numlayer].mnt = mnt;
|   |->     ofs->fs[fsid].is_lower = true;
|   |-> }
|
| // 设置overlayfs文件系统的根目录ovl_entry
|-> oe = ovl_alloc_entry(numlower);
|-> for (i = 0; i < numlower; i++) {
|->     oe->lowerstack[i].dentry = dget(stack[i].dentry);
|->     oe->lowerstack[i].layer = &ofs->layers[i+1];
|-> }
|
| // 释放临时存放lower层路径的path数组
|-> kfree(stack);
|-> return oe;

仔细阅读如上代码,我们会发现除了批量执行类似于ovl_get_upper()中解析目录操作外,还增加了分配并初始化一个ovl_entry类型结构实例的过程, 该ovl_entry的在Overlayfs虚拟文件系统中的功能主要为Overlayfs文件系统中的目录提供额外的联合文件系统的Lower层目录信息,其作用我们将在 root根目录初始化的过程中见到。

将ovl_get_lowerstack()内创建的数组和相关结构体类型的关系绘制成如下图形:

image-20230213190546351

从上图可知,ovl_get_lowerstack()的功能相对于ovl_get_upper()揉进了额外的功能,除了构建ovl_fs的layers数组外,还构建了fs数组,另外还构建Overlayfs目录的ovl_entry结构体对象。可以明显的感觉到,这部分代码不像Linux内核一贯严谨的代码风格,在一个函数混合了多个功能。 其中的lowerstack关系图可以参考下图,分别用图表和代码的形式绘制。

image-20230213185412287

3.3 root根目录构建过程解析

文件系统的目录和文件操作是以root根目录为起点,而对于Overlayfs联合文件系统,知道root根目录的构建过程,是理解该联合文件系统操作目录的关键。Overlayfs文件系统依靠ovl_get_root()完成根目录的构建,具体调用堆栈如下:

static struct dentry *
ovl_get_root(struct super_block *sb, struct dentry *upperdentry, struct ovl_entry *oe)
|-> struct dentry *root;
|-> struct ovl_path *lowerpath = &oe->lowerstack[0];
|-> struct ovl_inode_params oip = {
|->     .upperdentry = upperdentry,
|->     .lowerpath = lowerpath,
|-> };
|
|-> root = d_make_root(ovl_new_inode(sb, S_IFDIR, 0));
|-> root->d_fsdata = oe;
|
|-> ovl_inode_init(d_inode(root), &oip, ino, fsid);
|   |-> OVL_I(inode)->__upperdentry = oip->upperdentry;
|   |-> OVL_I(inode)->lower = igrab(d_inode(oip->lowerpath->dentry));
|
|-> ovl_dentry_update_reval(root, upperdentry, DCACHE_OP_WEAK_REVALIDATE);
|-> return root;

为便于理解其中繁杂的结构体之间的组合关心,还是将他们直接的关系绘制成如下图形:

image-20230213193218708

在构建root根目录的过程中,ovl_get_root()首先调用d_make_root(ovl_new_inode(sb, S_IFDIR, 0))创建一个ovl_inode类型的Overlay fs系统的inode节点,该节点中包含一个VFS系统的inode结构体;再创建一个跟目录价的dentry目录项,并将ovl_inode包含的inode成员的地址赋值给dentry目录项的d_inode指针。然后,ovl_get_root()将ovl_get_lowerstack()解析lower层目录时创建的ovl_entry结构体对象作为root根目录dentry的私有数据。最后,ovl_get_root()借助upper和lower目录在ovl_inode_init()函数内初始化了root根目录在VFS中的inode节点,借此间接设置了ovl_inode对象的上层目录的dentry和第一个lower层的inode节点地址。

至此,我们完成了挂载Overlayfs文件系统的整个过程。

总结

Overlay fs是一种虚拟文件系统,它的实现是在现有文件系统上又添加了一个抽象层,从而达到实现联合文件系统的目的。而这个抽象层的实现借助了负责的结构体类型以及他们之间的关联关系而实现,所以,要理解Overlay fs联合文件系统的关键就是理清这些结构体的组织关系。

为了能明白地解析Overlayfs文件系统挂载过程,本文只尽可能详细跟踪了代码执行过程,同时也省略了“自以为”不影响描述整个过程的代码,主要目的也是为了是读者更加关注在挂载流程。至于其他机制,例如目录的合并、目录或者文件的删除、目录的遍历等,这里不做涉及,将在后续的博客中介绍。

更多原创内容请关注:深开鸿技术团队

入门到精通、技巧到案例,系统化分享OpenHarmony开发技术,欢迎投稿和订阅,让我们一起携手前行共建生态。

想了解更多关于开源的内容,请访问:​

​51CTO 开源基础软件社区​

​https://ost.51cto.com/#bkwz​

标签:fs,Overlay,mount,mnt,文件系统,源码,挂载,ovl
From: https://blog.51cto.com/harmonyos/6189862

相关文章

  • melange 基于源码构建apk 包的工具
    实际上melange是apko的相关项目,结合起来可以更好的创建基于apk的oci镜像,melange主要是定义了一套pipeline可以方便的进行apk包开发安装可以基于docker运行 goinstallchainguard.dev/melange@latest使用配置package:name:h......
  • POJ 1780 Code (欧拉回路+非递归版dfs)
    题目地址:POJ1780还是求序列的欧拉回路。只不过这题有两坑。第一坑是用数字来当点的话,会MLE,因为每个数字可以连10条边,100w条边会MLE,即使用vector也会TLE。这题可以用边来记录,对于n为1时直接输出,然后后面的,比如12,23这两个点就用边权值为123来表示这两个点,这样就把点和边的范围......
  • Codeforces Round #286 (Div. 2) C题 Mr. Kitayuta, the Treasure Hunter (DFS+记忆化D
    题目地址:http://codeforces.com/contest/505/problem/C从d点开始,每个点都有三个方向,形成了一棵树,那么就从跟结点开始进行dfs查找,dp数组记录当前的点和长度,当这两个条件相同的时候,显然,后面的子树是完全相同的,于是用记忆化来优化。代码如下:#include<iostream>#include<string.h>#......
  • PdfSharpCore是MIT开源协议
    PdfSharpCore是MIT开源协议,不过他依赖Sixlabors.Fonts和Sixlabors.ImageSharp库,Sixlabors已经修改了协议,https://sixlabors.com/pricing/上面的说明是:IfyouareconsuminganySixLaborslibrariesasaDirectPackageDependencyforusageinClosedSourcesoftwareinthe......
  • 源码共读 | 如何优雅的捕获 await 的错误
    前言Promise是一种在JavaScript中用于处理异步操作的机制。Promise在开发中被广泛使用,这篇文章将学习如何优雅的捕获await的错误。资源:仓库地址:await-to-js参考文章:Howtowriteasyncawaitwithouttry-catchblocksinJavascript(grossman.io)Promise的使用方法......
  • IDEA之如何Debug源码跟踪
    IDEA之如何Debug源码跟踪以Debug模式启动服务,左边的一个按钮则是以Run模式启动。在开发中,我一般会直接启动Debug模式,方便随时调试代码。断点:在左边行号栏单击左键,或者快捷键Ctrl+F8打上/取消断点,断点行的颜色可自己去设置。Debug窗口:访问请求到达第一个断点后,会自动激活Debug......
  • Codeforces Round #316 (Div. 2) D. Tree Requests (DFS序)
    题目地址:http://codeforces.com/contest/570/problem/D比赛的时候实在没想到DFS序,。。想到DFS序后,分别存起每个深度的所有节点的DFS序,处理出前缀异或和,然后二分找到两个端点,再异或一下,就求出了所求区间的异或和,由于偶数次的都被异或掉了,所以判断下奇数次数是否大于1即可。代码......
  • POJ 1753 Flip Game(bfs枚举+递推)
    题目地址:http://poj.org/problem?id=1753这题此前曾经做过,但当时是用的纯BFS做的,然后后来又做了一次组队赛,那是16*16的,果断超时超内存。。能超的都超了。。于是又找了个更好的方法,就是枚举第一行,然后后面的根据第一行的情况推下去。比如,你要让所有的都变成W,如果上一行的对应位置是B......
  • CTFSHOW 萌新web10-21
    ctfshow萌新web10-21web10题目提示flag在congfig.php中php中作为执行系统命令的函数:system()passthru()exec()shell_exec()popen()proc_open()pcntl_exec()源码中过滤了system,exec,highlight这三个常用的PHP命令执行函数,绕过过滤条件就可以使用eval()函数执行PH......
  • 【开源项目】虎门大桥数字孪生应用智慧桥梁——开放数据及源码
    体验虎门大桥数字孪生技术,免费获取工程和源码,助力您的工程数字化转型。项目介绍虎门大桥是中国广东省珠海市和东莞市之间的一座跨海大桥,是世界上最长的跨海大桥之一,也是中国的一项重要基础设施工程。通过数字孪生技术,成功地实现了对桥梁的仿真和优化,给虎门大桥带上智慧的"眼睛"。通......