l4/pkg/l4re/util/include/region_mapping

   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/l4int.h>
  31 #include <l4/re/rm>
  32
  33
  34 namespace L4Re { namespace Util {
  35 class Region
  36 {
  37 private:
  38   l4_addr_t _start, _end;
  39
  40 public:
  41   Region() throw() : _start(~0UL), _end(~0UL) {}
  42   Region(l4_addr_t addr) throw() : _start(addr), _end(addr) {}
  43   Region(l4_addr_t start, l4_addr_t end) throw()
  44     : _start(start), _end(end) {}
  45   l4_addr_t start() const throw() { return _start; }
  46   l4_addr_t end() const throw() { return _end; }
  47   unsigned long size() const throw() { return end() - start() + 1; }
  48   bool invalid() const throw() { return _start == ~0UL && _end == ~0UL; }
  49   bool operator < (Region const &o) const throw()
  50   { return end() < o.start(); }
  51   bool contains(Region const &o) const throw()
  52   { return o.start() >= start() && o.end() <= end(); }
  53   bool operator == (Region const &o) const throw()
  54   { return o.start() == start() && o.end() == end(); }
  55   ~Region() throw() {}
  56 };
  57
  58 template< typename DS, typename OPS >
  59 class Region_handler
  60 {
  61 private:
  62   l4_addr_t _offs;
  63   DS _mem;
  64   l4_cap_idx_t _client_cap;
  65   unsigned char _flags;
  66
  67 public:
  68   typedef DS Dataspace;
  69   typedef OPS Ops;
  70   typedef typename OPS::Map_result Map_result;
  71
  72   Region_handler() throw() : _offs(0), _mem(), _flags() {}
  73   Region_handler(Dataspace const &mem, l4_cap_idx_t client_cap,
  74       l4_addr_t offset = 0, unsigned flags = 0) throw()
  75     : _offs(offset), _mem(mem), _client_cap(client_cap), _flags(flags)
  76   {}
  77   Dataspace const &memory() const throw() { return _mem; }
  78   l4_cap_idx_t client_cap_idx() const throw() { return _client_cap; }
  79   l4_addr_t offset() const throw() { return _offs; }
  80   l4_addr_t is_ro() const throw() { return _flags & L4Re::Rm::Read_only; }
  81   unsigned flags() const throw() { return _flags; }
  82
  83   Region_handler operator + (long offset) throw()
  84   { Region_handler n = *this; n._offs += offset; return n; }
  85
  86
  87   void unmap(l4_addr_t va, l4_addr_t ds_offs, unsigned long size) const throw()
  88   { Ops::unmap(this, va, ds_offs, size); }
  89
  90   void free(l4_addr_t start, unsigned long size) const throw()
  91   { Ops::free(this, start, size); }
  92
  93   void take() const    { Ops::take(this); }
  94   void release() const { Ops::release(this); }
  95
  96   int map(l4_addr_t adr, Region const &r, bool writable, Map_result *result) const
  97   { return Ops::map(this, adr, r, writable, result); }
  98
  99 };
 100
 101
 102 template< typename Hdlr, template<typename T> class Alloc >
 103 class Region_map
 104 {
 105 protected:
 106   typedef cxx::Avl_map< Region, Hdlr, cxx::Lt_functor, Alloc > Tree;
 107   Tree _rm; ///< Region Map
 108   Tree _am; ///< Area Map
 109
 110 private:
 111   l4_addr_t _start;
 112   l4_addr_t _end;
 113
 114 protected:
 115   void set_limits(l4_addr_t start, l4_addr_t end) throw()
 116   {
 117     _start = start;
 118     _end = end;
 119   }
 120
 121 public:
 122   typedef typename Tree::Item_type  Item;
 123   typedef typename Tree::Node       Node;
 124   typedef typename Tree::Key_type   Key_type;
 125   typedef Hdlr Region_handler;
 126
 127   typedef typename Tree::Iterator Iterator;
 128   typedef typename Tree::Const_iterator Const_iterator;
 129   typedef typename Tree::Rev_iterator Rev_iterator;
 130   typedef typename Tree::Const_rev_iterator Const_rev_iterator;
 131
 132   Iterator begin() throw() { return _rm.begin(); }
 133   Const_iterator begin() const throw() { return _rm.begin(); }
 134   Iterator end() throw() { return _rm.end(); }
 135   Const_iterator end() const throw() { return _rm.end(); }
 136
 137   Iterator area_begin() throw() { return _am.begin(); }
 138   Const_iterator area_begin() const throw() { return _am.begin(); }
 139   Iterator area_end() throw() { return _am.end(); }
 140   Const_iterator area_end() const throw() { return _am.end(); }
 141   Node area_find(Key_type const &c) const throw() { return _am.find_node(c); }
 142
 143   enum Attach_flags
 144   {
 145     None      = 0,
 146     Search    = L4Re::Rm::Search_addr,
 147     In_area   = L4Re::Rm::In_area,
 148   };
 149
 150   l4_addr_t min_addr() const throw() { return _start; }
 151   l4_addr_t max_addr() const throw() { return _end; }
 152
 153
 154   Region_map(l4_addr_t start, l4_addr_t end) throw() : _start(start), _end(end) {}
 155
 156   Node find(Key_type const &key) const throw()
 157   {
 158     Node n = _rm.find_node(key);
 159     if (!n)
 160       return Node();
 161
 162     // 'find' should find any region overlapping with the searched one, the
 163     // caller should check for further requirements
 164     if (0)
 165       if (!n->first.contains(key))
 166         return Node();
 167
 168     return n;
 169   }
 170
 171   Node lower_bound(Key_type const &key) const throw()
 172   {
 173     Node n = _rm.lower_bound_node(key);
 174     return n;
 175   }
 176
 177   Node lower_bound_area(Key_type const &key) const throw()
 178   {
 179     Node n = _am.lower_bound_node(key);
 180     return n;
 181   }
 182
 183   l4_addr_t attach_area(l4_addr_t addr, unsigned long size,
 184                         unsigned flags = None,
 185                         unsigned char align = L4_PAGESHIFT) throw()
 186   {
 187     if (size < 2)
 188       return L4_INVALID_ADDR;
 189
 190
 191     Region c;
 192
 193     if (!(flags & Search))
 194       {
 195         c = Region(addr, addr + size - 1);
 196         Node r = _am.find_node(c);
 197         if (r)
 198           return L4_INVALID_ADDR;
 199       }
 200
 201     while (flags & Search)
 202       {
 203         if (addr < min_addr() || (addr + size - 1) > max_addr())
 204           addr = min_addr();
 205         addr = find_free(addr, max_addr(), size, align, flags);
 206         if (addr == L4_INVALID_ADDR)
 207           return L4_INVALID_ADDR;
 208
 209         c = Region(addr, addr + size - 1);
 210         Node r = _am.find_node(c);
 211         if (!r)
 212           break;
 213
 214         if (r->first.end() >= max_addr())
 215           return L4_INVALID_ADDR;
 216
 217         addr = r->first.end() + 1;
 218       }
 219
 220     if (_am.insert(c, Hdlr(typename Hdlr::Dataspace(), 0, flags)).second == 0)
 221       return addr;
 222
 223     return L4_INVALID_ADDR;
 224   }
 225
 226   bool detach_area(l4_addr_t addr) throw()
 227   {
 228     if (_am.remove(addr))
 229       return false;
 230
 231     return true;
 232   }
 233
 234   void *attach(void *addr, unsigned long size, Hdlr const &hdlr,
 235                unsigned flags = None, unsigned char align = L4_PAGESHIFT) throw()
 236   {
 237     if (size < 2)
 238       return L4_INVALID_PTR;
 239
 240     l4_addr_t end = max_addr();
 241     l4_addr_t beg = (l4_addr_t)addr;
 242
 243     if (flags & In_area)
 244       {
 245         Node r = _am.find_node(Region(beg, beg + size - 1));
 246         if (!r || (r->second.flags() & L4Re::Rm::Reserved))
 247           return L4_INVALID_PTR;
 248
 249         end = r->first.end();
 250       }
 251
 252     if (flags & Search)
 253       {
 254         beg = find_free(beg, end, size, align, flags);
 255         if (beg == L4_INVALID_ADDR)
 256           return L4_INVALID_PTR;
 257       }
 258
 259     if (!(flags & (Search | In_area)) && _am.find_node(Region(beg, beg + size - 1)))
 260       return L4_INVALID_PTR;
 261
 262     if (beg < min_addr() || beg + size -1 > end)
 263       return L4_INVALID_PTR;
 264
 265     if (_rm.insert(Region(beg, beg + size -1), hdlr).second == 0)
 266       return (void*)beg;
 267
 268     return L4_INVALID_PTR;
 269   }
 270
 271   int detach(void *addr, unsigned long sz, unsigned flags,
 272              Region *reg, Hdlr *hdlr) throw()
 273   {
 274     Region dr((l4_addr_t)addr, (l4_addr_t)addr + sz - 1);
 275     Region res(~0UL,0);
 276
 277     Node r = find(dr);
 278     if (!r)
 279       return -L4_ENOENT;
 280
 281     Region g = r->first;
 282     Hdlr   h = r->second;
 283
 284     if (flags == L4Re::Rm::Detach_overlap || dr.contains(g))
 285       {
 286         if (_rm.remove(g))
 287           return -L4_ENOENT;
 288
 289         if (h.flags() & L4Re::Rm::Detach_free)
 290           h.free(0, g.size());
 291
 292         if (hdlr) *hdlr = h;
 293         if (reg) *reg = g;
 294
 295         if (find(dr))
 296           return Rm::Detached_ds | Rm::Detach_again;
 297         else
 298           return Rm::Detached_ds;
 299       }
 300     else if (dr.start() <= g.start())
 301       {
 302         // move the start of a region
 303
 304         if (h.flags() & L4Re::Rm::Detach_free)
 305           h.free(0, dr.end() + 1 - g.start());
 306
 307         unsigned long sz = dr.end() + 1 - g.start();
 308         Item *cn = const_cast<Item*>((Item const *)r);
 309         cn->first = Region(dr.end() + 1, g.end());
 310         cn->second = cn->second + sz;
 311         if (hdlr) *hdlr = Hdlr();
 312         if (reg) *reg = Region(g.start(), dr.end());
 313         if (find(dr))
 314           return Rm::Kept_ds | Rm::Detach_again;
 315         else
 316           return Rm::Kept_ds;
 317       }
 318     else if (dr.end() >= g.end())
 319       {
 320         // move the end of a region
 321
 322         if (h.flags() & L4Re::Rm::Detach_free)
 323           h.free(dr.start() - g.start(), g.end() + 1 - dr.start());
 324
 325         Item *cn = const_cast<Item*>((Item const*)r);
 326         cn->first = Region(g.start(), dr.start() -1);
 327         if (hdlr) *hdlr = Hdlr();
 328         if (reg) *reg = Region(dr.start(), g.end());
 329
 330         if (find(dr))
 331           return Rm::Kept_ds | Rm::Detach_again;
 332         else
 333           return Rm::Kept_ds;
 334       }
 335     else if (g.contains(dr))
 336       {
 337         // split a single region that contains the new region
 338
 339         if (h.flags() & L4Re::Rm::Detach_free)
 340           h.free(dr.start() - g.start(), dr.size());
 341
 342         // first move the end off the existing region before the new one
 343         const_cast<Item*>((Item const *)r)->first = Region(g.start(), dr.start()-1);
 344
 345         int err;
 346
 347         // insert a second region for the remaining tail of
 348         // the old existing region
 349         err = _rm.insert(Region(dr.end() + 1, g.end()), h + (dr.end() + 1 - g.start())).second;
 350
 351         if (err)
 352           return err;
 353
 354         if (hdlr) *hdlr = h;
 355         if (reg) *reg = dr;
 356         return Rm::Split_ds;
 357       }
 358     return -L4_ENOENT;
 359   }
 360
 361   l4_addr_t find_free(l4_addr_t start, l4_addr_t end, l4_addr_t size,
 362                       unsigned char align, unsigned flags) const throw();
 363
 364 };
 365
 366
 367 template< typename Hdlr, template<typename T> class Alloc >
 368 l4_addr_t
 369 Region_map<Hdlr, Alloc>::find_free(l4_addr_t start, l4_addr_t end,
 370     unsigned long size, unsigned char align, unsigned flags) const throw()
 371 {
 372   l4_addr_t addr = start;
 373
 374   if (addr == ~0UL || addr < min_addr() || addr >= end)
 375     addr = min_addr();
 376
 377   addr = l4_round_size(addr, align);
 378   Node r;
 379
 380   for(;;)
 381     {
 382       if (addr > 0 && addr - 1 > end - size)
 383         return L4_INVALID_ADDR;
 384
 385       Region c(addr, addr + size - 1);
 386       r = _rm.find_node(c);
 387
 388       if (!r)
 389         {
 390           if (!(flags & In_area) && (r = _am.find_node(c)))
 391             {
 392               if (r->first.end() > end - size)
 393                 return L4_INVALID_ADDR;
 394
 395               addr = l4_round_size(r->first.end() + 1, align);
 396               continue;
 397             }
 398           break;
 399         }
 400       else if (r->first.end() > end - size)
 401         return L4_INVALID_ADDR;
 402
 403       addr = l4_round_size(r->first.end() + 1, align);
 404     }
 405
 406   if (!r)
 407     return addr;
 408
 409   return L4_INVALID_ADDR;
 410 }
 411
 412 }}