l4/pkg/bootstrap_custom/server/src/region.h

   1 /*
   2  * (c) 2008-2009 Adam Lackorzynski <adam@os.inf.tu-dresden.de>,
   3  *               Alexander Warg <warg@os.inf.tu-dresden.de>,
   4  *               Frank Mehnert <fm3@os.inf.tu-dresden.de>
   5  *     economic rights: Technische Universität Dresden (Germany)
   6  *
   7  * This file is part of TUD:OS and distributed under the terms of the
   8  * GNU General Public License 2.
   9  * Please see the COPYING-GPL-2 file for details.
  10  */
  11 #ifndef REGION_H
  12 #define REGION_H
  13
  14 #include <l4/sys/compiler.h>
  15 #include <l4/sys/l4int.h>
  16
  17 #include "types.h"
  18
  19 /** Region in memory. */
  20 class Region
  21 {
  22 public:
  23   enum Type { No_mem, Kernel, Sigma0, Boot, Root, Arch, Ram, Info };
  24
  25   /** Basic noop constructor, to be able to have array without ini code */
  26   Region() {}
  27
  28   /** Create an invalid region. */
  29   Region(Type) : _begin(0), _end(0) {}
  30
  31   /** Create a 1byte region at begin, basically for lookups */
  32   Region(unsigned long long begin)
  33   : _begin(begin), _end(begin), _name(0), _t(No_mem), _s(0)
  34   {}
  35
  36   /** Create a 1byte region for address \a ptr.
  37    * @param ptr the start address for the 1byte region.
  38    */
  39   Region(void const *ptr)
  40   : _begin((l4_addr_t)ptr), _end((l4_addr_t)ptr), _name(0), _t(No_mem), _s(0)
  41   {}
  42
  43   /** Create a fully fledged region.
  44    * @param begin The start address.
  45    * @param end The address of the last byte in the region.
  46    * @param name The name for the region (usually the binary name).
  47    * @param t The type of the region.
  48    * @param sub The subtype of the region.
  49    */
  50   Region(unsigned long long begin, unsigned long long end,
  51          char const *name = 0, Type t = No_mem, short sub = 0)
  52   : _begin(begin), _end(end), _name(name), _t(t), _s(sub)
  53   {}
  54
  55   /**
  56    * Create a region ...
  57    * @param other a region to copy the name, the type, and the sub_type from
  58    * @param begin the start address of the new region
  59    * @param end the end address (inclusive) of the new region
  60    */
  61   Region(Region const &other, unsigned long long begin, unsigned long long end)
  62   : _begin(begin), _end(end), _name(other._name), _t(other._t), _s(other._s)
  63   {}
  64
  65   /**
  66    * Create a region...
  67    * @param begin The start address.
  68    * @param end The address of the first byte after the region.
  69    * @param name The name for the region (usually the binary name).
  70    * @param t The type of the region.
  71    * @param sub The subtype of the region.
  72    */
  73   static Region n(unsigned long long begin,
  74                   unsigned long long end, char const *name = 0,
  75                   Type t = No_mem, short sub = 0)
  76   { return Region(begin, end - 1, name, t, sub); }
  77
  78   /**
  79    * Create a region (using start and end pointers)
  80    * @param begin start address
  81    * @param end the address of the last byte in the region
  82    * @param name The name of the region
  83    * @param t the type of the region
  84    * @param sub the subtype of the region
  85    */
  86   static Region n(void const *begin,
  87                   void const *end, char const *name = 0,
  88                   Type t = No_mem, short sub = 0)
  89   { return Region((l4_addr_t)begin, (l4_addr_t)end - 1, name, t, sub); }
  90
  91   /**
  92    * Create a region from start and size.
  93    * @param begin the start address of the region
  94    * @param size the size of the region in bytes
  95    * @param name the name of the region
  96    * @param t the type of the region
  97    * @param sub the subtype of the region
  98    */
  99   static Region start_size(unsigned long long begin, unsigned long size,
 100                            char const *name = 0, Type t = No_mem,
 101                            short sub = 0)
 102   { return Region(begin, begin + size - 1, name, t, sub); }
 103
 104   /**
 105    * Create a region for the given object.
 106    * @param begin a pointer to the object that shall be covered
 107    *              (the size of the region will be sizeof(T))
 108    * @param name the name of the region
 109    * @param t the type of theregion
 110    * @param sub the subtype of the region
 111    */
 112   template< typename T >
 113   static Region from_ptr(T const *begin, char const *name = 0,
 114                          Type t = No_mem, short sub = 0)
 115   { return Region::start_size((l4_addr_t)begin, sizeof(T), name, t, sub); }
 116
 117   /**
 118    * Create a region for an array of objects.
 119    * @param begin pointer to the first element of the array
 120    * @param size the number of elements in the array (the size of the
 121    *             whole region will be size * sizeof(T))
 122    * @param name the name of the region
 123    * @param t the type of the region
 124    * @param sub the subtype of the region
 125    */
 126   template< typename T >
 127   static Region array(T const *begin, unsigned long size, char const *name = 0,
 128                       Type t = No_mem, short sub = 0)
 129   {
 130     return Region::start_size((l4_addr_t)begin, sizeof(T) * size,
 131                               name, t, sub);
 132   }
 133
 134   /** Get the start address. */
 135   unsigned long long begin() const { return _begin; }
 136   /** Get the address of the last byte. */
 137   unsigned long long end() const { return _end; }
 138   /** Set the start address. */
 139   void begin(unsigned long long b) { _begin = b; }
 140   /** Set the address of the last byte. */
 141   void end(unsigned long long e) { _end = e; }
 142   /** Get the name of the region. */
 143   char const *name() const { return _name; }
 144   /** Get size of the region */
 145   unsigned long long size() const { return _end - _begin + 1; }
 146   /** Set the name of the region. */
 147   void name(char const *name) { _name = name; }
 148   /** Get the type of the region. */
 149   Type type() const { return (Type)(_t); }
 150   /** Get the subtype of the region. */
 151   short sub_type() const { return _s; }
 152   /** Set the subtype of the region. */
 153   void sub_type(short s) { _s = s; }
 154
 155   /** Print the region [begin; end] */
 156   void print() const;
 157
 158   /** Print the region verbose (with name and type). */
 159   void vprint() const;
 160
 161   /** Compare two regions. */
 162   bool operator < (Region const &o) const
 163   { return end() < o.begin(); }
 164
 165   /** Check for an overlap. */
 166   bool overlaps(Region const &o) const
 167   { return !(*this < o) && !(o < *this); }
 168
 169   /** Test if o is a sub-region of ourselves. */
 170   bool contains(Region const &o) const
 171   { return begin() <= o.begin() && end() >= o.end(); }
 172
 173   /** Calculate the intersection. */
 174   Region intersect(Region const &o) const
 175   {
 176     if (!overlaps(o))
 177       return Region(No_mem);
 178
 179     return Region(begin() > o.begin() ? begin() : o.begin(),
 180         end() < o.end() ? end() : o.end(),
 181         name(), type(), sub_type());
 182   }
 183
 184   /** Check if the region is invalid */
 185   bool invalid() const { return begin()==0 && end()==0; }
 186
 187 private:
 188   unsigned long long _begin, _end;
 189   char const *_name;
 190   short _t, _s;
 191 };
 192
 193
 194 /** List of memory regions, based on an fixed size array. */
 195 class Region_list
 196 {
 197 public:
 198   /**
 199    * Initialize the region list, using the array of given size
 200    * as backing store.
 201    */
 202   void init(Region *store, unsigned size,
 203             const char *name,
 204             unsigned long long max_combined_size = ~0ULL,
 205             unsigned long long address_limit = ~0ULL)
 206   {
 207     _reg = _end = store;
 208     _max = _reg + size;
 209     _name = name;
 210     _max_combined_size = max_combined_size;
 211     _address_limit = address_limit;
 212     _combined_size = 0;
 213   }
 214
 215   /** Helper template for array parameters
 216    *
 217    * This helper allows to access the type and the size of compile-time
 218    * bound arrays. In particular used as parameters.
 219    */
 220   template< typename T >
 221     struct Array_type_helper;
 222
 223   template< typename T, unsigned SZ >
 224     struct Array_type_helper<T[SZ]> {
 225       enum { size = SZ };
 226       typedef T type;
 227     };
 228
 229   /**
 230    * Initialize the region list, using a region array as store
 231    *
 232    * @param store the array for the regoion backing store.
 233    * @param name the name of the region list for output
 234    * @param max_combined_size max sum of bytes in this list
 235    * @param address_limit maximum allowed address in this list
 236    */
 237   template<typename STORE>
 238   void init(STORE &store,
 239             const char *name,
 240             unsigned long long max_combined_size = ~0ULL,
 241             unsigned long long address_limit = ~0ULL)
 242   {
 243     init(store, Array_type_helper<STORE>::size, name,
 244          max_combined_size, address_limit);
 245   }
 246
 247   /** Search for a region that overlaps o. */
 248   Region *find(Region const &o) const;
 249
 250   /** Search for the region that contains o. */
 251   Region *contains(Region const &o);
 252
 253   /**
 254    * Search for a memory region not overlapping any known region,
 255    * within search.
 256    */
 257   unsigned long long find_free(Region const &search,
 258                                unsigned long long size, unsigned align) const;
 259
 260   /**
 261    * Search for a memory region not overlapping any know region, starting
 262    * from the end of the search region.
 263    */
 264   unsigned long long find_free_rev(Region const &search, unsigned long long _size,
 265                                    unsigned align) const;
 266   /**
 267    * Add a new region, with a upper limit check and verboseness.
 268    */
 269   void add(Region const &r, bool may_overlap = false);
 270
 271   bool sub(Region const &r);
 272
 273   /** Dump the whole region list. */
 274   void dump();
 275
 276   /** Get the begin() iterator. */
 277   Region *begin() const { return _reg; }
 278   /** Get the end() iterator. */
 279   Region *end() const { return _end; }
 280
 281   /** Remove the region given by the iterator r. */
 282   Region *remove(Region *r);
 283
 284   /** Sort the region list (does bubble sort). */
 285   void sort();
 286
 287   /** Optimize the region list.
 288    * Basically merges all regions with the same type, subtype, and name
 289    * that have a begin and end address on the same memory page.
 290    */
 291   void optimize();
 292
 293 protected:
 294   Region *_end;
 295   Region *_max;
 296   Region *_reg;
 297
 298   const char *_name;
 299   unsigned long long _max_combined_size;
 300   unsigned long long _address_limit;
 301   unsigned long long _combined_size;
 302
 303 private:
 304   void swap(Region *a, Region *b);
 305
 306   /**
 307    * Add a new memory region to the list. The new region must not overlap
 308    * any known region.
 309    */
 310   void add_nolimitcheck(Region const &r, bool may_overlap = false);
 311 };
 312
 313 #endif