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