Aiur

zellux 的博客

ICS Lab 8 - 实现一个简单的代理服务器

折腾了一下午加晚上,看了一堆包后总算把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都打不开的。 阅读全文 →

ICS Lab 7 数据结构相关

这个Lab是要自己实现一个malloc函数,要求内存利用率和速度尽可能高。 用红黑树的版本最后得分是97/100,没有针对测试数据作任何优化,据说可以改到100/100,不过95分以上就满分了我也懒得再改了。 这个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,直到现在和具体语言无关的算法层次,对写高效代码的帮助蛮大的。 阅读全文 →

ICS Lab 6

重定向: 主要用到open, close, read和write这几个函数,关于它们的使用方法可以使用 man 2 <函数名> 查看。 这里简单介绍下: Linux内核为每个进程维护了一张已打开的文件的表格,用File Descriptor(整型,以下简写成fd)可以访问到这些文件。所以很容易理解tsh.c中的函数listjobs为什么需要一个output_fd的整型参数,注意它的后面有这么一行: if (writer(output_fd, buf, strlen(buf)) < 0) … 这一行就把前面构造好的buf字符串(包括当前进程的信息)输出到这个output_fd对应的文件中了。 每个进程的值为0, 1, 2的fd都指向相同的文件,0对应标准输入(通常是键盘输入),1对应标准输出(通常为屏幕),2对应标准错误输出。 可以看到在main方法的开头,有这么一句 dup2(1, 2); dup2的作用是把参数二指向的文件改成和参数一一样(如果之前打开了文件,则先关闭),这句话的作用就是把原来要输出到标准错误端(stderr)的内容 输出到标准输出端(stdout),便于调试。 理解了fd和dup2的作用后,重定向也就很容易实现了,一种最简单的方法就是先用open函数打开输出文件并得到对应的fd,然后用dup2把标准输出/输入端的指向改成文件的fd。 另外注意用open创建输出重定向的文件的时候要加上S_IRUSR和S_IWUSR选项,否则创建后的文件没有读写权限。(不过好像这个lab的测试数据比较厚道,会事先touch一下,不加这两个选项应该也能通过测试) 一些文档中未定义的行为: argv 假如我输入的命令是/bin/ls -l > ls.txt,对应的argv应该包括哪些内容呢? 一般的情况argv的内容应该是[‘/bin/ls’, ‘-l’],后面的重定向符是不包括的不过在这个lab中似乎没有这个限制,不去掉重定向和管道部分应该还是能通过测试的。 Job ID的分配 如果现在1, 2, 4号子任务在后台运行,再新增一个进程的话应该给它分配多少呢? 这个问题不需要处理,只要所有的jobs队列操作统一使用tsh.c中给出的几个函数就行。 其他: 关于信号的转发、后台前台的转换等内容,文档和书上都说得很清楚了,这里不再赘述。 P.S. 多进程程序的调试大家之前应该接触的比较少,其实这个lab大致的代码不难写,难点在于细节上的debug比较困难,调试过程对第八章的理解很有帮助。 阅读全文 →

ICS Lab4 常用优化方法

几个基本的优化: 用iaddl代替irmovl, opl,效果显著 删去不必要的andl,效果显著 改变判断分支(大多数是正数),效果显著 实现Load Forwarding,效果显著 函数结束时使用自己的epilogue,效果一般 Unrolling相关: 通过合并相邻两个循环,把mrmovl和rmmovl拆开,效果显著 32, 16, 8, 4, 1分段处理,效果显著,我用这个方法做到过7.2左右 Jump Table 由Duff’s Device引申出来的想法,代替了我原来那个32-16-8-4-1程序。 很好用的一个技巧,配合unrolling就不需要不断比较i和len的大小了。 比如len=15的时候,只要跳转到倒数第15个复制段落,就可以挨个做下来,而不需要多余的判断。 具体的实现可以想想x86里的情况,假设几个复制段落的标签为Loop1, Loop2, … jump: .long Loop1 .long Loop2 … 之后就只要取出jump + (len - 1) * 4处的值,然后跳到这个位置就行了。 跳的时候还有个技巧,最简单的是把这个值push到栈,然后再ret。这样的话bubble很多。 考虑到这个模拟器里代码段是不受保护的,也就是说运行的时候可以动态修改内存中的代码,于是在跳转的地方写个jmp 0,然后运行的时候动态把这个0改掉就行。 另外要注意用这个方法的时候得手动写几个nop,或者在改内存的语句和jmp语句之间加几个其他命令,因为y86模拟器是默认程序不会修改自己的代码的(p328 灰色背景部分)。 用这个方法的时候还有一些细节可以优化,就不列举了。另外不知道利用自我修改这个特点能不能做出更神奇的效果呢? 比如我还想到另一种类似的方法,让程序从头到尾运行,不跳转,而是在程序运行时动态的插入ret语句直接把程序运行流掐断。我还没试过,有兴趣的同学可以试一试。 不知道还有没有其他的优化方法,欢迎讨论~ 阅读全文 →

ICS Lab4 经验

编译 不安装图形界面: 修改sim/Makefile,把前三行非注释部分用#注释掉,变成 # GUIMODE ... # TKLIB ... # TKINC ... 保存后运行 make 图形界面 安装Tcl/Tk库 Redhat 9: 可以在Redhat菜单->System Settings->Add/Remove Applications中添加X Software Development,根据提示载入相关镜像文件。 然后在 sim 目录下运行 make Arch Linux: 有包管理机制的发行版直接用相关软件安装(比如 Arch 中 pacman -S tcl tk),注意安装好以后生成的动态链接库可能带有版本号(比如 libtcl8.5.so libtk8.5.so) 具体版本号通过 pacman -Ql tcl tk | grep '.so' 查得 接着只要修改Makefile中的TKLIBS参数,或者用ln建个链接即可 Ubuntu 由于ubuntu默认没有lex词法分析工具,在编译时需要先安装flex:sudo apt-get install flex 图形界面和Arch类似 sudo apt-get install tcl8.5-dev tk8.5-dev tcl8.5 tk8.5 然后修改 Makefile 阅读全文 →

ICS Lab3 简易攻略

这个 Lab 应该比上一个 Lab 简单不少, Lab 的说明文档也差不多把基本的过关要点都提到了,所以这里主要介绍一下几个相关工具的使用,帮助大家进一步熟悉 Linux 命令行 ;-) 首先从主页上下载一个压缩包,最简单的方法是直接在命令行使用 wget 工具 wget http://10.132.143.100/lab2007/buflab-handout.tar 顺便提一下 wget 的功能很强大,除了可以在后台运行,它还支持 ftp https http 等协议,提供整个网站下载的功能(类似于 Windows 下的 WebZIP ) 接着使用 tar 命令解压这个文件 tar xvf buflab-handout.tar 其中, x 参数表示解压工作, v 表示显示解压所得的文件列表, f 及其后面跟着的文件 名指定了待解压文件 这样在当前目录下就多出了三个文件: bufbomb, makecookie, sendstring 接下来使用 makecookie 得到自己学号对应的 cookie 号,用法是 ./makecookie 学号 这个 cookie 号在后面的几个关卡中都有可能会用到,同时 http://10.132.143.234/bufbombstatus.html 中可以通过自己的 cookie 号随时获得自己现在的过关情况。 和上一个 Lab 一样,这里介绍一下怎么过 Level 0 。 这个热身关和两个函数有关, test() 和 smoke() ,正常情况下 smoke 不会被任何函数调用,我们要做的就是输入一串特定的字符,使得 smoke 被调用。另外这个关卡简单之处在于 smoke 被调用后就直接退出程序,我们在破坏了栈的数据后不需要恢复原样。 阅读全文 →