Welcome¶

2021年3月2日
需要 1 分钟阅读时间

右值, 临时变量与引用

我们说的临时变量通常是指在语句块里定义的短暂生命周期的局部变量, 其存储周期为'auto'，但这里讨论的是c++中'temporary object', 是在老版本c++中而语句块里定义的变量以及非引用类型参数，并不属于这里的临时变量

c++中的临时变量出现情况： * litteral常量, 如1 * 类型转换 // 赋值语句结束后，自动销毁 * 函数返回值 // 赋值语句结束后，自动销毁 * 表达式的值

而临时变量的定义就是编译器自动创建和销毁的没有名字的变量, 也无法取地址。并且规定：
- 常量类型的引用（reference to const）可以绑定到临时变量 - 非常量类型的引用（reference to non-const）类型不能绑定到临时变量

这个规定的原因是：因为上面说的编译器自动创建和销毁，所以去修改一个会销毁变量是没有意义的

什么时候编译器要需要创建临时变量

创建原因	销毁时机
Result of expression evaluation	All temporaries created as a result of expression evaluation are destroyed at the end of the expression statement (that is, at the semicolon), or at the end of the controlling expressions for for, if, while, do, and switch statements.
Initializing const references	If an initializer is not an l-value of the same type as the reference being initialized, a temporary of the underlying object type is created and initialized with the initialization expression. This temporary object is destroyed immediately after the reference object to which it is bound is destroyed.

主要是以下两个地方会需要临时变量： * 函数接受引用类型参数的时候 * 函数返回的时候 * 类型转换的时候

举例：

函数参数

void foo(const int &arg){}
foo(1);  // 此时创建了临时变量，可以想象成'foo(int _tmp(i));' 而且这个_tmp 不能被修改

函数返回值

int foo(){return 1;}
int i=foo(); // 此时创建了临时变量， int _tmp = foo(); int i = _tmp;

类型转换

int i = 1;
double d = i; // double _tmp = i; double d = _tmp;

单独讨论这些似乎意义不大，但是在实际编写代码的时候，可能会有疑惑

例如如何解释

const int& cr = 1; // ok
int &r = 1; // ng

这里赋值和函数传参一样，因为1是常数，这里为常量1创建临时变量，而只有reference to const 才能绑定到临时变量上

还有解释一个经常被引用的例子

void foo(int &arg){}
int i = 1; foo(i); // ok
double d = 1.0; foo(d); // ng

void foo(const int &arg){}
int i = 1; foo(i); // ok
double d = 1.0; foo(d); // ok

这里虽然i和d都不是常量（不会创建临时变量），但是因为类型不同，发生了类型转换，创建了临时变量。同样地，只有reference to const 才能绑定到临时变量上

2021年2月5日
需要 2 分钟阅读时间

子串查找算法

leetcode的题目, 实现strstr,即查找子字符串

最简单的算法

int strStr(char * haystack, char * needle){
    char *tmp = haystack;
    while(*tmp != 0){
        if(strncmp(tmp, needle,strlen(needle))==0){
            return tmp - haystack;
        }
        tmp ++;
    }
    return -1;
}

kmp 算法

// C++ program for implementation of KMP pattern searching 
// algorithm 
#include <bits/stdc++.h> 

void computeLPSArray(char* pat, int M, int* lps); 

// Prints occurrences of txt[] in pat[] 
void KMPSearch(char* pat, char* txt) 
{ 
    int M = strlen(pat); 
    int N = strlen(txt); 

    // create lps[] that will hold the longest prefix suffix 
    // values for pattern 
    int lps[M]; 

    // Preprocess the pattern (calculate lps[] array) 
    computeLPSArray(pat, M, lps); 

    int i = 0; // index for txt[] 
    int j = 0; // index for pat[] 
    while (i < N) { 
        if (pat[j] == txt[i]) { 
            j++; 
            i++; 
        } 

        if (j == M) { 
            printf("Found pattern at index %d ", i - j); 
            j = lps[j - 1]; 
        } 

        // mismatch after j matches 
        else if (i < N && pat[j] != txt[i]) { 
            // Do not match lps[0..lps[j-1]] characters, 
            // they will match anyway 
            if (j != 0) 
                j = lps[j - 1]; 
            else
                i = i + 1; 
        } 
    } 
} 

// Fills lps[] for given patttern pat[0..M-1] 
void computeLPSArray(char* pat, int M, int* lps) 
{ 
    // length of the previous longest prefix suffix 
    int len = 0; 

    lps[0] = 0; // lps[0] is always 0 

    // the loop calculates lps[i] for i = 1 to M-1 
    int i = 1; 
    while (i < M) { 
        if (pat[i] == pat[len]) { 
            len++; 
            lps[i] = len; 
            i++; 
        } 
        else // (pat[i] != pat[len]) 
        { 
            // This is tricky. Consider the example. 
            // AAACAAAA and i = 7. The idea is similar 
            // to search step. 
            if (len != 0) { 
                len = lps[len - 1]; 

                // Also, note that we do not increment 
                // i here 
            } 
            else // if (len == 0) 
            { 
                lps[i] = 0; 
                i++; 
            } 
        } 
    } 
} 

// Driver program to test above function 
int main() 
{ 
    char txt[] = "ABABDABACDABABCABAB"; 
    char pat[] = "ABABCABAB"; 
    KMPSearch(pat, txt); 
    return 0; 
}

使用哈希区分两个字符串是否一致

哈希可以利用硬件加速，非常高效

2021年1月28日
需要 1 分钟阅读时间

创建 systemd 服务

说一个老话，现在systemd作为linux的启动管理和服务管理已经越来越重要了，上周考试也遇到用systemd 来管理容器，这里记录一下如何编写systemd服务

关于systemd

systemd是只能运行在Linux上的init, 也就是启动后看到的1号进程。除了启动， systemd还管理着很多东西，例如网络（systemd-networkd），域名解析（systemd-resolved），为服务创建socket(systemd.socket) 文件系统挂载，还有系统和用户的服务
systemd太大，说不完，需要查看各种文档

systemd 的两种使用模式

systemd 分为system级别和user级别，对应的unit文件分别在/etc/systemd/ 和～/.config/systemd/下，前者是系统级别，后者是用户级别。用户只能运行自己设置的服务

systemctl start system_service.service

而普通用户只能执行

systemctl --user user_service.service

这个name就是文件名称，例如必须'/etc/systemd/system/'下存在'system_service.service'文件，在能执行第一条的命令、必须在 '~/.config/systemd/user/'下存在'user_service.service'在能执行第二条命令

系统服务以其他用户运行服务

系统级别的服务默认会以root来运行服务，但是也可以设置以其他用户来运行来最小化权限，例如音视频服务。也可以以某个用户来执行，那么service unit 文件就变为'system_service@user.service'

# system_service@user.service
[Unit]
Description=Watchman for user %i
After=remote-fs.target
Conflicts=shutdown.target

[Service]
ExecStart=/usr/local/bin/watchman --foreground --inetd
ExecStop=pkill -u %i -x watchman
Restart=on-failure
User=%i
Group=users
StandardInput=socket
StandardOutput=syslog
SyslogIdentifier=watchman-%i

[Install]
WantedBy=multi-user.target

上面的服务以下面的socket 单元启动，前提要这个服务实现接收socket,通过sd_listen_fds(3)

# system_service@user.socket

[Unit]
Description=Watchman socket for user %i

[Socket]
ListenStream=/var/facebook/watchman/%i-state/sock
Accept=false
SocketMode=0664
SocketUser=%i
SocketGroup=othergroup

[Install]
WantedBy=sockets.target

普通用户运行服务

注意，普通用户因为只会以自己的身份启动，所以不能想系统服务那样指定'User/Group'

[Unit]
Description=tun2socks for vpn
#Requires=ssh_to_alpha.service

[Service]
Type=simple
ExecStart=/usr/bin/badvpn-tun2socks 

[Install]
WantedBy=default.target

若希望这个用户自定义服务能自启动， WantedBy需要设置成'default.target'

自动创建unit-file

以下命令可以自动在对应目录创建*.service文件

systemctl --user --force --full edit test.service

2021年1月21日
需要 1 分钟阅读时间

rhel系列修改密码

考rhce8 栽在改密码了，现在彻底弄明白

关于selinux

这是rhel和其他发行版的最大区别，也是我忽略的点。启用selinux 时，改密码后，额外要执行touch /.autorelabel，新密码才能生效，而平时我使用centos一直是禁用selinux的。

启用selinux

selinux 默认状态是enforcing, 禁用时为disable, 通过sestate 查看状态。

编译'/etc/selinux/config'

修改selinux配置，从disable 到enforcing

执行两次下面动作

创建这个文件的意义是重新label selinux, 不仅是当修改selinux配置需要做，在重置root密码时也是需要

touch /.autorelabel
reboot

叙说改密

rhel5~8有两种方式重置密码，老版本为给linux启动参数加上'init=/bin/sh', 新版本为加rd.break
老版本适用于centos8（已测）, 而新版本应该不支持rhel5，6（未测），下面是完整步骤

老版本

进入grub界面，按e进入编辑启动参数，到linux 行，按ctrl+e或者end键到末尾，追加'init=/bin/sh'
按ctrl+x继续，系统自动进入内存文件系统的根目录
执行/sbin/load_policy -i来初始化selinux
此时系统处于ro模式，执行mount -oremount,rw / 重新挂载根分区，使系统可写
passwd 设置root密码
如果启用了selinux, 额外要执行touch /.autorelabel
最后执行exit或者 exec /sbin/reboot 或者exec /sbin/init

新版本

进入grub界面，按e进入编辑启动参数，到linux 行，按ctrl+e或者end键到末尾，追加'rd.break'
按ctrl+x继续，系统自动进入root系统，此时真正的文件系统以ro挂载在/sysroot
执行mount -oremount,rw /sysrot 重新挂载
执行chroot /sysroot 进入系统
执行passwd设置root密码
如果启用了selinux, 需要额外创建文件touch /.autorelabel
执行exit 退出，然后执行 umount /sysroot 来确保写入
reboot 来重新进入

通过rescue模式改密码

任何发行版都可以通过光盘引导来改密。如果熟悉archlinux安装的方式，就知道进入live os之后可以挂载原系统的磁盘
然后chroot成为root用户，就能直接执行passwd来修改密码

通过修改镜像改密码

最暴力的方式就是用guestfish工具, 一条命令改密。当然得先获取镜像文件
先切换到root用户，使用guestmount命令挂载分区，-i表示自动挂载

guestmount --add base.raw  -i /tmp/hm

然后chroot到挂载点

chroot /tmp/hm

然后改密

passwd

virt提供了简化版本，一条命令就能改密码

virt-customize -a centos8.qcow2 --root-password password:123456

可见镜像文件有多么不安全

最后记录一下vmware虚拟机镜像转换kvm镜像

由于收到的vmware镜像，又没有装vmware workstation，所以找到转换镜像的方法，也很方便

qemu-img convert  CentOS\ 5.vmdk  base-000001.raw

但问题是不支持转换快照文件

引用

https://docs.openstack.org/image-guide/convert-images.html

2021年1月19日
需要 1 分钟阅读时间

weechat 使用方法

weechat 是一个irc客户端，在终端中运行，不需要gui桌面，非常方便。这里记录配置方法

主要参考链接

安装和运行weechat

安装后，直接在终端运行weechat，就能进入weechat

配置

添加server

irc有很多server, 常用的是freenode。另外有darkscience。添加方法如下，另外weechat里面命令都是以'/' 开头，还能使用tab补全

/server add freenode chat.freenode.net/6697 -ssl

irc 除了有很多服务器url, 每个url 还有多个端口供链接，比如6697

设置昵称

昵称默认是linux系统的用户名，昵称用来在聊天中显示名称

/nick mynickname

**注意：手动修改昵称不是简单的事情，特别是当已经连接serer时。比较方便的办法就是直接改配置文件

# ～/.weechat/irc.conf
nicks = "malloy,malloy1,malloy2"

带后缀的昵称用来当malloy占用时的备用，比如网络重连时昵称有冲突就需要备用昵称

注册昵称

因为有很多聊天室要求注册后才能进入，所以先要使用邮箱注册

/msg nickserv register userpassword example@email

然后irc 会提示查收邮件，在邮件里面提示你在irc输入命令完成注册

加入聊天室

聊天室都是以#开头，例如我使用的 '#archlinuxcn'

/join #weechat

退出聊天室

/parted "leave message"

或者

/close

自动设置

设置打开weechat时，自动登陆和自动进入聊天室

/set irc.server.freenode.autoconnect on
/set irc.server.networkname.autojoin "#channel1,#channel2"

界面设置

先介绍weechat的各名称对应命令 : 聊天室称为buffer, 切换聊天室命令 /buffer n
最左边的聊天列表是bufferlist bar
进入buffer后，最右边的是nicklist bar，一个聊天室界面叫做window，所以下面的命令设置就与 /bar /windows 有关

隐藏和显示bufferlist

/bar hiden bufferlist 
/bar show bufferlist
/bar toggle bufferlist

分屏显示所有聊天室，水平分屏splith,竖直分屏 splitev

/window splitv

窗口切换

/window +1
/window -1

窗口合并

/window merge

安全设置

上面添加服务器时，已经配置了ssl选项，就表示使用通讯加密了，但irc的聊天记录一般是对外公开的
设置weechat开启密码，进入weechat前验密
```
/secure passphrase superSecretPassphrase
```

自动化设置和鉴权

注册好昵称之后，配置自动化登陆，而不需要手动执行命令

设置irc登陆昵称，作为identify的参数，务必要跟register的保持一致

/secure set networkname_nickname password

设置irc登陆密码，作为identify的参数，务必要跟register的密码保持一致

/secure set networkname_password password

设置weechat启动时自动登陆服务器，以及自动加入channel

/set irc.server.libera.autoconnect on
/set irc.server.libera.autojoin "#archlinux-cn,#c,#c++"

以及自动验密

/set irc.server.networkname.command "/msg nickserv identify ${sec.data.networkname_nickname} ${sec.data.network_password}"

其实显而易见地，sec.data.networkname_nickname和sec.data.network_password 都只是保存在sec.data里的变量，其实可以两个变量合成一条也没问题

udp 的端口复用实现负载均衡

前言

偶尔看到 python 3.9 的release note 里面提到一个bug

asyncio¶

出于重要的安全性考量，asyncio.loop.create_datagram_endpoint() 的 reuse_address 形参不再被支持。 这是由 UDP 中的套接字选项 SO_REUSEADDR 的行为导致的。 更多细节请参阅 loop.create_datagram_endpoint() 的文档。 （由 Kyle Stanley, Antoine Pitrou 和 Yury Selivanov 在 bpo-37228 中贡献。。）

意思是tcp的socket option:SO_REUSEADDR不适用于udp：在tcp中这个选项表示立即回收端口，减少 time_wait 的时间。而在udp中，这个选项表示多个socket可以绑定一个端口，由内核来分发请求。

所以看到此功能，自己试了一下，确实如此，顺便回顾一下知识

主要代码

    struct sockaddr_in addr;
    addr.sin_family = AF_INET;
    addr.sin_port = htons(8888);
    inet_pton(AF_INET,"127.0.0.1",(void*)&addr.sin_addr);
    // inet_pton 支持ipv4和ipv6,是比较新的转换函数

    sfd = socket(AF_INET, SOCK_DGRAM, IPPROTO_UDP);
    if(sfd == -1)
    {
        perror("socket");
        exit(1);
    }
    int val = 1;
    if(0 != setsockopt(sfd, SOL_SOCKET, SO_REUSEPORT,&val, sizeof(val))){
        perror("setsockopt");
        exit(1);
    }
    /* sockaddr 和 sockaddr_in 有什么区别？
       struct sockaddr {  
        sa_family_t sin_family;//地址族
　　      char sa_data[14]; //14字节，包含套接字中的目标地址和端口信息               
　　    }; 
　　    struct sockaddr_in {
　　      sa_family_t sin_family;//地址族
　　      uint16_t sin_port;
　　      struct in_addr sin_addr;    // 32 位地址
　　      char    sin_zero[8];    // reserve
　　    };
　　    struct in_addr {
　　      In_addr_t   s_addr;  //32位
　　    };
　　    
　　    sockaddr_in 和 sockaddr 长度相同，都 sin_family + 14 个字节，但是前者显式划分了
　　 */ 
    if(bind(sfd, (struct  sockaddr*) &addr, sizeof(addr)) != 0)
    {
        perror("bind");
        exit(1);
    }

效果

先启动两个服务端，再使用ncat 来模拟请求,

ncat -uv 0.0.0.0 8888

启动ncat时，系统会分配给一个服务端处理。但是重启ncat时，会切换到另一个服务端处理

2021年1月4日
需要 1 分钟阅读时间

阿里云动态设置 dns

如果服务器的公网ip动态变化的情况下，如何访问，甚至如何通过域名访问？

例如公司自己搭建的服务器如何暴露在公网上，如果请求固定ip听说很贵，还可以通过frp实现, 这里介绍2种方案

动态dns

前提是服务器有出口ip, 而不是在路由器下。 * 如果服务器在路由器下，通过设置nat,将外网访问的请求的目的ip转换为局域网'192.168..'，也能实现公网请求局域网的服务器

阿里云（相信大多数云厂商都支持）可以支持动态改变dns的解析地址，即通过api调用就能改变dns的解析，这样当出口ip变化时，立即调用api来修改dns解析

实现原理:

定时检测出口ip, 例如每5分钟执行一次。可以通过crontab和以下命令实现
```
curl https://httpbin.org/ip
```
通过阿里云的api操作dns
如果服务器在内网，添加nat规则，将目的ip转换为内网ip

这里有个现成的项目

frp

frp 就是内网穿透了，没有出口ip的情况下，例如在路由器下且路由器不支持nat的时候，或者是在运营商级NAT的模式下，就可以采取这中方式。但是前提是需要有公网的服务器

实现原理：

通过在公网服务器运行frp 服务端，在没有出口ip的局域网服务器上运行frp客户端
客户端主动去连接服务端，连接上之后，服务端会为客户端创建一个端口，所有的向这个端口的请求都被转发到局域网的服务器，实现公网访问局域网的服务器

wireguard

wireguard的功能更加强大，配对后就相当于互连了，不需要frp那样配置端口服务。而且自带加密，更安全。

zero-trust

研究过一会，发现这个和wireguard非常类似的功能。而且zero-trust有cloudflare提供了公网接入点，所以公网服务器的钱也省了, 再加上zero-trust自带的加密，所以是连cloudflare也不能侵入。这就比国内的NAT服务安全多了。唯一缺点估计是zero-trust的公网接入点都在国外，所以延迟会高些。

总结

如果有出口ip, 即使经常变化，可以使用动态dns的技术实现暴露到公网，成本低廉。否则使用frp,需要额外购买服务器，或者使用花生壳类似的穿透技术，但是有被掏裤裆的风险。有公网服务器就用wireguard，否则用zero-trust。

2021年1月4日
需要 1 分钟阅读时间

前言

元旦过完回公司发现archlinux 系统无法启动了，提示没有找到内核之类的错误。虽然也没有找到根本原因，只知道是内核镜像丢失了，这里记一下解决办法

现象

启动之后，提示缺少内核，需要先指定内核。回车后进入grub 界面。在grub 界面可以执行ls (hd,gpt)/ 来查看分区的文件
hd0、 hd1 代表的硬盘编号， gpt1、 gpt2、 gpt3 代表分区， ls (hd0, gpt1)/ 表示查看第一个硬盘第一个分区的文件

ls (hd1, gpt2)
EFI  grub  initramfs-linux-fallback.img

我的boot分区是第二个硬盘的第二个分区，可见确实没有 vmlinuz-linux 文件，也很奇怪

解决办法

没有 'vmlinuz-linux' 文件的话需要通过archlinux的U盘启动盘启动，挂载分区后，arch-chroot 进入到坏系统

执行重装linux

pacman -S linux

执行grub 相关命令，重建引导配置。我的EFI单独分区了

grub-install --target=x86_64-efi --efi-directory=/boot/EFI --bootloader-id=Arch
grub-config -o /boot/grub/grub.cfg

exit退出坏系统，umount 再重启。一定要umount 分区否则grub不会生效

没有umount 导致的grub不生效

因为没有umount，exit后直接重启，发现依旧无法进入系统，还是进入了grub界面，好在linux内核镜像已经存在了，可以通过grub来配置启动
所以这种情况也适用于系统ok，但引导损坏的情况。

解决办法

我的boot分区是(hd1,gpt2)

执行一下

set prefix=(hd1,gpt2)/grub/  # 指定实际的grub目录
set root=(hd1,gp2)
insmod normal
normal

此时grub会刷新，继续执行

insmod linux
linux /vmlinuz-linux root=/dev/nvme0n1p2   # 设置内核
initrd /initd.img
boot

由于不知道nvme的命名方式，导致也挺麻烦， grub下可以看到uuid,但不能看到分区名称，后来发现可以通过uuid方式指定root

insmod linux
linux /vmlinuz root=UUID=xxxxxxxxxxx
initrd /initd.img
boot

扩充

同样可以通过磁盘+分区的方式指定内核和initrd

2020年11月18日
需要 2 分钟阅读时间

二叉树遍历

二叉树定义

二叉树的父节点最多有2个子节点，如果二叉树的所有父节点没有节点或者有2个节点，那么叫完全二叉树

二叉树的遍历方式

二叉树有4中遍历方式：前序遍历，中序，后序，以及层序

前三种可以对比着看，区别在于父节点先被访问的顺序，这里的先后都是相对于同一个树而言。这里的访问意思是访问其值，例如打印节点的数据：
* 前序遍历，先父节点，再左子节点，最后是右子节点 * 中序遍历，先左子节点，再父节点，最后是右子节点 * 中序遍历，先左子节点，再右子节点，最后父节点

可见，都是先左子节点后右子节点

而层序遍历是从上往下，广度优先

效果

若有以下二叉树，则遍历结果

graph BT
    A[1] --> B[0]
    C[2] --> B
    D[3] --> A
    E[4] --> A
    F[5] --> C
    G[6] --> C
    H[7] --> D
    I[8] --> D
    J[9] --> E

层序: 0 1 2 3 4 5 6 7 8 9

先序: 0 1 3 7 8 4 9 2 5 6
中序: 7 3 8 1 9 4 0 5 2 6
后序: 7 8 3 9 4 1 5 6 2 0

注意下划线，即036组成的一个树，可以证实上面的总结

代码实现

实现前三种遍历都有2种方式，递归和使用stack

节点数据结构

    def Node:
        self.item
        self.lchild
        self.rchild

递归实现

前序遍历

def front_recursion(root: Node):
    if root is None:
        return None
    print(root.item)
    if root.lchild is not None:
        front_recursion(root.lchild)
    if root.rchild is not None:
        front_recursion(root.rchild)

中序遍历

def Middle_recursion(root: Node):
    if root is None:
        return None
    if root.lchild is not None:
        front_recursion(root.lchild)
    print(root.item)
    if root.rchild is not None:
        front_recursion(root.rchild)

后序遍历

def Middle_recursion(root: Node):
    if root is None:
        return None
    if root.lchild is not None:
        front_recursion(root.lchild)
    if root.rchild is not None:
        front_recursion(root.rchild)
    print(root.item)

stack实现

前序遍历

def Front_stack(root: Node):
    if root is None:
        return None

    stack = []
    Node = root
    stack.append(Node)

    while Node or stack:
        while Node:
            # 访问和入栈的顺序顺序是先父节点后左节点
            print(Node.item)
            # 父节点入栈
            stack.append(Node.lchild)
            # 深度优先，找最左节点，下个循环就是先访问父节点后左子节点
            Node = Node.lchild
        # 这里需要好好体会，父节点和左子节点已经访问过，只剩下右节点
        # 所以就是先左后右
        Node = stack.pop()
        Node = Node.rchild

中序遍历

def Middle_stack(root: Node):
    if root is None:
        return None

    stack = []
    Node = root
    stack.append(Node)

    while Node or stack:
        while Node:
            # 父节点入栈
            # 左子节点入栈
            # 但都不访问，因为压栈顺序是先父后左子，到出栈的时候再访问
            stack.append(Node.lchild)
            Node = Node.lchild

        Node = stack.pop()
        # 找到最左子节点了，开始出栈，所以肯定是先出左节点， 然后再出栈之后就是父节点
        print(Node.item)
        # 最后就是右节点， 回到第一个while 继续找右子树的最左节点
        Node = Node.rchild

后序的stack比较复杂

还有一个比较简单的先序stack

def Front_stack(root: Node):
    if root is None:
        return None

    stack = []
    stack.append(root)

    while stack:
        Node = stack.pop()
        print(Node.item)

        # stack 先进后出，所以先压右节点
        if Node.rchild is not None:
            stack.append(Node.rchild)

        if Node.lchild is not None:
            stack.append(Node.lchild)

层序遍历,是广度优先的一种方式，所以使用到queue

def Layer_queue(root: Node):
    if root is None:
        return None

    queue = []
    queue.append(root)
    while queue:
        # 取前面的
        Node = queue.pop(0)
        print(Node.item)
        if Node.lchild is not None:
            queue.append(Node.lchild)

        if Node.rchild is not None:
            queue.append(Node.rchild)

后序栈遍历

后序遍历的顺序是先左子后右子，最后才是父节点

'''
1. 同样先找到最左边的节点，父节点和左子节点入栈
2. 找到最后一个左子节点之后，判断栈顶的节点，出栈顺序是先左子后父节点，所以只需要判断右子节点的情况：
   如果栈顶节点的右子节点为空，直接打印栈顶节点。 如果栈顶节点的右子节点是上一个出栈的节点，那么说明已经访问到了右子节点，可以继续打印父节点  
   如果栈顶的右子节点不为空也不是上一个访问的节点，所以要先去访问右子树， 将右子节点入栈，退出循环，执行第一步
'''
def back_stack(self, root):
    if root is None:
        return None
    stack = []
    Tag = None
    stack.append(root)
    while stack:
        Node = stack[-1]
        while Node.lchild:
            stack.append(Node.lchild)
            Node = Node.lchild

        while stack:
            Node = stack[-1]
            if Tag == Node.rchild or Node.rchild is None:
                Node = stack.pop()
                print(Node.item)
                Tag = Node
            elif Node.rchild is not None:
                stack.append(Node.rchild)
                break

2020年11月18日
需要 2 分钟阅读时间

docker overlay filesystem

overlay 是docker使用的文件系统，具有分层的特点, docker使用的文件系统经过很多变化，而且各发行版可能不同。
执行docker info 查看当前使用的是overlay2

sudo docker info | grep -i storage                                                                                                                                              
 Storage Driver: overlay2

历史

除了 overlay，类似有rootfs， aufs （ubuntu）， devicemapper（centos），不够成熟的btrfs

他们都有2个目的：
1. 提供不含内核的文件系统（rootfs）即容器, 在内核之上。这是docker 最有价值的地方，就是无论在那里运行docker，容器里的环境都是一致的 2. 提供分层

overlay的优势

page caching，可以在多个不同实例之间共享
写时复制，只有执行write操作时，会将lower layer 的文件复制到container层
不同层之间，相同文件使用硬连接，节省inode 和大小

写时复制 copy-up 会导致第一次写时造成延迟，特别是大文件，拷贝起来费时。但第二次就不会延时，而且overlay2 有caching，相比其它文件系统，更减少延时

overlay的问题

实现不够完全，例如没有实现uname
先只读打开一个文件 open（read），再读写打开相同文件open（write），两个fd 会对应2个不同文件，第一个对应的lower的文件，第二个造成写时复制，对应容器里的文件。
规避方法是先执行touch 操作。现实的例子是 yum 需要安装yum-plugin-ovl。但这个只有7.2才支持，之前的话就需要先touch /var/lib/rpm/*

最佳实践

使用ssd
对于写操作比较多的目录，使用映射文件。这样跳过了overlay的复杂操作，直接使用主机的文件系统。

分层介绍

我理解就是将分离的多个目录挂载到一起的技术。例如对docker 容器的文件进行增删改后，再commit，会多一层layer。再当docker 容器启动时，会自动挂载多层layer。组织： overlay对运行的实例通过元数据组织文件，是否是link文件

ls 04ea1faa8074e5862f40eecdba968bd9b7f222cb30e5bf6a0b9a9c48be0940f2/
diff  link  lower  merged  work

手动mount的例子

.
├── A
│   ├── aa
│   └── a.txt
├── B
│   ├── a.txt
│   └── b.txt
├── C
│   └── c.txt
└── worker
    └── work [error opening dir]

overlay 挂载到/tmp/test目录 sudo mount -t overlay overlay -o lowerdir=A:B,upperdir=C,workdir=worker /tmp/test/

查看test目录

/tmp/test/
├── aa
├── a.txt
├── b.txt
└── c.txt

mount  | grep 'overlay'
overlay on /tmp/test type overlay (rw,relatime,lowerdir=A:B,upperdir=C,workdir=worker)

overlay的增删改

当运行docker容器时查看挂载

overlay on /var/lib/docker/overlay2/04ea1faa8074e5862f40eecdba968bd9b7f222cb30e5bf6a0b9a9c48be0940f2/merged type overlay 
(rw,relatime,
    lowerdir=/var/lib/docker/overlay2/l/B74PWZCBMRCWXFH5UL2ZXB5WEU:/var/lib/docker/overlay2/l/WNHICVPVSDNUGSCZW435TPSMOK,
    upperdir=/var/lib/docker/overlay2/04ea1faa8074e5862f40eecdba968bd9b7f222cb30e5bf6a0b9a9c48be0940f2/diff,
    workdir=/var/lib/docker/overlay2/04ea1faa8074e5862f40eecdba968bd9b7f222cb30e5bf6a0b9a9c48be0940f2/work
)

docker 将镜像的文件挂载为只读，将容器层挂载为可读可写。文件系统可以分为2部分 upper（容器层） + lower （镜像层）

当在容器里执行写时，如果文件不存在，会依次遍历lower。如果都不存在就会在upper层创建文件
读也相同
删除时会创建一个without 来隐藏，这是为什么即使删除容器里的文件，镜像还是会增大。
删除目录情况也差不多

似乎很奇怪，为什么多了一个workdir, 据说这个目录总是空的，为了实现原子操作添加和删除文件

特殊情况

在修改容器后，容器系统会多一层，里面包含了修改的文件，以及删除后生成的without文件，然后生成镜像

但对于以下特殊目录文件不会提交，因为这些文件是运行时docker 要根据用户配置进行修改的。

/etc/hostname
/etc/hosts
/etc/resov.conf

例如docker 的link选项，会在容器的hosts 文件里定义对应的容器名->容器ip