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