• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // Copyright (c) 2013 The Chromium OS Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #include "address_mapper.h"
6 
7 #include "base/logging.h"
8 
9 namespace quipper {
10 
AddressMapper(const AddressMapper & source)11 AddressMapper::AddressMapper(const AddressMapper& source) {
12   mappings_ = source.mappings_;
13 }
14 
Map(const uint64_t real_addr,const uint64_t size,const bool remove_existing_mappings)15 bool AddressMapper::Map(const uint64_t real_addr,
16                         const uint64_t size,
17                         const bool remove_existing_mappings) {
18   return MapWithID(real_addr, size, kuint64max, 0, remove_existing_mappings);
19 }
20 
MapWithID(const uint64_t real_addr,const uint64_t size,const uint64_t id,const uint64_t offset_base,bool remove_existing_mappings)21 bool AddressMapper::MapWithID(const uint64_t real_addr,
22                               const uint64_t size,
23                               const uint64_t id,
24                               const uint64_t offset_base,
25                               bool remove_existing_mappings) {
26   MappedRange range;
27   range.real_addr = real_addr;
28   range.size = size;
29   range.id = id;
30   range.offset_base = offset_base;
31 
32   if (size == 0) {
33     LOG(ERROR) << "Must allocate a nonzero-length address range.";
34     return false;
35   }
36 
37   // Check that this mapping does not overflow the address space.
38   if (real_addr + size - 1 != kuint64max &&
39       !(real_addr + size > real_addr)) {
40     DumpToLog();
41     LOG(ERROR) << "Address mapping at " << std::hex << real_addr
42                << " with size " << std::hex << size << " overflows.";
43     return false;
44   }
45 
46   // Check for collision with an existing mapping.  This must be an overlap that
47   // does not result in one range being completely covered by another
48   MappingList::iterator iter;
49   MappingList mappings_to_delete;
50   bool old_range_found = false;
51   MappedRange old_range;
52   for (iter = mappings_.begin(); iter != mappings_.end(); ++iter) {
53     if (!iter->Intersects(range))
54       continue;
55     // Quit if existing ranges that collide aren't supposed to be removed.
56     if (!remove_existing_mappings)
57       return false;
58     if (!old_range_found && iter->Covers(range) && iter->size > range.size) {
59       old_range_found = true;
60       old_range = *iter;
61       continue;
62     }
63     mappings_to_delete.push_back(*iter);
64   }
65 
66   while (!mappings_to_delete.empty()) {
67     const MappedRange& range = mappings_to_delete.front();
68     CHECK(Unmap(range));
69     mappings_to_delete.pop_front();
70   }
71 
72   // Otherwise check for this range being covered by another range.  If that
73   // happens, split or reduce the existing range to make room.
74   if (old_range_found) {
75     CHECK(Unmap(old_range));
76 
77     uint64_t gap_before = range.real_addr - old_range.real_addr;
78     uint64_t gap_after = (old_range.real_addr + old_range.size) -
79                          (range.real_addr + range.size);
80 
81     if (gap_before) {
82       CHECK(MapWithID(old_range.real_addr,
83                       gap_before,
84                       old_range.id,
85                       old_range.offset_base,
86                       false));
87     }
88 
89     CHECK(MapWithID(range.real_addr, range.size, id, offset_base, false));
90 
91     if (gap_after) {
92       CHECK(MapWithID(range.real_addr + range.size,
93                       gap_after,
94                       old_range.id,
95                       old_range.offset_base + gap_before + range.size,
96                       false));
97     }
98 
99     return true;
100   }
101 
102   // Now search for a location for the new range.  It should be in the first
103   // free block in quipper space.
104 
105   // If there is no existing mapping, add it to the beginning of quipper space.
106   if (mappings_.empty()) {
107     range.mapped_addr = 0;
108     range.unmapped_space_after = kuint64max - range.size;
109     mappings_.push_back(range);
110     return true;
111   }
112 
113   // If there is space before the first mapped range in quipper space, use it.
114   if (mappings_.begin()->mapped_addr >= range.size) {
115     range.mapped_addr = 0;
116     range.unmapped_space_after = mappings_.begin()->mapped_addr - range.size;
117     mappings_.push_front(range);
118     return true;
119   }
120 
121   // Otherwise, search through the existing mappings for a free block after one
122   // of them.
123   for (iter = mappings_.begin(); iter != mappings_.end(); ++iter) {
124     if (iter->unmapped_space_after < range.size)
125       continue;
126 
127     range.mapped_addr = iter->mapped_addr + iter->size;
128     range.unmapped_space_after = iter->unmapped_space_after - range.size;
129     iter->unmapped_space_after = 0;
130 
131     mappings_.insert(++iter, range);
132     return true;
133   }
134 
135   // If it still hasn't succeeded in mapping, it means there is no free space in
136   // quipper space large enough for a mapping of this size.
137   DumpToLog();
138   LOG(ERROR) << "Could not find space to map addr=" << std::hex << real_addr
139              << " with size " << std::hex << size;
140   return false;
141 }
142 
DumpToLog() const143 void AddressMapper::DumpToLog() const {
144   MappingList::const_iterator it;
145   for (it = mappings_.begin(); it != mappings_.end(); ++it) {
146     LOG(INFO) << " real_addr: " << std::hex << it->real_addr
147               << " mapped: " << std::hex << it->mapped_addr
148               << " id: " << std::hex << it->id
149               << " size: " << std::hex << it->size;
150   }
151 }
152 
GetMappedAddress(const uint64_t real_addr,uint64_t * mapped_addr) const153 bool AddressMapper::GetMappedAddress(const uint64_t real_addr,
154                                      uint64_t* mapped_addr) const {
155   CHECK(mapped_addr);
156   MappingList::const_iterator iter;
157   for (iter = mappings_.begin(); iter != mappings_.end(); ++iter) {
158     if (!iter->ContainsAddress(real_addr))
159       continue;
160     *mapped_addr = iter->mapped_addr + real_addr - iter->real_addr;
161     return true;
162   }
163   return false;
164 }
165 
GetMappedIDAndOffset(const uint64_t real_addr,uint64_t * id,uint64_t * offset) const166 bool AddressMapper::GetMappedIDAndOffset(const uint64_t real_addr,
167                                          uint64_t* id,
168                                          uint64_t* offset) const {
169   CHECK(id);
170   CHECK(offset);
171   MappingList::const_iterator iter;
172   for (iter = mappings_.begin(); iter != mappings_.end(); ++iter) {
173     if (!iter->ContainsAddress(real_addr))
174       continue;
175     *id = iter->id;
176     *offset = real_addr - iter->real_addr + iter->offset_base;
177     return true;
178   }
179   return false;
180 }
181 
GetMaxMappedLength() const182 uint64_t AddressMapper::GetMaxMappedLength() const {
183   if (IsEmpty())
184     return 0;
185 
186   uint64_t min = mappings_.begin()->mapped_addr;
187 
188   MappingList::const_iterator iter = mappings_.end();
189   --iter;
190   uint64_t max = iter->mapped_addr + iter->size;
191 
192   return max - min;
193 }
194 
Unmap(const MappedRange & range)195 bool AddressMapper::Unmap(const MappedRange& range) {
196   MappingList::iterator iter;
197   // TODO(sque): this is highly inefficient since Unmap() is called from a
198   // function that has already iterated to the right place within |mappings_|.
199   // For a first revision, I am sacrificing efficiency for of clarity, due to
200   // the trickiness of removing elements using iterators.
201   for (iter = mappings_.begin(); iter != mappings_.end(); ++iter) {
202     if (range.real_addr == iter->real_addr && range.size == iter->size) {
203       // Add the freed up space to the free space counter of the previous
204       // mapped region, if it exists.
205       if (iter != mappings_.begin()) {
206         --iter;
207         iter->unmapped_space_after += range.size + range.unmapped_space_after;
208         ++iter;
209       }
210       mappings_.erase(iter);
211       return true;
212     }
213   }
214   return false;
215 }
216 
217 }  // namespace quipper
218