iDO: Compiler-Directed Failure Atomicity for Non-Volatile Memory

Comment:

1. This approach is essentially a hybrid between value-logging and execution-driven recovery. It uses undo-based logging to create a consistent checkpoint before each idempotent region, and then relies on re-execution to reach the final state as if no crash had happened.

2. This scheme does not need to track dependencies, because no job that has already been done is rolled back (except the corner case when a thread acquired a lock but has not added the lock into the list, which makes no harm because for such a thread no dependency has been established).

This paper proposes iDO, a crash recovery scheme based on Non-Volatile Memory using idempotent regions. Classical crash recovery schemes, such as undo logging, redo logging, and shadow mapping, incur too much overhead by maintaining a runtime write set and persisting data into the NVM with heavy-weight barriers. A more recent proposal, Justdo Logging, abandons per-store logging and data-centric approach of recovery, and instead, relies on the re-execution of the Failure-Atomic Section (FASE) to reproduce the state before the crash, and furthermore, restore the consistent system state by executing the FASE till completion. Although Justdo logging may offer better performance because of less persistence barrier, it has two constraints which may hinder its practicability. First, Justdo logging assumes a non-volatile cache, which is not yet available on today’s architecture. Even on future platforms where the cache can be made persistent or be backed by a battery, the feasibility of persistent cache is still questionable. Second, Justdo logging requires FASEs be compiled in a way such that no variable is allocated in the register. To support resumation of execution from an arbitrary point within the FASE, all memory states must be consistent at the point of crash. If a variable is allocated in the register, then the most up-to-date value of the variable will be lost, resulting in an invalid snapshot. To enforce this allocation rule, all variables within a FASE must be declared as volatile, which forces writes to these variables to be conducted on the memory address.

Instead of performing value-based logging, or changing compiler’s optimization, iDO leverages the notion of idempotent regions. An idempotent region is a one-entry, multiple-exit deterministic code block, the execution of which always output the same result given the same input. The general idea is that, if we can divide FASEs into idempotent regions, then as long as we provide the same input as the ones in normal execution, the final system state will be exactly identical to the one as if normal execution had not been interrupted.

This paper assumes that the system is a hybird of NVM and DRAM, with a NVM-specific memory allocation that maps a region of memory onto the NVM device. Programmers need to wrap their FASE within a special routine, and all critical sections of the FASE must be included in the same routine (i.e. no lock held when the routine is called or returns). It is also assumed that FASEs themselves do not contain software bugs that can cause crash and invoke recovery, because the original execution will be replayed during recovery. If the crash is caused by the FASE itself, then during recovery the same bug will be produced again, which blocks the recovery handler from making any progress. The last assumotion is that persistent writes must be within a FASE, because the recovery guarantee of iDO is that the system will be restored to a state in which FASEs are either fully completed, or not executed at all. Writes to NVM outside a FASE may or may not have been persisted (due to lack of tracking) when the system crashes, and therefore the write might be missing from the final result, while a FASE after the write in program order is re-executed.

At initialization time, each thread is allocated a log object, which is organized into a linked list. The recovery handler will locate this linked list after a crash. The log object consists of three types of contect information for re-execution of an idempotent region. First, all input variables are recorded in the object, including register variables and stack allocated variables. Second, the program counter of the idempotent region is stored, which is co-located with a flag that indicates the validity of the log object. When setting this field of a log object, we can also atomically set the validity bit in the same write (since they are co-located in an 8-byte word), which saves an extra persistence barrier. The third type is a list of lock addresses, which represent the locks that this thread has acquired and may have executed the body of the critical section protected by the lock. During recovery, this list will be used to infer lock-ownership and re-acquire locks before execution resumes.

iDO relies on the compiler to identify idempotent regions and insert handler functions at appropriate locations. The compiler inserts function calls at the beginning and end of idempotent regions. On entering of the first idempotent region in a FASE, the handler function will copy the arguments and part of the stack frame into the log object for re-execution, execute a barrier, and then sets the PC in the log object, and then a second barrier. At the end of a idempotent region, the handler inserts a function to collect live variables and spill them into the log object as the input of the next region. These variables may be allocated in the register or on the stack. No instrumentation for store is inserted as in value-logging based approaches. Lock acquire and release are also instrumented. Locks in iDO are assumed to be volatile, and will be unlocked automatically when the system crashes. Compared with Justdo logging in which locks are persistent, this design avoids writing log entries both before and after the lock/unlock operation as in Justdo logging. Idempotent region boundaries are also inserted after lock acquisition and before lock release (although the paper did not mention the reason).

During recovery, the recovery handler first starts the same number of recovery threads as in Justdo logging. In the first stage, these threads re-acquire locks that have been acquired before the crash. Recall that in Justdo logging, threads first scan their own pending lists, and releases the lock that might have been acquired. In iDO, this step is omitted, because locks are volatile and will be released automatically by the crash. As a result, iDO recovery threads only scan the lock list and acquire locks using the addresses stored in the list. Threads execute a barrier to synchronize after this stage. In the second stage, threads locate their log object, and restores the state of local variables, including register variables and memory variables. After restoration of local states, the recovery thread jumps to the PC in the log object, which is the begin address of the most recent idempotent block. After that, threads keep executing until the FASE is completed, at which point they exit and leave the rest to the application.