内核中国 -- IT技术博客大学习 -- 共学习共进步！

• 回忆Windows开发中的古老概念

以前在Windows上面做过一些工作，那个时候还没有维基百科全书，很多计算机相关的概念由于是刚刚发展出来，身处其外的人往往不知道正确的含义。微软的技术那时候是最受开发人员关注的，当时也只有在Windows上做一些软件才可以赚钱，回想一下，微软没有推出App Store绝对是个极大的失策。微软的各种技术图书和开发工具涉及到很多的原创缩写词汇，让人不知所以，现在有个WIKI的归类总结我们才能真正的理解这些名词。下面列举一些例子： VBX：这个是我们在早期的VB乃至Delphi上面设计GUI的时候使用的控制。基于控件开发是当时的热潮，有公司专门出售这些控件，也有盗版光盘包含了很多的控件集合。试用各种控件也是学校生活的一部分。记得毕业实习的时候，用VB开发一个企业管理软件，有些高级表格需求windows自带控件无法实现，公司也是满世界去找。

• 空指针的解引用

空指针解引用是否导致异常应该是硬件设备和OS组合决定的。以前在VXwork下工作，空指针也可以解引用，可以访问内存0地址，还可以修改内容。这种情况下，为了便于程序员debug，印象中我们大概是采用了对于0地址内容监控，如果内容有改动则报告或者crash。

• 有关面试

最近集中面试人，也有了一些心得。首先是明确面试的目的，面试是希望招聘到合格的工程师，而不是难为别人或者炫耀技能，因此犄角旮旯的知识，高难度的数据结构就不必要拿出来炫耀了。其次确定问什么，大家都不是搞基本计算机理论研究的，而公司中特有的东西也没有办法拿出来问。其实可以深入问的有两个方面： 1.领域基本概念虽然是最基本的概念，但事实证明，少有应聘者可以给出深入和正确的回答。所谓深入，达到百度百科的标准就OK了。对于领域基本概念有清晰了解可以体现出面试者的敬业，也可以反映出面试者对于技术的渴望和好奇心。这类员工往往可以有潜力培养成为骨干。 2.面试者的工作领域如果一个面试者在一个项目工作了2，3年，则期望他对于相关知识有深入的了解是合理的，否则不要混了。

• 关于tcp-proxy的几个小问题

Tcp-proxy是什么东西就不说了，搜索本站就能找到答案，说说最近碰到的几个问题。 1)keep-alive 如果server或client开启keep-alive，需要tcp-proxy也能感知。但是keep-alive本身是不携带有效的数据(通常是最后收到并且已经确认的一个字节)，所以直接转发会有问题(tcp-proxy转发会重写tcp header，而且tcp-proxy之上的应用不能处理这个包)。所以说keep-alive是tcp层的行为，而不是应用层的行为，只要tcp-proxy的两端处理就可以了。由于tcp-proxy接管的tcp连接，所以最好是两边都能够发出keep-alive packet，这样才能完成协议所规定的功能。

• 有关TCP Flag

面试一小伙，老生长叹的问题，介绍一下TCP flags，小伙说多了，SYN, FIN在ACK的时候需要占一个Byte的数据，而其他几个不需要。于是反问之，为什么不要？小伙支吾一阵说，可能是其他几个不重要吧。这个问题其实很简单，对于需要ACK确认收到的标记，需要占用一个Sequence值。例如，你发送一个仅有FIN没有数据的报文，TCP一定要确认收到一把，而这种确认只能通过sequence加加。这个同标记的重要与否无关。其他的Flag是单向的不需要确认，尤其对于ACK，协议设计上就不允许确认，因为如果ACK需要确认，则协议必然陷入死循环不可自拔。对于SYN, FIN由于需要确认，因此逻辑上是Data的一部分。其实TCP的多数option也是需要确认的，逻辑上也是data的一部分。但Option设计本身就有option级别的确认机制，不需要利用sequence在搞一把。

• TCP SYN-Cookie背后的人和事 - 续

以前写过一篇“TCP SYN-Cookie背后的人和事”，今天讨论一下发现我的理解也没有到位。看来工程中没有看过code或者调试过，对于一个事物就无法透彻的理解。本来的理解是SynCookie不会保存Session信息，取而代之的是要保存一个32bits的Cookie。一个依据就是：如果本机没有保存任何秘密，如何验证正常的Session呢？如果不用秘密攻击者就可以制造出对应的第三个ACK，可以等待一段时间发送第三个ACK造成实际的攻击。现在有了更多的理解，看起来SynCookie不用本地缓存任何内容，包括不会生成的32bits的cookie。

• 我对总线的理解和总结

首先需要明确什么是总线，其用途是什么？根据wiki的解释，总线是用于连接计算机各部件的子系统，用于各部件间的数据传输。为什么叫做bus呢？大家可以想英文中bus的意思是公共汽车。在这里也有近似的意思，是一个公共传输线路，大家的信号都可以在上面传输

• TCP/IP源码学习——inet_select_addr函数分析

当一个网卡配置了多个IP时，那么kernel选择哪个IP作为源IP来发送数据包呢？

• 有关读写锁

为什么需要用读写锁。读写锁用于single thread写，多个thread读的情况。在没有发明读写锁之前，我们当然可以对所有的thread使用Mutex来控制资源访问。但是在这个场景中，两个thread读取数据没有必要进行互斥，读写锁应运而生，是的这种场景下所有拿到读锁的thread可以并行执行。读写锁的实现。实现：在多核系统中读写锁的实现一般是基于SpinLock，Linux就是如此。抢占策略：写优先还是读优先。这个都可以，我觉得写优先比较好一点，因为一般此类应用读thread占多数，如果读优先则写锁线程可能被饿死。读锁的upgrade和downgrade。有的时候在读到一半的时候，可能突然又要想写点什么东西，此时不能直接拿写锁，一定会死锁。只能关掉读锁来重新竞争写锁。这时候可以引入读锁的upgrade来使其直接升级为写锁。

• 编写安全代码：小心使用浮点数

浮点数的存储格式与整数完全不同。大部分的实现采用的是IEEE 754标准，float类型，是1个sign bit，8 exponent bits，23 mantissa bits。而double类型，是1个sign bit，11 exponent bits，52 mantissa bits。至于浮点如何去表示小数，请自行搜索google。由于float使用的小数表示方法，导致浮点数值是有精度限制的。有限的精度就引发了浮点数值使用时的两个陷阱。

• 编写安全代码：再论整数类型转换

在代码中还是要尽量避免有符号数和无符号数的比较。如果无法避免，为了清楚的表明自己的目的，最好使用强制类型转换。

• 锁是怎么实现的？

这是一个同事问我的问题。我并非专家，只是有基本的原理理解。首先排除上层的各种花里胡哨的锁的机制，基本的锁应该有如下的几种实现方式。 1.OS提供的内核对象方式提供的异步锁实现这种方式下，锁的实现是内核对象，对外提供API，之所以说是异步是因为试图加锁的进程如果无法获取这个锁，内核的操作方式是将进程加入这个锁的等待队列之中。当该锁被释放之后，OS对于等待队列中的进程进行唤醒。 2.对于单CPU的IntMask方式的同步的锁实现之所以说是同步是因为这种方式关中断，停止CPU的任务调度，这样我们可以保证互斥操作。 3.对于多CPU的处理器，多个CPU之间的Spin Lock 每个CPU只能关自己的中断，因此这个时候关中断无法保证全局互斥，需要找到一个全局的统一互斥点。我们依赖的是总线，各个CPU通过锁总线来进行竞争(据说Intel多核CPU提供了避免锁总线的机器指令)。

• 有关Cache 2 - 基本结构

周末花了一个下午看了一下《计算机体系结构量化方法》的附录B，是有关Cache原理的介绍。这本书写的还真是好啊，看似一块大砖头，本以为废话很多，其实多数描述很简练，微言大义。例如前些日子写了一个带宽和时延的关系，这本书一句话就写明白了：“时延决定数据第一个接收Bit的时间，带宽决定接收剩余数据的时间”，真实很牛X啊。画了一张小图总结Cache的基本结构。 CPU的处理器地址(我理解就是经过转换后的最终的硬件地址了)被划分为三个部分，Tag，Index，Offset。寻址的时候，首先用Index寻址Cache Set(这个是Cache相关性的产物)。Tag用作Key在Cache Line Set之中匹配Cache Line。Offset用于得到最终对象地址。其他很多概念和Cache Policy就是基于这个简单的数据结构图演化出来的。

• C函数串接的几种手法

经常会有这样的需求，一组处理业务逻辑的并列函数要串行调用，可以有下面的方法将其串接起来。例如我们有函数fa(), fb(), fc() 1.最简单就是顺序调用了 fa(); fb(); fc(); 2.上述调用在需要判断返回值的时候写起来有些冗余，于是可以这样写：假设返回非零表示错误 if (!fa()&&!fb()&&!fc()) …… 3.使用逻辑如下的调用方式 fa() return fb() return fc() 前述有写过一篇Nginx的filter，就是这么组织的。

• 时延和带宽的关系

末学很惭愧，网络做了多年，时延和带宽的概念一直没有搞的很清楚，认为二者是反比关系，即低时延对应高带宽。其实不对，请教了一下同事，总结如下：上述两个系统是带宽相同的系统，上面是高时延，下面是低时延。可以看出，高时延系统中，报文从进入系统到流出系统做的操作更多，耗时更长，但是并不影响带宽。同时可以看出来，高时延系统也不容易，必须有足够的内存queue足够多的输入才能在不影响带宽情况下做更多的处理。

• 开源世界中的算法与数据结构 3 -- Linux IPv6 FIB表实现

在Linux 2.4 IPv4 FIB的数据结构基础上实现IPv6的FIB是否可行呢？如果读了我前面这篇文字你应该会有一个判断。IPv4的FIB实现可以说有些拙劣，如果照搬一个IPv6版本，最差情况下需要进行128次hash key计算这还不包括链表的查找过程。看了一下Linux 2.6的IPv6 FIB实现，已经有了调整，用了Patrix(Radix)树实现了这个算法，下面是一些背景知识：首先是Trie树，下图是Wiki http://en.wikipedia.org/wiki/Trie 之中的一个例子 Trie树，尤其是二叉Trie树属于：是一直被使用，从未被(教科书)重视的东东。其特点是键值的内容成为树的检索路径，例如上图的to，tea等几条键值标明的路径。如果要对trie分类的话，我想只能按照出度来分类，上图假定键值的每一字节取值a-z，则这个trie是26叉trie树，最小

• 开源世界中的算法与数据结构 3 -- Linux Kernel List 和GList

List是工程师的基本功，这里并不描述list增删这些细节的内容，仅仅根据我的理解写一下工程中List库的设计和实践考量。看过几个不同的list库的实现，基本上涉及到如下的设计考量： 1.List数据结构上的差异有没有头结点，是否循环，是否双向。这样就有多种组合，不罗嗦。 2.list的读写的保护。 3.List直接指针遍历还是仿照STL的Iterator方式遍历。 4.List同实际用户数据是采取一体式还是干湿分离式。 5.系统对于数据结构和算法的影响 1.从数据结构上将，Linux Kernel之中的List是双向无头节点链表。空链表如下：非空链表如下：我觉得维护头结点的理由之一就是可以存放list size，而无需用户在应用部分进行维护。如果没有list size，用户需要在List删减的结束的时候维护list size，如果不愿意如此麻烦，只能悲催的在需要读取

• 开源世界中的算法与数据结构 2 -- Linux Skbuff实现

兼回忆贴，大概在03年开始接触Linux的协议栈代码，那个时候还找不到什么参考书，有些东西自己搞明白了但是也从来没想过在那个论坛发个帖子什么的，也没有现在的记录总结的习惯. 后来有一本08年版的《TCP/IP Architecture, Design and Implementation in Linux》其中解析了Linux2.4 协议栈的多数代码，其中第五章专门涉及skbuff的代码实现讲解，非常详细，这个小短文不翻译整个章节，各种网文很多，只是想根据关键部分说一下我理解的设计背后的原因。 skbuff的形态1 上面是最基本的一个sk_buff了，一个TCP报文的skbuff示意图，这里隐含着一些内容：报文分析的标准模式 skbuff采用的大块控制结构对象指向数据区是标准的实现模式，例如BSD这样的OS以及工程实现中都是这样的。参数的集中与其提供多个对象或者多个参数保存

• 开源世界中的算法与数据结构 1 -- Linux FIB实现

在Linux2.4的时候，对于Linux的FIB表有些研究。凭着残存的记忆和code，恢复一下FIB的数据结构。首先扫盲一下几个路由协议架构相关的概念：上图为路由协议的基本架构，相关内容在Cisco出版社出版的某一本图书上有概念描述，大概是《Routing TCP》。 1．每个路由协议根据自己收集到的路由信息产生内部的路由表。所有的路由协议的路由信息汇聚到统一的RIB之中。 2． RIB的管理模块根据RIB之中的路由条目按照优先级优选出实际用于转发的路由下发到FIB之中。 3．最终在Packet到来的时候，系统查找FIB表做路由查找。对于FIB的主要需求有两个： 1. 组织和存储选出的路由表项。 2. 按照LPM(最长掩码匹配)算法提供路由检索接口。下图是Linux24之中的FIB表中几个主要的数据对象的数据结构关系。具体字段不做解释，最终的目的就是找到dn_fib_n

• 做大的艺术 - 大型网站的架构设计

看了一些关于网站架构方面的文章，基本上是大同小异。也就是说，基本的原则都是一样的，而且软件也都是开源软件。但难点在于整合和运营。整合需要一些自制的工具或者根据业务定制软件；运营需要考虑数据中心建设，业务流程设计等等，不是一个简单的软件问题。从小到大的演化是一个很有意思的故事，和人的成长类似