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
9namespace quipper {
10
11AddressMapper::AddressMapper(const AddressMapper& source) {
12  mappings_ = source.mappings_;
13}
14
15bool 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
21bool 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
143void 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
153bool 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
166bool 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
182uint64_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
195bool 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