肥康

最早是在嫣牛博上乱逛，看到一个叫做”推倒柏林墙“的系列几篇文章都挺好玩的。然后在网上找了一个这系列的集合，大概这半个月时不时在看这里的一些文章，从中得到不少新的认知，因此在这里推荐一下。

不像某个小同学如此年纪有如此政治觉悟，本来我是对于政治甚至历史并不怎么感兴趣的，不感兴趣是觉得政治这东西与我相离太远，也参和不上，也不想参和上。一个室友倒是经常看一些历史方面的书籍，对此较有研究，偶尔听他的一些乱侃也别有一些风趣。以前和室友瞎讨论中，对方说某些政权很危险，若干年以后很可能会出现问题，我会嗤之以鼻，看这一副和谐盛世的样子，怎么肯可能。鄙人一直生活在这么一个人为制造出的信息荒漠中，上网翻墙的次数也没上20次，又没有主动去为了某些东西去研究历史，我和很多人一样对于历史的认知度可能在初高中历史课本的范围内，所以不可避免有些乐观。我只觉得这社会确实存在不少问题，教育、财富差距、社会公平性、贪污腐败都是些大家见怪不怪的问题，如韩少所说中国人的忍耐程度几乎超过了世界任何一个国家的人，偶尔跑出来几个屠刀向儿童的、爬上楼顶自焚的、身上背炸药包的也必然不奇怪。面对社会的种种阴暗面，人们往往只是小小愤怒一把、人肉一把、然后洗洗睡了，懒得去挖掘社会如此背后的真正原因，并在这种过程中不断降低自己的忍耐底线。毕业了会发现不得不去关注一下这类的东西，因为从一个月收入中扣去不小的一块肉作为我生活在这么一个社会的义务，那么我得稍微关注一下这义务到底尽到哪里去了，也许改变不了什么，也不能成为笨蛋。这个系列的文章一共几十篇，不少东西是以前所没有认识或者认真思考过的。关于民主、体制、言论自由、文革、8*8事件、大跃进、日本问题、钓鱼岛等等各种关键词。看了这么多，只能说很心寒。之前看到一个凤凰卫视拍的朝鲜记录片，采访一朝鲜平民说知道美国前总统要来朝鲜访问么？回答说知道一个西方的领导人来听取我们领导人的教导，幼儿园小娃娃背诵的全是金日成在哪里出生，顿时觉得挺好笑的。现在想想，我们在某个层面上和这些人类似，其实朝鲜人民挺幸福的，即使是仍然要靠联合国大量的粮食资助，朝鲜人民的上学和医疗是免费的、房子也是分配的，还真有点共产主义的意思，完全的封闭和愚昧相对于半封闭和半愚昧会更容易幸福。

隔绝而又甘于自陷其中就意味着思想被左右我们还是比朝鲜好不少能接触到一些，看来还是得看点杂书、翻翻墙，别太懒。刚好这阵子还学了点Latex，既然作者可以准许随便转载，我把手里的txt整理了一个PDF格式的，点击下载《推倒柏林墙》。也许文章里所说的全是完全符合历史的，完全是真实的或者对的，因为抱着批判的态度写东西或多或少会附带了作者的情绪，但至少可以看出是一些摆事实讲道理的文章。以后多研究一下历史，凡事都別”too simple and naive”。

噢，放些这东西我的博客会不会被和谐掉？

最近在看memcached的源代码，边看边随手记录了一下。

assoc.c: 记录一个item是否存在于缓存中，这里使用了power 2扩展，primary_hashtable,和old_hashtable分别存新申请的hashtable和旧的hashtable。这里起了个线程来做拷贝的工作，当需要扩展hashtable的时候就触发assoc_expand函数，但是这个函数做的工作是备份primary_hashtable，即old_hashtable=primary_hashtable；然后申请新的空间，标识expanding为true，如果申请空间失败则交换回来。通过条件信号量，assoc_maintenance_thread把old_hashtable的数据逐步拷贝到新的hashtable中，当拷贝完了后释放old_hashtable的空间。耗时的操作用另外一个线程逐步来处理，不过查询和插入都要注意是否是在扩展状态，判断是去old还是primary里面去操作。

cache.c: 在malloc和free的基础上封装了一层，多线程安全的。维持了一个指针列表，释放的时候并没有一下就把内存还给系统，而是在列表中保存了下来，申请时如果列表中有没用的指针就直接返回给出来。能这么因为这个cache模块只是负责申请和释放size相同的内存块。

thread.c: 维持连接列表相关的内容。为一个队列，cq_push、cq_pop，维持一个LRU机制。cqi_new函数返回一个新的CQ_ITEM指针，同样维持了一个cqi_freelist，当有空闲指针的时候直接返回，当没有空闲的时候申请一个列表，从第二个开始连结成链表形式，返回第一个元素的指针。create_worker，创建一个处理线程。Item为memcached中处理的主要对象，item_alloc、item_get、item_link、item_unlink、item_remove方法，处理的时候都要锁住cache_lock。threadlocal_stats_reset、threadlocal_stats_aggregate：统计信息相关。slab_stats_aggregate：统计一个线程使用的slab信息。threadlocal_stats_reset：清空统计信息。

thread_init：主程序中调用的创建多线程函数，包括初始化互斥锁(cache_lock,stats_lock)，条件锁，空闲连接列表等。nthreads为初始化的线程数目，继续调用setup_thread启动每一个线程，调用create_worker创建处理线程。

stats.c:负责统计信息，记录get、set、delete、hits的数目。以前缀作为key。

slabs.c：负责管理内存申请和释放，slabs主要是为了避免内存碎片问题，同时提高申请内存的速度，其基本原理是大块地申请内存，根据不同的slabclass块大小分给slabclass，申请内存的时候根据地址选择最适合的slabclass，从中去下内存返回指针，释放的时候只是放在其空闲指针列表中(不少地方都用到这样的方式)。slab_list没什么用，因为释放的指针放在了slots里面啊！slabs贪婪地使用内存，整个这东西的作用就是用内存空间来换时间效率的。

memcached.c：主程序，分析设置参数默认值，分析参数根据参数修改配置参数。初始化stats，assoc，conn，slabs等。thread_init启动线程，每一个线程都有自己的struct event_base，setup_thread函数初始化这些，最重要的设置thread_libevent_process来处理新的连接。一直到：

  /* Create threads after we've done all the libevent setup. */
    for (i = 0; i < nthreads; i++) {
        create_worker(worker_libevent, &threads[i]);
    }

每个线程进入自己的event_loop。

当请求来临的时候对于每一个连接，增加一个事件来调用处理函数event_handler。每个连接的处理过程是一个状态机，drive_machine(conn* c)来处理，由even_handler来调用，状态转移这部分代码比较复杂，conn_listening —> conn_new_cmd —> conn_parse_cmd —> conn_mwrite —> conn_closing。process_command来处理各种命令。

纪念一下跑测试跑了几天才找出的一个内存泄漏，这个函数源于UNP，还以为UNP有bug呢，找到原书当getaddreinfo失败或者res==NULL的时候直接退出了。但是写这个代码的同学当然不想连接不上直接退出，于是忘记了freeaddrinfo调用直接返回，那个struct addrinfo就没释放。很多错误都是这种，涉及到库函数的时候更加难查。

int tcp_connect(const char *host, const char *serv)
{
        int    sockfd, n;
        struct addrinfo hints, *res, *ressave;

        bzero(&hints, sizeof(struct addrinfo));
        hints.ai_family = AF_UNSPEC;
        hints.ai_socktype = SOCK_STREAM;

        if ( (n = getaddrinfo(host, serv, &hints, &res)) != 0)
        {
                log_sprintf("tcp_connect error for %s, %s: %s", host, serv, gai_strerror(n));
                freeaddrinfo(res); //oops: memory leak

                return -1;
        }
        ressave = res;

        do {
                sockfd = socket(res->ai_family, res->ai_socktype, res->ai_protocol);
                if (sockfd < 0)
                        continue;       /* ignore this one */
                if (connect(sockfd, res->ai_addr, res->ai_addrlen) == 0)
                        break;          /* success */
                close(sockfd);  /* ignore this one */

        } while ( (res = res->ai_next) != NULL);

        if (res == NULL)        /* errno set from final connect() */
        {
                log_sprintf("tcp_connect error for %s, %s", host, serv);
                freeaddrinfo(ressave); //oops: memory leak
                return -1;
        }
        freeaddrinfo(ressave);
        return(sockfd);
}

上一篇博文中说到自己包装的内存检测方法，这还有个问题当时没发现，就是那个包装malloc之类的方法对于库函数中的内存申请调用没法记录，所以是不会发现上面这个bug的。这个Memwatch倒是把原生的malloc都重定义了，但是最好的Linux下检测内存泄漏的工具还是valgrind，这真是个神器，在代码上不用做一点修改，这东西甚至能测试程序的cache命中率。看了一下valgrind的相关论文，对于检测方法都是一种称之为shadow value的方法，也就是用信息来记录每一个byte内存的使用情况。这种方式的一个缺点都是会拖慢速度，前面提到的那种稍微包装了一下的方式可能还好(因为使用的是静态数组), Memwatch里面使用了不少链表也会拖慢速度。再看看valgrind的实现，以后工作可能会碰上类似的。

更多valgrind

更多Memwatch

内存泄漏

上一次以为内存泄露查完了，发现服务器跑了比较长时间后又占用太多内存。刚好这段时间加了一些新的模块，又该查查了。整个服务器模块分的还行，但是中间经过几个人一起写，所以看起来就麻烦了。要解决问题还是必须找到泄露的代码段。在C/C++中，只要用了指针这东西，很多逻辑上的问题也会产生内存泄露。在线下用上次封装malloc和free的方法测试，找不到产生内存泄露的样例，grep了一下没有用原来的malloc之类的东西啊，那就应该是测试数量太少的问题。没法，从线上的log中导入一些天的访问记录，其中包含了一天的访问url。试着用Python写个小程序把一天中所有的url依次往线下的服务器发送，这应该有几万条数据了。Python中这相关的库够多的,可以用的httplib,或者webbrowser模块中的webbrowser.open(“url_address”,1),不过这得打开系统的默认的浏览器，并且好像还没关掉一个tab的接口。最合适这个简单任务的是urllib这个模块，下面这样就行了，往线下的服务器狂发请求吧:

    for rec in alllogs:
        urlstr = rec[0]
        #print urlstr
        line=line+1
        print line,allnum,allnum-line,urlstr
        try:
            u = urllib.urlopen(urlstr)
        except IOError,e:
            print 'connect refused',e
        except UnicodeError,e:
            print 'UnicodeError',e
        res = u.read()
        ##print u.info()

        print "read %d data"%(len(res))
        ##time.sleep(0.01)

调试方式

Linux下有一些内存调试工具，不过感觉要么过于复杂要么对代码改动太多，对于在后台这种长时间运行的程序不是很适用。上次提到的封装malloc,calloc,free这些函数的检测方法本来是挺好的，但是有两个问题：

1.用于存储内存信息的空间是用数组的，其大小运行时候就固定。
2.不适合多线程程序。

如果用上面所有的url向服务器发送完毕后，再来检查输出文件不可行，因为运行中超过了数组的最大记录数后面的检测就没办法记录下来了。对于第二个问题，这个服务器模型是一种简单的多线程并发，启动时设定其启动线程的数目，多个线程排队，一个线程处理一个请求所以之间并无过多的交互。如果保证一个线程运行过程中不会出现内存泄漏，那应该就没问题了。调试的时候在每一个线程开始跑的时候就启动清空上面的记录内存申请和释放的数组，如果某个一个url请求产生了泄漏就停下来查看生成的meminfo.xls。这样跑完几万个url后，发现一些代码问题。这些bug要是通过人来审查代码不可能查出来，所以测试还是非常重要。其中一部分代码错误是使用了C写了一些基本的数据结构，这些里面有的使用了malloc来动态调整空间大小，用起来倒是比较方便，但是用完后必须显式地释放掉。这和指针的问题是一样的:何时何地释放。调试后会在代码中加入了很多语句，打印信息、脚手架位置等等，这可以用下面这些命令来替换成空白或者注释。

 grep debug_str -rl ./*.c | xargs sed -i "s/debug_str/substr/g"

1  学吉他

我终于开始学吉他了，五音不全双手不灵活不识谱的我居然开始学吉他了。跟某些朋友说我要学吉他，对方往往有几种反应：1.头被墙夹了 2.要改变风格了？装文艺小青年了？ 3.要追哪个女生么？其实弹吉他还是符合本人闷骚这一特质的。说来惭愧，很早就想学点乐器了，小时候爸想让我学二胡来着，幸好没学，一听那声音就觉得悲催啊。在我高中毕业那会，会憧憬着大学应该能拿个吉他在湖边，身边还有个妹子坐着。这个画面在沙河少林寺和清水河少林寺连实现的欲望都没有。所以，这么个小愿望到现在才付诸实践。前些天买了个民谣吉他，目前还只上了一堂课，右手拨弦有点感觉了，左手按着很痛，这要靠长期练习，慢慢来吧。等我学会了对某个女生来这么首歌-黑眼睛的姑娘。

音频片段：需要 Adobe Flash Player（9 或以上版本）播放音频片段。 点击这里下载最新版本。您需要开启浏览器的 JavaScript 支持。

2 到处逛了一趟

从上学期开始实习并找工作以来就没怎么出门玩过，这段时间刚好论文写完，可以出去耍耍。刚好王聪同学从北京解放后开始到处游荡，打算在成都待一周，所以一起找个地方玩。本来计划去海螺沟的，出发前一天晚上被某失恋男说服去碧峰峡。提前假期一天出发，到了雨城雅安。上里古镇没什么好玩的，就是一条河，半个多小时逛完了。立马往碧峰峡赶，下午三点多才到，已经不卖门票了。在山上的旅馆住了一夜，晚上三个大男人在旅馆看成都电视台的特色节目《今天我相亲》，真实得很喜感。第二天从碧峰峡动物园开始逛，因为学生证没带，我买了全票，看完后真是觉得不值啊！！下午逛植物园，在票上看到一个雅女园。话说雅安三大特色：雅雨、雅鱼、雅女，这雅女园莫非有什么非同寻常的东西:)。沿着碧峰峡逛了一圈，中途发现三个mm，其中两个算是美女双胞胎，于是我们三个后面一直处于两种状态，等mm追上我们，在后面追mm。到最后最后，除了王同学搭讪了一句并且没下文，我们都只是有胆看没胆搭讪，很失败。逛完大概耗时三个多小时，急忙忙看完熊猫就得赶车回成都了，前面一直满怀期望的雅女园都没来得及逛，不过肯定是没雅女在里面的，哈哈。总得来说，这碧峰峡是不值我那两张全票的价格的，风景算一般吧。

回成都第二天去了石象湖，在我印象中石象湖应该是不错的，有几个人向我推荐过此处。于是叫上那失恋男饭量同学三个人一起前往。快出成都上高速的时候才发现出来的不是时候啊，车暴多太堵塞，经过漫长的堵车后13点多才到。在门口感觉已经不好了，人太多。进去后刚开始一块还可以，全是一片一片的郁金香，美女也不少。逛进去也就没什么了，一个小湖加几个小石头象，坑啊，开发商太黑了，弄个几个别墅在这园里，卖房又卖票。三个人很失望，立马找出口。在门口等回成都的车足足等了一个多小时，在路上又堵了一个很久，这一天总共在来回路上耗费七个小时，人挤人看了一个小时！我提议的出游计划，对不住两位了。这几天玩下来还真是有点累！

接下来该锻炼一下身体，打算去青海骑车，目前有四个人了。

前些天在写毕业论文，开题弄了个什么神经网络什么数据融合，至今没搞懂过，真是没话说，但是又不得不硬着头皮写，废话连篇，说来说去就那么几句。做的东西本来挺简单的，没用到那么高深的理论，不过为了装装深度，硬要往上面套，希望最好别出什么问题吧。写论文的时候我就想嗄，写代码好玩多了，异常怀念那段天天在poj上写程序的日子。这两天交完初稿，继续做做题，一是玩玩，二是为了原来定下的一个小目标：毕业前水到500题，还差20。两个比较好玩也折腾得比较久的题目。

poj 2050

这题折腾了很久很久，刚开始误以为每个文件的最大行数为1500，最后因为输出格式问题。代码也比较长330行，954ms。
使用数组作为hash，使用位图记录文件中存在的单词，idx为由单词转化得到的该单词在hash表中的index。

unsigned int docs_flag[MAXDOC][(MAXWORDS+31)/32]; //记录某个文件中是否存在某个单词
void set_docflag(int doc[], unsigned int idx)
{
        doc[idx>>5] |= (1<<(idx&0x1f));
}

int  get_docflag(int doc[],unsigned int idx)
{
        return doc[idx>>5] & (1<<(idx&0x1f));
}

poj 2518

这个好玩，一个4*4的方格，里面分别放四个A,B,C,D，初始状态从输入获取，先随便选取一个字母，然后能进行很多次操作。
每次能交换两个相邻的方格，到任何一个小的2*2的方格中全部都是所选的字母就获胜。对于每一个输入，求最少多少次交换就能达到胜利状态，
以及有多少方案可以达到这个目的。

例如：

AABB
ABAB
CDCD
CCDD          output ==> 1 4 (选择A或者B 交换BA 选择C或者D 交换DC)

ACAB
CBBD
ADAD
DCBC          output ==> 4 96

首先想到还是搜索，用bit来减少空间。求最少次数，BFS搜索也许太慢，毕竟每次状态转移会有16个选择。对于每一个输入，先枚举A,B,C,D进行搜索。对于每一个字母，比如A，用一个整数表示其在方格的位置(最大数字到1<<16)，

AABB
ABAB
CDCD
CCDD            state ==> 1100 1010 0000 0000

胜利的状态有9个，可以先枚举出来，1100110000000000等等。胜利状态比较多，照一般的BFS写下去代码肯定比较复杂，时间和空间肯定也都要求比较多。考虑可以从胜利状态反着向初始状态搜，先把9个胜利状态放入数组，求到初始状态最少的步数，同时可以算出有多少种走法。这样做了还是超时，看有人说线上输入有很多组数据。

看来每次计算调用了四次BFS确实比较要时间，看提示打表，对于每一个输入先查查看以前计算过没有，计算过则直接输出结果，否则照上面的枚举字母，调用BFS。提交还是超时。

再想想，每次输入可能A的分布是一样的，其他字母分布不一样，照上面那样做对于A还是BFS搜索了一次。从16个位置选择4个位置给A的总分布数目是C(16,4)=1820，不是很大的。很开心，把A的状态记录下来，对于每个输入先看看A这种布局以前算过了没有，如果算过则不用算了，其他字母都是一样处理。结果还是超时，无语了。

正要崩溃时，发现自己还是没看到本质，对于A的每一个布局，B不是一样么，是A还是B没关系的啊。所以，打表不用分字母需要1820*4这么大的表，只要一个1820的表就行了。对于每个输入，分字母获取四个分布状态，看这个状态以前是否算过了，如果算过直接拿那个结果，如果没算过算了存下来。再提交，终于AC了，：）这一步步够辛苦的。