RETCON: Transactional Repair without Replay

This is a paper from the architecture community (ISCA'10), and is solving transnational memory problem. But maybe it is useful in a journal file-system's context?

Inspired by selective replay [Sirnivasan+'04, Sarangi+'05,...]

Observation: main data are concurrent, but aux data are conflicted. Auxiliary data will serialize parallel operations, thus significantly reduce performance  (Example: hashtable's size etc.)

Basic idea: use symbolic tracking to ensure that if aux data conflicts, we repare, but the main data could be updated concurrently.


Approach:
1. Use symbolic values of input/output (keep track of what variables we are storing at each register, and what variables we are writing from register to the memory).
2. At commit: if somebody else changed the aux data's value when we are in our transaction, we just repair by update the aux data again, but the main data structure remain being updated concurrently.
2. Track constraint on inputs: if constraint is not violated, then not alternative code path needs to be taken (no change in control flow),  Then 1 and 2 would work just fine, but if the control flow changed, we need to abort the transaction and restart the execution.

How this could be applied to file system?

Related work:
•ReSlice [Sarangi+’05]
        Maintains insns in dependent slice of conflicting operation in TLS
        To repair, re-executes these instructions
•Dependence-aware transactional memory [Ramadan+’08]
        Forwards speculative values to optimize ordered communication
        Unlike RetCon, can’t handle conflicts with cyclic communication…
        But OTOH, can handle arbitrarily complex computation

•Advanced TM interfaces & data structure implementations
        Open nesting [Moss+’05,Moravan+’06,Ni+’07]
        Transactional boosting [Herlihy+’08]
         Abstract nesting [Harris+’07]
         Lock-free hashtables [Click’07,…]
         Scalable non-zero indicators [Ellen+’07]