Leo | 酷壳 - CoolShell

Cuckoo Filter：设计与实现

2015年09月02日 Leo 评论 37 条评论 68,814 人阅读

对于海量数据处理业务，我们通常需要一个索引数据结构，用来帮助查询，快速判断数据记录是否存在，这种数据结构通常又叫过滤器(filter)。考虑这样一个场景，上网的时候需要在浏览器上输入URL，这时浏览器需要去判断这是否一个恶意的网站，它将对本地缓存的成千上万的URL索引进行过滤，如果不存在，就放行，如果（可能）存在，则向远程服务端发起验证请求，并回馈客户端给出警告。

索引的存储又分为有序和无序，前者使用关联式容器，比如B树，后者使用哈希算法。这两类算法各有优劣：比如，关联式容器时间复杂度稳定O(logN)，且支持范围查询；又比如哈希算法的查询、增删都比较快O(1)，但这是在理想状态下的情形，遇到碰撞严重的情况，哈希算法的时间复杂度会退化到O(n)。因此，选择一个好的哈希算法是很重要的。

时下一个非常流行的哈希索引结构就是bloom filter，它类似于bitmap这样的hashset，所以空间利用率很高。其独特的地方在于它使用多个哈希函数来避免哈希碰撞，如图所示（来源wikipedia），bit数组初始化为全0，插入x时，x被3个哈希函数分别映射到3个不同的bit位上并置1，查询x时，只有被这3个函数映射到的bit位全部是1才能说明x可能存在，但凡至少出现一个0表示x肯定不存在。

Bloom_filter

…

阅读全文 Read More

(51 人打了分，平均分： 4.20 )

Linus：为何对象引用计数必须是原子的

2014年12月31日 Leo 评论 37 条评论 50,897 人阅读

（感谢网友 @我的上铺叫路遥 投稿）

Linus大神又在rant了！这次的吐槽对象是时下很火热的并行技术(parellism)，并直截了当地表示并行计算是浪费所有人时间(“The whole “let’s parallelize” thing is a huge waste of everybody’s time.”)。大致意思是说乱序性能快、提高缓存容量、降功耗。当然笔者不打算正面讨论并行的是是非非（过于宏伟的主题），因为Linus在另一则帖子中举了对象引用计数(reference counting)的例子来说明并行的复杂性。

在Linus回复之前有人指出对象需要锁机制的情况下，引用计数的原子性问题：

Since it is being accessed in a multi-threaded way, via multiple access paths, generally it needs its own mutex — otherwise, reference counting would not be required to be atomic and a lock of a higher-level object would suffice.

由于（对象）通过多线程方式及多种获取渠道，一般而言它需要自身维护一个互斥锁——否则引用计数就不要求是原子的，一个更高层次的对象锁足矣。

而Linus不那么认为：

The problem with reference counts is that you often need to take them *before* you take the lock that protects the object data.

引用计数的问题在于你经常需要在对象数据上锁保护之前完成它。

The thing is, you have two different cases:

问题有两种情况：

– object *reference* 对象引用

– object data 对象数据

and they have completely different locking.

它们锁机制是完全不一样的。

…

阅读全文 Read More

(42 人打了分，平均分： 3.83 )

State Threads 回调终结者

2014年10月12日 Leo 评论 50 条评论 54,767 人阅读

（感谢网友 @我的上铺叫路遥 投稿）

上回写了篇《一个“蝇量级”C语言协程库》，推荐了一下Protothreads，通过coroutine模拟了用户级别的multi-threading模型，虽然本身足够“轻”，杜绝了系统开销，但这个库本身应用场合主要是内存限制的嵌入式领域，提供原生态组件太少，使用限制太多，比如依赖其它调用产生阻塞等。

这回又替大家在开源界淘了个宝，推荐一个轻量级网络应用框架State Threads（以下简称ST），总共也就3000行C代码，跟Protothreads不同在于ST针对的就是高性能可扩展服务器领域（值得一提的是Protothreads官网参考链接上第一条就是ST的官网）。在其FAQ页面上一句引用”Perfection is achieved not when there is nothing more to add, but rather when there is nothing more to take away.”可以视为开发人员对ST源码质量的自信。

历史渊源

首先介绍一下这个库的历史渊源，从代码贡献者来看，ST不是个人作品，而是有着雄厚的商业支持和应用背景，比如服务器领域，在这里你可以看到ST曾作为Apache的多核应用模块发布。其诞生最初是由网景（Netscape）公司的MSPR（Netscape Portable Runtime library）项目中剥离出来，后由SGI（Silicon Graphic Inc）还有Yahoo!公司（前者是主力）开发维护的独立线程库。历史版本方面，作为SourceForge上开源项目，由2001年发布v1.0以来一直到2009年v1.9稳定版后未再变动。在平台移植方面，从Makefile的配置选项中可知ST支持多种Unix-like平台，还有专门针对Win32的源码改写。源码例子中，提供了web server、proxy以及dns三种编程实例供参考。可以说代码质量应该是相当的稳定和可靠的。

…

阅读全文 Read More

(31 人打了分，平均分： 4.00 )

一个“蝇量级” C 语言协程库

2014年01月28日 Leo 评论 54 条评论 108,940 人阅读

（感谢网友 @我的上铺叫路遥 投稿）

协程(coroutine)顾名思义就是“协作的例程”（co-operative routines）。跟具有操作系统概念的线程不一样，协程是在用户空间利用程序语言的语法语义就能实现逻辑上类似多任务的编程技巧。实际上协程的概念比线程还要早，按照 Knuth 的说法“子例程是协程的特例”，一个子例程就是一次子函数调用，那么实际上协程就是类函数一样的程序组件，你可以在一个线程里面轻松创建数十万个协程，就像数十万次函数调用一样。只不过子例程只有一个调用入口起始点，返回之后就结束了，而协程入口既可以是起始点，又可以从上一个返回点继续执行，也就是说协程之间可以通过 yield 方式转移执行权，对称（symmetric）、平级地调用对方，而不是像例程那样上下级调用关系。当然 Knuth 的“特例”指的是协程也可以模拟例程那样实现上下级调用关系，这就叫非对称协程（asymmetric coroutines）。

基于事件驱动模型

我们举一个例子来看看一种对称协程调用场景，大家最熟悉的“生产者-消费者”事件驱动模型，一个协程负责生产产品并将它们加入队列，另一个负责从队列中取出产品并使用它。为了提高效率，你想一次增加或删除多个产品。伪代码可以是这样的：

# producer coroutine
loop
while queue is not full
  create some new items
  add the items to queue
yield to consumer

# consumer coroutine
loop
while queue is not empty
  remove some items from queue
  use the items
yield to producer

…

阅读全文 Read More

(39 人打了分，平均分： 4.26 )

伙伴分配器的一个极简实现

2013年10月09日 Leo 评论 55 条评论 65,178 人阅读

（感谢网友 @我的上铺叫路遥 投稿）

提起buddy system相信很多人不会陌生，它是一种经典的内存分配算法，大名鼎鼎的Linux底层的内存管理用的就是它。这里不探讨内核这么复杂实现，而仅仅是将该算法抽象提取出来，同时给出一份及其简洁的源码实现，以便定制扩展。

伙伴分配的实质就是一种特殊的“分离适配”，即将内存按2的幂进行划分，相当于分离出若干个块大小一致的空闲链表，搜索该链表并给出同需求最佳匹配的大小。其优点是快速搜索合并（O(logN)时间复杂度）以及低外部碎片（最佳适配best-fit）；其缺点是内部碎片，因为按2的幂划分块，如果碰上66单位大小，那么必须划分128单位大小的块。但若需求本身就按2的幂分配，比如可以先分配若干个内存池，在其基础上进一步细分就很有吸引力了。

可以在维基百科上找到该算法的描述，大体如是：

分配内存：

1.寻找大小合适的内存块（大于等于所需大小并且最接近2的幂，比如需要27，实际分配32）

1.如果找到了，分配给应用程序。
2.如果没找到，分出合适的内存块。

1.对半分离出高于所需大小的空闲内存块
2.如果分到最低限度，分配这个大小。
3.回溯到步骤1（寻找合适大小的块）
4.重复该步骤直到一个合适的块

…

阅读全文 Read More

(29 人打了分，平均分： 3.79 )

7个示例科普CPU Cache

2013年07月30日 Leo 评论 73 条评论 106,786 人阅读

（感谢网友 @我的上铺叫路遥 翻译投稿）

CPU cache一直是理解计算机体系架构的重要知识点，也是并发编程设计中的技术难点，而且相关参考资料如同过江之鲫，浩瀚繁星，阅之如临深渊，味同嚼蜡，三言两语难以入门。正好网上有人推荐了微软大牛Igor Ostrovsky一篇博文《漫游处理器缓存效应》，文章不仅仅用7个最简单的源码示例就将CPU cache的原理娓娓道来，还附加图表量化分析做数学上的佐证，个人感觉这种案例教学的切入方式绝对是俺的菜，故而忍不住贸然译之，以飨列位看官。

原文地址：Gallery of Processor Cache Effects

大多数读者都知道cache是一种快速小型的内存，用以存储最近访问内存位置。这种描述合理而准确，但是更多地了解一些处理器缓存工作中的“烦人”细节对于理解程序运行性能有很大帮助。

在这篇博客中，我将运用代码示例来详解cache工作的方方面面，以及对现实世界中程序运行产生的影响。

下面的例子都是用C#写的，但语言的选择同程序运行状况以及得出的结论几乎没什么影响。

示例1：内存访问和运行

你认为相较于循环1，循环2会运行多快？

int[] arr = new int[64 * 1024 * 1024];

// Loop 1
for (int i = 0; i < arr.Length; i++) arr[i] *= 3;

// Loop 2
for (int i = 0; i < arr.Length; i += 16) arr[i] *= 3;

…

阅读全文 Read More

(53 人打了分，平均分： 3.96 )

C语言全局变量那些事儿

2013年07月21日 Leo 评论 92 条评论 77,443 人阅读

（感谢网友 @我的上铺叫路遥 投稿）

作为一名程序员，如果说沉迷一门编程语言算作一种乐趣的话，那么与此同时反过来去黑一门编程语言就是这种乐趣的升华。今天我们就来黑一把C语言，好好展示一下这门经典语言令人抓狂的一面。

我们知道，全局变量是C语言语法和语义中一个很重要的知识点，首先它的存在意义需要从三个不同角度去理解：对于程序员来说，它是一个记录内容的变量(variable)；对于编译/链接器来说，它是一个需要解析的符号(symbol)；对于计算机来说，它可能是具有地址的一块内存(memory)。其次是语法/语义：从作用域上看，带static关键字的全局变量范围只能限定在文件里，否则会外联到整个模块和项目中；从生存期来看，它是静态的，贯穿整个程序或模块运行期间（注意，正是跨单元访问和持续生存周期这两个特点使得全局变量往往成为一段受攻击代码的突破口，了解这一点十分重要）；从空间分配上看，定义且初始化的全局变量在编译时在数据段(.data)分配空间，定义但未初始化的全局变量暂存(tentative definition)在.bss段，编译时自动清零，而仅仅是声明的全局变量只能算个符号，寄存在编译器的符号表内，不会分配空间，直到链接或者运行时再重定向到相应的地址上。

我们将向您展现一下，非static限定全局变量在编译/链接以及程序运行时会发生哪些有趣的事情，顺便可以对C编译器/链接器的解析原理管中窥豹。以下示例对ANSI C和GNU C标准都有效，笔者的编译环境是Ubuntu下的GCC-4.4.3。

…

阅读全文 Read More

(29 人打了分，平均分： 3.86 )

Alan Cox：大教堂、市集与市议会

2013年07月08日 Leo 评论 20 条评论 24,080 人阅读

（感谢网友 @我的上铺叫路遥 投稿）

在网上搜到的Cox大叔于1998年在开源社区写的一篇文章，当时很轰动，明眼人一看就知道是针对ESR那篇《大教堂与市集》，从中可见Alan在项目管理风格上乃至个人性格上都与ESR、Linus等人不同之处。顺便说一句，Alan现在出于“家庭原因”已经离开了Linux项目，他曾经评价Linus是a good developer but a terrible engineer，甚至在Google+上直接说Linus就是一a*sh**e。不管如何，两位曾经十余年里并肩战斗惺惺相惜的大牛就此分道扬镳还是惹人唏嘘。

言归正传，以下为slashdot收录的英文原文：Cathedrals, Bazaars and the Town Council。

以下是一些我对市集模式的想法，我认为这值得分享，这种模式会教你如何完全毁掉一个自由软件项目。我还举了一个我称之为“市议会”(Town Council)效应的实例（虽然那些市议员们可不这么认为，注：此处指Linux项目开发者）。

关于软件开发人员，你必须去了解一些情况。首先要了解的是真正优秀的程序员相对来说并不普遍，不仅如此，在很多其它专业领域里“真正的程序员”和一些捣乱的家伙之间的区别要比“伟大”和“普通”之间的区别要大得多，研究表明生产效率上最好的同其余的比重是30:1。

其次，你需要了解的是一大堆妄想型码农(wannabe programmer)总是善于发表意见。其中很多人患上了一种叫做“流行性热词”(buzzword)疾病，或者对他们“非黑即白”(one true path)的思考方式有着特殊的偏执，网上很多讨论都是廉价的。

…

阅读全文 Read More

(21 人打了分，平均分： 3.62 )

Alan Cox：单向链表中prev指针的妙用

2013年06月30日 Leo 评论 56 条评论 38,156 人阅读

（感谢网友 @我的上铺叫路遥 投稿）

之前发过一篇二级指针操作单向链表的例子，显示了C语言指针的灵活性，这次再探讨一个指针操作链表的例子，而且是一种完全不同的用法。

这个例子是linux-1.2.13网络协议栈里的，关于链表遍历&数据拷贝的一处实现。源文件是/net/inet/dev.c，你可以从kernel.org官网上下载。

从最早的0.96c版本开始，linux网络部分一直采取TCP/IP协议族实现，这是最为广泛应用的网络协议，整个架构就是经典的OSI七层模型的描述，其中dev.c是属于链路层实现。从功能上看，其位于网络设备驱动程序和网络层协议实现模块之间，作为二者之间的数据包传输通道，一种接口模块而存在——对驱动层的接口函数netif_rx, 以及对网络层的接口函数net_bh。前者提供给驱动模块的中断例程调用，用于链路数据帧的封装；后者作为驱动中断例程底半部(buttom half)，用于对数据帧的解析处理并向上层传送。

为了便于理解，这里补充一下网络通信原理和linux驱动中断机制的背景知识。从最底层的物理层说起，当主机和路由器相互之间进行通信的时候，在物理介质上（同轴、光纤等）以电平信号进行传输。主机或路由器的硬件接口（网卡）负责收发这些信号，当信号发送到接口，再由内置的调制解调器(modem)将数字信号转换成二进制码，这样才能驻留在主机的硬件缓存中。这时接口（网卡）设备驱动程序将通过硬中断来获取硬件缓存中的数据，驱动程序是操作系统中负责直接同硬件设备打交道的模块，硬中断的触发是初始化时通过设置控制寄存器实现的，用于通知驱动程序硬件缓存中有新的数据到来。linux卡设备驱动就是在中断处理例程(ISR)中将硬件缓存数据拷贝到内核缓存中，打包成数据链路帧进行解析处理，再向上分发到各种协议层。由于ISR上下文是原子性的、中断屏蔽的，整个步骤又较为繁琐，因此全部放在ISR中处理会影响到其它中断响应实时性，于是linux有实现一种bottom half的软中断处理机制，将整个ISR一分为二，前半部上下文屏蔽所有中断，专门处理紧急的、实时性强的事务，如拷贝硬件缓存并打包封装，后半部上下文没有屏蔽中断（但代码不可重入），用于处理比较耗时且非紧急事务，包括数据帧的解析处理和分发。下面要讲的net_bh就属于后半部。

我们主要关心的是将链路帧分发到协议层那一段逻辑，下面摘自net_bh函数中的一段代码：

…

阅读全文 Read More

(36 人打了分，平均分： 4.11 )

Unix考古记：一个“遗失”的shell

2013年04月26日 Leo 评论 26 条评论 48,540 人阅读

(感谢网友Leo投递此文)

谨以此文纪念伟大的计算机科学巨匠Ken Thompson和Dennis Ritchie，并同时向其他所有为Unix发展做出贡献的黑客致敬。

历史的尘埃

Unix作为一个举世闻名的操作系统已有40余年的历史，围绕着这个古老的操作系统的发展又衍生出了一系列外围软件生态群，其中一个非常重要的组件就是shell。它是操作系统最外层的接口，负责直接面向用户交互并提供内核服务，包括命令行接口(CLI)或图形界面接口(GUI)两种形式。以CLI为例，它提供一套命令规范，是一种解释性语言，将用户输入经过解释器(interpreter)输出使其转化成真正的系统调用，实现人机交互的功能。

和操作系统一样，shell也经历了一个漫长的演变史。如今大部分资料讲述最古老的shell都是从1977年的Bourne Shell说起的，它最初移植到Unix V7上，被追认整个shell家族成员的鼻祖，后来的种群都是从其身上分支出来的。

Linux shells since 1977

对于1977年之前的历史很多资料大多一笔带过或略过不提。事实上，第一个移植到Unix上的shell却不是Steve Bourne写的，早在1975年5月，贝尔实验室就对外发布了第一个广泛传播的Unix版本——Unix V6（之前开发的版本只供内部研究之用），其根目录下的/bin/sh是第一个Unix自带的shell，由Ken Thompson写的，因此也被称为Thompson Shell。甚至，更早可以追溯到1971年的时候，Thompson Shell就作为一个独立于内核的应用程序而实现了，只不过从1975年正式问世到1977年被取代，短短两年的寿命使得它很少为大多数人所认识。

…

阅读全文 Read More

(39 人打了分，平均分： 4.15 )

酷壳 – CoolShell

享受编程和技术所带来的快乐 – Coding Your Ambition

Browsed by
作者： Leo

Cuckoo Filter：设计与实现

2015年09月02日 Leo 评论 37 条评论 68,814 人阅读

Linus：为何对象引用计数必须是原子的

2014年12月31日 Leo 评论 37 条评论 50,897 人阅读

State Threads 回调终结者

2014年10月12日 Leo 评论 50 条评论 54,767 人阅读

历史渊源

一个“蝇量级” C 语言协程库

2014年01月28日 Leo 评论 54 条评论 108,940 人阅读

基于事件驱动模型

伙伴分配器的一个极简实现

2013年10月09日 Leo 评论 55 条评论 65,178 人阅读

7个示例科普CPU Cache

2013年07月30日 Leo 评论 73 条评论 106,786 人阅读

示例1：内存访问和运行

C语言全局变量那些事儿

2013年07月21日 Leo 评论 92 条评论 77,443 人阅读

Alan Cox：大教堂、市集与市议会

2013年07月08日 Leo 评论 20 条评论 24,080 人阅读

Alan Cox：单向链表中prev指针的妙用

2013年06月30日 Leo 评论 56 条评论 38,156 人阅读

Unix考古记：一个“遗失”的shell

2013年04月26日 Leo 评论 26 条评论 48,540 人阅读

历史的尘埃