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