binary tree traversal

二叉树遍历

二叉树定义

二叉树的父节点最多有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

节点数据结构

1
2
3
4
def Node:
    self.item
    self.lchild
    self.rchild

递归实现

前序遍历

1
2
3
4
5
6
7
8
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)

中序遍历

1
2
3
4
5
6
7
8
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)

后序遍历

1
2
3
4
5
6
7
8
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实现

前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
'''
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

docker overlay filesystem

overlay 是docker使用的文件系统，具有分层的特点

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

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

历史

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

他们都有2个目的：

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

overlay的优势

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

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

overlay的问题

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

最佳实践

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

分层介绍

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

1
2
ls 04ea1faa8074e5862f40eecdba968bd9b7f222cb30e5bf6a0b9a9c48be0940f2/
diff  link  lower  merged  work

手动mount的例子

  1. 原本目录，文件都分散在不同目录ABC
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    .
    ├── A
    │   ├── aa
    │   └── a.txt
    ├── B
    │   ├── a.txt
    │   └── b.txt
    ├── C
    │   └── c.txt
    └── worker
        └── work [error opening dir]
  2. overlay 挂载到/tmp/test目录 sudo mount -t overlay overlay -o lowerdir=A:B,upperdir=C,workdir=worker /tmp/test/
  3. 查看test目录 
    1
    2
    3
    4
    5
    /tmp/test/
    ├── aa
    ├── a.txt
    ├── b.txt
    └── c.txt
    1
    2
    mount  | grep 'overlay'
    overlay on /tmp/test type overlay (rw,relatime,lowerdir=A:B,upperdir=C,workdir=worker)

overlay的增删改

当运行docker容器时查看挂载

1
2
3
4
5
6
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 要根据用户配置进行修改的。

  1. /etc/hostname
  2. /etc/hosts
  3. /etc/resov.conf

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

python package2

python 安装方式有2种 pip 和 easy_install

easy_install 是随setuptools 附带的安装工具
pip 是后出的替 代setuptools 的工具

支持情况

pip 支持新的sdist标准，包括whl二进制包和源码tar包，支持安装和卸载
easy_install 支持老的 Egg 格式

总结一句话

使用pip 不要使用easy_install

包 Platform tags

linux的包的tags有好几个，向后兼容

1
2
3
manylinux1 支持 x86_64 i686
manylinux2010 支持 x86_64 i686
manylinux2014 支持 x86_64 i686 arm ppc

manylinux2010 取代了 manylinux1, 而且已经EOL, 所以尽早使用manylinux2014

使用pip打包

先生成 requirements.txt, 手动加上自己的包myapp

1
2
3
4
pip list > requirements.txt

# 打包命令
python -m pip wheel --wheel-dir=./local/wheels -r requirements.txt

查看生成的包

1
2
3
4
cd local/wheels
Bootstrap_Flask-1.5.1-py2.py3-none-any.whl  Flask_SQLAlchemy-2.4.4-py2.py3-none-any.whl  Jinja2-2.11.2-py2.py3-none-any.whl                SQLAlchemy-1.3.20-cp38-cp38-manylinux2010_x86_64.whl
click-7.1.2-py2.py3-none-any.whl            Flask_WTF-0.14.3-py2.py3-none-any.whl        MarkupSafe-1.1.1-cp38-cp38-manylinux1_x86_64.whl  Werkzeug-1.0.1-py2.py3-none-any.whl
Flask-1.1.2-py2.py3-none-any.whl            itsdangerous-1.1.0-py2.py3-none-any.whl      myapp-0.1.dev0-py3-none-any.whl                   WTForms-2.3.3-py2.py3-none-any.whl

使用pip 安装

1
python -m pip install --no-index --find-links=./local/wheels -r requirements.txt

对于外部的包，需要本地安装

这个通常是在ci/cd上使用， 先把所有依赖拉到本地，就可以直接从本地的repo里下载依赖，离线安装

首先下载包的依赖，然后进行安装

1
2
3
python -m pip download --destination-directory DIR -r requirements.txt

python -m pip install --no-index --find-links=DIR -r requirements.txt

总结

pip和 whell 作为新的打包和安装方式，比较简单也支持多平台CPU, 推荐

advanced marco in c

介绍

宏定义是在c/c++里特有的方式， 像变量一样， 又像模板编程一样， 但最常见的用法还是做头文件的唯一性保证

在每一个头文件都套用这种格式，就可以避免多次引入头文件而导致的重复定义报错

1
2
3
4
5
6
#ifdef FILE_NAME
#def FILE_NAME

// 代码

#endif FILE_NAME

原理

宏定义与变量、模板的最大区别在与处理的时期， 宏定义在预编译时处理， 而变量和模板函数则是在编译期处理。
查看预编译后的代码可以使用命令gcc -E 或者 cpp， 实际上是前者是调用了后者

1
2
NAME
       cpp - The C Preprocessor

用法

除了#ifdef 的用法，宏定义可以分两种类型，变量型和函数型

变量型

这个最简单，就像使用变量一样，先define 然后再使用

1
2
3
4
5
6
# marco.c
#define BUFFER_SIZE 1024

int main(){
	foo = (char *) malloc (BUFFER_SIZE);
}

执行 gcc -E marco.c 得到

1
foo = (char *) malloc (1024);

多行使用 ‘' 来连接

1
2
3
4
#include <stdio.h>
#define GREETING_STR \
  "hello \
world"
  • 注意, 宏定义的定义不分前后， 也不像变量那样先定义再使用， 宏定义可以先使用后定义

以下两种方式的效果相同

1
2
3
4
5
6
7
8
define GREETING_NAME "wayou"

define GREETING "hello," GREETING_NAME

int main() {
printf(GREETING);
return 0;
}
1
2
3
4
5
6
7
8
9
10
+define GREETING "hello," GREETING_NAME

define GREETING_NAME "wayou"

-define GREETING "hello," GREETING_NAME

int main() {
printf(GREETING);
return 0;
}

函数型

函数类型的宏，可以像正常函数一样指定入参，入参需为逗号分隔合法的 C 字面量。
宏的参数必须要用括号包起来，否则当参数为表达式时，会出错

1
2
3
4
#define min(X, Y)  ((X) < (Y) ? (X) : (Y))
  x = min(a, b);          →  x = ((a) < (b) ? (a) : (b));
  y = min(1, 2);          →  y = ((1) < (2) ? (1) : (2));
  z = min(a + 28, *p);    →  z = ((a + 28) < (*p) ? (a + 28) : (*p));

宏定义字符串化

当宏定义的参数被引号包起来时， 不会进行替换，如下

1
2
#define foo(x) x, "x"
foo(bar)        → bar, "x"

加入需要将参数替换到字符串里， 可以使用’#’ 

1
2
3
4
5
6
7
#define WARN_IF(EXP) \
do { if (EXP) \
        fprintf (stderr, "Warning: " #EXP "\n"); } \
while (0)
WARN_IF (x == 0);
     → do { if (x == 0)
           fprintf (stderr, "Warning: " "x == 0" "\n"); } while (0);

而当 这里的x 也是宏定义时， 只有if里的x会替换， 字符串里的x则不会替换 

1
2
#define X ( 1 - 1 )
WARN_IF ( X == 0);

会被替换为 

1
2
3
do { if (( 1 - 1 ) == 0) fprintf (
stderr
, "Warning: " "X == 0" "\n"); } while (0);

拼接

通过 ## 可将两个宏展开成一个，即将两者进行了拼接，宏拼接一般用在需要拼接的宏是来自宏参数的情况，
其他情况，大可直接将两个宏写在一起即可

当有以下情况时非常有用

1
2
3
4
5
6
7
8
9
10
11
12
struct command
{
  char *name;
  void (*function) (void);
};

struct command commands[] =
{
{ "quit", quit_command },
{ "help", help_command },
…
};

可以使用如下：

1
2
3
4
5
6
7
8
#define COMMAND(NAME)  { #NAME, NAME ## _command }

struct command commands[] =
{
COMMAND (quit),
COMMAND (help),
…
};

不定参数和混合参数

宏定义也可以使用不定参数

1
#define eprintf(args…) fprintf (stderr, args)

也可以使用混合参数

1
#define eprintf(format, args...) fprintf (stderr, format, args)

这个可以常在格式化打印时用到， 例如 spdlog 库 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#define SPDLOG_LOGGER_CALL(logger, level, ...)                                                                                             \
    if (logger->should_log(level))                                                                                                         \
    logger->log(spdlog::source_loc{SPDLOG_FILE_BASENAME(__FILE__), __LINE__, SPDLOG_FUNCTION}, level, __VA_ARGS__)

#if SPDLOG_ACTIVE_LEVEL <= SPDLOG_LEVEL_TRACE
#define SPDLOG_LOGGER_TRACE(logger, ...) SPDLOG_LOGGER_CALL(logger, spdlog::level::trace, __VA_ARGS__)
#define SPDLOG_TRACE(...) SPDLOG_LOGGER_TRACE(spdlog::default_logger_raw(), __VA_ARGS__)
#else
#define SPDLOG_LOGGER_TRACE(logger, ...) (void)0
#define SPDLOG_TRACE(...) (void)0
#endif

#if SPDLOG_ACTIVE_LEVEL <= SPDLOG_LEVEL_DEBUG
#define SPDLOG_LOGGER_DEBUG(logger, ...) SPDLOG_LOGGER_CALL(logger, spdlog::level::debug, __VA_ARGS__)
#define SPDLOG_DEBUG(...) SPDLOG_LOGGER_DEBUG(spdlog::default_logger_raw(), __VA_ARGS__)
#else
#define SPDLOG_LOGGER_DEBUG(logger, ...) (void)0
#define SPDLOG_DEBUG(...) (void)0
#endif

重复和覆盖

这些是相似的：

1
2
3
#define FOUR (2 + 2)
#define FOUR         (2    +    2)
#define FOUR (2 /* two */ + 2)

以下都是不同的宏

1
2
3
4
#define FOUR (2 + 2)
#define FOUR ( 2+2 ) // 空白位置不一样 
#define FOUR (2 * 2) // 宏的内容不一样
#define FOUR(score,and,seven,years,ago) (2 + 2) // 入参不一样

对于使用了 #undef 注销过的宏，再次定义同名的宏时，要求新定义的宏不与老的相似。

而如果说一个已经存在的宏，并没有注销，重复定义时，如果相似，则新的定义会忽略，如果不相似，编译器会报警告同时使用新定义的宏。这允许在多个文件中定义同一个宏。

最后

可以查看更多内置宏定义

python package

python 包的管理

python 有 sdist 和 wheel 两种方式管理包：

sdist 是在 python setup.py sdist时产生的包，是一个源码压缩包，在安装时需要编译，所以环境依赖make和gcc
wheel 是在python setup.py bdist_wheel是产生的whl 格式包

从命令都可以看出来sdist即source源码包， bdist 即binary二进制包

sdist 由distutils、setuptools 定义和依赖的编译系统， 可以运行任意的代码
wheel 包为编译和安装时提供了简单的接口，里面包含了二进制的包，可以让安装者不需要知道编译体系,依赖wheel

1
pip install wheel

两种包的打包命令

前提是环境安装了setuptools和wheel, 且编写了setup.py文件如 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# setup.py

from setuptools import setup,find_namespace_packages
#import pathlib
#import pkg_resources
#import os
#import sys

#sys.path.insert(0, os.path.join(
#    os.path.dirname(os.path.abspath(__file__)), 'src'))

# 解析文本文件
#with pathlib.Path('requirements.txt').open() as requirements_txt:
#    install_requires = [str(requirement) for requirement in pkg_resources.parse_requirements(requirements_txt) ]

setup(name='myflask',
      version='1.3',
      install_requires=[
            'Bootstrap-Flask==1.4',
            'Flask==1.1.2',
            'Flask-Login==0.5.0',
            'SQLAlchemy==1.3.18',
            'Werkzeug==1.0.1',
            'WTForms==2.3.1'
          ],
      entry_points={
             'console_scripts':[
                   'myflask=wsgi:main'
                   ]
            },
      package_data = {
        '': ['*.html'],
        '': ['*.css'],
        '': ['*.js'],
        '': ['static/*'],
        '': ['templates/*'],
      },
      py_modules=['myflask'],
      packages=find_namespace_packages(),
      zip_safe=False,
      include_package_data=True,
      )

我这里定义了安装模块，myflask,可以被uwsgi 文件引入，方便管理， 同时也加入了很多html的静态文件， 是一个完整的网站

  1. 生成sdist包， 在项目目录执行python setup.py sdist，可以在sdit目录看到tar包

    1
    2
    # myflask > ls dist                                                                                                                                                                                                      
    myflask-1.3.tar.gz

  2. 生成wheel包，在项目目录执行python setup.py bdist_wheel，可以在sdit目录看到whl包

    1
    2
    # myflask > ls dist
    myflask-1.3-py3-none-any.whl  myflask-1.3.tar.gz

安装

安装命令相同，pip install myflask-1.3.tar.gz pip instal myflask-1.3-py3-none-any.whl。但过程不同

举例安装yarl 的源码包, 源码包需要编译，如果环境没有gcc,就会安装失败

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Collecting yarl<2.0,>=1.0 (from aiohttp==3.6.2)
  Downloading yarl-1.6.2.tar.gz (177kB)
  Installing build dependencies: started
  Installing build dependencies: finished with status 'done'
  Getting requirements to build wheel: started
  Getting requirements to build wheel: finished with status 'done'
    Preparing wheel metadata: started
    Preparing wheel metadata: finished with status 'done'
...

  gcc -pthread -Wno-unused-result -Wsign-compare -DNDEBUG -g -fwrapv -O3 -Wall -fPIC -I/opt/ha/include/python3.8 -c yarl/_quoting_c.c -o build/temp.linux-x86_64-3.8/yarl/_quoting_c.o
  error: command 'gcc' failed with exit status 1
  ----------------------------------------
  ERROR: Failed building wheel for yarl
  Running setup.py clean for yarl
Failed to build yarl

此时，如果使用wheel包就不会出问题，但如果wheel包里面依赖了二进制文件，则需要区分cpu架构和系统了
我的myflask不依赖任何二进制文件，所以是none, 所有cpu和系统都可以安装 

1
myflask-1.3-py3-none-any.whl

对于yarl不同， 在pypi.org 下载时，需要选择正确的包。或者选择源码包yarl-1.6.2.tar.gz来安装编译

当然如果让pip选择在线安装就不需要考虑， 他会自动帮你寻找对应你系统的版本

1
2
3
4
5
6
7
8
9
10
11
12
Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Files for yarl, version 1.6.2
Filename, size 	File type 	Python version 	Upload date 	Hashes
yarl-1.6.2-cp36-cp36m-macosx_10_14_x86_64.whl (128.3 kB) 	Wheel 	cp36 	Oct 13, 2020 	View
yarl-1.6.2-cp36-cp36m-manylinux1_i686.whl (293.5 kB) 	Wheel 	cp36 	Oct 13, 2020 	View
yarl-1.6.2-cp36-cp36m-manylinux2014_aarch64.whl (294.5 kB) 	Wheel 	cp36 	Oct 13, 2020 	View

...

yarl-1.6.2.tar.gz (177.5 kB) 	Source 	None 	Oct 13, 2020 	View

system calls method

前言

之前学汇编发现教材和实际的有出入， 书上写的int, 但是汇编不通过，而gcc 反汇编的结果是调用syscall。
原来这是两种方式调用方式即： int 0x80 和 syscall

除此之外还有一个名词是vdso, 很多elf文件会链接这个vdso库

1
2
3
4
ldd a.out                                                                                                                                                                                                                   √ 19:03:30 
	linux-vdso.so.1 (0x00007fffb3de0000)
	libc.so.6 => /usr/lib/libc.so.6 (0x00007f5b48d4a000)
	/lib64/ld-linux-x86-64.so.2 => /usr/lib64/ld-linux-x86-64.so.2 (0x00007f5b48f36000)

词汇说明

int 0x80 即80中断， 是最老的系统函数调用方式
syscall/sysret 是amd64 制定的标准， 也是目前的x86 64位的标准，即amd64
sysenter/syssysexit 是inter制定的x86 64位标准， 目前已被放弃
vdso 是linux内核虚拟出的so, 实现了int 80 和 syscall，调用方式为 vsyscall

系统函数调用路径

系统调用多被封装成库函数提供给应用程序调用，应用程序调用库函数后，由 glibc 库负责进入内核调用系统调用函数。
即用户函数-> glibc -> 系统调用

int 0x80

int 即是interrupt 中断， 0x80是IDT上注册的中断向量， 每个编号对应一个处理函数handle， linux的0x80的handle即是内核，即系统调用。
所以不同的系统设置的0x80的handle可能不同

调用方式：首先是将参数复制到寄存器， 参数包括系统调用编号和传入参数，然后执行 init 0x80
例如，以下的进程退出的系统调用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
.data
    s:
        .ascii "hello world\n"
        len = . - s
.text
    .global _start
    _start:

        movl $4, %eax   /* write system call number */
        movl $1, %ebx   /* stdout */
        movl $s, %ecx   /* the data to print */
        movl $len, %edx /* length of the buffer */
        int $0x80

        movl $1, %eax   /* 退出的系统调用编号 */
        movl $0, %ebx   /* exit status */
        int $0x80

vdos

vdos即 linux-vdso.so.1， 几乎很多elf 都会链接这个库，但其实他并不是真实存在的so文件，
而是由内核虚拟的文件，再映射到用户的进程来调用。

vdos 是对以下几个函数的实现，称作快速调用

1
2
3
4
#define __NR_gettimeofday 96 //0x60
#define __NR_time 201 //0xc9
#define __NR_clock_gettime 228 //0xE4
#define __NR_getcpu 309 //0x135

对比

所以以上总结其实就3种方式， int ，syscall/sysret ， vdso

int 0x80 方式很慢，所以出现了syscall 即快速调用

执行区别

1
2
3
在 x86 保护模式中，处理 INT 中断指令时，CPU 首先从中断描述表 IDT 取出对应的门描述符，判断门描述符的种类，然后检查门描述符的级别 DPL 和 INT 指令调用者的级别 CPL，当 CPL<=DPL 也就是说 INT 调用者级别高于描述符指定级别时，才能成功调用，最后再根据描述符的内容，进行压栈、跳转、权限级别提升。内核代码执行完毕之后，调用 IRET 指令返回，IRET 指令恢复用户栈，并跳转会低级别的代码。

其实，在发生系统调用，由 Ring3 进入 Ring0 的这个过程浪费了不少的 CPU 周期，例如，系统调用必然需要由 Ring3 进入 Ring0（由内核调用 INT 指令的方式除外，这多半属于 Hacker 的内核模块所为），权限提升之前和之后的级别是固定的，CPL 肯定是 3，而 INT 80 的 DPL 肯定也是 3，这样 CPU 检查门描述符的 DPL 和调用者的 CPL 就是完全没必要。正是由于如此，Intel x86 CPU 从 PII 300（Family 6，Model 3，Stepping 3）之后，开始支持新的系统调用指令 sysenter/sysexit。sysenter 指令用于由 Ring3 进入 Ring0，SYSEXIT 指令用于由 Ring0 返回 Ring3。由于没有特权级别检查的处理，也没有压栈的操作，所以执行速度比 INT n/IRET 快了不少。

返回的区别

1
在 Intel 的手册中，还提到了 sysenter/sysexit 和 int n/iret 指令的一个区别，那就是 sysenter/sysexit 指令并不成对，sysenter 指令并不会把 SYSEXIT 所需的返回地址压栈，sysexit 返回的地址并不一定是 sysenter 指令的下一个指令地址。调用 sysenter/sysexit 指令地址的跳转是通过设置一组特殊寄存器实现的。

vdos的局限（syscall）

1
而"快速系统调用指令"比起中断方式的系统调用方式，还存在一定局限，例如无法在一个系统调用处理过程中再通过"快速系统调用指令"调用别的系统调用。因此，并不一定每个系统调用都需要通过"快速系统调用指令"来实现。比如，对于复杂的系统调用例如 fork，两种系统调用方式的时间差和系统调用本身运行消耗的时间来比，可以忽略不计，此处采取"快速系统调用指令"方式没有什么必要。而真正应该使用"快速系统调用指令"方式的，是那些本身运行时间很短，对时间精确性要求高的系统调用，例如 getuid、gettimeofday 等等。

最后总结

int 是最老的方式，目前用amd64的 syscall 方式， 而vdso是基于syscall实现的快速调用。
只有在调用clock_gettime、gettimeofday、getcpu、time这些系统调用时，才会使用vdso，其他系统调用是通过syscall实现的

huawei unlock bootloader

目的

解锁华为平板M3的BL锁，以及获取root权限

背景

我有一个华为平板M3，WIFI版, 型号BTV-W09，系统是emui5， 买来没什么用，最大的功能就是看视频。 偶尔发现一个app，LinuxDeploy, 可以在安卓上安装完整的Linux系统，而不是内置的阉割版， 前提是获得root权限。

步骤

全部步骤分4个：

  1. 解BL
  2. 刷入recovery 也就是RTWP
  3. 将root压缩包复制到平板，在RTWP下安装
  4. 安装supersu 的apk
  5. 可选刷入xposed框架，并安装xposed manager，步骤参考3,4

解锁

因为华为官方停止申请解锁BL的服务， 所以需要上淘宝找人帮你搞定。 解锁BL之后， 在关机状态按住电源和音量减，进入fastboot模式时，有红字提示unlocked

刷入rec

找到与设备型号对应的rec非常重要，因为型号不对会刷不进去，我尝试了很多个版本，最终在华为论坛找到了。
有了rec后， 让手机处于fastboot状态， 连接手机到电脑，使用 fastboot flash recovery rec 来刷入 ，提书刷入成功之后，可能自动重启，如果没有重启，长按电源键强制关机。
关机状态下， 按住电源键和音量+，进入recovery ， 能看到RTWP的界面说明输入成功，如果没有看到RTWP,而是进入华为官方的eRecovery 表示失败，又可能是被华为覆盖了。
一旦能进入RTWP, 那么RTWP会自动安装，以后就不用担心被覆盖的问题。

刷入root工具

将root.zip 拷贝到平板的储存卡目录，进入RTWP，点INSTALL, 然后选择root.zip 就会开始安装了， 安装后再安装supersu 的应用

这样就root成功了， 所以步骤很简单，找到对应机型的rec 很关键。

刷入xposed

xposed 很强大，但是xposed只是个框架，需要安装包来实现对app的hack。但是我安装完，没发现什么很强大包，感觉也没什么用。

更新

平板一直都在吃灰，最近发现访问网站都报证书错误，可能是系统旧了(后面发现是电池馈电太久，时间不同步)，所以决定升级系统。这次完整贴出命令，因为发现我之前写的难以参考。在XDA网站发现有新的lineage17适合btv-w09,于是按照帖子里面的方法做：

  1. 下载TWRP 3.3.1-1，lineage 17 系统压缩包， boot 镜像，我的是wifi-only版本。
  2. 在平板关闭状态下，按住电源+音量减，振动的时候释放电源键，然后就进入fastboot状态，显示phone unlock
  3. 刷入twrp fastboot flash recovery twrp-xxx.img
  4. 刷入boot fastboot flash boot boot-xxx.img
  5. 进入twrp，这里有点迷惑，网上说（包括我之前说的）按住电源+音量加总是无法进入twrp而是进入了华为的eRecovery,使用adb boot-recovery则进入了正常系统。最后发现在开发者模式下开启高级重启功能，重启的时候选择重启到recovery则能正常进入Twrp界面。可能是平板接着USB线。
  6. 帖子上说了，升级lineage需要Wipe，彻底初始化但保留系统，执行后连sdcard目录也会格式化，剩几个标准目录。
  7. 用adb push 将系统安装压缩包发送到平板的存储空间，adb push Lineage-xxx.zip /sdcard，然后在TWRP中选择 Install，选择这个zip 进行安装。 不过发现这个zip文件校验失败，不管他了。

然后就重启进入新版本的Lineage 17(android 10)，可惜的是没有相机功能。

Install KVM on Debian of aarch64 architecture

背景

公司有台arm64位的设备，安装的银河麒麟系统，经验证就是debian 9。
现在需要运行更多arm64虚拟机。

安装步骤

配置免密sudoer

这里记一个坑， 第一次配置时拼写错误，导致sudo 命令执行失败。需要重置密码，所以很麻烦。
然后推荐使用 sudo visudo 命令来修改sudoer配置文件，这个命令在编辑结束后校验配置文件，避免出现编辑错误导致无法使用sudo的情况。 

1
2
kylin@Kylin:~$ cat /etc/sudoers.d/kylin 
kylin	ALL=(ALL:ALL) NOPASSWD:ALL

配置软件源

第一个是本地iso, 下面的是中科大的镜像源。 每个都设置了trust免校验gpg

1
2
3
4
5
deb [trusted=yes] file:///mnt/iso/ juniper main multiverse restricted universe
deb [trusted=yes] http://ftp.cn.debian.org/debian/ stretch main contrib non-free
deb [trusted=yes] http://ftp.cn.debian.org/debian/ stretch-updates main contrib non-free
deb [trusted=yes] http://mirrors.ustc.edu.cn/debian-security/ stretch/updates main contrib non-free
deb [trusted=yes] http://ftp.cn.debian.org/debian/ stretch-backports main contrib non-free

安装虚拟工具

安装 qemu, libvirt, virt-manager

1
sudo apt install  qemu  libvirt virt-manager

libvirt 没有网络

执行virsh net-list -all 发现default 网络处于未激活状态， 于是执行 systemctl status libvirtd 发现

1
2
3
10月 30 15:46:27 Kylin libvirtd[16741]: 2020-10-30 07:46:27.262+0000: 16764: error : virFileReadAll:1420 : 打开文件 '/sys/class/net/virbr0-nic/operstate' 失败: 没有那个文件或目录
10月 30 15:46:27 Kylin libvirtd[16741]: 2020-10-30 07:46:27.262+0000: 16764: error : virNetDevGetLinkInfo:2530 : unable to read: /sys/class/net/virbr0-nic/operstate: 没有那个文件或目录
10月 30 15:46:54 Kylin libvirtd[16741]: 2020-10-30 07:46:54.710+0000: 16745: error : virFirewallApply:916 : 内部错误：Failed to initialize a valid firewall backend

需要安装以下组件，然后重启libvirtd，这是因为libvirt的网络依赖这几个组件来创建nat 网络

1
2
sudo apt install ebtables iptables dnsmasq
systemctl restart libvirtd

virt-manager 提示aarch64 安装 uefi 错误

直接安装 qemu-efi

1
apt install qemu-efi

virt-manager 允许非root用户访问

因为当以普通用户运行 virt-manager 时，qemu的连接指向非qemu:///system， 这时看到的虚拟机和root看到的不一样，所以必须使用sudo运行。
通过修改配置来启用普通用户也访问qemu:///system， 将uri_defualt 的注释去掉。

1
2
3
4
5
6
7
vim /etc/libvirt/libvirt.conf 

#
# These can be used in cases when no URI is supplied by the application
# (@uri_default also prevents probing of the hypervisor driver).
#
uri_default = "qemu:///system"

这样就可以使用virt-manager来创建虚拟机了，跟x86的使用一样。

顺便记一下vnc的配置， 因为机器在机房里， 通过tigervnc来使用桌面。
另外提示一下，virt-manager 配置好后，可以直接连接远程的virt-manager,非常方便。

使用tigervnc 连接需要在远程主机安装 tigervnc-server 和 tigervnc-password。
使用普通用户执行 tigervnc-password 设置访问密码，然后直接执行tigervnc-server。

这时候vnc只接受本地连接， 如果远程访问，要使用ssh 本地转发来实现。 这也是vnc推荐的方式。

现在本地允许本地转发命令， 监听本地端口 9302, 转发到远程的 9300

1
ssh -L 9302:localhost:9300   -N -f  ssh-kylin

然后执行 vncviewer 127.0.0.1:9302 ，输入密码就能打开远程桌面了。

lvm 的使用

LVM 功能介绍

LVM 是在硬件和系统之间多加了一层，可以很方便地修改分区和扩容。 从效率上看肯定有所损失的，但是对于企业而言，灵活性也很重要
LVM具有在线扩容和快照的重要功能

在线扩容

当磁盘容量不够或者需要替换磁盘时，就需要扩容, 如果是替换磁盘就再需要换出旧硬盘

扩容步骤

使用lvm中的pvmove 命令假如原来是使用pv 为/dev/sda1, 新的硬盘为/dev/sdb1

  1. 新建pv: #pvcreate /dev/sdb1
  2. 扩容vg：#vgextend vg1 /dev/sdb1
  3. 如果要调整分区大小，使用lvresize -r -S 新大小。 不带-r的话需要重新mount才能生效， -S 是表示最终大小，-s +/- 是调整大小

换出步骤

vgreduce 是将pv踢出vg, pvremove是删除pv标记

  1. 把sda1 上数据迁移到sdb1上： #pvmove /dev/sda1 /dev/sdb1
  2. vgreduce 从vg1踢出sda1盘 #vgreduce vg1 /dev/sda1
  3. pvremove 删除磁盘分区的pv 标记 #pvremove /dev/sda1

磁盘换出是否需要停业务

LVM的在线扩容是不需要停止业务的，但是应该在业务闲的时候做。LVM在做pvmove的时候，会冻结旧分区，新的操作就需要做备份。
pvmove有时候很慢，但是不能中断，否则出现很多遗留的分区。

与pvmove类似的功能的还有磁盘镜像， 磁盘镜像的好处很明显，即使复制失败了，原数据依然存在。

但两个技术都要求能够“原子化”，所以不得不对业务有所影响，而且影响的是磁盘IO， 无法通过降低业务的NICE值来减弱这种影响

LVM 快照功能

当系统是安装在LVM文件系统之上，那么当需要进行高危操作的时候，可以先对分区进行快照备份，避免操作失败又无法恢复。
公司有一台centos7的自用系统， 需要升级到Centos8 以支持 Docker buildx。
虽然因操作到无法运行yum,dnf 时宣布失败，但好在有snapshot备份， 恢复后完好如初，太好用。

步骤

  1. 挂载如下
1
2
3
4
5
6
7
8
9
$ lsblk 
NAME                  MAJ:MIN RM   SIZE RO TYPE  MOUNTPOINT
sda                     8:0    0   477G  0 disk  
├─sda1                  8:1    0   200M  0 part  /boot/efi
├─sda2                  8:2    0     1G  0 part  /boot
└─sda3                  8:3    0 475.8G  0 part  
  ├─centos-root       253:2    0    50G  0 lvm   /
  ├─centos-swap       253:4    0  15.7G  0 lvm   [SWAP]
  ├─centos-docker     253:18   0   150G  0 lvm   /var/lib/docker

根分区为50G, 而卷组还剩余160G,完全足够生成一个镜像，50G并未完全使用。

1
2
3
4
$ sudo vgs
  VG     #PV #LV #SN Attr   VSize   VFree   
  centos   1   4   0 wz--n- 475.74g  160.05g
  data     1  13   0 wz--n-  <7.28t <721.91g

  1. 先对根分区进行快照，注意是根分区

    1
    2
    3
    # lvcreate -s -n <snapshot_name> -L <size> <logical_volume>

    $ lvcreate -s -n backup -L 50G  /dev/centos/root

    这里指定了快照的大小为50G, 理论上是要比源分区大， 这里也可以直接设置100G, 系统会自动调整大小到合适。

  2. 进行一顿操作后， 进行恢复, 提示根分区正在使用， 重启后生效。

1
2
3
$ lvconvert --mergesnapshot /dev/centos/backup 
  Delaying merge since origin is open.
  Merging of snapshot centos/backup will occur on next activation of centos/root.

保存

如果需要对快照进行备份到其他位置， 可以直接将快照分区挂载，然后通过tarball 来压缩。

1
tar -cvzf backup.tar.gz /mnt/lv_snapshot

还可以直接通过rsync 将挂载的snapshort 传输到其他服务器上

1
rsync -aPh /mnt/lv_snapshot  <remote_user>@<destination_server>:<remote_destination>

快照回滚

lvm的snapshort 也是写时复制的（copy on write），所以创建快照操作非常快，
当分区进行删除和修改操作的时候， lvm文件系统会拷贝文件到其他地方保存。

问题

lvm快照不等于备份， 仅有快照是不能恢复的

Linux Interrupts

Linux 中断请求

中断请求的英文是IRQ（Interrupt Request）,是用来驱动CPU正常工作的重要机制。 中断根据源头分类成：
由外设发出的硬件中断，软件发出的软中断，以及异常组成。

以前，每个外设都连接一根线到PIC(programmable Interrupt circuit)芯片，有PIC芯片来发生数据到CPU,并将CPU的INTR引脚置位。
现在，CPU集成了PIC成为APIC(Advanced PIC)。

中断分类

中断分为3类型

硬件中断

鼠标和键盘，还有IO设备都会发出硬件中断，例如网卡的数据到了，就会出发中断请求（IRQ），
这个请求会触发CPU去执行ISR, 而这个ISR需要在系统启动的时候注册的。一个Vector表。

软件中断

当播放电影的时候，声音和画面的同步非常重要，这是由系统的定时器jiffies来不停地调度声音播放器来准确播放对应的声音。
软中断在实时操作系统的作用也非常重要。

异常中断

异常中断又分为3类： 缺页异常(Faults)，陷入异常(Traps)，异常退出(Aborts)

例如当程序的内存被swap到硬盘了或者一段动态链接库还没有载入到内存里来，在程序走到这个位置之前，
程序就会提前发出缺页异常，当系统检查了权限和地址有效后（地址有效表示在逻辑地址范围内），
CPU开始为程序执行加载需要的数据，并清除这个异常。 所以这个异常是可以修正的，这个请求必须提前发出。

当GDB调试的时，设置断点会插入一条特殊的指令到程序里，当执行到断点位置就会出发Traps请求，软件的主导权由CPU交给GDB。

当程序触发一个异常例如0/0时，会出发退出异常，由cpu来清理堆栈。

请求的可阻塞性

对于硬件中断请求，CPU的决策是立即执行，对于软中断和异常，CPU采用尽量延后的策略。

查看系统的中断

在中断执行 watch -n1 "cat /proc/interrupts"可以定时更新中断的次数

列的含义从左至右以此为：

1
IRQ vector, interrupt count per CPU (0 .. n), the hardware source, the hardware source's channel information, and the name of the device that caused the IRQ.