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