[PATCH 1/2] apitrace trim: Remove memory leak in FastCallRange objects
Lawrence L Love
lawrencex.l.love at intel.com
Wed Nov 6 01:35:40 CET 2013
A CallSet class contains a FastCallSet member containing a
FastCallRange member. A FastCallRange object allocates memory on
instantiation. Instances were seen where, given CallSets x and y,
"x = y" would occur with no accounting of the allocated memory of
the FastCallRange object (no destructor or overloaded assignment
and copy operators).
Using Valgrind with a 56.3MB trace file and the command
aptrace trim --calls=<TRIM CALLS> <trace file>
TRIM CALLS LEAKED BYTES
---------------- -----------------------
10 704 in 5 blocks
1-1700510/2 1690856 in 8589 blocks
Attempts to add a destructor and an assignment and copy operator did
not fix the problem. Testing in apitrace-tests showed some tests
failing. It turns out that pointers to FastCallRange objects are
held and referenced from multiple locations due to the implementation
for a skip list. If an object referencing a FastCallRange* went out
of scope or deleted it explicitly while another one was intending to
use it, the freed memory would be stale.
Another attempt was made to use std::shared_ptr but the required
"std=c++0x" compile option broke the build in other modules
(glretrace). Instead of modifying the build the option was made
to add a reference counting class for FastCallRange objects.
This is an implementation of a simple reference counting class
modified from an example given at
http://www.parashift.com/c++-faq/ref-count-simple.html
The FastCallRangePtr class is a friend class of FastCallRange.
It keeps track of the number of references for a given
FastCallRange* and when the FastCallRange* is no longer referenced
the FastCallRange object is automatically deleted.
All tests in apitrace-tests pass and the above examples with
different trim calls end up with 0 bytes leaked (with the
cli/cli_trim.cpp patch being submitted next)
This implentation gives FastCallSet access to its FastCallRange
pointers. Consequently operators "->" and "*" do not need to be
defined for the FastCallRangePtr reference counting class but does
so in order to minimize code change (note that std::shared_ptr also
gives access to the raw pointer).
If we want to hide the FastCallRange* pointer from FastCallSet, we
need to add an iterator that allows the address of a non-allocated
FastCallRange object (FastCallSet::head).
Signed-off-by: Lawrence L Love <lawrencex.l.love at intel.com>
---
common/trace_fast_callset.cpp | 53 ++++++++++++++++++++++---------------------
common/trace_fast_callset.hpp | 49 ++++++++++++++++++++++++++++++++++++++-
2 files changed, 75 insertions(+), 27 deletions(-)
diff --git a/common/trace_fast_callset.cpp b/common/trace_fast_callset.cpp
index 5aebfd2..2ac5343 100644
--- a/common/trace_fast_callset.cpp
+++ b/common/trace_fast_callset.cpp
@@ -30,6 +30,7 @@
#include <stdio.h>
#include <stdlib.h>
#include <limits>
+#include <vector>
#include "os.hpp"
#include "trace_fast_callset.hpp"
@@ -39,12 +40,13 @@ using namespace trace;
#define MAX_LEVEL 16
FastCallRange::FastCallRange(CallNo first, CallNo last, int level)
+: ref_counter(0)
{
this->first = first;
this->last = last;
this->level = level;
- next = new FastCallRange*[level];
+ next.resize(level, 0);
}
bool
@@ -64,9 +66,6 @@ FastCallSet::FastCallSet(): head(0, 0, MAX_LEVEL)
head.first = std::numeric_limits<CallNo>::max();
head.last = std::numeric_limits<CallNo>::min();
- for (int i = 0; i < MAX_LEVEL; i++)
- head.next[i] = NULL;
-
max_level = 0;
}
@@ -97,15 +96,17 @@ random_level (void)
void
FastCallSet::add(CallNo first, CallNo last)
{
- FastCallRange **update[MAX_LEVEL];
- FastCallRange *node, *next;
+ std::vector<FastCallRangePtr*> update (MAX_LEVEL);
+ FastCallRange *node;
+ FastCallRangePtr new_node;
int i, level;
- /* Find node immediately before insertion point. */
- node = &head;
+ /* Find node immediately before insertion point.
+ * NOTE: FastCallRangePtr(), e.g., next[i](), returns FastCallRange* */
+ node = &head; // Can't reference &head as a FastCallRangePtr
for (i = max_level - 1; i >= 0; i--) {
- while (node->next[i] && first > node->next[i]->last) {
- node = node->next[i];
+ while (node->next[i]() && first > node->next[i]->last) {
+ node = node->next[i]();
}
update[i] = &node->next[i];
}
@@ -113,13 +114,14 @@ FastCallSet::add(CallNo first, CallNo last)
/* Can we contain first by expanding tail of current range by 1? */
if (node != &head && node->last == first - 1) {
- node->last = last;
+ new_node = FastCallRangePtr(node);
+ new_node->last = last;
goto MERGE_NODE_WITH_SUBSEQUENT_COVERED_NODES;
}
/* Current range could not contain first, look at next. */
- node = node->next[0];
+ node = node->next[0]();
if (node) {
/* Do nothing if new range is already entirely contained. */
@@ -136,7 +138,8 @@ FastCallSet::add(CallNo first, CallNo last)
/* This is our candidate node if first is contained */
if (node->first <= first && node->last >= first) {
- node->last = last;
+ new_node = FastCallRangePtr(node);
+ new_node->last = last;
goto MERGE_NODE_WITH_SUBSEQUENT_COVERED_NODES;
}
}
@@ -152,21 +155,21 @@ FastCallSet::add(CallNo first, CallNo last)
max_level = level;
}
- node = new FastCallRange(first, last, level);
+ new_node = FastCallRangePtr(new FastCallRange(first, last, level));
/* Perform insertion into all lists. */
for (i = 0; i < level; i++) {
- node->next[i] = *update[i];
- *update[i] = node;
+ new_node->next[i] = *update[i];
+ *update[i] = new_node;
}
MERGE_NODE_WITH_SUBSEQUENT_COVERED_NODES:
- next = node->next[0];
- while (next && next->first <= node->last + 1) {
+ FastCallRangePtr next = new_node->next[0];
+ node = new_node();
+ while (next() && next->first <= node->last + 1) {
if (next->last > node->last)
node->last = next->last;
- /* Delete node 'next' */
for (i = 0; i < node->level && i < next->level; i++) {
node->next[i] = next->next[i];
}
@@ -175,8 +178,6 @@ MERGE_NODE_WITH_SUBSEQUENT_COVERED_NODES:
*update[i] = next->next[i];
}
- delete next;
-
next = node->next[0];
}
}
@@ -190,17 +191,17 @@ FastCallSet::add(CallNo call_no)
bool
FastCallSet::contains(CallNo call_no) const
{
- const FastCallRange *node;
+ FastCallRange *node;
int i;
- node = &head;
+ node = const_cast<FastCallRange*>(&head);
for (i = max_level - 1; i >= 0; i--) {
- while (node->next[i] && call_no > node->next[i]->last) {
- node = node->next[i];
+ while (node->next[i]() && call_no > node->next[i]->last) {
+ node = node->next[i]();
}
}
- node = node->next[0];
+ node = node->next[0]();
if (node == NULL)
return false;
diff --git a/common/trace_fast_callset.hpp b/common/trace_fast_callset.hpp
index af20005..4b27c7a 100644
--- a/common/trace_fast_callset.hpp
+++ b/common/trace_fast_callset.hpp
@@ -62,16 +62,63 @@ namespace trace {
* optimizations in some cases).
*/
+class FastCallRangePtr;
+
class FastCallRange {
public:
CallNo first;
CallNo last;
int level;
- FastCallRange **next;
+ std::vector<FastCallRangePtr> next;
+ // (NOTE: Initalize ref_counter to 0 in all constructors)
FastCallRange(CallNo first, CallNo last, int level);
bool contains(CallNo call_no) const;
+
+private:
+ friend class FastCallRangePtr;
+ size_t ref_counter;
+ // ref_counter must be initialized to 0 by all constructors
+ // ref_counter is the number of FastCallRangePtr objects that point at this
+};
+
+class FastCallRangePtr {
+public:
+ FastCallRange* operator-> () { return this->ptr; }
+ FastCallRange& operator * () { return *this->ptr; }
+ FastCallRange* operator ()() { return this->ptr; } // get pointer
+
+
+ FastCallRangePtr () : ptr(0) {}
+ FastCallRangePtr(FastCallRange* _ptr) : ptr(_ptr)
+ { if (this->ptr) ++this->ptr->ref_counter; }
+
+ ~FastCallRangePtr() { if (this->ptr)
+ if (--this->ptr->ref_counter == 0)
+ delete this->ptr;
+ }
+
+ FastCallRangePtr(FastCallRangePtr const& _ptr) : ptr(_ptr.ptr)
+ { if (this->ptr) ++this->ptr->ref_counter; }
+
+ FastCallRangePtr& operator= (FastCallRangePtr const& new_ptr)
+ { // DO NOT CHANGE THE ORDER OF THESE STATEMENTS!
+ // (This order properly handles self-assignment)
+ // (This order also properly handles recursion, e.g.,
+ // if a FastCallRange contains FastCallRangePtrs)
+ FastCallRange* const old_ptr = this->ptr;
+ this->ptr = new_ptr.ptr;
+ if (this->ptr)
+ ++this->ptr->ref_counter;
+ if (old_ptr) {
+ if (--old_ptr->ref_counter == 0)
+ delete old_ptr;
+ }
+ return *this;
+ }
+private:
+ FastCallRange* ptr;
};
class FastCallSet {
--
1.8.4.rc3
More information about the apitrace
mailing list