The problem with 32-bit timestamps
When I was finally satisfied with the algorithm and had posted an RFC for review, Mathieu Desnoyers asked how the 64-bit atomic operations on the timestamps would work on 32-bit machines. I mentioned that I used the local64 variants of operations like local_read/cmpxchg/etc. operations. Desnoyers went on to argue that the local64 operations on 32-bit machines were horrible in performance, and worse, some require that interrupts be disabled, meaning that they could not be used in NMI context.
I conceded his point, and went about figuring out how to solve this for 32-bit systems. This required wrapping the 64-bit timestamp operations in a local function that would simply call the local64 operations on 64-bit machines, but would require doing something different for the 32-bit case. These functions were:
- rb_time_read()
- rb_time_set()
- rb_time_cmpxchg()
To come up with a solution, the requirements of the operations had to be defined that will still allow the above algorithm to work. These requirements are:
- The operation only needs to work on a 59-bit number, as that is how big the timestamps are.
- Reading may fail if (and only if) the read happens from a context that interrupted a write of that timestamp. Note, a read will succeed if it did not interrupt a write, but the read itself was interrupted, and a write occurred in the interrupting context. In that case, the read will return what was written.
- Writes via the set operation always succeed. After a write finishes, the value will always be correct. Since reads only fail if the last time it was updated was by a context the current context interrupted, a new write in the current context will make the value correct again. That is, a read after a write will always succeed.
- A read after a write will always succeed, but may not necessarily contain the same value, as an interrupt could occur between the two and update the value.
- A cmpxchg() acts like a normal cmpxchg() but may also fail if performed from a context that interrupted an update to the value.
The rb_time_* functions operate on an rb_time_struct descriptor. For 64-bit machines, it simply contains a single field of type local64_t and each of the rb_time_* functions map to the local64_* equivalents, except that rb_time_read will always return true stating that it has succeeded. Due to the true atomic features of local64_t on 64-bit machines, the values read will always have their integrity intact.
For 32-bit machines, the rb_time_* functions have a bit more work to do. The rb_time_struct is defined as follows:
struct rb_time_struct {
local_t cnt;
local_t top;
local_t bottom;
};
All fields are of the 32-bit local_t type and operations on each of them are atomic. The cnt field gets incremented every time the timestamp is updated. The 30 least significant bits (LSBs) of top and bottom are used to create a 60-bit timestamp. The two most significant bits (MSBs) are used as a counter to detect when the top and bottom are out of sync.
This structure is set using:
void rb_time_set(rb_time_t *t, u64 val)
{
unsigned long cnt, top, bottom, set;
top = val >> 30;
bottom = val & ((1 << 30) - 1);
do {
cnt = local_inc_return(&t->cnt);
set = top | ((cnt & 3) << 30);
local_set(&t->top, set);
set = bottom | ((cnt & 3) << 30)
local_set(&t->bottom, set);
} while (cnt != local_read(&t->cnt));
}
To begin, the cnt field of the rb_time_t struct is incremented and the result assigned to the local variable cnt. Then, both top and bottom are updated to the corresponding bits of that value, with the least-significant two bits of the cnt prepended to the MSBs of the value. At the end, the read cnt is compared once again with the cnt field to make sure nothing interrupted this process and wrote to the field. If it was interrupted, then the cnt field would be different and the process is repeated until it successfully updates the timestamp. It is understood that if this process was interrupted, this process would overwrite the timestamp from what it should be. But as explained in the overall algorithm, this is expected behavior and is dealt with.
Reading the timestamp must be able to detect if the value being read was in the process of being updated and was interrupted, as well as producing a valid result if the read itself is interrupted.
bool rb_time_read(rb_time_t *t, u64 *ret)
{
unsigned long cnt, top, bottom;
do {
cnt = local_read(&t->cnt);
top = local_read(&t->top);
bottom = local_read(&t->bottom);
} while (cnt != local_read(&t->cnt));
if ((top & (3 << 30)) != (bottom & (3 << 30)))
return false;
*ret = (top & ((1 << 30) - 1)) << 30 | (bottom & ((1 << 30) - 1));
return true;
}
A similar loop is performed as was done for the write to catch if an interrupt came in and updated the value between the reads of top and bottom. Then the two bits of the MSBs of top and bottom are compared. If they do not match, then this must have interrupted an update of the value. One may be wondering if two bits is enough. That gives a counter up to four, and since there are only four levels of interruption that need to be handled, each layer will see a unique number. Finally, the 60-bit value is put together from the 30 bits each of top and bottom. Note, this requires some typecasts to allow the 32-bit values to become 64-bit values, but that was left out of the example to keep it easier to read.
Finally the cmpxchg() function needs to be implemented:
int rb_time_cmpxchg(rb_time_t *t, u64 expect, u64 set)
{
unsigned long cnt, top, bottom;
unsigned long cnt2, top2, bottom2;
u64 val;
if (!rb_time_read(t, &val))
return false;
if (val != expect)
return false;
cnt = local_read(&t->cnt);
cnt2 = cnt + 1;
top = ((cnt & 3) << 30) | (val >> 30);
bottom = ((cnt & 3) << 30) | (val & ((1 << 30) - 1));
top2 = ((cnt2 & 3) << 30) | (set >> 30);
bottom2 = ((cnt2 & 3) << 30) | (set & ((1 << 30) - 1));
if (local_cmpxchg(&t->cnt, cnt, cnt2) != cnt)
return false;
if (local_cmpxchg(&t->top, top, top2) != top)
return false;
if (local_cmpxchg(&t->bottom, bottom, bottom2) != bottom)
return false;
return true;
}
This function starts out by simply using the above algorithm to read the
value and make sure that the resulting value matches the expected value, or
if the read has interrupted an update, which will fail the
cmpxchg() function. The cnt field is read and saved. As
updates increment this value, the cmpxchg() must also do so, and
the new value is set to one more than the read value. The top and
bottom are calculated from both the read value and the new value
along with the two LSBs from the appropriate cnt variables that
will be applied at the two MSBs of those values. The last thing to do is to
walk through each field using cmpxchg() to update them. If at any
time this gets interrupted and the values are updated during this process,
the next cmpxchg() will fail and the function exits with
false. In that case, the interrupting context would have
completely updated the value and the value would still retain
integrity. The three cmpxchg()s for one may seem to be a little
extreme. But remember, this is already performed in the slow path, and
these native updates are still more efficient than using a
local64_cmpxchg() on a 32-bit system.
| Index entries for this article | |
|---|---|
| GuestArticles | Rostedt, Steven |
