I spent nearly 3 days hunting for a bug in a queue data structure we are using in LVM. The queue is used to store a worklist of references to be marked during garbage collection. An LVM object reference (object_reference_t) is a 64-bit unsigned integer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class TCircularArray{
    private:
 
    // Backing array.
    object_reference_t* array;
    // Size of the array.
    u_int32_t array_size;
 
    // Index of first used spot in the queue.
    u_int32_t start;
    // Index of first free spot in the queue.
    u_int32_t end;
 
    // ...snip...
 
    public:
 
    // Constructor.
    TCircularArray(u_int32_t start_size);
 
    // ...snip...
 
    /** Adds an item to the end of the queue. */
    void Append(object_reference_t a);
    /** Removes the item at the front of the queue. */
    object_reference_t GetAndRemove();
};

The queue is implemented as an expandable circular array—it has a backing array, a start index and an end index, and the backing array grows as needed. The value 0 is used to signify an unused spot in the queue. Pretty simple.

Here is the implementation of the interesting functions, sanitized for comprehension:

26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

// We allocate enough space for the requested size
// using calloc, which zeroes the memory it provides.
TCircularArray::TCircularArray(u_int32_t start_size){
    array_size = start_size;
    array = (object_reference_t*) calloc(array_size,
        sizeof(object_reference_t));
    assert(array);  // Make sure we actually got memory.
    start = end = 0;
}
 
void TCircularArray::Append(object_reference_t a){
    // The queue should never be completely full---we grow
    // when needed to preserve this invariant.
    assert(array[end] == 0);
    // Make sure we're not inserting the sentinel value by
    // mistake.
    assert(a != 0);
 
    // ...snip code to enlarge the array if needed...
 
    // Insert to end of queue and increment end index.
    array[end] = a;
    end = (end + 1) % array_size;
 
    // Again, shouldn't ever be completely full.
    assert(array[end] == 0);
}
 
object_reference_t TCircularArray::GetAndRemove(){
    // Return sentinel if empty.
    if (is_empty()) return 0L;
 
    object_reference_t current = array[start];
    // Empty the front of the queue.
    array[start] = 0L;
    // Increment the start index.
    start = (start + 1) % array_size;
 
    return current;
}

Upon construction, the backing array is allocated using calloc. So, the backing array should be initialized to all 0s—our sentinel value—the queue starts empty. Append adds an item to the queue, which stores the item in the backing array at the end index, then increments the end index. GetAndRemove sets the array at the start index to 0, increments the start index, and returns the item at was at the old start index. Again, pretty simple.

When running JCheck, a model checker we are using for benchmarks, I sometimes saw the assertion at the end of Append fail: the index to the end of the queue pointed to a non-empty spot in the array. Sometimes the entire array was non-empty. Not good.

This assertion failure was seemingly nondeterministic. Sometimes the program ran for a few minutes before aborting, and other times it happened right away, with the exact same input. I saw this behavior only on machines in our older cluster. “Data race!” was my first thought—LVM is heavily multithreaded. Improper synchronization is often the cause of nondeterminism in programs.

I looked very closely at the thread synchronization code, added many asserts, and found a few other bugs, but nothing that would explain the nondeterminism. It looks like a bug in calloc—it is supposed to return memory that has been zeroed, but sometimes on those certain machines, this wasn’t happening.

I switched to a normal malloc + memset, and have not seen any assertion failures from TCircularArray since. I searched briefly for other people experiencing calloc bugs, but only found out that many implementations of calloc do some complex things with the MMU (when I told Ronald about my suspected calloc bug, he said very seriously, “calloc does magic. Don’t you like magic?”). Very tricky. I’ve so far been unable to reproduce this suspected calloc bug outside of LVM.

The moral of this story: don’t trust the OS facilities to actually do what they say they do.