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

   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 #include <stdio.h>
  12 #include <string.h>
  13 #include <assert.h>
  14
  15 #include "panic.h"
  16 #include <l4/util/l4_macros.h>
  17
  18 #include "region.h"
  19 #include "module.h"
  20
  21 unsigned long long
  22 Region_list::find_free(Region const &search, unsigned long long _size,
  23                        unsigned align) const
  24 {
  25   unsigned long long start = search.begin();
  26   unsigned long long end   = search.end();
  27   while (1)
  28     {
  29       start = (start + (1ULL << align) -1) & ~((1ULL << align)-1);
  30
  31       if (start + _size - 1 > end)
  32         return 0;
  33
  34       if (0)
  35         printf("try start %p\n", (void *)start);
  36
  37       Region *z = find(Region::start_size(start, _size));
  38       if (!z)
  39         return start;
  40
  41       start = z->end() + 1;
  42     }
  43 }
  44
  45 unsigned long long
  46 Region_list::find_free_rev(Region const &search, unsigned long long _size,
  47                            unsigned align) const
  48 {
  49   unsigned long long start = search.begin();
  50   unsigned long long end   = search.end();
  51   while (1)
  52     {
  53       end -= _size - 1;
  54       end &= ~((1ULL << align)-1);
  55
  56       if (end < start)
  57         return 0;
  58
  59       if (0)
  60         printf("try start %p\n", (void *)end);
  61
  62       Region *z = find(Region::start_size(end, _size));
  63       if (!z)
  64         return end;
  65
  66       end = z->begin() - 1;
  67     }
  68 }
  69
  70 void
  71 Region_list::add_nolimitcheck(Region const &region, bool may_overlap)
  72 {
  73   Region const *r;
  74
  75   /* Do not add empty regions */
  76   if (region.begin() == region.end())
  77     return;
  78
  79   if (_end >= _max)
  80     {
  81       // try to merge adjacent regions to gain space
  82       optimize();
  83
  84       if (_end >= _max)
  85         panic("Bootstrap: %s: Region overflow\n", __func__);
  86     }
  87
  88   if (!may_overlap && (r = find(region)))
  89     {
  90       printf("  New region for list %s:\t", _name);
  91       region.vprint();
  92       printf("  overlaps with:         \t");
  93       r->vprint();
  94
  95       dump();
  96       panic("region overlap");
  97     }
  98
  99   *_end = region;
 100   ++_end;
 101   _combined_size += region.size();
 102 }
 103
 104 void
 105 Region_list::add(Region const &region, bool may_overlap)
 106 {
 107   Region mem = region;
 108
 109   if (mem.invalid())
 110     {
 111       printf("  WARNING: trying to add invalid region to %s list.\n", _name);
 112       return;
 113     }
 114
 115   if (mem.begin() > _address_limit)
 116     {
 117       printf("  Dropping '%s' region ", _name);
 118       mem.print();
 119       printf(" due to %lld MB address limit\n", _address_limit >> 20);
 120       return;
 121     }
 122
 123   if (mem.end() >= _address_limit)
 124     {
 125       printf("  Limiting '%s' region ", _name);
 126       mem.print();
 127       mem.end(_address_limit - 1);
 128       printf(" to ");
 129       mem.print();
 130       printf(" due to %lld MB address limit\n", _address_limit >> 20);
 131
 132     }
 133
 134   if (_combined_size >= _max_combined_size)
 135     {
 136       printf("  Dropping '%s' region ", _name);
 137       mem.print();
 138       printf(" due to %lld MB size limit\n", _max_combined_size >> 20);
 139       return;
 140     }
 141
 142   if (_combined_size + mem.size() > _max_combined_size)
 143     {
 144       printf("  Limiting '%s' region ", _name);
 145       mem.print();
 146       mem.end(mem.begin() + _max_combined_size - _combined_size - 1);
 147       printf(" to ");
 148       mem.print();
 149       printf(" due to %lld MB size limit\n", _max_combined_size >> 20);
 150     }
 151
 152   add_nolimitcheck(mem, may_overlap);
 153 }
 154
 155 Region *
 156 Region_list::find(Region const &o) const
 157 {
 158   for (Region *c = _reg; c < _end; ++c)
 159     if (c->overlaps(o))
 160       return c;
 161
 162   return 0;
 163 }
 164
 165 Region *
 166 Region_list::contains(Region const &o)
 167 {
 168   for (Region *c = _reg; c < _end; ++c)
 169     if (c->contains(o))
 170       return c;
 171
 172   return 0;
 173 }
 174
 175 void
 176 Region::print() const
 177 {
 178   printf("  [%9llx, %9llx] {%9llx}", begin(), end(), size());
 179 }
 180
 181 void
 182 Region::vprint() const
 183 {
 184   static char const *types[] = {"Gap   ", "Kern  ", "Sigma0",
 185                                 "Boot  ", "Root  ", "Arch  ", "Ram   ",
 186                                 "Info  " };
 187   printf("  ");
 188   print();
 189   printf(" %s ", types[type()]);
 190   if (name())
 191     {
 192       if (*name() == '.')
 193         printf("%s", name() + 1);
 194       else
 195         print_module_name(name(), "");
 196     }
 197   putchar('\n');
 198 }
 199
 200 void
 201 Region_list::dump()
 202 {
 203   Region const *i;
 204   Region const *j;
 205   unsigned long long min, mark = 0;
 206
 207   printf("Regions of list '%s'\n", _name);
 208   for (i = _reg; i < _end; ++i)
 209     {
 210       min = ~0;
 211       Region const *min_idx = 0;
 212       for (j = _reg; j < _end; ++j)
 213         if (j->begin() < min && j->begin() >= mark)
 214           {
 215             min     = j->begin();
 216             min_idx = j;
 217           }
 218       if (!min_idx)
 219         {
 220           i->vprint();
 221           continue;
 222         }
 223       min_idx->vprint();
 224       mark = min_idx->begin() + 1;
 225     }
 226 }
 227
 228 void
 229 Region_list::swap(Region *a, Region *b)
 230 {
 231   Region t = *a; *a = *b; *b = t;
 232 }
 233
 234 void
 235 Region_list::sort()
 236 {
 237   if (end() - begin() < 2)
 238     return;
 239   bool swapped;
 240
 241   Region *e = end() - 1;
 242
 243   do
 244     {
 245       swapped = false;
 246       for (Region *c = begin(); c < e; ++c)
 247         {
 248           Region *n = c; ++n;
 249           if (*n < *c)
 250             {
 251               swap(c,n);
 252               swapped = true;
 253             }
 254         }
 255     }
 256   while (swapped);
 257 }
 258
 259 Region *
 260 Region_list::remove(Region *r)
 261 {
 262   memmove(r, r+1, (end() - r - 1)*sizeof(Region));
 263   --_end;
 264   return r;
 265 }
 266
 267 void
 268 Region_list::optimize()
 269 {
 270   sort();
 271   Region *c = begin();
 272   while (c < end())
 273     {
 274       Region *n = c; ++n;
 275       if (n == end())
 276         return;
 277
 278       if (n->type() == c->type() && n->sub_type() == c->sub_type()
 279           && n->name() == c->name() &&
 280           l4_round_page(c->end()) >= l4_trunc_page(n->begin()))
 281         {
 282           c->end(n->end());
 283           remove(n);
 284         }
 285       else
 286         ++c;
 287     }
 288 }
 289
 290 bool
 291 Region_list::sub(Region const &r)
 292 {
 293   Region *c = contains(r);
 294   if (!c)
 295     return false;
 296
 297   if (c->begin() == r.begin() && c->end() == r.end())
 298     {
 299       remove(c);
 300       return true;
 301     }
 302
 303   if (c->begin() == r.begin())
 304     {
 305       c->begin(r.end() + 1);
 306       return true;
 307     }
 308
 309   if (c->end() == r.end())
 310     {
 311       c->end(r.begin() - 1);
 312       return true;
 313     }
 314
 315   Region tail(*c);
 316   tail.begin(r.end() + 1);
 317   c->end(r.begin() - 1);
 318   add(tail);
 319   return true;
 320 }