TCP Keepalive && Heartbeat

在默认情况下,在建立TCP连接之后,空闲时刻客户端和服务端不会互相发送数据包确认连接。假如有一端发生异常而掉线(如死机、防火墙拦截包、服务器爆炸),另一端若不进行连接确认,则会一直消耗资源。

为了保证连接的有效性,可以检测到对方端非正常的断开,我们通常利用两种机制来实现:

  • 利用TCP协议的Keepalive
  • 在应用层实现心跳检测(Heart Beat)

TCP Keepalive

TCP Keepalive通过定时发送Keepalive探测包来探测连接的对端是否存活。

交互过程:

在收到对端的确认报文后,设置keepalive timer。当长时间两端无交互并且保活定时器超时的时候,本段会发送keepalive probe等待对端确认。若对端在一定时间内确认(具体的规则貌似比较繁琐),keepalive timer重置;否则,长时间未响应,连接终止。

TCP Keepalive默认是关闭的,因为它会消耗额外的资源,并且可能会关闭正常的连接。(它也非TCP标准,详情可见The Host Requirements RFC [RFC1122])

在Linux Kernal中可以调整以下几个数值来设置Keepalive的属性:

sysctl variables net.ipv4.tcp_keepalive_time net.ipv4.tcp_keepalive_intvl net.ipv4.tcp_keepalive_probes
default 7200s 75s 9

Heart Beat

很多应用层协议都有心跳检测机制,客户端每隔一段时间就会向服务端发送一个数据包,通知服务端自己可以正常工作,同时传递一些数据。

两种方式的特点:

  • TCP Keepalive是TCP协议自带的实现,使用简单,其发送的数据包与应用层心跳检测包相比更小,但其功能也简单,仅提供检测连接功能
  • 应用层心跳包不依赖于传输层协议,无论传输层协议是TCP还是UDP都可以用
  • 应用层心跳包可以定制,可以应对更复杂的情况或传输一些额外信息
  • Keepalive仅代表连接保持着,而心跳包往往还代表客户端可正常工作

TCP 拥塞控制

TCP拥塞控制这一块东西比较多~这里只总结重要的。

TCP的拥塞控制主要依赖于 拥塞窗口(congestion window, cwnd) 和 慢启动阈值(slow start threshold, ssthresh)。cwnd是发送端根据网络的拥塞程度所预设的一个窗口大小,而ssthresh则是慢启动窗口的阈值,cwnd超过此阈值则转变控制策略。

TCP拥塞控制的主要算法有 慢启动(Slow Start)、拥塞避免(Congestion Avoidance)、快速重传(Fast Retransmit)、快速恢复(Fast Recovery)等。

Slow Start

如果TCP连接一建立就向服务器大量发包,很容易导致拥塞。因此,新建立的连接不能一开始就大量发送数据包,而是应该根据网络状况,逐步地增加每次发送数据包的量,这就是慢启动。慢启动通常在新建立TCP连接或由于RTO而丢包时执行。

具体来说,新建TCP连接时,cwnd需初始化为一个或几个最大发送报文段大小(send maximum segment size, SMSS)。具体规则(IW为初始窗口大小):

IW = 1*(SMSS) (if SMSS <= 2190 bytes)

IW = 2*(SMSS) and not more than 2 segments (if SMSS > 2190 bytes)

IW = 3*(SMSS) and not more than 3 segments (if 2190 ≥ SMSS > 1095 bytes)

IW = 4*(SMSS) and not more than 4 segments (otherwise)

发送端按照cwnd大小发送数据,每当数据被确认时,cwnd就以2为倍数进行指数级增长,即 $cwnd{n}=2*cwnd{n-1}$

比如:

1
2
3
4
5
6
7
开始 ---> cwnd = 1*SMSS
经过一个RTT ---> cwnd = 2*SMSS
经过两个RTT ---> cwnd = 2^2=4*SMSS
经过三个RTT ---> cwnd = 2^3=8*SMSS

如果带宽为W,那么经过 $RTT log_{2}W$ 时间就可以占满带宽。

显然,慢启动并不慢,cwnd会飞速增长。但是cwnd不能无限制地进行指数增长。当cwnd值超过慢启动阈值(ssthresh)时,慢启动过程结束,进入拥塞避免阶段。拥塞避免算法将在下面总结。

Congestion Avoidance

当cwnd值超过ssthresh值时,慢启动过程结束,进入拥塞避免阶段。在拥塞避免阶段,cwnd将不再呈指数增长,而是呈线性增长。一般来说:

  • 收到一个ACK时,cwnd = cwnd + 1/cwnd
  • 当每过一个RTT时,cwnd = cwnd + 1

这样放缓了拥塞窗口的增长速率,避免增长过快导致网络拥塞,慢慢的增加调整到网络的最佳值。

拥塞状态

在慢启动阶段与拥塞避免阶段,只要判断发送方出现丢包,就会进行相应的控制。有两种情况:

(1) 等待RTO超时,重传数据包,此时TCP反应强烈:

  1. 将ssthresh降低为此时cwnd的一半
  2. 将cwnd重新设为初始值(IW)
  3. 重新进入慢启动阶段

原则:加法增大、乘法减小。

(2) 连续收到3个duplicate ACK时,重传数据包,无须等待RTO。此情况即为下面的快速重传。

Fast Retransmit

TCP在收到一个乱序的报文段时,会立即发送一个重复的ACK,并且此ACK不可被延迟。

如果连续收到3个或3个以上重复的ACK,TCP会判定此报文段丢失,需要重新传递,而无需等待RTO。这就叫做快速重传。

注:快速重传始于BSD 4.3 Tahoe,但Tahoe的TCP实现没有包含快速恢复阶段,快速重传后会退回至慢启动阶段。

Fast Recovery

快速恢复是指快速重传后直接进入拥塞避免阶段而非慢启动阶段。总结一下快速恢复的步骤(以SMSS为单位):

  1. ​当收到3个重复的ACK时,将ssthresh设置为cwnd的一半(ssthresh = cwnd/2),然后将cwnd的值设为ssthresh加3(cwnd = ssthresh + 3),然后快速重传丢失的报文段
  2. 每次收到重复的ACK时,cwnd增加1(cwnd += 1),并发送1个packet(如果允许的话)
  3. 当收到新的ACK时,将cwnd设置为第一步中ssthresh的值(cwnd = ssthresh),代表恢复过程结束

快速恢复后将进入拥塞避免阶段。

注:快速恢复始于BSD 4.3 Reno。

NewReno

快速恢复存在的一个问题是它只能针对一个packet重传而不能针对多个packet,这样会RTO到吐。因此后来标准提出了NewReno作为Reno的补充。NewReno可以解决一个窗口内多个packet丢失的情况(Partial ACK),即NewReno算法需要处理完该窗口内所有packet的ACK后方可结束恢复状态。这是一种激进的优化,适合不支持SACK的情况。(通过recovery变量实现)

SACK

SACK维持一个名为pipe的变量,代表流量的估计值。发包的时间由pipe决定。具体细节可见 RFC 2018

SACK可能会出现pipe计算不精确的情况,这样会使算法退化回Tahoe。Forward Acknowledgment (FACK)是对SACK的改进,它可以精确地计算pipe值。

其它

更多的拥塞控制算法见TCP Congestion Avoidance Algorithm

TCP Retransmission

TCP协议需保证所有的数据包都可以到达,因此必须要有重传机制。

  • RTT: Round Trip Time
  • RTO: Retransmission Timeout(重传超时时间)

RTO Algorithm

如何计算RTO:

  • 经典算法
  • Karn’s Algorithm
  • 标准算法(Jacobson/Karels Algorithm, 目前Linux内核在用)

前面两种算法用的都是“加权移动平均”,这种方法最大的毛病就是如果RTT有一个大的波动的话,很难被发现,因为被平滑掉了。

重传机制

超时重传

通过重传计时器(retransmission timer)实现。

快速重传

TCP在收到一个乱序的报文段时,会立即发送一个重复的ACK,并且此ACK不可被延迟。

如果连续收到3个或3个以上重复的ACK,TCP会判定此报文段丢失,需要重新传递,而无需等待RTO。这就叫做快速重传。

SACK && Duplicate SACK

Selective Acknowledgment (SACK)是 TCP 的一项可选特性,可以提高某些网络中所有可用带宽的使用效率。普通 TCP(即未提供 SACK 特性)应答是严格累积的 — 对 N 的应答意味着字节 N 和所有之前的字节都已经收到。SACK 要解决的问题普通累积式应答的 “全有或全无” 性质。

例如,即使包 2(假设从 0 到 9 的序列)是在传送过程中惟一丢失的包,接收方也只能对包 1 发出一个普通的 ACK,因为这是连续接收到的包中的最后一个。另一方面,SACK 接收方可以发出包 1 的 ACK 和包 3 到包 9 的 SACK 选项。这样,发送端就可以根据回传的SACK来知道哪些数据到了,哪些数据丢失了,进而可以优化Fast Retransmit。SACK需要两端的协议都支持,在目前的Linux Kernal中默认为开启状态。

low-rate DoS attacks

应用层应用:Slowloris (HTTP slow headers)

防范:随机化RTO

计算机网络相关知识总结

本文将不断更新~

网络模型

OSI七层模型:物理层、数据链路层、网络层、传输层、会话层、表示层、应用层

数据链路层对应的数据为Frame,网络层对应的数据为Packet,传输层对应的数据为Segment。

网络数据首先会打到TCP的Segment中,然后TCP的Segment会打到IP的Packet中,然后再打到以太网Ethernet的Frame中,传到对端后,各个层解析自己的协议,然后把数据交给更高层的协议处理。

The standard seven-layer OSI model

TCP/IP四层模型:链路层、网络层(IP/ICMP/IGMP)、传输层(TCP/UDP)、应用层(如Telnet/HTTP/FTP)

IPv4 and IPv6 Headers

IPv4 Datagram分为首部(Header)和数据两部分。IPv4 Header由固定部分(Basic)和选项部分(Options)组成,其中固定部分的大小为20 bytes。IPv4 Header最大为60 bytes。

总结几个重要的field:

  • ToS(Type of Service):DS Field(Differentiated Services Field) + ECN(Explicit Congestion Notification, 显式拥塞通知)
  • TTL(Time-to-Live):数据报可以经过的最多路由数,指示了数据报的生存时间

The IPv4 Datagram

与IPv4 Header不同,IPv6 Header具有固定的大小(40 bytes),并且没有选项部分。但是IPv6 Header可以有扩展首部(extension headers),其作用与Options类似。Next Header字段用于指示extension headers。

The IPv6 Header

大端、小端与网络字节序

大小端是面向多字节定义的字节存储顺序。

大端(Big-Endian)就是最高有效字节(MSB)在前,内存存储体现上,数据的高位更加靠近低地址。

小端(Little-Endian)就是最低有效字节(LSB)在前,内存存储体现上,数据的低位更加靠近低地址。

比如对字0x01234567,最高有效字节为0x01,最低有效字节为0x67,那么其对应的大端存储顺序为01 23 45 67,小端存储顺序为67 45 23 01

对于IP数据报来说,RFC标准要求数据在网络中传输时都要求以大端字节序传输,因此网络字节序就对应Big-Endian字节序。

TCP 连接的建立和终止

这篇文章将总结TCP首部及连接的相关知识。

TCP(Transmission Control Protocol)提供一种面向连接的、可靠的字节流服务。TCP连接是全双工的,即数据在两个方向上能够同时传递。

TCP Header

TCP报文由首部和数据组成,数据部分是可选的。TCP报文被封装在IP数据报中,结构如下图所示:

IP Datagram

TCP Header由固定部分(Basic)和选项部分(Options)组成,其中固定部分的大小为20 bytes。TCP Header最大为60 bytes。

TCP Header的结构如下图所示:

TCP Header

挑几个重要的说:

  • Sequence Number(序号,Seq):用来标识从TCP发送端到接收端发送的数据字节流,它表示这个报文段中的第一个数据字节,也用于解决packet乱序问题
  • Acknowledgment Number(确认序号):包含发送确认的一端所期望收到的下一个序列号
  • CWR:阻塞窗口减小(Congestion Window Reduced),通常是发送端减小了其发包速率
  • ECE:ECN Echo
  • URG:紧急指针(Urgent Pointer)有效
  • PSH:该标志置位时,接收端不将该数据进行队列处理,而是尽可能快将数据转由应用处理
  • ACK:确认序号(Acknowledgment Number)有效
  • RST:重置连接(通常由于连接错误)
  • SYN:同步序号(Sequence Number),用来发起一个连接
  • FIN:发送端完成发送任务
  • Window Size:滑动窗口大小,用于流量控制

TCP连接的建立和终止

三次握手

TCP three-way handshake(三次握手)的过程:

  1. 第一次握手(SYN):客户端首先发送一个SYN包到服务器,初始序号Seq=ISN(client)=a。客户端进入SYN_SENT状态。
  2. 第二次握手(SYN + ACK):服务端收到客户端发来的SYN包后,需要确认客户端的SYN包,将确认序号ACK设为客户端的ISN加1(ACK=a+1)作为确认,同时发回包含服务器的初始序号Seq=ISN(server)=b,即SYN+ACK包。服务端进入SYN_RECV状态。
  3. 第三次握手(ACK):客户端收到服务端发来的SYN+ACK包后,将确认序号设为服务端的ISN加1作为确认,向服务端发送确认包(ACK=b+1)。此包发送完毕,客户端与服务端进入ESTABLISHED状态,完成三次握手,建立连接。

【思考】为什么需要三次握手而不是两次握手?

四次挥手

由于TCP连接是全双工的,因此每个方向的连接必须单独地进行关闭,于是TCP连接的断开需要进行“四次挥手”(两端分别进行FIN+ACK和ACK两次挥手)。

TCP连接断开的过程:

  1. 客户端发起请求,向服务端发送一个FIN(Seq=c, ACK=d),用来关闭从客户端到服务端的传输。客户端的状态变为FIN_WAIT_1。此时客户端仍然可以接收数据。如果这之前发出的数据中存在没有ACK的,客户端仍然会重发这些数据。
  2. 服务端收到客户端的FIN包,然后向客户端发回一个ACK包(ACK=c+1)作为确认。
  3. 同时,服务端向客户端发送一个FIN(Seq=d, ACK=c+1),用来关闭从服务端到客户端的传输。服务端的状态变为LAST_ACK。
  4. 客户端收到服务端的FIN包,然后向服务端发回一个ACK包(ACK=d+1)作为确认。四次挥手结束,连接断开(CLOSED)。

注意:TIME_WAIT状态需要经过2MSL(最大报文段生存时间)才能返回到CLOSED状态,原因:

  • TIME_WAIT确保有足够的时间让对端收到了ACK(如果被动关闭的那方没有收到Ack,就会触发被动端重发Fin,一来一去正好2个MSL)
  • 有足够的时间让这个连接不会跟后面的连接混在一起(部分路由器会缓存数据包导致连接重用)

总结

用下面两幅图总结TCP连接的建立与终止:

最后来一张TCP状态转换图,可以很好地概括整个TCP连接的建立和终止的过程及状态的变化。图来自 TCP/IP Illustrated, Volume 1 : The Protocols(2nd Edition)

The TCP state transition diagram


Reference

  • TCP/IP Illustrated, Volume 1 : The Protocols(2nd Edition), Kevin.R.Fall

深入探究 JVM | klass-oop对象模型研究

最近对 JVM 兴趣大增(其实是想回归C艹的怀抱了)~

当我们在写 Java 代码的时候,我们会面对着无数个接口,类,对象和方法。但我们有木有想过,Java 中的这些对象、类和方法,在 HotSpot JVM 中的结构又是怎么样呢?HotSpot JVM 底层都是 C++ 实现的,那么 Java 的对象模型与 C++ 对象模型之间又有什么关系呢?今天就来分析一下 HotSpot JVM 中的对象模型:oop-klass model,它们的源码位于 openjdk-8/openjdk/hotspot/src/share/vm/oops 文件夹内。

注:本文对应的 OpenJDK 版本为 openjdk-8u76-b02。对于不同的版本(openjdk-7, openjdk-8, openjdk-9),其对应的 HotSpot JVM 的对象模型有些许差别(7和8的差别比较大)

oop-klass model 概述

HotSpot JVM 并没有根据 Java 实例对象直接通过虚拟机映射到新建的 C++ 对象,而是设计了一个 oop-klass model。

当时第一次看到 oop,我的第一反应就是 object-oriented programming,其实这里的 oop 指的是 Ordinary Object Pointer(普通对象指针),它用来表示对象的实例信息,看起来像个指针实际上是藏在指针里的对象。而 klass 则包含 元数据和方法信息,用来描述 Java 类。

那么为何要设计这样一个一分为二的对象模型呢?这是因为 HotSopt JVM 的设计者不想让每个对象中都含有一个 vtable(虚函数表),所以就把对象模型拆成 klass 和 oop,其中 oop 中不含有任何虚函数,而 klass 就含有虚函数表,可以进行 method dispatch。这个模型其实是参照的 Strongtalk VM 底层的对象模型。

体系总览

oopsHierarchy.hpp 里定义了 oop 和 klass 各自的体系。

这是oop的体系:

1
2
3
4
5
typedef class oopDesc* oop;
typedef class instanceOopDesc* instanceOop;
typedef class arrayOopDesc* arrayOop;
typedef class objArrayOopDesc* objArrayOop;
typedef class typeArrayOopDesc* typeArrayOop;

注意由于 Java 8 引入了 Metaspace,OpenJDK 1.8 里对象模型的实现与 1.7 有很大的不同。原先存于 PermGen 的数据都移至 Metaspace,因此它们的 C++ 类型都继承于 MetaspaceObj 类(定义见 vm/memory/allocation.hpp),表示元空间的数据。

这是元数据的体系:

1
2
3
4
5
6
7
8
9
10
11
// The metadata hierarchy is separate from the oop hierarchy
// class MetaspaceObj
class ConstMethod;
class ConstantPoolCache;
class MethodData;
// class Metadata
class Method;
class ConstantPool;
// class CHeapObj
class CompiledICHolder;

这是 klass 的体系:

1
2
3
4
5
6
7
8
9
10
// The klass hierarchy is separate from the oop hierarchy.
class Klass;
class InstanceKlass;
class InstanceMirrorKlass;
class InstanceClassLoaderKlass;
class InstanceRefKlass;
class ArrayKlass;
class ObjArrayKlass;
class TypeArrayKlass;

注意 klass 代表元数据,继承自 Metadata 类,因此像 MethodConstantPool 都会以成员变量(或指针)的形式存在于 klass 体系中。

以下是 JDK 1.7 中的类在 JDK 1.8 中的存在形式:

  • klassOop -> Klass*
  • klassKlass 不再需要
  • methodOop -> Method*
  • methodDataOop -> MethodData*
  • constMethodOop -> ConstMethod*
  • constantPoolOop -> ConstantPool*
  • constantPoolCacheOop -> ConstantPoolCache*

klass

一个 Klass 对象代表一个类的元数据(相当于 java.lang.Class 对象)。它提供:

  • language level class object (method dictionary etc.)
  • provide vm dispatch behavior for the object

所有的函数都被整合到一个 C++ 类中。

Klass 对象的继承关系:xxxKlass <:< Klass <:< Metadata <:< MetaspaceObj

klass 对象的布局如下:

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
// Klass layout:
// [C++ vtbl ptr ] (contained in Metadata)
// [layout_helper ]
// [super_check_offset ] for fast subtype checks
// [name ]
// [secondary_super_cache] for fast subtype checks
// [secondary_supers ] array of 2ndary supertypes
// [primary_supers 0]
// [primary_supers 1]
// [primary_supers 2]
// ...
// [primary_supers 7]
// [java_mirror ]
// [super ]
// [subklass ] first subclass
// [next_sibling ] link to chain additional subklasses
// [next_link ]
// [class_loader_data]
// [modifier_flags]
// [access_flags ]
// [last_biased_lock_bulk_revocation_time] (64 bits)
// [prototype_header]
// [biased_lock_revocation_count]
// [_modified_oops]
// [_accumulated_modified_oops]
// [trace_id]

oop

oop 类型其实是 oopDesc*。在 Java 程序运行的过程中,每创建一个新的对象,在 JVM 内部就会相应地创建一个对应类型的 oop 对象。各种 oop 类的共同基类为 oopDesc 类。

在 JVM 内部,一个 Java 对象在内存中的布局可以连续分成两部分:instanceOopDesc 和实例数据。instanceOopDescarrayOopDesc 又称为 对象头

instanceOopDesc 对象头包含两部分信息:Mark Word元数据指针(Klass*):

1
2
3
4
5
volatile markOop _mark;
union _metadata {
Klass* _klass;
narrowKlass _compressed_klass;
} _metadata;

分别来看一下:

  • Mark WordinstanceOopDesc 中的 _mark 成员,允许压缩。它用于存储对象的运行时记录信息,如哈希值、GC 分代年龄(Age)、锁状态标志(偏向锁、轻量级锁、重量级锁)、线程持有的锁、偏向线程 ID、偏向时间戳等。
  • 元数据指针instanceOopDesc 中的 _metadata 成员,它是联合体,可以表示未压缩的 Klass 指针(_klass)和压缩的 Klass 指针。对应的 klass 指针指向一个存储类的元数据的 Klass 对象。

下面我们来分析一下,执行 new A() 的时候,JVM native 层里发生了什么。首先,如果这个类没有被加载过,JVM 就会进行类的加载,并在 JVM 内部创建一个 instanceKlass 对象表示这个类的运行时元数据(相当于 Java 层的 Class 对象)。到初始化的时候(执行 invokespecial A::<init>),JVM 就会创建一个 instanceOopDesc 对象表示这个对象的实例,然后进行 Mark Word 的填充,将元数据指针指向 Klass 对象,并填充实例变量。

根据对 JVM 的理解,我们可以想到,元数据—— instanceKlass 对象会存在元空间(方法区),而对象实例—— instanceOopDesc 会存在 Java 堆。Java 虚拟机栈中会存有这个对象实例的引用。


参考文档

Inside The C++ Object Model 学习笔记(III)

这篇将总结C++的函数语义学相关的内容( Inside The C++ Object Model, Chapter 4 )。

Nonstatic Member Function

非静态成员函数和普通函数的等价形式:

1
2
float compute(const Strategy* sp);
float Strategy::compute() const;

一般来说,非静态成员函数在经过编译时会被转化为非成员函数,转化步骤如下:

  1. 改写函数原型,参数变为this指针。
  2. 将所有成员变量的存取操作都转化为经this指针的操作。
  3. 将此函数重写为一个外部函数并导出,名称进行 Name Mangling。最后函数的调用形式也随之改变:obj.magnitude()转化为类似于magnitude_7Point3dFv(&obj)这种名称

Deep in Virtual Function

单继承下的虚函数

对于普通的类,每个类只含一个虚函数表(vtbl),其中虚函数表记录了基本信息(type_info)及各函数的地址。每个对象在编译时都会被安插虚函数指针(vptr)指向虚函数表。

对于以下类:

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
class Scala {
protected:
int type;
public:
explicit Scala(int type): type(type) {}
virtual ~Scala() {}
virtual void f() = 0; // pure virtual function
virtual int g() {
return this->type;
}
virtual void h() {
std::cout << "FUCK 0" << std::endl;
}
};
class Scalaz : public Scala {
protected:
int s2;
public:
explicit Scalaz(int s2, int type): s2(s2), Scala(type) {}
virtual ~Scalaz() {}
void f() {
std::cout << "Scalaz" << std::endl;
}
void h() {
std::cout << "FUCK => 1" << std::endl;
}
};

其中的Scala类和Scalaz类的模型如下所示:

Object Model

注意:不同的C++编译器对vtable的实现不同,vtbl的初始偏移量可能是0,也可能是-8之类的。如果编译器开启了RTTI,则vtbl里会包含type_info

现在如果调用ptr->g(),我们并不知道ptr所指对象的具体类型,但是有两点很清楚:

  • 无论ptr对应哪种对象,我们总是可以通过ptr找到对应对象的vtable
  • 无论ptr对应哪种对象,g函数的地址总是在slot 3位置

因此此调用可以转化为:(*ptr->vptr[3])(ptr)

用gdb查看运行时的vtbl(命令:i vtbl 对象名):

1
2
3
4
5
6
vtable for 'Scala' @ 0x400d70 (subobject @ 0x603010):
[0]: 0x400bf0 <Scalaz::~Scalaz()>
[1]: 0x400c2a <Scalaz::~Scalaz()>
[2]: 0x400c50 <Scalaz::f()>
[3]: 0x400b7a <Scala::g()>
[4]: 0x400c7a <Scalaz::h()>

纯虚函数为什么等于0

在C++标准中,通过使虚函数=0来定义纯虚函数,其含义是在vtbl对应的地方填上0。关于为什么设计纯虚函数,以及纯虚函数为什么为0, The Design and Evolution of C++ 中的描述是:

The curious =0 syntax was chosen over the obvious alternative of introducing a new keyword pure or abstract because at the time I saw no chance of getting a new keyword accepted. Had I suggested pure, Release 2.0 would have shipped without abstract classes. Given a choice between a nicer syntax and abstract classes, I chose abstract classes. Rather than risking delay and incurring the certain fights over pure, I used the tradition C and C++ convention of using 0 to represent “not there.” The =0 syntax fits with my view that a function body is the initializer for a function also with the (simplistic, but usually adequate) view of the set of virtual functions being implemented as a vector of function pointers.

另外一点:在MSVC中,NULL = 0;而在GCC的实现中,NULL的内部实现是__null而不是0。因此在定义纯虚函数的时候不要用NULL代替0,也不能用C++ 11的nullptr

普通多继承下的虚函数

假设派生类直接继承了n个类,则派生类中就会有n个vptr。多继承下的派生类拥有一个主要的vptr和 n-1 个次要的vptr。多重继承最左端的基类,在派生类中作为主要实体,其对应的vtbl为主要的vtbl

假设现在有下面的类:

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
class Base1 {
public:
explicit Base1() {}
virtual ~Base1() {}
virtual void f() {}
virtual Base1 *clone() const {return ...}
protected:
float b1;
};
class Base2 {
public:
explicit Base2() {}
virtual ~Base2() {}
virtual void g() {}
virtual Base2 *clone() const {return ...}
protected:
float b2;
};
class Derived : public Base1, public Base2 {
public:
explicit Derived() {}
virtual ~Derived() {}
virtual Derived *clone() const {return ...}
protected:
float d;
};

在上面的继承关系中,Base1就作为主要实体。

例如,有以下调用:

1
2
3
4
5
Base1 *b1 = new Derived();
Base2 *b2 = new Derived();
...
delete b1;
delete b2;

这两个指针所指对象对应的vtbl是不同的,里面涉及多继承指针转换的问题:

  • b1不需要调整this指针(最左边的类)
  • b2需要调整this指针

b2来说,构造函数必须调整对象地址,使其指向Base2 sub-object(当然析构函数也是):

1
2
Derived *__temp = new Derived();
Base2 *b2 = __temp ? __temp + sizeof(Base1) : 0;

C++ 11 STL | functional 标准库

最近正好用到了这个,就顺便总结下吧。

C++ 11 引入了函数对象标准库 <functional>,里面包含各种内建的函数对象以及相关的操作函数,非常方便。这里总结一下 std::functionstd::bind 的相关用法。

Callable type

Callable type 指可以像调用函数一样被调用的对象或函数,包括:

  • std::function
  • std::bind
  • std::result_of
  • std::thread::thread
  • std::call_once
  • std::async
  • std::packaged_task
  • std::reference_wrapper

根据 C++ 17 Standard,所有 Callable type 都可以通过 std::invoke 方法进行显式调用

std::function

std::function类模板是一种通用的函数包装器,它可以容纳所有可以调用的对象(Callable),包括 函数函数指针Lambda表达式bind表达式、成员函数及成员变量或者其他函数对象。通过 std::function 可以储存、拷贝或调用 Callable 对象。它的模板参数如下:

1
2
template< class R, class... Args >
class function<R(Args...)>

使用时,模板参数与要存储的函数参数一致即可,下面是一些例子:

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
#include <iostream>
#include <functional>
double f(int x, char y, double z) {
return x + y + z;
}
void print_num(int num) {
std::cout << num << std::endl;
}
struct Dog {
int id;
explicit Dog(int id): id(id) {}
void print_add(int i) const {
std::cout << id + i << std::endl;
}
};
class PrintString {
public:
void operator()(std::string&& s) const {
std::cout << s << std::endl;
}
};
int main(int argc, char **argv) {
// common function
std::function<void(int)> func_display_num = print_num;
func_display_num(9);
// common function
std::function<double(int, char, double)> func_display = f;
std::cout << func_display(3, 'a', 1.7) << "\n";
// lambda expression
std::function<void(const char*)> lbd_dsp_str = [](const char *s) {std::cout << s << std::endl;};
lbd_dsp_str("Scala");
// bind expression
auto func_num_bind = std::bind(&f, std::placeholders::_1, 'c', 2.4);
std::cout << func_num_bind(24) << "\n";
// function object
std::function<void(std::string&&)> func_obj_print = PrintString();
func_obj_print("C++ 17 Nice!");
// member function
const Dog dog(2424);
std::function<void(const Dog&, int)> func_mem_display_num = &Dog::print_add;
func_mem_display_num(dog, 24);
return 0;
}

注意声明时可用auto进行自动类型推导,这样可以节约时间,不过这样会牺牲代码的可读性,因此需要根据情况合理使用auto

std::bind

顾名思义,std::bind函数用来绑定函数的某些参数并生成一个新的function对象。
bind用于实现偏函数(Partial Function),相当于实现了函数式编程中的 Currying(柯里化)。
比如有一函数的定义为:

1
2
3
void func_muti(int a, std::string&& b, const char* c, double d, char e) {
std::cout << a << ", " << b << ", " << c << ", " << d << ", " << e << "\n";
}

现在将此函数的一些参数绑定上值,其余部分用占位符对象(std::placeholders)表示。占位符是有序号的,代表调用此函数对象时参数在参数列表中的位置。比如:

1
2
auto f = std::bind(&func_muti, 24, std::placeholders::_1, "Haha", std::placeholders::_2, 'P');
f("Hehe", 24.24);

调用这个函数对象相当于调用以下函数:

1
2
3
void f(std::string&& b, double d) {
std::cout << "24" << ", " << b << ", " << "Haha" << ", " << d << ", " << 'P' << "\n";
}

Modern C++ | 移动语义与完美转发 | Universal Reference

简单总结一下C++ 11/14中的移动语义和完美转发~

lvalue && rvalue

表达式可以分为lvalue(左值)和rvalue(右值)两种。

左值与右值的区别是左值具名,可以取址 并访问;而右值不具名,通常是临时的变量,不可取址,仅在当前作用域有效,可以被移动。

对于函数及运算符,如果返回类型是左值引用类型(A&),那么返回值是左值;若返回类型是原对象类型(A),那么返回值就是右值。

举一些例子来说明:

1
2
3
4
5
6
7
8
int i = 2;
int a = 0, b = 1;
int *p = new int(24);
std::string str1 = "nice";
std::string str2 = "Scala";
std::vector<int> vec;
vec.push_back(24);
const int& m = 666;
Expression Value category
4 rvalue
i lvalue
a+b rvalue
&a rvalue
*p lvalue
++i lvalue(前缀自增运算符直接在原变量上自增)
i++ rvalue(后缀自增运算符先拷贝一份变量,自增后再重新赋值给原变量)
std::string(“oye”) rvalue
str1+str2 rvalue(重载的+运算符返回的是一个临时的std::string对象而不是引用)
vec[0] lvalue(重载的[]运算符返回类型为int&)
m lvalue(引用了一个右值,但本身是左值)

当然C++中表达式的分类还可以根据是否可移动及是否具名再细分。如果用m表示可移动(movable),用i表示具名(has identity),那么表达式类型可以进一步细分为:

Value categories since C++ 11

根据上面的分类,我们传统意义上讲的lvalue指的是具名并且不可被移动的值,而rvalue指的是可被移动的值。

更详细的信息可参考Value categories

Universal reference

C++ 11中引入了右值引用(rvalue reference)用于表示移动语义(绑定了右值)。在C++ 11中,类型T的右值引用表示为T&&。然而并不是所有的形如T&&的类型都为rvalue reference。形如T&&的类型有两种情况:一种是普通的rvalue reference,另一种则被称为 universal reference,它既可能表示lvalue reference,也可能表示rvalue reference。那么如何区分这两种引用呢?根据 Effective Modern C++, Item 24 总结一下:

  • 如果一个函数模板参数的类型为T&&,其中T是需要推导的类型,那么此处的T&&指代universal reference。若不严格满足T&&类型或没有发生类型推导,则T&&指代rvalue reference。比如下面的param参数即为universal reference:
1
2
template<typename T>
void f(T&& param);

上面有两个要点:类型为T&&和参与类型推导。也就是说T&&加上cv qualifiers就不是universal reference了,比如下面的param参数为rvalue reference而不是universal reference:

1
2
template<typename T>
void f(const T&& param);

另外一点就是要参与类型推导。比如以下vector类中的push_back函数,虽然参数类型为T&&,但是并未参与类型推导。因为vector模板实例化的时候,T的类型是已经推导出来的(如std::vector<T>, T = int),因此参数仍然为rvalue reference:

1
2
3
4
5
6
template<class T, class Allocator = allocator<T>>
class vector {
public:
void push_back(T&& x);
// ...
};

emplace_back模板函数则需要进行类型推导,因此对应的参数Args&&为universal reference(为方便起见,将此处的parameter pack看作是一个type parameter):

1
2
3
4
5
6
7
template<class T, class Allocator = allocator<T>>
class vector {
public:
template <class... Args>
void emplace_back(Args&&... args);
// ...
};
  • 如果一个对象的类型被定义为auto&&,则此对象为universal reference,比如auto&& f = g()

那么如何确定universal reference的引用类型呢?有如下规则:如果universal reference是通过rvalue初始化的,那么它就对应一个rvalue reference;如果universal reference是通过lvalue初始化的,那么它就对应一个lvalue reference。

确定了universal reference的引用类型后,编译器需要推导出T&&中的T的真实类型:若传入的参数是一个左值,则T会被推导为左值引用;而如果传入的参数是一个右值,则T会被推导为原生类型(非引用类型)。这里面会涉及到编译器的 reference collapsing 规则,下面来总结一下。

Reference collapsing

考虑以下代码:

1
2
3
4
5
6
7
class A {};
template<typename T>
void f(T&& param);
A a;
f(a); // T = A&

根据上面总结的规则,T = A&, T&& = A&。然而将T&&展开后我们发现这玩意像是一个reference to reference:

1
void f(A& && param);

如果我们直接表示这样的多层引用,编译器会报错;而这里编译器却允许在一定的情况下进行隐含的多层引用推导,这就是 reference collapsing (引用折叠)。C++中有两种引用(左值引用和右值引用),因此引用折叠就有四种组合。引用折叠的规则:

如果两个引用中至少其中一个引用是左值引用,那么折叠结果就是左值引用;否则折叠结果就是右值引用。

直观表示:

  • T& & = T&
  • T&& & = T&
  • T& && = T&
  • T&& && = T&&

Move semantic

移动语义的意义:资源所有权的转让。即进行数据复制的时候,将动态申请的内存空间的所有权直接转让出去,不用再另开辟空间进行大量的数据拷贝,既节省空间又提高效率。

被移动的数据交出了所有权,为了不出现析构两次同一数据区,要将交出所有权的数据的指向动态申请内存去的指针赋值为nullptr,即空指针。对空指针执行delete[]是合法的。

我们可以用标准库中的std::move函数来表示一个对象可以被移动,即交出资源所有权。它可以将传入的参数转化为右值引用(严格来说应该是xvalue,即具名但可被移动的值)。比如:

1
2
3
4
5
6
7
8
f(int&& a);
f(const int& a);
// ...
int s = 4;
f(s); // invoke f(&)
f(std::move(s));// invoke f(&&)

再比如对于只允许移动的对象(独占资源,如unique_ptr),可以通过std::move与move ctor来转移资源的所有权:

1
2
auto p1 = std::make_unique<std::string>("+1s");
auto p2 = std::move(p1); // p1管理的资源的所有权交给p2

注意std::move的本质,它其实就是一个转换函数,将给定的类型转化为右值引用,而并不是真正地“移动”了资源(组委会一直在吐槽move这个名,应该叫rval比较合适)。我们来看一下其实现(gcc 5.3.0):

1
2
3
4
template<typename _Tp>
constexpr typename std::remove_reference<_Tp>::type&&
move(_Tp&& __t) noexcept
{ return static_cast<typename std::remove_reference<_Tp>::type&&>(__t); }

可以看到,move函数的实现非常简单:通过type_traits中的remove_reference函数清除_Tp类型中的引用,然后再加上&&并转换(此处_Tp&&即为一个universal reference)。

Perfect forwarding

有的时候,我们需要将一个函数某一组参数原封不动地传递给另一个函数。这里不仅需要参数的值不变,而且需要参数的类型属性(左值/右值,cv qualifiers)保持不变,这叫做 Perfect Forwarding(完美转发)。

从C++ 11开始,perfect forwarding可以通过std::forward函数实现,其原型为:

1
2
3
4
5
6
// C++ 14 definition
template< class T >
constexpr T&& forward( typename std::remove_reference<T>::type& t );
template< class T >
constexpr T&& forward( typename std::remove_reference<T>::type&& t );

写个例子,实现C++ 14标准中的make_unique函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <utility>
#include <memory>
class A {
public:
A(int && n) { std::cout << "rvalue constructor -> n=" << n << std::endl;}
A(int& n) { std::cout << "lvalue constructor -> n=" << n << std::endl;}
};
template<class T, class U>
std::unique_ptr<T> make_unique1(U&& u) {
return std::unique_ptr<T>(new T(std::forward<U>(u)));
}
int main() {
int i = 24;
auto p1 = make_unique1<A>(666); // rvalue forwarding
auto p2 = make_unique1<A>(i); // lvalue forwarding
auto p3 = make_unique1<A>(std::move(i)); // rvalue forwarding
return 0;
}

程序运行结果:

1
2
3
rvalue constructor -> n=666
lvalue constructor -> n=24
rvalue constructor -> n=24

可以看到,参数在传递时都保留了参数原本的属性。

看一下forward函数的实现(gcc 5.3.0):

1
2
3
4
5
6
7
8
9
10
11
12
13
template<typename _Tp>
constexpr _Tp&&
forward(typename std::remove_reference<_Tp>::type& __t) noexcept
{ return static_cast<_Tp&&>(__t); }
template<typename _Tp>
constexpr _Tp&&
forward(typename std::remove_reference<_Tp>::type&& __t) noexcept
{
static_assert(!std::is_lvalue_reference<_Tp>::value, "template argument"
" substituting _Tp is an lvalue reference type");
return static_cast<_Tp&&>(__t);
}

可以看到forward函数底层也是利用了type_traits中的remove_reference以及universal reference和reference collapsing。


参考资料