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

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