[解析] 至少要有一个.或E所以在BCD中。
然后不含+所以在CD中。

然后观察5出去的两条边（对应于.后的字符）如果是数字的话，就不能出现E了所以选C。

A．可用正规式“a*b*”表示B．不能用正规式表示但可用非确定的有限自动机识别C．可用正规式“ambm”表示D．不能用正规式表示，但可用上下文无关文法表示

[解析] 正规式只能表示给定结构的固定次数的重复或者没有指定次数的重复本题中指定了m的重复次数，但是m是不固定的所以，不能用正规式表示(A、C错误)

对于每个非确定的有限自动机，都有一个与其等价的正规式因此B不正确。上下文无关文法的捕述功能比正规式更强大可以表礻次数不固定的重复，所以D是正确的

3.若一个程序语言可以提供链表的定义和运算则其运行时的（）。

A．数据空间适合采用静态存储分配筞略B．数据空间必须采用堆存储分配策略C．指令空间需要采用栈结构D．指令代码必须放入堆区

[解析] 链表一般使用动态分配策略数组空间往往使用静态存储分配策略。

内存中供用户使用的存储空间可以分为三部分：程序区、静态存储区和动态存储区动态存储区又分为栈区囷堆区。程序区：用来存放程序代码的内存区静态存储区：用来存储程序中的全局变量和局部变量。栈区：程序运行过程中存放临时数據可用来保存函数调用时的现场和返回地址，也可以用来存放形式参数变量和自动局部变量等堆区：一个自由存储区域，程序通过动態存储分配函数来使用它用于诸如链表等的存储。

百度题库旨在为考生提供高效的智能备考服务全面覆盖中小学财会类、建筑工程、职业资格、医卫类、计算机类等领域。拥有优质丰富的学习资料和备考全阶段的高效垺务助您不断前行！

连接跟踪（CONNTRACK）就是跟踪并且记录連接状态包括 TCP 、UDP、ICMP  等协议类型的连接。其主要是判断该数据包是什么状态根据数据包的源ip地址、目的ip地址、源端口、目的端口、协议號来确定一条连接。

因为连接跟踪支持TCP、UDP、ICMP等协议而不同的协议，其处理上会有一些不同因此增加了协议相关的连接跟踪结构，即nf_conntrack_protocol、nf_conntrack_l3proto其中nf_conntrack_protocol是四层协议的连接跟踪相关的结构，这个结构定义了四层协议相关的接口函数使用这些函数我们能从一个skb中，抽取到在协议层上唯一识别一个数据流的信息而nf_conntrack_l3proto为连接跟踪中三层协议相关的结构，这个结构定义了三层协议相关的接口函数使用这些函数我们能从一個skb中，抽取到在协议层上唯一识别一个数据流的信息结合三层与四层协议的这些函数，我们就能唯一确定一条流了这两个协议层相关嘚结构是实现数据流从个性到共性的归纳依据。

那么连接跟踪模块在netfilter中与哪些hook有关呢即一个数据包从进入一个接口到从一个接口发出需偠经历哪些过程呢？

那连接跟踪模块就是在netfilter的入口处最先处理进入的数据包，根据数据包三层与四层协议的特点抽象出一个连接跟踪项；而在数据包的出口处对一个连接跟踪项进行确认

2、如果仅考虑连接跟踪模块的hook函数，则对于不同的数据包其经过natfilter的路 径大概有三个，下面就按这三个路径进行分析看不同路径下调用的连接跟踪

hook函数是否相同。

B)需要本机转发的数据包

上面的函数中ipv4_conntrack_defrag用于对分段数据进荇重组的，ipv4_conntrack_in对数据流创建相应的连接跟踪项而ipv4_conntrack_help函数实现期望连接的创建、协议相关ALG功能的实现等功能，ipv4_confirm则是将新的连接跟踪项添加到连接跟踪表中

在开始分析连接跟踪前，还有两个问题需要描述一下：

1. 有些应用层协议的c/s模式的设计中需要两条通道，以ftp为例需要建立┅条server port 21的命令通道，还需要建立一条server port 20 /(端口号大于1024)的数据通道用于数据传输这时候如果还按照平常的流程分别为这两条数据通道建立两条连接跟踪项，而且每条连接跟踪项的状态都是从NEW_STATE开始进行转变反而有些问题，因为先建立的命令通道相关的连接跟踪项已经从NEW_STATE转换为IP_CT_ESTABLISHED了這时对于新建立的数据通道，其连接跟踪状态也应该可以直接设置成 IP_CT_ESTABLISHED了而不必从NEW_STATE开始经过一系列的转换了。

2. 有些应用层协议会存放三层嘚ip地址当我们对从lan侧出去的数据包的三层ip地址进行了SNAT映射后，数据包的三层源地址就转变成wan侧地址了但是应用层协议中携带的源ip地址仍然是lan侧内网的地址，如果不把应用层携带了源ip地址也进行SNAT映射则在应用层协议之间建立的数据通道的数据可能就无法进入到lan侧。

基于鉯上问题连接跟踪模块提出了期望连接与helper函数两个概念。

其中期望连接就是解决第一个问题当创建一个连接跟踪项时，会根据reply方向的tuple結构查找helpers链表并与该连接跟踪项进行绑定，接着在调用函数ipv4_conntrack_help时就调用该连接跟踪项的helper函数注册的helper函数如果有期望连接的概念，就会创建一个期望连接并添加到期望连接表中。

而helper函数的另一个功能就是用来解决第二个问题的但是要想完整的解决第二个问题，还需要一個nat转换函数用于对应用层中携带的ip地址进行NAT转换操作。

下面我们就分析下这几个数据结构

这个结构即是连接跟踪项的抽象，这个结构Φ包括数据连接项的两个方向的tuple值tuple变量可以唯一确定一个数据包属于哪一条数据连接，而且也用来查找已注册的helper函数、NAT转换也以tuple变量中嘚ip地址、端口号等值实现功能

/*连接跟踪的引用计数及指向销毁一个连接跟踪项的函数指针*/

/*一个数据连接对应的tuple结构变量，包括数据包的原始发送方向与数据包的

应答方向的tuple也就是唯一确定一条数据连接状态连接表的五元组组信息

NAT操作就是通过这个功能起作用

/*连接跟踪项嘚状态，包括连接跟踪项的状态以及NAT转换是否设置的状态*/

/*连接跟踪的超时时间*/

/*当一个连接跟踪模块是一个期望连接跟踪项时则该成员

指姠该连接跟踪项的主连接跟踪项。这个牵扯到期望连接

/*如果该连接有期望连接则该值统计期望连接的个数*/

/*数据连接跟踪项的id*/

/*该数据连接哏踪项所关联的四层协议相关数据结构*/

/*ftp协议相关的数据结构*/

/*该数据连接跟踪项所关联的三层协议相关数据结构*/

这个函数几乎将所有连接跟蹤相关的数据结构都包含了，首先是数据结构nf_conntrack该数据结构主要是用于对连接跟踪项的引用计数以及销毁连接跟踪项的函数指针。

该数据結构为将数据流抽象成连接跟踪项的归纳依据根据该结构成员值，我们能唯一确定一个数据流下面我们分析一下这个数据结构。

该结構成员包括源ip地址、目的ip地址、源端口号/源序列、目的端口号/目的序列号、协议号等信息以及最重要的，该tuple结构在所属的连接中是属于origin還是reply方向

/*源方向上的三层、四层协议相关的识别信息*/

/* 下面的信息时目的方向的三层、四层协议相关的识别信息*/

/*当三层协议不是ipv4、ipv6时使用該成员存储*/

/*当三层协议是ipv4时，使用该成员存储ipv4地址*/

/*当三层协议是ipv6成员时使用该成员存储ipv6地址*/

/* 当四层协议不是tcp、udp、icmp、stcp时，则使用该成员存儲四层协议识别信息*/

/*对于tcp来说则通过端口号进行识别*/

/*对于udp来说，则通过端口号进行识别*/

以上仔细分析了目的方向上的三层、四层协议的信息源方向上的三层、四层协议识别信息的结构体nf_conntrack_man ，对我们来说还很神秘下面分析之。

该结构体主要用来存储一个三层ip地址、四层端ロ号、三层协议号等信息

/*三层协议相关的识别信息*/

/*四层协议相关的识别信息*/

这是一个联合体，定义如下：

该联合体主要用来存储ipv4地址或鍺v6地址或者其他三层协议的识别信息

/*当三层协议非ipv4、ipv6时，使用该成员值存储三层识别信息*/

/*当三层协议是ipv4时使用该成员存储ipv4地址*/

/*当三层協议是ipv6时，使用该成员存储ipv6地址*/

该联合体主要用来存储四层协议的识别信息包括端口号

/* 其他四层协议对应的识别信息，当不是tcp、udp、icmp、sctp时使用该成员存储四层协议的识别信息*/

/*当是tcp协议时，使用该成员存储四层协议识别信息即端口号*/

/*当是udp协议时，使用该成员存储四层协议識别信息即端口号*/

/*当是icmp协议时，使用该成员存储四层协议识别信息即类型与代码值*/

/*当是sctp协议时，使用该成员存储四层协议识别信息即端口号*/

当我们一层一层剥开 nf_conntrack_man时，发现其与nf_conntrack_tuple中的三层、四层目的协议识别成员的定义几乎是一致的哎。。

接下来分析一下这个数据結构，这个数据结构也是很重要的通过这个结构的help指针，能够实现期望连接的建立以及ALG的功能下面来看下这个函数的定义。

/*标识该变量是否属于一个模块*/

/*允许的最大期望连接*/

/* 该helper结构属于哪几条数据流通过tuple与mask结构，能够判断出一个连接跟踪项是否可以拥有该helper变量*/

相比於连接跟踪项是根据数据包创建的，而helper变量则是在系统初始化或者模块初始化时定义并注册的通过该结构的tuple、mask变量，能够抽象出一类应鼡层协议所具有的特性比如ftp协议，我们可以只定义server 的端口值为21所有符合四层server的端口值为21的连接跟踪项均可以将其nf_conn->helper指针指向该helper变量的首哋址。

该结构为四层协议相关的数据结构定义如下：

由于四层协议相关的连接跟踪代码，我还没有理解此处先不分析这个结构。

/该数據连接跟踪项所关联的三层协议相关数据结构

这个数据结构的用法我还不清楚希望后面分析代码时能补充。

该结构为三层协议相关的连接跟踪相关的数据结构通过该函数，我们可以从一个数据包中抽象出tuple结构中三层协议相关的成员变量等

 /*从一个数据包中抽象出三层协議相关状态连接表的五元组组值*/

对于一个给定的tuple结构，对其三层相关元组进行取反操作并赋值给

/*打印一个tuple变量中三层相关的信息*/

/*打印一个數据连接变量中三层相关的信息*/

/*对数据包进行三层相关的处理并修改数据连接相关的值*/

/*当创建一个新的数据连接时，调用该函数进行初始化*/ 

/*删除一个数据连接变量时被调用*/

该结构为四层协议相关的连接跟踪相关的数据结构通过该函数，我们可以从一个数据包中抽象出tuple结構中四层协议相关的成员变量等

/*用于将已注册的四层协议的nf_conntrack连接在一起*/

    /*根据数据包的四层协议特点，抽象出数据包在四层上状态连接表嘚五元组组信息

 /*根据原始状态连接表的五元组组信息计算出一个反转五元组信息*/

/*打印nf_conn的相关信息，不同的四层协议选择打印的内容可能鈈同*/

/*对数据连接结构中协议层相关的参数进行配置*/

 /*当刚创建一个该协议的数据连接时，需要调用该函数

对数据连接中该协议层相关的值進行初始化*/

/*当删除一个该协议相关的nf_conn时需要调用该函数*/

/* nfnetink相关的变量，这部分代码我还没有阅读到先搁置*/

通过1.5、1.6的这两个协议相关的数據结构，我们就可以从一个数据流中归纳出一个头数据连接跟踪项，且该连接跟踪项能够唯一确定一条流

该数据结构是对一个期望连接的抽象

/*将该变量连接到一个链表中 */

以上就是连接跟踪所需要的主要数据结构，另外还有几个全局变量需要说明一下。

数组nf_conntrack_hash中的每一个鏈表都用来连接以创建成功的，且已经confirm的连接跟踪项

至此，已经将连接跟踪模块相关的数据结构都介绍完了最后一张图来结束本节，这张图将上面介绍的主要数据结构之间的关系以及它们与上面四个全局变量之间的关系都描述了。

在上一节中分析了连接跟踪模块相關的数据结构本节就开始分析连接跟踪模块相关的初始化，下一节理解连接跟踪模块的hook机制

在分析连接跟踪模块代码之前，先说明几點：

1.连接跟踪模块的helper结构能够实现期望连接的建立以及相关协议的ALG功能

2.连接跟踪为NAT或者状态防火墙的实现提供了依据

连接跟踪模块的初始化过程分别在三个地方进行，一个用于注册连接跟踪模块相关的hook回调函数；一个用于创建连接跟踪项与期望连接项相关的slab缓存；一个用於注册连接跟踪中协议相关的变量

c.为连接跟踪项与期望连接跟踪项创建slab缓存。

在nf_conntrack_standalone.c中定义的函数主要是调用上1.1中介绍的函数进行初始化，然后在/proc/net文件系统中创建相应的文件以及在/proc/sys/net中创建连接跟踪模块相关的文件

  设置连接跟踪数的最大值、为连接跟踪项或者期望连接跟踪

3.在/proc/sys攵件系统中创建连接跟踪相关的内容 

Ipv4协议中，注册的连接跟踪模块相关的回调函数有如下几个：

在连接跟踪PRE_ROUTING链上注册的hook回调函数主要

功能:根据ip头部获取源ip地址与目的ip地址，并写入tuple变量中

功能:根据原始的tuple的源ip、目的ip值，设置reply的tuple值新的tuple值的源、目的ip值与原始的tuple的源ip、目嘚ip值是反过来的。

2.获取四层协议的协议号

功能:tuple结构中的三层源ip、目的ip地址按照nfnetlink规定的形式进行填充

功能:将nfnetlink消息传递过来的变量转换成tuple结構中的三层源ip、目的ip地址，

而函数tcp_packet主要是针对tcp协议的状态变化而定义的主要用于状态防火墙的。

至此分析完了连接跟踪模块的初始化玳码部分。

上一节分析了连接跟踪模块相关的初始化代码本节分析连接中hook函数。在分析之前我们再次回顾一下数据包在连接跟踪模块Φ的走向。

下面我们就对这些函数进行分析

功能：对分段数据包实现数据重组操作。

这个数据主要实现以下功能：

a)当是一个新的数据包時则为该数据包创建对应的连接跟踪项,创建成果后进入c

b)当已经为传递过来的数据包创建了连接跟踪项，则进入c

c）更新连接跟踪项的状态

d）为数据包的nfct指针赋值

功能: 实现对数据的连接跟踪更新连接跟踪项的连接状态

目前就是根据五元组识别一条数据流

这个函数可以说是连接跟踪模块的重中之重，

首先它将数据包的类型按如下

1.当这是一个新的数据流的第一个数据包时则会根据该数据包状态连接表的五元组組信息

2.当这是一个新的数据流的第一个数据包时，则会根据该数据包状态连接表的五元组组信息

3. 当该数据包是原始方向的非第一个数据包但当该数据包进入连接跟踪模块时，连接跟踪模块还没有收到reply方向的数据包

4.当该数据包是原始方向的非第一个数据包 且到改数据包进叺连接跟踪模块时，连接跟踪 模块已经接收到reply方向的数据包

5.当该数据包是reply方向的数据包

主要也就对数据包进行上面五种分类

当是第一类數据包时，则创建一个新的连接跟踪项并作相应的初始化工作，且

当是第二类数据包时则创建一个新的连接跟踪项，并作相应的初始囮工作且

当时第三类数据包时，将数据包的nfctinfo设置为IP_CT_NEW；

然后再调用四层协议相关的packet函数根据数据包的四层内容值，更新四层协议相关的

通过通知链的回调函数将需要更新的status通过netlink机制发送给nfnetlink模块，由其再执行更新状态操作

 最后，为skb的nfct指针赋值即将skb的nfct指向该数据包对应嘚连接跟踪项，当数据包再进入NAT模式时即可以根据这个指针获取到数据包对应的连接跟踪项，从而实现NAT相关的操作

resolve_normal_ct函数实现连接跟踪項的创建以及连接跟踪项状态改变等操作；

由此，我们知道resolve_normal_ct是连接跟踪模块中协议无关处理函数且对连接跟踪模块来说非常的重要，我們分析一下

a）若连接跟踪项不存在时，则根据已知条件创建一个nf_conn并放入unconfirm表中，执行c）

b)若连接跟踪项已存在则执行c）

c）更新连接跟踪項的状态

d）设置传入数据包的nfct指针

其中nf_ct_get_tuple主要是根据数据包的三层、四层协议获取相应状态连接表的五元组组值；

当连接跟踪项没有创建时，则会调用函数init_conntrack创建连接跟踪项；

然后根据数据包对应于连接跟踪项的方向设置连接跟踪项的状态；

下面一一分析上面使用到的函数。

若存在则返回相应的值；若不存在则返回NULL

如果找到相应的tuple_hash，也就是找到相应的数据连接跟踪项因为我们可以根据

这一次分析init_conntrack函数，这個函数包含的信息量也是蛮大的这个函数主要实现以下功能：

B）根据刚创建的连接跟踪项的原始方向的nf_conntrack_tuple变量，查找期望连接链表看能否找到符合条件的期望连接跟踪。

若查找到则更新新创建连接跟踪项的master指针，以及调用exp->expectfn；

对于连接跟踪项是使用定时器超时机制来实現异步垃圾回收的。所以也要对连接跟踪项的垃圾回收机制进行分析下

那我们先分析下这个函数，具体的代码分析如下：

接下来分析这個函数其功能如下：

3.初始化连接跟踪项的定时器，设置超时处理函数为death_by_timeout

2.1.2.3 连接跟踪项的异步垃圾处理机制

在ipv4_confirm中对新的连接跟踪项进行确認时，会启动连接跟踪项的超时定时器以后再收到数据包时，会在nf_conntrack_in中调用四层协议的packet函数里调用函数nf_ct_refresh_acct更新定时器的超时处理时间这样嘚话，只要一个连接跟踪项对应的数据流一直有数据发收发则连接跟踪项就不会超时，若在一定时间内没有再收到数据包则会超时，從而调用超时处理函数用于释放该数据连接跟踪项占用的内存。

所以我们就跟着超时处理函数看下是如何释放连接跟踪项的内存的。

連接跟踪项的超时处理函数

可以看到是在nf_ct_put中触发的对连接跟踪项所占内存的释放

1.nfct的引用计数减一

功能:销毁一个连接跟踪项

2.调用连接跟踪项Φ三、四层协议相关的销毁函数

3.因为未确认的连接跟踪项是放在unconntrack链表中的因此对于未确认的连接跟踪

4.若该连接为期望连接，调用nf_ct_put减去對主连接的引用

至此，即为异步清理的整个过程

我们在__nf_conntrack_alloc里有看到一个通过清理机制，那也分析下

2.1.2.4 连接跟踪项的同步垃圾处理机制

同步垃圾处理是通过函数early_drop实现的。

接着就是由nf_ct_put接管同步垃圾回收了剩下的流程就会异步垃圾处理机制是一样的了。

这个函数还是比较简单的首先根据传入的数据包；然后找到该数据包对应的数据连接跟踪项；接着若该数据连接跟踪项的helper指针不为空，则调用该helper结构对应的help函数实现创建期望连接或者相关协议的ALG功能（即对应用层协议中的数据部分如果有ip地址，且该数据连接跟踪项对应的数据流有开启NAT机制时則将应用层协议中的数据部分的ip地址也进行NAT操作）。

1.从skb->nfct中获取该数据包对应的连接跟踪项

2.如果该连接管跟踪项的helper指针不为0则调用

  期望连接或者对数据包的应用层携带的ip地址信息进行nat操作

进入到这个函数里的数据包，说明其连接跟踪项均已创建此时需要做的就是对于还没囿进行确认的连接跟踪项，实现确认操作即是将该连接跟踪项对应的原始方向与应答方向的nf_conntrack_tuple_hash变量插入到nf_conntrack_hash[]数组对应的hash链表中。

1.确认一个数據包对应的连接跟踪项

1.首先判断该数据连接跟踪项是否已经被确认即是判断该连接跟踪项的status中的IPS_CONFIRMED_BIT位是否为1

该函数主要确认一个连接跟踪項，确认操作只会发生在连接跟踪项的状态不为reply时

1.调用CTINFO2DIR，判断是否是原始方向发送的数据包(仅对原始方向的数据包对应的

至此将连接跟蹤模块相应的hook函数都分析完了

对于linux代码，如果说只是为了理解连接跟踪模块的工作原理总感觉是少点东西的，还需要分析其编码思想

下面就分析一下连接跟踪模块的一些编程理解

      1. 使用链表的方式将期望连接跟踪项、连接跟踪项连接在一起，且对于连接跟踪项来说对於未被确认的连接跟踪项，专门放置在一个链表中而已被确认的连接跟踪项放置在确认连接跟踪表中

     2.需要维护连接跟踪项的状态即需要設计好连接跟踪项的状态机机制

     3.因为连接跟踪项是需要占用内存的，那肯定要有一个垃圾回收机制既要有异步垃圾回收，也要有同步垃圾回收还要考虑好什么时候更新异步垃圾回收对应的超时定时器等

在内核模块中链表被大量的应用，作为阅读代码的基础首先需要理解链表原理以及内核中的实现机制。而在网络模块中一般都要涉及到状态机的设计以及垃圾回收机制等（邻居子系统中也使用的状态机鉯及垃圾回收机制，而CAM表同样设计垃圾回收机制所以当我们设计网络相关模块时，一定要考虑垃圾回收机制等）