xCalls: safe I/O in memory transactions

ABSTRACT

Memory transactions, similar to database transactions, allow a programmer to focus on the logic of their program and let the system ensure that transactions are atomic and isolated. Thus, programs using transactions do not suffer from deadlock. However, when a transaction performs I/O or accesses kernel resources, the atomicity and isolation guarantees from the TM system do not apply to the kernel.

The xCall interface is a new API that provides transactional semantics for system calls. With a combination of deferral and compensation, xCalls enable transactional memory programs to use common OS functionality within transactions.

We implement xCalls for the Intel Software Transactional Memory compiler, and found it straightforward to convert programs to use transactions and xCalls. In tests on a 16-core NUMA machine, we show that xCalls enable concurrent I/O and system calls within transactions. Despite the overhead of implementing transactions in software, transactions with xCalls improved the performance of two applications with poor locking behavior by 16 and 70%.

REFERENCES

• 1: Lee Baugh , Naveen Neelakantam , Craig Zilles, Using Hardware Memory Protection to Build a High-Performance, Strongly-Atomic Hybrid Transactional Memory, Proceedings of the 35th International Symposium on Computer Architecture, p.115-126, June 21-25, 2008
• 2: Lee Baugh and Craig Zilles. An analysis of I/O and syscalls in critical sections and their implications for transactional memory. In TRANSACT 2, August 2007.
• 3: Andrew D. Birrell and Michael Isard. Automatic mutual exclusion. In HotOS 11, May 2007.
• 4: Colin Blundell , Joe Devietti , E. Christopher Lewis , Milo M. K. Martin, Making the fast case common and the uncommon case simple in unbounded transactional memory, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 5: Bryan Cantrill. Concurrency's shysters. http://blogs.sun.com/bmc/entry/concurrency_s_shysters, November 2008.
• 6: Calin Cascaval , Colin Blundell , Maged Michael , Harold W. Cain , Peng Wu , Stefanie Chiras , Siddhartha Chatterjee, Software transactional memory: why is it only a research toy?, Communications of the ACM, v.51 n.11, November 2008 [doi>10.1145/1400214.1400228]
• 7: Peter Damron , Alexandra Fedorova , Yossi Lev , Victor Luchangco , Mark Moir , Daniel Nussbaum, Hybrid transactional memory, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 8: Dave Dice, Ori Shalev, and Nir Shavit. Transactional locking ii. In DISC 20, September 2006.
• 9: Polina Dudnik and Michael M. Swift. Condition variables and transactional memory: Problem or opportunity? In TRANSACT 4, February 2009.
• 10: Alexandra Fedorova , Margo Seltzer , Michael D. Smith, Improving Performance Isolation on Chip Multiprocessors via an Operating System Scheduler, Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques, p.25-38, September 15-19, 2007 [doi>10.1109/PACT.2007.40]
• 11: Christof Fetzer and Pascal Felber. Improving program correctness with atomic exception handling. Journal of Universal Computer Science, 13(8):1047--1072, 2007.
• 12: R. M. Fujimoto, The virtual time machine, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.199-208, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72957]
• 13: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 14: Lance Hammond , Vicky Wong , Mike Chen , Brian D. Carlstrom , John D. Davis , Ben Hertzberg , Manohar K. Prabhu , Honggo Wijaya , Christos Kozyrakis , Kunle Olukotun, Transactional Memory Coherence and Consistency, Proceedings of the 31st annual international symposium on Computer architecture, p.102, June 19-23, 2004, München, Germany
• 15: Tim Harris. Exceptions and side-effects in atomic blocks. In PODC Workshop on Concurrency and Synchronization in Java Programs, Jul 2004.
• 16: Tim Harris , Keir Fraser, Language support for lightweight transactions, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 17: Tim Harris, Simon Marlow, Simon Peyton Jones, and Maurice Herlihy. Composable memory transactions. In PPOPP 12, June 1991.
• 18: Tim Harris , Mark Plesko , Avraham Shinnar , David Tarditi, Optimizing memory transactions, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 19: R. Haskin , Y. Malachi , W. Sawdon , G. Chan, Recovery management in QuickSilver, Proceedings of the eleventh ACM Symposium on Operating systems principles, p.107-108, November 08-11, 1987, Austin, Texas, United States
• 20: Maurice Herlihy and J. Eliot B. Moss. Transactional memory: Architectural support for lock-free data structures. Technical Report Technical Report 92/07, Digital Cambridge Research Lab, 1992.
• 21: Intel. Intel c++ stm compiler prototype edition 2.0 language extensions and user's guide. Technical Report 318253-001US, Intel Corp., April 2008.
• 22: Internet Systems Consortium. Berkeley internet name domain (BIND). http://www.isc.org/index.pl?/sw/bind/.
• 23: David R. Jefferson, Virtual time, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.3, p.404-425, July 1985 [doi>10.1145/3916.3988]
• 24: Tatuya Jinmei , Paul Vixie, Implementation and evaluation of moderate parallelism in the BIND9 DNS server, Proceedings of the annual conference on USENIX '06 Annual Technical Conference, p.12-12, May 30-June 03, 2006, Boston, MA
• 25: Horatiu Jula, Daniel Tralamazza, Cristian Zamfir, and George Candea. Deadlock immunity: Enabling systems to defend against deadlocks. In OSDI 8, November 2008.
• 26: David E. Lowell , Peter M. Chen, Persistent messages in local transactions, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.219-226, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277737]
• 27: Shan Lu , Soyeon Park , Eunsoo Seo , Yuanyuan Zhou, Learning from mistakes: a comprehensive study on real world concurrency bug characteristics, Proceedings of the 13th international conference on Architectural support for programming languages and operating systems, March 01-05, 2008, Seattle, WA, USA
• 28: Austen McDonald , JaeWoong Chung , Brian D. Carlstrom , Chi Cao Minh , Hassan Chafi , Christos Kozyrakis , Kunle Olukotun, Architectural Semantics for Practical Transactional Memory, Proceedings of the 33rd annual international symposium on Computer Architecture, p.53-65, June 17-21, 2006
• 29: Vijay Menon, Steven Balensiefer, Tatiana Shpeisman, Ali-Reza Adl-Tabatabai, Richard L. Hudson, Bratin Saha, and Adam Welc. Single global lock semantics in a weakly atomic STM. In TRANSACT 3, February 2008.
• 30: Microsoft Corp. Transactional memory team blog. http://blogs.msdn.com/stmteam/default.aspx, October 2008.
• 31: Chi Cao Minh, Martin Trautmann, JaeWoong Chung, Austen Mcdonald, Nathan Bronson, Jared Casper, Christos Kozyrakis, and Kunle Olukotun. An effective hybrid transactional memory system with strong isolation guarantees. In ISCA 34, June 2007.
• 32: Kevin E. Moore, Jayaram Bobba, Michelle J. Moravan, Mark D. Hill, and David A.Wood. Logtm: Log-based transactional memory. In HPCA 12, pages 258--269, February 2006.
• 33: Michelle J. Moravan , Jayaram Bobba , Kevin E. Moore , Luke Yen , Mark D. Hill , Ben Liblit , Michael M. Swift , David A. Wood, Supporting nested transactional memory in logTM, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 34: J. Eliot B. Moss. Open nested transactions: Semantics and support. In Workshop on Memory Performance Issues, February 2006.
• 35: Yang Ni , Adam Welc , Ali-Reza Adl-Tabatabai , Moshe Bach , Sion Berkowits , James Cownie , Robert Geva , Sergey Kozhukow , Ravi Narayanaswamy , Jeffrey Olivier , Serguei Preis , Bratin Saha , Ady Tal , Xinmin Tian, Design and implementation of transactional constructs for C/C++, Proceedings of the 23rd ACM SIGPLAN conference on Object-oriented programming systems languages and applications, October 19-23, 2008, Nashville, TN, USA
• 36: Edmund B. Nightingale , Peter M. Chen , Jason Flinn, Speculative execution in a distributed file system, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 37: Marek Olszewski , Jeremy Cutler , J. Gregory Steffan, JudoSTM: A Dynamic Binary-Rewriting Approach to Software Transactional Memory, Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques, p.365-375, September 15-19, 2007 [doi>10.1109/PACT.2007.42]
• 38: Oracle Corporation. Oracle Berkeley Database. http://www.oracle.com/database/berkeley-db/index.html.
• 39: Christopher J. Rossbach , Owen S. Hofmann , Donald E. Porter , Hany E. Ramadan , Bhandari Aditya , Emmett Witchel, TxLinux: using and managing hardware transactional memory in an operating system, Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles, October 14-17, 2007, Stevenson, Washington, USA
• 40: Bratin Saha , Ali-Reza Adl-Tabatabai , Richard L. Hudson , Chi Cao Minh , Benjamin Hertzberg, McRT-STM: a high performance software transactional memory system for a multi-core runtime, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA [doi>10.1145/1122971.1123001]
• 41: Bratin Saha , Ali-Reza Adl-Tabatabai , Quinn Jacobson, Architectural Support for Software Transactional Memory, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.185-196, December 09-13, 2006 [doi>10.1109/MICRO.2006.9]
• 42: Chris Schlaeger. The impact of operating systems on modern CPU designs (and vice versa). http://arcs08.inf.tu-dresden.de/docs/arcs08 schlaeger-sld.pdf,February 2008.
• 43: Yannis Smaragdakis , Anthony Kay , Reimer Behrends , Michal Young, Transactions with isolation and cooperation, Proceedings of the 22nd annual ACM SIGPLAN conference on Object-oriented programming systems and applications, October 21-25, 2007, Montreal, Quebec, Canada
• 44: Michael F. Spear, Maged M. Michael, and Michael L. Scott. Inevitability mechanisms for software transactional memory. In TRANSACT 3, February 2008.
• 45: Thomas Strandenæs and Randi Karlsen. Transaction compensation in web services. In Norsk Informatikkonferanse, June 2002.
• 46: Herb Sutter , James Larus, Software and the Concurrency Revolution, Queue, v.3 n.7, September 2005 [doi>10.1145/1095408.1095421]
• 47: Michael M. Swift, Haris Volos, Neelam Goyal, Luke Yen, Mark D. Hill, and David A.Wood. OS support for virtualizing hardware transactional memory. In TRANSACT 3, February 2008.
• 48: Marc Tremblay and Shailender Chaudhry. A third-generation 65nm 16-core 32-thread plus 32-scout-thread cmt sparc processor. In ISSCC 2008 Conference Proceedings, February 2008.
• 49: Haris Volos, Neelam Goyal, and Michael M. Swift. Pathological interaction of locks with transactional memory. In TRANSACT 3, February 2008.
• 50: Cheng Wang , Wei-Yu Chen , Youfeng Wu , Bratin Saha , Ali-Reza Adl-Tabatabai, Code Generation and Optimization for Transactional Memory Constructs in an Unmanaged Language, Proceedings of the International Symposium on Code Generation and Optimization, p.34-48, March 11-14, 2007 [doi>10.1109/CGO.2007.4]
• 51: Yin Wang, Terence Kelly, Manjunath Kudlur, Stephane Lafortune, and Scott Mahlke. Gadara: Dynamic deadlock avoidance for multithreaded programs. In OSDI 8, November 2008.
• 52: Adam Welc , Bratin Saha , Ali-Reza Adl-Tabatabai, Irrevocable transactions and their applications, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany [doi>10.1145/1378533.1378584]
• 53: xiph.com. Ogg Vorbis documentation. http://www.xiph.org/vorbis/doc/.
• 54: xmms.org. X Multimedia System. www.xmms.org.
• 55: Luke Yen , Jayaram Bobba , Michael R. Marty , Kevin E. Moore , Haris Volos , Mark D. Hill , Michael M. Swift , David A. Wood, LogTM-SE: Decoupling Hardware Transactional Memory from Caches, Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, p.261-272, February 10-14, 2007 [doi>10.1109/HPCA.2007.346204]
• 56: Craig Zilles and Lee Baugh. Extending hardware transactional memory to support non-busy waiting and nontransactional actions. In TRANSACT 1, June 2006.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Concurrency

General Terms:
Design, Languages, Performance

Keywords:
I/O, concurrent programming, system calls, transactional memory, xCalls