一、原理

linux支持多进程间共享打开文件，即同一时刻允许多个进程同时打开同个文件，每个进程之间的读写操作互不影响。为了实现这一个机制，linux内核使用了三种数据结构来表示打开的文件，它们之间的关系决定了在文件共享方面一个进程对另一个进程可能产生的影响。

1.1 内核数据结构

每个进程的进程表中有一个记录项，包含了当前进程所有打开的文件描述符，它包含了一个指向文件表项的指针和文件描述符标志。内核中，为所有打开的文件维持一张表，它包含了以下内容：

• 当前文件打开的状态：以何种方式打开的该文件，只读、只写或是可读可写等。
• 当前文件的偏移量：当前文件指针所处的位置。
• 指向该文件节点表的指针：节点包含了当前文件的属性信息。

每个文件的信息被封装在一个v节点表项中，包含了当前文件的文件名、所有者以及inode等信息。

三者之间的状态关系为：

1.2 多进程共享同一个文件

对于多个进程打开的同一个文件，其状态关系为：

正因为每个文件描述符都有一个属于自己的文件表项，所以每个进程间的文件指针偏移相互独立，互相读写不干扰。但是打开同一个文件的时候v节点指针都指向同一个节点：

• 每次完成write后，文件表项的当前文件指针偏移量也会立马加上写入的字节数。
• 如果打开文件的时候加了O_APPEND参数，每次写入数据前会先把偏移量设置到文件末尾。
• 通过lseek函数只修改当前文件偏移量，不进行任何I/O操作。

有一个要注意的是，每次fork进程后，子进程会复制父进程的文件描述符，两者相互独立。

二、dup和dup2

dup和dup2都可以用来复制一个现有的文件描述符，其用法如下：

#include <unistd.h>

int dup(int fd);
int dup2(int fd1, int fd2);

dup函数直接把复制后的文件描述符返回，返回的一定是当前文件描述符表中的最小数值。

对于dup2，可以通过fd2表示新描述符的值，如果fd2已经打开，系统会先关闭。如果fd1等于fd2，则直接返回不关闭。

复制过后的文件描述符共享一个文件表项，共享后的状态如下：

我们可以通过一个程序来验证这一个结论：

#include <unistd.h>
#include <stdio.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>

int main() {
    char buff[6] = { 0 };
    int fd_1, fd_2;

    fd_1 = open("data.txt", O_RDONLY);
    if (fd_1 == -1) {
        perror("open file error");
        return -1;
    }

    fd_2 = dup(fd_1);
    if (fd_2 == -1) {
        perror("dup error");
        return -1;
    }

    if (read(fd_1, buff, 5) == -1) {
        perror("read error at fd_1");
        return -1;
    }
    printf("fd_1 read: %s\n", buff);

    if (read(fd_2, buff, 5) == -1) {
        perror("read error at fd_2");
    }
    printf("fd_2 read: %s\n", buff);

    close(fd_1);
    close(fd_2);

    return 0;
}

上面的代码中通过fd_1打开文件data.txt，fd_2复制fd_1，两个文件描述符文件从文件中读取5个字节数据并打印出来。

我们编译代码执行：

# 先写十个字节数据到文件
> echo "HelloWorld" > data.txt
> mkdir debug
# 编译
> gcc dup.c -o debug/dup
# 执行
>  ./debug/dup 
fd_1 read: Hello
fd_2 read: World

可以看到，fd_2读取的数据是从第5个字节开始，即从fd_1读完偏移处开始，两者确实共享了同一个文件表项。

nginx访问限频

一、并发访问限制

ngx_http_limit_conn_module是一个默认安装的内置模块，被用来限制在某一个关键字维度上的最大并发数量，通常情况下，这个维度被设置为访问者的IP。在计算的一个连接当前的并发数量时，不是一连接就会被计数，而是当所有请求头都被读完才计数。它的示例配置为：

http {
    limit_conn_zone $binary_remote_addr zone=addr:10m;
    # ...
    server {
        # ...
        location /download/ {
            limit_conn addr 1;
        }
    }
}

以上配置通过limit_conn_zone指令定义了一个名为addr的并发限制器，它以$binary_remote_addr（即访问的IP地址）作为key，分配一块10m的空间来保存所有的连接数量。

而后的对应的server段中，使用这个addr，限制同一时刻最多只能有1个连接。所以整个配置的意思就是：限制单个IP同一时刻最多有3个访问连接。

相关的参考文档：Module ngx_http_limit_conn_module。

1.1 案例一：针对IP的并发数量限制

当前有一个站点d2.maqian.co，希望同一时刻同一IP最多只能3个并发访问：

http {
    limit_conn_zone $binary_remote_addr zone=addr:10m
    server {
        listen       80;
        server_name  d2.maqian.co;
        limit_conn   addr 3;
        limit_rate   1m; # 限制访问速率1M/s
    
        location / {
            root   html;
            index  index.html index.htm;
        }
        
        access_log logs/access.log main;
        error_log logs/error.log;
    }
}

网站的根目录下有个文件master.zip，大小8.8M，在另一台客户端上使用ab命令执行并发测试：

ab -c 5 -n 10 http://d2.maqian.co/master.zip # 同一时刻5个并发连接，一共10个连接

测试过程中Nginx的访问日志：

> cat access.log
192.168.123.101 - - [20/Oct/2018:17:45:19 +0800] GET "d2.maqian.co/master.zip" 503 537 "-" "ApacheBench/2.3" "-"
192.168.123.101 - - [20/Oct/2018:17:45:19 +0800] GET "d2.maqian.co/master.zip" 503 537 "-" "ApacheBench/2.3" "-"
192.168.123.101 - - [20/Oct/2018:17:45:19 +0800] GET "d2.maqian.co/master.zip" 503 537 "-" "ApacheBench/2.3" "-"
192.168.123.101 - - [20/Oct/2018:17:45:19 +0800] GET "d2.maqian.co/master.zip" 503 537 "-" "ApacheBench/2.3" "-"
192.168.123.101 - - [20/Oct/2018:17:45:19 +0800] GET "d2.maqian.co/master.zip" 503 537 "-" "ApacheBench/2.3" "-"
192.168.123.101 - - [20/Oct/2018:17:45:19 +0800] GET "d2.maqian.co/master.zip" 503 537 "-" "ApacheBench/2.3" "-"
192.168.123.101 - - [20/Oct/2018:17:45:19 +0800] GET "d2.maqian.co/master.zip" 503 537 "-" "ApacheBench/2.3" "-"
192.168.123.101 - - [20/Oct/2018:17:45:27 +0800] GET "d2.maqian.co/master.zip" 200 9204205 "-" "ApacheBench/2.3" "-"
192.168.123.101 - - [20/Oct/2018:17:45:27 +0800] GET "d2.maqian.co/master.zip" 200 9204205 "-" "ApacheBench/2.3" "-"
192.168.123.101 - - [20/Oct/2018:17:45:27 +0800] GET "d2.maqian.co/master.zip" 200 9204205 "-" "ApacheBench/2.3" "-"

可以看到，除了3个连接的的返回值为200以外，其他的都返回状态码503。

为什么三个200访问的日志在最后呢？

因为下载的文件内容是8.8M，配置中有限制最大下载速率为1M/s，所以它大概需要9秒才能下载完成，状态码是在连接返回完成才打印出来的，并且可以看到503状态码和200状态码的日志间隔差不多刚好8-9s。

那为什么要限制下载速率呢？

当前在内网环境下，下载速度非常快，8.8M的文件几乎1S内就能下载完成，连接很难并发，即使并发了，10个连接也很有可能有多个成功了。

1.2 针对服务端同一时刻的访问频率限制

和上面同样的环境，我们不限制单个IP的并发访问数量，而希望同一时刻服务器最多处理10个连接：

http {
    limit_conn_zone $server_name zone=web_server:10m;
    server {
        listen       80;
        server_name  d2.maqian.co;
        limit_conn web_server 10;
        limit_conn_log_level info;    
        limit_rate 1m;
    
        location / {
            root   html;
            index  index.html index.htm;
        }
    
        access_log logs/access.log main;
        error_log logs/error.log;
    }
}

执行命令测试：

ab -c 11 -n 15 http://d2.maqian.co/master.zip # 同时产生11个连接，一共访问15次

nginx访问日志：

192.168.123.101 - - [20/Oct/2018:18:23:49 +0800] GET "d2.maqian.co/master.zip" 503 537 "-" "ApacheBench/2.3" "-"
192.168.123.101 - - [20/Oct/2018:18:23:49 +0800] GET "d2.maqian.co/master.zip" 503 537 "-" "ApacheBench/2.3" "-"
192.168.123.101 - - [20/Oct/2018:18:23:49 +0800] GET "d2.maqian.co/master.zip" 503 537 "-" "ApacheBench/2.3" "-"
192.168.123.101 - - [20/Oct/2018:18:23:49 +0800] GET "d2.maqian.co/master.zip" 503 537 "-" "ApacheBench/2.3" "-"
192.168.123.101 - - [20/Oct/2018:18:23:49 +0800] GET "d2.maqian.co/master.zip" 503 537 "-" "ApacheBench/2.3" "-"
192.168.123.101 - - [20/Oct/2018:18:23:58 +0800] GET "d2.maqian.co/master.zip" 200 9204205 "-" "ApacheBench/2.3" "-"
192.168.123.101 - - [20/Oct/2018:18:23:58 +0800] GET "d2.maqian.co/master.zip" 200 9204205 "-" "ApacheBench/2.3" "-"
192.168.123.101 - - [20/Oct/2018:18:23:58 +0800] GET "d2.maqian.co/master.zip" 200 9204205 "-" "ApacheBench/2.3" "-"
192.168.123.101 - - [20/Oct/2018:18:23:58 +0800] GET "d2.maqian.co/master.zip" 200 9204205 "-" "ApacheBench/2.3" "-"
192.168.123.101 - - [20/Oct/2018:18:23:58 +0800] GET "d2.maqian.co/master.zip" 200 9204205 "-" "ApacheBench/2.3" "-"
192.168.123.101 - - [20/Oct/2018:18:23:58 +0800] GET "d2.maqian.co/master.zip" 200 9204205 "-" "ApacheBench/2.3" "-"
192.168.123.101 - - [20/Oct/2018:18:23:58 +0800] GET "d2.maqian.co/master.zip" 200 9204205 "-" "ApacheBench/2.3" "-"
192.168.123.101 - - [20/Oct/2018:18:23:58 +0800] GET "d2.maqian.co/master.zip" 200 9204205 "-" "ApacheBench/2.3" "-"
192.168.123.101 - - [20/Oct/2018:18:23:58 +0800] GET "d2.maqian.co/master.zip" 200 9204205 "-" "ApacheBench/2.3" "-"
192.168.123.101 - - [20/Oct/2018:18:23:58 +0800] GET "d2.maqian.co/master.zip" 200 9204205 "-" "ApacheBench/2.3" "-"

限制了同一时刻服务端只能有10个连接之后，现象也和上面的一样，15个连接有5个返回错误，但是不同的是这些连接可以同时来自于同一个IP。

1.3 多关键字配合使用

上面的基于IP和服务端访问限制可以同时使用，并且不只是这两个字段可以配合使用，其他的变量也都可以同时使用，具体的变量可以参考：Alphabetical index of variables。

例如我们可以同时限制单个IP并发连接数为3，并且同时访问服务端的连接数为100：

http {
    limit_conn_zone $server_name zone=web_server:10m;
    limit_conn_zone $binary_remote_addr zone=addr:10m
    server {
        listen       80;
        server_name  d2.maqian.co;
        limit_conn web_server 100; # 同一时刻最多100个连接访问服务端
        limit_conn addr 3; # 同一时刻同一IP最多3个连接访问
        limit_conn_log_level info;    
        limit_rate 1m;
    
        location / {
            root   html;
            index  index.html index.htm;
        }
    
        access_log logs/access.log main;
        error_log logs/error.log;
    }
}

二、限制访问频率

ngx_http_limit_req_module模块用于限制每个IP访问某个关键字维度的请求速率，其参数用法如下：

limit_req_zone key zone=name:size rate=rate;

以上的配置创建一个速率限制器，限制单个IP在key这个维度上的访问速率。和上面一样，这个key也通常被设置成访问者的IP。使用时在对应的server段内设置：

limit_req zone=name [burst=number] [nodelay];

burst表示令牌数量，连接满了之后，给接下来的连接发放令牌进行等待。令牌数量超出后，可以选择继续等待令牌或者直接返回错误状态。

这里的逻辑可以看成去银行办业务：人多的时候需要等号，number可以堪称最大的等号数量，rate可以堪称银行的窗口个数。银行同一时刻处理rate个客户的请求，并且同时允许number个客户排队，超出后，根据nodelay是否被设置来判断该连接是应该被丢弃还是等待。

参考文档：Module ngx_http_limit_req_module。

2.1 限制每秒只处理同一个用户的一个请求

http {
    # 以请求IP作为KEY，设置访问频率为1秒1次请求
    limit_req_zone $binary_remote_addr zone=addr:10m rate=1r/s;
    server {
        listen       80;
        server_name  d2.maqian.co;
        # 设置队列为5，最多有5个连接等待，超出的不继续等待
        limit_req zone=addr burst=5 nodelay;
        limit_rate 1m;
    
        location / {
            root   html;
            index  index.html index.htm;
        }

        access_log logs/access.log main;
        error_log logs/error.log;
    }
}

为了避免大文件下载耗时，这里不再和上面一样下载大文件，使用小文件测试：

ab -c 6 -n 100 http://d2.maqian.co # 6个并发连接，访问100次

得到日志后，复制到当前目录下，分别分析200和503响应的次数：

> grep "503" access.log | wc -l
94
> grep "200" access.log | wc -l
6

nginx第一秒处理第一个请求，同时给接下来的5个请求排队，剩下的都直接返回503，所以返回200的次数为6，503的次数为94。

ab返回的结果也能看到成功和失败的数量：

参考：extern "C"语句在C++中的作用

一、问题描述

在编译C++程序时，遇到以下问题：

/tmp/cccZeFer.o: In function `main':
main.cpp:(.text+0xf): undefined reference to `****'
collect2: error: ld returned 1 exit status

看到错误的第一直觉是共享库出问题了，因为以前出现这个问题都是因为库没有加进来，但是反复确认过后发现共享库并没有问题。

第一：编译的时候使用-l选项包含了库文件，并且库里面的函数也存在。

第二：库确实存在，不然也不会报上面的错误了，报的错误应该是：

/usr/bin/x86_64-linux-gnu-ld: cannot find -l***
collect2: error: ld returned 1 exit status

试了各种方法都无效，百思不得其解，最后无意间发现竟然是c和c符号表不兼容导致的。

因为库是c编译的，代码是c编译的，c和c的符号表规则不一致，导致编译c时找不到符号，因此编译报错。

二、重现

准备一个库libadd.so和一个源文件main.cpp：

> tree
.
├── libadd
│   ├── add.c
│   ├── add.h
│   └── Makefile
├── main.cpp
└── Makefile

1 directory, 5 files

add.h和add.c的内容：

> cat libadd/add.h
int add(int i, int j);

> cat libadd/add.c
#include "add.h"

> cat libadd/Makefile
app:
    gcc add.c -fPIC -shared -o libadd.so

编译libadd.so能够正常编译，然后编译main：

> cat main.cpp 
#include "libadd/add.h"
#include <iostream>

int main() {
    std::cout << add(1, 2) << std::endl;
    return 0;
}

> cat Makefile 
app:
    g++ main.cpp -Llibadd -ladd

此时编译就报错：

/tmp/cccZeFer.o: In function `main':
main.cpp:(.text+0xf): undefined reference to `add'
collect2: error: ld returned 1 exit status

解决方案

在add.h中使用宏定义把函数声明为c导出的函数：

#ifdef __cplusplus
extern "C" {
#endif

int add(int i, int j);

#ifdef __cplusplus
}
#endif

再编译就能通过了。

作者：LeetCode

链接：112. 路径总和

来源：力扣（LeetCode）

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

一、题目描述

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明：叶子节点是指没有子节点的节点。

示例:

给定如下二叉树，以及目标和sum = 22：

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

返回true, 因为存在目标和为 22 的根节点到叶子节点的路径5->4->11->2。

二、题解

2.1 dfs深搜（递归）

算法：

利用递归深度优先搜索每个节点，每经过一个节点，sum值减去当前节点的值，继续搜索子节点。直到叶子节点的时候判断sum，为0返回true，否则返回false。

代码：

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if (root == NULL) {
            return false;
        }
        sum -= root->val;

        // 搜索到叶子节点了
        if (root->left == NULL && root->right == NULL) {
            return sum == 0;
        }

        // 计算左右子节点
        return hasPathSum(root->left, sum) || hasPathSum(root->right, sum);
    }
};

复杂度分析

• 时间复杂度：我们访问每个节点一次，时间复杂度为O(N)，其中N是节点个数。
• 空间复杂度：最坏情况下，整棵树是非平衡的，例如每个节点都只有一个孩子，递归会调用N次（树的高度），因此栈的空间开销是O(N) 。但在最好情况下，树是完全平衡的，高度只有 log(N)，因此在这种情况下空间复杂度只有O(log(N)) 。

2.2 bfs广搜（迭代）

算法：

我们可以用栈将递归转成迭代的形式,深度优先搜索在除了最坏情况下都比广度优先搜索更快。最坏情况是指满足目标和的 root->leaf 路径是最后被考虑的，这种情况下深度优先搜索和广度优先搜索代价是相通的。

使用迭代的思路是：利用队列，每次保存当前节点以及剩余的sum，如果是叶子节点并且剩余的sum为0则返回true。否则，把节点的左右子节点分别压入队列，更新sum值。

所以我们从包含根节点的栈开始模拟，剩余目标和为 sum - root.val，然后开始迭代。弹出当前元素，如果当前剩余目标和为 0 并且在叶子节点上返回 True；如果剩余和不为零并且还处在非叶子节点上，将当前节点的所有孩子以及对应的剩余和压入栈中。

struct NodeSum {
    TreeNode *node; // 当前节点
    int sum; // 剩余的和
};

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        queue<NodeSum *> q;
        NodeSum* p;

        TreeNode *node;
        int residualSum;

        if (root == NULL) {
            return false;
        }
        q.push(new NodeSum{ root, sum });

        while (q.empty() == false) {
            p = q.front();
            q.pop();

            node = p->node;
            // 计算剩余需要的sum
            residualSum = p->sum - node->val;
            delete p;
            
            // 存在左子节点，压入队列
            if (node->left) {
                q.push(new NodeSum{ node->left, residualSum });
            }
            // 存在右子节点，压入队列
            if (node->right) {
                q.push(new NodeSum{ node->right, residualSum });
            }
            
            // 叶子节点，sum为0
            if (node->left == NULL && node->right == NULL && residualSum == 0) {
                return true;
            }
        }
        return false;
    }
};

复杂度分析：

• 时间复杂度：和递归方法相同是O(N)。
• 空间复杂度：当树不平衡的最坏情况下是O(N) 。在最好情况（树是平衡的）下是 O(log(N))。