5 ms·

Can someone explain the problem and fix in plain English

delecti 3y ago
There was a rare race condition [1] bug in the linux kernel, and they didn't know precisely where it was introduced (which made it difficult to know what to change to fix it). They knew it was introduced at some point between two versions, but there were 52,363 code changes between those two versions. Because the bug was rare, you would have to test any given code change multiple times (thousands of times, in their case) to be confident that the bug was still present (if working backwards), or still absent (if working forwards). A way to do that faster is a binary search [2], or commit bisection. Basically, you know commit 0 is fine, and change 52,363 is bad, so you run 1000 tests on change 26,180 to cut in half the number of commits that could have introduced the problem. If the bug is still there, then you run 1000 tests on change 13,090; if the bug is not in change 26,180, then you run 1000 tests on change 39,270. Eventually (after 15 or 16 iterations) you'll narrow down the problem to a single change which introduced the problem. Unfortunately code is complicated, so the first time they ran that procedure, their tests didn't find the right bug, so they did it again but slightly differently. (many details omitted for simplicity) [1] https://en.wikipedia.org/wiki/Race_condition https://en.wikipedia.org/wiki/Race_condition [2] https://en.wikipedia.org/wiki/Binary_search_algorithm https://en.wikipedia.org/wiki/Binary_search_algorithm?
- sh34r 3y ago
  It's worth mentioning that this generalized problem in user space can often be solved much more easily using concurrent fuzz testing (ex: https://www.microsoft.com/en-us/research/project/cuzz-concurrency-fuzzing/ https://www.microsoft.com/en-us/research/project/cuzz-concur...). Unfortunately, when the problem is in kernel boot software, that is not a practical solution for obvious reasons, and you're left using more basic techniques like running a binary search on the commit history.
- ufo 3y ago
  Furthermore, in this case there were actually two commits related to the bug. An older commit that introduced the race condition, and a second commit that triggered it (by subtly changing how long a certain function took to run). The long bisection process identified the second commit but it took further work to identify the true cause of the bug.
smaddox 3y ago
Based on my reading, under some circumstances the scheduler wasn't dedicating large enough chunks of time to a particular boot process for it actually make progress. The fix appears to have been to change how the time chunk size was calculated.
- dev_tty01 3y ago
  As a curious onlooker, was the calculated time below a reasonable minimum?
  - paulclinger 3y ago
    Based on my reading it looks like the accuracy wasn't enough, so they switched it to a bit later time when hires timer was already available.
  - jseutter 3y ago
    In retrospect you could say yes, but it was hard to tell. It ended up being either okay or not okay depending on Intel vs AMD and clock speed.

There was a rare race condition [1] bug in the linux kernel, and they didn't know precisely where it was introduced (which made it difficult to know what to change to fix it). They knew it was introduced at some point between two versions, but there were 52,363 code changes between those two versions. Because the bug was rare, you would have to test any given code change multiple times (thousands of times, in their case) to be confident that the bug was still present (if working backwards), or still absent (if working forwards). A way to do that faster is a binary search [2], or commit bisection. Basically, you know commit 0 is fine, and change 52,363 is bad, so you run 1000 tests on change 26,180 to cut in half the number of commits that could have introduced the problem. If the bug is still there, then you run 1000 tests on change 13,090; if the bug is not in change 26,180, then you run 1000 tests on change 39,270. Eventually (after 15 or 16 iterations) you'll narrow down the problem to a single change which introduced the problem. Unfortunately code is complicated, so the first time they ran that procedure, their tests didn't find the right bug, so they did it again but slightly differently. (many details omitted for simplicity) [1] https://en.wikipedia.org/wiki/Race_condition https://en.wikipedia.org/wiki/Race_condition [2] https://en.wikipedia.org/wiki/Binary_search_algorithm https://en.wikipedia.org/wiki/Binary_search_algorithm?

sh34r 3y ago
It's worth mentioning that this generalized problem in user space can often be solved much more easily using concurrent fuzz testing (ex: https://www.microsoft.com/en-us/research/project/cuzz-concurrency-fuzzing/ https://www.microsoft.com/en-us/research/project/cuzz-concur...). Unfortunately, when the problem is in kernel boot software, that is not a practical solution for obvious reasons, and you're left using more basic techniques like running a binary search on the commit history.
ufo 3y ago
Furthermore, in this case there were actually two commits related to the bug. An older commit that introduced the race condition, and a second commit that triggered it (by subtly changing how long a certain function took to run). The long bisection process identified the second commit but it took further work to identify the true cause of the bug.

smaddox 3y ago

Based on my reading, under some circumstances the scheduler wasn't dedicating large enough chunks of time to a particular boot process for it actually make progress. The fix appears to have been to change how the time chunk size was calculated.

dev_tty01 3y ago
As a curious onlooker, was the calculated time below a reasonable minimum?
- paulclinger 3y ago
  Based on my reading it looks like the accuracy wasn't enough, so they switched it to a bit later time when hires timer was already available.
- jseutter 3y ago
  In retrospect you could say yes, but it was hard to tell. It ended up being either okay or not okay depending on Intel vs AMD and clock speed.