猫猫攻城狮的博客
0%

Posted on Edited on In

虚函数表

所谓虚函数表，是编译器自动为一个带有虚函数的类生成的一块内存空间，其中存储着每一个虚函数的入口地址。由于函数的入口地址可以看成一个指针类型，因此这些虚函数的地址间隔为四个字节。而每一个带有虚函数类的实例，都拥有一个虚函数指针——vptr，在类的对象初始化完毕后，它将指向虚函数表。

相关概念

  1. vbase offset
    vbase offset全称为(Virtual Base offsets), 也即虚基类偏移。当一个class存在虚基类时，gcc编译器便会在
    primary virtual table中安插相应的vbase offset。 其主要作用为：
    用于访问对象的虚基类子对象。
    这样的条目被添加到派生类对象vtable，以获取虚拟基类子对象的地址。每个虚基类都需要这样一个条目。这些值可以是正的，也可以是负的。

  2. top offset
    top offset ，也即到class顶部的偏移，指的该class的vptr到对象顶部的位移，其类型为 ptrdiff_t。 它总是存。 偏移量提供了一种使用vptr从任何基类对象中查找对象顶部的方式。 这对于 dynamic_cast<void*> 尤其必要。

  3. typeinfo指针
    typeinfo 指针指向用于 RTTI 的 typeinfo 对象。 它总是存在的。 给定类的每个vtable中的所有typeinfo 指针都必须指向相同的 typeinfo 对象。 typeinfo 相等性的正确实现是检查指针相等性，但指向不完整类型的指针（直接或间接）除外。 typeinfo 指针在多态类的场景下是有效指针，对于非多态类为零。

  4. virtual function 指针
    函数指针用于虚函数调度。 每个指针要么保存类的虚函数的地址，要么保存在将控制权转移到虚函数之前执行某些调整的辅助入口点的地址。
    先有个初步的了解

    1
    2
    3
    4
    5
    6
    7
    8
    9
    class A
    {
    public:
        int a;
        virtual ~A(void) {}
    };
    class B : virtual public A
    {
    };

    对于上面的代码,执行g++ -fdump-lang-class code.cc，并执行c++命名反修饰cat code.001.class | c++filt会得到下面的输出,其中的VTT下面会解释

    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
    Class A
       size=16 align=8
       base size=12 base align=8
    A (0x0x7fb9e6855d80) 0
        vptr=((& A::vtable for A)   16)

    Vtable for B
    B::vtable for B: 8 entries
    0     16
    8     (int (*)(...))0
    16    (int (*)(...))(& typeinfo for B)
    24    (int (*)(...))B::bf
    32    0
    40    (int (*)(...))-16
    48    (int (*)(...))(& typeinfo for B)
    56    (int (*)(...))A::af

    VTT for B
    B::VTT for B: 2 entries
    0     ((& B::vtable for B)   24)
    8     ((& B::vtable for B)   56)

    Class B
       size=32 align=8
       base size=12 base align=8
    B (0x0x7fb9e66fe1a0) 0
        vptridx=0 vptr=((& B::vtable for B)   24)
      A (0x0x7fb9e6855e40) 16 virtual
          vptridx=8 vbaseoffset=-24 vptr=((& B::vtable for B)   56)

gcc查看虚函数表

做些设置

1
2
3
set print asm-demangle on
set print demangle on 
set print pretty on

查看对象结构：p 对象名

1
2
3
4
5
6
7
8
(gdb) p p1
$1 = {_vptr$Parent = 0x400bb8 <vtable for Parent+16>}
(gdb) p p2
$2 = {_vptr$Parent = 0x400bb8 <vtable for Parent+16>}
(gdb) p d1
$3 = {<Parent> = {_vptr$Parent = 0x400b50 <vtable for Derived+16>}, <No data fields>}
(gdb) p d2
$4 = {<Parent> = {_vptr$Parent = 0x400b50 <vtable for Derived+16>}, <No data fields>}

dump内存: x/字节数 起始位置
x/300xb 0x400b40

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
(gdb) x/300xb 0x400b40
0x400b40 <vtable for Derived>:	0x00	0x00	0x00	0x00	0x00	0x00	0x00	0x00
0x400b48 <vtable for Derived+8>:	0x90	0x0b	0x40	0x00	0x00	0x00	0x00	0x00
0x400b50 <vtable for Derived+16>:	0x80	0x0a	0x40	0x00	0x00	0x00	0x00	0x00
0x400b58 <vtable for Derived+24>:	0x90	0x0a	0x40	0x00	0x00	0x00	0x00	0x00
0x400b60 <typeinfo name for Derived>:	0x37	0x44	0x65	0x72	0x69	0x76	0x65	0x64
0x400b68 <typeinfo name for Derived+8>:	0x00	0x36	0x50	0x61	0x72	0x65	0x6e	0x74
0x400b70 <typeinfo name for Parent+7>:	0x00	0x00	0x00	0x00	0x00	0x00	0x00	0x00
0x400b78 <typeinfo for Parent>:	0x90	0x20	0x60	0x00	0x00	0x00	0x00	0x00
0x400b80 <typeinfo for Parent+8>:	0x69	0x0b	0x40	0x00	0x00	0x00	0x00	0x00
0x400b88:	0x00	0x00	0x00	0x00	0x00	0x00	0x00	0x00
0x400b90 <typeinfo for Derived>:	0x10	0x22	0x60	0x00	0x00	0x00	0x00	0x00
0x400b98 <typeinfo for Derived+8>:	0x60	0x0b	0x40	0x00	0x00	0x00	0x00	0x00
0x400ba0 <typeinfo for Derived+16>:	0x78	0x0b	0x40	0x00	0x00	0x00	0x00	0x00
0x400ba8 <vtable for Parent>:	0x00	0x00	0x00	0x00	0x00	0x00	0x00	0x00
0x400bb0 <vtable for Parent+8>:	0x78	0x0b	0x40	0x00	0x00	0x00	0x00	0x00
0x400bb8 <vtable for Parent+16>:	0xa0	0x0a	0x40	0x00	0x00	0x00	0x00	0x00
0x400bc0 <vtable for Parent+24>:	0x90	0x0a	0x40	0x00	0x00	0x00	0x00	0x00
...

单继承的虚函数表

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

class Parent {
 public:
  virtual void Foo() {}
  virtual void FooNotOverridden() {}
  int a;
};

class Derived : public Parent {
 public:
  void Foo() override {}
  int b;
};

int main() {
  Parent p1, p2;
  Derived d1, d2;

  std::cout << "done" << std::endl;
}

子类的内存布局
gdb中查看

子类布局
_vptr$Parent
int a (Parent data)
int b (Child data)
虚函数表,Drived只有一个函数表，但Parent和Derived都指向Derived的虚函数表,Derived复用了父类的vptr。下面是vtable布局
vtable布局

多继承的虚函数表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Mother {
 public:
  virtual void MotherFoo() {}
   int mother_data;
};

class Father {
 public:
  virtual void FatherFoo() {}
   int father_data;
};

class Child : public Mother, public Father {
 public:
  void FatherFoo() override {}
   int child_data;
};

按照上面gdb的查看步骤，可以得到:
内存布局
vtable
这里是把Monther当做主基类,Child复用Monther的vptr.观察可以发现，父类的vptr指针对于被覆盖的函数，实际上指向的子类的地址。
当做下面转换时，

1
2
Father f  = Child();
f.fatherFoo();

实际上调用的一段汇编的桩代码，类似于
gdb执行info vtbl c查看vtable有:
查看vtable
实际的内存地址可能和上面表格有出入，但顺序是一致的
得到函数地址再反汇编,有
反汇编覆盖的虚函数
第一行sub $0x10 %rdi就是在调整this指针，rdi寄存器一般用来保存成员函数的第一个参数，也就是this指针.偏移量有前面的top_offset得到
注意 为什么需要调整this指针呢？
因为Father实际上基类，但调用的实例是Child，成员函数的this指针必须指向当前实际类型的内存空间,因为在被覆盖的成员函数可能会访问子类成员数据，this指针如果不设置正确，则可能访问错误。所有的多态调用都必须调整this指针,主基类由于和子类共用vptr不需要调整。在我们这个例子中Mother是主基类，调佣Mother的虚函数，不需要调整this指针

虚拟继承的虚函数表

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>
using namespace std;

class Grandparent {
 public:
  virtual void grandparent_foo() {}
  int grandparent_data;
};

class Parent1 : virtual public Grandparent {
 public:
  virtual void parent1_foo() {}
  int parent1_data;
};

class Parent2 : virtual public Grandparent {
 public:
  virtual void parent2_foo() {}
  int parent2_data;
};

class Child : public Parent1, public Parent2 {
 public:
  virtual void child_foo() {}
  int child_data;
};

int main() {
  Child child;
}

还是按照上面步骤来看,打印Child的内存布局
gdb内存布局
内存布局
可以发现，实际上虚继承的每个父类都只有一份内存拷贝，相当于直接继承GrandParent。下面是vtable
vtable布局
gdb内存布局
实际的内存地址可能和上面表格有出入，但顺序是一致的
这里多出来了construct table和vtt。这篇反汇编gcc编译bin的论文有提到这些是干什么的.下面我也会解释这两个的作用。
注意 construct table和vtt在内存中实际存在的,要占用内存空间
construct table是在实例化Child需要用到的,比如在实例化Child时，会最先实例化GrandParent(相当于Child直接继承),然后再实例化Parent1,Parent2.但GrandParent已经有了，如何告诉Parent1呢？这里就用到了virtual base offset和construct table，告诉Parent1，GrandParent已经在this-32的位置(这里this是指向Child的内存首地址,因为是构造Child).这样就可以把类拼起来了。top_offset还是子类到Child数据成员首地址的偏移量。
Parent1 construct table
还有一个东西就是Vtable table，用来记录多个vtable的位置，充当一个索引的作用
vtt

虚函数表如何解决面向对象中的问题

实现多态

  1. 基类的vptr指向子类的虚函数
  2. 在调用时，根据子类记录的基类偏移量来调整this指针

遗留的问题

我搞不懂既然vptr是指向function pointer，那编译器怎么直到vptr前面有几个才是vtable的首地址呢，第几项是vbase offset呢？如果有多个虚继承的类，又当怎么vbase offset呢？

继承结构可视化

在有一篇反汇编gcc编译出的bin论文中有提到说可以可视化vtable,但我是没跑通，最后需要下载ida pro这个反编译工具,没跑通
https://github.com/bingseclab/VirtAnalyzer/blob/master/README.md

引用

  1. 深入探索C++对象-候捷
  2. 反汇编gcc编译bin的论文
  3. LLVM虚函数表
  4. vtable单继承详解
  5. vtable多重继承详解
  6. vtable虚继承详解

Posted on Edited on In

简单介绍下编译原理

词法分析->语法分析->生成中间代码->机器无关的优化->生成汇编(机器相关的优化)->交给汇编器生成机器码
编译原理我当时看完了龙书+斯坦福的编译器公开课之后,对其中细节还是一知半解,当时就暂时先放下了.最开始的递归下降,nfa,dfa直接给我劝退了。
AST啥的也理解不透彻.

词法分析和语法分析框架

lex和yacc是unix下的词法/语法分析框架,
flex/bison是词法/语法分析框架
bison和yacc实际上用途是同一种，不过在不同平台下,yacc已经成为语法分析框架的代名词。下文统一使用lex/yacc

Lex和YACC内部是如何工作的？

main ->yyparse() -> yylex()
yylex 会读取在yyin这个变量中的文件(没有则默认是stdin), yylex不断解析输入流,yyparse不断推导产生式并执行相应动作(在语法文件中定义),直到结束.
注意：所以现在语法推导和lex解析算法大多都是O(N),只扫描一遍输入流不回退

lex

hello world

这个框架实际上会根据给定的配置,来解析字符串

1
2
3
4
5
6
7
%{
#include <stdio.h>
%}
%%
stop       printf(“Stop command received\n”);
start      printf(“Start command received\n”);
%%

第一部分，位于%{和%}对之间直接包含了输出程序(stdio.h).我们需要这个程序，因为使用了printf函数，它在stdio.h中定义.

第二部分用’%%’分割开来，所以第二行起始于’stop’，一旦在输入参数中遇到了’stop’，接下来的那一行(printf()调用)将被执行.

1
匹配的字符串名称 执行动作

我们这里是固定字符串stop,start

除此之外，还有’start’，其跟stop的行为差不多.
执行以下命令：
编译时，我们增加『-ll』编译选项，因为libl会提供main函数.

1
2
flex helloworld.lex
gcc lex.yy.c –o example –ll

输出

正则表达式

1
2
3
4
5
6
7
%{
#include <stdio.h>
%}

%%
[0123456789]+     printf(“NUMBER\n”);
[a-zA-Z][a-zA-Z0-9]*  printf(“word\n”);

执行以下命令：

1
2
flex regex.lex
gcc lex.yy.c –o example –ll

输出

lex中的函数和变量

  • ytext char * 当前匹配的字符串
  • yleng int 当前匹配的字符串长度
  • yin FILE * lex当前的解析文件，默认为标准输出
  • yout FILE * lex解析后的输出文件，默认为标准输入
  • ylineno int 当前的行数信息
  • 宏
    CHO #define ECHO fwrite(yytext, yyleng, 1, yyout) 也是未匹配字符的默认动作
  • int yylex(void) 调用Lex进行词法分析
  • int yywrap(void) 在文件(或输入)的末尾调用。如果函数的返回值是1，就停止解析。 因此它可以用来解析多个文件。代码可以写在第三段，这样可以解析多个文件。 方法是使用 yyin 文件指针指向不同的文件，直到所有的文件都被解析。最后，yywrap() 可以返回1来表示解析的结束。

yacc

YACC可以解析输入流中的标识符(token)，这就描述了YACC和LEX的关系，YACC并不知道『输入流』为何物，它需要事先就将输入流预加工成标识符，我们也可以自己手工写一个Tokenizer.

yacc中的函数

  • yyerror()在YACC发现一个错误的时候被调用，我们只是简单的输出错误信息.
  • yywrap()函数用于不断的从一个文件中读取数据，当遇到EOF时，你可以再输入一个文件，然后返回0，你也可以使得其返回1，暗示着输入结束
  • 这里有一个main()函数，它基本什么也不做，只是调用一些函数.可以单独定义也可以就放在grammer.y中
  • yyparse() 会解析输入流中的token,并结合产生式推导

产生式

编译原理中的表达语法的上下文无关文法,确定了字符串的生成变换规则.这里需要将固定的语法拆分成字符串变换规则来理解,如果一个字符串没办法从终结符号结合变换规则得到，则该字符串不符合语法,需要抛出sytnax error.常见的语法分析算法有递归下降,LALR等

实例(实现一个固定语法的温度控制器)

我们希望实现下面的功能,如果用户输入heat on 就打开温度控制器,输入heat off就关闭温度控制器,用户还可以通过target temperature set xxx来设定温度值

lexer

1
2
3
4
5
6
7
8
9
10
11
12
13
%{
#include <stdio.h>
#include "y.tab.h"
%}
%%
[0-9]+         { yylval = atoi(yytext); return NUMBER;}
heat           return TOKHEAT;
on|off         return STATE;
target         return TOKTARGET;
temperature    return TOKTEMPERATURE;
\n             /* ignore end of line */;
[ \t]+         /* ignore whitespace */
%%

lex根据正则来确定TOKEN,这个也是在yacc产生式中的终结符

grammer

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
%{
#include <stdio.h>
#include <string.h>
void yywrap()
{
    return  1;
}
void yyerror(char * errmsg){
    printf("%s\n",errmsg);
}

int main()
{
    yyparse();
}
%}
//这里需要和lex中返回的token一致
%token  NUMBER TOKHEAT STATE TOKTARGET TOKTEMPERATURE
%%
commands: /* empty */
    | commands command
;

command: heat_switch
    | target_set
;

heat_switch:
    TOKHEAT STATE
    {
        printf("\tHeat turned on or off\n");
    }
;

target_set:
    TOKTARGET TOKTEMPERATURE NUMBER
    {
        //展示区别,这里给输入参数+5
        printf("\tTemperature set %d\n",$3 + 5);
    }
;
%%

输出

对于设定的温度,我为了展示有运算逻辑而不是直接拷贝字符串,我特意对参数做了一个加5的逻辑
执行下列命令

1
2
3
flex heat.lex
bison -d heat-grammer.y  --file-prefix y
gcc y.tab.c lex.yy.c

温度控制

yacc中的union类型(这种是实际工程中才使用的)

温度控制器的新语法

用下面方式控制，先选择heater，再设置温度
heater mainbuilding

Selected ‘mainbuilding’ heater

Target temperature 23

‘mainbuilding’ heater target temperature now 23

yacc中的变量

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
%{
#include <stdio.h>
#include <string.h>
extern int yydebug = 1;
char * heater=NULL;
void yywrap()
{
    return  1;
}
void yyerror(char * errmsg){
    printf("%s\n",errmsg);
}

int main()
{
    yyparse();
}
%}

%token  TOKHEAT TOKTARGET TOKTEMPERATURE  TOKHEATER 
%union
{

    int number;

    char *string;
}

%token <number> STATE

%token <number> NUMBER

%token <string> WORD

%%
commands: /* empty */
    | commands command
;

command: heat_switch
    | target_set | heater_select
;

heat_switch:
    TOKHEAT STATE
    {
         if ($2)
            printf("\tHeat turned on\n");
         else
            printf("\tHeat turned off\n");
    }
;

target_set:
    TOKTARGET TOKTEMPERATURE NUMBER
    {
        //展示区别,这里给输入参数+5
        printf("\tHeater '%s' temperature set to %d\n", heater, $3+5);
    }
;
heater_select :

    TOKHEATER WORD

    {

       printf("\tSelected heater ‘%s’\n", $2);

       heater = $2;

}

    ;
%%

这次我们在command产生式增加了heater_select,并且定义了一个全局变量来接收选择的温度控制器.token处，我们定义了一个union变量,用于处理输入中不同的数据类型.此处表示yylval是一个union类型,可用来处理不同的数据类型

语法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
%{
#include <stdio.h>
#include "y.tab.h"
%}
%%
[0-9]+         { yylval.number = atoi(yytext); return NUMBER;}
heater         return TOKHEATER;
heat           return TOKHEAT;
on|off         { yylval.number = !strcmp(yytext,  "on"); return STATE; }
target         return TOKTARGET;
temperature    return TOKTEMPERATURE;
[a-z0-9]+     yylval.string = strdup(yytext); return WORD;
\n             /* ignore end of line */;
[ \t]+         /* ignore whitespace */
%%

细心的同学可能已经发现了,这次对于yylval的赋值已经是具体到成员了

输出

对于设定的温度,我为了展示有运算逻辑而不是直接拷贝字符串,我特意对参数做了一个加5的逻辑
输出

yacc debug

当调试你的语法时，在YACC命令行中添加—debug和—verbose选项，在你的C文件头中添加以下语句：
int yydebug = 1;这将生成一个y.output文件，其中说明了所创建的那个状态机.
可以开启debug语法信息,详细查看yacc状态机和根据产生式推导的过程.这里我mark一下,以便后续自己查阅.

1
2
-t(--debug) -v
bison -t -v -d heat-grammer.y -b y

测试代码见

我的github代码

推广

我们发现lex和yacc可以用来处理有固定语法的字符串,那么我们可以用其来解析配置文件,解析sql,解析json等等.好啦,现在你可以去看mysql和pg的sql解析啦,为学到新知识开心.
mysql yacc
Postgres yacc

更深入的学习

北大编译实践
lex和yacc内核

引用

  1. flex和bison
  2. flex和bison实现计算器
  3. flex和bison中文版电子书

Posted on Edited on In

通信

主流的理解是将通信看成信息编码+信息传输+信息解码,这里不涉及到应用层的具体协议解读.只是将源产生的信息在经过不可靠信道传输之后,目的端能够接收并正确还原到多少.

编码定理

TODO

循环码

这块内容涉及到相当多的理论证明,等我后面慢慢研究再补充