6 ms·

Lock-Free Bugs

112 points by stablemap 10y ago

RossBencina 10y ago
Interesting read. It's about a lock;free bug (freeing a mutex while it is locked) in code using a custom mutex implementation.
fantasticsid 10y ago
I really enjoyed reading it! System programming is hard :)
beagle3 10y ago
mods (and russ..): perhaps better to change title to "lock;free" or "lock+free" bugs (or something else entirely), T he current title "Lock-Free Bugs" is confusing since the article has nothing to do with lock freedom.
- cespare 10y ago
  I read it as an intentional play on words.
- alfalfasprout 10y ago
  Agreed. If we're actually talking about "lockfree" bugs, it's amazing how easy they are to come by. The sometimes funky data structures and algorithms required to make things lockfree can lead to some perplexing situations.
davidtgoldblatt 10y ago
Here's a fun related issue: A common Linux mutex-implementation strategy to deal with this issue (waker-waiter races) is by releasing a mutex before futex-waking any threads blocked on it. Since the waker doesn't know for sure if a waiter is present at the time of waking, the locking thread may fail its futex-wait attempt, acquire the mutex, and destroy it, freeing the mutex's memory back to the allocator. In the end the waker issues a wakeup call to an address no longer occupied by a mutex. As a result, the mutex implementation might spray futex-wake calls into arbitrary addresses not owned by the implementation. This means that other libraries in the same process can't rely on accurate wakeups, even if it would otherwise be algorithmically correct to do so (unless it has some way of guaranteeing that its synchronization locations never share an address with other libraries). If you've ever wondered why pthreads-style condition variables allow spurious wakeups, this is one reasonable situation in which they can occur.
valarauca1 10y ago
“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 That cuts deep
eloff 10y ago
This is not a lock free bug. But it does illustrate how hard it is to get thread synchronization correct. The only bug that ever beat me was a lock free bug in a concurrent skip list. I spent two months of evenings and weekends trying to find it. I wrote special logging tools and visualization tools to try and gain insight. The bug would happen roughly once every hundred billion operations. In the end I decided it is easier to change the entire algorithm than to fix the bug.
- digler999 10y ago
  something like that could be a hardware malfunction. Did you try it on different machines ? On my workstation at home, there's a fault either in the CPU or RAM, that I only discovered when trying to make large backup archives. I made 40gb archives and ran md5sum to confirm integrity and occasionally the sum would differ between 2 consecutive operations. So either the ram or CPU/chipset has a bug during heavy IO operations. But I never fixed it because 99% of the time I never notice it.
- mikeash 10y ago
  It's not a lock-free bug, but it is a lock, free bug. My favorite lock-free bug involved a concurrent ring buffer. At one point the code had to figure out how much data to read, which was either the size of the buffer passed in, or the amount of data available in the ring buffer, whichever was smaller. So the code did something like: toRead = min(requestSize, availableData) But, surprise! The min macro was a custom job using the typical bad implementation of: #define min(a, b) ((a) < (b) ? (a) : (b)) But this is no problem as long as the two expressions have no side effects, right? Wrong! Every so often, another thread would write to the ring buffer between evaluating a<b and evaluating a or b the second time. And every so often, this would happen when availableData was smaller than the request size, but then became larger after writing the additional data. In those rare circumstances, the read function would use that too-large availableData as the amount of data to copy, and write past the end of the passed-in buffer. Hilarity then ensued. I deleted the custom min macro and used the (properly implemented) system-provided one, and all was well.
  - jjnoakes 10y ago

112 points by stablemap 10y ago

Interesting read. It's about a lock;free bug (freeing a mutex while it is locked) in code using a custom mutex implementation.

fantasticsid 10y ago

I really enjoyed reading it! System programming is hard :)

beagle3 10y ago

mods (and russ..): perhaps better to change title to "lock;free" or "lock+free" bugs (or something else entirely), T he current title "Lock-Free Bugs" is confusing since the article has nothing to do with lock freedom.

cespare 10y ago
I read it as an intentional play on words.
alfalfasprout 10y ago
Agreed. If we're actually talking about "lockfree" bugs, it's amazing how easy they are to come by. The sometimes funky data structures and algorithms required to make things lockfree can lead to some perplexing situations.

davidtgoldblatt 10y ago

Here's a fun related issue: A common Linux mutex-implementation strategy to deal with this issue (waker-waiter races) is by releasing a mutex before futex-waking any threads blocked on it. Since the waker doesn't know for sure if a waiter is present at the time of waking, the locking thread may fail its futex-wait attempt, acquire the mutex, and destroy it, freeing the mutex's memory back to the allocator. In the end the waker issues a wakeup call to an address no longer occupied by a mutex. As a result, the mutex implementation might spray futex-wake calls into arbitrary addresses not owned by the implementation. This means that other libraries in the same process can't rely on accurate wakeups, even if it would otherwise be algorithmically correct to do so (unless it has some way of guaranteeing that its synchronization locations never share an address with other libraries). If you've ever wondered why pthreads-style condition variables allow spurious wakeups, this is one reasonable situation in which they can occur.

valarauca1 10y ago

“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 That cuts deep

eloff 10y ago

This is not a lock free bug. But it does illustrate how hard it is to get thread synchronization correct. The only bug that ever beat me was a lock free bug in a concurrent skip list. I spent two months of evenings and weekends trying to find it. I wrote special logging tools and visualization tools to try and gain insight. The bug would happen roughly once every hundred billion operations. In the end I decided it is easier to change the entire algorithm than to fix the bug.

digler999 10y ago
something like that could be a hardware malfunction. Did you try it on different machines ? On my workstation at home, there's a fault either in the CPU or RAM, that I only discovered when trying to make large backup archives. I made 40gb archives and ran md5sum to confirm integrity and occasionally the sum would differ between 2 consecutive operations. So either the ram or CPU/chipset has a bug during heavy IO operations. But I never fixed it because 99% of the time I never notice it.
mikeash 10y ago
It's not a lock-free bug, but it is a lock, free bug. My favorite lock-free bug involved a concurrent ring buffer. At one point the code had to figure out how much data to read, which was either the size of the buffer passed in, or the amount of data available in the ring buffer, whichever was smaller. So the code did something like: toRead = min(requestSize, availableData) But, surprise! The min macro was a custom job using the typical bad implementation of: #define min(a, b) ((a) < (b) ? (a) : (b)) But this is no problem as long as the two expressions have no side effects, right? Wrong! Every so often, another thread would write to the ring buffer between evaluating a<b and evaluating a or b the second time. And every so often, this would happen when availableData was smaller than the request size, but then became larger after writing the additional data. In those rare circumstances, the read function would use that too-large availableData as the amount of data to copy, and write past the end of the passed-in buffer. Hilarity then ensued. I deleted the custom min macro and used the (properly implemented) system-provided one, and all was well.
- jjnoakes 10y ago