research-article

Open access

Project snowflake: non-blocking safe manual memory management in .NET

Authors:

Matthew Parkinson,

Dimitrios Vytiniotis,

Pantazis Deligiannis,

Dylan McDermott,

Aaron Blankstein,

Jonathan BalkindAuthors Info & Claims

Proceedings of the ACM on Programming Languages, Volume 1, Issue OOPSLA

Article No.: 95, Pages 1 - 25

https://doi.org/10.1145/3141879

Published: 12 October 2017 Publication History

Abstract

Garbage collection greatly improves programmer productivity and ensures memory safety. Manual memory management on the other hand often delivers better performance but is typically unsafe and can lead to system crashes or security vulnerabilities. We propose integrating safe manual memory management with garbage collection in the .NET runtime to get the best of both worlds. In our design, programmers can choose between allocating objects in the garbage collected heap or the manual heap. All existing applications run unmodified, and without any performance degradation, using the garbage collected heap.

Our programming model for manual memory management is flexible: although objects in the manual heap can have a single owning pointer, we allow deallocation at any program point and concurrent sharing of these objects amongst all the threads in the program. Experimental results from our .NET CoreCLR implementation on real-world applications show substantial performance gains especially in multithreaded scenarios: up to 3x savings in peak working sets and 2x improvements in runtime.

References

[1]

Periklis Akritidis. 2010. Cling: A Memory Allocator to Mitigate Dangling Pointers. In USENIX Security Symposium. 177–192.

[2]

Dan Alistarh, William M. Leiserson, Alexander Matveev, and Nir Shavit. 2015. ThreadScan: Automatic and Scalable Memory Reclamation. In SPAA.

[3]

ASP.Net. 2017. ASP.Net/Caching: Libraries for in-memory caching and distributed caching. https://github.com/aspnet/ Caching . (2017).

[4]

David F. Bacon, Clement R. Attanasio, Han B. Lee, V. T. Rajan, and Stephen Smith. 2001. Java Without the Coffee Breaks: A Nonintrusive Multiprocessor Garbage Collector. PLDI (2001).

Digital Library

[5]

David F. Bacon, Perry Cheng, and V.T. Rajan. 2003. The Metronome: A Simpler Approach to Garbage Collection in Real-time Systems. In In Workshop on Java Technologies for Real-Time and Embedded Systems (JTRES), OTM Workshops.

[6]

Henry G. Baker. 1995. Use-once variables and linear objects–storage management, reflection, and multi-threading. SIGPLAN Notices 30, 1 (January 1995), 45–52.

Digital Library

[7]

Oana Balmau, Rachid Guerraoui, Maurice Herlihy, and Igor Zablotchi. 2016. Fast and Robust Memory Reclamation for Concurrent Data Structures. In SPAA.

Digital Library

[8]

Emery D Berger and Benjamin G Zorn. 2006. DieHard: probabilistic memory safety for unsafe languages. In Acm sigplan notices, Vol. 41. ACM, 158–168.

[9]

S. M. Blackburn and K. S. McKinley. 2008. Immix: a mark-region garbage collector with space efficiency, fast collection, and mutator performance. In PLDI.

Digital Library

[10]

Burton H. Bloom. 1970. Space/Time Trade-offs in Hash Coding with Allowable Errors. Commun. ACM 13, 7 (1970).

Digital Library

[11]

Hans-Juergen Boehm and Mark Weiser. 1988. Garbage Collection in an uncooperative environment. Software – Practice and Experience 18, 9 (1988), 807–820.

Digital Library

[12]

Chandrasekhar Boyapati, Alexandru Salcianu, William Beebee, and Martin Rinard. 2003. Ownership types for safe regionbased memory management in real-time Java. In PLDI.

[13]

John Boyland. 2001. Alias burying: Unique variables without destructive reads. Software – Practice and Experience 31, 6 (2001), 533–553.

Digital Library

[14]

Trevor Alexander Brown. 2015. Reclaiming Memory for Lock-Free Data Structures: There Has to Be a Better Way. In PODC.

[15]

Perry Cheng, Robert Harper, and Peter Lee. 1998. Generational Stack Collection and Profile-driven Pretenuring. In Proceedings of the ACM SIGPLAN 1998 Conference on Programming Language Design and Implementation (PLDI ’98). ACM, New York, NY, USA, 162–173.

Digital Library

[16]

Dave Clarke and Tobias Wrigstad. 2003. External uniqueness is unique enough. In ECOOP. 176–200.

[17]

David G. Clarke, John M. Potter, and James Noble. 1998. Ownership types for flexible alias protection. In OOPSLA.

Digital Library

[18]

Daniel Clifford, Hannes Payer, Michael Stanton, and Ben L. Titzer. 2015. Memento Mori: Dynamic Allocation-site-based Optimizations. In Proceedings of the 2015 International Symposium on Memory Management (ISMM ’15). ACM, New York, NY, USA, 105–117.

Digital Library

[19]

Nachshon Cohen and Erez Petrank. 2015a. Automatic memory reclamation for lock-free data structures. In OOPSLA.

Digital Library

[20]

Nachshon Cohen and Erez Petrank. 2015b. Efficient Memory Management for Lock-Free Data Structures with Optimistic Access. In SPAA.

Digital Library

[21]

CoreCLR. 2017. CoreCLR: the .NET Core runtime. http://www.github.com/dotnet/CoreCLR . (2017).

[22]

Ulan Degenbaev, Jochen Eisinger, Manfred Ernst, Ross McIlroy, and Hannes Payer. 2016. Idle Time Garbage Collection Scheduling. In PLDI.

Digital Library

[23]

Dinakar Dhurjati and Vikram Adve. 2006. Efficiently Detecting All Dangling Pointer Uses in Production Servers. In DSN.

Digital Library

[24]

Dinakar Dhurjati, Sumant Kowshik, Vikram Adve, and Chris Lattner. 2003. Memory safety without runtime checks or garbage collection. ACM SIGPLAN Notices 38, 7 (2003), 69–80.

Digital Library

[25]

Dave Dice, Maurice Herlihy, and Alex Kogan. 2016. Fast non-intrusive memory reclamation for highly-concurrent data structures. In ISMM.

Digital Library

[26]

Keir Fraser. 2004. Practical lock-freedom. PhD Thesis UCAM-CL-TR-579. Computer Laboratory, University of Cambridge.

[27]

Lokesh Gidra, Gaël Thomas, Julien Sopena, Marc Shapiro, and Nhan Nguyen. 2015. NumaGiC: a garbage collector for big data on big NUMA machines. In ASPLOS.

Digital Library

[28]

Ionel Gog, Jana Giceva, Malte Schwarzkopf, Kapil Vaswani, Dimitrios Vytiniotis, Ganesan Ramalingam, Manuel Costa, Derek Gordon Murray, Steven Hand, and Michael Isard. 2015. Broom: Sweeping Out Garbage Collection from Big Data Systems. In HotOS.

[29]

Dan Grossman, Greg Morrisett, and Trevor Jim. 2002. Region-based Memory Management in Cyclone. In PLDI.

Digital Library

[30]

Timothy L. Harris. 2000. Dynamic Adaptive Pre-tenuring. In Proceedings of the 2Nd International Symposium on Memory Management (ISMM ’00). ACM, New York, NY, USA, 127–136.

Digital Library

[31]

Timothy L. Harris. 2001. A Pragmatic Implementation of Non-blocking Linked-Lists. In DISC.

[32]

Thomas E. Hart, Paul E. McKenney, Angela Demke Brown, and Jonathan Walpole. 2007. Performance of memory reclamation for lockless synchronization. Journal of Parallel and Distributed Computing 67 (May 2007), 1270–1285.

Digital Library

[33]

Matthew Hertz and Emery D. Berger. 2005. Quantifyng the Performance of Garbage Collection vs. Explicit Memory Management. In OOPSLA.

[34]

Michael Hicks, Greg Morrisett, Dan Grossman, and Trevor Jim. 2004. Experience With Safe Manual Memory-Management in Cyclone. In ISMM.

Digital Library

[35]

John Hogg. 1991. Islands: Aliasing protection in object-oriented languages. In OOPSLA.

[36]

Robert Hundt. 2011. Loop Recognition in C++/Java/Go/Scala. In Proceedings of Scala Days 2011.

[37]

Richard Jones, Antony Hosking, and Eliot Moss. 2011. The Garbage Collection Handbook: The Art of Automatic Memory Management (1st ed.). Chapman & Hall/CRC.

[38]

Piyus Kedia, Manuel Costa, Matthew Parkinson, Kapil Vaswani, and Dimitrios Vytiniotis. 2017. Simple, fast and safe manual memory management. In PLDI.

Digital Library

[39]

Byoungyoung Lee, Chengyu Song, Yeongjin Jang, and Tielei Wang. 2015. Preventing Use-after-free with Dangling Pointer Nullification. In NDSS.

[40]

Vitaliy B. Lvin, Gene Novark, Emery D. Berger, and Benjamin G. Zorn. 2008. Archipelago: trading address space for reliability and security. In ASPLOS.

Digital Library

[41]

Martin Maas, Krste Asanović, Tim Harris, and John Kubiatowicz. 2016. Taurus: A Holistic Language Runtime System for Coordinating Distributed Managed-Language Applications. In ASPLOS.

Digital Library

[42]

Maged M. Michael. 2004. Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects. IEEE Transactions on Parallel and Distributed Systems 15, 6 (June 2004), 491–504.

Digital Library

[43]

T. Minka, J.M. Winn, J.P. Guiver, S. Webster, Y. Zaykov, B. Yangel, A. Spengler, and J. Bronskill. 2014. Infer.NET 2.6. (2014). Microsoft Research Cambridge. http://research.microsoft.com/infernet.

[44]

Naftaly Minsky. 1996. Towards alias-free pointers. In ECOOP. 189–209.

[45]

Adam Morrison and Yehuda Afek. 2015. Temporally Bounding TSO for Fence-Free Asymmetric Synchronization. In ASPLOS.

Digital Library

[46]

MSDN. 2016. Asynchronous Programming with async and await. https://msdn.microsoft.com/en-us/library/mt674882.aspx . (2016).

[47]

Karl Naden, Robert Bocchino, Jonathan Aldrich, and Kevin Bierhoff. 2012. A Type System for Borrowing Permissions. In POPL.

Digital Library

[48]

Santosh Nagarakatte, Jianzhou Zhao, Milo M. K. Martin, and Steve Zdancewic. 2010. CETS Compiler-Enforced Temporal Safety for C. In ISMM.

[49]

Khan Nguyen, Lu Fang, Guoqing Xu, Brian Demsky, Shan Lu, Sanazsadat Alamian, and Onur Mutlu. 2016. Yak: A High Performance Big-Data-Friendly Garbage Collector. In OSDI.

[50]

Khanh Nguyen, Kai Wang, Yingyi Bu, Lu Fang, Jianfei Hu, and Guoqing Xu. 2015. FACADE: A Compiler and Runtime for (Almost) Object-Bounded Big Data Applications. In ASPLOS.

Digital Library

[51]

Gene Novark and Emery D Berger. 2010. DieHarder: securing the heap. In Proceedings of the 17th ACM conference on Computer and communications security. ACM, 573–584.

Digital Library

[52]

Matthew Parkinson, Dimitrios Vytiniotis, Kapil Vaswani, Manuel Costa, Pantazis Deligiannis, Dylan McDermott, Aaron Blankstein, and Jonathan Balkind. 2017. Project Snowflake: Safe Manual Memory Management in .NET. Technical Report MSR-TR-2017-32. Microsoft Research. https://www.microsoft.com/en-us/research/wp-content/uploads/2017/07/ snowflake-extended.pdf

[53]

Fred Smith, David Walker, and Greg Morrisett. 2000. Alias types. In European Symposium on Programming (ESOP).

[54]

Codruţ Stancu, Christian Wimmer, Stefan Brunthaler, Per Larsen, and Michael Franz. 2015. Safe and Efficient Hybrid Memory Management for Java. In ISMM.

Digital Library

[55]

D. Stefanovic, K. S. McKinley, and J. E. B. Moss. 1999. Age-based garbage collection. In OOPSLA.

Digital Library

[56]

Nikhil Swamy, Michael Hicks, Greg Morrisett, Dan Grossman, and Trevor Jim. 2006. Safe Manual Memory-Management in Cyclone. Science of Computer Programming 62, 2 (October 2006), 122–14.

Digital Library

[57]

Gil Tene, Balaji Iyengar, and Michael Wolk. 2011. C4: The Continuously Conucrrent Compacting Collector. In ISMM.

Digital Library

[58]

Mads Tofte and Jean-Pierre Talpin. 1997. Region-based memory management. Information and Computation 132, 2 (February 1997), 109–176.

Digital Library

[59]

TPC.org. 2017. The TPC Benchmark T M H. http://www.tpc.org/tpch . (2017).

[60]

Philip Wadler. 1990. Linear types can change the world!. In IFIP TC 2 Working Conference.

[61]

David Walker, Karl Crary, and Greg Morrisett. 2000. Typed memory management in a calculus of capabilities. ACM Transactions on Programming Languages and Systems 24, 4 (2000), 701–771.

Digital Library

[62]

David Walker and Kevin Watkins. 2001. On regions and linear types. In ICFP.

[63]

Yves Younan. 2015. FreeSentry: protecting Against User-After-Free Vulnerabilities Due to Dangling Pointers. In NDSS.

[64]

B. G. Zorn. 1993. The measured cost of conservative garbage collection. Software – Practice and Experience 23, 7 (1993), 733–756.

Digital Library

Cited By

Jung JKim JParkinson MKang J(2024)Concurrent Immediate Reference CountingProceedings of the ACM on Programming Languages10.1145/36563838:PLDI(151-174)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656383
Solomon DMorrison ALee JPetrank E(2021)Efficiently reclaiming memory in concurrent search data structures while bounding wasted memoryProceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3437801.3441582(191-204)Online publication date: 17-Feb-2021
https://dl.acm.org/doi/10.1145/3437801.3441582
Попова Е(2020)Investigation of the Dispose-Pattern Algorithm in Making Memory Management Decisions in the .NET Client-Component ModelМОДЕЛИРОВАНИЕ, ОПТИМИЗАЦИЯ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ10.26102/2310-6018/2020.30.3.0138:3(30)(13-14)Online publication date: 19-Sep-2020
https://doi.org/10.26102/2310-6018/2020.30.3.013
Show More Cited By

Index Terms

Project snowflake: non-blocking safe manual memory management in .NET
1. Computing methodologies
  1. Concurrent computing methodologies
    1. Concurrent algorithms
    2. Concurrent programming languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Object oriented languages
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Garbage collection

Recommendations

Safe manual memory management
ISMM '07: Proceedings of the 6th international symposium on Memory management

We present HeapSafe, a tool that uses reference counting to dynamically verify the soundness of manual memory management of C programs. HeapSafe relies on asimple extension to the usual malloc/free memory management API: delayed free scopes during which ...
A generational on-the-fly garbage collector for Java
PLDI '00: Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation

An on-the-fly garbage collector does not stop the program threads to perform the collection. Instead, the collector executes in a separate thread (or process) in parallel to the program. On-the-fly collectors are useful for multi-threaded applications ...
Controlling garbage collection and heap growth to reduce the execution time of Java applications

In systems that support garbage collection, a tension exists between collecting garbage too frequently and not collecting it frequently enough. Garbage collection that occurs too frequently may introduce unnecessary overheads at the risk of not ...

Comments

Information & Contributors

Information

Published In

cover image Proceedings of the ACM on Programming Languages

Proceedings of the ACM on Programming Languages Volume 1, Issue OOPSLA

October 2017

1786 pages

EISSN:2475-1421

DOI:10.1145/3152284

Issue’s Table of Contents

Copyright © 2017 Owner/Author.

This work is licensed under a Creative Commons Attribution-NoDerivatives International 4.0 License.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 October 2017

Published in PACMPL Volume 1, Issue OOPSLA

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
852
Total Downloads

Downloads (Last 12 months)143
Downloads (Last 6 weeks)27

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jung JKim JParkinson MKang J(2024)Concurrent Immediate Reference CountingProceedings of the ACM on Programming Languages10.1145/36563838:PLDI(151-174)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656383
Solomon DMorrison ALee JPetrank E(2021)Efficiently reclaiming memory in concurrent search data structures while bounding wasted memoryProceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3437801.3441582(191-204)Online publication date: 17-Feb-2021
https://dl.acm.org/doi/10.1145/3437801.3441582
Попова Е(2020)Investigation of the Dispose-Pattern Algorithm in Making Memory Management Decisions in the .NET Client-Component ModelМОДЕЛИРОВАНИЕ, ОПТИМИЗАЦИЯ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ10.26102/2310-6018/2020.30.3.0138:3(30)(13-14)Online publication date: 19-Sep-2020
https://doi.org/10.26102/2310-6018/2020.30.3.013
Kang JJung JDonaldson ATorlak E(2020)A marriage of pointer- and epoch-based reclamationProceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3385412.3385978(314-328)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3385412.3385978
Wesley Filardo NGutstein BWoodruff JAinsworth SPaul-Trifu LDavis BXia HTomasz Napierala ERichardson ABaldwin JChisnall DClarke JGudka KJoannou ATheodore Markettos AMazzinghi ANorton RRoe MSewell PSon SJones TMoore SNeumann PWatson R(2020)Cornucopia: Temporal Safety for CHERI Heaps2020 IEEE Symposium on Security and Privacy (SP)10.1109/SP40000.2020.00098(608-625)Online publication date: May-2020
https://doi.org/10.1109/SP40000.2020.00098
Psaroudakis IKaestle SGrimmer MGoodman DLozi JHarris TOliveira RFelber PHu Y(2018)Analytics with smart arraysProceedings of the Thirteenth EuroSys Conference10.1145/3190508.3190514(1-15)Online publication date: 23-Apr-2018
https://dl.acm.org/doi/10.1145/3190508.3190514

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents