Powered by
2024 ACM SIGPLAN International Symposium on Memory Management (ISMM 2024),
June 25, 2024,
Copenhagen, Denmark
2024 ACM SIGPLAN International Symposium on Memory Management (ISMM 2024)
Frontmatter
Papers
SSRD: Shapes and Summaries for Race Detection in Concurrent Data Structures
Xiaofan Sun
and Rajiv Gupta
(University of California at Riverside, Riverside, USA)
Concolic testing combines concrete execution with symbolic execution to automatically generate test inputs that exercise different program paths and deliver high code coverage. This approach has been extended to multithreaded programs for exposing data races. Multithreaded programs frequently rely upon concurrent dynamic data structures whose implementations may contain data races that manifest only when certain dynamic data structure shapes, program paths, and thread interleavings are exercised. The lack of support for exploring different data structure shapes compromises the detection of races. This paper presents a summarization-guided approach for concolic testing capable of efficiently exploring different dynamic data structure shapes to expose data races. Via unit testing of key functions, function summaries are generated that capture data structure shapes that cause various function paths to be exercised. The shapes are captured in the form of pointer-pointee relations among symbolic pointers. By reusing function summaries during concolic testing, much of the overhead of handling symbolic pointers and dynamic objects in summarized functions is avoided. The summary also contains symbolic memory accesses and synchronization events that guide application-level concolic testing first to identify and then confirm potential data races. We demonstrate the efficiency and efficacy of our approach via experiments with multithreaded programs performing concurrent operations on four widely used dynamic data structures - Skip List, Unrolled Linked List, Priority Queue, and AVL Tree. It increases the number of races detected from 34 to 74 in total in comparison to Cloud9, and reduces both constraints solving time and number of constraints needed to be solved via summarization.
Article Search
Reference Counting Deeply Immutable Data Structures with Cycles: An Intellectual Abstract
Matthew J. Parkinson
, Sylvan Clebsch
, and Tobias Wrigstad
(Microsoft Azure Research, United Kingdom; Microsoft Azure Research, USA; Uppsala University, Sweden)
Immutable data structures are a powerful tool for building
concurrent programs. They allow the sharing of data without
the need for locks or other synchronisation mechanisms.
This makes it much easier to reason about the correctness
of the program.
In this paper, we focus on what we call deep immutability
from freeze, that is, objects are initially mutable, and then can
be frozen, and from that point on the object and everything
it refers to (transitively) can no longer be mutated. A key
challenge with this form of immutability is “how to
manage the memory of cyclic data structures?” The standard
approach is to use a garbage collector (GC), or a back-up
cycle detector. These approaches sacrifice the promptness
of memory reclamation, and the determinism of memory
usage.
In this paper, we argue that memory underlying an immutable
data structure can be efficiently managed using reference
counting even in the presence of cycles, based on the
observation that the cycles are themselves immutable. Our
approach takes a classic algorithm for calculating strongly
connected components (SCCs) and managing equivalence
classes with union-find (UF), and combines them so that the
liveness of each SCC can be tracked efficiently using only a
single reference counter. The key observation is that since
the graph is unchanging, we can calculate the SCCs once, in
time that is almost linear in the size of the graph, and then
use the result to reference count at the level of the SCCs. This
gives precise reachability information, and does not require
any backup mechanism to detect or handle cycles.
Article Search
Garbage Collection for Mostly Serialized Heaps
Chaitanya Sunil Koparkar, Vidush Singhal, Aditya Gupta, Mike Rainey
, Michael Vollmer, Artem Pelenitsyn, Sam Tobin-Hochstadt
,
Milind Kulkarni , and Ryan Rhodes Newton
(Indiana University, USA; Purdue University, USA; Carnegie Mellon University, USA; University of Kent, Canada)
Article Search
Evaluating Finalization-Based Object Lifetime Profiling
Sebastian Jordan Montaño
, Guillermo Polito
,
Stephane Ducasse , and Pablo Tesone
(Univ. Lille - Inria - CNRS - Centrale Lille - UMR 9189 CRIStAL, France)
Using object lifetime information enables performance improvement through memory optimizations such as pretenuring and tuning garbage collector parameters. However, profiling object lifetimes is nontrivial and often requires a specialized virtual machine to instrument object allocations and dereferences. Alternative lifetime profiling could be done with less implementation effort using available finalization mechanisms such as weak references.
In this paper, we study the impact of finalization on object lifetime profiling. We built an actionable lifetime profiler using the ephemeron finalization mechanism named FiLiP. FiLiP instruments object allocations to exactly record an object’s allocation time and it attaches an ephemeron to each allocated object to capture its finalization time. We show that FiLiP can be used in practice and achieves a significant overhead reduction by pretenuring the ephemeron objects. We further experiment with the impact of sampling object allocations, showing that sampling further reduces profiling overhead while still maintaining actionable lifetime measurements.
Article Search
proc time: 3.63