Aiur – ZelluX 的技术博客

折腾了一下午加晚上，看了一堆包后总算把HTTPS协议搞定了，趁热写点心得。

这个Lab很强大，把11 12 13三章的内容全串起来了。

HTTP部分很简单，读个请求头把主机分析出来（有现成的函数），然后把客户端的所有请求传给Web服务器，再把服务器的所有反馈信息传给客户端就行了。另外注意传信息的时候不要使用Rio_readlineb之类的函数，而要用Rio_readnb，否则传图像时会碰到问题。

另外把版本统一成HTTP 1.0能明显的提高代理服务器的速度，具体原因还不清楚，明天再问问。

如果要把这个代理服务器写得健壮一点，要注意各种异常的处理，比如通常浏览器都能发送正确的报头，但是如果有人通过telnet发送了错误的报头也要能够正确的释放内存再结束线程。

然后是线程，这个问题也不大，使用信号量实现互斥锁，另外在即时free资源就好。

最后就是HTTPS协议的处理了，由于没正确理解文档的意思，在这上面花了很多时间，不过倒也接触了不少新东西。

首先是用gdb调试多线程程序，使用info threads查看当前所有线程，然后thread #切换到该线程就能查看那个线程的相关信息了。

然后来说下HTTPS协议的处理。一开始我有个错误的概念，就是代理服务器的责任是把所有客户端的信息转发到服务器端，把所有服务器端的信息转发到客户端，或者说在浏览器的眼中代理服务器和普通的Web服务器没有区别。其实并非如此，在我用OmniPeek截包看了半天后才意识到自己错了 =_=

浏览器不通过代理进行HTTPS连接时，只发送加密后的数据；而通过代理服务器时，先告诉代理服务器相关信息，然后再发送密文。另外，HTTPS的明码报头一般不会像文档中那样只有一行，代理服务器要记得所有的明文都读进来（但不转发给Web服务器），然后回复HTTP/1.0 200 Connection established，最后再负责密文的转发。

HTTPS的数据转发也和HTTP不一样，它需要客户端和服务器端多次的双向数据传输。而默认的read方法在没有信息读取和其他中断发生的时候是会block的。对于这个问题我的解决方法是结合I/O Multiplexing和Non-blocking I/O（搜资料的时候看到过这样处理的效率也比较高，见http://www.kegel.com/c10k.html）。用fcntl设置两个file descriptor的模式为O_NONBLOCK，然后再用select/poll实现multiplexing即可。不知道还有没有更好的方法。

另外测试HTTPS时建议使用https://mail.google.com，文档中的两个网页貌似firefox都打不开的。

这个Lab是要自己实现一个malloc函数，要求内存利用率和速度尽可能高。
用红黑树的版本最后得分是97/100，没有针对测试数据作任何优化，据说可以改到100/100，不过95分以上就满分了我也懒得再改了。

发信人: Zellux (1a2a3a4a5a6a7a8a9a0a, gg), 信区: Software_06
标 题: ICS Lab 7 数据结构相关
发信站: 日月光华 (2008年06月10日22:48:03 星期二), 站内信件

有人来催稿，随便写一点吧 =_=

这个Lab的重点在可用内存的管理上。关于数据的组织，似乎有两种比较常见的形式（我不知道的就不算进来了，下同 =_=）。一是slab/buddy系统，就是书上讲的segregated list；还有一种用二叉树实现，这个lab我用了二叉树。

第一种方法对提高性能很有帮助，但是利用率方面就比较有限了。而这个lab似乎提高性能比较容易，难点在于利用率的提高。

二叉树方面，也有两种：平衡二叉搜索树（AVL树、红黑树等），字典树（Trie, 似乎也叫Radix tree）

这些数据结构都比较经典，很多书上都有现成的代码，网上也有一堆，拿来改一下就行了（注意算法导论上的红黑树的left-rotate是有bug的，见勘误表）。

另外还有个优化，树的结点要保存很多数据，比如父结点、左右结点、前后结点（考虑到同一大小的块的存在），红黑树中还需要保存一个颜色值（当然这个值可以保存在header中）。如果所有的空结点都以这种形式保存的话，势必对利用率影响很大。

所以建议另外维护一个block size相对较小的（比如小于128字节）的list，把小于这个值的空闲块都放到那个list里。

差不多就这样了，思路还是蛮简单的，就是实现起来很恶心。

另外做的时候还可以考虑考虑多线程的情况下这个malloc的表现会如何。

感觉下学期的几个lab，Lab 4 5 7都和优化程序性能有关，颗粒度不断提高，从最底层的汇编指令，到语言级别的unrolling、splitting，直到现在和具体语言无关的算法层次，对写高效代码的帮助蛮大的。