4 ms·

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

by 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
  Your bug doesn't seem to be related to the 'min' macro, but to the fact that your lock-free algorithm is not actually lock-free: if one thread can update an 'availableData' variable while another thread can read it, make a choice based on it, and then act on that choice, then that's not lock-free; that requires a lock to keep the read, decision, and action "atomic". I'm skeptical that using some other 'min' implementation is a real fix to the root of your problem, but without knowing more, I can only speculate.
  - mikeash 10y ago
    The algorithm is sound given a proper min() implementation. The reader just needs to read at most however much data is available at the moment or however much data the passed-in buffer can hold. If the available data increases during this operation, it's no problem, because the reader is allowed to read less than all of the data available. For some concrete numbers, if the ring holds 4 bytes, the caller passes in a 6-byte buffer, and a concurrent writer adds 4 more bytes, it's OK if the reader only returns 4 bytes. It would also be OK if the reader sees the new data and returns 6 bytes. It is not OK if the reader returns 8 bytes, which the incorrect min macro could cause. In this scenario, the incorrect min macro could return 4, 6, or 8, despite the fact that one of the parameters was a constant 6 and the result should never exceed 6. The correct min macro always returns 4 or 6.
    - jjnoakes 10y ago
      I see. So you are relying on single-reads of your shared variables. They must be suitably defined to be atomic on your architecture (so no word-tearing, out-of-order visibility), etc. I would think that if you had all the proper barriers in place to do the reads and writes atomically, though, that you would never have been able to use the min() macro in the first place. You would have had to do your barrier reads into local variables first, and then the min() macro on those local variables would have produced the right result. Unless I'm missing something. Like I said, it all depends on your implementation, but in general, this sure sounds like the min() macro wasn't at fault. Perhaps your specific scenario is much more constrained (single architecture, no barriers required, non-portable, etc).

by eloff 10y ago

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
Your bug doesn't seem to be related to the 'min' macro, but to the fact that your lock-free algorithm is not actually lock-free: if one thread can update an 'availableData' variable while another thread can read it, make a choice based on it, and then act on that choice, then that's not lock-free; that requires a lock to keep the read, decision, and action "atomic". I'm skeptical that using some other 'min' implementation is a real fix to the root of your problem, but without knowing more, I can only speculate.
- mikeash 10y ago
  The algorithm is sound given a proper min() implementation. The reader just needs to read at most however much data is available at the moment or however much data the passed-in buffer can hold. If the available data increases during this operation, it's no problem, because the reader is allowed to read less than all of the data available. For some concrete numbers, if the ring holds 4 bytes, the caller passes in a 6-byte buffer, and a concurrent writer adds 4 more bytes, it's OK if the reader only returns 4 bytes. It would also be OK if the reader sees the new data and returns 6 bytes. It is not OK if the reader returns 8 bytes, which the incorrect min macro could cause. In this scenario, the incorrect min macro could return 4, 6, or 8, despite the fact that one of the parameters was a constant 6 and the result should never exceed 6. The correct min macro always returns 4 or 6.
  - jjnoakes 10y ago
    I see. So you are relying on single-reads of your shared variables. They must be suitably defined to be atomic on your architecture (so no word-tearing, out-of-order visibility), etc. I would think that if you had all the proper barriers in place to do the reads and writes atomically, though, that you would never have been able to use the min() macro in the first place. You would have had to do your barrier reads into local variables first, and then the min() macro on those local variables would have produced the right result. Unless I'm missing something. Like I said, it all depends on your implementation, but in general, this sure sounds like the min() macro wasn't at fault. Perhaps your specific scenario is much more constrained (single architecture, no barriers required, non-portable, etc).