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