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