l4/pkg/bootstrap/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 bool
  22 Region_list::test_fit(unsigned long long start, unsigned long long _size)
  23 {
  24   Region r(start, start + _size);
  25   for (Region const *c = _reg; c < _end; ++c)
  26     {
  27 #if 0
  28       printf("test [%p-%p] [%llx-%llx]\n", (char*)start, (char*)start + _size,
  29              c->begin(), c->end());
  30 #endif
  31
  32       if (c->overlaps(r))
  33         return false;
  34     }
  35   return true;
  36 }
  37
  38 unsigned long
  39 Region_list::next_free(unsigned long long start)
  40 {
  41   unsigned long long s = ~0ULL;
  42   for (Region const *c = _reg; c < _end; ++c)
  43     if (c->end() > start && c->end() < s)
  44       s = c->end();
  45
  46   return s;
  47 }
  48
  49 unsigned long long
  50 Region_list::find_free(Region const &search, unsigned long long _size,
  51                        unsigned align)
  52 {
  53   unsigned long long start = search.begin();
  54   unsigned long long end   = search.end();
  55   while (1)
  56     {
  57       start = (start + (1ULL << align) -1) & ~((1ULL << align)-1);
  58
  59       if (start + _size - 1 > end)
  60         return 0;
  61
  62       //printf("try start %p\n", (void*)start);
  63       if (test_fit(start, _size))
  64         return start;
  65
  66       start = next_free(start);
  67
  68       if (start == ~0UL)
  69         return 0;
  70     }
  71 }
  72
  73 void
  74 Region_list::add_nolimitcheck(Region const &region, bool may_overlap)
  75 {
  76   Region const *r;
  77
  78   /* Do not add empty regions */
  79   if (region.begin() == region.end())
  80     return;
  81
  82   if (_end >= _max)
  83     panic("Bootstrap: %s: Region overflow\n", __func__);
  84
  85   if (!may_overlap && (r = find(region)))
  86     {
  87       printf("  New region for list %s:\t", _name);
  88       region.vprint();
  89       printf("  overlaps with:         \t");
  90       r->vprint();
  91
  92       dump();
  93       panic("region overlap");
  94     }
  95
  96   *_end = region;
  97   ++_end;
  98 }
  99
 100 void
 101 Region_list::add(Region const &region, bool may_overlap)
 102 {
 103   Region mem = region;
 104
 105   if (mem.invalid())
 106     {
 107       printf("  WARNING: trying to add invalid region to %s list.\n", _name);
 108       return;
 109     }
 110
 111   if (mem.begin() >= _upper_limit)
 112     {
 113       printf("  Dropping %s region ", _name);
 114       mem.print();
 115       printf(" due to %lld MB limit\n", _upper_limit >> 20);
 116       return;
 117     }
 118
 119   if (mem.end() >= _upper_limit - 1)
 120     {
 121       printf("  Limiting %s region ", _name);
 122       mem.print();
 123       mem.end(_upper_limit - 1);
 124       printf(" to ");
 125       mem.print();
 126       printf(" due to %lld MB limit\n", _upper_limit >> 20);
 127     }
 128
 129   add_nolimitcheck(mem, may_overlap);
 130 }
 131
 132 Region *
 133 Region_list::find(Region const &o)
 134 {
 135   for (Region *c = _reg; c < _end; ++c)
 136     if (c->overlaps(o))
 137       return c;
 138
 139   return 0;
 140 }
 141
 142 Region *
 143 Region_list::contains(Region const &o)
 144 {
 145   for (Region *c = _reg; c < _end; ++c)
 146     if (c->contains(o))
 147       return c;
 148
 149   return 0;
 150 }
 151
 152 void
 153 Region::print() const
 154 {
 155   printf("  [%9llx, %9llx] {%9llx}", begin(), end(), end() - begin() + 1);
 156 }
 157
 158 void
 159 Region::vprint() const
 160 {
 161   static char const *types[] = {"Gap   ", "Kern  ", "Sigma0",
 162                                 "Boot  ", "Root  ", "Arch  ", "Ram   " };
 163   printf("  ");
 164   print();
 165   printf(" %s ", types[type()]);
 166   if (name())
 167     {
 168       if (*name() == '.')
 169         printf("%s", name() + 1);
 170       else
 171         print_module_name(name(), "");
 172     }
 173   putchar('\n');
 174 }
 175
 176 void
 177 Region_list::dump()
 178 {
 179   Region const *i;
 180   Region const *j;
 181   Region const *min_idx;
 182   unsigned long long min, mark = 0;
 183
 184   printf("Regions of list %s\n", _name);
 185   for (i = _reg; i < _end; ++i)
 186     {
 187       min = ~0;
 188       min_idx = 0;
 189       for (j = _reg; j < _end; ++j)
 190         if (j->begin() < min && j->begin() >= mark)
 191           {
 192             min     = j->begin();
 193             min_idx = j;
 194           }
 195       if (!min_idx)
 196         printf("Check region dump\n");
 197       min_idx->vprint();
 198       mark = min_idx->begin() + 1;
 199     }
 200 }
 201
 202 void
 203 Region_list::swap(Region *a, Region *b)
 204 {
 205   Region t = *a; *a = *b; *b = t;
 206 }
 207
 208 void
 209 Region_list::sort()
 210 {
 211   if (end() - begin() < 2)
 212     return;
 213   bool swapped;
 214
 215   Region *e = end() - 1;
 216
 217   do
 218     {
 219       swapped = false;
 220       for (Region *c = begin(); c < e; ++c)
 221         {
 222           Region *n = c; ++n;
 223           if (*n < *c)
 224             {
 225               swap(c,n);
 226               swapped = true;
 227             }
 228         }
 229     }
 230   while (swapped);
 231 }
 232
 233 void
 234 Region_list::remove(Region *r)
 235 {
 236   memmove(r, r+1, (end() - r - 1)*sizeof(Region));
 237   --_end;
 238 }
 239
 240 void
 241 Region_list::optimize()
 242 {
 243   sort();
 244   Region *c = begin();
 245   while (c < end())
 246     {
 247       Region *n = c; ++n;
 248       if (n == end())
 249         return;
 250
 251       if (n->type() == c->type() && n->sub_type() == c->sub_type()
 252           && n->name() == c->name() &&
 253           l4_round_page(c->end()) >= l4_trunc_page(n->begin()))
 254         {
 255           c->end(n->end());
 256           remove(n);
 257         }
 258       else
 259         ++c;
 260     }
 261 }
 262