Token epiphany

Matt Dillon was answering a question from Bosko Milekic that caused him to have a realization on how to improve token-handling in both single and multiple CPU situations, with apparently significant performance benefits. I’m pasting his post to .kernel here:

“Not entirely. First, please note that the current token implementation does not work very well… it’s a mess to use because cpu #B can steal away cpu #A’s token by sending cpu #A an IPI message requesting the token. This means cpu #A has to be in a critical section to ‘protect’ the token, and must re-acquire the token (in case it was lost) after it blocks.

After thinking about this quite a bit I have come up with a solution that, in a moment of enlightment, would make our tokens operate like self-contained little RCU implementations (superior to Linux’s implementation, in fact!).

I intend to fix our tokens by not allowing an IPI to steal a token until the owning cpu has gone through a thread switch, or by explicit release. This means that, once fixed, our token implementation will allow us to abstract RCU-like operations, which I think is very important. It is not what I originally intended tokens to be but it is turning out to be what they should be.

The nice thing about the revamp I intend to do on the token code is that the RCU abstraction will wind up being a lot better then Linux’s RCU abstraction, because it will be compartmentalized. Only cpus competing for the same token are effected rather then all cpus in the system. We would not have the serialization problem that Linux has.”