The Semantics of Data

前言

一个类的大小主要受三个因素影响：

• 语言本身带来的额外负担。比如如果是virtual base class，往往需要一个指针去指向某个virtual base class subobject；

• 编译器的特殊处理。比如有些编译器会为一个空类（继承自另外一个空类）添加1个byte，但有些编译器会做出优化；

• alignment。对齐；

另外需要注意的是，nonstatic data members也是放在类对象中，即使是继承而来的nonstatic data members也是一样，但static data members则放在程序的一个global data segment中

Data Member Layout

非静态成员变量在类的对象中的排列顺序与其声明顺序是一致的。

如果多个数据成员分布在不同的access session（public，private，protected）中，那么members的排列应该满足：较晚出现的成员应该在高地址，并且允许将多个access session连锁在一起，成为一个连续的区块，也就是你在一个session内声明8个变量，和在8个相同的session内声明8个变量对于内存布局是一样。

Data Member的存取

先抛出一个问题：

1
2
3

Point3d origin, *pt = &origin;
origin.x = 0.0;
pt->x = 0.0;

分别通过指针和对象去读取，会有什么不同呢？

Static Data Members

如果是以这两种方式去读取静态成员，那么是一样的。因为都会转化成对唯一的实体进行直接操作，例如：

1
2
3
4
5

//origin.chunkSize == 250;
Point3d::chunkSize == 250;

//pt->chunkSize == 250;
Point3d::chunkSize == 250;

由于静态数据成员是放在全局数据区，如果有两个类声明同名的静态数据成员，编译器会为每一个static data member进行唯一编码。

Nonstatic Data Members

这里需要注意的是，对一个非静态成员进行存取，编译器会通过把一个class object的起始地址加上data member的偏移量进行存取。

这里，如果是通过对象去存取成员变量，成员变量的偏移量会在编译时就已经得知，效率较高；

而如果一个类是派生类，其通过指针去存取它的成员变量，我们无法得知指针指向哪个class type，必须要等到运行时才确定下来，同时还要经历额外的间接导引才能找到那个数据成员。

继承与Data Members

考虑两个类Point2d, Point3d，如果一种组织方式是形成两个独立的类，另外一种的组织方式是形成继承链。那么会有声明不同。

Inheritance without Polymorphism

假如我们考虑Point3d继承自Point2d，但其中没有virtual functions，也就没有了额外的空间负担（vptr）。

但这种做法会带来的一个错误是，把一个class分解为多层，可能会带来的一个问题是抽象的结构会变得膨胀。例如：

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

class Concrete {
public:
    //...
private:
    int val;
    char c1;
    char c2;
    char c3;
};

//分解成
class Concrete1 {
public:
    //...
private:
    char c1;
};

class Concrete2: public Concrete1 {
public:
    //...
private:
    char c2;
};

class Concrete1: public Concrete3 {
public:
    //...
private:
    char c3;
};

32位的机器下，对于第一种不分解的情况，类的空间大小为8bytes，而第二种情况，Concrete3变成了16bytes，因为自定义的数据类型是在继承得来的subject的padding后面进行补全的。所以就浪费了更多的padding空间。

另外一个容易出现的问题是，考虑这种情况：

1
2
3
4
5
6

Concrete2 *pc2;
Concrete1 *pc1_1, *pc1_2;
pc1_1 = pc2;//另pc1_1指向Concrete2对象

//结果就是pc1_2指向的对象的成员变量可能会产生异常值
*pc1_2 = *pc1_1;

由于内存布局的不同，直接的复制操作执行的可能是复制一个一个的member，因此有可能会把原来的padding给覆盖掉。具体得看编译器如何实现，是把数据成员与concrete1的subject捆绑在一起，还是其它的实现。

Adding Polymorphism

如果继承链条（考虑一个point3d继承自point2d）中有虚函数，那么会带来如下的额外负担：

• point2d会有一个相关联的virtual table，存放这每一个virtual function的地址，则table的元素数目与virtual function的数目相同，另外可能还有一些slots，用以支持run time identification

• 为每一个class object提供一个vptr，在运行时能够找到virtual table的位置

• 扩充constructor，使得其能够初始化vptr

• 扩充destructor，能够摸消指向class相关的virtual table的vptr

关于vptr放在class object的位置有两种做法，一种是放在末端，为的是保留base class C struct的布局；另一种做法则是放在前端，带来的好处是不用在运行期测量出vptr的偏移量

Multiple Inheritance

对于多重继承，如果想要用父类的指针指向一个对象，那么在内存布局和指针的设置上会有更复杂的操作。

假如是这样的继承状态

其对象模型会有比较大的不同，与单一继承相比

这是因为，如果只是将地址赋予第一个base class会比较简单，和单一继承一样。因为两者指向相同的地址；如果是赋予第二个或者后续的base class的话，就需要修改地址，加上偏移位置。

Virtual Inheritance

虚拟继承的目的就是为了解决如何在派生类里维护一份基类的实体。

对于这样含有多个base class subject的类，会被分割为2个部分：不变局部和共享局部。由于共享局部拥有稳定的offset，可以直接存取；而对于共享局部，由于其位置会随着派生而变化，所以如何进行存取这部分的内容就成了一个难点。

一般来说，会先安排好不变局部，再去建立共享局部。而且编译器会在每一个派生类对象中安插指针,指向virtual base class。

这样就是通过派生类里面的指针去间接的索引共享部分的数据，但有所不同的是，有些编译器会优化使得存取时间和空间负担变得固定。

#基本UDP套接字编程

概述

与TCP不一样，UDP是无连接不可靠的数据报协议。在有些应用程序上会用到UDP，比如DNS, NFS, SNMP。

由于UDP不等待连接，所以客户端只管调用sendto函数，而服务端也只管调用recvfrom函数。

recvfrom和sendto函数

1
2
3

ssize_t recvfrom(int sockfd, void *buff, size_t nbytes, int flags, struct sockaddr *from, socklen_t *addrlen);

ssize_t sendto(int sockfd, const void *buff, size_t nbytes, int flags, const struct sockaddr *to, socklen_t addrlen);

在UDP的情况下，写一个长度为0的数据报是可行的，那样会形成一个包含一个IP首部和一个8字节的UDP首部而没有数据的IP数据报。这也意味着，与TCP不同的是，UDP中recvfrom返回0是可以接受的。

验证接收到的响应

由于recvfrom中最后两个参数是关于数据来源的地址等信息，如果设置为0则意味着我们忽略了该信息，但这样会带来的一个问题是，这就意味着任何一个端都可以给该客户端发送信息。

因此往往，我们需要验证接收到的响应

服务器未运行

考虑这样的情况，在服务端没有启动的情况下，启用客户端：

这种情况下，会返回一个ICMP的错误，并且是异步的。为什么要异步，因为如果一个客户端连续向三个服务端发送数据报，但其中一个对端的服务端没有开启，这种情况下，UDP还能继续工作。

但也要考虑到的一个问题是，这样我们如何区分是哪个服务端没有开启，但errno只有一个，不能区分是哪个IP地址和目的端口号。因此会有这样的规则，仅仅在进程将其UDP套接字连接到恰恰一个对端的的时候，这些异步错误才会返回进程。

小结

客户端在使用sendto时必须指定服务器的ip地址和端口号，但自身的ip地址和端口号则可以由内核自动选择，当然客户端也可以使用bind来指定它们。另外在内核指定的情况下，端口号是固定不变的，而ip地址则可能随着发送数据报的改变而改变。

如果我们使用了bind，但内核决定从另外一个数据链路发出，那么ip数据包仍然包含我们使用bind指定的ip地址，但是实际发送的链路ip地址即便不一样也无所谓。

UDP的connect函数

之前我们提到过，除非UDP的套接字已连接，否则异步错误是不会返回到UDP的套接字的。

我们可以在UDP的套接字上使用connect，但与TCP不同的是，这里没有三次握手的过程，只是检测是否存在立即可以感知的错误，记录对端的IP地址和端口号，并返回调用进程。

对于使用了connect的UDP套接字，接受和发送数据不能再使用sendto和recvfrom，而是read、write等。一个以连接的套接字仅仅与一个IP地址交换数据报。

给一个UDP套接字多次使用connect

这样做有两个目的：

• 指定新的IP地址和端口号;
• 断开连接，通过把套接字地址结构的的地址族成员设置为AF_UNSPEC即可；

性能

在一个未连接的套接字上调用sendto，会进行以下的步骤：

• 连接套接字；
• 输出第一个数据报；
• 断开套接字连接；
• 连接套接字；
• 输出第二个数据报；
• 断开套接字连接；

而如果使用了connect之后再调用两次write：

• 连接套接字；
• 输出第一个数据报；
• 输出第二个数据报；

UDP套接字接收缓冲区

由UDP给某个特定的套接字排队的UDP数据报数目受限于该套接字接收缓冲区的大小。如果我们要改变其缓冲区大小，可以使用SO_RCVBUF进行修改；

Member Initialization List

在使用构造函数的时候，你可以用两种方式来设定成员变量的初始值。要么使用initialization list，要么在构造函数内部进行构造。

首先说明，在以下的情形必须使用初始化列表：

• 初始化一个引用变量
• 初始化一个常量
• 调用基类的constructor，并且它拥有一组参数
• 调用成员类对象的constructor，并且它拥有一组参数

如果是在构造函数体内进行初始化，如下：

1
2
3
4
5
6
7
8
9

class Word {
    string _name;
    int _cnt;
public:
    Word() {
        _name = 0;
        _cnt = 0;
    }
}

它会被编译后修改为：

1
2
3
4
5
6
7

Word::Word() {
    _name.string::string();
    string tmp = string(0);
    _name.string::operator(temp);
    temp.string::~string();
    _cnt = 0;
}

也就是会定义了一个临时值，降低了效率。

然而如果是用的初始化列表：

1
2
3
4
5
6
7
8
9
10
11

Word::Word: _name(0){
    _cnt = 0;
}

//会被扩张成

Word::Word()
{
    _name.string::string(0);
    _cnt = 0;
}

编译器的操作

编译器会按照声明顺序一一地执行initialization list，在constructor安插初始化的操作。

注意是按照声明的顺序，例如以下的情况会出问题：

1
2
3
4
5
6

class X {
    int i;
    int j;
public:
    X(int val):j(val), i(j){...}
}

由于i先初始化，但j还没初始化，这样就会出现无法预知的值。

因此，可以这样设置：

1
2
3

X::X(int val):j(val){
    i = j;
}

因为initialization list的初始化操作，编译器会将初始化操作安插在explicit user assignment的操作之前。

调用member function设置初始值

考虑这样的例子：

1

X::X(int val): i(xfoo(val)), j(val){}

在这种情况下不会有问题，因为this指针已经构建号，代码会被扩张成：

1
2
3
4

X::X(int val){
    i = this->xfoo(val);
    j = i;
}

Implementation of Lexical Analysis

Regular languages

• Epsilon: a simple string namely the empty string
• Union: A+B == {a|a属于A} U {b|b属于B}
• Concatenation: AB = {ab|a属于A ^ b属于B}
• Iteration: A* = A...A(0次或多次)

正则表达式可能有多个表示方式

Formal languages

alphabet 表示一系列的字符，adcii码

meaning function L : maps syntax to semantics，将表达式映射到字符串的集合。比如：

L(epison) = {""} L('c') = {"c"} L(A+B) = L(A) U L(B)

Reason for meaning function：有时候一个semantics可以用多个syntax表示，可能是多对一的映射关系。用于不会有一对多的关系。

lexical specification

• letter = [a-zA-Z]
• keyword = 'if'+'else'+..
• digit = '0'+'1'+'2'+'3'+'4'+'5'+'6'+'7'+'8'+'9'
• Integer = digit digit* = digit+
• Identifier = letter(letter+digit)*
• whitespace(blanks/newlines/tabs) = (' '+''+')+

考虑如何匹配一个邮箱地址：anyone@cs.stanford.edu(考虑前面只由字母组成)

• 得到这样的正则表达式：letter+ '@' letter+ '.' letter+ '.' letter+

注意:

• union = A|B = A+B
• option: A+ ε = A?
• range: 'a'+'b'+...+'z' = [a-z]
• Excluded range: complement of [a-z] = [^a-z]

正则表达式可以描述很多语言，是一种语言的说明。

如何进行正则表达式的匹配

1. Write a rexp for the lexemes of each token

• number = digit*
• keyword = 'if'+'else'+..
• Identifier = letter(letter+digit)*
• OpenPar = '('

2. Construct R

R = keyword + Identifier + Number + ...

3. Let input be X1..Xn

For i<=i<=n check x1..xi 属于L(R)

4. if success, x1..xi属于L(Ri)

5. remove x1...xi

Question:

• How much input is used?

最长匹配原则，如果有两个字符串都符合正则表达式的话。

• which token is used?

x1..xi 属于L(R); R = R1+R2...Rn。

如果有x1...xi属于L(Ri),也有x1...xi属于L(Rj),那么采用priority choose。例如if应该是keyword，不是identifier。

Finite Automa

• Regular expressions = specification
• Finite automata = implementation

consists of:

• input alphabet

• a set of states

• a start state

• a set of accepting states

• a set of transitions:

from state1, inpute a, go to state2;

如果输入完之后还处于接收状态，就接收；

否则，就拒绝：处于结束状态（terminate states，no transitions）；遇到错误匹配

Regular Expressions to NFAS

Lexical Specification-> Regular expressions-> NFA-> DFA-> Table-driven Implementation of DFA

对于NFA，每个notation的图表示与正则表达式相对应，比如正则表达式的epsilon就与开始状态，接收一个epsilon，到达的结束状态的图表示相对应。比如AB，就是状态A接收一个epsilon到达状态B。

我觉得在这种情况下，AB中的A或者B用状态机来表示比较恰当。假如A是一个组合状态，就递归进去解析，直到得到最终的单元的notation。

NFA to DFA

假如在NFA中，由B分别经过epsilon可以到达B和C，那么可以说：

epsilon-closure(B) = {B, C, D}，就是仅仅经过epsilon，迭代可以到达的状态

对于NFA来说，在不同的时间NFA可能处于多个状态，a(X) = {y|x属于X and x->(a)y}表示a应用于X后到达Y

• 定义DFA

states: subset of S(all states in NFA)

start: epsilon-closure(s)

final: {X|x与NFA中final states的交集不等于空集的集合},也就是到达的状态中包含了NFA中的final states，就意味着这是DFA中的final states

transitions: X->(a)Y, if y == epsilon-closure(a(X))

implementing finite automata

由DFA组织一个表，有多少种状态就多少行，有多少种输入就多少列，表示出每种状态在不同输入的情况下到达的状态。

所以，匹配流程如下：

1
2
3
4
5

i = 0
state = 0
while(input[i]) {
    state = A[state, input[i++]]
}

DFA: faster, less compact

NFA: slower, more compact

提醒

本章内容仅本人所理解，不供参考

套接字选项

getsockopt和setsockopt函数

1
2
3
4

#include<sys/socket.h>
int getsockopt(int sockfd, int level, int optname, void *optval, socklen_t *optlen);

int setsockopt(int sockfd, int level, int optname, const void *optval, socklen_t oplen);

getsockopt从optval获取目前的选项设置值，setsockopt则是从optval获得选项待设置的新值

常用套接字选项

SO_KEEPALIVE

在设置keep-alive选项之后，如果套接字的任何一方向上都没有数据交换，TCP会自动向对端发送一个自动探测的分节，这是一个对端必须响应的分节。它会导致以下三种情况：

• 对端响应期望的ACK;
• 对端以RST响应，表明对端已经崩溃且重启，套接字的错误被设置为ECONNRESET，套接字关闭；
• 对端没有响应；TCP将会发送8个探测分节，两两相隔75s，如果还是没有响应，则关闭；

SO_RCVBUF和SO_SNDBUF

每个套接字都会有一个发送缓冲区和接收缓冲区，这两个套接字选项就是用来改变缓冲区的默认大小。

由于TCP的窗口规模是在建立连接时，通过SYN分节与对端交换得到的。所以对于客户，必须在调用connect之前调用；对于服务端，必须在listen之前调用。

SO_REUSEADDR

这个套接字选项有4个不同的作用：

1. 设置这个选项允许启动一个监听服务器并捆绑其众所周知的端口，即便以前建立的用作该端口作为本地端口的连接仍然存在。

考虑这样的条件

• 启动监听服务器；
• 连接请求到达，派生一个子进程提供服务；
• 监听服务器终止，但子进程仍然在服务着；
• 重启监听服务器；

因为如果不设置该选项，那重启监听服务器时将不能捆绑之前那个端口。

2. 允许在同一个端口上启动同一个服务器的多个实例。

3. 允许单个进程捆绑同一个端口到多个套接字上，只要每次捆绑指定不同的地址即可。这种情况发生希望在一个多目的主机的若干个本地地址上服务连接的TCP服务器进程上。

4. 完全重复的捆绑，包括IP地址和端口，一般用于支持UDP。

fcntl函数

1
2

#include <fcntl.h>
int fcntl(int fd, int cmd, .../*int arg*/);

这个函数的目的是执行各种描述符的控制操作，如设置非阻塞式I/O，信号驱动式I/O等等。

开启阻塞式I/O：

1
2
3
4
5
6

int flags;
if((flags=fcntl(fd, F_GETFL, 0)) < 0)
    err_sys("F_GETEL error");
flag |= O_NONBLOCK;
if (fcntl(fd, F_SETEL, flags) < 0)
    err_sys("F_SETEL error");

Program Transformation Semantics

明确的初始化

考虑这样的显式定义：

1
2
3
4
5
6
7
8

X x0;

void foo_bar()
{
    X x1(x0);
    X x2 = x0;
    X x3 = X(x0);
}

这里的定义会分两个阶段进行：重写定义和安插copy constructor。如下：

1
2
3
4
5
6
7
8
9
10
11

void foo_bar()
{
    X x1;
    X x2;
    X x3;

    //安插代码
    x1.X::X(x0);
    x2.X::X(x0);
    x3.X:;X(x0);
}

参数的初始化

C++标准中要求的是，当把一个class object当做参数传入函数或者作为返回值时，会这样初始化：

1
2
3
4
5
6

X xx = arg;//arg是实参

void foo(X x0);

X xx;
foo(xx);

而编译器的优化技术有两种方法，一个是采用临时值，然后修改foo函数；另一个方法就是采用copy contruct的方式把实参直接构建在应该的位置上。

对于第一个方法，如下：

1
2
3
4
5
6
7
8
9

//产生临时对象

X _temp0;
_temp0.X::X(x0);

foo(_temp0);

//修改foo函数，变成穿引用
void foo(X &x0);

返回值的初始化

考虑这样的函数定义：

1
2
3
4
5
6

X bar()
{
    X xx;
    //...
    return xx
}

那么，这个局部对象是如何返回的呢？编译器采用的是双阶段的转化.

• 首先是添加一个引用参数，作为返回值；
• 在return之前安插copy constructor的操作，以便将要传回的object作为初始值；

修改的代码如下：

1
2
3
4
5
6
7
8

void bar(X &__result)//额外参数
{
    X xx;
    xx.X:XX();

    __result.X::X(xx);
    return;
}

摘要

由于copy constructor的应用,编译器会对代码进行一定程度的优化。尤其是当函数以穿值的方式传回一个object时,编译器会对copy constructor进行优化,以一个额外的第一参数取代NRV。

链接

链接可以在编译时，也可以是在加载时，更可以在链接时。由于链接器的出现，使得分离编译成为了可能，也就是每次只要修改某个模块的代码就可以重新链接应用，不用重新编译其它代码。

编译器驱动程序

假如有两个源文件：main.c和sum.c

那么要通过这两个源程序生成可执行文件，要经过这些步骤：预处理——编译——汇编——链接。

以main.c为例，预处理器会将main.c翻译成一个ascii码的中间文件mian.i。接着运行编译器，生成main.s的汇编语言文件。然后是运行汇编器，将汇编语言翻译成二进制的可重定位目标文件main.o。最后与经过同样步骤生成的sum.o进链接，生成可执行的目标文件。

当shell要执行文件时，shell会调用一个loader的函数，将代码和数据复制到内存，然后将控制权移动到程序的开头。

静态链接

Linux的linker以一组可重定位的目标文件和命令行参数，生成一个可执行文件，这就叫静态链接。

链接器的两个功能：

• 符号解析：每个符号对应于一个函数，一个全局变量或是一个静态变量；
• 重定位：由于汇编器和编译器生成的代码都是从0地址开始的，链接器需要将原地址映射到真事的内存位置；

目标文件

三种目标文件：

• 可重定位目标文件：可与其它的可重定位目标文件进行链接，生成可执行的目标文件；
• 可执行的目标文件：能直接复制进内存并执行；
• 共享目标文件：特殊的可重定位目标文件，能够动态地进行链接；

可重定位目标文件

首先来看这种类型的文件具体表示

我们逐个section来看：

• .text：已经编译程序的机器代码；
• .rodata：只可以读的数据；
• .data：已经初始化的全局和静态变量；
• .bss：未初始化的全局和静态变量；
• .symtab：符号表，存放在程序中函数和全局变量的信息；
• .rel.text：一个.text节中位置的列表，当与其他文件合并时需要修改；
• .rel.data：被模块引用或者定义的所有全局变量的重定位信息；
• .debug：一个调试符号表；
• .line：源文件的行号与.text杰中机器指令之间的映射；
• .strtab：字符串表；

符号与符号表

每个可重定位目标文件的模块都会有一个符号表，里面存着本模块定义或者从外部引用的符号，主要分为三类：

• 由本模块定义并被其它模块引用的全局符号，对应于非静态的全局变量和C函数；
• 由其它模块定义的并被模块引用的全局符号，对应于在其它模块定义的非静态的全局变量和C函数；
• 只被本模块定义和引用的符号，对应于带static属性的的全局变量和C函数；

通常情况，利用static属性可以隐藏变量和函数名字，保证只能被本模块使用；

符号解析

链接器符号解析的方法就是将输入的引用与符号表中一个确定的符号定义关联起来。

对于局部静态变量，会有一个本地链接器，确保它们有唯一的名字。

至于全局符号会比较麻烦，有可能抛出错误，也可能通过某个规则选择某个定义。

对于C++和Java的重载而言，编译器会将每个唯一的函数名和参数列表组合编码成对于链接器唯一的符号，这叫mangling。

如何解析多重定义的全局符号

我们先来区分两种类型的符号：强类型和弱类型。这是由编译器输出到链接器的，函数和已经初始化的全局变量是强符号，未初始化的全局变量是弱符号。

如何处理多重定义的符号名：

• 规则1：不允许有同名的强符号；
• 规则2：如果有1个强符号和多个弱符号同名；
• 规则3：如果有多个弱符号同名，那么可以从这些弱符号中任意选择一个；

来看规则2：

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

/*foo2.c*/
#include <stdio.h>
void f();
int x = 15213;

int main()
{
    f();
    printf("%d\n", x);
    return 0;
}

/*bar2.c*/
int x;

void f()
{
    x = 15213;
}

linux> gcc -o foobar2 foo2.c bar2.c
linux> ./foobar2
15213

再来看规则3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/*foo2.c*/
#include <stdio.h>
void f();
int x;

int main()
{
    x = 15213;
    f();
    printf("%d\n", x);
    return 0;
}

/*bar2.c*/
int x;

void f()
{
    x = 15212;
}

linux> gcc -o foobar2 foo2.c bar2.c
linux> ./foobar2
15213

与静态库链接

静态库：将所有相关的目标文件模块打包成一个单独的可执行文件，它可以作为链接器的输入。这种做法的好处就是只复制静态库里被应用程序引用的目标模块。

例如：libm.a库中定义了一组浮点函数，sin, cos和sqrt；

在Linux系统中，静态库以一种称为存档（archive）的特殊文件格式存放在磁盘中，是一组连接起来的可重定位目标文件的集合。以后缀.a标识。

举个与静态库连接的例子：

创建一个静态库的方法：

1
2
3
4
5
6

linux> gcc -c addvec.c multvec.c
linux> ar rcs libvector.a addvec.o multvec.o

创建可执行文件
linux> gcc -c main2.c
linux> gcc -static -o prog2c main2.o ./libvector.a

如何使用静态库来解析引用

在符号解析阶段，链接器从左到右按照它们在编译器驱动程序命令上的顺序来扫描可重定位目标文件和存档文件。shell会自动将.c文件翻译成.o文件。

对于每个被存档文件的成员外部引用的符号s，在命令行中至少有一个s的定义是在对s的引用之后的。

假如依赖关系如下：p.o->libx.a->liby.a且liby.a->libx.a->p.o

那么编译命令应该为：gcc p.c libx.a liby.a libx.a

重定位

链接器进行符号解析之后，就要进行重定位了。重定位操作把输入模块进行合并，并且为每个符号分配运行时的地址。主要分为两步：

• 重定位节和符号定义：把相同类型的节合并成一个节；
• 重定位节中的符号引用：修改代码节和数据节中对每个符号的引用，使其指向正确的运行时地址；

重定位条目

由于汇编器有可能会遇到不知道数据和代码的内存位置的情况，因此会把信息存储在重定位条目，即代码的重定位条目在.rel.text中，数据的重定位条目在.rel.data中。

ELF有基本的两种重定位类型：R_X86_64_PC32（相对地址），R_X86_64_32（绝对地址）

重定位符号引用

迭代地在每个节和每个节相关联的重定位条目执行重定位：

可执行目标文件

文件格式

ELF头会描述文件的总体格式，还会有一个程序的入口点。.init节中有一个_init的函数来初始化代码。

可执行的目标文件可以轻易加载到内存，并且文件的连续的chunk与内存段有着直接的映射。

加载可执行目标文件

运行命令

1

linux> ./prog

因为prog不是一个内置的命令，所以shell会调用loader去加载运行它，loader将可执行文件的代码和数据从磁盘复制到内存，然后跳转到程序的第一条指令或入口点来运行该程序。

内存映像如下：

动态链接共享库

静态链接库的问题是，运行时调用的库函数会被复制到每个运行进程的文本段里面，这里带来的问题就是对内存造成了浪费。

而共享库可以解决这个问题，共享库是一个目标模块，在运行时会加载到任意的内存地址，并和一个在内存的程序链接起来，这是由动态链接器完成的。

一个库只有一个.so文件，所有引用该库的可执行目标文件共享这个.so文件的代码和数据，而不是像静态文件那样复制嵌入到它们的可执行文件里面去。

执行指令：

1
2

linux> gcc -shared -fpic -o libvector.so addvec.c multvec.c
linux> gcc -o prog21 main.c ./libvector.so

这里进行了两次链接，先是静态执行一些链接，复制一些重定位和符号表信息；然后是动态链接，但.so文件的代码和数据是不会被复制到可执行文件里的。

I/O复用：select和poll函数

概述

IO复用：一旦一个或者多个IO条件就绪了，内核就会通知进程

应用场景：

• 当客户处理多个描述符，例如交互输入和网络套接字
• 一个客户处理多个套接字
• 服务器既要处理监听套接字，又要处理已连接套接字
• 服务器既要处理TCP，又要处理UDP
• 服务器处理多个服务或者多个协议

I/O模型

阻塞型I/O；非阻塞型I/O；I/O复用；信号驱动式I/O；异步I/O

套接字上的输入分为两步：首先是等待数据从网络中到达。到达后会先将数据复制到内核缓冲区，接着复制到应用进程缓冲区。

阻塞式I/O模型

进程在调用recvfrom()之后，一直阻塞直到数据复制到应用进程缓冲区或者返回错误

非阻塞式I/O模型

应用进程持续的轮询，查看操作是否就绪。如果没有就绪就会返回一个错误。这种做法会耗费大量的CPU时间

I/O复用模型

对于这种模型，我们可以使用select或者poll来完成我们的需求。通过select这个系统调用（阻塞于此），让内核在IO就绪的情况下通知应用进程，然后应用进程再调用recvfrom。这里使用了两个系统调用，但好处是可以等待多个描述符就绪。

信号驱动式I/O

对于这种模型，首先是安装一个信号驱动函数，并马上返回。在内核发现描述符就绪后，通过信号通知应用进程。这样，在等待数据到达的期间进程不会被阻塞。

异步I/O

这种模型比之信号驱动式I/O更绝，它是内核完成IO操作之后才会通知应用进程

前面四种模型都是同步I/O模型，因为进程都会因为IO请求而阻塞，知道IO操作完成

select函数

先来看函数原型：

1
2
3
4

#include <sys/select.h>
#include <sys/time.h>

int select(int maxfdpl, fd_set *readset, fd_set *writeset, fd_set *exceptest, const struct timeval *timeout);

对于最后一个函数，这是一个时间参数，控制的是在内核等待操作就绪需要花费多少时间：

• 永远等待，直到有一个描述符就绪。设置为NULL
• 等待一定的时间，在时间范围内直到有一个描述符就绪
• 不等待，轮询，马上返回

至于中间三个参数：readset，writeset，exceptest。控制的是内核需要测试哪些描述符的读写，异常操作。

注意的是，fd_set是一个描述符集，通常是一个整数数组。每个元素是32位，每一个位对应的是一个描述符，其中第一个元素对应的是描述符0-31，第二个元素对应的是32-63。例如，3对应的就是描述符123。通过某些宏定义的操作可以设置需要检查的描述符。

另外就是，由于这里传入的指针会被修改，也就是作为值——结果返回。通过调用select之后检查指针的值就知道哪些bit修改了，也就是描述符的操作就绪了。也因此，每次调用select都要重新设置。

第一个参数就是待测试的最大描述符+1，也就是测试的描述符个数。

描述符就绪条件

shutdown函数

1
2

#include <sys/socket.h>
int shutdown(int sockfd, int howto);

• 与close函数相比，shutdown函数不需理会引用计数是否为0，它可以直接激发TCP的正常连接终止；
• 另外，close终止的是读与写两个方向的数据传送，而shutdown函数则是告诉对端我们已经完成了数据传送，即使对端仍有数据发送。

也就是shutdown函数的调用会关闭一半的TCP连接。

poll函数

1
2

#include <poll.h>
int poll(struct pollfd *fdarray, unsigned long nfds, int timeout);

poll函数与select类似，但它能提供额外的信息，而且用的不是值——结果参数。

注意第一个参数，fdarray是这样的一个结果体指针：

1
2
3
4
5

struct pollfd {
    int fd;
    short events;
    short revents;
}

需要测试的条件由events指定，函数会在revents成员中返回描述符的测试结果。具体表现如下图：

从这个表可以看到，我们可以测试读写和异常三种操作，另外还能识别三类数据：普通数据，优先级带，高优先级带。至于怎么区分这些数据的类型，就有些争议了，这里就不写了。

timeout参数跟select的类似，也是指定poll函数返回前等待多长时间。

• INFTIM：永远等待
• 0：立即返回，不阻塞进程

• 0：等待指定的时间

TCP客户/服务器程序

POSIX信号处理

信号：告知某个进程发生了某个事件的通知。由于信号是异步的，也就是进程无法得知信号发生的准确时间；

两个传播路径：

• 由一个进程发给另外一个进程（或自身）；
• 由内核发给某个进程；

函数声明：

1
2
3

#include <signal.h>

void (*signal(int signo, void (*func)(int)))(int);

POSIX的信号处理：

1. 一旦安装了信号处理函数，它便一直安装着；
2. 在一个信号处理函数运行期间，正在被递交的信号是阻塞的；
3. 如果一个信号在被阻塞期间产生了多次，那么信号不在阻塞之后只会被递交一次，也就是不进行队列排序；

Zombie进程

设置僵死(zombie)进程的一个目的就是维护子进程的信息，以便父进程在未来要使用的时候能获取诸如子进程的ID，进程终止状态和资源利用信息。

由于僵死进程会占用内核空间，因此我们通常利用函数wait或者waitpid来防止其变成僵死进程。

wait和waitpid函数

1
2

pid_t wait(int *staloc);
pid_t waitpid(pid_t pid, int *staloc, int options);

比较：

进程在调用wait之后，如果没有已终止的子进程，它会一直阻塞，直到现有的子进程第一个终止为止。

而对于waitpid来说，它在阻塞非阻塞方面有更多的控制权，首先是pid能指定等待的进程pid，options则是附加选项，设置为WNOHANG则可以告诉内核在没有子进程完成时不要阻塞。

accept返回前连接中止

在三次握手建立之后，客户端的TCP却发来了一个RST。那么一般来说，服务器端的accept函数将会返回一个错误。

服务器进程终止

假设我们在两端建立起连接之后，杀死了服务器端的进程。那么服务器端会向客户端发去一个FIN，而如果此时客户端阻塞于fgets，当我们在客户端输入要发送的内容之后，客户端仍然照常将数据发去服务端。

由于服务端的进程已经关闭了，所以服务端会响应一个RST。然而此时客户端还看不到RST，而是接受FIN，也就是在read中返回0，由于不像预期那样接收到EOF，所以客户端会因为出错而退出。

SIGPIPE

还是上面的那个情况，如果我们不是执行一次写操作，而是在读回数据之前执行两次写操作，那么会引发EPIPE错误。这是因为第一次的写操作会导致RST的接收，而第二次向接收到RST的套接字进行写操作是不允许的，因此返回了错误。

服务器主机崩溃后重启

假设客户端发送数据前，重启处于崩溃状态的服务器，那么由于服务器已经丢失了之前的连接信息，所以会响应一个RST。

Hashtable

三种解决冲突的方法

• 线性探测：当hash之后遇到冲突了，就在下一个位置进行寻找。问题是会遇到聚集。

• 二次探测：原先遇到冲突，在寻找下一个空位时是按照这样的顺序：H+1,H+2...H+n;而二次探测则是：H+1^2,H+22...H+n^2。

• 开链：在每个槽中维持一个链表，hash到同一个槽时就插入链表中。SGI的stl就是用这种方式。但hashtable维持的链不是stl的list，而是自行维护的__hashtable_node

hashtable的迭代器

迭代器的前进操作是从当前节点出发，前进一个位置，如果目前节点恰好是list的尾端，就进入下一个buckets内。注意，hashtable没有后退操作。

hashtable的数据结构

默认使用std::alloc。

1
2
3

template <class Value, class Key, class HashFun, 
            class ExtractKey, class EqualKey, class Alloc = alloc>
class hashtable{}

虽然使用开链法不需要指定table的大小为质数，但SGI stl还是使用了质数。做法就是提供一个函数用以查询最接近于某数n,但大于某数n的质数。

hashtable的构造与内存管理

由这一段代码可知，加入我们需要50个节点，它会返回53个节点（质数）：

1
2
3
4
5

void initialize_buckets(size_type n)
{
    const size_type n_buckets = next_size(n);
    ...
}

进行插入操作时，会判断是否需要重建（resize）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

...::resize(size_type num_elementsz_hint)
{
    //比较新老的size
    const size_type old_n = buckets.size();
    if (num_elementsz_hint > old_n) { //如果新的size比较大
        const size_type n = next_size(num_elementsz_hint);
        if (n > old_n) {
            vector<node*, A> tmp(n, (node*) 0);
            //处理每一个旧的buckets
            //首先是获取bucket的起始节点
            //迭代地将每个节点插在tmp（也就是新的buckets）的起始位置
        }
    }
}

hashfunction

在使用hashfunction时，SGI将其封装成bkt_num()，再由它来调用hash function。通常来说，stl只对char,long,int,short等进行处理。如果要处理其它类型的，必须要提供hashfunction，比如hash