RTFP.txt 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449
  1. Read the F-ing Papers!
  2. This document describes RCU-related publications, and is followed by
  3. the corresponding bibtex entries. A number of the publications may
  4. be found at http://www.rdrop.com/users/paulmck/RCU/.
  5. The first thing resembling RCU was published in 1980, when Kung and Lehman
  6. [Kung80] recommended use of a garbage collector to defer destruction
  7. of nodes in a parallel binary search tree in order to simplify its
  8. implementation. This works well in environments that have garbage
  9. collectors, but current production garbage collectors incur significant
  10. read-side overhead.
  11. In 1982, Manber and Ladner [Manber82,Manber84] recommended deferring
  12. destruction until all threads running at that time have terminated, again
  13. for a parallel binary search tree. This approach works well in systems
  14. with short-lived threads, such as the K42 research operating system.
  15. However, Linux has long-lived tasks, so more is needed.
  16. In 1986, Hennessy, Osisek, and Seigh [Hennessy89] introduced passive
  17. serialization, which is an RCU-like mechanism that relies on the presence
  18. of "quiescent states" in the VM/XA hypervisor that are guaranteed not
  19. to be referencing the data structure. However, this mechanism was not
  20. optimized for modern computer systems, which is not surprising given
  21. that these overheads were not so expensive in the mid-80s. Nonetheless,
  22. passive serialization appears to be the first deferred-destruction
  23. mechanism to be used in production. Furthermore, the relevant patent has
  24. lapsed, so this approach may be used in non-GPL software, if desired.
  25. (In contrast, use of RCU is permitted only in software licensed under
  26. GPL. Sorry!!!)
  27. In 1990, Pugh [Pugh90] noted that explicitly tracking which threads
  28. were reading a given data structure permitted deferred free to operate
  29. in the presence of non-terminating threads. However, this explicit
  30. tracking imposes significant read-side overhead, which is undesirable
  31. in read-mostly situations. This algorithm does take pains to avoid
  32. write-side contention and parallelize the other write-side overheads by
  33. providing a fine-grained locking design, however, it would be interesting
  34. to see how much of the performance advantage reported in 1990 remains
  35. in 2004.
  36. At about this same time, Adams [Adams91] described ``chaotic relaxation'',
  37. where the normal barriers between successive iterations of convergent
  38. numerical algorithms are relaxed, so that iteration $n$ might use
  39. data from iteration $n-1$ or even $n-2$. This introduces error,
  40. which typically slows convergence and thus increases the number of
  41. iterations required. However, this increase is sometimes more than made
  42. up for by a reduction in the number of expensive barrier operations,
  43. which are otherwise required to synchronize the threads at the end
  44. of each iteration. Unfortunately, chaotic relaxation requires highly
  45. structured data, such as the matrices used in scientific programs, and
  46. is thus inapplicable to most data structures in operating-system kernels.
  47. In 1993, Jacobson [Jacobson93] verbally described what is perhaps the
  48. simplest deferred-free technique: simply waiting a fixed amount of time
  49. before freeing blocks awaiting deferred free. Jacobson did not describe
  50. any write-side changes he might have made in this work using SGI's Irix
  51. kernel. Aju John published a similar technique in 1995 [AjuJohn95].
  52. This works well if there is a well-defined upper bound on the length of
  53. time that reading threads can hold references, as there might well be in
  54. hard real-time systems. However, if this time is exceeded, perhaps due
  55. to preemption, excessive interrupts, or larger-than-anticipated load,
  56. memory corruption can ensue, with no reasonable means of diagnosis.
  57. Jacobson's technique is therefore inappropriate for use in production
  58. operating-system kernels, except when such kernels can provide hard
  59. real-time response guarantees for all operations.
  60. Also in 1995, Pu et al. [Pu95a] applied a technique similar to that of Pugh's
  61. read-side-tracking to permit replugging of algorithms within a commercial
  62. Unix operating system. However, this replugging permitted only a single
  63. reader at a time. The following year, this same group of researchers
  64. extended their technique to allow for multiple readers [Cowan96a].
  65. Their approach requires memory barriers (and thus pipeline stalls),
  66. but reduces memory latency, contention, and locking overheads.
  67. 1995 also saw the first publication of DYNIX/ptx's RCU mechanism
  68. [Slingwine95], which was optimized for modern CPU architectures,
  69. and was successfully applied to a number of situations within the
  70. DYNIX/ptx kernel. The corresponding conference paper appeared in 1998
  71. [McKenney98].
  72. In 1999, the Tornado and K42 groups described their "generations"
  73. mechanism, which quite similar to RCU [Gamsa99]. These operating systems
  74. made pervasive use of RCU in place of "existence locks", which greatly
  75. simplifies locking hierarchies.
  76. 2001 saw the first RCU presentation involving Linux [McKenney01a]
  77. at OLS. The resulting abundance of RCU patches was presented the
  78. following year [McKenney02a], and use of RCU in dcache was first
  79. described that same year [Linder02a].
  80. Also in 2002, Michael [Michael02b,Michael02a] presented "hazard-pointer"
  81. techniques that defer the destruction of data structures to simplify
  82. non-blocking synchronization (wait-free synchronization, lock-free
  83. synchronization, and obstruction-free synchronization are all examples of
  84. non-blocking synchronization). In particular, this technique eliminates
  85. locking, reduces contention, reduces memory latency for readers, and
  86. parallelizes pipeline stalls and memory latency for writers. However,
  87. these techniques still impose significant read-side overhead in the
  88. form of memory barriers. Researchers at Sun worked along similar lines
  89. in the same timeframe [HerlihyLM02,HerlihyLMS03]. These techniques
  90. can be thought of as inside-out reference counts, where the count is
  91. represented by the number of hazard pointers referencing a given data
  92. structure (rather than the more conventional counter field within the
  93. data structure itself).
  94. In 2003, the K42 group described how RCU could be used to create
  95. hot-pluggable implementations of operating-system functions. Later that
  96. year saw a paper describing an RCU implementation of System V IPC
  97. [Arcangeli03], and an introduction to RCU in Linux Journal [McKenney03a].
  98. 2004 has seen a Linux-Journal article on use of RCU in dcache
  99. [McKenney04a], a performance comparison of locking to RCU on several
  100. different CPUs [McKenney04b], a dissertation describing use of RCU in a
  101. number of operating-system kernels [PaulEdwardMcKenneyPhD], a paper
  102. describing how to make RCU safe for soft-realtime applications [Sarma04c],
  103. and a paper describing SELinux performance with RCU [JamesMorris04b].
  104. 2005 has seen further adaptation of RCU to realtime use, permitting
  105. preemption of RCU realtime critical sections [PaulMcKenney05a,
  106. PaulMcKenney05b].
  107. Bibtex Entries
  108. @article{Kung80
  109. ,author="H. T. Kung and Q. Lehman"
  110. ,title="Concurrent Maintenance of Binary Search Trees"
  111. ,Year="1980"
  112. ,Month="September"
  113. ,journal="ACM Transactions on Database Systems"
  114. ,volume="5"
  115. ,number="3"
  116. ,pages="354-382"
  117. }
  118. @techreport{Manber82
  119. ,author="Udi Manber and Richard E. Ladner"
  120. ,title="Concurrency Control in a Dynamic Search Structure"
  121. ,institution="Department of Computer Science, University of Washington"
  122. ,address="Seattle, Washington"
  123. ,year="1982"
  124. ,number="82-01-01"
  125. ,month="January"
  126. ,pages="28"
  127. }
  128. @article{Manber84
  129. ,author="Udi Manber and Richard E. Ladner"
  130. ,title="Concurrency Control in a Dynamic Search Structure"
  131. ,Year="1984"
  132. ,Month="September"
  133. ,journal="ACM Transactions on Database Systems"
  134. ,volume="9"
  135. ,number="3"
  136. ,pages="439-455"
  137. }
  138. @techreport{Hennessy89
  139. ,author="James P. Hennessy and Damian L. Osisek and Joseph W. {Seigh II}"
  140. ,title="Passive Serialization in a Multitasking Environment"
  141. ,institution="US Patent and Trademark Office"
  142. ,address="Washington, DC"
  143. ,year="1989"
  144. ,number="US Patent 4,809,168 (lapsed)"
  145. ,month="February"
  146. ,pages="11"
  147. }
  148. @techreport{Pugh90
  149. ,author="William Pugh"
  150. ,title="Concurrent Maintenance of Skip Lists"
  151. ,institution="Institute of Advanced Computer Science Studies, Department of Computer Science, University of Maryland"
  152. ,address="College Park, Maryland"
  153. ,year="1990"
  154. ,number="CS-TR-2222.1"
  155. ,month="June"
  156. }
  157. @Book{Adams91
  158. ,Author="Gregory R. Adams"
  159. ,title="Concurrent Programming, Principles, and Practices"
  160. ,Publisher="Benjamin Cummins"
  161. ,Year="1991"
  162. }
  163. @unpublished{Jacobson93
  164. ,author="Van Jacobson"
  165. ,title="Avoid Read-Side Locking Via Delayed Free"
  166. ,year="1993"
  167. ,month="September"
  168. ,note="Verbal discussion"
  169. }
  170. @Conference{AjuJohn95
  171. ,Author="Aju John"
  172. ,Title="Dynamic vnodes -- Design and Implementation"
  173. ,Booktitle="{USENIX Winter 1995}"
  174. ,Publisher="USENIX Association"
  175. ,Month="January"
  176. ,Year="1995"
  177. ,pages="11-23"
  178. ,Address="New Orleans, LA"
  179. }
  180. @techreport{Slingwine95
  181. ,author="John D. Slingwine and Paul E. McKenney"
  182. ,title="Apparatus and Method for Achieving Reduced Overhead Mutual
  183. Exclusion and Maintaining Coherency in a Multiprocessor System
  184. Utilizing Execution History and Thread Monitoring"
  185. ,institution="US Patent and Trademark Office"
  186. ,address="Washington, DC"
  187. ,year="1995"
  188. ,number="US Patent 5,442,758 (contributed under GPL)"
  189. ,month="August"
  190. }
  191. @techreport{Slingwine97
  192. ,author="John D. Slingwine and Paul E. McKenney"
  193. ,title="Method for maintaining data coherency using thread
  194. activity summaries in a multicomputer system"
  195. ,institution="US Patent and Trademark Office"
  196. ,address="Washington, DC"
  197. ,year="1997"
  198. ,number="US Patent 5,608,893 (contributed under GPL)"
  199. ,month="March"
  200. }
  201. @techreport{Slingwine98
  202. ,author="John D. Slingwine and Paul E. McKenney"
  203. ,title="Apparatus and method for achieving reduced overhead
  204. mutual exclusion and maintaining coherency in a multiprocessor
  205. system utilizing execution history and thread monitoring"
  206. ,institution="US Patent and Trademark Office"
  207. ,address="Washington, DC"
  208. ,year="1998"
  209. ,number="US Patent 5,727,209 (contributed under GPL)"
  210. ,month="March"
  211. }
  212. @Conference{McKenney98
  213. ,Author="Paul E. McKenney and John D. Slingwine"
  214. ,Title="Read-Copy Update: Using Execution History to Solve Concurrency
  215. Problems"
  216. ,Booktitle="{Parallel and Distributed Computing and Systems}"
  217. ,Month="October"
  218. ,Year="1998"
  219. ,pages="509-518"
  220. ,Address="Las Vegas, NV"
  221. }
  222. @Conference{Gamsa99
  223. ,Author="Ben Gamsa and Orran Krieger and Jonathan Appavoo and Michael Stumm"
  224. ,Title="Tornado: Maximizing Locality and Concurrency in a Shared Memory
  225. Multiprocessor Operating System"
  226. ,Booktitle="{Proceedings of the 3\textsuperscript{rd} Symposium on
  227. Operating System Design and Implementation}"
  228. ,Month="February"
  229. ,Year="1999"
  230. ,pages="87-100"
  231. ,Address="New Orleans, LA"
  232. }
  233. @techreport{Slingwine01
  234. ,author="John D. Slingwine and Paul E. McKenney"
  235. ,title="Apparatus and method for achieving reduced overhead
  236. mutual exclusion and maintaining coherency in a multiprocessor
  237. system utilizing execution history and thread monitoring"
  238. ,institution="US Patent and Trademark Office"
  239. ,address="Washington, DC"
  240. ,year="2001"
  241. ,number="US Patent 5,219,690 (contributed under GPL)"
  242. ,month="April"
  243. }
  244. @Conference{McKenney01a
  245. ,Author="Paul E. McKenney and Jonathan Appavoo and Andi Kleen and
  246. Orran Krieger and Rusty Russell and Dipankar Sarma and Maneesh Soni"
  247. ,Title="Read-Copy Update"
  248. ,Booktitle="{Ottawa Linux Symposium}"
  249. ,Month="July"
  250. ,Year="2001"
  251. ,note="Available:
  252. \url{http://www.linuxsymposium.org/2001/abstracts/readcopy.php}
  253. \url{http://www.rdrop.com/users/paulmck/rclock/rclock_OLS.2001.05.01c.pdf}
  254. [Viewed June 23, 2004]"
  255. annotation="
  256. Described RCU, and presented some patches implementing and using it in
  257. the Linux kernel.
  258. "
  259. }
  260. @Conference{Linder02a
  261. ,Author="Hanna Linder and Dipankar Sarma and Maneesh Soni"
  262. ,Title="Scalability of the Directory Entry Cache"
  263. ,Booktitle="{Ottawa Linux Symposium}"
  264. ,Month="June"
  265. ,Year="2002"
  266. ,pages="289-300"
  267. }
  268. @Conference{McKenney02a
  269. ,Author="Paul E. McKenney and Dipankar Sarma and
  270. Andrea Arcangeli and Andi Kleen and Orran Krieger and Rusty Russell"
  271. ,Title="Read-Copy Update"
  272. ,Booktitle="{Ottawa Linux Symposium}"
  273. ,Month="June"
  274. ,Year="2002"
  275. ,pages="338-367"
  276. ,note="Available:
  277. \url{http://www.linux.org.uk/~ajh/ols2002_proceedings.pdf.gz}
  278. [Viewed June 23, 2004]"
  279. }
  280. @article{Appavoo03a
  281. ,author="J. Appavoo and K. Hui and C. A. N. Soules and R. W. Wisniewski and
  282. D. M. {Da Silva} and O. Krieger and M. A. Auslander and D. J. Edelsohn and
  283. B. Gamsa and G. R. Ganger and P. McKenney and M. Ostrowski and
  284. B. Rosenburg and M. Stumm and J. Xenidis"
  285. ,title="Enabling Autonomic Behavior in Systems Software With Hot Swapping"
  286. ,Year="2003"
  287. ,Month="January"
  288. ,journal="IBM Systems Journal"
  289. ,volume="42"
  290. ,number="1"
  291. ,pages="60-76"
  292. }
  293. @Conference{Arcangeli03
  294. ,Author="Andrea Arcangeli and Mingming Cao and Paul E. McKenney and
  295. Dipankar Sarma"
  296. ,Title="Using Read-Copy Update Techniques for {System V IPC} in the
  297. {Linux} 2.5 Kernel"
  298. ,Booktitle="Proceedings of the 2003 USENIX Annual Technical Conference
  299. (FREENIX Track)"
  300. ,Publisher="USENIX Association"
  301. ,year="2003"
  302. ,month="June"
  303. ,pages="297-310"
  304. }
  305. @article{McKenney03a
  306. ,author="Paul E. McKenney"
  307. ,title="Using {RCU} in the {Linux} 2.5 Kernel"
  308. ,Year="2003"
  309. ,Month="October"
  310. ,journal="Linux Journal"
  311. ,volume="1"
  312. ,number="114"
  313. ,pages="18-26"
  314. }
  315. @techreport{Friedberg03a
  316. ,author="Stuart A. Friedberg"
  317. ,title="Lock-Free Wild Card Search Data Structure and Method"
  318. ,institution="US Patent and Trademark Office"
  319. ,address="Washington, DC"
  320. ,year="2003"
  321. ,number="US Patent 6,662,184 (contributed under GPL)"
  322. ,month="December"
  323. ,pages="112"
  324. }
  325. @article{McKenney04a
  326. ,author="Paul E. McKenney and Dipankar Sarma and Maneesh Soni"
  327. ,title="Scaling dcache with {RCU}"
  328. ,Year="2004"
  329. ,Month="January"
  330. ,journal="Linux Journal"
  331. ,volume="1"
  332. ,number="118"
  333. ,pages="38-46"
  334. }
  335. @Conference{McKenney04b
  336. ,Author="Paul E. McKenney"
  337. ,Title="{RCU} vs. Locking Performance on Different {CPUs}"
  338. ,Booktitle="{linux.conf.au}"
  339. ,Month="January"
  340. ,Year="2004"
  341. ,Address="Adelaide, Australia"
  342. ,note="Available:
  343. \url{http://www.linux.org.au/conf/2004/abstracts.html#90}
  344. \url{http://www.rdrop.com/users/paulmck/rclock/lockperf.2004.01.17a.pdf}
  345. [Viewed June 23, 2004]"
  346. }
  347. @phdthesis{PaulEdwardMcKenneyPhD
  348. ,author="Paul E. McKenney"
  349. ,title="Exploiting Deferred Destruction:
  350. An Analysis of Read-Copy-Update Techniques
  351. in Operating System Kernels"
  352. ,school="OGI School of Science and Engineering at
  353. Oregon Health and Sciences University"
  354. ,year="2004"
  355. ,note="Available:
  356. \url{http://www.rdrop.com/users/paulmck/RCU/RCUdissertation.2004.07.14e1.pdf}
  357. [Viewed October 15, 2004]"
  358. }
  359. @Conference{Sarma04c
  360. ,Author="Dipankar Sarma and Paul E. McKenney"
  361. ,Title="Making RCU Safe for Deep Sub-Millisecond Response Realtime Applications"
  362. ,Booktitle="Proceedings of the 2004 USENIX Annual Technical Conference
  363. (FREENIX Track)"
  364. ,Publisher="USENIX Association"
  365. ,year="2004"
  366. ,month="June"
  367. ,pages="182-191"
  368. }
  369. @unpublished{JamesMorris04b
  370. ,Author="James Morris"
  371. ,Title="Recent Developments in {SELinux} Kernel Performance"
  372. ,month="December"
  373. ,year="2004"
  374. ,note="Available:
  375. \url{http://www.livejournal.com/users/james_morris/2153.html}
  376. [Viewed December 10, 2004]"
  377. }
  378. @unpublished{PaulMcKenney05a
  379. ,Author="Paul E. McKenney"
  380. ,Title="{[RFC]} {RCU} and {CONFIG\_PREEMPT\_RT} progress"
  381. ,month="May"
  382. ,year="2005"
  383. ,note="Available:
  384. \url{http://lkml.org/lkml/2005/5/9/185}
  385. [Viewed May 13, 2005]"
  386. ,annotation="
  387. First publication of working lock-based deferred free patches
  388. for the CONFIG_PREEMPT_RT environment.
  389. "
  390. }
  391. @conference{PaulMcKenney05b
  392. ,Author="Paul E. McKenney and Dipankar Sarma"
  393. ,Title="Towards Hard Realtime Response from the Linux Kernel on SMP Hardware"
  394. ,Booktitle="linux.conf.au 2005"
  395. ,month="April"
  396. ,year="2005"
  397. ,address="Canberra, Australia"
  398. ,note="Available:
  399. \url{http://www.rdrop.com/users/paulmck/RCU/realtimeRCU.2005.04.23a.pdf}
  400. [Viewed May 13, 2005]"
  401. ,annotation="
  402. Realtime turns into making RCU yet more realtime friendly.
  403. "
  404. }