1// -*- Mode: C++ -*- 2// vim:ft=cpp 3/** 4 * \file region_mapping 5 * \brief Region handling 6 */ 7/* 8 * (c) 2008-2009 Adam Lackorzynski <adam@os.inf.tu-dresden.de>, 9 * Alexander Warg <warg@os.inf.tu-dresden.de>, 10 * Björn Döbel <doebel@os.inf.tu-dresden.de> 11 * economic rights: Technische Universität Dresden (Germany) 12 * 13 * This file is part of TUD:OS and distributed under the terms of the 14 * GNU General Public License 2. 15 * Please see the COPYING-GPL-2 file for details. 16 * 17 * As a special exception, you may use this file as part of a free software 18 * library without restriction. Specifically, if other files instantiate 19 * templates or use macros or inline functions from this file, or you compile 20 * this file and link it with other files to produce an executable, this 21 * file does not by itself cause the resulting executable to be covered by 22 * the GNU General Public License. This exception does not however 23 * invalidate any other reasons why the executable file might be covered by 24 * the GNU General Public License. 25 */ 26 27#pragma once 28 29#include <l4/cxx/avl_map> 30#include <l4/sys/types.h> 31#include <l4/re/rm> 32 33 34namespace L4Re { namespace Util { 35class Region 36{ 37private: 38 l4_addr_t _start, _end; 39 40public: 41 Region() noexcept : _start(~0UL), _end(~0UL) {} 42 Region(l4_addr_t addr) noexcept : _start(addr), _end(addr) {} 43 Region(l4_addr_t start, l4_addr_t end) noexcept 44 : _start(start), _end(end) {} 45 l4_addr_t start() const noexcept { return _start; } 46 l4_addr_t end() const noexcept { return _end; } 47 unsigned long size() const noexcept { return end() - start() + 1; } 48 bool invalid() const noexcept { return _start == ~0UL && _end == ~0UL; } 49 bool operator < (Region const &o) const noexcept 50 { return end() < o.start(); } 51 bool contains(Region const &o) const noexcept 52 { return o.start() >= start() && o.end() <= end(); } 53 bool operator == (Region const &o) const noexcept 54 { return o.start() == start() && o.end() == end(); } 55 ~Region() noexcept {} 56}; 57 58template< typename DS, typename OPS > 59class Region_handler 60{ 61private: 62 L4Re::Rm::Offset _offs; 63 DS _mem; 64 l4_cap_idx_t _client_cap = L4_INVALID_CAP; 65 L4Re::Rm::Region_flags _flags; 66 67public: 68 typedef DS Dataspace; 69 typedef OPS Ops; 70 typedef typename OPS::Map_result Map_result; 71 72 Region_handler() noexcept : _offs(0), _mem(), _flags() {} 73 Region_handler(Dataspace const &mem, l4_cap_idx_t client_cap, 74 L4Re::Rm::Offset offset = 0, 75 L4Re::Rm::Region_flags flags = L4Re::Rm::Region_flags(0)) noexcept 76 : _offs(offset), _mem(mem), _client_cap(client_cap), _flags(flags) 77 {} 78 79 Dataspace const &memory() const noexcept 80 { 81 return _mem; 82 } 83 84 l4_cap_idx_t client_cap_idx() const noexcept 85 { 86 return _client_cap; 87 } 88 89 L4Re::Rm::Offset offset() const noexcept 90 { 91 return _offs; 92 } 93 94 constexpr bool is_ro() const noexcept 95 { 96 return !(_flags & L4Re::Rm::F::W); 97 } 98 99 L4Re::Rm::Region_flags caching() const noexcept 100 { 101 return _flags & L4Re::Rm::F::Caching_mask; 102 } 103 104 L4Re::Rm::Region_flags flags() const noexcept 105 { 106 return _flags; 107 } 108 109 Region_handler operator + (l4_int64_t offset) const noexcept 110 { 111 Region_handler n = *this; n._offs += offset; return n; 112 } 113 114 void free(l4_addr_t start, unsigned long size) const noexcept 115 { 116 Ops::free(this, start, size); 117 } 118 119 int map(l4_addr_t addr, Region const &r, bool writable, 120 Map_result *result) const 121 { 122 return Ops::map(this, addr, r, writable, result); 123 } 124 125}; 126 127 128template< typename Hdlr, template<typename T> class Alloc > 129class Region_map 130{ 131protected: 132 typedef cxx::Avl_map< Region, Hdlr, cxx::Lt_functor, Alloc > Tree; 133 Tree _rm; ///< Region Map 134 Tree _am; ///< Area Map 135 136private: 137 l4_addr_t _start; 138 l4_addr_t _end; 139 140protected: 141 void set_limits(l4_addr_t start, l4_addr_t end) noexcept 142 { 143 _start = start; 144 _end = end; 145 } 146 147public: 148 typedef typename Tree::Item_type Item; 149 typedef typename Tree::Node Node; 150 typedef typename Tree::Key_type Key_type; 151 typedef Hdlr Region_handler; 152 153 typedef typename Tree::Iterator Iterator; 154 typedef typename Tree::Const_iterator Const_iterator; 155 typedef typename Tree::Rev_iterator Rev_iterator; 156 typedef typename Tree::Const_rev_iterator Const_rev_iterator; 157 158 Iterator begin() noexcept { return _rm.begin(); } 159 Const_iterator begin() const noexcept { return _rm.begin(); } 160 Iterator end() noexcept { return _rm.end(); } 161 Const_iterator end() const noexcept { return _rm.end(); } 162 163 Iterator area_begin() noexcept { return _am.begin(); } 164 Const_iterator area_begin() const noexcept { return _am.begin(); } 165 Iterator area_end() noexcept { return _am.end(); } 166 Const_iterator area_end() const noexcept { return _am.end(); } 167 Node area_find(Key_type const &c) const noexcept { return _am.find_node(c); } 168 169 l4_addr_t min_addr() const noexcept { return _start; } 170 l4_addr_t max_addr() const noexcept { return _end; } 171 172 173 Region_map(l4_addr_t start, l4_addr_t end) noexcept : _start(start), _end(end) {} 174 175 Node find(Key_type const &key) const noexcept 176 { 177 Node n = _rm.find_node(key); 178 if (!n) 179 return Node(); 180 181 // 'find' should find any region overlapping with the searched one, the 182 // caller should check for further requirements 183 if (0) 184 if (!n->first.contains(key)) 185 return Node(); 186 187 return n; 188 } 189 190 Node lower_bound(Key_type const &key) const noexcept 191 { 192 Node n = _rm.lower_bound_node(key); 193 return n; 194 } 195 196 Node lower_bound_area(Key_type const &key) const noexcept 197 { 198 Node n = _am.lower_bound_node(key); 199 return n; 200 } 201 202 l4_addr_t attach_area(l4_addr_t addr, unsigned long size, 203 L4Re::Rm::Flags flags = L4Re::Rm::Flags(0), 204 unsigned char align = L4_PAGESHIFT) noexcept 205 { 206 if (size < 2) 207 return L4_INVALID_ADDR; 208 209 210 Region c; 211 212 if (!(flags & L4Re::Rm::F::Search_addr)) 213 { 214 c = Region(addr, addr + size - 1); 215 Node r = _am.find_node(c); 216 if (r) 217 return L4_INVALID_ADDR; 218 } 219 220 while (flags & L4Re::Rm::F::Search_addr) 221 { 222 if (addr < min_addr() || (addr + size - 1) > max_addr()) 223 addr = min_addr(); 224 addr = find_free(addr, max_addr(), size, align, flags); 225 if (addr == L4_INVALID_ADDR) 226 return L4_INVALID_ADDR; 227 228 c = Region(addr, addr + size - 1); 229 Node r = _am.find_node(c); 230 if (!r) 231 break; 232 233 if (r->first.end() >= max_addr()) 234 return L4_INVALID_ADDR; 235 236 addr = r->first.end() + 1; 237 } 238 239 if (_am.insert(c, Hdlr(typename Hdlr::Dataspace(), 0, 0, flags.region_flags())).second == 0) 240 return addr; 241 242 return L4_INVALID_ADDR; 243 } 244 245 bool detach_area(l4_addr_t addr) noexcept 246 { 247 if (_am.remove(addr)) 248 return false; 249 250 return true; 251 } 252 253 void *attach(void *addr, unsigned long size, Hdlr const &hdlr, 254 L4Re::Rm::Flags flags = L4Re::Rm::Flags(0), 255 unsigned char align = L4_PAGESHIFT) noexcept 256 { 257 if (size < 2) 258 return L4_INVALID_PTR; 259 260 l4_addr_t end = max_addr(); 261 l4_addr_t beg = (l4_addr_t)addr; 262 263 if (flags & L4Re::Rm::F::In_area) 264 { 265 Node r = _am.find_node(Region(beg, beg + size - 1)); 266 if (!r || (r->second.flags() & L4Re::Rm::F::Reserved)) 267 return L4_INVALID_PTR; 268 269 end = r->first.end(); 270 } 271 272 if (flags & L4Re::Rm::F::Search_addr) 273 { 274 beg = find_free(beg, end, size, align, flags); 275 if (beg == L4_INVALID_ADDR) 276 return L4_INVALID_PTR; 277 } 278 279 if (!(flags & (L4Re::Rm::F::Search_addr | L4Re::Rm::F::In_area)) 280 && _am.find_node(Region(beg, beg + size - 1))) 281 return L4_INVALID_PTR; 282 283 if (beg < min_addr() || beg + size -1 > end) 284 return L4_INVALID_PTR; 285 286 if (_rm.insert(Region(beg, beg + size -1), hdlr).second == 0) 287 return (void*)beg; 288 289 return L4_INVALID_PTR; 290 } 291 292 int detach(void *addr, unsigned long sz, unsigned flags, 293 Region *reg, Hdlr *hdlr) noexcept 294 { 295 Region dr((l4_addr_t)addr, (l4_addr_t)addr + sz - 1); 296 Region res(~0UL,0); 297 298 Node r = find(dr); 299 if (!r) 300 return -L4_ENOENT; 301 302 Region g = r->first; 303 Hdlr const &h = r->second; 304 305 if (flags & L4Re::Rm::Detach_overlap || dr.contains(g)) 306 { 307 if (_rm.remove(g)) 308 return -L4_ENOENT; 309 310 if (!(flags & L4Re::Rm::Detach_keep) && (h.flags() & L4Re::Rm::F::Detach_free)) 311 h.free(0, g.size()); 312 313 if (hdlr) *hdlr = h; 314 if (reg) *reg = g; 315 316 if (find(dr)) 317 return Rm::Detached_ds | Rm::Detach_again; 318 else 319 return Rm::Detached_ds; 320 } 321 else if (dr.start() <= g.start()) 322 { 323 // move the start of a region 324 325 if (!(flags & L4Re::Rm::Detach_keep) && (h.flags() & L4Re::Rm::F::Detach_free)) 326 h.free(0, dr.end() + 1 - g.start()); 327 328 unsigned long sz = dr.end() + 1 - g.start(); 329 Item *cn = const_cast<Item*>((Item const *)r); 330 cn->first = Region(dr.end() + 1, g.end()); 331 cn->second = cn->second + sz; 332 if (hdlr) *hdlr = Hdlr(); 333 if (reg) *reg = Region(g.start(), dr.end()); 334 if (find(dr)) 335 return Rm::Kept_ds | Rm::Detach_again; 336 else 337 return Rm::Kept_ds; 338 } 339 else if (dr.end() >= g.end()) 340 { 341 // move the end of a region 342 343 if (!(flags & L4Re::Rm::Detach_keep) && (h.flags() & L4Re::Rm::F::Detach_free)) 344 h.free(dr.start() - g.start(), g.end() + 1 - dr.start()); 345 346 Item *cn = const_cast<Item*>((Item const*)r); 347 cn->first = Region(g.start(), dr.start() -1); 348 if (hdlr) *hdlr = Hdlr(); 349 if (reg) *reg = Region(dr.start(), g.end()); 350 351 if (find(dr)) 352 return Rm::Kept_ds | Rm::Detach_again; 353 else 354 return Rm::Kept_ds; 355 } 356 else if (g.contains(dr)) 357 { 358 // split a single region that contains the new region 359 360 if (!(flags & L4Re::Rm::Detach_keep) && (h.flags() & L4Re::Rm::F::Detach_free)) 361 h.free(dr.start() - g.start(), dr.size()); 362 363 // first move the end off the existing region before the new one 364 const_cast<Item*>((Item const *)r)->first = Region(g.start(), dr.start()-1); 365 366 int err; 367 368 // insert a second region for the remaining tail of 369 // the old existing region 370 err = _rm.insert(Region(dr.end() + 1, g.end()), h + (dr.end() + 1 - g.start())).second; 371 372 if (err) 373 return err; 374 375 if (hdlr) *hdlr = h; 376 if (reg) *reg = dr; 377 return Rm::Split_ds; 378 } 379 return -L4_ENOENT; 380 } 381 382 l4_addr_t find_free(l4_addr_t start, l4_addr_t end, l4_addr_t size, 383 unsigned char align, L4Re::Rm::Flags flags) const noexcept; 384 385}; 386 387 388template< typename Hdlr, template<typename T> class Alloc > 389l4_addr_t 390Region_map<Hdlr, Alloc>::find_free(l4_addr_t start, l4_addr_t end, 391 unsigned long size, unsigned char align, L4Re::Rm::Flags flags) const noexcept 392{ 393 l4_addr_t addr = start; 394 395 if (addr == ~0UL || addr < min_addr() || addr >= end) 396 addr = min_addr(); 397 398 addr = l4_round_size(addr, align); 399 Node r; 400 401 for(;;) 402 { 403 if (addr > 0 && addr - 1 > end - size) 404 return L4_INVALID_ADDR; 405 406 Region c(addr, addr + size - 1); 407 r = _rm.find_node(c); 408 409 if (!r) 410 { 411 if (!(flags & L4Re::Rm::F::In_area) && (r = _am.find_node(c))) 412 { 413 if (r->first.end() > end - size) 414 return L4_INVALID_ADDR; 415 416 addr = l4_round_size(r->first.end() + 1, align); 417 continue; 418 } 419 break; 420 } 421 else if (r->first.end() > end - size) 422 return L4_INVALID_ADDR; 423 424 addr = l4_round_size(r->first.end() + 1, align); 425 } 426 427 if (!r) 428 return addr; 429 430 return L4_INVALID_ADDR; 431} 432 433}} 434