# On-the-Fly Repairing of Atomicity Violations in ARINC 653 Software
## 4 RAV: Repairing Atomicity Violations
### Embedded AI (eAI)  
RAV modifies the algorithm of AI to collect correct interleaving in the test phase and to treat atomicity violations in the operation phase by reflecting the problem as described above. We named eAI (embedded AI) the modified version of AI. When a loop is executed in embedded software, eAI collects the static instruction \(S_{x}\) that satisfies the following conditions for the current dynamic instruction \(D_{x}\):  
* A variable in the data area of low memory is allocated;
* The same memory address is assessed;
* The instruction comes from another thread;
* The instruction immediately before \(D_{x}\) is assessed. The training algorithm of AI keeps track of all variables and then identifies variables that have accessed the same memory address in different threads as shared variables. Local variables declared in a loop can be repeatedly allocated and deallocated. Then, the variable may be allocated in the same address as the previous allocation. Then, AI faces the problem of identifying the local variables as shared variables. The training algorithm of eAI does not track all variables but only the variables allocated to the data area of memory. The overall correct interleaving collection process is as follows: (1) Instrument TraceMemoryAccesses() in the target program. (2) Execute the target program to trace information of shared variables. (3) Once the target program's execution is completed, the \(BSet\) is executed to create a program with trace information. (4) Obtain \(BSet\), which is a correct interleaving set. This process is the same as AI, but the algorithm for instrumenting the memory tracking function into the target program was modified into Algorithm 1. Figure 4: The repairing time of synthetic programs with 1000 iterations. ```
1 FunctionInstrumentLoadOrStore(Instruction*I):
2 IRBuilder<> IRB(I)
3 MDNode*Node = I->getMetadata(\"eAIMemoryAccessID\")
4 Value*ID = Node>getOperand(0)
5 ConstantInt*CI = dyn_cast<ConstantInt>(ID)
6 Value*Addr = IsWrite? cast<StoreInst>(I)->getPointerOperand() : cast<LoadInst>(I)->getPointerOperand()
7 ifconstGlobalValue*G = dyn_cast<GlobalValue>(Addr)then
8 IRB.CreateCall2(TraceAccesses, CI, IRB.CreatePointerCast(Addr, IRB.getInt8 Ptr()))
```  
**Algorithm 1**Training of eAI. When atomicity violations are diagnosed, the treatAV() of AI stalls the thread using sleep(). Since stalling requires a fixed delay time, there is an issue of time overhead in the treatment process. If the overhead is high, the program may not meet the real-time performance requirements; thus, we should appropriately manage stalling time. As shown in Figure 4, the overhead of stalling in repair time increases rapidly according to the size of the delay time set for treatment. On the contrary, when we use the condition variable, the time spent repairing can be shorter than that when using the stalling. This paper used the condition variable, so that we could apply it in a real-time system. The stalling, which uses sleep(), can be easily applied because it only needs to delay the execution of the thread in which an atomicity violation has occurred. However, to use the condition variable, we must know the current repairing status of the program. Therefore, treatAV() of eAI uses a state machine to determine the current repairing status. The finite-state machine is illustrated in Figure 5. The state when the program is executed is \(Normal\). When an atomicity violation is diagnosed during execution and treatAV() executes wait(), a transition is made from the \"Normal\" state to the \"Wait\" state. Since the diagnosis of atomic violation after switching to the \(Wait\) state occurs because the repairing has not been completed yet, treatAV() of eAI is not performed. Upon diagnosing that there are no atomic violations (it has been repaired), treatAV() transitions from the \(Wait\) state to the \(Normal\) state, resuming the stopped thread via signal(). The treatment algorithm of eAI is described in Algorithm 2.