模板元编程，斐波那契数列

2024-02-28 C++11/14/17 废话少说,放码过来

定义一个模板结构体，模板参数是个常量，结构体有个成员 v,用于存储斐波那契数。

1
2
3
4
template<int N>
struct Fib {
    static constexpr int v = Fib<N-1>::v + Fib<N-2>::v;
};

注意, constexpr 用于声明一个常量表达式，明确告知编译器，该表达式可以在编译时期计算出结果。

然后针对 Fib<1> 和 Fib<2> 进行模板特化

1
2
3
4
5
6
7
8
9
template <>
struct Fib<1>{
    static constexpr int v = 1;
};

template <>
struct Fib<2>{
    static constexpr int v = 1;
};

然后 Fib<N>::v 就是编译期确定的斐波那契数。

下面是完整的例子

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

#include <iostream>

template<int N>
struct Fib {
    static const int v = Fib<N-1>::v + Fib<N-2>::v;
};

template <>
struct Fib<1>{
    static const int v = 1;
};

template <>
struct Fib<2>{
    static const int v = 1;
};

template <int Start, int End>
void print(){
    if constexpr (End >= Start){
        std::cout << Fib<Start>::v << std::endl;
        print<Start + 1,End>();
    }
}

int main(int argc, char **argv){
    print<1,10>();
    return 0;
}

TCP 随笔

2024-02-27 理解计算机

本文章记录TCP的一些杂七杂八的知识点，比较零碎。

  1. ICMP 可用于发现链路上的最小 MTU

  2. 一条 sock 连接有五元组(Proto, SourceIp, DestIp, SourcePort, DestPort) 组成，任意一个改变都是可以是一个新的连接。
    比如两台机器都有 2个IP，2个端口，用于TCP连接。那么他们之间可以创建 (2222)2 = 32 个 TCP 连接。

  3. 传输层协议除了TCP 还有 UDP/SCTP/DCTP

  4. TCP中的序号 是字节流编号，而不是报文的序号。比如第一个报文序号是0，然后该报文有300个字节的数据，那么第二个报文的序号就该是300

  5. 确认号表示期望收到的下一个报文的第一个字节编号是多少，比如面收到第一个报文之后，确认号就回设置为300，表示接下来希望收到第一个字节编号为300的报文

  6. TCP的第一个序号通常假设为0， 但实际上可以随机的选择初始序号

  7. 如果发送端收到同一个序号的重复确认3次（冗余ACK）即可认为序号之后的报文已经丢失，可以进行快速重传

  8. TCP 接受方重传的时候可以跳过那些已被选择确认的报文，需要接收方支持选择确认。（SACK，在TCP首部的 options 字段里）

  9. TCP 接受方会维护一个 LastByteRead, 用户层已读取的最后一个字节的编号; LastByteRecv, 放入到缓存区的最后一个字节的编号。还有一个缓存区大小RecvBuffer。滑动窗口大小，就是缓存区大小（Buffer）减去已缓存的大小(Recv-Read)

  10. TCP 发送方会维护一个 LatByteSent, 已发送的序号； LastByteAcked, 已被确认的序号。Sent-Acked 需要小于滑动窗口的大小。来保证接口方的缓存区不会被溢出。

  11. 如果接收方缓存区满了之后，窗口会设置为0；之后发送方会发送只有一个字节的报文段，用来 “轮询” 窗口更新。

  12. TCP第三次握手确认的时候可以携带一些数据。

  13. 现在的主流操作系统都支持syn-cookie，在第三次握手之前，服务器并不维护客户端的信息， 可以有效的防御syn-flood攻击。

  14. MSS 最大报文段长度，避免物理层分片，通常比MTU小一点。（在options里协商）

  15. RTT 连接往返时间，即发出后到收到ACK的时间。

  16. 拥塞控制

    1. 慢启动，刚开始以一个MSS的值传输，后面2个，4个，成指数增长。直到发生拥塞，把此时窗口值的1/2，叫做慢启动阈值。
    2. 发生拥塞的时候，重新从1个MSS开始增加，直到增加到慢启动阈值, 之后不再指数增加，而是一个MSS一个MSS的增加。这个过程叫拥塞避免。
    3. 快速恢复，收到3次冗余ACK的时候，窗口不再从1个MSS开始，而是从慢启动阈值+3开始，然后开始重传。

  17. TCP 字段

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
     0                   1                   2                   3   
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |          Source Port          |       Destination Port        |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                        Sequence Number                        |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                    Acknowledgment Number                      |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |  Data |           |U|A|P|R|S|F|                               |
    | Offset| Reserved  |R|C|S|S|Y|I|            Window             |
    |       |           |G|K|H|T|N|N|                               |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |           Checksum            |         Urgent Pointer        |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                    Options                    |    Padding    |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                             data                              |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

    在RFC 3168 中 TCP 的 reserved 位置又使用了两位(CWE, ECE 用于处理拥塞控制和显式拥塞通知)

    1
    2
    3
    4
    5
    6
    7
     0                   1                   2                   3   
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |  Data |       |C|E|U|A|P|R|S|F|                               |
    | Offset|Reser. |W|C|R|C|S|S|Y|I|            Window             |
    |       |       |R|E|G|K|H|T|N|N|                               |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

  18. TCP与网络编程

    1. 首先是服务端 bind，listen 初始化接受队列
    2. 客户端 connect 选择本地端口，发起 syn 握手请求，同时启动重传定时器
    3. 服务端 回应 syn ack， 将连接加入到半连接队列，启动重传定时器
    4. 客户端收到 ack，清除定时器，设置为已连接，发送ack
    5. 创建 sock 从半连接队列中取出放到全连接队列。
    6. accept 从全连接队列中取出 socket

C++中的锁

2024-02-19 C++11/14/17

C++中，锁是用来管理并发访问共享资源的工具，下面是与锁相关的一些概念。

std::mutex

互斥锁，最基本的锁类型之一，提供了最基本的锁操作，lock()/unlock()/try_lock();

std::shared_mutex

共享锁，或者叫读写锁， C++17中引入的。允许多个线程同时读取共享锁。

std::lock_guard, std::unique_lock, std::shared_lock

对 mutex 进行了一层封装，更为抽象的封装，RAII风格，为 mutex 的管理类。

  • std::lock_guard 在构造函数时候加锁，在析构的时候释放锁。
  • std::unique_lock 支持手动释放锁，加锁。
  • std::shared_lock 与 std::shared_mutex 配合实现共享锁

std::atomic_flag

原子布尔类型，可用于实现自旋锁。提供有 test_and_set()/clear() 方法

std::condition_varable

条件变量不是锁，而是与锁结合使用来实现复杂的线程同步机制。它允许一个线程在条件变量上等待，被唤醒之后先判断表达式的值，如果为真再尝试获取锁。

C++虚继承下的内存布局

2024-01-21 C++对象模型

多继承

讲虚继承之前，先讲讲多继承，下面是一个多继承的示例， C 继承了 A 和 B。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>

class A  {
public:
    long varA;
    virtual void funA1(){ std::puts("A::funA1()");};
    virtual void funA2(){ std::puts("A::funA1()");};
};

class B {
public:
    int varB;
    virtual void funB1(){ std::puts("B::funB1()");};
    virtual void funB2(){ std::puts("B::funB2()");};
};

class C: public A, public B {
public:
    int varC;
    virtual void funA1(){ std::puts("C::funA1()");};
    virtual void funB2(){ std::puts("C::funB2()");};
    virtual void funC(){ std::puts("C::funC()");};
};

先思考下面几个问题

  1. A, B, C的对象大小应该都是多大？
  2. 有 A* a = new C();， 那么 typeid(*a) 返回的会 A 的信息，还是 C 的信息？
  3. 有函数 void process(A *a);, 该函数内部，能否访问到 B::funB1 / B::funB2 吗?
  4. 只给一个类C的指针，怎么不用他的函数接口来访问它的虚函数？
  5. 虚函数调用会增加访问调用开销吗？多重继承得到的虚函数和单层继承得到的虚函数，他们调用开销一样吗？

如果你对上面的问题了如指掌，建议跳过本文章。

内存布局

A,B,C 的内存布局与虚函数表如下

可以通过 g++ -fdump-lang-class -c base.cpp 来看到C++ 类的虚函数表和内存布局

我们先以class A 为例， 讲解下虚函数表的内容。

1
2
3
4
5
6
7
8
9
--------------
0              // Top Offset 原始对象的偏移量
--------------
typeinfo for A // RTTI信息，dynmaic_cast 转换的时候会根据这个判断是否能转换
--------------
A::funA1()     //  虚函数表指针指向的位置，注意，虚函数表指针指向的是该位置，而不是虚函数表的开头
--------------
A::funA2()
--------------

在非虚继承当中，基类的内存布局要在派生类中保证完整性，比如示例中 C 的内存布局可以拆分成两块，一块用来表示子对象A，一块用来表示子对象B。上面的 Offset 原始对象指针的偏移。通常多继承的情况下，第一个子对象在内存布局的最顶部，所以 Offset 为 0，但是之后其它子对象的 Offset 就不为 0 了， 比如示例中的 子对象 B ，其 Offset 就为 -16，子对象B的指针向上偏移16就得到了原始对象的指针，该字段在基类向派生类转换的时候会用到。

基类派生类转换

派生类->基类

首先要知道，派生类到基类的转换，百分百会成功，因为所谓的转换就是对指针进行调整，使其指向子对象的位置，这个动作编译器在编译期间就已经确定了。

1
2
3
4
5
void fun(C *c){
    B *b = c; // 编译器会进行隐式转换，使指针B指向C内部子对象b的位置。
    printf("c: %p\n", c); // c: 0x000000000010
    printf("b: %p\n", b); // b: 0x000000000020
}

基类->派生类

但是当基类到派生类转换的时候，如果通过基类对象的地址找到其原本派生类对象的地址呢？ 这就用到了前面提到的 Top Offset, 基类对象的地址，加上该偏移就得到了原始对象的地址。

1
2
3
4
5
6
7
8
int main() {
    C c1;
    B *b = &c1;
    C *c2 = dynamic_cast<C *>(b); 
    printf("c1: %p\n", &c1); // c1: 0x000000000010
    printf("b : %p\n", b);   // b : 0x000000000020
    printf("c2: %p\n", c2);  // c2: 0x000000000010
}

访问虚函数

下面是一份通过内存布局访问虚函数的代码，在 Compiler Explore 上查看

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
#include <cstdio>

class A  {
public:
    long varA;
    virtual void funA1(){ std::puts("A::funA1()");};
    virtual void funA2(){ std::puts("A::funA1()");};
};

class B {
public:
    int varB;
    virtual void funB1(){ std::puts("B::funB1()");};
    virtual void funB2(){ std::puts("B::funB2()");};
};

class C: public A, public B {
public:
    int varC;
    virtual void funA1(){ std::puts("C::funA1()");};
    virtual void funB2(){ std::puts("C::funB2()");};
    virtual void funC(){ std::puts("C::funC()");};
};

int main(int argc, char **argv){
    C c;
    using Fun = void (*)();
    Fun *virtual_table = ((Fun**)&c)[0];

    //  virtual_table[-2] 内部子对象 A 的偏移
    //  virtual_table[-1] typeinf
    virtual_table[0]();
    virtual_table[1]();
    virtual_table[2]();
    virtual_table[3]();
    //  virtual_table[3] 内部子对象 B 的偏移
    //  virtual_table[4] typeinfo
    virtual_table[6]();
    virtual_table[7](); // thunk 间接调用
}

思考

如果 类 A 和类 B 都继承了一个 Base 类，那么 A 和 B 内部都有了 Base 类的成员。 那么 C 内部岂不是有两份 Base 的数据成员？怎么解决这个问题？这个就讲的了虚继承

虚继承

虚继承和普通继承的区别，简单来说有两点

  1. 新增加了一个 vtt 表，也就是虚函数表的表，里面存放的是虚函数表的地址。
  2. 虚函数表内在Top Offset上新增加了字段，用来表示内部虚拟子对象的偏移。

内存布局

下面是一个虚继承下的内存布局与虚函数表示例

注意到 VTT 中有几处空白没有列出来，那几个是构造函数虚表，有兴趣可自行了解。

访问虚函数表

下面是一份通过内存布局访问虚函数的代码，在 Compiler Explorer上查看 

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
43
44
45
46
47
48
49
50
51
52
53
54
#include <cstdio>

class Base {
public:
  long varBase{1};
  virtual void funBase() { std::puts("Base::funBase"); };
};

class A : virtual public Base {
public:
  long varA{2};
  virtual void funA1() { std::puts("A::funA1"); };
  virtual void funA2() { std::puts("A::funA2"); };
};

class B : virtual public Base {
public:
  long varB{3};
  virtual void funB1() { std::puts("B::funB1"); };
  virtual void funB2() { std::puts("B::funB2"); };
};

class C : public A, public B {
public:
  long varC{4};
  virtual void funA1() { std::puts("C::funA1"); };
  virtual void funB2() { std::puts("C::funB2"); };
  virtual void funC() { std::puts("C::funC"); };
};

void printMemoryLayout(void *ptr) {

  printf("[0]：%p, vtable_ptr_for_A\n", *((void **)ptr));
  printf("[1]：%ld, varA\n", *((long *)((char *)ptr + 8))); // varA = 2
  printf("[2]：%p, vtable_ptr_for_B\n", *((void **)ptr + 2));
  printf("[3]：%ld, varB\n", *((long *)((char *)ptr + 24))); // varB = 3
  printf("[4]：%ld, varC\n", *((long *)((char *)ptr + 32))); // varC = 4
  printf("[5]：%p, vtable_ptr_for_Base\n", *((void **)ptr + 5));
  printf("[6]：%ld, varBase\n", *((long *)((char *)ptr + 48))); // varBase = 1

  using Fun = void (*)();
  Fun *vtable_for_a = *((Fun **)ptr);
  Fun *vtable_for_b = *((Fun **)ptr + 2);
  Fun *vtable_for_base = *((Fun **)ptr + 5);

  (*vtable_for_a)();
  (*vtable_for_b)();
  (*vtable_for_base)();
}

int main() {
  C c;
  printMemoryLayout(&c);
}

你真的理解 shared_ptr 吗

2024-01-16 C++11/14/17

C++ 的 shared_ptr 是什么呢？你真的理解吗？让我们试着回答以下问题。

  1. 下面的几行代码是否正确，是否存在差异？
    1
    2
    3
    std::shared_ptr<int> p1;
    std::shared_ptr<int> p2(new int(0));
    std::shared_ptr<int> p3 = std::make_shared<int>(0);
  2. void func(Class *A); 的参数可以是 std::shared_ptr<A> 吗？
  3. shared_ptr<T> 是线程安全的吗？
  4. 类成员函数如何返回指向自身的 shared_ptr？
  5. 如何自定义 shared_ptr 的释放行为？

问题解答

1. shared_ptr(new T) 与 make_shared()

在 C++ 中，shared_ptr 内部有一个指向动态分配对象的指针和一个指向控制块的指针。指向同一对象的共享指针共享这两个块。

1
2
3
std::shared_ptr<int> p1;  // 空对象，数据指针指向空，分配控制块内存，并计数 0
std::shared_ptr<int> p2(new int(0)); // 数据指针指向 `new int(0)` 的内存地址，分配控制块内存，计数 1
std::shared_ptr<int> p3 = std::make_shared<int>(0); // 分配一次内存(数据块+计数块), 数据指针指向数据块，控制块计数为1

make_shared 只分配一次内存，效率更高，且能够有效避免内存碎片的产生。

2. 获取裸指针

std::shared_ptr<T> 构造函数中传入了一个对象指针。它同时提供了一个 get() 方法用来返回裸指针，但是在使用裸指针时要注意其生命周期。

3. shared_ptr 是线程安全的吗？

shared_ptr 的引用计数是原子操作，因此是线程安全的。但是 shared_ptr 指向的对象以及 shared_ptr 自身并不是线程安全的。在多线程中修改 shared_ptr 指向的数据或修改 shared_ptr 自身的指向可能对其他线程的 shared_ptr 造成破坏。

4. enable_shared_from_this

考虑下面的代码会有什么问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <memory>

class A {
public:
    std::shared_ptr<A> getPtr(){
        return std::shared_ptr<A>(this);
    }
};

int main(int argc, char **argv){
    auto p1 = std::shared_ptr<A>(new A());
    auto p2 = p1->getPtr();
}

运行这段代码会发现 A 会被析构两次。因为 std::shared_ptr<A>(this) 会增加一次引用计数，而返回的 shared_ptr 和之前的 shared_ptr 是没有关联的，所以会各自析构一次。下面的代码有同样的问题。

1
2
3
4
5
6
void test(){
    A *p = new A();
    auto p1 = std::shared_ptr<A>(p);
    auto p2 = std::shared_ptr<A>(p);
    // p1 和 p2 各自独立
}

enable_shared_from_this 就是为了解决通过对象获取自身的智能指针的问题。

1
2
3
4
5
6
7
8
#include <memory>

class A std::enable_shared_from_this<A> {};

int main(int argc, char **argv){
    auto p1 = std::shared_ptr<A>(new A());
    auto p2 = p1->shared_from_this(); // 同 auto p2 = std::weak_ptr<A>(p1);
}

enable_shared_from_this 内部也是通过 weak_ptr 的原理来实现的。

5. 自定义 shared_ptr 删除器

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <memory>

int main() {
    auto customDeleter = [](int* p) {
        std::cout << "Custom deleting: " << *p << std::endl;
        delete p;
    };

    std::shared_ptr<int> sharedPtr(new int(42), customDeleter);

    // 使用 sharedPtr，最后会调用 customDeleter 进行释放
    return 0;
}