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

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

Alan Cox
Alan Cox

(感谢网友 @我的上铺叫路遥 投稿)

之前发过一篇二级指针操作单向链表的例子,显示了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 )
Loading...
Javascript 装载和执行

Javascript 装载和执行

一两个月前在淘宝内网里看到一个优化Javascript代码的竞赛,发现有不少的人对Javascript的执行和装载的基础并不懂,所以,从那天起我就想写一篇文章,但一直耽搁了。自上篇《浏览器渲染原理简介》,正好也可以承前启后。

首先,我想说一下Javascript的装载和执行。通常来说,浏览器对于Javascript的运行有两大特性:1)载入后马上执行,2)执行时会阻塞页面后续的内容(包括页面的渲染、其它资源的下载)。于是,如果有多个js文件被引入,那么对于浏览器来说,这些js文件被被串行地载入,并依次执行。

因为javascript可能会来操作HTML文档的DOM树,所以,浏览器一般都不会像并行下载css文件并行下载js文件,因为这是js文件的特殊性造成的。所以,如果你的javascript想操作后面的DOM元素,基本上来说,浏览器都会报错说对象找不到。因为Javascript执行时,后面的HTML被阻塞住了,DOM树时还没有后面的DOM结点。所以程序也就报错了。

传统的方式

所以,当你写在代码中写下如下的代码:

<script type="text/javascript"
        src="https://coolshell.cn/asyncjs/alert.js"></script>

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (64 人打了分,平均分: 4.31 )
Loading...
无锁HashMap的原理与实现

无锁HashMap的原理与实现

 (本文由投稿)

在《疫苗:Java HashMap的死循环》中,我们看到,java.util.HashMap并不能直接应用于多线程环境。对于多线程环境中应用HashMap,主要有以下几种选择:

  1. 使用线程安全的java.util.Hashtable作为替代。
  2. 使用java.util.Collections.synchronizedMap方法,将已有的HashMap对象包装为线程安全的。
  3. 使用java.util.concurrent.ConcurrentHashMap类作为替代,它具有非常好的性能。

而以上几种方法在实现的具体细节上,都或多或少地用到了互斥锁。互斥锁会造成线程阻塞,降低运行效率,并有可能产生死锁、优先级翻转等一系列问题。

CAS(Compare And Swap)是一种底层硬件提供的功能,它可以将判断并更改一个值的操作原子化。关于CAS的一些应用,《无锁队列的实现》一文中有很详细的介绍。

Java中的原子操作

在java.util.concurrent.atomic包中,Java为我们提供了很多方便的原子类型,它们底层完全基于CAS操作。

例如我们希望实现一个全局公用的计数器,那么可以:

 

private AtomicInteger counter = new AtomicInteger(3);

public void addCounter() {
    for (;;) {
        int oldValue = counter.get();
        int newValue = oldValue + 1;
        if (counter.compareAndSet(oldValue, newValue))
            return;
    }
}

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (30 人打了分,平均分: 3.40 )
Loading...
浏览器的渲染原理简介

浏览器的渲染原理简介

看到这个标题大家一定会想到这篇神文《How Browsers Work》,这篇文章把浏览器的很多细节讲得很细,而且也被翻译成了中文。为什么我还想写一篇呢?因为两个原因,

1)这篇文章太长了,阅读成本太大,不能一口气读完。

2)花了大力气读了这篇文章后可以了解很多,但似乎对工作没什么帮助。

所以,我准备写下这篇文章来解决上述两个问题。希望你能在上班途中,或是坐马桶时就能读完,并能从中学会一些能用在工作上的东西。

浏览器工作大流程

废话少说,先来看个图:

从上面这个图中,我们可以看到那么几个事:

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (70 人打了分,平均分: 4.39 )
Loading...
疫苗:Java HashMap的死循环

疫苗:Java HashMap的死循环

在淘宝内网里看到同事发了贴说了一个CPU被100%的线上故障,并且这个事发生了很多次,原因是在Java语言在并发情况下使用HashMap造成Race Condition,从而导致死循环。这个事情我4、5年前也经历过,本来觉得没什么好写的,因为Java的HashMap是非线程安全的,所以在并发下必然出现问题。但是,我发现近几年,很多人都经历过这个事(在网上查“HashMap Infinite Loop”可以看到很多人都在说这个事)所以,觉得这个是个普遍问题,需要写篇疫苗文章说一下这个事,并且给大家看看一个完美的“Race Condition”是怎么形成的。

问题的症状

从前我们的Java代码因为一些原因使用了HashMap这个东西,但是当时的程序是单线程的,一切都没有问题。后来,我们的程序性能有问题,所以需要变成多线程的,于是,变成多线程后到了线上,发现程序经常占了100%的CPU,查看堆栈,你会发现程序都Hang在了HashMap.get()这个方法上了,重启程序后问题消失。但是过段时间又会来。而且,这个问题在测试环境里可能很难重现。

我们简单的看一下我们自己的代码,我们就知道HashMap被多个线程操作。而Java的文档说HashMap是非线程安全的,应该用ConcurrentHashMap。

但是在这里我们可以来研究一下原因。

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (184 人打了分,平均分: 4.66 )
Loading...
“C++的数组不支持多态”?

“C++的数组不支持多态”?

先是在微博上看到了个微博和云风的评论,然后我回了“楼主对C的内存管理不了解”。

后来引发了很多人的讨论,大量的人又借机来黑C++,比如:

//@Baidu-ThursdayWang:这不就c++弱爆了的地方吗,需要记忆太多东西

//@编程浪子张发财:这个跟C关系真不大。不过我得验证一下,感觉真的不应该是这样的。如果基类的析构这种情况不能 调用,就太弱了。

//@程序元:现在看来,当初由于毅力不够而没有深入纠缠c++语言特性的各种犄角旮旯的坑爹细枝末节,实是幸事。为现在还沉浸于这些诡异特性并乐此不疲的同志们感到忧伤。

然后,也出现了一些乱七八糟的理解:

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (52 人打了分,平均分: 4.25 )
Loading...
Unix考古记:一个“遗失”的shell

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

(感谢网友Leo投递此文)

谨以此文纪念伟大的计算机科学巨匠Ken ThompsonDennis 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 )
Loading...
PFIF网上寻人协议

PFIF网上寻人协议

本文的主要内容来自Wikipedia(http://en.wikipedia.org/wiki/People_Finder_Interchange_Format)

PFIF全称People Finder Interchange Format,是一个应用广泛的数据开源的标准协议,这个协议主要是设计用来在不同的政府、救援组织、或是其它的一些灾难中生存者和其亲人联系的网站间进行数据交换的一种协议。

这个协议基于XML,信息中包括人的身份标识,还有人目前的位置和状态等一些信息。PFIF可以通过Atom和RSS feed出去。PFIF可以允许不同的寻人站点进行数据交换和合并。每一条记录都有一个唯一的标识,这个标识说明了这是由哪个域名创建的。这样,当A站点获得B点的某个人的数据时,在A站点可以对这个人的增加的信息可以转到其它站点上再被增加相关的信息,因为有一个唯一的ID,所以信息可以在不同的站点上被附加。

从wikipedia上看,说起PFIF这个事,得回到2001年的911事件,那时人们一共使用了超过25个不同的在线论坛和网上寻人站来查找相关的亲人和朋友(注:寻人网站英文叫:Survivor Registry,生还者登记网站)。其中一个最大的网站是由伯克利大学的学生Ka-Ping Yee 和 Miriam Walker 开发运行在Millennium计算集群上的safe.millennium.berkeley.edu网站。那时,为了减少各种网站间的混乱,伯克利的寻人网站开始从其它几个比较大的寻人站点收集相关的数据,并人肉整合到一起。

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (31 人打了分,平均分: 3.97 )
Loading...
“作环保的程序员,从不用百度开始”

“作环保的程序员,从不用百度开始”

酷壳对来自百度搜索引擎的访问会弹窗,但是我的这个行为发酵出了一些事情,这里把这个事情说明如下,我会更新相关的东西。内行看门道,外行看热闹。

事由

2月6日 看到梁斌同学的微博(起因可能是因为梁斌同学在微博上对帮助百度的一些工程师们说话导致他的“微博寻人”全站被百度屏蔽)

我看到后,觉得梁斌同学有点太看重被百度收录了,没有站长应该有的气质,所以,我回了一个微博——

“我的酷壳倒反而因为被百度收录而感到掉价!”

2月6日当天,我给coolshell做了个弹窗,并发布微博—— (该微博目前已被新浪管理员删除,后面有说明)

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (623 人打了分,平均分: 4.86 )
Loading...
《Rework》摘录及感想

《Rework》摘录及感想

读了《Rework》这本书好多遍,每次读都有不同的感想。但从来没有把这些感想记录下来,今天把《Rework》书中的一些章节做一些摘录,并把我的一些感想总结出来。供大家参考。这是一本平生以来让我中毒很深的书,也是一本让我思考得很多的书。希望看到这篇文章的人都能好好地读读这本书。这本书并不难读,是一本你可以一口气不中断就可以读完的书。

现实世界

“这在现实世界里面行不通”,当你向人们介绍一个新创意时,人们总是这么回答你。这个“现实世界”听起来如此令人沮丧,……只有人耳熟能详,习以为常的事情才会胜利,即使是这些事情已经漏洞百出陈腐低效。

揭开“现实世界”这个锅盖,你会发现居住在里的人都充斥着悲观主义和失望的情绪。更糟的是,他们想将别人拖进他们的坟墓。如果你是充满希望和野心的人,他们会试着说服你,你的想法是不可能的。他们会说你在浪费时间。

“现实世界”并不存在,那只是人的一个借口。只是某些人为了开脱 自己的无所作为,跟你一点关系也没有。

感想:我经常会向一同事和朋友提及一些我的想法,朋友同事们经常会回答我——这个事某某人,某某团队做过了,没成功。或是对我说,你做这个事的时候,要小心这个要小心那个。我觉得,这个时候是最考验我们的时候了,要有一个清醒的头脑去分析别人的话,别人真不代表自己。这个世界上大多数人都是比较保守的,大多数都对这个现实世界都有或多或少的恐惧感。当然,你可以选择做大众,但是如果你想让你的人生有些不同,有些精彩,我还是建议你不要和大多数人想得一样,如果你和大多数人的想法一样,你必然会和大多数人一样的平庸。当然,如果你和大多数人不一样,你要么就是天才,要么就是傻瓜。要证明你自己是不是傻瓜,我们可以看看我们过去有没有过一些小成功或小成绩。如果有,那么就应该大胆地坚持自己的想法。

被高估的“从错误中学习”

你真的从错误和失败里面学到什么了吗?你也许学到了别再重蹈覆辙,但是这有什么意义吗?你仍然不知道接下来该做什么。

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (94 人打了分,平均分: 4.59 )
Loading...