Felix021

对ssh用得比较多的同学应该知道通过建立信任关系来免除输入密码的麻烦：

在A机器上执行：

$ ssh-keygen -t rsa (各种回车)
$ ssh-copy-id -i ~/.ssh/id_rsa.pub USER@B_ip

然后在A机器上 ssh USER@B_ip 就可以免密码使用USER用户登录B机器了。

实际上第二步操作是将 A 机器该用户的公钥(id_rsa.pub)追加到B机器的 ~/.ssh/authorized_keys 文件末尾中去。

当A机器访问B时，如果B机器的sshd能够在/home/USER/.ssh/authorized_keys中找到对应的公钥，就认为A机器具有B机器的USER用户访问权限，于是就直接让A机器以USER身份登录。

但是上周在线上某台机器进行操作时却发现这一机制失效了。通过该机制，A=>B可登录，但是B=>A失败，甚至A=>A也失败（B=>B却成功）。虽然问题很奇怪，但说明问题出在A机器上。

首先是 diff 了A、B两台机器的 /etc/ssh ，发现完全相同，所以不是配置的问题。

然后查看 ssh -vv localhost

而在B机器上，we sent a public key packet, wait for reply 之后则是紧跟着"debug1: Server accepts key: pkalg ssh-rsa blen 279"。由此可以看出，是A机器的sshd不认可publickey。

至于为什么不认可，在google上查了许多，毫无头绪，直到使用类似“ssh publickey ignore debug diagnose”这样的关键词，发现这个页面，其中的第二条和第六条给出了解答：

通过执行 /usr/sbin/sshd -d -p 2222 （在2222端口启动一个带debug输出的sshd） ，然后 ssh -vv localhost -p 2222 ，可以看到sshd输出了一行
正好与那第六条相对应，再检查一下 /home/felix021 ，其权限是其他组可写。

最终解决方案：将用户home目录的权限改为0755，登录成功。

这是第一个支持IBM PS/2和1.44MB 3.5寸软盘的DOS版本，可能是在家用PC上比较容易用虚拟机模拟的最古老的微软系操作系统。隐约记得这里头还有个BASICA解释器，比QBASIC还要老很多的那种，类似于文曲星上面的那个版本。

以前（大一之前）很喜欢玩这些东西，收集了不少东西，包括3.31, 6.22, win98/me/xp的DOS启动盘, windows 1.0 ~ 3.2（主要来自曾经的“bear5的软件地摊”），还有很多dos下的工具，tw ucdos 之类，甚至还有个VB DOS版。折腾bat、config.sys这些东西，玩得乐此不疲。如今突然想起，却发现它们静静地躺在硬盘的那个角落已经好多年了。

谨以此纪念那些二逼的时光。

如果到Google去搜索，"How to find out which process is listening upon a port"这是第一篇文章。

事实上大部分文章都是告诉你，要么 lsof -i :80 要么 netstat -antulp | grep :80 就能找到httpd。

可是如果就这样的话，这篇BLOG就变成微博了。

事实上我的目的是希望通过编程找出这个PID，而不是调用某个命令。

第一个尝试是去看lsof的源码。找源码容易，apt-get source lsof 就行。但是源码跟大部分linux软件包一样，看起来相当晦涩。

第二个尝试是Google，但是能找到的都是命令版的。

第三个尝试是stackoverflow，没有直接搜到问题，于是准备自己提问，但是在“Questions that may already have your answer”里头找到了一篇“How to get the pid of a process that is listening on a certain port programmatically?” ( http://stackoverflow.com/questions/10996242 )。

Answer给出的步骤非常清晰：与netstat的实现一样，先读取 /proc/net/tcp 这个文件，第二个字段（local_address）冒号后面的是端口号（十六进制），第四个字段st为0A表示TCP_LISTEN，第10个字段是十进制的inode编号；而通过遍历 /proc/PIDs/fd 下面的链接，找到链接到形如 socket:[端口号] 的fd进行对比，就能知道哪些进程与该端口有一腿。

我在机器上监听的是8888端口，换成hex是22B8，但是在 /proc/net/tcp 中却找不到。幸而那篇文章的第二个Answer给了个提示，于是 strace /usr/sbin/lsof -i :8888 ，发现它还打开了 /proc/net/tcp6 （也就是对应IPv6的那个文件了）。过去一查，果然有，再顺着inode，对照lsof的结果一看，的确符合。

于是再去grep一把 lsof 的源码目录，发现在 00FAQ 文件中的 10.2.2 一节就说明了 lsof 的实现机制：
看来在 Linux 下的实现方式确实只有这一种。顺便提一下，Stackoverflow上面的另一篇 http://stackoverflow.com/questions/4041003/c-what-process-is-listening-on-a-certain-port-in-windows 提到了，在Windows下可以用GetExtendedTcpTable/GetExtendedUdpTable来实现。

最后附上PHP实现的源码（这个代码用C/C++写确实蛋疼）

这是2012年百度实习招聘非技术类的某道笔试题。

给一个5×5的矩阵，每个元素只能是0或者1。

请问，有多少种不同的矩阵，能够满足每一行、每一列都有偶数个1？

==== 分割线 ====

乍看这个题目，觉得是数学题。画了个5*5的矩阵，试图填几个数字进去看看是否可以推出一些结论。果断失败。

然后想了下，这题如果枚举的话，也就是2的25次方，大约3200万这个规模，不是很夸张。于是决定暴力搞一下。

最简单的做法就是这个check_even(i)里头把 i 当成一个25bit的二进制数字，并转换为对应的5*5矩阵，判断其每一行和每一列是否满足要求。（p.s. whusnoopy的做法是直接使用位运算，更简单，不过思路就断了。。）

一个不难想到的优化是，在for之前先把每一行给枚举了，这样就不需要在check_even里面每次进行转换，只需要从 i 中取出对应的bits，就可以直接找到每一行。

更进一步，由于题目要求每一行都是偶数个1，所以可以进行剪枝——在枚举的时候只需要保留有偶数个1的情况就行了，枚举出5行，然后判断每个列。很容易计算，每行5个bit，偶数个1的情况是2^4=16种。于是需要枚举的矩阵数量降至16^5。

再进一步剪枝——题目要求所以列是偶数，那么在已经确定前4行的情况下，第5行是可以直接推出来的，需要枚举的矩阵数量降至16^4。但还需要做的事情是，判断第5行是否有偶数个1。

到了这一步，豁然开朗——因为很容易证明，第5行必然是偶数个1：
  1) 每一列都是偶数个1（ABCDE都是偶数），所以矩阵中必然有偶数个1（F=A+B+C+D+E为偶数）
  2) 前4行都是偶数个1（HIJK都是偶数），所以第5行必然是偶数个1（L=F-H-I-J-K为偶数）
  (p.s. 这个证明是WHUMSTC群里某同学给出的，非常清晰，所以我就不给我自己那个很挫的证明过程了）

于是开头的直觉获胜，问题的答案就是：16^4，也就是(2^4)^4。

==== 分割线 ====

扩展：

1. 如果矩阵的大小是 N×N ，甚至是 M×N 呢？

    根据上述结论，很容易推知，对于M*N的矩阵，结果是2^((M-1) * (N-1))。

2. 如果要求满足每一行、每一列都有奇数个1呢？(whusnoopy提出)

    这个结论就不那么直接了，对M*N有一定的限制。

从哪儿说起呢？我想了想，从 gets 说起可能最好。

初学C语言的时候，如果要输入一行字符串，该怎么办？看书，或者找老师，或者找学长，通常得到的答案是gets。用法很简单，似乎也很好用，但是很不幸，这个函数很危险。因为 gets 对输入不进行任何的限制。如果对应的字符数组只有100个字符，而面对的输入是1万个字符，那么几乎毫无疑问，这个程序是要崩溃的，除非运气特别好，或者……

或者给出的输入是经过精心设计的，例如一段shell code，及其对应的跳转地址。对于常见的计算机体系来说，函数调用时，返回地址是在栈上的，通过精心设计输入，使得溢出数据中的跳转地址好正好覆盖了该返回地址，于是函数在返回时不是如预期般回到调用者处，而是跳转到攻击者给出的shell code处，使得攻击者获得了额外的权限。

这就是典型的溢出攻击。

为了防止这种情况的出现，在C库函数中，许多对字符串操作的函数都有其"n兄弟"版本，例如strncmp，strncat，snprintf……兄弟版本的基本行为不变，但是通常在参数中需要多给出一个整数n，用于限制操作的最大字符数量（本句不够严谨，详情参见各函数的说明）。

这是技术上的解决方案。只是，代码都是人写出来的，总会有对溢出缺乏概念的人，写出令人蛋疼的代码。于是一些公司，例如（听说）腾讯，建立了一套规则，对提交的代码进行扫描，若发现使用了非“n兄弟”版本，就会给对应的码农一定的惩罚措施，从而在管理上降低此类问题出现的可能性。

加强管理当然是好事，但是也给某些有强迫症的码农带来了不便：因为strlen没有n兄弟版本，坑爹啊！事实上，更坑爹的是strcpy，在c语言标准里，它不但没有n兄弟版本，甚至还有一个“冒充”的"n兄弟"版本——也就是 strncpy 。

strncpy 到底做了什么事情呢？它基本上等同于这样几行代码：
比较诡异的两件事情是：

1. 如果src的前n个字符里面没有'\0'，那么它不会在末尾补上这个结束符

2. 如果拷贝的数据不满n个字符，那么它会用 '\0' 在末尾填充

以 strcpy 的行为来理解它，只会感到很蛋疼：第一点很可能会造成此后代码的数组越界访问，而第二点则是对cpu资源的浪费。

事实上，完全是因为历史的原因，造成了这样的误会。在第七版的UNIX文件系统中，每个inode结构体中包含的每个entry（对应文件或下级目录）只有16个字节，其中前两个用于标识inode，剩下的14个用于保存文件名。由于文件名最长只能有14个字符，所以在设计上，末尾不足的字符用'\0'来填充；如果达到14个字符，则不需要结束标志。

众所皆知，c是为unix而生，所以这就是strncpy的原始目的：定长字符串 的拷贝。对应的代码，很自然地，可以这样写：
那么如果确实需要一个strcpy的n兄弟版本该怎么办呢？最简单的办法是用snprintf：
p.s. 其实还有个 strlcpy ，只可惜它是OpenBSD 2.4引入的，并非C标准中的函数，适用范围较窄。

参考资料：
http://www.lysator.liu.se/c/rat/d11.html
http://stackoverflow.com/questions/1453876/why-does-strncpy-not-null-terminate
http://stackoverflow.com/questions/2884874/when-to-use-strncpy-or-memmove
http://blog.liw.fi/posts/strncpy/
http://pubs.opengroup.org/onlinepubs/9699919799/functions/stpncpy.html

为了论文搞了把机器学习的东西，虽然了解得非常肤浅，但是窥探了一下这个领域也还是很有收获。

对于遇到的问题，传统的思路是通过建模，然后使用对应的算法予以解决。但是对于很多问题，建模本身是不实际的，例如语音识别、计算机视觉等等。而机器学习算法的思路则不同，通过对现有的数据进行分析和统计，得到一组参数来逼近真实的模型，从而能够处理未知的数据。

我的论文里主要是使用SVM来解决简单的二分类问题。SVM，Support Vector Machine的简写，也就是“支持向量机”，很早以前有“听说过”，但是之前完全没有概念。这次在yihong妹妹的推荐下，看了faruto大牛写的《SVM入门精品系列讲解》，能大致在原理上明白svm分类的机制。之所以称faruto为大牛，主要是因为这个讲解系列非常地浅显易懂，没有卖弄玄虚，即使是我这样没学好数学的人，也能够非常容易地弄懂。

由我来归纳的话，svm的基本思路应该是，将每个样本x当作一个N维向量（也就是N维空间中的一个点），通过某种方式找到该空间中的一个超平面w * x + b = 0，将样本分成两类。例如二维空间中的点，可以用一条直线分成两类，而三维空间的点，可以用一个平面来分。由于并不是所有问题中，样本在N维空间中都可以被超平面分为两类，因此通过使用引入核函数将样本映射到更高维的空间、并引入松弛变量以忽略噪音数据等方式，达到对数据进行分类的目的。

可能看起来有点抽象？没关系，把那个系列（并不是很长）看完就懂了，其实不难理解。在此基础上，svm方法还有许多扩充，例如对不平衡样本集的处理、One-Class SVM、在线SVM训练等等。

想要使用svm算法的话，非常幸运，台湾大学林智仁(Lin Chih-Jen)副教授主持的 libsvm 项目提供了c/java/python/matlab 的接口，直接拿来就能用了，非常方便。

在学习svm的过程中，也顺便看了一些其他的机器学习算法，这里也大致列一下。

HMM，隐马尔可夫模型。李开复的主要学术成就（之一?），就是使用了HMM开发出世界上第一个大词汇量连续语音识别系统 Sphinx。根据Google研究员吴军的数学之美 系列三 -- 隐含马尔可夫模型在语言处理中的应用，使用HMM来进行语音识别是李开复的师兄提出的。

HMM算法是基于贝叶斯公式的。贝叶斯公式在机器学习中是一个非常基础的理论。关于这个，推荐阅读《数学之美番外篇：平凡而又神奇的贝叶斯方法》

神经网络算法，通过模拟神经元的工作方式来对数据进行学习，使用多个神经元构成一个网络，并适当加入反馈机制。详情参考神经网络编程入门。

遗传算法，通过模拟染色体复制、基因变异等机制，使状态不断”进化“，从而尽量逼近最优值。详情参考遗传算法入门。

模拟退火，非常简洁、实用的一个算法，基于“爬山算法”（不断逼近离当前点最近的极值，贪心）改进而来，通过引入随机化以获得跳跃到其他极值区域的机会，从而尽可能获得更高的极值点。详情可参考《大白话解析模拟退火算法》。

此外还看到了决策树、K-mean聚类等算法，不过没有细看，只是大致扫了一眼，就不扯了。

以上给出的链接大都是讲解得非常浅显易懂的文章，非常推荐阅读。

转载自 武城路下段 By 宋大妈 http://dharmasong.net/2012/02/642.html

知识的本质

抓住知识的本质是提升学习效率的重要方法。

从数量上说，现代社会的“知识”有两个特点，第一是“总量大”，第二是“增长快”，这两个特点合在一起就是过去常说的“知识爆炸”。但知识还有另外一个特点——相比表层知识的庞大数量和几何式增长，知识的核心部分的发展要平缓得多。

以计算机领域为例，虽然计算机是二战以后发展最快的领域，但著名的黑客Paul Graham却说今天最先进的计算机技术在思想上和20世纪50年代并没有什么不同；在经济学领域，无论涉足到那一个分支，都无法离开亚当·斯密这个根本；在管理学领域，尽管各种工具、方法层出不穷，但像价值链分析这样的方法仍然根源性的；而从更大的范围上讲，思考问题的方式、解决问题的方法同样是相对稳定不会过时的；甚至知识的发展也是有规律可循，并且这些规律同样是相对稳定的。

这些知识中相对“不变”的部分恰恰是知识中最关键的部分，一个人知道很多表层的知识，我们只会说他懂点“皮毛”，只有他掌握了“不变”的知识，我们才会认为他有“学识”。而另一方面，由于知识的总量太大了，如果没有这些“不变”的知识，学习和创造就会成为不可能的事，我们常说“触类旁通”，其基础就是“不变”的知识。

上面说的道理并不复杂，但执行起来却并不容易。在现实生活中，我们见到的懂点皮毛的人要远远多过功底深厚的人，究其原因，我觉得有以下几个：

首先，相比表层知识的具体，知识的本质部分总体上是相对抽象的。理解知识的本质，其难度比认识表层要高得多，陡峭的学习曲线经常会让人望而怯步；

第二，相比表层知识的“有用”，知识的本质部分往往很难立刻发现其实际用途。这并非功利不功利的问题，而是眼光的问题，追逐长远利益的人和只看得见眼前利益的人对“有用”的认识往往是大相径庭的。但眼光长远的人之所以受到普遍的尊敬，一个重要的原因是他们是社会的少数。

第三，知识的本质经常会落实在一些常用、普通也因此容易被忽视的概念上，因为这些概念太常见了，我们经常以为自己懂这些概念，但实际上却是似是而非的。比如经济学上最基本的成本、价格这些概念，现在随便看个报纸、听听新闻都能遇到很多次，但又有多少人去深究成本与价格的概念所指？当我弄清价格其实是成本的一种特例——市场揭示出来的成本时，我是很吃惊的，既惊讶于这些概念内涵的深刻，也惊讶于我自己学习的疏忽。

写到这里，似乎应该总结几个方法去提升学习知识本质的能力，但想来想去并没有任何可以讨巧的方法，事实上，讨巧本身就是惰性的一种，而学习、创造的过程也就是克服惰性的过程，学习之苦也正是学习之甜。

（原文完）

== Felix简评 ==

觉得好像很久没有看到这样的文章了，句句切中要点。

在计算机学科，现在新技术太多了，硬件、软件、网络、架构设计……满满当当，任何一部分在任何一个层面上都学不完。甚至有很多新的技术你还没能完全掌握，就已经被淘汰了。怎么办！

好办！因为你根本不需要学习那么多的东西，只要在掌握了底层知识的基础上，适当开阔眼界，那么就根本不必烦恼知识爆炸带来的问题。

然而底层知识的学习往往是枯燥、晦涩，并且“很难立刻发现其实际用途”。例如，计算机专业开设的操作系统原理这门课，课本通常都非常理论化，内存分配策略，进程调度，生产者消费者，竞争，同步，互斥……学生们往往在学的时候不知所云，学完以后不知何用。然而在实际的项目开发中，如果开发者对于这些知识缺乏了解，那么灾难就在所难免了。

反映到实际就业来说，大部分刚毕业的计算机专业学生代码都没多少项目经验，而社会上的培训机构如北大青鸟，能够让一个人在数月内学会某个开发技术。然而那些业内顶级的公司（例如NTMGB等公司），往往并不愿意招那些培训过的，而是选择校园招聘，其中很重要的原因就是，科班出身的毕业生学习过基础知识，尽管不能马上干活，但是经过短时间的培训就能比那些培训人员做的更好。

（简评烂尾）

注：NTMGB是指网易、腾讯、微软、谷歌、百度。

很多应用层协议都有HeartBeat机制，通常是客户端每隔一小段时间向服务器发送一个数据包，通知服务器自己仍然在线，并传输一些可能必要的数据。使用心跳包的典型协议是IM，比如QQ/MSN/飞信等协议。

学过TCP/IP的同学应该都知道，传输层的两个主要协议是UDP和TCP，其中UDP是无连接的、面向packet的，而TCP协议是有连接、面向流的协议。

所以非常容易理解，使用UDP协议的客户端（例如早期的“OICQ”，听说OICQ.com这两天被抢注了来着，好古老的回忆）需要定时向服务器发送心跳包，告诉服务器自己在线。

然而，MSN和现在的QQ往往使用的是TCP连接了，尽管TCP/IP底层提供了可选的KeepAlive（ACK-ACK包）机制，但是它们也还是实现了更高层的心跳包。似乎既浪费流量又浪费CPU，有点莫名其妙。

具体查了下，TCP的KeepAlive机制是这样的，首先它貌似默认是不打开的，要用setsockopt将SOL_SOCKET.SO_KEEPALIVE设置为1才是打开，并且可以设置三个参数tcp_keepalive_time/tcp_keepalive_probes/tcp_keepalive_intvl，分别表示连接闲置多久开始发keepalive的ack包、发几个ack包不回复才当对方死了、两个ack包之间间隔多长，在我测试的Ubuntu Server 10.04下面默认值是7200秒（2个小时，要不要这么蛋疼啊！）、9次、75秒。于是连接就了有一个超时时间窗口，如果连接之间没有通信，这个时间窗口会逐渐减小，当它减小到零的时候，TCP协议会向对方发一个带有ACK标志的空数据包（KeepAlive探针），对方在收到ACK包以后，如果连接一切正常，应该回复一个ACK；如果连接出现错误了（例如对方重启了，连接状态丢失），则应当回复一个RST；如果对方没有回复，服务器每隔intvl的时间再发ACK，如果连续probes个包都被无视了，说明连接被断开了。

这里有一篇非常详细的介绍文章： http://tldp.org/HOWTO/html_single/TCP-Keepalive-HOWTO ，包括了KeepAlive的介绍、相关内核参数、C编程接口、如何为现有应用（可以或者不可以修改源码的）启用KeepAlive机制，很值得详读。

这篇文章的2.4节说的是“Preventing disconnection due to network inactivity”，阻止因网络连接不活跃（长时间没有数据包）而导致的连接中断，说的是，很多网络设备，尤其是NAT路由器，由于其硬件的限制（例如内存、CPU处理能力），无法保持其上的所有连接，因此在必要的时候，会在连接池中选择一些不活跃的连接踢掉。典型做法是LRU，把最久没有数据的连接给T掉。通过使用TCP的KeepAlive机制（修改那个time参数），可以让连接每隔一小段时间就产生一些ack包，以降低被T掉的风险，当然，这样的代价是额外的网络和CPU负担。

前面说到，许多IM协议实现了自己的心跳机制，而不是直接依赖于底层的机制，不知道真正的原因是什么。

就我看来，一些简单的协议，直接使用底层机制就可以了，对上层完全透明，降低了开发难度，不用管理连接对应的状态。而那些自己实现心跳机制的协议，应该是期望通过发送心跳包的同时来传输一些数据，这样服务端可以获知更多的状态。例如某些客户端很喜欢收集用户的信息……反正是要发个包，不如再塞点数据，否则包头又浪费了……

大概就是这样吧，如果有大牛知道真正的原因，还望不吝赐教。


@2012-04-21

p.s. 通过咨询某个做过IM的同事，参考答案应该是，自己实现的心跳机制通用，可以无视底层的UDP或TCP协议。如果只是用TCP协议的话，那么直接使用KeepAlive机制就足够了。

@2015-09-14
补充一下 @Jack的回复：
“心跳除了说明应用程序还活着（进程还在，网络通畅），更重要的是表明应用程序还能正常工作。而 TCP keepalive 有操作系统负责探查，即便进程死锁，或阻塞，操作系统也会如常收发 TCP keepalive 消息。对方无法得知这一异常。摘自《Linux 多线程服务端编程》”