Index: syzygy/reorder/linear_order_generator.h |
=================================================================== |
--- syzygy/reorder/linear_order_generator.h (revision 365) |
+++ syzygy/reorder/linear_order_generator.h (working copy) |
@@ -17,6 +17,25 @@ |
// If data ordering is enabled, all data blocks referred to by a code block |
// are assumed to have been touched when the code block was executed, and they |
// are output in that order. |
+// |
+// If multiple runs of the instrumented binary are seen in the trace files, each |
+// run will be processed independently, and for each unique block, the count of |
+// how many runs in which its execution was seen is maintained. Blocks are first |
+// sorted by the number of individual runs in which they were seen (decreasing), |
+// and then sorted by the order in which they were seen. For the special case |
+// of blocks that were only seen in a single run of the binary, these are |
Siggi
2011/07/05 14:30:19
Nice. Thanks!
|
+// separated by run and then sorted by time seen. |
+// |
+// Consider a trace file that contains 3 runs of an executable. The generated |
+// ordering will be as follows: |
+// |
+// code seen in all 3 runs, code seen in any 2 runs, code seen only in 1st run, |
+// code seen only in 2nd run, code seen only in 3rd run |
+// |
+// In the case where there is a single run of the instrumented binary, the |
+// ordering will be a simple ordering of blocks by order of execution, as per |
+// our original proof-of-concept ordering. |
+ |
#ifndef SYZYGY_REORDER_LINEAR_ORDER_GENERATOR_H_ |
#define SYZYGY_REORDER_LINEAR_ORDER_GENERATOR_H_ |
@@ -30,11 +49,18 @@ |
public: |
typedef Reorderer::UniqueTime UniqueTime; |
typedef Reorderer::Order Order; |
+ struct BlockCall; |
LinearOrderGenerator(); |
virtual ~LinearOrderGenerator(); |
// OrderGenerator implementation. |
+ virtual bool OnProcessStarted(const Reorderer& reorderer, |
+ uint32 process_id, |
+ const UniqueTime& time); |
+ virtual bool OnProcessEnded(const Reorderer& reorderer, |
+ uint32 process_id, |
+ const UniqueTime& time); |
virtual bool OnCodeBlockEntry(const Reorderer& reorderer, |
const BlockGraph::Block* block, |
RelativeAddress address, |
@@ -45,19 +71,59 @@ |
Order* order); |
private: |
- typedef std::map<const BlockGraph::Block*, UniqueTime> BlockCallMap; |
+ typedef std::vector<BlockCall> BlockCalls; |
+ typedef std::map<size_t, BlockCalls> ProcessGroupBlockCalls; |
+ typedef std::map<const BlockGraph::Block*, BlockCall> BlockCallMap; |
// Called by OnFunctionEntry to update block_calls_. |
- bool TouchBlock(const BlockGraph::Block* block, const UniqueTime& time); |
- // Given a code block, touches the data blocks associated with it. |
- bool TouchDataBlocks(const Reorderer& reorderer, |
- const BlockGraph::Block* code_block, |
- const UniqueTime& time); |
+ bool TouchBlock(const BlockCall& block_call); |
+ // Given a block, inserts the data blocks associated with it into |
+ // the ordering. Will recursively traverse data blocks until the given |
+ // maximum stack depth (that way, we include data referred to by data). |
+ bool InsertDataBlocks(size_t max_recursion_depth, |
+ const Reorderer& reorderer, |
+ const BlockGraph::Block* block, |
+ Order* order); |
+ |
+ // This is called to indicate a process group closure. |
+ bool CloseProcessGroup(); |
+ |
+ // We assume that processes that co-exist are all part of a single run. |
+ // So we divide up block calls per run. This counts the number of currently |
+ // active processes, and when it reaches zero it means that we need to |
+ // start a new process. |
+ size_t active_process_count_; |
+ |
+ // This is for creating unique ids for groups of coexisting processes. |
+ // This is incremented every time active_process_count transitions from 0 |
+ // to 1. |
+ size_t next_process_group_id_; |
+ |
+ // Stores the linearized block list per process group. |
+ ProcessGroupBlockCalls process_group_calls_; |
+ |
// Stores pointers to blocks, and the first time at which they were accessed. |
- BlockCallMap block_calls_; |
+ // There is one of these per 'process group'. |
+ BlockCallMap block_call_map_; |
+ |
+ // Stores a list of already-inserted data blocks. |
+ std::set<const BlockGraph::Block*> data_block_set_; |
}; |
+struct LinearOrderGenerator::BlockCall { |
+ const BlockGraph::Block* block; |
+ uint32_t process_id; |
+ uint32_t thread_id; |
+ UniqueTime time; |
+ |
+ BlockCall(const BlockGraph::Block* block, uint32_t process_id, |
+ uint32_t thread_id, const UniqueTime& time) |
+ : block(block), process_id(process_id), thread_id(thread_id), |
+ time(time) { |
+ } |
+}; |
+ |
} // namespace reorder |
#endif // SYZYGY_REORDER_LINEAR_ORDER_GENERATOR_H_ |