operating system. Critical sections protected by locks will not restart and so may freely perform I/O. There will always be a need for some locking synchronization in an operating system, but operating systems should be able to take advantage of TM wherever possible. Given that transactions and locks will have to coexist in any realistic implementation, cooperation between locks and transactions is essential.

4. cooPeRation Bet Ween locKs anD
tRansactions

In order to allow both transactions and conventional locks in the operating system, we propose a synchronization API that affords their seamless integration, called cooperative transactional spinlocks, or cxspinlocks. Cxspinlocks allow different executions of a single critical section to be synchronized with either locks or transactions. This freedom enables the concurrency of transactions when possible and enforces the safety of locks when necessary. Locking may be used for I/O, for protection of data structures read by hardware (e.g., the page table), or for high-contention access paths to particular data structures (where the performance of transactions might suffer from excessive restarts). The cxspinlock API also provides a simple upgrade path to let the kernel use transactions in place of existing synchronization.

Cxspinlocks are necessary for the kernel only; they allow the user programming model to remain simple. Users do not need them because they cannot directly access I/O devices (in Linux and most operating systems, users perform I/O by calling the OS). Blocking direct user access to devices is a common OS design decision that allows the OS to safely multiplex devices among noncooperative user programs. Sophisticated user programs that want transactions and locks to coexist can use cxspinlocks, but it is not required.

Using conventional Linux spinlocks within transactions is possible and will maintain mutual exclusion. However, conventional spinlocks reduce the concurrency of transactions and lacks fairness. Conventional spinlocks prevent multiple transactional threads from executing a critical region concurrently. All transactional threads in a critical region must read the spinlock memory location to obtain the lock and must write it to obtain the lock and release it. This write sharing among transactional threads will prevent concurrent execution, even if concurrent execution of the “real work” in the critical section is safe. Moreover, conventional spinlocks do not help with the I/O problem. A transactional thread that acquires a spinlock can restart, therefore it cannot perform I/O.

The progress of transactional threads can be unfairly throttled by non-transactional threads using spinlocks. In Meta TM conflicts between transactional and non-transactional threads (asymmetric conflicts) are always resolved in favor of the non-transactional thread. To provide isolation, HTM systems guarantee either that non-transactional threads always win asymmetric conflicts (like MetaTM), or transactional threads always win asymmetric conflicts (like Log-TM¹⁴). With either convention, traditional spinlocks will cause unfairness between transactional and non-transactional threads.

4. 1. cooperative transactional spinlocks Cxspinlocks allow a single critical region to be safely protected by either a lock or a transaction. A non-transactional thread can perform I/O inside a protected critical section without concern for undoing operations on a restart. Many transactional threads can simultaneously enter critical sections protecting the same shared data, improving performance. Simple return codes in MetaTM allow the choice between locks and transactions to be made dynamically, simplifying programmer reasoning. Cxspinlocks ensure a set of behaviors that allow both transactional and non-transactional code to correctly use the same critical section while maintaining fairness and high concurrency:

 

• Multiple transactional threads may enter a single critical section without conflicting on the lock variable. A non-transactional thread will exclude both transactional and other non-transactional threads from entering the critical section.

• Transactional threads poll the cxspinlock using the xtest instruction, which allows a thread to check the value of a lock variable without entering the lock variable into the transaction’s read-set, enabling the transaction to avoid restarting when the lock is released (another thread writes the lock variable). This is especially important for acquiring nested cxspinlocks where the thread will have done transactional work before the attempted acquire.

• Non-transactional threads acquire the cxspinlock using an instruction (xcas) that is arbitrated by the transactional contention manager. This enables fairness between locks and transactions because the contention manager can implement many kinds of policies favoring transactional threads, non-transactional threads, readers, writers, etc.

 

Figure 2 shows the API and implementation. Cxspinlocks are acquired using two functions: cx_exclusive and cx_optimistic. Both functions take a lock address as an argument.

cx_optimistic is a drop-in replacement for spinlocks and is safe for almost all locking done in the Linux kernel (the exceptions are a few low-level page table locks and locks whose ownership is passed between threads, such as that protecting the run queue). cx_optimistic optimistically attempts to protect a critical section using transactions. If a code path within the critical section protected by cx_optimistic requires mutual exclusion, then the transaction restarts and acquires the lock exclusively. The code in Figure 1, which can fail due to I/O with bare transactions, functions with cxspinlocks, taking advantage of optimism with transactions when the dentry_iput function does no I/O, and retrying with with exclusive access when it does.

Control paths that will always require mutual exclusion (e.g., those that always perform I/O) can be optimized with cx_exclusive. Other paths that access the same data structure may execute transactionally using cx_optimistic. Allowing different critical regions to synchronize with a mix of