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 : // Declares AddressRange, AddressSpace and AddressRangeMap. AddressRange is
16 : // a primitive used by AddressSpace and AddressRangeMap. AddressSpace is useful
17 : // for maintaining a collection of objects that map to ranges of bytes in some
18 : // finite address-space, ensuring that they do not collide. An AddressRangeMap
19 : // is a specialized version of an AddressSpace where the stored objects are
20 : // themselves AddressRanges, with special semantics for simplifying the
21 : // representation.
22 :
23 : #ifndef SYZYGY_CORE_ADDRESS_SPACE_H_
24 : #define SYZYGY_CORE_ADDRESS_SPACE_H_
25 :
26 : #include <algorithm>
27 : #include <iosfwd>
28 : #include <map>
29 : #include <utility>
30 : #include <vector>
31 :
32 : #include "base/logging.h"
33 : #include "syzygy/core/address_range.h"
34 : #include "syzygy/core/address_space_internal.h"
35 : #include "syzygy/core/serialization.h"
36 :
37 : namespace core {
38 :
39 : // An address space is a mapping from a set of non-overlapping address ranges
40 : // (AddressSpace::Range), each of non-zero size, to an ItemType.
41 : template <typename AddressType, typename SizeType, typename ItemType>
42 : class AddressSpace {
43 : public:
44 : // Typedef we use for convenience throughout.
45 : typedef AddressRange<AddressType, SizeType> Range;
46 : typedef std::map<Range, ItemType> RangeMap;
47 : typedef typename std::map<Range, ItemType>::iterator RangeMapIter;
48 : typedef typename std::map<Range, ItemType>::const_iterator RangeMapConstIter;
49 : typedef std::pair<RangeMapConstIter, RangeMapConstIter> RangeMapConstIterPair;
50 : typedef std::pair<RangeMapIter, RangeMapIter> RangeMapIterPair;
51 :
52 : // STL-like type definitions
53 : // @{
54 : typedef typename RangeMapIter iterator;
55 : typedef typename RangeMapConstIter const_iterator;
56 : typedef typename RangeMap::value_type value_type;
57 : // @}
58 :
59 : // Create an empty address space.
60 : AddressSpace();
61 :
62 : // Insert @p range mapping to @p item unless @p range intersects
63 : // an existing range.
64 : // @param range the range to insert.
65 : // @param item the item to associate with @p range.
66 : // @param ret_it on success, returns an iterator to the inserted item.
67 : // @returns true iff @p range inserted.
68 : bool Insert(const Range& range,
69 : const ItemType& item,
70 : typename RangeMap::iterator* ret_it = NULL);
71 :
72 : // Insert @p range mapping to @p item or return the existing item exactly
73 : // matching @p range.
74 : //
75 : // @param range the range of the item to get or insert.
76 : // @param item the item to associate with @p range if none already exists.
77 : // @param ret_it on success, returns an iterator to the found or inserted
78 : // item if not NULL.
79 : //
80 : // @returns true if the {range, item} pair is inserted or if there exists
81 : // an item exactly matching range; otherwise false, indicating that a
82 : // conflict/error has been detected.
83 : bool FindOrInsert(const Range& range,
84 : const ItemType& item,
85 : typename RangeMap::iterator* ret_it = NULL);
86 :
87 : // Inserts @p range mapping to @p item, unless @p range intersects
88 : // an existing range and does not contain it. Any existing ranges it contains
89 : // will be removed. If a range exists that contains @p range, returns true
90 : // and returns the iterator to that range.
91 : // @param range the range to insert.
92 : // @param item the item to associate with @p range.
93 : // @param ret_it on success, returns an iterator to the inserted item.
94 : // @returns true on success.
95 : //
96 : // Example insertions:
97 : //
98 : // Existing : aaaa bbbb
99 : // Inserting: xxxxxxxxxxxx
100 : // Result : cccccccccccc
101 : //
102 : // Existing : aaaaaa bbbbbb
103 : // Inserting: xxxxxxxxxx
104 : // Result : failure!
105 : bool SubsumeInsert(const Range& range,
106 : const ItemType& item,
107 : typename RangeMap::iterator* ret_it = NULL);
108 :
109 : // Inserts @p range mapping to @p item. If this range overlaps any existing
110 : // blocks, all of the overlapping blocks will be merged to form one single
111 : // block. This insertion can never fail. If @p ret_it is non-null, return the
112 : // iterator to the inserted block, or if @p range lies entirely within an
113 : // existing block, returns the iterator to that block.
114 : // @param range the range to insert.
115 : // @param item the item to associate with @p range.
116 : // @param ret_it on success, returns an iterator to the inserted item.
117 : //
118 : // Example insertions:
119 : //
120 : // Existing : aaaa bbbb
121 : // Inserting: xxxxxxxxxxxx
122 : // Result : cccccccccccc
123 : //
124 : // Existing : aaaaaa bbbbbb
125 : // Inserting: xxxxxxxxxx
126 : // Result : cccccccccccccc
127 : void MergeInsert(const Range& range,
128 : const ItemType& item,
129 : typename RangeMap::iterator* ret_it = NULL);
130 :
131 : // Remove the range that exactly matches @p range.
132 : // Returns true iff @p range is removed.
133 : bool Remove(const Range& range);
134 : // Remove the item at position @p it.
135 E : void Remove(RangeMapIter it) { ranges_.erase(it); }
136 : // Remove the items in the given range.
137 E : void Remove(RangeMapIterPair its) { ranges_.erase(its.first, its.second); }
138 E : void Remove(RangeMapIter it1, RangeMapIter it2) { ranges_.erase(it1, it2); }
139 : // Remove all items from the address space.
140 E : void Clear() { ranges_.clear(); }
141 :
142 E : const RangeMap& ranges() const { return ranges_; }
143 E : const bool empty() const { return ranges_.empty(); }
144 E : const size_t size() const { return ranges_.size(); }
145 :
146 : // Finds the first contained range that intersects @p range.
147 : RangeMapConstIter FindFirstIntersection(const Range& range) const;
148 : RangeMapIter FindFirstIntersection(const Range& range);
149 :
150 : // Caution must be taken in using the non-const version of these! It is up
151 : // to the user not to change the values of any underlying ranges so as to
152 : // invalidate the non-overlapping range property of the address space. The
153 : // non-const iterator access is only intended for deletion of entire ranges.
154 E : RangeMapConstIter begin() const { return ranges_.begin(); }
155 E : RangeMapIter begin() { return ranges_.begin(); }
156 E : RangeMapConstIter end() const { return ranges_.end(); }
157 E : RangeMapIter end() { return ranges_.end(); }
158 :
159 : // Returns a pair of iterators that iterate over all ranges
160 : // intersecting @p range.
161 : RangeMapConstIterPair FindIntersecting(const Range& range) const;
162 : RangeMapIterPair FindIntersecting(const Range& range);
163 :
164 : // Returns true if the given range intersects any range currently in the
165 : // address space.
166 : bool Intersects(const Range& range) const;
167 E : bool Intersects(AddressType address, SizeType size = 1) const {
168 E : return Intersects(Range(address, size));
169 E : }
170 :
171 : // Returns true if the given range is contained exactly in the address
172 : // space.
173 : bool ContainsExactly(const Range& range) const;
174 E : bool ContainsExactly(AddressType address, SizeType size = 1) const {
175 E : return ContainsExactly(Range(address, size));
176 E : }
177 :
178 : // Returns true if the given range is contained by exactly one range in the
179 : // address space.
180 : bool Contains(const Range& range) const;
181 E : bool Contains(AddressType address, SizeType size = 1) const {
182 E : return Contains(Range(address, size));
183 E : }
184 :
185 : // Finds the range that contains @p range.
186 : typename RangeMap::const_iterator FindContaining(const Range& range) const;
187 : typename RangeMap::iterator FindContaining(const Range& range);
188 :
189 : private:
190 : // Our ranges and their associated items.
191 : RangeMap ranges_;
192 : };
193 :
194 : // An AddressRangeMap is used for keeping track of data in one address space
195 : // that has some relationship with data in another address space. Mappings are
196 : // stored as pairs of addresses, one from the 'source' address-space and one
197 : // from the 'destination' address-space. The ranges are sorted based on the
198 : // source ranges, and the source ranges must be disjoint. The data structure
199 : // ensures that the representation used is minimal in the following sense:
200 : // a pair of address-range mappings that have the same size in both images and
201 : // are consecutive in each image will be merged. For example, consider a
202 : // mapping containing the two pairs of ranges:
203 : //
204 : // [0, 10) maps to [1000, 1010), and
205 : // [10, 30) maps to [1010, 1030).
206 : //
207 : // This is more succinctly represented as (assuming linearity of the underlying
208 : // relationship):
209 : //
210 : // [0, 30) maps to [1000, 1030).
211 : //
212 : // However, a pair of mappings like:
213 : //
214 : // [0, 10) maps to [1000, 1010), and
215 : // [10, 30) maps to [1010, 1036)
216 : //
217 : // should not be merged, as even though they are contiguous in both address
218 : // spaces, the source and destination ranges are not of the same size for the
219 : // second pair. Thus, we can't imply that the relationship holds for the pair
220 : // [0, 30) and [1000, 1036).
221 : template <typename SourceRangeType, typename DestinationRangeType>
222 : class AddressRangeMap {
223 : public:
224 : typedef SourceRangeType SourceRange;
225 : typedef DestinationRangeType DestinationRange;
226 : typedef std::pair<SourceRange, DestinationRange> RangePair;
227 : typedef std::vector<RangePair> RangePairs;
228 :
229 E : const RangePairs& range_pairs() const { return range_pairs_; }
230 E : const RangePair& range_pair(size_t i) const { return range_pairs_[i]; }
231 E : void clear() { range_pairs_.clear(); }
232 E : bool empty() const { return range_pairs_.empty(); }
233 E : size_t size() const { return range_pairs_.size(); }
234 :
235 E : bool operator==(const AddressRangeMap& other) const {
236 E : return range_pairs_ == other.range_pairs_;
237 E : }
238 :
239 E : bool operator!=(const AddressRangeMap& other) const {
240 E : return range_pairs_ != other.range_pairs_;
241 E : }
242 :
243 : // Determines if this is a simple mapping.
244 : //
245 : // A mapping is simple if there exists exactly one range, and the sizes of the
246 : // source and destination ranges are identical.
247 : //
248 : // @returns true if this mapping is simple, false otherwise.
249 E : bool IsSimple() const {
250 : return range_pairs_.size() == 1 &&
251 E : range_pairs_.front().first.size() == range_pairs_.front().second.size();
252 E : }
253 :
254 : // Given a source range finds the range pair that encompasses it, if it
255 : // exists.
256 : //
257 : // @param sec_range the source range to search for.
258 : // @returns a pointer to the range pair, or NULL if none exists.
259 : const RangePair* FindRangePair(const SourceRange& src_range) const;
260 :
261 : // Given a source range finds the range pair that encompasses it, if it
262 : // exists.
263 : //
264 : // @param start the beginning of the source range to search for.
265 : // @param size the size of the source range to search for.
266 : // @returns a pointer to the range pair, or NULL if none exists.
267 : const RangePair* FindRangePair(typename SourceRange::Address start,
268 E : typename SourceRange::Size size) const {
269 E : return FindRangePair(SourceRange(start, size));
270 E : }
271 :
272 : // Determines if the given source address range is fully mapped.
273 : //
274 : // @param src_range the source range to confirm.
275 : // @returns true if @p src_range is fully mapped, false otherwise.
276 : bool IsMapped(const SourceRange& src_range) const;
277 :
278 : // Determines if the given source address range is fully mapped.
279 : //
280 : // @param start the beginning of the source range to confirm.
281 : // @param size the size of the source range to confirm.
282 : // @returns true if the source range is fully mapped, false otherwise.
283 : bool IsMapped(typename SourceRange::Address start,
284 E : typename SourceRange::Size size) const {
285 E : return IsMapped(SourceRange(start, size));
286 E : }
287 :
288 : // Adds a new pair of ranges to the map.
289 : //
290 : // This method allows insertions at arbitrary locations, but may consequently
291 : // be slower as a reallocation may be required.
292 : //
293 : // @param src_range the source range of the mapping to be inserted.
294 : // @param dst_range the destination range of the mapping to be inserted.
295 : // @returns true on success, false otherwise.
296 : bool Insert(const SourceRange& src_range, const DestinationRange& dst_range);
297 :
298 : // Pushes a new pair of ranges to the tail end of the source address range.
299 : //
300 : // This method is amortized O(1) and is simpler than Insert if the mapping
301 : // is being created in sequential order in the source address space. This will
302 : // fail if @p src_range is not greater than all existing ranges.
303 : //
304 : // @param src_range the source range of the mapping to be inserted.
305 : // @param dst_range the destination range of the mapping to be inserted.
306 : // @returns true on success, false otherwise.
307 : bool Push(const SourceRange& src_range, const DestinationRange& dst_range);
308 :
309 : // Computes the inverse of this mapping, returning the number of address
310 : // ranges mappings that were unable to be inverted. If DestinationRange and
311 : // SourceRange are the same type this may be performed in-place.
312 : //
313 : // The inversion is deterministic. When conflicting destination ranges are
314 : // found, earlier start addresses and shorter lengths have priority.
315 : //
316 : // @param inverted a pointer to the AddressRangeMap that will be populated
317 : // with the inverted address range map.
318 : // @returns the number of conflicting address ranges that were unable to be
319 : // inverted.
320 : size_t ComputeInverse(
321 : AddressRangeMap<DestinationRange, SourceRange>* inverted) const;
322 :
323 : // Rejigs a mapping by changing the underlying address-space that is being
324 : // mapped. This inserts a range of unmapped data in the source range, pushing
325 : // all mapped ranges that are beyond the newly unmapped data. If a mapped
326 : // source range intersects the unmapped range being inserted, this mapping
327 : // is split. During a split, the first of the two split ranges will maintain
328 : // linearity when possible.
329 : //
330 : // For example, consider the following address range map (expressed as
331 : // [start, end) ranges):
332 : //
333 : // [0, 10) -> [1000, 1010), [20, 30) -> [1020, 1030)
334 : //
335 : // After inserting an unmapped range at offset 25 size 5 the mapping will be:
336 : //
337 : // [0, 10) -> [1000, 1010), [20, 25) -> [1020, 1025), [30, 35) -> [1025, 1030)
338 : //
339 : // Simple splitting can fail in a very unlikely edge case. Consider the case
340 : // where the source range has size N > 1 and the destination range has size 1.
341 : // Now consider splitting the source range. We only have one byte of
342 : // destination range, so how to split that into two? The only solution is to
343 : // duplicate the destination range, which may make the mapping no longer
344 : // invertible.
345 : //
346 : // @param unmapped the unmapped source range to insert.
347 : void InsertUnmappedRange(const SourceRange& unmapped);
348 :
349 : // Modifies a mapping by changing the underlying address-space that is being
350 : // mapped. This removes a source range, erasing any mappings over that range
351 : // and shifting all mappings beyond that range to the left, as necessary. If
352 : // any mappings intersect the range being removed they will be split in such a
353 : // way as to keep the individual mappings linear, if possible.
354 : //
355 : // For example, consider the following address range map (expressed as
356 : // [start, end) ranges):
357 : //
358 : // [0, 10) -> [1000, 1010), [20, 30) -> [1020, 1030)
359 : //
360 : // After removing the source range [5, 20), the mapping will be:
361 : //
362 : // [0, 5) -> [1000, 1005), [5, 15) -> [1020, 1030)
363 : //
364 : // @param mapped the mapped source range to remove.
365 : void RemoveMappedRange(const SourceRange& mapped);
366 :
367 : // For serialization.
368 E : bool Save(OutArchive* out_archive) const {
369 E : DCHECK(out_archive != NULL);
370 E : return out_archive->Save(range_pairs_);
371 E : }
372 E : bool Load(InArchive* in_archive) {
373 E : DCHECK(in_archive != NULL);
374 E : return in_archive->Load(&range_pairs_);
375 E : }
376 :
377 : private:
378 : // Runs a lower bound search with the provided src_range and a made up
379 : // destination range. The returned iterator either intersects src_range, is
380 : // strictly greater than it, or is 'end()'.
381 : typename RangePairs::const_iterator LowerBound(
382 : const SourceRange& src_range) const;
383 :
384 : // Stores the mapping.
385 : RangePairs range_pairs_;
386 : };
387 :
388 : template <typename AddressType, typename SizeType, typename ItemType>
389 E : AddressSpace<AddressType, SizeType, ItemType>::AddressSpace() {
390 E : }
391 :
392 : template <typename AddressType, typename SizeType, typename ItemType>
393 : bool AddressSpace<AddressType, SizeType, ItemType>::Insert(
394 : const Range& range,
395 : const ItemType& item,
396 E : typename RangeMap::iterator* ret_it) {
397 : // We can't insert empty ranges.
398 E : if (range.IsEmpty())
399 E : return false;
400 :
401 : // Is there an intersecting block?
402 E : RangeMap::iterator it = FindFirstIntersection(range);
403 E : if (it != ranges_.end())
404 E : return false;
405 :
406 : std::pair<RangeMap::iterator, bool> inserted =
407 E : ranges_.insert(std::make_pair(range, item));
408 E : DCHECK(inserted.second);
409 E : if (ret_it != NULL)
410 E : *ret_it = inserted.first;
411 :
412 E : return true;
413 E : }
414 :
415 : template <typename AddressType, typename SizeType, typename ItemType>
416 : bool AddressSpace<AddressType, SizeType, ItemType>::FindOrInsert(
417 : const Range& range,
418 : const ItemType& item,
419 E : typename RangeMap::iterator* ret_it) {
420 : // We can't insert empty ranges.
421 E : if (range.IsEmpty())
422 E : return false;
423 :
424 : // Is there already an existing block exactly matching that range? If so,
425 : // return it.
426 E : RangeMap::iterator it = FindFirstIntersection(range);
427 E : if (it != ranges_.end()) {
428 E : if (ret_it != NULL)
429 E : *ret_it = it;
430 E : return range == it->first && item == it->second;
431 : }
432 :
433 : std::pair<RangeMap::iterator, bool> inserted =
434 E : ranges_.insert(std::make_pair(range, item));
435 E : DCHECK(inserted.second);
436 E : if (ret_it != NULL)
437 E : *ret_it = inserted.first;
438 :
439 E : return true;
440 E : }
441 :
442 : template <typename AddressType, typename SizeType, typename ItemType>
443 : bool AddressSpace<AddressType, SizeType, ItemType>::SubsumeInsert(
444 : const Range& range,
445 : const ItemType& item,
446 E : typename RangeMap::iterator* ret_it) {
447 : // We can't insert empty ranges.
448 E : if (range.IsEmpty())
449 E : return false;
450 :
451 E : RangeMapIterPair its = FindIntersecting(range);
452 :
453 : // We only need to check how we intersect the first and last ranges; we
454 : // are guaranteed to subsume all others.
455 E : if (its.first != its.second) {
456 E : RangeMapIter it = its.first;
457 :
458 : // Check the first range.
459 E : DCHECK(range.Intersects(it->first));
460 : // We do not contain the first returned range?
461 E : if (!range.Contains(it->first)) {
462 : // We do not contain it, it does not contain us. We have a proper
463 : // intersection with them and the insertion fails.
464 E : if (!it->first.Contains(range))
465 E : return false;
466 :
467 : // They strictly contain us. There should be only one of them, and we
468 : // should return it.
469 E : DCHECK_EQ(1, std::distance(its.first, its.second));
470 E : if (ret_it != NULL)
471 i : *ret_it = its.first;
472 E : return true;
473 : }
474 :
475 : // We now check the second range. If we got here, the first range is a
476 : // proper subset of the range we're trying to add. We need to contain the
477 : // second range in order for the insertion to proceed. If we do not contain
478 : // it, we know it starts within our range, and finished outside of it and
479 : // therefore it is a proper intersection.
480 E : it = its.second;
481 E : --it;
482 E : DCHECK(range.Intersects(it->first));
483 E : if (!range.Contains(it->first))
484 E : return false;
485 : }
486 :
487 E : ranges_.erase(its.first, its.second);
488 :
489 : std::pair<RangeMap::iterator, bool> inserted =
490 E : ranges_.insert(std::make_pair(range, item));
491 E : DCHECK(inserted.second);
492 E : if (ret_it != NULL)
493 i : *ret_it = inserted.first;
494 :
495 E : return true;
496 E : }
497 :
498 : template <typename AddressType, typename SizeType, typename ItemType>
499 : void AddressSpace<AddressType, SizeType, ItemType>::MergeInsert(
500 : const Range& range,
501 : const ItemType& item,
502 E : typename RangeMap::iterator* ret_it) {
503 : // We can't insert empty ranges.
504 E : if (range.IsEmpty())
505 i : return;
506 :
507 E : RangeMapIterPair its = FindIntersecting(range);
508 :
509 E : AddressType start_addr = range.start();
510 E : size_t length = range.size();
511 :
512 : // Have overlap with existing blocks?
513 E : if (its.first != its.second) {
514 : // Find start address of new block. This is the min of the requested range,
515 : // or the beginning of the first intersecting block.
516 E : RangeMap::iterator it_first = its.first;
517 E : DCHECK(it_first != ranges_.end());
518 E : start_addr = std::min(range.start(), it_first->first.start());
519 :
520 : // Find end address of new block. This is the max of the requested range,
521 : // or the end of the last intersecting block.
522 E : RangeMap::iterator it_last = its.second;
523 E : --it_last;
524 E : DCHECK(it_last != ranges_.end());
525 E : AddressType end_addr = std::max(range.end(), it_last->first.end());
526 :
527 : // Erase the existing blocks.
528 E : length = end_addr - start_addr;
529 E : ranges_.erase(its.first, its.second);
530 : }
531 :
532 : // Insert the new block.
533 E : Range new_range(start_addr, length);
534 : std::pair<RangeMap::iterator, bool> inserted =
535 E : ranges_.insert(std::make_pair(new_range, item));
536 E : DCHECK(inserted.second);
537 E : if (ret_it != NULL)
538 i : *ret_it = inserted.first;
539 :
540 : return;
541 E : }
542 :
543 : template <typename AddressType, typename SizeType, typename ItemType>
544 E : bool AddressSpace<AddressType, SizeType, ItemType>::Remove(const Range& range) {
545 : // We can't remove empty ranges.
546 E : if (range.IsEmpty())
547 E : return false;
548 :
549 E : RangeMap::iterator it = ranges_.find(range);
550 E : if (it == ranges_.end())
551 E : return false;
552 :
553 E : ranges_.erase(it);
554 E : return true;
555 E : }
556 :
557 : template <typename AddressType, typename SizeType, typename ItemType>
558 : typename AddressSpace<AddressType, SizeType, ItemType>::RangeMap::const_iterator
559 : AddressSpace<AddressType, SizeType, ItemType>::FindFirstIntersection(
560 E : const Range& range) const {
561 E : return const_cast<AddressSpace*>(this)->FindFirstIntersection(range);
562 E : }
563 :
564 : template <typename AddressType, typename SizeType, typename ItemType>
565 : typename AddressSpace<AddressType, SizeType, ItemType>::RangeMap::iterator
566 : AddressSpace<AddressType, SizeType, ItemType>::FindFirstIntersection(
567 E : const Range& range) {
568 : // Empty items do not exist in the address-space.
569 E : if (range.IsEmpty())
570 E : return ranges_.end();
571 :
572 E : RangeMap::iterator it(ranges_.lower_bound(range));
573 :
574 : // There are three cases we need to handle here:
575 : // 1. An exact match.
576 E : if (it != ranges_.end() && it->first == range)
577 E : return it;
578 :
579 : // 2. Intersection with the next earlier (lower address or shorter) range.
580 : // Back up one if we can and test for intersection.
581 E : if (it != ranges_.begin()) {
582 E : RangeMap::iterator prev(it);
583 E : --prev;
584 :
585 E : if (prev->first.Intersects(range))
586 E : return prev;
587 : }
588 :
589 : // 3. Intersection to a/the found block.
590 E : if (it != ranges_.end() && it->first.Intersects(range))
591 E : return it;
592 :
593 E : return ranges_.end();
594 E : }
595 :
596 : template <typename AddressType, typename SizeType, typename ItemType>
597 : typename AddressSpace<AddressType, SizeType, ItemType>::RangeMapConstIterPair
598 : AddressSpace<AddressType, SizeType, ItemType>::FindIntersecting(
599 E : const Range& range) const {
600 E : return const_cast<AddressSpace*>(this)->FindIntersecting(range);
601 E : }
602 :
603 : template <typename AddressType, typename SizeType, typename ItemType>
604 : typename AddressSpace<AddressType, SizeType, ItemType>::RangeMapIterPair
605 : AddressSpace<AddressType, SizeType, ItemType>::FindIntersecting(
606 E : const Range& range) {
607 : // Empty ranges find nothing.
608 E : if (range.IsEmpty())
609 E : return std::make_pair(ranges_.end(), ranges_.end());
610 :
611 : // Find the start of the range first.
612 E : RangeMap::iterator begin(FindFirstIntersection(range));
613 :
614 : // Then the end.
615 : RangeMap::iterator end(ranges_.lower_bound(
616 E : Range(range.start() + range.size(), 1)));
617 :
618 : // Ensure that the relationship begin <= end holds, so that we may always
619 : // iterate over the returned range. It is possible that begin == end(),
620 : // and end != end(), which can cause problems. This is specifically the case
621 : // when there is no intersection with @p range, but that there is at least
622 : // one range beyond @p range.
623 E : if (begin == ranges_.end())
624 E : begin = end;
625 :
626 : // Since we search for the first range that starts at or after the end
627 : // of the input range, the range we find should never be intersecting.
628 E : DCHECK(end == ranges_.end() || !end->first.Intersects(range));
629 :
630 E : return std::make_pair(begin, end);
631 E : }
632 :
633 : template <typename AddressType, typename SizeType, typename ItemType>
634 : bool AddressSpace<AddressType, SizeType, ItemType>::Intersects(
635 E : const Range& range) const {
636 E : RangeMapConstIterPair its = FindIntersecting(range);
637 E : return (its.first != its.second);
638 E : }
639 :
640 : template <typename AddressType, typename SizeType, typename ItemType>
641 : bool AddressSpace<AddressType, SizeType, ItemType>::ContainsExactly(
642 E : const Range& range) const {
643 E : RangeMapConstIterPair its = FindIntersecting(range);
644 E : if (its.first == its.second)
645 E : return false;
646 E : return its.first->first == range;
647 E : }
648 :
649 : template <typename AddressType, typename SizeType, typename ItemType>
650 : bool AddressSpace<AddressType, SizeType, ItemType>::Contains(
651 E : const Range& range) const {
652 E : RangeMapConstIterPair its = FindIntersecting(range);
653 E : if (its.first == its.second)
654 E : return false;
655 E : return its.first->first.Contains(range);
656 E : }
657 :
658 : template <typename AddressType, typename SizeType, typename ItemType>
659 : typename AddressSpace<AddressType, SizeType, ItemType>::RangeMap::const_iterator
660 : AddressSpace<AddressType, SizeType, ItemType>::FindContaining(
661 E : const Range& range) const {
662 : // If there is a containing range, it must be the first intersection.
663 E : RangeMap::const_iterator it(FindFirstIntersection(range));
664 E : if (it != ranges_.end() && it->first.Contains(range))
665 E : return it;
666 :
667 E : return ranges_.end();
668 E : }
669 :
670 : template <typename AddressType, typename SizeType, typename ItemType>
671 : typename AddressSpace<AddressType, SizeType, ItemType>::RangeMap::iterator
672 : AddressSpace<AddressType, SizeType, ItemType>::FindContaining(
673 E : const Range& range) {
674 : // If there is a containing range, it must be the first intersection.
675 E : RangeMap::iterator it(FindFirstIntersection(range));
676 E : if (it != ranges_.end() && it->first.Contains(range))
677 E : return it;
678 :
679 E : return ranges_.end();
680 E : }
681 :
682 : template <typename SourceRangeType, typename DestinationRangeType>
683 : const std::pair<SourceRangeType, DestinationRangeType>*
684 : AddressRangeMap<SourceRangeType, DestinationRangeType>::FindRangePair(
685 E : const SourceRange& src_range) const {
686 : // No empty range exists in the mapping.
687 E : if (src_range.IsEmpty())
688 E : return NULL;
689 :
690 : // Find the first existing source range that is not less than src_range.
691 : // The returned iterator either intersects src_range, or is strictly greater
692 : // than it.
693 E : RangePairs::const_iterator it = LowerBound(src_range);
694 :
695 E : if (it == range_pairs_.end())
696 E : return NULL;
697 E : if (it->first.Contains(src_range))
698 E : return &(*it);
699 E : return NULL;
700 E : }
701 :
702 : template <typename SourceRangeType, typename DestinationRangeType>
703 : bool AddressRangeMap<SourceRangeType, DestinationRangeType>::IsMapped(
704 E : const SourceRange& src_range) const {
705 : // By definition no empty range is mapped.
706 E : if (src_range.IsEmpty())
707 E : return false;
708 :
709 : // Find the first existing source range that is not less than src_range.
710 : // The returned iterator either intersects src_range, or is strictly greater
711 : // than it.
712 E : RangePairs::const_iterator it = LowerBound(src_range);
713 :
714 : // Step through the successive mapped ranges and see if they cover src_range.
715 E : typename SourceRange::Address position = src_range.start();
716 E : while (true) {
717 : // No more mapped source ranges? Then src_range is not covered.
718 E : if (it == range_pairs_.end())
719 i : return false;
720 :
721 : // Is there an uncovered gap between position and the next mapped source
722 : // range? Then src_range is not covered.
723 E : if (position < it->first.start())
724 E : return false;
725 :
726 : // Step over this mapped source range and see if we're completely covered.
727 E : position = it->first.end();
728 E : if (position >= src_range.end())
729 E : return true;
730 :
731 E : ++it;
732 E : }
733 E : }
734 :
735 : template <typename SourceRangeType, typename DestinationRangeType>
736 : bool AddressRangeMap<SourceRangeType, DestinationRangeType>::Insert(
737 E : const SourceRange& src_range, const DestinationRange& dst_range) {
738 : // No empty ranges may be inserted in the mapping.
739 E : if (src_range.IsEmpty() || dst_range.IsEmpty())
740 E : return false;
741 :
742 : // Find the first existing source range that is not less than src_range.
743 : RangePairs::iterator it = std::lower_bound(
744 : range_pairs_.begin(),
745 : range_pairs_.end(),
746 : std::make_pair(src_range, dst_range),
747 E : internal::RangePairLess<SourceRange, DestinationRange>());
748 :
749 : // The search fell off the end of the vector? Push it to the back.
750 E : if (it == range_pairs_.end())
751 E : return Push(src_range, dst_range);
752 :
753 : // Does this source range overlap at all with the existing one?
754 E : if (it->first.Intersects(src_range))
755 E : return false;
756 :
757 : // At this point we know that 'it' points to a source range that is greater
758 : // than src_range. There are now 4 possibilities:
759 : // 1. It can be merged with the source range to the left, at 'it - 1'.
760 : // 2. It can be merged with the source range to the right, at 'it'.
761 : // 3. It can be merged with both the source range to the left and the right.
762 : // 4. It can't be merged at all, and needs to be inserted.
763 :
764 : // Determine in which directions we need to merge.
765 E : bool merge_left = false;
766 E : bool merge_right = false;
767 E : if (src_range.size() == dst_range.size()) {
768 : // If there is an element to the left, see if we can merge with it.
769 E : if (it != range_pairs_.begin()) {
770 E : RangePairs::iterator it_left = it - 1;
771 : if (it_left->first.size() == it_left->second.size() &&
772 : it_left->first.end() == src_range.start() &&
773 E : it_left->second.end() == dst_range.start()) {
774 E : merge_left = true;
775 : }
776 : }
777 :
778 : if (it->first.size() == it->second.size() &&
779 : src_range.end() == it->first.start() &&
780 E : dst_range.end() == it->second.start()) {
781 E : merge_right = true;
782 : }
783 : }
784 :
785 : // Don't need to change sizes because we're merging in only one direction?
786 E : if (merge_left != merge_right) {
787 E : SourceRange merged_src_range;
788 E : DestinationRange merged_dst_range;
789 E : if (merge_left) {
790 E : --it;
791 : merged_src_range = SourceRange(it->first.start(),
792 E : it->first.size() + src_range.size());
793 : merged_dst_range = DestinationRange(it->second.start(),
794 E : it->second.size() + dst_range.size());
795 E : } else {
796 : merged_src_range = SourceRange(src_range.start(),
797 E : src_range.size() + it->first.size());
798 : merged_dst_range = DestinationRange(dst_range.start(),
799 E : dst_range.size() + it->second.size());
800 : }
801 :
802 E : *it = std::make_pair(merged_src_range, merged_dst_range);
803 E : return true;
804 : }
805 :
806 : // Merging in both directions and shrinking?
807 E : if (merge_left && merge_right) {
808 E : RangePairs::iterator it_left = it - 1;
809 :
810 : SourceRange merged_src_range(
811 : it_left->first.start(),
812 E : it_left->first.size() + src_range.size() + it->first.size());
813 : DestinationRange merged_dst_range(
814 : it_left->second.start(),
815 E : it_left->second.size() + dst_range.size() + it->second.size());
816 :
817 E : *it_left = std::make_pair(merged_src_range, merged_dst_range);
818 E : range_pairs_.erase(it);
819 E : return true;
820 : }
821 :
822 : // If we get here then we're growing.
823 E : range_pairs_.insert(it, std::make_pair(src_range, dst_range));
824 E : return true;
825 E : }
826 :
827 : template <typename SourceRangeType, typename DestinationRangeType>
828 : bool AddressRangeMap<SourceRangeType, DestinationRangeType>::Push(
829 E : const SourceRange& src_range, const DestinationRange& dst_range) {
830 : // We can't insert empty ranges.
831 E : if (src_range.IsEmpty() || dst_range.IsEmpty())
832 E : return false;
833 :
834 E : if (!range_pairs_.empty()) {
835 E : SourceRange& last_src_range = range_pairs_.back().first;
836 :
837 : // If we already have RangePairs in the list, then src_range must be beyond
838 : // the last SourceRange.
839 E : if (!(last_src_range < src_range) || last_src_range.Intersects(src_range))
840 E : return false;
841 :
842 : // Can we merge this new pair of ranges with the existing last pair of
843 : // ranges?
844 E : DestinationRange& last_dst_range = range_pairs_.back().second;
845 : if (last_src_range.size() == last_dst_range.size() &&
846 : src_range.size() == dst_range.size() &&
847 : last_src_range.end() == src_range.start() &&
848 E : last_dst_range.end() == dst_range.start()) {
849 : last_src_range = SourceRange(
850 E : last_src_range.start(), last_src_range.size() + src_range.size());
851 : last_dst_range = DestinationRange(
852 E : last_dst_range.start(), last_dst_range.size() + dst_range.size());
853 E : return true;
854 : }
855 : }
856 :
857 E : range_pairs_.push_back(std::make_pair(src_range, dst_range));
858 E : return true;
859 E : }
860 :
861 : template <typename SourceRangeType, typename DestinationRangeType>
862 : size_t AddressRangeMap<SourceRangeType, DestinationRangeType>::ComputeInverse(
863 E : AddressRangeMap<DestinationRangeType, SourceRangeType>* inverted) const {
864 E : DCHECK(inverted != NULL);
865 :
866 : // Get a list of inverted range pairs.
867 : std::vector<std::pair<DestinationRangeType, SourceRangeType>>
868 E : inverted_range_pairs;
869 E : inverted_range_pairs.reserve(range_pairs_.size());
870 E : for (size_t i = 0; i < range_pairs_.size(); ++i) {
871 : inverted_range_pairs.push_back(
872 E : std::make_pair(range_pairs_[i].second, range_pairs_[i].first));
873 E : }
874 :
875 : // We sort these with a custom sort functor so that a total ordering is
876 : // defined rather than the default partial ordering defined by AddressRange.
877 : std::sort(inverted_range_pairs.begin(),
878 : inverted_range_pairs.end(),
879 : internal::CompleteAddressRangePairLess<DestinationRangeType,
880 E : SourceRangeType>());
881 :
882 : // Push these back to the inverted address range map and count the conflicts.
883 E : size_t conflicts = 0;
884 E : inverted->clear();
885 E : for (size_t i = 0; i < inverted_range_pairs.size(); ++i) {
886 : if (!inverted->Push(inverted_range_pairs[i].first,
887 E : inverted_range_pairs[i].second)) {
888 E : ++conflicts;
889 : }
890 E : }
891 :
892 E : return conflicts;
893 E : }
894 :
895 : template <typename SourceRangeType, typename DestinationRangeType>
896 : typename AddressRangeMap<SourceRangeType, DestinationRangeType>::RangePairs::
897 : const_iterator
898 : AddressRangeMap<SourceRangeType, DestinationRangeType>::LowerBound(
899 E : const SourceRange& src_range) const {
900 : return std::lower_bound(
901 : range_pairs_.begin(),
902 : range_pairs_.end(),
903 : std::make_pair(src_range,
904 : // We have to manually create a valid DestinationRange with
905 : // a size > 0.
906 : DestinationRange(typename DestinationRange::Address(),
907 : 1)),
908 E : internal::RangePairLess<SourceRange, DestinationRange>());
909 E : }
910 :
911 : template <typename SourceRangeType, typename DestinationRangeType>
912 : void AddressRangeMap<SourceRangeType, DestinationRangeType>::
913 E : InsertUnmappedRange(const SourceRange& unmapped) {
914 : // Unmapping an empty range is a nop.
915 E : if (unmapped.IsEmpty())
916 E : return;
917 :
918 : typedef typename SourceRange::Size SrcSize;
919 : typedef typename DestinationRange::Size DstSize;
920 : typedef typename DestinationRange::Address DstAddr;
921 :
922 : // Walk backwards through the range pairs, fixing them as we go.
923 E : for (size_t i = range_pairs_.size(); i > 0; --i) {
924 E : RangePair& range_pair = range_pairs_[i - 1];
925 E : SourceRange& src = range_pair.first;
926 E : DestinationRange& dst = range_pair.second;
927 :
928 : // This range pair starts before the unmapped source range? We may have to
929 : // split it, but we can stop looking at earlier ranges.
930 E : if (src.start() < unmapped.start()) {
931 : // Do we need a split?
932 E : if (src.end() > unmapped.start()) {
933 : SrcSize src_size_before =
934 E : static_cast<SrcSize>(unmapped.start() - src.start());
935 : SrcSize src_size_after =
936 E : static_cast<SrcSize>(src.size() - src_size_before);
937 :
938 E : DstAddr dst_start_before = dst.start();
939 E : DstSize dst_size_before = src_size_before;
940 E : DstAddr dst_start_after(0);
941 E : DstSize dst_size_after(0);
942 :
943 : // Special case: The destination size is 1, so indivisible. In this
944 : // case we simply duplicate the destination range.
945 E : if (dst.size() == 1) {
946 E : dst_start_after = dst_start_before;
947 E : dst_size_after = dst_size_before;
948 E : } else {
949 : // If the destination range is smaller than the source range, it is
950 : // possible that dst_size_before consumes too much. In this case send
951 : // as much as possible to the left (so it is as close to linear as
952 : // possible), but leave some for the after the split.
953 E : if (dst_size_before >= dst.size()) {
954 i : dst_size_before = dst.size() - 1;
955 i : dst_size_after = 1;
956 : }
957 :
958 E : dst_start_after = dst_start_before + dst_size_before;
959 E : dst_size_after = static_cast<DstSize>(dst.size() - dst_size_before);
960 : }
961 :
962 : // Create the range for after the split.
963 : RangePair pair_after(
964 : SourceRange(src.start() + src_size_before + unmapped.size(),
965 : src_size_after),
966 E : DestinationRange(dst_start_after, dst_size_after));
967 :
968 : // Fix the existing pair, which is now the pair before the split.
969 E : src = SourceRange(src.start(), src_size_before);
970 E : dst = DestinationRange(dst_start_before, dst_size_before);
971 :
972 : // Insert the the new range. This invalidates range_pair, src and dst
973 : // hence the need to do it at the very end.
974 E : range_pairs_.insert(range_pairs_.begin() + i, pair_after);
975 : }
976 :
977 E : return;
978 : }
979 :
980 : // Shift this range to the right.
981 E : src = SourceRange(src.start() + unmapped.size(), src.size());
982 E : }
983 E : }
984 :
985 : template <typename SourceRangeType, typename DestinationRangeType>
986 : void AddressRangeMap<SourceRangeType, DestinationRangeType>::
987 E : RemoveMappedRange(const SourceRange& mapped) {
988 : // Removing an empty range is a nop.
989 E : if (mapped.IsEmpty())
990 E : return;
991 :
992 : typedef typename SourceRange::Size SrcSize;
993 : typedef typename DestinationRange::Size DstSize;
994 : typedef typename DestinationRange::Address DstAddr;
995 :
996 : // Special case: no source ranges to modify.
997 E : if (range_pairs_.size() == 0)
998 E : return;
999 :
1000 : // Walk backwards through the range pairs, fixing them as we go.
1001 E : size_t i = range_pairs_.size();
1002 E : for (; i > 0; --i) {
1003 E : RangePair& range_pair = range_pairs_[i - 1];
1004 E : SourceRange& src = range_pair.first;
1005 :
1006 : // This range pair starts before the end of the range we want to unmap?
1007 : // Then we've finished fixing ranges that simply need to be shifted.
1008 E : if (src.start() < mapped.end())
1009 E : break;
1010 :
1011 : // Shift this range to the left.
1012 E : src = SourceRange(src.start() - mapped.size(), src.size());
1013 E : }
1014 :
1015 : // At this point we've found the first range that is not beyond the
1016 : // end of mapped. Now we want to find the first range that is completely
1017 : // before mapped.
1018 E : size_t end_affected_ranges = i;
1019 E : for (; i > 0; --i) {
1020 E : RangePair& range_pair = range_pairs_[i - 1];
1021 E : SourceRange& src = range_pair.first;
1022 :
1023 E : if (src.end() <= mapped.start())
1024 E : break;
1025 E : }
1026 E : size_t begin_affected_ranges = i;
1027 :
1028 : // It's possible that the affected ranges are off the end of the vector,
1029 : // in which case there is absolutely nothing to do.
1030 E : if (begin_affected_ranges >= range_pairs_.size())
1031 E : return;
1032 :
1033 : // At this point the ith through (end_affected_ranges - 1)th ranges intersect
1034 : // the range to be removed. The two endpoints may need to be split, but
1035 : // everything between them needs to be deleted. We inspect each endpoint and
1036 : // split them if need be.
1037 :
1038 : // Does the ith range need to split?
1039 E : if (range_pairs_[begin_affected_ranges].first.start() < mapped.start()) {
1040 E : RangePair& range_pair = range_pairs_[begin_affected_ranges];
1041 E : SourceRange& src = range_pair.first;
1042 E : DestinationRange& dst = range_pair.second;
1043 :
1044 E : SrcSize src_size_left = mapped.start() - src.start();
1045 E : DstSize dst_size_left = src_size_left;
1046 E : if (dst_size_left > dst.size())
1047 i : dst_size_left = dst.size();
1048 :
1049 : // Special case: this element needs to be both left split and right split.
1050 : if (begin_affected_ranges == end_affected_ranges - 1 &&
1051 E : mapped.end() < src.end()) {
1052 : // Split in such as way as to prefer linear mappings. If being linear on
1053 : // the left leaves no destination range on the right, shuffle a byte
1054 : // between the two.
1055 E : SrcSize src_size_right = src.end() - mapped.end();
1056 E : DstSize dst_size_right = src_size_right;
1057 E : if (dst_size_left + dst_size_right > dst.size()) {
1058 i : dst_size_right = dst.size() - dst_size_left;
1059 i : if (dst_size_right == 0) {
1060 i : ++dst_size_right;
1061 i : --dst_size_left;
1062 : }
1063 : }
1064 E : DCHECK_GT(dst_size_left, 0u);
1065 E : DCHECK_GT(dst_size_right, 0u);
1066 E : DCHECK_LE(dst_size_left + dst_size_right, dst.size());
1067 E : DstAddr dst_start_right = dst.end() - dst_size_right;
1068 :
1069 E : src = SourceRange(src.start(), src_size_left);
1070 E : dst = DestinationRange(dst.start(), dst_size_left);
1071 :
1072 : // We do this last as it invalidates src and dst.
1073 : range_pairs_.insert(
1074 : range_pairs_.begin() + begin_affected_ranges + 1,
1075 : std::make_pair(SourceRange(mapped.start(), src_size_right),
1076 E : DestinationRange(dst_start_right, dst_size_right)));
1077 :
1078 E : return;
1079 : }
1080 :
1081 E : src = SourceRange(src.start(), src_size_left);
1082 E : dst = DestinationRange(dst.start(), dst_size_left);
1083 E : ++begin_affected_ranges;
1084 : }
1085 :
1086 : // Does the (end_affected_ranges - 1)th range need to be split?
1087 E : if (range_pairs_[end_affected_ranges - 1].first.end() > mapped.end()) {
1088 E : RangePair& range_pair = range_pairs_[end_affected_ranges - 1];
1089 E : SourceRange& src = range_pair.first;
1090 E : DestinationRange& dst = range_pair.second;
1091 :
1092 E : SrcSize src_size = src.end() - mapped.end();
1093 E : DstSize dst_size = src_size;
1094 E : if (dst_size > dst.size())
1095 i : dst_size = dst.size();
1096 :
1097 E : src = SourceRange(src.end() - src_size - mapped.size(), src_size);
1098 E : dst = DestinationRange(dst.end() - dst_size, dst_size);
1099 E : --end_affected_ranges;
1100 : }
1101 :
1102 : // Now we have that the ranges [begin_affected_ranges, end_affected_ranges)
1103 : // need to simply be erased.
1104 E : if (begin_affected_ranges < end_affected_ranges)
1105 : range_pairs_.erase(range_pairs_.begin() + begin_affected_ranges,
1106 E : range_pairs_.begin() + end_affected_ranges);
1107 E : }
1108 :
1109 : // An ostream operator for AddressRanges.
1110 : template<typename AddressType, typename SizeType>
1111 : std::ostream& operator<<(
1112 : std::ostream& str,
1113 E : const AddressRange<AddressType, SizeType>& range) {
1114 E : str << "AddressRange(" << range.start() << ", " << range.size() << ")";
1115 E : return str;
1116 E : }
1117 :
1118 : } // namespace core
1119 :
1120 : #endif // SYZYGY_CORE_ADDRESS_SPACE_H_
|