跳转至

随笔

这里放着一些未归类的文章。

算法题必备 - Python

输入输出

如果只有若干个元素,可以使用input()方法来获取输入的一行。

如果同质化的元素一行一行的输入并且用空格隔开,可能迭代stdin+split是更简单的方法。

import sys
for line in sys.stdin:
    a = line.split()

输出用print,如果复杂一点用format string。

排序

Python的list.sort是稳定排序,可以通过参数key来将list中的每个元素映射之后再比较。例如:

>>> l = ['a', 'B', 'c']
>>> l.sort()
>>> l
['B', 'a', 'c']
>>> l.sort(key=str.lower)
>>> l
['a', 'B', 'c']

最小堆

Python并没有一个叫堆堆容器。heapq是标准库自带的最小堆算法。他使用的容器就是Python list,heap[0]是最小元素。

和C++类似,我们可以通过重载运算符的方式,把最小堆变成最大堆。修改__lt__方法。

class Item:
    def __init__(self, value):
        self.value = value

    def __lt__(self, other):
        # 反转比较逻辑:原数的“小”对应取反后的“大”
        return self.value > other.value

# 使用自定义对象的最大堆
heap = []
heapq.heappush(heap, Item(5))
heapq.heappush(heap, Item(8))
print(heapq.heappop(heap).value)  # 输出 8(最大元素)

eval

eval可以直接执行字符串,可能会有意想不到的帮助。

数组

创建一个一维数组:

>>> [0] * n
[0, 0, 0]
>>> [0 for _ in range(n)]
[0, 0, 0]

创建一个二维数组:

>>> [[0 for _ in range(n)] for _ in range(m)]
[[0, 0, 0], [0, 0, 0]]

但是用[[0]*n]*m是不对的。对list采用乘法是浅拷贝列表的每个元素n次。所以如果list的元素是可变的,这样做可能会不符合你的本意。

tokio异步程序开发笔记

最近在使用Rust+Tokio开发一个流式任务(后文用pipeline指代)调度框架。踩了很多坑,这里记录一些心得。

安全退出

退出一个Shell程序,最最自然的想法是使用Ctrl+C,向程序发送一个SIGINT信号,默认处理就是退出程序。

然而,直接退出可能并不符合你的预期——如果任务执行了一半就退出了,会变成什么样子?

所以我们应该自定义对SIGINT的处理逻辑,这属于系统编程的范畴。还好,tokio库帮我们做了封装,我们可以在程序开始的时候开一个任务去等待SIGINT信号,然后进行处理

tokio::spawn(async move {
    tokio::signal::ctrl_c().await.unwrap();
    tracing::info!("Ctrl+C received, canceling...");
    // 退出逻辑,如果等待程序自然运行完成可以为空。
});

对于我的程序来说,每一个pipeline都会不停的等待新消息,也就是不会主动停止。那么就需要一个方式去通知所有的pipeline,应该停止接受消息了。自然的,你会想到消息队列——当收到 SIGINT 信号时,向所有pipeline 发送取消请求;所以所有的pipeline在等待新消息的同时,也要等待取消请求。这种同时等待两个异步任务的操作就是select

伪代码如下。由于有这个消息有多个consumer,且只需要发送一次。所以可以使用watch::channel

//  logic

let (cancel_tx, cancel_rx) = tokio::sync::watch::channel(false);

// 在多个任务中共享接收端
let task1 = tokio::spawn({
    let mut rx = cancel_rx.clone();
    async move {
        while !*rx.borrow() {
            // 正常工作循环
            tokio::select! {
                _ = rx.changed() => {
                    // 收到取消信号
                    break;
                }
                // 其他工作逻辑
            }
        }
    }
});

// 发送取消信号
cancel_tx.send(true)?;
// pipeline 具体逻辑
loop {
    tokio::select! {
        _ = rx.changed() => { break; }
        message => mq.recv() {
            // 具体的处理逻辑
        }
    }
}

不过我的程序其实使用了一个更高级的封装CancellationToken,我的使用方式和消息队列没有不同,但是事实上它支持多层级的任务取消。

日志记录

tokio团队的tracingtracing-subscriber用来记录异步日志很合适。我个人习惯在tokio::spawn的时候创建一个span

超时

tokio::time::timeout用起来很舒服,用它包裹一个异步任务,如果超时的可以提前返回。我用它来将 回调 和 轮询 机制结合在一起。

性能监控

异步 Drop

流式任务调度框架,如何追踪一个输入的全流程?最简单的办法就是一直使用同一个数据。我称之为Context,定义如下。在消息队列中直接传递Context,等到消息处理完成后,InnerContext就会被 drop。将一些逻辑放在Drop的实现中即可,如归档到数据库。

pub type Context = Arc<Mutex<InnerContext>>

impl Drop for InnerContext {
    fn drop(&mut self) {}
}

但是如果我需要在drop中调用异步函数怎么办?drop不能是异步的。如何阻塞的调用异步函数?

  • 可以使用futures::executor::block_on函数,它会创建一个简单的运行时单线程阻塞的执行异步任务。如果要进行的异步任务简单,可以使用这个方法。例如,将任务的数据通过 channel 传递给真正的工作任务。这是我所使用的。
  • 也许可以使用smol::block_on
  • 也可以使用tokio::task::block_in_place函数。
tokio::task::block_in_place(move || {
    tokio::runtime::Handle::current().block_on( async move {
        // logic
    })
});

数据查询语言

SQL 是一种 声明式 查询语言,用来对关系型数据库进行数据检索。

CSS 其实也是 一种 声明式 查询语言,用来修改HTML的样式。类似与 CSS 之于 HTML,XSL 也可以用来对 XML 进行检索。

对于使用者来说,API 会比命令式的更加简洁容易(想象使用Javascript修改HTML的样式)。并且它隐藏了引擎的实现细节,可以在无需对查询进行任何更改的情况下进行性能提升。最后,声明式语言往往适合并行执行。

MapReduce 是一个由 Google 推广的编程模型,用于在多台机器上批量处理大规模的数据

迭代器失效问题

在看leetcode题解的时候,不明白为什么可以一边持有容器的迭代器,一边对容器进行修改。如下代码的leftright变量。

class MedianFinder {
    multiset<int> nums;
    multiset<int>::iterator left, right;

public:
    MedianFinder() : left(nums.end()), right(nums.end()) {}

    void addNum(int num) {
        const size_t n = nums.size();

        nums.insert(num);
        if (!n) {
            left = right = nums.begin();
        } else if (n & 1) {
            if (num < *left) {
                left--;
            } else {
                right++;
            }
        } else {
            if (num > *left && num < *right) {
                left++;
                right--;
            } else if (num >= *right) {
                left++;
            } else {
                right--;
                left = right;
            }
        }
    }

    double findMedian() {
        return (*left + *right) / 2.0;
    }
};

事实上这和multiset的底层实现相关。mutliset底层实现是红黑树,节点之间用指针连接,插入新的元素不会导致原先节点的位置发生改变。所以代码的操作是安全的。而vector这样的数据结构就不一定了,因为它在插入的过程中需要进行扩容,改变元素的位置。

深入探究

map/set/multimap/multiset的底层实现是红黑树,list是链表。所以对于这些容器来说,插入insert新的元素不会导致原先的迭代器失效,而删除erase一个元素会导致删除元素的迭代器失效。

vector/string 在插入insert元素的时候,如果进行了扩容会导致所有迭代器失效;没有扩容由于需要将后面的元素整体向后移动,也会导致插入元素后面的所有迭代器失效。删除erase元素的时候,由于需要将后面的元素整体向前移动,也会导致删除元素后面的所有迭代器失效。

更详细的内容参考Stackoverflow,参考链接2。原理大同小异。

[!NOTE] 类比于Rust,是不会让你同时持有对一个容器的多个可变引用的。保证了安全的同时,极大的减轻了编程者的心智负担,代价则是灵活性的丧失。孰优孰劣没有答案。

What about Rust

类比于Rust,是不会让你同时持有对一个容器的多个可变引用的。保证了安全的同时,极大的减轻了编程者的心智负担,代价则是灵活性的丧失。孰优孰劣没有答案。

那么Rust需要如何遍历并删除item?如Vec,需要用Vec::retain方法,简化后的伪代码如下。相同的思路适用于C++。

fn retain<F>(&mut self, mut predicate: F)
where
    F: FnMut(&T) -> bool,
{
    let len = self.len();
    let mut write_idx = 0; // 慢指针:记录保留元素的位置
    let mut read_idx = 0;  // 快指针:遍历所有元素

    while read_idx < len {
        if predicate(&self[read_idx]) {
            // 保留元素:将元素移动到 write_idx 位置
            self.swap(write_idx, read_idx);
            write_idx += 1;
        }
        read_idx += 1;
    }

    // 截断向量,移除尾部不需要的元素
    self.truncate(write_idx);
}

Rust的其他容器的遍历并删除的方法也叫retain

参考链接

  1. 关于C++ 迭代器失效特性的研究 – 奇安信技术研究院
  2. Iterator invalidation rules for C++ containers - Stack Overflow

记一次SLOW SQL排查

没有使用ORM框架,也没有对SQL的执行时间进行统计,只是在运行的时候发现瓶颈貌似出现在了Postgresql数据库,于是开始尝试排查。。。

session

首先查看sessions。我用的是dbeaver,如果用SQL语句的话也可以:

SELECT sa.* FROM pg_catalog.pg_stat_activity sa

重点关注xact start记录的当前事务开始时间和query start当前正在执行的查询的开始时间。如果发现他们state=active而且他们较早,说明他们相关的SQL语句执行的很慢。

更好的办法应该是在执行SQL语句的时候进行时间统计,并LOG SLOW SQL,这也是很多ORM框架的自带功能。由于缺乏经验我没有做,只能这样排查。

explain

我找到了执行很慢的SQL,但是我自认为为他们创建了索引,不应该如此之慢。

这个时候可以用explain来看自己的索引到底有没有真正起作用。analyze选项表示真正执行这条SQL语句。

explain analyze  SELECT "from", amount, number
    FROM cashflow
    WHERE "to" = $1 AND is_fund = true
    ORDER BY number ASC LIMIT 1

这是explain analyze的结果:

Limit  (cost=1654659.38..1654659.50 rows=1 width=59) (actual time=154302.162..154654.812 rows=0 loops=1)
  ->  Gather Merge  (cost=1654659.38..1654669.42 rows=86 width=59) (actual time=154045.564..154398.214 rows=0 loops=1)
        Workers Planned: 2
        Workers Launched: 2
        ->  Sort  (cost=1653659.36..1653659.47 rows=43 width=59) (actual time=153242.010..153242.104 rows=0 loops=3)
              Sort Key: number
              Sort Method: quicksort  Memory: 25kB
              Worker 0:  Sort Method: quicksort  Memory: 25kB
              Worker 1:  Sort Method: quicksort  Memory: 25kB
              ->  Parallel Seq Scan on cashflow  (cost=0.00..1653659.15 rows=43 width=59) (actual time=153238.328..153238.422 rows=0 loops=3)
                    Filter: (is_fund AND (("to")::text = '0x42be8d8f46f1eeae232f684878bc5506af962637'::text))
                    Rows Removed by Filter: 19661737
Planning Time: 1.949 ms
JIT:
  Functions: 13
  Options: Inlining true, Optimization true, Expressions true, Deforming true
  Timing: Generation 73.339 ms (Deform 6.503 ms), Inlining 369.544 ms, Optimization 114.942 ms, Emission 130.445 ms, Total 688.269 ms
Execution Time: 154701.653 ms

其中的cost=start_time..end_time表示操作开始的代价操作完成的总代价。操作开始的代价看起来有些奇怪,它表示操作可以开始产生任何结果之前预计要花费的代价。对于一些操作,如排序或聚集,数据库需要读入所有相关数据并进行处理才能产生第一行结果。因此,这个 "开始代价" 包括了读取和处理数据直到第一行结果准备就绪所需的预计代价。可以看到执行计划中的每一步的总代价都是十分高昂的。

cost的单位并不是时间,而是对资源成本的抽象统计。具体可以看PostgreSQL: Documentation: 17: 19.7. Query Planning。真正的时间需要添加analyze真正执行后统计。

这是我为to, is_fund, number添加索引后的explain analyze结果。可以看到他用上了索引,效率很高。

Limit  (cost=0.56..4.62 rows=1 width=59) (actual time=1.888..1.888 rows=0 loops=1)
  ->  Index Scan using cashflow_fund_idx on cashflow  (cost=0.56..418.62 rows=103 width=59) (actual time=1.885..1.885 rows=0 loops=1)
        Index Cond: ((("to")::text = '0x42be8d8f46f1eeae232f684878bc5506af962637'::text) AND (is_fund = true))
Planning Time: 355.678 ms
Execution Time: 2.136 ms

C++中的四种多态(翻译)

通常讨论C++的多态,指的是通过基类指针/引用来使用其派生类,这叫做子类多态(subtype polymorphism)。但是实际上还有其他的多态,例如参数多态(parametric polymorphism)特设多态(ad-hoc polymorphism,我翻译的可能不太好,后面还是用ad-hoc原文)强制多态(coercion polymorphism)

这些多态在C++中还有其他名字:

  • 子类多态又称为运行时多态(runtime polymorphism)。(一般多态特指子类多态)
  • 参数多态又称为编译期多态(compile-time polymorphism)
  • ad-hoc多态又称为重载(overloading)
  • 强制转换多态又称为类型转换(casting)

在这篇文章中,我将通过C++语言的示例来阐述所有的多态性,并且解释它们为什么会有各种不同的名称。

子类多态(运行时多态)

当提到C++的多态时,默认指的是子类多态。它指的是通过基类指针/引用来使用其派生类的能力。

下面是一个例子。假设你有各种各样的猫科动物(felid)。由于它们都是猫科动物,并且它们都应该能够喵喵叫,因此它们可以表示为继承自Felid基类并覆盖meow纯虚函数的类,

// file cats.h

class Felid {
public:
 virtual void meow() = 0;
};

class Cat : public Felid {
public:
 void meow() { std::cout << "Meowing like a regular cat! meow!\n"; }
};

class Tiger : public Felid {
public:
 void meow() { std::cout << "Meowing like a tiger! MREOWWW!\n"; }
};

class Ocelot : public Felid {
public:
 void meow() { std::cout << "Meowing like an ocelot! mews!\n"; }
};

现在主程序可以通过Felid(基类)指针来调用Cat, TigerOcelot的方法。

#include <iostream>
#include "cats.h"

void do_meowing(Felid *cat) {
 cat->meow();
}

int main() {
 Cat cat;
 Tiger tiger;
 Ocelot ocelot;

 do_meowing(&cat);
 do_meowing(&tiger);
 do_meowing(&ocelot);
}

在这个程序中,主程序将指向Cat, TigerOcelot的指针传递给一个期望接收指向Felid的指针的do_meowing函数。由于它们都是Felid的子类,程序会为每个Felid调用正确的meow函数,输出结果如下:

Meowing like a regular cat! meow!
Meowing like a tiger! MREOWWW!
Meowing like an ocelot! mews!

子类多态也被称为运行时多态,这个名称的由来有很充分的理由。多态函数调用的解析是在运行时通过虚表(virtual table)的间接引用来完成的。另一种解释是,编译器在编译时并不确定被调用函数的地址,而是在程序运行时,通过在虚表中解引用正确的指针来调用函数。

在类型理论中,它也被称为包含多态

参数多态(编译期多态)

参数多态性提供了一种对任何类型执行相同代码的方法。在C++中,参数多态性是通过模板实现的。一个最简单的例子是一个泛型的max函数,它寻找两个参数中的最大值。

#include <iostream>
#include <string>

template <class T>
T max(T a, T b) {
 return a > b ? a : b;
}

int main() {
 std::cout << ::max(9, 5) << std::endl;     // 9

 std::string foo("foo"), bar("bar");
 std::cout << ::max(foo, bar) << std::endl; // "foo"
}

这里的max函数在类型T上是多态的。但是请注意,它不适用于指针类型,因为比较指针比较的是内存位置而不是内容。要让它为指针工作,你必须为指针类型专门化模板,这将不再是参数多态,而是特殊多态。

由于参数多态发生在编译时,因此也称为编译时多态。

[!NOTE] 关于模板,更多的内容可以参考模板

ad-hoc多态(重载)

ad-hoc多态允许具有相同名称的函数对每种类型有不同的行为。例如,对于两个int+将他们相加;对于两个string+将他们连接。这叫做重载

这里是一个具体的例子,为intstring实现函数add

#include <iostream>
#include <string>

int add(int a, int b) {
 return a + b;
}

std::string add(const char *a, const char *b) {
 std::string result(a);
 result += b;
 return result;
}

int main() {
 std::cout << add(5, 9) << std::endl;
 std::cout << add("hello ", "world") << std::endl;
}

ad-hoc多态也出现在C++的模板特化中。还是以上面的max模板为例,以下是如何为两个char *编写max

template <>
const char *max(const char *a, const char *b) {
 return strcmp(a, b) > 0 ? a : b;
}

现在你可以调用::max("foo", "bar")来查找字符串“foo”和“bar”的最大值。

强制转换多态

当一个对象或基本类型被强制转换为另一个对象类型或基本类型时,就会发生强制转换。例如:

float b = 6; // int gets promoted (cast) to float implicitly
int a = 9.99 // float gets demoted to int implicitly

如果类的构造函数不是explicit,也会发生强制转换。

#include <iostream>

class A {
 int foo;
public:
 A(int ffoo) : foo(ffoo) {}
 void giggidy() { std::cout << foo << std::endl; }
};

void moo(A a) {
 a.giggidy();
}

int main() {
 moo(55);     // prints 55
}

如果你创建了explicit修饰的构造函数,那就不可能了。推荐使用explicit修饰构造函数以避免意外转换。

同样,如果一个类定义了类型T的转换操作符,那么它可以在任何需要类型T的地方使用。例如:

class CrazyInt {
 int v;
public:
 CrazyInt(int i) : v(i) {}
 operator int() const { return v; } // conversion from CrazyInt to int
};

CrazyInt定义了一个类型为int的转换运算符。现在,如果我们有一个函数,比如说,print_int接受int作为参数,我们也可以向它传递一个CrazyInt类型的对象,

#include <iostream>

void print_int(int a) {
 std::cout << a << std::endl;
}

int main() {
 CrazyInt b = 55;
 print_int(999);    // prints 999
 print_int(b);      // prints 55
}

前面讨论的子类型多态实际上也是强制转换多态,因为派生类被转换为基类类型。

祝您在学习这些关于多态性的新知识时玩得开心,下次再见!

参考链接

原文链接:The Four Polymorphisms in C++。作者是一个大佬。

AppImage 创建“快捷方式”

AppImage是很 Linux 流行的应用打包方式。在运行的时候,他会将自身解压到/tmp/.mount_xxx文件夹下运行。

但是下载AppImage之后,难道每次使用都要打开下载目录然后运行吗?能不能在桌面,或者菜单,或者命令行直接打开呢?

想要在桌面/菜单打开,需要在~/Desktop/~/.local/share/applications创建一个Desktop文件。可以从/tmp/.mount_xxx复制Desktop文件,然后修改其中的可执行文件路径,以及Icon路径。必要的话将Icon文件复制出来。

想要在命令行打开,可以创建一个软链接到/usr/bin或者其他PATH中的路径。

ln -s xxx.AppImage /usr/bin/xxx

钉钉在部分桌面环境无法打开链接

我的桌面环境是Linux Mint。钉钉版本7.6.25-Release.4112601,无法通过点击打开链接(之前版本也是)。

钉钉默认安装在/opt/apps/com.alibabainc.dingtalk/files/<version>/com.alibaba.dingtalk,但是一般创建的快捷方式是运行上级目录的Elevator.sh,他里面链接了一个保护的动态链接库libcef.so(我并不知道具体是干啥的),导致无法通过浏览器打开链接。

可以修改Elevator.sh的这一行,将true改成false。或者通过修改其他地方让它不要被加载就可以了。

...
is_enable_cef109=true
if [ "${is_enable_cef109}" = "true" ]; then
    if [ "$os_machine" = "aarch64" ]; then
        if [ "${libc_lower_29}" = "true" ]; then
            preload_libs="${preload_libs} ./libm-2.31.so "
        fi
    fi
    preload_libs="${preload_libs} ./plugins/dtwebview/libcef.so "
else
if [ "$os_machine" = "mips64" ]; then
    echo mips64el branch
    preload_libs="${preload_libs} ./plugins/dtwebview/libcef.so "
fi
fi
...

ThirdWeb Attack Analysis

Summary

On December 5, 2023, Web3 development platform thirdweb reported security vulnerabilities in their prebuilt smart contracts. This flaw impacted all ERC20, ERC721, and ERC1155 tokens deployed using these contracts. In the following days, tokens deployed with the vulnerable contracts were progressively exploited in attacks.

Reason for selection

Thirdparty libraries play a critical role in software security, yet their importance is frequently underestimated. Modern software development relies heavily on reusing code from open source libraries. In smart contract programming, thirdparty libraries like OpenZeppelin are popular to incorporate security best practices and save time. But dependencies can still pose unforeseen dangers. The thirdweb hack is a typical example.

Vulnerability analysis

Simplified version

The root cause is that the forwarders (ERC-2771) were not designed to work with multicall.

Detailed version

ERC-2771

ERC-2771: This EIP defines a contract-level protocol for Recipient contracts to accept meta-transactions through trusted Forwarder contracts. No protocol changes are made. Recipient contracts are sent the effective msg.sender (referred to as _msgSender()) and msg.data (referred to as _msgData()) by appending additional calldata.

In practice, OpenZeppelin's ERC2771Context is widely used. The last 20 bytes of calldata from trusted forwarder is treated as _msgSender(). For common library users, it seems that they only need to replace all uses of msg.sender with _msgSender().

function _msgSender() internal view virtual override returns (address) {
    uint256 calldataLength = msg.data.length;
    uint256 contextSuffixLength = _contextSuffixLength();
    if (isTrustedForwarder(msg.sender) && calldataLength >= contextSuffixLength) {
        return address(bytes20(msg.data[calldataLength - contextSuffixLength:]));
    } else {
        return super._msgSender();
    }
}

function _msgData() internal view virtual override returns (bytes calldata) {
    uint256 calldataLength = msg.data.length;
    uint256 contextSuffixLength = _contextSuffixLength();
    if (isTrustedForwarder(msg.sender) && calldataLength >= contextSuffixLength) {
        return msg.data[:calldataLength - contextSuffixLength];
    } else {
        return super._msgData();
    }
}

Multicall

User can utilize multicall to integrate multiple calls into one single call. The calldatas of multiple calls extracted from the calldata of single call.  In practice, OpenZeppelin's MulticallUpgradeable is widely used. (The bug is fixed now)

function multicall(bytes[] calldata data) external virtual returns (bytes[] memory results) {
    results = new bytes[](data.length);
    for (uint256 i = 0; i < data.length; i++) {
        results[i] = _functionDelegateCall(address(this), data[i]);
    }
    return results;
}

ERC-2771+Multicall

The issue arises due to inconsistencies in how calldata is packed and unpacked between these two components (ERC-2771 and Multicall):

  1. As per ERC2771, the trusted forwarder should pack the message data and sender information together. The contract then uses _msgData() and _msgSender() to unpack the message data and sender information, respectively.

  2. However, the multicall function is not compatible with how ERC2771 packs data. In the correct implementation, multicall should use _msgSender() to unpack the sender information and append it to each message's calldata, so it can be unpacked properly in subsequent calls. But this step is missed.

  3. Meanwhile,  the contract following ERC2771 will try to unpack message data and sender information using _msgData() and _msgSender(). However, without the sender information appended to calldata, the sender information is unpacked as the last 20 bytes of _msgData(), which can be controlled by the attacker.

This allows an attacker to construct manipulated calldata that executes malicious logic with an arbitrary sender information, violating the expectations set by the specifications.

Attack analysis

Simplified version

Many tokens that use both of these libraries are vulnerable to similar attack methods. The attacker utilize the bug to impersonates the swap pool to burn its token, causing the price of token up. Then do a swap and draining the entire liquidity.

Detailed version

Let's take one instance of an attack transaction as an example.

https://phalcon.blocksec.com/explorer/tx/eth/0xecdd111a60debfadc6533de30fb7f55dc5ceed01dfadd30e4a7ebdb416d2f6b6

  1. Swap 5 $WETH for 3,455,399,346 $TIME.
  2. Invoke trusted forwarder with carefully crafted data, after being parsed by multicall, the burn function is called with Uniswap Pool as the _msgSender(). The $TIME balance of pool is decreased.

  1. Sync the pool, the price of $TIME is lifted.
  2. Swap 3,455,399,346 $TIME for 94 $WETH.

The step 2 is the key of attack. Attacker invoke Forwarder.execute to forward data:

However, it is parsed as bytes[] of length 1, then used as data to call the contract. 

Highlight & Lesson

In the DeFi space, it is crucial to also pay attention to the security of third-party libraries. Unfortunately, these libraries can sometimes interact with each other in unexpected and covert ways, posing a threat to the security of the contract. This highlights the importance of thorough auditing and monitoring to mitigate any potential vulnerabilities that may arise from such interactions.

零拷贝

减少内核和用户之间的拷贝

出于安全的考虑,内核不应该直接使用用户指针指向的内存,用户更不可能直接使用内核指针指向的内存。他们之间的信息交换,基本都要涉及拷贝,比如 Linux 上的 copy_to_usercopy_from_user

mmap 也是一个非常好用的东西。什么是 mmap?mmap 是一种内存映射文件的方法,即将一个文件或者其它对象映射到进程的地址空间,实现文件磁盘地址和进程虚拟地址空间中一段虚拟地址的一一对映关系。实现这样的映射关系后,进程就可以使用操作内存的方式操作文件,而系统会自动回写脏页面到对应的文件磁盘上,即完成了对文件的操作而不必再调用 read,write 等系统调用函数。相反,内核空间对这段区域的修改也直接反映用户空间,从而可以实现不同进程间的文件共享。

所以,当你有若干个进程以只读的方式访问一个文件,或者是访问较大文件的大块,用 mmap 都是很好的选择。mmap 还可以用来做进程通信。不过并不是所有的文件都可以用 mmap 来访问,例如 socket 就只能用他专有的接口读写,还有 pipe 类型的文件就只能用 read/write 等。也不是所有能用 mmap 的文件都适合用 mmap,一个和 page 差不多大的文件,或者你就想从文件中读那么几个字节,用 mmap 适得其反。

使用 mmap

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

int main() {
    long checksum = 0;
    struct stat sb;

    int fd = open("disk.dd", O_RDONLY);
    fstat(fd, &sb);
    void *file = mmap(0, sb.st_size, PROT_READ, MAP_PRIVATE, fd, 0);

    for (long i = 0; i < (sb.st_size >> 3); i++) {
        checksum ^= *((long *)file + i);
    }
    printf("checksum = 0x%lx\n", checksum);
    close(fd);
}

// checksum = 0xdcce4fdc7fd2151d
// real    0m5.762s
// user    0m2.910s
// sys     0m2.358s

mmap 为什么会比带 buffer 的 read/write 快呢,Page Size 是 4K,每次缺页加载 4K,和我之前手动 Buffer 不是很相似吗?因为 少了一次 CPU 的拷贝。试想 read 的过程,DMA 将数据从硬盘拷贝到 kernel space,CPU 再将数据从 kernel space 拷贝到 user space;而 mmap 就少了一次从 kernel space 拷贝到 user space 的过程。

不过在使用 mmap 的时候需要小心,如果有其他的进程截断了文件,那么你可能会访问到一个非法的地址,从而进程被杀死。

除了 mmapsendfile/splice 也可以实现类似的减少从 kernel space 到 user space 拷贝的作用,我们在后面介绍。他们提供的这种特性叫做 零拷贝 Zero Copy知乎上的这篇文章 提供了一个很好的介绍。

如果追求极致,你可以绕过内核做 I/O 操作,不过一般情况下这样做会牺牲相当的灵活性、可移植性,而且非常困难。

针对网络的零拷贝技术

下面我们要面对的场景,是我们从硬盘中读取数据到内存,进行处理,然后写到网卡中。这是一个很典型的网络应用的操作。

那么,最原始的使用 read/write 进行操作的话,我们将至少会有 4 次拷贝。中间两次是内存中的拷贝,虽然需要内核态到用户态的切换,但是相对 I/O 来说还是快的。但是我们还是要优化中间 2 次。

  • 硬盘拷贝到内存(内核态),DMA,慢
  • 内核态拷贝到用户态,CPU,快
  • 用户态拷贝到内核态,CPU,快
  • 内存(内核态)拷贝到网卡,DMA,慢

如果我们使用之前介绍的 mmap,我们可以优化到 3 次。

使用 sendfile,可以优化到 2 次,硬盘 ->内核态内存 ->网卡。但是你也发现了,没有经过用户态我们怎么处理数据,答案就是 没法处理数据,所以他可能只适合用于静态服务器。那么既然都无法处理了,还拷到内存干啥?能不能直接从硬盘 DMA 到网卡呢?答案是可以,新的 Linux 已经让 sendfile 可以做到这一点了,也就是可以优化到 1 次了。splice 也是类似的。

Copy On Write

其实这是一种思想,对于读多写少的场景的优化。在追求极致优化的内核中得到了广泛使用。你看到 rcu 字样的时候,多半就是 copy on write。