JanZou analyst, programmer

程序员调代码访谈：Russ Cox

12 Jan 2015 Translation

本文由@Jan_zou翻译，原文出处：debuggers.co

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

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

Russ cox

你是谁？

我是一个程序员。

我写程序。我在贝尔实验室的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运行了如下代码：

qlock(&conn->lk);
conn->writer_done = 1;
qsignal(&conn->writer_ack);
qunlock(&conn->lk);
thread_exit();

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

qlock(&conn->lk);
while(!conn->writer_done)
    qwait(&conn->writer_ack);

// The writer is done, and so are we:
// free the connection.
free(conn);

这是一个标准的锁和条件变量的代码片段：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）。同时，使用这种方法的锁被称为自旋锁。

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

struct SpinLock
{
    int bit;
};

void
spinlock(SpinLock *lk)
{
    for(;;) {
        if(atomic_cmp_and_set(&lk->bit, 0, 1))
            return;
    }
}

void
spinunlock(SpinLock *lk)
{
    atomic_set(&lk->bit, 0);
}

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

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

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

队列锁的队列需要自己的锁，这几乎总是一个自旋锁。在我使用的库中，qlock和qunlock 的实现如下：

struct QLock
{
    SpinLock spin;
    Thread *owner;
    ThreadQueue queue;
};

void
qlock(QLock *lk)
{
    spinlock(&lk->spin);
    if(lk->owner == nil) {
        lk->owner = current_thread();
        spinunlock(&lk->spin);
        return;
    }
    push(&lk->queue, current_thread());
    spinunlock(&lk->spin);
    os_sleep();
}

void
qunlock(QLock *lk)
{
    Thread *t;

    spinlock(&lk->spin);
    t = pop(&lk->queue);
    lk->owner = t;
    if(t != nil)
        os_wakeup(t);
    spinunlock(&lk->spin);
}

队列锁的核心是owner字段。如果owner的值为nil ，锁被解锁；否则owner会记录持有锁的线程。通过持有自旋锁lk->spin，lk->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)。spinunlock的atomic_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后来回忆说，

“到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”

Related Posts