OLD | NEW |
---|---|
1 // Copyright 2015 The Chromium Authors. All rights reserved. | 1 // Copyright 2015 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef COURGETTE_LABEL_MANAGER_H_ | 5 #ifndef COURGETTE_LABEL_MANAGER_H_ |
6 #define COURGETTE_LABEL_MANAGER_H_ | 6 #define COURGETTE_LABEL_MANAGER_H_ |
7 | 7 |
8 #include <stddef.h> | 8 #include <stddef.h> |
9 #include <stdint.h> | 9 #include <stdint.h> |
10 | 10 |
11 #include <map> | 11 #include <map> |
12 #include <vector> | 12 #include <vector> |
13 | 13 |
14 #include "base/gtest_prod_util.h" | 14 #include "base/gtest_prod_util.h" |
15 #include "base/macros.h" | 15 #include "base/macros.h" |
16 #include "courgette/image_utils.h" | 16 #include "courgette/image_utils.h" |
17 | 17 |
18 namespace courgette { | 18 namespace courgette { |
19 | 19 |
20 using LabelVector = std::vector<Label>; | 20 using LabelVector = std::vector<Label>; |
21 using RVAToLabel = std::map<RVA, Label*>; | 21 using RVAToLabel = std::map<RVA, Label*>; |
22 | 22 |
23 // A container to store and manage Label instances. | 23 // A container to store and manage Label instances, dedicated to reducing peak |
24 // memory usage. To this end we preallocate Label instances in bulk, and | |
25 // carefully control transient memory usage when initializing Labels. | |
24 class LabelManager { | 26 class LabelManager { |
25 public: | 27 public: |
26 virtual ~LabelManager(); | |
27 | |
28 // Returns an exclusive upper bound for all existing indexes in |labels|. | |
29 static int GetIndexBound(const LabelVector& labels); | |
30 | |
31 // Returns an exclusive upper bound for all existing indexes in |labels_map|. | |
32 static int GetIndexBound(const RVAToLabel& labels_map); | |
33 | |
34 // Returns the number of Label instances stored. | |
35 virtual size_t Size() const = 0; | |
36 | |
37 // Efficiently searches for a Label that targets |rva|. Returns the pointer to | |
38 // the stored Label instance if found, or null otherwise. Non-const to support | |
39 // implementations that allocate-on-read. | |
40 virtual Label* Find(RVA rva) = 0; | |
41 | |
42 // Removes Label instances whose |count_| is less than |count_threshold|. | |
43 virtual void RemoveUnderusedLabels(int32_t count_threshold) = 0; | |
44 | |
45 // Resets all indexes to an unassigned state. | |
46 virtual void UnassignIndexes() = 0; | |
47 | |
48 // Assigns indexes to successive integers from 0, ordered by RVA. | |
49 virtual void DefaultAssignIndexes() = 0; | |
50 | |
51 // Assigns indexes to any Label instances that don't have one yet. | |
52 virtual void AssignRemainingIndexes() = 0; | |
53 | |
54 protected: | |
55 LabelManager(); | |
56 | |
57 private: | |
58 DISALLOW_COPY_AND_ASSIGN(LabelManager); | |
59 }; | |
60 | |
61 // An implementation of LabelManager dedicated to reducing peak memory usage. | |
62 // To this end we preallocate Label instances in bulk, and carefully control | |
63 // transient memory usage when initializing Labels. | |
64 class LabelManagerImpl : public LabelManager { | |
65 public: | |
66 // An adaptor to sequentially traverse multiple RVAs. This is useful for RVA | |
67 // translation without extra storage. For example, we might have a stored list | |
68 // of RVA locations, but we want to traverse the matching RVA targets. | |
69 class RvaVisitor { | |
70 public: | |
71 virtual ~RvaVisitor(); | |
72 | |
73 // Returns the number of remaining RVAs to visit. | |
74 virtual size_t Remaining() const = 0; | |
75 | |
76 // Returns the current RVA. | |
77 virtual RVA Get() const = 0; | |
78 | |
79 // Advances to the next RVA. | |
80 virtual void Next() = 0; | |
81 }; | |
82 | |
83 // A helper class to heuristically complete index assignment for a list of | 28 // A helper class to heuristically complete index assignment for a list of |
84 // Labels that have partially assigned indexes. | 29 // Labels that have partially assigned indexes. |
85 // Goal: An address table compresses best when each index is associated with | 30 // Goal: An address table compresses best when each index is associated with |
86 // an address that is slightly larger than the previous index. | 31 // an address that is slightly larger than the previous index. |
87 // For example, suppose we have RVAs | 32 // For example, suppose we have RVAs |
88 // [0x0000, 0x0070, 0x00E0, 0x0150]. | 33 // [0x0000, 0x0070, 0x00E0, 0x0150]. |
89 // Consider candidate (RVA, index) assignments A and B: | 34 // Consider candidate (RVA, index) assignments A and B: |
90 // A: [(0x0000, 0), (0x0070, 1), (0x00E0, 2), (0x0150, 3)], | 35 // A: [(0x0000, 0), (0x0070, 1), (0x00E0, 2), (0x0150, 3)], |
91 // B: [(0x0000, 2), (0x0070, 1), (0x00E0, 0), (0x0150, 3)]. | 36 // B: [(0x0000, 2), (0x0070, 1), (0x00E0, 0), (0x0150, 3)]. |
92 // To form the address table, we first sort by indexes: | 37 // To form the address table, we first sort by indexes: |
93 // A: [(0x0000, 0), (0x0070, 1), (0x00E0, 2), (0x0150, 3)], | 38 // A: [(0x0000, 0), (0x0070, 1), (0x00E0, 2), (0x0150, 3)], |
94 // B: [(0x00E0, 0), (0x0070, 1), (0x0000, 2), (0x0150, 3)]. | 39 // B: [(0x00E0, 0), (0x0070, 1), (0x0000, 2), (0x0150, 3)]. |
95 // Then we extract the RVAs for storage: | 40 // Then we extract the RVAs for storage: |
96 // A: [0x0000, 0x0070, 0x00E0, 0x0150], | 41 // A: [0x0000, 0x0070, 0x00E0, 0x0150], |
97 // B: [0x00E0, 0x0070, 0x0000, 0x0150]. | 42 // B: [0x00E0, 0x0070, 0x0000, 0x0150]. |
98 // Clearly A compresses better than B under (signed) delta encoding. | 43 // Clearly A compresses better than B under (signed) delta encoding. |
99 // In Courgette-gen, an assignment algorithm (subclass of AdjustmentMethod) | 44 // In Courgette-gen, an assignment algorithm (subclass of AdjustmentMethod) |
100 // creates partial and arbitrary index assignments (to attempt to match one | 45 // creates partial and arbitrary index assignments (to attempt to match one |
101 // file against another). So the sorted case (like A) won't happen in general. | 46 // file against another). So the sorted case (like A) won't happen in general. |
102 // Our helper class fills in the missing assignments by creating runs of | 47 // Our helper class fills in the missing assignments by creating runs of |
103 // consecutive indexes, so once RVAs are sorted by these indexes we'd reduce | 48 // consecutive indexes, so once RVAs are sorted by these indexes we'd reduce |
104 // distances between successive RVAs. | 49 // distances between successive RVAs. |
105 class SimpleIndexAssigner { | 50 class SimpleIndexAssigner { |
106 public: | 51 public: |
107 SimpleIndexAssigner(LabelVector* labels); | 52 explicit SimpleIndexAssigner(LabelVector* labels); |
108 ~SimpleIndexAssigner(); | 53 ~SimpleIndexAssigner(); |
109 | 54 |
110 // Scans forward to assign successive indexes to Labels, using existing | 55 // Scans forward to assign successive indexes to Labels, using existing |
111 // indexes as start-anchors. | 56 // indexes as start-anchors. |
112 void DoForwardFill(); | 57 void DoForwardFill(); |
113 | 58 |
114 // Scans backward to assign successive indexes to Labels, using existing | 59 // Scans backward to assign successive indexes to Labels, using existing |
115 // indexes as end-anchors. | 60 // indexes as end-anchors. |
116 void DoBackwardFill(); | 61 void DoBackwardFill(); |
117 | 62 |
118 // Assigns all unsigned indexes using what's available, disregarding current | 63 // Assigns all unsigned indexes using what's available, disregarding current |
119 // Label assignment. | 64 // Label assignment. |
120 void DoInFill(); | 65 void DoInFill(); |
121 | 66 |
122 private: | 67 private: |
123 // List of Labels to process. Owned by caller. | 68 // The target LabelVector, owned by the caller. |
124 LabelVector* labels_; | 69 LabelVector* labels_; |
125 | 70 |
126 // A bound on indexes. | 71 // A bound on indexes. |
127 int num_index_ = 0; | 72 int num_index_ = 0; |
128 | 73 |
129 // Tracker for index usage to ensure uniqueness of indexes. | 74 // Tracker for index usage to ensure uniqueness of indexes. |
130 std::vector<bool> available_; | 75 std::vector<bool> available_; |
131 | 76 |
132 DISALLOW_COPY_AND_ASSIGN(SimpleIndexAssigner); | 77 DISALLOW_COPY_AND_ASSIGN(SimpleIndexAssigner); |
133 }; | 78 }; |
134 | 79 |
135 LabelManagerImpl(); | 80 LabelManager(); |
136 ~LabelManagerImpl() override; | 81 ~LabelManager(); |
137 | 82 |
138 // LabelManager interfaces. | 83 // Returns an exclusive upper bound for all existing indexes in |labels_map|. |
139 size_t Size() const override; | 84 // TODO(huangs): Remove once all callers are gone. |
Will Harris
2016/04/06 17:55:54
where did Size() go and why isn't it needed?
huangs
2016/04/06 18:28:05
LabelManager::Labels() is moved from private: to p
| |
140 Label* Find(RVA rva) override; | 85 static int GetIndexBound(const RVAToLabel& labels_map); |
141 void RemoveUnderusedLabels(int32_t count_threshold) override; | 86 |
142 void UnassignIndexes() override; | 87 // Returns an exclusive upper bound for all assigned indexes in |labels|. |
143 void DefaultAssignIndexes() override; | 88 static int GetLabelIndexBound(const LabelVector& labels); |
144 void AssignRemainingIndexes() override; | 89 |
90 // Accessor to stored Label instances. | |
91 const LabelVector& Labels() const { return labels_; } | |
92 | |
93 // Efficiently searches for a Label that targets |rva|. Returns the pointer to | |
94 // the stored Label instance if found, or null otherwise. Non-const to support | |
95 // implementations that allocate-on-read. | |
96 Label* Find(RVA rva); | |
97 | |
98 // Removes Label instances whose |count_| is less than |count_threshold|. | |
99 void RemoveUnderusedLabels(int32_t count_threshold); | |
100 | |
101 // Resets all indexes to an unassigned state. | |
102 void UnassignIndexes(); | |
103 | |
104 // Assigns indexes to successive integers from 0, ordered by RVA. | |
105 void DefaultAssignIndexes(); | |
106 | |
107 // Assigns indexes to any Label instances that don't have one yet. | |
108 void AssignRemainingIndexes(); | |
145 | 109 |
146 // Populates |labels_| using RVAs from |rva_visitor|. Each distinct RVA from | 110 // Populates |labels_| using RVAs from |rva_visitor|. Each distinct RVA from |
147 // |rva_visitor| yields a Label with |rva_| assigned as the RVA, and |count_| | 111 // |rva_visitor| yields a Label with |rva_| assigned as the RVA, and |count_| |
148 // assigned as the repeat. | 112 // assigned as the repeat. |
149 void Read(RvaVisitor* rva_visitor); | 113 void Read(RvaVisitor* rva_visitor); |
150 | 114 |
151 protected: | 115 protected: |
116 FRIEND_TEST_ALL_PREFIXES(LabelManagerTest, TrivialAssign); | |
117 FRIEND_TEST_ALL_PREFIXES(LabelManagerTest, AssignRemainingIndexes); | |
118 | |
152 // The main list of Label instances, sorted by the |rva_| member. | 119 // The main list of Label instances, sorted by the |rva_| member. |
153 LabelVector labels_; | 120 LabelVector labels_; |
154 | 121 |
155 private: | 122 private: |
156 FRIEND_TEST_ALL_PREFIXES(LabelManagerTest, TrivialAssign); | 123 DISALLOW_COPY_AND_ASSIGN(LabelManager); |
157 FRIEND_TEST_ALL_PREFIXES(LabelManagerTest, AssignRemainingIndexes); | |
158 | |
159 // Accessor to stored Label instances. For testing only. | |
160 const LabelVector& Labels() const { return labels_; } | |
161 | |
162 // Directly assign |labels_|. For testing only. | |
163 void SetLabels(const LabelVector& labels); | |
164 | |
165 DISALLOW_COPY_AND_ASSIGN(LabelManagerImpl); | |
166 }; | 124 }; |
167 | 125 |
168 } // namespace courgette | 126 } // namespace courgette |
169 | 127 |
170 #endif // COURGETTE_LABEL_MANAGER_H_ | 128 #endif // COURGETTE_LABEL_MANAGER_H_ |
OLD | NEW |