1 : // Copyright 2012 Google Inc. All Rights Reserved.
2 : //
3 : // Licensed under the Apache License, Version 2.0 (the "License");
4 : // you may not use this file except in compliance with the License.
5 : // You may obtain a copy of the License at
6 : //
7 : // http://www.apache.org/licenses/LICENSE-2.0
8 : //
9 : // Unless required by applicable law or agreed to in writing, software
10 : // distributed under the License is distributed on an "AS IS" BASIS,
11 : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : // See the License for the specific language governing permissions and
13 : // limitations under the License.
14 : //
15 : // An implementation of a Reorderer. The LinearOrderGenerator simply orders code
16 : // blocks in the order that they were executed as seen in the call-trace.
17 : // If data ordering is enabled, all data blocks referred to by a code block
18 : // are assumed to have been touched when the code block was executed, and they
19 : // are output in that order.
20 : //
21 : // If multiple runs of the instrumented binary are seen in the trace files, each
22 : // run will be processed independently, and for each unique block, the count of
23 : // how many runs in which its execution was seen is maintained. Blocks are first
24 : // sorted by the number of individual runs in which they were seen (decreasing),
25 : // and then sorted by the order in which they were seen. For the special case
26 : // of blocks that were only seen in a single run of the binary, these are
27 : // separated by run and then sorted by time seen.
28 : //
29 : // Consider a trace file that contains 3 runs of an executable. The generated
30 : // ordering will be as follows:
31 : //
32 : // code seen in all 3 runs, code seen in any 2 runs, code seen only in 1st run,
33 : // code seen only in 2nd run, code seen only in 3rd run
34 : //
35 : // In the case where there is a single run of the instrumented binary, the
36 : // ordering will be a simple ordering of blocks by order of execution, as per
37 : // our original proof-of-concept ordering.
38 :
39 : #ifndef SYZYGY_REORDER_LINEAR_ORDER_GENERATOR_H_
40 : #define SYZYGY_REORDER_LINEAR_ORDER_GENERATOR_H_
41 :
42 : #include <map>
43 : #include <set>
44 : #include <vector>
45 :
46 : #include "syzygy/reorder/reorderer.h"
47 :
48 : namespace reorder {
49 :
50 : // A simple linear order generator. See comment at top of this header file for
51 : // more details.
52 : class LinearOrderGenerator : public Reorderer::OrderGenerator {
53 : public:
54 : struct BlockCall;
55 :
56 : LinearOrderGenerator();
57 : virtual ~LinearOrderGenerator();
58 :
59 : // OrderGenerator implementation.
60 : virtual bool OnProcessStarted(uint32 process_id,
61 : const UniqueTime& time) override;
62 : virtual bool OnProcessEnded(uint32 process_id,
63 : const UniqueTime& time) override;
64 : virtual bool OnCodeBlockEntry(const BlockGraph::Block* block,
65 : RelativeAddress address,
66 : uint32 process_id,
67 : uint32 thread_id,
68 : const UniqueTime& time) override;
69 : virtual bool CalculateReordering(const PEFile& pe_file,
70 : const ImageLayout& image,
71 : bool reorder_code,
72 : bool reorder_data,
73 : Order* order) override;
74 :
75 : private:
76 : typedef std::vector<BlockCall> BlockCalls;
77 : typedef std::map<size_t, BlockCalls> ProcessGroupBlockCalls;
78 : typedef std::map<const BlockGraph::Block*, BlockCall> BlockCallMap;
79 : typedef std::set<const BlockGraph::Block*> BlockSet;
80 :
81 : // Called by OnFunctionEntry to update block_calls_.
82 : bool TouchBlock(const BlockCall& block_call);
83 :
84 : // Given a block, inserts the data blocks associated with it into
85 : // the ordering. Will recursively traverse data blocks until the given
86 : // maximum stack depth (that way, we include data referred to by data).
87 : bool InsertDataBlocks(size_t max_recursion_depth,
88 : const BlockGraph::Block* block,
89 : Order* order,
90 : BlockSet* inserted_blocks);
91 :
92 : // This is called to indicate a process group closure.
93 : bool CloseProcessGroup();
94 :
95 : // We assume that processes that co-exist are all part of a single run.
96 : // So we divide up block calls per run. This counts the number of currently
97 : // active processes, and when it reaches zero it means that we need to
98 : // start a new process.
99 : size_t active_process_count_;
100 :
101 : // This is for creating unique ids for groups of coexisting processes.
102 : // This is incremented every time active_process_count transitions from 0
103 : // to 1.
104 : size_t next_process_group_id_;
105 :
106 : // Stores the linearized block list per process group.
107 : ProcessGroupBlockCalls process_group_calls_;
108 :
109 : // Stores pointers to blocks, and the first time at which they were accessed.
110 : // There is one of these per 'process group'.
111 : BlockCallMap block_call_map_;
112 : };
113 :
114 : struct LinearOrderGenerator::BlockCall {
115 : const BlockGraph::Block* block;
116 : uint32 process_id;
117 : uint32 thread_id;
118 : UniqueTime time;
119 :
120 : BlockCall(const BlockGraph::Block* block, uint32 process_id,
121 : uint32 thread_id, const UniqueTime& time)
122 : : block(block), process_id(process_id), thread_id(thread_id),
123 E : time(time) {
124 E : }
125 : };
126 :
127 : } // namespace reorder
128 :
129 : #endif // SYZYGY_REORDER_LINEAR_ORDER_GENERATOR_H_
|