kernel/range_allocator.cpp

   1 /*
   2 lightOS kernel
   3 Copyright (C) 2007-2009 Jörg Pfähler
   4
   5 This program is free software; you can redistribute it and/or
   6 modify it under the terms of the GNU General Public License
   7 as published by the Free Software Foundation; either version 2
   8 of the License, or (at your option) any later version.
   9
  10 This program is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU General Public License for more details.
  14
  15 You should have received a copy of the GNU General Public License
  16 along with this program; if not, write to the Free Software
  17 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
  18 */
  19 #include <cstdint>
  20 #include <kernel/log.hpp>
  21 #include <kernel/range_allocator.hpp>
  22 #include <kernel/virtual_memory.hpp>
  23 using namespace std;
  24 using kernel::range_allocator;
  25 using kernel::virtual_memory;
  26
  27 SINGLETON_INSTANCE(kernel::range_allocator);
  28
  29 range_allocator::range_allocator()
  30 {
  31 }
  32
  33 range_allocator::~range_allocator()
  34 {
  35 }
  36
  37 // TODO: Locks
  38
  39 void *range_allocator::allocate_range(size_t size,
  40                                       size_t Type)
  41 {
  42   list<range> *Container = 0;
  43
  44   // Which container?
  45   if (Type == lightOS::memory::below_1mb)Container = &m_below1Mb;
  46   else if (Type == lightOS::memory::below_16mb)Container = &m_below16Mb;
  47   else
  48   {
  49     ERROR("range_allocator: invalid memory range type");
  50     return 0;
  51   }
  52
  53   // LOCK(mLock);
  54
  55     // Exact match
  56     list<range>::iterator i = Container->begin();
  57     list<range>::iterator best_fit = Container->end();
  58     for (;i != Container->end();i++)
  59       if ((*i).size == size)
  60       {
  61         void *page = reinterpret_cast<void*>((*i).address);
  62         Container->erase(i);
  63         //UNLOCK(mLock);
  64         return page;
  65       }
  66       else if ((*i).size > size &&
  67           (best_fit == Container->end() || (*i).size < (*best_fit).size))
  68       {
  69         best_fit = i;
  70       }
  71
  72     // Best fit?
  73     if (best_fit != Container->end())
  74     {
  75       void *page = reinterpret_cast<void*>((*best_fit).address);
  76       (*best_fit).size -= size;
  77       (*best_fit).address += size * virtual_memory::page_size;
  78       //UNLOCK(mLock);
  79       return page;
  80     }
  81
  82   //UNLOCK(mLock);
  83
  84   ERROR("range_allocator: no memory range found");
  85   return 0;
  86 }
  87 void range_allocator::free_range(uintptr_t page,
  88                 size_t size)
  89 {
  90   list<range> *Container = 0;
  91
  92   // Which container?
  93   if (page < 0x100000)Container = &m_below1Mb;
  94   else if (page < 0x1000000)Container = &m_below16Mb;
  95   else
  96   {
  97     ERROR("range_allocator: freeing range 0x" << hex(page) << " " << dec(size) << " pages");
  98     return;
  99   }
 100
 101   //LOCK(mLock);
 102
 103     // Can we add this somewhere?
 104     list<range>::iterator i = Container->begin();
 105     list<range>::iterator before = Container->end();
 106     list<range>::iterator after = Container->end();
 107     for (;i != Container->end();i++)
 108     {
 109       if ((*i).address == (page + size * virtual_memory::page_size))
 110         after = i;
 111       else if (((*i).address + (*i).size * virtual_memory::page_size) == page)
 112         before = i;
 113     }
 114
 115     if (before != Container->end())
 116     {
 117       (*before).size += size;
 118       if (after != Container->end())
 119       {
 120         (*before).size += (*after).size;
 121         Container->erase(after);
 122       }
 123     }
 124     else if (after != Container->end())
 125     {
 126       (*after).address = page;
 127       (*after).size += size;
 128     }
 129     else
 130     {
 131       // Add it to the end of the list
 132       range Range;
 133       Range.size = size;
 134       Range.address = page;
 135       Container->push_front(Range);
 136     }
 137
 138   //UNLOCK(mLock);
 139 }
 140 void range_allocator::remove_range( uintptr_t page,
 141                   size_t size)
 142 {
 143   list<range> *Container = 0;
 144
 145   // Which container?
 146   if (page < 0x100000)Container = &m_below1Mb;
 147   else if (page < 0x1000000)Container = &m_below16Mb;
 148   else
 149   {
 150     ERROR("range_allocator: removing range 0x" << hex(page) << " " << dec(size) << " pages");
 151     return;
 152   }
 153
 154   for (size_t i = 0;i < size;i++)
 155     remove_page(page + i * virtual_memory::page_size, Container);
 156 }
 157 void range_allocator::remove_page(uintptr_t page, list<range> *Container)
 158 {
 159   //LOCK(mLock);
 160
 161     list<range>::iterator i = Container->begin();
 162     for (;i != Container->end();i++)
 163     {
 164       if ((*i).address == page)
 165       {
 166         (*i).address = page + virtual_memory::page_size;
 167         --(*i).size;
 168         //UNLOCK(mLock);
 169         return;
 170       }
 171       else if (((*i).address + (*i).size * virtual_memory::page_size) == page)
 172       {
 173         --(*i).size;
 174         //UNLOCK(mLock);
 175         return;
 176       }
 177       else if ((*i).address < page && ((*i).address + (*i).size * virtual_memory::page_size) > page)
 178       {
 179         size_t newsize = (page - (*i).address) / virtual_memory::page_size;
 180         range Range;
 181         Range.address = page + virtual_memory::page_size;
 182         Range.size = (*i).size - newsize - 1;
 183         Container->push_back(Range);
 184         (*i).size = newsize;
 185         //UNLOCK(mLock);
 186         return;
 187       }
 188     }
 189
 190   //UNLOCK(mLock);
 191 }
 192 range_allocator::range range_allocator::get_range(size_t n)
 193 {
 194   //LOCK(mLock);
 195
 196     list<range>::iterator i;
 197     if (n < m_below1Mb.size())
 198       i = m_below1Mb.begin();
 199     else if ((n -= m_below1Mb.size()) < m_below16Mb.size())
 200       i = m_below16Mb.begin();
 201
 202     while (n-- != 0)++i;
 203
 204     range Range(*i);
 205
 206   //UNLOCK(mLock);
 207
 208   return Range;
 209 }