Oenhan Google Reader

    Oen 通过 Google 阅读器发送给您的内容：     一个绝妙的 exploit 于 13-5-15 通过 A Geek's Page 作者：王 聪 最近 Linux 内核爆出了一个严重的安全漏洞，非root用户可以通过该 漏洞的 exploit 获取root权限。这并不罕见，值得一提的是这个补丁看起来如此平常以至于我们绝大多数人都不会以为这是安全问题。 先看这个问题的 补丁 ，就是下面这个： static int perf_swevent_init(struct perf_event *event) { - int event_id = event->attr.config; + u64 event_id = event->attr.config; if (event->attr.type != PERF_TYPE_SOFTWARE) return -ENOENT; 我们第一眼的感觉就是这大概只是修复了编译器报的一个小警告吧，怎么会引起如此严重的安全问题呢？ 在没打补丁的代码中 event_id 是个 带符号 的整型，而且就在下面不远处的两行代码中只检查了其上界： PLAIN TEXT C: if ( event_id> = PERF_COUNT_SW_MAX )                 return - ENOENT; 而如果传递进来的 event->attr.config 值正好设置了符号位，那么 event_id 就会变成负值，而且能躲过上面的检查。 负值意味着什么呢？再继续看后面的代码： PLAIN TEXT C: if ( ! event - >parent ) {                 int err;                   err = swevent_hlist_get ( event ) ;                 if ( err ) ...

    Oen 通过 Google 阅读器发送给您的内容：     binary array search的几种写法（go） 于 13-6-3 通过 shenfeng's blog 儿童节那天， 对比了python内置的dict和binary array search查找的性能 ，dict大幅领先，有些出乎意料： dict虽然是O(1)，binary search是O(log n)。当n为1M时，log n也仅有20，并且直观上log n前面的常数不大，理论上应该和O(1)差别不是很大 怀疑到python语言，binary array search是由手工python实现，而dict是C实现。python语言比C慢很多 所以，6月2日，用go语言来对比一下，也熟悉一下go语言。 binary search有几种写法： recusive : 递归 3-branch : 迭代，每次迭代进行2次判断 == ， < （或者 > ），三个分支。找到后，立刻退出。最好情况为O(1) 2-branch : 迭代，每次迭代进行1次判断 < （或者 > ），二个分支。最好情况也为O(log n) library : go标准库 sort.Search ，它是3的通用版本，需要提供一个函数，用来提供 > 或 < 的依据 2-branch 3的想法比较有意思，它是先计算出对于要查找的数，如果放入这个已经排好序的数组array，下标是多少。如果在array里，有重复，返回的是则是第一个的下标。最后再对比一下数组里面的数，是否正是需要查找的key func binary_search2 ( arr [] int , key int ) int { lo , hi := 0 , len ( arr ) - 1 for lo < hi { mid := ( lo + hi ) / 2 if arr [ mid ] < key { lo = mid + 1...

    Oen 通过 Google 阅读器发送给您的内容：     公司这个利益组织 于 13-5-29 通过 扯氮集--上海魏武挥的博客 - 扯氮集--上海魏武挥的博客 作者：魏武挥 春秋吴越战争，勾践在范蠡和文种的帮助下，卧薪尝胆，终于把吴给灭了，成就霸业。范蠡决定跑路，勾践许诺"共分越国"，范蠡回"君行其法，我行其意。"文种挽留，范蠡反过来劝说："狡兔死，走狗烹；高鸟尽，良弓藏。越王为人，长颈鸟喙，可与共患难，不可与共荣乐，先生何不速速出走?"文种未听，后被赐剑而死。 范蠡说越王长相如何，由此而得"可共患难而不可共荣乐"。这话有点神神叨叨，论据不足。但范蠡说的是人性。大概率情况而言，的确人都是"可共患难不可共荣乐的"，为了赌一个小概率结果，把阖家性命押上，非智者所为。 公司亦然。 互联网企业，绝大部分都实施股权制或期权制，公司以为重要的人都会安排股权期权激励。一方面，对于很多创业公司而言，工资不高但要吸引人才，只好用股权期权来画个大饼。成功的榜样不是没有（据说百度上市时楼下的4S店都卖空了），比较有说服力。股权期权制，大有一丝丝的"共分越国"之意。在这个制度下，创始人会反复宣传这种理念：这个公司不仅仅是我的，也是大家的。嗯，有点那么个意思。 这套说法，涉世不深的年轻人很容易被忽悠进去，我也被忽悠过。关键在于，我认为我们现在的历史教育充其量只是在说故事，学史要知兴替，知兴替要明白里面的因果。范蠡的故事，就是可以用来知兴替的。不然只是知道范蠡跑了文种死了，有何意义？ 说这个说法是忽悠，不是说它在撒谎。忽悠的意思是有真有假，有合理之处，也有荒谬之处。因为它没有细分两样东西，而这两样东西其实是不能混在一起说的。...

    Oen 通过 Google 阅读器发送给您的内容：     在新 Thinkpad S3 上使用 bcache 作为 Linux 的根分区 于 13-6-1 通过 我有分寸 作者：gnawux 前两天采购了一台"全球首发"的 Thinkpad S3 超级本 ，激动之余，就把不会用的 Windows 8 给抹掉，装上 Linux 了。这台机器的配置如下 CPU i5-3337U 内存 8GB 芯片组 Intel HM77 显卡 CPU集成 + Radeon HD 8670M 硬盘 500GB SATA + 24GB mSATA SSD 嗯，其他先不说了，亮点基本就这些。新机器，一大堆支持得不好的东西，比如 suspend to ram 我到现在还没配好，先不说了，这次主要说硬盘。 基本思路 这台机器有一块过小的 SSD 和一块主硬盘，因为SSD太小了，以至于我不想把哪个分区整体放到上面，于是，想到了分级存储的策略——使用SSD作为缓存，让热数据缓存在SSD上，冷数据留在机械硬盘上，是的，这个和被广泛宣传的 Apple 的 Fusion Drive 很类似，当然，Apple 不是第一个开发这种技术的公司。 在 Linux 上，最广为传颂的这类技术就是 bcache 了，但有一个问题，bcache 直到 3.10 才进入 kernel，而 3.10 到目前为止还只是 -rc3。也就是说，如果要装 Debian、Ubuntu、Fedora 的话，你至少要等半年，才能找到一张支持 bcache 的启动盘。不过，我还是想用下这个个 Distro，于是，就采用了这样一个思路（思路抄袭自 这个 Arch 的 Wikipage ，有调整）: 先在 SSD 上装一个临时的系统 升级内核，支持 bcache 在主硬盘上做一个分区，作为 bcache 的后端存储 把装好的系统迁移到上面的 bcache 分区 修改 grub 重新启动，引导到 bca...

    Oen 通过 Google 阅读器发送给您的内容：     一些鲜为人知却非常实用的数据结构 于 13-5-27 通过 博客园_256code, 生活与技术 作者：Haippy 作为程序猿（媛），你必须熟知一些常见的数据结构，比如栈、队列、字符串、链表、二叉树、哈希，但是除了这些常见的数据结构以外，还有没有其他不是很有名，但却非常实用的数据结构呢，有人在 stackoverflow 上问了这样一个问题，得到了很多热心观众的回答，我们今天就来看看那些鲜为人知却非常实用的数据结构吧。 首先，维基百科上的一个页面列举了 常见的数据结构 ，你可以先去那个页面看看。下面我们就来看看一些不是很常见的数据结构吧： Tries (前缀树) Bloom filter (布隆过滤器) Rope : 主要用于某些文本编辑器中，可用于字符串高效地插入、删除、追加等操作。SGI 的 STL 中实现了 Rope(http://www.sgi.com/tech/stl/Rope.html) Skiplist (跳表) Spatial Indices (空间索引)，如 R-trees 和 KD-trees Splay trees (伸展树) Disjoint Set (并查集) Fibonacci heaps (斐波那切堆) Huffman trees (哈夫曼树) ring buffer (又名circular buffer) Merkle trees (哈希树) min-max heap bitset (又称bit array, 位数组) Xor linked list AA tree Log-structured merge-tree Radix tree Judy array       本文链接     可从此处完成的操作：...

    Oen 通过 Google 阅读器发送给您的内容：     gdb的基本工作原理是什么？ 于 10-10-28 通过 SpongeLiu的blog 作者：sponge 还是面某M的时候，面试官问我："用过gdb么？" 答："用过，调了两年bug了"。"那好，给我解释下gdb是怎么工作的？或者说跟内核什么地方有关系？"。 是阿， gdb凭什么可以调试一个程序？凭什么能够接管一个程序的运行？ 我以前也想过这样的问题，但是后来居然忘记去查看了。我想到了我们的二进制翻译器，想到了intel的pin，Dynamo。这些都是将翻译后的代码放到codecache中去运行，然后接管整个程序的执行。gdb是不是也一样呢？ 如果真是这样，为什么我记得用gdb跑一个程序，这个程序会有一个单独的进程？gdb的attach功能又是怎么实现的？ 想了想，我还是没有答上来。面试就是由这么一个又一个细节的小杯具最后汇集成一个大杯具。 那么，gdb到底是凭什么接管的一个进程的执行呢？其实，很简单， 通过一个系统调用：ptrace 。ptrace系统调用的原型如下： #include <sys/ptrace.h>   long ptrace ( enum __ptrace_request request , pid_t pid , void * addr , void * data ) ; 说明：ptrace系统调用提供了一种方法来让父进程可以观察和控制其它进程的执行，检查和改变其核心映像以及寄存器。 主要用来实现断点调试和系统调用跟踪。（man手册） 其实，说到这里，一切原理层面应该都比较明朗了（且先不去管内核中是怎么实现ptrace的）。gdb就是调用这个系统调用，然后通过一些参数来控制其他进程的执行的。 下面我们来看ptrace函数中request参数的一些主要选项： PTRACE_TRACEME： 表示本进程将被其父进程跟踪，交付给这个进程...

    Oen 通过 Google 阅读器发送给您的内容：     字符串匹配的Boyer-Moore算法 于 13-5-2 通过 阮一峰的网络日志 上一篇文章，我介绍了 KMP算法 。 但是，它并不是效率最高的算法，实际采用并不多。各种文本编辑器的"查找"功能（Ctrl+F），大多采用 Boyer-Moore算法 。 Boyer-Moore算法不仅效率高，而且构思巧妙，容易理解。1977年，德克萨斯大学的Robert S. Boyer教授和J Strother Moore教授发明了这种算法。 下面，我根据Moore教授自己的 例子 来解释这种算法。 1. 假定字符串为"HERE IS A SIMPLE EXAMPLE"，搜索词为"EXAMPLE"。 2. 首先，"字符串"与"搜索词"头部对齐，从尾部开始比较。 这是一个很聪明的想法，因为如果尾部字符不匹配，那么只要一次比较，就可以知道前7个字符肯定不是要找的结果。 我们看到，"S"与"E"不匹配。这时， "S"就被称为"坏字符"（bad character），即不匹配的字符。 我们还发现，"S"不包含在搜索词"EXAMPLE"之中，这意味着可以把搜索词直接移到"S"的后一位。 3. 依然从尾部开始比较，发现"P"与"E"不匹配，所以"P"是"坏字符"。但是，"P"包含在搜索词"EXAMPLE"之中。所以，将搜索词后移两位，两个"P"对齐。 4. 我们由此总结出 "坏字符规则" ： 　　后移位数 = 坏字符的位置 - 搜索词中的上一次出现位置 如果"坏字符"不包含在搜索词之中，则上一次出现位置为 -1。 以"P"为例，它作为"坏字符"，出现在搜索词的第6位（从0开...

    Oen 通过 Google 阅读器发送给您的内容：     字符串匹配的KMP算法 于 13-5-1 通过 阮一峰的网络日志 字符串匹配 是计算机的基本任务之一。 举例来说，有一个字符串"BBC ABCDAB ABCDABCDABDE"，我想知道，里面是否包含另一个字符串"ABCDABD"？ 许多算法可以完成这个任务， Knuth-Morris-Pratt算法 （简称KMP）是最常用的之一。它以三个发明者命名，起头的那个K就是著名科学家Donald Knuth。 这种算法不太容易理解，网上有很多 解释 ，但读起来都很费劲。直到读到 Jake Boxer 的文章，我才真正理解这种算法。下面，我用自己的语言，试图写一篇比较好懂的KMP算法解释。 1. 首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。 2. 因为B与A不匹配，搜索词再往后移。 3. 就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。 4. 接着比较字符串和搜索词的下一个字符，还是相同。 5. 直到字符串有一个字符，与搜索词对应的字符不相同为止。 6. 这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把"搜索位置"移到已经比较过的位置，重比一遍。 7. 一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。 8. 怎么做到这一点呢？可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。这张表是如何产生的，后面再介绍，这里只要会用就可以了。 9. 已知空格与D不匹配时，前...