程序员调代码访谈:Russ Cox

『程序员调代码访谈』是 Karim Hamidou 发起的一个程序员访谈系列,受访者分享他们遇到的最难/最有意思的Bug,以及如何解决。

本文的受访者是 Russ Cox,写过内核代码、网络服务器、文件系统和一点图形代码。他目前是GO语言的主要开发者之一。


你是谁?

我是一个程序员。

我写程序。我在贝尔实验室的“Plan 9”上大约工作了十年,写过内核代码、网络服务器、文件系统和一点图形代码。现在,我在谷歌工作,在那里我是GO语言的主要开发者之一。Go语言已经被证明是一个很好的通用语言,但其最初的设计目标是并发网络服务器,这种类型的程序我们曾为Plan 9和谷歌写过。

我也写与程序相关的东西。我最知名的文章是关于实现正则表达式,把一个zip文件放入自身里面,和在二维码中制造图片。我使用Go语言来实现上面这三个。

你见过的最有趣的bug是什么?

对我而言,最有趣的bug是那些能揭示程序工作方式根本而微妙地方的误解。一个好的bug就像一个好的科学实验:通过它,你会学到一些关于你正在探索的虚拟世界的意想不到的东西。

大约十年前,我工作使用联网的服务器,它使用线程来协调锁和条件变量。这个服务器是Plan 9的一部分,是用C语言写的。内部的malloc偶尔会崩溃,这通常意味着因为写后释放(write-after-free)错误引起的某种内存损坏。有一天,当大部分服务器的基准被禁用,我很幸运能有这样的崩溃重复发生。服务器大多数被禁用给了我在隔离bug方面有一个良好的开端。同时,重复性有可能使代码被一块块地削减,直到有一部分有非常清晰的关联。

在客户端最近断开之后,有问题的代码被清理。在服务器中,由两个线程共享每个客户端的数据结构:线程R从客户端连接中进行读取,线程W向其中写数据。线程R注意到断开在读取的信息中是EOF标识,它通知线程W,等待与线程W的确认,然后再释放每个客户端的数据结构。

要确认断开连接,线程W运行了如下代码:

同时,为了等待确认,线程R运行了如下代码:

这是一个标准的锁和条件变量的代码片段:qwait被定义为解除锁(here, conn->lk),等待,然后在返回前重新获得锁。线程R一旦观测到writer_done被设置,它就知道线程W已经结束,因此线程R就能释放每个连接的数据结构。

线程R不调用qunlock(&conn->lk)。我的理由是,在释放前调用qunlock会发送混乱的信息:qunlock建议协同另一个线程来使用conn,但只有在没有其他线程使用conn时,释放才是安全的。线程W是其他线程,它已经结束了。但为什么当我在free(conn)前加入qunlock(&conn->lk)时崩溃停止。为什么会这样呢?

要回答这个问题,我们必须来看看锁是如何实现的。

从概念上讲,一个锁的核心是具有解锁和锁定两个标记的变量。要获得一个锁,在一个原子操作中,一个线程检查其变量是否被标记为未锁定,如果是这样,则将其标记为锁定。因为是原子操作,如果两个(或更多)线程来试图获得这个锁,只有一个能成功。这线程(姑且称为线程A)现在持有了这个锁。争夺该锁的另一个线程(线程B)看到变量被标记为锁定,现在必须决定该怎么做。

首先,最简单的办法就是再不断的一次次尝试。最终,线程A将解除锁定(通过将变量标记为未锁定),此时线程B的原子操作会成功。这种方法被称为自旋(spinning)。同时,使用这种方法的锁被称为自旋锁

一个简单的自旋锁的实现是这样的:

自旋锁的核心是位字段,它通过0和1两个值来指示解锁和锁定。atomic_cmp_and_setatomic_set使用特殊的机器指令来对lk->bit进行原子操作。

如果锁从未保持很长时间,自旋才有意义。因此线程B的自旋循环只执行少数几次。如果锁能保持更长的时间,自旋会持续浪费CPU并与操作系统调度进行糟糕地交互。

其次,更普遍的方法是维持一个想要获得锁的线程队列。在这种方法中,当线程B发现锁已经在被持有状态时,它将自身增加到队列中,并使用操作系统原语来休眠。当线程A最终释放锁时,它检查队列,发现线程B,并且使用一个操作系统原语来唤醒线程B。这种方法被称为队列,使用这种方法的锁被称为队列锁。当锁能保持很长一段时间时,队列比自旋更有效。

队列锁的队列需要自己的锁,这几乎总是一个自旋锁。在我使用的库中,qlockqunlock的实现如下:

队列锁的核心是owner字段。如果owner的值为nil ,锁被解锁;否则owner会记录持有锁的线程。通过持有自旋锁lk->spinlk->owner被执行为原子操作。

回到之前提到的bug。

崩溃代码中的锁就是队列锁。线程R和线程W之间的确认协议在线程W调用qunlock和线程R调用qlock之间设置了一场竞争(无论是在代码中显示调用还是在qwait内部隐式调用)。其中哪个调用会先发生呢?

如果首先发生的线程W调用qunlock,那么线程R调用qlock发现锁未被锁定,则锁定它。这样一切都进行得没有问题。

如果首先发生的是线程R调用qlock,它发现线程W持有锁,因此它将现线程R添加到队列中,并让线程R休眠。然后线程W执行调用qunlock。它将owner设为线程R,唤醒线程R,并将自旋锁解锁。当线程W解锁自旋锁时,线程R可能已经开始运行,线程R可能已经调用了free(conn)spinunlockatomic_set指令将conn->lk.spin.bit写为零。这就是写后释放,且如果存储分配器不想这里有零,这个零就会导致崩溃(或内存泄露,或一些其他的行为)。

但是,这是服务器的代码错误还是qunlock错误?

此处的根本误解在队列锁API的定义中。队列锁需要在释放前被解锁?或者队列锁需要在锁定时支持被释放?我写过队列锁的程序,将它作为一个跨平台的库模拟Plan 9的一部分。当时我写qunlock时,我还没有遇到这个问题。

  • 如果队列锁必须在未锁定时才能释放,那么qunlock的实现是正确的,服务器的代码必须改变。如果线程R在释放前调用qunlock,那么线程R调用qunlock中的spinlock必须等待线程W调用qunlock中的spinunlock执行。因此,随着线程R的调用释放,线程W将真的会结束。
  • 如果队列锁能在锁定时被释放,那么服务器的代码是正确的,qunlock必须改变:os_wakeup放弃对lk的控制,且必须延迟到执行spinunlock后。

Plan 9文档中队列锁的部分没有直接解决这个问题,但这种释放锁定的队列锁的实现是没有害处的。因为我曾经使用我的库来运行修改Plan 9软件,我改变了锁的实现,在执行spinunlock后调用os_wakeup。两年后,当修复一个不同的bug时,我改变了服务器的实现来以防万一地调用qunlock。POSIX(Portable Operating System Interface)标准定义的pthread_mutex_destroy函数对于相同的设计问题给出了不同的答案:“销毁一个未锁定的初始化互斥量是安全的。试图销毁一个锁定的互斥量会导致不确定的行为。”

我们学到了什么?

对于在释放前不调用qunlock,我给出的理由做出了一个隐含的假设,那两者是独立的。在看过内部的实现后,我们可以知道为什么这两者相互关联,以及为什么API可以指定你必须在销毁它前解除锁定,正如POSIX所做的。创建一个“抽象泄露“,这是涉及影响API实现的一个示例。

让这个bug有趣的地方是,它是由手动内存管理和并发性之间的复杂交互所引起的。显然,一个程序必须在释放前停止使用资源。但一个并发程序必须在释放前停止所有线程使用资源。在很好的一天,这可能需要记录或多方协调来跟踪哪个线程仍在使用资源。在糟糕的一天,这可能需要读取锁的实现来了解在不同线程间进行操作的确切顺序。

在现代计算机的客户端、服务器和云中,并发是大多数程序的一个基本问题。在那个世界中,选择垃圾收集而不是手动内存管理来消除泄露抽象的来源,使程序更简单、更容易解释。

其他补充的内容?

在文章的开始,我提到好的bug帮助你学到一些关于你正在探索的虚拟世界的意想不到的东西。这对Maurice Wilkes和他的团队更是如此,他创造了第一个实用的存储程序的计算机EDSAC。他们在EDSAC上运行的第一个程序(打印平方数)运行正确,但第二个没有:1949年5月7日的日志上写着“素数表尝试程序不正确”。那是一个星期六,这使得它成为第一个工作在一个错误程序上的周末。

他们学到了什么?Wilkes后来回忆说,

“By June 1949, people had begun to realize that it was not so easy to get a program right as had at one time appeared. … It was on one of my journeys between the EDSAC room and the punching equipment that the realization came over me with full force that a good part of the remainder of my life was going to be spent in finding errors in my own programs.” (Wilkes, p. 145)

“到1949年6月,人们才开始意识到,让程序每次都运行正确不是那么容易。……在EDSAC和打孔设备间检查,让我突然意识到我余生的大部分时间都要花在寻找我程序中的错误。“(Wilkes,第145页)

想要了解更多有关这早期的历史,请看Brian Hayes的“The Discovery of Debugging”和Martin Campbell-Kelly的“The Airy Tape: An Early Chapter in the History of Debugging.”

收藏 1 评论

关于作者:Janzou

做一直倦懒的小猫咪,享受午后阳光(新浪微博:@Jan_zou) 个人主页 · 我的文章 · 13

相关文章

可能感兴趣的话题



直接登录
最新评论
  • “写后释放(write-after-free)错误”

    应该是释放后写吧!指的是释放指针指向的内存后又在那里进行数据的写入。

跳到底部
返回顶部