l4/pkg/bootstrap/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 };
  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 fully fledged region.
  37    * @param begin The start address.
  38    * @param end The address of the last byte in the region.
  39    * @param name The name for the region (usually the binary name).
  40    * @param t The type of the region.
  41    * @param sub The subtype of the region.
  42    */
  43   Region(unsigned long long begin, unsigned long long end,
  44          char const *name = 0, Type t = No_mem, char sub = 0)
  45   : _begin(begin), _end(end), _name(name), _t(t), _s(sub)
  46   {}
  47
  48   /**
  49    * Create a region...
  50    * @param begin The start address.
  51    * @param end The address of the first byte after the region.
  52    * @param name The name for the region (usually the binary name).
  53    * @param t The type of the region.
  54    * @param sub The subtype of the region.
  55    */
  56   static Region n(unsigned long long begin,
  57                   unsigned long long end, char const *name = 0,
  58                   Type t = No_mem, char sub = 0)
  59   { return Region(begin, end - 1, name, t, sub); }
  60
  61   /** Get the start address. */
  62   unsigned long long begin() const { return _begin; }
  63   /** Get the address of the last byte. */
  64   unsigned long long end() const { return _end; }
  65   /** Set the start address. */
  66   void begin(unsigned long long b) { _begin = b; }
  67   /** Set the address of the last byte. */
  68   void end(unsigned long long e) { _end = e; }
  69   /** Get the name of the region. */
  70   char const *name() const { return _name; }
  71   /** Get size of the region */
  72   unsigned long long size() const { return _end - _begin + 1; }
  73   /** Set the name of the region. */
  74   void name(char const *name) { _name = name; }
  75   /** Get the type of the region. */
  76   Type type() const { return (Type)(_t); }
  77   /** Get the subtype of the region. */
  78   char sub_type() const { return _s; }
  79
  80   /** Print the region [begin; end] */
  81   void print() const;
  82
  83   /** Print the region verbose (with name and type). */
  84   void vprint() const;
  85
  86   /** Compare two regions. */
  87   bool operator < (Region const &o) const
  88   { return end() < o.begin(); }
  89
  90   /** Check for an overlap. */
  91   bool overlaps(Region const &o) const
  92   { return !(*this < o) && !(o < *this); }
  93
  94   /** Test if o is a sub-region of ourselves. */
  95   bool contains(Region const &o) const
  96   { return begin() <= o.begin() && end() >= o.end(); }
  97
  98   /** Calculate the intersection. */
  99   Region intersect(Region const &o) const
 100   {
 101     if (!overlaps(o))
 102       return Region(No_mem);
 103
 104     return Region(begin() > o.begin() ? begin() : o.begin(),
 105         end() < o.end() ? end() : o.end(),
 106         name(), type(), sub_type());
 107   }
 108
 109   /** Check if the region is invalid */
 110   bool invalid() const { return begin()==0 && end()==0; }
 111
 112 private:
 113   unsigned long long _begin, _end;
 114   char const *_name;
 115   char _t, _s;
 116 };
 117
 118
 119 /** List of memory regions, based on an fixed size array. */
 120 class Region_list
 121 {
 122 public:
 123   /**
 124    * Initialize the region list, using the array of given size
 125    * as backing store.
 126    */
 127   void init(Region *store, unsigned size,
 128             const char *name,
 129             unsigned long long max_combined_size = ~0ULL,
 130             unsigned long long address_limit = ~0ULL)
 131   {
 132     _reg = _end = store;
 133     _max = _reg + size;
 134     _name = name;
 135     _max_combined_size = max_combined_size;
 136     _address_limit = address_limit;
 137     _combined_size = 0;
 138   }
 139
 140   /** Search for a region that overlaps o. */
 141   Region *find(Region const &o);
 142
 143   /** Search for the region that contains o. */
 144   Region *contains(Region const &o);
 145
 146   /**
 147    * Search for a memory region not overlapping any known region,
 148    * within search.
 149    */
 150   unsigned long long find_free(Region const &search,
 151                                unsigned long long size, unsigned align);
 152
 153   /**
 154    * Add a new region, with a upper limit check and verboseness.
 155    */
 156   void add(Region const &r, bool may_overlap = false);
 157
 158   /** Dump the whole region list. */
 159   void dump();
 160
 161   /** Get the begin() iterator. */
 162   Region *begin() const { return _reg; }
 163   /** Get the end() iterator. */
 164   Region *end() const { return _end; }
 165
 166   /** Remove the region given by the iterator r. */
 167   void remove(Region *r);
 168
 169   /** Sort the region list (does bubble sort). */
 170   void sort();
 171
 172   /** Optimize the region list.
 173    * Basically merges all regions with the same type, subtype, and name
 174    * that have a begin and end address on the same memory page.
 175    */
 176   void optimize();
 177
 178 protected:
 179   Region *_end;
 180   Region *_max;
 181   Region *_reg;
 182
 183   const char *_name;
 184   unsigned long long _max_combined_size;
 185   unsigned long long _address_limit;
 186   unsigned long long _combined_size;
 187
 188 private:
 189   void swap(Region *a, Region *b);
 190   unsigned long long next_free(unsigned long long start);
 191   bool test_fit(unsigned long long start, unsigned long long _size);
 192
 193   /**
 194    * Add a new memory region to the list. The new region must not overlap
 195    * any known region.
 196    */
 197   void add_nolimitcheck(Region const &r, bool may_overlap = false);
 198 };
 199
 200 #endif