Make TS::Cache atomic check-then-act methods "recursive-able"

[thedarkone]

WIP (next month?).

[sferik]

@thedarkone Just wanted to ping you about this issue, now that it’s November. I would really ❤️ to see this feature implemented.

[thedarkone]

Had a look at it, turns out it isn't as easy as I imagined, I'm not giving up, but dunno if it reasonably doable.

[sferik]

😞 What makes it harder than you imagined?

[thedarkone]

Long story short, non-MRI versions of TS::Cache are implemented as an array containing linked lists of key-value pairs (this is what 99% percent of Hash implementations usually are like inside). Check-then-act methods are implemented by holding a lock on the "head" of the given linked-list, the problem is that in the current implementation the lock is non-reentrant. I knew that the next version of CHMv8 was going to have re-entrant locks (note that this wasn't to enable nested check-then-act methods, rather it was coincidental) and naively thought that this would be enough, preliminary testing shows that it is not - the whole thing goes into an infinite loop :).

Now I have to try to understand what goes wrong and see if it is fixable, but the code is far from trivial (for example this is what internals of computeIfAbsent look like, feel free to scroll around for some other friendly code 😇).

Note that however that nested/re-entrant compute_if_absent isn't as useful as one might think, imagine for example that you have 3 keys: :A, :B, :C - where:

• :A depends (via compute_if_absent) on :B,
• :B depends (via compute_if_absent) on :C.

Now :C and :A end up in the same Hash "bucket" (a linked list from above) due to their hash collision (note that this doesn't mean that :C and :A have the same hash value, it's that when it gets mod-ed by the backing array's length they and up in the same slot). So :A and :C go into bucket_X and :B goes into bucket_Y. When Thread 1 tries to compute :A and Thread 2 tries to compute :B:

• Thread 1 gets a hold on the bucket_X's lock as it intends to compute :A's value,
• Thread 2 gets a hold on the bucket_Y's lock as it intends to compute :B's value,
• Thread 1 tries to grab bucket_Y's lock and gets stuck,
• Thread 2 tries to grab bucket_X's lock and the whole thing deadlocks.

[headius]

Is there anything left to do here? Is it doable?

[thedarkone]

I no longer think this is even remotely possible, CHMv8's design is heavily reliant on update methods having exclusive access to hash's bins (this includes non-reentrability). Besides, I still maintain that even if it is fixable, this would only open unsuspecting users to random deadlocks, therefore the current mode of early failure is even "beneficial".