Avoid deadlocks in multi-threaded attribute computation

[inkytonik]

From Miguel Branco:

In a multi-threaded environment, we can have two attributes being computed separately by two independent threads.

Attribute A is locking a parent node while recursing through a child (and trying to obtain a lock for that node). Attribute B, on another thread, is locking the child and trying to obtain a parent or something else locked. Attributes A and B are independent. This is totally harmless in general, but now that attributes are synchronized, the thread computing attribute A is holding a lock while trying to obtain another, while the thread computing attribute B is holding the other lock; so they deadlock.

We had this happen for instance as we had a shared tree used by all programs: a “standard library” tree of sorts, which all programs have access to. Each program is its own separate thread and normally is fully isolated. But as soon as attributes became synchronized, they were deadlocking. If we computed all attributes upfront for that shared tree first, all is ok (but somewhat clumsy to do as we do have many attrs). If we clone that standard library so that each program sees a different node, all is ok as well (better but slower).

I’m not sure what the right approach is here though. So far, this would have not been an issue, but adding synchronized to Kiama seems to indicate an intention to support muti-threaded environments. In that case, locking pairs of attribute/node sounded safer perhaps?

[inkytonik]

Note that we have some multi-threading support already, but it seems we lock things down too much. A possible avenue for exploration is to only lock when we are actively updating the caching information, rather than for the whole time an attribute is being evaluated.