TCP/IP网络栈实现

参考 翻译:理解TCP/IP网络栈&编写网络应用一文内容。

1. TCP/IP的特性

  1. 面向连接
    这里的连接用什么结构管理?
  2. 双向字节流
    字节流是什么意思?
  3. 顺序投递
    能够完全遵循时间顺序投递?
  4. ACK实现可靠性
    怎么可靠?
  5. 流量控制、阻塞控制

2. 数据传输流程

网络栈很多层
image

内核层使用socket(因为抽象成文件,会走VFS路径)来管理从用户区拷贝过来的接收与发送的数据缓冲区,socket会关联一个TCP控制块,其包含TCP连接的所有状态数据。(基本回答问题1)

TCP中允许情况下会创建TCP segment,包含两个部分:TCP头+数据,注意TCP校验和不会中内核中算出,会offload到NIC中处理
image

创建的TCP分段进入IP层中增加IP头,然后执行IP路由(之后下一层是链路层增加链路头,至此形成完整报文)在执行IP路由时回选择一个NIC传输接口,这时会调用NIC驱动程序。如果此时有抓包程序则会在此层进行数据拷贝处理。驱动程序与内核通过请求NIC定义的通讯协议进行传输。

NIC会从系统内存中拷贝数据包,向数据包中增加帧间隙(Inter-Frame Gap,IFG),同步码(preamble)和crc校验和。帧间隙和同步码用于区分数据包的开始(NIC目前是在哪一层?)。NIC会在主机的CPU上产生中断。驱动程序在启动时会注册一个处理中断的函数。操作系统调用中断处理程序,之后中断处理程序会把已发送的数据包返回给操作系统。

除了应用程序直接调用write之外,内核也可以直接调用TCP传输数据,比如接收到ACK并且得知接收方的接收窗口增大之后,内核会创建socket缓冲区剩余数据的TCP片段并且把数据发送给接收者。

3.数据接收流程

NIC接收到数据包后计算CRC,然后拷贝到驱动提前向内核申请的缓冲区中,之后NIC发出中断。驱动程序会判断它是否能处理新的数据包。
image

驱动向上层发送数据包时,Linux的sk_buff,或者BSD系列内核的mbuf,或者windows的NET_BUFFER_LIST。驱动会把数据包包装成指定的数据结构,并发送到上一层。

之后数据链路层,IP层同样检查数据包是否有效,最后到TCP层查找到对应的TCB,socket接收缓冲区的大小就是TCP接收窗口。TCP吞吐量会随着接收窗口变大而增加。

4. 流量控制

image

步骤3即使用定时器超时机制

5. 中断处理

中断比较复杂,例如NIC接收数据产生中断,驱动在释放已经传输的数据包之后调用napi_schedule()函数去处理接收到的数据包,这个函数会请求软中断。
image

在中断上下文被执行之后,软中断的上下文会被执行。中断上下文和软中断上下文会通过相同的线程执行,但是它们会使用不同的栈。并且中断上下文会屏蔽硬件中断;而软中断上下文不会屏蔽硬件中断。

处理接收到的数据包的软中断处理程序是net_rx_action()函数。这个函数会调用驱动程序的poll()函数。而poll()函数会调用netif_receive_skb()函数,并把接收到的数据包一个接一个的发送到上层。在软中断处理结束后,应用程序会从停止的位置重新开始执行完成系统调用。所以才有多队列NIC以解决软中断并发处理瓶颈问题。

程序员应该掌握的技术常识问题[持续更新]

1. SAN与NAS的不同,有哪些存储开源社区

san是存储区域网络,使用FC将存储设备连接起来形成的一个网络架构,以基于块的方式存储数据。

nas是网络附属存储,是一种网络存储服务器,以基于文件的方式存储数据。

存储方面的社区有ceph, freenas, openstack, suse, redhat,基本上一个开源产品对应一个开源社区。

2. LINUX内核开发需要注意的问题

内核开发需要注意:使用GNU C而非标准C语法(前者允许零长度数组,允许特殊属性声明__attribute__((aligned(4)));),慎用内核栈,没有用户态c标准库,注意同步和并发中断,不要轻易使用浮点数。

3. 内核中使用链表结构与用户态链表有什么不同

内核链表结构不含数据域,使用时作为成员嵌入到对应结构中;用户态链表实现通常直接使用结构指针,STL实现也是将结构包含在链表节点结构中。

4. 内核中红黑树的使用,特别是文件系统中的使用;基树又是怎么使用的

内核在进程地址空间的线性区管理(vm_area_struct)中使用了红黑树,新版的进程调度也使用了红黑树。

在linux 2.4时,可执行状态的进程被挂在一个链表中。每次调度,调度程序需要扫描整个链表,以找出最优的那个进程来运行。复杂度为O(n);在linux 2.6早期,可执行状态的进程被挂在N(N=140)个链表中,每一个链表代表一个优先级,系统中支持多少个优先级就有多少个链表。每次调度,调度程序只需要从第一个不为空的链表中取出位于链表头的进程即可。这样就大大提高了调度程序的效率,复杂度为O(1);在linux 2.6近期的版本中,可执行状态的进程按照优先级顺序被挂在一个红黑树(可以想象成平衡二叉树)中。每次调度,调度程序需要从树中找出优先级最高的进程。复杂度为O(logN)。

在18内核中文件系统方面仅有ocfs2,jffs2及ext3在使用红黑树,ext3在创建reservation window时使用了红黑树结构进行管理,主要是考虑文件增长会导致无法线性分配,所以先预留了一些空间(8块),具体原因可以参看此文此文,这颗红黑树的建立是为方便搜索其他预留窗口。

在32内核中连ext2也开始使用分配预留机制所以也使用红黑树,ext3及ext4在启用目录索引(磁盘上是B+树组织)时会在file的private_data中存放了dir_private_info结构,用来将一个打开目录文件的全部目录项组织成红黑树,其 root 字段指向 rbtree 的根 , rbtree 的节点由各 struct fname 结构(包含磁盘目录项的信息)的 rb_hash 字段形成,这颗红黑树的建立是为方便大目录的readdir操作多次进行。

nfs使用红黑树管理Access mode cache即acl元数据信息缓存,btrfs大量使用红黑树。

基树仅在Page cache中使用,将文件逻辑层的数据以页的形式映射到页高速缓存中,这些文件可能来自文件系统(文件数据或目录)也可能是块设备抽象。

5. B树和HASH方法的时间复杂度以及在系统中的表现,文件上散列又有何问题

B树访问是O(lgn)(树高度)复杂度,hash是O(1)复杂度。但是B树可扩展性更好,对于B+树来说在磁盘上对范围访问有很好的支持,相对hash表方法不易扩展且磁盘上范围访问性能不佳。顺序写文件并使用hash在顺序文件上做索引的方法,仍然受hash表大小限制不易扩展,且当索引表无法全部加载到内存时,hash随机访问特性无法在硬盘上发挥。

6.LINUX下线程与进程描述与区别

Linux下线程就是轻量级的进程,其进程描述符task_struct中tgid字段即为线程所属进程的pid,real_parent字段会指向所属进程的real_parent字段,thread_group链表字段会串起所有的线程。同时线程的地址空间mm、打开文件files、文件系统信息fs及信号处理sighand都会共用进程的。线程又分为用户态线程和内核态线程,用户态的线程栈是使用mmap在进程的堆空间分配的。内核线程使用clone系统调用创建时置CLONE_VM标志导致copy_mm()中将active_mm与mm赋值与父进程(所有内核线程的父进程都是kthreadd内核线程,而该内核线程又由swap内核线程创建,故而mm都是NULL)相同,避免复制页表。因为内核线程不会使用用户态地址,故而在运行时mm为NULL,active_mm指向上一个运行进程的active_mm。

7. 大致描述PAXOS过程及偶数台机器的处理

标准Paxos过程涉及三种角色proposer、accpetor以及learner,整个过程分为两大阶段:第一个阶段是选值,第二个阶段是同步,第一阶段中proposer提出编号为n的提案;accepetor在确认自己没有见过高于编号n的提案后回复对应proposer,否则将返回对应提案的值v,当proposer收到大多数的accepetor的确认信息后进入第二阶段;第二阶段中proposer如果收到大多数accepetor的提案值则只能选择该值,否则可以自由选值,并将该值同步到大多数accepetor,此时learner也将从大多数accepetor中学习到该值。paxos利用大多数原则保证一致性。

当因为偶数台出现无法选举成功时,可以先移除一台完成选举并检查网络问题。

8. WORDPRESS大致流程,其中URL固定链接如何实现的

分为admin与user两种大致逻辑。user起点是index.php并进入wp-blog-loader.php装载模型与视图而admin起点为wp-admin.php,之后进入wp-load.php加载wp-config.php初始化wp及wp-settings.php包括所有启用的plugins和主题的functions.php完成模型,之后uer使用template-loader.php完成视图,admin使用固定文件完成对应视图。

首先需要web服务器开启rewrite功能,将url统一定位到index.php,其后由WP接管负责处理url。整个过程如下:

a. wp初始化过程;b.在wp-setting.php中建立全局变量,特别是$wp和$wp_rewrite;c. 在classes.php中调用$wp的parse_request方法解析URL,该方法会处理$_SERVER['REUEST_URI']或$_SERVER['PATH_INFO']从而建立变量$request,然后使用$wp_rewrite的wp_rewrite_rules方法获取rewrite规则并逐条对$request进行匹配(preg_match),如果找到一个匹配, 则建立相关的变量$perma_query_vars并最后保存在 $wp->query_vars里;其中rewrite规则会保存在数据库的option表中。主要参考这篇文章

9. VFS大致构成介绍,其中 DENTRY结构如何形成, INODE结构如何形成

VFS为同一个目录结构下可能挂载的不同文件系统提供了统一接口,VFS提供了通用文件模型的多种对象内存结构包括file_system_type, super_block,inode,file,dentry以及进程相关结构包括files_struct及fs_struct,还有通用的页高速缓存page cache。

其中dentry结构在lookup操作发现dentry缓存中没有对应目录项时会从磁盘上读取目录内容找到对应目录项的内容(该操作为底层操作系统的lookup操作)并建立对应的dentry内存结构。

inode结构有三种形成方式,第一种是超级块载入时会将对应的inode读入并生成内存结构;第二种是mknod或create系统调用创建新的inode结构并标记为脏同步磁盘;第三种是lookup操作时目录项不在缓存中,完成dentry创建后还可能需要完成对应inode内存结构的创建并进行绑定。

10. JBD大致介绍及产生原因

JBD是一个日志子系统为ext系列文件系统提供一个独立的日志化系统,利用数据库中的日志技术实现WAL协议以加速e2fsck对系统一致性检查及系统一致性恢复的速度。JBD提供原子操作和事务两种抽象接口,前者保证多个低级操作构成的一个高级操作可以原子性的更新到文件系统,后者保证多个原子操作会原子性的提交到日志。JBD提供三种模式:journal模式会将数据及元数据都记入日志;ordered模式是默认模式会在元数据提交到日志前保证将对应数据写到磁盘对应位置;writeback模式只记录元数据到日志无视数据。

11. 什么是高端内存,在64G内存下又是什么情况

在32位系统中,线性地址空间是4G,其中内核规定3~4G的范围是内核空间,它映射到了物理地址的0~1G上.。然而 实际上没有映射1G,只映射了896M。大于896M的物理地址即高端内存,是没有写死的页表来对应的,内核必须要建立映射才能访问它们。该机制可以满足1G的内核线性空间寻址大于1G的物理空间的要求,比如应付PAE下对64G物理空间的寻址。

如果机器内存不足896M,就不存在高端内存。如果是64位机器,因为可用地址空间很大,也不存在高端内存,其中属于内核的线性空间默认为2G,具体规划可见此文

12. VM何时会产生,新建进程时已经刷新过页表之前为何还要分配VM

父进程通过fork创建子进程时使用copy_mm时会复制父进程的所有线性区(dup_mmap会遍历链表并进行复制),之后根据线性区情况填充对应子进程的页表。当可执行映象映射到进程的虚拟地址空间时,通过exec调用do_mmap也可能产生新的线性区。

进程建立vm_area_struct结构后,只是说明进程可以访问这个虚存空间,但有可能还没有分配相应的物理页面并建立好页面映射。在这种情况下,若是进程执行中有指令需要访问该虚存空间中的内存,便会产生一次缺页异常。这时候,就需要通过vm_area_struct结构里面的vm_ops->nopage所指向的函数来将产生缺页异常的地址对应的文件数据读取出来。

首先子进程需要继承父进程的地址空间,其次对于以后会调用exec的子进程也需要所有线性地址并标记为只读以确保能触发COW机制。

13. 如何实现线程安全

实现线程安全可以采用不共享状态变量,使用原子操作,或使用同步手段。

14.大致描述下LIRS算法的过程

所有缓存被分为冷区及热区,热区占用大部分缓存,另外准备一个空间用于存储最近被访问的块。当空间中一个块被命中时就会调至顶部,并通过操作移除空间底部的所有冷块直至底部是热块(这保证底部一定是热块且当该热块被移除后上面的冷块是没机会变成热块的);当空间中冷块被访问到就会转换为热块,同时空间底部的热块就会变为冷块并移至冷区缓存顶部,注意此时该冷块不一定出现在冷区中;当冷区中的冷块命中而空间中没有命中时,只要将其移到到冷区顶部;当未命中时,就必须替换冷区缓存底部的块。注意在空间中的块不一定在缓存中。

15. 进程同步的方法,各有什么优缺点

很容易与进程间通信(IPC)混淆,进程间通信有以下多种:管道,socket,消息队列,信号,信号量,共享内存

而同步方法有:文件锁,信号量,管道+select等,socket+select等

IPC的各种方法中消息队列不需要同步控制,但需要两次拷贝且需要处理上次的残余消息。共享内存需要同步控制,通常和信号量共同使用。管道和socket使用了内核锁进行同步控制。

文件锁效率不如信号量,但文件锁使用简单且会在进程退出时自动释放。

16. STATIC变量与全局变量区别,DLL共享了哪些信息

声明了static的变量或函数就失去了全局可见性仅能在声明文件内被访问;全局变量和static变量都在所谓的“静态存储区”,会在开始运行时即完成初始化,默认为0;所以主要区别还是访问域的。

17.一个星期秒数的宏定义写法

#define WEEK_SEC (7*24*3600UL),注意整形常量默认声明为int类型尽管32位下够用但声明为L兼容性更好,而秒数不可能为负数且可能由星期宏定义扩展为月或年故声明为UL更好

18. MYSQL有哪些存储引擎,MYISAM与INNODB有什么不同

MySQL有MyISAM,InnoDB,HEAP(内存),BDB,CSV等

19. GFS的元数据控制与数据控制流

20. 什么是僵死进程,什么是孤儿进程,进程退出会自动释放哪些资源

由于允许父进程调用wait系统调用检查子进程退出情况,因此子进程运行结束后需要继续等待,此时通知父进程并进入EXIT_ZOMBIE状态;而如果父进程先于子进程退出,则会将孤儿子进程交由init进程管理,这样init进程可以使用wait系统调用检查子进程终止然后删除EXIT_ZOMBIE状态进程;所以僵死进程一定是父进程没有退出且没有调用wait进行处理的子进程,而孤儿进程是父进程先于子进程退出的进程且一定会被init妥善管理,所以前者多了会消耗资源而后者不会。

进程退出会向所有线程发出退出信号,自动关闭文件描述符,释放socket连接,存储映射区也会自动解除(关闭文件描述符并不能解除存储映射),释放文件上的锁,信号量仅在设置undo标志时才会自动回收。

本站总访问量