1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/libexec/lib/src/memory_area.cc Wed Mar 15 00:33:40 2023 +0100
1.3 @@ -0,0 +1,434 @@
1.4 +/*
1.5 + * Memory area functionality.
1.6 + *
1.7 + * Copyright (C) 2022, 2023 Paul Boddie <paul@boddie.org.uk>
1.8 + *
1.9 + * This program is free software; you can redistribute it and/or
1.10 + * modify it under the terms of the GNU General Public License as
1.11 + * published by the Free Software Foundation; either version 2 of
1.12 + * the License, or (at your option) any later version.
1.13 + *
1.14 + * This program is distributed in the hope that it will be useful,
1.15 + * but WITHOUT ANY WARRANTY; without even the implied warranty of
1.16 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
1.17 + * GNU General Public License for more details.
1.18 + *
1.19 + * You should have received a copy of the GNU General Public License
1.20 + * along with this program; if not, write to the Free Software
1.21 + * Foundation, Inc., 51 Franklin Street, Fifth Floor,
1.22 + * Boston, MA 02110-1301, USA
1.23 + */
1.24 +
1.25 +#include <l4/re/c/rm.h>
1.26 +
1.27 +#include <mem/memory_utils.h>
1.28 +
1.29 +#include "mapped_region.h"
1.30 +
1.31 +
1.32 +
1.33 +/* Copy an area. */
1.34 +
1.35 +MemoryArea *MemoryArea::copy()
1.36 +{
1.37 + return new MemoryArea(_start, _end);
1.38 +}
1.39 +
1.40 +/* In general, a region cannot support other regions. */
1.41 +
1.42 +long MemoryArea::add(MemoryArea &area)
1.43 +{
1.44 + (void) area;
1.45 + return -L4_EPERM;
1.46 +}
1.47 +
1.48 +long MemoryArea::remove(MemoryArea &area)
1.49 +{
1.50 + (void) area;
1.51 + return -L4_EPERM;
1.52 +}
1.53 +
1.54 +/* In general, a region supports a memory access within its bounds. */
1.55 +
1.56 +long MemoryArea::find(address_t addr, MemoryArea **area)
1.57 +{
1.58 + if ((addr >= _start) && (addr < _end))
1.59 + {
1.60 + *area = this;
1.61 + return L4_EOK;
1.62 + }
1.63 + else
1.64 + return -L4_ENOMEM;
1.65 +}
1.66 +
1.67 +/* In general, a region does not support the identification of a location for
1.68 + region insertion. */
1.69 +
1.70 +long MemoryArea::find(address_t *start, address_t *size, map_flags_t flags,
1.71 + unsigned char align, MemoryArea **area)
1.72 +{
1.73 + (void) start; (void) size; (void) flags; (void) align; (void) area;
1.74 + return -L4_ENOMEM;
1.75 +}
1.76 +
1.77 +
1.78 +
1.79 +/* Copy a reserved area. */
1.80 +
1.81 +MemoryArea *ReservedMemoryArea::copy()
1.82 +{
1.83 + return new ReservedMemoryArea(_start, _end);
1.84 +}
1.85 +
1.86 +/* A reserved area does not support any memory access. */
1.87 +
1.88 +long ReservedMemoryArea::find(address_t addr, MemoryArea **area)
1.89 +{
1.90 + (void) addr; (void) area;
1.91 + return -L4_ENOMEM;
1.92 +}
1.93 +
1.94 +
1.95 +
1.96 +/* Discard all allocated areas. */
1.97 +
1.98 +AvailableMemoryArea::~AvailableMemoryArea()
1.99 +{
1.100 + MemoryAreas::iterator it;
1.101 +
1.102 + for (it = _allocated.begin(); it != _allocated.end(); it++)
1.103 + delete *it;
1.104 +
1.105 + _allocated.clear();
1.106 +}
1.107 +
1.108 +/* Copy an unused available memory area. */
1.109 +
1.110 +MemoryArea *AvailableMemoryArea::copy()
1.111 +{
1.112 + return new AvailableMemoryArea(_start, _end);
1.113 +}
1.114 +
1.115 +/* Add an area. */
1.116 +
1.117 +long AvailableMemoryArea::add(MemoryArea &area)
1.118 +{
1.119 + MemoryArea *a = area.copy();
1.120 +
1.121 + _areas[area.area_start()] = a;
1.122 + _allocated.insert(a);
1.123 +
1.124 + return L4_EOK;
1.125 +}
1.126 +
1.127 +/* Remove an area. */
1.128 +
1.129 +long AvailableMemoryArea::remove(MemoryArea &area)
1.130 +{
1.131 + MemoryAreaMap::iterator it = _areas.find(area.area_start());
1.132 +
1.133 + if (it != _areas.end())
1.134 + {
1.135 + _areas.erase(it);
1.136 +
1.137 + MemoryAreas::iterator ita = _allocated.find(it->second);
1.138 +
1.139 + if (ita != _allocated.end())
1.140 + {
1.141 + delete *ita;
1.142 + _allocated.erase(ita);
1.143 + }
1.144 + }
1.145 +
1.146 + return L4_EOK;
1.147 +}
1.148 +
1.149 +/* Find an region able to support a memory access. */
1.150 +
1.151 +long AvailableMemoryArea::find(address_t addr, MemoryArea **area)
1.152 +{
1.153 + MemoryAreaMap::iterator it = _areas.upper_bound(addr);
1.154 +
1.155 + /* Consider any area preceding or encompassing the desired address. */
1.156 +
1.157 + if (it != _areas.begin())
1.158 + {
1.159 + it--;
1.160 +
1.161 + /* Test whether the desired region start is encompassed by the preceding
1.162 + area. */
1.163 +
1.164 + MemoryArea *r = it->second;
1.165 +
1.166 + if (r->supports(addr))
1.167 + return r->find(addr, area);
1.168 + }
1.169 +
1.170 + /* Otherwise, no area within this area supports the address. */
1.171 +
1.172 + return -L4_ENOMEM;
1.173 +}
1.174 +
1.175 +/* Find an area suitable for attaching a memory region. */
1.176 +
1.177 +long AvailableMemoryArea::find(address_t *start, address_t *size,
1.178 + map_flags_t flags, unsigned char align,
1.179 + MemoryArea **area)
1.180 +{
1.181 + /* Obtain the alignment increment and a properly aligned size. */
1.182 +
1.183 + address_t increment = 1UL << align;
1.184 + address_t region_size = round(*size, increment);
1.185 +
1.186 + /* Align any desired location. */
1.187 +
1.188 + address_t region_start = trunc(*start, increment);
1.189 +
1.190 + /* Enforce a minimum address. */
1.191 +
1.192 + if (region_start < _start)
1.193 + region_start = round(_start, increment);
1.194 +
1.195 + /* Search for existing regions after the desired, conformant start address. */
1.196 +
1.197 + MemoryAreaMap::iterator it = _areas.upper_bound(region_start);
1.198 +
1.199 + /* Consider any area preceding or encompassing the desired address. */
1.200 +
1.201 + if (it != _areas.begin())
1.202 + {
1.203 + MemoryAreaMap::iterator next = it;
1.204 +
1.205 + /* Step back to the preceding area to get its details. */
1.206 +
1.207 + it--;
1.208 + MemoryArea *pr = it->second;
1.209 + it = next;
1.210 +
1.211 + /* Test whether the desired region start is encompassed by the preceding
1.212 + area. */
1.213 +
1.214 + if (region_start < pr->area_end())
1.215 + {
1.216 + /* Where the preceding area is mapped or a reserved area, adjust the start
1.217 + of any search range. If an exact request is made for a region, deny the
1.218 + request. */
1.219 +
1.220 + if (pr->is_mapped() || pr->is_reserved())
1.221 + {
1.222 + if (!(flags & L4RE_RM_F_SEARCH_ADDR))
1.223 + return -L4_ENOMEM;
1.224 +
1.225 + region_start = round(pr->area_end(), increment);
1.226 + }
1.227 +
1.228 + /* Where the preceding area is an area within which regions might be
1.229 + established, search within that area. */
1.230 +
1.231 + else
1.232 + return pr->find(start, size, flags, align, area);
1.233 + }
1.234 + }
1.235 +
1.236 + /* Consider the regions following the current region start candidate. */
1.237 +
1.238 + MemoryArea *r;
1.239 +
1.240 + while ((it != _areas.end()) && !(_end && ((region_start + region_size) > _end)))
1.241 + {
1.242 + r = it->second;
1.243 +
1.244 + /* Obtain the limit of available space being considered. */
1.245 +
1.246 + address_t end_limit = r->area_start();
1.247 +
1.248 + /* Test if not enough space exists between the preceding region (or start of
1.249 + memory) and the current region. */
1.250 +
1.251 + if ((region_start + region_size) > end_limit)
1.252 + {
1.253 + /* If an exact request is made for a region, deny the request. */
1.254 +
1.255 + if (!(flags & L4RE_RM_F_SEARCH_ADDR))
1.256 + return -L4_ENOMEM;
1.257 +
1.258 + /* Otherwise, investigate subsequent regions if not enough space exists
1.259 + between the preceding region (or start of memory) and the current
1.260 + region. */
1.261 +
1.262 + region_start = round(r->area_end(), increment);
1.263 + it++;
1.264 + }
1.265 +
1.266 + /* Otherwise, the region can be positioned. */
1.267 +
1.268 + else
1.269 + break;
1.270 + }
1.271 +
1.272 + /* Test for enough memory constrained by any predefined limit. */
1.273 +
1.274 + if (_end && ((region_start + region_size) > _end))
1.275 + return -L4_ENOMEM;
1.276 +
1.277 + /* Return the configured start and size. */
1.278 +
1.279 + *start = region_start;
1.280 + *size = region_size;
1.281 +
1.282 + /* Return the area within which any region will be added. */
1.283 +
1.284 + *area = this;
1.285 +
1.286 + return L4_EOK;
1.287 +}
1.288 +
1.289 +/* Obtain a recursive iterator over a memory area. */
1.290 +
1.291 +AvailableMemoryArea::iterator AvailableMemoryArea::begin()
1.292 +{
1.293 + return AvailableMemoryArea::iterator(_areas.begin(), _areas.end());
1.294 +}
1.295 +
1.296 +AvailableMemoryArea::iterator AvailableMemoryArea::end()
1.297 +{
1.298 + return AvailableMemoryArea::iterator(_areas.end(), _areas.end());
1.299 +}
1.300 +
1.301 +MemoryAreaMap::iterator AvailableMemoryArea::areas_begin()
1.302 +{
1.303 + return _areas.begin();
1.304 +}
1.305 +
1.306 +MemoryAreaMap::iterator AvailableMemoryArea::areas_end()
1.307 +{
1.308 + return _areas.end();
1.309 +}
1.310 +
1.311 +
1.312 +
1.313 +/* Initialise a recursive iterator over a memory area. */
1.314 +
1.315 +AvailableMemoryArea::iterator::iterator(MemoryAreaMap::iterator it,
1.316 + MemoryAreaMap::iterator end)
1.317 +{
1.318 + _iterators.push(it);
1.319 + _ends.push(end);
1.320 +
1.321 + /* Descend to the first non-container area. */
1.322 +
1.323 + descend_all();
1.324 +}
1.325 +
1.326 +AvailableMemoryArea::iterator::iterator()
1.327 +{
1.328 +}
1.329 +
1.330 +/* Return the current underlying iterator. */
1.331 +
1.332 +MemoryAreaMap::iterator &AvailableMemoryArea::iterator::area_iterator()
1.333 +{
1.334 + return _iterators.top();
1.335 +}
1.336 +
1.337 +/* Return the end point of the current underlying iterator. */
1.338 +
1.339 +MemoryAreaMap::iterator &AvailableMemoryArea::iterator::area_end()
1.340 +{
1.341 + return _ends.top();
1.342 +}
1.343 +
1.344 +/* Return the current area. */
1.345 +
1.346 +MemoryArea *AvailableMemoryArea::iterator::operator *()
1.347 +{
1.348 + return area_iterator()->second;
1.349 +}
1.350 +
1.351 +/* Return whether this iterator references the same area as the other
1.352 + iterator. */
1.353 +
1.354 +bool AvailableMemoryArea::iterator::operator ==(AvailableMemoryArea::iterator other)
1.355 +{
1.356 + return area_iterator() == other.area_iterator();
1.357 +}
1.358 +
1.359 +/* Return whether this iterator references a different area to the other
1.360 + iterator. */
1.361 +
1.362 +bool AvailableMemoryArea::iterator::operator !=(AvailableMemoryArea::iterator other)
1.363 +{
1.364 + return area_iterator() != other.area_iterator();
1.365 +}
1.366 +
1.367 +/* Advance this iterator to the next area. */
1.368 +
1.369 +AvailableMemoryArea::iterator &AvailableMemoryArea::iterator::operator ++()
1.370 +{
1.371 + /* Advance the area iterator. */
1.372 +
1.373 + area_iterator()++;
1.374 +
1.375 + /* Descend to the next non-container area. */
1.376 +
1.377 + descend_all();
1.378 +
1.379 + return *this;
1.380 +}
1.381 +
1.382 +AvailableMemoryArea::iterator &AvailableMemoryArea::iterator::operator ++(int)
1.383 +{
1.384 + return ++(*this);
1.385 +}
1.386 +
1.387 +/* Advance this iterator to the next area not containing other areas. */
1.388 +
1.389 +void AvailableMemoryArea::iterator::descend_all()
1.390 +{
1.391 + while ((area_iterator() != area_end()) || (_iterators.size() > 1))
1.392 + {
1.393 + /* Handle empty areas by ascending to refer to the area. */
1.394 +
1.395 + if (area_iterator() == area_end())
1.396 + {
1.397 + ascend();
1.398 + break;
1.399 + }
1.400 +
1.401 + MemoryArea *r = area_iterator()->second;
1.402 +
1.403 + /* Handle areas by descending into them. */
1.404 +
1.405 + if (!r->is_reserved() && !r->is_mapped())
1.406 + descend();
1.407 +
1.408 + /* Yield any non-container areas. */
1.409 +
1.410 + else
1.411 + break;
1.412 + }
1.413 +}
1.414 +
1.415 +/* Ascend from a memory area. */
1.416 +
1.417 +void AvailableMemoryArea::iterator::ascend()
1.418 +{
1.419 + _iterators.pop();
1.420 + _ends.pop();
1.421 +}
1.422 +
1.423 +/* Descend into a memory area. */
1.424 +
1.425 +void AvailableMemoryArea::iterator::descend()
1.426 +{
1.427 + AvailableMemoryArea *a = dynamic_cast<AvailableMemoryArea *>(area_iterator()->second);
1.428 +
1.429 + if (a != NULL)
1.430 + {
1.431 + _iterators.push(a->areas_begin());
1.432 + _ends.push(a->areas_end());
1.433 + }
1.434 +}
1.435 +
1.436 +/* vim: tabstop=2 expandtab shiftwidth=2
1.437 +*/