at the same time to update the parent directory modify time, same data. TM is more modular than locks and can provide
which will manifest as contention not just for the dentry greater concurrency with simpler/coarser locks; operating
->d_lock but for the parent directory’s p->d_lock, and systems can benefit.
p->d_count, as well as the dcache->lock). While an OS
provides programmers with the abstraction of a single se- 3. 2. converting linux to txlinux-ss
quential operation involving a single thread of control, all of Figure 1 also illustrates the most common paradigm for in-these threads coexist in the kernel. Even when the OS man- troducing transactions into a lock-based program: mapping
ages access to different files for different programs, resources lock acquires and releases to transaction begin and end, re-can be used concurrently as a result, and the OS must syn- spectively. This was the first approach taken to using trans-chronize its own accesses to ensure the integrity of the data actions in Linux, called TxLinux-SS. Linux features over 2000
structures involved. static instances of spinlocks, and most of of the transactions
To maintain good performance in the presence of such in TxLinux-SS result from converted spinlocks. TxLinux-SS
sharing patterns, many OSes have required great program- also converts reader/writer spinlock variants and se-qlocks
mer effort to make synchronization fine-grained—i.e., locks to transactions. Based on profiling data collected from the
only protect the minimum possible data. However, synchro- Syncchar tool, 18 the locks used in nine subsystems were con-nization makes OS programming and maintenance difficult. verted to use transactions. TxLinux-SS took six developers a
In one comprehensive study of Linux bugs, 346 of 1025 bugs year to create, and ultimately converted approximately 30%
(34%) involved synchronization, and another study7 found of the dynamic locking calls in Linux (in our benchmarks) to
four confirmed and eight unconfirmed deadlock bugs in use transactions.
the Linux 2. 5 kernel. The complexity of synchronization is The TxLinux-SS conversion of the kernel exposes several
evident in the Linux source file mm/filemap. c that has a serious challenges that prevent rote conversion of a lock-
50 line comment on the top of the file describing the lock based operating system like Linux to use transactions, in-ordering used in the file. The comment describes locks used cluding idiosyncratic use of lock functions, control flow that
at a calling depth of four from functions in the file. Locking is difficult to follow because of heavy use of function point-is not composable; a component must know about the locks ers, and most importantly, I/O. In order to ensure isolation,
taken by another component in order to avoid deadlock. HTM systems must be able to roll back the effects of a trans-
TM can help reduce the complexity of synchronization action that has lost a conflict. However, HTM can only roll
in contexts like the dparent_notify function. Because back processor state and the contents of physical memory.
multiple locks are involved, the OS must follow a locking The effects of device I/O, on the other hand, cannot be rolled
ordering discipline to avoid deadlock, which would be un- back, and executing I/O operations as part of a transaction
necessary with TM. The fine-grain locking illustrated by can break the atomicity and isolation that transactional
dparent_notify’s release of the dentry->d_lock and systems are designed to guarantee. This is known as the
subsequent acquisition of the p->d_lock and dcache “output commit problem.” 6 A computer system cannot un-_lock could be elided with transactions. If the function launch missiles.
is called with different parent directories, the lock-based If the dentry_iput function in Figure 1, performs
code still forces some serialization because of the dcache I/O, the TxLinux-SS transactionalization of the kernel will
->lock. However, transactions can allow concurrent execu- not function correctly if the transaction aborts. TM alone
tions of critical sections when they do not contend for the is insufficient to meet all the synchronization needs of an
figure 1: three adapted versions of the linux file system dparent_notify () function, which handles update of a parent directory when a
file is accessed, updated, or deleted. the leftmost version uses locks, the middle version uses bare transactions and corresponds to the code
in txlinux-ss, and the rightmost version uses cxspinlocks, corresponding to txlixux-cX. note that the dentry_iput function can do i/o.
void
dnotify_parent(dentry_t *dentry,
ulong evt) {
spin_lock(&dentry->d_lock);
dentry_t * p = dentry->d_parent;
dget(p);
spin_unlock(&dentry->d_lock);
inode_dir_notify(p->d_inode,evt);
spin_lock(&dcache_lock);
if(!(––p->d_count)) {
spin_lock(&p->d_lock);
dentry_iput(p);
d_free(p);
spin_unlock(&p->d_lock);
}
spin_unlock(&dcache_lock);
}
void
dnotify_parent(dentry_t *dentry,
ulong evt) {
xbegin;
dentry_t *p = dentry->d_parent;
dget(p);
inode_dir_notify(p->d_inode,evt);
if(!(--p->d_count)) {
dentry_iput(p);
d_free(p);
}
xend;
}
void
dnotify_parent(dentry_t *dentry,
ulong evt) {
cx_optimistic(&dentry->d_lock);
dentry_t * p = dentry->d_parent;
dget(p);
cx_end(&dentry->d_lock);
inode_dir_notify(p->d_inode,evt);
cx_optimistic(&dcache_lock);
if(!(--p->d_count)){
cx_optimistic(&p->d_lock);
dentry_iput(p);
d_free(p);
cx_end(&p->d_lock);
}
cx_end(&dcache_lock );
