Heap Growth Detection in C++

Heap Growth Detection in C++

Heap Growth Detection in C++ GrowthTracker 1 Heap Growth Detection in C++ Motivation Scalable City needs to run continuously Many months without intervention/access Had slow growth of memory Caused crash after several weeks Available analysis tools reported no leaks! Software frees all memory correctly!

Had different kind of undetected memory issue 2 What is a Memory Leak? 3 What is a Memory Leak? Has become a broad term for memory mismanagement Definition depends on the programming language Does it have Garbage Collection? 4

What is a Memory Leak? C/C++ Programmers generally subscribe to traditional definition: Def. 1: A memory leak occurs iff all references to a region of memory are lost before the memory is freed. 5 What is a Memory Leak? Java/C# Programmers generally have a different definition: Def. 2: A memory leak occurs when a programs memory is unexpectedly growing.

Using Def. 1, Java/C# dont have memory leaks Garbage Collector frees memory that is no longer referenced 6 What is a Memory Leak? C/C++ Java/C# Def .2 Def .2 (unbounded growth)

(unbounded growth) Def .1 Def .1 (lost refs) (lost refs) 7 What is a Memory Leak? We need new terminology!

Java/C# programmers Concerned with unbounded memory growth, not leaks References exist to all memory growth Have clearer understanding of their problem C/C++ programmers Multiple definitions causes confusion False sense of security when tools report no memory leaks Unbounded memory growth may still exist! A term for unbounded memory growth not caused by memory leaks, would clearly parse the 2 problems 8

New Leak Terminology Properties of new term Unbounded Heap Growth Reference(s) retained Manifests as dynamically growing data structure Will eventually kill the process Doesnt fit leaky pipe metaphor Memory Tumor

Structure of cells that exhibits unbounded growth 9 Memory Tumor Example void main(){ queue q; while( key != ESC ) // exits when ESC key pressed q.push(0); } q will grow constantly while the program runs there are no memory leaks if the user hits ESC, all memory is freed when q goes out of scope 10

Leak vs. Tumor Leak Tumor heap heap X X X X X

11 Separation of Concerns C/C++/Java/C# Memory Tumor Memory Leak (Def 1: lost refs) 12 Current C++ Tumor Detection Tools

SWAT and Hound Only ones were aware of Both use Staleness detection Misses some tumors by design Memory can be accessed, but not needed Investigate at allocation level Dont need to modify source code Not open source or commercially available 13 Memory Tumor Detection Theory

Tumors Data Structures that grow without bound Healthy data structures Will grow Maximum size stabilizes 14 Memory Tumor Detection Challenges Detect all growth that doesnt stabilize Dont dismiss non-stale growth

Tests must exhibit the growth that exists in a programs implementation Support Multithreaded programs 15 Memory Tumor Detection Approach Growth Tracker Tool Container Tracking Keep references to all data structures in memory Growth Tracking Track data structure size changes over time Identify those with unbounded growth

Automated Test Cyclically execute all code paths (user created) 16 Growth Tracker Tool Container tracking CAT (Central Aggregate Tracker) Maintains references to all aggregates in the system Create wrappers for each aggregate type in system Templated constructors, multiple inheritance Add to CAT on construction, remove on destruction

Namespace replacement to enable wrappers Find and replace to apply new namespace Wrappers disabled with compile time flag Example: trak::std::vector 17 Growth Tracker Tool Growth Tracking Take periodic samples of the CAT Exponentially increasing interval sizes Reduces false positives & negatives over time Report growing aggregates at each sample 18

Growth Tracking Heuristic Take periodic samples of the CAT Two Interval Analysis 1st interval establishes aggregate age, gives time to stabilize 2nd interval proves stability, non-tumors shouldnt grow 2nd interval becomes the 1st for next more accurate test Exponentially increasing interval sizes Reduces false positives & negatives over time Monitor size maximums Reduces size fluctuation false positives At each interval report all aggregates that:

Increased their size maximum Have existed for two full intervals Prioritize results by size & reporting frequency 19 Growth Tracking Heuristic Two interval analysis A Data Structure Memory Footprint 1 2 Not reported

(growth stabilized) memory time 20 3 4 Diagnosing Unbounded Heap Growth in C++ Detection Approach

Two interval analysis 1 2 Reported as tumor (false positive) memory time 21

3 Not reported (growth stabilized) 4 Growth Tracking Heuristic Take periodic samples of the CAT Two Interval Analysis 1st interval establishes aggregate age, gives time to stabilize 2nd interval proves stability, non-tumors shouldnt grow 2nd interval becomes the 1st for next more accurate test Exponentially increasing interval sizes

Reduces false positives & negatives over time Monitor size maximums Reduces size fluctuation false positives At each interval report all aggregates that: Increased their size maximum Have existed for two full intervals Prioritize results by size & reporting frequency 22 Diagnosing Unbounded Heap Growth in C++ Detection Approach

Growth Tracking Exponentially increasing interval size In this example: constant intervals would not report growth half the time 1 2 4 3 memory time

23 Growth Tracking Heuristic Take periodic samples of the CAT Two Interval Analysis 1st interval establishes aggregate age, gives time to stabilize 2nd interval proves stability, non-tumors shouldnt grow 2nd interval becomes the 1st for next more accurate test Exponentially increasing interval sizes Reduces false positives & negatives over time Monitor size maximums Reduces size fluctuation false positives

At each interval report all aggregates that: Increased their size maximum Have existed for two full intervals Prioritize results by size & reporting frequency 24 Diagnosing Unbounded Heap Growth in C++ Detection Approach Growth Tracking Max size variable 1

2 Growth would be reported without max size 3 ceiling memory time 25

Growth Tracking Heuristic Take periodic samples of the CAT Two Interval Analysis 1st interval establishes aggregate age, gives time to stabilize 2nd interval proves stability, non-tumors shouldnt grow 2nd interval becomes the 1st for next more accurate test Exponentially increasing interval sizes Reduces false positives & negatives over time Monitor size maximums Reduces size fluctuation false positives At each interval report all aggregates that:

Increased their size maximum Have existed for two full intervals Prioritize results by size & reporting frequency 26 Growth Tracker Targets Multi-threaded Applications Initial CAT implementation works Requires locking for each aggregate constructor Potential to diminish multi-threaded performance Good starting point Need new CAT implementation Eliminate Locks

Multiple bucket approach Map aggregate construction from different threads to buckets Design can accelerate sampling process as well 27 Growth Tracker Drawbacks Source code modification Tracking requires compilation with our wrappers Allows consideration of Objects not just allocations. Limited information about identified tumors Full type string & allocation number Code location possible requires stack tracing (slower)

Reliance on the user Must identify custom data structures Must run feature complete and cyclic test 28 Growth Tracker Drawbacks Multi-threaded potential slow down Persistent buckets Example: Linear hash table with std::vector buckets More useful to include child bucket sizes in parents output and stop reporting individual children

Multiple instances of same tumor reported Parent report including children would resolve 29 Growth Tracker Results Scalable City Identified tumor Eliminated memory growth Ogre3D Rendering Engine Identified 2 tumors Our fix integrated into their code base Bullet Physics Engine

Tests revealed no tumors in Core 1 tumor found in demo framework 30 Growth Tracker Results Google Chrome / Chromium Identified 21 tumors Fixed the fastest growing tumor ourselves WebKit (Safari Browser, etc.) Identified 2 tumors Submitted fix to code base 31

Growth Tracker Paper Recently accepted for publication IEEE International Conference on Software Testing, Verification and Validation (ICST 2013) 32 Growth Tracker Proposed Work Resolve Multithreaded locking limitations Solution designed, needs implementation Reduce tracking of temporaries Detect stack-based data structures

Multi-layer CAT to separate entries by age Will reduce overhead of CAT insertion/removal 33 Growth Tracker Proposed Work Automation Reduce reliance on the user Detect custom data structures Automatically create wrappers when possible Improvements to code transformation process After initial code conversion, detect when wrapper is forgotten.

34 Growth Tracker Proposed Work Prioritize tracking parent data structures Would address persistent bucket problem Would reduce reports of multiple instances of same tumor Must identify relationships between data structures. 35

Recently Viewed Presentations

  • 9.2 Scratching The Surface

    9.2 Scratching The Surface

    Unit Overview. We are going to look at computer programming and how to create your very own computer game. The piece of software we will be using is called Scratch, it is completely free and available to download from:
  • Starter: 1. Suggest two more pieces of observational

    Starter: 1. Suggest two more pieces of observational

    Cost effective - Can be distributed to lots of people (= large amounts of data) and the researcher need not be present.. Easy to analyse . if fixed choice, closed questions are used (statistical analysis and comparisons) X Social desirability...
  • Cellular Encryption

    Cellular Encryption

    Times New Roman Wingdings Wingdings 3 Blue Diagonal Theorem Proving Semantic Tableaux Review of Symbolic Logic Review of Symbolic Logic (cont.) The Tableaux Method The Tableaux Method Propositional Logic Rules The Tableaux Method Propositional Logic Example The Tableaux Method Quantificational...
  • PowerPoint Templates - Peter Liljedahl

    PowerPoint Templates - Peter Liljedahl

    building thinking classrooms - Peter Liljedahl. Steinbach 2016. THINGS I (WE) TRIED. tasks. hints and extensions . how we give the problem. how we answer questions. how we level . room organization. how groups are formed. student work space.
  • Heroes in Literature

    Heroes in Literature

    Heroes in Literature And The Quests That Make Them Famous What is a hero? Two Types of Heroes Folktale Hero An ordinary person, lowly or abused No powers; they are generally very smart, kind, or resourceful.
  • Honeymoon in Greece

    Honeymoon in Greece

    CheapOair. Kayak. Adams 2/26/2019. Since Athens is the starting point, let's find hotels! Shown is . The Central Athens Hotel. with rates starting at $125. (All prices will be shown as the nightly rate on August 12th) Adams 2/26/2019. The...
  • Genesis 6The Days of Noah I. Why is

    Genesis 6The Days of Noah I. Why is

    It was 30 cubits high, 50 cubits wide and 300 cubits long. A cubit is approximately 18 inches or one half of a meter. b. It would be approximately 15 meters high, 25 meters wide and 150 meters long. 2....
  • Under Pressure: Work-related stress in academic libraries

    Under Pressure: Work-related stress in academic libraries

    Not everyone agree that libraries are stressful places to work. According to this editorial, written shortly after the Jobs Rated Almanac (St. Martin's Griffin) was published. This book ranked 250 careers by 6 factors: environment, income, outlook, physical demands, security,...