[insight-vmi] r1997 committed - * Probabilities are now positive, sire!...

[insig...@googlecode.com]

Revision: 1997
Author: vo...@in.tum.de
Date: Mon Jun 24 10:25:15 2013
Log: * Probabilities are now positive, sire!
* Memorymap now stores function pointers in an own structure (This
structure is so far untested!)

http://code.google.com/p/insight-vmi/source/detail?r=1997

Modified:
/trunk/libinsight/include/insight/instance_def.h
/trunk/libinsight/include/insight/memorymap.h
/trunk/libinsight/include/insight/memorymapbuildercs.h
/trunk/libinsight/memorymapbuildercs.cpp

=======================================
--- /trunk/libinsight/include/insight/instance_def.h Tue Jan 29 08:01:53
2013
+++ /trunk/libinsight/include/insight/instance_def.h Mon Jun 24 10:25:15
2013
@@ -469,6 +469,31 @@
int maxPtrDeref = -1, KnowledgeSources src = ksAll,
int *result = 0) const;

+ /**
+ * Retrieves a member of this Instance based on a provided MemberList.
+ * If this Instance is not a structure or union or if the member cannot
+ * be resolved based on the provided list, a default Instance is
returned.
+ *
+ * \note Make sure to check Instance::isNull() on the returned object
to
+ * see if it is valid or not.
+ *
+ * @param members the memberlist that defines the location of the
member
+ * one wants to retrieve
+ * @param resolveTypes which types to automatically resolve, see
+ * BaseType::TypeResolution
+ * @param maxPtrDeref the maximum levels of pointers that should be
+ * dereferenced
+ * @param src selects which sources of knowledge to use when accessing
+ * members
+ * @param result provides the result of the knowledge source
evaluation,
+ * see TypeRuleEngine::MatchResult
+ * @return Instance object of the specified member
+ * \sa BaseType::TypeResolution, KnowledgeSources
+ */
+ Instance member(const ConstMemberList& members, int resolveTypes,
+ int maxPtrDeref, KnowledgeSources src = ksAll,
+ int *result = 0) const;
+
/**
* Obtain the member of this instance that has the given offset
provided that
* this instance is a structure. If \a exactMatch is true the function
will only
@@ -1033,9 +1058,6 @@

void setListNext(const Instance& inst);

- Instance member(const ConstMemberList& members, int resolveTypes,
- int maxPtrDeref, KnowledgeSources src = ksAll,
- int *result = 0) const;

Instance *typeRuleMatchRek(ConstMemberList &members, int *match) const;

=======================================
--- /trunk/libinsight/include/insight/memorymap.h Mon Mar 11 10:27:40 2013
+++ /trunk/libinsight/include/insight/memorymap.h Mon Jun 24 10:25:15 2013
@@ -56,7 +56,6 @@
/// Holds the nodes to be visited, sorted by their probability
typedef PriorityQueue<float, MemoryMapNode*> NodeQueue;

-
#define MAX_BUILDER_THREADS 8

/**
@@ -91,6 +90,7 @@
MemoryMapNode* lastNode;
qint64 processed;
QMutex queueLock;
+ QMutex functionPointersLock;
QReadWriteLock pmemMapLock, vmemMapLock, currAddressesLock,
typeInstancesLock, pointersToLock;

@@ -105,6 +105,24 @@
#endif
};

+/**
+ * Holds information about all function pointers contained
+ * within a specific \sa MemoryMapNode.
+ */
+struct FuncPointersInNode
+{
+ FuncPointersInNode() : node(0) {}
+ FuncPointersInNode(MemoryMapNode *node, ConstMemberList *path) :
+ node(node)
+ {
+ if (path)
+ funcPointers.append((*path));
+ }
+
+ MemoryMapNode *node;
+ QList<ConstMemberList> funcPointers;
+};
+

/**
* This class represents a map of used virtual and physical memory. It
allows
@@ -240,6 +258,15 @@
*/
const PointerNodeHash& pointersTo() const;

+ /**
+ * This data structure allows to access all function pointers that are
+ * contained within the map.
+ * @return a list of FuncPointersInNode structures that contain the
+ * MemoryMapNode as well as a list of MemberLists that can be used to
+ * retrieve the individual function pointers.
+ */
+ const QList<FuncPointersInNode> & funcPointers() const;
+
/**
* This property indicates whether the memory map is currently being
built.
* @return \c true if the build process is in progress, \c false
otherwise
@@ -391,6 +418,7 @@
VirtualMemory* _vmem; ///< the virtual memory object this map
is being built for
NodeList _roots; ///< the nodes of the global kernel variables
PointerNodeHash _pointersTo; ///< holds all pointers that point to a
certain address
+ QList<FuncPointersInNode> _funcPointers; ///< holds all function
pointers
IntNodeHash _typeInstances; ///< holds all instances of a given type
ID
MemoryMapRangeTree _vmemMap; ///< map of all used kernel-space virtual
memory
PhysMemoryMapRangeTree _pmemMap; ///< map of all used physical memory
@@ -453,6 +481,10 @@
return _pointersTo;
}

+inline const QList<FuncPointersInNode> & MemoryMap::funcPointers() const
+{
+ return _funcPointers;
+}

inline bool MemoryMap::isBuilding() const
{
=======================================
--- /trunk/libinsight/include/insight/memorymapbuildercs.h Fri Feb 1
10:51:35 2013
+++ /trunk/libinsight/include/insight/memorymapbuildercs.h Mon Jun 24
10:25:15 2013
@@ -9,6 +9,7 @@
#define MEMORYMAPBUILDERCS_H_

#include "memorymapbuilder.h"
+#include "memberlist.h"

// Forward declaration
class Instance;
@@ -43,16 +44,19 @@

void processNode(MemoryMapNode* node);
void processInstance(const Instance &inst, MemoryMapNode* node,
- bool isNested = false);
+ ConstMemberList *path = 0);
void processInstanceFromRule(const Instance &parent, const Instance&
member,
- int mbrIdx, MemoryMapNode* node);
+ int mbrIdx, MemoryMapNode* node,
ConstMemberList *path);
void processPointer(const Instance &inst, MemoryMapNode* node);
- void processArray(const Instance& inst, MemoryMapNode* node);
+ void processFunctionPointer(const Instance &inst, MemoryMapNode *node,
+ ConstMemberList *path);
+ void processArray(const Instance& inst, MemoryMapNode* node,
+ ConstMemberList *path);
void processStructured(const Instance &inst, MemoryMapNode* node,
- bool isNested = false);
+ ConstMemberList *path);

private:
- void addMembers(const Instance &inst, MemoryMapNode* node);
+ void addMembers(const Instance &inst, MemoryMapNode* node,
ConstMemberList *path);
static int countInvalidChildren(const Instance &inst, int *total);
static int countInvalidChildrenRek(const Instance &inst, int *total,
int *userlandPtrs);
=======================================
--- /trunk/libinsight/memorymapbuildercs.cpp Mon Mar 4 08:56:42 2013
+++ /trunk/libinsight/memorymapbuildercs.cpp Mon Jun 24 10:25:15 2013
@@ -115,12 +115,13 @@

// Create an instance from the node
Instance inst(node->toInstance(false));
+
processInstance(inst, node);
}


void MemoryMapBuilderCS::processInstance(const Instance &inst,
MemoryMapNode *node,
- bool isNested)
+ ConstMemberList *path)
{
// Ignore user-land objects
if (inst.address() < _map->_vmem->memSpecs().pageOffset)
@@ -131,18 +132,57 @@
return;

try {
- if (inst.type()->type() & rtPointer)
+ if (MemoryMapHeuristics::isFunctionPointer(inst))
+ processFunctionPointer(inst, node, path);
+ else if (inst.type()->type() & rtPointer)
processPointer(inst, node);
else if (inst.type()->type() & rtArray)
- processArray(inst, node);
+ processArray(inst, node, path);
else if (inst.type()->type() & StructOrUnion)
- processStructured(inst, node, isNested);
+ processStructured(inst, node, path);
}
catch (GenericException&) {
// Do nothing
}
}

+void MemoryMapBuilderCS::processFunctionPointer(const Instance &inst,
+ MemoryMapNode *node,
+ ConstMemberList *path)
+{
+ assert(node);
+
+ if (path)
+ path->append((const StructuredMember *)inst.type());
+ else {
+ _map->_shared->functionPointersLock.lock();
+ _map->_funcPointers.append(FuncPointersInNode(node, path));
+ _map->_shared->functionPointersLock.unlock();
+ return;
+ }
+
+ _map->_shared->functionPointersLock.lock();
+ if (_map->_funcPointers.size() == 0) {
+ _map->_funcPointers.append(FuncPointersInNode(node, path));
+ }
+ else {
+ // Check if the MemoryMapNode is already within the list
+ int position = -1;
+
+ for (int j = 0; j < _map->_funcPointers.size(); ++j) {
+ if (_map->_funcPointers[j].node == node) {
+ position = j;
+ break;
+ }
+ }
+
+ if (position != -1)
+ _map->_funcPointers[position].funcPointers.append((*path));
+ else
+ _map->_funcPointers.append(FuncPointersInNode(node, path));
+ }
+ _map->_shared->functionPointersLock.unlock();
+}

void MemoryMapBuilderCS::processPointer(const Instance& inst,
MemoryMapNode *node)
{
@@ -168,7 +208,8 @@



-void MemoryMapBuilderCS::processArray(const Instance& inst, MemoryMapNode
*node)
+void MemoryMapBuilderCS::processArray(const Instance& inst, MemoryMapNode
*node,
+ ConstMemberList *path)
{
assert(inst.type()->type() == rtArray);

@@ -177,26 +218,36 @@
for (int i = 0; i < len; ++i) {
Instance e(inst.arrayElem(i).dereference(BaseType::trLexical));
// Pass the "nested" flag to all elements of this array
- processInstance(e, node, true);
+ processInstance(e, node, path);
}
}


void MemoryMapBuilderCS::processStructured(const Instance& inst,
- MemoryMapNode *node, bool
isNested)
+ MemoryMapNode *node,
+ ConstMemberList *path)
{
assert(inst.type()->type() & StructOrUnion);

// Ignore non-nested structs/unions that are not aligned at a four-byte
// boundary
- if (!isNested && (inst.address() & 0x3ULL))
+ if (!path && (inst.address() & 0x3ULL))
return;

- addMembers(inst, node);
+ if (!path) {
+ ConstMemberList p;
+ addMembers(inst, node, &p);
+ }
+ else {
+ ConstMemberList p((*path));
+ p.append((const StructuredMember *)inst.type());
+ addMembers(inst, node, &p);
+ }
}


-void MemoryMapBuilderCS::addMembers(const Instance &inst, MemoryMapNode*
node)
+void MemoryMapBuilderCS::addMembers(const Instance &inst, MemoryMapNode*
node,
+ ConstMemberList *path)
{
const int cnt = inst.memberCount();

@@ -212,11 +263,11 @@

// Did the rules engine decide which instance to use?
if (TypeRuleEngine::useMatchedInst(result)) {
- processInstanceFromRule(inst, mi, i, node);
+ processInstanceFromRule(inst, mi, i, node, path);
}
// Pass the "nested" flag to nested structs/unions
else {
- processInstance(mi, node, true);
+ processInstance(mi, node, path);
}
}
catch (GenericException&) {
@@ -228,7 +279,8 @@

void MemoryMapBuilderCS::processInstanceFromRule(const Instance &parent,
const Instance &member,
- int mbrIdx, MemoryMapNode
*node)
+ int mbrIdx, MemoryMapNode
*node,
+ ConstMemberList *path)
{
if (!member.isNull()) {
// How does the returned instance relate to the given one?
@@ -247,7 +299,8 @@
// Preserve used-defined properties, if any
if (!member.properties().isEmpty())
mOrig.setProperties(member.properties());
- processInstance(mOrig, node, true);
+
+ processInstance(mOrig, node, path);
break;
}
// We followed a pointer
@@ -280,7 +333,7 @@
}

if (member.isList())
- processInstanceFromRule(parent, member.listNext(), mbrIdx, node);
+ processInstanceFromRule(parent, member.listNext(), mbrIdx, node,
path);
}


@@ -370,6 +423,7 @@
else if (invalidChildren > 0) {
float invalidPct = invalidChildren / (float) testedChildren;
prob *= invalidPct * (1.0 - degForInvalidChildAddr) + (1.0 -
invalidPct);
+
if (map)
map->_shared->degForInvalidChildAddrCnt++;
}
@@ -403,8 +457,12 @@
*total = tot;

// Allow at most 20% user-land pointers of all children
- if (tot > 1 && invalid >= 0 && userlandPtrs > (tot / 5))
+ if (tot > 1 && invalid >= 0 && userlandPtrs > (tot / 5)) {
invalid += userlandPtrs - (tot / 5);
+
+ if (total)
+ (*total) += (userlandPtrs - (tot / 5));
+ }

return invalid;
}