leetcode刷题笔记

数组

二分查找

关键：循环条件，先想好题目所求元素所在区间是左闭右开还是全闭
比如说:

1. target在[left,right]里，则当left=right时，[left,right]有效，所以循环条件为left<=right
2. target在[left,right)里，则当left=right时，[left,right)无效，所以循环条件为left<right

移除元素

双指针法

1. 移除、移动元素，返回前n位，两个指针cur和end
2. 有序数组的平方：从两边开始找当前最大值

区间和

前缀和：涉及计算区间和的问题

——p[i] 表示 下标 0 到 i 的 vec[i] 累加 之和

求2~5的区间和 =p[5] - p[1]

链表

链表设计

struct ListNode
dummy：做题也常用

链表相交

1. 求两链长度
2. 长链和断链末尾对齐后遍历
3. 相遇处即为相交点

环形链表

1. 快慢指针从头出发，快指针走两步，慢指针走一步，相遇则有环
2. ptr1从头出发，ptr2从相遇点出发，一次走一步
3. 再次相遇点——环入口

哈希表

哈希表理论基础

解决问题：快速查询

哈希碰撞

1. 拉链法：发生冲突的元素存储在链表里
   • 选择适当的哈希表的大小，不会因为数组空值浪费大量内存，也不会因为链表太长在查找上浪费时间
2. 线性探测法：遇到冲突向下找一个空位存放冲突元素
   • 保证tableSize>dataSize

常见的三种哈希结构

1. 数组

2. set

   • set：红黑树，增删查改：O(log n)

   • multiset：红黑树，增删查改：O(log n)

     key不可以修改，只能增加和删除

   • unordered_set：哈希表，增删查改：O(1)

3. map

总结：当需要快速判断一个元素是否出现在集合里，考虑哈希法

——牺牲空间换取时间

有效的字母异位词

• 数组是简单的哈希表，当遇到元素范围固定，可以考虑用数组作为哈希表，比如26个字母——使用数组来做哈希的题目，都限制了数值的大小

• 如果数据分散、跨度比较大，使用数组容易造成空间的浪费

• 直接使用set 不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的——如果数值范围固定，优先考虑用数组

快乐数

• 取位数

  1 2 3 4 5 6 7 8

  int getSum(int num){ int sum; while(num!=0){ int bit=num%10; num/=10; sum+=bit; } }

• 循环/成环问题

  • 使用哈希判断是否存在重复元素
  • 使用快慢指针：快指针一次走两步，慢指针一次走一步，快慢指针相遇——快指针比慢指针多走了一个循环周期

总结：map vs set vs 数组

1. 数组：大小受限，数据分散会浪费内存空间
2. set：只能存放key，同等情况下性能不如数组，因为取哈希值也要耗时
3. map：需要存放两个值，什么作为key取决于需要查询什么

不要求key有序的时候，使用unordered_map/set

四数之和II

给出四个数组，求四个数和为0，不要求去重

使用hashmap，两数之和：两数之和出现的次数，再去遍历另外两个数组

三数之和

可以使用双指针法

• 将数组排序

当返回值是具体数值，可以使用双指针法，如果要求返回的是下标，不能对数组排序，也就不能使用双指针法

四数之和

当求几个数之和时，要求返回的元组不能重复，使用双指针法

不管是求几个数之和，以前i-2个数作为标准，剩下两个数用双指针确定

时间复杂度从O(n^i)降为O(n^(i-1))

字符串

翻转字符串里的单词

• 移除不必要的空格 = 移除元素 ——>双指针法
• 翻转：先整体翻转后局部翻转——先翻转整个字符串，再翻转单词

右旋转字符串

字符串尾部的若干个字符转移到字符串的前面

解决方法：先整体翻转后局部翻转——先翻转整个字符串，再分别翻转左部和右部

KMP算法

解决问题：字符串匹配

eg：文本串：aabaabaaf 模式串：aabaaf

• 暴力解法：O(M*N)

• KMP

  1. 第一次匹配

     a	a	b	a	a	b	a	a	f
     a	a	b	a	a	f

  2. 第二次匹配

     a	a	b	a	a	b	a	a	f
     			a	a	b	a	a	f

     思路：文本串指针不变，模式串指针回转

• next数组构造思路

  1. 初始化next数组
  2. 处理不相等情况
  3. 处理相等情况
  4. 更新next的值

重复的子字符串

1. 暴力解法

   分别以1~n/2的字符结尾，判断能否构成字符串

2. 移除匹配

   如果 s 是重复字符串，则 s+s 去除首尾仍能检测出中间含 s

3. KMP算法

   如果字符串str能用子字符串substr重复组成，则

   len(str)=m*len(substr)

   len(presuf)=(m-1)*len(substr)

   → len(substr)=len(str)-len(presuf)

   → len(str)%[len(str)-len(presuf)]=0

栈和队列

栈与队列的理论基础

• 栈提供push 和 pop 等等接口，所有元素必须符合先进后出规则，所以栈不提供走访功能，也不提供**迭代器(iterator)**。 不像是set 或者map 提供迭代器iterator来遍历所有元素
• 栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）
• STL中栈往往不被归类为容器，而被归类为container adapter（容器适配器）
• 栈的内部结构，栈的底层实现可以是vector，deque，list
  • SGI STL，如果没有指定底层实现的话，默认是以deque为缺省情况下栈的底层结构：deque是一个双向队列，只要封住一段，只开通另一端就可以实现栈的逻辑了。
  • 指定vector为栈的底层实现： stack<int,vector<int>> stack;
• 队列是先进先出的数据结构，同样不允许有遍历行为，不提供迭代器
• 可以使用deque和list对queue初始化，而vector因其缺少pop_front()，不能用于queue
  • SGI STL中队列一样是以deque为缺省情况下的底部结构
  • 指定list 为队列的底层实现：queue<int,list<int>> queue

用栈实现队列

• 双栈
• 进队：进栈in
• 出队：栈in全部弹出到栈out，从栈out弹出

用队列实现栈

• 一个队列
• 进栈：进队
• 出栈：队列头部不断出队移到队尾，直到最后一个元素到队头 → 出队

有效的括号

• 括号匹配问题，使用栈实现

删除字符串中的所有相邻重复项

• 删除重复项也可以用栈实现
• 输出的时候记得翻转

逆波兰表达式求值

• 逆波兰表达式：一种后缀表达式，运算符放在后面
• 适合用栈操作运算：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中

滑动窗口最大值

• 单调队列：使用容器 deque 出口→入口
• 实现接口：
  • front：队头——最大值
  • pop(int val)：离开窗口的值 val如果比队头小，本来就不在队列里，不用处理；而队头已经是窗口内最大值了，所以 val也不可能比队头大。所以只有队列不为空并且弹出 val==队头，才弹出
  • push(int val): 如果push的值比队尾大，那么单调性被破坏，弹出直到队列为空或者队尾比push的值大→ 维护单调性

前k个高频元素

• 容器适配器：优先级队列
  • 披着队列外衣的堆，缺省情况下是大根堆——以vector为表现形式的完全二叉树
  • 要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素

快排的优化方法

1. 找基准方面的优化

   1. 聚集相同元素法：在经过一次找基准之后把数据中与基准相同的数据聚集到基准左右，优化后：由于相等元素被聚集在一起，递归时跳过这些元素，减少了比较和交换的次数，减少了递归深度

   2. 随机取基准法：产生随机数在数据中去取随机位置元素为基准

   3. 三分取基准：比较数据中start、end和两者中间位置的数据的大小，将这三个值处于中间位置的值放到首位，再进行找基准操作

2. 当序列长度达到一定大小时，使用插入排序

   • 当快排达到一定深度后，划分的区间很小，里面的元素已经基本有序了，再使用快排的效率不高
   • 当待排序列的长度达到一定数值后，可以使用插入排序
   • 当待排序列长度为5~20之间时，使用插入排序可以避免一些有害的退化情形

3. 尾递归优化

   • 快排跟大多数分治排序算法一样，都有两次递归调用，区别：归并排序的递归在函数一开始，快排的递归在函数尾部，这就使得快排可以使用尾递归优化
   • 尾递归概念：函数所有递归形式的调用都出现在函数的尾部，当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归
   • 尾递归特点：在回归过程中不用做任何操作，编译器会利用这种特点自动生成优化的代码
   • 尾递归原理：当编译器检测到一个函数调用时尾递归的时候，它就会覆盖当前的活动记录而不是在栈中去创建一个新的。因为尾递归是最后一条待执行语句，所以当这个递归返回时栈帧并没有其他事情可做，也就没有保存栈帧的必要了。通过覆盖当前栈帧而不是在其之上重新添加一个，这样使用的栈空间大大缩减，使得实际的运行效率变高

4. 多线程处理快排

   • 分治法的基本思想是将一个问题分解为多个规模较小的子问题，这些子问题独立且与原问题相同，求解子问题，再将子问题的解合并得到原问题的解。所以在处理快排时可以使用多线程提高排序的效率

constexpr

1. constexpr

1.1 const

在C++11之前只有const关键字，从功能上来说这个关键字有双重语义：1.变量可读；2.修饰常量
void func(const int num)表示这个变量是可读的，但不是常量；
const int num=24表示这个变量是常量
注意：变量只读不等于常量
例：

1
2
3
4

const int &num=a;
num=b;//错误，b是一个常量的引用，所以b引用的变量是不能修改的
a=10;//但是const对于变量a是没有影响的，a值变了b值也就变了
//所以引用b是只读的，但不能保证它的值不可改变，也就是说它不是常量

1.2 constexpr

C++11的新关键字，作用：修饰常量表达式
常量表达式：由多个常量组成并且在编译过程中就得到计算结果的表达式

非常量表达式只能在程序运行阶段计算出结果
但是常量表达式的计算往往发生在程序的编译阶段，可以提高程序的执行效率，因为表达式只要在编译阶段计算一次，节省了每次程序运行时都需要计算一次的时间

编译器如何识别常量表达式？constexpr
constvsconstexpr：使用中建议区分开，const表达只读语义，constexpr表达常量
在定义常量时，const和constexpr是等价的，都可以在程序编译阶段计算出结果

2. 常量表达式函数

使用constexpr修饰函数的返回值，这种函数叫做常量表达式函数，主要包括：1.普通函数/成员函数；2.类的构造函数；3.模板函数

2.1 修饰普通函数/成员函数

常量表达式函数的几个条件：

1. 函数必须有返回值，而且返回值必须是常量表达式
2. 函数在使用前必须有对应的定义语句
3. 整个函数的函数体中，不能出现非常量表达式之外的语句（using 指令、typedef 语句以及 static_assert 断言、return语句除外）

2.2 修饰模板函数

constexpr可以修饰函数模板,如果constexpr修饰的模板函数实例化结果不满足常量表达式函数的要求，则constexpr会被自动忽略，即该函数就等同于一个普通函数

2.3 修饰构造函数

如果想得到一个常量对象，也可以使用constexpr修饰构造函数——常量构造函数有一个要求：构造函数的函数体必须为空，并且必须采用初始化列表的方式为各个成员赋值
如果不这么做的话，当定义一个常量对象时会报错

1
2
3
4
5
6
7
8
9
10

class Student{
public:
    Student(int age):age(age){}
    int age;
};

int main(){
    constexpr Student stu(12);
    cout<<stu.age;
}

0717百度面经

1. python跟C++的区别

1. 语言类型不同
   1. C++是编译性编程语言，编程型语言在程序执行前有一个单独的编译过程，将程序翻译成机器语言，以后执行的时候就不用再编译，直接运行可执行文件
   2. python是解释性语言，解释型语言是指使用专门的解释器对源程序进行逐行解释成特定平台的机器码，并立即执行。每次执行解释性语言程序的时候都需要重新解释再执行，所以它的运行效率通常比较低，而且不能脱离解释器执行
2. 执行效率不同
   1. C++执行效率高
   2. python执行效率低
3. 开发效率不同
   1. C++开发效率低，编程难度大
   2. python开发效率高，编程难度小
4. 内存管理机制不同
   1. python有被称为“垃圾收集器”的自动内存管理机制，不允许直接进行内存处理操作
   2. C++里则没有这样的机制，并且所有内存管理操作都需要自行处理

2. 对称加密和非对称加密的区别

1. 加密和解密使用的密钥不同
   1. 对称加密双方使用相同密钥
   2. 非对称加密双方分别使用公钥和私钥
2. 成本不同
   1. 对称加密算法在加密和解密过程中只涉及一个密钥，算法的实现成本较低
   2. 而非对称加密算法涉及两个密钥，其中一个是非公开的，因此算法的实现成本较高
3. 加解密速度不同
   1. 对称加解密速度较快，适合数据比较长的时候使用
   2. 非对称加解密速度较慢，适合对少量数据的使用
4. 传输的安全性不同
   1. 对称加密的通信双方使用相同的秘钥，如果一方的秘钥遭泄露，那么整个通信就会被破解。
   2. 而非对称加密使用一对秘钥，一个用来加密，一个用来解密，而且公钥是公开的，秘钥是自己保存的，即便攻击者获得了公钥，也无法解密加密的数据。

3. AES算法几种工作模式

1. AES加密算法
   AES的轮函数每一轮迭代的结构都一样，由4种变换组成：字节替换、行移位、列混合、轮密钥加
2. 分组加密的工作模式
   块加密模式

• ECB：消息分成相互独立的加密模块，每块独立加密。特点：同样的明文会出现相同的密文，适合短数据加密
• CBC（分组链接模式）：消息块M1跟初始向量IV异或后加密得密文C1，消息块M2和C1异或后加密得密文C2。特点：适合用于加密较长的消息
  流加密模式：转化为流密码，不需要对密码进行填充
• CFB（密码反馈模式）：IV——移位寄存器加密后，选择前j比特和消息P1异或得C1，将移位寄存器左移j位并放入密文C1……
• OFB（输出反馈模式）：OFB是将加密算法的输出反馈到移位寄存器，CFB是将密文反馈到移位寄存器。OFB的优点是比特错误不会被传播，而CFB的比特错误会被放到移位寄存器里，影响接下来的解密过程
  CTR（计算器模式）：Counter加密后和明文P1异或得C1，Counter+1：加密后和明文P2异或后得C2。特点：可以并行加密。

4. C++内存分区

C++在执行时，将内存划分为4个区域：

1. 代码区：存放函数体的二进制代码
2. 全局区：存放全局变量、静态变量和常量
3. 栈区：由编译器自动分配释放，存放函数的参数值、局部变量
4. 堆区：由程序员分配和释放，若程序员不释放，程序结束时由操作系统回收

• 程序运行前：
  程序编译后，生成了exe可执行程序，未执行程序前分为两个区域
  1. 代码区：存放CPU执行的机器指令；是共享的，对于频繁执行的程序，在内存中有一份代码就行；是只读的，防止程序意外修改指令
  2. 全局区：存放全局变量和静态变量+常量区：存放const修饰的全局常量和字符串常量等
• 程序运行后：
  1. 栈区：由编译器自动分配和释放，存放函数的参数值、局部变量。所以注意：不要返回局部变量的地址，栈区开辟的数据由编译器自动释放。
  2. 堆区：由程序员分配释放，若程序员不释放，程序结束时由操作系统回收

5. 32位系统中堆通常在的地址范围是多少，大概有多大

对于linux来说，地址由低向高分别是：保留区，代码段，数据段，BSS段，堆，文件映射区，栈，内核空间
堆的大小范围可能在几百MB到2-3GB之间

6. C++中的智能指针

unique指针怎么做到不能被复制的

7. 指针传递、值传递和引用传递的区别

• python有没有值传递和引用传递的区别：python中没有严格的定义值传递与引用传递
  • python中的变量没有类型，变量相当于一个指针，可以指向任何类型的对象，也就是变量引用了某个对象；python对象是有类型的，一般看变量是什么类型需要看其引用的对象是什么类型。
  • 总的看来，函数传递参数都可以看做是引用传递的（因为python变量相当于指针，传递指针就相当于传递了地址的引用），只不过因为python中的有些对象是不可变的，因此让有些引用传递的过程中又像是值传递的。
  • 当python中的函数传递过来的是不可变的值时（比如数字常量、元组和字符串），相当于 C语言中的值传递的；若传递过来的参数是可变的（如列表、字典等），则相当于引用传递
• 可变类型与不可变类型
  • 不可变类型：不可变变量的值一旦创建，就不能被修改。如果你尝试修改一个不可变对象的值，Python 将会创建一个新的对象。Python 中的不可变对象包括整数（int）、浮点数（float）、字符串（str）、元组（tuple）等。
  • 可变类型：可变变量的值可以在原地修改，而不会创建一个新的对象。Python 中的可变对象包括列表（list）、字典（dict）、集合（set）等

    1 2 3 4 5 6 7 8 9 10 11

    def modify_value(x): print(f"变量x修改前地址：{id(x)}") x = x + 10 print(f"变量x修改后地址：{id(x)}") print("函数内部修改后的值为:", x) # 调用函数 value = 5 print(f"变量value地址：{id(value)}") modify_value(value) print("函数外部原始值为:", value)

8. C++编译链接的过程

1. 预处理阶段：预处理器主要处理以#号开头的预处理指令，包括头文件包含、宏定义、条件编译等等
   1. 头文件包含：预处理器会根据#include指令将需要的头文件内容插入到当前源文件中
   2. 宏替换：预处理器会识别并替换#define指令定义的宏
   3. 条件编译：预处理器根据#ifdef/#ifndef等条件编译指令来决定是否编译某段代码
   4. 在这个过程中，预处理器还会处理行链接、删除注释等工作
2. 编译阶段：编译器将预处理后的源代码转换成汇编语言代码
   1. 词法分析：编译器首先将源代码分解为一系列的tokens
   2. 语法分析：编译器根据语言的语法规则，将tokens组合成语法树或者中间表示
   3. 语义分析：编译器检查语法树或者中间表示的语义，确保类型正确、变量已定义等
   4. 优化：编译器可能会进行一系列优化，以提高生成代码的性能或减少其大小
   5. 最终编译器生成汇编语言代码文件（通常是以.s或.asm为扩展名）
3. 汇编阶段：汇编器将编译阶段生成的汇编代码转换成机器指令
   1. 汇编指令：汇编器将每一条汇编指令翻译成机器指令
   2. 最终，汇编器生成目标文件（通常以.o、.obj或.elf为扩展名）。这些目标文件包含了机器码、符号表和其他代码相关的信息
4. 链接阶段：链接器将多个目标文件和库文件（如静态库和动态库）结合起来，生成最终的可执行文件。地址重定位：链接器解决函数和变量之间的引用关系，确定他们在内存中的地址。
   1. 符号解析：链接器处理目标文件中定义的符号（如函数和变量）和引用的符号，确保他们之间的正确匹配
   2. 库文件链接：如果程序中使用了外部库，链接器会将这些库与目标文件链接起来
   3. 整个编译链接过程确保了源代码从高级语言形式逐步转换为机器可执行的形式，并处理了代码中的依赖关系和符号引用。最终生成的可执行文件可以在目标平台上运行

9. C++中static关键字的作用

1. static最重要的作用：隐藏（普通函数、普通变量）
   • 当同时编译多个文件时，所有未加static的全局变量和函数都具有全局可见性，其他源文件也能访问
   • 如果加了static，就会对其他源文件隐藏，避免命名冲突
2. static的第二个作用是改变变量的存储位置：静态存储区
   • 静态存储区存储的有全局变量和static变量
   • 存储在静态存储区的变量的特点：
     1. 在程序刚开始运行的时候就完成初始化，也是唯一的一次初始化
     2. 静态数据区中所有变量初始值默认为0
     3. 具有持久性
3. static修饰类成员
   静态数据成员是类的成员不是对象的成员，所以有以下作用
   1. 类的静态成员函数属于类而不是类的对象，所以没有this指针，不能访问非静态数据和非静态成员函数，也不能将静态成员函数定义为虚函数
   2. 类的静态成员数据是静态存储的，所以必须进行初始化，静态成员初始化和一般成员初始化不同，在类外初始化，格式如下：<数据类型> <类名>::<成员名>=<值>
   3. 静态成员为父类和子类共享。为了防止父类的影响，可以在子类定义一个与父类相同的静态变量，以屏蔽父类的影响

Q:在头文件中把变量声明为static变量，在引用该头文件的源文件中可以访问该变量吗
A：可以，声明static变量一般是为了在本cpp文件中的static变量不能被其他cpp引用。但是对于头文件，因为cpp文件中包含了该头文件，相当于该static变量在本cpp文件中也可见。而且当多个cpp文件包含该头文件时，static变量在各个cpp是独立的

Q：为什么静态成员函数不能修饰为const？
A：C++的类中，const修饰函数表示函数不能修改成员变量的值，而static函数没有this指针，不能访问非静态成员变量， 矛盾

Q：为什么不能在类的内部定义以及初始化static成员变量，必须放到类外定义？
A：因为静态成员属于整个类，而不属于某个对象，如果在类内初始化，会导致每个对象都包含该静态成员，矛盾

Q：为什么static关键字只能出现在类内部的声明语句中，而不能重复出现在类外的定义中
A：如果类外定义函数加了static，会导致该函数只能在本文件中使用，而类本来就是为了给程序里各个地方用的，其他地方使用是包含类的头文件，而无法包含类的源文件

智能指针

C++ 中的指针分为原始指针和智能指针
智能指针是裸指针的封装
智能指针只解决一部分问题：独占、共享所有权指针的释放、传输，没有从根本上解决C++内存安全的问题

独占指针：unique_ptr

特点：

• 在任何时刻，只能有一个指针管理内存
• 指针超出作用域，内存将自动释放
• 该类型指针不可以copy，只可以move

三种创建方式

• 通过已有裸指针创建
• 通过new来创建
• 通过std::make_unique创建（推荐）

unique_ptr可以通过get()来获取地址
unique_ptr实现了->和*

• 可以通过->调用成员函数
• 可以通过*调用dereferencing解引用
  代码实例
  unique指针的三种创建方式

1. 使用原始指针：注意将原始指针置空

   1 2 3 4

   Cat *c_ptr=new Cat("aa"); unique_ptr<Cat> u_c_ptr(c_ptr); //之后要将原始指针置空 c_ptr=nullptr;

2. 使用new

   1	unique_ptr<Cat> u_ptr(new Cat("bb"));

3. 使用make_unique（推荐）

   1	unique_ptr<Cat> u_ptr=make_unique<Cat>("cc");

   程序结束会后自动调用析构函数！

其他：使用get()获取地址，*解引用

1
2
3

unique_ptr<int> u_ptr=make_unique<int>(10);
cout<<*u_ptr<<endl;
cout<<u_ptr.get()<<endl;

1
2

10
0x183fb0

unique_ptr与函数调用

• unique_ptr是不可copy，只可以move
• 作函数参数和函数返回值时要注意所有权

1. passing by value

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

   void pass_by_value(unique_ptr<Cat> p){ p->cat_info(); } int main() { unique_ptr<Cat> c=make_unique<Cat>("Tom"); pass_by_value(move(c)); // 此时c已经被move到pass_by_value中，c已经不可用 //c->cat_info();此时程序会崩溃 pass_by_value(make_unique<Cat>("Jerry"));//默认调用move return 0; }

   1 2 3 4 5 6

   Constructor of Cat:Tom cat info name:Tom Desctructor of Cat:Tom Constructor of Cat:Jerry cat info name:Jerry Desctructor of Cat:Jerry

2. passing by reference
   • 不加const的情况

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

     void pass_by_reference(unique_ptr<Cat> &p) { p->set_name("Amy"); p->cat_info(); p.reset();// 清空 } int main() { unique_ptr<Cat> cat = make_unique<Cat>("Tom"); pass_by_reference(cat); cout << "=============unique_ptr=============" << endl; // 此时cat被清空了 cout << "cat address:" << cat.get() << endl; return 0; }

     1 2 3 4 5

     Constructor of Cat:Tom cat info name:Amy Desctructor of Cat:Amy =============unique_ptr============= cat address:0

   • 加const的情况

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

     void pass_by_reference(const unique_ptr<Cat> &p) { p->set_name("Amy"); p->cat_info(); // p.reset();加了const以后不允许清空 //但还是可以对对象进行修改 } int main() { unique_ptr<Cat> cat = make_unique<Cat>("Tom"); pass_by_reference(cat); cout << "=============unique_ptr=============" << endl; cout << "cat address:" << cat.get() << endl; return 0; }

     1 2 3 4 5

     Constructor of Cat:Tom cat info name:Amy =============unique_ptr============= cat address:0x1f3f60 Desctructor of Cat:Amy

3. return by value

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

   unique_ptr<Cat> get_unique_ptr() { unique_ptr<Cat> p = make_unique<Cat>("Local cat"); cout << "unique_ptr addreess:" << p.get() << endl; return p; } int main() { cout<<get_unique_ptr().get()<<endl; cout << "=============unique_ptr=============" << endl; return 0; }

   1 2 3 4

   Constructor of Cat:Local cat unique_ptr addreess:0x1043f60 0x1043f60 Desctructor of Cat:Local cat

共享指针:shared_ptr

• shared_ptr又称计数指针
• 与unique_ptr不同的是它可以共享数据，可以copy
• shared_ptr创建了一个计数器，与类对象的内存相关联；copy则计数器+1，销毁则计数器-1；api为use_count()

1. 常量类型

   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

   // 常量类型 // 还有一种定义方式 shared_ptr<int> ptr(new int(10)); shared_ptr<int> p1 = make_shared<int>(10); cout << "value:" << *p1 << endl; cout << "use count:" << p1.use_count() << endl; // 复制，引用计数+1 shared_ptr<int> p2 = p1; shared_ptr<int> p3 = p1; cout << "use count:" << p1.use_count() << endl; cout << "use count:" << p2.use_count() << endl; cout << "use count:" << p3.use_count() << endl; // 修改值，另一个值也会改变，因为指向一个地方 *p3 = 30; cout << "p1 value:" << *p1 << endl; cout << "p2 value:" << *p2 << endl; // 清空一个 p3 = nullptr; cout << "use count:" << p1.use_count() << endl; cout << "use count:" << p2.use_count() << endl; cout << "use count:" << p3.use_count() << endl;

2. 自定义类型

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

   shared_ptr<Cat> cat1 = make_shared<Cat>(); cout << "cat use count:" << cat1.use_count() << endl; shared_ptr<Cat> cat2 = cat1; shared_ptr<Cat> cat3 = cat2; cout << "cat use count:" << cat1.use_count() << endl; cout << "cat use count:" << cat2.use_count() << endl; cout << "cat use count:" << cat3.use_count() << endl; cat1.reset(); cout << "cat use count:" << cat1.use_count() << endl; cout << "cat use count:" << cat2.use_count() << endl; cout << "cat use count:" << cat3.use_count() << endl; cout << "==================================" << endl; return 0;

   1 2 3 4 5 6 7 8

   cat use count:3 cat use count:3 cat use count:3 cat use count:0 cat use count:2 cat use count:2 ================================== Desctructor of Cat:Mimi

   引用计数不为0，程序结束之后销毁

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

   shared_ptr<Cat> cat1 = make_shared<Cat>(); cout << "cat use count:" << cat1.use_count() << endl; shared_ptr<Cat> cat2 = cat1; shared_ptr<Cat> cat3 = cat2; cout << "cat use count:" << cat1.use_count() << endl; cout << "cat use count:" << cat2.use_count() << endl; cout << "cat use count:" << cat3.use_count() << endl; cat1.reset(); cout << "cat use count:" << cat1.use_count() << endl; cout << "cat use count:" << cat2.use_count() << endl; cout << "cat use count:" << cat3.use_count() << endl; cat2.reset(); cat3.reset(); cout << "==================================" << endl; return 0;

   1 2 3 4 5 6 7 8 9

   cat use count:1 cat use count:3 cat use count:3 cat use count:3 cat use count:0 cat use count:2 cat use count:2 Desctructor of Cat:Mimi ==================================

   引用计数为0，就调用析构函数

shared_ptr和函数调用

1. shared_ptr passed by value
   涉及copy，内部引用计数+1，但离开函数use_count-1
2. shared_ptr passed by ref
3. return by value

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

void pass_by_value(shared_ptr<Cat> cat){
    cat->cat_info();
    cat->set_name("cat2");
    cout<<"func1 use count:"<<cat.use_count()<<endl;
}
void pass_by_ref(shared_ptr<Cat> &cat){
    cat->cat_info();
    cout<<"func2 use count:"<<cat.use_count()<<endl;
}
// 一般不用
shared_ptr<Cat> get_shared_ptr(){
    shared_ptr<Cat> cat=make_shared<Cat>("local cat");
    return cat;
}
int main()
{
    shared_ptr<Cat> cat1=make_shared<Cat>("cat1");

    pass_by_value(cat1);
    cat1->cat_info();
    cout << "main use count:" << cat1.use_count() << endl;

    pass_by_ref(cat1);
    cat1->cat_info();
    cout << "main use count:" << cat1.use_count() << endl;

    shared_ptr<Cat> loacl_cat = get_shared_ptr();
    loacl_cat->cat_info();
    cout<<"==============================="<<endl;
    return 0;
}

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

Constructor of Cat:cat1
cat info name:cat1
func1 use count:2
cat info name:cat2
main use count:1
cat info name:cat2
func2 use count:1   // 此时引用计数并没有+1
cat info name:cat2
main use count:1
Constructor of Cat:local cat
cat info name:local cat
===============================
Desctructor of Cat:local cat
Desctructor of Cat:cat2

shared_ptr与unique_ptr

• 不能将shared_ptr转换为unique_ptr
• unique_ptr可以转换为shared_ptr
  • 通过std::move

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

unique_ptr<Cat> get_unique_ptr()
{
    unique_ptr<Cat> cat = make_unique<Cat>("local cat");
    return cat;
}
int main()
{
    unique_ptr<Cat> cat1 = make_unique<Cat>("Amy");
	// 通过move将unique_ptr转换为shared_ptr
    shared_ptr<Cat> cat2 = move(cat1);  // 此时cat1已经不能用了

    cout << "cat2 use count:" << cat2.use_count() << endl;
	// 函数返回值为unique_ptr，可以用shared_ptr接收
    shared_ptr<Cat> cat3 = get_unique_ptr();
    if (cat3) {
        cat3->cat_info();
        cout << "cat3 use count:" << cat3.use_count() << endl;
    }

    cout << "===============================" << endl;
    return 0;
}

weak_ptr

• weak_ptr并不拥有内存的所有权，所以不能调用->和*解引用
• 和shared_ptr类似，但不影响对象引用计数
• 为什么需要weak_ptr：解决shared_ptr循环引用的问题
  • 例：Person1中有一个成员friend，指向另一个Person2，Person2->friend又指向另一个Person3或者指向Person1，最后每个的引用计数都不为0 —— 循环引用
  • 这里需要用一个不需要拥有所有权的指针

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

int main()
{
    // weak_ptr不能单独存在
    shared_ptr<Cat> s_cat1=make_shared<Cat>("cat1");
    weak_ptr<Cat> w_cat1=s_cat1;
    // weak_ptr不影响引用计数
    cout<<"w_cat1:"<<w_cat1.use_count()<<endl;
    cout<<"s_cat1:"<<s_cat1.use_count()<<endl;
    // weak_ptr不能使用->和*操作符
    // w_cat1->cat_info();
    shared_ptr<Cat> s_cat2 = w_cat1.lock();
    cout<<"w_cat1:"<<w_cat1.use_count()<<endl;
    cout<<"s_cat1:"<<s_cat1.use_count()<<endl;
    cout<<"s_cat2:"<<s_cat2.use_count()<<endl;
    cout << "===============================" << endl;
    return 0;
}

循环依赖的问题

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

#include <iostream>
#include <memory>
#include <string>
using namespace std;

class Cat {
public:
    explicit Cat(string name);
    Cat() = default;
    ~Cat();
    void cat_info() const
    {
        cout << "cat info name:" << name << endl;
    }
    string get_name() const
    {
        return name;
    }
    void set_name(const string &name)
    {
        this->name = name;
    }
    void set_friend(shared_ptr<Cat> m_friend)
    {
        this->m_friend = m_friend;
    }

private:
    string name{"Mimi"};
    shared_ptr<Cat> m_friend;
};

Cat::Cat(string name) : name(name)
{
    cout << "Constructor of Cat:" << name << endl;
}

Cat::~Cat()
{
    cout << "Desctructor of Cat:" << name << endl;
}

int main()
{
    shared_ptr<Cat> cat1 = make_shared<Cat>("cat1");
    shared_ptr<Cat> cat3 = make_shared<Cat>("cat3");
    shared_ptr<Cat> cat4 = make_shared<Cat>("cat4");

    cat3->set_friend(cat4);
    cat4->set_friend(cat3);
    
    cout << "===============================" << endl;
    return 0;
}

1
2
3
4
5

Constructor of Cat:cat1
Constructor of Cat:cat3
Constructor of Cat:cat4
===============================
Desctructor of Cat:cat1

发现没有调用cat3和cat4的析构函数
解决方法：将成员变量数据shared_ptr<Cat> m_friend;改为weak_ptr<Cat> m_friend;
但是void set_friend(shared_ptr<Cat> m_friend)这里的不用改

1
2
3
4
5
6
7

Constructor of Cat:cat1
Constructor of Cat:cat3
Constructor of Cat:cat4
===============================
Desctructor of Cat:cat4
Desctructor of Cat:cat3
Desctructor of Cat:cat1

此时可以正常析构

DMA

1. 为什么要有DMA？

没有DMA的情况

1. 用户进程通过read()系统调用，进入内核态；
2. 由CPU向磁盘发送I/O请求
3. 磁盘收到CPU指令后，将数据放到磁盘控制器的缓冲区，然后发起中断
4. CPU收到中断，将数据从磁盘控制器的缓冲区拷贝到PageCache（磁盘高速缓存）
5. CPU再将数据从PageCache拷贝到用户缓冲区
6. read()调用返回

问题：在整个数据传输过程中，CPU一直参与数据搬运的工作，没有办法做其他事情

2. 什么是DMA？

DMA就是“直接内存访问”，也就是在I/O设备和内存的数据传输的时候，数据搬运的工作全部交给DMA控制器，而CPU不参与数据搬运的工作，从而可以做其他事情。

3. DMA怎么工作

1. 用户进程通过read()向CPU发起I/O请求，进入阻塞状态
2. CPU收到I/O请求后，将I/O请求发送给DMA控制器之后，执行其他任务
3. DMA接收I/O请求后，向磁盘发送I/O请求
4. 磁盘接收到请求后，将数据读到磁盘控制器的缓冲区，当磁盘控制器缓冲区读满后，向DMA发起中断
5. DMA收到中断后，将数据从磁盘控制器的缓冲区拷贝到内核缓冲区
6. 当DMA读取了足够多的数据，就向CPU发送中断信号
7. CPU收到信号后，知道数据已经准备好了，将数据从内核缓冲区拷贝到用户空间，系统调用返回

C++八股文

#define和const的区别

1. 类型和安全检查不同
   1. 宏定义是字符替换，没有数据类型的区别，并且这种替换没有类型安全检查，可能产生边际效应等错误；
   2. const是常量的声明，有类型区别，在编译阶段会进行类型的检查
2. 编译器处理不同
   1. 宏定义是一个“编译时”概念，在预处理阶段展开，因此不能对宏定义进行调试
   2. const常量是一个“运行时”的概念，在程序运行使用，相当于一个只读数据
3. 存储方式不同
   1. 宏定义是直接替换，不会分配内存，存储在程序的代码段中
   2. const常量需要进行内存分配，存储在程序的数据段中
4. 定义域不同
   在函数1内使用#define N 12和const int n=12，在函数2内可以使用N，不可以使用n
5. 是否可以取消定义
   1. 宏定义可以通过#undef来使之前的宏定义失效，取消后可以重新定义
      2.const常量定义之后在定义域内永久有效
6. 作为函数参数
   1. 宏定义不能作为参数传递给函数
   2. const常量可以在函数的参数列表中出现

static的作用

1. 修饰普通变量：修改变量的存储区域和生命周期，存储在静态区，有初始值就用初始值初始化，没有的话就用默认值初始化：
   1. 全局变量：只能在本文件内访问，即使是extern声明也不可以
   2. 局部变量：离开作用域，内存不会释放，但不能访问，只有再次进入作用域才可访问，并且值不变。在程序执行到该对象的声明处时被首次初始化，即以后的函数调用不再进行初始化。
2. 修饰普通函数：只在本文件可以使用，防止与他人的命名空间中的同名函数冲突
3. 修饰成员变量：使得该类的所有实例只保存一个该变量，并且不用生成对象就能通过类名::变量名访问
4. 修饰成员函数：不需要生成对象就能使用函数，但是不能访问非静态成员

inline内联函数

1. 特征：
   1. 把内联函数里的代码复制到内联函数调用处
   2. 相当于宏，但是比宏多了类型检查，真正具有函数特性
   3. 内联相当于对编译器的一个建议，具体是否内联看编译器选择。编译器一般不内联包含循环、递归等复杂操作的内联函数
   4. 类中定义的函数，除了虚函数以外都会自动隐式地当成内联函数
2. 优点：
   1. 内联函数和宏函数一样在调用时展开，省去了函数调用的开销
   2. 内联函数比宏函数多了类型检查
   3. 内联函数在运行时可调试，而宏定义不行
3. 缺点：
   1. 代码膨胀，每一次内联函数调用都要复制代码，消耗内存空间
   2. 是否内联对程序员来说不可控，内联是建议，具体是否内联看编译器决定
4. Q：虚函数可以是内联函数吗？
   内联是可以修饰虚函数的，但是当虚函数表现为多态时不能被内联：内联是在编译期建议编译器内联，而虚函数的多态在运行时才能动态确定调用哪个函数，所以虚函数表现为多态时不能内联。

volatile关键字

• 用来修饰变量，表示该变量可以被某些编译器未知的因素更改，比如操作系统、硬件或者其他线程。
• 遇到这个关键字声明的变量，编译器对该变量访问的代码不进行优化：系统总是重新从他所在的内存读取数据，即使它前面的指令刚刚读取过，而且读取的数据立刻被保存。
  • 如果是被优化的做法：编译器发现两次读取数据的代码没有对该数据进行操作，会自动使用上次读的数据

assert()

• 断言——是宏而不是函数，定义在头文件<assert.h>(C)、<cassert>(C++)中
• 作用：如果条件返回错误，则终止程序执行

1
2
3
4

#define NDEBUG          // 加上这行，则 assert 不可用
#include <assert.h>

assert( p != NULL );    // assert 不可用

pragma pack(n)

设定结构体、联合体以及类成员变量以n字节方式对齐

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

#pragma pack(push)  // 保存对齐状态
#pragma pack(4)     // 设定为 4 字节对齐

struct test1
{
    char m1;
    double m4;
    int m3;
};

#pragma pack(pop)   // 恢复对齐状态
struct test2
{
    char m1;
    double m4;
    int m3;
};

int main()
{
    cout<<sizeof(test1)<<endl;   //16=4+8+4
    cout<<sizeof(test2)<<endl;   //24=8+8+8
}

C++中的class和struct

• struct更适合看成一个数据结构的实现体=各种数据类型的集合
• class更适合看成一个对象的实现体=一个对象的方法和属性的集合
  区别：

1. 默认的访问属性不同：struct默认是public，class默认是private
2. 默认的继承方式不同：struct默认的继承方式是public，class默认是private

union

union是一种节省空间的特殊的类，可有多个数据成员，但是在任意时刻只有一个数据成员可以有值，当某个成员变量被赋值后其他成员变为未定义状态
特点：

1. 默认访问控制符为public
2. 可以有构造函数和析构函数
3. 不能有引用类型的成员变量
4. 不能有虚函数
5. 不能继承自其他类，不能作为基类
6. 联合体的大小=最大的那个成员变量的大小

explicit

——C++新标准出现的一个关键字
explicit作用：表明该构造函数是显式的，而非隐式的，不能进行隐式转换
相对应的另一个是implicit，类构造函数默认情况即声明为implicit，表示这个类是可以隐式构造的，但是implicit不是关键字，只能说是编译器的一种修饰，不能自己写上

隐式：编译器完成的转换，int a=1;float b=3;float sum=a+b这里编译器将a隐式地转换为了float
显式：用户完成的转换，float a=1;float b=3;int sum=(int)a+(int)b;这里a和b被显式的转化为了float

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

class A{
public:
	// explicit
    A(int a,int b):a(a),b(b){};
    int b;
    int a;
};
void f1(A a){
    cout<<a.a<<" "<<a.b<<endl;
}

int main(){
    A tmp1=A(1,2);  // 显示构造
    A tmp2={10,20}; // 隐式构造,如果加上explicit禁止隐式构造
    f1(tmp1);
    f1(tmp2);
}

friend友元类和友元函数

在C++中，一个类中可以有public protected private三种属性的成员，通过对象可以访问public成员，只有本类中的函数可以本类的private成员。
一种例外情况：友元，借助友元，可以使得其他类中的成员函数以及全局范围内的函数能够访问当前类的private成员

友元函数

在当前类中定义的，不属于当前类的成员函数也可以在类中声明，但要在前面加friend关键字，这样就构成了友元函数。
友元函数可以是不属于任何类的非成员函数和，也可以是其他类的成员函数

1. 将非成员函数声明为友元函数

   1 2 3 4 5 6

   class Student{ private: int name; public: friend void show(Student *stu); }

   注意：友元函数不同于成员函数，不能直接访问类的成员，必须借助对象
   因为成员函数在调用时会隐式地增加this指针，指向调用它的对象，从而使用该对象的成员;而show()是非成员函数，没有this指针，所以编译器不知道使用哪个对象的成员，所以必须通过参数传递对象，并通过对象访问成员。

2. 将其他类的成员函数声明为友元函数

   1 2 3 4 5 6 7 8 9

   class Address; class Student{ private: void show(Address *addr); }; class Address{ public: friend void Student::show(Address *addr); };

• 因此Student中show函数就可以访问Address中的成员变量
• 注意提前声明Address类
• 需要将show的声明和实现分开，将Address的声明放在中间，这是因为编译器从上到下编译代码，show中函数体用到了Address的成员，如果不提前知道Address的具体声明内容，就不能确定Address是否拥有该成员
• 一个函数可以被多个类声明为友元函数，这样就可以访问多个类的private成员

友元类

将整个类声明为另一个类的友元类，友元类中所有的成员函数都是另一个类的友元函数

1
2
3
4
5
6
7
8

class Address;
class Student{
	...
};
class Address{
public:
	friend class Student;
};

内核模块包过滤防火墙的原型实现

1.原型系统的总体设计

分为两部分独立实现

1. 运行在应用层的过滤规则配置程序，用来设置和启用包过滤规则和配置相应的规则参数，包括要控制的协议类型、IP地址、端口等
2. 实现IP报文过滤的内核模块，通过在Netfilter框架中注册钩子函数的方式来实现对IP数据包的过滤和控制

• 内核模块不能直接访问规则配置程序中的过滤规则，所以通过注册设备文件结点的方式实现应用程序和内核之间的通信，传递所配置的过滤规则和参数

2.规则配置程序的设计

主要完成两方面的工作：

1. 从用户的输入命令中解析出报文过滤规则
2. 创建一个新的设备文件，通过写该设备文件，将所设置的过滤规则传递给Linux内核模块

3.内核模块的设计

主要功能是对收到的数据包进行过滤，即依据所配置的过滤规则，丢弃与所配置报文信息特征相匹配的数据包，包括四个部分

1. 新设备文件的驱动：目的是获取规则配置程序向内核模块发送的过滤规则，也就是接收从规则配置程序写入设备文件的内容，将该内容保存到内核模块的变量中
2. 报文过滤控制函数：包括一个总入口函数和一组具体规则判断函数。该函数在模块初始化阶段会被注册到Netfilter框架的相应钩子点上，当报文经过时，该函数将会被自动调用，根据过滤规则，对是否过滤该IP报文进行逻辑判断，将判断结果作为函数返回值，Netfilter根据函数的返回值进行报文过滤，放行还是阻止
3. 内核模块的初始化函数：该函数在内核模块加载时被Linux自动调用，主要包括两方面的初始化工作：
   1. 注册新设备文件的驱动
   2. 将报文过滤控制函数注册到Netfilter框架的相应钩子点上，本系统是挂在IP_POST_ROUTING，即在对收到的报文做路由处理后执行包过滤，注册完成后，每次报文在路由处理后执行包过滤
4. 内核模块的注销函数：该函数在内核模块注销时被Linux自动调用，主要完成设备文件驱动的注销，以及从Netfilter框架中注销钩子函数

4.测试

1. ping功能测试

   1	ping 10.160.101.243

   此时可以ping通，打开防火墙

   1	./configure -p ping -y 10.160.101.243

   再次ping该ip，无响应
   使用dmesg | tail查看控制信息

   1 2 3 4

   [12103.702553] input info: p=1, x=0 y=-211443702 m=0 n=0 [12212.302296] An ICMP packet is denied! [12213.304010] An ICMP packet is denied! [12214.327981] An ICMP packet is denied!

2. udp报文过滤测试
   查看本地DNS服务器

   1	cat /etc/resolv.conf

   配置这条信息后，不能以域名形式访问外网服务器，但能够以IP地址的形式访问外网服务器

   1	./configure -p udp -y 127.0.0.53

   1 2 3 4 5

   [ 8225.935267] input info: p=17, x=0 y=889192575 m=0 n=0 [ 8234.208966] A UDP packet is denied! [ 8234.209040] A UDP packet is denied! [ 8234.209100] A UDP packet is denied! [ 8234.209212] A UDP packet is denied!

3. tcp报文过滤测试
   使用 hping3 工具发送一个 TCP SYN 报文到指定的目标 IP 地址和端口

   1	hping3 -c 1 -S -p 80 10.160.101.243

   配置规则之后

   1 2 3

   hping3 -c 1 -S -p 80 10.160.101.243 HPING 10.160.101.243 (ens33 10.160.101.243): S set, 40 headers + 0 data bytes [send_ip] sendto: Operation not permitted

   1 2 3

   [13043.943593] input info: p=6, x=0 y=-211443702 m=0 n=20480 [13051.969525] A TCP packet is denied! [13068.720651] A TCP packet is denied!

5.源代码

1. configure.c

   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 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128

   #include <sys/types.h> #include <sys/stat.h> #include <stdio.h> #include <fcntl.h> #include <unistd.h> #include <string.h> #include <stdlib.h> #include <arpa/inet.h> #include <netinet/in.h> // 规则配置程序定义5个全局变量，保存用户通过命令行选项配置的控制信息 unsigned int g_controlledProtocol = 0; unsigned short g_controlledSrcport = 0; unsigned short g_controlledDstport = 0; unsigned int g_controlledSaddr = 0; unsigned int g_controlledDaddr = 0; int getpara(int argc, char* argv[]); void display_usage(char* commandname); int main(int argc, char* argv[]) { char controlinfo[128]; // 规则信息的缓冲区 int controlinfoLen = 0; // 规则信息长度，0：关闭防火墙 int fd; // 设备文件打开后的文件描述符 struct stat buf; // 用于获取设备文件是否存在的临时缓冲区 if (argc == 1) { // 不带参数表示要关闭防火墙，把传入的规则长度置为0，关闭防火墙的报文检查控制功能 controlinfoLen = 0; } else { getpara(argc, argv); // 获取命令行选项中规则信息到相应的全局变量 // 规则信息顺序：协议类型、源IP、目的IP、源端口、目的端口 // 每个字段占四个字节 *(int*)controlinfo = g_controlledProtocol; *(int*)(controlinfo + 4) = g_controlledSaddr; *(int*)(controlinfo + 8) = g_controlledDaddr; *(int*)(controlinfo + 12) = g_controlledSrcport; *(int*)(controlinfo + 16) = g_controlledDstport; controlinfoLen = 20; // 设置规则信息的长度 } if (stat("/dev/controlinfo", &buf) != 0) { // 用stat调用来测试设备文件是否已经存在 /* 如果设备文件不存在，则先调用mknod创建设备文件， 注意创建设备文件的参数要和内核中设备注册的相应参数一致 */ if (system("mknod /dev/controlinfo c 124 0") == -1) { /* 创建设备文件:mknod /dev/controlinfo c 124 0: 创建一个字符型设备文件"/dev/controlinfo"， 并指定设备号为124，设备的权限为0。 */ printf("Cannot create the device file!\n"); printf("Please check and try again!\n"); exit(1); } } // O_RDWR：读写方式打开，S_IRUSR：用户可读权限，S_IWUSR：用户可写权限 fd = open("/dev/controlinfo", O_RDWR, S_IRUSR | S_IWUSR); // 打开设备文件 if (fd > 0) { write(fd, controlinfo, controlinfoLen); } else { perror("Cannot open /dev/controlinfo \n"); exit(1); } close(fd); } int getpara(int argc, char* argv[]) { int optret; unsigned short tmpport; // 保存端口的临时变量 optret = getopt(argc, argv, "pxymnh"); while (optret != -1) { switch (optret) { case 'p': // 协议类型 // ICMP/TCP/UDP的协议类型分别为1，6，17 if (strncmp(argv[optind], "ping", 4) == 0) g_controlledProtocol = 1; else if (strncmp(argv[optind], "tcp", 3) == 0) g_controlledProtocol = 6; else if (strncmp(argv[optind], "udp", 3) == 0) g_controlledProtocol = 17; else { printf("Unknown protocol!Please check and try again\n"); exit(1); }; break; case 'x': // 源IP // inet_aton用于将十进制点分IP地址格式转化为32位整数 if (inet_aton(argv[optind], (struct in_addr*)&g_controlledSaddr) == 0) { // 不是有效的ip地址 printf("Invalid source ip address!Please check and try again\n"); exit(1); } break; case 'y': // 目的IP if (inet_aton(argv[optind], (struct in_addr*)&g_controlledDaddr) == 0) { printf("Invalid destination ip address!Please check and try again\n"); exit(1); } break; case 'm': // 源端口 tmpport = atoi(argv[optind]); if (tmpport == 0) { // 转换失败或者非整数 printf("Invalid source port!Please check and try again\n"); exit(1); } g_controlledSrcport = htons(tmpport); // 转化为网络字节序 break; case 'n': // 目的端口 tmpport = atoi(argv[optind]); if (tmpport == 0) { // 转换失败或者非整数 printf("Invalid destination port!Please check and try again\n"); exit(1); } g_controlledDstport = htons(tmpport); // 转化为网络字节序 break; case 'h': // 帮助信息 display_usage(argv[0]); exit(1); default: display_usage(argv[0]); exit(1); } optret = getopt(argc, argv, "pxymnh"); } } void display_usage(char* commandname) { printf("Usage1: %s \n", commandname); // 后不跟任何参数，即关闭防火墙功能 printf("Usage2: %s -p protocol -x sourceip -y destinationip -m sourceport -n destinationport\n", commandname); }

2. mod_firewall.c

   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 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241

   #include <linux/kernel.h> #include <linux/module.h> #include <linux/types.h> #include <linux/if_ether.h> #include <linux/netfilter.h> #include <linux/netfilter_ipv4.h> #include <linux/tcp.h> #include <linux/ip.h> #include <linux/icmp.h> #include <linux/udp.h> #include <linux/fs.h> #include <linux/uaccess.h> // for copy_from_user #define MATCH 1 // 表示端口、ip地址的匹配结果和要控制的IP地址端口一致 #define NMATCH 0 // 函数原型 int port_check(unsigned short srcport, unsigned short dstport); int ipaddr_check(unsigned int saddr, unsigned int daddr); int icmp_check(void); int tcp_check(void); int udp_check(void); unsigned int hook_func(void *priv, struct sk_buff *skb, const struct nf_hook_state *state); ssize_t write_controlinfo(struct file *file, const char __user *buf, size_t len, loff_t *offset); static int __init initmodule(void); static void __exit cleanupmodule(void); // 过滤信息类变量 unsigned int g_controlledProtocol = 0; // 表示要控制的协议类型，1:ICMP,6:TCP,17:UDP unsigned short g_controlledSrcport = 0; // 表示要控制的源端口，该变量只对TCP和UDP报文有效 unsigned short g_controlledDstport = 0; // 该变量只对TCP和UDP报文有效 unsigned int g_controlledSaddr = 0; unsigned int g_controlledDaddr = 0; int g_enableFlag = 0; // 设备驱动变量 struct file_operations fops = { .owner = THIS_MODULE, .write = write_controlinfo, }; static struct nf_hook_ops myhook; struct sk_buff* tmpskb; struct iphdr* piphdr; module_init(initmodule); module_exit(cleanupmodule); MODULE_LICENSE("GPL"); // 函数实现 int port_check(unsigned short srcport, unsigned short dstport) { if (g_controlledSrcport == 0 && g_controlledDstport == 0) { return MATCH; } if (g_controlledSrcport != 0 && g_controlledDstport == 0) { if (g_controlledSrcport == srcport) { return MATCH; } else { return NMATCH; } } if (g_controlledSrcport == 0 && g_controlledDstport != 0) { if (g_controlledDstport == dstport) { return MATCH; } else { return NMATCH; } } if (g_controlledSrcport != 0 && g_controlledDstport != 0) { if (g_controlledSrcport == srcport && g_controlledDstport == dstport) { return MATCH; } else { return NMATCH; } } return NMATCH; // 正常情况不会运行到这 } int ipaddr_check(unsigned int saddr, unsigned int daddr) { if (g_controlledSaddr == 0 && g_controlledDaddr == 0) { return MATCH; } if (g_controlledSaddr != 0 && g_controlledDaddr == 0) { if (g_controlledSaddr == saddr) { return MATCH; } else { return NMATCH; } } if (g_controlledSaddr == 0 && g_controlledDaddr != 0) { if (g_controlledDaddr == daddr) { return MATCH; } else { return NMATCH; } } if (g_controlledSaddr != 0 && g_controlledDaddr != 0) { if (g_controlledSaddr == saddr && g_controlledDaddr == daddr) { return MATCH; } else { return NMATCH; } } return NMATCH; // 正常情况不会运行到这 } int icmp_check(void) { struct icmphdr* picmphdr; // ICMP报文紧跟在IP头部之后，IP报文头长piphdr->ihl*4,ip报文头右移32bit picmphdr = (struct icmphdr*)(tmpskb->data + (piphdr->ihl * 4)); if (picmphdr->type == 8) { // 客户端向远程主机发出的ping请求报文 if (ipaddr_check(piphdr->saddr, piphdr->daddr) == MATCH) { printk("An ICMP packet is denied!\n"); return NF_DROP; } } if (picmphdr->type == 0) { // 远程主机向客户端发出的ping响应报文 // 注意将响应报文的目的ip与要控制的源ip，报文的源ip跟要控制的目的ip作比较 if (ipaddr_check(piphdr->daddr, piphdr->saddr) == MATCH) { printk("An ICMP packet is denied!\n"); return NF_DROP; } } // 其他类型ICMP或者不是要控制的，通行 return NF_ACCEPT; } int tcp_check(void) { struct tcphdr* ptcphdr; // TCP报文紧跟在IP头部之后，IP报文头长piphdr->ihl*4,ip报文头右移32bit ptcphdr = (struct tcphdr*)(tmpskb->data + (piphdr->ihl * 4)); if (ipaddr_check(piphdr->saddr, piphdr->daddr) == MATCH && port_check(ptcphdr->source, ptcphdr->dest) == MATCH) { printk("A TCP packet is denied!\n"); return NF_DROP; } else { return NF_ACCEPT; } } int udp_check(void) { struct udphdr* pudphdr; pudphdr = (struct udphdr*)(tmpskb->data + (piphdr->ihl * 4)); if (ipaddr_check(piphdr->saddr, piphdr->daddr) == MATCH && port_check(pudphdr->source, pudphdr->dest) == MATCH) { printk("A UDP packet is denied!\n"); return NF_DROP; } else { return NF_ACCEPT; } } unsigned int hook_func(void *priv, struct sk_buff *skb, const struct nf_hook_state *state) { // skb 为指向 netfilter 正在处理报文缓冲区的指针 if (!g_enableFlag) { return NF_ACCEPT; } tmpskb = skb; // 获得报文缓冲区的指针 piphdr = (struct iphdr *)skb_network_header(tmpskb); if (piphdr->protocol != g_controlledProtocol) { return NF_ACCEPT; } if (piphdr->protocol == 1) { return icmp_check(); } else if (piphdr->protocol == 6) { return tcp_check(); } else if (piphdr->protocol == 17) { return udp_check(); } else { // 其他协议，默认放行，一般不会运行到这 printk("Unknown type of packet!\n"); return NF_ACCEPT; } } ssize_t write_controlinfo(struct file *file, const char __user *buf, size_t len, loff_t *offset) { char controlinfo[128]; // 用于保存所写入数据的内核空间缓冲区 char* pchar; // 临时缓冲区指针 pchar = controlinfo; if (len == 0) { // 写入内容为0，表示关闭防火墙 g_enableFlag = 0; printk("Firewall is closed!\n"); return len; } // 调用函数 copy_from_user 将规则配置程序传入的用户配置信息复制到内核空间缓存区 if (copy_from_user(controlinfo, buf, len) != 0) { printk("Can't get the control rule!\n"); printk("Something may be wrong, please check it!\n"); return 0; } // 将规则赋给全局变量 g_controlledProtocol = *((int*)pchar); pchar = pchar + 4; g_controlledSaddr = *((int*)pchar); pchar = pchar + 4; g_controlledDaddr= *((int*)pchar); pchar = pchar + 4; g_controlledSrcport= *((int*)pchar); pchar = pchar + 4; g_controlledDstport= *((int*)pchar); g_enableFlag = 1; printk("input info: p=%d, x=%d y=%d m=%d n=%d\n", g_controlledProtocol, g_controlledSaddr, g_controlledDaddr, g_controlledSrcport, g_controlledDstport); return len; } static int __init initmodule(void) { int ret; printk("Init Module\n"); myhook.hook = hook_func; myhook.hooknum = NF_INET_POST_ROUTING; myhook.pf = PF_INET; myhook.priority = NF_IP_PRI_FIRST; nf_register_net_hook(&init_net, &myhook); ret = register_chrdev(124, "/dev/controlinfo", &fops); if (ret != 0) { printk("Can't register device file!\n"); } return 0; } static void __exit cleanupmodule(void) { nf_unregister_net_hook(&init_net, &myhook); unregister_chrdev(124, "controlinfo"); printk("CleanUp\n"); }

3. Makefile

   1 2 3 4 5 6 7 8 9 10 11

   CC := gcc-13 obj-m += mod_firewall.o KDIR := /lib/modules/$(shell uname -r)/build PWD := $(shell pwd) default: $(MAKE) -C $(KDIR) M=$(PWD) modules $(CC) -o configure configure.c clean: rm -f *.o *.ko *.mod.c *.mod.o *.symvers *.order configure *.mod

vscode C++ launch.json和task.json配置

launch.json

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

{
    "version": "0.2.0",
    "configurations": [
        {
            "name": "g++.exe - 生成和调试活动文件",
            "type": "cppdbg",
            "request": "launch",
            "program": "${fileDirname}\\${fileBasenameNoExtension}.exe",
            "args": [],
            "stopAtEntry": false,
            "cwd": "${workspaceFolder}",
            "environment": [],
            "externalConsole": false,
            "MIMode": "gdb",
            "miDebuggerPath": "E:\\MinGW\\mingw-w64\\mingw64\\bin\\gdb.exe",#修改自己的 gdb地址
            "setupCommands": [
                {
                    "description": "为 gdb 启用整齐打印",
                    "text": "-enable-pretty-printing",
                    "ignoreFailures": true
                }
            ],
            "preLaunchTask": "C/C++: g++.exe build active file"
        }
    ]
}

task.json

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

{
    "version": "2.0.0",
    "tasks": [
        {
            "type": "shell",
            "label": "C/C++: g++.exe build active file",
            "command": "E:\\MinGW\\mingw-w64\\mingw64\\bin\\g++.exe",#修改自己的g++地址
            "args": [
                "-g",
                "${file}",
                "-o",
                "${fileDirname}\\${fileBasenameNoExtension}.exe"
            ],
            "options": {
                "cwd": "${workspaceFolder}"
            },
            "problemMatcher": [
                "$gcc"
            ],
            "group": {
                "kind": "build",
                "isDefault": true
            }
        }
    ]
}

包过滤防火墙

包过滤防火墙的主要功能：对所通过的IP数据包按照既定的包过滤规则进行检查和控制，“过滤”掉不能满足要求的IP数据包

1.包过滤防火墙工作原理

包过滤防火墙通常嵌入在连接内外网的路由器（或网关）上，包过滤操作是在IP层实现的。

• 普通的路由器只检查数据包的目的地址，并选择一个达到目标地址的最佳路径，或者通知数据包的发送者“数据包”不可达。
• 嵌入包过滤防火墙的路由器会检查经过的IP数据包，除了决定是否有到达目标地址的路径外，包过滤防火墙还会对接收的数据包作出允许或者拒绝通过的决定

2.包过滤防火墙工作流程

包过滤防火墙的报文处理流程：

1. 从网关的IP协议层截获所有经过该网关的IP数据包，或者截获需要进行控制的IP数据包
2. 对截获的IP数据包的包头进行分析，提取相应的网络访问属性
3. 根据IP数据包的网络访问属性，解释或执行所选取的包过滤规则
4. 基于IP数据包的网络访问属性，解释或执行所选取的包过滤规则，得出针对于该IP数据包的访问判决。如果没有找到合适的包过滤规则，则根据默认的包处理方式得到该IP数据包的访问判决
   5.根据判决结果，直接丢弃所截获的IP数据包，或者让IP协议层继续进行路由处理

3.包过滤防火墙的优缺点

1.优点：

• 包过滤防火墙工作在IP层，不需要改变客户端的任何应用程序
• 包过滤防火墙工作在IP层，最多分析对应的传输层协议，协议处理比较简单，处理包的速度比应用代理防火墙快
  2.缺点：包过滤防火墙针对IP数据包进行报文过滤，而不是对应用层回话进行网络访问控制，不会分析IP数据包的上层语义
• 包过滤防火墙在IP层实现网络访问控制，而用户认证是应用层的概念，因此包过滤防火墙不支持有效的用户认证
• 包过滤防火墙一般基于单个IP数据包进行控制，很少分析IP数据包之间的关系以及对应的高层语义信息
• 包过滤防火墙所能接触的信息少，生成的日志通常只包括通过数据包捕获的通信时间、IP地址、端口等低层信息