l4/pkg/sigma0/server/src/mem_man.cc

   1 /*
   2  * (c) 2008-2009 Adam Lackorzynski <adam@os.inf.tu-dresden.de>,
   3  *               Alexander Warg <warg@os.inf.tu-dresden.de>,
   4  *               Carsten Weinhold <weinhold@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 "mem_man.h"
  12 #include "globals.h"
  13
  14 #include <l4/cxx/iostream>
  15 #include <l4/sys/kdebug.h>
  16
  17 Mem_man Mem_man::_ram;
  18
  19 Region const *
  20 Mem_man::find(Region const &r, bool force) const
  21 {
  22   if (!r.valid())
  23     return 0;
  24
  25   Tree::Const_iterator n = _tree.find(r);
  26   if (n == _tree.end())
  27     return 0;
  28
  29   if (n->contains(r) || force)
  30     return &(*n);
  31
  32   return 0;
  33 }
  34
  35 bool
  36 Mem_man::add(Region const &r)
  37 {
  38   /* try to merge with prev region */
  39   Region rs = r;
  40   if (rs.start() > 0)
  41     {
  42       rs.start(rs.start()-1);
  43
  44       Tree::Node n = _tree.find_node(rs);
  45       if (n && n->owner() == r.owner())
  46         {
  47           r.start(n->start());
  48           int err = _tree.remove(*n);
  49           if (err < 0)
  50             { L4::cout << "err=" << err << " dump:\n"; dump();  enter_kdebug("BUG");}
  51         }
  52     }
  53
  54   /* try to merge with next region */
  55   rs = r;
  56   if (rs.end() + 1 != 0)
  57     {
  58       rs.end(rs.end()+1);
  59
  60       Tree::Node n = _tree.find_node(rs);
  61       if (n && n->owner() == r.owner())
  62         {
  63           r.end(n->end());
  64           int err = _tree.remove(*n);
  65           if (err < 0)
  66             { L4::cout << "err=" << err << " dump:\n"; dump();  enter_kdebug("BUG");}
  67         }
  68     }
  69
  70   /* do throw away regions owned by myself */
  71   if (r.owner() == sigma0_taskno)
  72     return true;
  73
  74   while (_tree.insert(r).second == -_tree.E_nomem)
  75     if (!ram()->morecore())
  76       {
  77         if (debug_errors)
  78           L4::cout << PROG_NAME": Out of memory\n";
  79         return false;
  80       }
  81
  82   return true;
  83 }
  84
  85 bool
  86 Mem_man::add_free(Region const &r)
  87 {
  88   if (!r.valid())
  89     return true;
  90
  91   // calculate the combined set of all overlapping regions within the tree
  92   while (1)
  93     {
  94       Tree::Node n = _tree.find_node(r);
  95
  96       if (!n)
  97         break;
  98
  99       if (n->start() < r.start())
 100         r.start(n->start());
 101       if (n->end() > r.end())
 102         r.end(n->end());
 103
 104       int err = _tree.remove(*n);
 105       if (err < 0)
 106         { L4::cout << "err=" << err << " dump:\n"; dump();  enter_kdebug("BUG");}
 107     }
 108
 109   return add(r);
 110 }
 111
 112 bool
 113 Mem_man::alloc_from(Region const *r2, Region const &_r)
 114 {
 115   Region r(_r);
 116   if (r2->owner() && r2->owner() != r.owner())
 117     return false;
 118
 119   if (r2->owner() == r.owner())
 120     return true;
 121
 122   if (r == *r2)
 123     {
 124       // L4::cout << "dump " << r << " " << *r2 << "\n"; dump();
 125       int err = _tree.remove(*r2);
 126       if (err < 0)
 127         { L4::cout << "err=" << err << " dump:\n"; dump(); enter_kdebug("BUG"); }
 128       return add(r);
 129     }
 130
 131   if (r.start() == r2->start())
 132     {
 133       r2->start(r.end()+1);
 134       //L4::cout << "move start to " << *r2 << '\n';
 135       add(r);
 136       return true;
 137     }
 138
 139   if (r.end() == r2->end())
 140     {
 141       r2->end(r.start()-1);
 142       //L4::cout << "shrink end to " << *r2 << '\n';
 143       add(r);
 144       return true;
 145     }
 146
 147   Region const nr(r.end()+1, r2->end(),r2->owner());
 148   r2->end(r.start()-1);
 149   //L4::cout << "split to " << *r2 << "; " << nr << '\n';
 150   if (r.valid())
 151     add(r);
 152   if (nr.valid())
 153     add(nr);
 154
 155   return true;
 156 }
 157
 158 unsigned long
 159 Mem_man::alloc(Region const &r, bool force)
 160 {
 161   if (!r.valid())
 162     return ~0UL;
 163   Region const *r2 = find(r, force);
 164   if (!r2)
 165     return ~0UL;
 166
 167   //L4::cout << "alloc_from(" << *r2 << ", " << r << ")\n";
 168   if (!alloc_from(r2, r))
 169     return ~0UL;
 170
 171   return r.start();
 172 }
 173
 174 bool
 175 Mem_man::reserve(Region const &r)
 176 {
 177   if (!r.valid())
 178     return false;
 179
 180   Region const *r2 = find(r, true);
 181   if (!r2)
 182     return true;
 183
 184   return alloc_from(r2, r);
 185 }
 186
 187
 188 bool
 189 Mem_man::morecore()
 190 {
 191   Tree::Item_type *n = 0;
 192   for (Tree::Rev_iterator i = _tree.rbegin(); i != _tree.rend(); ++i)
 193     {
 194         if (i->owner())
 195           continue;
 196
 197         l4_addr_t st = l4_round_page(i->start());
 198
 199         if (st < i->end() && i->end()-st >= L4_PAGESIZE-1)
 200           {
 201             n = &(*i);
 202             break;
 203           }
 204     }
 205
 206   if (!n)
 207     {
 208       if (debug_memory_maps)
 209         L4::cout << PROG_NAME": morecore did not find more free memory\n";
 210       return false;
 211     }
 212
 213   Region a = Region::bs(l4_round_page(n->end() - L4_PAGESIZE -1), L4_PAGESIZE, sigma0_taskno);
 214
 215   Page_alloc_base::free((void*)a.start());
 216
 217   alloc_from(n, a);
 218
 219   if (debug_memory_maps)
 220     L4::cout << PROG_NAME": morecore: total=" << Page_alloc_base::total() / 1024
 221              << "kB avail=" << Page_alloc_base::allocator()->avail() / 1024
 222              << "kB: added " << a << '\n';
 223   return true;
 224 }
 225
 226 unsigned long
 227 Mem_man::alloc_first(unsigned long size, unsigned owner)
 228 {
 229   Tree::Item_type *n = 0;
 230
 231   for (Tree::Iterator i = _tree.begin(); i != _tree.end(); ++i)
 232     {
 233       if (i->owner())
 234         continue;
 235
 236       // wrap-around?
 237       if ((i->start() + size - 1) < i->start())
 238         continue;
 239
 240       l4_addr_t st = (i->start() + size-1) & ~(size-1);
 241       //L4::cout << "test: " << (void*)st << " - " << i->end() << '\n';
 242
 243       if (st < i->end() && i->end() - st >= size - 1)
 244         {
 245           n = &(*i);
 246           break;
 247         }
 248     }
 249
 250   if (!n)
 251     return ~0UL;
 252
 253   Region a = Region::bs((n->start() + size-1) & ~(size-1), size, owner);
 254
 255   alloc_from(n, a);
 256
 257   return a.start();
 258 }
 259
 260 void
 261 Mem_man::dump()
 262 {
 263   for (Tree::Iterator i = _tree.begin(); i != _tree.end(); ++i)
 264     L4::cout << *i << '\n';
 265 }