1 /* 2 * Memory area functionality. 3 * 4 * Copyright (C) 2022, 2023 Paul Boddie <paul@boddie.org.uk> 5 * 6 * This program is free software; you can redistribute it and/or 7 * modify it under the terms of the GNU General Public License as 8 * published by the Free Software Foundation; either version 2 of 9 * the License, or (at your option) any later version. 10 * 11 * This program is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * GNU General Public License for more details. 15 * 16 * You should have received a copy of the GNU General Public License 17 * along with this program; if not, write to the Free Software 18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, 19 * Boston, MA 02110-1301, USA 20 */ 21 22 #include <l4/re/c/rm.h> 23 #include <l4/sys/err.h> 24 25 #include <mem/memory_utils.h> 26 27 #include "mapped_region.h" 28 29 30 31 /* Copy an area. */ 32 33 MemoryArea *MemoryArea::copy() 34 { 35 return new MemoryArea(_start, _end); 36 } 37 38 /* In general, a region cannot support other regions. */ 39 40 long MemoryArea::add(MemoryArea &area) 41 { 42 (void) area; 43 return -L4_EPERM; 44 } 45 46 long MemoryArea::remove(MemoryArea &area) 47 { 48 (void) area; 49 return -L4_EPERM; 50 } 51 52 /* In general, a region supports a memory access within its bounds. */ 53 54 long MemoryArea::find(address_t addr, MemoryArea **area, MemoryArea **parent) 55 { 56 /* The parent is merely propagated through this method, but is present for 57 conformance to the generic method signature. */ 58 59 (void) parent; 60 61 if ((addr >= _start) && (addr < _end)) 62 { 63 *area = this; 64 return L4_EOK; 65 } 66 else 67 return -L4_ENOMEM; 68 } 69 70 /* In general, a region does not support the identification of a location for 71 region insertion. */ 72 73 long MemoryArea::find(address_t *start, address_t *size, map_flags_t flags, 74 unsigned char align, MemoryArea **area) 75 { 76 (void) start; (void) size; (void) flags; (void) align; (void) area; 77 return -L4_ENOMEM; 78 } 79 80 81 82 /* Copy a reserved area. */ 83 84 MemoryArea *ReservedMemoryArea::copy() 85 { 86 return new ReservedMemoryArea(_start, _end); 87 } 88 89 /* A reserved area does not support any memory access. */ 90 91 long ReservedMemoryArea::find(address_t addr, MemoryArea **area, 92 MemoryArea **parent) 93 { 94 (void) addr; (void) area; (void) parent; 95 return -L4_ENOMEM; 96 } 97 98 99 100 /* Discard all allocated areas. */ 101 102 AvailableMemoryArea::~AvailableMemoryArea() 103 { 104 MemoryAreas::iterator it; 105 106 for (it = _allocated.begin(); it != _allocated.end(); it++) 107 delete *it; 108 109 _allocated.clear(); 110 } 111 112 /* Copy an unused available memory area. */ 113 114 MemoryArea *AvailableMemoryArea::copy() 115 { 116 return new AvailableMemoryArea(_start, _end); 117 } 118 119 /* Add an area. */ 120 121 long AvailableMemoryArea::add(MemoryArea &area) 122 { 123 MemoryArea *a = area.copy(); 124 125 _areas[area.area_start()] = a; 126 _allocated.insert(a); 127 128 return L4_EOK; 129 } 130 131 /* Remove an area. */ 132 133 long AvailableMemoryArea::remove(MemoryArea &area) 134 { 135 MemoryAreaMap::iterator it = _areas.find(area.area_start()); 136 137 if (it != _areas.end()) 138 { 139 _areas.erase(it); 140 141 MemoryAreas::iterator ita = _allocated.find(it->second); 142 143 if (ita != _allocated.end()) 144 { 145 delete *ita; 146 _allocated.erase(ita); 147 } 148 } 149 150 return L4_EOK; 151 } 152 153 /* Find an region able to support a memory access. */ 154 155 long AvailableMemoryArea::find(address_t addr, MemoryArea **area, 156 MemoryArea **parent) 157 { 158 MemoryAreaMap::iterator it = _areas.upper_bound(addr); 159 160 /* Consider any area preceding or encompassing the desired address. */ 161 162 if (it != _areas.begin()) 163 { 164 it--; 165 166 /* Test whether the desired region start is encompassed by the preceding 167 area. */ 168 169 MemoryArea *r = it->second; 170 171 *parent = this; 172 173 if (r->supports(addr)) 174 return r->find(addr, area, parent); 175 } 176 177 /* Otherwise, no area within this area supports the address. */ 178 179 return -L4_ENOMEM; 180 } 181 182 /* Find an area suitable for attaching a memory region. */ 183 184 long AvailableMemoryArea::find(address_t *start, address_t *size, 185 map_flags_t flags, unsigned char align, 186 MemoryArea **area) 187 { 188 /* Obtain the alignment increment and a properly aligned size. */ 189 190 address_t increment = 1UL << align; 191 address_t region_size = round(*size, increment); 192 193 /* Align any desired location. */ 194 195 address_t region_start = trunc(*start, increment); 196 197 /* Enforce a minimum address. */ 198 199 if (region_start < _start) 200 region_start = round(_start, increment); 201 202 /* Search for existing regions after the desired, conformant start address. */ 203 204 MemoryAreaMap::iterator it = _areas.upper_bound(region_start); 205 206 /* Consider any area preceding or encompassing the desired address. */ 207 208 if (it != _areas.begin()) 209 { 210 MemoryAreaMap::iterator next = it; 211 212 /* Step back to the preceding area to get its details. */ 213 214 it--; 215 MemoryArea *pr = it->second; 216 it = next; 217 218 /* Test whether the desired region start is encompassed by the preceding 219 area. */ 220 221 if (region_start < pr->area_end()) 222 { 223 /* Where the preceding area is mapped or a reserved area, adjust the start 224 of any search range. If an exact request is made for a region, deny the 225 request. */ 226 227 if (pr->is_mapped() || pr->is_reserved()) 228 { 229 if (!(flags & L4RE_RM_F_SEARCH_ADDR)) 230 return -L4_ENOMEM; 231 232 region_start = round(pr->area_end(), increment); 233 } 234 235 /* Where the preceding area is an area within which regions might be 236 established, search within that area. */ 237 238 else 239 return pr->find(start, size, flags, align, area); 240 } 241 } 242 243 /* Consider the regions following the current region start candidate. */ 244 245 MemoryArea *r; 246 247 while ((it != _areas.end()) && !(_end && ((region_start + region_size) > _end))) 248 { 249 r = it->second; 250 251 /* Obtain the limit of available space being considered. */ 252 253 address_t end_limit = r->area_start(); 254 255 /* Test if not enough space exists between the preceding region (or start of 256 memory) and the current region. */ 257 258 if ((region_start + region_size) > end_limit) 259 { 260 /* If an exact request is made for a region, deny the request. */ 261 262 if (!(flags & L4RE_RM_F_SEARCH_ADDR)) 263 return -L4_ENOMEM; 264 265 /* Otherwise, investigate subsequent regions if not enough space exists 266 between the preceding region (or start of memory) and the current 267 region. */ 268 269 region_start = round(r->area_end(), increment); 270 it++; 271 } 272 273 /* Otherwise, the region can be positioned. */ 274 275 else 276 break; 277 } 278 279 /* Test for enough memory constrained by any predefined limit. */ 280 281 if (_end && ((region_start + region_size) > _end)) 282 return -L4_ENOMEM; 283 284 /* Return the configured start and size. */ 285 286 *start = region_start; 287 *size = region_size; 288 289 /* Return the area within which any region will be added. */ 290 291 *area = this; 292 293 return L4_EOK; 294 } 295 296 /* Obtain a recursive iterator over a memory area. */ 297 298 AvailableMemoryArea::iterator AvailableMemoryArea::begin() 299 { 300 return AvailableMemoryArea::iterator(_areas.begin(), _areas.end()); 301 } 302 303 AvailableMemoryArea::iterator AvailableMemoryArea::end() 304 { 305 return AvailableMemoryArea::iterator(_areas.end(), _areas.end()); 306 } 307 308 MemoryAreaMap::iterator AvailableMemoryArea::areas_begin() 309 { 310 return _areas.begin(); 311 } 312 313 MemoryAreaMap::iterator AvailableMemoryArea::areas_end() 314 { 315 return _areas.end(); 316 } 317 318 319 320 /* Initialise a recursive iterator over a memory area. */ 321 322 AvailableMemoryArea::iterator::iterator(MemoryAreaMap::iterator it, 323 MemoryAreaMap::iterator end) 324 { 325 _iterators.push(it); 326 _ends.push(end); 327 328 /* Descend to the first non-container area. */ 329 330 descend_all(); 331 } 332 333 AvailableMemoryArea::iterator::iterator() 334 { 335 } 336 337 /* Return the current underlying iterator. */ 338 339 MemoryAreaMap::iterator &AvailableMemoryArea::iterator::area_iterator() 340 { 341 return _iterators.top(); 342 } 343 344 /* Return the end point of the current underlying iterator. */ 345 346 MemoryAreaMap::iterator &AvailableMemoryArea::iterator::area_end() 347 { 348 return _ends.top(); 349 } 350 351 /* Return the current area. */ 352 353 MemoryArea *AvailableMemoryArea::iterator::operator *() 354 { 355 return area_iterator()->second; 356 } 357 358 /* Return whether this iterator references the same area as the other 359 iterator. */ 360 361 bool AvailableMemoryArea::iterator::operator ==(AvailableMemoryArea::iterator other) 362 { 363 return area_iterator() == other.area_iterator(); 364 } 365 366 /* Return whether this iterator references a different area to the other 367 iterator. */ 368 369 bool AvailableMemoryArea::iterator::operator !=(AvailableMemoryArea::iterator other) 370 { 371 return area_iterator() != other.area_iterator(); 372 } 373 374 /* Advance this iterator to the next area. */ 375 376 AvailableMemoryArea::iterator &AvailableMemoryArea::iterator::operator ++() 377 { 378 /* Advance the area iterator. */ 379 380 area_iterator()++; 381 382 /* Descend to the next non-container area. */ 383 384 descend_all(); 385 386 return *this; 387 } 388 389 AvailableMemoryArea::iterator &AvailableMemoryArea::iterator::operator ++(int) 390 { 391 return ++(*this); 392 } 393 394 /* Advance this iterator to the next area not containing other areas. */ 395 396 void AvailableMemoryArea::iterator::descend_all() 397 { 398 while ((area_iterator() != area_end()) || (_iterators.size() > 1)) 399 { 400 /* Handle empty areas by ascending to refer to the area. */ 401 402 if (area_iterator() == area_end()) 403 { 404 ascend(); 405 break; 406 } 407 408 MemoryArea *r = area_iterator()->second; 409 410 /* Handle areas by descending into them. */ 411 412 if (!r->is_reserved() && !r->is_mapped()) 413 descend(); 414 415 /* Yield any non-container areas. */ 416 417 else 418 break; 419 } 420 } 421 422 /* Ascend from a memory area. */ 423 424 void AvailableMemoryArea::iterator::ascend() 425 { 426 _iterators.pop(); 427 _ends.pop(); 428 } 429 430 /* Descend into a memory area. */ 431 432 void AvailableMemoryArea::iterator::descend() 433 { 434 AvailableMemoryArea *a = dynamic_cast<AvailableMemoryArea *>(area_iterator()->second); 435 436 if (a != NULL) 437 { 438 _iterators.push(a->areas_begin()); 439 _ends.push(a->areas_end()); 440 } 441 } 442 443 /* vim: tabstop=2 expandtab shiftwidth=2 444 */