Introducing technology into the Linux kernel: a case study

ABSTRACT

There can be no doubt that a great many technologies have been added to Linux™ over the past ten years. What is less well-known is that it is often necessary to introduce a large amount of Linux into a given technology in order to successfully introduce that technology into Linux. This paper illustrates such an introduction of Linux into technology with Read-Copy Update (RCU). The RCU API's evolution over time clearly shows that Linux's extremely diverse set of workloads and platforms has changed RCU to a far greater degree than RCU has changed Linux---and it is reasonable to expect that other technologies that might be proposed for inclusion into Linux would face similar challenges. In addition, this paper presents a summary of lessons learned and an attempt to foresee what additional challenges Linux might present to RCU.

REFERENCES

• 1: Arcangeli, A., Cao, M., McKenney, P. E., and Sarma, D. Using read-copy update techniques for System V IPC in the Linux 2.5 kernel. In Proceedings of the 2003 USENIX Annual Technical Conference (FREENIX Track) (June 2003), USENIX Association, pp. 297--310.
• 2: Axboe, J. Re: {patch} cpufreq: mark cpufreq_tsc() as core_initcall_sync. Available: http://lkml.org/lkml/2006/11/17/56 {Viewed May 28, 2007}, November 2006.
• 3: Muli Ben-Yehuda , Eric Van Hensbergen, Open source as a foundation for systems research, ACM SIGOPS Operating Systems Review, v.42 n.1, January 2008 [doi>10.1145/1341312.1341315]
• 4: Corbet, J. Approaches to realtime Linux. Available: http://lwn.net/Articles/106010/ {Viewed March 25, 2008}, October 2004.
• 5: Corbet, J. Realtime preemption, part 2. Available: http://lwn.net/Articles/107269/ {Viewed March 25, 2008}, October 2004.
• 6: Corbet, J. Realtime preemption and read-copy-update. Available: http://lwn.net/Articles/129511/ {Viewed October 17, 2005}, March 2005.
• 7: Corbet, J. 2.6.24 - some statistics. Available: http://lwn.net/Articles/264440/ {Viewed March 25, 2008}, January 2008.
• 8: Desnoyers, M. Re: {patch 1/2} Linux kernel markers - support multiple probes. Available: http://lkml.org/lkml/2007/12/20/244 {Viewed March 27, 2008}, December 2007.
• 9: Ben Gamsa , Orran Krieger , Jonathan Appavoo , Michael Stumm, Tornado: maximizing locality and concurrency in a shared memory multiprocessor operating system, Proceedings of the third symposium on Operating systems design and implementation, p.87-100, February 1999, New Orleans, Louisiana, United States
• 10: Kourosh Gharachorloo, Memory Consistency Models for Shared-Memory Multiprocessors, Stanford University, Stanford, CA, 1995
• 11: Guniguntala, D., McKenney, P. E., Triplett, J., and Walpole, J. The read-copy-update mechanism for supporting real-time applications on shared-memory multiprocessor systems with Linux. IBM Systems Journal 47, 2 (May 2008), 221--236.
• 12: Thomas E. Hart , Paul E. McKenney , Angela Demke Brown , Jonathan Walpole, Performance of memory reclamation for lockless synchronization, Journal of Parallel and Distributed Computing, v.67 n.12, p.1270-1285, December, 2007 [doi>10.1016/j.jpdc.2007.04.010]
• 13: Hellwig, C. Re: {-mm PATCH 1/4} RCU: split classic rcu. Available: http://lkml.org/lkml/2006/9/28/160 {Viewed March 27, 2008}, September 2006.
• 14: Hennessy, J. P., Osisek, D. L., and Seigh II, J. W. Passive serialization in a multitasking environment. Tech. Rep. US Patent 4,809,168 (lapsed), US Patent and Trademark Office, Washington, DC, February 1989.
• 15: Houston, J. {RFC&PATCH} Alternative RCU implementation. Available: http://marc.theaimsgroup.com/?l=linux-kernel&m=109387402400673&w=2 {Viewed February 17, 2005}, August 2004.
• 16: Wilson C. Hsieh , William E. Weihl, Scalable Reader-Writer Locks for Parallel Systems, Proceedings of the 6th International Parallel Processing Symposium, p.656-659, March 01, 1992
• 17: Jacobson, V. Avoid read-side locking via delayed free. Verbal discussion, September 1993.
• 18: Aju John, Dynamic Vnodes - design and implementation, Proceedings of the USENIX 1995 Technical Conference Proceedings on USENIX 1995 Technical Conference Proceedings, p.2-2, January 16-20, 1995, New Orleans, Louisiana
• 19: H. T. Kung , Philip L. Lehman, Concurrent manipulation of binary search trees, ACM Transactions on Database Systems (TODS), v.5 n.3, p.354-382, Sept. 1980 [doi>10.1145/320613.320619]
• 20: Barbara Liskov, Distributed programming in Argus, Communications of the ACM, v.31 n.3, p.300-312, March 1988 [doi>10.1145/42392.42399]
• 21: Udi Manbar , Richard E. Ladner, Concurrency control in a dynamic search structure, ACM Transactions on Database Systems (TODS), v.9 n.3, p.439-455, Sept. 1984 [doi>10.1145/1270.318576]
• 22: McKenney, P. E. Stochastic fairness queuing. In IEEE INFOCOM'90 Proceedings (San Francisco, June 1990), The Institute of Electrical and Electronics Engineers, Inc., pp. 733--740.
• 23: Paul E. Mckenney , Jonathan Walpole, Exploiting deferred destruction: an analysis of read-copy-update techniques in operating system kernels, Oregon Health & Science University, 2004
• 24: McKenney, P. E. RCU vs. locking performance on different CPUs. In linux. conf. au (Adelaide, Australia, January 2004). Available: http://www.rdrop.com/users/paulmck/RCU/lockperf.2004.01.17a.pdf {Viewed June 23, 2004}.
• 25: Paul E. McKenney, Memory ordering in modern microprocessors, Part I, Linux Journal, v.2005 n.136, p.2, August 2005
• 26: McKenney, P. E. RCU Linux usage. Available: http://www.rdrop.com/users/paulmck/RCU/linuxusage.html {Viewed January 14, 2007}, October 2006.
• 27: McKenney, P. E. Sleepable RCU. Available: http://www.rdrop.com/users/paulmck/RCU/srcu.2007.01.14a.pdf {Viewed August 21, 2006}, October 2006.
• 28: McKenney, P. E. The design of preemptible read-copy-update. Available: http://lwn.net/Articles/253651/ {Viewed October 25, 2007}, October 2007.
• 29: McKenney, P. E. {PATCH} QRCU with lockless fastpath. Available: http://lkml.org/lkml/2007/2/25/18 {Viewed March 27, 2008}, February 2007.
• 30: McKenney, P. E. Priority-boosting RCU read-side critical sections. Available: http://www.rdrop.com/users/paulmck/RCU/RCUbooststate.2007.04.16a.pdf {Viewed September 7, 2007}, February 2007.
• 31: McKenney, P. E. RCU and unloadable modules. Available: http://lwn.net/Articles/217484/ {Viewed November 22, 2007}, January 2007.
• 32: McKenney, P. E. Using Promela and Spin to verify parallel algorithms. Available: http://lwn.net/Articles/243851/ {Viewed September 8, 2007}, August 2007.
• 33: McKenney, P. E. RCU part 3: the RCU API. Available: http://lwn.net/Articles/264090/ {Viewed January 10, 2008}, January 2008.
• 34: McKenney, P. E. What is RCU? part 2: Usage. Available: http://lwn.net/Articles/263130/ {Viewed January 4, 2008}, January 2008.
• 35: McKenney, P. E., Appavoo, J., Kleen, A., Krieger, O., Russell, R., Sarma, D., and Soni, M. Read-copy update. In Ottawa Linux Symposium (July 2001). Available: http://www.rdrop.com/users/paulmck/RCU/rclock_OLS.2001.05.01c.pdf {Viewed June 23, 2004}.
• 36: McKenney, P. E., and Sarma, D. Read-copy update mutual exclusion in Linux. Available: http://lse.sourceforge.net/locking/rcu/rcupdate_doc.html {Viewed October 18, 2004}, February 2001.
• 37: McKenney, P. E., and Sarma, D. Towards hard realtime response from the Linux kernel on SMP hardware. In linux.conf.au 2005 (Canberra, Australia, April 2005). Available: http://www.rdrop.com/users/paulmck/RCU/realtimeRCU.2005.04.23a.pdf {Viewed May 13, 2005}.
• 38: McKenney, P. E., Sarma, D., Arcangeli, A., Kleen, A., Krieger, O., and Russell, R. Read-copy update. In Ottawa Linux Symposium (June 2002), pp. 338--367. Available: http://www.linux.org.uk/~ajh/ols2002_proceedings.pdf.gz {Viewed June 23, 2004}.
• 39: McKenney, P. E., Sarma, D., Molnar, I., and Bhattacharya, S. Extending RCU for realtime and embedded workloads. In Ottawa Linux Symposium (July 2006), pp. v2 123--138. Available: http://www.linuxsymposium.org/2006/view_abstract.php?content_key=184 http://www.rdrop.com/users/paulmck/RCU/OLSrtRCU.2006.08.11a.pdf {Viewed January 1, 2007}.
• 40: McKenney, P. E., and Slingwine, J. D. Read-copy update: Using execution history to solve concurrency problems. In Parallel and Distributed Computing and Systems (Las Vegas, NV, October 1998), pp. 509--518. Available: http://www.rdrop.com/users/paulmck/RCU/rclockpdcsproof.pdf {Viewed December 3, 2007}.
• 41: McKenney, P. E., and Walpole, J. What is RCU, fundamentally? Available: http://lwn.net/Articles/262464/ {Viewed December 27, 2007}, December 2007.
• 42: Meuer, H., Dongarra, J., Strohmaier, E., and Simon, H. Top 500 supercomputer sites: Operating system family share. Available: http://www.top500.org/stats/list/30/osfam {Viewed March 25, 2008}, November 2007.
• 43: Minyard, C., and McKenney, P. E. {PATCH} add an RCU version of list splicing. Available: http://lkml.org/lkml/2007/1/3/112 {Viewed May 28, 2007}, January 2007.
• 44: Molnar, I., and Miller, D. S. brlock. Available: http://www.tm.kernel.org/pub/linux/kernel/v2.3/patch-html/patch-2.3.49/linux_include_linux_brlock.h.html {Viewed September 3, 2004}, March 2000.
• 45: Morris, J. Recent developments in SELinux kernel performance. Available: http://www.livejournal.com/users/james_morris/2153.html {Viewed December 10, 2004}, December 2004.
• 46: Nesterov, O. Re: {patch} cpufreq: mark cpufreq_tsc() as core_initcall_sync. Available: http://lkml.org/lkml/2006/11/19/69 {Viewed May 28, 2007}, November 2006.
• 47: Olsson, R., and Nilsson, S. TRASH: A dynamic LC-trie and hash data structure. Available: http://www.nada.kth.se/~snilsson/public/papers/trash/trash.pdf {Viewed February 24, 2007}, August 2006.
• 48: Piggin, N. {patch 3/3} radix-tree: RCU lockless readside. Available: http://lkml.org/lkml/2006/6/20/238 {Viewed March 25, 2008}, June 2006.
• 49: Pugh, W. Concurrent maintenance of skip lists. Tech. Rep. CS-TR-2222.1, Institute of Advanced Computer Science Studies, Department of Computer Science, University of Maryland, College Park, Maryland, June 1990.
• 50: Richard Rashid , Avadis Tevanian , Michael Young , David Golub , Robert Baron, Machine-independent virtual memory management for paged uniprocessor and multiprocessor architectures, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.31-39, October 1987, Palo Alto, California, United States
• 51: 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
• 52: Rostedt, S., and McKenney, P. E. {PATCH} add support for dynamic ticks and preempt rcu. Available: http://lkml.org/lkml/2008/1/29/208 {Viewed March 27, 2008}, January 2008.
• 53: Russell, R. Re: modular net drivers. Available: http://oss.sgi.com/projects/netdev/archive/2000-06/msg00250.html {Viewed April 10, 2006}, June 2000.
• 54: Dipankar Sarma , Paul E. McKenney, Making RCU safe for deep sub-millisecond response realtime applications, Proceedings of the annual conference on USENIX Annual Technical Conference, p.32-32, June 27-July 02, 2004, Boston, MA
• 55: Seigh, J. Lock-free synchronization primitives. Available: http://sourceforge.net/projects/atomic-ptr-plus/ {Viewed August 8, 2005}, July 2005.
• 56: Spraul, M. Re: RFC: patch to allow lock-free traversal of lists with insertion. Available: http://marc.theaimsgroup.com/?l=linux-kernel&m=100264675012867&w=2 {Viewed June 23, 2004}, October 2001.
• 57: Spraul, M. {rfc} 0/5 rcu lock update. Available: http://marc.theaimsgroup.com/?l=linux-kernel&m=108546407726602&w=2 {Viewed June 23, 2004}, May 2004.
• 58: Torvalds, L. Linux 2.5.43. Available: http://lkml.org/lkml/2002/10/15/425 {Viewed March 30, 2008}, October 2002.
• 59: Torvalds, L. Linux 2.5.69. Available: http://marc.theaimsgroup.com/?l=linux-kernel&m=105209603501299&w=2 {Viewed June 23, 2004}, May 2003.
• 60: Torvalds, L. Linux 2.5.70. Available: http://marc.theaimsgroup.com/?l=linux-kernel&m=105400162802746&w=2 {Viewed June 23, 2004}, May 2003.
• 61: Transaction Processing Performance Council. TPC benchmark A. Available: http://www.tpc.org/tpca/default.asp {Viewed July 6, 2007}, November 1989.
• 62: Zijlstra, P., and Molnar, I. {PATCH 3/7} barrier: a scalable synchonisation barrier. Available: http://lkml.org/lkml/2007/1/28/34 {Viewed March 27, 2008}, January 2007.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.0 General

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.m Miscellaneous

General Terms:
Design, Management, Theory