3 Copyright (C) 2007-2009 Jörg Pfähler
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.
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.
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
20 #include <kernel/log.hpp>
21 #include <kernel/range_allocator.hpp>
22 #include <kernel/virtual_memory.hpp>
24 using kernel::range_allocator
;
25 using kernel::virtual_memory
;
27 SINGLETON_INSTANCE(kernel::range_allocator
);
29 range_allocator::range_allocator()
33 range_allocator::~range_allocator()
39 void *range_allocator::allocate_range(size_t size
,
42 list
<range
> *Container
= 0;
45 if (Type
== lightOS::memory::below_1mb
)Container
= &m_below1Mb
;
46 else if (Type
== lightOS::memory::below_16mb
)Container
= &m_below16Mb
;
49 ERROR("range_allocator: invalid memory range type");
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
)
61 void *page
= reinterpret_cast<void*>((*i
).address
);
66 else if ((*i
).size
> size
&&
67 (best_fit
== Container
->end() || (*i
).size
< (*best_fit
).size
))
73 if (best_fit
!= Container
->end())
75 void *page
= reinterpret_cast<void*>((*best_fit
).address
);
76 (*best_fit
).size
-= size
;
77 (*best_fit
).address
+= size
* virtual_memory::page_size
;
84 ERROR("range_allocator: no memory range found");
87 void range_allocator::free_range(uintptr_t page
,
90 list
<range
> *Container
= 0;
93 if (page
< 0x100000)Container
= &m_below1Mb
;
94 else if (page
< 0x1000000)Container
= &m_below16Mb
;
97 ERROR("range_allocator: freeing range 0x" << hex(page
) << " " << dec(size
) << " pages");
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
++)
109 if ((*i
).address
== (page
+ size
* virtual_memory::page_size
))
111 else if (((*i
).address
+ (*i
).size
* virtual_memory::page_size
) == page
)
115 if (before
!= Container
->end())
117 (*before
).size
+= size
;
118 if (after
!= Container
->end())
120 (*before
).size
+= (*after
).size
;
121 Container
->erase(after
);
124 else if (after
!= Container
->end())
126 (*after
).address
= page
;
127 (*after
).size
+= size
;
131 // Add it to the end of the list
134 Range
.address
= page
;
135 Container
->push_front(Range
);
140 void range_allocator::remove_range( uintptr_t page
,
143 list
<range
> *Container
= 0;
146 if (page
< 0x100000)Container
= &m_below1Mb
;
147 else if (page
< 0x1000000)Container
= &m_below16Mb
;
150 ERROR("range_allocator: removing range 0x" << hex(page
) << " " << dec(size
) << " pages");
154 for (size_t i
= 0;i
< size
;i
++)
155 remove_page(page
+ i
* virtual_memory::page_size
, Container
);
157 void range_allocator::remove_page(uintptr_t page
, list
<range
> *Container
)
161 list
<range
>::iterator i
= Container
->begin();
162 for (;i
!= Container
->end();i
++)
164 if ((*i
).address
== page
)
166 (*i
).address
= page
+ virtual_memory::page_size
;
171 else if (((*i
).address
+ (*i
).size
* virtual_memory::page_size
) == page
)
177 else if ((*i
).address
< page
&& ((*i
).address
+ (*i
).size
* virtual_memory::page_size
) > page
)
179 size_t newsize
= (page
- (*i
).address
) / virtual_memory::page_size
;
181 Range
.address
= page
+ virtual_memory::page_size
;
182 Range
.size
= (*i
).size
- newsize
- 1;
183 Container
->push_back(Range
);
192 range_allocator::range
range_allocator::get_range(size_t n
)
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();