1 : // Copyright 2012 Google Inc.
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 empy 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 : 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 E : bool Intersects(AddressType addr, SizeType size = 1) const {
241 E : return Intersects(AddressRange(addr, size));
242 E : }
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 succintly 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 that the relationship holds for the
306 : // pair [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 : 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 addressess 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 mathing 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 E : }
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 E : }
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 E : 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 E : }
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? Simply insert it.
796 E : if (it == range_pairs_.end()) {
797 E : range_pairs_.push_back(std::make_pair(src_range, dst_range));
798 E : return true;
799 : }
800 :
801 : // Does this source range overlap at all with the existing one?
802 E : if (it->first.Intersects(src_range))
803 E : return false;
804 :
805 : // At this point we know that 'it' points to a source range that is greater
806 : // than src_range. There are now 4 possibilities:
807 : // 1. It can be merged with the source range to the left, at 'it - 1'.
808 : // 2. It can be merged with the source range to the right, at 'it'.
809 : // 3. It can be merged with both the source range to the left and the right.
810 : // 4. It can't be merged at all, and needs to be inserted.
811 :
812 : // Determine in which directions we need to merge.
813 E : bool merge_left = false;
814 E : bool merge_right = false;
815 E : if (src_range.size() == dst_range.size()) {
816 : // If there is an element to the left, see if we can merge with it.
817 E : if (it != range_pairs_.begin()) {
818 E : RangePairs::iterator it_left = it - 1;
819 : if (it_left->first.size() == it_left->second.size() &&
820 : it_left->first.end() == src_range.start() &&
821 E : it_left->second.end() == dst_range.start()) {
822 E : merge_left = true;
823 : }
824 E : }
825 :
826 : if (it->first.size() == it->second.size() &&
827 : src_range.end() == it->first.start() &&
828 E : dst_range.end() == it->second.start()) {
829 E : merge_right = true;
830 : }
831 : }
832 :
833 : // Don't need to change sizes because we're merging in only one direction?
834 E : if (merge_left != merge_right) {
835 E : SourceRange merged_src_range;
836 E : DestinationRange merged_dst_range;
837 E : if (merge_left) {
838 E : it--;
839 : merged_src_range = SourceRange(it->first.start(),
840 E : it->first.size() + src_range.size());
841 : merged_dst_range = DestinationRange(it->second.start(),
842 E : it->second.size() + dst_range.size());
843 E : } else {
844 : merged_src_range = SourceRange(src_range.start(),
845 E : src_range.size() + it->first.size());
846 : merged_dst_range = DestinationRange(dst_range.start(),
847 E : dst_range.size() + it->second.size());
848 : }
849 :
850 E : *it = std::make_pair(merged_src_range, merged_dst_range);
851 E : return true;
852 : }
853 :
854 : // Merging in both directions and shrinking?
855 E : if (merge_left && merge_right) {
856 E : RangePairs::iterator it_left = it - 1;
857 :
858 : SourceRange merged_src_range(
859 : it_left->first.start(),
860 E : it_left->first.size() + src_range.size() + it->first.size());
861 : DestinationRange merged_dst_range(
862 : it_left->second.start(),
863 E : it_left->second.size() + dst_range.size() + it->second.size());
864 :
865 E : *it_left = std::make_pair(merged_src_range, merged_dst_range);
866 E : range_pairs_.erase(it);
867 E : return true;
868 : }
869 :
870 : // If we get here then we're growing.
871 E : range_pairs_.insert(it, std::make_pair(src_range, dst_range));
872 E : return true;
873 E : }
874 :
875 : template <typename SourceRangeType, typename DestinationRangeType>
876 : bool AddressRangeMap<SourceRangeType, DestinationRangeType>::Push(
877 E : const SourceRange& src_range, const DestinationRange& dst_range) {
878 E : if (!range_pairs_.empty()) {
879 E : SourceRange& last_src_range = range_pairs_.back().first;
880 :
881 : // If we already have RangePairs in the list, then src_range must be beyond
882 : // the last SourceRange.
883 E : if (!(last_src_range < src_range) || last_src_range.Intersects(src_range))
884 E : return false;
885 :
886 : // Can we merge this new pair of ranges with the existing last pair of
887 : // ranges?
888 E : DestinationRange& last_dst_range = range_pairs_.back().second;
889 : if (last_src_range.size() == last_dst_range.size() &&
890 : src_range.size() == dst_range.size() &&
891 : last_src_range.end() == src_range.start() &&
892 E : last_dst_range.end() == dst_range.start()) {
893 : last_src_range = SourceRange(
894 E : last_src_range.start(), last_src_range.size() + src_range.size());
895 : last_dst_range = DestinationRange(
896 E : last_dst_range.start(), last_dst_range.size() + dst_range.size());
897 E : return true;
898 : }
899 : }
900 :
901 E : range_pairs_.push_back(std::make_pair(src_range, dst_range));
902 E : return true;
903 E : }
904 :
905 : template <typename SourceRangeType, typename DestinationRangeType>
906 : size_t AddressRangeMap<SourceRangeType, DestinationRangeType>::ComputeInverse(
907 E : AddressRangeMap<DestinationRangeType, SourceRangeType>* inverted) const {
908 E : DCHECK(inverted != NULL);
909 :
910 : // Get a list of inverted range pairs.
911 : std::vector<std::pair<DestinationRangeType, SourceRangeType>>
912 E : inverted_range_pairs;
913 E : inverted_range_pairs.reserve(range_pairs_.size());
914 E : for (size_t i = 0; i < range_pairs_.size(); ++i) {
915 : inverted_range_pairs.push_back(
916 E : std::make_pair(range_pairs_[i].second, range_pairs_[i].first));
917 E : }
918 :
919 : // We sort these with a custom sort functor so that a total ordering is
920 : // defined rather than the default partial ordering defined by AddressRange.
921 : std::sort(inverted_range_pairs.begin(),
922 : inverted_range_pairs.end(),
923 : internal::CompleteAddressRangePairLess<DestinationRangeType,
924 E : SourceRangeType>());
925 :
926 : // Push these back to the inverted address range map and count the conflicts.
927 E : size_t conflicts = 0;
928 E : inverted->clear();
929 E : for (size_t i = 0; i < inverted_range_pairs.size(); ++i) {
930 : if (!inverted->Push(inverted_range_pairs[i].first,
931 E : inverted_range_pairs[i].second)) {
932 E : ++conflicts;
933 : }
934 E : }
935 :
936 E : return conflicts;
937 E : }
938 :
939 : template <typename SourceRangeType, typename DestinationRangeType>
940 : typename AddressRangeMap<SourceRangeType, DestinationRangeType>::RangePairs::
941 : const_iterator
942 : AddressRangeMap<SourceRangeType, DestinationRangeType>::LowerBound(
943 E : const SourceRange& src_range) const {
944 : return std::lower_bound(
945 : range_pairs_.begin(),
946 : range_pairs_.end(),
947 : std::make_pair(src_range,
948 : // We have to manually create a valid DestinationRange with
949 : // a size > 0.
950 : DestinationRange(typename DestinationRange::Address(),
951 : 1)),
952 E : internal::RangePairLess<SourceRange, DestinationRange>());
953 E : }
954 :
955 : template <typename SourceRangeType, typename DestinationRangeType>
956 : void AddressRangeMap<SourceRangeType, DestinationRangeType>::
957 E : InsertUnmappedRange(const SourceRange& unmapped) {
958 : typedef typename SourceRange::Size SrcSize;
959 : typedef typename DestinationRange::Size DstSize;
960 : typedef typename DestinationRange::Address DstAddr;
961 :
962 : // Walk backwards through the range pairs, fixing them as we go.
963 E : for (size_t i = range_pairs_.size(); i > 0; --i) {
964 E : RangePair& range_pair = range_pairs_[i - 1];
965 E : SourceRange& src = range_pair.first;
966 E : DestinationRange& dst = range_pair.second;
967 :
968 : // This range pair starts before the unmapped source range? We may have to
969 : // split it, but we can stop looking at earlier ranges.
970 E : if (src.start() < unmapped.start()) {
971 : // Do we need a split?
972 E : if (src.end() > unmapped.start()) {
973 : SrcSize src_size_before =
974 E : static_cast<SrcSize>(unmapped.start() - src.start());
975 : SrcSize src_size_after =
976 E : static_cast<SrcSize>(src.size() - src_size_before);
977 :
978 E : DstAddr dst_start_before = dst.start();
979 E : DstSize dst_size_before = src_size_before;
980 E : DstAddr dst_start_after(0);
981 E : DstSize dst_size_after(0);
982 :
983 : // Special case: The destination size is 1, so indivisible. In this
984 : // case we simply duplicate the destination range.
985 E : if (dst.size() == 1) {
986 E : dst_start_after = dst_start_before;
987 E : dst_size_after = dst_size_before;
988 E : } else {
989 : // If the destination range is smaller than the source range, it is
990 : // possible that dst_size_before consumes too much. In this case send
991 : // as much as possible to the left (so it is as close to linear as
992 : // possible), but leave some for the after the split.
993 E : if (dst_size_before >= dst.size()) {
994 i : dst_size_before = dst.size() - 1;
995 i : dst_size_after = 1;
996 : }
997 :
998 E : dst_start_after = dst_start_before + dst_size_before;
999 E : dst_size_after = static_cast<DstSize>(dst.size() - dst_size_before);
1000 : }
1001 :
1002 : // Create the range for after the split.
1003 : RangePair pair_after(
1004 : SourceRange(src.start() + src_size_before + unmapped.size(),
1005 : src_size_after),
1006 E : DestinationRange(dst_start_after, dst_size_after));
1007 :
1008 : // Fix the existing pair, which is now the pair before the split.
1009 E : src = SourceRange(src.start(), src_size_before);
1010 E : dst = DestinationRange(dst_start_before, dst_size_before);
1011 :
1012 : // Insert the the new range. This invalidates range_pair, src and dst
1013 : // hence the need to do it at the very end.
1014 E : range_pairs_.insert(range_pairs_.begin() + i, pair_after);
1015 : }
1016 :
1017 E : return;
1018 : }
1019 :
1020 : // Shift this range to the right.
1021 E : src = SourceRange(src.start() + unmapped.size(), src.size());
1022 E : }
1023 E : }
1024 :
1025 : template <typename SourceRangeType, typename DestinationRangeType>
1026 : void AddressRangeMap<SourceRangeType, DestinationRangeType>::
1027 E : RemoveMappedRange(const SourceRange& mapped) {
1028 : typedef typename SourceRange::Size SrcSize;
1029 : typedef typename DestinationRange::Size DstSize;
1030 : typedef typename DestinationRange::Address DstAddr;
1031 :
1032 : // Special case: no source ranges to modify.
1033 E : if (range_pairs_.size() == 0)
1034 E : return;
1035 :
1036 : // Walk backwards through the range pairs, fixing them as we go.
1037 E : size_t i = range_pairs_.size();
1038 E : for (; i > 0; --i) {
1039 E : RangePair& range_pair = range_pairs_[i - 1];
1040 E : SourceRange& src = range_pair.first;
1041 E : DestinationRange& dst = range_pair.second;
1042 :
1043 : // This range pair starts before the end of the range we want to unmap? Then
1044 : // we've finished fixing ranges that simply need to be shifted.
1045 E : if (src.start() < mapped.end())
1046 E : break;
1047 :
1048 : // Shift this range to the left.
1049 E : src = SourceRange(src.start() - mapped.size(), src.size());
1050 E : }
1051 :
1052 : // At this point we've found the first range that is not beyond the
1053 : // end of mapped. Now we want to find the first range that is completely
1054 : // before mapped.
1055 E : size_t end_affected_ranges = i;
1056 E : for (; i > 0; --i) {
1057 E : RangePair& range_pair = range_pairs_[i - 1];
1058 E : SourceRange& src = range_pair.first;
1059 E : DestinationRange& dst = range_pair.second;
1060 :
1061 E : if (src.end() <= mapped.start())
1062 E : break;
1063 E : }
1064 E : size_t begin_affected_ranges = i;
1065 :
1066 : // It's possible that the affected ranges are off the end of the vector,
1067 : // in which case there is absolutely nothing to do.
1068 E : if (begin_affected_ranges >= range_pairs_.size())
1069 E : return;
1070 :
1071 : // At this point the ith through (end_affected_ranges - 1)th ranges intersect
1072 : // the range to be removed. The two endpoints may need to be split, but
1073 : // everything between them needs to be deleted. We inspect each endpoint and
1074 : // split them if need be.
1075 :
1076 : // Does the ith range need to split?
1077 E : if (range_pairs_[begin_affected_ranges].first.start() < mapped.start()) {
1078 E : RangePair& range_pair = range_pairs_[begin_affected_ranges];
1079 E : SourceRange& src = range_pair.first;
1080 E : DestinationRange& dst = range_pair.second;
1081 :
1082 E : SrcSize src_size_left = mapped.start() - src.start();
1083 E : DstSize dst_size_left = src_size_left;
1084 E : if (dst_size_left > dst.size())
1085 i : dst_size_left = dst.size();
1086 :
1087 : // Special case: this element needs to be both left split and right split.
1088 : if (begin_affected_ranges == end_affected_ranges - 1 &&
1089 E : mapped.end() < src.end()) {
1090 : // Split in such as way as to prefer linear mappings. If being linear on
1091 : // the left leaves no destination range on the right, shuffle a byte
1092 : // between the two.
1093 E : SrcSize src_size_right = src.end() - mapped.end();
1094 E : DstSize dst_size_right = src_size_right;
1095 E : if (dst_size_left + dst_size_right > dst.size()) {
1096 i : dst_size_right = dst.size() - dst_size_left;
1097 i : if (dst_size_right == 0) {
1098 i : ++dst_size_right;
1099 i : --dst_size_left;
1100 : }
1101 : }
1102 E : DCHECK_GT(dst_size_left, 0u);
1103 E : DCHECK_GT(dst_size_right, 0u);
1104 E : DCHECK_LE(dst_size_left + dst_size_right, dst.size());
1105 E : DstAddr dst_start_right = dst.end() - dst_size_right;
1106 :
1107 E : src = SourceRange(src.start(), src_size_left);
1108 E : dst = DestinationRange(dst.start(), dst_size_left);
1109 :
1110 : // We do this last as it invalidates src and dst.
1111 : range_pairs_.insert(
1112 : range_pairs_.begin() + begin_affected_ranges + 1,
1113 : std::make_pair(SourceRange(mapped.start(), src_size_right),
1114 E : DestinationRange(dst_start_right, dst_size_right)));
1115 :
1116 E : return;
1117 : }
1118 :
1119 E : src = SourceRange(src.start(), src_size_left);
1120 E : dst = DestinationRange(dst.start(), dst_size_left);
1121 E : ++begin_affected_ranges;
1122 : }
1123 :
1124 : // Does the (end_affected_ranges - 1)th range need to be split?
1125 E : if (range_pairs_[end_affected_ranges - 1].first.end() > mapped.end()) {
1126 E : RangePair& range_pair = range_pairs_[end_affected_ranges - 1];
1127 E : SourceRange& src = range_pair.first;
1128 E : DestinationRange& dst = range_pair.second;
1129 :
1130 E : SrcSize src_size = src.end() - mapped.end();
1131 E : DstSize dst_size = src_size;
1132 E : if (dst_size > dst.size())
1133 i : dst_size = dst.size();
1134 :
1135 E : src = SourceRange(src.end() - src_size - mapped.size(), src_size);
1136 E : dst = DestinationRange(dst.end() - dst_size, dst_size);
1137 E : --end_affected_ranges;
1138 : }
1139 :
1140 : // Now we have that the ranges [begin_affected_ranges, end_affected_ranges)
1141 : // need to simply be erased.
1142 E : if (begin_affected_ranges < end_affected_ranges)
1143 : range_pairs_.erase(range_pairs_.begin() + begin_affected_ranges,
1144 E : range_pairs_.begin() + end_affected_ranges);
1145 E : }
1146 :
1147 : // An ostream operator for AddressRanges.
1148 : template<typename AddressType, typename SizeType>
1149 : std::ostream& operator<<(
1150 : std::ostream& str,
1151 E : const AddressRange<AddressType, SizeType>& range) {
1152 E : str << "AddressRange(" << range.start() << ", " << range.size() << ")";
1153 E : return str;
1154 E : }
1155 :
1156 : } // namespace core
1157 :
1158 : #endif // SYZYGY_CORE_ADDRESS_SPACE_H_
|